基于輪廓局部線性擬合度估計的角點(diǎn)檢測方法

張世征,劉 珊,黃萬偉,鄭 倩

(1. 鄭州輕工業(yè)大學(xué)軟件學(xué)院,河南 鄭州 450001;2. 鄭州西亞斯學(xué)院電子信息工程學(xué)院,河南 鄭州 451150)

1 引言

角點(diǎn)作為圖像重要的局部特征之一,在簡化圖像信息數(shù)據(jù)量的同時還保留了圖像的關(guān)鍵特征,因而廣泛應(yīng)用于目標(biāo)識別[1]、3D重建[2]、圖像配準(zhǔn)[3]、攝像機(jī)標(biāo)定[4]和顯著性檢測等計算機(jī)視覺和圖像處理任務(wù)中。角點(diǎn)檢測算法從上世紀(jì)70年代首次受到關(guān)注,到目前為止,已經(jīng)有超過百種不同的角點(diǎn)檢測算法,根據(jù)其實(shí)現(xiàn)方法不同,大致將其分為三類[5]：分別是基于角點(diǎn)模型(Model-based),基于圖像灰度(Intensity-based)和基于圖像輪廓(Contour-based)的算法。本文關(guān)注基于圖像輪廓的角點(diǎn)檢測算法研究。

對于圖像輪廓而言,角點(diǎn)通常理解為曲率極值點(diǎn)或邊緣輪廓上輪廓方向急劇改變的點(diǎn)。基于輪廓的角點(diǎn)檢測方法首先通過邊緣檢測器從輸入圖像中提取邊緣輪廓,然后分析輪廓上的曲率值、形狀變化信息或梯度方向來檢測角點(diǎn)[5]。在1998年,Mokhartian等人[6]提出了著名的基于曲率尺度空間(Curvature Scale Space,CSS)的角點(diǎn)檢測算法,利用曲線輪廓上像素點(diǎn)的曲率值計算角點(diǎn)響應(yīng)函數(shù)。2007年,鐘寶江等人在CSS算法的基礎(chǔ)上進(jìn)行改進(jìn),提出了直接曲率尺度空間(Direct Curvature Scale Space,DCSS)[7]算法,使用直接曲率尺度空間對輪廓曲線上各點(diǎn)進(jìn)行建模計算該點(diǎn)是否為角點(diǎn),降低了計算復(fù)雜度。隨后張小洪[8]等人提出了一種多尺度曲率乘積(Multi-Scale Curvature Product,MSCP)算法,利用不同尺度乘積進(jìn)行角點(diǎn)檢測達(dá)到抑制噪聲點(diǎn)或非角點(diǎn)處的曲率效果。2008年,He和Yung[9,10]提出了自適應(yīng)閾值和動態(tài)支持域(Adaptive Curvature Scale Space,ATCSS)算法,該算法雖然降低了門限對性能的影響,但評估實(shí)驗不充分,沒有對仿射變換圖像和噪聲圖像進(jìn)行檢測。文獻(xiàn)[11-13]指出大部分基于CSS角點(diǎn)檢測算法仍然存在對曲線的局部變化和噪聲敏感、高斯平滑參數(shù)選取不合適的問題。基于此Awrangjeb等人[11]提出了弦點(diǎn)距離累積(Chord-to-Point Distance Accumulation,CPDA)算法,利用三個不同弦點(diǎn)距離累積值作為曲率點(diǎn)的響應(yīng)函數(shù)。該算法雖然沒有使用一階和二階導(dǎo)數(shù)但計算量仍然較大。2009年,Awrangjeb等人[14]提出了改進(jìn)的快速版本F-CPDA(Fast Chord-to-Point Distance Accumulation),大大減少了計算量,但是Teng等人[15]指出Fast-CPDA算法的較高效率是通過犧牲平均重復(fù)率性能為代價。2010年,張小洪等人[12]提出梯度相關(guān)矩陣GCM(Gradient Correlation Matrices,GCM)角點(diǎn)檢測算法。2015年,Teng等人[15]使用三角形弦長理論(Chord to Triangular Arms Ratio,CTAR)確定每個點(diǎn)的曲率值,與CPDA算法相比,CTAR平均重復(fù)率更高,檢測速度更快。張小洪等人[16]分析了高斯算子在構(gòu)造拉普拉斯尺度空間(Laplacian of Gaussian,LoG)的平面曲線上的尺度空間行為,得到了拉普拉斯比例尺度空間映射的解析表達(dá)式,基于新定義的統(tǒng)一角點(diǎn)模型、論證了平面曲線的拉普拉斯尺度空間行為。2017年,林薪雨等人[17]首先介紹了一種新的測量方法-輪廓的二階差分(Second-Order Difference of Contour,SODC),基于SODC的分布特征,提出了兩種新的方法,利用曼哈頓距離和歐氏距離計算輪廓點(diǎn)的響應(yīng)函數(shù),大大降低了計算復(fù)雜度。2019年,章為川等人[18]為了降低曲率估計對局部變換和噪聲敏感,同時提高角點(diǎn)相距過近時準(zhǔn)確性,提出了一種利用較大步長下曲率積以估計離散曲率的角點(diǎn)檢測算法。

