30693-1 (663164), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

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

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

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

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

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

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

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

.

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

,где

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

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

.

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

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

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

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

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

3.Сжатие.

Изображения, в машинном представлении, - двумерная матрица 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 формирует несколько векторов вида:

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

(0, 0000000, A, B) - где, A - количество повторяющего байта B. То есть код RLE.

(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.

Энтропийное сжатие.

Энтропийное сжатие в отличие от последовательного, в качестве информации о входном массиве использует только частоты встречаемости в нем отдельных байтов. Эту информацию он использует как при кодировании, так и при декодировании массива. Ее представляют в виде 256 компонентного вектора, координата i которого представляет собой сколько раз байт со значением i встречается в исходном массиве. Данный вектор занимает небольшое пространство и почти не влияет на степень компрессии. Многие методы энтропийного кодирования видоизменяют данный вектор в соответствии с используемым алгоритмом. Рассмотрим два наиболее часто используемых методов:

Метод Хаффмана. Данный метод сокращает избыточность массива, создавая при кодировании переменную битовую длину его элементов. Основной принцип таков: наиболее часто встречающемуся байту - наименьшую длину, самому редкому - наибольшую. Рассмотрим простейший пример кодирования методом Хаффмана - способ конечного нуля. Любой элемент кодируется цепочкой битов, состоящей из одних единиц и кончающийся нулем. Таким образом, самый частый закодируем одним битом - 0, следующий за ним по частоте как 10, далее - 110, 1110, 11110 и т.д. Процедура декодирования также очевидна.

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

Таким образом, мы закодировали исходный массив как 0 110 10 1110 0 10 0 11110 10 0. Итого: длина выходного сообщения - 22 бита. Степень компрессии ~4.

Метод арифметического кодирования. Данный метод появился позднее. Его принцип - кодирование исходного массива одним числом. Часто входной массив разбивают на одинаковые небольшие участки и кодируют их по отдельности, получая в результате последовательность кодовых чисел. Закодируем предыдущий пример числом, лежащим в единичном диапазоне. Схема кодировки следующая. Строим таблицу частот, каждому элементу таблицы ставим в соответствие диапазон, равный его частоте поделенной на длину входного массива. Устанавливаем верхнюю границу ВГ в 1, нижнюю НГ в 1. Далее N раз выполняем следующую последовательность действий (где N - длина кодируемого участка или всего массива):

Читаем из массива очередной символ.

Установка текущего интервала. Интервал И = ВГ - НГ.

ВГ = НГ + И*ВГ символа (берем из таблицы).

НГ = НГ + И*НГ символа (берем из таблицы).

Рассмотрим на примере: КЗСГКСКБСК. Построим необходимую таблицу:

Теперь, собственно, сама процедура кодирования:

Таким образом, любое число в диапазоне [0.18989472 .. 0.1898954112] однозначно кодирует исходный массив. В двоичном дробном виде как 0.XXXXXXXX...Для хранения такого числа хватит n бит (размерность XXXXXXXX....), где n ближайшее целое, удовлетворяющее неравенству: 2ⁿ > Интервал^-1=0.0000006912^-1. Искомое n равно 21. То есть мы можем закодировать исходный массив 21 битом. В данном примере - 001100001001110111111. Процедура декодирования обратная и состоит в выполнении n раз следующего:

Характеристики

Список файлов реферата