Применение вейвлет-преобразований для обработки картографических данных в экологической ГИС

Размещено на http://www.allbest.ru/

Применение вейвлет-преобразований для обработки картографических данных в экологической ГИС

Белов А.А., Кропотов Ю.А.

The represented problem of this article is the application of wavelet-transformation for cartographical data processing in GIS. The considered problems are electronic map compression on the base of original cartographical image transformation into the massive of wavelet transformation coefficients, operations with maps. The article contains a proposed alternative strategy of graphical information database search on the basis of metric-signature formation of inquired image and original image received from wavelet-transformation

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

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

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

Термин вейвлет-преобразование объединяет два вида преобразований - прямое и обратное, которые, соответственно, переводят исследуемую функцию f(x) в набор вейвлет-коэффициентов W(a,b)f и обратно [1].

Прямое вейвлет-преобразование осуществляется согласно правилу:

,(1)

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

Базисный, или материнский, вейвлет образует посредством растяжений и сдвигов семейство .

Имея известный набор коэффициентов , можно восстановить исходный вид функции f(x):

. (2)

В области обработки картографической информации, использование вейвлет-преобразований связано, прежде всего, с алгоритмами сжатия, обработки изображений и формирования запросов на изображения. [3]

Проблема сжатия изображений весьма актуальна при передаче и хранении растровых данных ГИС. Размер одного космического снимка может превышать размеры 60006000 точек и составлять сотни мегабайт. То же можно сказать и об электронных растровых картах высокого разрешения.

Метод сжатия изображений на основе вейвлет-преобразования проводится по следующему алгоритму:

- преобразование цветового пространства;

- вейвлет-преобразование;

- квантование;

- кодирование.

После преобразования в цветовое пространство типа цветность/яркость изображение обрабатывается высокочастотным и низкочастотным фильтрами по строкам и столбцам с последующим прореживанием. Фильтр представляет собой небольшое «окно». Значения яркости и цветности попавших в него пикселей умножаются на заданный набор коэффициентов, а полученные значения суммируются, и «окно» сдвигается для расчета следующего значения.

В результате фильтрации вместо одного изображения размером mxn вейвлет-преобразование дает четыре изображения размером (m/2) x (n/2). Фильтрация низкочастотным фильтром по горизонтали и по вертикали дает самое высокоинформативное изображение, которое подвергается дальнейшей фильтрации (число уровней фильтрации обычно составляет от 4 до 6), тогда как результат обработки высокочастотным фильтром по горизонтали и по вертикали чаше всего отбрасывается.

Общий подход к сжатию изображений при помощи вейвлет-преобразования состоит в следующем:

Над исходным изображением F выполняется вейвлет-преобразование

,(3)

где FWT - оператор вейвлет-преобразования,- массив вейвлет-коэффициентов.

- коэффициенты упорядочиваются по убыванию;

- отбрасывается “хвост” упорядоченного массива, энергия которого минимально допустима;

- запоминаются сохраненные коэффициенты и их положение в массиве исходных коэффициентов;

- при восстановлении отброшенные коэффициенты заменяются нулями.

Эта идея в той или иной форме присутствует во всех методах вейвлет - сжатия. Данную процедуру можно, например, применять раздельно к каждому из квадрантов, полученных при разложении по оптимально выбранным вейвлет-пакетам [2].

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

Результатом вейвлет-разложения двумерного сигнала f(x,y) (изображения) будет массив детализирующих числовых коэффициентов преобразования, полученных для различных масштабов рассмотрения i :

, ,

, , (4)

таких, что:

, (5)

где - двумерная скейлинг функция, представляющая собой тензорное произведение одномерных функций,

, , - вейвлет функции [2].

Затем массив коэффициентов подвергается кодированию.

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

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

Хранение изображений в виде усеченных наборов вейвлет-коэффициентов дает в настоящее время наилучший выигрыш по коэффициенту сжатия. Это во многом и определяет интерес к проведению остальных процедур обработки в области вейвлет-коэффициентов.[2]

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

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

Рассмотрим альтернативную стратегию поиска картографического изображения в базе данных изображений, в которой запрос выражается либо как изображение с низким разрешением, полученное с помощью сканера или видеокамеры, либо как грубый набросок искомого изображения, нарисованный самим пользователем. Этот базовый подход к формированию запроса изображе-ния получил различные названия, среди которых «поиск по запросу», «поиск по содержанию», «поиск по эскизу» [4].

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

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

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

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

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

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

