多支撐區域模式化融合角點檢測算法仿真

宋智禮，張家齊

(上海應用技術大學，上海 201418)

1 引言

近年來人工智能技術高速發展，計算機視覺相關技術成為研究者們關注的焦點。經過多年的研究，在對圖像的處理中，特征檢測的重要地位逐漸建立起來。在圖像的眾多特征中，特征點因其具有旋轉不變性、尺度不變性等優點而備受研究者的青睞。目前對于特征點并沒有嚴格的定義，相對公認的理解[1]是從廣義和狹義兩個方面定義的。廣義上來講，特征點是圖像中某種特性的位置，不需要滿足物理上對特征的定義。狹義上來講，特征點代表一種常規特征屬性，反映該點相對于其小范圍鄰域內的其它點的特殊性。本文算法檢測的角點屬于狹義特征點范疇。

到目前為止，角點檢測根據檢測機理不同，可大致分為兩類，分別是基于灰度的角點檢測算法[2]和基于輪廓的角點檢測算法[3-4]。本文角點檢測算法是基于圖像輪廓的。基于圖像輪廓的角點檢測算法通常是利用輪廓曲線上某點的幾何位置信息或者曲率來衡量曲線上該點所在位置的彎曲程度，以此判斷該點是否為較角點。早期此類算法中較為經典的是Mokhtarian等人于1988年提出的CSS(Curvature Scale Space)算法[5]，該算法利用輪廓曲線上每個像素點的曲率值來衡量角點響應程度。該算法的突出貢獻在于它引入了曲率尺度空間的定義，實現了在不同尺度下檢測和定位角點。后來的研究者在此基礎上提出了一系列改進算法[6-7]。2008年，Awrangjeb等人提出CPDA(Chord-to-Point Distance Accumulation)算法[8]，該算法利用輪廓曲線上點到弦距離的累加和來計算角點響應值。隨后學者在此基礎上進行了改進和應用[9-11]。Rosenfeld等人提出了k-余弦曲率算法[12]，用輪廓曲線上點與其鄰域內的點所成夾角的余弦值作為該點曲率的度量，以此來判斷該點是否為角點。

本文算法在k-余弦曲率算法為基礎，創新性的提出了多支撐區域模式化融合的角點檢測算法，在一定程度上解決了以往基于圖像輪廓的角點檢測算法中閾值選擇的困難，有效的提高了角點檢測的精度。

2 k-余弦曲率算法

2.1 曲線的描述

提取圖像輪廓后，得到閉合輪廓曲線，為曲線像素點的集合，即

L={pi=(xi，yi)|i=0，1，…，N-1}

(1)

其中，N為組成輪廓曲線的像素點的個數，pi和pi+1是曲線上相鄰的兩個像素點。

2.2 支撐區域的定義

記曲線L上任意一點pi為點A，Pi-k為點B，Pi+k為點C。

(2)

(3)

在計算cik時，需要在一個區域n內選擇一個合適的k值，這里的n(n≥k)被定義為支撐區域。

2.3 k-余弦曲率算法的描述

1)任取支撐區域n

2)對曲線L上的每一個點pi計算cik，k=1，2，3，…，n。

3)選取最大余弦值cih來代表pi處曲率的大小，記為ci，即cih≥cik，1≤k≤n且k≠n。

4)對于滿足|i-j|≤h/2的所有j，如果有ci≥cj，則pi為曲線L上的一個角點。

2.4 k-余弦曲率算法的的不足與改進

在重復的試驗中可以發現，支撐區域取值越小，越容易檢測到輪廓曲線上局部的微小變化(如圖1上的點P)，而難以檢測到輪廓曲線上的較大的彎曲(如圖1上的點Q)。反之，支撐區域取值越大，越難以檢測到曲線上的微小變化。顯然，想要準確得出曲線上的所有角點，對于曲線上各個局部就需要選取不同的支撐區域。本文在傳統的k-余弦曲率算法的基礎上進行了改進，使用多個不同的支撐區域計算曲率，減小了曲率選擇不當帶來的誤差，提高了角點檢測的準確率。

圖1 輪廓曲線上不同局部的彎曲程度不同

