基于SRG的快速圖像分割算法研究與實現

唐萬成，葉邦彥，梁立東

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

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

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

為了提高分割算法效率，本文模擬自然界中的病毒感染過程，提出一種基于SRG的智能分割算法，并在VC++6平臺上將其實現。通過實驗，證實該算法不僅能夠只通過一次掃描便可將目標與背景分離，算法周期短，同時還能夠對亮暗不均勻的圖像進行目標分割、并且能將目標逐一標記，方便后期區域的重建與檢測。

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

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

這樣的過程與該算法分割目標的過程極其相似，為了更好的了解這兩者之間的關系，作了兩者的對照表，其對應關系如下：

種群區域→目標區域

感染源→生長點

生態→圖像

個體→像素

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

步驟1：確定區域生長點

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

圖1 生長點探測圖示Fig.1 Seed detecting figure

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

表1 感染源判據表Tab.1 Origin virus criterion

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

參數λ與圖像背景亮度相關，該參數的存在是為了處理光線不均勻的圖片。初值為1，根據已確定為背景的像素點動態更新迭代：

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

步驟2：區域由感染源感染

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

域的像素點，當檢測到某一鄰域像素，若滿足準則：

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

步驟3：將第二步的被感染像素點作為下一輪的感染源，每個感染源均對其八鄰域中滿足條件（2）的像素點感染，所感染的個體又作為下一輪感染的感染源，繼續感染，直到某一輪的被感染的像素數為0。

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

2 算法實現

為了實現算法，筆者在VC++6平臺上編程實現，首先需要定義兩種數據結構：

struct OBJECT//表示個體

{

int i;//表示對象的縱坐標

int j;//表示對象的橫坐標

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

}；

Struct AREAINFO//表示區域

{

OBJECT m_VirusObj;//區域感染源

int m_AreaSize;//區域大小

int m_AreaNO;//記錄區域的編號}；

在算法開始前首先定義數組：

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

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

AREAINFO m_AreaInfo[b];//記錄區域的信息

同時定義3個變量：

int m_VirusObjNumber=0;

int m_InfectedObjNumber=0;

int m_AreaNumber=0;

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

圖2為算法具體流程圖。

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

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

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

{

//定義變量，初始化各個參數

……

for(int i=5;i

{

for(int j=5;j

{

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

{ j+=vDitch;

continue;

}

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

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

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

//根據感染源判據判斷區域感染源并感染

{ nSeedx=j;

nSeedy=i;

OnInfectedProcess(…);//感染過程

}

……

}

……

j=j+j_Jump;

}i=i+i_Jump；

}

return m_InfectedAreaNumber;

}

3 實驗結果及分析

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

圖3 原圖像Fig.3 Origin image

圖4 算法結果Fig.4 Algorithm processing result

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

表2為標記的圖像區域信息，記錄了各個目標區域的區域大小和生長點坐標。

4 結論

通過模擬生態中的病毒感染過程，提出一種基于SRG的快速圖像分割算法。從算法復雜度來看，該算法摒棄過多的數學計算，而以比較代替；從算法效率來看，該算法執行周期短，效率高，適用于序列圖片中的實時處理；從智能程度來看，該算法能根據光照變化做出一定的反應補償，能夠對亮暗不均的圖片進行目標分割及標記，對實時圖像處理分析具有較大的意義。

表2 區域信息記錄表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]魯宏偉，文燕.區域生長法在PCB元件分割中的應用[J].小型微型計算機系統，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]程明，黃曉陽，黃紹輝，等.定向區域生長算法及其在血管分割中的應用[J].中國圖像圖形學報，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]孔俊，王佳男，谷文祥，等.基于區域的自動種子區域生長法的彩色圖像分割算法[J].東北師大學報：自然科學版，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.