對Freeman鏈碼分析的角點檢測算法①

劉相湖, 王 濤, 張小哲

(華南師范大學 計算機學院,廣州 510631)

圖像中的角點是圖像的重要特征,具有旋轉不變性,決定了圖像形狀,可以降低圖像信息的存儲效率,在目標跟蹤,目標檢測,圖像匹配,圖像輪廓擬合等領域都有重要的應用價值. 近幾十年來,國內外學者提出的圖像角點檢測算法[1],各有各的優缺點,大致可分為三大類：基于灰度強度的角點檢測、基于模型的角點檢測、基于邊緣輪廓的角點檢測[1]. 基于灰度強度的方法是通過圖像的一階或二階導數查找,經典算法代表有Harris算法[2],Harris算法通過微分運算和自相關矩陣來檢測角點,穩定性高,但是高斯平滑函數的窗口可控性差,定位精度較差[3].基于模型的方法是通過將一小塊圖像與預定義的模型相匹配來查找角點,SUSAN算法[4]就是這類角點檢測的代表,SUSAN通過一個圓形模板實現角點檢測,通過模板中所有與圓心點像素相似的點組成的區域大小判斷角點,該算法不對圖像求導,精度較好,具有一定的抗噪性,但是相似函數計算較復雜,且需要人工設定閾值[4]. 基于邊緣輪廓的方法主要是通過分析圖像邊緣形狀來檢測角點的,包括五個步驟[1]：邊緣提取和選擇、曲線平滑、曲率估計、檢測角點和角點跟蹤篩選出最終的角點. 近年來,基于邊緣輪廓方法吸引了廣泛的關注,許多此類優秀的角點檢測算法被提出[5].1998年Mokhtarian等人提出的著名CSS角點檢測算法[4],利用Canny邊緣檢測算子提取圖像邊緣,從邊緣中提取邊緣輪廓,并填充邊緣輪廓缺口,在大尺度下得到輪廓曲率極大值點,通過閾值選定候選角點,大尺度到小尺度下對候選角點重新定位,比較T-角點與曲率極大值檢測的角點,剔除相距相近的點,該算法獲得良好的角點檢測效果. 但CSS有兩個主要的問題[6],一是曲率估計對對輪廓局部變化和噪聲較為敏感,二是很難選擇合適的高斯尺度平滑邊緣輪廓. 在CSS基礎上,通過考慮檢測中局部曲率,He和Yung[7]提出了一種使用自適應曲率閾值和動態支撐區域的檢測器. 隨后Awrangjeb和Lu利用點到弦的距離累加技術提出了一種穩健的角點檢測算法——CPDA[8],CPDA具有較高的可重復性和較低的定位誤差. 之后又提出了CPDA的快速算法[9].但CPDA有一個缺點是估計拐角的曲率值與角度可能不成正比[5]. 還有一些角點檢測算法,利用Freeman鏈碼多邊形近似方法查找角點,兩邊的交點判定為角點[1],文獻[10]對疑似角點統計鏈碼做進一步篩選角點,但文獻中的方法先使用的是CSS角點檢測算法,仍有曲率計算和角點閾值選取問題,并且時間復雜度較高; 文獻[11]通過判斷待定角點前后三個點的Freeman鏈碼是否相同進行檢測,該方法造成錯誤角點較多,且文中方法過于繁瑣.

本文在文獻[10,11]的啟發下,優化文獻[11]的鏈碼分析方法,同時引入文獻[10]的鏈碼統計思路,提出一種新的角點檢測算法：提取圖像邊緣輪廓Freeman鏈碼,分析鏈碼發生變化時連續多個點的碼值是否符合一定的規則來判定角點. 該算法將鏈碼分析和鏈碼統計相結合,不僅使得算法變得更加簡便,而且避免了傳統方法中輪廓曲率計算和閾值選取,通過實驗結果得出本文算法對于圖像角點檢測結果準確性高,具有良好穩健性.

1 Freeman鏈碼生成

