机器视觉之二值图像算法.docx

1、机器视觉之二值图像算法机器视觉之二值图像算法从背景中别离出物体是一个困难的问题，在此将不讨论这个问题。这里假设物体可以从背景中别离，并且使用某一谓词，可以对图像中属于物体的点进展标记。因此，问题就变为如何将一幅图像中所有被标记的点组合成物体图像。这里还假设物体点在空间上是非常接近的。利用空间接近概念可以严格定义，利用此定义研究的算法可以把空间上非常接近的点聚合在一起，构成图像的一个成分component)。下面首先引进一些定义，然后讨论有关算法。在数字图像中，一个象素在空间上可能非常接近其它一些象素。在用网格表示的数字图像中，一个象素与其它四个象素有公共边界，并与另外四个象素共享顶角。假设两个

2、象素有公共边界，那么称它们互为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)。3.前景图像中值为1的全部象素的集合称为前景(foreground),用S表示。4.连通性一个象素集合，假设集合内的每一个象素与集合内其它象素连通，那么称该集合为一个连通成分

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

4、interior)是S中不属于它的边界的象素集合.S的内部等于S-S。假设从S中任意一点到图像边界的4途径必须与区域T相交，那么区域T包围 (surrounds)区域S(或S在T内。图即为一幅简单二值图像和它的边界、内部、包围示意图。.2连通成分标记在一幅图像中找出连通成分是机器视觉中最常见的运算之一。连通区域内的点构成表示物体的候选区域。机器视觉中的大多数物体都有外表，显然，物体外表点投影到图像平面上会形成空间上密集的点集。这里应该指出，连通成分算法常常会在值视觉系统中形成瓶颈效应，原因是连通成分运算是一个全局性的运算，这种算法在本质上是序贯的。 假设图像中仅有一个物体，那么找连通成分就没有

5、必要；假设图像中有许多物体，且需要求出物体的特性与位置，那么必须确定连通成分。连通标记算法可以找到图像中的所有连通成分，并对同连通成分中的所有点分配同一标记。图表示的是一幅图像和已标记的连通成分。在很多应用中，要求在标记连通成分的同时算出连通成分的特征,如尺寸、位置、方向和外接矩形。下面介绍两种连通成分标记算法:递归算法和序惯算法Jain 1995。递归算法在串行处理器上的计算效率是很低的，因此，这一算法主要用于并行机上。算法连通成分递归算法扫描图像，找到没有标记的1点，给它分配一个新的标记L；递归分配标记L给1点的邻点；假设不存在没标记的点，那么停顿；返回第步。序惯算法通常要求对图像进展二次

6、处理。由于这一算法一次仅运算图像的两行，因此当图像以文件形式存贮且空间不允许把整幅图像载入内存时也能使用这一算法。这一算法见算法3.2)可以查看某一点的邻点，并且可以给象素值为1的邻点分配个已经使用过的标记。假设图像的邻点有两种不同的标记，那么叫一个等价表equivalent table来记录所有的等价标记。在第二次处理过程中，使用这一等价表來给某连通成分中所有象素点分配唯一的标记。本算法从左到右、从上到下扫描图像时，算法仅能查询到某象素点的4邻点中的两个邻点，即上点与左点。设算法已经查到了该象素的这两个邻点，此时出现三种情况: 假设这两个邻点中没有一点为1,那么该象素需要一个新的标记。假设这

7、两个邻点中只有一点为1，且分配了标记为L，那么该象素点的标记也为L。假设这两个邻点都为1，且已分配了标记L，那么该象素点的标记还是L；但是当邻点被分配了不同标记M与 N,那么这两个标记被用于了同一组元，应该把它们合并。在这种下,应把其中一个标记(一般选用最小的那个标记)分配给该象素点，并在等价表中登记为等价标记。等价表包含了给每一连通成分分配唯一标记的信息，第一次扫描中，所有属于同一连通成分的标记被视为是等价的。在第二次扫描中，从一个等价集equivalent set)中选择一个标记并分配给连通成分中所有象素点。通常将最小的标记分配给一个连通成分。第二次扫描将给每一连通成分分配唯一的标记。在找

