热线电话:0755-23712116
邮箱:contact@shuangyi-tech.com
地址:深圳市宝安区沙井街道后亭茅洲山工业园工业大厦全至科技创新园科创大厦2层2A
在计算机视觉领域,经常需要检测极值位置,比如SIFT关键点检测、模板匹配获得最大响应位置、统计直方图峰值位置、边缘检测等等,有时只需要像素精度就可以,有时则需要亚像素精度。本文尝试总结几种常用的一维离散数据极值检测方法,几个算法主要来自论文《A Comparison of Algorithms for Subpixel Peak Detection》,加上自己的理解和推导。
给定如下离散值,求其极值位置。可知125为观察极值。
如果这些离散值是从某个分布
下面给出形式化的定义:给定一组离散值,令为观测到的极值点位置,其值为
,其左右相邻位置的值为
,真正的极值点位置为
,令
为
的估计值。
假设的邻域可通过某个模型进行近似,如高斯近似、抛物线近似,则可以利用
的邻域信息根据模型估计出极值。使用的模型不同就有不同的算法,具体如下。
一维高斯函数如下:
当时为标准高斯函数,形如
假设的邻域可用高斯近似,用
三点对高斯函数进行拟合,获得模型参数
即为峰值位置,
。将三点带入上面的高斯函数两边同时取对数求得:
下面可以看到,高斯近似相当于取对数后的抛物线近似。
使用抛物线近似的局部,可以将
三点带入
求参数
即为估计的极值位置,也可采用泰勒展开(牛顿法)来求极值。泰勒公式实际上是一种利用高阶导数通过多项式近似函数的方法,下面的图示可直观理解这种近似,图示为通过泰勒公式近似原点附近的正弦曲线:
泰勒近似,则根据泰勒公式,
极值处导数为0,这里为常数
为变量,两边同时对
求导,忽略高阶项可得
使用一阶微分和二阶微分近似和
得
与带入抛物线求参数的结果是一致的,加上对数则与高斯近似一致。
若将看成质点,将
看成质点的质量,则可以把质心作为极值的估计。根据质点相对质心位置的质量加权和为零,可求得质心位置。令
和
分别为质点质量和坐标,则
个质点的质心满足
令,质心坐标为
带入得
以上考虑的是3质点系统的质心,还可考虑5质点、7质点等,甚至考虑所有点。
这个模型假设在极值两侧是线性增长和线性下降的,且上升和下降的速度相同,即,上升侧
,下降侧
,两者绝对值相同,可以利用这个性质求解极值位置。
若则极值位于
之间,可列等式
解得
同理,若求得
这个方法是利用极值处导数为0的性质,在微分滤波结果上插值得到导数为0的位置,因已知极值点在
论文Real-time numerical peak detector中定义了4阶和8阶线性滤波器和
,对应的函数形式为
2阶形式为,这些滤波器的表现与数值微分滤波器相似。
当时,极值点位于
之间,
,极值点位置为
与
连线的过零点,通过斜率求得
若,则
这些数值极值检测方法均是先获取观测极值及其邻域信息,然后综合邻域信息在各自的模型假设下通过插值估计出极值位置。若能知道数值来自的真实分布,则直接拟合真实分布然后求极值即可,但往往我们并不知道真实的分布是什么,即使知道真实分布,有时为了快速计算,也会采取插值的方式来估计极值,毕竟偏差可接受效果足够好就可以了。应用时,为了抗噪可对数据先平滑然后求极值,具体采用何种方法可在准确和速度间权衡——所用模型与真实分布越相近自然越准确,如果实在不知道怎么选,就实践对比吧(因为我也不知道),毕竟伟大领袖教导过我们——实践是检验真理的唯一标准!
热线电话:0755-23712116
邮箱:contact@shuangyi-tech.com
地址:深圳市宝安区沙井街道后亭茅洲山工业园工业大厦全至科技创新园科创大厦2层2A