Обробка зображень та мультимедіа

Модуль 1

Лекція 4. Геометричні, арифметико-логічні та статистичні методи

 ЛЕКЦІЯ 4. ГЕОМЕТРИЧНІ, АРИФМЕТИКО-ЛОГІЧНІ ТА СТАТИСТИЧНІ МЕТОДИ

  1. 4.1    Геометричні ознаки об’єктів на зображенні

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

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

Основними ознаками, які найбільш широко застосовуються для опису об’єктівє наступні:

Кількість пікселів контуру, довжина периметра об’єкту, крайні точки об’єкту обчислюються безпосередньо при обході контуру по простим алгоритмам. Довжина периметра об’єкту установлюється в 0, потім, якщо вектор переходу направлений по прямій, то довжина нарощується на 1, а якщо по діагоналі - то на корінь квадратний із 2. Крайні точки – це 4 точки які мають мінімум і максимум координат X і Y.

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

Тобто, якщо проходимо по рядку зліва направо і зустрічаємо не нульову точку – це початок об’єкту з номером, який зафіксовано в даній точці. При продовженні проходу можливі варіанти:

Таким чином для монохромних (чорно-білих) зображень виконуємо підрахунки за наступними правилами:

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

  1. Задають змінні A, Y, N і V. Установлюють A, Y і N рівними 0, а V — першому вектору в ланцюговому коді (Рис.5.3).

  2. Збільшують N на 1.

  3. Якщо V дорівнює 3, 4 чи 5, додають Y до А.

  4. Якщо V дорівнює 1, 2 чи 3, збільшують Y на 1.

  5. Якщо V дорівнює 5, 6 чи 7, зменшують Y на 1.

  6. Якщо V дорівнює 1 чи 5, зменшують А на 0,5.

  7. Якщо V дорівнює 3 чи 7, збільшують А на 0,5.

  8. Якщо V дорівнює 0, 1 чи 7, віднімають Y з А.

  9. Установлюють V рівним наступному вектору в ланцюговому коду і повторюють усю послідовність, починаючи з п. 2. Якщо векторів більше нема, то площа буде дорівнювати 1+A + N/2.

У тому випадку, коли площею дуже дрібних елементів можна зневажити, для прискорення процедури можна опустити пп.6 і 7. Можна також опустити п. 2, і тоді площа буде приблизно дорівнює 1+А, чи просто А.Площа елемента може бути тією величиною, що видається на виході чи використовується для класифікації і фільтрації елементів по розмірах.

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

Показник округлості = Периметр2/Площа.

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

  1. 4.2    Пошук об’єктів зображень за геометричними ознаками

Для подальших досліджень будемо розглядати випадок коли після сегментації маємо бінарне зображення, де на білому тлі представлені чорні об’єкти (або навпаки, це не принципово), що мають замкнені контури і позначені, як об’єкти 1-ого рівня. В межах об’єктів 1-ого рівня можуть бути розташовані білі об’єкти 2-ого рівня, в межах об’єктів 2-ого рівня можуть бути розташовані чорні об’єкти 3-ого рівня і так далі (дивись рис. 4.1).

Рисунок 4.1

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

Рисунок 4.2

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

  1. 4.3    Методи кодування контурів

Існує достатньо велика кількість методів і способів кодування контурів, котрі мають свої переваги і недоліки в залежності від потреб подальшої обробки. Перелічимо лише деякі з них надані в [2] і засновані на тому, що в рамках квадратної сітки (3х3) можливі лише вісім переходів від поточного піксела до сусідніх, тобто можливі вісім елементарних векторів (ЕВ) переходів.

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

  1. 4.4    Пошук і кодування контурів методом Фрімана

Часто для формування образів елементів зображень використовують ланцюговий код Фрімена, чи просто ланцюговий код. Він дозволяє представляти елемент будь-якої довільної форми у виді послідовності коротких векторів П 0, П 1........П 7, кожний з який відповідає напрямку переходу від одного пікселя до того, що примикає (рис. 4.3). Цей код можна використовувати для представлення будь-яких кривих чи ліній, а якщо ланцюжок з векторів замикається, то якихось елементів чи зображення суцільних фігур.

