圖像分割是模式識別和計算機視覺領(lǐng)域的重要基礎(chǔ)環(huán)節(jié)，也是當前的研究熱點之一。典型的圖像分割方法有閾值法[1]、邊緣檢測方法、多分辨率方法[2]、分裂合并方法等。
    分裂合并的分割方法[3]充分利用圖像的整體和局部特征進行分割，算法思路清晰，在圖像處理領(lǐng)域備受青睞。該算法主要包括分裂和合并兩個階段。傳統(tǒng)算法中，在分裂階段，將不同質(zhì)的區(qū)域遞歸分裂為四個一樣大小的子區(qū)域，直到每個區(qū)域都符合一致性。在合并階段，根據(jù)一致性規(guī)則將相似的區(qū)域合并起來。但這種算法思路直接，容易造成方塊效應(yīng)和過分割。近年來許多文獻嘗試對該算法進行改進，主要體現(xiàn)在分裂階段。參考文獻[4]用Delaunay三角剖分將圖像分割成一些不規(guī)則的三角形；參考文獻[5]除了在水平和豎直方向上將圖像進行分割外，還可以在45°和275°方向上將圖像一分為二；參考文獻[6]為了解決分割位置固定的缺點，選擇了“最優(yōu)”(“最優(yōu)”的定義是可以根據(jù)需要選取)位置實現(xiàn)水平或者豎直方向的一分為二分割。以上的分裂合并算法都沒有考慮到圖像的實際邊界形狀，而是人為地將圖像分為一些固定的形狀，通過對形狀的不斷細分來逼近圖像的邊界。特別在圖像的邊緣位置，如果分裂不夠細的話，容易產(chǎn)生方塊效應(yīng)，進而破壞圖像的邊界形狀。如果分裂較細，則會因為分塊過多而容易產(chǎn)生過分割現(xiàn)象。
    邊緣檢測的方法是基于圖像在區(qū)域邊緣上的像素灰度變化比較劇烈，通過檢測不同區(qū)域的邊緣來解決圖像分割問題。邊緣檢測的分割方法可以獲得邊界線段，但由于邊緣不連續(xù)，需要擬合圖像的邊緣以獲得輪廓的連續(xù)，而且在邊界不明顯的地方很難確定區(qū)域，同時容易造成過分割[7]。
    為此，本文結(jié)合分裂合并算法與邊緣檢測技術(shù)，提出了一種新的分裂合并算法。該算法在分裂過程中直接利用圖像的邊緣信息，不斷將圖像分裂為一些不規(guī)則形狀的一致性區(qū)域，然后根據(jù)一定規(guī)則將相似的區(qū)域合并起來。
1 分裂合并分割
    定義1  塊：用四分法對圖像進行逐層分裂，得到的一系列長方形區(qū)域。
    定義2  區(qū)域：一個圖像分塊內(nèi)，邊緣與塊邊界分隔而成的一些列的不規(guī)則區(qū)域。
    定義3  一致性：設(shè)max(R)為每個區(qū)域內(nèi)的像素與該區(qū)域均值的最大差值，在不考慮噪聲的情況下設(shè)置閾值V，如果某區(qū)域的max(R)<V，則認為該區(qū)域是一致性區(qū)域(或者區(qū)域同質(zhì));否則，區(qū)域不同質(zhì)。
       本文算法描述如下：(1)對圖像進行邊緣檢測,并且對邊緣進行增強處理；(2) 對圖像進行區(qū)域分裂，并消除邊緣像素；(3) 對邊緣像素進行歸并；(4) 對圖像進行區(qū)域合并。
