Методы, алгоритмы и программное обеспечение интеграции биометрических информационных технологий

Lu(x,y,z,t) = -f(x,y,z),(2.1).

где L следующий дифференциальный оператор:

L = /iV2+(A + //)Vdiv-/7-^T,(2.2)

u -- вектор смещений; f - внешняя сила; р -- плотность; t -- время;

коэффициенты упругости Ламе X и ц могут быть выражены через модуль Юнга Е и коэффициент Пуассона.

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

Это означает, что частная производная j-f равна нулю. Следовательно, решение не зависит от времени, то есть u(^,<y,z,/) = u(x,<y,z).

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

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

Далее рассматриваются два метода решения уравнения (2.5) -- методом конечных элементов и методом свертки.

Решение методом конечных элементов (МКЭ)

Тензор давлений вычислен в предположении о линейной зависимости между натяжением и давлением.

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

Два независимых коэффициента сх и с4 определяются внутренними свойствами кожи.

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

Р,+и(р,) = Ч

где {р,} -- набор точек первого изображения, {q,} -- набор точек второго изображения. Рассмотрим следующий аналог функционала энергии:

W(u) = Ed(u)+es(u)

Коэффициент 0 показывает «вес» каждой из компонент энергии. Физически функционал энергии соответствует силам, действующим в направлениях смещений опорных точек.

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

Приведем схему МКЭ минимизации функционала (2.14). Пусть функция смещений задана на равномерной прямоугольной сетке с координатами узлов:

*і=-Ч;yj=-Sy

На плотной сетке размерность вектора и слишком большая, поэтому точные методы решения такого уравнения вычислительно очень трудоемкие В таком случае предпочтительнее использовать итеративные процедуры, например, метод Зейделя или метод Якоби [85,86] (реальное тестирование показывает, что метод Якоби расходится). Учитывая разреженность матрицы А (не более Збпт ненулевых элементов из 4(п+1) (т+1)) и ее структурированность по элементам разбиения проектируются очень быстрые алгоритмы. Описание алгоритмов вынесено в Приложение.

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

В качестве критерия сходимости рассматривается невязка Аиг -- 11, деленная на число элементов -- такой критерий наиболее близок как к максимуму поточечного отклонения от решения, так и к визуальной оценке качества учета деформаций. На рисунке 2.4 приведены скорости сходимости метода Зейделя и градиентного метода по итерациям в зависимости от точности и количества элементов. На рисунке 2.5 приведены скорости сходимости по времени. Скорость сходимости измерялась на изображениях отпечатков размера 288x400.

Рисунок 2.4 - Скорость сходимости по итерациям итеративных методов учета деформаций

Рисунок 2.5 - Скорость сходимости по времени итеративных методов учета деформаций (Intel Pentium III, 733Mhz)

В таблице 2.4 приведены результаты тестирования приведенного метода учета нелинейных деформаций на базах отпечатков FVC2002 [45].

Таблица 2.4. Количественные показатели качества учета деформаций

База	Среднее изменение меры при прямом наложении изображений	Среднее изменение расстояния между минюциями
	«свои»	«чужие»	«свои»	«чужие»
DB1	+55%	+1%	-112%	-36%
DB2	+36%	+4%	-76%	-38%
DB3	+89%	+2%	-65%	-22%
DB4	+76%	+3%	-89%	-34%

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

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

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

Рисунок 2.6 - Использование векторов смещений в реализации классического алгоритма распознавания с учетом нелинейных деформаций

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

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

2.4 Анализ эффективности автоматического учета деформаций

В качестве тестового массива использовались, 4 базы данных отпечатков пальцев FVC2002 [45]. Для тестирования классического алгоритма распознавания по отпечаткам пальцев был взят алгоритм компании Biolink [88]. В качестве тестового корреляционного алгоритма рассматривался алгоритм, описанный в подразделе 2.1.

Дадим краткое описание используемых баз. Все базы FVC2002 [45] содержат информацию о 100 субъектов, по 8 изображений на каждого.

Всего сравнений «свой» 2800, «чужой» 316800 (для анализа рассматривались только 4950 сравнений, по одному изображению из каждого набора, чтобы избежать лишних корреляции).

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

Рисунок 2.8 - Примеры отпечатков пальцев из различных баз FVC2002

Таблица 2.5. Характеристики тестовых массивов отпечатков пальцев FVC2002

База	Сканер	Размер	Разрешение	Размер базы
DBla	Оптический "TouchViewII" Identix	388x374	500 dpi	100x8
DB2a	Оптический "FX200" Biometrika	296x560	500 dpi	100x8
DB3a	Емкостной "100SC" Precise Biometrics	300x300	500 dpi	100x8
DB4a	SFinGe v.2.51'	288x384	-500 dpi	100x8

На рисунках 2.9 - 2.11 приведены показатели качества алгоритмов с интегрированным алгоритмом учета деформаций на этапе регистрации. Учет деформаций на этапе сравнения рассматривается как интеграция различных алгоритмов в подразделе 4.3.

База FVC2002 DB4 является синтетической. Отпечатки созданы программой Synthetic Fingerprint Generator (SFinGe) [66,67].

Рисунок 2.9 - Корреляционный алгоритм с компенсацией деформаций'

Рисунок 2.10 - Классический алгоритм с компенсацией деформаций на этапе регистрации

Рисунок 2.11 - Показатели качества распознавания по прямой корреляции отпечатков в области пересечения с учетом и без учета нелинейных деформаций



3. Синтез комбинированных мер сходства

3.1 Статистические аспекты интеграции биометрических технологий

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

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

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

Теоретически при известных совместных распределениях результатов различных биометрических тестов, оптимальный численный интегральный критерий может быть построен на основании результатов теоремы Неймана-Пирсона [89]. А именно оптимальными (обеспечивающие минимальное значение ошибки 1-го рода при фиксированном уровне ошибки 2-го рода) разделяющими поверхностями являются гиперповерхности, на которых отношение плотности распределения вероятностей «на своих» к плотности распределения вероятностей «на чужих» постоянно.

Однако на практике прямое применение теоремы Неймана-Пирсона сопряжено со значительными трудностями. А именно:

1)Результат работы автоматической биометрической системы является дискретным. Следовательно, предварительно может оказаться необходимым приблизить дискретное распределение непрерывным.

