Help w/ Region/Island Detection via FloodFill Algorithm

Unity Engine
1

Hi All,

Using the alpha channel of the pixels of an image, I have created a 2-dimensional byte array where each byte is designated as a 0 or a 1 according to whether it’s alpha is 0 (invisible) or not (!=0). The 1s are clustered in groups were the non-transparent parts of the image are, but these parts are not necessarily all connected to one another. What I’m trying to do is detect how many unique clusters (or islands) there are. This is sometimes known as blob extraction or connected component labeling. I’m currently going through all the bytes in the 2d array and when I find a 1, I start floodfilling.

My trouble is, when do I increment the regionCounter so that the next pass will skip the cluster I just labelled in the first pass. I figure the regionCounter should increment when a region is done being labelled, but how do I know when a region is done being labelled? In other words, where should I put the “regionCounter++”?

Note: I’m starting the regionCounter at 2 because I’m trying to turn the first batch of 1s into 2s, then the next into 3s through the increment step.

Any hints?

public byte[,] map;
public int regionCounter = 2;

public void FindRegions () {
            for (int y = 1; y < this.map.GetLength(1)-1; y++) {
                for (int x = 1; x < this.map.GetLength(0)-1; x++) {
                    FloodFill(x,y,1,(byte)regionCounter);
                }
            }   
    }


    public void FloodFill(int x, int y, byte targetNumber, byte replacementNumber) {
        //if(x>0 && x < map.GetLength(0)-1 && y > 0 && y < map.GetLength(1)-1){ return; } //if you're within the array
        if(map[x,y] == replacementNumber) { return; } //if targetNum = replacementNum, return
        if(map[x,y] != targetNumber) { return; } //if number of Node != targetNum, return because you're not what we're looking for
        //if you've got this far...
        map[x,y] = replacementNumber; //set your current node to replacementNum
        //run function on it's neighbors...this is the floodfilling in action
        //WEST
        FloodFill(x-1,y, targetNumber, replacementNumber);
        //EAST
        FloodFill(x+1,y, targetNumber, replacementNumber);
        //NORTH
        FloodFill(x,y+1, targetNumber, replacementNumber);
        //SOUTH
        FloodFill(x,y-1, targetNumber, replacementNumber);

        return;
    }

Any help you could off would be fantastic.

Thanks so much!

  • Eric
2

Well… I’m not sure your loops are properly setup to count the blobs. There is no place in your code where a counter could be added correctly.

I also hope your blobs aren’t too big, because this kind of recursive methods could blow your stack.

3

Yeah, it did. How does recursion work? If I’m setting off all these FloodFill functions (which I’m guessing is recursion), when they’re done, is there any return to the starting floodfill where I could, conceivably, log that the process is all done for that blob?

4

It’s kinda weird, because I had to do almost exactly that lately. I had to find a zone in an image that should be turned transparent from a picture.

The pseudo code would look like something like this;

    public int FindZones(Pixel[] pixels)
    {
        List<Pixel> parsed = new List<Pixel>();
        List<Pixel> stack = new List<Pixel>();
        int count = 0;

        for (int x = 0; x < pixels.Length; x++)
        {
            Pixel firstPixel = pixels[x];
            if (parsed.Contains(firstPixel))
                continue;

            if (!PixelIsValid(firstPixel))
            {
                parsed.Add(firstPixel);
                continue;
            }

            count++;
            stack.Add(firstPixel);

            while (stack.Count > 0)
            {
                for (int y = 0; y < stack.Count; y++)
                {
                    Pixel stackedPixel = stack[y];
                    stack.RemoveAt(y);
                    parsed.Add(stackedPixel);

                    Pixel[] neighbors = GetNeighbours(stackedPixel);
                    for (int z = 0; z < pixels.Length; z++)
                    {
                        Pixel neighbor = neighbors[z];
                        if (!PixelIsValid(neighbor) || parsed.Contains(neighbor))
                            continue;

                        stack.Add(neighbor);
                    }
                }
            }
        }

        return count;
    }