基于圖像的二維剪紙自動生成方法

陳佳舟，王宇航，Amal Ahmed Hasan Mohammed，黃可妤，盧周揚，彭群生

（1.浙江工業大學計算機學院,浙江杭州310012；2.浙江大學CAD&CG國家重點實驗室,浙江杭州310058）

剪紙是我國寶貴的非物質文化遺產,具有“圓如秋月、尖如麥芒、方如青磚、缺如鋸齒、線如胡須”等鮮明特點,是一種廣泛流傳的民間藝術。剪紙在房屋裝飾、民俗禮葬、藝術收藏等方面具有舉足輕重的地位,使它躋身于中國國務院和聯合國教科文組織批準的《人類非物質文化遺產代表名錄》。

剪紙的設計極具挑戰性,不僅要求畫面簡潔、直觀,還需要表達特定的文化內涵,并且整個剪紙必須整體連通。這些設計要求對于業余剪紙愛好者來說無疑是巨大的挑戰,也給剪紙的藝術傳承和民間傳播帶來了很大困難。因此,我國的民間剪紙被列為中國民間十大文化遺產搶救工程之一。

本文旨在研究計算機輔助剪紙設計,從而降低人工剪紙設計的難度,滿足剪紙的連通性和藝術特點要求。現有的計算機輔助剪紙設計方法主要分為基于紋樣的交互設計和計算機自動生成兩種。基于紋樣的交互設計方法依賴大量的用戶交互,對用戶的要求比較高,難以推廣。而現有的計算機自動生成方法不是局限于特點題材(比如肖像),就是缺乏對連通性的保證和對剪紙效果的保證。

本文提出了一種基于圖像的二維剪紙生成方法,能夠將任意數碼照片自動轉化為剪紙圖形。首先利用圖像分割方法建立區域連接圖;其次,基于該連接圖對顏色、邊界對比度和區域連通性進行數學建模,并獲得優化目標函數;最后,通過模擬退火算法求解目標方程,自動生成保持圖像內容的剪紙圖形。此外,還開發了連通性后處理和區域指定等用戶交互工具,允許用戶干預剪紙圖形的自動生成。本文方法生成的剪紙圖形畫面簡潔、整體連通,在降低剪紙設計難度的同時還可滿足個性化的設計需求。

1 相關工作

1.1 基于紋樣的交互式剪紙設計

受紙張的空間和顏色限制,剪紙往往需要運用最為簡潔的線條符號來刻畫復雜的形象,久而久之便形成了一套確定的符號化紋樣,比如，動物五官結構,一般都采用特定的紋樣。剪紙紋樣是藝術家抒發情感、表達寓意的重要途徑,也是剪紙藝術區別于其他民間藝術形式的主要特征。剪紙紋樣可以分為形體結構紋樣、特征紋樣以及裝飾紋樣等。目前的研究工作主要集中在剪紙紋樣的識別和基于紋樣的交互式剪紙圖形設計兩方面。

由于紋樣是民間剪紙藝術在代代相傳中保留下來的表達特定寓意的符號化語言,從現有的剪紙作品中自動識別紋樣能夠幫助我們建立剪紙紋樣庫,從而輔助剪紙的設計。紋樣特征是識別剪紙紋樣的關鍵,通過深入研究目前現有的圖像特征提取方法[1],有助于自動識別剪紙紋樣。張顯全等[2]提出了一種基于紋樣庫的計算機剪紙系統設計。該紋樣庫包含許多不同特征的紋樣,并且通過參數變換可以適應不同的要求,即紋樣可按照用戶的需要進行長短、粗細、角度以及彎曲程度的變化[3],由于紋樣是手動設計的,因此其連通性需要用戶自己來保證。李岳等[4]對裝飾紋樣進行了深入研究,提出了一些復合紋樣的生成方法，如擴大對稱的紋樣設計,漸變的路徑裝飾等。張顯全等[5]利用小波分析理論對剪紙圖像中的紋理進行識別,小波變換具有多尺度分解特點,更符合人類的視覺機制,與計算機視覺過程相似,能夠在不同尺度上描述圖像的變化特征。

