OPTIMIZATION OF THE ALGORITHM FOR DETERMINING THE HAUSDORFF DISTANCE FOR CONVEX POLYGONS

Dmitry I. Danilov     (Ural Federal University, Ekaterinburg, Russian Federation)
Alexey S. Lakhtin     (Ural Federal University, Ekaterinburg, Russian Federation)

Abstract


The paper provides a brief historical analysis of problems that use the Hausdorff distance; provides an analysis of the existing Hausdorff distance optimization elements for convex polygons; and demonstrates an optimization approach. The existing algorithm served as the basis to propose low-level optimization with super-operative memory, ensuring the finding a precise solution by a full search of the corresponding pairs of vertices and sides of polygons with exclusion of certain pairs of vertices and sides of polygons. This approach allows a significant acceleration of the process of solving the set problem.


Keywords


Hausdorff distance, Polygon, Optimization, Optimal control theory, Differential games, Theory of image recognition

Full Text:

PDF

References


Arutyunov A.V. Lectures on Convex and Polysemantic Analysis. Moscow: Fizmatlit, 2014. 184 p.

Bronshtein E.M. Approximation of convex sets by polytopes. Sovremennaya matematika. Fundamental'nye napravleniya [Contemporary Mathematics. Fundamental Directions], 2007. vol. 22. P. 5–37. (in Russian)

Chernousko F. L. Otsenivanie fazovogo sostoyaniya dinamicheskih sistem [Estimation of the Phase State of Dynamic Systems]. Moscow: Nauka, 1988. (in Russian)

Gruber P.M. Approximation by convex polytopes. Polytopes: Abstract, Convex and Computational . NATO ASI Series (Series C: Mathematical and Physical Sciences), 1994. Vol. 440. P. 173–203. DOI: 10.1007/978-94-011-0924-6_8

Gruber P.M. Comparision of best and random approximation of convex bodies by polytopes. Rend. Circ. Mat. Palermo, II. Ser., Suppl., 1997. Vol. 50. P. 189–216.

Huttenlocher D.P., Klanderman G.A., Rucklidge W.J. Comparing images using the Hausdorff distance. IEEE Transactions on Pattern Analysis and Machine Intelligence, 1993. Vol. 15. no. 9. P. 850–863. DOI: 10.1109/34.232073

Huttenlocher D.P., Rucklidge W.J. A multi-resolution technique for comparing images using the Hausdorff distance. 1992. [Technical Report 1321, Cornell University]. http://hdl.handle.net/1813/6165

Jesorsky O., Kirchberg K.J., Frischholz R.W. Robust face detection using the Hausdorff distance. Audio- and Video-Based Biometric Person Authentication. AVBPA 2001, Lecture Notes in Computer Science, 2001. Vol. 2091. P. 90–95. DOI: 10.1007/3-540-45344-X_14

Kirchberg K.J., Jesorsky O., Frischholz R.W. Genetic model optimization for Hausdorff distance-based face localization. Biometric Authentication. BioAW 2002. Lecture Notes in Computer Science, 2002. Vol. 2359. P. 103–111. DOI: 10.1007/3-540-47917-1_11

Kurzhansky A.B., Filippova T.F. On the description of sets of surviving trajectories of differential inclusion. Doklady akademii nauk SSSR [Report of AS of the USSR], 1986. Vol. 289. no. 1. P. 38–41.

Lakhtin A.S. Konstruktsii negladkogo i mnogoznachnogo analiza v zadachah dinamicheskoy optimizatsii i teorii uravneniy Gamil'tona-Yakobi. Diss. dokt. fiz.-mat.nauk [Constructions of Non-smooth and Polysemantic Analyses in Problems of Dynamic Optimization and the Theory of Hamilton-Jacobi Equations. Dr. phys. and math. sci. diss.], Yekaterinburg, 2001. (in Russia)

Lakhtin A.S., Ushakov V.N. The problem of optimizing the Hausdorff distance between two convex polyhedra. Sovremennaya matematika i ee prilozheniya [Modern Mathematics and its Applications], 2003. Vol. 9. P. 60–67. (in Russian)

Lebedev P.D., Uspensky A.A. Procedures for calculating the non-convexity of a planar set. Comput. Math. Math. Phys., 2009. Vol. 49, no. 3. P. 418–427. DOI: 10.1134/S096554250903004X

Petrov N.N. Vvedenie v vypuklyy analiz: uchebnoe posobie. [Introduction to Convex Analysis: Study Guide], 2009. (in Russian)

Romanov A.V., Kataeva L.Yu. On the use of superconvertive memory for the solution of a system of algebraic equations by the method of alternating directions. VII Mezhdunarodnaya nauchno-tekhnicheskaya molodezhnaya konferentsiya "Budushchee tekhnicheskoy nauki", Nizhniy Novgorod, 16.05.2008: tezisy doklada [The Future of the Engineering Science. VII International Scientific and Technical Youth Conference: book of Abstracts], 2008. P. 33–34. (in Russian)

Rosenblum M., Yacoob Y., Davis L. Human expression recognition from motion using a radial basis function network architecture. IEEE Transactions on Neural Networks, 1996. Vol. 7, no. 5. P. 1121–1138. DOI: 10.1109/72.536309

Schlesinger M.I., Vodolazskii Y.V. and Yakovenko V.M. Recognizing the similarity of polygons in a strengthened Hausdorff metric. Cybern. Syst. Anal., 2014. Vol. 50, no. 3. P. 476–486. DOI: 10.1007/s10559-014-9636-2

Ushakov V.N., Lebedev P.D. Iterative methods for minimization of the Hausdorff distance between movable polygons. Vestn. Udmurtsk. Univ. Mat. Mekh. Komp. Nauki, 2017. Vol. 27, no. 1. P. 86–97. (in Russian) DOI: 10.20537/vm170108

Ushakov V.N., Lakhtin A.S., Lebedev P.D. Optimization of the Hausdorff distance between sets in Euclidean space. Proc. Steklov Inst. Math., 2015. Vol. 291, Suppl. 1. P. 222–238. DOI: 10.1134/S0081543815090151

Yaksubaev K.D., Shuklina Yu.A. Metric space of unlimited convex sets and unlimited polyhedron. Mezhdunarodnyy nauchno-issledovatel'skiy zhurnal [International Research Journal], 2017. No. 5 (59), part 3. P. 162–164. DOI: 10.23670/IRJ.2017.59.103

Zhang J., Liu Y. Medical image registration based on wavelet transform using Hausdorff distance. Transactions on Edutainment VII, Lecture Notes in Computer Science, 2012. Vol. 7145. P. 248–254. DOI: 10.1007/978-3-642-29050-3_24




DOI: http://dx.doi.org/10.15826/umj.2018.1.002

Article Metrics

Metrics Loading ...

Refbacks

  • There are currently no refbacks.