一種二值圖像連通區(qū)域標(biāo)記的簡單快速算法_葛春平

1、一種二值圖像連通區(qū)域標(biāo)記的簡單快速算法_葛春平價(jià)值工程0引言二值圖像連通區(qū)域標(biāo)記是從僅由表示背景的“0”像素和表示前景的“1”像素組成的圖像中將相互鄰接的(4鄰域鄰接和8鄰域鄰接)的連通區(qū)域用唯一的標(biāo)記編號進(jìn)行標(biāo)記。這種操作是圖像處理中的一個(gè)基本操作，可以用模式識(shí)別、OCR 、圖像標(biāo)注、圖像檢索等方面。1傳統(tǒng)標(biāo)記算法傳統(tǒng)標(biāo)記的算法主要有以下幾種：第一種方法是邊緣檢測和內(nèi)部填充法。這種算法先對二值圖像進(jìn)行邊緣檢測然后對封閉的邊緣內(nèi)部進(jìn)行標(biāo)號填充，這種方法需要對圖像進(jìn)行兩次處理，時(shí)間效率不高。而且在4鄰域的情況下會(huì)把非?？拷膬蓚€(gè)連通區(qū)域標(biāo)記為相同的標(biāo)號。第二種方法是跟綜算法。對每個(gè)目標(biāo)點(diǎn)標(biāo)記一個(gè)

2、與其坐標(biāo)相關(guān)的標(biāo)號，反復(fù)對圖像進(jìn)行掃描，將每個(gè)像素的標(biāo)號更改為其基金項(xiàng)目：本文得到渭南師范學(xué)院科研項(xiàng)目、陜西省教育學(xué)會(huì)科研項(xiàng)目的資助。項(xiàng)目名稱：大規(guī)模虛擬試驗(yàn)中網(wǎng)絡(luò)互聯(lián)問題研究、運(yùn)用信息技術(shù)手段構(gòu)建網(wǎng)絡(luò)教研新模式。項(xiàng)目編號:11YKZ017、SJHYBKT2021004-03。作者簡介：葛春平（1981-），男，甘肅慶陽人，渭南師范學(xué)院物理與電氣工程學(xué)院，講師，碩士，研究方向?yàn)檐浖こ?。一種二值圖像連通區(qū)域標(biāo)記的簡單快速算法A Simple and Rapid Algorithm of Connected Component Labeling for Binary Image葛春平GE Chu

3、n-ping（渭南師范學(xué)院，渭南714000）（Weinan Normal University ，Weinan 714000，China ）摘要：針對傳統(tǒng)二值圖像連通區(qū)域標(biāo)記需要對圖像進(jìn)行兩次掃描的缺點(diǎn)，提出了一鐘新的二值圖像連通區(qū)域標(biāo)記算法。算法借助創(chuàng)建一與圖像等大的標(biāo)記矩陣，通過深度優(yōu)先搜索算法對圖像進(jìn)行一次掃描后，將標(biāo)記編號記錄在標(biāo)記矩陣中。此算法不受連通區(qū)域的形狀和面積影響，表現(xiàn)出了良好的魯棒性。最后通過OpenCV 對該算法進(jìn)行了實(shí)現(xiàn)并與傳統(tǒng)標(biāo)記算法進(jìn)行了時(shí)間性能比較。Abstract:A new connected component labeling algorithm was

4、 proposed for improving of traditional algorithm for it need twice scanning of image.Algorithm need a matrix with the same size of image,the label recorded in the matrix by a depth-first search on the image.This algorithm is not affected by the shape and area of the connected component.Finally,imple

5、ment the Algorithm by OpenCV and compare it with the traditional algorithm in the aspect of time efficiency.關(guān)鍵詞：二值圖像連通區(qū)域標(biāo)記；標(biāo)記算法；矩陣Key words:connected component labeling for binary image ；labeling algorithm ；matrix 中圖分類號：TP31文獻(xiàn)標(biāo)識(shí)碼：A 文章編號：1006-4311（2021）28-0232-02y=fft(x);%對原始波形數(shù)據(jù)進(jìn)行快速FOURIER 變換subplot

