автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Теоретико-информационные критерии и методы оценивания трехмерной структуры сцены и смещений камеры в мобильных системах компьютерного зрения

САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

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

Специальность 05.13.01 — Системный анализ, управлепие и обработка информации (в технических системах)

На правах рукописи

005531465

Петерсон Максим Владимирович

Автореферат диссертации на соискание ученой степени кандидата технических наук

Санкт-Петербург . 2013

005531465

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

Научный доктор технических наук, доцент

руководитель: Потапов Алексей Сергеевич

Официальные доктор технических наук, профессор оппоненты: Тропченко Александр Ювенальевич

(СПбНИУ ИТМО, профессор)

Ведущая организация:

кандидат технических наук, доцент Станкевич Лев Александрович (СПбГПУ, профессор)

Санкт-Петербургский институт информатики и автоматизации РАН

Защита состоится «06» июня 2013 г. в 16 часов 00 минут на заседании диссертационного совета Д 212.227.03 в Санкт-Петербургском национальном исследовательском университете информационных технологий, механики и оптики по адресу: 197101, Санкт-Петербург, Кронверский пр., д. 49.

С диссертацией можно ознакомиться в библиотеке СПбНИУ ИТМО. Автореферат размещен на сайте www.ifmo.ru

Автореферат разослан «30» апреля 2013 г.

Ученый секретарь диссертационного совета Д 212.22703.

д.т.н., проф. Ожиганов Александр Аркадьевич

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Использование методов компьютерного зрения в целях визуальной локализации мобильных систем в окружающем пространстве, в том числе автономных роботов, транспортных средств и т.д., является востребованным в областях навигации, картографирования, создания систем дополненной реальности и в других приложениях. Актуальность тематики визуальной навигации подтверждается тем, что она соответствует таким пунктам перечня критических технологий Российской Федерации, как «8. Нано-, био-, информационные, когнитивные технологии» и «Технологии информационных, управляющих, навигационных систем», а также приоритетному направлению развития науки, технологий и техники Российской Федерации «3. Информационно-телекоммуникационные системы».

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

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

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

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

Основные задачи исследования

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

2. Увеличение быстродействия и надежности методов сопоставления при работе с видеоизображениями, полученными при перемещении камеры.

3. Разработка методов оценки структуры динамических сцен по результатам отождествления сопряженных точек на изображениях, полученных с разных ракурсов.

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

Научная новизна исследования

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

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

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

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

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

Реализация результатов работы

Результаты диссертационной работы были использованы в НИР, проводимых на кафедре Компьютерной фотоники и видеоинформатики СПбНИУ ИТМО: «Разработка теории обучаемых систем анализа изображений и распознавания образов на основе принципа репрезентационной минимальной длины описания» по гранту Президента Российской Федерации для государственной поддержки молодых российских ученых (МД-2040.2010.9) и «Разработка теории анализа изображений на основе принципа репрезентационной минимальной длины описания» (проект №2.1.2/3912) по аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» по заказу Федерального агентства по образованию (2009-2011), а также в проекте «Разработка алгоритмов для определения позиции привязки виртуальных объектов на видеоряде», выполненном лабораторией филиала корпорации «LG Electronics Inc.» в Санкт-Петербурге в 2012 году.

Использование результатов работы подтверждено двумя актами, приложенными к диссертации.

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

Личный вклад автора

Все основные результаты получены лично автором или при его непосредственном участии.

Апробация работы

Основные результаты работы докладывались на XXXIX научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2010), Первой международной конференции «Автоматизация управления и интеллектуальные системы и среды» (Приэльбрусье, Нальчик, 2010), XL научной и учебно-методической конференции СПбНИУ ИТМО (Санкт-Петербург, 2011), VI Всероссийской научно-практической конференции «Перспективные системы и задачи управления» (Таганрог, 2011), IAPR Conference on machine vision applications (Nara, Japan, 2011), The 3rd International topical meeting on optical sensing and artificial vision (Saint Petersburg, 2012).

