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

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

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

Земцов Андрей Николаевич

РАЗРАБОТКА СПЕКТРАЛЬНЫХ МЕТОДОВ КОМПРЕССИИ ТРИАНГУЛЯЦИОННЫХ МОДЕЛЕЙ НА ОСНОВЕ ДИСКРЕТНОГО ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЯ

Специальность 05 13 01 - Системный анализ, управление и обработка информации

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

Волгоград - 2005

Работа выполнена на кафедре "ЭВМ и системы" в Волгоградском государственном техническом университете

Научный руководитель: доктор технических наук

профессор Лукьянов Виктор Сергеевич

Официальные оппоненты: доктор технических наук

профессор Шилин Александр Николаевич

Защита диссертации состоится 20 сентября 2005 г. в 1400 часов на заседании диссертационного совета Д212.028.04 в Волгоградском государственном техническом университете по адресу: 400131, г. Волгоград, пр. Ленина, д. 28, зал заседаний ученого совета (ауд. 209).

С диссертацией можно ознакомиться в библиотеке Волгоградского государственного технического университета.

Автореферат разослан "£&' C>¿ 2005 г.

доктор технических наук

профессор Ярных Валерий Васильевич

Ведущая организация: ФГУП Инженерный центр "Азот1

jt

Ученый секретарь диссертационного совета

Водопьянов В.И.

поь

ААОвЫЪ

3

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

Цель и задачи исследования. Цель диссертационного исследования за-

ключается в разработке методов многомасштабног я-

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

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

■ Анализ существующих методов геометрической оптимизации триангуляционных моделей.

• Разрабо1ка многомасгатабной модели представления объектов реального мира посредством триангуляций.

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

■ Разработка эффективных методов компрессии триангуляционных моделей посредством нерегулярного кратномасштабного анализа.

■ Разработка схемы нерегулярного разбиения и слияния граней триангуляционной модели.

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

■ Разработка программы экспериментального моделирования компрессии цифровых сигналов в пространстве Я1 на основе вейвлет-преобразования с возможностью реализации и хранения собственных фильтров во внутренней базе данных фильтров программы.

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

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

Научная новизна. Основные результаты диссертационного исследования, имеющие научную новизну, заключаются в следующем:

■ Предложен новый метод нерегулярного кратномасштабного анализа триангуляционных моделей на основе вейвлет-преобразования с тру-

доемкостью о(п) в среднем.

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

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

• Предложены кластерные методы компрессии триангуляционных моделей на основе иерархической древовидной структуры.

• Предложена многомасштабная модель представления объектов реального мира посредством триангуляции.

Практическая ценность. Практическая ценность диссертационного исследования состоит в следуюхцем:

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

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

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

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

■ Разработана система анализа-синтеза на основе вейвлета В-сплайна 1-го порядка.

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

« Разработана и реализована программа экспериментального моделирования компрессии цифровых сигналов в пространстве Я' на основе вейвлет-преобразования с набором из 89 вейвлет-функций с возможностью реализации и хранения собственных фильтров во внутренней базе данных фильтров программы.

Реализация результатов работы. Разработанный метод компрессии триангуляционных моделей внедрен в виде алгоритма в прикладной геоинформационной системе в ООО "Термостройкомплект".

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

Апробация работы и публикации. Основные результаты диссертационной работы докладывались и обсуждались на Всероссийской конференции "Прогрессивные технологии в обучении и производстве", г. Камышин, 2002 г; Международной научно-технической конференции "Информационные технологии в образовании, технике и медицине", г. Волгоград, 2002 г; 4-й Всероссийской научной ¡гНетс^ конференции "Компьютерные технологии и моделирование в естественных науках и гуманитарной сфере", г. Тамбов, 2002 г; 3-й Международной конференции молодых ученых и студентов "Актуальные проблемы современной науки", г. Самара, 2002 г; Международной научно-технической конференции "Системные проблемы качества, математического моделирования, информационных и электронных технологий", г. Москва, 2003 г; Всероссийской научно-технической н^егпеЬконференции для студентов и аспирантов "Информатика в измерительных и управляющих системах", г. Волжский, 2004 г; 5-й Международной научно-практической конференции "Методы и алгоритмы прикладной математики в технике, медицине и экономике", г. Новочеркасск, 2004 г; Международной научно-технической конференции "Современные информационные технологии - 2004", г. Пенза, 2004 г; 5-й Международной научно-практической конференции "Моделирование. Теория, методы и средства", г. Новочеркасск, 2005 г; 11-й Международной научно-технической конференции "Радиоэлектроника, электротехника и энергетика", г. Москва, 2005 г; 10-й Международной открытой научной конференции

"Современные проблемы информатизации в непромышленной сфере и экономике", Воронеж, 2005 г.

По результатам выполненных исследований опубликовано 20 печатных работ.

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

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

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

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

Основная идея вейвлет-анализа заключается в разложении сигнала Г по базису функций :

Г = ЕС,Ч',, (I)

I

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

Для эффективного представления сигнала Г посредством только малого количества коэффициентов с, необходимо потребовать соответствия функции

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

Пример компрессии сигнала в пространстве К2 показан на рисунке 1. Изображение получено с помощью программы экспериментального моделирования компрессии цифровых сигналов в пространстве И2 на основе вейвлет-преобразования с набором из 16 вейвлет-функций для разработки вейвлет-кодера на ПЛИС (Попов Н.В., Земцов А.Н., 2000 г., результаты представлены в [6]). Видно, что аппроксимация исходного изображения на основе преобразования Добеши <1Ь4 имеет более высокие визуальные характеристики, чем аппроксимация исходного изображения на основе преобразования Хаара, что объясняется отсутствием гладкости базисных вейвлет-функций Хаара.

Исходное изображение Аппроксимация исходного Аппроксимация исходного

изображения изображения

(преобразование Хаара) (преобразование Добеши гШ4)

Рисунок 1. Пример компрессии двумерного изображения (сиIнала в пространстве Я2). Степень компрессии (коэффициент сжатия) составил 17:1.

Под кратномасштабным анализом понимают последовательность {У (} 2 |

замкнутых подпространств I.2(Я), удовлетворяющую следующим свойствам:

с • (2)

(3)

П^={0}; (4)

(5)

Ф)бУ0»Г(х-к)£У,. (6)

Существует функция <р <= У0 такая, что {<р(х - к)}иг образует базис Рисса в

Кратномасштабный анализ описывает последовательность вложенных аппроксимационных пространств V, в I-2 (я).

В силу (5) все подпространства V, однозначно определяются из пространства У0 при помощи соответствующего изменения масштаба одной функции ср. Функция ф называется масштабирующей функцией, если она порождает кратномасштабный анализ. Указанные пространства связаны таким соотношением, что функция Г пространства V при масштабировании на 2 становится

элементом пространства У,+1.

Пусть ф к (х) = 2,/2ф(2-1 х-к}], к е 7. Тогда, как следствие из (5) и (6), последовательность }ке2является базисом Рисса в VJ для любого

Существует последовательность {Ьк}Ьб7 такая, что:

<р(х)=-л/2£ьк<р(2х-к). (7)

Выражение (7) называется масштабным соотношением для масштабирующих функций.

