Способ верификации и идентификации отпечатков папиллярных узоров

Изобретение относится к области биометрии, а именно к способам распознавания и кодирования отпечатков папиллярных узоров, и может быть использовано в различных областях информационных технологий. Техническим результатом является повышение быстродействия сравнения и идентификации отпечатков папиллярных узоров при сохранении высокой достоверности результатов распознавания. Указанный технический результат достигается за счет того, что формируют паспорта отпечатков пальцев, осуществляют сравнение эталонных паспортов отпечатков пальцев и предъявленного паспорта путем сопоставления минуций. Одновременно с формированием паспортов отпечатков пальцев осуществляют фильтрационное кодирование изображений отпечатков пальцев, заключающееся в многократной математической обработке изображения папиллярного узора. При фильтрации изображения может быть использован фильтр Габора. 2 з.п. ф-лы, 7 ил.

 

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

Идентификация личности с помощью биометрических технологий является в настоящее время одним из перспективных, бурно развивающихся направлений, среди которых методы и средства, использующие отпечатки пальцев, занимают одно из ведущих мест.

Известен способ определения высоты дугового узора, предназначенный для распознавания папиллярных узоров отпечатков пальцев (см. патент РФ №2204941, МПК 7 А61В 5/117, опубл. 27.05.2003). Способ заключается в выявлении наиболее изогнутой папиллярной линии дугового узора, разметке этой линии, измерении угла ее изгиба и отнесении полученного значения угла изгиба к общепринятой в дерматоглифике категории высоты папиллярного узора. Способ позволяет косвенным путем определить высоту дугового папиллярного узора через измерение угла изгиба наиболее изогнутой папиллярной линии и использовать этот показатель в качестве характеристики данного типа папиллярных узоров.

Достоинством рассмотренного способа является высокая скорость кодирования. Однако существенным недостатком известного технического решения является невысокая точность кодирования, основанного на косвенном методе, а следовательно, и ненадежность распознавания, особенно при плохом качестве сравниваемых отпечатков.

Известен способ распознавания и кодирования отпечатков папиллярных узоров (см. патент РФ №2059979, МПК 6 G06K 9/00, опубл. 10.05.1996), заключающийся в сканировании изображения папиллярного узора, выделении характерных признаков изображения с последующим их кодированием, формировании массива выделенных характерных признаков и сравнении их кодов с кодами выделенных характерных признаков сравниваемых отпечатков папиллярных линий. Отличительной особенностью известного способа является то, что при формировании массива выделенных характерных признаков определяют направление потока папиллярных линий в окрестности точки, соизмеримой с межгребневым расстоянием, производят сглаживание картины потоков заменой значения направления потока на среднее из значений направлений потоков соседних точек, определяют вероятное положение характерных признаков папиллярного узора, определяют функции характерных признаков папиллярного узора и производят последовательное вычленение характерных признаков папиллярного узора, начиная с признака с максимальным значением весовой функции. Таким образом, в известном способе успешно решается не только задача определения положения особенностей, но и задача определения вероятности того, что определена именно особенность, а не точка шума. Это дает возможность использовать только те особенности, которые удовлетворяют определенному критерию точности при заданном уровне вероятности, а не использовать сомнительные особенности. Способ характеризуется сравнительно высоким быстродействием. Однако недостатком известного способа является невысокая точность кодирования, а следовательно, и распознавания отпечатков папиллярных узоров, что обусловлено большими погрешностями, вызванными разбросом положения пальца пользователя при снятии отпечатка. Это может привести к недостаточному количеству точек, необходимых для кодирования. Кроме того, существуют папиллярные узоры, в которых характерные точки вообще отсутствуют.

Известен способ сравнения папиллярных узоров пальцев (см. заявку РФ №94039018, МПК 6 G06К 9/00, 9/68, опубл. 10.09.1996), который заключается в том, что при сравнении папиллярных узоров регистрируют отпечатки с определением их координат и угла направления папиллярной линии в месте образования особенности. После формирования списка пар особенностей формируют матрицу совместности пар особенностей, из которой по заданным критериям выбирают наиболее идентичные пары и определяют итоговую однозначную комбинацию идентичных особенностей запросного и архивного отпечатков. При сравнении запросного и архивного отпечатков пальцев строят дифференциальную плоскость, на которую наносят точки, координаты которых определяют как разность между характеристиками особенностей запросного и архивного отпечатков пальцев. Для идентичных отпечатков пальцев эти точки образуют компактное множество. При нарушении компактности производят первичную отбраковку архивных отпечатков и дальнейшее их детальное исследование исключают. Очевидно, что при эластичной деформации запросного отпечатка пальца компактность множества точек на дифференциальной плоскости нарушается. Кроме того, для построения дифференциальной плоскости необходимо определить центр координат запросного и архивного отпечатков пальцев. Центр координат определяет характеристики особенностей. При смещении одного из центров координат компактность множества точек на дифференциальной плоскости тоже нарушается.

Таким образом, из-за деформации или смещения центров координат могут быть ложно забракованы идентичные отпечатки пальцев, что является существенным недостатком способа, так как снижает его надежность.

Указанный недостаток устранен в известном способе сравнения папиллярных узоров пальцев (см. патент РФ №2185661, МПК 7 G06К 9/62, опубл. 20.07.2002), который заключается в регистрации в области ясного отпечатка нумерованных особенностей с определением координат, угла направления и гребневого счета между особенностями запросного и архивного отпечатков пальцев. Для каждой особенности строят гнездо, в которое входит не менее двух особенностей, сравнивают все гнезда запросного и находящегося в базе архивного отпечатка пальцев и формируют не менее одной лучшей пары гнезд, содержащей гнездо запросного и гнездо архивного отпечатков пальцев. От каждой выделенной пары гнезд развивают параллельно фрагменты запросного и архивного отпечатков пальцев методом перехода от одной пары гнезд к другой по пути наилучшего сравнения гнезд. Накапливают оценки сравнения гнезд для каждого пути развития фрагментов и выбирают лучший путь. Сравнение гнезд запросного и архивного отпечатков пальцев производят после их геометрической привязки к петлям, дельтам и завиткам.

