Как расположить пиксели попарно по их сходству

Question

я хочу добиться перехода между двумя файлами изображений.Пиксели изображения A перемещаются и перестраиваются, образуя изображение B. Представьте себе облако частиц (которое состоит из пикселей изображения A), которое формируется в изображение B.

До сих пор я думал опросматривают все пиксели на изображении A и сравнивают их с пикселями на изображении B;Наиболее похожие пиксели извлекаются из массивов (с их координатами x, y) и помещаются в другой массив.Итак, в конце у меня есть пары пикселей от обоих изображений, которые похожи.Тогда мне нужно только создать анимацию / возможный баланс цвета (очевидно, что все пары не будут состоять из одинаковых пикселей), что довольно просто.

Проблема в алгоритме, который находит пары пикселей.Для небольшого изображения размером 100px x 100px потребуется 50 005 000 сравнений, для более крупного это будет невозможно.

Разделение изображений на кластеры?Любые идеи будут оценены.

Answer 1

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

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

Answer 2

Возможно, вы захотите взглянуть на Венгерский алгоритм , который уменьшает количество фактических сравнений для 100x100 пикселей до 10000 - и после этого у вас есть O (n ^ 3) времени для нахождения оптимальногоМатчи.По сути, присвойте каждой комбинации пикселей «стоимость» на основе сходства, а затем отправьте (инвертированную) матрицу затрат через алгоритм, чтобы получить оптимальное назначение пикселей от A до пикселей от B.

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

См. Нижнюю часть связанной статьи для реализации на разных языках - это не совсем тривиально для реализации.