c++ - 如何随机选择空间占用最大化的样本点？

Question

我想生成可以随机填充/覆盖空间的样本点(如附图所示)。我认为他们有一种叫做“准随机”的方法可以生成这样的样本点。但是，这离我的知识有点远。有人可以提出建议或帮助我找到可以做到这一点的图书馆吗？或者建议如何开始编写这样的程序？

在图像中，256 个样本点应用于给定空间，放置在随机位置以覆盖整个给定空间。

更新:我只是尝试使用来自 Halton Quasi-random Sequence 的一些代码并与下面 friend 发布的伪随机结果进行比较。我认为Halton方法的结果更好。我想分享一些结果如下；

我写的代码是

#include "halton.hpp"
#include "opencv2/opencv.hpp"
int main()
{
    int m_dim_num = 2;
    int m_n = 50;
    int m_seed[2], m_leap[2], m_base[2];
    double m_r[100];
    for (int i = 0; i < m_dim_num; i++)
    {
        m_seed[i] = 0;
        m_leap[i] = 1;
        m_base[i] = 2+i;
    }

    cv::Mat out(100, 100, CV_8UC1);
    i4_to_halton_sequence( m_dim_num, m_n, 0, m_seed, m_leap, m_base, m_r);

    int displaced = 100;
    for (int i = 0; i < 100; i=i+2)
    {
        cv::circle(out, cv::Point2d((m_r[i])*displaced, (m_r[i+1])*displaced), 1, cv::Scalar(0, 255, 0), 1, 8, 0);
    }
    cv::imshow("test", out);
    cv::waitKey(0);

    return 0;
}

由于我对 OpenCV 有点熟悉，所以我在 OpenCV (Mat) 的矩阵上绘制了这段代码。 “i4_to_halton_sequence()”是我上面提到的库中的函数。

结果并没有更好，但可能会以某种方式用于我的工作。有人有其他想法吗？

Answer 1

我将给出一个看似半信半疑的答案。然而，该主题已在文献中得到广泛研究，因此我将仅向您介绍维基百科和其他在线地方的一些摘要。

您想要的也称为低差异序列(或准随机，如您所指出的)。您可以在这里阅读更多相关信息:http://en.wikipedia.org/wiki/Low-discrepancy_sequence .它对很多事情都很有用，包括数值积分以及最近模拟视网膜神经节马赛克。

有很多方法可以生成低差异序列(或伪准随机序列 :p)。其中一些在 ACM 算法集 (http://www.netlib.org/toms/index.html) 中。

我认为，其中最常见的称为 Sobol 序列(来自 ACM 事物的算法 659)。您可以在此处获得一些详细信息:http://en.wikipedia.org/wiki/Sobol_sequence

在大多数情况下，除非您真的喜欢它，否则这些东西看起来非常可怕。为了快速获得结果，我会使用 GNU 的 GSL(GNU 科学图书馆):http://www.gnu.org/software/gsl/

该库包含生成准随机序列的代码 (http://www.gnu.org/software/gsl/manual/html_node/Quasi_002dRandom-Sequences.html)，包括 Sobol 序列 (http://www.gnu. org/software/gsl/manual/html_node/Quasi_002drandom-number-generator-examples.html)。

如果您仍然遇到困难，我可以在此处粘贴一些代码，但您最好还是深入研究 GSL。