# US 2010/0169576 A1 · System and method for sift implementation and optimization

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2010/0169576 A1
- Document ID: US20100169576A1
- Status: Published application
- Kind: A1
- Application number: 12/347,881
- Filed: 2008-12-31
- Published: 2010-07-01
- Earliest claimed: 2008-12-31
- Assignees: Intel Corporation
- Inventors: Yurong Chen
- Web page: https://patentgrep.com/patent/US20100169576A1

## CPC

- G06F 12/0897: with two or more cache hierarchy levels (with multilevel cache hierarchies G06F12/0811)
- G06V 10/462: {Salient features, e.g. scale invariant feature transforms [SIFT]}
- G06V 10/955: {using specific electronic processors}
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

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

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

### Claim 2 (depends on 1)

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

### Claim 3 (depends on 2)

The system of claim 2, further comprising:
a second level cache that couples each first level cache to the memory.

### Claim 4 (depends on 1)

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.

### Claim 5 (depends on 1)

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.

### Claim 6 (depends on 1)

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

### Claim 7 (depends on 4)

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.

### Claim 8 (depends on 7)

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.

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

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 9)

The method of claim 9, further comprising:
down-scaling the feature descriptors for all octaves of the input images to obtain SIFT features.

### Claim 12 (depends on 9)

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.

### Claim 13 (depends on 9)

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

### Claim 14 (depends on 9)

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

### Claim 15 (depends on 9)

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

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

### Claim 17 (depends on 16)

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.

### Claim 18 (depends on 16)

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

### Claim 19 (depends on 16)

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.

### Claim 20 (depends on 16)

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.

### Claim 21 (depends on 16)

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

### Claim 22 (depends on 16)

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.
