От плохого качества картинки к хорошему - концепция «сжатых измерений»

В Детском госпитале Люсиль Паккард (Lucile Packard Children's Hospital) в Пало-Альто, Калифорния, есть весьма любопытный магнитно-резонансный томограф. Интересен он тем, что для получения сверхдетализированного изображения сканируемого органа используется принцип «сжатых измерений» (compressed sensing). Это – новейшее слово в прикладной математике, новая теория обработки сигналов. В будущем она может изменить наш подход к тому, как мы смотрим на далекие галактики.

Для начала немного истории. «Сжатые измерения» были открыты случайно. В 2004 году Эммануэль Кандс (Emmanuel Candès) разглядывал изображение, известное как «Фантом Шеппа-Логана» (Shepp-Logan Phantom). Эта картинка используется учеными и исследователями для «обкатки» и проверки различных алгоритмов обработки изображения. Кандс, будучи на то время профессором Калифорнийского технического института, а ныне – Стэнфорда, экспериментировал с очень искаженной версией изображения, которая была аналогом плохого результата сканирования на томографе (например, если сканирование прервали или оно проводилось гораздо меньше требуемого времени). Профессор подумал, что математическая техника, носящая название l1 minimization, позволит уменьшить степень искажения картинки, и запустил алгоритм обработки.

Кандс ожидал, что изображение станет чуть более чистым. Каково же было его удивление, когда «фантом», как по волшебству, стал идеально четким и чистым. «Это невозможно» - сказал Кандс тогда, – «это как если бы вы дали мне первые три цифры 10-значного банковского счета, а я бы назвал вам остальные семь». Ученый проверял алгоритм на «фантомах» самого разного качества – и всегда изображения на выходе получались кристально чистыми. Затем мистер Кандс обратился за помощью к Джастину Ромбергу (Justin Romberg) и Терри Тао (Terry Tao), и устроил коллективный мозговой штурм. Результаты их размышлений легли в основу первой письменной работы о «сжатых измерениях».

Алгоритму compressed sensing всего шесть лет, однако он уже изменил понимание того, как можно работать с большими массивами данных. Написаны тысячи научных работ на эту тему, выдано множество государственных грантов на миллионы долларов. В 2006 году Кандс удостоился премии Алана Уотермана, сумма которой составляет $500 тыс. Премия считается наивысшей наградой, которую может получить ученый в США, причем кандидату должно быть не больше 35 лет.

Нетрудно понять, за что ученому выпала такая честь. Представьте томограф, который получает детальное изображение за считанные секунды - вместо нескольких часов, или военное программное обеспечение, эффективно перехватывающее неприятельские переговоры, или аппаратуру, быстро анализирующую радиоволны из далеких миров. Варианты применения «сжатых измерений» бесконечны…