close

Вход

Забыли?

вход по аккаунту

?

Описание работы

код для вставкиСкачать
МИНИСТЕРСТВО РОССИЙСКОЙ ФЕДЕРАЦИИ
ПО СВЯЗИ И ИНФОРМАТИЗАЦИИ
Московский технический университет связи и информатизации
Кафедра Мультимедийных Сетей и Услуг Связи
Лабораторная работа №
Эффективное кодирование и цифровое представление изображений
Москва 2010
_____________________________
Лабораторная работа №
Эффективное кодирование и цифровое представление изображений
Составители:А.В. Гузеев, старший преподаватель
В.В. Морозов, ассистент
Разработчик программного обеспечения: А.В. Гузеев
______________________________________________
______________________________________________
______________________________________________
Рецензент:_____________________________________
Цель работы
1. Изучение основ цифрового представления полутоновых и бинарных изображений;
2. Изучение алгоритма построения эффективных кодов Хаффмана по длинам кодов, использующегося в современных стандартах кодирования изображений (T.81,T.800);
3. Изучение методов оценки эффективности алгоритмов сжатия;
4. Исследование упрощенного алгоритма эффективного кодирования полутоновых и бинарных изображений.
Домашнее задание
1. Изучить алгоритм построения кодов Хаффмана по длинам кодов;
2. Найти длины кодов для всех символов алфавита генерируемого источником, который содержит, последовательно записанные через пробел, Ваши фамилию, имя и отчество;
3. Построить список счетчиков длин кодов;
4. Сформировать кодовые комбинации по изученному алгоритму для найденного списка длин кодов;
5. Определить значение средней длины кодовой комбинации , энтропии и максимальной энтропии ;
6. Определить значения коэффициентов относительной эффективности и сжатия ;
7. Закодировать свои фамилию, имя и отчество, записанные через пробел, сформированными кодовыми последовательностями. Объяснить использование свойства префиксности при декодировании полученной кодовой последовательности.
Краткая теория
Цифровое представление изображений
Все цифровые изображения можно разбить на два больших класса: векторные цифровые изображения и растровые цифровые изображения. Для векторного представления изображения характерно разбиение графического образа, содержащегося в этом изображении, на графические примитивы (линии, окружности, эллипсы, многоугольники и т.д.). Графические примитивы задаются координатой некоторой точки, принадлежащей этому примитиву и характеризующей его положение на плоскости изображения, и параметрами графического примитива, характеризующими его форму, размер и ориентацию (например, для квадрата это может быть координата любого угла, размер стороны и угол поворота). По этой причине, при сильном увеличении изображения при просмотре, векторные изображения остаются предельно четкими.
Для растровых цифровых изображений последнее утверждение не справедливо. Если у векторных изображений задаются параметры для каждого графического примитива, то у растровых изображений задаются параметры для каждой точки на плоскости изображения. Такая точка называется единичный элемент изображения или пиксель (от английского picture element). На первый взгляд, кажется, что задать каждую точку на изображении это гораздо более сложная задача, чем задание графических примитивов, но это совсем не так. Во-первых, графические примитивы отличаются большим разнообразием видов и различным количеством параметров для каждого вида, что вызывает определенные трудности для их описания некоторым двоичным кодом (т.е. для представления в цифровой форме). Во-вторых, разбить изображение на совокупность графических примитивов - далеко не тривиальная задача, поэтому область применения векторной графики сильно ограничена, в основном это искусственно созданные изображения (например, деловая графика). Изображения реального мира (фотографии и др.) являются растровыми. Конечно, можно нарисовать лицо человека в виде эллипса с глазами - кругами внутри и ртом - линией, но это будет очень грубое приближение. Растровое изображение дает настолько точное приближение, что человек может не заметить разницы, если не будет специально искать её. Растровые изображения получаются в результате процесса АЦП (аналого-цифровое преобразование). Сначала оригинал сканируется или фотографируется, количество светочувствительных датчиков в устройстве определяет разрешающую способность системы (измеряется в dpi, dot-per-inch или в точках на дюйм), на этом этапе происходит дискретизация образа оригинала. Затем происходит квантование каждой точки-отсчета; количество уровней квантования зависит от характеристик и назначения системы; остановимся на 3 основных вариантах: 2 уровня, 256 уровней и 16777216 уровней. Так как каждая точка изображения может принимать значение одного из возможных уровней квантования, то для возможности отличать один уровень от другого, соответственно, будем иметь 1 бит, 8 бит или 24 двоичных разряда (бита) на точку. Эта величина называется глубиной цветопередачи изображения и, в зависимости от её значения, будем различать черно-белые, полутоновые и цветные растровые изображения соответственно.
Итак, для черно-белых изображений, каждая точка кодируется одним битом, который может принимать значение "0", если точка белая и значение "1", если точка черная.
Для полутоновых изображений, каждая точка может принимать одно из 256 различных значений, которым соответствуют оттенки серого цвета (полутона или уровни) от полностью черного (значение "0"), до полностью белого (значение "255"). Так, как каждая точка полутонового изображения кодируется 8 битами, а каждая точка черно-белого изображения - 1 битом, то можно представить полутоновое изображение совокупностью восьми черно-белых изображений, которые будут называться плоскостями. Чем меньше номер плоскости, тем старше биты полутонового изображения, которые она представляет. Если изменить значение пиксела на плоскости с номером 1, то значение пиксела полутонового изображения изменится на 128 полутонов, если изменить значение пиксела на плоскости с номером 2, то на 64 полутона и т.д. Изменение одного пиксела на 8 плоскости поменяет значение пиксела полутонового изображения только на 1 полутон, иными словами на соседний. Однако для человеческого глаза такое различие является крайне не существенным. Убедится в этом, можно, проведя несложный эксперимент в любом современном графическом редакторе.
Наконец, цветные изображения кодируются 24 битами на пиксел, однако это значение нельзя воспринимать как номер одного из 16777216 различных уровней. Это значение разделяется на 3 подряд записанных числа, на каждое из которых отводится по 8 бит. Первое число кодирует красную компоненту (Red), второе - зелёную (Green) и третье - синюю (Blue), это, так называемая, RGB модель представления цветов, когда любой цвет можно представить тремя перечисленными цветами, "смешанными" в нужной пропорции. Существуют и другие модели представления цветов, а также формулы пересчета значений для перехода из одной модели в другую. Таким образом, цветное изображение в модели представления цветов RGB, состоит из трех цветовых плоскостей, каждая из которых кодируется как полутоновое изображение, т.е. по 8 бит на один пиксель.
В настоящей лабораторной работе используется разложение полутонового изображения на 8 черно-белых плоскостей, которые, затем, сжимаются отдельно друг от друга. Исследуются зависимости коэффициента сжатия и энтропии от характера черно-белого изображения. Кодирование алгоритмом Хаффмана
Эффективное кодирование или сжатие имеет своей целью компактное представление информации для её дальнейшего хранения или передачи. Одним из классов эффективных кодов являются статистические коды, к этому классу относятся и коды Хаффмана. Согласно теореме Шеннона о кодировании для канала без помех скорость передачи информации будет увеличиваться, если преобразовать сообщения от источника информации в статистически независимые, т.е. в символы с равномерной функцией распределения вероятности появления. Статистическое кодирование осуществляет такое преобразование посредством уменьшения числа символов необходимых для представления одного элемента алфавита. Для решения этой задачи алгоритм Хаффмана сопоставляет наиболее вероятным сообщениям кодовые последовательности меньшей длины, а наименее вероятным - большей длины. Входными данными для кодирования по алгоритму Хаффмана являются вероятности появления символов алфавита на выходе источника и последовательность символов, которую необходимо закодировать. Для декодирования необходимы вероятности появления (те же самые), сопоставленные соответствующим символам алфавита источника (для построения кодов) и закодированная последовательность символов. Таким образом, будем говорить о полезной нагрузке и о служебной информации необходимой для верного декодирования. Эта информация может быть как кодовым деревом, так и информацией для построения такого дерева, например, частоты или вероятности появления символов кодируемого алфавита. Хотя древовидная структура облегчает понимание принципов кодирования Хаффмана, это не самый простой путь получения кодов Хаффмана. Другой метод состоит в генерировании для всех символов кодируемого алфавита длин кодов (code length) и формировании на их основе кодов Хаффмана. Длины кодов будут занимать меньший объем, чем вероятности появления символов и тем более чем структура кодового дерева.
Для пояснения алгоритма получения кодов Хаффмана при помощи длин кодов, в качестве примера, воспользуемся следующим палиндромом:
A MAN A PLAN A CANAL PANAMA
Палиндром состоит из восьми различных символов с частотами появления, приведенными в Таблице 1.
Таблица 1
Частоты появления символов в палиндроме
ЗначениеЧастотаA10C1L2M2N4P2Пробел6. (точка)1
В этом алгоритме используются символы, связанные с длинами кодов и списки значений со связанными с ними частотами. Первоначально кодируемому значению присваивается длина кода равная 0, и каждое значение помещается в отдельный список, которому назначается частота, равная частоте кодируемого значения из этого списка. Для рассматриваемого палиндрома данный алгоритм образует структуру, показанную на рисунке 1.
Рис. 1 Первый этап генерирования длин кодов Хаффмана
Для получения длин кодов соединим два списка с самыми низкими частотами. При объединении двух списков частота нового списка равна сумме частот двух прежних списков. Каждый раз, при присоединении списка, частота каждого символа в списке увеличивается на единицу, а новый список перемещается на последнее место (записывается нижней строкой). Процесс повторяется до тех пор, пока не получится один список кодов. При наличии нескольких списков с наименьшей частотой, из них всегда выбирается тот список, который расположен ближе всех к концу.
Наименьшие частоты принадлежат спискам с точкой и буквой С, поэтому объединяем эти списки и увеличиваем на единицу длины кодов для двух символов (Рис.2 а).
В результате получаются четыре списка с наименьшей частотой равной 2. Выбираем два списка, ближайших к низу, и объединяем их(Рис.2 б).
Повторяя описанную выше процедуру, получаем структуры, показанные на рисунке 2 в-ж.
Рис.2 Генерирование длин кодов Хаффмана
Если отсортировать символы по длине кода, получим длины кодов, приведенные в Таблице 2. Используя алгоритм, блок-схема которого показана на рисунке 3, можно сгенерировать из отсортированного списка коды Хаффмана. Входными данными будет массив длин кодов Хаффмана, подобных тем, что приведены в Таблице 1, а выходными массив кодов Хаффмана, сгенерированных для длин кодов.
Таблица 2
Символы палиндрома, отсортированные по длине кода
СимволКод длиныA1Пробел3N3L4M4P4C5. (точка)5
Для того, что бы алгоритм корректно завершил свою работу к массиву длин кодов нужно добавить нулевую длину на последнюю позицию. Поэтому в примере работы данного алгоритма, рассмотренном ниже, входной массив будет содержать 9 позиций, а не 8.
Рис.3 Блок-схема алгоритма генерирования кодов Хаффмана по длинам кодов
На рисунке 3 приняты следующие обозначения:
MD - массив длин кодов
MK - массив кодов Хаффмана
с - текущий ход Хаффмана
s - текущая длина кода Хаффмана
k - индекс массива длин
== - равно
!= - неравно
= присвоить
← - увеличить массив на один элемент справа и добавить на это место указанное значение
++ - увеличить на единицу
<<= - сдвинуть значение влево на указанную величину с добавлением нулей справа.
Далее рассмотрим пример построения кодов Хаффмана по длинам с использованием алгоритма, представленного на рисунке 3. Входные данные: MD[9]={1,3,3,4,4,4,5,5,0}; MK[0]={};
1. c=0;s=1;k=0;
2. MD[0]==1 → MK={0};c=1;k=1;
3. MD[1]!=1
4. MD[1]!=0
5. c=10;s=2;
6. MD[1]!=2 → c=100;s=3;
7. MD[1]==3
8. MD[1]==3 → MK={0,100};c=101;k=2;
9. MD[2]==3 → MK={0,100,101};c=110;k=3;
10. MD[3]!=3
11. MD[3]!=0
12. c=1100;s=4;
13. MD[3]==4 14. MD[3]==4 → MK={0,100,101,1100};c=1101;k=4;
15. MD[4]==4 → MK={0,100,101,1100,1101};c=1110;k=5;
16. MD[5]==4 → MK={0,100,101,1100,1101,1110};c=1111;k=6;
17. MD[6]!=4
18. MD[6]!=0
19. c=11110;s=5;
20. MD[6]==5 21. MD[6]==5 → MK={0,100,101,1100,1101,1110,11110};c=11111;k=7;
22. MD[7]==5 → MK={0,100,101,1100,1101,1110,11110,11111};c=100000;k=8;
23. MD[8]!=5
24. MD[8]==0 → конец
Выходные данные: MK={0,100,101,1100,1101,1110,11110,11111};
Таким образом, служебная информация это список символов кодируемого алфавита плюс список длин кодов. Однако на декодер можно передавать не сам список длин, а список счетчиков длин, т.е. список количества появлений каждой длины от длины равной 1 до максимальной длины. Построим список счетчиков длин для нашего примера (Таблица 3):
Таблица 3
Пример построения списка счетчика длин
Код длины13344455
Список счетчиков длинДлинаСчетчик1120324352
Вместо частот появления символов можно использовать вероятности появления. Если заданы только частоты появления, то, зная суммарное количество символов в кодируемой последовательности можно перейти к вероятностям, разделив частоту появления каждого символа на общее количество.
Приведенный алгоритм, так же как и классический алгоритм Хаффмана позволяет построить совокупность кодовых комбинаций различной длины обладающих свойством преффиксности, которое гласит: никакая кодовая комбинация не может являться началом другой более длинной кодовой комбинации.
Если говорить о кодировании алгоритмом Хаффмана применительно к черно-белым изображениям, то возникает вопрос, каким образом выбирать алфавит источника-изображения. Так, как пиксель может принимать только два значения, то при выборе в качестве элемента алфавита пикселя, алгоритм Хаффмана построит две кодовые комбинации: "0" и "1". Как не сложно заметить, никакого сжатия в этом случае не будет. Для преодоления этой сложности будем объединять соседние пиксели в квадратные блоки, так, чтобы соседние блоки соприкасались сторонами, и вся плоскость изображения была ими покрыта. Для определённости, в данной лабораторной работе будем использовать квадратные блоки со стороной в 3 пикселя. Тогда, в качестве символа алфавита источника будет выступать уже блок. Максимальное количество различных символов в таком алфавите будет равно 512 (каждый блок со стороной 3 пикселя содержит 9 пикселей внутри, а число различных комбинаций, притом, что каждый пиксель принимает два значения, это 2 в степени 9), такой прием называется укрупнением алфавита.
Оценка эффективности кодирования
Основная теорема о кодировании сообщений заданного алфавита гласит, что такие сообщения всегда можно закодировать префиксными последовательностями так, что среднее значение длины кодовой комбинации будет удовлетворять неравенству:. Таким образом, Н битов информации нельзя представить в виде набора нулей и единиц длиной менее Н знаков, но можно сколь угодно близко подойти к этой границе. Для оценки эффективности неравномерных кодов используется коэффициент относительной эффективности , где это энтропия источника с алфавитом, имеющим объем N знаков, равная среднему количеству информации, приходящемуся на один знак на выходе источника и измеряющаяся в битах. Здесь - вероятность появления i-го символа из N различных символов алфавита источника, а средняя длина кодовой комбинации. Отношение среднего числа двоичных символов, приходящихся на один знак алфавита, при кодировании заданного источника неравномерным кодом к длине кодовой комбинации в случае кодирования источника равномерным кодом называется коэффициентом сжатия . Однако коды Хаффмана для своего декодирования используют некоторую служебную информацию, поэтому, рассчитывая коэффициент сжатия, необходимо учитывать это. Следующая формула иллюстрирует сказанное: , где - объем служебной информации; - объем полезной информации; V - объем исходных данных.
В качестве равномерного кода для цифрового представления текстовой информации используются коды ASCII. Таблицы кодов символов ASCII содержат десятичные и шестнадцатеричные представления расширенного ASCII (American Standards Committee for Information Interchange) набора символов. Расширенный набор ASCII символов включает в себя набор символов ASCII и 128 других символов, для представления графики и рисования линий, часто называемых набором символов IBM. Кроме того, существуют расширения кодов ASCII для представления символов национальных алфавитов, называемые кодовыми страницами или кодировками. Для русского языка существует две кодовые страницы с номерами 866 (DOS кодировка) и 1251 (Windows кодировка). Все названные таблицы приведены в приложении. Для представления каждого символа ASCII кодом необходимо 8 бит, т.е. длина кодовой комбинации в этом случае равна 8.
Для вычисления объема занимаемого служебной информацией при кодировании черно-белых изображений алгоритмом Хаффмана с использованием длин серий будем исходить из следующих соображений.
Кодирование изображения представленного совокупностью блоков размера w * h осуществляется сопоставлением каждому типу блока кодовой комбинации кода Хаффмана. Код Хаффмана построен для распределения вероятностей типов блоков встречающихся в кодируемом изображении. На рисунке 4 схематично показана структура файла для хранения изображения сжатого этим методом:
Рисунок 4 - Структура заголовка файла HFI
В верхней части рисунка указаны номера байтов начиная с 0. Для каждого байта номер поставлен в его начале и в конце. Первые 3 байта используются для кодирования формата файла (каждый байт содержит символ в ASCII коде), в данном случае это символы hfi. Следующие два поля содержат ширину и высоту кодируемого изображения, каждое поле занимает два байта, т.о. максимальная высота\ширина равняется пикселей. Затем два поля по одному байту для ширины и высоты блока (т.е. максимальное значение этих полей 255). Для декодирования изображения необходимо знать соответствие типа блока и кода Хаффмана, для этого предназначены поля список блоков и список счетчиков длин. Т.к. указанные поля имеют переменную величину, то необходимо сохранять размер для каждого из них - поля размер списка блоков и размер списка счетчиков длин соответственно. Кроме того, размер блоков в списке может быть не кратен восьми, поэтому может присутствовать дополнительное поле в конце списка блоков для выравнивания на границу байта. Максимальный размер этого поля семь бит. Полезная нагрузка также выравнивается на границу байта.
Итак, служебная информация будет рассчитываться по следующей формуле:
, байт.
Здесь - длина списка счетчиков, - мощность алфавита источника, скобки обозначают округление до целого в большую сторону после деления.
Объем полезной нагрузки буде вычисляться как:
, байт.
Здесь -средняя длина кодовой комбинации, а - суммарное количество появлений всех элементов алфавита источника на его выходе.
Лабораторное задание
1. На вкладке "Домашнее задание" введите свою фамилию имя и отчество, записанные с заглавной буквы, через пробел и на русском языке, в верхнее поле. Во второе поле сверху введите список счетчиков длин кодов, разделяя числа запятыми. Поставьте переключатель в положение "ПРОВЕРИТЬ домашнее задание" и нажмите кнопку "Выполнить выбранное действие". Если домашнее задание выполнено правильно, то внизу экрана появится соответствующая надпись. Выполнение лабораторного задания возможно, только в случае правильно выполненного домашнего задания. Если перевести переключатель в положение "ПРОПУСТИТЬ домашнее задание" и затем нажать кнопку "Выполнить выбранное действие", то будет доступен тестовый режим. В тестовом режиме есть возможность использовать для измерений любое полутоновое изображение, однако тестовый набор изображений для выполнения лабораторного задания будет недоступен.
2. Перейдите на вторую вкладку "Лабораторное задание". В области "Выбор изображения" используйте поле с выпадающим списком для выбора источника информации. Вам доступно три тестовых полутоновых изображения: "Лена", "Барбара" и "Золотой холм" (эти изображения используются инженерами и исследователями по всему миру для тестирования алгоритмов сжатия). После выбора одного из изображений оно будет разложено на восемь черно-белых плоскостей. Из-за ограниченного размера экрана и соображений удобства, одновременно будет видна только одна плоскость. Для определения номера видимой плоскости и переключения между плоскостями нужно использовать группу элементов управления "Выбор плоскости". Сразу после выбора источника информации или после выбора другой плоскости, в области "Анализ плоскости" будет показана соответствующая плоскость, её представление в виде совокупности блоков размером 3х3 (таблица чуть ниже). В текстовое поле под таблицей будут выведены: количество различных типов блоков в плоскости , средняя длинна кода Хаффмана , суммарное количество блоков в плоскости , длина списка счетчиков , исходный размер плоскости и энтропия плоскости .
3. Запишите выведенные значения для выбранной плоскости в таблицу 4.
Таблица 4
Название изображения№ плоскостиMNCHКсжКоэ12345678
4. Для записанных величин рассчитайте объем служебной информации и полезной нагрузки .
5. Рассчитайте коэффициенты сжатия и относительной эффективности.
6. Для второй плоскости каждого изображения запишите коды Хаффмана для первых пяти блоков, для этого используйте алгоритм на рисунке 3. Соответствующие позиции отмечены красным цветом в таблице в лабораторной работе. Есть возможность проверить правильность выполнения этого задания, заполнив пустые поля и нажав на кнопку , находящуюся справа от таблицы. В случае успеха красные поля окрасятся в зеленый цвет.
7. Выберите следующую плоскость и переходите к пункту 3, если все плоскости исследованы, выберите следующее изображение и переходите к пункту 3.
8. Постройте на одном графике зависимости Ксж от номера плоскости для всех изображений, а на другом зависимости Н от номера плоскости для всех изображений. Сделайте выводы по построенным графикам.
9. Рассчитайте коэффициенты сжатия для трех тестовых полутоновых изображений. Пронумеруйте полутоновые изображения в соответствии с полученной степенью сжатия, напишите выводы.
Контрольные вопросы
1. Принцип получения длин кодовых комбинаций для набора элементов алфавита источника и соответствующих вероятностей появления.
2. Алгоритм преобразования длин кодовых комбинаций в кодовые комбинации.
3. Процедура построения списка счетчиков длин из списка длин и обратная ей процедура.
4. Принцип декодирования последовательности префиксного кода.
5. Количественная оценка эффективности неравномерного кодирования.
6. Представление служебной информации для последующего хранения или передачи.
7. Отличия векторных цифровых изображений от растровых цифровых изображений.
8. Понятие глубины цветопередачи цифрового изображения.
9. Каким образом можно улучшить коэффициенты сжатия для, предлагаемого в настоящей лабораторной работе, алгоритма сжатия и способа хранения сжатой информации, если допустить сжатие с потерями и если не допускать сжатие с потерями?
10. Что такое укрупнение алфавита?
Содержание отчета
Отчет выполняется в отдельной тетради (использование листов А4 не допускается), аккуратным почерком, с использованием линейки и карандаша (допускается использование распечаток графиков, таблиц и т.д, с одним условием, что всё должно быть выполнено аккуратно) и должен содержать:
1. Титульный лист с названием и номером лабораторной работы, номером группы студента, фамилией именем и отчеством студента, фамилией именем и отчеством преподавателя;
2. Цель лабораторной работы;
3. Результаты выполнения домашнего задания (по этим записям Вы должны уметь объяснить, как получены те или иные величины, как построены кодовые комбинации или списки);
4. Формулы и результаты расчетов для величин пунктов 3, 4 и 5 лабораторного задания. А также 3 полностью заполненные таблицы (Таблица 4) для тестовых полутоновых изображений;
5. Пять первых кодовых комбинаций для второй плоскости каждого тестового изображения;
6. Два графика: для зависимостей коэффициента сжатия от номера плоскости и для зависимостей энтропии от номера плоскости;
7. Расчет коэффициентов сжатия для тестовых полутоновых изображений;
8. Выводы для пунктов 8 и 9 лабораторного задания.
Список рекомендуемой литературы
1. Д. Сэломон, Сжатие данных, изображений и звука // М.: Техносфера, 2004.
2. В.В. Панин. Основы теории информации: учебное пособие для вузов // М.: БИНОМ. Лаборатория знаний, 2007.
3. Information technology - Digital compression and coding Of continuous-tone still images - Requirements and guidelines // ITU-T Recommendation T.81, 1993.
4. JPEG 2000 image coding system \\ ITU-T Recommendation T.800, 2000.
Документ
Категория
Рефераты
Просмотров
189
Размер файла
476 Кб
Теги
лабораторная работа, описание, работы, лаба, лабораторная
1/--страниц
Пожаловаться на содержимое документа