圖像和視頻的低多邊形渲染

韓艷茹，尹夢曉，2*，覃子軒，蘇 鵬，楊 鋒，2

（1.廣西大學計算機與電子信息學院，南寧 530004；2.廣西多媒體通信與網絡技術重點實驗室（廣西大學），南寧 530004）

（*通信作者電子郵箱ymx@gxu.edu.cn）

0 引言

非真實感渲染（Non-Photorealistic Rendering，NPR），亦被稱為風格化渲染，專注于模擬藝術式的各種繪制風格，是計算機圖形學中一個傳統的研究領域［1-2］。低多邊形風格作為一種非真實感渲染的新型藝術形式，是一個比較新的研究課題，但多年來一直都有相似風格的非真實感渲染研究。早年，研究人員開發了基于描邊的系統［3-4］，隨著它的發展，呈現出不同的藝術風格，如Impasto 繪圖（厚涂顏料繪畫法）［5］、手繪［6-7］、彩繪玻璃風格［8-9］和Arcimboldo 般的拼貼［10-11］以及Chen 等［12］提出的用Voronoi 圖細分曲面生成具有多邊形風格的時尚圖像等，它們的生成結果看起來與低多邊形樣式非常類似。這些非真實感渲染的目的是相似的，即將圖像渲染成更抽象的結果，而不會丟失原圖像的結構特征和顏色等主要信息。

低多邊形渲染是把多色元素（如圖像、3D 模型）用三角形分割，并取原多色元素相應位置的顏色填充每個小三角形的一種渲染技術，可以產生具有簡約、抽象、棱角分明等特征的藝術風格效果。在計算機建模的早期階段，計算機性能有限，難以處理復雜的網格。由有限數量的多邊形（主要是三角形）面組成的低多邊形模型因其低細節、低精度的特點被廣泛用于早期3D建模。隨著簡化視覺設計的發展，低多邊形風格在2D插圖和平面設計領域獲得新的生命力，成為NPR 領域的一種新的設計趨勢，影響著其他數字藝術領域，如數字動畫、影像和游戲等，以及傳統藝術領域，如繪畫、雕塑等［13-14］（如圖1所示）。

圖1 低多邊形風格作品Fig.1 Low-poly style works

繪制低多邊形風格圖像需要專業的畫家才能完成，且繪制過程繁復而耗時，如果能用計算機自動生成低多邊形風格的作品，實現計算機“代替”手工繪制，就可以將人們從乏味而耗時的手動操作中解放出來，同時使非專業用戶也能進行低多邊形創作，因此在視覺設計方面有較高的實際應用價值。

本文提出了一種自動生成低多邊形風格圖像和視頻的方法，結合超像素和邊緣特征信息，能有效地保留圖像結構和顏色信息，減少圖像著色后的鋸齒偽影，同時低多邊形風格化明顯。對于視頻，應用時間超像素模型來跨時間跟蹤對象的同一部分，并通過在采樣點集中增加超像素塊的交點和重心，使相鄰幀之間的網格盡可能相似，從而減少抖動。

1 相關工作

目前已有一些編輯軟件可以幫助用戶執行圖像低多邊形渲 染，例 如Image Triangulator App、Adobe Photoshop 以 及Illustrator。但是，用戶必須手動選擇頂點來創建三角網格，這是一項繁瑣且耗時的工作。Dmesh［15］和TRIGRAFF［16］是兩個移動應用程序，它們可以在沒有用戶交互的情況下自動生成低多邊形圖像，但是圖像結構特征沒有得到很好的保留，視覺效果較差。

近年來，關于低多邊形渲染的研究主要集中在圖像上。Gai等［17］提出了一種基于特征流場的Voronoi圖迭代頂點選擇的低多邊形渲染方法，可以較好地保持圖像的結構特征，但對提取的特征邊緣的質量比較敏感；此外，若輸入圖像具有豐富細節信息，該算法生成的三角形數目過多，導致渲染過程耗時且渲染結果的低多邊形風格不明顯。Ma 等［18］提出了一種自適應細化方案，使用超像素方法提取圖像的結構信息，對于選擇的大量超像素交點，根據保持圖像結構和顏色的重要性對其進行預排序，并允許用戶自由選擇頂點數來構建三角形網格進行渲染。該方法僅基于超像素分割信息，缺少對圖像細節特征的考慮，因而渲染結果對圖像細節信息保持不充分且鋸齒狀偽影比較明顯。上述兩種方法只能處理圖像，沒有視頻處理方案。