為提高輪廓角點(diǎn)檢測算法對噪聲和局部變化的魯棒性,同時改善定位性能,本文提出了一種基于輪廓局部線性擬合誤差(Local Linear Fitting Error,LLFE)度量的角點(diǎn)檢測方案。與大多數(shù)直接估計曲率方法不同,本文采用估計曲線的局部彎曲程度來檢測角點(diǎn)。該方法使用距離定義角點(diǎn)響應(yīng)函數(shù),同時采用較大的支持域,因此和CSS類方法相比對噪聲的魯棒性更好;此外本文采用正則化方案進(jìn)一步增強(qiáng)了對仿射變換的魯棒性。與5種典型的輪廓角點(diǎn)檢測方法(CPDA[11]、F-CPDA[14]、Zhang[18]、LoG[16]和GCM[12])相比,本文提出的角點(diǎn)檢測方法具有更好的檢測性能和噪聲魯棒性。

2 本文方法

假設(shè)輪廓P由n個點(diǎn)構(gòu)成,P={pj=(xj,yj),j=1, 2,…,n},(xj,yj)是點(diǎn)pj的笛卡爾坐標(biāo)。定義Nm(pj)為輪廓的一個片段,Nm(pj)由pi-m和pi+m之間點(diǎn)集構(gòu)成(為正整數(shù)),這里m為支持域半徑大小,Nm(pi)={pi-m,…,pi,…,pi+m}。

圖1 LLFE的模型示意圖

(1)

(2)

通過求解上述兩個優(yōu)化問題,可以推導(dǎo)出最優(yōu)參數(shù)α*和β*為

(3)

(4)

(5)

(6)

式中

(7)

由于LLFEx或LLFEy單獨(dú)不能準(zhǔn)確反映線性擬合誤差,而LLFEx、LLFEy之和能夠反映線性擬合誤差,因此本文將LLFE=LLFEx+LLFEy稱作角點(diǎn)響應(yīng)函數(shù),值得注意的是,為了使LLFE在單尺度變換下具有更強(qiáng)的魯棒性,進(jìn)一步在LLFE上引入尺度正則化,式(8)表示基于正則化的LLFE：

(8)

式中

(9)

下面給出LLFE離散曲率在一幅飛機(jī)圖像上的仿真。圖2展示了使用LLFE算法對飛機(jī)輪廓的曲率響應(yīng)圖像,可以發(fā)現(xiàn),在角點(diǎn)位置的曲率峰值異常突出,在非角點(diǎn)位置的曲率值接近0。圖2的仿真結(jié)果驗證了式(8)給出的擬合誤差之和能夠反映輪廓曲線的角點(diǎn)行為。

圖2 LLFE在飛機(jī)輪廓上的曲率

LLFE算法流程圖如圖3所示,具體步驟如下:

圖3 LLFE算法的流程圖

