基于人機交互式圖割的目標快速提取*

徐秋平

(武警工程大學信息工程學院，陜西 西安 710086)

1 引言

目標提取是指利用灰度、顏色、紋理、形狀等信息從圖像中提取出感興趣的目標，它是圖像工程中目標表達、特征提取和參數測量的基礎，進而使得更高層的圖像分析和理解成為可能。人們利用各種數學理論和模型工具，研究出了錯綜復雜的目標提取方法。基于能量最小化理論，學者們提出了融合高層視覺線索和先驗知識的技術框架，給出了參數形式[1]、幾何形式[2]及組合優化形式[3,4]的活動輪廓模型。

利用圖割理論解決機器視覺問題是近年來組合優化領域發展起來的一個新興熱點分支[5]。其創新之處在于以人為本的交互方式[3]、新穎獨特的糾錯設計[4]、結合各種先驗知識的學習機制[6 - 9]、全局最優的求解能力[10,11]以及統一的問題解決框架[12]。圖割將圖像映射為1個s-t網絡，像素對應網絡節點，像素特征對應邊權值，割的容量對應能量函數，對s-t網絡進行最小代價切割得到機器視覺問題的解。

就目標提取問題而言，基于圖割理論主要有2類基本解決框架：一類是以GrabCut算法[13]為代表的基于區域信息的提取方法。GrabCut以高斯混和模型GMM(Gaussian Mixture Model)表征目標/背景，在GMM參數學習估計過程中用可進化的迭代算法來完成能量最小化。該方法要求概率模型有良好的表征和區分目標/背景的能力，概率模型參數的確定和海量計算是其面對的2大難題；另一類是以基于圖割的活動輪廓線GCBAC(Graph Cuts Based Active Contours)算法[14]為代表的基于邊緣信息的提取方法。GCBAC以邊緣梯度信息來表征目標邊界，從給定初始輪廓線的鄰域開始，迭代切割，更新鄰域，最終將活動輪廓線收斂至目標邊界。該類方法采用迭代局部尋優策略，難以避免陷入局部極值。

Figure 1 Roadmap of graph cut theory圖1 圖割理論技術路線

國內外研究人員就運用圖割理論解決目標提取問題進行了廣泛深入的研究。文獻[8]在Graph Cuts中加入先驗信息。文獻[15]提出一種新的查找最優路徑算法，提高了Graph Cuts目標提取質量。文獻[16]提出Lazy Snapping方法，在分割前利用K-means算法將圖像分成小塊，將各小塊作為s-t網絡中的節點，降低算法復雜度。文獻[17]提出了歸一化割Ncut(Normalized cut)，利用輪廓特征和紋理特征構建全局最小化代價函數，生成規則超像素，但圖像邊界保持不完整，計算量較大，處理大圖像時速度慢。文獻[18]采用支持向量機SVM(Support Vector Machine)分類器對每個像素進行后驗概率標記，然后使用基于圖割的概率傳播方法來自動提取復雜遙感圖像中的路網。文獻[19]綜合地震中毀損建筑形狀、邊、角的特征，構造能量函數，采用最大期望EM(Expectation Maximization)算法設定分類閾值，實現了高分遙感圖像中毀損建筑的檢測。文獻[20]以Lazy Snapping[16]為框架，引入多尺度分水嶺進行預分割，實現了基于區域的羊體圖像分割。文獻[21]采用交互分水嶺算法對圖像進行區域劃分，重新構造能量函數和s-t網絡，實現了生豬目標的快速準確分割。文獻[22]以interactive graph cuts[3]為框架，采用高斯混合模型計算t-link權值，去除人工標記環節，實現遙感圖像中水體自提取。文獻[23]先用歸一化割[17]方法完成冠層初始分割，以全局最大值代替局部最大值，實現單木精確探測。

后期對前期提取結果中的局部錯誤進行提示反饋并能夠糾正，是算法進一步提高準確率的重要舉措，也是基于圖割進行目標提取的特色機制。圖割理論因其特有的s-t網絡結構而能夠便捷地進行后期糾錯。如，GCBAC[14]算法通過在目標邊界添加硬約束點，約束活動輪廓線必須經過所添硬約束點來實現糾錯；Interactive graph cuts[3]、GrabCut[13]和OneCut[24]等算法則通過在錯誤區域添加目標或背景種子實現糾錯；文獻[25]則通過人工指定糾錯域，對其重新切割實現糾錯。

