Algorithm to split set of objects into certain number of groups? -


for example, have 2d array of pixels (in other words, image) , want arrange them groups number of groups add number (say, total items in 2d array of pixels). @ moment, try using combination of ratios , pixels, fails on other perfect integer ratios (so 1:2, 1:3, 1:4, etc). when fail, scales integer less it, so, example, 1:2.93 ratio scale using 1:2 scale part of image cut off. i'd rather not this, algorithms use not matrix multipication? remember seeing similar described @ first mentioned, cannot find it. np-type problem?

for example, have 12-by-12 pixel image , want split 64 sub-images of n-by-m size. through analysis 1 see break 8 2-by-2 sub-images, , 56 2-by-1 sub-images in order exact number of sub-images. so, in other words, 8+56=64 sub-images using 4(8)+56(2)=144 pixels.

similarly, if had 13 13 pixel image , wanted 81 sub-images of n-by-m size, need break 4 2-by-2 sub-images, 76 2-by-1 sub-images, , 1 1-by-1 sub-image exact number of sub-images needed. in other words, 4(4)+76(2)+1=169 , 4+76+1=81.

yet example, if wanted split same 13 13 image 36 sub-images of n-by-m size, need 14 4-by-2 sub-images, 7 2-by-2 sub-images, 14 2-by-1 sub-images, , 1 1-by-1 sub-image. in other words, 8(13)+4(10)+2(12)+1=169 , 13+10+12+1=36.

of course, image need not square, , neither amount of sub-images, neither should not prime. in addition, amount of sub-images should less number of pixels in image. i'd want stick powers of 2 width , height of sub-images ease of translating 1 larger sub image multiple sub images, if can find algorithm didn't it'd better. i'm trying find algorithm for.

i understand want split rectabgular image of given size, n rectangular sub-images. let have:

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

i think want 

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

that set of pairs (x, y) such x * y equal (w * h) / n, / integer division. also, want take x * y rectangle having smallest perimeter, i.e. smallest value of x + y.

for 3 examples in questions:

  • splitting 12 x 12 image 64 sub-images, r = {(1,2),(2,1)}, , have either 64 1 x 2 sub-images, or 64 2 x 1 sub-images

  • splitting 13 x 13 image 81 sub-images, het r = {(1,2),(2,1)}, , have either 64 1 x 2 sub-images, or 64 2 x 1 sub-images

  • splitting 13 x 13 image 36 sub-images, het r = {(1,4),(2,2),(4,1)}, , use 36 2 x 2 sub-images (smallest perimeter)

for every example, can of course combine different size of rectangles.

if want else, maybe tiling original image, may want have @ rectangle tiling algorithms


Comments

Post a Comment