張開(kāi)翼 程魯豫 汪云海
(山東大學(xué) 青島 266237)
拼貼畫(huà)(Collage)是一種經(jīng)典的視覺(jué)藝術(shù)形式,通過(guò)將圖片、文字、剪報(bào)、幾何圖形等元素拼接到畫(huà)布上,從而產(chǎn)生具有美感的藝術(shù)品。目前,較為流行的表現(xiàn)形式有 3 種:(1)圖片馬賽克,通過(guò)拼接圖片或彩色多邊形來(lái)產(chǎn)生不同的結(jié)果;(2)詞云(Word Cloud)[1],作為一種強(qiáng)大的文本可視化工具,通過(guò)拼接不同大小(代表權(quán)重)的單詞來(lái)產(chǎn)生美感;(3)傳統(tǒng)拼貼畫(huà),通過(guò)規(guī)則和緊密地分布主題較為統(tǒng)一的圖形來(lái)產(chǎn)生美感。拼貼畫(huà)強(qiáng)大的藝術(shù)表現(xiàn)力具有美觀(guān)與信息傳遞的雙重優(yōu)勢(shì),能使受眾感受到美學(xué)的同時(shí)獲取足夠的信息。但由于其組合、角度、位置的多樣性,輸入特征的復(fù)雜性,以及設(shè)計(jì)目標(biāo)的差異性,使人工設(shè)計(jì)過(guò)程復(fù)雜、設(shè)計(jì)步驟繁瑣。設(shè)計(jì)師需要反復(fù)地試錯(cuò)多種可能的拼接方式,才能制作出一個(gè)相對(duì)優(yōu)秀的作品,這個(gè)過(guò)程需要耗費(fèi)大量的時(shí)間和精力。即便如此,人工制作的拼貼畫(huà)也很難達(dá)到最優(yōu)的效果。
拼貼畫(huà)的生成屬于可視化與圖形學(xué)的交叉領(lǐng)域,其領(lǐng)域?qū)W者就拼貼畫(huà)問(wèn)題提出不同思路。圖形學(xué)領(lǐng)域?qū)W者將該問(wèn)題視作一個(gè)打包問(wèn)題:先利用形狀描述符[2]對(duì)輸入的圖形進(jìn)行相似度分析,然后將全局或局部輪廓相似的圖形進(jìn)行拼接;抑或是使用輪廓細(xì)分與匹配[3]的方法,將目標(biāo)輪廓按一定規(guī)則細(xì)分成格子后,將與格子相似的圖形填充到格子中。可視化領(lǐng)域?qū)W者側(cè)重如何傳遞信息,即如何將輸入數(shù)據(jù)中包含的信息與拼貼畫(huà)元素進(jìn)行映射:將輸入的圖形抽象為特征向量[4],從而與最終可視化的位置進(jìn)行映射,更好地展現(xiàn)圖形特征數(shù)據(jù);抑或是在可視化文本中[1],將帶有詞頻的文字視作圖形輸入,通過(guò)算法將填充文字與目標(biāo)輪廓進(jìn)行映射,從而生成信息量與美觀(guān)度俱佳的結(jié)果。
為更有邏輯地梳理不同學(xué)者在拼貼畫(huà)自動(dòng)生成領(lǐng)域提出的思路,本文將其粗略地分為自頂向下的生成技術(shù)和自底向上的生成技術(shù),并按兩大類(lèi)四小類(lèi)的分類(lèi)方式,從中具體介紹具有代表性或開(kāi)創(chuàng)性的方法。旨在幫助相關(guān)研究人員快速了解本領(lǐng)域演進(jìn)過(guò)程與代表性工作。并將本文中提到的常見(jiàn)算法整理為表 1 方便查看與對(duì)比。
表1 拼貼畫(huà)生成算法結(jié)構(gòu)表Table 1 Collage auto generation algorithm structure table
如圖 1 所示為常見(jiàn)的 3 種拼貼畫(huà)形式,首先對(duì)拼貼畫(huà)自動(dòng)生成技術(shù)進(jìn)行形式化定義—— 拼貼畫(huà)生成的輸入集主要分為兩部分:
第一個(gè)輸入集為目標(biāo)外輪廓約束,一般分為兩種:一種為強(qiáng)外輪廓約束,如復(fù)雜圖形、照片等,填充時(shí)需要充分考慮外輪廓的約束,使填充圖形的邊緣盡可能貼合強(qiáng)外輪廓約束的邊緣,這屬于較復(fù)雜問(wèn)題;另一種約束為弱外輪廓約束,如矩形、圓形、簡(jiǎn)單字母等,填充時(shí)外輪廓的約束較小,只需考慮邊界問(wèn)題即可。
第二個(gè)輸入集為填充圖形,主要分成兩類(lèi)。第一類(lèi)是核心圖形,即填充中主要考慮的圖形。核心圖形分為規(guī)則圖形(如矩形、圓形等)和非規(guī)則圖形(如照片、文字等)。規(guī)則圖形主要通過(guò)其顏色、大小、密度等參數(shù)表示輸入的外輪廓,且圖形間的拼接相對(duì)容易,可簡(jiǎn)化拼接算法。非規(guī)則圖形的難度主要在于非規(guī)則圖形邊緣的匹配以及對(duì)接,該部分的搜索空間會(huì)急劇膨脹,因此如何有效減少搜索空間成為加速和優(yōu)化匹配速度的核心問(wèn)題。第二類(lèi)填充圖形為輔助圖形,此概念來(lái)自設(shè)計(jì)師作品中為了減少拼接時(shí)間、提高填充率的技巧,如圖 1(c)中小方片與小五邊形等。在人工拼接時(shí),依靠窮舉達(dá)到最佳結(jié)果是非常困難的,所以設(shè)計(jì)師會(huì)引入較小且不引人注目的輔助圖形,來(lái)提高最終結(jié)果的填充率和非最優(yōu)拼接結(jié)果的視覺(jué)效果。
圖1 常見(jiàn)的拼貼畫(huà)設(shè)計(jì)Fig.1 Common collage design
自頂向下的生成技術(shù)思路是從生成的目標(biāo)輪廓分析或是從填充圖形的整體分析,先確定填充圖形在輪廓的粗略位置,再小范圍地改動(dòng)圖形的細(xì)節(jié)、角度、位置以得到更優(yōu)的結(jié)果。
基于輪廓細(xì)分與匹配算法常由 3 個(gè)步驟構(gòu)成:首先對(duì)目標(biāo)輪廓進(jìn)行細(xì)分,將輪廓分成多個(gè)規(guī)則或不規(guī)則的單元格;然后給每個(gè)單元格匹配最合適的填充圖形;最后對(duì)每個(gè)單元格的填充圖形進(jìn)行調(diào)整以增強(qiáng)效果。
3.1.1 相關(guān)算法介紹
Finkelstein[6]在 1998 年提出 Image Mosaics技術(shù),其針對(duì)的問(wèn)題為:如何將用戶(hù)輸入的一組圖片拼接到另一張目標(biāo)圖片中,產(chǎn)生近距離看是一組圖片,遠(yuǎn)距離看是目標(biāo)圖片的效果。在算法上,首先將目標(biāo)圖片分割成規(guī)律的矩形,利用基于小波變換的圖形匹配算法[7]對(duì)每個(gè)矩形匹配最相似的輸入圖片;然后對(duì)矩形內(nèi)圖片的亮度、灰度值進(jìn)行調(diào)整,從而使結(jié)果更接近目標(biāo)圖片。但由于其在分割目標(biāo)圖片時(shí),將圖片僅簡(jiǎn)單地分割為規(guī)則的矩形,而未考慮圖片本身的特點(diǎn),故被分割圖片不能很好地呈現(xiàn)目標(biāo)圖片的輪廓。
Haeberli[8]引入 Voronoi 算法,將不規(guī)則圖形(如油畫(huà)的筆觸或多邊形)隨機(jī)地?cái)[放并填充至目標(biāo)區(qū)域,以達(dá)到轉(zhuǎn)換輸入圖片風(fēng)格的目的。其思路是將油畫(huà)的筆觸或者多邊形抽象成填充圖形,并在填充至目標(biāo)圖片過(guò)程中,先使用 Voronoi 算法細(xì)分目標(biāo)圖片,再將筆觸填充至網(wǎng)格內(nèi)。在這一過(guò)程中,為了使筆觸更接近真實(shí)油畫(huà)效果,Haeberli 引入根據(jù)輸入圖片計(jì)算梯度方向的方式來(lái)引導(dǎo)筆觸的填充方向,使其更接近手繪效果。但該方法忽略了原始圖片中物體的邊緣(如人物圖片的人物輪廓、物體圖片中不同物體的邊緣),沒(méi)有使填充圖形貼合或者表達(dá)原圖片中的輪廓,導(dǎo)致生成結(jié)果中的輪廓不清晰。而清晰的輪廓可以幫助用戶(hù)迅速感知圖片本體,所以該方法生成的結(jié)果辨識(shí)度不佳。
在 Haeberli 方法基礎(chǔ)上,Hausner[9]引入基于重心的泰森多邊形圖(Centroidal Voronoi Diagram,CVD)[10],其針對(duì)的目標(biāo)問(wèn)題為:使用多邊形填充目標(biāo)圖片,著重表現(xiàn)輸入圖片中的邊緣與輪廓,來(lái)增強(qiáng)結(jié)果的辨識(shí)度。傳統(tǒng)的CVD 圖使用歐式距離度量,通過(guò)多次迭代使全局歐式距離最小,導(dǎo)致計(jì)算出來(lái)的區(qū)塊趨近于六邊形。在 Hausner 的研究中,通過(guò)將度量修改為曼哈頓距離使最終區(qū)塊接近正方形,并用于填充。此外,也可以通過(guò)修改度量的方向來(lái)影響CVD 圖中格子的方向。為了高效地生成帶方向度量的 CVD 圖,該研究借鑒了 Hoff[11]提出的生成技術(shù)。并在 Hoff 生成技術(shù)的基礎(chǔ)上,將歐式距離替換成曼哈頓距離。為了提取原始圖片中的方向信息,Hausner 引入了方向場(chǎng),從原始圖片的輪廓中產(chǎn)生方向場(chǎng)來(lái)指導(dǎo)帶方向度量的 CVD圖的生成。結(jié)果顯示,作為填充圖形的小正方形可以很好地表達(dá)原始圖片中的邊緣,用戶(hù)可以非常迅速地辨認(rèn)僅由帶色彩的正方形組成的拼貼畫(huà)。該方法有足夠的創(chuàng)新性,產(chǎn)生了具有強(qiáng)大表現(xiàn)力的拼貼畫(huà)。但缺陷在于其構(gòu)成要素僅為正方形,很難表現(xiàn)更為復(fù)雜的圖片,這很大程度上限制了輸入圖形的類(lèi)型,普適性較差。
3.1.2 代表性算法介紹
Kim[3]提出一種基于最小化能量函數(shù)的生成技術(shù),與 Hausner 方法相比,更具有普適性:將填充圖形從簡(jiǎn)單的多邊形,擴(kuò)充到任意的輸入圖形,并填充到任意的目標(biāo)輪廓中。該算法屬于基于輪廓細(xì)分與匹配算法中較有代表性的算法,綜合了該線(xiàn)路上前人的研究結(jié)果。如借鑒Hausner[9]的思路,使用 CVD 圖來(lái)輔助拼接等,在此基礎(chǔ)上將問(wèn)題抽象成能量函數(shù)最優(yōu)化的過(guò)程,并結(jié)合多種優(yōu)化方式來(lái)加速生成。同時(shí),Kim 將輸入集的范圍擴(kuò)充到任意圖形,進(jìn)一步擴(kuò)大了算法的適用范圍。具體來(lái)說(shuō),能量化定義的優(yōu)勢(shì)就是可以通過(guò)增減或調(diào)整各能量項(xiàng)的權(quán)重使最終的結(jié)果呈現(xiàn)不同的風(fēng)格,其能量 E 定義為:
其中,能量 E 由各項(xiàng)的加權(quán)和構(gòu)成;顏色項(xiàng) Ec為圖形顏色與當(dāng)前位置目標(biāo)容器顏色不符的程度,wc為權(quán)重;間隙項(xiàng) EG為最終結(jié)果中空白區(qū)域的大小,wG為權(quán)重;重疊項(xiàng) Eo為最終結(jié)果中圖形之間的重疊程度,wo為權(quán)重;變形項(xiàng) ED為圖形過(guò)度變形的程度,wD為權(quán)重。
拼接時(shí),是在不對(duì)圖形進(jìn)行變形的前提下減少間隙和重疊,并使圖形的顏色與目標(biāo)容器位置的顏色保持一致,從而得到圖形的初步匹配結(jié)果。為使每次拼接操作后,更新的容器更便于下一次拼接。在每次拼接之前,借鑒 Hausner[9]的思路,按圖形的平均大小對(duì)容器構(gòu)建 CVD 圖,隨機(jī)選擇鄰居數(shù)量最少的位置,從而減少拼接后容器產(chǎn)生突出或不連通的問(wèn)題,便于后續(xù)的拼接。如圖 2 所示,構(gòu)建 CVD 鄰接圖后,圖中綠色點(diǎn)為被選中的位置,其僅有 2 個(gè)鄰居,拼貼在此位置對(duì)網(wǎng)格的影響最小。
圖2 使用 CVD 鄰接圖選擇拼接位置Fig.2 Use the CVD adjacency graph to select location
當(dāng)某一步無(wú)法找到合適的圖形去填充目標(biāo)容器時(shí),算法需要退回上一能量最小處。為減少這種回溯,Kim[3]借鑒 Russell[12]的思想,使用超前技術(shù),懲罰拼接之后無(wú)法放置圖形的小面積區(qū)域。
前文所述,在不對(duì)圖形變形的情況下進(jìn)行拼接,盡可能形成少重疊和少間隙填充的目標(biāo)容器的布局。但其中仍會(huì)出現(xiàn)很多空隙與重疊,導(dǎo)致生成結(jié)果并不美觀(guān)。為此,該研究借鑒了Kass[13]的思路,使各個(gè)圖形可以在保持原始形狀和最小化能量 E 之間平衡,通過(guò)微小的變形來(lái)取得更好的結(jié)果。在 CVD 圖的變形過(guò)程中,初始拼接得到的 CVD 結(jié)果,會(huì)造成較多的重疊與空隙。經(jīng)過(guò)優(yōu)化過(guò)程,重疊與空隙有一定程度的減少。最終,在各個(gè) CVD 格子變化程度較小的前提下,減少了格子之間的重疊與空隙,達(dá)到控制變形程度與提高結(jié)果填充率、降低重疊率之間的平衡。
因拼貼畫(huà)的生成過(guò)程中需要考慮多種因素,如美觀(guān)度、空隙等,所以基于最小化能量函數(shù)的生成技術(shù)在拼貼畫(huà)的生成中非常常見(jiàn)。其大致流程為將拼貼畫(huà)生成中多種因素抽象為能量函數(shù)中的參數(shù)項(xiàng),并賦予不同的權(quán)重以形成能量函數(shù),之后通過(guò)算法最小化該能量函數(shù)。Xu[14]提出的Calligraphic packing 算法亦是如此,其將拼貼畫(huà)生成的范圍擴(kuò)展到書(shū)法中,將任意文字作為拼貼畫(huà)生成算法的輸入,通過(guò)傾斜、扭曲等操作使文字填充到任意給定的圖形中,形成有美感的書(shū)法藝術(shù)作品。并在能量函數(shù)中引入風(fēng)格因素,算法可以根據(jù)不同的風(fēng)格調(diào)整能量函數(shù)中各項(xiàng)的參數(shù),生成不同風(fēng)格的輸出結(jié)果。
基于特征提取的方法一般分為 3 個(gè)步驟:首先對(duì)輸入圖形進(jìn)行特征提取;然后處理特征信息,并進(jìn)行初步布局;最后對(duì)布局進(jìn)行優(yōu)化調(diào)整,以減少重疊和間隙。
3.2.1 相關(guān)算法介紹
鑒于使用參數(shù)控制圖形的分布十分困難,Hurtut[15]提出一種基于結(jié)果統(tǒng)計(jì)的方式。其針對(duì)的問(wèn)題為:如何從用戶(hù)輸入的拼貼畫(huà)學(xué)習(xí)拼貼畫(huà)結(jié)構(gòu),并以該結(jié)構(gòu)為基礎(chǔ),生成更大范圍的拼貼畫(huà)結(jié)果。算法輸入一張包含多種圖形的拼貼畫(huà),系統(tǒng)使用基于圖形外觀(guān)的分類(lèi)算法將原始拼貼畫(huà)中的組成圖形根據(jù)外觀(guān)分類(lèi),并抽象出布局。系統(tǒng)通過(guò)構(gòu)建統(tǒng)計(jì)學(xué)習(xí)模型,從輸入的布局中學(xué)習(xí)同類(lèi)別內(nèi)部以及不同類(lèi)別之間的布局關(guān)系,從而在輸入布局的基礎(chǔ)上擴(kuò)充出更大范圍的結(jié)果。其缺點(diǎn)是不能像傳統(tǒng)拼貼畫(huà)的構(gòu)造過(guò)程,輸入足夠的圖形與輪廓生成指定的結(jié)果。并且,由于采用了基于統(tǒng)計(jì)的生成方式,因此無(wú)法控制生成結(jié)果的風(fēng)格,也很難根據(jù)不同的情景生成不同的結(jié)果,使用戶(hù)對(duì)結(jié)果的控制力大大下降。
在特征提取上,Maharik 等[16]將特征提取的對(duì)象轉(zhuǎn)移到輪廓,其針對(duì)的問(wèn)題為:如何將輸入的文本以流線(xiàn)的形式填充到目標(biāo)輪廓上。該系統(tǒng)首先在目標(biāo)輪廓中生成矢量場(chǎng);進(jìn)而生成符合代表目標(biāo)輪廓的流線(xiàn),并使其接近正常閱讀方式;再在生成的流線(xiàn)上填充文本,從而使文本既能夠較好地填充目標(biāo)輪廓,又具有較強(qiáng)的可讀性。其結(jié)果在文本對(duì)目標(biāo)輪廓的表現(xiàn)力以及文本的可讀性之間取得了較好的平衡。
基于特稱(chēng)提取的算法也被應(yīng)用在其他類(lèi)型的可視化中,如 Afzal 等[17]提出的 Typographic Maps,其針對(duì)的問(wèn)題為:如何將文本依照地理信息填充到地圖中。該系統(tǒng)以地圖中提取的信息和用戶(hù)的約束作為特征填充文本,即以輸入地理信息作為布局文本的主要依據(jù),同時(shí)接受用戶(hù)定義的視覺(jué)屬性和約束條件。從地圖中提取的特征為文本布局的位置提供了基礎(chǔ),而文本又給地圖提供了更多的信息,最終提高了可視化信息傳遞的效率。
3.2.2 代表性算法介紹
Hurtut[15]和 ?ztireli[18]都認(rèn)為利用參數(shù)控制圖形的分布是非常困難的,但他們都選擇基于統(tǒng)計(jì)的方式來(lái)布局。而 Reinert[4]提出一種不基于統(tǒng)計(jì)數(shù)據(jù)的方法,即從用戶(hù)的輸入中推導(dǎo)布局規(guī)則。基于特征提取算法中,具有代表性的 Reinert 算法摒棄了以往使用參數(shù)或基于統(tǒng)計(jì)的布局方式,將拼貼問(wèn)題形式化為從每個(gè)圖形的高維特征空間映射到二維的布局問(wèn)題。同時(shí),通過(guò)在系統(tǒng)中引入交互,用戶(hù)可以使用圖釘固定一部分圖形的位置,系統(tǒng)從用戶(hù)確定的子集中計(jì)算出用戶(hù)期望的布局,并影響圖形的最終布局。
其中,P 為特征投影矩陣;t 為轉(zhuǎn)換參數(shù);f 為特征向量; 為布局函數(shù);X 為轉(zhuǎn)換后的坐標(biāo)矩陣。 可以將結(jié)果投影到不同的坐標(biāo)系統(tǒng)中,t可以使參數(shù)向量 x 沿參數(shù)的軸作偏移。如在笛卡爾坐標(biāo)系下,改變 t 可以使圖形沿坐標(biāo)軸偏移。
平衡臨近圖形的距離可以產(chǎn)生良好的最終布局,但從高維特征空間映射到二維坐標(biāo)時(shí),每個(gè)圖形被看作一個(gè)特征向量,并未考慮圖形之間的重疊與間隙。即映射時(shí)未考慮圖形在空間上的相互關(guān)系,故需在映射之后,對(duì)圖形的布局進(jìn)行優(yōu)化。
在布局上,系統(tǒng)也使用了基于 CVD 圖的方式,通過(guò)逐步迭代目標(biāo)函數(shù)來(lái)達(dá)到優(yōu)化目的。在目標(biāo)函數(shù)中,使用圖形邊界與 CVD 區(qū)域邊界的差值的平方和來(lái)衡量布局 X 偏離平衡的程度:
交互時(shí),系統(tǒng)首先生成一個(gè)初始結(jié)果,用戶(hù)可以使用圖釘工具在界面中固定一部分圖形的位置;隨后,系統(tǒng)根據(jù)用戶(hù)指定圖形的特征向量,推測(cè)用戶(hù)期望的布局,并將其應(yīng)用到全局。
自底向上生成技術(shù)的思路為從每個(gè)圖形出發(fā),依次向已有的圖形上拼接最合適的圖形,最終逐步填充整個(gè)目標(biāo)輪廓。
在自底向上的拼接過(guò)程中,由于每當(dāng)系統(tǒng)將一個(gè)圖形拼接到拼貼畫(huà)中,必須不斷地對(duì)圖形進(jìn)行角度、比例的調(diào)整,并評(píng)估兩者的匹配程度,因此需要高效的局部形狀匹配。這個(gè)過(guò)程涉及巨大的搜索空間——大量的圖形,且對(duì)于每個(gè)圖形又有無(wú)限個(gè)角度、位置、比例的組合。現(xiàn)有的描述符,如基于曲率比例空間(Curvature Scale Space)[19]、形狀上下文(Shape Context)[20]、三角區(qū)域表示(Triangle-area Representation)[21],可以很好地測(cè)量形狀之間的整體相似度,但不能直接應(yīng)用到拼貼畫(huà)的生成中。拼貼畫(huà)的生成核心在于兩個(gè)圖形的局部形狀的拼接,而并不考慮兩個(gè)圖形的整體相似度,且全局描述符帶來(lái)的巨大搜索空間會(huì)導(dǎo)致拼接效率極速下降。
Kwan[2]提出的算法可以對(duì)任意填充元素與任意指定的輪廓進(jìn)行拼貼畫(huà)生成,并支持對(duì)輸入元素進(jìn)行旋轉(zhuǎn)與比例縮放來(lái)優(yōu)化填充結(jié)果,極大地?cái)U(kuò)展了算法的應(yīng)用場(chǎng)景。該算法在拼貼畫(huà)生成領(lǐng)域具有開(kāi)創(chuàng)性,引入了以局部圖形描述符為基礎(chǔ),在填充圖形中搜索最適合填充的圖形。相比于傳統(tǒng)的形狀描述符在匹配時(shí)需要考慮位置、角度和比例的組合,Kwan 提出的 PAD(Pyramid of Arclength Descriptor)描述符在匹配時(shí)比例和角度不變,這意味著在匹配最相似的圖形時(shí),無(wú)需計(jì)算角度和比例。通過(guò)該描述符確定最優(yōu)匹配圖形以及最優(yōu)匹配點(diǎn)之后,可使用較小的搜索代價(jià)確定該圖形的角度和縮放。PAD 描述符也可以通過(guò)改變參考點(diǎn)的數(shù)量,動(dòng)態(tài)調(diào)整 PAD 向量的描述能力和計(jì)算復(fù)雜度。
PAD 描述符的核心是一個(gè)基于角度和比例不變域的塔式描述符。首先算法確定一個(gè)縮放比例不變域,此處使用的是絕對(duì)曲率的積分。給定一段曲線(xiàn),對(duì) t、s 點(diǎn)的絕對(duì)曲率積分的定義為:
但僅使用絕對(duì)曲率的積分并不能準(zhǔn)確地表達(dá)圖形,或者說(shuō),不能依靠絕對(duì)曲率的積分來(lái)進(jìn)行形狀匹配。所以研究中引入了弧長(zhǎng)這一形狀信息來(lái)輔助形狀匹配?;¢L(zhǎng)并不是對(duì)縮放比例不變的,但可以通過(guò)簡(jiǎn)單的變形來(lái)解決。
首先是對(duì)輸入圖形進(jìn)行離散化,離散化后的每?jī)蓚€(gè)點(diǎn)之間具有相同的絕對(duì)曲率的積分變化率。然后開(kāi)始構(gòu)建描述符,對(duì)于圖形輪廓上的任意點(diǎn) ,需要同時(shí)考慮 點(diǎn)的左側(cè)和右側(cè)。為了更精確描述圖形的局部,一個(gè) n 維的向量被引用進(jìn)來(lái):
可以通過(guò)計(jì)算兩點(diǎn)的 PAD 向量之間的距離,來(lái)計(jì)算兩圖形輪廓上兩點(diǎn)的相似度。其距離公式為:
對(duì)圖形局部進(jìn)行匹配之后,即可進(jìn)行拼貼畫(huà)的整體生成。給定一個(gè)比例任意的圖形庫(kù),其生成是一個(gè)迭代的過(guò)程。如圖 3 所示,每次迭代都是從一個(gè)目標(biāo)形狀開(kāi)始,最初的目標(biāo)形狀為種子圖形,由用戶(hù)指定,或者隨機(jī)產(chǎn)生。每次迭代都是從未拼接的圖形庫(kù)中尋找局部輪廓距離最近的K% 個(gè)作為候選,并對(duì)每個(gè)候選的拼接結(jié)果通過(guò)公式(9)進(jìn)行打分,選取最終打分高的結(jié)果作為最終的拼接圖形。
圖3 PAD 拼接示意圖Fig.3 Schematic diagram of PAD splicing
通過(guò)弧長(zhǎng)與曲率的結(jié)合,對(duì)圖形局部輪廓進(jìn)行特征描述,并計(jì)算圖形局部的相似度,可取得較優(yōu)的拼接效果。但這樣可能會(huì)陷入僅考慮輪廓的局部而忽略了整體的問(wèn)題,從而導(dǎo)致圖形局部匹配度較高,但全局相對(duì)較差。該方法通過(guò)引入對(duì)候選位置打分的方式來(lái)選擇最優(yōu)的拼接,一定程度上緩解了這個(gè)問(wèn)題。但從本質(zhì)上來(lái)說(shuō),PAD 的生成過(guò)程是貪婪的,并不能得到全局最優(yōu)的結(jié)果。
基于螺旋線(xiàn)算法將從文本中提取的核心詞作為主要的輸入圖形,文本的大小代表權(quán)重,最終拼接成完整的拼貼畫(huà),其主要用于詞云可視化中。Viegas[1]最初提出使用阿基米德螺旋線(xiàn)來(lái)生成詞云,將單詞沿著以畫(huà)布為中心的螺旋線(xiàn)按照權(quán)重從大到小的順序依次拼接,生成最終結(jié)果。詞云作為經(jīng)典的文本可視化工具,可以迅速生成美觀(guān)且信息量豐富的可視化結(jié)果。但在生成詞云的過(guò)程中,并不會(huì)考慮目標(biāo)輪廓,所以生成的結(jié)果不能很好地填充目標(biāo)輪廓,不適合生成有目標(biāo)輪廓的拼貼畫(huà)。故許多研究者在詞云算法的基礎(chǔ)上進(jìn)行了諸多改進(jìn),使詞云可以有效填充目標(biāo)輪廓。
4.2.1 相關(guān)算法介紹
Buchin[23]提出 Geo Word Clouds 算法,其輸入是一個(gè)在每個(gè)位置均有文本標(biāo)簽的目標(biāo)輪廓。首先,采用聚類(lèi)的方式對(duì)輸入的文本進(jìn)行分組;然后,根據(jù)填充詞的頻率,在填充目標(biāo)輪廓時(shí)盡可能使大小合適、不重疊的文本靠近。這一定程度上解決了詞云不能很好地填充目標(biāo)輪廓的問(wèn)題,并且取得了相對(duì)不錯(cuò)的效果。但其對(duì)用戶(hù)的輸入要求比較高,需要目標(biāo)輪廓的各個(gè)位置帶有文本標(biāo)簽,不具有普適性。
Chi 等[24]提出一種不同的思路,其輸入不同于傳統(tǒng)的帶權(quán)重文本:將傳統(tǒng)螺旋線(xiàn)生成的詞云作為輸入,使用受約束的剛體動(dòng)力學(xué)牽引單詞重新排布為目標(biāo)形狀。這大大降低了用戶(hù)的輸入要求,比較容易使用。但其生成方式的限制在于,如果輸入的詞云布局與目標(biāo)輪廓差距較大,則需要多次迭代才能得到較優(yōu)的布局。而迭代過(guò)程需要耗費(fèi)大量的時(shí)間,且其魯棒性較差,在部分情況下無(wú)法保證良好的填充效果,仍需要手動(dòng)參與。
4.2.2 代表性算法介紹
Wang[5]提出一種具有輪廓約束的詞云算法,降低了用戶(hù)使用的門(mén)檻——僅需要用戶(hù)輸入普通的文本和目標(biāo)輪廓,而無(wú)需額外的信息即可得到填充率高且美觀(guān)的結(jié)果。該算法復(fù)雜度較低、生成速度較快,適合大規(guī)模的文本可視化生成。
具體來(lái)說(shuō),系統(tǒng)首先提出了形狀感知的阿基米德螺旋線(xiàn)(如圖 4 所示),其核心在于將目標(biāo)輪廓的距離場(chǎng)和阿基米德螺旋線(xiàn)結(jié)合起來(lái)。傳統(tǒng)的螺旋線(xiàn)是以畫(huà)布中心為原點(diǎn),沿著圓的切線(xiàn)方向逐步擴(kuò)大半徑而繪制出來(lái)。在這個(gè)過(guò)程中,螺旋線(xiàn)的方向一直是圓的切線(xiàn)方向,所以繪制結(jié)果與目標(biāo)輪廓無(wú)關(guān)。而引入距離場(chǎng)后,距離場(chǎng)可以很好地反映目標(biāo)輪廓的信息。在繪制螺旋線(xiàn)時(shí),以距離場(chǎng)的極點(diǎn)為原點(diǎn),每一點(diǎn)的前進(jìn)方向并非一直是圓的切線(xiàn)方向,而是根據(jù)每一點(diǎn)的距離場(chǎng)信息確定,由距離場(chǎng)引導(dǎo)生成符合目標(biāo)輪廓的螺旋線(xiàn)。
圖4 形狀感知的阿基米德螺旋線(xiàn)Fig.4 Shape-aware Archimedean spirals
為了使算法更具有普適性,系統(tǒng)加入了對(duì)復(fù)雜圖形的處理。為了防止極端情況下,以中心為原點(diǎn)的螺旋線(xiàn)不能很好地對(duì)輪廓邊緣進(jìn)行處理,算法引入了圖形切割的步驟。在輸入圖形后系統(tǒng)會(huì)首先檢測(cè)目標(biāo)輪廓內(nèi)的所有分區(qū),并為每個(gè)分區(qū)生成單獨(dú)的距離場(chǎng);然后使用一個(gè)迭代的梯度下降過(guò)程,在每個(gè)分區(qū)中定位出局部最大值;最后生成單獨(dú)的螺旋線(xiàn)來(lái)排布單詞。其效果如圖 5所示,(a)中圖形僅被分為兩個(gè)區(qū)域,填充效果較差,(b)為 ShapeWordle 所采用的圖形切割后的分區(qū)結(jié)果,(c)為在新的分區(qū)結(jié)果上使用形狀感知的螺旋線(xiàn)所產(chǎn)生的效果。結(jié)果表明,經(jīng)過(guò)分區(qū)后,螺旋線(xiàn)對(duì)目標(biāo)輪廓的貼合能力得到提升,實(shí)現(xiàn)了文本填充目標(biāo)輪廓。但基于螺旋線(xiàn)算法的限制在于,螺旋線(xiàn)的排布適合規(guī)則的輸入,如矩形文本或常規(guī)且相似的圖形,而難以對(duì)不規(guī)則的輸入圖形進(jìn)行排布。
圖5 ShapeWordle 分區(qū)方式對(duì)比Fig.5 ShapeWordle partition mode comparison
拼貼畫(huà)的生成算法優(yōu)勢(shì)突出——加快設(shè)計(jì)速度、提高設(shè)計(jì)質(zhì)量、降低人工時(shí)間,可以迅速應(yīng)用于工業(yè)界。近年來(lái),隨著傳統(tǒng)電商及社交電商的發(fā)展,海報(bào)設(shè)計(jì)、營(yíng)銷(xiāo)設(shè)計(jì)的需求成幾何倍數(shù)增長(zhǎng),傳統(tǒng)靠人力設(shè)計(jì)的速度與效率已跟不上時(shí)代的需求,自動(dòng)化海報(bào)設(shè)計(jì)成為大勢(shì)所趨。如阿里推出的鹿班系統(tǒng)能智能生成大量的海報(bào)來(lái)應(yīng)對(duì)雙十一這類(lèi)電商節(jié)的需求,但其海報(bào)生成的結(jié)果大多設(shè)計(jì)簡(jiǎn)單、內(nèi)容單調(diào),容易引起大眾審美疲勞?,F(xiàn)有的拼貼畫(huà)生成技術(shù)非常適合生成風(fēng)格與眾不同的海報(bào)設(shè)計(jì),鑒于目前學(xué)界對(duì)兩者結(jié)合的研究并不多,所以如何針對(duì)海報(bào)等宣傳版面進(jìn)行拼貼畫(huà)算法設(shè)計(jì)將成為未來(lái)可能的研究方向。
在生成算法上,自頂向下的生成技術(shù)和自底向上的生成技術(shù)各自取得了相當(dāng)優(yōu)秀的結(jié)果,但也存在一些的問(wèn)題尚待解決。
自頂向下的生成技術(shù)可以快速地確定物體的初始位置,再對(duì)細(xì)節(jié)進(jìn)行微調(diào)。受限于算力與速度的同時(shí),由于系統(tǒng)確定初始位置時(shí)并不會(huì)過(guò)多考慮圖形的輪廓,使得圖形輪廓匹配不佳或微調(diào)耗費(fèi)時(shí)間長(zhǎng)?;谳喞?xì)分生成算法思路受限于先將目標(biāo)輪廓細(xì)分,然后將填充圖形變形以適應(yīng)細(xì)分后的網(wǎng)格。在網(wǎng)格已經(jīng)確定的情況下對(duì)填充圖形進(jìn)行調(diào)整時(shí),若對(duì)復(fù)雜的填充圖形進(jìn)行較大的改變易導(dǎo)致其失真,而微調(diào)算法也需要較為復(fù)雜的運(yùn)算。且這種變形往往不能取得全局最優(yōu)的結(jié)果。其中一個(gè)可行的思路是在進(jìn)行網(wǎng)格細(xì)分之前,先對(duì)填充圖形的輪廓進(jìn)行簡(jiǎn)化,達(dá)到計(jì)算可以接受的程度。即在網(wǎng)格生成之初,將簡(jiǎn)化后的圖形輪廓與網(wǎng)格細(xì)分的形狀結(jié)合起來(lái),使生成的網(wǎng)格更加接近填充圖形的輪廓,以提高匹配度、減少后續(xù)微調(diào)。
在自頂向下的生成技術(shù)中,Hurtut[15]和Reinert[4]將不同的思路引入拼貼畫(huà)生成中。Hurtut 借助統(tǒng)計(jì)模型,將用戶(hù)生成的拼貼畫(huà)進(jìn)行擴(kuò)展,這種方式非常適合墻紙、瓷磚等需要重復(fù)圖案生成的應(yīng)用場(chǎng)景。其問(wèn)題也相對(duì)明顯,用戶(hù)對(duì)生成結(jié)果的控制力較差,不能有效地對(duì)結(jié)果進(jìn)行定制。在該思路的基礎(chǔ)上可以嘗試拓展可控的參數(shù),增加用戶(hù)對(duì)生成過(guò)程的參與度或?qū)Y(jié)果的可操作性,從而有效提高算法的適用范圍。Reinert 的創(chuàng)新之處在于,從用戶(hù)的輸入中推導(dǎo)布局,將拼貼畫(huà)生成看作每個(gè)圖形的高維特征向量降維到二維坐標(biāo)的問(wèn)題,在降維之后進(jìn)行局部的微變以?xún)?yōu)化最終結(jié)果。該思路與常規(guī)的解決方式有較大區(qū)別,可以迅速確定圖形的大概位置,但系統(tǒng)中微調(diào)的算法只能減少重疊問(wèn)題,而不能提高圖形之間的匹配度,造成結(jié)果的填充率較低。該算法的缺點(diǎn)在于,初始降維時(shí)圖形輪廓完全被忽略。因此,可以在特征向量中進(jìn)一步引入對(duì)圖形輪廓的描述符,降維時(shí)將圖形相似或可拼接的圖形盡可能靠近,并在降維后小范圍內(nèi)引入圖形描述符來(lái)進(jìn)行局部圖形的位置調(diào)整。也可以進(jìn)一步對(duì)局部圖形的位置進(jìn)行小范圍的再分配,改變其角度與縮放比例,完善局部圖形的拼貼效果。
在自底向上的生成技術(shù)中,Kwan[2]提出的基于局部圖形描述符算法在生成時(shí)需要對(duì)所有圖形進(jìn)行描述與匹配,適用于少數(shù)需要精確匹配的場(chǎng)景。對(duì)于大規(guī)模的圖形匹配,則需要借助多塊高性能 GPU 進(jìn)行并行運(yùn)算,才能將生成時(shí)間壓縮到一個(gè)可以接受的范圍。原文使用了 8 塊NVIDIA Tesla K20m 進(jìn)行并行運(yùn)算才將生成時(shí)間壓縮到 3 h 左右??紤]到原文設(shè)計(jì)的描述符已足夠精簡(jiǎn),所以在硬件計(jì)算能力未達(dá)到質(zhì)的突破情況下,描述符的生成方式并不適合廣泛使用。但PAD 描述符后續(xù)被用于小范圍的圖形識(shí)別[25]說(shuō)明,局部的描述符不僅可以進(jìn)行全局、窮舉式的匹配,還可以作為其他拼貼算法進(jìn)行局部?jī)?yōu)化的補(bǔ)充。通過(guò)對(duì)小范圍圖形的局部輪廓進(jìn)行匹配,將小范圍內(nèi)相似的局部輪廓進(jìn)行拼接,或作為圖形調(diào)整角度與縮放的依據(jù),從而優(yōu)化局部的拼貼效果與填充率。
而對(duì)于基于螺旋線(xiàn)算法,目前 Wang[24]的形狀感知的螺旋線(xiàn)在實(shí)現(xiàn)將文本填充到目標(biāo)輪廓上取得了較為不錯(cuò)的效果,且能夠移植到其他類(lèi)矩形的填充圖形上。但由于沿螺旋線(xiàn)的初始布局過(guò)程中僅考慮了矩形之間簡(jiǎn)單的重疊避免,不適用于復(fù)雜圖形的重疊避免與局部輪廓拼接。同時(shí),形狀感知的螺旋線(xiàn)在將圖形填充到目標(biāo)輪廓中的價(jià)值很大,可以有效地提高填充算法對(duì)目標(biāo)輪廓的感知能力。且其算法復(fù)雜度較低,可與其他算法結(jié)合,增強(qiáng)其他算法對(duì)目標(biāo)輪廓的感知能力。如先用包圍盒算法將圖形抽象成易于計(jì)算重疊的簡(jiǎn)單圖形,然后使用形狀感知的螺旋線(xiàn)將圖形拼接到目標(biāo)輪廓中,以此為基礎(chǔ)進(jìn)行微調(diào),提高局部輪廓的匹配度,從而充分發(fā)揮其算法對(duì)輪廓的感知能力。
隨著智能算法的發(fā)展和應(yīng)用,越來(lái)越多學(xué)者嘗試將智能算法引入拼貼畫(huà)領(lǐng)域。根據(jù)目的,將應(yīng)用于拼貼畫(huà)自動(dòng)生成的智能算法簡(jiǎn)單分為兩類(lèi):第一種是將智能算法應(yīng)用在對(duì)輸入圖形的預(yù)處理中,如提取圖片的核心區(qū)域、人臉等,或?qū)D形的特征進(jìn)行提取,并根據(jù)提取的特征進(jìn)行降維,從而確定圖形的初始位置;第二種則直接將智能算法應(yīng)用于確定圖形的最終位置,即應(yīng)用于拼接,如根據(jù)統(tǒng)計(jì)學(xué)習(xí)對(duì)已有的拼貼畫(huà)進(jìn)行擴(kuò)展。
5.3.1 應(yīng)用于預(yù)處理
對(duì)于第一種智能算法的應(yīng)用,以 Liu[26]在2017 年的相關(guān)工作為例,其首先使用 VGG-16 特征提取網(wǎng)絡(luò)對(duì)圖像進(jìn)行特征提取,得到對(duì)應(yīng)的特征向量,然后通過(guò) t-SNE 將特征向量維度降至二維平面,并進(jìn)行聚類(lèi)。該類(lèi)智能算法的應(yīng)用可看作以 Reinert[4]為代表的使用特征提取算法進(jìn)行初步布局的后續(xù)工作,通過(guò)智能算法可以顯著提高根據(jù)特征聚類(lèi)的準(zhǔn)確度。但僅針對(duì)圖形特征預(yù)處理的智能算法并不能完善拼貼畫(huà)生成中的“硬性標(biāo)準(zhǔn)”,如輪廓匹配度、填充率等。
而使用智能算法進(jìn)行核心區(qū)域與人臉的提取,常應(yīng)用于圖片拼貼中,可以有效去除圖片中無(wú)效的背景區(qū)域,使拼貼算法的重心處于圖片中的核心區(qū)域。
對(duì)于該種類(lèi)型的智能算法應(yīng)用,核心區(qū)域的語(yǔ)義性提取具有較大的研究?jī)r(jià)值。此類(lèi)型拼貼畫(huà)大多為表現(xiàn)同一主題的圖片的拼貼結(jié)果,提高語(yǔ)義性提取可以增強(qiáng)主題信息表現(xiàn)的力度。目前,在特征提取方向,利用 CNN 進(jìn)行特征提取可使提取到的特征向量較好地對(duì)輸入集進(jìn)行聚類(lèi)。但對(duì)用戶(hù)來(lái)說(shuō),CNN 的聚類(lèi)結(jié)果是不可解釋的,相關(guān)智能算法更接近黑盒模式,很難進(jìn)行語(yǔ)義化的解釋?zhuān)埠茈y讓用戶(hù)介入?yún)?shù)調(diào)整過(guò)程。Reinert[4]的算法說(shuō)明,通過(guò)讓用戶(hù)交互地調(diào)整聚類(lèi)后的結(jié)果,從調(diào)整后的結(jié)果中推測(cè)用戶(hù)意圖并進(jìn)行重新聚類(lèi),較為有效地讓用戶(hù)影響聚類(lèi)結(jié)果,降低用戶(hù)介入聚類(lèi)過(guò)程的理解成本。
5.3.2 應(yīng)用于拼接
本文討論的拼接算法大多為傳統(tǒng)算法,如何將智能算法應(yīng)用于拼接仍然是一個(gè)待探索的問(wèn)題。Hurtut[15]基于統(tǒng)計(jì)模型學(xué)習(xí)輸入拼貼畫(huà)的布局,從而實(shí)現(xiàn)對(duì)布局的擴(kuò)展是一個(gè)很好的嘗試,但其應(yīng)用場(chǎng)景較為單一,并不能廣泛用于拼貼畫(huà)生成中。
Kwan[2]的工作表現(xiàn)了局部匹配的強(qiáng)大效果,但由于其忽略整體輪廓,出現(xiàn)了輪廓重疊現(xiàn)象。在某些輸入集中,局部輪廓的匹配度與整體輪廓的匹配度是相關(guān)聯(lián)的,能否通過(guò)建立模型來(lái)構(gòu)建圖形局部與整體之間的關(guān)系,提高局部輪廓計(jì)算中對(duì)整體輪廓的感知,從而在使用局部匹配的拼接算法中,用較低的局部輪廓計(jì)算量達(dá)到接近整體輪廓的匹配效果。
拼貼畫(huà)算法的輸入主要為規(guī)則的簡(jiǎn)單圖形或不規(guī)則的復(fù)雜圖形,輸出為在少量重疊下高填充率的拼接結(jié)果。其布局算法可對(duì)其他涉及布局問(wèn)題的領(lǐng)域有借鑒作用——直接使用算法產(chǎn)生布局結(jié)果,或應(yīng)用于對(duì)布局結(jié)果的調(diào)優(yōu)中。如可以借鑒 Reinert[4]的方法對(duì)降維算法結(jié)果在二維平面可視化的分布:在降維后,對(duì)降維結(jié)果在二維平面使用 CVD 相關(guān)算法進(jìn)行迭代優(yōu)化,降低投影點(diǎn)之間的重疊,平衡投影點(diǎn)之間的距離,提高降維結(jié)果的易讀性。
同時(shí),拼貼畫(huà)拼接過(guò)程中降低重疊率、提高填充率的目標(biāo)與其他可視化布局問(wèn)題的目標(biāo)基本一致,有很好的借鑒與啟發(fā)作用。拼貼畫(huà)領(lǐng)域針對(duì)目標(biāo)輪廓的相關(guān)算法可以提高其他領(lǐng)域布局問(wèn)題中對(duì)目標(biāo)輪廓的感知能力,如樹(shù)圖等可視化形式,可以從 Wang[24]針對(duì)輪廓的螺旋線(xiàn)算法中得到啟發(fā),將樹(shù)圖或其他可視化方式與用戶(hù)提供的目標(biāo)輪廓相結(jié)合,增強(qiáng)結(jié)果的視覺(jué)效果。
在設(shè)計(jì)拼貼畫(huà)生成算法之外,擴(kuò)大拼貼畫(huà)算法的適用范圍也是發(fā)展該領(lǐng)域的重要方向。如Xu[14]將拼貼畫(huà)的輸入擴(kuò)展到書(shū)法領(lǐng)域,通過(guò)應(yīng)用拼貼畫(huà)算法的思想將文字填充生成藝術(shù)性較強(qiáng)的文字畫(huà)?;谶@一思路,可將拼貼畫(huà)的輸入擴(kuò)大到其他元素,從而產(chǎn)生創(chuàng)意性的結(jié)果。將算法的輸出載體擴(kuò)展到其他領(lǐng)域亦是如此,如 Gal[27]將拼貼這一概念擴(kuò)展到三維空間,使三維的物體拼接到三維的輪廓中,增強(qiáng)了結(jié)果的表現(xiàn)能力與表現(xiàn)空間。在拓展維度方面,也可以在不同載體上做更多的嘗試,如將載體擴(kuò)展到 3D 打印、虛擬現(xiàn)實(shí)技術(shù)與增強(qiáng)現(xiàn)實(shí)技術(shù)等方向。
在當(dāng)前算法的基礎(chǔ)上進(jìn)行創(chuàng)意性改良也是一個(gè)有趣的研究方向。Huang[28]將傳統(tǒng)的用戶(hù)給定輸入集更改為用戶(hù)指定輸入集的主題,算法從互聯(lián)網(wǎng)中匹配適合指定主題的拼貼元素。該改進(jìn)思路既減少了用戶(hù)尋找輸入集的繁瑣工序,也由于每次互聯(lián)網(wǎng)圖片的隨機(jī)性,增加了生成結(jié)果的多樣性。鑒于拼貼畫(huà)的結(jié)果與藝術(shù)有一定的相關(guān)性,研究者可在傳統(tǒng)算法基礎(chǔ)上,添加更多創(chuàng)意性、藝術(shù)性的改進(jìn),擴(kuò)展和增強(qiáng)算法結(jié)果的藝術(shù)表現(xiàn)能力。
本文從自頂向下與自底向上兩種思路歸納概述了計(jì)算機(jī)用于拼貼畫(huà)自動(dòng)生成的研究進(jìn)展, 對(duì)其中較有創(chuàng)新性的算法進(jìn)行了分析,并對(duì)該技術(shù)的未來(lái)發(fā)展趨勢(shì)進(jìn)行了總結(jié)和展望。
隨著社交電商與社交互聯(lián)網(wǎng)的發(fā)展,工業(yè)界對(duì)自動(dòng)生成較為復(fù)雜的設(shè)計(jì)需求將持續(xù)增長(zhǎng),而拼貼畫(huà)自動(dòng)生成技術(shù)作為結(jié)合了圖形學(xué)與可視化兩個(gè)領(lǐng)域的自動(dòng)技術(shù),可在可視信息表達(dá)與圖形展示效果之間取得良好平衡。目前,該領(lǐng)域仍然存在許多重要的問(wèn)題和挑戰(zhàn),需要更多的研究人員繼續(xù)進(jìn)行深入研究與探索。