Моделирование при сжатии текстовых данных модели для сжатия изображений

Содержание

Сжатие изображений

Цифровое изображение при хранении занимает большие объемы памяти. Так растровое изображение размером 1024 на 1024 пикселов с глубиной цвета 24 бит занимает 3 Мб. Понятно, что хранение и передача изображений в таком виде является весьма трудоёмкой задачей. Поэтому задача представления изображений в компактной форме (сжатие данных) является весьма актуальной. При этом должны быть разработаны алгоритмы как для кодирования, так и для декодирования (восстановления) изображений.

Алгоритмы сжатия изображений делятся на два больших класса: без потерь и с потерями. В первом случае в ходе компрессии информация об изображении сохраняется в полном объеме, а во втором – частично утрачивается. Первая группа методов сжатия обеспечивает восстановление исходного изображения без потерь и искажений. Для хранения изображений, предназначенных для дальнейшей обработки, следует применять форматы, использующие именно такие методы сжатия. Однако, если изображение предназначено для визуального восприятия, это не всегда необходимо. В ряде случаев исходный сигнал уже содержит такие искажения и шумы, что небольшие потери информации при кодировании (в пользу высокой степени сжатия) не испортят качества изображения в целом.

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

Рассмотрим некоторые из используемых методов сжатия изображений.

Груповое сжатие

Одним из простейших методов сжатия изображений является алгоритм RLE (Run Length Encoding – кодирование с переменной длиной строки). Основной идеей этого метода является поиск одинаковых пикселов в одной строке. Найденные цепочки одинаковых элементов заменяются на пары (счетчик повторений, значение), что в определенных случаях существенно уменьшает избыточность данных.

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

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

Входной поток данных:
17 8 54 0 0 0 97 5 16 0 45 23 0 0 0 0 0 3 67 0 0 8

Поток данных после кодирования:
17 8 54 0 3 97 5 16 0 1 45 23 0 5 3 67 0 2 8

Чаще всего для кодирования используется схема, которая называется PackBits. По аналогии с хранением отрицательных чисел, каждые 7 бит исходных данных заменяются в результате на 8 бит. Дополнительный девятый бит интерпретируется как флаг сжатия. Например:

Входные данные: 1,2,3,4,2,2,2,2,4

Данные после кодирования: 1,2,3,4,2,&3,4.

Принцип: Последовательности повторяющихся значений цвета заменяются его значением и количеством повторений.

Форматы: BMP, TIFF, GIF

Коэффициент сжатия: 2

Метод Хафмана

Этот метод назван в честь его разработчика (1950). Алгоритм основан на том предположении, что некоторые значения сигнала встречаются чаще других. Если проанализировать гистограммы изображений, то можно в этом убедиться. Этот факт можно использовать для сжатия изображений. Использовать для хранения значений интенсивности, которые встречаются чаще, меньшее число бит чем на само значение. Главная проблема в том, чтобы отделять одно значение от другого. Ведь на разные значения отводится разное количество бит. Метод сжатия Хафмана можно проиллюстрировать следующим образом:

Значение Частота упоминания Код Хафмана
A
B
C
D
E
F
G
.154
.110
.072
.063
.059
.015
.011
1
01
0010
0011
0001
000010
000011

Входной поток данных: C E G A D F B E A

Поток данных после кодирования: 0010 0001 000011 1 0011 000010 01 0001 1)

Группировка по байтам: (0010 0001) (000011 1 0) (011 00001) (0 01 00 1 0 1)

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

Этот метод иногда используется в усложненной форме, когда кодируется не одно значение, а последовательности значений. Другая модификация метода – подвергнуть коды Хафмана групповому сжатию.

Форматы: TIFF, GIF

Коэффициент сжатия: 3

Метод LZW

Этот метод назван также в честь его разработчиков (Lempel, Ziv, Welch). Это универсальный метод, пригодный для кодирования любых сигналов. Похож на метод Хафмана, только для кодирования элементов используются коды равной длины, а также используются коды для часто встречающихся последовательностей элементов.

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

Индекс Значение
0000
0001
0254
0255
0256
0257
4095
0
1
254
255
145 201 4
243 245
xxx xxx xxx

Входной поток данных: 123 145 201 4 119 89 243 245 59 11 206 145 201 4 243 245

Поток данных после кодирования: 123 256 119 89 257 59 11 206 256 257

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

Форматы: TIFF, GIF

Коэффициент сжатия: 5

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

Метод JPEG

Среди методов сжатия с потерями следует выделить семейство JPEG, разработанное организацией Joint Photographers Experts Group. Метод основан на частотных представлениях изображения и следующих предположениях. Если к сигналу применить интегральное преобразование (Фурье например), то в результате в частотном представлении основную информации несут низкие частоты. Высокие частоты описывают шум и несущественные детали. Удаление 50% высокочастотной информации повлечет за собой удаление 5% полезной информации содержащейся в изображении.

JPEG-сжатие начинается с разбиения изображения на квадратные области размером 8 на 8 пикселов (64 пиксела — 64 байта). Эти области обрабатываются независимо. После преобразования в каждой группе остается от 2 до 20 байт. При восстановлении сигнала должна быть выполнена аппроксимация и восстановлена исходная область 8 на 8 пикселов.

Для сжатого представления сигнала могут использоваться различные преобразования. Наиболее адекватный (качественные) результат дает преобразование Karhunen-Loeve, но оно сложно и трудоемко в реализации. Преобразование Фурье просто, но не дает желаемого результата при восстановлении. Наиболее пригодным оказалось дискретное косинусное преобразование (Discrete Cosine Transform, DCT). При использовании DCT не нужно работать с комплексными числами (исходный сигнал и его спектр вещественные).

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

Если представить спектр в виде следующей последовательности:

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

Принцип: Используется методика сжатия с потерями. Хранится не информация о цвете пикселов, а коэффициенты разложения по некоторому базису.

Коэффициент сжатия: в зависимости от качества от 10 до 1000.

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

Алгоритмы сжатия изображений.

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

1. RLE-сжатие (групповое кодирование). Большая часть растровых изображений, используют RLE-метод сжатия(TIFF, BMP и PCX.). RLE в действительности не сжимает информацию заголовка или цветовую палитру , но сжимает только данные изображения. RLE является методом сжатия без потерь. RLE кодирует данные изображения по строке просмотра за один раз. Оно начинается с первого байта изображения и заканчиваются последним. Имеются два типа проходов, в соответствие с которыми осуществляется сжатие RLE — кодированные и литеральный. Кодированный проход всегда содержит байт для числа пикселов и байт для информации о пикселе. Литеральный проход может содержать пять и более байтов данных. Данный метод сжатия иногда увеличивает размер растрового файла. RLE — метод сжатия является быстрым, простым. Эффективность сжатия зависит от типа данных изображения, подлежащего кодированию. Черно-белые изображения, кодируются хорошо, Сложные изображения, кодируются плохо.

2. LZW — сжатие. Используется форматами TIF и GIF. Предназначен для сжатия неподвижных изображений. LZW сжатие является методом сжатия без потерь. алгоритм, основанный на поиске и замене в исходном файле одинаковых последовательностей данных, для их исключения, и уменьшения размера архива. Данный тип компрессии не вносит искажений в исходный графический файл, и подходит для сжатия растровых данных любого типа. Алгоритм LZW — сжатия уменьшает строку, которая имеет идентичные значения байтов до одного слова кода, а затем сохраняет эту информацию в горизонтальных полосках. Метод сжатия LZW может уменьшить размер изображения до 40%.

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

4.CCITT— алгоритм для сжатия факсимальных изображений, метод исп кодир хоффмана (Идея, кодировании Хаффмана, основана на частоте появления символа в последовательности. Символ, который встречается в последовательности чаще всего, получает новый очень маленький код, а символ, который встречается реже всего, получает, наоборот, очень длинный код.). Кодир строк происх независ одной от другой, данные идущие до строки и после нее не оказ на нее влияния. Такой вар наз однонапр или гр 3. Сущ еще гр 4-кодир осущ в 2х напр-кодир предыд строки влияет на текущ. Коэф сжатия для гр 3 1/15, для гр 4- 1/20

5. Фрактальное сжатие. Ученые выяснили, что при разбиении сложной структуры на набор фракталов, можно хранить фрагментарный набор на меньшем пространстве по сравнению с оригинальным объектом. Можно масштабировать изображения без искажений и разрешения .

6. Волновое сжатие. Описывает данные, подлежащие сжатию, в терминах частоты, энергии и тактов, а затем записывает определенные атрибуты изображения. Единственным примером этой технологии сжатия, является HARC-CHARC-C демонстрирует весьма поразительные коэффициенты сжатия, в среднем равные 300:1. HARC-C является методом сжатия без потерь.

Не нашли то, что искали? Воспользуйтесь поиском:

Лучшие изречения: Учись учиться, не учась! 10386 — | 7888 — или читать все.

188.64.174.135 © studopedia.ru Не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования. Есть нарушение авторского права? Напишите нам | Обратная связь.

Отключите adBlock!
и обновите страницу (F5)

очень нужно

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

Доклад

на тему: «Алгоритмы сжатия изображения. Типы изображений».

Выполнила:

Студентка группы 250201

Алексеева А. А.

Проверила:

Доцент каф. ВТ Первак И. Е.

Тула 2013 г.

Оглавление:

1. Алгоритмы сжатия изображения ………………………………………………3

2. Сжатие изображения RLE-методом …………………………………………..5

3. Сжатие изображения LZW-методом ………………………………………….6

5. Типы изображений …………………………………………………………….13

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

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

Сжатие данных в вычислительной технике – методика, позволяющая добиться сокращения объема памяти, занимаемой данным (в данном случае изображениями). Методы сжатия подразделяются на :

— алгоритмы без потери данных – при котором изображение не потеряет своего качества;

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

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

Основными алгоритмами сжатия без потерь являются:

1. Run Length Encoding (RLE) ;

2. LZW (получившее название по первым буквам его разработчика – Lempel, Ziv и Welch);

3. Метод Хоффмана – один из классических алгоритмов, известных с 60х годов. Использует только частоту появления одинаковых байт в изображении. Сопоставляет символам входного потока, которые встречаются большее число раз, цепочку бит меньшей длины. И, напротив, встречающимся редко – цепочку большей длины. Для сбора статистики требует двух проходов по изображению. Единственный алгоритм, который не увеличивает размера исходных данных. Для графики позволяет уменишить размер изображения примерно в 1,2-2,5 раза. Однако этот алгоритм оптимален только в тех случаях, когда вероятности появления символов кратны степеням ½.

