ШАДХІН В. Ю.,ГОГУ Л. О., КАРАКАТ В. Ю.

Київський національний університет технологій та дизайну, Україна

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

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

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

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

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

Така реалізація дозволяє зменшити час виконання оцінок по топології та геометрії в середньому в 1,8 рази при обчисленні на 2 потоках та в 3,5 рази на 4 потоках.

Алгоритм обчислення ступені подібності шаблонів ДЗ складається з наступних основних етапів:

- вибір однойменних зв’язків;

- оцінка ступеня подібності векторів за геометрією;

- оцінка ступеня подібності векторів за типологією;

- комплексна оцінка ступеня подібності векторів;

- оцінка ступеня подібності шаблонів.

На рис. 1 представлена загальна схема ступеня подібності векторів за геометрією, а на рис. 2 – за типологією.

Рисунок 1. Алгоритм оцінки векторів за геометрією

На етапах, виділених пунктиром, використовується паралельна обробка даних, що містить часткові ознаки зображення і зв’язку між ними, причому кожен крок обчислюється незалежно від інших. Паралельне обчислення забезпечується технологією OpenMP [6].

Рисунок 2. Алгоритм оцінки векторів за топологією

Загальна оцінка за топологією виконується на основі обчислювальних оцінок подібності за топологією для кожної пари випадків e_lⁱ, e_l^j. Після оцінки за топологією виконується прив’язка за індексами точок групи. Щоб уникнути утворення вузьких місць використовують:

- організацію паралельної обробки на вузькій частині за допомогою технології OpenMP;

- прив’язку за індексами суміщають з оцінкою за топологією.

Модифікований алгоритм показує кращу продуктивність, але через нерівномірне розподілення циклів і нециклічних розділів коли між потоками спостерігається і пониження продуктивності. Для подолання зазначених недоліків необхідно використовувати основну перевагу OpenMP: єдиний адресний простір для усих потоків, що задіяні в одному процесі.

Література

1. Андреев Н. Е. Методы автоматизированного анализа производительности параллельных программ // Вестник Новосибирского государственного университета. – 2009. – Т. 7, вып. 1. – С. 16-25.

2. Арутюнян А.Р. Методы и алгоритмы анализа и синтеза деформаций дактилоскопических изображений: автореферат дис. … канд. техн. наук / М: Цифровичок, 2010. – 18 с.

3. Гордеева Д.Н., Гудков, В.Ю. Распознавание дактилоскопических изображений // Вестник МГТУ. Серия «Приборостроение». Специальный выпуск «Биотехнологии». – 2011. – С. 47–58.

4. А.С. Боков, В.Ю. Гудков. Пат. 2185660 Российская Федерация, МПК G06K 9/52. Способ кодирования отпечатка папиллярного узора – № 2000118065/09; заявл. 07.07.2000; опубл. 20.07.2002; Бюл. № 20. – 13 с.

5. Ушмаев О.С. Проблемы распараллеливания биометрических вычислений в крупномасштабных информационных системах // Информатика и ее применения, т.3, вып. 1. – 2009. – С. 8-18.

6. OpenMP Tutorial. URL: https://computing.llnl.gov/tutorials/openMP/