基于圓環(huán)模板和標(biāo)志矩陣的角點(diǎn)檢測算法

王建衛(wèi)

(東北林業(yè)大學(xué) 機(jī)電工程學(xué)院，黑龍江 哈爾濱 150040)

0 引 言

隨著計算機(jī)技術(shù)的發(fā)展，使計算機(jī)具有視覺功能進(jìn)一步得到廣泛關(guān)注和研究，視覺系統(tǒng)已經(jīng)成為計算機(jī)系統(tǒng)不可或缺的一個重要組成部分，建立通用的計算機(jī)視覺系統(tǒng)完成視覺任務(wù)一直是計算機(jī)視覺領(lǐng)域、圖像處理領(lǐng)域的重要研究內(nèi)容。一般地，視覺任務(wù)是以任務(wù)初期獲取的原始圖像的理解為目的，圍繞著圖像理解的一系列研究也納入到了計算機(jī)研究工作者的視野中。通常，圖像理解的關(guān)鍵是通過分割圖像獲得目標(biāo)和背景，邊緣檢測往往是實(shí)現(xiàn)目標(biāo)和背景分割的首選方法。在邊緣檢測中，存在著邊緣點(diǎn)和邊緣段同時檢出的問題，角點(diǎn)是邊緣段的方向?qū)傩愿淖儠r所標(biāo)注的特殊的邊緣點(diǎn)。角點(diǎn)作為灰度圖像穩(wěn)定的局部特征，包含了圖像中的重要結(jié)構(gòu)信息[1]。自從1977年Moravec算法提出以來，研究者們開始研究圖像的角點(diǎn)檢測理論和方法[2-4]。由于角點(diǎn)檢測結(jié)果在計算機(jī)視覺理論的應(yīng)用領(lǐng)域都具有重要的作用[5-7]，因此，角點(diǎn)檢測理論始終是計算機(jī)視覺理論、圖像處理領(lǐng)域的研究熱點(diǎn)之一。

由于角點(diǎn)檢測理論的復(fù)雜性，角點(diǎn)很難給出明確的定義，目前將角點(diǎn)描述為二維圖像亮度變化劇烈的點(diǎn)，或邊緣曲線的曲率局部極大值點(diǎn)或多條邊緣曲線的交匯點(diǎn)[8-10]。角點(diǎn)檢測算法可分為三類：基于灰度強(qiáng)度的方法、基于邊緣輪廓的方法和基于角點(diǎn)模型的方法[11-14]。其中第一種方法可直接在灰度圖像上進(jìn)行，角點(diǎn)為在像素點(diǎn)的周圍鄰域內(nèi)有足夠多的像素點(diǎn)與該點(diǎn)處于不同的區(qū)域。角點(diǎn)是圖像各向異性的局部特征[15]，圖像像素的局部灰度變化和結(jié)構(gòu)信息的有效提取和描述是基于灰度強(qiáng)度算法的關(guān)鍵，常用的檢測方法有Moravec[16]、Harris[17-18]、SUSAN[19]和FAST[20-21]等。Moravec算法在檢測出角點(diǎn)的同時，邊緣點(diǎn)也會檢測出。Harris在平滑后的灰度圖像逐一檢測像素點(diǎn)是否為角點(diǎn)，檢測過程較復(fù)雜[17]。SUSAN算子檢測出邊緣點(diǎn)也是不可避免的[19]。FAST算子是在SUSAN算法的基礎(chǔ)上利用機(jī)器學(xué)習(xí)方法提出的，對半徑為3的圓周上的像素點(diǎn)進(jìn)行判決，根據(jù)設(shè)置的閾值提取角點(diǎn)，關(guān)鍵在于閾值的選取[20-21]。為解決角點(diǎn)檢測中邊緣點(diǎn)和邊緣段同時檢出問題，文中提出一種基于圓環(huán)模板和角點(diǎn)標(biāo)志矩陣表示的角點(diǎn)檢測算法。

1 FAST角點(diǎn)檢測算法的原理

FAST角點(diǎn)檢測算法的原理是檢測灰度圖像的Bresenham圓模板區(qū)域中，有足夠多的像素點(diǎn)的灰度值大于該點(diǎn)的灰度值或者小于該點(diǎn)的灰度值，關(guān)鍵在于設(shè)定的閾值和圓形檢測模板的設(shè)計[20-21]。

