Аннотация
Блохинов Ю.Б., Веркеенко М.С., Скрябин С.В., Андриенко Е.Э. Автоматическое ориентирование неупорядоченного набора перекрывающихся снимков. Приводится описание технологии автоматической обработки неупорядоченного набора снимков с использованием методов цифровой фотограмметрии. Основное внимание уделено методам связывания снимков, а также разработке новых методов ориентирования, не использующих данных о начальном приближении и взаимном расположении снимков. На основе разработанной технологии создан программный комплекс. В заключение представлены результаты работы комплекса для двух наборов снимков, один из которых сделан с БПЛА, другой в процессе наземной съемки. Результаты показывают, что предложенные алгоритмы и схема их совместного использования позволяют производить автоматическую обработку неупорядоченного набора снимков достаточно надежно и с высокой точностью.
Введение
В настоящее время чрезвычайно широкое распространение цифровых камер, повышение мощности компьютеров при их миниатюризации, а также повсеместное использование новых доступных каналов связи с высокой пропускной способностью произвели радикальные изменения в процессе алгоритмической обработки снимков для создания 3D-моделей местности. Возникают новые сложные задачи фотограмметрии и компьютерного зрения, связанные с требованиями полной автоматизации процесса обработки данных. Сегодняшние требования к процессу обработки снимков определяются следующими обстоятельствами.
1. Даже снимки с любительских камер имеют достаточно высокое качество, однако при отсутствии данных калибровки камеры неизвестные параметры калибровки, как правило, включаются в задачу уравнивания фототриангуляционной сети (самокалибровка).
2. Число снимков, которые нужно обрабатывать одновременно, может быть очень велико, достигая сотен тысяч и более.
3. При классической плановой аэрофотосъемке фотографирование местности производится строго упорядоченно, по маршрутам, с заданным перекрытием снимков. Для снимков, полученных с борта БПЛА, с камеры мобильного робота или в ходе наземной съемки, выполненной неподготовленными пользователями, характерны достаточно произвольная ориентация снимков и степень их перекрытия. Наконец рассматривается задача обработки больших коллекций снимков объекта, выложенных в Интернете необученными пользователями, снимавшими разными камерами. В этом случае исходное множество снимков представляет собой совершенно неупорядоченный набор [1-3].
4. Возникли новые области применения фотограмметрической технологии со своими специфическими требованиями [4,5].
5. Для некоторых приложений необходимо решение задачи ориентирования автоматически и в реальном времени как, например, в зрении роботов и навигации беспилотных летательных аппаратов [6].
Процесс создания 3D-моделей местности включает в себя два этапа: 1) ориентирование снимков в единой системе координат; 2) генерацию плотного облака точек, представляющих цифровую модель поверхности. Данная статья посвящена решению первой задачи.
Общая схема решения известна и достаточно отработана [7]. Сначала на исходных изображениях с помощью одного или нескольких операторов отыскивают точки интереса. Для них вычисляются дескрипторы, выбор которых также может определяться особенностями задачи. Путем сравнения дескрипторов связывают пары точек между перекрывающимися парами изображений. Как правило, близости дескрипторов недостаточно для определения соответственных точек, т.к. среди начальных пар имеются ложные соответствия. Для их выявления используются различные фильтры: топологические, метрические, RANSAC [8,9].
Проблема, однако, заключается в том, что для неупорядоченного набора неизвестно заранее какие пары снимков перекрываются и есть ли такие вообще. Таким образом, возникает еще задача определения соответствий снимков. При огромном числе исходных данных пытаться сравнивать все возможные пары из N снимков абсолютно неэффективно, учитывая, что число сочетаний составляет (N(N?1))/2. Существуют, тем не менее, решения задачи, допускающие численную реализацию за разумное время. В предлагаемой работе представлен один из вариантов такого решения.
В статье приводится описание современной технологии обработки неупорядоченного набора снимков с использованием методов цифровой фотограмметрии и компьютерного зрения. Основное внимание уделено методам вычисления и анализу матрицы расстояний между снимками с целью формирования наилучшего графа близости для конечного набора, а также разработке новых методов ориентирования, не использующих данных о начальном приближении и взаимном расположении снимков.
Построение схемы отождествления точек снимков
Поиск точек интереса. Набор связующих точек начинается с генерации точек интереса одного или нескольких типов независимо на всех снимках исходного набора. В данной работе использован детектор SIFT (Scale Invariant Feature Transform) [10].Для каждого снимка по заданным параметрам строится пирамида изображений, на верхнем уровне которой происходит выделение особых точек и построение их дескрипторов. Применение на данном этапе GPU реализации метода SIFT [11] позволяет существенно ускорить вычисления за счет параллельной обработки пикселей при детектировании, и найденных точек при построении дескрипторов. Кроме того, используются смешанные GPU/CPU методы для более быстрой обработки массивов точек. При спуске по пирамиде производится субпиксельное уточнение найденных координат стандартной функцией OpenCV [12]. Полученные в результате точки устойчивы к повороту изображения, его растяжению, а дескрипторы инвариантны к изменениям яркости.
Все вычисления в данном блоке, а также обработка массивов данных и обращение к изображениям, производятся параллельно с помощью открытой библиотеки OpenMP [13].
Предварительный отбор стереопар. Как уже упоминалось при очень большом числе исходных снимков прямое сравнение всех возможных пар практически невозможно. Чтобы сократить количество вычислений на этапе поиска соответствий используется метод «мешка слов» [14,15]. Он позволяет составить список потенциальных стереопар и отбросить те пары изображений, которые заведомо стереопарами не являются.
Под визуальным словом подразумевается кластер достаточно близких друг к другу по значению дескрипторов. Основная идея метода заключается в том, что похожие фрагменты изображений будут соответствовать одним и тем же визуальным словам. Из фрагментов, часто повторяющихся в коллекции снимков, формируется словарь, использующийся в дальнейшем для поиска похожих изображений. По найденным на предыдущем шаге дескрипторам особых точек строится древовидный словарь, общее число слов в котором составляет D=kL , где k — количество ветвей; L — высота дерева (количество уровней). Параметры k и L определяются автоматически из расчета, что для обеспечения хорошего качества поиска число кластеров должно равняться 12% общего числа дескрипторов. Вес слова — характеристика его встречаемости — определяется по TF-IDF метрике.
Далее каждое изображение в коллекции описывается набором визуальных слов. С учетом веса слов рассчитывается матрица расстояний между этими векторами в смысле «мешка слов». Установив пороговое значение для найденных расстояний, можем исключить из рассмотрения пары, содержащие слишком разные наборы дескрипторов.
Все вычисления распараллеливаются при помощи методов описанных в [13], однако есть и другие способы ускорения расчетов на данном этапе. В частности, длительность процедуры создания словаря зависит от того сколько дескрипторов особых точек подается на вход. Расчет по всем найденным методом SIFT точкам займет слишком много времени, что сведет преимущества метода «мешка слов» к нулю. Для того, чтобы сократить количество вычислений используется процедура адаптивного прореживания немаксимумов (adaptive nonmaximal suppression) [16]. В предложенном методе для каждой особой точки вычисляется расстояние до ближайшей точки с более сильным откликом и если это расстояние слишком мало, то точка отбрасывается. Из оставшихся после этой процедуры точек выбирают заранее заданное количество наиболее изолированных, остальные исключаются из рассмотрения. Данная процедура позволяет избежать проблем, связанных с фильтрацией точек только по силе отклика или по их количеству, таких, как отсев достаточно информативных точек либо неравномерное их распределение на изображении, что может сказаться на точности дальнейших вычислений.
На рис. 1 изображен граф близости для набора снимков, вершины которого соответствуют центрам съемки. Рис. 1, а соответствует набору всех возможных пар изображений, рис. 1, б — набору потенциальных стереопар, полученных на этапе предварительного отбора. Как видно из рис. 1, применение метода «мешка слов» позволяет существенно уменьшить количество рассматриваемых пар, и соответственно, ускорить дальнейшие расчеты.
Рисунок 1 – Граф близости для набора снимков:
a — все возможные пары; б — пары, предварительно отобранные методом мешка слов
; в — пары, прошедшие отбор по соответственным точкам и этап фильтрации
Отбор стереопар по набору соответственных точек. Задача анализа и распознавания изображений чрезвычайно сложна и, к сожалению, в большинстве случаев не удается сделать вывод о совпадении контента двух изображений на основе какого-то одного критерия. Так и в данном случае результат работы метода «мешка слов» требует дальнейшей проверки другими методами. По полученному на предыдущем шаге набору предполагаемых стереопар осуществляется поиск пар соответственных особых точек. Для этого применяется алгоритм прямого перебора с использованием критерия Лове [17]. Суть метода заключается в том, что для каждого из дескрипторов проверяется отношение расстояний до двух наилучших кандидатов и если оно оказывается ниже заданного порога, то соответствие отбрасывается. Подобный подход позволяет сократить число ложных соответствий, возникающих в случае, когда рассматриваемые варианты соответственных точек мало отличаются друг от друга. Пары изображений, число найденных соответствий для которых оказалось ниже заданного порога, исключаются из рассмотрения.
Фильтрация ложных соответствий. Как правило, близости дескрипторов недостаточно для достоверного определения соответственных точек, поэтому среди отобранных пар все еще могут быть ложные соответствия. Для их выявления и отбраковки используются различные фильтры [8]. Алгоритм RANSAC (RANdom Sampling Consensus) [18] основывается на робастной оценке параметров модели стереопары по случайным выборкам исходных данных. В реализации, представленной библиотекой OpenMVG [10], для расчета фундаментальной матрицы используется семиточечный алгоритм [19]; он более устойчив к шуму чем нормализованный восьмиточечный и требует меньше выборок исходных данных. После того, как модель стереопары построена проверяется сумма расстояний от соответствующих точек до эпиполярных линий, если она слишком велика — пара отбрасывается.
Данный фильтр не отсеивает случаи, когда соответственная точка лежит на эпиполярной линии, но в другой части изображения. Подобные выбросы могут быть найдены топологическим фильтром [20], который основан на анализе геометрических отношений между точками. Коллинеарность точек и их циклическая нумерация устойчивы к поворотам, сдвигам, аффинным и проективным преобразованиям. Выбирается небольшое подмножество пар точек, проверяются геометрические отношения, отсеиваются выбросы. По прошедшим фильтрацию точкам проверяется оставшаяся часть выборки. Топологический фильтр, в отличие от RANSAC, не учитывает глубину сцены, поэтому для повышения точности используется комбинация этих алгоритмов. На рис. 1, в изображен граф близости, полученный после отбраковки ложных соответствий. Представленные пары снимков действительно содержат перекрытия, а найденные на них соответствующие точки могут быть использованы на этапе ориентирования.
Особенности ориентирования неупорядоченного набора перекрывающихся снимков
В отечественной литературе детально разработаны методы для классической плановой аэрофотосъемки, когда фотографирование местности производится строго упорядоченно по маршрутам с заданным перекрытием снимков [21].
Для широкобазисной и конвергентной съемки нужны новые методы ориентирования, не использующие данные о начальном приближении и структуре съемки. Взаимное ориентирование должно выполняться без задания начального приближения, как при классической аэросъемке. Ориентирование набора снимков осуществляется на основе найденных соответственных точек на всех парах снимков. Основными используемыми алгоритмами ориентирования являются усовершенствованный пятиточечный алгоритм с использованием RANSAC [22,23], ориентирование одиночного снимка по облаку точек [24], уравнивание блока с минимизацией ошибок методом Левенберга– Марквардта [25].
На рис. 2 приведена блок-схема описываемого алгоритма. Перед началом уравнивания на основе найденных соответствий на парах снимков строятся треки точек. Трек – проекция одной и той же точки на нескольких снимках. Для построения треков исходный набор соответствий представляется в виде системы непересекающихся множеств, поиск и объединение точек в треки осуществляется при помощи алгоритма Union-Find [26].
Рисунок 2 – Схема алгоритма уравнивания набора снимков
Первый этап процедуры ориентирования снимка состоит в выборе начальной стереопары. Перебираются все возможные сочетания пар снимков из списка снимков, составленного по результатам предварительного отбора стереопар. Для каждой образованной пары определяется общее количество соответственных точек. Пара, имеющая наибольшее количество таких точек, выбирается в качестве первой стереопары. Выполняется взаимное ориентирование первой стереопары по общим точкам с использованием пятиточечного алгоритма [22,23]. Производится пороговая фильтрация точек при помощи оптимизированного алгоритма RANSAC – ORSA с адаптивным порогом фильтрации [27]. В свободной фотограмметрической системе координат, привязанной к первому снимку, восстанавливаются трехмерные координаты оставшихся точек. Получается трехмерное облако точек.
Начиная с первой стереопары, происходит наращивание блока снимков. Снимки добавляются по одному. Из списка непривязанных снимков выбирается очередной, имеющий наибольшее число общих измеренных точек с трехмерным облаком точек. Производится одиночное ориентирование нового снимка, используя в качестве опоры облако точек [24]. В процессе ориентирования осуществляется фильтрация точек по адаптивному порогу методом ORSA [27]. Перебираются все парные сочетания нового снимка с уже привязанными снимками. Для каждой образованной пары восстанавливаются трехмерные координаты соответственных точек. Если очередная точка не присутствует уже в облаке точек, то она добавляется к нему.
Добавление снимков происходит в несколько этапов. Если на очередном этапе первый добавляемый снимок имел N общих точек с облаком точек, то этап заканчивается после того, как добавлены все снимки, имеющие не меньше pN общих точек, где p — задаваемый порог (0 В статье представлена современная технология автоматической обработки набора неупорядоченных снимков с использованием методов цифровой фотограмметрии и компьютерного зрения. На основе разработанной технологии создан программный комплекс, частично использующий открытые коды библиотек стандартных алгоритмов [12–14,17,25,28]. Приведены результаты работы комплекса для двух наборов снимков. Первый набор снимков сделан с БПЛА eBee и взят из свободного доступа в интернете https://www.sensefly.com/ drones/example-datasets.html. Примеры снимков приведены на рис. 3, число снимков 182. Рисунок 2.1 – Результаты уравнивания Рисунок 3 – Примеры снимков, снятые с БПЛА eBee Второй набор снимков памятника Карлу Марксу был сделан бытовой фотокамерой Canon PowerShot A590 IS (рис. 4), число снимков 34. Рисунок 4 – Снимки памятника Карлу Марксу На рис. 5 показано расположение центров уравненных снимков и трехмерные облака точек, используемые при уравнивании, в таблице представлены ошибки обратного проектирования используемого трехмерного облака точек. Рисунок 5 – Результаты ориентирования набора снимков: Результаты показывают, что предложенные алгоритмы и схема их совместного использования позволяют решить задачу полной автоматизации обработки набора снимков с достаточно высокой точностью. Снимки могут представлять собой неупорядоченный набор, полученный разными способами фотосъемки (наземная, аэрофотосъемка БПЛА плановая и наклонная) и не иметь параметров калибровки. В процессе обработки снимков решается задача поиска перекрывающихся снимков, выделения связующих точек из множества точек интереса и уравнивание блока снимков произвольной структуры. Работа выполнена при финансовой поддержке РФФИ (проект № 17-08-00191 а). 1. Agarwal, S., Snavely, N., Simon, I., Seitz, S. & Szeliski, R. (2009): Buildng Rome in a Day. International Conference on Computer Vision, pp. 72–79. Заключение
а — с БПЛА eBeе; б — памятник Карлу МарксуСписок использованной литературы
2. Frahm, J.-M., Gallup, D., Johnson, T., Raguram, R., Wu, C., Jen, Y.-H., Dunn, E., Clipp, B., Lazebnik, S. & Pollefeys, M. (2010): Building Rome on a Cloudless Day. Eleventh European Conference on Computer Vision, IV, pp. 368–381.
3. Goesele, M., Ackermann, J., Fuhrmann, S., Klowsky, R., Langguth, F., Muecke, P. & Ritz, M.(2010): Scene Reconstruction from Community Photo Collections. IEEE Computer, 43 (6), pp.48–53.
4. Yvain Tisserand, Nadia Magnenat-Thalmann Image-based 3D Avatar for Virtual Try-on Applications – 55th Photogrammetric Week, September, 7 - 22, Stuttgart, 2015, pp.269–279.
5. D. Marmanis, J. D. Wegner, S. Galliani, K. Schindler, M. Datcu, U. Stilla SEMANTIC SEGMENTATION OF AERIAL IMAGES WITH AN ENSEMBLE OF CNNS – ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, Vol.III-3, Prague, 2016, pp.473–480.
6. Y.B. Blokhinov, A.S. Chernyavskiy, S.Y. Zheltov Photogrammetric model based method of automatic orientation of space cargo ship relative to the international space station – XXII Congress of the ISPRS, Int. Arch. Photogramm. Remote Sens. Spatial Inf. Sci., Vol. XXXIX, P.B3, Melbourne, Australia, 2012, pp.7–12.
7. Konrad Schindler, Wilfried Hartmann, Michal Havlena Recent Developments in Large-scale Tie-point Search – 55th Photogrammetric Week, September, 7 - 22, Stuttgart, 2015, pp.175–182.
8. Блохинов Ю.Б., Грибов Д.А., Чернявский А.С. Задача привязки изображений для некоторых случаев ракурсной фотосъемки // Изв. РАН. ТИСУ, 2008. – №6. – С.129–143.
9. Блохинов Ю.Б. Автоматизация взаимного ориентирования цифровых снимков на основе алгоритмов машинного зрения // Изв. РАН. ТИСУ. –2010. – №6. – С.152–163.
10. D.G. Lowe. Distinctive image features from scale-invariant keypoints. //International Journal of Computer Vision, 60(2):91– 110, 2004. 1, 2.
11. C. Wu. SiftGPU: A GPU implementation of Scale Invaraint Feature Transform (SIFT), 2007.
12. Открытая библиотека OpenCV http://opencv.org/
13. Открытая библиотека OpenMP http://www.openmp.org/
14. Открытая библиотека DBoW2 https://github.com/dorian3d/DBoW2
15. D. Galvez-Lopez and J. D. Tardos, Bags of binary words for fast place recognition in image sequences. //IEEE Transactions on Robotics, vol. 28, no. 5, pp. 1188–1197, 2012.
16. Szeliski R., Winder S. Multi-image matching using multiscale oriented patches // Proc. IEEE Conference on Computer Vision and Pattern Recognition. – 2005. – P. 510–517.
17. Открытая библиотека SiftGPU https://github.com/pitzer/ SiftGPU.
18. Fischler M.A., Bolles R.C. Random sample consensus: a paradigm for model fitting with applications to image analysis and automated cartography // Communications of the ACM. – 1981. – V.24. – P. 381–395.
19. R. Hartley and A. Zisserman, Multiple View Geometry in Computer Vision, 2nd ed. Cambridge University Press, 2004.
20. Ferrari V., Tuytelaars T., Van Gool L. Wide-baseline multiple view correspondences // Proc. IEEE Conference on Computer Vision and Pattern Recognition. – 2003. – P. 718–725.
21. Михайлов А.П., Чибуничев А.Г. Фотограмметрия – М.: Изд-во МИИГАиК, 2016. – 357 с.
22. Nister D. (2004): An Efficient Solution to the Five-Point Relative Pose Problem. //IEEE Transactions on Pattern Analysis and Machine Intelligence, 26 (6), 756–770.
23. H Stewenius, C Engels, D Nister (2006): Recent developments on direct relative orientation. //ISPRS Journal of Photogrammetry and Remote Sensing 60 (4), 284–294.
24. Kneip L., Scaramuzza D., Siegwart R. A novel parametrization of the perspective-three-point problem for a direct computation of absolute camera position and orientation //Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conference on. – IEEE, 2011. – С. 2969–2976.
25. Открытая библиотека ceres http://ceres-solver.org/
26. P. Moulon, P. Monasse, Unordered feature tracking made fast and easy, CVMP 2012.
27. Moisan L., Moulon P., Monasse P. Automatic homographic registration of a pair of images, with a contrario elimination of outliers //Image Processing On Line. – 2012. – Т. 2. – С. 56–73. 28. Открытая библиотека OpenMVG https://github.com/ openMVG