Ng 等［19］提出了一種Pic2Geom 算法來生成低多邊形幾何圖形，利用邊緣檢測、顯著性檢測和人臉檢測生成一組頂點，然后基于這些頂點執行Delaunay三角剖分生成三角網格進行顏色填充。該方法可以較好地保持圖像中人臉部分的特征信息，但對于圖像中人臉之外其他部分的圖像結構特征保持得較差。吳凱琳［20］提出一種繪制低多邊形風格人物肖像畫的方法。該方法通過圖像前景、背景分割以及邊緣檢測得到肖像圖的五官特征以及面部輪廓的特征點，并結合基于灰度信息隨機選取的頂點執行Delaunay 三角剖分生成三角網格；然后根據三角形內的灰度值繪制平行線以生成低多邊形風格肖像畫。該方法只能對肖像畫進行低多邊形風格化，且要求輸入的肖像畫是正面的以便檢測五官特征。

Zhang 等［21］的方法可以自動生成低多邊形風格的圖像和視頻。該方法為每個點設置一個采樣概率，以保留輸入圖像的邊緣特征，但采樣點通常會偏離目標對象的特征邊，導致圖像邊緣特征不能得到很好的保持，渲染結果存在明顯的鋸齒狀偽影；對于視頻低多邊形風格化，則通過提高在當前幀中位于圖像邊緣且在上一幀被選為頂點的像素點的選擇概率來消除相鄰幀之間三角形位置和顏色突然變化而引起的抖動，但消除效果不佳，仍存在明顯的抖動現象。Lawonn 等［22］將圖像三角剖分過程描述為一個能量最小化問題，基于三角剖分和原圖像的顏色構建均方根近似誤差，通過減小近似誤差來自適應調整頂點位置以優化三角剖分。處理過程中在高近似誤差區域自適應地逐步插入更多的頂點，以此來拆分原有三角形，迭代執行此過程來逐步細化三角剖分，直到滿足所需的近似準則。該方法中能量梯度的計算是昂貴的，需通過圖形處理器（Graphics Processing Unit，GPU）來加速實現。Lawonn等［22］將該方法應用于視頻數據，從前一幀的三角剖分開始，優化下一幀的頂點位置，以最小化近似誤差，計算得到幀相干的視頻三角剖分。

2 圖像低多邊形渲染

圖2 所示為本文提出的圖像低多邊形渲染方法的框架流程（原圖Flamingo 來源：https：//www.quanjing.com），主要由3個核心部分組成：圖像的特征提取和超像素分割、三角網格的生成以及網格渲染。

本文提出的圖像低多邊形渲染方法首先結合輸入圖像的超像素分割［23］和邊緣特征信息［24］選擇三角網格頂點，然后基于這些頂點執行Delaunay 三角剖分［25］生成初始三角網格，并采用帶約束的二次誤差度量（Quadric Error Metric，QEM）算法［26］保持圖像特征邊對初始三角網格進行簡化，調整網格頂點分布生成最終的三角網格，最后對三角網格填充顏色獲得具有低多邊形風格的圖像。該方法分為3 個階段：預處理、三角網格的生成和網格渲染。

2.1 預處理

首先對輸入圖像I進行預處理，采用SLIC 算法［23］生成圖像I的超像素分割，其中超像素數目K由用戶指定；使用Canny邊緣檢測算法［24］提取圖像I的特征邊。

2.2 三角網格的生成

低多邊形風格圖像由數量有限且大小不一的三角形構成，生成高質量的三角網格是獲得良好的低多邊形渲染效果的關鍵，而三角網格的質量取決于網格頂點的分布。高質量的三角網格需具備以下特征：細節豐富區域的三角形密集且小，用來保持圖像結構特征；相應地，缺少細節區域的三角形稀疏且大，能突出低多邊形棱角分明的藝術風格。本文將三角網格的生成過程分為三個部分：三角網格頂點的選取、初始三角網格的生成以及特征保持的最終三角網格生成。

圖2 圖像低多邊形渲染的基本框架Fig.2 Basic framework of image low-poly rendering

