Аппроксимация полутонами

Сглаживание или устранение ступенчатости — это метод улучшения визуального разрешения с использованием нескольких уровней интенсивности. Аппроксимация полутонами, с другой стороны, — это метод, в котором используется минимальное число уровней интенсивности, обычно черный и белый, для улучшения визуального разрешения, то есть получения нескольких полутонов серого или уровней интенсивности. Метод полутонов известен довольно давно. Первоначально он использовался при изготовлении шелковых картин и других текстильных изделий. В 1880 г. Стефаном Хагеном была изобретена современная полутоновая печать. В этом методе можно получить большое количество фотографических полутонов серого, используя чисто двухуровневую среду: черную краску на белой бумаге. Полутоновая печать — это решеточный или клеточный процесс. Размер клетки варьируется в зависимости от мелкозернистости решетки и длительности экспозиции. Для газетных фотографий из-за низкого качества бумаги применяются решетки от 50 до 90 точек на дюйм. Бумага более высокого качества, предназначенная для книг и журналов, позволяет использовать решетки с количеством точек от 100 до 300 на дюйм. Успех метода полутонов зависит от свойства зрительной системы человека быть интегратором, то есть объединять или сглаживать дискретную информацию.

Визуальное разрешение машинно-сгенерированных изображений можно улучшить с помощью метода, называемого конфигурированием. В противоположность полутоновой печати, в которой используются переменные размеры клеток, в данном методе обычно размеры клеток фиксированы. Для изображения с фиксированным разрешением несколько пикселов объединяются в конфигурации. Здесь ухудшение пространственного разрешения обменивается на улучшение визуального. На рис. 17.1a показана одна из возможных групп конфигураций для двухуровневого черно-белого дисплея. Для каждой клетки используется четыре пиксела. При такой организации получается пять возможных уровней или тонов серого (0-4).

В общем случае для двухуровнего дисплея число возможных интенсивностей на единицу больше числа пикселов в клетке. При выборе конфигураций следует проявлять осторожность, так как иначе могут возникнуть нежелательные мелкомасштабные структуры. Например, не следует применять ни одну из конфигураций, изображенных на рис. 17.1b или рис. 17.1c, иначе это приведет к тому, что для большой области с постоянной интенсивностью на изображении появятся нежелательные горизонтальные или вертикальные линии. Число доступных уровней интенсивности можно увеличить с помощью увеличения размера клетки. Конфигурации для клетки 3 * 3 пикселов приведены на рис. 17.2. Они дают десять уровней (с 0 по 9) интенсивности.

Клетки конфигураций не обязательно должны быть квадратными; на рис. 17.3 изображена клетка 3 * 2 пикселов, дающая семь (0-6) уровней интенсивности.

Если точки могут быть разного размера, то можно получить дополнительное количество уровней интенсивности. На рис. 17.4 представлены конфигурации для клетки 2 * 2 пиксела с двумя размерами точек. В результате получается 9 уровней интенсивности. Подобная клетка размера 3 * 3 с точками двух размеров позволяет иметь 27 уровней интенсивности. Если на пиксел приходится больше одного бита, то также можно получить дополнительные уровни интенсивности.

Для конфигурации 2 * 2 с 2 битами на пиксел получится 13 уровней интенсивности, показанные на рис. 17.5. Большее количество бит на пиксел или больший размер клетки дадут соответствующее увеличение числа уровней интенсивности.

Использование конфигураций ведет к потере пространственного разрешения, что приемлемо в случае, когда разрешение изображения меньше разрешения дисплея. Разработаны также методы улучшения визуального разрешения при сохранении пространственного. Простейший из них состоит в применении порогового значения для каждого пиксела. Если интенсивность изображения превышает некоторую пороговую величину, то пиксел считается белым, в противном случае он черный: if I(x, y) > Т then Белый else Черный, где I(x, y) означает интенсивность пиксела (x, y) изображения. Белый соответствует максимальной интенсивности для дисплея, а черный — минимальной. Пороговую величину обычно устанавливают приблизительно равной половине максимальной интенсивности.

