Efficient SIMD implementation of 3x3 non maxima suppression of sparse 2D image feature points

• US 9,984,305 B2
• Filed: 07/07/2016
• Issued: 05/29/2018
• Est. Priority Date: 04/19/2016
• Status: Active Grant

• Current Assignee: Texas Instruments, Inc.
• Original Assignee: Texas Instruments, Inc.
• Inventors: Poddar, Deepak Kumar, Swami, Pramod Kumar, Viswanath, Prashanth
• Primary Examiner(s): Carter, Aaron W
• Application Number:
  US15/203,973
• Publication Number:
  US 20170300773A1
• Time in Patent Office: 691 Days
• Field of Search: 382201, 382118, 382218, 1 1, 250306, 250307, 250396 R, 3482086, 348 79, 348135, 702 81, 702 84, 702182
• 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

This invention transforms a list of feature points in raster scan order into a list of maxima suppressed feature points. A working buffer has two more entries than the width of the original image. Each entry is assigned to an x coordinate of the original image. Each entry stores a combined y coordinate and reliability score for each feature point in the original list. This process involves a forward scan and a backward scan. For each original feature point its x coordinate defines the location within the working buffer where neighbor feature points would be stored if they exist. The working buffer initial data and the y coordinates assure a non suppress comparison result if the potential neighbors are not actual neighbors. For actual neighbor data, the y coordinates match and the comparison result depends solely upon the relative reliability scores.

Claims

1. A tangible, non-transitory, and non-volatile computer readable media storing instructions for controlling a computer to transform a list of feature points of an image into a list of maxima suppressed feature points of the image, wherein the instructions, when executed by a processor of the computer, cause the computer to:

receive an original list of feature points including x and y coordinates and a reliability score of the feature point determination for each feature point, the feature points of the original list sorted in image raster scan order;

initialize a working buffer having a number of entries equal to a width of the image, each entry capable of storing a combined y coordinate and reliability score of a feature point of the original list;

scan the original list in a forward direction from a first feature point to a final feature point, wherein scanning the original list in the forward direction includes, for each feature point;

selecting the feature point as a current feature point;

comparing a combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one less than an x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential left neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential top left neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential top neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential top right neighbor of the current feature point; and

storing the combined y coordinate and reliability score of the current feature point in an entry within the working buffer corresponding to the x coordinate of the current feature point;

re-initializing the working buffer;

scanning the original list in a backward direction from a final feature point to a first feature point, wherein scanning the original list in the backward direction includes, for each feature point;

selecting the feature point as a current feature point;

comparing a combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential right neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential bottom right neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential bottom neighbor of the current feature point;

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate incremented by 1 and reliability score of an entry of the working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point and determining whether to suppress the current feature point dependent upon results of the comparison for a potential bottom left neighbor of the current feature point; and

storing the combined y coordinate and reliability score of the current feature point in an entry within the working buffer corresponding to the x coordinate of the current feature point; and

forming a list of maxima suppressed feature points of the image by including feature points from the original list not determined to be suppressed in response to any of the comparison steps from the scanning of the original list in the forward direction and in the backward direction.

2. The tangible, non-transitory, and non-volatile computer readable storage media of claim 1, wherein:

initializing the working buffer and re-initializing the working buffer stores data in each entry of the working buffer, and wherein any comparison with the initialized or re-initialized data produces a do not suppress result.

3. The tangible, non-transitory, and non-volatile computer readable media of claim 1, wherein:

the working buffer includes an additional entry prior to a first x coordinate in the image, and seeking an entry of the working buffer having a location corresponding to an x coordinate one less than the first x coordinate of the image does not fall out of range of the working buffer.

4. The tangible, non-transitory, and non-volatile computer readable media of claim 1, wherein:

the working buffer includes an additional entry following a final x coordinate in the image, and seeking an entry of the working buffer having a location corresponding to an x coordinate one more than the final x coordinate of the image does not fall out of range of the working buffer.

5. The tangible, non-transitory, and non-volatile computer readable media of claim 1, wherein the instructions, when executed by a processor of the computer, further cause the computer to:

initializing a valid buffer having one entry for each feature point of the original list, each entry storing initial data indicating whether a corresponding feature point is valid or invalid;

wherein scanning the original list in the forward direction further includes storing data in an entry of the valid buffer indicating a corresponding feature point is invalid upon any comparison determining to suppress the current feature point;

wherein scanning the original list in the backward direction further includes storing data in an entry of the valid buffer indicating a corresponding feature point is invalid upon any comparison determining to suppress the current feature point; and

wherein forming the list of maxima suppressed feature points selects feature points from the original list if a corresponding valid buffer entry indicates valid and does not select feature points from the original list if a corresponding valid buffer entry indicates invalid.

6. The tangible, non-transitory, and non-volatile computer readable media of claim 1, wherein:

scanning the original list in the backward direction further includes, prior to all comparing steps, replacing each original y coordinate Y_org in the original list of feature points with a new y coordinate Y_new as follows;

Y_new=ImageHeight+1−

Y_org.

7. The tangible, non-transitory, and non-volatile computer readable media of claim 1, wherein:

scanning the original list in the forward direction further includes;

after the steps of comparing for the current feature point, storing the combined y coordinate and reliability score of an entry of the working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point in a temporary top left buffer; and

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary top left buffer for an immediately prior feature point rather than with an entry of the working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point if the x coordinate of the immediately prior feature point is one less than the x coordinate of the current feature point and the y coordinate of the immediately prior feature point equals the y coordinate of the current feature point; and

scanning the original list in the backward direction further includes;

after the steps of comparing for the current feature point, storing the combined y coordinate and reliability score of an entry of the working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point in a temporary bottom right buffer; and

comparing the combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary bottom right buffer for an immediately prior feature point rather than with an entry of the working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point if the x coordinate of the immediately prior feature point is one more than the x coordinate of the current feature point and the y coordinate of the immediately prior feature point equals the y coordinate of the current feature point.