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

Question

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

3

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

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

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

我不知道如何快速生成这些允许的子窗口，并且按照正确的分布进行选择，而不是粗暴地评估所有可能的窗口，然后从列表中选择一个。但我非常确信有一种更聪明的方法来解决这个问题，只是我不知道从哪里开始。

谢谢！

- aardvarkk

2个回答

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)
<br>
(Px,Py), (Px+S,Py),(Px,Py+S),(Px+S,Py+S) would define the coordinates of the region

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

1       2       3       4       5
0.60427 0.24523 0.10356 0.03875 0.00819

- frankc

我认为问题在于，如果您选择(Px，Py)接近左上角，那么您将面临与我最初遇到的相同问题：你会有很多“大窗口”可供选择。如果您恰好选择接近右下角的(Px，Py)，那么您更有可能选择较小的窗口。这是一种有趣的方法，但我认为它不是“正确”的。 - aardvarkk

不要删除它！我认为留下这些东西让其他人查看是很好的。感谢您尝试翻译！ - aardvarkk

问题在于我实际上遇到了相反的问题 - 太多的小区域。我的子区域中有60%的区域是大小为1，而建议的分布是45%。 - frankc

抱歉，是的，我在脑海中搞反了...嗯...需要重新思考。 - aardvarkk

这样怎么样：我们知道“左上角”在图像中不是均匀分布的。例如，对于最大可能的窗口，唯一可能的左上值可以是（0,0）。 “左上角”很大程度上被加权，必须位于图像的左上角才能适合窗口。如果您调整算法以选择窗口的“中心”，然后从那里尝试找到窗口大小会发生什么？ - aardvarkk

我认为我的想法通常不起作用，因为它均匀地选择要开始的行和列，但如果分析可能的（行、列、大小）三元组集合，则行和列并不均匀。我认为使这个想法可行的唯一方法是像这样迭代像素，生成所有合法的三元组，并形成一个经验分布函数，然后通过反演变换算法将其用作选择函数。 - frankc

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

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

- Lior Kogan · Accepted Answer

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

通常情况下，对于一个 x∙y 的窗口，大小为 m∙m 的子窗口有 (x-m+1)(y-m+1) 个。

建议的算法：

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

编辑： 实际上你可以做得更好。

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

高度同理。