способ и устройство инвариантной идентификации отпечатков пальцев по ключевым точкам

Формула изобретения

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

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

Описание изобретения к патенту

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

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

Известен метод и устройство биометрической аутентификации (патент № 7526110 B2 US, МПК G06K 9/00, 2009.04.28). Для увеличения достоверности распознавания при отказе в верификации по основному признаку, использующему ключевые точки, в нем предусматривается проверка по дублирующему признаку, использующему рисунок папилляров и не связанному с основным.

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

Известен способ верификации и идентификации отпечатков паиллярных узоров (патент № 2310910 C1 RU, МПК G06K 9/00, БИМП № 32, 2007.11.20). В нем предусматривается формирование паспорта отпечатков пальцев с помощью кодирования с использованием различных фильтров. Затем сравниваются векторы признаков ключевых точек по всем полученным описаниям.

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

Наиболее близким к заявляемому можно считать способ формирования биометрического кода отпечатка пальца (патент № 2395840 C1 RU, МПК G06K 9/00, 2010.07.27). В нем предусматривается восстановление и скелетизация папиллярных линий, выделение ключевых точек и запись их параметров относительно их центра тяжести.

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

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

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

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

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

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

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

На Фиг.1 изображена область неудаленных достоверных ключевых точек и центрирующий контур одного отпечатка пальца.

На Фиг.2 изображена схема подключения специализированного многопроцессорного ускоряющего устройства.

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

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

Устройство 1 (Фиг.3) состоит из головной микроЭВМ 2 (ГМЭВМ), ведомой микроЭВМ 3 (ВМЭВМ), многопроцессорного акселератора распознавания 4 (MAP), транспортной сети 5 и блоков оперативной памяти 6, 7 для хранения архивного и запросного отпечатков. Устройство подключается между основной рабочей ЭВМ, если она является объектом ограничения доступа, или между экспертным персональным компьютером (ПК), так называемой в данном описании главной ЭВМ 8 (ГЭВМ) (Фиг.2), имеющим доступ в базу данных отпечатков пальцев, и дактилоскопическим датчиком 9 (ДД) (Фиг.2), в качестве которого может быть использован сканер отпечатков пальцев, а также ПК или сеть ЭВМ, если распознаваемые изображения отпечатков пальцев заранее отсканированы и хранятся во внешней памяти ПК или сетевой ЭВМ.

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

