Optimized fast feature detection for vector processors

Patent metadata

Field	Value
Publication number	US-9652686-B2
Application number	US-201615345523-A
Country	US
Kind code	B2
Filing date	Nov 8, 2016
Priority date	Nov 3, 2014
Publication date	May 16, 2017
Grant date	May 16, 2017

Abstract

This invention enables effective corner detection of pixels of an image using the FAST algorithm using a vector SIMD processor. This invention loads an 8×8 pixel block that includes four 7×7 pixel blocks including the 16 peripheral pixels to be tested for each of four center pixels. This invention rearranges the 64 pixels of the 8×8 block to form a 16 element array for each center pixel preferably using a vector permutation instruction. This invention uses vector SIMD subtraction and compare and vector SIMD addition and compare to make the FAST algorithm comparisons. The N consecutive pixels determinations of the FAST algorithm are made from the results of plural shift and AND operations. The corresponding center pixel is marked a corner or not a corner dependent upon of the results of plural shift and AND operations.

First claim

What is claimed is:

1. A method of corner detection of pixels of an image comprising the steps of:
loading an 8×8 pixel block data of the image from memory into central processing unit data registers;
forming a 16 peripheral pixel data word for peripheral pixels corresponding to each of four center pixels in four 7×7 pixel blocks within the 8×8 pixel block;
for each of the four 16 peripheral pixel data words
determining for each of the 16 peripheral pixels whether a pixel value is greater than a corresponding center pixel value plus a predetermined threshold amount,
determining whether there are N consecutive pixels of the 16 peripheral pixels having a pixel value greater than the corresponding center pixel value plus the threshold amount,
marking the corresponding center pixel a corner pixel if there are N consecutive pixels of the 16 peripheral pixels having a pixel value greater than the corresponding center pixel value plus the threshold amount, where N is a predetermined constant,
determining for each of the 16 peripheral pixels whether a pixel value is less than a corresponding pixel value minus the predetermined threshold amount,
determining whether there are N consecutive pixels of the 16 peripheral pixels having a pixel value less than the corresponding pixel value plus the threshold amount,
marking the corresponding center pixel a corner pixel if there are N consecutive pixels of the 16 peripheral pixels having a pixel value less than a corresponding pixel value minus the threshold amount, and
marking the corresponding center pixel not a corner pixel if there are neither N consecutive pixels of the 16 peripheral pixels having a pixel value greater than the corresponding center pixel value plus the threshold amount nor N consecutive pixels of the 16 peripheral pixels having a pixel value less than a corresponding pixel value minus the threshold amount.

2. The method of claim 1 , wherein:
said step of determining for each of the 16 peripheral pixels whether a pixel value is greater than a corresponding center pixel value plus a predetermined threshold amount comprises the steps of:
performing a SIMD subtraction of the 16 peripheral pixel data word and a constant having the threshold amount in each SIMD slot,
performing a SIMD comparison of each difference of the SIMD subtraction and a first variable consisting of the corresponding center pixel value in each SIMD slot producing 16 one-bit comparison results.

3. The method of claim 2 , wherein:
said step of determining whether there are N consecutive pixels of the 16 peripheral pixels having a pixel value greater than the corresponding center pixel value plus the threshold amount comprises the steps of:
performing a plurality of SHIFT and AND operations on the 16 one-bit comparison results, and
determining whether a result of the Shift and AND operation is zero.

4. The method of claim 3 , wherein:
N is nine; and
said step of performing a plurality of SHIFT and AND operations performs
a first right shift by one bit and ANDing with the 16 one-bit comparison results forming a first intermediate result,
a second right shift by two bits and ANDing with the first intermediate result forming a second intermediate result,
a third right shift by one bit and ANDing the second intermediate result forming a third intermediate result and
a fourth right shift by one bit and ANDing the third intermediate result forming the shift and AND result.

