Сравнение изображений

[prim.ko 3]

Приветствую!

Думаю я обращусь по адресу со следующей задачей:

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

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

Попробовал реализацию хэшем:

Слева направо - изображение полученное объектом, изображение из Google maps

расстояние = 15

 

Слева направо - Google maps, Yandex maps

Расстояние = 7

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

 

Второй вариант который я попробовал это контурный анализ при помощи Hu моментов:

Подал на вход сегментированное сетью изображение, в котором белым залит класс "вода". Затем подал векторную карту в качестве шаблона. Получилось не очень хорошо. Алгоритм выделил контур в самой нижней части изображения (окно find).

Если подать на вход маску а не изображение совмещенное с результатами сегментации, то вроде бы как алгоритм срабатывает:

Немного не то нашел, ну да ладно. Близко.

Минус данного алгоритма в том, что если у меня будет множество шаблонов, скажем это будут все озера и реки в округе, и я стану сравнивать изображение на котором не полностью уместилось в кадр озеро или река, то ничего хорошего не выйдет из этого, так как контур не полностью замкнет водную поверхность. Что посоветуете в данной ситуации? Только не нужно вопросов про GPS, на то оно и тех. зрение, для того и спрашиваю совета на данном форуме.

 

[Nuzhny 243]

Представь, что будет зимой, осенью, в дождь. Я бы начал с ключевых точек и сопоставления их дескрипторов (SIFT, например). В качестве ускорения, дескрипторы для карт тоже можно вычислить заранее. Но и у этого способа есть свои недостатки, если применять его в лоб: найти точки на снимке, найти точке на участке карты и сопоставлять тем же RANSAC. Недостатки:

1. Точек может быть слишком мало. В этом случае надо использовать другой метод, те же контуры (если они есть).

2. Может быть слишком много похожих объектов, у точек будет несколько матчей в обе стороны. Чаще всего такие матчи просто выбрасывают, как недостоверные. Альтернативный способ - представлять точки как биполярный взвешенный граф и искать в нём максимальный поток (кажется так).

3. Часто карта может по времени не соответствовать снимку: появились/исчезли здания, дороги. В данном случае ищут не одну гомографию, а выделяют области точек, для каждой из которых находится неплохая гомография. И уже эти гомографии как-нибудь проверяют на истинность.

Я бы использовал несколько методов, выбор в пользу одного из них делал исходя из данных. Зима/лето, город/поле, горы. Всё это очень разные случаи и почти наверняка разные алгоритмы будут показывать себя лучше/хуже в каждом из конкретных случаев.

[prim.ko 3]

Применимость зимой я не рассматривал как раз из-за низкой корреляции.

6 часов назад, Nuzhny сказал:

1. Точек может быть слишком мало. В этом случае надо использовать другой метод, те же контуры (если они есть).

В примере с контуром, который не замкнут как будет производиться сравнение? Ведь моменты дадут нам много совпадений.

Тут нейронка может дать существенный прирост информации для существующих/модифицированных алгоритмов?

[Nuzhny 243]

Контуры можно сравнивать и напрямую, без использования моментов.

И да: нейронки дадут больше.

[mrgloom 242]

Задача не ясна. Пары изображений заданы заранее?

 

p.s. Есть такая штука

http://www.terrapattern.com/

https://github.com/CreativeInquiry/terrapattern

[Nuzhny 243]

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

Если у топикстартера задача аналогичная, то terrapettern ему не поможет.

[mrgloom 242]

А какая точность достижима?

Тут вот например пишут про погрешность при определении центра фотографирования, но не пишут про то как эта погрешность потом будет влиять на привязку ортофотоплана сгенерированного Photoscan'ом.

http://gisinfo.ru/techno/photoscan.htm

[Nuzhny 243]

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

Зависело от ситуации, короче. Фотоскан решает несколько иную задачу.

[prim.ko 3]

В 17.04.2017 at 15:27, mrgloom сказал:

Задача не ясна. Пары изображений заданы заранее?

 

p.s. Есть такая штука

http://www.terrapattern.com/

https://github.com/CreativeInquiry/terrapattern

Задача первичная стоит не в сопоставлении фотоснимков, а в определении геопозиции объекта. Сопоставление пар кадров - это метод решения данной задачи, который первым пришел мне в голову. Какую информацию будем загружать в объект - здесь нет ограничений, пока не найдено оптимальное решение. 

