зао стт груп
Практическое применение методов ключевых точек

Практическое применение методов ключевых точек

(локальных особенностей)

на примере сопоставления

снимков КА Канопус-В

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

с переменным коэффициентом отражения, техногенных и естественных изменений местности.

 

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

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

Особенности данных космической съемки в задачах сопоставления изображений

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

гео-привязки, кроме того неточное знание рельефа в холмистой местности вносит дополнительную плановую ошибку.

 

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

Разное световое представление одной и той же местности на снимках разных КА

Иллюстрация 1. Разное световое представление одной и той же местности на снимках разных КА.

Блики (отмечены красным) и изменения на местности (зеленым)

Иллюстрация 2. Блики (отмечены красным) и изменения на местности (зеленым).

Локальные особенности

Локальные особенности изображения, которые можно использовать в задачах автоматической обработки (local features), обладают следующими характерными свойствами:

Устойчивость

(робастность)

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

Отличимость

(дискриминантность)

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

Локальность

Особенность занимает небольшую площадь снимка (не районы).

Одним из видов локальных особенностей являются т.н. ключевые точки (в англоязычной литературе - keypoints), обладающие этими свойствами.

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

 

Преимущества применения метода ключевых точек:

 

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

2. Повышение вероятности верного совпадения при умеренном изменении сцены и условий съемки.

3. Найденные совпадения обладают пиксельной и даже субпиксельной точностью.

4. Уменьшение количества вычислений и их оптимизация: сравниваются не полные изображения снимков, а только их фрагменты (окрестности характерных точек).

Адаптация методов машинного зрения к космической съемке

Текущие реализации алгоритмов детекции ключевых точек (FAST, SIFT, SURF) в целом предназначены и оптимизированы под объекты окружающего мира: в большинстве случаев рассматриваются объекты искусственного происхождения, характеризующиеся наличием плоских текстурированных поверхностей, прямых линий и резкими изменениями коэффициента отражения (грани), и т.п., кроме того в них не учитывается влияние атмосферы, «размывающей» границы объектов.

 

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

 

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

Обобщенный алгоритм сопоставления космических снимков с применением методов ключевых точек

Обобщенный алгоритм применения методов ключевых точек для сопоставления космических снимков состоит из следующих шагов:

1. Предварительная обработка снимков.

2. Детекция ключевых точек и вычисление описания окрестностей точек (дескрипторов).

3. Деление снимков на зоны с гарантированным пересечением области.

4. Аппроксимированный поиск похожих дескрипторов в сопоставляемом снимке.

5. Проверка дискриминантности похожих дескрипторов относительно других дескрипторов (фильтр ошибок второго рода).

6. Геометрическая валидация ключевых точек внутри района.

7. Робастное вычисление подходящей геометрической трансформации одного снимка в другой.

Предварительная обработка снимков

На данном этапе производится предварительная обработка исходного снимка для адаптации к алгоритмам детекции ключевых точек. Для большинства получаемых снимков (здесь и далее упоминаются данные космической съемки, полученные КА «Канопус-В») распределение значений яркостей пикселов концентрируется в достаточно узком диапазоне. Выравнивание гистограммы приводит к распределению значений яркостей пикселов по всему задействуемому диапазону (8 бит, или 256 градаций яркости). Такая предобработка деструктивна для снимка, поэтому при дальнейшей обработке (после найденного сопоставления) используется исходный снимок. Более продвинутая предобработка должна быть индивидуальна: нормализация гистограммы яркости проводится в соответствии с референсной гистограммой данной местности и данного сезона года. Снимок ортотрансформируется с учетом ЦМР для устранения влияния ориентации камеры.

Детекция ключевых точек и вычисление дескриптора по окрестностям точки

