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

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

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

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

    由于交互式分割方法受人為交互作用的影響較大，進行算法對比分析比較困難，實驗中盡可能保證所提供交互信息相同。從實驗數據可以看出，本算法準確率高于其他3種方法，并且在實際中，隨著提供交互信息可靠性的提高，準確率也會隨之提高。
    雖然二維圖動態切分算法在圖像分割中有較好的結果，但由于該算法最優路徑搜索基于全圖擴展，使得算法在應對大圖像時出現執行效率低的缺點，并且難以應對邊緣彎曲度較大的區域。本文針對以上不足，在最優路徑搜索中對搜索區域的范圍及方向進行了控制，并且引入了圖像的角點信息和動態軌跡長度，提高了算法的執行效率以及魯棒性,并通過實驗驗證了算法的有效性。
參考文獻
[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.