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

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

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

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

• 1 Ранняя история
• 2 Цифровая эра
• 3 Описание алгоритма
  • 3.1 Распространение одномерных ошибок
  • 3.2 Распространение двумерных ошибок
  • 3.3 Распространение цветовых ошибок
  • 3.4 Распространение ошибок с несколькими уровнями серого
  • 3.5 Рекомендации по принтеру
  • 3.6 Сравнение улучшения краев и сохранения яркости
• 4 См. Также
• 5 Ссылки
• 6 Внешние ссылки

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

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

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

$1\; 16\; [-\; \#\; 7\; 3\; 5\; 1]\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{16\}\}\; \backslash \; left\; [\{\backslash \; begin\; \{array\}\; \{ccccc\}\; -\; \backslash \; \#\; 7\; \backslash \backslash \; 3\; 5\; 1\; \backslash \; end\; \{array\}\}\; \backslash \; right]\}$

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

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

$1\; 48\; [-\; -\; \#\; 7\; 5\; 3\; 5\; 7\; 5\; 3\; 1\; 3\; 5\; 3\; 1]\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{48\}\}\; \backslash \; left\; [\{\backslash \; begin\; \{array\}\; \{ccccc\}\; -\; -\; \backslash \; \#\; 7\; 5\; \backslash \backslash \; 3\; 5\; 7\; 5\; 3\; \backslash \backslash \; 1\; 3\; 5\; 3\; 1\; \backslash \; end\; \{array\}\}\; \backslash \; right]\}$

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

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

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

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

Распространение двумерных ошибок

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

Ядро:

$1\; 2\; [\#\; 1\; 1\; 0]\; \{\backslash \; displaystyle\; \{\backslash \; frac\; \{1\}\; \{2\}\}\; \backslash \; left\; [\{\backslash \; begin\; \{array\}\; \{cc\}\; \backslash \; \#\; 1\; \backslash \; \backslash \; 1\; 0\; \backslash \; end\; \{array\}\}\; \backslash \; right]\}$

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

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

Распространение цветовых ошибок

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

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

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

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

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

Распространение ошибок с несколькими уровнями серого

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

Особенности принтера

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

Улучшение краев по сравнению с сохранением яркости

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

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

• дизеринг Флойда – Стейнберга
• Полутона

1. ^Ричард Хоуленд Рейнджер, Факсимильная система. Патент США 1790723, выдан 3 февраля 1931 г.
2. ^Дж. Ф. Джарвис, К. Н. Джудис и У. Н. Нинке, Обзор методов отображения изображений с непрерывным тоном на двухуровневых дисплеях. Компьютерная графика и обработка изображений, 5 : 1: 13–40 (1976).

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