Qualitative Organization of Collections of Shapes via Quartet Analysis
Shi-Sheng Huang, Ariel Shamir, Chao-Hui Shen, Hao Zhang, Alla Sheffer, Shi-Min Hu, Daniel Cohen-Or


We present a method for organizing a heterogeneous collection of 3D shapes for overview and exploration. Instead of relying on quantitative distances, which may become unreliable between dissimilar shapes, we introduce a qualitative analysis which utilizes multiple distance measures but only in cases where the measures can be reliably compared. Our analysis is based on the notion of quartets, defined by two pairs objects. In each pair the shapes are close to each other, but far apart from the shapes of the other pair. Combining the information from many quartets computed across a shape collection using several distance measures, we create a hierarchical structure we call categorization tree of the shape collection. This tree satisfies the topological (qualitative) constraints imposed by the quartets creating an effective organization of the shapes. We present categorization trees computed on various collections of shapes and compare them to ground truth data from human categorization. We further introduce the concept of degree of separation chart for every shape in the collection and show the effectiveness of using it for interactive shapes exploration.

Results: Categorization Tree (Left: input dataset, Middle: ground truth, Right: ours)

Application: Interactive Exploration of Shape Collection


View in Youku (for domestic users)


We thank the anonymous reviewers for their constructive comments. This work was supported by the Israel Science Foundation (Number 324/11), NSERC Grant (Number 611370), the National Basic Research Project of China (Project Number 2011CB302202), the Natural Science Foundation of China (Project Number 61120106007), the National High Technology Research and Development Program of China (Project Number 2012AA011801) and Tsinghua University Initiative Scientific Research Program.


author = {Shi-Sheng Huang and Ariel Shamir and Chao-Hui Shen and Hao Zhang and Alla Sheffer and Shi-Min Hu and Daniel Cohen-Or},
title = {Qualitative Organization of Collections of Shapes via Quartet Analysis},
journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH 2013)},
volume = {32},
number = {4},
year = {2013},
pages = {accepted}

Source Code:

Building Trees the core source code to build the C-Tree.

Vis Trees the source code to visualize the C-Tree.

please email me shishenghuang0@gmail.com to get the ReadMe file to how to use the source code.

paper (large)[47M] paper (small)[9M] demo [48M] [MOV]
SuppMatt: TinyExample [15M]
SuppMatt: largerCases [34M]
slides [41M]