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

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

1и

484991

ЮСОВ Егор Александрович

Модели и алгоритмы многомасштабного

представления данных для высокопроизводительной визуализации ^ геоповерхностей ~~~

Специальность: 05.13.17 - «Теоретические основы информатики» (технические науки)

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

1 6 июн 2011

Нижний Новгород - 2011

4849988

Работа выполнена на кафедре математического обеспечения ЭВМ в Нижегородском государственном университете им. Н.И.Лобачевского (г. Нижний Новгород)

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

доктор технических наук, доцент, профессор каф. МО ЭВМ ННГУ Турлапов Вадим Евгеньевич

Официальные оппоненты:

доктор технических наук, профессор, заслуженный деятель науки РФ Васин Юрий Григорьевич

доктор технических наук, профессор, Утробин Владимир Александрович

Ведущая организация:

ВМиК МГУ им. М.В.Ломоносова, г. Москва

Защита диссертации состоится «30» июня 2011 г. в 13 часов на заседании диссертационного совета Д.212.165.05 в Нижегородском государственном техническом университете им. Р.Е.Алексеева по адресу: 603950, г. Нижний Новгород, ГСП-41, ул. Минина, 24, ауд. 1258.

7

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

Автореферат разослан «30» мая 2011 г.

Ученый секретарь диссертационного совета кандидат технических наук А.С. Суркова

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

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

Разработка эффективных технологий сжатия изображений и другой информации с целью повышения эффективности хранения и передачи, а также методов многомасштабного моделирования объектов различной природы, в том числе и рельефа, отвечающих современному уровню развития вычислительной техники, является активно исследуемой областью, как в России, так и за ее пределами. Подтверждением этому является большое количество публикаций, посвященных проблемам сжатия изображений и пространственных данных. Здесь следует отметить работы Ю.Г. Васина, A.B. Кудина, С.В. Жерздева, В.В.Сергеева, ВА.Сойфера, М.Кунта (M.Kunt), Дж. Шапиро (J.Shapiro), А.Саида (A.Said), У.Перельмана (W.Pearlman) и др. Многомасштабным моделям и методам построения адаптивных триангуляций рельефов для их эффективной визуализации также посвящено много работ. В последние годы этой проблемой занимались А.В.Плесков, Ю.Г.Васин, A.B. Переберин, Ю.М. Баяковский, М.В. Михайлюк, ПЛиндстром (Р. Lindstrom), М.Дюшейн (М. Duchaineau), Х.Хоуп (Н. Hoppe), и др. Тем не менее, с развитием вычислительной техники быстро растут требования к реалистичности выводимой сцены, увеличиваются объемы данных, задающих рельеф местности.

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

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

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

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

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

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

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

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

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

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

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

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

• Экспериментально исследовать эффективность комплекса и реализованных в нем моделей и методов.

Объектом исследования являются информационные модели открытых территорий большой площади.

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

Методы исследования. Решение задач диссертационной работы базируется на: методах обработки и сжатия изображений, в том числе теории вейвлет-преобразований; теории информации; теории вероятностей; теоретических основах аналитической геометрии; методах компьютерной графики; методах параллельных вычислений. Теоретической базчй настоящего исследования явились основополагающие работы: отечественных ученых - Ю.Г.Васина, В.В .Сергеева, В.А.Виттиха, ВА.Сойфера и их учеников, а также зарубежных ученых - М.Кунта (М.КиШ), У.К. Прэтга ^.К.РгаП), И.Добеши (ХОаиЬесЫез), Дж. Шапиро (.Г.8Ьарш>), У.Перельмана (>У.Реаг1тап), П.Линдстрома (Р. ЬпкЫгот) и др.

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

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

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

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

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

Создан набор библиотек СОМ-компонентов, реализующих разработанные модели и алгоритмы, готовый к практическому использованию в подсистемах визуализации местности таких приложений как авиакосмические симу-ляторы, системы виртуальной реальности для киноиндустрии и путешествий, игры и т.д. Модель внедрена в корпорации Интел; в НИИ Системных Исследований РАН; использована институтом машиноведения УрО РАН. Программный комплекс включен в виде лабораторной работы по моделированию рельефа в учебно-методический комплекс «Компьютерная графика» и может быть использован в учебном процессе вузов.

Достоверность результатов работы подтверждена компьютерными экспериментами по моделированию конкретных участков земной поверхности, заданных равномерной матрицей высот (рельеф гор Кавказа, прилегающая территория горы Puget Sound, рельеф Великого Каньона США и др.).

Апробация работы. Основные результаты работы доложены и обсуждены на: международной конференции по компьютерной графике, визуализации и компьютерному зрению WSCG2011 (Пльзень, Чехия, 2011); международной конференции по компьютерной графике, визуализации, компьютерному зрению и обработке изображений CGVCVIP'2010 (Фрейбург, Германия, 2010); международных конференциях по компьютерной графике и визуализации -GraphiCon (Новосибирск, 2005, 2006; Москва, 2007, 2008; Санкт-Петербург, 2010); международной научной конференции «Параллельные Вычислительные Технологии (ПаВТ'2009)»; всероссийских конференциях «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2006, 2007, 2008 - дипломы I степени на конкурсах, проводимых в рамках конференций); всероссийской конференции по параллельным вычислениям (Нижний Новгород, 2008); всероссийских конференциях «Методы и средства обработки сложной графической информации» (Нижний Новгород, 2005,2006); семинарах кафедры МО ЭВМ факультета ВМК ННГУ. Лабораторная работа по моделированию рельефа внедрена в курсе «Компьютерная графика» на факультете ВМК ННГУ, использована в образовательном проекте Intel Studio Graphics 2008, во Всероссийской научной школе для молодежи «Компьютерное зрение, 3D моделирование и компьютерная графика» 2010 года (госконтракт №02.741.12.2170). Результаты работы использованы корпорацией Интел, НИИ Системных Исследований РАН, а также институтом машиноведения УрО РАН. Работа также прошла конкурсный отбор для участия в программе У.М.Н.И.К (госконтракт №7095р/9642).

Публикации. Основные результаты исследования опубликованы в 17 работах, из них 4 - публикации в изданиях, рекомендованных ВАК.

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

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

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

Структура и объем работы. Диссертация состоит из введения, трех глав, заключения, списка литературы из 160 наименований. Общий объем - 180 стр.

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

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

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

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

В подразделе 1.2 рассмотрены иерархические алгоритмы вейвлет-сжатия. Приведены основные положения вейвлет-анализа и дискретное вейвлет-преобразование (ДВП) как свертка строк и столбцов матрицы S исходных данных с низкочастотным и высокочастотным фильтрами с последующим прореживанием. Результат — матрица того же размера, состоящая из: низкочастотной части исходного сигнала (LL) и высокочастотных частей (LH, HL и НН), содержащих вейвлет-коэффициенты для восстановления S. Линейные операторы прямого и обратного ДВП обозначены следующим образом:

LL-Wa{S), LH = Wjj,(S), HL = WHL(S), HH = WHH(S); (1)

S = JV~' (LL, LH, HL, HH). (2)

В подразделе 1.3 представлены двухэтапные методы сжатия с контролем ошибки в метрике Чебышева. Подраздел 1.4 посвящен методам построения адаптивной триангуляции для целей визуализации рельефа. Анализ работ в подразделе 1.5 подтверждает целесообразность и актуальность настоящего диссертационного исследования.

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

- блочная организация существенно увеличивает параллельность и производительность вычислений благодаря однородному оперированию целыми областями (64x64, 128x128,256x256) вершин как с одним узлом дерева;

- высокий коэффициент сжатия данных;

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

- при передаче данных по сети восстановление данных может выполняться по мере поступления информации.

В подразделе 2.2 построен метод сжатия, обеспечивающий восстановление данных с заданной максимально допустимой поэлементной чебышевской погрешностью и превосходящий по степени сжатия лучшие из известных алгоритмов. Метод включает в себя следующие стадии: 1) блочная реструктуризация регулярной матрицы высот, 2) построение последовательности более грубых приближений исходных данных путем применения вейвлет-фильтрации; 3) построение квадродерева для иерархии приближений; 4) вейвлет-интерполяция (предсказание) значений более детального уровня иерархии по более грубому и переход к дереву невязок предсказания; 5) сжатие матриц невязок при помощи двухэтапной схемы: а) вейвлет-декомпозиция матрицы;

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

в) восстановление матрицы невязок; г) вычисление ошибки восстановления; д) квантование и кодирование ошибки восстановления с заданной максимально допустимой поэлементной пмрешностью в метрике Чебышева; 6) бесшовное соединение соседних матриц высот в одном уровне иерархии.

В пункте 2.1.1 формализуются исходные данные для задачи обработки, моделирования и визуализации рельефа. Под входными несжатыми данными понимается матрица А размером 2'°х2'°, содержащая отсчеты высоты

О < ¿,7 < 2'° в узлах регулярной сетки.

В пункте 2.1.2 описан метод блочно-иерархической вейвлет-декомпозиции матрицы высот. На первом шаге матрица разбивается сеткой из 2*° х 2*° квадратных блоков Атп = {а^^,]), 0 < г,у < 2Р° размером 2Р° х 2Ра отсчетов (64x64, 128x128,256x256), где к0=10~р0:

А =