人機交互式方法本質在于人與機器的整合，既融入了人獨有的智力判斷，又利用了機器強大的計算能力，使得目標提取速度更快、精度更高、可操控性更強。人機交互式目標提取方法在諸如醫學目標獲取、運動目標識別等領域有著廣泛應用。

本文以基于邊緣信息的圖割提取框架為基礎，對活動輪廓線迭代過程進行深入研究分析，重新構造能量函數與s-t網絡，消除前后重疊，避免重復切割，并在提取后期輔以手自結合的糾錯手段，尋求一種人機交互方便快捷，糾錯方式有效完備，目標提取快速準確的提取算法。

2 技術路線

圖割理論的技術路線是將目標提取問題轉化為能量最小化問題，并運用組合優化技術獲取能量函數的全局最優解。如圖1所示，首先將目標提取問題歸結為將圖像像素P標為L={目標,背景}的f:P→L的標號問題，進而通過構造能量函數，將其轉換為1個能量最小化的優化問題；然后構造s-t網絡，將問題轉化為1個網絡最小割問題；最后根據最大流-最小割定理將問題轉化為網絡最大流問題。目前已有諸多經典成熟算法可在多項式時間內對網絡最大流問題求得最優解。

Figure 2 Algorithmic design圖2 算法設計

3 算法設計

本文算法基本設計如圖2a所示，在目標邊界附近，以人機交互方式輸入1條封閉的多邊形折線作為初始活動輪廓線。以其為基準，向兩側膨脹固定寬度得到1個環狀域。運用圖割理論，對該環狀域構造s-t網絡并進行最小代價切割得到1條新的活動輪廓線。由此經過若干次迭代，最終活動輪廓線變形至目標邊界。

4 算法實現

在圖像中，目標邊界像素顏色值的劇烈變化是圖像重要的基本特征，因此，可通過構造能量函數對目標邊界的這一重要基本特征加以表達，并映射成s-t網絡，通過最小代價切割來識別目標邊界。

4.1 構造能量函數

在s-t網絡中，若2個相鄰節點對應的像素處于非邊緣處，則二者間的邊權值應較大，從而將二者切斷的代價較高；反之，若2個相鄰節點對應的像素處于邊緣處(如1個是目標中的像素，另1個是背景中的像素)，則二者間的邊權值應較小，使得將二者切斷開的代價較低。本文算法通過式(1)來表征具備上述2個特性的2個像素間的RGB值間的距離，采用式(2)設計s-t網絡邊權值wij，進而構造實現目標提取的能量函數。

Cij=‖Ii-Ij‖2

(1)

其中，Ii和Ij分別為節點i,j所對應像素顏色值(一般可取RGB值)。

(2)

其中，E為s-t網絡邊集。

4.2 構造s-t網絡

當前環狀域覆蓋部分目標邊界段后，需要構造合適的s-t網絡，使得最小代價切割后，所得活動輪廓線能夠經過這些覆蓋的目標邊界段。

以環狀域外邊界作為s-t網絡源點s，內邊界作為s-t網絡匯點t，環狀域內部每個像素映射為1個網絡節點，以8鄰域方式連接相鄰節點，邊權值為式(2)中的wij。對于與源點s或匯點t相連的內部節點，其權值為該節點所對應的像素與環狀域外邊界或內邊界中所有相連接的像素的權值累加。

在以上述方法構造的s-t網絡中，邊權值大小與邊的粗細正相關，目標邊界兩側節點所對應的像素顏色值變化劇烈，所連接的邊的權值較小，目標邊界經過的所有邊的權值累加也為最小。因此，目標提取問題最終轉化為對該s-t網絡進行最小代價切割，也就是對s-t網絡進行切割，得到曲線f，曲線所經過的邊的權值之和為該條曲線所對應的切割代價cost(f),切割代價最小的曲線對應目標邊界，即：：

(3)

