蘭國(guó)清，胡旭曉，王永力，吳躍成

(浙江理工大學(xué) 機(jī)械與自動(dòng)控制學(xué)院，浙江 杭州 310018)

在整個(gè)計(jì)算機(jī)視覺(jué)和圖像處理過(guò)程中，圖像的特征提取與匹配是最基本的處理方法[1-3]，已經(jīng)廣泛應(yīng)用于全景拼接、三維匹配、目標(biāo)跟蹤等場(chǎng)合[4-8].而角點(diǎn)是圖像特征的重要部分，它既保留了圖像的重要信息，又減少了大量的數(shù)據(jù)，在當(dāng)前大數(shù)據(jù)時(shí)代，扮演著越來(lái)越重要的角色，并且角點(diǎn)在圖像仿射變換和噪聲環(huán)境中具有相對(duì)穩(wěn)定和不變性.計(jì)算機(jī)視覺(jué)領(lǐng)域的許多學(xué)者對(duì)特征提取和匹配問(wèn)題已經(jīng)進(jìn)行了深入研究.現(xiàn)有的角點(diǎn)檢測(cè)算法一般被分為3類：第一類是利用角點(diǎn)附近灰度值變化劇烈這一特點(diǎn)提出的算法，即基于梯度的角點(diǎn)檢測(cè)方法，其經(jīng)典算法主要有Moravec算法[9]、Harris算法[10](1977年Moravec發(fā)現(xiàn)在角點(diǎn)附近圖像的灰度值變化很大，利用此特點(diǎn)提出了一種角點(diǎn)檢測(cè)方法；Harris則是對(duì)此算法進(jìn)行改進(jìn)，通過(guò)局部自相關(guān)矩陣來(lái)區(qū)分角點(diǎn)和非角點(diǎn))；第二類是用已有模板與圖像上小區(qū)域進(jìn)行匹配的算法，即基于模板的角點(diǎn)檢測(cè)方法(Smith和Brady利用圓形模板于1997年提出了SUSAN檢測(cè)算法[11])；第三類是利用輪廓上曲率極大值點(diǎn)進(jìn)行閾值處理的算法，即基于輪廓的角點(diǎn)檢測(cè)方法.此類方法包括k-cosine方法[12]、CSS角點(diǎn)檢測(cè)方法[13]、ANDD角點(diǎn)檢測(cè)方法[14]、KD曲率角點(diǎn)檢測(cè)方法[15]等.其中，基于曲率尺度空間(CSS)的角點(diǎn)檢測(cè)器應(yīng)用較多.該算法主要是提取好的邊緣輪廓曲線，對(duì)曲線進(jìn)行大尺度的高斯核平滑處理，并分析曲線的極大值點(diǎn)，找出候選角點(diǎn)，然后通過(guò)小尺度進(jìn)行定位跟蹤.2013年Shui P L等提出利用各向異性高斯方向?qū)?shù)(ANDD)對(duì)角點(diǎn)進(jìn)行提取與分類[14].2016年Chen S T等提出KD曲率焦點(diǎn)檢測(cè)算法，通過(guò)曲線融合填補(bǔ)提取高質(zhì)量的曲線，經(jīng)高斯平滑處理，確定固定的支撐鄰域和閾值，然后根據(jù)kd曲率含義進(jìn)行曲線的曲率估計(jì)，將局部曲率最大值大于閾值的點(diǎn)作為候選角點(diǎn)[15].該方法中支撐鄰域是固定的，這就意味著數(shù)字化曲線上相鄰的兩像素之間距離是固定的，從而在評(píng)估各角點(diǎn)強(qiáng)度時(shí)能夠保持標(biāo)準(zhǔn)一致，但是現(xiàn)實(shí)中相鄰像素之間的距離并不是固定的，如在研究機(jī)器人自主定位與導(dǎo)航的過(guò)程中，每幀圖片都會(huì)發(fā)生旋轉(zhuǎn)并可能受到噪聲干擾，每條曲線上的像素點(diǎn)都會(huì)發(fā)生變化，即固定像素點(diǎn)個(gè)數(shù)對(duì)應(yīng)著不同的曲線段，因此該算法會(huì)丟失許多角點(diǎn)，同時(shí)抗噪和抗旋性能不佳.