Ад 0 ... А(

0,2*°-1

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

1. Матрицы высот А^ максимального уровня разрешения ко задаются исходным данными: А^ = Ат „, 0 < ти, п < 2*°. (3)

о(*> =

т,л

2. В процессе построения уровня к матрицы высот А^ уровня £+1 объединяются в группы по 2x2:

>(»+1) АМ) \

2:,Г > 0<т,п<2к, к = к0 ...,0. (4)

3. К объединенным матрицам 0(тк)„ применяется двумерное ДВП (1), что дает матрицы высот А(тк)п уровня иерархии к, а также матрицы детализирующих коэффициентов ЬН^, и НН^П уровня к:

= Г/ш (О^), НИк\ = (£%), НН™ (5X8)

0£м,п<2к, к = ко-1,...,0.

Для выполнения вейвлет-декомпозиции используется наиболее эффективное из известных биортогональное преобразование Коэна-Добеши-Фово (СБР9/7). Результат построения (3)-(8) может быть представлен в виде квадро-дерева, имеющего к0 уровней, с узлами (0йк<,к0, 0 < от, и < 2*). Каждому узлу из уровня от 0 до к0 -1 приписаны соответствующие детализирующие вейвлет-матрицы, корневой вершине дополнительно приписана матрица высот самого грубого приближения, а узлы из уровня к0 не содержат данных:

<>: {<>, ,Ш<°>}, (9)

0<т,п <2к,\<к<,к0-\. (10)

При сжатии с потерями, восстановленные матрицы высот (обозначены через А^ 0<г,7<2Ро, 0<ти,л<2*, 0<к^к0) будут отличаться от

исходных. Будем говорить, что матрица сжата с ошибкой 5к, если:

^¿а^-а^^бь. (11)

Для точного восстановления матрицы 0(тк)п (и матриц А^2п,

и по матрице А^] декодеру помимо детализирующих матриц

НИк\ и НН1Ч необходима еще поправка Тогда 0(тк)„

может быть вычислена с помощью обратного ДВП (2):

0(:1 = +АА%, НИ», НН1'1). (12)

Для решения задачи контроля поэлементной погрешности восстановления (11) в пункте 2.1.3 предлагается эквивалентное представление иерархии (9)-(10) в виде дерева невязок вейвлет-предсказания. Под невязкой вейвлет-предсказания понимается отклонение точной матрицы от матрицы

0^1, получаемой применением обратного ДВП (2) с нулевыми детализирующими коэффициентами к восстановленной матрице А^п:

' (13)

<^=^-'(^,0,0,0). (14)

Матрицы невязок , 0 < < 2*, 0<к<к0-1 могут быть объединены в квадродерево, подобное дереву (9)-(10), узлам Л^*' из уровней от 0 до к0 — 1 которого приписаны соответствующие матрицы , корневому узлу дополнительно приписана матрица высот самого грубого представления а узлы из уровня к0 не содержат данных:

(15)

(О. 0^т,п<2\ lrSt^-l. (16)

Дерево (15)-(16), как и дерево (9)-(10), представляет исходную матриц}' высот А в виде грубого ее приближения °о и набора невязок D^, позволяющих последовательно восстановить исходные данные.

Доказана следующая теорема: блочно-иерархическая вейвлет-декомпозиция, заданная матрицами поправок АЛ™ и детализирующими вейв-лет-матрицами LH^n, и НН^„ эквивалента дереву невязок вейвлет-

предсказания, определенному матрицами D(Jl.

Также доказана теорема: дерево невязок вейвлет-предсказания (15)-(16) может быть построено за линейное от объема исходных входных данных N число операций. Дополнительные затраты памяти на построение квадродерева невязок не превышают МЗ.

Переход к дереву невязок (15)-(16) позволяет заменить задачу сжатия блочно-иерархической вейвлет-декомпозиции задачей сжатия дерева невязок, для которой осуществим контроль поэлементной погрешности восстановления, т.к. требование (11) (как показано в подразделе 2.21 эквивалентно следующему:

^J^U-^U (17)

где (0<i,j<2-2р°, 0<т,п<2\ 0<к<к0-\) - восста-

новленная матрица невязок.

Сжатие матриц невязок, описанное в подразделе 2.2. состоит из двух этапов. На первом этапе (пункты 2.2.1-2.2.5) выполняется вейвлет-сжатие матрицы

D^l. На втором этапе матрица декодируется и полученная матрица вычитается из исходной , что дает матрицу ошибок восстановления :

о»)

Матрица R(m*l квантуется (пункт 2.2.61 с учетом погрешности SM, так,

чтобы для восстановленной матрицы невязок D^l = + (где R^ - квантованная матрица ошибок) выполнялось требование (17), и кодируется.

Первым шагом вейвлет-сжатия матрицы является построение ее вейв-лет-декомпозиции (пункт 2.2.1) (индексы т, п, к для удобства в некоторых обозначениях опущены):

LL(">=(//<f)2"*2" =Wa(Dlkl), ГЛР)={1ф2'*2' = WU(LL<>*1)), (19H20)

Ltf"°> LH{P) = (Iff?)1'*' = Ww{Llip*n), (21)-(22)

HI}*'={hl\??n*n =W„L(Dl% HL(P> =(h!<?f"2'=fV„L(LL<^), (23)-(24)

HH<P°) = {hhlff^ = Ж„„«>), ЯЯ(" = (Ц?)2'*2' - WHH(Lli^), (25H26)

Коэффициенты вейвлет-декомпозиции (19)-(26) квантуются при помощи антователя с мертвой зоной (пункт 2.2.2):

q = М/2"» - шаг квантования, где М = max (| Ihjf |,| |,| hh™ |) - мак-

симальное абсолютное значение коэффициентов из детализирующих субполос (ЬН, НЬ и НН) всех масштабов, пЬр - заданное максимальное количество бит,

отведенное для представления абсолютных значений.

Показано, что оптимальным, по критерию минимизации среднеквадрати-ческого отклонения в пространстве вейвлетов, методом восстановления коэффициентов, при аппроксимации распределения их абсолютных значений экспоненциальным законом Лапласа, является следующий: Иедшт^) = !ц + р.,

где ц = — ^ | • <?) - средняя величина смещения истинных значений абсолютных величин коэффициентов от нижней границы интервала квантования, в который они попадают.

Ввиду иерархической природы вейвлет-преобразования коэффициенты декомпозиции (19)-(26) естественным образом упорядочиваются в иерархические структуры квадродеревьев. Согласно свойству локализации энергии в вейвлет-представлении сигнала, если коэффициент из некоторого масштаба приближения квантован к нулю, то с большой вероятностью все коэффициенты, принадлежащие растущему из него поддереву, также квантованы к нулю. Поддеревья, содержащие только квантованные к нулю коэффициенты, называются в литературе нуль-деревьями. Для кодирования структуры дерева (пункт 2.23). оставшейся после отбрасывания нуль-деревьев, введены следующие обозначения: Т/у' - множество позиций всех потомков узла (¡,],р),

ивд, 1Л&Д. ит«£>,+1, о<1,]<2р,о<р<р0~1-

А}'* — множество позиций узлов поддерева, растущего из узла ис-

ключая сам узел: А<? = (г, ./,/>)}, 0<г,у<2", 0<р<р0-\\

(27)

где через ^ обозначен любой коэффициент , Ы\р) или

- операция округления аргумента вниз до ближайшего целого,

В)"/ - множество позиций узлов в поддереве, растущем из узла (/,7, р), исключая сам узел, а также его непосредственных потомков: В<? = А<*> /{{И,и,р +1), (2/ + \,1],р +1), (2/,2у +1,/> +1), (2г +1,2/ + 1.Р + 1)}, 0</,у<2", р = р0-2....0.

Введены флаги а^р), а™(р\ а также Д™

зНН(р)

нали-

чия хотя бы одного квантованного не к нулю (значимого) коэффициента во множествах А^ и В^, а также флаги , у"^Р) и у""{р) наличия квантованного коэффициента в узле (1,],р) дерева соответствующей субполосы.

Кодирование структуры дерева выполняется в процессе обхода коэффициентов зигзагом (рис.1 (а)) следующим образом (принято, что =1, Д^1' =1):

2. Если = то кодируется флаг а.р). Если а\р) =1, то кодируется

флаг

3. Выполняется переход к следующему коэффициенту в порядке обхода.

В силу свойства пространственной локализации вейвлет-преобразования, между пространственно близкими флагами а.р) и существует статистическая зависимость. Для ее учета используется адаптивное статистическое моделирование. Контекст для кодирования флагов изображен на рис. 1(6), а номер гистограмм для кодирования вычисляется по следующим формулам: СМ[а'?] = а» + + + >

СМ[Д<?] = Д« + Д« + Д<?, + Д<*+1.

Ч

£ Ш да*?1 ——

ки ¡»л нр^1'

у--' л ]

—гтт"

........1

1 1 1 1

а'-и :

«1'А

1 1

а)

б)

нй

М-и- «-V

Ач'Ь-! Г7">

Рисунок 1 - а) Порядок обхода квантованных вейвлет-коэффициентов; б) Контекст для кодирования флагов а.р) и ; в) Положения коэффициентов для оценки абсолютного значения кодируемого коэффициента

В процессе обхода (рис.1(а)) вейвлет-коэффициентов, для каждого коэффициента, для которого установлен флаг у = 1, кодируется количество бит пЬиз{1) для представления его квантованного абсолютного значения I. После

этого по битам кодируется само квантованное абсолютное значение ?, и, наконец, - знак коэффициента. Этот процесс описан в пункте 2.2.4.

Для кодирования пЬШ(з) используется адаптивное статистическое моделирование. Благодаря пространственной и частотной локализации ДВП, ожидаемое абсолютное значения восстановленного коэффициента может быть

достаточно точно оценено через абсолютные значения четырех соседних коэффициентов и родителя (рис. 1(в)) по формуле:_ _

«Й* +",(5Й!н)2 .

где веса м>, определяются из условия минимизации объема кодового потока. Предсказанное значение квантуется согласно (27): т. ^ =

