一種基于圖像結構特征的實時點畫生成算法

柳有權，張彩榮，馬 雷，石 劍，孫 昭，陳彥云

一種基于圖像結構特征的實時點畫生成算法

柳有權1，張彩榮1，馬 雷2,3，石 劍4，孫 昭1，陳彥云3

(1. 長安大學信息工程學院，陜西 西安 710064；2. 中國科學院大學計算機控制學院，北京 100049；3. 中國科學院軟件研究所，北京 100190；4. 中國科學院自動化研究所，北京 100190)

點畫是一種經典的藝術技巧，其用點的形式模擬圖像中色調的明暗變化，表現其藝術特質。由圖像自動生成點畫是圖像風格化和非真實感渲染的對象之一。為此，提出了一種基于圖像結構特征的實時點畫生成算法。使用一個預計算的增量Voronoi序列快速生成點畫所需的采樣點，通過輸入圖像和對應的結構特征圖共同指導點畫圖中點的半徑和色調，提高點畫圖像在邊緣及細節上的質量。實驗結果表明，該算法生成的點畫結果在視覺效果和數值誤差(SSIM)上均優于現有點畫生成算法，并且在繪制速度上能夠達到實時的性能，可應用于高幀率的場景中。

點畫；風格化；圖像處理；非真實感繪制

點畫是通過分布不同尺寸和密度的點來表現圖像色調明暗變化的一種藝術表現形式，可分為點畫雕刻和點畫繪制2類。點畫雕刻技術通常應用在版畫制作中，需要藝術家在印版上使用蝕刻工藝進行逐點雕刻。而點畫繪制通常是用大小和疏密程度不同的點在圖紙上進行創作。圖1展示了西班牙藝術家Pablo Jurado Ruiz的點畫繪制作品，該作品使用0.05 mm，0.1 mm和0.3 mm等3種不同規格的畫筆繪制而成。

圖1 Pablo Jurado Ruiz點畫作品

圖像風格化是圖像處理及非真實感繪制中的一類重要任務，而點畫生成算法是其研究的對象之一。傳統的點畫生成算法用點的密度變化來表現圖像中色調上的差別，通常使用半徑相同且色調單一的點。而藝術家在創作過程中會使用型號不同的畫筆來繪制不同大小和色調的點。目前，文獻[1]提出了一種可以生成不同尺寸和多色調的點畫算法。該算法在色調較亮的區域，繪制半徑和灰度值較大且稀疏的點; 而在較暗區域，繪制大量密集且半徑和灰度值較小的點。相比傳統方法，該算法更加真實地模擬了藝術家的創作過程，繪畫結果在質量上得到了提升。但在圖像的結構和細節信息的處理上，仍然存在一定的不足。

為了進一步提升點畫效果，更好地處理點畫圖像中結構和細節信息，本文對文獻[1]的工作進行了擴展，提出了一種基于圖像結構特征的實時點畫生成算法。使用預計算的增量Voronoi序列快速獲取點畫圖的采樣點。同時對輸入圖像進行處理，根據獲取的圖像結構信息，對點畫圖中點的大小和色調進行調整，以提升所生成的點畫圖的視覺效果。

1 相關工作

非真實感繪制是計算機圖形學中一類重要的研究方向。圖像風格化作為其中的實現方法之一，是一種建立在人類感知的基礎上，利用計算機生成具有藝術風格圖像的技術。常見的圖像風格化目標包括鉛筆畫、水彩畫、油畫等，而點畫的生成也是其主要研究的對象之一。

目前，已有不少針對圖像的點畫生成算法展開的研究。其中，文獻[2]將數字圖像作為輸入，通過半色調方法得到點的初始分布并對其進行松弛調整，以得到分布均勻且隨機的點。但該方法會使圖像邊緣模糊。使用泊松采樣獲取采樣點時[3-4]，由于得到的點分布不具有藍噪聲特性，會降低點畫質量。為了得到高質量的點畫結果，一些工作使用了不同的Voronoi迭代方法[5-7]。雖然提高了點畫質量，但都無法達到實時的性能。文獻[8]提出了基于圖像的加權Voronoi點畫技術。該方法根據點的初始分布計算相應的Voronoi區域，通過迭代調整每個點到其Voronoi區域的質心優化其分布。此方法生成的點畫圖質量較高，但迭代過程耗時較長，文獻[9]在Secord的基礎上，提出了隨機點畫快速生成算法。該算法通過提供多種密度分布函數，同時制定隨機分布策略，將點的模型參數化，進而實現點畫的快速繪制，不需要進行大量的迭代運算，但降低了點畫質量；為了獲得較好的視覺效果，文獻[10-11]提出了一種交互式點畫技術，手動確定點畫區域的方法；文獻[12]對傳統的Voronoi點畫法進行了改進，提出了用圖像特征來指導點畫生成的技術。雖然能夠得到合理的點分布，但仍然采用了Voronoi迭代松弛法來調整點的分布，迭代過程耗時較長；文獻[13]同樣使用基于迭代的方法進行繪制，雖然可以對采樣點密度進行控制從而大幅度提高點畫質量，但無法達到實時效果。