2)Получаемые операционные кривые (ROC) и интегральные показатели работы (FAR, FRR) не являются плотностями меры сходства «на своих» и «на чужих», а могут рассматриваться лишь как статистические оценки соответствующих величин. При тестировании на небольших базах доверительный интервал для значений плотности оказывается довольно широким, что делает применение теоремы Неймана-Пирсона практически нецелесообразным.

Для изучения свойств комбинированных мер сходства и статистических критериев качества работы комбинированных систем введем следующие обозначения:

s = (s_l,...,s_n) - элемент признакового пространства, вектор результатов работы интегрированной БТ;

fL_P{^sk) " плотность распределение k-го признака «на чужих» (impostor);

fgen(^sk)" плотность распределение k-го признака «на своих» (genuine);

fim_P{^s) " совместная плотность распределение вероятности «на чужих»;

f_gen{^s) " совместная плотность распределение вероятности «на своих»;

В общем случае функции f_imp и f удобно считать обобщенными функциями.

Произвольный численный многомерный критерий может быть рассмотрен как параметризованное семейство {DA}, Л є Л, областей признакового пространства. А именно при фиксированном значении Л, если ssDA, тогда субъект принимается. Соответственно, интегральные характеристики FAR и FRR могут быть определены как

FAR{X)= jf_imp{v)dv;

FRR(A) = l- \fjy)br

В случае, если требования к ошибкам первого и второго рода известны, то можно ограничится выбором одного значения Л, при котором данные требования удовлетворяются.

Более распространенной является ситуация, при которой требуется параметризация семейства {Dx} ОДНИМ действительным числом (т.е. ЛеК),обычно интерпретируемым как «жесткость» критерия. Чем «жестче» критерий, тем ниже ошибка 2-го рода, и как следствие выше ошибка 1-го рода. В таком случае естественным является требование:

при Л>/л. Тогда функции FAR(X) И FRR(X) являются монотонными

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

AN = -\ogl0FAR{Z)

при неоднозначном выборе Л (т.е. когда для разных Л ошибка 2-го рода одинакова) в семействе подмножеств достаточно оставить подмножество, обеспечивающее минимальное значение ошибки 1-го рода.

Л. = |"1/„(»)//,-«*4

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

Несмотря на то, что функции плотностей распределения вероятностей «на своих» и «на чужих» входят симметрично в условия оптимальности критерия, на практике методики их определение существенно отличаются.

Основными причинами является следующее:

1)Размер выборки. Пусть в распоряжении имеется тестовый массив, содержащий по к записей п субъектов (количество записей обычно колеблется в пределах от 2 до 10 и значительно меньше количества субъектов). Тогда размер выборки «по своим» равен 0.5к(к -- \)п, а размер выборки «по чужим» можно считать от 0.5л(и-1), если брать по одной записи для каждого субъекта, чтобы избежать появление ненужных корреляций, до 0.5к2п(п -- 1), если рассматривать все записи.

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

2)Распределение «на чужих» является довольно объективной технологической характеристикой функционирования системы и в основном зависит от технических характеристик используемых устройств и алгоритмов сравнения.

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

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

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

3.2 Оптимальная интеграция независимых биометрических технологий

Результаты тестирований биометрических технологий, проводимых до настоящего времени, не позволяют с полной уверенностью утверждать о статистической независимости результатов различных биометрических измерений. Для подтверждения или опровержения данного предложения необходимо иметь огромный тестовый массив биометрических измерений, которым на данный момент не обладает ни одна организация [3,6,15].

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

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

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

/^W=/iW«/ifc);

/^W=/i,W-/i.(0.-

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

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

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

1)недостаточным размером выборки;

