Method and apparatus for extracting feature points from digital image

• US 8,306,366 B2
• Filed: 08/22/2008
• Issued: 11/06/2012
• Est. Priority Date: 08/23/2007
• Status: Active Grant

• Current Assignee: Samsung Electronics Co. Ltd.
• Original Assignee: Samsung Electronics Co. Ltd.
• Inventors: Kwon, Bom-jun, Choi, Tai-ho, Chung, Hee-jin, Kim, Geon-ho
• Primary Examiner(s): Hung, Yubin
• Application Number:
  US12/196,720
• Publication Number:
  US 20090052780A1
• Time in Patent Office: 1,537 Days
• Field of Search: 382/190, 382/260, 382/264, 382/304, 700/2, 700/4
• US Class Current: 382/304
• CPC Class Codes: G06T 5/20 using local operators
• CPC Class Codes: G06T 5/73 Deblurring; Sharpening
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/94 Hardware or software architectures specially adapted for image or video understanding

Abstract

An apparatus and method for extracting feature points from an image in a multiprocessor system having a plurality of processors, the method including: dividing an original image into a plurality of regions so as to be allocated to a plurality of processors of the multiprocessor system; performing, by the plurality of processors, blurring operations by levels; dividing the images blurred by levels into a plurality of regions to be allocated to the processors and calculating, by the plurality of processors, differences of Gaussian (DoGs); and generating feature point data according to the calculated DoGs. Because a plurality of processors performs the operations of the method, the total time to extract the feature points from the image is significantly reduced.

Claims

1. A method of extracting feature points from a digital image in a multiprocessor system using a scale invariant feature transform (SIFT) technique, the method comprising:

dividing an original image into a plurality of regions so as to be allocated to a plurality of processors of the multiprocessor system;

performing, by the plurality of processors, blurring operations by levels;

dividing the images blurred by levels into a plurality of regions to be allocated to the processors and calculating, by the plurality of processors, differences of Gaussian (DoGs); and

generating feature point data according to the calculated DoGs, wherein;

the performing of the blurring operations comprises;

adding a predetermined number of virtual pixels to both borders of an original line to produce a revised line on which the blurring operation is to be performed;

performing convolution operations on all pixels of the revised line using a blur kernel; and

correcting a result value obtained from one of the convolution operations in which one or more of the virtual pixels is used for calculating the result value, and the correcting the result value comprises;

generating a correction weight which indicates a ratio of a sum of kernel values applied to pixels other than the virtual pixels in the one of the convolution operations to the sum of all kernel values; and

dividing the result value by the generated correction weight.

2. The method as claimed in claim 1, wherein the generating of the feature point data comprises:

selecting feature points according to the DoGs;

dividing the original image into a plurality of regions to be allocated to the plurality of processors to calculate gradient values for pixels of allocated regions;

allocating the selected feature points to the processors to calculate descriptors for the allocated feature points according to the gradient values; and

generating the feature point data according to coordinates of the selected feature points and the calculated descriptors.

3. The method as claimed in claim 2, wherein the allocating of the selected feature points comprises allocating the selected feature points to the processors according to a round-robin scheme.

4. The method as claimed in claim 2, wherein the selecting of the feature points comprises collating the calculated DoGs to select the feature points according to a predetermined standard.

5. The method as claimed in claim 4, wherein the selecting of the feature points further comprises selecting a DoG as a feature point if the DoG is larger than a predetermined threshold.

6. The method as claimed in claim 2, wherein the allocating of the selected feature points comprises:

collating the calculated gradient values to generate a gradient map; and

calculating the descriptors according to the gradient map.

7. The method as claimed in claim 1, wherein the performing of the blurring operations comprises:

allocating lines of the original image to the plurality of processors to perform first convolution operations on the lines in a transverse direction;

collating results of the first convolution operations into a collated image and rotating the collated image by 90′

;

allocating lines of the collated image to the plurality of processors; and

performing second convolution operations on the lines in the transverse direction.

8. The method as claimed in claim 1, wherein the performing of the blurring operations comprises performing, by the plurality of processors, the blurring operations in parallel.

9. The method as claimed in claim 1, wherein the dividing of the blurred images comprises calculating, by the plurality of processors, the DoGs in parallel.

10. The method as claimed in claim 1, wherein:

the dividing of the blurred images comprises dividing the blurred images into N number of regions; and

the multiprocessor system includes N number of processors.

11. A non-transitory computer-readable medium encoded with the method of claim 1 and implemented by a computer.

12. A multiprocessor apparatus to extract feature points from a digital image according to a scale invariant feature transform (SIFT) technique, the apparatus comprising:

a plurality of processors to perform blurring operations by levels on corresponding regions of the digital image and to calculate differences of Gaussian (DoGs) on corresponding regions of the images blurred by levels; and

at least one processor to generate feature point data according to the calculated DoGs wherein;

the plurality of processors add a predetermined number of virtual pixels to both borders of an original line to produce a revise line on which the blurring operation is to be performed and perform convolution operations on all pixels of the revised line using a blur kernel, and

at least one processor corrects a result value obtained from one of the convolution operations in which one or more of the virtual pixels is used for calculating the result value by generating a correction weight which indicates a ratio of a sum of kernel values applied to pixels other than the virtual pixels used in the one of the convolution operations to the sum of all kernel values and dividing the result value by the generated correction weight.

13. The apparatus as claimed in claim 12, wherein:

the plurality of processors calculate gradient values for pixels of corresponding regions of the digital image and are allocated with feature points selected by the at least one processor to calculate descriptors according to the calculated gradient values; and

the at least one processor selects the feature points according to the calculated DoGs and generates the feature point data by using coordinates of the selected feature points and the calculated descriptors.

14. The apparatus as claimed in claim 13, wherein the at least one processor allocates the selected feature points to the plurality of processors according to a round-robin scheme.

15. The apparatus as claimed in claim 13, wherein the plurality of processors perform first convolution operations on lines of the original image in a transverse direction and perform second convolution operations in the transverse direction on lines of an image that is generated by collating results of the first convolution operations into a collated image and rotating the collated image by 90°

.

16. The apparatus as claimed in claim 13, wherein the at least one processor collates the DoGs and selects a DoG therefrom as a feature point if the DoG is larger than a predetermined threshold.

17. The apparatus as claimed in claim 12, wherein the plurality of processors perform the blurring operations in parallel.

18. The apparatus as claimed in claim 12, wherein the plurality of processors calculate the DoGs in parallel.