Контекстом для кодирования пЬИз^^) является число бит пЬйзОя,^), требующееся для ожидаемого квантованного абсолютного значения т. ? в паре с уровнем декомпозициир: СМ[пЬШ{^р^)] = (пЬиз(т^)),р).

Кодирование знака основано на том факте, что паттерны, которые образуют знаки в каждой детализирующей субполосе, не равновероятны. Если обозначить знак коэффициента 5 через = {-1Д+1}, то контекст для кодирования знака будет вычисляться на основе знака и значимости трех соседей:

СЛф/^')] = ) + 2) • + 2) • + 2).

Псевдокод операций, объединяющий результаты пунктов 2.2.1-2.2.4 приведен в пункте 2.2.5.

Пункт 2.2.6 посвящен сжатию матрицы ошибок восстановления

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

ошибок ее соседей:

СМ[ги ] = г1щН + + + гн ^.

Верхняя оценка погрешности ЕггЛррг(А^), с которой матрица аппроксимирует исходные данные, представлена в пункте 2.2.7. Вычисление выполняется рекурсивно по уровням, от нижних к верхним, следующим образом:

ЕггЛррг(А^) = 6ч,

=^»сД^. +Л:=Ль -1. — .0,

где - максимальное отклонение отсчетов матрицы, линейно

интерполированной по восстановленной из сжатого представления матрице высот , от отсчетов матрицы 0^1.

В пункте 2.2.8 представлен метод кодирования дополнительных граничных отсчетов, обеспечивающих бесшовное соединение соседних матриц. Матрицы расширенные согласующими контурами, обозначаются Е^. Согла-

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

В подразделе 2.3 представлены результаты вычислительных экспериментов и их анализ. Показано, что сжатие каждого уровня с одной и той же ошибкой 8: Skt=8k^=...-ß0 = S является более эффективным по сравнению с

экспоненциально возрастающей максимально допустимой ошибкой: St=2

Показано, что оптимальным размером блока являются 128x128 и 256x256. Использование блоков размером 64x64 и меньше также возможно, однако сжатие в этом случае оказывается менее эффективным.

Представленный метод иерархического вейвлет-сжатия сокращает объем исходной матрицы высот «Puget Sound» с 512 МБ (16 бит/отсчет) до 18.8 МБ (0.588 bps), то есть более, чем в 27 раз при точности восстановления 1 м, составляющей 0.625 от среднего перепада высот между соседними отсчетами матрицы. Метод C-BDAM (один из наиболее известных) позволяет сжать ту же матрицу до объема 19.5 МБ (0.61 bps). При сжатии с погрешностью, равной точности представления данных (0.1 м), достигается сжатие в 7 раз.

В подразделе 2.4 представлены выводы к главе.

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

В подразделе 3.1 описывается построение усеченного квадродерева текущего представления адаптивной модели. Для визуализации на графическом процессоре с каждой матрицей связывается индивидуальная сетка (блок), представляющая собой множество вершин и построенную на них адаптивную триангуляцию Т™: = Т^}. Для триангулированной сетки Mjfl введено понятие экранной ошибки аппроксимации Егг&г(М^„), как максимального видимого отклонения (в пикселях экрана) на участке местности, аппроксимируемом блоком . Егг&г(М^п) определяется формулой:

Егг(А^)

где у=тах(#л • / 2), Д, •«:/&($?„/2)) - коэффициент, учитывающей размеры области вывода и параметры проецирования, и /?у - горизонтальное и вертикальное разрешения экрана в пикселях, <рк и (ру - углы обзора камеры в горизонтальном и вертикальном направлениях, р(с,В^п) - расстояние от каме-

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

Через S* обозначается срез, задающий усеченное квадродерево с минимальным числом листовых узлов, обеспечивающим допустимое отклонение е упрощенной модели от точной:

5* = {(т,п,к): £/т&,«>) i е лЕгг&г(^„ ,2) > е}. В подразделе 3.2 описывается аппаратно-реализуемый алгоритм построения адаптивных триангуляции для блоков среза S*.

В пункте 3.2.1 представлен метод пофрагментной тесселяции для адаптивной динамической триангуляции блоков. Каждая расширенная матрица высот (содержащая (2Р° +1)х(2л' +1) отсчетов) интерпретируется как сетка одинаковых фрагментов тесселяции размером (2''° +1) х (2d° +1), d0<p0. Каждый фрагмент может быть выведен в разрешении 2d, где d = 1,2, ...,d0. На этапе исполнения при распаковке блока для каждого его фрагмента вычисляется серия ошибок отражающих максимальную погрешность, вносимую данным фрагментом, когда он имеет разрешение d:

= maxp(v,T}d)) + Err(A^n), ¿ = 1,2,...Д,,

где Tfd) - триангуляция рассматриваемого фрагмента тесселяции (г, s), 0<r,s <2p°'da для уровня разрешения 2d, p(v,Tfd)) - вертикальное расстояние от вершины v до триангуляции Tr(d).

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

В пункте 3.2.3 рассматриваются возможности графического конвейера Di-rect3Dll в обеспечении адаптивной триангуляции, а также реализация представленного алгоритма с их помощью. В пункте 3.2.4 представлены детали реализации, способствующие увеличению производительности, а именно: хранение матриц высот, карт нормалей, и ошибок фрагментов тесселяции в виде массивов текстур; визуализация рельефа при помощи техники инстанцирования (instancing); построение системы визуализации по многопоточному асинхронному принципу с предсказанием положения камеры в пространстве.

В пункте 3.2.5. представлены результаты экспериментов по визуализации тестового рельефа в разрешении 1920x1200 на платформе, оснащенной процессором Intel Core i 7 @2.67 ГГц, 6.0 ГБ и графическим процессором NVidia

GTX480. Средняя скорость визуализации составила 607 fps (кадров в секунду) при минимальном значении 465 fps.

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

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

С целью решения задачи в пункте 3.3.1 вводится понятие вычислительного веса поддерева wf?, характеризующего вычислительную сложность обработки поддерева:

где с<'> - вычислительные затраты, связанные с обработкой только данного узла. Вес и^ корневой вершины дерева равен сложности всего дерева.

В пункте 3.3.2 формулируется и доказывается теорема о распределении вычислительных весов нерегулярных иерархических древовидных структур: число первых Г уровней (считая от корня дерева), достаточное для обеспечения заданной неравномерности распределения вычислительной нагрузки <5 по N потокам, зависит только от неравномерности распределения вычислительного веса по ветвям дерева и от числа потоков исполнения И, и не зависит от полной глубины дерева.

Дано конструктивное доказательство теоремы, основанное на понятии неравномерности распределения вычислительного веса, определяемого для каждой вершины как отношение вычислительного веса родительской вершины к весу поддерева, растущего из данного узла:

с)], для листовой вершины

для нелистовой вершины

т,п-0,1

и максимальной величины rjm на пути длины L. Доказано, что

Теорема обосновывает возможность равномерного, с заданной точностью, распараллеливания рекурсивных алгоритмов на усеченном квадродереве для N вычислительных ядер (потоков). Равномерность достигается за счет незначительного объема дополнительных вычислений на небольшом числе верхних уровней квадродерева. Распределение задач выполняется на предварительном этапе, перераспределение на этапе исполнения основного алгоритма отсутствует и позволяет полностью исключить обмен данными между различными потоками исполнения, повысить эффективность распараллеливания. Построенные зависимости позволяют сделать оценки числа уровней для любых N и 5. Так, при распараллеливании алгоритма построения триангуляции на 8 ядрах, значение Г по оценке и в эксперименте не превышало 6 уровней.

В пункте 3.3.3 приведены детали организации данных, повышающие эффективность использования процессорной КЭШ-памяти, что позволяет дополнительно увеличить производительность на 10-15%.

В пункте 3.3.4 представлены результаты вычислительных экспериментов. При запуске на 2-8 потоках исполнения параллельный рекурсивный алгоритм построения триангуляции продемонстрировал ускорение от 1.95 до 6.95 соответственно и эффективность распараллеливания от 0.98 до 0.87.

В подразделе 3.4 представлен согласованный с предложенной моделью подход к фотореалистичному процедурному текстурированию геоповерхности методом комбинирования различных материалов, выполняемого непосредственно на графическом ускорителе. Подход позволяет получать фотореалистичное качество изображения без использования уникальной текстуры, что позволяет свести затраты памяти к минимуму. Приведены результаты исследования производительности системы на рабочей станции, оснащенной процессором Intel Core i7 на частоте 2.67 ГГц, 6.0 Гб ОП и видеокартой среднего класса nVidia GeForce 295 GTX. Скорость визуализации в разрешении HD 1920x1080 пикселей не падала ниже 100 кадров в секунду при максимальной сложности сцены до 1 млн. треугольников / кадр.

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

Комплекс включает в себя:

• библиотеку ТеггаЗБ - основной элемент системы, содержащий компоненты, реализующие алгоритмы построения многомасштабного представления иерархии, построения и визуализации адаптивной модели и т.п.;

• Библиотеку Е1еуайопБа1а8оигсе, реализующую источники данных о рельефе;

• библиотеку ТеггаЕпу, предназначенную для моделирования эффектов среды (солнца, неба, облаков, рассеяния солнечного света и т.п.)

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

Подраздел 3.6 содержит выводы к главе.

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

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

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

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

• в равномерном распараллеливании рекурсивных вычислений, выполняемых на усеченном квадродереве, при исполнении адаптивной триангуляции поверхности на многоядерных центральных процессорах;

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

1) улучшенная технология построения многомасштабного представления данных, включающая:

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

