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

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

（1.浙江工業(yè)大學(xué)計算機(jī)學(xué)院,浙江杭州310012；2.浙江大學(xué)CAD&CG國家重點(diǎn)實(shí)驗(yàn)室,浙江杭州310058）

剪紙是我國寶貴的非物質(zhì)文化遺產(chǎn),具有“圓如秋月、尖如麥芒、方如青磚、缺如鋸齒、線如胡須”等鮮明特點(diǎn),是一種廣泛流傳的民間藝術(shù)。剪紙?jiān)诜课菅b飾、民俗禮葬、藝術(shù)收藏等方面具有舉足輕重的地位,使它躋身于中國國務(wù)院和聯(lián)合國教科文組織批準(zhǔn)的《人類非物質(zhì)文化遺產(chǎn)代表名錄》。

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

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

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

1 相關(guān)工作

1.1 基于紋樣的交互式剪紙?jiān)O(shè)計

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

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

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

1.2 計算機(jī)自動剪紙生成方法

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

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

2 本文方法

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

2.1 建立區(qū)域連接圖

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

2.1.1 圖像分割

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

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

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

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

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

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

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

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

2.1.2 生成連接圖

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

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

2.2 建立優(yōu)化目標(biāo)函數(shù)

一幅剪紙只有2種顏色,而輸入圖像包含成千上萬種顏色。即使用每個分割區(qū)域的平均顏色來代替該區(qū)域的所有顏色,圖像的顏色也遠(yuǎn)多于2種。而要將一幅圖像轉(zhuǎn)化為一幅剪紙,實(shí)際上是確定每個分割區(qū)域是取前景色還是背景色。其中,前景色為紅色,是保留下來的紙張顏色,而背景色是白色,是鏤空后的顏色?；谏鲜鰠^(qū)域連接圖G=(V;E),本文引入一個優(yōu)化目標(biāo)函數(shù),該函數(shù)由3個約束條件加權(quán)組成,分別對頂點(diǎn)約束、邊界約束和連通性約束進(jìn)行數(shù)學(xué)建模。

2.2.1 頂點(diǎn)約束方程

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

于是,目標(biāo)剪紙圖形與輸入圖像之間的頂點(diǎn)約束函數(shù)可以用所有區(qū)域的顏色差來定義：

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

2.2.2 邊界約束方程

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

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

2.2.3 連通性約束方程

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

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

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

2.3 求解目標(biāo)函數(shù)

目標(biāo)函數(shù)為所有約束項(xiàng)的加權(quán)和,即

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

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

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

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

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

2.4 后處理和用戶交互

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

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

2.4.1 連通性后處理

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

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

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

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

2.4.2 用戶交互

本文剪紙自動生成方法的目的是輔助業(yè)余剪紙愛好者進(jìn)行設(shè)計,而非取代傳統(tǒng)的手工剪紙藝術(shù)。當(dāng)用戶對自動生成的剪紙圖樣不滿意或有一些特殊要求時,允許用戶進(jìn)行手動修改。自動生成和用戶交互工具相結(jié)合,可大大提高業(yè)余甚至專業(yè)剪紙愛好者使用本系統(tǒng)進(jìn)行剪紙?jiān)O(shè)計的效率。為此,還開發(fā)了區(qū)域?qū)傩灾付ê图y樣添加2種用戶交互工具。

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

初始化階段：將區(qū)域初始化為用戶需要的屬性,即鏤空或保留，對區(qū)域?qū)傩韵嗤?取相同的隨機(jī)二進(jìn)制值;

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

需要指出的是,用圖切割方法求解目標(biāo)函數(shù),難以通過算法的調(diào)整來支持用戶交互指定的預(yù)處理。

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

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

3 實(shí)驗(yàn)結(jié)果與比較

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

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

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

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

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

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

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

4 結(jié) 論

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

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

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