Публикации

Основные научные результаты диссертации опубликованы в 8 научных работах, среди которых 2 статьи опубликованы в ведущих рецензируемых изданиях, входящих в перечень ВАК, а также получено 2 свидетельства о государственной регистрации программ для ЭВМ.

Структура и объем диссертации

Диссертация состоит из введения, четырех глав, заключения и списка цитируемой литературы. Она содержит 121 страницу машинописного текста, 34 рисунка и 7 таблиц. Список цитируемой литературы содержит 100 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении обоснована актуальность темы исследования, сформулированы цель и задачи исследования, представлены основные результаты, выносимые на защиту, а также приведены основные положения, составляющие его научную новизну и практическую значимость.

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

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

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

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

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

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

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

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

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

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

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

Таким образом, каждый из критериев представляется в виде суммарного числа бит, необходимого для описания параметров модели и возникающих невязок между точечными соответствиями на паре изображений. Оптимальным распределением точечных соответствий по кластерам является то, которое минимизирует суммарную длину описания всех выделенных моделей. Для расчета длины описания преобразования каждого класса необходимо оценить: £р - длину описания вектора параметров р модели каждого класса, ¿¡„^ - длину описания номеров отождествленных ключевых точек, которые принадлежат к рассматриваемому кластеру, ¿£ - длину описания вектора невязок При оценке длины описания вектора параметров р можно руководствоваться минимальным количеством точечных соответствий, которое необходимо для его вычисления. Стандартная оценка для длины описания вектора параметров р, состоящего из пр элементов, при имеющихся Л^ точках в кластере будет иметь вид

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

ввиду того, что число различных вариантов формирования кластера, состоящего из Нк точек, равно числу сочетаний из ЛГпо

Длина описания невязок зависит от класса преобразования. Можно предположить, что в случае томографии и аффинного преобразования компоненты вектора невязок с,- независимы и являются равномерно распределенными. В таком случае длина описания невязок может быть оценена согласно выражению

где ав ,ае - значение среднеквадратичного отклопения по оси X и У

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

где с, - значение среднеквадратичного отклонения расстояния от проекций точек одного изображения до соответствующей эпиполярной линии на

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

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

Для выполнения кластеризации необходимо оценивать выигрыш в длине описания, получаехмый при различных моделях межкадрового преобразования. Предполагается, что координаты точек, которые не подходят под описание выбранной модели, являются независимыми и равномерно распределенными, поэтому каждая координата задастся битами, где 5 - линейпый размер изображений. Общий выигрыш для кластера из ТУ* точек будет

2^108,5-1-6

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

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

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

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

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

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

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

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

В процессе трекинга будет формироваться определенная цепочка кадров, связашгых между собой томографией. Обозначим множество ключевых точек на начальном изображении плоского маркера как Fri. Тогда набор точек Frz па следующем кадре будет записываться как Fr2 = HI >2F^, где Н)+2 - матрица томографии. Таким образом, каждый ¡-й кадр будет связан с первым через набор гомографий

Ъ = Н= ны>н,2 „_,...Н^Frt, поэтому, вычислив томографию между текущим и предыдущим кадром в цепочке, можно определить текущее положение камеры относительно маркера.

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

Следует отметить, что выполнение процедуры сопоставления с каждым кадром в цепочке при увеличении ее размера влечет за собой значительное увеличение времени работы всего алгоритма восстановления текущего положения камеры. Для уменьшения количества производимых операций сопоставления в рамках данной работы был разработан специальный алгоритм обхода цепочки ключевых кадров. На первом этапе среди ключевых кадров цепочки длиной N рассматривается три: Fry FrN/2 и FrN. Сначала осуществляется сопоставление с первым кадром Frit затем с кадром Frm, и если оно произведено успешно, то все последующие кадры в цепочке удаляются, а текущий кадр помещается после Fr\ или Frm соответственно. Если нужного количества отождествленных точек найдено не было, то производится сопоставление с кадром FrN. Если оно произведено успешно, то далее до первой неудачи осуществляется сопоставление с кадрами, стоящими перед FrN, т.е. от FrNA до FrM2-i- Текущий кадр помещается в