本文在KD曲率角點(diǎn)檢測(cè)算法的基礎(chǔ)上，提出一種基于自適應(yīng)支撐鄰域的角點(diǎn)檢測(cè)算法，通過(guò)自適應(yīng)閾值提取候選角點(diǎn)，并進(jìn)行非極大值抑制，選出角點(diǎn)集，以期提高算法的抗噪、抗旋性能.

1 離散kd曲率的提取

Borrelli V等提出的曲率計(jì)算方法是針對(duì)連續(xù)型曲線的[16]，而數(shù)字化圖像上都是離散的像素點(diǎn).因此，該方法需作修改才可能適用于圖像的角點(diǎn)提取.

1.1 連續(xù)曲線的kd曲率計(jì)算

假設(shè)連續(xù)曲線為Γ，pi是曲線上的一個(gè)點(diǎn).以pi為原點(diǎn)建立坐標(biāo)系，則曲線上的點(diǎn)坐標(biāo)pi(x,y)如圖1所示.由泰勒展開(kāi)式得：

(1)

式中：y″(0)=k；y?(0)=v；o(x3)為x3的高階無(wú)窮小.假設(shè)pi點(diǎn)的y′(0)=0,則有極坐標(biāo)：x=ηcosθ和y=ηsinθ.

圖1 連續(xù)曲線上的點(diǎn)坐標(biāo)

由隱函數(shù)定理[17]得：

(2)

(3)

式中，kd(pi)為pi點(diǎn)曲率，即kd(pi)=k.

由式(3)可知，在同一支撐鄰域內(nèi)，曲率越大的點(diǎn)，其αi值越小.

1.2 離散曲線的kd曲率計(jì)算

由于圖像上像素是離散的(圖2)，因此需要修改式(3)，使其能用于圖像的曲率計(jì)算.

注：ros為支撐鄰域.圖2 離散型曲線

設(shè)pi-1=(xi-1，yi-1)，pi=(xi，yi)，pi+1=(xi+1，yi+1)，則ηi-1=(xi-1-xi，yi-1-yi)，ηi+1=(xi+1-xi，yi+1-yi)，αi=arccos[(ηi-1ηi+1)/(ηi-1ηi+1)](這里,ηi-1和ηi+1分別為ηi-1和η+1對(duì)應(yīng)的向量),得:

(4)

2 支撐鄰域的選取

為了區(qū)別傳統(tǒng)的支撐鄰域[18]，本文提出自適應(yīng)支撐鄰域檢測(cè)思想，即采用一條曲線上總體支撐鄰域來(lái)計(jì)算該曲線上各離散點(diǎn)、曲率所需的支撐鄰域.當(dāng)圖像發(fā)生仿射變換或者受到噪聲干擾時(shí)，根據(jù)曲線變化確定新的支撐鄰域.為找出一個(gè)可以描述曲線變化的參數(shù)，當(dāng)圖像變換后，此參數(shù)仍能反映這條曲線的曲率變化趨勢(shì)，本文做了進(jìn)一步研究.

假設(shè)輪廓曲線Γ是以弧長(zhǎng)s為參數(shù)的函數(shù)：

Γ=(x(s),y(s))

(5)

用高斯核g(s,σ)對(duì)輪廓曲線進(jìn)行卷積運(yùn)算，有：

(6)

則：

Γ={X,Y}

(7)

(8)

通過(guò)大量實(shí)驗(yàn)發(fā)現(xiàn)，kd曲率和Kros值變化趨勢(shì)大致相同.對(duì)一條輪廓曲線(圖3)進(jìn)行仿射變換，在支撐鄰域?yàn)?的情況下，它的kd曲率、Kros值變化如圖4所示.

圖3 積木圖及其一條輪廓曲線

由圖4可看出，即使對(duì)圖像做不同處理，Kros值與kd曲率變化趨勢(shì)也基本相同.從數(shù)學(xué)角度不難證明，Kros值與kd曲率存在相關(guān)關(guān)系.因此，通過(guò)Kros值可確定支撐鄰域的長(zhǎng)度.因kd曲率局部最大值對(duì)應(yīng)于候選角點(diǎn)，所以Kros值局部最大值也對(duì)應(yīng)于候選角點(diǎn).本文首先提取Kros局部最大值，并進(jìn)行閾值處理，統(tǒng)計(jì)滿足要求的Kros值個(gè)數(shù)，然后通過(guò)不斷調(diào)整參數(shù)得出最終閾值Tthred，最后計(jì)算出支撐領(lǐng)域.其具體步驟如下：

