геофизик Жан Морле и специалист по математической физике Александр Гроссман предложили реалистичный материнский вейвлет. В 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 с лишним километров и шесть часов езды. Дети разместились на заднем сиденье. Через полчаса после отправления сзади начинают ныть: «Мы уже почти приехали?»
Здесь у меня имеются разногласия с заокеанскими родичами, которые, похоже, убеждены, что фраза звучит немного иначе: «Мы уже приехали?» Может быть, в США спрашивают именно так, но это неверно, потому что такой вариант говорит о недопонимании. Ответ в этом случае всегда очевиден: мы либо приехали и тогда вопрос излишен, либо нет и тогда спрашивать бесполезно. Нет, на самом деле в любом долгом путешествии, когда дети начинают капризничать, добрые (или просто раздраженные) родители их успокаивают: «Уже почти приехали». Даже если до места добираться еще пять часов. На некоторое время это успокаивает детей. В любом случае после нескольких поездок дети начинают адресовать родителям этот вопрос скорее с отчаянием, чем с надеждой: «Мы уже почти приехали?» Это разумный вопрос, потому что определить местоположение, глядя в окно, невозможно. Если, конечно, вы не знаете местных ориентиров. У нас когда-то был кот, который их знал.
Мы уже почти приехали? Где мы сейчас? Два десятилетия назад для ответа на этот вопрос нужна была карта, хорошие навыки ее чтения и штурман на пассажирском сиденье. Сегодня эти задачи отданы на откуп всевозможным электронным помощникам. Вам достаточно посмотреть на прибор спутниковой навигации. Правда, он иногда заводит людей в чистое поле, где и бросает. Одна машина не так давно заехала по указаниям навигатора в реку. Так что на дорогу смотреть тоже полезно. Но даже эта предосторожность может не помочь. В прошлом году мы, занимаясь поисками придорожного мотеля, заехали во
