Эффективные алгоритмы сравнения поверхностей, заданных облаками точек

Дышкант, Наталья Федоровна

Эффективные алгоритмы сравнения поверхностей, заданных облаками точек тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Дышкант, Наталья Федоровна АВТОР

кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2011 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

Автореферат диссертации на тему "Эффективные алгоритмы сравнения поверхностей, заданных облаками точек"

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

484В4У1

Дышкант Наталья Федоровна

ЭФФЕКТИВНЫЕ АЛГОРИТМЫ СРАВНЕНИЯ ПОВЕРХНОСТЕЙ, ЗАДАННЫХ ОБЛАКАМИ ТОЧЕК

Специальность

01.01.09 - дискретная математика и математическая кибернетика

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

2 (1 ЮН 2011

Москва - 2011

4848494

Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М.В.Ломоносова.

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

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

Кузюрин Николай Николаевич, доктор физико-математических наук Крылов Андрей Серджевич. Ведущая организация: Институт прикладной математики

им. М. В. Келдыша РАН.

Защита диссертации состоится «17» июня 2011 г. в 11 часов на заседании диссертационного совета Д 501.001.44 в Московском государственном университете имени М.В.Ломоносова, расположенном по адресу: 119991, ГСП-1, Москва, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за 2 дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в библиотеке факультета ВМК МГУ. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.su в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».

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

Учёный секретарь / диссертационного совета ' профессор

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

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

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

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

Известно много работ, посвященных решению этой задачи. Рассматриваемые в них подходы можно отнести к двум типам. Первый тип подходов состоит в вычислении меры близости поверхностей, представленных пространственными облаками точек, на основе попарных расстояний между точками. Для двух облаков из щ и 712 точек при т итерациях подгонки вычислительная сложность такого подхода составляет 0(тгцк^тгг). При реальных размерностях задачи, когда число точек составляет 103 - 105, такие алгоритмы не могут использоваться в реальном времени работы систем машинного зрения.

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

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

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

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

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

— сравниваемые поверхности рассматриваются как кусочно-линейиые функ-

ции на триангуляциях Делоне, построенных на проекциях облаков точек на картинную плоскость;

— для сравнения функций вычисляются их значения в узлах сеток друг друга на основе линейной интерполяции;

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

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

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

— оценка асимметрии 3с1 модели человеческого лица;

— построение совместной пространственной модели лица и челюстей для задач ортодонтии;

— сегментация 3(1 модели лица на статические и динамические области по трёхмерному видеоряду.

Методы исследования. В работе использованы методы теории графов,

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

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

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

2. Эффективный в среднем 0(п 1 + пг) алгоритм локализации узлов двух триангуляций Делоне друг в друге, основанный на построении и обходе минимальных остовных деревьев триангуляций.

3. Эффективный в худшем случае 0(п 1 + Пг) алгоритм прослеживания цепочек интерфейсных граней и локализации в них узлов сеток при объединении перекрывающихся триангуляций Делоне.

4. Метод оценки асимметрии 3(1 модели человеческого лица на основе сравнения исходной и отражённой моделей поверхности лица и поиска оптимальной плоскости симметрии.

5. Метод сегментации модели поверхности лица на статические и динамические области по трёхмерной видеопоследовательности.

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

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

— всероссийская конференция «Математические методы распознавания образов» ММРО-13 (Зеленогорск, 2007 год) [1];

— XV международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2008» (Москва, 2008 год) [2];

— 7-я международная конференция «Интеллектуализация обработки информации» ИОИ'08 (Алушта, Украина, 2008 год) [3];

— 18я международная конференция по компьютерной графике и машинному зрению «ГрафиКон'08», (Москва, 2008 год) [6];

— 4я международная конференция «Машинное зрение: теория и приложения» У1ЭАРР-2009 (Лиссабон, Португалия, 2009 год) [7];

— 2-ой международный семинар «Извлечение знаний из изображений. Теория и приложения» 1МТА-2009 (Лиссабон, Португалия, 2009 год) [8];

— XVI международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009» (Москва, 2009 год) [9];

— 19я международная конференция по компьютерной графике и машинному зрению «ГрафиКон'09» (Москва, 2009 год) [10];

— всероссийская конференция «Математические методы распознавания образов» ММРО-14 (Суздаль, 2009 год) [11];

— научные семинары по совместному российско-индийскому проекту «Пространственное моделирование человеческих лиц для анализа и классификации в реальном времени» (МГУ, Москва, сентябрь 2009 года; Мангалорский университет, Мангалор, Индия, декабрь 2009 года; МГУ, Москва, октябрь 2010 года; Мангалорский университет, Мангалор, Индия, январь 2011 года);

— 8-я международная конференция «Интеллектуализация обработки информации» ИОИ'Ю (Пафос, Республика Кипр, 2010 год) [12];

— научный спецсеминар «Дискретно-непрерывные преобразования изображений в задачах распознавания» под руководством д.т.н., профессора Л. М. Местецкого, (факультет ВМК МГУ, Москва, 2010 год);

— 2-я научно-техническая конференция «Техническое зрение в системах управления» ТУСБ 2011 (ИКИ РАН, Москва, 2011 год) [14].

— 16-я международная конференция Международной ассоциации по распознаванию образов (1АР11) «Дискретная геометрия для компьютерной обработки изображений» БСС1-2011 (Нанси, Франция, 2011 год) [15].

Описания отдельных результатов работы включены в отчёты по проектам РФФИ №№08-01~00670-а, 08-07-00305-а, 09-07-92652-ИНДа, 10-07— 00609-а.

тору принадлежат разработанные методы сегментации 3с1 модели лица на статические и динамические области. В совместно опубликованных работах [1, 3, 4, 6, 7] автору принадлежат модели и методы решения задач. Публикации. Материалы диссертации опубликованы в 15 работах [1-15], из них 2 работы [13, 15], включённые в Перечень ведущих рецензируемых научных журналов и изданий, 1 статья в журнале [4], 5 статей в сборниках трудов международных научных конференций и семинаров [6-8, 10, 12], 2 статьи в сборниках трудов всероссийских научных конференций [1, 11] и 5 тезисов докладов [2, 3, 5, 9, 14].

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

Содержание работы

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

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

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

Рис. 1. Примеры однозначной поверхности (слева), нерегулярной сетки (в центре), регулярной сетки (справа).

в следующем: даны две однозначные поверхности, заданные облаками точек, требуется сравнить эти поверхности (вычислить некоторую меру сходства/различия).

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

В разделе 1.3 представлен обзор существующих методов сравнения поверхностей объектов. Качество метода сравнения обычно зависит от соотношения между точностью полученной оценки сходства и его вычислительной сложностью. Известные методы для сопоставления поверхностей можно разделить на два класса: 1) подгонка на основании вычисления расстояний между точками в трёхмерном пространстве, которая имеет большую вычислительную сложность; 2) пересчёт исходных данных в двумерные регулярные сетки, при котором возникает избыточность, приводящая также к существенному повышению вычислительной сложности.

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

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

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

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

В разделе 2.1 формулируется следующая постановка задачи. Пусть однозначные поверхности £1 и 5г заданы облаками точек {(^Ьг/Ь^)}^ и {(хг2, у\, соответственно в системе координат Охуг в Е3, так, что 51, £>2

однозначно проецируются на плоскость Оху. Пусть д\ и д^ — нерегулярные двумерные сетки, узлы которых есть проекции исходных облаков точек и 5г на плоскость Оху:

92 = {(ХШ-:у (!)

Рассмотрим функции /1 и /2, заданные в узлах сеток д\ и </2 соответственно так, что:

й = ¿ = /2(4. У\) = 4 (2)

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

Пусть б — множество нерегулярных двумерных сеток, содержащихся внутри некоторого объемлющего прямоугольника Я, а Р1 — множество однознач-

ных функций, заданных на сетках из множества G. Функция / аппроксимирует f на множестве узлов сетки g € G, если f = f в узлах д.

Пусть /ь/г € F; функции fi и /2 непрерывны в Е2 и аппроксимируют /1 и /2 на множествах узлов сеток gi и g2 соответственно. Будем называть сетку j = й U й общей, или объединённой, сеткой. Будем считать, что исходные сетки состоят из непересекающихся множеств узлов: gi П рг = 0. Тогда количество узлов в сетке g равно Л*" = JVi + А^г-

Вводится мера различия между поверхностями, представляющая собой среднее расстояние между двумя функциями по всем точкам объединённой сетки — среднее осевое расстояние:

PttUuh) = £ \fi(x,y)-f2(x,y)\/N. (3)

(зд)ег

В реальных данных образуются шумовые эффекты — выбросы. Для подавления таких шумов вводится мера отсечённого осевого расстояния pif

paM = axgmm{p\K(p)>aN}, (4)

К(р) = |{г : |/j — /¿I ^ р}| — количество точек, в которых значения функций отличаются не более чем на величину р, a G [0,1]—заданный пороговый уровень допустимых шумовых выбросов.

Пусть Ti = T(gi), Т2 = T(g2) и Т = T(g) — триангуляции Делоне, построенные на сетках д\, д^ и объединённой сетке g соответственно. Триангуляцию Т будем называть объединённой триангуляцией Делоне (ОТД).

Вводится понятие взвешенного объёма разности между поверхностями на треугольной области, ограниченной узлами А, В, С:

| l/i(z.2/) - /2(2;, у) I ц(х,у) dxdy, (5)

1/м(Л,В,С,/1,/2) =

Д АВС

где ^ 0 —функция, определяющая вес (значимость) различия срав-

ниваемых поверхностей в точке {х,у). Будем считать, что ц{х,у) определена

и конечна во всех точках выпуклой оболочки Сот(д) множества д, равна нулю вне Сопь(д) и интегрируема.

Уц при является метрикой Ь\ для функций /1 и /2 на ААВС.

Пусть 8с(щу{д) площадь выпуклой оболочки множества д, равная сумме площадей всех треугольников триангуляции множества д\

Зсту(д) ~ £ ЗъАВС-ДЛВСеГ

Вводится мера различия поверхностей на ОТД:

РУ^ьк)= £ / Зсспу(д)- (6)

ллвсет

Суммирование в (6) ведётся по всем треугольникам объединённой триангуляции Т. Мера ру^ является полуметрикой.

Теорема 1. Для введённой функции руД/1, /2) выполнены все аксиомы метрики, за исключением, быть может, неравенства треугольника.

Если в качестве функции ц(х,у) взять тождественную единицу, сходство всех фрагментов поверхностей будет учитываться с одинаковым весом. Обозначим через V значение (5) при р(х,у) = 1 на Сопу(д), а через ру — соответствующую (6) меру сравнения:

М/1,/а) == £ У{А,В,С,Ь,Ь)/ Бсоп^у (7)

длвсет

Плотностью сетки д мощности N будем называть величину Зсти(д)/М.

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

Предлагается модифицировать меру ру так, чтобы она учитывала только репрезентативные данные —те области, где сосредоточены точки обеих сеток, т. е, те треугольники ОТД Т, которые не входят ни в одну из триангуляции Т\ и Г2 исходных сеток. Пусть 5<тЦд) ~ суммарная площадь таких треугольников.

Вводится следующая модификация меры ру.

№у(/Ь/2)= £ У(А,В,С,1ьЬ) /5Мг). (8)

