基于Harris-CPDA的角點檢測算法

胡曉彤，朱博文，程 晨

(天津科技大學 人工智能學院，天津 300457)

0 引 言

在工業(yè)自動化檢測中，特征點檢測被廣泛應用于目標檢測[1]、目標定位[2]、圖像配準、圖像拼接中，該技術減少人為手動調(diào)整，同時能準確反應被檢測物體圖像的重要的特征信息。目前針對提取角點的方式不同可以分為兩大類[3]。

基于圖像灰度變化檢測角點。Harris算法[4]是由Harris和Stephens提出，針對更早期的Moravec算法[5,6]的優(yōu)秀改進型。而針對Harris需人為多次調(diào)整閾值的弊端，提出非極大抑制[7]方式處理。韓松奇等[8]提出針對Harris算法采用非極大抑制時采用雙閾值的方式對不同閾值下的角點進行比對；蘇婷等[9]提出通過二次非極大值抑制，在第一次取極大值點之后，在其基礎上再次選取，相當于選取第二大灰度變化值保留稍大局部里的相應度最大的點；而張見雙等[10]提出將原圖像分割成無重疊子區(qū)域，針對每個單獨子區(qū)域設定單獨閾值，根據(jù)子圖對比度大小從而自適應閾值。

另一類是基于類曲率角點檢測方式。最初由Ronsenfeld和Johnston提出支持域的余弦相似度估計曲率[11]，并在之后提出RJ73算法[12]，用平均K-consine代替原有算法，并且提出曲線上的某一點不能被賦予正確的支撐域大小；此時Mokhtarian和Suomela提出基于曲率尺度空間(curvature scale space，CSS)的角點檢測算法[13]，該算法是在局部上進行檢測角點，再從上至下的高尺度逐漸向低尺度追蹤角點的位置，在不同尺度下進行搜索；為了彌補尺度因子與閾值選取問題，Awrangjeb和Lu提出點到弦距離累加和技術(chord-to-point distance accumulation，CPDA)[14]。

從Zhang等于ECCV上提出在基于圖像細粒度上的分類識別實驗[15]，將整體圖像根據(jù)細粒度分類算法，在不同區(qū)域進行微小的特征分析。由這一思想，本文提出結合改進的Harris-CPDA算法生成關鍵點區(qū)域，從而進行進一步分析。

1 Harris角點檢測算法及其優(yōu)化

1.1 Harris角點檢測的原理

Harris角點檢測的算法可以說是對Moravec算法已有的缺陷問題進行優(yōu)化及改良。Moravec算子實際上是依托一個正方形窗口只計算了8個方向的相鄰像素灰度，同時使用了窗口值，只要在窗口中，權重都設置為1，但其實應當在中心位置賦予更大的權重。后人進行了很多改進的算法，其中Harris算法選取了一個較為平滑的窗口計算了各個方向上的像素灰度變化。圖1(a)為圖像中某一區(qū)域，我們在該局部區(qū)域存在一個窗口；圖1(b)為當前局部區(qū)域各個方向上移動灰度信息并未發(fā)生變化，判定為該窗口區(qū)域并無角點特征；圖1(c)為該平滑窗口在某一特定的方向上移動灰度值發(fā)生變化，而其它方向上并無變化，那么窗口檢測的可能為一條直線線段，其中也無角點的特征；圖1(d)為當該窗口多個方向運動存在不同的灰度值的變化則判定為該平滑窗口區(qū)域可能存在角點特征。

圖1 不同區(qū)域灰度變化的描述

Harris算法獲得各個方向上的灰度變化值。通過一個自相關函數(shù)計算灰度有明顯變化的像素點位置，構造一個與相關函數(shù)相關的矩陣,通過比較構造出的矩陣的特征值可以得到相應的角點位置信息。將窗口平移[u,v]產(chǎn)生的灰度變化為E[u,v]，即

(1)

其中，w(x,y)表示窗口函數(shù)，向量[u,v]表示在某個方向及在其方向上的位移。I(x+u,y+v)表示唯一強度(shifted intensity)。為確定其為角點，通過公式可知，E[u,v]表示圖像上某個方向上的灰度邊度，要取得最大值應保證位移強度取得最大值。由

I(x+u,y+v)=I(x,y)+Ixu+Iyv+o(u2,v2)

得到

記上式最后的結果為Δ，則我們可以推出

(2)

M為2*2的矩陣可由圖像的導數(shù)求得

(3)

其中，窗口函數(shù)為

