Costcomplexity pruning of random forests ISMM 2017Given a hierarchy of partitions \(H = \{ \pi_i \}_{ 0 \leq i n}\) the optimal cut problem aims at calculating : \(\begin{aligned} & \underset{\pi \in \Pi(E,H)}{\text{minimize}} & & \sum_{S \in \pi} \omega(S)\\ \end{aligned}\) The problem can be solved greedily using the dynamic program whose substructure is given by \(\pi^{\ast}(S) = \begin{cases} \{S\}, & \text{if}\ \omega({S})\leq \sum(\omega(\pi^\ast(a))), a \in \pi(S)\\ \bigsqcup_{a \in \pi(S)} \pi^\ast(a), & \text{otherwise} \end{cases}\) \(h\)increasingness provides the condition on the energy defined on the partial partitions \(\omega(\pi(S))\) to so as to obtain a global optimum : \(\omega(\pi_1(S)) \leq \omega(\pi_2(S)) \implies \omega(\pi_1(S) \sqcup \pi_0) \leq \omega(\pi_2(S) \sqcup \pi_0)\) There can be many solutions to the dynamic program. We impose uniqueness by imposing the following condition on \(\omega\) : \(\forall \ \pi(S)\in\Pi(S), \ \ \omega(\{S\})\neq\omega(\pi(S))\}\) Given the uniqueness condition the energeticordering between two partitions \(\pi_1, \pi_2\) is : \(\pi \preceq _{\omega }\pi^\prime \ \Leftrightarrow \ \forall S\in \pi \vee \pi^\prime \ \text{we have} \ \omega (\pi \sqcap \{S\})\leq \ \omega(\pi^\prime \sqcap \{S\})\) Here \(\pi \preceq _{\omega } \pi^{\prime}\) In fact during the optimization procedure one never evaluates energy of a partition, but only of the partial partitions. This is the cruicial part of the problem which renders the dynamic program to be forumlated as a lattice structure. The energetic lattice ( \(\preceq _{\omega }, \vee_{\omega}\) ) derives from the energetic order. The hierarchy of partitions can be created using two different types of operations. Given a elementary leaves partition one can create the hierarchy bottomup by fusing classes of the partitions together creating coarser parent partitions (child>parent fils > pere). Or given a coarse elementary partition one can create the hierarchy topdown by dividing classes of the partitions into finer children classes (parent>child pere > fils). While the braid of partitions consists of a third type of refinement operation, including the fusion and division operations. This is termed as hierarchical reorganization, while mathematically it corresponds to local partitioning that keeps the pairwise supremum partitions a hierarchy of partitions. More particularly, this corresponds to a fusiondivision (or divisionfusion) operation on the same set of classes in a partition, that produces a new local partitioning of the space. Braids are the largest family over which the dynamic programming substructure is preserved to yield a global optimum. \[ B = \{\pi_i\}_{i=1}^n  \pi_i \vee \pi_j \in \Pi(E,H) \] We can see from the braid structure that it is in accordance with the energetic ordering and also generalizes hierarchical partitioning of the space while preserving the dynamic program's substructure.</p> Examples of partition families that form braidsThe Ultrametric contour map(UCM) from the berkeley group is an example of a hierarchy. While the Stochastic watershed by Angulo et al. is an example of a braid. There is a total ordering between the partitions in a hierarchy, while there is a partial ordering for partitions belonging to a braid. The supremum partitions of a braid though turn out to be hierarchical. This provides a generalization of the hierarchical structure for the purpose of dynamic programming and search of better solution spaces. Stochastic watershed Braids:Composition of Attribute watershed hierarchies:Dynamic programming substructre on BraidsTo ensure that one reaches the minimum using previously calculated results over finer partial partitions, we use the hierarchical increasingness property. This ensures the monotonic property of the energy during the bottomup/topdown scan by the dynamic program. \(h\)increasingness is over partial partitions from a hierarchy and a braid is demonstrated. We see that the braid provides a larger family of partitions over which the dynamic program works. This requires a partial ordering in case of braids.
Human annotated & algorithm segmentations match in three different ways (shown below) Optimal Cuts from hierarchies of partitions
Optimal Cut (Luminance) VS Optimal Cut (Chrominance)
\(\omega_{\text{Lum}}(S) = \sum_{x \in S} \l(x)\mu(S)\^2 + \lambda(24 + \partial S)\)
\(\omega_{\text{Chrom}}(S) = \sum_{x \in S, i} \c_i(x)\bar{c}_i(S)\^2 + \lambda(24 + \partial S)\)
Mean size of siblings \(\mu_A = \frac{\sum_{S^\prime \in \text{siblings}(S)} S}{\text{siblings}(S)}\) Texture energy \(\omega_{\text{texture}}(S) = \omega_{\text{Chrom}}(S) + \frac{\nu}{\sum_{S^\prime \in \text{siblings(S)}} \mu_AS^\prime^2}\) Intial Image  VS  For weak uniformity  VS  For strong uniformity:Related Publications and slides
Tutorial on optimization on hierarchies at ICIP 2014
Reading List
Ground truth energies and Class openingDuring the evaluation of ground truth segmentation one problem is the evauation of a numerical measure that determines if the given image segmentation is close to the expert/human drawn ground truth. Given a hierarchy of segmentations one faces the problem of chosing which partition amongst all cuts is closest to a given ground truth. We evaluate a localized haussdorf distance locally for every superpixel segment belonging to the input hierarchy of segmentations corresponding to the input image, using the ground truth partition contours and their distance functions. First energy : Maximum distance function value of the contours of the segment over the contour of the ground truth passing within the segment, Second energy : Maximum distance function value of the ground truth contour over the segment contours. These local energies termed as ground truth energies. These functions are hincreasing. Once, these energies calculated for every segment in the hierarchy, we can extract the partition whose with least value of composition of ground truth energies. The optimal cut extracted here thus corresponds to the partition from the hierarchy of partitions closest locally w.r.t each class, to the input ground truth partition.
Related Publications
References
