Кластеризация эталонов радужки для оптимизации поиска в больших базах

Тип работы:
Реферат
Предмет:
ТЕХНИЧЕСКИЕ НАУКИ


Узнать стоимость

Детальная информация о работе

Выдержка из работы

БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Ting Chen. Video Stabilization Algorithm Using a Block-Based Parametric Motion Model. Winter 2000, Stanford University. — P. 3−4
2. Бондаренко С., Бондаренко М. Создание 3Б-изображений: теория и практика [Электронный ресурс] // Сайт проекта 3Domen. 2011, 27 февраля. URL:
http: //3domen. com/index. php? newsid=5794 (дата обращения 26. 07. 2012.
3. Jesse S Jin, Zhigang Zhu, Guangyou Xu. Digital Video Sequence Stabilization Based on 2. 5D Motion Estimation and Inertial Motion Filtering. IEEE International Conference on Intelligent Vehicles (2001) Volume 7, Issue 4, pp. 357−365.
4. .,.. web- -
//:: материалы XI Международной научно-методической конференции, Воронеж, 10−11 февраля 2011 г.: В 3-х т. — Воронеж: Изд-во Воронежского государственного университета, 2011. — Т. 2. — С. 229−232.
5. Takeo Kanade, Masatoshi Okutomi. A stereo matching algorithm with an adaptive window: theory and experiment // IEEE Transactions on Pattern Analysis and Machine Intelligence. — Sep. 1994 — P. 920−932.
6. Eddy Vermeulen. Real-time Video Stabilization For Moving Platforms. 21st Bristol UAV Systems Conference — April 2007.
Статью рекомендовал к опубликованию к.ф. -м.н., доцент НА. Тюкачёв.
Протасов Станислав Игоревич — Воронежский государственный университет- e-mail: stanislav. protasov@gmail. com- 394 062, Воронеж, ул. Южно-Моравская, 16, кв. 73- тел.: +79 167 434 994- факультет компьютерных наук- кафедра цифровых технологий- аспирант.
— e-mail: aakryl@sc. vsu. ru-
— -. -. .-.
Protasov Stanislav Igorevich — Voronezh State University- e-mail: stanislav. protasov@gmail. com- 16, Yuzhno-Moravskaya street, apt. 73, Voronezh, 394 062, Russia- computer science faculty- the department of digital technologies- postgraduate student.
Krylovetsky Alexander Abramovich — e-mail: aakryl@sc. vsu. ru- computer science faculty- the department of digital technologies- cand. of phis. -math. sc.- associate professor.
Кургалии Сергей Дмитриевич — e-mail: kurgalin@bk. ru- факультет компьютерных наук-
-. -. -. .-.
Kurgalin Sergey Dmitrievch — e-mail: kurgalin@bk. ru- computer science faculty- the department of digital technologies- head of department- dr. of phis. -math. sc.- associate professor.
УДК 004. 93'14, 51−76, 57. 087. 1
ИЛ. Симоненко, И.А. Матвеев
КЛАСТЕРИЗАЦИЯ ЭТАЛОНОВ РАДУЖКИ ДЛЯ ОПТИМИЗАЦИИ ПОИСКА В БОЛЬШИХ БАЗАХ*
В работе биометрических систем распознавания можно выделить два этапа: определение биометрических признаков (так нназываемого эталона) и сравнение полученного эталона с ранее зарегистрированными, содержащимися в базе данных. Для больших баз сравнение может занимать значительное, неприемлемое время. В работе предложен способ уменьшения времени поиска путём кластеризации некоторой выборки эталонов ра-
* Работа выполнена при финансовой поддержке РФФИ (проект № 12−07−778-а). 148
.
базы эталонов для сравнения, лучший по сравнению с прямым перебором. В тестах, проведённых на доступных базах изображений радужек, применение метода позволило сократить количество сравнений в 1,5−2,5раза.
Распознавание по радужке- кластеризация.
I.V. Simonenko, I.A. Matveev
CLUSTERING OF IRIS TEMPLATES FOR OPTIMIZING MATCHING AGAINST BIG DATABASES
Biometric identification system workflow can be split into two stages: determining biometric features (i.e. template) and matching this template against previously registered ones contained in database. The matching against big databases can take considerable, unacceptable time. A way of reducing matching time is proposed by means of clustering some group of template samples. The clusters break the space of templates into parts and yield an order of fetching of templates for matching, which is better than default straightforward fetching. In the tests, applying the method to public domain iris images resulted in reduction of number of comparisons in 1. 5−2.5 times.
Iris identification- clusterization.
. -
ции (в том числе по радужке глаза) доказали свою применимость для задач кон-[1]. -
екты с участием биометрического распознавания [2]. Принципиальным моментом развития таких систем является возрастание их масштаба, а именно, увеличение количества зарегистрированных персон. Уже существует потребность в биометри-
, 100 [3].
Процесс распознавания по радужке состоит из следующих основных этапов: регистрация изображения- выделение информативной области- получение признаков, характерных для индивида и инвариантных к условиям регистрации, в совокупности называемых биометрическим эталоном- поиск в базе. Вычислительная сложность и время исполнения первых трёх этапов не зависят от размера базы. Послед-
ний этап в большинстве существующих реализаций — это полный перебор эталонов (,), -,.
(т.е. метрики в пространстве эталонов) зависит от природы эталона- так, для IrisCode [4].
на основе спектрального преобразования Хаара, и использовалось евклидово расстояние для компонент спектра из определённого диапазона частот.
Для баз размером тысячи и более эталонов этап поиска становится основным по времени вычисления, которое линейно возрастает с увеличением количества эталонов в базе. Для систем распознавания, работающих на основе IrisCode, был разработан метод быстрого поиска FFS [3]. В работе [5] проводится грубая классификация изображений радужки на 4 класса путем определения фрактальной
. [6]
,.
. -лона исходно можно проводить двумя разными путями: 1) уменьшение времени
— 2), -бора, а значит требующего меньшего количества сравнений. В работе исследовался второй подход. Для достижения поставленной цели была сделана попытка кластеризовать пространство изображений радужки так, чтобы для предъявленного эталона можно было вычислить, к какому классу он принадлежит и производит
поиск только по элементам этого класса. Для разбиения множества эталонов на классы использовался иерархический аггломеративный метод кластеризации [7]. Для определения межкластерного расстояния экспериментально был выбран метод дальнего соседа (расстоянию между кластерами присваивается максимальное значение попарных расстояний между элементами двух кластеров), так как он порождает наиболее сбалансированное распределение по классам.
В результате проведения иерархической кластеризации получается последовательность шагов объединения кластеров, и возрастающих расстояний между объединяемыми кластерами на каждом шаге. По этим данным можно построить зависимость количества кластеров k от порогового расстояния между кластерами T. По этой зависимости можно определить, при каких значениях k при очередном слиянии происходит резкое увеличение расстояния T. Эти значения можно использовать для выбора уровня кластеризации естественного для данной выборки. К сожалению, при такой кластеризации не удаётся добиться того, чтобы несколько изображений одной и той же радужки гарантированно попадали в единст-., ,, попадают эталоны одной персоны, существенно меньше как общего количества, .
1
Распределение персон по количеству содержащих классов
Число классов, в которые попадает персона 1 2 3 4 5 & gt-5
Доля персон, эталоны которых распределились по данному числу классов 0,52 0,25 0,14 0,05 0,03 0,01
Распознавание нового эталона при сравнении таким образом в кластеризованной базе состоит из нескольких шагов. На первом шаге эталон сравнивается с классами (с типичными их представителями или иным методом) для того, чтобы определить наиболее близкий класс (т.е. тот, который с наибольшей вероятностью
,). -вый эталон сравнивается с представителями этого класса. Если достаточного для распознавания сходства не получено, то производится выбор второго по порядку наиболее близкого класса и перебор элементов из него.
Пусть N — количество эталонов в базе, k — количество классов. Введём ограничение: каждая персона представлена одинаковым количеством эталонов m.
[8, 9], ,
всегда одинакового числа эталонов при регистрации персоны представляется.
()., , ш = 20, персона «А» встречается в трёх классах, в одном из них 14 раз, во втором — 5, в третьем — 1, что даёт частоты рА = (0,7- 0,25- 0,05- 0,…) — персона «В»
— 20 раз в одном классе рв =(1−0-…) — персона «С» — 16 раз в одном и ещё по
разу в 4 классах рс = (0,8- 0,05- 0,05- 0,05- 0,…)
порядковых распределений по всем людям получим общее распределение рЕ. Для базы эталонов трёх персон «А», «В», «С» компоненты этого распределения будут рЕД =(0,7 +1 + 0,8)/3 = 0,833, рЕ2 =(0,25 + 0 + 0,05)/3 = 0,1,
рЕ3 =(0,05 + 0 + 0,05)3 = 0,033 и т. д. Таким образом рЪ1 — это вероятность того, что эталон будет найден в I-м по порядку перебора классе.
Общее время поиска складывается из времени, затрачиваемого на ранжирование классов: ktcl, где tcl — время сравнения эталона с классом, и последовательных переборов классов, с учётом вероятностей наступления этих событий. Обозначим qcl — вероятность ошибки при сравнении нового эталона с классом (выбран не класс, содержащий максимальное число эталонов человека, а другой). Эта величина близка к ошибке первого рода (не узнан свой) при сравнении эталонов. Метод кластеризации по ближайшему соседу создаёт примерно равные классы,
поэтому число элементов класса = -. В первом выбранном классе (если не про-
k
изошла ошибка) содержится в среднем р? — элементов нужного класса, и сред, k
нее время перебора до первого из этих элементов можно оценить как г = mini------------, — & gt-. Будем полагать, что первый же встреченный элемент
1 [(m + 1) рЕД' kJ
распознан. В этом случае первый класс обрабатывается за время (l — qd) rltel, где
td — время сравнения двух эталонов. В случае, если произошла ошибка и класс не содержит максимального числа элементов, время перебора будет больше. Поло-(),
, (
-
q i -tel), а затем начать обработку второго класса. Таким образом, время, затра-c k е чиваемое на поиск:
t& lt-ktcl + (1 -qd)ritel + qd ke + (1 -qcl)це1 + qd[^tei + (1 -qd)rKl+… j
В случае непосредственного перебора (без разбиения на классы) получим частный случай при k = 1: qcl = 0, рЪ1 = 1, t = - (m +1).
.
изображений радужек. Первая (BATH) включает в себя по 20 снимков левого и правого глаза для 300 человек, то есть 600 уникальных глаз [8]. Вторая (CASIA) содержит снимки 1000 людей, по 10 изображений для каждого глаза [9].
Был поставлен эксперимент, моделирующий применение системы в реальной жизни. Под этим в первую очередь понимается то, что в ходе эксплуатации системы в неё могут добавляться новые люди, и при этом кластеризация не должна про., ,, -тификации может быть зарегистрирован новый человек, а, с другой стороны, пока, -бражений можно проводить лишь на некоторой выборке, что критично для сверх,
провести за приемлемое время.
Эксперимент ставился следующим образом: кластеризация проводилась для выборки из 300 человек по 5 изображений на каждого. После чего оставшиеся изображения распределялись по классам. Вычислялись центры классов, которые считались далее их представителями, используемыми при ранжировании. После чего для всех оставшихся эталонов базы производился поиск описанным методом и подсчитывалось число сравнений. Также производился поиск прямым перебором. Коэффициент ускорения определялся как отношение числа сравнений, потребовавшегося в этих двух случаях.
2
Результаты моделирования
База Обучающая выборка Число распознаваемых изображений Число кластеров Коэффициент ускорения
BATH 100×5 100×20 29 1. 62
BATH 300×4 300×20 59 2. 29
CASIA 300×5 1000×10 42 2. 61
. -
нии биометрических эталонов путём кластеризации базы эталонов. На базах данных радужки глаза показано, что эталоны действительно кластеризуются таким образом, что один человек попадает в малое число классов (не больше 5). Предложен способ распознавания, состоящий из выбора наиболее похожего класса и перебора элементов в нём в первую очередь. Поставлен вычислительный экс пер и,, .
БИБЛИОГРАФИЧЕСКИЙ СПИСОК
1. Pato J.N., Millett L.I. Biometric recognition: challenges and opportunities // National Research Council: Whither Biometrics Committee. — 2010.
2. Future Challenges based on the Multiple Biometric Grand Challenge // NIST Information Access Division: Multiple Biometric Grand Challenge. — February 2010. — Web: http: //face. nist. gov.
3. Hao F., Daugman J., Zielinski P. A fast search algorithm for a large fuzzy database // IEEE Trans. Information Forensics and Security. — № 3 (2). — P. 203−212.
4. Daugman J. How iris recognition works // IEEE Trans. CSVT 14(1). — P. 21−30.
5. Yu L., Wang K., Zhang D. Coarse Iris Classification Based on Box-Counting Method // Proc. IEEE ICIP 2005. 11−14 September. — Vol. 3. — P. 301−304.
6. Vatsa M., Singh R., Noore A. Improving Iris Recognition Performance Using Segmentation, Quality Enhancement, Match Score Fusion, and Indexing // IEEE Trans. SMC. B-Cybern.
— 2008. — № 38 (4). — P. 1021−1035.
7. Ким Дж. -О., Мьюллер Ч. У., Клекка У.P., Олдендерфер М. С., Блэшфилд Р Ж. Факторный,
/.. . — .: —
, 1989. — 215.
8. Monro D. University of Bath Iris Image Database. 2005. http: //www. bath. ac. uk/eleceng/ research/sipg/irisweb/.
9. Chinese academy of sciences institute of automation (CASIA), CASIA Iris image data-base. 2005. http: //www. cbsr. ia. ac. cn/IrisDatabase. htm.
Статью рекомендовал к опубликованию д.ф. -м.н., профессор В. И. Цурков.
Матвеев Иван Алексеевич — Федеральное государственное бюджетное учреждение науки Вычислительный центр им. А. А. Дородницына Российской академии наук- e-mail: matveev@ccas. ru- 119 333, г. Москва, ул. Вавилова, 40- тел.: 84 991 352 489- отдел сложных -. -. .-..
Симоненко Иван Владимирович — Московский физико-технический институт (государственный университет) — e-mail: matveev@ccas. ru- 119 333, г. Москва, ул. Вавилова, 40- тел.: 84 991 352 489- -.
Matveev Ivan Alexeevich — Institution of Russian Academy of Sciences Dorodnicyn Computing Centre of RAS- e-mail: matveev@ccas. ru- 40, Vavilov street, Moscow, 119 333, Russia- phone: +74 991 352 489- the department of complex systems- head of sector- cand. of phis. -math. sc.
Simonenko Ivan Vladimirovich — Moscow Institute of Physics and Technology- e-mail: matveev@ccas. ru- 40, Vavilov street, Moscow, 119 333, Russia- phone: +74 991 352 489- the department of complex systems- postgraduate student.

ПоказатьСвернуть
Заполнить форму текущей работой