柳有權(quán)，張彩榮，馬 雷，石 劍，孫 昭，陳彥云

一種基于圖像結(jié)構(gòu)特征的實時點畫生成算法

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

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

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

點畫；風(fēng)格化；圖像處理；非真實感繪制

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

圖1 Pablo Jurado Ruiz點畫作品

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

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

1 相關(guān)工作

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

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

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

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

2 算法實現(xiàn)

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

圖2 本文算法流程圖

2.1 增量Voronoi序列

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

算法1. 生成增量Voronoi序列

Input：目標(biāo)序列長度

Output：增量Voronoi序列

1：← {}，← []

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

3：for= 1 todo

4：根據(jù)生成Voronoi圖

5：找到對應(yīng)的Delaunay三角形的最大外接圓

6：← 該外接圓的圓心

7：← 對應(yīng)Voronoi區(qū)域的面積×n

8：←+

9：←+

10：end for

Return

2.2 圖像結(jié)構(gòu)特征提取

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

2.3 點畫圖像生成

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

算法2. 生成點畫圖

Input：二維圖像。繪制點的最大、最小半徑1、2；權(quán)重1、2；使用的色調(diào)集合

Output：點畫圖

4：I←對應(yīng)的結(jié)構(gòu)特征圖

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

else

end if

end for

14：根據(jù).，，進(jìn)行繪制

3 實驗結(jié)果與分析

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

圖4 本文所提算法與其他算法對比結(jié)果

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

圖5 文章中所提算法的其他點畫結(jié)

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

圖6 用戶評分結(jié)果

4 結(jié) 論

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

[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]. 中國圖象圖形學(xué)報, 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] 基金項目：中央高?；究蒲袠I(yè)務(wù)費專項資金(310824173401)

[18] 第一作者：柳有權(quán)(1976-)，男，湖北秭歸人，教授，博士，碩士生導(dǎo)師。主要研究方向為計算機圖形學(xué)、虛擬現(xiàn)實技術(shù)等。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；