注：sx、sy均為縮放尺度.圖4 輪廓曲線的kd曲率與Kros值

(1) 選取初始閾值t0=0.030 9;

(2) 通過(guò)t0，選取Kros大于t0的局部最大值，并且將最大值個(gè)數(shù)記為N；

(4) 判斷N是否大于n，若大于n，則t=t0+Δt，返回(2)；

(5) 若t>0.082 3，則退出循環(huán)，取最后t值為最終閾值，即Tthred=t；

(6) 輪廓曲線的支撐鄰域?yàn)椋?/p>

(9)

式中：round為取整函數(shù)；c為常量.

3 候選角點(diǎn)閾值的獲取

由式(3)可知，kd曲率大小取決于α角，而α的大小取決于Lros.根據(jù)文獻(xiàn)[15]，對(duì)于不同的α和Lros值，kd曲率也不同(表1).

表1 不同支撐鄰域Lros和α角對(duì)應(yīng)的kd曲率

(10)

(11)

從表1可知，Lros值一定時(shí)，α越大，則kd曲率越小.本文提出的Lros是自適應(yīng)變化的，針對(duì)不同曲線，有不同的Lros值，但是同一條曲線的Lros值是固定的.如果一條曲線上出現(xiàn)幾個(gè)α角點(diǎn)，為了篩選真角點(diǎn)，則可設(shè)置閾值為：

(12)

式中，kthred為閾值.

以上即為本文提供篩選不同角點(diǎn)強(qiáng)度的方法.

4 新的角點(diǎn)檢測(cè)算法

以式(9)獲取每條曲線的Lros值后，計(jì)算每條曲線的kd曲率，通過(guò)式(12)確定真角點(diǎn)的閾值，從而克服KD算法中Lros值固定不變時(shí)，提取真角點(diǎn)閾值固定不變的缺陷，在此基礎(chǔ)上提出新的角點(diǎn)檢測(cè)算法.

提取邊緣曲線后進(jìn)行高斯核平滑處理，能夠降低曲線附帶噪聲以及曲線局部變化對(duì)檢測(cè)結(jié)果的影響.本文通過(guò)一次高斯平滑，用kd曲率來(lái)估計(jì)平滑后曲線的曲率，以大于閾值的局部最大值對(duì)應(yīng)候選角點(diǎn)，進(jìn)行非極大值抑制，從而去除偽角點(diǎn).

(1) 根據(jù)文獻(xiàn)[19]，用Canny算子進(jìn)行邊緣檢測(cè).

(2) 對(duì)提取的邊緣曲線進(jìn)行填補(bǔ)、融合，以提高邊緣曲線的質(zhì)量.受強(qiáng)噪聲干擾以及利用Canny算子提取曲線本身缺陷的影響，提取曲線可能較短，而高斯卷積對(duì)短的邊緣曲線來(lái)說(shuō)比較困難，因此需要去除短的曲線.當(dāng)曲線長(zhǎng)度m滿足下式：

(13)

式中：w和h分別為輸入圖片的寬和高，ε是一個(gè)參數(shù).那么，可認(rèn)為應(yīng)該去除曲線.依據(jù)該原則提取高質(zhì)量的曲線，加快了后續(xù)算法的速度；同時(shí)，本文還應(yīng)用了T角點(diǎn)融合技術(shù)[15].

(3) 根據(jù)高斯卷積的需要，將邊緣曲線狀態(tài)分為兩種loop、line[20].若曲線的第一個(gè)像素和最后一個(gè)像素之間的距離小于6個(gè)像素則認(rèn)為是loop型曲線，其他的則屬于line型曲線.

(4) 由于噪聲對(duì)曲率的計(jì)算有很大影響，因此可用高斯核對(duì)邊緣曲線進(jìn)行平滑處理，較長(zhǎng)曲線用大的尺度，相對(duì)短的曲線用小的尺度[15].但是若尺度σ太大或者太小，則平滑處理中會(huì)丟失角點(diǎn)，對(duì)噪聲抑制能力較差，而且，曲線高斯平滑會(huì)使角點(diǎn)定位產(chǎn)生一定的誤差.因此，選擇合適的σ既能減小定位誤差，也能夠去除曲線局部變化對(duì)計(jì)算的不必要影響.σ的選取采取以下規(guī)則：

(14)

