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

004617065

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

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

ВОССТАНОВЛЕНИЕ ПРОСТРАНСТВЕННЫХ ЦИРКУЛЯРНЫХ МОДЕЛЕЙ ПО СИЛУЭТНЫМ ИЗОБРАЖЕНИЯМ

Специальность 05.13.17 - теоретические основы информатики

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

- 9 ЛЕН 2010

Москва-2010

004617065

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

Научный руководитель: доктор технических наук,

профессор Л. М. Местецкий

Официальные оппоненты: доктор физико-математических наук,

профессор В. Н. Козлов

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

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

математической геофизики СО РАН

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

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

Автореферат разослан « 2.1 » На?%ЪрЭ1 2010 г.

Ученый секретарь /7 / / /

диссертационного совета Д 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 наименований.

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

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

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

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

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

Рассмотрим непрерывное отображение c^o.i]-»«1 х[0,ю) отрезка [о, А] числовой

прямой во множество сфер в пространстве R'. Каждому значению параметра /e[a,è] соответствует сфера;

С, = l(w):{х-u(t)f + (у-v(0)2 + (z -s(t)f <r{t)\{x,y,z) е Л3} с центром в точке P(t) = (и(t),v(t), s(t)) и радиусом r(t) е [0,оо).

Объединение С = (Je, всех сфер этого семейства будем называть

пространственной жирной кривой с осевой линией P(t) и шириной r(t). Циркулярной моделью или просто циркуляром называется объединение нескольких пространственных жирных кривых, у которых осевые линии образуют связное множество.

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

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

С каждой точкой t е Т графа Т связан некоторый шар с, с центром в этой точке. Это семейство шаров С = {с,,ГеГ} составляет циркуляр. Граф Т называется осевым

графом циркуляра Объединение 5 = [Je, всех шаров семейства С, как точечных

кт

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

поверхность (справа).

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

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

Найти: пространственный циркулярный граф С = (с,, / е Т}, осевой граф Т которого имеет заданную структуру, при этом объединение проекций всех шаров с,, / е Т на плоскости камер совпадают с 5] и ^ соответственно.

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

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

<Ртт ^ <Р ^ «'шах

^ Ч> ^ ^шах

@тт — $ — ^щах

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

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

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

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

различия проекций циркулярной модели при параметрах в с силуэтами , ¿>2.

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

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

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

1) Синтетические данные "Kungfti girl", предоставленные группой Graphics-Optics-Vision ИЗ института Max-Planck (http://www.mpi-infmpg.de/departments/irg3/kungfu/index.htinl). Эти данные представляют собой последовательности двумерных изображений размером 320x240, синтезированные для 25 различных камер, расположенных в полусфере вокруг сцены. Сцена содержит анимированную фигуру человека. При формировании синтезированных изображений использовалась модель перспективной проекции камеры. Кроме изображений силуэтов, также имеются проекционные матрицы камер, которые заданы абсолютно точно без погрешностей.

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

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

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

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

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

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

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

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

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

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

Если задать кривую ОА как непрерывное отображение rx :[0,1]->ÄJ, а кривую О'А' как г,: [0,1] -»R2, задача выбора соответствия сводится к нахождению непрерывного монотонного отображения w: [0,1] —> [0,1], которое сопоставляет стереопары точек л,(/)<н>г2(м>(()) и при этом минимизирует расхождение, заданное в виде функционала:

1 _

min [pir^MHm^ + w'itfdt (1)

veeC[0,l] J w-монот. 0 w(0)=0 w(l)=l

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

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

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

<ij) соответствует сопоставлению точек r(-L ]<_» r (-L). Поиск наилучшего соответствия

\N) \N)

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

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

Таким образом, вместо непрерывного монотонного отображения м> будем рассматривать монотонный путь, соединяющий вершину сетки (0,0) и (N,1^) (рис. 66). Обозначим его через (i0,jJ,(i^Jt),.■■(iкJк), где К - число ребер в пути. Тогда

интегральный функционал (1) заменится дискретной суммой: к

Я = 1',ы=Л-<) . где (2)

4-1

</<4, л м,_„/;_,)=¡ЕШМ^РШ^Ш!.

Задача сопоставления кривых (1) сводится к задаче нахождение оптимального монотонного пути (/„,/Д (¿,,7,),...(!,;,./*:) из вершины (0,0) в вершину (Л',Л/), проходящего

через вершины сетки. Обозначим через Ц^п (/,./) длину (штраф) оптимального пути из вершины (0,0) в (у). Тогда будет выполняться принцип оптимальности Беллмана:

Аш„('*>Л)= пнп[£»ш|„_!,Л-1) + ^(4,Л 14-1 ^Л-[)] (3)

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

всевозможные варианты предпоследнего узла (/,._,, ), найти оптимальный пусть до него и достроить путь до вершины (4>Л)- В каждую вершину (/,/) можно попасть только из соседних вершин (¿-1,у'-1),(г-1,_/),(г,у-1) (это следует из требования монотонности отображения). Таким образом, используя рекуррентное соотношение (3), мы за время 0(Л<г) находим оптимальный путь.

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

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

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

связанных с распознаванием позы, такая точность представляется вполне приемлемой. Во второй главе также приведены результаты вычислительных экспериментов Примеры стереопар и полученных .моделей показаны на рисунках 3,4,7,8,9.

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

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

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

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

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

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

в' -

(4)

Мера вводится через скелеты силуэтов, а также предлагается метод ее

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

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

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

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

Ф

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

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

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

Далее выполняется выравнивание граничных функций ширины для заданных силуэтов. Пусть имеются два силуэта, и пусть г, :[0,1]->Ä2 и г2 :[0,1]-> Я2 - их граничные функции ширины, а deg,: [0,1]->{1,2,3} и deg2: [0,1]->{1,2,3} - граничные функции для степеней вершин соответствующих скелетов. Объединим две такие функции в двухкомпонентный вектор Д = (г, deg,.): /' е {1,2}. Обозначим через Т6 оператор циклического сдвига аргументов на S для функций, определенных на отрезке [0,1], т.е. Vw: [ОД] —> [0,1]:

Т °w(r} = iW(i + (5' KPU ' + S ' (w(f + £-l) при t + S> 1

Здесь кружком ° обозначена операция суперпозиции. Задача выравнивания заключается в построении непрерывного монотонного отображения w: [0,1]->[0,1] и нахождения сдвига <?>0, которые сопоставляют граничные функции ширины R\(t) о i?j(w(i)) и при этом минимизируют расхождение, заданное в виде функционала:

1 _

d(RuR2)= min min [p{R{(t),R2(Ts oW(t))^w'(t)2dt

¿e[0,l]weC[0,l] J W

w(0)=0 0 w(I)=l

w-M0H0m.

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

P = <\ri~r2 'Ideg-deg^ + itj)

Здесь к2 константа, которая отвечает за гладкость кривой м»(г). Полученная задача минимизации (5) отличается от (1) лишь наличием дополнительной минимизации по круговому сдвигу 8. Дискретизируем задачу (5)

относительно параметра 8 . Выберем N точек ~,/ = 0.М на отрезке [ОД] и будем

N

варьировать значение 8 путём выбора начальных точек среди них. Тогда задача (5) сводится к N подзадачам, каждая из которых имеет такой же вид что и задача (1). Как было показано выше, каждая подзадача решается методом динамического программирования за время 0(Ы2). Соответственно задача минимизации (5) решается за время 0(Л'3).

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

Выравнивание функции ширины К{(1)<г>Тв ° Л2(м*(гу) двух силуэтов позволяет нам сопоставить точки скелетов. Для переноса проекции узлов шарнирной модели с эталона на тестовый силуэт используется следующая схема:

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

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

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

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

Стереопара образцов

Эталон

Стереопара образцов

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

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

ЩЁ

Ш

Рис. 14: Визуализация узловых точек в пространстве Для получения начального приближения в виде вяап е 0 решается оптимизационная задача. Обозначим через г,:0-»Д3,;' = 1..15 зависимость координат узлов шарнирной модели от динамических параметров. Тогда, начальное приближение определяется методом наименьших квадратов:

15 - |2 ве& ы

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

I / I

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

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

оптимизации. Функция различия //(0,5,,Х2) шарнирной модели со стереопарой силуэтов определяется следующим образом.

Для начала введем функцию различия р{9,5) между позой в шарнирной модели и одним силуэтом 5. Построим скелет силуэта 5, и представим его в виде семейства вписанных в силуэт окружностей (Лг,Ог):геТ. Здесь Т задает скелетный граф для силуэта 51, а Л, радиусы вписанных в силуэт окружностей с центрами в точках Ог.

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

Введем функцию различия р(в, 5) между позой в шарнирной модели и силуэтом 5 через семейство окружностей (Дг,бг):гбТ и {г^(6),сг(9)) :г е Й следующим образом:

| тттах(|Оа-с^(0)|-Да+^((9),О)-£//?+ |т¡¡¡ра-ср(в)\-с1а (6)

/?еП абТ ае

Первый член в сумме отвечает за то, чтобы окружности из проекции шарнирной модели по возможности находились внутри окружностей силуэта 5. При этом учитываются сами размеры кругов. Более точно, выражение \ра-с/1{в^-Ка+г/,(в) = АВ

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

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

Для стереопары силуэтов б1,,!?, функцию различия между позой в

шарнирной модели и силуэтами введем как сумму различий для каждого силуэта:

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

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

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

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

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

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

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

Рис. 17: Примеры из синтетической базы Пусть С,,02...СЛ. скелетные графы, входящие в один и тот же кластер верхнего уровня. Построим для них признаковое пространство. Так как эти скелетные графы изоморфны между собой, обозначим ребра графов С1,1е{\..К) через таким

образом, чтобы при изоморфизме <3 о , е {\..К} ребра ер ] еч е {Ь.Л'} сопоставлялись друг другу. Каждому графу б,.,г е {1-Х} сопоставим вектор: / = ..(7) Здесь через I,обозначена длина ребра е, ], а г, ] обозначает усредненную ширину скелетной дуги е, .. Вектор / задает признаковое описание графа б,. Введём обозначения:

N N

¿,=£/а, Л, = ]Г/-а> /е{1 ..К].

к=1 к=1

Далее введём расстояние с1(Ор,Оч) между графами Ср,Оч через признаковое описание

* (1 1

ьч

©

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

строится его скелет. Анализ топологии скелетного графа позволяет определить, в какой кластер верхнего уровня он попадает. Определив этот кластер, строим признаковое описание тестового силуэта. Используя расстояние (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. Местецкий JI.M., Цискаридзе A.K. Пространственная реконструкция локально симметричных объектов по силуэтным изображениям // Труды 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. Местецкий Л.М., Цискаридзе A.K. Восстановление в реальном времени пространственных характеристик гибкого объекта по стереопаре изображений // Доклады XIII Всероссийской конференции "Математические методы распознавания образов" (ММРО-13), Ленингр.обл., г. Зеленогорск, 2007, с. 359-363.

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

Подписано в печать: 19.11.2010

Заказ № 4629 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www.autoreferat.ru

Введение.

1 Пространственные циркулярные модели и проблема их восстановления.

1.1 Постановка задачи.

1.1.1 Проволочные модели.

1.1.2 Шарнирные модели.

1.1.3 Математическая модель камеры.

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

1.1.5 Экспериментальная база.

1.1.6 Оценка результата при реконструкции.

1.2 Анализ существующих подходов.

1.2.1 Визуальный объем.

1.2.2 Восстановление проволочных моделей.

1.2.3 Подгонка шарнирных моделей.

1.2.4 Реконструкция на основе обучения.

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

2 Метод скелетного восстановления проволочных пространственных моделей.

2.1 Непрерывное гранично-скелетное представление изображения.

2.1.1 Граница и скелет изображения.

2.1.2 Построение базового скелета.

2.2 Сегментация силуэта человека на основе анализа скелета.

2.2.1 Выделение конечностей.

2.2.2 Нахождение внутренних вершин.

2.3 Эпиполярная геометрия.

2.3.1 Основные понятия.

2.3.2 Калибровка камер.

2.3.3 Определение координат с помощью двух камер.

2.4 Восстановление позы на основе проволочной модели.

2.4.1 Структура метода.

2.4.2 Идентификация реперных точек на скелетах.

2.4.3 Решение вариационной задачи методом динамического программирования.

2.4.4 Вычисление радиусов сфер.

2.4.5 Вычислительные эксперименты.

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

3 Метод восстановления шарнирных пространственных моделей.

3.1 Предлагаемый подход к решению задачи.

3.2 Построение начального приближения.

3.2.1 Получение граничной функции ширины.

3.2.2 Выравнивание граничной функции ширины двух силуэтов.

3.2.3 Построение разметки узловых точек.

3.2.4 Построение узловых точек в пространстве.

3.3 Подгонка шарнирной модели под стереопару наблюдаемых силуэтов.

3.3.1 Определение функции различия ^, 5"2 ).

3.3.2 Минимизация функции различия.

3.4 Диаграмма работы системы.

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

4 Метод классификации формы силуэтов с окклюзиями.

4.1 Синтетическая База Эталонов.

4.2 Кластеризация Базы Эталонов.

4.3 Признаковое описание скелетных графов.

4.4 Расстояние между графами.

4.5 Классификация тестовых силуэтов.

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

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

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

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

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

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

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

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

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

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

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

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

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

Положения, выносимые на защиту:

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

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

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

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

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

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

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

Обоснование специальности

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

5) Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечениях, разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений.

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

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

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

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

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

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

4.6 Выводы по главе 4

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

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

• построение синтетической базы данных различных поз человека;

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

• построение признакового описания скелетных графов и метрики для сравнения скелетных графов для каждого кластера.

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

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

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

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

Заключение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4. 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.

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

6. Anthony J. Yezzi, Stefano Soatto. Structure From Motion for Scenes Without Features. CVPR(l) 2003.

7. Vincenzo Caglioti and Alessandro Giusti, Reconstruction of canal surfaces from single images under exact perspective, European Conference on Computer Vision (ECCV 2006).

8. A. Senior. Real-time articulated human body tracking using silhouette information. In proceedings IEEE Workshop on Visual Surveillance/PETS, Nice, France, 2003.

9. Cumani, A. and A. Guiducci. Recovering the 3D structure of tubular objects from stereo silhouettes. Pattern Recognition, 1997, volume 30, number 7.

10. Местецкий JI. M., Щетинин Д.В. Объемные примитивы Безье. Труды 11 международной конф. ГРАФИКОН-2001, Н.Новгород,

11. Minglei Tong, Yuncai Liu, Thomas S. Huang. 3D human model and joint parameter estimation from monocular image. Pattern Recognition Letters, 28 (2007).

12. Balan A.O., Sigal L., Black M.J., Davis J.E., Haussecker H.W. Detailed Human Shape and Pose from Images. Computer Vision and Pattern Recognition, 2007

13. C. Sminchisescu and B. Triggs. Kinematic Jump Processes For Monocular 3D Human Tracking. In Int. Conf. Computer Vision & Pattern Recognition, June 2003

14. Agarwal A., Triggs B. Recovering 3D human pose from monocular images. Pattern Analysis and Machine Intelligence. 2006

15. Mestetskiy L. Shape comparison of flexible objects. International Conference on Computer Vision Theory and Applications, 2007.

16. Местецкий Л. M. Непрерывный скелет бинарного растрового изображения. Труды межд. конф. Графикон-98.

17. Форсайт Д., Понс Ж. Компьютерное зрение. Вильяме, 2004.

18. Burger Т., Caplier A., Mancini S. Cued speech hand gestures recognition tool. International Conference on Computer Vision Theory and Applications, 2007.

19. Keskin C., Aran O., Akarun L. Real time gestural interface for generic applications. European Signal Processing Conference, EUSIPCO 2005.

20. Brückner M., Bajramovic F., Denzler J. Experimental evaluation of relative pose estimation algorithms. International Conference on Computer Vision Theoiy and Applications, 2008.

21. Hartley R., Zisserman A. Multiple View Geometry in Computer Vision. Second Edition, Cambridge University Press, March 2004.

22. Pillow N., Utcke S., Zisserman A. Viewpoint-invariant representation of generalized cylinders using the symmetry set. 5th British Machine Vision Conference: Image and* Vision Computing, Volume 13, Issue 5, June 1995.

23. Navab N., Appel M. Canonical Representation and Multi-View Geometry of Cylinders, International Journal of Computer Vision archive Volume 70, Issue 2.

24. A. Laurentini, "The Visual Hull Concept for Silhouette-Based Image Understanding", IEEE Transactions on Pattern Analysis and Machine Intelligence archive, Volume 16, Issue 2.

25. Forbes K., Nicolls F., De Jager G., Voigt A., Shape-from-silhouette with two mirrors and an uncalibrated camera" In Proceedings of the 9th; European Conference on Computer Vision (ECCV 2006).

26. Grasp C.T., Taylor C.J. Reconstruction of Articulated Objects from Point Correspondences in a Single Uncalibrated Image, Computer Vision and Image Understanding, 2000, volume 80.

27. J. Vijay, S. Ivekovic, E. Trucco, "Articulated Human Motion Tracking with HPSO", Proceedings of the Fourth International Conference on Computer Vision Theory and Applications, 2009 Volume 1.

28. C.Menier, E. Boyer, B. Raffin, "3D Skeleton-Based Body Pose Recovery", Proceedings of the Third International Symposium on 3D Data Processing, Visualization, and Transmission (3DPVT06), 2006.

29. M. Isard, A. Blake, "CONDENSATION—Conditional Density Propagation for Visual Tracking", International Journal of Computer Vision, Vol. 29, No. 1. (1 August 1998).

30. G. Mori, J. Malik, "Recovering 3D Human Body Configurations Using Shape Contexts", IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2006, vol. 28:

31. JI.M. Местецкий, "Скелет многосвязной многоугольной фигуры", Труды 15-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2005), 2005, Новосибирск, Россия.

32. A. Doucet, N. De Freitas, N.J. Gordon, "Sequential Monte Carlo Methods in Practice". Springer 2001.

33. J. Kennedy, R. Eberhart, "Particle Swarm Optimization". Proceedings of IEEE International Conference on Neural Networks (1995).

34. J. Franco, E. Boyer, "Exact Polyhedral Visual Hulls", In British Machine Vision Conference, 2003.

35. S. Corazza, L. Mimdermann, E. Gambaretto, G. Ferrigno, T. Andriacchi, "Markerless Motion Capture through Visual Hull, Articulated ICP and Subject Specific Model Generation", International Journal of Computer Vision, Vol. 87, No. 1. 2010.

36. S.Theodoridis, K.Koutroumbas, "Pattern Recognition", 4th Edition. Academic Press, 2006.

37. H. Blum. Biological shape and visual science (part I), Journal of Theoretical Biology, 38 (1973).43. http://artec-group.ru/3dscanning.htinl

38. Де Ванса Викрамаратне В.К. Автоматизированная система реконструирования и анализа текстурированных 3D моделей человеческих лиц. Диссертация кандидата технических наук, Моск. гос. ин-т радиотехники, электроники и автоматики, Москва, 2009.

39. Knyaz V. Photogrammetric Technique for Accurate Human Body 3D Model Reconstruction. Труды 15-ой Международной Конференции по Компьютерной Графике и Зрению (Графикон-2005), 2005, Новосибирск, Россия.

40. Козлов В.Н. Введение в математическую теорию зрительного восприятия. Москва, МГУ, 2007.

41. Шапиро JL, Стокман Дж. Компьютерное зрение. Москва, Бином, 2006.

42. Гонзалес Р., Вудс Р. Цифровая обработка изображений. Москва, Техносфера, 2006.

43. Siddiqi К., Pizer S.M. Medial representations. Mathematics, algorithms and applications. Springer, 2008.

44. Costa L., Cesar R. Shape analysis and classification, CRC Press, 2001.

45. Копылов A.B., Ермаков A.C., Татарчук А.И. Процедура совмещения изображений для формирования симметричных мер сходства // Доклады XI Всероссийской конференции "Математические методы распознавания образов" (ММРО-13), Москва, 2003.

46. Castleman K.R. Digital image processing. Prentice-Hall, New Jersey, USA, 1996.

47. Russ J.C. The image processing handbook. CRC Press LLC, USA, 1999.

48. Стронгин Р.Г. Численные методы в многоэкстремальных задачах. Москва, Наука, 1978.

49. Foley Т., Sugerman J. KD-Tree Acceleration Structures for a GPU Raytracer. Tn Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, 2005.

50. Shevtsov M., Soupikov A., Kapustin A. Highly Parallel Fast KD-tree Construction for Interactive Ray Tracing of Dynamic Scenes. In Proceedings of the EUROGRAPHICS conference, 2007.

51. Lin I-J., Kung S.Y. Video object extraction and representation: theory and applications. Kluwer Academic Publishers, Boston, USA, 2000.i