Какой есть алгоритм для автоматической компоновки нескольких изображений в одно?

Question

[MegaMufa]

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

Нужна программа для этого. Подскажите, есть ли такие программы (язык не важен)? Интересуют исходники, а не сама утилита.

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

Буду благодарен за любые рекомендации.

Answer 1

[Иван Старков]

В составе imagemagik есть прекрасная утилита montage которая позволяет как угодно объединять картинки,
примеры использования тут

Несмотря на кажущуюся простоту - сгенерить можно что угодно, просто объединяя вызовы montage по принципу - вывод одной используется как ввод другой.

Я для генерации составных картинок использую свой скрипт поверх montage который запускает shell команды, или если задача одноразовая то генерю shell script где внутри все выглядит как то так

montage ./images/0.jpg[x${HALF_HEIGHT}] ./images/1.jpg[x${HALF_HEIGHT}] ./images/2.jpg[x${HALF_HEIGHT}] -geometry "${THRD_WIDTH}x<" -gravity center -crop ${THRD_WIDTH}x${HALF_HEIGHT}+0+0 -geometry "+${BORDER}+${BORDER}" ./out/4.html

Comments

[Иван Старков]

могу дать пример оберки для nodejs но через почту

[MegaMufa]

@icelaba Спасибо за совет. Но это немного не то. Меня интересует, не само формирование изображения. Это я умею.
Мне интересен сам алгоритм расчета положения маленьких изображений на общем холсте.

[Иван Старков]

Все зависит от того как хотите расположить, вариантов очень много:
Просто укладка прямоугольных кусков в большой прямоугольник называется "Bin Packing Problem" подробности есть тут: habrahabr.ru/post/136225

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

я недавно как раз генерил картинки выглядят так

img0.solvertour.ru/img/hotels/Mal__divi/Baa_atoll/...

img1.solvertour.ru/img/hotels/Mal__divi/Alifu_Dhaa...

и тп.
Алгоритм простой и по моему он сразу виден если глянуть на примеры.

Answer 2

[Андрей]

Если интересует алгоритмический аспект, то :
1) Это задача об упаковке двумерного ящика (2-dimension bin packing).
2) В общем случае - вычислительная сложность велика, поэтому решают эвристиками
3) Идеально решить не получится - останутся "зазоры"
4) В-общем, выбираете какую-нибудь эвристику (могу предложить пару), а затем немного "растаскиваете" картинки, чтобы вокруг них были равномерные поля, и неразмеченная область не сильно бросалась в глаза.