亚像素数值极值检测算法总结

动机

在计算机视觉领域，经常需要检测极值位置，比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等，有时只需要像素精度就可以，有时则需要亚像素精度。本文尝试总结几种常用的一维离散数据极值检测方法，几个算法主要来自论文《A Comparison of Algorithms for Subpixel Peak Detection》，加上自己的理解和推导。

问题定义

算法

标准高斯函数

泰勒近似正弦曲线

质心算法

In physics, the center of mass of a distribution of mass in space is the unique point where the weighted relative position of the distributed mass sums to zero, or the point where if a force is applied it moves in the direction of the force without rotating.——Center of mass wiki

质心

线性插值

数值微分滤波

这个方法是利用极值处导数为0的性质，在微分滤波结果上插值得到导数为0的位置，因已知极值点在x附近，因此只需在x附近做微分和插值即可。插值时取极值点两侧正负值连线的过零点作为极值点的估计，如下图所示

Linear interpolation of the peak position

总结

这些数值极值检测方法均是先获取观测极值x及其邻域信息，然后综合邻域信息在各自的模型假设下通过插值估计出极值位置。若能知道数值来自的真实分布，则直接拟合真实分布然后求极值即可，但往往我们并不知道真实的分布是什么，即使知道真实分布，有时为了快速计算，也会采取插值的方式来估计极值，毕竟偏差可接受效果足够好就可以了。应用时，为了抗噪可对数据先平滑然后求极值，具体采用何种方法可在准确和速度间权衡——所用模型与真实分布越相近自然越准确，如果实在不知道怎么选，就实践对比吧（因为我也不知道），毕竟伟大领袖教导过我们——实践是检验真理的唯一标准！

参考

• A Comparison of Algorithms for Subpixel Peak Detection
• Real-time numerical peak detector