algorithm - 从给定窗口生成离散随机子窗口

Question

我正在处理一个图像处理应用程序，我遇到了一个问题，我想从给定的窗口生成一个随机的子窗口。例如，给定一个 5x5(像素)窗口，我想在 x,y 的给定位置生成一个具有给定宽度和高度的子窗口。目前，可以假设子窗口的宽度和高度始终彼此相等。然而，原始窗口没有此约束。

目前，我只是为我知道适合原始窗口的子窗口生成一个随机宽度/高度。然后我生成一个有效的 x,y 坐标，使该子窗口适合原始窗口。当前方法的问题在于它没有考虑到这样一个事实，即较小的窗口更为丰富，因此更有可能发生。通过为子窗口宽度/高度选择一个随机尺寸，我假设它们在宽度和高度方面的分布是均匀的，但实际上并非如此。

例如，假设我们有一个 5x5 的窗口。有 25 个可能的 1x1 子窗口、16 个可能的 2x2 窗口、9 个可能的 3x3 窗口、4 个可能的 4x4 窗口和 1 个可能的 5x5 窗口。因此，我应该选择概率约为 0.45 (25/(25+16+9+4+1) 的 1x1 窗口、概率约为 0.29 的 2x2 窗口等。

我不确定如何从正确的分布中快速生成这样的允许子窗口，而无需暴力评估所有可能的窗口，然后简单地从列表中选择一个，但我相当确定有一种更聪明的方法来做到这一点，我只是不知道从哪里开始。

谢谢!

Answer 1

对于一个 n∙n 窗口，有 (n-m+1)² 个大小为 m∙m 的子窗口。

一般来说，对于一个x∙y窗口，有(x-m+1)(y-m+1)个大小为m∙m。

推荐算法:

• 对于每个m，计算子窗口的数量；构建这些值的数组。
• 将数组中的值求和，生成一个在该范围内均匀分布的整数
• 将这个整数映射到相关的子窗口大小(使用值映射或范围映射)

编辑:

实际上你可以做得更好。

• 有 1 个宽度为 x 的子窗口，2 个宽度为 (x-1) 的子窗口，... , x 个宽度为 (x-(x -1))。总共有 (1+2+3+...+x)= x(x+1)/2 可能的宽度/水平位置选项。
• 在 [1, x(x+1)/2] 范围内生成一个均匀分布的整数 r。
• 使用以下公式确定宽度:w= x-floor( sqrt(2r-1.75)-0.5 )

高度相同。