Файл: Методы кодирования данных ( КОДИРОВАНИЕ И МЕТОДЫ КОДИРОВАНИЯ ).pdf

«Текущий интервал» становится меньше с каждым новым кодированным символом, и требуется все больше бит, чтобы выразить его, однако на выходе получаем единственное число [6]^[17].

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

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

2.1.6. МЕТОД JPEG-LS

Алгоритм JPEG-LS основан на формате LOCO-I (Low Complexity Lossless Compression for Images), который был разработан компанией Hewlett-Packard для сжатия непрерывно-тоновых изображений. Официально этот метод известен как рекомендация ISO/IEC CD 14495.

JPEG-LS кодирование состоит из следующих шагов:

изучает несколько предыдущих соседей текущего пиксела и рас- сматривает их как контекст этого пиксела;

использует контекст для прогнозирования пиксела и для выбора распределения пиксела и для выбора распределения вероятностей из нескольких имеющихся;

применяет полученное распределение вероятностей для кодирования ошибки прогноза с помощью специального кода Голомба.

Если большое количество пикселов в строке одинаковы, то используется кодирование длин серий. Сжатый файл состоит из сегментов данных (содержащих коды Голомба и длины серий), сегментов маркеров (в качестве которых используются некоторые зарезервированное маркеры JPEG).

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

2.1.7. АЛГОРИТМЫ С ПОТЕРЕЙ ДАННЫХ

Изображения крайне важны для современного человека, но они требуют большого объема памяти. Алгоритмы сжатия изображений с потерей данных сжимают психофизическую избыточность [9]^[18]. Этот вид избыточности обусловлен особенностями зрительной системы человека. Например, объекты малого размера с малой контрастностью не заметны для глаза на изображении, поэтому их можно не передавать.

Как правило, в таких алгоритмах можно задавать степень потери качества, создавая компромисс между качеством и объемом изображения. Существует множество критериев оценки потерь качества (например, среднеквадратичное отклонение, пиковое отношение сигнал-шум), но часто оценка этими критериями расходится с визуальной оценкой человеком. Лучше всего потерю качества оценивают наши глаза. Отличным считается сжатие, при котором исходное и сжатое изображение не различить. Хорошим – когда можно отличить сжатое изображение только в сравнении с оригинальным. При дальнейшем сжатии, как правило, становятся заметны артефакты, характерные для данного алгоритма.

2.1.8. АЛГОРИТМ СЖАТИЯ JPEG

JPEG назван по первым буквам организации, разработавшей этот алгоритм – Joint Photographic Experts Group (Объединенная группа экспертов по фотографии). Метод позволяет сжимать любые изображения: как полутоновые черно-белые, так и цветные. Далее будем рассматривать алгоритм сжатия цветных изображений.

В цветном изображении каждый пиксел описан тремя байтами, по байту на цвета красный (R), зеленый(G) и синий(B). Сжатие начинается с разбиения изображения на блоки 16x16 отсчетов, затем сжимаются независимо друг от друга. Если число строк или столбцов изображения не кратно 8, то самая нижняя строка или самый правый столбец повторяются нужное число раз[8]^[19].

Далее в каждом блоке переводим изображение в другую цветовую систему: из RGB в YCrCb по формуле (2).

где Y-яркостная компонента; Cr-цветоразностная красная компонента; Cb-цветоразностная синяя компонента; R, G, B – значения красной, зеленой и синей компоненты цвета соответственно.

Переход к системе YCrCb выгоден, так как глаз лучше замечает переходы яркости, чем цвета, поэтому компоненты Cr и Cb можно сильнее сжимать.

Далее блок 16х16 яркостной компоненты делится на 4 блока 8х8 отсчетов каждая, а цветоразностные матрицы Cr и Cb с помощью прореживания преобразуются в матрицы 8х8 отсчетов. При прореживании этих матриц удаляются каждая вторая строка и каждый второй столбец. При декодировании недостающие элементы восстанавливаются интерполированием. Такое преобразование допустимо, так как глаз имеет пониженную остроту при наблюдении чисто хроматических изображений и не замечает подобных погрешностей [16]^[20].

На данном этапе у нас 4 матрицы яркостной компоненты Y и 2 цветоразностных матрицы Cr и Cb. К каждой матрице применяется дискретное косинус преобразование (ДКП), в результате получаем матрицу частотных коэффициентов. Особенность матриц состоит в том, что полученные коэффициенты расположены в определенном порядке: коэффициенты низкой частоты – в левом верхнем углу, высокой частоты – в правом нижнем. Крупные объекты на изображении соответствуют низкочастотным составляющим, а мелкие – высокочастотным. Коэффициенты низкой частоты оказываются больше коэффициентов высокой частоты. На данном этапе происходит некоторые необратимые изменения в информации из-за ограниченности точности машинных вычислений. Несмотря на то, что пока не произошло сжатия, происходит очень слабое искажение изображения.

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

Следующим шагом матрица 8х8 преобразуется в вектор из 64 элементов. Для того, чтобы нулевые и единичные коэффициенты оказались сгруппированы в одном месте, используется специальный метод, называемый зиг-заг сканированием, пример на рисунке 1.

Рисунок 1 – Зиг-заг сканирование

Зиг-заг сканирование начинается с точки (0,0). В начале считываются коэффициенты с большими значениями, в конце – с малыми. В результате получаем последовательность из 64 значений, в начале которого большие числа, а ближе к концу - последовательность из нулей и единиц. Этот код сжимается с помощью метода Хаффмана с фиксированной таблицей CCITT Group 3.

При декодировании повторяются все шаги кодирования в обратном порядке. Переход из системы YCrCb в RGB выполняется по формуле (3).

