Простой и понятный алгоритм сравнения картинок Опции

[iiv]

Добрый день,

ищу понятный, легко объясняемый и, по возможности короткий (на одну-две страницы текста) с оптимальной или субоптимальной асимптотически сложностью алгоритм сравнения двух картинок, которые могут соответствовать одному объекту, но аффинно преобразованному, ну то есть как, например, на приложенной ниже картинке. Картинка не моя, взято с доклада "Multiscale analysis of similarities between images on Riemannian manifolds" Coloma Ballester. То есть чтоб на входе было две картинки, а на выходе - коэффициенты аффинного преобразования + величина достоверности в какой-нибудь адекватной метрике. Через риманово преобразование с CNN объяснить и запрограммировать могу, но это - тонна кода. Нужно просто и понятно. У кого-то есть идеи? Буду премного благодарен!

Спасибо!

ИИВ

Эскизы прикрепленных изображений

 

[ViKo]

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

[AlexandrY]

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

По 9-и степеням.

[ViKo]

По 9-и степеням.

Геометрических всего 6 в нашем мире. Вы имеете в виду цвета? Согласен.

[AlexandrY]

Геометрических всего 6 в нашем мире. Вы имеете в виду цвета? Согласен.

А ваш мир плоский или объемный?

[ViKo]

А ваш мир плоский или объемный?

Такой же, как и ваш. А вас механическим дисциплинам каким-нибудь обучали в универе/институте?

[AlexandrY]

Такой же, как и ваш. А вас механическим дисциплинам каким-нибудь обучали в универе/институте?

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

[ViKo]

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

Может быть. Но одно сводится к другому.
Опишите ваши степени свободы.

[AlexandrY]

Может быть. Но одно сводится к другому.
Опишите ваши степени свободы.

Так нет там "свободы", эт я просто применил вашу "свободу" как метафору к коэффициентам матрицы преобразования, которая 3 на 3.

[ViKo]

Так нет там "свободы", эт я просто применил вашу "свободу" как метафору к коэффициентам матрицы преобразования, которая 3 на 3.

Ваша матрица мне непонятна, а степени свободы - понятны. Топикстартер просил просто и понятно.

[@Ark]

Если у ТС не абстрактные картинки, а фотографии реальных предметов с разных ракурсов и расстояний, то, пожалуй, механика (кинематика) будет так же применима, как и проективная геометрия.
У твердого тела шесть степеней свободы. Его положение в пространстве описывается поворотом (3 угловых координаты) и переносом (3 линейных координаты).
Поворот можно представить в виде матрицы преобразования координат 3 x 3. Но у нее только 3 степени свободы - то есть все 9 коэффициентов, можно определить через 3 независимых параметра.

Сообщение отредактировал @Ark - Sep 3 2018, 09:00

[AlexandrY]

Ваша матрица мне непонятна, а степени свободы - понятны. Топикстартер просил просто и понятно.

Тогда самый верный способ - Fuzzy Logic.
Спрашивать на форуме похожи или нет картинки.
Каждому мнению присваивать уровень доверия, а потом выводить дефузификатор.

. Но у нее только 3 степени свободы - то есть все 9 коэффициентов, можно определить через 3 независимых параметра.

Да ну!?
Даже на картинке ТС видна проективность. Причем тут механика?
Я б тогда за оптику агитировал бы.

[@Ark]

Я б тогда за оптику агитировал бы.

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

Сообщение отредактировал @Ark - Sep 3 2018, 09:19

[yes]

а что про это "думают" нейросети?

вроде бы из банальной эрудиции - нужно "разобрать" картинки на объекты/фичи из них уже вычислять преобразование - перебирать, наверно, не получится
начинать, наверно, надо с opencv - может там уже что-то есть...

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

[iiv]

Спасибо, что не оставляете наедине с проблемой!

Да, там 6 степеней свободы, фактически для координаты первой картинки надо найти матрицу и вектор что
координата второй картинки будет выражаться как



С помощью CNN (convolutional neural networks), то есть нейросетей, как я писал выше я это могу сделать, но тут будет тонна кода, который получается довольно тормознутым и плохо ложащимся на маломощные контроллеры. Лет 7 назад я это программировал и у меня это работает, но мне кажется, что есть что-то проще и быстрее, собственно как я и писал в головном топике.

Спасибо!

PS: math->tex поправил, спасибо большое, thermit что подсказали!

[thermit]

Спасибо, что не оставляете наедине с проблемой!

Да, там 6 степеней свободы, фактически для координаты первой картинки [math] x \in \R^2[/math] надо найти матрицу [math] A \in \R^{2 \times 2}[\math] и вектор [math] b \in \R^2[\math] что
координата второй картинки будет выражаться как