4. CCITT Group3, CCITT group 4 – два похожих метода сжатия графических данных, работающие с однобитными изображениями, сохраненными в цветовой модели Bitmap. Основаны на поиске и исключении из исходного изображения дублирующихся последовательностей данных (как и в RLE). Эти алгоритмы ориентированы на упаковку именно растовой графической информации, так как работают с отдельными рядами пикселов в изображении.

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

Основной алгоритм сжатия с потерями данных:

JPEG (Joint Photographic Experts Group) – алгоритм основан на особенностях восприятия челвоеческим глазом различных цветов, и достаточно громоздок с вычислительной точки зрения, так как занимает много процессорного времени. Происходит кодирование файла в несколько этапов. Изображение условно разбивается на несколько цветовых каналов, затем изображение разбивается на группы по 64 пиксела в каждой, затем цвет пикселов специальным образом кодируется. Полученные данные сжимаются по RLE или LZW-алгоритму для получения большей компрессии. В результате, на выходе получаем файл, иногад в десятки раз меньший, чем его неконвертированный аналог. Этот метод сжатия используется в файлах формата PDF, PostScript, собственно в JPEG и других.

Главным недостатком компрессии с частичной потерей качества является то, что эти потери, выражающиеся в искажении цветого тона или проявлении характерной кубической структуры в контрастных участах изображения возникают каждый раз при сохранении изображения, и “накладываются” друг на друга при многократном сохранении файла в этом формате.

Реферат: Методы компрессии и сжатия изображений

Графические данные, особенно данные растровых файлов, занимают колоссальное количество дискового пространства. Например, растровое изображение формата А4 в цветовой модели CMYK при разрешении 300 точек на дюйм занимает порядка 30 мегабайт дискового пространства. Хорошо, если файл один, и ваша публикация не использует других изображений (что крайне маловероятно). Ситуация в корне изменяется тогда, когда вы создаете некий шедевр, например, галерею репродукций картин А2 формата, при этом она с трудом умещается на 100 листах, запечатанных с двух сторон. При самых скромных подсчетах (120 мегабайт х 100 листов х 2 стороны у каждого листа), растровые изображения в этом формате при таком количестве листов будут занимать порядка 24 гигабайт дискового пространства. На чем вы собираетесь хранить такую публикацию ? А теперь представьте, что у вас несколько заказчиков, и работы каждого из них хранятся в нескольких вариантах оформления, кроме того, для большинства заказов вы сохранили выполненный проект на разных стадиях его готовности, чтобы в случае желания заказчика все в корне и кардинально изменить, вы могли быстро это выполнить. Естественно, все эти данные сохранить будет очень и очень сложно. Именно поэтому, а также потому, что дисковое пространство обычно достаточно дорого обходится (не смотря на то, что устройства для хранения цифровой информации постоянно дешевеют, их все время требуется больше и больше, что требует немалых капиталовложений), были изобретены множество методов сжатия данных самого различного типа, в том числе и графических. О наиболее распространенных и широко использующихся мы сейчас поговорим.

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

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

Компрессия (конвертирование) данных — это способ сохранения данных таким образом, при использовании которого не гарантируется (хотя иногда возможно) полное восстановление исходных графических данных. При таком способе хранения данных обычно графическая информация немного «портится» по сравнению с оригинальной, но этими искажениями можно управлять, и при их небольшом значении ими вполне можно пренебречь. Обычно файлы, сохраненные с использованием этого способа хранения, занимают значительно меньше дискового пространства, чем файлы, сохраненные с использованием простой аривации (сжатия). Сильная степень компрессии при использовании второго способа сжатия и дает этому способу хранения данных право на существование (в противном случае, все поголовно использовали бы сжатие без потерь). Как правило, при сохранении данных с использованием компрессии, имеется возможность компромисса между размером выходного файла и его качеством. Понятно, что возможна оптимизация только по одному параметру (чем меньше качество, тем меньше объем выходного файла, и наоборот).

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

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

RLE (Run — length encoding) — метод сжатия данных, при котором одинаковые последовательности одних и тех же байт заменяются однократным упоминанием повторяющегося байта (или целой цепочки байтов), и числа его повторений в исходных данных. Например, строка типа 0100 0100 0100 0100 0100 0100 0100 0100, описывающая некую группу пикселов будет заменена на запись типа 0100 х 8, и т.д. Применяется этот тип сжатия в тех случаях, когда изображение имеет большие участки одинакового цвета, цифровое представление которых идентично. В основном, этот тип сжатия применим для монохромных изображний, сохраненных в цветовой модели Bitmap, где при сжатии данных с его использованием можно добиться наилучших результатов. Для сжатия других типов данных (в том числе, и не графических) алгоритм применим, но малоэффективен, так как сжимаемые данные должны иметь простую повторяющуюся структуру). Этот алгоритм имеет еще одно важное преимущество, заключающееся в его относительной простоте, что позволяет быстро производить распаковку из этого формата и упаковку в этот формат (как вы помните, все графические данные для их обработки должны быть предварительно распакованы, а любая компрессия или архивация применяется, в основном, для временного или постоянного хранения файла). В принципе, на основе этого несложного алгоритма, работают более совершенные и более сложные (а также менее быстрые) методы сжатия графических данных, которые мы рассмотрим ниже. Этот метод сжатия графических фанных испольуется для файлов формата PSD, BMP и других.

CCITT Group 3, CCITT Group 4 — Два похожих метода сжатия графических данных, работающие с однобитными изображениями, сохраненными в цветовой модели Bitmap. Основаны на поиске и исключении из исходного изображения дублирующихся последовательностей данных (как в предыдущем типе сжатия, RLE). Различием является лишь то, что эти алгоритмы ориентированы на упаковку именно растровой графической информации, так как работают с отдельными рядами пикселов в изображении. Изначально алгоритм был разработан для сжатия данных, передаваемых через факсимильные системы связи (CCITT Group 3), а более совершенная разновидность этого метода архивации данных (CCITT Group 4) подходит для записи монохромных изображений с более высокой степенью сжатия. Как и предыдущий алгоритм, он, в основном, подходит для сжатия изображений с большими одноцветными областями. Его достоинством является скорость выполнения, а недостатком — ограниченность применения для компрессии графических данных (не все данные удается таким образом эффективно сжать). Этот метод сжатия графических фанных испольуется в файлах формата PDF, PostScript (в инкапсулированных объектах) и других.

LZW (Lemple-Zif-Welch) — алгоритм сжатия данных, основанный на поиске и замене в исходном файле одинаковых последовательностей данных, для их исключения, и уменьшения размера «архива». В отличие от предыдущих рассмотреных методов сжатия, в данном случае производится более «интеллектуальный» просмотр сжимаемого cодержимого, для достижения большей степени сжатия данных. Данный тип сжатия не вносит искажений в исходный графический файл, и подходит для обработки растровых данных любого типа — монохромных, черно — белых, или полноцветных. Наилучшие результаты получаются при компрессии изображений с большими областями одинакового цвета или изображений с повторяющимися одинаковыми структурами. Этот метод позволяет достичь одну из самых наилучших степеней сжатия среди других существующих методов сжатия графических данных, при одновременном полном отсутствии потерь или искажений в исходных файлах. Этот метод сжатия графических фанных испольуется в файлах формата TIFF, PDF, GIF, PostScript (в инкапсулированных объектах) и других.

ZIP — метод сжатия данных, аналогичный методу, использованному в популярном алгоритме архивации PKZip. В основу метода сжатия положен метод, аналогичный LZW. Как и предыдущий метод сжатия данных, этот способ не вносит искажений в исходный файл, и лучше всего подходит для обработки графических данных с одинаковыми одноцветными или повторяющимися областями. Этот метод сжатия графических фанных испольуется в файлах формата PDF, TIFF и некоторых других.

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

JPEG (Joint Photographic Experts Group) — метод, используемый для хранения полутоновых и полноцветных изображений, позволяющий добиться наивысшей степени сжатия и минимальный размер выходного файла. Основан алгоритм на особенностях восприятия человеческим глазом различных цветов, и достаточно громоздок с вычислительной точки зрения, так как занимает много процессорного времени. Происходит кодирование файла в несколько этапов. Во-первых, изображение условно разбивается на несколько цветовых каналов, для дальнейшего анализа. Затем, изображение разбивается на группы, по 64 пиксела в каждой группе, которые представляют из себя квадратные участки изображения размером 8х8 пикселов, для последующей обработки. Затем, цвет пикселов специальным образом кодируется, исключается дублирующая и избыточная информация, причем при описании цвета большее внимание уделяется скорее яркостной, чем цветовой составляющей, так как человеческий глаз воспринимает больше изменения яркости, чем конкретного цветового тона. Полученные данные сжимаются по RLE или LZW — алгоритму, для получения еще большей компрессии. В результате, на выходе мы получаем файл, иногда в десятки раз меньший, чем его неконвертированный аналог. Однако, чем меньше размер выходного файла, тем меньше степень «аккуратности» при работе программы — конвертора, и, соответственно, ниже качество выходного изображения. Обычно, в программах, позволяющих сохранять растровые данные, возможно задание некоего компромисса между объемом выходного файла и качеством изображения. При наивысшем качестве, обхем выходного файла в 3-5 раз меньше исходного незапакованного. При наименьшем — меньше исходника в десятки раз, но, как правило, при этом качество изображения не позволяет его где-либо использовать. Как правило, для сохранения достойного уровня качества, используют наивысшую из доступных степень качества. Данный формат предназначен для хранения, в основном, фотографических изображений с большим количеством оттенков и цветовых переходов, и практически не подходит для хранения однотонных изображений типа кадров из мультфильмов, скриншотов и пр.(сжатие будет слишком низким, или качество картинки окажется просто недопустимым). Этот метод сжатия графических фанных испольуется в файлах формата PDF, PostScript (в инкапсулированных объектах), собственно, в JPEG и других.

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

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

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

