机器视觉之二值图像算法

机器视觉之二值图像算法 从背景中分离出物体是一个困难的问题，在此将不讨论这个问题。这里假设物体可以从背景中分离，并且使用某一谓词，可以对图像中属于物体的点进行标记。因此，问题就变为如何将一幅图像中所有被标记的点组合成物体图像。这里还假设物体点在空间上是非常接近的。利用空间接近概念可以严格定义，利用此定义研究的算法可以把空间上非常接近的点聚合在一起，构成图像的一个成分（component)。下面首先引进一些定义，然后讨论有关算法。

3.5.1定义 1.近邻 在数字图像中，一个象素在空间上可能非常接近其它一些象素。在用网格表示的数字图像中，一个象素与其它四个象素有公共边界，并与另外四个象素共享顶角。如果两个象素有公共边界，则称它们互为4邻点(4-neighbors).同样，如果两个象素至少共享一个顶角，则称它们互为8邻点。例如，位于[i，j]的象素有四个4邻点：[i-1,j]，[i+1，j]，[i，j-1]，[i，j+1]。它的8邻点包括这四个4邻点,再加上[i-1,j-1]，[i + 1，j-1」，[i-1， j + 1],[i + 1,j+ 1]。一个象素被认为与它的4邻点是4连通(4-conneeted)关系，与它的8 邻点是8连通关系（如图3.7)。

2.路径 3.前景 图像中值为1的全部象素的集合称为前景(foreground),用S表示。

4.连通性

5.连通成分 一个象素集合，如果集合内的每一个象素与集合内其它象素连通，则称该集合为一个 连通成分（connected component）。

6.背景 S( S的补集）中包含图像边界点的所有连通成份的集合称为背景（background)。 S中所有其它元称为洞。考虑下面的两个图像。 首先看左图中有几个洞和几个物体。如果从前景和背景来考虑4连通，有四个大小为一个象素的物体和一个洞。如果考虑8连通，那么有个物体而没有洞。直观地，在这两种情况下出现了不确定性情况。右图为另一个类似的不确定问题。其中如果1是连通的，那么0 就应该是不连通的。 为了避免这种难以处理的情况，对物体和背景应使用不同的连通。如果对S使用8连通，那么对S就应用4连通。

7.边界 S的边界（boundary)是S中与中有4连通关系的象素集合。边界通常记为S'。 8.内部 内部（interior)是S中不属于它的边界的象素集合.S的内部等于S-S"。

9.包围 如果从S中任意一点到图像边界的4路径必须与区域T相交，则区域T包围 (surrounds)区域S(或S在T内）。图3.9即为一幅简单二值图像和它的边界、内部、包围示意图。

3.5.2连通成分标记 在一幅图像中找出连通成分是机器视觉中最常见的运算之一。连通区域内的点构成表示物体的候选区域。机器视觉中的大多数物体都有表面，显然，物体表面点投影到图像平面上会形成空间上密集的点集。这里应该指出，连通成分算法常常会在值视觉系统中形成瓶颈效应，原因是连通成分运算是一个全局性的运算，这种算法在本质上是序贯的。 如果图像中仅有一个物体，那么找连通成分就没有必要；如果图像中有许多物体，且需要求出物体的特性与位置，则必须确定连通成分。 连通标记算法可以找到图像中的所有连通成分，并对同连通成分中的所有点分配同一标记。图3.10表示的是一幅图像和已标记的连通成分。在很多应用中，要求在标记连通成分的同时算出连通成分的特征,如尺寸、位置、方向和外接矩形。下面介绍两种连通成分标记算法:递归算法和序惯算法[Jain 1995]。

1.递归算法 递归算法在串行处理器上的计算效率是很低的，因此，这一算法主要用于并行机上。 算法3.1连通成分递归算法 ①扫描图像，找到没有标记的1点，给它分配一个新的标记L； ②递归分配标记L给1点的邻点； ③如果不存在没标记的点，则停止； ④󰀀 返回第①步。

2.序贯算法 序惯算法通常要求对图像进行二次处理。由于这一算法一次仅运算图像的两行，因此当图像以文件形式存贮且空间不允许把整幅图像载入内存时也能使用这一算法。这一算法（见算法3.2)可以查看某一点的邻点，并且可以给象素值为1的邻点分配个已经使用过 的标记。如果图像的邻点有两种不同的标记，则叫一个等价表（equivalent table）来记录所有的等价标记。在第二次处理过程中，使用这一等价表來给某连通成分中所有象素点分配唯一的标记。 本算法从左到右、从上到下扫描图像时，算法仅能查询到某象素点的4邻点中的两个邻点，即上点与左点。设算法已经查到了该象素的这两个邻点，此时出现三种情况:① 如果这两个邻点中没有一点为1,则该象素需要一个新的标记。②如果这两个邻点中只有一点为1，且分配了标记为L，那么该象素点的标记也为L。③如果这两个邻点都为1，且已分配了标记L，则该象素点的标记还是L；但是当邻点被分配了不同标记M与 N,则这两个标记被用于了同一组元，应该把它们合并。在这种下,应把其中一个标记(一般选用最小的那个标记)分配给该象素点，并在等价表中登记为等价标记。 等价表包含了给每一连通成分分配唯一标记的信息，第一次扫描中，所有属于同一连通成分的标记被视为是等价的。在第二次扫描中，从一个等价集（equivalent set)中选择一个标记并分配给连通成分中所有象素点。通常将最小的标记分配给一个连通成分。第二次扫描将给每一连通成分分配唯一的标记。 在找到所有的连通成分后，应该统计等价表，以便删除其中的空格；然后将等价表作为查找表对图像重新进行扫描，以便重新统计图像中的标记。 计算每一连通成分的面积、一阶矩、二阶矩是序贯连通成分算法的个部分。当然，必须使用分离变暈来累加每一区域的矩信息)。当区域合并后，每一区域的矩累计值也应加到一起。 ^ 算法3.2 4连通成分序贯算法 ①从左至右、从上到下扫描图像。 ②如果象素点为1，则： •如果上面点和左面点有一个标记,则复制这一标记。 •如果两点有相同的标记，复制这一标记。 •如果两点有不同的标记,则复制上点的标记且将两个标记输人等价表中作为等价标记。 •否则给这一个象素点分配一新的标记并将这一标记输入等价表。 ③如果需考虑更多的点，则回到第②步。 ④在等价表的每一等价集中找到最低的标记。 ⑤扫描图像，用等价表中的最低标记取代每一标记。