3 新算法實現

3.1 算法基本思路

本文算法的具體步驟如下：

1)提取圖像輪廓曲線；

2)先任選一個支撐區域，按照k-余弦曲率算法對曲線上每一個點計算ci，i=0，1，…，N-1；某條輪廓曲線上各店曲率值如圖2所示。

圖2 輪廓曲線上各點曲率值圖

3)選擇一個較為寬松的閾值T對曲線上的點進行初步篩選，保留ci>T的點，經過篩選后保留下的點稱為初選角點；

4)對初選角點進行分組;

5)在每組中選取一個或多個點作為備選角點；

6)選取不同的支撐區域，重復步驟2)-4)；

7)將多個備選角點集進行模式化融合，刪除重復、多余的角點。

3.2 算法的具體描述

3.2.1 分組的方法

經過3.1節的步驟3的初步篩選，能夠大致確定曲線上角點的位置，此時保留下來的點數量較多，需要進一步篩選。可以發現，初選角點集中分布在真實角點的附近。將曲線上位置相近的點劃分為一組。具體方法如下：

1)將第一個初選角點的分組編號設為1；

2)從第二個初選角點開始，依次判斷是否與上一個初選角點相鄰(本文算法中設定在曲線上相距3個像素以內即判斷為相鄰)，如果相鄰，則與上一個初選角點劃分為同一組；如果不相鄰，該點為下一個分組的起始點，直到遍歷所有初選角點。分組結果如圖3所示。

圖3 分組結果示意圖

3.2.2 備選角點的選取

備選角點的選取在每組點中獨立進行，每一組點中選出一個或多個備選角點。在某組中，對于滿足|i-j|≤r/4的所有j，如果有ci≥cj，則pi為一個備選角點，其中，r代表該組中點的個數。

3.2.3 支撐區域的選取

本文2.4節部分描述了支撐區域的選取和曲率計算結果的關系。本文算法中需選取m個大小不同的支撐區域。最小的支撐區域決定了算法可檢測到的曲線上最小的彎曲程度，本文取為5。考慮到如果支撐區域取值太大，會對程序執行時間產生較大影響，本文算法最大的支撐區域取為min{N/20，20}(N表示構成輪廓曲線的點的個數)。其余支撐區域選取從最小值開始依次乘以2。本文實驗中選取m=3，故支撐區域依次為5，10，20。

3.2.4 輪廓曲線模式劃分及角點融合方法

根據不同的支撐區域會選取多個備選角點集，需要將這些點集進行有效的融合，保留正確的角點，刪除重復和錯誤的角點。本文算法將曲線上的復雜變化概括為以下三種模式，在不同的模式下使用相應的方式進行角點的融合，以m=3(即選取3個不同支撐區域)的情況進行說明，三個支撐區域由小到大分別為α，β，γ，在每種模式中檢測出的角點分別為Pα，Pβ，Pγ，示意圖中正確檢測到的角點用白色點表示，重復或錯誤的角點用灰色點表示。

模式一：曲線上較大的彎曲處，如圖4(a)所示，這種情況下，選取最小的支撐區域時，難以準確檢測到角點，選取其它較大的支撐區域時都可以較為準確的檢測到角點。此時在真實角點附近會出現m個或m個以下備選角點，只需要任選一點或選取曲率最大值點作為角點，刪除其它備選角點即可。

圖4 輪廓曲線模式圖

模式二：曲線上微小波動處，如圖4(b)，這種情況下，只有在選取最小的支撐區域時可以檢測到角點的存在，此時在真實角點附近只有1個備選角點，保留即可。

模式三：曲線上的方形突起處，如圖4(c)，這種情況下，當選取較小的支撐區域時，可以準確的檢測到每一個角點，如圖4(c)中的Pα1點和Pα2點，當選取較大的支撐區域時，只能檢測兩個真實角點之間的某一個點，如圖4(c)中的Pβ點和Pγ點。此時，在真實角點附近會出現大于或等于m個備選角點，保留兩邊的備選角點，刪除其它的備選角點即可。

4 實驗結果分析

