реклама на сайте
подробности

 
 
3 страниц V  < 1 2 3 >  
Reply to this topicStart new topic
> Простой и понятный алгоритм сравнения картинок
thermit
сообщение Sep 3 2018, 18:47
Сообщение #16


Знающий
****

Группа: Участник
Сообщений: 781
Регистрация: 3-08-09
Пользователь №: 51 730



Цитата(iiv @ Sep 3 2018, 14:02) *
Спасибо, что не оставляете наедине с проблемой!

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

Go to the top of the page
 
+Quote Post
Андрей Ефимович
сообщение Sep 3 2018, 19:07
Сообщение #17


Участник
*

Группа: Участник
Сообщений: 61
Регистрация: 30-06-18
Пользователь №: 105 565



Гуглите "гомоморфные преобразования"
Go to the top of the page
 
+Quote Post
iiv
сообщение Sep 3 2018, 20:18
Сообщение #18


вопрошающий
*****

Группа: Свой
Сообщений: 1 726
Регистрация: 24-01-11
Пользователь №: 62 436



Цитата(Андрей Ефимович @ Sep 4 2018, 01:07) *
Гуглите "гомоморфные преобразования"

спасибо, погуглил... Правда ничего не понял. ИМХО, не об этом, но может конечно я что просмотрел и с радостью прочитаю понятно написанную ссылку. Я ж говорю, мне не диссер на этом писать, а тупо малюсенькую и понятную программку написать. Если есть красивая задача, то к ней должно быть красивое решение.
Go to the top of the page
 
+Quote Post
Андрей Ефимович
сообщение Sep 4 2018, 03:20
Сообщение #19


Участник
*

Группа: Участник
Сообщений: 61
Регистрация: 30-06-18
Пользователь №: 105 565



Цитата(iiv @ Sep 3 2018, 23:18) *
мне не диссер на этом писать

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

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

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

Phiplastic

Сообщение отредактировал Андрей Ефимович - Sep 4 2018, 03:15
Go to the top of the page
 
+Quote Post
iiv
сообщение Sep 4 2018, 09:48
Сообщение #20


вопрошающий
*****

Группа: Свой
Сообщений: 1 726
Регистрация: 24-01-11
Пользователь №: 62 436



Цитата(Андрей Ефимович @ Sep 4 2018, 09:20) *
Так разработка такой программы и тянет даже не кандидатскую, а на докторскую диссертацию.

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

Цитата(Андрей Ефимович @ Sep 4 2018, 09:20) *
А их нет. НИ ОДНОЙ.

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

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

Цитата(Андрей Ефимович @ Sep 4 2018, 09:20) *
За всё время я только одну прогу нашёл, который делает что-то подобное, о чём Вы говорите.

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

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

То есть не хочу быть старым пердуном, не способным освоить современный топ-сайнс, поэтому-то и задал этот вопрос.
Go to the top of the page
 
+Quote Post
@Ark
сообщение Sep 4 2018, 11:35
Сообщение #21


Знающий
****

Группа: Участник
Сообщений: 688
Регистрация: 13-05-16
Пользователь №: 91 710



Цитата(iiv @ Sep 3 2018, 14:02) *
... мне кажется, что есть что-то проще и быстрее, собственно как я и писал в головном топике.

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

Сообщение отредактировал @Ark - Sep 4 2018, 12:06
Go to the top of the page
 
+Quote Post
khach
сообщение Sep 4 2018, 11:42
Сообщение #22


Гуру
******

Группа: Свой
Сообщений: 3 439
Регистрация: 29-12-04
Пользователь №: 1 741



Двумерное фурье считать, а потом расятигать спектр в соответствии с масштабом и сравнивать позиции пиков.
Go to the top of the page
 
+Quote Post
@Ark
сообщение Sep 4 2018, 11:59
Сообщение #23


Знающий
****

Группа: Участник
Сообщений: 688
Регистрация: 13-05-16
Пользователь №: 91 710



Цитата(khach @ Sep 4 2018, 14:42) *
Двумерное фурье считать, а потом расятигать спектр в соответствии с масштабом и сравнивать позиции пиков.

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

Сообщение отредактировал @Ark - Sep 4 2018, 12:42
Go to the top of the page
 
+Quote Post
Pavia
сообщение Sep 4 2018, 21:10
Сообщение #24


Участник
*

Группа: Участник
Сообщений: 67
Регистрация: 3-02-14
Из: Интернет
Пользователь №: 80 322



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() без всяких там МНК и прочих штучик.
ПС. Дополнительные вопросы приветсвуются.
Go to the top of the page
 
+Quote Post
AlexandrY
сообщение Sep 5 2018, 05:04
Сообщение #25


Ally
******

Группа: Модераторы
Сообщений: 6 232
Регистрация: 19-01-05
Пользователь №: 2 050



Цитата(Pavia @ Sep 5 2018, 00:10) *
AlexandrY В ваших 9 коэффициентах 3 лишние. Аффинная матрица расскладывается на 6 матриц: трёх поворотов и 3-х перемещений. Откуда 6 степеней свободы.

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

Навигационные алгоритмы также здесь не в тему, поскольку работают с малыми изменениями пространственного положения.
Go to the top of the page
 
+Quote Post
Pavia
сообщение Sep 5 2018, 07:36
Сообщение #26


Участник
*

Группа: Участник
Сообщений: 67
Регистрация: 3-02-14
Из: Интернет
Пользователь №: 80 322



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

Цитата
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
Go to the top of the page
 
+Quote Post
AndreyVN
сообщение Sep 5 2018, 13:05
Сообщение #27


Знающий
****

Группа: Свой
Сообщений: 754
Регистрация: 29-06-06
Из: Volgograd
Пользователь №: 18 458



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




Go to the top of the page
 
+Quote Post
amaora
сообщение Sep 5 2018, 13:21
Сообщение #28


Местный
***

Группа: Участник
Сообщений: 421
Регистрация: 2-01-08
Пользователь №: 33 778



Цитата(AndreyVN @ Sep 5 2018, 16:05) *
Многомерной статистикой в таких случаях не пользуются?
Если'б удалось сопоставить каждой картинке многомерный вектор, то степенью похожести были бы угол между векторами и их модули.


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

Самым интересным решением было бы взять с помощью некого преобразования образы от исходных изображений которые инвариантны аффинному преобразованию. То есть образ не изменяется при поворотах, скосах и сдвигах изображений. Здесь наверно существую подобные решения на тему векторизации изображения.
Go to the top of the page
 
+Quote Post
Pavia
сообщение Sep 5 2018, 13:28
Сообщение #29


Участник
*

Группа: Участник
Сообщений: 67
Регистрация: 3-02-14
Из: Интернет
Пользователь №: 80 322



Цитата(AndreyVN @ Sep 5 2018, 16:05) *
Многомерной статистикой в таких случаях не пользуются?
Если'б удалось сопоставить каждой картинке многомерный вектор, то степенью похожести были бы угол между векторами и их модули.

Пользуются. К примеру вот 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
Go to the top of the page
 
+Quote Post
@Ark
сообщение Sep 6 2018, 10:43
Сообщение #30


Знающий
****

Группа: Участник
Сообщений: 688
Регистрация: 13-05-16
Пользователь №: 91 710



Цитата(amaora @ Sep 5 2018, 16:21) *
Самым интересным решением было бы взять с помощью некого преобразования образы от исходных изображений которые инвариантны аффинному преобразованию. То есть образ не изменяется при поворотах, скосах и сдвигах изображений. Здесь наверно существую подобные решения на тему векторизации изображения.

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

Go to the top of the page
 
+Quote Post

3 страниц V  < 1 2 3 >
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 14th August 2022 - 15:22
Рейтинг@Mail.ru


Страница сгенерированна за 0.01098 секунд с 7
ELECTRONIX ©2004-2016