1.1 圖像預處理

本文圖像在預處理方面與文獻[5]一致采用Canny算法[12]檢測邊緣,Canny算法抑制了多響應邊緣,提高邊緣的定位精度,具有一定的抗噪能力. Canny算法檢測邊緣的步驟如圖1.

圖1 Canny邊緣檢測步驟

1.2 Freeman鏈碼

鏈碼是通過帶有給定方向的單位長度的線段序列來描述輪廓的邊界,鏈碼的表示方法有基于4-鄰接和8-鄰接[12],如圖2(a)和圖2(b)所示,8-鄰接鏈碼比4-鄰接鏈碼增加了4個斜方向,而較多的基于Freeman鏈碼的算法[10-13]都采用8-鄰接來表示鏈碼. 在實際應用中,邊界跟蹤法[12]產生輪廓的鏈碼,4-鄰接檢測邊界只需要搜索4個方向,8-鄰接則需要搜索8個方向,我們實驗所用圖都是點陣圖,當輪廓是一條直線時,4-鄰接鏈碼要比8-鄰接鏈碼要快捷的多; 當輪廓是一條斜邊時,用4-鄰接鏈碼只能搜索上下左右4個方向,表示輪廓時會丟失大量的邊緣信息,而8-鄰接鏈碼正好與像素點的實際情況相符,能夠準確地描述中心像素點與其鄰接點的信息,能較好地保留輪廓邊緣信息. 因為任意一個像素周圍均有8個鄰接點,因此本文算法采用的是8-鄰接鏈碼.

圖2 鏈碼示意圖

1.3 輪廓跟蹤得到Freeman鏈碼

基于八鄰域邊界跟蹤可以得到輪廓的Freeman鏈碼,輪廓跟蹤[13]方法如算法1.

通過上述輪廓跟蹤算法就得到了邊緣輪廓的Freeman鏈碼,我們假定逆時針為正方向,分輪廓將輪廓點坐標和鏈碼值存儲,存儲FMP格式有如下的定義：

2 對Freeman鏈碼方向分析進行角點檢測

文獻[11]通過對真實角點周圍的幾個點的Freeman鏈碼分析,文中分析出要想成為一個真實角點,分情況討論了前后連續的三個點的鏈碼值是否相同,相同則為角點,不相同則不是角點,但這樣檢測出角點誤檢漏檢點較多,且分析方法較為繁瑣; 而文獻[10]在改進CSS角點檢測之后利用鏈碼統計思路,統計疑似角點周圍幾個點的鏈碼值相同的點數再做進一步的判斷,較好地排除了一些錯誤角點,但算法時間復雜度較高,依然存在曲率計算和閾值選取問題. 本文算法在鏈碼分析上做了較大的改善,同時結合了鏈碼統計思路,提出了鏈碼分析規則1 . 如圖3所示,A點有可能是角點,A的鏈碼值為7,此時有4種情況：如果B點之后的鏈碼序列是{00000},那么A點就不是角點,視為一條斜線的一點; 如果B點之后的序列是{77777},那么A點視為兩條夾角為135°的直線的交點,如果B點之后的序列是{66666},那么A點也視為兩條夾角為90°的直線的交點;如果B點之后的序列是{55555},那么A點也視為兩條夾角為45°的直線的交點,后3種情況都是角點,這里的4種情況包含了文獻[11]中提及的所有情況的分析.

圖3 疑似角點周圍點的方向

由于A點的鏈碼值為7,角點符合上述3種情況的鏈碼序列值分別為7,6,5. 綜上總結,本文提出下述規則.

規則1. 如果某一個真實角點存在,那么它的前后幾個點的鏈碼方向與它的鏈碼方向夾角都是小于或者等于 90°.

2.1 算法基本思路

本文算法角點檢測思路如下：

(1) Canny算法進行圖像邊緣檢測;

(2)輪廓跟蹤法得到輪廓的Freeman鏈碼;

