Алгоритм множественного размещения изображений - Алгоритм коллажа

Question

Я создаю приложение для одновременного отображения нескольких видеороликов (скажем, 2-10 видео). Я в основном ищу алгоритм, который может помочь в размещении видео на экране. Проблема, с которой я сталкиваюсь, заключается в том, что у каждого видео может быть разное соотношение сторон, и мне, очевидно, нужно будет изменить размер видео, чтобы они все поместились на экране. Но я хочу изменить размер и поместить их таким образом, чтобы я максимально использовал экран (и минимизировал искажение пропорций). Кроме того, я хочу, чтобы пользователь мог увеличить размер одного или нескольких видео, чтобы он занимал больше места на экране. Таким образом, алгоритм должен быть стабильным, в том смысле, что увеличение одного видео не позволяет перемещаться по местам размещения.

Я задаю этот вопрос агностическим языком, и тот факт, что я использую видео, не имеет значения, эта проблема в равной степени относится к неподвижным изображениям.

Так кто-нибудь знает об алгоритме размещения?

Чтобы помочь пояснить здесь, приведен пример. У меня есть три видеоролика со следующими размерами. Я хочу, чтобы первое видео занимало примерно 50% экрана, а два последних видео занимали примерно 25% экрана.

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

Как разместить их на экране (1024x800), чтобы достичь этого? Я решил, что сначала разделил бы экран пополам и лучше всего поместил бы первое видео в верхней половине. Тогда я разделил бы нижнюю половину на две и поместил бы оба оставшихся видео, насколько смогу.

заранее спасибо

Answer 1

Это вариант задачи упаковки в контейнерах http://en.wikipedia.org/wiki/Bin_packing_problem который является NP-трудным, так что вы хотите выбрать какие-то разумные эвристики.Если вы не хотите, чтобы видео перескакивали при изменении размера, вам нужно оставить кучу лишнего мертвого пространства или автоматически сжать другие.

Если у вас нет веской причины для его разрешения, я бы предложил, чтобы соотношение сторон оставалось фиксированным.

Предложение: начните с фиксации высоты всех видеороликов, затем используйте жадный алгоритм первого соответствия, чтобы упаковать их. Начальная высота была бы целой долей от общей высоты экрана. Если кто-то изменяет размер видео, все остальное сжимается тем же значением фракции и сдвигается в сторону.

Answer 2

Квадратный корень + логика, основанная на округление. Если остаток sqrt равен < 0,5, округлите результат вниз, используйте результат в виде строк/столбцов и добавьте 1 к строке или столбцу; если остаток sqrt равен> 0.5, округлите результат и используйте его как количество строк/столбцов.

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 

Теперь это сделать все видео «квадратными», и, вероятно, самый лучший вариант, потому что вы действительно не можете легко объяснить различные разрешения/соотношения, которые существуют там (если это не статический для вас).

Таким образом, в зависимости от соотношения разрешения экрана и разрешения видео, вокруг сетки будет заполнено пространство, поэтому вы хотите, чтобы сетка была центрирована. Тем не менее, один вариант заключается в том, чтобы вы взяли это пространство заполнения и разделили его на количество строк (или столбцов) и использовали это как буфер между видео.

Если у вас есть количество строк/столбцов и предполагается, что все видео должны быть одного размера, вы просто разделите ширину экрана по столбцам и высоте по строкам, и у вас есть размеры видео.

Затем нарисуйте видео на экране - очевидно, в тех же случаях некоторые пятна на сетке могут быть пустыми. Вы можете определить, какие строки и столбцы занимают место на сетке, и центрировать видео в этой конкретной строке.

Если вы хотите «максимизировать» видео, то заранее определите, сколько пространства «максимизирует» означает. Затем вычитайте размер пикселя из разрешения экрана, прежде чем вычислять размер других видео. Если максимизация означает 50% экрана, то вы вычитаете это видео из числа видео в сетке и вычитаете 50% пространства пикселей из разрешения экрана.

Answer 3

Я думаю, что Treemap - это то, что вам может понадобиться.

Хорошее описание истории алгоритма here

упорядоченные квантовые Древовидные карты ALGS, более уместной в текущем поиске делового, here

НТН!