σ=1時(shí)，曲線的平滑處理效果不佳，需要設(shè)置理想的閾值來(lái)去除錯(cuò)誤角點(diǎn).

在計(jì)算kd曲率之前，需要確定Lros值.文獻(xiàn)[15]中直接以一個(gè)固定的Lros來(lái)計(jì)算kd曲率.這種方法很容易丟失角點(diǎn)個(gè)數(shù)，并且抗旋性能不太好.本文首先確定每條曲線的Lros值，然后通過(guò)式(4)計(jì)算出kd曲率，利用式(12)并設(shè)置不同α0值(如α0=155°)來(lái)確定閾值kthred，最后，曲線上α≤α0的局部最大值通過(guò)該閾值即可被篩選出來(lái).但是篩選出的局部最大值角點(diǎn)可能是錯(cuò)誤或者比較弱的角點(diǎn).因此，對(duì)這些局部最大值進(jìn)行非最大抑制處理，可消除一些偽角點(diǎn).從圖4(c)—(f)中可以看出，對(duì)于真角點(diǎn)，它的kd曲率較大，對(duì)于偽角點(diǎn)則kd曲率很小.通過(guò)閾值處理和非極大值抑制，可以快速得到真角點(diǎn).

新的角點(diǎn)檢測(cè)算法流程如圖5所示.

圖5 新的角點(diǎn)檢測(cè)算法流程

5 仿真實(shí)驗(yàn)與性能分析

5.1 實(shí)驗(yàn)步驟

任何非平移仿射變換都可以分解為旋轉(zhuǎn)、均勻縮放和非均勻變換.本文算法與KD角點(diǎn)提取算法、ANDD角點(diǎn)提取算法、CPDA角點(diǎn)提取算法[21]、Harris角點(diǎn)提取算法、ATCD角點(diǎn)提取算法[22]進(jìn)行了實(shí)驗(yàn)比較.實(shí)驗(yàn)中使用10幅圖像處理經(jīng)常使用的積木圖、實(shí)驗(yàn)室圖、房子圖等圖像.對(duì)這10幅圖像進(jìn)行高斯噪聲實(shí)驗(yàn)和仿射變換[23]，具體步驟如下：

(1) 對(duì)原圖進(jìn)行旋轉(zhuǎn)變換，在[-90°,90°]范圍內(nèi)進(jìn)行旋轉(zhuǎn)，旋轉(zhuǎn)間隔為10°；

(2) 對(duì)圖像進(jìn)行非一致尺度變換，sx=1，sy的值在[0.5，2.0]之間變化，間隔為0.1；

(3) 對(duì)圖像進(jìn)行一致尺度變換，即sx=sy，并且它們的值在[0.5，2.0]之間變化，間隔為0.1；

(4) 對(duì)圖像添加高斯白噪聲.

5.2 實(shí)驗(yàn)評(píng)估方法

為了確定算法的魯棒性，需要對(duì)實(shí)驗(yàn)進(jìn)行評(píng)估，本文采用文獻(xiàn)[24]的方法進(jìn)行評(píng)估，計(jì)算重復(fù)率和定位誤差.測(cè)試圖像和原始圖像之間的角點(diǎn)重復(fù)率為：

Rav=Nr/2×(1/N0+1/Nt)

(15)

式中：N0為原始圖像中檢測(cè)到的角點(diǎn)數(shù)；Nt為圖像變換后檢測(cè)到的角點(diǎn)數(shù)，Nr為原始圖像變換前后檢測(cè)到的角點(diǎn)重復(fù)數(shù).

Rav反映了仿射變換下或者高斯白噪聲下的角點(diǎn)檢測(cè)算法的穩(wěn)定性.平均重復(fù)率越高，角點(diǎn)檢測(cè)算法魯棒性越好.

定位誤差為：

(16)

5.3 參數(shù)的選擇

表2所示為每階段實(shí)驗(yàn)得到的參數(shù).

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

采用本文算法進(jìn)行角點(diǎn)提取的實(shí)驗(yàn)結(jié)果如圖6所示.通過(guò)5種算法(即：Harris、He&Yang[25]、ANDD、ATCD、本文算法)，在有噪聲和無(wú)噪聲的情況下測(cè)試積木圖和實(shí)驗(yàn)室圖像角點(diǎn)錯(cuò)誤率和損失率的實(shí)驗(yàn)結(jié)果如圖7所示.角點(diǎn)錯(cuò)誤率和損失率分別指錯(cuò)誤角點(diǎn)與丟失角點(diǎn)占總角點(diǎn)的百分比.

