Efficient descriptor extraction over multiple levels of an image scale space

• US 9,530,073 B2
• Filed: 04/19/2011
• Issued: 12/27/2016
• Est. Priority Date: 04/20/2010
• Status: Expired due to Fees

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Hamsici, Onur C., Hong, John H., Reznik, Yuriy, Vaddadi, Sundeep, Lee, Chong Uk.
• Primary Examiner(s): Thirugnanam, Gandhi
• Application Number:
  US13/090,180
• Publication Number:
  US 20110255781A1
• Time in Patent Office: 2,079 Days
• Field of Search: 382/170, 382/201
• US Class Current: 1/1
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A local feature descriptor for a point in an image is generated over multiple levels of an image scale space. The image is gradually smoothened to obtain a plurality of scale spaces. A point may be identified as the point of interest within a first scale space from the plurality of scale spaces. A plurality of image derivatives is obtained for each of the plurality of scale spaces. A plurality of orientation maps is obtained (from the plurality of image derivatives) for each scale space in the plurality of scale spaces. Each of the plurality of orientation maps is then smoothened (e.g., convolved) to obtain a corresponding plurality of smoothed orientation maps. Therefore, a local feature descriptor for the point may be generated by sparsely sampling a plurality of smoothed orientation maps corresponding to two or more scale spaces from the plurality of scale spaces.

Claims

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

identifying a point within a first scale space from a plurality of scale spaces for an image;

obtaining a plurality of image derivatives for each of the plurality of scale spaces;

obtaining a plurality of orientation maps for each scale space in the plurality of scale spaces, where each of the plurality of orientation maps is obtained from non-negative values of a corresponding image derivative;

for each scale space in the plurality of scale spaces, smoothing each of the plurality of orientation maps to obtain a corresponding plurality of smoothed orientation maps; and

sparsely sampling a plurality of smoothed orientation maps corresponding to two or more scale spaces from the plurality of scale spaces to generate a local feature descriptor for the point

wherein each of the smoothed orientation maps that is sparsely sampled is derived using a different orientation map than each of the other smoothed orientation maps that is sparsely sampled.

2. The method of claim 1, further comprising gradually smoothing the image to obtain the plurality of scale spaces.

3. The method of claim 1, wherein said smoothing comprises:

smoothing each of the plurality of orientation maps for the first scale space by a first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps; and

smoothing each of the plurality of orientation maps for a second scale space in the plurality of scale spaces by the first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps,

wherein the second scale space is different than the first scale space.

4. The method of claim 1, wherein the point is a sample point from a subset of locations within the plurality of scale spaces, and

wherein the subset of locations is selected based on a pattern that represents an object to be detected.

5. The method of claim 1, wherein the point is a sample point from a subset of locations within the plurality of scale spaces, and

wherein the subset of locations is selected based on identified keypoints within the image, wherein a keypoint is a point that has been identified as being robust to changes in imaging conditions.

6. The method of claim 1, wherein the two or more scale spaces include the first scale space and one or more additional scale spaces of lower resolution than the first scale space.

7. The method of claim 1, wherein the local feature descriptor has a kernel pooling configuration defined by spatial pooling of sample points distributed over a center of the point.

8. The method of claim 1, wherein sparsely sampling a plurality of smoothed orientation maps includes

sampling a first plurality of points on a first smoothed orientation map, the first plurality of points arranged in a first ring concentric with a location of the point;

and

sampling a second plurality of points on a second smoothed orientation map, the second plurality of points arranged in a second ring concentric with the location of the point, the second smoothed orientation map corresponding to a second scale space of lower resolution than the first scale space.

9. The method of claim 8, wherein sparsely sampling a plurality of smoothed orientation maps further includes

sampling a third plurality of points on a third smoothed orientation map, the third plurality of points arranged in a third ring concentric with the location of the point, the third smoothed orientation map corresponding to a third scale space of lower resolution than the first scale space.