Чтобы выполнить такое упорядочивание, необходимо определить мет-рику формирования запроса изображения (image quering metric), в которой задействованы укороченные квантованные версии вейвлет-разложений, на-зываемые сигнатурами (signatures). Эти сигнатуры содержат только самую существенную информацию о каждом изображении. По существу, метри-ка формирования запроса изображения сличает, сколько общих значимых вейвлет-коэффициентов имеется у изображения-запроса и у потенциаль-ных целевых изображений. Используя статистические методы можно про-изводить настройку такой метрики для того, чтобы наиболее эффективным образом выполнять распознавание для различных типов формирования за-просов по содержанию, скажем, для формирования путем сканирования и для формирования путем рисования от руки.

Применение переменного разрешения при формировании запроса обес-печивает множество преимуществ перед другими методами. Использование вейвлетов позволяет задавать запрос при любом разрешении (потенциаль-но отличном от разрешения целевого изображения); более того, хранение и продолжительность выполнения этого метода с переменной разрешающей способностью не зависят от разрешений изображений, хранимых в базе дан-ных. В дополнение ко всему, информацию, содержащуюся в сигнатуре, мож-но извлекать по требованию алгоритма непосредственно из вейвлет-сжатых версий изображения, что позволяет сформировать базу данных сигнатуры из множества сжатых изображений. Наконец, этот алгоритм гораздо легче реализовать и использовать по сравнению с большинством предшествую-щих подходов [5].

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

Двумерное вейвлет-преобразование может служить прекрасным «фундаментом» для формирования таких метрик по следующим причинам:

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

- вейвлет-разложения можно использовать для извлечения и кодирова-ния информации о контурах изображения, которые, вероятно, можно отнести к основным характеристикам изображения-запроса, в случае если последнее нарисовано пользователем;

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

- вейвлет-разложение вычисляется легко и быстро, программа для вы-полнения разложения очень короткая, а время ее выполнения линейно зависит от размера изображения [4].

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

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

Для изображений форматом 128 х 128 каждому цветовому каналу соответствует последовательность из 128² = 16384 различ-ных вейвлет-коэффициентов. Вместо использования в метрике всей последовательности было бы предпочтительнее произвести ее усече-ние и оставить в ней только коэффициенты с наибольшими значениями. Выполнение такого усечения способствует как ускорению поиска, так и уменьшению объема памяти для хранения базы данных [4]

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

В целом, алгоритм сводится к следующему:

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

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

Рисунок 1 - Процесс формирования сигнатуры

Одна из возможных L^q - метрик формирования запроса изображения может иметь следующий вид:

,(6)

где Q и J - сигнатуры исходного изображения и изображения-запроса соответственно. Весовые коэффициенты обеспечивают удобный механизм настройки метрики на различные базы данных и типы формирования запросов.

Схема процесса обнаружения изображения по нечеткому запросу приведена на рисунке 2.

Рисунок 2 - Схема процесса обнаружения изображения по нечеткому запросу

Работа осуществлена при поддержке РФФИ по проекту 06-07-96501.

ЛИТЕРАТУРА

1. Добеши, И. Десять лекций по вейвлетам [Текст] / И. Добеши. - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2001.- С. 28-30.

2. Жизняков, А.Л. Вейвлет-обработка изображений в ГИС [Текст] / А.Л. Жизняков, Н.В. Вакунов //Современные проблемы информатизации Сб. трудов. Вып.10 / Под ред. д.т.н., проф. О.Я. Кравца. - Воронеж: Научная книга, 2005. - С. 9495.

3. Смоленцев, Н.К. Основы теории вейвлетов. Вейвлеты в MATLAB [Текст] / Н.К. Смоленцев. - М.: ДМК Пресс, 2005.-С. 68.

4. Столниц, Э. Вейвлеты в компьютерной графике [Текст] / Э. Столниц, Т. ДеРоуз, Д. Салезин - Ижевск: НИЦ «Регулярная и хаотическая динамика», 2002.- С. 44-46, 61-66.

5. Jacobs, Ch.E. Fast multiresoluting image quering [Text] / Ch.E. Jacobs, A. Finkelstein, D.H. Salesin // In Proceedings of SIGGRAPH '95. - New York: ACM, 1995. - P. 277-282.

Размещено на Allbest.ru