5 算法完善

第3節通過構造能量函數和映射s-t網絡，得到了具備目標提取功能的初步算法。在具體實現中，繼續對初步算法進行改進，得到1個效率更高、交互方式更為完整的完善算法：

(1)重新構造s-t網絡，提高算法提取效率。初步算法的鄰域是1個以固定寬度向活動輪廓線兩側膨脹的環狀鄰域(以下稱“雙側定寬域”)，如圖2b所示，本文將其改造為單側向內膨脹、寬度可變的單側變寬域(以下稱“單側變寬域”)，大幅減少切割s-t網絡的時間消耗，顯著提高算法效率。

(2)引入后期糾錯機制，凸顯人機交互特色。目標提取的復雜性使得算法難以做到完全正確提取目標，本文巧妙沿用前期目標提取算法框架，給出了一種方便快捷、安全導向、手自結合的糾錯方法。

5.1 設計單側變寬域

(1)定寬域向變寬域的改進。

當前活動輪廓線經過若干次變形后，部分活動輪廓線到達了目標邊界(以下稱“已達段”)；部分尚未到達目標邊界(以下稱“未達段”)。隨著迭代的進行，已達段越來越多，未達段越來越少，最終未達段消失，已達段構成目標邊界。

對已達段，在之后的迭代中，由于已經到達目標邊界，不再變化，顯然之后對其膨脹生成的鄰域進行切割已無必要。但是，初步算法沒有對當前活動輪廓線進行“已達”與“未達”的分類，仍會對已達段所在鄰域進行切割。隨著活動輪廓線逼近目標邊界，已達段越來越多，這種無效切割問題愈顯突出。

因此，可對當前活動輪廓線進行“已達”與“未達”分類，迭代時僅對未達段所在鄰域進行切割，從而避免無效切割，提高算法效率。要實現該思路，有2個問題要解決：一是如何判定已達段，二是如何避免對已達段所在鄰域反復切割。

①已達段的判定。

已達段已經到達目標邊界，因而其具有不再變化的性質。理論上，可將當前活動輪廓線Ci與前1次活動輪廓線Ci-1進行比較，其不變部分判定為已達段。但是，實際上Ci與Ci-1中可能會存在少數位置暫時不變但并未真正到達目標邊界的像素，這些像素一旦被誤判為“已達”后就會被錯誤固定下來，造成算法失敗。

為避免上述問題，本文通過取連續n次(n≥2)活動輪廓線進行比較來減少誤判。n值越大，誤判可能性越低，但會推遲部分曲線段的“已達”判定。在實踐中，n=3時即可在減少誤判的同時對活動輪廓線進行有效分類。

②避免反復切割已達段。

如何實現不再對已達段所在鄰域切割？考慮到不調整算法基本架構，本文采取的策略仍是統一進行切割，通過將已達段所在鄰域寬度壓縮為零來實現對已達段所在鄰域切割代價為0，從而來等價實現避免反復切割。具體步驟為：對未達段，仍向兩側膨脹，形成固定寬度的鄰域；對已達段，向外側膨脹1個像素，形成寬度為0的輪廓線鄰域。由此將原來寬度固定的環狀鄰域變為寬度可變的0-1脈沖式鄰域。

在將上述變寬域映射成s-t網絡時，變寬域內外邊界分別對應s-t網絡單一的源點、匯點，已達段的零寬度鄰域被映射到單一的源點、匯點中，從而實現了零代價切割且切割后已達段位置保持不變。

(2)雙側域向單側域的改進。

如圖3所示，為便于觀察分析，假設活動輪廓線鄰域寬度為d，初始輪廓線與目標邊界相距4d，二者之間為白色勻質區域。1次切割后，當前活動輪廓線變形到其鄰域內邊界，即活動輪廓線以每次d/2的速度逼近目標邊界。

Figure 3 Improvement of neighborhood from bilateral-way to unilateral-way圖3 雙側域向單側域的改進

分析上述迭代切割過程可以發現：先后2條活動輪廓線所生成的鄰域有d/2寬度的位置重疊，這種重疊會造成先后2次對該d/2寬重疊區域進行重復切割。在上述場景中，初始輪廓線與目標邊界相距4d，一共要進行8次寬度為d的區域切割，會造成7次對d/2寬重疊區域的重復切割，這種對重疊區域的重復切割對算法并沒有貢獻。