第1步:使用Canny邊緣檢測器提取輸入圖像的邊緣輪廓,并填充斷裂邊緣,獲得相對完整的邊緣輪廓,同時標(biāo)識T-型角點(diǎn)。

第2步:使用均值為0,高斯核為σ的函數(shù)平滑,步驟1中提取的邊緣輪廓,以及去除量化噪聲和局部范圍內(nèi)的變化。

第3步:使用式(8)計算平滑去噪后邊緣輪廓的角點(diǎn)曲率值,得到候選角點(diǎn)集。

第4步:進(jìn)行非極大值抑制,將角點(diǎn)曲率值大于預(yù)設(shè)閾值T的點(diǎn)加入角點(diǎn)合集。

3 仿真與結(jié)果分析

本節(jié)通過相關(guān)實(shí)驗,將提出的LLFE算法與五種經(jīng)典的角點(diǎn)檢測算法進(jìn)行比較。下面介紹實(shí)驗配置環(huán)境、數(shù)據(jù)集和評價標(biāo)準(zhǔn)。

3.1 運(yùn)行環(huán)境

本文算法運(yùn)行環(huán)境為i7-4790處理器,64位操作系統(tǒng),內(nèi)存8GB,主頻3.60GHz以及MATLAB 2014b。

3.2 數(shù)據(jù)集

使用公開可用的GCM圖像數(shù)據(jù)集,如圖4所示,一共包括20幅不同的灰度圖像,其中13幅為人工合成圖像,7幅為真實(shí)世界圖像,這些原始圖像大部分選自標(biāo)準(zhǔn)數(shù)據(jù)庫,包括經(jīng)典的Block、House、Leaf等圖像及一些簡單的平面曲線。GCM數(shù)據(jù)集中的每幅原始圖像經(jīng)過5種不同的變換得到測試數(shù)據(jù)集,這五種變換類型是:

圖4 GCM圖像數(shù)據(jù)集

1)高斯白噪聲變換。零均值高斯白噪聲以 [0.005,0.05]范圍,0.005為間隔加入原始圖像。

2)旋轉(zhuǎn)。在-90°至90°范圍內(nèi)以10°為間隔進(jìn)行旋轉(zhuǎn)變換。

3)一致尺度變換。x軸和y軸方向在[0.5,2]范圍內(nèi)以0.1為間隔進(jìn)行同尺度的放大、縮小變換。

4)非一致尺度變換。x軸方向在[0.7,1.5]范圍內(nèi)以0.1為間隔進(jìn)行放大縮小變換,y軸方向在[0.5,1.8]范圍內(nèi)以0.1為間隔進(jìn)行放大和縮小變換。

5)旋轉(zhuǎn)-縮放變換。原始圖像同時進(jìn)行3種變換:在-30°至30°范圍內(nèi)以10°為間隔進(jìn)行旋轉(zhuǎn)變換;x軸和y軸在[0.8,1.2]范圍內(nèi)以0.1為間隔進(jìn)行同尺度放大、縮小變換。

3.3 評價準(zhǔn)則

使用兩個評價準(zhǔn)則進(jìn)行性能分析:①平均重復(fù)率和定位誤差[11];②精確度和定位誤差[11,19]。

3.3.1 平均重復(fù)率評價標(biāo)準(zhǔn)

Awrangjeb等人[11]提出了一種魯棒的評估方法,該方法不涉及人工干預(yù),適用于任何規(guī)模的數(shù)據(jù)集,使用平均重復(fù)率和定位誤差評價標(biāo)準(zhǔn)來衡量角點(diǎn)檢測器的魯棒性。平均重復(fù)率Ravg表示原始圖像和經(jīng)過尺度變換后圖像之間的角點(diǎn)重復(fù)率,表達(dá)式如下

(10)

其中,No表示原始圖像中檢測到的角點(diǎn)個數(shù),NT是測試圖像檢測到的角點(diǎn)個數(shù),NR表示原始圖像與測試圖像之間重復(fù)的角點(diǎn)個數(shù),Ravg值越大表示算法的魯棒性越優(yōu)異。

(11)

