Beyond Geometry and Topology - Mathematical Tools for Shape Analysis and Description - page 93

separated pairs made of enough close objects. Four shape descriptors are used along with their
distances, namely the LightField descriptor [ 44 ], the Spherical Harmonics descriptor [ 84 ], the
Bag-of-Words based on the Heat Kernel Signature [ 37 ], the Shape Diameter Function [ 179 ]. A
set of reliable quartets is created for each descriptor separately, then they are combined to build
the C-tree.
Figure 12.3: A collection of 3D objects is organized in a categorization tree (middle) and a Degree
of Separation chart (right) via quartet-based analysis (left) [ 106 ].
e C-tree is built from the quartets using a two-stage algorithm: first embedding, then
partitioning. Shapes are represented as points in the unit sphere S n . An energy function is defined
as the difference between two terms: the sum over quartets of the angles between close objects,
and the sum over quartets of the angles between distant objects. Minimizing this energy function
yields optimized points which respect the topological relations imposed by the quartets. Finally,
also the partitioning is guided by information from the quartets. Naming bad edges those be-
tween close objects and good edges those between distant objects, the partition is sought which
maximizes the number of cuts through good edges while minimizing the number of cuts through
bad ones. is is done using the Quartets MaxCut (QMC) algorithm [ 186 ]. e partition is op-
erated recursively until no more partitions are obtained. e resulting hierarchy of sub-partitions
defines the C-tree.
Figure 12.4: Four objects and six associated edges (a). Candidate quartets (b and c) and quadruplets
to be discarded (d and e) [ 106 ].