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

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

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

    不同圖像分裂的區域數如表1所示。

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

    從運行時間上比較,由1.2節中分析可以得知，在邊緣位置，本文算法可以明顯地減少分裂次數，相應地，合并次數也可以減少許多。而在內部區域則與其他算法一致。不足之處在于,由于本文算法中分裂后的形狀不規則，區域分裂過程中需要采用水壩法以確定區域的形狀，相對耗時較多。整體上，每張圖片的分割時間略高于普通的分裂合并算法。
    本文提出的結合邊緣檢測和分裂合并的圖像分割算法，有效地利用圖像邊緣信息進行區域分裂。由于最大限度地利用了圖像的邊緣信息，一定程度上避免了過分割和人為分割造成的方塊效應。實驗表明，利用改進后的算法分割的邊界清晰光滑，效果理想。下一步的研究內容是如何根據圖像實際情況自適應地選擇相關參數對圖像進行分割，以及提高分割的運算速度，適應圖像檢索系統的需要。
參考文獻
[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].計算機應用, 2008,28(7):1744-174.