Method and apparatus for identifying scale invariant features in an image and use of same for locating an object in an image

• US 6,711,293 B1
• Filed: 03/06/2000
• Issued: 03/23/2004
• Est. Priority Date: 03/08/1999
• Status: Expired due to Term

• Current Assignee: British Columbia Cancer Agency Branch (Province of British Columbia)
• Original Assignee: University of British Columbia
• Inventors: Lowe, David G.
• Primary Examiner(s): Boudreau, Leo
• Assistant Examiner(s): Lu, Tom Y.
• Application Number:
  US09/519,893
• Time in Patent Office: 1,478 Days
• Field of Search: 382/130, 382/236, 382/219, 382/220
• US Class Current: 382/219
• CPC Class Codes: G06T 7/73 using feature-based methods
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]

Abstract

A method and apparatus for identifying scale invariant features in an image and a further method and apparatus for using such scale invariant features to locate an object in an image are disclosed. The method and apparatus for identifying scale invariant features may involve the use of a processor circuit for producing a plurality of component subregion descriptors for each subregion of a pixel region about pixel amplitude extrema in a plurality of difference images produced from the image. This may involve producing a plurality of difference images by blurring an initial image to produce a blurred image and by subtracting the blurred image from the initial image to produce the difference image. For each difference image, pixel amplitude extrema are located and a corresponding pixel region is defined about each pixel amplitude extremum. Each pixel region is divided into subregions and a plurality of component subregion descriptors are produced for each subregion. These component subregion descriptors are correlated with component subregion descriptors of an image under consideration and an object is indicated as being detected when a sufficient number of component subregion descriptors (scale invariant features) define an aggregate correlation exceeding a threshold correlation with component subregion descriptors (scale invariant features) associated with the object.

Claims

1. A method of identifying scale invariant features in an image defined by a plurality of pixels, the method comprising:

locating pixel amplitude extrema in a plurality of difference images produced from said image by;

comparing the amplitude of each pixel in an image under consideration with the amplitudes of pixels in an area about said each pixel in said image under consideration to identify local maximal and minimal amplitude pixels;

comparing the amplitudes of said local maximal and minimal amplitude pixels with the amplitudes of pixels in a predecessor image to the image under consideration to identify possible maximal and minimal amplitude pixels and

comparing the amplitudes of said possible maximal and minimal amplitude pixels with the amplitudes of pixels in a successor image to the image under consideration to identify actual maximal and minimal amplitude pixels; and

producing a plurality of component subregion descriptors for each subregion of a pixel region about said pixel amplitude extrema in said plurality of difference images produced from said image.

2. The method claimed in claim 1 further comprising producing said difference images.

3. The method claimed in claim 2 wherein producing a difference image comprises blurring an initial image to produce a blurred image and subtracting said blurred image from said initial image to produce a difference image.

4. The method claimed in claim 3 wherein producing said difference images comprises successively blurring and subtracting as recited in claim 3 where said initial image used in a successive blurring function includes a blurred image produced in a predecessor blurring function.

5. The method claimed in claim 1 further comprising producing a pixel gradient vector for each pixel in each difference image.

6. The method claimed in claim 5 further comprising associating vector orientations with respective actual maximal and minimal amplitude pixels associated with each difference image.

7. The method claimed in claim 6 wherein producing a plurality of component subregion descriptors comprises producing subregion descriptors for each respective subregion in response to pixel gradient vectors of pixels within said each respective subregion.

8. The method claimed in claim 7 wherein producing each of said subregion descriptors comprises determining the number of pixel vectors at orientations within a predefined range of orientations in said subregion.

9. The method claimed in claim 7 wherein producing a plurality of subregion descriptors comprises associating with each of said descriptors a plurality of orientation ranges and determining the number of pixel vectors at orientations within respective orientation ranges, for each subregion.

20. A computer readable medium comprising codes for directing a processor circuit to execute the method of claim 1.

10. An apparatus for identifying scale invariant features in an image defined by a plurality of pixels, the apparatus comprising a processor circuit configured to:

locate said pixel amplitude extrema in difference images by;

comparing the amplitude of each pixel in an image under consideration, with the amplitudes of pixels in an area about said each pixel in said image under consideration to identify local maximal and minimal amplitude pixels;

comparing the amplitudes of said local maximal and minimal amplitude pixels with the amplitudes of pixels in a predecessor image to the image under consideration to identify possible maximal and minimal amplitude pixels;

comparing the amplitudes of said possible maximal and minimal amplitude pixels with the amplitudes of pixels in a successor image to the image under consideration to identify actual maximal and minimal amplitude pixels; and

produce a plurality of component subregion descriptors for each subregion of a pixel region about pixel amplitude extrema in said plurality of difference images.

11. The apparatus claimed in claim 10 wherein said processor circuit is configured to produce said difference images.

12. The apparatus claimed in claim 11 wherein said processor circuit is configured to blur an initial image to produce a blurred image and to subtract said blurred image from said initial image to produce a difference image.

13. The apparatus claimed in claim 12 wherein said processor circuit is configured to successively blur and subtract as recited in claim 12 and is configured to use a blurred image produced in a predecessor blurring function as said initial image, in a successive blurring function.

14. The apparatus claimed in claim 10 wherein said processor circuit is configured to produce a pixel gradient vector for each pixel in each difference image.

15. The apparatus claimed in claim 14 wherein said processor circuit is configured to associate vector orientations with respective actual maximal and minimal amplitude pixels associated with each difference image.

16. The apparatus claimed in claim 15 wherein said processor circuit is configured to produce subregion descriptors for each respective subregion in response to pixel gradient vectors of pixels within said each respective subregion.

17. The apparatus claimed in claim 16 wherein said processor circuit is configured to determine the number of pixel vectors at orientations within a predefined range of orientations in said subregion.

18. The apparatus claimed in claim 16 wherein said processor circuit is configured to associate with each of said descriptors a plurality of orientation ranges and to determine the number of pixel vectors at orientations within respective orientation ranges, for each subregion.

19. An apparatus for identifying scale invariant features in an image defined by a plurality of pixels, the apparatus comprising:

means for locating pixel amplitude extrema in a plurality of difference images produced from said image, said means for locating comprising;

means for comparing the amplitude of each pixel in an image under consideration, with the amplitudes of pixels in an area about said each pixel in said image under consideration to identify local maximal and minimal amplitude pixels;

means for comparing the amplitudes of said local maximal and minimal amplitude pixels with the amplitudes of pixels in a predecessor image to the image under consideration to identify possible maximal and minimal amplitude pixels and

means for comparing the amplitudes of said possible maximal and minimal amplitude pixels with the amplitudes of pixels in a successor image to the image under consideration to identify actual maximal and minimal amplitude pixels; and

means for producing a plurality of component subregion descriptors for each subregion of a pixel region about said pixel amplitude extrema in said plurality of difference images.