3

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ УКРАИНЫ

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

К КУРСОВОЙ РАБОТЕ

на тему: «Сжатие изображений»

по курсу «Цифровая обработка сигналов»

2006

Содержание

Введение

1. ОБЗОР МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ

1.1 Общие понятия, связанные с изображениями

1.2 Требования к JPEG

1.3 Форматы графических файлов

1.3.1 Файлы BMP

1.3.2 Файлы PCX

1.3.3 Файлы JPEG

1.4 Сравнительная характеристика алгоритмов сжатия

2 ВЫБОР И ОБОСНОВАНИЕ ВЫБРАННОГО МЕТОДА

2.1 Обоснование выбора метода сжатия изображения

2.2 Алгоритм архивации графики JPEG

2.2.1 Дискретно-косинусное преобразование

2.2.2 Этап квантования

2.2.3 Этап вторичного сжатия

3 РАЗРАБОТКА ПРОГРАММНО-АППАРАТНЫХ МОДУЛЕЙ

3.1 Разработка программного модуля на языке MatLab

3.2 Разработка программно-аппаратного модуля на языке С++

4 АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

5 РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЯ

ПРИЛОЖЕНИЕ А. Текст программы на MatLab

Введение

В 1990 году была завершена большая часть технических работ по разработке основных стандартов цифровых систем мультимедиа. Это дает возможность создавать интегрированные цифровые архивы, что в свою очередь будет способствовать развитию средств записи и хранения видео и аудио массивов информации в дополнение к имеющейся текстовой информации. При этом еще большее распространение получат цветные факсы, сканеры, принтеры; еще большим станет их быстродействие. Возникает обширное поле деятельности практически для каждой отрасли научной деятельности, связанной так или иначе с компьютерами: связь, системы обработки данных реального времени, параллельная обработка, разработка микросхем, объектно-ориентированное программирование, микропрограммирование и т.д.

Следует отметить, что одним из наиболее важных и определяющих аспектов как для хранения, так и для передачи является сжатие исходной информации. Большинство пользователей компьютерами уже знакомы со сжатием текстовой информации, позволяющей экономить место на дисках. Для текста необходима компрессия без потерь (нешумовая), если, конечно в дальнейшем потребуется восстановление текста. Такое сжатие обычно позволяет сократить занимаемое место в соотношении 2 : 1.

С другой стороны компрессия с потерями (шумовая) позволяет достичь значительно большего коэффициента - 1000 : 1, однако она применяется только в случае, когда условием ставится только визуальное распознавание изображения.

1 ОБЗОР МЕТОДОВ СЖАТИЯ ИЗОБРАЖЕНИЙ

1.1 Общие понятия, связанные с изображениями

Оцифрованный кадр цветного ТВ-изображения содержит информацию объемом порядка в миллион байт, а снимок на 35-миллиметровой фотопленке - где-то в десять раз больше. Это обширное количество данных - серьезное препятствие перед непосредственным использованием без предварительного сжатия оцифрованного изображения. Современные технические средства позволяют сжимать исходные изображения от 10 до 50 раз без заметного ухудшения их визуального качества. Технология сжатия не существует сама по себе. Для широкого применения систем сжатия информации то ли в целях передачи, то ли в целях хранения изображений, на рынке, куда поступают изделия от многих изготовителей, должен существовать определенный стандарт, позволяющий устройствам разных фирм работать совместно. Существующие ныне рекомендации Международного Телефонного и Телеграфного Консультативного Комитета (CCITT), известные под названием метода Группы 3, определяют условия работы только с двух градационными изображениями. За последние несколько лет был разработан стандарт JPEG, определяющий правила сжатия много градационных как полутоновых, так и цветных неподвижных изображений. Это результат сотрудничества ССITT и ISO (Международная Организация по стандартизации).

Использование компрессии позволяет:

снизить стоимость систем хранения и передачи информации;

увеличить количество каналов связи при сохранении заданной скорости передачи;

хранить больший объем информации;

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

Методы сжатия изображений подразделяются на две большие группы:

в первой предполагается частично утраченная информация (сжатие изображений с потерями);

во второй - информация полная (сжатие без потерь).

В первом случае усеченная часть информации либо субъективно не будет заметна, либо, будучи замеченной, не окажет существенного влияния на восприятие информации в целом. Обычно такие методы применяются для передачи изображения и звука, исходя из особенностей нашего восприятия. Так, на движущемся объекте мы не замечаем мелких деталей, поэтому при сжатии видеозаписи быстродвижущихся предметов их можно не передавать и подробнее прорисовывать только на статичных картинах. Воспроизводя музыку, мы в момент звучания громкого инструмента не обращаем внимание на одновременно звучащий, но более тихий инструмент. Значит, при громком звучании можно не заботиться о качестве синхронных тихих звуков, а передавать их с высокой точностью лишь в моменты низкого уровня громкости. Методы сжатия с потерями позволяют достичь коэффициента десятикратного сжатия, но без значительного ухудшения качества изображения и звука. Наиболее известны сжатия с потерями в форматах JPEG для неподвижных изображений. Однако у десятикратного коэффициента сжатия есть оборотная сторона - это погрешности в записываемой информации.

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

1.2 Требования к JPEG

