Share
Embed
Transcript
13 slides
-
VECTOR ORDERING DERIVED FROM BINARY PARTITION TREE LEAF REORDERING FOR
MATHEMATICAL MORPHOLOGY Olivier Lézoray Université Caen Normandie, ENSICAEN, CNRS, Normandie Univ. GREYC UMR 6072, Caen, France [email protected] https://lezoray.users.greyc.fr -
Why do we need a vector ordering? The problem Mathematical
morphology is naturally defined on a complete lattice, and requires a total order. ▶ Grayscale values have a natural total order. ▶ Color, multispectral or learned feature vectors do not. ▶ Lexicographic orderings are possible, but become unsuitable as the dimension grows. Standard solution Standard solution: construct an h-ordering, i.e. a surjection h : T → L onto a totally ordered lattice L, v i ≤h v j ⇐⇒ h(vi ) ≤ h(vj ) Our proposition Reorder the leaves of a Binary Partition Tree representing and image using both hierarchy and feature similarity O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 2 / 13 -
The ordering defines a palette and an index image Let
the reordered vectors vi be P = {v′1 , . . . , v′m }. The image is represented by an index image I and an ordered palette P: f(v) = P[I(v)]. f I P Morphological operations are applied to the index and reconstructed from the palette : g(f(v)) = P[g(I(v))] Vector image f Index image I O. Lézoray grayscale MM Ordered palette P Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 3 / 13 -
From a BPT to a complete lattice Binary Partition Tree
A BPT is obtained by hierarchical agglomerative clustering of image regions. ▶ Leaves correspond to the original pixels/regions. ▶ Each merge creates an internal node. An image and its BPT. ▶ With efficient data structures: O(m log m) construction. 1 Key observation At every internal node, the two children can be swapped. Thus the same BPT topology admits many valid leaf permutations. O. Lézoray 2 3 4 With a tree topology fixed, the leaf order can change How to order the leaves? Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 4 / 13 -
Leaf reordering: local traversal vs global optimization Existing BPT ordering
The BPT can simply be traversed from left to right: ▶ Determined by the local child ordering. ▶ No explicit optimization of the final leaf sequence. Our viewpoint Instead of accepting one traversal, optimize over all permutations compatible with the tree topology. ▶ Used by Veganzones et al. for vector ordering. OLO: the reference algorithm Optimal Leaf Ordering minimizes OLO(π) = m−1 X d(πi , πi+1 ). i=1 1 2 3 4 2| m−1 {z } compatible leaf permutations It explicitly favors smooth consecutive leaf vectors. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 5 / 13 -
UltraMixed: combine hierarchy and feature similarity Proposed objective For a
leaf order π = (π1 , . . . , πm ): UltraMixed(π) = m−1 X [h(LCA(πi , πi+1 )) + λ d(πi , πi+1 )] i=1 where d is the Euclidean feature distance and λ ≥ 0 controls the trade-off ▶ h(LCA) keeps consecutive leaves close in the hierarchy. ▶ λd keeps consecutive vectors similar. ▶ Produces a path that respects both the tree structure and the original data similarities. ▶ As OLO: can be solved by dynamic programming. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 6 / 13 -
How do we evaluate an ordering? 1. Palette smoothness 2.
Index irregularity The ordered palette should form a short path in feature space: The total order should preserve spatial neighborhoods: m−1 ∥P∥TV = 1 X ′ ∥vi − v′i+1 ∥. m−1 i=1 ▶ Lower = smoother ordering. ▶ Measures feature-space continuity. O. Lézoray ∥∇I∥TV = 1 X X |I(vi )−I(vj )|. |V||E| v v ∼v i j i ▶ Lower = better spatial neighborhood preservation and lower artifacts ▶ Computed directly from I. Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 7 / 13 -
A single CIFAR image: smoothness vs spatial regularity Lex BPT
OLO UltraMixed GPL P ∥P∥T V 0.4937 0.9165 0.7529 0.7720 0.8519 I ∥∇I∥T V 0.0936 0.0978 0.0869 0.0795 0.0838 What matters? ▶ Lexicographic order is very smooth, but has high spatial irregularity. ▶ OLO improves irregularity through leaf reordering. ▶ UltraMixed gives the lowest irregularity while remaining smooth. ▶ Optimizing only feature smoothness is not enough: the spatial structure encoded by the BPT matters. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 8 / 13 -
CIFAR: consistent behavior over 30,000 images Experimental setting ▶ CIFAR
training set: 30,000 color 32 × 32 images. ▶ BPT: average linkage. Main observation UltraMixed provides the best trade-off: short palette path and low index irregularity. Lexicographic smoothness is lower, but irregular and cannot be used with high-dimensional vectors. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 9 / 13 -
Any kind of feature! Dilation Opening Closing VGG16 Patches Colors
Erosion Figure: Morphological operations with a 3 × 3 structuring element with vectors: colors, 5 × 5 patches, and VGG16 features O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 10 / 13 -
Comparison with Veganzones et al. Original image UltraMixed [1] Erosion
Dilation Opening Closing Figure: Comparison with Veganzones [1] with a 11 × 11 structuring element. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 11 / 13 -
Conclusion 1. BPT leaf reordering: a way to build vector
orderings for multivariate mathematical morphology. 2. The proposed UltraMixed objective combines two complementary sources of information: hierarchical structure + feature similarity 3. UltraMixed gives a strong balance between palette smoothness and low irregularity, with coherent morphological results. 4. The approach is generic and can operate on high-dimensional feature representations. Future work Improve the scalability of leaf-reordering methods for large images and larger feature sets. O. Lézoray Vector Ordering Derived from Binary Partition Tree Leaf Reordering for Mathematical Morphology 12 / 13 -
The End O. Lézoray Vector Ordering Derived from Binary Partition
Tree Leaf Reordering for Mathematical Morphology 13 / 13