Алгоритмы для создания мозаики изображений - есть ли более быстрый способ, чем этот?

9

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

Подход на самом деле довольно приятен:

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

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

Проблема с жадностью заключается в том, что в конечном итоге вы кладете самые разные большие пальцы на наименее популярные плитки, независимо от того, совпадают они или нет. Я показываю примеры здесь: http://williamedwardscoder.tumblr.com/post/84505278488/making-image-mosaics

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

Случайный обмен двух плиток не всегда является улучшением, но иногда чередование трех или более плиток приводит к глобальному улучшению, то есть A <-> Bне может улучшиться, но A -> B -> C -> A1может ...

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

Но это требует времени .. Много времени!

Есть ли лучший и быстрый подход?


Обновление Баунти

Я протестировал различные реализации Python и привязки венгерского метода .

Безусловно, самым быстрым был чистый Python https://github.com/xtof-durr/makeSimple/blob/master/Munkres/kuhnMunkres.py

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

Скорость очень зависит от данных; Мона Лиза помчалась через kuhnMunkres.py через 13 минут, но Scarlet Chested Parakeet заняла 16 минут.

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

введите описание изображения здесьвведите описание изображения здесь

(kuhnMunkres.py слева, случайные перестановки справа; исходное изображение для сравнения )

Однако, для изображения Моны Лизы, с которым я тестировал, результаты были заметно улучшены, и у нее фактически была ее определенная улыбка:

введите описание изображения здесьвведите описание изображения здесь

(kuhnMunkres.py слева, случайные перестановки справа)

Будет
источник
1
Относящиеся ... иш. На Codegolf неба было преобразование схожие проблемы.
1
И еще один связанный набор изображений - это allRGB, где каждое изображение (хотя это не дает вам большого намека на то, как это сделать ... просто есть еще одна область, где эта проблема была решена).
1
Я столкнулся с этой проблемой с создателем мозаики несколько лет назад. Я рассуждал тогда и сейчас, что проблема не столько в вашем алгоритме (часть MSE), сколько в ограниченном размере палитры входных изображений. Не имея миллиарда изображений для работы, я подделал его, позволив повторно использовать изображение через некоторое время. Однако, если вы хотите придерживаться своего подхода, может быть целесообразно сделать первый проход для «хороших» подгонок, а затем обработать остальные изображения как случайные (или случайные), с ограниченным набором входных данных, который у вас есть только так много вариантов.
J Trana
@MichaelT спасибо за эту прекрасную ссылку :) Codegolf особенно увлекателен. Я считаю, что решения, получившие наибольшее количество голосов, используют случайные свопы (не случайные повороты) и, по-видимому, работают довольно долго ...
Will
1
Приходите к этому после того, как вы выбрали ответ и получили награду. Другой подход заключается в том, чтобы рассматривать это как проблему имитации отжига . Вы можете использовать SA как один из этапов вашего конвейера решений.
andy256

Ответы:

3

Да, есть два лучших и более быстрых подхода.

  • Более простая проблема: для каждой плитки выберите лучший большой палец (с возможным дублированием). Хорошо, это обман, но может привести только к лучшему визуальному результату.
  • Ваш дубль алгоритмически более интересен и сводится к «проблеме линейного присвоения», при условии, что вы берете MSE в качестве затрат на совпадение, сумма которых должна быть минимальной. Такая проблема может быть решена за полиномиальное время, например, с помощью «венгерского метода»

Затем вы можете скорректировать свои затраты, заменив MSE на более визуально точное расстояние, не меняя основной алгоритм.

YvesgereY
источник
Спасибо! LAP и венгерский метод - вот что мне нужно! Обновление с результатами в вопросе.
Будет
3

Я вполне уверен, что это проблема NP-сложная. Чтобы найти «идеальное» решение, вы должны использовать все возможности исчерпывающе, и это экспоненциально.

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

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


Да, это похоже на то, что вы уже делаете. Дело в том, чтобы забыть волшебный ответ и подумать о двух алгоритмах: сначала заполнить, а затем оптимизировать.

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

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

Вам нужен показатель «благости» и количество времени, которое вы готовы потратить на это и просто поэкспериментировать. Или найти кого-то, кто действительно сделал это.

david.pfx
источник
Вы точно описываете подход, описанный в вопросе ...?
Будет
1

Если последние фишки - ваша проблема, постарайтесь как-то разместить их как можно раньше;)

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

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

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

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

back2dos
источник