其中,(xoi,yoi)和(xti,yti)分別代表原始圖像和測試圖像中第i個匹配角點(diǎn)位置,定位誤差越小表示角點(diǎn)定位越精確。

3.3.2 精確度評價標(biāo)準(zhǔn)

Mohanna和Mokhtarian[19]提出了基于精確度(Accuracy,ACU)的評估標(biāo)準(zhǔn),該方法表示原始圖像真實(shí)角點(diǎn)和測試圖像角點(diǎn)的匹配率。No表示測試算法檢測到的角點(diǎn)個數(shù),Ng表示真實(shí)角點(diǎn)(ground truth)個數(shù),Na表示真實(shí)圖像角點(diǎn)和測試算法檢測角點(diǎn)之間匹配的個數(shù)。精確度可由式(12)表示

(12)

LE[11]是基于兩點(diǎn)之間歐式距離定義的均方根誤差。表達(dá)式如下

(13)

其中,Nr表示真實(shí)角點(diǎn)和算法檢測角點(diǎn)匹配的個數(shù),(xgi,ygi)是真實(shí)角點(diǎn)中第i個匹配的位置,(xti,yti)是檢測角點(diǎn)第i個匹配的位置。

3.4 實(shí)驗結(jié)果分析

3.4.1 參數(shù)選擇

LLFE角點(diǎn)檢測算法主要涉及三個可調(diào)節(jié)參數(shù):支持域大小(Region of Support,RoS)、高斯標(biāo)準(zhǔn)差(σ)和曲率閾值(Threshold),本文采用一次只調(diào)整一個參數(shù),同時固定另外兩個參數(shù)的方法來獲取最優(yōu)參數(shù)。為了公平比較,對比實(shí)驗中其它角點(diǎn)檢測算法也執(zhí)行相同的最優(yōu)參數(shù)選擇方案。需要指出的是,按照文獻(xiàn)[11,12,20]中設(shè)置,基于精確度準(zhǔn)則的Canny邊緣檢測器的閾值設(shè)置為低=0和高=0.35,基于平均重復(fù)率準(zhǔn)則的Canny邊緣檢測器的閾值設(shè)置為低=0.2和高=0.7,本文采用相同的Canny邊緣檢測子參數(shù)。表1展示了基于平均重復(fù)率評價準(zhǔn)則選取的最優(yōu)參數(shù)。表2展示了基于精確度評價準(zhǔn)則選取的最優(yōu)參數(shù)。

表1 六種對比算法基于平均重復(fù)率評價標(biāo)準(zhǔn)的參數(shù)設(shè)置

表2 六種對比算法基于精確度評價標(biāo)準(zhǔn)的參數(shù)設(shè)置

3.4.2 高斯噪聲和仿射變換實(shí)驗

本文將提出的LLFE角點(diǎn)檢測算法與CPDA[11]、F-CPDA[14]、Zhang[18]、LoG[16]和GCM[12]算法進(jìn)行高斯噪聲和仿射變換實(shí)驗比較。圖5和圖6顯示了六種算法關(guān)于噪聲和仿射變換的平均重復(fù)率和定位誤差。從圖5和圖6可以看出,隨著高斯白噪聲的增大,所有算法的穩(wěn)健性逐漸降低,但LLFE算法下降趨勢明顯低于所對比的其它算法,表明LLFE算法對噪聲的干擾具有較強(qiáng)的穩(wěn)健性,另外,F-CPDA和Zhang算法隨著噪聲的增加,穩(wěn)健性下降比較快,表明F-CPDA和Zhang算法對噪聲較為敏感;在旋轉(zhuǎn)變換下,LLFE算法獲得最高的平均重復(fù)率和最低的定位誤差;在一致尺度變換下,本文算法獲得了優(yōu)異的平均重復(fù)率,而在定位誤差方面,CPDA和F-CPDA相比更低一些;在非一致尺度變換下,LLFE算法獲得最高的平均重復(fù)率和最低的定位誤差;最后在旋轉(zhuǎn)尺度變換下,LLFE算法同樣獲得最高的平均重復(fù)率,本文算法和LoG算法具有最好的定位性能;從五種變換的平均結(jié)果來看,本文提出的LLFE算法表現(xiàn)出最高的平均重復(fù)率和最低的定位誤差(定位誤差越小,檢測性能越優(yōu)異)。實(shí)驗結(jié)果表明,在基于平均重復(fù)率評價標(biāo)準(zhǔn)下,本文提出的LLFE角點(diǎn)檢測算法具有最優(yōu)異的魯棒性。

