對(duì)Freeman鏈碼分析的角點(diǎn)檢測(cè)算法①

劉相湖, 王 濤, 張小哲

(華南師范大學(xué) 計(jì)算機(jī)學(xué)院,廣州 510631)

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

本文在文獻(xiàn)[10,11]的啟發(fā)下,優(yōu)化文獻(xiàn)[11]的鏈碼分析方法,同時(shí)引入文獻(xiàn)[10]的鏈碼統(tǒng)計(jì)思路,提出一種新的角點(diǎn)檢測(cè)算法：提取圖像邊緣輪廓Freeman鏈碼,分析鏈碼發(fā)生變化時(shí)連續(xù)多個(gè)點(diǎn)的碼值是否符合一定的規(guī)則來(lái)判定角點(diǎn). 該算法將鏈碼分析和鏈碼統(tǒng)計(jì)相結(jié)合,不僅使得算法變得更加簡(jiǎn)便,而且避免了傳統(tǒng)方法中輪廓曲率計(jì)算和閾值選取,通過(guò)實(shí)驗(yàn)結(jié)果得出本文算法對(duì)于圖像角點(diǎn)檢測(cè)結(jié)果準(zhǔn)確性高,具有良好穩(wěn)健性.

1 Freeman鏈碼生成

1.1 圖像預(yù)處理

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

圖1 Canny邊緣檢測(cè)步驟

1.2 Freeman鏈碼

鏈碼是通過(guò)帶有給定方向的單位長(zhǎng)度的線段序列來(lái)描述輪廓的邊界,鏈碼的表示方法有基于4-鄰接和8-鄰接[12],如圖2(a)和圖2(b)所示,8-鄰接鏈碼比4-鄰接鏈碼增加了4個(gè)斜方向,而較多的基于Freeman鏈碼的算法[10-13]都采用8-鄰接來(lái)表示鏈碼. 在實(shí)際應(yīng)用中,邊界跟蹤法[12]產(chǎn)生輪廓的鏈碼,4-鄰接檢測(cè)邊界只需要搜索4個(gè)方向,8-鄰接則需要搜索8個(gè)方向,我們實(shí)驗(yàn)所用圖都是點(diǎn)陣圖,當(dāng)輪廓是一條直線時(shí),4-鄰接鏈碼要比8-鄰接鏈碼要快捷的多; 當(dāng)輪廓是一條斜邊時(shí),用4-鄰接鏈碼只能搜索上下左右4個(gè)方向,表示輪廓時(shí)會(huì)丟失大量的邊緣信息,而8-鄰接鏈碼正好與像素點(diǎn)的實(shí)際情況相符,能夠準(zhǔn)確地描述中心像素點(diǎn)與其鄰接點(diǎn)的信息,能較好地保留輪廓邊緣信息. 因?yàn)槿我庖粋€(gè)像素周?chē)?個(gè)鄰接點(diǎn),因此本文算法采用的是8-鄰接鏈碼.

圖2 鏈碼示意圖

1.3 輪廓跟蹤得到Freeman鏈碼

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

通過(guò)上述輪廓跟蹤算法就得到了邊緣輪廓的Freeman鏈碼,我們假定逆時(shí)針為正方向,分輪廓將輪廓點(diǎn)坐標(biāo)和鏈碼值存儲(chǔ),存儲(chǔ)FMP格式有如下的定義：

2 對(duì)Freeman鏈碼方向分析進(jìn)行角點(diǎn)檢測(cè)

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

圖3 疑似角點(diǎn)周?chē)c(diǎn)的方向

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

規(guī)則1. 如果某一個(gè)真實(shí)角點(diǎn)存在,那么它的前后幾個(gè)點(diǎn)的鏈碼方向與它的鏈碼方向夾角都是小于或者等于 90°.

2.1 算法基本思路

本文算法角點(diǎn)檢測(cè)思路如下：

(1) Canny算法進(jìn)行圖像邊緣檢測(cè);

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

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

(4)對(duì)于凸起或者凹陷處輪廓點(diǎn)進(jìn)行鏈碼修復(fù);

(5)分析鏈碼發(fā)生變化的點(diǎn)的周?chē)鄠€(gè)鏈碼：(a)對(duì)于di=±3的輪廓點(diǎn)判定為角點(diǎn); (b)對(duì)于di=±1或±2的輪廓點(diǎn)判斷附近多個(gè)點(diǎn)的鏈碼值是否符合上述規(guī)則1.

2.2 算法具體描述

2.2.1 計(jì)算輪廓鏈碼差

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

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

計(jì)算得到的di表示前后兩點(diǎn)輪廓之間的關(guān)系[13]：

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

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

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

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

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

2.2.2 凸起點(diǎn)鏈碼修復(fù)

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

圖4 輪廓的凸起點(diǎn)

處理過(guò)程：判斷變化點(diǎn)是否為凸起點(diǎn),若為凸起點(diǎn),則進(jìn)行鏈碼修復(fù),并修改對(duì)應(yīng)的di值. 對(duì)每一條輪廓循環(huán)查找.