Визуально после сжатия изображение должно оцениваться как "отлично" или "хорошо" в сравнении с оригиналом; метод должен быть применим и удобен при практическом применении для любых многоградационных изображений; иметь невысокую расчетную сложность, что позволило бы избежать дополнительных аппаратных разработок и ограничиться лишь несложным программным обеспечением; JPEG должен иметь следующие режимы работы:

Последовательное кодирование: компоненты изображения кодируются слева направо, сверху вниз;

Прогрессивное кодирование: изображение кодируется при многократном сканировании, в случаях, когда время передачи велико;

Нешумовое кодирование: изображение кодируется с гарантией точного воспроизведения каждого элемента (даже, если это приводит к заметному снижению коэффициента сжатия);

Иерархическое кодирование: изображение разбивается и кодируется по многим уровням, причем нижние уровни могут быть доступны сразу и без предварительного декомпрессирования изображения на всех его уровнях.

1.3 Форматы графических файлов

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

Вызывает интерес та часть процесса, где происходит преобразование данных в растровый массив. Существует несколько форматов файлов растровой графики, и каждый формат предусматривает собственный способ кодирования информации о пикселах и другой присущей компьютерным изображениям информации. Именно поэтому программа Paint, поставляемая в комплекте ОС Windows 95, совместима с BMP-файлами, но не может считывать файлы формата GIF. Создатели программы Paint наделили ее способностью декодировать графическую информацию, хранящуюся в формате BMP, но не сможет прочитать формат GIF

Распространенные форматы файлов растровой графики:

Формат	Макс. число бит/пиксел	Макс. число цветов	Макс. размер изображения, пиксел	Методы сжатия	Кодирование нескольких изображений
BMP	24	16'777'216	65535 x 65535	RLE*	-
GIF	8	256	65'535 x 65535	LZW	+
JPEG	24	16'777'216	65535 x 65535	JPEG	-
PCX	24	16'777'216	65535 x 65535	RLE	-
PNG	48	281'474'976'710'656	2'147'483'647 x 2 147 483 647	Deflation (вариант LZ77)	-
TIFF	24	16'777'216	всего 4'294'967'295	LZW, RLE и другие*	+

1.3.1 Файлы BMP

Формат файла BMP (сокращенно от BitMaP) - это "родной" формат растровой графики для Windows, поскольку он наиболее близко соответствует внутреннему формату Windows, в котором эта система хранит свои растровые массивы. Для имени файла, представленного в BMP-формате, чаще всего используется расширение BMP, хотя некоторые файлы имеют расширение RLE, означающее run length encoding (кодирование длины серий). Расширение RLE имени файла обычно указывает на то, что произведено сжатие растровой информации файла одним из двух способов сжатия RLE, которые допустимы для файлов BMP-формата.

В файлах BMP информация о цвете каждого пиксела кодируется 1, 4, 8, 16 или 24 бит (бит/пиксел). Числом бит/пиксел, называемым также глубиной представления цвета, определяется максимальное число цветов в изображении. Изображение при глубине 1 бит/пиксел может иметь всего два цвета, а при глубине 24 бит/пиксел - более 16 млн. различных цветов.

Файл разбит на четыре основные раздела: заголовок файла растровой графики, информационный заголовок растрового массива, таблица цветов и собственно данные растрового массива. Заголовок файла растровой графики содержит информацию о файле, в том числе адрес, с которого начинается область данных растрового массива. В информационном заголовоке растрового массива содержатся сведения об изображении, хранящемся в файле, например, его высоте и ширине в пикселах. В таблице цветов представлены значения основных цветов RGB (красный, зеленый, синий) для используемых в изображении цветов. Программы, считывающие и отображающие BMP-файлы, в случае использования видеоадаптеров, которые не позволяют отображать более 256 цветов, для точной цветопередачи могут программно устанавливать такие значения RGB в цветовых палитрах адаптеров.

Формат собственно данных растрового массива в файле BMP зависит от числа бит, используемых для кодирования данных о цвете каждого пиксела. При 256-цветном изображении каждый пиксел в той части файла, где содержатся собственно данные растрового массива, описывается одним байтом (8 бит). Это описание пиксела не представляет значений цветов RGB, а служит указателем для входа в таблицу цветов файла. Таким образом, если в качестве первого значения цвета RGB в таблице цветов файла BMP хранится R/G/B=255/0/0, то значению пиксела 0 в растровом массиве будет поставлен в соответствие ярко-красный цвет. Значения пикселов хранятся в порядке их расположения слева направо, начиная (как правило) с нижней строки изображения. Таким образом, в 256-цветном BMP-файле первый байт данных растрового массива представляет собой индекс для цвета пиксела, находящегося в нижнем левом углу изображения; второй байт представляет индекс для цвета соседнего справа пиксела и т. д. Если число байт в каждой строке нечетно, то к каждой строке добавляется дополнительный байт, чтобы выровнять данные растрового массива по 16-бит границам.

Структура файла BMP:

1. Заголовок файла растровой графики (14 байт) Сигнатура файла BMP (2 байт) Размер файла (4 байт) Не используется (2 байт) Не используется (2 байт) Местонахождение данных растрового массива (4 байт)

