На момент написания этой статьи точный критерий, который мы пытаемся оптимизировать, не был установлен.Но какой бы критерий в конечном итоге не был выбран, может быть полезен следующий эвристический (то есть обычно неоптимальный) подход:
Рассмотрим только небольшое количество «макетов» для объединения небольшого числа прямоугольников в один большийrectangle. Затем рекурсивно рассмотрите способы объединения этих новых прямоугольников в еще большие прямоугольники, используя те же самые несколько макетов, пока не останется только один прямоугольник.
Это не гарантирует оптимального решения, потому чтонекоторые подмножества фотографий ограничены, чтобы сформировать прямоугольники в конечном решении.Но кажется вероятным, что это даст решения приемлемого качества.
Например, для 3 прямоугольников A, B и C рассмотрим следующие 4 макета:
A
B
C
ABC
AB (i.e. A appears on the left)
AC
AA (i.e. A appears on the top)
BC
Кадрирование будет происходить тольков первом туре, когда мы объединяем группы из 3 фотографий.Для этого шага каждое подмножество из 3 фотографий должно быть рассмотрено для каждого из 4 приведенных выше макетов, и для каждого из них должно быть определено оптимальное масштабирование и кадрирование с учетом того, что получаемый прямоугольник может быть увеличен или уменьшен последующими шагами .(Хороший выбор критерия оптимальности должен иметь свойство, чтобы идеальное количество масштабирования и обрезки для каждого из A, B и C при конкретной компоновке не зависело от того, насколько масштабируется результирующий прямоугольник, поэтому это не должно бытьпроблема.)
Последующие раунды объединения будут вести себя аналогично, но без учета обрезки.Для полного решения, раунд 2 будет включать в себя попытку объединить все наборы из 3 прямоугольников, созданных раундом 1, в котором все 9 фотографий различны, однако следование этому подходу приведет к экспоненциальному увеличению.Достаточно сохранить только несколько лучших аранжировок для каждого набора фотографий.Обратите внимание, что важно, чтобы каждая фотография появлялась как минимум в одном из прямоугольников, полученных в каждом раунде.