(3)根據圖像輪廓點的鏈碼,求出該輪廓所有點的鏈碼差di[11];

(4)對于凸起或者凹陷處輪廓點進行鏈碼修復;

(5)分析鏈碼發生變化的點的周圍多個鏈碼：(a)對于di=±3的輪廓點判定為角點; (b)對于di=±1或±2的輪廓點判斷附近多個點的鏈碼值是否符合上述規則1.

2.2 算法具體描述

2.2.1 計算輪廓鏈碼差

輪廓鏈碼差[11]即輪廓曲線上的點和它的前一個點的鏈碼方向之差,定義數組di,存儲兩個點的鏈碼差,令f(i)=ai-ai-1,則整個輪廓的di數學計算公式定義：

其中di為正表示正方向(逆時針),為負表示反方向(順時針).

計算得到的di表示前后兩點輪廓之間的關系[13]：

(1)di=±1表示前后兩個方向夾角為銳角45°;

(2)di=±2表示夾角為直角90°;

(3)di=±3表示夾角為鈍角135°;

(4)di=±4表示夾角為直線180°;

(5)di=0表示前后兩個方向夾角0°,不發生變化,將不做下面的討論范圍.

2.2.2 凸起點鏈碼修復

在輪廓曲線中,由于噪聲使得在輪廓查找中或多或少有些像素點出現誤差. 例如原本一段直線中某像素點突然的凸起或者凹陷,會造成角點檢測錯誤或漏檢,需要將鏈碼進行修復. 如圖4,為了便于計算,這里只是進行鏈碼簡單修復.

圖4 輪廓的凸起點

處理過程：判斷變化點是否為凸起點,若為凸起點,則進行鏈碼修復,并修改對應的di值. 對每一條輪廓循環查找.

為了修復凸起點的鏈碼,設計了算法2.

2.2.3 根據鏈碼差分析出角點

循環判斷di是 否等于0,如果不等于0,說明前后兩點的鏈碼值發生了變化,初步認定為疑似角點,根據1.2可知,我們這里把點i- 1的鏈碼到點i的鏈碼變化定義為：ai-1→ai. 對疑似角點的前后相鄰多個點鏈碼值進行分析,設置相鄰因子NF,同時為了彌補圖像的邊緣丟失和滿足一定的曲線的曲率變化,設置相同點數(鏈碼與變化前后相同的點數)S,輸出的角點存儲到vecCorner中.

對所有輪廓FMP的每一條輪廓(FMP[index].size>20,index表示輪廓索引號)循環查找角點. 對輪廓FMP[index]的鏈碼差計算和鏈碼修復完成后,再重新對該輪廓循環查找角點,對鏈碼差分分以下3種情況討論,設置標記數Q12=0：

(1)若di=±3; 則該點Pi被判定為角點,Q12=NF;

(2)若di=±2; 循環觀察該點Pi輪廓前NF個點和點Pi輪廓后NF個點的鏈碼,如圖6,即pre_dirs={ai-2,ai-3,···,ai-NF-1}和d i r s={ai+1,ai+2,···,ai+NF},計 算pre_dirs與ai相 同的個數和dirs與ai-1相同的個數之和num,若num≤S,Q12=NF;

(3)若di=±1; 對di=1和di=-1分析. 分別計算與ai-1和ai的鏈碼方向的夾角小于等于90°的鏈碼集合.

1)當di=1,即鏈碼變化前后為逆時針旋轉. 以如下計算方法得到的值存入數組K1和K2中：

計算ai-1的順時針方向的兩個鏈碼組成數組K1,即K1={ai-1,ai-1-1,ai-1-2};

計算ai的逆時針方向的兩個鏈碼組成數組K2,即K2={ai,ai+1,ai+2}.

例如 0 →1逆時針方向變化：計算0的順時針方向的兩個鏈碼分別為7和6,組成數組K1= { 0,7,6}; 計算1的逆時針方向的兩個鏈碼分別為2和3,組成數組K2= { 1,2,3},如圖5(a).

