Реалізація системи. Сучасні проблеми науки та освіти Алгоритми попередньої обробки зображень

Лабораторна робота №1

Алгоритми обробки зображень

Операція згортки

Згортка - це алгоритм широкого застосування, який можна використовувати як для попередньої обробки зображення, так і для розпізнавання та ідентифікації об'єктів. Нехай зображення задається двовимірною матрицею яскравостей F" , а імпульсна характеристика матрицею H. Математично згортку матриці Fз ядром Hможна визначити наступною формулою:

де M2xN2 – розмір матриці ядра згортки. Розмір матриці Fдорівнює (M1+M2-1)x(N1+N2-1), де M1xN1 - Розмір вихідної матриці F" . Матриця Fвиходить з вихідної шляхом додавання елементів на краях матриці за деяким правилом для того, щоб привести її до необхідного розміру. Зазвичай, вихідна матриця на краях доповнюється нулями на половину ширини матриці. Hліворуч і праворуч і відповідно на половину висоти вгору і настільки ж вниз. Тоді розмір отриманої матриці Rбуде таким самим, як і у матриці F" .

Згортку можна обчислювати безпосередньо "пробіганням" однієї матриці по іншій, як було показано вище. На рис. 1 показана схема обчислення згортки (розмір матриці маски взятий рівним 3х3). Оператор згортки можна розглядати як матрицю коефіцієнтів (масок), які поелементно множаться з виділеним фрагментом зображення з подальшим підсумовуванням для отримання нового значення елемента відфільтрованого зображення. Ця матриця може бути будь-якого розміру, необов'язково квадратна.

Рис. 1. Реалізація операції згортки.

Завдання

Реалізувати алгоритм, що виконує операцію згортки вихідного зображення з матрицею маскою.

Розмір та вид матриці-маски задаються користувачем.

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

• для згладжування та придушення шумів у зображенні використовують матрицю-маску розміром 3х3 наступного виду:

для підкреслення контурів використовуються матриці-маски наступного виду:

1/9*

для виділення контурів використовуються маска такого вигляду:

4. Реалізувати медіанний фільтр, який використовується для придушення точкових та імпульсних перешкод. Піксел зображення та його сусіди в області, що розглядається, вибудовуються в варіаційний ряд (за зростанням або зменшенням значень пікселів) і відбирається центральне значення цього варіаційного ряду як нове значення пікселя. Результатом усередненого фільтрування є те, що будь-який випадковий шум, що міститься у зображенні, буде ефективно усунений. Це тому, що будь-яке випадкове різке зміна інтенсивності пікселя у межах аналізованої області сортуватиметься, тобто. воно поміщатиметься або на вершину, або на нижню частину сортованих значень цієї області і не враховуватиметься, так як для нового значення елементів завжди відбирається центральне значення.

5. Реалізувати алгоритм тиснення. Тиснення виробляється аналогічно алгоритмам усереднення чи підкреслення контурів. Кожен піксел у зображенні обробляється ядром (матрицею-маскою) тиснення розміром 3х3. Наприклад, як ядро ​​тиснення можна взяти наступну матрицю-маску:

Після того, як значення піксела оброблено ядром тиснення, до нього додається 128. Таким чином, значенням фонових пікселів стане середній сірий колір (червоний = 128, зелений = 128, синій = 128). Суми, що перевищують 255, можна заокруглити до 255.

У тисненому варіанті зображення контури видаються видавленими над поверхнею. Напрямок підсвічування можна змінювати, змінюючи позиції 1 і -1 в ядрі. Якщо, наприклад, змінити місцями значення 1 і -1, то реверсується напрямок підсвічування.

6. Акварелізація зображення. Акварельний фільтр перетворює зображення, і після обробки воно виглядає так, ніби написано аквареллю:

Перший крок у застосуванні акварельного фільтра – згладжування кольорів у зображенні. Одним із способів згладжування є застосування медіанного усереднення кольору в кожній точці. Значення кольору кожного пікселя та його 24 сусідів (розмір матриці-маски дорівнює 5х5) вишиковуються в варіаційний ряд за зменшенням або зростанням. Медіанне (тринадцяте) значення кольору в варіаційному ряді надається центральному пікселю.

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

Сутність обробки зображення полягає у приведенні вихідного зображення сцени до виду, що дозволяє вирішити завдання розпізнавання об'єктів.

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

1) попередня обробка зображення;

2) сегментація;

3) опис.

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

Попередня обробка зображення

Усі методи попередньої обробки зображення у СТЗ поділяють на просторові та частотні. Просторові методи є процедурами, що оперують безпосередньо з пікселями зображення. Як характеристику зображення використовується яскравість У(х, у).Частотні методи пов'язані з переведенням зображення в комплексну площину за допомогою перетворення Фур'є.

При розгляді процедур попередньої обробки обмежимося лише просторовими методами, а вихідне зображення вважатимемо півтоновим.

На першому етапі попередньої обробки відбувається формування зображення.Формуванням зображення називається процедура безпосереднього отримання зображення у вигляді розміщеного у пам'яті відеопроцесора масиву дискретних елементів - пікселів, що утворюють матрицю чи контур.

У СТЗ на етапі формування зображення вибирають поріг яскравості шляхом регулювання освітлення та проводять фільтрацію зображення.

Фільтруваннязображення є найбільш тривалою та складною стадією попередньої обробки. У випадку фільтрація вирішує такі основні задачи:

· Згладжування (пригнічення високочастотної перешкоди типу «сніг»);

· Підвищення контрастності;

· Виділення контуру.

Процедура згладжування реалізується одразу після вибору порога яскравості. Її зміст полягає у усередненні за певним правилом значень функції яскравості Y(X, у)усередині аналізованого фрагмента зображення.

Для усунення високочастотної перешкоди типу "сніг" служить фільтр нижніх частот. Недоліком низькочастотної фільтраціїє погіршення контрастності зображення.

Сегментація

В результаті попередньої обробки зображення містить одне або кілька контурних уявлень об'єктів. Процедура поділу цих контурів та співвідношення їх з певними об'єктаминазивається сегментації.

Якщо апріорно відомо, що зображення містить кілька об'єктів, процедура сегментації проводиться після виділення контурів перед етапом кодування зображення.

Алгоритми сегментації, як правило, ґрунтуються на пошуку розривності в контурі та подобі областей. У першому випадку знаходиться контур та здійснюється його програмний обхід за встановленим правилом. Якщо контур виявляється замкнутим, вважається, що він належить об'єкту. У другому випадку визначаються області зображення, що мають спільні властивості (наприклад, однакову яскравість пікселів). При знаходженні таких областей проводиться їхнє віднесення або до фону, або до об'єкта.

Кодування зображення

Для систем, що обробляють напівтонові зображення просторовими методами, розрізняють два основні методи кодування:

· Кодування власне зображення методом кодів довжин серій;

· Кодування контуру зображення ланцюговим кодом Фрімана.

В обох випадках при кодуванні відбувається значне зменшення обсягу даних, що характеризують зображення. Ефективність кодування визначається ступенем стиснення зображення.

Сутність кодування методом кодів довжин серій,реалізованого за допомогою алгоритму RLE, полягає у поданні зображення однорідними відрізками рядки розгортки, де яскравості та кольори пікселів однакові. При цьому кожна серія характеризується відповідним значенням та довжиною серії (числом пікселів).

Для кодування безпосередньо контуру зображення найчастіше застосовують ланцюговий код Фрімана(Рис. 6.22, б).У цьому випадку контур об'єкта починаючи з деякої точки задається послідовністю векторів, що приймають дискретні значення, з кутом нахилу модуля, кратним 45. Значення модуля дорівнює 2, якщо кут нахилу вектора становить 45 і 1 при вертикальному або горизонтальному його положенні. Зміна напрямку вектора при переході від однієї точки кривої до іншої відображає характер зміни кривої, що моделюється.

Опис зображення

Під описом розуміється визначення характерних параметрів об'єкта - ознак(дискримторів), необхідні його виділення з-поміж усіх, утворюють сцену.

За своєю фізичною сутністю ознаки поділяються на глобальні та локальні. Глобальна ознакаЗображення – це ознака, яку можна обчислити для будь-якого зображення об'єкта.

Локальні ознакивикористовують рідше; вони характеризують в повному обсязі зображення, лише частина його. До них відносяться кут між двома контурними лініями, число та параметри отворів на зображенні об'єкта тощо.

Розпізнавання зображення

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

Розпізнавання реалізує функцію аналізу візуального образу.

Умовно всі методи розпізнавання можна поділити на дві групи: теоретичні та структурні. Найбільш поширені теоретичні методи розпізнавання використовують принципи теорії ухвалення рішень.

