在Python中实现8连接性连接组件标签 [英] Implementing 8-Connectivity Connected-Component Labeling in Python

问题描述

出于教育目的，我正在用Python制作一个字母和符号识别程序，我遇到了区域分离的麻烦。我使用以下信息制作了一个有效的连通组件标签功能：

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 - 维基百科

但是我需要一个具有8连接精度的，它提到但不提供信息对于。它有一个右侧的图表，显示要检查它，需要包括西北和东北像素，但我不知道我怎么也找不到任何信息。我不是要求代码，但任何熟悉这种方法的人都可以描述如何合并这些代码吗？

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?

推荐答案

8-connectivity isn更准确，实际上它只适用于某些应用。使用4连接更常见，特别是对于自然图像而不是在实验室中创建的图像进行测试。 8连接区域将包括棋盘图案和锯齿形噪声。 4连接前景产生8连接背景。

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.

您可以深入了解OpenCV函数cvFindContours（）的源代码。有Python的OpenCV绑定。
http://opencv.willowgarage.com/documentation/python/structural_analysis_and_shape_descriptors.html

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

我建议首先实现一个4连接算法。您可以在以下书籍中找到伪代码：

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

• 机器视觉：理论，算法，实用性作者：ER Davies
  在第3版中，请参阅第6.3节对象标注和计数


• 数字图像处理作者：Gonzalez和Woods
  请参阅9.5.3连接组件的提取
  演示文稿不太清楚，但这是用于图像处理的标准一体化教科书。关于二值化阈值的部分是好的。国际版费用约为35美元。


• 较旧的教科书可能有简单直接的描述。 Ballard和Brown使用的
  计算机视觉的副本非常便宜。在那本书中，算法5.1被称为Blob Coloring。


• 我最喜欢的快速描述可以在图像和视频处理手册由Al Bovik编辑。方便地，第44-45页可在Google图书中在线获取：
  http://books.google.com/books?id=UM_GCfJe88sC&q=region+labeling+algorithm#v=snippet&q=region% 20标记％20算法& f =假

• 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

对于OCR，通常在灯上寻找暗连通区域（blob）背景。我们的二值化图像将是1位图像中白色背景（1）上的黑色前景（0）。

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.

对于4连接算法，您将使用如下所示的结构元素（您也可以在Bovik书中看到）。一旦你修改了4连接，8连接的扩展应该是显而易见的。

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.

我们从左到右扫描图像中的每一行像素，从顶部扫描所有行到底。对于任何像素（x，y），其左邻居（x-1，y）和顶邻居（x，y-1）已被扫描，因此我们可以检查区域编号是否已分配给一个或两个那些邻居例如，如果像素（x，y-1）被标记为区域8，并且如果（x，y）也是前景像素，则我们将区域8分配给（x，y）。如果像素（x，y）是前景像素但左和上邻居是背景像素，我们将新的区域编号分配给（x，y）。

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).

我推荐Bovik参考，但这里是算法的快速概述。

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

1. 初始化区域编号轮廓（例如region = 0）


2. 初始化区域等效数据结构以供以后处理。


3. 创建使用二值化阈值的黑白图像。


4. 从上到下，从左到右扫描图像中的每个像素。


5. 将区域0指定给任何白色背景（1）像素。


6. 对于任何黑色前景像素（x，y），请测试以下条件：
   
   
   
   
   • 如果顶部和左侧像素是前景，请使用（x-1，y）的区域编号作为（x，y）的区域编号，并跟踪左边和顶部区域编号的等效性。
   
   
   • 如果只有左邻居（x - 1，y）是前景像素，则使用其区域编号为（x，y）
   
   
   • 如果只有顶级邻居（x，y - 1）是前景像素，则使用其区域编号为（x，y）
   
   
   • 如果是左邻居和顶级邻居是背景像素，增加区域编号并将此新区域编号分配给（x，y）。
   
   

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).

等效性的减少是棘手的部分。在下图中，根据算法正确标记了区域。图像显示每个区域编号的不同颜色。必须将三个接触区域缩小为一个连接区域。

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.

您的代码应扫描等效数据结构，将2（红色）和3（深蓝色）重新分配给编号最小的区域，即1（黄色）。一旦区域编号重新分配完成，区域标记就完成了。

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.

有一种通过算法可以完全避免需要进行等效检查，尽管这些算法有点更难实施。我建议首先实现传统的4连接算法，解决它的问题，然后引入一个使用8连接的选项。 （此选项在图像处理库中很常见。）一旦您进行了4连接和8连接区域标记工作，您将拥有一个可以找到许多用途的良好算法。在搜索关于该主题的学术论文时，检查区域标记，斑点，轮廓和连通性。

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."

对于需要的灰度算法如果要进行二值化，您的阈值算法可能会成为算法链中的一个弱点。有关阈值处理的帮助，请获取Gonzalez和Woods书籍的副本。对于OCR，请查看Cheriet，Karma，Liu和Suen的书字符识别系统。

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.

这篇关于在Python中实现8连接性连接组件标签的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！