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

Размещено на http://www.allbest.ru/

Автореферат

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

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

05.13.17 - теоретические основы информатики

кандидата физико-математических наук

Цискаридзе Арчил Константинович

Москва, 2010

Работа выполнена в Московском физико-техническом институте (государственном университете)

Научный руководитель: доктор технических наук, профессор Л.М. Местецкий

Официальные оппоненты:

доктор физико-математических наук, профессор В.Н. Козлов

кандидат технических наук А.В. Копылов

Ведущая организация: Институт вычислительной математики и математической геофизики СО РАН

Защита диссертации состоится «____» ______________ 2010 г. в ____ часов на заседании диссертационного совета Д002.017.02 в Учреждении Российской академии наук Вычислительный центр им. А.А. Дородницына Российской Академии Наук по адресу: 119333, г. Москва, ул. Вавилова, д. 40.

С диссертацией можно ознакомиться в библиотеке Вычислительного Центра им. А.А. Дородницына РАН

Автореферат разослан «____» ______________ 2010 г.

Ученый секретарь диссертационного совета Д 002.017.02 доктор физико-математических наук, профессор В.В. Рязанов

Общая характеристика работы

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

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

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

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

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

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

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

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

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

Первый путь состоит в прямом построении пространственной циркулярной модели пространственного объекта по скелетам проекций. Этот метод предполагает, что проекции отдельных элементов пространственного объекта не перекрываются между собой, т.е. не имеют окклюзий. Силуэтное изображение объекта называется изображением без окклюзии, если в каждую его точку проектируется не более двух точек поверхности объекта. Метод основывается на идее конструирования стереопар «невидимых» общих точек обоих изображений. Серединные оси силуэтов предлагается рассматривать, как плоские проекции пространственных осевых линий жирных кривых, составляющих объект. Данное допущение вполне справедливо в случае отсутствия окклюзий в силуэтах. Такой подход позволяет свести задачу восстановления осевых линий пространственных жирных кривых к вычислению пространственных кривых по стереопарам их проекций. Результатом решения задачи является циркулярная модель, представляющая собой объединение нескольких пространственных жирных линий (рис.1). Этот поход в работе условно назван восстановлением проволочной модели.

Второй путь состоит в восстановлении формы сложного пространственного объекта в виде циркулярной модели заранее заданной структуры. В частности, для восстановления позы человека используется кусочно-линейная «шарнирная» модель (рис.2). Шарнирная модель описывает пространственный объект как объединение нескольких шарнирно закрепленных твердых тел. Каждый элемент этой конструкции представляет собой пространственную жирную кривую постоянной ширины, у которой осевой линией является прямолинейный отрезок. Форма пространственного объекта ищется путём подбора некоторого преобразования шарнирной модели, при котором её проекции на плоскости изображений будут в наибольшей степени совпадать со стереопарой силуэтов. Процесс итерационного преобразования шарнирной модели называется подгонкой. В диссертации процесс подгонки строится на основе использования скелетов силуэтных изображений.

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

Результаты, выносимые на защиту:

1. Метод описания формы сложного пространственного объекта в виде циркулярной модели.

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

3. Метод восстановления шарнирной пространственной модели без окклюзий на основе итерационной подгонки.

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

Научная новизна работы определяется:

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

- использованием техники непрерывной скелетизации для восстановления циркулярных моделей по стереопаре силуэтных изображений;

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

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

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

Апробация результатов исследования. Основные результаты диссертационного исследования докладывались на следующих конференциях: 49-я научная конференция Московского физико-технического института (Долгопрудный, 2006), 9-я Международная конференция по распознаванию образов и обработке информации (Минск, 2007), 13-я Всероссийская конференция «Математические методы распознавания образов» (Зеленогорск, 2007), 18-я и 19-я Международная конференция ГРАФИКОН (Москва, 2008, 2009), International conference on computer vision theory and applications (Лиссабон 2009).

Основные результаты исследования опубликованы в работах [1-7], в том числе в издании [1], входящем в список ВАК.

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

Содержание диссертации

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

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

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

Рассмотрим непрерывное отображение отрезка числовой прямой во множество сфер в пространстве . Каждому значению параметра соответствует сфера:

с центром в точке и радиусом .

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

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

