一種改進(jìn)的多尺度Harris算法

楊秋慧

(梧州學(xué)院 廣西高校圖像處理與智能信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 梧州 543002)

?

一種改進(jìn)的多尺度Harris算法

楊秋慧

(梧州學(xué)院 廣西高校圖像處理與智能信息系統(tǒng)重點(diǎn)實(shí)驗(yàn)室，廣西 梧州 543002)

傳統(tǒng)Harris算法依據(jù)經(jīng)驗(yàn)確定興趣值計(jì)算參數(shù)，并且對(duì)于一些類(lèi)型的角點(diǎn)識(shí)別能力較差。針對(duì)這些問(wèn)題，該文提出了一種基于局部標(biāo)準(zhǔn)差和對(duì)數(shù)計(jì)算的多尺度角點(diǎn)檢測(cè)方法。該方法通過(guò)對(duì)數(shù)化梯度取降低邊緣響應(yīng)對(duì)候選點(diǎn)興趣值的影響，有效地檢測(cè)不同類(lèi)型的角點(diǎn)。并重新定義興趣值函數(shù)，由標(biāo)準(zhǔn)差的統(tǒng)計(jì)特性計(jì)算興趣值，避免主觀(guān)選擇參數(shù)，使算法具有更高的客觀(guān)性。實(shí)驗(yàn)結(jié)果表明，該方法具有檢測(cè)復(fù)雜類(lèi)型角點(diǎn)、精確定位，并具有旋轉(zhuǎn)、灰度、噪聲、尺度不變性。

角點(diǎn)提??；Harris 算法；標(biāo)準(zhǔn)差；定位

角點(diǎn)是圖像灰度變化劇烈的點(diǎn)或圖像邊緣曲線(xiàn)的曲率極大值點(diǎn)。曲線(xiàn)或直線(xiàn)的交叉點(diǎn)，圖像區(qū)域的中心點(diǎn)，小波變換的局部極值點(diǎn)等等，這些能夠用某種相似性度量準(zhǔn)則提取出來(lái)的顯著點(diǎn)都可以作為圖像的角點(diǎn)。這些點(diǎn)保留了圖像的重要特征，對(duì)圖像匹配，目標(biāo)跟蹤、運(yùn)動(dòng)估計(jì)等后續(xù)圖像處理有重要意義。由于角點(diǎn)對(duì)圖像幾何形狀的不變性和易于被觀(guān)察者所接受，在特征點(diǎn)提取算法中可作為控制點(diǎn)。

角點(diǎn)可以定義為局部區(qū)域內(nèi)灰度變化劇烈的點(diǎn)、目標(biāo)區(qū)域邊緣曲線(xiàn)的曲率極大值點(diǎn)、曲線(xiàn)或直線(xiàn)的交叉點(diǎn)、圖像區(qū)域的中心點(diǎn)、或小波變換的局部極值點(diǎn)等等，能夠用某種相似性度量準(zhǔn)則提取出來(lái)的、包含圖像的重要信息的顯著點(diǎn)。根據(jù)對(duì)“角點(diǎn)”不同的定義，可將角點(diǎn)檢測(cè)方法主要分為兩類(lèi)：基于邊緣的方法和基于圖像灰度的方法?；谶吘壍姆椒ú捎锰崛D像邊緣并編碼，然后計(jì)算邊緣曲率，根據(jù)曲率是否為極值判斷該點(diǎn)是否為角點(diǎn)。其中，一些方法是直接對(duì)曲線(xiàn)進(jìn)行擬合，另一些則是用某類(lèi)函數(shù)對(duì)曲線(xiàn)進(jìn)行分段擬合，然后根據(jù)這些擬合的分段方程計(jì)算曲率極值點(diǎn)的位置[1-2]?；谶吘壍姆椒ㄌ幚硇Ч蕾?lài)于圖像分割和邊緣提取的結(jié)果，當(dāng)被檢測(cè)圖像發(fā)生變化時(shí)，可能會(huì)導(dǎo)致結(jié)果錯(cuò)誤，并且對(duì)噪聲敏感、計(jì)算量大?；卩徲蚧叶鹊姆椒?，主要根據(jù)鄰域內(nèi)灰度的變化情況確定角點(diǎn)位置，如以某種局部結(jié)構(gòu)特性、灰度相似性等特征作為篩選角點(diǎn)的條件。Harris角點(diǎn)檢測(cè)方法[3-5]、KLT[6]，MIC[7-8]，SIFT[9-11]算法等都是基于領(lǐng)域灰度的方法。其中，SIFT算法在尺度空間中尋找極值點(diǎn)，對(duì)于存在部分遮擋、拍攝角度變化等情況較好的穩(wěn)定性。該算法信息量豐富，但是過(guò)程較復(fù)雜，包含大量的浮點(diǎn)數(shù)運(yùn)算，而且提取的特征點(diǎn)沒(méi)有直觀(guān)地反映圖像的結(jié)構(gòu)特征。近年來(lái)，國(guó)內(nèi)外研究者對(duì)這些經(jīng)典算法進(jìn)行了多種改進(jìn)[12-16]。

