Топологічні характеристики

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

плівка

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

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

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

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

Одна з часто використовуваних топологічних властивостей множин - це число його пов'язаних компонент.

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

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

Одне з можливих рішень такої проблеми складається з вибору 4 - зв'язності для об'єкта і 8- зв'язності для фону. Але подібна асиметрія для об'єкта і фону не зручна. Частіше вводять 6 - зв'язність, тобто сусідніми вважаються

виходять два об'єкти на зв'язаному полі

На гексагональному растрі ця проблема вирішується простіше, тобто елементарні комірки не прямокутники, а шестикутники.

Тут всі шість елементів,що стосуються даного центрального елемента являются сусідами, і невизначеність не виникає.

Наші попередні дії ( шестизв'язність ) можна трактувати як просте перенесення прямокутної решітки в гексагональну.

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

Нехай С - число пов'язаних компонент, а Н - число дір, тоді число Ейлера:

Е = С- Н

Е = 1-2 = -1

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

Наприклад, деякі методи розпізнавання знаків використовують число дір у якості одного з ознак в описі форми знака.

Загалом, завдання, в яких для розпізнавання достатньо одного топологічного опису зустрічаються рідко .

Опукла оболонка і дефіцит опуклості

Опукла оболонка містить кожен відрізок, що з'єднує дві довільні точки. Опукла оболонка Н множини S є найменшою опуклою множиною,що містить S.

Якщо S містить 1 пов'язану компоненту, то Н можна уявити собі як множину, обмежену гумовою стрічкою, натягнутою по периметру S.

Різниця множин Н і S називається дефіцитом опуклості.

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

Такий підхід дозволяє часто розривати складний об'єкт на кілька менш складних частин.

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

Для дискретних об'єктів представляються на прямокутному растрі визначення опуклої оболонки необхідно трохи видозмінити.

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

1. 8-зв'язана С = 4, Н = 4,Е = 0

2. 6- зв'язана

С = 3 + 2 + 3 = 8,

Н = 2, Е = 8-2 = 6

3. 6- зв'язність

С = 2 + 1 + 1 + 1+3 = 7,

Н = 2, Е = 5

4. 4- зв'язність

С = 4 + 1 + 1+7 = 13, К = 2, Е=11

Зобразити опуклість і дефіцит опуклості

Опуклість ( плівка )

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

Зазвичай подібне завдання вирішується методом порівняння з еталоном.

Потрібно виявити трикутник і його місце розташування

трафарет

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

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

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

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

Одним з можливих варіантів міри відповідності є наступні.

Нехай g ( i, j ) - розпізнаваєме дискретне зображення, а t ( i, j ) - еталон, а D ( 20х20 ) - область визначення еталону.

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

M(m,n)=

Всі i, j - такі, що точки ( im, jm ) лежать всередині D.

По суті, це визначення зводиться до зрушення еталона t ( i, j ) у положення ( m, n ) на зображенні та привласнення величиною M ( m, n ) значення рівного числа елементів у яких рівні півтонів зображення і розміщеного на них еталона різні.

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

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

Оскільки фігурує відстань, то необхідно використовувати деяку метрику. Фактично функція M ( m, n ) використовує метрику абсолютних значень. Але можна взяти і інші метрики.

1/2

Евклідова

S(m,n) = max?g(i,j)-t(i -m,j-n)? , де область визначення і, j також

Візьмемо Евклідову метрику. Зводимо в квадрат

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

Фактично даний вираз задає СКО, яке має бути мінімізовано вибором відповідної позиції ( m, n ).

Зазвичай вважається, що є схожість з еталоном в точці ( m, n ), якщо значення E ( m, n ) = L, L - деякий поріг.

З цього виразу видно, що при переміщенні еталона по зображенню шляхом зміни m і n,останній член постійний

Оскільки ця енергія еталона, яка незмінна, тому що значення m і n беруться такими, що область аргументу для t 2 збігається з областю визначення функції.

Результат зміни для 1 - го числа - це енергія зображення в межах вікна еталона. У загальному випадку вона зміниться Зі зміною m іn, але на практиці зміниться досить повільно ( тобто теж можна прибрати).

Тоді величина Е2 ( т, п ) стає малою, коли

зростає, тому визначимо функцію взаємної кореляції

Rgt(m,n)=

Де підсумовування по всіх i, j всередині області, займаної зрушеним еталоном.

Це визначення можна розглянути як міру подібності між еталоном і областю зображення характеризує позицією ( m, n ).

При цьому еталон і зображення схожі, якщо взаємна кореляція велика.

Rgt ( m, n )> = LD

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

Взаємна кореляція може збільшитися навіть за відсутності відповідності зображення еталону, якщо яскравість зображення в околиці точки ( m, n ) велика.

Можливою альтернативою є обчислення нормованої функції взаємної кореляції.

Ngt(m,n)=

Де і та j змінюються в тих же межах, як і раніше.

Можна показати, що

Ngt(m,n)~

випливає з нерівності Коші-кварцу.

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

З іншого боку, за деяких умов припущення щодо мед ства зміни ?g2 справедливо.

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

Взаємна кореляція застосовується досить широко в силу своєї простоти і ефективності реалізації.

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

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

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

Такий підхід розумний до великого класу задач. Характеризується сильною мінливістю зовнішнього вигляду розпізнається об'єкта.

Існують деякі задачі розпізнавання зображень, які можна так поставити, що кожен образ може мати один і той же розмір, і єдиний орієнтир.

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

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