基于有序点集距离的形状匹配算法.pdfVIP

第 49卷 第 12期 上 海 交 通 大 学 学 报 Vo1．49No．12 2015年 12月 JOuRNAL OFSHANGHAIJIA0 T0NG UNIVERSITY Dec．2O15 文章编号 ：1006—2467(2015)12—1826—07 DOI：10．16183／j．cnki．jsjtu．2015．12．013 基于有序点集距离的形状匹配算法 朱鹏伟， 李 勃 ， 王云烨， 陈启美 (南京大学 电子科学与工程学院，南京 210023) 摘 要 ：针对基于豪斯多夫距离的匹配算法存在 时间复杂度 高、较难处理部分匹配和无法精确对 位等问题，提 出了一种改进的基于有序点集距离的形状匹配算法．该算法利用轮廓 点集的有序性 ， 动态计算点集之 间的匹配关系．算法首先计算曲线的轮廓 点曲率，并根据 匹配代价作 出匹配矩 阵， 然后基于匹配矩 阵的连通情况来判断2幅图像是否匹配，最后依据最短连通路径 附近的像素点分 布来确定最终的匹配点．实验证明，本算法能加快匹配速度 ，较好地处理部分曲线匹配，并能确定匹 配轮廓点到点的一一对应关系． 关键词：形状匹配；曲率；有序点集距离；匹配矩阵；豪斯多夫距离 中图分类号：TP391 文献标志码：A ShapeMatchingAlgorithm BasedonDistanceofOrderedPoints ZHUPeng—wei， LIBo， WANG Yun—ye， CHEN Qi—mei (SchoolofElectronicScienceandEngineering，NanjingUniversity，Nanjing210023，China) Abstract：A shapematchingalgorithm wasproposedbasedonthedistanceoforderedpoints，which used theorderlinessofthecontourpointstocalculatethematchingrelationship betweenthecontoursdynami— cally．First，thealgorithm calculatedthecurvatureofeverypointanddrew thematchingmatrixaccording tOthematchingcost．Then，thefactthatwhetherthetwoimagesmatch ornotwasdetermined basedon theconnectivityofthematchingmatrix．Intheend，thefinalmatchingpointswereobtained byanalysing thepixeldistributionneartheshortestcommunication path．Realisticexperimentsprovethatthemethod canacceleratethematchingspeed，handlepartialmatching well，andmatcheverypointofeach contours accuratelyby． Keywords：shapematching；curvature；distanceoforderedpoints；matchingmatrix；Hausdorffdistance 形状匹配是计算机视觉和图像处理领域 中十分 集之问的平方距离 以及局部最小值的方法来进行曲 重要的一项技术．目前在这一领域 已经有 了很多匹 线匹配 ，算法可以在多项式时间内完成．文献Es]中 配算法，其中基于豪斯多夫 (Hausdorff)距离的匹配 提出了一种增量 Hausdorff距离计算方法 ，文献 [6] 算法 由于计算简便且匹配效果较好得到了广泛的应 中通过提取特征点来进行 曲线匹配，这些方法减小 用 ]．文献E33中提出了一种基于 Harris角点 的匹