Введение к работе
Актуальность темы. В настоящее время проблемы реконструкции и поиска схожих по форме поверхности трёхмерных моделей в базах данных являются одними из актуальных направлений теоретических и прикладных исследований. Научные исследования в области трёхмерного компьютерного зрения активно ведутся лабораториями Stanford Computer Graphics Laboratory (Стэнфорд, США), Center for Geometry, Imaging and Virtual Environments (Утрехт, Нидерланды), Laboratoire d'rnformatique Fondamentale de Lille (Вильнёв-д'Аск, Франция), Microsoft Research Cambridge (Кембридж, Великобритания), Princeton Shape Retrieval and Analysis Group (Принстон, США). Информационные системы трёхмерного компьютерного зрения решают задачи построения геоинформационных систем, автоматизации биомедицинских комплексов, удалённого присутствия, представления трёхмерной информации, контроля производства и т. п. Алгоритмы компьютерного зрения применяются для навигации мобильных роботов, беспилотных летательных аппаратов, автомобилей, распознавания объектов, построения и анализа точных трёхмерных моделей и др.
В целях упрощения аппаратной части программно-аппаратных комплексов для автоматической реконструкции трёхмерных моделей решение ряда математических и алгоритмических задач трёхмерного компьютерного зрения в настоящее время возлагается на обрабатывающую программу. Постоянный рост доступности и числа трёхмерных моделей делают всё более востребованными быстрые и эффективные методы и алгоритмы поиска трёхмерных моделей в базах данных. Использование как методов реконструкции, так и методов поиска трёхмерных моделей непосредственно связано с проблемой анализа формы поверхности трёхмерных моделей. Сложность решения данной проблемы связана с тем, что в системах компьютерного зрения поверхности трёхмерных моделей, как правило, представляют собой множества точек и соединяющих эти точки рёбер. Один из наиболее успешных подходов к описанию формы трёхмерных моделей заключается в построении дескрипторов («инвариантов») формы поверхности, их анализе и обработке. D.V. Vranic и D. Saupe (Лейпциг, Германия) предлагают использовать для поиска трёхмерных моделей дескрипторы, основанные на трёхмерном дискретном преобразовании Фурье. Метод преобразования дескрипторов поверхности при помощи сферических гармоник для получения инвариантных представлений дескрипторов представлен в работах М. Kazhdan, Т. Funkhouser и S. Rusinkiewicz (Принстон, США). Сегодня значительная часть исследований в данной области сосредоточена на разработке новых дескрипторов поверхности, которые, однако, часто оказываются слишком сложными для реализации и малоэффективными в вычислительном плане. При этом не уделяется достаточного внимания таким проблемам, как: верификация соответствующих точек поверхностей в рамках метода первичного совмещения поверхностей трёхмерных моделей, нормализация трёхмерных моделей и устойчивость дескрипторов к зашумлённости данных.
Представленная диссертационная работа посвящена разработке и исследованию модели поиска, методов реконструкции трёхмерных моделей, отличающихся применением дескрипторов, основанных на спиновых изображениях, что обеспечивает высокую скорость и эффективность работы использующих их систем. В основе предлагаемых методов и модели лежат усовершенствованные классические подходы к описанию формы поверхности трёхмерных моделей. Использование в модели поиска
интегральных спиновых изображений в качестве глобальных дескрипторов поверхности наряду с хорошо зарекомендовавшим себя методом нормализации трёхмерных моделей позволяет превзойти по производительности существующие методы поиска. Разработка метода реконструкции с реализацией в нём новых подходов к проблемам выбора точек и верификации соответствий, возникающих в рамках процедуры первичного совмещения, обеспечивает возможность работы метода в программно-аппаратных комплексах с системами сканирования с низкой разрешающей способностью.
Диссертационная работа выполнена на кафедре цифровых технологий Воронежского государственного университета по НИР «Разработка новых методов обработки, хранения и передачи информации в информационно-коммуникационных системах» № ГР 01201170666 (2011 г.) аналитической ведомственной целевой программы «Развитие научного потенциала высшей школы» и НИР «Разработка моделей, методов и алгоритмов обработки информации для создания информационных технологий нового поколения» № ГР 01201263910 (2012-2014 гг.).
Цель и задачи исследования. Цель работы - создание и исследование теоретических методов и алгоритмов анализа формы поверхности трёхмерных моделей, реконструкции, поиска и визуализации трёхмерных моделей.
Для достижения цели в работе решались следующие задачи:
-
Создание новых локальных дескрипторов поверхности.
-
Разработка метода первичного совмещения поверхностей с использованием предложенных локальных дескрипторов и метода верификации соответствующих точек в рамках решения задачи автоматической реконструкции поверхности трёхмерных моделей.
-
Создание и исследование модели поиска трёхмерных моделей в базах данных и метода нормализации трёхмерных моделей.
-
Разработка и исследование алгоритмов работы предложенных методов и модели, их реализация в форме компьютерных программ и проведение вычислительных экспериментов.
Объект исследования - дальнометрические изображения, поверхности моделей, получаемые посредством трёхмерного сканирования, трёхмерные полигональные модели, локальные и глобальные дескрипторы трёхмерной поверхности; предмет исследования - методы совмещения трёхмерных поверхностей, автоматической реконструкции, нормализации моделей, модель поиска трёхмерных моделей, способы представления формы поверхности таких моделей, алгоритмы предложенных методов.
Методы исследования. При выполнении работы использовались: методы математического и компьютерного моделирования, математические и статистические методы обработки данных, методы теории алгоритмов, теории вероятностей, численные методы, методы визуального проектирования.
Новизна работы:
1. Предложены новые локальные дескрипторы поверхности, развивающие принципы построения известных дескрипторов спиновых изображений за счёт использования информации о локальной ориентации поверхности, что обеспечивает лучшие по сравнению со спиновыми изображениями результаты решения задачи реконструкции трёхмерных моделей и большую устойчивость к шуму.
-
Разработаны: метод первичного совмещения поверхностей, особенностью которого является использование предложенных локальных дескрипторов поверхности, и метод верификации соответствующих точек совмещаемых поверхностей.
-
Созданы: модель поиска трёхмерных моделей в базах данных по трёхмерному шаблону, отличительной особенностью которой является использование интегральных спиновых изображений в качестве глобальных дескрипторов поверхности, и метод нормализации трёхмерных моделей.
-
На основе разработанной модели и предложенных методов трёхмерного компьютерного зрения созданы и исследованы новые алгоритмы, проанализированы результаты их программной реализации.
Практическая значимость результатов работы заключается в том, что предложенные методы, модель, алгоритмы и программы можно использовать для модификации и развития систем трёхмерного компьютерного зрения, что позволит повысить их эффективность, устойчивость результатов к погрешностям в данных, увеличить скорость их работы. Применение новых локальных и глобальных дескрипторов поверхности трёхмерных моделей даст возможность перейти к построению полностью автоматизированных, робастных и приближенных к выполнению в реальном масштабе времени систем реконструкции трёхмерных моделей, распознавания объектов, поиска трёхмерных моделей в базах данных и т. п.
Область исследования - содержание диссертации соответствует паспорту специальности 05.13.17 - «Теоретические основы информатики» (физико-математические науки), область исследований соответствует п. 2 «Исследование информационных структур, разработка и анализ моделей информационных процессов и структур»; п. 5 «Разработка и исследование моделей и алгоритмов анализа данных, обнаружения закономерностей в данных и их извлечения; разработка и исследование методов и алгоритмов анализа текста, устной речи и изображений»; п. 7 «Разработка методов распознавания образов, фильтрации, распознавания и синтеза изображений, решающих правил. Моделирование формирования эмпирического знания».
Реализация результатов исследования. Результаты диссертации в форме элементов системы компьютерного зрения для реконструкции трёхмерных моделей объектов реального мира, а также модели поиска трёхмерных моделей, включающие ряд отдельных методов и алгоритмов, используются в учебном процессе Воронежского государственного университета при чтении спецкурсов, выполнении выпускных квалификационных и курсовых работ.
Основные результаты, выносимые на защиту:
1. Локальные дескрипторы поверхности: трёхмерные и ориентированные спиновые
изображения, обладающие лучшими описательными характеристиками по сравнению
со спиновыми изображениями.
2. Метод первичного совмещения поверхностей трёхмерных моделей,
принципиальным отличием которого является использование в качестве локальных
дескрипторов поверхности предложенных трёхмерных и ориентированных спиновых
изображений, и быстрый метод верификации соответствующих точек совмещаемых
поверхностей.
-
Модель поиска трёхмерных моделей в базах данных, особенностью которой является применение интегральных спиновых изображений в качестве глобальных дескрипторов поверхности, используемая совместно с разработанным методом нормализации трёхмерных моделей.
-
Алгоритмы, построенные на основе созданной модели и предложенных методов, и результаты их программной реализации.
Апробация работы. Основные положения диссертационной работы докладывались и обсуждались на 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 рисунков.
