Версия для печати темы

Автор: iiv Sep 2 2018, 16:39

Добрый день,

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

Спасибо!

ИИВ

Автор: ViKo Sep 3 2018, 07:04

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

Автор: AlexandrY Sep 3 2018, 07:11

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

Автор: ViKo Sep 3 2018, 07:37

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

Автор: AlexandrY Sep 3 2018, 08:05

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

Автор: ViKo Sep 3 2018, 08:10

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

Автор: AlexandrY Sep 3 2018, 08:16

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

Автор: ViKo Sep 3 2018, 08:19

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

Автор: AlexandrY Sep 3 2018, 08:23

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

Автор: ViKo Sep 3 2018, 08:34

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

Автор: @Ark Sep 3 2018, 08:53

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

Автор: AlexandrY Sep 3 2018, 08:56

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


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

Автор: @Ark Sep 3 2018, 09:13

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

Автор: yes Sep 3 2018, 10:53

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

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

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

Автор: iiv Sep 3 2018, 11:02

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

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



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

Спасибо!

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

Автор: thermit Sep 3 2018, 18:47

math tex

Автор: Андрей Ефимович Sep 3 2018, 19:07

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

Автор: iiv Sep 3 2018, 20:18

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

Автор: Андрей Ефимович Sep 4 2018, 03:20

Так разработка такой программы и тянет даже не кандидатскую, а на докторскую диссертацию.
Если бы это было так просто - то весь инет бы был завален http://electronix.ru/redirect.php?https://electronix.ru/forum/index.php?s=&showtopic=139351&view=findpost&p=1472611 программами.
А их нет. НИ ОДНОЙ.

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

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

http://electronix.ru/redirect.php?http://www.phiplastic.com/drafts_comparision_ru.html

Автор: iiv Sep 4 2018, 09:48

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


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

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


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

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

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

Автор: @Ark Sep 4 2018, 11:35

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

Автор: khach Sep 4 2018, 11:42

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

Автор: @Ark Sep 4 2018, 11:59

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

Автор: Pavia Sep 4 2018, 21:10

AlexandrY В ваших 9 коэффициентах 3 лишние. Аффинная матрица расскладывается на 6 матриц: трёх поворотов и 3-х перемещений. Откуда 6 степеней свободы.
iiv
Ваша задача решена в взад и поперёк.
К примеру:
1) Выделяем особые точки известные как углы. Алгоритм http://electronix.ru/redirect.php?https://www.edwardrosten.com/work/fast.html . Особых точек в разы меньше фактически задачу сводим от N^2 к N. Далее сопоставляем облака точек простым перебором по 3-углам с поиском минимума с шагом в 10 градусов, алгоритм http://electronix.ru/redirect.php?https://ru.wikipedia.org/wiki/Итеративный_алгоритм_ближайших_точек. Используем метрику подсчитывающую минимальное расстояние между точками находим минимум. Далее через МНК уточняем решение - известны координаты одних точек известны координаты других точек это две матрицы надо найти матрицу перехода. Система переопределённая.
Поэтому применяем сведение к квадратной матрице A*A^T - не помню чей метод.
Каханер, Моулер, Наш.-Численные методы и программное обеспечение-Мир (1998), раздел про МНК

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

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


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

Автор: AlexandrY Sep 5 2018, 05:04

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

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

Автор: Pavia Sep 5 2018, 07:36

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

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

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

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


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

Автор: AndreyVN Sep 5 2018, 13:05

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

Автор: amaora Sep 5 2018, 13:21

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

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

Автор: Pavia Sep 5 2018, 13:28

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

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

Автор: @Ark Sep 6 2018, 10:43

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

Автор: Kluwert Sep 11 2018, 06:22

http://electronix.ru/redirect.php?https://courses.graphicon.ru/files/courses/vision/2012/lectures/cv2012_04_features_web.pdf

Автор: _Vova Sep 18 2018, 06:23

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