Legacy ImageMagick Discussions Archive

ok, so here's what I got.

I have a given sheet size, lets say 11x17, at 300 dpi, thats about 3300x5100.

Now I need to take images of varying sizes, 300x500, 200x150, 400x800 and place them on the sheet to fill with as little left over space as possible.

So like this:


Now, I'd REALLY like to be able to do this with circular shapes as well, with a bit of padding, but as images aren't circles, I'm wondering if anyone can come up with a method that allows for transparent overlap.

My question is here first so I can see what the community thinks of it, but I do plan on moving it to paid for support if it becomes necessary.

Thanks guys

You will need to composite each image in its proper place using either -compose over -composite or -page -flatten. You will need to compute where each should be placed or if your template already has the correct locations and sizes for the black rectangles, then just measure each upper left corner of the black rectangles. If you want to have circles, each image can include an alpha channel (mask) with the shape of a circle or ellipse which you can create using -draw.

If the images had been laid out in nice rows, you could have used append or montage. But since they are irregularly laid out, you will need to do as above. There is no automatic way to lay them out in such an irregular manner that I know and have as little spacing as possible.

see
http://www.imagemagick.org/Usage/layers/#convert
http://www.imagemagick.org/Usage/layers/#flatten
http://www.imagemagick.org/Usage/draw/#primitives
http://www.imagemagick.org/Usage/compose/#copyopacity

http://www.imagemagick.org/Usage/layers/#append
http://www.imagemagick.org/Usage/montage/

What version of Imagemagick and what platform (I presume Unix variant)


P.S. If you need to figure out the proper locations, you can start by appending the top 3 images from left to right. That will allow you to measure where the corners are for top 3 images and then you can see where the bottoms are located, so you can then composite them all at the correct upper left corner locations. Once you have these locations specified, and if all your other images follow this layout, then you can reuse the coordinates for other images. If they all are going to be different layouts, then you will need to set that up for each set of images. If you have the same layout and all your images are the sizes you have specified, then one layout would work. A script could be created that would check the image size and place that image into the correct location per a template such as above, once the coordinates are known for each corner and size of the image to go into each region.

A script might be able to do this for an arbitrary arrangement, but I would have to think about how to do that by finding for each subsequent image a region where it would fit and not overlap any other image. Offhand, I know of no method to do that in an optimal space conserving manner.

Perhaps you need to clarify your problem further with regard to these issues/questions.

1) Is there a fixed pattern/template?

2) Do you only have a limited number of sizes of images?

3) If totally random number (and size?) of images and a dynamic fit, then what do you want to do if you have more images than will fit on the sheet?

4) Do you have a set of test images that you can provide?

I don't understand what problem is to be solved. If the given images fit on a given sheet then, however they are arranged, exactly the same space (number of pixels) will be left over.

You might be trying to solve some other problem such as:

1. Find an arrangement (if one exists) to fit these given images on this given sheet.

2. Given a collection of images, find the smallest sheet that will contain them.

3. Or something else.

EDIT: Or 4. Given sheets of a given size, and a collection of images, fit them on as few sheets as possible.

I should say that I don't know the solution to any of these. But the first step to finding a solution is to define the problem.

Hey Snibgo,

Your last option, 4, is the optimal solution. take a series of images, all different sizes, and lay them out so they can be put onto a sheet with a fixed size using as little space as possible.

My initial approach to think in terms of free space and used space, and neighbors. so, each pixel would have references to eachother, that would mean putting each pixel of the max-size into an array, each one being indexed. Then applying attributes to it, such was neighbors, Then when I position an image at the top left, I caculate it's total pixel usage and shape, so then each pixel it's using would get attributes of used in the array. then when I goto put the next image in place,I would have to make an array of the same type as the total image, then find (anywhere) within the total image array that matched perfectly (with the exception of the offsets), the image array, then I know the top left, and position it onto the total image and make the matched array from the total image, all set to used.

