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

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

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

ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ, МЕХАНИКИ И ОПТИКИ

Тропченко А.Ю., Тропченко А.А.

ЦИФРОВАЯ ОБРАБОТКА СИГНАЛОВ

МЕТОДЫ ПРЕДВАРИТЕЛЬНОЙ ОБРАБОТКИ

Учебное пособие по дисциплине "Теоретическая информатика" Санкт-Петербург 2009 2 Тропченко А Ю., Тропченко А.А. Цифровая обработка сигналов. Методы предварительной обработки. Учебное пособие по дисциплине "Теоретическая информатика". – СПб: СПбГУ ИТМО, 2009. – 100 с.

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

Задания, приведенные в шестом разделе, имеют своей целью выработать у студентов практические навыки применения основных положений теории цифровой обработки сигналов и ее методов. Пособие может быть использовано при подготовке магистров по направлению 230100.68 “ИНФОРМАТИКА И ВЫЧИСЛИТЕЛЬНАЯ ТЕХНИКА”, а также инженеров по специальности 230101.65 “ВЫЧИСЛИТЕЛЬНЫЕ МАШИНЫ, КОМПЛЕКСЫ, СИСТЕМЫ И СЕТИ” и аспирантов.

Рекомендовано Советом факультета Компьютерных технологий и управления 13 октября 2009 г., протокол № СПбГУ ИТМО стал победителем конкурса инновационных образовательных программ вузов России на 2007-2008 годы и успешно реализовал инновационную образовательную программу «Инновационная система подготовки специалистов нового поколения в области информационных и оптических технологий», что позволило выйти на качественно новый уровень подготовки выпускников и удовлетворять возрастающий спрос на специалистов в информационной, оптической и других высокотехнологичных отраслях науки. Реализация этой программы создала основу формирования программы дальнейшего развития вуза до 2015 года, включая внедрение современной модели образования.

©Санкт-Петербургский государственный университет информационных технологий, механики и оптики, © А.Ю. Тропченко, А.А. Тропченко, Содержание стр.

Введение…………………………………………………………………………… 1. ОСНОВНЫЕ ПОНЯТИЯ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ………. 1.1. Понятие о первичной и вторичной обработке сигналов………………….. 1.2. Технические средства комплекса обработки сигналов………………….. 1.3. Основные типы алгоритмов цифровой обработки сигналов……………… 1.4. Линейные и нелинейные преобразования…………………………………. 1.5. Переход от непрерывных сигналов к дискретным………………………... 1.6. Циклическая свертка и корреляция……………………………………….... 1.7. Апериодическая свертка и корреляция…………………………………….. 1.8. Двумерная апериодическая свертка и корреляция…………………………. 1.9. Контрольные вопросы и задания ……………………………………………. 2. ДИСКРЕТНЫЕ ОРТОГОНАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ……………… 2.1. Введение в теорию ортогональных преобразований………………………. 2.2. Интегральное преобразование Фурье………………………………………. 2.3. Интегральное преобразование Хартли……………………………………… 2.4. Дискретное преобразование Фурье…………………………………………. 2.5. Дискретное преобразование Хартли………………………………………… 2.6. Двумерные дискретные преобразования Фурье и Хартли………………… 2.7.Ортогональные преобразования в диадных базисах………………………... 2.8. Понятие о вейвлет-преобразовании. Преобразование Хаара……………… 2.9. Контрольные вопросы и задания……………………………………………..

3. БЫСТРЫЕ АЛГОРИТМЫ ОРТОГОНАЛЬНЫХ ПРЕОБРАЗОВАНИЙ……