本文通過(guò)對(duì)傳統(tǒng)Harris算法進(jìn)行分析，通過(guò)選取邊緣附近的像素點(diǎn)作為候選點(diǎn)，減少計(jì)算量。對(duì)候選點(diǎn)篩選時(shí)，對(duì)梯度值取對(duì)數(shù)值，降低位于角點(diǎn)附近的邊緣點(diǎn)的邊緣響應(yīng)對(duì)角點(diǎn)興趣值的影響，更有效地檢測(cè)出復(fù)雜類(lèi)型的角點(diǎn)。最后，為提高角點(diǎn)的定位精度及尺度不變性，采用非極大值抑制和多尺度的Harris算法檢測(cè)角點(diǎn)，并使用標(biāo)準(zhǔn)差重新定義了角點(diǎn)的興趣值函數(shù)。

1Harris算法

Harris算法是由ChrisHarris在1988年提出的，它是在Moravec角點(diǎn)提取算法的基礎(chǔ)上，采用邊界曲率描述灰度變化的情況。Harris角點(diǎn)提取算法，計(jì)算簡(jiǎn)單，只用到一階差分及濾波計(jì)算，提取的角點(diǎn)均勻分布在圖像上。算法需要對(duì)圖像中的每個(gè)點(diǎn)都計(jì)算興趣值，然后選擇最優(yōu)角點(diǎn)位置。該算法有很好的穩(wěn)定性，對(duì)圖像旋轉(zhuǎn)、灰度、噪聲等變化魯棒性較好，但不具有尺度不變性。下面簡(jiǎn)單介紹該算法的主要步驟。

(1)

(2)

其中，W為高斯平滑函數(shù)。

(3)

M矩陣為二階實(shí)對(duì)稱(chēng)陣，故存在兩個(gè)特征值λ1，λ2。這兩個(gè)特征值反映像素點(diǎn)的特征，因此能夠根據(jù)特征值來(lái)判別像素點(diǎn)是位于平滑區(qū)、邊緣還是角點(diǎn)。λ1，λ2的取值有以下3種情況：

(1)λ1，λ2為正值并且都較大時(shí)，M矩陣為峰值，各個(gè)方向相鄰像素點(diǎn)之間灰度差值都較大，則認(rèn)為這個(gè)像點(diǎn)為角點(diǎn)；

(2)當(dāng)其中一個(gè)特征值較大，一個(gè)特征值較小時(shí)，M為山脊形，沿著山脊方向的相鄰像素點(diǎn)灰度變化很小，而垂直山脊方向的變化很大，那么該像素位于圖像邊緣上；

(3)當(dāng)λ1，λ2都較小時(shí)，M矩陣是平滑的，該像素位于圖像平滑區(qū)。

于是，由M矩陣的行列式和跡計(jì)算Harris角點(diǎn)的興趣值，見(jiàn)公式(4)和公式(5)。

Det(M)=αβ=(AB)-C2Tr(M)=α+β=A+B

(4)

C(x，y)=Det(M)-k×Tr2(M)=(AB-C2)-k(A+B)2

(5)

其中，k為經(jīng)驗(yàn)值，取值區(qū)間為0.04～0.07。局部范圍內(nèi)的極大興趣值點(diǎn)就被認(rèn)為是角點(diǎn)。由于極值點(diǎn)的數(shù)量往往較大，因而需要較大的計(jì)算量。

