蓝噪声取样(Blue noise sampling) 相关知识

论文方面涉及的知识点，果然一下就遇到脑容量的瓶颈。嗯，加快进度憋论文。

‘with minimal low frequency components and no concentrated spikes in energy.’

蓝噪声的特征：最小限量的低频成分，能量峰值也没有提供。这意味着取样时没有结构上低频导致的混淆现象和杂波导致的间隙。

我找到的资料通过泊松碟分布的生成蓝噪声属性的点分布方法：在泊松碟分布的中，通过Dart-Throwing Algorithm生成这种蓝噪声属性的点分布。这种方法为随机在平面上生成候选点，如果处在前面已经接受的样本点的最小距离内才接受其的生成。《Stochastic sampling in computer graphics. ACM Trans. Graph》描述泊松碟分布，Yellott通过观察眼球中的锥体分布并进行傅里叶变化得到它的泊松碟分布。它在频域的图像如下，在原点上有一个尖峰。

除了两个样本之间的距离需要大于某个具体的值这个限制外，样本还被随机放置在平面上。这个最小距离减少了噪音的幅度。《Hierarchical Poisson disk sampling distributions》继续通过泊松碟分布来取样平面的数据，描述了dart-throwing算法是实现了按序布局点：将每个候选点放置到它的位置上。同样的地，当新点与已放置点的距离太近时则证明这个候选点无法放置。当点的数量达到某个具体的阈值，或者已经无法放置新点时，算法停止。并改进了算法，使得通过改变点之间的限制半径来控制呈现点的数量。并减少了对初始参数的依赖。可以通过下方两个图比较，上图为原始的dart-throwing算法的结果，下图为作者改进后的dart-throwing算法。

生成可以含有蓝噪声属性泊松碟点分布的方法主要有3种：

• incremental methods(增量方法)：也就是前述的dart-throwing方法。在《Adaptive Incremental Stippling using the Poisson-Disk Distribution》的改进方法中自适应了局部密度更新碟的半径大小，使得保留更多的特征。算法开始于时，初始包含一个随机位置的碟（disk，包含位置信息和限制距离半径）和放置碟的可用范围（boundary）。这个初始元素直接在图层上绘制。接下来，迭代地从队列中获取合法位置的碟，并与新生成的碟P进入函数中运算出一个半径值，使得P的半径依据局部密度调整为合适的大小。只要新的碟P不与已经绘制到图层上的碟产生重叠问题，就将新生成的碟压入队列成为可以绘制的碟。否这不做处理。无论成功与否都将通过新生成的碟更新Q的合理范围。使得下一个碟的布局能在合理范围内。直到将所有队列中的元素都出队。可以从下图中的例子模拟一下，程序运行的判断。(a)中红线为碟Q的可用范围。(b)为新碟与已经绘制的元素重叠，(c)为合适的位置。

• High-throughput methods(高通量方法)：大量的预计算过程，但是执行时快。在《Recursive Wang tiles for real-time blue noise》使用了一种生成progressive blue noise Wang tiles（王氏砖块）的算法。依据王氏砖块的特点，新砖块只能与已存在砖块边的颜色一致才能渲染。在蓝噪声取样的应用中能减少锯齿并显著降低噪音水平。使用这种方法生成的均匀密度点和jittered regular grids一样快。如下图，中间图为取样特征得出的4个原砖块合并。

• Approaches based on Constrained Voronooi Diagrams(基于CVD的方法)：这种方法使用沃罗诺伊图来生成样本。在《Fast capacity constrained Voronoi tessellation》中将处理过程加快。依据开销函数来寻找取样结果合并最小的开销。其大致进行取样的过程如下，沿着不规则的边缘消除距离远远高于平均距离的点。

这三种方法的横向比较：增量方法和基于CVD的方法的结果是最好的，但执行速度远远慢于高通量方法。

####参考

1. Stippling and Blue Noise
2. Cook, R.L., Stochastic sampling in computer graphics. ACM Trans. Graph., 1986. 5(1): p. 51-72.
3. McCool, M. and E. Fiume. Hierarchical Poisson disk sampling distributions. in Proceedings of the conference on Graphics interface ‘92. 1992. Vancouver, British Columbia, Canada: Morgan Kaufmann Publishers Inc.
4. Ascencio-Lopez, I., O. Meruvia-Pastor and H. Hidalgo-Silva, Adaptive Incremental Stippling using the Poisson-Disk Distribution. Journal of Graphics, GPU, and Game Tools, 2010. 15(1): p. 29-47.
5. Kopf, J., et al., Recursive Wang tiles for real-time blue noise. ACM Trans. Graph., 2006. 25(3): p. 509-518.
6. Li, H., et al. Fast capacity constrained Voronoi tessellation. in Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. 2010. Washington, D.C.: ACM.