Affine invariants of generalized polygons and matching under affine transformations (Q340532)

The paper deals with the problem of matching generalized polygons (ordered set of vertices) with the same number of vertices under affine transformations. The proposed approach is based on invariants. The authors firstly associate an ordered set of complex number with each polygon and then construct a collection of \(\lfloor (n-1)/2 \rfloor\) complex scalar functions, where \(n\) is the number of vertices. The functions are defined as quotients of the so-called Fourier descriptors. They prove that each of the functions assigns the same value to any two similar polygons under the assumption that the vertices of the two polygons have been presented in the same cyclic order. Moreover, they show that the \(n\)th power of each of the functions is invariant under similarity transformations and under arbitrary relabelling of the polygon vertices. Next, the authors prove that if two polygons are affine related, then the pseudo-hyperbolic distance between their associated values is a constant that depends only on the affine transformations, but is independent of the polygons. Finally, using the obtained results, the authors introduce four algorithms for solving several problems related to indexed polygon matching. In each algorithms we have a collection \(\{ Z_1, Z_2, \dots, Z_m \}\) of \(n\)-sided polygons and an \(n\)-sided query polygon \(W\). In the first presented algorithm the authors show how to find exact matches of \(W\), including cyclic relabelling of \(W\), under an unknown similarity of a known affine transformation, in time independent of \(m\). The second algorithm is related to the problem of finding all the approximate matches of \(W\) under unknown noisy similarities with cyclic relabelling. The proposed algorithm runs in \(O(R n^2 \log m)\) time, where \(R\) is the number of points in a circular range query of a certain radius, and without the cyclic relabelling in \(O(R n \log m)\) time. In the third algorithm the authors present a method of finding exact matches under unknown affine transformation that runs in \(O(m n^2)\) time. The last presented algorithms finds all the approximate matches under unknown affine transformations in noisy conditions and runs in \(O(m(R + n^2))\) time, where \(R\) is the number of matches of certain indicator functions derived from the invariants.