Multiple Image Placement Algorithm - Collage Algorithm

Question

I'm creating an application to display multiple videos concurrently (lets say 2-10 videos). I'm basically looking for an algorithm which can aid in the placement of the videos on the screen. The problem I face is that each video may have a different aspect ratio, and I will obviously need to resize the videos to make them all fit on the screen. But I want to resize and fit them in a way that I maximise the use of the screen (and minimise aspect ratio distortion). In addition I want the user to be able to increase the size of one or more videos so it takes more space on the screen. Thus the algorithm should be stable, in the sense that enlarging one video doesn't make all the placements jump around.

I'm asking this question in a language agnostic way, and the fact I'm using video is irrelevant, this problem applies equally to still images.

So does anyone know of a placement algorithm?

To help clarify here is an example. I have three videos, with the following sizes. I want the first video to take up roughly 50% of the screen, and the last two videos to take up roughly 25% of the screen.

(464, 336) 50%
(624, 480) 25%
(608, 336) 25%

How would I place them on the screen (1024x800) to achieve this? I figured I would first divide the screen in half and best fit the first video in the top half. Then I would divide the bottom half into two and fit both remaining videos as best I can.

thanks in advance

Answer 1

Square root + logic based on rounding. If the remainder of sqrt is < 0.5, round the result down, use the result as rows/cols, and add 1 to either row or col count; if the remainder of sqrt is >= 0.5, round the result up and use it as row/col count.

10 videos = 4x3 (3.16; rounded down, so add 1 row or col)
9 videos = 3x3 (3; abs)
8 videos = 3x3 (2.82; round up)
7 videos = 3x3 (2.64; round up)
6 videos = 3x2 (2.44; round down, so add 1 row or col)
5 videos = 3x2 (2.23; round down, so add 1 row or col)
4 videos = 2x2 (2; abs)
3 videos = 2x2 (1.73; round up)
2 videos = split screen in half vertically or horizontally (however you'd like)
1 video = full screen

Now this is to make all of the videos "square", and, likely the best option because you really can't easily account for the different resolution/ratios which exist out there (unless it's static for you).

So, depending on the ratio of display-resolution to video-resolution, there will padding space around the grid so you'll want the grid to be centered. That said, one option is for you to take that "padding" space and divide it by the number of rows (or cols) and use that as a buffer between videos.

Once you have the row/col count and assuming all the videos are to be the same size, you simply divide screen width by cols and height by rows and you have your video dimensions.

Then, tile the videos onto the screen -- obviously, in same cases, some spots on the grid maybe empty. You can detect what rows and cols that space covers on the grid and center up the videos on that particular row.

If you wish to "maximize" a video then determine ahead of time how much space "maximizing" means. Then, subtract that pixel footprint from the screen resolution before calculating the size of the other videos. If maximizing means 50% of the screen, then, you subtract that video from the number of videos in the grid and subtract 50% of the pixel space from the display resolution.

Answer 2

This is a version of the bin packing problem http://en.wikipedia.org/wiki/Bin_packing_problem which is NP-hard, so you'll want to choose some reasonable heuristic. If you don't want videos to jump around as you resize one, you'll need to leave a bunch of extra dead space or automatically shrink the others.

Unless you have a good reason for allowing it, I'd suggest requiring the aspect ratios to stay fixed.

A suggestion: start by fixing the height of all videos, then use a greedy first fit algorithm to pack them in. The initial height would be an integer fraction of the total screen height. If someone resizes a video, everything else shrinks by the same fraction value and shifts away to accomodate.

Answer 3

I think a Treemap is what you may need.

Good description of the algorithm history here

Ordered quantum treemaps algs, more relevant to your current seach, here

HTH!