Изменение разрешения растрового файла. Файл с разрешением 600 точек на дюйм больше своего аналога разрешением в 300 точек в четыре раза, а качество печати при повышенном разрешении не всегда будет выше, нем при номинальном его значении. Так что если разрешение избыточно, можете его понизить. Понижение разрешения файла — необратимый процесс, и никакя последующая интерполяция потом потерянные пикселы не восстановит. Так что при задании необходимого разрешения также будьте внимательны и рациональны. Следует учесть, что параметр разрешения контуров применительно к векторной графике не имеет отношения к объему выходного файла (это уже несколько другое разрешение и несколько другое понятие), а влияет на аккуратность «прорисовки» вектора при его растеризации в устройстве, где производится печать. Так что уменьшение этого параметра для векторной графики не уменьшит объем ваших файлов, а только ухудшит качество печати.

Ресемплирование (изменение глубины цвета растрового изображения) — это изменение начальной глубины цвета файла. Некоторые оцифровывающие устройства выдают растровую информацию с глубиной цвета, превышающую достаточное для печати значение 8 бит на канал. Это иногда оправдано, так как большее значение бит на канал позволяет задавать большее число градаций цвета, что требуется, например, при сильной, «кардинальной» цветокоррекции — сильном осветлении или затенении отдельных участков. Однако, в большинстве случаев для хранения растровых данных в различных цветовых моделях с лихвой достаточно глубины цвета 8 бит на канал. Кроме того, один из стандартов сжатия для RGB изображений подразумевает использование разного количества бит для разных цветовых составляющих (обычно наибольшее количество бит используется для зеленого канала). Также, большинство фильтров Adobe Photoshop рассчитано на работу с изображениями с глубиной цвета в 8 бит (с изображением, использующим нестандартную глубину цвета, становится практически невозможно работать, так как большинство фильтров рассчитаны на значение глубины цвета в 8 бит).

Хорошим примером настройки опций сжатия графики является диалоговое окно Job Options — Compression из программы Adobe Acrobat Distiller, опции которого рассмотрены ниже.

Рис. 1. Диалоговое окно Adobe Acrobat Distiller

Для различных типов изображений, которые могут быть составляющими файла PostScript (про такие объекты говорят, что они инкапсулированы) — для — полноцветных (color bitmap), полутоновых черно-белых (grayscale) и для штриховых объектов (bitmap, 1 bit per pixel) указаны различные установки параметров сжатия, являющиеся оптимальными для создания PDF — документа, оптимизированного для печати и сжатого с минимальными потерями качества. В качестве параметра сжатия изображения выбрана альтернатива JPEG с максимально возможным качеством. Выходное разрешение растровых полноцветных изображений выбрано не более 300 точек на дюйм, и в случае превышения указанного предельного разрешения к изображению будет применен алгоритм бикубической интерполяции с понижением разрешения (bicubic downsampling) — это наиболее медленный, но и наиболее качественный алгоритм интерполяции. Кроме этого алгоритма, допустимо также указать алгоритмы Average downsampling (усреднение значения цвета пикселов) и Subsampling (полное отсутствие интерполяции, берется один из пикселов, и его цвет устанавливается как цвет всего участка изображения). Естественно, последний вариант работает быстрее всех, но и с наименьшим качеством выходного изображения. Для черно — белых полутоновых изображений (grayscale) установки интерполояции, предельного разрешения и метода сжатия аналогичны прерыдущему примеру. Для монохромных изображений, заданных в цветовой модеди Bitmap с глубиной цвета 1 бит на пиксел параметры несколько другие. Во-первых, значение предельного разрешения установлено на уровне 1200 точек на дюйм, что является корректным для изображений в этой цветовой модели (напомню, что спектр разрешений для изображений в этой цветовой модели обычно задается в пределах от 800 до 2540 точек на дюйм). Метод интерполяции в случае превышения разрешения также бикубический, как и в предыдущих примерах, а вот метод сжатия выбран именно ZIP (возможен также выбор CCITT Group 3, CCITT Group 4, или RLE). При этом не происходит никаких потерь качества в выходном изображении. Кроме того, с учетом специфики цветовой модели, невозможно задание алгоритмов сжатия типа JPEG.

Последняя опция — Compress text and line art — подразумевает сжатие текстовых и векторных данных по одному из алгоритмов, подобных ZIP или LZW. Естественно, подразумевается полное восстановление данных при распаковке файла.

Методы сжатия графических данных

Читайте также:

  1. I. Методы коммутации.
  2. III. Методы финансирования инвестиционного проекта
  3. VI. МЕТОДЫ ИССЛЕДОВАНИЯ
  4. Автоматизированные методы
  5. Адаптивные методы прогнозирования используются
  6. Административно-правовые методы менеджмента
  7. Административно-правовые методы менеджмента.
  8. Административные методы
  9. Административные методы
  10. Активизирующие методы.
  11. Активные методы обучения на уроках РЯ
  12. Алгоритмические методы повышения достоверности контроля
Название: Методы компрессии и сжатия изображений
Раздел: Издательское дело и полиграфия
Тип: реферат Добавлен 12:55:02 29 марта 2008 Похожие работы
Просмотров: 1838 Комментариев: 13 Оценило: 4 человек Средний балл: 4.5 Оценка: неизвестно Скачать
Илон Маск рекомендует:  Свойства flex-контейнера

[119] При сжатии методом RLE (Run – Length Encoding) последовательность повторяющихся величин (величина – набор битов для представления видеопикселя) заменяется парой – повторяющейся величиной и числом ее повторений.

Метод сжатия RLE включается в некоторые графические форматы, например формат PCX.

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

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

[120] Метод сжатия LZW (Lempel-Ziv-Welch) основан на поиске повторяющихся узоров в изображении. Сильно насыщенные узорами рисунки могут сжиматься до 0,1 их первоначального размера. Метод сжатия LZW включается в файлы форматов TIFF и GIF; при этом данные формата GIF сжимаются всегда, а в случае формата TIFF право выбора возможности сжатия предоставляется пользователю. Существуют варианты формата TIFF, которые используют другие методы сжатия. Из-за различных схем сжатия некоторые версии формата TIFF могут оказаться несовместимыми друг с другом. Это означает, что возможна ситуация, когда файл в формате TIFF не может быть прочитан в некоторой графической программе, хотя она должна принимать этот формат. Другими словами, не все форматы TIFF одинаковы. Но, несмотря на эту проблему, TIFF является одним из самых популярных растровых форматов в настоящее время.

[121] Метод сжатия LZW разработан в 1978 году израильтянами Лемпелом и Зивом, и доработан позднее в США. Сжимает данные путем поиска одинаковых последовательностей (они называются фразы) во всем файле. Выявленные последовательности сохраняются в таблице, им присваиваются более короткие маркеры (ключи). Так, если в изображении имеются наборы из розового, оранжевого и зеленого пикселей, повторяющиеся 50 раз, LZW выявляет это, присваивает данному набору отдельное число (например, 7) и затем сохраняет эти данные 50 раз в виде числа 7. Метод LZW, так же, как и RLE, лучше действует на участках однородных, свободных от шума цветов, он действует гораздо лучше, чем RLE, при сжатии произвольных графических данных, но процесс кодирования и распаковки происходит медленнее.

[122] Метод сжатия JPEG обеспечивает высокий коэффициент сжатия (возможно сжатие 100:1) для рисунков фотографического качества. Формат файла JPEG, использующий этот метод сжатия, разработан объединенной группой экспертов по фотографии (Joint Photographic Experts Group). Высокий коэффициент сжатия достигается за счет сжатия с потерями, при котором в результирующем файле теряется часть исходно информации. Метод JPEG использует тот факт, что человеческий глаз очень чувствителен к изменению яркости, но изменения цвета он замечает хуже. Поэтому при сжатии этим методом запоминается больше информации о разнице между яркостями видеопикселей и меньше – о разнице между их цветами. Так как вероятность заметить минимальные различия в цвете соседних пикселей мала, изображение после восстановления выглядит почти неизменным. Пользователю предоставляется возможность контролировать уровень потерь, указывая степень сжатия. Благодаря этому, можно выбрать наиболее подходящий режим обработки каждого изображения: возможность задания коэффициента сжатия позволяет сделать выбор между качеством изображения и экономией памяти. Если сохраняемое изображение – фотография, предназначенная для высокохудожественного издания, то ни о каких потерях е может быть и речи, так как рисунок должен быть воспроизведен как можно точнее. Если же изображение – фотография, которая будет размещена на поздравительной открытке, то потеря части исходной информации не имеет большого значения. Эксперимент поможет определить наиболее допустимы уровень потерь для каждого изображения.

[123] BMP (Windows Device Independent Bitmap)

Самый простой растровый формат BMP, также известный под именем DIB, является родным форматом Windows, он поддерживается всеми графическими редакторами, работающими под ее управлением. В BMP данные о цвете хранятся только в модели RGB, поддерживаются как индексированные цвета (до 256 цветов), так и полноцветные изображения, причем в режиме индексированных цветов возможна простейшая компрессия RLE (Run Length Encoding — кодирование с переменной длиной строки). Без компрессии размер файла оказывается близок к максимально возможному. Благодаря примитивнейшему алгоритму записи изображения, при обработке файлов формата BMP очень мало расходуется системных ресурсов, поэтому этот формат очень часто используется для хранения логотипов, экранных заставок, иконок и прочих элементов графического оформления программ.

[124] PCX (Soft Publisher’s Paintbrush)

Примерно такими же возможностями, как BMP, обладает и формат PCX, разработанный еще на заре компьютерной эпохи фирмой Z-Soft специально для своего графического редактора PC PaintBrush. Цветовые возможности: 1, 2, 4, 8 или 24- битовый цвет, поддерживается только схема RGB, причем полностью отсутствуют возможности сохранения монохромного изображения в оттенках серого. Как и ВМР, этот формат в значительной мере устарел и поддерживается современными графическими программами исключительно для совместимости с антикварным софтом.

[125] GIF (Graphics Interchange Format)

