Слева: кривая синуса продолжается бесконечно. В центре: вейвлет локализован. Справа: еще три поколения
Вейвлеты придуманы для эффективного описания всплескоподобных данных. Более того, поскольку дочерние и внучатые вейвлеты представляют собой всего лишь отмасштабированные версии материнского, можно сосредоточиться на конкретных уровнях детализации. Если вы хотите устранить мелкомасштабную структуру, то удаляете все праправнучатые вейвлеты в вейвлет-преобразовании. Представьте себе превращение леопарда в вейвлеты – несколько крупных для тела, более мелкие для глаз, носа и пятен, затем совсем крохотные для шерстинок. Стремясь сжать эти данные, но сохранить их внешнее сходство с леопардом, вы решаете, что отдельные шерстинки не имеют значения, и удаляете все праправнучатые вейвлеты. Пятна остаются, и в целом все по-прежнему выглядит как леопард. Нечто подобное очень трудно – а то и вообще невозможно – сделать при помощи преобразования Фурье.
Подавляющая часть математических инструментов, необходимых для создания вейвлетов, существовала на тот момент в абстрактном виде уже полстолетия и даже больше в области функционального анализа. Когда вейвлеты получили известность, выяснилось, что заумный аппарат функционального анализа – это именно то, что требуется для их понимания и превращения в эффективный метод. Главным предварительным требованием для того, чтобы машина функционального анализа заработала, является хорошая форма материнского вейвлета. Мы хотим, чтобы все дочерние вейвлеты были математически независимы от матери, чтобы информация, закодированная матерью и дочерью, не перекрывалась и чтобы ни одна часть ни одной дочери не была избыточной. Говоря языком функционального анализа, мать и дочь должны быть ортогональны.
В начале 1980-х годов геофизик Жан Морле и специалист по математической физике Александр Гроссман предложили реалистичный материнский вейвлет. В 1985 году математик Ив Мейер доработал вейвлеты Морле и Гроссмана. Открытие, широко распахнувшее перспективы в этой области, сделала в 1987 году Ингрид Добеши. Предыдущие материнские вейвлеты выглядели надлежаще похожими на всплески, но все они имели крохотный математический хвостик, который волнами убегал в бесконечность. Добеши построила материнский вейвлет совсем без хвоста: за пределами определенного интервала мать всегда в точности равна нулю. Ее материнский вейвлет представлял собой настоящий всплеск, полностью заключенный в конечную область пространства.
Вейвлеты действуют как своего рода числовое увеличительное стекло, сфокусированное на свойствах данных, которые занимают конкретные пространственные масштабы. Эта способность может быть использована не только для анализа данных, но также и для их сжатия. Манипулируя вейвлет-преобразованием, компьютер «прищуривается» на изображение и отбрасывает нежелательные масштабы разрешения. Именно это решило сделать ФБР в 1993 году. В то время дактилоскопическая его база данных содержала 200 млн записей, которые хранились в виде чернильных отпечатков на бумажных карточках. В процессе модернизации эти изображения оцифровывались, а результаты закладывались в компьютер. Очевидным преимуществом новой системы была возможность быстро искать в базе соответствия отпечаткам, найденным на месте преступления.
Традиционное изображение с достаточным разрешением дает компьютерный файл объемом 10 Мб для каждой карточки с отпечатками. Архив ФБР занимает 2000 терабайт памяти. Каждый день в него поступает по крайней мере 30 000 новых карточек, так что требования к объему хранилища возрастают на 2,4 трлн двоичных цифр ежедневно. ФБР отчаянно нуждалось в сжатии данных. Там пробовали JPEG, но этот формат бесполезен для отпечатков пальцев (в отличие от отпускных фоток), когда коэффициент сжатия – отношение размера первоначальных данных к размеру сжатых – становится высоким, примерно 10:1. Тогда сжатые изображения теряют смысл из-за так называемых артефактов в виде квадратиков, в которых деление на блоки 8 × 8 оставляет заметные границы. Естественно, метод был практически бесполезен для ФБР, если не мог обеспечить сжатия по крайней мере 10:1. Артефакты-квадратики – это не просто эстетическая проблема: они серьезно ухудшают способность алгоритмов проверять отпечатки пальцев на соответствие. Альтернативные методы на основе преобразования Фурье также привносили в изображения нежелательные артефакты, причем все они связаны с проблемой бесконечных «хвостов» в синусах и косинусах рядов Фурье. Так что Том Хоппер из ФБР и Джонатан Брэдли с Крисом Брислоном из Лос-Аламосской национальной лаборатории решили кодировать оцифрованные записи с отпечатками пальцев при помощи вейвлетов с использованием метода, известного как вейвлет-скалярное квантование, или, короче, WSQ.
Вместо того чтобы удалять избыточную информацию путем создания артефактов-квадратиков, WSQ удаляет мелкие детали по всей площади изображения – детали настолько мелкие, что они не влияют на способность глаза распознавать структуру отпечатка пальца. В проведенных ФБР испытаниях все три опробованных вейвлет-метода показали себя лучше двух фурье-методов, таких как JPEG. В итоге самым разумным методом оказался WSQ. Он обеспечивает коэффициент сжатия не менее 15:1, снижая стоимость хранения информации на 93 %. Теперь WSQ является стандартом для обмена и хранения отпечатков пальцев. Большинство американских правоохранительных органов пользуются им для сжатия отпечатков пальцев с разрешением 500 dpi (пикселей на дюйм). Для отпечатков с более высоким разрешением они используют JPEG{60}.
Вейвлеты появляются практически везде. Команда Денниса Хили применяет основанные на вейвлетах методы коррекции изображений к результатам КТ, ПЭТ и МРТ-сканирования. Они также используют вейвлеты для доработки стратегий, посредством которых сканеры получают свои данные. Рональд Койфман и Виктор Викерхаузер использовали их для удаления нежелательного шума в записях. Настоящим триумфом стало восстановление записи исполнения Иоганнесом Брамсом одного из своих «Венгерских танцев», сделанной на восковом валике в 1889 году, хотя он и был частично оплавленным. Запись перевели на диск так, что она воспроизводилась на скорости 78 оборотов в минуту. Койфман начал с того, что передал запись по радио, хотя к тому моменту музыка там была уже почти неслышна на фоне шума. После вейвлетной очистки на записи уже можно было услышать, что играет Брамс, – не идеально, но все же услышать.
Отпечатки пальцев. Слева: оригинал. Справа: после сжатия до 1/26 объема данных
Лет 40 назад функциональный анализ был всего лишь еще одной мудреной областью абстрактной математики, которая если где и применялась, то разве что в теоретической физике. Появление вейвлетов все изменило. Теперь функциональный анализ обеспечивает базу, необходимую для разработки новых типов вейвлетов с особыми свойствами, которые делают их применимыми в прикладной физике и технике. Сегодня вейвлеты незаметно вошли практически во все аспекты нашей жизни – они используются в сфере профилактики преступности, в медицине, в цифровой музыке нового поколения. Завтра они захватят весь мир.
11Мы уже почти приехали?
Путь в тысячу ли начинается с одного шага.
Этот сценарий знаком каждому родителю, который водит машину. Семья направляется в другой город навестить бабушку, до нее 400 с лишним километров и шесть часов езды. Дети разместились на заднем сиденье. Через полчаса после отправления сзади начинают ныть: «Мы уже почти приехали?»
Здесь у меня имеются разногласия с заокеанскими родичами, которые, похоже, убеждены, что фраза звучит немного иначе: «Мы уже приехали?» Может быть, в США спрашивают именно так, но это неверно, потому что такой вариант говорит о недопонимании. Ответ в этом случае всегда очевиден: мы либо приехали и тогда вопрос излишен, либо нет и тогда спрашивать бесполезно. Нет, на самом деле в любом долгом путешествии, когда дети начинают капризничать, добрые (или просто раздраженные) родители их успокаивают: «Уже почти приехали». Даже если до места добираться еще пять часов. На некоторое время это успокаивает детей. В любом случае после нескольких поездок дети начинают адресовать родителям этот вопрос скорее с отчаянием, чем с надеждой: «Мы уже почти приехали?» Это разумный вопрос, потому что определить местоположение, глядя в окно, невозможно. Если, конечно, вы не знаете местных ориентиров. У нас когда-то был кот, который их знал.
Мы уже почти приехали? Где мы сейчас? Два десятилетия назад для ответа на этот вопрос нужна была карта, хорошие навыки ее чтения и штурман на пассажирском сиденье. Сегодня эти задачи отданы на откуп всевозможным электронным помощникам. Вам достаточно посмотреть на прибор спутниковой навигации. Правда, он иногда заводит людей в чистое поле, где и бросает. Одна машина не так давно заехала по указаниям навигатора в реку. Так что на дорогу смотреть тоже полезно. Но даже эта предосторожность может не помочь. В прошлом году мы, занимаясь поисками придорожного мотеля, заехали во двор сельского дома, потому что наш спутниковый навигатор не смог отличить настоящую дорогу, похожую на подъездную дорогу к усадьбе, от подъездной дороги к усадьбе, похожей на настоящую дорогу.
Спутниковая навигация похожа на волшебство. У вас в машине есть экран, на котором видна часть карты. Эта карта показывает в точности, где вы находитесь. Вы едете вперед, и карта движется так, что символ, обозначающий вашу машину, всегда находится в правильном месте. Устройство знает, в каком направлении вы едете, ему известно название или номер дороги, на которой вы находитесь. Оно предупреждает вас о пробках. Оно знает, куда вы едете и как быстро, когда превышаете скорость, где находятся дорожные камеры и скоро ли вы окажетесь у ближайшей из них. Научите детей пользоваться этой информацией, и они перестанут спрашивать.