10
\$\begingroup\$

I am starting with a starting colour, a target colour and a starting position in an image. I want to change every contiguous pixel if it is close to the starting colour.

Imagine a stop sign. It has white letters on a red background. But the red is faded to a bunch of different reds. It should work that all of the red around the letters is one shape to be filled any colour, each letter is another shape to be coloured, and the holes of the O and P should also be shapes to be coloured. If I picked a midrange red from the stop sign and my starting point is on the outside of the letters, I would want all the outside red to be changed to the target colour.

So I used colormath to do a delta_e on each pixel to see if it is less than the max acceptable delta, and it works. However, it is painfully slow. I was thinking instead of doing a delta_e on each pixel I could do a histogram of all the colours and then have some sort of look up table. However, I am brand spankin new to Python and I was hoping to get some help with how I would do that.

Please help optimize it for speed.

from colormath.color_objects import RGBColor
import Image


def floodFill(x,y, d,e,f, g,h,i, image):
    toFill = set()
    alreadyfilled = set()
    toFill.add((x,y))
    image = Image.open(image)
    xsize, ysize = image.size
    print(xsize,ysize)
    print(image.getpixel((x,y)))
    while (toFill):
        (x,y) = toFill.pop()
        alreadyfilled.add((x,y))
        #print (x,y)
        (a,b,c) = image.getpixel((x,y))
        if not (FindDeltaColor(a,b,c,d,e,f) < 50):
            continue
        image.putpixel((x,y), (g,h,i))
        if x != 0:
            if (x-1,y) not in alreadyfilled:
                toFill.add((x-1,y))
        if y != 0:
            if (x,y-1) not in alreadyfilled:
                toFill.add((x,y-1))
        if x != (xsize-1):
            if (x+1,y) not in alreadyfilled:
                toFill.add((x+1,y))
        if y != (ysize-1):
            if (x,y+1) not in alreadyfilled:
                toFill.add((x,y+1))
    return image


def FindDeltaColor(r1,g1,b1,r2,g2,b2):
    rgb1 = RGBColor(r1,g1,b1, rgb_type='sRGB')
    rgb2 = RGBColor(r2,g2,b2, rgb_type='sRGB')
    lab1 = rgb1.convert_to('lab', target_illuminant='D50')
    lab2 = rgb2.convert_to('lab', target_illuminant='D50')
    return lab1.delta_e(lab2, mode='cie1994')


newimg = floodFill(1,1,255,255,255,245,224,60,original.jpg' )
newimg.save(r'midway.jpg')
img = floodFill(205,350,0,0,0,45,178,191,r'midway.jpg')
img.save(r'floodfill.jpg')
\$\endgroup\$
5
\$\begingroup\$

numpy and skimage can do this quite fast. Without plotting the intermediate results in there, this runs in about 120ms.
Using some random stopsign image found from google: http://www.ecovelo.info/images/stop-sign.jpg
Using a formula from wikipedia to calculate color difference: http://en.wikipedia.org/wiki/Color_difference

from skimage.data import imread
from skimage.color import rgb2lab
from skimage.morphology import label
import numpy as np
import matplotlib.pyplot as plt

img = imread('stop-sign.jpg')
imgLab = rgb2lab(img)

fig = plt.figure()
fig.add_subplot(231)
plt.imshow(img)
plt.title("original image")

pos = (200, 270)
color = img[pos]
colorLab = rgb2lab(color[None, None, :])

#calculate deltaE for the whole image.
deltaE = np.sqrt(((imgLab - colorLab)**2).sum(axis=2))
fig.add_subplot(232)
plt.imshow(deltaE)
plt.title("Delta E of image")

#create a boolean mask of where deltaE is less than a given threshold
mask = np.where(deltaE < 50, True, False)
fig.add_subplot(233)
plt.imshow(mask.copy())
plt.title("mask of Delta E")

#connected labeling calculation, used to find all the pixels in the boolean mask connected to our starting position
label, nlabels = label(mask, 4, False, return_num=True)
fig.add_subplot(234)
plt.imshow(label)
plt.title("labeling")
#If the algorithm finds more than 1 label, we need to modify our mask.
if nlabels > 1:
    label_at_pos = label[pos]
    mask[label != label_at_pos] = False
    fig.add_subplot(235)
    plt.imshow(mask.copy())
    plt.title("mask connected with start position")

img[mask] = color
#Too see exactly what got filled, uncomment the next line
#img[~mask] = [0,0,0]

fig.add_subplot(236)
plt.imshow(img)
plt.title("Result")
plt.show()

output:
enter image description here

\$\endgroup\$
3
\$\begingroup\$

An optimization in here would be for you to cache the results of your FindDeltaColor lookup in a dictionary.

deltacache = dict()
.....
while ...
    (a,b,c) = image.getpixel((x,y))
    delta = deltacache.get((a,b,c));
    if delta is None:
        delta = FindDeltaColor(a,b,c,d,e,f)
        deltacache[(a,b,c)] = delta
    if delta < 50:
        continue

This optimization optimistically expects there to be a relatively small set of unique colours... but, even with worst case large colour bit-depths, and ranges, the dict will be not much larger than the values that are similar to the margin test anyway.

\$\endgroup\$
  • 1
    \$\begingroup\$ Well that worked quite well. I reduced running time from 1 minute 39 seconds to ... 9 seconds. Would I save even more time to read the image in as a numpy array instead of poking each pixel to see it's color? \$\endgroup\$ – sleepingbeauty Jan 21 '14 at 3:14
  • \$\begingroup\$ @sleepingbeauty frankly I don't know python very well at all (in fact, I actively avoid it).... but I know an algorithmic enhancement when I see one. So, as for numpy, that is more detail than I am familiar with... but I know some people... who know some people. \$\endgroup\$ – rolfl Jan 21 '14 at 3:18
  • \$\begingroup\$ you can get more coherency in the cache by quantizing A,B and C too, if the difference between (.81,.81,.79) and (.8, .8, .8) is not significant. Another possible option is to use lower resolution copies of the image as a quadtree to tell you where to look: if a pixel in a half-res image is more than (delta * 4) from your target color, none of the 4 pixels in the original image which made it up is likely to be one you want.... \$\endgroup\$ – theodox Jan 21 '14 at 22:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.