Method for constructing covariance matrices from data features

• US 7,720,289 B2
• Filed: 12/14/2005
• Issued: 05/18/2010
• Est. Priority Date: 12/14/2005
• Status: Expired due to Fees

• Current Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Original Assignee: Mitsubishi Electric Research Laboratories, Inc. (Mitsubishi Electric Corporation)
• Inventors: Tuzel, Oncel, Porikli, Fatih M.
• Primary Examiner(s): Werner; Brian P
• Assistant Examiner(s): VANCHY JR, MICHAEL J
• Application Number:
  US11/305,427
• Publication Number:
  US 20070133878A1
• Time in Patent Office: 1,616 Days
• Field of Search: 382/190, 382/103, 382/191, 382/195
• US Class Current: 382/195
• CPC Class Codes: G06F 18/22 Matching criteria, e.g. proximity measures
• CPC Class Codes: G06V 10/50 by performing operations within image blocks; by using histograms, e.g. histogram of oriented gradients [HoG]; by summing image-intensity values; Projection analysis
• CPC Class Codes: G06V 10/761 Proximity, similarity or dissimilarity measures

Abstract

A method constructs descriptors for a set of data samples and determines a distance score between pairs of subsets selected from the set of data samples. A d-dimensional feature vector is extracted for each sample in each subset of samples. The feature vector includes indices to the corresponding sample and properties of the sample. The feature vectors of each subset of samples are combined into a d×d dimensional covariance matrix. The covariance matrix is a descriptor of the corresponding subset of samples. Then, a distance score is determined between the two subsets of samples using the descriptors to measure a similarity between the descriptors.

Claims

1. A computer implemented method for constructing descriptors for a set of data samples, comprising a computer for performing steps of the method, comprising the steps of:

selecting multiple subsets of samples from a set of data samples;

extracting a d-dimensional feature vector for each sample in each subset of samples, in which the feature vector includes indices to the corresponding sample and properties of the sample;

combining the feature vectors of each subset of samples into a d×

d dimensional covariance matrix, the covariance matrix being a descriptor of the corresponding subset of samples; and

determining a distance score between a pair of covariance matrices to measure a similarity of the corresponding subsets of samples;

defining a covariance distance metric;

determining pair-wise distance scores between pairs of the covariance matrices;

constructing a d×

d dimensional auto-distance matrix from the pair-wise distance scores; and

assigning the auto-distance matrix as the descriptor of the set of data samples.

2. The method of claim 1, further comprising:

arranging the covariance matrices into an aggregated covariance matrix as the descriptor of the set of data samples.

3. The method of claim 1, further comprising:

defining a covariance distance metric;

determining iteratively a first order approximation of an intrinsic mean matrix of the covariance matrices; and

assigning the intrinsic mean matrix as the descriptor of the set of data samples.

4. The method of claim 1, further comprising:

applying masks to set of data samples.

5. The method of claim 1, in which the indices are spatial.

6. The method of claim 5, in which the set of data samples includes pixels of an image.

7. The method of claim 6 in which the feature vectors include locations of the pixels in the image.

8. The method of claim 7, in which the feature vectors including intensities of the pixels, color information of the pixels, color gradients of the pixels, color derivatives of the pixels, and filter responses of the pixels.

9. The method of claim 6, further comprising:

determining a set of integral images from the image; and

deriving the covariance matrices from the set of integral images.

10. The method of claim 9, further comprising:

determining a first order of the integral images as