• метод представления иерархии в виде дерева невязок, получаемых вейв-лет-предсказанием отсчетов детальных уровней по отсчетам грубых уровней, позволяющий обеспечить контроль поэлементной ошибки восстановления в метрике Чебышева;

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

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

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

• новым алгоритмом построения адаптивной триангуляции, реализуемым с помощью аппаратных возможностей графических процессоров класса БцесШМ 1, имеющих в своем составе тесселяторы;

• параллельной моделью рекурсивных вычислений на усеченном квадроде-реве для N вычислительных ядер (потоков) центрального процессора;

• согласованным с моделью методом процедурного текстурирования поверхности на основе локальных характеристик местности.

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

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

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

Статьи в изданиях, рекомендованных ВАК

1. Юсов, Е.А. Эффективный аппаратно-реализуемый алгоритм сжатия данных о рельефе / Е.А. Юсов // Веста. Нижегородского гос. университета. Математическое моделирование и оигимальное управление. - 2008. - № 1.- С. 108-117. http://www.unn.ги/е-ПЬгагу/уе5(п1к.Ыт1?апит=1876.

2. Юсов, Е.А. Адаптивная триангуляция ландшафта с представлением квадра-дерева вершинной текстурой и вейвлет-оценкой значимости вершин / Е.А. Юсов, В.Е. Турлапов // Программирование. - 2008. - №5. - С. 1-16. http://www.maik.ru/contents/procom/procom5 8v34cont.htm.

3. Юсов, Е.А. Алгоритм фотореалистичного отображения рельефа путем комбинирования текстур, управляемого локальными особенностями поверхности / Е.А.Юсов // Веста. Нижегородского гос. университета. Математиче-

ское моделирование и оптимальное управление. - 2008. - № 2. - С. 158-165. http://www.unn.ru/e-librarv/vestnik.html7anunFl922.

4. Юсов, Е.А. Эффективное кодирование адаптивной триангуляции рельефа в контексте иерархического вейвлет-сжатия сетки высот / Е.А. Юсов // Вестн. Нижегородского гос. университета. Математическое моделирование и оптимальное управление - № 5 (1). - 2010. - С. 209-219. http://www.unn.ru/e-librarv/vestnik.html?anum=3261.

Публикации в других изданиях

5. Юсов, Е.А. Наследование положения объектов по z-координате в построении трехмерных редакторов и геоинформационных систем / ЕА. Юсов, В.Е. Турлапов // Тезисы докладов VII всероссийской с участием стран СНГ научной конференции «Методы и средства обработки сложной графической информации». - Н.Новгород, 2003. - С. 90-91.

6. Юсов, Е.А. Восстановление рельефа по географической карте и моделирование активной обстановки на основе рельефа / Е.А. Юсов, В.Е. Турлапов // Тезисы докладов VIII всероссийской научной конференции «Методы и средства обработки сложной графической информации». - Н.Новгород, 2005.-С. 99-104.

7. Юсов, Е.А. Динамическая симплификация и визуализация ландшафта на базе DirectX / Е.А. Юсов // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Н.Новгород, 2006. - С. 326-330. http://microsoft.unn.ru/msconf7Conference 2006.pdf.

8. Юсов, Е.А. Динамическая оптимизация ландшафта на базе преобразования Хаара и квадродерева вершин / Е.А. Юсов, В.Е. Турлапов // Труды XVI международной конференции по компьютерной графике и ее приложениям «ГрафиКон'2006». - Новосибирск, 2006. - С. 198-205. http://www.graphicon.ru/2006/proceedings/papers/frl4 36 YusovTurlapov.pdf.

9. Юсов, Е.А. Параллельная модель вычислений для отображения больших участков ландшафта на основе прогрессивного квадродерева и максимального использования графического процессора средствами Microsoft DirectX / Е.А. Юсов // Материалы конференции «Технологии Microsoft в теории и практике программирования». - Н.Новгород, 2007. — С. 316-320. http://www.itlab.unn.ru/archive/MSConf07/MSConf2007.pdf

10. Юсов, Е.А. Построение адаптивной модели рельефа на графическом процессоре средствами Microsoft DirectXlO и шейдеров 4 версии / Е.А. Юсов // Материалы конференции «Технологии Microsoft в теории и практике про-1раммирования». - Н.Новгород, 2008. - С. 362-365. http://www.itlab.unn.ru/archive/MSConf08/Book.pdf

11. Юсов, Е.А. Параллельный алгоритм рекурсивной обработки динамических древовидных структур данных на примере усеченного квадродерева / Е.А. Юсов // Труды III международной научной конференции «Параллельные

Вычислительные Технологии (ПаВТ'2009)». - Н. Новгород, 2009. - С. 787796. http://omeea.sp.susu.ac.ru/books/conference/PaVT2009/papers/short papers/066.pdf.

12. Yusov, Е.А. Relief shape inheritance and graphical editor for the landscape design / E.A. Yusov, V.E. Turlapov // Conf. Proc. of 15th Int. Conf. on Computer Graphics and Applications (GraphiCon'2005). - Novosibirsk, 2005. - P. 170-174. http://www.graphicon.rU/2005/proceedings/napers/Yusov Turlapov.pdf

13. Yusov, E. GPU-optimized efficient quad-tree based progressive multiresolution model for interactive large scale terrain rendering / E. Yusov, V. Turlapov // Conference Proceedings of the 17th international Conference on Computer Graphics and Vision «GraphiCon'2007». - Moscow, 2007. - P. 53-60. http://www.graphicon.ru/2007/proceedings/Papers/Paper 13.pdf.

14. Yusov, E. JPEG2000-based compressed multiresolution model for real-time large scale terrain visualization / E. Yusov, V. Turlapov // Conference Proceedings of the 18th international Conference on Computer Graphics and Vision «Graphi-Con'2008». - Moscow, 2008. - P. 164-171.

http://www.graphicon.ru/2008/procxedmgs/Engnsh/S8/Paper 1 ,pdf>.

15. Yusov, E. Compact compressed terrain representation using joint zero trees of wavelet coefficients for real-time triangulation and rendering / E. Yusov // Conf. proc. Of the LADIS international conf. on сотр. graph., visual., сотр. vision and image proc. CGVCVIP'2010. - Freiburg, Germany, 2010. - P. 165-175. http://www.iadisportal.org/digital-librarv/compact-compressed-terrain-representation-using-ioint-zero-trees-of-wavelet-coefficients-for-real-time-triangulation-and-rendering.

16. Yusov, E. Adaptive Context Modeling for Efficient Image and Elevation Data Compression / E. Yusov II Proc. of the 20th International Conference on Computer Graphics and Vision «GraphiCon'2010». - St. Petersburg, 2010. - P. 22-29. http://www.graphicon.ru/proceedings/2010/Proceedings.pdf.

17. Yusov, E. High-performance terrain rendering using hardware tessellation / E. Yusov, M. Shevtsov // Journal of WSCG ISSN 1213-6972. - Plzen, Czech Republic, 2011. - Vol. 19, No. 3 - P. 85 - 92. http://wscg.zcu.cz/WSCG2011/! 2011 J WSCG l-3.pdf

Подписано в печать 26.05.2011. Формат 60 х 84 Vi6. Бумага офсетная. Печать офсетная. Уч.-изд. л. 1,0. Тираж 100 экз. Заказ 412.

Нижегородский государственный технический университет им. P.E. Алексеева.

Типография НГТУ. Адрес университета и полиграфического предприятия: 603950, г. Нижний Новгород, ул. Минина, 24.

Аннотация

Введение Актуальность темы исследования Цель и задачи исследования Методы исследования Научная новизна работы Практическая значимость исследования Апробация работы, и публикации Структура диссертации

4 9 И

1 Обзор и анализ существующих иерархических алгоритмов сжатия данных и методов многомасштабного моделирования рельефа

1.1 Конструктивные методы на базе хорошо приспособленных базисных функций

1.2 Иерархические алгоритмы сжатия данных на основе вейвлет-преобразования

1.3 Двухэтапные методы сжатия с контролем ошибки в метрике Чебышева 35.

1.4 Методы построения адаптивной триангуляции для визуализации рельефа

1.5 Анализ представленных алгоритмов

Выводы к главе

2 Технология блочно-иерархического вейвлет-сжатия матрицы высот рельефа

2.1 Построение многомасштабной иерархии

2.2 Кодирование квадродерева невязок вейвлет-предсказания

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

2.4 Выводы к главе

3 Высокопроизводительная многомасштабная модель рельефа местности

3.1 Построение усеченного квадродерева текущего представления адаптивной модели

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

3.3 Высокопроизводительная параллельная реализация рекурсивных алгоритмов обработки усеченного квадродерева

3.4 Процедурное текстурирование поверхности на GPU

3.5 Общее описание программного комплекса

3.6 Выводы к главе

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

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

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

Возможным путем решения проблемы является организация хранилища на жестких дисках или внешнем сервере и использование специальных алгоритмов подкачки данных, как, например, в подходах ЕШАМ [65], Р-ВБАМ [66].

Такой метод требует существенных затрат памяти и связан с задержками при { чтении с внешнего устройства или из сети. Значительно снизить расход памяти и объем пересылаемых данных позволяет использование эффективных методов сжатия. Разработка методов компрессии является одним из важнейших направлений современной информатики, существенно зависит от решаемой задачи и актуальна для многих областей, среди которых также: цифровое фото и видео; хранение и обработка данных медицинских исследований; теле- и Интернет-коммуникации; цифровая картография и т.п.

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

Кроме необходимости оперировать большими объемами данных в задаче визуализации рельефа возникает и другая проблема: вычислительная сложность исходной равномерно триангулированной модели оказывается слишком высокой для вывода даже на самых производительных современных графических системах. Таким образом, весьма актуальна задача адаптации модели к особенностям поверхности и параметрам отображения, которая позволит без потери точности задавать плоские и расположенные далеко от камеры участки, большими треугольниками, а области с высокочастотными особенностями, расположенные близко к камере, - используя плотную сетку и триангуляцию. Можно выделить следующие основные требования, которым должна удовлетворять адаптивная модель.триангуляции поверхности рельефа [18, 83,108,119]:

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

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

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

4. Модель должна исключать разрывы в триангулированной поверхности.

5. Локальные высокочастотные особенности, такие как выпуклости или вогнутости, не должны приводить к глобальному увеличению сложности модели.

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

Особое внимание при проектировании многомасштабной модели должно уделяться реализуемости положенных в ее основу принципов на современных аппаратных средствах. Необходимо ориентироваться на обе основные линии развития, декларированные сегодня ведущими производителями аппаратного обеспечения: 1) развитее возможностей дискретных графических процессоров как вычислителей общего назначения, и 2) развитие архитектуры «многоядерный центральный процессор — встроенная графическая карта».

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

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

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