На рис. 17.6b представлен результат для фотографии, изображенной на рисунке рис. 17.6a, со значением T = 150. В точках исходной фотографии, соответствующих каждому пикселу, интенсивность была разбита на дискретные значения в диапазоне от 0 до 255, то есть использовалось 8 бит. Как показано на рис. 17.6b, при простом пороговом методе наблюдается потеря большого количества мелких деталей. Особенно это заметно для волос и черт лица. Мелкие детали теряются из-за относительно больших ошибок выводимой интенсивности для каждого пиксела.

В методе, разработанном Флойдом и Стейнбергом, эта ошибка распределяется на окружающие пикселы. Распределение ошибки происходит всегда вниз и вправо. Следовательно, при генерации изображения в порядке сканирования возвращаться обратно не нужно. В частности, в алгоритме Флойда-Стейнберга 3/8 ошибки распределяется вправо, 3/8 — вниз и 1/4 — по диагонали, как это показано на рис. 17.7.

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

Для порога, равного среднему между минимальной и максимальной интенсивностями, T = (Белый + Черный)/2, алгоритм формулируется следующим образом.

Xmin, Xmax, Ymin, Ymax — пределы растра
 T = (Черный + Белый)/2
 for y = Ymax to Ymin step -1
   для каждого пиксела на строке (слева направо)
   for x = Xmin to Xmax
         определяем выводимое значение пиксела для пороговой величины T и вычисляем ошибку
         if I(x, y) < Т then
                 Пиксел(x, y) = Черный
                 Ошибка = I(x, y) - Черный
         else
                 Пиксел(x, y) = Белый
                 Ошибка = I(x, y) - Белый
         end if
         изображаем пиксел
         Display Пиксел(x, y)
         распределяем ошибку на соседние пикселы
         I(x + 1, y) = I(x + 1, y) + 3 * 0шибка/8
         I(x, y - 1) = I(x, y - 1) + 3 * Ошибка/8
         I(x + 1, y - 1) = I(x + 1, y - 1) + Ошибка/4
   next x
 next y
finish

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

Существует другой метод улучшения визуального разрешения для двухуровневых дисплеев без уменьшения пространственного разрешения — метод возбуждения. В изображение вводится случайная ошибка, которая добавляется к интенсивности каждого пиксела до ее сравнения с выбранной пороговой величиной. Добавление совершенно произвольной ошибки не приводит к оптимальному результату. Тем не менее существует оптимальная аддитивная матрица ошибки, минимизирующая эффекты появления фактуры на изображении. Матрица ошибки добавляется к изображению таким же способом, как расположены клетки на шахматной доске. Данный метод называется упорядоченным возбуждением. Минимальная матрица упорядоченного возбуждения имеет размер 2 * 2. Оптимальная 2 * 2-матрица, которую первым предложил Лим, имеет вид:

Матрицы 4 * 4, 8 * 8 и больших размеров получают с помощью рекуррентных соотношений (n => 4)

где n — размер матрицы и

Например, матрица возбуждения размера 4 * 4 имеет вид:

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

Алгоритм упорядоченного возбуждения

Xmin, Xmax, Ymin, Ymax — пределы растра
Mod — функция, возвращающая остаток от целого деления первого аргумента на второй
  for y = Ymax to Ymin step -1
    для каждого пиксела на строке (слева направо)
    for x = Xmin to Xmax
        определяем позицию в матрице возбуждения
        i = (x Mod n) + 1
        j = (y Mod n) + 1
        определяем выводимое значение пиксела
        if I(x, y) < D(i, j) then
            Пиксел(x, y) = Черный
        else
            Пиксел(x, y) = Белый
        end if
        изображаем пиксел
    Display Пиксел(x, y)
    next x
  next y
finish

На рис17.6c показано изображение, полученное из фотографии на На рис17.6a в результате обработки ее с матрицей упорядоченного возбуждения размера 8 * 8. При использовании матрицы такого размера эффективно вводится 64 уровня интенсивности. На рис17.6c свидетельствует о том, что восстанавливается много мелких деталей. Алгоритм Флойда-Стейнберга и упорядоченное возбуждение можно применять к цветным изображениям. Конфигурационные методы тоже можно использовать с цветом.