УДК 004.414.23

Ларин М.С. 

Локализация камеры

Санкт-Петербургский государственный университет информационных технологий, механики и оптики

Научный руководитель – д.т.н., профессор В.М. Мусалимов

 

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

Ключевые слова: локализация, вэб-камера, виртуальное пространство, PnP

The paper proposes an approach for the implementation of automated localization systems equipped with web cameras. We consider methods of localization using additional devices and without them, by analyzing visual data.

Keywords: localization, web cam, virtual space, PnP

Локализация

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

На примере паспортизации зданий, при сопоставлении не только процесса измерения в виртуальном пространстве[1], но и затраченного времени, измерение оптической системой даст преимущество перед измерением рулеткой. Также очевидны положительные стороны при использовании автоматической системы локализации для эффективного передвижения роботов. Автономный робот без системы локализации способен выполнять узкий круг задач, связанных с неподвижной системой координат или заранее известной локацией, по сравнению с системой ориентирования, которая заметно увеличит не только круг задач, но и универсальность системы в целом.

Спутниковая локализация

Спутниковая система навигации, часто именуемая GPS. Позволяет в любом месте Земли (включая приполярные области), почти при любой погоде, а также в космическом пространстве вблизи планеты определить местоположение и скорость объектов. Система разработана, реализована и эксплуатируется Министерством обороны США.

Основной принцип использования системы — определение местоположения путём измерения расстояний до объекта от точек с известными координатами — спутников. Расстояние вычисляется по времени задержки распространения сигнала от посылки его спутником до приёма антенной GPS-приёмника. То есть, для определения трёхмерных координат GPS-приёмнику нужно знать расстояние до трёх спутников и время GPS системы[1]. Таким образом, для определения координат и высоты приёмника, используются сигналы как минимум с трёх спутников.

Точность системы в теории составляет около 1-2 метров, на практике, область возможного нахождения приёмника определяется с погрешностью около 100 метров. Тем не менее, это единственная глобальная система локализации, которую можно использовать в совокупности с локальной системой локализации, в зависимости от поставленной задачи.

Существует альтернатива спутниковой локализации, основанная на базе данных особых точек извлечённых из изображения местности. Программа PhotoSynth[2] от Microsoft наглядно показывает, что серии фотографий достаточно, чтобы создать “облако вершин”, по которым, изображения будут связываться в общую картину. Каждая часть такой картины, представляет набор уникальных расстояний между особыми точками, что даёт положение камеры относительно общей картины. Один раз получив положение особых точек на объекте, и переведя координаты точек  в глобальную систему координат используя данные о положении с GPS, можно производить последующие определения местоположения по изображению, не используя GPS устройства. В подобной реализации локализации, недостатком будет являться необходимость хранить базу данных.

Ориентирование по компасу

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

Типовой электронный компас создается при помощи установки двух магнитометров под правильными углами на плоской горизонтальной опоре. Каждый датчик измеряет одину из компонент горизонтального поля - по оси x опоры и по оси y. Если мы запишем эти компоненты как Bx и By, то угол между осью x и направлением горизонтального поля (указывающим на северный магнитный полюс) будет равен:

.(1)

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

Также существуют распространенные типы электронных компасов на основе: магнитометра, изготовленные по технологии “fluxgate”, датчик на основе эффекта Холла, магнитоиндуктивный датчик и магниторезистивный датчик. [3]

Эмпирическое ориентирование

Основной плюс эмпирического ориентирования — отсутствие дополнительных устройств, достаточно только вычислительной и оптической систем, всё остальное определяется при помощи алгоритмов анализа и обработки изображения. Данные полученные при обработке дают возможность выводить графику в виртуальном пространстве[4] в соответствии с системой координат зафиксированной сцены. Исходные данные для системы является видео – ряд изображений, а точнее особые точки. Особые точки тем особенны, что имеют соответствие точке на предыдущем кадре – точка объекта снятая с разных ракурсов. Извлечение особых точек на изображении и характера изменения положения особой точки в следующем изображении, даёт возможность строить фундаментальную матрицу (позиция камеры относительно центра сцены) на основе эпиполярной геометрии[5].

Также существует PnP[6] (Perspective-n-Point) проблема известная как расчёт позиции и ориентации камеры. Это проблема соответствия нескольких n точек в перспективе и на плоскости. Эта проблема формулируется как:

“Учитывая относительное пространственное расположение n контрольных точек, и с учетом угла каждой парой контрольных точек с дополнительной точкой называемой центром Перспективы (ЦП), найти длины отрезков соединяющих ЦП с каждой из контрольных точек.”

