Poisson disk sample (泊松盘采样)

今天组会时的一篇2017年TVCG的论文, “Uncertainty Visualization by Representative Sampling from Prediction Ensembles”,其中用到了一个随机采样的方法叫泊松盘采样,我感觉效果很棒,联想到之前投稿月我们图布局项目中也用到了随机采样,以后或许可以试试泊松盘,所以会后整理了一下这个采样方法。

泊松盘采样优点

首先说一下泊松盘采样的优点,

  • 具有蓝色噪声频谱特征。
  • 与单纯的随机采样方法相比,这种方法在保持随机性的同时,使采样点的分布更加均匀,可以弥补随机采样的不足。

其中,关于蓝色噪声频谱,它是描述随机类型特征的一个统计模型,其特点是主要频率周围分布的其他频率值都非常小,所以真值或者主频率很容易被检测到。这种特征很类似于点扩散函数,可以降低互相干噪声。

与其他算法的对比

  • uniform random,算法虽然简单,有现成的库可以使用,但是最后随机出来的效果不是很好,存在采样点重叠,过采样,欠采样等问题。
  • 米切尔最佳候选算法(Mitchell’s best-candidate algorithm),从候选的采样点中选择出最佳采样点。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    function sample() {
    var bestCandidate, bestDistance = 0;
    //numCandidates为固定数量候选采样点,这个越少算法运行速度越快,越大速度慢质量高
    for (var i = 0; i < numCandidates; ++i) {
    var c = [Math.random() * width, Math.random() * height],
    d = distance(findClosest(samples, c), c);
    //最佳采样点就是距离固定点最远的那个点
    if (d > bestDistance) {
    bestDistance = d;
    bestCandidate = c;
    }
    }
    return bestCandidate;
    }

    function distance(a, b) {
    var dx = a[0] - b[0],
    dy = a[1] - b[1];
    return Math.sqrt(dx * dx + dy * dy);
    }

泊松盘采样与前面两个算法最大不同在于,它是充分利用现有采样点逐步生成新的采样点,而不是在整个采样区域随机生成新的采样点。同时也注意到,任意两个采样点的最小距离都是一定,没有特别靠近的两个点(正如泊松圆盘分布所定义的那样),这些都是由算法的执行过程严格保证的。

Reference

[1]. Liu, L., Boone, A.P., Ruginski, I.T., Padilla, L., Hegarty, M., Creem-Regehr, S.H., Thompson, W.B., Yuksel, C. and House, D.H., 2017. Uncertainty Visualization by Representative Sampling from Prediction Ensembles. IEEE transactions on visualization and computer graphics, 23(9), pp.2165-2178.
[2]. Visualizing Algorithms
[3]. 算法可视化
[3]. 图形算法