雖然紋樣的構造較為固定,但在不同的剪紙藝術家手上卻往往各有特點。為了形成各種紋樣,僅有一些基本的紋樣是不夠的,需要在已有紋樣的基礎上,通過計算機輔助設計思想生成大量紋樣。劉濤等[6]對剪紙圖案風格進行了研究,提出利用遺傳算法對剪紙圖案進行設計的理念。涂傳朋等[7]研究了計算機生成剪紙風格流水動畫形式,提出一種生成剪紙風格流水動畫的方法：首先對手工剪紙紋樣進行分類處理,如平穩流水波紋、浪花紋等,并且構造出靜態結構,然后，根據不同類型的水紋構建不一樣的動態控制機制。

1.2 計算機自動剪紙生成方法

文獻[8]提出了一種基于閾值的自動生成方法,其大致思路為：首先，尋找一個合適的閾值,將整幅圖像二值化,然后，采用不連通區域的連接算法。使用Dijkstra算法連接不連通的鄰近區域，將不連通區域連接起來。文獻[9]提出了藝術閾值處理的相關技術，結合圖像信息來處理圖像閾值,對圖像分塊,對每個塊設定閾值并進行二值化操作，使用藝術閾值算法對圖像進行優化,并通過調整參數得到不同風格的藝術形象。

文獻[10]提出了一種人物肖像剪紙生成方法。優秀的肖像類剪紙作品需要捕獲特殊的人物特征。基于此,MENG等[10]提出以自底向上和自頂向下為線索進行取值。在自底向上階段,從輸入圖像中提取包含臉部器官的圖像區域,用動態閾值的方法將這些圖像區域二值化。在自頂向下階段,則使用藝術家預先描繪的模板對相關圖像區域進行匹配。最后對各個區域進行And-Or圖連接,從而得到最終的剪紙效果。基于模塊的方法能夠達到滿意的效果,但只適用于人物肖像,并且基于模板方法，需要預先建庫,工作量較大。

2 本文方法

為了緩解交互式剪紙圖形設計的交互困難,也為了克服基于模板的人物肖像剪紙自動生成方法的局限性[8],提出了一種新的基于圖像的二維剪紙生成方法,能夠將一幅彩色圖像自動轉換為一幅整體連通的剪紙圖形。首先利用圖像分割方法建立區域連接圖(2.1小節);接著,基于該連接圖，對顏色、邊界對比度和區域連通性等進行建模,并建立優化目標函數(2.2小節);然后,通過求解該目標函數獲得每個區域的鏤空屬性(2.3小節);最后,自動生成剪紙圖形,并允許用戶進行局部特征修改和紋樣添加等后處理和交互操作(2.4小節)。該方法能夠自動生成相互連通的剪紙圖形,圖形線條光順度可控,并能保持原圖中大部分物體的形狀特征。

2.1 建立區域連接圖

現有基于閾值的方法能夠將輸入圖像劃分為鏤空和保留兩部分,從而獲得一個粗糙的剪紙圖形。然而,剪紙設計需要綜合考慮物體的明暗、邊緣的強弱和畫面整體的連通等因素,基于閾值的方法，僅根據像素的明暗來確定像素的鏤空屬性，并不符合剪紙的藝術特色。另一方面,由于本文方法不限定所處理的輸入圖像內容,因此無法與基于模板的方法[10]一樣，從輸入圖像中直接檢測需要轉化為剪紙形狀的物體。為此,首先將圖像空間分割為顏色相近的許多子區域,再將這些子區域按照空間位置關系建立區域連接圖,為尋找同時解決區域明暗、邊界強弱和整體連通等多種藝術要求的方案提供條件。

2.1.1 圖像分割

能夠將彩色圖像分割為多個子區域的方法不勝枚舉,除了已經提到的閾值方法外,常用的還有分水嶺分割方法、金字塔分割方法、圖切割（graph cut）方法、K-means分割方法、Mean-shift分割方法等。分水嶺分割算法可以通過閾值的方法自動選擇種子點,但所產生的分割結果過于粗糙,無法滿足本文建立區域連接圖的要求,如圖1(b)所示。金字塔分割是一種形態學分割方法,筆者用OpenCV中的cvPyrSeg-mentation函數進行嘗試,分割結果中含有很多面積很小的區域,且區域邊界鋸齒嚴重,如圖1(c)所示。K-means分割是一種基于聚類分析的方法,其結果和金字塔分割方法類似,如圖1(d)所示。需要指出的是,圖1(c)和(d)的結果,都是預先將輸入圖像進行一定的高斯模糊后完成的,鋸齒邊界和小面積區域依然難以去除。

