Sycamore

Phoenix reborns from the ashe

0%

Digital Stippling Survey

Posted on Edited on In

Martín, Domingo, et al. "A survey of digital stippling." Computers & Graphics 67 (2017): 24-44.

  • 传统点画
  • 数字点画
  • 点画技术
  • 数字点画和半色调

传统点画

传统的点画的目标是：使用点来表示主题的色调、形状、纹理等

但是这是一个耗时的过程，需要大量小时才能得出结果，这也就导致了点画艺术品的大小相对较小。并且点画的观察是需要有35cm-65cm的观看距离，在这个距离上，点的颜色和形状都是可以被辨别的。——艺术家秉承着“每一个点都自己的目的”

这种对单个点的点画和与放置更多点、像素的半色调形成对比。

在半色调中：每一个点、像素都应该不被观察到，这样只有他对色调的贡献才是最重要的

点画图像是静态的，在创建之后不能更改，这就意味着点画的布局模式非常重要，它传达了图像中的局部色调。点画艺术家通常旨在避免任何可见的点图案，但是一些特征可以有意地以线的形式进行放置点，比如说hedcut变体。

点画艺术家经常将“点画”和“线条”组合在一起，用点画来表现色调和纹理、用线条来强调边缘和轮廓

数字点画

点的排列

点放置的基本特征是：

  1. 对于给定的色调，点应该均匀放置
  2. 点的放置不能规则，要保持随机
  3. 点的密度表示图像中给定区域的阴影强度

在第一条特征中，默认是点与点不应该重叠，但是后来NPAR发现，某些传统点画技术依赖色调范围内点画的重叠和合并

早期的点画还是会在放置的点画上产生了规则的伪影（人为制造出来的pattern）。由于 Lloyd 方法的固有特性以及使用其未加权和加权质心 Voronoi 图进行点分布的点画。

伪影一般是不可取的，因为他们暗示了一些不存在的结构

现在避免伪影的办法有如下几种：

  1. 随机性/噪声

  2. 概率密度函数

  3. 泊松盘分布

  4. 非重复平铺

  5. 容量受限的松弛

  6. 基于示例的点放置：这种方法试图从真实示例中复制分布特征，不仅可以捕捉个别点画艺术家的风格，还避免了纯粹算法点画放置可能传达的过于完美的印象。例如泊松盘，虽然具有均匀但随机的点分布，但是在黑暗区域，点的灵活度较低，导致产生“自动放置”的印象。

    但是为了能匹配真实图片，必须考虑示例的原始尺寸和数字输出的尺寸和分辨率，所以这种办法不能选择任意数量的点画点，而是基于示例的点画密度从预期输出图像的空间大小中导出。

但是也可以有意引入伪影来强调线性特征，比如图像或线条中的边缘。

在采取预防措施后，点会自动、或多或少沿着特征排列。例如：Deussen通过使用色调阈值来实现这个效果。

在加权的Voronoi点画中，可以通过增加源图像的对比度实现边缘。

还有一种是将此类线放置作为算法的一部分，比如说hedcut点画就是一种几乎完全依赖于沿线性结构排列的点画的特殊形式

除去这个方面，数字点画为动态交互开辟了很多可能，人们可以通过放大点画图像来获得更多的细节，但是这个目标需要一种在适当点添加或删除点画的方法，从而不引入可见的伪影。

点的特征

一般来说，大多数数字点画方法都是假设所有点都是白纸上的黑色标记，许多早期的方法都是将点画点当做理想圆圈。

不使用圆圈的第一步是：使用任意点画形状来代替圆圈的位置（直接替换），但是对于一些考虑到点形状的算法不再适用：比如，Hiller扩展了Lloyd的方法来考虑点画标记的形状，Dalal使用了基于频率的包装方法来放置任意点

其他人一般使用平面图案的一般分布的创建，或者放置一些类似于特定类型的hatch插图的短标记，这些短标记是支持overlap的。这些技术都不需要形状感知。

除了上述的形式，很多研究人员将点画点用像素表示，渲染像素点是不需要复杂的计算的，并且提供了一种将点画点减少到只有其分布能被感知到的可能

还有一种方法不仅考虑点画的位置，还要尝试将形状建立在手工点画的基础上；最近的工作认为，还需要考虑点的灰度和颜色纹理。

