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

Российская Академия Наук Институт прикладной математики им. М.В. Келдыша

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

Переберин Антон Валерьевич

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

Специальность 05.13.11 — математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

АВТОРЕФЕРАТ

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

Москва — 2002

Диссертация выполнена в Институте прикладной математики им. М.В. Келдыша РАН.

Научный руководитель — кандидат физико-математических наук Юрий Матвеевич Баяковский.

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

- доктор физико-математических наук, профессор Александр Константинович Платонов,

- кандидат физико-математических наук Андрей Серджевич Крылов.

Ведущая организация — Механико-математический факультет МГУ им. М.В. Ломоносова (Москва).

Защита состоится 16 апреля 2002 г. в II00 на заседании диссертационного совета Д 002.024.01 ИПМ им. М.В. Келдыша РАН в конференц-зале Института (125047, Москва, Миусская пл., 4).

С диссертацией можно ознакомиться в библиотеке ИПМ им. М.В. Келдыша РАН.

Автореферат разослан «_»_ 2002 г.

Ученый секретарь диссертационного совета доктор физико-математических наук

Т.А. Полилова

Общая характеристика работы Актуальность работы

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

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

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

Цель работы

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

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

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

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

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

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

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

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

Результаты работы докладывались и обсуждались на:

• 10-й международной конференции по компьютерной графике и машинному зрению GraphiCon'2000 "Fast Multi-Scaled Texture Generation and Rendering" («Быстрая многоуровневая генерация и отображение текстур»), Россия, Москва, 2000;

• 9-й международной конференции по компьютерной графике и машинному зрению GraphiCon'99 "Hierarchical Approach for Texture Compression" («Иерархический подход к сжатию текстур»), Россия, Москва, 1999;

• 7-й международной конференции по компьютерной графике и машинному зрению GraphiCon'97 "From Photon Map to Irradiance Function via Wavelet Transform" («От фотонных карт к функции освещенности через вейвлет-преобразование»), Россия, Москва, 1997;

• семинаре по компьютерной графике и обработке изображений Ю.М. Ба-яковского (ф-т ВМиК МГУ).

Основные результаты работы изложены в 5-и научных публикациях. Структура и объем работы

Диссертация состоит из введения, четырех глав, заключения, списка литературы и приложения. Содержание работы изложено на 138 страницах (включая 12 страниц приложения). Список литературы включает 78 наименований. В работе содержится 19 рисунков и 3 таблицы.

Содержание работы

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

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

Вейвлет,-преобразование (ВП) одномерного дискретного сигнала в = {<%}, ] 6 2, выполняется по следующим рекурсивным формулам:

V, =\-2 * Ь| , =^2 * 0 , г = '¿1 - 1, '¿1 - 2, ..., г0;

(1)

V?1 = S.

Знак "*" обозначает операцию свертки, оператор 4-2 [х] удаляет из сигнала х каждый второй элемент. Фильтры h и g называются соответственно НЧ и ВЧ фильтрами анализа.

Индекс г называется уровнем разрешения или разрешением. Исходному сигналу ставится в соответствие некоторое произвольное значение разрешения i\.

На каждом шаге ВП сигнал распадается на две составляющие: приближение с более низким разрешением v.; (НЧ составляющую) и детализирующую информацию w?; (ВЧ составляющую). Элементы ВЧ составляющих ВП называют вейвлет,-коэффициентами.

Разрешение ?'о, до которого выполняется преобразование, теоретически может быть любым, меньшим i\. Для случая конечных сигналов самым низким разрешением является то, при котором НЧ составляющая состоит из единственного элемента (сокращение количества элементов происходит под действием оператора 4-2 [•])•

Обратное ВП, или восстановление сигнала s выполняется по формуле:

v7:+i =t2 [vj * h+ t2 [w,:] * g, i = i0, k + 1, ..., 4 ~ 1, (2)

Оператор f2 [x] осуществляет вставку нулевого элемента между элементами сигнала х. Фильтры h и g называются соответственно НЧ и ВЧ фил ъ-трамм синтеза.

Очевидно, что формула (2) обеспечивает реальное восстановления сигнала только для фильтров, для которых:

Vx [U [х * h]] * h+ [U [x * g]] * g = x.

Таким образом, конкретное ВП определяется четверкой фильтров h, g, h и g.

Простейшим ВП является преобразование Хаара, которому соответствуют следующие фильтры:

h= [1/2, 1/2], g= [-1/2, 1/2]; h= [1, 1], g= [1, -1].

Рис. 1: Структура вейвлет-преобразования (слева) и дерево преобразования (справа).

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

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

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

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

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

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

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

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

Координаты на плоскости узла уровня разрешения г являются средним арифметическим координат четырех соответствующих ему узлов уровня г + 1. На рис. 2 показано взаимное расположение узлов решеток трех соседних уровней разрешения.

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

X - уровень О О - уровень 1 • - уровень 2

Рис. 2: Узлы решеток уровней 0, 1 и 2 (стрелками показаны ребра квадродерева).

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

Триангулировать полученный набор нерегулярно расположенных узлов предлагается следующим образом. Создается двумерный массив ссылок на вершины, который имеет в точности такой же размер, что и исходная решетка. Если узлу решетки соответствует листовая вершина дерева, то в соответствующий узлу элемент массива заносится ссылка на эту вершину; если узлу решетки соответствует вершина нуль-дерева, то в элемент массива заносится ссылка на корень этого нуль-дерева. Таким образом, массив заполняется ссылками на листовые вершины дерева, причем часть элементов массива содержит ссылки на одни и те же вершины (кроме случая, когда нуль-деревья отсутствуют). Далее по полученному массиву строится триангуляция, как если бы триангулировалась регулярная решетка (эта операция тривиальна). В этом случае часть треугольников будет иметь по две или по три совпадающие вершины (за счет повторяющихся ссылок в массиве). Такие треугольники просто игнорируются. Оставшиеся же треугольники и образуют искомую сетку (рис. 3). Некоторые результаты работы метода показаны на рис. 4.

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

• - узлы, соотв. листовым вершинам дерева О - узлы, соотв. некорневым вершинам нулв-дереввев

Рис. 3: Триангуляция массива ссылок (слева) и итоговая сетка (справа).

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

дом Монте-Карло.

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

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

В п. 4 предложен метод реконструкции и построения адаптивного сеточного представления функции освещенности на основе метода, рассмотренного в п. 2.

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

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

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

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

шагов, а сверткой с двумерным НЧ фильтром-матрицей, с последующим применением оператора 4-2 [•] к строкам и столбцам полученного сигнала. ВЧ составляющие не вычисляются.

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

1

32

12 2 1

2 3 3 2

2 3 3 2

12 2 1

1 124

3 3

5 5

6 6 6 6 5 5 3 3

1

344

1 2

3

4 4 3 2 1

2 3

5 6

6 8

4 7 9

7 9 10 10 9

7 9 10 10 9

6 8 9

5 6 7

2 3 4

4 3 2 7 6 5 9 8 6 7 7

9 8 6 7 6 5 4 3 2

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

На рис. 5 показан пример исходных данных, построенная по ним сетка и восстановленная функция освещенности.

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

Рис. 5: Восстановление освещенности. Результат попадания 200 тыс. фотонов (слева), адаптивная сетка (в центре) и итоговое изображение (справа).

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

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

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

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

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

На примере реализации двух вариантов одного метода показано, как,

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

В третьей главе рассматривается применение вейвлет-анализа для решения задачи построения линий уровня (изолиний) на плоскости.

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

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

Исходными данными является таблично заданная функция

-Л./.з) = ъл, ' = О.Д/. 1. 3 = 0. Л/, 1.

Требуется построить линию уровня некоторого значение Z этой функции.

Для любого квадрата, вершины которого имеют координаты (г,^), (г + I,]), {1,з + 1), (г + 1,3 + 1), г = 0,МХ- 2, 3 = 0,МУ- 2, можно определить, проходит ли через него линия (для этого значения в вершинах сравниваются с Z). Если линия проходит через квадрат, то ищется и запоминается точка пересечения линии с одной из сторон квадрата, и через эту сторону происходит переход в соседний квадрат. В этом квадрате ищется следующая точка пересечения, и происходит дальнейший переход. Так формируется управляющая последовательность.

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

применять В-сплайновое ВП.

В-сплайновая кривая "f(t) — задается в виде:

N-1

7Й = Е CjBj(t), t G [0,1], (3)

j=o

где сj — управляющие точки, а функции Bj(t) — элемент,арные В-сплайны.

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

h h =

А _3 _5_ 5 _5_ _3 _3_ 32 8 32 4 32 8 32

g =

J_ 16

13 11

2 4 2 8

g =

A __5_ 5

16 4 16 2

1 3 1 1

"4 8 4 16

5 3 3

16 4 16

(4)

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

Применение шагов прямого преобразования приводит к сокращению числа управляющих точек и потери части ВЧ информации — таким образом реализуется сглаживание кривой.

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

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

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

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

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

Важная особенность предложенного метода — использование одного представления и одного аппарата обработки (вейвлет-анализа) для решения всех поставленных подзадач обработки объекта. Это обеспечивает не

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

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

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

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

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

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

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

