在Python中实现8连接区域标记

Question

为了学习，我正在用Python制作一个识别字母和符号的程序，但在区域分离方面遇到了一些麻烦。我参考了这里的信息，做了一个有效的连通组件标记函数：

CCL - 维基百科

不过，我需要一个具有8连通性准确度的版本，虽然文中提到了这一点，但没有提供具体的信息。右侧有一张图，显示要检查8连通性时，需要包含西北和东北的像素，但我不知道该怎么做，也找不到相关的信息。我并不是在请求代码，但有没有人能告诉我，如何将这些像素包含进来？

Answer 1

我推荐这个8连通区域标记的实现，可以在Github上找到。

Answer 2

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连通的算法。你可以在一些书籍中找到伪代码，比如以下几本：

• 机器视觉：理论、算法与实践，作者E. R. Davies 在第三版中，查看第6.3节，“对象标记和计数”
• 数字图像处理，作者Gonzalez和Woods 查看第9.5.3节“连接组件的提取” 这本书的内容不太清晰，但它是一本关于图像处理的标准教材。关于二值化的阈值处理部分写得很好。国际版大约35美元。
• 旧书可能有简单明了的描述。
  计算机视觉，作者Ballard和Brown的二手书相当便宜。在那本书中，第5.1算法叫做“斑点着色”。
• 我最喜欢的简要描述可以在图像和视频处理手册中找到，由Al Bovik编辑。方便的是，44-45页在Google图书上可以在线查看： http://books.google.com/books?id=UM_GCfJe88sC&q=region+labeling+algorithm#v=snippet&q=region%20labeling%20algorithm&f=false

在光学字符识别（OCR）中，通常会在亮色背景上寻找暗色的连接区域（斑点）。我们的二值化图像将是黑色前景（0）在白色背景（1）上的1位图像。

对于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. 初始化一个区域编号轮廓（例如“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)。
7. 在完成整个图像的处理后，分析等价性矩阵，并将每个等价区域的集合简化为一个区域。

简化等价性是比较棘手的部分。在下面的图像中，区域已经根据算法正确标记。图像中每个区域编号都有不同的颜色。三个相邻的区域必须简化为一个连接区域。

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

还有一些一次性算法可以完全避免等价性检查，尽管这些算法实现起来稍微复杂一些。我建议你先实现传统的4连通算法，解决它的问题，然后再引入使用8连通性的选项。（这个选项在图像处理库中很常见。）一旦你实现了4连通和8连通的区域标记，你就会有一个很好的算法，可以找到很多用途。在寻找相关的学术论文时，可以查找“区域标记”、“斑点”、“轮廓”和“连通性”。

对于需要二值化的灰度算法，你的阈值算法可能会成为你算法链中的一个薄弱环节。关于阈值处理的帮助，可以参考Gonzalez和Woods的书。对于OCR，可以查看字符识别系统这本书，作者是Cheriet、Karma、Liu和Suen。