Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Національний Університет “Львівська Політехніка”
Кафедра ЕОМ
Цифрове опрацювання сигналів та зображень: Алгоритми та реалізація
Навчальний посібник
до лекційного курсу з дисципліни “Проектування комп’ютерних засобів обробки сигналів та зображень” для студентів спеціальностей 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 /"Спеціалізовані комп'ютерні системи"/ здобути початкові практичні навички у оптимальному виборі алгоритмів, їх програмній та апаратній реалізації.
Зміст
ВСТУП
В останні роки цифрове опрацювання сигналів та зображень (ЦОСЗ) суттєво впливає на такі ключові технологічні галузі, як телекомунікації, цифрове телебачення і засоби інформації, біомедицина і цифровий звукозапис. Сьогодні ЦОСЗ є основою багатьох новітніх видів цифрових розробок і різних застосувань в інформаційному середовищі (наприклад. цифровий мобільний зв'язок, цифрові відеокамери, телебачення і системи звукозапису). Поряд з тим ЦОСЗ ширше впроваджується і в класичні галузі застосування (радіолокація, геофізика, опрацювання мовних сигналів, сейсмологія, системи зв'язку і передачі даних, медична і технічна діагностика, системи керування). Такому широкому застосуванню сприяли успіхи в розробці швидких алгоритмів і методів ЦОСЗ (наприклад, хвилькові перетворення), досягнення в технології конструювання інтегральних схем (архітектура нових процесорів ЦОСЗ, програмовані логічні інтегральні схеми – ПЛІС, системи на кристалі), використання програмних пакетів (MATLAB, база програм на мові С). Суть ЦОСЗ як області науки пролягає у розв'язку на обчислювальній машині чотирьох основних задач: - представлення сигналів та зображень в зручній для сприйняття формі; - виділення із сигналів та зображень корисної інформації; - внесення в сигнали та зображення корисної інформації; - формування сигналів та зображень із заданими параметрами. Основні переваги ЦОСЗ полягають в: можливості реалізації складних методів та алгоритмів опрацювання сигналів та зображень, недоступних для аналогових пристроїв; забезпеченні високої точності опрацювання; гнучкості і універсальності засобів, розвиненому користувацькому інтерфейсові тощо.
Головна проблема ЦОСЗ полягає у підвищенні швидкодії при реалізації певного набору математичних операцій над сигналами та зображеннями. Цей набір, як правило, визначається проблемною орієнтацією засобів ЦОСЗ. Для розв'язання цієї задачі комплексно застосовуються два напрямки - підвищення ефективності обчислювальних алгоритмів і вдосконалення архітектури комп'ютерних засобів. При цьому виходять з детального аналізу особливостей проблемної області. Власне, незалежно від вибраного напрямку і теми, студенти повинні виконувати курсові роботи з даного курсу виходячи з головної проблеми ЦОСЗ. Метою вивчення дисципліни є засвоєння основних методів та алгоритмів опрацювання сигналів та зображень, принципів та шляхів проектування апаратних і програмних комп’ютерних засобів опрацювання сигналів та зображень, набуття початкових практичних навиків проектування таких засобів. В результаті вивчення дисципліни студенти повинні: знати: типи і особливості алгоритмів опрацювання сигналів та зображень, математичні основи їх реалізації, характеристики елементної бази та основи реалізації алгоритмів на її основі, особливості і етапи розробки цифрових пристроїв на процесорах і вузлах, орієнтованих на задачі опрацювання сигналів та зображень; мови програмування та мови опису апаратних засобів; пакети моделювання, опрацювання і фільтрації сигналів та зображень вміти: вибирати найефективніший метод і алгоритм, здійснювати математичне формування алгоритму та методу його розв’язання, розробляти блок-схеми алгоритмів, розробляти програмну реалізацію виконання алгоритмів, розраховувати технічні параметри апаратних і програмних засобів, проектувати структурні та функціональні схеми процесорів та вузлів опрацювання сигналів; моделювати і опрацьовувати сигнали різної форми. Для тих, хто хоче краще орієнтуватися в перспективних напрямках розвитку комп’ютерних засобів опрацювання сигналів та зображень, краще розуміти специфіку і особливості їх проектування радимо, насамперед, скористатись матеріалами Internet-сайтів 1. Особливості задач і алгоритмів цифрового опрацювання сигналів та зображень Аналіз задач і алгоритмів До основних галузей, де використовується опрацювання сигналів та зображень відносяться: 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 =log2 N етапів, на кожному з яких вхідний дискретний набір розділяється на дві частини. До кожної такої частини вхідного дискретного набору, застосовується операція ДПФ в 2 рази меншої розмірності: в результаті застосувань розбиття m разів на останньому етапі, матимемо тривіальне 2-х точкове ДПФ. Застосування ШПФ можливе лише тоді, коли N є складним числом. Найбільшого розповсюдження набули алгоритми ШПФ для послідовностей довжини N, що є степенем числа 2 (N =2 m). Загальне число операцій в алгоритмі ШПФ складає приблизно N log2 N додавань і 0,5 N log2 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 0(k) та X 1(k) відповідно N /2 - точкові ДПФ послідовностей x (2 n) та x (2 n +1), n =0, 1,..., (N /2-1). При проріджуванні, N -точкове ДПФ зводиться до обчислення двох N /2-точкових ДПФ. Рекурсивно застосовуючи вказаний спосіб розділення до перетворень меншої розмірності, отримуємо алгоритм ШПФ за основою два з проріджуванням в часі. Аналізуючи формулу (1.5), і беручи до уваги, що послідовності X 0(k) та X 1(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,…, N 1-1, m = 0,1,…, N 2-1, виконується обробка згідно з формулою (1.9). ; (1.9) де h (m) і x (n) рівні нулю поза відповідними інтервалами, h (m) - дискретна імпульсна характеристика системи (фільтра). Нормування сигналів. Одним з прикладів операції нормування сигналів є ділення комплексних чисел, що виконується згідно з формулою (1.10). (1.10) Сортування. В основі алгоритмів сортування лежать дві основні операції: порівняння і пересилання даних. Більшості з названих алгоритмів властиві регулярність, рекурсивність і локальність, що робить їх придатними для реалізації на НВІС. Зокрема, до локально рекурсивних алгоритмів відносяться алгоритми премноження матриць, згортки, НІХ-фільтрація, сортування вибором; до глобально-рекурсивних - алгоритми ШПФ, бітове сортування. На основі аналізу алгоритмів в табл. 1.2 виділено набір базових операцій для опрацювання сигналів та зображень. Таблиця 1.2. Базові операції для задач керування та опрацювання інформації
Детальніше конкретні алгоритми описані і реалізовані в подальших розділах посібника. Основні параметри типових операцій. Основні параметри типових операцій наведені в табл. 1.3, де N - розмірність масиву інформації. Таблиця 1.3. Параметри типових операцій
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Последнее изменение этой страницы: 2021-12-15; просмотров: 32; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.144.12.205 (0.032 с.) |