8、到所有的连通成分后，应该统计等价表，以便删除其中的空格；然后将等价表作为查找表对图像重新进展扫描，以便重新统计图像中的标记。计算每一连通成分的面积、一阶矩、二阶矩是序贯连通成分算法的个局部。当然，必须使用别离变暈来累加每一区域的矩信息)。当区域合并后，每一区域的矩累计值也应加到一起。 算法3.2 4连通成分序贯算法从左至右、从上到下扫描图像。假设象素点为1，那么：假设上面点和左面点有一个标记,那么复制这一标记。假设两点有一样的标记，复制这一标记。假设两点有不同的标记,那么复制上点的标记且将两个标记输人等价表中作为等价标记。否那么给这一个象素点分配一新的标记并将这一标记输入等价表。假设需考虑更多

9、的点，那么回到第步。在等价表的每一等价集中找到最低的标记。扫描图像，用等价表中的最低标记取代每一标记。3.5.3欧拉数在许多应用中，亏格数(genus)或欧拉数可作为识别物体的特征。亏格数定义为连通成分数减去洞数。E = C - H (3.21)其中，E,C和H分别是欧拉数、连通成分数与洞数。这个式子给出了一个简单的拓朴特怔，这种拓扑特征具有平稳、旋转和比例不变特性。图给出了一些例子及其对应的欧拉数.区域边界连通成分S的边界是那些属于S且与邻接的点集。使用简单的局部运算就可找到边界点。在大多数应用中，我们都想用一特定的顺序跟踪边界点。一般的算法是按顺时针方向跟踪区域的所有点。此处讨论一个简单的

10、边界跟踪算法。假定物体边界不在图像的边界上即物体完全在图像内部，边界跟踪算法先选择一起始点，然后跟踪边界直到回到起始点。这种算法概括在算法中，这种算法对尺寸大于1个象素的所有区域是有效的。用这种算法求8邻点区域的边界点如图a)所示，为了得到平滑的图像边界后，可以在检测和跟踪图像边界后，利用边界点的方向信息来平滑边界。显然，图像边界噪声越太，图像边界点变化越剧烈，图像边界相邻点的方向变化数也越大。显然，根据这一特点，设置一个边界点方向变化数阈值，把方向变化数大于这一阈值的图像边界点滤除，由此可得到平滑的图像边界。图3.12(b)所示的是一个经过平滑过的区域边界示意图，其中的方向变化数阈值为1。注

