Обзор литературы Режимы работы биометрических систем
|
Скачать 250.76 Kb.
|
Алгоритмы обработки отпечатков пальцевВ соответствии с ранее рассмотренной структурой биометрической системы выделяют следующие группы алгоритмов:
Следует отметить, что многие алгоритмы являются взаимозаменяемыми в том смысле, что при согласовании входных и выходных данных их можно заменять на другие. К ним относятся, например, алгоритмы первой группы, принимающие и возвращающие двумерное растровое изображение, а также алгоритмы извлечения минуций из изображения. Алгоритмы улучшения изображенияПонятие качества отпечатка формализовано Национальным институтом стандартов и технологий США в концепции NFIQ [ссылка]. Алгоритмами оцениваются различные характеристики изображения, показатели которых подаются на вход нейронной сети. Её ответом является число от 1 (превосходное качество) до 5 (очень плохое качество). Среди исследуемых характеристик присутствуют, например, наличие шрамов или порезов, степень жирности и сухости кожи, чёткость папиллярных линий и т.д. На практие этот стандарт не всегда оказывается эффективен, так как разные участки отпечатка могут обладать разным качеством. В [Джейн] приводится алгоритм, согласно которому на отпечатке можно выделить регионы, которые не нуждаются в улучшении, регионы с восстановимым папиллярным узором и невосстановимые регионы. Для первых двух категорий могут применяться алгоритмы улучшения изображения. Попиксельные алгоритмы [Хэндбук, с.133] используют для улучшения статистическую информацию об изображении, в частности, среднюю интенсивность пикселов и их среднеквадратичное отклонение. На основании этой информации интенсивности пикселов пересчитываются к желаемым значениям среднего и среднеквадратичного отклонения, что позволяет сделать папиллярные линии более чёткими, однако не устраняет такие структурные недостатки, как размытые границы между разными линиями и небольшие разрывы, не являющиеся истинными минуциями. Для преодоления этих ограничений используются алгоритмы контекстной фильтрации, основанные на извлечении информации из области вокруг каждого пиксела и выборе того или иного действия на её основе. Например, в [Джейн Габор] изображение делится на блоки, и в каждом из них оценивается ориентация папиллярных линий и расстояние между соседними гребнями. На основе этой информации из набора заранее подготовленных выбирается конкретный фильтр Габора с наиболее близкими к полученым частотой и направлением. Свёртка с таким фильтром позволяет сделать более контрастными линии в выбранном направлении и, наоборот, снизить интенсивность остальных. Существуют также алгоритмы, улучшающие изображения с помощью преобразования Фурье [хэндбук 139], дискретного косинусного преобразования [там же], а также на основе анализа матрицы вторых моментов в различных разрешениях исходного изображения [Бигун!!!] Алгоритмы выделения отличительных особенностей Как будет показано далее, большинство алгоритмов сопоставления используют минуции в качестве отличительных характеристик отпечатка пальца. Алгоритмы выделения минуций из изображения отпечатка подразделяются по тому, с каким изображением они работают – двухцветным (чёрно-белым) или в оттенках серого. Существует несколько алгоритмов получения двухцветного изображения отпечатка пальца из исходного. Самый простой – присваивать белый цвет пикселам со значением выше некоторого глобального порога и чёрный – ниже его. Этот способ не принимает во внимания «контекст» пиксела (находится ли он на гребне или на впадине, и т.д.), что может приводить к недостаточно точным результатам в отпечатках плохого качества. Более сложные алгоритмы используют локальный порог, то есть такой порог, значение которого изменяется в зависимости от окрестности пиксела. Например, в [Moayer and Fu 1986] предлагается алгоритм, основанный на итеративном применении к изображению оператора Лапласа и сравнению его с двумя динамически изменяющимися порогами. Каждому пикселу, который после свёртки оказался за пределами интервала, ограниченного двумя порогами, присваивается в зависимости от области, в которой он оказался, чёрный или в белый цвет. После каждой итерации пороги сдвигаются в сторону уменьшения интервала, что приводит к сходимости алгоритма. Другой алгоритм основан на выделеннии границ между гребнями и впадинами [Coetzee Botha 1993], где отнесение пикселов к гребню происходит в результате сравнения с локальным порогом, полученным по результатам анализа окрестностей как на исходном изображении, так и на изображении границ. Другие исследователи показали высокую эффективность метода бинаризации, основанного на выборе для каждого пиксела локального порога на базе пикселов изображения, спроецированных на линию, перпендикулярную ориентации гребней по координатам исходного пиксела [Ratha Chen Jain 1995]. Другие алгоритмы изложены в [и 100500 ссылок]. После бинаризации производится утончение линий, соответствующих гребням, до толщины в один пиксел. Обзор таких алгоритмов представлен в [ссылка брыксинской девочки]. Утончённое таким образом изображение отпечатка позволяет находить координаты минуций с помощью простого подсчёта числа соседних чёрных пикселов вокруг каждого чёрного пиксела пиксела (рис.): - Если оно равно 1, то пиксел – окончание линии - Если оно равно 2, то пиксел – промежуточный участок линии - Если оно равно 3, то пиксел – разветвление линии - Если оно больше 3, то в координатах пиксела находится более сложная минуция (например, ветвление на три линии) Рис. Минуции и промежуточные участки гребней на утончённом изображении При этом направление минуции определяется с помощью поля ориентаций и отслеживания расходящихся от минуции линий, хотя общепринятого алгоритма его определения к настоящему моменту нет. Достоинством такого подхода является возможность его эффективного распараллеливания [Говришанкар]. Другие алгоритмы основаны на анализе окрестностей пикселов нейронными сетями [Leung 1991], движению вдоль гребней исходного бинаризованного изображения с отслеживанием ситуаций ветвления и окончания [Weber 1992, Shi Govindaraju 2006], а также специальных операторах, способных распознавать нарушения непрерывности линий, связанных с минуциями [Székely 1993]. Алгоритмы извлечения минуций из изображений в оттенках серого как правило основаны на некоторых эвристиках. Например, в [Maio, Maltoni] для нахождения минуций предлагается выбрать первоначальную точку на папиллярной линии, выбрать первоначальное направление (например, по полю ориентаций) и двигаться вдоль линии в выбранном направлении с дискретным шагом, корректируя направление после каждого шага по отклонению максимально тёмного пиксела на линии, перпендикулярной текущему направлению, от центра. Алгоритм остановится и перейдёт к следующим точкам в следующих случаях: линия окончилась (найдена минуция), линия разветвилась (найдена минуция и две новых стартовых точки), все линии в отпечатке пройдены (для учёта пройденных линий строится вторичный двумерный массив). В то же время другие алгоритмы основаны на фундаментальных особенностях отпечатков пальцев. В [Бигун!!! И КОллрайдер] для определения координат и направления минуций используются свойства структурного тензора. Было обнаружено, что метрика, основанная на определении линейной симметрии и комплексных моментах структурного тензора в каждом пикселе изображения, имеет малые по модулю значения в точках, где находятся разветвления и особенно окончания линии. Более сложная метрика была использована для более точного нахождения ветвлений. Алгоритмы сопоставления шаблоновЗадача сопоставления отпечатков по минуциям формулируется следующим образом [ссылка]. Предположим, что множества минуций для сравниваемого отпечатка и отпечатка из базы – это {(xn, yn, n)} с числом элементов N и {(xm, ym, m)} с числом элементов M соответственно, где n = 1, 2, … , N, m = 1, 2, … , M, (xn, yn) и (xm, ym) – координаты минуций, n – направление минуции. Отпечаток пальца может быть подвергнут обычным геометрическим преобразованиям: повороту, параллельному переносу и масштабированию. В результате этих преобразований из множества минуций {(xn, yn, n)} получается множество {(x’n, y’n, ’n)}, где где s – коэффициент масштабирования, – угол поворота, – значения параллельного переноса по оси абсцисс и ординат соответственно. Эти значения называются параметрами выравнивания. Полученное множество минуций сопоставляется с множеством минуций отпечатка в базе. Считается, что две минуции сопоставлены, если выполнены следующие условия: где Td – порог сопоставления по расстоянию между минуциями, Ta – порог сопоставления по углам между минуциями. Такое сопоставление производится независимо для всех несопоставленных минуций целевого отпечатка, а потому может быть эффективно распараллелено [Джейн, Прабакар]. Цель сопоставления в такой формулировке – найти значения , ,, максимизирующие число пар сопоставленных минуций. Пары сопоставленных минуций образуют отображение из некоторого подмножества минуций предоставленного отпечатка в подмножество минуций отпечатка из базы. Большинство алгоритмов формируют биективное отображение, однако в общем случае это необязательно. Так как разные шаблоны могут состоять из различного числа минуций, сравнивать абсолютное количество минуций некорректно. Вместо этого с порогом сопоставления сравнивают степень сходства, рассчитываемую как , где К – число сопоставленных пар. Исторически первыми алгоритмами сопоставления шаблонов отпечатков пальцев были алгоритмы глобального сопоставления минуций. К тривиальным алгоритмам можно отнести перебор значений параметров выравнивания из некоторого диапазона с заданным шагом дискретизации, а также перебор параметров выравнивания, полученных из наложения каждой минуции рассматриваемого отпечатка на все минуции отпечатка из базы [ссылка]. На элементах алгебраической геометрии основан подход в [Udupa 2001]. Для каждого множества минуций формируется множество векторов , и параметры выравнивания определяются путём накладывания друг на друга векторов с разницей в длине меньше некоторого порога, после чего определяется консистентность лучших 10 сопоставлений. Ряд методов работают на основе обобщённого преобразования Хафа [Ratha 96 Chang 97], отмечается высокая степень параллелизма этого процесса [Ratha Jain 95]. Так как скорость работы этих алгоритмов напрямую зависит от размера диапазона параметров выравнивания, предложено несколько методов предварительного выравнивания, направленных на его уменьшение. Предварительное выравнивание может быть абсолютным (например, нахождение в одной и той же точке изображения ядер всех отпечатков, ориентированных определённым образом [Bazen Gerez 2002]) или относительным (производится наложение координат некоторых особенностей распознаваемого отпечатка на координаты этих же особенностей отпечатка из базы). Относительное выравнивание меньше зависит от качества и типа узора отпечатка, а потому применяется чаще. Предлагается, например, выравнивать отпечатки по положению ядер и дельт, если они могут быть найдены [Бигун!!!], по сопоставленнным полям ориентаций [Бигун!!! Yager Amin 2004] или по сопоставимым по кривизне и длине отрезкам папиллярных линий [Jain, Hong Bolle 1997]. Алгоритмы глобального сопоставления плохо работают с отпечатками, подвергшихся эластичным деформациям, так как они приводят к существенным отличиям в расстоянии и ориентации минуции относительно некоторой исходной от отпечатка к отпечатку. Новым этапом развития стали алгоритмы локального сопоставления. В них непосредственно сопоставление осуществляется не над всем множеством минуций, а над некоторыми структурами, образованными, как правило, близко расположенными друг относительно друга минуциями. После шага сопоставления производится этап объединения локальных результатов, в результате которого делается вывод о принадлежности или непринадлежности отпечатков одному и тому же образцу. Локальные структуры могут быть основаными на ближайших соседях (тройки, образованные минуцией и её двумя ближайшими соседями [Jiang Yau 2000]), на соседях в определённом радиусе (звёзды, образованные всеми соседями минуции в некотором радиусе [Ratha 2000]), треугольниками минуций [Tan Bhanu 2003a] или основанными на информации о папиллярном узоре вокруг минуции (вектор относительных ориентаций, взятых в определённых точках на концентрических окружностях с центром в самой минуции [Tico Kuosmanen 2003]). Шаг объединения может заключаться либо в глобальном сопоставлении на основе параметров выравнивания, полученных из сопоставленных пар локальных структур [ссылки], либо в нахождении степени консистентности всех получаемых таким образом параметров выравнивания [ссылки]. Одним из наиболее современных алгоритмов локального сопоставления является алгоритм MCC (Minutiae Cylinder-Codes) [MCC]. Первым шагом алгоритма является построение структуры данных, называемой цилиндром, для каждой минуции шаблона. Цилиндр – это линеаризованное представление трёхмерного кубоида, у которого две координаты соответствуют разнице в координатах относительно исходной минуции, а а третья – дискретизованной разнице в направлениях. Зачения ячеек кубоида составляются из суммы метрики по каждой из минуций – минуция имеет тем большую метрику, чем ближе разница её координат и направления относительно исходной к координатам ячейки. Сопоставление цилиндров осуществляется путём представления значений ячеек как координат в многомерном пространстве и вычисления евклидового расстояния. Цилиндры могут быть тажке бинаризованы путём сравнения значений ячеек с порогом, что позволяет использовать эффективные битовые вычисления. Результатом сопоставления отдельных цилиндров является матрица индивидуальных сопоставлений, которая является основой для шага объединения. Объединение происходит путём определения средней схожести лучших сопоставлений с повторами цилиндров либо без повторов, в последнем случае для определения лучших сопоставлений используется венгерский алгоритм. Для более точных результатов к матрице может применяться процедура релаксации. |
Похожие:
 |