圖5 方向分析示意圖

2)當di=-1,即鏈碼變化前后為順時針旋轉. 以如下計算方法得到的值存入數組K1和K2中：

計算ai-1的逆時針方向的兩個鏈碼組成數組K1,即K1={ai-1+1,ai-1+1,ai-1+2};

計算ai的順時針方向的兩個鏈碼組成數組K2,即K2={ai,ai-1,ai-2}.

例如 0 →7順時針方向變化：計算0的逆時針方向的兩個鏈碼分別為1和2,組成數組K1= { 0,1,2}; 計算0的順時針方向的兩個鏈碼分別為7和6,組成數組K2={ 0,7,6},如圖5(b).

上述得到K1和K2數組后,再進行如下運算：對于該點Pi的輪廓前面NF個點的鏈碼,如圖6,即pre_dirs= {ai-2,ai-3,···,ai-NF-1}和該點Pi的輪廓后面NF個點的鏈碼,如圖6,即dirs= {ai+1,ai+2,···,ai+NF},計算pre_dirs在數組K1中存在相同鏈碼的個數N1和dirs在數組K2中存在相同鏈碼的個數N2,滿足N1+N2≥2NF-S,則Q12=NF.

圖6 疑似角點輪廓前后鏈碼示意圖

選擇執行完上述3種情況后,角點的判定條件是：Q12==NF,若滿足此條件的點再與vecCorner[index]里的角點比較輪廓差,若相差小于NF,則與它最近的角點位置取中間位置作為新角點,且該點只能比較一次;若相差大于等于NF,則直接判定為角點,存入vecCorner[index].

3.3 算法復雜度分析

本文算法在角點檢測部分主要是分情況分析鏈碼方向,對疑似角點的周圍幾個點的鏈碼值進行分析比較,不涉及乘除法運算和曲率運算,算法角點檢測部分計算量較少,計算過程是分輪廓計算,得到的角點也是分輪廓存儲. 本文算法的角點檢測部分(不包括輪廓跟蹤部分)的時間復雜度為 O (n),空間復雜度為 O (n),其中n為所有輪廓的總點數.

3 實驗結果分析

為了驗證本文算法的有效性和準確性,實驗在PC(Inter(R) Core(TM) i5-3450 CPU @ 3.10GHz,8G內存)機上利用MATLAB R2014b進行實驗,與基于邊緣輪廓法影響較廣且較新的一些算法：ARCSS[14],CPDA[8],Fast-CPDA[9]和 He&Yung[7]做比較. 實驗所用圖和參考圖均來自文獻[15-18],如圖7所示為角點參考圖,其中兩幅二值圖,兩幅實物灰度圖.

圖7 本文實驗所用圖

3.1 準確性實驗

本文先以精確度ACU評估五種角點檢測算法的準確性[17]. 假設N0是原始圖像中的真實角點,Na是算法檢測出的正確角點數,Nt是算法從原始圖像檢測出的角點數. 另外,如果檢測到的最小距離小于或者等于所設定的距離閾值(本文設置為4,即4個像素的距離),則判斷該角點檢測正確[19]. 精確度ACU定義如下：

為了對比的公平性,在比較過程中,五種算法在提取邊緣輪廓選取相同參數,均采用Canny算法,低閾值L=0.2,高閾值H=0.35,檢測時選取算法檢測最優結果時的參數[1]進行實驗比較. 本文算法參數設置：相鄰因子NF=6,相同點S=2. 對飛機檢測結果如圖8,具體結果如下表1.

圖8 各算法對飛機圖像的角點檢測

表1 準確性實驗結果

由圖8和表1可以看出,ARCSS、CPDA和Fast-CPDA檢測到的錯誤角點較少,但是丟失角點都較多;雖然He&Yung檢測到的角點最多,但是錯誤角點也是最多的,而本文算法檢測到的丟失角點與錯誤角點之和最少,四幅圖的平均準確率也是最高,可以看出本文算法具有良好的角點檢測準確性.

