Преподаватель который помогает студентам и школьникам в учёбе.

Создание программного обеспечения для сжатия изображений

Содержание:

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:

Алгоритмы сжатия без потерь;
Алгоритмы сжатия с потерями.

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

Алгоритмы сжатия без потерь

Алгоритм RLE

Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.

Словарные алгоритмы

Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:

Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.

В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.

Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.

Алгоритмы статистического кодирования

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

Алгоритм Хаффмана

Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.
Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.

Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
Выбираются два свободных узла дерева с наименьшими весами
Создается их родитель с весом, равным их суммарному весу
Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0
Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.

С помощью этого алгоритма мы можем получить коды Хаффмана для заданного алфавита с учётом частоты появления символов.

Арифметическое кодирование

Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал [0;1) на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi.
Кодирующая дробь строится следующим образом: строится система вложенных интервалов так, чтобы каждый последующий полуинтервал занимал в предыдущем место, соответствующее положению элемента в исходном разбиении. После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код.
Декодирование – расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот.
Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным.

Алгоритмы сжатия с потерями

Не смотря на множество весьма эффективных алгоритмов сжатия без потерь, становится очевидно, что эти алгоритмы не обеспечивают (и не могут обеспечить) достаточной степени сжатия.
Сжатие с потерями (применительно к изображениям) основывается на особенностях человеческого зрения. Мы рассмотрим основные идеи, лежащие в основе алгоритма сжатия изображений 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 пользователь устанавливает показатель качества, величине которого "управляет" значениями матрицы квантования. Оптимальные показатели качества, обеспечивающие лучший баланс между коэффициентом сжатия и качеством изображения, различны для разных изображений и обычно могут быть найдены только методом проб и ошибок.

Алгоритм JPEG2000

Алгоритм JPEG-2000 разработан той же группой экспертов в области фотографии, что и JPEG. Формирование JPEG как международного стандарта было закончено в 1992 году. В 1997 стало ясно, что необходим новый, более гибкий и мощный стандарт, который и был доработан к зиме 2000 года.

Основные отличия алгоритма в JPEG 2000 от алгоритма в JPEG заключаются в следующем:

1)Лучшее качество изображения при сильной степени сжатия. Или, что то же самое, большая степень сжатия при том же качестве для высоких степеней сжатия. Фактически это означает заметное уменьшение размеров графики "Web-качества", используемой большинством сайтов.

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

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

4)Для повышения степени сжатия в алгоритме используется арифметическое сжатие. Изначально в стандарте JPEG также было заложено арифметическое сжатие, однако позднее оно было заменено менее эффективным сжатием по Хаффману, поскольку арифметическое сжатие было защищено патентами. Сейчас срок действия основного патента истек, и появилась возможность улучшить алгоритм.

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

6)Поддержка сжатия однобитных (2-цветных) изображений. Для сохранения однобитных изображений (рисунки тушью, отсканированный текст и т.п.) ранее повсеместно рекомендовался формат GIF, поскольку сжатие с использованием ДКП весьма неэффективно к изображениям с резкими переходами цветов. В JPEG при сжатии 1-битная картинка приводилась к 8-битной, т.е. увеличивалась в 8 раз, после чего делалась попытка сжимать, нередко менее чем в 8 раз. Сейчас можно рекомендовать JPEG 2000 как универсальный алгоритм.

7)На уровне формата поддерживается прозрачность. Плавно накладывать фон при создании WWW страниц теперь можно будет не только в GIF, но и в JPEG 2000. Кроме того, поддерживается не только 1 бит прозрачности (пиксель прозрачен/непрозрачен), а отдельный канал, что позволит задавать плавный переход от непрозрачного изображения к прозрачному фону.

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

Этапы кодирования

Процесс сжатия по схеме JPEG2000 включает ряд этапов:

1. Преобразование изображения в оптимальное цветовое пространство.

На данном этапе кодирования с помощью соответствующих соотношений цветовая модель RGB преобразуется в YUV:

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

2. Дискретное вейвлет преобразование.

Дискретное wavelet преобразование (DWT) также может быть двух видов - для случая сжатия с потерями и для сжатия без потерь.

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

y( 2*n + 1 ) = x( 2*n + 1 ) - (int)( x( 2*n ) + x( 2*n + 2 ) ) / 2

y( 2*n ) = x( 2*n ) + (int)( y( 2*n - 1 ) + y( 2*n + 1 ) + 2 ) / 4

и обратное

x( 2*n ) = y( 2*n ) - (int)( y( 2*n - 1 ) + y( 2*n + 1 ) + 2 ) / 4

x( 2*n + 1 ) = y( 2*n + 1 ) + (int)( x( 2*n ) + x( 2*n + 2 ) ) / 2.

3. Квантование коэффициентов.

Так же как и в алгоритме JPEG, при кодировании изображения в формат JPEG2000 используется квантование. Дискретное вейвлет преобразование, так же как и его аналог, сортирует коэффициенты по частотности. Но, в отличие от JPEG, в новом формате матрица квантования одна на все изображение.

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

.Как и в JPEG, в новом формате последним этапом алгоритма сжатия является кодирование без потерь. Но, в отличие от предыдущего формата, в JPEG2000 используется алгоритм арифметического сжатия.

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

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

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

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

С выходом iOS 11 и MacOS High Sierra миллионы пользователей продукции яблочного гиганта получили возможность использовать новый формат хранения изображений HEIF. Он пришел на смену старому доброму JPEG, хотя многие и не знают, что это произошло. По расчетам Apple пользователи должны получить значительную экономию места на диске (до 50%) за счет большей эффективности сжатия при лучшем качестве картинки.

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

Им стал High Efficiency Image Format, или сокращенно HEIF. Файлы этого формата в операционных системах Apple получили расширение .heic, хотя другими производителями чаще используется .heif.