1）三角網格頂點集P的選取。用于生成三角網格的頂點集記為P，它包含三個子集P1、P2和P3，即P=P1∪P2∪P3。其中，P1、P2和P3的選取流程如下：

a）基于圖像I的超像素分割，利用8 鄰域邊界跟蹤法提取超像素塊的邊界，將邊界上點的集合記為ES；圖像I四條邊界上像素點的集合記為Eb，則P1=ES∩Eb。

b）基于超像素邊界ES，提取超像素分割中相鄰超像素塊的交點，記為點集P2。

c）基于預處理提取的圖像I的特征邊，將特征邊上點的集合記為Ee，計算差集Ed=Ee-N(e，2)，其中e∈ES，N(e，2)表示超像素邊界ES的2-鄰域集。然后對差集Ed進行均勻采樣，得到均勻采樣點集，記為P3。這里Ed取為Ee和N(e，2)的差集可以避免對集合Ee和ES重復取點；集合P3是對集合Ed的均勻采樣，如圖3 所示（原圖來源：https：//www.gdalpha.com/），這樣能夠有效保留細節豐富區域的邊緣特征。

在選點過程中，Canny 檢測算子［24］提取的圖像特征邊對參數設定敏感，參數不同會影響選點及渲染結果，如圖3（a）～（c）分別對應不同參數所得結果，其中：Ksize 表示高斯核大小，Threshold 表示Canny 算子的滯后閾值。通過調整參數以得到較完整且噪點少的特征邊，即：細節豐富區域的特征邊保留完整，細節較少區域的像素點則作為不重要的點被過濾掉。如圖3（b），設置參數高斯核大小為（9，9），低閾值為5，高閾值為60，得到的輪廓較完整（對比圖3（c））且噪點少（對比圖3（a）），圖像細節得到有效保留且低多邊形風格化明顯。

均勻采樣過程與文獻［27］的方法相似。假設Ed為初始頂點集，在Ed中隨機選擇一點作為種子，畫出一個以種子為中心、半徑為r的排斥圓，而后去掉圓內的其他點。然后從圓外隨機選取一個新的種子采樣點，生成另一個以新種子為中心、半徑為r的圓，并刪除該排斥圓內的點。重復該過程，直到Ed中的所有點都被處理完畢，最后所有中心點形成均勻分布的點集P3。我們觀察到大多數超像素塊的形狀都接近正六邊形（如圖4（a）所示），易得出正六邊形的邊長為，因此，選取，其中w，h分別為圖像的寬度和高度，K為超像素塊數，fs為控制采樣半徑大小的權重。經過測試分析，本文實驗中取fs=0.5。

圖3 Canny算子參數對渲染結果的影響Fig.3 Effect of Canny operator parameters on rendering results

圖4（原圖來源：https：//www.quanjing.com/）展示了使用特征邊信息優化頂點采樣的結果，其中黑線表示超像素邊界，淺色線表示特征邊。可以看出，通過結合特征邊信息顯著減少了鋸齒狀偽影。

圖4 結合邊緣信息前后的結果對比Fig.4 Results comparison before and after combining edge information

2）初始三角網格的生成。基于步驟1）中選取的三角網格頂點集P執行Delaunay三角剖分［25］，生成初始三角網格MI。

3）最終三角網格的生成。采用QEM 算法［26］對初始三角網格MI進行保持特征邊的簡化，調整網格頂點分布，生成更能反映圖像特征且突出低多邊形簡約風格的最終三角網格，具體實現流程如下：

a）將步驟1）中得到的對特征邊Ee與超像素邊界ES的2-鄰域集的差集Ed的均勻采樣點集P3中的點，標記為特征點。

b）基于初始三角網格MI，標記網格MI中兩個端點都是特征點的邊為特征邊。

c）分別設定邊收縮代價公式（1）中的四項權重w1、w2、w3和w4，將初始三角網格MI的顏色屬性看作高度場來計算MI中所有網格頂點的二次誤差矩陣。

d）計算初始三角網格MI中所有邊的收縮代價，選擇收縮代價最小的邊進行收縮，形成新的網格頂點和拓撲連接關系。

e）迭代執行步驟d）直到滿足簡化要求為止，完成初始三角網格MI的簡化，生成最終的三角網格M。

QEM算法［26］中邊的總收縮代價定義為：

