On the Calculation of Similarity Measures for Figures by Nonsmooth Global Optimization

Vladimir Norkin () and Georg Pflug ()
Additional contact information
Vladimir Norkin: V.M. Glushkov Institute of Cybernetics of the National Academy of Sciences of Ukraine & National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute”
Georg Pflug: University of Vienna

A chapter in Theory, Algorithms, and Experiments in Applied Optimization, 2025, pp 261-294 from Springer

Abstract: Abstract This paper addresses the challenge of calculating figure-to-figure and figure-to-class similarity measures for rigid and bendable figures. Figures are represented as sets of line segments and points in a Euclidean space, and their similarity is assessed based on the minimal Hausdorff distance or deviation between their isometric transforms. For rigid figures, the problem is formulated as a global optimization of a nonsmooth Lipschitz function. A specific branch-and-bound algorithm is proposed for solving this optimization problem. For bendable figures, the Gromov-Hausdorff distance is used as a similarity measure, and its calculation is reduced to a nonsmooth global optimization problem with a number of nonlinear equality constraints. Additional complexity of the above problems is that for figures containing line segments even a calculation of Hausdorff distance requires solution of a number of one-dimensional Lipschitz global optimization problems. The figure-to-class similarity measure is defined as the average value at risk of the random variable representing individual figure-to-figure similarities. Complexity reduction techniques are introduced to efficiently compute this measure. The application of these similarity measures to pattern recognition is also explored.

Keywords: Figures similarity; Transformation-based similarity; Gromov-Hausdorff distance; Lipschitz global optimization; Branch-and-bound method (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-031-91357-0_13

Ordering information: This item can be ordered from
http://www.springer.com/9783031913570

DOI: 10.1007/978-3-031-91357-0_13

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().