區域重疊的原因在于初步算法以當前活動輪廓線為中心雙向膨脹。而之所以雙向膨脹，則是因為算法設定初始活動輪廓線在目標邊界附近，即目標邊界有可能在初始活動輪廓線內側，也有可能在外側，這樣在迭代時，部分活動輪廓線要向外側運動，其余部分活動輪廓線要向內側運動。因此，可將初始活動輪廓線設定在目標邊界外側，使其僅向內側單方向運動，即可避免前后鄰域重疊，杜絕重復切割，提高算法效率。

(3)單側變寬域到s-t網絡的映射。

由于單側變寬域是以當前活動輪廓線為基準單側向內，同時注意到最大流-最小割算法切割所得輪廓線可能經過源點但不會經過匯點，因此將單側變寬域的內側邊界映射為s-t網絡的源點s，外側邊界映射為s-t網絡的匯點t。

每個像素點映射為1個網絡節點，相鄰節點間以8鄰域方式連接，邊權值為式(2)中的wij。

特別地，s-t網絡中的非邊界節點與源點s(匯點t)連接的權值為該節點對應像素與單側變寬域外(內)側邊界中所有8鄰域方式相連接的像素的權值累加和。

5.2 設計手自結合糾錯

文獻[25]給出了一種基于圖割的目標提取實時糾錯方法，其基本流程如圖4a所示：前期方法得到1條局部存在錯誤的輪廓線，通過鼠標在錯誤所在區域創建1塊“糾錯域”(如圖4b所示)，并對其構造s-t網絡(如圖4c所示)，進行最小代價切割，得到糾錯域內正確的目標曲線段(如圖4d所示)，且該曲線段能夠與已有正確的曲線段無縫連接(如圖4e所示)。

Figure 4 Later correction of local errors圖4 局部錯誤的后期糾正

Figure 5 Effectiveness verification of preliminary extraction and later error correction圖5 前期目標提取與后期錯誤糾錯的有效性驗證實驗

上述方法能夠以交互方式自動實現目標邊界錯誤部分重新提取、正確部分保持不變的糾錯功能。但是，自動糾錯方式在目標邊界不夠清晰等較為極端情況下可能會失效，為此，本文對上述方法進一步進行研究分析，實現全手工方式的糾錯。

如圖4c所示，把s-t網絡中所有與匯點t(即糾錯域外邊界)相連接的邊記作:

ET={(k,t)|(k,t)∈E}

(4)

事實上，在調整區中，穿過邊集ET的曲線段正是通過鼠標輸入的折線線段。若能夠控制調整區中的切割線恰好穿過邊集ET，即可實現完全手工的糾錯方式。因此，

對邊集ET，令:

wij=0,(i,j)∈ET

(5)

在調整區中，經過邊集ET的切割代價為0，而切割時輪廓線必然經過邊集ET，也就是鼠標輸入的折線線段，因此可通過設置邊集ET的權值為0來實現完全手工的糾錯目標。

6 實驗分析

本文所用實驗平臺：(1)計算機：聯想ThinkPad X280,CPU Intel i7-855U 1.8 GHz,內存16 GB；(2)操作系統：Windows 7 64位簡體中文旗艦版；(3)仿真軟件：Matlab R2019a；(4)圖像來源：伯克利圖像分割測試圖庫BSDS500(Berkeley Segmentation Data Set and Benchmarks 500)。

6.1 有效性實驗

取1幅編號為227092的圖像進行目標前期提取及后期局部糾錯的全過程有效性驗證實驗。環狀域寬度取20個像素，在目標外圍人工勾劃1條封閉折線(如圖5a所示)，以該多邊形作為初始活動輪廓線，得到圖5b所示提取結果。可見，活動輪廓線錯誤停止于陶器雙耳內側邊界。分別通過2次人機交互干預，錯誤得到自動糾正(如圖5c和圖5d所示)。又因陶器底部右側部分釉面脫落，底座與地面融為一體，致使活動輪廓錯誤停止于釉面斷層處，未能正確停止于底座，當采用自動修正方式時，也因邊界不清晰而失敗。此時通過完全手工控制鼠標繪制軌跡，將該錯誤糾正(如圖5e和圖5f所示)。經過人機交互式的前期提取與后期糾錯，得到最終的提取目標(如圖5g所示)。

