Проникновение вейвлетов в область компьютерной графики происходит весьма стремительно.
Это не удивительно, если вспомнить, сколько приложений нашлось в ней для преобразования Фурье, логическим продолжением которого можно считать вейвлет-преобразования, а круг приложений вейвлет-преобразований значительно шире.
Одним из наиболее выразительных примеров использования вейвлетов в компьютерной графике является обработка растровых изображений.
Изображение есть не что иное, как функция цвета (или, в монохромном случае, функция интенсивности), определенная на участке плоскости, обычно прямоугольном или квадратном.
"Реальное" изображение имеет непрерывную область определения, растровое изображение определено на дискретном наборе точек растра - пикселах.
Важной задачей обработки изображений является частотный анализ. Одним из способов частотной обработки является способ, основанный на преобразовании Фурье.
Преобразование Фурье действительно позволяет получить частотный спектр изображения и дает возможность производить с этим спектром определенные операции.
Использование для этой цели вейвлет-преобразований открывает дополнительные возможности, которые в основном обусловлены локализацией вейвлет-базиса в пространстве.
А это значит, что и частотную обработку можно проводить локально для различных фрагментов изображения.
Допустим, например, что имеется фотография, на которой необходимо выделить один-два основных объекта, скажем, лица, и "размыть" все остальное.
С точки зрения вейвлет-преобразования это значит всего лишь, что нужно обратить в ноль вейвлет-коэффициенты, соответствующие определенным частотам и не относящиеся к специально отмеченным областям изображения.
Вейвлеты используются и для сжатия изображений.
Идея вейвлет-сжатия также напоминает идею сжатия, основанную на использовании преобразования Фурье. Дискретное преобразование Фурье ставит с соответствие набору из N значений функции, выражающей, например, зависимость некоторого параметра от пространственной координаты, набор из N коэффициентов Фурье - элементов частотного спектра этой функции.
Если некоторые коэффициенты Фурье оказались равными 0, то оставшихся значений будет достаточно, чтобы полностью (без искажений) восстановить исходный набор. Таким образом, удается представить исходную информацию меньшим числом значений.
Еще одна распространенная задача - построение разного рода сеток.
Сетка весьма удобна для представления объектов самой разнообразной структуры. В компьютерной графике часто используются треугольные сетки, они относительно просты в обработке, позволяют представлять объекты с высокой точностью.
Кроме того, на многих графических станциях обработка треугольников, например заливка Гуро, поддерживается аппаратно.
Использование равномерной сетки бывает оправдано не всегда - объект может иметь как фрагменты, с хорошей степенью точности представимые лишь несколькими крупными треугольниками, так и детали со сложной структурой, которые следует представлять возможно более мелкой сеткой.
Существуют так называемые алгоритмы адаптивной триангуляции. Они обычно рекурсивные и решают эту задачу следующим образом: в уже имеющуюся сетку добавляется по определенному правилу новая вершина либо одна из вершин исключается, а изменившаяся структура триангулируется заново. Такие алгоритмы работают медленно.
Использование вейвлетов позволяет сразу построить набор вершин треугольников, при этом уже учитываются особенности объекта и степень точности представления. Этот набор вершин можно триангулировать и сразу получать необходимую сетку.
Возможно, читатель знаком с трассировкой лучей методом Монте-Карло. Это один из широко используемых в настоящее время методов синтеза освещения в трехмерных сценах с помощью моделирования физических процессов распространения света.
Суть метода заключается в следующем.
Требуется промоделировать ход лучей от источников света, их отражение, преломление или поглощение объектами сцены, и, самое главное, зарегистрировать "след", который они оставляют на этих объектах.
Разумеется, невозможно промоделировать весь непрерывный световой поток. Вместо этого проводят конечное число статистических экспериментов по испусканию лучей источниками света.
Выпущенный источником световой луч достигает одной из поверхностей сцены. Он может быть либо поглощен поверхностью, либо может отразиться или преломиться и таким образом продолжить свой путь.
Вероятность каждого из этих событий, а также вероятность того, под каким углом луч может отразиться или преломиться, определяется специальной функцией, характеризующей отражающие свойства данной поверхности.
Понятно, что при стремлении числа выпущенных лучей к бесконечности процесс будет сходиться к реальной картине распространения света.
Луч, попавший на поверхность, оставляет на ней след - световую точку. Следы регистрируются в специальной структуре данных, которая называется фотонной картой (photon map). Для каждой поверхности создается своя фотонная карта.
Будем считать, что поверхности сцены плоские (это не столь серьезное ограничение, даже реальные сложные сцены содержат большое количество объектов с плоскими поверхностями или объектов, хорошо приближаемых набором плоских поверхностей), тогда фотонной картой в простейшем случае можно считать простой список точек-фотонов, попавших на поверхность.
С этого момента каждая фотонная карта обрабатывается совершенно независимо от других. (Это является одним из преимуществ метода, так как позволяет легко распараллеливать дальнейшие вычисления).
Итак, получена фотонная карта. Требуется по дискретному набору точек восстановить функцию освещенности поверхности. Понятно, что чем гуще скопление фотонов, тем ярче должно быть в этом месте световое пятно. Подобные задачи называют задачами оценки плотности (density estimation).
Существуют различные методы их решения. Эти методы позволяют получить приближенное значение функции освещенности в любой точке, однако это достаточно трудоемкий процесс.
В таких случаях часто поступают следующим образом. Сначала табулируют функцию, то есть вычисляют ее значения в узлах мелкой сетки с постоянным шагом - такая таблица называется картой освещенности (illumination map).
Затем "прореживают" полученную таблицу, стараясь избавиться от возможно большего числа значений, не нарушая при этом заданной точности представления.
На последнем этапе функция освещенности восстанавливается интерполяцией по оставшимся точкам.
Был реализован следующий процесс.
При построении карт освещенности считали не значения функции в узлах, а средние значения в ячейках равномерной квадратной сетки. К построенной таким образом карте применили вейвлет-преобразование Хаара, которое позволило построить кусочно-постоянную аппроксимацию функции в виде неравномерной квадратной сетки.
Полученная сетка триангулировалась. При визуализации выполнялась заливка треугольников методом Гуро, что эквивалентно кусочно-билинейной интерполяции.
Для тестирования метода пользовались фотонными картами, построенными не трассировщиком лучей, а полученными специальным образом из обычных растровых изображений.
В каждый пиксел исходного изображения "бросается" определенное число фотонов. Вероятность "попадания" фотона пропорциональна яркости пиксела.
Такой способ позволяет без использования трассировщика моделировать фотонные карты самых замысловатых структур. Пример того, как из моей собственной фотографии получилась фотонная карта.
Данная работа не является завершенной. В дальнейшем предполагается использовать вейвлеты не только для обработки карт освещенности, но и для их построения (в настоящее время для этого используется метод, не использующий вейвлетов), а также перейти к работе с цветом.