2. Информационный заголовок растрового массива (40 байт) Длина этого заголовка (4 байт) Ширина изображения (4 байт) Высота изображения (4 байт) Число цветовых плоскостей (2 байт) Бит/пиксел (2 байт) Метод сжатия (4 байт) Длина растрового массива (4 байт) Горизонтальное разрешение (4 байт) Вертикальное разрешение (4 байт) Число цветов изображения (4 байт) Число основных цветов (4 байт)

3. Таблица цветов (длина изменяется от 8 до 1024 байт)

4. Собственно данные растрового массива (длина переменная)

1.3.2 Файлы PCX

PCX стал первым стандартным форматом графических файлов для хранения файлов растровой графики в компьютерах IBM PC. На этот формат, применявшийся в программе Paintbrush фирмы ZSoft, в начале 80-х гг. фирмой Microsoft была приобретена лицензия, и затем он распространялся вместе с изделиями Microsoft. В дальнейшем формат был преобразован в Windows Paintbrush и начал распространяться с Windows. Хотя область применения этого популярного формата сокращается, файлы формата PCX, которые легко узнать по расширению PCX, все еще широко распространены сегодня.

Файлы PCX разделены на следующие три части: заголовок PCX, данные растрового массива и факультативная таблица цветов. 128-байт заголовок PCX содержит несколько полей, в том числе поля размера изображения и числа бит для кодирования информации о цвете каждого пиксела. Информация растрового массива сжимается с использованием простого метода сжатия RLE; факультативная таблица цветов в конце файла содержит 256 значений цветов RGB, определяющих цвета изображения. Формат PCX первоначально был разработан для адаптеров CGA- и EGA-дисплеев и в дальнейшем был модифицирован для использования в адаптерах VGA и адаптерах истинных цветов. Кодирование цвета каждого пиксела в современных изображениях PCX может производиться с глубиной 1, 4, 8 или 24 бит.

1.3.3 Файлы JPEG

