動機

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

問題定義

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

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

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

算法

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

高斯近似

一維高斯函數如下：

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

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

下面可以看到，高斯近似相當于取對數后的拋物線近似。

拋物線近似

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

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

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

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

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

質心算法

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

令，質心坐標為

帶入得

以上考慮的是3質點系統的質心，還可考慮5質點、7質點等，甚至考慮所有點。

線性插值

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

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

解得

同理，若求得

數值微分濾波

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

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

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

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

若，則

總結

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