3.1. Вычислительная сложность ДПФ и способы её сокращения……………... 3.2. Запись алгоритма БПФ в векторно-матричной форме…………………….. 3.3. Представление алгоритма БПФ в виде рекурсных соотношений………….. 3.4. Алгоритм БПФ с прореживанием по времени и по частоте………………... 3.5. Алгоритм БПФ по основанию r (N = rm)…………………………………….. 3.6. Вычислительная сложность алгоритмов БПФ………………………………. 3.7. Выполнение БПФ для случаев Dq: = Dq1; ……………………………………... 3.8. Быстрое преобразование Хартли…………………………………………….. 3.9. Быстрое преобразование Адамара…………………………………………… 3.10. Контрольные вопросы и задания……………………………………………

4. ЛИНЕЙНАЯ ФИЛЬТРАЦИЯ СИГНАЛОВ ВО ВРЕМЕННОЙ И

ЧАСТОТНОЙ ОБЛАСТЯХ……………………………………………………….. 4.1. Метод накопления…………………………………………………………….. 4.2. Не рекурсивные и рекурсивные фильтры………………………………..…. 4.3. Выбор метода вычисления свертки / корреляции…………………………... 4.4. Выполнение фильтрации в частотной области……………………………… 4.5. Адаптивные фильтры…………………………………………………………. 4.6. Оптимальный фильтр Винера………………………………………………... 4.7. Методы обращения матриц………………………………………………….. 4.8. Контрольные вопросы и задания…………………………………………….. 5. АЛГОРИТМЫ НЕЛИНЕЙНОЙ ОБРАБОТКИ СИГНАЛОВ………………… 5.1. Ранговая фильтрация…………………………………………………………. 5.2. Взвешенная ранговая фильтрация…………………………………………… 5.3. Скользящая эквализация гистограмм………………………………………... 5.4. Преобразование гистограмм распределения………………………………... 5.5. Контрольные вопросы и задания…………………………………………….. ЛИТЕРАТУРА……………………………………………………………………... Бурный прогресс вычислительной техники в последние десятилетия привел к широкому внедрению методов цифровой обработки информации практически во всех областях научных исследований и народно-хозяйственной деятельности. При этом среди различных применений средств вычислительной техники одно из важнейших мест занимают системы цифровой обработки сигналов (ЦОС), нашедшие использование при обработке данных дистанционного зондирования, медико-биологических исследований, решении задач навигации аэрокосмических и морских объектов, связи, радиофизики, цифровой оптики и в ряде других приложений [1,7,8,11].

Цифровая обработка сигналов (ЦОС) - это динамично развивающаяся область ВТ, которая охватывает как технические, так и программные средства.

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

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

В широком смысле под системами ЦОС понимают комплекс алгоритмических, аппаратных и программных средств. Как правило, системы содержат специализированные технические средства предварительной (или первичной) обработки сигналов и специальные технические средства для вторичной обработки сигналов. Средства предварительной обработки предназначены для обработки исходных сигналов, наблюдаемых в общем случае на фоне случайных шумов и помех различной физической природы и представленных в виде дискретных цифровых отсчетов, с целью обнаружения и выделения (селекции) полезного сигнала, его пеленгования и оценки характеристик обнаруженного сигнала. Полученная в результате предварительной обработки полезная информация поступает в систему вторичной обработки для классификации, архивирования, структурного анализа и т.д. [7,8].

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

1. ОСНОВНЫЕ ПОНЯТИЯ ЦИФРОВОЙ ОБРАБОТКИ СИГНАЛОВ

1.1. Понятие о первичной и вторичной обработке сигналов В задачах ЦОС выделяют этапы предварительной (первичной) и вторичной обработки сигналов. Это связано с тем, что в общем случае на входе системы ЦОС наблюдается смесь V(t) полезного сигнала x(t), некоторого шума n(t) и различных помех разной природы p(t):

где n(t) является характеристикой самого техничного устройства, а p(t) некоторое искажающее воздействие самой физической среды, в которой распространяется сигнал (например, затухание).

Важнейшей задачей предварительной обработки сигнала является подавление n(t) и p(t) (шума и помехи). Такая задача оптимального может быть решена только на основе использования избыточности представления исходного сигнала, а также имеющихся сведений о свойствах полезного сигнала, помехи и шума для увеличения вероятности правильного приема [7,11].

