韩艳茹，尹梦晓，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 算法简化初始三角网格，在保持图像结构特征的同时，减少网格顶点以突出简约、棱角分明的低多边形效果。实验结果表明所提方法有效地保留了图像的结构和颜色信息，减少了图像着色后的锯齿伪影，同时保持明显的低多边形风格化。对于视频低多边形渲染，利用时间一致性超像素跨帧跟踪同一对象的相同部分，建立视频帧之间的关联，并通过在采样点集中增加超像素块的交点和重心，使相邻帧之间的网格尽可能相似，从而降低了视频渲染后的抖动。