Алгоритмы повышения количества оттенков (псевдотонирования)

11.1. Актуальность задачи аппроксимации полутонового изображения двухуровневым

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

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

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

Существует подход, когда пространственное разрешение приносят в жертву визуальному [45]. Например, если число выводимых оттенков равно 2, то область размером 2x2 пикселя может аппроксимировать 5 значений атрибутов (см. рис. 11.2). Общее правило для черно-белых устройств такое: область пикселей размером nxn позволяет аппроксимировать n2+1 значений атрибутов. Однако потери в пространственном разрешении часто недопустимы, плюс к тому, чтобы добиться приемлемого количества оттенков, придется уменьшить пространственное разрешение в 7-10 раз, что дает 50-101 оттенков серого.

(рис 11.2) Увеличенный газетный снимок.(рис 11.1) Шаблон для приближения 5 значений интенсивности.

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

11.2. Простой алгоритм аппроксимации полутонов

Самый простой алгоритм - это усечение по порогу (см. алгоритм 11.1). Порог обычно выбирается равным половине максимального значения интенсивности.

foreach( pixel in 8bit_picture )  // для каждого пикселя
{
      // Threshold - порог, I(pixel) - атрибут пикселя
      if( I(pixel) > Threshold )
          I(pixel) = Белый;
      else
          I(pixel) = Черный;
}

Как видно из рис. 11.4, метод имеет явно выраженный недостаток - теряется слишком много деталей.

11.3. Алгоритм упорядоченного размытия

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

Тем не менее существует искусственный псевдошум, который минимизирует эффект периодичности, т.е. появления на изображении некоторого упорядоченного узора. Данный шум возможно задать с помощью квадратной матрицы специального вида [13]. Такая матрица называется матрицей размытия(англ.) dither matrix. Сначала исходное изображение разбивается на квадратные области размером NxN, совпадающие с размерностью матрицы размытия, затем к каждому квадрату применяется алгоритм 11.2, где в качестве порога выбирается соответствующее значение из матрицы.

(рис 11.3) Исходное изображение.

Для случая 2x2 оптимальной является следующая матрица:

$$D_2 = {\left( \begin{array}{cc} 0 2 \\ 3 1 \end{array} \right)}.$$

Для получения матриц большего размера следует использовать следующие рекурсивные соотношения:

$$D_n = { \left( \begin{array}{cc} 4D_{n/2} 4D_{n/2} + 2U_{n/2} \\ 4D_{n/2} + 3U_{n/2} 4D_{n/2} + U_{n/2} \end{array} \right) },$$

где

$$U_n = \left( \begin{array}{ccccc} 1 1 1 \ldots 1 \\ 1 1 1 \ldots 1 \\ 1 1 1 \ldots 1 \\ \vdots \vdots \vdots \ddots 1 \\ 1 1 1 1 1 \end{array} \right)$$

- матрица, состоящая из единиц размером nxn. Например, матрица размером 4x4 будет следующая:

$$D_4 = { \left( \begin{array}{cccc} 0 8 2 10 \\ 12 4 14 6 \\ 3 11 1 9 \\ 15 7 13 5 \end{array} \right) }.$$ (рис 11.5) Результат работы простого метода псевдотонирования.(рис 11.4) Результат работы алгоритма упорядоченного размытия.

Матрица размытия Dn позволяет получить n2 значений атрибутов; при этом пространственное разрешение не изменяется. Ниже приведен псевдокод алгоритма:

foreach( pixel in 8bit_picture ) // для каждого пикселя
{
      // I(pixel) - атрибут пикселя
      // Dn(i,j) - матрица размытия, n - размер матрицы
      // X Mod Y - остаток от деления X на Y
      // i, pixel.Y - координаты строк
      i = pixel.Y Mod n;
      // j, pixel.X - координаты столбцов
      j = pixel.X Mod n;
      if( I(pixel) > Dn(i,j) )
          I(pixel) = Белый;
      else
          I(pixel) = Черный;
}

Как видно из рис. 11.5 результаты работы данного алгоритма намного лучше, чем описанного в разделе 11.2, - изображение выглядит более детально.

11.4. Алгоритм рассеивания ошибок Флойда-Стейнберга

Данный метод также является модификацией алгоритма усечения по порогу, рассмотренного в разделе 11.2. Идея состоит в распределении (рассеивании) ошибки, возникшей при аппроксимации данного пикселя, на соседние пиксели. Существуют разные варианты распределения ошибки на соседние пиксели. Приведем тот вариант, который использует все доступные (при однопроходном построчном алгоритме) непосредственные соседние пиксели в 8-связном смысле и является оптимальным [30]. Осуществляется проход изображения сверху вниз, слева направо и применяется усечение по порогу; при этом ошибка распределяется следующим образом (см. рис. 11.6): к значению атрибута пикселя справа добавляется $$\frac{7}{16}$$ ошибки, справа внизу добавляется $$\frac{1}{16}$$ ошибки, внизу добавляется $$\frac{5}{16}$$ ошибки, слева внизу добавляется $$\frac{3}{16}$$ ошибки.

(рис 11.3) Распределение ошибки.(рис 11.6) Алгоритм псевдотонирования - рассеивание ошибок Флойда-Стейнберга// проход по пикселям строго справа налево, сверху вниз
// Threshold - порог, I(pixel) - атрибут пикселя
// pixel.right - пиксель справа, pixel.down - пиксель внизу
// pixel.down_right - пиксель справа внизу
// pixel.down_left - пиксель слева внизу
foreach( pixel in 8bit_picture ) //для каждого пикселя
{
      if( I(pixel) > Threshold )
      {
          I(pixel) = Белый;
          Error = I(pixel) - Белый;
      }
      else
      {
          I(pixel) = Черный;
          Error = I(pixel) - Черный;
      }
      I(pixel.right)+= 7/16 * Error;
      I(pixel.down_right)+= 1/16 * Error;
      I(pixel.down)+= 5/16 * Error;
      I(pixel.down_left)+= 3/16 * Error;
}

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

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

(рис 11.7) Результат работы алгоритма рассеивания ошибок.