Nonlinear operators on graphs via stacks

28/10/2015
Publication GSI2015
OAI : oai:www.see.asso.fr:11784:14336

Résumé

We consider a framework for nonlinear operators on functions evaluated on graphs via stacks of level sets. We investigate a family of transformations on functions evaluated on graph which includes adaptive flat and non-flat erosions and dilations in the sense of mathematical morphology. Additionally, the connection to mean motion curvature on graphs is noted. Proposed operators are illustrated in the cases of functions on graphs, textured meshes and graphs of images.

Nonlinear operators on graphs via stacks

Collection

application/pdf Nonlinear operators on graphs via stacks Santiago Velasco-Forero, Jesús Angulo

Média

Voir la vidéo

Métriques

116
6
6.78 Mo
 application/pdf
bitcache://a28871cee30af65f27ec09810e65714367d7094a

Licence

Creative Commons Attribution-ShareAlike 4.0 International

Sponsors

Organisateurs

logo_see.gif
logocampusparissaclay.png

Sponsors

entropy1-01.png
springer-logo.png
lncs_logo.png
Séminaire Léon Brillouin Logo
logothales.jpg
smai.png
logo_cnrs_2.jpg
gdr-isis.png
logo_gdr-mia.png
logo_x.jpeg
logo-lix.png
logorioniledefrance.jpg
isc-pif_logo.png
logo_telecom_paristech.png
csdcunitwinlogo.jpg
<resource  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
                xmlns="http://datacite.org/schema/kernel-4"
                xsi:schemaLocation="http://datacite.org/schema/kernel-4 http://schema.datacite.org/meta/kernel-4/metadata.xsd">
        <identifier identifierType="DOI">10.23723/11784/14336</identifier><creators><creator><creatorName>Jesús Angulo</creatorName></creator><creator><creatorName>Santiago Velasco-Forero</creatorName></creator></creators><titles>
            <title>Nonlinear operators on graphs via stacks</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2015</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Sun 8 Nov 2015</date>
	    <date dateType="Updated">Wed 31 Aug 2016</date>
            <date dateType="Submitted">Sun 16 Sep 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">a28871cee30af65f27ec09810e65714367d7094a</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>24731</version>
        <descriptions>
            <description descriptionType="Abstract">
We consider a framework for nonlinear operators on functions evaluated on graphs via stacks of level sets. We investigate a family of transformations on functions evaluated on graph which includes adaptive flat and non-flat erosions and dilations in the sense of mathematical morphology. Additionally, the connection to mean motion curvature on graphs is noted. Proposed operators are illustrated in the cases of functions on graphs, textured meshes and graphs of images.

</description>
        </descriptions>
    </resource>
.