(4)

這里Ix和Iy為在x和y方向上的導數(shù)，即各自方向上的梯度，w(x,y)窗口函數(shù)為高斯函數(shù)。其本質(zhì)是一個橢圓的函數(shù)。橢圓的曲率大小是由M的特征值λ1與λ2決定的，所以通過比對矩陣M的特征值λ1與λ2，當兩個特征值都很小時，自相關函數(shù)值在各個方向上都很小，說明高斯窗口函數(shù)中的圖像灰度較為平坦；當矩陣M的特征值一個大一個小時，自相關函數(shù)值在某一方向上大，在其它方向上小，則表示檢測到邊緣直線；當矩陣M的特征值都很大，自相關函數(shù)值在所有方向上都增加，表示檢測到了角點。這同時也是對Moravec算子邊緣響應過于敏感做出了改善。

而針對矩陣M的特征值λ1與λ2大小的度量通過定義角點的響應函數(shù)CRF去衡量[1]

R=Det(M)-KTrace2(M)

(5)

其中，Det(M)為矩陣M的行列式，K通常取經(jīng)驗值0.04～0.06，Trace(M)為矩陣M的跡，通過角點相應函數(shù)值與選取的閾值T進行比對得到角點。

為避免K值選取的隨機性，采取角點相應函數(shù)式(5)計算從而選取角點，即

(6)

1.2 改進的Harris算法

當然Harris算法也存在一定的缺陷，一方面是需要人為通過給出多次閾值，計算出圖像中局部極點值即為角點，而閾值過小或過大會造成丟失與偽角點的形成，需要通過多次效果比對，選定一個較為合適的閾值才能得到預期效果角點的檢測。另一方面角點的分布往往在特征值較大的某些區(qū)域，降低閾值產(chǎn)生角點的聚簇的現(xiàn)象，對后面角點的進一步提取造成一定的影響。所以本文采用徐克虎提出的一種自適應非最大抑制的Harris角點檢測算法[16]，實驗結果表明與CPDA共同檢測特征點效果較好。

這種自適應非最大抑制的角點檢測，是先對局部最大值進行從大到小的排序，在這基礎上針對每一個局部最大值設定一個抑制半徑r，為保證準確性該抑制最大值的c= 0.9倍大于抑制半徑內(nèi)的所有值時被添加進待選角點中，當?shù)玫阶銐驍?shù)量角點時停止。

當一個局部最大值R(x,y)i為角點時，應滿足

c·R(x,y)i>R(x,y)j
st(x,y)j∈(x,y)i±r

(7)

其最小抑制半徑為

(8)

2 CPDA角點檢測算法及其優(yōu)化

2.1 CPDA角點檢測的原理

采用尺度曲率空間的CSS算法，低尺度上對邊緣的計算，這樣對圖像中局部的噪聲和變化變得很敏感，會造成一定程度上的誤檢。在較高尺度的高斯函數(shù)進行平滑處理，取局部極大值點作為角點候選點，雖對敏感性進行了一定的緩解，但這樣會造成曲線細節(jié)的丟失，造成定位不精確的問題。

一方面通過CSS算法計算量大，另一方面容易造成誤差。與計算耗時的Harris算法結合起來時耗更長，所以通過計算點到弦的距離來模擬曲度，確定角點的位置，提出采用基于點到弦距離累加和的CPDA算法，如圖2所示。

圖2 CPDA算法點到弦距離累加和原理

邊緣曲線上存在n個像素點，由P1，P2，…，Pn。從弦CL在Pk-LPk的位置開始，計算Pk到弦CL的距離記為dk,k-L，然后弦CL向曲線方向移一個像素到Pk-L+1Ck+1記為CL+1，計算Pk到弦CL+1的距離為dk,k-L+1，依次移動到弦CL在位置PkPk+L結束，求得所有距離的和，即為點Pk到弦CL的距離累加和hL(k)，求得和公式為

(9)

而定義的弦長如果太小，跨度過小會使定位角點錯誤，產(chǎn)生誤檢；弦長定義過大，可能存在將多個曲線峰谷描述成一個角點。所以此時CPDA定義3種不同的弦長長度L,并通過每個點3個曲度歸一化，相乘獲得曲度乘積項。通過曲度乘積項獲取局部最大值作為候選點，首先通過獲取的局部最大值與自適應的曲度閾值進行比較去除偽角點。曲度乘積項公式為

(10)

2.2 改進的CPDA算法

2.2.1 自適應曲度閾值