Визначити реальне значення ознак об'єкта неможливо, оскільки значення різняться при кожному вимірі. Тому завдання розпізнавання ставиться так: визначити можливість того, що об'єкт належить до заданого класу.

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

Подання зображень

Існують два основні види уявлень зображень – векторне та растрове.

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

Растрове зображення є однією або кількома матрицями, що описують просторовий розподіл характеристик зображення на деякій декартовій координатній сітці. У цьому випадку зображення будується з множини точок і має структуру растру. Основним елементом растрового представлення зображення є піксел (скорочення від словосполучення «picture elements» - елементи зображення), що має координати в растрової системи координат та деякі атрибути (колір, яскравість, прозорість тощо). Число пікселів за координатами X і Y (по горизонталі та вертикалі) задає роздільну здатність (розмірність) подання зображення. Колір пікселя задається глибиною – кількістю бітів, необхідним завдання будь-якого кольору.

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

Бінарні

Напівтонові

Палітрові

Повнокольорові

У бінарному поданні колір пікселя може бути білим, або чорним і кодується одним бітом. Зображення є матрицею. Кожен елемент I (i, j) цієї матриці має значення або 0 або 1, де i - номер рядка, а - номер j стовпця елемента, що відповідає заданому пікселю (рис. 1).

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

- Задає його яскравістьI (i, j) (рис. 2).

Палітрові зображення описуються двома матрицями (рис. 3). Одна зберігає значення індексів, що задають звернення до рядка матриці палітр. Матриця палітр це колірна карта. Вона містить 3 групи стовпців - відповідних червоному "R", зеленому "G" і синьому "B" кольорам. Вони й задають колір відповідного пікселя.

Палітра це матриця розмірністю Nc 3 де Nc - кількість кольорів.

Алгоритми попередньої обробки зображень

Повнокольорові зображення – будуються в форматі RGBі являють собою три матриці R (i, j), G (i, j), B (i, j). Відповідні елементи кожної матриці містять значення інтенсивностей червоного, зеленого та синього кольорів для пікселя, що задається індексами матриць. Таким чином, повнокольорове зображення не має колірної карти і колір кожного пікселя представляється трьома числами, взятими з відповідних матриць (рис. 4).

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

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

Для повнокольорових зображень одним із параметрів є максимальна кількість кольорів, яка може бути представлена ​​у цьому форматі. Найчастіше використовуються зображення, що мають 16, 256, 65536 (High Color) та 10.7 мільйона (True Color) кольорів.

Алгоритми попередньої обробки зображень

	0 0 0 0 1 1 1 0 0	120 122 125 128 115 117 118
	1 0 0 0 1 1 1 1 0	119 121 124 125 128 130 133
	1 1 0 0 1 1 0 0 1	122 122 124 123 127 126 128
		120 121 123 125 127 125 126
	1 1 1 0 1 1 0 0 0
		118 110 109 108 108 109 110
	0 0 1 0 0 1 0 0 1

Алгоритми попередньої обробки зображень

Матриця індексів

31 15 03 09

Матриця палітри

Алгоритми попередньої обробки зображень

Повнокольорове зображення може бути представлене у форматі RGB, а й з допомогою інших колірних систем.

У системі HSB колір представляється такими колірними характеристиками: Hue - колірний тон;

Saturation – насиченість; Brightness – яскравість.

Вважається, що ця колірна система відповідає особливостям людського сприйняття кольору.

У системі LAB колір розглядається як сукупність яскравості (lightness) та двох незалежних значень кольоровості, які визначають істинний колір пікселя. Кольоровість A – колірна складова вибирається в діапазоні від пурпурового до зеленого. Кольоровість B – друга колірна складова вибирається з діапазону від жовтого до блакитного.

Існують інші системи подання кольору. Природно, що вони пов'язані і з одному уявленню може бути отримано інше. Розмаїття колірних систем обумовлено, розв'язуваними з допомогою завданнями. Наприклад корекцію кольору зручніше виконають в системі LAB, відтворювати зображення на екрані монітора в системі RGB, друкувати краще,

Алгоритми попередньої обробки зображень

використовуючи уявлення CMYK. Однак у будь-якому випадку при обробках зображень та їх розпізнаванні працюють з растровим представленням зображень, що містять одну або декілька матриць.

Класифікація алгоритмів попередньої обробки

Алгоритми попередньої обробки зображень поділяться різні групи залежно від класифікуючого ознаки. Всі алгоритми попередньої обробки або повинні поліпшувати в якомусь сенсі якість зображень, або перетворювати його до вигляду, найбільш зручному для подальшої обробки.

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

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

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

Алгоритми попередньої обробки зображень

– Кадрування зображення - виділення з вихідного зображення деякої частини прямокутної форми;

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

– Повертання зображення. Ці алгоритми здійснюють поворот вихідного зображення на заданий кут, коректно перераховуючи значення пікселів, використовуючи різні методи інтерполяції.

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

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

Алгоритми попередньої обробки зображень

Алгоритми просторової фільтрації

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

If (i, j)	Im(i m , j n )h (m , n ), де:

m N11 n N21

Im, If матриці вихідного та відфільтрованого зображень, h матриця імпульсної характеристики фільтра,

N 11 , N 21 нижня і верхня межі стовпців імпульсної характеристики, N 12 , N 22 ліва та права межі рядів імпульсної характеристики.

Матриця імпульсної характеристики може бути отримана при розрахунку просторового фільтра, виходячи із заданих параметрів. Методам розрахунку просторових фільтрів присвячено велику кількість літератури присвяченої цифрової фільтрації, наприклад. Для практичних розрахунків можна використовувати стандартні математичні пакети, наприклад, до складу системи “MATLAB” входить система розрахунку фільтрів “Image Filter Design”.

Зазначимо, що фільтрацію можна проводити і частотної області. В цьому

Алгоритми попередньої обробки зображень

у разі порядок фільтрації наступний:

Перевести зображення з просторової області на частотну, використовуючи двовимірне дискретне перетворення Фур'є

Здійснити поелементне множення частотної матриці зображення на частотну матрицю фільтра

Отриманий результат перетворити на просторову область, використовуючи зворотне двовимірне дискретне перетворення Фур'є.

Im(x, y)	Im(f x , f y )	If (f x , f y ) Im(f x , f y ) H (f x , f y )	If (fx, f y)		If(x, y).

Фільтрація зображень у частотній області, застосовується досить рідко з-за великого обсягу обчислень. Однак такий спосіб фільтрації широко використовується при теоретичних викладках для аналізу варіантів обробки зображень. Він дозволяє досить наочно уявити які фільтрація необхідна. Наприклад, якщо потрібно виділити на зображенні різкі перепади яскравості, то очевидно, що необхідно використовувати фільтри верхніх частот. Навпаки, якщо потрібно позбавитися низькочастотних перешкод – тремтливих контурів, окремих викидів і т.п., то потрібно застосовувати фільтри нижніх частот. Конкретні параметри фільтрів вибираються з частотного аналізу перешкод і властивостей вихідного зображення.

1

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

обробка зображення

нечітка логіка

інтелектуальна система

розпізнавання об'єктів

1. Веснін О.М., Вето А.В., Царьов В.А. До питання про розробку та застосування адаптивних оптоелектронних систем технічного зору// Автоматизація у промисловості, 2009. - № 11. - С. 48-52.

2. Гришин В.А. Системи технічного зору у вирішенні завдань управління безпілотними літальними апаратами // Датчики та системи, №2, 2009. - C. 46-52.

3. Клевалін В.А., Поліванов А.Ю. Цифрові методи розпізнавання в системах технічного зору промислових роботів// Мехатроніка, автоматизація, управління, 2008 № 5. - С. 56-56.

4. Михайлов С.В., Романов В.В., Заїкін Д.А. Система технічного зору для діагностики процесу різання матеріалів// Вісник комп'ютерних та інформаційних технологій, 2007 № 3. - С. 12-19.

5. Сьомін М.С. Огляд рішення прикладних завдань з допомогою систем технічного зору// http://www.videoscan.ru/page/718#13.

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

Сутність гібридного алгоритму обробки зображень у СТЗ мобільного робототехнічних комплексів (МРК) полягає у приведенні вихідного зображення сцени до виду, що дозволяє вирішити задачу розпізнавання її об'єктів.

Алгоритм попередньої обробки зображення за допомогою нечіткої системи у СТЗ

