Розпізнавання тривимірних об'єктів на складному тлі за
частини контуру
Протасов Владислав Іванович
Представлено
опис простого алгоритму розпізнавання тривимірних предметів; описаний алгоритм
оконтурювання проекцій предметів та їх частин на образотворчу площину;
запропоновані методи розпізнавання тривимірних предметів по частині контуру у випадках
простого і складного фону, представлені результати демонстраційних розрахунків.
В
ряді технічних програм вельми актуальною є задача розпізнавання
техногенних тривимірних об'єктів, що знаходяться під різними ракурсами щодо
пристрої розпізнавання. Так, наприклад, для орієнтування роботизированного
мобільного комплексу (РМК) на пересіченій, заздалегідь невідомій місцевості,
актуальною є задача аналізу ситуації за допомогою бортового обчислювача,
виходячи з інформації, що поставляється системою технічного зору в реальному
часу. Необхідно оперативно визначати швидкості об'єктів і відстані до
них, розпізнавати об'єкти, інформація про яких є в базі даних бортового
обчислювача, визначати їх положення в просторі щодо світової та
бортовий систем координат.
В
основу рішення поставленої задачі був обраний метод аналізу геометричних
характеристик контурних ліній, що оздоблюють розпізнається предмет на
образотворчої площини, на яку вони проектуються. Був запропонований і випробуваний
ефективний метод розпізнавання тривимірних об'єктів, орієнтованих довільним
чином.
З
використанням розробленої на основі цього методу обчислювальної програми
DETERMINATOR, здійснюється порівняння що пред'являється до розпізнавання контуру з
еталонними контурами деякого числа заздалегідь заданих предметів у різних
ракурсах, стисла інформація про яких розміщена в базі даних. При застосуванні в
системах технічного зору метод окрім визначення геометричного положення
розпізнаного предмета в просторі, дозволяє визначати також і відстань
до нього.
На
першому етапі випробування ефективності запропонованого методу вважається, що
розпізнається предмет розташовується ізольовано від інших на тлі однотонному
і на образотворчу площину проектується тільки його зовнішній контур, причому
на стадії створення бази даних він проектується в повну величину, без
будь-яких спотворень.
В
основу методу покладено просте уявлення контуру у вигляді набору деякого
невеликої кількості цифр, інваріантного щодо трансляцій, ротації і
зміни масштабу. На першому етапі проводиться вибір характерних точок
контуру.
Першої
характерною точкою як і в [1], є найбільш віддалена точка від центру
тяжкості контуру, другий характерною точкою є точка контуру, найбільш
далеко відстоїть від першої. Третя точка і наступні визначаються як
найбільш віддалені від двох точок, куди вони пішли. Процес
знаходження характерних точок продовжується до тих пір, поки відношення відстані
від шуканої точки до прямої, що з'єднує ці дві точки, до довжини відрізка між
ними не стане менше деякої, наперед заданої величини EPS. Ця величина
є одним з небагатьох настроювальних параметрів програми, вона підбирається
експериментально таким чином, щоб програма розрізняла два найбільш близьких
до один одного контуру двох різних предметів з усієї групи. Результат знаходження
характерних точок для деякого приватного прикладу проекції тривимірного предмета
на площину представлений на рис.1.
Рис.1.
Знаходження характерних точок контуру
Гідністю
даного методу пошуку характерних точок контуру є те, що цей процес
інваріантний щодо поворотів, трансляцій і зміни масштабу. Можна
показати, що даний метод слабо чутливий і до спотворень частини контуру:
положення характерних точок у частинах, не піддалися спотворень, залишається
тим самим.
Кожному
отриманого за приведеним вище алгоритмом лінеаризації контуру відрізку
ставиться у відповідність два деяких числа N1 і N2, рівних відносин довжини
даного відрізка до довжинах сторін трикутників, прилеглих до нього (причому
вибирається сторона, яка не є відрізком контуру).
Додатково
до цих двох числах даному відрізку присвоюється ознака Z, рівний 1, якщо
сусідні відрізки прилягають до цього з одного боку, як на правій частині
малюнка, або Z =- 1, якщо вони знаходяться з різних сторін.
Шляхом
найпростіших математичних перетворень можна показати, що отриманий таким
чином набір груп чисел для відрізків всього контура дозволяє однозначно
визначити відносні координати всіх характерних точок і, отже, в
цьому наборі міститься інформація не тільки про відносні довжинах відрізків
контуру а й про кути між ними і даний набір чисел є стислим
поданням лінеарізірованного контуру. Це подання контуру після
простого перетворення дозволяє організувати просту і займає мало місця
базу даних або застосовувати Нейромережеве розпізнавання.
Очевидно,
що отримане таким чином двійкове число для даного контуру буде
інваріантної щодо трансляцій, ротації і зміни масштабу контуру.
В
справжній роботі розпізнавання предметів по частині контуру або по всьому контуру
здійснювалося з використанням спеціально влаштованій бази даних, яка містить
набори двійкових чисел, що характеризують контури, і відповідні їм назви
тривимірних предметів і параметри їх орієнтації в просторі.
Заповнення
бази даних здійснювалося так: що запам'ятовуються предмет випадковим чином
орієнтується щодо образотворчої площини і за алгоритмом, описаного
вище, визначається характеристичне двійкове число для даного контуру та
заноситься до бази даних спільно з назвою цього предмета, параметрами його
орієнтації в простору і послідовно розташованими по обходу контуру
трійками чисел N1, N2 і Z, однозначно описують його.
Виходячи
з цієї інформації визначається, чи був уже занесений даний контур в базу даних
і якщо він вже є, то генерується наступне випадкове положення предмета. У
Інакше інформація про предмет і його орієнтації заноситься до бази
даних. Цей процес продовжується до тих пір, поки не буде отримано поспіль До
відмов у занесення інформації в базу даних. Величина K є третьою
параметри настройки програми (другий параметр це масштабний коефіцієнт М)
і в цій роботі отримані оцінки, що при К = 10 відбувається надійне
розпізнавання пропонованих предметів з ймовірністю, що перевищує 0.99. Також
оцінки показують, що для набору з семи предметів, використаного при
тестуванні даної програми при значеннях настроювальних параметрів, наведених
у цій роботі, достатньо занести приблизно 3000 різних ракурсів кожного
предмета. При використанні в якості носія бази даних сучасних CD-ROM,
можна розмістити близько тисячі предметів. Слід також зазначити, що
пропонований метод розпізнавання є універсальним і може застосовуватися в
більш простих задачах - розпізнаванні символів, ієрогліфів, відбитків пальців
та інших плоских зображень.
При
розпізнаванні невідомого предмета програма працює таким чином. Після
попередньої обробки контуру або його частини виходить характеристичне
число Х, як це описано вище. Далі з бази даних вибирається найбільш близьке
по набору одиниць число або кілька таких чисел і проводиться остаточна
перевірка на відповідність контуру або його частини контуру, описаного в базі
даних наборами з трійок чисел, однозначно описують контур. Заключна
перевірка особливо актуальна, коли з'являється одночасно декілька
рівноцінних "кандидатів".
В
базу даних заносяться також габаритні геометричні розміри кожного предмета.
Ця інформація може бути використана для визначення відстані від пристрою
розпізнавання до даного предмета. Розрахунок відстані проводиться за найпростішим
формулами геометричної оптики. Як це було описано вище, при наявності двох
послідовних зображень предмета, простими обчисленнями визначається
швидкість предмета, а оскільки програма дозволяє визначити просторову
орієнтацію розпізнаного предмета, то стає можливим і визначення
вектори напряму швидкості.
Отримувана
таким чином інформація дозволить вирішувати такі складні завдання, як аналіз
ситуації, формування і накопичення бази знань про середовище, планування
оптимальної безпечної траєкторії руху до мети, прийняття управлінських
рішень про чергове русі. Простота використовуваних алгоритмів для вирішення
таких завдань дозволяє сподіватися, що при застосуванні даного методу стануть
можливими обробка інформації в реальному часі і збільшення швидкості РМК
під час руху по невідомій місцевості до технічно досяжних величин.
При
розпізнаванні тривимірного предмета за частиною його контуру на складному тлі
програма працює таким чином. При заповненні бази даних
характеристичні числа Х визначаються для всієї сукупності контурів,
належать тривимірних предмету, як зовнішніх, так і внутрішніх. Контури в
даному випадку утворюються межами розділу областей різних кольорів і
інтенсивностей на зображенні предмета в проектує площині так, як це
представлено, наприклад, на четвертій частині рис.2.
Розпізнавання
предмета на складному тлі здійснюється після попередньої обробки
плоского кольорового зображення. Спочатку кольорове зображення конвертується в
чорно-біле із ступінчастою градацією яскравості (див. першу частину рис. 2). Далі
програма визначає межі між областями різної інтенсивності і внутрішні
частини областей, розташованих між цими межами, заливає чорним кольором
(див. другу частину рис.2). Галузі, площі яких менше деякого
критичного розміру, підбираємо заздалегідь експериментально, з розгляду
виключаються (заливаються білим кольором). Після цього включається в роботу
підпрограма оконтурювання, яка обробляє кожну чорну область, як це
було описано вище. Результат виконання даної операції наведено на третьому
частини рис.2. Далі за алгоритмом, описаного вище, для кожного замкнутого
контуру визначаються характеристичне число Х і з бази даних вибираються
списки найбільш близьких по складу набору одиниць ракурсів тривимірних предметів.
Оскільки в даному випадку в порівнянні з оконтурювання по зовнішньому контуру
часткові контури предмета простіше по складу і в числі Х менше число одиниць,
то, як правило, кожному простому внутрішньому контуру програма знаходить з бази
даних десятки можливих кандидатів.
Після
складання списків можливих кандидатів на розпізнавання для кожного
замкнутого контуру проводиться просторовий аналіз оконтуренного малюнка.
Він полягає в наступному. Зіставляються списки можливих кандидатів кожного
розглянутого замкнутого контуру і всіх його найближчих сусідніх і той
кандидат на розпізнавання, який зустрічається в більшості з цих списків і
є найбільш вірогідним.
На
четвертої частини рис.2 представлений остаточний результат розпізнавання - на
ньому відображені всі замкнуті, розташовані по сусідству контури ракурсу
єдиного збігається предмета у всій базі даних. Природно, якщо б
на картинці на складному фоні були б розташовані різні предмети, то вони після
подібної фільтрації всі були б виявлені. Виходячи з аналізу представленого
тут опису методу розпізнавання тривимірного предмета на складному фоні,
очевидна його потенційна працездатність і у випадку, коли на малюнку
зображена тільки частина контуру або тривимірні предмети частково заступають один
одного. Експериментальна перевірка розпізнавання різних випадків такого
перекриття або розташування частини предмета на малюнку показала впевнене
розпізнавання предметів, якщо на малюнку присутні більше половини
зображення предмета. У випадках, коли на малюнку присутня менша частина
зображуваного предмета, тим з'являється велика кількість кандидатів на
розпізнавання, чим менша частина предмета зображена на малюнку.
Рис.2.
Результат розпізнавання об'єкта на складному фоні.
Тестування
програми в "стерильному" випадку, коли предмет розпізнавати за його зовнішньої
проекції на чистому тлі, здійснювалося на наборі з семи предметів з
використанням спеціальної програми створення тривимірних об'єктів в 3D --
геометрії. На рис.3 представлені зображення цих предметів у фіксований
момент часу. За допомогою цієї програми виділяється одиночний предмет, і його
зображення запам'ятовується в графічному файлі. Далі здійснюється вхід у
програму DETERMINATOR в режим РОЗПІЗНАВАННЯ. На екрані з'являється силует
запомненного на попередньому етапі предмета і проводиться пошук цього контуру в
базі даних по алгоритму, описаного вище. Результат розпізнавання предмета за
частини контуру представлений на мал.4.
Рис.3.
Бібліотека об'єктів
Рис.4.
Результат розпізнавання об'єкта за частиною контуру.
Перевірка
програми на тестових наборах предметів при проведенні статистичних випробувань
за методикою, близької до [2], показала стійку роботу при різних спотвореннях
частин контурів, що досягають до 50% контуру.
Була
здійснюється перевірка методу при роботі програми DETERMINATOR на складному
тлі, коли розпізнається предмет розташований серед контурних ліній,
обрамляють різноманітні предмети, їх тіні і пр. (см.ріс.2). Отримані
задовільні результати, що дозволяє сподіватися на застосування
пропонованого методу в реальній обстановці при розпізнаванні предметів на
фотознімках і телеізображеніях.
В
закінчення автор дякує І. Каляєва, ініціював цю роботу і В.
Шаповала, що люб'язно надав програмний генератор рухомих тривимірних
об'єктів. Дана стаття була опублікована в 2001 році в журналі
"Нейрокомп'ютери. Розробка та застосування "в 7 і 8 випусках.
Список літератури
1. L. Gupta and M. R. Sayeh. Neural
networks for planar shape classification. IEEE. 1988. P.936.
2.
А.П. Горелик, В.А. Скрипкін. Методи розпізнавання. М. "Вища школа".
1989. С.216.
Для
підготовки даної роботи були використані матеріали з сайту http://www.sciteclibrary.ru
