№12. Геоинформационные системы. Wavelet-анализ в ECW и MrSID: кто сильнее – кит или слон?

> Wavelet-анализ в ECW и MrSID: кто сильнее – кит или слон?
> Ольга Блинкова
> В настоящее время все большую популярность среди геоинформатиков получают инструменты сжатия растровых изображений на основе вэйвлет-технологий (от английского “wavelet”

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

> , в российской литературе их еще называют “всплесками”). Вэйвлеты все чаще используются для компрессии изображений, так как позволяют сжимать растр во много раз практически без геометрических искажений. На сегодняшний день существует три коммерческих продукта, предназначенных для работы с растровыми файлами, — это MrSID американской компании Lizardtech (http://www.lizardtech.com/), ECW австралийской фирмы Earth Resource Mapping (http://www.ermapper.com/) и DejaVu от Bell Laboratories, который, кстати, также распространяется компанией Lizardtech. Первый и второй продукты распространены гораздо шире, чем третий, поэтому сосредоточимся на них.
> Инструменты для компрессии растровых изображений на основании вэйвлет-анализа полезны в области наук о Земле, где часто приходится иметь дело с аэрофотоснимками и картами огромных размеров. Компрессоры и декомпрессоры на основе вэйвлет-технологий работают быстро и эффективно: так, сжатие изображения размером порядка 90 Мб происходит примерно за 2 мин. Результирующий файл при масштабе компрессии 1:100 занимает менее 1 Мб, причем разница в обоих изображениях — исходном и обработанном, — скажем прямо, в глаза не бросается.
> Сферы применения столь эффективного инструмента сжатия многообразны — например, он используется при передаче данных со спутника на приемную станцию. Эту задачу нужно выполнить быстро, так как существует ограничение на время передачи, и без потери качества (или с такими потерями, которые могут быть восстановлены впоследствии). Существует два метода — по первому из них сжатие данных происходит перед их передачей, с тем чтобы она заняла не более 40 мин (среднее время связи со станцией), второй предусматривает хранение данных на спутнике, а при переходе спутника к следующей станции приема — их передачу порциями с разной степенью компрессии, т. е. сначала передаются сильно сжатые данные, позволяющие операторам на Земле оценить ценность содержащейся на снимках информации. Конечно, оба способа требуют наличия на спутнике специального оборудования. Важную роль методы компрессии, основанные на вэйвлет-анализе, играют при создании кадастров. При этом часто сканируется большое количество карт, планов-схем и т. д. Все исходные растровые изображения можно хранить на сервере, а для работы пользователей вполне достаточно точности, обеспечиваемой сжатым изображением. Разница между исходным файлом и сжатым изображением практически незаметна, даже если произведено сжатие в сотню раз. Бывали случаи, когда архив карт, занимающий 650 Мб, сжимали до 1 Мб. Многие разработчики ГИС уже встроили возможности работы с вэйвлет-компрессией в свои продукты.
> Кстати, одним из самых известных проектов применения вэйвлет-анализа для хранения изображений является база данных ФБР с отпечатками пальцев всех граждан Соединенных Штатов (да и не граждан тоже). Эта база помещается на одном CD, который есть в каждой полицейской патрульной машине.
> Краткое введение в технологии wavelet
> Вэйвлет-анализ бывает ортогональным и непрерывным. Последний производится следующим образом: берется одна из двух функций, изображенных на рисунке (та, которая более соответствует характеру анализируемой функции), и используется в качестве базисной при аппроксимации примерно так же, как это происходит в преобразовании Фурье. Об ортогональном вэйвлет-анализе можно подробно прочитать в статье Леонида Левковича-Маслюка “Дайджест вэйвлет-анализа в двух формулах и 22 рисунках” на сайте: http://www.vsma.ac.ru/~gai/wavelet/4.1.html или в работе “Вэйвлет-анализ в картинках”, опубликованной в этом номере PC Week/RE.
> Два слова об истории MrSID и ECW
> MrSID пришел из исследовательского центра Los Alamos, где методы обработки изображений, основанные на вэйвлетах, реализовывались по заказу правительства США — необходимо было обрабатывать мгновенные снимки камер и данные датчиков, регистрировавших взрывы бомб и другую подобную информацию. Сотрудники этого центра впоследствии основали компанию Lizardtech, занимающуюся коммерческим распространением формата MrSID. Директор компании ER Mapper Ричард Никсон в течение 22 лет работал в NASA и по существу являлся заказчиком этого ПО. Позже г-н Никсон вернулся в Австралию и оcновал там компанию 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, так как он при расчетах применяет алгоритмы, полученные при классификации изображения с помощью мощного пакета ER Mapper.
> Ядро же, основанное на вэйвлетах, в обеих системах одинаковое, отличается только программная реализация и настройки, в данном случае представляющие собой априорное знание о параметрах фильтров, которые нужно применять для работы. Считается, что ECW, созданный на базе ER Mapper, больше подходит для подготовленного пользователя, при желании способного изучить программный код, реализующий тот или иной алгоритм, и написать свой скрипт на языке Си. В MrSID встроенного языка написания приложений, к сожалению, нет.

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

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

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