Аналіз задач і алгоритмів

До основних галузей, де використовується опрацювання сигналів та зображень відносяться:

1. Радіолокація (РЛ) — виявлення, фільтрація сигналу з режекцією завад та накопичення сигналу.

2. Гідроакустика (ГА) — контроль водяного простору, підводна сейсмологія, гідронавігація.

3. Зв’язок (ЗВ) — підвищення надійності, пропускної здатності, скритності, виділення символів, згортка символьних послідовностей, скорочення надлишковості, підвищення завадостійкості, керування транспортними засобами.

4. Геофізика (ГФ) — пошук нафтоносних (водоносних) шарів.

5. Біомедицина (БМ) — візуалізація органів, діагностика.

6. Системи керування виробничими процесами — керування, знімання даних, передача інформації.

7. Промислова діагностика — неруйнівний контроль, візуалізація стану вузлів, діагностика віддалених об’єктів.

Кількість основних алгоритмів і операцій, що використовуються для їх виконання, як це видно з табл.1.1 є невеликою.

Таблиця 1.1. Перелік основних алгоритмів і застосованих операцій

Алгоритми обробки і	Області застосування
застосовувані операції	РЛ	ГА	ЗВ	ГФ	БМ	СК
Згортка	+		+	+
ШПФ	+	+	+	+	+
Перемноження елементів векторів	+	+			+	+
Додавання елементів векторів	+	+				+
Перетворення координат	+	+	+
Обчислення тригонометричних функцій	+	+	+	+		+
Пошук максимальних значень	+					+
Операції над матрицями	+	+	+		+
Табличне перетворення відліків зображення	+
Сортування	+					+
Отримання квадратного кореня	+	+	+	+		+
Піднесення до степеня	+	+	+	+		+
Статистична обробка	+
Нормування	+	+
Розрахунок нормованих коефіцієнтів кореляції		+
Операції повертання координат			+
Логарифмування				+
Потенціювання				+
Номінальні розкиди координат					+
Інтерполяція даних					+	+

Розглянемо основні типи алгоритмів.

Лінійна фільтрація. Лінійна фільтрація використовується для подавлення шумів, спектр яких не перетинається зі спектром сигналу і дозволяє виділити в чистому вигляді функцію, що описує явище, яке досліджується. На практиці розрізняють два основних типи лінійних фільтрів: з скінченою (СІХ) і нескінченою (НІХ) імпульсними характеристиками. НІХ фільтри мають рекурсивну структуру, що описується різницевими рівняннями згідно з формулою (1.1).

, n ³ 0; (1.1)

де x та y - вхідна та вихідна реалізації процесу; a_i і b_i - постійні коефіцієнти, що характеризують властивості фільтра, причому a_м ¹0; M – порядок фільтру.

СІХ - фільтри реалізуються на основі нерекурсивної структури, яка описується формулою (1.2), і може бути отримана з формули (1.1) якщо a_i прирівняти до нуля, .

, n ³ 0; (1.2)

причому, b_i можна назвати дискретною імпульсною характеристикою системи (фільтра).

Медіанна фільтрація. Медіанна фільтрація є нелінійним способом опрацювання одномірних та двомірних послідовностей (виборок) і використовується для зменшення рівня імпульсних шумів. В порівнянні з лінійною, медіанна фільтрація має такі переваги: зберігає різкі перепади сигналу і добре згладжує імпульсний шум. Процес виконання фільтрації цього типу виконується в три етапи: сортування виборок реалізації в ковзаючому «вікні»; вибір середнього значення у «вікні» (медіана); заміна відліку, розташованого в середині вікна значенням медіани.

Дискретне перетворення Фур’є. Дискретне перетворення Фур’є (ДПФ) скінченої періодичної послідовності відліків сигналу { х (n)}, 0< n < N -1, визначається формулою (1.3):

, k =0,1,…, N -1 (1.3)

де - комплексний дискретний ортонормований базис.

Таким чином, ДПФ представляє собою множину спектральних коефіцієнтів Фур’є, що відповідають N рівномірно рознесеним частотам, починаючи від нульової і до (але не включно) частоти 2p/ T. Обернене дискретне перетворення Фур’є (ОДПФ) визначається формулою (1.4):

, n =0,1,…, N -1; (1.4)

ОДПФ дозволяє однозначно перейти від Фур’є-образу X (k) до функції х (n).