Самым популярным форматом на интернетовских просторах является достаточно уже пожилой формат GIF, предложенный фирмой CompuServe в далеком 1987 году. Отличительной его особенностью является использование режима индексированных цветов (не более 256), что ограничивает область применения формата изображениями, имеющими резкие цветовые переходы. Формат GIF является излюбленным форматом веб-мастеров, использующих его для сохранения многочисленных элементов оформления своих страничек. Небольшие размеры файлов изображений обусловлены применением алгоритма сжатия без потерь качества LZW, благодаря чему изображения в этом формате наиболее удобны для пересылки по каналам связи глобальной сети. К числу его самых заметных отличий относятся возможность использования режима постепенного проявления изображения (interleaved), в этом режиме строки изображения выводятся на экран не подряд, а в определенном порядке: сначала каждая 8-я, затем — 4-я и т.д. Таким образом, полностью изображение показывается в четыре прохода, что позволяет еще до полной загрузки изображения понять его суть, и, в случае необходимости, прервать его закачку. В 1989 году формат был обновлен и получил наименование GIF89А. От предыдущей версии его отличает наличие дополнительного альфа-канала для реализации эффекта прозрачности (к сожалению, не больше одной градации) и возможности хранить в одном файле несколько картинок с указанием времени показа каждой (эта особенность формата GIF89А больше всего по душе пришлась создателям анимированных рекламных баннеров).

[126] Тем не менее, формат GIF медленно, но уверенно сходит со сцены, и толчком к этому послужили требования выплаты денежных компенсаций американской компании Unisys, владеющей патентом на алгоритм сжатия данных LZW, лежащего в основе этого формата. Кроме того, невозможность отображения более чем 256 цветов тоже не способствует долголетию формата. На сегодняшний день самым вероятным его преемником видится формат PNG.

[127] PNG (Portable Network Graphics)

Формат PNG, являющийся плодом трудов сообщества независимых программистов, появился на свет как ответная реакция на переход популярнейшего формата GIF в разряд коммерческих продуктов. Этот формат, сжимающий графическую информацию без потерь качества, в отличие от GIF или TIFF сжимает растровые изображения не только по горизонтали, но и по вертикали, что обеспечивает более высокую степень сжатия и поддерживает цветные фотографические изображения вплоть до 48-битных включительно. Как недостаток формата часто упоминается то, что он не дает возможности создавать анимационные ролики, хотя сейчас, при повальном переходе практически всей анимации на технологию Flash, это уже совсем не актуально. Зато формат PNG позволяет создавать изображения с 256 уровнями прозрачности за счет применения дополнительного альфа-канала с 256 градациями серого что, безусловно, выделяет его на фоне всех существующих в данный момент форматов. В числе других отличительных особенностей этого формата можно отметить двумерную чересстрочную развертку (т.е. изображение проявляется постепенно не только по строкам, но и по столбцам) и встроенную гамма-коррекцию, позволяющую сохранять изображения, яркость которых будет неизменна не только на любых машинах PC, но и на таких альтернативных платформах, как Mac, Sun или Silicon Graphics. Так как формат создавался для Интернета, в его заголовке не предназначено место для дополнительных параметров типа разрешения, поэтому для хранения изображений, подлежащих печати, PNG плохо подходит, для этих целей лучше подойдет PSD или TIFF. Зато он хорош для публикации высококачественной растровой графики в Интернете.

[128] Но широкое распространение этого, поистине передового формата сдерживают и некоторые его недостатки. Так, формат PNG значительно уступает своему предшественнику, GIF-у, в тех случаях, когда речь идет о мелких элементах оформления веб-страниц, таких, как кнопки, рамки и т.п. Проблема заключается в том, что в файле изображения около 1 Кб занимает описание палитры цветов, что порой бывает сопоставимо с размером самого изображения.

[129] JPEG (Joint Photographic Experts Group)

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

[131] Существует разновидность формата JPEG, именуемая «прогрессивный JPEG» (p-JPEG). Прогрессивный JPEG отличается от обычного тем, что при выводе его на экран изображение появляется почти сразу, но низкого качества, а по мере загрузки качество улучшается (процесс аналогичен постепенному показу GIF). Формат JPEG не поддерживает анимацию или прозрачный цвет, и пригоден в подавляющем большинстве случаев только для публикации полноцветных изображений, типа фотографических, в интернете.

[132] TIFF (Tag Image File Format)

Формат TIFF был разработан компанией Aldus для своего графического редактора PhotoStyler. Как универсальный формат для хранения растровых изображений, TIFF достаточно широко используется, в первую очередь, в издательских системах, требующих изображения наилучшего качества. Кстати, возможность записи изображений в формате TIFF является одним из признаков высокого класса современных цифровых фотокамер. Формат поддерживает множество алгоритмов сжатия (в том числе популярные LZW, Deflate или JPEG), типов изображений от битового (1-, 2-, 4-, 8-, 24- и 32-битные изображения) и индексированных цветов до LAB, CMYK и RGB (кроме дуплексов и многоканальных документов). Со сжатием LZW файл TIFF занимает почти столько же места, сколько и GIF, только, в отличие от последнего, TIFF поддерживает полноцветные изображения и хранит в своем теле подробную информацию об изображении — разрешение, тип принтера и другие детали, необходимые для профессиональной работы с изображениями. В этом формате поддерживаются такие чисто профессиональные возможности, как обтравочные контуры, альфа-каналы, возможность сохранять несколько копий изображения с разным разрешением и даже включать в файл слои. Формат TIFF очень удобен при переносе изображений между компьютерами различных типов.

[133] PSD (Adobe Photoshop)

Формат PSD является стандартным форматом пакета Adobe Photoshop и отличается от большинства обычных растровых форматов возможностью хранения слоев (layers). Он содержит много дополнительных переменных (не уступает TIFF по их количеству) и сжимает изображения, используя алгоритм сжатия без потерь, иногда даже сильнее, чем PNG (только в тех случаях, когда размеры файла измеряются не в килобайтах, а в десятках или даже сотнях мегабайт). Формат поддерживает глубины цвета, вплоть до 16 бит на канал (48-битные цветные и 16-битные черно-белые), а также альфа-каналы, слои, контуры, прозрачность, векторные надписи и т. п. Прекрасно подойдет для переноса или хранения изображений, содержащих специфические, свойственные только Adobe Photoshop, элементы. Файлы PSD свободно читаются большинством популярных просмотрщиков, но не стоит забывать, что, открыв эти файлы в некоторых графических редакторах третьих фирм, даже декларирующих поддержку формата PSD, можно потерять значительную часть их специфических возможностей.

Дата добавления: 2014-01-05 ; Просмотров: 1500 ; Нарушение авторских прав? ;

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

1.2. Математическая модель сжатия цифровых изображений

Основу данной модели составляет декоррелирующее преобразование, подобное преобразованию Фурье, отображающему дискретную функцию двух переменных, которой является изображение, из пространственной области в частотную 115, 31, 51]. Исходная функция представляется в виде суммы элементарных функций различных частот, причем низкочастотные составляющие определяют общий вид функции, а высокочастотные — ее поведение на локальных участках.

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

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

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

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

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

Затем осуществляется построенное на основе некоторого ортогонального базиса декоррелирующее преобразование, которое независимо от используемого математического аппарата приводит к удалению пространственной избыточности, связывающей элементы исходного изображения (или преобразованного изображения, полученного после предварительной обработки), и выявлению статистической избыточности. Декоррелирующее преобразование применяется не ко всему изображению, а к некоторым его участкам равного размера, называемым блоками. Это обусловлено тем, что пространственная избыточность, присущая изображениям, является локальной: каждый пиксель коррелирует с ограниченным числом других пикселей по горизонтали и вертикали. Обычно в качестве локальной области с существенной пространственной избыточностью принимают блок изображения размером 8×8 пикселей.

Переход из пространственной области f(x, у) в частотную д(и, а) является отображением из множества целых чисел в множество вещественных чисел:

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

Рис. 1.1. Обобщенная модель сжатия цифровых изображений

после перехода к вещественным числам с меньшей точностью посредством округления до одного-двух знаков после запятой.

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

Этап округления естественно совмещается со следующим этапом, называемым квантованием, на котором и происходят основные потери информации. Квантование заключается в делении полученных частотных составляющих на некоторые коэффициенты и округлении результата [13, 65, 107]. Для этого вводится функция q(x,y), определяющая для каждого элемента преобразованного изображения коэффициент квантования

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

Последним этапом является статистическое сжатие квантованных элементов изображения. Обычно для этого используется кодирование Хаффмана 112] или арифметическое кодирование [56, 58, 106]. Значения функции дч(х,у) рассматриваются как произвольные текстовые данные, обладающие статистической избыточностью. Большое значение имеет порядок обхода матрицы, в которой представлены значения указанной функции, выбираемый таким образом, чтобы нули, получаемые в результате квантования, образовывали серии максимальной длины.

Рассмотренная обобщенная модель сжатия цифровых изображений представлена на рис. 1.1. Данная модель описывает случай сжатия с потерями, когда высокая степень сжатия может быть достигнута путем удаления из исходного изображения некоторого количества информации. Сжатие без потерь можно описать аналогичным образом, но убрав этап квантования и исключив возможность необратимых потерь информации на этапе предварительной обработки |83, 100|.

Существующие методы сжатия изображения и их перспективы использования

Секция: Технические науки

XL Студенческая международная заочная научно-практическая конференция «Молодежный научный форум: технические и математические науки»

Существующие методы сжатия изображения и их перспективы использования

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

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

Первый вид – сжатие без потерь, который основывается на снижение объема выходного потока информации без потери информационной структуры.

RLE (run-length encoding) – один из самых старых и самых простых алгоритмов архивации графики. Изображение в нем вытягивается в цепочку байт по строкам растра. Само сжатие в RLE происходит за счет того, что в исходном изображении встречаются цепочки одинаковых байт. Применим алгоритм для изображений с небольшим количеством цветов: деловую и научную графику. Применяется в форматах РСХ, TIFF, ВМР. На его принципах и комбинациях основываются более эффективные и сложные алгоритмы.

Алгоритм Лемпеля – Зива – Велча (Lempel-Ziv-Welch, LZW). Идея алгоритма LZW в том, что с входного потока последовательно считываются символы, далее в созданной таблице проверяются строки. Если данная строка имеется, то следующий символ считывается, а если строки нет, тогда в поток записывается код для предыдущей найденной строки, строка вносится в таблицу. В настоящий момент алгоритм применяют во многих известных программах сжатия данных – ZIP, ARJ, LHA, и в файлах формата TIFF, PDF, GIF, PostScript и других.

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

Илон Маск рекомендует:  DupeString - Функция Delphi

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