• Легко реализуется масштабирование текстуры.

• Алгоритм генерации текстуры по ее представлению должен работать в реальном времени и допускать аппаратную реализацию.

В п. 2 описывается иерархическая модель представления текстур.

В основе модели лежит идея о «детерминированно-случайной» природе стохастической текстуры. Обе компоненты такой текстуры предлагается

задавать в явном виде: детерминированную компоненту в виде изображения, а случайную — в виде распределения.

Базовым элементом называется некоторое произвольное растровое изображение.

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

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

Предположим, что базовый элемент — квадратное растровое изображение с размером стороны N = 21 точек. Тогда масштабированные версии базового элемента — это квадратные растровые изображения с размерами сторон 2' , i, = 1, I точек. Индекс г назовем уровнем разрешения или просто разрешением.

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

В каждой точке репликации могут иметь место следующие события:

• Позитивная репликация (простое наложение), негативная репликация (наложение с инверсией), нет, репликации.

• Поворот, элемента на 0°, 90°, 180°, 270°.

• Отражение элемента, нет, отражения.

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

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

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

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

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

Последним шагом является добавление к каждой точке изображения фиксированного значения интенсивности фона.

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

Базовый элемент может либо включаться, либо не включаться в описание модели. Последнее значит, что модель предназначена для работы с различными базовыми элементами.

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

Предлагаемая модель обеспечивает очень простой способ масштабирования изображений (в масштабе 1:2, 1:4, 1:8 и т.д.) Для этого достаточно лишь изменить соответствие между слоем изображения и разрешением базового элемента.

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

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

Рис. 7: Различные текстуры с базовыми элементами.

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

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

малых объемов памяти.

Вместе с тем, применение УМС предоставляет следующие преимущества:

• Возможна локальная генерация текстуры по УМС.

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

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

П. 6 посвящен связи предложенной модели с теорией вейвлет-анализа. Описанная выше структура репликаций основана на простом двумерном обратном ВП непрерывных сигналов (которое рассматривается в приложении к диссертации). Запишем ее с помощью следующей формулы:

N-1 / +00

./'(,<•. у) = V + Е ( Ё W [ф(Ух - J. Ту - к), сЩ). (5)

г=0 \j,A'=—оо /

Начальным приближением является константа v — интенсивность фона. Аналогом вейвлета является базовый элемент i/j(x,y). Аналогами вейвлет-коэффициентов выступают два объекта. Во-первых, это весовые коэффициенты определяемые по одному для каждого слоя. Во-вторых, коэффициент при каждой копии базового элемента меняется на функционал W[*, с], который преобразует аргумент в зависимости от значения числового параметра с. Параметр с — код ячейки УМС или значение случайной величины, распределение которой задается таблицей событий.

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

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

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

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

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

Основные результаты работы

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

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

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

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

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

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

Публикации по теме диссертации

1. Переберин А.В. О систематизации вейвлет-преобразований // Вычислительные методы и программирование. — 2001. — Т. 2, № 2. — С. 133-158. (Электронная версия на сайте http://num-meth.srcc.msu.su/)

2. Переберин А.В. Построение изолиний с автоматическим масштабированием // Вычислительные методы и программирование. — 2001. — Т. 2, № 1. — С. 118-128.