曲度閾值通常不穩(wěn)定，所以提出與自適應局部曲度閾值進行比較，初步篩選較弱的角點。

自適應局部曲度閾值公式為

(11)

如果局部最大曲率值的絕對值小于公式的閾值，則被舍棄。其中C表示系數(shù)，當C設置為1時，說明沒有角點被舍棄，為一個標準三角形角點；當C設置為2時，得到的是呈凸型的角點，為一個大曲度的圓角點；當C設置為1到2之間時，表示獲取為圓角點，介于平滑與標準三角形角點之間，多適用于各類圖像檢測。其中K用來表示局部曲率的平均值，L1與L2為局部大小。

2.2.2 動態(tài)角點區(qū)域

由CPDA中自適應局部曲度閾值公式可知，L1到L2區(qū)域為動態(tài)角點區(qū)域(region of support)[17]，其定義為從一圖像中的鄰域局部曲率極小值到下一個從候選點到兩端嚴格減少的曲率。本文提出在Harris算法檢測下自適應曲率閾值的基礎上，動態(tài)區(qū)域性的CPDA檢測。動態(tài)角點區(qū)域針對局部細節(jié)檢測精度有較大的提升,在魯棒性上有較大的提升空間[18]。非動態(tài)的弦長，不同跨度產(chǎn)生的角點結果，可能存在漏檢與重復檢測，如圖3所示。

圖3 動態(tài)角點區(qū)域

其中曲線上存在5個不同曲率的標記點，在不同曲率下檢出的效果不相同。當ROS設定過小時，每個標記點都會被認作角點；而當動態(tài)角點區(qū)域設定過大時，所有標記可能會被遺漏。需要動態(tài)設定檢索區(qū)域范圍的值，當檢測標記點2的時候，應當選取標記點1到標記點3之間的區(qū)域，檢測標記點3的時候應當選取標記點2到標記點4之間的區(qū)域，而不選取標記點1到標記點5之間的區(qū)域，從而造成漏檢。通過這種動態(tài)角點區(qū)域選定，可以有效找到角點位置

(12)

經(jīng)分析當∠Ci在160度與200度之間會從候選點中排除。

通常在CSS算法中使用動態(tài)區(qū)域方法，本文將自適應曲度閾值與動態(tài)檢索角點區(qū)域的方法引入CPDA算法中，減少人為設定閾值，在一定程度上減少噪聲對圖像角點檢測效果的影響[19]，提高了CPDA角點檢測算法精度。

3 基于改進算法的圖像局部細粒度特征分析

由圖4可以看出，在整體中不同粒度下包含了不同層次的圖像信息，在不同的定位下提取不同粒度的特征信息最終合并生成多粒度特征。

通過細粒度圖像分類思想可以看出無論是在人工標注圖像關鍵區(qū)域的強監(jiān)督學習下，還是通過注意力機制的弱監(jiān)督學習下，都是通過定位分類進行細小特征差分化分析。所以提出通過本文提出算法實現(xiàn)粗定位實現(xiàn)感興趣區(qū)域的描述，針對該區(qū)域形成8*8的圖像鄰域，在全局中通過區(qū)域中的局部特征進行特征點定位分析。這有利于多尺度圖像及細微差距特征的圖像分類與識別。

圖4 不同粒度下的粗定位

4 算法及流程

主體是通過文獻提及的自適應非最大抑制的Harris算法檢測出可能存在的角點，包含大量偽角點及重復角點，基于這些候選角點通過改進的CPDA算法的曲率自適應比較變換計算進行再次篩選，最終得到準確的區(qū)域，在該區(qū)域內(nèi)進行特征點的定位分析。

(1)通過角點響應函數(shù)計算每個像素的響應值，獲得初次篩選下的局部最大值點，記錄相應坐標及編號。

(2)針對所有局部最大值點進行由大到小的順序進行排序，相同的值時依據(jù)初次篩選下記錄的編號進行排序。

(3)根據(jù)設定的最小抑制半徑r逐漸縮小半徑，對已有排序后的局部最大值進行二次篩選，得到非最大抑制下的第二次篩選下的候選角點。

(4)應用Canny邊緣檢測算子得到圖像邊緣，填充曲線邊緣縫隙，檢測出T型角點，加入第二次篩選的候選點中。

(5)將二次篩選的候選點與T型角點通過曲度乘積公式計算曲率與自適應曲度閾值進行比較去除圓角點，得到第三次篩選結果。