JPEG (Joint Photographic Expert Group) является популярным графическим форматом, который чаще всего используют для хранения фотоизображений. В целом алгоритм основан на дискретном косинусоидальном преобразовании, применяемом к матрице изображения для получения некоторой новой матрицы коэффициентов. Для получения исходного изображения используется обратное преобразование. Сжатие в JPEG производиться за счет плавного изменения цвета в изображении. JPEG обеспечивает высокий коэффициент сжатия. Бывают ситуации, в которых алгоритм создает “ореол” вокруг резких вертикальных и горизонтальных границ в изображении (эффект Гиббса). При слишком высокой степени сжатия изображение делится на блоки 8х8 пикселов. Поддерживается алгоритм JPEG в форматах Quick Time, PostScript Level 2, Tiff 6.0.

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

Следующий алгоритм JPEG 2000. Он использует технологию вейвлет-преобразования, которая основывается на представлении сигнала в виде суперпозиции базовых функций — волновых пакетов. Таким образом, изображение не только станет более четким и гладким, но и размер файла по сравнению с JPEG при таком же качестве уменьшится. Из-за применения вейвлетов, изображения в данном формате, при высоких степенях сжатия устраняются недостатки более ранней версии. JPEG-2000 применяется для цифровых охранных систем, а так же в разных алгоритмах распознавания и в биометрии. JPEG-2000 можно использовать для создания изображения глубиной цвета в 48 бит. Широкое распространение данного алгоритма способствует введению новационных технологий работы с изображениями и приложений.

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

Фрактальные методы рассматривают, как альтернативу технологиям, которые основаны на преобразовании Фурье, например, таким как JPEG.

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

Рекурсивный (волновой) алгоритм (wavelet). Данный вид архивации используется очень давно и происходит из идеи применения когерентности областей. Алгоритм ориентирован на черно-белые и цветные изображения с плавными переходами. Идеально подходит для иллюстраций типа рентгеновских снимков. Если задается слишком больший коэффициент, то на резких границах, а именно приходящихся на диагонали, появляется «лестничный эффект» – ступеньки разного размера в несколько пикселов, а также яркости. Идея алгоритма заключается в том, что мы сохраняем в файл разницу число между средними значениями соседних блоков в изображении, которая обычно принимает значения близкие к 0.

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

Сжатие изображений для веб-разработчиков

Введение

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

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

Памятка: Контрольный список по сжатию изображений

  1. Сжимайте изображения в подходящем формате в наименьшем приемлемом качестве:
    • Настройте уровень сжатия всех изображений вручную, где это возможно.
    • Автоматизируйте сжатие остальных, чтобы достичь наивысшей производительности.
  2. Рассмотрите возможность использования формата WebP для ваших изображений;
  3. Сохраняйте ваши изображения с прогрессивными настройками. Это благоприятно скажется на восприятии пользователями вашего сайта;
  4. Исследуйте другие интересные способы достичь лучшего сжатия или прозрачности. Мыслите нестандартно.

Почему важно быть маленьким

Если говорить очень упрощённо, чем больше страница, тем дольше она загружается. Проведено множество исследований, которые показывают, что пользователи медленных сайтов проводят меньше времени на сайте, меньше нажимают на ссылки и рекламные блоки, и тратят меньше денег. Маленькие сайты, такие как AutoAnything, которые вдвое сократили время загрузки сайта, отметили увеличение выручки на 13 процентов . А исследования на крупных сайтах, таких как Amazon, показали, что их выручка снижается на 1 процент на каждые 100 миллисекунд задержки загрузки .

Что может быть хуже, чем заставлять пользователей платить за загрузку вашего сайта

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

Даже так называемые « безлимитные » тарифные планы для мобильных телефонов, на самом деле таковыми не являются. Большинство из них предоставляют около 2Гб за фиксированную плату, а превышение этого лимита может тарифицироваться дополнительно. Не говоря уже о том, что есть множество мест в мире, где отсутствуют безлимитные тарифные планы и где стоимость загрузки информации является серьёзной проблемой для пользователей.

Большие изображения – большие проблемы

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

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

Виды алгоритмов сжатия

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

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

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

До После
0.123, 1.2345, 21.2165, 21.999, 12.123 0,0,20,20,10

Рис. 1 – Пример сжатия с потерей данных. Значения округляются до ближайшего числа, кратного 10. Это преобразование необратимо.

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

До После
aaaaabbbbbcccddddeeeeffffaaaaabb a5b4c2d4e4f4a5bb0

Рис. 2 – Пример сжатия без потерь. Количество символов, идущих подряд, определяется числом, после символа. Мы можем точно восстановить исходные данные. Заметьте, что если подряд идут не больше двух символов, имеет смысл просто оставить их как есть. Вы видите такой пример в конце потока в виде ‘bb’.

Форматы изображений

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

В общем случае веб-разработчику при выборе формата изображения нужно ответить на следующие вопросы:

  • Нужна ли прозрачность?
  • Нужна ли анимация?
  • Нужно ли высокое качество изображения?

‘Lena’ – распространённое изображение для оценки и сравнения алгоритмов сжатия изображений.

PNG – простой формат, поддерживающий прозрачность и сжатие без потерь. Он позволяет вам выбрать альфа-канал для вашего изображения, чтобы замаскировать прозрачные области, а также, по желанию, активировать компрессор данных Deflate .
(Deflate – это комбинация двух компрессоров: LZ77 и Кода Хаффмана ). Поскольку сжатие происходит без потерь, качество изображения остаётся идентичным исходному. Однако это порождает проблемы: размеры файлов обычно получаются раздутыми, не такими маленькими, какими они могут быть.

GIF – ещё один формат, поддерживающий прозрачность наряду с анимацией. Формат GIF содержит две стадии сжатия: этап сжатия с потерей данных или определение палитры (ограничение цветовой гаммы изображения до 256 цветов), за которым следует сжатие без потерь по алгоритму LZW . Процесс квантования цветов изображения до всего лишь 256 производит агрессивное снижение качества в пользу меньшего размера, что также хорошо влияет на сжатие на этапе LZW.

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

Если вам не нужна прозрачность или анимация, JPG – лучший формат для вас.

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

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

Конечно, новый формат пока не поддерживается всеми браузерами , поэтому веб-разработчики, которые уже внедрили его, сейчас сталкиваются с проблемами юзабилити . Несмотря на это, 30% экономия, по сравнению с JPG наряду с возможностью адаптации формата на уровне сервера доказывают, что WebP – доминирующий формат для любых сайтов, где размер изображений представляет проблему.

Сжатие Без потерь С потерями Прозрачность Анимация
PNG Хорошее Да Нет Полная Нет
GIF OK Да Да Бинарная Да
JPG Хорошее Да Да Нет Нет
WebP Отличное Да Да Полная Да

Рис. 3 – Особенности некоторых форматов, поддерживаемых браузерами.

Компромисс между качеством и размером

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

Кроме того, как показывает проект imgmin , как правило, при сжатии JPG на уровне от 75 до 100 восприятие качества изменяется незначительно:

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

Следующая таблица показывает, что на большинстве крупных веб-сайтов уровень качества колеблется около 75 практически для всех их изображений JPG:

Сайт Качество JPG
Эскизы картинок Google 74-76
Полноразмерные изображения на Facebook 85
Изображения JPEG на главной странице Yahoo 69-91
Изображения JPEG на главной странице Youtube 70-82
Изображения в Википедии 80
Фоновое изображение на Windows live 82
Изображения JPEG пользователей Twitter 30-100

Рис. 4 – Средний уровень качества JPG, используемый на крупнейших сайтах.

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

Некоторые разработчики выбрали более автоматизированный подход к этому типу кодирования, часто применяя к изображениям собственные эвристические процессы и процессы кодирования во время разработки. Этот способ обработки подходит в качестве золотой середины между настройкой и автоматизацией, которая поможет большинству веб-разработчиков. Вы можете также использовать различные приложения, например JPEGmini , которое также автоматически настроит ваш уровень сжатия JPG, чтобы получить наилучшее качество.

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

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

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

Рис. 5 – Пример растрового изображения (слева) в сравнении с векторным изображением (справа). Заметьте, что векторное изображение намного проще и менее детализировано. Это из-за того, что данный формат не предназначен для создания высококачественных изображений.

Думайте об SVG как о формате, который позволяет вам хранить «описание» изображения в очень небольшом объёме памяти и генерировать высококачественное, независимое от разрешения изображение на клиенте, вне зависимости от размера исходных данных. Одно из ограничений формата SVG заключается в том, что он может быть использован для представления только определённого вида изображений, иначе говоря, векторные изображения должны быть упрощёнными и использовать набор примитивных типов, чтобы определить, как отобразить цвета на экране.

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

Качество изображений, размер и различные разрешения экранов.

Одна из больших проблем, с которой сталкиваются разработчики – это количество пикселей монитора относительно размера создаваемых изображений. То есть, если автор создаёт изображения для настольного веб-сайта, скорее всего, размеры изображений были выбраны им для просмотра на больших настольных мониторах. Однако мобильные устройства создают проблему, так как размеры их экранов гораздо меньше и их трафик гораздо дороже. Как следствие пользователи будут загружать изображения размером больше, чем им требуется или чем они могут отобразить.

Есть несколько способов решить эту проблему.

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

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

Для тех, кто использует Node/Express, в качестве альтернативы подойдёт express-processimage, или вы можете создать скрипт, вызывающий для вас ImageMagick .

Однако, одна из пока-не-разрешённых проблем с этим подходом – найти хорошее решение для управления ростом объёма ваших данных. Что касается логики, есть надежда, что атрибут srcset решит эту проблему (движок WebKit, как вы знаете, поддерживает его, Blink намерен реализовать поддержку, FF будет его поддерживать в iOS).

А пока, можно использовать polyfill для srcset в качестве промежуточного шага.

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

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

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

Размеры изображений, восприятие пользователя и время загрузки

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

Существует два основных способа отображать изображения в сети.

  • Подождать полной загрузки изображения и отобразить его после загрузки;
  • Отобразить часть изображения, загруженную на данный момент.

Браузеры не используют первый вариант, так как это приводит к наиболее медленной загрузке страницы.

Большинство сайтов в сети построено на втором варианте. Я уверен, мы все знакомы с постепенным « разворачиванием » изображения сверху вниз. Это происходит потому, что обычно изображения хранятся в растровом порядке, иначе говоря, первые байты изображения, которые получает браузер, находятся в левом верхнем углу изображения и дальше идут по порядку горизонтально. Очевидно, что если мы храним изображение по-другому, мы можем изменить порядок передачи битов по сети, что изменит то, как изображение отображается на экране.

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

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

