10445

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

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

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

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

Русский

2013-03-26

109 KB

57 чел.

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

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

  •  

 

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

82761. Развитие прокуратуры в переходный период. Упразднение прокуратуры СССР Постановлением Президиума ВС РСФСР от 28.12.1991 года 27.19 KB
  С распадом СССР в начале 90-х годов прошлого века органы военной прокуратуры как и вся страна переживали непростые времена: трудности в экономике резко осложнили финансирование вооружённые конфликты в различных регионах лавинообразный всплеск преступности многочисленные реорганизации вызвали...
82762. Расходы бюджетной системы 592 KB
  В современных условиях бюджетные кредиты предоставляются в основном в форме связанных кредитов иностранных государств зарубежных банков фирм и международных финансовых организаций. Таким образом сумма налога на имущество физических лиц в следующем финансовом году составит...
82763. Биологический возраст человека 41.42 KB
  Определение биологического возраста. Понятие биологического возраста возникло в результате осознания неравномерности развития зрелости и старения. Биологический возраст может опережать либо отставать от хронологического возраста.
82764. Білінгвізм як психолінгвістичний феномен 43.01 KB
  Двомовність привертає увагу лінгвістів, психологів, педагогів відповідно до динаміки когнітивних підходів до опису мовних явищ та мовленнєвих процесів. У вивченні й оволодінні іноземною мовою надзвичайно велику роль відіграють різноманітні нейро- та психолінгвістичні аспекти.
82765. Типическое и индивидуальное в образах Онегина и Ленского 38.77 KB
  Цели: Формировать у учащихся представление об эпохе, в которой жил и создавал свои произведения А.С. Пушкин; Раскрыть причину недуга времени - равнодушия, разочарования во всем; Воспитывать чувство прекрасного и уважение к русской культуре.
82766. Давление и сила давления 67.5 KB
  Как вы считаете какие задачи нам нужно решить что нужно узнать о давлении чтобы разгадать всю тайну Учащиеся называют что нужно узнать о давлении что такое давление чем оно характеризуется от чего зависит как его рассчитать где применяется.
82767. Царство Грибов. Плесневые грибы 40.08 KB
  Дидактическая цель: Создать условия для осознания и осмысления блока новой учебной информации средствами критического мышления. Тип урока: комбинированный( изучения нового материала и первичное закрепление); Методы обучения: частично – поисковый, репродуктивный...
82768. С любовью на все времена. Ко Дню 8 Марта 41 KB
  Без солнца не цветут цветы без любви нет счастья без женщин нет любви без матери нет ни поэта ни героя. Горький Ведущий что может быть на свете священнее имени матери Человек еще не сделавший ни одного шага по земле и только только начинающий лопотать неуверенно и старательно складывает...
82769. «Literary quiz». Внеклассное мероприятие для учащихся 9-ых классов 28.43 KB
  Выбор темы внеклассного мероприятия по английскому языку обусловлен ее актуальностью и местом в системе уроков английского языка. Время проведения мероприятия: 40 минут Место проведения: кабинет английского языка. Содержание и методика мероприятия: учащиеся делятся на две команды соответствующие...