Рисунок 4.3 Ланцюговий код Фрімена.

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

  1. Знаходять відправну точку. Для цього переглядають зображення по рядках, починаючи від верхнього лівого кута для пошуку першого об’єкту, або від останньої знайденої відправної точки враховуючи зону допустимого знаходження для послідуючих об’єктів доти, поки не буде знайдений піксел зі значенням 1. Відзначають цей піксел як «П - поточний».

  2. Перевіряють усі що примикають піксели, починаючи від вектора 0 (рис. 4.3), доти, поки не буде знайдений піксел зі значенням 1. Вектор, спрямований до цього пікселу, і буде першим вектором. Якщо ж такий піксел, що примикає, не знайдений, то вважають, що виявлено одиночний ізольований піксел, і дана область представляється «порожнім» списком.

  3. Відзначають напрямок останнього побудованого вектора як поточний і переміщають «поточний піксел » в область кінця вектора.

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

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

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

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

4.5    Виділення контурів об’єктів і формування бази даних

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

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

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

4.5.1    Алгоритм пошуку відстаней

Пояснимо процедуру формуваня шаблону контура із заданим максимальним відхиленням. Введемо поняття “елементарна зона допуску” - це зона допуску однієї окремої точки контуру. Спочатку розглянемо як формується елементарна зона допуску, а потім в цілому шаблон. На рис. 5.4 представлена квадратна сітка розміром 9 х 9, в комірки якої вписані квадрати відстаней від центральної точки. Мається на увазі, що відстань при переході по горизонталі чи вертикалі на один крок дорівнює одиниці.

Рисунок 4.4

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

Рисунок 4.5

Якщо наприклад задане максимальне відхилення дорівнює 3,5 то елементарна зона допуску буде включати всі точки, для яких квадрат відстаней менший або рівний 12,25 , тобто точки з кодами менше 8 (дивись рис. 4.6).

Рисунок 4.6

4.5.2    Алгоритм обчислення шаблону контуру

Маючи елементарну зону допуску з закодованими відстанями, шаблон контуру формується наступним чином:

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

  2. В точки шаблона з координатами точок контура записується код 0;

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

  4.  

4.6     ПОРІВНЯННЯ СПОТВОРЕНИХ КОНТУРНИХ ЗОБРАЖЕНЬ ОБ’ЄКТІВ ІЗ ВИЗНАЧЕННЯМ    ЇХ ВЗАЄМНОЇ ОРІЄНТАЦІЇ ПО ХАРАКТЕРНИХ ТОЧКАХ АБО ПРЯМИХ

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

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

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

З контурного зображення еталона формується шаблон, тобто з “однопіксельної” лінії контуру формується зона допустимих відхилень контурної кривої на величину похибки, яка задається. На рис. 4.7 представлено: ліворуч - замкнені контури еталона, праворуч - сформований шаблон.

Рисунок 4.7

Отримане контурне зображення аналізованого об’єкта з врахуванням його положення, орієнтації і масштабу відносно еталона перетворюється і накладається на шаблон. Підраховується процент “пікселів” контуру об’єкта які вийшли за рамки шаблона і робиться висновок, наскільки в цілому зрівнялись контур об’єкта з шаблоном еталона і в яких місцях відбулося не зрівняння. На рис. 4.8 представлено: ліворуч - виділений контур об’єкта, праворуч - цей контур (білі точки) зсунутий, повернутий і накладений на шаблон (сіра зона).

 

Рисунок 4.8

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

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

4.7    АЛГОРИТМ ВИДІЛЕННЯ КІСТЯКА КАПІЛЯРУ

Наведемо приклад застосування геометричних ознак. Для знаходження кістяка (середньої лінії) капіляру був використаний алгоритм, розроблений Nicholas Read Howe з деякими модифікаціями. Ідею алгоритму можна описати таким чином. Точка, що належить середній лінії, є центром кола, яке торкається меж фігури в декількох точках. Інтенсивність зображення кістяка у відтінках сірого кольору грунтується на найменшій відстані, яку довелося подолати, здійснюючи обхід по периметру фігури, щоб з'єднати найвіддаленіші дві такі точки. Таким чином, відростки в кістяку, завдяки малим відхиленням по периметру, будуть мати малу інтенсивність, навіть якщо вони і дуже довгі. Якщо коло торкається двох нез'єднаних меж, наприклад, всередині і зовні кола, то кістяк буде нескінченний в цій точці. Для отримання остаточного результату необхідно використати поріг в залежності від очікуваного розміру шумових виступів в контурі фігури.

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

  1. Відеопослідовність розбивається на кадри.

  2. Інтерактивно вибираються капіляри (рис. 4.9), що підлягають вивченню.

  3. Зображення стабілізується одним з вище наведених алгоритмів.

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

Shape1

Рисунок 4.9 - Досліджуваний капіляр


 

Рисунок 4.10 - Капіляр після усереднення

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

  1. Отримане зображення переводиться з відтінків сірого кольору в бінарне чорно-біле зображення. Це перетворення проводиться з адаптивним порогом (рис. 4.11).

