Модели и алгоритмы построения криволинейных скелетов пространственных форм тема автореферата и диссертации по математике, 01.01.09 ВАК РФ
|
Хромов, Денис Валерьевич
АВТОР
|
||||
|
кандидата физико-математических наук
УЧЕНАЯ СТЕПЕНЬ
|
||||
|
Москва
МЕСТО ЗАЩИТЫ
|
||||
|
2012
ГОД ЗАЩИТЫ
|
|
01.01.09
КОД ВАК РФ
|
||
|
|
||||
Московский государственный университет имени М.В. Ломоносова
На правах рукописи
Ок
005051689
Хромов Денис Валерьевич
Модели и алгоритмы построения криволинейных скелетов пространственных
форм
01.01.09 - дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук
11 АПР ¿013
Москва - 2013
005051689
Работа выполнена на кафедре математических методов прогнозирования факультета вычислительной математики и кибернетики Московского государственного университета имени М. В. Ломоносова.
Научный руководитель: доктор технических наук, профессор
Местецкий Леонид Моисеевич
Официальные оппоненты: доктор физико-математических наук,
профессор, член-корреспондент РАН Щепин Евгений Витальевич кандидат физико-математических наук Конушин Антон Сергеевич
Ведущая организация: Институт систем обработки изображений РАН
Защита состоится 26 апреля 2013 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова, расположенном по адресу: 119991, Москва, Ленинские горы, МГУ имени М.В. Ломоносова, 2-й учебный корпус. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформленя заявки на пропуск).
С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте ВМК МГУ http://cs.msu.ru в разделе «Наука» — «Работа диссертационных советов» — «Д 501.001.44».
Автореферат разослан '-^^рг^С^ 2013 г.
Ученый секретарь диссертационного совета
остенко Валерий Алексеевич
Общая характеристика работы
Актуальность темы В настоящее время возникает большое количество практических задач, связанных с анализом формы трёхмерных объектов. Это связано с широким распространением устройств, позволяющих получать цифровые трёхмерные модели объектов реального мира. Такие модели, как правило, представляют собой вексельные изображения, облака точек или полигональные поверхности. Все эти структуры данных на практике обладают очень большой размерностью и в явном виде не содержат в себе информации о форме исходных трёхмерных объектов с «человеческой» точки зрения. Проблема распознавания формы пространственных объектов, описанных таким образом, является весьма актуальной в различных приложениях. Поэтому задача распознавания формы может вызывать существенные трудности. Кроме того, зачастую требуется построить алгоритмы, работающие в режиме реального времени, что накладывает дополнительные ограничения на эффективность.
В задачах анализа формы плоских изображений хорошо зарекомендовало себя применение аппарата непрерывных скелетов. Скелетом двумер-'ной области обычно называется её серединная ось — множество центров максимальных вписанных в эту область кругов. Скелет плоской области представляет собой планарную укладку некоторого графа, удачно схватывающего основные геометрические свойства фигуры. Визуально скелет выглядит как утончение исходной формы до набора одномерных линий. Извлекать из такого графа признаковую информацию для задач распознавания и классификации значительно проще, чем из исходного гранично-контурного описания двумерной области.
Существует аналогичный подход в задачах обработки трёхмерных изображений. Серединная ось области в трёхмерном пространстве определяется как множество центров максимальных вписанных в эту область шаров.
Однако в отличие от двумерного случая, трёхмерная серединная ось не является укладкой графа в пространстве и в общем случае представляет собой двумерное стратифицированное многообразие. Это множество может обладать очень сложной внутренней структурой, поэтому его применение зачастую не приводит к существенному упрощению решаемой задачи.
Поэтому существует большая потребность в математической модели, описывающей аналог двумерной серединной оси в трёхмерном пространстве именно как пространственную укладку некоторого графа. В литературе такие объекты принято называть криволинейными скелетами (curve-skeletons). Несмотря на большое количество публикаций по этой теме, общего строгого определения криволинейного скелета до сих пор не существует. В одной из наиболее полных обзорных работ1 криволинейный скелет неформально определяется как одномерное представление трёхмерного объекта; в качестве формальных критериев перечислены свойства, выполнение которых желательно для хороших математических моделей скелетов. К этим свойствам относятся сохранение топологии, инвариантность относительно изометрических преобразований, возможность реконструкции исходного объекта по скелету, минимальная толщина (для вексельных изображений), центрированность, достоверность, возможность основанной на структуре скелета сегментации, устойчивость к малым преобразованиям поверхности объекта, гладкость образующих скелет кривых, наличие иерархических отношений между различными элементами скелета.
В многочисленных публикациях обычно предлагаются разнообразные эвристики для построения скелетов, при этом формального математического определения скелета не даётся. Существующие попытки формализовать понятие криволинейного скелета пока не привели к выработке общепринятой математической модели. В качестве наиболее известного примера мож-
1 Cornea N., Silver D. Curve-skeleton properties, applications, and algorithms // IEEE Transactions on Visualization and Computer Graphics. 2007. Vol. 13. P. 530-548.
но привести определение скелета как множества центров максимальных вписанных в исходный объект шаров, таких, что их точки касания могут быть соединены как минимум двумя различными геодезическими линиями по поверхности объекта2. Однако определяемый таким образом скелет в общем случае не является одномерным (он может содержать двумерные страты для объектов, поверхность которых не является гладкой).
К настоящему моменту накоплено очень большое количество способов построения криволинейных скелетов. Идеи, на которых эти подходы основаны, чрезвычайно разнообразны. При этом общепризнанного формального определения не существует (в отличие от двумерного случая, где использование серединной оси в качестве непрерывного скелетного представления области практически не имеет сравнимых альтернатив). Таким образом, не существует какого-либо обоснованного метода для оценки и сравнения различных подходов между собой, если не считать таковым визуальную оценку качества скелетов, получаемых при помощи различных алгоритмов. Поэтому актуальной является задача построения общего определения трёхмерного криволинейного скелета, а также математического аппарата для строгой численной оценки качества различных конкретных способов построения скелетов.
Цель диссертационной работы Целью настоящей работы является исследование и разработка математической модели трёхмерных криволинейных скелетов, позволяющей проводить строгую оценку качества различных конкретных способов построения скелетов, а также построение эффективных алгоритмов, действующих в рамках заданной модели. Для того, чтобы продемонстрировать практическую полезность предлагаемого подхода,
2 Dey Т., Sun J. Defining and computing curve-skeletons with medial geodesic function // Proceedings of the fourth Eurographics symposium on Geometry processing. SGP '06. Aire-laVille, Switzerland, Switzerland: Eurographics Association, 2006. P. 143-152.
необходима практическая реализация разработанных алгоритмов.
Предлагаемый подход основан на аппроксимации исходного трёхмерного объекта при помощи пространственных циркуляров — геометрических примитивов, для которых криволинейный скелет определяется однозначно. Циркуляры, с одной стороны, могут рассматриваться в качестве приближенного представления трёхмерных объектов самой разнообразной формы, а с другой — для них естественным и однозначным образом вводится понятие криволинейного скелета. Отсюда вытекает основная идея метода: всякую трёхмерную фигуру можно с некоторой погрешностью аппроксимировать при помощи пространственного циркуляра, тогда скелетом этой фигуры можно считать скелет аппроксимируюущего её циркуляра. При этом численной оценкой качества скелета является величина погрешности аппроксимации.
Таким образом, алгоритм построения криволинейного скелета сводится к аппроксимации фигуры пространственным циркуляром. Такая аппроксимация выполняется в два шага. Сначала ищется начальное приближение циркуляра, топология осей которого хорошо воспроизводит топологию искомого скелета. Затем происходит итеративная подгонка приближенного циркуляра согласно используемому критерию качества.
Научная задача Основная задача настоящей работы заключается в разработке общей математической модели криволинейных скелетов. Важно, чтобы при этом было дано строгое и обоснованное определение, предоставляющее возможность численно оценить качество скелета. Критерий качества должен иметь ясный физический смысл и соответствовать интуитивным представлениям о том, что такое трёхмерный криволинейный скелет; кроме того, практическая ценность этого критерия должна быть явным образом продемонстрирована на реальных примерах.
Для того, чтобы оценить полезность предлагаемого подхода, в работе рассматриваются как конкретные алгоритмы построения локально оптимальных скелетов в рамках предложенной модели, так и их практические приложения.
Методы исследования Работа носит теоретико-экспериментальный характер. Теоретическая часть содержит в себе элементы дифференциальной геометрии, вычислительных методов, теории графов, теории сложности алгоритмов и вычислений. Для проведения экспериментов создан специализированный программный комплекс, входными данными для которого послужили как синтетические трёхмерные модели, так и модели реальных объектов, полученные методами трёхмерного сканирования.
Научная значимость состоит в разработке формальной математической модели криволинейных скелетов. Предложенная модель даёт теоретическую основу для разработки и сравнения алгоритмов скелетизации пространственных объектов. Наличие численной меры качества скелетов позволяет формулировать задачу трёхмерной скелетизации как задачу оптимизации некоторой функции; в работе описан основанный на этом подходе алгоритм, использующий численные методы для уточнения получаемых скелетов.
Практическая значимость Трёхмерные криволинейные скелеты находят широкое применение в многочисленных задачах анализа формы трёхмерных изображений. В работе предлагаются эффективные алгоритмы построения скелетов, которые могут быть использованы в практических приложениях (например, в медицине, биометрической идентификации, распознавании жестов).
На защиту выносятся следующие научные результаты:
7
• Математическая модель трёхмерных криволинейных скелетов, основанная на аппроксимации исходного трёхмерного объекта при помощи пространственных циркуляров, для которых криволинейный скелет определяется однозначно.
о Мера близости между циркуляром и пространственным объектом, основанная на скелетном отображении — продолжении гомотопии, связывающей внутреннюю область объекта и оси циркуляра, на поверхность объекта.
• Метод построения трёхмерных скелетов при помощи численной оптимизации меры близости, описывающей точность аппроксимации исходного объекта пространственным циркуляром.
• Алгоритм построения начального приближения скелета при помощи графов Риба поверхности исходного пространственного объекта.
• Алгоритм построения начального приближения скелета при помощи двумерных скелетов плоских проекций, основанный на оценке качества проекций при помощи введённой меры близости.
• Алгоритм итеративной оптимизации меры близости методом наискорейшего градиентного спуска, в котором вычисление градиента и шага осуществляется на основе скелетного отображения.
Апробация работы Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:
• научно-техническая конференция «Техническое зрение в системах управления» TVCS 2011 (Москва, Россия, 2011 год) [2];
• международная конференция «Advanced Concepts for Intelligent Vision Systems» ACIVS 2011 (Гент, Бельгия, 2011 год) [4];
8
• всероссийская конференция «Математические методы распознавания образов» ММРО-15 (Петрозаводск, Россия, 2011 год) [1];
• международная конференция «21th International Conference on Computer Graphics and Vision» GraphiCon 2011 (Москва, Россия, 2011 год) [7];
• международная конференция «24th Canadian Conference on Computational Geometry» CCCG 2012 (Шарлоттаун, Канада, 2012 год) [8];
• ярославская международная конференция «Дискретная геометрия», посвященная 100-летию А.Д. Александрова (Ярославль, Россия, 2012 год) [6].
Описания отдельных результатов работы включены в отчёты по проектам РФФИ 11-01-00783, 12-07-31107.
Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена совместно с научным руководителем.
Публикации по теме диссертации в изданиях списка ВАК: [3, 4]. Другие публикации по теме диссертации: [1, 2, 5-8].
Структура и объём диссертационной работы. Работа состоит из оглавления, введения, четырёх глав, заключения и списка литературы. Содержание работы изложено на 133 страницах. Список литературы включает 59 наименований.
Содержание работы
Введение содержит общую характеристику работы, обоснование актуальности темы исследования, цели и задачи диссертационного исследова-
ния.
В первой главе рассматривается общая постановка задачи построения трёхмерных криволинейных скелетов, проведен обзор существующих подходов к решению этой задачи.
В разделе 1.1 содержится краткий обзор существующих способов цифрового геометрического описания трёхмерных объектов, и указаны прикладные области, в которых возникают задачи, связанные с анализом трёхмерных форм.
В разделе 1.2 рассматривается понятие серединной оси области П С К".
Определение 1. Серединной осью открытого ограниченного множества П С К™ называется множество точек этого множества, для которых существует не менее двух ближайших точек на границе этого множества:
М = {а 6 Г2|Эх,у е да-.х^у, ||а - х|| = ||а - у||, Уг € Ш||а-г|| > ||а-х||}.
Перечислены основные свойства серединных осей. Показано, что серединные оси плоских объектов представляют собой геометрические графы и потому используются в задачах распознавания двумерных изображений, но серединные оси трёхмерных объектов являются существенно более сложным объектом (двумерным стратифицированным многообразием), поэтому их практическое применение ограничено.
В разделе 1.3 вводится понятие трёхмерного криволинейного скелета, представляющего собой обобщение плоской серединной оси для трёхмерных объектов; в ряде практических задач применение криволинейных скелетов оказывается более проодуктивным по сравнению с использованием
трёхмерных серединных осей. Проведен обзор публикаций, посвящённых построению трёхмерных скелетов; показано, что несмотря на разнообразие существующих алгоритмов и наличие общего интуитивного представления о том, что должен представлять собой криволинейный скелет, математического определения трёхмерного криволинейного скелета не существует. Поэтому анализ и сравнение существующих алгоритмов между собой на практике трудновыполнимы и обычно сводятся к визуальной оценке результатов, получаемых тем или иным алгоритмом.
Во второй главе описана предлагаемая математическая модель трёхмерных криволинейных скелетов. В основе модели лежит сведение скеле-тизации к аппроксимации трёхмерной формы при помощи набора жирных кривых — пространственных объектов, для которых криволинейный скелет определяется естественным образом. При этом скелет исходного объекта определяется как объединение осевых линий жирных кривых, а мера сходства, относительно которой производится аппроксимация, является численной оценкой качества полученного скелета.
В разделе 2.1 вводится понятие жирной кривой как объединения шаров, центры которых расположены на некоторой гладкой кривой (рис. 1); анализируются некоторые свойства жирных кривых.
Определение 2. Пусть 7 — гладкая кривая в R", не имеющая особых точек. Пусть, кроме того, на ней задана неотрицательная гладкая функция г
г: 7 R+, (2)
которая не обращается в нуль нигде, кроме, может быть, концевых точек7. Тогда жирной кривой с осью 7 и радиальной функцией г называется множество точек
jr(7f r) = {а е Rn|3x € 7 = IIa - х|| < г(х)} . (3)
11
Концевые точки кривой 7 называются вершинами жирной кривой.
Рис. 1: Жирная кривая и её ось.
Определение 3. Пусть 7 - жирная кривая вГ с осью 7 и радиальной функцией г, причём ось и радиальная функция параметризованы на отрезке от 0 до 1. Огибающей поверхностью жирной кривой Т называется огибающая семейства п-мерных шаров
если такая огибающая существует.
Теорема 1. Для того, чтобы у жирной кривой существовала огибающая, необходимо и достаточно, чтобы для всех 0 < t < 1 выполнялось
|г|< ||У7||.
В качестве частного случая жирных кривых, удобных для практического применения, предложен класс жирных кривых Безье.
Определение 4. Пусть заданы (к + 1) точка
В(і) = {хєМ" : ||х-7(г)||2 <г\і),0 <Ь < 1}
(4)
Р0> Рь • • ■ > Рк Є К'
п
(5)
и (к + 1) неотрицательное число
Г0,Гі, ... ,гк Є 1+.
(6)
Тогда жирной кривой Безъе порядка к с опорным множеством (р»,Г{) называется жирная кривая с осью
к
7 (*) = Х>ЬЛЮ (7)
¿=0
и радиальной функцией
к
Г(і) = у£гіЬ№, (8)
¿=0
где Ъ\ — полиномы Берпштейна
и
= О»
В разделе 2.2 вводится понятие пространственного циркуляра, представляющего собой объединение жирных кривых (рис. 2); описывается применение циркуляров для аппроксимации трёхмерных объектов.
Определение 5. Пусть V — конечное множество точек Ип. Циркуляром С с множеством вершин V называется объединение конечного множества жирных кривых, вершины которых содержатся в V.
Определение 6. Графом связности циркуляра с множеством вершинУ называется граф, множество вершин которого совпадает с множеством V, а две вершины иг этого графа соединены ребром тогда и только тогда, когда пространственный циркуляр содержит в себе жирную кривую с парой концевых вершин Уі,г>2-
Пространственный циркуляр представляет собой фигуру, составленную из набора примитивов (жирных линий). Пусть задана некоторая мера близости между фигурами в Мп (например, метрика Хаусдорфа; подробнее вопрос о выборе меры близости рассматривается в разделе 2.3), тогда можно поставить задачу об аппроксимации произвольной фигуры циркуляром с заданной погрешностью. Если для фигуры П построен аппроксимирующий её циркуляр С, то естественно определить скелет П как множество осей циркуляра.
Определение 7. Пусть Г2 — ограниченная область в Мп, С — аппроксимирующий её циркуляр. Тогда оси циркуляра С называются криволинейным скелетом фигуры £1.
Взаимосвязь между трёхмерной формой и аппроксимирующим её циркуляром описывается в терминах скелетной гомотопии и скелетного отображения. Скелетная гомотопия является математической формализацией интуитивного представления о скелете как о некотором «утончении» исходной формы; скелетное отображение, вычисляемое для заданной скелетной гомотопии, описывает взаимосвязь между граничными точками формы и точками скелета.
Определение 8. Пусть П — фигура, £1 — её замыкание, А — оси аппроксимирующего её циркуляра, причём Л С П. Скелетной гомотопией называется непрерывное отображение
Р1: [0; 1] х О -> А, (10)
такое, что для всех х £ П выполнено
Г(0,х) = х,Г(1,х)еД (11)
где А = А\Агегггч ^етт ~ множество точек, каждая из которой является концевой ровно для одной кривой из множества осей жирных кривых, составляющих С.
Определение 9. Пусть даны фигура £1, аппроксимирующий её циркуляр С с осями Л и скелетная гомотопия х). Скелетным отображением а называется функция, которая каждой граничной точкех 6 дС1 ставит в соответствие пересечение замыканий
а(х) = П^(1,Пе(х)), (12)
£>0
где
Пе(х) = {у еП: ||х-у|| <е}. (13)
Теорема 2. Скелетное отображение а каждой точке границы дП ставит в соответствие непустое замкнутое подмножество осей циркуляра.
В разделе 2.3 описывается мера сходства, задающая погрешность аппроксимации фигуры пространственным циркуляром. Показано, что меры, традиционно используемые при сравнении подмножеств М" (например, метрика Хаусдорфа), не подходят для решения задачи скелетизации в рамках описываемой модели. Предложена мера, основанная на использовании скелетного отображения.
Определение 10. Погрешностью аппроксимации объекта П циркуляром С называется величина
е(П,С)= шах (||х-у||2-г2(у))2сг5, (14)
и уеа(х) хея=ап
где г(у) — значение радиальной функции в точке у € С, а сг(х) — скелетное отображение.
В разделе 2.4 задача аппроксимации формы циркуляром рассмотрена для плоских многоугольных фигур. Показано, что предложенная модель действительно является обобщением двумерного скелета: серединная ось
плоской многоугольной области является осью циркуляра, аппроксимирующего эту область с нулевой погрешностью.
Определение 11. Плоская фигура О называется многоугольной, если её граница Ш представляет собой объединение конечного числа отрезков прямых линий.
Теорема 3. Для всякой плоской многоугольной фигуры О, существует совпадающий с ней циркуляр, оси которого совпадают с серединной осью этой фигуры.
Теорема 4. У жирных линий циркуляра, порождённого серединной осью плоской многоугольной фигуры, существуют огибающие.
Теорема 5. Пусть Г2 — плоская многоугольная фигура. Тогда существует скелетное отображение, связывающее фигуру и порождённый её серединной осью циркуляр, для которого погрешность аппроксимаи^1ие{£1, С) равна нулю.
Таким образом, в рамках предложенной модели оптимальным двумерным криволинейным скелетом является плоская серединная ось. Это даёт теоретическое обоснование практической полезности модели, т.к. серединная ось является общепринятым способом задания скелетов двумерных изображений.
В главе 3 описаны алгоритмы построения скелетов, основанные на использовании численного критерия качества, позволяющего решать задачу трёхмерной скелетизации как обычную задачу численной оптимизации. Решение состоит из двух этапов: построения начального приближения и последующей оптимизации этого начального приближения численными методами.
В разделе 3.1 вводятся основные определения и допущения, используемые в описываемых алгоритмах. Предполагается, что телоП представлено в виде множества, ограниченного полигональной поверхностью с множеством вершин множеством рёбер <£ и множеством граней
В качестве жирных кривых используются жирные кривые Безье первого порядка. Алгоритмы строят только такие скелетные отображения, которые каждой граничной точке х € дП ставят в соответствие единственную точку скелета сг(х) £ С (а не некоторое множество, как в общем случае, согласно теореме 2). Погрешность аппроксимации вычисляется приближенно как дискретная сумма по вершинам полигональной модели.
Определение 12. Пусть трёхмерная фигураП задана полигональной моделью. Дискретной погрешностью аппроксимации объекта П циркуляром С называется величина
ё(Я,С) = £ (||х - <т(х)||2 - Г>(х)))2 , (15)
хеОЗ
где 27 — множество вершин полигональной модели.
В разделе 3.2 описывается алгоритм построения начального приближения, основанный на применении графов Риба.
Определение 13. Пусть / — непрерывная вещественная функция, заданная на компактном многообразии М. Линией уровня функции / называется максимальное связное подмножество М, на котором / принимает постоянное значение.
Определение 14. Пусть / — непрерывная вещественная функция, заданная на компактном многообразии М. Графом Риба функции / называется факторпространство многообразия М
Я/ = М/ 17
где~/ —отношение эквивалентности, такое, что
х~/у,х,у еМ (17)
тогда и только тогда, когда х, у принадлежат одной и той же линии уровня функции /.
Граф Риба является топологическим пространством на множестве линий уровня некоторой функции /, заданной на поверхности объекта Г2 (см. рис. 3).
Рис. 3: Линии уровня функции, порождающей граф Риба.
Приведены процедуры, необходимые для построения скелета на основе данного подхода: вычисление функции / и дискретизация её уровней относительно полигональной сетки (93, Зг), построение графа Риба и его вложения в пространство R3.
Алгоритм. Построение начального приближения скелета_
Вход:
93 — вершины трёхмерной модели; б — рёбра трёхмерной модели. Выход:
С — начальное приближение пространственного циркуляра.
1: function Начальное_приближение(93, <£) 2: / Порождающая _функция(93, <£)
3: Rf <r- Граф_Риба(/, 2J, <£)
4: С Вложение_графа_Риба(і?/) 5: return С 6: end function
В разделе 3.3 описывается алгоритм построения начального приближения, основанный на вычислении двумерных серединных осей плоских проекций объекта П. В общем случае выбор плоской проекции, позволяющей получить адекватный трёхмерный криволинейный скелет, представляет собой нетривиальную задачу; в настоящей работе она решается при помощи численного критерия, позволяющего оценить качество получаемых скелетов. Общая схема алгоритма показана на рис. 4.
Л
ж
іі : I а
Рис. 4: Модель лошади, серединная ось плоской проекции и полученный в результате трёхмерный криволинейный скелет.
Обозначим через § единичную сферу в К3:
§ = {рЄІ3: ||р|| = 1}. (18)
Определение 15. Проекцией множества X С К3 вдоль вектора р Є § называется параллельная проекция Ргр(Х) множества X на плоскость Пр, проходящую через начало координат и перпендикулярную вектору р.
Пр = {х Є І3 : (р, х) = 0}. (19)
Обозначим через СР(Г2) процедуру построения пространственного циркуляра по двумерной серединной оси плоской проекции Ргр(П). Тогда зада-
19
ча выбора оптимальной плоской проекции сводится к минимизации функции
p* = argndne(ii,Cp(n))- (20)
В работе описана простейшая реализация этого подхода, основанная на применении метода Монте-Карло.
В разделе 3.4 описан численный алгоритм оптимизации пространственного циркуляра С относительно меры сходства e(2J, С). Используется метод наискорейшего спуска. Приведены формулы, по которым происходит выис-ление промежуточных значений функции и её градиента.
Обозначим вектор из всех переменных, описывающих циркуляр, через
Z. _
Алгоритм. Численная оптимизация пространственного циркуляра_
Вход:
Z0 — описание начального приближения; е — требуемая точность численного метода. Выход:
Z — описание оптимизированного циркуляра.
1: function Оптимизация_циркуляра(^о, е)
2: к*-0
3: repeat
4: д«- Ve{Zk)
5: А <- Величина_шага(Zk, д)
6: Zk+i = Zk~ Хд
7: к к + 1
8: until \i{Zk) - s{Zk-i)\ <£ 9: retUm Zk 10: end function
Теорема 6. Последовательность значений дискретной погрешности аппроксимации ¿(2'к) сходится.
Итерационная процедура может приводить к возникновению радиальных функций с отрицательными значениями. Эта проблема разрешается путём расширения модели и введения понятия обобщённой жирной кривой (рис. 5), радиальная функция которой может принимать отрицательные значения. Доказано, что обобщённые жирные кривые могут быть представлены в виде объединения жирных кривых в смысле определения 2, поэтому алгоритм корректен в рамках используемой математической модели.
Рис. 5: Обобщённая линейная жирная кривая и её ось.
Определение 16. Обобщённой линейной жирной кривой называется множество
Лр(1),Р(а),г«,гт) = {абК3|34€[0;1]: ||ф(1) + (1 _ ¿)р(2) _ а|| < 1^(1) + (1 _ ¿)г(2)|},
где
Р(1))Р(2) 6К3)Г(1))Г(2) €М. (22)
Теорема 7. Всякая обобщённая жирная кривая ЛР(1),Р<2),г(1),г(2)) может быть представлена в виде линейной жирной кривой или пространственного циркуляра, состоящего из двух линейных жирных кривых.
В разделе 3.5 проведен анализ вычислительной сложности описанных алгоритмов.
Теорема 8. Итерация алгоритма численной оптимизации методом градиентного спуска имеет вычислительную сложность 0(\Щ).
Теорема 9. Алгоритм построения начального приближения пространственного циркуляра при помощи графов Риба имеет вычислительную сложность 0(|<Е| 1о§|0?|).
Теорема 10. Алгоритм построения начального приближения при помощи плоских проекций имеет вычислительную сложность 0(\Щ2).
В главе 4 описана практическая реализация алгоритмов, продемонстрированы результаты проведенных вычислительных экспериментов.
В разделе 4.1 приведена техническая информация, связанная с деталями программной реализации. Перечислены используемые технологии, описаны основные структуры данных.
и=
Рис. 6: Примеры криволинейных скелетов и пространственных циркуляров.
В разделе 4.2 приведены результаты проведенных вычислительных экспериментов. Продемонстрированы результаты работы алгоритмов для различных изображений (рис. 6). Подробно показаны различные этапы работы алгоритмов, существенно зависящих от адекватности меры сходства между трёхмерным объектом и аппроксимирующим её циркуляром; сюда относятся выбор оптимальной плоской проекции при построении начального приближения и итеративная подгонка численными методами.
В разделе 4.3 проведен обзор свойств, которым должен удовлетворять алгоритм скелетизации согласно общепринятыми представлениям. Показано, что большая часть из этих свойств выполняется или может быть выполнена при некоторых модификациях описанных алгоритмов.
В заключении сформулированы основные результаты диссертационной работы.
Список публикаций по теме диссертации
1. Местецкий JI.., Хромов Д.. Криволинейные скелеты трёхмерных форм // Доклады 15-й Всероссийской конференции «Математические методы распознавания образов». 2011.
2. Хромов Д.. Построение трёхмерных криволинейных скелетов при помощи пространственных циркуляров // Научно-техническая конференция «Техническое зрение в системах управления». Тезисы докладов. 2011.
3. Хромов Д.. Трехмерные циркуляры и криволинейные скелеты // Известия ВУЗов. Математика. 2012. по. 4. Р. 90-99.
4. Khromov D.. Curve-skeletons based on the fat graph approximation // Proceedings of the 13th international conference on Advanced concepts for intelligent vision systems. ACIVS'll. Berlin, Heidelberg: Springer-Verlag, 2011. P. 239-248.
5. Khromov D.. 3D circular shapes and curve skeletons // Russian Mathematics (Iz VUZ). 2012. Vol. 56. P. 75-83. 10.3103/S1066369X1204010X.
6. Khromov D.. A Numerical Approach of the Curve-Skeletons Problem // Yaroslavl International Conference "Discrete Geometry"dedicated to the centenary of A.D. Alexandrov. 2012.
7. Khromov D.., Mestetskiy L.. 3D Curve-Skeletons Extraction and Evaluation // Proceedings of the 21th International Conference on Computer Graphics and Visionth (GraphiCon 2011). 2011.
8. Khromov D.., Mestetskiy L.. 3D Skeletonization as an Optimization Problem // In Proceedings of the 24th Canadian Conference on Computational Geometry. 2012.
Напечатано с готового оригинал-макета
Подписано в печать 22.03.2013 г. Формат 60x90 1/16. Усл.печл. 1,0. Тираж 70 экз. Заказ 080.
Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. Тел./факс 8(495)939-3891.
Московский государственный университет имени М.В.Ломоносова Факультет вычислительной математики и кибернетики
На правах рукописи
04201355640
Хромов Денис Валерьевич
Модели и алгоритмы построения криволинейных скелетов пространственных форм
01.01.09 - дискретная математика и математическая кибернетика
Диссертация па соискание учёной степени кандидата физико-математических наук
Научный руководитель
доктор технических наук, профессор
Местецкий Леонид Моисеевич
Москва - 2012
Содержание
Введение ............................................................5
Глава 1. Трёхмерные криволинейные скелеты: постановка задачи........................................................15
1.1. Трехмерные формы и связанные с ними прикладные задачи........................................................15
1.2. Серединная ось ............................................16
1.3. Криволинейный скелет....................................19
1.3.1. Понятие криволинейного скелета................19
1.3.2. Свойства криволинейных скелетов..............20
1.3.3. Алгоритмы построения..............23
1.4. Основные выводы.....................25
Глава 2. Математическая модель криволинейных скелетов ..............................................................28
2.1. Жирные кривые............................................28
2.2. Пространственные циркуляры и криволинейные скелеты .............................33
2.3. Мера близости между формой и аппроксимирующим пространственным циркуляром .............40
2.4. Аппроксимация плоской многоугольной фигуры .... 45
2.5. Основные выводы..........................................54
Глава 3. Алгоритмы построения скелетов................56
3.1. Общая схема алгоритма....................................56
3.2. Построение первого приближения при помощи графов Риба..........................................................59
3.2.1. Графы Риба........................................59
3.2.2. Порождающая функция..........................66
3.2.3. Вложение графа Риба..............68
3.3. Построение первого приближения при помощи плоских проекций........................72
3.3.1. Общая идея....................72
3.3.2. Построение трёхмерного криволинейного скелета по плоской проекции........................76
3.3.3. Выбор оптимальной плоской проекции.....86
3.4. Численная оптимизация ..................................88
3.4.1. Использование градиентного метода......88
3.4.2. Вычисление промежуточных значений.....91
3.4.3. Корректность алгоритма..........................95
3.5. Анализ вычислительной сложности алгоритма.....99
3.5.1. Построение первого приближения при помощи графов Риба........................................99
3.5.2. Построение первого приближения при помощи плоских проекций.................100
3.5.3. Оптимизация методом градиентного спуска . . 102
3.6. Основные выводы.....................103
Глава 4. Вычислительный эксперимент..........106
4.1. Практическая реализация ................106
4.2. Экспериментальная проверка модели..........109
4.3. Свойства алгоритма....................113
4.4. Основные выводы.....................120
Заключение.............................122
Литература.............................124
Введение
Диссертационная работа посвящена определению и алгоритмам построения криволинейных скелетов трёхмерных моделей. Вводится общее определение скелета как набора осей некоторой циркулярной фигуры, аппроксимирующей исходную трёхмерную модель. Для этой аппроксимации задана функция погрешности, позволяющая численно оценить качество получаемого скелета.
Актуальность темы В настоящее время возникает большое количество практических задач, связанных с анализом формы трехмерных объектов. Это связано с широким распространением устройств, позволяющих получать цифровые трёхмерные модели объектов реального мира. Такие модели, как правило, представляют собой вексельные изображения, облака точек или полигональные поверхности. Все эти структуры данных на практике обладают очень большой размерностью и в явном виде не содержат в себе информации о форме исходных трехмерных объектов с «человеческой» точки зре-пя. Поэтому генерация признаков в таких задачах может вызывать существенные трудности. Кроме того, зачастую требуется построить алгоритмы, работающие в режиме реального времени, что накладывает дополнительные ограничения па эффективность.
В задачах анализа формы плоских изображений хорошо зарекомендовало себя примсиспис аппарата непрерывных скелетов. Скс-
летом двумерной области называют плаиарную укладную некоторого графа, удачно схватывающего основные геометрические свойства фигуры. Визуально скелет выглядит как утончение исходной формы до набора одномерных линий. Извлекать признаковую информацию из такого графа значительно проще, чем из исходного гранично-контурного описания двумерной области. Обычно скелет двумерной области определяется как сё серединная ось — множество центров максимальных вписанных в эту область кругов [19] (хотя существуют и другие модели, например, прямолинейные скелеты — straight skeletons [131).
Было бы естественно применить аналогичный подход для обработки трёхмерных изображений. Серединная ось области в трёхмерном пространстве определяется как множество центров максимальных вписанных в эту область шаров. Однако в отличие от двумерного случая, трёхмерная серединная ось не является укладкой графа в пространство, так как может содержать в себе фрагменты двумерных поверхностей. Такое множество поверхностей может обладать очень сложной внутренней структурой, поэтому его использование не приводит к существенному упрощению процедуры генерации признаков.
Тем не менее, существует большая потребность в математической модели, описывающей аналог двумерной серединной оси в трёхмерном пространстве именно как пространственную укладпу пското-
рого графа. В литературе такие объекты принято называть криволинейными скелетами (curve-skeletons). Несмотря на большое количество публикаций по этой теме, общего строгого определения криволинейного скелета до сих пор не существует [24]. В многочисленных публикациях обычно предлагаются разнообразные эвристики для построения скелетов, при этом криволинейный скелет определяется как то, что получается на выходе описываемых авторами алгоритмов. Это означает, что не существует какого-либо обоснованного метода для оценки и сравнения различных подходов между собой, если не считать таковым визуальную оценку качества скелетов, получаемых при помощи различных алгоритмов.
Такое положение дел сохраняется в том числе потому, что понятие криволинейного скелета хорошо понятно на иитуитивпом уровне. Поэтому визуальная оценка качества того или иного подхода к решению задачи в ряде случаев может быть вполне уместной. Однако к настоящему моменту накоплено очень большое количество способов построения криволинейных скелетов. Идеи, на которых эти подходы основаны, чрезвычайно разнообразны. При этом общепризнанного определения до сих пор IIC найдено (в отличие от двумерного случая, где использование серединной оси в качестве непрерывного скелетного представления области практически пе имеет сравнимых альтернатив). Поэтому чрезвычайно актуальной является задача построения общего определения трёхмерного криволинейного скелета.
а также математического аппарата для строгой численной оценки качества различных конкретных способов построения скелетов.
Цель диссертационной работы Целыо настоящей работы является исследование и разработка математической модели трёхмерных криволинейных скелетов, позволяющей проводить строгую оценку качества различных конкретных способов построения скелетов, а также построение эффективных алгоритмов, действующих в рамках заданной модели. Для того, чтобы продемонстрировать практическую полезность предлагаемого подхода, необходима практическая реализация разработанных алгоритмов.
Предлагаемый подход основан на использовании специальных геометрических примитивов — пространственных циркуляров. Циркуляры, с одной стороны, могут рассматриваться в качестве приближенного представления трёхмерных объектов самой разнообразной формы, а с другой — для них естественным и однозначным образом вводится понятие криволинейного скелета. Отсюда вытекает основная идея метода: всякую трёхмерную фигуру можно с некоторой погрешностью аппроксимировать при помощи пространственного циркуляра, тогда скелетом этой фигуры можно считать скелет аппрок-симируюущего её циркуляра. При этом численной оценкой качества скелета является величина погрешности аппроксимации.
Таким образом, алгоритм построения криволинейного скелета
сводится к аппроксимации фигуры пространственным циркуляром. Такая аппроксимация выполняется в два шага. Сначала ищется первое приближение циркуляра, который сохраняет топологические свойства исходного объекта. Затем происходит итеративная подгонка приближенного циркуляра согласно используемому критерию качества.
Научная задача Основная задача настоящей работы заключается в разработке общей математической модели криволинейных скелетов. Важно, чтобы при этом было дано строгое и обоснованное определение, предоставляющее возможность численно оценить качество скелета. Критерий качества должен иметь ясный физический смысл и соответствовать интуитивным представлениям о том, что такое трёхмерный криволинейный скелет; кроме того, практическая ценность этого критерия должна быть явным образом продемонстрирована па реальных примерах.
Для того, чтобы оценить полезность предлагаемого подхода, в работе рассматриваются как конкретные алгоритмы построения локально оптимальных в рамках модели скелетов, так и их практические приложения.
Методы исследования Работа носит тсоретико-эксперимеиталь-пый характер. Теоретическая часть содержит в себе элементы дифференциальной геометрии, вычислительных методов, теории графов, теории сложности алгоритмов и вычислений. Для проведения экспе-
риментов создан специализированный программный комплекс, входными данными для которого послужили как синтетические трёхмерные модели, так и модели реальных объектов, полученные методами трёхмерного сканирования.
Научная значимость Многочисленные публикации о трёхмерных криволинейных скелетах не опираются на общую теоретическую базу; отсутствует даже общепринятое определение криволинейного скелета. Это делает невозможным содержательное обсуждение и сравнение различных конкретных способов построения скелетов. Настоящая работа призвана заполнить этот пробел. Предлагаемое общее предслепие криволинейных скелетов включает в себя различные эвристические определения, позволяя при этом численно оценивать степень соответствия между тем или иным скелетом и исходной моделью.
Наличие численной меры качества скелетов позволяет формулировать задачу трёхмерной скелетизации как задачу оптимизации некоторой функции; в работе описан основанный па этом подходе алгоритм, основанный на использовании численных методов для уточнения получаемых скелетов.
Практическая значимость Трёхмерные криволинейные скелеты находят широкое применение в многочисленных задачах анализа формы трёхмерных изображений. К ним относятся задачи анализа
формы и поиска оптимального маршрута, медицинские приложения, биометрия. В работе предлагаются эффективные алгоритмы построения скелетов, которые могут быть использованы в практических приложениях.
На защиту выносятся следующие научные результаты: Принципиально новым в своей предметной области результатом является формулировка строгого математического определения криволинейного скелета. Это определение включает в себя широкий класс скелетов, описанных в литературе, что позволяет оценивать и сравнивать их между собой не только при помощи визуальной оценки, но и путём численных экспериментов.
Алгоритмы, работающие на основе предлагаемой модели, эффективны и теоретически обоснованы — последнее обстоятельство также содержит в себе элемент новизны, т.к. общепринятый порядок заключается в определении скелета как результата работы некоторого эвристического алгоритма.
Апробация работы Результаты работы докладывались и обсуждались на следующих научных конференциях и семинарах:
• научно-техническая конференция «Техническое зрение в системах управления» TVCS 2011 (Москва, Россия, 2011 год) [10];
• международная конференция «Advanced Concepts for Intelligent
Vision Systems» ACIVS 2011 (Гспт, Бельгия, 2011 год) [36];
• всероссийская конференция «Математические методы распознавания образов» ММРО-15 (Петрозаводск, Россия, 2011 год)
[31;
• международная конференция «21th International Conference on Computer Graphics and Vision» GraphiCon 2011 (Москва, Россия, 2011 год) [391;
• международная конференция «24th Canadian Conference on Computational Geometry» CCCG 2012 (Шарлоттауп, Канада, 2012 год) [40];
• ярославская международная конференция «Дискретная геометрия», посвященная 100-летию А.Д. Александрова (Ярославль, Россия, 2012 год) [38].
Личный вклад. Все результаты, выносимые на защиту, получены автором самостоятельно. Постановка задачи была выполнена сов- 1 местио с научным руководителем.
Публикации по теме диссертации в изданиях списка ВАК: [11, 36]. Другие публикации по теме диссертации: [3, 10, 37-40].
Структура и объём диссертационной работы. Работа состоит из оглавления, введения, четырёх глав, заключения и списка литера-
туры. Содержание работы изложено па 133 страницах.
В первой главе рассматриваются основные понятия, связанные с темой работы: трёхмерные формы и способы их описания, серединная ось и её свойства, криволинейные скелеты и способы их построения, предложенные в существующей литературе по этой теме; формулируется постановка задачи построения трёхмерного криволинейного скелета.
Во второй главе описывается предлагаемая в работе математическая модель трёхмерных скелетов: вводятся понятия жирной кривой и пространственного циркуляра, формулируется постановка задачи аппроксимации трёхмерной формы при помощи некоторого пространственного циркуляра, описывается численная мера близости между формой и аппроксимирующим циркуляром; доказывается, что для двумерных изображений оптимальным криволинейным скелетом в рамках предложенной модели является серединная ось.
В третьей главе описывается алгоритм построения криволинейного скелета, основанный на решении задачи оптимизации. Описание алгоритма включает в себя два различных метода построения первого приближения скелета (на основе графов Риба и скелетов плоских проекций), численную оптимизацию при помощи метода наискорейшего спуска, обоснование корректности алгоритма и анализ его вычислительной сложности.
В четвёртой главе описывается практическая реализация алго-
ритма построения криволинейных скелетов и анализируются результаты вычислительных экспериментов.
В заключении подводится итог выполненной работе.
Глава 1
Трёхмерные криволинейные скелеты: постановка задачи
1.1. Трёхмерные формы и связанные с ними прикладные задачи
В настоящее время возникает большое количество практических задач, связанных с анализом формы трёхмерных объектов, например, в медицине [14, 20, 59], архитектуре [45, 50], биометрии [29, 58]. Это связано с широким распространением устройств, позволяющих получать цифровые трёхмерные модели объектов реального мира [27, 54].
Существует несколько основных способов для описания геометрической формы пространственных объектов. К ним относятся облака точек, полигональные модели и вокссльпыс изображения
Определение 1. Облаком точек (point cloud) называется конечное мноэюеегпво точек в К3.
Определение 2. Полигональной моделью (полигональной сеткой, polygonal rriesh) называется конечная триангулированная поверхность, влоэ!сеипая в К3.
Полигональные модели в зависимости от качества исходных данных могут обладать различными свойствами. В частности, модель может быть неупорядоченным множеством полигонов, открытым двумерным многообразием, или, в лучшем случае, замкнутым двумерным многообразим (т.е. границей некоторой трёхмерной области).
Определение 3. Воксельиым изобраэ/сением (voxel image) называется ограниченное подмноэ/сество точек целочисленной трёхмерной решётки.
Воксельное изображение является трёхмерным аналогом двумерного растрового изображения.
1.2. Серединная ось
Понятие серединной оси (medial axis) впервые было введено в [19]. В настоящее время серединные оси широко используются при решении задач вычислительной геометрии и анализа формы.
Пусть Г2 — открытое ограниченное подмножество Мп. Через дО, обозначим границу этого множества, а через £1 его замыкание:
П = (1.1)
Определение 4. Серединной осью открытого ограниченного множества О С М" называется мнооюсство точек этого множества,
для которых существует не менее двух ближайших точек на границе этого множества:
М = {а € Г2|3х,у е дО. : х ф у, ||а — х|| = ||а - у||,
(1.2)
Уг £ ШЦа-гЦ > ||а-х||}.
Определение 5. Серединной осью замкнутого ограниченного множества С Мп называсупся замыкание серединной оси открытого множества П.
Серединная ось является стратифицированным многообразием, размерность которого в общем случае не превосходит размерности границы множества [23]. Таким образом, середиипа�
