Инструменты сжатия растровых изображений на основе wavelet-технологий становятся в геоинформатике всё популярнее и востребованнее

В настоящее время все большую популярность среди геоинформатиков получают инструменты сжатия растровых изображений на основе вэйвлет-технологий (от английского “wavelet”, в российской литературе их еще называют “всплесками”). Вэйвлеты все чаще используются для компрессии изображений, так как позволяют сжимать растр во много раз практически без геометрических искажений. На сегодняшний день существует три коммерческих продукта, предназначенных для работы с растровыми файлами, - это MrSID американской компании Lizardtech (www.lizardtech.com), ECW австралийской фирмы Earth Resource Mapping (www.ermapper.com) и DejaVu от Bell Laboratories, который, кстати, также распространяется компанией Lizardtech. Первый и второй продукты распространены гораздо шире, чем третий, поэтому сосредоточимся на них.

Инструменты для компрессии растровых изображений на основании вэйвлет-анализа полезны в области наук о Земле, где часто приходится иметь дело с аэрофотоснимками и картами огромных размеров. Компрессоры и декомпрессоры на основе вэйвлет-технологий работают быстро и эффективно: так, сжатие изображения размером порядка 90 Мб происходит примерно за 2 мин. Результирующий файл при масштабе компрессии 1:100 занимает менее 1 Мб, причем разница в обоих изображениях - исходном и обработанном, - скажем прямо, в глаза не бросается.

Сферы применения столь эффективного инструмента сжатия многообразны - например, он используется при передаче данных со спутника на приемную станцию. Эту задачу нужно выполнить быстро, так как существует ограничение на время передачи, и без потери качества (или с такими потерями, которые могут быть восстановлены впоследствии). Существует два метода - по первому из них сжатие данных происходит перед их передачей, с тем чтобы она заняла не более 40 мин (среднее время связи со станцией), второй предусматривает хранение данных на спутнике, а при переходе спутника к следующей станции приема - их передачу порциями с разной степенью компрессии, т. е. сначала передаются сильно сжатые данные, позволяющие операторам на Земле оценить ценность содержащейся на снимках информации. Конечно, оба способа требуют наличия на спутнике специального оборудования. Важную роль методы компрессии, основанные на вэйвлет-анализе, играют при создании кадастров. При этом часто сканируется большое количество карт, планов-схем и т. д. Все исходные растровые изображения можно хранить на сервере, а для работы пользователей вполне достаточно точности, обеспечиваемой сжатым изображением. Разница между исходным файлом и сжатым изображением практически незаметна, даже если произведено сжатие в сотню раз. Бывали случаи, когда архив карт, занимающий 650 Мб, сжимали до 1 Мб. Многие разработчики ГИС уже встроили возможности работы с вэйвлет-компрессией в свои продукты.

Кстати, одним из самых известных проектов применения вэйвлет-анализа для хранения изображений является база данных ФБР с отпечатками пальцев всех граждан Соединенных Штатов (да и не граждан тоже). Эта база помещается на одном CD, который есть в каждой полицейской патрульной машине.

Краткое введение в технологии wavelet

Вэйвлет-анализ бывает ортогональным и непрерывным. Последний производится следующим образом: берется одна из двух функций, изображенных на рисунке (та, которая более соответствует характеру анализируемой функции), и используется в качестве базисной при аппроксимации примерно так же, как это происходит в преобразовании Фурье. Об ортогональном вэйвлет-анализе можно подробно прочитать в статье Леонида Левковича-Маслюка “Дайджест вэйвлет-анализа в двух формулах и 22 рисунках” на сайте: www.vsma.ac.ru/~gai/wavelet/4.1.html или в работе “Вэйвлет-анализ в картинках”, опубликованной в этом номере PC Week/RE.

Два самых популярных вэйвлета: “сомбреро” (а) и вэйвлет Морле (б)

Два слова об истории MrSID и ECW