Изучение PnP проблемы в основном состоит из двух направлений:

1.            Построить быстрый и стабильный алгоритм для нахождения всех или некоторых решений PnP проблемы.

2.            Дать классификацию для решения PnP проблемы, т.е. дать  условия, при которых проблема имеет одно, два или четыре решения.

PnP проблема в простейшем случае предстаёт как P3P нахождение соответствий для трёх точек на стереопаре это проблема наименьшего набора контрольных точек, которая имеет бесконечно много решений. Фишлер и Боллес презентовавшие RANSAC   заметили, что при решении четырёх наиболее возможных случаев можно обойтись решением P3P системы уравнений. P3P проблема наиболее основательна в случае PnP проблем. Все другие PnP (n>3) проблемы включают P3P проблему как вырожденный случай, и проблемой она названа не спроста. Есть два подхода к решению P3P  проблемы: алгебраический подход и геометрический. В алгебраическом подходе используется алгоритм декомпозиции нуля Wu-Ritta. Эта декомпозиция обеспечивает первое полностью аналитическое решение CASSC (Complete Analytical Solution

with the assistance of Solution Classification) P3P проблемы. В геометрическом подходе подразумевается три пространственных угла раздельно. Здесь центр точки перспективы для каждого угла – тороид и центр перспективы находится как пересечение трёх тороидов. В этом случае получаются чисто геометрические критерии для числа решений P3P проблемы. Например: одним из интересных результатов является "P3P проблема может иметь только одно решение, если три угла перспективы тупые". Это намного проще алгебраической и даёт некоторое представление о феномене мультирешений. [6]

Ниже приведены основные алгоритмы и подходы к реализации нахождения особых точек и извлечения соответствий.

RANSAC (Random Sample Consensus), [7]

Алгоритм предложен в 1981г Фишлером и Боллесом. Алгоритм с общей схемой устойчивой оценки с выбором случайных подмножеств данных. Возьмем подмножество K(k элементов) из всех T. Вычислим на нем модель M(P(K)). Проверим все элементы T на соответствие модели M(P(K)). Определим количество соответствий в T для данной модели. Повторим весь этот процесс m раз. Та модель, которой соответствует наибольшее число соответствий и будет результатом работы алгоритма. Каждый элемент при выборе очередного подмножества выбирается с равной вероятностью. Количество подмножеств, которые необходимо попробовать, можно вычислить следующим образом:

, (2)

,где Г – требуемая вероятность выбора подходящего подмножества; k – количество элементов в выбранном подмножестве, необходимое для вычисления модели; e – процент выбросов в наборе Т; m – количество проверяемых подмножеств.

В алгоритме RANSAC есть “узкие места” для оптимизации – условие выбора подмножества и условие соответствия модели исходным данным. Существуют модификации алгоритма пытающиеся устранить недостатки RANSAC и не вносить свои – MLESAC (1998г), NAPSAC (2002г), R-RANSAC (2002г) и др.

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

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

Разновидности RANSAC делятся на три основных параметра которые в большей степени необходимы для конкретной реализации.

·             Быстрота

§                                                             Частичная оценка

·                                                                                     RANSAC with Boil-out Test

·                                                                                     R-RANSAC with SPRT

·                                                                                     R-RANSAC with Td,d Test

·                                                                                     Progressive RANSAC

§                                                             Руководствуясь выборкой

·                                                                                     PROSAC, [10]

·                                                                                     NAPSAC, [8]

·                                                                                     GASAC, [11]

·                                                                                     Guided MLESAC, [9]

·             Надёжность

§                                                             Адаптивная оценка

·                                                                                     Адаптивное прекращение

o                                                                                                            Feng and Hung’ MAPSAC

o                                                                                                            uMLESAC

o                                                                                                            AMLESAC

·                                                                                     Локальная оптимизация

o                                                                                                            pbM-estimator

·             Точность

§                                                             Локальная оптимизация

·                                                                                     LO-RANSAC

§                                                             Выбор модели

·                                                                                     QDEGSAC

·                                                                                     MAPSAC

§                                                             Функция потерь

·                                                                                     MLESAC

·                                                                                     MSAC

·                                                                                     MAPSAC

 

Разновидности RANSAC с которыми знаком MatLab

RANSAC

LMedS

LO-MSAC

MSAC

NAPSAC

R-RANSAC

ZHANGSAC

SIFT (Scale Invariant Feature Transform), [12, 13]

Алгоритм представил David Lowe в 1999г. Условно, алгоритм можно разделить на пункты.

