Ідентифікація відбитків пальців на основі Гамільтонових циклів розподілу локальних ознак

Анотація

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