Несколько фактов о HEIF:

В 2013 году формат HEIF был предложен Moving Picture Experts Group (MPEG), он был определен в рамках стандарта MPEG-H Part 12 (ISO/IEC 23008-12). В течение полутора лет продолжалось его техническая разработка, которая была завершена к 2015 году.

Сам HEIF является контейнерным форматом, состоящим из метаданных Exif с дополнительными разделами для XMP и MPEG-7

В дополнение к метаданным контейнер HEIF содержит одно или несколько изображений или последовательность изображений, закодированных с использованием высокоэффективного стандарта сжатия HEVC — High Efficiency Video Coding, который более известен как стандарт H.265. За счет этого пользователи получат экономию памяти как локально, так и в облаке. Если несколько изображений упакованы в контейнер HEIF, размер файла будет значительно меньше, чем хранение нескольких JPEG, представляющих одно и то же изображение или набор изображений. Несколько изображений и видео могут быть одновременно упакованы в контейнере HEIF.

В отличие от JPEG, HEIF может содержать несколько изображений, используемых для разных случаев. Например, основное полноразмерное изображение может быть представлено первичным, вспомогательным и эскизным изображениями.

Вспомогательные изображения могут иметь альфа канал.

Имеется встроенная поддержка оверлеев.

Контейнер HEIF может содержать эквивалентные изображения, например альтернативу более низкому разрешению. В качестве примера можно привести браузер, загружающий картинку с низким разрешением на медленном канале связи или обнаружение дисплея < 4K. В стандарте HTML 5.2 предусмотрена поддержка подобных случаев.

Поддержка одновременного хранения данных, сжатых с потерями и без (lossy and lossless). Фотографы оценят сохранение необработанных и сжатых фотографий в одном контейнере.

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

HEIF также поддерживает прозрачность и цвет изображения до 16 бит, по сравнению с 8-битной глубиной цвета в JPEG. На практике это означает, что HEIF может захватить весь расширенный цветовой диапазон, предоставляемый 10-битным цветовым выходом цифровых камер, исключая нежелательные артефакты.

Теперь, когда вы немного больше узнали о HEIF, давайте поговорим о стандарте кодирования HEVC или H.265.

В двух словах, стандарт HEVC поддерживает эффективное сжатие для полноразмерных изображений наряду с предсказанием последовательностей (predictive sequencing) и дополнениями для поддержки других медиа-потоков, таких, как синхронизированный текст и аудио.

Формат предоставляет потрясающие возможности — это не только потенциальная замена анимированного GIF, но и усовершенствование живых фотографий Apple, что открывает двери для других функций, таких как встроенное редактирование и полный контроль воспроизведения.

Кроме того, HEVC поддерживает прямоугольную обрезку и вращение на 90 градусов без необходимости повторного кодирования изображения или последовательности изображений. Это дает возможность написания эффективного кода обработки изображений на мобильных устройствах, что приведет к значительной экономии заряда батареи. На самом деле, устройства Apple с чипом A9 и выше выиграют от аппаратного ускорения для кодирования и декодирования файлов HEIF.

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 Разработка программного модуля на языке JPHP

Прежде, чем приступить к разработке программного обеспечения для сжатия изображений, необходимо выбрать алгоритм обработки и язык программирования. Выбор пал на проект Devel Next, среда разработки которого довольно проста в использовании и построена на языке JPHP.

JPHP – это альтернативная реализация языка php, от автора DevelNext. Проект jphp был начат еще в октябре 2013 года, целью проекта было написать компилятор в байткод (аля машинный код) Java, который затем бы выполнялся на виртуальной машине Java (да это и язык, и виртуальная машина, название одинаковое). Виртуальная машина (JVM если коротко), способна выполнять этот “машинный код” очень быстро, применять технику JIT там, где необходимо и даже оптимизировать полученный код, все для того, чтобы код выполнялся быстрее.

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

Интерфейс программы выполнен в стиле UI Windows, что не вызывает проблем при взаимодействии с созданным программным обеспечением. Управление процессом полностью интуитивно, так как в нем нет огромного количества непонятных переключателей: все управление завязано на 2 кнопках и 1 ползунке для выбора качества сохраняемого изображения.

Код программы:

<?php

namespace app\forms;

use compress\Compress;

use ErrorException;

use std, gui, framework, app;

class MainForm extends AbstractForm

{

/**

* @event button.action

function doButtonAction(UXEvent $e = null)

{

if($this->fileChooser->execute()) {

$this->image->image = new UXImage($this->fileChooser->file);

}

$input = 'r5OSGSM.jpg';

$this->lib = new Compress($input, "./output.jpg");

$this->lib->compress(0.5);

$this->slider->observer("value")->addListener(function ($old, $new) {

new Thread(function () use ($new) {

try {

$this->lib->compress($new * 0.01);

} catch (ErrorException $e) {}

$file = File::of("./output.jpg");

if($file->exists()) {

uiLater(function () use ($file) {

$this->imageAlt->image = new UXImage($file);

});

}

})->start();

});

}

ЗАКЛЮЧЕНИЕ

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

Но, так как сам по себе алгоритм jpeg уже довольно стар и неидеален, в дальнейшем исследовании данной темы будут применены более современные и прогрессивные алгоритмы сжатия, такие как HEIC и AV1.

ИCТОЧНИКИ:

http://compression.ru/

http://develnext.org/ru/

ПРИЛОЖЕНИЕ 1 (Программа и инструкция)

ПРИЛОЖЕНИЕ 1 (Исходный код программы)

https://drive.google.com/drive/folders/1TINmyUnsvmEKmoL-1sZ3ymXth5MadIq6?usp=sharing