[link]
Summary by Oleksandr Bailo 3 years ago
Keypoint detection is an important step in various tasks such as SLAM, panorama stitching, camera calibration, and more. Efficient keypoint detectors, FAST (Features from Accelerated and Segments Test) for example, would detect keypoints where a relatively high brightness change is observed in relation to surrounding pixels. Most probably, the keypoints would be located on edges, as shown below:
https://i.imgur.com/ylC4BM3.jpg
Let's consider another image shown below. Here, while the detector is capable of detecting many keypoints, they are mostly located on trees (see subfigure (a) below). This causes redundancy and this paper focuses on solving it by selecting locally strong keypoints that are well distributed all over the image (subfigure (c)).
https://i.imgur.com/1MqZhmT.png
The algorithm requires input keypoints to be sorted in decreasing order of strength. The keypoints are then processed in that order and points that fall within the suppression range of a current keypoint are removed from the consideration. The process is repeated for the next unsuppressed keypoint in the sorted order. The process continues until no points remain. If the number of filtered points is not close enough to what we require, the suppression range is modified and the process is repeated. The suppression range is modified using binary search.
https://i.imgur.com/qryscZP.png
Binary search requires lower and upper bounds to operate. Naive initialization would be setting lower bound to 1 pixel, while upper bound - image width or height. On the other hand, this paper proposes better initialization of the suppression range that is dependent on image height $H_I$, width $W_I$, number of input keypoints $n$ as well as the number of output keypoints $m$.
* Upper bound: $\frac{H_I + W_I + 2m - \sqrt{\Delta}}{2m - 1}$ (see paper for more details)
* Lower bound: $\frac{1}{2}\sqrt{\frac{n}{m}}$
This initializing helps to decrease the number of iterations to convergence by a factor of three:
https://i.imgur.com/7NCpgbi.png
Homogenous location of keypoints is beneficial for SLAM algorithm and reduce translational and rotational errors compared to naive filtering when evaluated on KITTI:
https://i.imgur.com/4wq0kLK.png
Overall, this paper proposes a fast, efficient, and effective method to post-process noisy and redundant keypoint detections with a clear benefit to SLAM. The codes are publically available in multiple languages: C++, Python, Java, and Matlab. See https://github.com/BAILOOL/ANMS-Codes

more
less