«Обзор современной литературы» Новолакской гимназии в рамках Года Культуры состоялась читательская конференция учащихся 10-11 классов на тему: «Обзор современной... |
|
Тема: обзор литературы Краткий обзор литературы по теме должен показать основательное знакомство начинающего исследователя со специальной литературой, умение... |
 |
Обзор особенностей работы в условиях указанной технологии Описание... Выбор оборудования, обзор возможностей и технических характеристик выбранного оборудования |
|
Реферат по дисциплине: «Операционные системы» на тему «Режимы работы... По числу одновременно выполняемых задач операционные системы могут быть разделены на два класса |
|
Краткое содержание справочника Даны рекомендации специалистов по выбору газовых, электрических, универсальных котлов и комплектующих. Дан обзор систем солнечного... |
|
«Психосоматический подход к депрессивным расстройствам». Обзор литературы. Диков С. Ю |
|
Реферат 7 введение 8 обзор программного обеспечения для работы приемной... Пакеты программ для автоматизации работы приемной комиссии на базе системы «1С: Предприяти8» |
|
Петербургский Государственный Университет о распаллеливании дактилоскопических алгоритмов В настоящее время достигнуто такое значение far, как, что свидетельствует о высоком уровне развития разрабатываемых биометрических... |
|
Определения и сокращения 2 введение 3 1 аналитический обзор литературы 5 Математические модели, положенные в основу разрабатываемого проекта, и теоретические исследования 17 |
|
Мероприятия Ответственный Сроки 1-я четверть I. Обзор методической литературы Систематическое ознакомление и изучение отдельных вопросов журнала «Дефектология» |