Efficient SIMD Implementation of 3x3 Non Maxima Suppression of sparse 2D image feature points

• US 20170300773A1
• Filed: 07/07/2016
• Published: 10/19/2017
• 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
• Granted Patent: US 9,984,305 B2
• Time in Patent Office: Days
• 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 computer implemented method of transforming a list of feature points of an image into a list of maxima suppressed feature points of the image, comprising the steps of:

receiving 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 sorted of the original list in image raster scan order;

initializing 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;

scanning the original list in a forward direction from a first feature point to a final feature point, for each feature point including

comparing a combined y coordinate and reliability score of a 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 the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential left neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point thereby determining whether to suppress said current feature point dependent upon results of said comparison for a potential top left neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential top neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said 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, for each feature point including

comparing a combined y coordinate and reliability score of a 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 thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential right neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential bottom right neighbor of the current feature point,

comparing a 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 a working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential bottom neighbor of the current feature point,

comparing a 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 a working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said 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 by any said comparison steps.

2. The method of claim 1, wherein:

said steps of initializing the working buffer and re-initializing the working buffer stores data in each entry whereby any comparison with the initialized or re-initialized data produced a not suppress result.

3. The method of claim 1, wherein:

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

4. The method of claim 1, wherein:

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

5. The method of claim 1, further comprising:

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;

said step of scanning the original list in a 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;

said step of scanning the original list in a 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

said step of forming a 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 method of claim 1, wherein:

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

Y_new=ImageHeight+1−

Y_org.

7. The method of claim 1, wherein:

said step of scanning the original list in a forward direction further includes

following said steps of comparing for the current feature point, storing said 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 said combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary 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 a prior feature point is one less than the x coordinate of the current feature point and the y coordinate of the prior feature point equals the y coordinate of the current feature point; and

said step of scanning the original list in a backward direction further includes

following said steps of comparing for the current feature point, storing said 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 said combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary 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 a prior feature point is one less than the x coordinate of the current feature point and the y coordinate of the prior feature point equals the y coordinate of the current feature point.

8. A tangible, non-transitory and non-volatile data storage media storing instructions controlling a general purpose computer to transform a list of feature points of an image into a list of maxima suppressed feature points of the image, said controlling including:

receiving 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 sorted of the original list in image raster scan order;

initializing 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;

scanning the original list in a forward direction from a first feature point to a final feature point, for each feature point including

comparing a combined y coordinate and reliability score of a 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 the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential left neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point thereby determining whether to suppress said current feature point dependent upon results of said comparison for a potential top left neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential top neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said 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, for each feature point including

comparing a combined y coordinate and reliability score of a 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 thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential right neighbor of the current feature point,

comparing said 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 a working buffer having a location corresponding to an x coordinate one more than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential bottom right neighbor of the current feature point,

comparing a 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 a working buffer having a location corresponding to an x coordinate equal to the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said comparison for a potential bottom neighbor of the current feature point,

comparing a 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 a working buffer having a location corresponding to an x coordinate one less than the x coordinate of the current feature point thereby determining whether to suppress the current feature point dependent upon results of said 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 by any said comparison steps.

9. The tangible, non-transitory and non-volatile data storage media of claim 8, said controlling wherein:

said steps of initializing the working buffer and re-initializing the working buffer stores data in each entry whereby any comparison with the initialized or re-initialized data produced a not suppress result.

10. The tangible, non-transitory and non-volatile data storage media of claim 8, wherein:

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

11. The tangible, non-transitory and non-volatile data storage media of claim 8, wherein:

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

12. The tangible, non-transitory and non-volatile data storage media of claim 8, said controlling further comprising:

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;

said step of scanning the original list in a 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;

said step of scanning the original list in a 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

said step of forming a 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.

13. The tangible, non-transitory and non-volatile data storage media of claim 8, said controlling wherein:

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

Y_new=ImageHeight+1−

Y_org.

14. The tangible, non-transitory and non-volatile data storage media of claim 8, said controlling wherein:

said step of scanning the original list in a forward direction further includes

following said steps of comparing for the current feature point, storing said 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 said combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary 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 a prior feature point is one less than the x coordinate of the current feature point and the y coordinate of the prior feature point equals the y coordinate of the current feature point; and

said step of scanning the original list in a backward direction further includes

following said steps of comparing for the current feature point, storing said 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 said combined y coordinate and reliability score of the current feature point with a combined y coordinate and reliability score stored in the temporary 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 a prior feature point is one less than the x coordinate of the current feature point and the y coordinate of the prior feature point equals the y coordinate of the current feature point.