Цифровая обработка изображений

 

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

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

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

 

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

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

 

Цвет

Частота

Код

К

4

0

З

1

110

С

3

10

Г

1

1110

Б

1

11110

 

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

 

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

 

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

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

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

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

 

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

 

Цвет

Частота

Нижняя граница НГ

Верхняя граница ВГ

К

4

0

0.4

З

1

0.4

0.5

С

3

0.5

0.8

Г

1

0.8

0.9

Б

1

0.9

1

 

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

 

Шаг

Символ

НГ

ВГ

Интервал

0 

 

0

1

1

1

К

0

0.4

0.4

2

З

0.16

0.2

0.04

3

С

0.18

0.192

0.012

4

Г

0.1896

0.1908

0.0012

5

К

0.1896

0.19008

0.00048

6

С

0.18984

0.189984

0.000144

7

К

0.18984

0.1898976

0.0000576

8

Б

0.18989184

0.1898976

0.00000576

9

С

0.18989472

0.189896448

0.000001728

10

К

0.18989472

0.1898954112

0.0000006912

 

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

 

1.   Ищем в таблице интервал, в который попадает наше число Ч, и выдаем символ в него входящий  в декодируемый массив.

2.   Интервал И = ВГ символа - НГ символа (оба значения - из таблицы).

3.   Ч = (Ч - НГ) / И.

 

Шаг

Число

Символ

НГ

ВГ

Интервал

1

0.18989472

К

0

0.4

0.4

2

0.4747368

З

0.4

0.5

0.1

3

0.747368

С

0.5

0.8

0.3

4

0.82456

Г

0.8

0.9

0.1

5

0.2456

К

0

0.4

0.4

6

0.614

С

0.5

0.8

0.3

7

0.38

К

0

0.4

0.4

8

0.95

Б

0.9

1

0.1

9

0.5

С

0.5

0.8

0.3

10

0

К

0

0.4

0.4

 

В данном примере арифметический кодер «обогнал» метод Хаффмана на 1 бит. В отличие от метода Хаффмана трудоемкость алгоритма значительна. В чем же тогда «полезность» алгоритма? Рассмотрим последовательность КККККККС. При кодировании методом Хаффмана получим выходную последовательность длиной в 9 бит (можно и в 8, так  как массив состоит из 2 разных байт). При арифметическом кодировании  данную последовательность можно закодировать числом 0.4375 или в двоичном виде как 0111, занимающей 4 бита. То есть при арифметическом кодировании возможно получать плотность кодирования меньше бита на символ. Это свойство проявляется, когда во входном массиве частоты некоторых символов значительно выше остальных.

 

 

 

Обработка графической информации.

 

Для простоты изложения пусть  изображение хранится в квадратной матрице X с элементами x_i,j N строк на N столбцов. Для некоторых методов применяют разбивку исходного изображения на блоки. Обрабатывая матрицу, мы будем иметь временную сложность алгоритма как минимум кратной N³ . Для ее уменьшения поступают следующим образом: разбивают изображение на несколько малых размером n на n, n << N, каждое малое изображение будем обрабатывать отдельно. Тогда, вместо N³ будем иметь N²n сложность алгоритма.

 

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

Самый первый способ, который  приходит в голову, следующий. Уменьшим количество бит для хранения одного пикселя (элемента исходной матрицы). Пусть  пикселы исходного изображения имеют формат RGB Truecolor 8:8:8 (на каждую цветовую составляющую отводится по 8 бит). Перекодируем изображение в формат 5:5:5 (то есть каждая цветовая составляющая будет иметь 2⁵ =32 градации), отбрасывая младшие четыре бита изображения. Мы также можем использовать свойство глаза наиболее хорошо различать цвет в области зеленого и кодировать изображение в формат RGB 4:5:4 и каждый пиксел будет занимать два байта.

Можно пойти еще дальше: перевести исходное изображение  в другую цветовую модель и отформатировать  его. Например, в YIQ 6:3:3 - отводим на яркость 6 бит, на синфазный и интегрированный  каналы по 3, используя то, что человеку более важна информация об интенсивности, нежели о цвете. При «жадном» кодировании, когда используем малое количество бит на пиксел, сразу после декодирования, перед выводом изображения можно провести так называемый anti-aliasing - сгладить резкие цветовые переходы, возникшие из-за малого числа градаций цветовых составляющих. Дальнейшее усовершенствование заключается в индексировании цветов. RGB Truecolor формат может поддерживать более 16 млн. цветов. Выберем n (обычно n - степень 2 ) индексных цветов c_K так, чтобы минимизировали сумму:

 

.

Далее создаем выходной массив B N на N, элемент которого b_i,j равен k, где k= m - номер цвета такой, что выполняется  . Выходная информация - массив B и собственно таблица индексных цветов c. Результаты данного подхода можно посмотреть в разделе «Форматирование и индексирование изображений».

 

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

.

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

. Самый оптимальный метод  - Карунена-Лоэва. Строки матрицы преобразования A - нормированные собственные вектора K_x,  то есть являются решением уравнения вида K_xx = l_ix, K_x = E{(x- Ex)(x-Ex)^T} - ковариация, E - мат. ожидание, T - знак транспонирования. Коэффициенты преобразования y=Ax имеют матрицу преобразования вида:

, где l₁.. l_g - собственные значения K_x. Отбрасывая малые собственные значения получаем сжатие. Данный метод, хотя и дает наименьшую ошибку приближения среди аналогичных кодеров, используется редко, так как требует большого объема вычислений при своей работе. Преобразование Карунена-Лоэва называют также оптимальным кодированием. Рассмотрим другие кодеры данного семейства:

1. Фурье,, для данного преобразования существует алгоритм, с временной сложностью n²log₂n. Преобразование Фурье представляет собой разложение по спектру.

2. Дискретное косинусное  преобразование (ДКП).

.Наиболее используемый

в настоящее время метод, так как он дает результат ошибку приближения чуть больше чем разложению Карунена-Лоэва. Существует алгоритм, реализующий данный метод со сложностью 2n²log₂n-1.5n+4.

3.Симметричное преобразование  Адамара.

, где

i_l и j_l - состояние разрядов двоичного представление чисел i и j. Для n=2 матрица будет следующей: . Хотя метод Адамара не дает столь хороших результатов как предыдущие, зато все операции преобразование сводится к сложениям и вычитаниям.

 

При отборе коэффициентов  пользуются следующими способами:

1.Пороговый отбор. Отбрасываются  коэффициенты, которые по модулю, ниже установленного порога.

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

 

Обычно отбрасываемые  коэффициенты обнуляют. Далее применяют  последовательное и энтропийное сжатие. Так работает алгоритм JPEG кодирования. Все это дает снижение размера массива, при приемлемом качестве изображения, в 5-16 раз. На приведенном примере использовалось исходное изображение в разрешении 240 на 362 пикселя в RGB Truecolor и занимало 240*362*3=260640 байт. Левое сжатое изображение занимает 46000 байт и внешне не отличается от исходного. Левое нижнее изображение имеет размер 8004 байт и имеет заметные резкие цветовые переходы в области неба. Правое нижнее изображение имеет размер 5401 байт (!) и хотя изображение стало слишком мозаичным, мы вполне можем понять его содержание. При использовании разбивок на блоки иногда возникает побочный эффект: становятся заметными границы блоков. Для борьбы с ним разбивку проводят так, чтобы блоки «наезжали» на границы соседних с ним блоков.