[МУЗЫКА] Добрый день! Ранее мы показали, что с помощью двух снимков возможно получение трехмерных координат объектов местности. Если таким образом будут восстановлены пространственные координаты большого количества объектов, мы сможем получить реальную модель местности. Именно поэтому все современные фотограмметрические алгоритмы сконцентрированы на задаче определения тождественных точек на парах фотоснимков. Если автоматически получать наборы тождественных точек на большом количестве фотоснимков, то легко автоматически получать качественные модели местности. На этом и основаны принципы действия всего фотограмметрического ПО. Существуют два основных подхода к отождествлению точек на паре фотоснимков. Первая группа методов называются площадными. Это методы, которые основаны на анализе значений пикселей изображений в пределах области. Эти методы делятся на корреляционные и на методы, основанные на методе наименьших квадратов. Вторая группа методов основана на выделении характерных элементов изображения. В первой группе методов компьютер последовательно сравнивает некоторые фрагменты снимков друг с другом методом последовательного перебора. Этот метод — очень простой в реализации, он не требователен к вычислительным ресурсам. Однако у него есть недостатки. Он работает только в случае идеально качественных снимков без шумов, засветов и при идеальной маршрутной аэрофотосъемке. Любой поворот сразу сломает алгоритм. Мы с вами понимаем, что невозможно добиться идеальной аэрофотосъемки, а значит, площадной метод не сработает практически никогда. Во всех остальных случаях нас спасут методы, основанные на выделении характерных элементов изображения. Методы достаточно разнообразны, но их работу можно свести к некоему унифицированному сценарию из трех этапов. На первом этапе происходит выделение точек, так называемых особых точек, на всех изображениях. Второй этап — это создание дескрипторов, описания этих точек. И третий этап — это сопоставление дескрипторов на разных фотоснимках и отождествление этих точек. Разберемся с каждым этапом подробнее. Что такое «особая точка»? Под особой точкой, как правило, понимают точку, которая значимо и однозначно отличается от фона и от соседних точек. То есть это пиксель цифрового изображения, который мы без труда идентифицируем относительно других пикселей. Математика процесса может быть разная. Существует несколько операторов, которые ищут такие точки: оператор Moravec, оператор Forstner, оператор SIFT. Современные фотограмметрические алгоритмы позволяют на любых фотоснимках автоматически определять и находить тысячи, десятки тысяч и сотни тысяч таких точек, поскольку для компьютера особыми точками является гораздо большее количество, чем для человеческого глаза. После того как мы нашли эти особые точки, их необходимо описать. Под описанием понимается набор данных о точке и ее окружении, который позволяет однозначно сопоставить точку с такой же точкой, но на другом снимке. Создание дескрипторов — процесс, который может быть основан на большом количестве разных алгоритмов, использующих, например, градиенты яркости. После того как мы нашли и описали особые точки, остается последняя задача, сопоставление этих точек. Качество решения задачи сопоставления напрямую зависит от качества поиска точек и от качества описания. Очевидно, что даже при качественном описании на разных снимках могут быть разные условия яркости и освещенности, которые успели поменяться между этими снимками. То есть не все особые точки будут связаны между собой, поэтому и требуется поиск большого количества точек. Если нам удалось сопоставить большое количество дескрипторов на двух изображениях, то задача считается решенной. Вернемся немного к теории и вспомним, что для построения точной модели нам необходимо знать параметры снимков. Элементы внутреннего ориентирования нам известны, из элементов внешнего ориентирования нам известны координаты точки фотографирования. Они определены из GNSS-измерений. С помощью поиска особых точек мы сможем определить угловые элементы внешнего ориентирования и элементы взаимного ориентирования снимков. То есть после поиска и сопоставления мы знаем все необходимые значения для того, чтобы построить модель местности по снимкам. Отметим, что модель будет иметь правильный масштаб, так как координаты снимков определены в геодезической системе. Давайте поговорим про SIFT-алгоритм. Его появление действительно изменило цифровую фотограмметрию и компьютерное зрение. SIFT — scale-invariant feature transform, в переводе «масштабно-инвариантная трансформация признаков», он был запатентован Дэвидом Лоу в 1999 году. Этот алгоритм нашел широкое применение для создания панорам, создания стереоизображений, реконструкции трехмерного объекта по его двухмерным фотографиям, слежения за движением объекта и распознавания объектов. Человеческий мозг достаточно легко может сопоставить два изображения и сообщить, что на изображениях один и тот же объект, сфотографированный с разных ракурсов. Однако стоит принимать во внимание, что для вычислительной машины изображение — это набор ни о чем не говорящих единиц и нулей, организованных в каком-то порядке. Как мы уже упоминали, можно сравнивать изображения кусками или отдельными точками. Однако на этот процесс оказывается слишком много негативного воздействия от любых неидеальностей на изображениях: смещения объектов, разницы масштабов фотографирования, шумов, динамики освещения и прочих других. И хорошо бы сравнивать изображения не по всем точкам, среди которых есть плохие, а лишь по хорошим, дающим более или менее однозначный результат. Как вы поняли, речь идет о первом этапе, поиске особых точек. Необходимо придумать метод, детектор для извлечения этих особых точек. И по сути мы будем сравнивать не фотографии, а их некие модели, составленные из этих особых точек. Еще раз вспомним цепочку «детектор — присвоение дескриптора — сопоставление — построение модели преобразования». Как происходит поиск особых точек? Основной механизм детектирования — это построение пирамиды гауссианов и разности гауссианов для каждого изображения. Что такое гауссиан? Это изображение, размытое методом Гаусса с использованием функции Гаусса. Это достаточно известный прием, такой инструмент есть, например, в популярном редакторе фотографий Photoshop. Размытие по Гауссу — это тип фильтра размытия изображений, который использует гауссову функцию, которая также выражает нормальное распределение в статистике, для расчета преобразования, применяемого к каждому пикселю изображения. При применении в двух измерениях эта формула создает поверхность, контуры которой представляют собой концентрические окружности с гауссовым распределением от центральной точки. Значения из этого распределения используются для построения матрицы свертки, которая применяется к исходному изображению. Новое значение каждого пикселя устанавливается как средневзвешенное значение окрестности этого пикселя. Значение исходного пикселя получает наибольший вес, имеющий наибольшее значение Гаусса, а соседние пиксели получают меньший вес при увеличении их расстояния до исходного пикселя. Это приводит к размытию, которое сохраняет границы и края лучше, чем другие, более однородные фильтры размытия. Понятно, что степень размытия мы можем менять и строить бесконечное количество гауссианов изображения. Разностью гауссианов называют изображение, полученное путем попиксельного вычитания одного гауссиана исходного изображения из гауссиана с другим радиусом размытия. Точка считается особой, если она является локальным экстремумом разности гауссианов. В каждом изображении из пирамиды ищутся точки локального экстремума. Каждая точка текущего изображения сравнивается с ее восемью соседями и девятью соседями, находящимися на уровень выше и ниже в пирамиде. Если эта точка больше или меньше всех соседей, то она принимается за точку локального экстремума. Далее после нахождения точек необходимо отфильтровать их и уточнить. Для этого последовательно вычисляют координаты точек с субпиксельной точностью путем математических преобразований определяется, правильно ли была взята точка, или нужно сместиться от нее в некотором направлении. Также применяя математические преобразования, можно определить контрастность. Если она небольшая, то точка выкидывается, если точка находится на границе объектов или она плохо освещена, то из дальнейших вычислений ее также исключают. После того как мы убедились, что какая-то точка является ключевой для нас, можно вычислить ее ориентацию. Направление ключевой точки вычисляется, исходя из направлений градиентов точек, соседних с особой. Все вычисления градиентов производятся на изображении в пирамиде гауссианов с масштабом, наиболее близким к масштабу ключевой точки. Теперь, зная, что какая-то точка — особая, перейдем к построению дескриптора. Как уже ранее было сказано, дескриптор — это некая информация об окружении особой точки. Это сделано по понятным причинам. Искажения, о которых мы говорили: изменение положения объекта на картинке, изменение сцены, перекрытие одного объекта другим, поворот, оказывают на маленькие области минимальное влияние или не оказывают его вовсе. В методе SIFT дескриптором является вектор. Как и направление ключевой точки, дескриптор вычисляется на гауссиане, ближайшем по масштабу к ключевой точке, и исходя из градиентов в некотором окне ключевой точки. На изображении приведен пример дескриптора точки с размерностью 2*2*8, где первые две компоненты — это количество регионов, не пикселей, в регионе может быть несколько пикселей, по горизонтали и вертикали. Третья цифра означает количество компонент гистограмм этих регионов. Дескриптор ключевой точки состоит из всех полученных гистограмм. Размеры дескриптора на рисунке — 32 компоненты, мы перемножаем два на два и на восемь. Но на практике чаще всего используются дескрипторы размерностью 128 компонент, то есть 4*4*8. После того как мы нашли точки и правильным образом их описали, остается только сопоставить их на разных изображениях. Для этого используется метод поиска Best bin first, BBF, который может идентифицировать ближайшего соседа с большой вероятностью, используя лишь ограниченное количество вычислений. После сопоставления изображений остается только рассчитать координаты точек, используя формулы из фотограмметрии. В результате будет получено облако точек, модель местности с правильными координатами. О том, что происходит дальше, мы говорим позднее. Помимо алгоритма SIFT, есть и другие реализации решения подобных задач. Во-первых, это различные вариации самого алгоритма SIFT, такие как RIFT PCA-SIFT. Также стоит упомянуть метод SURF, «устойчивые ускоренные признаки», speeded up robust features, и метод KAZE. Последний является относительно новым методом и получил широкую популярность вследствие того, что распространяется свободно и имеет открытые исходные коды.