3.2 穩定性實驗

為了驗證算法在圖像變換下的魯棒性,實驗利用圖7的四幅基礎圖建立一個數據集,經過如下變換[15]：

(1)旋轉變換：旋轉角度區間為[-90°,+90°],每10°旋轉一次,除 0°之外;

(2)等比例尺度變換：尺度因子變化區間為[0.5,2],以0.1逐步增加,除1.0之外;

(3)非等比例尺度變換：x的變換范圍為[0.7,1.5],y的變換范圍為[0.5,1.8],以0.1逐步增加,除了都為1.0;

(4)組合變換：角度旋轉區間為[-30°,+30°],每10°旋轉一次,除0°外; 圖像橫縱坐標x,y變換范圍：[0.8,1.2],以0.1為單位逐步增加,其中x,y都為1.0除外;

(5)添加噪聲：噪聲范圍[0.005,0.05],以 0.005 為單位逐步添加零均值高斯白噪聲.

圖像變換實驗時,以平均重復率(AR)和定位誤差(LE)來評價角點檢測算法[15]. 假設N0是算法檢測初始圖像的角點個數,NT是算法檢測變換后圖像的角點個數,Nr是兩者重復的角點個數. 則平均重復率為：

平均重復率越高,說明算法在越穩定. 定位誤差為：

其中,(x0i,y0i)和(xti,yti)分別為初始圖像和變換后圖像位置的第i個重復的角點. 這里,如果兩點相差的距離不大于4個像素,則認為它們是重復的[19]. 如圖9是上述5種變換下各算法的AR和LE.

從圖9可以看出,本文算法在除了旋轉變換和組合變換下平均重復率不及He&Yung和Fast-CPDA,其他變換下平均重復率都要高于其他算法; 不過定位誤差要高于CPDA、Fast-CPDA和He&Yung算法. 最終的平均值如表2.

由表2可以看出,本文算法在定位誤差方面雖然沒有CPDA、Fast-CPDA和He&Yung算法好,但要好于ARCSS,并且本文算法在5個檢測算法具有最高的平均重復率,說明本文算法具有良好的角點檢測穩健性.

圖9 5種變換下各算法的AR和LE

表2 穩定性實驗比較結果

此外,本文提出的相鄰因子NF和相同點S在圖像的等比例尺度變換時可以與尺度因子等比例增減. 實驗過程中,為了實驗對比的公平性,本文沒有采用等比例NF和S,都以不改變NF和S進行角點檢測實驗. 在實際應用中,圖像執行等比例尺度變換時,可以采用等比例增減NF和S進行角點檢測,效果更佳.

3.3 算法運行時間實驗

我們記錄上述五種算法運行圖7中4幅圖所耗費時間,分別運行10次,然后計算平均運行時間(除去統一使用的Canny算法運行時間). 運行時間如表3

表3 五種角點檢測算法運行時間(單位：s)

由表3可以得出,He&Yung運行時間最快,本文算法運行時間稍長于Fast-CPDA、He&Yung和CPDA,主要在輪廓跟蹤得到鏈碼部分耗時較多.

通過以上3種實驗對比分析,He&Yung運行時間最快,Fast-CPDA算法定位誤差最低,但本文算法的角點準確率和平均重復率都是最高的,且本文算法不需要閾值選取.

4 結束語

本文提出一種基于Freeman鏈碼方向分析的角點檢測算法,通過巧妙地分析鏈碼方向,計算鏈碼發生變化時周圍多個鏈碼的值是否在一定的數組中來判定角點,而不需要經過傳統的曲線曲率計算檢測角點,同時避免了閾值選取的問題,實驗結果得出本文算法在角點檢測時具有良好的檢測準確性和穩健性,角點存儲分輪廓具有順序性,算法很好理解,角點檢測部分時間復雜度小. 不過在算法前期需要鏈碼的提取,使得算法運行時間要比He&Yung、Fast-CPDA、CPDA算法稍長,另外,本文算法在組合變換中檢測角點不夠理想,在以后工作中會加以改進.