基于圖像的點畫技術除了傳統的繪制方法，還可以根據圖像灰度值設置背景和點的顏色，即在灰度值較大的區域，設置背景為白色，點為黑色；而在灰度值較小的區域，將背景設置為黑色，點為白色[2]。文獻[14]根據該方法提取出圖像特征區域，設置特征區域的底色為黑色，而其他區域為白色，有效地突出了圖像特征結構，改變了傳統技術中根據灰度值確定區域底色的方法。但該方法需要通過設計密度函數來控制點的疏密程度，而密度函數設計不合理會直接導致最終的點畫質量較差。文獻[1]提出了一種基于增量Voronoi序列的快速點畫生成算法，該算法中增量Voronoi序列具有藍噪聲特性，可預先離線生成，因此具有較高的繪制效率。但該方法在點畫質量上存在細節部分缺失和整體結構信息不夠完整等問題。

本文對文獻[1]的算法進行了改進。使用增量Voronoi序列獲取采樣點，并對原始圖像進行處理得到圖像的結構特征信息，通過使用原始圖像和該結構特征信息來調整點畫圖中點的半徑和色調，以得到更高質量的點畫結果。

2 算法實現

本文提出了一種基于圖像的實時點畫生成算法，其流程如圖2所示。使用一個預先生成的增量Voronoi序列來快速獲取采樣點。對原始圖像進行處理得到相應的結構特征圖，根據原始圖像和結構特征圖來調整點畫圖中點的半徑和色調。

圖2 本文算法流程圖

2.1 增量Voronoi序列

本文使用增量Voronoi序列[11]來獲取采樣點。該序列可預先離線生成，在使用時可以根據需要靈活選取序列長度。同時該序列具有藍噪聲特性，并且能保證在任何位置截斷所得到的序列都具有較好的藍噪特性。相比于其他采樣算法，本文使用預計算的增量Voronoi序列進行采樣，可以有效減少點畫繪制過程中的計算量，提高繪制效率，并同時保證樣本分布的質量。該序列首先使用2個隨機點對采樣空間進行Voronoi劃分，所得到的對應Delaunay三角形中具有最大外接圓的圓心即為采樣點的位置，而樣本的權重由對應的Voronoi區域面積決定。通過迭代更新Voronoi劃分來生成所需要的全部采樣點。具體生成算法如下：

算法1. 生成增量Voronoi序列

Input：目標序列長度

Output：增量Voronoi序列

1：← {}，← []

2：初始化隨機種子點vv添加到中

3：for= 1 todo

4：根據生成Voronoi圖

5：找到對應的Delaunay三角形的最大外接圓

6：← 該外接圓的圓心

7：← 對應Voronoi區域的面積×n

8：←+

9：←+

10：end for

Return

2.2 圖像結構特征提取

本文使用結構特征圖來提取圖像中的邊界和細節豐富的區域，并用該圖來指導點畫中采樣點的作用面積，進而決定其半徑及色調。在圖像中物體的邊界以及細節較為豐富的區域，通常需要分布更多的點來保留其特征。本文使用像素灰度與其4-鄰域的像素差值絕對值的最大值來表示該像素在圖像結構上的重要性。為了避免噪聲，對所得到的結構特征圖進行了平滑處理。

2.3 點畫圖像生成

