3

我正在开发一个图像处理应用程序，我有一个问题，我想从给定窗口生成一个随机子窗口。例如，给定一个 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 窗口等。

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

谢谢！

4

2 回答 2

3

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

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

推荐算法：

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

编辑：

其实你可以做得更好。

  • 有 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 )

高度也一样。

于 2012-12-04T16:58:07.663 回答
1

我将把它放在这里，即使它不太正确，因为我的模拟表明它很接近，也许我们可以找出缺陷所在。如果无法修复，我将删除它：


1) Generate an Px discretely uninform on 1 to X
2) Generate a Py discretely uniform on 1 to Y
3) let Rx = X - Px + 1, let Ry = Y - Py + 1
4) Let A = Rx * Ry - the remaining area we can fill
5) Generate S discretely uniform on 1:min(Rx,Ry)


(Px,Py), (Px+S,Py),(Px,Py+S),(Px+S,Py+S) would define the coordinates of the region

基本上我只选择子区域的左上角，然后随机选择一个允许的正方形子区域大小，因为我的子区域从 Rx，Ry 位置开始。子区域大小的分布具有正确的递减形状，但过于陡峭（5x5 的 100,000 次迭代）： 

1 2 3 4 5
0.60427 0.24523 0.10356 0.03875 0.00819
于 2012-12-04T19:28:13.020 回答