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

Question

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

CCL - 维基百科

但我需要一个8连接的准确性,它提到但不提供信息.它有一个右侧的图表,显示要检查它,需要包括西北和东北像素,但我不知道我怎么也找不到任何信息.我不是要求代码,但熟悉这种方法的人是否可以描述如何合并代码呢？

Answer 1

8连接不准确,实际上它仅适用于某些应用.使用4连接更常见,尤其是"自然"图像,而不是实验室中用于测试的图像.8连接区域将包括棋盘图案和锯齿形噪声.4连接前景产生8连接背景.

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

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

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

• 机器视觉: 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 = MAG_GCfJe88sC&q = region + label + algorithm_v = ofnippet&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. 初始化区域编号轮廓(例如"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的字符识别系统一书.