Piece together several images into one big image

Question

I'm trying to put several images together into one big image, and am looking for an algorithm which determines the placing most optimally. The images can't be rotated or resized, but the position in the resulting image is not important.

edit: added no resize constraint

Answer 1

Possibly you are looking for something like this: Automatic Magazine Layout.

Answer 2

You are probably looking for SIFT

http://www.cs.ubc.ca/~lowe/keypoints/

http://user.cs.tu-http://www.cs.ubc.ca/~lowe/keypoints/.de/~nowozin/autopano-sift/technicaldetails.html

Answer 3

I created an algorithm for this ones, it's actually a variant of the NP-Hard Bin packing problem, but with a infinite bin size.

You could try to find some articles about it and try to optimize your algorithm, but in the end it will remain a brute force way to try every possibility and try to minimize the resulting bin size.

If you don't need the best solution, but just one solution, you could avoid brute forcing all the combinations. I created a program which did that once too.

Description:

Images: array of the input images
ResultMap: 2d array of Booleans
FinalImage: large image

1. Sort the Images array so that the largest image is at the top.
2. Calculate the total size of your images and initialise the ResultMap so that it's size is 1.5 times the total size of your images (you could make this step smarter for better memory usage and performance). Make the ResultMap the same size and fill it with False values.
3. Then add the first image in the left of your FinalImage and set all the Booleans in ResultMap true from 0,0 until ImageHeight, ImageWidth.

The ResultMap is used to quickly check if you can fit an image on the current FinalImage. You could optimize it to use a int32 and use each bit for one pixel. This will reduce memory and increase performance, because you can check 32 bit's at once (using a mask). But it will become more dificult because you'll have to think about the mask you'll need to make for the edges of your image.

Now I will describe the real loop of the "algorithm".

1. For each image in the array try to find a place were it would fit. You could write a loop which would look trough the ResultMap array and look for a false value and than start to see if it remains false in both directions for the size of the image to place.
   • If you find a place, copy the image to the FinalImage and update the correct booleans in ResultMap
   • If you cand find a place, increase the size of the FinalImage just enough (so look at the edges where the minimal amount of extra space is needed) and also sync that with the ResultMap
2. GOTO 1 :)

It's not optimal, but it can solve the problem in a reasonably optimal way (especially if there are a few smaller images to fill up the gabs in the end).

Answer 4

Appearantly it's called a 'packing problem', which is something frequently used in game programming. For those interested, here are some suggested implementations:

Packing Lightmaps, Rectangle packing and Rectangle Placement

Answer 5

Hi,

In a non-programmatical way, u can use MS Paint feature "Paste From" i.e. Paste a (JPEG) file into the mspaint image area. Using this u can arrange the individual images, and create a final big image and save it as JPEG/GIF/Raw-BMP format.

-AD.

Answer 6

Optimal packing is hard, but there might be simplifications available to you depending on the details of your problem domain. A few ideas:

1. If you can carve up your bitmaps into equally sized tiles, then packing is trivial. Then, on-demand, you'd reassemble the bitmaps from the tiles.

2. Sort your images largest to smallest, then, for each image use a greedy-allocator to select the first available sub-rectangle that fits the image.

3. Use a genetic algorithm. Start with several randomly-selected layouts. Score them based on how tightly they're packed. Mix solutions from the top scoring ones, and iterate until you get to an acceptable score.