一种基于图像结构特征的实时点画生成算法

柳有权，张彩荣，马 雷，石 剑，孙 昭，陈彦云

一种基于图像结构特征的实时点画生成算法

柳有权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；