如何随机选择样本点以最大化空间利用率？

Question

如何随机选择样本点以最大化空间利用率？

c++algorithm

7

我希望能够生成可以随机填充/覆盖空间的样本点（就像附图中那样）。我认为他们有一种叫做“准随机”的方法可以生成这样的样本点。然而，这距离我的知识有些远。有人可以提出建议或帮助我找到一个可以实现这个功能的库吗？或者建议如何开始编写这样的程序？

Sample points cover the space

在这张图片中，256个样本点被应用于给定的空间，并随机放置以覆盖整个给定的空间。

更新：我尝试使用Halton准随机序列中的一些代码并与下面朋友发布的伪随机结果进行比较。在我看来，Halton方法的结果更好。我想分享以下一些结果；

Pseudo-random and Halton's sequence

我写的代码是：

#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()"是我提到过的库中的函数。

结果并不是很好，但可能在我的工作中会有所用处。有人有其他想法吗？

- mojiiz

@acheong87谢谢您改善我的语法。 - mojiiz

你的示例图像具有很多对称性 - 这是你需要从解决方案中得到的吗？ - JasonD

你的例子恰好是 Sobol 序列。你是从维基百科上得到的吗？ - thang

@thang 我从其他来源得到了这张图片，不过那个网站链接又是来自维基百科 :p - mojiiz

@JasonD 我只需要点是随机分布在空间的任意区域内。这张图片只是一个示例，方便解释。 - mojiiz

5个回答

3

这里有一种涵盖整个空间的准随机方法。

由于您有256个点可以使用，因此可以将这些点绘制为16x16的网格。

然后应用某些函数来给每个点一个随机偏移量（例如在点的x和y坐标中加上0到±2）。

- kei

0

你可以创建等距点（所有点与它们的邻居之间的距离相同），然后在第二步中，随机移动每个点一点，以使它们看起来“随机”。

我有的第二个想法是：
1. 从一个区域开始。
2. 在您的区域“中心”周围创建一个随机点P rand。
3. 通过该点将区域分成4个区域。 P是左下子区域的右上角，左下角的右上角等等。
4. 对所有4个子区域重复步骤2..4。当然，不是永远，而是直到您满意为止。

此算法确保每个“孔”（即新子区域）都填充了一个点。

更新：由于步骤（2），您的初始区域应该是两倍大，这样可以确保边缘和角落也有点。

- alzaimar

0

这被称为 "低差异序列"。链接的维基页面解释了如何生成它们。

但是我怀疑你已经知道这一点了，因为你的图片与维基百科上的 2,3哈尔顿序列示例非常相似。

- MSalters

请注意，在某些情况下，适当磁盘半径的硬核分布可能会起作用（我并不是说它会更好）。 - Marc Glisse

@MSalters 是的，我知道这是Halton序列图像，就像我之前提到的那样。但是，我的观点是实现步骤对我来说有点困难。我需要一些帮助 :) - mojiiz

-3

你只需要使用库函数 rand() ：

#include <stdlib.h>
#include <time.h>

unsigned int N = 256; //number of points
int RANGE_X = 100; //x range to put sample points in
int RANGE_Y = 100;

void PutSamplePoint(int x, int y)
{
   //some your code putting sample point on field
}

int main()
{
    srand((unsigned)time(0)); //initialize random generator - uses current time as seed
    for(unsigned int i = 0; i < N; i++)
    {
        int x = rand() % RANGE_X; //returns random value in range [0, RANGE_X)
        int y = rand() % RANGE_Y;
        PutSamplePoint(x, y);
    }

    return 0;
}

- Arsenii Fomin

@FominArseniy，感谢您的代码。然而，通过您提供的方法，似乎点并没有覆盖整个块（100x100）。这些点是随机的，但仍然有一些区域是空白的。 - mojiiz

3

这完全是错误的。这个问题要求的与简单的伪随机点完全不同。 - Jan Hudec

为了维护@FominArseniy的权益，实际上问者的意思并不是立即清晰明了的。同时请记住，在我改进问题语法之前，FominArseniy已经回答了这个问题。我可以理解这个问题被解释为用随机点填充空间（但让统计数据填满“整个”空间）。是的，这似乎是一个不太具有挑战性的问题，但我们不能假设问者在这方面有专业知识。 - Andrew Cheong

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- thang · Accepted Answer

我将提供一个看起来有些草率的答案。然而，这个主题在文献中已经被广泛研究，所以我会直接引用一些维基百科和其他在线资源的摘要。

您想要的也被称为低差异序列（或准随机序列，正如您指出的）。您可以在此处阅读更多信息：http://en.wikipedia.org/wiki/Low-discrepancy_sequence。它在很多方面都很有用，包括数值积分和最近模拟视网膜神经节树突阵列。

有许多方法可以生成低差异序列（或伪准随机序列:p）。其中一些在ACM Collected Algorithms（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。