Основные типы алгоритмов цифровой обработки сигналов

Математические методы обработки сигналов можно подразделить на три группы, если в основу классификации положить принцип формирования отдельного элемента (отсчета) результата по некоторой совокупности элементов (отсчетов) исходного сигнала [16].

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

Иначе говоря, пусть требуется обработать вектор из n отсчетов сигнала: (1.2)

и получить последовательность чисел:

, (1.3)

причем

y_i = f(x_i) (1.4)

Точечные преобразования достаточно просты и наименее громоздки с точки зрения вычислительных затрат. Если обрабатывается матрица размером N x N элементов отсчетов исходного двумерного сигнала, то вычислительная сложность процедуры точечных преобразований составит

Q_т = N² (БО),

где под базовой операцией (БО) понимается операция вида (1.4).

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

y_i = F(X^{^} ) ; X^{^} = {x_i-m/2, x_i-m/2+1, ..., x_i, ..., x_i+m/2-1, x_i+m/2}, (1.5)

где i = 0,N-1 - индекс отсчета результата , m - размер окна сканирования. Если i<m/2 или i>N-m/2, что имеет место на практике при обработке начальных и конечных отсчетов вектора исходного сигнала, то элементы вектора исходных данных с "недостающими" индексами полагаются равными нулю.

Вычислительная сложность локального преобразования составляет

Q_л = N² m² (БО),

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

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

Y_i = F(G_i,X); ,i = 0, N-1 (1.6)

где G_i – изменяемое ядро преобразования. Вычислительная сложность глобального преобразования в общем случае для случая обработки двумерного сигнала составляет

Q_г = N⁴ (БО),

где под базовой операцией понимается выполнение заданного преобразования вида (1.6) для отдельного элемента исходных данных. Примером подобных преобразований могут служить дискретные ортогональные преобразования типа преобразования Фурье, Хартли, Адамара.