圖1 不同圖像分割方法的比較Fig.1 Comparison of different image segmentation methods

基于計算機視覺的Mean-shift分割方法,通過迭代偏移局部均值,達到任意維空間數據的聚類效果,計算量較小,收斂速度快,不需要用戶通過交互指定,在圖像分割、平滑和視頻目標跟蹤等領域具有廣泛應用。筆者對該分割方法進行了嘗試，結果如圖1(e)所示，可以看出,產生的區域大小合適,邊界鋸齒不嚴重。

本文采用Mean-shift分割方法對圖像做聚類分析,利用位置-顏色空間向量v=(αx,αy,R,G,B)完成初始樣本的構建,該5維向量表示p=(x,y)位置上的像素顏色R,G,B。由此,Mean-shift分割方法可定義為一個搜索中心點位置的迭代過程：

式（1）的作用就是在每次迭代過程中對所有符合‖v i-uk‖≤δ這一局部鄰域條件的初始樣本求平均值,k代表目前的迭代次數,uk代表迭代次數為k時的均值位置,nk代表在該局部鄰域范圍內初始樣本的個數。因此,局部鄰域中心點位置隨初始樣本的變化不斷移動,直到該中心位置幾乎不再改變，迭代過程結束。另外,Mean-shift分割方法以每個初始樣本vi為起點（即u0=vi）,分別進行迭代，迭代過程結束后,將距離中心位置較近的鄰域劃分為同一個子區域,計算每個子區域的平均顏色,并將該子區域的所有像素都設置成平均顏色，進而得到分割后的圖像,實現過程參見文獻[11]。

Mean-Shift分割方法依賴于參數調節。其中,參數δ主要控制分割子區域的大小,分割區域的面積隨δ的增大而增加,而分割區域的數量隨δ的增大而減少,δ是本文方法的調節參數之一。為避免分割后產生面積過小的區域,將該算法的最小區域面積參數設為 wh,其中，w表示圖像區域的長,h表示圖像區域的寬。參數α主要控制位置空間和顏色空間之間的尺度比。本文將該參數值設定為自適應值255/ wh。

雖然Mean-shift分割能得到封閉的區域,但其邊界往往帶有鋸齒,與剪紙藝術追求的簡潔畫面不符,見圖1(e)。為此,提出一種基于局部統計的濾波方法,以消除鋸齒效應。對于像素p(其所屬區域編號為λp),統計該像素局部鄰域內全體像素的所屬區域編號{λq|‖p-q‖≤s},并用出現次數最多的區域編號λp代替當前像素p的區域編號。其中,參數s是代表濾波范圍的整數,用于控制邊界的光滑程度,s越大,邊界線條越光滑。如圖1(f)所示,該統計濾波方法不僅可有效解決邊界鋸齒問題,而且不會破壞圖像的整體分割結果。

需要指出的是,去除邊界鋸齒的傳統解決方法是：首先，矢量化邊界線條（一般表示為多邊形）,接著，對線條進行分段光順處理,最后，用原有的編號填充每個區域。這類方法不僅無法并行計算，效率低,而且穩定性較差,分割產生的鋸齒邊界容易矢量化，導致失敗。而本文基于統計的濾波方法,可以并行處理區域編號濾波,能夠有效去除復雜的鋸齒,只需要一個簡單的4-鄰域判斷即可獲得邊界像素,從而避免進行復雜的邊界像素矢量化和區域填充。

2.1.2 生成連接圖

有了上述圖像分割,基于圖像的剪紙生成任務就不需要逐個像素地判定應鏤空還是保留,而只要計算每個分割區域的鏤空屬性,即是否進行整體的鏤空處理。計算時不僅需要考慮每個區域的顏色、面積等屬性,而且需要考慮區域之間的取值關系。如相鄰區域的鏤空屬性不同,之間的邊界會得到保留;如果相鄰區域的鏤空屬性相同,之間的邊界會消失。因為分割區域之間的鏤空屬性存在相互影響,為此，用一個連接關系圖對其建模,將其視作一個整體,建立優化目標函數,全局求解每個區域的鏤空屬性分類。