表2 實(shí)驗(yàn)參數(shù)表

圖6 實(shí)驗(yàn)室圖像角點(diǎn)提取結(jié)果

從圖7可以看出，在無(wú)噪聲的情況下，He&Yang算法錯(cuò)誤率最高，本文算法錯(cuò)誤率最低；在損失率方面，Harris算法最高(其主要原因是此算法需要利用圖像的灰度信息)，而本文算法中等.在有噪聲的情況下，Harris算法錯(cuò)誤率很高，對(duì)噪聲比較敏感，而本文算法錯(cuò)誤率最低.綜合來(lái)說(shuō)，本文算法最優(yōu).

幾種算法實(shí)驗(yàn)室圖和積木圖有無(wú)添加高斯白噪聲的情況下定位誤差如圖8所示.從圖8可以看出，Harris算法在有無(wú)噪聲干擾下定位誤差都很大，添加噪聲情況下，本文算法相比于其他算法的定位誤差最小，算法性能良好.

幾種算法的平均重復(fù)率如圖9所示.從圖9可以看出，各種算法的平均重復(fù)率都很好，在圖9(a)中，隨著尺度慢慢變大，其平均重復(fù)率先增大后減小，同時(shí)也可以看出本文的算法有著更好的重復(fù)性能；圖9(b)表明了在非一致尺度因子中，本文算法的平均重復(fù)率比較高，而且相對(duì)穩(wěn)定；在圖9(c)中，在順時(shí)針旋轉(zhuǎn)時(shí)，隨著角度的增加，平均重復(fù)率減小，當(dāng)旋轉(zhuǎn)角度超過(guò)40°時(shí)，平均重復(fù)率開(kāi)始增加，逆時(shí)針變化情況與順時(shí)針大致相同，而在這幾種算法中，Harris算法上下波動(dòng)比較大，但是總體上看要好于CPDA算法、He&Yang算法，而KD算法與本文算法處于同一水平，都優(yōu)于其他算法.

圖7 錯(cuò)誤率和損失率折線圖 圖8 幾種算法的定位誤差

圖9 幾種算法的平均重復(fù)率

5.5 性能分析

從實(shí)驗(yàn)結(jié)果可知，許多算法的平均重復(fù)率相對(duì)穩(wěn)定，這意味著用現(xiàn)有許多角點(diǎn)檢測(cè)算法檢測(cè)到的角點(diǎn)還是很穩(wěn)定的，但是對(duì)于一些比較復(fù)雜的曲線，可能會(huì)檢測(cè)到偽角點(diǎn)或者丟失角點(diǎn)，而本文提出的算法能夠在很大程度上降低錯(cuò)誤率和損失率且能夠提高重復(fù)率.本文提出自適應(yīng)支撐鄰域，并確定一個(gè)良好的全局kd閾值，使算法具有良好的抗噪和抗旋轉(zhuǎn)性能，且有較高的平均重復(fù)率.

6 結(jié)束語(yǔ)

本文提出了自適應(yīng)支撐鄰域的角點(diǎn)檢測(cè)方法，使用kd曲率對(duì)輪廓曲線進(jìn)行曲率估計(jì)，計(jì)算簡(jiǎn)單、快捷，能夠加快算法速度.通過(guò)大量實(shí)驗(yàn)，檢測(cè)圖像仿射變換下算法的檢測(cè)能力，如計(jì)算定位誤差、平均重復(fù)率以及錯(cuò)誤率和損失率.實(shí)驗(yàn)表明，本文算法具有良好的性能，能夠與現(xiàn)階段一些優(yōu)秀角點(diǎn)檢測(cè)算法媲美.本文提出的自適應(yīng)支撐鄰域技術(shù)，結(jié)合kd曲率以及融合曲線技術(shù)，采用自適應(yīng)閾值提取角點(diǎn)，避免了許多偽角點(diǎn).但本文自適應(yīng)支撐鄰域還缺少嚴(yán)格的數(shù)學(xué)證明，只是經(jīng)驗(yàn)公式.因此，在下一步研究中，將著重從數(shù)學(xué)角度進(jìn)行分析，最終提高算法的魯棒性，使算法進(jìn)一步優(yōu)化.