Использование описанного способа сравнения отпечатков папиллярных узоров при идентификации человека по отпечаткам пальцев позволяет решить поставленную авторами задачу, которая заключается в повышении достоверности сравнения папиллярных узоров пальцев, что является несомненным достоинством способа.

Однако к недостаткам описанного выше технического решения следует отнести невысокую скорость сравнения папиллярных узоров, а следовательно, и недостаточное быстродействие распознавания, свойственное всем способам, основанным на выделении и сопоставлении минуций. Это объясняется большим объемом вычислительных операций в процессе выявления наиболее близких папиллярных узоров.

Наиболее близким к заявляемому способу является способ сравнения папиллярных узоров пальцев (см. Кухарев Г.А. Биометрические системы: Методы и средства идентификации личности человека. - СПб.: Политехника, 2001, стр.27-33), выбранный в качестве прототипа. Способ основан на выделении и сопоставлении минуций и включает следующие этапы:

- улучшение качества исходного изображения отпечатка;

- вычисление поля ориентации папиллярных линий исходного отпечатка;

- бинаризация изображения отпечатка;

- утончение линий изображения отпечатка;

- выделение минуций и запись их параметров в вектор;

- сопоставление минуций.

Процесс сопоставления минуций состоит из трех частей:

- регистрация данных;

- поиск пар соответствующих друг другу минуций;

- оценка меры согласования двух сопоставляемых отпечатков.

В процессе выделения минуций, определения их типа и угла ориентации, координаты обнаруженных минуций, а также углы их ориентации записываются в вектор минуций. При этом в реальной ситуации два отпечатка одного и того же пальца, полученные один за другим на одном и том же сканере, будут отличаться друг от друга поворотом относительно одной из осей, смещением узора отпечатка относительно осей Х и Y, несколько различной деформацией узора (или нелинейными искажениями) узора, возможными изменениями масштаба представления отпечатков и, наконец, разными периферийными участками реального пальца. В связи с этим процесс сопоставления минуций должен быть реализован не за одну итерацию комплектно для всей их совокупности, а итерационно для каждой отдельной минуции. Этим обусловлена высокая достоверность идентификации, присущая описанному способу. Однако это же самое обстоятельство является причиной невысокого быстродействия способа, выбранного в качестве прототипа. Быстродействие способов, основанных на распознавании отпечатков путем сопоставления минуций, находится в диапазоне (300÷2000) сравнений/сек, что является существенным недостатком известного способа, так как ограничивает возможности его использования при работе с большими базами данных.

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

Для достижения указанного технического результата предлагается способ верификации и идентификации отпечатков папиллярных узоров, который, как и наиболее близкий к нему способ, выбранный в качестве прототипа, заключается в регистрации данных эталонного и предъявленного отпечатков папиллярных узоров. Регистрация данных состоит из формирования паспортов отпечатков пальцев путем выделения минуций, определения их типа, координат, углов ориентации и их записи в виде эталонного и предъявленного векторов минуций. Затем осуществляется сравнение эталонных паспортов отпечатков пальцев и предъявленного паспорта путем сопоставления минуций, заключающегося в поиске пар соответствующих друг другу минуций, оценки меры схожести сопоставляемых отпечатков и сравнения ее с порогом.

Особенностью предлагаемого способа, отличающей его от известного способа, выбранного в качестве прототипа, является то, что одновременно с формированием паспортов эталонного и предъявленного отпечатков пальцев осуществляют дополнительное фильтрационное кодирование, заключающееся в построении поля направлений папиллярных линий путем многократной математической обработки изображения отпечатка пальца проекционно-дисперсионным фильтром с последующей обработкой модернизированным медианным фильтром, поиске характерных точек, определении их типов и координат, фильтрации изображения в окрестностях каждой найденной характерной точки путем многократной обработки пространственно-волновым фильтром с плавающим окном и сохранении закодированных данных каждого отпечатка папиллярного узора вместе с данными, полученными на этапе формирования паспортов. При сравнении предъявленного и эталонного отпечатков папиллярных узоров перед процедурой сопоставления минуций осуществляют сравнение дополнительного кода предъявленного папиллярного узора с дополнительными кодами всех эталонных папиллярных узоров, полученными путем дополнительного фильтрационного кодирования и хранящимися в базе данных. Это сравнение осуществляют путем определения дистанции между двумя изображениями, представленными векторами минуций, полученными при дополнительном фильтрационном кодировании для всех возможных углов, принятия минимальной дистанции в качестве результата, соответствующего максимальной схожести изображений папиллярных узоров, формирования списка отпечатков-кандидатов, то есть эталонных паспортов, имеющих наиболее близкую степень совпадения с предъявленным отпечатком. После этого осуществляют сравнение каждого отпечатка-кандидата с предъявленным отпечатком методом, основанным на сопоставлении минуций.

При фильтрации изображения может быть использован фильтр Габора.

Для формирования списка отпечатков-кандидатов их количество задается в зависимости от размера базы эталонных отпечатков.

Сущность предлагаемого способа заключается в следующем.

