Geek Answers Handbook

Combine multiple images with one large image

I am trying to combine several images into one large image and am looking for an algorithm that determines the placement most optimally. Images cannot be rotated or resized, but the position in the resulting image does not matter.

edit: resize limit added

+6
algorithm packing
source share
6 answers

Perhaps you are looking for something like this: Automatic magazine layout .

+3
source share

This is apparently called the "packaging problem", which is often used in game programming. For those who are interested, some suggested implementation options are provided:

Packing Lightmaps , Rectangular Packaging and Rectangle Placement

+2
source share

I created an algorithm for this, this is actually an NP-Hard version of the packaging problem , but with an infinite bin size.

You can try to find some articles about this and try to optimize your algorithm, but in the end it will remain a rude way to try every opportunity and try to minimize the resulting bin size.

If you do not need the best solution, but only one solution, you can avoid rough forcing all the combinations. I created a program that also did this.

Description:

Images: array of the input images ResultMap: 2d array of Booleans FinalImage: large image
  • Sort the "Images" array so that the largest image is at the top.
  • Calculate the total size of your images and initialize the ResultMap so that it is 1.5 times larger than 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.
  • Then add the first image to the left of your FinalImage and set all the boolean values ​​in ResultMap true from 0.0 to ImageHeight, ImageWidth.

ResultMap is used to quickly check if you can put an image in the current FinalImage. You can optimize it for using int32 and use each bit for one pixel. This will reduce memory and increase performance, because you can immediately check 32 bits (using a mask). But it will become more dense because you have to think about the mask that you will need to make for the edges of your image.

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

  • For each image in the array, try to find a place that would be suitable. You can write a loop that will look through the ResultMap array and look for a false value, and then start to see if it remains in both directions by default for the image size.
    • If you find a place, copy the image in FinalImage and update the correct boolean values ​​in ResultMap
    • If you find a place, just increase the size of FinalImage (so look at the edges where the minimum amount of extra space is required), and also synchronize it with ResultMap
  • GOTO 1 :)

This is not optimal, but it can solve the problem in a reasonably optimal way (especially if there are several smaller images at the end to fill in the gabs).

0
source share

Optimal packaging is complex, but there may be simplifications for you depending on the details of your problem domain. A few ideas:

  • If you can split your bitmaps into tiles of the same size, then the packaging is trivial. Then, on demand, you compiled the bitmap images from the tiles.

  • Sort the images with the largest smallest, then use the greedy distributor for each image to select the first available sub-rectangle that fits the image.

  • Use the genetic algorithm. Start with a few randomly selected layouts. Rate them based on how tightly packed they are. Mix the solutions with the top scoring ones and repeat until you get an acceptable result.

0
source share

In the non-software key u, you can use the MS Paint function "Insert from", that is, insert a file (JPEG) into the mspaint image area. Using this, you can organize individual images and create the final large image and save it in JPEG / GIF / Raw-BMP format.

-AD.

-3
source share

More articles:


All Articles