Студопедия
Новини освіти і науки:
МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах


РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання


ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ"


ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ


Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків


Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні


Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах


Гендерна антидискримінаційна експертиза може зробити нас моральними рабами


ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ


ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів



Контакти
 


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






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

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

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. Алгоритм розв’язування задачі




Переглядів: 1733

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

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

 

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


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