Когда ваша камера создает файл JPEG, ее электроника производит все расчеты на лету, как только вы нажимаете на спуск. Процесс сжатия проходит не без потерь, но большинство из нас никогда этого не заметит. В любом случае экраны компьютеров и принтеры при распечатке не передают цвета и яркость в точности, за исключением случаев, когда их заранее тщательно калибруют. Непосредственное сравнение оригинального изображения и его сжатой версии делает различия более очевидными, но даже в этом случае только эксперт заметит разницу, если файл был сжат до 10 % от первоначального объема. Обычные смертные замечают разницу, только когда файл уменьшается до примерно 3 % от оригинала. Так что JPEG позволяет записать на карту памяти в 10 раз больше изображений, чем оригинальный формат данных RAW. Описанная выше сложная пятиступенчатая процедура, выполняемая в мгновение ока за кулисами, – это и есть магия, в которой задействованы пять областей математики.
Другой способ сжатия изображений вырос в конце 1980-х годов из фрактальной геометрии. Фрактал, как вы помните, это геометрическая фигура, структура которой детализируема на всех масштабах, как у береговой линии или облака. С фракталом связано определенное число, называемое размерностью и представляющее собой меру того, насколько данный фрактал угловат или волнист. Как правило, размерность фрактала не является целым числом. Полезный класс математически разрешимых фракталов включает самоподобные фракталы: небольшие их кусочки, надлежащим образом увеличенные, выглядят в точности так же, как более крупные куски целого. Классический пример – папоротник, состоящий из десятков листов, каждый из которых выглядит как миниатюрный папоротник. Самоподобные фракталы могут быть представлены математической структурой, известной как система итерированных функций (IFS). Это набор правил, говорящих, как следует сжимать копии формы и сдвигать получившиеся плитки так, чтобы они сложились и образовали целое. Фрактал можно восстановить по этим правилам, а для размерности фрактала существует даже формула.
Фрактальный папоротник, составленный из трех преобразованных копий самого себя
В 1987 году математик Майкл Барнсли, давно увлекавшийся фракталами, понял, что их главное свойство может стать основой для нового метода сжатия изображений. Вместо того чтобы использовать огромное количество данных для кодирования каждой крохотной детали папоротника, можно просто закодировать соответствующую систему итерированных функций, на что потребуется значительно меньше данных. Программное обеспечение всегда может восстановить изображение папоротника по IFS. Барнсли вместе с Аланом Слоуном основал компанию Iterated Systems Inc., которая получила более 20 патентов. В 1992 году она совершила настоящий прорыв: был разработан автоматический метод нахождения подходящих правил IFS. Программа ищет на изображении маленькие области, которые можно рассматривать как съежившиеся версии бо́льших по размеру областей. Таким образом, она использует намного больше плиток для мощения изображения. Однако метод остается общим и применим к любым изображениям, а не только к тем из них, которые очевидно самоподобны. Фрактальное сжатие изображений не настолько популярно, как JPEG, по разным причинам, но использовалось в нескольких практических приложениях. Пожалуй, самым успешным из них была цифровая энциклопедия Encarta компании Microsoft, где все основные изображения были сжаты методом IFS.
Кто это? Прищурьтесь
На протяжении 1990-х годов компания предпринимала энергичные попытки распространить свой метод на сжатие видео, но из этого ничего не вышло, в основном потому, что тогдашние компьютеры были недостаточно быстрыми и имели недостаточно памяти. На сжатие одной минуты видео уходило 15 часов. Сегодня все изменилось, и фрактальное видеосжатие в отношении 200:1 можно проводить со скоростью один видеокадр в минуту. Повышение мощности компьютеров делает реальными и другие методы, и на данный момент от фрактального видеосжатия практически отказались. Но идея, лежащая в его основе, в свое время была полезна, да и сейчас таит в себе интересные возможности.
У людей есть очень странный прием для расшифровки некачественных изображений: мы прищуриваемся. Поразительно, но часто это помогает разобрать, что на самом деле изображено на картинке, особенно если она слегка размыта или если это компьютерное изображение с очень грубыми пикселями. Существует знаменитое изображение, составленное из 270 черных, белых и серых квадратов, которое создал в 1973 году Леон Хармон из Bell Labs для статьи о человеческом восприятии и компьютерном распознавании образов. Кто это? Если внимательно вглядеться в изображение, можно различить в нем что-то слегка напоминающее Авраама Линкольна, но если прищуриться, изображение начинает и правда походить на Линкольна.
Мы все это делаем, то есть знаем, что это работает, но вообще такой способ кажется безумием. Как можно улучшить плохую картинку, ухудшив собственное зрение? Отчасти ответ лежит в области психологии: прищуриваясь, мы переводим систему обработки визуальной информации в мозге в режим «плохое изображение», который, по всей видимости, запускает особые алгоритмы обработки изображений, развившиеся в ходе эволюции для работы с некачественными данными. Но есть и другая часть: как ни парадоксально, прищуривание выполняет роль своего рода предварительной обработки и очищает изображение в нескольких полезных отношениях. Так, оно размывает у Линкольна границы пикселей-квадратиков, так что портрет перестает походить на штабель серых строительных блоков.
Около 40 лет назад математики начали исследовать точный и гибкий эквивалент человеческого прищуривания, известный как вейвлет-анализ, или анализ формы сигнала. Этот метод применим не только к изображениям, но и к численным данным и первоначально был предложен для выделения структуры на конкретном пространственном масштабе. Вейвлет-анализ позволяет заметить лес, не обращая внимания на то, что он состоит из множества сложных деревьев и кустов.
Сначала математиками двигали в основном теоретические соображения: вейвлеты прекрасно годились для проверки научных гипотез о таких вещах, как турбулентный поток жидкости. Позже вейвлетам нашлись кое-какие чрезвычайно практические применения. В США Федеральное бюро расследований применяет вейвлеты для хранения дактилоскопических данных, и правоохранительные службы других стран следуют их примеру. Вейвлеты позволяют не просто анализировать изображения, а сжимать их.
В JPEG изображения сжимаются за счет отбрасывания информации, которая не слишком важна для человеческого зрения. Однако информация редко бывает представлена таким образом, что сразу становится очевидно, какие из битов можно считать лишними. Предположим, вы хотите отправить другу по электронной почте рисунок, сделанный на довольно грязном листе бумаги. Помимо собственно рисунка, на нем видно множество мелких черных пятнышек. Мы с вами, взглянув на этот рисунок, сразу понимаем, что эти пятнышки не важны, но сканер этого понять не может. Он просто сканирует лист, представляя изображение в виде длинной строки двоичных черно-белых сигналов, и не может определить, является ли какое-то черное пятнышко значимой частью рисунка или случайной помаркой. Некоторые «помарки», кстати говоря, могут в реальности оказаться зрачком далекой коровы или пятнышками мультяшного леопарда.
Главное препятствие заключается в том, что сигналы сканера не представляют данные об изображении в таком виде, который облегчал бы распознавание и устранение нежелательных элементов. Однако существуют и другие способы представления данных. Преобразование Фурье заменяет кривую списком амплитуд и частот, кодируя ту же самую информацию иначе. А когда данные представляются разными способами, то операции, которые сложны или невозможны в одном случае, могут стать простыми в другом. Например, вы можете взять телефонный разговор, применить к нему преобразование Фурье, а затем удалить все те части сигнала, фурье-компоненты которых имеют частоты слишком высокие или слишком низкие для человеческого уха. После этого вы можете применить к результату обратное преобразование Фурье и получить звук, идентичный с точки зрения человеческого восприятия оригиналу. Таким образом можно передавать больше разговоров по тому же каналу связи. Но в эту игру невозможно играть с оригинальным непреобразованным сигналом, поскольку у него нет «частоты» как очевидной характеристики.
Для некоторых целей метод Фурье обладает одним-единственным недостатком: синусовые и косинусовые компоненты продолжаются до бесконечности. Преобразование Фурье плохо представляет компактный сигнал. Единичный «всплеск» – простой сигнал, но для получения хотя бы умеренно убедительного всплеска требуются сотни синусов и косинусов. Проблема не в получении правильной формы всплеска, а в том, чтобы сделать все за его пределами равным нулю. Приходится избавляться от бесконечно длинных волнистых хвостов всех синусов и косинусов и, как следствие, добавлять еще более высокочастотные синусы и косинусы в отчаянной попытке компенсировать нежелательный мусор. В конечном итоге преобразованный вариант становится более сложным и требует больше данных, чем первоначальный всплеск.
Преобразование элементарных волн, или вейвлет-преобразование, полностью меняет ситуацию, поскольку использует в качестве базовых компонентов всплески (вейвлеты). Это непросто, и это нельзя сделать с любым подвернувшимся всплеском, но математику ясно, с чего следует начинать. Выбираем конкретную форму всплеска, которая будет служить материнским вейвлетом. Получаем дочерние вейвлеты (а также внучатые, правнучатые и т. д.), сдвигая материнский вейвлет вбок в различные позиции, а также расширяя или сжимая при помощи изменения масштаба. Чтобы представить более общую функцию, добавляем подходящие кратные этих вейвлетов на различных масштабах. Точно так же базовые синус и косинус фурье-преобразования являются «материнскими синусоидами», а синусы и косинусы всех остальных частот – дочерними по отношению к ним.