1.1 邊緣檢測
　    邊緣檢測主要檢測圖像中像素值變化明顯的點。由于在兩個不同區(qū)域的交界處，像素灰度變化明顯，因此，檢測出來的邊緣可以直接將兩個不同的區(qū)域隔離開來。理想情況下，一張圖像由一些連續(xù)的邊緣分割成若干個區(qū)域，但實際上獲得的邊緣卻是一些不連續(xù)的曲線，需要對邊緣作進一步處理。目前的邊緣檢測算子主要有Roberts算子、Prewitt算子、Sobel算子和Canny算子等[8]。本文采用Canny梯度算子對圖像進行邊緣檢測。Canny算子參數(shù)中閾值threthold1和threthold2主要用來控制生成邊緣。
    圖像分割中，為了獲取足夠多的邊緣像素，需要動態(tài)地調(diào)整閾值。閾值較高時，圖像的邊緣較少，可直接利用的邊緣也少；閾值較低時，圖像的邊緣較豐富，有利于分裂操作，但卻容易造成過分割，同時會在合并步驟中增加不必要的工作量。因此對閾值的選擇要達到一個平衡點。本文設(shè)threthold1=2threthold2，通過不斷地調(diào)整閾值，使圖像的邊緣密度控制在一定的范圍內(nèi)。經(jīng)多次實驗，邊緣密度在30%左右時分割效果最理想，其分割圖像如圖1所示。

    邊緣檢測后，對邊緣圖像進行閉操作，連接一些小的邊緣開口，可以有效地減少圖像分割的次數(shù)。
1.2圖像分裂
    (1)初始層的確定
    在分裂合并方法中，確定圖像塊的初始劃分，就是從四分樹中選擇某一層作為初始層，該層圖像的劃分即為圖像塊的初始劃分。若初始層選擇較上層時，由于圖像的分塊內(nèi)部邊緣長度較長，出現(xiàn)斷裂的概率較高，塊內(nèi)各區(qū)域相連通的概率較大，需要對塊繼續(xù)四等分。若初始層選擇較下層時，圖像容易被過分割，造成合并運算量劇增，增加不必要的開銷。參考文獻[9]采用分塊的邊緣密度作為初始層的劃分標準：當每個圖像塊的邊緣密度均小于給定的閾值時，該層可以作為最佳初始層。本文對此作了改進，把邊緣密度為0或邊緣密度大于給定閾值的層，作為初始劃分層。邊緣密度為0時，說明塊內(nèi)的邊緣同質(zhì)的概率較大。邊緣密度大于閾值時，說明分塊內(nèi)部邊緣豐富，極有可能將分塊分割成幾個同質(zhì)的區(qū)域。
    如圖2所示，每一分塊內(nèi)，圖像的邊緣將分塊分割成若干個區(qū)域。判斷分塊的每一個區(qū)域是否滿足一致性，若不滿足，則將該分塊繼續(xù)進行2&times;2等分。

    (2)分塊內(nèi)區(qū)域的搜索
    圖像的邊緣將圖像分割成幾個不規(guī)則的區(qū)域。搜索分塊內(nèi)每個像素所屬的四連通區(qū)域，將這些像素并入所屬的區(qū)域中。
   圖3(a)所示的圖像中，左上角的邊緣位置有一個斷裂口，使得兩個不一致的區(qū)域相互連通，因此該塊不同質(zhì)。為了獲得同質(zhì)的區(qū)域，需繼續(xù)對該塊進行2&times;2等分。分裂后得到的4個子塊中,有3塊可以獲得同質(zhì)的區(qū)域，只有左上角部分需要繼續(xù)分裂。對左上角繼續(xù)分裂，子塊中只有四分之一部分需要繼續(xù)分裂，這樣極大地減少了分裂的次數(shù)。
　而傳統(tǒng)的四分法中，由于只在水平和垂直方向上分裂，對于邊緣是斜線的情況，只能不斷地將塊分裂成一些極小的塊，以獲取同質(zhì)的區(qū)域。
　圖3(b)所示的圖像中，右上角和下面的兩個區(qū)域已經(jīng)符合一致性的標準，因此只需要對左上角分塊繼續(xù)分裂，比傳統(tǒng)方法的分裂次數(shù)減少了3/4。同時，在左上角的第二次分裂中，又減少了3/4,經(jīng)過不斷遞推，可以得到分裂次數(shù)比傳統(tǒng)減少了：

    不同圖像分裂的區(qū)域數(shù)如表1所示。

1.3 邊緣的歸并
    在分裂合并中，圖像的邊緣像素并沒有參加分裂操作。因此需要將邊緣的像素歸并到已經(jīng)分裂好的區(qū)域中。由于邊緣像素處在像素灰度迅速變化的區(qū)域，因此歸并算法十分簡單。對于每個邊緣像素，只需判斷該像素的八鄰域，將該像素歸并到與之最相似的八鄰域所在的區(qū)域中,不斷檢測圖中的邊緣像素，執(zhí)行歸并算法，直到每個像素都歸并到小區(qū)域中即可。