·               На уменьшенной копии исследуемого изображения ищутся особенности

·               Ищется соответствие с предыдущем изображением

·               Пересчёт соответствий на исходные изображения, найденным особым точкам будет соответствовать области изображения

·               Фильтрация ложных соответствий

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

MSER (Maximally Stable External Region), [14]

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

·               Использование интенсивности – что мало влияет при аффинных преобразованиях

·               Ковариации сохранения смежности (производится непрерывно)

·               Стабильность: выбираются только те регионы, которые практически неизменны на протяжении целого ряда порогов.

·               Многомасштабное обнаружения без сглаживания с участием, как мелких так и крупных обнаруженных структур.

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

·               В наихудшем варианте алгоритм выполнит O(N) действий, где N количество пикселей в изображении.

ASIFT (Affine SIFT), [15]

Опубликованный в 2009г , J.M. Morel и G.Yu, ASIFT может похвастаться большим количеством совпадений на паре изображений находящихся в разных системах координат где SIFT не даёт приемлемых результатов.

Идея в том чтобы объединить симуляцию и нормализацию главного ингредиента SIFT. SIFT нормализует вращения и перемещения, и симулирует все масштабы (уменьшенные копии) и запроса на поиск и исходного изображения. Поэтому только на особые точки не влияет масштабирование. Другими словами ASIFT симулирует три параметра: масштаб и сферические координаты (longitude angle and the latitude angle) которые эквивалентны наклону, и нормализует другие три (смещение и вращение).

SURF (Speeded Up Robust Features), [16]

Herbert Bay et al. (2006г) представляет SIFT - надежный детектор изображения и дескриптора, который может быть использован в компьютерном зрении, например, сопоставление или 3D реконструкция объектов. Алгоритм разработан вдохновившись SIFT, но авторы заявляют, что стандартная версия SURF в несколько раз быстрее, чем SIFT, и более устойчива к разного рода трансформациям изображения, чем SIFT. В основе SURF лежит вычисление сумм приближенных 2D вейвлетов Хаара и делает эффективным использование интегрального изображения. В качестве особых точек изображения используется приближение вейвлета Хаара, определителя Гессе.

LESH (Local Energy based Shape Histogram)

LESH (Sarfraz, S., Hellwich, O в 2008г.), - является недавно предложенным,  описанием изображения в компьютерном зрении. Она может быть использована для получения описания базовой формы. LESH описывает функции строящиеся на местной энергетической модели художественного восприятия, например, конгруэнтность (для более подробной информации). Кодирование происходит путем аккумулирования энергии местного основного сигнала в нескольких направлениях фильтра, генерируются несколько местных гистограмм из разных частей изображения (128-мерные компактные пространственные гистограммы). LESH функции могут использоваться в приложениях, как основа поиска изображений, обнаружение объектов, представляет собой их оценку.

PTAM (Parallel Tracking and Mapping), [17]

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

Georg Klein и David Murray работающие над этой системой имеют публикации с 2002г. Система написана на C++ и компилируется под целевую платформу Linux, есть возможность компиляции под OSX или Windows но роботоспособность не гарантируется т.к. при написании использовались сторонние математические библиотеки, что доставляет особые трудности при портировании или компиляции.

SLAM (Simultaneous Localisation and Mapping), [18]

Или дополненная разработка monoSLAM может быть классифицирована как структура из движения в реальном времени (Real-Time Structure from Motion), или однокамерный SLAM (Single Camera SLAM) или monoSLAM (основанная на обработке изображений, с использованием одной камеры, в 3D и без внешних сенсоров). Это технология, которая может обеспечить дешевую, в реальном времени, локализацию для роботов, роботов-гуманоидов, одеваемые сенсоры, игровые интерфейсы или другие. Разработка monoSLAM это продолжение ранней SLAM начатой в 1998.

Заключение

Приведённые алгоритмы используются в программных пакетах компьютерного зрения, таких как открытая библиотека OpenCV[19] – набор функций для работы с обработкой изображений, векторами, вывод графики, работа с веб-камерами и обработка видео, или небольшой пакет ARToolKit[20] нацеленный на распознавание маркеров и помощь в построении дополненной реальности. Есть и коммерческие разработки как TotalImmersion, предоставляющих свой пакет для работы с дополненной реальностью. Пакеты как TotalImmersion предоставляют не просто функции, а регулируемую и настроенную систему построения дополненной реальности. С подобной системой можно сравнить разработки студентов Оксфорда как PTAM или monoSLAM, где не только оригинально выбраны способы инициализации системы координат но и имеется достаточно видео с процессом работы системы и на официальных сайтах и просто в сети. Неплохая особенность то, что эти системы открыты частично для общего доступа, но для, хотя бы, успешной компиляции кода понадобится найти код нескольких сторонних библиотек необходимой версии, и понимание базовых функций и взаимосвязи для внесения собственных изменений - тут если и разберешься, то лучше бы и сам писал.

 

