10445

Реализация JPEG-подобного алгоритма сжатия изображений

Лабораторная работа

Информатика, кибернетика и программирование

Реализация JPEGподобного алгоритма сжатия изображений. Алгоритмы на основе дискретного косинусного преобразования наиболее распространенным из которых является разработанный в начале 1990х годов алгоритм JPEG Joint Photographic Expert Group являются относительно простыми в реал

Русский

2013-03-26

109 KB

66 чел.

Реализация JPEG-подобного алгоритма сжатия изображений.

Алгоритмы на основе дискретного косинусного преобразования, наиболее распространенным из которых является разработанный в начале 1990-х годов алгоритм JPEG (Joint Photographic Expert Group) являются относительно простыми в реализации и достаточно эффективными.

К положительным сторонам алгоритма относятся:

  •  Хорошая передача периодических структур даже при высоких степенях сжатия.
  •  Гибкость алгоритма и возможность подстраивать алгоритм под то или иные задачи дистанционного зондирования.
  •  Хорошая изученность алгоритма и наличие эффективных алгоритмов вычисления дискретного косинусного преобразования.
  •  Наличие серийных микросхем аппаратного сжатия и проектов прошивок ПЛИС.

К недостаткам алгоритма JPEG следует отнести:

  •  Эффективность алгоритма находится на уровне алгоритма ИСИ и уступает алгоритмам на основе вейвлет – преобразования.
  •  При высоких степенях сжатия изображение распадается на блоки.
  •  Проявляется эффект Гиббса в виде ореолов вокруг перепадов яркости в изображении.

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

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

Исходя из требуемой степени сжатия, можно определить расчетный объем информации, приходящейся на один макроблок. Если объем сжатой информации для текущего макроблока получился более чем в 1,1 раза больше расчетного, то коэффициент при матрице квантования γ увеличивается в 1,3 раза, что повышает степень сжатия следующего макроблока. Если объем сжатой информации для текущего макроблока получился меньше чем в 0,9 от расчетного, то коэффициент при матрице квантования γ уменьшается в 1,3 раза. Кроме того, если заполненность выходного буфера превышает 50%, то коэффициент γ увеличивается еще в 1,3 раза. После (или в процессе) сжатия очередного макроблока происходит передача данных из буфера. Объем передаваемой информации равен расчетному размеру сжатого макроблока. Если при передаче информации происходит опустошение буфера, то формируемый информационный пакет дополняется специальным кодом "пробел", который определяется на этапе формирования кодовой таблицы Хаффмана. Объем буфера должен быть не менее чем в 4 раза больше расчетного объема сжатого макроблока.

Блок – схема алгоритма приведена на рисунке 7.


Рисунок 7.


Сначала опишем собственно алгоритм сжатия. Изображение разбивается на блоки размером 8 на 8 пикселов. Каждый блок представляется в виде матрицы 8 на 8 элементов. Над каждым блоком производится дискретное косинусное преобразование по формуле

B = D*A*DT,          (1)

A – исходная матрица,

B – матрица после дискретного косинусного преобразования

D – фиксированная матрица. Коэффициенты матрицы, умноженные на 65536, приведены в таблице 3.

Таблица 3

23170

23177

23171

23170

23171

23179

23177

23177

32138

27246

18205

6393

-6393

-18205

-27246

-32138

30274

12540

-12540

-30274

-30274

-12540

12540

30274

27246

-6393

-32138

-18205

18205

32138

6393

-27246

23170

-23170

-23170

23170

23170

-23170

-23170

23170

18205

-32138

6393

27246

-27246

-6393

32138

-18205

12540

-30274

30274

-12540

-12540

30274

-30274

12540

6393

-18205

27246

-32138

32138

-27246

18205

-6393

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

Таблица 4

1

1

1

1

1

2

2

4

1

1

1

1

1

2

2

4

1

1

1

1

2

2

2

4