Оптимизировать операции обработки больших объемов данных во многих случаях помогают многомасштабные представления информации. Многомасштабным называют иерархическое представление, описывающее объект в виде последовательности приближений, задающих его с возрастающей степенью точности (разрешением). Такое описание можно понимать как многослойную структуру, первый слой которой задает объект в грубом приближении (с низким разрешением), а каждый последующий слой содержит дополнительную информацию, которая постепенно увеличивает степень детализации до полного восстановления объекта [28]. Многомасштабное представление позволяет извлекать из всей иерархии/аппроксимацию объекта, оптимально соответствующую не только локальным; особенностям его формы и точности: восстановления, но-и« условиям ¿его наблюдения« И' визуализации; Так-, при; обзоре рельефа* местности с большой высоты достаточно отображать его в грубомгразрешении: Если же камера находится близко к поверхности, необходимо использовать детальное приближение. Многомасштабные представления позволяют решать многие другие задачи обработки информации, такие как организация прогрессивной передачи данных (по сети, к примеру), редактирование, различные виды анализа и т.п. Актуален как можно- более полный перевод многомасштабных представлений* на аппаратную основу и формирование, на:основе типовых задач моделирования рельефа, базовой системы команд (операций) графического процессора как специализированного геометрического процессора [40,41].

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

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

Актуальность темы исследования

Разработка эффективных технологий сжатия изображений и другой информации с целью повышения эффективности хранения и передачи, а также методов многомасштабного моделирования объектов различной природы, в том числе и рельефа, отвечающих современному уровню развития вычислительной техники, является активно исследуемой областью как в России, так и за ее пределами. Подтверждением этому является большое количество публикаций, посвященных проблемам сжатия изображений и пространственных данных. Здесь следует отметить работы Ю.Г. Васина, A.B. Кудина, C.B. Жерздева, В.В.Сергеева, В.А.Сойфера, Ю.МТИтарькова, М.Кунта (M.Kunt), Дж. Шапиро (J.Shapiro), А.Саида (A.Said), У.Перельмана (W.Pearlman) и др. Многомасштабным моделям и методам построения адаптивных триангуляций рельефов для их эффективной визуализации также посвящено много работ. В последние годы этой проблемой занимались A.B. Переберин, Ю.М. Баяковский, М.В. Михайлюк, Ю.Г.Васин, А.В.Плесков, H.A. Елыков, И.В. Белаго, В.ДЕрухимов, А.Д. Капустин, Р. Lindstrom, M. Duchaineau, R. Pajaróla, P. Cignoni, F. Ganovelli, F. Losasso, H. Hoppe, A. Asirvatham и др. Тем не менее, с развитием вычислительной техники быстро растут требования к реалистичности выводимой сцены, увеличиваются объемы данных, задающих рельеф местности.

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

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

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

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

Цель и задачи исследования

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

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

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

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

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

• Экспериментально исследовать эффективность комплекса и реализованных в нем моделей и методов.

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

Решение задач диссертационной работы базируется на: методах обработки и сжатия изображений, в том числе теории вейвлет-преобразований; теории информации; теории вероятностей; теоретических основах аналитической геометрии; методах компьютерной графики; методах параллельных вычислений. Теоретической базой настоящего исследования явились основополагающие работы: отечественных ученых - Ю.Г.Васина, В.В.Сергеева, В.А.Виттиха, В.А.Сойфера и их учеников, а также зарубежных ученых - М.Кунта (М.Кип1), У.К. Прэтга ^.К.Ргай), И.Добеши (1.БаиЬесЫез), Дж. Шапиро (1.8Ьарко), У.Перельмана (\¥.Реаг1тап), П.Линдстрома (Р.ИлпсЫгот) и др.

Научная новизна работы

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

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

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

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

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

Модель оформлена в виде набора библиотек СОМ-компонентов (по аналогии с MS DirectX) и готова к практическому использованию в подсистемах визуализации местности таких приложений как авиасимуляторы, геоинформационные системы и т.д. Модель внедрена в корпорации Интел; в ВИИ Системных Исследований РАН в виде компонентов методического и программного обеспечения системы, предназначенной для визуализации земной поверхности (поверхности планеты) в тренажерах аэрокосмического назначения; использована институтом машиноведения УрО РАН, а также включена в виде лабораторной работы по моделированию рельефа в учебно-методический .комплекс «Компьютерная графика», разработанный в 2007 году при поддержке государства (государственный контракт № 4016р/6181) для свободного распространения,в вузах России. Результаты использованы во Всероссийской научной школе для молодежи. «Компьютерное зрение, 3D моделирование И'компьютерная-графика» 2010года (госконтракт №02.741.12.2170).

Достоверность результатов работы подтверждена ¡компьютерными экспериментами по моделированию конкретных участков земной поверхности, заданных равномерной матрицей высот (рельеф гор Кавказа, прилегающая территория горы Puget Sound, рельеф Великого Каньона США и др.).

Апробация работы и публикации

Основные результаты работы доложены и обсуждены на: международной-конференции по компьютерной графике, визуализации и компьютерному зрению WSCG2011 (Пльзень, Чехия, 2011); международной конференции по компьютерной графике, визуализации, компьютерному зрению и обработке изображений CGVCVIP'2010 (Фрейбург, Германия, 2010); международных конференциях по компьютерной графике и визуализации - GraphiCon (Новосибирск, 2005, 2006; Москва, 2007, 2008; Санкт-Петербург, 2010); международной'научной конференции «Параллельные Вычислительные Технологии (ПаВТ'2009)»; всероссийских конференциях «Технологии Microsoft в теории и практике программирования» (Нижний Новгород, 2006, 2007, 2008 — дипломы I степени на конкурсах, проводимых в рамках конференций); всероссийской конференции по параллельным вычислениям (Нижний Новгород, 2008); всероссийских конференциях «Методы и средства обработки сложной графической информации»

Нижний Новгород, 2005, 2006); семинарах кафедры МО ЭВМ факультета ВМК ННГУ.

Лабораторная работа по моделированию рельефа внедрена в курсе «Компьютерная графика» на факультете ВМК ННГУ, использована в образовательном проекте Intel Studio Graphics 2008, во Всероссийской научной школе для молодежи «Компьютерное зрение, 3D моделирование и компьютерная графика» 2010 года (госконтракт №02.741.12.2170). Результаты работы использованы корпорацией-Интел, НИИ4 Системных Исследований РАН, а также институтом машиноведения УрО РАН. Работа также прошла конкурсный отбор для участия в программе У.М.Н.И.К (госконтракт №7095р/9642).

Основные результаты, полученные в процессе выполнения работы, опубликованы в 17 работах, из них 4 — публикации в изданиях, рекомендованных ВАК.

Структура диссертации

Диссертация состоит из введения, 3 глав и заключения.

3.6 Выводы к главе 3

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

Предложен новый метод построения триангуляции поверхности? отличающийся тем, что алгоритм построения реализуется непосредственно на GPU и использует аппаратные возможности графических процессоров последнего поколения, имеющих в своем составе тесселяторы (т.е. класса Direct3E>H)- Метод позволяет многократно снизить нагрузку на центральный процессор, многократно уменьшить объем пересылаемых по шине данных и достичг»? таким образом, наибольшей производительности визуализации.

Предложена высокопроизводительная реализация модели, ориентированная на сочетание многоядерного центрального процессора и встроенной; видеокарты, для которой теоретически обоснована возможность равномерного с за~ данной точностью, распараллеливания рекурсивных алгоритмов триангуляции и восстановления поверхности на усеченном квадродереве для N вычислительных ядер (потоков) за счет незначительных дополнительных вычислены*1 на не~ большом числе верхних уровней квадродерева; показано, что время работы алгоритма распределения вычислительной нагрузки между потоками не: зависит от глубины* исходного дерева, а определяется только точностью распре^Деления нагрузки. При запуске на 2-8 потоках исполнения рекурсивный алгорГ^™ "Ч511-ангуляции и восстановления поверхности демонстрирует ускорение, соответственно, от 1.95 до 6.95 и эффективность распараллеливания от 0.98 до О.^^

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

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

Заключение

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

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

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

• в равномерном распараллеливании рекурсивных вычислений, выполняемых на усеченном квадродереве, при исполнении адаптивной триангуляции поверхности на многоядерных центральных процессорах;

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

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

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

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

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

1. Васин, Ю.Г. Кодирование ЭКГ неравномерными отсчетами / Ю.Г. Васин // Сборник «Биологическая и медицинская кибернетика», ч.4. М., 1974. - С. 7374.