где Y-яркостная компонента; Cr-цветоразностная красная компонента; Cb- цветоразностная синяя компонента; R, G, B – значения яркости красной, зеленой и синей компоненты соответственно.

Этот алгоритм широко распространен в нынешнее время. Коэффициент сжатия цветных изображений при отличном сжатии может достигать 6-10. В большинстве графических редакторов можно изменять степень сжатия в обмен на качество. Это реализовано с помощью изменения коэффициентов матрицы квантования. Но чем больше степень сжатия, тем больше будет заметны артефакты на восстановленном изображении. В случае JPEG это будет блочность – выделение границ блоков 8х8, с которыми производятся преобразования.

2.1.9. ВЕЙВЛЕТ-ПРЕОБРАЗОВАНИЕ

Вейвлет (Wavelet) переводят как «короткая волна» или «всплеск». В алгоритме к исходному изображению применяются так называемые вейвлет- и скейлинг-функции [3]^[21]. В результате вейвлет-преобразования спектр исходного сигнала делится на низкочастотную и высокочастотную компоненты, причем, в случае сжатия изображения.

Рассмотрим алгоритм на примере черно-белого изображения. Изображение разбивается на группы 2х2 пиксела, обозначим яркость пикселов L(2k, 2n), L(2k + 1,2n ), L(2k , 2n + 1), L(2k + 1,2n + 1) , где k – номер строки, n – номер столбца. Яркость используется для вычисления последовательностей v⁽¹⁾ (k,n), v⁽²⁾ (k,n), v⁽³⁾ (k,n), v⁽⁴⁾ (k,n), которые представляют собой полусуммы и полуразности яркостей, см. формулу (4).

Эти компоненты объединяются в четыре матрицы и размещаются рядом, как показано на рисунке 2. Так же на рисунке 2 обозначена ориентация контуров, представляемых матрицами v⁽²⁾ (k,n), v⁽³⁾ (k,n), v⁽⁴⁾ (k,n).

v⁽¹⁾ (k,n)v⁽²⁾ (k,n)

v⁽³⁾ (k,n)v⁽⁴⁾ (k,n)

а б

Рисунок 2– а – матрица отсчетов; б – матрицы компонентов вейвлет-преобразования

Матрица v⁽¹⁾ (k,n) содержит уменьшенное исходное изображение и называется «аппроксимация». Компоненты v⁽²⁾ (k,n), v⁽³⁾ (k,n), v⁽⁴⁾ (k,n) называются «деталями» и представляют собой резкие границы, расположенные вертикально, горизонтально и по диагонали.

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

Декодирование происходит в обратном порядке: вначале отсутствующие отсчеты в матрицах восстанавливаются интерполяцией, а затем все компоненты суммируются.

В результате вейвлет-преобразования можно достигнуть коэффициента сжатия в 30-50 раз. Так же как и в JPEG коэффициент сжатия можно регулировать с помощью изменения коэффициентов матрицы квантования. Однако вейвлет-преобразование не лишено артефактов: характерные искажения – это окантовки и посторонние узоры.

2.1.10. АЛГОРИТМ JPEG2000

Алгоритм JPEG2000 был разработан в 2000 году той же группой экспертов, что и JPEG. JPEG2000 очень похож на своего предшественника, однако использует более ресурсозатратные операции. Основное различие в том, что вместо дискретного косинус-преобразования в нем используется вейвлет-преобразование.

Первым шагом осуществляется сдвиг по интенсивности каждого компонента RGB изображения, это делается для симметрирования динамического диапазона сигнала относительно нуля, что приводит к увеличению степени сжатия. Преобразование выполняется по формуле (5). При декомпрессии выполняется обратное преобразование.

где I_вых - интенсивность бита после преобразования; I_вх - интенсивность бита до преобразования; k – номер строки; n – номер столбца; ST – значение степени для каждого компонента R, G, B определяется кодером при сжатии и сообщается декодеру.

Следующим шагом изображение переводится из цветовой системы RGB в YUV по формуле (6). При декодировании используется обратное преобразование.

где R, G, B – значения красной, зеленой и синей компоненты цвета соот- ветственно; Y – яркостная компонента; U и V – цветоразностные состав- ляющие красная и синяя соответственно.

Далее применяется дискретное вейвлет-преобразование ко всем трем матрицам, причем для лучшего сжатия эта операция применяется трижды: вначале ко всему изображению, далее к получившимся аппроксимациям. В этом случае получаем до v⁽¹⁰⁾ (k, n) компоненты для каждой матрицы. В отличие от алгоритма JPEG в JPEG2000 не применяется прореживание матриц U и V, однако для этих компонент просто не сохраняют составляющие вейвлет-преобразования v⁽⁸⁾ (k, n), v⁽⁹⁾ (k, n), v⁽¹⁰⁾ (k, n). [13]^[22]

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

К результирующим отсчетам применяется энтропийное кодирование посредством так называемого MQ-кодера. В кодере производится де- корреляция отсчетов и арифметическое кодирование.

Так как алгоритм использует вейвлет-преобразование он достаточно ресурсозатратный, однако по сравнению с JPEG при одинаковом качестве размер файла отказывается меньшим.

2.1.11. ФРАКТАЛЬНОЕ КОДИРОВАНИЕ

Начало разработке данного метода положила работа Майкла Барнсли, открывшим новый класс теорем, которые можно использоваться для сжатия изображений. По сути, сжимается не само изображение, а алгоритм его построения [18]^[23]. Метод основывается на особенности природных объектов, который заключается в том, что эти объекты состоят из множества вариаций самоподобных элементов. То есть изображение состоит из некоторого количества основных элементов и их вариаций, например, окна в доме, чешуя на рыбе, границы между градациями цвета. Вариации создаются из основных элементов с помощью преобразований, называемых аффинные – преобразование координат X и Y и яркости.