在 Python 中实现 8 连接连通分量标签

发布于 2024-12-20 04:21:05 字数 320 浏览 4 评论 0原文

出于教育目的，我正在用 Python 制作一个字母和符号识别程序，但我在区域分离方面遇到了一些麻烦。我使用此处的信息制作了一个可用的连接组件标记函数：

CCL - Wikipedia

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

新一帅帅 2024-12-27 04:21:05

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 连接算法。您可以在以下书籍中找到伪代码：

机器视觉：理论、算法、实用性，作者：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%20labeling%20algorithm&f=false

对于OCR 通常会在浅色背景上寻找深色连接区域（斑点）。我们的二值化图像将是 1 位图像中白色背景 (1) 上的黑色前景 (0)。

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

4-connected Structure element

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

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

初始化区域编号轮廓（例如“区域= 0”）
初始化“区域等效”数据结构以供后续处理。
使用二值化阈值创建黑白图像。
从上到下、从左到右扫描图像中的每个像素。
将区域 0 分配给任何白色背景 (1) 像素。
对于任何黑色前景像素 (x,y) 测试以下条件：
- 如果顶部和左侧像素是前景，则使用 (x-1, y) 的区域编号作为 (x,y) 的区域编号，并跟踪左侧和顶部区域编号的等效性。
- 如果只有左邻居 (x - 1,y) 是前景像素，则使用其区域编号作为 (x,y)
- 如果只有顶部邻居 (x, y - 1) 是前景像素，则使用其区域编号作为 (x,y)
- 如果左侧和顶部邻居是背景像素，则增加区域编号并将此新区域编号分配给 (x,y)。
对整个图像完成此处理后，分析等效矩阵并将等效区域的每个集合减少为单个区域。

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

三个相邻区域应减少为一个区域

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

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

对于需要二值化的灰度算法，您的阈值算法可能会成为算法链中的弱点。如需阈值处理方面的帮助，请获取 Gonzalez 和 Woods 的书。对于 OCR，请查看 Cheriet、Karma、Liu 和 Suen 所著的《字符识别系统》一书。

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.

4-connected structure element

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.

Initialize a region number contour (e.g. "region = 0")
Initialize a "region equivalency" data structure for later processing.
Create a black and white image using a binarization threshold.
Scan each pixel in the image from top to bottom, left to right.
Assign region 0 to any white background (1) pixel.
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).
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.

Three adjacent regions that should be reduced to one 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.

回复收藏 0 原文