Project

Back to overview

The Scale Axis Transformation

English title The Scale Axis Transformation
Applicant Gross Markus
Number 124740
Funding scheme Project funding (Div. I-III)
Research institution Laboratoire d'informatique graphique et géométrique EPFL - IC - ISIM - LGG
Institution of higher education ETH Zurich - ETHZ
Main discipline Information Technology
Start/End 01.04.2009 - 31.10.2010
Approved amount 85'225.00
Show all

Keywords (5)

computational geometry; medial axis; shape analysis; skeletal representations; segmentation

Lay Summary (English)

Lead
Lay summary
Digital representations of complex 2D and 3D geometric models have recently become ubiquitous due to advances in acquisition technology and increased computing capabilities. Analyzing and processing such data sets is of paramount importance in many application fields, such as mechanical engineering, geology, physics, architecture, life sciences, or medicine. Recently, we have discovered a new type of skeletal structure that we coined the scale axis. The scale axis is a generalization of the medial axis that provides a systematic treatment of spatial adaptivity. For a given shape S, the scale axis transform computes a family of skeletal structures parameterized by a scale parameter s. For s = 1 the scale axis is identical to the medial axis. With increasing s, the scale axis gradually removes less important features of S leading to a successive simplification of the skeletal structure. The key defining principle of the scale axis is spatial adaptivity. The definition of feature importance is based on a size comparison between a feature and the surrounding ones, effectively defining a simplification scheme where features are deleted first, if they appear small relative to their neighborhood. The main objective of this project is to develop a comprehensive theory for the scale axis transform. The definition of the scale axis relies on a simple construction, growing and shrinking of balls, which makes it amenable to a rigorous theoretical analysis. This analysis will provide new insights on the nature both of continuous as well as discretely sampled geometry. At the same time, the conceptual simplicity allows the design and implementation of efficient algorithms with provable guarantees to compute the scale axis for 2D and 3D shapes, which is a second focus of the proposed project. These algorithms will be directly disseminated to the research community through our publicly available software tool Mesecina. Given a sound theoretical framework and effective algorithms, the scale axis has the potential to become a fundamental and essential building block for applications in shape analysis and semantic modeling. With its inherent feature classification based on geometric importance, the scale axis can provide a hierarchical shape representation in the form of a one-parameter filtration, where the parameter quantifies the level of details. An important characteristic of the scale axis transform is that this parameter is intrinsic, hence no prior evaluation of a relevant sub-range in the parameter space is needed. We envisage, among others, applications in shape simplification, reverse engineering, segmentation, and object retrieval.
Direct link to Lay Summary Last update: 21.02.2013

Responsible applicant and co-applicants

Employees

Name Institute

Associated projects

Number Title Start Funding scheme
111890 Stabile Definition einer medialen Achse für bewegte Objekte 01.11.2006 Project funding (Div. I-III)

Abstract

Digital representations of complex 2D and 3D geometric models have recently become ubiquitous due to advances in acquisition technology and increased computing capabilities. Analyzing and processing such data sets is of paramount importance in many application fields, such as mechanical engineering, geology, physics, architecture, life sciences, or medicine. This proposal concerns the continuation of our project "Stable Medial Axis in Motion", funded by the 2-year SNF grant 200021-111890, that started in November 2006. During the course of the last 20 months we studied stability aspects of the medial axis transform, one of the fundamental concepts in shape analysis and digital geometry processing. In particular, we investigated the connection between the lambda-medial axis and conformal alpha-shapes to address one of the main limitations of the medial axis, its inherent geometric instability. In the course of this research, we discovered a new type of skeletal structure that we coined the "scale axis". The scale axis is a generalization of the medial axis that provides a systematic treatment of spatial adaptivity. For a given shape S, the scale axis transform computes a family of skeletal structures parameterized by a scale parameter s. For s=1 the scale axis is identical to the medial axis. With increasing s, the scale axis gradually removes less important features of S leading to a successive simplification of the skeletal structure. The key defining principle of the scale axis is spatial adaptivity. The definition of feature importance is based on a size comparison between a feature and the surrounding ones, effectively defining a simplification scheme where features are deleted first, if they appear small relative to their neighborhood.The main objective of this project is to develop a comprehensive theory for the scale axis transform. The definition of the scale axis relies on a simple construction, growing and shrinking of balls, which makes it amenable to a rigorous theoretical analysis. This analysis will provide new insights on the nature both of continuous as well as discretely sampled geometry.At the same time, the conceptual simplicity allows the design and implementation of efficient algorithms with provable guarantees to compute the scale axis for 2D and 3D shapes, which is a second focus of the proposed project. These algorithms will be directly disseminated to the research community through our publicly available software tool Mesecina. Given a sound theoretical framework and effective algorithms, the scale axis has the potential to become a fundamental and essential building block for applications in shape analysis and semantic modeling. With its inherent feature classification based on geometric importance, the scale axis can provide a hierarchical shape representation in the form of a one-parameter filtration, where the parameter quantifies the level of details. An important characteristic of the scale axis transform is that this parameter is intrinsic, hence no prior evaluation of a relevant sub-range in the parameter space is needed. On the contrary, the features of the shape are ordered by the computation of the scale axis transform, and this ordering allows us to extract, a posteriori, the relevant values of the parameter. These properties make the scale axis transform a perfect fit in an automated tool chain, which is of crucial importance in application domains that have to deal with increasingly complex digital geometric data sets. We envisage, among others, applications in shape simplification, geometric abstraction, reverse engineering, segmentation, and object retrieval.
-