FAST角點(diǎn)檢測算法步驟如下：

步驟1：輸入灰度圖像I，設(shè)定閾值t；

步驟2：將圖像的左上角的第一個像素點(diǎn)設(shè)置為候選角點(diǎn)p，該像素點(diǎn)的亮度值為I(p)；

步驟3：以p為圓心檢測如圖1所示的Bresenham圓周上的16個像素點(diǎn)x。若有n(n=7,8,9,12)個像素點(diǎn)的像素值小于I(p)+t或者有連續(xù)的n個像素I(p)-t，那么該點(diǎn)為角點(diǎn)；

圖1 Bresenham圓周上的16個像素點(diǎn)

步驟4：檢測圖像中p后續(xù)的所有像素點(diǎn)。

該算法先檢測p點(diǎn)周圍的1，5，9，12四個點(diǎn)中是否有三個點(diǎn)超過I(p)+t，如果有，則直接跳過該像素點(diǎn)；如果沒有，則繼續(xù)使用前面的算法，全部判斷16個點(diǎn)中是否有12個滿足條件。

由于圓周上至少有12個連續(xù)點(diǎn)的灰度值與中心點(diǎn)像素有差值變化，12個連續(xù)點(diǎn)必然包括圓周上的1、5、9、13這4個位置的像素中的3個，所以先檢測位置1和位置9，若它們與中心點(diǎn)像素的灰度差值在規(guī)定的閾值范圍內(nèi)，再檢測位置5和位置13。若上述4個像素點(diǎn)中至少有3個大于或小于閾值，則保留像素點(diǎn)p，否則選取其他的中心像素點(diǎn)進(jìn)行檢測[21]。圖像上的像素點(diǎn)經(jīng)過初步檢測后，符合條件的將成為候選角點(diǎn)。分析FAST算法中16個像素點(diǎn)與檢測點(diǎn)所處的位置，可知其實(shí)質(zhì)為半徑為3的圓形模板圓周上的像素點(diǎn)，可以考慮將圓形模板擴(kuò)展為通用模板，如圓形的半徑為1，2，4等。當(dāng)半徑為1時，檢測點(diǎn)的圓形模板退化為該像素的8鄰域。

文中應(yīng)用半徑為4的外圓和半徑為2的內(nèi)圓的圓環(huán)模板作為候選角點(diǎn)確立的模板，該模板的28個像素點(diǎn)如圖2所示。

圖2 28個像素點(diǎn)組成的圓環(huán)模板

2 基于圓環(huán)模板和角點(diǎn)標(biāo)志矩陣表示的角點(diǎn)檢測算法的設(shè)計

2.1 算法原理

文中算法的原理是先設(shè)置較小的閾值，通過簡單的篩選得到角點(diǎn)的與灰度圖像同型的標(biāo)志矩陣，根據(jù)角點(diǎn)在矩陣中所處的行列位置逐步刪除孤立的角點(diǎn)、邊緣段上的角點(diǎn)。算法的關(guān)鍵在于孤立的角點(diǎn)、邊緣段上的角點(diǎn)類型的判斷。

算法步驟為：應(yīng)用圓環(huán)模板提取候選角點(diǎn)；記錄角點(diǎn)在原圖像中的位置，建立與原圖像同型的角點(diǎn)標(biāo)志矩陣；將矩陣按照四叉樹結(jié)構(gòu)分解，并刪除孤立的角點(diǎn)；刪除邊緣段上的角點(diǎn)。

2.2 算法步驟

根據(jù)上述算法原理，corner_detection算法過程如下：

cor=corner_detection(I)

輸入：灰度圖像I；

輸出：角點(diǎn)集合cor。

步驟1：讀入灰度圖像I。

步驟2：設(shè)置閾值t，選擇模板類型(下面以圓環(huán)型模板為例設(shè)計算法)。

步驟3：以模板結(jié)構(gòu)將圖像的邊界進(jìn)行擴(kuò)充，以免將邊界上的角點(diǎn)漏選。文中將邊界上像素值設(shè)置為0，使對角點(diǎn)的選取結(jié)果無影響。

步驟4：根據(jù)模板類型和閾值提取較多的灰度圖像I的亮度變化點(diǎn)作為角點(diǎn)，建立角點(diǎn)集合cor。