(Электронная версия на сайте http://num-meth.srcc.msu.su/)

3. Pereberin A.V. From Photon Map to Irradiance Function via Wavelet Transform // GraphiCon'97 Proceedings. — 1997. — P. 38-43.

4. Pereberin A.V. Hierarchical Approach for Texture Compression // GraphiCon'99 Proceedings. — 1999. — P. 195-199.

5. Pereberin A.V. Fast Multi-Scaled Texture Generation and Rendering // GraphiCon'2000 Proceedings. — 2000. — P. 145-150.

Введение

1 Основы многомасштабного представления информации

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

1.2 Преобразование Хаара.

1.3 Вейвлет-преобразования дискретных сигналов.

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

1.5 Вейвлет-преобразования двумерных сигналов.

1.6 Древовидные структуры для представления вейвлет-преоб-разований.

2 Адаптивное сеточное представление объектов, определенных на плоскости. Задача реконструкции освещенности на плоскости

2.1 Двумерные сигналы и сеточное представление.

2.2 Использование вейвлет-анализа для построения адаптивных сеток.

2.2.1 Дерево узлов.

2.2.2 Альтернативный подход: дерево ячеек.

2.2.3 Примеры работы метода.

2.3 Многомасштабный анализ и реконструкция освещенности

2.3.1 Методы глобальной освещенности.

2.3.2 Метод Монте-Карло трассировки лучей

2.3.3 Представление функции освещенности.

2.3.4 Вычисление значений освещенности.

2.4 Описание метода реконструкции освещенности.

2.4.1 Начальное приближение функции освещенности

2.4.2 Структура преобразования.

2.4.3 Дерево преобразования и триангуляция.

2.4.4 Выбор фильтров.

2.4.5 Примеры работы метода.

2.5 Анализ результатов.

3 Многомасштабное представление линий уровня

3.1 Описание задачи.

3.2 Построение последовательности управляющих точек.

3.3 Построение линии.

3.3.1 Уточнение формулировки задачи

3.3.2 В-сплайновые кривые и вейвлеты.

3.3.3 Реализация вейвлет-преобразования.

3.3.4 Преобразование управляющей последовательности

3.3.5 Сглаживание кривой

3.3.6 Масштабирование и отображение кривой.

3.4 Реализация и анализ результатов.

4 Генерация текстур

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

4.2 Описание модели.

4.2.1 Базовый элемент и репликации

4.2.2 Построение изображения из репликаций.

4.2.3 Определение параметров модели.

4.2.4 Масштабирование.

4.3 Примеры.

4.4 Управляющие маски слоев.

4.5 Представление данных и особенности реализации.

4.6 Связь с теорией вейвлет-анализа.

4.7 Анализ результатов. Развитие задачи.

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

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

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

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

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

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

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

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

Иерархическое представление, обладающее подобными свойствами, в литературе называют многомасштабным. Примером конструкций, обеспечивающих многомасштабное представление информации, служат пирамиды лапласианов и гауссианов, предложенные в [24]. Идеи, использованные при построении этих пирамид, легли в основу теории в ейв лет,-анализ а (или анализа всплесков)[2, 3, 11, 15, 25, 29, 45, 56, 73, 77] — инструмента, который активно используется в настоящее время для работы с многомасштабными представлениями данных самой различной структуры.

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

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

Другим отличием является то, что в случае вейвлет-анализа в наиболее общей постановке не конкретизируется не только сам порождающий вейвлет, но и то, какие именно его копии участвуют в разложении. Отсюда очевидно, что термин «вейвлет-преобразование» является обозначением целого класса разложений. Анализ Фурье, как известно, является разложением по фиксированной системе функций.

Считается, что начало вейвлет-анализу было положено в работах А. Ха-ара еще в начале XX века [40]. В дальнейшем предпринимались попытки создания иерархических базисов для решения различных задач, но они не были объединены единой теорией и, следовательно, не имели единого подхода.

В конце 80-х годов С. Малла вводит понятие многомасштабного анализа [55], и определяет общий подход для поиска различных вейвлет-базисов. Им же разрабатывается основной алгоритм вычисления вейвлет-преобразований для дискретных сигналов, что открывает широкие возможности для практической реализации метода. С этого момента теория и практика вейвлет-анализа начинают активно развиваться. В 1992 году появляется классическая работа И. Добеши «Десять лекций по вейвлетам» [29] (в 2001 году издана на русском языке [3]). Эта книга, а также некоторые другие издания (напр., [77]), посвящены строгому изложению теории вейвлет-анализа. Выходит в свет несколько книг, в которых содержится подробное введение в вейвлет-анализ, а также рассматривается широкий круг прикладных задач [25, 26, 56]. В середине 90-х годов В. Свелденс предлагает новый метод вычисления вейвлет-преобразований, названный лифт.ингом [30, 74], который несколько более эффективен, чем классический алгоритм, предложенный Малла, и, кроме того, позволяет расширить класс вейвлет-преобразований.

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

Наиболее распространенным примером применения вейвлет анализа в компьютерной графике и обработке изображений является сжатие изображений [15, 31, 57, 66, 68]. Во многих публикациях можно встретить упоминание о том, что один из первых алгоритмов был разработан для сжатия изображений отпечатков пальцев по заказу ФБР США, где и сейчас успешно используется. Разработчики стандарта JPEG-2000 утверждают, что их алгоритм сжатия основан на вейвлет-преобразовании.

Кроме этого вейвлеты применяются для обработки практически всех основных графических объектов: кривых [25, 34], поверхностей [22, 32, 39, 53, 54], сплошных трехмерных тел [42]. Отдельно можно отметить применение вейвлет-анализа в таких сложных задачах графики, как моделирование освещенности методом излучательности [38].

Вейвлет-анализ находит применение и в задачах компьютерного зрения, распознавание и классификации образов [44, 76].

В 1996 году выходит книга Дж. Столнитза и др. «Вейвлеты в компьютерной графике. Теория и приложения» [73], в которой, кроме необходимого введения в теорию, описываются наиболее характерные приложения вейвлет-анализа в графике, а также содержится большой библиографический список.

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

В настоящее время вейвлет-анализу уделяется все больше внимания и в отечественных исследованиях, однако, пока этот аппарат еще не получил широкого распространения. Возможно, это связано с недостатком литературы по основам вейвлет-анализа, она выходит небольшими тиражами и не всегда доступна [11, 15]. Переводы трудов зарубежных авторов стали появляться совсем недавно [3, 20].

Тем не менее, появляются работы как теоретического плана [10, 51, 78], так и посвященные различным прикладным задачам [4, 9, 18] (см. также списки публикаций отечественных авторов в [3, 20]).

Что касается компьютерной графики и обработки изображений, то отечественных работ в этой области весьма мало, и посвящены они, в основном, сжатию изображений [7, 16]. Из других задач можно упомянуть работу об использовании вейвлетов для решения уравнения излучательности [8].

Кроме того, следует отметить работы по обработке изображений с помощью базиса Эрмита [48], а также оригинальный алгоритм сжатия изображений, который основан на иерархическом, но не вейвлетном представлении данных [43].

Цель работы

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

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

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

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

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

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

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

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

Основные результаты диссертации докладывались на конференциях по компьютерной графике и машинному зрению «ГрафиКон'97», «Графи

Кон'99», «ГрафиКон'2000», семинаре по компьютерной графике и обработке изображений Ю.М. Баяковского (ф-т ВМиК МГУ), объединенном семинаре ИПМ им. М.В. Келдыша РАН и МГТУ им. Н.Э. Баумана и опубликованы в работах [13, 14, 62, 63, 64].

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

Диссертация состоит из четырех глав и приложения.

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

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

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

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

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

Благодарности

Автор выражает благодарность научному руководителю Ю.М. Баяковско-му, а также Л.И. Левковичу-Маслюку (ИПМ им. М.В. Келдыша РАН) за сотрудничество и помощь в работе, А.В. Черницкому (ОАО «ВНИИ-нефть») за поддержку проекта по обработке линий уровня, компанию Intel Techologies, Inc. за поддержку проекта по генерации текстур.

Основные результаты диссертации состоят в следующем:

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

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

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

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

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

Иллюстрации j i г с л 1; с jr. и с L! r; j1 r.' .-j j-r.1^ j лт:; ::1тлт^глтлт1Г1 iwj" i a 5 л 1; c jr. ii n г г; j1 r. G1UICGJ1UI0G012FW JJttlGflSHilJimMWinflMmiiajGJlllICGaiJIJGI! HHMGBHUQWJ! .KTiSMirMMJMaiMeMaBJIJGBlUJMarGfll шгшгдонни'.шннишилотимивишшдошынй мнгма^с маык,: ^Еанпшмашваааииютшма; ;с малнис а^ысгшодготтшевштпсмансма^см naicGjaBscwaz1 isserjjajjfи mzEftigzcfw i^iSisiHHifaaiMJBBoeMweHOJiflazGJMazGJi

GGWGJUIJGG ^мзннннягамлАявямяетяйАи^зи^в шншиш .^ишнннныбемввеввииедшшнин aafsctcaucae. ^^^ссг^тпаишавееоюнаоса^саса^са; гмгнгггш^вдгчипээвдиащювагимагэгмй магссмагат^млл-гслаиммкямлплганноивмагаАмагма tMicGfaasctH asset; сегавгошиггм'алшвивмагсгмагвн

HMMGBQiGf н; ли®' лв0яя0влии;ж* aoonaejiiazGJMSZGJi GWfGfllJIJGGH™?; 'iraWeaiffmiWr&flJBSeBOMBlJICGGlSIJGB тгмсэистг тл л шншмш мммимиылввгмидминшгнд? spazGHQfaztiu; . jimwBicHHfliLrdiiwtfmimmBBjaiicsjszics Еодиикагоиамвдггакюишнсма^са; игв;; tjaiGf ыa!G(;: ",;: ;!r iгагававаыамвмввптапаагврмагмг GIUIBGMUIBGJ; „";:■.:,'. mmBumraffaGOHBOiraoBeGiiiiBGjaiiisifl

151ZSJGBlZtJli."' 1:. !BnnmSSnUdG«SOS16l1BiaiBG3t!EfGsajcai шншншл мС^егошгатынтощпввввшншгндг mitcac aitcaf >L : ti-u, гъввшшыгв! агашэагаяшютас aitcaf siiua 'dSUjCdUijjC'di'iLii 'I-; .^-тововдоедоаавдвдяпвдеа; seMadicM MazGcuazMMH.■^ниа^готаиаяммьвдяоииагммагма iMituaflicwazGr .' iiUfQzwwueeuasraaasoiaGPQHCMaiiicH gmscmmscmqzgc

JJ1ZGJ IfllZGMHSJ. : :VlVIBSOOmMGIOBIB5QBiBG( IfllZGMBSZGJl

GiuicGjmicGaizsji иштлииотпвповявиогсллгслзи GS jfliitJGjanjwfG^:;. ■■привтааяагавввовнаийгш:!!^?^;! шншшшнн1 :i

MHEMaufMazGcai > ^ггшпаиаиишигаганиагмансмалнис cpazGcafaztcwHtcai mivmBHaBeHUfmBBjaflicajszGBajszMS шгэнйвпвдаплигмансмагссмагмг i faiGf naiGj 155BGJ - -"™s3misieGfai!i( naiGj маю: i

GMSCGHgscMtzccMazGfazccGfMSCMUECMQiGfMaiGHgseMtJSCM

GbWGfllJIJGBlZSJGBlZSJGWGfllJIJGBlZSJCBlZSJGBaiGfllJIJGBlJIJGB

Рис. 1.1: Слева исходная сетка 4096 (64 x 64) уз., 7938 тр.; справа сетка 2046 уз., 4120 тр.

Рис. 1.2: Слева сетка 1651 уз., 3252 тр.; справа сетка 1396 уз., 2744 тр.

Рис. 1.3: Эталонное изображение (слева) и рез-т попадания 200 тыс. фотонов (справа).

Рис. 1.4: Сетка (слева) и итоговое изображение (справа).

Рис. 1.5: Реконструкция по 500 тыс. фотонам.

Рис. II. 1: Построение линий по исходным данным без сглаживания

Рис. II.2: Сглаживание (2 шага, основной филвтр)

Рис. II.3: Сглаживание (2 шага, дополнительный фильтр)

Рис. II.4: Подавление лестничного эффекта и масштабирование

Рис. III. 1: Модель «произвольное вращение» с разными базовыми элементами

Рис. III.2: Модель «произвольное вращение». Текстура показана в двух масштабах

• •

Рис. III.3: Модель «сыр» с базовым элементом

Рис. III.4: Модель «кирпичная стена» с базовым элементом (слева первоначальный вариант, справа вариант с добавлением шума)

Заключение

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

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

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

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

1. Баяковский Ю.М., Галактионов В.А., Михайлова Т.Н. Графор. Графическое расширение Фортрана. — М.: Наука, 1985.

2. Бердышев В.И., Петрак JI.B. Аппроксимация функций, сжатие численной информации, приложения. — Екатеринбург: УрО РАН, 1999.

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

4. Захаров В.Г. Разработка и применение методов вейвлет-анализа к нелинейным гидродинамическим системам: Дис. . канд. физ.-мат. наук: 01.02.05 — Пермь, 1997.

5. Иванов В.П., Батраков А.С. Трехмерная компьютерная графика. — М.: Радио и связь, 1995.

6. Каханер Д., Моулер К., Нэш С. Численные методы и программное обеспечение. — М.: Мир, 2001.

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

8. Кокорин О.Ю., У дольников С. А. Использование иерархического алгоритма в методе излучательности // Труды конференции ГрафиКон'97.1997. — С. 31-37.

9. Левкович-Маслюк Л.И. Аппроксимация финансовых рядов фрактальными интерполяционными функциями // Вопросы анализа риска. — 1998.1. Vol. 1, No. 1.

10. Лоренц Р.А., Саакян А.А. О подпространствах, порожденных всплеск-системами // Математические заметки. — 1998. — Т. 63, № 2. — С. 299-302.

11. Новиков И.Я., Стечкин С.Б. Основные конструкции всплесков // Фундаментальная и прикладная математика. — 1997. — Т. 3, № 4. — С. 999-1028.

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

13. Переберин А.В. О систематизации вейвлет-преобразований // Вычислительные методы и программирование. — 2001. — Т. 2, № 2. — С. 133-158. (Электронная версия на сайте http://num-meth.srcc.msu.su/)

14. Переберин А.В. Построение изолиний с автоматическим масштабированием // Вычислительные методы и программирование. — 2001. — Т. 2, № 1. — С. 118-128. (Электронная версия на сайтеhttp://num-meth.srcc.msu.su/)

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

16. Поспелов В.В., Кислицына М.А. Использование преобразования Хаара для модификации алоритма JPEG сжатия изображений // Тезисы докладов коференции РОАИ'97. — 1997. Ч. 1. С. 210-212.

17. Роджерс Д., Адаме Дж. Математические основы машинной графики. — М.: Мир, 2001.

18. Стаховский И.Р. Вейвлетный анализ временных сейсмических рядов // ДАН. 1996. Т. 350, № 3. С. 393-396.

19. Шикин Е.В., Боресков А.В. Компьютерная графика. Динамика, реалистические изображения. — М.: ДИАЛОГ-МИФИ, 1996.

20. Чуй К. Введение в вэйвлеты. — М.: Мир, 2001.

21. De Bonet J.S. Multiresolution Sampling Procedure for Analysis and Synthesis of Texture Images // SIGGRAPH'97 Proceedings. — 1997. — P. 362-368.

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

23. Bonneau G.-P., Hahmann S., Nielson G.M. BLaC-Wavelets: A Multiresolution Analysis With Non-Nested Spaces // IEEE Visualization'96 Proceedings. — 1996. — P. 43-48.

24. Burt P.J., Adelson E.H. The Laplasian Pyramid as a Compact Image Code // IEEE Trans, on Communications. — 1983. — Vol. COM-31, No. 4. — P. 532-540.

25. Chui С.К. An Introduction to Wavelets. — New York London: Academic Press, 1992.

26. Chui C.K., editor. Wavelets: a Tutorial in Theory and Applications. — New York London: Academic Press, 1992.

27. Chui C.K., Quak E. Wavelets on a Bounded Interval // Numerical Methods in Approximation Theory. — 1992. — Vol 9. — P. 53-75.

28. Coifman R.R., Meyer Y., Wickerhauser V. Wavelet Analysis and Signal Processing Wavelets // Wavelets and their Applications. — Boston: Jones and Barlett, 1992. — P. 153-178.

29. Daubechies I. Ten Lectures on Wavelets. — Philadelphia: SIAM, 1992.

30. Daubechies I., Sweldens W. Factoring Wavelet Transforms into Lifting Steps // IEEE Trans, on Image Processing. — 2000. — Vol. 9, No. 3. — P. 480-496.

31. DeVore R., Jawerth W., Lucier B. Image Compression Trough Wavelet Transform Coding // IEEE Trans, on Information Theory. — 1992. — Vol. 39, No. 2. — P. 719-746.

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

33. Efros A.A., Leung Т.К. Texture Synthesis by Non-Parametric Sampling // IEEE International Conference on Computer Vision. 1999.

34. Finkelstein A., Salesin D.H. Multiresolution Curves // SIGGRAPH'94 Proceedings. — 1994. — P. 261-268.

35. Foley J.D., van Dam A., Feiner S.K., Huges J.F. Computer Graphics. Principles and Practice. — New York: Addison-Wesley, 1990.

36. Gabour D. Theory of Communications // Journal of the Institute of Electrical Engineers. — 1946. — Vol. 93, No. 22. — P. 429-457.

37. Glassner A.S. Principles of Digital Image Synthesis. — San Francisco: Morgan Kaufmann, 1995.

38. Gortler S.J., Schroder P., Cohen M.F., Hanrahan P. Wavelet Radiosity // SIGGRAPH'93 Proceedings. 1993. P. 221-230.

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

40. Haar A. Zur Theorie der Orthogonalen Funktionen-Systeme // Math. Ann.1910. — No. 69. — P. 331-371.

41. Heeger D.J., Bergen J.R. Pyramid-based Texture Analysis/Synthesis // SIGGRAPH'95 Proceedings. — 1995. — P. 229-238.

42. Ihm I., Park S. Wavelet-Based 3D Compression Scheme for Ineractive Visualization of Very Large Volume Data // Computer Graphics Forum.1999. — Vol. 18, No. 1. — P. 3-15.

43. Ivanov D.V., Kuzmin E.P., Burtsev S.V. Progressive Image Compression Using Binary Trees // GraphiCon'98 Proceedings. — 1998. — P. 187-194.

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

45. Jawerth В., Sweldens W. An Overwiew of Wavelet Based Multiresolution Analyses // SIAM Rev. — 1994. — Vol. 36, No. 3. — P. 377-412.

46. Jensen H.W. Global Illumination Using Photon Maps // The 7-th Eurographics Workshop on Rendering Proseedings. — 1996. — P. 21-30.

47. Jensen H.W., Christensen N.J. Bidirectional Monte Carlo Ray Tracing of Copmplex Objects Using Photon Maps // Computers and Graphics. — 1995. — Vol. 19, No. 2.

48. Kortchagine D.N., Krylov A.S. Projection Filtering in Image Processing // GraphiCon'2000 Proceedings. — 2000. — P. 42-45.

49. Kovacevic J., Sweldens W. Wavelet Families of Increasing Order in Arbitrary Dimentions // IEEE Trans, on Image Processing. — 2000. — Vol. 9, No. 3. — P. 480-496.

50. Lee S., Lawton W., Shen Z. An Algorithm for Matrix Extension and Wavelet Constructions // Mathematics of Computation. — 1996. — Vol. 65, No. 214.1. P. 723-737.

51. Levkovich-Maslyuk L.I. Wavelet-Based Determination of Generating Matrices for Fractal Interpolation Functions // Regular and Chaostic Dynamics. — 1998. — Vol. 3, No. 2.

52. Lorensen W.E., Cline H.E. Marching Cubes: A High Resolution 3D Surface Reconstruction Algorithm // Computer Graphics. — 1987. — Vol. 21, No. 4. — P. 163-169.

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

54. Lounsbery M., T.D. DeRose T.D., Warren J. Multiresolution Analysis for Surfaces of Arbitrary Topological Type // ACM Trans, on Graphics. — 1997. — Vol. 16, No. 1. — P. 34-73.

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

56. Mallat S. A Wavelet Tour of Signal Processing. — New York London: Academic Press, 1998.

57. Mallat S., Zhong S. Characterization of Signals from Multiscale Edges // IEEE Trans, on Pattern Analysis and Machine Intelligence. — 1992. — Vol. 14, No. 7. — P. 710-732.

58. Martens J.-B. The Hermite Transform — Theory // IEEE Trans, on Acoustics, Speech and Signal Processing. — 1990. — No. 38. — P. 1595-1606.

59. Martens J.-B. The Hermite Transform — Applications // IEEE Trans, on Acoustics, Speech and Signal Processing. — 1990. — No. 38. — P. 1607-1618.

60. Myszkowski K. Lighting Reconstruction Using Fast and Adaptive Density Estimation Techniques // Rendering Techniques'97. 1997.

61. Mumford D., Gidas B. Stochastic Models for Generic Images. — 2000. (http: / / www.dam.brown.edu / people / mumford/Papers / Generic5 .pdf)

62. Pereberin A.V. From Photon Map to Irradiance Function via Wavelet Transform // GraphiCon'97 Proceedings. — 1997. — P. 38-43.

63. Pereberin A.V. Hierarchical Approach for Texture Compression // GraphiCon'99 Proceedings. — 1999. — P. 195-199.

64. Pereberin A.V. Fast Multi-Scaled Texture Generation and Rendering // GraphiCon'2000 Proceedings. — 2000. — P. 145-150.

65. Rogers D. Introduction to NURBS: With Historical Perspective. — San Francisco: Morgan Kaufmann, 2000.

66. Said A., Perlman W.A. A New Fast and Efficient Image Codec Based on Set Partitioning in Hierarchical Trees // IEEE Trans. CSVT. — 1996. — Vol. 6, No. 3. — P. 243-250.

67. Schroeder W.J., Zarge J.A., Lorensen W.E. Decimation of Triangle Meshes // SIGGRAPH'92 Proceedings. — 1992. — P. 65-70.

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

69. Shirley P. Time Complexity of Monte Carlo Radiosity // Eurographics'91 Proceedings. — 1991. — P. 459-466.

70. Shirley P., Wade В., Hubbard P.M., Zareski D., Walter В., Greenberg D.P. Global Illumination via Density Estimation // The 6-th Eurographics Workshop on Rendering Proseedings. — 1995. — P. 219-230.

71. Silverman B.W. Density Estimation for Statistics and Data Analysis. — London: Chapmann and Hall, 1985.

72. Smits В.E., Arvo J.R., Greenberg D.P. A Clustering Algorithm for Radiosity in Complex Envirounments // SIGGRAPH'94 Proceedings. — 1994. — P. 435-442.

73. Stollnitz E.J., DeRose T.D., Salesin D.H. Wavelets for Computer Graphics. Theory and applications. — San Francisco: Morgan Kaufmann, 1996.

74. Sweldens W. The Lifting Scheme: A Construction of Second Generation Wavelets // SIAM J. Math. Anal. — 1996. — Vol. 3, No. 2. — P. 186-200.

75. Sweldens W., Schroder P. Building Your Own Wavelets at Home // Wavelets in Computer Graphics, ACM SIGGRAPH Course Notes, 1996.

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

77. Wojtaszczyk P. A Mathematical Introduction to Wavelets. — Cambridge: Cambridge University Press, 1997.

78. Zakharov V. Nonseparable Multidimentional Littlewood-Paley Like Wavelet Bases. — Marseille: Centre de Phisique Theorique, 1996.