Сжатие с потерями и минимизация потерь

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

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

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

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

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

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

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

Дополнительная информация о сжатии с потерями приведена в разделе "Сжатие JPEG".

Упаковка пикселей

Упаковка пикселей не может считаться методом сжатия, однако она позволяет эффективно хранить данные в смежных байтах памяти. Большинство растровых форматов применяют упаковку пикселей для сохранения объема памяти или диска, требуемого для записи растра. Если вы когда-нибудь работали с данными изображения, содержащими 4 бита на пиксель, то вам, вероятно, показалось удобным, что каждый пиксель хранится в отдельном байте памяти, поскольку байт обычно является наименьшим адресуемым элементом памяти в большинстве компью­терных систем. Однако вы не могли не обратить внимания на то, что при таком методе половина каждого байта не используется (см. рис. 9.1, а). Данные изображения, состоящие из 4096 четырехбитовых пикселей, требуют для своего хранения 4096 байтов памяти, половина из которых расходуется напрасно.

Чтобы сэкономить память, можно применить упаковку пикселей, что позволит записывать два 4-битовых пикселя в один байт (см. рис. 9.1, б). Теперь размер памяти, требуемой для хранения изображения из 4096 четырехбитовых пикселей, уменьшится с 4096 до 2048 байтов, т.е. понадобится только половина занимаемой ранее памяти.

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

За сжатие всегда нужно платить. В данном случае платой является время, затрачиваемое на распаковку каждого байта в два 4-битовых пикселя. При распаковке данных изображения могут появиться и другие проблемы: для размещения и обработки данных нужны буферы, требуется выполнять процессорные операции, вести "бухгалтерию" строк развертки. Если вы пишете программу чтения файла, то у вас нет выбора — вы должны поддерживать все схемы сжатия, определенные спецификацией данного формата. Однако если вы создаете программу записи файла, то вам следует оценивать все плюсы и минусы записи файла в сжатом виде.

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

Групповое кодирование (RLE)

Групповое кодирование — алгоритм сжатия данных, поддерживаемый большинством растровых файловых форматов, таких как TIFF, BMP и PCX. Алгоритм RLE позволяет сжимать данные любых типов, невзирая на содержащуюся в них информацию. Однако сама информация влияет на полноту сжатия. Хотя большинство алгоритмов RLE не могут достигать высокой степени сжатия, характерной для наиболее совершенных алгоритмов сжатия, но групповое кодирование легко и быстро выполняется, являясь хорошей альтернативой применению сложных алгоритмов сжатия или отказу от использования таковых вообще.

RLE уменьшает физический размер повторяющихся строк символов. Такие повторяющиеся строки, называемые группами, обычно кодируются в двух байтах. Первый байт определяет количество символов в группе и называется счетчиком группы. На практике закодированная группа может содержать от 1 до 128 или 256 символов, что часто записывается в счетчик группы в виде: количество символов минус единица (значения в диапазоне от 0 до 127 или 255). Второй байт содержит значение символа в группе, которое находится в диапазоне от 0 до 255 и называется значением группы.

Несжатая символьная группа из 15 символов А обычно занимает 15 байтов:

ААААААААААААААА

После RLE-кодирования та же строка займет всего два байта:

15А

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

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

AAAAAAbbbXXXXXt

Применив групповое кодирование, мы сможем сжать ее в четыре 2-байтовых пакета:

6A3b5X1t

Таким образом, в результате группового кодирования 15-байтовая строка станет занимать только 8 байтов. В данном случае групповое кодирование позволило получить степень сжатия, примерно равную 2:1.

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

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

Xtmprsqzntwifb

После RLE-кодирования эта строка будет иметь вид:

1X1t1m1p1r1s1q1z1n1t1w1l1f1b

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