Упорядоченное сглаживание

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

Характерные 17 шаблонов упорядоченной матрицы дизеринга 4×4 можно ясно увидеть при использовании только двух цветов: черного и белого. Каждый узор отображается над соответствующим неразмытым оттенком.

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

Карта порогов

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

Первые пороговые карты были разработаны вручную, чтобы минимизировать разницу восприятия между изображением в оттенках серого и его двухбитным квантованием для матрицы размером до 4x4. ^[1]

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

\mathbf {M} ={\frac {1}{4}}\times {\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}

\mathbf {M} ={\frac {1}{16}}\times {\begin{bmatrix}0&8&2&10\\12&4&14&6\\3&11&1&9\\15&7&13&5\\\end{bmatrix}}

\mathbf {M} ={\frac {1}{64}}\times {\begin{bmatrix}0&32&8&40&2&34&10&42\\48&16&56&24&50&18&58&26\\12&44&4&36&14&46&6&38\\60&28&52&20&62&30&54&22\\3&35&11&43&1&33&9&41\\51&19&59&27&49&17&57&25\\15&47&7&39&13&45&5&37\\63&31&55&23&61&29&53&21\\\end{bmatrix}}

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

\mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}\times {\begin{bmatrix}(2n)^{2}\times \mathbf {M} _{n}&(2n)^{2}\times \mathbf {M} _{n}+2\\(2n)^{2}\times \mathbf {M} _{n}+3&(2n)^{2}\times \mathbf {M} _{n}+1\end{bmatrix}}

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

Эту функцию также можно выразить, используя только битовую арифметику: ^[3]

M(i, j) = bit_reverse(bit_interleave(bitwise_xor(i, j), i)) / n ^ 2

Предварительно рассчитанные карты порогов

Вместо того, чтобы хранить карту порогов в виде матрицы $n$ × $n$ целые числа от 0 до $n^{2}$ В зависимости от конкретного оборудования, используемого для выполнения сглаживания, может оказаться полезным предварительно рассчитать пороговые значения карты в формате с плавающей запятой, а не в традиционном формате целочисленной матрицы, показанном выше.

Для этого можно использовать следующую формулу:

Mpre(i,j) = Mint(i,j) / n^2

Это генерирует стандартную пороговую матрицу.

для карты 2×2:

{\frac {1}{4}}\times {\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}

это создает предварительно рассчитанную карту:

{\begin{bmatrix}0.0&0.5\\0.75&0.25\\\end{bmatrix}}

Кроме того, нормализацию значений для усреднения их суммы до 0 (как это сделано в алгоритме сглаживания, показанном ниже) можно выполнить и во время предварительной обработки, вычитая 1 ⁄ 2 от каждого значения:

Mpre(i,j) = Mint(i,j) / n^2 – 0.5

создание заранее рассчитанной карты:

{\begin{bmatrix}-0.5&0.0\\0.25&-0.25\\\end{bmatrix}}

Алгоритм

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

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

Два изображения, имитирующие градиент 140 × 140 = 19600 разных цветов. Оба изображения используют одни и те же 64 цвета. Изображение справа было размытым. Сглаживание выполнялось с использованием ненормализующего алгоритма сглаживания, в результате чего в изображении было небольшое перепредставление ярких пикселей.

Другими словами, алгоритм выполняет следующее преобразование для каждого цвета $c$ каждого пикселя: $c'=\mathrm {nearest\_palette\_color} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-1/2\right){\mathclose {}}\right)$ где $M (i, j)$ — карта порогов в $i$ -й строке и $j$ -м столбце, $c ’$ — преобразованный цвет, а $r$ — величина разброса в цветовом пространстве. Предполагая палитру RGB с $2 3 Н$ равномерно распределенные цвета, где каждый цвет (тройка значений красного, зеленого и синего) представлен октетом от 0 до 255, обычно выбирают ${\textstyle r\approx {\frac {255}{N}}}$ . ( 1 ⁄ 2 снова является нормирующим членом.)

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

Значения, считанные из карты порогов, предпочтительно должны масштабироваться в том же диапазоне, что и минимальная разница между отдельными цветами в целевой палитре. Аналогичным образом, размер выбранной карты должен быть равен или превышать соотношение исходных цветов к целевым цветам. Например, при квантовании изображения с разрешением 24 бит на пиксель до 15 бит на пиксель (от 256 цветов на канал до 32 цветов на канал) наименьшая карта, которую можно выбрать, будет 4×2 для соотношения 8 (256:32). Это позволяет выразить каждый отдельный тон входного сигнала с помощью различных шаблонов дизеринга. ^{[ нужна ссылка ]}

Переменная палитра: сглаживание узора

Небайеровские подходы

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

Полутона

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

Пустота и скопление