5. The method of claim 3 , wherein:
N is twelve; and
said step of performing a plurality of SHIFT and AND operations performs
a first right shift by one bit and ANDing with the 16 one-bit comparison results forming a first intermediate result,
a second right shift by two bits and ANDing with the first intermediate result forming a second intermediate result,
a third right shift by one bit and ANDing the second intermediate result forming a third intermediate result and
a fourth right shift by four bits and ANDing the third intermediate result forming the shift and AND result.

6. The method of claim 1 , wherein:
said step of determining for each of the 16 peripheral pixels whether a pixel value is less than a corresponding center pixel value minus a predetermined threshold amount comprises the steps of:
performing a SIMD addition of the 16 peripheral pixel data word and a constant having the threshold amount in each SIMD slot,
performing a SIMD comparison of each difference of the SIMD addition and first variable consisting of the corresponding center pixel value in each SIMD slot producing 16 one-bit comparison results.

7. The method of claim 6 , wherein:
said step of determining whether there are N consecutive pixels of the 16 peripheral pixels having a pixel value less than the corresponding center pixel value minus the threshold amount comprises the steps of:
performing a plurality of SHIFT and AND operations on the 16 one-bit comparison results, and
determining whether a result of the SHIFT and AND operation is zero.

8. The method of claim 7 , wherein:
N is nine; and
said step of performing a plurality of SHIFT and AND operations performs
a first right shift by one bit and ANDing with the 16 one-bit comparison results forming a first intermediate result,
a second right shift by two bits and ANDing with the first intermediate result forming a second intermediate result,
a third right shift by one bit and ANDing the second intermediate result forming a third intermediate result and
a fourth right shift by one bit and ANDing the third intermediate result forming the shift and AND result.

9. The method of claim 7 , wherein:
N is twelve; and
said step of performing a plurality of SHIFT and AND operations performs
a first right shift by one bit and ANDing with the 16 one-bit comparison results forming a first intermediate result,
a second right shift by two bits and ANDing with the first intermediate result forming a second intermediate result,
a third right shift by one bit and ANDing the second intermediate result forming a third intermediate result and
a fourth right shift by four bits and ANDing the third intermediate result forming the shift and AND result.

10. The method of claim 1 , wherein:
said step of forming a 16 peripheral pixel data word for peripheral pixels corresponding to each of said four center pixels in four 7×7 pixel blocks within the 8×8 pixel block includes for each of said four center pixels
pre-calculating a control word specifying for each equal sized data portion of said corresponding 16 peripheral pixel data word a data location within said 8×8 pixel block data of the image in the data registers, and
executing a vector permutation instruction having a first instruction specified operand of said 16 peripheral pixel data word stored in the data registers, a second instruction specified operation of a corresponding pre-calculated control word and a destination forming said 16 peripheral pixel data word for peripheral pixels for said corresponding center pixel, wherein said vector permutation instruction stores data in each equal sized data portion of said 16 peripheral pixel data word for peripheral pixels for said corresponding center pixel data from a data location within said first instruction specified operand specified by a corresponding equal sized data portion in said second instruction specified source operand.

11. The method of claim 10 , further comprising the step of:
forming for each of said four center pixels said first variable consisting of the corresponding center pixel value in each SIMD slot by
pre-calculating a center pixel control word specifying for each equal sized data portion a data

Assignees

• Texas Instruments Inc

Inventors

• Sankaranarayanan Jayasree
• Mandal Dipan Kumar
• Viswanath Prashanth R

Classifications

• G06V10/457

  by analysing connectivity, e.g. edge linking, connected component analysis or slices · CPC title

• G06V10/955 Primary

  using specific electronic processors · CPC title

• G06V10/44

  Local feature extraction by analysis of parts of the pattern, e.g. by detecting edges, contours, loops, corners, strokes or intersections; Connectivity analysis, e.g. of connected components · CPC title

• G06K9/481

  Physics · mapped topic

• G06K9/4638 Primary

  Physics · mapped topic