蓝噪声取样(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算法。

原始的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)为合适的位置。

    range的意思

  • 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.