10445

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

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

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

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

Русский

2013-03-26

109 KB

62 чел.

Реализация 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

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

  •  

 

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

17095. Функції введення/виведення printf(), scanf().Лінійні обчислювальні процеси 99.5 KB
  Лабораторна робота № 7 Тема: Функції введення/виведення printf scanf.Лінійні обчислювальні процеси Ціль роботи: Вивчити формати оголошень і роботу основних функцій уведення/виведення інформації. Навчитися складати прості програми з лінійним обчислювальним процесом. О...
17096. Розробка програм зі скалярними типами даних 90 KB
  Лабораторна робота № 8 Тема: Розробка програм зі скалярними типами даних Ціль роботи: Розглянути і вивчити скалярні типи даних С int char float і ін. і їхнє використання. Обладнання: ПКПО Borland C Теоретичні відомості У С перемінні повинні бути оголошені тобто їхній ...
17097. Склад програми циклічної структури з розгалуженням 60 KB
  Лабораторна робота № 9 Тема: Склад програми циклічної структури з розгалуженням. Мета: навчитися складати програми циклічної структури застосовуючи цикли з параметром; працювати в інтегрованому середовищі використовуючи структуру розгалуження. Обладнання: ПК. ...
17098. Розробка програм з циклічними обчислювальними процесами 127.5 KB
  Лабораторна робота № 10 Тема: Розробка програм з циклічними обчислювальними процесами Ціль роботи: Вивчити написання програм мовою С використовуючи ітераційні циклічні методи освоїти основні оператори що підтримують роботу з циклами for while do... while. Навчитися писа...
17099. Обчислювальний процес, що розгалужується, з різними логічними умовами: оператор if... else, умовна операція (?:), оператор switch, оператор break, оператор goto 107 KB
  Лабораторна робота № 11 Тема: Обчислювальний процес що розгалужується з різними логічними умовами: оператор if... else умовна операція : оператор switch оператор break оператор goto Ціль роботи: Вивчити реалізацію в мові ветвящихся обчислювальних процесів . Навчитися писат
17100. Операції С, їхні пріоритети і використання. Перетворення типів 155 KB
  Лабораторна робота № 12 Тема: Операції С їхні пріоритети і використання.Перетворення типів Ціль роботи: Вивчити основні логічні арифметичні й інші операції С навчитися правильно складати вираження С вивчити пріоритети операцій С навчитися використовувати перетвор...
17101. Складання програм циклічної структури 72.5 KB
  Лабораторна робота № 13 Тема: складання програм циклічної структури. Ціль: навчитися складати програми циклічної структури застосовуючи різні типи операторів циклу в інтегрованому середовищі. Обладнання: ПК. Хід роботи. 1.Правила техніки безпеки при роботі в к
17102. Складання програм циклічної структури. Цикли з відомою та невідомою кількістю Повторів 105 KB
  Лабораторна робота № 14 Тема: склад програм циклічної структури. Цикли з відомою та невідомою кількістю Повторів. Мета: навчитися складати циклічні програми різних типів: з відомою та невідомою кількістю повторів. Обладнання: ПК. Хід роботи. Правила техніки
17103. Вкладені цикли. Упорядкування елементів масиву 49.5 KB
  Лабораторна робота № 15 Тема: Вкладені цикли. Упорядкування елементів масиву. Мета: навчитися складати програми упорядкування масивів Обладнання: ПК інструкция до практичної роботи. Обладнання:ПК Хід роботи Правила техніки безпеки в класі комп'ютерної технік