Download BlobColouring.zip (47 KB)
A few years ago I had to implement a blob colouring algorithm for a university assignment. Since I had some free time over the holidays I decided to try and recreate it in C#. The algorithms purpose is to divide an image into regions of similar colour such as grass, sky or water:
The process involves moving a 3-pixel ‘L’ shaped template across the image, left to right, top to bottom, recording the region number of the pixel in an array of equal size to the image (which I call a region map). To find the region number we calculate the difference between the current pixel and the pixel above and to the left:
P3 represents the current pixel. We need to calculate the difference in colour between p1 and p3, and p2 and p3. Since colour can be represented by its 3 component parts (Red, Green and Blue) we can taken the Euclidean distance (E) between the two pixels as:
E = Sqrt( (R – R’)^2 + (G – G’)^2 + (B – B’)^2 )
Where R,G,B represent the colour components of the first pixel, and R’,G’,B’ represent the second. We use a threshold to decide if two colours should belong in the same region, and apply the blob colouring algorithm:
if p1 and p2 are similar to p3 then join both regions together set p3's region to p1's region else if p1 is similar to p3 then set p3's region to p1's region else if p2 is similar to p3 then set p3's region to p2's region else create a new region end if
We need to maintain a list of regions as we go, with a colour assigned to each one (I use the colour of the first pixel in that region, you could take the average colour).
We also need a way of joining regions together. This is done using an equivalence table, recording next to each region number the regions that are equal to it. After you have processed every pixel in the image, you will need to ‘flatten’ the equivalence table, finding the lowest possible equivalent number for each region. For a detailed explanation, please visit uk-dave’s blog, as he describes it far clearer than I ever could:
His source code should contain a working example of how to flatten the equivalence table. Although I’ve implemented my own version that does the job, it is far from perfect.
To draw the final image just move through the region map drawing each pixel based on the colour of that pixel’s region.
Download BlobColouring.zip (47 KB)Advertisements