Nonlinear operators on graphs via stacks Nonlinear operators on graphs via stacks Santiago Velasco-Forero and Jesus Angulo velasco@cmm.ensmp.fr CMM - MINES-PARISTECH, France October 30, 2015 GSI 2015 1 / 53 Nonlinear operators on graphs via stacks Plan Motivation to G signal processing Max-plus signal processing on graphs Some applications 2 / 53 Nonlinear operators on graphs via stacks A graph signal 1. A graph signal on G = (V, E), is defined as a scalar valued discrete mapping f : V → R, such that f(n) is the value of the signal on node n 2. The objects under study are considered as the nodes (or vertices) of the graph G. 3. A simple, connected, undirected, and weighted graph G = (V, E) consists of a set of nodes V = {v1, v2, . . . , vN } and edges E = {(vn, vm, wnm)}, vn, vm ∈ V, where (vn, vm, wnm) denoted an edge of weight wnm between node vn and vm. 3 / 53 Nonlinear operators on graphs via stacks Motivation to G signal processing Graph signal processing (a) Image (b) Non-uniform sampling (c) Textured Mesh (d) G of images (e) Social networks (f) Discrete ap- proximation of a manifold 4 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Plan Motivation to G signal processing Max-plus signal processing on graphs Diffusion on graphs Morphological operators on graphs: via max-plus convolution Morphological operators on graphs: via diffusion Unexpected Link: Motion by mean curvature on graphs Some applications Mesh data Data analysis 5 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Notation 1. A graph signal is defined as a scalar valued discrete mapping f : V → R, such that f(n) is the value of the signal on node n. 2. We often analyze operators transforming signals evaluated on graphs, for instance φ : f → φ(f), in this case we say that φ ∈ V × V, where the space of functions from V to R is denoted by V. 3. The adjacency matrix W of the graph is an N × N matrix with W(n, m) = wnm 6 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Example: Mesh-Hand 7 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Basic definitions: Upper level sets on graphs: The ULS of f ∈ V at level λ ∈ R is defined by χ(f, λ) = {n ∈ V : f(n) ≥ λ}. (1) 8 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Basic definitions: Upper level sets on graphs: The ULS of f ∈ V at level λ ∈ R is defined by χ(f, λ) = {n ∈ V : f(n) ≥ λ}. (1) Figure: Example of ULS for Lena 8 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Basic definitions: Upper level sets on graphs: The ULS of f ∈ V at level λ ∈ R is defined by χ(f, λ) = {n ∈ V : f(n) ≥ λ}. (1) Figure: Example of ULS for Lena Figure: Example of ULS in Hand-Mesh 8 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Basic definitions: Threshold-linear superposition on graphs The threshold-linear superposition of f ∈ V is defined by: f(n) = +∞ 0 χ(f, λ)(n)dλ (2) ... 9 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Commutation with thresholding We shall say that an operator φ ∈ V × V commutes with thresholding if φ (χ(f, λ)) = χ (φ(f), λ) for any signal f ∈ V and any value λ ∈ R. 10 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Commutation with thresholding We shall say that an operator φ ∈ V × V commutes with thresholding if φ (χ(f, λ)) = χ (φ(f), λ) for any signal f ∈ V and any value λ ∈ R. Proposition 1: The class of operators φ ∈ V × V that obey the threshold-linear superposition: 1. is closed under minimum, maximum and composition. 2. forms a vector space over the field of real numbers under vector addition (φ1 + φ2)(f) := φ1(f) + φ2(f) and the scalar multiplication (cφ)(f) := cφ(f) with c ∈ R. 10 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Second component: Diffusion on graphs [Evans, 1998] Consider an arbitrary graph G = (V, E, W) with Laplacian matrix L and a signal f ∈ V → RN . For a given constant σ > 0, define the time-varying vector fσ,t ∈ RN as the solution of the linear differential equation: ∂fσ,t ∂t = −σLfσ,t, f0 = f, (3) where σ is the thermal conductivity and controls the heat diffusion rate. 11 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Diffusion on graphs The general solution of the heat equation on RN is obtained by convolution. However, the solution of (3) denoted by fL σ,t ∈ V × V, is given by the matrix exponential as follows fL σ,t := exp (−σLt) f (4) which can be verified by direct substitution in (3). 12 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Diffusion on graphs The general solution of the heat equation on RN is obtained by convolution. However, the solution of (3) denoted by fL σ,t ∈ V × V, is given by the matrix exponential as follows fL σ,t := exp (−σLt) f (4) which can be verified by direct substitution in (3). 12 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Note that for a given time t, the n-th element of fσ,t(n) is ∂fL σ,t(n) ∂t = −σLfi (t) ⇐⇒ ∂fi (t) ∂t = N k=1 −σWik (fk (t) − fi (t)) = k∈N (n) σW(n, k)(fL σ,t(k) − fL σ,t(n)) where N(n) is the neighborhood of n. Thus, the heat flow on an edge grows proportionally with both the “temperature differential" fL σ,t(k) − fL σ,t(n) and the weight W(n, k). 13 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .1 14 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .2 15 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .3 16 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .4 17 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .5 18 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .6 19 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .7 20 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .8 21 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = .9 22 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1 23 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.1 24 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.2 25 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.3 26 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.4 27 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.5 28 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs σ = 1.6 29 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Diffusion on graphs Proposition 3: The operator fL σ,t in eq. (4) associated to the diffusion of a graph signal f, commutes with the stacking of cross-sections according to the threshold-linear superposition, i.e., fL σ,t(n) = +∞ 0 (χ(f, λ))L σ,t(n)dλ. Proof: 30 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Diffusion on graphs Aim: Nonlinear filters in max-plus algebra (a.k.a morphological filters) 31 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Max-plus algebra approach Assumption: The matrix W is −∞ ≤ W(n, m) ≤ 0, for all n, m. 1For a given matrix W = [W(i, j)], the conjugate of W to be W∗ = [−W(j, i)], i.e., W∗ is derived from W by transposing and negating. 32 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Max-plus algebra approach Assumption: The matrix W is −∞ ≤ W(n, m) ≤ 0, for all n, m. Given a dilation of f on a graph given by: δW(f)(n) = N m=1 (f(m) + W(n, m) := W ⊕ f(n) (5) 1For a given matrix W = [W(i, j)], the conjugate of W to be W∗ = [−W(j, i)], i.e., W∗ is derived from W by transposing and negating. 32 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Max-plus algebra approach Assumption: The matrix W is −∞ ≤ W(n, m) ≤ 0, for all n, m. Given a dilation of f on a graph given by: δW(f)(n) = N m=1 (f(m) + W(n, m) := W ⊕ f(n) (5) then the dual adjoint erosion is given by εWf(n) := N m=1 (f(m) + W∗ (n, m)) = N m=1 (f(m) − W(m, n)) := W∗ f(n) 1 1For a given matrix W = [W(i, j)], the conjugate of W to be W∗ = [−W(j, i)], i.e., W∗ is derived from W by transposing and negating. 32 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Contribution 1: Galois connection theorem Theorem 1 Given a W morphological weight matrix and, the pair of operators (εW, δW) defines an Galois connection, i.e., for all f, g ∈ V, we have W ⊕ f ≤ g ⇐⇒ f ≤ W∗ g.Proof: 33 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Contribution 1: Galois connection theorem Theorem 1 Given a W morphological weight matrix and, the pair of operators (εW, δW) defines an Galois connection, i.e., for all f, g ∈ V, we have W ⊕ f ≤ g ⇐⇒ f ≤ W∗ g.Proof: 33 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Why do we need a Galois connection? 34 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Textured mesh (a) εW(f) (b) f (c) δW(f) 35 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via max-plus convolution Contribution 2 (Morphological) Non-linear filters via Max-plus algebra approach: Non-linear filter via Diffusion + Thresholding approach. 1. Upper level sets 2. Diffusion 3. → Erosion, Dilation and Curvature Motion 36 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion Morphological operators on graphs: via diffusion Definition For a graph signal value f ∈ V, the convolution-thresholding nonlinear operator associated to the heat diffusion W of conductivity σ at scale t, and the threshold τ, with τ ∈ [0, 1], is the mapping F(V, R) → F(V, R) defined by ψL, τ (f) = +∞ 0 (χ(f, λ))L σ,t ≥ τ dλ (6) 37 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion Morphological operators on graph Proposition 4 For all f ∈ V: 1. ψL, τ (f) satisfies the threshold-linear superposition. 2. ψL, τ (f) is monotonous with respect to the choice of τ, i.e, τ1 ≤ τ2 ⇒ ψL, τ1 (f) ≤ ψL, τ2 (f). 3. If f1 ≤ f2, then ψL, τ (f1) ≤ ψL, τ (f2) for all σ, t ≥ 0. 38 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion Morphological operators on graph Proposition 4 For all f ∈ V: 1. ψL, τ (f) satisfies the threshold-linear superposition. 2. ψL, τ (f) is monotonous with respect to the choice of τ, i.e, τ1 ≤ τ2 ⇒ ψL, τ1 (f) ≤ ψL, τ2 (f). 3. If f1 ≤ f2, then ψL, τ (f1) ≤ ψL, τ (f2) for all σ, t ≥ 0. Proposition 5 δB(f) = lim τ→0+ ψB, τ (f) and εB(f) = lim τ→1− ψB, τ (f). 38 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion Erosion (d) Original (e) τ = .999, σ = 2 (f) τ = .999, σ = 3 (g) τ = .999, σ = 4 39 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion Dilation (h) Original (i) τ = .001, σ = 2 (j) τ = .001, σ = 3 (k) τ = .001, σ = 4 40 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Morphological operators on graphs: via diffusion τ = .5 (l) Original (m) τ = .5, σ = 2 (n) τ = .5, σ = 3 (o) τ = .5, σ = 4 Figure: 41 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Unexpected Link: Motion by mean curvature on graphs Motion by mean curvature on graphs Proposition 6: The operator in (6) in the case of τ = .5 is an iteration with of the approximate motion by mean curvature on a graph. [van Gennip et al., 2014, Merkurjev et al., 2013] 42 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Unexpected Link: Motion by mean curvature on graphs Motion by mean curvature on graphs Proposition 6: The operator in (6) in the case of τ = .5 is an iteration with of the approximate motion by mean curvature on a graph. [van Gennip et al., 2014, Merkurjev et al., 2013] Comments: 1. Discrete version of the Allen-Cahn equation, which is a reaction-diffusion equation of mathematical physics which describes the process of phase separation in iron alloys, including order-disorder transitions 2. It is important to note that the curvature is defined by means of the isotropic total variation [van Gennip et al., 2014] instead of the one-Laplacian as it is the case in [Elmoataz et al., 2008, Ta et al., 2008, Ta et al., 2011, Elmoataz et al., 2012] (d) Original (e) τ = .5, σ = 5 (f) τ = .5, σ = 10 42 / 53 Nonlinear operators on graphs via stacks Max-plus signal processing on graphs Unexpected Link: Motion by mean curvature on graphs Iteration until convergence in τ = .5 (Curvature Motion) (g) Original (h) τ = .5, σ = 2 (i) τ = .5, σ = 3 (j) τ = .5, σ = 4 43 / 53 Nonlinear operators on graphs via stacks Some applications Some examples in function evaluated on graphs (k) Original 44 / 53 Nonlinear operators on graphs via stacks Some applications Some examples in function evaluated on graphs (a) Original (b) Diffusion (c) Erosion (d) Dilation Figure: (σ = .02,t = 10) 44 / 53 Nonlinear operators on graphs via stacks Some applications (a) τ =0.2 (b) τ =0.5 (c) τ =0.8 (d) τ =0.2 (e) τ =0.5 (f) τ =0.8 Figure: Family of linear (b) and nonlinear transformations via thresholding of diffusion process. First row: (σ = .1, t = 10). Second row: (σ = .01, t = 10) 45 / 53 Nonlinear operators on graphs via stacks Some applications Textured mesh (a) Original 46 / 53 Nonlinear operators on graphs via stacks Some applications Textured mesh (c) Original (d) Dilation (τ = .001) 46 / 53 Nonlinear operators on graphs via stacks Some applications (e) Erosion (τ = .999) 47 / 53 Nonlinear operators on graphs via stacks Some applications (a) Erosion (τ = .999) (b) Curv. motion (τ = .5) Figure: Illustration of nonlinear filters on textured mesh. Note that both colors and mesh coordinates have been modified in the processing. 47 / 53 Nonlinear operators on graphs via stacks Some applications Applications on Machine Learning Figure: Semisupervised learning 48 / 53 Nonlinear operators on graphs via stacks Some applications Graph of images (a) τ = .1 (b) τ = .9 49 / 53 Nonlinear operators on graphs via stacks Some applications Graph of images (c) Original (d) τ = .5 Figure: Original vs Mean Curvature Filter 50 / 53 Nonlinear operators on graphs via stacks Some applications (a) Original Digits 51 / 53 Nonlinear operators on graphs via stacks Some applications (a) Original Digits (b) Mean Curvature, iter 3 51 / 53 Nonlinear operators on graphs via stacks Some applications (a) Original Digits (b) Mean Curvature, iter 3 (c) Mean Curvature, iter 6 51 / 53 Nonlinear operators on graphs via stacks Some applications (a) Original Digits (b) Mean Curvature, iter 3 (c) Mean Curvature, iter 6 (d) Mean Curvature, iter 9 51 / 53 Nonlinear operators on graphs via stacks Some applications (a) Original Digits (b) Mean Curvature, iter 3 (c) Mean Curvature, iter 6 (d) Mean Curvature, iter 9 (e) Mean Curvature, (convergence) Figure: G is the 5 nearest neighbors with W the Euclidean distance between pairs of images. Diffusion parameters (t = 20 and σ = .03). Note that digits tend to be similar in (d) (after ten iterations). 51 / 53 Nonlinear operators on graphs via stacks Some applications Conclusions Extension of Nonlinear filters to graph signal processing via Max-plus algebra approach. via Diffusion + Thresholding approach. 52 / 53 Nonlinear operators on graphs via stacks Some applications Conclusions Extension of Nonlinear filters to graph signal processing via Max-plus algebra approach. via Diffusion + Thresholding approach. Thanks for your attention. 52 / 53 Nonlinear operators on graphs via stacks Some applications Allen-Cahn phase-field equation The MBO algorithm is obtained by time splitting the Allen-Cahn phase-field equation for motion by mean curvature. 2 (a) Original (b) τ = .5, σ = 1 (c) τ = .5, σ = 5 (d) τ = .5, σ = 10 2The semi-linear heat equation called the Allen-Cahn equation is a reaction-diffusion equation of mathematical physics of the form: ∂u ∂t − δu + W (u) 2 = 0 ∈ RN × (0, ∞) (7) which was introduced by S.M. Allen and J.W. Can (1979) [Allen and Cahn, 1979] to describe the process of phase separation in iron alloys, including order-disorder transitions. Here W is a function that has only two equal minima; its typical form is W (v) = (v2 −1)2 2 , W denotes the derivative and is a positive parameter. 53 / 53 Nonlinear operators on graphs via stacks Some applications Allen, S. M. and Cahn, J. W. (1979). A microscopic theory for antiphase boundary motion and its application to antiphase domain coarsening. Acta Metallurgica, 27(6):1085–1095. Elmoataz, A. et al. (2008). Nonlocal discrete regularization on weighted graphs: a framework for image and manifold processing. Trans. Im. Proc., 17(7):1047–1060. Elmoataz, A. et al. (2012). Non-local morphological PDEs and p-Laplacian equation on graphs with applications in image proc. J. of Sel.Top. in S. P., 6(7):764–779. Evans, L. C. (1998). Partial differential equations. Providence, Rhode Land: American Mathematical Society. Merkurjev, E., Kostic, T., and Bertozzi, A. L. (2013). 53 / 53 Nonlinear operators on graphs via stacks Some applications An MBO scheme on graphs for segmentation and image proc. SIAM J. I. S., 6(4):1903–1930. Ta, V.-T., Elmoataz, A., and Lézoray, O. (2011). Nonlocal pdes-based morphology on weighted graphs for image and data processing. Trans. Im. Proc., 20(6):1504–1516. Ta, V.-T. et al. (2008). P.D.E. over graphs: Morphological processing of arbitrary discrete data. In Computer Vision–ECCV 2008, pages 668–680. Springer. van Gennip, Y. et al. (2014). Mean curvature, threshold dynamics, and phase field theory on finite graphs. Milan Journal of Mathematics, 82(1):3–65. 53 / 53