Harris角點(diǎn)檢測(cè)方法對(duì)T,Y,X形的角點(diǎn)檢測(cè)效果較差。圖像中若含有大量結(jié)構(gòu)復(fù)雜的角點(diǎn)，Harris算法檢測(cè)結(jié)果會(huì)漏掉這些類(lèi)型的角點(diǎn)，導(dǎo)致后續(xù)的圖像分析精確度下降。

2改進(jìn)的算法

本文通過(guò)對(duì)Harris算法的研究和分析，對(duì)傳統(tǒng)算法進(jìn)行相應(yīng)的改進(jìn)。改進(jìn)的算法流程如圖1所示。

圖1 改進(jìn)的算法流程圖

角點(diǎn)是位于邊緣附近的，因此本文先對(duì)圖像進(jìn)行篩選，去除平滑區(qū)域，將邊緣附近的點(diǎn)作為候選點(diǎn)，以減少計(jì)算量。然后，算法準(zhǔn)確地區(qū)分角點(diǎn)和邊緣點(diǎn)，達(dá)到提取角點(diǎn)的目的。

當(dāng)候選點(diǎn)位于角點(diǎn)附近時(shí)，由于窗口W中包含大量邊緣點(diǎn)，這些點(diǎn)的特征值α?β，得到的興趣值與角點(diǎn)的興趣值均較大，混淆了算法對(duì)于角點(diǎn)的判斷。本文對(duì)此進(jìn)行改進(jìn)，通過(guò)對(duì)數(shù)化候選點(diǎn)的梯度值，抑制邊緣附近的候選點(diǎn)特征值中較大的值，降低邊緣響應(yīng)對(duì)計(jì)算興趣值的影響，從而達(dá)到提高角點(diǎn)定位精度的目的。則有公式(6)、公式(7)、公式(8)。

(6)

log(G′(x,y))=log(G(x,y))

(7)

計(jì)算中僅僅改變了梯度的值，梯度的方向不變，故G’θ(x,y)=Gθ(x,y)。

根據(jù)公式(1)以及梯度的求值公式，可得：

=(G′(x,y))*cos(Gθ(x,y))

(8)

(9)

使用I’x,I’y分別來(lái)代替Harris算法公式(2)中的Ix,Iy。抑制角點(diǎn)附近的邊緣點(diǎn)的興趣值對(duì)判斷角點(diǎn)的影響。

傳統(tǒng)算法的興趣值C(x,y)計(jì)算需根據(jù)經(jīng)驗(yàn)確定參數(shù)k的值，具有主觀(guān)性，降低檢測(cè)的穩(wěn)定性。本文用標(biāo)準(zhǔn)差的計(jì)算來(lái)取代對(duì)參數(shù)k，重新定義了興趣值函數(shù)，自動(dòng)地判別角點(diǎn)。為增強(qiáng)角點(diǎn)的尺度不變性，同時(shí)采用laplace多尺度算法，通過(guò)非極大值抑制法和興趣值的大小來(lái)確定角點(diǎn)的位置。

I′(x,y,s,δD)=I?W(x,y,sδD)

(10)

其中，i=1，2，3，....，N為候選點(diǎn)總數(shù)目。d1,d2分別表示矩陣M’的行列式和跡平方的均值，興趣值函數(shù)中兩部分分別為行列式和跡平方的標(biāo)準(zhǔn)差。

由于角點(diǎn)的兩個(gè)特征值都較大，而邊緣附近的像素點(diǎn)，兩個(gè)特征值中僅含一個(gè)較大值，且候選點(diǎn)所包含的邊緣點(diǎn)數(shù)目遠(yuǎn)大于角點(diǎn)數(shù)目，因此，

(1)當(dāng)R(x,y)>0時(shí)，候選點(diǎn)為角點(diǎn)。角點(diǎn)響應(yīng)大于邊緣響應(yīng)。

(2)當(dāng)R(x,y)<0時(shí)，候選點(diǎn)為邊緣點(diǎn)。邊緣響應(yīng)大于角點(diǎn)響應(yīng)。

對(duì)于每個(gè)候選點(diǎn)分別計(jì)算其興趣值，結(jié)果大于零，并且是局部極大值，那么這個(gè)點(diǎn)被判定為角點(diǎn)，不需要Harris算法中篩選角點(diǎn)時(shí)選取閾值，可以直接區(qū)分出角點(diǎn)和邊緣點(diǎn)；反之，則判斷為邊緣點(diǎn)。

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

