METHOD AND APPARATUS FOR EXTRACTING FEATURE POINTS FROM DIGITAL IMAGE

• US 20090052780A1
• Filed: 08/22/2008
• Published: 02/26/2009
• 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, Chung, Hee-jin, Choi, Tai-ho, Kim, Geon-ho
• Granted Patent: US 8,306,366 B2
• Time in Patent Office: Days
• US Class Current: 382/190
• 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.

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 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.

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

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

performing convolution operations on all pixels of the original line by using the line added with the virtual pixels and by using the lines that are shifted by an offset of a blur kernel after the line added with the virtual pixels is multiplied by the blur kernel; and

correcting results of the convolution operations on pixels including one or more of the virtual pixels.

6. 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.

7. 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.

8. 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.

9. The method as claimed in claim 8, 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.

10. 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.

11. 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.

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

13. 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.

14. The apparatus as claimed in claim 13, 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.

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

16. The apparatus as claimed in claim 14, wherein the plurality of processors perform first convolution operations on allocated lines of the original image in a transverse direction and perform second convolution operations in the transverse direction on allocated 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°

.

17. The apparatus as claimed in claim 14, wherein:

the plurality of processors add a predetermined number of virtual pixels to both borders of an original line on which the blurring operation is to be performed and perform convolution operations on all pixels of the original line by using the line added with the virtual pixels and by using lines that are shifted by an offset of a blur kernel after the line added with the virtual pixels is multiplied by the blur kernel.

18. The apparatus as claimed in claim 17, wherein the at least one processor corrects results of the convolution operations on pixels including one or more of the virtual pixels.

19. The apparatus as claimed in claim 13, wherein the plurality of processors performs the blurring operations in parallel.

20. The apparatus as claimed in claim 13, wherein the plurality of processors calculates the DoGs in parallel.

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

22. 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 one or more image regions of the digital image blurred by levels into a plurality of regions to be allocated to a plurality of processors of the multiprocessor system;

calculating, by the plurality of processors, differences of Gaussian (DoGs); and

generating feature point data according to the calculated DoGs.

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

selecting feature points according to the calculated DoGs;

dividing the digital image into a plurality of regions to be allocated to the 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.

24. The method as claimed in claim 23, wherein the selecting of the feature points comprises collating the calculated DoGs to select the feature points and selecting a DoG as a feature point if the DoG is larger than a predetermined threshold.

25. A computer-readable medium encoded with the method of claim 22 and implemented by a computer.