Алгоритм сжатия файлов следующих форматов bmp gif jpeg
Сжатие файлов позволяет быстрее передавать, получать и хранить большие файлы. Оно используется повсеместно и наверняка хорошая вам знакомо: самые популярные расширения сжатых файлов — ZIP, JPEG и MP3. В этой статье кратко рассмотрим основные виды сжатия файлов и принципы их работы.
Что такое сжатие?
Сжатие файла — это уменьшение его размера при сохранении исходных данных. В этом случае файл занимает меньше места на устройстве, что также облегчает его хранение и передачу через интернет или другим способом. Важно отметить, что сжатие не безгранично и обычно делится на два основных типа: с потерями и без потерь. Рассмотрим каждый из них по отдельности.
Сжатие с потерями
Такой способ уменьшает размер файла, удаляя ненужные биты информации. Чаще всего встречается в форматах изображений, видео и аудио, где нет необходимости в идеальном представлении исходного медиа. MP3 и JPEG — два популярных примера. Но сжатие с потерями не совсем подходит для файлов, где важна вся информация. Например, в текстовом файле или электронной таблице оно приведёт к искажённому выводу.
MP3 содержит не всю аудиоинформацию из оригинальной записи. Этот формат исключает некоторые звуки, которые люди не слышат. Вы заметите, что они пропали, только на профессиональном оборудовании с очень высоким качеством звука, поэтому для обычного использования удаление этой информации позволит уменьшить размер файла практически без недостатков.
Аналогично файлы JPEG удаляют некритичные части изображений. Например, в изображении с голубым небом сжатие JPEG может изменить все пиксели на один или два оттенка синего вместо десятков.
Чем сильнее вы сжимаете файл, тем заметнее становится снижение качества. Вы, вероятно, замечали такое, слушая некачественную музыку в формате MP3, загруженную на YouTube. Например, сравните музыкальный трек высокого качества с сильно сжатой версией той же песни.
Сжатие с потерями подходит, когда файл содержит больше информации, чем нужно для ваших целей. Например, у вас есть огромный файл с исходным (RAW) изображением. Целесообразно сохранить это качество для печати изображения на большом баннере, но загружать исходный файл в Facebook будет бессмысленно. Картинка содержит множество данных, не заметных при просмотре в социальных сетях. Сжатие картинки в высококачественный JPEG исключает некоторую информацию, но изображение выглядит почти как оригинал.
При сохранении в формате с потерями, вы зачастую можете установить уровень качества. Например, у многих графических редакторов есть ползунок для выбора качества JPEG от 0 до 100. Экономия на уровне 90 или 80 процентов приводит к небольшому уменьшению размера файла с незначительной визуальной разницей. Но сохранение в плохом качестве или повторное сохранение одного и того же файла в формате с потерями ухудшит его.
Посмотрите на этот пример.
Оригинальное изображение, загруженное с Pixabay в формате JPEG. 874 КБ:
Результат сохранения в формате JPEG с 50-процентным качеством. Выглядит не так уж плохо. Вы можете заметить артефакты по краям коробок только при увеличении. 310 КБ:
Исходное изображение, сохранённое в формате JPEG с 10-процентным качеством. Выглядит ужасно. 100 КБ:
Где используется сжатие с потерями
Как мы уже упоминали, сжатие с потерями отлично подходит для большинства медиафайлов. Это крайне важно для таких компаний как Spotify и Netflix, которые постоянно транслируют большие объёмы информации. Максимальное уменьшение размера файла при сохранении качества делает их работу более эффективной.
Сжатие без потерь
Сжатие без потерь позволяет уменьшить размер файла так, чтобы в дальнейшем можно было восстановить первоначальное качество. В отличие от сжатия с потерями, этот способ не удаляет никакую информацию. Рассмотрим простой пример. На картинке ниже стопка из 10 кирпичей: два синих, пять жёлтых и три красных.
Вместо того чтобы показывать все 10 блоков, мы можем удалить все кирпичи одного цвета, кроме одного. Используя цифры, чтобы показать, сколько кирпичей каждого цвета было, мы представляем те же данные используя гораздо меньше кирпичей — три вместо десяти.
Это простая иллюстрация того, как осуществить сжатие без потерь. Та же информация сохраняется более эффективным способом. Рассмотрим реальный файл: mmmmmuuuuuuuoooooooooooo. Его можно сжать до гораздо более короткой формы: m5u7o12. Это позволяет использовать 7 символов вместо 24 для представления одних и тех же данных.
Где используется сжатие без потерь
ZIP-файлы — популярный пример сжатия без потерь. Хранить информацию в виде ZIP-файлов более эффективно, при этом когда вы распаковываете архив, там присутствует вся оригинальная информация. Это актуально для исполняемых файлов, так как после сжатия с потерями распакованная версия будет повреждена и непригодна для использования.
Другие распространённые форматы без потерь — PNG для изображений и FLAC для аудио. Форматы видео без потерь встречаются редко, потому что они занимают много места.
Сжатие с потерями vs сжатие без потерь
Теперь, когда мы рассмотрели обе формы сжатия файлов, может возникнуть вопрос, когда и какую следует использовать. Здесь всё зависит от того, для чего вы используете файлы.
Скажем, вы только что откопали свою старую коллекцию компакт-дисков и хотите оцифровать её. Когда вы копируете свои компакт-диски, имеет смысл использовать формат FLAC, формат без потерь. Это позволяет получить мастер-копию на компьютере, которая обладает тем же качеством звука, что и оригинальный компакт-диск.
Позже вы, возможно, захотите загрузить музыку на телефон или старый MP3-плеер. Здесь не так важно, чтобы музыка была в идеальном качестве, поэтому вы можете конвертировать файлы FLAC в MP3. Это даст вам аудиофайл, который по-прежнему достаточно хорош для прослушивания, но не занимает много места на мобильном устройстве. Качество MP3, преобразованного из FLAC, будет таким же, как если бы вы создали сжатый MP3 с оригинального CD.
Тип данных, представленных в файле, также может определять, какой вид сжатия подходит больше. В PNG используется сжатие без потерь, поэтому его хорошо использовать для изображений, в которых много однотонного пространства. Например, для скриншотов. Но PNG занимает гораздо больше места, когда картинка состоит из смеси множества цветов, как в случае с фотографиями. В этом случае с точки зрения размера файлов лучше использовать JPEG.
Проблемы во время сжатия файлов
Бесполезно конвертировать формат с потерями в формат без потерь. Это пустая трата пространства. Скажем, у вас есть MP3-файл весом в 3 МБ. Преобразование его в FLAC может привести к увеличению размера до 30 МБ. Но эти 30 МБ содержат только те звуки, которые имел уже сжатый MP3. Качество звука от этого не улучшится, но объём станет больше.
Также стоит иметь в виду, что преобразовывая один формат с потерями в аналогичный, вы получаете дальнейшее снижение качества. Каждый раз, когда вы применяете сжатие с потерями, вы теряете больше деталей. Это становится всё более и более заметно, пока файл по существу не будет разрушен. Помните также, что форматы с потерями удаляют некоторые данные и их невозможно восстановить.
Заключение
Мы рассмотрели как сжатие файлов с потерями, так и без потерь, чтобы увидеть, как они работают. Теперь вы знаете, как можно уменьшить размер файла и как выбрать лучший способ для этого.
Алгоритмы, которые определяют, какие данные выбрасываются в методах с потерями и как лучше хранить избыточные данные при сжатии без потерь, намного сложнее, чем описано здесь. На эту тему можно почитать больше информации здесь, если вам интересно.
Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.
Словарные алгоритмы
Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:
Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.
В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.
Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c — это один символ, а S — строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.
Алгоритмы статистического кодирования
Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.
Алгоритм Хаффмана
- Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
- Выбираются два свободных узла дерева с наименьшими весами
- Создается их родитель с весом, равным их суммарному весу
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой — бит 0
- Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Арифметическое кодирование
Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал [0;1) на N непересекающихся полуинтервалов. Каждый полуинтервал соответствует элементам ai, при этом длина полуинтервала пропорциональна частоте pi.
Кодирующая дробь строится следующим образом: строится система вложенных интервалов так, чтобы каждый последующий полуинтервал занимал в предыдущем место, соответствующее положению элемента в исходном разбиении. После того, как все интервалы вложены друг в друга можно взять любое число из получившегося полуинтервала. Запись этого числа в двоичном коде и будет представлять собой сжатый код.
Декодирование – расшифровка дроби по известному распределению вероятностей. Очевидно, что для декодирования необходимо хранить таблицу частот.
Арифметическое кодирование чрезвычайно эффективно. Коды, получаемые с его помощью, приближаются к теоретическому пределу. Это позволяет утверждать, что по мере истечения сроков патентов, арифметическое кодирование будет становиться всё более и более популярным.
Алгоритмы сжатия с потерями
Не смотря на множество весьма эффективных алгоритмов сжатия без потерь, становится очевидно, что эти алгоритмы не обеспечивают (и не могут обеспечить) достаточной степени сжатия.
Сжатие с потерями (применительно к изображениям) основывается на особенностях человеческого зрения. Мы рассмотрим основные идеи, лежащие в основе алгоритма сжатия изображений JPEG.
Алгоритм сжатия JPEG
JPEG на данный момент один из самых распространенных способов сжатия изображений с потерями. Опишем основные шаги, лежащие в основе этого алгоритма. Будем считать, что на вход алгоритма сжатия поступает изображение с глубиной цвета 24 бита на пиксел (изображение представлено в цветовой модели RGB).
Перевод в цветовое пространство YCbCr
В цветовой модели YCbCr мы представляем изображение в виде яркостной компоненты (Y) и двух цветоразностных компонент (Cb,Cr). Человеческий глаз более восприимчив к яркости, а не к цвету, поэтому алгоритм JPEG вносит по возможности минимальные изменения в яркостную компоненту (Y), а в цветоразностные компоненты могут вноситься значительные изменения. Перевод осуществляется по следующей формуле:
Выбор Kr и Kb зависит от оборудования. Обычно берётся Kb=0.114;Kr=0.299. В последнее время также используется Kb=0.0722;Kr=0.2126, что лучше отражает характеристики современных устройств отображения.
Субдискретизация компонент цветности
- :4:4 – отсутствует субдискретизация;
- 4:2:2 – компоненты цветности меняются через одну по горизонтали;
- 4:2:0 – компоненты цветности меняются через одну строку по горизонтали, при этом по вертикали они меняются через строку.
Дискретное косинусное преобразование
Изображение разбивается на компоненты 8*8 пикселов, к каждой компоненте применятся ДКП. Это приводит к уплотнению энергии в коде. Преобразования применяются к компонентам независимо.
Квантование
Человек практически не способен замечать изменения в высокочастотных составляющих, поэтому коэффициенты, отвечающие за высокие частоты можно хранить с меньшей точностью. Для этого используется покомпонентное умножение (и округление) матриц, полученных в результате ДКП, на матрицу квантования. На данном этапе тоже можно регулировать степень сжатия (чем ближе к нулю компоненты матрицы квантования, тем меньше будет диапазон итоговой матрицы).
Зигзаг-обход матриц
Зигзаг-обход матрицы – это специальное направление обхода, представленное на рисунке:
При этом для большинства реальных изображений в начале будут идти ненулевые коэффициенты, а ближе к концу будут идти нули.
RLE- кодировние
Используется особый вид RLE-кодирования: выводятся пары чисел, причём первое число в паре кодирует количество нулей, а второе – значение после последовательности нулей. Т.е. код для последовательности 0 0 15 42 0 0 0 44 будет следующим (2;15)(0;42)(3;44).
Кодирование методом Хаффмана
Используется описанный выше алгоритм Хаффмана. При кодировании используется заранее определённая таблица.
Алгоритм декодирования заключается в обращении выполненных преобразований.
К достоинствам алгоритма можно отнести высокую степень сжатие (5 и более раз), относительно невысокая сложность (с учётом специальных процессорных инструкций), патентная чистота. Недостаток – артефакты, заметные для человеческого глаза.
История
Иерархия алгоритмов:
Хотя сжатие данных получило широкое распространение вместе с интернетом и после изобретения алгоритмов Лемпелем и Зивом (алгоритмы LZ), можно привести несколько более ранних примеров сжатия. Морзе, изобретая свой код в 1838 году, разумно назначил самым часто используемым буквам в английском языке, “e” и “t”, самые короткие последовательности (точка и тире соотв.). Вскоре после появления мейнфреймов в 1949 году был придуман алгоритм Шеннона — Фано, который назначал символам в блоке данных коды, основываясь на вероятности их появления в блоке. Вероятность появления символа в блоке была обратно пропорциональна длине кода, что позволяло сжать представление данных.
Дэвид Хаффман был студентом в классе у Роберта Фано и в качестве учебной работы выбрал поиск улучшенного метода бинарного кодирования данных. В результате ему удалось улучшить алгоритм Шеннона-Фано.
Ранние версии алгоритмов Шеннона-Фано и Хаффмана использовали заранее определённые коды. Позже для этого стали использовать коды, созданные динамически на основе данных, предназначаемых для сжатия. В 1977 году Лемпель и Зив опубликовали свой алгоритм LZ77, основанный на использования динамически создаваемого словаря (его ещё называют «скользящим окном»). В 78 году они опубликовали алгоритм LZ78, который сначала парсит данные и создаёт словарь, вместо того, чтобы создавать его динамически.
Проблемы с правами
Алгоритмы LZ77 и LZ78 получили большую популярность и вызвали волну улучшателей, из которых до наших дней дожили DEFLATE, LZMA и LZX. Большинство популярных алгоритмов основаны на LZ77, потому что производный от LZ78 алгоритм LZW был запатентован компанией Unisys в 1984 году, после чего они начали троллить всех и каждого, включая даже случаи использования изображений в формате GIF. В это время на UNIX использовали вариацию алгоритма LZW под названием LZC, и из-за проблем с правами их использование пришлось сворачивать. Предпочтение отдали алгоритму DEFLATE (gzip) и преобразованию Барроуза — Уилера, BWT (bzip2). Что было и к лучшему, так как эти алгоритмы почти всегда превосходят по сжатию LZW.
К 2003 году срок патента истёк, но поезд уже ушёл и алгоритм LZW сохранился, пожалуй, только в файлах GIF. Доминирующими являются алгоритмы на основе LZ77.
В 1993 году была ещё одна битва патентов – когда компания Stac Electronics обнаружила, что разработанный ею алгоритм LZS используется компанией Microsoft в программе для сжатия дисков, поставлявшейся с MS-DOS 6.0. Stac Electronics подала в суд и им удалось выиграть дело, в результате чего они получили более $100 миллионов.
Рост популярности Deflate
К сожалению Фил Катц не дожил до триумфа DEFLATE, он умер от алкоголизма в 2000 году в возрасте 37 лет. Граждане – чрезмерное употребление алкоголя опасно для вашего здоровья! Вы можете не дожить до своего триумфа!
Современные архиваторы
ZIP царствовал безраздельно до середины 90-х, однако в 1993 году простой русский гений Евгений Рошал придумал свой формат и алгоритм RAR. Последние его версии основаны на алгоритмах PPM и LZSS. Сейчас ZIP, пожалуй, самый распространённый из форматов, RAR – до недавнего времени был стандартом для распространения различного малолегального контента через интернет (благодаря увеличению пропускной способности всё чаще файлы распространяются без архивации), а 7zip используется как формат с наилучшим сжатием при приемлемом времени работы. В мире UNIX используется связка tar + gzip (gzip — архиватор, а tar объединяет несколько файлов в один, т.к. gzip этого не умеет).
Прим. перев. Лично я, кроме перечисленных, сталкивался ещё с архиватором ARJ (Archived by Robert Jung), который был популярен в 90-х в эру BBS. Он поддерживал многотомные архивы, и так же, как после него RAR, использовался для распространения игр и прочего вареза. Ещё был архиватор HA от Harri Hirvola, который использовал сжатие HSC (не нашёл внятных объяснений — только «модель ограниченного контекста и арифметическое кодирование»), который хорошо справлялся со сжатием длинных текстовых файлов.
В 1996 году появился вариант алгоритма BWT с открытыми исходниками bzip2, и быстро приобрёл популярность. В 1999 году появилась программа 7-zip с форматом 7z. По сжатию она соперничает с RAR, её преимуществом является открытость, а также возможность выбора между алгоритмами bzip2, LZMA, LZMA2 и PPMd.
В 2002 году появился ещё один архиватор, PAQ. Автор Мэтт Махоуни использовал улучшенную версию алгоритма PPM с использованием техники под названием «контекстное смешивание». Она позволяет использовать больше одной статистической модели, чтобы улучшить предсказание по частоте появления символов.
Будущее алгоритмов сжатия
Конечно, бог его знает, но судя по всему, алгоритм PAQ набирает популярность благодаря очень хорошей степени сжатия (хотя и работает он очень медленно). Но благодаря увеличению быстродействия компьютеров скорость работы становится менее критичной.
С другой стороны, алгоритм Лемпеля-Зива –Маркова LZMA представляет собой компромисс между скоростью и степенью сжатия и может породить много интересных ответвлений.
Ещё одна интересная технология «substring enumeration» или CSE, которая пока мало используется в программах.
В следующей части мы рассмотрим техническую сторону упомянутых алгоритмов и принципы их работы.
Фотографии и картинки отличаются друг от друга не только по содержанию, но и по другим «компьютерным» характеристикам. Например, по размеру.
Бывает так, что, вроде бы, два одинаковых рисунка, но у одного размер в три раза больше, чем у другого.
Также изображения отличаются по качеству. Думаю, Вам не раз встречались фото крайне плохого качества. Это видно невооруженным глазом. Например, две одинаковые фотографии, но одна лучшего качества, а другая - худшего.
А бывает так, что рисунку как будто не хватает красок. Вот пример.
И за все это отвечает формат или тип файла.
Вообще-то изображения бывают самых разных форматов. И существует их очень и очень много. Мы не будем рассматривать их все, а поговорим про самые распространенные. Это такие форматы, как bmp, gif, jpg, png, tiff .
Отличаются он друг от друга, в первую очередь, качеством. А качество отличается по количеству (насыщенности) цветов.
Например, я рисую картину, используя разные цвета. И тут вдруг часть из них закончилась, и приходится дорисовывать тем, что есть. Я, конечно, постараюсь сделать всё возможное, чтобы это не сильно отразилось на результате, но все равно картина получится не такая, как хотелось бы - более блеклая, размытая.
Вот так и с форматами изображений. Какой-то оставляет все цвета, другой же обрезает часть. И, бывает, из-за этого картинка портится.
Это довольно грубый пример. На самом деле, там все несколько сложнее, но, думаю, главное Вы уловили.
Распространенные форматы изображений
BMP - формат рисунков, сделанных в программе Paint. Его можно использовать для хранения нарисованных картинок на компьютере. Но вот в Интернете такой тип файлов не используется из-за большого объема. Так что если Вы хотите опубликовать картинку, нарисованную в Paint, в блоге или социальной сети, она должна быть другого типа - gif, jpg или png.
GIF - популярный формат картинок в Интернете. В нем можно сохранять их без потери качества, но с ограниченным количеством цветов - 256. Особую популярность gif получил благодаря тому, что в нем можно создать небольшие анимированные (движущиеся) картинки.
JPG - формат фотографий и картин с большим количеством цветов. В нем можно сохранить изображение как без потери качества, так и с потерей.
PNG - современный формат рисунков. Изображение такого типа получается небольшого размера и без потери качества. Очень удобно: и файл маленький, и качество хорошее. А еще он поддерживает прозрачность.
TIFF - изображения очень хорошего качества, без сжатия.Соответственно, и размер у таких файлов огромный. TIFF используют тогда, когда качество имеет большое значение. Например, при создании визиток, буклетов, журнальных обложек.
Какой формат выбрать
- BMP - если это рисунок, сделанный в программе Paint, и Вы собираетесь держать его только в компьютере.
- GIF - если анимация или рисунок с небольшим количеством цветов для публикации в Интернете.
- PNG - если это рисунок, в котором много цветов или есть какие-то прозрачные части.
- JPG (jpeg) - если фотография.
- TIFF - изображение для полиграфии (визитки, буклеты, плакаты и т.д.).
Сегодня профессиональные фотоаппараты способны выдавать фотоснимки потрясающего качества, но для хранения необработанных снимков потребуется огромное количество дискового пространства. Именно поэтому специалистами всего мира не один год разрабатываются специальные алгоритмы, позволяющие сжимать растровые изображения до разумных пределов. У всех существующих на сегодня алгоритмов в основе заложены немного различные способы оптимизации итогового размера файла. Все разработанные алгоритмы сжатия изображений можно разделить на два больших вида: алгоритм без потери качества изображения и алгоритмы с потерей качества.
Алгоритмы сжатия изображений без потерь качества в основе своей имеют задачу поиска повторяющихся элементов внутри массива данных и замену их на эквивалентную информацию, но занимающую меньший объем данных. Данные алгоритмы применяются к каждому используемому цветовому компоненту (например, в цветовой схеме RGB алгоритм будет применяться к каждому используемому цвету). Распространение таких алгоритмов объясняется тем, что каждый отдельный элемент в цифровом снимке отличается от близстоящего гораздо меньше, нежели в итоговом изображении, что дает на выходе хорошие результаты по уменьшению размера фотографий.
RLE (Run Length Encoding - кодирование длин серий) - самый простейший алгоритм сжатия, в котором обработчик отслеживает последовательность одинаковых байт и меняет ее на пару "длина серии - значение байта". Например, серию байт в файле 55555555 алгоритм заменяет на пару 85. Данная технология очень хорошо применяется в тех файлах, где присутствуют большие области, залитые одним цветом (блок-схемы, диаграммы). Сегодня данный алгоритм используется для предварительной обработки в таких форматах, как BMP, PCX, TIFF, JPEG.
LZW (Lempel-Ziv-Welch) - авторы данного алгоритма заложили в основу технологии ведение специального словаря повторяющихся цепочек битов. В отличие от RLE байты здесь не должны повторяться? учитывается лишь последовательность. При нахождении последовательности цепочка помещается в специальный словарь, а на ее место кодировщик проставляет код данной цепочки из словаря. Соответственно, итоговый файл преобразования содержит в себе словарь, коды, указывающие на элементы словаря, и неповторяющиеся элементы. Сегодня алгоритм используется в форматах цифровых файлов: GIF, PNG, TIFF.
Кодирование Хоффмана - разработчик в данном случае также использует кодирование повторяющихся данных, где для кодирования более повторяющихся цепочек используются коды меньшей длины, нежели для более редких цепочек. Словарь кодов при этом является двоичным деревом, где редко встречающиеся повторяющиеся последовательности находятся дальше от корня дерева. Здесь номера веток от корня до самой цепочки и составляют код последовательности. Данный алгоритм сегодня практически не используется в чистом виде, но применяется в файлах JPEG, PNG.
Алгоритмы сжатия изображений с потерей качества - в процессе сжатия файла часть информации отбрасывается, чем достигается большая степень сжатия. Однако разработчикам необходимо решать важный вопрос: какая именно отброшена информация не повлияет на результат.
JPEG - разработка "Группы экспертов в области фотографии" для изображений с 24-битной цветовой глубиной. Сегодня это почти стандарт полноцветных изображений. Технология использует дискретное косинусное преобразование (DCT), применяемой к матрице изображения размеров 8х8 для получения некоторой новой матрицы коэффициентов. Само кодирование проходит в четыре этапа.
На первом этапе идет выборка (sampling), где цветовые данные преобразуются в модель YCbCr. Затем выполняется прореживающая выборка (down-sampling), где компоненты цветности (Cb, Cr) снижаются в качестве, так как для глаза человека эти потери наиболее несущественны.
На втором этапе происходит DCT, где изображение разбивается на матричные блоки 8х8 для последующего преобразования.
Третьим этапом в алгоритме является квантование (quantization), где из изображения удаляются последние элементы матрицы DCT, которые влияют на конечный результат изображения в наименьшей степени. Оставшиеся коэффициенты DCT колируются по методу Хоффмана.
Описанный алгоритм применяется повсеместно, за исключением кодирования простых рисунков, где глаз человека видит четкие переходы от одного цвета к другому. В таких изображениях при использовании алгоритма сжатия JPEG пользователь получит на границах перехода эффект Гиббса (размазанные границы с грязным ореолом).
Фрактальный алгоритм - метод, использующий отличный от остальных алгоритмов способ сжатия. Здесь за основу взято нахождение на изображении подобных областей, которые затем кодируются особым способом. При этом подобие элементов ищется в квадратных областях с ограниченным использованием поворотов на определенный угол. Данный метод является очень ресурсоемким, но позволяет получить отличные результаты по соотношению качество/объем файла. Применяется метод в полноцветных изображениях формата FIF.
Рекурсивное волновое преобразование - данный алгоритм сжатия использует обработку фильтрами (низко- и высокочастотным) по строкам и столбцам с последующей операцией прореживания. Суть метода заключается в том, что при сжатии фильтр в виде небольшой области сканирует изображение. Значения цветовых элементов (пикселей), попавших в фильтр, умножаются на определенные коэффициенты, а значения суммируются. Далее фильтр сканирует следующую область изображения. В итоге на выходе из изображения размером XY получается четыре размером в половину первоначального. Первая картинка здесь - уменьшенное исходное изображение, а другие - картины наибольших разностей между пикселями по горизонтали, вертикали и диагонали. Далее все изображения подвергаются квантованию, где все коэффициенты, близкие к значению 0, отбрасываются. Данный метод позволяет преобразовывать не отдельные блоки имеющегося рисунка (как в алгоритме JPEG), а целые картинки, что позволяет получать более качественные изображения на выходе. Волновой метод нашел свое применение сегодня в формате файлов JPEG-2000.
Рассмотренные алгоритмы сегодня позволяют пользователю выбрать из широкого спектра представленных форматов наиболее выгодный, но в этой области есть и ряд препятствий. Во-первых, новые технологии сжатия требуют больших вычислительных мощностей и времени на обработку, что критично для портативных аппаратов (фотокамеры). В связи с этим, не прекращается работа экспертов по оптимизации уже разработанных алгоритмов и внедрению аппаратных средств компрессии изображений.
Легко подсчитать, что несжатое полноцветное изображение, размером 2000*1000 пикселов будет иметь размер около 6 мегабайт. Если говорить об изображениях, получаемых с профессиональных камер или сканеров высокого разрешения, то их размер может быть ещё больше. Не смотря на быстрый рост ёмкости устройств хранения, по-прежнему весьма актуальными остаются различные алгоритмы сжатия изображений.
Все существующие алгоритмы можно разделить на два больших класса:
- Алгоритмы сжатия без потерь;
- Алгоритмы сжатия с потерями.
Алгоритмы сжатия без потерь
Алгоритм RLE
Все алгоритмы серии RLE основаны на очень простой идее: повторяющиеся группы элементов заменяются на пару (количество повторов, повторяющийся элемент). Рассмотрим этот алгоритм на примере последовательности бит. В этой последовательности будут чередовать группы нулей и единиц. Причём в группах зачастую будет более одного элемента. Тогда последовательности 11111 000000 11111111 00 будет соответствовать следующий набор чисел 5 6 8 2. Эти числа обозначают количество повторений (отсчёт начинается с единиц), но эти числа тоже необходимо кодировать. Будем считать, что число повторений лежит в пределах от 0 до 7 (т.е. нам хватит 3 бит для кодирования числа повторов). Тогда рассмотренная выше последовательность кодируется следующей последовательностью чисел 5 6 7 0 1 2. Легко подсчитать, что для кодирования исходной последовательности требуется 21 бит, а в сжатом по методу RLE виде эта последовательность занимает 18 бит.
Хоть этот алгоритм и очень прост, но эффективность его сравнительно низка. Более того, в некоторых случаях применение этого алгоритма приводит не к уменьшению, а к увеличению длины последовательности. Для примера рассмотрим следующую последовательность 111 0000 11111111 00. Соответствующая ей RL-последовательность выглядит так: 3 4 7 0 1 2. Длина исходной последовательности – 17 бит, длина сжатой последовательности – 18 бит.
Этот алгоритм наиболее эффективен для чёрно-белых изображений. Также он часто используется, как один из промежуточных этапов сжатия более сложных алгоритмов.
Словарные алгоритмы
Идея, лежащая в основе словарных алгоритмов, заключается в том, что происходит кодирование цепочек элементов исходной последовательности. При этом кодировании используется специальный словарь, который получается на основе исходной последовательности.
Существует целое семейство словарных алгоритмов, но мы рассмотрим наиболее распространённый алгоритм LZW, названный в честь его разработчиков Лепеля, Зива и Уэлча.
Словарь в этом алгоритме представляет собой таблицу, которая заполняется цепочками кодирования по мере работы алгоритма. При декодировании сжатого кода словарь восстанавливается автоматически, поэтому нет необходимости передавать словарь вместе с сжатым кодом.
Словарь инициализируется всеми одноэлементными цепочками, т.е. первые строки словаря представляют собой алфавит, в котором мы производим кодирование. При сжатии происходит поиск наиболее длинной цепочки уже записанной в словарь. Каждый раз, когда встречается цепочка, ещё не записанная в словарь, она добавляется туда, при этом выводится сжатый код, соответствующий уже записанной в словаре цепочки. В теории на размер словаря не накладывается никаких ограничений, но на практике есть смысл этот размер ограничивать, так как со временем начинаются встречаться цепочки, которые больше в тексте не встречаются. Кроме того, при увеличении размеры таблицы вдвое мы должны выделять лишний бит для хранения сжатых кодов. Для того чтобы не допускать таких ситуаций, вводится специальный код, символизирующий инициализацию таблицы всеми одноэлементными цепочками.
Рассмотрим пример сжатия алгоритмом. Будем сжимать строку кукушкакукушонкукупилакапюшон. Предположим, что словарь будет вмещать 32 позиции, а значит, каждый его код будет занимать 5 бит. Изначально словарь заполнен следующим образом:
Эта таблица есть, как и на стороне того, кто сжимает информацию, так и на стороне того, кто распаковывает. Сейчас мы рассмотрим процесс сжатия.
В таблице представлен процесс заполнения словаря. Легко подсчитать, что полученный сжатый код занимает 105 бит, а исходный текст (при условии, что на кодирование одного символа мы тратим 4 бита) занимает 116 бит.
По сути, процесс декодирования сводится к прямой расшифровке кодов, при этом важно, чтобы таблица была инициализирована также, как и при кодировании. Теперь рассмотрим алгоритм декодирования.
Строку, добавленную в словарь на i-ом шаге мы можем полностью определить только на i+1. Очевидно, что i-ая строка должна заканчиваться на первый символ i+1 строки. Т.о. мы только что разобрались, как можно восстанавливать словарь. Некоторый интерес представляет ситуация, когда кодируется последовательность вида cScSc, где c - это один символ, а S - строка, причём слово cS уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.
Алгоритмы статистического кодирования
Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.
Алгоритм Хаффмана
- Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
- Выбираются два свободных узла дерева с наименьшими весами
- Создается их родитель с весом, равным их суммарному весу
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0
- Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Арифметическое кодирование
Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.
Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал ,"es":["6mXZvupymQA"],"pt":["UGdJom2ju4s","ajncQV0z3qY","UGdJom2ju4s","DOWOVOmgTLk","akl2DUlj9cw"],"fr":["iWImoHl0t9k"],"pl":["cWN28dMK0T0","XtT7ZEnVrbY"],"la":["Of6EBLVYKwA"],"el":>
Вам известна разница между JPEG, GIF, PNG и другими графическими форматами? Когда нужно использовать тот или иной формат, или какой лучше всего подойдет для сохранения фотографий? Ниже вы найдете ответы на все эти вопросы.
Алгоритмы сжатия данных с потерями / без потерь
Прежде всего, нужно понимать разницу между алгоритмами сжатия данных с потерями и без потерь. Сжатие без потерь – метод компрессии изображения, при котором сохраняется его качество вне зависимости от того, сколько раз файл был сжат и восстановлен.
Формат файлов, содержащий необработанную информацию, поступающую напрямую с матрицы полупрофессиональной и профессиональной фотокамер. Эти файлы не обрабатываются процессором камеры и содержат всю отснятую информацию в «сыром» виде. Размер таких файлов может превышать 25 МБ. Файлы RAW отлично подойдут для редактирования, однако из-за большого размера хранить их не слишком удобно.
.JPEG (JPG)
Это, пожалуй, самый распространенный графический формат. Обычно он используется для публикации в интернете фотографий и изображений с текстом. JPEG является TrueColor-форматом, то есть может хранить изображения с глубиной цвета 24 бит/пиксель. Данный формат может отображать более 16 млн цветов.
Свою популярность JPEG заслужил гибкой возможностью сжатия данных. Если нужно, изображение можно сохранить с высоким качеством. При использовании алгоритма сжатия с потерями, с каждым сохранением файла происходит потеря качества изображения. Ниже продемонстрированы изображения в формате JPEG с высоким, средним и низким качеством.
JPEG с высоким качеством (100). Размер 113 КБ
JPEG со средним качеством (50). Размер 59 КБ
JPEG с низким качеством (20). Размер 27 КБ
Формат GIF (Graphics Interchange Format) не радует глубиной цвета (8 бит). Он может хранить сжатые без потери данных изображения в формате не более 256 цветов. Одной из особенностей GIF является поддержка анимации.
ПО ТЕМЕ:
Данный формат был разработан в качестве замены GIF. Расшифровывается PNG как Portable Network Graphics. В отличии от GIF, у PNG есть поддержка градаций прозрачности за счет дополнительного альфа-канала. Обычно на прозрачность указывает шахматный фон, как видно из расположенного ниже изображения.
Внешне файлы в формате PNG практически не отличаются от JPG-изображений. PNG сжимает данные без потерь. Если для вас важна прозрачность, лучше выбирать именно этот формат.
Данная аббревиатура расшифровывается как Tagged Image File Format. Это высококачественный формат, использующийся для хранения изображений с большой глубиной цвета. Файлы TIFF могут храниться как в сжатом, так и в распакованном виде. Большим достоинством формата остается поддержка практически любого алгоритма сжатия.
Изображение в TIFF не будет терять в качестве после каждого сохранения файла. Но, к сожалению, именно из-за этого TIFF-файлы весят в разы больше JPG и GIF.
Формат BMP (bitmap) один из первых графических форматов и в настоящее время не слишком популярен. BMP хранит изображения с глубиной цвета до 64 бит. Данный формат поддерживает прозрачность, однако он не читается некотороми приложениями Microsoft. Иными словами, файлы BMP лучше конвертировать в другие форматы.
Так какой же формат следует использовать?
Оптимальным выбором будет формат PNG. Он отлично подойдет для изображений большого размера. Если требуется большая степень сжатия, например, для отправки фото по электронной почте, лучше воспользоваться JPEG. Формат TIFF достаточно сложен для работы и практически не поддерживается в браузерах.
Ниже опубликована сравнительная таблица характеристик различных форматов.
Читайте также: