Jump to content

    

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

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

 

Да, там 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

?c=a*b

 

Share this post


Link to post
Share on other sites
Гуглите "гомоморфные преобразования"

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

Share this post


Link to post
Share on other sites
мне не диссер на этом писать

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

Если бы это было так просто - то весь инет бы был завален ТАКИМИ программами.

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

 

Т.е. хотя вид картинок может быть разным - топология может быть одна и та же.

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

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

 

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

 

Phiplastic

Edited by Андрей Ефимович

Share this post


Link to post
Share on other sites
Так разработка такой программы и тянет даже не кандидатскую, а на докторскую диссертацию.

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

 

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

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

 

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

 

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

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

 

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

 

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

Share this post


Link to post
Share on other sites
... мне кажется, что есть что-то проще и быстрее, собственно как я и писал в головном топике.

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

Edited by @Ark

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
Двумерное фурье считать, а потом расятигать спектр в соответствии с масштабом и сравнивать позиции пиков.

Прямое "лобовое" решение, вероятно, будет слишком ресурсо-затратным...

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

В общем, как-то так...

Edited by @Ark

Share this post


Link to post
Share on other sites

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() без всяких там МНК и прочих штучик.

ПС. Дополнительные вопросы приветсвуются.

Share this post


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

Сами поняли че написали?

6 матриц по 3 на 3 - это 54 коэффициента.

Или в ваших матрицах только по одному ненулевому члену?

Да и не сможете вы поворотом и перемещением превратить квадрат в трапецию, а это и происходит в оптике.

 

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

Share this post


Link to post
Share on other sites

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

 

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

Edited by Pavia

Share this post


Link to post
Share on other sites

Многомерной статистикой в таких случаях не пользуются?

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

 

 

 

 

 

Share this post


Link to post
Share on other sites
Многомерной статистикой в таких случаях не пользуются?

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

 

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

 

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

Share this post


Link to post
Share on other sites
Многомерной статистикой в таких случаях не пользуются?

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

Пользуются. К примеру вот N-мерным вектором https://habr.com/post/120562/

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

Или вот к примеру с привлечением особых точек https://habr.com/post/320720/

Или можно поднять качество распознавания без особых точек, а чисто используя разложения на собственные числа/вектора (метод компонентного анализа).

http://www.cse.psu.edu/~rtc12/CSE486/lecture32.pdf

 

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

Edited by Pavia

Share this post


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

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

P.S. Не забываем, что речь идет только о плоских объектах.

 

 

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now