Спосіб порівняння зображень відбитків пальців

УКРАЇНА (19) UA (11) 51255 (13) U (51) МПК (2009) G06K 9/00 МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ ДЕРЖАВНИЙ ДЕПАРТАМЕНТ ІНТЕЛЕКТУАЛЬНОЇ ВЛАСНОСТІ ОПИС видається під відповідальність власника патенту ДО ПАТЕНТУ НА КОРИСНУ МОДЕЛЬ (54) СПОСІБ ПОРІВНЯННЯ ЗОБРАЖЕНЬ ВІДБИТКІВ ПАЛЬЦІВ рмулою: sim nmatched / k1 * k 2 , де nmatched , k1, k 2 - відповідно кількість знайдених відповідних точок і загальні кількості особливих точок двох зображень в області їх перекриття, та (13) 51255 (11) порівняння обчисленої міри близькості з попередньо заданим граничним значенням. 3. Спосіб за п. 1, який відрізняється тим, що опорні точки на двох порівнюваних зображеннях вибирають з числа особливих точок, які відповідають кінцям або розгалуженням папілярних ліній цих зображень. 4. Спосіб за п. 1, який відрізняється тим, що виконують пошук множини М пар відповідних точок шляхом побудови повного дводольного графа, лівим та правим вершинам якого відповідають особливі точки відповідно першого та другого порівнюваних зображень, а дужкам графа - сума зважених різниць атрибутів вершин, які з'єднує ця дужка, та знаходження оптимальної розмітки вершин цього дводольного графа. 5. Спосіб за п. 1, який відрізняється тим, що визначають ділянку перекриття двох порівнюваних зображень як таку, що є перекриттям опуклих оболонок множин особливих точок на цих зображеннях. 6. Спосіб за п. 1, який відрізняється тим, що визначають ділянку перекриття двох суміщених порівнюваних зображень як таку, що є перекриттям тих (інформативних) ділянок на цих зображеннях, на яких можуть бути виділені папілярні лінії. 7. Спосіб за п. 1, який відрізняється тим, що визначають остаточну сукупність пар відповідних точок шляхом визначення та додавання до МO нових пар відповідних особливих точок, які знаходяться в області перекриття двох порівнюваних зображень і є просторово сумісними з усіма іншими парами точок цієї множини. 8. Спосіб за пп. 1, 3, який відрізняється тим, що формують список пар кандидатів на опорні точки, упорядкованих у цьому списку по значенню міри близькості точок, що входять в ці пари, а наступні операції порівняння двох зображень виконують з послідовним вибором опорних точок, що містяться у цьому списку, починаючи з першої, доти, поки або буде отримано значення міри близькості між порівнюваними зображеннями, що перевищує задане граничне значення, або ж будуть вибрані усі пари точок із цього списку. 9. Спосіб за пп. 1, 3, 8, який відрізняється тим, що міра близькості двох точок, які є кандидатами на відповідні опорні точки, визначається на основі порівняння атрибутів папілярних ліній, що відпові UA (21) u201000002 (22) 11.01.2010 (24) 12.07.2010 (46) 12.07.2010, Бюл.№ 13, 2010 р. (72) КИЙКО ВОЛОДИМИР МИХАЙЛОВИЧ (73) МІЖНАРОДНИЙ НАУКОВО-НАВЧАЛЬНИЙ ЦЕНТР ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ ТА СИСТЕМ (57) 1. Спосіб порівняння зображень відбитків пальців, що заснований на пошуку особливих точок на зображеннях, пошуку відповідних опорних точок на зображеннях, визначенні значень атрибутів особливих точок на зображеннях відносно їх опорних точок, пошуку відповідних особливих точок на двох порівнюваних зображеннях і прийнятті рішення про ці зображення на основі кількості знайдених відповідних особливих точок, який відрізняється тим, що виконують пошук попередньої сукупності пар відповідних особливих точок на двох зображеннях такої, що цій сукупності М відповідає найменша сума зважених різниць атрибутів відповідних точок, а кількість відповідних пар точок дорівнює меншій з двох загальних кількостей особливих точок на зображеннях, виконують пошук відповідних особливих точок шляхом виділення з множини М найбільшої підмножини МO М просторово сумісних пар особливих точок, виконують суміщення особливих точок першого зображення з особливими точками другого зображення шляхом збігу їх опорних точок та відповідного повороту особливих точок одного з зображень навколо опорної точки на цьому зображенні, обчислюють загальні кількості особливих точок двох порівнюваних зображень в області перекриття цих зображень і приймають рішення про два порівнювані зображення на основі кількості знайдених відповідних точок, а також загальних кількостей особливих точок в області перекриття цих двох зображень. 2. Спосіб за п. 1, який відрізняється тим, що приймають рішення про те, що два порівнювані зображення є відбитками одного пальця шляхом обчислення міри близькості цих зображень за фо U 2 (19) 1 3 51255 4 дають цим точкам, а також визначення кількості пар відповідних особливих точок в певній околиці цих опорних точок. 10. Спосіб за пп. 1, 4, який відрізняється тим, що дужкам дводольного графа відповідають значення, які не перевищують попередньо заданого граничного значення. 11. Спосіб за пп. 1, 2, який відрізняється тим, що k1, k2 обчислюють як зважені суми особливих точок в області перекриття двох зображень, взяті з коефіцієнтами, які залежать від надійності визначення цих точок на зображеннях. Спосіб порівняння зображень відбитків пальців людини відноситься до обробки зображень, зокрема до обробки та розпізнавання зображень відбитків пальців і може бути використаний в комп'ютерних системах ідентифікації людини, безпеки, контролю доступу до приміщень та до інформації. Найбільш поширений підхід до ідентифікації людини за відбитками її пальців полягає у пошуку особливих точок на папілярному узорі відбитка пальця, які є кінцями або розгалуженнями папілярних ліній на цьому узорі, та порівнянні сукупностей особливих точок на вхідному та еталонних зображеннях між собою. Кожна з цих точок задається своїми координатами (х, у) та кутом напряму 1 папілярної лінії, що відповідає цій точці (Фіг.1). Для пошуку особливих точок, як правило, виконують такі етапи обробки півтонового вхідного зображення: - пошук відбитка пальця на зображенні; - покращення якості зображення за допомогою одного з алгоритмів направленої фільтрації (наприклад, Hong L.,Wan Y., and Jain A.K., "Fingerprint Image Enhancement: Algorithms and Performance Evaluation", IEEE Trans. On РАМІ, vol.20, no.8, pp.777-789, 1998), виділення інформативних частин на покращеному зображенні (сегментація) та перетворення його на бінарне зображення; - усунення завад типа «сіль» та «перець» на бінарному зображенні; тоншання ліній на бінарному зображенні (скелетизація) до товщини, яка дорівнює одній клітці; - усунення завад на скелетизованому зображенні та пошук особливих точок на цьому зображенні. Головна проблема при розпізнаванні зображень відбитків пальців відноситься до порівняння двох сукупностей (на вхідному та еталонному зображеннях) особливих точок. Складність цієї проблеми обумовлена тим, що зображення відбитка одного й того ж пальця можуть мати значні відмінності, які зумовлені численними завадами на зображеннях, різними умовами та неоднорідністю притиснення пальця, а також ушкодженнями поверхні пальця людини в процесі його діяльності. Як наслідок цих, а також інших обставин, сукупності особливих точок на двох зображеннях відбитка одного й того ж пальця можуть мати значні відмінності, наприклад такі: - сукупності особливих точок зміщені та повернуті відносно одна одній або мають різний масштаб; при цьому ділянка перекриття двох суміщених зображень може бути малою у порівнянні з розмірами зображень; - присутні помилкові та відсутні справжні особливі точки; - особливі точки зміщені відносно своїх правильних положень і ці зміщення є різними для різних точок; ці зміщення можуть бути досить великими (більшими, ніж відстані між папілярними лініями) і змінюватись лінійно або нелінійно уздовж зображення. Відомий спосіб порівняння двох зображень (вхідного та еталонного) відбитків пальців (N. Ratha, К. Каru, S. Chen and A. K. Jain, A Real-time Matching System for Large Fingerprint Database, IEEE Transactions on Pattern Analysis and Machine Intelligence, Volume 18, Number 8, pages 799-813, 1996). Цей спосіб заснований на пошуку особливих точок на обох зображеннях, які відповідають кінцям або розгалуженням папілярних ліній на цих зображеннях; визначенні методом Хока параметрів перетворення (зміщення, повороту та масштабування) особливих точок на вхідному зображенні з метою кращого суміщення з особливими точками еталонного зображення; перетворенні особливих точок на вхідному зображенні згідно з визначеними параметрами; пошуку відповідних пар особливих точок на порівнюваних зображеннях шляхом перевірки для кожної особливої точки t на вхідному зображенні, чи є особлива точка t' на еталонному зображенні така, що її атрибути (координати (x', y') і кут напряму 1) є близькими з точністю попередньо заданих граничних значень до відповідних параметрів точки t; прийнятті рішення про два порівнювані зображення на основі визначеної кількості пар відповідних особливих точок та загальних кількостей особливих точок на цих зображеннях. Загальними ознаками пропонованого і відомого способів є пошук особливих точок на двох зображеннях; визначення параметрів перетворення вхідного зображення для кращого збігання сукупностей особливих точок двох зображень; збігання особливих точок першого зображення з особливими точками другого зображення шляхом зміщення та повороту цих точок та прийняття рішення про те, чи є два порівнювані зображення відбитками одного й того ж пальця людини, на основі визначення кількості відповідних особливих точок на двох зображеннях. Причиною, що заважає вирішити поставлену задачу, є те, що відомий спосіб не використовує оптимальні алгоритми для знаходження відповідних особливих точок на двох зображеннях, а також не забезпечує пошук відповідних точок в умовах суттєвих нерівномірних локальних зміщень особливих точок на одному зображенні відносно положень відповідних особливих точок на другому зображенні. 5 З відомих способів порівняння зображень відбитків пальців найбільш близьким по своїй сутності і результату, що досягається, є спосіб (див. патент США №6.185.318, G06О09/00, 6.02.2001), заснований на пошуку особливих точок на двох зображеннях, які відповідають кінцям або розгалуженням папілярних ліній на цих зображеннях; пошуку на зображеннях двох відповідних одна одній (перша точка на одному і друга точка на другому зображенні) так званих «опорних» точок; обчисленні значень атрибутів (відстань та кути напрямів) особливих точок двох зображень відносно до їх опорних точок; формуванні упорядкованих (по положенню відносно опорних точок) списків особливих точок на обох зображеннях; знаходженні методом еластичної розмітки (динамічного програмування) найкращої (оптимальної по певному критерію) відповідності особливих точок у цих двох списках і прийнятті рішення про два порівнювані зображення на основі кількості знайдених відповідних точок та загальних кількостей особливих точок на обох зображеннях. Загальними ознаками пропонованого і відомого способів є пошук особливих точок на двох зображеннях; пошук на зображеннях двох відповідних опорних точок; обчислення значень атрибутів особливих точок двох зображень відносно до їх опорних точок; знаходження оптимальної відповідності особливих точок на двох зображеннях та прийняття рішення про два порівнювані зображення на основі кількості знайдених відповідних особливих точок на цих зображеннях. Причиною, що заважає вирішити поставлену задачу, є те, що пошук відповідних точок на порівнюваних зображеннях виконується шляхом отримання одновимірних представлень зображень у вигляді упорядкованих списків їх особливих точок і знаходження відповідних точок у цих двох списках методом еластичної розмітки точок у цих списках, тому що такий підхід забезпечує перевірку лише частини можливих відповідностей між особливими точками двох зображень. Так наприклад, якщо у першому списку порядок слідування деяких двох точок (наприклад, друга точка має більший порядковий номер, ніж перша) є відмінним (внаслідок завад, помилок при упорядкуванні або виборі перших точок) від порядку слідування відповідних їм двох особливих точок у другому списку, то установлення правильної відповідності цих точок за допомогою алгоритму еластичної розмітки є неможливим при будь-яких параметрах цього алгоритму. Цей недолік відомого методу не може бути виправлений шляхом зміни його параметрів, а лише шляхом використання не одновимірних, а двовимірних представлень порівнюваних зображень, а також більш потужних, ніж динамічне програмування, методів порівняння цих представлень, зокрема метода знаходження оптимальної розмітки на відповідних дводольних графах. Інший недолік відомого способу порівняння двох зображень полягає у тому, що за цим способом міра близькості двох зображень обчислюється за формулою: sim nmatched N1 * N2 , 51255 6 де nmatched , N1, N2 - відповідно кількість знайдених відповідних точок і загальні кількості особливих точок на двох зображеннях. У більшості випадків отримують лише часткові фрагменти відбитків пальців, тобто рішення про порівнювані зображення необхідно приймати в умовах лише часткового перекриття цих зображень. У таких умовах більш доцільно обчислювати і використовувати у попередній формулі замість загальних кількостей N1, N2 особливих точок двох зображень - загальні кількості цих точок лише в області перекриття суміщених порівнюваних зображень. В основу моделі поставлена задача розробити такий спосіб порівняння зображень відбитків пальців, у якому завдяки запропонованій послідовності операцій забезпечується підвищення надійності розпізнавання зображень відбитків пальців в умовах лише часткового перекриття порівнюваних зображень та суттєвого зміщення особливих точок на одному зображенні відносно положень відповідних особливих точок на другому зображенні. Поставлена задача досягається тим, що виконують пошук особливих точок на двох порівнюваних зображеннях, знаходять відповідні опорні точки на цих зображеннях, визначають значення атрибутів (відстань та кути напрямів) особливих точок на зображеннях відносно до їх опорних точок, формують зважений дводольний граф, лівими та правими вершинами якого є особливі точки відповідно першого та другого порівнюваних зображень, виконують пошук відповідних особливих точок за допомогою алгоритму знаходження оптимальної розмітки вершин на цьому дводольному графі, приймають рішення про порівнювані зображення на основі кількості знайдених відповідних точок, а також визначених загальних кількостей особливих точок в межах перекриття цих двох суміщених між собою зображень. Відмітними ознаками пропонованого способу є те, що з метою підвищення надійності розпізнавання зображень відбитків пальців спочатку виконують пошук попередньої множини М пар відповідних особливих точок на двох зображеннях шляхом знаходження оптимальної розмітки на зваженому дводольному графі, лівими і правими вершинами якого є особливі точки відповідно першого та другого зображень, а вага кожної дужки є зваженою сумою абсолютних різниць атрибутів двох вершин, які з'єднує ця дужка. Після цього виконують пошук відповідних особливих точок шляхом виділення з множини М найбільшої підмножини Мо М просторово сумісних пар особливих точок (таких пар, коли просторові відношення між точками на одному зображенні є приблизно такими ж як і між відповідними точками на другому зображенні), виконують суміщення особливих точок другого зображення з особливими точками першого зображення шляхом суміщення їх опорних точок та відповідного повороту особливих точок на другому зображенні навколо опорної точки, обчислюють загальні кількості особливих точок двох порівнюваних зображень в ділянці перекриття цих зображень і приймають рішення про порівнювані зображення на основі кількості знайдених відповідних точок, а також загальних кількостей 7 особливих точок в межах перекриття цих двох суміщених зображень. Практична цінність пропонованого способу полягає у підвищенні надійності розпізнавання зображень відбитків пальців в умовах часткового перекриття порівнюваних зображень та суттєвого зміщення особливих точок на одному зображенні відносно положень відповідних особливих точок на другому зображенні. Це забезпечується шляхом а) збільшення кількості знайдених відповідних точок на двох порівнюваних зображеннях і б) використання при обчисленні міри близькості двох зображень замість загальних кількостей особливих точок - кількостей цих точок лише в області перекриття двох суміщених порівнюваних зображень. Суть пропонованого способу полягає у наступному: 1) Виконують попередню обробку вхідного зображення та отримують його представлення у вигляді списку особливих точок. Кожна з особливих точок t описується у кращому варіанті пропонованого способу за допомогою таких атрибутів (Фіг.1): - Тип особливої точки n: n=1 (кінець відповідної папілярної лінії) або n=3 (розгалуження ліній), якщо надійність виділення цієї точки вважається порівняно високою, та відповідно n=2 і n=4 у противному випадку. - Координати (х, у) особливої точки на зображенні. - Кут напряму 1 (0-360 град.) особливої точки. - Кути напрямів 2 i 3 в точках t2 і t3 папілярної лінії, які знаходяться на тій же папілярній лінії, що і особлива точка t, на відстанях, які відповідно дорівнюють 25 и 40 кліткам зображення від цієї особливої точки. При цьому кут 2 може бути обчислений як кут напряму від точки t2 до точки t, а 3 - як кут напряму від точки t3 до точки t2. Таким чином, кожна особлива точка описується за допомогою 6-й чисел, для зберігання яких потрібно 11 байт. При необхідності кількість атрибутів може бути скорочена до 3-х: координати (х, у) і кут напряму 1 особливої точки, що відповідає формату даних, які використовуються у FBI [J.H. Wegstein. "An automated fingerprint identification system", U.S. Government Publication, Washington, DC: U.S. Dept. Of Commerce, National Bureau of Standards, 1982]. 2) Виконують пошук відповідних опорних точок на порівнюваних зображеннях. Для цього обчислюють міри близькості тих пар особливих точок на двох порівнюваних зображеннях (одна з точок є на одному зображенні і інша - на другому), які мають однаковий тип і близькі значення таких різниць кутів напряму, відповідних цим точкам: 1= 1- 2; 2= 1- 3. Міру близькості кожної з цих пар точок t1, t2 обчислюють за формулою: sim(t1,t2)=nmatch(t1,t2)*100/(n1*n2), де nmatch(t1,t2) - кількість знайдених відповідних особливих точок в околицях точок t1 і t2 розміром 75 кліток зображення, а n1(n2) - загальна кількість особливих точок в околиці точки t1(t2), тобто відстань яких до точки t1(t2) не перевищує задану 51255 8 граничну відстань 75 кліток. Кількість nmatch(t1,t2) відповідних точок при цьому визначають по такому алгоритму: - Формують два списки особливих точок такі, що особливі точки із першого списку розташовані в заданій околиці точки t1, а точки із другого списку в околиці точки t2. Для кожної точки t з першого(другого) списків визначають такі три атрибути: відстань та дві різниці кутів 1, 2 відносно точки t1(t2). При цьому, якщо t є точкою з першого списку, то 2= (t,t1)- 1(t1), де (t,t1) 1= 1(t)- 1(t1), кут напряму від точки t1 до точки t, a 1(t), 1(t1) кути напрямів особливих точок t і t1 (Фіг.1). - Послідовно вибирають точки з першого списку і для кожної з цих точок перевіряють, чи є у другому списку одна з точок така, що різниці її атрибутів з атрибутами першої точки не перевищують заданих граничних значень. Якщо є така точка, то її видаляють із другого списку, збільшують значення nmatch(t1,t2) на 1 і вибирають наступну точку з першого списку. На основі обчислених значень мір близькості формують упорядкований по цим значенням список пар особливих точок - кандидатів на відповідні опорні точки на двох порівнюваних зображеннях. Першою у цьому списку є пара особливих точок, яка має найбільше значення міри близькості. Довжина списку залежить від отриманих значень мір близькості. Так, наприклад, довжина списку може дорівнювати двом, якщо найбільше отримане значення міри близькості перевищує 70, або - десяти у противному випадку. 3) Послідовно вибирають пари точок із упорядкованого списку пар - кандидатів на опорні точки, приймають ці точки за опорні особливі точки на порівнюваних зображеннях і за такої умови визначають міру близькості між цими зображеннями до тих пір, поки або буде отримано значення міри близькості, що перевищує задане граничне значення, або ж будуть вибрані усі пари точок із цього списку. Останнє означає прийняття рішення про те, що два порівнювані зображення не відповідають відбиткам одного й того ж пальця людини. При цьому визначення близькості між двома порівнюваними зображеннями для кожної пари опорних точок виконується за допомогою наступних дій. 4) Визначають значення атрибутів (відстань та кути напрямів) особливих точок на двох порівнюваних зображеннях відносно до їх опорних точок. T Позначимо через p0 і piT опорну та деяку іншу і-у особливі точки на еталонному зображенні, і відповідно через pI0 , pIi - опорну та деяку іншу j-у особливі точки на вхідному зображенні. Атрибути точки piT , які визначають відносно опорної точки T p0 (див. Фіг.2) є такими: а) відстань (в мм) dТ (i,0) між цими точками; б) кут напряму T (i,0) від точки T T p0 до точки piT (кут між відрізком лінії ( p0 , piT ) та горизонталлю); в) різниця d 1T(i,0) кутів T 1 T i : d 1 i,0 параметра 1 T i,0 T 1 i , де T 1 i T (i,0) і - значення і-ї особливої точки і г)різниця d 2T 9 (і,0) параметрів 1 51255 T для і-ї та опорної p0 точок: T T d 2T i,0 1 i 1 0 . Таким же чином визначають атрибути особливих точок на вхідному зображенні відносно опорної точки на цьому зображенні. 5) Виконують пошук попередньої сукупності пар відповідних особливих точок на двох зображеннях такої, що цій сукупності М відповідає найменша сума зважених різниць атрибутів відповідних точок, а кількість відповідних пар точок дорівнює меншій з двох загальних кількостей особливих точок на зображеннях. Wij min( ni n j * 2 min( min( d 1T i,0 d 1I j,0 ,360 min( d 2T i,0 dT i,0 T i,0 I d 1T i,0 d 2I j,0 ,360 j,0 ,360 10 Для знаходження такої сукупності формують повний дводольний граф, лівим та правим вершинам якого відповідають особливі точки відповідно першого та другого порівнюваних зображень, а дужкам графа - суми зважених різниць атрибутів вершин, які з'єднують ці дужки. Кожна ліва вершина цього графу з'єднана дужками з усіма правими вершинами, а кожна права вершина - з усіма лівими. Вага Wij деякої дужки дводольного графу у кращому варіанті пропонованого способу дорівнює такій сумі зважених різниць атрибутів вершин piT і pIj , які з'єднує ця дужка: T i,0 I j,0 ) * 0 .2 d 1I j,0 ) * 0.25 d 2T i,0 d 2I j,0 ) * 0.25 (1) dI j,0 * 10.30 де ni, nj - значення параметру n (1 або 3) відповідно і-ї точки на еталонному та j-ї точки на вхі означає, що точці pIi на вхідному зображенні пос особливих точок на еталонному зображенні. Пошук оптимальної розмітки на дводольному графі може бути виконаний за допомогою відомих алгоритмів, зокрема алгоритму, який запропонований у [Jonker R., Volgenant A.A shortest augmenting path algorithm for dense and sparse linear assignment problems. / Computing 38, 1987, p.p.325-340]. Кількість попередньо знайдених відповідних пар точок дорівнює на цьому етапі меншій з двох загальних кількостей особливих точок на порівнюваних зображеннях. 6) Виконують пошук відповідних особливих точок на двох зображеннях шляхом виділення з отриманої на попередньому кроці множини М найбільшої підмножини Мо М просторово сумісних пар особливих точок. Останнє означає, що такі просторові відношення як відстані та кути напрямів між точками на одному зображенні є приблизно такими ж як і між відповідними точками на другому зображенні. Знаходження оптимальної розмітки не гарантує того, що знайдена відповідність для усіх особливих точок є правильною, особливо в тих випадках коли має місто лише часткове перекриття порівнюваних зображень. З метою знаходження помилок розмітки виконують наступні дії: - Переглядають усі пари попередньо визначених відповідних точок і якщо для деякої пари цих точок різниця одного з їх атрибутів перевищує задане граничне значення, ці точки вважаються невідповідними. - Переглядають усі пари точок, що залишились відповідними після виконання попереднього тавлено у відповідність точку pT на еталонному t етапу. Для кожної з цих пар ( pIi , pT ) перевіряють t 0 - що точці pIi не поставле чи є просторові відношення першої точки pIi цієї T I дному зображенні, 1 0 1 0 - кут повороту вхідного зображення відносно еталонного, який дорівнює різниці кутів напрямів опорних точок на цих зображеннях. Перше складове значення у фо рмулі (1) - штраф за те, що точки piT і pIj мають різні типи (одна з точок-кінець, а друга точка - розгалуження папілярної лінії); друге - штраф за різність напрямів цих точок після суміщення зображень до відповідних опорних точок на цих зображеннях; третє та четверте - штрафи за різниці відносних кутів напряму цих точок і п'яте штраф за різницю відстаней точок piT і pIj до опорних точок. Згідно цієї формули ваги на дужках графу не перевищують значення, що дорівнює 30. Після формування дводольного графа виконують пошук оптимальної розмітки вершин на цьому графі. Це означає, що а) кожній лівій вершині графа ставиться у відповідність не більше, ніж одна права вершина, б) кожній правій вершині ставиться у відповідність не більше, ніж одна ліва вершина, і, крім того, сумарна вага дужок, які з'єднують відповідні вершини, є найменшою у порівнянні з усіма іншими можливими розмітками вершин. Знайдена розмітка є така функція: R : R pIi p T , R pT t t pIi для усіх пар відповідних особливих точок ( pIi , pT ). При цьому R pIi t зображенні, a R pIi pT t на у відповідність ні одна з точок pT . Останнє моt же бути тоді, коли кількість знайдених особливих точок на вхідному зображенні більше кількості пари з іншими розміченими ( R pIi 0 ) точками pIj на вхідному зображенні приблизно такими же, як і просторові відношення другої точки pT з відповідt 11 ними точками R pIi на еталонному зображенні. Результат перевірки кожної пари точок ( pIi , pT ) є t кількість розмічених точок, які є просторово несумісними з точками цієї пари ( pIi , pT ), та список t номерів цих несумісних точок. - Знаходять дві відповідні точки ( pIi , pT ), яким t відповідає найбільша кількість просторово несумісних з ними розмічених точок, вважають ці дві точки невідповідними і виключають їх із усіх списків несумісних точок. Повторюють ці дії до тих пір, поки усі пари відповідних точок, що залишились, будуть між собою просторово сумісними. 7) Виконують збігання особливих точок першого зображення з особливими точками другого зображення шляхом збігу їх опорних точок та повороту особливих точок одного з зображень навколо опорної точки. Обчислюють загальні кількості особливих точок двох порівнюваних зображень в ділянці перекриття цих зображень. При цьому, якщо на зображеннях визначені області їх інформативності (області, де знаходяться папілярні лінії, які можуть бути розпізнані людиною або комп'ютерною програмою), то вважається, що деяка особлива точка знаходиться в області перекриття двох зображень, якщо вона належить до інформативних областей на кожному з цих суміщених між собою зображень. Якщо ж області інформативності порівнюваних зображень не визначені, то у кращому варіанті пропонованого способу ділянка перекриття двох порівнюваних зображень визначається як така, що є перекриттям опуклих оболонок множин особливих точок на цих зображеннях. 8) Визначають остаточну сукупність пар відповідних точок шляхом знаходження повним перебором та додавання до визначеної у п. 6 множини МО нових пар відповідних особливих точок, які знаходяться в області перекриття двох порівнюваних зображень і є просторово сумісними з усіма іншими парами точок цієї множини. 9) Приймають рішення про два порівнювані зображення на основі кількості знайдених відповідних точок, а також загальних кількостей особливих точок в межах перекриття цих зображень. При цьому приймають рішення про те, що два порівнювані зображення є відбитками одного пальця шляхом а) обчислення міри близькості цих зображень за формулою: sim nmatched / k1 * k 2 , де nmatched - кількість знайдених відповідних точок і k1, k2 - загальні кількості особливих точок двох зображень в області їх перекриття, та б) порівняння обчисленої міри близькості з попередньо заданим граничним значенням. Розглянемо приклад, що ілюструє пропонований спосіб. На Фіг.3 показано: два вхідні зображення різних відбитків одного й того ж пальця (а), бінарні представлення зображень (б), знайдені особливі точок на скелетизованих представленнях зображень (в) і результат пошуку відповідних точок на цих зображеннях (г). Вхідні зображення взяті з бази даних FVC2002 (Maio D., Maltoni D., 51255 12 Cappeli R., Wayman J.L., and Jain A.K."FVC2002: Second Fingerprint Verification Competition", in Proc. Int. Conf. On Pattern Recognition (16th), Vol. 3, pp. 811-814, 2002). Ці зображення введені за допомогою оптичного сканеру Optical Identixtouch ViewII (388x374; 500 dpi). Загальні кількості знайдених особливих точок на лівому і правому зображеннях на Фіг.3 відповідно дорівнюють 47 і 28. Ці особливі точки показані на Фіг.3,в за допомогою позначок у формі квадрату, при цьому менші по розміру позначки відповідають більш надійно визначеним особливим точкам. На Фіг.3,г показано результат пошуку відповідних точок на цих зображеннях. Дві опорні точки на цьому рисунку показані за допомогою прямокутників навколо цих точок. Параметри зміщення (вліво на 138 кліток та вниз на 57 кліток) та повороту відносно опорної точки ( = -31°) правого зображення для суміщення з лівим зображенням визначені за допомогою координат та кутів напрямів опорних точок на цих зображеннях. Знайдені відповідні особливі точки показані на Фіг.3,г за допомогою менших по розміру квадратних позначок, а всі інші (нерозмічені) особливі точки, які знаходяться в області перекриття двох суміщених зображень, показані на Фіг.3,г за допомогою більших квадратних позначок. Одна пара точок, яка була добавлена до числа відповідних (див. вище етап 8), показана на Фіг.3,г за допомогою двох кіл навколо цих точок. При цьому кількість знайдених відповідних точок дорівнює 23, а загальні кількості особливих точок в області перекриття лівого та правого суміщених зображень складають відповідно 39 і 25 точок. Обчислена міра близькості між двома порівнюваними зображеннями є досить великою і дорівнює 76, що дозволяє прийняти рішення про те, що ці два зображення відповідають відбиткам одного й того ж пальця. Перелік фігур креслення Фіг.1. Приклади особливих точок на зображенні відбитка пальця, кожна з яких задається своїми координатами та кутом напряму папілярної лінії, що відповідає цій точці. Фіг.2. Кути напряму особливої точки piT відноT сно опорної точки p0 . Фіг.3,а. Приклад двох зображень різних відбитків одного й того ж пальця. Фіг.3,б. Бінарні представлення зображень на Фіг.3,а. Фіг.3,в. Знайдені особливі точки на скелетизованих представленнях зображень на Фіг.3,б. Фіг.3,г. Результат пошуку відповідних точок на зображеннях на Фіг.3,в. Відомості, які підтверджують можливість здійснення моделі Розроблено програмне забезпечення MMV (minutiae matching verification) для розпізнавання зображень відбитків пальців, що реалізує пропонований спосіб порівняння двох або декількох зображень відбитків пальців. Тестування розробленого програмного забезпечення виконувалось на відомих базах даних FVC2002 та NIST27. База даних FVC2002 була створена для проведення світової першості програм верифікації 13 відбитків пальців у 2002 році і складається з 4-х частин: DB1, DB2, DB3 и DB4. Тестування виконувалось на перших двох частинах DB1 і DB2, які були створені за допомогою відповідно оптичних датчиків Optical Identixtouch ViewII (388 374; 500 dpi) і Biometrica FX2000 (296 560; 569 dpi). Кожна з DB1 і DB2 містить 880 зображень (110 8: по 8 відбитків кожного з 110 пальців). Тестування програмного забезпечення виконувалось таким чином: спочатку для кожного з 110 пальців вибиралось одне з 8-й зображень у якості еталона, після чого виконувалось порівняння усіх 8-й відбитків цього пальця з еталоном для отримання оцінки FNMR вірогідності помилки розпізнавання (вірогідності не розпізнавання) зображень «свого» класу, тобто зображень, які відповідають тому ж пальцю людини, що і еталон. Після цього усі 110 еталонні зображення перехрест порівнювались між собою (загалом 12100 порівнянь) для отримання оцінки FMR - вірогідності помилки розпізнавання зображень «чужих» класів, тобто помилкового прийняття рішення про два зображення, що вони відповідають одному класу, коли фактично вони відповідають різним класам. Для більшості класів (для DB1 - 106 з 110-и, а для DB2 - 109 з 110-и) у якості еталонного зображення відбитка пальця бралось перше з 8-й зображень цього пальця. При тестуванні використовувалось фіксоване граничне значення міри близькості sim між двома порівнюваними зображеннями, яке дорівнює 62. Основні результати тестування полягають у наступному. База даних DB1. Кількість нерозпізнаних зображень: n=0. Кількість помилок розпізнавання: m=2. FNMR=n*100/880=0.68 %; FMR=m*100/12100=0.016 %; EER≈(0+0.016)*0.5=0.08%. Час обробки та пошуку особливих точок на еталонному зображенні у середньому складає 0.78 сек (Pentium 800 Мгц). Час обробки, пошуку особливих точок на вхідному зображенні та порівнювання цього зображення з еталонним зображенням у середньому складає 0.86 сек. База даних DB2. 51255 14 Кількість нерозпізнаних зображень: n=6. Кількість помилок розпізнавання: m=1. FNMR=n*100/880=0.68 %; FMR=m*100/12100=0.008%; EER≈(0.68+0.008)*0.5=0.34 %. Час обробки та пошуку особливих точок на еталонному зображенні у середньому складає 0.95сек. (Pentium 800 Мгц). Час обробки, пошуку особливих точок на вхідному зображенні та порівнювання цього зображення з еталонним зображенням у середньому складає 1.08сек. База даних NIST27 створена Національним інститутом стандартів та технологій США (NIST) сумісно з Федеральним Бюро Досліджень (FBI). Ця база даних містить 258 зображень відбитків пальців, що були залишені на містах злочину на поверхні різних предметів, а також дані про особливі точки на цих зображеннях, які були отримані за допомогою експертів. Загалом ці зображення мають дуже низьку якість і численні завади. Ось чому помилка ідентифікації цих зображень навіть за допомогою досвідчених експертів дорівнює 80%. Дані про особливі точки на зображеннях з бази даних NIST27, які сформовані цими експертами, також містять багато помилок внаслідок низької якості зображень. Тестування розробленого програмного забезпечення виконувалось на сукупності даних про особливі точки(координати та кути напрямів), які містяться в базі даних NIST27 і отримані за допомогою експертів. Сукупність особливих точок кожного з 258 зображень послідовно порівнювалась з 206-ма еталонними сукупностями особливих точок, які також були знайдені експертом, але на еталонних зображеннях відбитків пальців. При цьому, якщо вхідне зображення мало найбільшу міру близькості з деяким еталонним зображенням, то приймалось рішення про те, що ці зображення відповідають одному й тому ж класу. Головний результат цього тестування полягає у наступному: помилка розпізнавання 258 зображень при порівнянні кожного з цих зображень з 206-ма еталонами складає 80%, тобто не є більшою ніж помилка досвідчених експертів при ідентифікації зображень у ручному режимі. 15 Комп’ютерна верстка Н. Лиcенко 51255 Підписне 16 Тираж 26 прим. Міністерство освіти і науки України Державний департамент інтелектуальної власності, вул. Урицького, 45, м. Київ, МСП, 03680, Україна ДП “Український інститут промислової власності”, вул. Глазунова, 1, м. Київ – 42, 01601