10445

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

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

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

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

Русский

2013-03-26

109 KB

61 чел.

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

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

  •  

 

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

16466. МЕЖДУНАРОДНОЕ ГУМАНИТАРНОЕ ПРАВО 93 KB
  Лекция № 9. МЕЖДУНАРОДНОЕ ГУМАНИТАРНОЕ ПРАВО. 1. Понятие и источники международного гуманитарного права. 2. Права человека: понятие классификация и стандарты в международном праве. 3. Система межгосударственного сотрудничества в области прав человека. 1. Нормы ме...
16467. МЕЖДУНАРОДНАЯ ОТВЕТСТВЕННОСТЬ И МЕЖДУНАРОДНОЕ УГОЛОВНОЕ ПРАВО 72 KB
  Лекция № 10. МЕЖДУНАРОДНАЯ ОТВЕТСТВЕННОСТЬ И МЕЖДУНАРОДНОЕ УГОЛОВНОЕ ПРАВО. 1. Ответственность в международном праве. 2. Понятие особенности и правовая природа международного сотрудничества в борьбе с преступностью. 3. Преступления имеющие международный уголовный...
16468. Важнейшие подотрасли международного публичного права 44 KB
  Лекция. Важнейшие подотрасли международного публичного права. 1. Международное морское право. 2. Международное воздушное право. 3. Международное космическое право. 1. Международное морское право совокупность норм международного права регулирующих отношения ме...
16469. Муниципальное право 995 KB
  Глава 1 МУНИЦИПАЛЬНОЕ ПРАВО КОМПЛЕКСНАЯ ОТРАСЛЬ ПРАВА Понятие €œмуниципальное право€ новое для нашего государствоведения хотя вопросы муниципального управления муниципального хозяйства в свое время являлись предметом исследования юристов и деятелей земского...
16470. Основи конституційного ладу України 378 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО основи конституційного ЛАДУ УКРАЇНИ Київ Ін Юре 1997 ББК 67.94УКР300 1143 Погорілко В. Ф. П43Основи конституційного ладу України. К.: Ін Юре 1997. 40
16471. Права та свободи людини і громадянина в Україні 494 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО В. Ф. ПОГОРІЛКО В. В. ГОЛОВЧЕНКО М. І. СІРИЙ ПРАВА ТА СВОБОДИ ЛЮДИНИ І ГРОМАДЯНИНА В УКРАЇНІ Київ Ін Юре 1997 ББК 67.94УКР300 П43 Погорілко В. Ф. Головчен...
16472. Президент України 276.5 KB
  У брошурі розглядаються питання запровадження в Україні інституту президентства, аналізується конституційний статус Президента як глави держави, висвітлюється порядок його обрання і вступу на посаду. Особлива увага приділяється розгляду конституційних повноважень Президента, його відносини з іншими інститутами державної влади, роль у забезпеченні державного суверенітету України, прав та свобод людини і громадянина.
16473. Верховна Рада України 403.5 KB
  НАЦІОНАЛЬНА АКАДЕМІЯ НАУК УКРАЇНИ ІНСТИТУТ ДЕРЖАВИ І ПРАВА ім. В. М. КОРЕЦЬКОГО Л. Т. КРИВЕНКО ВЕРХОВНА РАДА УКРАЇНИ Київ Ін Юре 1997 ББК 67.94УКР300.6 К82 Кривенко Л. Т. К82Верховна рада України. К.: 1н Юре 1997. 47 с Бчка Нова Конституція Украї
16474. Органи виконавчої влади в Україні 419.5 KB
  У брошурі висвітлюються питання змісту, організації та правового регулювання виконавчої влади в Україні. Розглядаються побудова та функціонування системи органів виконавчої влади, характеризуються правовий статус і структура її окремих ланок, а також ключові напрями здійснення адміністративної реформи