С математической точки зрения ключевые точки - это точки, являющиеся локальными экстремумами функции яркости, в том числе и после наложения сглаживающих фильтров. Часто ключевые точки определяются как локальный экстремум в матрице, полученной разницей Гауссианов. Значение найденного локального экстремума - отклик (response). Распространенным критерием отбора "хороших" ключевых точек является «отклик» - значение найденного локального экстремума после наложенного сглаживающего фильтра. Однако в случае обработки космической съемки большое значение отклика может быть ложным, поскольку высокий отклик имеют блики, не являющиеся устойчивыми. Поэтому при анализе моделей сопоставления не учитывается значение отклика. Другим критерием отбора ключевых точек является октава гауссовой пирамиды, на которой была произведена детекция. Уровень октавы характеризует площадь, на которой данная точка является локальным экстремумом. Соотношение масштабов сопоставляемых снимков при анализе моделей должно соответствовать соотношению уровней октав.

Вычисление разностей гауссианов (Lowe, 2004)

Иллюстрация 3.

Вычисление разностей гауссианов (Lowe, 2004).

Проверка точки: является ли локальным экстремумов среди 8+9+9 точек на текущей и смежных 3x3 шкалах (scale) (Lowe, 2004)

Иллюстрация 4.

Проверка точки: является ли локальным экстремумов среди 8+9+9 точек на текущей и смежных 3x3 шкалах (scale) (Lowe, 2004).

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

Вычисление дескриптора ключевой точки (Lowe, 2004)

Иллюстрация 5.

Вычисление дескриптора ключевой точки (Lowe, 2004).

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

Пример детектированных ключевых точек
Пример детектированных ключевых точек

Иллюстрация 6. Пример детектированных ключевых точек.

Анализируются тысячи неотфильтрованных моделей совпадений. Задача: учитывая дополнительную информацию о местности, отфильтровать неверные модели

Иллюстрация 7. Анализируются тысячи неотфильтрованных моделей совпадений. Задача: учитывая дополнительную информацию о местности, отфильтровать неверные модели.

Деление снимков на зоны с гарантированным пересечением области

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

 

Размер грани квадрата связан с предельной величиной ошибки привязки (т.е. ошибки несопоставления). Квадрат опорного в сопоставлении изображения должен быть выбран большей площади, так чтобы однозначно существовало решение задачи сопоставления изображений. Таким образом при большей предельной ошибке сопоставления объем анализируемых моделей увеличивается. Более того значительно увеличивается число ложных соответствий, что ухудшает качество анализируемых моделей и в конечном итоге приводит к вырожденному решению.

 

Тем не менее предельная величина ошибки привязки изображений - один из оптимизируемых параметров в анализе моделей сопоставления изображений. Ошибка привязки состоит из двух составляющих: систематической и случайной. При реализации итеративного поиска решения (coarse to fine) можно начинать с действительно больших величин предельной величины ошибки привязки, пропуская неизбежные отсутствия решений, но после первых найденных совпадений, прошедших валидации, следует переинициализировать цикл найденным значением.

Грани квадрата опорного изображения больше граней сопоставляемого снимка на величину предельной ошибки

Иллюстрация 8. Грани квадрата опорного изображения больше граней сопоставляемого снимка на величину предельной ошибки.

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

S сопоставляемого изображения =n2

S опорного изображения = (n+2ε)2

S решения = 4ε2 + 4nε

Иллюстрация 9. отношение площади решения к площади сопоставляемого снимка.

Аппроксимированный поиск похожих дескрипторов в сопоставляемом снимке

Применение точного поиска одинаковых дескрипторов не дает результатов из-за свойства непостоянства местности. Поэтому применяется поиск похожего дескриптора (аппроксимационный поиск). Один из подходов к сравнению похожести дескрипторов состоит в:

 

1. Представлении каждого множества (т.е. каждой окрестности ключевой точки) в виде точки в многомерном пространстве (по количеству элементов в множестве. дескрипторы распространенных алгоритмов детекторов содержат 64 элемента).

2. Вычислении Lp-нормы для каждой многомерной точки.

3. Предположении о похожести окрестностей на основании близости их Lp-норм.

 

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

 

Лучший результат показывает аппроксимированный поиск с помощью k-мерного дерева (k-d tree) разбивающее k-мерное пространство на подпространства таким образом, чтобы каждая точка находилась в своем собственном подпространстве. Важно найти не самый похожий дескриптор (ближайший сосед), а как минимум двух соседов (точки D и B на иллюстрации) для проверки дискриминантности дескрипторов. В итоге для каждой ключевой точки сопоставляемого изображения будет найдено на опорном изображении два ближайших кандидата в пары.

Деления пространства k-мерным деревом (Beis and Lowe 1999)

Иллюстрация 10.

Деления пространства k-мерным деревом (Beis and Lowe 1999).

Проверка дискриминантности похожих дескрипторов относительно других дескрипторов (фильтр ошибок второго рода)

Найденные на предыдущем шаге два похожих дескриптора-претендента в пары (два ближайших соседа) анализируются: выполняется проверка соотношением совпадений (см. Иллюстрацию 12.), после которой отфильтровываются все пары, кроме «доминантных», в которых второй ближайший кандидат в пары к точке на сопоставляемом снимке значительно хуже (дальше в многомерном пространстве). В итоге остается множество пар ключевых точек, образованных выраженным сходством окрестностей.

Пример хороших пар, найденных с помощью аппроксимированного поиска дескрипторов. среди пар еще есть много ложных

Иллюстрация 11.

Пример хороших пар, найденных с помощью аппроксимированного поиска дескрипторов. среди пар еще есть много ложных.

Cимметричная проверка (cross-check) совпадения окрестностей ключевой точки

Иллюстрация 12.

Cимметричная проверка (cross-check) совпадения окрестностей ключевой точки. Если окрестности точки '1' наиболее похожи окрестностям точки 'a', то осуществляется обратная проверка. Если окрестности точки 'a' более всего похожи на окрестности другой точки '2', то и точка '1', и точка 'a' удаляются из моделей сопоставления.

Проверка соотношением совпадений (ratio-check)

Иллюстрация 13.

Проверка соотношением совпадений (ratio-check). Точки, чьи окрестности похожи на несколько других окрестностей, удаляются из модели сопоставления, поскольку не являются характерными.

Геометрическая валидация ключевых точек внутри района

Среди пар ключевых точек, совпадающих по окрестностям, много ложных: около половины. Решение этой задачи методом наименьших квадратов дает неуверенные результаты из-за высокой доли ложных совпадений. Для выявления совпадений среди большинства ложных совпадений применяется статистический алгоритм RANSAC (RANdom SAmple Consensus - консенсус случайных выборок). Реализация алгоритма RANSAC в библиотеке OpenCV осуществляет проверку консенсуса с помощью перспективного преобразования двух плоскостей, в то время как эффективной для рассматриваемого метода является более строгая проверка консенсуса ригидной трансформацией (3 степени свободы вместо 8).

Пример удачной геометрической валидации

Иллюстрация 14.

Пример удачной геометрической валидации: отфильтрованы все ложные совпадения. Красным показаны границы квадрата сопоставляемого снимка, зеленым — границы квадрата опорного снимка.

Геометрическая валидация ключевых точек внутри снимка

Полученные на предыдущем шаге геометрические преобразования применяются ко всем парам ключевых точек для оценки геометрии по площади всего снимка. Отбираются трансформация, имеющая наименьшее значение среднеквадратичного отклонения (СКО).

Робастное вычисление подходящей геометрической трансформации одного снимка в другой

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

Выводы

Рассмотренные алгоритмы и методы были аппробированы в составе стенда главного конструктора КА "Канопус-В". Успешная обработка снимков возможна только при наличии качественных данных, полученных ранее, в том числе и с других КА. Очевидна необходимость инвестировать в уже имеющиеся данные ДЗЗ, что ставит особые задачи по созданию репозиториев гео-даных, в которых изображения хранятся и управляются на всех этапах жизненного цикла по сквозным наборам гео-пространственных аттрибутов.

Библиография

1. Beis and Lowe 1999. Indexing without invariants in 3D object recognition

2. David G. Lowe 2004. Distinctive Image Features from Scale-Invariant Keypoints

Автор: Райченко Борис Валериевич

© АО «СТТ груп» г.Москва 2009–2016

 

info@cttgroup.ru

+7 (495) 545–45–40

Андроновское ш., д. 26, стр. 5