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

005536135

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

Черников Игорь Сергеевич

МЕТОДЫ И АЛГОРИТМЫ РЕКОНСТРУКЦИИ, ПОИСКА И ВИЗУАЛИЗАЦИИ ТРЁХМЕРНЫХ МОДЕЛЕЙ

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

Автореферат диссертации на соискание ученой степени кандидата физико-математических наук

31 ОКГ 2013

Воронеж - 2013

005536135

Работа выполнена в Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет»

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

доцент Кургалин Сергей Дмитриевич

Официальные оппоненты Батаронов Игорь Леонидович, доктор

физико-математических наук, профессор, Воронежский государственный

технический университет, заведующий кафедрой математики и физико-математического моделирования

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

технический университет, заведующий кафедрой информационных систем и технологий

Ведущая организация - Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Тверской государственный технический университет»

Защита состоится 20 ноября 2013 года в 15.10 на заседании совета Д212.038.20 при Федеральном государственном бюджетном образовательном учреждении высшего профессионального образования «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская площадь, д.1, ауд. 335.

С диссертацией можно ознакомиться в библиотеке Федерального государственного бюджетного образовательного учреждения высшего профессионального образования «Воронежский государственный университет»

Автореферат разослан « АЯ-» октября 2013 г.

Ученый секретарь диссертационного совета, кандидат физико-математических наук, доцент

С.А. Шабров

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

Актуальность темы. В настоящее время проблемы реконструкции и поиска схожих по форме поверхности трёхмерных моделей в базах данных являются одними из актуальных направлений теоретических и прикладных исследований. Научные исследования в области трёхмерного компьютерного зрения активно ведутся лабораториями Stanford Computer Graphics Laboratory (Стэнфорд, США), Center for Geometiy, Imaging and Virtual Environments (Утрехт, Нидерланды), Laboratoire d'Informatique Fondamentale de Lille (Вильнёв-д'Аск, Франция), Microsoft Research Cambridge (Кембридж, Великобритания), Princeton Shape Retrieval and Analysis Group (Принстон, США). Информационные системы трёхмерного компьютерного зрения решают задачи построения геоинформационных систем, автоматизации биомедицинских комплексов, удалённого присутствия, представления трёхмерной информации, контроля производства и т. п. Алгоритмы компьютерного зрения применяются для навигации мобильных роботов, беспилотных летательных аппаратов, автомобилей, распознавания объектов, построения и анализа точных трёхмерных моделей и др.

В целях упрощения аппаратной части программно-аппаратных комплексов для автоматической реконструкции трёхмерных моделей решение ряда математических и алгоритмических задач трёхмерного компьютерного зрения в настоящее время возлагается на обрабатывающую программу. Постоянный рост доступности и числа трёхмерных моделей делают всё более востребованными быстрые и эффективные методы и алгоритмы поиска трёхмерных моделей в базах данных. Использование как методов реконструкции, так и методов поиска трёхмерных моделей непосредственно связано с проблемой анализа формы поверхности трёхмерных моделей. Сложность решения данной проблемы связана с тем, что в системах компьютерного зрения поверхности трёхмерных моделей, как правило, представляют собой множества точек и соединяющих эти точки рёбер. Один из наиболее успешных подходов к описанию формы трёхмерных моделей заключается в построении дескрипторов («инвариантов») формы поверхности, их анализе и обработке. D.V. Vranic и D. Saupe (Лейпциг, Германия) предлагают использовать для поиска трёхмерных моделей дескрипторы, основанные на трёхмерном дискретном преобразовании Фурье. Метод преобразования дескрипторов поверхности при помощи сферических гармоник для получения инвариантных представлений дескрипторов представлен в работах M. Kazhdan, T. Funkhouser и S. Rusinkiewicz (Принстон, США). Сегодня значительная часть исследований в данной области сосредоточена на разработке новых дескрипторов поверхности, которые, однако, часто оказываются слишком сложными для реализации и малоэффективными в вычислительном плане. При этом не уделяется достаточного внимания таким проблемам, как: верификация соответствующих точек поверхностей в рамках метода первичного совмещения поверхностей трёхмерных моделей, нормализация трёхмерных моделей и устойчивость дескрипторов к зашумлённости данных.

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

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

Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения и передачи информации в информационно-коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» и НИР «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий нового поколения» № ГР 01201263910 (2012-2014 гг.).

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

