Efficient SIMD implementation of 3X3 non maxima suppression of sparse 2D image feature points
First Claim
1. A method comprising:
- receiving a list of feature points of an image, wherein each feature point corresponds to a pixel of the image and has properties including an x-coordinate, a y-coordinate, and a reliability score;
initializing a valid list, the initialized valid list indicating that all of the feature points of the list are non-suppressed feature points;
performing a first scan of the list of feature points in a first direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a first plurality of feature points, wherein each of the first plurality of feature points correspond to a respective one of a first plurality of pixels, and wherein each of the first plurality of pixels neighbor the pixel to which the feature point corresponds;
updating the valid list in response to the first scan to obtain an intermediate valid list;
performing a second scan of the list of feature points in a second direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a second plurality of feature points, wherein each of the second plurality of feature points correspond to a respective one of a second plurality of pixels, and wherein each of the second plurality of pixels neighbor the pixel to which the feature point corresponds;
updating the intermediate valid list in response to the second scan to obtain a final valid list, wherein the final valid list indicates that at least one of the feature points of the list is to be suppressed; and
generating a non-maxima suppressed feature point list that includes only feature points from the list that the final valid list indicates are not to be suppressed.
0 Assignments
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
16 Claims
-
1. A method comprising:
-
receiving a list of feature points of an image, wherein each feature point corresponds to a pixel of the image and has properties including an x-coordinate, a y-coordinate, and a reliability score; initializing a valid list, the initialized valid list indicating that all of the feature points of the list are non-suppressed feature points; performing a first scan of the list of feature points in a first direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a first plurality of feature points, wherein each of the first plurality of feature points correspond to a respective one of a first plurality of pixels, and wherein each of the first plurality of pixels neighbor the pixel to which the feature point corresponds; updating the valid list in response to the first scan to obtain an intermediate valid list; performing a second scan of the list of feature points in a second direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a second plurality of feature points, wherein each of the second plurality of feature points correspond to a respective one of a second plurality of pixels, and wherein each of the second plurality of pixels neighbor the pixel to which the feature point corresponds; updating the intermediate valid list in response to the second scan to obtain a final valid list, wherein the final valid list indicates that at least one of the feature points of the list is to be suppressed; and generating a non-maxima suppressed feature point list that includes only feature points from the list that the final valid list indicates are not to be suppressed. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8)
-
-
9. An electronic device comprising:
-
a processor; a memory to store image data and program instructions that, when executed by the processor, cause the processor to; retreive a list of feature points of an image from the image data stored in the memory, wherein each feature point corresponds to a pixel of the image and has properties including an x-coordinate, a y-coordinate, and a reliability score; initialize a valid list, the initialized valid list indicating that all of the feature points of the list are non-suppressed feature points; perform a first scan of the list of feature points in a first direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a first plurality of feature points, wherein each of the first plurality of feature points correspond to a respective one of a first plurality of pixels, and wherein each of the first plurality of pixels neighbor the pixel to which the feature point corresponds; update the valid list in response to the first scan to obtain an intermediate valid list; perform a second scan of the list of feature points in a second direction in which, for each feature point, at least one property of the feature point is compared a corresponding property of each of a second plurality of feature points, wherein each of the second plurality of feature points correspond to a respective one of a second plurality of pixels, and wherein each of the second plurality of pixels neighbor the pixel to which the feature point corresponds; update the intermediate valid list in response to the second scan to obtain a final valid list, wherein the final valid list indicates that at least one of the feature points of the list is to be suppressed; and generate a non-maxima suppressed feature point list that includes only feature points from the list that the final valid list indicates are not to be suppressed. - View Dependent Claims (10, 11, 12, 13, 14, 15, 16)
-
Specification