«Всплеск, который быстро затухает»

В минувший вторник был объявлен лауреат Абелевской премии, или, как ее называют иначе, «Нобелевской премии по математике». Им стал Ив Мейер, французский математик, сыгравший «ключевую роль в развитии математической теории вейвлетов». Вейвлеты, или как их часто называют в русскоязычной традиции, всплески, — часть математической теории, широко используемой для обработки, сжатия и хранения информации. К примеру, они лежат в основе формата JPEG2000 и многих современных алгоритмов увеличения резкости в фоторедакторах. Чтобы узнать, что же такое всплески, мы обратились к доктору физико-математических наук Владимиру Юрьевичу Протасову, член-корреспонденту РАН и крупнейшему специалисту в области теории всплесков и выпуклой геометрии в России.

Абелевская премия вручается с 2003 года Норвежской академией наук. Лауреаты определяются на основе рекомендаций комитета премии, в который входят пять математиков, признанных на  международном уровне. В этом году членами комитета были Джон Рогнес, Марта Санс-Соле, Луиджи Амбросио, Мари-Франс Винера и Бен Грин. Размер премии составляет шесть миллионов норвежских крон (40,7 миллиона рублей).

N+1: Как все-таки правильнее перевести термин wavelet — вейвлет или всплеск?

Владимир Протасов: Можно и так и так. «Всплеск» чуть популярнее. В свое время были большие дискуссии на этот счет. Специалист по теории приближений, Константин Ильич Осколков, он работает в университете Южной Каролины, он и придумал это слово — «всплеск». Хотели назвать «волночка» или как-то еще, но прижилось слово «всплеск». Иногда говорят «вейвлет», но мне, например, «всплеск» больше нравится.

Очень хочется понять, как говорится, «на пальцах», что же это такое. Возникает ощущение, что всплески — это что-то очень близкое к преобразованию Фурье. Это так?

Всплески — это замена для преобразования Фурье. Дело в том, что у преобразования Фурье есть несколько непреодолимых недостатков. Если к периодической функции [которую мы раскладываем в ряд Фурье] добавить щелчок, который сначала ноль, потом резкий скачок, потом снова ноль, тогда все коэффициенты Фурье более или менее равномерно изменятся. Большинство шумов именно так и устроены — это очень сильно локализованные по времени, но большие по амплитуде функции – щелчок, скрип, стук, царапина на диске и так далее. Получается, что прибавление такого шума равномерно меняет все коэффициенты Фурье. Получив эти коэффициенты, мы не сможем определить, где находится источник шума, как его удалить.

Из-за этого с помощью преобразований Фурье очень сложно восстановить старую запись — например, пластинку или видеозапись. Скажем, помехи на старых фильмах выглядят как царапины или мелкие точки. Если мы применим к ним преобразование Фурье, а потом его округлим и применим обратное преобразование, то получим картину уже без точек и царапин. Но она будет равномерно размытой и нечеткой. Именно потому, что все коэффициенты Фурье «испортились».

Это связано с тем, что синус и косинус — функции, которые используются в преобразовании Фурье, — равномерны на всей прямой. Они не убывают на бесконечности. Если мы хотим создать систему функций, разложение по которой чувствительно к шуму, которое показывало бы, где находится шум, и позволяло его удалить, то нам надо выбрать локализованные функции. То есть они должны убывать: чем больше t (время), тем меньше значение функции. Например, 1/t, 1/t², e^-t. Это во-первых.

Во-вторых, хотелось бы иметь некоторую структуру этих функций. Чтобы они были как-то друг с другом связаны. Есть такая техника быстрого преобразования Фурье, которая позволяет вычислять коэффициенты разложения с помощью этой связи (рекуррентного соотношения) за очень короткое время. Хотелось бы это свойство также сохранить, а если возможно — улучшить.