應(yīng)用圖2的圓環(huán)模板檢測I的像素點(diǎn)，外圓環(huán)的像素點(diǎn)數(shù)為n1=20，內(nèi)圓環(huán)的像素點(diǎn)數(shù)為n2=8，I的候選角點(diǎn)集合cor元素p的響應(yīng)函數(shù)為：

當(dāng)f1(x)∈{9,10,11,12,13,14,15}且f2(x)∈{4,5,6}時，p∈cor。

步驟5：記錄角點(diǎn)在原圖像中的位置，并將原圖像的對應(yīng)像素值設(shè)置為1，其他像素設(shè)置為0，建立角點(diǎn)標(biāo)志矩陣M。

將角點(diǎn)標(biāo)志矩陣按照四叉樹結(jié)構(gòu)進(jìn)行分解，即分成N×N(N=2n)的子矩陣Mi，一般地N=32,64,128,256。考慮到圖像子塊的相關(guān)性，文中以N=128為例進(jìn)行后續(xù)步驟。

在傳統(tǒng)的小學(xué)語文教學(xué)中，大多教師局限于“書本”二字，使學(xué)生的視野被限制于語文教材當(dāng)中，學(xué)生只能通過課堂教學(xué)獲取一定的信息和資源。再加上語文教材更新的周期長，許多深受學(xué)生喜愛的、緊跟時代發(fā)展的童話被排斥在語文教材之外，導(dǎo)致教材中的童話對學(xué)生逐漸喪失了吸引力。因此，為充分發(fā)揮童話的審美功能，教師應(yīng)當(dāng)適當(dāng)拓展教學(xué)內(nèi)容，通過課下進(jìn)行互聯(lián)網(wǎng)閱讀、構(gòu)建圖書角、組織閱讀課的形式，適時拓展一些課外童話讀物，增加學(xué)生的閱讀容量，進(jìn)而開闊學(xué)生的視野，充分發(fā)揮童話的審美功能，讓學(xué)生在學(xué)習(xí)過程中逐漸提高童話鑒賞能力。

下面逐一分析各角點(diǎn)標(biāo)志子矩陣Mi(128×128)。分析角點(diǎn)標(biāo)志矩陣，將孤立的1設(shè)置為0，即刪除該角點(diǎn)。

步驟7：分析角點(diǎn)標(biāo)志矩陣，通過距離計算分析將孤立的1設(shè)置為0，即刪除該角點(diǎn)。

設(shè)Mi(h,w)為Mi的h行w列的元素1，若該元素與該子塊中其他元素1的D4距離(行坐標(biāo)之差的絕對值和列坐標(biāo)之差的絕對值之和)的最小值大于3，則該角點(diǎn)為孤立角點(diǎn)，刪除該角點(diǎn)。

步驟8：刪除水平和垂直邊緣段上的連續(xù)角點(diǎn)。

對各個子矩陣Mi按照行的方式進(jìn)行行程編碼，保留連續(xù)1序列的第一個1，后續(xù)的置為0，結(jié)果矩陣為MRi。刪除策略為同一行的各矩陣元素為128個由0或1組成的隨機(jī)序列，保留連續(xù)的1序列中的第一個1，其他的刪除。

例：設(shè)數(shù)據(jù)data為X=[0 1 0 0 0 1 1 1 1 0 1 0]，編碼rle為兩個長度相同的行向量：

data=[0 1 0 1 0 1 0]

rle=[1 1 3 4 1 1 1]

其中，結(jié)合data，分析3的含義是3個0,4的含義是4個1，處理后的X為：

X=[0 1 0 0 0 1 0 0 0 0 1 0]

同理，得到按列的方式處理的結(jié)果子矩陣MCi。

步驟9：依次讀取MRi和MCi的元素，若同行同列的元素為1，則置M的相應(yīng)元素為1，否則為0。

步驟10：記錄矩陣M中矩陣元素為1的行號和列號，在圖像I中將該行列的像素點(diǎn)標(biāo)記為角點(diǎn)。

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

為驗(yàn)證該算法在計算機(jī)視覺系統(tǒng)中的通用性，在Windows7系統(tǒng)MATLAB 2016環(huán)境下編程實(shí)現(xiàn)上述算法，并選取了具有不同性質(zhì)目標(biāo)的、目標(biāo)數(shù)目不同的以建筑物和樹葉目標(biāo)為主的兩類圖像做了分析和比較。