ААВСеТ-.

ААВС(Т„

ААВС£Т2

Определение 1. Грани ОТДТ, построенной на множестве узлов сетки д = 31 и 52, соединяющие узлы из разных исходных сеток д\ и д2, будем называть интерфейсными гранями.

Меру рду (8) будем называть мерой различия на интерфейных гранях ОТД (рис.2).

Рис. 2. Две триангулированные сетки (слева) и ОТД с закрашенными интерфейсными гранями (справа).

Утверждение 2. Мера (8) является частным случаем меры (6): РэИ/ь к) = РуЛ!1, /г) при ц = р,*:

1, (х,у)еААВС:ААВСеТ.,

А АБС £ Тг иААВС £ Т2; О, иначе.

Для вычисления мер Рм,Рм>РУц необходимы значения обеих функций /ь /2 в каждой точке объединённой сетки д.

В разделе 2.2 предлагается алгоритм сравнения поверхностей объектов, позволяющий эффективно (с точки зрения сложности вычислений) вычислять введённые меры рм^р'м, Ру^-

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

1. Построение триангуляций Делоне 7\, Т2 на множествах узлов сеток д\, <й соответственно;

2. Локализация узлов каждой из триангуляций в треугольниках другой триангуляции;

3. Интерполяция значений функции Д, /2 в узлах сеток 52,9\ соответственно на основе результатов локализации;