Первый путь основывается на идее конструирования стереопар «невидимых» общих точек обоих изображений. Серединные оси силуэтов предлагается рассматривать, как плоские проекции осевых линий циркулярной модели. Данное допущение справедливо в случае отсутствия окклюзии в силуэтах. Рассмотрим множество точек в евклидовом пространстве , имеющее вид связного графа. Например, так можно схематично представить человеческой фигуру (рис.1).

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

Размещено на http://www.allbest.ru/

Рис.1: Циркулярная модель фигуры человека. Осевой граф (слева) и огибающая поверхность (справа).

Задача восстановления проволочной модели формулируется следующим образом:

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

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

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

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

Например, суставы колена или локтя позволяют делать вращение только в определенной плоскости бедра или плеча в диапазоне углов 30-180. На рисунке 2 указано число степеней свободы для каждой части тела. Под позой объекта будем понимать вектор значений динамических параметров модели. Каждой позе соответствует точка в пространстве из 24 динамических параметров фигуры, а всё множество поз описывается параллелепипедом в 24-х мерном пространстве . Таким образом, задача состоит в том, чтобы по стереопаре бинарных изображений найти вектор динамических параметров шарнирной модели, аппроксимирующей форму пространственного объекта, силуэты которого представлены на бинарных изображениях. Этот вектор динамических параметров шарнирной модели и является описанием позы. Он может быть использован в качестве вектора признаков при дальнейшем распознавании позы и выражаемого ею жеста.

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

Дано: шарнирная модель, стереопара силуэтов , проекционные матрицы камер .

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

Здесь мера различия проекций циркулярной модели при параметрах с силуэтами .

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

Размещено на http://www.allbest.ru/

Рис.2: Шарнирная модель фигуры человека. Структура модели (слева) пространственные элементы модели (справа).

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

1) Синтетические данные “Kungfu girl”, предоставленные группой Graphics-Optics-Vision из института Max-Planck (http://www.mpi-inf.mpg.de/departments/irg3/kungfu/index.html). Эти данные представляют собой последовательности двумерных изображений размером 320Ч240, синтезированные для 25 различных камер, расположенных в полусфере вокруг сцены. Сцена содержит анимированную фигуру человека. При формировании синтезированных изображений использовалась модель перспективной проекции камеры. Кроме изображений силуэтов, также имеются проекционные матрицы камер, которые заданы абсолютно точно без погрешностей.

2) Данные, предоставленные Брауновским университетом (США). Эти данные получены с помощью 4-х синхронизованных чёрно-белых камер, которые расположены вокруг сцены. Камеры откалиброваны относительно лабораторной системы координат и выдают полутоновые изображения размером 644Ч488. С их помощью записано движение человека, идущего по кругу. В отличие от предыдущих данных они соответствуют реальным снимкам.

3) Кроме этого для проведения экспериментов в рамках проводимого исследования был создан собственный стенд. Для получения изображений использовались две обычные web-камеры с разрешением 640Ч480. Калибровка камер проводилась с помощью эталонного объекта, представляющего собой картонную модель куба с нанесённой на грани прямоугольной сеткой. Для получения экспериментальных данных использовались куклы размером в 30 см. Выбор кукол в качестве моделей вместо полномасштабных человеческих фигур объясняется лишь упрощением съёмки в лабораторных условиях.

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

Сначала для силуэтов, полученных на основе сегментации исходных изображений (рис.3), строятся их скелеты в виде серединных осей, образованных центрами вписанных в силуэты окружностей (рис.4). При этом использованы подходы и методы, описанные в монографии Л.М.Местецкого «Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. М., Физматлит, 2009.

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



Рис.3: Стереопары исходных изображений (слева) и бинарных изображений силуэтов, полученных из них в результате сегментации, (справа).

Размещено на http://www.allbest.ru/

Рис.4: Стереопары скелетов силуэтов (слева), семейства вписанных в силуэты кругов (в центре), реконструированная модель фигуры человека (справа).

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

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

Рис.5: Выравнивание ветвей скелетов

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

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

Решение полученной вариационной задача (1) осуществляется на основе построения её дискретного аналога. Дискретизация задачи выполняется следующим образом. Рассматривается сетка размером NN (рис.6б). Вершина сетки с координатами (i,j) соответствует сопоставлению точек . Поиск наилучшего соответствия сводится к построению кратчайшего пути на целочисленной сетке, которое выполняется методом динамического программирования.