2. Васин, Ю.Г. Хорошо приспособленные базисы и задачи обработки экспериментальной информации / Ю.Г. Васин. — Горький: ГГУ, 1979.

3. Васин, Ю.Г. Хорошо приспособленные локальные однородные методы обработки графической информации / Ю.Г. Васин // Автоматизация обработки сложной графической информации: Межвуз. сб. Горький: ГГУ, 1984.

4. Васин, Ю.Г. Эффективность различных стратегий обработки видеоинформации на базе локальных однородных рекуррентно-рекурсивных функций / Ю.Г. Васин // Методы и средства обработки графической информации: Межвуз. сб. Горький: ГТУ, 1986. - С. 4-47.

5. Васин, Ю.Г. Рекуррентные алгоритмы адаптивного сжатия с использованием хорошо приспособленных локальных восстанавливающих функций / Ю.Г. Васин, В.П. Бакараева // Математическое обеспечение САПР: Межвуз. сб. -Горький: ГГУ, 1978.-Вып. 1.

6. Васин, Ю.Г. Технология иерархического кодирования видеоинформации / Ю.Г. Васин, C.B. Жерздев // Труды 12 международной конференции по комп. граф. «ГрафиКон'2002». Н. Новгород, 2002.

7. Васин, Ю.Г. Эффективное кодирование усеченных двоичных деревьев в задаче сжатия изображений / Ю.Г. Васин, C.B. Жерздев // Труды 6-й конференции «Методы и средства обработай сложной графической информации». — Н. Новгород, 2001. С. 36-38.

8. Васин, Ю.Г. Метод от общего к частному при решении пространственных задач дискретной геометрии / Ю.Г. Васин, А.Д. Крахнов, Т.Ш. Утешева // Автоматизация обработки сложной графической информации: Межвуз. сб. — Горький: ГТУ, 1988. С. 73-83.

9. Ватолин, Д. Эффективный метод сжатия видео без потерь / Д. Ватолин, Д. Попов // Материалы конференции «ГрафиКон'2004». — Москва, 2004.

10. Ватолин, Д.С. Гибридная^ схема фрактальной компрессии и квантования векторов для малых блоков / Д.С. Ватолин // Материалы 8 международной конференции по комп. граф. и визуал. «ГрафиКон'98». — Москва, 1998.

11. Ватолин, Д.С. Увеличение степени компрессии фрактального сжатия путем указания качества участков изображения / Д.С. Ватолин // Материалы 9 международной конф. по комп. граф. и видению «ГрафиКон'99». — Москва, 1999.

12. Воеводин, В.В. Параллельные вычисления / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург. - 2002. - 608 с.

13. Воробьев, В.И. Теория и практика Вейвлет-преобразования / В.И. Воробьев, В.Г. Грибунин. С.Петербург, 1999.

14. Гашников, М.В. Иерархическая компрессия изображений в системах реального времени / М.В. Гашников, Н'.И. Глумов, В.В. Сергеев // Научно-теоретический журнал "Искусственный интеллект" (Украина), 2003. — №3. — С. 218-222.

15. Добеши, И. Десять лекций по вейвлетам / И. Добеши. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.

16. Елыков, H.A. Методы непрерывной детализации террэйна / H.A. Елыков, И.В. Белаго, С.А. Кузиковекий, Ю.Ю. Некрасов-// Материалы конф. по комп. граф. и визуализации «ГрафиКон'2002». Н. Новгород, 2002.

17. Ерухимов, B.JI. Реализация алгоритма визуализация местности в режиме реального времени / Ерухимов B.JL, А.Д. Капустин, A.B. Малашкина // Материалы конф. по комп. граф. и визуализации «ГрафиКон'99». — Москва, 1999. — С.110-116.

18. Кудин, A.B. Алгоритм RRE-кодирования технических, изображений / A.B. Кудин, C.B. Жерздев // Вестн. Нижегородского университета. Математическое моделирование и оптимальное управление. Н. Новгород. Изд-во ННГУ, 1998. -Вып. 2 (19).

19. Методы компьютерной обработки изображений / Под. ред. В.А.Сойфера. — 2-е изд., испр. М.: ФИЗМАТЛИТ, 2003. - 784 с. - ISBN 5-922-0270-2.

20. Михайлюк, М.В. Компьютерная графика в видеотренажерах / М.В. Михай-люк, В.И. Якунин // Материалы конференции «ГрафиКон'2002». — Н. Новгород, 2002.

21. Неймарк, Ю.И. Кодирование больших массивов информации в связи с задачами распознавания образов / Ю.И. Неймарк, Ю.Г. Васин. Изв. вузов. Радиофизика, 1968.-С. 1081-1085.

22. Нетравали, А. Кодирование изображений: Обзор / А. Нетравали, Дж. Лимб // ТИИЭР. 1980. - № 3. - С. 76-94.

23. Переберин, A.B. Многомасштабные методы синтеза и анализа изображений: дис. . канд. физ.-мат. наук 05.13.11 / Переберин Антон Валерьевич; Ин-т прикладной математики им. М.В. Келдыша. Москва, 2002. - 138 с.

24. Переберин, A.B. О систематизации вейвлет-преобразований / A.B. Переберин // Вычислительные методы и программирование. — 2001. Т. 2, № 2. — С. 133-158.

25. Сергеев, В.В. Метод контроля максимальной ошибки компрессии / В.В. Сергеев, Е.И. Тимбай // Компьютерная оптика. — 2007. -Т. 31, №3. С. 83-85.

26. Сетка высот территории горы Puget Sound Электронный ресурс] / Режим доступа: http://www.cc.gatech.edu/projects/large models/ps.html, свободный.

27. Смоленцев, Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB / Н.К. Смоленцев. М.: ДМК Пресс, 2005. - 304 с.

28. Снук, Г. Создание ЗБ-ландшафтов в реальном времени с использованием С++ и DirectX 9 / Г. Снук // Пер. с англ. М.: КУДИЦ-ОБРАЗ, 2006. - С. 194215.

29. Столниц, Э. Вейвлеты в компьютерной графике. Теория и приложения / Э. Столниц, Т. ДеРоуз, Д. Салезин. — Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002.

30. Тетенев, Е.В. Навигация в реальном времени над моделью местности неограниченного размера / Е.В. Тетенев // Материалы 16-й» международной конференции по комп. граф. «ГрафиКон'2006». — Новосибирск, 2006.

31. Тимошевская, Н.Е. Параллельные методы обхода дерева / Н.Е. Тимошев-ская // Математическое моделирование. Томск. — 2004. №1.- С. 105-114.

32. Турлапов, В.Е. Аксиоматический подход в вычислительной геометрии / В.Е. Турлапов, В.И. Якунин // Конструирование поверхностей и их технические приложения: Тем. сб. науч. тр. МАИ. — М.: Изд-во МАИ, 1992. С. 42-46.

33. Турлапов, В.Е. Проблема построения геометрического процессора и ее решение / В.Е. Турлапов, В.И. Якунин // Компьютерная геометрия и графика в инженерном образовании: Матер, всесоюзн. конф. — Нижегор. политехи, ин-т. — Н. Новгород, 1991.-С. 146/

34. Юнаковский, А.Д. Теория вейвлетов: Учебно-методическое пособие / А.Д. Юнаковский. Н. Новгород: Изд-во Нижегородского гос. университета, 2008. — 122 с.

35. Adams, M. The JPEG-2000 Still Image Compression Standard / M. Adams. -Tech. Rep. N2412, ISO/IEC JTC 1/SC 29/WG 1. Sept. 2001.

36. Ahmed, N. Discrete Cosine Transform / N. Ahmed, T. Natrajan, K.R. Rao // IEEE Trans. Computers. -1974. Vol. 23, No. 1. - P. 90-93.

37. Andrew, J. A simple and efficient hierarchical image coder / J. Andrew // ICIP'97. 1997. - Vol. 3. - P. 658-661.

38. Ansari, R. Near-lossless image compression techniques / R. Ansari, N. Memon, E. Ceran // J. Electronic Imaging. Jul. 1998. - Vol. 7. - P. 486-494.

39. Antal, G. Fast Evaluation of Subdivision Surfaces on Direct3D10* Graphics Hardware / G. Antal, L. Szirmay-Kalos // Shader X6 Advanced rendering techniques. Charles River Media, 2008. - P. 5-16.

40. Antonini, M. Image coding using wavelet transform / M. Antonini, M. Barlaud, P. Mathieu, I. Daubechies // IEEE Trans. Image Proc. 1992. - Vol. 1, No. 2. - P. 205-220.

41. Asirvatham, A. Terrain Rendering Using GPU-Based Geometry Clipmaps / A. Asirvatham, H. Hoppe // GPU Gems 2. Addison-Wesley, 2005. - P. 27-46.

42. Bayazit, U. Algorithmic Modifications to SPIHTIU. Bayazit, W.A. Pearlman // IEEE Int. Conf. on Image Proc. (ICIP 2001). Thessaloniki, Greece., Oct. 2001.

43. Blythe, D. The Direct3D 10 System / D. Blythe // SIGGRAPH 2006 Proceedings. 2006. - P. 724-734.

44. Brettell, N. Terrain Rendering Using Geometry Clipmaps / N. Brettell. — Nov. 10, 2005. http://www.cosc.canterbury.ac.nz/research/reports/HonsReps/2005/hons 0502.pdf

45. Cho, Y. Hierarchical Dynamic Range Coding of Wavelet Subbands for Fast and Efficient Image Compression / Y. Cho, W.A. Pearlman // IEEE Trans, on Image Processing. Aug. 2007. - Vol. 16, No. 8. - P. 2005-2015.

