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

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

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

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

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