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

Вступ

Біометрія, як наука вивчення математичних або статистичних властивостей у фізіологічних і поведінкових людських характеристиках, широко використовується у сфері захисту інформації. Використання відбитків пальців в якості біометрії є одним з найстаріших методів автоматизоматизованої ідентифікації особи і водночас найбільш поширеною в наш час. До числа факторів, які сприяють поширенню використання систем такого типу можна віднести: незначні розміри та вартість апаратури для обробки зображень відбитків пальців, високопродуктивне апаратне забезпечення, степінь та швидкість розпізнавання, що відповідають вимогам програмного забезпечення, різкий ріст та розвиток мережних технологій та Інтернету, а також усвідомлення необхідності простих, базових методів захисту та безпеки інформації.
В даній статті пропонується визначення класичного методу ідентифікації особи за відбитками пальців та на його основі проводиться аналіз різних його модифікацій. Виділено проблеми, які виникають на різних етапах у систем ідентифікації.
Приведена також статистика та ефективність методів розпізнавання, яка допомагає визначити ефективність даного методу для різних систем.

Постановка задачі

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

Обробка зображення та розпізнавання

Після отримання зображення відбитка пальця необхідно здійснити його обробку. В процесі обробки, зображення повинне досягнути якомога кращої якості, що необхідно досягнути для здійснення коректного розпізнавання. Основні етапи процесу обробки зображення є наступними: усунення завад(шуму) та покращення чіткості, виявлення основних характеристик та саме розпізнавання.
Фільтрація зображення .
У результаті того, що пальці можуть бути забруднені, пошкоджені, вологі чи сухі постає проблема максимально відфільтрувати зображення та зробити відображення папілярів та відстаней між ними більш чіткими. З цією метою виконуються 2 операції: адаптивна узгоджуюча і фільтрація та адаптивна порогова сегментація. Незважаючи на можливі обриви і неоднорідності окремих папілярів можна визначити їх напрям. Така фільтрація застосовується до кожного пікселя зображення. На основі даних про такого роду орієнтацію папілярів до кожного пікселя застосовується адаптивна узгоджуюча фільтрація для виділення папілярів, які орієнтовані в однаковому напрямку і приглушення на зображенні частинок протилежного напрямку. Проте і надалі можуть існувати шуми, які спричиняють ефект злиття сусідніх папілярів. Саме такі шуми можна забрати завдяки використанню узгоджуючих фільтрів. Фільтр є адаптивним оскільки він сам орієнтується відносно напрямку папілярів, а узгоджуючим оскільки він має збільшувати та робити чіткішим зображення папілярів на пальцях.
Після подавлення шумів проводиться виділення папілярів через бінаризацію зображення. Проблема бінаризації полягає у нерівноміному розподілу яскравості по площині зображення. Наприклад, той самий папіляр може мати більшу інтенсивність посередині зображення, оскільки там палець був сильніше притиснений до сканера. Тому зазвичай, для обробки такого зображення використовується порогова сегментація. Тобто для кожної окремо взятої частини зображення визначаєтсья свій поріг контрасту. Останнім етапом виконання обробки зображення перед розпізнаванням є векторизація папілярів. Тобто товщина кожного папіляра зводиться до товщини одного пікселя.
Узгоджуюча фільтрація та векторизація вносять левову частку в часові затрати. Результати всіх подальших етапів обробки залежать від якості початкового зображення, яке надалі буде оброблятись. Тому економія заради збільшення швидкості обробки зображення не завжди виправдана в таких випадках. Це призведе до погіршення результатів розпізнавання, що в свою чергу спричинить необхідність повторів верифікації системою або визнання даних некоректними.
Виділення ключових ознак відбитку для ідентифікації
В даному випадку під ключовими ознаками потрібно вважати закінчення (кінець) папіляру та його роздвоєння. Саме по цим ознакам буде проводитись ідентифікація особи .
Як би детально не було зображення опрацьовано на попередніх етапах, все одно залишаться надлишкові та некоректні роздвоєння, які не були усунені і є своєрідним зашумленням рисунку. Наприклад, два закінчення папіляра, які знаходяться дуже близько один біля одного швидше за все тепер будуть трактуватись як один суцільний папіляр, бо внаслідок зашумлення і не зовсім коректного аналізу він був розділений. Якщо знайдено дуже короткий папіляр, в якому відстань між його кінцями дуже коротка то це скоріш за все шум, який не буде братись до уваги і т.д.

