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

宋智禮，張家齊

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

1 引言

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

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

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

2 k-余弦曲率算法

2.1 曲線的描述

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

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

(1)

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

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

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

(2)

(3)

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

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

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

2)對(duì)曲線L上的每一個(gè)點(diǎn)pi計(jì)算cik，k=1，2，3，…，n。

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

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

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

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

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

3 新算法實(shí)現(xiàn)

3.1 算法基本思路

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

1)提取圖像輪廓曲線；

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

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

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

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

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

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

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

3.2 算法的具體描述

3.2.1 分組的方法

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

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

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

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

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

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

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

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

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

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

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

圖4 輪廓曲線模式圖

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

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

(4)

At為Na和Nt的比值，Ag為Na和Ng的比值。如果角點(diǎn)檢測(cè)器檢測(cè)到的角點(diǎn)個(gè)數(shù)很多，這意味著錯(cuò)誤角點(diǎn)個(gè)數(shù)也會(huì)增加，此時(shí)At接近于0，而Ag接近于100%；如果角點(diǎn)檢測(cè)器檢測(cè)到的角點(diǎn)個(gè)數(shù)很少，那么正確的角點(diǎn)個(gè)數(shù)也會(huì)減少，此時(shí)At接近于100%，而Ag接近于0。為了更加準(zhǔn)確的評(píng)估角點(diǎn)檢測(cè)器是否能夠盡可能多的檢測(cè)到正確的角點(diǎn)，同時(shí)避免檢測(cè)到錯(cuò)誤的角點(diǎn)，本實(shí)驗(yàn)采用At和Ag的平均值作為準(zhǔn)確率的評(píng)價(jià)指標(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ū)域的方式，可以檢測(cè)到輪廓曲線上不同彎曲程度下的角點(diǎn)，又在角點(diǎn)融合過(guò)程中刪除了不正確的角點(diǎn)。

圖5 實(shí)驗(yàn)結(jié)果圖

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

圖6 檢測(cè)結(jié)果直觀對(duì)比圖

5 結(jié)論

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