Пространство WJ определяется как ортогональное дополнение к^в V,,,, т.е. и WJ 1 У:, ] е 7.. В силу (3) и (4) имеет место следствие:

Ь2(Я)= ...Ф |е№1Ф*|®... = ®)17¥). (8)

Графическое представление кратномасштабного анализа с разложением пространства У^, на пространство VJ и ортогональное дополнение WJ показано на рисунке 2.

V -► V -► V -► V

VJ VI ^ VJ г

WJ V

J 2

Рисунок 2 Графическое представление кратномасштабного анализа.

Существует такая функция ц)>м(х)=2'пц(2'х-к\),ке7,, называемая вейвлет-функцией, что последовательность Ь'^к }кбХ > как следствие из (7), является базисом Рисса в WJ для любого \ причем существует последовательность = (— 1)к Ь)ке2 такая, что:

цд(х)=ЛХ8кф(2х-к), (9)

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

Следовательно, система масштабирующих функций и вейвлет-функций может быть определена множеством коэффициентов и {Ьк}ке7.

Таким образом, любую функцию Ге I2(я) можно представить на некотором заданном уровне разрешения .¡„ в виде:

Г60 = X'ск Ф* ,к 00+1I'VV,к (х) • (10)

к а. к

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

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

Сформулируем задачу кратномасштабного анализа триангуляционной модели следующим образом. Пусть имеется некоторая триангуляционная модель М" с высоким разрешением, тогда необходимо получить описание Мл в виде многослойной структуры, содержащую п последовательных приближений М° к М" (см. рисунок 3).

Мл Б" 1 М-' О"'2 М"-2 Л""3 Б0 М°

Рисунок 3 Декомпозиция исходной триангуляционной модели М"

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

Кроме того, необходимо иметь возможность получать исходную триангуляционную модель М" по имеющемуся множеству базовых аппроксимаций М\]е {0,1,...,п-1} и множеству детализирующих составляющих Б^е {ОД,..., п-1} (см. рисунок 4).

Рисунок 4. Реконструкция исходной триангуляционной модели

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

В работе Лонсбери триангуляционные модели представляются с помощью сплайн-вейвлетов, разработанных Чуй, которые строятся на основе В-сплайнов, а именно - В-сплайна 1-го порядка в качестве масштабирующей функции Ф'(х), заданной в пространстве, определяемом топологией триангуляционной модели (см. рисунок 5). Для триангуляционной модели М', со-

сюящей из у= (у ^ = 0^-1 вершин, представляется множеством векторного пространства V' посредством J масштабирующих функций.

Рисунок 5 Масштабирующая функция Лонсбери Ф'(х) (В-сплайн 1-го порядка).

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

Использование в качестве масштабирующей функции В-сплайна 1-го порядка позволило получить математическое описание 8' векторного пространства V' посредством 3 масштабирующих функций, триангуляционной модели М1, состоящей из V = {у,}, j = 0, J—1 вершин, исключая информацию о связности вершин:

8'(х)=Ф'(х)С', (П)

Ф;М = [фо(4- ,Ф,(х)], (12)

С' =

хо У о

Х1 У.

Х.1-2 У .1-2

Х^> У] I

(13)

В силу того, что V, = у,., ® АУ,. , представляется возможным определить масштабирующую функцию Фн(х), записанную в терминах базисных функций пространства V,. Таким образом, существует матрица Р\ или фильтр в терминах субполосного кодирования, размерностью 1x1-1 такая, что:

Фн(х)=Ф'(х)Р'. (14)

Запишем аналогичные соотношения для вейвлет-функции:

Ч"(х) = [ч;в(х>...,ч/^.у1(х)], (15)

Ч"-'(х)=Ф,(х)(3\ (16)

где QJ - матрица, имеющая размерность у' -у]').

Декомпозируя 8', определенную в терминах базисных функций пространства V , запишем ее в терминах базисных функций пространств V, , и АУН с учетом (15):

8'(х) = Ф'~'(х)Сн + Ч"~'(х)0'~|, (17)

где С'' и О'' - вейвлет-коэффициенты декомпозируемой триангуляционной модели М'. Перепишем (17) с учетом (14) и (16):

8'(х) = Ф'(х)Р'С'1 +Ф'(х)0)Он. (18)

В работе Лонсбери используется разбиение триангуляционной модели по схеме 1 —> 4, т.е. каждая грань модели разбивается на четыре грани посредством введения новой вершины в середине каждого ребра как показано на рисунке 6.

Рисунок 6. Разбиение по схеме 1 -» 4.

Разбиение согласно схеме, представленной на рисунке 6, позволяет определить семейство вейвлет-функций для пространства V'"1 такого же вида, как и вейвлет-функции для пространства У\ т.е. В-сплайна 1-го порядка, с областью определения в 4 раза меньше, чем у масштабирующей функции. С учетом (18) получили:

С'=Р'Сн+д'0'-'. (19)

В связи с тем, что пространство \УН определяется как ортогональное дополнение к V1'1 в V', имеем:

Ф'(х) = Фн(х)А'+Ч"-'(х)В'. (20)

Тогда соотношение (11) с учетом (20) запишется следующим образом:

Я'(х) = Ф' '(х)А,С '(х)В'С>. (21)

Из (21) и (17) следует, что:

Сн =А'С',

(22)

Он =В'С'

Следовательно:

А'

И О']"', (23)

В'

где А' и В' - фильтры декомпозиции триангуляционной модели, Р> и С' -фильтры реконструкции триангуляционной модели, т.е.

А' V1

В' • V' V1

• ' (24)

Р' .V'"1 -»V',

Таким образом, для разбиения по схеме 1-»4 матрицы А', В1, Г" и О1 задаются в явном виде.

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

Ми од Лонсбери Разработанный метод

Рисунок 7. Схема кратномасшгабного анализа данных в пространстве Я3 (классический и альтернативный подходы)

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

Пример работы алгоритма показан на рисунке 8. Необходимо отметить, что выбор первой грани в алгоритме является произвольным, т.е. для простоты берется первая грань в списке. Для представленного примера информация о 12 добавляемых гранях кодируется в среднем 2.17 битами на грань.

сверху - участок исходной триангуляционной модели (22 грани), •%

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

Рисунок 8. Пример декомпозиции и реконарукции триангуляционной модели

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

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

Продемонстрируем на конкретных примерах (см. рисунки 10 и 1 ]) ре-зулыаты применения разработанного метода компрессии триангуляционных моделей.

Фрагмент исходной триангулядаоивей модели Аппроксимация исходной триангуляционной мо-

