Вейвлеты в компьютерной графике

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

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

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

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

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

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

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

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

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

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

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

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

Итак, получена фотонная карта. Требуется по дискретному набору точек восстановить функцию освещенности поверхности. Понятно, что чем гуще скопление фотонов, тем ярче должно быть в этом месте световое пятно. Подобные задачи называют задачами оценки плотности (density estimation). Существуют различные методы их решения. Эти методы позволяют получить приближенное значение функции освещенности в любой точке, однако это достаточно трудоемкий процесс. В таких случаях часто поступают следующим образом. Сначала табулируют функцию, то есть вычисляют ее значения в узлах мелкой сетки с постоянным шагом - такая таблица называется картой освещенности (illumination map). Затем "прореживают" полученную таблицу, стараясь избавиться от возможно большего числа значений, не нарушая при этом заданной точности представления. На последнем этапе функция освещенности восстанавливается интерполяцией по оставшимся точкам.

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

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

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

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

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

О применения вейвлетов в компьютерной графике можно говорить долго. Тем, кого заинтересовали вейвлеты, могу порекомендовать книгу [1], в которой вопрос раскрывается весьма полно, с достаточной степенью научности и в то же время не очень утомительно (только, боюсь, достать эту книгу будет непросто).

С автором можно связаться по e-mail: avpereb@cs.msu.su.

Литература

1. E. J. Stollnitz, T. D.Derose, D. H.Salesin. Wavelets for Computer Graphics. Theory and Applications. - San Francisco, California: Morgan Kaufmann Publishers, Inc., 1996.

2. A. S. Glassner. Principles of Digital Image Synthesis. Vol. 1, Ch. 6. - San Francisco, California: Morgan Kaufmann Publishers, Inc., 1995.

3. A. V. Pereberin. From Photon Map to Irradiance Function via Wavelet Transform // Graphicon'97 Proceedings, 1997, pp. 38-44.