Abstract Representation of Object and Structural Symmetries Detection

Vincent Dugat; Pierre Gambarotto; Yannick Larvor

doi:10.3217/jucs-009-09-1008

JUCS - Journal of Universal Computer Science 9(9): 1008-1029, doi: 10.3217/jucs-009-09-1008

Abstract Representation of Object and Structural Symmetries Detection

Vincent Dugat^‡, Pierre Gambarotto^‡, Yannick Larvor^‡

‡ IRIT-UPS, Toulouse, France

Corresponding author: Vincent Dugat ( dugat@cict.fr )

This article is freely available under the J.UCS Open Content License.

Citation: Dugat V, Gambarotto P, Larvor Y (2003) Abstract Representation of Object and Structural Symmetries Detection. JUCS - Journal of Universal Computer Science 9(9): 1008-1029. https://doi.org/10.3217/jucs-009-09-1008

Abstract

This paper describes a method for constructing an abstract representation of a shape from a classical polyhedral 3D representation of an object. This framework is suitable for qualitative reasoning. As an application we use this abstract representation to compute the structural symmetries of a 3D polyhedron. The starting point of the computation is a classical polyhedral 3D representation of the object. From the Medial Axis Transform (MAT) of this object we propose a more abstract representation based on a set of spheres extracted from the MAT and structured as one or several graphs. This framework can be used for several purposes. Here we focus on the problem of finding structural symmetries of the object. We use the automorphisms group of the computed graphs. Then we propose a method to compute the automorphisms that have a geometrical sense among the set of all automorphisms. We compare the brute force algorithm with a branch and bound strategy based on the orbits partition of the vertices.

Keywords

qualitative reasoning, spatial reasoning, shape recognition, spatial representation, medial axis transform