其中：w1、w2、w3、w4為用戶指定的權重；CQ(v1，v2)為邊(v1，v2)的二次誤差代價，CR(v1，v2)為三角形正則性代價，CF(v1，v2)為特征邊代價，CA(v1，v2)為三角形面積代價。各項代價的詳細計算方式請參考文獻［26］。

2.3 網格渲染

低多邊形風格圖像由大小不同的三角形構成，且每個三角形都有唯一的顏色。本節使用原圖像中每個三角形重心的顏色作為三角形的渲染顏色，對生成的最終網格M著色。

對于每個頂點為pi，pj，pk的三角形T(pi，pj，pk)，選取輸入圖像中T重心處的顏色作為T的渲染顏色RC(T)，即：

其中：C(x，y)是輸入圖像的(x，y)處像素的顏色，(xpi，ypi)，(xpj，ypj)，(xpk，ypk)分別是點pi，pj和pk的坐標。

3 視頻低多邊形渲染

3.1 視頻低多邊形渲染方法

視頻低多邊形渲染方法是對圖像渲染方法的擴展，可以對視頻全局或視頻中局部移動對象進行低多邊形風格渲染。相比圖像渲染，視頻渲染要考慮幀與幀之間的連續性，需要滿足相鄰幀之間的網格盡可能相似，以減少視頻著色后的抖動。本文利用時間一致性超像素［28］跨幀跟蹤一個對象的相同部分的特性，建立視頻幀之間的關聯。此外，采用視頻分割算法［29］分割視頻中的移動對象，對移動對象和背景執行不同的頂點采樣策略以得到其對應分布密度不同的網格頂點。然后可選擇對全部網格頂點或只對視頻中移動對象內部的網格頂點執行Delaunay 三角剖分［25］并著色，對應獲得全局渲染或局部移動對象渲染的效果。視頻低多邊形渲染方法如下：

輸入 原視頻（幀數為N，N＞1）；

輸出 原視頻的低多邊形風格渲染視頻。

步驟1 預處理。將輸入視頻以每秒25幀的幀率轉換為圖像序列IF={ |Ii i=1，2，…，N}；然后采用時間一致性超像素算法［28］對圖像序列IF進行預處理，得到IF的時間一致性超像素分割，其中每幀圖像的超像素數目都為K且由用戶指定；使用Canny 邊緣檢測算法［24］提取圖像序列IF的特征邊；對圖像序列IF，利用視頻分割算法［29］將移動對象與背景分離，得到視頻中移動對象的分割。

步驟2 三角網格的生成。

1）選擇三角網格的頂點集P。點集P由子集P1、P2、P3和P4組成，即P=P1∪P2∪P3∪P4。

a）將Ii的時間一致性超像素分割中的超像素邊界點集記為ES，圖像Ii四條邊界上像素點的集合記為Eb，P1=ES∩Eb。

b）基于超像素邊界ES，提取Ii的超像素分割中的相鄰超像素塊的交點，記為點集P2。

c）基于超像素交點集P2，計算Ii的每個超像素塊的重心，將重心的集合記為P3。P3可以使相鄰幀之間的網格盡可能相似（如圖5所示），進而減少抖動。

圖5 超像素的重心可以使相鄰幀之間的網格盡可能相似Fig.5 Centroids of superpixels making meshes between adjacent frames as similar as possible

d）基于預處理提取的Ii的特征邊，將特征邊上點的集合記為Ee，選取差集Ed中在Ii的移動對象內部的點進行均勻采樣得到P4，其中Ed=Ee-N(e，2)（e∈ES，N(e，2)表示超像素邊界ES的2-鄰域集）。

2）基于頂點集P執行Delaunay 三角剖分［25］，生成Ii的三角網格M。

步驟3 網格渲染。對步驟2生成的三角網格M根據3.2節視頻網格渲染方法填充顏色，M中的每個三角形都著色后，得到Ii的低多邊形風格的圖像。

步驟4 視頻合成。將步驟3 得到的低多邊形風格圖像序列按序以每秒25 幀的幀率合成視頻，得到低多邊形風格視頻并輸出。

基于全局渲染得到的P，選取移動對象內部的點作為局部移動對象渲染的頂點集，然后執行Delaunay 三角剖分［25］進而填充顏色得到局部移動對象渲染的效果。