10. The method of claim 9, wherein the second ring has a second radius greater than a first radius for the first ring, and the third ring has a third radius greater than the second radius for the second ring.

11. The method of claim 1, wherein the plurality of orientation maps for each scale space include orientation maps for a plurality of different orientations.

12. The method of claim 1, further comprising:

building a plurality of histograms of oriented gradients from the sparse sampling of the plurality of smoothed orientation maps, wherein the local feature descriptor comprises the plurality of histograms.

13. The method of claim 1, wherein said method includes, subsequent to said identifying and prior to said sparsely sampling, selecting a scale space to be among the two or more scale spaces, based on a smoothing coefficient of the scale space.

29. The method of claim 1, wherein each orientation map in the plurality of orientation maps has only one corresponding smoothed orientation map in the plurality of smoothed orientation maps.

30. The method of claim 1, wherein said sparsely sampling comprises:

sparsely sampling a smoothed orientation map that is derived from the first scale space; and

sparsely sampling a smoothed orientation map that is derived from a scale space in the plurality of scale spaces that is different than the first scale space.

14. An image processing device, comprising:

an input interface adapted to obtain an image;

a storage device to store local feature descriptors for one or more images;

a hardware processing circuit coupled to the input interface and the storage device, the hardware processing circuit adapted to;

identify a point within a first scale space from a plurality of scale spaces for an image;

obtain a plurality of image derivatives for each of the plurality of scale spaces;

obtain a plurality of orientation maps for each scale space in the plurality of scale spaces, where each of the plurality of orientation maps is obtained from non-negative values of a corresponding image derivative;

for each scale space in the plurality of scale spaces, smooth each of the plurality of orientation maps to obtain a corresponding plurality of smoothed orientation maps; and

sparsely sample a plurality of smoothed orientation maps corresponding to two or more scale spaces from the plurality of scale spaces to generate a local feature descriptor for the point,

wherein each of the smoothed orientation maps that is sparsely sampled is derived using a different orientation map than each of the other smoothed orientation maps that is sparsely sampled.

15. The device of claim 14, wherein the two or more scale spaces include the first scale space and one or more additional scale spaces of lower resolution than the first scale space.

16. The device of claim 14, wherein the processing circuit is further adapted to gradually smooth the image to obtain the plurality of scale spaces.

17. The device of claim 14, wherein the local feature descriptor has a kernel pooling configuration defined by spatial pooling of sample points distributed over a center on the point.

18. The device of claim 14, wherein sparsely sampling a plurality of smoothed orientation maps includes

sampling a first plurality of points on a first smoothed orientation map, the first plurality of points arranged in a first ring concentric with a location of the point;

and

sampling a second plurality of points on a second smoothed orientation map, the second plurality of points arranged in a second ring concentric with the location of the point, the second smoothed orientation map corresponding to a second scale space of lower resolution than the first scale space.

19. The device of claim 14, wherein the processing circuit is further adapted to:

build a plurality of histograms of oriented gradients from the sparse sampling of the plurality of smoothed orientation maps, wherein the local feature descriptor comprises the plurality of histograms.

20. The device of claim 14, wherein said hardware processing circuit is adapted to select, subsequent to said identifying and prior to said sparsely sampling, a scale space to be among the two or more scale spaces, based on a smoothing coefficient of the scale space.

32. The device of claim 14, wherein said smoothing comprises:

smoothing each of the plurality of orientation maps for the first scale space by a first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps; and

smoothing each of the plurality of orientation maps for a second scale space in the plurality of scale spaces by the first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps,

wherein the second scale space is different than the first scale space.

33. The device of claim 14, wherein said sparsely sampling comprises:

sparsely sampling a smoothed orientation map that is derived from the first scale space; and

sparsely sampling a smoothed orientation map that is derived from a scale space in the plurality of scale spaces that is different than the first scale space.

21. An image processing device, comprising:

means for identifying a point within a first scale space from a plurality of scale spaces for an image;