Линейная Прогрессивная

Рис. 6 – Пример линейной и прогрессивной загрузки изображений.

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

Использовать это свойство для ваших изображений чрезвычайно просто: Просто сохраните ваши GIF или PNG изображения с опцией « interlaced », или JPEG изображения с опцией « progressive » — и вашим пользователям начнёт нравиться время загрузки вашего веб-сайта. Хотя, стоит уточнить, что прогрессивные изображения пока не поддерживаются всеми браузерами, и загрузка прогрессивного изображения на таких платформах может на самом деле ухудшить производительность.

Нестандартные изображения

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

Разделение вашего прозрачного слоя для улучшения сжатия.

Разработчики игр под HTML5 обычно пересылают больше изображений, чем ваш обычный веб-сайт, большинство из которых – прозрачные рамки для анимации. К сожалению это вынуждает делать PNG изображения, чтобы добиться прозрачности. Однако несколько разработчиков изобрели обходные пути, чтобы получить лучшее сжатие и прозрачность изображений. Например, вы можете разделить данные по цветам и прозрачности в два разных файла изображений (например, два файла JPG), и восстановить их на клиенте, используя элемент CANVAS. Хотя это и увеличивает количество запросов в сети, экономия в размере изображения может быть существенной для разработчиков, у которых на сайте множество прозрачных изображений.

Улучшения сжатия PNG за счёт лучшей обработки.

Опция Deflate в PNG – это кодер без потерь, но это не должно останавливать вас от использования предобработки с потерей качества, если вы хотите. Инструменты обработки изображений, такие как ImageAlpha и ImageOptim , могут сжать ваше PNG изображение, используя метод с потерей данных в качестве предварительной обработки перед кодированием изображения в PNG формат. Это создаёт двухступенчатый процесс, где сжатие с потерями и без потерь осуществляются двумя разными приложениями. Результаты впечатляющие: уменьшение пространства цветов позволяет сжатию без потерь найти и обработать больше совпадений в файле, что выливается в лучшее сжатие.

После того, как вы сохранили изображение в формате PNG, можно переупаковать ваши данные PNG, используя более совершенные компрессоры, чтобы сгенерировать меньший файл PNG. Такие инструменты, как advPNG , возьмут ваш файл PNG и прогонят его через улучшенный Deflate компрессор, чтобы получить меньший файл. Или вы можете совместить PNGOUT с инструментами, вроде OptiPNG или Zopfli , чтобы добиться того же эффекта. Конечно, каждая из этих систем выдаёт немного разные результаты, в зависимости от входных данных, поэтому мудрой мыслью будет использовать систему, которая произведёт сжатие несколькими компрессорами и выберет наименьший файл. Если вам лень её создавать, ScriptPNG возьмёт на себя всю тяжёлую работу.

Не все анимации созданы равными .

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

Существует больше одного пути к отзывчивым изображениям .

Поскольку восприятие пользователя – это самый важный элемент сайта, стоит сказать, что существуют другие способы создать сайты, которые «воспринимаются» как быстрые. Недавно BBC изменили подход к обработке отзывчивых изображений. Их метод позволяет клиенту загрузить сначала маленькое изображение (чтобы создать видимость картинки), а затем получать изображения в высоком разрешении с помощью ленивой загрузки при необходимости. Вы можете найти более детальное описание этого способа, а также версию с открытым кодом , чтобы попробовать её на вашем сайте.

Заключение

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

  1. Сжимайте изображения в подходящем формате в наименьшем приемлемом качестве:
    • Настройте уровень сжатия всех изображений вручную, где это возможно
    • Автоматизируйте сжатие остальных, чтобы достичь наивысшей производительности
  2. Рассмотрите возможность использования формата WebP для ваших изображений;
  3. Сохраняйте ваши изображения с прогрессивными настройками. Это благоприятно скажется на восприятии пользователями вашего сайта;
  4. Исследуйте другие интересные способы достичь лучшего сжатия или прозрачности. Мыслите нестандартно.
  • ImageAlpha
  • ImageOptim
  • advPNG
  • ImageAlpha w/ Canvas Helper Library
  • Interactive tool for testing progressive images

Данная публикация представляет собой перевод статьи « Image Compression for Web Developers » , подготовленной дружной командой проекта Интернет-технологии.ру

Это интересно!

Увеличение ресурсов сети

В статье рассмотрены методы расширения спектра и виды уплотнения доступа. Рассказывается об основных особенностях и преимуществах каждого подхода.

Управление ориентацией поля в электроприводах

Метод управления ориентацией поля в электроприводах с регулированием скорости вращения улучшает динамические параметры, позволяет выбрать оптимальный электродвигатель и улучшить эффективность системы. В статье описаны базовые принципы метода, построение схемы управления и применение цифровых сигнальных контроллеров для эффективной реализации системы. Статья представляет собой перевод [1].

Основы теории демодулирующих логарифмических усилителей

Подробно рассматриваются принципы и особенности функционирования демодулирующих логарифмических усилителей. Описываются особенности популярного среди разработчиков усилителя AD8307. Очерчен круг применения логарифмических усилителей.

Илон Маск рекомендует:  Плюсы и минусы моноблока и что это вообще такое

1 сентября

Форматы сжатия данных

В статье рассматриваются основные методы сжатия данных, приводится классификация наиболее известных алгоритмов, и на простых примерах обсуждаются механизмы работы методов CS&Q, RLE-кодирования, Хаффмана, LZW, дельта-кодирования, JPEG и MPEG. Статья представляет собой авторизованный перевод [1].

ередача данных и их хранение стоят определенных денег. Чем с большим количеством информации приходится иметь дело, тем дороже обходится ее хранение и передача. Зачастую данные хранятся в наиболее простом виде, например в коде ASCII (American Standard Code for Information Interchange — американский стандартный код для обмена информацией) текстового редактора, в исполняемом на компьютере двоичном коде, в отдельных файлах, полученных от систем сбора данных и т.д. Как правило, при использовании этих простых методов кодирования объем файлов данных примерно в два раза превышает действительно необходимый размер для представления информации. Ее сжатие с помощью алгоритмов и программ позволяет решить эту задачу. Программа сжатия используется для преобразования данных из простого формата в оптимизированный по компактности. Наоборот, программа распаковки возвращает данные в исходный вид. Мы обсудим шесть методов сжатия данных в этом разделе. Первые три из них являются простыми методами кодирования: кодирование длин серий с передачей информации об их начале и длительности; кодирование Хаффмана и дельта-кодирование. Последние три метода являются сложными процедурами сжатия данных, которые стали промышленными стандартами: LZW, форматы JPEG и MPEG.

Методы сжатия данных

В таблице 1 показаны два разных способа распределения алгоритмов сжатия по категориям. К категории (а) относятся методы, определяемые как процедуры сжатия без потерь и с потерями. При использовании метода сжатия без потерь восстановленные данные идентичны исходным. Этот метод применяется для обработки многих типов данных, например для исполняемого кода, текстовых файлов, табличных данных и т.д. При этом не допускается потеря ни одного бита информации. В то же время файлы данных, представляющие изображения и другие полученные сигналы, нет необходимости хранить и передавать без потерь. Любой электрический сигнал содержит шум . Если изменения в этих сигналах схожи с небольшим количеством дополнительного шума, вреда не наносится. Алгоритм, применение которого приводит к некоторому ухудшение параметров сигнала, называется сжатием с потерями. Методы сжатия с потерями намного эффективнее методов кодирования без потерь. Чем выше коэффициент сжатия, тем больше шума добавляется в данные.

Табл. 1. Классификация методов сжатия: без потерь и с потерями

Передаваемые по интернету изображения служат наглядным примером того, почему необходимо сжатие данных. Предположим, что требуется загрузить из интернета цифровую цветную фотографию с помощью 33,6-Кбит/с модема. Если изображение не сжато (например, это файл TIFF-формата), его объем составит около 600 Кбайт. При сжатии фото без потерь (в файл GIF-формата) его размер уменьшится примерно до 300 Кбайт. Метод сжатия с потерями ( JPEG-формат ) позволит уменьшить размер файла до 50 Кбайт. Время загрузки этих трех файлов составляет 142, 72 и 12 с, соответственно. Это большая разница. JPEG идеально подходит для работы с цифровыми фотографиями, тогда как GIF используется только для рисованных изображений.

Второй способ классификации методов сжатия данных проиллюстрирован в таблице 2. Большинство программ сжатия работает с группами данных, которые берутся из исходного файла, сжимаются и записываются в выходной файл. Например, одним из таких методов является CS&Q (Coarser Sampling and Quantization — неточные выборка и дискретизация). Предположим, что сжимается цифровой сигнал, например звуковой сигнал, который оцифрован с разрядностью 12 бит. Можно прочесть две смежные выборки из исходного файла (24 бит), отбросить одну выборку полностью, отбросить наименее значащие 4 бита из другой выборки, затем записать оставшиеся 8 битов в выходной файл. При 24 входных битах и 8 выходных коэффициент сжатия алгоритма с потерями равен 3:1. Этот метод высокоэффективен при использовании сжатия с преобразованием , составляющего основу алгоритма JPEG.

Табл. 2. Классификация методов сжатия: фиксированный и переменный размер группы

В методе CS&Q из входящего файла читается фиксированное число битов, и меньшее фиксированное число записывается в выходной файл. Другие методы сжатия позволяют создавать переменное число битов для чтения или записи. Причина того, почему в таблицу не вошли форматы JPEG и MPEG, в том, что это составные алгоритмы, в которых совмещено множество других методов.

RLE-кодирование

Файлы данных содержат одни и те же символы, повторяющиеся множество раз в одном ряду. Например, в текстовых файлах используются пробелы для разделения предложений, отступы, таблицы и т.д. Цифровые сигналы также содержат одинаковые величины, указывающие на то, что сигнал не претерпевает изменений. Например, изображение ночного неба может содержать длинные серии символов, представляющих темный фон, а цифровая музыка может иметь длинную серию нулей между песнями. RLE-кодирование (Run-length encoding — кодирование по длинам серий) представляет собой метод сжатия таких типов файлов.
На рисунке 1 проиллюстрирован принцип этого кодирования для последовательности данных с частым повторением серии нулей. Всякий раз, когда нуль встречается во входных данных, в выходной файл записываются два значения: нуль, указывающий на начало кодирования, и число нулей в серии. Если среднее значение длины серии больше двух, происходит сжатие. С другой стороны, множество одиночных нулей в данных может привести к тому, что кодированный файл окажется больше исходного.

