Распространение ошибок - это тип полутонового изображения, при котором остаток квантования распределяется на соседние пиксели, которые еще не были обработаны. Его основное использование - преобразование многоуровневого изображения в двоичное , хотя у него есть и другие приложения.
В отличие от многих других методов полутонового изображения, распространение ошибок классифицируется как операция области, потому что то, что алгоритм делает в одном месте, влияет на то, что происходит в других местах. Это означает, что требуется буферизация , и усложняет параллельную обработку . Точечные операции, такие как упорядоченный дизеринг , не имеют этих сложностей.
Распространение ошибок имеет тенденцию усиливать края изображения. Это может сделать текст в изображениях более читабельным, чем при использовании других методов полутонового изображения .
Ранняя история [ править ]
Ричард Хауленд Рейнджер получил патент США 1790723 на свое изобретение «Факсимильная система». Патент, выданный в 1931 году, описывает систему для передачи изображений по телефону или телеграфу или по радио. [1] Изобретение Рейнджера позволило сначала преобразовать фотографии с непрерывным тоном в черно-белые, а затем передать их в удаленные места, где ручка перемещалась по листу бумаги. Чтобы сделать черный цвет, перо опускалось на бумагу; чтобы получить белый цвет, перо было поднято. Оттенки серого отображались путем периодического подъема и опускания пера в зависимости от желаемой яркости серого.
В изобретении Рейнджера использовались конденсаторы для хранения зарядов и компараторы на электронных лампах, чтобы определить, когда текущая яркость плюс любая накопленная ошибка была выше порогового значения (вызывая подъем пера) или ниже (вызывая опускание пера). В этом смысле это была аналоговая версия распространения ошибок.
Цифровая эра [ править ]
Флойд и Стейнберг описали систему распространения ошибок на цифровых изображениях, основанную на простом ядре:
![{\ frac {1} {16}} \ left [{\ begin {array} {ccccc} - & \ # & 7 \\ 3 & 5 & 1 \ end {array}} \ right]](https://wikimedia.org/api/rest_v1/media/math/render/svg/aef590317e58bf01da429ca7063b5a71e9e44327)
где " " обозначает пиксель в текущей строке, который уже был обработан (следовательно, распространение ошибки на него было бы бессмысленным), а "#" обозначает пиксель, который в настоящее время обрабатывается.
Почти одновременно Дж. Ф. Джарвис, К. Н. Джудис и У. Нинке из Bell Labs раскрыли аналогичный метод, который они назвали « минимизированной средней ошибкой » с использованием большего ядра : [2]
![{\ frac {1} {48}} \ left [{\ begin {array} {ccccc} - & - & \ # & 7 & 5 \\ 3 & 5 & 7 & 5 & 3 \\ 1 & 3 & 5 & 3 & 1 \ end {array}} \ right]](https://wikimedia.org/api/rest_v1/media/math/render/svg/2afcbcf36957fb6560391c4d1f12da577ec4a436)
Описание алгоритма [ править ]
Распространение ошибок принимает монохромное или цветное изображение и уменьшает количество уровней квантования. Популярное применение диффузии ошибок включает сокращение количества состояний квантования до двух на канал. Это делает изображение пригодным для печати на бинарных принтерах, таких как черно-белые лазерные принтеры.
В нижеследующем обсуждении предполагается, что количество состояний квантования в изображении с диффузной ошибкой равно двум на канал, если не указано иное.
Распространение одномерных ошибок [ править ]
Самая простая форма алгоритма сканирует изображение по одной строке за раз и по одному пикселю за раз. Текущий пиксель сравнивается со значением полутонового серого. Если оно выше значения, в результирующем изображении генерируется белый пиксель. Если пиксель ниже средней яркости, создается черный пиксель. Если целевая палитра не является монохромной, можно использовать разные методы, например, пороговое значение с двумя значениями, если целевая палитра - черный, серый и белый. Сгенерированный пиксель либо полностью яркий, либо полностью черный, поэтому в изображении есть ошибка. Затем ошибка добавляется к следующему пикселю изображения, и процесс повторяется.
Распространение двумерных ошибок [ править ]
Распространение одномерных ошибок имеет тенденцию иметь серьезные артефакты изображения, которые проявляются в виде отдельных вертикальных линий. Распространение двумерных ошибок уменьшает визуальные артефакты. Простейший алгоритм точно такой же, как диффузия одномерных ошибок, за исключением того, что половина ошибки добавляется к следующему пикселю, а половина ошибки добавляется к пикселю в следующей строке ниже.
Ядро:
![{\ displaystyle {\ frac {1} {2}} \ left [{\ begin {array} {cc} \ # & 1 \\ 1 & 0 \ end {array}} \ right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2fc09e179d72b9c6edd48de013aba58a6b6add32)
где «#» обозначает пиксель, обрабатываемый в данный момент.
Дальнейшее уточнение может быть достигнуто путем разброса ошибки дальше от текущего пикселя, как в матрицах, приведенных выше в эпоху цифровых технологий . Образец изображения в начале этой статьи является примером двумерной диффузии ошибок.
Распространение цветовых ошибок [ править ]
Те же алгоритмы могут применяться к каждому из красного, зеленого и синего (или голубого, пурпурного, желтого, черного) каналов цветного изображения для достижения цветового эффекта на таких принтерах, как цветные лазерные принтеры, которые могут печатать только значения одного цвета. .
Однако лучшие визуальные результаты можно получить, сначала преобразовав цветовые каналы в воспринимаемую цветовую модель , которая разделит каналы яркости, оттенка и насыщенности, так что каналу яркости будет присвоен более высокий вес для рассеивания ошибок, чем каналу оттенка. . Мотивация для этого преобразования заключается в том, что человеческое зрение лучше воспринимает небольшие различия в освещенности в небольших локальных областях, чем аналогичные различия оттенков в той же области, и даже больше, чем аналогичные различия насыщенности в одной и той же области.
Например, если есть небольшая ошибка в зеленом канале, которая не может быть представлена, и другая небольшая ошибка в красном канале в том же случае, правильно взвешенная сумма этих двух ошибок может быть использована для корректировки заметной ошибки яркости, которая могут быть представлены сбалансированным образом между всеми тремя цветовыми каналами (согласно их соответствующему статистическому вкладу в яркость), даже если это приводит к большей ошибке для оттенка при преобразовании зеленого канала. Эта ошибка будет распространена на соседние пиксели.
Кроме того, для каждого из этих каналов восприятия может потребоваться гамма-коррекция , если они не масштабируются линейно с человеческим зрением, так что диффузия ошибок может линейно накапливаться в этих линейных каналах с гамма-коррекцией перед вычислением окончательных цветовых каналов округленные цвета пикселей с использованием обратного преобразования в исходный формат изображения без гамма-коррекции, из которого будет вычислена и снова преобразована новая остаточная ошибка для распределения на следующие пиксели.
Следует также отметить, что из-за ограничений точности во время числового преобразования между цветовыми моделями (особенно, если это преобразование не является линейным или использует нецелочисленные веса), могут возникать дополнительные ошибки округления, которые следует учитывать в остаточной ошибке.
Распространение ошибок с несколькими уровнями серого [ править ]
Распространение ошибок также может использоваться для создания выходных изображений с более чем двумя уровнями (на канал, в случае цветных изображений). Это применяется в дисплеях и принтерах, которые могут создавать 4, 8 или 16 уровней в каждой плоскости изображения, например, в электростатических принтерах и дисплеях в компактных мобильных телефонах. Вместо того, чтобы использовать один порог для создания двоичного вывода, определяется ближайший разрешенный уровень, и ошибка, если таковая имеется, рассеивается, как описано выше.
Рекомендации по использованию принтера [ править ]
Большинство принтеров слегка перекрывают черные точки, поэтому нет точного однозначного отношения к частоте точек (в точках на единицу площади) и яркости . К исходному изображению можно применить линеаризацию шкалы тонов, чтобы напечатанное изображение выглядело правильно.
Улучшение краев по сравнению с сохранением легкости [ править ]
Когда изображение имеет переход от светлого к темному, алгоритм распространения ошибок стремится сделать следующий сгенерированный пиксель черным. Переход от темного к светлому обычно приводит к тому, что следующий сгенерированный пиксель становится белым. Это вызывает эффект выделения контуров за счет точности воспроизведения уровня серого. Это приводит к тому, что диффузия ошибок имеет более высокое видимое разрешение, чем другие полутоновые методы. Это особенно полезно для изображений с текстом, таких как типичное факсимиле.
Этот эффект довольно хорошо показан на картинке в верхней части этой статьи. Трава и текст на вывеске хорошо сохранены, а легкость неба - мало деталей. Полутоновое изображение с кластерными точками того же разрешения будет гораздо менее резким.
См. Также [ править ]
- Дизеринг Флойда – Стейнберга
- Полутона
Ссылки [ править ]
- ^ Ричард Хоуленд Рейнджер, Факсимильная система. Патент США 1790723, выдан 3 февраля 1931 г.
- ^ JF Jarvis, CN Judice и WH Ninke, Обзор методов отображения изображений с непрерывным тоном на двухуровневых дисплеях. Компьютерная графика и обработка изображений, 5 : 1: 13–40 (1976).
Внешние ссылки [ править ]
- Распространение ошибок в Matlab
