一、相關背景：圖像摳圖

圖像摳圖指的是將圖像中需要的部分從畫面中提取出來，也叫去底。通常地，人們用圖像摳圖技術從一幅圖片中將某一部分截取出來，然后和另外的背景圖像進行合成生成一幅新的圖像。如我們可以把人物肖像從一幅圖像中摳取出來放到另一幅美麗的自然風景圖片中，加工成一幅藝術作品。

Adobe公司的知名圖形處理軟件PhotoShop中提供了套索工具對圖像進行摳圖操作，Corel公司開發(fā)的專業(yè)摳圖軟件Knockout也提供了摳圖操作，并且連細小的毛發(fā)都能從復雜的背景中分離出來。但是這些軟件的使用比較復雜，如果不經過一段時間的培訓和練習，用戶很難掌握摳圖操作的要領。

微軟亞洲研究院的研究員們在2004年世界最頂尖的計算機圖形學學術會議SIGGRAPH上發(fā)表了一篇名為《Lazy Snapping》的圖像摳圖技術的文章。利用Lazy Snapping技術，用戶只需要進行一些簡單的操作，就可以將圖像中需要的內容截取出來。其基本操作界面就是讓用戶在圖像的不同區(qū)域中隨意畫幾條線，來分別表示所需要的部分和不需要的部分；軟件根據用戶所畫的線條來自動摳取出圖像中所需要的部分。Lazy Snapping技術使得圖像摳圖操作變得異常簡單與方便，使其成為圖像摳圖中的一種嶄新的實用技術。

二、輕松曲面切割軟件

在三維計算機圖形學中，人們也常常需要從一個已知物體上選取并切割出一部分，然后進行諸如編輯、變形和拼接等操作。通常地，人們認識一個幾何物體形狀，往往是從“高層認知”的角度將其分解為若干個有意義的部分，如對于人或者動物的模型來說，人們從視覺認知上都將它們分解為頭部，身體和四肢等部分來認識。如何快速地從一個已知物體上選取并切割出一個有意義的子部分，一直是擺在計算機圖形學科研工作者面前的一個難題。

基于《Lazy Snapping》圖像摳圖技術所采用的線畫用戶操作的簡便性，我們將這種用戶交互技術用于三維物體的選取和切割中，并于2006年世界頂尖的歐洲計算機圖形學學術會議EUROGRAPHICS上發(fā)表了一篇名為《Easy Mesh Cutting》的論文。使用我們的技術，對于絕大多數物體來說，只需要輕松的幾步操作，就可以將我們需要的子部分切割出來。

比如，我們想要將一只兔子的頭部選取出來。首先，我們按住鼠標左鍵，在需要選取的區(qū)域——兔子的頭部表面，隨意劃條線（綠線），然后，在兔子的非頭部的部位，如身上，點住鼠標右鍵再隨意劃條線（紅線），軟件就會根據用戶所劃的綠線和紅線信息自動地計算出綠線所表示的部分，你會發(fā)現綠線所在的部分會被顯示成紫紅色，而這正是用戶所希望得到的“有意義”的部分，即兔子的頭部，如圖1(a)。

圖1 利用輕松曲面切割工具，我們可以很輕松并很準確地選取出模型中的某個部分，并將此部分從模型中切割出來，然后用于其他應用中，如和其他模型合成一個新的模型。

對于大部分的模型，特別是對于那些子部分之間的分界線比較明顯的模型，只需要做到上述的一步就很容易得到所需要的部分。但是子部分之間的分界線可能會出現少數不規(guī)則或者不精確的邊界線，我們則可以進行邊界微調。這一步的操作依然非常簡單，用戶可以直接利用鼠標選取分割邊界線的頂點并進行拖動以修改其位置；用戶還可以很簡單地利用軟件提供的粗畫筆功能，在邊界線不夠準確的地方利用鼠標隨著邊界刷一下，軟件就會自動將所希望的邊界線準確地勾畫出來，如圖2。

另外，對于最后的分割結果，由于表示模型的頂點數可能比較稀疏，所得到的子部分的邊界線就可能會出現鋸齒形狀，軟件會利用蛇形曲線原理自動優(yōu)化邊界線，使其盡量光滑，如圖3。

圖2 利用軟件提供的粗畫筆功能，用戶只要在邊界線不夠準確的地方利用鼠標隨著邊界刷一下(c)，軟件就會自動將所希望的邊界線準確地勾畫出來(d)

