形状匹配方法研究与展望

周瑜; 刘俊涛; 白翔

doi:10.3724/SP.J.1004.2012.00889

形状匹配方法研究与展望

doi: 10.3724/SP.J.1004.2012.00889

周瑜¹,
刘俊涛^1,2, ,,
白翔¹

1.
华中科技大学电子与信息工程系武汉 430074;
2.
军械工程学院计算机工程系石家庄 050003

详细信息

通讯作者:
刘俊涛,军械工程学院计算机工程系讲师.现为华中科技大学电信系博士研究生.主要研究方向为计算机视觉,计算机图形学和模式识别.E-mail: ropobox@21cn.com

计量
- 文章访问数: 13561
- HTML全文浏览量: 83
- PDF下载量: 4219
- 被引次数: 0
出版历程
- 收稿日期: 2011-11-19
- 修回日期: 2012-02-10
- 刊出日期: 2012-06-20

Research and Perspective on Shape Matching

ZHOU Yu¹,
LIU Jun-Tao^{1,2
, ,},
BAI Xiang¹

1.
Department of Electronics and Information Engineering, Huazhong University of Science and Technology, Wuhan 430074;
2.
Department of Computer Engineering, Mechanical Engineering Institute, Shijiazhuang 050003

摘要

摘要: 形状匹配及分类是计算机视觉中的重要问题. 近年来,以形状上下文为代表的基于轮廓的形状匹配方法和以奇点图为代表的基于骨架的形状匹配方法获得了长足的发展. 本文介绍了形状匹配问题的基本概念, 分析了形状匹配问题的难点, 按照基于轮廓和基于骨架的分类方法对近年来最新出现的形状表示与形状匹配的方法进行了详尽的介绍, 并介绍了基于度量学习的形状检索方法, 本文还详细介绍了近年来形状匹配研究领域常用的一些测试数据库, 之后对局部形状匹配和形状分类等有潜力的研究方向进行了展望. 最后对形状匹配的整体框架及其应用前景进行了总结.
- 形状表示 /
- 形状匹配 /
- 形状分类 /
- 轮廓 /
- 骨架
Abstract: Shape matching and classification are important issues in computer vision. In recent years, contour-based shape matching approaches (e.g., shape context) and skeleton-based shape matching methods (e.g., shock graph) both have a lot of developments. In this paper, we introduce the basic concept of shape matching, give the difficulties of this topic, and provide a detailed review on the most recent approaches about shape representation and matching for both contour-based and skeleton-based methods. We also give a brief introduction about metric learning based shape retrieval. Moreover, we introduce some widely used benchmarks for shape matching in details, along with some hot topics including partial shape matching, shape classification, etc. Finally, this paper concludes with the whole framework of shape matching and the application perspective of this topic.
- Shape representation /
- shape matching /
- shape classification /
- contour /
- skeleton

HTML全文

参考文献(1)

[1]

