Соберите несколько изображений в одно большое изображение - PullRequest
Новая
       43

Соберите несколько изображений в одно большое изображение

6 голосов
/ 24 сентября 2008

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

edit: добавлено ограничение на изменение размера

Ответы [ 6 ]

3 голосов
/ 24 сентября 2008

Возможно, вы ищете что-то вроде этого: Автоматический макет журнала .

2 голосов
/ 24 сентября 2008

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

Упаковочные лайтмапы , Прямоугольная упаковка и Размещение прямоугольника

0 голосов
/ 10 мая 2009

Оптимальная упаковка сложна, но возможны упрощения в зависимости от деталей вашей проблемной области. Несколько идей:

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

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

  3. Используйте генетический алгоритм. Начните с нескольких случайно выбранных макетов. Оценка их в зависимости от того, насколько плотно они упакованы. Комбинируйте решения из лучших, и повторяйте, пока не получите приемлемый результат.

0 голосов
/ 24 сентября 2008

Непрограммным способом вы можете использовать функцию MS Paint «Вставить из», т.е. вставить (JPEG) файл в область изображения mspaint. С его помощью вы можете упорядочить отдельные изображения, создать окончательное большое изображение и сохранить его в формате JPEG / GIF / Raw-BMP.

-AD.

0 голосов
/ 24 сентября 2008

Я создал алгоритм для этого, на самом деле это вариант задачи NP-Hard Бин , но с бесконечным размером бина.

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

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

Описание: 

Images: array of the input images
ResultMap: 2d array of Booleans
FinalImage: large image
  1. Сортируйте массив изображений так, чтобы наибольшее изображение находилось сверху.
  2. Рассчитайте общий размер ваших изображений и инициализируйте ResultMap, чтобы его размер в 1,5 раза превышал общий размер ваших изображений (вы можете сделать этот шаг умнее для лучшего использования памяти и производительности). Сделайте ResultMap такого же размера и заполните его ложными значениями.
  3. Затем добавьте первое изображение слева от FinalImage и установите для всех логических значений в ResultMap значение true от 0,0 до ImageHeight, ImageWidth.

ResultMap используется для быстрой проверки, можете ли вы вписать изображение в текущий FinalImage. Вы можете оптимизировать его для использования int32 и использовать каждый бит для одного пикселя. Это уменьшит память и увеличит производительность, потому что вы можете проверять 32-битные данные одновременно (используя маску). Но это станет более сложным, потому что вам придется подумать о маске, которую вы должны будете сделать для краев вашего изображения.

Теперь я опишу реальный цикл «алгоритма».

  1. Для каждого изображения в массиве попытайтесь найти место, где оно будет подходить. Вы можете написать цикл, который будет выглядеть через массив ResultMap и искать ложное значение, а затем начать проверять, остается ли оно ложным в обоих направлениях для размера изображения, которое нужно разместить.
    • Если вы найдете место, скопируйте изображение в FinalImage и обновите правильные логические значения в ResultMap
    • Если вы найдете место, достаточно увеличить размер FinalImage (посмотрите на края, где требуется минимальное количество дополнительного пространства), а также синхронизируйте его с ResultMap
  2. GOTO 1:)

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

0 голосов
/ 24 сентября 2008
...