本文將分割區域視作頂點V={vi},相鄰區域之間的邊界視作它們的邊E={eij},由此構建一個連接關系圖G=(V;E)。計算每個頂點的區域面積、平均顏色、平均位置等屬性。其中,區域面積Ai是指該區域所包含的像素點個數,平均顏色ci是指像素顏色的平均值,平均位置pi是指像素點位置的平均值。對于每條邊界,也可以計算長度和強度等屬性。其中,長度li,j是指該邊界所經過的像素點個數,強度si,j是指這些像素點梯度的平均值,用以計算該邊界的視覺顯著性。本文用Sobel算子計算梯度大小。

2.2 建立優化目標函數

一幅剪紙只有2種顏色,而輸入圖像包含成千上萬種顏色。即使用每個分割區域的平均顏色來代替該區域的所有顏色,圖像的顏色也遠多于2種。而要將一幅圖像轉化為一幅剪紙,實際上是確定每個分割區域是取前景色還是背景色。其中,前景色為紅色,是保留下來的紙張顏色,而背景色是白色,是鏤空后的顏色。基于上述區域連接圖G=(V;E),本文引入一個優化目標函數,該函數由3個約束條件加權組成,分別對頂點約束、邊界約束和連通性約束進行數學建模。

2.2.1 頂點約束方程

剪紙是一種鏤空的藝術,鏤空的區域由于透光更為明亮。為了使生成的剪紙圖形盡可能地反映輸入圖像的內容,剪紙中的鏤空區域應該盡量與輸入圖像中的明亮區域對應,非鏤空區域則與輸入圖像中的灰暗區域對應。本文將鏤空區域的顏色視作白色,非鏤空區域的顏色視作黑色,由此定義它們與輸入圖像中相應分割區域的顏色差：

于是,目標剪紙圖形與輸入圖像之間的頂點約束函數可以用所有區域的顏色差來定義：

其中,Ai為分割區域的面積,W和H分別為輸入圖像的長和寬。

2.2.2 邊界約束方程

塊之間的邊界包含了圖像的輪廓和邊緣。為了保留這些邊緣的可見性,顏色差別較大的兩個相鄰區域應取相反的二進制值,即一個鏤空、一個保留，顏色差別較小的兩個相鄰區域則可以取相同的二進制值,即同時鏤空或保留。本文以此為原則,對取相同二進制值和取不同二進制值的相鄰區域分別計算懲罰函數,即Calike和Copp。對于任意一對相鄰區域(i,j),如果它們的二進制取值相同(bi=bj),則(i,j)∈Ealike, 反之則屬于Eopp。Calike和 Copp的定義如下：

其中,對二進制取值相同的相鄰區域Ealike用平均顏色差的加權平均來計算Calike,而對二進制取值不同的相鄰區域Eopp,則用1減去平均顏色差的加權平均來計算Copp。需要指出的是,該公式與文獻[12]的主要差別在于邊界強度si,j的使用。注意到有一些邊界雖然很長,但邊界兩側的區域在邊界附近顏色過渡很光滑,即si,j值較小，這些邊界即使兩側區域的整體平均顏色有一定差異,但在視覺上邊界兩側的顏色差異較小。因此,該邊界對應的懲罰因子應適當減小,本文通過引入si,j的權重因子來實現。

2.2.3 連通性約束方程

我國早期的民間剪紙主要用于窗花裝飾,出于張貼的便利,要求剪紙聯通為一個整體。經過上百年的傳承,形成了中國剪紙有別于其他任何民間藝術的構型特色。傳統的二值化方法雖然能夠將輸入圖像轉化為局部區域鏤空或保留的剪刻效果,但難以保證剪紙的連通性。雖然可以用后處理方法將不連通的區域強行連接起來,如文獻[8]采用的Dijkstra算法,但連接部分計算機處理痕跡明顯,且難以保證連接的牢固。而民間剪紙藝術家在設計剪紙時通常已考慮了剪紙的整體連通性,僅需在剪刻過程中做簡單的局部調整即可。本文將連通性約束加入目標函數,試圖一次性生成具有良好連通性的剪紙圖形。

為了達到約束剪紙連通性的目的,將生成剪紙中的不連通的前景（保留）區域數量Nc用于連通性約束的計算：

其中,N為整幅圖像分割得到的區域總數量。由于不連通前景區域數量一般遠少于區域總量,因此將N取平方根做分母。