為驗證本文算法的有效性和準確性，在PC機(Inter(R)Core(TM)i5-5200 CPU @ 2.20GHz，4G內存)上進行實驗，所用軟件為Visual Studio 2017。分別對He&Yung，CSS以及本文算法進行性能評估。

實驗所用原始圖像來自文獻[13]。每幅原始圖像經過旋轉變換和伸縮產生多幅測試圖像。旋轉變換從-90°到90°，每隔10°旋轉一次，每幅原始圖像會產生18幅旋轉變換圖。伸縮變換中，x方向放大倍數從0.5到2，相應地，y方向放大倍數從1.8到0.3，每幅原始圖像會產生16幅伸縮變換圖。

實驗采用了兩種性能評價指標，分別為平均重復率(average repeatability)[14]和準確率(accuracy)[15]。用R代表平均重復率，A代表準確率，Nr是指在原始圖像和變換圖像中都被檢測到并且匹配的角點數目，No是指在原始圖像中被檢測到的角點數目，Nt是指在變換圖像中被檢測到的角點數目，Na是指變換圖像中被檢測出的正確角點數目，Ng是指在原始圖像中標注的正確角點數目。

Ro為Nr和No的比值，Rt為Nr和Nt的比值，Ro和Rt都可以表示重復率，但是問題在于這兩種方法都對檢測到的錯誤角點個數高度敏感。在極端情況下，如果角點檢測器認為原始圖像中所有的點都是角點，此時Nr=Nt，Rt=100%；如果角點檢測器認為變換圖像中所有的點都是角點，此時No=Nt，Ro=100%。為了降低錯誤角點個數對性能評估的影響，本實驗采用Ro和Rt的平均值作為重復率的評價指標，稱作平均重復率，其定義如下：

(4)

At為Na和Nt的比值，Ag為Na和Ng的比值。如果角點檢測器檢測到的角點個數很多，這意味著錯誤角點個數也會增加，此時At接近于0，而Ag接近于100%；如果角點檢測器檢測到的角點個數很少，那么正確的角點個數也會減少，此時At接近于100%，而Ag接近于0。為了更加準確的評估角點檢測器是否能夠盡可能多的檢測到正確的角點，同時避免檢測到錯誤的角點，本實驗采用At和Ag的平均值作為準確率的評價指標，其定義如下：

(5)

本文算法與其它兩種算法比較結果如圖5所示，圖5(a)，圖5(b)顯示了三種算法在旋轉變換下的平均重復率和準確率，圖5(c)，圖5(d)顯示了在伸縮變換下的平均重復率和準確率。觀察發現，旋轉變換下，本文算法的平均重復率表現最佳，He&Yung次之，準確率三種算法相差不大，本文算法總體表現略高于其它兩種算法。在伸縮變換下，本文算法的平均重復率和準確率都有較好的表現。這是由于本文算法采用了多支撐區域的方式，可以檢測到輪廓曲線上不同彎曲程度下的角點，又在角點融合過程中刪除了不正確的角點。

圖5 實驗結果圖

圖6展示的是三種算法檢測結果的直觀對比，此圖像輪廓細節豐富，不同局部彎曲程度差異較大，角點檢測難度較高，可以直觀的體現算法角點檢測性能強弱。可以看出，就此圖像而言，CSS算法對于飛機機翼前側細節檢測效果較好，而對飛機機身以及飛機尾部幾處明顯的角點并沒有檢測到。He&Yung算法和本文算法能夠較好的兼顧圖像輪廓上不同局部的檢測效果，而本文算法有更少的誤檢測點。綜上所述，本文算法檢測效果最佳。

圖6 檢測結果直觀對比圖

5 結論

本文提出了一種多支撐區域模式化融合的角點檢測算法，通過選取不同閾值計算出多組備選角點，以選取不同彎曲程度下的角點，提取曲線上跟多的有效信息，再對其進行模式化融合，刪除多余重復的角點。該方法在一定程度上解決了閾值選擇的問題，提高了對復雜曲線角點檢測的能力。從實驗結果可以看出，有效提高了角點檢測的準確性，但在應對噪聲以及效率方面有略有不足，下一步可以考慮針對此缺陷進行優化。本算法可應用于圖像配準、形狀分析、目標檢測等領域。