11、意，由于采用8邻点边界跟踪，因此方向变化数的最大值为4。假设阈值设成4,那么对原始边界没有平滑。边界跟踪和平滑常常结合在一起使用，见计算机作业3.5.算法边界跟踪算法间隔 测量在许多应用中，找到一幅图像中两个象素点或两个连通成分之间的间隔 是很有必要的。目前还没有定义数字图像间隔 的唯一方法，但对所有的象素点p，q和r,任何间隔 度量都必须满足以下性质：假设对S中象素i，j的所有邻点u，v有下式成立 (3.25)那么S中象素i,y到的间隔 d(i,j, )是局部最大值。S中所有到的间隔 是局部最大值的象素点集合称为对称轴或中轴，通常记为S，使用u,v4邻点的中轴变换的一些例子见图。图3.13(

12、b)说明少量噪声会使中轴变换结果产生显著的差异。由S和S中每一点到的间隔 能重构原始象素集S.S是s的简洁表示。S可用来表示一个区域的形状。通过去除S中与间隔 较小的象素点，可以生成一个简化的S 集。中轴可作为物体的一种简洁表示。但是，二值图像中的区域也可用其边界来表示。边界跟踪算法可用来获得表示边界的序列点。在第七章还将讨论用链码来简洁地表示边界的方法。对任意物体，边界将是区域的简洁表示。但要明确给定象素点是否在某一区域内，中轴那么是更好的表示，因为使用中轴上的象素点和每一个给定象素点的最大间隔 圆盘中轴间隔 变换，可以很容易地检测出给定象素是否在中轴定义的区域中。3.5.7 细化细化(th

13、inning)是一种图像处理运算，可以把二值图像区域缩成线条，以逼近区域的中心线，也称之为骨架或核线。细化的目的是减少图像成分，直到只留下区域的最根本信息，以便进一步分析和识别。虽然细化可以用在包含任何区域形状的二值图像，但它主要对细长形而不是凸圆形或水滴状)区域有效。细化一般用于文本分析预处理阶段，以便将文本图像中线条图画或字符笔画表示成单象素线条。细化要求如下：连通区域必须细化成连通线构造。细化结果最少应该是8连通(下面将要解释。保存终止线的位置。细化结果应该近似于中轴线。由细化引起的附加突刺(短分支)应该是最小的。细化结果应该保证第一条要求中所定义的连通性，这一点是最根本的要求，它保证了

14、连通线构造的数量等于原始图像中连通区域的数量。第二条要求保证所得到的线条总是含有8连通图像的最小数量。第三条要求说明终止线位置应该保持不变。细化可以通过迭代方式不断去除边界点来实现，在迭代过程中注意不要去除端点象素，因为这样不仅会缩短细化线，丢掉构造信息，而且不能保持其位置不变。第四条要求说明所得线段应能最好地逼近原始区域的中线，如两个象素点宽的竖线或程度线的真正中线应该位于这两个象素之间半个象素间距的位置。在数字图像中表示半个象素间距是不可能的，因此得到的结果是一条位于原直线一侧的直线。第五条要求没有明确指出噪声的影响控制到最低程度，因为判断噪声本身是一件很难的事。一般不希望原始区域含有会引

15、起突刺的隆起，但当某些较大隆起是区域特征时，却必须识别它们。应该指出，某些细化算法有去除突刺的参数，不过最好将细化和去除噪声分开进展，这是由于某些情况下不需要的突刺，可能是另一些情况下所需要的短线。因此，最好的方法是先进展细化，然后单独去除长度低于某一特定最小值的任何突刺。一种常用的细化手段是在至少3x3邻域内检查图像的每一点，剥去区域边界。一次剥去一层图像，直至区域被细化成一条线。这一过程是用迭代法实现的，见算法。 在每次迭代时，每一个象素点用nn窗函数检查，为了保持连通性或线末端位置，将单象素厚的边界擦除。在图中将会看到，在每次迭代中，值为1的外层区域就是用这种方式削掉的。当迭代结果没有变

16、化时，迭代过程完毕，图像得到细化。算法3.4 4邻点细化迭代算法对于每一个象素，假设没有上邻点下邻点左邻点右邻点；不是孤立点或终止线；去除该象素点不会断开区域，那么去除该象素点；重复这一步骤直到没有象素点可以去除。3.5.8 扩展与收缩图像中的一个连通成分可以进展全方位的扩展expanding)或收缩(shrinking)。假设某一连通成分可以变化，使得一些背景象素点变成1，这一运算就称为扩展。假设物体象素点全方位地消减或变为0时，那么称为收缩。一种简单的扩展与收缩实现方法如下：扩展:假设邻点是1,那么将该点从0变为1.收缩:假设邻点是0,那么将该点从1变为0.这样，收缩可以看作是扩展背景。这类运算的例子见图3.15.需要指出，扩展与收缩这样简单的运算可以完成非常有用而又貌似很复杂的运算。下面引进符号先扩展后收缩算法能补上不希望存在的洞，如图3.15(b)(d)所示；先收缩后扩展算法那么能去除孤立的噪卢点，见图3.15(c)(e)，请注意，扩展与收缩可用来确定孤立组元或簇，扩展后收缩有效地填满了空洞却不能去除噪声；相反，收缩后扩展能去除噪声却不能填满空洞。扩展与收缩算法的一般形式被广泛地用在形态图像处理和膨胀与腐蚀运算中。