Implementing 8-Connectivity Connected-Component Labeling in Python

Question

Just for educational purposes, I'm working on making a letter-and-symbol recognition program in Python, and I've run into some trouble with region separation. I made a working connected-component labeling function using the information here:

CCL - Wikipedia

But I need one with the accuracy of an 8-connectivity, which it mentions but doesn't provide info for. It has a diagram on the right side that shows that to check for it, the Northwest and Northeast pixels need to be included, but I have no idea how and I can't find any information on it. I'm not asking for code, but can anybody familiar with this method describe how to incorporate those?

Solution 1

8-connectivity isn't more accurate, and in practice it's suitable only for certain applications. It's more common to use 4-connectivity, especially for "natural" images rather than images created in the lab for testing. An 8-connected region will include checkerboard patterns and zigzag noise. A 4-connected foreground yields an 8-connected background.

You can dig into the source for the OpenCV function cvFindContours(). There are OpenCV bindings to Python. http://opencv.willowgarage.com/documentation/python/structural_analysis_and_shape_descriptors.html

http://opencv.willowgarage.com/wiki/PythonInterface

I would recommend first implementing a 4-connected algorithm. You can find pseudocode in books like the following:

• Machine Vision: Theory, Algorithms, Practicalities by E. R. Davies In the 3rd edition, see section 6.3, "Object Labeling and Counting"
• Digital Image Processing by Gonzalez and Woods See section 9.5.3 "Extraction of Connected Components" The presentation is less clear, but this is a standard all-in-one textbook for image processing. The section on thresholding for binarization is good. An international edition costs about $35.
• Older textbooks may have simple, straightforward descriptions. Used copies of
  Computer Vision by Ballard and Brown are quite cheap. In that book, Algorithm 5.1 is called Blob Coloring.
• My favorite quick description can be found in the section "Region Labeling Algorithm" of Handbook of Image and Video Processing edited by Al Bovik. Conveniently, pages 44 - 45 are available online in Google Books: http://books.google.com/books?id=UM_GCfJe88sC&q=region+labeling+algorithm#v=snippet&q=region%20labeling%20algorithm&f=false

For OCR it's common to look for dark connected regions (blobs) on a light background. Our binarized image will be a black foreground (0) on a white background (1) in a 1-bit image.

For a 4-connected algorithm you'll use structure elements like the ones shown below (which you'll also see in the Bovik book). Once you've tinkered with 4-connectivity, the extension to 8-connectivity should be obvious.

We scan each row of pixels in the image from left to right, and all rows from top to bottom. For any pixel (x,y), its left neighbor (x - 1, y) and top neighbor (x, y - 1) have already been scanned, so we can check whether a region number has already been assigned to one or both of those neighbors. For example, if pixel (x, y-1) is labeled region 8, and if (x,y) is also a foreground pixel, then we assign region 8 to (x,y). If pixel (x,y) is a foreground pixel but the left and top neighbors are background pixels, we assign a new region number to (x,y).

I recommend the Bovik reference, but here's a quick overview of the algorithm.

1. Initialize a region number contour (e.g. "region = 0")
2. Initialize a "region equivalency" data structure for later processing.
3. Create a black and white image using a binarization threshold.
4. Scan each pixel in the image from top to bottom, left to right.
5. Assign region 0 to any white background (1) pixel.
6. For any black foreground pixel (x,y) test the following conditions:
   • If top and left pixels are foreground, use the region number for (x-1, y) as the region number for (x,y), and track the equivalency of the left and top region numbers.
   • If only left neighbor (x - 1,y) is a foreground pixel, use its region number for (x,y)
   • If only top neighbor (x, y - 1) is a foreground pixel, use its region number for (x,y)
   • If left and top neighbors are background pixels, increment the region number and assign this new region number to (x,y).
7. After completing this processing for the entire image, analyze the equivalency matrix and reduce each collection of equivalent regions to a single region.

The reduction of equivalencies is the tricky part. In the image below, regions have been correctly labeled according to the algorithm. The image shows a different color for each region number. The three touching regions must be reduced to one connected region.

Your code should scan the equivalency data structure to reassign 2 (red) and 3 (dark blue) to the lowest-numbered region, which is 1 (yellow). Once the region number reassignment is complete, region labeling is complete.

There are one-pass algorithms that avoid the need for an equivalency check altogether, though such algorithms are a bit harder to implement. I would recommend first implementing the traditional 4-connected algorithm, solving its problems, and then introducing an option to use 8-connectivity instead. (This option is common in image processing libraries.) Once you have 4-connected and 8-connected region labeling working you'll have a good algorithm that will find many uses. In searching for academic papers on the subject, check for "region labeling," "blobs," "contours," and "connectivity."

For grayscale algorithms that need to be binarized, your threshold algorithm will likely become a weak point in your chain of algorithms. For help with thresholding, get a copy of the Gonzalez and Woods book. For OCR, check out the book Character Recognition Systems by Cheriet, Karma, Liu, and Suen.

Solution 2

I propose this implementation of 8-cclabeling, posted on Github.