4. Построение ОТД Т на сетке д\

5. Сравнение функций /1,/2 на отдельных гранях ОТД. Вычисление меры р.

Рассматривается задача геометрического поиска — локализации узла в триангуляции. Приводится обзор существующих методов её решения. Показывается, что наиболее быстрые методы решения задачи локализации узла в триангуляции из N узлов имеют сложность 0(\ogN) и требуют 0(И) памяти. В задаче локализации сетки из N1 узлов в триангуляции из N2 узлов возникает массовый запрос на решение задачи локализации узла. Неструктурированный массовый запрос из N1 узлов может быть обработан за время \0gN2). Показывается, как можно использовать дополнительную информацию о том, что сетка представлена триангуляцией Делоне для получе-

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

Лемма 3. Пусть узлы сеток gi,g2 с мощностями Ari, iV2 соответственно распределены равномерно в прямоугольнике и Ni/N2 ^ с = const. Тогда среднее количество пересечений МОД множества узлов д\ с рёбрами триангуляции Делоне, построенной на узлах 52, линейно по N2-

Теорема 4. В условиях леммы 3 алгоритм локализации множества узлов сетки д\ в триангуляции Делоне, построенной на множестве узлов gi, на основе МОД имеет линейную по max(JVi, N2) вычислительную сложность в среднем.

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

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

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

В разделе 2.3 предлагаются алгоритмы перечисления интерфейсных граней для вычисления меры рду (8) и локализации узлов сетки в триангуляции Делоне на основе списка интерфейсных граней. Также предлагается модификация алгоритма Ар сравнения поверхностей для случая использова-

ния меры рду (8). Получены теоретические оценки сложности предложенных алгоритмов.

Множество интерфейсных граней разбивается на несколько непересекающихся подмножеств, каждое из которых является цепочкой из смежных по рёбрам треугольников: либо замкнутой (циклической), в которой все интерфейсные ребра являются внутренними рёбрами ОТДТ, либо разомкнутой, в которой крайние треугольники имеют хотя бы одну граничную сторону, т.е. сторону выпуклой оболочки Сопу{д) (см. рис. 3). Алгоритм выделения всех интерфейсных граней сводится к прослеживанию цепочек из таких граней.

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

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

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

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

Утверждение 5. Задача прослеживания цепочек интерфейсных граней линейно сводится к задаче локализации лоскутов в триангуляции.

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

Предложенный алгоритм выделения интерфейсных граней состоит из следующих этапов:

1. Поиск начального стартера;

2. Прослеживание цепочки граней, соответствующей найденному стартеру;

3. Поиск очередного стартера. Если стартер найден, перейти к предыдущему пункту, иначе закончить.

Теорема 6. Алгоритм выделения всех интерфейсных граней имеет сложность 0(ЛГ), где N — общее число узлов в объединённой сетке.

Теорема 7. Локализация сетки в триангуляции на основе списка интерфейсных граней может быть осуществлена за время О (И) в худшем случае.

Для вычисления меры рду (8) предлагается алгоритм АРву — модификация алгоритма Ар, состоящая в том, что вместо этапа локализации сеток в триангуляции на основе обхода МОД производятся два этапа: поиска интерфейсных граней и локализации сеток на основе списка найденных интерфейсных граней.

Теорема 8. Алгоритм APsv имеет вычислительную сложность О (TV log N).

Следствие 8.1. При построенных на этапе предобработки триангуляциях Делоне Tí, Т2 вычислительная сложность алгоритма Apsv равна O(N).

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

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

Обозначим через М движение в пространстве Е3, состоящее в последовательных поворотах на углы сем, Рм, 7м вокруг осей Ox, Оу, Oz соответственно и параллельного переноса на вектор Дм — Az^).

Пусть однозначная поверхность S задана облаком точек с координатами {{xi,yi, f(xi,yi))}f=l в пространстве Е3. Будем рассматривать движения М, не выводящие 5 из класса поверхностей, однозначно проецируемых на плоскость, на которой расположено множество точек {(£¿,í/í)}Hi- Обозначим через /м образ / при движении М.

Рассматривается оптимизационная задача:

P(flJ2M)^mm. (10)

Минимизация в задаче (10) производится по 6 параметрам преобразования ам, Рм, тм, определяющим движение М.

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

