Національний Університет “Львівська Політехніка”

Кафедра ЕОМ

 

 

 

Цифрове опрацювання сигналів та зображень:

Алгоритми та реалізація

 

Навчальний посібник

 

до лекційного курсу

з дисципліни “Проектування комп’ютерних засобів обробки сигналів та зображень” для студентів спеціальностей

7.091501 і 8.091501 "Комп'ютерні системи та мережі"

7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“

 

 

Львів – 2008

Цифрове опрацювання сигналів та зображень: Алгоритми та реалізація. Навчальний посібник до лекційного курсу з дисципліни “Проектування комп’ютерних засобів ообробки сигналів та зображень” для студентів спеціальностей 7.091501 і 8.091501 "Комп'ютерні системи та мережі", 7.091503 і 8.091503 “Спеціалізовані комп'ютерні системи“ / Укладачі: Р. Попович, Є. Ваврук – Львів: Національний університет “Львівська політехніка”, 2008,  147 с.

 

Укладачі:                      Є. Ваврук, к.т.н., доцент

                                          Р. Попович, к.т.н., доцент

                                              

 

 

Відповідальний за випуск: Мельник А. О., професор, завідувач кафедри

 

Рецензенти:                 Ткаченко Р.О., д. т. н, професор

                                          Голембо В.А. В.В., к. т. н, доцент

Анотація

Даний навчальний посібник укладений відповідно до навчальної програми з дисципліни "Проектування комп’ютерних засобів обробки сигналів та зображень". В ньому розглянуті основні питання проектування алгоритмічних, програмних та апаратних засобів опрацювання сигналів та зображень, вивчення яких допоможе студентам спеціальностей 7.091501 і 8.091501 /"Комп'ютерні системи та мережі"/ та 7.091503 і 8.091503 /"Спеціалізовані комп'ютерні системи"/ здобути початкові практичні навички у оптимальному виборі алгоритмів, їх програмній та апаратній реалізації.

 

Зміст

Вступ	5
1. Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень	7
2. Алгоритми швидкого перетворення Фур’є та їх програмна реалізація	13
3. Організація DSP- процесорів для задач опрацювання сигналів та зображень	26
4: Інтерфейси DSP-процесорів	30
5. Проектування процесора ШПФ на ПОС	38
6: Проектування засобів опрацювання сигналів та зображень на ПЛІС	53
7. Реалізація алгоритмів опрацювання сигналів та зображень на нейропроцесорах	62
8. Стиск нерухомих зображень з використанням перетворень різного типу дискретних косинусних перетворень	71
9. Опрацювання мовних сигналів	95
10. Використання вікон для опрацювання сигналів	122
11. Діагностика і контроль процесорів і систем опрацювання сигналів та зображень	135
Висновки	145
Література	146

ВСТУП

В останні роки цифрове опрацювання сигналів та зображень (ЦОСЗ) суттєво впливає на такі ключові технологічні галузі, як телекомунікації, цифрове телебачення і засоби інформації, біомедицина і цифровий звукозапис. Сьогодні ЦОСЗ є основою багатьох новітніх видів цифрових розробок і різних застосувань в інформаційному середовищі (наприклад. цифровий мобільний зв'язок, цифрові відеокамери, телебачення і системи звукозапису). Поряд з тим ЦОСЗ ширше впроваджується і в класичні галузі застосування (радіолокація, геофізика, опрацювання мовних сигналів, сейсмологія, системи зв'язку і передачі даних, медична і технічна діагностика, системи керування). Такому широкому застосуванню сприяли успіхи в розробці швидких алгоритмів і методів ЦОСЗ (наприклад, хвилькові перетворення), досягнення в технології конструювання інтегральних схем (архітектура нових процесорів ЦОСЗ, програмовані логічні інтегральні схеми – ПЛІС, системи на кристалі), використання програмних пакетів (MATLAB, база програм на мові С).

Суть ЦОСЗ як області науки пролягає у розв'язку на обчислювальній машині чотирьох основних задач:

- представлення сигналів та зображень в зручній для сприйняття формі;

- виділення із сигналів та зображень корисної інформації;

- внесення в сигнали та зображення корисної інформації;

- формування сигналів та зображень із заданими параметрами.

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

Головна проблема ЦОСЗ полягає у підвищенні швидкодії при реалізації певного набору математичних операцій над сигналами та зображеннями. Цей набір, як правило, визначається проблемною орієнтацією засобів ЦОСЗ. Для розв'язання цієї задачі комплексно застосовуються два напрямки - підвищення ефективності обчислювальних алгоритмів і вдосконалення архітектури комп'ютерних засобів. При цьому виходять з детального аналізу особливостей проблемної області. Власне, незалежно від вибраного напрямку і теми, студенти повинні виконувати курсові роботи з даного курсу виходячи з головної проблеми ЦОСЗ.

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

В результаті вивчення дисципліни студенти повинні:

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

вміти: вибирати найефективніший метод і алгоритм, здійснювати математичне формування алгоритму та методу його розв’язання, розробляти блок-схеми алгоритмів, розробляти програмну реалізацію виконання алгоритмів, розраховувати технічні параметри апаратних і програмних засобів, проектувати структурні та функціональні схеми процесорів та вузлів опрацювання сигналів; моделювати і опрацьовувати сигнали різної форми.

Для тих, хто хоче краще орієнтуватися в перспективних напрямках розвитку комп’ютерних засобів опрацювання сигналів та зображень, краще розуміти специфіку і особливості їх проектування радимо, насамперед, скористатись матеріалами Internet-сайтів

1. Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень

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

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

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	Скалярний	10^2 - 10^5
Операції другого порядку: лінійні перетворення, перетворення Фур'є, кореляція, перемноження матриці на вектор, сортування, медіанна фільтрація.	N^2	Векторний	10^3 - 10^7
Операції вищих порядків: матричні операції, спектральні обчислення, адаптивні операції, розв’язання задач лінійних алгебраїчних рівнянь	N^3	Матричний	10^4 - 10^8