В предыдущей части я рассмотрел определение дизеринга и объяснил, как он изменяет характеристики погрешностей простой 1D-дискретизации и функций.

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

Ноутбук Mathematica для ряда золотого сечения находится здесь, а его pdf-версия — здесь.

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

Ряд золотого сечения

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

FractionalPart[N*GoldenRatio]

Идею его использования я нашёл в статье “Golden Ratio Sequences For Low-Discrepancy Sampling” авторов Colas Schretter и Leif Kobbelt.

Это невероятно потрясающий ряд, потому что он распределяет следующие значения очень хорошо и на достаточно далёком расстоянии:

Разность между следующими элементами находится в пределах 1:

{0.381966, 0.618034, 0.381966, 0.381966, 0.618034, 0.381966, 0.618034, 0.381966}

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

Дополнение: Mikkel Gjøl заметил, что модуль/минимальное тороидное расстояние 0.618034 равно 0.381966, то есть ряд превращается в:

{0.381966, 0.381966, 0.381966, 0.381966, 0.381966, 0.381966, 0.381966, 0.381966}

Я нахожу это свойство очень красивым!

Даже при небольшом количестве «сэмплов» в ряду они очень хорошо покрывают весь интервал 0-1:

Числа в виде цветов тоже выглядят «приятно»:

Если взглянуть на периодограмму ряда:

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

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

Но я всё равно считаю это ряд чрезвычайно ценным и активно использую его, например, во временнЫх техниках (а также в сэмплировании полусфер). Существуют и другие очень полезные ряды с низким расхождением, которые активно используются в рендеринге — я не буду их здесь рассматривать, а просто сошлюсь на «библию» основанного на физике рендеринга — “Physically Based Rendering, Third Edition: From Theory to Implementation” авторов Matt Pharr, Wenzel Jakob и Greg Humphreys, и на главу 7, которую авторы любезно выложили в бесплатный доступ!

А теперь давайте рассмотрим синий шум и теоретически «идеальные» ряды для дизеринга.

Синий шум

Что такое синий шум? Википедия даёт следующее определение:

Синий шум также называется лазурным (azure noise). У синего шума плотность энергии увеличивается по 3 дБ на октаву с повышением частоты (плотность пропорциональна f) на конечном интервале частот. В компьютерной графике понятие синего шума часто используется в более широком смысле и обозначает любой шум с минимально низкими компонентами частот и без концентрированных всплесков энергии.

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

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

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

Генерация синего шума — highpass and remap

Первая рассматриваемая техника взята из поста Тимоти Лоттса в AMD GPUOpen “Fine art of film grain”.

Эта техника проста, но великолепна — на первом шаге мы возьмём шум с нежелательным частотным спектром и просто изменим его форму, применив фильтр верхних частот.

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

Картина после операции с произвольным фильтром для случайного шума, изначально находившегося в интервале 0-1.

Здесь вступает в действие вторая часть алгоритма. Мы преобразуем гистограмму, загоняя её в интервал 0-1! Алгоритм прост — сортируем все элементы по значению, а затем преобразуем значение в позицию в списке.

Результат намного лучше:

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

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

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

Сверху — обычный случайный шум. Внизу — с фильтром верхних частот и преобразованием гистограммы.

Частотный спектр выглядит многообещающе:

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

Но мы снова можем применить ту же технику!

И вот что мы получим:

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

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

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

Небольшая часть ряда с локальным минимумом; от неё не удалось избавиться даже после 10 повторений алгоритма. Заметьте, что некоторые области почти равномерно серые.

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

Стоит заметить, что исходный алгоритм создаёт ряд, который неидеален, но «достаточно хорош» — он сохраняет довольно плохие локальные места, но оптимизирует частотный спектр в глобальном плане. Давайте проверим его в действии.

Результаты

Давайте взглянем на наш исходный, простой 1D-дизеринг для двоичной дискретизации:

Строки 1, 3, 5 — исходная синусоида. Строка 2 — дизеринг обычным шумом. Строка 4 — дизеринг рядом золотого сечения. Строка 6 — дизеринг «highpass and remap» (рядом, напоминающим синий шум).

Как видите, и ряд золотого сечения, и highpass and remap лучше, чем обычный шум. Однако кажется, что ряд золотого сечения проявляет себя лучше из-за меньшей «скученности». Мы можем увидеть, что некоторые «пульсации» частот соответствуют пиковым частотам:

Чёрный — белый шум. Красный — ряд золотого сечения. Зелёный — ряд шума highpass and remap.

То есть эта техника неидеальна, но a) очень быстра b) гибка и c) намного лучше любого белого шума.

Что лучше? Более медленный синий шум

Итак, что можно сделать, если нам нужно решение без таких локальных «скученностей»? Можно взглянуть на статью с Siggraph 2016 “Blue-noise Dithered Sampling” Ильяна Георгиева и Маркоса Фахандо из Solid Angle.

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

Я реализовал простую (неполную имитацию отжига, больше напоминающую случайное блуждание) и довольно медленную версию, поддерживащую одно-, двух- и трёхмерные массивы с соединением краёв: https://github.com/bartwronski/BlueNoiseGenerator/

Как это обычно и бывает с техниками глобальной оптимизации, выполнение может занять огромную кучу времени! Я экспериментировал с моей наивной реализацией для 3D-массивов, и мой трёхлетний MacBook после выполнения её в течение всей ночи обеспечил схождение алгоритма к наилучшему среднему качественному ряду. Однако этот пост не о самом алгоритме (который на самом деле замечателен и довольно прост в реализации), а о дизеринге и шуме.

Для этого поста я сгенерировал при помощи своей реализации одномерный ряд из 2000 элементов.

Вот график первых 64 элементов:

Выглядит довольно неплохо! Никакой скученности, достаточно хорошее распределение.

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

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

Highpass and remap (чёрный) и техника Solid Angle (красный).

Мы видим, что при дизеринге одномерного сигнала они сравнимы со всеми остальными техниками:

Каждая нечётная строка — это сырые данные. Чётные строки: белый шум, ряд золотого сечения, highpass and remap и сгенерированный ряд синего шума.

Мне кажется, что он лучший и наиболее равномерный (на одном уровне с рядом золотого сечения).

Можно рассмотреть их частотный спектр погрешностей:

Чёрный — белый шум. Красный — ряд золотого сечения. Зелёный — highpass and remap. Жёлтый — сгенерированный ряд.

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

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

Ряд золотого сечения,
Синий шум, сгенерированный по технике Solid Angle,
Синий шум, сгенерированный highpass and remap,
Белый шум.

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

Подведём итог

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

Ссылки

https://www.graphics.rwth-aachen.de/media/papers/jgt.pdf “Golden Ratio Sequences For Low-Discrepancy Sampling”, Colas Schretter and Leif Kobbelt

“Physically Based Rendering, Third Edition: From Theory to Implementation”, Matt Pharr, Wenzel Jakob and Greg Humphreys.

https://en.wikipedia.org/wiki/Colors_of_noise#Blue_noise

http://gpuopen.com/vdr-follow-up-fine-art-of-film-grain/ “Fine art of film grain”, Timothy Lottes

“Blue-noise Dithered Sampling”, Iliyan Georgiev and Marcos Fajardo

Дизеринг 2: ряд золотого сечения, синий шум и highpass-and-remap