подгонке, затратив к^М) на предобработку при построении триангуляции Делоне.

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

В разделе 3.1 сформулирована постановка задачи оценки асимметрии лица по 3<1 модели: вводятся формальные понятия симметрии и асимметрии для модели, предлагается количественная оценка асимметрии. Описывается разработанный метод для вычисления такой оценки, основанный на сравнении исходной и отражённой масок лица и поиске оптимальной плоскости симметрии исходной маски (рис. 4). Приводится описание базы трёхмерных моделей человеческих лиц, на которой проводились эксперименты. Получено экспериментальное подтверждение устойчивости предложенной оценки. Исследована зависимость между оценкой асимметрии модели и количеством точек в ней.

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

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

Входными данными в задаче являются 3(1 модель лица 5, полученная при нейтральном выражении лица снимающегося, и трёхмерный видеоряд — последовательность трёхмерных моделей лица ..., £)„.

Рис. 4. Примеры исходных масок и их отражений относительно плоскостей симметрии. Более тёмным цветом выделены участки лица, на которых исходная маска выше отражён-

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

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

Список публикаций по теме диссертации

1. Дышкант Н. Ф., Местецкий Л. М. Сравнение 3D портретов при распознавании лиц // Докл. всеросс. конф. Математические методы распознавания образов-13. — М: МАКС Пресс, 2007. - С. 314-316.

2. Дышкант Н. Ф. Операции над функциями, заданными на разных нерегулярных двумерных сетках // Сборник тезисов XV Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2008». — М: МАКС Пресс, 2008.-С.32.

3. Дышкант Н. Ф., Местецкий Л. М. Оценка асимметрии лица по трёхмерному портрету // Интеллектуализация обработки информации (ИОИ-2008): Тез. докл. Междунар. науч. конф. — Симферополь: Крымский НЦ НАН Украины, 2008.-С. 94-96.

4. Дышкант Н. Ф., Местецкий Л. М. Оценка асимметрии лица по трёхмерному портрету // Таврический вестник информатики и математики. — 2008.— №1.-С. 189-198.

5. Дышкант Н. Ф. Метод сравнения формы пространственных объектов // Сборник тезисов лучших дипломных работ 2008 года. — Москва: Изд. отдел ф-та ВМК МГУ, 2008. - С. 69-70.

6. Дышкант Н. Ф., Местецкий Л. М. Сравнение однолистных поверхностей, полученных при 3D сканировании // Труды 18й международной конференции по компьютерной графике и машинному зрению ГрафиКон'2008. — Москва, МГУ, 2008.-С.270-277.

7. Dyshkant N., Mestetskiy L. Estimation of Asymmetry in 3D Face Models // Proceedings of International conference on computer vision theory and applications (VISAPP 2009).-Lisbon, Portugal: INSTICC Press, 2009.-Pp.402-405.

8. Dyshkant N. Disparity Measure Construction for Comparison of 3D Objects' Surfaces // Proceedings of the Workshop IMTA.- Lisbon, Portugal: INSTICC

Press, 2009.-Pp.43-52.

9. Дъшкант H. Ф. Оценка мимической динамики движения челюсти в процессе жевания по трёхмерному видеоряду // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009». — М: МАКС Пресс, 2009.-С.28.

10. Гордеев Д. В., Дъшкант Н. Ф. Построение модели динамики движения челюсти человека в процессе жевания по серии трёхмерных изображений // Труды 19й международной конференции по компьютерной графике и машинному зрению ГрафиКон'2009. - Москва, МГУ, 2009. - С. 348-352.

11. Гордеев Д. В., Дъшкант Н. Ф. Сегментация модели лица на статические и динамические области по трёхмерной видеопоследовательности // Докл. все-росс. конф. Математические методы распознавания образов-14. — М: МАКС Пресс, 2009. - С. 329-332.

12. Дъшкант, Н. Ф. Сравнение поверхностей, заданных на неструктурированных сетках и сетках разной плотности // Доклады 8-й Международной конференции «Интеллектуализация обработки информации» (ИОИ-2010). —М.: МАКС Пресс, 2010. - С. 339-342.

13. Dyshkant N. An algorithm for calculating the similarity measures of surfaces represented as point clouds // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications.— 2010.— Vol.20, no. 4.— Pp. 495-504.

14. Дъшкант H. Ф. Сравнение и подгонка поверхностей при решении прикладных задач анализа 3d портретов человеческих лиц // Тез. докл. конф. Техническое зрение в системах управления-2011. — Москва, ИКИ РАН, 2011. — С. 76-77.

15. Dyshkant N. Measures for surface comparison on unstructured grids with different density // Lecture Notes in Computer Science: Discrete Geometry for Computer Imagery. - 2011. - Vol. 6607. - Pp. 501-512.

Напечатано с готового оригинал-макета

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. Подписано в печать 13.05.2011 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 205. Тел. 939-3890. Тел./факс 939-3891. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 627 к.

Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Дышкант, Наталья Федоровна

Введение.

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

1.1. Задача сравнения поверхностей.

1.1.1. Представление объекта облаком точек.

1.1.2. Основные определения.

1.1.3. Общая постановка задачи сравнения поверхностей

1.2. Способы задания поверхностей.

1.2.1. Сетки регулярной структуры.

1.2.2. Сетки нерегулярной структуры.

1.3. Обзор методов сравнения поверхностей.

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

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

Известно много работ, посвященных решению этой задачи. Рассматриваемые в них подходы можно отнести к двум типам. Первый тип подходов состоит в вычислении меры близости поверхностей, представленных пространственными облаками точек, на основе попарных расстояний между точками. Для двух облаков из пх и П2 точек при т итерациях подгонки вычислительная сложность такого подхода составляет О (га 774 к^пг). При реальных размерностях задачи, когда число точек составляет 103 - 105, такие алгоритмы не могут использоваться в реальном времени работы систем машинного зрения.

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

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

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

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

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

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

