Компьютерная графика

Grayscale(градации серого).Отличие данного формата от предыдущего в том, что для каждого элемента матрицы отводится 8 битов (байт). Это позволит нам использовать 2⁸=256 уровней серого цвета. Если a_i,j=0, то имеем белый цвет, с возрастанием до 255 мы будем терять яркость и при a_i,j=255 получим черный цвет. В промежутке от 0 до 255 будут располагаться серые цвета по правилу: чем ближе значение к 255, тем чернее будет серый. Данный формат позволяет получать довольно качественные черно-белые изображения. Значения a_i,j содержат обратную яркость, т.е. значение (1 - L)*255, где L - яркость, которая может быть получена, например из RGB цветовых изображений по формуле:

L = aR + bG + cG,

где R,G,B лежат в интервале [0;1], а веса a, b, c в сумме дают единицу.

Иногда, для хранения grayscale изображений используют на точку 4-7 и 16 битов. В таком случае мы имеем 16-128 или 65536 оттенков серого цвета.

Многоканальные. В данном случае a_i,j представлен в виде вектора с координатами используемой цветовой модели. Обычно вектор трехмерный, так как природа глаза реагирует на три различных цветовых составляющих. Каждый компонент вектора чаще всего занимает байт. Рассмотрим наиболее распространенные многоканальные форматы:

 

Название	Соотношение бит	1-ый компонент	2-ой компонент	3-ий компонент
RGB - Truecolor	8:8:8	Красный0-255	Зеленый0..255	Синий0-255
RGB - Highcolor	5:6:5/5:5:5	Красный0-31	Зеленый0.63/31	Синий0-31
RGB - Extended	12:12:12/ 16:16:16	Красный 0-4095/0-65535	Зеленый 0-4095/0-65535	Синий0-4095   /0-65535
CMY	8:8:8	Голубой0-255	Пурпур0-255	Желтый0-255
LAB	8:8:8	Яркость0-255	Канал A         0-100%	Канал B         0-100%
YIQ	8:8:8	Яркость0-255	Синфазный 0-255	Интегрированный 0-255
HLS	8:8:8	Тон 0-3600	Яркость0-100%	Насыщенность   0-100%
HSB	8:8:8	Тон 0-3600	Насыщенность   0-100%	Яркость0-100%

 

Встречаются четырех и  более мерные вектора, например, модель CMYK, она применяется, когда имеются четыре основных цветовых красителя. Двумерные модели называют дуплексами. Их применяют в полиграфии, например, при печати стандартного grayscale изображения, реально в промышленности оно будет выполнено лишь в ~50 градациях серого, и для повышения числа градаций вводят вторую краску.

Индексированный. Для уменьшения объемов изображения или для  использования определенных цветов используют данный формат. Элемент  матрицы a_i,j является указателем на таблицу цветов. Число используемых цветов равно 2^K, где K - количество бит, используемый для хранения элемента матрицы. Цвета в указываемой таблице могут кодироваться другим числом бит. Например, в 256 цветовых режимах видеоадаптеров выбирается 256 цветов из 262144 возможных, так как выбираемые цвета представляются в RGB формате и для каждой цветовой компоненты кодируется 6-ю битами. Существует много методов преобразования многоканальных изображения в индексированные (Error diffusion, ближайшего цвета ...).

Фильтрация изображения.

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

 

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

 

3. Текстуры изображения. Чтобы понятно объяснить, что это такое проведем небольшой эксперимент. Расслабьтесь, вспомните интерьер вашего дома, например, письменный стол. Вы знаете его очертания, местоположение, цвет - это низкочастотные характеристики, вспомнили его заостренные углы, небольшую царапину где-нибудь ближе к его кромке - это высокочастотные составляющие. Также Вы знаете, что стол деревянный, но не можете в точности рассказать обо всех мельчайших деталях его поверхности, хотя общие характеристики (коричневый с темными впадинами, две области расхождения концентрических эллипсов от сучков) - наверняка. В данном случае в скобках - описание текстуры. Можно трактовать текстуру как характеристику участков в контурах изображения.

 

Будем рассматривать фильтры  в виде квадратной матрицы A. Пусть исходное изображение X, а получаемое как результат фильтрации - Y. Для простоты будем использовать матрицы 3x3:

Рекурсивными фильтрами  первого рода будут такие фильтры, выход Y которых формируется перемножением весовых множителей A с элементами изображения X. Для примера рассмотрим фильтры низких частот:

.

Фильтром низких частот пользуются часто для того, чтобы подавить шум в изображении, сделать его  менее резким. Используя фильтр A₃ , будем получать изображение Y следующим образом:

Выход фильтра второго рода формируется  аналогично первому, плюс фильтра B:

Для простоты рассмотрим одномерный фильтр вида: :

Рассмотрим и другие фильтры:

1. Высокочастотные (для подчеркивания резкости изображения):

 

2. Для подчеркивания ориентации:

 

3. Подчеркивание без учета ориентации (фильтры Лапласа):

.

 

4. Корреляционный:

,где

 

- коэффициенты корреляции между  соседними элементами по строке (столбцу). Если они равны нулю  то отфильтрованное изображение  будет совпадать с исходным, если  они равны единице, то фильтр  будет эквивалентен лапласиану. При обработке изображений очень  часто используют последовательность  фильтров: низкочастотный + Лапласа.  Часто используют и нелинейную  фильтрацию. Для контрастирования  перепадов изображения используют  градиентный фильтр:

 

, или его упрощенный вид:

 

.

 

Еще один часто используемый нелинейный фильтр - Собела:

 

A₀ ... A₇ - входы, y_i,j - результат фильтрации.

                        

 

Рекурсивная версия :

где B₀ ... B₇ - выход отфильтрованного изображения.

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

