СПОСОБ ФОРМИРОВАНИЯ И ВЕРИФИКАЦИИ БИОМЕТРИЧЕСКОГО КОДА ОТПЕЧАТКА ПАЛЬЦА
METHOD OF CREATING AND VERIFYING FINGERPRINT BIOMETRIC CODE

Изобретение относится к области распознавания, представления и воспроизведения данных, а именно способам считывания и распознавания напечатанных или написанных знаков или распознавания образов, в частности отпечатков пальцев и формирования их биометрических кодов.
Известен способ формирования и верификации биометрического кода (заявка US 2007/0036401 A1 "System for recognition fingerprint image, method and program for the same", 15 февраля 2007 года), предусматривающий преобразование папиллярного узора отпечатка пальца в электронный вид, обработку его электронного изображения, определение аргументов функции биометрического кода папиллярного узора - координат минуций, которые сравниваются с предварительно сформированным набором координат минуций эталонного отпечатка.
Недостатком данного способа является то, биометрический код формируется в виде набора координат минуций в чистом виде, а следовательно, большое количество вычислительных операций необходимо выполнять на этапе сравнения биометрических кодов. Кроме того, данный способ неустойчив к равномерным сжатиям/растяжениям изображения отпечатка.
Известен способ формирования биометрического кода (заявка US 2004/0252868 A1 "Method and device for matching fingerprints", 16 декабря 2004 года), предусматривающий преобразование папиллярного узора отпечатка пальца в электронный вид, обработку его электронного изображения, определение аргументов функции биометрического кода папиллярного узора - квадратных областей электронного изображения и последующую его верификацию.
Недостатком данного способа является то, что биометрический код формируют в виде набора квадратных областей изображения, а следовательно, большое количество вычислительных операций необходимо выполнять на этапе сравнения биометрических кодов. Кроме того, данный способ неустойчив к поворотам изображения отпечатка.
Наиболее близким по своей технической сущности является способ формирования биометрического кода по международной заявке WO 2008/030166 A1 "A method, an apparatus, and a computer program product within fingerprint matching". Способ-прототип заключается в том, что преобразуют папиллярный узор отпечатка пальца в электронный вид, обрабатывают его электронное изображение, определяют координаты минуций папиллярного узора, запоминают их, определяют аргументы функции биометрического кода папиллярного узора, по которым формируют его биометрический код.
По сравнению с аналогами способ-прототип обеспечивает устойчивость к равномерным сжатиям/растяжениям изображения и поворотам отпечатка.
Однако ближайший аналог имеет относительно низкую надежность кода, обусловленную тем, что в нем не учитывают возрастания вероятности появления ложных минуций при удалении от центра электронного изображения отпечатка. Низкая надежность связана также с необходимостью выполнения большого числа операций на этапе сравнения биометрических кодов и отсутствием избыточности.
Целью заявленного технического решения является разработка способа формирования и верификации биометрического кода отпечатка пальца, обеспечивающего более высокую надежность кода, уменьшение количества операций, выполняемых на этапе сравнения кодов, формирование кода с учетом того, что вероятность появления ложных минуций возрастает при удалении от центра электронного изображения отпечатка.
пор
пор
пор
n
n
n
порог.
порог
порог.
порог
Поставленная цель достигается тем, что в известном способе формирования и верификации биометрического кода отпечатка, содержащего N минуций, заключающимся в том, что преобразуют папиллярный узор отпечатка пальца в электронный вид, обрабатывают его электронное изображение, определяют координаты минуций папиллярного узора, запоминают их, определяют аргументы функции биометрического кода папиллярного узора, по которым формируют его биометрический код, при обработке электронного изображения папиллярного узора (ПУ) бинаризируют его. Бинаризация изображения ПУ заключается в его фильтрации, сращивании имеющихся на нем ложных разрывов, удалении ложных слияний линий и выравнивании пикселей электронного изображения относительно предварительно заданного порога интенсивности И пикселей, который выбирается в пределах 60÷100, причем пиксели с интенсивностью ниже предварительно заданного порога И преобразуют в черные, а пиксели с интенсивностью выше предварительно заданного порога И преобразуют в белые. Затем формируют остов бинарного электронного изображения путем утончения его линий до заданной толщины Δ, равной одному пикселю. После определения координат x, y N минуций, где n=1, 2,…,N, на остове папиллярного узора вычисляют центр их масс С по формуле . Для определения аргументов функции биометрического кода выделяют 2≤K≤N сердцевин папиллярного узора, для чего для n-й минуции вычисляют ее удаление S от центра масс С, а в качестве К сердцевин принимают К минуций с наименьшими значениями их удалений S от центра масс С. Затем от каждой k-й сердцевины, где k=1, 2,…, K, строят деревья к остальным J=N-1 минуциям, вычисляют длины ребер  каждого k-го дерева, где j=1, 2,…, J, и ранжируют их, рассчитывают аргументы кучности минуций с сердцевинами путем вычисления соотношений длин ребер  каждой k-й сердцевины и углов  между j-м и r-м ребром, а биометрический код папиллярного узора формируют в виде , причем значение r и r' выбирают равным j+1. Для верификации биометрического кода сравнивают данный биометрический код с предварительно сформированным эталонным биометрическим кодом путем вычисления степени их схожести W и сравнения с предварительно заданным значением порога схожести биометрических кодов WПредварительно заданный порог схожести деревьев W выбирают в интервале 1÷К, а значение степени схожести W рассчитывают как количество попарно равных деревьев из двух биометрических кодов, причем два дерева считают равными, если количество попарно равных их элементов превышает предварительно заданный порог схожести деревьев UПредварительно заданный порог схожести деревьев U выбирают в интервале 1÷J.
Благодаря новой совокупности признаков в заявленном способе снижается вероятность появления ложных минуций, так как формирование кода учитывает несколько сердцевин, находящихся в центральной части электронного изображения ПУ, а также необходимые вычислительные операции до сравнения кодов, что обеспечивает повышение надежности биометрического кода отпечатка пальца и времени, необходимого для его верификации.
Заявленный способ поясняется изображениями, на которых показаны:
фиг.1 - изображение отпечатка пальца в электронном виде;
фиг.2 - изображение отпечатка пальца после фильтрации;
фиг.3 - изображение отпечатка пальца после сращивания ложных разрывов и удаления ложных слияний;
фиг.4 - бинарное изображение отпечатка пальца;
фиг.5 - остов бинарного изображения отпечатка пальца;
фиг.6 - минуции на остове бинарного изображения отпечатка пальца;
фиг.7 - сердцевины на остове бинарного изображения отпечатка пальца;
фиг.8 - дерево от сердцевины к остальным минуциям;
фиг.9 - биометрический код в матричном представлении.
Заявленный способ реализуется следующим образом.
Известные способы формирования биометрического кода отпечатка пальца, как правило, основаны на определении координат минуций и преобразовании их значений в некоторый набор данных (см. David Maltoni, Handbook of fingerprint recognition, изд. Springer 2003 г., стр.83). Как правило, в структуре изображения могут появляться ложные минуции, причем с вероятностью, возрастающей при увеличении смещения от центра изображения, для увеличения скорости обработки коды упрощают, при этом на этапе верификации появляется большая вычислительная нагрузка, а надежность кода падает.
Отмеченное указывает на существование проблемы разработки технических решений, обеспечивающих формирование биометрического кода с учетом уменьшения точности координат минуций при увеличении их расстояний от центра изображения, повышение надежности кода и проведение всех расчетных операций до верификации кода.
Отмеченная задача решается в заявленном способе следующим образом.
Электронный вид изображения папиллярного узора отпечатка пальца, показанный на фиг.1, представляет собой растровый рисунок с интенсивностями пикселей в диапазоне 0÷255 (см. стандарт ANSI, www.ansi.com, обращение 19.01.2009), на котором пикселями с меньшей интенсивностью представлены бороздки отпечатка - линии папиллярного узора 1, а пикселями с большей интенсивностью - фон. Исходное изображение содержит высокочастотные помехи - шум и ложные разрывы линий 2 и ложные слияния линий 3 (см. фиг.2), вызванные неплотным прилеганием пальца к поверхности сканирующего устройства.
Технология удаления шума на изображении известна. Для этого его обрабатывают низкочастотным фильтром, например с ядром Гаусса (см. Л.Шапиро, Дж Стокман. Компьютерное зрение, изд. БИНОМ 2006 г., стр.196). Результат такого преобразования представлен на фиг.2.
Для исправления ложных разрывов линий 2 и ложных слияний линий 3 применяют известную технологию (см. Sharat Chikkerur, Alexander N. Cartwright "Fingerprint image enhancement using STFT analysis", Center of unified biometrcis and sensors. University at Buffalo, NY, USA, 2003 г.): определяют локальную ориентацию линий и выполняют фильтрацию ядром Габора, результат которой приведен на фиг.3.
порог
порог
порог
Для выравнивания интенсивностей пикселей И выполняют пороговую обработку изображения (см. Л.Шапиро, Дж Стокман. Компьютерное зрение, изд. БИНОМ, 2006 г., стр.116), результат которой представлен на фиг.4. При этом пиксели с интенсивностью ниже предварительно заданного порога И<И преобразуют в черные, а пиксели с интенсивностью выше предварительно заданного порога И>И преобразуют в белые. Исходя из диапазона возможных значений интенсивностей пикселей, наилучшее качество бинарного изображения достигается при И=60÷100.
Затем для упрощения процесса поиска минуций выполняют построение остова бинарного изображения, показанного на фиг.5, путем утончения его линий до заданной толщины Δ. Толщину линий остова 8 обычно выбирают равной одному пикселю. (Я.А.Фурман, А.Н.Юрьев, В.В.Яшин. Цифровые методы обработки и распознавания бинарных изображений, Издательство Красноярского университета 1992 г., стр.192).
n
n
n
max
n
max
max
max
На остове бинарного изображения определяют координаты минуций 9 (x, y), расположенных в точках, в которых линии остова 8 раздваиваются или заканчиваются (см. стандарт ANSI, www.ansi.com, обращение 19.01.2009), запоминают их координаты. Размер координатной сетки определяется интервалами x=0, 1,…, X, y=0, 1,…, Y, где X и Yвыбирают в интервале 200-500 пикселей (см. стандарт ФБР, www.fbi.com, обращение 15.01.2009).
n
Для того чтобы наибольшее влияние на биометрический код оказывали минуции, находящиеся ближе к центру электронного изображения, вычисляют центр масс минуций 11, изображенный на фиг.7, по формуле . Чтобы внести избыточность, повышающую надежность кода, для определения аргументов функции биометрического кода выделяют 2≤K≤N сердцевин 10 папиллярного узора, показанных на фиг.7 в виде концентрических кругов, для чего для n-й минуции 9 вычисляют ее удаление S от центра масс 11, а в качестве К сердцевин 10 принимают минуции с наименьшими значениями их удалений S от центра масс 11.
порог
порог
порог
Затем чтобы все параметры, составляющие биометрический код, были относительные, что делает код устойчивым к поворотам, сдвигам и равномерным сжатиям/растяжениям электронного изображения ПУ, от каждой k-й сердцевины 10, где k=1, 2,…, K, строят ребра деревьев 12 к остальным J=N-1 минуциям 9. Одно из таких деревьев представлено на фиг.8. Вычисляют длины ребер 12  каждого k-го дерева, где j=1, 2,…, J, и ранжируют их. Рассчитывают аргументы кучности минуций с сердцевинами путем вычисления соотношений длин ребер 12 , каждой k-й сердцевины и углов , между j-м и r-м ребром, а биометрический код папиллярного узора формируют в виде , который представляет собой матрицу размерности K×J, показанную на фиг.9. Верификацию данного биометрического кода с предварительно сформированным эталонным биометрическим кодом реализуют следующим образом. Вычисляют степень схожести данного и эталонного биометрического кода W и сравнивают с предварительно заданной величиной порога схожести биометрических кодов W, где W выбирают в интервале 1÷К. При этом степень схожести W рассчитывают как количество попарно равных деревьев из двух биометрических кодов. Два дерева считают равными, если количество попарно равных их элементов превышает предварительно заданный порог схожести деревьев U, который выбирают в интервале 1÷J.
За счет выбора сердцевин сформированный биометрический код в большей степени подвержен влиянию минуций, находящихся ближе к центру электронного изображения. Все параметры, составляющие биометрический код, относительные, что делает код устойчивым к поворотам, сдвигам и равномерным сжатиям/растяжениям электронного изображения ПУ, а также исключает необходимость выполнения расчетных операций на этапе сравнения кодов. Этим и обусловлено достижение сформулированного технического результата - обеспечение более высокой надежности кода, уменьшения количества операций, выполняемых на этапе верификации кода, формирование кода с учетом того, что вероятность появления ложных минуций возрастает при удалении от центра электронного изображения отпечатка.