(6)將第三次篩選得到得候選角點通過動態(tài)區(qū)域比對進行角度閾值比較，刪除錯誤角點。同時對歐式距離小于25像素的近鄰T型角點進行刪除操作，符合則并入正確角點集合中，得到最終的特征區(qū)域。

(7)經(jīng)過該算法圖像已經(jīng)得到特征點的粗定位，將粗定位候選區(qū)域作為網(wǎng)絡的輸入端，在當前像素區(qū)域進行局部的特征學習，經(jīng)過多粒度的網(wǎng)絡得到融合特征。

5 實驗結果及性能評價

相關算法實驗采用Windows XP系統(tǒng)，處理器為Intel(R) Core(TM) i5，2.60 GHz,可用內(nèi)存為3.26 GB。本文算法基于改進的Harris-CPDA算法主要與典型Harris算法、非極大抑制下的Harris算法、CPDA算法進行實驗結果與性能評價。經(jīng)典的Harris算法與CPDA算法在不同的閾值區(qū)間下檢測效果各不相同，所以通過設置3種不同的閾值區(qū)間[0，20]、[20，50]、[50，80]與本文算法進行實驗比對。實驗圖片方面，圖片工件選擇單個工件，單個工件不同種類與多種類工件混合進行對照實驗。

5.1 檢測性能評估

角點檢測的評估，本文首先依據(jù)Mokhtarian提出的角點數(shù)一致性(consistence of corner numbers，CCN) 的概念[20]

CCN=100%×1.1-|Nt-NO|

(13)

其中，CCN數(shù)值越大，表明角點檢測效果越好。基于式(13)基礎上，提出3種不同點的檢測效果，正確檢測、誤檢測、漏檢測。其中Nt為變換后檢測角點數(shù)目，Nc為原始圖像檢測角點數(shù)目。而人為選取特征點并不具有客觀性，所以Awrangjeb等提在CCN基礎上提出平均重復率(ave-rage repeatability)與定位誤差(localization error)[21]

(14)

(15)

其中，Nm為圖形變換前后都存在的特征點，(xoi,yoi)和(xti,yti)為變換圖像與原圖像相應角點的坐標位置，相差3個像素以內(nèi)為匹配的特征點。

5.2 多閾值實驗分析

這里以圖5中3幅實驗圖片為例，選取單一不同種，與多種模型混合情況實驗。

圖5 算法測試實驗用圖

這里依據(jù)CCN式(13)及準確率式(14)與定位誤差式(15)提出，在準確角點范圍內(nèi)，合格率是指在檢出角點中有效角點所占實際角點的比例，漏檢率是指未檢測出來角點的比例，誤檢率是指多余的干擾點與重復點的比例。

通過實驗分析，由其不同閾值下的數(shù)據(jù)如表1所示可以直觀發(fā)現(xiàn)，Harris算法在閾值為[0.2,0.5]區(qū)間內(nèi)效果最佳，中間閾值強度在合格率方面介于其它兩種閾值中間，漏檢率與誤檢率也處在中間，相對其它兩種閾值強度較為均衡。所以確定Harris算法在該區(qū)間與本文算法進行比對。同樣CPDA算法在canny算法邊緣檢測中選取閾值范圍在[0.2,0.5]取得較好的結果，其數(shù)據(jù)見表2。

5.3 傳統(tǒng)算法對比結果

通過圖6(a)、圖6、(d)、圖6 (g)可以看出，Harris算法檢測出來點的數(shù)量很多，但相應存在很多誤檢與漏檢的特征點；而圖6(b)、圖6(e)、圖6(h)CPDA算法在曲率確定上帶有模糊性，大曲率與小曲率是否劃定為特征點為漏檢的主要原因；本文算法完善了Harris與CPDA算法的缺陷，在特征點檢測上有良好效果。

表1 Harris算法多閾值分析/%

表2 CPDA算法多閾值分析/%

而從局部圖7來看，圖7(b)、圖7(c)相應的Harris算法檢測偽角點仍舊過多，其基于灰度在灰度變化區(qū)域敏感，容易認定為角點；圖7(d)、圖7(e)基于曲率的CPDA算法在工件內(nèi)部的特征點檢測并不敏銳；圖7(f)為提出的算法,其檢測特征點準確，同時在工件內(nèi)部檢測表現(xiàn)良好。