3.5.3欧拉数 在许多应用中，亏格数(genus)或欧拉数可作为识别物体的特征。亏格数定义为连通成分数减去洞数。

E = C - H (3.21) 其中，E,C和H分别是欧拉数、连通成分数与洞数。这个式子给出了一个简单的拓朴特怔，这种拓扑特征具有平稳、旋转和比例不变特性。图3.11给出了一些例子及其对应的欧拉数. 3.5.4区域边界 连通成分S的边界是那些属于S且与邻接的点集。使用简单的局部运算就可找到边界点。在大多数应用中，我们都想用一特定的顺序跟踪边界点。一般的算法是按顺时针方向跟踪区域的所有点。此处讨论一个简单的边界跟踪算法。 假定物体边界不在图像的边界上（即物体完全在图像内部），边界跟踪算法先选择一

起始点，然后跟踪边界直到回到起始点。这种算法概括在算法3.3中，这种算法对尺寸大于1个象素的所有区域是有效的。用这种算法求8邻点区域的边界点如图3.12（a)所示，为了得到平滑的图像边界后，可以在检测和跟踪图像边界后，利用边界点的方向信息来平滑边界。显然，图像边界噪声越太，图像边界点变化越剧烈，图像边界相邻点的方向变化数也越大。显然，根据这一特点，设置一个边界点方向变化数阈值，把方向变化数大于这一阈值的图像边界点滤除，由此可得到平滑的图像边界。图3.12(b)所示的是一个经过平滑过的区域边界示意图，其中的方向变化数阈值为1。注意，由于采用8邻点边界跟踪，因此方向变化数的最大值为4。如果阈值设成4,则对原始边界没有平滑。边界跟踪和平滑常

常结合在一起使用，见计算机作业3.5. 算法3.3边界跟踪算法

3.5.5距离测量 在许多应用中，找到一幅图像中两个象素点或两个连通成分之间的距离是很有必要的。目前还没有定义数字图像距离的唯一方法，但对所有的象素点p，q和r,任何距离度量都必须满足下列性质： 3.5.6 中轴 如果对S中象素[i，j]的所有邻点u，v有下式成立

(3.25) 则S中象素[i,y]到的距离d([i,j], )是局部最大值。S中所有到的距离是局部最大值的象素点集合称为对称轴或中轴，通常记为S'，使用[u,v]4邻点的中轴变换的一些例子见图3.13。图3.13(b)表明少量噪声会使中轴变换结果产生显著的差异。

由S’和S’中每一点到的距离能重构原始象素集S.S’是s的简洁表示。S’可用来表示一个区域的形状。通过去除S’中与距离较小的象素点，可以生成一个简化的S’ 集。 中轴可作为物体的一种简洁表示。但是，二值图像中的区域也可用其边界来表示。边界跟踪算法可用来获得表示边界的序列点。在第七章还将讨论用链码来简洁地表示边界的方法。对任意物体，边界将是区域的简洁表示。但要明确给定象素点是否在某一区域内，中轴则是更好的表示，因为使用中轴上的象素点和每一个给定象素点的最大距离圆盘（中 轴距离变换），可以很容易地检测出给定象素是否在中轴定义的区域中。 3.5.7 细化 细化(thinning)是一种图像处理运算，可以把二值图像区域缩成线条，以逼近区域的中心线，也称之为骨架或核线。细化的目的是减少图像成分，直到只留下区域的最基本信息，以便进一步分析和识别。虽然细化可以用在包含任何区域形状的二值图像，但它主要对细长形（而不是凸圆形或水滴状)区域有效。细化一般用于文本分析预处理阶段，以便将文本图像中线条图画或字符笔画表示成单象素线条。细化要求如下： ①连通区域必须细化成连通线结构。 ②细化结果最少应该是8连通(下面将要解释）。 ③保留终止线的位置。 ④细化结果应该近似于中轴线。 ⑤由细化引起的附加突刺(短分支)应该是最小的。 细化结果应该保证第一条要求中所定义的连通性，这一点是最基本的要求，它保证了连通线结构的数量等于原始图像中连通区域的数量。第二条要求保证所得到的线条总是含有8连通图像的最小数量。第三条要求说明终止线位置应该保持不变。细化可以通过迭代方式不断去除边界点来实现，在迭代过程中注意不要去除端点象素，因为这样不