Вследствие того, что на вход приемного устройства системы поступает сумма полезного сигнала и помехи, вероятность правильного приема будет определяться отношением полезного сигнала к помехе. Для повышения вероятности правильного приема сигнала должна быть произведена предварительная обработка принятого сигнала, обеспечивающая увеличение отношения сигнал/помеха. Таким образом, средства предварительной обработки при приеме должны содержать два основных элемента (рис.1.1) :

фильтр Ф, обеспечивающий улучшение отношения сигнал/помеха, и решающее устройство РУ, выполняющее главные функции приема (обнаружения, различения и восстановления сигналов).

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

• метод накопления;

• частотная фильтрация;

• корреляционный метод;

• согласованная фильтрация;

• нелинейная фильтрация.

Все эти методы основаны на использовании различий свойств полезного сигнала и помехи.

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

Во входной смеси может и не быть полезного сигнала x(t), поэтому на выходе системы предварительной обработки не будет никакого сигнала;

следовательно, интенсивность потока данных на выходе будет ниже, чем на входе.

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

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

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

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

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

В настоящее время, согласно литературе, известны два типа систем обработки сигналов [7, 8,11,16].

Динамический Фиксированная Сжатие изображений, Первый тип систем ЦОС предусматривает построение конструктивно законченного блока. Как правило, такой блок имеет модульную структуру и строится на базе специализированных СБИС (например, на основе БМК), что позволяет обеспечить аппаратную реализацию подлежащего исполнению алгоритма и оптимизировать структуру аппаратных средств под особенности алгоритма. К этому направлению можно отнести системы Series-151 и MaxVideo. В ряде случаев такие процессоры могут программироваться в целях выполнения тех или иных функций, как, например, WARP-процессор [1].

Отличительной чертой такой архитектуры является наличие отдельных магистралей ввода/вывода данных и возможность автономного функционирования. Блок со спецпроцессором при этом может быть выполнен в стандартном конструктиве типа VME, CAMAC, Multibys [7,8].

Такая система ЦОС допускает не только ввод, но и обработку изображений в реальном масштабе времени, поэтому подобный подход весьма эффективен при построении систем обработки видеоданных.

специализированным сопроцессором в виде платы, подключаемой к магистрали ПЭВМ и конструктивно встраиваемый в ее корпус. Примером такой архитектуры могут служить наборы модулей фирмы Data Translation на базе сигнальных процессоров типа TMS и платы-акселераторы типа B фирмы INMOS на базе транспьютеров T800 [27] Указанные технические средства ориентированы на использование в качестве периферийных спецпроцессоров для построения систем на базе IBM PC/AT. Спецпроцессор, входящий в эту систему, имеет, как правило, конвейерную структуру и может выполнять процедуры обработки изображений, требующие больших вычислительных затрат, в реальном масштабе времени. Настройка на выполнение тех или иных конкретных алгоритмов обработки видеоинформации производится программированием спецпроцессора, что увеличивает функциональную гибкость подобных систем и расширяет области их возможного применения.

На практике первый тип систем ЦОС наиболее часто используется в составе средств предварительной обработки сигналов, причем соответствующие вычислительные средства строятся по принципу операционного автомата с жесткой логикой. Такой подход связан с автономностью функционирования средств предварительной обработки от управляющей ЭВМ при неизменном алгоритме обработки и высокой интенсивности входного потока данных.

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

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

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

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

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

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