До обробки зображень нечітка обробка є безліч різних нечітких підходів, якими є розуміння, уявлення, обробки зображень, сегменти і нечіткі множини. У процесі розпізнавання образів велике значення має процес попередньої нечіткої обробки зображень, оскільки саме від нього залежить якість даних, що далі надходять на входи нейронної мережі. У рамках розв'язуваного завдання розроблений алгоритм попередньої нечіткої обробки можна представити у вигляді наступної послідовності кроків (рис. 1): захоплення зображення за допомогою веб-камери; перетворення отриманого кольорового зображення зображення в градаціях сірого кольору; нечітка обробка зображень.

Рис. 1. Алгоритм попередньої нечіткої обробки зображення

Таким чином, першим кроком попередньої нечіткої обробки є перетворення зображення з кольорового на відтінки сірого. Перетворення кольорів зображення на відтінки сірого кольору здійснюється в такий спосіб. Вся палітра кольорів представляється у вигляді куба, вершини якого відповідають різним кольорам. Сіра шкала розташовується на діагоналі куба, що з'єднує чорну та білу вершини.

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

де - нове значення кольору, - інтенсивність червоної складової кольору, - інтенсивність зеленої складової кольору, а - інтенсивність синій складової кольору. Вихід кожного алгоритму відтінки сірого між 0 і 1. Для перетворення зображень на використовувані тільки відтінки сірого існує деякі методи. У способі визначення світлоти використовується середнє між двома найбільш і найменш значущими кольорами: . У методі середнього використовується середнє значення всіх трьох кольорів: . У методі визначення яскравості використовується виважене середнє значення всіх трьох кольорів, що враховує сприйняття людини. Так, оскільки людське око найбільш сприйнятливе до зеленого кольору, його вага вважається найважливішим: . Метод визначення яскравості використовується програмне забезпеченнядля обробки зображень. Він реалізований функцію « rgb2gray» в середовищі MATLAB і це часто використовується для комп'ютерного зору. У процесі попередньої нечіткої обробки процес перетворення зображень з кольорового (RGB) у відтінки сірого за допомогою методу визначення яскравості. Далі зображення перетворюється з відтінку сірого на чорно-білий (рис. 2).

Рис. 2. процес перетворення зображень з кольорового у відтінки сірого

Бінарізація зображення під час попередньої обробки

Метою попередньої нечіткої обробки зображення є формування та подальше покращення зображення, його бінаризація та кодування (зокрема, отримання контурного подання). Бінаризація зображення є процес перетворення зображення, що складається з градації одного кольору (у разі - сірого), в бінарне зображення, тобто. зображення, в якому кожен піксель може мати лише два кольори (у нашому випадку це чорний та білий кольори). В результаті такого перетворення, колір пікселя умовно вважають рівним нулю або одиниці, при цьому пікселі з нульовим значенням (в даному випадку це пікселі білого кольору) називають заднім планом, а пікселі зі значенням рівним одиниці (чорного кольору) називають переднім планом. Але бінарне зображення, отримане в результаті такого перетворення, спотворюється, порівняно з оригіналом, що характеризується появою розривів та розмитостей на об'єктах, виникненням зашумлень зображення в однорідних областях, а також до втрати цілісності структури об'єктів.

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

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

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

У процесі бінаризації всі методи поділяються на дві групи за принципом побудови граничної поверхні - це методи глобальної та локальної обробки бінаризації. p align="justify"> У методах глобальної обробки бінаризації порогова поверхня є площиною з постійним значенням порогової яскравості, тобто. значення порога розраховується виходячи з аналізу гістограми всього зображення та є однаковим для всіх пікселів вихідного зображення. Глобальна порогова обробка має істотний недолік - якщо вихідне зображення має неоднорідне освітлення, області, які гірше освітлені, цілком класифікуються як передній план. У локальних методах обробки бінаризації порогове значення змінюється кожної точки з деяких ознак області, що належить певної околиці цієї точки. Недоліком такого роду перетворень є низька швидкістьроботи алгоритмів, пов'язана з перерахуванням порогових значень кожної точки зображення.

Як метод для вирішення поставленого завдання скористаємося методом Бернсена. Спосіб базується на ідеї зіставлення рівня яскравості перетворюваного пікселя зі значеннями локальних середніх, що обчислюються в його оточенні. Пікселі зображення обробляються по черзі шляхом порівняння їх інтенсивності із середніми значеннями яскравості у вікнах із центрами у точках (рис.3).

Рис. 3. Перетворення пікселя зображення

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

Після перетворення зображення на чорно-білий, виходить градієнтне зображення за допомогою оператора Собеля і надходить на входи нечіткої обробки зображення (НДІ) (рис. 4).

Нечітка обробка зображень складається з трьох основних етапів: фазифікація зображень, система нечіткого виведення на значеннях приналежності та дефаззифікація зображень. Головна нечітка обробка зображень перебуває у середньому кроці (система нечіткого виведення ). Після передачі даних зображення з сірого рівня фазифікацію, система нечіткого виведення визначається значенням приналежності. Фаззифікація – кодування даних зображень та дефаззифікація – декодування результатів, які дозволяють обробляти зображення з нечіткими методами.

Зображення - розмір із сірими рівнями і може бути визначено як масив нечітка одноточкова множина (нечіткі множини можна підтримувати тільки з однією точкою), що вказує значення приналежності кожного пікселя щодо заздалегідь властивості зображення (наприклад - яскравість, гладкість і т.д.).

(1)

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

Вихід системи для вхідної системи задається такою формулою:

(2)

Рис. 4. Алгоритм нечіткої обробки зображень виділення кордонів

Застосування нейронних мереж для розпізнавання образів

Багатошаровим персептроном називають штучну нейронну мережу, що складається з кількох вхідних вузлів, що утворюють вхідний шар, одного або кількох обчислювальних шарів нейронів та одного вихідного шару (рис. 6). У таких мережах сигнал, що подається на вхідний шар, послідовно передається в прямому напрямку від шару до шару. Цей типІНС успішно застосовується на вирішення різноманітних завдань, зокрема завдання розпізнавання образів .

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

Одним із найпоширеніших алгоритмів навчання багатошарових нейронних мереж є алгоритм зворотного поширення помилки. У цьому алгоритмі обчислюється вектор градієнта помилок. Потім просуваємось на деяку величину в напрямку вектора (він буде вказувати нам напрямок якнайшвидшого спуску), де значення помилки буде вже менше. Такий послідовний поступ поступово призведе до мінімілізації помилки. Тут виникає труднощі з визначенням величини, яку слід просуватися. Якщо величина кроку буде відносно великою, це призведе до якнайшвидшого спуску, однак є можливість «перестрибнути»

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

Введемо такі позначення. Матрицю вагових коефіцієнтів від входів до прихованого шару позначимо , а матрицю ваг, що з'єднують прихований та вихідний шар - . Для індексів приймемо такі позначення: входи нумеруватимемо тільки індексом , елементи прихованого шару - індексом , а виходи - індексом . Число входів мережі дорівнює, число нейронів у прихованому шарі-, число нейронів у вихідному шарі-. Нехай мережа навчається на вибірці. Тоді алгоритм навчання багатошарового персептрона буде виглядати так:

Крок 1. Ініціалізація мережі. Ваговим коефіцієнтам надаються малі випадкові значення, наприклад, з діапазону (-0.3, 0.3); задаються параметр точності навчання, параметр швидкості навчання (як правило, і може ще зменшуватися в процесі навчання), максимально допустиме число ітерацій.

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

Крок 3. Налаштування синоптичних ваг. Розрахувати зміну ваги для вихідного шару нейронної мережі за формулами:

де , . Розрахувати зміну ваги для прихованого шару за формулами: , де

Крок 4. Кроки 2-3 повторюються всім навчальних векторів. Навчання завершується після досягнення для кожного з навчальних образів значення функції помилки, що не перевищує е або після максимально допустимого числа ітерацій.

На кроці 2 вектори з навчальної послідовності краще пред'являти вхід у випадковому порядку.