[math] y = A x + b[\math]

С помощью CNN (convolutional neural networks), то есть нейросетей, как я писал выше я это могу сделать, но тут будет тонна кода, который получается довольно тормознутым и плохо ложащимся на маломощные контроллеры. Лет 7 назад я это программировал и у меня это работает, но мне кажется, что есть что-то проще и быстрее, собственно как я и писал в головном топике.

Спасибо!

PS: а разве [math] - [/math] на этом форуме не работает, а как тогда в ЛаТеХе формулы вставлять, гифами что-ли????

math tex

[Андрей Ефимович]

Гуглите "гомоморфные преобразования"

[iiv]

Гуглите "гомоморфные преобразования"

спасибо, погуглил... Правда ничего не понял. ИМХО, не об этом, но может конечно я что просмотрел и с радостью прочитаю понятно написанную ссылку. Я ж говорю, мне не диссер на этом писать, а тупо малюсенькую и понятную программку написать. Если есть красивая задача, то к ней должно быть красивое решение.

[Андрей Ефимович]

мне не диссер на этом писать

Так разработка такой программы и тянет даже не кандидатскую, а на докторскую диссертацию.
Если бы это было так просто - то весь инет бы был завален ТАКИМИ программами.
А их нет. НИ ОДНОЙ.

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

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

Phiplastic

Сообщение отредактировал Андрей Ефимович - Sep 4 2018, 03:15

[iiv]

Так разработка такой программы и тянет даже не кандидатскую, а на докторскую диссертацию.

не, лет 20 назад может да, сейчас - далеко нет. Я когда свой кандидатский диссер в 1999 защищал, тогда уже были методы решения таких задач, но компьютерных мощностей не сильно хватало, потом был бум и сделали многое. Как я говорил, в 2011 я по готовым статьям писал конволюционную нейронную сеть и она довольно успешно вычисляла коэффициенты аффинного преобразования... Но - там было много магии - то есть фактов, которые надо было принять на веру без доказательств, да и громадность кода впечатляла!!!

А их нет. НИ ОДНОЙ.

В тензорфлоу и еще куче пакетов этого завались. Вы разве с такими фреймворками не знакомы?

Еще раз повторяю, наука-то вперед движется. Я эти 7 лет совсем этим не занимался, и не смотрел актуальные статьи. На раз найти не удалось, в то же время, такие разпознавалки есть в реально куче фреймворков, да, понятно, вокруг да около графических карт и CUDA, и, часто там пишут, что именно на CNN сделано, но не всегда. Поэтому, давайте вместе не проспим - не знание современного уровня техники не означает, что этого всего нет.

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

я боюсь быть правым, но мне кажется, что тут все делается обычной конволюцией через двухмерное быстрое преобразование Фурье, так как на схемах никто в здравом уме не повернет чертеж на несколько градусов, то есть сравнивать можно только в масштабе (одна координата) и сдвиге (две координаты, решаемые через БПФ). Результирующая вычислительная сложность этого всего получается совсем копеешной. Мне на кандидатском минимуме в 1996 году приходилось выводить формулы для такой двухмерной конволюции, то есть тогда это было что-то обыденное для обычного нормально учащегося студента. Могу на бис повторить, если кому интересно, или дать ссылки, как другие делают.

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

То есть не хочу быть старым пердуном, не способным освоить современный топ-сайнс, поэтому-то и задал этот вопрос.

[@Ark]

... мне кажется, что есть что-то проще и быстрее, собственно как я и писал в головном топике.

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

Сообщение отредактировал @Ark - Sep 4 2018, 12:06

[khach]

Двумерное фурье считать, а потом расятигать спектр в соответствии с масштабом и сравнивать позиции пиков.

[@Ark]

Двумерное фурье считать, а потом расятигать спектр в соответствии с масштабом и сравнивать позиции пиков.

Прямое "лобовое" решение, вероятно, будет слишком ресурсо-затратным...
Я бы попытался для начала сделать декомпозицию обоих рисунков - представить каждый из них в виде множества каких-то отдельных однородных объектов. Потом, неплохо бы определиться - какие из них относятся собственно к предмету, а какие - к фону рисунка. Вероятно, этот процесс должен быть динамическим. Фон, понято, не обязан совпадать, и сравнивать его ни к чему. А потом уже крутить, сжимать/растягивать одно из изображений предмета (а не весь рисунок), и смотреть на сколько он похож на другое изображение, выбрав какой-то критерий похожести. Желательно, чтобы алгоритм был каким-то итерационным, реализующим последовательное приближение к результату, и подсказывающий направление дальнейшего движения. Чтобы избежать тупого перебора всех вариантов.
В общем, как-то так...

Сообщение отредактировал @Ark - Sep 4 2018, 12:42

[Pavia]

AlexandrY В ваших 9 коэффициентах 3 лишние. Аффинная матрица расскладывается на 6 матриц: трёх поворотов и 3-х перемещений. Откуда 6 степеней свободы.
iiv
Ваша задача решена в взад и поперёк.
К примеру:
1) Выделяем особые точки известные как углы. Алгоритм FAST ER . Особых точек в разы меньше фактически задачу сводим от N^2 к N. Далее сопоставляем облака точек простым перебором по 3-углам с поиском минимума с шагом в 10 градусов, алгоритм ICP. Используем метрику подсчитывающую минимальное расстояние между точками находим минимум. Далее через МНК уточняем решение - известны координаты одних точек известны координаты других точек это две матрицы надо найти матрицу перехода. Система переопределённая.
Поэтому применяем сведение к квадратной матрице A*A^T - не помню чей метод.
Каханер, Моулер, Наш.-Численные методы и программное обеспечение-Мир (1998), раздел про МНК

2)
Или второй способ акселерометр. Просто отслеживаете перемещение камеры в пространстве тогда ничего сопоставлять не надо будет.
2.2)Если на борту нет акселерометра, то вычиcлся оптический поток можно так же установить куда переместилась камера.

3) Таки стоит упомянуть способ через фурье. Можно считать свёртку(корреляцию) и для вращения тоже. Далее ищется пик в заданном пространстве.


Насчёт красивого решения, мне вот этот проект нравится http://wiki.ros.org/tum_ardrone хотя возможно не совсем в тему.
А вообще лучше напишите подробнее что у вас за задача? А то может сравнение здесь лишнее. Или напротив можно завести вероятностное дерево решений, оно тогда будет быстрее и без лишних движений одни IF() без всяких там МНК и прочих штучик.
ПС. Дополнительные вопросы приветсвуются.

[AlexandrY]

AlexandrY В ваших 9 коэффициентах 3 лишние. Аффинная матрица расскладывается на 6 матриц: трёх поворотов и 3-х перемещений. Откуда 6 степеней свободы.

Сами поняли че написали?
6 матриц по 3 на 3 - это 54 коэффициента.
Или в ваших матрицах только по одному ненулевому члену?
Да и не сможете вы поворотом и перемещением превратить квадрат в трапецию, а это и происходит в оптике.

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

[Pavia]

Трапецевидное преобразование не относится к аффинным (в игровой индустрии).

6 матриц по 3 на 3 - это 54 коэффициента.
Или в ваших матрицах только по одному ненулевому члену?

Нулевых коэффициентов там больше половины. Но не суть, суть в том что они зависят всего от 6 параметров. X,Y,Z, и 3-х углов вращения вокруг осей Yaw, pitch ,roll.

, а это и происходит в оптике.

В оптике много всего происходит не только аффинное перемещение камеры и/или объекта.
Там есть и перспективные искажения и дисторсия. И трапецевидные из-за неточной установки матрицы в видео-камере.

Аффинные это 6 параметров, матричные 9, внутренние параметры камеры 5 параметров плюс 12 внешние=17 параметров. Число 17 неокончательное, можно уменьшить или увеличить, но пока научных работ никто не делал.

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

Они накопительные. См видео, правда оно выходит за рамки сравнения.
https://www.youtube.com/watch?v=CZiSK7OMANw

Сообщение отредактировал Pavia - Sep 5 2018, 07:52

[AndreyVN]

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

[amaora]

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

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

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

[Pavia]

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

Пользуются. К примеру вот N-мерным вектором https://habr.com/post/120562/
Сравнение можно делать по разному, без хэшей. Другой вопрос что разностное сравнение не самый лучший способ. И тут кто как улучшает показатели
Или вот к примеру с привлечением особых точек https://habr.com/post/320720/
Или можно поднять качество распознавания без особых точек, а чисто используя разложения на собственные числа/вектора (метод компонентного анализа).
http://www.cse.psu.edu/~rtc12/CSE486/lecture32.pdf

ПС. Добавил ещё ссылку.

Сообщение отредактировал Pavia - Sep 5 2018, 16:58

[@Ark]

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

После декомпозиции изображения на множество отдельных объектов, инвариантами будут: некий "усредненный цвет" объекта (конечно, с поправками по освещенности) и особенности контура объекта - углы (угловые точки) и прямые линии (отрезки) контура.
P.S. Не забываем, что речь идет только о плоских объектах.

[Kluwert]

https://courses.graphicon.ru/files/courses/...eatures_web.pdf

[_Vova]

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