Diffusion bases methods for segmentation and clustering

• US 20080181503A1
• Filed: 01/30/2007
• Published: 07/31/2008
• Est. Priority Date: 01/30/2007
• Status: Active Grant

• Current Assignee: Alon Schclar, Amir Zeev Averbuch
• Original Assignee: Alon Schclar, Amir Zeev Averbuch
• Inventors: Schclar, Alon, Averbuch, Amir Zeev
• Granted Patent: US 7,961,957 B2
• Time in Patent Office: Days
• US Class Current: 382/181
• CPC Class Codes: G06F 18/21375 involving differential geometry, e.g. embedding of pattern manifold
• CPC Class Codes: G06F 18/2323 based on graph theory, e.g. minimum spanning trees [MST] or graph cuts
• CPC Class Codes: G06V 10/267 by performing operations on regions, e.g. growing, shrinking or watersheds
• CPC Class Codes: G06V 10/28 Quantising the image, e.g. histogram thresholding for discrimination between background and foreground patterns
• CPC Class Codes: G06V 10/7635 based on graphs, e.g. graph cuts or spectral clustering
• CPC Class Codes: G06V 10/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods

Abstract

Methods for dimensionality reduction of large data volumes, in particular hyper-spectral data cubes, include providing a dataset Γ of data points given as vectors, building a weighted graph G on Γ with a weight function w_ε, wherein w_ε corresponds to a local coordinate-wise similarity between the coordinates in Γ; obtaining eigenvectors of a matrix derived from graph G and weight function w_ε, and projecting the data points in Γ onto the eigenvectors to obtain a set of projection values Γ_B for each data point, whereby Γ_B represents coordinates in a reduced space. In one embodiment, the matrix is constructed through the dividing each element of w_ε by a square sum of its row multiplied by a square sum of its column. In another embodiment the matrix is constructed through a random walk on graph G via a Markov transition matrix P, which is derived from w_ε. The reduced space coordinates are advantageously used to rapidly and efficiently perform segmentation and clustering.

Claims

1. A method for dimensionality reduction of large data volumes comprising the steps of:

a. providing a dataset Γ

of data points given as vectors;

b. building a weighted graph G on Γ

with a weight function w_ε

, wherein w_ε

corresponds to a local coordinate-wise similarity between the coordinates in Γ

;

c. constructing a random walk on graph G via a Markov transition matrix P, which is derived from w_ε

;

d. performing a spectral decomposition of P to obtain right and left eigenvectors of P; and

e. projecting the data points in Γ

onto the right eigenvectors of P to obtain a set of projection values Γ

_B for each data point, whereby Γ

_B represents coordinates in a reduced space.

2. The method of claim 1, wherein dataset Γ

is a static dataset.

3. The method of claim 2, wherein the static dataset is uniform.

4. The method of claim 3, wherein the uniform static dataset represents hyper-spectral data.

5. The method of claim 1, wherein dataset Γ

is a heterogeneous dataset.

6. The method of claim 5, wherein the heterogeneous dataset is dynamic.

7. The method of claim 1, wherein Γ

={x_i}_i=1^m,x_i∈

ⁿ and wherein the step of building a weighted graph G on Γ

includes;

i. providing a coordinate dataset Γ

′

={x′

_j}_j=1ⁿ based on Γ

, and

ii. building a weight function w_ε

using coordinate dataset Γ

′

={x′

_j}_j=1ⁿ

8. The method of claim 1, wherein the step of projecting the data points in Γ

onto the eigenvectors of A to obtain a set of projection values Γ

_B for each data point includes;

i. constructing a diffusion basis B using a spectral decay property of the spectral decomposition, and

ii. projecting dataset Γ

onto basis B to obtain Γ

_B.

9. The method of claim 1, applied to an action selected from the group consisting of segmentation and clustering.

10. The method of claim 1, wherein the step of projecting the data points in Γ

onto the right eigenvectors of P to obtain a set of projection values Γ

_B includes;

i. constructing a diffusion basis B using a spectral decay property of the spectral decomposition, and

ii. projecting dataset Γ

onto basis B to obtain Γ

_B

11. The method of claim 1, applied to an action selected from the group consisting of segmentation and clustering.

12. The method of claim 7, wherein the providing a coordinate dataset Γ

′

={x′

_j}_j=1ⁿ based on Γ

further includes;

A. constructing a matrix M so that its i-th row is composed of x_i,

B. defining a vector x′

_j(x₁(j), . . . ,x_m(j)) to be the j^th coordinate of all the vectors in Γ

, wherein x′

_j is the j-th row of the transpose of matrix M, and

C. using vectors x′

_j to construct coordinate dataset Γ

′

={x′

_j}_j=1ⁿ.

13. The method of claim 7, wherein the providing a coordinate dataset Γ

′

={x′

_j}_j=1ⁿ based on Γ

further includes;

A. constructing a matrix M so that its i-th row is composed of x_i,

B. defining a vector x′

_j(x₁(j), . . . ,x_m( j)) to be the j^th coordinate of all the vectors in F, wherein x′

_j is the j-th row of the transpose of matrix M, and

C. using vectors x′

_j to construct coordinate dataset Γ

′

={x′

_j}_j=1ⁿ.

14. A method for dimensionality reduction of large data volumes comprising steps of:

a. providing a dataset Γ

of data points given as vectors;

b. building a weighted graph G on Γ

with a weight function w_ε

, wherein w_ε

corresponds to a local coordinate-wise similarity between the coordinates in Γ

;

c. constructing a matrix A which is the result of dividing each element of w_ε

by a square sum of its row multiplied by a square sum of its column;

d. performing a spectral decomposition of matrix A to obtain eigenvectors of A; and

e. projecting the data points in Γ

onto the eigenvectors of A to obtain a set of projection values Γ

_B for each data point, whereby Γ

_B represents coordinates in a reduced space.

15. The method of claim 14, wherein dataset Γ

is a static dataset.

16. The method of claim 15, wherein the static dataset is uniform.

17. The method of claim 16, wherein the uniform static dataset represents hyper-spectral data.

18. The method of claim 14, wherein dataset Γ

is a heterogeneous dataset.

19. The method of claim 18, wherein the heterogeneous dataset is dynamic.

20. The method of claim 14, wherein Γ

={x_i}_i=1^m, x_i∈

ⁿ and wherein the step of building a weighted graph G on Γ

includes;

i. providing a coordinate dataset Γ

′

={x′

_j}_j=1ⁿ based on Γ

, and

ii. building a weight function w_ε

using coordinate dataset Γ

′

={x′

_j}_j=1ⁿ