摘  要：提出了基于邊緣提取的交互式圖像分割算法，該算法將圖像映射為無向圖，使用拉普拉斯零交叉點、邊緣強度和動態(tài)軌跡長度構(gòu)造能量模型，并為無向圖中的邊賦予能量代價。根據(jù)能量代價，引入角點信息，在交互得到的控制點間搜索最優(yōu)路徑，迭代此過程，實現(xiàn)分割。實驗結(jié)果表明，該算法具有較高的精度和效率，能較好地克服噪聲影響，適用于灰度及彩色圖像。
關鍵詞： 圖像分割; 交互; 邊緣; 能量模型

    圖像分割是依據(jù)圖像的某種屬性特征將圖像分成若干區(qū)域，并在這些區(qū)域中提取出感興趣的物或景的技術和過程，這些特征既可以是圖像的固有屬性特征，也可以是在空間頻域中構(gòu)造的特征(如灰度值、邊緣輪廓、顏色和紋理等)。圖像分割是從圖像處理到圖像解析的關鍵步驟。手動分割過于繁瑣，需要消耗大量的人力與時間；自動分割常基于圖像的某種特性進行分割，在實際應用中，由于需求的不同，感興趣的目標也不盡相同，自動圖像分割很難有效分割；與前兩者相比，交互式分割綜合了兩者的優(yōu)點，在人的干預下能準確高效地分割圖像，得到廣泛重視。
    對于圖像分割技術的研究，其代表性工作包括：基于特征聚類的方法[1-2]、基于邊緣檢測的方法[3-4]和基于圖切的分割方法[5]等。上述方法中，未能充分借助交互所提供的信息,并且過多依靠圖像邊緣特征進行分割，使算法執(zhí)行效率低，魯棒性差，分割效果不理想。為保證分割效果準確的同時提高圖像分割的效率，本文提出一種基于邊緣提取的交互式分割算法。首先,將全局范圍的搜索精簡到局部范圍，減少搜索節(jié)點的數(shù)目，提高了算法的執(zhí)行效率；其次,引入圖像的角點特征，以應對彎曲度顯著變化的邊緣；最后,引入動態(tài)軌跡長度，克服偽輪廓的干擾并且可以平滑所得到的邊緣。
1 基于邊緣提取的交互式圖像分割算法
    通過在目標區(qū)域邊緣附近移動鼠標得到控制點信息后，構(gòu)造能量模型，并將二維圖像映射到無向圖。其中，像素點被映射為無向圖中的節(jié)點，像素點與其8鄰域內(nèi)的點均構(gòu)成一條邊，根據(jù)能量模型，每條邊被賦予一個能量代價。在無向圖上，使用Dljkstra’s的最優(yōu)路徑算法求得控制點間的最優(yōu)路徑。迭代上述過程，最終實現(xiàn)分割。其中，能量模型包括拉普拉斯零交叉點、邊緣強度和動態(tài)軌跡長度3部分。
1.1 交互方式
    交互式的分割方法需要利用用戶實時提供的“準邊緣”信息，在二維圖上迭代計算最優(yōu)路徑，并且在滿足算法收斂條件時鎖定軌跡路線，直至分割完成。“準邊緣”信息由用戶鼠標在目標區(qū)域邊緣附近游走提供，并且可以控制軌跡的鎖定。算法執(zhí)行過程中可根據(jù)收斂條件進行軌跡路線的鎖定，但對于復雜圖像或含有大量噪聲的圖像，借助用戶控制鎖定軌跡則更為準確。

