Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences

COLLEGE OF ENGINEERING

UC Berkeley

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

Maryann Simmons

EECS Department
University of California, Berkeley
Technical Report No. UCB/CSD-97-972
September 1997

http://www.eecs.berkeley.edu/Pubs/TechRpts/1997/CSD-97-972.pdf

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.


BibTeX citation:

@techreport{Simmons:CSD-97-972,
    Author = {Simmons, Maryann},
    Title = {2D Object Abstraction: The Automatic Generation of Hierarchical Geometric Representations},
    Institution = {EECS Department, University of California, Berkeley},
    Year = {1997},
    Month = {Sep},
    URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1997/5678.html},
    Number = {UCB/CSD-97-972},
    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. <p>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. <p>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.}
}

EndNote citation:

%0 Report
%A Simmons, Maryann
%T 2D Object Abstraction: The Automatic Generation of Hierarchical Geometric Representations
%I EECS Department, University of California, Berkeley
%D 1997
%@ UCB/CSD-97-972
%U http://www.eecs.berkeley.edu/Pubs/TechRpts/1997/5678.html
%F Simmons:CSD-97-972