Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

МОДЕЛЮВАННЯ ЗОРОВОГО СПРИЙНЯТТЯ

В даному розділі передбачається, що об'єкт являє собою кінцеве безліч точок на площині. Кожен з класів i = 1,2, ..., га визначається як безліч всіх об'єктів, отриманих аффіннимі перетвореннями до деякого еталонного об'єкту S t , причому еталонні об'єкти різних класів афінно один до одного не зводяться. Безліч М всіх об'єктів визначається як об'єднання класів До у ..., К т , тобто в даному випадку відомо точний опис як безлічі М, так і класів До і ..., К т . Треба для довільно взятого об'єкта з М встановити, до якого класу він належить.

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

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

Мал. 1.1 :

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

Питання: як здійснюється розпізнавання таких ситуацій?

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

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

Нехай А - безліч з п різних точок площині, тобто | Л | = П. Це безліч надалі будемо називати зображенням.

Взаємно однозначну функцію Ма: А -> {1,2, ..., п} будемо називати функцією нумерації зображення А. Оскільки Ма взаємно однозначна функція, то визначена функція MJ 1 , яка номеру з {1,2, ..., п} зіставляє точку з А.

Якщо а точка площині, то через Х (а ), У (а) позначимо відповідно абсциссу і ординату точки а.

вектор

До Мл = (X (Mx4l)), Y (M ^ (l)), ..., X (M ^ ( n )), Y (Mx4n))) будемо називати вектором координат зображення А при нумерації Ма-

Нехай Т : R 2n - [1] R 1 - деяка i-мірна вектор функція, звана кодує. Пару ( Ма, Та)> де Та = Т (Км А )> будемо називати кодом зображення А при нумерації Ма для кодує функції Т. Число t , яка дорівнює довжині вектора Та й розмірності кодує функції Т, назвемо складністю коду (М А , Т А ).

Два зображення А і В назвемо еквівалентними щодо кодує функції Т, якщо А = В і існують такі функції нумерації Ма і Mb, що Т (Км Л ) = Т (Км в ) •

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

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

зсуву, повороту і перетворень симетрії і зміни в розмірах (зі збереженням подібності);

• Г4 - безліч афінних перетворень площини.

Скажімо, що два зображення еквівалентні щодо безлічі перетворень Г, якщо одне може бути отримано з іншого за допомогою перетворень з Г.

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

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

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

Нехай дано зображення А. Перенумеруем його точки деяким чином так, щоб номери були попарно різні, тобто задамо функцію нумерації Мд. Кодом До 1 зображення А (позначення: К) назвемо пару множин <МД, 7д>. Тут Та безліч координат (х, у) п точок із зазначенням їх номера, тобто, наприклад, (5,3) п означає, що у точки з номером п координатами є пара (5,3). Те мережу для коду До як кодує функції виступає функція Т : R 2n -> R 2n така, що Тд = Т (К Мол ) = К Ма .

Перенумерувати по іншому безліч точок зображення Л, отримаємо іншу пару <МД, Тд>. Будемо, однак, розглядати кодування з точністю до перенумерации і називати зображення, що відрізняються тільки нумерацією точок, еквівалентними (в сенсі випадку 1). Таким чином, якщо є зображення А з кодом <МД, Тд> і В з кодом < Мв, Тв >, то назвемо А і В еквівалентними (в сенсі випадку 1), якщо існує така нумерація точок зображення Л, при якій його код є <МД, Тд>, і така нумерація для В, при якій його код є < Мв / Гв >> і при цьому Тд = ТВ-

Легко бачити, що код До є правильним для безлічі перетворень Г.

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

При зсуві і повороті змінюється положення зображення на сітківці, іншими словами, положення зображення по відношенню до осей системи координат. Взаиморасположение же точок зображення не змінюється, що означає збереження відстаней між ними. Саме збереження відстаней між точками зображення при зсуві і повороті покладемо в основу нового коду К. В коді <МД, Тд>, як і раніше, Л / д є функція нумерації безлічі А. Безліч Тд складають все числа r (g, m) ( я і тп - номери точок з {1,2, ..., | Л |}), що є відстанями між точками зображення, із зазначенням того, відстанню між якими точками є дане число. Тобто, якщо | Л | = П, то кодує функція Т така, що Т : R 2n -> IR f , де t = n (n - l) / 2 - число різних пар (<7, га), <7 <m, і якщо нумерувати компоненти вектор-функції т парами то (q, т) -я компонента дорівнює

