在计算机视觉领域经常需要检測极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等有时只需要像素精度就可以,有时则需要亚像素精度本文尝试总结几种常用的一维离散数据极值检测方法,几个算法主要来自论文《A Compariso of Algorithms for Subpixel Peak Detectio》加上自己的理解和推导。
给定如下離散值求其极值位置。可知125为观察极值
如果这些离散值是从某个分布
f 中等间距采样获得,其真正的极值位置应位于120和125之间
下面给出形式化的定义:给定一组离散值,令
x 为观测到的极值点位置其值为
f ( x ) ,其左右相邻位置的值为
f ( x + 1 ) 真正的极值点位置为
x 的邻域**可通过某个模型进行近似,如高斯近似、抛物线近似则可以利用
x 的邻域信息根据模型估计出极值。使用的模型不同就有不同的算法具体如下。
? π 1 ? 时为标准高斯函数形如
x 的邻域可用高斯近似,用
( x + 1 , f ( x + 1 ) ) 三点对高斯函数进行拟合获得模型参数
δ ^ = μ ? x 。将三点带入上面的高斯函数两边同時取对数求得:
下面可以看到高斯近似相当于取对数后的抛物线近似 。
b 即为估计的极值位置也可采用()来求极值。泰勒公式实际上昰一种利用高阶导数通过多项式近似函数的方法下面的图示可直观理解这种近似,图示为通过泰勒公式近似原点附近的正弦曲线:
x 附近如只取到二阶则为抛物线近似。假设高阶可导极值为
f ( x + δ ) ,则根据泰勒公式
δ 求导,忽略高阶项可得
0
使用一阶微分和二阶微分近似
f ( x + 1 ) 看荿质点的质量则可以把质心作为极值的估计。根据质点相对质心位置的质量加权和为零可求得质心位置。令
r 分别为质点质量和坐标則
0
M = ∑ i = 1 ? m i ? ,质心坐标为
以上考虑的是3质点系统的质心还可考虑5质点、7质点等,甚至考虑所有点
这个模型假设在极值两侧是线性增长和線性下降的,且上升和下降的速度相同 即
0
0
k < 0 ,两者绝对值相同可以利用这个性质求解极值位置。
这个方法是利用极值处导数为0的性质茬微分滤波结果上插值得到导数为0的位置 ,因已知极值点在
x 附近做微分和插值即可插值时取极值点两侧正负值连线的过零点作为极值点嘚估计,如下图所示
论文中定义了4阶和8阶线性滤波器
0
0
g 2 ? ( x ) = f ( x ? 1 ) ? f ( x + 1 ) 这些滤波器的表现与数值微分滤波器相似。
0 0 g ( x + 1 ) 连线的过零点通过斜率求得
**这些数值极值检测方法均是先获取观测极值
x 及其邻域信息,然后综合邻域信息在各自的模型假设下通过插值估计出极值位置**若能知道数值來自的真实分布,则直接拟合真实分布然后求极值即可但往往我们并不知道真实的分布是什么,即使知道真实分布有时为了快速计算,也会采取插值的方式来估计极值毕竟偏差可接受效果足够好就可以了。应用时为了抗噪可对数据先平滑然后求极值,具体采用何种方法可在准确和速度间权衡——所用模型与真实分布越相近自然越准确如果实在不知道怎么选,就实践对比吧(因为我也不知道)毕竟伟大领袖教导过我们——实践是检验真理的唯一标准 !
}