math tex

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

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

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

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

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

Phiplastic

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

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


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

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


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

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

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

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

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

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

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

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

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

Сами поняли че написали?
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

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

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

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

Пользуются. К примеру вот 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

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