Ding Xian-Feng, Wu Hong, Zhang Hong-Jiang, Ma Song-De. Review on shape matching. Acta Automatica Sinica, 2001, 27(5): 678-694 (丁险峰, 吴洪, 张宏江, 马颂德. 形状匹配综述. 自动化学报, 2001, 27(5): 678-694)[2] Blum H. Biological shape and visual science (Part I). Journal of Theoretical Biology, 1973, 38(2): 205-287[3] Belongie S, Malik J, Puzicha J. Shape matching and object recognition using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2002, 24(4): 509-522[4] Daliri M R, Torre V. Robust symbolic representation for shape recognition and retrieval. Pattern Recognition, 2008, 41(5): 1782-1798[5] Ling H B, Jacobs D W. Using the inner-distance for classification of articulated shapes. In: Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Washington, DC, USA: IEEE, 2005. 719-726[6] Ling H B, Jacobs D W. Shape classification using the inner-distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2007, 29(2): 286-299[7] Biswas S, Aggarwal G, Chellappa R. Efficient indexing for articulation invariant shape matching and retrieval. In: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Minneapolis, MN: IEEE, 2007. 1-8[8] Grigorescu C, Petkov N. Distance sets for shape filters and shape recognition. IEEE Transactions on Image Processing, 2003, 12(10): 1274-1286[9] Tu Z W, Yuille A. Shape matching and recognition: using generative models and informative features. In: Proceedings of the 8th European Conference on Computer Vision (ECCV). Prague, Czech Republic: Springer, 2004. 195-209[10] Tu Z W, Zheng S F, Yuille A. Shape matching and registration by data-driven EM. Computer Vision and Image Understanding, 2008, 109(3): 290-304[11] Yang M Q, Kidiyo K, Joseph R. Shape matching and object recognition using chord contexts. In: Proceedings of the International Conference Visualisation. London, UK: IEEE, 2008. 63-69[12] Mori G, Belongie S, Malik J. Efficient shape matching using shape contexts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(11): 1832-1837[13] Thayananthan A, Stenger B, Torr P H S, Cipolla R. Shape context and chamfer matching in cluttered scenes. In: Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Washington, DC, USA: IEEE, 2003. 127-133[14] Zhang H, Malik J. Learning a discriminative classifier using shape context distances. In: Proceedings of the 2003 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Washington, DC, USA: IEEE, 2003. 242-247[15] Adamek T, O'Connor N E. A multiscale representation method for nonrigid shapes with a single closed contour. IEEE Transactions on Circuits and Systems for Video Technology, 2004, 14(5): 742-753[16] Mokhtarian F, Abbasi S, Kittler J. Efficient and robust retrieval by shape content through curvature scale space. In: Proceedings of the International Workshop on Image Databases and Multi-Media Search. Amsterdam, The Netherlands: IAPR, 1996. 35-42[17] Alajlan N, El Rube I, Kamel M S, Freeman G. Shape retrieval using triangle-area representation and dynamic space warping. Pattern Recognition, 2007, 40(7): 1911-1920[18] Alajlan N, Kamel M S, Freeman G H. Geometry-based image retrieval in binary image databases. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(6): 1003-1013[19] Mokhtarian F, Bober M. Curvature Scale Space Representation: Theory, Applications, and MPEG-7 Standardization. Dordrecht, The Netherlands: Kluwer Academic Publishers, 2003[20] Latecki L J, Lakaemper R. Shape similarity measure based on correspondence of visual parts. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2000, 22(10): 1185-1190[21] Attalla E, Siy P. Robust shape similarity retrieval based on contour segmentation polygonal multiresolution and elastic matching. Pattern Recognition, 2005, 38(12): 2229-2241[22] Felzenszwalb P F, Schwartz J D. Hierarchical matching of deformable shapes. In: Proceedings of the 2007 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Minneapolis, MN, USA: IEEE, 2007. 1-8[23] Gorelick L, Galun M, Sharon E, Basri R, Brandt A. Shape representation and classification using the Poisson equation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(12): 1991-2005[24] Peter A M, Rangarajan A. Maximum likelihood wavelet density estimation with applications to image and shape matching. IEEE Transactions on Image Processing, 2008, 17(4): 458-468[25] Peter A, Rangarajan A, Ho J. Shape L'ne rouge: sliding wavelets for indexing and retrieval. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK, USA: IEEE, 2008. 1-8[26] Bartolini I, Ciaccia P, Patella M. Warp: accurate retrieval of shapes using phase of Fourier descriptors and time warping distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(1): 142-147[27] Rodrigues J J, Aguiar P M Q, Xavier J M F. ANSIG --- an analytic signature for permutation-invariant two-dimensional shape representation. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK, USA: IEEE, 2008. 1-8[28] Veltkamp R C, Latecki L J. Properties and performance of shape similarity measures. In: Proceedings of the 10th International Conference on Data Science and Classification (IFCS). Ljubljana, Slovenia, 2006. 47-56[29] Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5): 550-571[30] Shokoufandeh A, Macrini D, Dickinson S, Siddiqi K, Zucker S W. Indexing hierarchical structures using graph spectra. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2005, 27(7): 1125-1140[31] Siddiqi K, Shokoufandeh A, Dickinson S J, Zucker S W. Shock graphs and shape matching. International Journal of Computer Vision, 1999, 35(1): 13-32[32] Macrini D, Siddiqi K, Dickinson S. From skeletons to bone graphs: medial abstraction for object recognition. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK, USA: IEEE, 2008. 1-8[33] Aslan C, Tari S. An axis-based representation for recognition. In: Proceedings of the IEEE International Conference on Computer Vision (ICCV). Beijing, China: IEEE, 2005. 1339-1346[34] Aslan C, Erdem A, Erdem E, Tari S. Disconnected skeleton: shape at its absolute scale. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(12): 2188- 2203[35] Chen Xiao-Fei, Wang Run-Sheng. Multi-scale trees representation for object's skeletons. Chinese Journals of Computers, 2004, 27(11): 1540-1545 (陈晓飞, 王润生. 目标骨架的多尺度树表示. 计算机学报, 2004, 27(11): 1540-1545)[36] Liu Wen-Yu, Liu Jun-Tao. Objects similarity measure based on skeleton tree descriptor matching. Journal Infrared Millimeter and Wave, 2005, 24(6): 432-436 (刘文予, 刘俊涛. 基于骨架树描述符匹配的物体相似性度量方法. 红外与毫米波学报, 2005, 24(6): 432-436)[37] Liu J T, Liu W Y, Wu C H. Objects similarity measurement based on skeleton tree descriptor matching. In: Proceeding of 10th IEEE International Conference on Computer-Aided Design and Computer Graphics. Beijing, China: IEEE, 2007. 91-101[38] Torsello A, Hancock E R. A skeletal measure of 2D shape similarity. Computer Vision and Image Understanding, 2004, 95(1): 1-29[39] Di Ruberto C. Recognition of shapes by attributed skeletal graphs. Pattern Recognition, 2004, 37(1): 21-31[40] Xie J, Heng P A, Shah M. Shape matching and modeling using skeletal context. Pattern Recognition, 2008, 41(5): 1756-1767[41] Bai X, Latecki L J. Path similarity skeleton graph matching. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2008, 30(7): 1282-1292[42] Bai X, Yang X W, Yu D G, Latecki L J. Skeleton-based shape classification using path similarity. International Journal of Pattern Recognition and Artificial Intelligence, 2008, 22(4): 733-746[43] Bai X, Latecki L J. Discrete skeleton evolution. In: Proceedings of the 6th International Conference on Energy Minimization Methods in Computer Vision and Pattern Recognition (EMMCVPR). Berlin, Heidelberg: Springer-Verlag, 2007. 362-374[44] Baseski E, Erdem A, Tari S. Dissimilarity between two skeletal trees in a context. Pattern Recognition, 2009, 42(3): 370 -385[45] Goh W B. Strategies for shape matching using skeletons. Computer Vision and Image Understanding, 2008, 110(3): 326-345[46] Cornea N D, Demirci M F, Silver D, Shokoufandeh A, Dickinson S J, Kantor P B. 3D object retrieval using many-to-many matching of curve skeletons. In: Proceedings of the 2005 International Conference on Shape Modeling and Applications (SMI). Washington, DC, USA: IEEE, 2005. 368-373[47] Sundar H, Silver D, Gagvani N, Dickinson S. Skeleton based shape matching and retrieval. In: Proceedings of the 2003 Shape Modeling International Conference. Washington, DC, USA: IEEE, 2003. 130-139[48] Chui H, Rangarajan A. A new algorithm for non-rigid point matching. In: Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Hilton Head Island, SC, USA: IEEE, 2000. 44-51[49] Zheng Y F, Doermann D S. Robust point matching for nonrigid shapes by preserving local neighborhood structures. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2006, 28(4): 643-6496[50] McNeill G, Vijayakumar S. 2D shape classification and retrieval. In: Proceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI). San Francisco, CA, USA: Morgan Kaufmann Publishers Inc., 2005. 1483-1488[51] McNeill G, Vijayakumar S. Part-based probabilistic point matching using equivalence constraints. In: Neural Information Processing Systems (NIPS) Informatics Publications, 2006. 969-976[52] Felzenszealb P F, Zabih R. Dynamic programming and graph algorithms in computer vision. IEEE Transactions Pattern Analysis and Machine Intelligence, 2011, 33(4): 721 -740[53] McNeill G, Vijayakumar S. Hierarchical procrustes matching for shape retrieval. In: Proceedings of the 2006 IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR). Washington, DC, USA: IEEE, 2006. 885-894[54] Sebastian T B, Klein P N, Kimia B B. On aligning curves. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2003, 25(1): 116-125[55] Yang X W, Bai X, Latecki L J, Tu Z W. Improving shape retrieval by learning graph transduction. European Conference on Computer Vision (ECCV), 2008, 32(5): 788-801[56] Bai X, Yang X W, Latecki L J, Liu W Y, Tu Z W. Learning context-sensitive shape similarity by graph transduction. IEEE Transactions Pattern Analysis and Machine Intelligence, 2010, 32(5): 861-874[57] Yang X W, Koknar-Tezel S, Latecki L J. Locally constrained diffusion process on locally densified distance spaces with applications to shape retrieval. In: Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami, FL: IEEE, 2009. 537-564[58] Kontschieder P, Donoser M, Bischof H. Beyond pairwise shape similarity analysis. In: Proceedings of the 9th Asian Conference on Computer Vision (ACCV). Berlin, Heidelberg: Springer-Verlag, 2009. 655-666[59] Chen L B, Feris R S, Turk, M. Efficient partial shape matching using Smith-Waterman algorithm. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK, USA: IEEE, 2008. 1-6[60] Daliri M R, Torre V. Classification of silhouettes using contour fragments. Computer Vision and Image Understanding, 2009, 113(9): 1017-1025[61] Bai X, Wang B, Wang X G, Liu W Y, Tu Z W. Co-transduction for shape retrieval. In: Proceedings of the 11th European Conference on Computer Vision (ECCV). Berlin, Heidelberg: Springer-Verlag, 2010. 328-341[62] Latecki L J, Lakaemper R, Eckhardt T. Shape descriptors for non-rigid shapes with a single closed contour. In: Proceedings of the 2000 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Hilton Head Island, SC, USA: IEEE, 2000. 424-429[63] Super B J. Learning chance probability functions for shape retrieval or classification. In: Proceedings of the 2004 IEEE Conference on Computer Vision and Pattern Recognition Workshop (CVPRW). Washington, DC, USA: IEEE, 2004. 93[64] Super B J. Retrieval from shape databases using chance probability functions and fixed correspondence. International Journal of Pattern Recognition and Artificial Intelligence, 2006, 20(8): 1117-1138[65] Ling H B, Okada K. EMD-L1: an efficient and robust algorithm for comparing histogram-based descriptors. In: Proceedings of the 9th European Conference on Computer Vision (ECCV). Graz, Austria: Springer-Verlag, 2006. 330-343[66] Ling H B, Yang X W, Latecki L J. Balancing deformability and discriminability for shape matching. In: Proceedings of the 11th European Conference on Computer Vision (ECCV). Berlin, Heidelberg: Springer-Verlag, 2010. 411-424[67] Lin L, Zeng K, Liu X B, Zhu S C. Layered graph matching by composite cluster sampling with collaborative and competitive interactions. In: Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami, FL, USA: IEEE, 2009. 1351-1358[68] Xu C J, Liu J Z, Tang X O. 2D shape matching by contour flexibility. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2009, 31(1): 180-186[69] Leibe B, Schiele B. Analyzing appearance and contour based methods for object categorization. In: Proceedings of the 2003 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Madison, Wisconsin, USA: IEEE, 2003. 409-415[70] Sebastian T B, Klein P N, Kimia B B. Recognition of shapes by editing their shock graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(5): 550-571[71] Demirci M F, Shokoufandeh A, Keselman Y, Bretzner L, Dickinson S. Object recognition as many-to-many feature matching. International Journal of Computer Vision, 2006, 69(2): 203-222[72] Sderkvist O. Computer vision classification of leaves from Swedish trees [Master dissertation], Linkoping University, Sweden, 2001[73] Latecki L J, Lakaemper R, Wolter D. Optimal partial shape similarity. Image and Vision Computing, 2005, 23(2): 227- 236[74] Lakaemper R, Sobel M. Correspondences between parts of shapes with particle filters. In: Proceedings of the 2008 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Anchorage, AK, USA: IEEE, 2008. 1-8[75] Tanase M, Veltkamp R C. Part-based shape retrieval with relevance feedback. In: Proceedings of the 2005 IEEE International Conference on Multimedia and Expo (ICME05). Amsterdam, Netherlands: ACM, 2005. 936-939[76] Saber E, Xu Y W, Murat Tekalp A. Partial shape recognition by sub-matrix matching for partial matching guided image labeling. Pattern Recognition, 2005, 38(10): 1560-1573[77] Bai X, Yang X W, Latecki L J. Detection and recognition of contour parts based on shape similarity. Pattern Recognition, 2008, 41(7): 2189-2199[78] Sun K, Super B J. Classification of contour shapes using class segment sets. In: Proceedings of the 2005 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Washington DC, USA: IEEE, 2005. 727-733[79] Bicego M, Murino V. Investigating hidden Markov models' capabilities in 2D shape classification. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004, 26(2): 281-286[80] Bai X, Yang X W, Yu D G, Latecki L J. Skeleton-based shape classification using path similarity. International Journal of Pattern Recognition and Artificial Intelligence, 2008, 22(4): 733-746[81] Chen L B, McAuley J J, Feris R S, Turk M. Shape classification through structured learning of matching measures. In: Proceedings of the 2009 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). Miami, FL, USA: IEEE, 2009. 365-372[82] Daliri M R, Torre V. Shape recognition based on Kernel-edit distance. Computer Vision and Image Understanding, 2010, 114(10): 1097-1103[83] Erdem A, Tari S. A similarity-based approach for shape classification using Aslan skeletons. Pattern Recognition Letters, 2010, 31(13): 2024-2032[84] Zhu X J. Semi-Supervised Learning with Graphs [Ph.D. dissertation], Carnegie Mellon University, USA, 2005

施引文献

资源附件(0)

访问统计