1

1

1

1

2

2

4

4

1

1

2

2

2

2

4

8

2

2

2

2

2

4

8

8

2

2

2

4

4

8

8

16

4

4

4

4

8

8

16

16

После этого полученная матрица 8 на 8 элементов переводится в 64-элементный вектор при помощи "зигзаг-сканирования". Порядок обхода элементов приведен на рисунке 6.

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

Элементы полученного 64-элементного вектора разделяется на 2 массива. Первый массив (DC-коэффициенты), состоит их 1-х элементов всех 64 элементных векторов в макроблоке и сжимается отдельно. Оставшиеся коэффициенты образуют 63-элементный вектор.

Каждому ненулевому элементу в этом векторе ставится в соответствие пара вида <количество нулей перед числом, число>. При этом количество нулей перед числом не должно превышать 15. В противном случае в качестве числа берется нуль. Например, пусть 63-элементный вектор имеет вид:

7, 0, 0, 0, 10, 0, -19, 7, 0, 0, 0, 0, 7, 0, 0, …только нули…, 0.

Он будет закодирован следующим образом:

<0 7>, <3 10>, <1 -19>, <0 7>, <4 7>, <КОНЕЦ БЛОКА>.

Здесь <КОНЕЦ БЛОКА> обозначает специально зарезервированное значение пары.

Если же имеется 63-элементный вектор такого вида:

10, 0, 0, 5, …33 нуля…, 1, 0, -2, … только нули…, 0,

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

<0 10>, <2 5>, <15 0>, <15 0>, <1 1>, <1 -2>, <КОНЕЦ БЛОКА>.

Здесь вторая, третья и четвертая пары кодируют последовательность из 33 нулей.

Затем полученный массив пар кодируется в виде двух потоков. Первый из них является байтовым и содержит т. н. байты-ключи, которые в 4 младших битах содержат информацию о числе пропускаемых нулей, а в 4 старших битах – информацию о количестве бит, необходимом для представления числа.

Таблица 5.

Число

Старшие биты байта-ключа

Информативные биты

0

0000

-

±1

0001

1 0

±2, 3

0010

11 10 00 01

±4…7

0011

111 110 101 100 000 001 010 011

±8…15

0100

±16…31

0101

±32…63

0110

±64…127

0111

±128…255

1000

±256…511

1001

±512…1023

1010

±1024…2047

1011

±2048…4095

1100

±4096…8191

1101

±8195…16383

1110

±16384…32767

1111

Информативные биты представляют собой все биты числа, включая знаковый, но исключая старший значащий бит, так как он при заданном числе бит всегда равен 1.

Символу <КОНЕЦ БЛОКА > соответствует байт-ключ 0xFF, причем такому ключу не ставятся в соответствие биты в потоке информативных бит.

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

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

Таблица 6.

Число

Количество бит

Информативные биты

0

0

-

-1 1

1

1 0

-3, -2, 2, 3

2

11 10 00 01

-7 -6 -5 -4 4 5 6 7

3

111 110 101 100 000 001 010 011

-15 -14 -13 -12 -11 -10 -9 -8 8 9 10 11 12 13 14 15

4

1111 1110 1101 1100 1011 1010 1001 1000

0000 0001 0010 0011 0100 0101 0110 0111

±16…31

5

±32…63

6

±64…127

7

±128…255

8

±256…511

9

±512…1023

10

±1024…2047

11

±2048…4095

12

±4096…8191

13

±8195…16383

14

±16384…32767

15

Информативные биты представляют собой все биты числа, включая знаковый, но исключая старший значащий бит, так как он при заданном числе бит всегда равен 1.

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

Алгоритм декодирования является обратным к алгоритму сжатия. Единственным отличием является использование вместо формулы (1) формулы

B = DT*A*D,          (2)

где А – матрица коэффициентов дискретного косинусного преобразования,

В – матрица фрагмента изображения.

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

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