本文提出的基于圖像結構特征的實時點畫算法使用增量Voronoi序列來獲取樣本分布，而點的大小和色調由輸入圖像及其結構信息共同決定。點畫繪制過程如算法2所示。使用二維灰度圖像作為輸入，并指定繪制最大點和最小點的半徑1和2、圖像與結構信息的權重1和2以及所使用的色調集合來進行繪制。根據圖像在結構信息上的重要性，算法通過第8，9行來決定是否保留采樣點。算法第10行得到點畫中點的覆蓋面積，進而求出點的半徑(可變半徑點畫中)。對于不可變半徑的點畫，設置1=2且1=0。算法第13行用來選取多色調點畫中點的色調。根據點的覆蓋面積、其所在位置圖像的亮度以及樣本的權重來決定其色調。

算法2. 生成點畫圖

Input：二維圖像。繪制點的最大、最小半徑1、2；權重1、2；使用的色調集合

Output：點畫圖

4：I←對應的結構特征圖

12：找出中與相鄰的兩個灰度值darker、lighter.

else

end if

end for

14：根據.，，進行繪制

3 實驗結果與分析

本文算法使用C++實現，在i7 3.40 GHz CPU、12 GB內存、Windows 10平臺上進行測試，并使用結構相似性(structural similarity，SSIM)對點畫質量進行定量評估[15]。SSIM是一種常見的衡量圖像相似度的指標，其值域為[0,1]，值越大表示2幅圖像相似性越高。圖3列出了實驗所使用的測試圖像與結構特征提取結果。

圖4 本文所提算法與其他算法對比結果

本文算法與現有其他算法進行對比，其結果如圖4所示。其中，圖4(a)~(c)均由半徑相同的點繪制而成：圖4(a)為由泊松采樣算法得到的點畫圖，可以觀察到點的分布不合理，圖像結構不完整和細節丟失等缺陷。圖4(b)和(c)分別為文獻[1]實現的單色調和多色調相同半徑的點畫結果，該結果與圖4(a)相比視覺效果有了明顯的提升，但細節繪制不夠清晰。圖4(d)~(g)為單色調可變半徑的點畫結果。其中圖4(d)為由傳統Voronoi序列采樣得到的點畫圖，該點畫圖質量較高，但實現該算法耗時較長。圖4(e)為文獻[1]提出的算法實現結果，其點的半徑由原圖像相應位置灰度值決定。圖4(f)和(g)為由文章中所提算法分別在1=0，2=1與1=1，2=1時的點畫結果，即圖4(f)中采樣點的大小由結構特征決定，圖4(g)中由結構特征和原圖像共同決定。從數值誤差SSIM可以發現，由原圖像和結構特征共同決定點的半徑所得到的點畫效果最好。圖4(h)~(j)為圖4(e)~(g)相對應的多色調可變半徑的點畫結果，色調級數均為8。由數值誤差評估可以看出，在多色調情況下，同樣是由原圖像和結構特征圖共同決定點的半徑所得到的點畫圖效果最好(圖4(j))。本文算法實現平均用時約0.72 ms，能夠實時繪制點畫圖像。相比其他算法，本文利用了圖像的結構特征，使得最終得到的點畫結果在視覺效果和數值誤差上均優于現有方法。圖5顯示了本文算法在其他圖像上得到的點畫結果。其中第一行為輸入圖像。圖5(a)和(b)為單色調點畫結果，其中圖5(a)中采樣點的大小由結構特征決定。圖5(b)中點的半徑由輸入圖像相應位置灰度值和結構特征圖共同決定。圖5(c)和(d)為圖5(a)和(b)相對應的多色調點畫結果，色調級數均為8。

圖5 文章中所提算法的其他點畫結

本文對圖4中各點畫結果進行了用戶調研，讓10名用戶對其進行評分，評分范圍為1~10，分數越高表示該點畫結果與原圖像更相似。用戶評分結果如圖6所示，可看出點畫結果的視覺效果和所測SSIM接近一致，即相比于其他算法的點畫結果，通過本文算法得到的點畫結果用戶評分較高。

圖6 用戶評分結果

4 結 論

本文提出了一種實時的圖像點畫生成算法。利用預計算的增量Voronoi序列來快速獲取采樣點，并使用圖像的結構特征來指導點畫中點的分布、大小和色調。實驗表明，該算法在視覺效果及數值誤差上優于現有算法，能夠得到質量更高，細節更豐富的結果，且可實現實時繪制。在本文算法的基礎上，進一步研究基于圖像結構特征的實時點彩畫算法，以及改變點畫中點的表現形式，用不同的形狀進行創作來增加點畫的多樣性具有一定的研究價值。

