Студопедия
Новини освіти і науки:
Контакти
 


Тлумачний словник






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

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

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

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

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

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

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

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

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

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

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

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

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

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

, n ³ 0; (1.1)

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

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

, n ³ 0; (1.2)

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

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

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

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

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

A*=A+WNkB; B*=A – WNk B; (1.6)

причому kО{0, 1, ..., (N/2-1)}, а величини A, B, A*, B*, і WNk - комплексні числа. Для виконання базової операції (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,…,N1-1, m = 0,1,…,N2-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

 


Читайте також:

  1. ABC-XYZ аналіз
  2. II. Багатофакторний дискримінантний аналіз.
  3. SWOT-аналіз у туризмі
  4. SWOT-аналіз.
  5. Tема 4. Фації та формації в історико-геологічному аналізі
  6. V. Нюховий аналізатор
  7. АВС (XYZ)-аналіз
  8. Автомати­зовані інформаційні систе­ми для техніч­ного аналізу товар­них, фондових та валют­них ринків.
  9. Алгоритм однофакторного дисперсійного аналізу за Фішером. Приклад
  10. Алгоритм розв’язання задачі
  11. Алгоритм розв’язання розподільної задачі
  12. Алгоритм розв’язування задачі




<== попередня сторінка | наступна сторінка ==>
Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень | Особливості організації обчислювальних засобів

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

 

© studopedia.com.ua При використанні або копіюванні матеріалів пряме посилання на сайт обов'язкове.


Генерація сторінки за: 0.002 сек.