цепочку за кадром, на котором прервался ряд успешных сопоставлений. В случае, когда сопоставление с кадром Ргц было неудачным, по очереди проверяются кадры в интервалах [/<У2,] и

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

В качестве исходных данных имеется массив из N предварительно сопоставленных пар ключевых точек. Чтобы найти межкадровое преобразование, необходимо выполнить произвольную выборку из п точек, которые нужны для оценки параметров рассматриваемых моделей. Поскольку для оценки фундаментальной матрицы Р требуется наиболыие количество точек, за размер произвольной выборки принимается /1 = 7. Для повышения вероятности того, что точки в выборке будут принадлежать одному объекту, необходимо ввести некоторые топологические ограничения. Например, можно сделать допущение, что на наблюдаемой сцене присутствуют только твердотельные объекты, поэтому следует выбирать только те соответствия, которые на обоих изображениях находятся друг от друга в пределах некоторого порогового расстояния л Далее выполняется оценивание вектора параметров для каждого из рассматриваемых классов преобразований.

Предположим, что была осуществлена произвольная выборка из п = 1 пар точечных соответствий и произведена оценка параметров модели какого-либо межкадрового преобразования М е Тогда пройдя по

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

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

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

Выбор модели с МДО,

удаление соответствующих

точек из дальнейшего

рассмотрения

Рисунок 1 - Схема алгоритма кластеризации отождествленных ключевых точек

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

Для экспериментальной проверки разработанного инкрементного метода сопоставления изображений с цепочкой опорных кадров использовались тестовые видеопоследовательности, где в кадре присутствовал плоский объект, выступавший в качестве маркера, относительно которого восстанавливалось текущее положение камеры. Поскольку при использовании разработанного метода сопоставления изображений применялась упрощенная схема построения локальных дескрипторов, то в первую очередь была произведена оценка быстродействия процесса детектирования и описания ключевых точек. Оценка быстродействия выполнялась в сравнении с известной реализацией дескриптора SURF в библиотеке OpenCV. В данной работе для составления локальных дескрипторов на основе ключевых точек использовался метод, аналогичный применяемому методу в подходе SIFT, однако для повышения производительности применялась упрощенная схема, в рамках которой выполнялась обработка изображения только исходного масштаба, а размер вектора-дескриптора был уменьшен до 36 элементов. Результаты оценки производительности процедуры выделения и описания для Np = 150 ключевых точек на изображении 320x240 пикселей приведены в табл. 1.

Таблица — 1 Оценка времени работы процедур выделения и описания Ыр ключевых точек

Процессор: Intel Core ¡5-2400 3.10Гц

Среднее время, мс Макс, время, мс

Выделение и описание точек по упрощенной схеме (Np = 150) 8 10

Выделение и описание точек с помощью метода SURF в библиотеке OpenCV (Np = 150) 57 67

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

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

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

Количество раз, при которых наблюдалось заданное соотношение числа сопосгавлений и кадров в цепочке (тт.)

Количество произведенных сопоставлений (шт.)

Порядковый номер кадра в цепочке, с которым выполнено сопоставление (шт.)

Рисунок 2 — Количество произведенных операций сопоставления пары изображений в зависимости от размера цепочки опорных кадров

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

Для оценивания быстродействия предложенного инкрементного метода сопоставления с цепочкой кадров производилось измерение времени работы его программной реализации. Помимо измерений времени работы на персональном стационарном компьютере с процессором Intel Core ¡5-2400 3.10Гц, осуществлялись измерения времени на мобильном устройстве с процессором ARM Cortex А9 1.2Гц. Полученные результаты измерений приведены в табл. 2.

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