2. Эффективный в среднем 0(п1 +П2) алгоритм локализации узлов двух триангуляций Делоне друг в друге, основанный на построении и обходе минимальных остовных деревьев триангуляций.

3. Эффективный в худшем случае 0(п\ + П2) алгоритм прослеживания цепочек интерфейсных граней и локализации в них узлов сеток при объединении перекрывающихся триангуляций Делоне.

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

XV международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2008» (Москва, 2008 год) [8];

7-я международная конференция «Интеллектуализация обработки информации» ИОИ'08 (Алушта, Украина, 2008 год) [9];

18я международная конференция по компьютерной графике и машинному зрению «ГрафиКон'08», (Москва, 2008 год) [14];

4я международная конференция «Машинное зрение: теория и приложения» У18АРР-2009 (Лиссабон, Португалия, 2009 год) [50];

2-ой международный семинар «Извлечение знаний из изображений. Теория и приложения» 1МТА-2009 (Лиссабон, Португалия, 2009 год) [49];

XVI международная научная конференция студентов, аспирантов и молодых учёных «Ломоносов-2009» (Москва, 2009 год) [12]; и

19я международная конференция по компьютерной графике и машинному зрению «ГрафиКон'09» (Москва, 2009 год) [3]; всероссийская конференция «Математические методы распознавания образов» ММРО-14 (Суздаль, 2009 год) [4]; научные семинары по совместному российско-индийскому проекту «Пространственное моделирование человеческих лиц для анализа и классификации в реальном времени» (МГУ, Москва, сентябрь 2009 года; Мангалорский университет, Мангалор, Индия, декабрь 2009 года; МГУ, Москва, октябрь 2010 года; Мангалорский университет, Мангалор, Индия, январь 2011 года);

8-я международная конференция «Интеллектуализация обработки информации» ИОИ'Ю (Пафос, Республика Кипр, 2010 год) [15]; научный спецсеминар «Дискретно-непрерывные преобразования изображений в задачах распознавания» под руководством д.т.н., профессора Л. М. Местецкого, (факультет ВМК МГУ, Москва, 2010 год);

2-я научно-техническая конференция «Техническое зрение в системах управления» ТУСБ 2011 (ИКИ РАН, Москва, 2011 год) [13].

16-я международная конференция Международной ассоциации по распознаванию образов (ГАРИ,) «Дискретная геометрия для компьютерной обработки изображений» 0001-2011 (Нанси, Франция, 2011 год) [51].

Описания отдельных результатов работы включены в отчёты по проектам РФФИ Ж№08-01-00670-а, 08-07-00305-а, 09-07-92652-ИНДа, 10-07— 00609-а.

Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена совместно с научным руководителем. В совместных публикациях в трудах конференций [3, 4] автору принадлежат разработанные методы сегментации 3с1 модели лица на статические и динамические области. В совместно опубликованных работах [7, 9, 10, 14, 50] автору принадлежат модели и методы решения задач. Публикации. Материалы диссертации опубликованы в 15 работах [3, 4, 715, 48-51], из них 2 работы [48, 51], включённые в Перечень ведущих рецензируемых научных журналов и изданий, 1 статья в журнале [10], 5 статей в сборниках трудов международных научных конференций и семинаров [3, 14, 15, 49, 50], 2 статьи в сборниках трудов всероссийских научных конференций [4, 7] и 5 тезисов докладов [8, 9, 11-13].

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

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

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

В заключении подводятся итоги работы.

Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

3.4. Основные выводы

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

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

3. Сформулирована численная постановка задачи, оценки асимметрии лица по трёхмерной модели: введены формальные понятия симметрии и асимметрии для модели, предложена количественная оценка асимметрии.

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

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

Заключение

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

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

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

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

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

Список источников диссертации и автореферата по математике, кандидата физико-математических наук, Дышкант, Наталья Федоровна, Москва

1. Амелин В. ВКнязь В. А. Объединение фрагментов трёхмерной модели объекта // Труды 12й международной конференции по компьютерной графике и машинному зрению ГрафиКон'2002. — Нижний Новгород, 2002. — С.99-103.

2. Ахо А., Хопкрофт Дснс., Ульман Дж. Построение и анализ вычислительных алгоритмов: Пер. с англ. А. О. Слисеико. — Москва: Издательство «Мир», 1979. 536 с.

3. Гордеев Д. В., Дышкант Н. Ф. Сегментация модели лица на статические и динамические области по трёхмерной видеопоследовательности // Докл. всеросс. конф. Математические методы распознавания образов-14. — М: МАКС Пресс, 2009. — С. 329-332.

4. Дзараев Ч. Р., Персии Л. С., Порохин А. Ю. Применение ЗБ сканеров при диагностики зубочелюстных аномалий (МГМСУ) // Доклады Всероссийского научно-практического форума «Дентал-Ревю — 2010». — Москва, 2010.

5. Делоне Б. Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934. 4. -С.793-800.

6. Дышкант Н. Ф., Местецкий Л. М. Сравнение ЗБ портретов при распознавании лиц // Докл. всеросс. конф. Математические методы распознавания образов-13. М: МАКС Пресс, 2007. - С. 314-316.

7. Дышкант Н. Ф. Операции над функциями, заданными на разных нерегулярных двумерных сетках // Сборник тезисов XV Международной научной конференции студентов, аспирантов и молодых учёных «Ломоно-сов-2008». М: МАКС Пресс, 2008. - С. 32.

