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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Практическая значимость состоит в разработке эффективных алгоритмов сравнения поверхностей, позволяющих существенно расширить круг решаемых задач, в частности, в системах машинного зрения, требующих работы в режиме реального времени. Результаты работы могут найти применение в медицине, геоинформатике, биометрической идентификации. Апробация работы. Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах: всероссийская конференция «Математические методы распознавания образов» ММРО-13 (Зеленогорск, 2007 год) [7];

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−670-а, 08−07−305-а, 09−07−92 652-ИНДа, 10−07— 609-а.

Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена совместно с научным руководителем. В совместных публикациях в трудах конференций [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].

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

Список литературы

включает 97 наименований. Текст работы иллюстрируется 58 рисунками и 9 таблицами.

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

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

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

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

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

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

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

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

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

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

Заключение

.

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

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

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

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

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