圖3 軟件會利用蛇形曲線原理自動優(yōu)化邊界線，使其盡量光滑

對于特別復雜的模型，用戶只劃一條綠線和一條紅線來標注區(qū)域往往不能得到所滿意的分割結果。這時用戶可以劃多條綠線和紅線來標注更精確的部位。由于整個過程都能實時看到分割結果的，因此用戶能很輕松地根據分割結果來交互標注更多的部位，直到得到滿意的分割結果。如圖4所示，龍的一個浮雕模型位于一張帶有很多噪音的曲面上，即使是人眼也不太容易能區(qū)分出龍的邊界線。在我們的軟件中，用戶只要輕松地劃如圖的3條綠線和5條紅線，即可很精確地分割出龍的模型出來。

圖4 用戶可以劃多條綠線和紅線來得到滿意的分割結果

三、技術基礎：基于特征的區(qū)域增長法

區(qū)域增長技術是計算機圖像和圖形學中的一個常用技術，也是Easy Mesh Cutting的核心技術。在我們的軟件中，物體表面是由許多采樣點所表示的，然后頂點和頂點之間通過邊的連接關系構成三角片，從而構成整個物體表面。用戶通過在物體表面上劃線，告訴了軟件曲面上哪些是用戶想要的部分，而哪些是用戶不想要的部分。這些劃線經過了曲面上的一些頂點，這些頂點我們稱為“種子點”，這些“種子點”所涉及的區(qū)域稱為“種子區(qū)域”。軟件就根據這些“種子區(qū)域”將物體表面分為“前景區(qū)域”和“背景區(qū)域”兩大類，分別表示用戶所想要的部分和不想要的部分。

如何由種子點擴張成種子區(qū)域的過程就要用到區(qū)域增長的技術。簡單地講，對于所有未歸類的頂點，軟件先根據某個度量來計算這些頂點分別到兩個區(qū)域邊界的距離，然后選擇距離值最小的那個頂點將它歸并到這個距離值所對應的區(qū)域內，此時區(qū)域的范圍就增長了一個頂點。隨著上述過程的不斷重復，兩個區(qū)域都在同時不斷地增長，直到所有頂點都被歸類，此時物體表面就被分成前景區(qū)域和背景區(qū)域兩大塊，兩大區(qū)域分別表示了物體分割后的不同部分，這樣就完成了整個分割過程。

在上述過程中，計算一個未歸類的頂點到已知區(qū)域邊界的距離是基于一個最近提出的新度量，稱為Isophotic度量。對于曲面上兩點之間的連線，Isophotic度量不僅考慮了連線的長度，而且還考慮了連線上的曲面法向量的變化。因此這種度量是一種基于曲面特征敏感的度量。我們根據計算機視覺研究的理論，人的感知對于物體分割部分的最小化規(guī)則(minimal rule)，將Isophotic度量進行了改進，將頂點連線的曲面曲率的變化信息也加入到Isoph- otic度量，有效刻劃了最小化規(guī)則。我們改進的Isoph- otic度量，能很有效地刻劃曲面的細微特征變化。

改進后特征敏感的Isophotic度量是我們軟件的核心技術之一，它考慮了每一個未歸類頂點與種子區(qū)域之間的幾何相似性，幾何特征越像“前景區(qū)域”就越可能被分在前景區(qū)域。將這種新的度量應用到區(qū)域增長算法中，對于一個結構比較簡單的物體來說，如果其前景部分和背景部分的分解線的幾何特征非常明顯，則前景部分很容易就被分割出來了。而對于前景部分和背景部分的分解線的幾何特征不太明顯，則我們的軟件可能得不到的用戶滿意的分割結果，此時就需要用戶再次進行交互指定更多的信息。

我們軟件中的另一個核心技術就是分割邊界線的優(yōu)化方法，它是基于一種稱為蛇形曲線(snake)來進行優(yōu)化的。蛇形曲線是一種帶有能量的曲線，曲線能根據自身的能量和某些外在能量進行最小化優(yōu)化來達到一個能量最小化的狀態(tài)。我們對傳統(tǒng)的蛇形曲線的能量進行了有效的改進，使其外在能量是根據它所在的曲面的位置的幾何特征相關的，這樣邊界線優(yōu)化后就能有效消除鋸齒形現象了。