rinse and repeat until I can't find a matching array.

I'm afraid that this would require a LOT of processing power, as well as some techniques that would be better suited written in C and utilized by the GPU rather than a CPU.

I am hoping that someone else has a cleaner and more efficient solution.

Perhaps you need to clarify your problem further with regard to these issues/questions.

1) Is there a fixed pattern/template?

2) Do you only have a limited number of sizes of images?

3) If totally random number (and size?) of images and a dynamic fit, then what do you want to do if you have more images than will fit on the sheet?

4) Do you have a set of test images that you can provide?

My thought was to simply to sort the images by largest area first. The start with the largest at the top left. Then add each new image from the sorted list (by area) until the first row of images is complete using -mosaic (canvas expanding composite) and does not exceed your base image width. Convert the image to a white on black mask. Then trim the bottom of all white space. Then test each new image from left to right for the first location of a white pixel in the mask and check whether it fits. If it fits, then add it there in the mosaid, If none fit the empty spaces, then start a new row and repeat. Stop when no images can be added once the base image has expanded to your final height. I have not worked out how to test for a fit. Perhaps, crop the mask area corresponding to the tentative fit and test if it is pure white. This may not be optimal, but should be a reasonable and more efficient approach, since it is not testing every permutation of image and locations.

Fred and I are thinking along the same lines.

An overall algorithm might be:

1. Pick an image that hasn't been placed.

2. Place it in the most north-westerly position possible, on the first sheet that it will fit.

3. Repeat steps 1 and 2 until no images remain.

In what order should the images be picked? I don't know. Perhaps in height order, tallest first. Or size order (width * height), largest first.


How do we find "the most north-westerly position possible" for an image? Start with a white canvas. When we place an image, paint those pixels black. Then, to find the most north-westerly position possible:

1. Search the sheet in row order, then column order, for a white pixel.

2. If the image will fit here, end the search. (The test could be: crop that area from the sheet and check that all pixels are white.)

3. Find the next white pixel that is either on the north edge or has a black pixel to its north, AND is either on the west edge or has a black pixel to the its west. (Perhaps this can be optimised more.)

4. Repeat from 2 until we have no more white pixels.

5. Repeat from 1 for the next sheet until the image fits somewhere.

You would need to check at the start that no images were bigger than the sheets. If any are, then obviously no solution is possible.

EDIT: Various optimisations could be made. For example, each sheet could have metadata that gives the largest (W*H) gap remaining. This would be updated each time an image is placed on the sheet. When we pick an image for possible placement on the sheet, we first check against this W*H gap. If the image is larger, then it can't fit, so we don't bother trying.

I suspect this general problem (packing rectangles) has been looked at before. A web-search might be useful.

An interesting method snibgo.

It made me think that a mathematical method might be quicker by getting the image sizes and loading them into an array. This is still to complicated for me but I found an interesting javascript method here: http://codeincomplete.com/posts/2011/5/7/bin_packing/
You would need to link the blocks to the image name in some way.

It seems this problem is called "2D Bin Packing" and there are probably more examples on the internet as snibgo said.

Bonzo, you hit the nail on the head.

That is exactly what I was looking for, though I do need to be able to set a max size limit and I think it's using the basic idea I was thinking about with array's, though far more thought out than I did.

I wonder how difficult it would be to code this out... I'm working on that now. Thanks for pointing it out.

Be careful, I think that code was for sprites that are square and factors of 1/2 in size at each grouping. You seem to need arbitrary sizes and shapes, which is more difficult. I would do as bonzo says and search Google to see if there are more flexible code approaches.

Thanks Fred,

I already did that. I recognized the same issue with the layout as you did, Googled the idea, and found this:

https://github.com/juj/RectangleBinPack

Looked at the logic behind it, and kept digging.

I found that while this does not provide Everything I'd like, it's one hell of a start.

Good. And thanks for the link and the links referenced. Keep us posted. And if you get some code that works, perhaps you might contribute it to IM.