46. Chiysafis, G. Efficient Context-Based Entropy Coding for Lossy Wavelet Image Compression / C. Chiysafis, A. Ortega // Proceedings of the Conference on Data Compression. March 25-27, 1997. - P. 241-250.

47. Cignoni, P. BDAM Batched Dynamic Adaptive Meshes for, High Performance Terrain Visualization / P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, R. Scopigno //Computer Graphics Forum. - 2003. - Vol. 22, No. 3. - P. 505-514.

48. Cignoni, P. Planet-Sized Batched Dynamic Adaptive Meshes (P-BDAM) / P. Cignoni, F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, R: Scopigno // IEEE Visualization.-2003.-P. 147-154.

49. Cignoni, P. A comparison of mesh simplification algorithms / P. Cignoni, C. Montani, R. Scopigno // Computers & Graphics. 1998. - Vol. 22, No. 1. - P. 3754.

50. Cignoni, P. Representation and visualization of terrain surfaces at variable resolution / P. Cignoni, E. Puppo, R. Scopigno // The Visual Computer. 1997. - Vol. 13, No. 5.-P. 199-217.

51. Clasen, M. Terrain Rendering using Spherical Clipmaps / M. Clasen, H. Hege // Eurographics / IEEE-VGTC Symposium on Visualization. 2006. http://www.zib.de/clasen/download/SphericalClipmaps Electronic.pdf

52. Cohen, A. Bi-orthogonal bases of compactly supported wavelets / A. Cohen, I. Daubechies, J. Feauveau // Comm. Pure Appl. Math. 1992. - Vol. 45. - P. 485-560.

53. Cohen, M. Wang Tiles for Image and Texture Generation / M. Cohen, J. Shade, S. Hiller, O. Deussen // ACM Transactions on Graphics. 2003. - Vol. 22, No. 3. -P. 287-294.

54. Dachsbacher, C. Cached procedural textures for terrain rendering / C. Dachsbacher, M. Stamminger // Shader X4 Advanced rendering techniques. Charles River Media, 2006. - P. 457-466.

55. De Floriani, L. A pyramidal data structure for triangle-based surface description / L. De Floriani // IEEE Computer Graphics & Applications. 1989. - Vol. 9, No.2. -P. 67-78.

56. De Floriani, L. Building and traversing a surface at variable resolution / L. De Floriani, P. Magillo, E. Puppo // IEEE Visualization. 1997. - P. 103- 110.

57. De Floriani, L. Multiresolution models for topographic surface description / L. De Floriani, P. Marzano, E. Puppo // The Visual Computer. 1996. - Vol. 12, No. 7. -P. 317-345.

58. De Floriani, L. Hierarchical triangulation for multiresolution surface description. / L. De Floriani, E. Puppo // ACM Transactions on Graphics. 1995. — Vol. 14, No. 4.-P. 363^11.

59. DeCoro, C. Implementing Real-Time Mesh Simplification Using the GPU / C. DeCoro, N. Tatarchuk // Shader X6 Advanced rendering techniques. Charles River Media, 2008.-P. 29-39.

60. Delaunay, B. Sur la sphère vide. A la memoire de Georges Voronoi. Izv. Akad. Nauk S S SR, Otdelenie Matematicheskih i Estestvennyh Nauk / B. Delaunay. 1934. 7:793-800. Translated as Bull. Acad. Sei. USSR: Class. Sei. Math. Nat.

61. DeVore, R. Image compression through wavelet transform coding / R. DeVore, B. Jawerth, B. Lucier // IEEE Transactions on Information Theory. 1992. - Vol. 39, No. 2.-P. 719-746.

62. Dick, C. Efficient Geometry. Compression for GPU-based Decoding in Realtime Terrain Rendering / C. Dick, J. Schneider, R. Westermann // Computer Graphics Forum. 2009. - Vol. 28, No 1. - P. 67-83.

63. Ebrahimi, F. JPEG vs. JPEG2000: An objective comparison of image encoding quality / F. Ebrahimi, M. Chamik, S. Winkler // Proc. SPIE Applications of Digital Image Processing. Denver, CO, August 2-6,2004. - Vol. 5558 - P. 300-308.

64. Gerasimov, P. Shader Model 3.0: Using Vertex Textures / P. Gerasimov, R. Fernando, S. Green // NVIDIA white paper DA-01373-001v00. June, 2004. http.y/developer.nvidia.com/obiect/using vertex textures.html

65. Gerstner, T. Multiresolution visualization and compression of global topographic data: Technical Report 29 / T. Gerstner. Institut für Angewandte Mathematik, Universität Bonn, 1999.

66. Gobbetti, E. C-BDAM Compressed Batched Dynamic Adaptive Meshes for Terrain Rendering / E. Gobbetti, F. Marton, P. Cignoni, M. Di Benedetto, F. Gano-velli // Computer Graphics Forum. - 2006. - Vol. 25, No 3.

67. Gray, K. The JPEG2000 Standard / K. Gray. Technische Universität München Lehrstuhl fur Kommunikationsnetze. München, Feb. 18,2003. http://omen.cs.uni-magdeburg.de/itiamsl/cms/upload/lehre/winter06 07/content.pdf.

68. Gribb, G. Fast Extraction of Viewing Frustum Planes from the World-View-Projection Matrix. / G. Gribb, K. Hartmann. 2001.thttp://www2.ravensoft.com/users/ggribb/plane%20extraction.pdf.

69. Gross, M. Fast multiresolution surface meshing / M. Gross, R. Gatti, O. Staadt // Proceedings Visualization 95. IEEE Computer Society Press, 1995. - P. 135-142.

70. Gross, M. Fast multiresolution surface meshing / M. Gross, R. Gatti, O. Staadt // Proc. of 14th International Conf. on Data Engineering, ICDE'98. IEEE. 1998. - P. 550-557.

71. Gross, M.H. Efficient Triangular Surface Approximations Using Wavelets and Quadtree Data Structures / M.H. Gross, O.G. Staadt, R. Gatti // IEEE Trans, on Visualization and Computer Graphics. -1996. Vol. 2, No. 2. - P. 130-143.

72. Heckbert, P. Survey of polygonal surface simplification algorithms / P. Heckbert, P. Garland // SIGGRAPH 97 Course Notes 25. 1997.

73. Hoffman, N. Rendering Outdoor Light Scattering in Real Time / N. Hoffman, A. Preetham. 2002.http://developer.amd.com/media/gpu assets/ATI-LightScattering.pdf.

74. Hoppe, H. Progressive meshes / H. Hoppe // Proceedings SIGGRAPH 96. -ACM SIGGRAPH, 1996. P. 99-108.

75. Hoppe, H. Smooth view-dependent level-of-detail control and its application to terrain rendering / H. Hoppe // Proceedings Visualization 98. — IEEE, Computer Society Press, Los Alamitos, California, 1998. — P. 35-42.

76. Huffman, D.A. A method for the reconstruction of minimum redundancy codes / D.A. Huffman // Proc. of the Institute of the Electrical and Radio Engineers. — 1952. -Vol. 40,No. 9.-P. 1098-1101.

77. Hwa, L. Adaptive 4-8 Texture Hierarchies / L. Hwa, M. Duchaineau, K. Joy // Proc. IEEE Visualization'04. 2004. - P. 219-226.

78. Islam, A. An embedded and efficient low-complexity hierarchical image coder / A. Islam, W.A. Pearlman // VCIP'99. San Jose, CA, 1999. - Vol. 3653. - P. 294305.

79. Jawerth, B. An Overview of Wavelet Based Multiresolution Analyses / B; Ja-werth, W. Sweldens// SIAM Rev. 1994. - Vol. 36, No. 3. - P. 377^-412.

80. Kovacevic, J. Wavelet families of.increasing order in arbitrary dimensions,/ J. Kovacevic, W. Sweldens // IEEE Transactions on Image Processing. 2000: — Vol. 9, No. 3.-P. 480-496.

81. Lario, R. HyperBlock-QuadTIN: Hyper-Block Quadtree based Triangulated Irregular Networks / R. Lario, R. Pajarola, F. Tirado // IASTED International Conf. on Visualization, Imaging and Image Processing (VHP 2003). -2003. P. 733-738.

82. Larsen, B. Real-time Terrain Rendering using Smooth Hardware Optimized Level of Detail / B. Larsen, N. Christensen // Journal of WSCG. WSCG'2003, February 3-7, Plzen, Czech Republic, 2003. - Vol. 11, No. 1.

83. Lee, J. Comparison of existing methods for building triangular irregular network models of terrain from grid digital elevation models / J. Lee // International Journal of Geographic Information Systems. 1991. - Vol. 5, No. 3. - P. 267-285.

84. Lefebvre, S. Filtered Tilemaps / S. Lefebvre // Shader X6 Advanced rendering techniques. Charles River Media, 2008. - P. 63-71.

85. Levenberg, J. Fast View-Dependent Level-of-Detail Rendering Using Cached Geometry / J. Levenberg // Proc. IEEE Visualization'02. IEEE, 2002. - P. 259-266.

86. Lindstrom, P. Real-time, continuous level of detail rendering of height fields / P. Lindstrom, D. Koller, W. Ribarsky, L.F. Hodges, N. Faust, G.A. Turner // Proceedings SIGGRAPH 96. ACM SIGGRAPH, 1996. - P. 109-118.

87. Lloyd, S.P. Least Squares Quantization in PCM / S.P. Lloyd // IEEE Transactions on Information Theory. 1982. - Vol. IT-28. - P. 129-137.175

