1.2. ВИДЫ ДАННЫХ, ПРЕДСТАВЛЕННЫХ В ФОРМЕ ИЗОБРАЖЕНИЙ

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

1.2.1. КЛАСС 1: ТОНОВЫЕ И ЦВЕТНЫЕ ИЗОБРАЖЕНИЯ

В класс 1 входят изображения, имеющие вид обычных телевизионных изображений. Они обеспечивают довольно точное воспроизведение «реальности» и представляются матрицами с целочисленными элементами (для обозначения последних обычно используют термины элемент изображения, пиксел и пэл). В большинстве прикладных задач эти матрицы имеют очень большие размеры (512x512), являющиеся наиболее общепринятыми. В связи с этим представления изображений не всегда хранятся в памяти в виде обычных матриц — часто используются и более изощренные разновидности структур данных. Эта тема обсуждается в гл. 6. Цветные изображения могут представляться либо при помощи трех матриц (для красного, зеленого и синего цветов), либо с помощью одной матрицы таким образом, что отдельные биты каждого элемента представляют различные цвета. Поскольку человеческий глаз обычно не в состоянии различать уровни освещенности, отличающиеся друг от друга менее чем на 1%, то для представления цветного изображения достаточно затрачивать по одному байту на цвет на пиксел. Однако приемлемых результатов удается добиться, используя по 3 бита для передачи каждого из двух цветов и 2 бита для передачи третьего, так что в конечном счете для хранения изображения в памяти затрачивается лишь по одному байту на пиксел. Это мы более подробно обсудим в разд. 2.5. С математической точки зрения иногда удобнее рассматривать цветные изображения как матрицы трехмерных векторов.

1.2.2. КЛАСС 2: ДВУХУРОВНЕВЫЕ ИЛИ ПРЕДСТАВЛЯЕМЫЕ В НЕСКОЛЬКИХ «ЦВЕТАХ» ИЗОБРАЖЕНИЯ

Изображение книжной страницы служит типичным примером представителя класса 2-двухуровневого (черно-белого) изображения. Подобные изображения можно представлять матрицами, затрачивая по одному биту на элемент, а также и в виде «карт», так как на этих изображениях имеются хорошо различимые области одного цвета. Именно поэтому мы объединяем в один класс изображения, представляемые в нескольких «цветах», и двухуровневые изображения, несмотря на то, что представление с затратой одного бита на элемент матрицы удачно лишь для двухуровневых изображений. Одна из проблем, возникающих в связи с использованием одного бита для представления каждого пиксела, заключается в отсутствии стандартного для различных типов ЭВМ и устройств визуального отображения способа объединения битов в байт и байтов в слово. Так, крайний слева пиксел может представляться как наименее, так и наиболее значимыми битами байта. Следовательно, пользователям всегда приходится думать о выборе способа представления, наиболее подходящего для применяемых ими устройств. Ниже опишем, каким образом карты могут быть представлены в ЭВМ Отметим, что различие между цветными и представляемыми Б нескольких цветах изображениями неопределенно и приобретает смысл лишь применительно к способу, используемому для представления изображения.

1.2.3. КЛАСС 3: НЕПРЕРЫВНЫЕ КРИВЫЕ И ЛИНИИ

Примерами изображений класса 3 служат контуры областей, сигналы и диаграммы (графики). Соответствующие данные являются последовательностями точек, допускающих представление через их координаты х, у. Однако этот метод представления довольно неэффективен, причем то же самое относится к представлению, основанному на использовании разностей значений координат у соседних точек. Более эффективным является представление с помощью цепных кодов, при использовании которых вектору, соединяющему две соседние точки, ставится в соответствие один символ, принадлежащий некоторому конечному множеству. На рис. 1 2 показан обычный цепной код, использующий восемь направлений. Если точки расположены достаточно близко друг к другу, то ошибка, вносимая квантованием, может оказаться приемлемой. Если в качестве кодируемых точек выбираются смежные элементы матрицы изображения (вдоль строк, столбцов или диагоналей), то представление, основанное на использовании разностей индексов, указывающих положение элементов матрицы, требует затраты четырех

Рис. 1.2. Задание стандартною цепного кода; штриховые линии — направления, которые ставятся в соответствие некоторому определенному элементу кода

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

Еще более эффективный способ представления заключается в применении дифференциального цепного кода, предусматривающего кодирование каждой точки разностью двух последовательных абсолютных кодов. В этом случае все еще сохраняется восемь значений (0, ±1, ±2, ±3 и 4), однако вероятности их появления неодинаковы. Можно ожидать, что при кодировании гладких кривых значения 0 и ±1 будут появляться много чаще, чем все остальные, а значение 4 — чрезвычайно редко. Поэтому для представления различных направлений можно воспользоваться каким-либо из кодов с переменной длиной.

Приведем один из возможных вариантов кодирования словами с переменной длиной при использовании дифференциального цепного кода.

При таком способе кодирования обычно затраты в среднем не превышают двух битов на точку. Проверка, проведенная автором на различных данных, показала, что для буквенно-цифровых символов средние затраты составляют 1,8-1,9 бит, а для очертаний таких объектов, как бокал на ножке или болт, эти затраты составляют в среднем 1,5-1,9 бит. Для небольшой окружности, являющейся неблагоприятным случаем, требуемые затраты равняются 2,3 бит/пиксел. Желательность применения цепного кода при обработке кривых зависит от конкретной задачи, однако заметим, что переход к координатам х, у и обратно не вызывает затруднений (см. задачу 14).

1.2.4. КЛАСС 4: ТОЧКИ ИЛИ МНОГОУГОЛЬНИКИ

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

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

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

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

б. Криволинейная аппроксимация поверхности; на поверхности тела вычерчивается ряд кривых, описания которых затем используются для получения проекций, воспроизводимых в виде изображений класса 3.

в. Аппроксимация участками поверхности высшего порядка; этот способ аналогичен способу «а», за исключением того, что в качестве элементов, образующих поверхность объекта, используются не плоские многоугольники, а участки поверхности высшего порядка.

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