實(shí)驗(yàn)是在操作系統(tǒng)為Windows7的微機(jī)上進(jìn)行的，使用MATLAB7.10對(duì)圖像進(jìn)行處理。

圖2 圖像1

圖3 圖像1的細(xì)節(jié)部分

圖3為圖2中圈出的部分放大后的圖像。從上述實(shí)驗(yàn)可以看出改進(jìn)的算法能夠更好地檢測(cè)出復(fù)雜類(lèi)型的角點(diǎn)，改進(jìn)后的Harris算法能夠更加準(zhǔn)確地定位角點(diǎn)的位置。

對(duì)于圖2中圖像的角點(diǎn)提取效果，兩種算法的比較如表1所示，改進(jìn)后的算法可以提取到足夠數(shù)量的角點(diǎn)，有較少的缺失及錯(cuò)誤的角點(diǎn)數(shù)，能夠更加準(zhǔn)確地提取各種類(lèi)型的角點(diǎn)。

表1 兩種算法的效果對(duì)比

圖像算法角點(diǎn)總數(shù)檢測(cè)的角點(diǎn)總數(shù)錯(cuò)誤角點(diǎn)數(shù)正確的角點(diǎn)數(shù)缺失的角點(diǎn)數(shù)圖像1Harris改進(jìn)的Harris607144614583555

實(shí)驗(yàn)表明，算法對(duì)于實(shí)際場(chǎng)景圖像的角點(diǎn)提取也有著良好的效果，如圖4所示，圖中用圓圈標(biāo)記檢測(cè)出的角點(diǎn)，相對(duì)于Harris算法，可以獲得數(shù)量充足、多種復(fù)雜類(lèi)型的角點(diǎn)，并且對(duì)于旋轉(zhuǎn)、灰度及噪聲均具有較好的穩(wěn)定性，角點(diǎn)的定位更接近于實(shí)際物體的角點(diǎn)位置。

圖4 兩種算法結(jié)果對(duì)比

從表2的數(shù)據(jù)可以看出，本文改進(jìn)的算法在旋轉(zhuǎn)、縮放、灰度變化以及噪聲變換情況下，角點(diǎn)的復(fù)現(xiàn)率均比Harris算法高，能取得更好的提取效果。

表2 原圖1復(fù)現(xiàn)率比較

原圖像旋轉(zhuǎn)圖像縮放圖像灰度反轉(zhuǎn)加噪圖像Harris算法特征點(diǎn)數(shù)26692807210926664584復(fù)現(xiàn)率441%442%534%683%改進(jìn)的算法特征點(diǎn)數(shù)72562384466541復(fù)現(xiàn)率676%663%849%767%

4結(jié)論

本文提出一種改進(jìn)的Harris角點(diǎn)提取算法，有效地改善了傳統(tǒng)Harris算法對(duì)T、X、Y等類(lèi)型角點(diǎn)無(wú)法檢測(cè)出來(lái)的問(wèn)題。通過(guò)數(shù)據(jù)的統(tǒng)計(jì)特性，定義新的興趣值函數(shù)，消除興趣值計(jì)算中的參數(shù)的經(jīng)驗(yàn)取值，降低了對(duì)算法的主觀(guān)性，取得比原算法更好的實(shí)驗(yàn)結(jié)果。本文的算法不僅對(duì)于角點(diǎn)的定位更加精確，還保持了算法對(duì)于旋轉(zhuǎn)、灰度變化、尺度以及噪聲較好的穩(wěn)定性。但是，角點(diǎn)定位精度也仍舊只精確到像素級(jí)，維持在與圖像像素相同的精度。

[1]L Kitchen, A Rosenfeld. Gray Level Corner Detection[J]. Pattern Recognition Letters, 1982, 3(1): 95-102.

[2]鐘寶江,廖文和.基于精化曲線(xiàn)累加弦長(zhǎng)的角點(diǎn)檢測(cè)技術(shù)[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào),2004,16(7):939-943.

[3]Harris C G, Stephens M J. A combined Corner and Edge Detector[A]//Proceedings Fourth Alvey Vision Conference. Manchester, 1988.