Рисунок 4.11 - Капіляр після перетворення в чорно-біле зображення

  1. Виділяється контур капіляра (рис. 4.12).

Рисунок 4.12 - Виділення контуру капіляра

  1. Виділяються 8-зв'язкові компоненти в капілярі (рис. 4.13). Кожна зв'язкова компонента отримує свій унікальний номер. На малюнку нижче кожна зв'язна компонента пофарбована у свій колір.

Рисунок 4.13 - Зв'язкові компоненти капіляра

  1. Виділяється зв'язна компонента з найбільшою площею (рис. 4.14). Подальша робота буде вестися саме з цією компонентою.

Рисунок 4.14 - Зв'язкова компонента з найбільшою площею

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

Рисунок 4.15 - Заповнена компонента

  1. Виділяється кістяк капіляра з допомогою вищевикладеного алгоритму (рис. 4.16).

Рисунок 4.16 - Кістяк і межі компоненти

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

4.8    Ймовірнісні моделі зображень (probabilistic image models)

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

У відповідності з визначенням математичне сподівання (середнє значення, mathematical expectation) стаціонарного процесу в широкому змісті

(1)

Дисперсія (dispersion, variance)

(2)

Функція автокореляції (autocorrelation function) обчислюється наступним чином:

(3)

Де τх, τy задають зсуви зображення по відповідним осям координат.

 

4.9    Статистичні ознаки зображень

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

  кутовий момент;

  контрастність;

  кореляція;

  ентропія.

До статистичних методів можна віднести кореляційний аналіз зображень. На основі кореляційного підходу найбільш успішним є метод матриць взаємозв’язку (co-occurrence matrices – GLCM). Дані матриці характеризують частоту пар різних градацій сірого кольору, що присутні в зображенні, і визначаються шляхом кореляційного аналізу пікселів зображення, при цьому якщо піксель відповідає вибраній градації, то він враховується як одиничне значення, якщо ні, то як нульове. У випадку кольорових зображень даний підхід використовують до аналізу кожного з трьох базових кольорів. Як слідує з методу формування матриць взаємозв’язку, вони найкраще підходять до розв’язання задач класифікації текстур.

Наряду з статистичним аналізом в просторовій області використовують аналогічний аналіз в спектральній області із застосуванням двовимірного дискретного перетворення Фур’є в базисі різних ортогональних функцій – дискретних експоненціальних функцій (ДЕФ), косинусних, Уолша-Адамара, Хаара та інших. Для аналізу текстур використовують метод гістограм розподілу спектральних коефіцієнтів. Загальною характеристикою такого підходу є те, що гістограми спектральних коефіцієнтів, що отримані в результаті інтегральних перетворень, більш стійкі та надійні ніж гістограми розподілу окремих пікселів чи груп пікселів. Даний метод також нечутливий до присутнього в зображенні шуму, але це є одночасно і недоліком в разі використання методу до розв’язання задачі розпізнавання незначних за розміром об’єктів на текстурованому фоні. Також спектральні методи згладжують різкі границі між об’єктами зображення.

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

4.10    Стохастична модель та її застосування

Найпростішою і найбільш часто вживаною є стохастична модель. Фон зображення характеризують гістограмою розподілу значень кольору по величині в деякій базовій області, вільній від об’єктів. Гістограму апроксимують функцією щільності розподілу ймовірності, найбільш часто гаусовою. В цьому випадку параметрами моделі є середнє значення m та дисперсія σ. За максимальне відхилення сигналу моделі приймають 2σ. В якості мінімального порогового значення величини відхилення можна прийняти величину ɛtr=3σ.

В якості прикладу розглянемо алгоритм розпізнавання зображення об’єктів за допомогою стохастичної моделі:

If | Ui,j - m | > ɛtr, then Vi,j = Ui,j else Vi,j = 0                  (4)

де Ui,j , Vi,j, – елементи матриць заданого зображення та зображення об’єктів. На рис. 4.17 представлено результат розпізнавання та відбору об’єктів згідно з алгоритмом (4) за статистичним методом.

Застосування статистичної методики наступне:

1. Фрагмент зображення фону, вільний від сторонніх предметів (тобто обєктів), розміром 80х80 пікселів використано як базовий для того, щоб знайти статистичні параметри фону.

2. За допомогою виразу (4) створено зображення об’єктів.

А

Б

Рисунок 4.17 – Тестове зображення (А) та результат розпізнавання об’єктів за статистичним методом (Б)

 

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

Лекція 3. Попіксельна (локальна) обробка Лекція 5. Поняття та моделі кольору
© 2023 СумДУ
created with Lectur'EDbeta