# [Image-SIG] Flood fill with threshold

Yury V. Zaytsev yury at shurup.com
Tue Apr 20 18:00:23 CEST 2010

```On Fri, 2010-04-16 at 08:47 -0700, Edward Cannon wrote:

> > Right know I have found Eric Raymond's flood fill code in ImgDraw.py
> > trying to adapt it to use a threshold, but it's not entirely clear how
> > to define distance in terms of colors. Maybe just as the distance
> > between vectors will do.
> I have found that works pretty well.

FYI, I have finished to code so that it actually works. I want to send
the solution I came up with to the list so that the others can benefit.

Interestingly enough I have found that COMPOSITE and HUE distances work
best for me depending on the circumstances. Enjoy!

import numpy as np
import colorsys as cs

def pixel_difference(col1, col2, threshold, select_criterion = "CRITERION_COMPOSITE"):
"""
Direct reimplementation of gimp-2.6.8/app/core/gimpimage-contiguous-region.c.
"""

if select_criterion == "CRITERION_COMPOSITE":
max = np.max(np.abs(col1 - col2))
elif select_criterion == "CRITERION_R":
max = np.max(np.abs(col1[0] - col2[0]))
elif select_criterion == "CRITERION_G":
max = np.max(np.abs(col1[1] - col2[1]))
elif select_criterion == "CRITERION_B":
max = np.max(np.abs(col1[2] - col2[2]))
elif select_criterion in ("CRITERION_H", "CRITERION_S", "CRITERION_V"):
av0, av1, av2 = cs.rgb_to_hsv( *col1 )
bv0, bv1, bv2 = cs.rgb_to_hsv( *col2 )
if select_criterion == "CRITERION_H":
dist1 = np.abs(av0 - bv0)
dist2 = np.abs(av0 - 360 - bv0)
dist3 = np.abs(av0 - bv0 + 360)
max = np.min( (dist1, dist2) )
if (max > dist3):
max = dist3
elif select_criterion == "CRITERION_S":
max = np.abs(av1 - bv1)
elif select_criterion == "CRITERION_V":
max = np.abs(av2 - bv2)
else:
raise ValueError("Invalid select_criterion supplied!")

if (max < threshold):
return True
else:
return False

def floodfill(pixels, seed, value, threshold, criterion = "CRITERION_COMPOSITE", bitness = 8, return_region = False):
"""
Fill bounded region, based on an implementation by Eric S. Raymond:
http://mail.python.org/pipermail/image-sig/2005-September/003559.html

Licence unspecified, might count as public domain.
"""

max_color = np.power(2, bitness) - 1
threshold *= 1. / max_color
x, y = seed

# Color normalization, so that the colors are in the range [0, 1]
def normalize (color):
return [value * 1. / max_color for value in color]

# Get and normalize the color of the seed point
seed_normalized = normalize(pixels[x, y])
pixels[x, y] = value

if return_region:
roi = [ (x, y) ]

edge = [ (x, y) ]
while edge:
newedge = []
for (x, y) in edge:
for (s, t) in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)):
try:
item = pixels[s, t]
except IndexError:
pass
else:
if pixel_difference(seed_normalized, normalize(item), threshold, criterion) and \
not np.alltrue(item == value):
pixels[s, t] = value
newedge.append((s, t))
if return_region and not (s, t) in roi:
roi.append( (s, t) )
edge = newedge

if return_region:
return roi

--
Sincerely yours,
Yury V. Zaytsev

```