《复杂物体轮廓提取.doc》由会员分享，可在线阅读，更多相关《复杂物体轮廓提取.doc（6页珍藏版）》请在金锄头文库上搜索。
1、复杂物体轮廓提取 本课题得到国家自然科学基金(69973043)与(60073024)资助。徐晓刚 于金辉 马利庄(浙江大学CAD&CG国家重点实验室,杭州 310027)摘要 图象分割是图象处理中的一项重要工作，目前手工与自动相结合的分割方法在实际工作中得到了广泛应用。本文根据图象经Maar变换后的特征，采用新的判断准则，提出了一种复杂物体边缘定位算法，可以对具有尖角特征的物体轮廓进行快速准确地提取，同时利用矢量化方法消除毛刺，使跟踪获得的边界更符合物体的实际轮廓特征。对多种图象的实验表明本文方法十分有效。关键词 复杂轮廓提取，Snake 算法，基于动态规划图搜索算法中图法分类号：TP751
2、.1Extraction of Complex Object ContourXU Xiao-gang YU Jin-hui MA Li-zhuang (State Key Lab of CAD&CG Zhejiang University Hangzhou 310027)Abstract Image segment plays an important role in the field of image processing, and currently the hybrid approach combining the manual and automatic methods is wid
3、ely used in segment practice. In this paper we present an algorithm capable of locating the target object contour of sharp tips accurately in the interactive rate. Considering that the edge are usually on the zero-crossing points after Marr transformation for most images, existing techniques tend to
4、 give undesirable results because the energy path containing more points is given less priority. In our method we specify a pointer to point the current point on a path of interest, when the energy of current path is less than the energy for the previous point, we check n latest points in the curren
5、t path instead of checking only one point as existing techniques do, and, if more than m point (mn) is zero-crossing, the pointer of the point is updated, otherwise, the pointer remains unchanged. Using this criterion we can insert new seeds automatically near the tips of the target object and the b
6、urr is eliminated by a vectorization approach. The final contour traced out fits the feature of the target object well and the effectiveness of our method is demonstrated by examples shown in the paper. Keywords contour detection, snake, graph searching formulation of dynamic programming.0引言图象分割是一项广
7、泛应用的图象处理技术。由于图象的多义性和复杂性，许多分割的工作无法依靠计算机自动完成，而手工分割又存在工作量大，定位不准确的难题，因此，人们提出了一些人工交互和计算机自动定位相结合的方法，利用各自的优势，实现目标轮廓的快速定位。纵观这些方法，它们大致可以归结为两类：一类为Snake 算法或Active Contour Models12；这类算法需要给出初始的轮廓，然后进行迭代，使轮廓沿能量降低的方向靠近，最后得到一个优化的边界。能量函数包括内外力两方面，如边界曲率和梯度。由于用户无法估计迭代的最后结果，应用Snake 算法往往需要进行多次的交互工作。特别当目标比较复杂时，或与其它物体靠得较近时
8、，初始的轮廓不易确定，而迭代的结果往往不能达到要求。另一类为基于动态规划图搜索算法345678；图搜索算法是在全图范围内寻找优化的边界。与Snake 算法不同，图搜索算法不通过迭代初始轮廓降低能量的方式，而是通过分步优化能量函数获得边界，但图搜索算法也需要一个初始的模板以约束搜索。Eric N. Mortensen37提出了一种更方便的交互提取目标轮廓的算法“Intelligent Scissors（IS）”，在搜索轮廓时与一般的图搜索算法有些类似，但可以更好地利用人的交互优势。该方法的基本思想是在设定种子点后，计算出图上各点到种子点的最小能量。由于边缘点多为零交叉点，其能量较邻点小，因而使能
9、量图呈“总线”结构，其中边缘为代表低能量的“总线”，从而在交互引导过程中自动勾勒出边缘。对于轮廓比较平滑的目标，37的方法可以获得比较好的效果，但在处理具有尖锐边角的目标时，对尖锐边角往往不能准确地定位从而造成“割角”。通过分析能量的迭代过程，本文提出了一种改进算法，克服了IS算法中的缺点，可以对复杂物体的边缘进行比较准确的定位，同时针对跟踪过程产生的“毛刺”现象，采用矢量化方法消除毛刺，使获得的边界具有比较好的视觉效果。1算法能量的计算方法有多种，如以轮廓线的亮度，曲率和长度来计算，或以梯度值，梯度方向和闭合曲线的曲率。从运算速度考虑，本文采用零交叉点，梯度值，梯度方向作为能量评价函数因子。
10、1.1能量的计算方法l(p,q)= （1） 式中，分别表示零交叉点，梯度值，梯度方向，q为p的邻点,，为权值，本文计算中采用4中的取值方法，对大多数图象，分别取为0.43, 0.14,0.43。1.1.1 的计算 （2）是对原图进行Marr变换得到的结果，对于，零交叉点的定义如下：1、该点为0；2、若相邻两点p,q为从正到负，且,则取绝对值小者为零交叉点。对大多数图象，阈值（threshold）选取为1.66较有效。实验表明，采用该方法可以克服一定噪声的影响，且比3中的算法更易跟踪到物体的边界。1.1.2的计算 计算梯度时可以采用不同的算子，对最终计算所得的能量影响较大的是模板的宽度，本文中采
11、用了高斯函数计算梯度。令, 表示x,y方向的梯度，则梯度G （3）为使高梯度产生低能量，令 （4）最后若q是p的对角邻点, 不变, 若q是p的水平或垂直邻点, 除以。1.1.3的计算因为梯度方向能量是对变化剧烈边缘的一种平滑，且当p,q两点相似时，其梯度方向所占的能量较小，因此这种能量因子的最终影响结果是使相似点归于同一条能量路径。 （5）其中 （6） （7）为常数3.14,“”表示矢量点乘。矢量 , （8） （9）式（8）中的分别为p,q点x,y方向梯度，式（9）中加黑的p,q表示p,q点的坐标。从上述能量的计算方法可以看出，分别起到了突出边缘，平滑边缘和归类相似点的作用，从而使用户能够快速
12、地找到边缘点。由于37中在计算新点的能量时，只考虑了与当前点的能量和能量差，也即新点的能量是当前点的能量与新增能量和（这里新点是当前点的邻点），这种计算只考虑邻点的影响，使实际路径距离短的能量值占优，所以在对具有尖角的物体定位时，将造成割角，如图1所示。 （a） （b） （c）图1 （a）原图。（b） 搜索后的定位边界。 （c）边界放大图。我们跟踪能量计算过程发现对于C点，由于通过OAEC的能量大于通过OABC的能量，从而导致无法检测到轮廓AEC。 我们可以从改变能量迭代算法和适当设置新的种子点两方面来解决上述问题。（1）采用新的迭代判断准则。对大多数图象，经过Marr变换后，边缘点一般处于零
13、交叉点，对同一点的两条能量路径，若边缘点多的一条不能占优显然不符合要求，因此当能量不占优时需要添加新的约束，本文根据能量路径上零交叉点数的多少来判断取舍。具体为在计算获得新点的能量后，若当前计算获得的能量大于已有的能量，则反向跟踪路径的最近n个点，统计两路径的零交叉点数，若当前路径的零交叉点数大于旧路径的零交叉点数，则用当前计算获得能量替换旧的能量，继续进行迭代。（2）在尖点处自动选取种子点。适时地插入新的种子点可以在一定程度上避免能量迭代误差引起的边缘定位不准确问题，显然，在尖点处自动插入新种子点则可以改善边缘定位准确性。在交互过程中，跟踪从种子点到当前点的路径，若发现路径方向发生剧烈的改变
14、，则在方向改变处设置新的种子点。判断方向是否改变的一般方法是计算相邻点间的角度，但在交互中显然不能满足实时性要求，因此，本文通过相邻点的变号情况（在八邻域中，相邻两点坐标通过+1，0，-1来表示，若两邻点“坐标值”发生变化，即为变号）来判断是否发生方向剧烈改变。由于交互中从边缘点到非边缘点也会发生方向剧烈改变，在实际应用中，从种子点到当前点，若累计发生两次方向剧烈改变，则在第一次发生改变的位置设置种子点。综上述，我们的能量迭代最终算法如下：1）初始化，设置种子点和标志位Flag=0；2）是否处理完毕，若是，转7；否则转3；3）计算当前点的八邻域点能量，若Flag=0，把能量值写入能量表，转4；
15、若Flag=1，转5；4）比较各邻域点能量，选取能量最小者进栈，转2；5）若新计算的能量小于旧的能量，把能量值写入能量表，转4；否则转6；6）反向跟踪新，旧能量的路径，统计最近一段距离内过零点的数量；若，则把新能量值写入能量表，转4；否则转4；7）结束。1.2平滑处理受噪声的干扰，跟踪得到的边缘会产生毛刺，如图3（b）（d）（e）和图4（b）（d）（e）所示。本文采用矢量化方法快速消除毛刺，见图2。 图2 矢量化方法消除毛刺。对于任意点A与B，检查曲线AB之间各点到直线AB距离，取最大距离点C，连接AC, CB；检查曲线AC之间各点到直线AC距离，取最大距离点D，连接AD, DC；对曲线CB同样处理；当距离达到设定阈值或两点之间小于设定的点数时，迭代结束。上述算法的极限收敛于原曲线，可以根据不同的要求设置误差。迭代完成后，对各线段离散化，即可得到连续的边缘曲线。