3.2 視頻網格渲染

對于視頻渲染，定義三角形T(pi，pj，pk)的顏色初始估計值IC(T)為：

渲染顏色RC(t)(T)定義為：

其中：t是幀號，RC(t-1)(T)是前一幀中T對應三角形的渲染顏色；d是一常數，本文的實驗中，取d=100；DC(T)是IC(T)與前一幀中相應三角形的渲染顏色RC(t-1)(T)之間的顏色誤差，DC(T)可以減少相鄰幀間因顏色輕微變化引起的抖動（如圖6所示（原圖來源：https：//www.gdalpha.com））。DC(T)定義為：

其中R(T)、G(T)和B(T)分別表示三角形T的紅、綠、藍三色通道的值。

圖6 DC(T)約束相鄰幀間顏色的輕微變化Fig.6 Slight change in color between adjacent frames under DC(T)constraint

4 實驗和結果分析

本章將本文方法與其他低多邊形渲染方法［17-18，21］進行對比和分析，并定義平均誤差（Average Error，AE）來度量輸入圖像I和其渲染圖像I′之間差異，AE 值越小，則表示I′和I越相似，圖像的顏色信息保持得越好。圖像I′的AE定義為：

其中：w、h分別為圖像I′的寬和高，p為I′中的像素點，OC(p)、RC(p)分別表示I′中p點處的原始顏色和渲染顏色。

圖7（來源：https：//www.photophoto.cn）是圖像低多邊形渲染實驗的原圖，圖8是不同方法的渲染對比結果。從圖8中可以看出，本文方法生成的渲染結果能獲得更小的AE 值，有效地保持了原圖像的豐富細節信息和原圖像的結構特征，減少了著色后的鋸齒狀偽影，且低多邊形風格化效果明顯。

圖9 展示了本文方法與文獻［21］的視頻低多邊形渲染方法的2 組測試實例對比結果，其中Card(P)表示頂點數。從圖中可以看出，在頂點數較少的情況下，本文方法生成的渲染結果獲得了更小的AE值，細節保持較好，圖像邊界比較清晰，沒有明顯的鋸齒狀偽影，具有更好的圖像結構和視覺效果。

圖7 圖像低多邊形渲染實驗的原圖Fig.7 Original images for image low-poly rendering experitments

圖8 圖像低多邊形渲染結果的比較Fig.8 Comparison of image low-poly rendering results

圖9 視頻低多邊形渲染結果的比較Fig.9 Comparison results of video low-poly rendering

圖10（原圖來自http：//www.92sucai.com/）則給出了更多類型公開視頻的渲染結果，以展示本文方法的有效性。

圖10 本文方法針對視頻的渲染效果展示Fig.10 Rendering effect of the proposed method for vedios

圖11 給出了包括自然場景、物體和動畫在內的許多場景的低多邊形渲染結果（原圖來源：https：//www.redocn.com）。

本文方法在3.6 GHz 頻率Inter Core i7-4790 CPU 和8 GB內存的PC 上進行測試。本文方法主要步驟的運行時間以及對比方法對應的計算時間如表1 所示，其中文獻［17］未提供算法代碼，表1中對應的時間數據來自文獻［17］。

圖11 本文方法生成的各種場景的渲染結果Fig.11 Rendering results of a wide range of scenes generated by the proposed method

表1 運行時間對比 單位：sTab.1 Comparison of running time unit：s

5 結語

本文提出了一種低多邊形渲染方法，可以自動對圖像和視頻進行低多邊形風格化。該方法基于超像素分割和邊緣特征信息選擇網格頂點生成初始三角網格，使圖像細節特征得到最大化的保留，然后采用帶約束的QEM 算法簡化初始三角網格，在保持圖像結構特征的同時，減少網格頂點以突出簡約、棱角分明的低多邊形效果。實驗結果表明所提方法有效地保留了圖像的結構和顏色信息，減少了圖像著色后的鋸齒偽影，同時保持明顯的低多邊形風格化。對于視頻低多邊形渲染，利用時間一致性超像素跨幀跟蹤同一對象的相同部分，建立視頻幀之間的關聯，并通過在采樣點集中增加超像素塊的交點和重心，使相鄰幀之間的網格盡可能相似，從而降低了視頻渲染后的抖動。