Литература

1.            Ларин М.С. Измерительные функции виртуального пространства // Сборник докладов 9й сессии международной школы. “Фундаментальные и прикладные проблемы надежности и диагностики машин и механизмов” СПбГУ ИТМО 2009, с 386.

2.            Photosynth, домашняя страница [Электронный ресурс] http://photosynth.net/ – Загл. с экрана. – Яз. англ.

3.            Richard B. Langley, “The Magnetic Compass and GPS”, GPS World, September 1, 2003

4.            Ларин М.С. Среда виртуального пространства // Сборник докладов 8й сессии международной школы. “Фундаментальные и прикладные проблемы надёжности и диагностики машин и механизмов”, ФГУП НТЦ “ИНФОРМРЕГИСТР”, PC №11991 от 20 ноября 2007г (№ гос. рег. 0320702575), СПбГУ ИТМО 2007, c 146-149.

5.            Антон Конушин. “Геометрические свойства нескольких изображений” Компьютерная графика и мультимедиа. Выпуск №4(3)/2006.

6.            Gao, X.S.[Xiao-Shan], Hou, X.R.[Xiao-Rong], Tang, J.[Jianliang], Cheng, H.F.[Hang-Fei],  Complete solution classification for the perspective-three-point problem, PAMI(25), No. 8, August 2003, pp. 930-943.

7.            M. A. Fischler and R. C. Bolles. Random Sample Consensus: A paradigmformodel tting with applications to image analysis and automated cartography. Communications of the ACM, 24(6):381–395, June 1981

8.            D.R. Myatt, P.H.S Torr, S.J. Nasuto, J.M. Bishop, and R. Craddock. NAPSAC: High noise, high dimensional robust estimation - it’s in the bag. In Preceedings of the 13th British Machine Vision Conference (BMVC), pages 458–467, 2002.

9.            Ben J. Tordoff and David W. Murray. Guided-mlesac: Faster image transform estimation by using matching priors. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(10):1523–1535, October 2005.

10.        Ondrej Chum and Jiri Matas. Matching with PROSAC – Progressive Sample Consensus. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), 2005.

11.        Volker Rodehorst and Olaf Hellwich. Genetic Algorithm Sample Consensus (GASAC) - a parallel strategy for robust parameter estimation. In Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition Workshop (CVPRW), 2006.

12.        Lowe, D. G., “Object recognition from local scale-invariant features”, International Conference on Computer Vision, Corfu, Greece, September 1999.

13.        Кудряшов А.П., “Извлечение и сопоставление точечных особенностей”, Институт Автоматики и Процессов Управления ДВО РАН, Электронный научный журнал «ИССЛЕДОВАНО В РОССИИ»  1104.

14.        J. Matas, O. Chum, M. Urba, and T. Pajdla. "Robust wide baseline stereo from maximally stable extremal regions." Proc. of British Machine Vision Conference, pages 384-396, 2002

15.        J.M. Morel and G.Yu, ASIFT: A New Framework for Fully Affine Invariant Image Comparison. SIAM Journal on Imaging Sciences, 2(2):438-469, 2009

16.        Herbert Bay, Andreas Ess, Tinne Tuytelaars, Luc Van Gool, "SURF: Speeded Up Robust Features", Computer Vision and Image Understanding (CVIU), Vol. 110, No. 3, pp. 346--359, 2008

17.        Parallel Tracking and Mapping for Small AR Workspaces (PTAM), страница [Электронный ресурс] – Режим доступа: http://www.robots.ox.ac.uk/~gk/PTAM/, свободный. – Загл. с экрана. – Яз. англ.

18.        Andrew Davison: Research, страница [Электронный ресурс] – Режим доступа: http://www.doc.ic.ac.uk/~ajd/, свободный. – Загл. с экрана. – Яз. англ.

19.        Ларин М. С.  Работа  с  пакетом  программ Open Computer Vision // Науч.-техн.  вестн. СПбГУ ИТМО. 2008. Вып. 48. С. 95.

20.        Augmented Reality Tool Kit, домашняя страница [Электронный ресурс] – Режим доступа: http://www.hitl.washington.edu/artoolkit/, свободный. – Загл. с экрана. – Яз. англ.