Кількість входів і виходів мережі, зазвичай, диктується умовами завдання, а розмір прихованого шару знаходять експериментально. Зазвичай число нейронів у ньому становить 30-50% від числа входів. Занадто багато нейронів прихованого шару призводить до того, що мережа втрачає здатність до узагальнення (вона просто досконало запам'ятовує елементи навчальної вибірки і не реагує на схожі зразки, що неприйнятно для завдань розпізнавання). Якщо число нейронів у прихованому шарі занадто мало, мережа виявляється просто не в змозі навчитися.

Висновок

Розглянуто основні проблеми, а також шляхи їх вирішення під час первинної підготовки зображення до розпізнавання. Детально розібрано алгоритм попередньої обробки за допомогою нечіткої логіки та процес бінаризації зображення. Побудовано алгоритм нечіткої обробки виділення кордонів у зображенні з допомогою оператора Собеля.

Рецензенти:

Гагаріна Л.Г., д.т.н., професор, завідувач кафедри «Інформатика та програмне забезпечення обчислювальних систем» Національного дослідницького університету «МІЕТ», м. Москва.

Портнов Є.М., д.т.н., професор кафедри «Інформатика та програмне забезпечення обчислювальних систем», начальник науково-дослідної лабораторії «Управляючі інформаційні системи»Національного дослідницького університету «МІЕТ», м. Москва.

Бібліографічне посилання

Аунг Ч.Х., Тант З.П., Федоров А.Р., Федоров П.А. РОЗРОБКА АЛГОРИТМІВ ОБРОБКИ ЗОБРАЖЕНЬ ІНТЕЛЕКТУАЛЬНИМИ МОБІЛЬНИМИ РОБОТАМИ НА ОСНОВІ нечіткої ЛОГІКИ І НЕЙРОННИХ МЕРЕЖЕЙ // Сучасні проблеми науки та освіти. - 2014. - № 6.;
URL: http://science-education.ru/ru/article/view?id=15579 (дата звернення: 01.02.2020). Пропонуємо до вашої уваги журнали, що видаються у видавництві «Академія Природознавства»

ЦИФРОВА ОБРОБКА СИГНАЛІВ

Тема 17. ОБРОБКА зображень

Немає нічого, на що б не зважило уяву людини.

Тіт Лукрецій. Римський філософ та поет. І ст. до зв. е.

Уява річ хороша. Але витягнути бомжа з підвалу, відмити, перетворити на Аполлона, запакувати в сірникову коробку і відправити подрузі по електронній поштіхороша графічна програма зробить краще.

Анатолій Пишмінцев, Новосибірський геофізик Уральської школи. ХХ ст.

Вступ.

1. Основні поняття. Графічне уявленнязображень. Подання кольору у машинній графіці. Колірна модель RGB. Колірна система CIE XYZ.

2. Геометричні перетворення растрових зображень. Області та етапи перетворень. Дискретизація. Інтерполяційний ряд відновлення двовимірного сигналу Частотні спотворення зображень та їх усунення. Передискретизація зображень.

3. Фільтрування зображень. Лінійні фільтри Фільтри, що згладжують. Контрастопідвищувальні фільтри. Різнісні фільтри. Двовимірна циклічна згортка. Нелінійні фільтри Порогова фільтрація. Медіанна фільтрація. Фільтри екстремумів.

4. Стиснення зображень. Алгоритми кодування довжини повторення (RLE). Словникові алгоритми. Алгоритми статистичного кодування. Стиснення зображень із втратами. Оцінка втрат у зображеннях. Перетворення Фур'є. Вейвлет-перетворення.

ВСТУП

Розмах досліджень у галузі цифрової обробки зображень стрімко наростає. Це визначається тим, що обробка зображень – це обробка багатовимірних сигналів, а більшість сигналів у реальному світі є багатовимірними.

Зображення в математичному уявленні - двовимірний сигнал, що несе величезну кількість інформації. Кольорове зображення розміром 500×500 елементів – це масив у кілька сотень тисяч байтів. Обробляти таку інформацію можна лише раціональною організацією обчислень. Для конкретних завдань обробки зображень можна застосовувати ефективні способиобробки з урахуванням особливостей та обмежень цього конкретного завдання. Але якщо говорити про обробку зображень для вирішення широкого класу завдань, то необхідно виділити набір стандартних операцій, у тому числі можна будувати алгоритми на вирішення довільних завдань. До них відносяться лінійні перетворення, двовимірна згортка і двовимірне дискретне перетворення Фур'є.

Але під час обробки зображень широке використання знаходять і нелінійні перетворення. Особливість зображень полягає в тому, що окремі елементи зображення знаходяться у певному зв'язку із сусідніми елементами. Тому більшість алгоритмів перетворення зображень носить локальний характер, тобто обробляють зображення за групами елементів, що розташовуються навколо навколо даного. Лінійні перетворення задовольняють властивості локальності і допускають побудову алгоритмів, обчислювальна складність яких мало залежить від розмірів околиці, що охоплюється. Такі самі властивості потрібні і від нелінійних перетворень зображень. До класу таких перетворень відносяться алгоритми, які називають алгоритмами рангової фільтрації, що ґрунтуються на обчисленні локальних рангових статистик зображень. При обчисленні рангових статистик та похідних від них можливі спрощення, пов'язані з інформаційною надмірністю зображень. Найбільш відомий алгоритм цього класу – алгоритм медіанної фільтрації. Іншими прикладами рангових алгоритмів можуть бути алгоритми екстремальної фільтрації, які замінюють аналізований елемент зображення максимумом або мінімумом по околиці. Ще одна властивість рангових алгоритмів – локальна адаптація до характеристик оброблюваного зображення та потенційні можливості їх використання не тільки для згладжування та очищення від шумів, але й для виділення ознак при автоматичному розпізнаванні зображень.

При обробці зображень широко використовуються методи обробки одновимірних сигналів, якщо можливе їх узагальнення багатовимірні сигнали. При цьому доводиться враховувати, що математичні методи опису багатовимірних систем не відрізняються завершеністю. Багатомірні системи мають велику кількість ступенів свободи, та його проектування набуває гнучкість, не властиву одновимірним системам. У той же час, багатовимірні поліноми не розкладаються на прості множники, що ускладнює аналіз та синтез багатовимірних систем.

17.1. Основні поняття

Графічні подання зображень. Для представлення графічної інформації на двовимірній площині (екрані монітора) застосовуються два підходи: растровий та векторний.

При векторному підході графічна інформаціяописується як сукупність абстрактних геометричних об'єктів- Прямі, відрізки, криві, прямокутники і т. п. Векторний опис передбачає апріорні знання про структуру зображення.

Растрова графіка оперує з довільними зображеннями у вигляді растрів. Растр - це опис зображення на площині шляхом розбиття (дискретизації) його на однакові елементи по регулярній сітці та присвоєння кожному елементу свого колірного та будь-яких інших атрибутів. Найпростіший растр – прямокутний, найекономічніший за кількістю відліків передачі зображень - гексагональний. З математичних позицій растр – це шматково-постійна апроксимація на площині безперервної функції зображення.

Елемент растру називають пікселем (pixel). Стандартна ідентифікація пікселів:

f(i, j) = (A(i, j), C(i, j)), (17.1.1)

де A(i, j) R2 - область пікселя, C(i, j) Î C - атрибут пікселя (як правило, колір). Найчастіше використовуються два види атрибутів:

C(i, j) = I(i, j) – інтенсивність (яскравість) пікселя;

C(i, j) = (R(i, j), G(i, j), B(i, j)) - колірні атрибути у колірній моделі RGB.

У матричній формі:

Mij ​​= (Aij, Cij).

При дискретизації безперервних зображень значення Aij можуть визначатися подвійно, або як значення точок Aij = (i, j), для яких визначено атрибути Cij, або як значення квадратів Aij = (i, i+1) × (j, j+1) або будь-якої іншої форми, з визначенням Cij за середніми значеннями в межах цієї форми (рис. 17.1.1).

Насправді, зазвичай, X і Y - обмежені набори неотрицательных цілих чисел квадратного чи прямокутного растру з аспектовим ставленням (aspect ratio) ширини до висоті растру, яке записується як, наприклад "4:3".

Подання кольору у машинній графіці. Поняття кольору базується на сприйнятті очима людини електромагнітних хвиль у певному діапазоні частот. Денне світло, що сприймається нами, має довжини хвиль λ від 400 нм (фіолетовий) до 700 нм (червоний). Описом світлового потокуможе бути його спектральна функція I(λ). Світло називається монохроматичним, якщо його спектр має лише одну певну довжину хвилі.

На сітківці ока знаходяться два типи рецепторів: палички та колбочки. Спектральна чутливість паличок (рис. 17.1.2) прямо пропорційна яскравості падаючого світла. Колбочки поділяються на три види, кожен з яких має певну чутливість в обмежених діапазонах з максимумами до червоного, зеленого та синього кольорів, і різко втрачають свою чутливість у темряві. Сприйнятливість ока до синього кольору значно нижча, ніж до двох інших. Важливою властивістю сприйняття світла людиною є лінійність при складанні кольорів із різними довжинами хвиль.

Колірна модель RGB (Red, Green, Blue – червоний, зелений, блакитний) у машинній графіці в даний час є найпоширенішою. У цій моделі спектральна функція представляється як сума кривих чутливості для кожного типу колб із невід'ємними ваговими коефіцієнтами (з нормуванням від 0 до 1), які так і позначаються - R, G і B. Модель характеризується властивістю адитивності для отримання нових кольорів. Наприклад, кодування спектральних функцій:

Чорного кольору: fblack = 0, (R, G, B) = (0,0,0);

Фіолетового кольору fviolet = fred + fblue, (R, G, B) = (1,0,1);

Білого кольору fwhite = fred + fgreen + fblue, (R, G, B) = (1,1,1).

Тривимірний простір кольорів моделі RGB наведено на рис. 17.1.3. З огляду на особливості сприйняття світла рецепторами в повному обсязі кольори, видимі людиною, представні у цій моделі. Однак частка відтворюваних кольорів значно більша, ніж частка не представлених у цій моделі.

Колірна система CIE XYZ. Міжнародний стандарт подання кольору CIE (CIE - Commission Internationale de l'Eclairage) був прийнятий у 1931 році Міжнародною комісією з висвітлення. У ньому визначаються три базисні функції ρX(λ), ρY(λ), ρZ(λ), що залежать від довжини хвилі , лінійні комбінації яких з невід'ємними коефіцієнтами (X, Y і Z) дозволяють отримати всі видимі людиною кольори.Цими функціями враховується відносне сприйняття інтенсивності світла рецепторами ока.У тривимірному просторі колірна система CIE утворює конус у першому квадранті та застосовується для високоякісного відображення кольорових зображень.

17.2. Геометричні перетворення растрових зображень

Області та етапи перетворень. Зображення можна розділити на текстури та деталі. У текстурних зображеннях всі відліки (елементи) несуть інформацію (зображення на екрані телевізора). Детальним називається зображення, на якому можна виділити об'єкти, що заважають, фон і корисні об'єкти.

Існують три основні групи алгоритмів обробки зображень на комп'ютерах:

1. Первинна (попередня) обробка зображень з метою реставрації, очищення від випадкових шумів, покращення якості, корекції геометричних спотворень оптичних систем (розфокусування, аберація тощо).

2. Опис зображень, розпізнавання образів. Виконується визначення параметрів деталей зображення і включає: знаходження однорідних за рівнем освітленості і кольору областей зображення, виділення ознак форми зображень, визначення координат особливих точок об'єктів тощо.

3. Ефективне кодування для зменшення обсягу при передачі та зберіганні.

Більшість методів первинної обробкизасновані на використанні лінійних просторово-інваріантних (ЛПІ) фільтрів. Лінійні алгоритмивиконуються за допомогою двовимірних аналогів одновимірних КІХ та БІХ фільтрів. Їх можна застосовувати, наприклад, при реалізації фільтрів зниження рівня шуму на зображеннях.

КІХ фільтри реалізуються методом згортки. Перевагою двовимірних КІХ фільтрів є наочність, простота та абсолютна стійкість. БІХ фільтри реалізуються за допомогою різницевих рівнянь та z-перетворень. Вони більш швидкісні в порівнянні з КІХ фільтрами, але можуть виявитися нестійкими. Синтез двовимірних БІХ фільтрів відрізняється від синтезу одновимірних, тому що для двовимірної функції у явному вигляді не вдається виділити полюси.

Для реставрації зображень та покращення їх якості можуть знадобитися і нелінійні методи. Так, наприклад, щоб придушити шум і зберегти контурну частину зображень, доводиться застосовувати нелінійні або лінійні просторово-неінваріантні (ЛПНІ) фільтри, які реалізуються ранговими алгоритмами. Усі рангові нелінійні фільтри засновані на швидких алгоритмах обчислення локальних гістограм.

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

Алгоритми опису зображень та розпізнавання образів, як правило, нелінійні та носять евристичний характер. Ознаками об'єктів зазвичай є площа зображення об'єкта, периметр контуру зображення, відношення площі квадрату периметра зображення. Форму об'єкта можна охарактеризувати радіусом, вписаним у зображення або описаним навколо зображення об'єкта кола, довжиною мінімального та максимального радіус-вектора від “центру мас” зображення.

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

У найпростішому випадку чорно-білих зображень ми маємо двомірний масив sa(x, y). Для кольорових зображень у моделі RGB, враховуючи властивість адитивності при додаванні кольорів, кожен шар R, G і B також може розглядатися та оброблятися, як двовимірний масив, з подальшим підсумовуванням результатів.

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

s(n, m) = sa(nDx, mDy),

де Dx та Dy - горизонтальний та вертикальний інтервали дискретизації двовимірного безперервного сигналу sa(x, y) з безперервними координатами x та y. Нижче значення Dx та Dy, як і в одновимірному випадку, приймаються рівними 1.

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

S(k, l) = s(n, m) exp(-jn2pk/N-jm2pl/M), (17.2.1)

S(k, l) = exp(-jn2pk/N) s(n, m) exp(-jm2pl/M), (17.2.1")

s(n, m) = S(k, l) exp(-jn2pk/N-jm2pl/M). (17.2.2)

s(n, m) = exp(-jn2pk/N) S(k, l) exp(-jm2pl/M). (17.2.2")

Рис. 17.2.1. Періодизація діапазону.

Ці вирази показують, що двовимірне ДПФ прямокутного растру дискретизації даних може обчислюватися за допомогою одномірних послідовних ДПФ. Другі суми виразів (17.2.1") та (17.2.2") є одновимірними ДПФ перерізів функцій s(n, m) і S(k, l) по лініях n і k відповідно, а перші - одновимірними ДПФ обчислених функцій у перерізах по m та l. Іншими словами, вихідні матриці значень s(n, m) і S(k, l) перераховуються спочатку в проміжні матриці з ДПФ рядками (або стовпцями), а проміжні - остаточні з ДПФ стовпчиками (або відповідно рядками).

Для того щоб періодичне повторення спектру (рис. 17.2.1), викликане дискретизацією аналогового сигналу з частотою Fx=1/Dx і Fy=1/Dy, не змінювало спектр у головному частотному діапазоні (стосовно спектру вихідного аналогового сигналу), необхідно і достатньо, щоб максимальні частотні складові fmax у спектрі аналогового сигналу як по рядках, так і по стовпчикам не перевищували частоти Найквіста (fmax. x £ fN = Fx/2, fmax. y £ fM = Fy/2). Це означає, що частота дискретизації сигналу повинна бути мінімум вдвічі вищою за максимальну частотну складову в спектрі сигналу:

Fx ³ 2fmax. x, Fy ³ 2fmax. y, (17.2.3)

що забезпечує вихід спектральних функцій на нульові значення кінцях головного діапазону спектра.

Інтерполяційний ряд відновлення двовимірного сигналу Якщо безперервний сигнал sa(x, y) є сигналом з обмеженим спектром, а періоди дискретизації обрані досить малими та спектри сусідніх періодів не перекриваються:

Sa(Wx, Wy) = 0 при |Wx|p/Dx, |Wy|p/Dx,

те, як і в одновимірному випадку, сигнал sa(x, y) може бути відновлений за дискретним сигналом з використанням двовимірного аналога ряду Котельникова-Шеннона:

sa(x, y) = Sn Sm s(n, m) . (17.2.4)

Частотні спотворення зображень та їх усунення. Сигнал з необмеженим спектром також може бути дискретизований, однак у цьому випадку має місце накладення спектрів у суміжних періодах, причому високі частоти, великі частоти Найквіста, будуть "маскуватися", як і в одновимірному випадку, під низькі частотиосновного періоду. Ефект "віддзеркалення" від меж періоду дає ще більш складну картину внаслідок інтерференції частот, відображених за різними координатами. Аналогічний ефект, відомий як аліасинг (aliasing), буде спостерігатися і при недостатній частоті дискретизації зображень. Особливо цей ефект можна спостерігати на різких контрастних змінах яскравості.

Для боротьби з подібними явищами застосовують префільтрацію (антіаліасинг) – попередню згортку аналогового зображення з ваговою функцією фільтра, що відсікає високочастотні компоненти, які можуть призвести до аліасингу. У двовимірному випадку фільтрація описується так:

z(x, y) = h(x", y") ③③ s(x-x", y-y"). (17.2.5)

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

На рис. 17.2.3 та нижче, у таблиці 17.2.1 наведено приклади найбільш поширених одновимірних фільтрів для антиалісингу. Вони можуть виконуватися і у вигляді аналогових фільтрів, і застосовуватись, наприклад, при передачі телевізійних рядків зображень в аналоговій формі по радіоканалах (антіаліасинг по горизонталі). У принципі, подібна операція може виконуватися і по стовпцях (дубль - зображення), і після підсумовування зображення буде виконана повна операція антиалісінгу, але такий метод відноситься більше до галузі спеціальних наукових досліджень.

Таблиця 17.2.1.

Основні вагові функції

Тимчасове вікно	Вагова функція	Фур'є-образ
Природне (П)	П(t) = 1, | t | £ t; П(t) = 0, |t|>t	П(w) = 2t sinc
Бартлетта (D)		B(w) = t sinc2(wt/2).
Хеннінга, Ганна	p(t) = 0.5	0.5П(w)+0.25П(w+p/t)+0.25П(w-p/t)
Хеммінга	p(t) = 0.54+0.46 cos(pt/t)	0.54П(w)+0.23П(w+p/t)+0.23П(w-p/t)
Карре (2-е вікно)	p(t) = b(t) sinc(pt/t)	t B (w) * П (w), П (w) = 1 при | w |
Лапласа-Гаусса	p(t) = exp[-b2(t/t)2/2]	[(t/b) exp(-t2w2/(2b2))] ③ П(w)

Двовимірні аналоги одновимірних фільтрів f1(x) будуються у двох варіантах симетрії: або як функція від радіусу:

f2(x, y) = f1(),

або як твір:

f2(x, y) = f1(x) × f1(y).

Перший варіант - коректніший, але другий має властивість сепарабельності, тобто двовимірну згортку можна виконувати двома одновимірними згортками послідовно по рядках з f1(x) і по стовпцях з f1(y).

Передискретизація зображення або ресамплінг (resampling) – це зміна частоти дискретизації цифрового сигналу. Що стосується цифрових зображень, це означає зміну розмірів зображення.

Існують різні алгоритми ресамплінгу зображень. Наприклад, збільшення зображення в 2 разу методом білінійної інтерполяції (bilinear interpolation) проміжні стовпці і рядки отримують лінійною інтерполяцією значень сусідніх стовпців і рядків. Кожну точку нового зображення можна отримати як виважену суму більшої кількості точок вихідного зображення (бікубічна та інші види інтерполяції). p align="justify"> Найбільш якісний ресамплінг виходить при використанні алгоритмів, що враховують не тільки тимчасову, але і частотну область сигналу.

Розглянемо алгоритм ресамплінгу із максимальним збереженням частотної інформації зображення. Роботу алгоритму будемо розглядати на одновимірних сигналах, оскільки двовимірне зображення можна спочатку розтягнути або стиснути по горизонталі (по рядках), а потім – по вертикалі (по стовпцях), і звести ресамплінг двовимірного зображення до ресамплінгу одновимірних сигналів.

Допустимо, ми маємо одновимірний сигнал (рис. 17.2.4), заданий на інтервалі 0-Т та дискретизований з кроком Dt=1 (N інтервалів). Потрібно "розтягнути" сигнал у m разів. Спектр сигналу, показаний малюнку, обчислюється швидким перетворенням Фур'є (БПФ, кількість відліків спектра дорівнює кількості відліків сигналу) і наводиться у головному діапазоні БПФ (0-2p, частота Найквіста wN = p/Dt = p, чи 0.5N за нумерацією відліків спектра при кроці спектром Df = 1/T або Dw = 2p/T). Для виконання розтягування необхідно виконати 2 кроки.

Перший крок - інтерполяція нулями, що збільшує довжину сигналу в m разів. (Рис. 17.2.5). Потрібно помножити всі відліки вихідного сигналу на m, потім після кожного відліку сигналу вставити m-1 нульове значення. На інтервалі 0-Т, значення якого залишається без зміни, тепер розташовується в m-раз більше інтервалів дискретизації (mN), і новий крок дискретизації дорівнюватиме Dx=Dt/m. Відповідно, нова частота Найквіста для цього сигналу дорівнює mp/Dt = mp. Але фізична величина кроку по спектру в одиницях частоти зворотна фізичній величині інтервалу завдання сигналу (Df=1/T), і, отже, БПФ по mN точках сигналу обчислить mN точок спектра в головному діапазоні БПФ 0-2pm з кроком спектра вихідного сигналу, якому будуть присутні m-періодів спектра вихідного сигналу (один головний та m-1 бічних).

Другий крок – відфільтровування бічних діапазонів спектра за допомогою НЧ-фільтра або в часовій, або спектральній області. На рис. 17.2.6 виконано очищення спектра та зворотне перетворення Фур'є, в результаті чого отриманий сигнал у m разів довше вихідного з повним збереженням всієї частотної інформації.

За аналогічним принципом може бути побудований і алгоритм стиснення (децимації) сигналу в n разів, причому порядок кроків змінюється на зворотний. При стисненні сигналу виконується збільшення кроку дискретизації сигналу і, відповідно, зменшення частоти Найквіста, при цьому високі частоти, що відрізаються (шуми і незначні високочастотні частини спектру сигналу) будуть відображатися від межі головного діапазону і сумуватися з основною інформацією, створюючи спотворення. Для виключення цього явища спочатку проводять низькочастотну фільтрацію сигналу з частотою зрізу, що дорівнює новій частоті Найквіста (антіаліасинг), і тільки потім децимацію сигналу шляхом проріджування.

При виконанні ресамплінгу тільки в часовій області алгоритми розтягування та стиснення об'єднують, як правило, у єдиний послідовний процес із завданням зміни кроку дискретизації у вигляді відношення m/n, що дозволяє задавати цілі значення m та n при дробових значеннях зміни кроку дискретизації. Це суттєво спрощує алгоритми та підвищує ефективність та якість їх роботи. Так, наприклад, при розтягуванні сигналу в 1.5 рази при m/n = 3/2 сигнал спочатку розтягується в 3 рази (просте і рівномірне доповнення нулями всіх відліків, потім виконується НЧ-фільтрація, після чого сигнал проріджується в два рази. Антіаліасингового фільтра не потрібно , т. к. частота його зрізу перекривається частотою першого НЧ-фільтра.

17.3. фільтрація зображень

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

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

Лінійні фільтри мають дуже простий математичний опис. Вважатимемо, що задано вихідне напівтонове зображення A, і позначимо інтенсивності його пікселів A(x, y). Лінійний фільтр визначається речовиннозначною функцією h (ядром фільтра), заданою на растрі. Сама фільтрація проводиться за допомогою операції дискретної згортки (зваженого підсумовування):

B(x, y) = h(i, j) ③A(x, y) = h(i, j) A(x-i, y-j). (17.3.1)

Результатом служить зображення B. Зазвичай ядро ​​фільтра відмінно від нуля тільки в околиці N точки (0, 0). За межами цієї околиці h(i, j) дорівнює нулю, або дуже близько до нього і їх можна знехтувати. Підсумовування проводиться за (i, j) N, і значення кожного пікселя B(x, y) визначається пікселями зображення A, які лежать у вікні N, центрованому в точці (x, y) (позначення - безліч N(x, y) ). Ядро фільтра, задане прямокутної околиці N, може розглядатися як матриця m на n, де довжини сторін є непарними числами. При завданні ядра матрицею її слід центрувати. Якщо піксель (x, y) знаходиться на околиці країв зображення, то координати A(x-i, y-j) для певних (i, j) можуть відповідати неіснуючим пікселям A за межами зображення. Цю проблему можна вирішити кількома способами.

Не проводити фільтрацію для таких пікселів, обрізавши зображення B з обох боків, або застосувавши для їх значень вихідні значення зображення А.

Не включати відсутній піксель до підсумовування, розподіливши його вага h(i, j) рівномірно серед інших пікселів околиці N(x, y).

Визначити значення пікселів за межами зображення за допомогою екстраполяції.

Визначити значення пікселів за межами зображення за допомогою дзеркального продовження зображення.

Вибір способу здійснюється з урахуванням конкретного фільтра та особливостей зображення.

Фільтри, що згладжують. Найпростіший прямокутний згладжуючий фільтр радіуса r задається за допомогою матриці розміру (2r+1) × (2r+1), всі значення якої дорівнюють 1/(2r+1)2, а сума значень дорівнює одиниці. Це двовимірний аналог низькочастотного одновимірного П-подібного фільтра ковзного середнього. При фільтрації з таким ядром значення пікселя замінюється усередненим значенням пікселів у квадраті зі стороною 2r+1 навколо нього. Приклад маски фільтра 3×3:

.

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

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

.

Більш ефективне шумозаглушення можна здійснити, якщо вплив пікселів на результат зменшуватиметься зі збільшенням відстані від оброблюваного. Цю властивість має гаусівський фільтр з ядром: h(i, j) = (1/2ps2) exp(-(i2+j2)/2s2). Гаусівський фільтр має ненульове ядро ​​нескінченного розміру. Однак значення ядра фільтра дуже швидко зменшується до н), і тому на практиці можна обмежитися згорткою з вікном невеликого розміру навколо (0, 0), наприклад, взявши радіус вікна рівним 3σ.

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

Контрастопідвищувальні фільтри . Якщо фільтри, що згладжують, знижують локальну контрастність зображення, розмиваючи його, то контрастопідвищуючі фільтри справляють зворотний ефект і, по суті, є фільтрами високих просторових частот. Ядро контрастопідвищуючого фільтра в точці (0, 0) має значення більше 1 при загальній сумі значень, що дорівнює 1. Наприклад, контрастопідвищуючими фільтрами є фільтри з ядром, що задається матрицями:

. .

Приклад застосування фільтра наведено на рис. 17.3.1. Ефект підвищення контрасту досягається завдяки тому, що фільтр підкреслює різницю між інтенсивностями сусідніх пікселів, видаляючи ці інтенсивності друг від друга. Цей ефект буде тим сильнішим, чим більше значення центрального члена ядра. Характерним артефактом лінійної контрастопідвищуючої фільтрації є помітні світлі та менш помітні темні ореоли навколо кордонів.

Різнісні фільтри – це лінійні фільтри, які задаються дискретними апроксимаціями диференціальних операторів (за методом кінцевих різниць). Дані фільтри відіграють найважливішу роль багатьох додатках, наприклад, завдань пошуку кордонів на зображенні.

Найпростішим диференціальним оператором є взяття похідної по x-координаті d/dx, визначений для безперервних функцій. Найпоширенішими варіантами аналогічних операторів для дискретних зображень є фільтри Прюїта (Prewitt) та Собеля (Sobel):

. .

Фільтри, що наближають оператор похідної по y-координату d/dy, виходять шляхом транспонування матриць.

Найпростіший алгоритм обчислення норми градієнта за трьома суміжними точками:

G(x, y) = .

Застосовується також спрощена формула обчислень:

Обчислення норми градієнта за чотирма суміжними точками (оператор Робертса):

В алгоритмі Собеля використовується вісім відліків яскравості на околицях центральної точки:

G(x, y) = , G(x, y) @ ,

Gxx, y = - ,

Gyx, y = -.

Поряд з більш точним визначенням норми градієнта алгоритм Собеля дозволяє визначати напрям вектора градієнта в площині аналізу зображення у вигляді кута j між вектором градієнта і напрямком рядків матриці:

j(x, y) = argtg(Gyx, y/Gxx, y).

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

Аналогічно наведеним вище фільтрам, за методом кінцевих різниць можна скласти фільтри для інших диференціальних операторів. Зокрема, важливий для багатьох додатків диференціальний оператор Лапласа (лапласіан) D= 𝝏2/𝝏x2 + 𝝏2/𝝏y2 можна наблизити для дискретних зображень фільтром з матрицею (один з варіантів):

.

Як бачимо на рис. 17.3.2 в результаті застосування дискретного лапласіана великі за модулем значення відповідають як вертикальним, так і горизонтальним перепадам яскравості. Фільтр є таким чином фільтром, що знаходить межі будь-якої орієнтації. Знаходження кордонів на зображенні може здійснюватися шляхом застосування цього фільтра та взяття всіх пікселів, модуль значення яких перевершує певний поріг.

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

Двовимірна циклічна згортка. Як і для одновимірних сигналів, двовимірна згортка може виконуватися в області просторових частот з використанням алгоритмів швидкого перетворення Фур'є та перемноженням двовимірних спектрів зображення та ядра фільтра. Вона також є циклічною, і виконується зазвичай у ковзному варіанті. З урахуванням циклічності, для обчислення постійного шаблону спектра ядра розміри маски фільтра ядра подвоюються по осях і доповнюються нулями, і ці ж розміри маски використовуються для виділення вікна, що ковзає по зображенню, в межах якого і виконується БПФ. Реалізація КІХ фільтра за допомогою БПФ особливо ефективна, якщо фільтр має велику опорну область.

Нелінійні фільтри . У цифровій обробці зображень широко використовуються нелінійні алгоритми на основі рангової статистики для відновлення зображень, пошкоджених різними моделями шумів. Вони дозволяють уникнути додаткового спотворення зображення при видаленні шуму, а також значно покращити результати роботи фільтрів на зображеннях із високим ступенем шумування.

Введемо поняття M-околиці елемента зображення A(x, y), який для цієї околиці центральним. У найпростішому випадку M-околиця містить N-пікселів - точки, що потрапляють в маску фільтра, включаючи (або не включаючи) центральний. Значення цих N-елементів можна розташувати в варіаційному ряду V(r), ранжированном за зростанням (або спаданням), і обчислити певні моменти цього ряду, наприклад, середнє значення яскравості mN та дисперсії dN. Обчислення вихідного значення фільтра, яким замінюється центральний відлік, виконується за такою формулою:

B(x, y) = aA(x, y) + (1-a)mN. (17.3.2)

Значення коефіцієнта a = зв'язується певною залежністю зі статистикою відліків у вікні фільтра, наприклад:

a = dN / (dN + k dS), (17.3.3)

де dS – дисперсія шумів за зображенням загалом або за S-околицями при S > M та MÎS, k – константа довіри дисперсії S-околиць. Як випливає з цієї формули, при k = 1 і dN » dS має місце a » 0.5, а значення B (x, y) = (А (x, y) + mN) / 2, тобто складаються рівною мірою від значень центрального відліку та середнього значення пікселів його M-околиці. При збільшенні значень dN відбувається збільшення вкладу результат значення центрального відліку, при зменшенні – значення mN. Вагомість вкладу середніх значень M-околиці можна змінювати значенням коефіцієнта k.

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

Найбільш простими та поширеними типами нелінійних фільтрів для обробки зображень є порогові та медіанні фільтри.

Порогова фільтрація задається, наприклад, наступним чином:

B(x, y) =

Величина pє порогом фільтрації. Якщо величина центральної точки фільтра перевищує середнє значення відліків mN у її М-околиці на величину порога, вона замінюється середнім значенням. Значення порога може бути як константою, і функціонально залежним від величини центральної точки.

Медіанна фільтрація визначається так:

B(x, y) = med (M(x, y)),

т. е. результат фільтрації є медіа значення пікселів околиці, форма якої визначається маскою фільтра. Медіанна фільтрація здатна ефективно видаляти зображення перешкоди, незалежно впливають на окремі пікселі. Наприклад, такими перешкодами є "биті" пікселі при цифровій зйомці, "сніговий" шум, коли частина пікселів замінюється на пікселі з максимальною інтенсивністю, і т. п. Перевага медіанної фільтрації полягає в тому, що "гарячий" піксель на темному тлібуде замінено темним, а не "розмазаним" по околиці.

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

Фільтри екстремумів визначаються за правилами:

Bmin(x, y) = min (M(x, y)),

Bmax(x, y) = max (M(x, y)),

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

17.4. Стиснення зображень

Типове зображення з роздільною здатністю близько 3000×2000 при 24 біт на піксель для передачі кольору має об'єм 17 мегабайт. Для професійних пристроїв розмір одержуваного растру зображень може бути значно більшим, глибина кольору до 48 біт на піксель, а розмір одного зображення може бути більше 200 мегабайт. Тому дуже актуальними є алгоритми стиснення зображень зменшення обсягу даних, що представляють зображення.

Існують два основні класи алгоритмів:

1. Стиснення без втрат А (lossless compression), якщо є такий зворотний алгоритм A-1, що з будь-якого h - зображення A[h] = h1 маємо A-1 = h. Стиснення без втрат застосовується в таких графічних форматахуявлення зображень, як: GIF, PCX, PNG, TGA, TIFF, і застосовується при обробці особливо цінної первинної інформації (медичні зображення, аеро- та космознімки тощо), коли навіть найменші спотворення небажані

2. Стиснення з втратами (lossy compression), якщо воно не забезпечує можливість точного відновлення вихідного зображення. Парний до A алгоритм зразкового відновлення зображення позначатимемо як A*. Пара (A, A*) підбирається так, щоб забезпечити більші коефіцієнти стиснення при збереженні візуальної якості. Стиснення з втратами застосовується у графічних форматах: JPEG, JPEG2000 і т.д.

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

Алгоритми кодування довжини повторення (RLE) базуються на простому принципі: заміні повторюваних груп елементів вихідної послідовності на пару (кількість, елемент), або лише кількість.

Битовий рівень. Розглянемо вихідні дані на рівні послідовності бітів, наприклад, що представляють чорно-біле зображення. Підряд зазвичай йде кілька 0 або 1, і кодувати можна кількість однакових цифр, що йдуть поспіль. Але кількість повторень також треба кодувати бітами. Можна вважати, що кожне число повторень змінюється від 0 до 7 (3-бітний код), чергуючи послідовність кодів одиниць і нулів. Наприклад, послідовності можна зіставити числа 7 0 4, тобто 7 одиниць, 0 нулів, 4 одиниці, при цьому маємо новий рік - Чим більша довжина послідовностей однакових біт, тим більший ефект. Так, послідовність з 21 одиниці, 21 нуля, 3 одиниць і 7 нулів закодується так: тобто з вихідної послідовності довжиною 51 біт, маємо послідовність довжиною 36 біт.

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

Будемо розбивати вхідний потік на байти (код від 0 до 255) і кодувати байти парою (кількість, літера). Поодинокий байт можна не змінювати. Так, байти AABBBCDAA кодуємо (2A) (3B) (C) (D) (2A).

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

Словникові алгоритми замість кодування тільки по одному елементу вхідної послідовності роблять кодування ланцюжка елементів. При цьому використовується словник ланцюжків (створений за вхідною послідовністю) для кодування нових.

Алгоритм LZ77 був одним із перших, що використовують словник. Як словник використовуються N останніх вже закодованих елементів послідовності. У процесі стиснення словник-підпослідовність "ковзає" за вхідною послідовністю. Ланцюжок елементів на виході кодується наступним чином: положення збігаючої частини оброблюваного ланцюжка елементів у словнику - зміщення (щодо поточної позиції), довжина, перший елемент, наступний за частиною ланцюжка, що збіглася. Довжина ланцюжка збігу обмежується зверху числом n. Відповідно, завдання полягає у знаходженні найбільшого ланцюжка зі словника, що збігається з оброблюваною послідовністю. Якщо ж збігів немає, записується нульове зміщення, одинична довжина і перший елемент незакодованої послідовності.

Описана схема кодування призводить до поняття ковзного вікна (sliding window), що складається з двох частин:

Підпослідовність вже закодованих елементів довжини N-словник – буфер пошуку (search buffer);

Підпослідовність довжини n із ланцюжка елементів, для якої буде зроблена спроба пошуку збігу - буфер попереднього перегляду(Look-ahead buffer).

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

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

Алгоритм LZW. Словник у цьому алгоритмі є таблицю, яка заповнюється ланцюжками елементів у міру роботи алгоритму. У процесі стиснення знаходиться найдовша ланцюжок, вже записана в словник. Кожного разу, коли новий ланцюжок елементів не знайдений у словнику, він додається до словника, при цьому записується код ланцюжка. Теоретично розмір таблиці не накладається обмежень, проте обмеження розмір дозволяє поліпшити ступінь стиснення, т. до. накопичуються непотрібні (не зустрічаються) ланцюжка. Чим більше входження має таблиця, тим більше інформації потрібно виділяти для зберігання кодів.

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

Алгоритми статистичного кодування ставлять у відповідність кожному елементу послідовності код так, щоб його довжина відповідала ймовірності появи елемента. Стиснення відбувається за рахунок заміни елементів вихідної послідовності, що мають однакові довжини (кожен елемент займає однакову кількість біт), на елементи різної довжини, пропорційної негативному логарифму від ймовірності, тобто елементи, що зустрічаються частіше, ніж інші, мають код меншої довжини.

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

Алгоритм Хаффмена є двопрохідним. Перший прохід зображення створює таблицю ваг елементів, а під час другого відбувається кодування. Існують реалізації алгоритму з фіксованою таблицею. Часто буває, що апріорний розподіл ймовірностей елементів алфавіту невідомий, тому що не доступна вся послідовність відразу, при цьому використовуються адаптивні модифікації алгоритму Хаффмена.

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

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

Оцінка втрат у зображеннях. Існує безліч заходів для оцінки втрат у зображеннях після їх відновлення (декодування) зі стислих, проте для всіх з них можна підібрати такі два зображення, що їх відмінність буде досить великою, але на око відмінності будуть майже непомітними. І навпаки - можна підібрати зображення, що сильно різняться на око, але мають невелику міру відмінності.

Стандартним числовою мірою втрат зазвичай є середньоквадратичне відхилення (СКО) значень пікселів відновленого зображення від вихідного. Тим не менш, найважливішим "заходом" оцінки втрат є думка спостерігача. Чим менше відмінностей (а краще їх відсутність) виявляє спостерігач, тим вище якість алгоритму стиснення. Алгоритми стиснення з втратами часто надають користувачеві можливість вибирати обсяг "втрачених" даних, тобто право вибору між якістю та розміром стисненого зображення. Природно, що краще візуальне якість при більшому коефіцієнті стиску, тим алгоритм краще.

Перетворення Фур'є. Загалом зображення можна розглядати як функцію двох змінних, визначену в точках кінцевого растру. Безліч таких функцій на точках фіксованого кінцевого растру утворюють кінцево евклідово простір, і до них може бути застосовано дискретне перетворення Фур'є, тобто спектральне подання зображення. Воно забезпечує:

Некорельованість і незалежність коефіцієнтів спектра, т. е. точність уявлення одного коефіцієнта залежить від будь-якого іншого.

- "Ущільнення" енергії (energy compaction). Перетворення зберігає основну інформацію у малій кількості коефіцієнтів. Ця властивістьнайсильніше проявляється на фотореалістичних зображеннях.

Коефіцієнти спектрального уявлення – це амплітуди просторових частот зображення. У разі зображень з плавними переходами більшість інформації міститься в низькочастотному діапазоні.

Алгоритм стиснення, що використовується в форматі JPEGпобудований на використанні дискретного косинусного перетворення Фур'є Схема стиску в алгоритмі є конвеєром, де це перетворення - лише одна зі стадій, але одна з основних. Алгоритм містить такі основні операції:

1. Переведення в колірний простір YCbCr. Тут Y – компонента яскравості, Cb та Cr – компоненти кольоровості. Людське око більш чутливе до яскравості, ніж до кольору. Тому важливіше зберегти більшу точність під час передачі Y, ніж за передачі Cb і Cr.

2. Дискретне косинус-перетворення (ДКП). Зображення розбивається на блоки 8 × 8. До кожного блоку застосовується дискретне косинус-перетворення (окремо компонент Y, Cb і Сr).

3. Скорочення високочастотних складових у матрицях ДКП. Людське око практично не помічає зміни у високочастотних складових, отже коефіцієнти, що відповідають за високі частоти, можна зберігати з меншою точністю.

4. Зигзаг-упорядкування матриць. Це спеціальний прохід матриці для отримання одномірної послідовності. Спочатку йде елемент T00, потім T01, T10, T1. Причому для типових фотореалістичних зображень спочатку будуть йти ненульові коефіцієнти, що відповідають низькочастотним компонентам, а потім - безліч нулів (високочастотні складові).

5. Стиснення спочатку методом RLE, а потім методом Хаффмена.

Алгоритм відновлення зображення діє у зворотному порядку. Ступінь стиску від 5 до 100 і більше разів. При цьому візуальна якість для більшості фотореалістичних зображень залишається на хорошому рівніпри стисканні до 15 разів. Алгоритм та формат є найпоширенішими для передачі та зберігання повнокольорових зображень.

Вейвлет-перетворення сигналів є узагальненням класичного перетворення Фур'є. Термін "вейвлет" (wavelet) у перекладі з англійської означає "маленька (коротка) хвиля". Вейвлети - це узагальнена назва сімейств математичних функцій певної форми, які локальні в часі та за частотою, і в яких усі функції виходять з однієї базової за допомогою її зсувів та розтягувань по осі часу.

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

література

46. ​​та ін. Швидкі алгоритми у цифровій обробці зображень. - М.: Радіо і зв'язок, 1984. - 224 с.

47. Сойфер обробка зображень. Частина 2. Методи та алгоритми. - Соросівський освітній журнал №3, 1996.

48. , Хрящів шуму із зображень на основі нелінійних алгоритмів з використанням рангової статистики. – Ярославський державний університет, 2007.

49. Андрєєв телевізійні системиспостереження. Частина ІІ. Арифметико - логічні основи та алгоритми. Навчальний посібник. - СПб: СПб, ГУІТМО, 2005. - 88с.

51. Введення у цифрову обробкусигналів (Математичні основи). - М.: МДУ, Лабораторія комп'ютерної графікита мультимедіа, 2002. - http://pv. *****/dsp/dspcourse. pdf, http://dsp-book. *****/dspcourse. djvu, http://geogin. *****/arhiv/dsp/dsp4.pdf.

1i. та ін Алгоритмічні основи растрової графіки. - Інтернет університет інформаційних технологій. - http://www. *****/goto/course/rastrgraph/

2i. Лукін -електронні системи: Конспект лекцій. ІТМО, 2004. - СПб, ІТМО ІФФ, 2004. - http://iff. *****/kons/oes/KL. htm

Про помічені помилки та пропозиції щодо доповнення: *****@***ru.

Copyright©2008ДавидовА.V.