基于SRG的快速圖像分割算法研究與實(shí)現(xiàn)

唐萬成，葉邦彥，梁立東

(華南理工大學(xué) 機(jī) 械與汽車工程學(xué)院， 廣東 廣 州 5 10640）

圖像分割是計(jì)算機(jī)視覺重要研究內(nèi)容，計(jì)算機(jī)視覺中的圖像理解包括目標(biāo)檢測、特征提取和目標(biāo)識別等,都依賴于圖像分割的質(zhì)量。在圖像處理與分析中，人們往往只對圖像中的某些區(qū)域感興趣，需要將感興趣的區(qū)域從背景中分離出來，并且將其標(biāo)記，才能進(jìn)行下一步的處理與分析。因此，圖像處理的目標(biāo)是將構(gòu)成圖像的各個像素分配到不同的區(qū)域中[1]，從而將人們感興趣的區(qū)域從復(fù)雜的背景中分離出來。圖像分割算法有很多種，廣義上可分為：基于閾值的分割算法、基于邊緣檢測的分割算法、基于區(qū)域分割算法以及基于簇類的分割算法。其中基于區(qū)域的算法最容易實(shí)現(xiàn)自動化。區(qū)域生長法（SRG）是基于區(qū)域分割算法的一種，其原理是通過給定的生長點(diǎn)（區(qū)域）逐步合并其周圍特征一致的像素點(diǎn)（或區(qū)域），形成一個大的區(qū)域。

SRG分割算法在圖像分割與連通域標(biāo)記中應(yīng)用廣泛，在圖像處理技術(shù)中已有許多研究[2-6]，其算法步驟有：1）選擇合適的生長點(diǎn)2）確定生長準(zhǔn)則3）確定生長停止條件。文獻(xiàn)[1]通過SRG算法對彩色圖像進(jìn)行智能分割，取得很好的效果。文獻(xiàn)[7]中提出一種結(jié)合SRG與分水嶺算法得出的一種圖像分割算法，該算法首先用分水嶺算法進(jìn)行初始化分割，然后再利用SRG算法進(jìn)行合并。盡管SRG便于實(shí)現(xiàn)智能圖像分割，但傳統(tǒng)的SRG算法需要給定生長、多次掃描整張圖片，而且大多算法復(fù)雜程度高，執(zhí)行效率低，不利于用在快速圖像序列分析與檢測。

為了提高分割算法效率，本文模擬自然界中的病毒感染過程，提出一種基于SRG的智能分割算法，并在VC++6平臺上將其實(shí)現(xiàn)。通過實(shí)驗(yàn)，證實(shí)該算法不僅能夠只通過一次掃描便可將目標(biāo)與背景分離，算法周期短，同時還能夠?qū)α涟挡痪鶆虻膱D像進(jìn)行目標(biāo)分割、并且能將目標(biāo)逐一標(biāo)記，方便后期區(qū)域的重建與檢測。

1 基于SRG的快速圖像分割算法

基于SRG的快速圖像分割算法是模擬了生態(tài)中的病毒感染過程。在生態(tài)中，病毒在傳播時，當(dāng)遇到能夠被感染的個體便寄宿在該個體上，此時該個體成為病毒攜帶體。該病毒攜帶體成為感染源，立即將其周圍沒有被感染過、且體抗力不強(qiáng)的個體逐一感染。被感染的個體成為新的感染源，并按照相同的方式逐步感染完整個區(qū)域的所有能被感染的個體。以此方式感染其他區(qū)域的個體。區(qū)域的標(biāo)記可用該區(qū)域中第一個被感染的個體作為記號。

這樣的過程與該算法分割目標(biāo)的過程極其相似，為了更好的了解這兩者之間的關(guān)系，作了兩者的對照表，其對應(yīng)關(guān)系如下：

種群區(qū)域→目標(biāo)區(qū)域

感染源→生長點(diǎn)

生態(tài)→圖像

個體→像素

因此，參照病毒感染過程，將這種過程用于圖像分割算法中，其步驟如下：

步驟1：確定區(qū)域生長點(diǎn)

算法確定生長點(diǎn)時是根據(jù)區(qū)域邊界兩側(cè)像素灰度差大小確定的。每隔m行，n個像素單向遍歷圖片。目標(biāo)區(qū)域與背景往往有較大的像素差，但邊界的相鄰兩個像素的像素值卻很相近，因此為了保證探測初始生長點(diǎn)的準(zhǔn)確度，采用基于跨像素搜索。如圖1所示。