Таблица - 2 Оценка времени работы реализации инкрементного метода сопоставления с цепочкой опорных кадров__

Тип процессора Intel Core ¡5-2400 3.10Гц ARM Cortex А9 1.2Гц

Среднее время, MC Макс, время, мс Среднее время, MC Макс, время, мс

Сопоставление с цепочкой опорных кадров 13 35 22 81

Выделение и описание точек по упрощенной схеме (Np= 150) 8 10 17 39

Рисунок 3 - Пример работы системы дополненной реальности на мобильном устройстве с использованием предлагаемого инкрементного метода сопоставления изображений. На

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

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

На паре изображений, представленных на рис. 4а, также выделены ключевые точки на двух независимо перемещающихся объектах и фоновых объектах, при этом сама камера неподвижна.

£« = 3728

¿и, = 3569

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

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

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

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

Кластеризованные точки

Некластеризованные точки

Расстояние от центра проекции камеры вдоль оптической оси, отн. сд.

Расстояние от центра проекции камеры вдоль ^ оптической оси, отн. сд.

Смещение п оси У, отн. ед.

Смещение по оси У, 01Н. сд.

б)

Смещение по оси А", ОТН. ед.

В)

3 -2 Смешение по оси Л", ОТН. ел.

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

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

параметрам камеры были вычислены ошибки репроецирования, полученные данные приведены в табл. 4.

Таблица - 4 Параметры ошибок репроецирования для сцены на рис. 5а

1 ^кластеризованные точки Кластеризованные точки

Средняя ошибка, пике. 2,7 0,57

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

РЕЗУЛЬТАТЫ, ВЫНОСИМЫЕ НА ЗАЩИТУ

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

Публикации в изданиях, рекомендуемых ВАК РФ

1. Петерсон М.В. Кластеризация множества отождествлённых точек на изображениях динамических сцен на основе принципа минимальной длины// Оптический журнал.-2010.-№.11.-том 77.-С.56-62.

2. Петерсон М.В., Потапов A.C. Применение принципа репрезентационной минимальной длины описания для сенсомоторной калибровки // Известия КБНЦ РАН. - 2011. - №1. - С. 221-225.

Свидетельства о государственной регистрации программ для ЭВМ

3. Петерсон М.В., Потапов A.C. Программный модуль «Система представления пространственной динамической информации» // Свидетельство о гос. регистрации программы для ЭВМ № 2010615978. -М.: Роспатент, 2010. - Дата поступления 15.07.2010, дата регистрации 13.09.2010.

4. Петерсон М.В., Потапов A.C. Программный модуль «Контекстное обучение системы управления на основе теоретико-информационного критерия» // Свидетельство о гос. регистрации программы для ЭВМ № 2011614453. - М.: Роспатент, 2011. - Дата поступления 12.04.2011, дата регистрации 06.06.2011.

Публикации в других изданиях

5. Петерсон М.В., Гуров И.П. Определение характеристик цифровой видеокамеры в системах компьютерного зрения по изображению калибровочного объекта // Труды научно-технического центра Фотоники и оптоинформатики /Под ред. И.П. Гурова и С. А. Козлова. - СПб: СПбГУ ИТМО. - 2009. - С. 387-397.

6. Петерсон М.В., Потапов А.С. Сенсомоторная калибровка систем компьютерного зрения на основе принципа репрезентационной длины описания // Труды научно-исследовательского центра Фотоники и оптоинформатики. Сб. статей / Под ред. И.П. Гурова и С.А. Козлова. -СПб: СПбГУ ИТМО. - 2010. - Вып. 2. - С. 290-297.

7. Тупиков В.А., Малышев И.А., Потапов А.С., Петерсон М.В. Подсистема обработки изображений как элемент системы управления // Материалы шестой Всероссийской научно-практической конференции «Перспективные системы и задачи управления» и третьей молодежной школы-семинара «Управление и обработка информации в технических системах» - 2011. - С. 70-72.

