НАУКА и ОБРАЗОВАНИЕ

О.П. АРХИПОВ, канд. техн. наук, З.П. ЗЫКОВА, канд. физ.-мат. наук Орловский филиал ИПИ РАН

Вероятностный алгоритм полутонирования Random Dot

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

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

Для определенности рассмотрим прямоугольную матрицу А размера m х n с компонентами a_ij, 1 £ i £ m, 1 £ j £ n, 1 £ a_ij £ 255:

Предполагается, что для печати изображений используется принтер с точечным выводом, например, струйный, матричный и т.д. Такой принтер воспроизводит на бумаге битовые матрицы, значениями компонентов которых может быть лишь одно из двух значений: 0 или 1. Черная точка на бумаге ставится, если значение соответствующего компонента матрицы равно 1, и не ставится в противном случае. В таких условиях единственное средство для воспроизведения полутонов — варьирование плотности размещения черных точек на бумаге. Следовательно, необходим алгоритм преобразования матрицы А в матрицу В размера m х n с компонентами b_ij 1£ i £ m, 1 £ j £ n, b_ij = {О, 1}:

причем единицы в матрице В должны быть размещены с плотностью, соответствующей плотности а_ij/255 распределения черного цвета в матрице А.

Предлагается вероятностный алгоритм полутонирования "Случайная точка — Random Dot", состоящий в том, что компонент b_ij матрицы В полагается равным 1 с вероятностью p_ij = а_ij/255.

Реализация Random Dot проста и состоит из двух шагов:

1) определение случайного числа R_ij из отрезка [0,255];

2) определение b_ij:

Очевидно, что при а_ij = 0 справедливо b_ij º 0, а при а_ij º 255 справедливо b_ij º 1. При а_ij º const применение Random Dot приведет к тому, что из компонентов b_ij матрицы в единице будет равна часть, составляющая const/255, а следовательно, черными пикселами будет запечатан соответствующий процент площади изображения, т.е. на бумаге будет воспроизведен требуемый тон серого цвета.

При применении Random Dot интенсивность черного цвета переносится точно и не возникает ошибок преобразования, которые являются основанием для применения алгоритма полутонирования Error Diffusion [1], [2], а следовательно, отпадают соответствующие вычислительные затраты и запросы по памяти. Вероятностный алгоритм Random Dot просто реализуем и не требует хранения и обработки многочисленных единичных матриц тонопередачи, как в методе Dither [2].

В приводимом ниже листинге содержится текст процедуры на языке С преобразования компонента а_ij в компонент b_ij:

#include <stdlib.h>
BYTE ByteToBit (BYTE Gray)
{
if (Gray = = NULL) return 0;
if (Gray = = 255) return 1;
if (random(255) <= Gray) return 1;
return 0;
}

Результат использования этой процедуры для получения тонов серого со значениями 50, 75, 100, 125, 150, 175, 200 демонстрирует рис. 1*. Каждый из образцов сформирован на прямоугольнике 150x300 пикселов при многократном выводе на печать матриц размером 1x300, компоненты которых постоянны и равны соответственно 50, 75, 100, 125, 150, 175, 200.

Примеры образцов получены на струйном принтере DeskJet 560 (разрешение 300 точек/дюйм).

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

Небольшое обобщение Random Dot решает эту проблему. Рассмотрим матрицу С с вещественными неотрицательными компонентами С_ij, 1£1£m, 1£j£n, 0£C_ij. Обозначим С_max=max C_ij и выберем любое С ³ С_max. Условимся, что отно шение С_ij/С^* показывает долю черного в данном сером тоне. Очевидно, что О £ С/С^* £ 1 . Теперь можем определять компоненты b_ij матрицы В равными 1 с вероятностью С_ij/С^*.

Реализация Random Dot проста и в обобщенном виде состоит из шагов:

1) определение случайного вещественного числа r_ij из отрезка [О, 1];

2) определение b_ij:

Как и ранее, при С_ij = 0 справедливо b º 0, а при С_ij = С^* справедливо Ь º 1.

Результаты применения Random Dot при получении части горизонтальной тоновой шкалы от тона 50/255 до тона 150/255 длиной 1200 пикселов демонстрирует рис. 2, Значение промежуточных значений тонов для внутренних пикселов получены при линейной интерполяции известных граничных значений:

Аналогичным образом формируются тона и других доступных принтеру цветов. Например, на СМУК-принтере НР DeskJet 660 получены фрагменты тоновой шкалы Magenta от тона 50 до тона 125 различной длины: 600, 1200, 1800 пикселов (рис. 3).

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

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