Для достижения цели в работе решались следующие задачи:

1. Создание новых локальных дескрипторов поверхности.

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

3. Создание и исследование модели поиска трёхмерных моделей в базах данных и метода нормализации трёхмерных моделей.

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

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

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

Новизна работы:

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

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

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

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

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

Область исследования - содержание диссертации соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» (физико-математические науки), область исследований соответствует п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п. 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечения; разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»; п. 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».

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

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

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

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

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

4. Алгоритмы, построенные на основе созданной модели и предложенных методов, и результаты их программной реализации.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на IX и X международных научно-технических конференциях «Компьютерное моделирование 2008» и «Компьютерное моделирование 2009», г. Санкт-Петербург, 2008-2009 гг.; XVI и XVII Всероссийских научно-методических конференциях «Телематика'2009» и «Телематика'2010», г. Санкт-Петербург, 2009-2010 гг.; IX и X международных научно-методических конференциях «Информатика: проблемы, методология, технологии», г.Воронеж, 2009-2010 гг.; XI международной научно-технической конференции «Кибернетика и высокие технологии XXI века», г. Воронеж, 2010 г.; 22-ой международной конференции по компьютерной графике и зрению «ГрафиКон'2012», г. Москва, 2012 г.; Всероссийской научной конференции «Современные проблемы математического моделирования, супервычислений и информационных технологий», г. Таганрог, 2012 г.

Публикации. Основные результаты диссертации опубликованы в 17 печатных изданиях [1-17], в том числе в трёх [1-3] - из списка изданий, рекомендованных ВАК РФ. Получено одно свидетельство о государственной регистрации программ для ЭВМ [18].

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 105 наименований и 7 приложений. Объем диссертации составляет 145 страниц, включая 112 страниц основного текста, содержащего 57 рисунков.

СОДЕРЖАНИЕ РАБОТЫ

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

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

б

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

Процесс реконструкции моделей включает в себя получение трёхмерных данных посредством использован™ различных сенсоров и дальнейшую программную обработку полученных данных. Наиболее распространённым сегодня является подход к решению задачи реконструкции, заключающийся в максимальном упрощении аппаратной части систем компьютерного зрения путём совершенствования программной реализации алгоритмов автоматического совмещения поверхностей. При этом первичное совмещение основывается на определении соответствующих точек на двух смежных отсканированных поверхностях посредством построения и сравнения локальных дескрипторов формы поверхности. Классическим и достаточно эффективным решением задачи точного совмещения является итеративный алгоритм ближайших точек (ICP -Iterative Closest Points), предложенный P. J. Besl и N. D. McKay (1992 г.).

Проблема нормализации трёхмерных моделей возникает при решении задач выравнивания и определения положения моделей в трёхмерном пространстве. Нормализация также необходима при поиске трёхмерных моделей в базах данных. Наиболее сложным этапом нормализации моделей представляется нахождение преобразования оптимального вращения. В большинстве работ такое преобразование определяется на основе векторов главных осей модели, полученных при помощи известного метода главных компонент (Principal Component Analysis - РСА), а также его модификаций. В работах М. Kazhdan (2004-2009 гт.) для оптимального выравнивания трёхмерных моделей используется свойство симметрии моделей.

В работе J. W. Н. Tangelder и R. С. Veitkamp (2004 г.) изложены основные принципы построения моделей поиска трёхмерных моделей, приводится классификация моделей поиска. Один из наиболее популярных подходов к решению задачи поиска состоит в вычислении глобальных дескрипторов поверхности моделей и последующем их сравнении. Работа L. Zhang, М. Fonseca, A. Ferreira (2007 г.) содержит исчерпывающий обзор дескрипторов формы поверхности.

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

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

Идея спиновых изображений основана на сопоставлении опорной точке (точке поверхности, в которой вычисляется локальный дескриптор) цилиндрической

системы координат без учёта полярного угла. Начало цилиндрической системы

координат помещается в опорную точку, а ось z направляется параллельно

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

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

Отображение /0:Л3—>Л2 каждой произвольной точке A{Ax,Ay,Az) поверхности 5 с Л3 ставит в соответствие координаты её спинового изображения а и р относительно опорной точки 0(0x,0y,0z)e R3 с ассоциированной нормалью к

