多支撐區(qū)域模式化融合角點(diǎn)檢測算法仿真

宋智禮，張家齊

(上海應(yīng)用技術(shù)大學(xué)，上海 201418)

1 引言

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

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

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

2 k-余弦曲率算法

2.1 曲線的描述

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

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

(1)

其中，N為組成輪廓曲線的像素點(diǎn)的個數(shù)，pi和pi+1是曲線上相鄰的兩個像素點(diǎn)。

2.2 支撐區(qū)域的定義

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

(2)

(3)

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

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

1)任取支撐區(qū)域n

2)對曲線L上的每一個點(diǎn)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上的一個角點(diǎn)。

2.4 k-余弦曲率算法的的不足與改進(jìn)

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

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

3 新算法實現(xiàn)

3.1 算法基本思路

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

1)提取圖像輪廓曲線；

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

圖2 輪廓曲線上各點(diǎn)曲率值圖

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

4)對初選角點(diǎn)進(jìn)行分組;

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

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

7)將多個備選角點(diǎn)集進(jìn)行模式化融合，刪除重復(fù)、多余的角點(diǎn)。

3.2 算法的具體描述

3.2.1 分組的方法

經(jīng)過3.1節(jié)的步驟3的初步篩選，能夠大致確定曲線上角點(diǎn)的位置，此時保留下來的點(diǎn)數(shù)量較多，需要進(jìn)一步篩選。可以發(fā)現(xiàn)，初選角點(diǎn)集中分布在真實角點(diǎn)的附近。將曲線上位置相近的點(diǎn)劃分為一組。具體方法如下：

1)將第一個初選角點(diǎn)的分組編號設(shè)為1；

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

圖3 分組結(jié)果示意圖

3.2.2 備選角點(diǎn)的選取

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

3.2.3 支撐區(qū)域的選取

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

3.2.4 輪廓曲線模式劃分及角點(diǎn)融合方法

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

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

圖4 輪廓曲線模式圖

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

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

4 實驗結(jié)果分析

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

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

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

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

(4)

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

(5)

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

圖5 實驗結(jié)果圖

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

圖6 檢測結(jié)果直觀對比圖

5 結(jié)論

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