在Python中实现8连接性连接组件标记

Question

出于教育目的，我正在用Python编写一个字母和符号识别程序，在区域分离方面遇到了一些问题。我使用以下信息制作了一个工作连接组件标签功能：

CCL - Wikipedia

但我需要一个8连接性的准确性，它提到，但没有提供信息。它的右侧有一个图表，显示要检查它，需要包括西北和东北像素，但我不知道如何，也找不到任何关于它的信息。我不是要代码，但是熟悉这个方法的人能描述一下如何合并这些代码吗？

Answer 1

8连接性并不更精确，实际上它只适用于某些应用程序。使用4连接性更为常见，尤其是对于“自然”图像，而不是在实验室中创建用于测试的图像。一个8连接的区域将包括棋盘格图案和锯齿形噪声。4连接的前景产生8连接的背景。

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

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

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

• 机器视觉：理论、算法、实用性 在第3版中，见第6.3节“对象标记和计数”
• 冈萨雷斯和伍兹的数字图像处理 见第9.5.3节“连接部件的提取” 演示不太清楚，但这是一本标准的图像处理一体化教材。二值化的阈值部分很好。国际版大约35美元。
• 旧的教科书可能有简单、直接的描述。
  的已用副本 巴拉德和布朗的计算机视觉很便宜。在那本书中，算法5.1被称为Blob着色。
• 我最喜欢的快速描述可以在Al-Bovik编辑的图像和视频处理手册的“区域标记算法”部分找到。方便的是，第44-45页可在谷歌图书在线获得： 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）。

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

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

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

1. 初始化区域号轮廓（例如“区域=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）。
7. 在对整个图像完成此处理后，分析等效矩阵，并将每个等效区域集合减少为单个区域。

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

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

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

对于需要二值化的灰度算法，阈值算法可能会成为算法链中的一个弱点。要获得阈值设置的帮助，请获取冈萨雷斯和伍兹书籍的副本。对于OCR，请参阅Cheriet、Karma、Liu和Suen的《字符识别系统》。

Answer 2

我建议实现8-cclabeling，posted on Github。