8. Averkin A., Gurov I., Peterson М., Potapov A. Spectral-differential feature matching and clustering for multi-body motion estimation // Proc. of conference on machine vision applications, Nara, Japan. - 2011. - P. 173-176.

9. Peterson M. Potapov A. Practical aspects of point feature matching for affine and projective cases // Technical digest of The 3rd international topical meeting on optical sensing and artificial vision (OSAV'2012), Saint Petersburg, Russia.- 2012. -P.42-43.

Ю.Потапов A.C., Петерсон M.B., Козлов В.А., Аверкин А.Н. Системы компьютерного зрения: реализация в библиотеке OpenCV: учебно-методическое пособие - СПб: СПбГУ ИТМО. - 2011. - 83 с.

Тиражирование и брошюровка выполнены в учреждении «Университетские телекоммуникации» 197101, Санкт-Петербург, Саблинская ул., 14 Тел.(812)233 46 69. Объем 1,0 у.п.л. Тираж 100 экз.

САНКТ-ПЕТЕРБУРГСКИЙ НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

На правах рукописи

"¿201358625

Петерсон Максим Владимирович

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

Специальность 05.13.01 - Системный анализ, управление и обработка информации (в технических системах)

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель д.т.н. Потапов A.C.

Санкт-Петербург 2013

Оглавление

Введение......................................................................................................................4

Глава 1. Методы восстановления относительной ориентации камеры и трехмерной структуры сцены...............................................................................10

1.1 Использование локальных признаков в мобильных системах компьютерного зрения.......................................................................................10

1.2 Модель формирования изображений на основе центральной перспективной проекции....................................................................................14

1.3 Методы калибровки камеры........................................................................17

1.4 Методы восстановления относительного положения камеры и трехмерных координат точек сцены.................................................................27

Выводы по главе 1...............................................................................................37

Глава 2. Разработка информационных критериев для выбора моделей пространственных преобразований....................................................................38

2.1 Априорная информация о геометрической модели камеры.....................38

2.2 Критерии выбора геометрических моделей из семейств со сложной структурой...........................................................................................................42

2.3 Определение внутренних параметров камеры...........................................51

2.4 Определение смещения камеры и восстановление структуры сцены.....57

Выводы по главе 2...............................................................................................64

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

относительного смещения камеры......................................................................65

3.1 Получение исходных данных для определения внутренних параметров камеры..................................................................................................................65

3.2 Сопоставление изображений по набору ключевых точек........................71

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

Выводы по главе 3...............................................................................................84

Глава 4. Экспериментальная проверка..............................................................85

4.1 Инкрементный метод сопоставления изображений..................................85

4.2 Проверка критериев для выбора типа межкадрового преобразования... 96

4.3 Реконструкция моделей динамических сцен...........................................103

Выводы по главе 4.............................................................................................108

Заключение.............................................................................................................110

Литература..............................................................................................................112

Введение

Актуальность темы

Использование методов компьютерного зрения в целях визуальной локализации мобильных систем в окружающем пространстве, в том числе автономных роботов, транспортных средств и т.д., является востребованным в областях навигации, картографирования [1, 2], создания систем дополненной реальности [3, 4] и в других приложениях. Актуальность тематики визуальной навигации подтверждается тем, что она соответствует таким пунктам перечня критических технологий Российской Федерации, как «8. Нано-, био-, информационные, когнитивные технологии» и «Технологии информационных, управляющих, навигационных систем», а также приоритетному направлению развития науки, технологий и техники Российской Федерации «3. Информационно-телекоммуникационные системы».

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

быть классифицирована как наиболее сложный тип задач структурной идентификации моделей.

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

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

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

независимо перемещающихся объектов. Таким образом, может быть сформулирована следующая цель работы.

Цель работы

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

Основные задачи

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

