Смекни!
smekni.com

Эффективность вейвлет фильтрации сигнала на GPGPU (стр. 1 из 6)

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра Вычислительной Техники

Реферат

По дисциплине «Испытание и квалиметрия информационных систем»

на тему «Эффективность вейвлет фильтрации сигнала на GPGPU»

Факультет: АВТ

Группа: АММ-09

Студент: Е.Ю. Скоморохов

Проверил: Хайретдинов М.С., Пискунов С.В.

Новосибирск 2010


Содержание

Введение. 3

1 Вейвлет преобразование. 3

1.1 Организация модуля. 3

1.2 Фильтрация на CPU.. 3

1.3 Фильтрация на GPGPU.. 3

1.4 Проблемы распараллеливания. 3

1.5 Методы оптимизации. 3

Работа с памятью.. 3

Реорганизация вычислений. 3

1.6 Исследование производительности. 3

Заключение. 3

Список использованных источников. 3

Приложение А. Исходный код Вейвлет преобразования на GPGPU.. 3

dwt_kernel_float.cu — ядра GPGPU.. 3

dwt_float.cu — промежуточный слой между CPU и GPU слоями. 3

dwt_float.h — заголовочный файл с описание ядер и их параметров. 3

wavelet_denoise.cpp – общий ход Вейвлет преобразования. 3

Приложение Б. Характеристики сопроцессора на основе GPGPU.. 3

Приложение В. Запуск теста вейвлет преобразования. 3

Приложение Г. Калькулятор использования ресурсов устройства GPGPU.. 3


Введение

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

Первое ДВП было придумано венгерским математиком Альфредом Хааром. Для входного сигнала, представленного массивом 2n чисел, вейвлет-преобразование Хаара просто группирует элементы по 2 и образует от них суммы и разности. Группировка сумм проводится рекурсивно (в случае чётной длины последовательности сумм) для образования следующего уровня разложения. В итоге получается 2n−1 разность и 1 общая сумма.

Это простое ДВП иллюстрирует общие полезные свойства вейвлетов. Во-первых, преобразование (один уровень) можно выполнить за O(n) операций. Во-вторых, оно не только раскладывает сигнал на некоторое подобие частотных полос (путём анализа его в различных масштабах), но и представляет временную область, то есть моменты возникновения тех или иных частот в сигнале. Вместе эти свойства характеризуют быстрое вейвлет-преобразование — альтернативу обычному быстрому преобразованию Фурье.

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

В ходе данной работы запланировали достичь целей:

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

· получить единые средства для вейвлет преобразования с любым ядром (Добеши, Хаара и другие);

· получить бесплатное средство обработки сигналов;

· проверить на практике эффективность GPGPU.

1 Вейвлет преобразование

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

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

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

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

где

То есть базис функционального пространства

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

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

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

где

M – целое число коэффициентов h,

Для дискретного вейвлет-преобразования Добеши 4-го порядка (при

) коэффициенты hk имеют следующие значения: h0=0.48, h1=0.84, h2=0.22, h3=-0.129 (рисунок 1).

На рисунке 1 приведены вейвлеты семейства Добеши 2-го, 4-го, 5-го, 8-го и 10-го порядков. С повышением порядка (число нулевых моментов) повышается гладкость функций. Таким образом, подбором порядка материнского вейвлета можно добиться наилучшего приближения.

Рисунок 1 ‑ Семейство вейвлетов Добеши

Для шумоподавления возьмем вейвлет Добеши 8.

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

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

ДВП сигнала x получают применением набора фильтров. Сначала сигнал пропускается через низкочастотный (low-pass) фильтр с импульсным откликом g, и получается свёртка:

Одновременно сигнал раскладывается с помощью высокочастотного (high-pass) фильтра h. В результате получаются детализирующие коэффициенты (после ВЧ-фильтра) и коэффициенты аппроксимации (после НЧ-фильтра). Эти два фильтра связаны между собой и называются квадратурными зеркальными фильтрами (QMF).

Так как половина частотного диапазона сигнала была отфильтрована, то, согласно теореме Котельникова, отсчёты сигналов можно проредить в 2 раза:

Однако каждый из получившихся сигналов представляет половину частотной полосы исходного сигнала, так что частотное разрешение удвоилось.

Рисунок 2 – Свертка и прореживание сигнала

Схема разложения сигнала в ДВП

С помощью оператора прореживания

вышеупомянутые суммы можно записать короче:

Каскадирование и банки фильтров.

Это разложение можно повторить несколько раз для дальнейшего увеличения частотного разрешения с дальнейшим прореживанием коэффициентов после НЧ и ВЧ-фильтрации. Это можно представить в виде двоичного дерева, где листья и узлы соответствуют пространствам с различной частотно-временной локализацией. Это дерево представляет структуру банка (гребёнки) фильтров.