從實驗結果數(shù)據(jù)與實驗結果圖來看，可以看出Harris算法在檢測方面，傾向于大而全，在角點檢測數(shù)量上較多，非常全面，細節(jié)上也會采用較多角點去表示，因為數(shù)量較多所以存在較少的漏檢角點，但同時帶來的是一個特征用多個重復角點表述；典型的CPDA算法針對邊界檢測效果相對于Harris算法較好，但其多受限于邊界的閾值效果，對于工件的內(nèi)部細節(jié)特征找的不夠詳細，同時也受限于檢測步長，跨度大小不能適應性調(diào)整也是局限了多尺度下的角點檢測，在圓角點的區(qū)分還是相對模糊。

通過表3與表4分析可以看出本文算法在保證檢測角點正確數(shù)量的同時，針對Harris系算法在CCN計算下合格率上有7%的提升，漏檢率提升30%，誤檢率方面也有50%以上的提升，在CCN計算上的準確率上更有40%的提高，定位誤差減少了0.3個像素；針對CPDA算法來看有小幅提升，著重在特征點的漏檢率方面有了40%以上的提升，誤檢率上30%的提升并降低了特點的定位誤差。而通過表5可以看出比Harris系算法時間提升0.8 s，比CPDA算法花費時間小幅降低。在改善相應的缺陷同時，在時效上比Harris系算法與CPDA算法有了較大的提升。

圖6 整體檢測效果展示

圖7 局部檢測效果展示

表3 角點CCN檢測數(shù)據(jù)對比/%

表4 角點檢測重復率與定位誤差數(shù)據(jù)對比

表5 算法運行時間(以圖6為例)

5.4 多粒度下的實驗對比結果

為方便觀察，選取圖5(a)中的軸類零件及相應自標定數(shù)據(jù)集，經(jīng)過校正之后原圖像通過本文提出的改進Harris-CPDA算法生成一個特征點的粗定位，針對不同的關注度得到不同細粒度下的特征信息，相比于強監(jiān)督學習，減少人為標注同時提高準確度。本文選取與Part-based R-CNNs進行對比性實驗，針對這種強監(jiān)督學習可以分為兩部分定位與識別，其在大規(guī)模數(shù)據(jù)集中有良好的表現(xiàn)，而在工業(yè)上數(shù)據(jù)集較少，兩者選取自標定數(shù)據(jù)集進行測試。

從圖8(a)、圖8(c)可以看出Part-based R-CNNs算法存在框選錯誤，光線及角度的改變對其判定產(chǎn)生一定的干擾，致使誤差；相比與本文提出的算法圖8(b)、圖8(d)與深度學習有很好的結合性，對于不同場景下的檢測，有較強的魯棒性。

圖8 本文算法與Part-based R-CNNs效果對比

定位上來說Part-based R-CNNs的Selective Search會在一張圖片生成較多的候選區(qū)域，會產(chǎn)生大量的無關區(qū)域,增加了運行時間，同時定位的準確程度是建立在多候選區(qū)域之上，與本文提出算法相比并不理想,通過表6與表7可以看出，相比于有Bounding box的基礎上,定位的準確性上提升了16%左右。針對于分類在準確性上也有近5%的提升。為了展示分類效果選取環(huán)類工件，展示定位效果以軸類零件展示，如圖8，針對環(huán)型工件區(qū)分內(nèi)外環(huán)分類定位，對于軸類工件以特征區(qū)域及整體進行分類定位。

表6 與Part-based R-CNNs定位數(shù)據(jù)對比

表7 與Part-based R-CNNs分類數(shù)據(jù)對比

6 結束語

本文首先介紹了基于兩種不同方法角點檢測算法的基本構成及現(xiàn)狀，針對Harris算法采用文獻提及的非最大抑制的方法進行處理，一定程度上減少閾值強度對其影響，此時檢測角點重復點數(shù)量較多，存在一定的誤檢點。同時針對CPDA算法提出自適應曲率閾值的方法，去除圓角點，而針對相對單一化的步長，不能檢測多尺度下的角點，采用動態(tài)角點區(qū)域的方式不斷迭代排除偽角點。

而通過本文提出的基于灰度與基于曲率的兩種角點檢測結合提出改進的Harris-CPDA算法。實驗結果表明在保證較多的正確角點檢測的前提下，減少了單一位置重復的特征描述，相比于Harris算法與CPDA算法在檢測精度方面有了較大的提升。而通過傳統(tǒng)方法針對圖像進行粗定位，與圖像的細粒度的結合，使圖像在多尺度與監(jiān)督學習方向上的微小特征的定位有了進一步的提升，這種融合提升了特征的表達能力。