• Увеличение быстродействия и надежности методов сопоставления при работе с видеоизображениями, полученными при перемещении камеры.

• Разработка методов оценки структуры динамических сцен по результатам отождествления сопряженных точек на изображениях, полученных с разных ракурсов.

Используемые методы исследования

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

Научная новизна

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

• Предложен новый инкрементный метод определения ракурса съемки путем оптимизации сопоставления с последовательностью опорных кадров.

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

Практическая значимость

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

Достоверность результатов работы

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

На защиту выносятся следующие результаты

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

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

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

Реализация результатов работы

Результаты диссертационной работы были использованы в НИР, проводимых на кафедре Компьютерной фотоники и видеоинформатики СПбНИУ ИТМО: «Разработка теории обучаемых систем анализа изображений и распознавания образов на основе принципа репрезентационной минимальной длины описания» по гранту Президента Российской Федерации для государственной поддержки молодых российских ученых (МД-2040.2010.9) и «Разработка теории анализа изображений на основе принципа репрезентационной минимальной длины описания» (проект №2.1.2/3912) по аналитической ведомственной целевой программе «Развитие научного потенциала высшей школы» по заказу Федерального агентства по образованию (2009-2011), а также в проекте «Разработка алгоритмов для определения позиции привязки виртуальных объектов на видеоряде», выполненном

лабораторией филиала корпорации «LG Electronics Inc.» в Санкт-Петербурге в 2012 году.

Получено два акта об использовании результатов диссертационной работы.

Личный вклад автора

Все основные результаты получены лично автором или при его непосредственном участии.

Апробация работы

Основные результаты работы докладывались на XXXIX научной и учебно-методической конференции СПбГУ ИТМО (Санкт-Петербург, 2010), Первая международная конференция «Автоматизация управления и интеллектуальные системы и среды» (Приэльбрусье, Нальчик, 2010), XL научная и учебно-методическая конференция СПбНИУ ИТМО (Санкт-Петербург, 2011), VI Всероссийская научно-практическая конференция «Перспективные системы и задачи управления» (Таганрог, 2011), IAPR Conference on machine vision applications (Nara, Japan, 2011), The 3rd International topical meeting on optical sensing and artificial vision (Санкт-Петербург, 2012).

Публикации

Основные научные результаты диссертации опубликованы в 8 научных работах, среди которых 2 статьи опубликованы в ведущих рецензируемых изданиях, входящих в перечень ВАК, а также получено 2 свидетельства о государственной регистрации программ для ЭВМ.

Глава 1. Методы восстановления относительной ориентации камеры и трехмерной структуры сцены

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

1.1 Использование локальных признаков в мобильных системах компьютерного зрения

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

10

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

всех остальных точек в некоторой окрестности по значению сравниваемых

/

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

Признаковый подход имеет свои преимущества, например, после построения дескрипторов ключевые точки становятся геометрически и фотометрически инвариантны [7], также существует большой набор методов для оценки геометрических параметров съемки по набору сопоставленных точек на серии изображений. Помимо этого, набор локальных особенностей может быть использован для сопоставления и распознавания изображений трехмерных сцен особенно в том случае, когда распознаваемый объект заслонен каким-либо посторонним объектом, что значительно затрудняет применение классических методов сопоставления, например, прямого поэлементного согласования или поиска шаблонов [8].

Классическими и одними из наиболее широко используемых детекторов ключевых точек являются «уголковый» детектор Харриса [9], использующий автокорреляционную матрицу яркости элементов изображения и детектор FAST (features from accelerated segment test) [10], основанный на сравнении

яркостей текущего элемента изображения и его соседей в определенной конфигурации. Для обеспечения инвариантности к повороту и изменению масштаба между сопоставляемыми изображениями на практике часто применяются такие классические подходы к построению дескрипторов как SIFT (scale invariant features transform) [11] и его ускоренная модификация SURF (speeded-up robust features) [12].

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

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