поверхности в этой точке п0& \ 10(А) = (а, /3),

а = (J\\A -Of- (п0 ■ (А - О))2 ,р = п о-(А-О)). (1)

Определим функцию f0(a,/3), задающую распределение точек поверхности S относительно опорной точки О:

fo («,/?) = count {A е S:I0(A) = (a,/3)), (2)

где coimt{...) - функция, определяющая количество точек, удовлетворяющих указанному выше условию. Очевидно, что точки с одинаковыми значениями а и /? лежат на окружности радиуса а и на расстоянии fS от точки О вдоль её нормали. На практике точек с абсолютно совпадающими значениями а и Д, как правило, не существует. Поэтому значения а и /? разбивают на классы (или корзины) и подсчитывают количество точек поверхности, попавших в каждую корзину. В трёхмерном пространстве такие корзины представляют собой цилиндрические кольца.

Утверждение 1. Каждому спиновому изображению можно поставить во взаимно однозначное соответствие двумерный массив корзин Ма. При этом значение элемента массива определяется количеством точек, попавших в соответствующую корзину:

MQ[iJl= I /о («,/?), (3)

<а<ан1

Pj<P<Pj+1

i=\,...,wa,j=\,~.,wp, dj = ьа■ (/-1), ftj=bfi-u-i),

% v.

vi у

д J i

__-__-— '< '•-■

' Yj -. ■ *v\ 1 л, ' 1 ■ \m

/1 )\ ! : ^ N

Рис. 1. Трёхмерное спиновое изображение, a, /J и у -относительные координаты

где Wa - ширина (размер) спинового изображения по координате а; Wß - ширина спинового изображения по координате ß\ ba и bß - размеры корзин по координатам

а и ß. Таким образом, для вычисления спинового изображения используются точки поверхности S, ограниченные цилиндром с центром в точке О, высотой ßmaK = Wßbß и радиусом «max = WаЪа.

Особенностью предлагаемых нами трёхмерных и ориентированных спиновых изображений является использование при их построении информации о локальной ориентации поверхности, которая задаётся углом у между нормалью опорной точки и нормалями точек из её окрестности (рис. 1). При этом для новых локальных дескрипторов поверхности свойство инвариантности сохраняется. В случае трёхмерных спиновых изображений отображение (1) для произвольной точки A(Ax,Ay,Az)<= Ä3 с нормалью пА е R3 принимает следующий вид:

7о : R6 Ä3,Т0(А) = (a,ß,i), у = arccos(п0 -пл).Функция (2) преобразуется к виду: 7о(от,Ду) = count(Aе S:T0(A) = (а,ß,у)). (4)

Утверждение 2. Каждому трёхмерному спиновому изображению можно поставить во взаимно однозначное соответствие трёхмерный массив корзин М0:

M0[i,j,k]= 1/о(а,Дг).где Bijk={ai<a<ai + x\ßj<ß<ßj + l-,yk<y<rk + l}.

Bijk

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

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

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

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

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

множеств ориентированных точек (точек с нормалями) Аг = {х,-еЛ3,их. еЛ3},/ = 1,...,и и Р = {р^ Я3,пр. е Л3},г = 1,...,т. При этом будем

рассматривать случай присоединения точек множества Р к точкам множества А', то есть среди точек из Р будем искать точки, соответствующие точкам из X.

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

Путём проведения вычислительных экспериментов было установлено, что выбор 5-10% всех точек поверхности X обеспечивает успешное выполнение совмещения. Для выбора точек Х'= {*/} 1 ,...,£ , участвующих в совмещении,

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

к П] 2 II

квадратичной ошибки Е= ¿¿И^ _СЛ ' где р * ~ евклидово расстояние

между точкой е Л3 и центром кластера Су е Л3. Количество кластеров

определяется в соответствии с числом выбираемых точек. В каждом кластере выбирается точка х,'=х . н _ и, ближайшая к его центру с,-. Такой способ

У ГП1П С j

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

Для поиска точек Р'={ру'}с=Р,у' = 1,...,А:, соответствующих выбранным точкам

А"={ху,}сАг,у' = 1,...,Л, локальные дескрипторы точек р,- е Р последовательно

сравниваются с дескрипторами каждой точки х^е X': р/=рм%тах(н(мх.,,мпу)-

1=1.....т ^

Сравнение дескрипторов осуществляется путём вычисления коэффициента линейной корреляции Я:

N N N

щмх,м2)= , <=1 7=1 (5)

N I N - N N

(лг2>„2 )(^Х«2/2 -(Е«2,Г)

¡=\ ¡=1 1=1 /=1

где Ы— количество элементов дескриптора.

-Реляционные

векторы

--- Строгое

преобразование

/

100 1000 2000 3000 4000 5000 6000 7000 8000 Когосчество верифэддаруешхх соответствий

Рис. 2. Время работы алгоритма совмещения поверхностей для разных способов верификации соответствий

В главе рассмотрены два подхода к верификации соответствующих точек: подход, основанный на проверке геометрической

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

векторы полностью описывают взаимное положение двух ориентированных точек в пространстве и позволяют выявить геометрическую конгруэнтность пары соответствий путём поэлементного сравнения этих векторов, вычисленных для двух точек одной поверхности и соответствующих им точек другой поверхности. Согласованность более чем двух соответствий проверяется посредством группировки согласованных соответствий. Идея второго подхода основана на том, что при попытке строгого преобразования (оно представлено ниже) соответствующих точек двух поверхностей истинные соответствующие точки окажутся ближе друг к другу, чем ложные. Это объясняется значительно меньшим количеством ложных соответствий по отношению к истинным, что достигается за счёт использования предлагаемых локальных дескрипторов в рамках метода первичного совмещения поверхностей. Истинными полагаются соответствующие точки (х,*,р*), расстояние между которыми после преобразования оказалось меньшим заданного порога: (дг,*,р,*) : d(x/' ,р/) < d"lrM1. Xj" - точки, полученные в результате строгого преобразования координат точек xj' к координатам точек pj';

jthreshold _

а - порог, вычисленный с использованием межквартильного расстояния

распределения значений расстояний d между всеми точками. К координатам точек (Х*>Р*) снова применяется строгое преобразование. Итерации продолжаются до тех пор, пока среди точек (х, *,р*) присутствуют ложные соответствующие точки. На рис. 2 представлены графики зависимости времени работы алгоритма совмещения поверхностей от количества верифицируемых соответствий.

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

Будем искать такие матрицу вращения R и вектор трансляции t, для которых выполняется приближённое равенство х* = Rp*+t.

Теорема. Пусть существует s пар согласованных точек х/* и pt * (/ = >3). Тогда существуют единственные матрица вращения R и вектор

трансляции минимизирующие ошибку Е = *~RPi * -t\\2.

il

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

т

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

значением этой матрицы. Этот вектор и выбирается в качестве

2 5

0,05 0,045 0,04 0,035 0,03 0.025 0.02 0.015 0.01 0,005 0

-трёхмерные спиновые изображения

• • • ■ спиновые изображения ---ориентированные спиновые изображения

•У

птттттпттттт

3 ё

гттттттпттттттттттпттп

б) т- « «

о

ниппмпшпннищницитмнии

N OJ « lO Ю О

г г N W N N М О О О ООО сГ

Рис. 3.

о (шум), ед. изм. координат точек поверхностей

Зависимость ошибки совмещения

трёхмерных поверхностей от их зашумлённости

С

' Ввод всех иоделсй из базы у

f Подготовка базы, ^ I для всех моделей Л/,

Нормализация модели

I —

/ Ввод запроса R /

■ I ,

I Нормализация R

I

кватерниона оптимального поворота. Матрица вращения R, соответствующая этому кватерниону, получается из известного соотношения между ними (Horn, 1987).

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

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

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

результаты функционирования модели с использованием простых характеристик поверхности модели (главные оси, гистограмма распределения расстояний и площадь поверхности), интегральных

Вычисление глобальною дескриптора поверхности

(гтм?

Получение изотропного ГДПМ~"

^^ Подготовка базы ^^J

вычисление глобального дескриптора поверхности (ГДП) RIS'

Л

Попуч ение изотропного ГДП Л*™

I

/ Поиск моделей, для всех моделей М,

вычисление коэффициента корреляции С,

между R

¡И-

Сортировка Л/, по убыванию С,

/ Вывод И, / ( Конец )

Рис. 4. Блок-схема алгоритма предложенной модели поиска

работы

нормализованные анизотропные изотропные

спиновых изображений (ИСИ), а также их модификаций: трёхмерных и ориентированных интегральных спиновых изображений.

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

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

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

На основании следствия из теоремы об оптимальном масштабировании двух векторов (М. КагЬ(1ап, 2004) оптимальный коэффициент масштабирования трёхмерной модели находится из условия равенства единице среднеквадратического

отклонения точек данной модели {рь...,рп} с Я3 : у, = ^п/ £ (р? + р?г + р?.)-

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

100 90

— ■ — главные оси ----гистограмма

распределения расстояний

-площадь поверхности

---------интегральные спиновые

изображения

— трёхмерные ИСИ

.....ориентированные ИСИ

............ИСИ + простые

характеристики

трёхмерной модели: р =

/и.

2> V/=i

Для определения опорного вектора мы используем известный метод уменьшения размерности системы -метод главных компонент (Principal Component Analysis - РСА). В главе

10 20 30 40 60 60 7С полнота. %

Результаты работы модели поиска с разных глобальных дескрипторов

Рис. 6.

использованием поверхности

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

2 Д - шах Д - min Д по обеим координатам (« и ß): а.<-_h--а " ' 1=1....." <=i- ." о

max

1=1,...,

а,

max

/=!,..., л

ßi

где а, и Д - текущие координаты интегрального спинового изображения; атт и /?max - максимальные значения координат (они определяются числом и размером корзин интегрального спинового изображения); п - количество точек трёхмерной модели.

Создана компьютерная программа на языке программирования С/С-Ь+, реализующая предложенную модель поиска. В ней предусмотрен блок визуализации трёхмерных моделей, использующий возможности графической библиотеки Direct3D. Поддерживаются форматы файлов трёхмерных данных PLY и OFF. Для оценки эффективности предложенной модели поиска использовались стандартные меры: точность Precision и полнота Recall, которые вычисляются для каждого запроса к базе данных: Precision = \К п А\/\А\ , Recall = \К п А\/\К\, где К - множество всех релевантных моделей из базы данных; А - множество найденных моделей.

Как следует из рис. 6, на котором представлены результаты работы модели поиска в координатах точность-полнота (precision-recall) для разных глобальных дескрипторов, наилучшие результаты достигаются при использовании интегральных спиновых изображений в комплексе с простыми характеристиками поверхности трёхмерной модели (главные оси, гистограмма распределения расстояний и площадь поверхности).

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

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

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

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

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

Основные публикации по теме диссертации

1. Крыловецкий А. А. Нормализация 3D-модели для вычисления интегрального спинового изображения / А. А. Крыловецкий, И. С. Черников // Известия Южного федерального университета. Технические науки. - 2012. - JV® 6. - С. 135-139.

2. Крыловецкий А. А. Автоматическое совмещение поверхностей в системах компьютерного зрения / А. А. Крыловецкий, И. С. Черников, С. Д. Кургалин // Математическое моделирование. - 2013. - Т. 25, № 3. - С.33-46.

3. Черников И. С. Интегральные спиновые изображения в задаче поиска трёхмерных моделей / И. С. Черников // Системы управления и информационные технологии. - 2013. - № 2.1(52). - С. 181-186.

4. Черников И. С. Пространственное совмещение дальнометрических данных / И. С. Черников // Компьютерное моделирование 2008 : труды международной научно-технической конференции. - Санкт-Петербург, 2008. - С. 166-170.

5. Крыловецкий А. А. Построение виртуальных моделей по дальнометрическим данным / А. А. Крыловецкий, Г. А. Карапиш, И. С. Черников // Телематика'2008 : труды XV Всероссийской научно-методической конференции. - Санкт-Петербург, 2008.-Т. 1.-С. 208.

6. Крыловецкий А. А. Реконструкция и распознавание объектов в системах компьютерного зрения / А. А. Крыловецкий, И. С. Черников // Телематика'2009 : труды XVI Всероссийской научно-методической конференции. - Санкт-Петербург, 2009. - Т. 2. - С. 314-315.

7. Черников И. С. Совмещение дальнометрических изображений / И. С. Черников, А. А. Крыловецкий // Информатика : проблемы, методология, технологии : материалы 9-ой международной научно-методической конференции. - Воронеж, 2009. - Т. 2. - С. 439-442.

8. Черников И. С. Трехмерная реконструкция и распознавание по наборам дальнометрических данных / И. С. Черников, А. А. Крыловецкий // Компьютерное моделирование 2009 : труды международной научно-технической конференции. -Санкт-Петербург, 2009. - С. 284-287.

9. Крыловецкий А. А. Автоматическое совмещение поверхностей: улучшенные спиновые изображения / A.A. Крыловецкий, И.С. Черников // Кибернетика и высокие технологии XXI века: труды XI Международ, научно-технич. конф. - Воронеж, 2010. -Т.2.-С. 781-790.

10. Крыловецкий А. А. Модифицированные спиновые изображения в системах трехмерной реконструкции / А. А. Крыловецкий, И. С. Черников // Телематика'2010 : труды XVII Всероссийской научно-методической конференции. - Санкт-Петербург, 2010.-Т. 2.-С. 309-310.

11. Черников И. С. Модифицированные спиновые изображения в системах трехмерной реконструкции / И. С. Черников, А. А. Крыловецкий // Сборник студенческих научных работ факультета компьютерных наук ВГУ. - Воронеж, 2010. -Вып. 4.-С. 157-160.

12. Черников И. С. Автоматическая реконструкция и распознавание реальных объектов / И. С. Черников, А. А. Крыловецкий // Информатика : проблемы, методология, технологии : материалы X международ, научно-методической конф. -Воронеж, 2010—Т. 2. - С. 327-331.

13. Крыловецкий А. А. Метод интегрального представления формы поверхности в системах поиска трехмерных моделей / А. А. Крыловецкий, И. С. Черников // Информатика : проблемы, методология, технологии : материалы XII Международной научно-методической конференции. - Воронеж, 2012. - Т. 1. - С. 208-209.

14. Черников И. С. Модифицированные спиновые изображения в системах трехмерной реконструкции / И. С. Черников, А. А. Крыловецкий // Сборник студенческих научных работ факультета компьютерных наук ВГУ. - Воронеж, 2011. -Вып. 4.-С. 157-160.

15. Крыловецкий А. А. Интегральные спиновые изображения в системах поиска ЗЭ моделей / А. А. Крыловецкий, И. С. Черников // Телематика'2012 : труды XIX Всероссийской научно-методической конференции. — Санкт-Петербург, 2012. — Т. 2. - С. 311-313.

16. Крыловецкий А. А. Интегральные спиновые изображения в системах поиска трёхмерных моделей / А. А. Крыловецкий, И. С. Черников // ГрафиКон'2012 : труды 22-й Международной конференции по компьютерной графике и зрению. - Москва, 2012. - С. 214-217.

17. Черников И. С. Глобальные дескрипторы поверхности интегральные спиновые изображения / И. С. Черников // Информатика : проблемы, методология, технологии : материалы XIII Международ, научно-методической конф.-Воронеж, 2013.-Т.З .-С .402406.

18. Свидетельство о государственной регистрации программы для ЭВМ ЗОЗеагсЬ / И.С. Черников. - № 2013616205, зарегистрировано в Реестре программ для ЭВМ 2 июля 2013.

Подписано в печать 16.10.13. Формат 60x84 '/,6. Усл. печ. л. 0,93. Тираж 100 экз. Заказ 1017.

Отпечатано с готового оригинал-макета в типографии Издательско-полиграфического центра Воронежского государственного университета. 394000, Воронеж, ул. Пушкинская, 3

Воронежский государственный университет

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

04201364590

Черников Игорь Сергеевич

МЕТОДЫ И АЛГОРИТМЫ РЕКОНСТРУКЦИИ, ПОИСКА И ВИЗУАЛИЗАЦИИ ТРЁХМЕРНЫХ МОДЕЛЕЙ

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

Диссертация на соискание ученой степени кандидата физико-математических наук

Научный руководитель доктор физ-мат. наук, доцент Кургалин Сергей Дмитриевич

Воронеж - 2013 г.

Оглавление

ВВЕДЕНИЕ..............................................................................................................4

ГЛАВА 1. СОВРЕМЕННЫЕ ПОДХОДЫ К РЕШЕНИЮ ЗАДАЧ РЕКОНСТРУКЦИИ И ПОИСКА ЗБ-МОДЕЛЕЙ.............................................14

1.1. Трёхмерное компьютерное зрение..............................................................14

1.2. Дескрипторы формы поверхности................................................................19

1.2.1. Классификация дескрипторов формы поверхности.............................20

1.3. Методы нормализации трёхмерных моделей..............................................22

1.4. Методы реконструкции трёхмерных моделей............................................23

1.5. Методы поиска трёхмерных моделей..........................................................29

1.6. Выводы............................................................................................................32

ГЛАВА 2. ТРЁХМЕРНЫЕ И ОРИЕНТИРОВАННЫЕ СПИНОВЫЕ ИЗОБРАЖЕНИЯ...................................................................................................34

2.1. Трёхмерные данные. Ориентированные точки.........................................34

2.2. Спиновые изображения................................................................................38

2.3. Трёхмерные спиновые изображения..........................................................41

2.4. Ориентированные спиновые изображения................................................44

2.5. Параметры генерации спиновых изображений.........................................44

2.5.1. Размер корзины.........................................................................................44

2.5.2. Ширина спинового изображения............................................................45

2.6. Выводы...........................................................................................................47

ГЛАВА 3. МЕТОДЫ РЕКОНСТРУКЦИИ ТРЁХМЕРНЫХ МОДЕЛЕЙ........49

3.1. Метод первичного совмещения....................................................................51

3.1.1. Способ выбора точек поверхности для совмещения............................51

3.1.2. Алгоритм определения соответствующих точек..................................56

3.1.3. Методы верификации соответствий.......................................................58

3.1.4. Проведение вычислительных экспериментов.......................................63

3.1.5. Вычисление строгого преобразования...................................................64

3.2. Метод точного совмещения..........................................................................68

3.3. Вычислительные эксперименты по выявлению свойств новых локальных дескрипторов..........................................................................................................71

3.4. Результаты автоматического первичного совмещения..............................73

3.5. Выводы............................................................................................................77

ГЛАВА 4. МОДЕЛЬ ПОИСКА ЗБ-МОДЕЛЕЙ В БАЗЕ ДАННЫХ................80

4.1. Интегральные спиновые изображения в качестве глобальных дескрипторов поверхности...................................................................................81

4.2. Метод нормализации ЗБ-моделей................................................................85

4.3. Анизотропия трёхмерных моделей. Метод получения изотропных интегральных спиновых изображений................................................................93

4.4. Метод сравнения ЗБ-моделей.......................................................................95

4.5. Простые способы описания трёхмерных моделей......................................96

4.6. Алгоритм и компьютерная программа для модели поиска.....................100

4.7. Результаты вычислительных экспериментов............................................103

4.8. Выводы..........................................................................................................109

ЗАКЛЮЧЕНИЕ...................................................................................................112

СПИСОК ЛИТЕРАТУРЫ...................................................................................113

ПРИЛОЖЕНИЕ А...............................................................................................124

ПРИЛОЖЕНИЕ Б................................................................................................126

ПРИЛОЖЕНИЕ В................................................................................................128

ПРИЛОЖЕНИЕ Г................................................................................................131

ПРИЛОЖЕНИЕ Д...............................................................................................134

ПРИЛОЖЕНИЕ Е................................................................................................136

ПРИЛОЖЕНИЕ Ж...............................................................................................144

Г £

' t l

Введение

Актуальность темы. В настоящее время проблемы реконструкции и поиска схожих по форме трёхмерных моделей в базах данных являются одними из актуальных направлений теоретических и прикладных исследований. Научные исследования в области трёхмерного компьютерного зрения активно ведутся лабораториями всего мира. Работы по созданию программно-аппаратных комплексов для получения пространственных данных объектов реального мира и воссоздания (реконструкции) точных трёхмерных моделей успешно ведутся лабораторией Stanford Computer Graphics Laboratory (Стэнфорд, США), а также компанией DAVID Vision Systems GmbH (Кобленц, Германия). Модели поиска трёхмерных моделей в крупных базах данных разрабатываются в лабораториях Center for Geometry, Imaging and Virtual Environments (Утрехт, Нидерланды), Laboratoire d'Informatique Fondamentale de Lille (Вильнёв-д'Аск, Франция), Microsoft Research Cambridge (Кембридж, Великобритания), Princeton Shape Retrieval and Analysis Group (Принстон, США). Информационные системы трёхмерного компьютерного зрения решают задачи контроля производства, построения геоинформационных систем, автоматизации медицинских комплексов, удалённого присутствия, представления, трёхмерной информации и т. п. Алгоритмы компьютерного зрения используются для навигации мобильных роботов, беспилотных летательных аппаратов, автомобилей, распознавания объектов, построения и анализа точных трёхмерных моделей и др.

В настоящее время в целях упрощения аппаратной части программно-

<

аппаратных комплексов для автоматической реконструкции трёхмерных

моделей решение ряда математических и алгоритмических задач

трёхмерного компьютерного зрения возлагается на обрабатывающую

программу. Доступность и постоянный рост количества трёхмерных моделей

делают весьма востребованными быстрые и эффективные методы поиска

трёхмерных моделей в базах данных. Как методы реконструкции, так и

методы поиска трёхмерных моделей непосредственно связаны с проблемой

4

анализа формы поверхности трёхмерных моделей. Сложность данной проблемы вызвана тем, что в системах компьютерного зрения поверхность трёхмерных моделей, как правило, представляет собой множество точек и соединяющих эти точки рёбер. Один из наиболее успешных подходов к описанию формы трёхмерных моделей заключается в построении дескрипторов формы поверхности, их анализе и обработке. Сегодня значительная часть исследований в данной области сосредоточена на разработке новых, сложных, часто вычислительно неэффективных, дескрипторов поверхности. При этом не уделяется достаточного внимания таким проблемам, как верификация соответствий на этапе первичного совмещения метода реконструкции трёхмерных моделей, нормализация трёхмерных моделей и устойчивость дескрипторов к зашумлённым данным. Разработкой методов и алгоритмов реконструкции и поиска трёхмерных моделей занимаются учёные всего мира: Р. Min, М. Kazhdan, S. Rusinkiewicz (Принстон, США), R.C. Veitkamp (Утрехт, Нидерланды), Chi-Chou Као (Тайнань, Тайвань), группа под управлением Dr.-Ing. Simon Winkelbach (Брауншвейг, Германия).

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

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

Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения и передачи информации в информационно-коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы»; «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий нового поколения» № ГР 01201263910 (2012 - 2014 гг.).

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

Для достижения цели в работе решались следующие задачи:

1. Создание новых локальных дескрипторов поверхности.

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

3. Создание и исследование модели поиска трёхмерных моделей в базах данных и метода нормализации трёхмерных моделей.

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

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

модель поиска трёхмерных моделей, способы представления формы поверхности трёхмерных моделей, алгоритмы предложенных методов.

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

Новизна работы:

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

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

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

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

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

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

Область исследования - содержание диссертации соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» (физико-математические науки), область исследований соответствует п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п. 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечения; разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»; п. 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».

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

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

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

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

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

4. Алгоритмы, построенные на основе созданной модели и предложенных методов, и их программная реализация.

Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на IX и X международных научно-технических конференциях «Компьютерное моделирование 2008» и «Компьютерное моделирование 2009», г. Санкт-Петербург, 2008-2009 гг.; XVI и XVII Всероссийских научно-методических конференциях «Телематика'2009» и «Телематика'2010», г. Санкт-Петербург, 2009-2010 гг.; IX и X международных научно-методических конференциях «Информатика: проблемы, методология, технологии», г. Воронеж, 2009-2010 гг.; XI международной научно-технической конференции «Кибернетика и высокие технологии XXI века», г. Воронеж, 2010 г.; 22-ой международной конференции по компьютерной графике и зрению «ГрафиКон'2012», г. Москва, 2012 г.; Всероссийской научной конференции «Современные проблемы математического моделирования, супервычислений и информационных технологий», г. Таганрог, 2012 г.

Публикации. Основные результаты диссертации опубликованы в 17 печатных изданиях, в том числе в трёх - из списка изданий, рекомендованных ВАК РФ. Получено одно свидетельство о государственной регистрации программ для ЭВМ.

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

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

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, списка литературы из 105 наименований и 7 приложений. Объем диссертации составляет 145 страниц, включая 112 страниц основного текста, содержащего 57 рисунков.

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

Первая глава посвящена обзору и классификации существующих дескрипторов формы поверхности трёхмерных моделей, рассмотрению и анализу методов и алгоритмов реконструкции, нормализации и поиска трёхмерных моделе