為了修復(fù)凸起點(diǎn)的鏈碼,設(shè)計(jì)了算法2.

2.2.3 根據(jù)鏈碼差分析出角點(diǎn)

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

對(duì)所有輪廓FMP的每一條輪廓(FMP[index].size>20,index表示輪廓索引號(hào))循環(huán)查找角點(diǎn). 對(duì)輪廓FMP[index]的鏈碼差計(jì)算和鏈碼修復(fù)完成后,再重新對(duì)該輪廓循環(huán)查找角點(diǎn),對(duì)鏈碼差分分以下3種情況討論,設(shè)置標(biāo)記數(shù)Q12=0：

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

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

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

1)當(dāng)di=1,即鏈碼變化前后為逆時(shí)針旋轉(zhuǎn). 以如下計(jì)算方法得到的值存入數(shù)組K1和K2中：

計(jì)算ai-1的順時(shí)針?lè)较虻膬蓚€(gè)鏈碼組成數(shù)組K1,即K1={ai-1,ai-1-1,ai-1-2};

計(jì)算ai的逆時(shí)針?lè)较虻膬蓚€(gè)鏈碼組成數(shù)組K2,即K2={ai,ai+1,ai+2}.

例如 0 →1逆時(shí)針?lè)较蜃兓河?jì)算0的順時(shí)針?lè)较虻膬蓚€(gè)鏈碼分別為7和6,組成數(shù)組K1= { 0,7,6}; 計(jì)算1的逆時(shí)針?lè)较虻膬蓚€(gè)鏈碼分別為2和3,組成數(shù)組K2= { 1,2,3},如圖5(a).

圖5 方向分析示意圖

2)當(dāng)di=-1,即鏈碼變化前后為順時(shí)針旋轉(zhuǎn). 以如下計(jì)算方法得到的值存入數(shù)組K1和K2中：

計(jì)算ai-1的逆時(shí)針?lè)较虻膬蓚€(gè)鏈碼組成數(shù)組K1,即K1={ai-1+1,ai-1+1,ai-1+2};

計(jì)算ai的順時(shí)針?lè)较虻膬蓚€(gè)鏈碼組成數(shù)組K2,即K2={ai,ai-1,ai-2}.

例如 0 →7順時(shí)針?lè)较蜃兓河?jì)算0的逆時(shí)針?lè)较虻膬蓚€(gè)鏈碼分別為1和2,組成數(shù)組K1= { 0,1,2}; 計(jì)算0的順時(shí)針?lè)较虻膬蓚€(gè)鏈碼分別為7和6,組成數(shù)組K2={ 0,7,6},如圖5(b).

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

圖6 疑似角點(diǎn)輪廓前后鏈碼示意圖

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

3.3 算法復(fù)雜度分析

本文算法在角點(diǎn)檢測(cè)部分主要是分情況分析鏈碼方向,對(duì)疑似角點(diǎn)的周?chē)鷰讉€(gè)點(diǎn)的鏈碼值進(jìn)行分析比較,不涉及乘除法運(yùn)算和曲率運(yùn)算,算法角點(diǎn)檢測(cè)部分計(jì)算量較少,計(jì)算過(guò)程是分輪廓計(jì)算,得到的角點(diǎn)也是分輪廓存儲(chǔ). 本文算法的角點(diǎn)檢測(cè)部分(不包括輪廓跟蹤部分)的時(shí)間復(fù)雜度為 O (n),空間復(fù)雜度為 O (n),其中n為所有輪廓的總點(diǎn)數(shù).

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

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

圖7 本文實(shí)驗(yàn)所用圖

3.1 準(zhǔn)確性實(shí)驗(yàn)

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

為了對(duì)比的公平性,在比較過(guò)程中,五種算法在提取邊緣輪廓選取相同參數(shù),均采用Canny算法,低閾值L=0.2,高閾值H=0.35,檢測(cè)時(shí)選取算法檢測(cè)最優(yōu)結(jié)果時(shí)的參數(shù)[1]進(jìn)行實(shí)驗(yàn)比較. 本文算法參數(shù)設(shè)置：相鄰因子NF=6,相同點(diǎn)S=2. 對(duì)飛機(jī)檢測(cè)結(jié)果如圖8,具體結(jié)果如下表1.

圖8 各算法對(duì)飛機(jī)圖像的角點(diǎn)檢測(cè)

表1 準(zhǔn)確性實(shí)驗(yàn)結(jié)果

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

3.2 穩(wěn)定性實(shí)驗(yàn)

為了驗(yàn)證算法在圖像變換下的魯棒性,實(shí)驗(yàn)利用圖7的四幅基礎(chǔ)圖建立一個(gè)數(shù)據(jù)集,經(jīng)過(guò)如下變換[15]：

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

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

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

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

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

圖像變換實(shí)驗(yàn)時(shí),以平均重復(fù)率(AR)和定位誤差(LE)來(lái)評(píng)價(jià)角點(diǎn)檢測(cè)算法[15]. 假設(shè)N0是算法檢測(cè)初始圖像的角點(diǎn)個(gè)數(shù),NT是算法檢測(cè)變換后圖像的角點(diǎn)個(gè)數(shù),Nr是兩者重復(fù)的角點(diǎn)個(gè)數(shù). 則平均重復(fù)率為：

