ЛекцииММ1 (Курс электронных лекций), страница 9

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

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

Алгоритмы сжатия с потерями.

JPEG - один из самых новых и достаточно мощных алгоритмов. Практически он становится стандартом де - факто для полноцветных изображений. Алгоритм JPEG был разработан группой фирм под названием Joint Photographic Experts Group. Целью проекта являлось создание высокоэффективного стандарта сжатия как черно-белых, так и цветных изображений, эта цель и была достигнута разработчиками. В настоящее время JPEG находит широчайшее применение там, где требуется высокая степень сжатия - например, в Internet.

В отличие от LZW - алгоритма JPEG - кодирование является кодированием с потерями. Сам алгоритм кодирования базируется на очень сложной математике, но в общих чертах его можно описать так:    

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

Схема YUV использует три компоненты, Y – яркость (может быть использована как чёрно – белое изображение), U – голубизна, V – краснота. Перевод из RGB осуществляется по схеме:

Y = 0.299R + 0.587G + 0.114B

U = 0.1687R - 0.3313G + 0.5B

V = 0.5R - 0.1187G + 0.0813B

Это преобразование, в принципе, не имеет потерь, но на практике вводится ошибка округления, обусловленная необходимостью округления результата до целого. Так как глаз человека более чувствителен к первой компоненте, чем к двум другим, то в JPEG допускает дискретизацию различных компонент с различной частотой. Наиболее общий случай – использование одной выборки U и V для четырёх выборок Y. Это позволяет сохранять лишь 50% используемого объёма при практически неизменном качестве изображения. Технология дискретизации, при которой некоторые компоненты оцифровываются с меньшей частотой, чем другие, называется поддескритизацией.

К значениям пикселей применяется формула, названная дискретным косинусоидальным преобразованием (Discrete Cosine Transform - DCT). DCT переводит матрицу значений пикселей 8х8 в матрицу значений амплитуд такой же размерности, соответствующую определенным частотам синусоидальных колебаний. Левый верхний угол матрицы соответствует низким частотам, а правый нижний - высоким.

Дискретное косинусоидальное преобразование (DCT) превращает массив данных интенсивности в массив данных частоты, который содержит информацию о том, как быстро изменяется интенсивность. В JPEG применяется DCT для квадратов 8*8 данных о пикселях для каждого компонента цвета. Точки в каждом блоке нумеруются от (0,0) в верхнем левом до (7,7) в нижнем правом углах. F(x,y) есть значение данных в точке (x,y). Создаётся новый блок по формуле:

Обратное преобразование имеет вид:

По физическому смыслу преобразование сводится к представлению изображения в виде суммы (ко)синусоидальных гармоник (волн). Значения F определяют амплитуды гармоник, u,v – их частоты. F(u,v) указывает на степень изменения величин для каждой из множества частот. Значение F(0,0) указывает что уровень значения не изменился, F(7,7) определяет наиболее быстрое изменение величины в обоих направлениях. Более высокие частоты “отвечают” за передачу более “тонких” деталей изображения.

Для блоков 8*8 выходные данные на 4 бита длиннее входных. Отличие интенсивностей от частот в том, что медленные изменения гораздо заметнее, чем быстрые, так что данные низкой частоты более важны, чем высокой для восстановления изображения.

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

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

Далее программа, двигаясь по матрице зигзагообразно (13456 и т.д.), считывает элементы матрицы и кодирует их последовательно методами без потерь.

Заметим, что сжатие существенно зависит от нулей в правой нижней половине матрицы. Чем ниже коэффициент качества, тем больше нулей в матрице и, следовательно, тем выше степень сжатия.

Декодирование JPEG-изображения начинается с шага обратного кодированию без потерь, в результате чего восстанавливается матрица квантования пикселей.

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

Обратная к DCT формула (IDCT) применяется к матрице для восстановления значений пикселей исходного изображения.

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

Итак, теперь мы можем сделать вывод о достоинствах и недостатках формата JPEG. Безусловно, его сильной стороной является большой коэффициент сжатия при сохранении исходной цветовой глубины. Именно это свойство обусловило его широкое применение в Internet, где уменьшение размера файлов имеет первостепенное значение, в мультимедийных энциклопедиях, где требуется хранение возможно большего количества графики в ограниченном объеме.

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

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

Фрактальное сжатие.

Эта группа алгоритмов, по-видимому, является самой перспективной и развивается сейчас наиболее бурно. Первые практические результаты были получены сравнительно недавно - в 1992 году - и произвели ошеломляющее впечатление. В декабре 1992 года компания Microsoft выпустила свой новый компакт - диск Microsoft Encarta. С тех пор эта мультимедиа - энциклопедия, содержащая информацию о животных, цветах, деревьях и живописных местах, не покидает списки наиболее популярных энциклопедий на компакт - дисках. Коэффициент сжатия у фрактальных алгоритмов варьируется в пределах 2-2000. Причем большие коэффициенты достигаются на реальных изображениях, что, вообще говоря, нетипично для предшествующих алгоритмов. Кроме того, при разархивации изображение можно масштабировать. Уникальная особенность этого алгоритма заключается в том, что увеличенное изображение не дробится на квадраты. Во фрактальном сжатии используется принципиально новая идея - не близость цветов в локальной области, а подобие разных по размеру областей изображения. Это, безусловно, наиболее прогрессивный подход на сегодняшний день. Алгоритм ориентирован на полноцветные изображения и изображения в градациях серого цвета.

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

(отношение времени архивации ко времени разархивации) не превышал 3, то у фрактального алгоритма он колеблется в пределах 1000-10000. Как следствие - основные работы сейчас ведутся по распараллеливанию и ускорению его работы. Фрактальное сжатие реализовано в формате FIF.

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

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

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

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

Наиболее известны два изображения, полученных с помощью IFS треугольник Серпинского и папоротник Барнсли. Первое задается тремя, а второе - пятью аффинными преобразованиями (или, в нашей терминологии, линзами). Каждое преобразование задается буквально считанными байтами, в то время, как изображение, построенное с их помощью, может занимать и несколько мегабайт.

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

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

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