Локальные преобразования - при локальных преобразованиях обеспечивается формирование каждого элемента матрицы или вектора результата как функции от некоторого множества соседних элементов матрицы или вектора отсчетов исходного сигнала, составляющих некоторую локальную окрестность. При этом полагается, что местоположение вычисляемого отсчета результата (или текущий индекс элемента) задается координатами (или текущими индексами) центрального элемента локальной окрестности. Для смещение окрестности вдоль строки матрицы исходных данных или вдоль исходного вектора. Такая перемещаемая окрестность часто носит название окна сканирования. При обработке матрицы исходных данных после прохождения всей строки матрицы исходных данных окно сканирования смещается на одну строку и возвращается в начало следующей строки, после чего продолжается обработка. Просматриваемая при перемещении окна сканирования полоса строк матрицы носит название полосы сканирования. Иначе говоря, при такой обработке yi = F(X^ ) ; X^ = {xi-m/2, xi-m/2+1,..., xi,..., xi+m/2-1, xi+m/2}, (1.5) где i = 0,N-1 - индекс отсчета результата, m - размер окна сканирования. Если iN-m/2, что имеет место на практике при обработке начальных и конечных отсчетов вектора исходного сигнала, то элементы вектора исходных данных с "недостающими" индексами полагаются равными нулю.

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

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

Все преобразования ЦОС могут быть подразделены по своему типу на линейные и нелинейные преобразования [5,16,20,21].

Пусть x( t ) - входная последовательность, последовательность, связанная со входной через некоторое функциональное преобразование T Для линейных преобразований справедлив аддитивный закон :

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

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

где a - амплитуда, = - частота, T - период,, - начальная фаза.

Тогда более сложный полигармонический сигнал может быть записан как суперпозиция простейших моногармонических сигналов:

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

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

где x(t) – отсчет сигнала в некоторый момент времени.

Если на вход системы ЦОС, выполняющей линейное преобразование, поступает единичный импульс, то сигнал h(t), снимаемый с выхода системы и являющийся откликом системы на единичный импульс, носит название импульсной характеристики (импульсного отклика) системы. Импульсный отклик является важнейшей характеристикой системы и позволяет описать ее как “черный ящик”, задав реакцию системы на некоторый простейший эталонный сигнал.

Если h(t) конечна, то такие системы называются КИХ-системами, т.е.

системами с конечной импульсной характеристикой. Если h(t) бесконечна, то это БИХ-системы, т.е. системы с бесконечной импульсной характеристикой. В цифровой обработке сигналов имеет смысл рассматривать только КИХсистемы, поскольку время обработки, т.е. реакции системы на входной сигнал должно быть конечно.

Подставив (1.9) в (1.7), получаем для линейных преобразований:

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

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

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

Условие, при котором возможно восстановление сигнала без потерь, определяется из теоремы Котельникова [16,21].

Пусть функции f(x) и F() связаны обратным преобразованием Фурье, т.е.

Прямая формулировка теоремы Котельникова. Если функция f(x) имеет ограниченный спектр, локализованный в диапазоне max max, то она полностью определена путем задания отсчетов на наборе точек, отстоящих друг от друга на расстоянии 1 2max.

Обратная формулировка теоремы Котельникова/ Если f(x) задана в ограниченной области xmax x xmax, то ее спектр F() полностью определен набором отсчетов в точках, равноотстоящих друг от друга на расстоянии 1 2x max.

Поясним выбор шагов дискретизации по теореме Котельникова на рис.1.2.

Рис.1.2. Выбор шага дискретизации по теореме Котельникова При дискретизации согласно теореме Котельникова исходная функция f(x) может быть получена по ее дискретным значениям по формуле:

причем шаг дискретизации составляет Однако согласно теории Фурье-анализа конечной апериодической функции f(x) соответствует бесконечный спектр и наоборот, конечный спектр соответствует бесконечной исходной функции.

Поэтому для реальных сигналов условия теоремы Котельникова в строгом смысле слова не выполняются.

1. Все реальные сигналы ограничены во времени и имеют неограниченный 2. В соответствии с рядом Котельникова восстановление осуществляется по бесконечному числу отсчетов (- k ).

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

Поэтому, чтобы получить конечный спектр, можно воспользоваться равенством Парсеваля:

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