Из патентной и научной литературы (см. Кухарев Г.А. Биометрические системы: Методы и средства идентификации личности человека. - СПб.: Политехника, 2001, стр.19-20) известно, что в каждом отпечатке можно определить признаки двух типов, используемые при их идентификации: глобальные и локальные. К первому типу относятся признаки, которые можно разглядеть и/или различить на отпечатках пальцев невооруженным глазом: папиллярные узоры, область образа, "ядро", пункты "дельта", тип папиллярных линий и их число. Ко второму типу относятся локальные признаки, называемые минуциями: это уникальные для каждого отпечатка признаки, определяющие пункты изменения структуры папиллярных линий (например, разрыв, окончание, раздвоение и т.д.), ориентацию папиллярных линий и координаты Х и Y в этих пунктах. Каждый отпечаток может быть представлен 50-70 минуциями. Исследования и практика подтверждают, что в отпечатках пальцев разных людей могут встречаться идентичные глобальные признаки, но при этом вероятность наличия в этих же отпечатках одинаковых микроузоров минуций очень мала. Как правило, глобальные признаки используют при больших базах отпечатков пальцев на этапах предварительной классификации. А затем, на втором этапе распознавания используют уже локальные признаки.

Процедуру идентификации условно можно разделить на следующие основные этапы:

- получение отпечатка пальца пользователя;

- регистрация данных папиллярного узора отпечатка пальца (формирование паспорта папиллярного узора) и их сохранение для последующей идентификации;

- собственно идентификация или верификация, то есть сравнение предъявленного отпечатка пальца конкретного пользователя с паспортом (эталоном), полученным на этапе регистрации данных;

- оценка уровня подобия сопоставляемых отпечатков папиллярных узоров и сравнение его с порогом.

Скорость и достоверность процедуры идентификации существенным образом зависит от того, каким путем осуществляется формирование паспортов отпечатков папиллярных узоров. В зависимости от поставленных задач эта процедура, называемая кодированием изображения отпечатка пальца, может осуществляться либо на основе характерных точек (глобальных признаков), либо на основе минуций (локальных признаков). При этом каждому способу присущи свои достоинства и недостатки, описанные в разделе "Уровень техники" предлагаемой заявки. Общие выводы, которые можно сделать на основании изучения уровня техники, следующие:

- способам идентификации, основанным на кодировании характерных точек, свойственна невысокая точность при высокой скорости процесса кодирования и дальнейшей идентификации;

- способы идентификации, использующие методы кодирования и сравнения на основе минуций и их сопоставления, отличаются высокой точностью и достоверностью при сравнительно невысокой скорости процесса сравнения и идентификации отпечатков папиллярных узоров.

Способ идентификации, выбранный в качестве ближайшего аналога (см. Кухарев Г.А. Биометрические системы: Методы и средства идентификации личности человека. - СПб.: Политехника, 2001, стр.27-33), основан на кодировании и сопоставлении минуций и имеет предел по скорости при сравнении наборов особенностей, который составляет (300÷2000) сравнений в секунду. Это принципиальное ограничение объясняется большими временными затратами, обусловленными многократными вычислениями наименьших дистанций между минуциями с целью установления наиболее схожих отпечатков. Естественно, что скорость сравнения и идентификации папиллярных узоров, закодированных методом, описанным в прототипе, будет также невысокая.

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

Эта особенность заявляемого способа обеспечена за счет того, что в отличительную часть формулы введен новый существенный признак - дополнительное фильтрационное кодирование, заключающееся в математической обработке изображения папиллярного узора отпечатка пальца, полученного на этапе регистрации пользователя. Эта высокоскоростная процедура производится одновременно с основным кодированием, которое осуществляется в процессе формирования паспорта папиллярного узора. Указанное дополнительное кодирование осуществляется путем пространственно-волновой фильтрации в области характерных точек с очень высокой скоростью. Осуществляется дополнительное кодирование в следующей последовательности, приведенной в формуле заявляемого изобретения, а именно:

- построении поля направлений папиллярных линий путем многократной математической обработки изображения отпечатка пальца проекционно-дисперсионным фильтром;

- последующей обработки модернизированным медианным фильтром;

- поиске характерных точек, определении их типов и координат;

- фильтрации изображения в окрестностях каждой найденной характерной точки путем многократной обработки пространственно-волновым фильтром с плавающим окном;

- сохранении закодированных данных отпечатка папиллярного узора для последующего распознавания совместно с данными, полученными при формировании паспорта отпечатка пальца пользователя.

Важной особенностью заявляемого способа верификации и идентификации отпечатка папиллярного узора является то, что дополнительное кодирование отпечатка пальца фильтром пространственно-волнового резонанса может быть проведено и при отсутствии на отпечатке пальца характерных точек ("ядер", "дельт") (такие отпечатки встречаются).

Таким образом, в результате обработки отпечатка папиллярного узора пальца описанным способом к основному набору данных, полученных в результате очень точного кодирования путем выделения минуций (основного кодирования), добавляется дополнительный набор данных, полученных путем многократной высокоскоростной математической обработки изображения отпечатка пальца сначала проекционно-дисперсионным фильтром, затем модернизированным медианным фильтром и, наконец, - фильтром пространственно-волнового резонанса.

Существенными признаками, относящимися к сравнению дополнительных кодов предъявленного и эталонного папиллярных узоров, являются признаки, отражающие последовательность проведения этой процедуры, а именно:

- определение дистанции между двумя изображениями, представленными векторами минуций, полученными при дополнительном фильтрационном кодировании для всех возможных углов;

- принятие минимальной дистанции в качестве результата, соответствующего максимальной схожести изображений папиллярных узоров;

- формирование списка отпечатков-кандидатов, то есть эталонных паспортов, имеющих наиболее близкую степень совпадения с предъявленным отпечатком.

Указанная процедура является высокоскоростной и оказывает существенное влияние на повышение быстродействия заявляемого способа в целом, способствуя тем самым решению поставленной задачи.

Рассмотрим теперь, каким образом происходит идентификация предъявленного отпечатка пальца при его сравнении с эталонным отпечатком, закодированным с помощью заявляемого способа.

