are dilation and erosion. Dilation δ of a function f0 : Ω ⊂ R2 → R consists in replacing the function value by the maximum value within a structuring element B such that: δB f0(x, y) = max f0(x + x , y + y )|(x , y ) ∈ B Erosion is computed by: B f0(x, y) = min f0(x + x , y + y )|(x , y ) ∈ B O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
king of multivariate data (signals on D or D domains), we will use the formalism of signals on graphs: The domain Ω of an image or a mesh is considered as a graph G = (V, E) Vertices V = {v1, . . . , vm} correspond to pixels of images or to nodes of a mesh. Edges eij = (vi, vj) connect vertices with 8-adjacency in images or according to the topology of the mesh. Images and meshes are represented as graph signals where real-valued vectors are associated to vertices: f : G → T ⊂ Rn The set T = {v1, · · · , vm} represents all the vectors associated to all vertices To each vertex vi ∈ G is associated a vector f(vi) = vi = T [i] O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
vectors: a complete lattice (T , ≤) MM is problematic for multivariate data since there is no natural ordering for vectors The framework of h-orderings can be considered for that : construct a mapping h from T to L where L is a complete lattice equipped with the conditional total ordering h : T → L and v → h(v), ∀(vi, vj) ∈ T × T vi ≤h vj ⇔ h(vi) ≤ h(vj) . ≤h denotes such an h-ordering O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
ordering ≤h on T ) ⇔ (space filling curve in T ) ⇔ (One dimensional permutation of T ) We propose to explore two different ways to construct complete lattices : By learning the mapping h : T → L to define a complete lattice ≤h By constructing a one dimensional permutation ordering P as an Hamiltonian path on the graph G O. L´ ezoray Multivariate approaches for graph signal morphological processing 8 / 8
total ordering relation using an explicit ordering: Lexicographic ordering BitMixing Ordering By proceeding this way, this is the definition of the ordering that induces the total lattice. We propose to consider the opposite. We will explicitly learn a mapping h : T → L on a multivariate graph signal. The obtained mapping will define the complete lattice in the projection space L Advantage : the learned lattice depends of the signal content and is more adaptive. h corresponds to a manifold learning operator. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
be linear since a distortion of the space is inevitable ! Solution : Consider non-linear dimensionality reduction with Laplacian Eigenmaps that corresponds to learn the manifold where the vectors live. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
be linear since a distortion of the space is inevitable ! Solution : Consider non-linear dimensionality reduction with Laplacian Eigenmaps that corresponds to learn the manifold where the vectors live. × Problem : Non-linear dimensionality reduction directly on the set T of vectors is not tractable in reasonable time ! O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
be linear since a distortion of the space is inevitable ! Solution : Consider non-linear dimensionality reduction with Laplacian Eigenmaps that corresponds to learn the manifold where the vectors live. × Problem : Non-linear dimensionality reduction directly on the set T of vectors is not tractable in reasonable time ! Solution : Consider a more efficient strategy. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
be linear since a distortion of the space is inevitable ! Solution : Consider non-linear dimensionality reduction with Laplacian Eigenmaps that corresponds to learn the manifold where the vectors live. × Problem : Non-linear dimensionality reduction directly on the set T of vectors is not tractable in reasonable time ! Solution : Consider a more efficient strategy. Proposed Three-Step Strategy Dictionary Learning to produce a set D from the set of initial vectors T Laplacian Eigenmaps Manifold Learning on the dictionary D to obtain a projection operator hD Out of sample extension to extrapolate hD to T and define h O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
, by Vector Quantization, a dictionary D = {x1 , . . . , xp } with p m Step : Manifold Learning on the dictionary Laplacian Eigenmaps Manifold Learning searches Φ such that 1 2 ij Φ(xi ) − Φ(xj ) 2 KD(i, j) = Tr(ΦT LΦ) with ΦT DDΦ = I. Compute the similarity matrix KD between vectors xi ∈ D with KD(i, j) = k(xi , xj ) = exp − x i −x j 2 2 σ2 with σ = max (x i ,x j )∈D xi − xj 2 2 Compute the degree diagonal matrix DD of KD Solution is obtained with the eigen-decomposition of the normalized Laplacian L = I − D−1 2 D KDD−1 2 D as L = ΦDΠDΦT D with eigenvectors ΦD = [Φ1 D , · · · , Φp D ] and eigenvalues ΠD = diag[λ1, · · · , λp] O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
for each element xi of the dictionary D: hD : xi → (φ1 D (xi ), · · · , φp D (xi ))T ∈ Rp . This constructs the lattice (D, ≤hD ) with a hD -ordering, valid only on D. Step : Extrapolation of the projection ΦD to all the vectors of T Compute similarity matrices KT on T and KDT between sets D and T Compute the degree diagonal matrix DDT of KDT Extrapolate eigenvectors obtained from D to T with ˜ Φ = D−1 2 DT KT DT D−1 2 D ΦD(diag[1] − ΠD)−1 Output: The final projection h : T ⊂ R3 → L ⊂ Rp on the manifold is given by ˜ Φ and defined as h(x) = ( ˜ φ1 (x), · · · , ˜ φp (x))T . The complete lattice (T , ≤h) is obtained by using the conditional ordering on h. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
of the set T : sorting all the vectors and retaining their rank in the ordering corresponds to creating explicitly the complete lattice (T , ≤h). Once the complete lattice is created, each element of the graph signal can be replaced by its rank, creating an index image. Image of 256 colors Index Image (T , ≤h) This (scalar) index image is the lattice representation of the multivalued image according to the ordering strategy ≤h . O. L´ ezoray Multivariate approaches for graph signal morphological processing 6 / 8
a sorted permutation P of T is constructed P = {v1 , · · · , vm } with vi ≤h vi+1 , ∀i ∈ [1, (m − 1)]. From the ordering, an index signal I : Ω ⊂ Z2 → [1, m] is defined as: I(pi ) = {k | vk = f(pi ) = vi} . The pair (I, P) provides a new graph signal representation (the index and the palette of ordered vectors). The original signal f can be directly recovered since one has f(pi ) = P[I(pi )] = T [i] = vi O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
be directly used to process the original graph signal, however, to be able to reconstruct the result, the values have to be kept within [1, m]. · A processing g operating on I must be a vector preserving one : g(f(vi)) = P[g(I(vi))] . Erosion and dilation of a graph signal f at vertex vi ∈ G by a structuring element Bk ⊂ G as: Bk (f)(vi) = {P[∧I(vj)], vj ∈ Bk(vi)} δB(f)(vi) = {P[∨I(vj)], vj ∈ Bk(vi)} A structuring element Bk(vi) of size k defined at a vertex vi corresponds to the set of vertices that can be reached from vi in k walks: Bk(vi) = {vj ∼ vi} ∪ {vi} if k = 1 Bk−1(vi) ∪ ∪∀vl∈Bk−1(vi) B1(vl) if k ≥ 2 O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
result Figure: Morphological image filtering (opening by reconstruction on a 2-hop). O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
Original image Contrast mapping result Figure: Morphological image contrast mapping (2 iterations of a contrast mapping on a 2-hop). O. L´ ezoray Multivariate approaches for graph signal morphological processing 6 / 8
or dilation depending on the sign of the morphological Laplacian. Original Toggle contrast mapping Figure: Morphological colored mesh toggle contrast mapping (5 iterations of a toggle contrast mapping on a 2-hop). O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
δB Figure: HDR Morphological Processing (B is a square of side 9 pixels) O. L´ ezoray Multivariate approaches for graph signal morphological processing 8 / 8
decomposition of a graph signal into l layers. The graph signal is decomposed into a base layer and several detail layers, each capturing a given scale of details. d−1 = f, i = 0 while i < l do Compute the graph signal representation at level i − 1: di−1 = (Ii−1, Pi−1) Morphological Filtering of di−1 : fi = MFBl−i (di−1) Compute the residual (detail layer): di = di−1 − fi Proceed to next layer: i = i + 1 end while O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
represented by f = l−2 i=0 fi + dl−1 To extract the successive layers in a coherent manner, the sequence of scales should be decreasing · Bl−i is a sequence of structuring elements of decreasing sizes with i ∈ [0, l − 1] Each detail layer di is computed on a different set of vectors than the previous layer di−1 · The graph signal representation (Ii, Pi) is computed for the successive layers The considered Morphological Filter should be suitable for a multi scale analysis · Use of OCCO filter : OCCOBk (f) = γBk (φBk (f))+φBk (γBk (f)) 2 O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
manipulating the different layers with specific coefficients and adding the modified layers altogether. ˆ f(vk) = S0(f0(vk)) + M(vk) · l−1 i=1 Si(fi(vk)) with fl−1 = dl−1 ( ) Each layer is manipulated by a nonlinear function Si(x) = 1 1+exp(−αix) for detail enhancement and tone manipulation. The parameter αi of the sigmoid is automatically determined and decreases while i increases: αi = α i+1 A structure mask M prevents boosting noise and artifacts while enhancing the main structures. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
MF with linear Our MF with mask coefficients ( , . , . ) (α = 30) ( . ) and without mask ( . ) O. L´ ezoray Multivariate approaches for graph signal morphological processing 6 / 8
with an image-adaptive h-ordering based on an space filling curve on the graph · an Hamiltonian path Equivalent as defining a sorted permutation of the vectors of T It is defined as P = PT with P a permutation matrix of size m × m Any permutation is not of interest, we search for the smoothest permutation expressed by the Total Variation of its elements: T TV = m−1 i=1 vi − vi+1 The optimal permutation operator P∗ can be obtained by minimizing the total variation of PT : P∗ = arg min P PT TV O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
solving the traveling salesman problem, which is very computationally demanding We consider a greedy approximation using a stochastic version of nearest neighbors heuristics This algorithm starts from an arbitrary vertex and continues by finding its unexplored neighbor vertex A new representation of the graph signal is obtained in the form of the pair (I, P) with I(vi) = σ(i) The original graph signal can be recovered: f(vi) = P[I(vi)] f : G → T I P = P∗T O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
the graph, its topology has strong influence The graph can consider only spatial or spectral information: Adjacency graph (denoted GB ): connects each vertex vi to all the vertices contained in a square box of size (2B + 1) × (2B + 1) around vi . K-Nearest Neighbor graph (denoted Gs K ): connects each vertex vi to its K nearest neighbors (in terms of spectral distance) within the set of all vertices. The graph can also consider both information and can use patches pw i around each vertex for distance computation P on G1 P on G10 P on G1 ∪ G20 ∗ with vi P on G1 ∪ G20 ∗ with p3 i PT TV = 5.81 PT TV = 2.60 PT TV = 1.06 PT TV = 6.42 Figure: Illustration of the influence of graph construction on the obtained permutation ordering. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
arbitrary vertex Different results with different starting vertices Idea: combine several orders hi Three different aggregation strategies are considered: Instant-Runoff: determines the final order according to majority ranking votes Borda-Count: assigns each item a score Bi(vj) = 1 − hi(vj)−1 m based on the positions and ranks the elements according to mean aggregation of the scores Weighted Borda Count: takes into account the smoothness of the order Bi s (vj) = Bi(vj) × ∇Pi(vj) O. L´ ezoray Multivariate approaches for graph signal morphological processing 6 / 8
P4 P5 Original image Instant-Runoff P Borda count P Weighted BC P Weighted BC I Figure: Consensus combination of different stochastic permutations. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
ordering ≤S ≤SwBc ≤SwBc with p5 i . 8 . . . . 6 . . 6 Figure: Comparison of different vectorial ordering strategies for a given image (shown in the first row). Second row presents for all the considered orderings, the ordering palette P and third row the associated index I. For each ordering the smoothness value PiT T V is provided. O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
5 × 5 square structuring element with 5 combined permutations and graph G10 . Original image Instant-Runoff Borda count Weighted BC WBC - G10 ∪ Gs 20 with vi WBC - G10 ∪ Gs 20 with p5 i O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
Veganzones et al. Our approach Figure: Comparison between the approach of Veganzones et al., and our approach with a 11 × 11 SE (one approach per line). O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
G10 graph) and a processing based on patches (with a G10 ∪ Gs 20 graph) Original image color closing Patch closing O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
we can obtain several complete lattices We built M stochastic permutation orderings (Ii, Pi) with i ∈ [1, M] We construct M watersheds from the minima of each ordering WSi(f) = WS(Ii, ∇f) We construct a pdf from the segmentation: pdf(f) = 1 M M i=0 G(WSi(f)) and combine it with the classical gradient ∇f = pdf(f) + ∇f 2 This pdf can be used for watershed segmentation from markers O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
gp Seeds Watershed with gc Watershed with gradient gp Figure: Segmentation examples with our stochastic permutation watershed. O. L´ ezoray Multivariate approaches for graph signal morphological processing 6 / 8
characters in the tapestry images A precise segmentation is required by using simple object/background seed labeling by point click to ease the end-users use The characters are visually easy to identify but the reduced number of colors, the fine embroidery as well as the texture differences in the linen fabric can make the segmentation hard. The permutation based stochastic watershed is performed with 7 × 7 patches O. L´ ezoray Multivariate approaches for graph signal morphological processing / 8
lezoray
atsukomasano2026
vegapunkhiroshi79
.jpg){kind=avatar}
iflection
yegusa
tomohirokoana
e869120_sub
fkske
nttcom
.png){kind=avatar}
satai
signer
yuukit
miso2024
sachag
emna__ayadi
jakevdp
bkeepers
jonoalderson
aleyda
mlcsv
tammyeverts
kimpetersen
aarron
marktimemedia
.png){kind=avatar}
helenjbeal
![The end [thank you] Any Questions ? [email protected] https://lezoray.users.greyc.fr O.](https://files.speakerdeck.com/presentations/dff6cdf7bdba4ad8b9ffb2f845d16b05/slide_66.jpg){kind=link}