Алгоритм Void и кластера использует предварительно сгенерированный синий шум в качестве матрицы для процесса сглаживания. ^[4] Матрица синего шума сохраняет хорошие высокие частоты Байера, но при более равномерном покрытии всех задействованных частот демонстрирует гораздо меньшую степень структурирования. ^[5]

Метод «пустоты и кластеры» получил свое название от процедуры генерации матрицы, при которой черное изображение со случайно инициализированными белыми пикселями размывается по Гауссу, чтобы найти самые яркие и самые темные части, соответствующие пустотам и кластерам. После того, как несколько замен равномерно распределили светлые и темные части, пиксели нумеруются по важности. Для генерации матрицы синего шума требуются значительные вычислительные ресурсы: на современном компьютере матрица размером 64×64 требует пару секунд при использовании оригинального алгоритма. ^[6]

Этот алгоритм можно расширить для создания анимированных масок дизеринга, которые также учитывают ось времени. Это делается путем запуска алгоритма в трех измерениях и использования ядра, которое является произведением двумерного ядра Гаусса на плоскости XY и одномерного ядра Гаусса на оси Z. ^[7]

Ссылки

^ Липпель, Курляндия (декабрь 1971 г.). «Влияние дизеринга на квантование яркости изображений» . Транзакции IEEE по коммуникационным технологиям . 19 (6): 879–888.
^ Байер, Брайс (11–13 июня 1973 г.). «Оптимальный метод двухуровневого воспроизведения однотонных изображений» (PDF) . Международная конференция IEEE по коммуникациям . 1 :11–15. Архивировано из оригинала (PDF) 12 мая 2013 г. Проверено 19 июля 2012 г.
^ Джоэл Илилуома. « Алгоритм позиционного дизеринга произвольной палитры »
^ Улични, Роберт А. (1993). «Метод пустоты и кластера для создания массива дизеринга» (PDF) . Проверено 11 февраля 2014 г.
^ Вронски, Барт (31 октября 2016 г.). «Сглаживание, часть третья – сглаживание при двумерном квантовании в реальном мире» .
^ Питерс, Кристоф. «Бесплатные текстуры синего шума» . Momentsingraphics.de .
^ Вулф, Алан; Моррикаль, Натан; Акенине-Мёллер, Томас; Рамамурти, Рави (2022). Пространственно-временные маски синего шума . Ассоциация еврографики. дои : 10.2312/ср.20221161 . ISBN 978-3-03868-187-8 . S2CID 250164404 .

Ordered Dithering (курсовой проект по графике, лаборатория Visgraf, Бразилия)
Алгоритмы сглаживания (Ли Дэниел Крокер, Пол Буле и Майк Морра)

Дальнейшее чтение

Анчин, Хакан; Бхаттачарджья, Ануп К.; Шу, Джозеф С. (2 января 1998 г.). Беретта, Джордано Б.; Эшбах, Райнер (ред.). «Улучшение пустот и кластеров для лучшей однородности полутонов». Электронная визуализация Photonics West '98 . Цветное изображение: цвет, независимый от устройства, цветная печатная копия и графика III. 3300 : 321–329. Бибкод : 1998SPIE.3300..321A . CiteSeerX 10.1.1.40.5331 . дои : 10.1117/12.298295 . S2CID 6219511 .

Внешние ссылки

Реализация в Matlab различных методов дизеринга
anim8gdx , Java-реализация различных (в основном упорядоченных) методов сглаживания

[lippelkurland-1] Липпель, Курляндия (декабрь 1971 г.). «Влияние дизеринга на квантование яркости изображений» . Транзакции IEEE по коммуникационным технологиям . 19 (6): 879–888.

[bayermatrix-2] Байер, Брайс (11–13 июня 1973 г.). «Оптимальный метод двухуровневого воспроизведения однотонных изображений» (PDF) . Международная конференция IEEE по коммуникациям . 1 :11–15. Архивировано из оригинала (PDF) 12 мая 2013 г. Проверено 19 июля 2012 г.

[3] Джоэл Илилуома. « Алгоритм позиционного дизеринга произвольной палитры »

[voidcluster-4] Улични, Роберт А. (1993). «Метод пустоты и кластера для создания массива дизеринга» (PDF) . Проверено 11 февраля 2014 г.

[5] Вронски, Барт (31 октября 2016 г.). «Сглаживание, часть третья – сглаживание при двумерном квантовании в реальном мире» .

[6] Питерс, Кристоф. «Бесплатные текстуры синего шума» . Momentsingraphics.de .

[7] Вулф, Алан; Моррикаль, Натан; Акенине-Мёллер, Томас; Рамамурти, Рави (2022). Пространственно-временные маски синего шума . Ассоциация еврографики. дои : 10.2312/ср.20221161 . ISBN 978-3-03868-187-8 . S2CID 250164404 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]