Рис.6: (а) Вычисление функции штрафа для учета эпиполярного ограничения; (б) дискретный вариант сопоставления точек кривых.

Таким образом, вместо непрерывного монотонного отображения будем рассматривать монотонный путь, соединяющий вершину сетки (0,0) и (N,N) (рис. 6б). Обозначим его через , где K - число ребер в пути. Тогда интегральный функционал (1) заменится дискретной суммой:

 (2)

где

Задача сопоставления кривых (1) сводится к задаче нахождение оптимального монотонного пути из вершины (0,0) в вершину (N,N), проходящего через вершины сетки. Обозначим через длину (штраф) оптимального пути из вершины (0,0) в . Тогда будет выполняться принцип оптимальности Беллмана:

(3)

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

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

Рис.7: Стереопары силуэтных изображений куклы и полученная пространственная модель.

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



Рис.8: Стереопары и полученные пространственные объекты для “Kungfu girl”

Рис.9: Стереопара силуэтных изображений из Брауновской базы и полученный пространственный объект под разными ракурсами

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

Скорость работы на компьютере Intel Pentium IV, Core 2 Duo, 2800 Mhz составила более 5 кадров в секунду. Это даёт возможность использовать предложенный метод в системах компьютерного зрения в реальном масштабе времени их работы.

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

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

(4)

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

Эталон представляет собой силуэт, на котором заранее, например, вручную, нанесены проекции узлов шарнирной модели. Шарнирная модель (рис.2) имеет 15 узлов. На рисунке 10 приведены примеры эталонов. Кроме силуэтов изображены также их скелеты.

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

Рис. 10: Примеры шаблонов с нанесенными проекциями узлов.

Возьмем любую точку на скелете и начнем обход скелета по часовой стрелке. Функция ширины задаёт для каждой точки скелета радиус вписанной окружности с центром в этой точке. Зависимость этого радиуса от длины пройденного при обходе скелета пути будем называть граничной функцией ширины. Обход закончится возвращением в точку, откуда начиналось движение. Отмасштабируем фигуру таким образом, чтобы длина замкнутого обхода равнялась 1, т.е. будем считать, что граничная функция определена на отрезке [0,1]. В зависимости от того, с какой точки началось движение, получаются разные функции, но они будет отличаться друг от друга лишь круговым сдвигом по аргументу. Кроме граничной функции ширины построим аналогичную функцию для степени вершины скелета. На рисунке 11 приведены примеры граничных функций ширины для двух силуэтов, показанных на рисунке 10.

Рис. 11: Примеры граничных функций ширины до выравнивания

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

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

(5)

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



Здесь константа, которая отвечает за гладкость кривой .

Полученная задача минимизации (5) отличается от (1) лишь наличием дополнительной минимизации по круговому сдвигу . Дискретизируем задачу (5) относительно параметра . Выберем точек на отрезке [0,1] и будем варьировать значение путём выбора начальных точек среди них. Тогда задача (5) сводится к подзадачам, каждая из которых имеет такой же вид что и задача (1). Как было показано выше, каждая подзадача решается методом динамического программирования за время . Соответственно задача минимизации (5) решается за время .

Результат выравнивания для графиков из рисунка 11 показан на рисунке 12. Как видно, после выравнивания графики стали существенно лучше совпадать.

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

1. Для каждой узловой точки с эталонного силуэта находим ближайшую к ней точку скелета.

2. С помощью выравнивания строим образ полученной точки на тестовом силуэте.

В первом случае стереопара силуэтов и эталон получены от одного и того же объекта (они являются силуэтами синтетических данных “kungfu-girl”) и различаются только позой и ракурсом. Во втором случае стереопара взята из Брауновской базы и представляет собой реальный силуэт, полученный с помощью видеокамеры. По визуальной оценке, на обеих стереопарах проекции узлов шарнирной модели найдены достаточно точно.

Рис. 12: Граничные функции ширины после выравнивания

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

Размещено на http://www.allbest.ru/

Рис. 13: Разметка стереопар с помощью эталонных силуэтов. Стереопара силуэтов слева и эталон получены от одного и того же объекта, справа - от различных объектов.

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