Розпізнавання
На етапі розпізнавання відбиток який вимагає верифікації порівнюється з еталонним. Зазвичай таке розпізнавання робиться на основі порівняння сусідніх ознак на схожість. Кожна з таких ознак (тобто кінець папіляра або роздвоєння) містить три чи більше сусідніх ознак, кожна з яких знаходиться на певній відстані, та має певну орієнтацію відносно сусідніх ознак. Крім того, як уже зазначалось кожна ознака характеризується типом і напрямком, які теж порівнюються. Якщо в результаті розпізнавання виявляються дуже незначні відмінності між сусідніми ознаками на еталонному зразку і тому, який подано для верифікації, тоді вважається, що вони співпадають. Це проробляється для всіх ознак, і коли виявляється, що вони з заданою точністю співпадають тоді можна говорити про розпізнавання поданого на автентифікацію відбитку.
Результатом розпізнавання є виявлення кількості однакових ознак. Це число від 0 до n. Більша кількість співпадінь означає більшу ймовірність розпізнавання. Саме кількість співпадінь є мірою для встановлення порогової величини. Якщо ця кількість більша від порогової, тоді говорять про позитивну верифікацію, тобто відбитки відповідають еталонним, в іншому випадку це негативна верифікація. Значення порогу теж може коливатись. Є сенс збільшити порогове значення для підвищення надійності верифікації. Або відповідно навпаки – за зниженням порогової величини зменшується надійність верифікації і відповідно зменшується кількість неспівпадінь з еталоном.

Модифікації класичного підходу

