EECS technical reports

Oskicat catalog record
Conditions of Use

Archive Home Page

2D Object Abstraction: The Automatic Generation of Hierarchical Geometric Representations

Simmons, Maryann
Technical Report Identifier: CSD-97-972
September 17, 1997

Abstract: This thesis presents an exploratory framework for automatically generating hierarchical object representations specialized for geometric tasks. The approach consists of two subprocesses: the first extracts geometric information from the input object, and the second generates a specialized representation based on this information.

The first subprocess produces a multi-resolution representation that encapsulates the salient geometric features of an object, as well as its topological decomposition into parts. The representation is generated in two steps. First, a multi-resolution Geometry Representation (G-Rep) is built. Its main components are a Cell-Based Spatial Representation (CSR) that provides spatial filtering at the desired feature resolution, and an Axial Shape Graph (ASG) that captures local shape information as well as global information about the overall geometric structure of the object. The CSR and ASG components are calculated at multiple resolutions and linked together to form the G-Rep hierarchy. In the second step, the Axial Shape Graph is decomposed into a tree representing the overall shape structure of the object as a hierarchy of subcomponents. Using the Axial Shape Graph, the task of shape decomposition is reduced to a graph partitioning problem whose solution results in a well-balanced part hierarchy.

The second subprocess constructs a hierarchy of task-specific representations utilizing the geometric information provided by the G-Rep. The entire representation generation framework is driven by metrics that quantify the desirable characteristics of representations for the particular task. We show that this structure can be utilized to generate representations specialized for the task of Collision Detection in 2D environments.