Рис. 14: Визуализация узловых точек в пространстве

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

Для решения этой задачи мы использовали квазиньютоновскую схему с численным градиентом. Градиент вычислялся разностной схемой по двум точкам. Алгоритм в среднем сходится за 400 итераций. На рисунке 15 (слева) показан пример построенного начального приближения.

Рис. 15: Построенное начальное приближение (слева) и подогнанная модель (справа)

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

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

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

Введем функцию различия между позой шарнирной модели и силуэтом через семейство окружностей и следующим образом:

(6)

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

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

Для стереопары силуэтов функцию различия между позой шарнирной модели и силуэтами введем как сумму различий для каждого силуэта:

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

Рис. 16: Результат подгонки, спроецированный под разными ракурсами

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

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

Узлы шарнирной модели пронумерованы от 1 до 15. В каждой вершине скелета пишется номер ближайшей к ней проекции узла. Далее производится двухуровневая кластеризация базы по следующим правилам:

1. На верхнем уровне два силуэта попадают в один кластер, если их скелетные графы изоморфны.

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

Рис. 17: Примеры из синтетической базы

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

(7)

Здесь через обозначена длина ребра , а обозначает усредненную ширину скелетной дуги . Вектор задает признаковое описание графа . Введём обозначения:

Далее введём расстояние между графами через признаковое описание :

(8)

Здесь параметр подбирается эмпирическим путем. Данное расстояние используется для классификации тестовых силуэтов полученных с камер. В каждом кластере второго уровня выбирается представитель кластера. Для тестового силуэта строится его скелет. Анализ топологии скелетного графа позволяет определить, в какой кластер верхнего уровня он попадает. Определив этот кластер, строим признаковое описание тестового силуэта. Используя расстояние (8), ищем ближайший кластер второго уровня. Данная кластеризация позволяет переносить разметку проекции узлов шарнирной модели на тестовый силуэт. На рисунке 18 показаны тестовые силуэты и представители найденных классов. Следует отметить, что, несмотря на метрическое различие в позах исходной и тестовой модели, обнаруживаемое на этих рисунках, топологическая разметка узловых точек произведена правильно.

В вычислительном эксперименте получены оценки правильной классификации силуэтов с произвольными окклюзиями на уровне 68% при количестве кластеров более 3000, что следует рассматривать как достаточно хороший результат.

Рис. 18: Тестовые силуэты (сверху) и представители найденных классов (снизу).

Основные результаты диссертации

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

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

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

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

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

Основное содержание диссертации отражено в следующих публикациях

1. Цискаридзе А. К. Математическая модель и метод восстановления позы человека по стереопаре силуэтных изображений // Научный журнал «Информатика и её применения», том.4, вып.4, 2010, с. 51-62.

2. Бакина И.Г., Местецкий Л.М., Цискаридзе А.К. Метод активного скелета в задаче распознавания формы изображений // Труды 19 международной конференций ГРАФИКОН-2009, Москва, с. 279-283.

3. Mestetskiy L., Tsiskaridze A. Spatial reconstruction of locally symmetric objects based on stereo mate images // Proceedings of the International conference on computer vision theory and applications (VISAPP 2009), Volume 1, Lisbon, Portugal, February 5-8,2009, p.443-448.

4. Местецкий Л.М., Цискаридзе А.К. Пространственная реконструкция локально симметричных объектов по силуэтным изображениям // Труды 18 международной конференций ГРАФИКОН-2008, Москва, ВМК МГУ, 2008. с. 221-226.

5. Tsiskaridze A. Palm Parameters Recognition Based on Stereo Mate Image Analysis // Proceedings of the Ninth International conference on Pattern recognition and information processing (PRIP'2007), Volume I, Minsk, Belarus, May 22-24, 2007.

6. Местецкий Л.М., Цискаридзе А.К. Восстановление в реальном времени пространственных характеристик гибкого объекта по стереопаре изображений // Доклады XIII Всероссийской конференции "Математические методы распознавания образов" (ММРО-13), Ленингр.обл., г. Зеленогорск, 2007, с. 359-363.

7. Цискаридзе А.К. Определение параметров ладони человека по стереопаре изображений при биометрической идентификаций // Труды 49-й научной конференции МФТИ, 2006. с. 280-281.

Размещено на Allbest.ru

...