$P<br><br>\left(x^{\mathrm{\prime <br><br>}},y^{\mathrm{\prime <br><br>}},i\right)=\underset{x<<br><br>x^{\mathrm{\prime <br><br>}},y<<br><br>y^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>F<br><br>\left(x,y,i\right)<br><br><br><br>i=1<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>d,$

and

a second order of the integral images as

$Q<br><br>\left(x^{\mathrm{\prime <br><br>}},y^{\mathrm{\prime <br><br>}},i,j\right)=\underset{x<<br><br>x^{\mathrm{\prime <br><br>}},y<<br><br>y^{\mathrm{\prime <br><br>}}}{\sum <br><br>}<br><br>F<br><br>\left(x,y,i\right)<br><br>F<br><br>\left(x,y,j\right)<br><br><br><br>i,j=1<br><br><br><br>\mathrm{\dots <br><br>}<br><br><br><br>d.,$

where x and y represent the locations of the pixels.

11. The method of claim 9, further comprising:

constructing the covariance matrices of different sized regions from the corner point values of the first and second order integral images.

12. The method of claim 6, further comprising:

locating an object in a test image according to the covariance matrices.

13. The method of claim 12, further comprising:

constructing covariance matrices for pixels in an entire region of the test image including the object and pixels in sub-regions including the object; and

assigning the multiple covariance matrices as a descriptor of the object.

14. The method of claim 12, further comprising:

selecting multiple test regions from the test image;

constructing multiple covariance matrices as descriptors of test regions;

determining distance scores for the test regions; and

assigning a minimum distance score as an estimated location of the object in the test image.

15. The method of claim 14, further comprising:

assigning an initial size to a target region to obtain a candidate region including the object;

selecting multiple test regions from the image with the initial size;

determining distance scores between the descriptors; and

changing a size; and

iterating the selecting and determining steps.

16. The method of claim 6, further comprising:

classifying textures in the image according to the covariance matrices.

17. The method of claim 16, further comprising:

representing each class of known textures in known regions as a first set of covariance matrices;

representing each test region with an unknown texture as a second set of covariance matrices;

determining distances scores between the first and second covariance matrices;

selecting a class that has a minimum distance score as the class of the test region.

18. The method of claim 17, further comprising:

giving a single vote to a particular class that has a minimum distance score to each covariance matrix of the test region; and

selecting the class that has a majority vote as the class of the test region.

19. The method of claim 18, further comprising:

computing a variance of the class votes; and

assigning the variance as a confidence score.

20. The method of claim 5, in which the set of data samples includes points of a volumetric data set.

21. The method of claim 20, in which the feature vectors include coordinates of the pixels.

22. The method of claim 1, in which the indices are temporal.

23. The method of claim 22, in which the set of data samples includes pixels of a video.

24. The method of claim 1, in which the indices are spatial and temporal.

25. The method of claim 1, in which the covariance matrix is

$\mathrm{CR}=\frac{1}{n-1}$

∑

k = 1 n ⁢

( z k - μ

) ⁢

( z k - μ

) T ,

where n is the number of samples in the subset, z represents the feature vectors, μ

is a mean of the features, and T is a transpose operator.

26. The method of claim 1, in which diagonal entries of the covariance matrix represent variances of the features and non-diagonal entries represent correlations of the features.

27. The method of claim 1, further comprising:

filtering the set of data samples prior to extracting the feature vectors.

28. The method of claim 1, in which the distance score is

$\rho$

⁡

( C 1 , C 2 ) = ∑

i = 1 n ⁢

ln 2 ⁢

λ

i ⁡

( C 1 , C 2 ) ,

where {λ

_i(C₁, C₂)}_{i=1, . . . , n} are generalized eigenvalues of two covariance matrices C₁ and C₂, according to λ

_iC₁x_i−

C₂x_i=0, for i=1, . . . , d, and x≠

0 are generalized eigenvectors of the covariance matrices.

29. The method of claim 1, further comprising:

constructing a cross-distance matrix from multiple pair-wise distances.

30. The method of claim 1, further comprising:

determining the distance scores as

$\mathrm{\rho <br><br>}<br><br>\left(O,T\right)=\underset{j}{\min }<br><br>\left[\underset{i=1}{\overset{5}{\sum <br><br>}}<br><br>\mathrm{\rho <br><br>}<br><br>\left(C_i^O,C_i^T\right)-\mathrm{\rho <br><br>}<br><br>\left(C_j^O,C_j^T\right)\right],$

where C^O_i and C^T_i represent various covariance matrices.