2)функциональной ошибкой в алгоритме;

3)наличием грубых ошибок в тестовом массиве.

Последние две проблемы не могут быть устранены в автоматическом режиме.

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

1)заменить максимальным значение слева (АНМС Мах);

2)заменить минимальным значение справа (АНМС Min).

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

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

max\F(x)-F(x]<^

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

Изучим влияние неточностей в определении эмпирической плотности на статистические показатели ошибок 1-го и 2-го рода комбинированной меры сходства.

Рассмотрим следующую схему эксперимента:

1)Выбор подмножества тестового массива

2)Определение комбинированной меры сходства по подмножеству

3)Сравнение ошибок 1-го и 2-го рода на всем тестовом массиве в зависимости от используемой выборки.

Такой подход к тестированию биометрической технологии соответствует основных требованиям к тестированию биометрических систем, систематизированным Д. Вейманом [3,15]. В целом результаты такого тестирования можно оценить теоретически. Однако в данной работе используются методы статистического моделирования.

Статистическое моделирование ошибок при использовании малых выборок проводилось на основе результатов тестирований технологий распознавания по форме лица FRVT2002 [47] и технологий распознавания по отпечаткам пальца NIST VTB (2002г.) [46].

Результаты такого тестирования показывают, что для получения меры сходства, устойчивой при уровне ошибки 2-го рода 10'к, требуется настроечный массив из примерно 10к. Графики дрейфа ошибок при настройке на выборках размера 500, 1000, 5000 и 10000 на рисунках 3.1-3.3.

Рисунок 3.1 - Дрейф ошибок при использовании малых выборок для АНМС Мах

Рисунок 3.2 - Дрейф ошибок при использовании малых выборок для АНМС Мах

Рисунок 3.3 - Дрейф ошибок при использовании малых выборок для АНМС Мах

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

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

Однако, как было отмечено выше в задаче предварительного анализа обычно доступна только информации о зависимости ошибок 1-го и 2-го рода, т.е. известна функция FRR(FAR) = w(x) или FRR(ln(FAR)) = w^ (х). Тогда для определения точки операционной кривой, соответствующей какому-либо значению адаптивной нормализованной меры сходства достаточно знать функцию w (или win) зависимости FRR от FAR.

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

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

3.3 Условно оптимальная интеграция биометрических технологий

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

s_N=-log_l0(l-F_imp(s)),

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

F_impM = e-^MOs»

Так как обычно точное распределение неизвестно, нормализацию проводят по данным тестирования на достаточно большой выборке:

s„=-log_l0FAR{s)

Безусловно, данный способ стандартизации меры сходства не единственный. Можно, например, преобразовать меру сходства, чтобы добиться нормального распределения «на чужих». Однако практика показывает, что использование экспоненциального распределения более целесообразно.

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

Рисунок 3.4 - Характерный вид функций плотности распределения меры сходства «на своих» (Fgen) и «на чужих» (Fimp)

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

Рассмотрим простейший пример параметризации распределения «на своих». Предлагается в области непрерывности приближать плотность куском нормального распределения:

[[s-mf

f_gen(s) = ce *°^г

Обозначим верхнюю границу области непрерывности через s^, нижнюю - через smin, вероятности того, что мера сходства принимает нулевое и предельное максимальное значение, через р0 и рНт соответственно. Обозначая индикатор области непрерывности через Хс> плотность распределения меры сходства «на своих» на всей области значений можно записать следующим образом:

fgen(^S)=^S(s)P0+^{Ce 2а2} Zc(^S)^+S(^S-^S\im)P\im>

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

-optv³/^-111 2-і \ fb_VKV_J

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

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

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



Список литературы

1.Federal Bureau of Investigation, "The FBI Fingerprint Identification Automation Program: Issues and Options", U.S. Government Publication, U.S. Congress, Office of Technology Assessment, Washington, DC, 1991.

2.N. Kingsbury, Technology Assessment: Using Biometrics for Border Security. DIANE Publishing Co., 2003.

3.James Wayman et al. Biometric Systems: Technology, Design and Performance Evaluation. Springer Verlag, 2004.

4.Monrose F., Reiter M.K., Li Q. and Wetzel S., "Cryptographic Key Generation From Voice", in Proc. Symp. On Security and Privacy, pp.202-213, 2001.

5.Monrose F., Reiter M.K., and Wetzel S., "Password Hardening Based on Keystroke Dynamics" in Proc. Computer and Communications Security Conf. (6th), 1999.

6.P. Griffin, "Topics for Multi-Biometrics Research" // Panel Discussion MMUA'2003. http://mmua03 .cs.ucsb.edu

7.Jain A.K., Hong L., Pankanti S. and Bolle R, "An Identity-Authentication System Using Fingerprints", Proc. of IEEE, 1997, 85(9), pp. 1365-1388.

8.Daugman J., "The Importance of Being Random", Pattern Recognition, vol.36, no.2, 2003.

9.J. Ashbourn, Practical Biometrics: From Aspiration to Implementation. Springer Verlag, 2003.

10.Daugman J., Recognizing Persons by Their Iris Patterns, in Biometrics: Personal Identification in a Networked Society, A.K. Jain, R.Bolle, and S.Pankanti (edt), Kluwer Academic, New York, 1999.

11.Halici U., Jain L.C., Erol A., Introduction to Fingerprint Recognition, Intelligent Biometric Techniques in Fingerprint and Face Recognition, CRC Press, 1999.

12.Large & Medium Scale ID, online available at: www.biolinkUSA.com.

13.Civil Fingerprint Identification Systems, online available at: www.east-shore.com.

14.www.civilidsystems.com.

15.J. Wayman. "Biometric Testing Celebrating 35+ Years"// Panel Discussion MMUA'03. http://mmua03 .cs.ucsb.edu

16.John D. Woodward, Jr. "Biometrics: Facing Up to Terrorism", The Biometric Consortium Conference 2002, Arlington, February, 2002.

17.Соколов A.B., Шаныгин В.Ф., Защита информации в распределенных корпоративных сетях и системах. - М.: ДМК, 2002. - 656с.

18.Программно-аппаратные средства обеспечения информационной безопасности. Защита программ и данных: Учебное пособие для вузов / Белкин П.Ю., Михальский О.О., Першаков А.С. и др. - М: Радио и связь. -1999.-168 с.

19.Чмора А.Л. Современная прикладная криптография. - М.: Гелиос АРВ. -2001.-256 с.

20.Петров А.А. Компьютерная безопасность. Криптографические методы защиты. -М: ДМК, 2000. - 448 с.

21.Beardsley, Chartles Т., Is your computer insecure?, IEEE Spectrum, Jan, 1972,pp.67-78.

22.S.Reed and D. Branstad, Controlled Accessibility Workshop Report, NBS Tech. Note 827, May, 1974.

23.J. Wegstein "Automated Fingerprint Identification", NBS Tech. Note 538, Aug. 1970.

24.Lee H.C. and Gaenssley R.E., Advances in Fingerprint Technology, Elsevier, New York, 1991

25.Eleccion M., "Automatic Fingerprint Identification", IEEE Spectrum, 1973, 10, pp. 36-45.

26.B. Dalrymple, Fingerprints (Dactyloscopy) Identification and Classification in Encyclopedia of Forensic Science, Siegel, J. et al., Eds., Academic Press, New York, 2000, 872.

27.Federal Bureau of Investigation, "The Science of Fingerprints: Classifications and Uses", U.S. Government Publication, Washington, DC, 1984.

28.Henry E. "Classification and Uses of Finger Prints", Routledge, London, 1900.

29.Jain A.K., Hong L. and Bolle R., "On-Line Fingerprint Verification", IEEE Trans. On Pattern Analysis and Machine Intelligence, 1997, 19(4), pp. 302-314.

30.BiometricsinDriver'sLicenseOperations. http://www.biometricgroup.com/dl_id_operations.pdf

31.Biometric Consortium, http://www.biometric.org

32.International Biometric Group, http://www.biometricgroup.com

33.BioAPI Consortium, http://www.bioAPI.org

34.International Biometric Industry Association, http://www.IBIA.org

35.Официальный сайт русского биометрического общества http://www.biometricsguide.ru

36.Biometrics Application Programming Interface www.parallaxresearch.com/ ataclips/pub/infosec/biometrics/bapi_20overview.pdf

37.HAAPI 2.0. www.biometrics.org/REPORTS/HAAPI20/

38.Roles for the National Institute of Standards and Technology (NIST) in Accelerating the Development of Critical Biometric Consensus Standards for US Homeland Security and the Prevention of ID Theft, March 11, 200 available at http://www.itl.nist.gov/div895/biometrics/documents/WhitePaper%20Roles%20for %20NIST%20FP&MH%20Marchll%202003.PDF

39.ANSI INCIST 358-2002.

40.ANSI, "Fingerprint Identification - Data Format for Information Interchange", American National Standards Institute, New York, 1986.

41.National Institute of Standards and Technology, "Data Format for the Interchange of Fingerprint Information", U.S. Government Publication, Washington, DC, 1991.

42.National Institute of Standards and Technology, "Guideline for the Use of Advanced Authentication Technology Alternatives", Federal Information Processing Standards 190,1994.

43.Crypto API. http://CryptoAPI.sourceforge.net

44.First International Competition for Fingerprint Verification Algorithms (FVC2000), http://bias.csr.unibo.it/fVc2000/.

45.FVC2002, the Second International Competition for Fingerprint Verification Algorithms (FVC2002), http://bias.csr.unibo.it/fVc2002/.

46."Studies of Fingerprint Matching Using the NIST Verification Test Bed (VTB)" available at ftp://sequoyah.nist.gov/pub/nist internal reports/ir 7020.pdf

47.Face Recognition Vendor Test, http://www.frvt.org

48.Fingerprint Vendors Technology Evaluation, http://fbvte.nist.gov

49.FVC2004, the Third International Competition for Fingerprint Verification Algorithms (FVC2004),, http://bias.csr.unibo.it/fVc2004/

50.T. Mansfield et al. "Biometric Product Testing Final Report". UK BiometricsWorkingGroup,2001, http://www.cesg.gov.uk/site/ast/biometrics/media/BiometricTestReportptl.pdf

51.A.J. Mansfield and J.L. Wayman "Best Practices in Testing and Reporting Performance of Biometric Devices". UK Biometrics Working Group, 2002.

52.L.G. Kersta "Voiceprint Identification", Nature, vol. 196, Dec. 29, 1962, pp. 1253-1257.

53.O. Tosi, Experimental Studies on the reliability of the voiceprint identification technique, Proc. of 3rd National Symposium on Law Enforcement and Technology, 1970.

54.A.J. Goldsten, L.D. Harmon, and A.B. Lesk "Identification of Human Faces", Proc. IEEE, 59(5), May, 1971

55.L.D. Harmon "The recognition of Faces", Scientific American 229(5), 1973.

56.W. Haberman and A. Fejfar "Automatic ID of personnel through Speaker and Signature verification - System Description and Testing", 1976 Carnahan Conference on Crime Countermeasures, U of KY, May 1976.

57.A. Fejfar and J. Myers, "The Testing of 3 Automatic ID Verification Techniques of Entry Control", 2nd International Conf. on Crime Countermeasures, Oxford, July, 25-29, 1977.

58.A. Fejfar, "Combining Techniques for Improve Security in Automated Entry Control", 1978, Carnahan Conf. On Crime Countermeasures, Mitre Corp. MTP-191, May 1978

59."Guidelines for Evaluation of Techniques for Automated Personal Identification", NBS, FIPS Pub. 48, April 1977

60.Davide Maltoni, Dario Maio, Anil K. Jain, Salil Prabhakar. Handbook of Fingerprint Recognition. Springer Verlag, New York, 2003

61.FAC(withFVC04)

62.SVC (with FVC04)

63.R. Chellapa, C. Wilson, and S.Sirohey, Human and Machine Recognition of Faces: a Survey, Proc. Of IEEE, 83(5), pp. 705-741, 1995

64.V. Blanz and T. Vetter, A Morphable Model for Synthesis of 3D Faces. In Computer Graphics Proceedings SIGGRAPH, pages 187-194, Los Angeles, 1999

65.Genemation. www.genemation.com

66.SfmGe v.2.51. http://bias.csr.unibo.it/research/biolab/bio tree.html

67.R. Cappelli, A. Erol, D. Maio and D.Maltoni, Synthetic Fingerprint-Image Generation // Proc. ICPR2000, Barcelona, Sep. 2000

68.J.G. Daugman, US Patent No. 2591 260, U.S. Government Printing Office, Washington DC, 1994.

69.L. Flom and A. Safir, U.S. Patent No. 4641 349, U.S. Government Printing Office, Washington, DC, 1987

70.Delean Vision, www.delean.com

71.Cnews analytics, www.cnews.ru

72.Dieckmann U., Plankensteiner P. and Wagner Т., "SESAM: A Biometric Person Identification System Using Sensor Fusion", Pattern Recognition Letters, vol.18, pp. 827-833,1997.

73.L. Xu, A. Krzyzak and C.Y. Suen "Methods of Combining Multiple Classifiers and Their Applications To Handwriting Recognition", IEEE Trans. On SMC, 22(3), 1992, pp. 418-435.

74.J. Kittler, M. Haref, R.P.W. Duin and J. Matas, "On combining classifiers", IEEE Trans. On РАМІ, vol.20, no.3,1998, pp.226-239

75.Frischholz R.W., Dieckmann U., "BioID: A Multimodal Biometric Identification System", IEEE Computer, pp. 64-68, Feb. 2000.

76.Novikov S.O., Glushchenko G.N., "Fingerprint ridges structure generation models", 6th Int. Workshop on Digital Image Processing and Computer Graphics. Vienna, 20-22 Oct. 1997, Proc. SPIE, vol. 3346.

77.S. Pankanti, S. Prabhakar and A.K. Jain, "On the Individuality of Fingerprints", IEEE Trans. РАМІ, 2002, 24(8), pp. 1010-1025

78.Bazen A.M., Gerez S.H., "Thin-Plate Spline Modelling of Elastic Deformation in Fingerprints", Proceedings of 3rd IEEE Benelux Signal Processing Symposium, 2002.

79.Bookstein F.L., "Comment to D.G. Kendall's A survey of the statistical theory of shape", Statistical Science, vol.4, no. 2,1989, pp. 99-105.

80.M. Fornefett, K. Rohr and H.S. Stiehl, "Elastic Medical Image Registration Using Surface Landmarks with Automatic Finding of Correspondences", In A. Horsch and T. Lehmann, editors Proc. Workshop Bildverarbeitung fur die Medizinl, Informatik actuell, Munchen, Germany, Springer-Verlag Berlin Heidelberg, 2000, pp. 48-52.

81.M. Fornefett, K. Rohr and H.S. Stiehl, "Radial Basis Functions with Compact Support for Elastic Registration of Medical Images", Image and Vision Computing, 19 (1-2), 2001, pp. 87-96.

82.Raffaele Cappelli, Dario Maio, Davide Maltoni, "Modelling Plastic Distortion in Fingerprint Images", ICAPR2001, pp. 369-376.

83.Landau L.D., Lifshits E.M., "Theory of Elasticity: Course of Theoretical Physics", Butterworth-Heinemann Edition, 1995

84.Shames, I.H. and Pitarresi, J.M., Introduction to Solid Mechanics, Upper Saddle River, NJ, 2000.

85.Федоренко Р.П. Введение в вычислительную физику. -М.: изд-во МФТИ, 1994.-528с.

86.Бахвалов Н.И., Жидков Н.П., Кобельков Г.М., Численные методы. -- М.: Лаборатория базовых знаний, 2003.

87.Основные физические константы. Энергоатомиздат, 1991.

88.U.S. Patent No. 6282 304.

89.Neyman J. and E.S. Pearson (1933) On the problem of the most efficient tests of statistical hypotheses. Philos. Trans. Roy. Soc, London A, 231, p. 289-337.

90.Пугачев B.C., Синицын И.Н. Теория стохастических систем. - М.: Логос, 2000.

91.Пугачев B.C., Синицын И.Н. Стохастические дифференциальные системы. Анализ и фильтрация (2-е изд.). - М.: Наука, 1990.

92.Pugachev V.S., Sinitsin I.N., Stochastic Systems. Theory and Applications. Singapore, World Scientific, 2001.

93.C.Watson, NIST Special Database 14: Mated Fingerprint Card Pairs 2, CD-ROM & documentation, September 1993.

94.C.Watson, NIST Special Database 29: Plain and Rolled Images from Paired Fingerprint Cards, CD-ROM & documentation, November 2001.

95.Richard O. Duda, Peter E. Hart, Pattern Classification and Scene Analysis. -John Wiley & Sons, New York, 1973.

96.Kohonen T. "Self-Organization and Associative Memory", Series in Informatic Sciences, vol. 8. Springer Verlag, 1984.

97.M. Pelillo, K. Siddiqi, S.W. Zucker, Matching Hierarchical Structures Using Association Graphs // IEEE Trans. РАМІ, v.21, NO.ll, November 1999, p.1105-1120.

98.Т. Павлидис, Алгоритмы машинной графики и обработки изображений. - М.: Радио и связь, 1986. - 400с.

99.У. Претт, Цифровая обработка изображений. - М. Мир, 1982. - 792с.

100.M.S. Grewal, А.Р. Andrews, Kalman filtering: Theory and Practice, Prentice Hall, 1993.-383 с

101.Васильев K.K., Крашенинников В.P., Синицын И.Н., Синицын В.И. Технологии обработки сигналов и изображений в информационных и управляющих системах // Наукоемкие технологии, №3, 2002, т.З. С. 4-23.

102.Тематический выпуск памяти B.C. Пугачева // АиТ, №11, 1998.

103.Grewal M.S., Weill L.R. and Andrews A.P. Global Positioning Systems, Inertial Navigation, and Integration. - John Wiley & Sons, 2000. - 392c.

104.Микаэлян А.Л. Оптические методы в информатике. - М.: Наука, 1990.

105.Валях Е. Последовательно-параллельные вычисления, - М.: Мир, 1985.

106.Тербер К. Дж., Архитектура высокопризводительных вычислительных систем, - М.: Наука, 1985.

107.J. Joseph, С. Fellenstein, Grid Computing. - Prentice Hall, 2003.

108.Burtsev V.S., Fyodorov V.D. Associative memory of new generation supercomputers based on optical information processing principles // Holography and Optical Informational Processing, 1991, v. 1731, p.201-216.

109.Kautz W.H., Pease M.C. Cellular Logic-in-Memory Arrays.. - 1971, November, AD763710.

ПО. Бурцев B.C. Система массового параллелизма с автоматическим распределением аппаратных средств суперЭВМ в процессе решения задачи. Юбилейный сборник трудов ОИВТА РАН. М. 1993. т.2, С.5-27.

111.Бурцев B.C. Выбор новой системы организации выполнения высокопараллельных вычислительных процессов, примеры возможных архитектурных решений построения суперЭВМ // В сб.: B.C. Бурцев. Параллелизм вычислительных процессов и развитие архитектуры суперЭВМ, М., 1997, С. 41-78.

112.Бурцев B.C. Новые принципы организации вычислительных процессов высокого параллелизма // Труды Первой Всероссийской конференции «Методы и средства обработки информации», М.: МГУ, 2003, С. 17-31.

113.Andrews H.C., Caspari К., A Generalized Technique for Spectral Analysis, IEEE Trans. Computers, C-19,1, 16-25 (January 1970).

114.J.R. Parker, Algorithms for Image Processing and Computer Vision. - John Wiley & Sons, New York, 1996.

115.B.H. Малоземов, СМ. Машарский, Основы дискретного гармонического анализа. - Спб.: 2003. 228 с.

11*6. Standard Performance Evaluation Corporation, http://www.spec.org.

117.Intel Corporation, http://www.intel.com.

118.Floating point performance withFlops.cprogram. http ://www.computational-battery. org/Maskinvare/Flops .html

119.x86 Overview. http://www.cs.utk.edu/~rwhalev/ATLAS/x86.html.

120.J.R. Gurd, D.F. Snelling. Manchester Data-Flow: A Progress Report // Proceedings 6th ACM International Conference on Supercomputing (ICS'92). ACM Press. 1992, P. 216-225.

121.Popadopoulos G., Culler D. Monsoon: an Explicit Token-Store Architecture // Sigarch Computer Architecture News. 1990. Vol. 18, No.2.

122.Проект OCBM. 1993.

123.V.K. Prasanna Kumar, Venkatesh Krishan, Efficient Parallel Algorithms for Image Template Matching on Hypercube SIMD Machine // IEEE Trans. РАМІ, v.l 1, no.6, June 1989. p. 665-669.

124.Синицын И.Н., Синицын В.И., Степанов A.M., Ушмаев O.C., Проблемы реализации вычислительных методов обработки и анализа сигналов на архитектурах с ассоциативной памятью // Труды Первой Всероссийской конференции «Методы и средства обработки информации», - М.: Изд-во МГУ, 2003. С. 137-141.

125.Синицын И.Н., Степанов A.M., Ушмаев О.С., Применение ассоциативной памяти для распараллеливания алгоритмов фильтрации и распознавания изображений // Сб. материалов 6-й международной конференции «Распознавание 2003», Курск, 2003. С. 23-24.

126.Синицын И.Н., Синицын В.И., Корепанов Э.Р., Белоусов В.В., Ильясов Д.Ф., Ушмаев О.С., Субоптимальные обучающиеся информационные технологии и системы // Тула, 2003.

127.Ushmaev O.S., Novikov S.O., Registration of Elastic Deformations of Fingerprint Images with Automatic Finding of Correspondences // Proc. of workshop on Multimodal User Authentication (MMUA03), Santa Barbara, С A, December 11-12,2003, P. 196-201.

128.Синицын И.Н., Степанов A.M., Ушмаев O.C., Проблемы синтеза фильтров и идентификаторов с ассоциативной памятью // Труды III международной конференции «Идентификация систем и проблемы управления» (SICPRO04). 2004. CD-ROM, С. 1896-1911.

129.О. Ushmaev and S. Novikov, Integral Criteria for Large-scale Multiple Fingerprint Solutions // SPIE Symposium on Security & Defense. Orlando, FL, USA, April 12-16, 2004.

130.S.O. Novikov, O.S. Ushmaev, // European Conference on Computer Vision (ECCV'04), Workshop on Biometric Authentication (BioAW'04), Prague, May 10-17,2004.



Приложение

1. Итеративные методы решения уравнения упругой деформации отпечатка пальца

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

ff(u) = T-2Iur + uAur

Отметим особенности матрицы А:

1)симметричность;

2)разреженность (в каждом столбце не более 18 ненулевых элемента) Если компоненты вектора смещений в узле (ij) сетки разбиения обозначить через щ, то ненулевыми являются элементы А, соответствующие следующим переменным:

№		№
1	u(i-lu-l)	10	v(i-lu-l)
2	u(i-lu)	11	v(i-ly)
3	u(i-lu'+l)	12	v(i-l;j+l)
4	u(iu'-l)	13	v(iy-l)
5	u(i;j)	14	v(i;j)
6	u(iy+l)	15	v(iu+l)
7	u(i+ly-l)	16	v(i+ly-l)
8	u(i+ly)	17	v(i+i;j)
9	u(i+l;j+l)	18	v(i+l;j+l)

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

Метод Зейделя

Функционал минимизируется из соображений равенства 0 производной Аиг-1 = 0.

Полученное уравнение решается методом Зейделя. Переменные пересчитываются следующим образом:

"v=7--fe, - І^и- - 2X,v„vJ;

Вычислительная сложность одной итерации:

64гап + 48n + 48т, где пит- число точек разбиения по осям х и у соответственно.

Градиентный метод

Точка минимума функционала ищется следующим образом: u»+i=un-yn(u")vW.

Коэффициент подбирается уп так, чтобы обеспечить максимального уменьшение функционала (П.1), т.е. значение (ия -y„VW)A(U" -y„VwJ -2l(u" -ynVWj + T должно быть минимальным. Градиент определяется следующим образом:

VW = Au"-\.

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

Уп = VWVWT(VWAVWTY. Шаги градиентного метода:

1)VW = Aun-\;

2)u"+1 =u" -VWVWT(yWAVWTYvW;

3)r(u"+1)=^(u',)-(v^Vfrr)2(v^AVI^7')"1. Вычислительная сложность одной итерации: 136nm + 98n + 98m,



2. Листинги тестовых программ

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

double MatrixMultiplicationOp(int m)

{

time__t tstart, tfinish; unsigned long timeelapsed; double tel; int i,j,q,w,e;

double r;

double a[n*n];double b[n*n]/double c[n*n];

for (q=0; q<n; q++) for (w=0; w<n; w++){ a[q*n+w]=random(); b[q*n+w]=random();}

tstart = time(NULL);

for (j=0; j<m; j++){

for (q=0; q<n; q++) for (w=0; w<n; w++){

r=0;

for (e=0; e<n; e++) r+=a[q*n+e]*b[e*n+w];

c[q*n+w]=r; } }

tfinish = time(NULL);

timeelapsed=tfinish-tstart;

flop=2*n*n*n-n*n;

tel=(timeelapsed*CPUSpeed)/flop/m*1000000000;

return tel;

double MatrixInvertionOp(int m) {

time__t tstart, tfinish; unsigned long timeelapsed; double tel; int i,j,q,w,e,flop;

double r;

double a[n*n];double b[n*n];double c[n*n];

for (q=0; q<n; q++) for (w=0; w<n; w++){ a[q*n+w]=random(); b[q*n+w]=random();}

double cii;

tstart = time(NULL);

for (j=0; j<m; j++){ for (q=0; q<n; q++){ cii=a[q*n+q];

for (w=0; w<n; w++) a[q*n+w]=a[q*n+w]/cii; for (w=0;w<q; w++){

cii=a[w*n+q];

for (e=0; e<n; e++) a[w*n+e]=a[w*n+e]-cii*a[q*n+e];

) for (w=q+l;w<n; w++){ cii=a[w*n+q]/

for (e=0; e<n; e++) a[w*n+e]=a[w*n+e]-cii*a[q*n+e]; } } }

tf inish «я time (NULL) ;

timeelapsed=tfinish-tstart; flop=2*n*n*n-n*n;

tel=(timeelapsed*CPUSpeed)/flop/m*1000000000; return tel; }

double FilterFT(int m) {

time_t tstart, tfinish;

unsigned long timeelapsed;

double tel;

int i,j,q,w,e,flop;

double rl,r2;

double mf[n*n];double mc[n*n];double ms[n*n]; double cf[n*n];double sf[n*n];double mr[n*n]; double mi[n*n];double mw[n*n];

for (q=0; q<n; q++) for (w=0; w<n; w++){ mf[q*n+w]=random(); mw[q*n+w]=random();

mc[q*n+w]=cos(2*Pi*(q-0.5*n)/n*w)/sqrt(n); ms[q*n+w]=sin(2*Pi*(q-0.5*n)/n*w)/sqrt(n); cf[q*n+w]=0;sf[q*n+w]=0;mi[q*n+w]=0; mr[q*n=w]=0; }

tstart = time(NULL);

for (i=0; i<m; i++){

for (j=0; j<n; j++) for (q=0; q<n; q++) { rl=0 ; r2=0 ; for (w=0; w<n; w++) {

rl=rl+mc[j*n+w]*mf[w*n+q];

r2=r2+ms[j *n+w]*mf[w*n+q]; }

cf[j*n+q]=rl; sf[j*n+q]=r2; }

for (j=0; j<n; j++) for (q=0; q<n; q++) { rl=0 ; r2=0 ; for (w=0; w<n; w++) {

rl=rl+cf[j*n+w]*mc[q*n+w]-sf[j*n+w]*ms[q*n+w];

r2=r2-cf[j*n+w]*ms[q*n+w]-sf[j*n+w]*mc[q*n+w];

}

mr[j*n+q]=rl*mw[j*n+q]; mi[j *n+q]=r2 *mw[j *n+q]; }

for (j=0; j<n; j++) for (q=0; q<n; q++) { rl=0; r2=0; for (w=0; w<n; w++) {

rl=rl+mc[j*n+w]*mr[w*n+q]-ms[j*n+w]*mi[w*n+q]; r2=r2-mc[j*n+w]*mi[w*n+q]-ms[j*n+w]*mr[w*n+q] ; }

cf[j*n+q]=rl; sf[j*n+q]=r2; }

for (j=0; j<n; j++) for (q=0; q<n; q++) {

rl=0;

for (w=0; w<n; w++)

rl=rl+cf[j*n+w]*mc[q*n+w]+sf[j*n+w]*ms[q*n+w];

mf[j *n+q]=rl; )

} tfinish = time(NULL);

timeelapsed=tfinish-tstart;

flop=24*n*n*n-7*n*n;

tel=(timeelapsed*CPUSpeed)/flop/m*1000000000;

return tel;

Размещено на Allbest.ru