Efficient SIMD implementation of 3x3 non maxima suppression of sparse 2D image feature points
First Claim
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.
1 Assignment
0 Petitions
Accused Products
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.
-
Citations
7 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. - View Dependent Claims (2, 3, 4, 5, 6, 7)
-
Specification