В процессе сравнения предъявленного и эталонного отпечатков первым шагом является высокоскоростное сравнение дополнительного кода предъявленного папиллярного узора с кодами всех папиллярных узоров, находящимися в базе данных, полученными путем дополнительного фильтрационного кодирования.

Скорость этого сравнения, составляющая от 3000 до 60000 сравнений/сек, на несколько порядков выше, чем скорость сравнения отпечатков пальцев, основанного на сопоставлении минуций, которая составляет всего (300÷2000) сравнений/сек. В результате получается сравнительно небольшой список отпечатков - претендентов, имеющих наиболее близкую степень совпадения с предъявленным отпечатком (их количество зависит от размера базы эталонных отпечатков). Следующим шагом является более длительное, но очень точное сравнение, в ходе которого предъявленный отпечаток сравнивается уже только с отобранными отпечатками методом сопоставления минуций. Таким образом, происходит существенное увеличение скорости сравнения, а следовательно, и идентификации. Это обусловлено тем, что отпадает необходимость сравнения предъявленного отпечатка с каждым из хранящихся в базе данных отпечатком, закодированным точным, но сравнительно медленным способом - способом, основанным на кодировании и сопоставлении минуций, выбранным в качестве прототипа.

В признаках, включенных в зависимые пункты формулы, представлены конкретные примеры:

- выполнения процедуры фильтрации изображения, например, с использованием фильтра Габора (см. пункт 2 формулы);

- формирования списка отпечатков-кандидатов, задавая количество отпечатков-кандидатов в зависимости от размера базы эталонных отпечатков (см. пункт 3 формулы).

Таким образом, совокупность указанных выше признаков позволяет решить поставленные задачи.

Предлагаемый способ верификации и идентификации отпечатков папиллярных узоров иллюстрируется чертежами, на которых представлено:

на фиг.1 - поле направлений папиллярных линий, в котором каждому из четырех направлений соответствует свой цвет;

на фиг.2 - поле направлений папиллярных линий, в котором каждое направление изображено линиями, соответствующими одному из четырех основных направлений: 0°, 45°, 90°, 135° после обработки изображения отпечатка пальца проекционно-дисперсионным фильтром;

на фиг.3 - поле направлений папиллярных линий после обработки (фильтрации, сглаживания) изображения отпечатка пальца модернизированным медианным фильтром;

на фиг.4 - определение наличия "ядра" по комбинации полей направлений (изменение поля направлений папиллярных линий вокруг "ядра");

на фиг.5 - определение наличия "дельты" по комбинации полей направлений (изменение поля направлений папиллярных линий вокруг "дельты");

на фиг.6 - изображение папиллярных линий отпечатка пальца после обработки изображения пространственно-волновым фильтром в диапазоне [0°-180°);

на фиг.7 - фильтрованное изображение папиллярных линий отпечатка пальца, разбитое на (m×2n) кольцевых сектора.

Предлагаемый способ осуществляется следующим образом.

На первом этапе осуществления способа каждый пользователь должен быть зарегистрирован. Для этого на контактной поверхности устройства для регистрации отпечатков пальцев (оптического, емкостного или другого типа) необходимо получить отпечаток пальца каждого пользователя. В качестве устройства для регистрации отпечатков пальцев может быть использован любой из перечисленных ниже приборов:

- модели BS1620, BS2024 (Россия), технические решения запатентованы заявителем предлагаемого изобретения (см. патент РФ на полезную модель №46914, МПК 7 А61В 5/053, А61В 5/117, опубл. 10.08.2005);

- модель Fingkey Hamster, фирма Nitgen (Корея, Сеул),

- модели TCR42C, TCRUK, TCEBB1C, фирма UPEK (США), а также другие модели, выпускаемые за рубежом и в России.

Полученное изображение отпечатка папиллярного узора пальца оцифровывается и преобразуется в уникальный цифровой код, который является эталонным паспортом регистрируемого пользователя и заносится в базу данных системы для его сохранения и последующего сравнения с предъявленным папиллярным узором. Этот процесс, который назовем условно основным кодированием, должен быть основан на кодировании (экстракции) минуций - самом высокоточном и достоверном способе, известном на сегодняшний день из уровня техники.

Основное кодирование состоит из нескольких процедур и производится в следующей последовательности.

- Улучшение качества исходного изображения отпечатка. Для этого реализуется либо низкочастотная фильтрация, либо нормализация, назначением которых является исправление структуры гребней папиллярных линий и улучшение резкости их границ.

- Вычисление поля ориентации папиллярных линий. При этом все изображение разбивается на блоки, например, В×В пикселей (В≥5, целое) и для каждого блока (по градиентам яркости в блоке) вычисляется один угол ориентации θ папиллярных линий.

- Бинаризация изображения отпечатка. Процедура реализуется пороговой обработкой.

- Утончение линий изображения отпечатка. Выполняется процедурой утончения линий бинарного образа до тех пор, пока эти линии не станут равными одному пикселю.

- Выделение минуций и запись их параметров в вектор. Указанная процедура реализуется локальной обработкой всего изображения отпечатка пальца с помощью маски и подсчетом числа пикселей, находящихся вокруг центра маски и имеющих ненулевые значения. Пиксель в центре маски принимается за минуцию, если он сам имеет ненулевое значение и если число "соседей" также ненулевое и равно 1 или 2. При этом определяется тип обнаруженной минуций ("окончание" гребня или "раздвоение" гребня), а также координаты и угол ориентации минуций. Найденные координаты и углы их ориентации записываются в вектор минуций.

