Affine Shape Comparison using Different Distances

Khalid Aznag - Computer Science Department, Cadi Ayyad University, Marrakesh, Morocco
Toufik Datsi - Computer Science Department, Cadi Ayyad University, Marrakesh, Morocco
Ahmed El Oirrak - Computer Science Department, Cadi Ayyad University, Marrakesh, Morocco
Essaid El Bachari - Computer Science Department, Cadi Ayyad University, Marrakesh, Morocco


Citation Format:



DOI: http://dx.doi.org/10.30630/joiv.4.3.388

Abstract


In this work, we propose to compare affine shape using Hausdorff distance (HD), Dynamic Time Warping (DTW), Frechet (DF), and Earth Mover distance (EMD). Where there is only a change in resolution shape distance are computed between shape coordinates because the distance is not invariant under rotation or affinity. In case of transformation, distances are calculated not between shape coordinates but between Arc length or Affine Arc length. Arc length is invariant under rotation while Affine Arc length is invariant under affinity. The main advantage is invariance under change of resolution, rotation, and affinity.


Keywords


HD;EMD; DF; DTW; Invariant; Arc length; Affine Arc length.

Full Text:

PDF

References


G. Sparr, “A common framework for kinetic depth, reconstruction and motion for deformable objects,†In ECCV (2) , 1994, pp. 471-482.

G. Sparr, “Structure and motion from kinetic depth,†In: The Sophus Lie International Workshop on Computer Vision and Applied Geometry, 1995, Vol. 2.

O. Klein, and R. C. Veltkamp, “Approximation algorithms for computing the earth mover’s distance under transformations,†In International Symposium on Algorithms and Computation.

Springer, Berlin, Heidelberg, pp. 1019-1028, 2005.

H. Alt, and L.J. Guibas, “Discrete geometric shapes: Matching, interpolation, and approximation,†In Handbook of computational geometry, 2000, pp. 121-153.

S. Abbasi, F. Mokhtarian, and J. Kittler, “Curvature scale space image in shape similarity retrieval,†Multimedia systems, 1999, Vol. 7, No. 6, pp. 467-476.

F. Mokhtarian, and S. Abbasi, “Curvature scale space for shape similarity retrieval under affine transforms,†In International Conference on Computer Analysis of Images and Patterns. Springer, Berlin, Heidelberg, 1999, pp. 65-72.

P. Yuen, N. Khalili, and F. Mokhtarian, “Curvature Estimation on Smoothed 3-D Meshes ,†In BMVC, 1999, pp. 1-10.

T. Wylie, and B. Zhu, “Following a curve with the discrete Fréchet distance,†Theoretical Computer Science, 2014, Vol. 556, pp. 34-44.

M. Zhang, Y. Liu, H. Luan, and M. Sun, “Earth mover’s distance minimization for unsupervised bilingual lexicon induction,†In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, 2017, pp. 1934-1945.

Z. Zhang, R. Tavenard, A. Bailly, X. Tang, P. Tang, and T. Corpetti , “Dynamic time warping under limited warping path length, †Information Sciences, 2017, 393, 91-107.

X.D. Chen, W. Ma, G. Xu, and J. C. Paul, “Computing the Hausdorff distance between two B-spline curves,†Computer-Aided Design, 2010, Vol. 42, No. 12, pp.1197-1206.

L. Dantanarayana, G. Dissanayake and R. Ranasinge, “C-log: A chamfer distance-based algorithm for localisation in occupancy grid-maps,†CAAI transactions on intelligence technology, 2016, 1(3), 272-284.