means for obtaining a plurality of image derivatives for each of the plurality of scale spaces;

means for obtaining a plurality of orientation maps for each scale space in the plurality of scale spaces, where each of the plurality of orientation maps is obtained from non-negative values of a corresponding image derivative;

means for smoothing, for each scale space in the plurality of scale spaces, each of the plurality of orientation maps to obtain a corresponding plurality of smoothed orientation maps; and

means for sparsely sampling a plurality of smoothed orientation maps corresponding to two or more scale spaces from the plurality of scale spaces to generate a local feature descriptor for the point,

wherein each of the smoothed orientation maps that is sparsely sampled is derived using a different orientation map than each of the other smoothed orientation maps that is sparsely sampled.

22. The device of claim 21, further comprising means for gradually smoothing the image to obtain the plurality of scale spaces.

23. The device of claim 21, wherein the two or more scale spaces include the first scale space and one or more additional scale spaces of lower resolution than the first scale space.

24. The device of claim 21, wherein the local feature descriptor has a kernel pooling configuration defined by spatial pooling of sample points distributed over a center on the point.

25. The device of claim 21, wherein means for sparsely sampling a plurality of smoothed orientation maps includes

means for sampling a first plurality of points on a first smoothed orientation map, the first plurality of points arranged in a first ring concentric with a location of the point;

and

means for sampling a second plurality of points on a second smoothed orientation map, the second plurality of points arranged in a second ring concentric with the location of the point, the second smoothed orientation map corresponding to a second scale space of lower resolution than the first scale space.

26. The device of claim 21, further comprising:

means for building a plurality of histograms of oriented gradients from the sparse sampling of the plurality of smoothed orientation maps, wherein the local feature descriptor comprises the plurality of histograms.

34. The device of claim 21, wherein said smoothing comprises:

smoothing each of the plurality of orientation maps for the first scale space by a first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps; and

smoothing each of the plurality of orientation maps for a second scale space in the plurality of scale spaces by the first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps,

wherein the second scale space is different than the first scale space.

35. The device of claim 21, wherein said device includes means for selecting, subsequent to said identifying and prior to said sparsely sampling, a scale space to be among the two or more scale spaces, based on a smoothing coefficient of the scale space.

36. The device of claim 21, wherein said sparsely sampling comprises:

sparsely sampling a smoothed orientation map that is derived from the first scale space; and

sparsely sampling a smoothed orientation map that is derived from a scale space in the plurality of scale spaces that is different than the first scale space.

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

identify a point within a first scale space from a plurality of scale spaces for an image;

obtain a plurality of image derivatives for each of the plurality of scale spaces;

obtain a plurality of orientation maps for each scale space in the plurality of scale spaces, where each of the plurality of orientation maps is obtained from non-negative values of a corresponding image derivative;

for each scale space in the plurality of scale spaces, smooth each of the plurality of orientation maps to obtain a corresponding plurality of smoothed orientation maps; and

sparsely sample a plurality of smoothed orientation maps corresponding to two or more scale spaces from the plurality of scale spaces to generate a local feature descriptor for the point,

wherein each of the smoothed orientation maps that is sparsely sampled is derived using a different orientation map than each of the other smoothed orientation maps that is sparsely sampled.

28. The non-transitory processor-readable medium of claim 27, wherein the two or more scale spaces include the first scale space and one or more additional scale spaces of lower resolution than the first scale space.

31. The non-transitory processor-readable medium of claim 27, wherein said one or more instructions, when executed by the processing circuit, further causes the processing circuit to gradually smooth the image to obtain the plurality of scale spaces.

37. The non-transitory processor-readable medium of claim 27, wherein said smoothing comprises:

smoothing each of the plurality of orientation maps for the first scale space by a first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps; and

smoothing each of the plurality of orientation maps for a second scale space in the plurality of scale spaces by the first smoothing coefficient to generate the corresponding plurality of smoothed orientation maps,

wherein the second scale space is different than the first scale space.