Содержание к диссертации
Введение 4
1 Анализ методов представления и компрессии сигналов, 14
Вейвлет-анализ как альтернатива анализу Фурье 14
Кратномасштабный анализ 17
Вейвлет-функции. 17
Быстрое вейвлет-преобразование 19
Структура вейвлет-разложения сигнала 19
Вычисление быстрого вей влет-преобразования 21
Нормализация вей влет-базисов 24
Вейвлет-пакеты , 25
Вейвлеты Хаара, вейвлеты Добеши-и Койфлеты. 27
Выбор базисной вейвлет-функции. 32
Компрессия сигналов на основе вейвлет-преобразований; 34
Сравнительный анализ статистических методов компрессии .37
1,9- Сравнительный анализ методов компрессии на основе
ортогональных разложений 40
Сравнительный анализ вейвлет-преобразований 43
Многомерные преобразования 49
Выводы по главе 1 53
2 Адаптивное представление объектов полигональными
триангуляционными моделями 55
Обоснование выбора модели аппроксимации поверхности 55
Триангуляция Делоне. 57
Определение триангуляционной модели поверхности 60
Анализ известных методов компрессии триангуляционных
моделей. 63
2АЛ Методы геометрической оптимизации. 65
Адаптивные методы компрессии триангуляционных моделей 68
Сравнение методов 69
Триангуляционные модели сигналов в R2 71
Разработка кратном ас штабной триангуляционной модели поверхности 72
Декомпозиция триангуляционной модели 74
Реконструкция триангуляционной модели 76
2.7 Методы перестройки триангуляционной модели. 82
Выводы по главе 2 83
3 Разработка новых спектральных методов- компрессии
триангуляционных моделей на основе дискретного всЙвлст-
преобразования 84
Кластерные методы компрессии триангуляционных моделей 85
Альтернативная схема кратномасштабного анализа в пространстве R1 92
Разбиение триангуляционной модели по нерегулярной схеме 94
Слияние граней триангуляционной модели. 96
Компрессия информации о связности триангуляционной модели 99
Компрессия информации о геометрии триангуляционной модели 101
Особенности программной реализации методов компрессии 101
Постановка задачи 101
Общая характеристика. 102
Структуры представления данных 110
3^7.4 Обобщенный алгоритм компрессии.триангуляционных моделей.... 112
3.8 Результаты компрессии триангуляционных моделей 115
Выводы по главе 3 122
Заключение 123
Список использованной литературы 125
Введение к работе
В последние годы наблюдается интенсивное развитие средств информатизации и телекоммуникаций, в том числе и сети Internet, что является важнейшим фактором ускорения мирового прогресса, основой информационного обмена. По мере совершенствования графических средств обработки изображений заметно увеличивается поток цифровых данных, передаваемых по каналам связи с ограниченной, скоростью, причем, повышение требований к качеству триангуляционных моделей, другими словами, полигональных моделей содержащих только треугольные грани, приводит к лавинообразному увеличению объема хранимых и передаваемых данных. Эффективным способом сокращения интенсивности цифрового потока является компрессия передаваемых данных с последующим восстановлением на принимающей стороне.
Компрессия данных без потери, качества накладывает жесткую нижнюю границу на размер сообщения. Этой границей является энтропия сообщения. Для триангуляционных моделей, которые по своей природе весьма избыточны, не требуется абсолютно точной реконструкции исходной информации. В связи с этим представляется целесообразным применять методы компрессии триангуляционных моделей с потерей информации.
На основе проведенного анализа работ исследователей в области компрессии сигналов и изображений-можно выделить методы компрессии, ориентированные на стационарные и нестационарные сигналы.
В настоящее время стало очевидно, что традиционный аппарат анализа стационарных сигналов, каким является преобразование Фурье, оказывается малоэффективным для представления фрактальных функций и сигналов, другими словами, функций.с локальными особенностями, например, разрывами, получивших широкое распространение в последние годы.
Одним из основных недостатков преобразования Фурье является использование в качестве базовой функции синусоиды, периодически продол-
жаемой на R \ В условиях ограничения числа членов ряда Фурье или спектра разложения такая функция принципиально не способна описывать нестационарные сигналы [3, 19, 20, 21, 22, 25, 26, 27 и др.]. Ограничение бесконечного числа членов в ряде Фурье приводит к возникновению эффекта Гиббса.
Недостатки преобразования Фурье были исследованы Табором в [18], где он использовал функцию Гаусса в качестве базисной оконной функции, преобразование которой также является, функцией Гаусса, что позволяет локализовать и обратное преобразование Фурье. В этом случае сигнал оказывается локализованным во времени, но при оконном преобразовании Фурье окно имеет фиксированный размер, не зависящий от рассматриваемого масштаба. Кроме того, размер окна определяется различными функциями по времени и частоте.
К недостаткам такого подхода следует отнести жесткость определения частотно-временного окна, что в свою очередь, накладывает ограничения на класс возможных исследуемых сигналов [3, 19, 20, 21, 25, 26, 28 и др.]. Существуют и другие альтернативы анализу Фурье, например, разложение по> базисным функциям Эрмита, Лежандра, Чебышева [67, 68, 69, 70], которые нашли применение в различных задачах обработки сигналов.
В последнее время широко используются методы обработки нестационарных сигналов, основанные на принципиально новом математическом аппарате теории вейвлетов и кратномасштабного анализа, что позволяет анализировать различные частотные компоненты сигналов, локализованные во времени. По мнению большинства исследователей [3, 19, 20, 21, 22, 23, 24, 25, 26, 28, 29, 30, 144 и др.] вейвлет-преобразование обладает существенными преимуществами по сравнению с преобразованием Фурье.
Действительно, для нестационарных сигналов оказывается важным определить моменты времени, когда изменяется частотная характеристика, поэтому базисные функции должны иметь конечную область определения.
В настоящей работе обозначения являются общепринятыми и оформлены в соответствии с "Справочником по математике" Г. Корна и Т. Корпа [66].
Некоторые аспекты математической теории вейвлетов.были изучены достаточно давно. А. Хаар предложил в 1910 году полную ортонормальную систему базисных функций с локальной областью определения [1]. Гроссман и Морле в работе [2] по цифровой обработке и анализу сейсмических сигналов впервые ввели понятие интегрального или дискретного вейвлет-преобразования, однако некоторыми исследователями [3] отмечается, что техника использования, сдвигов и растяжений использовалась Кальдероном
[4].
Понятие кратномасштабного анализа было впервые введено Мейером [8] и Малла [5] и в дальнейшем развито Малла [6,' 7]. В работах [5, 6, 7] Малла предложил алгоритмы вейвлет-разложения или декомпозиции и вейв-лет-реконструкции, использующие аппарат кратномасштабного анализа. Представление разложения в прямую сумму предложено Коэном, Добеши и Фово в [10].
Вейвлеты Мейера [9] являются ортонормальными вейвлетами, основанными на преобразовании Фурье и.имеющими компактный носитель. К сожалению, ни вейвлеты Мейера, ни некоторые другие вейвлеты, например, вейвлет Стремберга [11], Вейвлеты Баттла-Лемарье [14, 15], не имели компактного носителя.
Впервые ортонормальные вейвлеты с компактным носителем были предложены на основе аппарата кратномасштабного анализа Добеши в [16]. Вейвлет-пакеты были введены Кауфманом, Куейком, Мейером и Викерхау-зером в [17].
В середине 90-х годов Свелденс предложил новый метод вычисления вейвлет-преобразования - лифтинг, имеющий ряд преимуществ по сравнению с классической схемой,Малла [46]. В работе [31] был разработан эффективный алгоритм вычисления вейвлет-преобразования в виде последовательности простых шагов, позволяющий создавать вейвлеты второго поколения [47], которые не являются растяжениями и сдвигами одной функции.
Рассмотрим свойства преобразований, которые являются наиболее
важными при компрессии сигналов и изображений.
Во-первых, для эффективного представления любого изображения важную роль играет разрешение или масштаб. В структуре сигналов и изображений присутствуют элементы различных размеров. В связи с этим преобразование должно позволять анализировать изображение одновременно и независимо при различном разрешении.
В случае многомерных сигналов, к которым относятся изображения, видеопоследовательности и триангуляционные.модели, каждая спектральная область соответствует определенному разрешению и особенностям базисных функций. Особенности базисных функций (см. п:1.5) определяют способность преобразования корректно анализировать структуры, типичные для определенного вида изображений. Примером могут служить контуры и линии: Следовательно, для более эффективного анализа сигналов желательно иметь преобразование, с помощью которого становится возможным декомпозировать входной сигнал на локальные частотные области.
Во-вторых, кроме частотной локализации, базисные функции должны быть.локальными и в пространстве. Необходимость в-пространственной локализации возникает в случае, когда информация о местоположении деталей. сигнала или изображения является важной.
В-третьих, желательно потребовать выполнения требования ортогональности преобразования. Вейвлет-преобразование, как правило, является ортогональным несмотря на отсутствие необходимости ортогональности в субполосном кодировании [23, 144]. Ортогональность функций упрощает многие вычисления. В [144] показано, что неортогональное преобразование может являться непригодным для кодирования.
В-четвертых, вычисление преобразования должно осуществляться на основе эффективных алгоритмов. Необходимо отметить, что невозможность практической реализации преобразования в реальном масштабе времени сводит на нет все его положительные свойства.
В настоящее время вейвлеты используются во многих секторах совре-
менной науки. Являясь эффективным инструментом обработки сигналов различной природы, кратномасштабный анализ: нашел применение в таких отраслях, как: цифровая обработка изображений и сигналов, компрессия изображений и видеопоследовательностей [40, 41,.42, 43, 44,91 и др. ] численные методы, геометрическое моделирование, компьютерная графика (распознавание образов (см., например, [48, 49]), редактирование изображений [50], обработка кривых [3^ 52, 53], поверхностей [51, 54, 55, 137, 145, 154 и др.],, твердотельных моделей [56]), математика, математическая и теоретическая физика [21, 22, 32, 33 и др.], астрономия, медицина и биология [21, 31, 34, 35, 36, 37, 38, 39 и др.], авиация и пр. [3,6,21,22,24,25, 136, 137, 144, 145 и др.].
В компьютерной [рафике большинство применений теории вейвлетов связано с компрессией изображений (см., например, [19, 20, 21, 25, 57, 58; 59, 60, 75, 78]), Один из первых алгоритмов, который был разработан для компрессии отпечатков пальцев по заказу ФБР США и позволил выполнять поиск в многомиллионной базе данных в реальном масштабе времени, описан в [61, 62, 63]. Коэффициент сжатия в среднем составил 15:1.
По мере совершенствования графических средств геоинформационных систем растут ^требования к реалистичности, т.е. разрешению или уровню: детализации триангуляционных моделей, что приводит к заметному росту объемов обрабатываемых моделей, и, в свою очередь, к увеличению нагрузки на вычислительные компоненты. Необходимо отметить, что многие, используемые в геоинформационных системах, методы обработки триангуляции, имеют вычислительную сложность выше линейной и наращивание мощности информационной системы не приводит к пропорциональному уменьшению времени обработки моделей.
Резюмируя.отметим, что существующие.статистические и;словарные алгоритмы не обеспечивают приемлемой степени компрессии триангуляционных моделей, существующие методы компрессии с потерей информации не являются эффективными по интегральному критерию степени компрессии модели, точности представления полученной модели при заданной степени
компрессии; требований метода к вычислительным ресурсам. Компрессия моделей, выполняемая с помощью известных ортогональных разложений, характеризуется существенной вычислительной сложностью, неустойчивостью и сильными колебаниями ошибки.
Таким образом, в настоящее время существует актуальная научно-техническая проблема разработки новых методов компрессии триангуляционных моделей на основе вейвлет-преобразования.
Цель работы
Цель работы заключается в повышении эффективности компрессии триангуляционных моделей посредством разработки спектральных методов анализа на основе дискретного вейвлет-преобразования, пригодных для практического применения.
Задачи исследования
В рамках поставленной цели в диссертационной работе были решены следующие основные задачи исследования:
Анализ существующих методов геометрической оптимизации
триангуляционных моделей.
Разработка многомасштабной модели представления объектов реального мира посредством триангуляции.
Разработка метода декомпозиции и реконструкции триангуляционных моделей.
Разработка новой схемы нерегулярного разбиения-слияния граней триангуляционной модели.
Разработка эффективных по критерию среднеквадратичного отклонения методов компрессии триангуляционных моделей с помощью новой схемы разбиения-слияния граней.
Разработка программы экспериментального моделирования компрессии триангуляционных моделей кластерным методом с воз-
можностью реализации и хранения собственных фильтров во внутренней базе данных фильтров программы. Разработка библиотеки классов и методов компрессии триангуляционных моделей поверхности рельефа,, реализующей новый метод компрессии триангуляционных моделей.
Методы исследования
При выполнении диссертационной работы использовались методы теории спектрального анализа, аппарат матричной алгебры, методы вычислительной геометрии, машинной графики, методы теории вейвлетов и кратно-масштабного анализа.
Научная новизна
Предложена новая схема представления триангуляционных моделей в виде многослойной структуры.
Предложена новая схема разбиения-слияния граней модели.
Предложен новый метод нерегулярного кратномасштабного анализа триангуляционных, моделей с линейной вычислительной. сложностью (О(п) в среднем) на основе вейвлет-преобразования и новой схемы разбиения-слияния.
На основе нового метода нерегулярного кратномасштабного анализа триангуляционных моделей разработан метод компрессии триангуляционных моделей, сочетающий низкую вычислительную сложность и высокое качество обработки.
Получены выражения для порождающих масштабирующих функций и вейвлет-функций в пространстве R3 и порожденных. ими пространств.
Предложен кластерный метод компрессии триангуляционных моделей на основе иерархической древовидной структуры.
Практическая ценность
Разработан и реализован новый метод нерегулярного кратномасштабного анализа триангуляционных моделей на основе вейвлет-преобразования, не требующий больших вычислительных.затрат,
Предложенный метод нерегулярного.кратномасштабного анализа триангуляционных моделей с линейной в среднем трудоемкостью позволяет увеличить производительность операций обработки моделей поверхности, построенных по нерегулярным наборам вершин.
- Разработанный метод компрессии триангуляционных моделей: поверхности рельефа является эффективням по критерию вычислительной сложности и среднеквадратичного отклонения, что позволило существенно повысить потенциальные объемы обрабатываемых данных при компрессии реальных триангуляционных моделей поверхности.
Разработана и внедрена библиотека-компрессии триангуляционных- моделей поверхности рельефа, реализующая новый метод компрессии триангуляционных моделей с помощью нерегулярного кратномасштабного анализа.
Разработана и доведена до реализации программа экспериментального моделирования компрессии триангуляционных моделей кластерным методом на основе иерархической древовидной структуры с набором из 89 вейвлет-функций: с возможностью реализации и хранения собственных фильтров во внутренней базе данных фильтров протраммы.
Реализация результатов работы
Разработанный метод компрессии триангуляционных моделей внедрен виде алгоритма в прикладной геоинформационной системе в ООО Термостройкомплект".
Кроме того, материалы исследований используются в учебном процессе при чтении курса лекций "Моделирование" по специальности 22.01 "Вычислительные машины, комплексы, системы и сети" в Волгоградском государственном техническом университете и научно-исследовательской работы студентов.
Апробация работы и публикации
По результатам выполненных исследований опубликовано 24 печатные работы. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской конференции "Прогрессивные технологии в обучении, и производстве", г. Камышин, 2002 г.; Международной научно-технической конференции, "Информационные технологии в образовании, технике и медицине", г. Волгоград, 2002 г.; 4-й Всероссийской научной internet-конференции "Компьютерные технологии и моделирование в естественных науках и гуманитарной, сфере", г. Тамбов, 2002 г.; 3-й Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки", г. Самара, 2002 г.; Международной научно-технической конференции "Системные проблемы качества, математического моделирования, информационных и электронных технологий", г. Москва, 2003 г.; Всероссийской научно-технической internet-конференции для студентов, и аспирантов "Информатика в измерительных и управляющих системах", г. Волжский, 2004 г.; 5-й Международной научно-практической конференции "Методы и алгоритмы прикладной математики в технике, медицине и экономике", г. Новочеркасск, 2004 г.; Международной научно-технической конференции. "Современные информационные технологии - 2004", г. Пенза, 2004 г.; 5-й Международной научно-практической конференции "Моделирование. Теория, методы и средства", г. Новочеркасск, 2005 г.; 11-Й Международной научно-технической конференции "Радиоэлектроника, электротехника и энергетика", г. Москва, 2005 г.; 10-й Международной открытой научной конференции "Современные проблемы информатизации в непромышленной сфере и экономике", г. Воронеж, 2005 г.; 6-й Международной конференции "Компьютерное моделирование 2005", г. Санкт-Петербург, 2005 г.
Структура и объем диссертации
Диссертация состоит из .введения, трех глав, заключения, списка литературы и приложения, включающего документы о внедрении результатов работы. Основные результаты работы сформулированы в виде выводов. Диссертационная работа содержит ПО страниц, 72 рисунка. Список использованной литературы включает в себя 170 наименований.
Первая глава содержит краткое описание аппарата вейвлет-преобразований сигналов в пространствах R1 и R2. Рассматриваются вопросы, связанные с вычислением вейвлет-преобразования и адаптацией вейвлет-базиса к конкретным сигналам. Проводится краткий обзор-основных подходов к реализации эффективной компрессии сигналов на основе дискретного вейвлет-преобразования. Получены выражения для порождающих масштабирующих функций и вейвлет-функций в пространстве RJ и порожденных ими пространств, которые применяются при решении задач, рассматриваемых в последующих главах.
Во второй главе проводится обоснование выбора модели аппроксимации поверхности в пользу триангуляционных моделей. Рассматриваются существующие методы компрессии триангуляционных моделей. Предложен новый подход к применению кратномасштабного анализа к триангуляционным моделям и возможность создания многомасштабной, модели посредством декомпозиции и реконструкции. Приводится система анализа-синтеза на основе вейвлета В-сплайна 1-го порядка.
В третьей главе предложена и исследована новая схема разбиения и новая схема слияния граней триангуляционной модели, вопросы компрессии информации о связности модели и информации о геометрии модели. Представлен альтернативный методу Лонсбери метод компрессии на основе нерегулярного кратномасштабного анализа,.. Приводятся результаты компрессии конкретных триангуляционных моделей.
В заключении формулируются основные результаты диссертационной работы.