圖1 生長點(diǎn)探測圖示Fig.1 Seed detecting figure

圖中：1為向右探測；3為向左探測。1,3,4的特點(diǎn)是探測基點(diǎn)在背景上，情況2是探測不出來的，但可以在另一行的掃描中的情況4探測到。探測準(zhǔn)則為：當(dāng)找到一個像素點(diǎn)，滿足表1中的某一種情況時，則確定當(dāng)前區(qū)域的第一感染源。

表1 感染源判據(jù)表Tab.1 Origin virus criterion

表中，g(i，j)為標(biāo)記矩陣，g(i，j)=0，表示該像素已被感染過，反之則未被感染。

參數(shù)λ與圖像背景亮度相關(guān)，該參數(shù)的存在是為了處理光線不均勻的圖片。初值為1，根據(jù)已確定為背景的像素點(diǎn)動態(tài)更新迭代：

其中b(i)為前(s-i)個背景像素點(diǎn)的灰度值。

步驟2：區(qū)域由感染源感染

當(dāng)找到感染源(ivirus，jvirus)后，算法開始檢測感染源的八鄰

域的像素點(diǎn)，當(dāng)檢測到某一鄰域像素，若滿足準(zhǔn)則：

則將該八領(lǐng)域的像素點(diǎn)(ivirus+k，jvirus+l)感染，即令g(ivirus+k,jvirus+l)=0。

步驟3：將第二步的被感染像素點(diǎn)作為下一輪的感染源，每個感染源均對其八鄰域中滿足條件（2）的像素點(diǎn)感染，所感染的個體又作為下一輪感染的感染源，繼續(xù)感染，直到某一輪的被感染的像素?cái)?shù)為0。

步驟4：檢測是否遍歷完整個圖像，若沒有，則繼續(xù)尋找下一個區(qū)域的第一個被感染的像素點(diǎn)步、第三步操作，直到遍歷完整個圖像，完成圖像的分割與目標(biāo)的標(biāo)記。

2 算法實(shí)現(xiàn)

為了實(shí)現(xiàn)算法，筆者在VC++6平臺上編程實(shí)現(xiàn)，首先需要定義兩種數(shù)據(jù)結(jié)構(gòu)：

struct OBJECT//表示個體

{

int i;//表示對象的縱坐標(biāo)

int j;//表示對象的橫坐標(biāo)

unsigned char vPixel;//表示對象的像素值

}；

Struct AREAINFO//表示區(qū)域