2.3 求解目標函數

目標函數為所有約束項的加權和,即

為此,需要尋找 N個二進制值,即{b1,b2,…,bN},bi∈{0,1},使該目標函數 Ctotal最小化。最為簡單的方法是窮舉所有的可能二進制值組合,計算在這些組合下的目標函數值,經比較得到最小值。然而,這樣的組合有2N種,窮舉所有的組合顯然不合適，計算開銷太大,處理復雜圖像時可能需要數小時。

為解決目標函數求解問題,本文用近似求解方法取代窮舉法。能用于這一類目標函數的近似求解方法很多,考慮本文的頂點約束項和邊界約束項等都是建立在連接關系圖上的,故選擇基于圖的近似求解方法，主要有圖切割法[13](graph cuts)、置信度傳播算法[14](belief propagation)和模擬退火法[15]。

圖切割法的能量函數主要由數據項和光滑項組成,如用本文中的頂點約束項和邊界約束項來代替，然而，文獻[16]發現，將圖像分割問題轉換為圖的最大流/最小流問題所產生的區域分割往往過于粗糙,無法保留大部分邊界輪廓特征；如目標函數采用置信度傳播算法的無向有環版本,即帶圈置信度傳播算法（loopy belief propagation）（一種機器學習方法）求解，計算效率又較低,且穩定性和收斂性難以保證。故本文選擇隨機算法——模擬退火法,雖然也不能保證找到全局的最優解,但可以較快地找到問題的近似最優解,且具有良好的穩定性和收斂性，在參數設置得當的情況下,模擬退火法的搜索效率較窮舉法高很多。

模擬退火法首先用隨機值{b1,b2,…,bN}作為初始化狀態值,并計算在當前狀態下的目標函數值；接著,隨機選擇一個區域bi,更改狀態值,并計算新的目標函數值，如果新目標函數值較原目標函數值小,就接受該狀態值的改變，如果新目標函數值增加,就以一定的概率pk接受該狀態值的改變。其中,pk=p0βn,p0為接受概率的初始值（本文取0.5）,β為接受概率的下降速度（本文取0.9）,而n是在目標函數值增加的情況下狀態值改變被接受的次數。不斷迭代上述過程,直至迭代達到一定次數（本文取1 000次）,或者連續多次迭代都無法接受狀態值的改變（本文取30次）,或者p k的值小于一個很小的閾值（本文取0.001）。

在模擬退火過程中,以一定的概率接受局部非最優解的目的是防止陷入局部極小值點,從而得到全局最優解。由于接受概率每使用一次都會以α的比例下降,所以模擬退火法的收斂性是能夠保證的，但每次迭代都需要計算目標函數值。為了降低計算量,本文僅計算狀態值改變產生的目標函數值的變化量,即ΔCtotal,如果ΔCtotal＜0,說明應該接受狀態值改變;如果ΔCtotal≥0,則以概率p k接受這一改變。由于ΔCtotal的計算僅涉及當前區域、相鄰區域和與其連通的區域,因此，計算量較重新計算ΔCtotal小很多。

2.4 后處理和用戶交互

上述目標函數求解結束后,即可獲得保留了大部分輪廓特征的剪紙效果,如圖2和圖3所示。然而,這些剪紙效果與民間藝術家創作的紙質剪紙相比,在整體連通性和裝飾紋樣方面仍有差距。為此,本文開發了連通性后處理和針對紋樣的用戶交互工具,使用戶能夠輕松地生成符合剪紙藝術特點的剪紙圖形。

圖2 部分紋樣庫示意Fig.2 Some patterns in our library

2.4.1 連通性后處理

由于目標函數將整體連通性視作軟約束而非硬約束,生成的剪紙雖然不連通區域數量較少,但無法保證僅有一個不連通區域。通過增大式(6)中的連通性約束系數wconnect，可減少不連通區域數量,但增大過多會導致頂點約束和邊界約束失效,使剪紙效果失真。