88. Losasso, F. Geometry Clipmaps: Terrain Rendering Using Nested Regular Grids / F. Losasso, H. Hoppe // ACM Transactions on Graphics (Proceedings of SIG-GRAPH 2004). 2004. - Vol. 23, No. 3. - P. 769-776.

89. Luebke, D. A developer's survey of polygonal simplification algorithms / D. Luebke // IEEE Comp. Graph. & Applications. 2001. - Vol. 21, No. 3. - P. 24-35.

90. Mallat, S. Multiresolution Approximation and Wavelet Othonormal Bases L2(R) / S. Mallat // Trans. AMS. 1989. - Vol. 1, No. 315. - P. 69-87.

91. Malvar, H. Fast Progressive Image Coding without Wavelets / H. Malvar // Data Compression Conference (DCC '00). 2000. - P. 243-252.

92. Max, J. Quantizing for Minimum Distortion / J. Max // IRE Transactions on Information Theory. 1960. - Vol. IT-6. - P. 7-12.

93. Melax, S. Simple, Fast and Effective Polygon Reduction Algorithm / S. Melax // Game Developer Magazine. 1998. - P. 44-49.

94. NVidia White Paper. NVIDIA's Next Generation CUDA™ Compute Architecture: Fermi™.http://www.nvidia.com/content/PDF/fermi white^)apers/NVIDIA Fermi Compute Architecture Whitepaper.pdf.

95. Oliver, J. Fast and efficient spatial scalable image compression using wavelet lower trees / J. Oliver, M.P. Malumbres // Proc. 2003 IEEE Data Compression Conference.-2003.-P. 133-142.

96. Pajarola, R. Large scale terrain visualization using the restricted quadtree triangulation / R. Pajarola // Proceedings Visualization 98. IEEE Computer Society Press, 1998. - P. 19-26 and 515.

97. Pajarola, R. Overview of quadtree-based terrain triangulation and visualization: Technical Report UCI-ICS-02-01, I&C Science / R. Pajarola. University of California Irvine, 2002.

98. Pajaróla, R. QuadTIN: Quadtree based Triangulated Irregular Networks / R. Pajaróla, M. Antonijuan, R. Lario // Proceedings IEEE Visualization 2002. IEEE Computer Society Press, 2002. - P. 395-402.

99. Pajaróla, R. Survey on Semi-Regular Multiresolution Models for Interactive Terrain Rendering / R. Pajaróla, E. Gobbetti. The Visual Computer. - 2007. - Vol. 23,No. 8.-P. 583-605.

100. Pangerl, D. Quantized. Ring Clipping / D. Pangerl // Shader X6 Advanced rendering techniques. Charles River Media, 2008. - P. 133—140¿

101. Pomeranz, A. ROAM Using Surface Triangle Clusters (RUSTiC). Master's thesis / A. Pomeranz. — University of California at Davis, 2000.

102. Preetham, A. A Practical Analytic Model for Day-light / A. Preetham, P. Shirley, B. Smits // Siggraph proceedings. — 1999.

103. Puppo, E. Variable resolution terrain surfaces / E. Puppo // Proceedings of the 8th Canadian Conference on Computational Geometry. 1996. - P. 202-210.

104. Rissanen, J. Universal modeling and coding / J. Rissanen, G. Langdon // IEEE Trans. Inf. Theory IT-27. 1981. - P. 12-23.

105. Sadashivappa, G. Evaluation of Wavelet Filters for Image Compression / G. Sadashivappa, K. AnandaBabu // Proceedings of ICIPA2009 International Conference on Image Processing and analysis. — Hong Kong. - 2009.

106. Said, A. A new fast and efficient image codec based on set partitioning in hierarchical trees / A. Said, W. Pearlman // IEEE Trans. Circuits Syst. Video Technol. — 1996. Vol. 6, No 3. - P. 243-250.

107. Schneider, J. GPU-Friendly High-Quality Terrain Rendering / J. Schneider, R. Westermann // Journal of WSCG ISSN 1213-6972. Plzen, Czech Republic, 2006. -Vol. 14.

108. Shannon, C.E. A mathematic theory for communication / C.E. Shannon. — Bell Syst. Tech. J., 27, Jul. 1948. P. 298-403.

109. Shapiro, J.M. Embedded Image Coding Using Zerotrees of Wavelet Coefficients / J.M. Shapiro // IEEE Transactions on Signal Processing. 1993. - Vol. 41, No 12.-P. 345-362.

110. Sivan, R. Algorithms for constructing quadtree surface maps / R. Sivan, H. Samet // Proc. of the 5th Int. Symposium on Spatial Data Handling. 1992. - P. 361370.

111. Stollnitz, E. Wavelets for Computer Graphics. Theory and applications / E. Stollnitz, T. DeRose, D. Salesin. San Francisco: Morgan Kaufmann, 1996.

112. Tanner, C. The clipmap: A virtual mipmap / C. Tanner, C. Migdai; M. Jones // ACM SIGGRAPH. 1998. - P. 151-158.

113. Tian, J. Embedded image coding using wavelet difference reduction / J. Tian, R.O. Wells, Jr. // Wavelet Image and Video Compression. Academic Publ., Nor-well, MA, 1998. - P. 289-301.

114. Torchelsen, R. Practical Geometry Clipmaps for Rendering Terrains in Computer Games / R. Torchelsen, L. Joâo, R. Comba // Shader X6 Advanced rendering techniques. Charles River Media, 2008. - P. 103-114.

115. Ulrich, T. Rendering massive terrains using chunked level of detail control / T. Ulrich // SIGGRAPH Course Notes. 2002.

116. Ulrich, T. Rendering massive terrains using chunked level of detail / T. Ulrich // ACM SIGGRAPH Course "Super-size it! Scaling up to Massive Virtual Worlds". -2000.

117. Vanëk, J. Real Time Terrain visualization on PC / J. Vanëk, B. Jezek // Proc. of the 12th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision'2004 «WSCG'2004». 2004.

118. Vasin, Ju. Information Techniques for Hierarchical Image Coding / Ju. Vasin, S. Zherzdev // Pattern Recognition and Image Analysis. 2003. - Vol. 13, No. 3. — P. 539-548.

119. Vasin, Ju. Interpolation in the Hierarchical Coding of Images / Ju. Vasin, S. Zherzdev // Pattern Recognition and Image Analysis. 2003. - Vol. 13, No. 1. -P.179-181.

120. Villasenor, J. Wavelet Filter Evaluation for Image Compression / J. Villasenor, B. Beizer, J. Liao II IEEE Trans. Image Processing. 1995. - Vol. 2. - P. 1053-1060.

121. Von Herzen, B. Accurate triangulations of deformed, intersecting surfaces / B. Von Herzen, A.H. Barr // Proceedings SIGGRAPH'87. ACM Journal Computer Graphics. ACM SIGGRAPH, 1987. - No. 4. - P. 103-110.

122. Vyatkin, S. Voxel-Based Terrain Generation Using Scalar Perturbation Functions / S. Vyatkin, B. Dolgovesov // Conference Proceedings of the 13th international Conference on Computer Graphics «GraphiCon'2003» -Moscow, 2003.

123. Walker, J.S. A lossy image codec based on adaptively scanned wavelet difference reduction / J.S. Walker // Optical Eng. 2000. - Vol. 39, No. 7. - P. 1891-1897.

124. Weinberger, M. The LOCO-I1 lossless image compression algorithm: principles and standardization into JPEGLS / M. Weinberger, G. Seroussi, G. Sapiro // IEEE Trans. Image Processing. 2000. - Vol. 9 - P. 1309-1324.

125. Wheeler, F.W. SPIHT Image Compression without Lists / F.W. Wheeler, W.A. Pearlman // IEEE Int. Conf. on Acoustics, Speech and Signal Processing (ICASSP 2000). Istanbul, Turkey, 2000.

126. Williams, L. Pyramidal parametrics / L. Williams // ACM SIGGRAPH. 1983. -P. 1-11.

127. Witten, I.H. Arithmetic coding for data compression / I.H. Witten, R.M. Neal, J.G. Cleary // Comm. ACM. -1987. Vol. 30, No. 6. - P. 520-540.y

128. Wojtaszczyk, P. A Mathematical Introduction to Wavelets / P. Wojtaszczyk. -Cambridge: Cambridge University Press, 1997.

129. Wong, T. Shader Implementation of Discrete Wavelet Transform / T. Wong, C. Leung // Shader X4. Advanced rendering techniques. Charles River Media, 2006.

130. Wu, X. High-order context modeling and embedded conditional entropy coding of wavelet coefficients for image compression / X. Wu // Proc. ACSSC. Nov. 1997.

131. Wu, X. Context-based, adaptive, lossless image coding / X. Wu, N.D. Memon-// IEEE Trans. Commun. -1997. Vol. 45, No. 4. - P. 437-444.

132. Yea, S. A wavelet-based two-stage near-lossless coder / S. Yea, W. Pearlman // Proc. ICIP. 2004. - P. 2503-2506.

133. Yusov, E. Adaptive Context Modeling for Efficient Image and Elevation Data Compression / E. Yusov // Proc. of the 20th International Conference on Computer Graphics and Vision «GraphiCon'2010». St. Petersburg, 2010. - P. 22-29.

134. Yusov, E. High-performance terrain rendering using hardware tessellation / E. Yusov, M. Shevtsov // Journal of WSCG ISSN 1213-6972. Plzen, Czech Republic, 2011.-Vol. 19, No. 3-P. 85-92.

135. Yusov, E. GPU-optimized efficient quad-tree based progressive multiresolution model for interactive large scale terrain rendering / E. Yusov, V. Turlapov // «Gra-phiCon'2007» Conf. Proceedings. Moscow, 2007. - P. 53-60.