Affine invariants of generalized polygons and matching under affine transformations
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.
- Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations
- Computing conformal structures of surfaces
- Elastic image matching is NP-complete
- Fourier Descriptors for Plane Closed Curves
- scientific article; zbMATH DE number 5532284 (Why is no real title available?)
- scientific article; zbMATH DE number 3979443 (Why is no real title available?)
- scientific article; zbMATH DE number 1391661 (Why is no real title available?)
- Optimal Deterministic Algorithms for 2-d and 3-d Shallow Cuttings
- Optimal halfspace range reporting in three dimensions
- The Finite Fourier Series and Elementary Geometry
- Affine invariant triangulations
- scientific article; zbMATH DE number 3857851 (Why is no real title available?)
- Calculation of the invariant signature of a polygon
- scientific article; zbMATH DE number 3570473 (Why is no real title available?)
- scientific article; zbMATH DE number 2040608 (Why is no real title available?)
- scientific article; zbMATH DE number 917637 (Why is no real title available?)
- scientific article; zbMATH DE number 7758314 (Why is no real title available?)
- Affine invariants of an immersion of a topological space in the \(n\)-dimensional real vector space
- Locality sensitive hashing for efficient similar polygon retrieval
This page was built for publication: Affine invariants of generalized polygons and matching under affine transformations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q340532)