{

OBJECT m_VirusObj;//區(qū)域感染源

int m_AreaSize;//區(qū)域大小

int m_AreaNO;//記錄區(qū)域的編號}；

在算法開始前首先定義數(shù)組：

OBJECT m_VirusObj[a];//本輪感染源個體

OBJECT m_InfectedObj[a];//本輪被感染個體

AREAINFO m_AreaInfo[b];//記錄區(qū)域的信息

同時定義3個變量：

int m_VirusObjNumber=0;

int m_InfectedObjNumber=0;

int m_AreaNumber=0;

其中，a，b的取值可根據(jù)實(shí)際情況來取，確保每一輪參與感染與被感染的對象數(shù)目小于a以及圖像中的連通區(qū)域數(shù)目小于b。每一輪感染前，m_InfectedObjNumber清零，且在感染過程中，每感染成功一個個體時該變量加1。

圖2為算法具體流程圖。

圖2 程序流程圖Fig.2 Program flow chart

按照流程圖的感染過程部分代碼如下：

int CInfectingAlg::algCalculating(…)//感染算法主函數(shù)

{

//定義變量，初始化各個參數(shù)

……

for(int i=5;i

{

for(int j=5;j

{

if(pCurFrameData[i*widthstep+j]==0)//當(dāng)前個體已被感染，則繼續(xù)檢測下一個個體

{ j+=vDitch;

continue;

}

if(pCurFrameData[i*widthstep+j-vDitch]!=0)//檢測當(dāng)前點(diǎn)的左vDitch個個體是否已被感染

{ if (pOriFrameData [i*widthstep+j]-

pOriFrameData[i*widthstep+j-vDitch]>=bVirusFeather)

//根據(jù)感染源判據(jù)判斷區(qū)域感染源并感染

{ nSeedx=j;

nSeedy=i;

OnInfectedProcess(…);//感染過程

}

……

}

……

j=j+j_Jump;

}i=i+i_Jump；

}

return m_InfectedAreaNumber;

}

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

在奔騰4處理器，主頻為1.86 GHz的處理器上執(zhí)行算法，分別采用本文所述分割算法與傳統(tǒng)閾值分割法處理大小為如圖3所示640×480的光線不均勻圖片。兩種算法的分割結(jié)果比較如圖4所示。

圖3 原圖像Fig.3 Origin image

圖4 算法結(jié)果Fig.4 Algorithm processing result

圖中（a）為本文算法分割的結(jié)果，（b）為傳統(tǒng)閾值分割算法分割的結(jié)果。由實(shí)驗(yàn)結(jié)果比較可以看出，兩種目標(biāo)分割算法所用的時間均不超過1ms，但本文所述分割算法分割出的目標(biāo)輪廓清晰，噪聲少，并且保持原有目標(biāo)形狀；而傳統(tǒng)閾值分割算法由于圖片亮暗不均，無法選取一個全局最優(yōu)閾值，從而導(dǎo)致部分目標(biāo)輪廓無法被分割出來，造成信息丟失，影響后續(xù)處理和應(yīng)用。因此，對于亮暗不均勻的藥片圖片處理，本文算法較傳統(tǒng)閾值分割算法更優(yōu)，同時除了具有目標(biāo)分割功能之外，本文算法同時還可以標(biāo)記每一個目標(biāo)，如表2所示。

表2為標(biāo)記的圖像區(qū)域信息，記錄了各個目標(biāo)區(qū)域的區(qū)域大小和生長點(diǎn)坐標(biāo)。

4 結(jié)論

通過模擬生態(tài)中的病毒感染過程，提出一種基于SRG的快速圖像分割算法。從算法復(fù)雜度來看，該算法摒棄過多的數(shù)學(xué)計(jì)算，而以比較代替；從算法效率來看，該算法執(zhí)行周期短，效率高，適用于序列圖片中的實(shí)時處理；從智能程度來看，該算法能根據(jù)光照變化做出一定的反應(yīng)補(bǔ)償，能夠?qū)α涟挡痪膱D片進(jìn)行目標(biāo)分割及標(biāo)記，對實(shí)時圖像處理分析具有較大的意義。

表2 區(qū)域信息記錄表Tab.2 Area Information table

[1]Frank YS,CHENG Shou-xian.Automatic seeded region growing for color image segmentation[J].Image and Vision Computing,2005,23(10):877-886.

[2]FAN Jian-ping,ZENG Gui-hua,Body M.Seeded region growing:An extensive and comparative study[J].Pattern Recognition Letters,2005,26(8):1139-1156.

[3]Takanashi T,Shin J.Color image segmentation based on region growing algorithm[J].Jou-rnal of Convergence Information Technology,2012,7(16):152-160.

[4]WANG Jia-nan,KONG Jun,LU Ying-hua.A region-based SRG algorithm for color image segmentation[J].Proceedi-ngs of the Sixth International Conference on Machine Learning and Cybernetics,2007(3):1524-1547.

[5]魯宏偉，文燕.區(qū)域生長法在PCB元件分割中的應(yīng)用[J].小型微型計(jì)算機(jī)系統(tǒng)，2007,28(8):1489-1491.LU Hong-wei,WEN Yan.Region growing algorithm in PCB element segementation[J].Journal of Chinese Computer Systems,2007,28(8):1489-1491.

[6]程明，黃曉陽，黃紹輝，等.定向區(qū)域生長算法及其在血管分割中的應(yīng)用[J].中國圖像圖形學(xué)報(bào)，2011（1）：44-49.CHENG Ming,HUANG Xiao-yang,HUANG Shao-hui,et al.Directional region growing algorithm and its applications in vessel segm entation[J].Journal of Image and Graphics,2011(1):44-49.

[7]孔俊，王佳男，谷文祥，等.基于區(qū)域的自動種子區(qū)域生長法的彩色圖像分割算法[J].東北師大學(xué)報(bào)：自然科學(xué)版，2008,40(4):47-51.KONG Jun,WANG Jia-nan,GU Wen-xiang,et al.Automatic SRG based region for color image segmentation[J].Journal of Northeast Normal University：Natural Science Edition,2008,40(4):47-51.