Shape retrieval using triangle-area representation and dynamic space warping. (English) Zbl 1120.68046

Summary: In this paper, we present a shape retrieval method using triangle-area representation for nonrigid shapes with closed contours. The representation utilizes the areas of the triangles formed by the boundary points to measure the convexity/concavity of each point at different scales (or triangle side lengths). This representation is effective in capturing both local and global characteristics of a shape, invariant to translation, rotation, and scaling, and robust against noise and moderate amounts of occlusion. In the matching stage, a dynamic space warping algorithm is employed to search efficiently for the optimal (least cost) correspondence between the points of two shapes. Then, a distance is derived based on the optimal correspondence. The performance of our method is demonstrated using four standard tests on two well-known shape databases. The results show the superiority of our method over other recent methods in the literature.


68P20 Information storage and retrieval of data
68T10 Pattern recognition, speech recognition
68P15 Database theory
90C39 Dynamic programming
Full Text: DOI Link


[1] Lambert, S.; de Leau, E.; Vuurpijl, L., Using pen-based outlines for object-based annotation and image-based queries, (), 585-592
[2] J.M. Martinez, Mpeg-7 overview (version 9), Technical Report ISO/IEC JTC1/SC29/WG11N5525, ISO/IEC JTC1/SC29/WG11, International Organisation for Standardisation, Coding of Moving Pictures and Audio, March 2003.
[3] El Rube, I.; Alajlan, N.; Kamel, M.; Ahmed, M.; Freeman, G., Robust multiscale triangle-area representation for 2d shapes, (), 545-548
[4] El Rube, I.; Alajlan, N.; Kamel, M.; Ahmed, M.; Freeman, G., Efficient multiscale shape-based representation and retrieval, (), 415-422
[5] Roh, K.; Kweon, I., 2-d object recognition using invariant contour descriptor and projective refinement, Pattern recognition, 31, 4, 441-445, (1998)
[6] Ip, H.H.S.; Shen, D.G., An affine-invariant active contour model (ai-snake) for model-based segmentation, Image vision comput., 16, 2, 135-146, (1998)
[7] Shen, D.G.; Wong, W.; Ip, H.H.S., Affine invariant image retrieval by correspondence matching of shapes, Image vision comput., 17, 7, 489-499, (1999)
[8] Shen, D.G.; Ip, H.H.S.; Teoh, E.K., Affine invariant detection of perceptually parallel 3d planar curves, Pattern recognition, 33, 11, 1909-1918, (2000)
[9] I. El Rube, M. Ahmed, M. Kamel, Coarse-to-fine multiscale affine invariant shape matching and classification, in: 17th International Conference on Pattern Recognition (ICPR), vol. 2, Cambridge, UK, 2004, pp. 163-166.
[10] El Rube, I.; Ahmed, M.; Kamel, M., Affine invariant multiscale wavelet-based shape matching algorithm, (), 217-224
[11] The MPEG Home Page, \(\langle\)http://www.chiariglione.org/mpeg⟩.
[12] Loncaric, S., A survey of shape analysis techniques, Pattern recognition, 31, 8, 983-1001, (1998)
[13] Zhang, D.; Lu, G., Review of shape representation and description techniques, Pattern recognition, 37, 1, 1-19, (2004)
[14] Bartolini, I.; Ciaccia, P.; Patella, M., Warp: accurate retrieval of shapes using phase of Fourier descriptors and time warping distance, IEEE trans. pattern anal. Mach. intell., 27, 1, 142-147, (2005)
[15] Abbasi, S.; Mokhtarian, F.; Kittler, J., Curvature scale space image in shape similarity retrieval, Multimedia syst., 7, 6, 467-476, (1999)
[16] H. Ling, D. Jacobs, Using the inner distance for classification of articulated shapes, in: IEEE International Conference on Computer Vision and Pattern Recognition, vol. 2, San Diego, CA, USA, 20-26 June 2005, pp. 719-726.
[17] Belongie, S.; Malik, J.; Puzicha, J., Shape matching and object recognition using shape contexts, IEEE trans. pattern anal. Mach. intell., 24, 24, 509-522, (2002)
[18] Adamek, T.; O’Connor, N.E., A multiscale representation method for nonrigid shapes with a single closed contour, IEEE trans. circuits syst. video techol., 14, 5, 742-753, (2004)
[19] Petrakis, E.G.M.; Diplaros, A.; Milios, E., Matching and retrieval of distorted and occluded shapes using dynamic programming, IEEE trans. pattern anal. Mach. intell., 24, 11, 1501-1516, (2002)
[20] Sebastian, T.; Klein, P.; Kimia, B., On aligning curves, IEEE trans. pattern anal. Mach. intell., 25, 1, 116-124, (2003)
[21] Arica, N.; Vural, F., Bas: a perceptual shape descriptor based on the beam angle statistics, Pattern recognition lett., 24, 9-10, 1627-1639, (2003) · Zbl 1048.68072
[22] Latecki, L.J.; Lakamper, R., Shape similarity measure based on correspondence of visual parts, IEEE trans. pattern anal. Mach. intell., 22, 10, 1185-1190, (2000)
[23] Latecki, L.J.; Lakamper, R.; Wolter, D., Optimal partial shape similarity, Image vision comput., 23, 227-236, (2005)
[24] Itakura, F., Minimum prediction residual principle applied to speech recognition, IEEE trans. acoust. speech signal process. ASSP, 23, 52-72, (1975)
[25] Sakoe, H.; Chiba, S., Dynamic programming algorithm optimization for spoken word recognition, IEEE trans. acoust. speech signal process., 26, 43-49, (1978) · Zbl 0371.68035
[26] Deller, J.; Hansen, J.; Proakis, J., Discrete-time processing of speech signals, (1999), Wiley-IEEE Press New York
[27] Wang, K.; Gasser, T., Alignment of curves by dynamic time warping, Ann. statist., 25, 3, 1251-1276, (1997) · Zbl 0898.62051
[28] Jain, A.K.; Vailaya, A., Shape-based retrieval: a case study with trademark image databases, Pattern recognition, 31, 9, 1369-1390, (1998)
[29] L.J. Latecki, R. Lakamper, U. Eckhardt, Shape descriptors for non-rigid shapes with a single closed contour, In: IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2000, pp. 424-429.
[30] Sebastian, T.; Klein, P.; Kimia, B., Recognition of shapes by editing their shock graphs, IEEE trans. pattern anal. Mach. intell., 26, 5, 550-571, (2004)
[31] Mokhtarian, F.; Bober, M., Curvature scale space representation: theory, applications, and MPEG-7 standardization, (2003), Kluwer Academic Publishers · Zbl 1022.68120
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.