Fast subspace projection of descriptor patches for image recognition

• US 8,897,572 B2
• Filed: 12/02/2010
• Issued: 11/25/2014
• Est. Priority Date: 12/02/2009
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Hamsici, Onur C., Reznik, Yuriy, Hong, John, Vaddadi, Sundeep, Lee, Chong U.
• Primary Examiner(s): Koziol, Stephen R
• Assistant Examiner(s): LE, TOTAM HA
• Application Number:
  US12/959,347
• Publication Number:
  US 20110299782A1
• Time in Patent Office: 1,454 Days
• Field of Search: 382/195
• US Class Current: 382/195
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A method for generating a feature descriptor is provided. A set of pre-generated sparse projection vectors is obtained. A scale space for an image is also obtained, where the scale space having a plurality scale levels. A descriptor for a keypoint in the scale space is then generated based on a combination of the sparse projection vectors and sparsely sampled pixel information for a plurality of pixels across the plurality of scale levels.

Claims

1. A method for generating a feature descriptor, comprising:

obtaining a set of pre-generated sparse projection vectors over a first plurality of scale levels;

obtaining a scale space for an image, the scale space having a second plurality scale levels; and

generating a descriptor for a keypoint in the scale space based on a combination of the sparse projection vectors and sparsely sampled pixel information for a plurality of pixels across the second plurality of scale levels.

2. The method of claim 1, wherein the sparse projection vectors are generated independent of the image.

3. The method of claim 1, where each sparse projection vector is constrained to scales of a smoothening kernel for the image.

4. The method of claim 1, wherein each of the sparse projection vectors maximize or minimize an objective function.

5. The method of claim 4, wherein the objective function is maximization of an autocorrelation matrix for pixel information across the first plurality of scale levels for a training set of images.

6. The method of claim 1, wherein a sparse projection vector includes a majority of zero elements and a plurality of non-zero elements.

7. The method of claim 6, wherein the non-zero elements are obtained by a variance maximization procedure.

8. The method of claim 1, wherein the pixel information includes gradient information for each pixel within a patch associated the keypoint.

9. The method of claim 1, wherein the plurality of pixels are associated with a patch for the keypoint.

10. The method of claim 1, wherein the plurality of pixels are selected at pre-determined locations corresponding to non-zero coefficients for the sparse projection vectors.

11. The method of claim 1, further comprising:

obtaining a keypoint from the scale space for the image; and

obtaining a patch for the keypoint, where the patch includes the plurality of pixels.

12. The method of claim 11, wherein the plurality of sparse projection vectors define a set of non-zero scaling coefficients, each non-zero scaling coefficient being associated with a corresponding pixel location within the patch.

13. The method of claim 12, wherein the descriptor is generated by combining a plurality of descriptor components, each descriptor component generated by;

identifying pixel locations based on the non-zero scaling coefficient locations for a first sparse projection vector;

multiplying a value of the pixel location from the patch with the corresponding non-zero scaling coefficient for the first sparse projection vector and add the resulting values together to obtain a first descriptor component.

14. The method of claim 13, further comprising:

obtaining additional descriptor components for the remaining plurality of sparse projection vectors to obtain additional descriptor components, wherein the first descriptor component and additional descriptor components are combined as a vector to obtain the keypoint descriptor.

15. The method of claim 9, wherein the patch has a dimension of m pixels by n pixels and is projected over the second plurality of scale levels s, then the keypoint descriptor is generated with fewer operations than the m*n*s dimensions of the patch.

61. The method of claim 1, wherein the scale space is a differential scale space.

16. A device, comprising:

a storage device for storing a set of pre-generated sparse projection vectors over a first plurality of scale levels; and

a processing circuit coupled to the storage device, the processing circuit adapted to;

obtain a scale space for an image, the scale space having a second plurality scale levels; and

generate a descriptor for a keypoint in the scale space based on a combination of the sparse projection vectors and sparsely sampled pixel information for a plurality of pixels across the second plurality of scale levels.