Первая такая система функций появилась в 1909 году вне контекста любых приложений. Ее придумал венгерский математик Альфред Хаар. Он придумал такую систему функций, которая состоит из кусочно-постоянных ступенек. По ним можно раскладывать любую функцию и даже делать преобразования, аналогичные преобразованию Фурье. Они до сих пор широко используются, но у них есть существенный недостаток. Эта система состоит из разрывных функций (грубо говоря, в их графике есть разрывы). Из-за этого возникает много неудобств — она медленно сходится, то есть для хорошего приближения функции нужно хранить много коэффициентов разложения Хаара. Кроме того, не очень хорошо приближать разрывными функциями какие-то процессы реального мира, потому что все процессы в реальном мире непрерывны.

Появилась задача сделать систему функций как у Хаара, но чтобы функции были непрерывными и, более того, гладкими (имеющими производные, чем большего порядка, тем лучше). В 1933–1949 году появилась система функций Шеннона-Котельникова. Клод Шеннон — американец, а Владимир Александрович Котельников — советский математик и радиотехник. Эта система часто использовалась для хранения и обработки аудиозаписей и других сигналов. Функции в ней убывали на бесконечности довольно медленно — со скоростью примерно 1/t. Хотелось бы, чтобы они убывали еще быстрее — 1/t², а может и e^-t. С этого времени не прекращались попытки создать более эффективные функции.

Собственно, в 1986 году Ив Мейе́р создал такую систему. Это действительно был прорыв — до этого было непонятно, существуют ли они вообще. Он чуть-чуть поправил систему Шеннона-Котельникова, немного сгладил ступеньки в ней. Конструкция Мейера технически очень остроумная — практически «олимпиадная», но содержащая много тонких деталей. Если читать про нее лекцию, то полную полуторачасовую лекцию надо на нее потратить. И при этом не всякий курс это выдержит.

Система Мейера оказалась очень удобной. Функции в ней глаже некуда — аналитические, и при этом они очень быстро убывают на бесконечности.

А можно как-то представить графически, на что похожи всплески?

Давайте попробуем. Возьмем гиперболу — 1/x — и впишем в нее синусоиду. Получится синусоида с затухающими колебаниями. Посередине у нее будет ощутимый бугорок — это такая четная функция, которая большая в нуле и дальше колеблется в точности как синус и медленно затухает как гипербола. Это одна из функций Шеннона-Котельникова. Остальные функции — это ее двоичные сжатия (сжатие в 2ⁿ раз) и целые сдвиги. По такой счетной системе функций можно раскладывать или приближать любую функцию.

Функции в системе Мейера выглядят похоже — практически так же, но затухание происходит гораздо быстрее. Третье-четвертое колебание в ней уже несущественны. Это такой высокий бугорок, устроенный как косинус, но затухающий гораздо-гораздо быстрее, чем 1/x. Такой, действительно, всплеск в нуле, который очень быстро затухает. Функция существует на всей прямой, но при x=2, 3 она уже очень мала. Это именно такая волночка, а не волна которая, как синус, по всему морю распространяется. Тут именно всплеск — как будто камень бросили, и в одном месте возник всплеск, а дальше идет маленькая-маленькая волночка, которая затухает.

Говорят, что Абелевская премия — это «Нобель» в математике. Одно из требований к работам, за которые дают Нобелевскую премию, это практическое применение открытия. В прошлом году «Абеля» дали за доказательство Великой теоремы Ферма. Такое ощущение, что результаты, за которые вручена новая премия, гораздо более «прикладные».

Да. Они используется в алгоритмах сжатия и хранения информации и в численных решениях дифференциальных уравнений. Но скорее Мейер преодолел какой-то психологический барьер, показав, что такие функции вообще можно строить. Хаар — это все-таки 1909 год, а Мейер — 1986-й. Между ними была система Шеннона-Котельникова, но она была в некоторой степени естественна. Владимир Котельников даже не был математиком — он был радиоинженером. И свою систему он придумал из технических предпосылок, он взял их из жизни. Система Мейера же — чисто математическая конструкция. Очень нетривиальная, остроумная и совершенно искусственная. Мейер показал, что такими искусственными математическими конструкциями и нужно строить новые системы. Это в каком-то смысле значило, что не надо бояться использовать вещи, которые являются игрой разума. Не надо искать их в природе — их может и не быть. После Мейера разные системы всплесков стали появляться в больших количествах ежегодно. Сейчас их уже столько, что хватит на все случаи жизни.