Рис. 1. Пример RLE-кодирования


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

Кодирование Хаффмана

Этот метод был разработан Хаф­фманом в 1950-х гг. Метод основан на использовании относительной частоты встречаемости индивидуальных элементов. Часто встречающиеся элементы кодируются более короткой последовательностью битов. На рисунке 2 представлена гистограмма байтовых величин большого файла ASCII. Более 96% этого файла состоит из 31 символа: букв в нижнем регистре, пробела, запятой, точки и символа возврата каретки.

Алгоритм, назначающий каждому из этих стандартных символов пятибитный двоичный код по схеме 00000 = a, 00001 = b, 00010 = c и т.д., позволяет 96% этого файла уменьшить на 5/8 объема. Последняя комбинация 11111 будет указывать на то, что передаваемый символ не входит в группу из 31 стандартного символа. Следующие восемь битов в этом файле указывают, что представляет собой символ в соотоветствии со стандартом присвоения ASCII. Итак, 4% символов во входном файле требуют для представления 5 + 8 = 13 бит.

Принцип этого алгоритма заключается в присвоении часто употребляемым символам меньшего числа битов, а редко встречающимся символам — большего количества битов. В данном примере среднее число битов, требуемых из расчета на исходный символ, равно 0,96 . 5 + 0,04 . 13 = 5,32. Другими словами, суммарный коэффициент сжатия составляет 8 бит/5,32 бит, или 1,5 : 1.

Рис. 2. Гистограмма значений ASCII фрагмента текста из этой статьи


На рисунке 3 представлена упрощенная схема кодирования Хаффмана. В таблице кодирования указана вероятность употребления символов с A по G, имеющихся в исходной последовательности данных, и их соответствия. Коды переменной длины сортируются в стандартные восьмибитовые группы. При распаковке данных все группы выстраиваются в последовательность нулей и единиц, что позволяет разделять поток данных без помощи маркеров. Обрабатывая поток данных, программа распаковки формирует достоверный код, а затем переходит к следующему символу. Такой способ формирования кода обеспечивает однозначное чтение данных.

Рис. 3. Пример кодирования Хаффмана

Дельта-кодирование

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

Рис. 4. Пример дельта-кодирования

Дельта-кодирование используется для сжатия данных, если значения исходного файла изменяются плавно , т.е. разность между следующими друг за другом величинами невелика. Это условие не выполняется для текста ASCII и исполняемого кода, но является общим случаем, когда информация поступает в виде сигнала . Например, на рисунке 5а показан фрагмент аудиосигнала, оцифрованного с разрядностью 8 бит, причем все выборки принимают значения в диапазоне –127–127. На рисунке 5б представлен кодированный вариант этого сигнала, основное отличие которого от исходного сигнала заключается в меньшей амплитуде . Другими словами, дельта-кодирование увеличивает вероятность того, что каждое значение выборки находится вблизи нуля, а вероятность того, что оно значительно больше этой величины, невелика. С неравномерным распределением вероятности работает метод Хаффмана. Если исходный сигнал не меняется или меняется линейно, в результате дельта-кодирования появятся серии выборок с одинаковыми значениями, с которыми работает RLE-алгоритм. Таким образом, в стандартном методе сжатия файлов используется дельта-кодирование с последующим применением метода Хаффмана или RLE-кодирования.

Рис. 5. Пример дельта-кодирования


Механизм дельта-кодирования можно расширить до более полного метода под названием кодирование с линейным предсказанием (Linear Predictive Coding, LPC).
Чтобы понять суть этого метода, представим, что уже были закодированы первые 99 выборок из входного сигнала и необходимо произвести выборку под номером 100. Мы задаемся вопросом о том, каково наиболее вероятное ее значение? В дельта-кодировании ответом на данный вопрос является предположение, что это значение предыдущей, 99-й выборки. Это ожидаемое значение используется как опорная величина при кодировании выборки 100. Таким образом, разность между значением выборки и ожиданием помещается в кодируемый файл. Метод LPC устанавливает наиболее вероятную величину на основе нескольких последних выборок. В используемых при этом алгоритмах применяется z-преобразование и другие математические методы.

Алгоритм LZW

LZW-сжатие — наиболее универсальный метод сжатия данных, получивший распространение благодаря своей простоте и гибкости. Этот алгоритм назван по имени его создателей (Lempel-Ziv-Welch encoding — сжатие данных методом Лемпела-Зива-Велча). Исходный метод сжатия Lempel-Ziv был впервые заявлен в 1977 г., а усовершенствованный Велчем вариант — в 1984 г. Метод позволяет сжимать текст, исполняемый код и схожие файлы данных примерно вполовину. LZW также хорошо работает с избыточными данными, например табличными числами, компьютерным исходным текстом и принятыми сигналами. В этих случаях типичными значениями коэффициента сжатия являются 5:1. LZW-сжатие всегда используется для обработки файлов изображения в формате GIF и предлагается в качестве опции для форматов TIFF и PostScript.
Алгоритм LZW использует кодовую таблицу, пример которой представлен на рисунке 6. Как правило, в таблице указываются 4096 элементов. При этом кодированные LZW-данные полностью состоят из 12-битных кодов, каждый из которых соответствует одному табличному элементу. Распаковка выполняется путем извлечения каждого кода из сжатого файла и его преобразования с помощью таблицы. Табличные коды 0—255 всегда назначаются единичным байтам входного файла (стандартному набору символов). Например, если используются только эти первые 256 кодов, каждый байт исходного файла преобразуется в 12 бит сжатого LZW-файла, который на 50% больше исходного. При распаковке этот 12-битный код преобразуется с помощью кодовой таблицы в единичные байты.

Пример кодовой таблицы

Рис. 6. Пример сжатия в соответствии с таблицей кодирования

Метод LZW сжимает данные с помощью кодов 256—4095, представляя последовательности байтов. Например, код 523 может представлять последовательность из трех байтов: 231 124 234. Всякий раз, когда алгоритм сжатия обнаруживает последовательность во входном файле, в кодируемый файл ставится код 523. При распаковке код 523 преобразуется с помощью таблицы в исходную последовательность из трех байтов. Чем длиннее последовательность, назначаемая единичному коду и чем чаще она повторяется, тем больше коэффициент сжатия.
Существуют два основных препятствия при использовании этого метода сжатия: 1) как определить, какие последовательности должны указываться в кодовой таблице и 2) как обеспечить программу распаковки той же таблицей, которую использует программа сжатия. Алгоритм LZW позволяет решить эти задачи.

Когда программа LZW начинает кодировать файл, таблица содержит лишь первые 256 элементов — остальная ее часть пуста. Это значит, что первые коды, поступающие в сжимаемый файл, представляют собой единичные байты исходного файла, преобразуемые в 12-бит группы. По мере продолжения кодирования LZW-алгоритм определяет повторяющиеся последовательности данных и добавляет их в кодовую таблицу. Сжатие начинается, когда последовательность обнаруживается вторично. Суть метода в том, что последовательность из входящего файла не добавляется в кодовую таблицу, если она уже была помещена в сжатый файл как отдельный символ (коды 0—255). Это важное условие, поскольку оно позволяет программе распаковки восстановить кодовую таблицу непосредственно из сжатых данных, не нуждаясь в ее отдельной передаче.

Из множества алгоритмов сжатия с потерями кодирование с преобразованием оказалось наиболее востребованным. Наилучший пример такого метода — популярный стандарт JPEG (Joint Photographers Experts Group — Объединенная группа экспертов по машинной обработке фотографических изображений). Рассмотрим на примере JPEG работу алгоритма сжатия с потерями.

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

Сжатие с преобразованием основано на простом условии: в трансформированном сигнале (например, с помощью преобразования Фурье) полученные значения данных не несут прежней информационной нагрузки. В частности, низкочастотные компоненты сигнала начинают играть более важную роль, чем высокочастотные компоненты. Удаление 50% битов из высокочастотных компонентов может привести, например, к удалению лишь 5% закодированной информации.

Из рисунка 7 видно, что JPEG-сжатие начинается путем разбиения изображения на группы размером 8×8 пикселов. Полный алгоритм JPEG работате с широким рядом битов на пиксел, включая информацию о цвете. В этом примере каждый пиксел является единичным байтом, градацией серого в диапазоне 0—255. Эти группы 8×8 пикселов обрабатываются при сжатии независимо друг от друга. Это значит, что каждая группа сначала представляется 64 байтами. Вслед за преобразованием и удалением данных каждая группа представляется, например, 2—20 байтами. При распаковке сжатого файла требуется такое же количество байтов для аппроксимации исходной группы 8×8. Эти аппроксимированные группы затем объединяются, воссоздавая несжатое изображение. Почему используются группы размерами 8×8, а не 16×16? Такое группирование было основано исходя из максимального возможного размера, с которым работали микросхемы на момент разработки стандарта.

Рис. 7. Пример применения метода сжатия JPEG. Три группы 8?8, показанные в увеличенном виде, представляют значения отдельных пикселов

Для реализации методов сжатия было исследовано множество различных преобразований. Например, преобразование Karhunen-Loeve обеспечивает наиболее высокий коэффициент сжатия, но оно трудно осуществляется. Метод преобразования Фурье реализуется гораздо проще, но он не обеспечивает достаточно хорошего сжатия. В конце концов, выбор был сделан в пользу разновидности метода Фурье — дискретного косинусного преобразования (Discrete Cosine Transform — DCT).

На примере работы алгоритма JPEG видно, как несколько схем сжатия объединяются, обеспечивая большую эффективность. Вся процедура сжатия JPEG состоит из следующих этапов:
– изображение разбивается на группы 8×8;
– каждая группа преобразуется с помощью преобразования DCT;
– каждый спектральный элемент 8×8 сжимается путем сокращения числа битов и удаления некоторых компонентов с помощью таблицы квантования ;
– видоизмененный спектр преобразуется из массива 8×8 в линейную последовательность, все высокочастотные компоненты которой помещаются в ее конец;
– серии нулей сжимаются с помощью метода RLE;
– последовательность кодируется либо методом Хаффмана, либо арифметическим методом для получения сжатого файла.