Аналогічно тому, як це зроблено вище, визначимо однакові з точністю до перенумерации точок коди. Зображення з такими кодами будемо називати еквівалентними (в сенсі випадку 2). Можна показати, що два зображення еквівалентні тоді і тільки тоді, коли одне може бути отримано з іншого комбінацією зсуву, повороту і перетворення симетрії, тобто код До - правильний для безлічі перетворень Г2. Це можна розглядати як окремий випадок затвердження, доведеного в [24].

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

Грунтуючись на коді До , неважко здійснити розпізнавання зсунутих, повернутих і симетрично перетворених зображень. Нехай зображення А і В задані координатами своїх точок, тобто задані кодами До і Кд. Ми припускаємо, що В - це зрушене, повернене і симетрично перетворене зображення А і маємо намір перевірити це припущення. Визначимо коди До і Кд - це будуть, відповідно, < М А , Т А > і < Мв, Тв > • Коди і Кд очевидним чином будуються за кодами До і Кд. Якщо зображення А і В еквівалентні, то коди До і Кд повинні бути однакові з точністю до перенумерации точок. Залишається тільки перевірити це для кодів До і Кд . Ця процедура може бути визначена по-різному і ґрунтується на очевидних властивості кодів еквівалентних зображень. Так, потужності множин Т А і Тв рівні, якщо зображення А і В еквівалентні. Виділимо, далі, в Т А підмножини, що складаються з рівних за величиною елементів і розташуємо ці підмножини в порядку зростання цієї величини, тобто Т А = {t *, Очевидно, що tfntf = 0 для

i, j = 1 , тп иг / j = Т А , JX, * = Ta- Тут | < д |

і ТА - потужності відповідних множин. Таке ж подання до вигляді підмножин і з такими ж властивостями має мати місце і для зображення В, тобто Тв = {tf, ..., tf ^}. Ясно, що при цьому |? ^ | = | 7 ^ | для всіх 2 = 1, ..., т.

Очевидним чином виникає "прив'язка" множин tf і tf один до одного дає можливість визначити відповідність між трійкою точок в А і трійкою точок в В - відповідність між іншими точками визначається цим однозначно.

Відзначимо, що для зображення Л, що складається з п точок, складність До дорівнює 2п, а складність До дорівнює п (п - 1) / 2.

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

Випадок 3. Нехай зображення перед оком наближається або віддаляється зі збереженням паралельними площині зображення і площини сітківки (або, якщо вони не паралельні, зі збереженням незмінним кута між ними). Це ж можна трактувати і так, що зображення перед оком нерухомо, а наближається сам очей. В обох випадках зображення на сітківці збільшується або зменшується в розмірах зі збереженням подібності. Можна відзначити, що такі ж зміни на

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

Коди До До зображення А коли він підійшов або видаленні від ока очевидно змінюються, оскільки змінюються і координати точок його проекції на сітківку, і відстані між точками цієї проекції. Співвідносні ж розміри частин зображення при збільшенні або зменшенні зі збереженням подібності не змінюються. Це і покладемо в основу коду К. Так само, як і в попередніх випадках, перенумеруем безліч точок зображення А і позначимо функцію нумерації через Мл • Далі задамо безліч Та чисельних значень відносин виду r (ra, l) / r (p , g) , де r (m, I) і r (p, q) - відстані між точками з номерами відповідно ти /, ри ^, тобто

Тут m, l, p, q - номери з {1,2, ..., | Л |}, т </, р <q. Для кожного числа з Та вважаємо відомою відповідну йому четвірку номерів m, n, р, q. Код є пара < Ма, Та> • Аналогічно тому, як це розглядалося для попередніх двох випадків, можна визначити однакові з точністю до перенумерации точок коди. Зображення з такими кодами будемо називати еквівалентними (в сенсі випадку 3). Можна показати, що два зображення еквівалентні в тому і тільки в тому випадку, якщо на площині одне може бути отримано з іншого зрушенням, поворотом, зміною в розмірах (зі збереженням подібності), перетворенням симетрії або їх комбінацією (тобто подібними перетвореннями), т . Е. код - правильний для безлічі перетворень Г3. Відповідне твердження доведено в [33].

Розглянемо тепер, як співвідносяться коди і К і чим пояснюється відмінність їх властивостей. За кодом До можна, очевидно, побудувати код К. Зворотне невірно. Код До визначається таким чином, щоб в описі зображення не брала б і зовнішня "по відношенню до зображення система координат. Однак щось від цієї зовнішньої системи в визначенні коду П залишилося, а саме - одиниця вимірювання відстаней між точками зображення. Вона, ця одиниця, передбачається для коду до апріорі заданої. Коли ж ми беремо відношення r (m y n) / r (p, q) (в коді к), ця одиниця виміру усувається. Дійсно, величина відносини r (m, n) / r (p , q) буде однією і тією ж незалежно від того, в яких одиницях вимірюються відстані (тп, п) і r (p, q). Звідси і виникає можливість за допомогою К описувати зображення безвідносно до його розмірів.

Можна і дещо по-іншому інтерпретувати код К. Візьмемо в якості одиниці вимірювання відстань між будь-якої парою точок на самому зображенні. Нехай це будуть точки з номерами р і q. Тепер для того, щоб для довільних точок тип зображення отримати відстань між ними, виражене в одиницях, які є відстанню між точками р і п) і r (p y q). Потім розділити r (m, n) на r (p, q) } тобто отримати r (m y n) / r (p, q). Це і буде шуканим числом. Якщо тепер по черзі вважати одиницею виміру відстань між кожною парою точок в зображенні, то ми і прийдемо до безлічі Та для коду К.

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

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