為保證剪紙的整體連通性，首先,根據區域邊界的強度si,j，將邊界線條劃分為物體輪廓線和非物體輪廓線，如圖3(e)所示,顏色越紅的邊界強度越大,越有可能被劃分為物體輪廓線。檢查每條物體輪廓線能否連接不連通區域，如能,用寬度為5的紅色線條繪制該物體輪廓線,將不連通區域連接起來,如圖3(f)所示。需要指出的是,當強度si,j難以有效計算物體輪廓線時（如當物體內部的紋理邊界強度很大時）,需要手動進行前景分割[13]，以獲取更準確的物體輪廓線,如圖5(e)所示。

圖3 天鵝圖像的自動剪紙生成結果Fig.3 Paper-cut results of the swan image

物體輪廓線并不能連接所有不連通的區域,如圖3(f)中中央的一塊前景區域。為此,還采用了Dijkstra算法[17],以最短路徑連通算法連接相鄰不連通區域。首先對圖像進行八連通掃描線種子填充標記[18],對同一區域像素點取相同標簽；標記完像素點后,以圖像像素點為結點,以圖像像素點的像素值為每個結點的初始距離,相鄰結點間的距離為2個結點像素值之和,為改變連通效果設定閾值,當距離大于閾值時，規定該像素點距離為無窮大。基于上述假設,求出圖像上一點到某點的距離。從某個像素點z出發,將圖像像素點分成兩類,a類為已求得的到該像素點的距離,b類為未求得的,從b類中尋找距離最小的點作為更新點p,從p出發，更新距離,并且將p歸為a類,重復上述操作,直到b類為空集為止,這樣可以求出z到其余像素點的距離。將2個圖像塊之間像素點間距離最短的作為這2個塊間的距離,利用主元分析,得到此路徑的主方向,并對路徑進行填充,以改善效果。

2.4.2 用戶交互

本文剪紙自動生成方法的目的是輔助業余剪紙愛好者進行設計,而非取代傳統的手工剪紙藝術。當用戶對自動生成的剪紙圖樣不滿意或有一些特殊要求時,允許用戶進行手動修改。自動生成和用戶交互工具相結合,可大大提高業余甚至專業剪紙愛好者使用本系統進行剪紙設計的效率。為此,還開發了區域屬性指定和紋樣添加2種用戶交互工具。

目標函數為一組約束方程,當對某一局部進行調整(將某一區域指定為鏤空、保留或與另一個區域相同)時，需進行預處理和后處理。預處理，指在目標函數求解前已指定的,會影響其他區域的屬性;后處理，指在目標函數求解后指定的,僅改變指定區域的屬性,不會影響其他區域。后處理非常簡單,而預處理則需要適當改進模擬退火求解算法，步驟如下：

初始化階段：將區域初始化為用戶需要的屬性,即鏤空或保留，對區域屬性相同的,取相同的隨機二進制值;

算法迭代階段：當隨機選擇到指定的區域時,算法不會改變其鏤空或保留屬性,或者在改變當前區域的同時也改變同值的其他區域。

需要指出的是,用圖切割方法求解目標函數,難以通過算法的調整來支持用戶交互指定的預處理。

紋樣是中國民間剪紙的重要特色,主要由剪紙設計者憑其所要表達的寓意而定,有時與圖像內容并不相關，因此,根據圖像內容自動生成剪紙紋樣缺乏合理性,現有的基于紋樣的剪紙方法大多以手動交互為主。本文開發了相應的紋樣設計交互工具,以彌補自動生成方法難以生成紋樣的不足。首先,建立一個剪紙紋樣庫,包括諸如月牙紋、柳葉紋、花瓣紋、銅錢紋和鋸齒紋等最為常見的紋樣,如圖2所示。

此外,還為每個紋樣設計了不同的變化模板,用戶可以輕易編輯，如添加花瓣紋的花瓣數量、增加鋸齒紋的鋸齒數量等。當用戶將紋樣添加到自動生成的剪紙中時,本文方法會根據背景的鏤空屬性自動判斷該紋樣是鏤空還是保留狀態,當難以簡單判定時,也會對出現的不連通區域進行提示。

3 實驗結果與比較

圖3展示了從輸入圖像到最終剪紙結果的主要流程，其中,(b)為Mean-shift圖像分割后再使用邊界光順的結果,可以看到其邊界較為光滑;(c)為分割后每個區域的平均顏色;(d)為采用模擬退火法求解目標函數式(6)的結果,其中不連通區域有3塊；(e)展示了邊界線條的強度,越紅表示強度越大,是物體輪廓線,越藍表示強度越小,不是物體輪廓線;(f)為用物體輪廓線將不連通區域進行連接的結果,可以看到，剪紙圖形的不連通區域降至2塊；(g)為采用Dijkstra連接算法,將剩下的2塊不連通區域連接為一個整體,使最終結果不僅整體連通,且保持了輸入圖像的主要輪廓特征。