Сжатие.

Изображения, в машинном представлении, - двумерная матрица  N на M, где N - его ширина, M - высота. При сканировании обычно используют разрешение от 72 до 2400 dpi (dots per inch - точек на дюйм). Наиболее часто - 300 dpi. Если взять лист бумаги 21/29 см с изображением и отсканировать его в RGB Truecolor, то несжатое изображение будет занимать ~27300000 байтов или 26 Мбайт. Обычно в базах данных применяют изображения порядка от 320x240 до 640x480. Но и они занимают 76 до 900 Кбайт. А что, если таких изображений сотни, тысячи? В данном разделе рассмотрим методы сжатия. Они применительны для любых массивов данных, а не только для изображений. О методах сжатия, характерных только для изображений узнаем немного позже. Будем рассматривать статическое сжатие, то есть массив данных для сжатия целиком сформирован. Методы сжатия статического часто подразделяют на последовательное и энтропийное. Последовательное сжатие использует в работе наличие повторяющихся участков. Энтропийное используется с целью сокращения к минимуму избыточности информации. Последовательное применение этих методов позволяет получить хороший результат.

Последовательное сжатие.

Наиболее часто применяют  метод RLE. Почти в любом изображении, особенно в компьютерных рисунках, встречаются последовательности одинаковых байтов. Например, в участке изображения, в котором нарисована часть неба, идут подряд несколько значений голубого цвета. Для участка вида: ККККККККЗЗЗЗСЗССССССССС , где К- красный, З - зеленый, С - синий цвета, будет закодирован как (8,К),(4,З),С,З,(10,С). В скобках - пары количество повторений, значение байта. Вот как данный метод применяется в формате PCX. Декодирование: если код принадлежит множеству [192..255], то вычитаем из него 192 и получаем количество повторений следующего байта. Если же он меньше 192, то  помещаем его в декодируемый поток без изменений. Оригинально кодируются единичные байты в диапазоне [192..255] - двумя байтами, например, чтобы закодировать 210 необходимо, представить его как (193, 210). Данный метод дает выигрыш в среднем в 2 раза. Однако для отсканированных изображений, содержащих плавные цветовые переходы (то есть повторяющиеся цепочки почти не встречаются), данный метод может преподнести сюрприз - размер массива с закодированным изображением будет больше исходного.

Наиболее распространены в настоящее время модификации  алгоритма LZ (по имени их авторов - Лемпела и Зива). По сравнению с RLE сделан шаг вперед - будем искать в исходном материале не последовательности одинаковых видов, а повторяющихся цепочек символов. Повторяющие цепочки в кодированном сообщении хранятся как ссылка на первое появление данной цепочки. Например, в цепочке КЗСЗБСКЗСЗБ начиная с 7 символа, идет цепочка КЗСЗ, которую мы можем заменить ссылкой на 1-ый символ. Рассмотрим наиболее распространенные реализации алгоритма LZ:

 LZ77 - при работе выдает тройки вида (A, B, C), где A - смещение (адрес предыдущей цепочки B байтов которой совпадают с кодируемой цепочкой), B - длина цепочки, C - первый символ в кодируемом массиве, следующий за цепочкой. Если совпадение не обнаружено то создается тройка вида (0, 0, С), где C - первый символ кодируемой цепочки. Недостаток такого подхода очевиден - при кодировании «редких» байтов мы «сжимаем» один байт в три. Преимущество - простота реализации, большая скорость декодирования.

 LZSS - создает при работе вектора вида (флаг, C) и (флаг, A, B). Если битовый флаг=0, то следующий за ним C трактуется, как единичный байт и выдается в декодируемый массив. Иначе, когда флаг=1, то в декодируемый массив выдается цепочка длиною B по смещению A. LZSS кодирует намного более эффективно, по сравнению с LZ77, так как использует битовые флаги и мало проигрывает при кодировании одиночных символов. При кодировании строится словарь встречающихся цепочек в виде двоичного упорядоченного дерева. Скорость и простота алгоритма декодирования массива у LZSS также высока.

 

LZMX (упрощенный LZM) - данный алгоритм предназначен для скоростного кодирования и по эффективности уступает LZSS, заметно обгоняя его по скорости работы. При работе кодер LZMX формирует несколько векторов вида:

1. (0, A, несжатый поток) - где 00 -2х битовый флаг признака данного блока, A (7 битов с диапазоном в [1..127]) - длина следующего за ним несжатого потока в байтах..
2. (0, 0000000, A, B) - где, A - количество повторяющего байта B. То есть код RLE.
3. (1, A, B) - где A(7 битов с диапазоном в [1..127]) - длина декодируемой цепочки, B - ее смещение. 

 

Для быстрого поиска повторяющихся  цепочек используется хеш. Индекс - 12 битовый, вычисляется как [ (a*4) xor (b*2) ] xor c, где a, b, c - первые символы цепочки. Индекс дает смещение в массиве ранее встреченной цепочки с теми же первыми символами. Использование хеша и дает высокую скорость кодирования.  
Декодирование также имеет большую скорость - читается бит - флаг, если он есть 0 и следующие за ним 7 битов также ноль, читаем следующие два байта - A и B и копируем  в выходной массив байт B  A - раз: если при флаге=0 следующие 7 битов=A больше нуля, то в выходной массив копируем A байтов следующих за A. И, наконец, если флаг установлен в единицу, то  читаем A и следующий за ним байт B и копируем в выходной массив цепочку длиною A байт со смещения B.

Существуют и другие модификации  алгоритма LZ (LZW, LZS, LZ78 ...). Общее свойство LZ - высокая скорость декодирования. Общая проблема - эффективность поиска кодируемых цепочек. Модификация данного алгоритма используется в графическом формате GIF.