1 Awrangjeb M,Lu GJ,Fraser CS. Performance comparisons of contour-based corner detectors. IEEE Transactions on Image Processing,2012,21(9)：4167-4179. [doi：10.1109/TIP.2012.2200493]

2 Harris C,Stephens M. A combined corner and edge detector.Proceedings of the 4th Alvey Vision Conference.Manchester,England. 1988. 147-151.

3 洪改艷,芮廷先,俞偉廣,等. Harris角點檢測的優化算法.計算機系統應用,2017,26(4)：169-172.

4 章為川,孔祥楠,宋文. 圖像的角點檢測研究綜述. 電子學報,2015,43(11)：2315-2321. [doi：10.3969/j.issn.0372-2112.2015.11.026]

5 Zhang WC,Shui PL. Contour-based corner detection via angle difference of principal directions of anisotropic Gaussian directional derivatives. Pattern Recognition,2015,48(9)：2785-2797. [doi：10.1016/j.patcog.2015.03.021]

6 李云紅,姚韻,賈利娜. 基于圖像輪廓的角點檢測算法. 計算機與數字工程,2016,44(10)：2015-2019. [doi：10.3969/j.issn.1672-9722.2016.10.032]

7 He XC,Yung NHC. Corner detector based on global and local curvature properties. Optical Engineering,2008,47(5)：057008. [doi：10.1117/1.2931681]

8 Awrangjeb M,Lu GJ. Robust image corner detection based on the chord-to-point distance accumulation technique. IEEE Transactions on Multimedia,2008,10(6)：1059-1072. [doi：10.1109/TMM.2008.2001384]

9 Awrangjeb M,Lu GJ,Fraser CS,et al. A fast corner detector based on the chord-to-point distance accumulation technique.Proceedings of 2009 Digital Image Computing：Techniques and Applications. Melbourne,VIC,Australia. 2009. 519-525.

10 曾接賢,李煒燁. 曲率尺度空間與鏈碼方向統計的角點檢測. 中國圖象圖形學報,2014,19(2)：234-242.

11 黃瓊丹. 一種基于輪廓分析的圖像特征點檢測方法. 微計算機信息,2009,25(25)：123-125. [doi：10.3969/j.issn.1008-0570.2009.25.051]

12 Sonka M,Hlavac V,Boyle R. 圖像處理、分析與機器視覺.興軍亮 艾海舟,譯. 4版. 北京：清華大學出版社,2016.97-106.

13 吳桐樹,張瑞林,鄒敏. 基于Freeman鏈碼的B樣條曲線輪廓擬合. 計算機系統應用,2014,23(8)：130-134.

14 Awrangjeb M,Lu GJ,Murshed M. An affine resilient curvature scale-space corner detector. Proceedings of 2007 IEEE International Conference on Acoustics,Speech and Signal Processing. Honolulu,HI,USA. 2007. I-1233-I-1236.

15 Zhang SZ,Yang D,Huang S,et al. Robust corner detection using the eigenvector-based angle estimator. Journal of Visual Communication and Image Representation,2017,45：181-193. [doi：10.1016/j.jvcir.2017.01.020]

16 Xing YX,Zhang DY,Zhao JH,et al. Robust fast corner detector based on filled circle and outer ring mask. IET Image Processing,2016,10(4)：314-324. [doi：10.1049/ietipr.2014.0952]

17 徐玲. 基于圖像輪廓的角點檢測方法研究[博士學位論文].重慶：重慶大學,2009.

18 李冬晴. 圖像角點檢測算法與測評技術研究[碩士學位論文]. 蘇州：蘇州大學,2015.

19 趙亞利,章為川,李云紅. 圖像邊緣輪廓自適應閾值的角點檢測算法. 中國圖象圖形學報,2016,21(11)：1502-1514.[doi：10.11834/jig.20161110]