Abstract

A graph theoretic approach is proposed for ob ject shape representation in a hierarchical compositional architecture called Com- positional Hierarchy of Parts (CHOP). In the proposed approach, vocab- ulary learning is performed using a hybrid generative-descriptive model. First, statistical relationships between parts are learned using a Mini- mum Conditional Entropy Clustering algorithm. Then, selection of de- scriptive parts is defined as a frequent subgraph discovery problem, and solved using a Minimum Description Length (MDL) principle. Finally, part compositions are constructed using learned statistical relationships between parts and their description lengths. Shape representation and computational complexity properties of the proposed approach and algo- rithms are examined using six benchmark two-dimensional shape image datasets. Experiments show that CHOP can employ part shareability and indexing mechanisms for fast inference of part compositions using learned shape vocabularies. Additionally, CHOP provides better shape retrieval performance than the state-of-the-art shape retrieval methods.