Вокруг подобных методов выросла целая отрасль математики – теория кодирования. В общем случае эти методы куда тоньше, чем описанный выше, и обычно в них для определения кодов используются свойства абстрактной алгебры. Это не должно слишком удивлять: в главе 5 мы видели, что, по существу, коды – это математические функции и что особенно полезны здесь функции теории чисел. Там целью была секретность, здесь цель – сжатие данных, но общий принцип одинаков в обоих случаях. Алгебра имеет отношение к структуре, как и избыточность.
Сжатие данных, а следовательно, и сжатие изображений, использует избыточность для создания кодов, укорачивающих данные конкретного типа. Иногда данные сжимаются «без потерь»: в этом случае первоначальную информацию можно восстановить по сжатой версии в точности. Иногда данные теряются, и тогда восстановленный вариант лишь приближение первоначальных данных. Это было бы плохо, скажем, для банковских счетов, но зачастую вполне годится для изображений: главное – устроить все так, чтобы приближенный вариант по-прежнему выглядел для человеческого глаза похожим на первоначальное изображение. Тогда информация, которая теряется безвозвратно, вообще не имеет значения.
Изображения в реальном мире по большей части избыточны. Отпускные фотки часто содержат большие блоки голубого неба, нередко примерно одинакового оттенка по всей площади, так что множество пикселей с одинаковым цветовым кодом может быть заменено двумя парами координат для противоположных углов прямоугольника и коротким кодовым сообщением типа «окрасить эту область этим оттенком голубого цвета». Такой метод сжимает изображения без потерь. Реально его не применяют, но он наглядно показывает, почему сжатие без потерь возможно.
Я старомоден, то есть пользуюсь фототехникой, которой – какой ужас! – уже около 10 лет. Возмутительно! Я умею обращаться с техникой и вполне могу снять что-то с помощью смартфона, но это не превратилось в рефлекс, и в серьезные путешествия, такие как сафари с тиграми в национальных парках Индии, я беру с собой маленькую автоматическую цифровую камеру. Она создает файлы изображений с такими названиями, как IMG_0209.JPG. Идентификатор JPG свидетельствует о том, что файлы сохранены в формате JPEG, по первым буквам названия Joint Photographic Expert Group, и указывает на систему сжатия данных. JPEG – отраслевой стандарт, хотя с годами он получил некоторое развитие и теперь существует в нескольких формально разных формах.
Формат JPEG{59} предполагает выполнение не менее пяти последовательных преобразований, большинство из которых сжимает данные, полученные на предыдущем этапе (первоначальные сырые данные на первом этапе). Остальные перекодируют их для дальнейшего сжатия. Цифровые изображения состоят из миллионов крохотных квадратиков, именуемых пикселями – элементами картинки (на английском слово pixel расшифровывается как picture element). Сырые данные с камеры присваивают каждому пикселю битовую строку, представляющую как цвет, так и яркость. Обе величины представляются как доли трех компонентов: красного, зеленого и синего. Низкие доли всех трех компонентов соответствуют бледным цветам, высокие – темным. Эти числа конвертируются в три связанных друг с другом числа, которые лучше соответствуют тому, как человеческий мозг воспринимает изображения. Первое из них – светлота – дает общую яркость изображения и измеряется числами от черного, через все более светлые оттенки серого, до белого. Если удалить информацию о цвете, у вас останется старомодное черно-белое изображение – на самом деле это множество оттенков серого. Другие два числа, известные как цветность, представляют собой разности между светлотой и количеством синего и красного света соответственно.
Символьно, если R – красный, G – зеленый и B – синий, то начальные числа для R, G и B заменяются светлотой R + G + B и двумя цветностями (R + G + B) – B = R + G и (R + G + B) – R = G + B. Если вы знаете R + G + B, R + G и G + B, то можете вычислить R, G и B, так что этот этап проходит без потерь.
Реализовать второй этап без потерь не удастся. Здесь данные цветности урезаются до меньших значений за счет огрубления разрешения. Один только этот этап снижает размер файла данных наполовину. Это приемлемо, потому что в сравнении с тем, что «видит» камера, зрительная система человека более чувствительна к яркости и менее – к цветовым различиям.
Третий этап наиболее математичен. Он сжимает информацию светлости с использованием цифровой версии преобразования Фурье, которую мы встречали в главе 9 в связи с медицинскими сканерами. Там оригинальное преобразование Фурье, которое превращает сигналы в составляющие их частоты и наоборот, было модифицировано, чтобы представлять проекции черно-белых изображений. На этот раз мы представляем сами черно-белые изображения, но в простом цифровом формате. Изображение разбивается на крохотные блоки 8 × 8 пикселей, так что в каждом из них присутствуют 64 возможных значения светлости, по одному на каждый пиксель. Дискретное косинусное преобразование – цифровой вариант преобразования Фурье – представляет это черно-белое изображение 8 × 8 как суперпозицию 64 стандартных изображений с коэффициентами. Эти коэффициенты суть амплитуды соответствующих изображений, а сами изображения выглядят как полосы и клетки разной ширины. Таким образом может быть получен любой блок 8 × 8 пикселей, так что этот этап тоже проходит без потерь. Во внутренних координатах эти блоки представляют собой дискретные версии cos mx cos ny для разных целых m и n, где x меняется по горизонтали, а y – по вертикали, и оба они принимают значения от 0 до 7.
Хотя дискретное преобразование Фурье реализуется без потерь, его нельзя назвать бессмысленным, потому что именно оно делает возможным четвертый этап. Этот этап опять же основан на недостаточной чувствительности человеческого зрения, которая порождает избыточность. Если яркость или цвет меняется на большой площади изображения, мы это замечаем. Если они меняются на очень небольших участках, зрительная система сглаживает эффект, и мы видим лишь среднее. Именно поэтому печатные изображения воспринимаются как картинки, хотя при ближайшем рассмотрении они представляют оттенки серого россыпью черных точек на белой бумаге. Эта особенность человеческого зрения означает, что узоры с очень тонкими полосками менее важны, так что их амплитуды могут быть записаны с меньшей точностью.
64 базовых паттерна дискретного косинусного преобразования
Пятый этап – это технический прием, известный как «код Хаффмана», для более эффективной записи амплитуд 64 базовых паттернов. Дэвид Хаффман придумал этот метод в 1951 году еще студентом. Он тогда получил задание написать курсовую работу по оптимально эффективным двоичным кодам, но не мог доказать, что хотя бы какой-нибудь из существовавших на тот момент кодов оптимален. Уже собираясь сдаться, Хаффман придумал новый метод, а затем и доказал, что он является наилучшим из возможных. Грубо говоря, задача в том, чтобы закодировать множество символов при помощи двоичных строк, а затем использовать их как словарь для кодирования сообщения. Сделать это необходимо так, чтобы минимизировать общую длину закодированного сообщения.
Например, в качестве словарных символов можно использовать буквы алфавита. В английском алфавите их 26, так что каждой из них можно было бы присвоить 5-битную строку, скажем, A = 00001, B = 00010 и т. д. Пять бит нужны потому, что из четырех бит можно составить только 16 строк. Но использовать 5-битные строки было бы неэффективно, потому что на буквы, которые встречаются редко, такие как Z, уходит ровно столько же битов, сколько на распространенные буквы, такие как E. Лучше было бы присвоить E короткую строку, такую как 0 или 1, и постепенно удлинять строки по мере того, как буквы становятся менее вероятными. Однако, поскольку в этом случае кодовые строки получаются разными по длине, потребуется дополнительная информация, которая сообщит реципиенту, где следует разбить строку на отдельные буквы. В принципе, это можно сделать при помощи префикса перед кодовой строкой, но у нас сам код должен быть, как говорят математики, беспрефиксным: кодовая строка не должна начинаться с другой, более короткой кодовой строки. Редко используемые буквы, такие как Z, при этом требуют намного больше битов, но, поскольку они редкие, более короткие строки для E с лихвой компенсируют это. Общая длина типичного сообщения оказывается короче.
В коде Хаффмана это достигается формированием «дерева» – своеобразного графа, не имеющего замкнутых петель и очень распространенного в информатике, потому что такой граф представляет целую стратегию решений типа да/нет, где каждое решение зависит от предыдущего. Листьями дерева являются символы A, B, C, …, и из каждого листа выходит по две ветви, соответствующие двум битам 0 и 1. Каждый лист обозначен числом, которое называют его весом и которое показывает, как часто встречается соответствующий символ. Дерево строится шаг за шагом путем слияния двух наименее частых листьев в новый «материнский» лист, тогда как первые два листа становятся листьями-«дочками». Материнскому листу присваивается вес, равный сумме весов двух дочерних листьев. Этот процесс продолжается до тех пор, пока все символы не сольются. Тогда кодовая строка для символа считывается с пути, который ведет по дереву к этому символу.
Построение кода Хаффмана
Например, на рисунке слева вверху показаны пять символов A, B, C, D, E и числа 18, 9, 7, 4, 3, указывающие на частоту их встречаемости. Самые редко встречающиеся символы здесь D и E. На втором этапе, вверху по центру, их смешивают с образованием материнского листа (ненумерованного) с весом 4 + 3 = 7, а символы D и E становятся дочерними. Две ведущие к ним ветви получают обозначения 0 и 1. Этот процесс повторяется несколько раз, пока все символы не сливаются воедино (внизу слева). Теперь мы считываем кодовые строки, следуя по путям вниз по дереву. К A ведет одна-единственная ветвь, обозначенная как 0. К B ведет путь 100, к C – путь 101, к D – путь 110 и к E – путь 111. Обратите внимание, что A, самый часто встречающийся символ, получает короткий путь, а менее распространенные символы – более длинные пути. Если бы вместо этого мы использовали код с фиксированной длиной строки, нам потребовалось бы по крайней мере три бита, чтобы закодировать пять символов, потому что двухбитных строк всего четыре. Здесь же в самых длинных строках по три бита, но в самой часто встречающейся – всего один, так что в среднем этот код более эффективен. Эта процедура гарантирует, что наш код беспрефиксный, поскольку любой путь на дереве ведет к какому-нибудь символу и на нем останавливается. Он не может продолжаться до другого символа. Более того, начав с наименее распространенных символов, мы гарантируем, что к самым распространенным символам будут вести самые короткие пути. Это отличная идея, легкая в программировании и очень простая концептуально, стоит один раз в ней разобраться.