6.2 對比實驗

考慮本文算法是圖割中基于邊緣信息類的提取算法，算法技術路線也來自于經典的GCBAC算法，因而將本文算法與GCBAC算法進行對比。

為保證算法對比科學有效，作以下處理：(1)GCBAC算法無法對彩色圖像進行目標提取，因而需先將圖像由彩色圖像變換為灰度圖像，之后根據灰度圖像的提取結果獲取對應的彩色圖像提取結果。(2)約定2個算法的初始輪廓線相同，由于本文算法的活動輪廓線為單側向內運動，因而初始輪廓線需在目標邊界外側而不是附近。(3)為使2個算法迭代次數相當，方便對比，本文算法鄰域寬度取GCBAC算法鄰域寬度的一半。

Figure 6 Comparison of extraction result and time consumption圖6 提取結果與時間消耗對比實驗

實驗設定：待提取圖像編號124084，像素大小481×321。初始輪廓線相同，GCBAC算法鄰域寬度36個像素，本文算法鄰域寬度18個像素。

實驗結果：2個算法均迭代20次，耗時分別為0.335 s和0.947 s，目標提取正確率分別為95.83%和97.02%。

對比分析：如圖6所示，(1)經過前3次(占比15%)的迭代切割，2個算法的活動輪廓線大部分已到達目標邊界，剩下的17次(占比85%)迭代切割均用來獲取剩余的小部分目標邊界段。此時，GCBAC算法鄰域定寬不變，對已達段反復切割；而本文算法鄰域可變，在已達段鄰域寬度為0，切割代價為0，而僅切割未達段所在鄰域，切割效率顯著提升。(2)隨著迭代切割推進，活動輪廓線因貼近目標邊界而變長。此時，GCBAC算法因鄰域定寬不變，待切割的鄰域隨活動輪廓線長度增加而增加；而本文算法鄰域可變，待切割的鄰域隨未達目標邊界段的減少而減少，從而切割時間消耗呈現一增一減的強烈反差。(3)2個算法目標提取正確率相當，無顯著差異。(4)本文算法耗時約為GCBAC算法的1/3。

如表1所示，從測試圖庫中選取更多圖像進行對比實驗。本文算法與GCBAC算法平均正確率之比為92.75∶92.78,約為1∶1，平均耗時之比為0.39∶0.99,約為2∶5，結果進一步表明總體上2個算法目標提取正確率相當，無顯著差異，但本文算法耗時顯著小于GCBAC算法耗時。

Table 1 Comparison of a set of experimental results表1 1組實驗結果對比

上述實驗結果表明，本文算法既能有效繼承經典GCBAC算法目標提取精度高的優點，又能穩定實現算法效率的顯著提升。當前期提取結果出現局部錯誤時，本文算法能夠通過簡單便捷的人工交互，根據需要手自結合，有效地對局部錯誤進行徹底糾正。此外，本文算法利用RGB顏色值表征像素距離，實現了彩色圖像的目標提取，拓展了算法的應用范圍。

7 結束語

目標提取是模式識別與圖像分析首要解決的關鍵問題，也是圖像處理的基礎課題。因此，設計一個以人為本、快速有效的目標提取算法將為后續的目標特征提取、識別與分類、跟蹤與理解等研究打下堅實基礎。本文利用圖像邊緣信息，運用圖割理論，提出了一種操作便利、響應快速、提取準確的人機交互式目標提取算法，并在算法后期輔以手自結合的完備糾錯機制，滿足在醫學目標獲取與測量等交互環境下的目標提取需求。但是，本文算法在目標背景較為復雜時容易陷入局部極值，造成提取正確率下降。對圖像進行降噪預處理、探索新的目標邊界特征、融合目標形狀先驗知識，是進一步提高本文算法提取性能的努力方向。