MPEG (Moving Pictures Experts Group — Экспертная группа по кинематографии) — стандарт сжатия цифровых видеоданных. Этот алгоритм обеспечивает также сжатие звуковой дорожки к видеофильму. MPEG представляет собой еще более сложный, чем JPEG, стандарт с огромным потенциалом. Можно сказать, это ключевая технология XXI века.
У MPEG имеется несколько очень важных особенностей. Так например, он позволяет воспроизводить видеофильм в прямом и обратном направлениях, в режиме нормальной и повышенной скорости. К кодированной информации имеется прямой доступ , т.е. каждый отдельный кадр последовательности отображается как неподвижное изображение. Таким образом, фильм редактируется — можно кодировать его короткие фрагменты, не используя всю последовательность в качестве опорной. MPEG также устойчив к ошибкам, что позволяет избегать цифровых ошибок, приводящих к нежелательному прерыванию воспроизведения.

Используемый в этом стандарте метод можно классифицировать по двум типам сжатия: внутрикадровое и межкадровое . При сжатии по первому типу отдельные кадры, составляющие видеопоследовательность, кодируются так, как если бы они были неподвижными изображениями. Такое сжатие выполняется с помощью JPEG-стандарта с несколькими вариациями. В терминологии MPEG кадр, закодированный таким образом, называется внутрикодированным, или I-picture.

Наибольшая часть пикселов в видеопоследовательности изменяется незначительно от кадра к кадру. Если камера не движется, наибольшая часть изображения состоит из фона, который не меняется на протяжении некоторого количества кадров. MPEG использует это обстоятельство, сжимая избыточную информацию между кадрами с помощью дельта-кодирования. После сжатия одного из кадров в виде I-picture последующие кадры кодируются как изображения с предсказанием, или P-pictures , т.е. кодируются только изменившиеся пикселы, т.к. кадры I-picture включены в P-picture.

Эти две схемы сжатия составляют основу MPEG, тогда как практическая реализация данного метода намного сложнее описанной. Например, кадры P-picture могут использовать изображение I-picture как опорное, которое претерпело изменение при перемещении объектов в последовательности изображений. Существуют также двунаправленные предиктивно-кодированные изображения, или B-pictures. Эти видеокадры формируются способом предсказания «вперед» и «назад» на основе I-picture. При этом обрабатываются участки изображения, которые постепенно меняются на протяжении множества кадров. Отдельные кадры также хранятся без соблюдения последовательности в сжатых данных, чтобы облегчить упорядочение изображений I-, P- и B-pictures. Наличие цвета и звука еще больше усложняет реализацию этого алгоритма.

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

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

Опрос

Новички

Контекстное моделирование

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

Пожалуй, наиболее простой способ оценки реализуется с помощью по­луадаптивного моделирования и заключается в предварительном подсчете безусловной частоты появления символов в сжимаемом блоке. Полученное распределение вероятностей используется для статистического кодирования всех символов блока. Если, например, такую модель применить для сжатия текста на русском языке, то в среднем на кодирование каждого символа бу­дет потрачено примерно 4.5 бита. Это значение является средней длиной кодов для модели, базирующейся на использовании безусловного распределения вероятностей букв в тексте. Заметим, что уже в этом простом случае достигается степень сжатия 1.5 по отношению к тривиальному кодированию, когда всем символам назначаются коды одинаковой длины. Действительно, размер алфавита русского текста превышает 64 знака, но меньше 128 знаков (строчные и заглавные буквы, знаки препинания, пробел), что требует 7-битовых кодов.

Анализ распространенных типов данных, — например, тех же текстов на естественных языках, — выявляет сильную зависимость вероятности появ­ления символов от непосредственно им предшествующих. Иначе говоря, большая часть данных, с которыми мы сталкиваемся, порождается источни­ками с памятью. Допустим, нам известно, что сжимаемый блок является текстом на русском языке. Если, например, строка из трех только что обра­ботанных символов равна «_цы» (подчеркиванием здесь и далее обозначает­ся пробел), то текущий символ скорее всего входит в следующую группу: «г» («цыган»), «к» («цыкать»), «п» («цыпочки»), «ц» («цыц»). Или, в случае анализа фазу нескольких слов, если предыдущая строка равна «Вста-вай,_проклятьем_заклейменный,», то продолжением явно будет «весь_мир_». Следовательно, учет зависимости частоты появления символа (в общем случае — блока символов) от предыдущих должен давать более точные оценки и в конечном счете лучшее сжатие. Действительно, в случае посим­вольного кодирования при использовании информации об одном непосред­ственно предшествующем символе достигается средняя длина кодов в 3.6 бита для русских текстов, при учете двух последних — уже порядка 3.2 бита. В первом случае моделируются условные распределения вероятностей сим­волов, зависящие от значения строки из одного непосредственно предшест­вующего символа, во втором — зависящие от строки из двух предшествую­щих символов.

Любопытно, что модели, оперирующие безусловными частотами и часто­тами в зависимости от одного предшествующего символа, дают примерно оди­наковые результаты для всех европейских языков (за исключением, быть мо­жет, самых экзотических) -4.5 и 3.6 бита соответственно.

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

Под контекстным моделированием будем понимать оценку вероятности появления символа (элемента, пиксела, сэмпла, отсчета и даже набора каче­ственно разных объектов) в зависимости от непосредственно ему предшест­вующих, или контекста.

Заметим, что в быту понятие «контекст» обычно используется в глобаль­ном значении — как совокупность символов (элементов), окружающих те­кущий обрабатываемый. Это контекст в широком смысле. Выделяют также «левосторонние» и «правосторонние» контексты, т. е. последовательности символов, непосредственно примыкающих к текущему символу слева и справа соответственно. Здесь и далее под контекстом будем понимать именно классический левосторонний: так, например, для последнего симво­ла «о» последовательности «. молоко. » контекстом является «. молок».

Если длина контекста ограничена, то такой подход будем называть кон­текстным моделированием ограниченного порядка (finite-context modeling), при этом под порядком понимается максимальная длина используемых кон­текстов N. Например, при моделировании порядка 3 для последнего симво­ла «о» в последовательности «. молоко. » контекстом максимальной длины 3 является строка «лок». При сжатии этого символа под «текущими контек­стами» могут пониматься «лок», «ок», «к», а также пустая строка «». Все эти контексты длины от N до 0 назовем активными контекстами в том смысле, что при оценке символа может быть использована накопленная для них сть тистика.

Далее вместо «контекст длины о, о N , где q — размер алфавита обрабатываемой последовательности. КМ(0) и КМ(-1) всегда ак­тивны.

Заметим, что часто не делается различий между понятиями «контекст» и «контекстная модель». Авторы этой книги такое соглашение не поддержи­вают.

Часто говорят о «родительских» и «дочерних» контекстах. Для контекста «к» дочерними являются «ок» и «лк», поскольку они образованы сцеплением (конкатенацией) одного символа и контекста «к». Аналогично для контекста «лок» родительским является контекст «ок», а контекстами-предками — «ок», «к», «». Очевидно, что «пустой» контекст «» является предком для всех. Ана­логичные термины применяются для КМ, соответствующих контекстам.

Совокупность КМ образует модель источника данных. Под порядком модели понимается максимальный порядок используемых КМ.

ВИДЫ КОНТЕКСТНОГО МОДЕЛИРОВАНИЯ

Пример обработки строки «абсабвбабс» иллюстрирует сразу две пробле­мы контекстного моделирования:

■ как выбирать подходящий контекст (или контексты) среди активных с целью получения более точной оценки, ведь текущий символ может лучше предсказываться не контекстом 2-го порядка «аб», а контекстом 1-го порядка «б»;

■ как оценивать вероятность символов, имеющих нулевую частоту (на­пример, «г»).

Выше были приведены цифры, в соответствии с которыми при увеличе­нии длины используемого контекста сжатие данных улучшается. К сожале­нию, при кодировании блоков типичной длины — одного или нескольких мегабайтов и меньше — это справедливо только для небольших порядков модели, так как статистика для длинных контекстов медленно накапливает­ся. При этом также следует учитывать, что большинство реальных данных характеризуется неоднородностью, нестабильностью силы и вида статисти­ческих взаимосвязей, поэтому «старая» статистика контекстно-зависимых частот появления символов малополезна или даже вредна. Поэтому модели, строящие оценку только на основании информации КМ максимального по­рядка N, обеспечивают сравнительно низкую точность предсказания. Кроме того, хранение модели большого порядка требует много памяти.

Если в модели используются для оценки только КМ(ЛО, то иногда такой подход называют «чистым» (pure) контекстным моделированием порядка N. Из-за вышеуказанного недостатка «чистые» модели представляют обычно только научный интерес.

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

Рассмотрим модель произвольного порядка N. Если q(si\o) есть вероят­ность, присваиваемая в активной КМ(о) символу j, алфавита сжимаемого потока, то смешанная вероятность q(si) вычисляется в общем случае как

где w(o) — вес оценки КМ(о).

Оценка q(Sj\o) обычно определяется через частоту символа s,- по триви­альной формуле

rnfiJ[si\o) — частота появления символа st в соответствующем контексте по­рядка о; До) — общая частота появления соответствующего контекста поряд­ка о в обработанной последовательности.

Заметим, что правильнее было бы писать не, скажем, Ду/|о), иДз^С^), т. е. «частота появления символа S/ в КМ порядка о с номером До)», по­скольку контекстных моделей порядка о может быть огромное количество. Но при сжатии каждого текущего символа мы рассматриваем только одну КМ для каждого порядка, так как контекст определяется непосредственно примыкающей слева к символу строкой определенной длины. Иначе говоря, для каждого символа мы имеем набор из N+1 активных контекстов длины от N до 0, каждому из которых однозначно соответствует только одна КМ, если она вообще есть. Поэтому здесь и далее используется сокращенная за­пись.

Если вес w(-l) > 0, то это гарантирует успешность кодирования любого символа входного потока, так как наличие КМ(-1) позволяет всегда получать ненулевую оценку вероятности и, соответственно, код конечной длины.

Различают модели с полным смешиванием (fully blended), когда предска­зание определяется статистикой КМ всех используемых порядков, и с час­тичным смешиванием (partially blended) — в противном случае.

Рассмотрим процесс оценки отмеченного на рисунке стрелкой символа

«л», встретившегося в блоке «молочноемолоко». Считаем, что модель рабо­тает на уровне символов.

Понравилась статья? Поделиться с друзьями:
Кодинг, CSS и SQL