Фотографии и картинки отличаются друг от друга не только по содержанию, но и по другим «компьютерным» характеристикам. Например, по размеру.
Бывает так, что, вроде бы, два одинаковых рисунка, но у одного размер в три раза больше, чем у другого.
Также изображения отличаются по качеству. Думаю, Вам не раз встречались фото крайне плохого качества. Это видно невооруженным глазом. Например, две одинаковые фотографии, но одна лучшего качества, а другая - худшего.
А бывает так, что рисунку как будто не хватает красок. Вот пример.
И за все это отвечает формат или тип файла.
Вообще-то изображения бывают самых разных форматов. И существует их очень и очень много. Мы не будем рассматривать их все, а поговорим про самые распространенные. Это такие форматы, как 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 уже есть в словаре. На первый взгляд может показаться, что декодер не сможет разрешить такую ситуацию, но на самом деле все строки такого типа всегда должны заканчиваться на тот же символ, на который они начинаются.
Алгоритмы статистического кодирования
Алгоритмы этой серии ставят наиболее частым элементам последовательностей наиболее короткий сжатый код. Т.е. последовательности одинаковой длины кодируются сжатыми кодами различной длины. Причём, чем чаще встречается последовательность, тем короче, соответствующий ей сжатый код.Алгоритм Хаффмана
Алгоритм Хаффмана позволяет строить префиксные коды. Можно рассматривать префиксные коды как пути на двоичном дереве: прохождение от узла к его левому сыну соответствует 0 в коде, а к правому сыну – 1. Если мы пометим листья дерева кодируемыми символами, то получим представление префиксного кода в виде двоичного дерева.Опишем алгоритм построения дерева Хаффмана и получения кодов Хаффмана.
- Символы входного алфавита образуют список свободных узлов. Каждый лист имеет вес, который равен частоте появления символа
- Выбираются два свободных узла дерева с наименьшими весами
- Создается их родитель с весом, равным их суммарному весу
- Родитель добавляется в список свободных узлов, а двое его детей удаляются из этого списка
- Одной дуге, выходящей из родителя, ставится в соответствие бит 1, другой - бит 0
- Шаги, начиная со второго, повторяются до тех пор, пока в списке свободных узлов не останется только один свободный узел. Он и будет считаться корнем дерева.
Арифметическое кодирование
Алгоритмы арифметического кодирования кодируют цепочки элементов в дробь. При этом учитывается распределение частот элементов. На данный момент алгоритмы арифметического кодирования защищены патентами, поэтому мы рассмотрим только основную идею.Пусть наш алфавит состоит из N символов a1,…,aN, а частоты их появления p1,…,pN соответственно. Разобьем полуинтервал ,"es":["6mXZvupymQA"],"pt":["UGdJom2ju4s","ajncQV0z3qY","UGdJom2ju4s","DOWOVOmgTLk","akl2DUlj9cw"],"fr":["iWImoHl0t9k"],"pl":["cWN28dMK0T0","XtT7ZEnVrbY"],"la":["Of6EBLVYKwA"],"el":}
