Методы и алгоритмы реконструкции, поиска и визуализации трёхмерных моделей тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат наук Черников, Игорь Сергеевич

• Черников, Игорь Сергеевич
• кандидат наук
• 2013

Оглавление диссертации кандидат наук Черников, Игорь Сергеевич

Оглавление

ВВЕДЕНИЕ

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

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

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

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

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

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

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

1.6. Выводы

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

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

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

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

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

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

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

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

2.6. Выводы

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

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

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

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

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

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

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

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

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

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

3.5. Выводы

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

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

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

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

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

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

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

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

4.8. Выводы

ЗАКЛЮЧЕНИЕ

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

ПРИЛОЖЕНИЕ А

ПРИЛОЖЕНИЕ Б

ПРИЛОЖЕНИЕ В

ПРИЛОЖЕНИЕ Г

ПРИЛОЖЕНИЕ Д

ПРИЛОЖЕНИЕ Е

ПРИЛОЖЕНИЕ Ж

Г £

' 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 рисунков.

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

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

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

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

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

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

применением простых характеристик поверхности модели (главные оси,

»

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

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

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

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

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

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

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

Глава 1. Современные подходы к решению задач реконструкции и поиска ЗБ-моделей 1.1. Трёхмерное компьютерное зрение

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

В последнее врямя появился новый термин «компьютерное зрение» -это теория и технология создания компьютерных систем, которые могут производить обнаружение и классификацию объектов и слежение за ними на основе анализа информации, получаемой от объектов в виде изображений [97]. Изображения могут быть представлены множеством форм, таких как видеопоследовательность, изображения с различных камер или же трехмерными данными, например, с устройства Ктес! [45], медицинского сканера и т. п.

Теория и модели компьютерного зрения применяются для создания соответствующих систем:

- системы управления процессами (промышленные роботы, автономные транспортные средства);

- системы видеонаблюдения;

- системы организации информации (например, для индексации баз данных изображений);

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

- системы взаимодействия (например, устройства ввода для системы человеко-машинного взаимодействия);

- системы дополненной реальности;

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

Системы компьютерного зрения, в целом, представляют собой программно-аппаратные комплексы.

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

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

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

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

Формально трёхмерные данные (модели трёхмерных объектов) могут быть представлены различными способами [105]: каркасные модели, модели типа поверхность-ребро-вершина, вексельные модели, модели на основе октантных деревьев, модели на основе обобщённых цилиндров, модели на основе суперквадрик, деформационные модели и др.

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

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

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

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

л

трёхмерном пространстве Р = {р1 \ р1е Я ,/ = 1,...,«} формулы для соответствующих преобразований будут иметь следующий вид:

= (1)

р:=Яр;, 1 = \,...,п, (2)

Л г = (3)

Рисунок 2. Трёхмерная модель автомобиля с применением разных типов трансформаций: а - трансляция; Ь - масштабирование; с - вращение

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

Список литературы диссертационного исследования кандидат наук Черников, Игорь Сергеевич, 2013 год

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

1. Akgul C. B. Density-Based Shape Descriptors for 3D Object Retrieval / Ceyhun Burak Akgul, Bulent Sankur, Francis Schmitt, Yucel Yemez // International Workshop, MRCS 2006, Istanbul, Turkey, Proceedings, 2006, pp. 322-329

2. Ankerst M. 3D Shape Histograms for Similarity Search and Classification in Spatial Databases / M. Ankerst, G. Kastenmueller, H.-P. Kriegel, T. Seidl // Proc. 6th Int. Symposium on Large Spatial Databases (SSD,99), 1999, pp. 207-226

3. Axenopoulos A. 3D Model Retrieval using Accurate Pose Estimation and View-based Similarity / Apostolos Axenopoulos, Georgios Litos, Petros Daras // ICMR '11 Proceedings of the 1st ACM International Conference on Multimedia Retrieval, Article No. 41, 2011, pp. 1-8

4. Benjemaa R. Fast Global Registration of 3D Sampled Surfaces Using a Multi-Z-Buffer Technique / R. Benjemaa, F. Schmitt // 3DIM. IEEE Computer Society, 1997, pp. 113-120

5. Besl P. J. A method for registration of 3-D shapes / P. J. Besl, N. D. McKay // IEEE Transactions on Pattern Analysis and machine Intelligence, 14(2), 1992, pp. 239-258

6. Brusco N. 3D Registration by Textured Spin-Images / Nicola Brusco, Marco Andreetto, Andrea Giorgi, Guido M. Cortelazzo // 3DIM '05 Proceedings of the Fifth International Conference on 3-D Digital Imaging and Modeling, 2005, pp. 262-269

7. Bustos B. Feature-based Similarity Search in 3D Object Databases / B. Bustos, D. Keim, D. Saupe, T. Schreck, D. Vranic // ACM Computing Surveys (CSUR), 37(4), Association for Computing Machinery, 2005, pp. 345-387

8. Callieri M. Roboscan: An automatic system for accurate and unattended 3d scanning / M. Callieri, A. Fasano, G. Impoco, P. Cignoni, R. Scopigno, R. Parrini, G. Biagini // In 3DPVT04: Second Int. Symp. on 3D Data Processing, Visualization and Transmission, IEEE Comp. Soc., 2004, pp. 805-812

9. Chen Y. Object modelling by registration of multiple range images / Y. Chen, G. Medioni // International Journal of Image and Vision Computing, 10(3), 1992, pp. 145-155

10. Chen D.-Y. On Visual Similarity Based 3D Model Retrieval / Ding-Yun Chen, Xiao-Pei Tian, Yu-Te Shen, Ming Ouhyoung // EUROGRAPHICS 2003, Volume 22 (2003), Number 3, 2003, pp. 223-232

11. Chua C.S. Point signatures: A new representation for 3d object recognition / C.S. Chua, R. Jarvis // Int. J. Comput. Vision, 25,1997, pp. 63-85

12. Clarkson K. A randomized algorithm for closest point queries // SIAM J. Computing, V.17,1998, pp. 830-847

13. COMET series // Steinbichler Optotechnik. URL: http://www.steinbichler.ш/пpoдyкция/surface-scanning/Зd-oцифpoвки/comet-5.html (Дата обращения: 24.07.2013)

14. Correa S. A new signature-based method for efficient 3-D object recognition / S. Correa, L. Shapiro // Proc. IEEE Conf. on Computer Vision and Pattern Recognition, vol. 1, 2001, pp. 769-776

15. Correa S. A New Paradigm for Recognizing 3-D Object Shapes from Range Data / Salvador Ruiz-Correa, Linda G. Shapiro, Marina Meila // ICCV '03, Proceedings of the Ninth IEEE International Conference on Computer Vision, Volume 2,2003, pp. 1126-1133

16. Curless B. A volumetric method for building complex models from range images / Brian Curless, Marc Levoy // SIGGRAPH '96 Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, 1996, pp. 303-312

17. DAVID-laserscanner // DAVID 3D Solutions GbR. URL: http://www.david-laserscanner.com (Дата обращения: 01.10.2012)

18. Delingette H. Shape representation and image segmentation using deformable surfaces / H. Delingette, M. Hebert, K. Ikeuchi // Image and vision computing, 10, 1992, pp. 132-144

19. Delingette H. A spherical representation for the recognition of curved objects / H. Delingette, M. Hebert, K. Ikeuchi // In Proc. IEEE Int. Conf. On Computer Vision, 1993, pp. 103-112

20. Devore J. Probability and Statistics for Engineering and the Sciences. 8th edition, 2011, pp. 267-299

21. Endres F. Unsupervised discovery of object classes from range data using latent Dirichlet allocation / F. Endres, C. Plagemann, C. Stachniss, Burgard W. // In Robotics: Science and Systems V, Seattle, USA, 2009, pp. 1-8

22. Fang R. A New Shape Benchmark for 3D Object Retrieval / Rui Fang, Afzal Godil, Xiaolan Li, and Asim Wagan // ISVC 2008 Part I, LNCS 5358, 2008, pp. 381-392

23. Friedman J. An algorithm for finding best matches in logarithmic expected time / J. Friedman, J. Bentley, R. Finkel // ACM Transactions on Mathematical Software, Volume 3, Issue 3, 1977, pp. 209-226

24. Frome A. Recognizing Objects in Range Data Using Regional Point Descriptors / A. Frome, D. Huber, R. Kolluri, T. Bulow, J. Malik // Proceedings of the European Conference on Computer Vision (ECCV), 2004, pp. 224-237

25. Funkhouser T. Rotation invariant spherical harmonic representation of 3d shape descriptors / T. Funkhouser, M. Kazhdan, S. Rusinkiewicz // In Eurographics Symposium on Geometry Processing, 2003, pp. 156-164

26. Funkhouser T. Shape-based Retrieval and Analysis of 3D Models / T. Funkhouser, M. Kazhdan, P. Min, P. Shilane // Communications of the ACM, 48(6), 2005, pp. 58-64

27. Gray K. Microsoft DirectX 9 Programmable Graphics Pipeline - Redmond: Microsoft Press, 2003, 458 p.

28. Hoppe H. Progressive Meshes // ACM SIGGRAPH 1996 Proceedings, 1996, pp. 99-108

29. Horn B. K. P. Extended Gaussian images // Proc. of the IEEE, 72, 1984, pp. 1671-1686

30. Horn B. K. P. Closed-form solution of absolute orientation using unit quaternions // Journal of the Optical Society America A, V. 4, №4, 1987, pp. 629-642

31. Huang Q.-X. Reassembling fractured objects by geometric matching / Qi-Xing Huang, Simon Flory, Natasha Gelfand, Michael Hofer, Helmut Pottmann // SIGGRAPH '06 ACM SIGGRAPH 2006 Papers, 2006, pp. 569-578

32. Iyer N. Three-dimensional shape searching: state-of-the-art review and future trends / Natraj Iyer, Subramaniam Jayanti, Kuiyang Lou, Yagnanarayanan Kalyanaraman, Karthik Ramani // Computer-Aided Design 37 (2005), 2005, pp. 509-530

33. Jaeggli T. Online 3d acquisition and model integration / T. Jaeggli, T. Koninckx, L. V. Gool // In Pro. Cam., 2003, pp. 1-8

34. Johnson A. E. Using spin images for efficient object recognition in cluttered 3D scenes / A. E. Johnson, M. Hebert // IEEE Trans. Pattern Analysis and Machine Intelligence, 21(5), 1999, pp. 433-449

35. Johnson A.E. Spin-Images: A Representation for 3-D Surface Matching, Ph. D. Thesis, Carnegie Mellon University, 1997,288 p.

36. Kagami S. High-Speed Vision Systems and Projectors for Real-Time Perception of the World // Conference on Computer Vision and Pattern Recognition Workshops (CVPRW), 2010 IEEE Computer Society, 2010, pp. 100107

37. Kaick O. A Survey on Shape Correspondence / Oliver van Kaick, Hao Zhang, Ghassan Hamarneh, Daniel Cohen-Or // Computer Graphics Forum, Volume 30, Issue 6, 2011, pp. 1681-1707

38. Kang S. B. The complex EGI: A new representation for 3D pose determination / S. B. Kang, K. Ikeuchi // IEEE Trans. Pattern Anal, and Mach. Intell., 15(7), 1993, pp. 707-721

39. Kao C.-C. View Based Rotation Invariant 3D Shape Retrieval // 2011 International Conference on Asia Agriculture and Animal. IPCBEE, V. 13, IACSIT Press, Singapoore, 2011, pp. 150-155

40. Kazhdan M. Rotation Invariant Spherical Harmonic Representation of 3D Shape Descriptors / M. Kazhdan, T. Funkhouser, S. Rusinkiewicz // Symposium on Geometry Processing (June 2003), 2003, pp. 167-175

41. Kazhdan M. Shape Representations And Algorithms For 3D Model Retrieval. Ph. D. Thesis, Princeton University, 2004, 120 p.

42. Kazhdan M. Reconstruction of solid models from oriented point sets // SGP '05 Proceedings of the third Eurographics symposium on Geometry processing, Article No. 73, 2005, pp. 1-11

43. Kazhdan M. Poisson surface reconstruction / Michael Kazhdan, Matthew Bolitho, Hugues Hoppe // SGP '06 Proceedings of the fourth Eurographics symposium on Geometry processing, 2006, pp. 61-70

44. Khoury R. 3D-model retrieval using bag-of-features based on closed curves / Rachid El Khoury, Jean-Philippe Vandeborre, Mohamed Daoudi // Eurographics Workshop on 3D Object Retrieval (2013), 2013, pp. 101-104

45. Kinect // Википедия : свобод. энцикл. URL: http://ru.wikipedia.org/wiki/Kinect (Дата обращения: 24.07.2013)

46. Kobbelt L. A survey of point-based techniques in computer graphics / Leif Kobbelt, Mario Botsch // Computers and Graphics, Volume 28, Issue 6, 2004, pp. 801-814

47. Lavoue G. Bag ofWords and Local Spectral Descriptor for 3D Partial Shape Retrieval // Eurographics Workshop on 3D Object Retrieval (2011), 2011, pp. 4148

48. Levoy M. The Digital Michelangelo Project: 3D scanning of large statues / M. Levoy, K. Pulli, B. Curless, S. Rusinkiewicz, D. Koller, L. Pereira, M. Ginzton, S. Anderson, J. Davis, J. Ginsberg, J. Shade, D. Fulk // In SIGGRAPH 2000 Computer Graphics Proceedings, Annual Conference Series, Addison Wesley, 2000, pp. 131-144

49. Li X. 3D object recognition from range images using pyramid matching / Xinju Li, and Igor Guskov // ICCV, 2007, pp. 1-6

50. Liu B. Research on Shape Similarity and Shape Matching / B. Liu, N. Shangguan // International Conference on Computer Science and Software Engineering, Vol. 1,2008, pp. 1028-1031

51. Lmaati E. A. A 3-D Search Engine based on Fourier Series / Elmustapha Ait Lmaati, Ahmed El Oirrak, Mohamed Daoudi, Driss Aboutajdine, Mohammed

Najib Kaddioui // Computer Vision and Image Understanding, Volume 114, Issue 1,2010, pp. 1-7

52. Loncaric S. A survey of shape analysis techniques // Pattern Recognition, 31,8, 1998, pp. 983-1001

53. Lorensen W. Marching Cubes. A high resolution 3D surface construction algorithm / William E. Lorensen, Harvey E. Cline // in proceedings of the 14th annual conference on Computer graphics and interactive techniques, Vol. 21, №4, 1987, pp. 163-169

54. Lu T. 3D similarity search using a weighted structural histogram representation / T. Lu, R. Gao, T. Wang, Y. Yang // Proceedings of the 11th Pacific Rim conference on Advances in multimedia information processing: Part I, 2010, pp. 348-356

55. Lucchese G. D. L. A frequency domain technique for range data registration / Gianfranco Doretto Luca Lucchese, Guido Maria Cortelazzo // IEEE Trans, on Pattern Analysis and Machine Intelligence, 24(11), 2002, pp. 1468-1484

56. Luna F. D. Introduction to 3D game programming with DirectX 9.0. — Texas: Wordware Publishing, Inc., 2003, 388 p.

57. Masuda T. Registration and Integration of Multiple Range Images for 3-D Model Construction / T. Masuda, K. Sakaue, N. Yokoya // Proceedings of the 13th International Conference on Pattern Recognition, Volume 1, 1996, pp. 879-883

58. Mian A. S. A Novel Representation and Feature Matching Algorithm for Automatic Pairwise Registration of Range Images / A. S. Mian, M. Bennamoun, R. A. Owens // International Journal of Computer Vision, Volume 66, Issue 1, 2006, pp. 19-40

59. Novotni M. 3D zernike descriptors for content based shape retrieval / M. Novotni, R. Klein // In Proc. of the 8th ACM symposium on Solid modeling and applications (SM '03), New York, NY, USA, ACM Press, 2003, pp. 216-225

60. Papaioannou G. Fast Fragment Assemblage Using Boundary Line and Surface Matching / G. Papaioannou, T. Theoharis // IEEE Proc. ICPR/ACVA (2003), 2003, pp. 1-2

61. Petzold С. Programming Windows. - Redmond: Microsoft Press, 1998, 1479 P-

62. PLY (file format) // Wikipedia : the free encyclopedia. URL: http://en.wikipedia.org/wiki/PLY_(file_format) (Дата обращения: 7.10.2013)

63. Pottmann H. Registration without ICP / H. Pottmann, S. Leopoldseder, M. Hofer // Computer Vision and Image Understanding, Volume 95, 2004, pp. 54-71

64. Rijsbergen C. J. V. Information Retrieval, 2nd edn. Butterworths, 1979, pp. 112-140

65. Roth G. Registering two overlapping range images // In 3DIM'99: Second Int. Conf. on 3D Digital Imaging and Modelling, 1999, pp. 191-200

66. Rowe J. Acquisition, representation, query and analysis of spatial data: a demonstration 3D digital library / Jeremy Rowe, Anshuman Razdan, Arleyn Simon // JCDL '03 Proceedings of the 3rd ACM/IEEE-CS joint conference on Digital libraries, 2003, pp. 147-158

67. Rusinkiewicz S. Efficient Variants of the ICP Algorithm / S. Rusinkiewicz, M. Levoy // Third International Conference on 3D Digital Imaging and Modeling. Proceedings, 2001, pp. 145-152

68. Rusinkiewicz S. Real-time 3D model acquisition / Szymon Rusinkiewicz, Olaf Hall-Holt, Marc Levoy // Journal ACM Transactions on Graphics (TOG). Proceedings of ACM SIGGRAPH 2002, Volume 21, Issue 3, 2002, pp. 438-446

69. Sappa A. D. Range image registration by using an edge-based representation / A. D. Sappa, A. R. Specht, M. Devy // In: Proc. Int. Symp. Intelligent Robotic Systems, 2001, pp. 167-176

70. Schön N. Automatic coarse registration of 3D surfaces / N. Schön, G. Häusler // Vision, modeling, and visualization, 2005, pp. 71-178

71. Shilane P. The Princeton Shape Benchmark / Philip Shilane, Patrick Min, Michael Kazhdan, and Thomas Funkhouser // In Shape Modeling International, 2004, pp. 167-178

72. Simon D. Fast and Accurate Shape-Based Registration, Ph. D. Thesis, Carnegie Mellon University, 1996,196 p.

73. Stein F. Structural indexing: Efficient 3-d object recognition / F. Stein, G. Medioni // IEEE Trans. Pattern Anal. Mach. Intell., 14, 1992, pp. 125-145

74. Sun Y. Point fingerprint: A new 3-d object representation scheme / Y. Sun, J. Paik, A. Koschan, D. L. Page, M. A. Abidi // IEEE Transactions on Systems, Man and Cybernetics, 33(4), 2003, pp. 712-717

75. Tang S. An evaluation of local shape descriptors for 3D shape retrieval / Sarah Tang, Afzal Godil // Proc. SPIE 8290 Three-Dimensional Image Processing (3DIP) and Applications II, 2012, pp. 1-15

76. Tangelder J. W. H. A Survey of Content Based 3D Shape Retrieval Methods / J. W. H. Tangelder, R. C. Veltkamp // In proceeding of: 2004 International Conference on Shape Modeling and Applications (SMI 2004), 39(3), 2004, pp. 145-156

77. The Digital Michelangelo Project // Stanford Computer Graphics Laboratory, Stanford University. URL: http://www.graphics.stanford.edu/projects/mich/ (Дата обращения: 24.07.2013)

78. The FastSCAN Cobra scanning system // Polhemus. URL: http://www.polhemus.com/?page=Scanning_Fastscan (Дата обращения: 24.07.2013)

79. The Stanford 3D Scanning Repository // Stanford Computer Graphics Laboratory, Stanford University. URL: http://graphics.stanford.edu/data/3Dscanrep/ (Дата обращения: 7.10.2013)

80. Tombari F. Unique signatures of histograms for local surface description / Federico Tombari, Samuele Salti, Luigi Di Stefano // ECCV'10 Proceedings of the 11th European conference on computer vision: Part III, 2010, pp. 356-369

81. Turk G. Zippered Polygon Meshes from Range Images / G. Turk, M. Levoy // Proc. SIGGRAPH '94 (Orlando, Florida, July 24-29, 1994). In Computer Graphics Proceedings, Annual Conference Series, ACM SIGGRAPH, 1994, pp. 311-318

82. Vanden W. J. Automatic crude patch registration: Toward automatic 3d model building / Vanden Wyngaerd J., Van Gool L. // Computer Vision and Image Understanding, 86(2), 2002, pp. 8-26.

83. Vasa L. CODDYAC: Connectivity Driven Dynamic Mesh Compression / L. Vasa, V. Skala // 3DTV Conference, 2007, pp. 1-4

84. Vranic D. 3D model retrieval with spherical harmonics and moments / D. Vranic, D. Saupe // In Proc. of the DAGM, 2001, pp. 392-397

85. Vranic D.V. 3D Model Retrieval / D.V. Vranic, D. Saupe // In: Proceedings of the Spring Conference on Computer Graphics and its Applications (SCCG2000) (editor B. Falcidieno), 2000, pp. 89-93

86. Vranic D. V. 3D Shape Descriptor Based on 3D Fourier Transform / D. V. Vranic, D. Saupe // In: Proceedings of the EURASIP Conference on Digital Signal Processing for Multimedia Communications and Services (ECMCS 2001) (editor K. Fazekas), 2001, pp. 271-274

87. Vranic D. V. 3D Model Retrieval. Ph. D. Thesis, 2003, pp. 61-73

88. Winkelbach S. Fast Random Sample Matching of 3d Fragments / Simon Winkelbach, Markus Rilk, Christoph Schonfelder, Friedrich M. Wahl // Pattern Recognition. Lecture Notes in Computer Science, Volume 3175, 2004, pp. 129136

89. Winkelbach S. Pairwise Matching of 3D Fragments Using Cluster Trees / Simon Winkelbach, Friedrich M. Wahl // International Journal of Computer Vision, Volume 78, Issue 1, 2008, pp. 1-13

90. Winkelbach S. Low-Cost Laser Range Scanner and Fast Surface Registration Approach / Simon Winkelbach, Sven Molkenstruck, Friedrich M. Wahl. DAGM

2006, LNCS 4174,2006, pp. 718-728

91. Yau H. Automatic Registration Using Virtual Polar Ball / H. T. Yau, L. S. Tsou, H. M. Tseng // Computer-Aided Design & Applications, Vol. 4, Issue 1-4,

2007, pp. 427-436

92. Young M. Viewpoint-coded structured light / M. Young, E. Beeson, J. Davis, S. Rusinkiewicz, R. Ramamoorthi // In Proceedings of CVPR, 2007, pp. 1-8

93. Zhang L. Survey on 3D Shape Descriptors / L. Zhang, M. Fonseca, A. Ferreira // Technical report, Project DecorAR, Fundacao para a Ciencia e Tecnologia, 2007, pp. 1-28

94. Zhang Z. Iterative point matching for registration of free-form curves // INRIA Technical Report No. 1658,1992, pp. 1-42

95. Анизотропия // Википедия : свобод. энцикл. URL: http://ru.wikipedia.org/wiki/AHH30TponHfl (Дата обращения: 5.10.2013)

96. Атанов А. В. Параллельный алгоритм реконструкции объектов по неупорядоченному набору точек на основе радиальных базисных функций / А. В. Атанов, А. А. Крыловецкий, С. Д. Кургалин // Вестник Воронежского государственного технического университета. - Воронеж, 2012. - Т. 8, № 10-2.-С. 13-15

97. Компьютерное зрение // Википедия : свобод, энцикл. URL: http://ru.wikipedia.org/wiki/KoMnbioTepHoe_3peHHe (Дата обращения: 24.07.2013)

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

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

100. Морс Ф.М., Фешбах Г. Методы теоретической физики, Т.1. - М.: ИЛ, 1958.-931 с.

101. Страуструп Б. Язык программирования С++. Специальное издание — СПб.: Невский диалект, 2001, 314 с.

102. Форсайт Д. А. Компьютерное зрение. Современный подход / Д. А. Форсайт, Ж. Понс; Пер. с англ. - М.: Издательский дом Вильяме, 2004. - 928 с.

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

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

105. Шапиро Л. Компьютерное зрение / Л. Шапиро, Дж. Стокман; Пер. с англ. - М.: БИНОМ. Лаборатория знаний, 2006. - 752 с.

Формат PLY

PLY (Polygon File Format или Stanford Triangle Format) - формат файлов для хранения трёхмерных графических объектов, представленных в виде множества полигонов. Основными структурными элементами PLY-файла являются вершины и полигоны. Элементы обладают определёнными свойствами, такими как координаты вершин, индексы вершин полигона, цвет полигона и направление нормали, которые также отражены в формате PLY. Типичный PLY-файл содержит два элемента — вершины и полигоны, т. е. трёхмерные координаты для вершин (х, у, z) и индексы вершин, образующих каждый полигон. В общем случае PLY-файлы могут содержать другие элементы, например, рёбра и материал, а также такие свойства, как координаты текстуры, прозрачность, свойства для внутренней и внешней сторон полигона. Возможно добавление в структуру PLY-файла и пользовательских элементов, однако, это приведёт к тому, что сторонние приложения не смогут их идентифицировать и проигнорируют их. Ниже приведён пример PLY-файла для куба в формате ASCII. Любой файл формата PLY должен содержать заголовок, начинающийся с директивы "ply" и заканчивающийся "end_header". В заголовке находится описание всех элементов объекта со своими свойствами. После заголовка один за другим следуют списки значений свойств каждого элемента. Заголовок файла вне зависимости от формата представляет собой текст в формате ASCII. Числовые данные, следующие за заголовком, записываются в соответствии с форматом файла (ASCII или binary).

Пример PLY-файла, описывающего куб

ply

format ascii 1.0 { ascii/binary, версия формата } comment made by Igor { комментарии } comment this file is a cube

element vertex 8 { определяется элемент "vertex", их 8 в файле }

property float x { у элемента "vertex" есть координата "x" } property float у { координата "у" - также свойство элемента "vertex" }

property float z { координата "z" }

element face 6 { 6 элементов "face" в файле }

property list uchar int vertex_index { элемент "vertex_indices" - набор значений типа "int" } end_header { обозначает конец заголовка } ООО { начало списка вершин } 0 0 1 0 11 0 10 10 0 10 1 111 110

4 0 12 3 { начало списка полигонов } 4 7 6 5 4 4 0 4 5 1 4 15 6 2 4 2 6 7 3 4 3 7 4 0

Кватернионы вращения

Понятие кватерниона ввел У. Р. Гамильтон в 1843 году. Кватернионы удобно использовать для представления вращения в пространстве. Кватернион # определяется его действительной частью, скаляром а, и его мнимой частью, вектором а в трёхмерном пространстве, и обычно записывается как д=а+а. Таким образом, действительные числа можно определить как кватернионы с нулевой мнимой частью, а векторы в трёхмерном пространстве - как кватернионы с нулевой действительной частью. Операция сложения кватернионов определена следующим образом

с1е/

(а + а) + (Ь + Р) =(а + Ь) + (а + Р).

Умножение кватерниона на скаляр:

¿е/

Л(а + а) = Ла + Ла.

Операция перемножения кватернионов:

с!е/

(а + а)(Ь + Р) = (аЬ - а • /?) + {ар + Ъа + ахР).

Произведение кватернионов некоммутативно, то есть

{а + сс){Ъ + Р)*{Ь + Р)(а + а).

Если под кватернионом подразумевать вектор-столбец, состоящий из четырёх компонент, то произведение двух кватернионов удобно представить как произведение ортогональной матрицы размерности 4x4 и вектора с четырьмя компонентами:

(а + а)(Ь + Р) =

а -ах -а у -ссЛ (ЪЛ

а (Ху рх

ссу а2 а -ссх Ру

-а у ах а У

(Б.1)

и

(b + /3)(a + a) =

a

av

-ax -ay

a.

a

a y -az

a,

a,

a

-oc.

-a

у

a

X

a

\rb\

fix

Py

(Б.2)

Сопряжённым кватерниона ц=а+а является кватернион д ~ а — а. Квадрат нормы кватерниона определяется следующим образом:

¿е/

q \2 = q.q = qq=qq = a2+\a\2,

(Б.З)

причём для любой пары кватернионов q и q' выполняется свойство мультипликативности нормы кватерниона: \ qq'\=\q\\q'\-Кватернион

в . 9 а = cos—I-sin—и 2 2

представляет вращение на угол в вокруг единичного вектора и в следующем смысле: если v - некоторый вектор в трёхмерном пространстве, то

Rv = qvq, (Б.4)

где R - матрица вращения, выполняющая то же преобразование. Нужно

■у

также отметить, что в данном случае \q\ = 1.

Метод Якоби вычисления собственных чисел и векторов

Задача нахождения собственных значений и векторов матрицы В из раздела 2.2 решается по методу Якоби. Метод Якоби состоит из цепочки ортогональных преобразований подобия матрицы. Каждое преобразование (ротация Якоби) - это плоский поворот с целью обнуления одного из внедиагональных элементов матрицы. Последовательные преобразования не сохраняют уже установленные нулевые элементы, но, вместе с тем, внедиагональные элементы становятся всё меньше и меньше до тех пор, пока матрица не станет диагональной с точностью до машинного нуля. Накопление в процессе преобразований произведения трансформационных матриц дает матрицу собственных векторов, в то время как диагональные элементы являются собственными значениями. Метод Якоби всегда является надёжным и эффективным методом получения собственных значений и векторов действительных симметричных матриц размерности не больше 10.

Базовая матрица ротации Якоби имеет вид:

_Р_-_Ч_

Км =

-5

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

равны нулю, за исключением двух элементов грд и гдр, равных 5 и —б. Числа

9 9

с и 5 являются косинусом и синусом угла поворота /, так что с = 1.

т

Ротация Якоби преобразует матрицу А согласно формуле А'=Ярс. АЯ .

т

Произведение Ярд А изменяет только строки р и q матрицы А, в то время

как АЯрд меняет только столбцы р и q. Таким образом, измененные

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

а\Р = са1Р ~ в"* 0' * ф

а\Ч = сагд + 5«г> 0' * Р> * * Ч)>

2 2 а рр = с арр ^ ачч 9

а\ч = Б арр+С ачч + '

a'pq = (C ~S )apq+CS(app-aqq)-

Идея метода Якоби состоит в том, чтобы постараться обнулить внедиагональные элементы серией ротаций. Для того, чтобы обнулилось а' рд, угол ротации, согласно формулам, приведенным выше, должен быть

2 2 Q Q

следующим: q = cot(2/) =-= ——-—. Полагая t = —, для

2^^ с

определения t прийдем к следующему уравнению: t +2tq- \ = 0. Меньший по модулю корень этого уравнения соответствует вращению на угол,

7Z

меньший —. Выбор такого угла на каждой из стадий дает наиболее

устойчивый алгоритм. Используя формулу для решения квадратного

уравнения с дискриминантом в знаменателе, меньший корень определяется

sign(q) _ 2

как t =- . . Если величина q такова, что q даст переполнение,

\q\+^lq2+l

полагаем t = —. По значению t определяются с и s: с= , ^ , s = te. При

V*2 +1

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

а РР арр '

а\р = а1р -я(агд +{а1р)> где ^ (тангенс половины угла поворота) определяется как £ = 5

1 + с

Сходимость метода Якоби можно оценить, рассматривая сумму квадратов внедиагональных элементов £ = X а у . После трансформации

уравнения преобразований определяют для этой суммы следующее соотношение:

5'= 5 - 2а рд.

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

элементов при этом возрастает соответственно на ард2. Сумма же квадратов

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

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

соотношение Б = У АУ, где V = К1Я2Я3..., а Щ - матрицы ротации Якоби. Столбцы матрицы V являются собственными векторами. Они вычисляются рекуррентно на каждой стадии по формулам: V- УЩ, где первоначально V— единичная матрица. Для преобразования элементов V используются формулы:

Для уменьшения ошибки округления вышеприведенные формулы следует переписать в терминах величины / (как выше это было сделано для элементов матрицы А).

Получение дальнометрических данных

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

Поверхность исследуемого объекта освещается плоскостью света, создаваемой лазером. При этом положение пятна света (место падения лазерного луча на рассматриваемую поверхность), которое фиксируется камерой по яркости, находится как точка пересечения лазерного луча с лучом проектирования Р. Существует ряд моделей сканеров, дающих исключительно высокую точность формируемых дальнометрических данных. Однако, в связи с большой стоимостью высокоточного оборудования, для получения собственных данных мы использовали собственную измерительную систему, созданную нами с применением программного обеспечения БАУГО-Ьазегесаппег. Эта система работает по схеме, описанной выше, и включает в себя недорогие и доступные средства:

- стенд для проведения экспериментов;

- цифровая камера (например, простая веб-камера);

- лазерная указка со специальной насадкой в качестве источника света;

- программное обеспечение ОАУГО-Ьавегесаппег для обработки получаемых данных.

Л£

Рисунок 1. Дальнометрическая система

Схема проводимого эксперимента представлена на рис. 2.

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

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

Псевдокод алгоритма изменения разрешения

ChangeResolution(LMIN,LMAX,CMAX,MESH) // Инициализация приоритетной очереди рёбер PQ = InitializePriorityQueueO Для всех рёбер е поверхности

С = ShapeChangeMeasure(e,MESH) // вычисление изменения формы поверхности

W = EdgeLengthWeight(LMIN,LMAX,e,MESH) // вычисление веса ребра AccumulateShapeChange(e) = 0 // суммарное изменение формы поверхности для ребра е приравнивается нулю

If (CanOperateOn(e,LMIN,LMAX,СМАХ,MESH)) // ребро включается в очередь если над ним

lnsertEdgelnPriorityQueue(e,W*C,PQ) // необходимо выполнить какую-либо операцию // Нормализация рёбер

While (!Empty(PQ)) // пока не опустеет очередь

edge е = PopPriorityQueue(PQ) // берём очередное ребро If (Length(e)>LMAX) // длина ребра больше LMAX Для всех рёбер ое из старой окрестности

RemoveEdgeFromPriorityQueue(oe,PQ) //убираем ребро ое из очереди vertex v = SplitEdge(e,MESH) // операция разбиения ребра Для всех рёбер пе из новой окрестности

AccumulateShapeChange(ne) = AccumulateShapeChange(ne) + О С = ShapeChangeMeasure(ne,MESH)+AccumulateShapeChange(ne) W = EdgeLengthWeight(LMIN,LMAX,ne,MESH) If (CanOperateOn(ne,LMIN, LMAX, CMAX, MESH)) lnsertEdgelnPriorityQueue(ne,W*C,PQ) If (Length(e)<LMIN) //длина ребра меньше LMIN Для всех рёбер ое из старой окрестности RemoveEdgeFromPriorityQueue(oe,PQ) vertex v = ColIapseEdge(e,MESH) // операция сворачивания ребра Для всех рёбер пе из новой окрестности

AccumulateShapeChange(ne) = AccumulateShapeChange(ne)+ ShapeChange(e) //добавляем к суммарному изменению формы для

ребра пе изменение формы для ребра е

С = 8ИареСИапдеМеазиге(пе,МЕЗН)+Ассити1а1е5ЬареСЬапде(пе) = ЕЬде1епд^е1дМ(1М1М,1МАХ,пе,МЕЗН) (СапОрега1еОп(пе,1М1М,1МАХ1СМАХ,МЕ5Н)) lnsertEdgelnPriorityQueue(neIW*C,PQ)

Исходный код основных классов и методов, реализующих модель поиска

трёхмерных моделей в базе данных

class Baseltem {

public:

int id;

char path[256] ;

float frate, ISIrate, rate;

float area; float* distHist; float* PCA_EVec; float* PCA_EVal; Spinlmage ISI;

void FeaturesFroraFile();

inline bool operator< (const Baseltem& bi){ return (rate<bi.rate); } inline bool operator> (const BaseltemS bi){ return (rate>bi.rate); } inline bool operator<= (const BaseltemS bi){ return (rate<=bi.rate); } inline bool operator>= (const BaseltemS bi){ return (rate>=bi.rate); }

} ;

void Search(Baseltem qi, Baseltem* {

float maxFrate = O.Of; float minFrate = 100.Of;

for (int i=0; i<100; i++) {

is[i].frate =

+EuclidDist(is[i].distHist,

is)

EuclidDist(is[i].PCA_EVal, qi.distHist)+abs(qi.area-is[i].area); if (is[i].frate > maxFrate) maxFrate = is[i].frate; if (is[i].frate < minFrate) minFrate = is[i].frate; is [i].ISIrate = SpinlmageCorrCoeff(is[i].ISI, qi.ISI,

qi.PCA_EVal)

O.Of);

for (int i=0; i<100; i++) {

is [i] .frate = (maxFrate-is[i].frate)/(maxFrate-minFrate); is[i].rate = is [i].frate*is[i].ISIrate;

}

heapSort(is, 100);

chdir(qi.path); HANDLE file; fstream fileStream;

file = CreateFileCsearch_res.txt", FILE_ADD_FILE, FI LE_S H ARE_WR IT E, NULL, CREATE_ALWAYS, FILE_ATTRIBUTE_NORMAL, NULL); CloseHandle(file); fileStream.open("search_res.txt");

for (int i=99; i>=0; i—) {

fileStream « is[i].id « " " « is[i].rate « " " «

is [i] .ISIrate« " " « is[i]. frate « "\n"; }

fileStream.close();

}

J Ii

//-------------------------------------------------------------->

class CheMesh {

public:

CheMesh( void ); ~CheMesh( void ); void Free( void );

void Clear(); // set down color and vertex size

void MeshFromPLYFile( const char* fName ); // loads model from PLY file void LoadComputelntegralSpinlmage(int SpinlmageType); // compute spin images if there is no file with precomp Sis

void CreateBuffersInDXDevice(LPDIRECT3DDEVICE9); // initialize DXDevice buffers

void FillBuffers(); // copy 3D data to the buffers void Transform(D3DXMATRIX*); // transform data by matrix

void Transform(float*, float*); // rotate and translate data by matrix R & vector T

int FindVertex(int x, int y, HWND window, D3DXMATRIX *pProj, D3DXMATRIX *pView, D3DXMATRIX *pWorld);

void TranslateToOrigin(); void ToOptimalScale(); float ComputeArea(); void ComputeDistHist(); void ComputeVertexPCA(); void VertexPCAtoFile(); void FeaturesToFile();

void SetVertexColor( int n, DWORD value ); void SetVertexSize( int n, float value ); void SetFullTransformMatrix(D3DXMATRIX);

D3DXVECT0R3* GetPoints();

D3DXVECTOR3* GetNormals();

D3DXVECTOR3 GetMean();

int GetNumOfPoints();

int GetNumOfTriangles();

char* GetName();

char* GetPathO;

float GetResolution();

float GetScaleFactor();

Spinlmage GetlntegralSpinlmage();

D3DXVECTOR3 GetMaxVertexPCA_EVec();

D3DXMATRIX* GetFullTransformMatrix();

LPDIRECT3DVERTEXBUFFER9 GetVBSolid();

LPDIRECT3DVERTEXBUFFER9 GetVBWireframe();

LPDIRECT3DVERTEXBUFFER9 GetVBBox();

IDirect3DIndexBuffer9* GetIB();

IDirect3DIndexBuffer9* GetlBBox();

private:

char name[128]; // name of the mesh char path[256];

D3DXVECTOR3 *points; // mesh's points

int numOfPoints;

// mesh points' attributes

D3DXVECTOR3 *normals;

float *weights;

DWORD *colors;

float *sizes;

bool *active;

set<int> ^neighbours; //------------------

// mesh's features D3DXVECTOR3 mean; float resolution; float scaleFactor; float area; float* distHist; Spinlmage ISI; float **vertexPCA_EVec;

float *vertexPCA_EVal; //-----------------------

CTriangle *triangles; // mesh's triangles int numOfTriangles;

// matrices & buffers for visualization

D3DXMATRIXA16 *fullTransformMatrix; //

LPDIRECT3DVERTEXBUFFER9 pVBTriSolid, pVBTriWireframe; // FOR

Visualisation

IDirect3DIndexBuffer9* pIB; //

LPDIRECT3DVERTEXBUFFER9 pVBBox;

IDirect3DIndexBuffer9* pIBBox; // -----------------------

} ;

float CheMesh: :ComputeArea() {

float S = 0;

for (int i=0; i<this->numOfTriangles; i++) {

float al, a2, a3, p;

al = D3DXVec3Length(&(points[triangles[i].vl]-

points[triangles[i].v2]));

a2 = D3DXVec3Length(&(points[triangles[i] .v2]-

points[triangles[i].v3]));

a3 = D3DXVec3Length(&(points[triangles[i].v3]-

points[triangles[i].vl]));

p = (al+a2+a3)/2;

S += sqrt(p*(p-al)*(p-a2)*(p-a3));

}

area = S; return S;

}

void CheMesh::ComputeDistHist() {

float d; float t=0.1;

distHist = new float[10];

for (int i=0; i<10; i++) distHist[i]=0.Of;

for (int i=0; i<this->numOfPoints; i++) {

d = D3DXVec3Length(&(mean-points [i]));

int k = floor(d/t);

distHist[k]+=1.Of/numOfPoints;

}

}

void CheMesh::ComputeVertexPCA() {

float **C;

float Cxx, Cyy, Czz, Cxy, Cxz, Cyz;

Cxx = 0; Cyy = 0; Czz = 0; Cxy = 0; Cxz = 0; Cyz = 0;

for {

[int i = 0; iCnumOfPoints; i++)

}

int

C =

C[0]

C[0]

C[1]

C[1]

C[2]

C[2]

Cxx += points[i] .x Cyy += points[i].y Czz += points[i].z Cxy += points[i].X Cxz += points[i].x Cyz += points[i].y

N = numOfPoints ; new float*[3]; = new float[3]; [0] = Cxx/N; C[0][1] = new float[3]; [0] = Cxy/N; C[l] [1] = new float [3]; [0] = Cxz/N; C [2] [1]

points[i].x; points[i].y; points[i]. z; points[i].y; points[i].z; points[i].z;

Cxy/N; C[0][2] = Cxz/N; Cyy/N; C[l][2] = Cyz/N; Cyz/N; C[2][2] = Czz/N;

int nrot;

vertexPCA_EVec = new float*[3]; vertexPCA_EVec[0] = new float[3] vertexPCA_EVec[1] = new float[3] vertexPCA_EVec[2] = new float[3] vertexPCA_EVal = new float[3];

jacobi(C, 3, vertexPCA_EVal, vertexPCA_EVec, &nrot)

delete [] C[0];

delete [] C[1];

delete [] C[2];

delete [] C;

class Spinlmage {

public:

Spinlmage(void);

int operator- (const SpinlmageS si) const;

void SetSIType(int value){ this->SIType = value; };

void SetlmageWidth(int value);

void SetAngleSupport(int value){ this->angleSupport = value; }; void SetBinAlphaSize(float value){ this->binAlphaSize = value; }; void SetBinBetaSize(float value){ this->binBetaSize = value; }; void SetBinGammaSize(float value){ this->binGammaSize = value; };

int GetSIType(void){ return this->SIType; }; int GetlmageWidth(void){ return this->imageWidth; }; int GetAngleSupport(void){ return this->angleSupport; }; float GetBinAlphaSize(void){ return this->binAlphaSize; }; float GetBinBetaSize(void){ return this->binBetaSize; }; float GetBinGammaSize(void){ return this->binGammaSize; }; void Zeros(); void Free();

void CreateSpinlmage(int OPoint, D3DXVECTOR3 *V, D3DXVECTOR3 *N); void CreateSpinlmage(D3DXVECTOR3 Op, D3DXVECTOR3 On, D3DXVECTOR3 D3DXVECTOR3 *N);

void ToBMP(const char* fn); void MatrixToFile(void); void FromFile(char* fileName); void ToFile(const char* fn);

int pointID; int ***SI;

float **eigenVectors; float *eigenValues; int *pointIDsInSI; int unemptyBins;

private:

void SIAlphaBeta(D3DXVECTOR3 Op, D3DXVECT0R3 On, D3DXVECT0R3 x, float *alpha, float *beta);

void SIAlphaBetaGamma(D3DXVECTOR3 Op, D3DXVECTOR3 On, D3DXVECTOR3 Xp, D3DXVECTOR3 Xn, float *alpha, float *beta, float *gamma);

void SIBinIJ(float alpha, float beta, int *i, int *j);

void SIBinIJK(float alpha, float beta, float gamma, int *i, int *j, int

*k) ;

void BilinearWeights (float alpha, float beta, int i, int j, float *a, float *b);

int SIType;

float binAlphaSize, binBetaSize, binGammaSize; int imageWidth;