Швидке перетворення Фур’є (ШПФ) є узагальненою назвою множини алгоритмів, що призначені для виконання ДПФ і ОДПФ. Основна ідея алгоритмів ШПФ полягає в розбитті процедури виконання ДПФ на m =log₂ N етапів, на кожному з яких вхідний дискретний набір розділяється на дві частини. До кожної такої частини вхідного дискретного набору, застосовується операція ДПФ в 2 рази меншої розмірності: в результаті застосувань розбиття m разів на останньому етапі, матимемо тривіальне 2-х точкове ДПФ. Застосування ШПФ можливе лише тоді, коли N є складним числом. Найбільшого розповсюдження набули алгоритми ШПФ для послідовностей довжини N, що є степенем числа 2 (N =2 ^m). Загальне число операцій в алгоритмі ШПФ складає приблизно N log₂ N додавань і 0,5 N log₂ N множень комплексних чисел. Алгоритми ШПФ з проріджуванням в часі і з проріджуванням по частоті принципово мало відрізняються між собою. Тому розглянемо тільки алгоритм ШПФ з проріджуванням в часі. Формула розкладу алгоритму, в результаті застосування якої отримується шуканий дискретний набір X (k), k =0,1,..., N -1, що є зображенням вихідного дискретного набору перетворюваної функції x(n), n =1,2,..., N -1 в Фур’є просторі визначається згідно з формулою (1.5).

, k =0,1,..., N -1; (1.5)

де X ₀(k) та X ₁(k) відповідно N /2 - точкові ДПФ послідовностей x (2 n) та x (2 n +1), n =0, 1,..., (N /2-1). При проріджуванні, N -точкове ДПФ зводиться до обчислення двох N /2-точкових ДПФ. Рекурсивно застосовуючи вказаний спосіб розділення до перетворень меншої розмірності, отримуємо алгоритм ШПФ за основою два з проріджуванням в часі. Аналізуючи формулу (1.5), і беручи до уваги, що послідовності X ₀(k) та X ₁(k), періодичні з періодом N /2, та W_N^N-k = - W_N^k, можна встановити, що при кожному розділенні реалізується однотипна базова операція:

A*=A+W_N^kB; B*=A – W_N^k B; (1.6)

причому k О{0, 1,..., (N /2-1)}, а величини A, B, A*, B*, і W_N^k - комплексні числа. Для виконання базової операції (1.6) необхідно виконати одне множення, одне додавання і одне віднімання комплексних величин.

Кореляція. Для визначення подібності між сигналами в різні моменти часу або виділення сигналу на фоні шуму проводять кореляційну обробку, важливе місце в якій займає обчислення функцій взаємної кореляції двох числових послідовностей x і y, кожна з яких містить N відліків, записується у вигляді:

, r = 0,1,…, N -1; (1.7)

Тобто, взаємна кореляційна функція двох сигналів обчислюється як сума їх поелементних добутків з відносною затримкою r.

Автокореляційна функція записується у вигляді:

, r = 0,1,…, N -1; (1.8)

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

Згортка сигналів. При згортці сигналів x (n) та h (m), де n = 0,1,…, N ₁-1, m = 0,1,…, N ₂-1, виконується обробка згідно з формулою (1.9).

; (1.9)

де h (m) і x (n) рівні нулю поза відповідними інтервалами, h (m) - дискретна імпульсна характеристика системи (фільтра).

Нормування сигналів. Одним з прикладів операції нормування сигналів є ділення комплексних чисел, що виконується згідно з формулою (1.10).

(1.10)

Сортування. В основі алгоритмів сортування лежать дві основні операції: порівняння і пересилання даних.

Більшості з названих алгоритмів властиві регулярність, рекурсивність і локальність, що робить їх придатними для реалізації на НВІС. Зокрема, до локально рекурсивних алгоритмів відносяться алгоритми премноження матриць, згортки, НІХ-фільтрація, сортування вибором; до глобально-рекурсивних - алгоритми ШПФ, бітове сортування.

На основі аналізу алгоритмів в табл. 1.2 виділено набір базових операцій для опрацювання сигналів та зображень.

Таблиця 1.2. Базові операції для задач керування та опрацювання інформації

Алгоритм	Базові операції
Реалізація фільтрів, обчислення кореляційної і взаємокореляційної функцій	Додавання, віднімання, множення, обчислення суми парних добутків
Алгоритми перетворення	Множення, додавання комплексних чисел; обчислення операцій ШПФ, ШПХ, множення послідовностей комплексних чисел
Алгоритми обчислення: коефіцієнтів взаємної кореляції, координат, відстаней, виконання вагового множення, тощо	Обчислення тригонометричних функцій, добування квадратного кореня, піднесення до степені, ділення, сортування

Детальніше конкретні алгоритми описані і реалізовані в подальших розділах посібника.

Основні параметри типових операцій. Основні параметри типових операцій наведені в табл. 1.3, де N - розмірність масиву інформації.

Таблиця 1.3. Параметри типових операцій

Тип операції	Складність виконання	Тип обчислюва-льних засобів	Необхідна швидкодія (MOPS)
Лінійні операції: просторова фільтрація, згортка, виявлення контурів, скалярний добуток, КІХ-фільтрація.	N	Скалярний	102 - 105
Операції другого порядку: лінійні перетворення, перетворення Фур'є, кореляція, перемноження матриці на вектор, сортування, медіанна фільтрація.	N2	Векторний	103 - 107
Операції вищих порядків: матричні операції, спектральні обчислення, адаптивні операції, розв’язання задач лінійних алгебраїчних рівнянь	N3	Матричний	104 - 108