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

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.