Blob detection IV: Edge tracing algorithm

By Erik van Kempen | January 10, 2008

In Blob detection II - Tracing edges, I have already described in a nutshell the algorithm I have been using for my multi-touch project. In this article I am trying to give a better and more understandable description of the used algorithm. I will not only describe the algorithm, but also show the pros, cons and encountered problems. Some of the information can be already found in the previous article.

The blobs are being detected in a stream of grayscale images. These images have already been preprocessed, by converting them from 24-bit color to grayscale and by blurring to minimize noise and false positives. These grayscale blurred images are fed to the blob detection algorithm.

Algorithm

The algorithm tracks the edge of a blob by executing a sequence of activities:

  1. Find an entry point: the image can be considered as a two-dimensional matrix of brightness values with a x rows and y colunns. The entry point can be found by checking the pixels one at a time, from left to right (incrementing y) and from top to bottom (incrementing x). If your blobs are darker than the background, you should find an entry point with a brightness value below a certain treshold. If your blobs are lighter than the background, which is the case with the multi-touch project, you should find the entry point by checking the pixels for a brightness above the threshold. In my case I only consider pixels with a brightness of 255, which is the maximum value.
  2. Find a neighbour with a brightness above/below the threshold: every pixel in the image, except for the pixels at the sides, has eight neighbouring pixels. The entry point also has eight neighbouring pixels, which need to be checked in order to find the nex pixel at the edge of the blob. The order in which these neighbours are checked depends on the direction of the center pixel of these neighbours with respect to the previous center pixel. In the following image you can see in which order the pixels are checked in certain orders.

    Blob detection edge tracing order

  3. Determine the next order in which the next neighbours will be checked:
    • Is the direction of the current center pixel, with respect to the previous center pixel, west or northwest? Use Order 2 for the next iteration.
    • Is the direction of the current center pixel, with respect to the previous center pixel, north or northeast? Use Order 3 for the next iteration.
    • Is the direction of the current center pixel, with respect to the previous center pixel, east or southeast? Use Order 4 for the next iteration.
    • Is the direction of the current center pixel, with respect to the previous center pixel, south or southwest? Use Order 1 for the next iteration.
  4. Rerun the sequence from the second activity until you are at the entry point of the blob again.
  5. Determine the extreme values of the blob's coordinates to calculate the bounding box and center coordinate (the actual data you need).
  6. Fill the box with a brightness below (or above) the threshold to keep it undetected during the next blob search.
  7. Rerun the sequence from the first activity until there is no pixel with a brightness value above (or below) threshold left.

Example

You can try to execute the sequence in your head on the following image:

Blob detection example

The entry point will be pixel 1. Then you will use the first order to check the neighbouring pixels (starting with the neighbour in the east). You will find pixel 2 as the next center pixel, because it's the first pixel you check and it has a brightness below the threshold (ie. is black). Next you will use the fourth order to determine the next center pixel. Etcetera...

Pros

  • It is a lot faster than the detection methods proposed in the entry Blob detection. Only the outer pixels of the blob need to be checked, instead of the poor growing algorithms. It can run at the full speed image stream from a webcam.
  • It is easy to understand the algorithm. There is no mathematics involved or difficult calculations, just intuitive edge tracing. That is why I was able to use this method to succesfully demonstrate my multi-touch project quickly.

Cons

  • It is still slow. On my laptop, which is quite new, it needs over 40% of the CPU time while processing low resolution webcam images (300.000 pixels @ 30 frames per second). This is too much to use it for interfacing.
  • My crappy implementation seems to run into deadlock sometimes. Because it depends on the pixel checking to return to its starting point to end, it will not stop if the starting point is not being reached anymore. I used a quick and dirty solution with a counter to stay below a certain number of iterations.

Conclusion

So perfomance is a big issue when you want to use the blob detection for interfacing purposes. I am currently looking for another algorithm to solve the performance issues. I think I have found one and I will describe this in the future. I you have any thoughts about this, please contact me via my email address (see the about section at the bottom of this page).

Return to home

© 2007-2008 Erik van Kempen