Факультет комп'ютерних наук та технологій
Кафедра програмного забезпечення систем
Спеціальність Програмне забезпечення систем
Розробка та аналіз алгоритму виділення контуру на півтоновому
зображенні за умови слабоконтрастних меж об'єктів
Науковий керівник: к.т.н., доц. Волченко Олева Володимирівна
Автоматична обробка візуальної інформації є одним з найважливіших напрямків в галузі штучного інтелекту. Інтерес до проблем комп'ютерної обробки визначається розширенням можливостей як самих комп'ютерних систем, так і розробкою нових технологій обробки, аналізу та ідентифікації різних видів зображень. При цьому для створення ефективних технологій розроблювані методи і алгоритми повинні задовольняти ряду вимог по швидкодії і точності. Зазвичай кожен алгоритм, володіючи певними характеристиками, спеціалізується
на своєму типі зображеннь. Тому в системах технічного зору необхідне поєднання декількох методів, які вирішують одну задачу різними способами, забезпечуючи при цьому необхідні показники по швидкодії та достовірності [1].
Однією з найбільш складних проблем обробки візуальної інформації є виділення контуру об'єктів, так як контур — це найбільш інформативні структурні елементи об'єктів. Проте контури, які виділяються на слабоконтрастних розмитих зображеннях відомими методами, мають такі вади, як розриви, відсутність контурних ліній або наявність помилкових, які не відповідають досліджуваному об'єкту.
Більшість одержуваних зображень зазвичай слабоконтрастні, мають нерівномірний фон, а також містять різного роду шуми. Тому для аналізу такої інформації необхідно забезпечити високу візуальну якість і ефективність попередньої обробки досліджуваного зображення, яка може бути отримана за допомогою сучасних методів виділення контурів і меж. Це дозволить поліпшити вирішення великої кількості завдань [2].
На сьогоднішній день існує безліч методів виділення контурів. Ці методи ефективні для обробки зображень з низьким рівнем шуму.
Таким чином, на сьогоднішній день залишається актуальною розробка методів виділення об'єктів на слабоконтрастних зображеннях.
Виділення контуру об'єкта на зображенні є одним з актуальних завдань в цифровій обробці сигналу. Дослідженнями психологів виявлено, що з точки зору розпізнавання і аналізу об'єктів на зображенні найбільш інформативним є не значення яскравості об'єктів, а характеристики їх кордонів — контурів.
При аналізі зображень і розпізнаванні об'єктів, присутніх на ньому, вагому частку приймають на себе методи і алгоритми виділення контурів, оскільки вони значно спрощують роботу з зображенням і/або цифровим рядом. Але більшість існуючих на сьогоднішній день алгоритмів не може надати достатню точність виділення контуру об'єктів, так як завжди присутні розриви і помилкові кордони. Це значною мірою ускладнює подальшу роботу над зображенням. Дана робота націлена на розробку алгоритму, що дозволяє максимально поліпшити виділення меж зображення шляхом комбінації і модифікації існуючих методів обробки зображень.
Метою роботи є розробка оптимальної комбінації алгоритмів обробки для кращого виділення контурів.
Головним завданням є виділення ліній, що проходять на кордонах однорідних областей.
Предметом дослідження є розробка алгоритму виділення контуру слабоконтрастних об'єктів на зображенні на підставі існуючих алгоритмів і аналізу результатів їх роботи.
Об'єктом дослідження є існуючі методи обробки та виділення контурів на зображенні.
Науковою новизною данної роботи є розробка алгоритму виділення контурів на слабоконтрастних напівтонових зображеннях. Існуючі на сьогоднішній день алгоритми виділення контурів погано справляються з низькою контрастністю об'ктов і фону, а також украй чутливі до шуму на зображенні. Розроблюваний алгоритм буде спрямований на максимальне виділення всіх контурів об'єктів і на придушення виявлених помилкових контурів, які часто виникають від присутності імпульсного шуму.
Психофізичні експерименти показали, що фотографічне або телевізійне зображення з підкресленими границями виявляється суб'єктивно більш приємним, ніж фотометрично досконала репродукція. Підвищення різкості зображення може бути досягнуто шляхом чисельного диференціювання. Величина відгуку оператора похідної в точці зображення пропорційна ступеню розриву зображення в даній точці. Таким чином, диференціювання зображення дозволяє посилити перепади яскравості і інші розриви (шуми, перешкоди) і не підкреслювати області з повільними змінами яскравості [1].
Однією з найбільш складних задач, що використовують алгоритм виділення контурів, є завдання виділення ліній на долоні. Складність даної задачі обумовлена низькою контрастністю ліній по відношенню до їх оточення і велика кількість перешкод (шуму), розриви, помилкові лінії або повна їх відсутність. Для даної задачі є актуальним посилення перепадів яскравості.
Для обчислення двовимірної другої похідної і накладення результату на зображення (високочастотна фільтрація) використовуються три маски, представлені в формулах 5.1–5.3:
| (5.1) | ||||||||||
| (5.2) | ||||||||||
| (5.3) |
Одним із завдань фільтрації зображення з підйомом високих частот є випадок, коли вихідне зображення темніше, ніж потрібно. У цьому випадку можна варіювати коефіцієнт підсилення високих частот U > 1 для збільшення загальної яскравості зображення. Матриці наведені в формулах 5.4–5.6.
| (5.4) | ||||||||||
| (5.5) | ||||||||||
| (5.6) |
Аналіз результатів обробки показує, що імпульсні перешкоди не можуть ефективно придушуватися згладжуючими фільтраціями, але повністю видаляються відповідним медіанним фільтром. Високочастотний фільтрація не тільки покращує діяльність об'єктів на зображенні, а й підкреслює високочастотні шуми [1, 2, 3].
Виділення меж грунтується на алгоритмах, які визначають різку зміну яскравості на зображенні. Результатом виконання алгоритму виділення кордонів має бути деяка кількість пов'язаних кривих, які відображають межі об'єктів. У більшості випадків кордони на зображеннях виражені не настільки контрастно, тому існуючі на даний час алгоритми і оператори не дають належного результату. Часто результат обробки варіюється від розривів контурів і ліній (фрагментованість) до повної відсутності кордону.
Загалом, алгоритми виділення контурів зображень грунтуються на одному з двох базових властивостей сигналу яскравості: розриви і однорідність.
У першому випадку підхід полягає в розбитті зображення на підставі різких розривів яскравості, які є важливими найпростішими ознаками, оскільки вони часто визначають обриси зображених об'єктів. Локальні розриви значень яскравості називаються яркістними перепадами, або яркістними контурами. Друга категорія методів використовує розбиття зображення на області, однорідні з точки зору обраних критеріїв [1, 5].
На рисунках 6.1 та 6.2 показані ділянки зображення з швидкою зміною яскравості від низького рівня до високого в одновимірному і двовимірному випадках. У одновимірному випадку перепад характеризується висотою, кутом нахилу і координатою цента схилу. Перепад існує, якщо його кут нахилу і висота більше деякого заданого порогу. Для двовимірного випадку важлива також орієнтація перепаду по відношенню до осі x. Ідеальний детектор перепаду при обробці областей зображення, представлених на рисунках 6.1 та 6.2, повинен вказувати на наявність перепаду в єдиній точці, розташованій в центрі схилу.
Рисунок 6.1 — Одновимірний випадок
Рисунок 6.2 — Двовимірний випадок
Загальний підхід у виявленню перепадів на зображенні можна сформулювати наступним чином. Початкове зображення представляється цифровий матрицею F з елементами fi, j і піддається лінійній або нелінійній обробці для того, щоб посилити перепади яскравості. У результаті утворюється масив чисел G з елементами gi, j, що описує зображення з підкресленими змінами яскравостей. Потім виконується операція порівняння з порогом і визначається положення елементів зображення з яскраво вираженими перепадами. Якщо gi, j < Ti, jL, то має місце низхідний перепад, а при gi, j ≥Ti, jU — висхідний перепад. Величини Ti, jL и Ti, jU являють собою нижнє і верхнє порогові значення. Ці значення можна зробити змінними в площині зображення для компенсації впливу сильних змін яскравостей на результати виявлення перепадів.
Вибір порога є одним з ключових питань виділення перепадів. При занадто високому рівні порога не будуть виявлені структурні елементи з низьким контрастом. Навпаки, занадто низький рівень порога є причиною того, що шум буде помилково прийнятий за перепад. Для позначення положення перепадів на зображенні часто формують контурний препарат — масив елементів. Таким чином, перепади яскравостей на зображеннях є характеристиками контурів областей об'єктів. Завдання виділення контурів полягає в побудові бінарного зображення, що містить лише контур.
До виконання операції порогового виявлення можна підкреслити
перепади за допомогою різних способів. Один з найбільш простих способів полягає в обчисленні дискретних різниць, що аналогічно безперервному просторовому диференціюванню. Підкреслення вертикальних перепадів здійснюється горизонтальним (порядковим) дискретним диференціюванням (обчисленням дискретних похідних) [1, 5, 6]. В результаті формується деяке зображення — масив елементів, представлений у формулі 6.7.
gi, j = fi, j - fi, j+1 | (6.7) |
Аналогічно здійснюється підкреслення горизонтальних перепадів. У результаті виходить масив елементів, представлений у формулі 6.8.
gi, j = fi, j - fi+1, j | (6.8) |
Диагональное підкреслення можна отримати шляхом обчислення різниць рівнів діагональних пар елементів зображення.
Горизонтальне підкреслення також можна виконати обчислюючи різниці яскравостей елементів вздовж рядка зображення за формулами 6.9 та 6.10.
gi, j = [fi, j - fi, j-1] - [fi, j+1 - fi+1, j] | (6.9) |
або
gi, j = 2 * fi, j - fi, j-1 - fi, j+1 | (6.10) |
Такі висловлювання можна записати для зміни яскравості по вертикалі і діагоналі.
Для виявлення ліній на зображеннях можна використовувати набір масок, наведений у (5.5–5.8). Тут (6.10) — горизонтальна, (6.11) — +450, (6.12) — вертикальна і (6.13) — -450. Назва масок відповідає їх найбільш сильному відгуку при ковзанні по зображенню.
| (6.10) | ||||||||||
| (6.11) | ||||||||||
| (6.12) | ||||||||||
| (6.13) |
Для виділення всіх ліній заданого напрямку необхідно застосувати маску для зображення в цілому порівнюючи абсолютне значення результату відгуку маски з заданим порогом. Таким чином рішення про наявність елемента лінії на зображенні приймається на основі виразу, представленого у формулі 6.14:
|R|≥T | (6.14) |
де R — результат відгуку маски, T — заданий поріг.
Решта точок на зображенні при цьому відповідають найбільшим значенням відгуку, які в разі наявності на зображенні ліній товщиною в один піксель найбільш близькі до напрямку, що визначається маскою.
Підвищення контрасту перепадів без обліку їхньої орієнтації можна отримати шляхом згортки масиву зображення з оператором Лапласа, представленим у вигляді маски 6.15.
| (6.15) |
Оператори Лапласа реагують на перепади яскравості у вигляді ступеневого перепаду і на дахоподібний
перепад. Вони також виділяють ізольовані точки, тонкі лінії, їхні кінці і гострі кути об'єктів. Лінія підкреслюється в два рази яскравіше, ніж східчастий перепад, кінець лінії — в три рази, а точки — у чотири рази яскравіші. Оператор Лапласа інваріантний до орієнтації перепадів: наприклад, відгук оператора на похилий перепад у діагональному напрямку майже вдвічі більше, ніж у горизонтальному і вертикальному [8].
В нелінійних системах виявлення перепадів для контрастування перед пороговим обмеженням використовуються нелінійні комбінації значень яскравості елементів зображення. У більшості методів обмежуються обробкою вікном розміром 2×2 або 3×3. Серед існуючих нелінійних методів можна виділити алгоритми Робертса, Превітт, Собела, Кірша і Уолліса.
Ряд нелінійних операторів виділення контурів використовує обчислення модуля градієнта яскравості, представлене у формулі 6.16.
∇ = gi, j = √(X2 + Y2) | (6.16) |
где X і Y — приватні похідні, що характеризують швидкість зміни яскравості за двома напрямками.
Робертс для обчислення перепадів запропонував наступну операцію знаходження величин X і Y, представлену у формулі 6.17 и 6.18:
X = fi, j − fi+1, j+1 | (6.17) |
Y = fi, j+1 − fi+1, j | (6.18) |
При побудові оператора Робертса використовується той факт, що для визначення перепаду яскравості можна використовувати похідні (різниці) в будь-яких двох взаємно перпендикулярних напрямках. Відзначаючи той з чотирьох елементів зображення, розташованих близько оголеною точки, який має найбільше значення яскравості, можна отримати інформацію про приблизну орієнтації перепаду.
Маски для отримання складових градієнта X і Y за допомогою оператора Робертса наведені в 6.19 та 6.20.
| (6.19) | |||||
| (6.20) | |||||
Рисунок 6.3 — Робота алгоритму Робертса з попередньою обробкою (анімація: 4 кадри, 20 циклів повторення, 16,3 кілобайт) |
Реалізація масок розміром 2×2 незручна, тому що у них немає чітко вираженого центрального елемента. Метод, при якому використовується маски розміром 3×3 запропонував Превітт [8, 10]. Алгоритм використовує модуль вектора градієнта і для знаходження величин X і Y використовуються вирази, наведені в 6.21 и 6.22.
X = (fi-1, j-1 + fi-1, j + fi-1, j+1) - (fi+1, j-1 + fi+1, j + fi+1, j+1) | (6.21) |
Y = (fi-1, j+1 + fi, j+1 + fi+1, j+1) - (fi-1, j-1 + fi, j-1 + fi+1, j-1) | (6.22) |
Маски для отримання складових градієнта X і Y за допомогою оператора Превітта наведені в 6.23 и 6.24.
| (6.23) | ||||||||||
| (6.24) |
Собел модифікував даний алгоритм і запропонував використовувати ваговий коефіцієнт 2 для середніх елементів, що дозволяє зменшити ефект згладжування за рахунок надання більшої ваги середнім точкам. Вирази для знаходження X і Y в операторі Собела представлені в 6.25 и 6.26.
X = (fi-1, j-1 + 2 * fi-1, j + fi-1, j+1) - (fi+1, j-1 + 2 * fi+1, j + fi+1, j+1) | (6.25) |
Y = (fi-1, j+1 + 2 * fi, j+1 + fi+1, j+1) - (fi-1, j-1 + 2 * fi, j-1 + fi+1, j-1) | (6.26) |
Маски для отримання складових градієнта X і Y за допомогою оператора Собела наведені в 6.27 и 6.28. Для обчислення величини градієнта ці складові, а відповідно і маски, необхідно використовувати спільно.
| (6.27) | ||||||||||
| (6.28) |
Для оператора Робертса наближені вирази не є однаково чутливими до кордонів з будь-якою орієнтацією. Для строго вертикальних або горизонтальних ліній всі вирази дають однакові результати, але для ліній з нахилом 450 наближені значення можуть відрізнятися від точного в √2 раз. Для операторів Превітт і Собела питання ізотропності не виникає, так як самі маски інваріантні лише для поворотів на кути в 900.
Слід зазначити, що оператори Превітт і Собел можна змінити так, щоб вони давали максимальний відгук для контурів, спрямований діагонально [1].
Уоллес запропонував нелінійний метод виявлення перепадів, заснованої на гомоморфной обробці зображення. Відповідно до цього методу, точка знаходиться на перепаді, якщо величина логарифма від яскравості в цій точці перевершує середнє значення логарифмів яскравостей чотирьох найближчих сусідніх елементів на деяке фіксоване значення. Елемент обробленого зображення визначається формулою 6.29, що еквівалентно 6.30:
gi, j = log(fi, j − ¼ * log(fi-1, j) − ¼ * log(fi, j+1) − ¼ * log(fi+1, j) − ¼ * log(fi, j-1) | (6.29) |
gi, j = ¼ * log{ fi, j4 / (fi-1, j * fi, j+1 * fi+1, j * fi, j-1) | (6.30) |
Рисунок 6.4 — Робота алгоритму Уоллеса з попередньою обробкою (анімація: 4 кадри, 20 циклів повторення, 16,3 кілобайт) |
Порівняння gi, j з верхнім і нижнім граничним значеннями еквівалентно порівнянню дробу в дужках виразу з видозміненим порогом. Тому не потрібно точно обчислювати значення логарифмів. Основна перевага логарифмічного детектора перепадів крім простоти обчислень полягає в тому, що він не чутливий до мультиплікативний змін рівня яскравості.
На сьогоднішній день запропонована велика кількість алгоритмів виділення контурів [4–18]. Одним з нових і найбільш ефективних з них є алгоритм виділення контурів на малоконтрастних і розмитих зображеннях на основі фрактальної фільтрації. Фрактали більш наочно виділяють контури, ніж інші оператори, але вони орієнтовані на обробку малоконтрастних зображень в цілому, ніж виділення таких ліній і меж [19].
Алгоритм виділення контурів Лаплассіан Гауссіана був запропонований в 1982 році. Даний алгоритм є другою похідною, визначеної як:
∇2f = d2*f / d*x2 + d2*f / d*y2 | (6.29) |
Рисунок 6.5 — Робота алгоритму Лаплассіан Гауссіана з попередньою обробкоюй (анімація: 5 кадрів, 20 циклів повторення, 18,3 кілобайт) |
Він здійснюється в два кроки. На першому кроці він згладжує зображення, а потім обчислює функцію Лапласса, що призводить до утворення подвійних контурів. Визначення контурів зводиться до знаходження нулів на перетині подвійних кордонів. Комп'ютерна реалізація функції Лапласса зазвичай здійснюється через наступну маску:
| (6.30) | ||||||||||
| (6.31) |
Лапласcіан зазвичай використовує знаходження пікселя на темній або світлій стороні контуру.
Детектор меж Канні є одним з найпопулярніших алгоритмів виявлення контурів. Вперше він був запропонований Джоном Канні в магістерській дисертації в 1983 році, і до цих пір він кращий ніж більшість алгоритмів, розроблених пізніше. Важливим кроком у даному алгоритмі є усунення шуму на злбраженні, який значною мірою може вплинути на результат, при цьому необхідно максимально зберегти контури [20]. Для цього необхідний ретельний підбір порогового значення при обробці цим методом.
Алгоритм:
У відмінності від операторів Робертса і Собеля, алгоритм Канні не надто сприйнятливий до шуму на зображенні.
Алгоритм штучної бджолиної колонії є досить молодим алгоритмом для знаходження глобальних екстремумів складних багатовимірних функцій. Ідея алгоритму взята, як видно з назви, у бджіл, а саме з їхньої поведінки при пошуку місць, де можна роздобути якомога більше нектару.
Колонія бджіл може долати великі відстані в різних напрямках одночасно в пошуках джерел живлення. Спочатку з вулика у випадковому напрямку вилітає якась кількість бджіл-розвідників, які намагаються відшукати ділянки, де є нектар. По поверненню в вулик розвідники повідомляють іншим бджолам де і скільки вони знайшли нектару. Після чого на знайдені ділянки відправляються інші бджоли, причому чим більше на даній ділянці передбачається знайти нектару, тим більше бджіл летить в цьому напрямку [21].
В рамках цього завдання найбільшою кількістю нектару будуть володіти ті точки обробленого зображення, в яких буде саме ймовірне знаходження контуру, що буде здаватися його фітнес-функцією. Тобто бджоли-працівники будуть надсилатися в ті ділянки, в яких на думку бджіл-розвідників є розірваний контур. Бджоли-працівники повинні провести аналіз точок зображення в області знаходження нектару і або вибрати точку для відновлення контурної лінії, або ж повідомити, що в даному місці нектар відсутній. Спочатку бджоли будуть спрямовані випадковим чином в точки ймовірного знаходження контурних ліній.
Модифікацією даного алгоритму може бути додавання бджолам можливості створювати мертву зону
. В даному випадку це точки зображення, які з максимальною вірогідністю не належать до одного з можливих контурів. У такому випадку бджола закопує
дану ділянку, тим самим видаляючи цю ділянку з зображення.
Ідея алгоритму заснована на здатності мурах знаходити найкоротший шлях між джерелом їжі та мурашником без використання візуальної інформації [22]. Здатність ця обумовлена виділенням феромону під час їх руху і використанням цього феромону в якості маркера.
Алгоритм, запропонований в роботі [22],реалізує процедуру дискретної оптимізації. Перехід від безперервної оптимізації до дискретної здійснюється за допомогою побудови повного орієнтованого графа пошуку рішення, кількість вершин в якому визначається точністю знаходження значень параметрів. З кожної вершини виходять дуги з рівномірно розподіленими значеннями нормованих параметрів. У вершини графа рівномірно розподіляються мурашки. Мета мурашки — відвідати той список вершин, який найімовірніше є контуром або кордоном. Позначки дуг, за якими пройшов мураха, будуть знайденим ним рішенням. Загальним же рішенням буде максимальний рівень феромону, залишений безліччю мурах. Кількість феромону, що наноситься на дуги, пропорційно якості рішення: чим найімовірніше наявність контуру в районі даної дуги, тим більше феромона наноситься на дугу.
На кожній ітерації відбувається збільшення кількості феромону на кожній дузі і його випаровування.
Модифікацією даного алгоритму для поточного завдання може виступати поетапне збільшення точності обчислення маршруту мурахи. Спочатку алгоритм працює c графом, в якому мінімальна кількість вершин, далі на підставі отриманих результатів алгоритм запускається на графі більшого розміру і так до знаходження оптимального результату.
В результаті виконання даної роботи були розглянуті та проаналізовані деякі методи і алгоритми поліпшення якості зображення і виділення контурів об'єктів на зображенні, а саме фільтрація зображень і низькочастотна фільтрація, підкреслення меж різними методами, такими як Робертс, Превітт, Собел і Уоллес, видозміна гістограм для збільшення контрастності зображення, лінійні і нелінійні методи виявлення ліній і виділення контурів. Було виявлено, що класичні алгоритми досить добре справляються з простими завданнями, але вони не придатні для роботи з слабоконтрастними зображеннями. Результат обробки таких зображень виходить зашумленним і перевантаженим надлишковими контурами. Поліпшити виділення меж можна за допомогою попередньої обробки зображення певним набором алгоритмів і операторів, а також алгоритмів, призначених для відновлення загублених фрагментів контурів.
В даній роботі запропоновано два варіанти поліпшення результатів виділення контуру, заснованих на алгоритмах бджолиних і мурашиних колоній. Дані варіанти можуть дати непогані результати при обробці зображень, але завдання ускладнюється наявністю на реальних зображеннях шумів, які можуть призвести до виникнення помилкових меж і контурів.
При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: грудень 2015 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.
Мир, 1979. — С. 28–47.
Мир, 1989. — С. 50–61.
Вильямс, 2004. — С. 728–733.
Performance Characterization in Computer Vision: The Role of Statistics in Testing and Design, Chapter in: Imaging and Vision Systems: Theory, Assessment and Applications, Jacques Blanc-Talon and Dan Popescu (Eds.), NOVA Science Books.