例1采用以建筑物為主的scene_categories的灰度圖像image_0001.jpg作為測試圖像[12]，原圖像為256×256的灰度圖像，分別采用Moravec算法、SUSAN算法、Harris算法、FAST算法和文中算法進(jìn)行了角點(diǎn)檢測。

為了更好地進(jìn)行比較，該例中采用的是固定閾值。角點(diǎn)檢測結(jié)果如圖3所示，角點(diǎn)檢測數(shù)據(jù)如表1所示。

表1 image_0001.jpg角點(diǎn)檢測數(shù)據(jù)

由表1的數(shù)據(jù)可知，Moravec算法得到的角點(diǎn)數(shù)目較少，且定位不夠準(zhǔn)確；SUSAN算法在角點(diǎn)集中的區(qū)域有角點(diǎn)聚集的現(xiàn)象，算法的執(zhí)行時間也較長；Harris算法得到的角點(diǎn)數(shù)目較少，有漏檢現(xiàn)象，算法的執(zhí)行時間也較長；FAST算法得到的角點(diǎn)數(shù)目較多，有聚集的現(xiàn)象，算法的執(zhí)行時間較短；文中算法檢測出的角點(diǎn)具有相應(yīng)次數(shù)較低、無重復(fù)的優(yōu)點(diǎn)，較好地達(dá)到了精確檢測角點(diǎn)的目的，其中外環(huán)的參數(shù)為15，內(nèi)環(huán)的參數(shù)為6，執(zhí)行時間與Moravec算法和Harris算法接近。

例2采用對比度較低的以樹葉目標(biāo)為主、背景較復(fù)雜的灰度圖像image_leaf.jpg作為測試圖像[12]，原圖像為256×256的灰度圖像。角點(diǎn)檢測結(jié)果如圖4所示。

圖3 圖像image_0001.jpg的角點(diǎn)檢測結(jié)果

圖4 圖像image_leaf.jpg的角點(diǎn)檢測結(jié)果

由圖4可知，Moravec算法的角點(diǎn)定位不夠準(zhǔn)確；SUSAN算法在角點(diǎn)集中的區(qū)域有角點(diǎn)聚集的現(xiàn)象；Harris算法有漏檢的現(xiàn)象；FAST算法與Harris算法類似，角點(diǎn)數(shù)目較少，有漏檢的現(xiàn)象；文中算法適用于背景部分的角點(diǎn)檢測，其中外環(huán)的參數(shù)為10，內(nèi)環(huán)的參數(shù)為5，候選角點(diǎn)數(shù)為1 820，經(jīng)過篩選后得到的角點(diǎn)數(shù)為920，執(zhí)行時間與Moravec算法接近。

上述實(shí)驗(yàn)結(jié)果表明，與Moravec、SUSAN、Harris與FAST等算法相比較，文中算法通過二次篩選保證了提取的角點(diǎn)數(shù)目，在一定程度上解決了角點(diǎn)數(shù)目過少或過多導(dǎo)致角點(diǎn)聚集的問題。

4 結(jié)束語

文中以角點(diǎn)檢測算法的改進(jìn)為主要研究內(nèi)容，為計算機(jī)視覺理論的圖像邊緣檢測中的角點(diǎn)檢測問題提供了一種較合理的解決方法，對計算機(jī)視覺系統(tǒng)的實(shí)現(xiàn)具有一定的實(shí)踐意義。

實(shí)驗(yàn)證明，該算法具有執(zhí)行速度快、角點(diǎn)檢測準(zhǔn)確的優(yōu)點(diǎn)，可以檢測出較復(fù)雜的三類圖像的各種角點(diǎn)，而且適用面較廣、通用性較強(qiáng)，也在圖像分割研究領(lǐng)域?yàn)榻⑼ㄓ玫挠嬎銠C(jī)視覺系統(tǒng)完成視覺任務(wù)提供了新的思路。

該算法的不足之處在于參數(shù)較多，因此還需進(jìn)一步研究像素值與參數(shù)值之間的內(nèi)在關(guān)系，以實(shí)現(xiàn)更準(zhǔn)確的提取。