FAST PATTERN CLASSIFICATION BASED ON A SPARSE TRANSFORM

• US 20090297048A1
• Filed: 04/30/2009
• Published: 12/03/2009
• Est. Priority Date: 06/02/2008
• Status: Active Grant

• Current Assignee: Massachusetts Institute of Technology
• Original Assignee: Massachusetts Institute of Technology
• Inventors: Slotine, Jean-Jacques Emile, Yu, Guoshen
• Granted Patent: US 8,553,984 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• CPC Class Codes: G06F 18/2113 by ranking or filtering the set of features, e.g. using a measure of variance or of feature cross-correlation
• CPC Class Codes: G06F 18/2136 based on sparsity criteria, e.g. with an overcomplete basis
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/771 Feature selection, e.g. selecting representative features from a multi-dimensional feature space
• 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

Techniques for determining a feature in an image or soundtrack of one or more dimensions include receiving a subject image. A sparse transformed subject image is determined, which represents the subject image with a few significant coefficients compared to a number of values in the subject image. Multiple patch functions are received, which are based on a portion of a sparse transformed image for each of a training set of images and which represent learned features in the training set. A feature is determined to be in the subject image based on the transformed subject image and the plurality of patch functions. In various embodiments, a wavelet transformation or audio spectrogram is performed to produce the sparse transformed images. In some embodiments, the feature in the subject is determined regardless of feature location or size or orientation in the subject image.

Claims

1. A method for determining a feature in a subject image, comprising:

receiving a subject image;

determining a sparse transformed subject image that represents the subject image with a few significant coefficients compared to a number of values in the subject image;

receiving a plurality of number I of patch functions that are based on a portion of a sparse transformed image for each of a training set of images and represent learned features in the training set; and

sending data that indicates a feature in the subject image based on the transformed subject image and the plurality of patch functions.

2. A computer-readable storage medium carrying one or more sequences of instructions for determining a feature in a subject image, wherein execution of the one or more sequences of instructions by one or more processors causes the one or more processors to perform:

receiving a subject image;

determining a sparse transformed subject image that represents the subject image with a few significant coefficients compared to a number of values in the subject image;

receiving a plurality of number I of patch functions that are based on a portion of a sparse transformed image for each of a training set of images and represent learned features in the training set; and

determining a feature in the subject image based on the transformed subject image and the plurality of patch functions.

3. The computer-readable storage medium as recited in claim 2, wherein the image is a one-dimensional data set, such as a soundtrack data.

4. The computer-readable storage medium as recited in claim 2, wherein the image is a two-dimensional data set, such as a picture or a time-frequency plot of recorded sound.

5. The computer-readable storage medium as recited in claim 2, wherein the image is a three-dimensional data set, such as video data or a scanned volume comprising multiple scans of a two-dimensional scanning system.

6. The computer-readable storage medium as recited in claim 3, wherein determining the sparse transformed subject image comprises determining a log-spectrogram of soundtrack data.

7. The computer-readable storage medium as recited in claim 2, wherein determining a feature in the subject image further comprises determining the feature regardless of feature location or size or orientation in the subject image.

8. The computer-readable storage medium as recited in claim 2, wherein determining the sparse transformed subject image comprises performing a wavelet transformation of the subject image to produce a plurality of transformed subject images wherein each transformed image of the plurality of transformed images represents wavelet coefficients for a different combination of scale and orientation.

9. The computer-readable storage medium as recited in claim 2, wherein determining a feature in the subject image based on the transformed subject image and the plurality of patch functions further comprises:

determining for each patch function a similarity S of cell values in a local metric matrix based on the transformed subject image with the patch function positioned on the cell; and

determining a signature vector with a number I elements, wherein the ith element of the signature vector is a scalar measure of values of S produced from the similarity values of the ith patch function, P_i,

wherein the signature vector indicates which learned features are in the subject image.

10. The computer-readable storage medium as recited in claim 8, wherein receiving the plurality of number I of patch functions further comprises:

performing a wavelet transformation of each of the training images to produce a plurality of transformed training images wherein each transformed training image represents wavelet coefficients for a different combination of scale and orientation; and

determining each patch function P_i by selecting from one or more local metric matrices based on corresponding transformed training images a sample in a spatial window of maximum dimension M_i that is small compared to the size of the local metric matrix for each orientation at a particular scale, wherein i varies from 1 to I.

11. The computer-readable storage medium as recited in claim 2, wherein receiving the plurality of number I of patch functions further comprises further comprises:

determining a greater plurality of patch functions of number I₀ greater than I;

determining for each patch function a similarity S of cell values in a local metric matrix based on the transformed training images with the patch function positioned on the cell;

determining a variance vector with a number I₀ elements, wherein each element of the variance vector is a measure of difference among similarity values S over the plurality of training images with each patch function; and

retaining only the I patch functions corresponding to I elements of the variance vector associated with the greatest differences.

12. The computer-readable storage medium as recited in claim 2, wherein determining the plurality of number I of patch functions further comprises:

determining a greater plurality of patch functions of number I₀ greater than I;

determining a plurality of I clusters of patch functions; and

retaining only one patch function in each of the plurality of I clusters.

13. The computer-readable storage medium as recited in claim 8, wherein:

the plurality of number I of patch functions are based on a wavelet transformation of each of the training images, which produces a plurality of transformed training images wherein each transformed training image represents wavelet coefficients for a different combination of scale and orientation; and

each patch function P_i, for i varying from 1 to I, is determined by selecting from one or more local metric matrices based on corresponding transformed training images a sample in a spatial window of maximum dimension Mi that is small compared to the size of the local metric matrix for each orientation at a particular scale.

14. The computer-readable storage medium as recited in claim 2, further comprising classifying the image based on the feature in the subject image.

15. An apparatus for determining a feature in an image, comprising:

means for receiving a subject image;

means for determining a sparse transformed subject image that represents the subject image with a few significant coefficients compared to a number of values in the subject image;

means for receiving a plurality of number I of patch functions that are based on a portion of a sparse transformed image for each of a training set of images and represent learned features in the training set; and

means for determining a feature in the subject image based on the transformed subject image and the plurality of patch functions.

16. An apparatus for determining a feature in an image, comprising logic encoded in a tangible medium and configured to:

receive a subject image;

determine a sparse transformed subject image that represents the subject image with a few significant coefficients compared to a number of values in the subject image;

receive a plurality of number I of patch functions that are based on a portion of a sparse transformed image for each of a training set of images and represent learned features in the training set; and

determine a feature in the subject image based on the transformed subject image and the plurality of patch functions.

17. The apparatus as recited in claim 16, wherein the image is a one-dimensional data set, such as a soundtrack data.

18. The apparatus as recited in claim 16, wherein the image is a two-dimensional data set, such as a picture or a time-frequency plot of recorded sound.

19. The apparatus as recited in claim 16, wherein determining a feature in the subject image further comprises determining the feature regardless of feature location or size or orientation in the subject image.

20. The apparatus as recited in claim 16, wherein determining the sparse transformed subject image comprises performing a wavelet transformation of the subject image to produce a plurality of transformed subject images wherein each transformed image of the plurality of transformed images represents wavelet coefficients for a different combination of scale and orientation.