《复杂物体轮廓提取》由会员分享，可在线阅读，更多相关《复杂物体轮廓提取（6页珍藏版）》请在金锄头文库上搜索。
1、复杂物体轮廓提取徐晓刚 于金辉 马利庄 (浙江大学 CAD 0 qIifqIifqfLL Z是对原图进行 Marr 变换得到的结果，对于，零交叉点的定义如下：1、该点为 0；2、若LILI相邻两点 p,q 为从正到负，且,则取绝对值小者为零交叉点。对大多数图象，阈thresholdIIqp值（threshold）选取为 1.66 较有效。实验表明，采用该方法可以克服一定噪声的影响，且比3中的 算法更易跟踪到物体的边界。1.1.2的计算 qfG计算梯度时可以采用不同的算子，对最终计算所得的能量影响较大的是模板的宽度，本文中采用了高斯函数计算梯度。令, 表示 x,y 方向的梯度，则梯度 GxIyI
2、（3）22 yxIIG为使高梯度产生低能量，令（4） GG GGGfGmax1maxmax最后若 q 是 p 的对角邻点, 不变, 若 q 是 p 的水平或垂直邻点, 除以。 qfG qfG21.1.3的计算qpfD,因为梯度方向能量是对变化剧烈边缘的一种平滑，且当 p,q 两点相似时，其梯度方向所占的能 量较小，因此这种能量因子的最终影响结果是使相似点归于同一条能量路径。（5）11,cos,cos1,qpdqpdqpfqpD 其中（6） qp,LpDqpdp,（7） qDqp,Lqpdq,为常数 3.14,“”表示矢量点乘。矢量, （8） pIpIxy,pD qIqIxy,qD（9） 0;0
3、; pqpDqppqpDpqqp,Lifif式（8）中的分别为 p,q 点 x,y 方向梯度，式（9）中加黑的 p,q 表示 p,q qIqIpIpIyxyx,点的坐标。从上述能量的计算方法可以看出，分别起到了突出边缘，平 qfZ qfGqpfD,滑边缘和归类相似点的作用，从而使用户能够快速地找到边缘点。 由于37中在计算新点的能量时，只考虑了与当前点的能量和能量差，也即新点的能量是当前 点的能量与新增能量和（这里新点是当前点的邻点） ，这种计算只考虑邻点的影响，使实际路径距离 短的能量值占优，所以在对具有尖角的物体定位时，将造成割角，如图 1 所示。（a） （b） （c）图 1 （a）原图。
4、 （b） 搜索后的定位边界。 （c）边界放大图。我们跟踪能量计算过程发现对于 C 点，由于通过 OAEC 的能量大于通过 OABC 的能量，从而导致无 法检测到轮廓 AEC。我们可以从改变能量迭代算法和适当设置新的种子点两方面来解决上述问题。 （1）采用新的迭代判断准则。对大多数图象，经过 Marr 变换后，边缘点一般处于零交叉点， 对同一点的两条能量路径，若边缘点多的一条不能占优显然不符合要求，因此当能量不占优时需要 添加新的约束，本文根据能量路径上零交叉点数的多少来判断取舍。具体为在计算获得新点的能量后，若当前计算获得的能量大于已有的能量，则反向跟踪路径的最近 n 个点，统计两路径的零交叉
5、 点数，若当前路径的零交叉点数大于旧路径的零交叉点数，则用当前计算获得能量替换旧的能量， 继续进行迭代。 （2）在尖点处自动选取种子点。适时地插入新的种子点可以在一定程度上避免能量迭代误差引 起的边缘定位不准确问题，显然，在尖点处自动插入新种子点则可以改善边缘定位准确性。在交互 过程中，跟踪从种子点到当前点的路径，若发现路径方向发生剧烈的改变，则在方向改变处设置新 的种子点。判断方向是否改变的一般方法是计算相邻点间的角度，但在交互中显然不能满足实时性 要求，因此，本文通过相邻点的变号情况（在八邻域中，相邻两点坐标通过+1，0，-1 来表示，若两 邻点“坐标值”发生变化，即为变号）来判断是否发生
6、方向剧烈改变。由于交互中从边缘点到非边 缘点也会发生方向剧烈改变，在实际应用中，从种子点到当前点，若累计发生两次方向剧烈改变， 则在第一次发生改变的位置设置种子点。 综上述，我们的能量迭代最终算法如下： 1）初始化，设置种子点和标志位 Flag=0； 2）是否处理完毕，若是，转 7；否则转 3； 3）计算当前点的八邻域点能量，若 Flag=0，把能量值写入能量表，转 4；若 Flag=1，转 5； 4）比较各邻域点能量，选取能量最小者进栈，转 2； 5）若新计算的能量小于旧的能量，把能量值写入能量表，转 4；否则转 6；6）反向跟踪新，旧能量的路径，统计最近一段距离内过零点的数量；若，oldn
7、ewNN,oldnewNN则把新能量值写入能量表，转 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 同样处理；当 距离达到设定阈值或两点之间小于设定的点数时，迭代结束。上述算法的极限收敛于原曲线，可以 根据不同的要
8、求设置误差。迭代完成后，对各线段离散化，即可得到连续的边缘曲线。2 实验结果我们用毛笔字以及葵花图片对本文提出的算法进行实验。图 3 和图 4 中（a）系原图。 （b）为7算 法得到轮廓。 （c）为7算法平滑后轮廓。 （d）为1 算法得到轮廓。 （e）为本文算法得到轮廓。 （f） 为本文算法平滑后轮廓。 从图中可以看出，采用7的算法时，图 3 和图 4 的（b） （c）中“讯”字和花瓣的几个尖角被 “割”掉了。采用1的 Snake 算法其结果更差（图 3（d）和图 4（d） ） ，无法对复杂物体进行定位。 采用本文算法的图 3 和图 4（e） （f）比较准确地勾勒出了“讯”字和花瓣的外轮廓。（
9、a） （b） （c） （d） （e） （f）图 3（a）原图。 （b）7算法得到轮廓。 （c）7算法平滑后轮廓。 （d）1 算法得到轮廓。 （e）本文算法得到轮廓。 （f）本文算法平滑后轮廓。（a） （b） （c） （d）（e） （f） 图 4（a）原图。 （b）7算法得到轮廓。 （c）7算法平滑后轮廓。 （d）1 算法得到轮廓。 （e）本文算法得到轮廓。 （f）本文算法平滑后轮廓。3 结束语Snake 算法和图搜索算法在目标的匹配定位中已得到了广泛的应用，但无法对复杂物体的轮廓进 行准确定位，本文针对复杂物体，提出了一种有效的轮廓交互提取算法。可以较好地保持目标的尖 角特征，避免了以往算法中
10、的“割角”问题，提高了轮廓跟踪的准确性。参 考 文 献 1 Williams. Donna and Shah. Mubarak. “A Fast Algorithm for Active Contours and Curvature Estimation“, CVGIP: Image Understanding. Vol. 55, No. 1, January 1992. pp. 14-26. 2 M. Kass, A. Witkin, D. Terzopoulos. Snake: Active Contour Models. International Journal of Computer
11、 Vision. Vol.1, No.4, pp.321-331, 1988. 3 E. N. Mortensen and W. A. Barrett, “Intelligent Scissors for Image Composition,” in Proceedings of the ACM SIGGRAPH 95, pp. 191-198, Los Angeles, CA, Aug. 1995. 4 E. N. Mortensen, B. S. Morse, W. A. Barrett, and J. K. Udupa, “Adaptive Boundary Detection Usin
12、g Live-Wire Two-Dimensional Dynamic Programming,” in IEEE Proceedings of Computers in Cardiology, pp. 635-638, Durham, NC,Oct. 1992. 5 Y. P. Chien and K. S. Fu, “A Decision Function Method for Boundary Detection,” Computer Graphics and Image Processing, vol. 3, no. 2, pp. 125-140, June 1974. 6 A. Ma
13、rtelli, “An Application of Heuristic Search Methods to Edge and Contour Detection,” Communications of the ACM, vol. 19, no. 2, pp. 73-83, Feb. 1976.7 E. N. Mortensen, L. J. Reese, and W. A. Barrett, “Intelligent Selection Tools,“ in Proc. IEEE: Computer Vision and Pattern Recognition (CVPR00), Vol.
14、II, pp. 776-777, Hilton Head, SC, June 2000.8 B. S. Morse, W. A. Barrett, J. K. Udupa, and R. P. Burton, Trainable Optimal Boundary Finding Using Two-Dimensional Dynamic Programming. Technical Report No. MIPG180, Department of Radiology, University of Pennsylvania, Philadelphia, PA, March 1991.徐晓刚 1967年生，博士，讲师，现为浙江大学CAD&CG国家重点实验室博士后。目前研究方向为 图象处理，计算机动画，虚拟现实，系统仿真。于金辉 1960年生，博士，副教授，研究方向为计算机辅助制作卡通动画，非真实感绘制技术，物 体变形技术，计算机生成装饰物体，计算机书法，计算机美术等。马利庄 1963年生，博士，研究员，博士生导师，国家杰出青年基金，中国青年科技奖获得者，目 前研究方向为CAGD，计算机动画。 Email:
