将一组对象分成一定数量的组的算法？
例如，假设我有一个 2D 像素数组（换句话说，一个图像），我想将它们排列成组，以便组数加起来完美达到某个数字（例如，另一个 2D 中的总项目数）像素阵列）。目前，我尝试的是使用比率和像素的组合，但是除了完美的整数比率（例如 1:2、1:3、1:4 等）之外，这都失败了。当它失败时，它只是将其缩放到小于它的整数，因此，例如，1:2.93 比例比例将使用 1:2 比例，并截掉部分图像。我不想这样做，那么我可以使用哪些不进入矩阵乘法的算法？我记得看到过与我最初提到的类似的东西，但我找不到它。这是一个NP型问题吗？
例如，假设我有一个 12×12 像素的图像，我想将其分割为 64 个 n×m 大小的子图像。通过分析可以看出，我可以将其分解为 8 个 2×2 子图像和 56 个 2×1 子图像，以获得确切数量的子图像。所以，换句话说，我将使用所有 4(8)+56(2)=144 像素获得 8+56=64 个子图像。
同样，如果我有一个 13 x 13 像素的图像，并且想要 81 个 n×m 大小的子图像，我需要将其分成 4 个 2×2 子图像，即 76 个 2×2 子图像。 1 个子图像和 1 个 1×1 子图像以获得所需子图像的确切数量。换句话说，4(4)+76(2)+1=169并且4+76+1=81。
另一个例子，如果我想将相同的 13 x 13 图像分割成 36 个 n×m 大小的子图像，我将需要 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。
当然，图像不必是正方形，子图像的数量也不必是正方形，但都不应该是素数。此外，子图像的数量应小于图像中的像素数。我可能想坚持子图像的宽度和高度的二次方，以便于将一个较大的子图像转换为多个子图像，但如果我能找到一种不这样做的算法，那么它会变得更好。这基本上就是我试图寻找算法的目的。
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?
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.
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.
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.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我知道您想要将给定大小的矩形图像分割为 n 个矩形子图像。假设您有：
w * h的图像n个尺寸为x * y的子图像I认为您想要的是
(x, y)对的集合，使得x * y等于(w * h) / n< /code>，其中/是整数除法。另外，您可能希望采用周长最小的x * y矩形，即x + y的最小值。对于问题中的三个示例：
将
12 x 12图像分割为 64 个子图像，您将得到R = {(1,2),(2,1)}，因此您有 64 个1 x 2子图像，或 64 个2 x 1子图像，
将
13 x 13图像分割成 81 个子图像，你会R = {(1,2),(2,1)}，因此您有 64 个1 x 2子图像，或 64 个2 x 1子图像将
13 x 13图像分割为 36 个子图像图像，您会R = {(1,4),(2,2),(4,1)}，因此您可以使用 362 x 2sub -图像（最小周长）对于每个示例，您当然可以组合不同大小的矩形。
如果您想做其他事情，也许平铺您的原始图像，您可能需要查看矩形平铺算法
I understand that you want to split a rectabgular image of a given size, into
nrectangular sub-images. Let say that you have:w * hnsub-images of sizex * yI think that what you want is
That is the set of pairs
(x, y)such thatx * yis equal to(w * h) / n, where/is the integer division. Also, you probably want to take thex * yrectangle having the smallest perimeter, i.e. the smallest value ofx + y.For the three examples in the questions:
splitting a
12 x 12image into 64 sub-images, you getR = {(1,2),(2,1)}, and so you have either 641 x 2sub-images, or 642 x 1sub-imagessplitting a
13 x 13image into 81 sub-images, you hetR = {(1,2),(2,1)}, and so you have either 641 x 2sub-images, or 642 x 1sub-imagessplitting a
13 x 13image into 36 sub-images, you hetR = {(1,4),(2,2),(4,1)}, and so you could use 362 x 2sub-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
如果您不关心子图像的大小不同，一个简单的方法就是反复将子图像分成两部分。每一次新的分割都会使子图像的数量增加一个。
If you don't care about the subimages being differently sized, a simple way to do this is repeatedly splitting subimages in two. Every new split increases the number of subimages by one.