Using the Bhattacharyya Mean for the Filtering and Clustering of Positive-Definite Matrices

28/08/2013
OAI : oai:www.see.asso.fr:2552:4870
DOI :

Résumé

Using the Bhattacharyya Mean for the Filtering and Clustering of Positive-Definite Matrices

Métriques

906
219
2.35 Mo
 application/pdf
bitcache://1bcee8805fb9b1a8b8a54213bb913f816af10309

Licence

Creative Commons Aucune (Tous droits réservés)

Sponsors

Sponsors scientifique

logo_smf_cmjn.gif

Sponsors financier

gdrmia_logo.png
logo_inria.png
image010.png
logothales.jpg

Sponsors logistique

logo-minesparistech.jpg
logo-universite-paris-sud.jpg
logo_supelec.png
Séminaire Léon Brillouin Logo
sonycsl.jpg
logo_cnrs_2.jpg
logo_ircam.png
logo_imb.png
<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/2552/4870</identifier><creators><creator><creatorName>Malek Chari</creatorName></creator><creator><creatorName>Zaineb Chebbi</creatorName></creator><creator><creatorName>Maher Moakher</creatorName></creator><creator><creatorName>Baba Vemuri</creatorName></creator></creators><titles>
            <title>Using the Bhattacharyya Mean for the Filtering and Clustering of Positive-Definite Matrices</title></titles>
        <publisher>SEE</publisher>
        <publicationYear>2013</publicationYear>
        <resourceType resourceTypeGeneral="Text">Text</resourceType><dates>
	    <date dateType="Created">Mon 16 Sep 2013</date>
	    <date dateType="Updated">Mon 25 Jul 2016</date>
            <date dateType="Submitted">Mon 12 Nov 2018</date>
	</dates>
        <alternateIdentifiers>
	    <alternateIdentifier alternateIdentifierType="bitstream">1bcee8805fb9b1a8b8a54213bb913f816af10309</alternateIdentifier>
	</alternateIdentifiers>
        <formats>
	    <format>application/pdf</format>
	</formats>
	<version>9637</version>
        <descriptions>
            <description descriptionType="Abstract"></description>
        </descriptions>
    </resource>
