Практическое применение методов ключевых точек на примере сопоставления снимков со спутника «Канопус-В»

0

Б.В. Райченко, В.В. Некрасов

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

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

ОСОБЕННОСТИ ДАННЫХ КОСМИЧЕСКОЙ СЪЕМКИ В ЗАДАЧАХ СОПОСТАВЛЕНИЯ ИЗОБРАЖЕНИЙ

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

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

Рис. 1. Разное световое представление одной и той же местности на снимках разных КА
Рис. 1. Разное световое представление одной и той же местности на снимках разных КА
Рис. 2. Блики (отмечены красным) и изменения на местности (зеленым)
Рис. 2. Блики (отмечены красным) и изменения на местности (зеленым)

ЛОКАЛЬНЫЕ ОСОБЕННОСТИ

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

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

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

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

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

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

АДАПТАЦИЯ МЕТОДОВ МАШИННОГО ЗРЕНИЯ К КОСМИЧЕСКОЙ СЪЕМКЕ

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

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

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

ОБОБЩЕННЫЙ АЛГОРИТМ СОПОСТАВЛЕНИЯ КОСМИЧЕСКИХ СНИМКОВ С ПРИМЕНЕНИЕМ МЕТОДОВ КЛЮЧЕВЫХ ТОЧЕК

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

  1. предварительная обработка снимков;
  2. детекция ключевых точек и вычисление описания окрестностей точек (дескрипторов);
  3. деление снимков на зоны с гарантированным пересечением области;
  4. аппроксимированный поиск похожих дескрипторов в сопоставляемом снимке;
  5. проверка дискриминантности похожих дескрипторов относительно других дескрипторов (фильтр ошибок второго рода);
  6. геометрическая валидация ключевых точек внутри района;
  7. геометрическая валидация ключевых точек внутри снимка;
  8. робастное вычисление подходящей геометрической трансформации одного снимка в другой.

ПРЕДВАРИТЕЛЬНАЯ ОБРАБОТКА СНИМКОВ

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

ДЕТЕКЦИЯ КЛЮЧЕВЫХ ТОЧЕК И ВЫЧИСЛЕНИЕ ДЕСКРИПТОРА ПО ОКРЕСТНОСТЯМ ТОЧКИ

Рис. 3. Вычисление разностей гауссианов [1]
Рис. 3. Вычисление разностей гауссианов [1]
С математической точки зрения ключевые точки — это точки, являющиеся локальными экстремумами функции яркости, в т. ч. и после наложения сглаживающих фильтров. Часто ключевые точки определяются как локальный экстремум в матрице, полученной разницей гауссианов. Распространенным критерием отбора «хороших» ключевых точек является «отклик» (response) — значение найденного локального экстремума после наложенного сглаживающего фильтра.

Рис. 4. Проверка точки: является ли локальным экстремумом среди 8+9+9 точек на текущей и смежных 3x3 шкалах (scale) [1]
Рис. 4. Проверка точки: является ли локальным экстремумом среди 8+9+9 точек на текущей и смежных 3×3 шкалах (scale) [1]
Однако в случае обработки данных космической съемки большое значение «отклика» может быть ложным, поскольку высокий «отклик» имеют блики, не являющиеся устойчивыми. Поэтому при анализе моделей сопоставления не учитывается значение «отклика». Другим критерием отбора ключевых точек является октава гауссовой пирамиды, на которой была произведена детекция. Уровень октавы характеризует площадь, на которой данная точка является локальным экстремумом. Соотношение масштабов сопоставляемых снимков при анализе моделей должно соответствовать соотношению уровней октав (рис. 3, 4).

 

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

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

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

ДЕЛЕНИЕ СНИМКОВ НА ЗОНЫ С ГАРАНТИРОВАННЫМ ПЕРЕСЕЧЕНИЕМ ОБЛАСТИ

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

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

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

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

 

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

formula

АППРОКСИМИРОВАННЫЙ ПОИСК ПОХОЖИХ ДЕСКРИПТОРОВ В СОПОСТАВЛЯЕМОМ СНИМКЕ

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

  • представлении каждого множества (т. е. каждой окрестности ключевой точки) в виде точки в многомерном пространстве (по количеству элементов в множестве. дескрипторы распространенных алгоритмов детекторов содержат 64 элемента);
  • вычислении Lp-нормы для каждой многомерной точки;
  • предположении о похожести окрестностей на основании близости их Lp-норм.

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

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

 

ПРОВЕРКА ДИСКРИМИНАНТНОСТИ ПОХОЖИХ ДЕСКРИПТОРОВ ОТНОСИТЕЛЬНО ДРУГИХ ДЕСКРИПТОРОВ (ФИЛЬТР ОШИБОК ВТОРОГО РОДА)

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

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

Рис. 10. Пример хороших пар, найденных с помощью аппроксимированного поиска дескрипторов (среди пар пока есть много ложных)
Рис. 11. Симметричная проверка (cross-check) совпадения окрестностей ключевой точки. Если окрестности точки 1 наиболее похожи окрестностям точки a, то осуществляется обратная проверка. Если окрестности точки a более всего похожи на окрестности другой точки 2, то и точка 1, и точка a удаляются из моделей сопоставления.

ГЕОМЕТРИЧЕСКАЯ ВАЛИДАЦИЯ КЛЮЧЕВЫХ ТОЧЕК ВНУТРИ РАЙОНА

Среди пар ключевых точек, совпадающих по окрестностям,много ложных — около половины. Решение этой задачи методом наименьших квадратов дает неуверенные результаты из-за высокой доли ложных совпадений. Для выявления совпадений среди большинства ложных совпадений применяется статистический алгоритм RANSAC (RANdomSAmpleConsensus — консенсус случайных выборок). Реализация

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

алгоритма RANSAC в библиотеке OpenCV осуществляет проверку консенсуса с помощью перспективного преобразования двух плоскостей, в то время как эффективной для рассматриваемого метода является более строгая проверка консенсуса ригидной трансформацией (3 степени свободы вместо 8; рис. 13).

 

 

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

 

ГЕОМЕТРИЧЕСКАЯ ВАЛИДАЦИЯ КЛЮЧЕВЫХ ТОЧЕК ВНУТРИ СНИМКА

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

РОБАСТНОЕ ВЫЧИСЛЕНИЕ ПОДХОДЯЩЕЙ ГЕОМЕТРИЧЕСКОЙ ТРАНСФОРМАЦИИ ОДНОГО СНИМКА В ДРУГОЙ

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

ВЫВОДЫ

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

СПИСОК ЛИТЕРАТУРЫ

  1. David G. Lowe 2004. Distinctive Image Features from Scale-Invariant Keypoints
  2. Beis and Lowe 1999. Indexing without invariants in 3D object recognition