Способ оперирует паспортами запросного и архивного отпечатков пальцев, представленными множествами значений декартовых координат их ключевых точек. Если отпечатки пальцев представлены предшествующими растровыми полутоновыми изображениями, то необходимо при их преобразовании в паспорта уменьшить число ошибок поиска ключевых точек, применив следующие три известных этапа предварительной обработки изображений отпечатков пальцев (например, как описано в Долгий И.Д. К вопросу об идентификации личности в системе диспетчерской централизации [Текст] / И.Д.Долгий, С.М.Ковалев, С.А.Кулькин // Перспективные информационные технологии и интеллектуальные системы, № 4(24), 2005):

1. Восстановление папиллярных линий.

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

3. Логическая фильтрация ключевых точек.

К предварительной обработке можно отнести также и взаимное масштабирование сравниваемых отпечатков пальцев.

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

1. Этап неточного центрирования.

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

3. Сравнение базовых отрезков из разных отпечатков пальцев и выделение по одному достоверному базовому отрезку в каждом из двух отпечатков пальца.

4. Присвоение точкам новых координат.

Этапы 1, 2 и 4 выполняются одинаково и независимо в каждом из отпечатков пальцев в отдельности.

Первый этап неточного центрирования:

1. Определяем координаты центра ложной декартовой системы координат.

1.А. Подсчитываем общее число ключевых точек в отпечатке пальца.

1.Б. Складываем значения первичных координат X всех ключевых точек отпечатка пальца в исходной декартовой системе координат и делим на общее их число. Это и есть координата X центра ложной декартовой системы координат.

1.В. Складываем значения первичных координат У всех ключевых точек отпечатка пальца в исходной декартовой системе координат и делим на общее их число. Это и есть координата У центра ложной декартовой системы координат.

2. Переприсваиваем значения координат X и У каждой точке относительно центра ложной декартовой системы координат. Для этого вычитаем из первичных координат X и У каждой точки, найденной в пункте 1, значения координат центра ложной декартовой системы координат.

3. Подсчитываем расстояние от каждой ключевой точки до центра ложной декартовой системы координат как корень квадратный из суммы квадратов разностей их координат в исходной декартовой системе координат.

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

5. Удаляем ключевые точки, для которых величина, найденная в пункте 3, меньше, чем 10% от величины, найденной в пункте 4, или больше, чем 90% от величины, найденной в пункте 4 (Фиг.1).

6. Подсчитываем число оставшихся ключевых точек в усеченном по пункту 5 изображении отпечатка пальца.

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

Второй этап формирования центрирующего контура из базовых отрезков (Фиг.1):

1. Подсчитываем для каждой оставшейся после первого этапа ключевой точки значение арксинуса от ее координаты У, деленной на корень квадратный из суммы квадратов ее координат.

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

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

4. Проверяем знаки координат X и У каждой ключевой точки и вносим ее в подмассив соответствующей четверти.

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

6. Удаляем временные массивы по четвертям.

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

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

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

3. Выполняем сравнение всех базовых отрезков первого отпечатка пальца со всеми базовыми отрезками второго отпечатка пальца:

3.A. Вначале сравниваем попарно только длины базовых отрезков. Если длины отличаются меньше, чем на 10%, то переходим к пункту 3.Б. Если они отличаются более чем на 10%, то игнорируем данный очередной отрезок, выбранный в этом центрирующем контуре, и переходим к проверке следующего базового отрезка.

3.Б. Находим величину нормированного расстояния C между сравниваемыми отрезками в каждой из их пар:

С=(С1+С2+С3+С4)/4,

где l - длина базового отрезка;

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

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

a_A1 и a_B1, a_A2 и a_B2 - углы с соседями первого и второго порядка против часовой стрелки;

a_A3 и a_B3, a_A4 и a_B4 - углы с соседями первого и второго порядка по часовой стрелке;

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

- максимально возможная величина угла, равная 2 .

3.В. Выделяем по наименьшей величине С пару наиболее близких базовых отрезков из двух сравниваемых отпечатков и признаем каждый из этих базовых отрезков наиболее достоверным в своем отпечатке пальца.

Четвертый этап присвоения точкам новых координат.

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

2. Определяем, какой из концов выделенного в пункте 3.В отрезка расположен дальше от центра ложной декартовой системы координат, по большему из значений расстояний, полученных ранее в пункте 3 первого этапа неточного центрирования.

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

где X_T, Y_T - абсцисса и ордината данной ключевой точки в первичной декартовой системе координат,

X_O, Y_O - абсцисса и ордината центра достоверного базового отрезка в ложной декартовой системе координат,

X_K , Y_K - абсцисса и ордината наиболее удаленного по пункту 2 данного этапа конца достоверного базового отрезка в ложной декартовой системе координат.

Приведенная формула для вычисления угла является следствием теоремы косинусов.

4. Удаляем массивы базовых отрезков.

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

Алгоритм распознавания отпечатков пальцев на основе метрики Хаусдорфа содержит следующие восемь этапов:

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

2. Создаем два временных массива для промежуточных величин по двум отпечаткам пальцев, с числом элементов в каждом, равным числу ключевых точек в этом отпечатке пальца.

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

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

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

6. Вычисляем минимальное значение из двух величин, полученных в пункте 5.

7. Сравниваем величину, найденную в пункте 6, с величиной установленного порога (порог определяется по величине расстояния между папилярами в распознаваемых отпечатках пальцев). Если величина, найденная в пункте 6, меньше порога, то считаем отпечатки пальцев идентичными, иначе - различными.

8. Удаляем все временные массивы.

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

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

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

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

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

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

Для экспериментов были использованы отпечатки пальцев пяти различных типов (арка, правый и левый завитки, левая и правая петля), были проведены более трехсот сравнений на десяти тестовых наборах отпечатков пальцев.

Устройство идентификации 1 (Фиг.2) реализует все этапы описанного способа. Схема подключения устройства 1 к главной ЭВМ 8 (ГВЭМ) и дактилоскопическому датчику 9 (ДД) системы распознавания отпечатков пальцев показана на Фиг.2. С помощью ГЭВМ 8 задаются и исполняются следующие начальные и заключительные этапы работы системы распознавания отпечатков пальцев, инициируемые сигналами 10-13 (Фиг.2):

10. Выбор режима работы, подача сигнала ожидания ввода отпечатка пальца к ДД 9.

11. Загрузка архивного изображения отпечатка пальца из ГЭВМ 8 в устройство 1 для формирования его паспорта.

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

13. Организация приема в ГЭВМ 8 из устройства 1 результатов сравнения отпечатков пальцев и принятого решения.

Структурная схема предлагаемого устройства приведена на Фиг.3. Вход 11 устройства (Фиг.3) подключается к выходу ГЭВМ 8 (Фиг.2), а его выход 13 ко входу ГЭВМ 8 (Фиг.2). Вход 12 устройства подключается к выходу ДД 9 (Фиг.2). В головную микроЭВМ 2 (ГМЭВМ) и ведомую микроЭВМ 3 (ВМЭВМ) устройства (Фиг.3) из ГЭВМ 8 (Фиг.2) заранее загружаются команды, объединенные в подпрограммы по этапам, выполняемым одновременно и независимо. Если одна из этих двух МЭВМ 2 или 3 (Фиг.3) завершила обработку всех команд этапа, то она ждет, пока другая также завершит все свои команды этого же этапа. Номер текущего этапа хранится в регистре команд устройства. Аналогично объединены в подпрограммы команды и в акселераторных ЭВМ 14-29 (АЭВМ). Они хранятся в оперативных памятях 30-46 (ОП) АЭВМ 14-29 и управляющей ЭВМ 47 (УЭВМ) многопроцессорного акселератора распознавания 4 (MAP) (Фиг.3) и используют регистры команд АЭВМ 14-29 и УЭВМ 47, входящих в состав MAP 4.

В MAP 4 предлагаемого устройства 1 (Фиг.3) используется шестнадцать акселераторных ЭВМ с сокращенной системой команд 14-29 (АЭВМ), управляющая ЭВМ 47 (УЭВМ), известный пирамидально-конвейерный блок вычисления максимумов или минимумов 48 (ПКБММ) (построенный на основе логических элементов многоместного минимума и максимума, например, как в Кочергин В.И.Теория многомерных цифровых множеств в приложениях к электроприводам и системам электропитания [Текст] / В.И.Кочергин // Томск: Изд-во Том. ун-та, 2002. - 444 с. - ISBN 5-751 1-1583-Х), известный блок барьерной синхронизации 49 (ББС) (например, Johnson Т.А. Cyclical cascade chains: dynamic barrier synchronization mechanism for multiprocessor systems [Text] / T.A.Johnson, R.R.Hoare // ipdps, vol.3, pp.30193b, 15th International Parallel and Distributed Processing Symposium (IPDPS'01) Workshops, 2001), транспортная сеть в виде транзитной магистральной общей шины 5 (ТМОШ) и вспомогательные элементы. ГМЭВМ 2 содержит оперативную память 6 для хранения паспорта архивного отпечатка, обрабатываемого на текущем этапе работы устройства. ВМЭВМ 3 содержит оперативную память 7 для хранения паспорта запросного отпечатка, созданного из распознаваемого отпечатка. Последняя заполняется декартовыми координатами его ключевых точек, которые выделяются в результате известной предварительной обработки изображения, полученного по входу 12 с дактилоскопического датчика 9 (ДД). Памяти ОП 6 и ОП 7 головной 2 и ведомой 3 микроЭВМ устройства 1 содержат дополнительные графические буферы, в которые могут помещаться растровые изображения отпечатков пальцев, если еще не выполнена их предварительная обработка и не выделены их ключевые точки. В ячейке памяти ОП 6 (регистре результата) ГМЭВМ 2 хранится код конечного результата принятого решения, значение первого бита которого является признаком идентичности или неидентичности сопоставляемых отпечатков пальцев.

ГМЭВМ 2 и ВМЭВМ 3 (Фиг.3) состоят из типовых микропроцессоров 50, 51 (МП), оперативных памятей 6, 7 (ОП), контроллеров памяти 52, 53 (КП), портов ввода-вывода 54, 55 (ПВВ) и контроллеров прямого доступа в память 56, 57 (КПДП). АЭВМ 14-29 и УЭВМ 47 представляют собой программно управляемые ЭВМ с сокращенной системой команд и состоят из типовых микропроцессоров 58-74 (МП), оперативных памятей 30-46 (ОП), контроллеров памяти 75-91 (КП). Через КП 52, 53, 75-91 каждая ЭВМ подключается к транзитной магистральной общей шине 5 (ТМОШ). С их помощью из блоков ОП 6, 7, 30-46 всех ЭВМ 2, 3, 14-29, 47, подключенных к ТМОШ 5, организуется общая оперативная память с общим адресным пространством всех ЭВМ, аналогичная известной общей памяти мультипроцессорной вычислительной системы (например, описанной в Цилькер Б.Я. Организация ЭВМ и систем [Текст] / Б.Я.Цилькер, С.А.Орлов // Учебник для вузов. - СПБ: Питер, 2004).

В MAP 4 из АЭВМ 14-29 посредством ПВВ 92-107 передаются данные на входы 108-123 ПКБММ 48, а также сигналы готовности на входы 124-139 ББС 49. При этом выход ББС 49, соединенный с выходом ПКБММ 48, используется для синхронизации приема его входных данных с выходом ПВВ 140 УЭВМ 47. Найденная максимальная или минимальная величина передается с выхода ББС 48 на вход ПВВ 140 УЭВМ 47. Через ПВВ 140 управляющая ЭВМ 47 передает на управляющий вход 141 ПКБММ 48 сигнал, задающий режим работы блока ПКБММ 48: выделение максимума или минимума.

Предлагаемое устройство 1 (Фиг.2, 3), подключаемое к ГЭВМ 8 (Фиг.2) для ускорения идентификации личности по отпечатку пальца, построено на основе мультипроцессорной архитектуры с транзитной магистральной общей шиной 5 (ТМОШ), по которой передаются пакеты данных. Все ЭВМ, присутствующие в устройстве, используют для работы с ТМОШ 5 собственные КП 52, 53, 75-91 (Фиг.3).

После формирования паспортов запросного и архивного отпечатков пальцев в виде списков декартовых координат ключевых точек начинается обработка по данному заявленному способу. Как только получен паспорт запросного отпечатка в виде списка декартовых координат ключевых точек, начинается загрузка координат всех ключевых точек запросного и архивного отпечатков в ОП 30-45 АЭВМ 14-29 и реализация этапов неточного центрирования и формирования центрирующего контура. В УЭВМ 47 передаются только числа ключевых точек в запросном и архивном отпечатках пальцев, так как она следит за выполнением этапов вычисления в MAP 4. В ГМЭВМ 2 и ВМЭВМ 3 независимо и параллельно выполняются все пункты этапов неточного центрирования и формирования центрирующих контуров из базовых отрезков. Промежуточные результаты хранятся в ОП 6, 7 соответствующих МЭВМ 2, 3. MAP 4 задействуется при вычислении расстояний от каждой ключевой точки до центра ложной декартовой системы координат и упорядочивании их по полученной величине с использованием ПКБММ 48. Из MAP 4 обратно в ГМЭВМ 2 и ВМЭВМ 3 передаются упорядоченные массивы ключевых точек, соответствующие критериям удаления от ложного центра в декартовой системе координат по пункту 5 первого этапа неточного центрирования (см. описание способа).

Во время выполнения этапа формирования центрирующего контура для вычислений во всех пунктах алгоритма используется MAP 4. Для этого откорректированные массивы ключевых точек передаются в ОП 30-45 всех АЭВМ 14-29. В MAP 4 происходит вычисление величин углов расположения ключевых точек относительно центра ложной декартовой системы координат и упорядочивание по полученным величинам углов, а также формирование массивов базовых отрезков по четвертям в соответствии с пунктом 3 второго этапа формирования центрирующего контура (см. описание способа). Полученные массивы ключевых точек передаются в ГМЭВМ 2 и ВМЭВМ 3, где формируются два центрирующих контура из базовых отрезков для архивного и запросного отпечатков соответственно. Эти контуры, представленные массивами пар ключевых точек и еще незаполненных слов, соответствующих длинам базовых отрезков и углам между каждым из них и четырьмя соседними отрезками, передаются в ОП 30-45 АЭВМ 14-29.

В начале этапа попарного сравнения базовых отрезков из разных отпечатков пальцев и выделения по одному достоверному базовому отрезку в каждом из двух отпечатков пальцев в MAP 4 вычисляются длины всех отрезков и углы их отношений с соседями. Затем вычисляется нормированное расстояние между базовыми отрезками из двух отпечатков пальцев по формулам из пункта З.Б. третьего этапа описания способа. С помощью ПКБММ 48 находится пара базовых отрезков запросного и архивного отпечатков с минимальным расстоянием друг от друга, и каждый из них признается наиболее достоверным в своем отпечатке пальца. Затем УЭВМ 47 передает в ГМЭВМ 2 и ВМЭВМ 3 указание на идентификаторы достоверных базовых отрезков в архивном и запросном отпечатке соответственно.

На этапе присвоения новых полярных координат в MAP 4 из ГМЭВМ 2 и ВМЭВМ 3 передаются координаты центров найденных выше достоверных базовых отрезков и тех их концов, которые имеют наибольшее удаление от центров ложных декартовых систем координат архивного и запросного отпечатков соответственно. В MAP 4 параллельно-последовательно вычисляются новые координаты ключевых точек в устойчивой полярной системе координат по формулам из пункта 3 четвертого этапа описания способа. Сформированные подмножества координат ключевых точек архивного и запросного отпечатка передаются из ОП 30-45 АЭВМ 14-29 в ГМЭВМ 2 и ВМЭВМ 3 соответственно. Объединенные и упорядоченные массивы названных координат переписываются в каждую ОП 30-45 всех АЭВМ 14-29.

При сравнении отпечатков по методу, основанному на метрике Хаусдорфа, в MAP 4 параллельно-последовательно вычисляются величины удалений всех ключевых точек выбранного отпечатка пальца от всех ключевых точек другого отпечатка пальца. Для этих вычислений удобнее выбрать отпечаток пальца с меньшим числом ключевых точек. С помощью блока ПКБММ 48 находятся минимальные удаления для всех ключевых точек запросного и архивного отпечатков и сохраняются в ОП 46 УЭВМ 47. Затем они передаются в ГМЭВМ 2 для дальнейшего анализа и принятия решения по пунктам 5-7 алгоритма распознавания на основе метрики Хаусдорфа (см. описание способа).

Блок ББС 49 применяется для синхронизации приема во все параллельные входные регистры блока ПКБММ 48 очередных промежуточных значений величин удалений, вычисленных в шестнадцати АЭВМ 14-29 и кратковременно сохраняемых в их выходных буферных регистрах. Эта синхронизация необходима в связи с тем, что возможен небольшой нестабильный сдвиг во времени моментов параллельной записи данных в названные выходные регистры АЭВМ 14-29, а известный пирамидально-конвейерный блок ПКБММ 48 построен по принципу синхронного конвейера и требует синхронной подачи множества входных операндов.

Устройство может выполнять следующие функции.

Первая функция: ограничение доступа и аутентификация личности.

В графический буфер ОП 6 ГМЭВМ 2 помещается изображение распознаваемого отпечатка пальца. После предварительной обработки паспорт архивного отпечатка пальца в виде выделенных ключевых точек помещается в ОП 6. После процедуры сравнения анализируется только первый бит регистра результата. После завершения аутентификации устройство возвращается в исходное состояние.

Вторая функция: идентификация.

В режиме идентификации требуются небольшая модификация алгоритма работы устройства 1 и увеличение в ГМЭВМ 2 емкости памяти фрагмента базы данных для хранения требуемых архивных отпечатков. Паспорта архивных отпечатков пальцев формируются аналогично режиму аутентификации. Результаты сравнения архивных отпечатков с запросным записываются в поле итогов базы данных, где значения первых битов каждого результата является кодом события преодоления порога. Наименьшее значение вычисленной степени близости и номер архивного отпечатка, на котором оно получено, хранится в регистре результата. После окончания анализа базы данных отпечатков пальцев можно отобрать все архивные отпечатки, на которых был преодолен порог, или использовать значение из регистра результата.

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