SYSTEM AND METHOD FOR SIFT IMPLEMENTATION AND OPTIMIZATION

• US 20100169576A1
• Filed: 12/31/2008
• Published: 07/01/2010
• Est. Priority Date: 12/31/2008
• Status: Active Grant

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Chen, Yurong
• Granted Patent: US 8,441,489 B2
• Time in Patent Office: Days
• US Class Current: 711/122
• CPC Class Codes: G06F 12/0897 with two or more cache hierarchy levels with multilevel cache hierarchies G06F12/0811
• CPC Class Codes: G06V 10/462 Salient features, e.g. scale invariant feature transforms [SIFT]
• CPC Class Codes: G06V 10/955 using specific electronic processors

Abstract

A method is to implement a Scale Invariant Feature Transform algorithm in a shared memory multiprocessing system. The method comprises building differences of Gaussian (DoG) images for an input image, detecting keypoints in the DoG images; assigning orientations to the keypoints and computing keypoints descriptors and performing matrix operations. In the method, building differences of Gaussian (DoG) images for an input image and detecting keypoints in the DoG images are executed for all scales of the input image in parallel. And, orientation assignment and keypoints descriptions computation are executed for all octaves of the input image in paralle.

Claims

1. A system, comprising:

a memory;

two or more cores that shares the memory, wherein at least two cores each perform at least a thread of a scale invariant feature transform algorithm in parallel.

2. The system of claim 1, further comprising:

a set of first level cache, each core being coupled to the memory by a first level cache

3. The system of claim 2, further comprising:

a second level cache that couples each first level cache to the memory.

4. The system of claim 1, wherein two or more cores are to build Gaussian scale space for all scales of an input image in parallel.

5. The system of claim 1, wherein each thread operates on its local list, and the local lists are merged at an end of a parallel region.

6. The system of claim 1, wherein buffer manipulation for each thread is conducted outside a parallel region.

7. The system of claim 4, wherein two or more cores each perform at least a thread to detect a keypoint in a difference of Gaussian scale space in parallel.

8. The system of claim 7, wherein two or more cores each perform at least a thread to generate a feature factor based on the keypoint for all octaves of the input image in parallel.

9. A method to implement a scale invariant feature transform algorithm, comprising:

building difference of Gaussian images for all scales of an input image in parallel;

detecting keypoints with a local extrema in the difference of Gaussian images for all scales in parallel;

assigning orientations to the keypoints; and

computing feature descriptors for the keypoints.

10. The method of claim 9, wherein the data of the input image is accessed in an order of rows.

11. The method of claim 9, further comprising:

down-scaling the feature descriptors for all octaves of the input images to obtain SIFT features.

12. The method of claim 9, wherein building difference of Gaussian images comprises a set of threads that each operate on a local list, the local lists of the set of threads are merged at an end of a parallel region.

13. The method of claim 9, wherein a size of a feature descriptor is adjusted based on a size of a cache line of data.

14. The method of claim 9, wherein the threads associated with assigning orientations to the keypoints are performed in parallel.

15. The method of claim 9, further comprising dynamically scheduling the keypoints to the threads in computing feature descriptors.

16. A machine readable medium comprising a plurality of instructions that in response to being executed result in a computing device

building difference of Gaussian images for all scales of an input image in parallel;

detecting keypoints with a local extrema in the difference of Gaussian images for all scales in parallel;

assigning orientations to the keypoints; and

computing feature descriptors for the keypoints.

17. The machine readable medium of claim 16, further comprising a plurality of instructions that in response to being executed result in a computing device

down-scaling the feature descriptors for all octaves of the input images to obtain SIFT features.

18. The machine readable medium of claim 16, wherein the data of the input image is accessed in an order of rows.

19. The machine readable medium of claim 16, wherein building difference of Gaussian images comprises a set of threads that each operate on a local list, the local lists of the set of threads are merged at an end of a parallel region.

20. The machine readable medium of claim 16, wherein a size of a feature descriptor is adjusted based on a size of a cache line of data.

21. The machine readable medium of claim 16, wherein, wherein the threads associated with assigning orientations to the keypoints are performed in parallel.

22. The machine readable medium of claim 16, further comprising a plurality of instructions that in response to being executed result in a computing device

dynamically scheduling the keypoints to the threads in computing feature descriptors.