Описанные процедуры называются в патентной и технической литературе формированием паспорта отпечатка пальца (см., например, заявку на изобретение РФ №2003124350, МПК 7 G06K 19/073, G07C 9/00, G06F 1/00, опубл. 10.02.2005) или определением эталона отпечатка пальца (см. Кухарев Г.А. Биометрические системы: Методы и средства идентификации личности человека. - СПб.: Политехника, 2001, стр.233). Таким образом, в результате формирования паспорта отпечатка пальца его папиллярный узор преобразуется в уникальный цифровой код, который является эталонным паспортом регистрируемого пользователя и заносится в базу данных системы для его сохранения и последующего использования при сравнении с предъявляемым папиллярным узором.

Вторым этапом осуществления заявляемого способа является дополнительное кодирование эталонного отпечатка папиллярного узора, которое производится путем математической обработки оцифрованного изображения папиллярного узора регистрируемого отпечатка пальца. Второй этап осуществляется одновременно с цифровым (основным) кодированием, производимым на первом этапе при формировании эталонного паспорта папиллярного узора, и заключается в следующем.

Сначала путем многократной математической обработки изображения отпечатка пальца проекционно-дисперсионным фильтром определяют поле направлений папиллярных линий.

Для этого задаются размером плавающего окна n_sws более одного шага папиллярных линий и имеющем в пиксельном представлении нечетный размер. Размер плавающего окна определяется шагом папиллярных линий отпечатка, что в свою очередь зависит от разрешения исходного изображения.

Разрешение, dpi	Размер окна, пиксель
500-600	21-25
250-300	11-13

Данный фильтр является крайне трудоемким. Для каждой точки исходного изображения размером W×H производится следующее количество операций, не считая операций сравнения и присваивания.

Операция	Код	Число операций на точку
++	inc	2n2+6n-2
+	add	6n2+10n+1
-	sub	2n2+6n-2
*	imul	2n+11
/	idiv	4n+9
=	mov	5n2+18n+20
if	cmp+jmp	6n2+9n+9
memset	lodsb	24n-8

Например, для изображения размером 456×548 точек выбирается окно размером 25×25 точек, следовательно, получаем следующее число вычислений:

Операция	Код	Число операций на точку	Число операций на изображение
++	inc	1398	349343424
+	add	4001	999 801888
-	sub	1398	349343424
*	imul	61	15243168
/	idiv	109	27237792
=	mov	3595	898347360
if	cmp+jmp	3984	995553792
memset	lodsb	592	147933696
ИТОГО	3782804544

На компьютере с процессором Intel Pentium с частотой 2 ГГц и системной шиной на 266 МГц данная операция будет выполняться более 21 с, при этом необходимо еще выполнять операции сравнения и присваивания, а также изменение и контроль счетчиков циклов, которые по вложенности имеют четвертый порядок. Время необходимое на операцию рассчитывается исходя из того, что для чтения/записи результата требуется один такт системный шины и определенное число тактов процессора на саму операцию:

Операция	Код	Число тактов на операцию	Число тактов на изображение	Время, с
++	inc	3	1048030272	1.837336279
+	add	3	2999405664	5.258356546
-	sub	3	1048030272	1.837336279
*	imul	10	152431680	0.133520983
/	idiv	46	1252938432	0.72886693
=	mov	1	898347360	3.826419394
If	cmp+jmp	4	3982215168	5.733791013
memset	lodsb	2	295867392	0.70407541
ИТОГО	11677266240	20.06

Увеличения производительности можно добиться путем некоторого снижения точности получаемого результата. Для этого необходимо задаться некоторым шагом s_sws плавающего окна, т.е. перебирать не все точки исходного изображения, а через s_sws точек по горизонтали и вертикали.

Если выбирать s_sws<n_sws, то происходит перекрытие плавающих окон, и результат работы фильтра ухудшается незначительно. При s_sws≥n_sws картина проекционно-дисперсионного фильтра начинает достаточно сильно деградировать, и результат получается крайне неточным. Очевидно, что при такой организации работы фильтра мы получаем в раз выигрыш по производительности.

Практически для всех видов изображений сканированных отпечатков параметр s_sws можно выбирать в пределах 4...16.

После определения шага и размера плавающего окна вокруг некоторой точки изображения с координатами (x, y) в пределах размера плавающего окна вычисляем дисперсии значений в четырех основных направлениях - 0°, 45°, 90°, 135°. Каждое направление кодируется своим числом, в результате работы фильтра получается отображение поля направлении размера состоящее из пяти значении.

После этого, зададимся следующей кодировкой направлений и фона:

g_bg - индекс для фона,

g₀ - индекс для направления 0°,

g₄₅ - индекс для направления 45°,

g₉₀ - индекс для направления 90°,

g₁₃₅ - индекс для направления 135°,

При этом должно выполняться следующее неравенство:

g_bg<g₀<g₄₅<g₉₀<g₁₃₅.

Далее делаем следующие вычисления:

- вычисление среднего значения по плавающему окну:

среднее значение яркости в пределах плавающего окна вокруг точки (x, y):

Если среднее значение превысит порог яркости для фона, то принимаем в данной точке результат, равный индексу фона:

g(x,y)=g_bg, при μ≥f_bg.

- вычисление дисперсии в направлении 0°:

Вычисляем средние значения по строчкам плавающего окна:

где k=i.

Вычисляем дисперсию значений :

- вычисление дисперсии в направлении 45°:

Вычисляем средние значения по линиям плавающего окна расположенным под углом 45°:

где k=(i+j)-1.

Вычисляем дисперсию значений :

- вычисление дисперсии в направлении 90°:

Вычисляем средние значения по столбцам плавающего окна:

где k=j.

Вычисляем дисперсию значений :

- вычисление дисперсии в направлении 135°:

Вычисляем средние значения по линиям плавающего окна расположенным под углом 135°:

где k=(n-1)+(i-j)+1.

Вычисляем дисперсию значений :

Далее проводится оценка направления, которая заключается в следующем. Так как дисперсии, вычисленные по углам 45° и 135°, имеют заведомо завышенные значения, то перед сравнением их необходимо скорректировать. Для этого определяется максимальная дисперсия, которая и характеризует преобладающее направление папиллярных линий в заданной точке изображения:

