Архив

Архив раздела ‘Математика’

Два примера вейвлет-анализа

12 Май 2013 Сергей Сергеевич Comments off

На сегодня примеров вейвлет-анализа так много, что я ограничусь только двумя примерами, понятные всем нам, простым смертным:)

1. Сжатие данных

Сжимать те или иные данные приходится, например, если надо хранить их в компьютере с ограниченной памятью или же если требуется передать большой объем информации через линию связи с ограниченной пропускной способностью.

Хорошо известен пример, когда ФБР использовало вейвлет-анализ для сжатия информации, в результате чего удалось хранить боль­шое количество отпечатков пальцев в сравнительно небольших компьютерах, что в свою очередь позволило сэкономить заметные средства.

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

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

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

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

В разных ситуациях требуется выбрать разные вейвлеты для оптимизации всей проце­дуры анализа и синтеза. В любом случае вейвлет-анализ имеет преимущество по сравнению с методами кодиро­вания, использующими  преобразование Фурье.

Любое изображение, вводимое в компьютер, оцифровывается и хранится в нем в виде так называемой битовой карты (bitmap) или, иначе говоря, матрицы, каждый элемент которой описывает цвет точки на исходном изображении.

Количество эле­ментов матрицы (точек изображения) зависит от разре­шения, выбранного при оцифровке. Именно битовая карта используется для последующего воспроизведения «картинки» на экране, печатающем устройстве и т.п. Однако хранить ее в таком виде невыгодно из-за использования   большого   количества   компьютерной памяти.

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

сжатие без потери (когда исходная битовая карта полностью восстанавливается в результате процедуры декодирования) и с потерей информации. В более общем применении алгоритмы первой группы часто назы­ваются архивацией данных.

В качестве иллюстрации рассмотрим более подробно алгоритм сжатия изображений с потерей информации. Потеря информации в данном случае означает, что восстановленная картинка не будет абсолютно точно совпадать с исходной, однако различия будут практиче­ски незаметны для человеческого глаза.

В настоящее время большинство хранящихся на компьютерах изображений (в том числе используемых в Интернете) с непрерывным цветовым тоном сжимается с помощью алгоритма JPEG.

Основные стадии этого алгоритма следующие. Изображение разбивается на шаблоны 8×8 точек. Для каждого шаблона (мат­рицы) выполняется дискретное косинус-преобразование. Далее из получившихся частот с помощью специальной весовой таблицы отбираются наиболее существенные для визуального восприятия.

Эта процедура называется квантованием и является единственным этапом, на котором происходит потеря информации. Далее мат­рица отобранных частот представляется компактным образом и кодируется так называемым энтропийным методом (хаффмановским или арифметическим).

Volki

На этом рисунке показаны оригиналь­ное изображение и восстановленные после сжатия по JPEG-алгоритму и по вейвлет-алгоритму.

Легко видеть, что при практически одинаковых размерах закодирован­ных файлов качество «вейвлет-картинки» существенно выше (крайний справа волк).

Требование одинаковости качества приводит к выигрышу по размерам файла в 1,5-2 раза в случае вейвлет-алгоритма, что может оказаться существенным для передачи изображений, особенно если пропускная способность передающей линии ограничена.

2. Клетки крови

Читать далее…