.

Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Using the Bhattacharyya Mean for the Filtering and Clustering of Positive-Definite Matrices Malek Charfi, Zaineb Chebbi, Maher Moakher and Baba Vemuri National Engineering School at Tunis, Tunisia GSI’13, August 29, 2013 M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications OUTLINE 1 INTRODUCTION 2 DISTANCES ON THE SPACE OF POSITIVE-DEFINITE MATRICES Riemannian distance Bhattacharyya distance 3 MEANS AND MEDIANS OF POSITIVE-DEFINITE MATRICES 4 APPLICATIONS Application to smoothing magnetic resonnance imaging Application to data classification M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications INTRODUCTION In the last few years there has been a growing interest in studying means of symmetric positive-definite matrices. The interest in matrix means has been motivated by theoretical, computational and practical aspects : • Theory of matrix means [M. ’02, Ando, Li & Matthias ’04, M. ’05, Bhatia & Holbrook ’06, ...] • Effective computation of matrix means [M. ’06, Lawson & Lim ’09, Bini, Meini & Poloni ’09, ...] • Smoothing, interpolation and classification of Diffusion-Tensor MRI data sets [M. & Batchelor ’06, Deriche ’06, Vemuri ’07, ...], averaging elasticity tensors [M. ’06]. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications AVERAGING POSITIVE NUMBERS If d(·, ·) is a distance function on R+ then for a set of real numbers, x1, . . . , xN, and a set of positive weights that sum to 1, w1, . . . , wN one can define : The weighted mean mean(x1, . . . , xN; w1, . . . , wN) = argminx∈R+ N i=1 wid2 (xi, x); and the weighted median med(x1, . . . , xN; w1, . . . , wN) = argminx∈R+ N i=1 wid(xi, x). M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications EXAMPLES If we take the Euclidean distance d(x, y) = |x − y|, then we get the weighted arithmetic mean A(x1, . . . , xN; w1, . . . , wN) = N i=1 wixi. If we take the hyperbolic distance d(x, y) = | Log(x) − Log(y)|, then we get the weighted geometric mean G(x1, . . . , xN; w1, . . . , wN) = N i=1 xwi i . Given any distance on R+, the median is defined as the middle entry in the list after sorting it into increasing order if the cardinal of the list is odd. Otherwise, the median is then equal to the associated mean of the two middle numbers. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance SPACE OF SYMMETRIC POSITIVE-DEFINITE MATRICES The space of symmetric positive-definite matrices P(n) := {A ∈ M (n) | A = AT , A > 0} is a Riemannian manifold. In fact, it is the interior of a pointed convex cone : cone : A ∈ P(n) ⇒ tA ∈ P(n), t > 0. convex : A, B ∈ P(n) ⇒ tA + (1 − t)B ∈ P(n), 0 ≤ t ≤ 1. The boundary of P(n) is the set of singular positive semidefinite matrices. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance SYMMETRIC POSITIVE-DEFINITE 2-BY-2 MATRICES P(2) := a c c b , a > 0, ab − c2 > 0 . With the change of variables u = 1 2 (a + b), v = 1 2 (a − b), the conditions of positive definiteness become c2 + v2 < u2 , u > 0, which are clearly the equations of the forward light cone. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance RIEMANNIAN METRIC The Hessian of the information potential function (also called Logarithmic barrier) ϕ(X) = − ln det X defines a Riemannian metric on P(n) : Hess ϕ(X)(U, V) = tr(X−1 UX−1 V) =: gX(U, V). Facts : The Riemannian metric ds2 ϕ := gX(dX, dX) is invariant under I) inversion : X → X−1 ; II) congruent transformations : X → CXCT , ∀C ∈ GL(n). M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance RIEMANNIAN DISTANCE Let CA,B = {Γ : [a, b] → P(n) is C2 , Γ(a) = A, Γ(b) = B}. The length of a curve in CA,B is defined by the functional L (Γ) := b a [gΓ( ˙Γ(t), ˙Γ(t))]1/2 dt. Riemannian distance distR(A, B) := inf L (Γ), Γ ∈ CA,B = Log(A−1/2 BA−1/2 ) F. Fact : (P(n), distR(·, ·)) is a complete Riemannian manifold. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance DIVERGENCE FUNCTION DEFINITION A divergence on a space X is a function J : X × X → R that satisfies : J(x, y) ≥ 0 for all x and y in X, J(x, y) = 0 if and only if x = y. REMARK The divergence function is “almost” a distance function. It needs not to be symmetric with respect to its arguments, nor to satisfy the triangle inequality. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance BHATTACHARYYA DIVERGENCE If f : ω → R is a differentiable and strictly convex function defined on a closed convex set ω of Rm, then [Zhang ’04] Df (x, y) = 1 2f(x) + 1 2f(y) − f 1 2 x + 1 2 y , defines a divergence function. By using the strictly convex function ϕ(X) = − ln det X on P(n) we obtain the divergence function : DEFINITION (M. & CHEBBI ’10, CHEBBI & M. ’12) The Bhattacharyya divergence function of two matrices A and B in P(n) is defined by D(A, B) = 4ln det 1 2A + 1 2 B det(A) 1 2 det(B) 1 2 , M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance PROPERTIES The Bhattacharyya divergence satisfies the following invariance properties : 1 Symmetry D(A, B) = D(B, A), ∀A, B ∈ P(n). 2 Invariance under congruence transformations D(CACT , CBCT ) = D(A, B), ∀A, B ∈ P(n), ∀C ∈ GL(n). 3 Invariance under inversion D(A−1 , B−1 ) = D(A, B), ∀A, B ∈ P(n). M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance CONNECTION TO THE BHATTACHARYYA DIVERGENCE FUNCTIONS OF PROBABILITY DISTRIBUTIONS To measure closeness between two probability distributions p and q, Bhattacharyya (1943) introduced the divergence : B(p, q) = − ln Ω p(x)q(x)dx. When p and q are two n-dimensional multivariate Gaussian distributions zero mean vectors : p(x) = N(0, P) = 1 (2π)n det P exp (−1 2 xT P−1 x), q(x) = N(0, Q) = 1 (2π)n det Q exp (−1 2 xT Q−1 x), then, the Bhattacharyya divergence becomes B(N(0, P), N(0, Q)) = D(P, Q). M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Riemannian distance Bhattacharyya distance BHATTACHARYYA DISTANCE In general, the square root of symmetric divergence function satisfies all the properties of a distance function except the triangle inequality. PROPOSITION (CHEBBI & M. 12, SRA 13) The square root of the Bhattacharyya divergence is a distance function on P(n) that is unvariant under inversion and under congruent transformations. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications MEANS AND MEDIANS ON P(n) For the averaging on P(n) the space of positive-definite matrices, we shall use these two properly invariant distances : • The Riemannian distance dR(X, Y) := LogX(Y) F, where LogX(Y) = X 1 2 Log(X− 1 2 YX− 1 2 )X 1 2 . • The Bhattacharyya distance dB(X, Y) := 2 ln det 1 2 (X + Y) det (X) det (Y) . DEFINITION (M. ’05, FLETCHER ’09) The weighted mean/median associated with a distance dist(·, ·) of N symmetric positive-definite matrices A1, . . . , AN and weights w1, . . . , wN is M(A1, . . . , AN; w1, . . . , wN) = argminA∈P(n) N k=1 wk distp (A, Ak), where p is equal to 2 for the mean and 1 for the median. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications RIEMANNIAN MEAN PROPOSITION (M. ’05) Riemannian mean (Geometric mean) : MR(A1, . . . , AN) is the unique solution to N k=1 wk Log(XA−1 k ) = O. PROPOSITION (M. ’05, BHATIA & HOLBROOK ’06) The Riemannian mean (Geometric mean) of two symmetric positive-definite matrices A and B is given explicitly by A#B := A(A−1 B)1/2 = A1/2 (A−1/2 BA−1/2 )1/2 A1/2 . More generally, the weighted geometric mean of A and B with weights 1 − s and s is A#sB := A(A−1 B)s . M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications RIEMANNIAN MEDIAN The weighted Riemannian median of P1, . . . , PN, is the unique SPD matrix X, solution of : N i=1 ωi dR(Pi, X) LogX Pi = 0. Numerical solution : gradient-descent algorithm Xk+1 = ExpXk (α N i=1 ωi dR(Pi, Xk) LogXk Pi). M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications THE BHATTACHARYYA MEAN The weighted Bhattacharyya mean is given by the unique positive-definite matrix P ∈ P(n) satisfying : N i=1 wi 1 2 Pi + 1 2 P −1 = P−1 . Numerical solution : Fixed-point algorithm Xk+1 = N i=1 wi Pi + Xk 2 −1 −1 . M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications BHATTACHARYYA MEDIAN The weighted Bhattacharyya median is the unique positive-definite matrix X solution of the following equation : N i=1 ωi dB(Pi, X) Pi + X 2 −1 = N i=1 wi dB(Pi, X) X−1 . Numerical solution : Fixed-point algorithm Xk+1 = N i=1 ωi dB(Pi, Xk)   N j=1 wj dB(Pj, Xk Pj + Xk 2 −1   −1 . M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification APPLICATION TO SMOOTHING MAGNETIC RESONNANCE IMAGING We apply the different averaging methods described above to denoise a set of Magnetic Resonnance Imaging (MRI) data. In each pixel of the image, the MRI data can be stored as a fourth order tensor which is a symmetric positive definite matrix of order 6. Experiments were performed using synthetic DW-MRI dataset. We use an image region of size 32 × 32 of fourth-order diffusion tensors. Then, we add to it various levels of Rician noise of standard deviation σ = 0.1, 0.2 and 0.5. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification σ = 0.1 Original Noisy RiMedian BhMedian BhMean M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification σ = 0.2 Original Noisy RiMedian BhMedian BhMean M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification The error is calculated as the sum of the differences between the norm of the initial data and the norm of the denoised data. Error σ = 0.1 σ = 0.2 σ = 0.5 Original data 0 0 0 Noisy data 0.7091 1.0898 1.2782 Riemannian median 0.5474 0.8780 1.0403 Bhattacharyya median 0.5477 0.8849 1.0582 Bhattacharyya mean 0.5498 0.8627 1.0350 TABLE: Error values of the different filtering algorithms. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification CLASSIFICATION OF POSITIVE-DEFINITE MATRICES Another important area of research that uses Hermitian positive-definite matrices averaging is the clustering of polarimetric SAR data. The polarimetric data in each pixel follows a K distribution with parameters τ and C [Formont, Ovarlez and Pascal ’13]. Here C is a covariance matrix of a complex Gaussian vector and τ is a positive scalar random variable usually chosen to be gamma distributed. A Maximum-likelihood estimate algorithm for the estimation of the covariance matrix is proposed by [Gini and Greco ’02]. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification THE WISHART CLASSIFIER ALGORITHM In the literature, the well known classification model for polarimetric SAR data is the Wishart classifier which is described by : The Wishart classifier algorithm 1. Start with an initial classification of the image. 2. Compute the class centers Hi as the mean (or median) of the class elements. 3. Reassign the pixels to the corresponding class that minimizes the Wishart distance measure defined by dW(C, Hi) = log det(Hi) + tr(Hi −1 C). 4. Repeat steps 2-3 until a stopping criterion is met. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification To compare the efficiency of the three averaging methods, we constructed a simulated image as in [Formont, Ovarlez and Pascal ’13]. Then, the image is divided into four equal quadrants A1, . . . , A4. Each Ai, i = 1, . . . , 4 is again divided into four small quadrants Aij, j = 1, . . . , 4. Polarimetric information in each pixel of the region Aij is randomly chosen following the K distribution. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification FIGURE: In (a) we present the shape of a constructed image as in [Formont, Ovarlez and Pascal ’13], while in (b) we show the intialisation clusters for both the Wishart and Bhattacharyya classifier algorithms. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification FIGURE: Results of Wishart classifier algorithm for Riemannian median, Bhattacharyya median and Bhattacharyya mean, respectively after 3 iterations. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification MODIFIED WISHART CLASSIFIER Now, we replace the Wishart distance by the Bhattacharyya distance in the Wishart classifier algorithm. FIGURE: Results of modified Wishart classifier algorithm for Riemannian median, Bhattacharyya median and Bhattacharyya mean, respectively after 3 iterations. M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n) Introduction Distances on P(n) Means and medians of positive-definite matrices Applications Application to smoothing magnetic resonnance imaging Application to data classification Thank you for your attention ! M. Charfi, Z. Chebbi, M. Moakher and B. Vemuri Bhattacharyya Mean for the Filtering and Clustering on P(n)