Дизеринг что это в фотошопе
Что такое дизеринг в обработке изображений?
Узнайте, как это относится к градиентам цвета
Независимо от того, являетесь ли вы веб-дизайнером, художником-графиком или даже электронным музыкантом, сглаживание играет жизненно важную роль в творческом процессе. Дизеринг при обработке изображений – это метод, используемый для имитации цветов или затенения. Основной концепцией дизеринга является добавление шума или дополнительных пикселей в цифровой файл. В графике сглаживание добавляет случайные структуры пикселей для улучшения качества изображения, избегая полосатости.
История дизеринга
В основном забытое, одно из самых ранних применений дизеринга было во Второй мировой войне для траекторий бомбардировок и навигации. Это использование сильно отличается от размывания, как мы его знаем сегодня. Широко использовавшийся в печатном прессе как для газет, так и для комиксов, с появлением Всемирной паутины возникло сглаживание. Мы знаем, что до того, как интернет стал блестящим глазным леденцом, почти все сайты были текстовыми. Скорость набора номера в режиме улитки позволяла загружать графику только на ужасно медленных скоростях. Однако, когда вычисления расширились до 8-битного цвета с мониторами, графика и сглаживание вышли на передний план для Интернета.
Как использовался дизеринг в прошлом
При более раннем использовании в газетах, комиксах и других печатных СМИ к изображениям применялось сглаживание для создания уровней имитации серой шкалы путем стратегического размещения черных точек. Использование процесса сглаживания даст гладкое изображение с серыми оттенками, даже если печатные машины поддерживают только черные чернила. Комиксы и другая цветная печать работали аналогично, но имитировали больше оттенков цвета, чем печатные машины с ограниченной палитрой. Ниже приведен пример того, как печатные машины обрабатывают высококачественные изображения в размытое изображение. Обратите внимание, что вы по-прежнему можете видеть различные цвета и тени, но изображение гораздо более пиксельное.
В последнее время дизеринг стал популярным в веб-графике. Несмотря на то, что большая часть населения имеет доступ к высокоскоростному Интернету, все еще остается скромный процент пользователей Интернета, которые зависят от коммутируемого доступа. Использование сглаживания в обработке изображений не только уменьшает полосу цветов и затенение, что создает более гладкое законченное изображение, но также уменьшает размер файла. Первое изображение является полосатым изображением. Вы можете ясно видеть переходы в цвете.
Второе изображение представляет собой плавный градиент, в котором применено сглаживание. Полоски больше не видны и создают более плавное изображение.
Одним из ключевых применений для сглаживания было предотвращение появления полос любого цвета или градиента оттенка. Смешивая оттенки из ограниченной палитры для имитации исходного цвета, вы уменьшаете файл, создавая файл, который может быстрее загружаться на ваш экран и \ или компьютер. GIF-файлы являются отличным примером сглаживания изображений. Меньшие файлы требуют меньшей пропускной способности, что обеспечивает более быструю передачу. В первые дни Интернета дизеринг был лучшим другом веб-дизайнера. Они могли бы создавать более визуально привлекательные веб-сайты, в то же время поддерживая более медленные соединения для передачи данных.
Дизеринг в печати
Хотя ограничения старых 8-битных и 16-битных мониторов больше не являются проблемой, а технологические усовершенствования намного превзошли необходимость сглаживания, сегодня они все еще пользуются популярностью. Многие модели домашних принтеров используют дизеринг. Главным образом это снижает стоимость эксплуатации принтера и снижает стоимость самого принтера. Струйные принтеры специально распыляют микроскопические точки на бумаге, производя различные цвета и оттенки. Даже монохромные принтеры переведут цветную фотографию в размытое черное изображение, чтобы создать черно-белую копию изображения.
Дизеринг в фотошопе
Вот оригинальное черно-белое фото. В то время как хорошая фотография, добавив некоторые текстуры и цветовые заливки, Photoshop может преобразовать это изображение в художественно размытое изображение, как показано ниже:
Наложение рисунка из бумаги Pastel Paper с заливкой цветом имитируемого оттенка сепии в Photoshop резко меняет внешний вид фотографии.
Что такое дизеринг в обработке изображений?
Узнайте, как это относится к градиентам цвета
Независимо от того, являетесь ли вы веб-дизайнером, художником-графиком или даже электронным музыкантом, сглаживание играет жизненно важную роль в творческом процессе. Дизеринг при обработке изображений – это метод, используемый для имитации цветов или затенения. Основной концепцией дизеринга является добавление шума или дополнительных пикселей в цифровой файл. В графике сглаживание добавляет случайные структуры пикселей для улучшения качества изображения, избегая полосатости.
История дизеринга
В основном забытое, одно из самых ранних применений дизеринга было во Второй мировой войне для траекторий бомбардировок и навигации. Это использование сильно отличается от размывания, как мы его знаем сегодня. Широко использовавшийся в печатном прессе как для газет, так и для комиксов, с появлением Всемирной паутины возникло сглаживание. Мы знаем, что до того, как интернет стал блестящим глазным леденцом, почти все сайты были текстовыми. Скорость набора номера в режиме улитки позволяла загружать графику только на ужасно медленных скоростях. Однако, когда вычисления расширились до 8-битного цвета с мониторами, графика и сглаживание вышли на передний план для Интернета.
Как использовался дизеринг в прошлом
При более раннем использовании в газетах, комиксах и других печатных СМИ к изображениям применялось сглаживание для создания уровней имитации серой шкалы путем стратегического размещения черных точек. Использование процесса сглаживания даст гладкое изображение с серыми оттенками, даже если печатные машины поддерживают только черные чернила. Комиксы и другая цветная печать работали аналогично, но имитировали больше оттенков цвета, чем печатные машины с ограниченной палитрой. Ниже приведен пример того, как печатные машины обрабатывают высококачественные изображения в размытое изображение. Обратите внимание, что вы по-прежнему можете видеть различные цвета и тени, но изображение гораздо более пиксельное.
В последнее время дизеринг стал популярным в веб-графике. Несмотря на то, что большая часть населения имеет доступ к высокоскоростному Интернету, все еще остается скромный процент пользователей Интернета, которые зависят от коммутируемого доступа. Использование сглаживания в обработке изображений не только уменьшает полосу цветов и затенение, что создает более гладкое законченное изображение, но также уменьшает размер файла. Первое изображение является полосатым изображением. Вы можете ясно видеть переходы в цвете.
Второе изображение представляет собой плавный градиент, в котором применено сглаживание. Полоски больше не видны и создают более плавное изображение.
Одним из ключевых применений для сглаживания было предотвращение появления полос любого цвета или градиента оттенка. Смешивая оттенки из ограниченной палитры для имитации исходного цвета, вы уменьшаете файл, создавая файл, который может быстрее загружаться на ваш экран и \ или компьютер. GIF-файлы являются отличным примером сглаживания изображений. Меньшие файлы требуют меньшей пропускной способности, что обеспечивает более быструю передачу. В первые дни Интернета дизеринг был лучшим другом веб-дизайнера. Они могли бы создавать более визуально привлекательные веб-сайты, в то же время поддерживая более медленные соединения для передачи данных.
Дизеринг в печати
Хотя ограничения старых 8-битных и 16-битных мониторов больше не являются проблемой, а технологические усовершенствования намного превзошли необходимость сглаживания, сегодня они все еще пользуются популярностью. Многие модели домашних принтеров используют дизеринг. Главным образом это снижает стоимость эксплуатации принтера и снижает стоимость самого принтера. Струйные принтеры специально распыляют микроскопические точки на бумаге, производя различные цвета и оттенки. Даже монохромные принтеры переведут цветную фотографию в размытое черное изображение, чтобы создать черно-белую копию изображения.
Дизеринг в фотошопе
Вот оригинальное черно-белое фото. В то время как хорошая фотография, добавив некоторые текстуры и цветовые заливки, Photoshop может преобразовать это изображение в художественно размытое изображение, как показано ниже:
Наложение рисунка из бумаги Pastel Paper с заливкой цветом имитируемого оттенка сепии в Photoshop резко меняет внешний вид фотографии.
Дизеринг: зашумляем сигнал, чтобы улучшить его
Введение
В первой части этой серии статей мы рассмотрим теоретическую сторону дизеринга, немного истории и применение его к 1D-сигналам и дискретизации. Я попытаюсь провести частотный анализ ошибок дискретизации и расскажу о том, как дизеринг помогает их исправить. В основном это будет теоретическая статья, поэтому если вам интересны более практические применения, то ждите следующих частей.
Блокнот Mathematica для воспроизведения результатов можно найти здесь, а pdf-версия находится здесь.
Что такое дизеринг?
Дизеринг (Dithering) можно описать как намеренное/осознанное внесение в сигнал шума для предотвращения ошибок большого масштаба/низкого разрешения, возникающих вследствие дискретизации или субдискретизации.
Если вы когда-нибудь работали с:
Однако я обнаружил в Википедии довольно удивительный факт о том, как впервые был определён и использован дизеринг:
— Кен Полманн, Principles of Digital Audio
Это вдохновляющий и интересный исторический факт и мне понятно, почему он позволяет избегать отклонений в вычислениях и резонансах, случайным образом разрушая циклы обратной связи механической вибрации.
Но хватит истории, давайте для начала рассмотрим процесс дизеринга в 1D-сигналах, например, в аудио.
Дискретизация дизерингом постоянного сигнала
Мы начнём с анализа самого скучного в мире сигнала — постоянного сигнала. Если вы знаете немного о цифровой обработке сигналов, связанных со звуком, то можете сказать: но ты же обещал рассмотреть аудио, а в звуке по определению нет постоянной составляющей! (Более того, и в ПО, и в оборудовании обработки звука намеренно устраняется так называемый сдвиг постоянной составляющей (DC offset).)
Это правда, и вскоре мы рассмотрим более сложные функции, но начнём мы сначала.
Представьте, что мы выполняем 1-битную дискретизацию нормализованного сигнала с плавающей запятой. Это значит, что мы имеем дело только с конечными двоичными значениями, 0 или 1.
Если сигнал равен 0,3, то простое округление без дизеринга будет самой скучной функцией — просто нулём!
Погрешность тоже постоянна и равна 0,3, следовательно, и средняя погрешность равна 0,3. Это означает, что мы внесли довольно большое отклонение в сигнал и полностью потеряли информацию исходного сигнала.
Мы можем попробовать выполнить дизеринг этого сигнала и посмотреть на результаты.
Дизеринг в этом случае (при использовании функции округления) просто применяет обычный случайный белый шум (случайное значение для каждого элемента, что создаёт равномерный спектр шума) и прибавляет в сигнал перед дискретизацией случайное в интервале (-0.5, 0.5).
quantizedDitheredSignal =
Round[constantSignalValue + RandomReal[] – 0.5] & /@ Range[sampleCount];
Здесь сложно что-то увидеть, теперь результат дискретизации — это просто набор случайных единиц и нулей. С (ожидаемо) большим количеством нулей. Сам по себе этот сигнал не особо интересен, однако довольно интересен график погрешностей и средняя погрешность.
Итак, как мы и ожидали, погрешность тоже варьируется, но пугает то, что погрешность иногда стала больше (абсолютное значение 0,7)! То есть максимальная погрешность к сожалению стала хуже, однако средний шум имеет значение:
Намного лучше, чем первоначальная погрешность в 0,3. При значительно большом количестве сэмплов эта погрешность будет стремиться к нулю (к пределу). Итак, погрешность постоянной составляющей стала намного меньше, но давайте взглянем на частотный график всех погрешностей.
Красный график/всплеск = частотный спектр погрешности при отсутствии дизеринга (постоянный сигнал без частот). Чёрный — с дизерингом при помощи белого шума.
Всё становится интереснее! Это демонстрирует первый вывод из этого поста — дизеринг распределяет погрешность/отклонение дискретизации среди множества частот.
В следующем разделе мы узнаем, как это нам поможет.
Частотная чувствительность и низкочастотная фильтрация
Выше мы наблюдали за дизерингом дискретизированного постоянного сигнала:
Более того, наши медиаустройства становятся всё лучше и лучше, обеспечивая большую избыточную дискретизацию (oversampling). Например, в случае телевизоров и мониторов у нас есть технология «retina» и 4K-дисплеи (на которых невозможно разглядеть отдельный пиксель), в области звука мы используем форматы файлов с дискретизацией не менее 44 кГц даже для дешёвых динамиков, которые часто не могут воспроизводить больше, чем 5-10 кГц.
Это значит, что мы можем аппроксимировать воспринимаемый внешний вид сигнала, выполнив его низкочастотную фильтрацию. На графике я выполнил низкочастотную фильтрацию (заполнение нулями слева — это «нарастание»):
Красный — желаемый недискретизированный сигнал. Зелёный — дискретизированный сигнал с дизерингом. Синий — низкочастотный фильтр этого сигнала.
Сигнал начинает выглядеть гораздо более близким к исходной, недискретизированной функции!
К сожалению, мы начинаем видеть низкие частоты, которые очень заметны и отсутствуют в исходном сигнале. В третьей части серии мы попробуем исправить при помощи синего шума. А пока вот как график может выглядеть с функцией псевдо-шума, имеющей содержимое с гораздо меньшей частотой:
Это возможно, потому что наша псевдослучайная последовательность имеет следующий спектр частот:
Но давайте закончим рассматривать простые, постоянные функции. Взглянем на синусоиду (если вы знакомы с теоремой Фурье, то знаете, что она является строительным блоком любого периодического сигнала!).
Дискретизация синусоиды
Если мы дискретизируем синусоиду 1-битной дискретизацией, то получим простой прямоугольный сигнал.
Прямоугольный сигнал довольно интересен, потому что включает в себя и базовую частоту, и нечётные гармоники.
Это интересное свойство, которое активно используется в аналоговых субтрактивных синтезаторах для создания звучания полых/медных инструментов. Субтрактивный синтез берёт сложный, гармонически богатый звук и фильтрует его, устраняя некоторые частоты (параметры фильтра варьируются со временем), чтобы придать звукам нужную форму.
Спектр частот прямоугольного сигнала:
Но в этом посте нас больше интересую погрешности дискретизации! Давайте создадим график погрешности, а также спектр частот погрешности:
В этом случае ситуация гораздо лучше — средняя погрешность близка к нулю! К сожалению, у нас по-прежнему присутствует множество нежелательных низких частот, очень близких к нашей основной частоте (нечётных множителей с уменьшающейся величиной). Это явление называется алиасингом или шумом дизеринта — возникают частоты, отсутствовавшие в исходном сигнале, и они имеют довольно большие величины.
Даже низкочастотная фильтрация не сможет значительно помочь сигналу. Погрешность имеет очень много низких частот:
Дискретизированная синусоида с низкочастотной фильтрацией
Погрешность дискретизированной синусоиды с низкочастотной фильтрацией
Давайте взглянем, как меняется ситуация при добавлении дизеринга. На первый взгляд, улучшений почти нет:
Однако если мы рассмотрим это как изображение, то оно начинает выглядеть лучше:
Заметьте, что погрешности дискретизации снова распределены среди различных частот:
Выглядит очень многообещающе! Особенно учитывая то, что теперь мы можем попробовать выполнить фильтрацию:
Это немного искажённая синусоида, но она выглядит намного ближе к исходной, чем версия без дизеринга, за исключением фазового сдвига, внесённого асимметричным фильтром (я не буду объяснять этого здесь; скажу только, что проблему можно устранить, применив симметричные фильтры):
Красный — исходная синусоида. Зелёный — подвергнутый низкочастотной фильтрации сигнал без дизеринга. Синий — подвергнутый низкочастотной фильтрации сигнал с дизерингом.
Графики обеих погрешностей численно подтверждают, что погрешность намного меньше:
Красный — погрешность подвергнутого низкочастотной фильтрации сигнала без дизеринга. Синий — погрешность подвергнутого низкочастотной фильтрации сигнала с дизерингом.
Наконец, давайте вкратце рассмотрим сигнал с более качественной функцией дизеринга, содержащей только высокие частоты:
Верхнее изображение — функция белого шума. Нижнее изображение — функция, содержащая более высокие частоты.
Версия с низкочастотной фильтрацией, дизерингом и улучшенной функцией — почти идеальные результаты, если не учитывать фазовый сдвиг, вызванный фильтром!
И наконец, сравнение всех трёх спектров погрешностей:
Красный — спектр погрешности дискретизации без дизеринга. Чёрный — спектр погрешности дискретизации с дизерингом белым шумом. Синий — спектр погрешности дискретизации с дизерингом с более высокими частотами.
На этом первая часть серии заканчивается. Основные выводы:
Псевдотонирование изображений: одиннадцать алгоритмов и исходники
Псевдотонирование: обзор
Про сегодняшнюю тему для программирования графики — псевдотонирование (дизеринг, псевдосмешение цветов) — я получаю много писем, что может показаться удивительным. Вы можете подумать, что псевдотонирование — это не то, чем программисты должны заниматься в 2012 году. Разве псевдосмешение — не артефакт история технологий, архаизм времён, когда дисплей с 16 миллионами цветов программистам и пользователям мог только сниться? Почему я пишу статью о псевдотонировании в эпоху, когда дешевые мобильные телефоны работают с великолепием 32-битной графики?
На самом деле псевдотонирование по-прежнему остаётся уникальным методом не только по практическим соображениям (например, подготовка полноцветного изображения для печати на чёрно-белом принтере), но и по художественным. Дизеринг также находит применение в веб-дизайне, где этот полезный метод используется для сокращения числа цветов изображения, что уменьшает размер файла (и трафик) без ущерба для качества. Он также используется при уменьшении цифровых фотографий в формате RAW в 48 или 64 бита на пиксель до RGB в 24 бита на пиксель для редактирования.
И это — применения лишь в области изображений. В звуке дизеринг тоже играет ключевую роль, но боюсь, обсуждать здесь дизеринг аудио я не буду. Только псевдотонирование изображений.
В этой статье я собираюсь сосредоточиться на трех пунктах:
Псевдотонирование: примеры
Рассмотрим следующее полноцветное изображение, обои со знаменитым Кубом-Компаньоном из игры Portal:
Эта картинка будет тестовым изображением для этой статьи. Я выбрал её, потому что у неё есть отличные сочетания мягких градиентов и жестких краев.
На современном ЖК- или светодиодном дисплее — будь то монитор компьютера, смартфон или телевизор — это полноцветное изображение можно выводить без проблем. Но представим ПК постарее с поддержкой ограниченной палитры цветов. Если мы попытаемся отобразить наше изображение на таком ПК, это может выглядеть примерно так:
Это то же изображение, что и выше, но ограниченное веб-палитрой безопасных цветов.
Довольно мерзотно, не так ли? Рассмотрим еще более яркий пример, в котором мы хотим напечатать изображение куба на чёрно-белом принтере. Тогда у нас получается что-то подобное:
Здесь изображение едва узнаваемо.
Проблемы возникают каждый раз, когда изображение отображается на устройстве, которое поддерживает меньше цветов, чем содержит изображение. Тонкие градиенты в исходном изображении могут быть заменены пятнами однородного цвета, и в зависимости от ограничений устройства, исходное изображение может стать неузнаваемым.
Псевдотонирование (или дизеринг) — это попытка решить эту проблему. Псевдотонирование работает через приближённое выражение недоступных цветов доступными, для чего доступные цвета смешиваются так, чтобы имитировать недоступные. В качестве примера здесь приведено изображение куба, вновь ухудшенное до цветов воображаемого старого ПК, только на этот раз применено псевдотонирование:
Значительно лучше, чем в версии без псевдотонирования!
Если вы внимательно посмотрите, вы увидите, что это изображение использует те же цвета, что и его копия без псевдотонирования. Но эти несколько цветов расположены так, что кажется, будто присутствует много других цветов.
В качестве другого примера: здесь чёрно-белая версия нашего изображения с похожим псевдотонированием:
Если говорить конкретно, то здесь применено псевдотонирование по двухрядном алгоритму Сьерры (2-row Sierra).
Несмотря на наличие только чёрного и белого цветов, мы всё ещё можем различить форму куба вплоть до сердец с обеих сторон. Дизеринг — чрезвычайно мощный метод, и его можно использовать в ЛЮБОЙ ситуации, когда данные должны быть представлены в более низком разрешении, чем то, для которого их создавали. В этой статье основное внимание будет уделено изображениям, но те же методы могут быть применены к любым двухмерным данным (или к одномерным данным, что еще проще!).
Основная концепция псевдотонирования
Если коротко, псевдотонирование в корне связано с рассеиванием ошибок.
Рассеивание ошибок работает следующим образом: предположим, что нам нужно свести фотографию в градациях серого до чёрных и белых цветов, чтобы мы могли напечатать её на принтере, который поддерживает только чистый черный (чернила) или чистый белый (бумага без чернил) цвет. Первый пиксель на изображении — тёмно-серый, со значением 96 по шкале от 0 до 255, где 0 — чистый чёрный цвет, 255 — чистый белый.
Визуализация значений RGB в нашем примере.
При преобразовании такого пикселя в черный или белый мы используем простую формулу: значение цвета ближе к 0 (черному) или 255 (белому)? 96 ближе к 0, чем к 255, поэтому мы делаем пиксель черным.
На этом этапе стандартный подход — просто перемещаться к следующему пикселю и выполнять то же сравнение. Но проблема возникает, если у нас есть куча подобных серых пикселей со значением 96 — все они превращаются в чёрные. У нас получается с огромный кусок пустых черных пикселей, которые плохо представляют оригинальный серый цвет.
Рассеивание ошибок следует более умному подходу к проблеме. Как вы могли предположить, рассеивание ошибок работает путем «рассеивания» — или распространения — ошибки каждого вычисления в соседние пиксели. Если алгоритм находит серый пиксель со значением 96, он также определяет, что 96 ближе к 0, чем к 255 — и поэтому делает пиксель черным. Но тогда алгоритм учитывает «ошибку» в его преобразовании. В частности, ошибку в том, что серый пиксель, который мы заставили быть черным, на самом деле был на расстоянии в 96 шагов от черного.
Когда он перемещается к следующему пикселю, алгоритм рассеивания ошибок добавляет ошибку предыдущего пикселя к текущему пикселю. Если следующий пиксель также имеет серый цвет 96, вместо того, чтобы сделать его черным, алгоритм добавляет ошибку 96 из предыдущего пикселя. Это приводит к значению 192, которое на самом деле ближе к 255 — и, следовательно, ближе к белому! Таким образом, алгоритм делает этот пиксель белым и снова учитывает ошибку. В этом случае ошибка составляет −63, потому что 192 на 63 меньше, чем 255 — то значение, на которое этот пиксель поменяли.
По мере того, как алгоритм продолжает работу, рассеивание ошибок приводит к чередованию черных и белых пикселей, что довольно хорошо имитирует серый цвет значения 96 этого сегмента. Это куда лучше, чем окрашивать все пиксели подряд чёрным. Как правило, когда мы заканчиваем обработку строки изображения, мы отбрасываем значение ошибки, которое мы отслеживали, и начинаем заново с ошибкой «0» со следующей строки изображения.
Ниже приведен пример изображения нашего куба с применением описанного алгоритма. В частности, каждый пиксель преобразуется в черный или белый, ошибка преобразования отмечается и передается следующему пикселю справа:
Это самое простое применение псевдотонирования с рассеиванием ошибок.
К сожалению, псевдотонирование с рассеиванием ошибок имеет свои собственные проблемы. Как бы то ни было, псевдотонирование всегда приводит к заметным точкам или к пунктирному виду. Это неизбежный побочный эффект работы с небольшим количеством доступных цветов — из-за их количества эти цвета будут повторяться снова и снова.
В приведенном выше простом примере алгоритма рассеивания ошибок очевидна другая проблема — если у вас есть блок очень похожих цветов, и вы толкаете ошибку только вправо, все «точки» оказываются в одном и том же месте! Это приводит к забавным линиям точек, которые почти так же отвлекают, как и оригинальная версия без псевдотонирования.
Проблема в том, что мы используем только одномерное рассеивание ошибок. Распространив ошибку только в одном направлении (вправо), мы не очень хорошо её распределяем. Поскольку у изображения измерения два (горизонтальное и вертикальное), почему бы не направить ошибку в нескольких направлениях? Это распределит ошибку более равномерно, что, в свою очередь, позволит избежать странных линий точек, рассмотренных в примере рассеивания ошибок выше.
Псевдотонирование с двухмерным рассеиванием ошибок
Существует много способов рассеивания ошибки в двух измерениях. Например, мы можем распространить ошибку на один или несколько пикселей вправо, влево, вверх и вниз.
Для простоты расчетов все стандартные формулы дизеринга продвигают ошибку только вперед. Если обойти изображение попиксельно, начиная с верхнего левого угла и двигаясь вправо, учитывать ошибки назад (например, влево и/или вверх) необходимости не будет. Причина этого очевидна — если закидывать ошибку назад, придётся вернуться к пикселям, которые уже обработаны, что приводит к большему количеству ошибок при движении назад. В итоге получится бесконечный цикл распространения ошибок.
Таким образом, для стандартного поведения цикла (начиная с верхнего левого угла изображения и двигаясь вправо) мы хотим, чтобы движение пикселей шло только вправо и вниз.
Извиняюсь за паршивое изображение — но я надеюсь, что это поможет проиллюстрировать суть правильного распространения ошибок.
Что же касается конкретных способов распространения ошибки, над этой задачей билось много людей умнее меня. Позвольте мне поделиться этими формулами с вами.
(Примечание: эти формулы дизеринга доступны на нескольких сайтах в Интернете, но наиболее полный справочник из всего, что я нашел — этот.)
Алгоритм рассеивания ошибок Флойда-Стейнберга
Первая и возможно самая известная формула рассеивания ошибок была опубликована Робертом Флойдом и Луисом Стейнбергом в 1976 году. Рассеивание ошибок происходит по следующей схеме:
В приведенных выше обозначениях X означает текущий пиксель. Дробь в нижней части представляет собой делитель для ошибки. Иначе говоря, формула Флойда-Стейнберга может быть записана в виде:
Но такое обозначение длинное и неаккуратное, поэтому я буду придерживаться оригинала.
Вернёмся к нашему оригинальному примеру преобразования пиксельного значения от 96 к 0 (чёрный) или к 255 (белый). При окрашивании пикселя в чёрный мы получаем ошибку 96. Мы распространяем эту ошибку окружающим пикселям, поделив 96 на 16 ( = 6), затем умножаем её на соответствующие значения, например:
Путем распространения ошибки нескольким пикселям, каждому с различным значением, мы сводим к минимуму все отвлекающие полосы с точками, заметные в исходном примере алгоритма рассеивания ошибок. Вот изображение куба с применением алгоритма Флойда-Стейнберга:
Алгоритм рассеивания ошибок Флойда-Стейнберга
Алгоритм рассеивания ошибок Флойда-Стейнберга — вероятно, наиболее известный алгоритм рассеивания ошибок. Он даёт достаточно хорошее качество, а также требует только один передний массив (одномерный массив шириной в изображение, где хранятся значения ошибок, распространяемые к следующей строке). Кроме того, поскольку его делитель 16, вместо деления можно использовать битовые сдвиги. Так алгоритм достигает высокой скорости работы даже на старом оборудовании.
Что касается значений 1/3/5/7, используемых для распространения ошибки – они были выбраны специально, потому что они создают равномерный клетчатый узор для серого изображения. Умно!
Одно предупреждение по поводу алгоритма Флойда-Стейнберга — некоторые программы могут использовать и другие, более простые формулы псевдотонирования и называть их «Флойд-Стейнберг», надеясь, что люди не знают разницы. Вот отличная статья о дизеринге, которая описывает один из таких «ложных алгоритмов Флойда-Стейнберга»:
Этот упрощение оригинального алгоритма Флойда-Стейнберга даёт не только заметно худший результат, но и делает это без каких-либо значимых преимуществ с точки зрения скорости (или памяти, так как массив для хранения значений ошибки для следующей строки всё ещё требуется).
Но если вам интересно, вот изображение куба после прохода «ложного Флойда-Стейнберга»:
Гораздо больше скоплений точек, чем в настоящем алгоритме Флойда-Стейнберга — так что не используйте эту формулу!
Алгоритм Джарвиса, Джудиса и Нинке (Jarvis, Judice, Ninke)
В год, когда Флойд и Стейнберг опубликовали свой знаменитый алгоритм дизеринга, был издан менее известный, но гораздо более мощный алгоритм. Фильтр Джарвиса, Джудиса и Нинке значительно сложнее, чем Флойда-Стейнберга:
При таком алгоритме ошибка распределяется на в три раза больше пикселей, чем у Флойда-Стейнберга, что приводит к более гладкому и более тонкому результату. К сожалению, делитель 48 не является степенью двойки, поэтому битовые сдвиги применить не удастся. Используются только значения 1/48, 3/48, 5/48, и 7/48, так что эти значения могут быть вычислены единожды, а затем размножены несколько раз для небольшого увеличения по скорости.
Другим недостатком фильтра JJN является то, что он толкает ошибку вниз не на одну строку, а на две. Это означает, что нам нужны два массива — один для следующей строки, второй для строки после неё. Это было проблемой в то время, когда алгоритм был впервые опубликован, но на современных ПК и смартфонах это дополнительное требование не имеет никакого значения. Честно говоря, может быть лучше использовать единый массив ошибки размером с изображение, а не стирать две однорядные решетки снова и снова.
Псевдотонирование Джарвиса, Джудиса и Нинке
Дизеринг Штуки (Stucki)
Через пять лет после публикации формулы дизеринга Джарвиса, Джудиса и Нинке Питер Штуки опубликовал скорректированную версию с небольшими изменениями для улучшения времени обработки:
Степенью двойки делитель 42 не является, а вот значения рассеивания ошибки — да. Поэтому ошибка делится на 42, сдвиги по битам могут быть использованы для получения конкретных значений для рассеивания.
Для большинства изображений разница между алгоритмами Штуки и JJN будет минимальна. Поэтому первый чаще используется из-за его небольшого преимущества в скорости.
Дизеринг Аткинсона
В середине 1980-х годов псевдотонирование становится все более популярным, поскольку аппаратное обеспечение компьютеров доросло до поддержки более мощных драйверов видеоадаптера и дисплея. Один из лучших алгоритмов дизеринга той эпохи разработал Билл Аткинсон, сотрудник компании Apple, который работал над всем: от MacPaint (который он писал с нуля для оригинального Macintosh) до HyperCard и QuickDraw.
Формула Аткинсона немного отличается от других в этом списке, потому что она распространяет только часть ошибки, не всю целиком. В современных графичесих приложениях этот метод встречается под именем «уменьшить выцветание». Рассеивание только части ошибок помогает уменьшить зернистость, но непрерывные светлые и темные участки изображения могут потерять цвет.
Псевдотонирование Бёркеса (Burkes)
Через семь лет после того, как Штуки опубликовал улучшения алгоритма Джарвиса, Джудиса и Нинке, Дэниэл Бёркес предложил дальнейшее развитие:
Предложение Бёркеса заключалось в том, чтобы в алгоритме Штуки опустить нижний ряд матрицы. Это не только устранило необходимость в двух массивах, но и в результате привело к делителю, вновь кратному 2. Это изменение означало, что вся математика, участвующая в вычислении ошибки, могла быть выполнена простым битовым сдвигом, причем с незначительной потерей качества.
Псевдотонирование Сьерры (Sierra)
Последние три алгоритма дизеринга были созданы Фрэнком Сьеррой, который опубликовал следующие матрицы в 1989 и 1990 годах:
Эти три фильтра обычно называются Sierra, Two-Row Sierra (двухрядный алгоритм Сьерры) и Sierra Lite. Их конечное изображение на тестовой картинке куба выглядит следующим образом:
Sierra (иногда называют Sierra-3)
Two-row Sierra (двухрядный алгоритм Сьерры)
Остальные соображения по псевдотонированию
Если вы сравните изображения выше с результатами псевдотонирования другой программы, вы можете обнаружить небольшие различия. Подобное ожидаемо. Есть на удивление много переменных, которые могут повлиять на точность вывода алгоритма псевдотонирования. В их числе:
Псевдотонирование с упорядоченным размытием с матрицей 8×8
С учетом этих методов статья описывает 11 различных алгоритмов псевдотонирования.
Написание собственного алгоритма псевдотонирования общего назначения
Ранее в этом году я написал полностью функциональный генератор псевдотонирования общего назначения для PhotoDemon (фоторедактор с открытым исходным кодом). Вместо того чтобы размещать здесь весь код, позвольте мне направить вас на соответствующую страницу на GitHub. Движок преобразования черно-белых изображений начинается на строке 350. Если у вас есть вопросы по коду, который охватывает алгоритмы, описанные на этой странице, пожалуйста, сообщите мне, и я опубликую дополнительные пояснения.
Этот движок работает, позволяя вам заранее указать любую матрицу псевдотонирования точно так же, как в этой статье. Затем вы передаете эту матрицу в движок псевдотонирования, и он делает всё остальное.
Движок спроектирован на основе монохромного преобразования, но его можно легко модифицировать для работы с цветовыми палитрами. Самое большое отличие ситуации с цветовыми палитрами — то, что вы должны отслеживать отдельные ошибки для красного, зелёного и синего цветов, а не для одной ошибки яркости. В остальном вся математика та же.