8. Дышкант Н. Ф., Местецкий Л. М. Оценка асимметрии лица по трёхмерному портрету / / Интеллектуализация обработки информации (ИОИ-2008): Тез. докл. Междунар. науч. копф. — Симферополь: Крымский НЦ НАН Украины, 2008. С. 94-96.

9. Дышкант Н. Ф., Местецкий Л. М. Оценка асимметрии лица по трёхмерному портрету // Таврический вестник информатики и математики. — 2008. — № 1.-С. 189-198.

10. Дышкант Н. Ф. Метод сравнения формы пространственных объектов // Сборник тезисов лучших дипломных работ 2008 года. — Москва: Изд. отдел ф-та ВМК МГУ, 2008. С. 69-70.

11. Дышкант Н. Ф. Оценка мимической динамики движения челюсти в процессе жевания по трёхмерному видеоряду // Сборник тезисов XVI Международной научной конференции студентов, аспирантов и молодых учёных «Ломоносов-2009». — М: МАКС Пресс, 2009.-С. 28.

12. Дышкант Н. Ф. Сравнение и подгонка поверхностей при решении прикладных задач анализа 3(1 портретов человеческих лиц // Тез. докл. конф. Техническое зрение в системах управления-2011. — Москва, ИКИ РАН, 2011.-С. 76-77.

13. Дышкант Н. Ф., Местецкий Л. М. Сравнение однолистных поверхностей полученных при 3D сканировании // Труды 18й международной конференции по компьютерной графике и машинному зрению Графи-Кон'2008.- Москва, МГУ, 2008. С. 270-277.

14. Дышкант Н. Ф. Сравнение поверхностей, заданных на неструктурированных сетках и сетках разной плотности // Доклады 8-й Международной конференции «Интеллектуализация обработки информации» (ИОИ-2010). — М.:МАКС Пресс, 2010. С. 339-342.

15. Колесов А., Павлова О. Пакет Surfer — обработка и визуализация двумерных функций // КомпьютерПресс. — 1999. — N2 2/99.

16. Кормен Т., Лейзереон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО: БИНОМ. Лаборатория знаний, 2004, —960 с.

17. Костюк Ю. Л., Фукс А. Л. Визуально гладкая аппроксимация однозначной поверхности, заданной нерегулярным набором точек // Геоинформа-тика-2000: Труды международной научно-практической конференции. — Томск: Изд-во Томского ун-та, 2000. — С. 41-45.

18. Костюк Ю. Л. Графический поиск с использованием триангуляции и клеточного разбиения // Вестник Томского гос. ун-та. — 2002. — № 275. — С.147-152.

19. Кэмп М. С., Вот В. В., Филип Э., Картер К. С., Губта С С. Старение периорбитальной области: количественный анализ // Инъекционные методы в косметологии. — 2010.— №4.

20. Левицкий В. В. Разработка системы трёхмерной визуализации лица и зубных рядов и её применение в стоматологической клинике: Автореф. дис. канд. мед. наук: 14.00.21 / ЦНИИС и 4JIX.-M., 2008.-23 с.

21. Марков К. Н., Ширков П. Д. Алгоритмы сглаживания поверхностей, заданных на нерегулярных сетках // Матем. моделирование. — 2009. — Т. 21, №6.-С. 69-78.

22. Местецкий Л. М. Непрерывная морфология бинарных изображений: фигуры, скелеты, циркуляры. — М.:ФИЗМАТЛИТ, 2009. —288 с.

23. Местецкий Л. М., Царик Е. В. Триангуляция Делоне: рекурсия без пространственного разделения точек // Труды международной конференции по компьютерной графике и машинному зрению ГрафиКон'2004. — Москва, МГУ, 2004. С. 267-270.

24. Местецкий Л. М., Царик Е. В. Слияние неразделённых триангуляций Делоне // Сложные системы: обработка информации, моделирование и оптимизация: Сборник научных трудов. Вып. 2.—Тверь: Тверской гос. университет, 2004. С. 216-231.

25. Оноприйко М.Д., Попов Е. В. Создание NURBS поверхностей в системе трёхмерного компьютерного моделирования КЗ // Труды международной конференции по компьютерной графике и машинному зрению Графи-Кон'2001 Нижний Новгород, 2001. - С. 145-149.

26. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. —М.: Мир, 1989. —478 с.

27. Скворцов А. В. Обзор алгоритмов построения триангуляции Делоне // Вычислительные методы и программирование. — 2002. — № 3 — С. 14-39.

28. Скворцов А. В. Триангуляция Делоне и её применение. — Томск: Изд-во Томского ун-та, 2002. — 128 с.

29. Скворцов А. В., Костюк Ю. JI. Эффективные алгоритмы построения триангуляции Делоне // Геоинформатика. Теория и практика. — № 1. — Томск: Изд-во Томского ун-та, 1998. — С. 22-47.

30. Форсайт Д., Понс Ж. Компьютерное зрение. Современный подход.— Изд-во Вильяме, 2004. — 928 с.

31. Яблонский С. В. Введение в дискретную математику: Учеб. пособие для вузов.— 2-е изд., перераб. и доп. — М.: Наука. Гл. ред. физ.-мат. лит., 1986.-394 с.

32. Alliez P., Ucelli G., Gotsman С., Attene М. Recent Advances in Remeshing of Surfaces // Shape Analysis and Structuring: Mathematics and Visualization:. 2008. — Pp. 53-82.

33. Pierre Alliez, Giuliana Ucelli, Craig Gotsman and Marco Attene

34. Bern M., Eppstein D. Mesh generation and optimal triangulations — In D. Z. Du and F.K. Hwang, editors, Computing in Euclidean Geometry. World Scientific Publishing Co., 1992.-78 p.

35. Besl P., McKay H. A method for registation of 3-d shapes // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1992. — Vol. 14, no. 2.-Pp. 239-256.

36. Boissonnat J.-D., Teillaud M. Effective Computational Geometry for Curves and Surfaces — Springer-Verlag Berlin Heidelberg, 2006.— 343 p.

37. Bose P., Devroye L. Intersections with Random Geometric Objects // Computational Geometry: Theory and Applications. —1998.— Vol, 10, no. 3,-Pp. 139-154.

38. Brunelli R., Poggio T. Face recognition: features versus templates // IEEE Transactions on Pattern Analysis and Machine Intelligence. — 1993. — Vol. 15, no. 10.-Pp. 1042-1052.

39. Brunnstrom;K., Stoddart A. J. Genetic algorithms for free-form surface matching // Proc. ICPR. -1996. Pp. 689-693.

40. Chen Y., Medioni G. Object modelling by registration of multiple range images // Image and Vision Computing. — 1992.—Vol. 10, no. 3. — Pp. 145-155.

41. Cheriton D., Tarjan R. E. Finding minimum spanning trees // SIAM J. Comput. 1976. - Vol. 5, no. 4. - Pp. 724-742.

42. Cignoni P., Roccini C., Scopigno R. Metro: measuring error on simplified surfaces // Computer Graphics Forum, Blackwell Publishers. —1998. — Vol.17, no. 2.-Pp. 167-174.

43. Clarkson K. A randomized algorithm for closest point queries // SIAM J. Computing. — 1998. — Vol. 17. — Pp. 830-847.

44. Devillers O., Pion STeillaud M. Walking in a triangulation // Internat. J. Found. Comput. Sci. 13. 2002. - Pp. 181-199.

45. Devroye L., Lemaire C., Moreau J. Expected time analysis for Delaunay point location // Computational geometry. — 2004. — Vol. 29, no. 2.— Pp. 61-89.

46. Devroye L., Mucke E. P., Zhu B. A note on point location in Delaunay triangulations of random points // Algorithmica. — 1998. — Vol. 22. — Pp. 477-482.

47. Dyshkant N. An algorithm for calculating the similarity measures of surfaces represented as point clouds // Pattern Recognition and Image Analysis: Advances in Mathematical Theory and Applications. — 2010.—Vol.20, no. 4. Pp. 495-504.

48. Dyshkant N. Disparity Measure Construction for Comparison of 3D Objects' Surfaces // Proceedings of the Workshop IMTA. — Lisbon, Portugal: INSTICC Press, 2009. Pp. 43-52.

49. Dyshkant N., Mestetskiy L. Estimation of Asymmetry in 3D Face Models // Proceedings of International conference on computer vision theory and applications (VISAPP 2009). Lisbon, Portugal: INSTICC Press, 2009.-Pp. 402-405.

50. Dyshkant N. Measures for Surface Comparison on Unstructured Grids with Different Density // Lecture Notes in Computer Science: Discrete Geometry for Computer Imagery. 2011. - Vol. 6607. - Pp. 501-512.

51. EggertD.W., Larusso A., Fisher R. B. Estimating 3-D rigid body transformations: a comparison of four major algorithms // Machine Vision and Applications. —1997. Vol. 9, no. 5-6. — Pp. 272-290.

52. Enciso R., Memon A., Fidaleo D. A., Neumann U., Mah J. The Virtual Craniofacial Patient: 3D Jaw Modeling and Animation // The 11th Annual Medicine Meets Virtual Reality Conference. — 2003. — Pp. 65-71.

53. Fary I. On straight-line representations of planar graphs // Acta a Sci. Math. (Szeged). -1948. Vol. 11. - Pp. 229-233.

54. Fan T., Medioni G., Nevatia R. Recognizing 3D objects using surface descriptions // IEEE PAMI. -1989. Vol. 11, no. 11. - Pp. 1140-1157.

55. Feldmar J., Ayache N., Betting F. D-2D projective registration of free-form curves and surfaces // CVIU. -1997. Vol. 65. - Pp. 403-424.

56. Tarjan R. E. Data Structures and Network Algorithms — Society for Industrial and Applied Mathematics, 1983. — 131 p.

57. Friedman J. H., Bentley J. L., Finkel R. A. An Algorithm for Finding Best Matches in Logarithmic Expected Time // ACM Transactions on Mathematical Software. —1977. — Vol. 3, no. 3. — Pp. 209-226.

58. Gatzke T., Zelinka S., Grimm C., Garland M. Curvature Maps for Local Shape Comparison // In: Shape Modeling International. — 2005. — Pp. 244-256.

59. G elf and N., Ikemoto L., Rusinkiewicz S., Levoy M. Geometrically Stable Sampling for the ICP Algorithm // Fourth International Conference on 3D Digital Imaging and Modeling. 2003. - Pp. 260—267.

60. Godin G., Rioux M., Baribeau R. Three-dimensional registration using range and intensity information // Proceedings of the SPIE. — 1994. — Vol. 2350. — Pp. 279—290.

61. Gordon G. G. Face recognition based on depth maps and surface curvature // In SPIE Geometric Methods in Computer Vision. — 1991.— Vol. 1570.— Pp. 234—247.

62. Gruen A., Akca D. Least Squares 3D Surface and Curve Matching // ISPRS Journal of Photogrammetry and Remote Sensing. — 2005. — Vol. 59. — Pp. 151-174.

63. Gu X., GortlerS.J., Hoppe H. Geometry images // Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings. — 2002.-Pp. 355-361.

64. Guskov I., VidimceK., Sweldens W., Schroeder P. Normal meshes // Computer graphics proceedings, annual conference series: SIGGRAPH conference proceedings. — 2000. — Pp. 95-102.

65. Hajeer M. Y., Millet D. T., Ayoub A. F., Siebert J. P. Applications of 3D imaging in orthodontics // Journal of Ortodontics. — 2004. — Vol. 31, no. 1. — Pp. 62-70.

66. Haran I., Helperin D. An Experimental Study of Point Location in Planar Arrangements in Cgal // ACM Journal of Experimental Algorithms. — 2009. — Vol.13, no. 3.-Pp. 1-31.

67. Huang J., Heisele B., Blanz V. Component-based Face Recognition with 3D Morphable Models //In International Conference on Audio- and Video-Based Biométrie Person Authentication (AVBPA-03). 2003. - Pp. 27-34.

68. Kirkpatrik D. G. Optimal search in planar subdivisions // SIAM J. Comput. 1983. - Vol. 12, no. 1. - Pp. 28-35.

69. Koidis PPatias PTsioukas V. 3D Visualization of Dental Data for Virtual Treatment Planning // ISPRS Congress Istanbul 2004, Proceedings of Commission V 2004. - Pp. 996-1001.

70. Koseki M., Niitsuma A., Inou N., Maki K. Three-dimensional Display System of Individual Mandibular Movement // Complex Medical Engineering, (Springer), 2007. - Pp. 117-127.

71. Knyaz V. A., Zheltov S. Yu. Photogrammetric Techniques for Dentistry Analysis, Planning and Visualisation // ISPRS Congress Beijing 2008, Proceedings of Commission V. — 2008. — Pp. 783-788.

72. Lee D. T., Schachter B. J. Two Algorithms for Constructing a Delaunay Triangulation // International Journal of Computer and InformationI

73. Science. 1980. - Vol. 9, no. 3. - Pp. 219-242.

74. Liu Y., Rodrigues M. A. Geometrical analysis of two sets of 3D correspondence data patterns for the registration of free-form shapes //J. Int. and Rob. Systems. 2002. - Vol. 33. - Pp. 409-436.

75. Mccool C., Cook J., Chandran V., Sridharan S. Feature Modelling of PCA Difference Vectors for 2D and 3D Face Recognition //In Video and Signal Based Surveillance, AVSS '06. IEEE International Conference. 2006.— Pp.57.

76. MitraNJ., GuibasL.J., Pauly M. Partial and approximate symmetry detection for 3D geometry // In ACM SIGGRAPH. 2006. - Pp. 560 568.

77. Mitra S., Lazar N., Liu Y. Understanding the Role of Facial Asymmetry in Human Face Identification // Statistics and Computing. — 2007.— Vol. 17. — Pp. 57-70.

78. Mitra S., Liu Y. Local Facial Asymmetry for Expression Classification // Proceedings the 2004 IEEE Conference on Computer Vision and Pattern Recognition (CVPR'04). 2004. - Vol. 2 - Pp. 889-894.

79. Mohan A., Papageorgiou C., Poggio T. Example-based object detection in images by components //In IEEE Transactions on Pattern Analysis and Machine Intelligence. — 2001. — Vol. 23, no. 4. — Pp. 349-361.

80. NelderJ.A., Mead R. A simplex method for function minimization // Computer Journal. 1965. - Vol. 7. Pp. 308-313.

81. Ohbuchi R., Takei T. Shape-similarity comparison of 3D models using alpha shapes // Proceedings of the 11th Pacific Conference on Computer Graphics and Application. 2003. - Pp. 293-302.

82. Prim R. C. Shortest connecting networks and some generalizations // Bell Systems Techn. J. 1957. - Vol. 36. - Pp. 1389-1401.

83. Shamos M. I. Computational geometry. — Ph.D. thesis, Dept. of Comput. Sci., Yale Univ.-1978.

84. Shapiro M. A note on Lee and Schachter's algorithm for Delaunay triangulation // Inter. Jour, of Comp. and Inf. Sciences. —1981. —Vol. 10, no. 6.-Pp. 413-418.

85. Schenk T. Digital Photogrammetry. — Terra-Science, Laurelville, Ohio, 1999.-428 p.

86. Slingsby A. An Object-Orientated Approach to Hydrological Modelling using Triangular Irregular Networks // Proceedings of GISRUK03, City University, London, UK.-2003.

87. Stepanyants D. G., Knyaz V. A. PC-Based Digital CloseRange Photogrammetric System for Rapid 3D Data Input in CAD Systems // International Archives of Photogrammetry and Remote Sensing. — 2000. — Vol. 33, Part B5. Pp. 756-763.

88. Szymczak A., Rossignac J., King D. Piecewise regular meshes: Construction and compression / / Graphical Models. — 2002. — Vol. 64, no. 3-4. — Pp. 183-198.

89. Tarjan R. E. Fibonacci heaps and their uses in improved network optimization algorithms // Journal of the Association for Computing Machinery. 1987. - Vol. 34, no. 3. - Pp. 596-615.

90. Teng K., Liu Y. Expression Classification using Wavelet Packet Method on Asymmetry Faces // tech. report CMU-RI-TR-06-03, Robotics Institute, Carnegie Mellon University. — January 2006.

91. Tomaka A. The application of 3d surfaces scanning in the facial features analysis // Journal of Medical Informatics and Technologies. — 2005. — Pp. 233-240.

92. Turk G., Levoy M. Zippered polygon meshes from range images // Proc. SIGGRAPH. -1994. Pp. 311-318.

93. Vaillant M., Glaunes J. Surface matching via currents // Lecture Notes in Computer Science: Information Processing in Medical Imaging. — 2005. — Vol. 3565. Pp. 1-5.

94. Zhang Z. Iterative point matching for registration of freeform curves and surfaces // International Journal of Computer Vision. — 1994. — Vol. 13, no. 2.-Pp. 119-152.