где С - поправочный коэффициент для направлений 0° и 90°, который для большинства изображений отпечатка пальца можно выбирать в пределах от 1,5...2.

Картина поля направлений, полученная после применения проекционно-дисперсионного фильтра, представленная на фиг.2 и фиг.3, будет иметь помехи и неточности. Для построения более "гладкого" поля направлений необходимо удалить появившиеся случайные шумы. Для этой цели используется специальный модифицированный медианный фильтр.

Обработка изображения отпечатка пальца медианным фильтром осуществляется следующим образом.

Задаемся нечетным размером плавающего окна n_sws медианного фильтра. Вокруг некоторой точки изображения с координатами (х, y) в пределах размера плавающего окна вычисляем число повторений каждого значения с учетом коэффициентов, заданных матрицей фильтра размером [n_sws×n_sws]. Значение, которое имеет большее значение счетчика, выбирается в качестве результата фильтрации. Подсчитываем число повторений некоторого значения с учетом коэффициентов матрицы фильтра:

где , для всего отображения поля направлений;

с_ij - образуют матрицу коэффициентов фильтра:

Для отображения поля направлений, полученного проекционно-дисперсионным фильтром с указанными выше значениями размера и шага плавающего окна, можно принять в качестве размера плавающего окна и матрицы n_sws=3, а в качестве значений элементов матрицы - единицу с_ij=1.

Далее в векторе счетчиков находим максимальное значение и в качестве результата фильтрации в данной точке (х, y) выбираем значение, которое соответствовало этому счетчику:

.

После медианной фильтрации на картине поля направлений будут удалены случайные выпады значений из общего числа, тем самым картина поля направлений приобретает более "гладкий" вид (см. фиг.4). Данный фильтр является сходящимся и для полноценной картины необходимо выполнять фильтрацию до тех пор, пока отображение поля направлений не перестанет изменяться, т.е. g(x, y)=f(x, y), для всех х и y. Обычно число итераций не превышает 10-ти.

После обработки изображения отпечатка пальца модернизированным медианным фильтром осуществляется поиск глобальных особенностей (характерных точек), определяется тип характерных точек (ядро, дельта и т.д.) и их координаты. Под глобальными особенностями понимаются такие особенности папиллярного рисунка, которые сохраняются от изображения к изображению и в пределах допустимого шума могут быть однозначно определены. Например, точки типа "ядро" или "дельта".

Глобальные особенности характеризуются изменением поля направлений, которое вокруг таких особенностей как "ядро" или "дельта" последовательно изменяет свое значение в диапазоне от 0° до 360°. Найденные точки используют затем в качестве центров для осуществления дополнительной пространственно-волновой фильтрации Габора.

Вокруг такой характерной точки папиллярного рисунка, как "ядро" направления линий изменяется от 0° до 360° против часовой стрелки. Т.е. если рассмотреть построенное нами поле направлений вокруг этой точки, то мы увидим, как оно последовательно против часовой стрелки изменяет значения в сторону увеличения угла - 0°, 45°, 90° и 135° (см. фиг.5).

Вокруг такой характерной точки папиллярного рисунка как "дельта" направления линий изменяется от 0° до 360° по часовой стрелке. Т.е. если рассмотреть построенное нами поле направлений вокруг этой точки, то мы увидим, как оно последовательно по часовой стрелке изменяет значения в сторону увеличения угла - 0°, 45°, 90° и 135° (см. фиг.6).

После определения глобальных особенностей (характерных точек), их типа и координат осуществляют поиск точек интереса и вычисление центров особенностей.

Первый этап поиска глобальных особенностей - это составление списка точек интереса, т.е. таких точек, в районе которых поле направлений ведет себя характерным для глобальной особенности образом.

Данный поиск осуществляется плавающим окном размера 2×2. Окно строится относительно своего верхнего левого угла, т.е. в рассмотрение попадают, кроме точки с координатами (х, y), также точки с координатами (х+1, y), (х, y+1) и (х+1, y+1).

Если среди четырех значений есть значение g_bg, то точка не рассматривается. Аналогично когда в пределах окна всего одно или два значения, то точка также не рассматривается.

На рассмотрение попадают точки, вокруг которых имеется три или четыре разных направления. В этом случае анализируется последовательность изменения направлений. Начиная с минимального, они должны последовательно возрастать либо по часовой стрелке - для "дельты", либо против часовой стрелки - для "ядра". Такие точки запоминаются в массивы предполагаемых точек типа "дельта" и "ядро".

Если в окне присутствуют сразу все четыре направления и их последовательность соответствует "дельте" или "ядру", то данная точка принимается за центр данной особенности. Если же в окне присутствуют только три направления, то такая точка требует уточнения.

Уточнение начинается с построения массива дистанций между предполагаемыми точками одного типа, которые дополняют друг друга по не хватающим направлениям. То есть вычисляются дистанции между всеми парами точек одного типа, в которых в сумме присутствуют все четыре направления. Из такого массива выбираются такие пары, дистанция между которыми, во-первых, минимальна, во-вторых, не превышает некоторого предельного значения [D] (обычно квадрат предельной дистанции не превышает 9...40).

Для пар, удовлетворяющих этим условиям, вычисляются координаты среднего положения между ними и принимаются за координаты центра особенности.

Далее изображение обрабатывается плавающим окном нечетного размера n_sws несколько раз для различных направлений распространия волны. Коэффициенты окна вычисляются по формуле и зависят от угла распространения волны. Исходная волна распространяется вдоль оси х с симметричным экспоненциальным затуханием амплитуды:

при

где - частота волн, обратно пропорциональная разрешению;

σ˜dpi - обратный коэффициент затухания.

