Что такое сжатие изображений с потерями и без потерь
Простым языком о том, как работает сжатие файлов
Авторизуйтесь
Простым языком о том, как работает сжатие файлов
Сжатие файлов позволяет быстрее передавать, получать и хранить большие файлы. Оно используется повсеместно и наверняка хорошая вам знакомо: самые популярные расширения сжатых файлов — ZIP, JPEG и MP3. В этой статье кратко рассмотрим основные виды сжатия файлов и принципы их работы.
Что такое сжатие?
Сжатие файла — это уменьшение его размера при сохранении исходных данных. В этом случае файл занимает меньше места на устройстве, что также облегчает его хранение и передачу через интернет или другим способом. Важно отметить, что сжатие не безгранично и обычно делится на два основных типа: с потерями и без потерь. Рассмотрим каждый из них по отдельности.
Сжатие с потерями
Такой способ уменьшает размер файла, удаляя ненужные биты информации. Чаще всего встречается в форматах изображений, видео и аудио, где нет необходимости в идеальном представлении исходного медиа. MP3 и JPEG — два популярных примера. Но сжатие с потерями не совсем подходит для файлов, где важна вся информация. Например, в текстовом файле или электронной таблице оно приведёт к искажённому выводу.
MP3 содержит не всю аудиоинформацию из оригинальной записи. Этот формат исключает некоторые звуки, которые люди не слышат. Вы заметите, что они пропали, только на профессиональном оборудовании с очень высоким качеством звука, поэтому для обычного использования удаление этой информации позволит уменьшить размер файла практически без недостатков.
20–22 декабря, Онлайн, Беcплатно
Аналогично файлы 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. Качество звука от этого не улучшится, но объём станет больше.
Также стоит иметь в виду, что преобразовывая один формат с потерями в аналогичный, вы получаете дальнейшее снижение качества. Каждый раз, когда вы применяете сжатие с потерями, вы теряете больше деталей. Это становится всё более и более заметно, пока файл по существу не будет разрушен. Помните также, что форматы с потерями удаляют некоторые данные и их невозможно восстановить.
Заключение
Мы рассмотрели как сжатие файлов с потерями, так и без потерь, чтобы увидеть, как они работают. Теперь вы знаете, как можно уменьшить размер файла и как выбрать лучший способ для этого.
Алгоритмы, которые определяют, какие данные выбрасываются в методах с потерями и как лучше хранить избыточные данные при сжатии без потерь, намного сложнее, чем описано здесь. На эту тему можно почитать больше информации здесь, если вам интересно.
Как устроено сжатие с потерями
Благодаря этому у нас есть стримы и ютуб.
Недавно мы рассказывали про сжатие данных без потерь. Смысл в том, что существуют некие алгоритмы, которые позволяют уложить данные более компактно и передать их другому человеку, не потеряв ни байта.
Часто сжатия без потерь недостаточно. Сегодня поговорим о сжатии с потерями.
Чем отличается от сжатия без потерь
При таком сжатии мы теряем часть информации. Но смысл алгоритмов сжатия в том, чтобы мы этого не замечали: сжатие должно происходить так, чтобы всё важное передалось, а неважное — нет.
Можно представить, что мы говорим с человеком по телефону. Его голос немного искажён, может прерываться или немного сбоить. Но если мы смогли понять собеседника, то нам достаточно такого качества. При этом мы можем не расслышать какие-то нюансы, не ощутить всю глубину баса или не оценить все оттенки интонаций, но это нам и неважно. Разговор по телефону — это пример передачи информации с использованием сжатия с потерями.
Сжатие фотографий
Есть алгоритм сжатия для фотографий, который используют для изображений типа JPEG. В этом алгоритме изображение разделяется на один слой яркости и два слоя цвета (если упрощённо, то картинка разделяется, на чёрно-белый слой и на слой с красками).
Из Википедии: Цветное изображение и его компоненты Y, CB и CR
Эти слои нарезаются на квадраты 8 × 8 пикселей и кодируются с помощью особой математики. Её смысл в том, чтобы понять: есть ли в этом квадрате 8 × 8 что-то важное. Если оно есть, то оно кодируется и данные сохраняются. Если квадрат более-менее однородный, то он записывается как однородный, данных мало.
Экономия данных происходит как раз за счёт этой математики: например, если в квадрат 8 × 8 попал кусочек ясного неба, то там достаточно сказать «весь кусок такого-то синего цвета», и тогда нужно хранить немножко данных. А если на квадрат пришёлся какой-то угол или деталь, то данных нужно сохранить больше.
А если у вас картинка нарезана отдельно на яркость и отдельно на цвет, вы экономите ещё больше данных: в слое с яркостью у вас будут все контрастные детали, а в цветовых слоях — плавные цветовые переливы. Плавные переливы легче закодировать, это будет незаметно для глаза.
Сжатие JPEG идеально подходит для фотографий, где размер деталей намного больше, чем размер пикселей.
Возьмём странное изображение винограда на ржавой трубе. Найдите различия между двумя картинками:
Слева — оригинал, справа изображение сжато в 20 раз. Визуально разницу заметить трудно.
Теперь сожмём оригинал в 415 раз: было 10 мегабайт, стало 24 килобайта. При этом мы всё равно понимаем, что на фотографии — виноград с плодами на ржавой трубе. Наш мозг сглаживает эти неровности и узнаёт картинку.
Справа уже видны пиксели и размытость — это побочные явления сильного сжатия.
Хуже всего JPEG подходит для сжатия изображений, в которых есть мелкие детали, острые края и резкие контрасты. Особенно — если изображения мелкие. Тогда алгоритмы JPEG создают слишком много артефактов. Дизайнеры говорят, что картинку зашакалило (от слова «шакал»):
Убейте меня
Сжатие звука
Существуют алгоритмы сжатия для аудиозаписей. Их смысл в том, чтобы не кодировать ту часть данных, которая не особо влияет на восприятие аудиосигнала.
Например, человеческое ухо в среднем воспринимает звуки частотой от 20 герц до 20 килогерц. 20 Гц — это супергрудной бас, а 20 КГц — это супертонкий писк. Чтобы закодировать волну с максимальной частотой 20 КГц, на каждую секунду вам нужно 40 тысяч чисел размером 2 байта. Получается, что секунда несжатого звука будет занимать 80 килобайт.
Но содержательная часть человеческого голоса (та, в которой зашита вся информация) заканчивается на 4000 герцах. Если отрезать у голоса всё, что выше 4000 герц, вы запросто различите смысл слов и поймёте интонацию. Пропадёт лишь некоторая «воздушность» звука. Если нет цели сделать суперкрутой звук, то алгоритмам нет смысла кодировать диапазон 4—20 КГц.
Тогда из звука отсекается лишняя информация и кодируется только диапазон до 4 КГц. Для этого кодирования достаточно 16 килобайт в секунду. Это уже экономия в 5 раз!
Самая важная часть голоса вообще болтается в районе 1000—2000 герц. Если отрезать у голоса всё от 2 до 20 КГц, то нам хватит 8 КБ в секунду, а это экономия в 10 раз по сравнению с несжатым файлом.
Сравните три варианта аудио: сначала несжатый вариант, потом сжатый в 6 раз, наконец — в 160 раз:
При таком сжатии существенно «съедаются» верхние частоты, но оно и понятно: на их кодирование компьютеру нужно в несколько раз больше данных, чем на кодирование основной информационной нагрузки аудиофайла.
Когда вы говорите по телефону, ваш голос сжимается в несколько сотен раз, потому что телефонный разговор заточен только под частоты голоса. Поэтому любая музыка в телефонной трубке звучит так погано.
Сжатие видео
Чтобы сжать видео, используют комбинацию сжатия картинок и звука. И есть один дополнительный момент: сжатие только изменяющихся частей кадра. Как это работает:
Пример кодирования одной и той же сцены с разной чувствительностью — на видео она отображена в килобитах в секунду. Чувствительность влияет на итоговый размер видеофайла:
Стримы и потоковое видео
В потоковом видео ситуация усугубляется тем, что данные нужно передавать миллионам людей как можно скорее. Поэтому, помимо того чтобы сжимать видео, стриминговые сервера ещё и меняют его физический размер, то есть из большой картинки делают маленькую.
Размеры кадров в таких видео часто измеряются в «строках» — это те самые числа возле буквы p:
Соответственно, чем выше кадр, тем он шире; тем больше размер изображения; тем больше деталей в него влезает.
Самое низкое качество, которое есть в потоковом видео — 144p. Мутная картинка и пиксели, зато можно смотреть даже с медленным интернетом 
То же самое видео в формате HD или 1080p — можно прочитать даже мелкие надписи в интерфейсе игры, запущенной на умных часах. Но для этого нужен быстрый интернет/img]
Буква p в 1080p означает progressive — то есть кодируется каждая строка видеофайла. А бывает ещё буква i, которая означает interlaced. Это значит, что в одном кадре кодируются каждые чётные строки, а в следующем — каждые нечётные. Потом их объединяют в одной картинке, и если не знать, куда смотреть, то можно не заметить подвоха.
Межстрочное сжатие будет хорошо видно, если в кадре что-то движется. Вы заметите характерные «полоски» и задвоение изображения:
Машина кажется раздвоенной, потому что в одном кадре она была левее, в другом — правее, а потом эти два кадра соединили в одном, используя чересстрочное кодирование
И что нам с этим делать
Да ничего особо. Радоваться, что в наше время можно смотреть потоковое видео в прямом эфире с телефона в разрешении 1080p через сотовую вышку, пользуясь роскошным сжатием и широкополосным доступом в интернет.
В чем разница сжатия с потерями и сжатия без потерь
В озможно, Вы уже знаете, что компьютеры и умные устройства используют сжатие для экономии дискового пространства и пропускной способности, используя сжатие с потерями или сжатие без потерь. Оба типа сжатия имеют свое место, но что именно их разделяет и какое лучше?
Сжатие с потерями делает файлы меньше
Сжатие с потерями отбрасывает как можно больше данных, чтобы уменьшить размер файлов. Это достигается за счет удаления данных, которые считаются менее заметными, так что сам файл по-прежнему во многом напоминает оригинал. Чем сильнее сжат файл, тем хуже будет качество.
Двумя хорошими примерами сжатия с потерями являются изображения JPEG и аудиофайлы MP3. JPEG с высокой степенью сжатия (пример ниже) будет демонстрировать визуальные артефакты, потерю четкости и детализации, цветовые полосы и даже изменение цвета. Вы можете заметить очертания вокруг частей изображения, которых не было на оригинале.
Что касается звука, файл MP3 с высокой степенью сжатия звучит заметно хуже, чем исходный файл без сжатия, особенно на низких и высоких частотах.
Не все JPEG-файлы выглядят отвратительно, и не все MP3 звучат так, что хочется закрыть уши. Используемый уровень сжатия может иметь огромное значение для качества файла. Слегка сжатый файл JPEG или MP3 со скоростью 320 кбит/с в большинстве случаев будет трудно отличить от несжатого оригинала.
Сжатие без потерь способствует большему качеству
Сжатие без потерь требует, чтобы данные не удалялись, что, в свою очередь, требует больше места или пропускной способности. В отличие от сжатия с потерями, сжатие без потерь не приводит к ухудшению качества данных, а распакованные данные идентичны несжатым оригиналам.
Некоторые примеры сжатия без потерь включают аудиокодеки FLAC и ALAC, архивы ZIP и изображения PNG. Аудиофайлы, использующие сжатие без потерь, составляют примерно половину размера несжатого оригинала при той же частоте дискретизации. Многие сервисы потокового аудио теперь предлагают потоковую передачу без потерь, включая Apple Music, Tidal, Deezer и HiFi Spotify.
Файлы ZIP часто используются для сжатия программного обеспечения, которое не может подвергаться какой-либо форме сжатия с потерями, в результате чего данные будут удалены (и программное обеспечение больше не будет работать). Файлы изображений PNG полагаются исключительно на сжатие без потерь, а такие службы, как TinyPNG, вместо этого сжимают изображения, чтобы они соответствовали гораздо меньшей цветовой палитре, чтобы уменьшить размер файла.
И сжатие с потерями и сжатие без потерь имеют свое место применения
Сжатие без потерь — главное в архивных целях. Невозможно восстановить версию файла без потерь, если он был сжат с потерями.
Если размер файла или пропускная способность вызывают беспокойство, сжатие с потерями имеет гораздо больше смысла. Например, если Вы хотите загрузить музыку на свой смартфон для прослушивания в автономном режиме, использование кодеков с потерями, таких как AAC, позволит Вам хранить гораздо больше музыки за счет небольшого снижения качества.
Сжатие изображений с потерями
Прежде чем говорить об алгоритмах сжатиях с потерями, необходимо договориться о том, что считать приемлемыми потерями. Понятно, что главным критерием остаётся визуальная оценка изображения, но также изменения в сжатом изображении могут быть оценены количественно. Самый простой способ оценки – это вычисление непосредственной разности сжатого и исходного изображений. Договоримся, что под 
мы будем понимать пиксел, находящийся на пересечении i-ой строки и j-ого столбца исходного изображения, а под 
— соответствующий пиксел сжатого изображения. Тогда для любого пиксела можно легко определить ошибку кодирования 
, а для всего изображения, состоящего из N строк и M столбцов, можно вычислить суммарную ошибку 
. Очевидно, что, чем больше суммарная ошибка, тем сильнее искажения на сжатом изображении. Тем не менее, эту величину крайне редко используют на практике, т.к. она никак не учитывает размеры изображения. Гораздо шире применяется оценка с использованием среднеквадратичного отклонения 
.
Другой (хотя и близкий по сути) подход заключается в следующем: пиксели итогового изображения рассматриваются как сумма пикселей исходного изображения и шума. Критерием качества при таком подходе называют величину отношения сигнал-шум (SNR), вычисляемую следующим образом: 
.
Обе эти оценки являются т.н. объективными критериями верности воспроизведения, т.к. зависят исключительно от исходного и сжатого изображения. Тем не менее, эти критерии не всегда соответствуют субъективным оценкам. Если изображения предназначены для восприятия человеком, единственное, что можно утверждать: плохие показатели объективных критериев чаще всего соответствуют низким субъективным оценкам, в то же время хорошие показатели объективных критериев вовсе не гарантируют высоких субъективных оценок.
С процессом квантования и дискретизации связано понятие визуальной избыточности. Значительная часть информации на изображении не может быть воспринята человеком: например, человек способен замечать незначительные перепады яркости, но гораздо менее чувствителен к цветности. Также, начиная с определённого момента, повышение точности дискретизации не влияет на визуальное восприятие изображения. Таким образом, некоторая часть информации может быть удалена без ухудшения визуального качества. Такую информацию называют визуально избыточной.
Самым простым способом удаления визуальной избыточности является уменьшение точности дискретизации, но на практике этот способ можно применять только для изображений с простой структурой, т.к. искажения, возникающие на сложных изображениях, слишком заметны (см. Табл. 1)
Для удаления избыточной информации чаще уменьшают точность квантования, но нельзя уменьшать её бездумно, т.к. это приводит к резкому ухудшению качества изображения.
Рассмотрим уже известное нам изображение с. Предположим, что изображение представлено в цветовом пространстве RGB, результаты кодирования этого изображения с пониженной точностью квантования представлены в Табл. 2.
В рассмотренном примере используется равномерное квантование как наиболее простой способ, но, если важно более точно сохранить цветопередачу, можно использовать один из следующих подходов: либо использовать равномерное квантование, но значением закодированной яркости выбирать не середину отрезка, а математическое ожидание яркости на этом отрезке, либо использовать неравномерное разбиение всего диапазона яркостей.
Внимательно изучив полученные изображения, можно заметить, что на сжатых изображениях возникают отчётливые ложные контуры, которые значительно ухудшают визуальное восприятие. Существуют методы, основанные на переносе ошибки квантования в следующий пиксел, позволяющие значительно уменьшить или даже совсем удалить эти контуры, но они приводят к зашумлению изображения и появлению зернистости. Перечисленные недостатки сильно ограничивают прямое применение квантования для сжатия изображений.
Большинство современных методов удаления визуально избыточной информации используют сведения об особенностях человеческого зрения. Всем известна различная чувствительность человеческого глаза к информации о цветности и яркости изображения. В Табл. 3 показано изображение в цветовом пространстве YIQ, закодированное с разной глубиной квантования цветоразностных сигналов IQ:
Как видно из Табл. 3, глубина квантования цветоразностных сигналов может быть понижена с 256 до 32 уровней с минимальными визуальными изменениями. В то же время потери в I и Q составляющих весьма существенны и показаны в Табл. 4
Несмотря на простоту описанных методов, в чистом виде они применяются редко, чаще всего они служат одним из шагов более эффективных алгоритмов.
Кодирование с предсказанием
Мы уже рассматривали кодирование с предсказанием как весьма эффективный метод сжатия информации без потерь. Если совместить кодирование с предсказанием и сжатие посредством квантования, получится весьма простой и эффективный алгоритм сжатия изображения с потерями. В рассматриваемом методе будет квантоваться ошибка предсказания. Именно точность её квантования будет определять как степень сжатия, так и искажения, вносимые в сжатое изображение. Выбор оптимальных алгоритмов для предсказания и для квантования — довольно сложная задача. На практике широко используют следующие универсальные (обеспечивающие приемлемое качество на большинстве изображений) предсказатели:
Мы же в свою очередь подробно рассмотрим самый простой и в тоже время весьма популярный способ кодирования с потерями – т.н. дельта-модуляцию. Этот алгоритм использует предсказание на основе одного предыдущего пиксела, т.е. 
. Полученная после этапа предсказания ошибка квантуется следующим образом:
На первый взгляд это очень грубый способ квантования, но у него есть одно неоспоримое преимущество: результат предсказания может быть закодирован единственным битом. В Табл. 5 показаны изображения, закодированные с помощью дельта-модуляции (обход по строкам) с различными значениями ξ.
Наиболее заметны два вида искажений – размытие контуров и некая зернистость изображения. Это наиболее типичные искажения, возникающие из-за перегрузки по крутизне и из-за т.н. шума гранулярности. Такие искажения характерны для всех вариантов кодирования с потерями с предсказанием, но именно на примере дельта-модуляции они видны лучше всего.
Шум гранулярности возникает в основном на однотонных областях, когда значение ξ слишком велико для корректного отображения малых колебаний яркости (или их отсутствия). На Рис. 1 жёлтой линией отмечена исходная яркость, а синие столбцы показывают шум, возникающий при квантовании ошибки предсказания.
Ситуация перегрузки по крутизне принципиально отличается от ситуации с шумом гранулярности. В этом случае величина ξ оказывается слишком малой для передачи резкого перепада яркости. Из-за того, что яркость закодированного изображения не может расти также быстро, как яркость исходного изображения, возникает заметная размытость контуров. Ситуация с перегрузкой по крутизне поясняется на Рис. 2
Легко заметить, что шум гранулярности уменьшается вместе с уменьшением ξ, но вместе с этим растут искажения из-за перегрузки по крутизне и наоборот. Это приводит к необходимости оптимизации величины ξ. Для большинства изображений рекомендуется выбирать ξ∈[5;7].
Трансформационное кодирование
Все рассмотренные ранее методы сжатия изображений работали непосредственно с пикселами исходного изображения. Такой подход называют пространственным кодированием. В текущем разделе мы рассмотрим принципиально иной подход, называемый трансформационным кодированием.
Основная идея подхода похожа на рассмотренный ранее способ сжатия с использованием квантования, но квантоваться будут не значения яркостей пикселов, а специальным образом рассчитанные на их основе коэффициенты преобразования (трансформации). Схемы трансформационного сжатия и восстановления изображений приведены на Рис. 3, Рис. 4.
Непосредственно сжатие происходит не в момент кодирования, а в момент квантования коэффициентов, т.к. для большинства реальных изображений большая часть коэффициентов может быть грубо квантована.
Для получения коэффициентов используют обратимые линейные преобразования: например преобразование Фурье, дискретное косинусное преобразование или преобразование Уолша-Адамара. Выбор конкретного преобразования зависит от допустимого уровня искажения и имеющихся ресурсов.
В общем случае изображение размерами N*N пикселов рассматривается как дискретная функция от двух аргументов I(r,c), тогда прямое преобразование можно выразить в следующем виде:
Набор 
как раз и является искомым набором коэффициентов. На основе этого набора можно восстановить исходное изображение, воспользовавшись обратным преобразованием:
Функции 
называют ядрами преобразования, при этом функция g – ядро прямого преобразования, а функция h — ядро обратного преобразования. Выбор ядра преобразования определяет как эффективность сжатия, так и вычислительные ресурсы, требуемые для выполнения преобразования.
Широкораспространённые ядра преобразования
Наиболее часто при трансформационном кодировании используются ядра, перечисленные ниже.
Использование первых двух ядер этих ядер приводит к упрощённому варианту дискретного преобразования Фурье. Вторая пара ядер соответствует довольно часто используемому преобразованию Уолша-Адамара. И, наконец, наиболее распространённым преобразованием является дискретное косинусное преобразование:
Широкая распространённость дискретного косинусного преобразования обусловлена его хорошей способностью производить уплотнение энергии изображения. Строго говоря, есть более эффективные преобразования. Например, преобразование Кархунена-Лоэва имеет наилучшую эффективность в плане уплотнения энергии, но его сложность практически исключает возможность широкого практического применения.
Сочетание эффективности уплотнения энергии и сравнительной простоты реализации сделало дискретное косинусное преобразование стандартом трансформационного кодирования.
Графическое пояснение трансформационного кодирования
В контексте функционального анализа рассмотренные преобразования можно рассматривать как разложение по набору базисных функций. В то же время в контексте обработки изображений эти преобразования можно воспринимать как разложение по базисным изображениям. Чтобы пояснить эту идею, рассмотрим квадратное изображение I размером n*n пикселов. Ядра преобразований не зависят ни от коэффициентов преобразования, ни от значения пикселов исходного изображения, поэтому обратное преобразование можно записать в матричном виде:
Если эти матрицы расположить в виде квадрата, а полученные значения представить в виде пикселов определённого цвета, можно получить графическое представление базисных функций, т.е. базисные изображения. Базисные изображения преобразования Уолша-Адамара и дискретного косинусного преобразования для n=4 приведены в Табл. 7.
Особенности практической реализации трансформационного кодирования
Общая идея трансформационного кодирования была описана ранее, но, тем не менее, практическая реализация трансформационного кодирования требует прояснения нескольких вопросов.
Перед кодированием изображение разбивается на квадратные блоки, а затем каждый блок подвергается преобразованию. От выбора размера блока зависит как вычислительная сложность, так и итоговая эффективность сжатия. При увеличении размера блока растёт как эффективность сжатия, так и вычислительная сложность, поэтому на практике чаще всего используются блоки размером 8*8 или 16*16 пикселов.
После того, как для каждого блока вычислены коэффициенты преобразования, необходимо их квантовать и закодировать. Наиболее распространёнными подходами являются зональное и пороговое кодирование.
При зональном подходе предполагается, что наиболее информативные коэффициенты будут находиться вблизи нулевых индексов полученного массива. Это значит, что соответствующие коэффициенты должны быть наиболее точно квантованы. Другие коэффициенты можно квантовать значительно грубее или просто отбросить. Проще всего понять идею зонального кодирования можно, посмотрев на соответствующую маску (Табл. 8):
Число в ячейке показывает количество бит, отводимых для кодирования соответствующего коэффициента.
В отличие от зонального кодирования, где для любого блока используется одна и та же маска, пороговое кодирование подразумевает использование уникальной маски для каждого блока. Пороговая маска для блока строится, исходя из следующих соображений: наиболее важными для восстановления исходного изображения являются коэффициенты с максимальным значением, поэтому, сохранив эти коэффициенты и обнулив все остальные, можно обеспечить как высокую степень сжатия, так и приемлемое качество восстановленного изображения. В Табл. 9 показан примерный вид маски для конкретного блока.
Единицы соответствуют коэффициентам, которые будут сохранены и квантованы, а нули соответствуют выброшенным коэффициентам После применения маски полученная матрица коэффициентов должна быть преобразована в одномерный массив, причём для преобразования необходимо использовать обход змейкой. Тогда в полученном одномерном массиве все значимые коэффициенты будут сосредоточены в первой половине, а вторая половина будет практически полностью состоять из нулей. Как было показано в ранее, подобные последовательности весьма эффективно сжимаются алгоритмами кодирования длин серий.
Вейвлет сжатие
Вейвлеты – математические функции, предназначенные для анализа частотных компонент данных. В задачах сжатия информации вейвлеты используются сравнительно недавно, тем не менее исследователям удалось достичь впечатляющих результатов.
В отличие от рассмотренных выше преобразований, вейвлеты не требуют предварительного разбиения исходного изображения на блоки, а могут применяться к изображению в целом. В данном разделе вейвлет сжатие будет пояснено на примере довольно простого вейвлета Хаара.
Для начала рассмотрим преобразование Хаара для одномерного сигнала. Пусть есть набор S из n значений, при преобразовании Хаара каждой паре элементов ставится в соответствие два числа: полусумма элементов и их полуразность. Важно отметить, что это преобразование обратимо: т.е. из пары чисел можно легко восстановить исходную пару. На Рис. 5 показан пример одномерного преобразования Хаара:
Видно, что сигнал распадается на две составляющее: приближенное значение исходного (с уменьшенным в два раза разрешением) и уточняющую информацию.
Двумерное преобразование Хаара – простая композиция одномерных преобразований. Если исходные данные представлены в виде матрицы, то сначала выполняется преобразование для каждой строки, а затем для полученных матриц выполняется преобразование для каждого столбца. На Рис. 6 показан пример двумерного преобразования Хаара.
Цвет пропорционален значению функции в точке (чем больше значение, тем темнее). В результате преобразования получается четыре матрицы: одна содержит аппроксимацию исходного изображения (с уменьшенной частотой дискретизации), а три остальных содержат уточняющую информацию.
Сжатие достигается путём удаления некоторых коэффициентов из уточняющих матриц. На Рис. 7 показан процесс восстановления и само восстановленное изображение после удаления из уточняющих матриц малых по модулю коэффициентов:
Очевидно, что представление изображения с помощью вейвлетов позволяет добиваться эффективного сжатия, сохраняя при этом визуальное качество изображения. Несмотря на простоту, преобразование Хаара сравнительно редко используется на практике, т.к. существуют другие вейвлеты, обладающие рядом преимуществ (например, вейвлеты Добеши или биортогональные вейвлеты).