基于轮廓的形状匹配方法研究
|
摘要
近几十年来,计算机技术取得了很大的进步,其中,尤为明显的是互联网技术的发展和推广应用,在这一过程中产生了大量的多媒体信息,其中又是以图像信息为最直观、最重要的表示方式。如何从这些纷繁复杂的图像信息中找到所需要的图像也就成为了当今热门的研究领域。在计算机视觉领域中,一幅图像存在这多个底层特征,主要有：颜色、纹理、形状等,其中形状是一种描述图像轮廓的特征,它是人类识别物体最主要的信息,因此形状特征在图像描述和相似度计算过程中起到了尤为重要的作用。
形状匹配的研究主要包括形状描述和相似度计算两个方面。在形状描述中主要有基于轮廓的形状描述和基于区域的形状描述两种方法；在相似度计算中主要是按照一定的准则计算两个形状之间的相似度,完成形状匹配。本文主要从基于轮廓的形状描述方法,对形状的描述以及相应的相似度计算方法进行了研究,提出了基于轮廓分割的形状匹配方法和基于图结构的形状匹配方法以及两种方法相应的相似度计算方法。
本文的工作的主要内容有：
对于形状的轮廓曲线,本文采用离散曲线演化的方法得到简化多边形,根据得到的简化多边形的顶点分别采用：
(1)将轮廓曲线分成若干个片段,对于每个小的片段提取片段上的曲率极大值以及空间方向向量作为其片段描述子,然后所有的片段描述子组成了整个形状的描述子,对每两个片段之间进行距离计算得到形状片段之间的距离矩阵,再根据匈牙利算法得到距离矩阵中的最小代价,从而完成形状匹配。实验证明该方法原理简单,易于实现,具有平移,缩放等不变性。
(2)进行Delaunay三角剖分得到Delaunay图,使用图结构来描述形状问题,对Delaunay图中的每个图结构提取相同的采样点,根据这些采样点构造最小外接圆,将采样点分割成若干个区域,得到二维直方图来描述形状。然后计算出区域之间的地面距离矩阵,再根据EMD方法的推广形式得到描述子之间的距离,从而完成形状匹配。实验证明该方法能很好的反映不同类形状之间的差别,具有较好的匹配效果,具有平移、缩放、旋转等不变性。
In recent decades, computer technology has made great progress, especially the development of Internet technology, this process produces a large number of multimedia information, in which the image information is the most intuitive representation. How to find images we need from a great number of images has become a popular field of research. In the field of computer vision, images have multiple underlying characteristics:color, texture, shape and so on. Shape is a way to describe the characteristics of the image contour. It is the most important information for object recognition. So shape plays a crucial role in the image description and similarity measurement.
The study of shape matching includes shape description and similarity measurement. Shape description mainly includes two kind of methods:contour based and region based. Similarity measurement is to calculate the distance between two shapes by a certain criteria, and completes the shape matching. This paper is mainly based on shape contour description methods. Two different kinds of shape descriptors and their similarity measurement methods are carried out. One new method of shape matching is by contour segmentation. Another shape matching method is based on the graph structure.
The main content of this paper is as follow:
Considering the contour of the shape, this paper uses the discrete curve evolution method to obtain a simplify polygon. According to the vertices of the simplify polygon, two novel methods are proposed:
(1) The contour is divided into several fragments, and we extract the maximum curvature value and the direction vector of each segment as the segment descriptor. The whole segment descriptors form a shape descriptor. And then segment distance matrix is calculated, the minimum value of distance matrix is obtained with Hungarian algorithm. Experiments proof that the principle of this method is simple and it is easy to implement. This method has translation and scaling invariance.
(2)Delaunay triangulation is used to obtain Delaunay graph for shape contour. We use graph structure to describe the problem of the shape. The same number of sampling points are extracted for each Delaunay graph. According to these sampling points, the minimum circumcircle is constructed to divide the sampling points into several zones. And2-dimension histogram is obtained to describe the shape. Then ground distance matrix is calculated for different zones. After that the improved EMD method is used to obtain distance to complete shape matching. Experiments show that this method can reflect the difference between different types of shape and it has translation, scaling and rotation invariance.
形状匹配的研究主要包括形状描述和相似度计算两个方面。在形状描述中主要有基于轮廓的形状描述和基于区域的形状描述两种方法；在相似度计算中主要是按照一定的准则计算两个形状之间的相似度,完成形状匹配。本文主要从基于轮廓的形状描述方法,对形状的描述以及相应的相似度计算方法进行了研究,提出了基于轮廓分割的形状匹配方法和基于图结构的形状匹配方法以及两种方法相应的相似度计算方法。
本文的工作的主要内容有：
对于形状的轮廓曲线,本文采用离散曲线演化的方法得到简化多边形,根据得到的简化多边形的顶点分别采用：
(1)将轮廓曲线分成若干个片段,对于每个小的片段提取片段上的曲率极大值以及空间方向向量作为其片段描述子,然后所有的片段描述子组成了整个形状的描述子,对每两个片段之间进行距离计算得到形状片段之间的距离矩阵,再根据匈牙利算法得到距离矩阵中的最小代价,从而完成形状匹配。实验证明该方法原理简单,易于实现,具有平移,缩放等不变性。
(2)进行Delaunay三角剖分得到Delaunay图,使用图结构来描述形状问题,对Delaunay图中的每个图结构提取相同的采样点,根据这些采样点构造最小外接圆,将采样点分割成若干个区域,得到二维直方图来描述形状。然后计算出区域之间的地面距离矩阵,再根据EMD方法的推广形式得到描述子之间的距离,从而完成形状匹配。实验证明该方法能很好的反映不同类形状之间的差别,具有较好的匹配效果,具有平移、缩放、旋转等不变性。
In recent decades, computer technology has made great progress, especially the development of Internet technology, this process produces a large number of multimedia information, in which the image information is the most intuitive representation. How to find images we need from a great number of images has become a popular field of research. In the field of computer vision, images have multiple underlying characteristics:color, texture, shape and so on. Shape is a way to describe the characteristics of the image contour. It is the most important information for object recognition. So shape plays a crucial role in the image description and similarity measurement.
The study of shape matching includes shape description and similarity measurement. Shape description mainly includes two kind of methods:contour based and region based. Similarity measurement is to calculate the distance between two shapes by a certain criteria, and completes the shape matching. This paper is mainly based on shape contour description methods. Two different kinds of shape descriptors and their similarity measurement methods are carried out. One new method of shape matching is by contour segmentation. Another shape matching method is based on the graph structure.
The main content of this paper is as follow:
Considering the contour of the shape, this paper uses the discrete curve evolution method to obtain a simplify polygon. According to the vertices of the simplify polygon, two novel methods are proposed:
(1) The contour is divided into several fragments, and we extract the maximum curvature value and the direction vector of each segment as the segment descriptor. The whole segment descriptors form a shape descriptor. And then segment distance matrix is calculated, the minimum value of distance matrix is obtained with Hungarian algorithm. Experiments proof that the principle of this method is simple and it is easy to implement. This method has translation and scaling invariance.
(2)Delaunay triangulation is used to obtain Delaunay graph for shape contour. We use graph structure to describe the problem of the shape. The same number of sampling points are extracted for each Delaunay graph. According to these sampling points, the minimum circumcircle is constructed to divide the sampling points into several zones. And2-dimension histogram is obtained to describe the shape. Then ground distance matrix is calculated for different zones. After that the improved EMD method is used to obtain distance to complete shape matching. Experiments show that this method can reflect the difference between different types of shape and it has translation, scaling and rotation invariance.
引文
[1]章毓晋.图像理解与计算机视觉[M].北京：清华大学出版社,2000.
[2]吕科.基于物体轮廓的曲线技术研究[D].西安,西北大学,2003.
[3]丁险峰,吴洪,张洪江等.形状匹配综述[J].自动化学报,2001,27(5)：678-693.
[4]Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions On Pattern Analysis And Machine Intelligence.2002,24(4):509-522.
[5]Mori G, Belongie S, Malik J. Efficient shape matching using shape contexts[J]. IEEE Transactions On Pattern Analysis And Machine Intelligence.2005,27(11): 1832-1837.
[6]Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing shock graphs[C]//In:IEEE International Conference on Computer Vision.2001.
[7]Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(5):550-571.
[8]Klein P N, Sebastian T B, Kimia B B. Shape matching using edit-distance:an implementation[J]. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms.2001:781-790.
[9]Kimia B B, Tannenbaum A R, Zucker S W. Shape, shocks and deformations[J]. International Journal Of Computer Vision.1995,15(3):189-224.
[10]Chui H, Rangarajan A. A new point matching algorithm for non-rigid registration[J]. Computer Vision And Image Understanding.2003,89(2): 114-141.
[11]Chui H, Rangarajan A. A new point matching algorithm for non-rigid point matching[C]//In:IEEE Conference on Computer Vision and Pattern Recognition.2000:44-51.
[12]Yang X, Bai X, Latecki L J, et al. Improving shape retrieval by learning graph transduction[C]//In:European Conference on Computer Vision.2008.
[13]http://www.engineeringvillage.org[Z]:2013.
[14]Kim H, Kim J. Region-based shape descriptor invariant to rotation, scale and translation[J]. Signal Processing. Image Communication.2000,16:87-93.
[15]Zhang D, Lu G. Review of shape representation and description techniques [J]. Pattern Recognition.2004,37(1):1-19.
[16]Latecki L J, Lakamper R. Convexity rule for shape decomposition based on discrete contour evolution[J]. Computer Vision And Image Understanding.1999, 73(3):441-454.
[17]Felzenszwalb P F, Schwartz J. Hierarchical matching of deformable shapes [C]// In:CVPR.2007.
[18]Lu G J, Sajjanhar A. Region-based shape representation and similarity measure suitable for content-based image retrieval[J]. Mutimedia System.1999,7(2): 165-174.
[19]Chakrabarti K, Binderberger M O, Porkaew K, et al. Similar shape retrieval in MARS[C]. In:IEEE International Conference on Multimedia and Expo. New York, USA:2000:141-144.
[20]Zhang D S, Lu G. Generic Fourier descriptor for shape-based image retrieval[C] //In:IEEE International Conference on Multimedia and Expo. Lausanne, Switzerland:2002:425-428.
[21]Zhang D S, Lu G. Enhanced generic Fourier descriptor for object-based image retrieval[C]. In:IEEE International Conference on Acoutics, Speech and Signal Processing. Orlando, FL, USA:2002:3668-3671.
[22]Blum H. A transformation for extracting new descriptors of shape[C]//In: Whaten-dunn W. Models for the Perception of Speech and Visual Forms. Cambridge, MA:MIT Press,1967:362-380.
[23]David M. Mathematic theories of shape:Do they model perception?[C]//In: Geometric Methods in Computer Vision, SPIE. San Diego. VA. USA:1991. 2-10.
[24]Bookstein F L. Thin-plate splines and the decompostion of deformations [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1989,11 (6): 567-585.
[25]Chui H L, Rangarajan A. A new algorithm for non-rigid point matching[C]//In: Computer Vision and Pattern Recognition,2000,44-51.
[26]Christos H P, Kenneth S. Combinatorial optimization:algorithms and complexity [M], Dover Publications,1998.
[27]Zheng Y F, Doermann D. Robust point matching for non-rigid shapes by preserving local neighborhood structures [J], Pattern Analysis and Machine Intelligence,2006,28(4):643-649.
[28]Freeman H. On the encoding of arbitrary geometric conlgurations[J]. IRE Trans. Electron. Comput. EC-10 (1961):260-268.
[29]Pavlidis T. Algorithms for graphics and image processing[M]. PHD, Spinger, Berlin,1982.
[30]章志勇,潘志庚,张明敏等.基于多尺度通用傅里叶描述子的灰度图像检索[J].中国图象图形学报,2005,10(5)：612-615.
[31]赵荣梅.数字图像处理导论[M].西安,西北工业大学出版社,1995.
[32]孙冬,明军.基于小波域分形编码的图像插值[J].中国图象图形学报,2007,12(12)：2063-2067.
[33]于秋则,金文.基于边缘正则化小波描述的多传感器图像自动配准研究[J].信号处理,2005,21(1)：35-40.
[34]孙君顶,赵珊.图像体层特征提取与检索技术[M].北京,电子工业出版社,2009.
[35]刘进,张天序.图像不变矩的推广[J].计算机学报,2004,27(5)：668-674.
[36]范春年,傅德胜.一种改进的二维傅里叶描述子在基于形状的图像检索中的应用[J].武汉理工大学学报(交通科学与工程版),2004,2(28)：266-269.
[37]Bo G P, Kyoung M L, Sang U L. Color-based image retrieval using perceptually modified Hausdorff distance [J]. EURASIP Journal on Image and Video Processing,2008,1(10):1-10.
[38]Huang X, Zhang S, Wang G, et al. A new image retrieval method based on optimal color matching [C]//In:Proceedings of the International Conference on Image Processing, Computer Vision & Pattern Recognition (IPCV'06), Las Vegas, Nev, USA, June 2006,1(1):276-281.
[39]Stefano B, Alberto D B, Pietro P. Retrieval by shape similarity with perceptual distance and effective indexing [J]. IEEE Trans on Multimedia,2000, 2(4):225-239.
[40]Latecki L J, Lakamper R. Convexity rule for shape decomposition based on discrete curve evolution [J]. Computer Vision and Image Understanding,1999, 73:441-454.
[41]Latecki L J, Lakamper R. Polygon evolution by vertex deletion [C]//In:Proc. Int'l Conf. Scale-Space,1999,398-409.
[42]Latecki L J, Lakamper R. Shape similarity measure based on correspondence of visual parts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(10):1185-1190.
[43]Latecki L J, Lakamper R. Application of planar shape comparison to object retrieval in image databases [J]. Pattern Recognition,2002,35(1):15-29.
[44]Mokhtarian F, Abbasi S, Kittler J. Efficient and robust retrieval by shape content through curvature scale space [C]//In:Int. Workshop on Image Databases and Multi-Media Search, Aug.1996:35-42.
[45]Papadimitriou C, Stieglitz K. Combinational optimization:algorithm and complexity [C]//In:Prentice Hall,1982.
[46]Luo B, Wilson R C, Hancock E R. Spectral embedding of graghs [J]. Pattern Recognition,2003,36(10):2213-2230.
[47]Gao X B, Xiao B,Tao D C, et al. Image categorization:graph edit distance+ edge direction histogram [J]. Pattern Recognition,2008,41(10):3179-3191.
[48]Rubner Y, Tomasi C, Guibas L J. The earth mover's distance as a metric for image retrieval [J]. International Journal of Computer Vision,2000,40(2): 99-121.
[49]Leichter I. Mean shift trackers with cross-bin metrics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(4):695-706.
[50]Pele O, Werman M. Fast and robust earth mover's distances [C]//In: Proceedings of the 12th IEEE International Conference on Computer Vision. Washington DC: IEEE Computer Society,2009:460-467.
[2]吕科.基于物体轮廓的曲线技术研究[D].西安,西北大学,2003.
[3]丁险峰,吴洪,张洪江等.形状匹配综述[J].自动化学报,2001,27(5)：678-693.
[4]Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts[J]. IEEE Transactions On Pattern Analysis And Machine Intelligence.2002,24(4):509-522.
[5]Mori G, Belongie S, Malik J. Efficient shape matching using shape contexts[J]. IEEE Transactions On Pattern Analysis And Machine Intelligence.2005,27(11): 1832-1837.
[6]Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing shock graphs[C]//In:IEEE International Conference on Computer Vision.2001.
[7]Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(5):550-571.
[8]Klein P N, Sebastian T B, Kimia B B. Shape matching using edit-distance:an implementation[J]. Proceedings of the twelfth annual ACM-SIAM symposium on Discrete algorithms.2001:781-790.
[9]Kimia B B, Tannenbaum A R, Zucker S W. Shape, shocks and deformations[J]. International Journal Of Computer Vision.1995,15(3):189-224.
[10]Chui H, Rangarajan A. A new point matching algorithm for non-rigid registration[J]. Computer Vision And Image Understanding.2003,89(2): 114-141.
[11]Chui H, Rangarajan A. A new point matching algorithm for non-rigid point matching[C]//In:IEEE Conference on Computer Vision and Pattern Recognition.2000:44-51.
[12]Yang X, Bai X, Latecki L J, et al. Improving shape retrieval by learning graph transduction[C]//In:European Conference on Computer Vision.2008.
[13]http://www.engineeringvillage.org[Z]:2013.
[14]Kim H, Kim J. Region-based shape descriptor invariant to rotation, scale and translation[J]. Signal Processing. Image Communication.2000,16:87-93.
[15]Zhang D, Lu G. Review of shape representation and description techniques [J]. Pattern Recognition.2004,37(1):1-19.
[16]Latecki L J, Lakamper R. Convexity rule for shape decomposition based on discrete contour evolution[J]. Computer Vision And Image Understanding.1999, 73(3):441-454.
[17]Felzenszwalb P F, Schwartz J. Hierarchical matching of deformable shapes [C]// In:CVPR.2007.
[18]Lu G J, Sajjanhar A. Region-based shape representation and similarity measure suitable for content-based image retrieval[J]. Mutimedia System.1999,7(2): 165-174.
[19]Chakrabarti K, Binderberger M O, Porkaew K, et al. Similar shape retrieval in MARS[C]. In:IEEE International Conference on Multimedia and Expo. New York, USA:2000:141-144.
[20]Zhang D S, Lu G. Generic Fourier descriptor for shape-based image retrieval[C] //In:IEEE International Conference on Multimedia and Expo. Lausanne, Switzerland:2002:425-428.
[21]Zhang D S, Lu G. Enhanced generic Fourier descriptor for object-based image retrieval[C]. In:IEEE International Conference on Acoutics, Speech and Signal Processing. Orlando, FL, USA:2002:3668-3671.
[22]Blum H. A transformation for extracting new descriptors of shape[C]//In: Whaten-dunn W. Models for the Perception of Speech and Visual Forms. Cambridge, MA:MIT Press,1967:362-380.
[23]David M. Mathematic theories of shape:Do they model perception?[C]//In: Geometric Methods in Computer Vision, SPIE. San Diego. VA. USA:1991. 2-10.
[24]Bookstein F L. Thin-plate splines and the decompostion of deformations [J]. IEEE Transaction on Pattern Analysis and Machine Intelligence,1989,11 (6): 567-585.
[25]Chui H L, Rangarajan A. A new algorithm for non-rigid point matching[C]//In: Computer Vision and Pattern Recognition,2000,44-51.
[26]Christos H P, Kenneth S. Combinatorial optimization:algorithms and complexity [M], Dover Publications,1998.
[27]Zheng Y F, Doermann D. Robust point matching for non-rigid shapes by preserving local neighborhood structures [J], Pattern Analysis and Machine Intelligence,2006,28(4):643-649.
[28]Freeman H. On the encoding of arbitrary geometric conlgurations[J]. IRE Trans. Electron. Comput. EC-10 (1961):260-268.
[29]Pavlidis T. Algorithms for graphics and image processing[M]. PHD, Spinger, Berlin,1982.
[30]章志勇,潘志庚,张明敏等.基于多尺度通用傅里叶描述子的灰度图像检索[J].中国图象图形学报,2005,10(5)：612-615.
[31]赵荣梅.数字图像处理导论[M].西安,西北工业大学出版社,1995.
[32]孙冬,明军.基于小波域分形编码的图像插值[J].中国图象图形学报,2007,12(12)：2063-2067.
[33]于秋则,金文.基于边缘正则化小波描述的多传感器图像自动配准研究[J].信号处理,2005,21(1)：35-40.
[34]孙君顶,赵珊.图像体层特征提取与检索技术[M].北京,电子工业出版社,2009.
[35]刘进,张天序.图像不变矩的推广[J].计算机学报,2004,27(5)：668-674.
[36]范春年,傅德胜.一种改进的二维傅里叶描述子在基于形状的图像检索中的应用[J].武汉理工大学学报(交通科学与工程版),2004,2(28)：266-269.
[37]Bo G P, Kyoung M L, Sang U L. Color-based image retrieval using perceptually modified Hausdorff distance [J]. EURASIP Journal on Image and Video Processing,2008,1(10):1-10.
[38]Huang X, Zhang S, Wang G, et al. A new image retrieval method based on optimal color matching [C]//In:Proceedings of the International Conference on Image Processing, Computer Vision & Pattern Recognition (IPCV'06), Las Vegas, Nev, USA, June 2006,1(1):276-281.
[39]Stefano B, Alberto D B, Pietro P. Retrieval by shape similarity with perceptual distance and effective indexing [J]. IEEE Trans on Multimedia,2000, 2(4):225-239.
[40]Latecki L J, Lakamper R. Convexity rule for shape decomposition based on discrete curve evolution [J]. Computer Vision and Image Understanding,1999, 73:441-454.
[41]Latecki L J, Lakamper R. Polygon evolution by vertex deletion [C]//In:Proc. Int'l Conf. Scale-Space,1999,398-409.
[42]Latecki L J, Lakamper R. Shape similarity measure based on correspondence of visual parts [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000,22(10):1185-1190.
[43]Latecki L J, Lakamper R. Application of planar shape comparison to object retrieval in image databases [J]. Pattern Recognition,2002,35(1):15-29.
[44]Mokhtarian F, Abbasi S, Kittler J. Efficient and robust retrieval by shape content through curvature scale space [C]//In:Int. Workshop on Image Databases and Multi-Media Search, Aug.1996:35-42.
[45]Papadimitriou C, Stieglitz K. Combinational optimization:algorithm and complexity [C]//In:Prentice Hall,1982.
[46]Luo B, Wilson R C, Hancock E R. Spectral embedding of graghs [J]. Pattern Recognition,2003,36(10):2213-2230.
[47]Gao X B, Xiao B,Tao D C, et al. Image categorization:graph edit distance+ edge direction histogram [J]. Pattern Recognition,2008,41(10):3179-3191.
[48]Rubner Y, Tomasi C, Guibas L J. The earth mover's distance as a metric for image retrieval [J]. International Journal of Computer Vision,2000,40(2): 99-121.
[49]Leichter I. Mean shift trackers with cross-bin metrics [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2012,34(4):695-706.
[50]Pele O, Werman M. Fast and robust earth mover's distances [C]//In: Proceedings of the 12th IEEE International Conference on Computer Vision. Washington DC: IEEE Computer Society,2009:460-467.