Исходя из максимальной частоты определяется число отсчетов. Если размер области задания исходной функции f(x) равен X=2Xmax, а число отсчетов функции при дискретизации должен составлять N, то шаги дискретизации исходной функции и ее спектра составят:

Итак, в результате дискретизации в соответствии с теоремой Котельникова от x(t) мы переходим к набору отсчетов или к вектору:

В дискретном виде линейные преобразования могут быть описаны в общем виде как векторно-матричные операции [3,5, 16]:

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

К числу подобных преобразований относится циклическая свертка последовательностей X = [ x0 x1 x2... x N 1 ] и G = [ g0 g1 g2... g N 1 ], в этом случае строится матрица ядра свертки:

Каждый элемент вектора Y может быть описан как:

Матрица ядра циклической взаимокорреляции может быть построена как транспонированная матрица ядра свертки, т.е. следующим образом:

Поэтому каждый отсчет результата может быть записан как:

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

Вычисление свертки и корреляции лежит в основе корреляционного метода подавления помех.

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

Рассмотрим сущность метода на примере, когда полезный сигнал является гармоническим, а помеха - типа белого гауссова шума [21].

Автокорреляционная функция сигнала является тоже гармонической и имеет ту же частоту. Метод автокорреляционного приема основан на анализе автокорреляционной функции принятого сигнала y(t)=x(t)+р(t).

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

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

1.8. Двумерная апериодическая свертка и корреляция Важное место среди операций линейной обработки сигналов занимает операция перемножения матриц одинаковой размерности. Такая операция имеет вид:

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

где x ik, bkj - элементы исходных матриц.

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

Математически двумерная апериодическая свертка может быть описана следующим образом:

где y ij - отсчеты результатов вычислений (отсчеты свертки), g mn - отсчеты весовой функции окна (ядра свертки) размерностью M x M отсчетов, причем N >> M. Очевидно, что размерность матрицы, описывающей двумерную свертку, равна (N + M-1) x (N + M -1) отсчетов. Поэтому матрица исходных данных также должна быть дополнена до указанного размера нулевыми элементами по краям кадра.

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

После прохождения i-й строки изображения (i= 1,N) окно смещается на одну строку вниз и возвращается к началу следующей (i + 1)-й строки изображения.

По окончании обработки кадра изображения окно перемещается в исходное положение.

При вычислении свертки можно распараллелить вычисления по столбцам окна сканирования, выполняя параллельно вычисление произведений столбцов gn и столбцов X j^+ n 1 текущей полосы сканирования изображеядра свертки ния. Поэтому для окончательного вычисления отсчета свертки достаточно сформировать сумму:

соответствующую отсчету свертки с номером j, расположенному в средней строке полосы шириной М.

Представляет интерес распараллеливание по разрядным срезам, поскольку в этом случае практически исключается операция умножения [16]. При разрядно-срезовой обработке данные должны быть представлены в формате с фиксированной точкой. Представим значение элемента изображения в следующем виде :

где b - q-ый разряд x mn (q= 1,…, Q), (g=(1,Q)) где Q - разрядность данных.

С учетом этого процедура вычисления свертки принимает вид:

Таким образом, процедура двумерной апериодической свертки для одного положения окна сводится к M x N x Q операциям сложения и (Q-1) операциям сдвига. Умножение под знаком суммы сводится к операции вида :

Поэтому разрядно-срезовый алгоритм вычисления свертки или корреляции для одного положения окна может быть представлен в виде [16]:

начало;

конец.

Физический смысл функций свертки и корреляции состоит в том, что они являются количественной мерой совпадения (сходства) двух последовательностей f(x) и g(x). При этом наиболее полно мера сходства может быть определена по функции корреляции, в связи с чем функция взаимокорреляции (или кросскорреляции) может быть использована для распознавания сигналов. Если распознаваемый сигнал f(t) точно соответствует эталонному сигналу g(t), то результирующий сигнал k(t) принимает значение:

что соответствует функции автокорреляции. Если сигналы отличаются, то