MrSID пришел из исследовательского центра Los Alamos, где методы обработки изображений, основанные на вэйвлетах, реализовывались по заказу правительства США - необходимо было обрабатывать мгновенные снимки камер и данные датчиков, регистрировавших взрывы бомб и другую подобную информацию. Сотрудники этого центра впоследствии основали компанию Lizardtech, занимающуюся коммерческим распространением формата MrSID. Директор компании ER Mapper Ричард Никсон в течение 22 лет работал в NASA и по существу являлся заказчиком этого ПО. Позже г-н Никсон вернулся в Австралию и основал там компанию Earth Resource Mapping, разработчика популярной ГИС ER Mapper и формата ECW. Впоследствии компания Lizardtech обвинила ER Mapper в использовании при разработке ECW конфиденциальных сведений, полученных в период работы Никсона и других его сотрудников на правительство США, - это вовсе не значит, что компанию Никсона обвиняли в применении вэйвлет-анализа, поскольку это примерно то же самое, что обвинить кого-то в неправомерном использовании преобразования Фурье, - нет, речь шла только о конфиденциальных сведениях, которые, как установил недавно завершившийся суд, компания ER Mapper не использовала. Другими словами, ноги у ECW и MrSID растут из лаборатории Los Alamos так же, например, как почти у всех основных современных браузеров - из CERN. Но реализация продуктов различна - MrSID (Multiresolution Image Database) параметры для расчетов берет из базы данных, а ECW (Enhanced Compressor Wavelet) рассчитывает эти же параметры “на лету”, с помощью алгоритмов, встроенных в пакет ER Mapper.

Фрагменты одного и того же изображения, сжатые MrSID (вверху) и ECW - разница практически незаметна

MrSID и ECW: сходство и различия

Если изображение является стандартным и принадлежит к распространенному типу (например, аэрофотоснимок или изображение, полученное с помощью электронного микроскопа), то MrSID сжимает его эффективнее, чем ECW. Это происходит за счет того, что в базу данных MrSID разработчики уже занесли параметры потока, который должен обрабатываться в ходе работы с изображением.

Другое дело - уникальные изображения, в процессе их сжатия лучше использовать ECW, так как он при расчетах применяет алгоритмы, полученные при классификации изображения с помощью мощного пакета ER Mapper.

Сходства и различия ECW и MrSID

Ядро же, основанное на вэйвлетах, в обеих системах одинаковое, отличается только программная реализация и настройки, в данном случае представляющие собой априорное знание о параметрах фильтров, которые нужно применять для работы. Считается, что ECW, созданный на базе ER Mapper, больше подходит для подготовленного пользователя, при желании способного изучить программный код, реализующий тот или иной алгоритм, и написать свой скрипт на языке Си. В MrSID встроенного языка написания приложений, к сожалению, нет.

Если провести сжатие одних и тех же файлов с помощью MrSID и ECW, то на некоторых изображениях разница видна невооруженным глазом. Правда, дело тут не в принципиальных различиях между продуктами, а в конкретных настройках, которые можно подобрать и так, что никакой разницы видно не будет. В целом сравнение MrSID и ECW напоминает сравнение “Лексуса” с “Тойотой” - оба ездят, и неплохо, отличия только в деталях (так, ECW поддерживает больше форматов, а MrSID платформно-независим и может использоваться в аппаратных ускорителях сжатия). Таким образом, выбор - исключительно дело вкуса пользователя.

Скорость компрессии/декомпрессии зависит в основном от кодирования. Но, по нашему глубокому убеждению, этот показатель не принципиален: далеко не все задачи требуют оптимизации по скорости (одной из них, кстати, и является передача данных со спутника). Большинство же задач все же не накладывает особых требований на скорость, и поэтому 20%-ная разница в производительности, которая в целом выше у ECW при использовании универсальных процессоров и операционных систем, не так уж и важна (это только статистическая закономерность - среди файлов, как мы отмечали выше, попадаются и те, с которыми MrSID работает значительно быстрее ECW).

По мнению специалистов ЭСТИ-МАП (www.esti-map.ru) Алексея Колотова и Бориса Рубцова, ядро, реализующее алгоритм компрессии, эффективнее работает у MrSID, но этот продукт проигрывает в скорости чтения файла и развертывания его в памяти. Тем не менее уместно сослаться на создателя dBase Уэйна Рэтлифа, который, отвечая на вопрос о проблеме производительности, сказал когда-то: “Я считаю, что затраты сил и времени на приведение программы к суперпроизводительности нерентабельны, так как через полгода появится новый процессор”. Другими словами, если можно выиграть 10% производительности, затратив на это полгода времени и много усилий, то лучше просто подождать появления нового процессора и падения цен на модули памяти. В среднем MrSID требует больше памяти, так как использует большую эвристическую базу данных.

