Другие журналы

научное издание МГТУ им. Н.Э. Баумана

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

Издатель ФГБОУ ВПО "МГТУ им. Н.Э. Баумана". Эл № ФС 77 - 48211.  ISSN 1994-0408

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

#12 декабрь 2004

О

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

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

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

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

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

A =

a11       a12      ...      a1n
a21       a22      ...      a2n
...           ...       ...        ...
am1      am2      ...    
amn

.

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

B =

b11       b12      ...      b1n
b21       b22      ...      b2n
...           ...       ...        ...
bm1      bm2      ...    
bmn

.

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

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

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

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

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

bij =

{

1, если Rij £ aij;
0 в противном случае.

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

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

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

#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£Cij. Обозначим Сmax=max Cij и выберем любое С ³ Сmax. Условимся, что отно шение Сij* показывает долю черного в данном сером тоне. Очевидно, что О £ С/С* £ 1 . Теперь можем определять компоненты bij матрицы В равными 1 с вероятностью Сij*.

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

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

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

bij=

{

1, если rij £ Cij;
0 в противном случае.

Как и ранее, при С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, начиная с некоторого значения могут давать полную запечатку бумаги (например, при расплывании чернил на струйном принтере).

Поэтому может оказаться полезным умение отображать совокупность тонов исходного изображения [Cmin*, Сmax*] на произвольный отрезок вещественных чисел [q1, q2].

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

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

Pij = min (1,max(0, qij))

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

1, Р2] = [q1, q2] Ç [О, 1].

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

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

• q1 = 0; q2= 1;

• q1 =—0.25; q2= 1.25;

• q1 = 0.25; q2 = 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

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

 

 

 

Поделиться:
 
ПОИСК
 
elibrary crossref ulrichsweb neicon rusycon
 
ЮБИЛЕИ
ФОТОРЕПОРТАЖИ
 
СОБЫТИЯ
 
НОВОСТНАЯ ЛЕНТА



Авторы
Пресс-релизы
Библиотека
Конференции
Выставки
О проекте
Rambler's Top100
Телефон: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)
  RSS
© 2003-2020 «Наука и образование»
Перепечатка материалов журнала без согласования с редакцией запрещена
 Тел.: +7 (915) 336-07-65 (строго: среда; пятница c 11-00 до 17-00)