Безліч Та має (п (п - 1) / 2) (п (п - 1) / 2 - 1) елементів.

Разом з тим код До , очевидно, надмірний.

Випадок 4 (основний). Проведемо в площині зображення перед оком пряму (перетинає зображення). Повернемо зображення навколо прямої на деякий кут. Зображення на сітківці стиснеться в напрямку, перпендикулярному прямий (приклад на рис. 1.2). Цей випадок можна трактувати і так, що зображення перед оком нерухомо, а повертається на деякий кут площину сітківки. Нарешті, зображення перед оком може дійсно стискатися по деякому напрямку. У всіх цих випадках перетворення зображення на сітківці зведеться до стиснення.

Мал. 1.2 :

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

Ще раз підкреслимо, що тільки до стиснення або до розтягування перетворення зображення на сітківці зводиться в тому випадку, коли несуттєва різниця у відстанях до ока від різних частин зображення, що виникає після повороту навколо осі. В цілому ця особливість виникає як частина ширшої проблеми, зазначеної в дослідженнях по машинному зору (див., Наприклад, [58, 60]). Проекції тіла на сітківку розглядаються зазвичай як паралельні проекції (з додаванням можливості перетворення подібності). Оком ж, можна вважати з більшими підставами, здійснюється центральна проекція. Якщо, проте, відстань до об'єкта велике в порівнянні з розмірами самого об'єкта, то відмінності між центральною і паралельної проекціями невеликі і ними можна знехтувати. Ми вважаємо, що знаходимося в межі застосування саме цього випадку.

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

Назвемо двовимірним зображенням кінцеве безліч точок на площині. Перенумеруем деяким чином точки зображення А, тобто задамо функцію нумерації Мд. Нехай S mnu і Skps - площі трикутників з вершинами в трійках точок з номерами т, п, і та k, p, s і нехай р ТП і, до Р з = S mnu / Sk ps . Вважаємо, що порядок номерів в трійках не важливий, самі трійки різні і при 5 * рв = 0 значення р т пі, до Р з не визначене. Безліч індексованих чисел pmnu, k P s для всіх таких пар трійок позначимо через Т д. Код До зображення А - пара < МД, Т А >. Зображення, всі крапки яких розташовані на одній прямій, не розглядаємо, оскільки код для них не визначено. Як і раніше, зображення А і В назвемо еквівалентними в сенсі випадку 4 (далі - просто еквівалентними), якщо існують такі нумерації МД і Мв, що коди Тд і Тв рівні. Ясно, що еквівалентність зображень змістовно означає однаковість їх кодів з точністю до перенумерации точок.

  • [1] Гз - безліч перетворень подібності, тобто перетворень, які утворюються за допомогою будь-яких комбінацій
 
<<   ЗМІСТ   >>