Формат файла JPEG (Joint Photographic Experts Group - Объединенная экспертная группа по фотографии, произносится "джейпег) был разработан компанией C-Cube Microsystems как эффективный метод хранения изображений с большой глубиной цвета, например, получаемых при сканировании фотографий с многочисленными едва уловимыми (а иногда и неуловимыми) оттенками цвета. Самое большое отличие формата JPEG от других рассмотренных здесь форматов состоит в том, что в JPEG используется алгоритм сжатия с потерями (а не алгоритм без потерь) информации. Алгоритм сжатия без потерь так сохраняет информацию об изображении, что распакованное изображение в точности соответствует оригиналу. При сжатии с потерями приносится в жертву часть информации об изображении, чтобы достичь большего коэффициента сжатия. Распакованное изображение JPEG редко соответствует оригиналу абсолютно точно, но очень часто эти различия столь незначительны, что их едва можно (если вообще можно) обнаружить.

Процесс сжатия изображения JPEG достаточно сложен и часто для достижения приемлемой производительности требует специальной аппаратуры. Вначале изображение разбивается на квадратные блоки со стороной размером 8 пиксел. Затем производится сжатие каждого блока отдельно за три шага. На первом шаге с помощью формулы дискретного косинусоидального преобразования фуры (DCT) производится преобразование блока 8х8 с информацией о пикселах в матрицу 8x8 амплитудных значений, отражающих различные частоты (скорости изменения цвета) в изображении. На втором шаге значения матрицы амплитуд делятся на значения матрицы квантования, которая смещена так, чтобы отфильтровать амплитуды, незначительно влияющие на общий вид изображения. На третьем и последнем шаге квантованная матрица амплитуд сжимается с использованием алгоритма сжатия без потерь.

Поскольку в квантованной матрице отсутствует значительная доля высокочастотной информации, имеющейся в исходной матрице, первая часто сжимается до половины своего первоначального размера или даже еще больше. Реальные фотографические изображения часто совсем невозможно сжать с помощью методов сжатия без потерь, поэтому 50%-ное сжатие следует признать достаточно хорошим. С другой стороны, применяя методы сжатия без потерь, можно сжимать некоторые изображения на 90%. Такие изображения плохо подходят для сжатия методом JPEG.

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

1.4 Сравнительная характеристика алгоритмов сжатия

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

Сейчас не редкость создание базы данных, хранящей изображения, активное использование изображений в программах. Критичность их размеров дает себя знать довольно быстро, поэтому резонно применить один или несколько алгоритмов сжатия. Возможно, идеальным решением будет воспользоваться парой-тройкой новых универсальных алгоритмов, а может быть, стоит разработать специальный. Для электронных фотографий из досье, отпечатков пальцев, рентгеновских снимков созданы специальные алгоритмы, обеспечивающие сжатие до 1000 раз. Если планируется создание большой многогигабайтной базы данных, содержащей однородную информацию, то уменьшение ее хотя бы в 10 раз - это уже серьезно.

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

2 ВЫБОР И ОБОСНОВАНИЕ ВЫБРАННОГО МЕТОДА

2.1 Обоснование выбора метода сжатия изображения

В данном курсовом проекте реализуется сжатие изображений на основе дискретного косинусного преобразования, (дискретное косинусное преобразование используется в широко распространенном стандарте сжатия изображений - JPEG). Рассмотрим сравнительную характеристику выше рассмотренных алгоритмов сжатия изображений (таблица 2.1).

Таблица 2.1

Алгоритм	Коэфф-ты сжатия	На что ориентирован	Потери
Групповое кодирование (RLE)	1/32 1/2 2/1	3,4 битные	Нет
LZW	1/100 1/4 7/5	1-8 битные	Нет
Хаффмана	1/8 2/3 1/1	1-битные	Нет
JBIG	1.5 раза	1-битные	Нет
Lossless JPEG	2 раза	24-битн.	Нет
Рекурс. сжатие (Wavelet)	2-20 раз	серые	Да
JPEG	2-200 раз	24-битн.	Да
Фрактальный	2-2000 раз	24-битн.	Да

При сохранении изображений, содержащих фотографии (изображения с 16 миллионами цветов (24 бита)), ни один формат не приведет к созданию файла меньшего размера, чем JPEG.

Это метод сжатия с потерей данных, который, жертвует качеством изображения для сохранения пространства на диске. Однако можно управлять тем, сколько данных потеряется во время операции сохранения. JPEG лучше всего использовать при сжатии изображений с непрерывным тоном (изображения, в которых цветовой контраст между ближайшими пикселями невелик). Любое изображение, которое включает постепенные цветовые переходы, как на фотографии, пригодно для JPEG-сжатия. JPEG - не самый лучший выбор для сохранения снимков экрана, векторных рисунков и других высококонтрастных изображений. Эти изображения лучше обрабатывать в формате TIFF с LZW-сжатием. Из таблицы видно, что большой коэффициент сжатия достигается при использование фрактального метода сжатия изображений, а остальные методы либо не дают достаточный коэффициент сжатия, либо ориентированы на меньшее количество бит. Сравним алгоритм архивации графики JPEG с фрактальной компрессией.

Во-первых, заметим, что и тот, и другой алгоритм оперируют 8-битными (в градациях серого) и 24-битными полноцветными изображениями. Оба являются алгоритмами сжатия с потерями и обеспечивают близкие коэффициенты архивации. И у фрактального алгоритма, и у JPEG существует возможность увеличить степень сжатия за счет увеличения потерь. Кроме того, оба алгоритма очень хорошо распараллеливаются.

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

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

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

2.2 Алгоритм архивации графики JPEG

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

Подготовка:

Нужно преобразовать изображение в вид яркость/цветность, можно использовать цветовую схему YCbCr (YUV), вот формулы перевода:

Y = 0.299*R + 0.578*G + 0.114*B

Cb = 0.1678*R - 0.3313*G + 0.5*B

Cr = 0.5*R - 0.4187*G + 0.0813*B

Y нужно сохранить без изменений, его можно сжать любым алгоритмом без потери данных.

2.2.1 Дискретное косинус преобразование

Основным этапом работы алгоритма является дискретное косинусное преобразование (ДКП), представляющее собой разновидность преобразования Фурье. Оно позволяет переходить от пространственного представления изображения к его спектральному представлению и обратно. Что нужно сделать на первом этапе первом этапе ? Следует создать ДКП матрицу, используя такую формулу :

DCT = 1/sqr(N), если i=0

DCT = sqr(2/N)*cos[(2j+1)*i*3.14/2N], если i > 0

N = 8, 0 < i < 7 , 0 < j < 7

в результате имеем (матрица ДКП):

|.353553 .353553 .353553 .353553 .353553 .353553 .353553 .353553|

|.490393 .415818 .277992 .097887 -.097106 -.277329 -.415375 -.490246|

|.461978 .191618 -.190882 -.461673 -.462282 -.192353 .190145 .461366|

|.414818 -.097106 -.490246 -.278653 .276667 .490710 .099448 -.414486|

|.353694 -.353131 -.354256 .352567 .354819 -.352001 -.355378 .351435|

|.277992 -.490246 .096324 .416700 -.414486 -.100228 .491013 -.274673|

|.191618 -.462282 .461366 -.189409 -.193822 .463187 -.460440 .187195|

|.097887 -.278653 .416700 -.490862 .489771 -.413593 .274008 -.092414|

например, нам нужно сжать следующий фрагмент изображения:

| 95 88 88 87 95 88 95 95|

|143 144 151 151 153 170 183 181|

|153 151 162 166 162 151 126 117|

IMG = |143 144 133 130 143 153 159 175|

|123 112 116 130 143 147 162 189|

|133 151 162 166 170 188 166 128|

|160 168 166 159 135 101 93 98|

|154 155 153 144 126 106 118 133|

|-33 -40 -40 -41 -33 -40 -33 -33|

| 15 16 23 23 25 42 55 53|

| 25 23 34 38 34 23 -2 -11|

IMG = | 15 16 5 2 15 25 31 47|

| -5 -16 -12 2 15 19 34 61|

| 5 23 34 38 42 60 38 0|

| 32 40 38 31 7 -27 -35 -30|

| 26 27 25 16 -2 -22 -10 5|

вот формула, по которой производится ДКП: RES*IMG*DCT

Для начала нужно посчитать промежуточную матрицу: TMP= IMG*DCT

|-103 -3 1 2 4 0 -1 5|

| 89 -40 12 -2 -7 5 1 0|

| 57 31 -30 6 2 0 5 0|

TMP = | 55 -28 24 1 0 -8 0 0|

| 32 -60 18 -1 14 0 -8 1|

| 84 -11 -37 17 -24 4 0 -4|

| 19 81 -16 -20 8 -3 4 0|

| 22 40 11 -22 8 0 -3 2|

затем умножаем ее на ДКП матрицу: RES = TMP*DCT

| 91 3 -5 -6 2 0 1|

|-38 -57 9 17 -2 2 2|

|-80 58 0 -18 4 3 4|

RES = |-52 -36 -11 13 -9 3 0|

|-86 -40 44 -7 17 -6 4|

|-62 64 -13 -1 3 -8 0|

|-16 14 -35 17 -11 2 -1|

|-53 32 -9 -8 22 0 2|

2.2.2 Этап Квантования

На этом этапе мы посчитаем матрицу квантования, используя этот псевдо код:

for i:=0 to 8 do

for j:=0 to 8 do

Q[i,j] = 1+((1+i+j)*q);

где q - это коэффициент качества, от него зависит степень потери качества сжатого изображения для q = 2 имеем матрицу квантования:

| 3 5 7 9 11 13 15 17|

| 5 7 9 11 13 15 17 19|

| 7 9 11 13 15 17 19 21|

Q = | 9 11 13 15 17 19 21 23|

|11 13 15 17 19 21 23 25|

|13 15 17 19 21 23 25 27|

|15 17 19 21 23 25 27 29|

|17 19 21 23 25 27 29 31|

теперь нужно каждое число в матрице квантования разделить на число в соответствующей позиции в матрице RES, в результате получим:

| 30 0 0 0 0 0 0 0|

| -7 8 1 1 0 0 0 0|

|-11 6 0 1 0 0 0 0|

A = | -5 -3 0 0 0 0 0 0|

| -7 -3 2 0 0 0 0 0|

| -4 4 0 0 0 0 0 0|

| -1 0 1 0 0 0 0 0|

| -3 1 0 0 0 0 0 0|

как вы видите здесь имеется довольно много нулей, мы получим наиболее длинную последовательность нулей, если будем использовать следующий алгоритм:

+----+----+----+----+----+----+----+----+

| 1 | 2 | 6 | 7 | 15 | 16 | 28 | 29 |

+----+----+----+----+----+----+----+----+

| 3 | 5 | 8 | 14 | 17 | 27 | 30 | 43 |

+----+----+----+----+----+----+----+----+

| 4 | 9 | 13 | 18 | 26 | 31 | 42 | 44 |

+----+----+----+----+----+----+----+----+

| 10 | 12 | 19 | 25 | 32 | 41 | 45 | 54 |

+----+----+----+----+----+----+----+----+

| 11 | 20 | 24 | 33 | 40 | 46 | 53 | 55 |

+----+----+----+----+----+----+----+----+

| 21 | 23 | 34 | 39 | 47 | 52 | 56 | 61 |

+----+----+----+----+----+----+----+----+

| 22 | 35 | 38 | 48 | 51 | 57 | 60 | 62 |

+----+----+----+----+----+----+----+----+

| 36 | 37 | 49 | 50 | 58 | 59 | 63 | 64 |

+----+----+----+----+----+----+----+----+

итак у нас получилась последовательность:

30 0 -7 -11 8 0 0 1 6 -5 -7 -3 0 1 0 0 0 1 0 -3 -4 -1 4 2 0 0 0 0

0 0 0 0 0 0 0 -3 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

2.2.3 Этап Вторичного Сжатия

Самым распространенным методом вторичного сжатия является метод Хаффмана и его разновидности.

Сжатие Хаффмана - статистический метод сжатия, который уменьшает среднюю длину кодового слова для символов алфавита. Код Хаффмана является примером кода, оптимального в случае, когда все вероятности появления символов в сообщении - целые отри- цательные степени двойки. Код Хаффмана может быть построен по следующему алгоритму:

1.Выписываем в ряд все символы алфавита в порядке возрастания или убывания вероятности их появления в тексте;

2.Последовательно объединяем два символа с наименьшими веро- ятностями появления в новый составной символ, вероятность появ- ления которого полагается равной сумме вероятностей составляю- щих его символов. В конце концов, мы построим дерево, каждый узел которого имеет суммарную вероятность всех узлов, находя- щихся ниже него;

3.Прослеживаем путь к каждому листу дерева помечая направление к каждому узлу (например, направо - 1, налево - 0).

Подведя итог над вышесказанным покажем обобщенную структуру компрессора и декомпрессора по стандарту JPEG:

Рисунок 2.2.1 - Компрессор и декомпрессор JPEG

3. РАЗРАБОТКА ПРОГРАММНО-АППАРАТНЫХ МОДУЛЕЙ

3.1 Разработка программного модуля на языке MatLab

Прежде, чем приступить к разработке программ по обработке изображений для цифровых сигнальных процессоров, необходимо выбрать и алгоритм обработки, провести их всесторонние исследования и определить оптимальные параметры процедур. Затем эти процедуры должны быть реализованы в виде программных модулей, написанных на языке С конкретного сигнального процессора. С практической точки зрения представляется наиболее целесообразным проводить выше указанные исследования в области обработки изображений с использованием системы MatLab, которая является удобным и достаточно простым инструментом исследования и, кроме того, в ее состав входит компилятор языка MatLab на язык С и библиотека математических функций на C++. Таким образок процедуры обработки изображений, написанные в системе МАТLАВ, без особых трудностей преобразуются в исполняемые модули для цифровых сигнальных процессоров семейств ТМS и АDSР. Для исследования методов обработки изображений в системе МАТLАВ 5.2 разработан пакет Image Processing Toolbox, включающий широкий набор функций, который мог быть дополнен путем написания пользователем собственных нетиповых функций.

Базовым типом данных в МАТLАВ является прямоугольная матрица упорядоченного множества действительных или комплексных элемент изображения. Поэтому доступ к произвольному пикселю изображения осуществляется как к элементу матрицы.

МАТLАВ 5.2 поддерживает четыре типа изображений:

1) цветное индексированное;