平均重復(fù)率越高,說(shuō)明算法在越穩(wěn)定. 定位誤差為：

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

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

由表2可以看出,本文算法在定位誤差方面雖然沒(méi)有CPDA、Fast-CPDA和He&Yung算法好,但要好于ARCSS,并且本文算法在5個(gè)檢測(cè)算法具有最高的平均重復(fù)率,說(shuō)明本文算法具有良好的角點(diǎn)檢測(cè)穩(wěn)健性.

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

表2 穩(wěn)定性實(shí)驗(yàn)比較結(jié)果

此外,本文提出的相鄰因子NF和相同點(diǎn)S在圖像的等比例尺度變換時(shí)可以與尺度因子等比例增減. 實(shí)驗(yàn)過(guò)程中,為了實(shí)驗(yàn)對(duì)比的公平性,本文沒(méi)有采用等比例NF和S,都以不改變NF和S進(jìn)行角點(diǎn)檢測(cè)實(shí)驗(yàn). 在實(shí)際應(yīng)用中,圖像執(zhí)行等比例尺度變換時(shí),可以采用等比例增減NF和S進(jìn)行角點(diǎn)檢測(cè),效果更佳.

3.3 算法運(yùn)行時(shí)間實(shí)驗(yàn)

我們記錄上述五種算法運(yùn)行圖7中4幅圖所耗費(fèi)時(shí)間,分別運(yùn)行10次,然后計(jì)算平均運(yùn)行時(shí)間(除去統(tǒng)一使用的Canny算法運(yùn)行時(shí)間). 運(yùn)行時(shí)間如表3

表3 五種角點(diǎn)檢測(cè)算法運(yùn)行時(shí)間(單位：s)

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

通過(guò)以上3種實(shí)驗(yàn)對(duì)比分析,He&Yung運(yùn)行時(shí)間最快,Fast-CPDA算法定位誤差最低,但本文算法的角點(diǎn)準(zhǔn)確率和平均重復(fù)率都是最高的,且本文算法不需要閾值選取.

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

本文提出一種基于Freeman鏈碼方向分析的角點(diǎn)檢測(cè)算法,通過(guò)巧妙地分析鏈碼方向,計(jì)算鏈碼發(fā)生變化時(shí)周?chē)鄠€(gè)鏈碼的值是否在一定的數(shù)組中來(lái)判定角點(diǎn),而不需要經(jīng)過(guò)傳統(tǒng)的曲線曲率計(jì)算檢測(cè)角點(diǎn),同時(shí)避免了閾值選取的問(wèn)題,實(shí)驗(yàn)結(jié)果得出本文算法在角點(diǎn)檢測(cè)時(shí)具有良好的檢測(cè)準(zhǔn)確性和穩(wěn)健性,角點(diǎn)存儲(chǔ)分輪廓具有順序性,算法很好理解,角點(diǎn)檢測(cè)部分時(shí)間復(fù)雜度小. 不過(guò)在算法前期需要鏈碼的提取,使得算法運(yùn)行時(shí)間要比He&Yung、Fast-CPDA、CPDA算法稍長(zhǎng),另外,本文算法在組合變換中檢測(cè)角點(diǎn)不夠理想,在以后工作中會(huì)加以改進(jìn).

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角點(diǎn)檢測(cè)的優(yōu)化算法.計(jì)算機(jī)系統(tǒng)應(yīng)用,2017,26(4)：169-172.

4 章為川,孔祥楠,宋文. 圖像的角點(diǎn)檢測(cè)研究綜述. 電子學(xué)報(bào),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 李云紅,姚韻,賈利娜. 基于圖像輪廓的角點(diǎn)檢測(cè)算法. 計(jì)算機(jī)與數(shù)字工程,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 曾接賢,李煒燁. 曲率尺度空間與鏈碼方向統(tǒng)計(jì)的角點(diǎn)檢測(cè). 中國(guó)圖象圖形學(xué)報(bào),2014,19(2)：234-242.

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

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

13 吳桐樹(shù),張瑞林,鄒敏. 基于Freeman鏈碼的B樣條曲線輪廓擬合. 計(jì)算機(jī)系統(tǒng)應(yīng)用,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 徐玲. 基于圖像輪廓的角點(diǎn)檢測(cè)方法研究[博士學(xué)位論文].重慶：重慶大學(xué),2009.

18 李冬晴. 圖像角點(diǎn)檢測(cè)算法與測(cè)評(píng)技術(shù)研究[碩士學(xué)位論文]. 蘇州：蘇州大學(xué),2015.

19 趙亞利,章為川,李云紅. 圖像邊緣輪廓自適應(yīng)閾值的角點(diǎn)檢測(cè)算法. 中國(guó)圖象圖形學(xué)報(bào),2016,21(11)：1502-1514.[doi：10.11834/jig.20161110]