圖4為本文方法對長頸鹿圖像的處理結果，(b)為分割區域的平均顏色圖，(c)為求解目標函數后得到的剪紙效果，(d)為用戶通過本文提供的紋樣交互工具為長頸鹿添加了鋸齒紋樣后的效果。

圖4 長頸鹿圖像的剪紙生成效果Fig.4 Paper-cut results of the giraffe image

圖5 展示了本文方法對建筑環境圖像的處理結果，(b)為分割邊界；(c)為分割區域的平均顏色圖；(d)為通過全自動目標函數模擬退火法求解得到的剪紙效果,該結果尚有少量不連通的區域(綠色圓圈處)；(e)為經連通性后處理,即Dijkstra算法處理后的圖,保證了剪紙的整體連通；(f)為利用紋樣庫中的紋樣模板,手動添加云朵紋樣和流水紋樣后的效果。

圖6 展示了本文對斑馬圖像的處理結果。其中,(b)和(c)分別為Mean-shift產生的分割邊界和分割區域平均顏色；(d)為求解沒有使用連通性約束項的目標函數的結果,且沒有添加物體輪廓線,該結果存在25塊不連通區域；(e)為添加物體輪廓線、去除面積很小的不連通區域后的結果,雖然其目標函數依然沒有使用連通性約束,但其連通性比(d)好很多,尤其在物體輪廓附近;(f)為既有輪廓線又有連通性約束的結果，內部不連通區域較（e）少。

為展示連通性約束項的影響,將有連通性約束和沒有連通性約束的結果相減，即圖(f)減去圖(e)，得到圖(g)。圖(g)中的紅色區域表明，連通性約束雖然產生了與頂點約束相違背的鏤空屬性賦值，但緩解了區域連通性的問題。圖6(h)為經Dijkstra算法后處理(藍色圓圈內)和用戶區域指定交互(斑馬的鼻子處)的最終剪紙結果,該結果已經完全實現了整體連通,且基本保留了斑馬的外觀特征。

利用GPU進行加速,分割區域的光順、區域邊界的提取、Sobel邊界強度的計算均基于GLSL腳本實現,采用NVIDIA GeForce 9800 GT顯卡僅需0.03～0.08 s。在CPU上,時間主要花在Mean-shift分割和模擬退火法計算上，其中,Mean-shift分割的時間依賴于圖像的大小,一般需0.1～3.2 s，模擬退火法的快慢主要由區域連接圖的規模決定,一般需0.3～2.0 s，上述時間均為 Intel? CoreTM2 DuoE 6550@2.33GHz臺式電腦上的統計數據。

4 結 論

提出了一種基于圖像的二維剪紙生成方法,能夠將任意數碼照片自動轉化為剪紙圖形。該方法首先利用圖像分割方法建立區域連接圖;接著,基于該連接圖，對顏色、邊界對比度和區域連通性進行數學建模,并獲得優化目標函數;最后,通過模擬退火算法求解目標函數,自動生成保持圖像內容的剪紙圖形。同時,還提供了諸如連通性后處理和區域指定等用戶交互工具,用戶可便捷地在自動生成的剪紙圖形中加入個性化內容。實驗表明,本文方法生成的剪紙，畫面簡潔、整體連通,既提高了剪紙的設計效率,又滿足了個性化的設計需求,有利于推動和促進我國民間剪紙藝術的傳承與傳播。

本文方法依賴于初始的圖像分割結果,對分割失敗的圖像往往剪紙效果較差。因此,將來的工作之一是研究如何將剪紙的各種約束加入到圖像分割環節,或許不需要分割就能得到剪紙結果。此外,不同地區不同愛好者的剪紙風格千差萬別,如果能收集不同風格的剪紙,將來或許可以研究數據驅動的剪紙自動生成方法,使生成的剪紙帶有鮮明的風格特征。

圖6 斑馬圖像的剪紙效果對比Fig.6 Comparison of the Zebra paper cutting effect