2) полутоновое яркостное;

3) бинарное изображение;

4) цветное RGB,

Для индексированного цветного изображения требуется наличие двух матриц, таблицы цветности и матрицы индексов. Таблица цветности (со1огтар) представляет собой набор используемых в изображении цветов, а матрица индексов - набор номеров (индексов) от 0 до п-1 соответствующих цветов таблицы цветности. Размер таблицы цветности зависит от количества N_ц используемых в изображении цветов и равен N_ц *3 , Каждому индексу таблицы соответствуют значения трех RGВ цветов. Для отображения каждого из этих цветов используются действительные числа с двойной точностью в диапазоне от 0,0 (уровень черного) до 1,0 (максимальная интенсивность).

В яркостном типе изображения используется только одна матрица, содержащая значения интенсивности q (уровней серого) каждого из пикселов. Значения интенсивности представляются реальными числами с двойной точностью в диапазоне от 0,0 до 1.0, где уровень 0,0 соответствует черному а 1,0 - белому цвету.

Инструментальные средства MATLAB позволяют обрабатывать изображения отдельными фрагментами (по терминологии MATLAB - блоками) с использованием оконных функций. Это позволяет снизить расход памяти компьютера и повысить скорость обработки. При этом нет необходимости программно задавать перемещения окна (блока) по изображению. Заданная функция автоматически выполняется для каждого фрагмента всего обрабатываемого изображения. Отдельные блоки поочередно покрывают матрицу изображения начиная с левого верхнего угла. Если блоки не укладываются в границах изображения, то недостающие пикселы автоматически заполняются нулями. Аналогичное заполнение нулями производится при обработке пикселов, расположенных на краях изображения.

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