Так як одна із найбільш складних задач обробки зображень відбитків пальців – це отримання чіткого зображення для виконання розпізнавання, є декілька методів її розв’язку. Більшість з цих методів використовують адаптивне розпізнавання окремих частин зображення [2,4,3]. Спочатку зображення розбивається на квадрати у яких визначаються характеристики папілярів та їх орієнтація. Орієнтація кожного участка визначається при обробці просторової чи частотної області виконанням двовимірного швидкого перетворення Фур’є.
Після бінаризації зображення, зазвичай виконується векторизація ліній папілярів. Однак існують методи обробки при яких етапи бінаризації та векторизації (обидва етапи вимагають значних обчислювальних витрат та можуть вносити шуми на зображення) опускаються. Є інший підхід, згідно з яким зображення папілярів отримуються з оригінального вхідного зображення в сірих тонах. Результатом є також зображення з виділеними кінцями та роздвоєннями на відбитку, як і в результаті традиційної обробки такого зображення. Розглянемо підхід детальніше.
Замість використання одного вікна(сегменту) для визначення розміщення та орієнтації папілярів використовується так званий мультивіконний режим, або режим мультирозширення [3]. Спочатку ведеться обробка зображення вибраного розміру. В ньому визначається орієнтованість папілярів, визначається наскільки чітко можна розрізнити кінці та роздвоєння. Якщо дане значення є меншим ніж визначений поріг, тоді дане вікно розділяється на чотири менші підвікна і те ж саме повторюється для кожного підвікна. Така процедура виконується до тих пір, поки отримане значення не стане більшим визначеного порогу для кожного підвікна. Цей метод використовується для уникнення згладжування на окремих частинах зображення, що дуже часто є характерним для центральної частини зображення.
Через значну складність порівняння характерних ознак на двох відбитках, порівняння сусідніх ознак, було одним з найдавніших способів розв’язку задачі [13]. Спочатку ознаки групувались за близькістю розташування одна до одної. Таких сусідніх ознак могло бути від двох до чотирьох. І кожна з них порівнювалась відповідно з ознаками на іншому відбитку, що значно спрощувало завдання. Існує два етапи такого розпізнавання. Спочатку розпізнавання ведеться всередині окремих частин на обох відбитках. Потім проводиться глобальне розпізнавання, тобто аналізується повністю весь відбиток – вхідний і еталонний.
Проте через трудомісткість таких операцій було запропоноване певне покращення цього методу. Для цього визначається положення центра та дельт. На рис.5 показаний приклад центру та дельти відбитка пальця.
Центр і дельти зазвичай визначаються виходячи з напрямку папілярів. Кращим методом для визначення окремих точок на такій площині є використання індексів Пуанкаре [8,7]. Для кожної точки на схемі розташування сумуються кути розміщення відносно замкненої кривої в напрямку за годинниковою стрілкою. Для не вироджених точок ця сума рівна нулю, для центра вона рівна 180 градусів, а для дельти до 180 градусів.
Для зменшення часу обчислень при розпізнаванні було запропоновано також ряд інших методів розпізнавання характерних ознак. Один з підходів пропонує спочатку провести співставлення, а потім розпізнавати ознаки (це особливо актуально для методів, коли порівняння необхідно проводити раз, а розпізнавання багато разів). Лінійний перелік ознак складається при скануванні. Спочатку вибирається середина, а потім від неї рухаються до країв по спіралі [16]. Таким чином одновимірні вектори, які містять характеристики кожної з ознак порівнюються на вхідному і еталонному відбитках. Іншим методом порівняння ознак є ступінчатий метод [10]. Будується граф атрибутів, в якому найближчі характерні ознаки сполучені ребрами, а вершинами є ознаки [9]. Ці вершини порівнюються на двох відбитках. Кількість співпадінь і визначає значення рівня ймовірності відповідності. Через такі незначні відмінності при порівнянні двох ознак розпізнавання може відбутись некоректно. Тому для кожної ознаки вводяться додаткові характеристики, такі як довжина та кривизна папіляра, на якому її виявлено та аналогічні характеристики по відношенню до сусідніх ознак.
Відбитки можна порівнювати і через кореляцію. Якщо бути точним, то кореляція двох зображень включає в себе трансляцію одного зображення в інше. Виконується мультиплікація відповідних пікселів [15]. Тому пара відбитків, які співпадають, буде мати вище кореляційне значення. Порогове значення класифікації визначає чи достатньою є величина відповідності для того щоб даний відбиток був визначений як розпізнаний.
Кореляційний аналіз можна проводити не лише в просторовій, а і в частотній області [11]. Першим кроком в такому випадку буде виконання двовимірного швидкого перетворення Фур’є (ШПФ) над вхідним та еталонним зображеннями. Відбувається перетворення зображення в частотну область. Потім виконується перемноження кожного з пікселів двох перетворених зображень, а сума цих перемножених результатів в частотній області і є еквівалентом кореляційного значення, яке отримується таким самим чином в просторовій області. Перевагою виконання такої обробки в частотній області є те, що відбитки стають незалежними при перетворенні, це означає що вони не повинні вирівнюватись з точки зору перетворення, оскільки початки координат для двох зображень є нульове значення частоти.
Кореляція в частотній області може виконуватись не лише цифровими засобами [14], а й оптичними системами. Це досягається використанням лінз та лазерного освітлення. При розкладанні призмою променя в частотний ряд, відбувається частотне перетворення. Аналогічним чином вхідне та еталонне зображення відбитків пальців пропускаються за допомогою лазерного світла через лінзу для виконання перетворення Фур’є. Їхні накладання спричиняють піки кореляції чиє значення є надзвичайно важливим при розпізнаванні відбитків. Перевагою такої оптичної обробки зображення є те, що швидкість операцій це і є по суті швидкість світла, що є значно швидшим, ніж швидкість обробки звичайними цифровими процесорами. В будь-якому випадку оптичні процесори не є настільки гнучко програмованими як цифрові, і в зв’язку з цим вони дуже рідко використовуються в комерційних проектах та системах.
Однією з модифікацій просторової кореляції є обробка не окремих пікселів самого зображення, а виконання операцій над рядками пікселів або над ознаками, які виявлені в даних рядках [5, 6]. Вхідне та еталонне зображення спочатку вирівнюються, а потім розділяються на частинки цими рядками. Характеристики папілярів визначаються для кожної частинки в рядку: середня інтенсивність кольору, напрям папіляра, частота, кількість папілярів у рядку. Відповідні частинки рядка порівнюються на наявність однакових ознак. Якщо значна частка ознак співпадає, тоді кажуть про високу ймовірність розпізнавання даного відбитка.
Кореляційний метод виконується швидше, особливо в системах, які виконують ШПФ на апаратному рівні. Проте він гірше справляється із зображеннями залежними від зовнішніх факторів та зашумленими зображеннями.
При проведенні верифікації відбитків пальців можна виділити наступні проблеми:
1. Зображення папілярів матимуть різні відповідні відображення. Можна встановити орієнтири такі як центр чи дельта, але якщо їх встановити чітко неможливо, тоді подальше розпізнавання не матиме сенсу.
2. На двох відбитках може бути різний кут повороту. Якщо на відбитку знайдено відповідний орієнтир, то можна спробувати обертати зображення для кращого співпадіння відносно цього орієнтиру. Проте, в процесі такої обробки можуть виникати помилки. А також в даному випадку будуть значні обчислювальні витрати через те, що кожен раз повертаючи доведеться знову обробляти ціле зображення.
3. Через те що шкіра є еластичною, відбитки можуть співпадати по розміщенню і напрямку, проте окремі частини, особливо з країв можуть не співпадати.
4. І нарешті, неминуча проблема зашумлення зображення. Два зображення для яких треба зробити розпізнавання можуть бути різної якості і зображення відбитків пальців могло бути зроблене за різних умов (температура, вологість шкіри) чи різними пристроями, тому вони можуть відрізнятись.

Степінь розпізнавання

