Это база: Зачем нужна математика в повседневной жизни - Йэн Стюарт
Шрифт:
Интервал:
Закладка:
* * *
Я старомоден, то есть пользуюсь фототехникой, которой – какой ужас! – уже около 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, и постепенно удлинять строки по мере того, как буквы становятся менее вероятными. Однако, поскольку в этом случае кодовые строки получаются разными по длине, потребуется дополнительная информация, которая сообщит реципиенту, где следует разбить строку на отдельные буквы. В принципе, это можно сделать при помощи префикса перед кодовой строкой, но у нас сам код должен быть, как говорят математики, беспрефиксным: кодовая строка не должна начинаться с другой, более короткой кодовой строки. Редко используемые буквы, такие как
