Разработка математической модели кодера и декодера алгоритма JPEG

JPEG - один из новых и достаточно мощных алгоритмов. Оперирует алгоритм областями 8x8, на которых яркость меняется сравнительно плавно. Вследствие этого при разложении матрицы такой, области в двойной ряд по косинусам значимыми оказываются только первые коэффициенты. Алгоритм разработан группой экспертов в области фотографии. JPEG – подразделение в рамках Международной организации по стандартизации.

Метод позволяет сжимать некоторые изображения в 10-15 раз без серьезных потерь. Существенными положительными сторонами алгоритма является то, что задаётся степень сжатия (2-200 (задаётся пользователем)). Как мы выясним ниже, выходным изображением данного формата будет изображение в градациях серого без резких переходов цветов.

JPEG, как уже говорилось выше, использует несколько методов кодирования изображения: DCT, RLE, кодирование Хаффмана. Структурные схемы алгоритма для шифратора и дешифратора алгоритма JPEG показаны на рисунках 1 и 2 соответственно.

Рисунок 1 — Структурная схема шифратора алгоритма JPEG

Рисунок 2 — Структурная схема дешифратора алгоритма JPEG

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

Матрица 8х8 переводится в 64-элементный вектор при помощи «зигзаг»-сканирования, т.е. берутся элементы с индексами (0,0), (0,1), (1,0), (2,0)..., как показано на рисунке 3.

Рисунок 3 — «Зигзаг»-сканирование

Далее производится сжатие алгоритмом группового кодирования RLE и алгоритмом Хаффмана с использованием готового алфавита в виде таблицы кодирования.

Декодирование изображения происходит по тому же принципу, только в обратном порядке.

В результате проведенной работы было разработано программное обеспечение, листинг которого приведен в приложении В.

1.3.1 Применение дискретного косинусного преобразования

Дискретное косинусное преобразование представляет собой преобразование информации без потерь и не осуществляет никакого сжатия. DCT подготавливает информацию для этапа сжатия с потерями или округления.

Дискретное косинусное преобразование осуществляет перевод отдельных блоков изображения из пространственной в область пространственных частот. Для многокомпонентных изображений, например, RGB (Red, Green, Blue), DCT применяется раздельно к блокам каждого компонента. Известно, что пиксели изображения имеют корреляцию по двум направлениям (горизонтальном и вертикальном). Поэтому методы сжатия изображений используют двумерное DCT, которое задается формулой:

где i – горизонтальнаякоордината пиксела в матрице ДКП;

j – вертикальная координата пиксела в матрице ДКП;

 – матрица коэффициентов ДКП;

х – горизонтальная координата пиксела в исходной матрице;

y – вертикальная координата пиксела в исходной матрице;

N – порядковый номер преобразования;

 – матрица исходных коэффициентов преобразования;

– матрица косинусного преобразования размером 8х8, элементы которой определяются по формулам:

где i –координата пиксела в матрице ДКП по оси абсцисс;

j – координата пиксела в матрице ДКП по оси ординат;

N – порядковый номер преобразования.

Двумерное обратное косинусное преобразование описывается следующим уравнением:

Два члена под знаком косинуса являются ядрами преобразования, показанными ниже на рисунке 4.

Рисунок 4 — Графическое представление двумерного DCT

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

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

Исследование алгоритма JPEG

В рамках данной части научно-исследовательской работы в математическом пакете MATLAB мною был создан код кодера и декодера чёрно-белого изображения с использованием методов JPEG.

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

Однако, главным способом уменьшения объёма информации без потерь в JPEG является кодирование Хаффмана. Возьмём для начала такую матрицу квантования, при которой (как и задумано) человеческому глазу не видно потерянную информацию в декодированном изображении.

При использовании матрицы квантования, продиктованной стандартом JPEG, нули в декодированном изображении составляют доли процента — 0.17%.

Характеристики изображений:

- объём исходного изображения – 262144 байта;

- объём закодированного изображения (после кодирования Хаффмана) – 24042 байта.

    Матрица квантования:

.

