動(dòng)機(jī)

在計(jì)算機(jī)視覺領(lǐng)域，經(jīng)常需要檢測極值位置，比如SIFT關(guān)鍵點(diǎn)檢測、模板匹配獲得最大響應(yīng)位置、統(tǒng)計(jì)直方圖峰值位置、邊緣檢測等等，有時(shí)只需要像素精度就可以，有時(shí)則需要亞像素精度。本文嘗試總結(jié)幾種常用的一維離散數(shù)據(jù)極值檢測方法，幾個(gè)算法主要來自論文《A Comparison of Algorithms for Subpixel Peak Detection》，加上自己的理解和推導(dǎo)。

問題定義

給定如下離散值，求其極值位置?？芍?25為觀察極值。

如果這些離散值是從某個(gè)分布中等間距采樣獲得，其真正的極值位置應(yīng)位于120和125之間。

下面給出形式化的定義：給定一組離散值，令為觀測到的極值點(diǎn)位置，其值為，其左右相鄰位置的值為和$$，真正的極值點(diǎn)位置為$$，令為的估計(jì)值。

算法

假設(shè)的鄰域可通過某個(gè)模型進(jìn)行近似，如高斯近似、拋物線近似，則可以利用$$的鄰域信息根據(jù)模型估計(jì)出極值。使用的模型不同就有不同的算法，具體如下。

高斯近似

一維高斯函數(shù)如下：

當(dāng)時(shí)為標(biāo)準(zhǔn)高斯函數(shù)，形如

假設(shè)$$的鄰域可用高斯近似，用$$三點(diǎn)對高斯函數(shù)進(jìn)行擬合，獲得模型參數(shù)即為峰值位置，。將三點(diǎn)帶入上面的高斯函數(shù)兩邊同時(shí)取對數(shù)求得：

下面可以看到，高斯近似相當(dāng)于取對數(shù)后的拋物線近似。

拋物線近似

使用拋物線近似的局部，可以將三點(diǎn)帶入求參數(shù)即為估計(jì)的極值位置，也可采用泰勒展開（牛頓法）來求極值。泰勒公式實(shí)際上是一種利用高階導(dǎo)數(shù)通過多項(xiàng)式近似函數(shù)的方法，下面的圖示可直觀理解這種近似，圖示為通過泰勒公式近似原點(diǎn)附近的正弦曲線：

泰勒近似x$x$附近，如只取到二階則為拋物線近似。假設(shè)高階可導(dǎo)，極值為，則根據(jù)泰勒公式，

極值處導(dǎo)數(shù)為0，這里為常數(shù)為變量，兩邊同時(shí)對$$求導(dǎo)，忽略高階項(xiàng)可得

使用一階微分和二階微分近似和得

與帶入拋物線求參數(shù)的結(jié)果是一致的，加上對數(shù)則與高斯近似一致。

質(zhì)心算法

若將看成質(zhì)點(diǎn)，將看成質(zhì)點(diǎn)的質(zhì)量，則可以把質(zhì)心作為極值的估計(jì)。根據(jù)質(zhì)點(diǎn)相對質(zhì)心位置的質(zhì)量加權(quán)和為零，可求得質(zhì)心位置。令為質(zhì)心坐標(biāo)，和分別為質(zhì)點(diǎn)質(zhì)量和坐標(biāo)，則個(gè)質(zhì)點(diǎn)的質(zhì)心滿足

令，質(zhì)心坐標(biāo)為

帶入得

以上考慮的是3質(zhì)點(diǎn)系統(tǒng)的質(zhì)心，還可考慮5質(zhì)點(diǎn)、7質(zhì)點(diǎn)等，甚至考慮所有點(diǎn)。

線性插值

這個(gè)模型假設(shè)在極值兩側(cè)是線性增長和線性下降的，且上升和下降的速度相同，即，上升側(cè)，下降側(cè)，兩者絕對值相同，可以利用這個(gè)性質(zhì)求解極值位置。

若則極值位于之間，可列等式

解得

同理，若求得

數(shù)值微分濾波

這個(gè)方法是利用極值處導(dǎo)數(shù)為0的性質(zhì)，在微分濾波結(jié)果上插值得到導(dǎo)數(shù)為0的位置，因已知極值點(diǎn)在x$x$附近，因此只需在x$x$附近做微分和插值即可。插值時(shí)取極值點(diǎn)兩側(cè)正負(fù)值連線的過零點(diǎn)作為極值點(diǎn)的估計(jì)，如下圖所示

論文Real-time numerical peak detector中定義了4階和8階線性濾波器和，對應(yīng)的函數(shù)形式為

2階形式為，這些濾波器的表現(xiàn)與數(shù)值微分濾波器相似。

當(dāng)時(shí)，極值點(diǎn)位于之間，，極值點(diǎn)位置為與連線的過零點(diǎn)，通過斜率求得

若，則

總結(jié)

這些數(shù)值極值檢測方法均是先獲取觀測極值及其鄰域信息，然后綜合鄰域信息在各自的模型假設(shè)下通過插值估計(jì)出極值位置。若能知道數(shù)值來自的真實(shí)分布，則直接擬合真實(shí)分布然后求極值即可，但往往我們并不知道真實(shí)的分布是什么，即使知道真實(shí)分布，有時(shí)為了快速計(jì)算，也會(huì)采取插值的方式來估計(jì)極值，畢竟偏差可接受效果足夠好就可以了。應(yīng)用時(shí)，為了抗噪可對數(shù)據(jù)先平滑然后求極值，具體采用何種方法可在準(zhǔn)確和速度間權(quán)衡——所用模型與真實(shí)分布越相近自然越準(zhǔn)確，如果實(shí)在不知道怎么選，就實(shí)踐對比吧（因?yàn)槲乙膊恢溃?，畢竟偉大領(lǐng)袖教導(dǎo)過我們——實(shí)踐是檢驗(yàn)真理的唯一標(biāo)準(zhǔn)！