边缘图像连通区域标记的算法研究和SoPC实现
158 浏览量
2020-10-22
13:28:08
上传
评论
收藏 244KB PDF 举报
边缘图像连通区域标记的算法研究和边缘图像连通区域标记的算法研究和SoPC实现实现
针对二值边缘图像目标点较少的特点，提出了基于目标像素邻域的8方向生长区域标记算法。该算法充分利用了
边缘图像的走向信息，提高了搜索效率，降低了堆栈空间消耗，消除了邻域反复扫描问题。
目前的连通区域标记算法中，基于等价标号的标记算法需要至少扫描图像两次，并且要处理标记冲突问题，其执行时间过
于依赖连通区域的复杂程度[2]。而基于
本文所标记的图像是经过边缘检测得的二值
1 基于生长算法的区域标记基于生长算法的区域标记
像素P的上、下、左、右、左上、左下、右上、右下的像素集合为像素P的8邻域，邻域内所有目标点同属于一个连通区。
通常采用8邻域生长法则进行连通区域标记。
1.1 8邻域区域生长算法邻域区域生长算法
设边缘图像的背景像素为255，目标像素为0，对其进行8邻域区域生长标记的步骤如下：
(1)按从上到下、从左到右的顺序扫描图像，遇到目标像素P时，标记为新的标记值L；
(2)以P为种子点，将其8邻域内的目标像素标记为L；
(3)将所有与L像素8邻域内相邻的目标像素标记为L，直到该连通区域标记完毕；
(4)继续按顺序扫描图像，重复前三步，直到图像中所有目标像素都标记完毕。
每个连通区域的起始点是按顺序扫描整个图像得到的，而各个连通区域的标记过程是递归调用生长函数的过程。生长函数
依次扫描目标点的8邻域，若遇到新的目标点，则将当前目标点的处理过程压栈，转而扫描新目标点的8邻域，如此不断地将
目标点压栈。当某一目标点的8邻域内没有新的目标点，则将其弹栈，当所有目标点都弹栈完毕，则该连通区域标记完毕。
1.2 邻域重复扫描问题邻域重复扫描问题
在图1中，P0的8邻域和P1、P2、P3、P4的8邻域有4个像素的重叠，与P5、P6、P7、P8的8邻域有2个像素的重叠。按上
述的8邻域区域生长算法，当P0与P4均为目标点时(设递归过程由P0 向P4传递)，P0、P1、P8、P3、P7这5个像素点被扫描
了2次；当P0与P5均为目标点时(设递归过程由P0 向P5传递)，P0、P1、P2这3个像素点被扫描了2次。
1.3 8方向邻域生长算法方向邻域生长算法
8方向邻域生长算法的思路是：目标点A和目标点B相邻，从A到B有8个方向，当按某个方向从A传递到B的8邻域搜索时，只
搜索B的8邻域中未被A的8邻域覆盖的部分。例如，图1中从P0传递到P4的8邻域搜索时，只搜索P18、P04、P37；从P0传递
到P5的8邻域搜索时，只搜索P05、P25、P01、P15、P02。即：
8方向邻域生长算法由9个生长函数组成。对于连通区域的起点，必须搜索8个方向，此时调用主生长函数。在目标点传递的
过程中，按其传递方向，按式(1)调用相应的生长函数搜索邻域点。区域标记从起点调用主生长函数开始，过程是8个生长函数
互相调用，最后这些函数都返回时，区域标记完毕。
该方法充分利用了从目标点A到目标点B的方向信息，从而在搜索B的邻域时，搜索个数降低为原来的3/8或5/8，平均效率提
高了50%。
1.4 边缘端点与区域合并边缘端点与区域合并
仅用8邻域搜索连通区，往往得到的连通区域并不完整，连通性不好。图2(a)中，右半部分是圆形左下局部放大图。当按逆
时针搜索到图中圆圈标识的“11”时，在其8邻域内没有新的目标点，因此也就和区域“15”断开了。
当搜索到某个目标点时，其8邻域内没有新的目标点，则该点就是边缘的“末端”。一个区域可能有多个末端。
在图2(b)中，右半部分是“米”字中心局部放大图。图中圆圈标识的“4”点，其8邻域内有新的目标
点（左下点），但最近的“3”点并不在其邻域内，因此两个连通区断开。对于单个像素宽的边缘图像，其走向基
本一致；而走向改变较大的点，就是图形的“拐点”，此时容易出现区域断开的现象。
资源评论