[1] MA L, CHEN Y, QIAN Y, et al. Incremental Voronoi sets for instant stippling [J]. The Visual computer, 2018, 34(6-8): 863-873.

[2] DEUSSEN O, HILLER S, VAN OVERVELD C, et al. Floating points: A method for computing stipple drawings [J]. Computer Graphics Forum, 2000, 19(3): 41-50.

[3] YUKSEL C. Sample elimination for generating poisson disk sample sets [J]. Computer Graphics Forum, 2015, 34(2): 25-32.

[4] COOK R L. Stochastic sampling in computer graphics [J]. ACM Transaction on Graphics (TOG), 1986, 5(1): 51-72.

[5] XU Y, LIU L G, GOTSMAN C, et al. Capacity-constrained Delaunay triangulation for point distributions [J]. Computers and Graphics, 2011, 35(3): 510-516.

[6] AHMED A G M, GUO J W, YAN D M, et al. A simple push-pull algorithm for blue-noise sampling [J]. IEEE Transactions on Visualization and Computer Graphics, 2017, 23(12): 2496-2508.

[7] DE GOES F, BREEDEN K, OSTROMOUKHOV V, et al. Blue noise through optimal transport [J]. ACM Transactions on Graphics, 2012, 31(6): 171.

[8] SECORD A. Weighted Voronoi stippling [C]//The 2nd International Symposium on Non-Photorealistic Animation and Rendering. New York: ACM Press, 2002: 37-43.

[9] 周亮, 李建明, 錢昆明. 隨機分布點畫快速算法[J]. 中國圖象圖形學報, 2003, 8(Z1): 9-12.

[10] LU A D, MORRIS C J, EBERT D S, et al. Non-photorealistic volume rendering using stippling techniques [C]//Proceedings of the Conference on Visualization '02. Washington, D C: IEEE Computer Society, 2002: 211-218.

[11] LU A D, MORRIS C J, TAYLOR J, et al. Illustrative interactive stipple rendering [J]. IEEE Transactions on Visualization and Computer Graphics, 2003, 9(2): 127-138.

[12] KIM D, SON M, LEE Y, et al. Feature-guided image stippling [C]//EGSR '08 Proceedings of the Nineteenth Eurographics Conference on Rendering. AIRE-la-Ville: Eurographics Association, 2008: 1209-1216.

[13] DEUSSEN O, SPICKER M, ZHENG Q. Weighted linde-buzo-gray stippling [J]. ACM Transactions on Graphics, 2017, 36(6): 1-12.

[14] 王會芹. 一種基于圖像的快速點畫法[J]. 計算機仿真, 2009, 26(10): 221-224.

[15] WANG Z, BOVIK, A C, SHEIKH, H R, et al. Image quality assessment: from error visibility to structural similarity [J]. IEEE Transaction on Image Processing, 2004, 13(4): 600-612.

[17] 基金項目：中央高校基本科研業務費專項資金(310824173401)

[18] 第一作者：柳有權(1976-)，男，湖北秭歸人，教授，博士，碩士生導師。主要研究方向為計算機圖形學、虛擬現實技術等。E-mail：youquan@chd.edu.cn

Structure-Based Real-Time Image Stippling

LIU You-quan1, ZHANG Cai-rong1, MA Lei2,3, SHI Jian4, SUNZhao1, CHEN Yan-yun3

(1. School of Information Engineering, Chang’an University, Xi’an Shaanxi 710064, China; 2. School of Computer and Control, University of Chinese Academy of Sciences, Beijing 100049, China;3. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China; 4. Institute of Automation, Chinese Academy of Sciences, Beijing 100190, China)

Stippling is a classical art technique that uses small dots to simulate varying degrees of solidity or shading and show its artistry. Generating stippling from image is one of the targets of image stylization and non-photorealistic rendering. In this paper, we propose a structure-based real-time image stippling algorithm. A pre-computed incremental Voronoi sequence is employed to generate sample points for stippling. To improve the quality on the edge and detail regions, we introduced input image and its corresponding image structure information to guide the radius and tone of the stipples. Experiments show that the stippling generated by pro-posed method is superior to the state-of-the-arts in visual and numerical error (SSIM). Our proposed algorithm can achieve real-time performance and apply to high frame rate scenes.

stippling; stylization; image processing; non-photorealistic rendering

TP 391

10.11996/JG.j.2095-302X.2019030435

A

2095-302X(2019)03-0435-06

2018-09-07；