Polygon recognition and symmetry detection

DOI10.1007/S10208-001-0027-5MaRDI QIDQ1405723zbMATH OpenOpenAlexFDO

Authors Mireille Boutin

Publication date 26 August 2003

Published in Foundations of Computational Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0011128

zbMATH Keywords

invariantspolygon recognitionsymmetry detection

Mathematics Subject Classification ID

Computational aspects related to convexity (52B55) Differential invariants (local theory), geometric objects (53A55) Machine vision and scene understanding (68T45)

Abstract: We introduce an approach based on moving frames for polygon recognition and symmetry detection. We present detailed algorithms for recognition of polygons modulo the special Euclidean, Euclidean, equi-affine, skewed-affine and similarity Lie groups, and explain the procedure for a generic Lie group. The time complexity of our algorithms is linear in the number of vertices and they are noise resistant. The signatures used allow the detection of partial as well as approximate equivalences. Our method is a particular case of a general method for curve recognition modulo Lie group action.

Review text

The paper contains an approach to recognition and symmetry detection of polygons or parts of them in various geometries. Let \(M\) be a manifold on which a Lie group \(G\) is acting. Then to any polygon \((p_1, \dots, p_k)\) on \(M\) an ordered set of invariants \(I_1, \dots, I_n\), called a signature, can be attached which uniquely determines the polygon up to transformations of \(G\). This means that two polygons \((p_1, \dots, p_k)\) and \((q_1, \dots, q_k)\) have the same signature if and only if there is a transformation \(g \in G\) with \(g(p_i) = q_i\). The author shows how to construct such signatures for a general Lie group \(G\) and discusses in detail examples for the cases where \(G\) is the special Euclidean, the Euclidean, the similarity, the affine or the equiaffine group acting in the plane or the group \(SL(2)\) acting in the Poincaré halfplane. The signatures also facilitate the detection of symmetries or partial equivalences of two polygons. The time complexity of the algorithms is linear in the number \(k\) of vertices and moreover these algorithms are noise resistant and hence can also be used to decide whether two polygons are 'roughly' equivalent.

Recommendations

• scientific article; zbMATH DE number 176577
• Polygon Graph Recognition
• Detection of rotational and involutional symmetries and congruity of polyhedra
• SHAPE PARTITIONING BASED ON SYMMETRIES DETECTION

Cited in

(12)

• Recognizing polygons, or how to spy
• Optimal algorithms for symmetry detection in two and three dimensions
• Moving frames
• Detection of rotational and involutional symmetries and congruity of polyhedra
• I. GM-sets applied to Lie theory
• Recognition of triangles by covariogram
• The regular polygon detector
• scientific article; zbMATH DE number 6378923 (Why is no real title available?)
• Affine invariants of generalized polygons and matching under affine transformations
• scientific article; zbMATH DE number 176577 (Why is no real title available?)
• scientific article; zbMATH DE number 1759539 (Why is no real title available?)
• Invariants of objects and their images under surjective maps

This page was built for publication: Polygon recognition and symmetry detection

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1405723)