1.4區(qū)域合并
    圖像分裂成一些不規(guī)則的區(qū)域后，需要對相似的區(qū)域進行合并。由于使用區(qū)域內(nèi)的平均值作為一致性的判別根據(jù)，每個區(qū)域的最初被包含的元素對該區(qū)域的劃分影響較大。因此在合并的初期，應(yīng)該把最相似的區(qū)域首先合并。
    設(shè)R1為圖像中的區(qū)域，搜索與R1相鄰的每一個區(qū)域Rn，設(shè)置閾值T2，判斷dis2=|average(R1)-average(R2)|。
若dis2<T2，則將Rn并入R1所在區(qū)域中，重新計算average(R1)。為了使最相似的區(qū)域首先合并，開始時，應(yīng)賦予T2較小的值，然后使T2不斷遞增，繼續(xù)執(zhí)行上面的合并操作。
2 實驗結(jié)果分析
    如圖4~圖6所示,所有(b)圖左欄均為采用了本文算法，在邊緣的連接處，分塊數(shù)量并無明顯增多，且邊界光滑。所有(b)圖右欄均為采用傳統(tǒng)(一般)的分裂方法，在圖像的邊緣位置，分塊急劇增多，且有明顯的方塊效應(yīng)。從(c)圖中也可以看出，本文算法在圖像邊緣明顯的區(qū)域發(fā)揮了較大的作用。在區(qū)域邊界不明顯的區(qū)域，本文算法同其他算法一樣,只能通過不斷地對分塊進行分裂，以逼近區(qū)域的邊界，不可避免地會造成一些方塊效應(yīng)。

    從運行時間上比較,由1.2節(jié)中分析可以得知，在邊緣位置，本文算法可以明顯地減少分裂次數(shù)，相應(yīng)地，合并次數(shù)也可以減少許多。而在內(nèi)部區(qū)域則與其他算法一致。不足之處在于,由于本文算法中分裂后的形狀不規(guī)則，區(qū)域分裂過程中需要采用水壩法以確定區(qū)域的形狀，相對耗時較多。整體上，每張圖片的分割時間略高于普通的分裂合并算法。
    本文提出的結(jié)合邊緣檢測和分裂合并的圖像分割算法，有效地利用圖像邊緣信息進行區(qū)域分裂。由于最大限度地利用了圖像的邊緣信息，一定程度上避免了過分割和人為分割造成的方塊效應(yīng)。實驗表明，利用改進后的算法分割的邊界清晰光滑，效果理想。下一步的研究內(nèi)容是如何根據(jù)圖像實際情況自適應(yīng)地選擇相關(guān)參數(shù)對圖像進行分割，以及提高分割的運算速度，適應(yīng)圖像檢索系統(tǒng)的需要。
參考文獻
[1] Li Judong, Ge Yu, OGUNBNA P. An efficient iteractive algorithm for image thresholding[J].Pattern Recognition Letters,2008,29(9):1311-1316.
[2] 劉國英，傅明.一種基于多分辨分析的簡化的分裂-合并圖像分割算法[J].長沙理工大學學報，2006，3(4):77-79.
[3] HOROWITZ S L. Picture segmentation by a tree traversal algorithm[J]. Journal of the ACM,1976,23(2):368-388.
[4] BARRA V. Robust segmentation and analysis of DNA microarray spots using an adaptative split and merge algorithm[J]. Computer Methods and Programs in Biomedicine, 2006,81(2):174-180.
[5] WU X. Adaptive Split-and-Merge segmentation based on piecewise least-square approximations[M].IEEE Transactionson Pattern Analysis and Machine Intelligence, 1993:808-815.
[6] MERIGOT A. Revisiting image splitting[C]. Proceedings of IEEE International Conference on Computer Vision.[S.l.]: IEEE Computer Society, 2001:517-524.  
[7] EVANS A N, LIU X U.Amorphological gradient approach  to color edge detetion[J].IEEE Transactions.on Image  Processing, 2006,15(6):1454-1463.
[8] 尹平，王潤生.基于邊緣信息的分開合并圖象分割方法[J].中國圖像圖形學報, 1998，3(6):450-454.
[9] 謝鈞，俞潞，吳樂南.一種改進的Split-Merge圖像分割算法[J].計算機應(yīng)用, 2008,28(7):1744-174.