算法来分割对象集到一定数量的群体？ [英] Algorithm to split set of objects into certain number of groups?

问题描述

举例来说，说我有个像素的2D阵列（换言之，图像），我想将它们安排成组，以使组的数目将完美加起来一定数量（比如，总项在像素的另一个二维数组）。此刻，我尝试是使用比率和象素的组合，但本上失败任何比完美整数比其它（因此1：2,1：3,1：4，等）。当它失败了，这只是其刻度为整数小于它，所以，例如，以1：2.93的比例尺度将使用1：2的比例与切断图像的一部分。我宁愿不这样做，那么有哪些算法，我可以用不进入矩阵Multipication？我记得看到类似于我在描述第一次提到的东西，但我不能找到它。这是一个NP型问题？

For example, say I have a 2D array of pixels (in other words, an image) and I want to arrange them into groups so that the number of groups will add up perfectly to a certain number (say, the total items in another 2D array of pixels). At the moment, what I try is using a combination of ratios and pixels, but this fails on anything other than perfect integer ratios (so 1:2, 1:3, 1:4, etc). When it does fail, it just scales it to the integer less than it, so, for example, a 1:2.93 ratio scale would be using a 1:2 scale with part of the image cut off. I'd rather not do this, so what are some algorithms I could use that do not get into Matrix Multipication? I remember seeing something similar to what I described at first mentioned, but I cannot find it. Is this an NP-type problem?

举例来说，假设我有一个12×12像素的图片，我想分割成正由米大小正好为64个子图像。通过分析人们可以看到，我可以把它分解成8×2×2子图像，和56 2×1子图像，以获得子图像的该具体数量。所以，换句话说，我会得到使用所有4（8）+56（2）= 144像素的8 + 56 = 64分的图像。

For example, say I have a 12-by-12 pixel image and I want to split it up into exactly 64 sub-images of n-by-m size. Through analysis one could see that I could break it up into 8 2-by-2 sub-images, and 56 2-by-1 sub-images in order to get that exact number of sub-images. So, in other words, I would get 8+56=64 sub-images using all 4(8)+56(2)=144 pixels.

同样，如果我有一个13 13像素的图片，我想正由-M尺寸81个子图像，我需要它分解成4 2×2子图像，76 2 ×1子图像，和1 1×1子图像以获得所需的子图像的具体数量。换句话说，4（4）76（2）+ 1 = 169和4 + 76 + 1 = 81

Similarly, if I had a 13 by 13 pixel image and I wanted to 81 sub-images of n-by-m size, I would need to break it up into 4 2-by-2 sub-images, 76 2-by-1 sub-images, and 1 1-by-1 sub-image to get the exact number of sub-images needed. In other words, 4(4)+76(2)+1=169 and 4+76+1=81.

另一个例子，如果希望由13图像分割同一13成正逐米大小36子图像，我需要14 4×2子图像，7 2乘2子图像，14 2×1子图像，和1 1×1子图像。换言之，8（13）4（10）2（12）+ 1 = 169和13 + 10 + 12 + 1 = 36

Yet another example, if I wanted to split the same 13 by 13 image into 36 sub-images of n-by-m size, I would need 14 4-by-2 sub-images, 7 2-by-2 sub-images, 14 2-by-1 sub-images, and 1 1-by-1 sub-image. In other words, 8(13)+4(10)+2(12)+1=169 and 13+10+12+1=36.

当然，图像不必是正方形，和子图像既不的量，但也不应该是素数。此外，子图像的量应小于在图像中的像素的数目。我可能要坚持两个为子图像，便于翻译一个容量较大的子图像分为多个子图像的宽度和高度的权力，但如果我能找到一种算法，并没有这样做，它会会更好。这基本上就是我试图找到一个算法。

Of course, the image need not be square, and neither the amount of sub-images, but neither should not be prime. In addition, the amount of sub-images should be less than the number of pixels in the image. I'd probably want to stick to powers of two for the width and height of the sub-images for ease of translating one larger sub image into multiple sub images, but if I can find an algorithm which didn't do that it'd be better. That is basically what I'm trying to find an algorithm for.

推荐答案

据我所知，要分割给定大小，的rectabgular图像转换成 N 矩形子图像。让说，你有：

I understand that you want to split a rectabgular image of a given size, into n rectangular sub-images. Let say that you have:

• 尺寸的图像 W * H
• ，并要分割成 N 尺寸的子图像 X * Y

• an image of size w * h
• and you want to split into n sub-images of size x * y

我认为，你想要的是

R = { (x, y) | x in [1..w], y in [1..h], x * y == (w * h) / n }

这是一组对（X，Y），使得 X * Y 等于（W * H）/ N ，其中 / 是整数除法。此外，你可能想借此 X * Y 具有最小周长，即的最小值矩形X + Y 。

That is the set of pairs (x, y) such that x * y is equal to (w * h) / n, where / is the integer division. Also, you probably want to take the x * y rectangle having the smallest perimeter, i.e. the smallest value of x + y.

有关的问题的三个例子：

For the three examples in the questions:

• 拆分一个 12×12 图像分为64个子图像，你得到 R = {（1,2），（2 1）} ，所以你要么64 1×2 子图像，或64 2×1 子图

• splitting a 12 x 12 image into 64 sub-images, you get R = {(1,2),(2,1)}, and so you have either 64 1 x 2 sub-images, or 64 2 x 1 sub-images

拆分一个 13×13 图像分为81个子图像，你HET R = {（1,2），（2 1）} ，所以你要么64 1×2 子图像，或64 2×1 子图

splitting a 13 x 13 image into 81 sub-images, you het R = {(1,2),(2,1)}, and so you have either 64 1 x 2 sub-images, or 64 2 x 1 sub-images

拆分一个 13×13 图像分为36个子图像，你HET R = {（1,4），（2 ，2），（4,1）} ，所以你可以使用36 2×2 子图像（最小周长）

splitting a 13 x 13 image into 36 sub-images, you het R = {(1,4),(2,2),(4,1)}, and so you could use 36 2 x 2 sub-images (smallest perimeter)

对于每一个例子，你当然可以结合矩形的大小不同。

For every example, you can of course combine different size of rectangles.

如果你想做些别的事情，也许的瓷砖的原始图像，你可能想看看的矩形拼接算法

If you want to do something else, maybe tiling your original image, you may want to have a look at rectangle tiling algorithms

这篇关于算法来分割对象集到一定数量的群体？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！