17. The device of claim 16, wherein the sparse projection vectors are generated independent of the image.

18. The device of claim 16, where each sparse projection vector is constrained to scales of a smoothening kernel for the image.

19. The device of claim 16, wherein each of the sparse projection vectors maximize or minimize an objective function.

20. The device of claim 19, wherein the objective function is maximization of an autocorrelation matrix for pixel information across the first plurality of scale levels for a training set of images.

21. The device of claim 16, wherein a sparse projection vector includes a majority of zero elements and a plurality of non-zero elements.

22. The device of claim 21, wherein the non-zero elements are obtained by a variance maximization procedure.

23. The device of claim 16, wherein the pixel information includes gradient information for each pixel within a patch associated the keypoint.

24. The device of claim 16, wherein the plurality of pixels are associated with a patch for the keypoint.

25. The device of claim 16, wherein the plurality of pixels are selected at pre-determined locations corresponding to non-zero coefficients for the sparse projection vectors.

26. The device of claim 16, wherein the processing circuit is further adapted to:

obtain a keypoint from the scale space for the image; and

obtain a patch for the keypoint, where the patch includes the plurality of pixels.

27. The device of claim 26, wherein the plurality of sparse projection vectors define a set of non-zero scaling coefficients, each non-zero scaling coefficient being associated with a corresponding pixel location within the patch.

28. The device of claim 27, wherein the descriptor is generated by combining a plurality of descriptor components, each descriptor component generated by:

identifying pixel locations based on the non-zero scaling coefficient locations for a first sparse projection vector;

multiplying a value of the pixel location from the patch with the corresponding non-zero scaling coefficient for the first sparse projection vector and add the resulting values together to obtain a first descriptor component.

29. The device of claim 28, wherein the processing circuit is further adapted to:

obtain additional descriptor components for the remaining plurality of sparse projection vectors to obtain additional descriptor components, wherein the first descriptor component and additional descriptor components are combined as a vector to obtain the keypoint descriptor.

30. The device of claim 24, wherein the patch has a dimension of m pixels by n pixels and is projected over the second plurality of scale levels s, then the keypoint descriptor is generated with fewer operations than the m*n*s dimensions of the patch.

31. A device, comprising:

means for obtaining a set of pre-generated sparse projection vectors over a first plurality of scale levels;

means for obtaining a scale space for an image, the scale space having a second plurality scale levels; and

means for generating a descriptor for a keypoint in the scale space based on a combination of the sparse projection vectors and sparsely sampled pixel information for a plurality of pixels across the second plurality of scale levels.

32. The device of claim 31, wherein the sparse projection vectors are generated independent of the image.

33. The device of claim 31, where each sparse projection vector is constrained to scales of a smoothening kernel for the image.

34. The device of claim 31, wherein each of the sparse projection vectors maximize or minimize an objective function.

35. The device of claim 34, wherein the objective function is maximization of an autocor.

36. The device of claim 31, wherein a sparse projection vector includes a majority of zero elements and a plurality of non-zero elements.

37. The device of claim 36, wherein the non-zero elements are obtained by a variance maximization procedure.

38. The device of claim 31, wherein the pixel information includes gradient information for each pixel within a patch associated the keypoint.

39. The device of claim 31, wherein the plurality of pixels are associated with a patch for the keypoint.

40. The device of claim 31, wherein the plurality of pixels are selected at pre-determined locations corresponding to non-zero coefficients for the sparse projection vectors.

41. The device of claim 31, further comprising:

means for obtaining a keypoint from the scale space for the image; and

means for obtaining a patch for the keypoint, where the patch includes the plurality of pixels.

42. The device of claim 41, wherein the plurality of sparse projection vectors define a set of non-zero scaling coefficients, each non-zero scaling coefficient being associated with a corresponding pixel location within the patch.

43. The device of claim 42, wherein the descriptor is generated by combining a plurality of descriptor components, each descriptor component generated by:

means for identifying pixel locations based on the non-zero scaling coefficient locations for a first sparse projection vector;

means for multiplying a value of the pixel location from the patch with the corresponding non-zero scaling coefficient for the first sparse projection vector and add the resulting values together to obtain a first descriptor component.

44. The device of claim 43, further comprising:

means for obtaining additional descriptor components for the remaining plurality of sparse projection vectors to obtain additional descriptor components, wherein the first descriptor component and additional descriptor components are combined as a vector to obtain the keypoint descriptor.

45. The device of claim 39, wherein the patch has a dimension of m pixels by n pixels and is projected over the second plurality of scale levels s, then the keypoint descriptor is generated with fewer operations than the m*n*s dimensions of the patch.

46. A non-transitory processor-readable storage medium comprising one or more instructions operational on a device, which when executed by a processing circuit, causes the processing circuit to:

obtain a set of pre-generated sparse projection vectors over a first plurality of scale spaces;

obtain a scale space for an image, the scale space having a second plurality scale levels; and

generate a descriptor for a keypoint in the scale space based on a combination of the sparse projection vectors and sparsely sampled pixel information for a plurality of pixels across the second plurality of scale levels.

47. The non-transitory processor-readable storage medium of claim 46, wherein the sparse projection vectors are generated independent of the image.

48. The non-transitory processor-readable storage medium of claim 46, where each sparse projection vector is constrained to scales of a smoothening kernel for the image.

49. The non-transitory processor-readable storage medium of claim 46, wherein each of the sparse projection vectors maximize or minimize an objective function.

50. The non-transitory processor-readable storage medium of claim 49, wherein the objective function is maximization of an autocorrelation matrix for pixel information across the first plurality of scale levels for a training set of images.

51. The non-transitory processor-readable storage medium of claim 46, wherein a sparse projection vector includes a majority of zero elements and a plurality of non-zero elements.

52. The non-transitory processor-readable storage medium of claim 51, wherein the non-zero elements are obtained by a variance maximization procedure.

53. The non-transitory processor-readable storage medium of claim 46, wherein the pixel information includes gradient information for each pixel within a patch associated the keypoint.

54. The non-transitory processor-readable storage medium of claim 46, wherein the plurality of pixels are associated with a patch for the keypoint.

55. The non-transitory processor-readable storage medium of claim 46, wherein the plurality of pixels are selected at pre-determined locations corresponding to non-zero coefficients for the sparse projection vectors.

56. The non-transitory processor-readable storage medium of claim 46, further comprising one or more instructions which when executed by the processing circuit, causes the processing circuit to:

obtain a keypoint from the scale space for the image; and

obtain a patch for the keypoint, where the patch includes the plurality of pixels.

57. The non-transitory processor-readable storage medium of claim 46, wherein the plurality of sparse projection vectors define a set of non-zero scaling coefficients, each non-zero scaling coefficient being associated with a corresponding pixel location within the patch.

58. The non-transitory processor-readable storage medium of claim 57, wherein the descriptor is generated by combining a plurality of descriptor components, each descriptor component generated by:

identifying pixel locations based on the non-zero scaling coefficient locations for a first sparse projection vector;

multiplying a value of the pixel location from the patch with the corresponding non-zero scaling coefficient for the first sparse projection vector and add the resulting values together to obtain a first descriptor component.

59. The non-transitory processor-readable storage medium of claim 58, further comprising one or more instructions which when executed by the processing circuit, causes the processing circuit to:

obtain additional descriptor components for the remaining plurality of sparse projection vectors to obtain additional descriptor components, wherein the first descriptor component and additional descriptor components are combined as a vector to obtain the keypoint descriptor.

60. The non-transitory processor-readable storage medium of claim 54, wherein the patch has a dimension of m pixels by n pixels and is projected over the second plurality of scale levels s, then the keypoint descriptor is generated with fewer operations than the m*n*s dimensions of the patch.