1.3 最優(yōu)路徑搜索
    在基于圖論的交互式分割方法中，用戶實時地提供控制點，算法針對整幅圖像在兩控制點間搜索最優(yōu)路徑。搜索的效率受圖像的大小影響，因此，算法在處理大圖像時運算效率降低。但是，由于交互的作用，兩控制點間存在著空間上的相互聯(lián)系，借助這種關系可以將整幅圖從全局搜索縮小至兩控制點某范圍尺寸內(nèi)局部搜索。局部圖的建立是根據(jù)p、q(p、q為兩控制點,其中p為前點、q為后點）兩點的坐標確定的。其計算方法如下。
 
　基于對搜索范圍以及搜索方向的控制，使得算法在執(zhí)行效率上得到提高。搜索過程如圖1所示。其中，左上部分為初始圖，右上部分為搜索結(jié)果圖，箭頭線連接經(jīng)過的邊緣節(jié)點。下側(cè)為搜索執(zhí)行前3步的結(jié)果，圓圈區(qū)域為搜索經(jīng)過的節(jié)點，深色區(qū)域為擴展的節(jié)點。圖1上側(cè)居中部分表示搜索方向控制圖，其中p為起始點，q為終止點，根據(jù)q點位置確定擴展的節(jié)點：若q在A區(qū)，擴展節(jié)點1、2、3；若q在B區(qū)，擴展節(jié)點3、4、5；若q在C區(qū)，擴展節(jié)點5、6、7；若q在D區(qū)，擴展節(jié)點7、8、1。若q在a線，擴展節(jié)點2、3、4；若q在b線，擴展節(jié)點4、5、6；若q在c線，擴展節(jié)點6、7、8；若q在d線，則擴展節(jié)點1、2、8。
1.4 角點信息
    “角點”是穩(wěn)定的圖像邊緣信息。引入圖像的角點特征可以更加準確定位圖像的邊緣。借助角點的穩(wěn)定性可以消除偽輪廓的干擾，提高抗噪能力。
    Harris角點[6]定義的基礎是圖像灰度強度的二階導數(shù)(?墜2x，?墜2y，?墜x?墜y)矩陣。對于圖像中的所有像素點，其二階導數(shù)形成Hessian圖像。此術語源自于一個點的二維Hessian矩陣如式(10)定義:
　   
　    Harris算法取以目標像素點為中心的小窗口，將窗口沿任意方向移動并計算窗口內(nèi)灰度的變化，取其中最小值為該目標像素點的角點響應函數(shù)值，若該值大于閾值，則為角點。對于Harris角點，使用每點周圍小窗口的二階導數(shù)圖像的自相關矩陣，此矩陣定義為：
    
其中，ωi,j是可以歸一化的權重比例。Harris定義的角點能定位周圍存在多個方向的邊緣或紋理的點。矩陣H(p)的行列式值和H(p)的跡(帶權重系數(shù))這兩個特征值中，若較小的一個大于最小閾值，則得到角點。將整幅圖像中的角點保存起來，當動態(tài)規(guī)劃時，將當前點與所有角點進行匹配，若在一定范圍內(nèi)匹配成功，則當前點定位至角點位置。由起點到當前點采用動態(tài)規(guī)劃的算法獲得路徑，并進行鎖定。
1.5 算法流程
    首先，載入圖像對原始圖像進行預處理，得到算法執(zhí)行中所需特征值：灰度圖像Ig、梯度圖像Id、拉普拉斯算子卷積圖Il以及圖像的角點序列。然后，根據(jù)算法中所需特征值，采用Dljkstra’s的動態(tài)規(guī)劃最優(yōu)路徑的算法，搜索用戶輸入的起始點與終止點間的最優(yōu)路徑，這條路徑即為所求邊緣。動態(tài)路徑規(guī)劃算法如下。
　    數(shù)據(jù)結(jié)構(gòu)：
　    S               {起始點}
　    E               {終止點}
　    Cost(p,q)        {p、q兩點間的權值代價}
　    List             {已擴展節(jié)點鏈表}
　　Map            {圖像節(jié)點擴展標記矩陣}
　    N(p)            {p點的相鄰節(jié)點（已精簡）}
　    T(p)            {從S點到p點的累積權值代價}
　    輸出：
　    O                {保存搜索路徑上的節(jié)點}
　    算法：
　        T(S)=0; Insert(S,List) {初始化鏈表，壓入S點}
　        While (List)      {仍然有可擴展的節(jié)點}
　        P=First(List);  {取權值代價最小的節(jié)點}
　　        Map(P)=1；   {標記已擴展節(jié)點}
　        Get N(S,E,P);  {求與P相鄰的節(jié)點}
　        For each q in N(p) and Map(q)=0 do begin
　            C=T(p)+Cost(p,q);  {計算累積代價}
　            If q in List and C<T(q)
　                Delete(List, q);   {刪除高代價節(jié)點}
　            If q in List then begin
　                T(q)=C;     {設定權值}
　                Path(q);     {添加q到S的路徑}
　                Insert(q,List);
　            End
　        End
　    End
2 實驗結(jié)果
　    實驗結(jié)果如圖2所示。其中，原始圖像lenna圖是一幅具有光照干擾的彩色圖，并且所分割區(qū)域在視覺角度上像素值相差較小。在canny算子圖像中可以看到所分割區(qū)域邊界存在干擾，尤其是在光照部分產(chǎn)生了偽輪廓。而本算法則克服了干擾，取得了比較準確的效果。

    對于數(shù)據(jù)庫中的圖像選擇人物、動物、交通工具、家電和陳設物品5類進行對比分析，每類選取30張圖像。實驗中分別采用人工標記、分水嶺、二維圖動態(tài)切分方法以及本文算法對上述5類圖像集進行分割，其平均準確率如表1所示。

    由于交互式分割方法受人為交互作用的影響較大，進行算法對比分析比較困難，實驗中盡可能保證所提供交互信息相同。從實驗數(shù)據(jù)可以看出，本算法準確率高于其他3種方法，并且在實際中，隨著提供交互信息可靠性的提高，準確率也會隨之提高。
    雖然二維圖動態(tài)切分算法在圖像分割中有較好的結(jié)果，但由于該算法最優(yōu)路徑搜索基于全圖擴展，使得算法在應對大圖像時出現(xiàn)執(zhí)行效率低的缺點，并且難以應對邊緣彎曲度較大的區(qū)域。本文針對以上不足，在最優(yōu)路徑搜索中對搜索區(qū)域的范圍及方向進行了控制，并且引入了圖像的角點信息和動態(tài)軌跡長度，提高了算法的執(zhí)行效率以及魯棒性,并通過實驗驗證了算法的有效性。
參考文獻
[1] Li Chunming, Xu Chenyang, Gui Changfeng,et al. Distance  regularized level set evolution and its application to image segmentation [J]. IEEE Transactions on Image Processing, 2010,19(12):3243-3254.
[2] NUZHNAYA T, Cheng Erkang, Ling Haibin,et al.Segmentation of anatomical branching structures based on texture  features and graph cut [C]. IEEE International Symposium  on Biomedical Imaging: From Nano to Macro, Chicago, 2011: 673-676.
[3] Wang Hongrui, Yang Jianli, Sun Haijun, et al. An improved region growing method for medical image selection and evaluation based on canny edge detection[C]. International Conference on Management and Service Science, Wuhan, 2011:1-4.
[4] KHAN N M,RAAHEMIFAR K. A novel accelerated greedy  snake algorithm for active contours[C]. Canadian Conference on Electrical and Computer Engineering,Niagara Falls,2011:186-190.
[5] Zheng Shuxian,Li Jia,Sun Qingfeng.Extraction of the borderline in prepared tooth cavity based on intelligent scissors[C].International Conference on Bioinformatics and Biomedical Engineering, Shanghai, 2008:680-683.
[6] HARRIS C, STEPHENS M. A combined corner and edge detector[C]. Proceedings of the 4th Alvey Vision Conference, Manchester, 1988:147-151.