Как видим объём данных, передаваемых по каналам, уменьшилось более чем в 10 раз, что обеспечит значительное уменьшение скорости передачи. И напомню, что такое уменьшение не заметно человеческим зрением, как можно убедиться, сравнив рисунок 5 и рисунок 6.

      Рисунок 5 — Исходное тестовое изображение «Лена»

   Рисунок 6 — Декодированное изображение «Лена»

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

.

 

    Произошло увеличение объёма данных в 1,5 раза:

- объём исходного изображения – 262144 байта;

- объём закодированного изображения (после кодирования Хаффмана) – 411656 байта.

Ниже мы убедимся, что при увеличении индекса квантования, размер данных после кодирования уменьшается и без использования кодирования Хаффмана. Но потеря качества изображения непомерно высока, что видно невооружённым глазом, сравнив рисунок 7 и рисунок 8.

Увеличим значение чисел в матрице квантования в 15 раз. В таком случае наглядно видно количество потерянной информации в «квадратах» 8х8. Очень многие квадраты были переведены в один и тот же цвет в результате квантования.

Процент нулей в декодированном изображении составляет 17%. Это та информация, которая утеряна безвозвратно из-за особенностей метода кодирования JPEG. Если мы посмотрим на блок-схему реализации алгоритма, то увидим блок с названием «квантователь», использующий «таблицу квантования». В процессе этого этапа каждый элемент исходной матрицы 8х8 терпит деление на соответствующий элемент матрицы квантования. Именно с этот момент происходит безвозвратная потеря информации.

Такой метод называется алгоритмом сжатия изображения с потерями. Сами потери были переведены в рисунок, названный изображением ошибки (рисунок 9). Изображение получено путём вычитания из исходного изображения конечный вариант декодированных данных. На нём белым цветом показаны пикселы, которые были потеряны в результате квантования.

В данном случае объём данных уменьшился в 60 раз:

- объём исходного изображения – 262144 байта;

- объём изображения после безвозвратной утери информации – 85512 байта;

- объём закодированного изображения (после кодирования Хаффмана) – 4360 байта.

       Рисунок 7 — Исходное тестовое изображение «Лена»

Рисунок 8 —Декодированное изображение «Лена» (матрица х15)

Рисунок 9 — Изображение ошибки после декодирования изображения «Лена»

    При применении кодирования JPEG может сложиться ложное впечатление, что возможно уменьшать объёмы изображения при необходимости и не испытывать впоследствии проблем с узнаванием фотографии, раз мы берём матрицу квантования с большим коэффициентом сжатия и потеря качества не влияет на распознавание фотографии. Это верно для многих кусочков фотографий, тех, чьи значения не меняются резко, как в случае с «Девушкой в шляпе». Однако, на границе контрастных участков значения будут резко «скакать». Как мы можем убедиться на следующем примере.

    Также следует обратить внимание, что качество восстановленного изображения зависит от расположения в пространстве границы резкого цветового перехода. На рисунках 10 и 11 ясно видно, что в случае с горизонтальной или вертикальной полосой появляются ореолы. Это называется эффектом Гиббса. А на цветовом переходе наклонных границ отчётливо видно, как изображение распадается на отдельные квадраты и размывается при высокой степени сжатия. Это связано с тем, что происходят большие потери в низких частотах при квантовании и восстановить исходные данные становится невозможно.                                                                             

                         а)                                                         б)                            

Рисунок 10 — (а) Исходное изображение (б) Декодированное изображение «food»

 

                     а)                                                              б)                                    

Рисунок 11 —  Горизонтальная линия (а) исходная (б) декодированная

    Обращаю внимания на плавные переходы изображения «food», увеличенные на рисунке 12. Распад на квадраты обусловлен первоначальным делением пикселов изображения на квадраты 8х8 для удобства применения ДКП, последующего квантования и «зигзаг» сканирования. В данном случае такое искажение не мешает нам понимать, что изображено на картинке ввиду простоты изображения, но при применении данного способа в целях разведки может стать критическим при восприятии фото и видеоинформации.

                      а)                                                               б)                                  

Рисунок 12 — Наклонная линия (а) исходная (б) декодированная

    Изображение «baboom» (рисунок 13) имеет большие области одного цвета, что даёт хорошие предпосылки для степени сжатия изображения с минимальными потерями при декодировании.

                            а)                                                       б)                                  