[prim.ko 3]

Вечер добрый.

Хочу поделится тем, что у меня не получается в данной задаче.

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

В качестве подложки использую векторную карту местности. Векторную карту я разбиваю на тайлы 256*256 объединяя их в слои  пирамиды, в которой кол-во слоев высчитываю как  |log2(max(max(H,W), 256)/256|+1
H,W у меня размеры векторной карты.
Далее я вычисляю для каждого тайла каждого уровня hu moments, сохраняю информацию на диск.

Обучил нейронку на спутниковых снимках, скармливаю ей изображения с бла.
hu moments  сегментированного изображения сравниваю с каждым тайлом выбранного слоя в пирамиде, используя евклидову метрику. Слой в пирамиде выбираю основываясь на высоте бла
Все хорошо, если изображение с бла совпадает с фрагментом из векторной карты, но когда изображение с бла "пересекает" несколько фрагментов из векторной карты, ничего хорошего не получается. Какие есть мысли по поводу всего этого? Как это победить?
На примере красным - положение бла, зеленым - вычисленная позиция.
 

[Nuzhny 243]

А ты можешь в каждом тайле нарисовать евклидову метрику, которая получается?

[prim.ko 3]

Да, если ты имеешь ввиду значения между текущим кадром с бла и всеми тайлами векторной карты. Как это поможет?

[Nuzhny 243]

Да, именно это. Можно попробовать за положение тайла брать взвешенное значение окрестных к максимуму тайлов. Веса - как раз твоя метрика.

[prim.ko 3]

18 часов назад, Nuzhny сказал:

Да, именно это. Можно попробовать за положение тайла брать взвешенное значение окрестных к максимуму тайлов. Веса - как раз твоя метрика.

Криво, но сделал в большом разрешении.

Взято три итерации. На каждой итерации красное окно сдвигалось на 50 pix. 

#1
current min distance:
0.0

#2
current min distance:
0.0001358896369232954

#3
current min distance:
0.00016839950091911252

 

Взвешивать средним?

[mrgloom 242]

А из чего это следует |log2(max(max(H,W), 256)/256|+1  ?

Похоже что в таком идеальном случае можно сравнивать через template matching или chamfer matching.

На кагле кстати была задача по сегментации спутниковых фотоснимков https://www.kaggle.com/c/dstl-satellite-imagery-feature-detection

 

p.s. задача интересная, держите нас в курсе.

[Nuzhny 243]

Я ожидал увидеть значения метрики в каждом из тайлов. Найти минимум, значения метрики в тайлах рядом. Если они совсем большие, то не учитывать. С остальными взвешивать.

Например, минимальная метрика равна n1 = 0.001, у соседа справа n2 = 0.002. У остальных соседей больше 0.1, т.е. больше некоторого порога, всех их не учитываем.

Тогда получим координаты:

x = x1 * (1 - n1 / (n1 + n2)) + x2 * (1 - n2 / (n1 + n2))

y = y1 * (1 - n1 / (n1 + n2)) + y2 * (1 - n2 / (n1 + n2))

Как-то так.

[prim.ko 3]

1 час назад, Nuzhny сказал:

Я ожидал увидеть значения метрики в каждом из тайлов. Найти минимум, значения метрики в тайлах рядом. Если они совсем большие, то не учитывать. С остальными взвешивать.

Например, минимальная метрика равна n1 = 0.001, у соседа справа n2 = 0.002. У остальных соседей больше 0.1, т.е. больше некоторого порога, всех их не учитываем.

Тогда получим координаты:

x = x1 * (1 - n1 / (n1 + n2)) + x2 * (1 - n2 / (n1 + n2))

y = y1 * (1 - n1 / (n1 + n2)) + y2 * (1 - n2 / (n1 + n2))

Как-то так.

В скринах выводится метрика в каждом из тайлов ( сравнивается с текущим кадром ). 
Сейчас остановился на фазовой корреляции. Она дает отличные результаты в качестве "уточнения" области поиска абсолютных координат объекта.

 

2 часа назад, mrgloom сказал:

А из чего это следует |log2(max(max(H,W), 256)/256|+1  ?

Похоже что в таком идеальном случае можно сравнивать через template matching или chamfer matching.

На кагле кстати была задача по сегментации спутниковых фотоснимков https://www.kaggle.com/c/dstl-satellite-imagery-feature-detection

 

p.s. задача интересная, держите нас в курсе.

Если я не ошибаюсь, так работают всякие SASplanet и др. гис системы, при отображении глобальной карты на заданный масштаб. В ods dstl уже спрашивал совета. Оттуда и перенял опыт тренировки UNet и использования ее для данной задачи.

[Nuzhny 243]

18 minutes ago, prim.ko said:

В скринах выводится метрика в каждом из тайлов ( сравнивается с текущим кадром ). 
Сейчас остановился на фазовой корреляции. Она дает отличные результаты в качестве "уточнения" области поиска абсолютных координат объекта.

А, сразу не заметил. А где там находится истинное положение объекта?

Фазовая корреляция - это хорошо. Ещё как вариант можно брать то, что Szeliski называет Parametric motion в своей книге. Оригинал метода описан в статье Lucas-Kanade 20 Years On: A Unifying Framework и называется Inverse Compositional Algorithm. Отличная штука. Это если фазовая корреляция не подойдёт.

Нашёл исходники с Image alignment с помощью инверсного Лукаса-Канаде - вот. И видео с иллюстрацией есть.

[prim.ko 3]

8 минут назад, Nuzhny сказал:

А где там находится истинное положение объекта?

Истинное положение объекта обведено красной рамкой, вычисленное моментами - зеленой рамкой (без всяких улучшений тупым сравниванием ).

Поэтому на первой итерации зеленая рамка перекрывает красную - метрика = 0,0

[Nuzhny 243]

Тогда я проиллюстрирую то, о чём говорил. Берём метрики четырёх тайлов из левого верхнего угла, где находится красный квадрат (у меня там только первые знаки). Взвешенные координаты получились 85 и 91. Не точно, конечно, но и не так плохо.

Для такого метода надо искать не абсолютный минимум в одном тайле, а минимальную сумму из четырёх тайлов, образующих квадрат. При этом значения, которые больше некоторого порога учитывать в этой сумме не надо, как заведомо ложные. Они не должны участвовать ни в поиске минимума из четырёх квадратов, ни в вычислении взвешенной суммы. Если в моём примере взять такой порог за 0.003, то 4-й тайл учитывать не надо и значения получатся ближе к истине: х = 62, у = 70.

[prim.ko 3]

2 часа назад, Nuzhny сказал:

получатся ближе к истине: х = 62, у = 70.

Почему-то у меня выходит 

x= 47.7060367454
y = 60.4724409449

import numpy as np

def calc(tiles_arr, weights, tr):
    res = 0
    weights = np.delete (weights, np.where (weights > tr))

    for i in range (len(weights)):
        res += tiles_arr[i]*(1-weights[i]/(np.sum(weights)))

    return res / len(weights)

weights=np.array([0.0017, 0.0028, 0.00185, 0.00427])
x = [0,256,0,256]
y = [0,0,256,256]

print (calc(x, weights, 0.004))
print(calc(y, weights, 0.004))

 

[Nuzhny 243]

Может быть, я на скорую руку делал.

[prim.ko 3]

В 26.06.2017 at 17:47, Nuzhny сказал:

Фазовая корреляция - это хорошо. Ещё как вариант можно брать то, что Szeliski называет Parametric motion в своей книге.

В общем Inverse compositial - это тоже хорошо, но он бесполезен в условиях сегментации. Наличие общих черт между предыдущим и текущим сегментированным кадром крайне невелико.  При сравнении моментов между сегментированным изображением и векторной картой ничего толкового не выходит 

 

[Nuzhny 243]

Ммм, что фазовую корреляцию, что Лукаса-Канаде надо применять к исходным снимкам, до сегментации. Они полезны в качестве метода доуточнения позиции, найденной моментами.

Про моменты: ты можешь сохранять моменты не только изображений регулярной сетки как сейчас, а ещё и моменты перекрытий?

Другими словами, у тебя сейчас есть плавающее окно размером 256х256 с шагом 256 по вертикали и горизонтали - перекрытий нет, вся площадь покрывается. Может стоит сделать окно 256х256 с шаком 128 по вертикали и по горизонтали? Окон получится в 4 раза больше, но моменты же сравниваются всё равно быстро.

[prim.ko 3]

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

Куда смотреть?

 

На пальцах: увидели объект А класса дом, увидели объект Б класса дом, рассчитали центр масс, сравнили расстояние. ищем что-то похожее в базе