Probabilistic matching of planar regions (Q1037777)

Given two shapes \(A\) and \(B\), a set of transformations \(T\) and a distance measure \(d\), the matching problem is to find the transformation \(t\in T\) such that \(t(A)\) and \(B\) match optimally with respect to \(d\). The authors consider the problem of matching 2D shapes modeled by sets of polygons, using as sets of allowed transformations the set of translations or the set of planar rigid motions, and as similarity measure, the area of overlap. The probabilistic matching algorithm for translations works as follows: Given two shapes \(A\) and \(B\), in one random experiment a point \(a\in A\) and another point \(b\in B\) are selected. The vector \(b-a\in{\mathbb R}^2\) defines a translation \(t\). After repetition of this procedure, a point cloud in \({\mathbb R}^2\) is obtained. The center of the resulting point cloud is a translation that maps a large part of \(A\) onto \(B\). For rigid motions, two different approaches using analogous ideas are given. In the first, besides the translation vector defined as before, a rotation angle is randomly selected. In the second approach, the rigid motion is determined by selecting two points \(a_1,a_2\in A\) and one point \(b_1\in B\). Then another point \(b_2\in B\) is selected such that the distances between the points \(a_1\) and \(a_2\) and \(b_1\) and \(b_2\) are the same. The translation vector is \(b_1-a_1\) and the two vectors \(a_2-a_1\) and \(b_2-b_1\) define the rotation angle. It is shown that the algorithm approximates the maximal area of overlap. A time bound is given that does not depend significantly on the number of vertices, but on perimeter and area of the shapes and, in the case of rigid motions, also on the diameter.