Рисунок 13 —Изображение baboom (а) исходное (б) декодированное при m=2

При 2-кратном увеличении матрицы квантования (m=2) объём передаваемых данных в тестовом изображении «baboom.bmp» уменьшился в 7.1 раза:

- объём исходного изображения – 65536 байт;

- объём закодированного изображения (после кодирования Хаффмана) – 9160 байт;

- количество нулей в исходном изображении – 0,0305%;

- количество нулей в декодированном изображении – 0,0977%.

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

                            а)                                                       б)                              

Рисунок 14 —Изображение baboom (а) исходное (б) декодированное при m=4

Заметное ухудшение качества становится заметно при 4-кратном увеличение матрицы квантования (рисунок 14). В этом случае объём данных уменьшился более чем в 12 раз:

- объём исходного изображения – 65536 байт;

- объём закодированного изображения (после кодирования Хаффмана) – 5406 байт;

- количество нулей в исходном изображении – 0,0305%;

- количество нулей в декодированном изображении – 0,5859%.

    За счет больших областей одного тона наибольшая ошибка происходит на стыке областей разных оттенков и в местах мелких деталей. Для наглядности возьмём 15-кратное увеличение матрицы квантования. При таком большом значении коэффициента m изображение ошибки на рисунке 15а наглядно показывает «больные» места. В данном случае произошло сжатие в 34.8 раза (рисунок 14б), а процент нулей в декодированном изображении более 23%.

                

а)                                                                    б)

Рисунок 15 —изображение baboom (а) изображение ошибки (б) декодированное

Характеристики изображения:

- объём исходного изображения – 65536 байт;

- объём закодированного изображения (после кодирования Хаффмана) – 1882 байт;

- количество нулей в исходном изображении – 0,0305%;

- количество нулей в декодированном изображении – 23,1445%.

    И последним объектом исследования нам послужит тестовое изображение «Barbara». По рисунку 16 видим, что исходная матрица квантования отлично работает и не даёт видимой ошибки. Сжатие данных происходит в 7,6 раза. А количество нулей в декодированном изображении ничтожно мало.

    Однако, при коэффициенте квантования m ≥3 проявляются негативные последствия особенностей изображения, а именно: потеря информации в местах стыка двух областей с разными цветами. В изображении Barbara, как можно заметить, таких мест предостаточно: платок, брюки, скатерть. Присутствуют также и большие участки одного цвета, которые будут преобразованы в однотонные участки при больших индексах квантования, например, пол.

                          а)                                                           б)                                  

Рисунок 16 —Изображение baboom (а) исходное (б) декодированное при m=1

Характеристики изображения:

- объём исходного изображения – 262144 байт;

- объём закодированного изображения (после кодирования Хаффмана) – 34244 байт;

- количество нулей в исходном изображении – 0,0000 %;

- количество нулей в декодированном изображении – 0,0244%.

    Все эти особенности наглядно видно на рисунке 17 при 15-кратном увеличении матрицы квантования. «Больными» местами оказываются именно брюки, платок и скатерть в местах резкого перехода оттенков.

    В итоге, из-за особенностей данного изображения мы можем сжать его не более чем в 11.5 раз без видимой потери качества. Такое сжатие обеспечивает коэффициент квантования m=2 (рисунок 18). Матрица квантования при этом выглядит следующим образом:

.

    Характеристики изображений:

- объём исходного изображения – 262144 байт;

- объём закодированного изображения (после кодирования Хаффмана) – 22686 байт;

- количество нулей в исходном изображении – 0,0305 %;

- количество нулей в декодированном изображении – 0,2197 %.

 

                      а)                                                                    б)                                  

Рисунок 17 —Изображение Barbara (а) ошибка (б) декодированное при m=15

                         а)                                                           б)                                  

Рисунок 18 —Изображение baboom (а) исходное (б) декодированное при m=2

    В результате проделанной работы по исследованию алгоритма JPEG были сделаны выводы о его пригодности к специальным задачам, рассмотренным в данной ВКР:

- показана необходимость использования преобразования Хаффмана и его положительная роль в уменьшении объёма передаваемых данных;

- исследована роль матрицы квантования её влияние на разные типы изображений, таким образом, показана адаптация алгоритма JPEG к особенностям участков изображений.