Для распространения волны в произвольном направлении под углом ϕ, имеем следующую зависимость:

где χ=xcosϕ-ysinϕ, для и

Для дискретной сетки плавающего окна получим следующее выражение:

где , , при и

χ_ij=x_jcosϕ-y_isinϕ.

Результирующее отображение вычисляется следующим образом:

Расчет ведется по n направлениям в диапазоне [0,180), пронумерованным для определенности против часовой стрелки. В результате получаем n фильтрованных изображений (см. фиг.7).

В окрестностях каждой найденной характерной точки путем пространственно-волновой фильтрации Габора вычисляют характерные числовые особенности изображения отпечатка пальца (минуции).

Для вычисления характерных числовых особенностей изображения - минуций фильтрованные изображения разбиваются на m колец, пронумерованных для определенности, начиная от центра, и 2n секторов вокруг геометрического центра глобальных особенностей, которые для определенности пронумерованы против часовой стрелки. Таким образом, на каждом из n фильтрованных изображений мы получаем m×2n областей (см. фиг.8), в каждой из которых вычисляем среднее значение:

, при

где О_kij - область k-го изображения, i-го кольца и j-го сектора;

- число отсчетов изображения находящихся в области O_kij.

Далее для каждой такой области вычисляется абсолютное среднее отклонение:

, при

В результате вычислений получаем вектор минуций М, состоящий из n×m×2n=2n²m чисел, который внутри разбит на n матриц размером m×2n.

В случае, если элемент сетки выходит за границы изображения или на исходном изображении в этом месте проекцонно-дисперсионным фильтром был определен фон, то в качестве значения записывается -1. И далее в функции сравнения оно не участвует.

Таким образом, описанная выше процедура кодирования состоит из двух параллельно проходящих этапов: основного и дополнительного кодирования и может быть названа комбинированным кодированием.

Закодированные таким образом данные отпечатка папиллярного узора сохраняются для последующей идентификации вместе с эталонными данными, полученными на первом этапе формирования паспорта отпечатка пальца.

Рассмотрим теперь, каким образом происходит идентификация предъявленного отпечатка пальца при его сравнении с эталонным отпечатком, закодированным с помощью комбинированного метода, включающего основное и дополнительное фильтрационное кодирование. Предъявленный отпечаток кодируется высокоточным способом, основанным на кодировании минуций (основное кодирование), и параллельно проводится дополнительное фильтрационное кодирование (дополнительное кодирование). Результатом кодирования является паспорт предъявленного папиллярного узора, который должен быть идентифицирован по эталонным паспортам, хранящимся в базе данных.

Все этапы процедуры кодирования (основного и дополнительного) осуществляются идентично и в той же самой последовательности, что и описанные выше процедуры, проводимые при формировании эталонного паспорта папиллярного узора, подробно описанные в начале раздела "Осуществление способа" на стр.13-26 предлагаемой заявки.

Следующим этапом осуществления заявляемого способа является сравнение предъявленного и эталонного паспортов отпечатков папиллярных узоров, при этом первый шаг заключается в высокоскоростном сравнении дополнительного кода предъявленного папиллярного узора с кодами всех папиллярных узоров, находящимися в базе данных, полученными путем дополнительного фильтрационного кодирования.

Сравнение изображений основано на использовании глобальных особенностей, что позволяет при сравнении изображений избавиться от степеней свободы, связанных со смещением. Кроме того, благодаря построению минуций вокруг базовой точки в полярных координатах поворот вокруг центра заменяется сдвигом.

Дистанция Ω между двумя изображениями, представленными векторами минуций M₁ и M₂, вычисляется по формуле:

где Δ - абсолютное среднее отклонение яркости сектора;

2n - число секторов вокруг геометрического центра глобальных особенностей;

m - число колец.

Так как мы не знаем, на какой угол одно изображение повернуто относительно другого, то необходимо просчитать дистанцию между изображениями для всех возможных 2n углов и выбрать в качестве результирующего значения минимальное. Для этого последовательно выполняется круговой сдвиг матриц m×2n внутри одного из сравниваемых векторов, например, вектора M₂, таким образом, что последний становится первым - это соответствует выбранной нумерации направлений фильтраций против часовой стрелки. Необходимо также внутри каждой из n матриц сдвигаемого вектора произвести циклический сдвиг столбцов, таким образом, чтобы последний становился первым, что соответствует выбранной нумерации секторов против часовой стрелки.

Получив таким образом "2n" дистанций, необходимо принять в качестве результата минимальную, что соответствует предположению о максимальной схожести изображений. Нормированный результат в пределах (0,1], где ноль соответствует абсолютной непохожести изображений, а единица полному соответствию, получается из выражения:

где ρ - степень непохожести изображений,

(х, y) принадлежат изображению.

Двойка в знаменателе получается из соображений, что фильтр Габора имеет значения коэффициентов в пределах [-1, 1], следовательно, фильтрованное изображение g[x, y) может имеет значения в пределах [-f_max, f_max]. Далее среднее значение μ_kij также попадает в диапазон [f_max, f_max]. А вот абсолютное среднее отклонение Δ_kij может изменяться в диапазоне [0,2f_max].

Скорость этого сравнения, которая составляет от 3000 до 60000 сравнений/сек, на несколько порядков выше, чем скорость сравнения отпечатков пальцев при кодировании, основанном на сопоставлении минуций. В результате получается сравнительно небольшой список, например, несколько десятков отпечатков - претендентов, прошедших порог и имеющих наиболее близкую степень совпадения с предъявленным отпечатком. Порог задается из расчета оптимального соотношения вероятности пропуска "чужих" и не пропуска "своих" и зависит от размера базы эталонных отпечатков.