Возможные варианты упрощенного алгоритма:

  •  Передача фиксированных коэффициентов из левого верхнего угла коэффициентов ДКП
  •  Передача N наибольших коэффициентов ДКП (с указанием их координат)
  •  Модификация предыдущих способов, включая сжатие по Хаффману (используя таблицу из 16-32 кодовых слов). Представляет интерес при больших степенях сжатия
  •  Передача коэффициентов (кроме, быть может, верхнего левого) по битовым плоскостям, ограничиваясь передачей заданного количества бит или битовых плоскостей


Формирование макроблока из 8 строк

Сжатие блока при заданном γ

азмер сжатого макроблока <0,9 от номинального

Размер сжатого макроблока >0,9, но <1,1 от номинального

Размер сжатого макроблока >1,1 от номинального

γ = γ / 1,3

γ = γ * 1,3

Буфер заполнен больше, чем на 50%

Буфер заполнен меньше, чем на 50%

γ = γ * 1,3

Передача макроблока

  •  

 

А также другие работы, которые могут Вас заинтересовать

69755. Шукання елемента списку 22.5 KB
  Алгоритм шукання елемента в списку аналогічний до шукання в динамічному рядку. Тому для списку теж складемо логічну функцію, побічним ефектом якої є інформація про першу за порядком ланку, яка містить шуканий елемент.
69756. Поняття про графи і дерева 39 KB
  Графом називають скінченну множину точок - вершин графа, для деяких пар якої налагоджені зв’язки - ребра графа. Розглянемо використання графів для зображення динамічних структур. Нехай є деяка структура, що складається з записів, пов’язаних між собою системою вказівок...
69757. Особливості використання динамічних змінних 26.5 KB
  3 доступ до динамічних змінних відбувається за допомогою змінних з вказівником. Множина операцій над змінними з вказівником визначена типом цих динамічних змінних. Зрозуміло що для реалізації цього алгоритму можна було б не використовувати вказівних змінних і динамічних структур...
69758. Технології передавання повідомлень 38 KB
  Сокет це абстрактна кінцева точка з’єднання через яку процес може відсилати або отримувати повідомлення. Під час обміну даними із використанням сокетів зазвичай застосовується технологія клієнтсервер коли один процес сервер очікує з’єднання а інший клієнт з’єднують із ним.
69759. Сторінково-сегментна організація пам’яті 52 KB
  Оскільки сегменти мають змінну довжину і керувати ними складніше, чиста сегментація зазвичай не настільки ефективна, як сторінкова організація. З іншого боку, видається цінною сама можливість використати сегменти як блоки пам’яті різного призначення змінної довжини.
69760. Атрибути файлів. Операції над файлами і каталогами 34.5 KB
  Кожний файл має набір характеристик - атрибутів. Набір атрибутів змінюється залежно від файлової системи. Найпоширеніші атрибути файла наведено нижче. Ім’я файла, докладно розглянуте раніше. Тип файла, який звичайно задають для спеціальних файлів (каталогів, зв’язків тощо).
69761. Продуктивність файлових систем 87 KB
  Оптимізація продуктивності під час розробки файлових систем Розглянемо яким чином можна оптимізувати продуктивність файлової системи зміною структур даних і алгоритмів які в ній застосовують. У викладі використовуватимемо класичний приклад оптимізації традиційної...
69762. Введення-виведення у режимі користувача 63 KB
  Тут зупинимося на взаємодії підсистеми введення-виведення із процесами режиму користувача та на різних методах організації введення-виведення з режиму користувача. Синхронне введення-виведення У більшості випадків введення-виведення на рівні апаратного...
69763. Таймери і системний час 27.5 KB
  Таймери керують пристроями які передають у систему інформацію про час. Вони відстежують поточний час доби здійснюють облік витрат процесорного часу повідомляють процеси про події що відбуваються через певний проміжок часу тощо.