Algorithm/suggestions for mosaic collage layout of images (like picasa)?

[Jason Veldicott]

Hi,

I am wanting to arrange a collection of images into a collage in the same way as picasa, specifically the "mosaic" style in which images are tiled ie non overlapping, 100% coverage, and no gaps. e.g (http://weddingdish.thinklikeabride.com/wp-content/uploads/2010/10/Frrontporchfarms-collage.jpg). few software programs seem to be able to do this, particularly ones that can be utilised programatically (non interactively). finding an algorithmic solution to this problem would not seem straightforward.

there isn't that much information on the internet about it:

* it relates to the "packing problem" http://en.wikipedia.org/wiki/Packing_problem. although in this case, object size is not fixed, and coverage must be complete. an algorithmic solution to the general 2d packing problem: "Solving the 2D Packing Problem" at http://www.devx.com/dotnet/Article/36005/0/page/1.

* a method for "picture collage" (photo 'stickup' layout) rather than "mosaic collage" is described in research paper titled "Picture Collage" at http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.132.3609&rep=rep1&type=pdf.

it would seem a tree like algorithm for exploring 'mosaic' combinations might be used, in which the rectangles are recursively partitioned. if one combination does't work, then can repeat. conceptually this is simple, but if it is followed through, if rectangles are successfuly partitioned at arbirary points, there are difficulties. one is arriving at boxes that not only allow perfect fit of all images, but that the last box found, fills the last remaining layout space.

would be glad to hear of:

* software that can do this which can be called programatically
* links to any relevant pages
* suggestions as to how an algorithm to do this might work.

thanks

Jason

[ezequiel...@gmail.com]

Hi! I'm working on something similar. Did you find out any solution?

[Vlad Sarella]

Okey, he was approaching problem incorrectly, You can't fit anything into an arbitrary rectangle, it's impossible. For instance imagine you have two squares and you want to fit those into a larger square. Can't do that. No amount of scaling, tweaking will help, they will never fit. I'm sure there's a gazillion other cases like that, not just with squares. Instead you need to allow the surrounding rectangle to change in it's aspect ratio, you can do this by iteratively pairing rectangles into clusters. Here, i can't explain it in words, i made some diagrams:

https://docs.google.com/file/d/0ByMwHA9tTU6GNV9DY3luVDBUbkE/edit?usp=sharing

I can't control yet, the aspect ratio, you can kind of choose which way you want to grow the cluster, vertically or horizontally, but there might be better ways. Right now it just whatever it happens to be, but i DID achieve perfect rectangular packing, the only problem is to figure out the best clustering configuration.

[Jason Veldicott]

Thanks, will have a look.