6. Сжатие с потерями на примере изображений
Курс “Теория информации и кодирования”

Подходы к сжатию информации с потерями
Сжатие по блочному алгоритму JPEG
Сжатие по волновому алгоритму JPEG
Фрактальное сжатие изображений
Метод MPEG сжатия видеопотока

6.1 Подходы к сжатию информации с потерями

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

Причины этого отображены на рисунке:
  • эти виды сообщений предъявляют высокие требования к каналам передачи (особенно, с учетом высокого траффика). Например, хранение минуты несжатого видео даже при относительно скромном разрешении 800х600 требует около 2Гбайт памяти;
  • универсальные методы сжатия, используемые, например, в архиваторах, не обеспечивают радикального уменьшения их объема. Например, исходный растровый файл (формат .bmp) при архивировании уменьшается лишь в 2-4 раза;
  • в силу особенно особенностей человеческого зрения и слуха определенные потери качества (например, снижение четкости изображения или урезание частотного состава звука) воспринимаются как приемлемые. Например, фотография, сжатая каким-либо из современных методов в 10-15 раз на глаз мало отличается от исходного варианта.

В данной лекции мы детально рассмотрим методы сжатия изображений.

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

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

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

6.2 Сжатие по блочному алгоритму JPEG

Первым по времени создания и наиболее распространенным стандартом сжатия растровых изображений является блочный метод JPEG.

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

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


На первом этапе выполняются:
  • переход к цветоразностной модели;
  • разделение изображения на блоки;
  • «прореживание» блоков цветовых составляющих.


а) Переход к цветоразностной модели означает преобразование значений базовых цветовых составляющих R G B к тройке составляющих Y U V, где Y — яркость, U - хроматические красный, V - хроматические синий.
Пересчет выполняется по приведенным на рисунке формулам. Разумеется, возможно и обратное преобразование.

б) Изображение разделяется на блоки 8х8 пикселей. При этом описание каждого блока можно представить тремя матрицами чисел (от 0 до 255), которые отвечают компонентам Y, U, V. При необходимости четверки соседних блоков объединяются в макроблоки 16х16.

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

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

Формально при этом коэффициенты pxy исходной матрицы P преобразуется в коэффициенты dij матрицы D согласно приведенной здесь формуле.

Смысл преобразования заключается в том, что коэффициенты dij отражают «амплитуду колебаний» яркости пикселей. Например, если все пиксели блока имеют одинаковую яркость, то максимальными будет коэффициент d11 , а остальные dij = 0.

Чем больше деталей в изображении, тем большими окажутся значения “удаленных” коэффициентов. При этом, огрубляя коэффициенты матрицы, находящиеся ближе к ее правому нижнему углу, мы будем воздействовать именно на мелкие детали изображения. Визуально это проявится в "размывании" внутри блоков (как это показано на верхнем рисунке).

Порядок следования коэффициентов dij в соответствии с увеличением частоты ("змейкой" от левого верхнего к нижнему правому углу) показан на рисунке.

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

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

Чем больше степень сжатия, тем большими задаются делители. В практическом алгоритме они увеличиваются в направлении правого нижнего угла матрицы D. В результате этой операции строка из 64 коэффициентов матрицы содержит длинные последовательности «0» и удобна для окончательного сжатия.

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

6.3 Сжатие по волновому алгоритму JPEG

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

Пример применения метода показан а рисунке. Усреднение яркостей соседних пикселей визуально проявляется как «размывание» деталей, причем результирующее изображение уменьшается в 4 раза (1). Отклонения визуально напоминают тени на барельефе (2,3).

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

По сравнению с более ранним «блочным» методом JPEG волновой метод дает в целом лучшие результаты по сжатию (типовые значения коэффициента сжатия от 10 до 50). Это связано с особенностями зрения, которое более лояльно воспринимает «размытость» изображения, чем его «мозаичность». Вместе с тем, недостатком JPEG-2000 продолжает оставаться относительно низкая скорость обработки изображения (особенно — при сжатии).

Основная процедура сжатия включает следующие шаги.

Шаг 1. Для исходных яркостей четверок соседних пикселей выполняется расчет по формулам на рисунке

Шаг 2. Из средних значений яркости b1ij строится новый растр изображения (рис. — зона 1 справа вверху).

Шаг 3. Значения b2ij и b3ij сохраняются в компактной форме для использования при восстановлении изображения («тени» в зонах 2 и 3 справа и внизу).

Шаг 4. «Диагональные» значения b4ij не сохраняются, поскольку не оказывают существенного влияния на изображение при его восстановлении (зона 4 на рисунке).

Сжатие изображения достигается за счет следующего:
- полуразности b2ij и b3ij значительно меньше, чем исходные коэффициенты a i j и для их хранения необходимо меньше разрядов. Кроме того, коэффициент b4ij не сохраняется вовсе. Таким образом, даже в отсутствие потерь информации достигается сжатие изображения;
- для сжатия с потерями можно выполнять огрубление полуразностей, в результате чего хранению подлежат еще меньшие числа, которые дополнительно могут быть сжаты по Хаффмену.

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

6.4 Фрактальное сжатие изображений

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

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

Здесь показано также построенное таким способом изображение ветки папоротника, каждый лист которой точно повторяет форму всей ветки. Этот классический пример предложен «отцом» данного направления Майклом Барнсли и получил название «папоротника Барнсли».

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

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

Подобная процедура применяется итеративно. Пример ее применения показан на рисунке.

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

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


6.5 Метод MPEG сжатия видеопотока

Семейство стандартов MPEG (MPEG 1, MPEG 2, MPEG 4) используется для сжатия видеопотока за счет устранения пространственной и временной избыточности. При этом пространственная избыточность обеспечивается методами JPEG, которые мы рассмотрели выше. Временная избыточность связана с похожестью следующих друг за другом кадров.

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


На следующем рисунке показана реальная последовательность кадров согласно стандарта MPEG:
  • опорные, прогнозные и двунаправленные кадры традиционно обозначаются соотвественно как I- (Intra frame), P- (Predicted frame) и В- (Bidirectional frame). Их частота следования и пропорция видны по рисунку, где отображен блок, отвечающий половине секунды видеопотока;
  • важно, что для построения B-кадров все необходимые I- и P- кадры должны быть уже получены. Блок кадров, начиная с I и включая все зависящие от него P и B, называется GOP (Group of Pictures). Последовательно идущие GOP составляют выходной видеопоток. К примеру, порядок кадров согласно рисунку должен иметь вид 1,4,2,3,6,5,6 и.т.д. Из-за смены порядка неизбежно возникают задержки в воспроизведении.

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






О дисциплине ТИК
Почему «Теория информации и кодирования» - одна из самых интересных дисциплин, которые изучают будущие системщики и защитники информации?

В ней сочетаются золотая классика и самая актуальная современность computer-science.

продолжение
О сайте
Здесь вы найдете материалы, которые помогут в изучении дисциплины “Теория информации и кодирования” (ТИК) в том виде, как она преподается на кафедре ЭВМ ДИИТа.

На сайте размещены методические материалы:
  • электронный конспект лекций;
  • методическое обеспечение к лабораторным работам;
  • полезные ссылки.

продолжение
© 2008-2013 • Теория информации и кодирования
UP