点画技术

质心Voronoi图

这一类方法的主要目标：均匀分布点画点，同时避免他们彼此靠得太近

Lloyd方法提供了一个机制：

  1. 计算初始点分布的Voronoi图
  2. 将点移动到Voronoi图的质心
  3. 迭代1,2步骤

但是会出现一些链伪影。

Deussen是第一个将这种方法应用与点画的人：如果有参考图像则先生成一个半色调的图（图像的黑暗部分是密集区域，较亮的部分是稀疏的区域），如果没就通过特殊的brush手动添加点， 然后在这个半色调的基础上利用手动控制的brush进行基于CVD的松弛。

brush的种类：

  1. Edit brush

    添加或删除点是在逐点的基础上完成的，也可以通过在每个时间步长以给定数量的点进行操作的画笔来完成的。也可以将点标记为固定的，这可以防止它们受到后续移动操作的影响。

  2. Relaxation brush

    使用此刷子，用户能够放松点画点的位置，以实现均匀分布。

  3. Jitter brush

    有时候点太规则了，如果用户想要消除视觉边界或更改区域中的均匀间距，就可以使用该brush来获得一个小的随机偏移（点到点距离的百分比）

  4. Shape brush

    形状画笔允许修改点的参数。 用户可以按给定的百分比放大/缩小点或直接设置它们的大小。 这有助于稍微改变区域的色调或生成强烈的深色边框。

Secord将Deussen的方法进行了更新：根据要复制的图像的色调来权衡Voronoi区域的计算。

使用这种加权的质心Voronoi图 (wcvd) 的主要优点是：现在在迭代放置点画时会自动考虑图像的颜色/灰度值——不再需要交互式使用brush。

这种方法引入了密度函数，也就是每一个图像的位置根据初始图像的深浅会给定一个密度值，那么质心的位置就应该是 \[ C_i=\frac{\int_Ax\rho(x,y)dA}{\int_A\rho(x,y)dA} \] 这里的\(\rho(x,y)\)是每个像素点的密度值

这样再迭代过程中，质心会不断向高密度区域靠拢，会导致点不断在高密度区域聚集，这样就能区别高低密度的区域。

Secord还提出了一个基于预先计算点画点分布的快速点画过程。

将恒定色调的图像结果成为点画等级：\(0\leq t \leq 1\)，最高的度是纯黑色的度，其余逐渐递减

下图是一个从黑色到白色的九个等级，分布有1000个点画，每个图相差125个点。

在预先计算好的点画等级，就可以快速stipple一个图像：

1
2
3
4
5
for all pixel positions (x,y) ∈ [0,1]×[0,1] do
	Map image value at (x,y) to stipple level l
	Copy stipples on level l inside (x − 1/2, y − 1/2) × (x + 1/2, y + 1/2)
	to output
end for

将图像切分成很多小region，然后检查每个像素的值，确定哪个点画的级别是合适的，并将落在像素覆盖区域的所有点画复制输出。

会降低图像的分辨率。

Hiller基于像素的方法计算WCVD，将其扩展到了线和多边形。

这个方法让对象可以旋转，需要去确定几何距和主要惯性轴。

算法的输入是一组在平面上的对象\(\{Q_i\}_{i=1}^k\)和一个密度函数\(\rho\)

输出是松弛的质心Voronoi镶嵌和松弛的对象分布

1
2
3
4
5
6
7
8
9
10
确定对象Q的质心和对象的主要惯性轴
repeat
	确定每一个对象的Voronoi图
	for i=1 to k do begin
		计算每一个Voronoi图的质心z
		将对象的质心c移动到Voronoi图的质心z中
		调用ORIENTATION(根据角度phi调整对象的主轴角度)
	end
until 点z满足收敛准则
end
1
2
3
ORIENTAION():
	输入：Voronoi区域V和对象Q，他们俩的质心重叠
	输出：对象Q围绕着其质心旋转角度phi

Balzer等人解决了WCVD的主要问题之一——结果倾向于规律的伪影，例如可见链

他们证明：传统的WCVD会产生规律的伪影是因为迭代乜有及时停止，似乎没有理想的时间点来停止迭代。

他们在松弛过程中为每个区域引入了容量约束来使得约束收敛到无伪影分布。

定义站点\(s_i\)对应的Voronoi \(V_i\)的容量计算如下： \[ c(s_i)=\int_{V_i}\rho(x)dx \] 所有点的分布最佳适应密度函数\(c^*\)为： \[ c^*=\frac{\int_\Omega\rho(x)dx}{n} \] 容量约束就是\(c(s_i)=c^*\)

一个站点的容量相当于其相应的Voronoi区域的面积，该区域用密度函数加权。因此，我们的容量限制要求分布中的每个站点都同等重要。

  1. 先从随机分配开始：\(A: X \to S\)，其中X有m个点，S有n个站点，这些都满足容量约束
  2. 在初始化之后，最小化\(F'(X,A)=\sum^m_{i=1}|x_i-A(x_i)|^2\)，通过交换X中属于不同站点的点来最小化\(F'\)
  3. 对交换操作的限制保证了容量约束 C 在整个最小化过程中保持不变。
  4. 执行分配交换，直到没有进一步的交换减少能量并且算法停止在代表 \(F'\) 的局部最小值的稳定状态。

这种局部最小值是通过优化分配A来实现的，而不是像Lloyd放法那样通过重新放置站点s来实现的。

分布函数

Secord基于从输入图像派生的概率密度函数，该函数用于重新分布一组初始均匀分布的随机点。这种方法不仅消除了迭代处理，而且还允许创建帧连贯动画，因为 PDF 会针对动画图像序列不断变化。

从一维PDF中获得随机点（二维同理）：

已知PDF为\(p(x)\)

  1. 将\(p(x)\)进行积分:\(C(x)=\int_0^xp(t)dt\)
  2. 将\(C(x)\)进行反函数操作得到：\(x'=C^{-1}(x)\)
  3. 在y轴等距离采点，在x轴上就可以得到密度分布

Kopf提出了一种快速算法：渐进式蓝噪声Wang tile

通过使用飞镖投掷算法来生成蓝噪声图块，其中飞镖的半径会逐渐减少来获得一个密度增加的点的渐进序列。这样的图块可以快速生成具有任意非均匀密度的点集。

为了避免伪影重复，我们使用Wang tile，难点在于，不同密度的Wang tile相互拼接会导致边缘不符合泊松盘属性。

因此，我们的想法是：通过合并几个渐进的环形源块来创建一组Wang tile

目标是生成：\(2K^2\)个Wang tile

  1. 首先应该为每一个K创建一个源砖
  2. 将其余对应边缘的源砖合并
  3. 合并后，我们定义结果点的顺序排序来使得图块渐进

按照上文所述，我们先创建一个源砖T，并合并到与其边缘颜色对应的其他四个源砖N、E、S、W。

为了合并两个图块，我们需要计算连接的接缝，由于两个源砖都是蓝噪声砖，所以接缝两侧的点都较好的分离

所以目标是：寻找一个接缝，避免缝左右的点不符合蓝噪声

做法就是：将两个源砖做并集，然后利用Voronoi图来将集中的相邻点分开，最后的缝就是用Voronoi图的边构成。我们使用Dijkstra的最短路径来计算s,t的最短路径（s，t就是两个砖拼接起来的端点）。

这样的好处是：防止接缝进入瓷砖的内部太深

Jones介绍了一种基于 Voronoi 图的\(O(NlogN)\) 算法，但没有松弛。在每一步中，算法都会搜索剩余空间最多的区域来放置一个新点。

Dunbar 和 Humphreys描述了一种类似的增量算法来计算泊松盘分布，该算法基于专用数据结构以及对仅具有线性运行时间的类泊松磁盘分布的修改。

Xu 开发了一种基于 Delaunay 三角剖分的容量受限版本的方法。 在某种程度上，这形成了和 Balzer 等人引入的容量受限的 Voronoi 镶嵌一样的效果。但计算时间更快。

Delaunay三角就是将站点当做点，然后和相邻的两个点连接起来形成一个三角形，优化的目标函数如下： \[ T=argmin\frac{1}{m}\sum_{t\in T}(A_t-\frac{1}{m}\sum_{t\in T}A_t)^2 \] \(A_t\)是三角形的面积，\(m\)是三角形的数量。

如果是不均匀的图像，则优化的目标函数如下： \[ T=argmin\frac{1}{m}\sum_{t\in T}(A_td_t-\frac{1}{m}\sum_{t\in T}A_td_t)^2 \] \(d_t\)表示的是每个三角形t内的平均像素密度。

通用分布函数

在平面上分布点的问题，其应用远不止点画。 例如，点分布的通常目标是符合一些数学属性，例如蓝噪声。 然后，它们可以用于多种应用，如纹理、基于点的渲染、蒙特卡洛方法等； 点画只是其中一种可能性。

Ebeida展示了一种计算均匀泊松盘分布的方法，该分布既是最大的又是无偏差的，并且可以在非凸域上使用。

算法有如下步骤：

  1. 建立一个背景网格；标注好内部网格和边缘网格
  2. 阶段一，向网格中扔飞镖，去除掉击中的飞镖
  3. 生成剩余空隙的多边形近似值
  4. 阶段二，向空隙扔飞镖，更新剩余区域

我们通过生成覆盖输入域边界框的统一网格来启动算法。单元边为长度\(r/\sqrt{2}\)，单元对角线为长度\(r\)，因此每个单元只能容纳单个样本。每个单元格都有两个属性。有效单元格是可能接受样本的单元格；边界单元格与一个或多个输入边相交。

在有效的单元格中扔飞镖，如果这个飞镖命中了非空盘区域或者边界之外，就认定此次迭代未命中，如果命中则将其命中的网格更改为无效。

第二步就是对于每一个有效的网格，去找其空盘的区域，也就是说圆弧与网格线界定的封闭区域，为了方便计算，用弦来代替弧

第三步和第一步类似，就是将第二步产生的多边形去代替步骤一中的网格。

施洛默提出了一种方法，该方法应用将点从样本迭代移动到最远点或样本中所有点的策略，以增加每对点之间的总距离，从而获得几乎最佳的蓝噪声特性。

基本算法非常简单：每一步从一组点\(X\)中去一个点，并试图将其移动到一个新的位置，该位置尽可能原理其余点，即最远点。

本文利用Delaunay三角剖分，最远距离计时所有Delaunay三角剖分中的最大外接圆圆心。即要移动\(x\)，则将其从三角剖分中移除，然后检查剩余的三角形来找到最远的点\(f\)，将\(x\)插入到\(f\)中

Heck等人解决了点分布中的混叠问题，并根据高频中的振荡水平定义了两种新类型的蓝噪声采样模式: 步进蓝噪声和单峰蓝噪声。它们产生的模式防止了结构化的混叠。

基于示例

旨在直接从特定示例中提取特定属性，并在基于示例的方法中使用这些属性来生成新图像，或者通过使用用于分布点画点的示例 (即，基于示例的点画) 或通过使用示例创建点画点 (即基于示例的点画)。

Barla使用基于示例的方法来捕获绘制的输入图案的样式，然后以相同的样式合成更大的图案。他们通过评估元素集群及其分布来捕获输入模式的组织特征。基于此分析，他们使用邻域匹配算法合成了新的模式，以生成新的感知相似的笔画簇以及其中的几组。合成依赖于Lloyd的方法来生成种子位置，然后将学习到的特征用于实际元素和笔画放置。Barla等人的技术存在的问题是：它只生成模式本身，而不考虑目标色调。

Kim在示例图中考虑了一整套点画图案，为不同的色调提取不同的补丁。 然后，他们提取点画的中心，计算得到的分布纹理的灰度共生矩阵 (GLCM)，并使用它来记录几个纹理统计数据。 然后，他们可以使用拒绝采样为每个不同的色调级别合成新的分布纹理，从而最大限度地减少样本和合成补丁之间的统计测量之间的误差。 他们要么直接使用合成结果，要么根据来自示例的扫描将点画点纹理放置在新位置。 这种整体方法适用于浅色调和深色调，但在手绘示例中点画可以合并的中间色调存在问题。

灰度共生矩阵：

以（1，1）点为例，GLCM（1，1）值为1说明只有一对灰度为1的像素水平相邻。GLCM（1，2）值为2，是因为有两对灰度为1和2的像素水平相邻。

Martín通过将点不再视为完全黑色的标记来解决后一问题-它们捕获并使用点画点示例作为灰度/彩色纹理。

结构感知

强调图像边缘，Mould提出了一种方法：

首先从输入图像中构造一个图：图中的每一个像素都是一个节点，每个节点的重要性计算为\(\alpha d+\beta g\)，其中\(d\)是黑暗程度，\(g\)是梯度幅度，\(\alpha=1/\sum d\)，\(\beta = 1/\sum g\)。

渐进式算法从距离为零的单个站点 (例如，图像的一个角) 开始，并向外扩散，从而计算图形中的最短路径。当最短路径超过阈值长度时，将放置距离为零的新站点; 我们继续直到探索整个图。

初始种子放置在图像中的某个位置。Dijkstra的算法用于扩展种子周围的区域；当新扩展的节点的路径成本超过阈值时，扩展步骤会触发添加新的点画。新的点画位置是具有最高梯度幅度的前沿节点，因为我们希望将点画优先放置在图像边缘上。至关重要的是，新站点的距离设置为零，因此扩展最初发生在新站点附近 (因为堆中的所有其他节点都具有至少阈值的距离)。当图形的任何部分都没有待扩展时，渐进算法终止。

  1. 围绕第一个中心展开一个区域；
  2. 在边界上选择了一个新的中心；
  3. 新区域被扩展，直到再次达到阈值；
  4. 第三个中心被放置，并扩展

在图中，黑色轮廓表示距离中心点画最近的节点集，类似于Voronoi区域。在放置新点画时，边界是灰色和白色区域之间的边界。

Li和mould后来推出了一种方法，该方法在强调线性特征的同时，产生了更好地保留原始图像的色调和对比度的结果。他们的总体方法是按照输入图像的像素对对比度和结构极端 (黑色或白色) 像素的重要性得出的优先级顺序来处理输入图像的像素。然后，如果放置点画点，则引入的误差将分布在相邻像素之间，从而导致其优先级的更新。

Hedcut

Kim通过提取图像中的特征线来模拟手动过程，使用这些特征线生成距离场，然后依次使用这些特征线生成平行的引导线，沿着这些引导线，点画点使用约束Lloyd算法进行排列。对于最终的图像，作者通过基于色调图像调节点画的大小来控制色调。

之后他们不仅使用图像特征提取引导线，还考虑了等照度线。

Son等人进一步改进了结果，不仅从特征图中提取了一组平行线，而且提取了一个特征矢量场，并从中提取了一个结构网格用于hatch,此结构网格遵循垂直和平行于从图像中提取的特征的方向。然后在网格线相交的位置排列点画点，并根据结构网格和色调图对点进行参数化。

衡量与基准

Halper研究了心理学和NPR之间的关系，从而提出了关于不同渲染风格如何改变观看者对各自图像的感知和交互的建议。

研究人员使用了知觉研究（即使用人类参与者）或对结果进行物理分析（即不涉及人类；例如光谱分析）。

Isenberg等人进行了一项实验，比较了手绘插图和计算机生成的插图，包括点画作为插图风格。他们发现，人们可以很容易地区分这两种类型的点画，特别是由于WCVD驱动的点画放置伪影，以及在计算机生成的图像中使用大量点画点的倾向。然而，参与者表示，他们欣赏计算机生成的图像的准确性，而他们喜欢手绘图像的“角色”

数字点画与半色调

点画和半色调都有共同的目标，即代表二进制介质的连续色调图像。

然而，我们从观察到手工点画是一种艺术形式，与其他用于双调再现的技术 (例如半色调) 相反，半色调纯粹是转换图像的算法方法。

前者导致相对规则的表示，而后者产生更随机的结果。在这两个极端之间，绿色噪声半色调结合了这两种方法的特性。

尽管如此，所有形式的半色调都使用像素或打印机点作为它们的主要原语，他的目的是放置点，使它们的图案导致对正确色调的感知，理想情况下根本看不到各个点。

传统点画的目标与其相反：每个点都更大，并且有一个目的： 除了简单地再现色调外，圆点还经常被放置在图像中的特征和细节引导下，有时会与其他基元 (例如线条) 组合并相互作用。

然而，在迄今为止的数字点画中，这种控制是缺乏的——仅存在部分 (算法) 解决方案 。因此，今天的数字点画在很大程度上缺乏传统艺术中的美学控制，就像半色调一样，虽然它能够再现通常以艺术示例的方式放置的大点的方面。