Распространение ошибок

Диффузия ошибок — это тип полутонового изображения , при котором остаток квантования распределяется по соседним пикселям , которые еще не были обработаны. Его основное применение — преобразование многоуровневого изображения в двоичное , хотя у него есть и другие применения.

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

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

Ранняя история

Ричард Хауленд Рейнджер США получил патент 1790723 на свое изобретение «Факсимильная система». Патент, выданный в 1931 году, описывает систему передачи изображений по телефонным, телеграфным линиям или по радио. ^[1] Изобретение Рейнджера позволило с непрерывным тоном сначала преобразовать фотографии в черно-белые, а затем передать их в отдаленные места, где ручка перемещалась по листу бумаги. Чтобы сделать черный цвет, перо опускали на бумагу; чтобы получить белый цвет, перо поднимали. Оттенки серого отображались путем периодического поднятия и опускания пера в зависимости от желаемой яркости серого.

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

цифровая эра

Флойд и Стейнберг описали систему диффузии ошибок на цифровых изображениях, основанную на простом ядре. ^[2]

{\frac {1}{16}}{\begin{bmatrix}-&\#&7\\3&5&1\end{bmatrix}},

где " $-$ " обозначает пиксель в текущей строке, который уже был обработан (поэтому распространять на него ошибку было бы бессмысленно), а "#" обозначает пиксель, обрабатываемый в данный момент.

Почти одновременно Дж. Ф. Джарвис, К. Н. Джудис и У. Н. Нинке из Bell Labs раскрыли аналогичный метод, который они назвали « минимальная средняя ошибка » с использованием ядра большего размера ^[3]

{\frac {1}{48}}{\begin{bmatrix}-&-&\#&7&5\\3&5&7&5&3\\1&3&5&3&1\end{bmatrix}}.

Описание алгоритма

Диффузия ошибок принимает монохромное или цветное изображение и уменьшает количество уровней квантования. ^[4] Популярное применение диффузии ошибок предполагает сокращение количества состояний квантования до двух на канал. Это делает изображение пригодным для печати на бинарных принтерах, таких как черно-белые лазерные принтеры.

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

Одномерное распространение ошибок

Самая простая форма алгоритма сканирует изображение по одной строке и по одному пикселю за раз. Текущий пиксель сравнивается со значением полусерого. Если оно превышает это значение, в результирующем изображении генерируется белый пиксель. Если яркость пикселя ниже половины, генерируется черный пиксель. Если целевая палитра не является монохромной, можно использовать разные методы, например, определение порога с двумя значениями, если целевая палитра — черный, серый и белый. Сгенерированный пиксель либо полностью яркий, либо полностью черный, поэтому в изображении есть ошибка. Затем ошибка добавляется к следующему пикселю изображения, и процесс повторяется.

Двумерная диффузия ошибок

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

Ядро

{\frac {1}{2}}{\begin{bmatrix}\#&1\\1&0\end{bmatrix}},

где «#» обозначает пиксель, обрабатываемый в данный момент.

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

Диффузия цветовых ошибок

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

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

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

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

Диффузия ошибок с несколькими уровнями серого

Диффузию ошибок также можно использовать для создания выходных изображений с более чем двумя уровнями (на канал в случае цветных изображений). Это находит применение в дисплеях и принтерах, которые могут создавать 4, 8 или 16 уровней в каждой плоскости изображения, например, в электростатических принтерах и дисплеях в компактных мобильных телефонах. Вместо использования одного порога для получения двоичного вывода определяется ближайший разрешенный уровень, а ошибка, если таковая имеется, распределяется, как описано выше.

Улучшение краев и сохранение легкости

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

Этот эффект довольно хорошо виден на картинке вверху статьи. Детали травы и текст на знаке хорошо сохранились. и легкость неба, содержащая мало деталей. изображение с кластерными точками Полутоновое того же разрешения будет гораздо менее резким.

См. также

Ссылки

^ Ричард Хауленд Рейнджер, «Факсимильная система». Патент США 1790723, выданный 3 февраля 1931 г.
^ Флойд, Роберт В.; Стейнберг, Луи (1976). «Адаптивный алгоритм для пространственных оттенков серого». Труды Общества отображения информации . 17 (2): 75–77.
^ Дж. Ф. Джарвис, К. Н. Джудис и У. Н. Нинке, «Обзор методов отображения изображений с непрерывным тоном на двухуровневых дисплеях». Компьютерная графика и обработка изображений, 5 :1:13–40 (1976).
^ «Распространение ошибок — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 9 мая 2022 г.

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

Распространение ошибок в Matlab

[Ranger1931-1] Ричард Хауленд Рейнджер, «Факсимильная система». Патент США 1790723, выданный 3 февраля 1931 г.

[2] Флойд, Роберт В.; Стейнберг, Луи (1976). «Адаптивный алгоритм для пространственных оттенков серого». Труды Общества отображения информации . 17 (2): 75–77.

[Jarvis1976-3] Дж. Ф. Джарвис, К. Н. Джудис и У. Н. Нинке, «Обзор методов отображения изображений с непрерывным тоном на двухуровневых дисплеях». Компьютерная графика и обработка изображений, 5 :1:13–40 (1976).

[4] «Распространение ошибок — обзор | Темы ScienceDirect» . www.sciencedirect.com . Проверено 9 мая 2022 г.

[1]

[2]

[3]

[4]