Project topics and materials
Get Complete Project Material File(s) Now! »
Reweighing and energy optimization on hierarchies
We have seen in section 2.1.3 that some merging criteria (flooding by area, volume, dynamics. . . ) could affect the quality of the resulting hierarchy of watershed. This can be seen as a way of reweighing the hierarchy.
In section 2.1.1, we have introduced a hierarchical structure based on the notion of quasi-flat zones, namely the α-tree. In [118], the authors proposed the constrainedconnectivity, as well as a way to modify the original hierarchy indexed by α to a new hierarchy indexed by the bounded variation ω of the component to limit the linking effect. More formally, the bounded variation BV is defined as: BV(G) = max.x∈G u(x) − min x∈G u(x) The ω-connected components do not form a partition of the image as they may overlap. Their idea is thus to limit themselves to α-connected components but constrained with the bounded variation ω. In other words, they are the largest α-connected components of bounded variation less than ω: ω-CC = Maximal elements of ⊆ {G, G ∈ α-CC | BV(G) ≤ ω} From now, any horizontal cut on the new ω-indexed hierarchy corresponds to a nonhorizontal cut on the old α-indexed hierarchy. This is illustrated on fig. 18. The α-tree given as an example in fig. 14 has been reweighed with the bounded variation. In other words, we compute the ω value of each region and reindex the hierarchy with these values. As one can see, it changes the topology of the tree and the horizontal green cut in the new hierarchy is related to a the non-horizontal red one in the original hierarchy.
on the imposition of a total ordering
Among hierarchical representations of images, component trees rely on a data (pixel values) ordering that needs to be total. When dealing with multivariate data, authors generally have two approaches. They either define a new total ordering relation on their data, or adapt their structures to deal with the natural partial order. Many authors have attempted to define orders on colors. There actually exist more than seventy ways of ordering a vector space (see Aptoula and Lefèvre [9] for a rather complete survey of color orders used in the mathematical morphology framework). In this section, we review only the most well-known approaches to order vectorial data.
Conditional orderings (C-ordering)
With C-ordering, vectors are ordered by means of one, several, or all of their marginal components. The most well-known C-ordering is the lexicographical ordering, that is a total order. If only several components participate in the comparison, it yields a total preorder. For example let v, w ∈ Rn, the lexicographical ordering ≤L using only the two first components (v ≤L w iff v1 < w1 ∨ v1 = w1 ∧ v2 ≤ w2) is a total preorder. Colors (1, 1, 2) and (1, 1, 3) are considered as equivalent by the above relation. The main pitfall of C-orderings lies in the importance given to the first components. Considering the RGB space for example, it implies that the red component is more relevant than the others. Workarounds like the sub-quantization of first components (also known as α-trimmed lexicographical ordering [97, 7, 115]) enables to lower the importance given to the first dimension.
Local orderings and “pseudo”-morphological filters
Because of the consequences of theorem 1 (i.e., there does not exist a-priori any relevant total ordering on a multi-dimensional value space), authors have been involved in developing image content dependant ordering relations (see. sections 4.3.2 and 4.3.3). This idea can be developed further by considering an ordering relation which is locally dependant on the data. In [72, 73], authors impose a total order for each pixel, relying only on the vector values in a spacial local window. Those values are represented as a fully connected graph where edges are valuated with a distance color. Then, they aim at extracting an Hamiltonian path (i.e., a linear order) from this graph using minimum spanning trees. Yet, a drawback of a local ordering lies in that the fact that it does not provide a partial ordering of the full value set; erosion and dilation lose important algebraic properties (e.g. they do not commute with the infimum/supremum) that prevent the construction of “real” morphological filters.
Table of contents :
1 introduction
Part I A REVIEW OF CLAS S ICAL IMAGE HIERARCHIES
2 hierarchical clustering approaches
2.1 Well-known hierarchies of segmentations
2.2 Processing and transforming hierarchies
2.3 Conclusion
3 trees based on the threshold decomposition
3.1 Min and max-trees
3.2 The Tree of Shapes (ToS)
4 morphological trees extended to multivariate images
4.1 Problem statement
4.2 Multivariate mage processing strategies
4.3 On the imposition of a total ordering
4.4 Conclusion
5 component graphs
5.1 Component trees extended to partial order
5.2 Processing the component graphs
5.3 Conclusion
ii a new approach for a tree of shapes on multivariate images
6 the multivariate tree of shapes (mtos)
6.1 Method overview
6.2 The Graph of Shapes (GoS)
6.3 Computing a tree from the graph
6.4 Choosing a Sensible ρ Function
6.5 Selecting shapes by priority
6.6 Conclusion
7 properties of the mtos
7.1 Topological Considerations
7.2 Proof of correctness
7.3 Conclusion
8 mtos computation algorithm
8.1 Computing the Graph of Shapes
8.2 Tree Extraction Algorithm
8.3 Complexity analysis
8.4 Conclusion