Поэтому может оказаться полезным умение отображать совокупность тонов исходного изображения [C_min/С^*, С_max/С^*] на произвольный отрезок вещественных чисел [q₁, q₂].

Обозначим С₁ = Сmin/С^*; С₂ = Сmax/С^*. Пусть С₁ << С₂. Для отображения [С₁, С₂] => [q₁, q₂] полагаем

Полагая b_ij равным 1 с вероятностью

P_ij = min (1,max(0, q_ij))

мы отобразим совокупность тонов [С₁, С₂] на отрезок

[Р₁, Р₂] = [q₁, q₂] Ç [О, 1].

Рис. 4 демонстрирует некоторые возможности такого подхода. В прямоугольнике 400x400 значения тонов задаются следующим образом:

Образцы изображений получены для случаев:

• q₁ = 0; q₂= 1;

• q₁ =—0.25; q₂= 1.25;

• q₁ = 0.25; q₂ = 0.75.

Применение описанного алгоритма полутонирования приводит к построению двоичной матрицы В — кода оттиска, и возникает естественный вопрос — каким образом рядовой пользователь или разработчик программного обеспечения может превратить полученный код в собственно оттиск на имеющемся в его распоряжении, скажем, струйном принтере. Следует отметить, что тут имеется масса возможностей. Ограничимся описанием использования языка управления принтером.

В настоящее время имеется два широко распространенных, поддерживаемых многими разработчиками принтеров фактических стандарта языков управления принтером: стандарт PCL (Printer Communications Language), разработанный фирмой Hewlett-Packard, и Post Script фирмы Adobe. Какая бы фирменная технология растрирования ни была реализована на принтере, средства языков управления принтером позволяют точно воспроизводить на нем двоичные матрицы — коды оттиска, независимо от того, каким способом они получены, каковы были исходные изображения и какая технология растрирования (в частности, технология полутонирования) применялась.

В качестве примера приведем последовательность команд (в шестнадцатеричнои кодировке) для принтера стандарта PCL, обеспечивающих печать одной строки растровой страницы (одной строки матрицы В в наших обозначениях):

1) 1В45 — инициализация принтера;

2) 1В2А7433303052 — установление разрешения 300 точек/дюйм;

3) 1В2А62 [количество байт данных] 57 [данные] — пересылка растровых данных;

4) 1В2А726243 — конец растровой графики;

5) 1В266С3048 — выталкивание оттиска.

Команда 3 должна быть повторена столько раз, сколько строк имеет матрица В.

Пусть матрица В такова: В = (1, 0, 0, 1, 1, 1, 0, 0, 0, 1). Последовательно объединяя ее компоненты группами по четыре для шестнадцатеричнои кодировки, получим два байта данных — 9С40. Поскольку количеству — цифре 2 — отвечает код 32, команда 3 будет иметь следующий вид: 1В2А6232579С40.

После копирования в соответствующий порт (как правило, LPT1) файла

1В451В2А74333030521В2А6232579С401В2А7262431В266С3048

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

Предположим, что имеются два разных струйных PCL-принтера. Насколько велики различия при воспроизведении на них битовых карт оттиска? Единственное, на что следует обратить внимание, — это разрешение принтера, поскольку у разных принтеров эта характеристика может быть разной, да и для одного и того же принтера, как правило, возможно указание различных значений разрешения. Например, для принтера HP DeskJet 560, кроме приведенной ранее команды 2, задающей разрешение 300 точек/дюйм, возможно использование команд: 1В2А74373552, 1В2А7431303052 и 1В2А7431353052, задающих соответственно разрешение 75, 100 и 150 точек/дюйм. Понятно, что если, скажем, одна и та же битовая матрица воспроизводится на принтерах с разрешением 300 и 600 точек на дюйм, оттиски будут различаться размерами (площадь второго оттиска составит четвертую часть площади первого).

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

Список литературы

1. Жаров А. Короче . Да нельзя короче, или преобразование серых изображений для вывода на устройство печати // Монитор. 1995. № 6. С. 62-64.

2. Шлепфер К. Частотно-модулированное растрирование в офсете // Интерпринт. 1993. № 2. С. 18—25

ИНФОРМАЦИОННЫЕ ТЕХНОЛОГИИ, №1. 1997

КОМПЬЮТЕРНАЯ ГРАФИКА И ГЕОМЕТРИЧЕСКОЕ МОДЕЛИРОВАНИЕ