рельефа земной поверхносш дели рельефа земной поверхности (преобразование

Хаара, степень компрессии 146' I, среднеквадратичное отклонение 10 5/28% от исходной)

Аппроксимация исходной триангуляционной модели рельефа земной поверхности (преобразование Хаара, степень компрессии 342'1, среднеквадратичное отклонение 7 9/44% от исходной)

Аппроксимация исходной триангуляционной модели рельефа земной поверхности (преобразование Ангонини, степень компрессии 146 1, среднеквадратичное отклонение 7 1/42% от исходной)

Аппроксимация исходной триангуляционной модели рельефа земной поверхности (преобразование Брислауна, степень компрессии 146-1, среднеквадратичное отклонение 8 2/3% от исходной)

Аппроксимация исходной триангуляционной модели рельефа земной поверхности (преобразование Одегарда, степень компрессии 16:1, среднеквадратичное отклонение 3.5/16% от исходной)

Рисунок 9. Примеры компрессии триангуляционных моделей посредством разработанного кластерного метода.

Исходная триангуляционная модель Аппроксимация модели Аппроксимация модели

поверхности земного рельефа (11856 вершин и 23330 граней) (2054 вершины и 3958 граней) (45602 вершины и 90000 граней)

Исходная триангуляционная модель Аппроксимация модели Аппроксимация модели

(2562 вершины и 5120 граней) (1178 вершин и 2352 грани) (486 вершин и 968 граней)

Рисунок 10 Примеры компрессии триангуляционных моделей посредством разработанного метода на основе нерегулярного кратномасштабного анализа.

карниадр ЭллайаиДасбраи карии и Готсмак Лаисвари

Раз рвботаниый метод

ООО 500 13 00 15 00 20 0(

Инфврмациоиныа затраты кодирования (вит на варШину)

-•-Карнаадр -о- Эллаиа и Дасбраи ■» Карай а Готсыан

Лонсбери »- Тоума

Пайярсла и Россинья« раараеотанный матод

)00 500 1000 1500 2000 2200 ЗООО Ииформацнениыа затраты годароааиаа (Вит на варятиу)

Рисунок 11. Зависимости среднеквадратичного отклонения от информационных затрат при компрессии триангуляционной модели статуи Венеры (а) и при компрессии триангуляционной модели головы Венеры (б).

В заключении формулируются основные результаты диссертационной работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

В результате проведенных теоретических и экспериментальных исследований в диссертационной работе получены следующие результаты:

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

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

Разработаны схемы нерегулярного разбиения и слияния граней триангуляционной модели.

Разработана система анализа-синтеза на основе вейвлета В-сплайна 1-го порядка.

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

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

Разработана и реализована программа экспериментального моделирования компрессии цифровых сигналов в пространствах Я' и Я2 на основе вейв-лет-преобразования с набором из 89 вейвлет-функций с возможностью реализации и хранения собственных фильтров во внутренней базе данных фильтров программы.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Земцов А.Н. Графический процессор обработки данных в трехмерном пространстве с программируемой структурой. // Концептуальное проектирование в образовании, технике и технологии: Межвуз. сб. науч. тр. ВолгГТУ. -2002.-С. 99-104.

2. Земцов А.Н., Кривоносов Д.М. Имитационная модель проектирования топологических структур сетей // Прогрессивные технологии в обучении и производстве: Материалы Всероссийской конференции КТИ (фил. ВолгГТУ). -2002.- С. 133.

3. Земцов А.Н., Лебедев М.В. Имитационная модель сети передачи данных, Прогрессивные технологии в обучении и производстве: Материалы Всероссийской конференции КТИ (фил. ВолгГТУ). - 2002. - С. 134.

4. Земцов А.Н. Имитационная модель проектирования топологических структур сетей // Компьютерные технологии и моделирование в естественных науках и гуманитарной сфере: Материалы IV Всероссийской научной ¡п1егпе1-конференции. - 2002. - Т.22. - С. 87.

5. Андреев А.Е., Андреева М.И., Земцов А.Н. Аппаратурная реализация алгоритмов многомерных ДЛП на ПЛИС // Информационные технологии в об-

разовании, т ехнике и медицине: Сб. науч. тр. ВолгГТУ. - 2002. - Т. 1. - С. 4548.

6. Попов Н.В., Земцов А.Н. Реализация вейвлет-преобразования на ПЛИС // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. ВолгГТУ. - 2002. - Т.1. - С. 211-213.

7. Земцов А.Н., Андреев А.Е., Попов Н.В. Аппаратурно-ориентированные структуры компрессии графической информации // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. ВолгГТУ. - 2002. - Т.1. -С. 113-115.

8. Земцов А.Н. Имитационная модель сети передачи данных // Актуальные проблемы современной науки: Труды 3-й Международной конференции молодых учёных и студентов СамГТУ. - 2002. - Ч.12-16. - С. 24-25.

9. Земцов А.Н. Реализация вейвлет-преобразования на ПЛИС // Актуальные проблемы современной науки: Труды 3-й Международной конференции молодых учёных и студентов СамГТУ. - 2002. - Ч. 12-16. - С. 26-27.

10. Земцов А.Н. Концептуальные модели компрессии трехмерных изображений // Системные проблемы качества, математического моделирования, информационных и электронных технологий: Сб. тр. Международной конференции и Российской научной школы. - М.: Радио и связь, 2003. - Ч.З, Т.1. - С. 37-38.

11. Земцов А.Н. Автоматизированная система анализа результатов динамической аппроксимации триангуляционных моделей рельефа поверхности // Методы и алгоритмы прикладной математики в технике, медицине и экономике' Сб. тр. V Международной научно-практической конференции ЮРГТУ. -2004.-Т.З-С.31-34.

12. Земцов А.Н. Программная система экспериментального моделирования компрессии трехмерных изображений // Современные информационные технологии: Сб. тр. Международной научно-технической конференции ПГТА. -2004. - С. 26-28.

13. Земцов А.Н. Прогрессивная передача триангуляционных моделей по каналам данных с помехами // Современные информационные технологии: Сб. тр. Международной научно-технической конференции ПГТА. - 2004. - С. 3133.

14. Земцов А.Н. Компрессия триангуляционных моделей с адаптивным уточнением // Современные проблемы информатизации в непромышленной сфере и экономике: Сб. трудов ВорГТУ. - 2005. - №.10 - С. 106-107.

15. Земцов А.Н. Фрактально-вейвлетный метод компрессии триангуляционных моделей // Современные проблемы информатизации в непромышленной сфере и экономике: Сб. трудов. ВорГТУ. -2005. - №10. - С.104-106.

16. Земцов А.Н. Особенности аппроксимации триангуляционных моделей с помощью вейвлет-преобразования // Современные проблемы информатизации в непромышленной сфере и экономике: Сб. трудов. ВорГТУ. - 2005. -№10.-С. 103-104.

17. Земцов А.Н. Прогрессивная передача триангуляционных моделей в сети Internet // 11-я Международная научно-техническая конференция студентов и аспирантов: Сб. тр. МЭИ. -2005. - Т.1. - С. 370-371.

18. Земцов А.Н. Применение смешанного кодирования для компрессии триангуляционных моделей // 11-я Международная научно-техническая конференция студентов и аспирантов: Сб. тр. МЭИ. - 2005. - Т.1. - С. 335-336.

19. Земцов А.Н. Особенности применения вейвлет-преобразования для компрессии триангуляционных моделей // 11-я Международная научно-техническая конференция студентов и аспирантов. Сб. гр. МЭИ. - 2005. - Т.1. -С. 304-305.

20. Земцов А.Н. Математическая модель локальной обработки широкополосных сигналов // Моделирование. Теория, методы и средства: Сб. тр. Международной научно-практической конференции ЮРГТУ. - 2005. - Т.1 - С. 41-

21. Земцов ATI. Оптимизированный метод передачи триангуляционных моделей в сети Internet на основе вейвлет-преобразования // Компьютерное моделирование 2005: Сб. тр. 6-й Международной конференции СПбГПУ. - Санкт-Петербург, 2005.

22. Земцов А.Н. Спектральный метод компрессии триангуляционных моделей с гарантированной точностью // Компьютерное моделирование 2005: Сб. тр. 6-й Международной конференции СПбГПУ. - Санкт-Петербург, 2005.

23. Земцов А.Н. О выборе оптимального вейвлет-базиса в задаче компрессии триангуляционных моделей рельефа поверхности // Концептуальное проектирование в образовании, технике и технологии: Межвуз. сб. науч. тр. ВолгГ-ТУ. - Волгоград, 2005.

24. Земцов А.Н. Прогрессивная передача аудиосигналов в компьютерных сетях // Концептуальное проектирование в образовании, технике и технологии: Межвуз. сб. науч. тр. ВолгГТУ. - Волгоград, 2005.

45.

Находятся в печати:

Подписано в печать 28.06. 2005 г. Заказ № 456 . Тираж 100 экз. Печ. л. 1,0. Формат 60 х 84 1/16. Бумага офсетная. Печать офсетная.

Типография «Политехник» Волгоградского государственного технического университета.

400131, Волгоград, ул. Советская,35

J

\

ll'

Y

»13078

РНБ Русский фонд

2006-4 9706

Введение.

1 Анализ методов представления и компрессии сигналов.

1.1 Вейвлет-анализ как альтернатива анализу Фурье.

1.2 Кратномасштабный анализ.

1.3 Вейвлет-функции.

1.4 Быстрое вейвлет-преобразование.

1.4.1 Структура вейвлет-разложения сигнала.

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

1.4.3 Нормализация вейвлет-базисов.

1.4.4 Вейвлет-пакеты.

1.5 Вейвлеты Хаара, вейвлеты Добеши и Койфлеты.

1.6 Выбор базисной вейвлет-функции.

1.7 Компрессия сигналов на основе вейвлет-преобразований.

1.8 Сравнительный анализ статистических методов компрессии.

1.9 Сравнительный анализ методов компрессии на основе ортогональных разложений.

1.10 Сравнительный анализ вейвлет-преобразований.

1.11 Многомерные преобразования.

Выводы по главе 1.

2 Адаптивное представление объектов полигональными

S триангуляционными моделями.

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

2.2 Триангуляция Делоне.

2.3 Определение триангуляционной модели поверхности.

2.4 Анализ известных методов компрессии триангуляционных моделей.

2.4.1 Методы геометрической оптимизации.

2.4.2 Адаптивные методы компрессии триангуляционных моделей.

2.4.3 Сравнение методов.

2.5 Триангуляционные модели сигналов в R2.

2.6 Разработка кратномасштабной триангуляционной модели поверхности.

2.6.1 Декомпозиция триангуляционной модели.

2.6.2 Реконструкция триангуляционной модели.

2.7 Методы перестройки триангуляционной модели.

Выводы по главе 2.

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

3.1 Кластерные методы компрессии триангуляционных моделей.

3.2 Альтернативная схема кратномасштабного анализа в пространстве R3.

3.3 Разбиение триангуляционной модели по нерегулярной схеме.

3.4 Слияние граней триангуляционной модели.

3.5 Компрессия информации о связности триангуляционной модели.

3.6 Компрессия информации о геометрии триангуляционной модели.

3.7 Особенности программной реализации методов компрессии.

3.7.1 Постановка задачи.

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

3.7.3 Структуры представления данных.

3.7.4 Обобщенный алгоритм компрессии триангуляционных моделей.

3.8 Результаты компрессии триангуляционных моделей.

Выводы по главе 3.

В последние годы наблюдается интенсивное развитие средств информатизации и телекоммуникаций, в том числе и сети 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.

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

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

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

Цель работы

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

Задачи исследования

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

Анализ существующих методов геометрической оптимизации триангуляционных моделей.

Разработка многомасштабной модели представления объектов реального мира посредством триангуляций.

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

- Разработка новой схемы нерегулярного разбиения-слияния граней триангуляционной модели.

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

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

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

Методы исследования

При выполнении диссертационной работы использовались методы теории спектрального анализа, аппарат матричной алгебры, методы вычислительной геометрии, машинной графики, методы теории вейвлетов и кратно-масштабного анализа.

Научная новизна

Предложена новая схема представления триангуляционных моделей в виде многослойной структуры.

Предложена новая схема разбиения-слияния граней модели.

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

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

Получены выражения для порождающих масштабирующих функций и вейвлет-функций в пространстве 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 г.

Структура и объем диссертации

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

Выводы по главе 3

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

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

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

4. Предлагается информацию о связности модели и информацию о координатах вершин сохранять в два независимых потока. Сравнительный анализ показал, что разделение на два независимых потока позволяет повысить степень компрессии универсальными статистическими алгоритмами на 15-25% дополнительно.

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

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

Заключение

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

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

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

В результате проведенных теоретических и экспериментальных исследований в диссертационной работе получены следующие результаты:

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

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

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

4. Предложена схема многомасштабного представления триангуляционных моделей.

5. Разработана схема нерегулярного разбиения-слияния граней триангуляционной модели.

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

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

8. Результаты диссертационной работы внедрены в прикладной геоинформационной системе в ООО "Термостройкомплект".

1. Г. Haar A. Zur Theorie der orthogonalen Funktionensysteme // Math. Ann. 69. 1910.-pp. 331-371.

2. Grossmann A., Morlet J. Decomposition of Hardy functions into square integrable wavelets of constant shape // SIAM J. Math. Anal. 15. 1984. - pp.723736.

3. Чуи-Ч. Введение в Вейвлеты: Пер. с англ. М.: Мир, 2001. - 412 с.

4. Calderon А.Р. Intermediate spaces and interpolation, the complex method // Studia Math. 24. 1964. - pp. 113-190.

5. Mallat S. Multiresolution representation and wavelets: PhD thesis / Univ. of Pennsylvania. Philadelphia, 1988.

6. Mallat S. A theory of multiresolution signal decomposition: the wavelet representation // IEEE Trans. Pattern Anal. Machine Intell. 11.- 1989. pp. 674693.

7. Mallat S. Multiresolution approximations and wavelets orthonormal bases of L2 (r) // Trans. Amer. Math. Soc. 315.- 1989. p. 69-87.

8. Meyer Y. Ondelettes et functions splines: Seminaire EDP / Ecole Poly-technique. Paris. - 1986.

9. Meyer Y. Principe d' incertitude, bases Hilbertiennes et algebras d'operateurs // Seminaire Bourbaki 662. 1985.

10. Cohen A., Daubechies I., Feauveau J. Biorthogonal bases of compactly supported wavelets // Comm. Pure and Appl. Math. 1991.

11. Stromberg J.O. A modified Franklin system and higher order spline systems on Rn as unconditional bases for Hardy spaces // Proc. Conf. in Honor of Antoni Zygmund. 1981. - Vol.2. - pp. 475-493.

12. Quale E., Weyrich N. Decomposition and reconstruction algorithms for spline wavelets on a bounded interval // BIT Numerical Maths. 1994. - Vol:l. -pp. 217-231.

13. Quak E., Weyrich N. Algorithms for spline wavelet packets on an interval // BIT Numerical Maths. 1997. - Vol.37, No.l. - pp. 76-95.

14. Lemarie P.G. Ondelettes a localization exponentielles // J. Math. Pure et Appl. 67. 1988.-pp. 227-236.

15. Battle G. A block spin construction of ondelettes // Comm. Math. Phys. 110.- 1987.-pp. 601-615.

16. Daubechies I. Orthonormal bases of compactly supported wavelets // Comm. Pure and Math. 41. 1988. - pp. 909-996.

17. Coifman R., Meyer Y., Quake S., Wickerhauser M. Signal processing and compression with wave packets // Proc. of Conference on Wavelets. 1989. — pp. 77-93.

18. Gabor D. Theory of communication / J. IEE 93. 1946. - pp. 429-457.

19. Дьяконов В.П. От теории к практике. М.: СОЛОН-Р, 2002. - 448с.

20. Добеши И. Десять лекций по вейвлетам. Ижевск: НИЦ "Регулярная и хаотическая динамика", 2001. -464 с.

21. Дремин И.М., О.В. Иванов, Нечитайло В.А. Вейвлеты и их использование // Успехи физических наук. 2001. - Т. 171, №5. - С. 465-501.

22. Астафьева Н.М. Вейвлет-анализ: основы теории и примеры применения // Успехи физических наук. 1996. - Т. 166, №11. - С. 1145-1170.

23. Переберин А.В. О систематизации вейвлет-преобразований // Вычислительные методы и программирование. 2001. - Т.2. - С. 15-40.

24. Васильева Л.Г., Жилейкин Я.М., Осипик Ю.И. Преобразования Фурье и вейвлет-преобразования. Их свойства и применение // Вычислительные методы и программирование. 2002. - Т.З. - С. 172-175.

25. Петухов А.П. Введение в теорию базисов всплесков. СПб.: Изд-во СПбГТУ, 1999.-132 с.

26. Новиков JI.B. Основы вейвлет-анализа сигналов. СПб.: МОДУС+, 1999. - 152 с.

27. Новиков Л.В. Адаптивный вейвлет-анализ сигналов // Научное приборостроение. 1998. - Т.9, №2. - С. 35-48.

28. Новиков И.Я. Основы теории всплесков // Успехи математических наук. 1998. - Т.53, № 6. - С. 9-13.

29. Малоземов В. Н., Машарский С. М. Основы дискретного гармонического анализа. СПб.: НИИММ, 2003. - 288 с.

30. Умняшкин С.В. Компрессия цифровых изображений на основе кодирования древовидных структур вейвлет-коэффициентов с прогнозированием статистических моделей // Изв. вузов. Электроника. 2001. - №5. - 9 с.

31. Ivanov P., Goldberg A., Halvin S., Peng С., Rosenblum М., Stanly Н. Wavelets in Medicine and Psychology // Wavelets in Physics. 1999. — p. 391419.

32. Галягин Д. К., Печерскии Д. M., Решетняк М. Ю., Соколов Д. Д., Фрик n.r.mailto:frick@icmm.ru Вейвлет-анализ характеристик геомагнитного поля в неогее // Изв. РАН. Сер. Физика Земли. 2000. - Т.36, №4. - С. 82-89.

33. Фрик П.Г. Вейвлет-анализ и иерархические модели турбулентности. Пермь, 1992. - 40 с. - (Препринт / ИМСС УрО РАН).

34. Anant К., Dowla F. Vector Quantization of ECG Wavelet Coefficients // Signal Processing Letters. 1995. - pp. 1-4.

35. Wu X., Yun D.Y., Pearlman W.A. Progressive Coding of Medical Volumetric Data Using Three-dimensional Integer Wavelet Packet Transform // Workshop on Multimedia Signal Processing. 1998. - pp. 553-558.

36. Lu Z., Kim D.Y., Pearlman W.A. Wavelet Compression of ECG Signals by the Set Partitioning in Hierarchical Trees (SPIHT) Algorithm // IEEE Trans, on Biomedical Engineering. 2000. - Vol.47. - pp. 849-856.

37. Healy D., Lu J., Weaver J., Two Applications of Wavelets and Related Techniques in Medical Imaging // Ann. of Biomedical Engineering. 1995. -Vol.23, No.5.-pp. 637-665.

38. Weaver J., Healy D., Xu Y., Driscoll J. Wavelet Encoding in MR Imaging // Magnetic Resonance in Medicine. 1992. - Vol.24, No.2. - pp. 275-287.

39. Lemire D. Wavelet Time Entropy, T Wave Morphology and Myocardial Ischemia // IEEE Trans, on Biomedical Engineering. 2000. - Vol.47. - p. 11.

40. Shen К., Delp E.J. Wavelet Based Rate Scalable Video Compression // IEEE Trans, on Circuits and Systems for Video Tech. 1999. - Vol.9, No.l. - pp. 109-122.

41. Martucci S.A., Sodagar I., Chiang Т., Zhang Y.Q. A Zerotree Wavelet Video Coder // IEEE Trans, on Circuits and Systems for Video Tech. 1997. -Vol;7, No.l. - pp. 109-118.

42. Kim S., Rhee S., Jeon J.G., Park К.Т. Interframe Coding Using Two-Stage Variable Block-Size Multiresolution Motion Estimation and Wavelet Decomposition // IEEE Trans, on Circuits and Systems for Video Tech. 1998. -Vol.8, No.4. - pp. 399-410.

43. Luo J., Chen C.W., Parker K.J., Huang T.S. A Scene Adaptive and Signal Adaptive Quantization for Subband Image and Video Compression Using Wavelets // IEEE Trans, on Circuits and Systems for Video Tech. 1997. - Vol.7, No.2. -pp. 343-357.

44. Kim B.J., Xiong Z., Pearlman W.A., Kim Y.S. Progressive Video Coding for Noisy Channels // Visual Communication and Image Representation. -1999.- Vol.10.-pp. 173-185.

45. Daubechies I., Sweldens W. Factoring Wavelet Transforms into Lifting Steps // IEEE Trans, on Image Proc. 2000. - Vol.9, No.3. - pp. 480-496.

46. Sweldens W. The Lifting Scheme: A custom-design construction of biorthogonal wavelets // Appl. Сотр. Harmon. Anal. 1996. - Vol.3, No.2. - pp. 186-200.

47. Sweldens W. The Lifting Scheme: A Construction of Second Generation Wavelets // S1AM J. Math. Anal. 1996. - Vol.29, No.2. - pp. 511-546.

48. Tieng Q.M., Boles W.W. Recognition of 2D Object Contours Using the Wavelet Transform Zero-Crossing Representation // IEEE Trans, on Pattern Analysis and Machine Intelligence. 1997. - Vol. 19, No. 8. - pp. 910-916.

49. Jacobs C.E., Finkelstein A., Salesin D. Fast Multiresolution Image Querying // SIGGRAPH'92 Proceedings. 1992. - pp. 177-184.

50. BermanD., Bartell J., Salesin D. Multiresolution painting and compositing 11 SIGGRAPH'94 Proceedings. 1994. - pp. 85-90.

51. Gross M.H., Staadt O.G., Gatti R. Efficient Triangular Surface Approximation Using Wavelets and Quadtree Data Structures // IEEE Trans, on Visualization and Computer Graphics. 1995. - Vol.1, No.l. - pp. 44-59.

52. Stollnitz E.J., DeRose T.D., Salesin D.H. Wavelets for Computer Graphics. Theory and applications. San Francisco: Morgan Kaufmann, 1996. - p. 245.

53. Finkelstein A., Salesin D.H. Multiresolution Curves // SIGGRAPH'94 Proceedings. 1994. - pp. 261-ё268.

54. Bonneau G.P. Multiresolution Analysis of Irregular Surface Meshes // IEEE Trans, on Visualization and Computer Graphics. 1998. - Vol.4, No.4. - pp. 365-378.

55. Eck M., DeRose T.D., Duchamp Т., Hoppe H., Lounsbery M., Stuetzle W. Multiresolution Analysis of Arbitrary Meshes // SIGGRAPH'95 Proceedings. -1995.-pp. 173-182.

56. Ihm I., Park S. Wavelet-Based 3D Compression Scheme for Interactive Visualization of Very Large Volume Data// Computer Graphics Forum 1999.-Vol.18, No.l. - pp. 3-15.

57. DeVore R., Jawerth W., Lucier B. Image Compression Trough Wavelet Transform Coding // IEEE Trans, on Inf. Theory. 1992. - Vol.39, No.2. - pp. 719-746.

58. Дьяконов В.П., Абраменкова И. В. MATLAB. Обработка сигналов и изображений. Специальный справочник. СПб: Питер, 2002. - 608 с.

59. Кирушев В. А. Быстрый алгоритм сжатия изображений//Вестник молодых ученых. Прикл. матем. и механика. 1997. - № 1. - С. 4-10.

60. Малоземов В.Н., Певный А.Б., Третьяков А.А. Быстрое вейвлетное преобразование дискретных периодических сигналов и изображений // Проблемы передачи инф. 1998. - Т.34, Вып.2. - С. 77-85.

61. Brislawn С.М. The FBI Fingerprint Image Compression Specification in Wavelet Image and Video Compression / Boston Kluwer. . 998. — ch.16. - pp.271.288.

62. Bradley J.N., Brislawn C.M. Compression of fingerprint data using the wavelet vector quantization image compression algorithm // Los Alamos Nat'l. Lab. 1992. - FBI Tech. Rep. LA-UR-92-1507.

63. Bradley J.N., Brislawn C.M. FBI parameter settings for the first WSQ fingerprint image coder // Los Alamos Nat'l. Lab. 1995. - FBI Tech. Rep. LA-UR-95-1410.

64. Колмогоров A.H., Фомин C.B. Элементы теории функций и функционального анализа. М;: Изд-во "Наука", 1976. - 543 с.

65. Иванов В.И. Введение в теорию приближений. 2-е изд., испр. Тула: ТулГУ, 1999.- 116 с.

66. Корн Г., Корн Т. Справочник по математике (для научных работников и инженеров). 6-е изд., стер. СПб.: Изд-во "Лань", 2003. - 832 с.

67. Martens J.B. The Hermite Transform Theory // IEEE Trans, on Acoustics, Speech and Signal Proc. - 1990.- Vol.38.-pp. 1595-1606.

68. Martens J.B. The Hermite Transform Applications // IEEE Trans, on Acoustics, Speech and Signal Proc. - 1990.- Vol.38. - pp. 1607-1618.

69. Радченко Ю.С., Радченко М.Ю. Оптимальные быстрые алгоритмы представления изображений в базисе ортогональных полиномов // Труды I международной конференции DSPA'98; 1998. - Т.З. - С. 163-166.

70. Радченко Ю.С., Кожин А.Ю., Радченко М.Ю. Обнаружение и оценка параметра сдвига сжатых с помощью ортогональных полиномов сигналов // Радиотехника. 1999. - №6. - С. 17-19.

71. Блаттер К. Вейвлет-анализ. Основы теории. М.: Техносфера, 2004. - 280 с.

72. Уэлстид С. Фракталы и, вейвлеты для сжатия изображений в действии. М.: Изд-во "Триумф", 2003. - 320 с.

73. Jawerth В., Sweldens W. An Overwiew of Wavelet Based Multiresolu-tion Analyses // S1AM Rev. 1994. - Vol.36, No.3. - pp. 377-412.

74. Lewis A., Knowles G. Image Compression Using the 2D Wavelet

75. Transform // IEEE Trans, on Image Proc. 1992. - Vol.1, No.2. - pp. 244-250.

76. Said A., Pearlman W. A New; Fast and Efficient image Codec Based on Set Partitioning in Hierarchical Trees // IEEE trans, on Circuits and Systems for Video Technology. 1996. - Vol.6. - pp. 243-250.

77. Said A., Pearlman W. An image Multiresolution Representation for lossless and lossy Compression // IEEE Trans, on Image Proc. 1996. — Vol.5, No.9. - pp. 243-250.

78. Mandal M., Panchanathan S., and Aboulnasr T. Choice of Wavelets for Image Compression // Lecture Notes in Computer Science. 1996. - Vol.1133. -pp. 239-249.

79. Shapiro J. Embedded Image Coding Using Zerotrees of Wavelet Coefficients // IEEE Trans, on Signal Proc. 1993. - Vol.41, No. 12. - pp. 3445-3462.

80. Поршнев C.B. Применение непрерывного вейвлет-преобразования для обработки широкополосных частотномодулированных сигналов // Вычислительные методы и программирование. 2003. - Т.4. - С. 104-116.

81. Прэтт У. Цифровая обработка изображений: Пер. с англ. М.: Мир, 1982.-т.1.-312с.

82. Meyer Y. Wavelets: Algorithms and Applications. Philadelphia: SIAM, 1993.-p.127.

83. Coifman R., Meyer Y., Quake S., Wickerhauser M. Entropy based algorithms for best basis selections // IEEE Trans, on Inf. Theory. 1992. - Vol.38, No.2. -pp. 713 -718.

84. Monro D.M., Bassil B.E., Dickson G.J. Orthonormar wavelets with balanced uncertainty // IEEE Trans, on Image Proc. 1996. - Vol.2. - pp. 581-584.

85. Monro D.M., Sherlock B.G. Space-frequency balance in biorthogonal wavelets // IEEE Trans, on Image Proc. 1997. - Vol.1. - pp. 624-627.

86. Villasenor J.D., Belzer В., Liao J. Wavelet Filter Evaluation for Image Compression // IEEE Trans, on Image Proc. 1995. - Vol.4, No.8. - pp. 10531060.

87. Kim W.H., Hu Y.H., Nguyen T.Q. Wavelet-Based Image Coder with

88. Entropy Constrained Lattice Vector Quantizer // IEEE Trans, on Circuits and Systems. 1998. - Vol.45, No.8. - pp. 1015-1030.

89. Tran T.D., Nguyen T.Q. A Progressive Transmission Image Coder Using Linear Phase Uniform Filterbanks as Block Transform // IEEE Trans, on Image Proc. Vol.8, No.l 1. - pp. 1493-1507.

90. The Theory and Design of Arbitrary-Length Cosine-Modulated Filter Banks and Wavelets, Satisfying Perfect Reconstruction // IEEE Trans, on Signal Proc. Vol.44, No.3. - pp. 473-483.

91. Vetterli M. Filter banks allowing perfect reconstruction // IEEE Trans, on Signal Proc. 1986. - Vol: 10, No.3. - pp. 219-244.

92. VetterliM., Her ley C. Wavelets and Filter Banks: Theory and Design // IEEE Trans, on Signal Proc. 1992. - Vol.40, No.9. - pp. 2207-2232.

93. Kim B.J., Xiong Z., Pearlman W. Low Bit-Rate Scalable Video Coding with 3D Set Partitioning in Hierarchical Trees // IEEE Trans, on Circuits and Systems for Video Tech. 2000. - Vol.10, No.8. - pp. 1374-1387.

94. Хилл Ф. OpenGL. Программирование компьютерной графики. -СПб.: Питер, 2002. 1008 с.

95. Русев А.В., Ивашин С.Л., Талныкин Э.А. Математические модели сцен в синтезирующих системах визуализации реального времени // Автометрия. 1985. - №4. - С. 3-9.

96. Палташев Т.Т., Климина С.И., Лях А.С. Технология визуализации в компьютерном синтезе реалистичных изображений // Зарубежная радиоэлектроника. 1984. - №8. - С. 64-79.

97. Роджерс Д.Ф. Алгоритмические основы машинной графики. М.: Мир, 1989. -512 с.

98. Эйнджел Э. Интерактивная компьютерная графика. Вводный курс на базе OpenGL. М.: Издательский дом "Вильяме", 2001. - 592 с.

99. Шикин Е.В., Боресков А.В. Компьютерная графика. Полигональные модели. М.: ДИАЛОГ-МИФИ, 1999. - 464 с.

100. Laur, D. and Hanrahan, P. Hierarchical Splatting: A Progressive Refmement Algorithm for Volume Rendering // S1GGRAPH'91 Proceedings. 1991. -pp. 285-288.

101. Westover L. Footprint Evaluation for Volume Rendering // SIGGRAPH'90 Proceedings. 1990. - pp. 367-376.

102. Lorensen W.E., Cline H. E. Marching Cubes: A High Resolution 3D Surface Construction Algorithm // SIGGRAPH'87 Proceedings. ~ 1987. Vol.21, No.4.-pp. 163-169.

103. Agarwal P.K., Suri S. Surface approximation and geometric partitions // ACM Symposium on Discrete Algorithms Proceedings. — 1994. pp. 24-33.

104. Oxley A. Surface fitting by triangulation // Computer Journal. 1985- Vol.28, No.3. pp. 243-245.

105. Puppo E. Variable resolution triangulations // Computational Geometry. 1998. - Vol.11. - pp. 219-238.

106. De Floriani L. A pyramidal data structure for triangle-based surface description // IEEE Computer Graphics and Applications. —1989. Vol.9, No.2. -pp. 67-78.

107. De Floriani L., Marzano P., Puppo E. Multiresolution Models for Topographic Surface Description // The Visual Computer. 1996. - Vol: 12, N.7. -pp. 317-345.

108. Koninger A., Bartel S. 3D-GIS for Urban Purposes // Geolnformatica.- 1998.-Vol.2, No. 1.-pp. 79-103.

109. Кошкарев A.B., Тикунов B.C. Геоинформатика. ~ M.: Картгеоиз-дат-геодезиздат, 1993.-213 с.

110. Желтов С.Ю., Инвалев А.С., Кирьяков К.Р., Степанов А.А. Особенности реализации 3D ГИС // Инф. бюллетень ГИС-ассоциации. — 1997. -№5.-С. 52-53.

111. Делоне Б.Н. О пустоте сферы // Изв. АН СССР, ОМЕН. 1934. -№4. - С. 793-800.

112. Voronoi G. Nouvelles applications des parameters continues a la therie des formes quadratiques. Deuxieme Memorie: Recherches sur les parralleloeddres primitifs//J. reine angew. Math. 1908. - No. 134. - pp. 198-287.

113. Кошкарев A.B., Тикунов B.C. Геоинформатика. M.: Картгеоиз-дат-Геодезиздат, 1993. - 213 с.

114. Ильман В.М. Алгоритмы триангуляции плоских областей.по нерегулярным сетям точек // Алгоритмы и программы, ВИЭМС. 1985. -Вып. 10(88). - С. 3-35.

115. Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. - 478 с.

116. Фокс А., Пратт М. Вычислительная геометрия. Применение в проектировании и на производстве. М.: Мир, 1982. -304 с.

117. Ильман В.М. Экстремальные свойства триангуляции Делоне // Алгоритмы и программы, ВИЭМС. 1985. - Вып. 10(88). - С. 57-66.

118. Tan T.S. An Optimal Bound for High-Quality Conforming Triangula-tions // Discrete and Сотр. Geometry. 1996. - Vol.15. - pp. 169-193.

119. Lingas A. The Greedy and Delaunay triangulations are not bad // Lect. Notes Сотр. Sc. 1983. - Vol.158. - pp. 270-284.

120. Manacher G., Zobrist A. Neither the Greedy nor the Delaunay triangu-lation of planar point set approximates the optimal triangulation // Inf. Proc. Lett. -1977. Vol.9, No.l. - pp. 31-34.

121. Midtbo T. Spatial Modeling by Delaunay Networks of Two and Three Dimensions: PhD thesis / Norwegian Inst, of Tech. Trondheim, 1993.

122. Скворцов A.B, Триангуляция Делоне и ее применение. Томск: Изд-во Том. ун-та, 2002. —128 с.

123. Lawson С. Transforming triangulations // Discrete Mathematics. -1972. No.3.-pp. 365-372.

124. Weiler К. Edge-based data structures for solid modeling in curved surface environments // IEEE Computer Graphics and Applications. 1985.,- Vol.5, No.4. - pp. 21-40.

125. Schroeder W.J., Zarge J.A., Lorensen W.E. Decimation of triangle mesh // SIGGRAPH'92 Proceedings. 1992. - pp. 65-70.

126. Земцов А.Н. Прогрессивная передача триангуляционных моделей в сети Internet // 11-я Международная научно-техническая конференция студентов и аспирантов: Сб. тр. МЭИ. 2005. —-Т. Г. - С. 370.

127. Попов Н.В., Земцов А.Н. Реализация вейвлет-преобразования на ПЛИС // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. ВолгГТУ. 2002. - Т. 1. - С. 211-213.

128. Земцов А.Н., Андреев А.Е., Попов Н.В. Аппаратурно-ориентированные структуры компрессии графической информации // Информационные технологии в образовании, технике и медицине: Сб. науч. тр. ВолгГТУ. 2002; - Т. 1. - С. 113-115.

129. Cignoni P., Montani С., Scopigno R. A Comparison of Mesh Simplification Algorithms // SIGGRAPH'97. 1997. - pp. 123-152.

130. Cignoni P., Rocchini C., Scopigno R. Metro: measuring error on simplified surfaces // l.E.I. C.N.R. - 1996. - Tech. Rep. B4-01-01-96.

131. Pajarola R, Rossignac J. Compressed; Progressive Meshes // IEEE Trans, on Visualisation and Computer Graphics. 2000. - Vol.6, No.l. - pp. 7993.132; Turk G. Re-tiling polygonal surfaces // SIGGRAPH'92 Proceedings. -1992.-pp. 55-64.

132. Rossignac J. Geometric simplification and compression //

133. SIGGRAPH'97 Proceedings. 1997. - pp. 55-64.

134. Low K.L., Tan T.S. Model simplification using vertex-clustering // SIGGRAPH'97 Proceedings. 1997. - pp. 75-81.

135. Hoppe H., DeRose Т., Duchamp Т., McDonald J., Stuetzle W. Mesh optimization // SIGGRAPH'93 Proceedings. 1993. - pp. 19-26.

136. Heckbert P., Garland M. Survey of Polygonal Surface Simplification Algorithms // ACM SIGGRAPH'97 Course Notes. 1997. - No.25. - pp. 1-29.

137. Soucy M;, Laurendau D. Multiresolution surface modeling based on hierarchical triangulation // Computer vision and image understanding. 1996. -Vol.63, No. 1.-pp. 1-14.

138. Taubin G., Gueziec A., Horn W., Lazarus F. Progresive Forest Split Compression // SIGGRAPH'98 Proceedings. 1998. - pp. 123-132.

139. Taubin G., Rossignac J. Geometric compression through topological surgery // SIGGRAPH'98. 1998. - Vol.17, No.2. - pp. 84-115.

140. Cohen-Or D., .Levin, D., Remez O. Progressive Compression of Arbitrary Triangular Meshes // IEEE Visualisation'99. 1999. - pp. 67-72.

141. Alliez P., Desbrun M. Progressive Encoding for Lossless Transmission of 3D Meshes // SIGGRAPH'2001 Proceedings. 2001. - p. 8.

142. Kami Z., Gotsman C. Spectral Compression of Mesh Geometry // SIGGRAPH'2000. 2000. - pp. 279-286.

143. Hoppe H. Progressive meshes // SIGGRAPH'96 Proceedings. 1996. -pp. 99-108.

144. Воробьев В.И., Грибунин B.F. Теория и практика вейвлет-преобразования. СПб.: ВУС, 1999: - 204 с.

145. Lounsbery М., DeRose Т., Warren J. Multiresolution Analysis for Surface of Arbitrary Topological Type 7/ ACM Trans, on Graphics. 1997. -Vol.16, No.l.-pp. 34-73.

146. Catmull E., Clark J. Recursively Generated B-spline Surfaces on Arbitrary Topological Meshes // Computer Aided Design. 1978. - Vol.10, No.7. - pp. 350-355.

147. Doo D., Sabin M. Behaviour of Recursive Division Surfaces Near Extraordinary Points7/ Computer Aided Design. 1978. - Vol.10, No.6. - pp. 356360.

148. Dyn N., Levin D., Gregory J. A Butterfly Subdivision Scheme for Surface Interpolation with Tension Control7/ ACM Trans, on Graphics. 1990. -Vol.9, No.2.-pp. 160-169.

149. Dyn N., Hed S., Levin D. Subdivision schemes for surface interpolation // Workshop in Сотр. Geometry. 1993. - pp. 97-118.

150. Loop C.T. Smooth Subdivision Surfaces Based on Triangles: MS thesis / Univ. of Utah. Salt Lake City, 1987.

151. Kobbelt L. Interpolatory Subdivision on Open Quadrilateral Nets with Arbitrary Topology // Eurographics'96 Proceedings. 1996. - pp. 409-420.

152. Zorin D., Schroder P., Sweldens W. Interpolating Subdivision for Meshes with Arbitrary Topology // SIGGRAPH'96 Proceedings. 1996. - pp. 189-192.

153. Zorin D., Schroder P., Sweldens W. Interactive Subdivision for Meshes with Arbitrary Topology // SIGGRAPH'97 Proceedings. 1997. - pp. 259-268.

154. Lounsbery M. Multiresolution Analysis for. Surfaces of Arbitrary Topological Type: PhD thesis / Univ. of Washington. Seattle, 1994.

155. Deering M. Geometric compression // SIGGRAPH'95 Proceedings. -1995.-pp. 13-20.

156. Rossignac J. Edgebreaker: Connectivity compression for triangle meshes // IEEE Trans, on Visualization and Computer Graphics. 1999. - Vol.5, No.l.-p. 16.

157. Скворцов A.B. Сжатие топологических связей триангуляции // Вычислительные методы и программирование. 2002. - Т.З. - С. 124-132.

158. Chow М. Optimized Geometry Compression for Real-Time rendering // IEEE Visualization Proc. 1997. - pp. 347-354.

159. Evans F., Skiena S., Varshney A. Optimizing triangle strips for fastrendering // IEEE Visualization Proc. 1996. - pp. 319-326.

160. ToumaC., Gotsman C. Triangle Mesh Compression// Graphics Interfaced- 1998. pp. 26-34.

161. Isenburg M., Snoeyink J. Mesh Collapse Compression // Proc, of ACM Symp. on Сотр. Geometry. 1999. - pp. 419-420.

162. Садыков С.С., Захаров А.А. Выбор уровня детальности при непрерывном упрощении поверхностей полигональных объектов // Вычислительные методы и программирование. 2003. - Т.4. - С. 82-93;

163. Федотов Р.В. Алгоритмы оптимизации фасетчатых моделей и методы из сетевой передачи // Вычислительные методы и программирование. -2003.- Т.4.-С. 216-226.

164. Kim Y.S., Valette S., Prost Rl Adaptive wavelets based multiresolution modeling of irregular meshes via harmonic maps // IEEE Int. Conf. on Image Proc. ICIP'2001. 2001.- Vol.3.-pp. 210-213.

165. Eells J., Lemaire L. Another report on harmonic maps // Bull. London Math. Soc. 1988. - Vol.20. - pp. 385-524.

166. Mount D.M. Voronoi diagrams on the surface of a polyhedron // Univ. of Maryland. 1985. - Dept. of CS Tech. Rep.CAR-TR-121.

167. Mount D.M. Voronoi diagrams on the surface of a polyhedron // Univ. of Maryland. 1985. - Dept. of CS Tech. Rep. CS-TR-1496.

168. Mitchell J.S., Mount D.M., Papadimitriou C.H. The discrete geodesic problem // SIAM Journal of Computing. 1987. - Vol.16, No.4. - pp. 647-668.

169. Lee A.W.F., Sweldens W., Schroder P., Cowsar L., Dobkin D. MAPS: Multiresolution Adaptive Parametrization on Surfaces // SIGGRAPH'98 Proceedings.- 1998.- pp.95-104.

170. Howard Vitter J. Arithmetic Coding for Data Compression // Proc. IEEE. 1994. - Vol.82, No.6. - pp. 857-865.1. ТЕХНИЧЕСКИЙ АКТ ВНЕДРЕНИЯ

171. Внедрен метод компрессии Снижение объема 49.5триангуляционных моделей доли трафикарельефа земной поверхности передаваемых посети моделей