Модели и алгоритмы многомасштабного представления данных для высокопроизводительной визуализации геоповерхностей тема диссертации и автореферата по ВАК РФ 05.13.17, кандидат технических наук Юсов, Егор Александрович

• Юсов, Егор Александрович
• кандидат технических наук
• 2011

Оглавление диссертации кандидат технических наук Юсов, Егор Александрович

Аннотация

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

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

Список литературы диссертационного исследования кандидат технических наук Юсов, Егор Александрович, 2011 год

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.