動機

在計算(suan)機視覺領(ling)域，經常需(xu)要(yao)檢(jian)測(ce)極值位(wei)置，比如SIFT關鍵點檢(jian)測(ce)、模板(ban)匹配獲得(de)最大響應位(wei)置、統計直方圖(tu)峰(feng)值位(wei)置、邊緣檢(jian)測(ce)等等，有(you)時只(zhi)需(xu)要(yao)像素(su)(su)精(jing)度就可以，有(you)時則需(xu)要(yao)亞像素(su)(su)精(jing)度。本文(wen)嘗試總結幾(ji)種常用的(de)一(yi)維離散數(shu)據極值檢(jian)測(ce)方法，幾(ji)個算(suan)法主要(yao)來(lai)自論文(wen)《A Comparison of Algorithms for Subpixel Peak Detection》，加(jia)上自己的(de)理解和推導。

問題定義

給定如下離散值，求其極值位置。可知125為觀(guan)察極值。

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

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

算法

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

高斯近似

一維如下：

當時為標準高斯函(han)數，形如

假設的鄰域(yu)可用(yong)高斯近似，用(yong)三點對高斯函數進行擬合，獲得模型參數即為峰值位置，。將三點帶入上面的高斯函(han)數兩邊同(tong)時(shi)取對數求得：

下面可以看到，高斯近似相當于(yu)取對(dui)數(shu)后(hou)的拋物(wu)線近似。

拋物線近似

使用拋物線近似的局部，可以將三點帶入求參數即為估計的極值位置，也可采用（）來求極值(zhi)。泰勒公式(shi)實(shi)際上(shang)是(shi)一(yi)種(zhong)(zhong)利(li)用高階(jie)導(dao)數(shu)通(tong)過(guo)多項式(shi)近(jin)似函數(shu)的(de)方法，下面(mian)的(de)圖示(shi)可直觀理(li)解這種(zhong)(zhong)近(jin)似，圖示(shi)為通(tong)過(guo)泰勒公式(shi)近(jin)似原點附近(jin)的(de)正弦曲線：

泰勒近似xx附近，如只取到二階則為拋物線近似。假設高階可導，極值為，則根據泰勒公式，

極值處導數為0，這里為常數為變量，兩邊同時對求導，忽略高階項可得(de)

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

與(yu)帶入拋(pao)物線(xian)求參數(shu)的(de)結果是一(yi)致的(de)，加(jia)上對(dui)數(shu)則與(yu)高斯近似一(yi)致。

質心算法

若將看成質點，將看成質點的質量，則可以把質心作為極值的估計。根據質點相對質心位置的質量加權和為零，可求得質心位置。令為質心坐標，和分別為質點質量和坐標，則個質點的質心滿足

令，質心坐標為

帶入得

以(yi)上考慮的是(shi)3質(zhi)點(dian)系統的質(zhi)心，還(huan)可考慮5質(zhi)點(dian)、7質(zhi)點(dian)等，甚至考慮所(suo)有點(dian)。

線性插值

這個模型假設在極值兩側是線性增長和線性下降的，且上升和(he)下降的速(su)度相同，即，上升側，下降側，兩者絕對值(zhi)相同，可以(yi)利(li)用(yong)這個性質(zhi)求解極值(zhi)位置(zhi)。

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

解得

同理，若求得

數值微分濾波

這個方法是利用極值處導數為0的性質，在微(wei)分(fen)濾波結果上插值得到導(dao)數為0的位置，因已知極值點在xx附近，因此只需在xx附近(jin)做(zuo)微(wei)分和插(cha)值即可。插(cha)值時取極(ji)值點兩側正(zheng)負值連線的(de)過零點作為極(ji)值點的(de)估計，如(ru)下圖所示

論文中定義了4階和8階線性濾波器和，對應的函數形式為

2階形式為，這些濾(lv)波器的表(biao)現與數值微分濾(lv)波器相似(si)。

當時，極值點位于之間，，極值點位置為與連線的過(guo)零點，通過(guo)斜率求得

若，則

總結

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