Следующим шагом является более длительное, но очень точное сравнение, основанное на сопоставлении минуций. В ходе этого сравнения предъявленный (текущий) отпечаток, прошедший регистрацию, сравнивается только с отобранными на предыдущем этапе отпечатками методом сопоставления минуций, который заключается в следующем.

Как было указано выше, на этапе регистрации пользователей и формировании базы эталонных отпечатков координаты обнаруженных минуций, а также углы их ориентации записываются в вектор минуций, который может быть представлен в следующей форме:

W^(р)=[(x₁, y₁, θ₁), (x₂, y₂, θ₁), (х₃, y₃, θ₃), ..., (х_р, y_р, θ_р)],

где параметр "р" определяет число минуций.

На этапе регистрации пользователей указанный вектор определяет эталон Е^(p), который записывается в базу эталонов. На этапе распознавания вектор определяет текущий (предъявленный) отпечаток O^(q) и его параметры. Далее необходимо определить такие параметры аффинных преобразований, как угол поворота, масштаб и сдвиги (Δх и Δу), при которых некоторая минуция вектора О^(q) будет согласована с некоторой минуцией вектора Е^(p). Для того чтобы решить эту задачу (при условии q≠р), необходимо выполнить пересчет координат каждой минуций из вектора О^(q) для всех возможных значений изменений параметров поворота, масштаба и сдвигов. Общее число пересчетов координат только одной минуций составит 2Ф MNL,

где Ф - угол поворота, на который могут быть повернуты относительно друг друга два отпечатка пальца;

М - максимальный сдвиг по оси х;

N - максимальный сдвиг по оси y;

L - максимальное изменение масштаба отпечатка.

Затем осуществляется поиск пар соответствующих друг другу минуций, для чего на каждом шаге (из 2Ф MNL возможных) координаты минуций из вектора О^(q) подвергаются аффинным преобразованиям, и полученные новые координаты сопоставляются с каждой из координат минуций вектора Е^(p). Согласованные пары минуций в дальнейших итерациях не участвуют (если речь не идет о новом эталоне). После этого проводится оценка меры соответствия двух сопоставляемых отпечатков. В процессе поиска пар минуций в памяти сохраняется информация о параметрах {Δх, Δy, Δk, Δϕ}, при которых найдена пара, а также подсчитывается число найденных пар минуций. Если одинаковая информация о параметрах {Δx, Δy, Δk, Δϕ} повторяется довольно часто, то это свидетельствует о высоком качестве соответствия отпечатков и определении истинных параметров аффинных преобразований, связывающих два отпечатка между собой.

Если сопоставление выполнялось в задаче верификации отпечатков, то на этом весь процесс заканчивается. Если же поставленной задачей была идентификация отпечатков, то описанный процесс необходимо повторять, но не для всех отпечатков, как в прототипе, а только для отпечатков - кандидатов, прошедших порог и имеющих наиболее близкую степень совпадения с предъявленным отпечатком.

Таким образом, происходит существенное увеличение скорости сравнения, так как отпадает необходимость сравнения предъявленного отпечатка с каждым из хранящихся в базе данных эталонным отпечатком, закодированным точным, но сравнительно медленным способом - способом кодирования на основе минуций, выбранным в качестве прототипа.

В заключение следует также отметить, что использование в предложенном способе верификации и идентификации отпечатков папиллярных узоров дополнительного фильтрационного кодирования, реализованного на уровне программного или аппаратного обеспечения, позволяет по сравнению с прототипом существенно повысить быстродействие процесса идентификации предъявленного отпечатка пальца, сохранив при этом высокую достоверность способа, выбранного в качестве прототипа.

1. Способ верификации и идентификации отпечатков папиллярных узоров, заключающийся в регистрации данных эталонного и предъявленного отпечатков папиллярных узоров, состоящей из формирования паспортов отпечатков пальцев путем выделения минуций, определения их типа, координат, углов ориентации и их записи в виде эталонного и предъявленного векторов минуций соответственно, сравнении эталонных паспортов отпечатков пальцев и предъявленного паспорта путем сопоставления минуций, заключающегося в поиске пар соответствующих друг другу минуций, оценки меры схожести сопоставляемых отпечатков и сравнения ее с порогом, отличающийся тем, что одновременно с формированием паспортов эталонного и предъявленного отпечатков пальцев осуществляют дополнительное фильтрационное кодирование, заключающееся в построении поля направлений папиллярных линий путем многократной математической обработки изображения отпечатка пальца проекционно-дисперсионным фильтром с последующей обработкой модернизированным медианным фильтром, поиске характерных точек, определении их типов и координат, фильтрации изображения в окрестностях каждой найденной характерной точки путем многократной обработки пространственно-волновым фильтром с плавающим окном и сохранении закодированных данных каждого отпечатка папиллярного узора вместе с данными, полученными на этапе формирования паспортов, причем при сравнении предъявленного и эталонного отпечатков папиллярных узоров перед процедурой сопоставления минуций осуществляют сравнение дополнительного кода предъявленного папиллярного узора с дополнительными кодами всех эталонных папиллярных узоров, полученными путем дополнительного фильтрационного кодирования и хранящимися в базе данных, путем определения дистанции между двумя изображениями, представленными векторами минуций, полученными при дополнительном фильтрационном кодировании для всех возможных углов, принятия минимальной дистанции в качестве результата, соответствующего максимальной схожести изображений папиллярных узоров, формирования списка отпечатков-кандидатов, то есть эталонных паспортов, имеющих наиболее близкую степень совпадения с предъявленным отпечатком, и последующего сравнения каждого отпечатка-кандидата с предъявленным отпечатком методом, основанным на сопоставлении минуций.

2. Способ по п.1, отличающийся тем, что при фильтрации изображения используется фильтр Габора.

3. Способ по п.1 или 2, отличающийся тем, что для формирования списка отпечатков-кандидатов их количество задается в зависимости от размера базы эталонных отпечатков.