Я читал, что анализ всплесков используется при поиске гравитационных волн, например. Сейчас это уже стало какой-то общепринятой техникой?

Не совсем. Это все-таки зависит от конкретной задачи. Вот, скажем, формат JPEG2000 уже целиком основан на вейвлет-преобразованиях. Но иногда, для разных классов изображений, там применяются другие методы – преобразование Габора, оконное преобразование Фурье и другие. Метод всплесков – мощный, но он не один, есть и другие. Все зависит от задачи.

А расскажите о каких-нибудь необычных применениях всплесков, с которыми вы сталкивались?

Несколько лет назад я был приглашенным профессором в Университете Эйндховена. Там мы консультировали группу математиков из Италии. У них была задача о старинных водопроводах. В маленьком городе есть водопровод, который был построен еще древними римлянами и сегодня иногда ломается. Где слабые места в этой системе, не очень понятно — раскапывать старинную часть города не разрешается. Поэтому единственное, что можно сделать, — подать в водопровод воду и аккуратно измерить давление, гидродинамический удар. И по этому гидродинамическому удару нужно рассчитать место, где произошла течь. А она может располагаться в ста метрах от места, где мы поставили датчик. Получается волновое уравнение, которое необходимо решить, а гидродинамический удар — это тот самый шум, который необходимо локализовать. Это такая функция-скачок. И они искали решения с помощью систем всплесков. То есть предполагаемое решение представлялось как сумма нескольких всплеск-функций, потом вычислялись коэффициенты и один из них был очень большим. Тут же они понимали с точностью до метра, где произошел прорыв и где можно копать и чинить. Получилась практическая задача, над которой пришлось поработать довольно долго.

Я также знаю, что вейвлет-преобразования используются в сканерах в аэропортах, при сканировании багажа. Но там используются не обязательно мейеровские всплески. Когда сканер обнаруживает мелкую железку в багаже, вейвлет-преобразование помогает локализовать сигнал от нее. Это я обсуждал с коллегами, которые участвовали в разработке этих программ — что там хорошо себя зарекомендовали именно системы всплесков.

А что сейчас происходит в теории вейвлет-преобразований?

Эйфория и самое бурное развитие теории всплесков пришлось на конец 1990-х — начало 2000-х годов. Можно сказать, произошел всплеск (смеется). Если вспомнить график функции Мейера, то у нас сейчас идет такое затухание интереса. Тем не менее во всей этой теории вопросов осталось больше, чем ответов. Систем всплесков действительно построено очень много, и они зарекомендовали себя в самых разных задачах, но сейчас наблюдается застой. Были и другие подходы, основанные на том, что можно ограничивать преобразования Фурье — так называемые оконные преобразования. В некоторых задачах, связанных с Интернетом и передачей изображения, модернизированное оконное преобразование Фурье, в свою очередь, теснит всплески. 

Кроме того, очень много вопросов осталось по поводу того, как построить систему всплесков на плоскости или в пространстве. То, о чем мы говорили, это система всплесков на прямой. Это необходимо, например, для той же самой компьютерной томографии. Если мы возьмем просто один всплеск Мейера по оси x и другой всплеск по оси y и просто их перемножим, то мы тоже получим всплеск-функцию. Но она будет неудобной и не будет обладать на плоскости теми же хорошими свойствами, что и на прямой. Они далеко не оптимальны. Кроме того, для ряда задач нужны системы функций, обладающие в пространстве определенной симметрией, например сферической, чтобы эти функции можно было, например, вращать. Дизайн таких функций это тоже самостоятельная задача.

Есть много математиков, которые не вникают в практическое содержание. Они просто работают с теоретическими задачами, связанными с теорией всплесков. Таких задач тоже накопилось очень много — они даже математически очень интересные по постановке. В настоящее время интерес к теме не такой большой, как лет 20 назад, но довольно много математиков в ней работает — в основном это зарубежные ученые, но есть и наши. Мне кажется, что с прогрессом компьютерных технологий всплески еще себя покажут. У меня есть ощущение, что их возможности и ресурс далеко не исчерпан.