[4] Misra I, Moorthi S M, Dhar D, et al. An automatic satellite image registration technique based on Harris corner detection and Random Sample Consensus (RANSAC) outlier rejection model[C]//Recent Advances in Information Technology (RAIT), 2012 1st International Conference on. IEEE, 2012: 68-73..

[5]呂恒利，尚振宏.基于Harris角點(diǎn)和SIFT算法的車(chē)輛圖像匹配[J].昆明理工大學(xué)學(xué)報(bào)：自然科學(xué)版，2015，40(1)：50-54.

[6]Ramakrishnan N, Srikanthan T, Lam S K, et al. Adaptive Window Strategy for High-Speed and Robust KLT Feature Tracker[M]//Image and Video Technology. Springer International Publishing, 2015: 355-367..

[7]Fanzhi K, Xiao X. SIFT-MIC Based Matching Location Algorithm for Wire Bonding[C]//3rd International Conference on Multimedia Technology (ICMT-13). Atlantis Press, 2013:1349-1355.

[8]孫亮,王雙慶.一種基于自適應(yīng)閾值的改進(jìn)MIC算法[J].微電子學(xué)與計(jì)算機(jī),2015,32(5):79-83.

[9]Kang T K, Zhang H, Kim D W, et al. Enhanced SIFT descriptor based on modified discrete Gaussian-Hermitemoment[J].ETRI Journal, 2012, 34(4): 572-582.

[10]Yi J K, Bian G H, Jiang D G. Optimization of scale-invariant feature transform(SIFT) feature extraction[J]. Journal of Beijing University of Chemical Technology, 2013, 40(1): 115-119.

[11]范宗杰,徐向輝.一種基于SIFT算法的SAR圖像配準(zhǔn)方法[J].電子測(cè)量技術(shù),2014,37(8):70-74.

[12]Xing Y, Zhang D, Zhao J, et al. Robust fast corner detector based on filled circle and outer ring mask[J].IET Image Processing, 2016, 10(4):314-324.

[13]Liao B, Xu J, Sun H, et al. Robust Corner Detection Based on Bilateral Filter in Direct Curvature Scale Space[M]//Advances in Swarm and Computational Intelligence. Springer International Publishing, 2015: 357-365.

[14] Peng W, Hongling X, Wenlin L, et al. Harris Scale Invariant Corner Detection Algorithm Based on the Significant Region[J]. International Journal of Signal Processing, Image Processing and Pattern Recognition, 2016, 9(3): 413-420.

[15] Lei Zhang, Kuiyuan Yang, Hongxun Yao. Nested-SIFT for efficient image matching and retrieval[J].MultiMedia, IEEE, 2013, 20(3):34-46.

[16]陶雪焦.改進(jìn)的多尺度Harris亞像素角點(diǎn)檢測(cè)[J].工業(yè)控制計(jì)算機(jī),2016,29(3):50-52.

(責(zé)任編輯：覃華巧)

An Improved Harris Algorithm with Multi Scales

Yang Qiuhui

(College of Information and Electronic Engineering, Wuzhou University, Wuzhou 543002, China)

Traditional algorithms of Harris needs to decide parameter for computing interest values of pixels by experience and the recognition ability for some types of corners is poor. To solve these problems, this paper proposes a corner detection method based on local standard deviation and logarithmic computing. The method decreased the response values of corners near the candidate interested points through computing the logarithms of gradient, so it can detect corners with different types more effectively. And then, according to the statistical features of the standard deviation, it redefines the interest value function. The function could avoid subjectively selecting the value of parameters and it could directly judge whether a candidate interested point is a corner, which makes the algorithm more objective. The experimental results show that the method can effectively detect the corners with various types and it has a more accurate effect of positioning.

Corner detected; Harris algorithm; Standard deviation; Positioning

2016-03-28

國(guó)家自然基金項(xiàng)目(61562074)；廣西高?？茖W(xué)技術(shù)研究項(xiàng)目(KY2015YB290)；梧州學(xué)院科研項(xiàng)目(2011C002)

TP391

A

167-8535(2016)03-0007-07

楊秋慧(1990-),女，河南省信陽(yáng)市潢川縣人，梧州學(xué)院信息與電子工程學(xué)院教師，研究方向：圖像處理。