img_rgb = imread('astrologer.bmp');

В составе MATIAB имеется широкий набор функций для различных преобразований изображений (Image transforms), в частности:

DCT2 и IDCT2 - вычисление двумерного прямого и обратного дискретно-косинусного преобразования соответственно;

FFT2 , FFTn, IFFT2 , IFFTn- прямое и обратное, двумерное и n-мерное быстрые преобразования Фурье;

rgb2ycbcr(in) - Стакндартная функция преобразования, изображения из RGB в YCbCr. В качестве параметра функции передается RGB-изображение, а на выходе - преобразованное изображение.

ycbcr2rgb(in) - функция MatLabа отвечает за преобразования, изображения из YCbCr в RGB. В качестве параметра функции передается YCbCr-изображение, а на выходе - преобразованное изображение.

Текст программы приведен в Приложении А.

3.2 Разработка программно-аппаратного модуля на языке С++

Язык программирования часто можно определить, просто взглянув на исходный текст программы. Так, программа на языке APL напоминает иероглифы, текст на языке ассемблера представляется столбцами мнемоник, язык Pascal выделяется своим читабельным синтаксисом. А что можно сказать о языке С? Многие программисты, впервые столкнувшиеся с ним, находят его слишком замысловатым и пугающим. Конструкции, напоминающие выражения на английском языке, которые характерны для многих языков программирования, в С встречаются довольно редко. Вместо этого программист сталкивается с необычного вида операторами и обилием указателей. Многие возможности языка уходят своими корнями к особенностям программирования на компьютерах, существовавших на момент его появления.

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

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

Язык С содержит все управляющие конструкции, характерные для современных языков программирования, в том числе инструкции for, if/else, switch/case,while и другие. На момент появления языка это было очень большим достижением.

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

Язык С поддерживает модульное программирование, суть которого состоит в возможности раздельной компиляции и компоновки отдельных частей программы.

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

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

Текст программы приведён в Приложении Б.

 Суть данной программы заключается в том, что входным файлом к программе является файл изображения в формате BMP от которого отделяется заголовок и данные о цвете переводятся из RGB представления в цветовую модель YCRCb, далее программа работает по стандартному алгоритму который описан выше. Результатом работы части программы которая отвечает за компрессию является текстовый файл в котором записано числовое представление сжатого изображения. Та часть программы которая отвечает за декомпрессию читает полученный на предыдущем этапе файл и перекодирует его обратно в BMP файл (это необходимо для того чтобы увидеть получившийся результат)

В качестве входных данных используется графический файл.

Выходные данные представлены изображение исходное и изображение сжатое.

4. АНАЛИЗ ВЫЧИСЛИТЕЛЬНОЙ СЛОЖНОСТИ

4.1 Требуемый объем памяти

При анализе вычислительной сложности необходимо руководствоваться объемом ОЗУ ЦПОС TMS320C6711. Так как параметры системы сжатия хранятся в виде констант, то нужно определить какой объем памяти необходим для размещения всех значений.

Для работы с одним изображением (возьмем средних размеров изображение) нам необходимо выделить память под:

Исходное, сжатое и промежуточное изображения;( 3 таблицы - R,G,B)

Три промежуточные матрицы размером 8х8 для работы с блоками изображения;

Таблицу квантов 8х8;

Таблица коэффициентов ДКП и транспонированная таблица.

Исходя из того, что размер каждой из таблиц 8*8, имеем:

Объем памяти = 3*3*(100*100)+3*(8*8)+8*8+2*8*8 = 90384 [слов]

Из расчетов видно, что для размещения параметров системы сжатия в памяти необходимо примерно 90384 слова, следовательно, на ЦПОС TMS320C6711 с установленными 16 Мбайт оперативной памяти, реализовать поставленную задачу представляется возможным.

4.2 Количество операций

Процесс сжатия включает в себя косинусное преобразование - вычисление трансформант, деление каждой трансформанты матрицы на соответствующий коэффициент квантования, округление результата, а затем умножение на этот же коэффициент. Фрагмент изображения, размером 8х8 получается путем разбиения входного сигнала на блоки и вычисление для каждого из них ДКП. Для вычисления одной трансформанты нам необходимо 64 раза осуществить 8 операций сложения и 8 операций умножения. В нашем случае получим:

N1_оп = 3*(64_транс*(8+8)+ 64_округл+64_делен) = 3456 [операций]

Для обратного процесса понадобиться такое же количество операций,

N2_оп = 3*(64_транс*(8+8)+ 64_округл+64_умнож) = 3456 [операций]

Таким образом, общее число операций, необходимых для сжатия и разжатия 1 блока изображения:

Количество операций = 3456*2 = 6912 [операции].

Данные расчеты показывают средние числа, как для необходимого объема ОЗУ, так и для количества операций в секунду выполняемых процессором при обработке 1 блока изображения.

5. РУКОВОДСТВО ПОЛЬЗОВАТЕЛЯ

Для работы с программой, разработанной на языке MATLAB необходимо:

1.Запустить программу jpeg.m в среде разработки MATLAB.

2.После выполнения данной программы на экране отображается исходное изображение и сжатое. Для представления возможности сравнить их, увидеть потерю качества.

1. Также вы можете улучшить/ухудшить качество сжатия, изменяя коэффициент сжатия непосредственно в программе.

Для работы с программой, разработанной на языке C++ необходимо:

1. Кодируемый файл изображения поместить в Папку “_kurs” и программа после запуска будет выполнятся в соответствии с «Описанием алгоритма работы программы» изложенным выше.

2. Варьируя коэффициентом сжатия вы можете пронаблюдать, как изменяется при этом качество восстанавливаемого изображения.

ЗАКЛЮЧЕНИЕ

В ходе выполнения курсового проекта была разработана система сжатия на основе дискретного косинусного преобразования. Так как наилучшим способом преобразования сигналов, обеспечивающим минимальную среднеквадратическую ошибку, является преобразование Карунена-Лоэва, но не имеющее алгоритма быстрого вычисления, то применялось именно ДКП, как наиболее близкое по эффективности к преобразованию К-Л.

Но степень сжатия изображений уступает сжатию стандартным jpeg-кодером. Это обуславливается тем, что разработанный в данной курсовой работе компрессор изображений не использует всех методов сжатия, используемых стандартным jpeg-компрессором. В перспективе, вместо косинусного преобразования можно использовать wavelet-преобразование, что позволяет улучшить качество восстановленного изображения.

БИБЛИОГРАФИЯ

Бондарев В.Н., Трестер Г., Чернега В.С. Цифровая обработка сигналов: методы и средства.- СевГТУ..- 398 с.

Чернега В.С. Сжатие информации в компьютерных сетях. СевГТУ..- 198 с.

Лазарев Ю., MatLAB 5.x. - Киев .-384 с.

ПРИЛОЖЕНИЕ А

Текст программы на MatLab

% сжатие

clear;

img_rgb = imread('astrologer.bmp');

figure (1);

subplot(1,2,1);

imshow(img_rgb);

title('Исходное изображение');

set(1,'name','JPEG');

img_ybr = rgb2ycbcr(img_rgb);

Y = img_ybr(:,:,1);

Cb = img_ybr(:,:,2);

Cr = img_ybr(:,:,3);

width = length(img_ybr(1,:,:));

height = length(img_ybr(:,1,:))

blocksize = 8;

q = 6; % степень сжатия

for i=1:1:blocksize

for j=1:1:blocksize

Q(i,j) = 1+(1+i+j)*q;

end;

end;

i = 1;

j = 1;

max_i = fix(height/8)*8;

max_j = fix(width/8)*8;

res_Y = zeros(max_i,max_j);

l_yi = 1;

l_cbi = 1;

l_cri = 1;

Yt = zeros(max_i,max_j);

%ДКП и квантование

while i < max_i

j = 1;

while j < max_j

br_part = dct2(Y(i:i+blocksize-1,j:j+blocksize-1));

br_part = round(br_part./Q);

blue_part = dct2(Cb(i:i+blocksize-1,j:j+blocksize-1));

blue_part = round(blue_part./Q);

red_part = dct2(Cr(i:i+blocksize-1,j:j+blocksize-1));

red_part = round(red_part./Q);

for ii=1:1:blocksize

for jj=1:1:blocksize

l_Y(l_yi) = br_part(ii, jj);