6、(2,1,2)；%頻域坐標(biāo)方框圖semilogy(0:length(x)-1/(length(x)*dt),abs(y)；%畫出頻域中FFT 波形圖xlabel(Frequency/HZ);%頻域圖的X 軸坐標(biāo)標(biāo)識(shí)xlim(01/2/dt)；%頻域軸只畫出采樣頻率具有特定功能的M 函數(shù)文件創(chuàng)建后，根據(jù)上一節(jié)介紹的方法生成COM 組件。組件名和類名，都取名為fft,如圖2所示。3.2創(chuàng)建VB 工程并調(diào)用COM 組件新建“標(biāo)準(zhǔn)EXE ”工程，進(jìn)入VB 編程環(huán)境，在“工程”菜單中單擊“引用”選項(xiàng)，在列表中選中“fft 1.0Type Library ”，單擊“確定”按鈕。在VB 工程引用后需按照以下

7、步驟來調(diào)用Matlab 文件：Dim ft as fft.fft 聲明一個(gè)COM 組件Set ft=New fft.fft Call ft.ff_t 調(diào)用一個(gè)COM 組件軟件運(yùn)行界面如圖3所示，從圖3中可分析出地震信號的優(yōu)勢頻率分布和特性；需要注意的是在使用軟件進(jìn)行地震信號分析時(shí)要先將地震事件格式轉(zhuǎn)換成.txt 格式。4結(jié)語主要介紹了通過COM 組件技術(shù)實(shí)現(xiàn)Matlab 與VB 的混合編程，并通過數(shù)字地震波譜分析的實(shí)例說明了這種方法的可行性。對于數(shù)字地震波分析含有復(fù)雜算法的界面設(shè)計(jì)有舉一反三的作用，VB 的可視化界面與Matlab 強(qiáng)大函數(shù)庫有效結(jié)合，可以很容易的編寫出數(shù)字地震波形分析應(yīng)用軟件

8、，對地震分析人員在地震研究方面具有實(shí)用價(jià)值。參考文獻(xiàn)：1宋建鎖.濾波在地震分析中的應(yīng)用J.防災(zāi)技術(shù)高等專科學(xué)校學(xué)報(bào),2021,8(1):75-79.2李敬.數(shù)字地震記錄干撓波的排除J.防災(zāi)技術(shù)高等?？茖W(xué)校學(xué)報(bào),2021,3(1):32-35.3潘曉霞.Matlab 與VB 的接口編程及在測漏儀中的應(yīng)用J.機(jī)械設(shè)計(jì)與制造,2021,(2):67-69.4徐金明.MATLAB 實(shí)用教程M.北京:清化大學(xué)出版社，2021:462-470.232DOI:10.14018/ValueEngineering表2算法效率分析圖序連通區(qū)域個(gè)數(shù)時(shí)間(單位：毫秒)邊緣檢測填充法跟蹤算法順序標(biāo)記法遞歸法本文算法12

9、3442484100.582.393.790.583.470.391.272.350.570.270.390.860.565.290.395.844.727.739.243.7表1標(biāo)記矩陣0000000000100000000111100300111103330000000300222021000222021000022021055000004055000000055000 0000 領(lǐng)域內(nèi)的最我號。第三種是順序標(biāo)記法。對圖像進(jìn)行兩次掃描，對未作標(biāo)記的像素的標(biāo)記從其領(lǐng)域獲得。這種算法可能會(huì)在第一次掃描完時(shí)，同一領(lǐng)域中出現(xiàn)不同的標(biāo)記編號，需要構(gòu)造標(biāo)記沖突表進(jìn)行解決。第四種是遞歸法。逐個(gè)遍歷像素點(diǎn)

10、，碰到未被標(biāo)記的前景像素點(diǎn)時(shí)對其進(jìn)行標(biāo)記，并遞歸處理其未被標(biāo)記的鄰接像素點(diǎn)。只到遞歸調(diào)用結(jié)束時(shí)即表示一個(gè)連通區(qū)域被標(biāo)記結(jié)束。該方法實(shí)現(xiàn)簡單，但是當(dāng)圖像上存在大面積的連通區(qū)域時(shí)算法將會(huì)是一個(gè)深度遞歸，即容易導(dǎo)致內(nèi)存棧溢出。2本文算法2.1算法描述本文提出一種基于區(qū)域生長的廣度優(yōu)先標(biāo)記算法。算法中我們需要定義一個(gè)和二值圖像具有想同行列數(shù)的標(biāo)記矩陣來存放我們的標(biāo)記結(jié)果。首先將這個(gè)標(biāo)記矩陣初始化為0。等算法結(jié)束時(shí)，標(biāo)記矩陣中將存放由0到連通區(qū)域個(gè)數(shù)的整數(shù)。其中0表示對應(yīng)行列處為圖像的背景像素，其它值表示被標(biāo)記的圖像中的連通區(qū)域的編號。如表1所示的標(biāo)記矩陣表示的標(biāo)記矩陣表示對應(yīng)的圖像中有五個(gè)連通區(qū)域。根

11、據(jù)該標(biāo)記矩陣可以很容易的求出原圖像中各個(gè)連通區(qū)域的面積，邊界，重心等一些重要的圖像特征參數(shù)。算法首先對圖像進(jìn)行逐像素掃描，掃描到某個(gè)像素時(shí)，首先判斷是不是背景像素。如果是背景像素，只接跳過該像素處理下一個(gè)像素。如果是前景像素，先判斷該像素是否已被標(biāo)記過，判斷標(biāo)準(zhǔn)就是對應(yīng)位置的標(biāo)記矩陣值。如果值為0則表示該位置未被標(biāo)記。對于未被標(biāo)記的像素則對其進(jìn)行標(biāo)記，標(biāo)記完了需要判斷該像素的鄰接像素是否未被標(biāo)記。如果未被標(biāo)記，對其標(biāo)記上相同的標(biāo)記編號。然后判斷鄰接像素的鄰接像素，只到?jīng)]有鄰接像素為止。從以上算法描述來看是一個(gè)遞歸的思想，通過編寫一個(gè)處理像素的遞歸函數(shù)來實(shí)現(xiàn)以上算法是比較容易的。但是如果圖像中的

12、連通區(qū)域面積比較大時(shí)，算法處理將是一個(gè)深度遞歸。極其容易造成棧溢出。所以本文設(shè)計(jì)的算法借助一個(gè)隊(duì)列將這種遞歸的思想轉(zhuǎn)換為疊代的思想。每次掃描到一個(gè)未標(biāo)記像素時(shí)將該像素入隊(duì)列，然后對隊(duì)頭像素進(jìn)行標(biāo)記，再將其未標(biāo)記的鄰接像素也入隊(duì)列并標(biāo)記，最后刪除隊(duì)頭像素，如此疊代循環(huán)只到隊(duì)列為空時(shí)即表示一個(gè)連通區(qū)域已被標(biāo)記完成。最后將標(biāo)記標(biāo)號加1再順序掃描下一像素進(jìn)行相同的操作只到掃描完所有的像素。2.2算法流程對上面提到的算法描述，可以按照下面的步驟加以實(shí)現(xiàn)：步驟1：設(shè)圖像矩陣為I ，創(chuàng)建一個(gè)與圖像I 相同行列數(shù)的標(biāo)記矩陣M ，將標(biāo)記矩陣初始化為0。創(chuàng)建一標(biāo)記變量count ，表示將要進(jìn)行標(biāo)記的區(qū)域編號，將其

13、初始化為1。步驟2：對圖像按照從上到下，從左到右進(jìn)行逐像素掃描。掃描到第m 行n 列像素點(diǎn)時(shí)，對該像素的點(diǎn)值Im,n,(0或1)和標(biāo)記矩陣中的第m 行n 列的值Mm,n(1到連通區(qū)域個(gè)數(shù))進(jìn)行步驟3中的幾種情況處理。步驟3：對步驟2中取出的值分以下兩種情況處理。如果Im,n已被標(biāo)記過(判斷依據(jù)為Mm,n0)，或者Im,n為背景像素(判斷依據(jù)為Im,n=0)，跳過后面步驟，返回步驟2取出下一像素處理。否則創(chuàng)建一存儲(chǔ)行列坐標(biāo)(m,n)的隊(duì)列L ，并將(m,n)插入隊(duì)列L 隊(duì)尾。步驟4：循環(huán)取出L 隊(duì)頭元素(x,y)，如果Ix,y未被標(biāo)記(即Mx,y0)，將Ix,y標(biāo)記為count(置Mx,y=co

14、unt)，判斷x,y的所有鄰域點(diǎn)x1,y1，如果Ix1,y1未被標(biāo)記(即M x1,y10)，將Ix1,y1插入隊(duì)列L 隊(duì)尾，并將Ix1,y1標(biāo)記為count(置Mx1,y1=count)。最后將隊(duì)列L 隊(duì)頭素出列。循環(huán)該步驟真到隊(duì)列為空后將標(biāo)記變量count 加1。步驟5：返回步驟2處理下一像素點(diǎn)。2.3實(shí)驗(yàn)及結(jié)果分析將以上算法在OpenCV 中實(shí)現(xiàn)后對以下四種不同復(fù)雜程度的256256像素的二值圖像進(jìn)行處理，其處理結(jié)果如圖1到圖4所示。本文算法與傳通算法的運(yùn)行效率比較如表2所示。通過以上分析可以看出本文中的算法對任意復(fù)雜的連通區(qū)域都表現(xiàn)出一定的魯棒性。同時(shí)也具有可觀的時(shí)間效率。3總結(jié)本文提出

15、了一種二值圖像連通區(qū)域標(biāo)記的新算法，能夠通過對圖像進(jìn)行一次掃描將將其連通特征標(biāo)記到標(biāo)記矩陣中。通過等不同數(shù)目和復(fù)雜度的二值圖像進(jìn)行測試以及與傳統(tǒng)算法進(jìn)行比較，可以發(fā)現(xiàn)算法復(fù)雜度低，不受連通區(qū)域的特征和數(shù)量影響，相比比傳統(tǒng)二值圖像連通區(qū)域標(biāo)記算法具有容易實(shí)現(xiàn)，時(shí)間效率和空間效率較高。參考文獻(xiàn)：1Rosenfeld A,Pfaltz J L.Sequential operations in digitalpicture processing.Journal of th ACM,1966，13(4):480-385.2高紅波，王衛(wèi)星.一種二值圖像連通區(qū)域標(biāo)記的新算法.計(jì)算機(jī)應(yīng)用.2021，27(11):2776-2777.3SAMETH.Connected compone