Основна міра рентабельності систем розпізнавання, в кожному окремому випадку, це степінь розпізнавання. Це значення описується двома величинами. Кількість прийняття хибних результатів (false acceptance rate - FAR) - це кількість виявлених хибних співпадінь в співвідношенні до всіх виконаних порівнянь. Альтернативною величиною є неприйняття хибних результатів (false rejection rate - FRR) – це співвідношення кількості хибних неспівпадінь до загальної кількості порівнянь. Значення FAR та FRR можуть заміняти одне одного.
Тобто система врівноважується коливанням цих двох величин - збільшення одної величини призводить до зменшення іншої і навпаки. FAR по-іншому називають рівнем хибних співпадінь або помилкою другого рівня, а FRR називають рівнем хибних неспівпадінь або помилкою першого рівня. Обидві величини визначаються на проміжку від 0 до 1, або у відсотковому співвідношенні.
Крива ROC (робоча характеристика отримувача) будується на основі залежності FAR та FRR харатеристик. FAR відкладається на осі х як незалежна величина. По осі у відкладається залежна величина FRR. Вісь х є логарифмічною. На рисунку 6 зображено дві криві суцільними лініями і три пунктиром. Суцільні лінії не відображають конкретних даних, вони наведені для того щоб відобразити межі характеристик.
Процедура обрахунків за допомогою такої кривої є наступною. Вибирається достатній рівень величини FАR. Пунктирна лінія встановлена на 0,01% FАR. FRR, який відповідає даному значенню в даному випадку буде приблизно на рівні 4%. Можна визначати дані і в зворотному порядку, тобто визначати FАR за FRR.
Проте дані які обчислюють за даними кривими не є стандартними і однаковими для всіх програм розпізнавання. Наприклад у військовій промисловості значення FАR є дуже важливе, і його намагаються мінімізувати наскільки це можливо (навіть до 0,001%). Однак, це відбивається на значенні FRR. В такому випадку його величина може досягати значення навіть 5-20%.
Для ведення та збору статистичної інформації необхідна наступна інформація: кількість зразків, опис типу процедури верифікації. Розмір зразка може містити таку інформацію: кількість людей, кількість відбитків, кількість відбитків для кожного пальця. Крім того кількість співпадінь і не співпадінь має бути усереднена. Наприклад, база буде містити дані про 100 людей. В кожної людини було взято відбитки двох пальців, по 4 зображення для кожного пальця. Тобто загалом є 100х4х2=800 відбитків у базі. Якщо кожне зображення для кожного пальця (200) порівнювати із іншими зображеннями для того ж пальця отримаємо 1200 порівнянь відбитків. Якщо зображення одного відбитка порівнюється з усіма відбитками для інших пальців , тоді це буде 158400 порівнянь при розпізнаванні. Це говорить про неефективність існуючих методів. Якщо у базу даних помістити кілька мільйонів відбитків, то чекати результату доведеться дуже довго. Для зменшення кількості операцій верифікації, відбитки можна класифікувати і відповідно пошук проводити по розбитим групам.

Висновки

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

1. Lawrence O’Gorman, Veridicom Inc. “Fingerprint verification” 2000. 2. O. Nakamura, K. Goto, and T. Minami, “Fingerprint Classification by Directional Distribution Patterns,” Systems, Computers, and Controls, Vol. 13, pp. 81-89, 1982. 3. L. O'Gorman and J. V. Nickerson, “An approach to fingerprint filter design”, PatternRecognition, Vol. 22, No. 1, pp. 29-38, 1989. 4. E. Peli, “Adaptive Enhancement Based on a Visual Model,” Optical Engineering, Vol. 26, No. 7, pp. 655-660, 1987. 5. E. C. Driscoll Jr., C. O. Martin, K. Ruby, J. J. Russell, and J. G. Watson, “Method and Apparatus for Verifying Identity Using Image Correlation, 1991. 6. L. Coetzee and E. C. Botha, “Fingerprint Recognition in Low Quality Images,” PatternRecognition, Vol. 26, No. 10, pp. 1441-1460, 1993. 7. K. Karu and A. K. Jain, “Fingerprint Classification,” Pattern Recognition, Vol. 29, No. 3, pp. 389-404, 1996. 8. M. Kawagoe and A. Tojo, “Fingerprint Pattern lassification,” Pattern Recognition, Vol. 17, pp. 295-303, 1984. 9. M. A. Eshera and R. E. Sanders, “Fingerprint Matching System,”1997. 10. S. Ferris, R. L. Powers, and T. Lindh, “Hyperladder Fingerprint Matcher,” 1997. 11. R. C. Gonzalez and Richard E. Woods, Digital Image Processing, Addison-Wesley, Massachusetts, 1992. 13. K. Asai, H. Izumisawa, H. Owada, S. Kinoshita, and S. Matsuno, “Method and Device for Matching Fingerprints with Precise Minutia Pairs Selected from Coarse Pairs,”, 1987. 14. R. A. Marsh and George S. Petty, “Optical Fingerprint Correlator,” ,1991. 15. A. Sibbald, “Method and Apparatus for Fingerprint Characterization and Recognition Using Auto-correlation Pattern,” 1997. 16. M. K. Sparrow, “Fingerprint Recognition and Retrieval System,” 1988.