l_yi = l_yi+1;

l_Cb(l_cbi) = blue_part(ii, jj);

l_cbi = l_cbi+1;

l_Cr(l_cri) = red_part(ii, jj);

l_cri = l_cri+1;

end;

end;

j = blocksize+j;

end;

i = blocksize+i;

end;

yj = 1;

cbj = 1;

crj = 1;

y_zero_count = 0;

cb_zero_count = 0;

cr_zero_count = 0;

%сжатие

for i=1:1:length(l_Y)

if (l_Cb(i) ~= 0)

if (cb_zero_count ~= 0)

coded_Cb(cbj) = 0;

cbj = cbj+1;

coded_Cb(cbj) = cb_zero_count;

cb_zero_count = 0;

cbj = cbj+1;

end;

coded_Cb(cbj) = l_Cb(i);

cbj = cbj+1;

else

cb_zero_count = cb_zero_count+1;

end;

if (l_Y(i) ~= 0)

if (y_zero_count ~= 0)

coded_Y(yj) = 0;

yj = yj+1;

coded_Y(yj) = y_zero_count;

y_zero_count = 0;

yj = yj+1;

end;

coded_Y(yj) = l_Y(i);

yj = yj+1;

else

y_zero_count = y_zero_count+1;

end;

if (l_Cr(i) ~= 0)

if (cr_zero_count ~= 0)

coded_Cr(crj) = 0;

crj = crj+1;

coded_Cr(crj) = cr_zero_count;

cr_zero_count = 0;

crj = crj+1;

end;

coded_Cr(crj) = l_Cr(i);

crj = crj+1;

else

cr_zero_count = cr_zero_count+1;

end;

end;

if (cb_zero_count ~=0)

coded_Cb(cbj) = 0;

cbj = cbj+1;

coded_Cb(cbj) = cb_zero_count;

end;

if (y_zero_count ~=0)

coded_Y(yj) = 0;

yj = yj+1;

coded_Y(yj) = y_zero_count;

end;

if (cr_zero_count ~=0)

coded_Cr(crj) = 0;

crj = crj+1;

coded_Cr(crj) = cr_zero_count;

end;

% запись в файл сжатый массив и фактор качества, и размер изображения

f = fopen('coded.img','wb');

res = [coded_Y,coded_Cb,coded_Cr];

fprintf(f,'%d %d %d ',max_i,max_j,q);

for i=1:1:length(res);

fprintf(f,'%d ',res(i));

end;

fclose(f);

% восстановление

clear;

blocksize = 8;

f = fopen('coded.img','rb');

sourse = fscanf(f,'%d');

fclose(f);

width = sourse(2);

height = sourse(1);

q = sourse(3);

N_sourse = length(sourse);

sourse = sourse(4:N_sourse);

N_sourse = N_sourse-3;

% декомпрессия изображения

j = 1;

i = 1;

while (i<N_sourse)

if (sourse(i) ~= 0)

out(j) = sourse(i);

j = j+1;

i = i+1;

else

out(j:j+sourse(i+1)) = 0;

j = j+sourse(i+1);

i = i+2;

end;

end;

% разбиение на яркость, синий, красный

new_length = fix(length(out)/8)*8;

out = out(1:new_length);

part_length = new_length/3;

%вычисление матрицы квантов

for i=1:1:blocksize

for j=1:1:blocksize

Q(i,j) = 1+(1+i+j)*q;

end;

end;

% формирование массивов

l_Y = out(1:part_length);

l_Cb = out(part_length+1:part_length+part_length);

l_Cr = out(part_length+part_length+1:part_length+part_length+part_length);

% вычисление кол-ва матриц

N_elem = blocksize*blocksize;

N_matr = round(part_length/(N_elem));

i_block = 1;

i = 1;

while i < height

j = 1;

while j < width

yblock_64 = l_Y(i_block:i_block+N_elem-1);% выделяемм 64 элемента

cbblock_64 = l_Cb(i_block:i_block+N_elem-1);

crblock_64 = l_Cr(i_block:i_block+N_elem-1);

l_yi = 1;

for ii=1:1:blocksize

for jj=1:1:blocksize

br_part(ii, jj) = yblock_64(l_yi);% записываем в матрицу

blue_part(ii, jj) = cbblock_64(l_yi);

red_part(ii, jj) = crblock_64(l_yi);

l_yi = l_yi+1;

end;

end;

%для записи другого блока (запись c 65)

i_block = i_block+64;

% деквантование

br_part = br_part.*Q;

blue_part = blue_part.*Q;

red_part = red_part.*Q;

% обратное косинусное преобразование

Y(i:i+blocksize-1,j:j+blocksize-1) = idct2(br_part);

Cb(i:i+blocksize-1,j:j+blocksize-1) = idct2(blue_part);

Cr(i:i+blocksize-1,j:j+blocksize-1) = idct2(red_part);

j = j+blocksize;

end;

i = i+blocksize;

end;

% формирование изображения

img_ybr(:,:,1) = uint8(Y);

img_ybr(:,:,2) = uint8(Cb);

img_ybr(:,:,3) = uint8(Cr);

img_rgb = ycbcr2rgb(img_ybr);

%изображение

figure (1);

subplot(1,2,2);

imshow(img_rgb,'truesize');%вывод изображения на экран

title('Сжатое изображение');