圖6 基于平均重復(fù)率標(biāo)準(zhǔn)下的定位誤差

圖7和圖8顯示了六種算法關(guān)于噪聲和仿射變換的精確度和定位誤差。由圖7可知,在添加不同高斯白噪聲和非一致尺度變換下,LLFE算法具有最高的精確度;旋轉(zhuǎn)、一致尺度變化和旋轉(zhuǎn)-尺度變化下LLFE算法與LoG算法精確度相似。由圖8可知,在添加不同高斯白噪聲變換下,LLFE算法也能優(yōu)于CPDA、FCPDA和Zhang算法;在不同的旋轉(zhuǎn)角度變換下,LLFE算法也取得了優(yōu)異的檢測結(jié)果。在一致尺度變換下、非一致尺度變換和旋轉(zhuǎn)-尺度變換下LLFE算法定位性能比CPDA、GCM和Zhang算法表現(xiàn)出色;從平均結(jié)果可以看出,LLFE算法定位誤差在六種算法中排名第二。根據(jù)噪聲和仿射變換的精確度和定位性能結(jié)果,可以得出本文提出的LLFE算法具有較高的檢測精度和良好的定位性能。

圖7 六種算法的精確度

圖8 基于精確度標(biāo)準(zhǔn)下的定位誤差

3.4.3 角點(diǎn)檢測實(shí)驗

對GCM圖像數(shù)據(jù)集中每幅測試圖像,執(zhí)行算法10次,計算平均執(zhí)行時間。如表3所示,在6個檢測器中,本文提出的LLFE算法執(zhí)行速度比較快,約是CPDA檢測角點(diǎn)速度的3倍,這主要是因為CPDA算法曲率計算需要進(jìn)行多次平方根運(yùn)算[17],同時LLFE比F-CPDA、LoG和GCM算法檢測速度也更快,這驗證了LLFE算法的高效性。

表3 角點(diǎn)檢測時間對比(10次隨機(jī)實(shí)驗的平均結(jié)果)

圖9給出了LLFE算法在8幅圖像上的角點(diǎn)檢測結(jié)果,可以看出,對于人工合成圖像,幾乎所有的真實(shí)角點(diǎn)都能被檢測到,在真實(shí)圖像中,有少數(shù)角點(diǎn)被遺漏。這些結(jié)果驗證了LLFE算法的準(zhǔn)確性。

圖9 LLFE算法的角點(diǎn)檢測結(jié)果

4 總結(jié)

本文提出了一種新穎的基于輪廓局部線性擬合誤差的角點(diǎn)檢測算法,與大多數(shù)直接估計曲率的檢測算法不同,本文采用最小線性擬合誤差估計曲線局部彎曲程度,整個算法計算過程使用距離而不是導(dǎo)數(shù),故對噪聲和局部變換不敏感,同時采用正則化方案進(jìn)一步增強(qiáng)了對一致尺度變換的魯棒性。基于平均重復(fù)率和精確度兩種不同評價標(biāo)準(zhǔn)的實(shí)驗結(jié)果驗證了LLFE角點(diǎn)檢測算法的優(yōu)異檢測性能和對噪聲較好的穩(wěn)健性,但在角點(diǎn)檢測運(yùn)行時間方面,LLFE算法與文獻(xiàn)[18]還存在一定的差距。同時作為一種基于輪廓的角點(diǎn)檢測算法,LLFE對邊緣檢測算法性能具有高度依賴性。因此下一步工作將會對提出的LLFE算法進(jìn)行不斷優(yōu)化,提高角點(diǎn)檢測速度,擴(kuò)大適用范圍,使其應(yīng)用于更多的計算機(jī)視覺和圖像處理任務(wù)。