2D Alpha Decomposition

Yanyan Lu and Jyh-Ming Lien

Image above: shape features (red dots) detected by convolving the elephant with an increasingly larger disc.

Overview

Decomposing a shape into visually meaningful parts comes naturally to human vision, but recreating this fundamental operation in computers has been shown to be difficult. Similar challenges have puzzled researchers in shape reconstruction for decades. In this paper, we recognize the strong connections between shape reconstruction and shape decomposition at a fundamental level and propose a method called α-decomposition. The α-decomposition generates a space of decompositions parameterized by α, the diameter of a circle convolved with the input polygon. As we vary the value of α, some structural features appear and disappear quickly while others persist. Therefore, by analyzing the persistence of the features, we can determine better decompositions that are more robust to both geometrical and topological noises.

Publications

α-Decomposition of Polygons, Yanyan Lu and Jyh-Ming Lien and Mukulika Ghosh and Nancy Amato, Computers & Graphics, May 2012, Special edition of Shape Modeling International (SMI) Conference 2012
Web Site / Paper (pdf) / BibTeX

Software

Download the source code (Last update: Dec 2014)
Please report bugs to jmlien@cs.gmu.edu

Benchmark Data

The input polygons (MPEG7 dataset) used in the experiment: (MPEG7.zip)
Decomposition results of MPEG7 dataset in pdf format (mpeg7-pdf.zip)
Decomposition results of MPEG7 dataset in jpg format (mpeg7-jpg.zip)
- View all decomposition results of MPEG7 in JPG format

Examples

Persistence Analysis

α is 0.05	α is 0.2

Decomposition Results

View all decomposition results of MPEG7 in JPG format

Decomposition of a beetle model	Decomposition of a chickenmodel
Decomposition of a dog model	Decomposition of a fly model
Decomposition of a horse model	Decomposition of a octopus model