Blob Colouring Algorithm

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:

http://www.uk-dave.com/projects/misc/java-colour-tracker/

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
This entry was posted in Projects and tagged . Bookmark the permalink.

2 Responses to Blob Colouring Algorithm

  1. Runfile says:

    Hi,
    first thank you for your code. i have an university assignment too. my friends and i try to understand what image proccessing is. And i am doing the blob coloring part. i have to understand why we are using this algorithm. i don’t have so much document about blob coloring(especially in my language) and because of this i cant get the what blob coloring is. if you still save your documents can you share them? you can e-mail me. thank you 🙂

    • codeoverload says:

      Hi Runfile, sadly I don’t have my lecture notes any more but I do remember our task was to calculate what percentage of the image was occupied by the sky – not very useful in the real world. I guess you could use it as part of object detection – perhaps if you combined it with an edge detection algorithm you might be able to detect objects by their shape.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s