[Image-SIG] Flood fill with threshold

[Yury V. Zaytsev]

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.
    GIMP software is licensed under GPL.
    """

    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