LINEAR SPATIAL PYRAMID MATCHING USING SPARSE CODING

• US 20100124377A1
• Filed: 05/20/2009
• Published: 05/20/2010
• Est. Priority Date: 11/19/2008
• Status: Active Grant

• Current Assignee: NEC Corporation
• Original Assignee: NEC Laboratories America Inc (NEC Corporation)
• Inventors: Yu, Kai, Yang, Jianchao, Gong, Yihong
• Granted Patent: US 8,374,442 B2
• Time in Patent Office: Days
• US Class Current: 382/224
• 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/7715 Feature extraction, e.g. by transforming the feature space, e.g. multi-dimensional scaling [MDS]; Mappings, e.g. subspace methods

Abstract

Systems and methods are disclosed to classify an input image by determining a spatial-pyramid image representation based on sparse coding; determining a descriptor for each interest point in the input image; encoding the descriptor; and applying max pooling to form the spatial pyramid representation of images.

Claims

1. A method to classify an input image, comprising

a. determining a spatial-pyramid image representation based on sparse coding;

b. determining a descriptor for each interest point in the input image;

c. encoding the descriptor; and

d. applying max-pooling to form the spatial pyramid representation of images.

2. The method of claim 1, wherein the interest point detection comprises scanning the input image and detecting a set of key points representing the objects in the input image.

3. The method of claim 2, comprising selecting key points located on a predefined grid.

4. The method of claim 1, comprising determining a descriptor for each interest point.

5. The method of claim 1, comprising determining a descriptor feature vector to represent a visual pattern at a predetermined location.

6. The method of claim 1, wherein the descriptor comprises a raw image patch or a transformed representation of the raw image patch.

7. The method of claim 1, wherein the transformed representation comprises a local feature, a SIFT feature, or a SURF feature.

8. The method of claim 1, comprising performing a nonlinear transformation to encode each descriptor into a compact representation.

9. The method of claim 1, comprising applying local max pooling on multiple spatial scales to incorporate translation and scale invariance.

10. The method of claim 1, comprising determining a spatial pyramid representation of the image.

11. The method of claim 1, comprising determining statistics of the codes for each region of the input image in a set of locations and scales, and concatenating the statistics to form a vector.

12. The method of claim 1, comprising determining code statistics by computing a Least Mean Square or a Root Mean Square of the codes.

13. The method of claim 1, comprising determining code statistics by computing an absolute value of the codes.

14. The method of claim 1, comprising applying a linear support vector machine (SVM) based on the sparse coding of a local feature.

15. The method of claim 14, wherein the linear SVM kernel is used and wherein an image I_i is represented by z_i, comprising determining:

16. The method of claim 1, wherein the linear SVM comprises a binary SVM decision function

17. The method of claim 1, comprising applying a pooling function F as a max pooling function on absolute sparse codes

z_j=max{|u_1j|,u_2j|, . . . , |u_Mj|},

where z_j is the j-th element of z, u_ij is the matrix element at i-th row and j-th column of U, and M is the number of local descriptors in the region.

18. The method of claim 1, comprising solving an unconstrained convex optimization problem

19. The method of claim 1, comprising applying sparse coding followed by multi-scale spatial max pooling and applying a linear SVM kernel based on SIFT sparse codes.

20. An image classifier, comprising:

a. a nonlinear spatial pyramid matching engine with a sparse coding engine;

b. a feature extractor coupled to the pyramid matching engine to form a pyramid with max pooling; and

c. a linear support vector machine coupled to the feature extractor.