В целом оба продукта отлично справляются с решением своей основной задачи - сжимают изображения быстро и качественно.

Вэйвлет-анализ в картинках

Напомним простейшую схему фильтрации сигналов (см. рис. 1):

- низкочастотная фильтрация фильтром Н - обычное локальное усреднение, т. е. замена выходного отсчета средним значением нескольких предшествующих входных отсчетов;

- высокочастотная фильтрация фильтром G - вычитание из каждого отсчета локального среднего.

Рис. 1. Фильтрация сигналов

Теперь можно проредить низкочастотную и высокочастотную части и сохранить их по отдельности. А затем - вытащить их, дополнить прореженные отсчеты (например, интерполировать с соседними) и сложить. Получившийся сигнал будет очень близок к исходному.

Аналогичным образом изображение можно разделить на низкочастотные (основную сцену) и высокочастотные (границы контуров и мелкие детали) компоненты. Для этого используются вэйвлеты - низкочастотные фильтры Н и высокочастотные G. От приведенной выше иллюстрации они отличаются только тем, что отсчеты сигнала/изображения суммируются не с единичными, а со специальным образом выбранными весами.

Изображение преобразуется по следующей схеме.

А. Берем исходное изображение (матрица А размером N х N) и:

- фильтруем все строки фильтром Н (выделяем низкие частоты);

- фильтруем все столбцы фильтром H (выделяем низкие частоты).

В результате получаем размытое изображение.

Прореживаем его через один элемент, для чего из результата фильтрации выбираем элементы:

(0,0) (0,2), (0,4)+

(2,0) (2,2), (2,4)+

и т. д,

т. е. создаем новую матрицу HH размером (N/2 х N/2) элементов (та же картинка, но поменьше).

Б. Снова берем исходное изображение (матрица А размером N х N) и опять:

- фильтруем все строки фильтром Н (выделяем низкие частоты);

- фильтруем все столбцы фильтром G (выделяем высокие частоты).

В результате получаем странное изображение - вдоль оси X размытое, а вдоль оси Y - только контуры. Также прореживаем его через один элемент и создаем вторую матрицу HG размером N/2 х N/2.

В. Опять берем исходное изображение (матрица А размером N х N) и:

- фильтруем все строки фильтром G (выделяем высокие частоты);

- фильтруем все столбцы фильтром Н (выделяем низкие частоты).

И опять получаем странное изображение - размытое вдоль оси Y и контуры вдоль оси X.

Проредив его через один элемент, создаем еще одну матрицу HG размером N/2 х N/2.

Г. Еще раз берем исходное изображение и фильтром G фильтруем все строки и все столбцы (выделяем высокие частоты). И опять - странное изображение: одни контуры.

Снова прореживаем его через один элемент и получаем матрицу GG размером N/2 х N/2.

Матрицы GH, HG и GG размещаем и сохраняем так, как это показано на рис. 2, а с матрицей НН еще раз поступим вышеозначенным образом и снова получим четыре матрицы - HH, HG, GH, GG, но уже размером N/4 х N/4.

Рис. 2. Вэйвлет-анализ изображения

И так будем делать несколько раз, пока не получим маленькое-премаленькое сжатое изображение и дерево матриц, которое содержит отличия от исходного.

Для того чтобы восстановить изображение, сделаем все наоборот: профильтруем самую маленькую матрицу изображения и добавки к ней фильтрами H* и G* (индекс * означает комплексное сопряжение) и сложим их. Это даст нам следующую матрицу изображения с вдвое лучшим разрешением, а у нас и к ней есть добавки; мы все это снова профильтруем и сложим, и так далее, пока не получим исходное изображение.

Фокус в том, что если вэйвлет - фильтры H и G - грамотно подобран, то в этих “матрицах-отличиях” (GH, HG, HH) очень много маленьких элементов, которые с незначительным ухудшением качества восстановленного изображения можно выкинуть (заменить на ноль), что и позволяет использовать для хранения исходного изображения размером N х N гораздо меньший объем данных.

См. примечание в PC Week/RE N 23/2001 с. 29