Упорядоченное сглаживание
Алгоритм сглаживания изображения
В этом примере слева показана исходная фотография. Версия справа демонстрирует эффект квантования до 16 цветов и дизеринга с использованием упорядоченного шаблона дизеринга 8×8.
Характерные 17 шаблонов упорядоченной матрицы дизеринга 4×4 можно ясно увидеть, если использовать только два цвета, черный и белый. Каждый шаблон показан над соответствующим недизеринговым оттенком.

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

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

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

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

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

М 2 = 1 4 [ 0 2 3 1 ] {\displaystyle \mathbf {M_{2}} ={\frac {1}{4}}{\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}}
М 4 = 1 16 [ 0 8 2 10 12 4 14 6 3 11 1 9 15 7 13 5 ] {\displaystyle \mathbf {M_{4}} ={\frac {1}{16}}{\begin{bmatrix}0&8&2&10\\12&4&14&6\\3&11&1&9\\15&7&13&5\\\end{bmatrix}}}
М 8 = 1 64 [ 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 ] {\displaystyle \mathbf {M_{8}} ={\frac {1}{64}}{\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}}}

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

M 2 n = 1 ( 2 n ) 2 [ ( 2 n ) 2 M n ( 2 n ) 2 M n + 2 J n ( 2 n ) 2 M n + 3 J n ( 2 n ) 2 M n + J n ] = J 2 ⊗ M n + 1 n 2 M 2 ⊗ J n , {\displaystyle \mathbf {M} _{2n}={\frac {1}{(2n)^{2}}}{\begin{bmatrix}(2n)^{2}\mathbf {M} _{n}&(2n)^{2}\mathbf {M} _{n}+2\mathbf {J} _{n}\\(2n)^{2}\mathbf {M} _{n}+3\mathbf {J} _{n}&(2n)^{2}\mathbf {M} _{n}+\mathbf {J} _{n}\end{bmatrix}}=\mathbf {J} _{2}\otimes \mathbf {M} _{n}+{\frac {1}{n^{2}}}\mathbf {M} _{2}\otimes \mathbf {J} _{n},}

где — матрицы из единиц , а — произведение Кронекера . J n {\displaystyle \mathbf {J} _{n}} n × n {\displaystyle n\times n} ⊗ {\displaystyle \otimes }

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

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

M(i, j) = битовое_обратное(битовое_чередование(побитовое_исключающее_ИЛИ(i, j), i)) / n ^ 2

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

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

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

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

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

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

1 4 [ 0 2 3 1 ] {\displaystyle {\frac {1}{4}}{\begin{bmatrix}0&2\\3&1\\\end{bmatrix}}}

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

[ 0.0 0.5 0.75 0.25 ] {\displaystyle {\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 * maxValue

создание предварительно рассчитанной карты:

[ − 0.375 0.125 0.375 − 0.125 ] {\displaystyle {\begin{bmatrix}-0.375&0.125\\0.375&-0.125\\\end{bmatrix}}}

Алгоритм

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

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

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

Другими словами, алгоритм выполняет следующее преобразование для каждого цвета c каждого пикселя: где M ( i , j ) — пороговая карта в i -й строке и j -м столбце, c ′ — преобразованный цвет, а r — величина разброса в цветовом пространстве. Предполагая палитру RGB с 2 3 N равномерно разнесенными цветами, где каждый цвет (тройка значений красного, зеленого и синего) представлена ​​октетом от 0 до 255, обычно выбирают . ( 1 ⁄ 2 — снова нормализующий член.) c ′ = n e a r e s t _ p a l e t t e _ c o l o r ( c + r × ( M ( x mod n , y mod n ) − 1 / 2 ) ) {\displaystyle c'=\mathrm {nearest\_palette\_color} {\mathopen {}}\left(c+r\times \left(M(x{\bmod {n}},y{\bmod {n}})-1/2\right){\mathclose {}}\right)} r ≈ 255 N {\textstyle r\approx {\frac {255}{N}}}

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

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

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

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

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

Полутона

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

Пустота и кластер

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

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

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

Имитация отжига

Имитация отжига может генерировать маски дизеринга, начиная с плоской гистограммы и меняя значения для оптимизации функции потерь. Функция потерь управляет спектральными свойствами маски, позволяя ей создавать синий шум или шумовые паттерны, предназначенные для фильтрации определенными фильтрами. Алгоритм также может быть расширен с течением времени для анимированных масок дизеринга с выбранными временными свойствами. [8]

Ссылки

  1. ^ Липпель, Курланд (декабрь 1971 г.). «Влияние дизеринга на квантование яркости изображений». Труды IEEE по коммуникационным технологиям . 19 (6): 879– 888. doi :10.1109/TCOM.1971.1090773.
  2. ^ Bayer, Bryce (11–13 июня 1973 г.). «Оптимальный метод двухуровневой передачи изображений с непрерывным тоном» (PDF) . Международная конференция IEEE по коммуникациям . 1 : 11–15 . Архивировано из оригинала (PDF) 2013-05-12 . Получено 2012-07-19 .
  3. ^ Джоэл Илилуома. «Алгоритм позиционного дизеринга с произвольной палитрой»
  4. ^ Ulichney, Robert A (1993). "Метод пустоты и кластера для генерации массива дизеринга" (PDF) . Получено 2014-02-11 .
  5. ^ Вронски, Барт (31 октября 2016 г.). «Дизеринг, часть третья – дизеринг реального мира с двумерным квантованием».
  6. ^ Питерс, Кристоф. "Бесплатные текстуры синего шума". momentsingraphics.de .
  7. ^ Вулф, Алан; Моррикал, Натан; Акенин-Мёллер, Томас; Рамамурти, Рави (2022). Пространственно-временные маски синего шума. Ассоциация Eurographics. doi :10.2312/sr.20221161. ISBN 978-3-03868-187-8. S2CID  250164404.
  8. ^ Доннелли, Уильям; Вулф, Алан; Бютепаж, Джудит; Вальдес, Джон (2024). «FAST: Адаптированная к фильтру пространственно-временная выборка для рендеринга в реальном времени». Труды ACM по компьютерной графике и интерактивным технологиям . 7 (1). doi :10.1145/3651283.
  • Упорядоченное сглаживание (проект курса «Графика», лаборатория Visgraf, Бразилия)
  • Алгоритмы дизеринга (Ли Дэниел Крокер, Пол Булай и Майк Морра)

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

  • Ancin, Hakan; Bhattacharjya, Anoop K.; Shu, Joseph S. (2 января 1998 г.). Beretta, Giordano B.; Eschbach, Reiner (ред.). «Улучшение пустоты и кластера для лучшей однородности полутонов». Photonics West '98 Electronic Imaging . Color Imaging: Device-Independent Color, Color Hardcopy, and Graphic Arts III. 3300 : 321– 329. Bibcode :1998SPIE.3300..321A. CiteSeerX  10.1.1.40.5331 . doi :10.1117/12.298295. S2CID  6219511.
  • Реализация различных методов дизеринга в Matlab
  • anim8gdx, реализация на Java различных (в основном упорядоченных) методов дизеринга
Retrieved from "https://en.wikipedia.org/w/index.php?title=Ordered_dithering&oldid=1269448413"