автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.12, диссертация на тему:Разработка математического, алгоритмического и программного обеспечения подсистемы САПР СБИС для биометрической идентификации пользователей

На правах рукописи^

ФАРТУКОВ АЛЕКСЕЙ МИХАЙЛОВИЧ

РАЗРАБОТКА МАТЕМАТИЧЕСКОГО, АЛГОРИТМИЧЕСКОГО И ПРОГРАММНОГО ОБЕСПЕЧЕНИЯ ПОДСИСТЕМЫ САПР СБИС ДЛЯ БИОМЕТРИЧЕСКОЙ ИДЕНТИФИКАЦИИ ПОЛЬЗОВАТЕЛЕЙ

Специальность: 05.13.12. - системы автоматизации проектирования

АВТОРЕФЕРАТ Диссертации на соискание ученой степени кандидата технических наук

Москва-2005г.

Работа выполнена на кафедре «ПКИМС» Московского государственного института электронной техники (технического университета)

Научный руководитель: Д.т.н., профессор,

Казенное Г.Г.

Официальные оппоненты: Д.т.н., профессор,

Лисов О.И.

к.т.н., старший научный сотрудник, Архипкин В.Я.

Ведущая организация: Гос. НИИ ФП им. Ф.В. Лукина

Защита диссертации состоится «Лт%> _2005 г.

на заседании диссертационного совета Д 212.134.01 при Московском государственном институте электронной техники 124498 Москва, Зеленоград МИЭТ.

С диссертацией можно ознакомиться в библиотеке Московского государственного института электронной техники.

Автореферат разослан « у> л_ 2005 года.

Ученый секретарь д.т.н., профессор,

(9 h г

Общая характеристика работы

Актуальность темы

Последнее десятшхетие характеризуется существенным прогрессом в области технологии производства интегральных схем. Это привело к появлению принципиально нового класса СБИС - «систем на к-ристалле» (СНК), степень интеграции которых составляет не менее 1 млн. вентилей на кристалл. Одной из основных особенностей при проектировании СНК является повторное использование сложных функциональных (СФ, IP - Intellectual Property) блоков. СФ-блоки, как правило, предназначены для решения таких общих задач, как организация MPEG2 кодирования/декодирования, цифровой обработки сигналов, различных интерфейсов (USB, PCI) и т.п. При этом СФ-блок должен быть спроектирован таким образом, чтобы его можно было легко включить в состав той или иной СНК. Поэтому стоимость СФ-блока в среднем в 10 раз превышает стоимость аналогичного однократно используемого блока. Использование специализированных библиотек СФ-блоков позволяет значительно сократить время проектирования, которое напрямую влияет на получаемую прибыль предприятий-разработчиков ИС.

Библиотеки СФ-блоков можно рассматривать как самостоятельный продукт, представляющий собой объект интеллектуальной собственности. Поэтому в последнее время актуальным становится необходимость обеспечить эффективную защиту от несанкционированного доступа к проектным данным и документации, а также их нежелательной модификации. Для решения указанных задачи в состав современных САПР СБИС включаются системы информационной безопасности (ИБ). Основными функциями систем ИБ САПР СБИС являются: аутентификация пользователей, разграничение доступа пользователей САПР СБИС к определенным ресурсам, а также обеспечение защиты на сетевом уровне рабочих станций, на которых ведется проектирование.

Традиционными способами аутентификации в системах ИБ САПР СБИС являются методы, основанные на знаниях (пароли) и/или обладании ключом (идентификационные карты и т.п.). Достоинства использования указанных средств защиты заключаются в их простоте, а также низкой стоимости интеграции в различные системы безопасности. Однако такую защиту можно легко обойти в том случае,

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

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

Обычно отпечаток получают с помощью чернильного оттиска подушечки пальца на бумаге. В настоящее время появляются компактные устройства считывания, способные получать цифровые изображения отпечатков в реальном масштабе времени. Такие устройства имеют сравнительно низкую стоимость и могут быть легко интегрированы в существующую структуру систем безопасности. Это ведет к более широкому применению полностью автоматических систем распознавания по отпечаткам пальцев во многих областях, в том числе и системах ИБ САПР СБИС.

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

Цель работы

Целью диссертационной работы является разработка математического, алгоритмического и программного обеспечения для автоматической системы дактилоскопического распознавания личности в составе системы ИБ САПР СБИС. Для достижения поставленной цели необходимо решить следующие научно-технические задачи:

1. Исследовать существующие методы аутентификации пользователей, используемые в системах ИБ САПР СБИС.

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

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

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

5. Разработать программные средства, реализующие предложенные алгоритмы автоматического сравнения дактилоскопических изображений в составе системы ИБ САПР СБИС.

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

Научная новизна

Разработано математическое и алгоритмическое обеспечение системы

ИБ САПР СБИС, включающее в себя:

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

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

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

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

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

Практическая значимость работы

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

Реализация результатов работы

На основе полученных в работе результатов на предприятии ООО «Юник Ай Сиз» разработана система обеспечения информационной безопасности САПР БИС Avocad. Разработанное алгоритмическое и программное обеспечение внедрено в учебный процесс кафедры ПКИМС.

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

Представляется к защите Математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее:

1. Методы формирования и сравнения векторов-описателей для локальных областей блочного поля направлений;

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

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

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

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

Апробация результатов работы

Результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях: V международная научно-техническая конференция «Электроника и информатика - 2005», Москва, 2005; ХЬУШ научная конференция МФТИ, Москва, 2005; 7 международная конференция «Распознавание образов и анализ изображений: новые информационные технологии», Санкт-Петербург, 2004; Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2004», Москва, 2004. Публикации

Основные результаты диссертационной работы опубликованы в 7 печатных работах.

Структура и объем диссертацию

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

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

В первой главе диссертационной работы рассмотрены назначение и структура биометрических систем аутентификации пользователей в составе систем ИБ САПР СБИС. Описаны режимы их функционирования. Рассмотрены критерии точности процедур биометрической аутентификации. Приведена классификация методов распознавания отпечатков пальцев человека. Сформулирована задача сравнения точечных образов отпечатков и дан обзор методов ее решения.

В первой главе сделаны следующие выводы: 1. Традиционные методы аутентификации пользователей в системах ИБ САПР СБИС, основанные на использовании паролей и/или идентификационных карт, не удовлетворяют все возрастающим требованиям по защите проектных данных и документации.

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

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

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

окончание ветвление

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

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

Постановка задачи:

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

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

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

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

4. Разработать программное обеспечение, реализующее предложенные методы сравнения в составе системы ИБ САПР СБИС.

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

Во второй главе сформулированы основные требования к используемым при распознавании признакам. К этим требованиям относятся:

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

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

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

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

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

AD* _ pN _ рк

ERROR ~ * ERROR гERROR '

Здесь Pehror - полная вероятность ошибки распознавания для двух классов при использовании системы N признаков, Р£моя вероятность ошибки распознавания для двух классов после исключения к -го признака из используемой системы признаков.

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

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

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

сложность указанной процедуры.

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

Указанный описатель строится для каждой минюции с параметрами {х,у,в}, для которой соответствующая ей локальная

область поля направлений полностью покрывает папиллярный рисунок отпечатка. Здесь {х, у) - координаты минюции по откошеншо к системе координат, связанной с изображением отпечатка; в е [0;2,т) -направление, которое определяется значением угла касательной к папиллярной линии в точке (:с,}') по отношению к горизонтальной оси (Рис. 2).

V

Рис. 2 Параметры мишоции: а) окончания, б) ветвления.

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

1) определить координаты (/с,/) блока, которому принадлежит минюция:

к = У ,1 = X

}V

2) для каждого из блоков В(у)е£), где О - окрестность блока (&,/), вычислить модуль разности между углом определяющим направление папиллярных линий в блоке В{г,]), и углом Ш(к,1), характеризующим блок с координатами (&,/).

^ (г; У) № I) - 1% «яи № У) - /) > §, I ^(г, у) - в противном случае;

3) упорядочить полученные значения разностей для блоков В(1,/)е£1 в соответствии с их расположением относительно направления в рассматриваемой мишоции.

Результатом работы этого метода является вектор И, элементами которого являются значения Ч'0 (/,_/). Этот вектор обладает свойством

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

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

30 31 32 '17 18

/

29 14 15 16 /1 2 19

13 3

28 12 / 4 20

11 5

27 10 9 й 7 6 21

26 25 24 23 22

Рис. 3 Конфигурация окрестности блока (порядок формирования результирующего вектора отмечен цифрами).

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

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

Пусть В(д) = (ч*®- вектор-описатель локальной области поля направлений для минюции а

В(р)=(ч/1Р,Ч'£,...,Ч'£) - вектор для минюции р е Р. Здесь Р - вектор (точечный образ) отпечатка-шаблона; <2 - вектор входного отпечатка, подвергаемого операции сравнения; Ь - размер вектора - описателя локальной области поля направлений. Тогда функция подобия векторов £>(#) и £>(р) 50Л/ЯЛГГ е [0;1] задается следующими выражениями:

угде [О, в противном случае.

ЬТ - пороговая величина, определяющая сходство элементов сравниваемых описателей локальных полей направлений.

Если для минюции область £> поля направлений покрывает папиллярный рисунок не полностью, то минюции присваивается нулевой вектор £>0, сравнение с которым всегда дает 50Д/£ЛТ = 0.

Величина ошибок распознавания при сравнении векторов-описателей минюций определяется областью перекрытия между эмпирическими функциями плотности распределения вероятностей для действительных (класс £>0) и ложных (класс £1,) пар минюций,

которые обозначим через и Д£од/£т.|й,)

соответственно. Количественной характеристикой возникающего

перекрытия функций К$0шт\О.а) и /(50Л/£ЛТ|а,) может служить

оценка разделимости классов, имеющая следующий вид: 1

С^^ошеит) = ^(^оиелт^О)-/(^оетйУг!^!)!^ • (2)

о

Одним из возможных путей увеличения значения С88(80Шт) является адаптивная нормализация получаемых коэффициентов подобия 8ошт в соответствии с выражением:

^ошш =[1+Л-ехр(-5.5ол/дуг)]-\ (3)

где

А = Д"'-1, 5 =

с

Здесь с - значение коэффициента подобия 5ошт., при котором

/(с|й0) = /(с|£2,).Постоянная А полагается равной 0,01.

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

нормализации (3) позволяет увеличить значение С58(30ттг) в 1,5 раза.

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

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

Пусть А = (а1,а2,...,ам), а, ,у°,6°), ¡ = точечный

образ отпечатка. Тогда граф локальной конфигурации Б1аг{ак е л)= (^к,Ек) определяется как:

V? = |а,:-у1(х?-хакУ -уак} <МсаЯасИи)^,

Здесь МахКасНив определяет размер окрестности, для которой строится граф локальной конфигурации (Рис. 4).

Каждая вершина а, е Ук характеризуется набором параметров

(х\у\в"), а каждое ребро е = (ак ,а,)е Ек - параметрами (ге,£с), где гс - евклидово расстояние между соответствующими вершинами, 3е е [0;2тг) - угол, который образует отрезок, соединяющий минюции ак и а., и направление 0к минюции ак, для которой построен граф 81аг(ак ).

Рис. 4 Граф локальной конфигурации: а) при МахЯа(Ииз= 50; б) при МахЖайшз=100.

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

=(8,* = (г* X«'==| -

Функция подобия для векторов

= «2106(2 И ад = (<^,..х1реР,где ¿и К -

число ребер в графах и Лаг(р) соответственно, строится

следующим образом:

(?>/>)=

если \К-1\£ЛАТкг;>те

пищ

О, в противном случае,

, , (4)

ЪеспиЗя^такой что1г,р -гЯ <ЬОТ и

Х5й(у/Р)= • -3,р\,2• яг-|<У« -

0, в противном случае.

Пороговые величины 1£>Т и ЬАТ определяют окно допуска для компенсации малых локальных деформаций и ошибок при определении параметров минюций. ВАТИг задает допустимую разность между числом ребер в сравниваемых графах локальных конфигураций.

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

разделимости классов при сравнении локальных конфигураций мишоций.

Операция упорядочивания ребер графа локальной конфигурации 5Шг(ак) в зависимости от направления центральной минюции ак на

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

Основываясь на разработанных описателях, предлагается следующая оценка коэффициента подобия РтгБтИагИу^р) для минюций #е<2 и р^Р:

0,в противном случае; (5)

где Р1>(дг,р)=а1 -30Шт(д,р)+а2

Здесь РТ - пороговая величина, определяющая сходство минюций на основе коэффициентов подобия векторов-описателей, связанных с минюциями р&Р и qeQ, ах и аг - коэффициенты, определяющие вклад каждого из векторов-описателей в формируемый коэффициент сходства и удовлетворяющие условию: а1>0,а2>0,а1+а2=1. Указанные коэффициенты а, и аг определяются на основе обучающей выборки.

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

1) поиск и назначение пар минюций в соответствии с оценкой (5);

2) проверка состоятельности проведенного назначения пар;

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

Рассмотрим каждый из указанных этапов более подробно. На первом этапе строится матрица 8М размером |Р| х|£7| > каждый

элемент которой 5!М,, представляет собой коэффициент подобия (5),

вычисленный для /-ой минюции шаблона Р и j-ой минюции входного отпечатка Q .

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

R(SM)= £SM<J

(l.J^CPS

достигает своего максимума при условии, что i -ая минюция шаблона Р образует единственную пару с j -ой минюцией входного отпечатка.

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

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

В представленном методе указанная проверка выполняется путем сравнения взаимных расстояний между соответствующими точками, которые образуют пары. Пара минюций {q,,p,)е CPS, р,еР, q, е @, i = \,...,L является состоятельной, если выполняется следующее условие:

^CONSISTENCY [(#/) pi)] ^ »

1 1

где FcomisTENcr\knP,)\ = 7-г-

(6)

LCF[{qi,P\{qk,Pk)

[ 0, в противном случае,

DD<j>t>Pj) = pf-xPf+(yf-yPf

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

Условие (в) тлеет сизысл только в случае, есяг: число назначенных на перЕо.ч этапе пзр минющш Z >2. В врзтпвком случаз сравниваемые отпечатл: считаются нгсовпадаютцпгли (коэффициент подобия MatchingScore{F,Q) полагается равным 0).

Обозначиг.1 через CPSs множество пар глшгаций, удовлетворяющих условию (6). Как и в случае с исходным множеством CPS, на мощность множества состоятельных пар минюций CPSB накладывается дополнительное ограничение

jCPSgj > MinConsistencyPairs. Если это условие не выполняется,

сравниваемые отпечатки признаются несовпадающими и процесс сравнения прекращается.

Этап расширения множества состоятельных пар минюций можно представить как процесс формирования множества пар CPSE. Каждая пара (tj,p)e CPSЕ должна удовлетворять определенным ограничениям, накладываемым на нее со стороны назначенных пар минюций из множества CPSB. В разработанном методе предлагается следующая процедура формирования множества CPSE:

1) совместить точечный образ входного отпечатка Q с точечным образом шаблона Р:

vn (cos в -sin ¿Л (хчЛ (Ах (sin6» cos<9 Ду» J+^Ay

J i?

V"

, У i

и

где (Дх, Ay, в} - значения параметров совмещения, полученных на основании пар минюций из множества CPSB;

2) определить область взаимного перекрытия common Я™

сравниваемых точечных образов Р и Q';

3) сформировать множества минюций:

ре ={pi pi е ^common е q : CP-SJ,! = 1,...,М},

Qe = {q) :q'e QcomoN лфреР:fe,,p)e CPSB], j = 1,...,tf };

MatchingSor<{p,Q)=•

4) для каждой минюции рЕ &РЕ провести поиск минюции qEeQE, для которой выполняются условия:

^.-хгу+Щ-угу <ВТ,

minjfl/-9f\l-K-\e]-0f\)< at.

Пороговые величины DT и AT определяют размеры окна допуска, которое служит для компенсации малых локальных деформаций, присутствующих на отпечатках, а также позволяет до некоторой степени устранить ошибки при извлечении минюций. Если такая мишоция найдена, то (qE,pE) становится элементом CPSЕ, а рЕ и qE исключаются из дальнейшего рассмотрения. Результат сравнения точечных образов Р и @ выражается коэффициентом подобия, который имеет следующий вид:

мcommon' n common (7)

еслиМсотоы> MThru Ncommon> MThr, О, в противнолслучае

Здесь Д и Д - коэффициенты, характеризующие вклад числа

найденных пар, принадлежащих множествам CPSB и CPSE при

определении коэффициента подобия. В настоящей работе Д = /?2 = 1.

мcommon и ncommon " числ0 минюций, находящихся внутри области

перекрытия QC0MftW и принадлежащих сравниваемым точечным

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

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

1) для каждой минюции реР и деО определяются параметры совмещения {Дг-,Д>',0} точечных образов Р и О . Эта параметры выбираются так, чтобы выполнялись условия:

4 = V 4 = >'/" -в[\,2^-\в]-фАТ, где Р = (хр,ур,вр),

Я'= (*', > Л , в'ч )> таР^у,в (Ф = Я' ■

Затем найденные значения {Лх, Ду, в] подвергаются квантованию.

Квантованные величины {Дхй1ШГ, Аувшт., вдшт} задают

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

2) среди полученных показателей достоверности производится поиск максимального по величине показателя, который определяет значения параметров совмещения {дхЛШГ, Дуьш, вмлх }. Указанный метод предполагает, что каждая минюция реР может

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

В настоящей работе для уменьшения влияния ложных или отсутствующих минюций на процесс определения параметров совмещения {Дх, Ду, в\ предлагается использовать условие образования пар минюций (5), основанного на сравнении разработанных векторов-описателей. С этой целью формирование показателей достоверности должно проводиться только для тех пар минюций (р,д), для которых величина РтгБтИа гИу{д, р) не равна 0.

Таким образом, во второй главе разработано математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее: 1. Методы формирования и сравнения векторов-описателей для локальных областей поля направлений, где с целью снижения вычислительных затрат на этапе построения вектора-описателя

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

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

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

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

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

Третья глава посвящена разработке программного обеспечения, реализующего предложенные методы обработки и анализа цифровых изображений отпечатков. Разработанное программное обеспечение представляет собой библиотеку подпрограмм, которая является составной частью ПО ИБ САПР СБИС. Сформулированы основные требования, предъявляемые к разрабатываемой библиотеке. Подробно описаны ее основные модули и их функции. Приведен пример использования разработанной библиотеки в составе ПО для аутентификации пользователей САПР СБИС Avocad.

Основные выводы третьей главы заключаются в следующем:

1. Разработана структура библиотеки подпрограмм для системы ИБ САПР СБИС, которая отвечает требованиям модульности, расширяемости и гибкости при ее использовании;

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

кйучнс-псслгзоЕзтелъекнг: работ, так и при полрсзнпи прикладных программных комплексов аутентпфшпдцш; 3. На основе разработанной библиотеки подпрограмм создана подсистема аутентификации пользователей в составе системы ИБ САПР СБИС Ai'ocad, элементом которой является система контроля локального доступа к ПЭВМ, функционирующей под управлением ОС Microsoft Windows 2000/ХР Professional.

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

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

На рис. 5 показаны графики зависимости вероятности ложного несовпадения FNMR от вероятности ложного совпадения FMR при значениях коэффициента подобия t е [ОД], взятых с шагом 0,01. Здесь через L1 обозначена модификация разработанного алгоритма сравнения, для которого SMqp = S^ENT(g,p). Алгоритм L2

представляет собой модификацию исходного алгоритма сравнения, для которого SMgp=SLS(q,p). Исходный алгоритм, в котором

SMq p = PairSimilarity(q,p) обозначен через L3. Известный алгоритм

сравнения точечных образов, основанный на использовании преобразования Хока, обозначен как G1.

а)

..............&....................[.......!....!.. ; ;

[ - [I ; г, 5 • • ; • • | { -"-Алгоритм 1.1 —Ь Алгоритм 12 -в- Алгоритм 13 Алгоритме!

*. ; • ; я! ; ; ; ; 1

| I I ПшГмГ 1 1

гж 1 !

: !!!!!::« : ! ;

Й ' £ * 5 * * 5 5 5 5

: • '^ЦТл : : \ : : :

•

1 1. Л 1.: 1 .. (р

1 1 1 ( 1 1 { 1 1 1 1 11 (

б)

Рис. 5 Графики зависимости ЕЫМЯ от РМЯ для различных алгоритмов сравнения: а) для базы БВ1; б) для базы БВ2.

На основании проведенных в четвертой главе исследований сделаны следующие выводы:

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

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

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

Заключение.

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

В заключении выделим основные результаты данной работы:

1. Проведено исследование существующих методов аутентификации пользователей, используемые в системах ИБ САПР СБИС. Выявлены их достоинства и недостатки;

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

методы их формирования и сравнения, которые могут использоваться при проведении аутентификации пользователей САПР СБИС.

3. Разработано математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее:

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

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

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

4. Разработано программное обеспечение, реализующее предложенные алгоритмы автоматического сравнения дактилоскопических изображений. Указанное программное обеспечение представляет собой библиотеку подпрограмм, которая является составной частью ПО ИБ САПР СБИС.

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

пользователей САПР СБИС. Представленные в диссертационной работе алгоритмы сравнения отпечатков, использующсе предложенный коэффициент сходства минюцнй, позволяют примерно 1,5-2 раза снизить вероятность ложного отказа при значениях вероятности ложного совпадения, меньпюх 0,1%, по сравнению с известным алгоритмом, основанным на использовании преобразования Хока.

6. Разработанная подсистема ИБ САПР СБИС позволила повысить надежность автоматической аутентификации пользователей при организации доступа к проектным данным и документации, которые содержатся в БД САПР СБИС.

Основные результаты диссертации опубликованы в следующих работах:

1. Фартуков A.M. Формирование дополнительных признаков при сравнении точечных образов отпечатков пальцев человека// «Электроника и информатика - 2005». Международная научно-техническая конференция. Тезисы докладов, Москва: МИЭТ, 2005.

2. Фартуков A.M. Метод формирования дополнительных признаков при сравнении точечных образов отпечатков пальцев человека// «XLVIII научная конференция МФТИ». Тезисы докладов, Москва: МФТИ, 2005.

3. Fartukov А.М., Shereshevskii D.I. Alignment-Based Algorithm of Fingerprint Minutiae Matching. "Pattern Recognition and Image Analysis (MAIK «Nauka/Interperiodica»)", 2005, vol. 15, no. 2, pp. 547-549.

4. Фартуков A.M., Шерешевский Д.И. Алгоритм сравнения точечных образов отпечатков пальцев, основанный на их взаимном совмещении/Материалы 7-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии», СПб., 2004, с. 662 - 665.

5. Шерешевский Д.И., Фартуков А.М., Баринов А.Б. Система контроля доступа к ПК. Дактилоскопическая идентификация. «ЭЛЕКТРОНИКА: Наука, Технология, Бизнес», 2004, №5, с. 22.

6. Фартуков А.М. Алгоритм сравнения отпечатков пальцев, основанный на совмещении// «Микроэлектроника и информатика 2004». 11-ая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, Москва, 2004, с. 197.

Шерешевский Д.И., Мишуровский М.Н., Перминов В.Н., Фартуков А.М. Устройство для определения различия между несколькими обработанными цифровыми изображениями, полученными из исходного. Патент №223413, приоритет от 26.12.2002, зарегистрирован: 10.09.2004.

Подписано в печать

Заказ Тиражэкз. Уч.-изд. Формат 60x84 1/16.

Отпечатано в типографии МИЭТ (ТУ). 124498, Москва, МИЭТ.

РНБ Русский фонд

2007-4 9677

Введение

Глава 1. Автоматическая аутентификация личности на основе дактилоскопической информации в системах информационной безопасности САПР СБИС

1.1 Назначение и структура биометрических систем аутентификации в системах информационной безопасности САПР СБИС. Режимы их функционирования.

1.2 Критерии точности процедур биометрической аутентификации.

1. 3 Дактилоскопические системы аутентификации.

1.4 Методы распознавания отпечатков пальцев человека.

1.5 Обобщенный метод обнаружения характерных точек (минюций)

1.5.1 Улучшение качества изображения отпечатка и выделение папиллярных линий.

1.5.2 Обнаружение минюций и определение их характеристик

1.6 Задача сравнения точечных образов отпечатков и методы ее решения.

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

1.8 Выводы и постановка задачи.

Глава 2. Разработка математического и алгоритмического обеспечения для системы информационной безопасности САПР СБИС.

2.1 Формирование системы информативных признаков при распознавании.

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

2.3 Разработка методов формирования и сравнения описателей для локальных областей поля направлений.

2.4 Разработка методов формирования и сравнения описателей локальной конфигурации минюций.

2.5 Разработка метода формирования коэффициента сходства минюций при сравнении точечных образов отпечатков.

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

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

2.8 Разработка алгоритма глобального совмещения точечных образов, основанного на использовании преобразования Хока.

2.9 Выводы.

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

3.1 Формирование требований к разрабатываемой библиотеке подпрограмм.

3.2 Разработка общей структуры библиотеки подпрограмм.

3.3 Определение набора функций, предоставляемых разрабатываемой библиотекой

3.4 Пример использования разработанной библиотеки в составе системы идентификации.

3.5 Разработка подсистемы контроля локального доступа к ПЭВМ в составе системы ИВ САПР СВИС.

З.б Выводы.

Глава 4. Исследование эффективности разработанной системы признаков при сравнении точечных образов отпечатков в системах ИБ САПР СБИС.

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

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

4.3 Выводы.

Последнее десятилетие характеризуется существенным прогрессом в области технологии производства интегральных схем. Это привело к появлению принципиально нового класса СБИС «систем на кристалле» (СНК) , степень интеграции которых составляет не менее 1 млн. вентилей на кристалл. Одной из основных особенностей при проектировании СНК является повторное использование сложных функциональных (СФ, IP) блоков. СФ-блоки, как правило, предназначены для решения таких общих задач, как организация MPEG2 кодирования/декодирования, цифровой обработки сигналов, различных интерфейсов (USB, PCI) и т.п. При этом СФ-блок должен быть спроектирован таким образом, чтобы его можно было легко включить в состав той или иной СНК. Поэтому стоимость СФ-блока в среднем в 10 раз превышает стоимость аналогичного разово используемого блока. Использование специализированных библиотек СФ-блоков позволяет значительно сократить время проектирования, которое напрямую влияет на получаемую прибыль предприятий-разработчиков ИС.

Библиотеки СФ-блоков можно рассматривать как самостоятельный продукт, представляющий собой объект интеллектуальной собственности (Intellectual Property IP) . Поэтому в последнее время актуальным становится необходимость обеспечить эффективную защиту от несанкционированного доступа к проектным данным и документации, а также их нежелательной модификации. Для решения указанных задачи в состав современных САПР СБИС включаются системы информационной безопасности (ИБ). Основными функциями систем ИБ САПР СБИС являются: аутентификация пользователей, разграничение доступа пользователей САПР СБИС к определенным ресурсам, а также обеспечение защиты на сетевом уровне рабочих станций, на которых ведется проектирование.

Традиционными способами аутентификации в системах ИБ • САПР СБИС являются методы, основанные на знаниях (пароли) и/или обладании ключом (идентификационные карты и т.п.). Достоинства использования указанных средств защиты заключаются в их простоте, а также низкой стоимости интеграции в различные системы безопасности. Однако такую защиту можно легко обойти в том случае, когда пароль становится известен постороннему человеку, а идентификационная карта оказывается похищенной. Более того, простые пароли не являются криптостойкими, а использование сложных и часто меняющихся паролей оказывается затруднительным для легальных пользователей при повторных обращениях к системе. Биометрические технологии распознавания личности призваны решить указанные проблемы современных систем безопасности.

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

Обычно отпечаток получают с помощью чернильного оттиска подушечки пальца на бумаге. В настоящее время появляются компактные устройства считывания, способные получать цифровые изображения отпечатков в реальном масштабе времени. Такие устройства имеют сравнительно низкую стоимость и могут быть легко интегрированы в существующую структуру систем безопасности. Это ведет к более широкому применению полностью автоматических систем распознавания по отпечаткам пальцев во многих областях, в том числе и системах ИБ САПР СБИС.

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

Цель работы

Целью диссертационной работы является разработка математического, алгоритмического и программного обеспечения для автоматической подсистемы дактилоскопического распознавания личности в составе системы ИБ САПР СБИС. Для достижения поставленной цели необходимо решить следующие научно-технические задачи:

1. Исследовать существующие методы аутентификации пользователей, используемые в системах ИБ САПР СБИС.

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

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

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

5. Разработать программные средства, реализующие предложенные алгоритмы автоматического сравнения дактилоскопических изображений в составе системы ИБ САПР СБИС.

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

Научная новизна

Разработано математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее в себя:

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

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

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

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

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

Практическая значимость работы

Результаты работы нашли применение в составе системы информационной безопасности САПР БИС. Предложенные алгоритмы формирования системы признаков при использовании в составе подсистемы дактилоскопической аутентификации позволяют повысить точность распознавания. Реализация результатов работы

На основе полученных в работе результатов на предприятии ООО «Юник Ай Сиз» разработана система обеспечения информационной безопасности САПР БИС Avocad. Разработанное алгоритмическое и программное обеспечение внедрено в учебный процесс кафедры ПКИМС.

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

Представляется к защите

Математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее:

1. Методы формирования и сравнения векторов-описателей для локальных областей блочного поля направлений;

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

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

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

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

Апробация результатов работы

Результаты диссертационной работы докладывались и обсуждались на международных и всероссийских научно-технических конференциях: V международная научно-техническая конференция «Электроника и информатика 2005 , Москва, 2005; Х1Л/Ш научная конференция МФТИ, Москва, 2005; 7 международная конференция «Распознавание образов и анализ изображений: новые информационные технологии», Санкт-Петербург, 2004; Всероссийская межвузовская научно-техническая конференция студентов и аспирантов «Микроэлектроника и информатика-2004», Москва, 2004.

Публикации

Основные результаты диссертационной работы опубликованы в 7 печатных работах [33], [42] [47] .

Структура и объем диссертации

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

4.3 Выводы

1. Проведено исследование влияния разработанных векторов-описателей на достигаемую точность распознавания, которое выявило преимущество использования предложенного коэффициента сходства минюций Рмг5тПагИу{д,р), <7 60, реР при формировании матрицы БМ на первом шаге разработанного метода сравнения точечных образов отпечатков перед раздельным использованием векторов-описателей, характеризующих локальные области полей направлений и локальные конфигурации минюций.

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

3. Разработанные в главе 2 алгоритмы сравнения точечных образов отпечатков, использующие предложенный коэффициент сходства минюций, позволяют примерно 1,5-2 раза снизить вероятность ложного отказа при значениях вероятности ложного совпадения, меньших 0,1%, по сравнению с известным алгоритмом [16] , основанным на использовании преобразования Хока.

Заключение

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

В заключении выделим основные результаты данной работы:

1. Проведено исследование существующих методов аутентификации пользователей, используемые в системах ИБ САПР СБИС. Выявлены их достоинства и недостатки;

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

3. Разработано математическое и алгоритмическое обеспечение системы ИБ САПР СБИС, включающее:

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

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

Алгоритм глобального совмещения точечных образов, основанный на использовании преобразования Хока и предложенного коэффициента сходства минюций. Разработано программное обеспечение, реализующее предложенные алгоритмы автоматического сравнения дактилоскопических изображений. Указанное программное обеспечение представляет собой библиотеку подпрограмм, которая является составной частью ПО ИБ САПР СБИС. Проведено исследование влияния предложенных векторов-описателей на достигаемую точность распознавания в рамках разработанных алгоритмов сравнения отпечатков пальцев, предназначенных для автоматической аутентификации пользователей САПР СБИС. Представленные в диссертационной работе алгоритмы сравнения отпечатков, использующие предложенный коэффициент сходства минюций, позволяют примерно 1,5-2 раза снизить вероятность ложного отказа при значениях вероятности ложного совпадения, меньших 0,1%, по сравнению с известным алгоритмом, основанным на использовании преобразования Хока.

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

Jain A.K., Ross A., Prabhakar S. An Introduction to Biometric Recognition//IEEE Trans. on Circuits and Systems for Video Technology, 2004, vol. 14, pp.4 20. Maltoni D., Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition New York: Springer, 2003. 348 p.

International Biometric Group. Biometrics Market and Industry Report 2004-2008, http://www.biometricgroup.com Hatano T., Adachi T., Shigematsu S. et al. A Fingerprint Verification Algorithm Using the Differential Matching Rate//Proc. Int. Conf. on Pattern Recognition (16th), 2002, vol. 3, pp. 799-802.

Bazen A.M., Verwaaijen G.T.B., Gerez S.H., Veelenturf L.P.J., van der Zwaag B.J. A Correlation-Based Fingerprint Verification System//Proc. Workshop on Circuits, Systems and Signal Processing, 2000, pp. 205213.

Coetzee L., Botha E.C. Fingerprint Recognition in Low Quality Images//Pattern Recognition, 1993, vol. 26, no. 10, pp. 1441-1460.

Jain A.K., Prabhakar S., Hong L., Pankanti S. Filterbank-Based Fingerprint Matching//IEEE Trans, on Image Processing, 2000, vol. 9, pp. 846-859. Polikarpova N. On the Fractal Features in Fingerprint Analysis//Proc. Int. Conf. on Pattern Recognition (13th), 1996, vol.3, pp. 591-595.

A. Jain, R. Bolle, and S. Pankanti Biometrics: Personal Identification in Networked Society - New York: Kluwer, 1999 411 p.

10.Maio D., Maltoni D. Direct Gray-Scale Minutiae Detection in Fingerprints//IEEE Trans. On Pattern Analysis and Machine Intelligence, 1997, vol. 19, no. 1, pp. 27-40.

11. Ranade A., Rosenfeld A. Point Pattern Matching by Relaxation//Pattern Recognition, 1993, vol. 12, no. 2, pp. 269-275.

12. Sprinzak J., Werman M. Affine Point Matching//Pattern Recognition Letters, 1994, vol. 15, pp. 337-339.

13. Baird H. Model Based Image Matching Using Location Cambridge, MA: MIT Press, 1984. 115 p.

14. Starink J.P.P., Backer E. Finding Point Correspondence Using Simulated Annealing//Pattern Recognition, 1995, vol. 28, no. 2, pp. 231-240.

15. Jain A.K., Hong L., Bolle R. , On-line Fingerprint Verification//IEEE Trans. on Pattern Analysis and Machine Intelligence, 1997, vol. 19, no. 4, pp. 302-313.

16.Ratha N.K., Karu K. , Chen S., Jain A.K. A Real-Time Matching System for Large Fingerprint Databases//IEEE Trans, on Pattern Analysis and Machine Intelligence, 1996, vol. 18, no. 8, pp. 799-813.

17. Luo X., Tian J., Wu Y. A minutia Matching Algorithm in Fingerprint Verification//Proc. Int. Conf. on Pattern Recognition (15th), 2000, Vol. 4, pp. 833-836.

18. Jiang X., Yau W.Y. Fingerprint Minutiae Matching Based on the Local and Global Structures//Proc. Int. Conf. on Pattern Recognition (15th), 2000, vol. 2, pp. 1042-1045.

19. Ratha N.K., Pandit V.D., Bolle R.M., Vaish V. Robust Fingerprint Authentication Using Local Structural Similarity//Proc. Workshop on Applications of Computer Vision, 2000, pp. 29-34.

20. Pankanti S., Prabhakar S., Jain A.K. On the Individuality of Fingerprints//IEEE Trans, on Pattern

Analysis and Machine Intelligence, 2002, vol. 24, no. 8, pp. 1010-1025.

21.Duda R.O., Hart P.E. Pattern Classification and Scene Analysis. - Wiley-Interscience, 1973. 482 p.

22. Kullback S. Information Theory and Statistics. - Dover Publications, 1997. 416 p.

23 . Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений. Учеб. пособие для студентов вузов. М.: Высшая школа, 1983. 295 с.

24. Moenssens A. Fingerprint Techniques. London: Chilton Book Co., 1971. 321 p.

25. Методы компьютерной обработки изображений/под ред. Сойфера В.А. - М.: ФИЗМАТЛИТ, 2003. 784 с.

26. Hong L. , Wan Y. , Jain А.К. Fingerprint Image Enhancement: Algorithms and Performance Evaluation//lEEE Trans, on Pattern Analysis and Machine Intelligence, 1998, vol. 20, no. 8, pp. 777-789.

27.Tico M. , Kuosmanen P. Fingerprint Matching Using an Orientation-Based Minutia Descriptor//lEEE Trans. on Pattern Analysis and Machine Intelligence, 2003, vol. 25, no. 8, pp. 1009-1014.

28. Oh I.-S., Lee J.-S, Suen C.Y. Analysis of Class Separation and Combination of Class-Dependent Features for Handwriting Recognition//IEEE Trans. Pattern Analysis and Machine Intelligence, 1999, vol. 21, no. 10, pp. 1089-1094.

29. Indovina M., Uludag U. , Snelick R. , Mink A., Jain A.K. Multimodal Biometric Authentication Methods: A COTS Approach//Proc Workshop on Multimodal User Authentication, 2003, pp. 99-106.

30. Wang Y., Tan Т., Jain A.K. Combining Face and Iris Biometrics for Identity Verification//Proc. of 4th Int.

Conf. on Audio- and Video-Based Biometric Person Authentication (AVBPA), 2003, pp. 805-813.

31. Cormen Т.Н., Leiserson C.E., Rivest R.L. Introduction to Algorithms New York, McGraw-Hill, 1990. 768 p.

32.Казенов Г.Г., Кокин С.А., Макаров С.В., Перминов В.Н., Перминов Д. В. Система схемотехнического моделирования AV0CAD. Проектирование анолого-цифровых систем на кристалле// Электроника: Наука, Технология, Бизнес . 2004. - №5. - с.72-75.

33. Шерешевский Д.И., Фартуков A.M., Баринов А.Б. Система контроля доступа к ПК. Дактилоскопическая идентификация// Электроника: Наука, Технология, Бизнес .

2004. №6. - с. 22.

34. BioAPI Consortium. BioAPI Specification Version 1.1. The BioAPI Consortium, March 2001. http://www.bioapi.org

35. Страуструп Б. Язык программирования С++. Специальное издание./Пер. с англ. СПб.: Бином; М. : Невский диалект, 2004. 1104 с.

36. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000. Мастер-класс./Пер. с англ. СПб. : Питер; М. : Издательско-торговый дом «Русская Редакция», 2001. 752 с.

37. Microsoft Corporation. Platform SDK Documentation, Release February 2003.

38. Best Practices in Testing and Reporting Biometric Device Performance, version 2.01, tech. report, United Kingdom Biometric Working Group, 2002; http://www.npl.co.uk/scientific software/publications/bi ometrics/bestprac v2 l.pdf.

39.Maio D., Maltoni D., Cappelli R. , Wayman J.L. and Jain A.K. FVC2000: Fingerprint verification competition//lEEE Trans, on Pattern Analysis and Machine Intelligence, 2002, vol.24, no.3, pp.402-412.

40.Maio D., Maltoni D., Cappelli R. , Wayman J.L. and Jain A. K. FVC2002: second fingerprint verification competition//Proc. of Int. Conf. on Pattern Recognition (16th), 2002, vol. 3, pp.811-814.

41. Официальный сайт Национального института стандартов и технологий США: http://www.nist.gov/srd/biomet.htm

42. Фартуков A.M. Формирование дополнительных признаков при сравнении точечных образов отпечатков пальцев человека// «Электроника и информатика 2005». Международная научно-техническая конференция. Тезисы докладов, Москва: МИЭТ, 2005.

43. Фартуков A.M. Метод формирования дополнительных признаков при сравнении точечных образов отпечатков пальцев человека// «XLVIII научная конференция МФТИ». Тезисы докладов, Москва: МФТИ, 2005.

44. Fartukov A.M., Shereshevskii D.I. Alignment-Based Algorithm of Fingerprint Minutiae Matching. Pattern Recognition and Image Analysis (MAIK

Nauka/Interperiodica ) , Vol. 15, No. 2, 2005, pp. 547 549.

45. Фартуков A.M., Шерешевский Д.И. Алгоритм сравнения точечных образов отпечатков пальцев, основанный на их взаимном совмещении//Материалы 7-ой международной конференции «Распознавание образов и анализ изображений: новые информационные технологии», СПб, 2004, с. 662 -665.

46. Фартуков A.M. Алгоритм сравнения отпечатков пальцев, основанный на совмещении// «Микроэлектроника и информатика 2004». 11-ая Всероссийская межвузовская научно-техническая конференция студентов и аспирантов. Тезисы докладов, Москва, 2004.

47. «Устройство для определения различия между несколькими обработанными цифровыми изображениями, полученными из исходного», патент №223413, приоритет от 26.12.2002., зарегистрирован: 10 августа 2004г. Авт.: Шерешевский Д.И., Мишуровский М.Н., Перминов В.Н., Фартуков A.M.

1. Jain А.К., Ross А., Prabhakar S. An 1.troduction toBiometric Recognition//IEEE Trans. on Circuits andSystems for Video Technology, 2004, vol. 14, pp.4 20.

2. Maltoni D., Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition New York: Springer, 2003.348 p.

3. International Biometric Group. Biometrics Market and Industry Report 2004-2008, http;//www.biometricgroup.com

4. Hatano Т., Adachi Т., Shigematsu S. et al. A Fingerprint Verification Algorithm Using the Differential MatchingRate//Proc. Int. Conf. on Pattern Recognition (16th),2002, vol. 3, pp. 799-802.

5. Bazen A.M., Verwaaijen G.T.B., Gerez S.H., Veelenturf 1..P.J., van der Zwaag B.J. A Correlation-BasedFingerprint Verification System//Proc. Workshop onCircuits, Systems and Signal Processing, 2000, pp. 205-213.

6. Coetzee L., Botha E.C. Fingerprint Recognition in Low Quality Images//Pattern Recognition, 1993, vol. 26, no.10, pp. 1441-1460.

7. Jain A.K., Prabhakar S., Hong L., Pankanti S. Filterbank-Based Fingerprint Matching//IEEE Trans, onImage Processing, 2000, vol. 9, pp. 846-859.

8. Polikarpova N. On the Fractal Features in Fingerprint Analysis//Proc. Int. Conf. on Pattern Recognition(13th), 1996, vol.3, pp. 591-595.

9. Ranade A., Rosenfeld A. Point Pattern Matching by Relaxation//Pattern Recognition, 1993, vol. 12, no. 2,pp. 269-275.

10. Sprinzak J., Werman M. Affine Point Matching//Pattern Recognition Letters, 1994, vol. 15, pp. 337-339.

11. Baird H. Model Based Image Matching Using Location Cambridge, MA: MIT Press, 1984. 115 p.

12. Starink J.P.P., Backer E. Finding Point Correspondence Using Simulated Annealing//Pattern Recognition, 1995,vol. 28, no. 2, pp. 231-240.

13. Jain A.K., Hong L., Bolle R. , On-line Fingerprint Verification//IEEE Trans. on Pattern Analysis andMachine Intelligence, 1997, vol. 19, no. 4, pp. 302-313.

14. Ratha N.K., Karu K. , Chen S., Jain A.K. A Real-Time Matching System for Large Fingerprint Databases//IEEETrans, on Pattern Analysis and Machine Intelligence,1996, vol. 18, no. 8, pp. 799-813.

15. Luo X., Tian J. , Wu Y. A minutia Matching Algorithm in Fingerprint Verification//Proc. Int. Conf. on PatternRecognition (15th), 2000, Vol. 4, pp. 833-836.

16. Jiang X., Yau W.Y. Fingerprint Minutiae Matching Based on the Local and Global Structures//Proc. Int. Conf. onPattern Recognition (15th), 2000, vol. 2, pp. 1042-1045.

17. Ratha N.K., Pandit V.D., Bolle R.M., Vaish V. Robust Fingerprint Authentication Using Local StructuralSimilarity//Proc. Workshop on Applications of ComputerVision, 2000, pp. 29-34.

18. Pankanti S., Prabhakar S., Jain A.K. On the Individuality of Fingerprints//IEEE Trans, on Pattern113Analysis and Machine Intelligence, 2002, vol. 24, no. 8,pp. 1010-1025.

19. Duda R.O., Hart P.E. Pattern Classification and Scene Analysis. - Wiley-Interscience, 1973. 482 p.

20. Kullback S. Information Theory and Statistics. - Dover Publications, 1997. 416 p.23 . АниСИМОВ Б.В., Курганов В.Д., Злобин В.К. Распознаваниеи цифровая обработка изображений. Учеб. пособие длястудентов вузов. М.: Высшая школа, 1983. 295 с.

21. Moenssens А. Fingerprint Techniques. London: Chilton Book Co., 1971. 321 p.

22. Методы компьютерной обработки изображений/под ред. Сойфера В.А. - М.: ФИЗМАТЛИТ, 2003. 784 с.

23. Hong L., Wan Y. , Jain A.К. Fingerprint Image Enhancement: Algorithms and Performance Evaluation//IEEETrans, on Pattern Analysis and Machine Intelligence,1998, vol. 20, no. 8, pp. 777-789.

24. Tico M. , Kuosmanen P. Fingerprint Matching Using an Orientation-Based Minutia Descriptor//IEEE Trans. onPattern Analysis and Machine Intelligence, 2003, vol.25, no. 8, pp. 1009-1014.

25. Oh I.-S., Lee J.-S, Suen C.Y. Analysis of Class Separation and Combination of Class-Dependent Featuresfor Handwriting Recognition//IEEE Trans. PatternAnalysis and Machine Intelligence, 1999, vol. 21, no.10, pp. 1089-1094.

26. Indovina M., Uludag U. , Snelick R. , Mink A., Jain A.K. Multimodal Biometric Authentication Methods: A COTSApproach//Proc Workshop on Multimodal UserAuthentication, 2003, pp. 99-106.

27. Wang Y., Tan Т., Jain A.K. Combining Face and Iris Biometrics for Identity Verification//Proc. of 4th Int.114Conf. on Audio- and Video-Based Biometric PersonAuthentication (AVBPA), 2003, pp. 805-813.

28. Cormen Т.Н., Leiserson C.E., Rivest R.L. Introduction to Algorithms New York, McGraw-Hill, 1990. 768 p.

29. Казенов Г.Г., Кокин А., Макаров СВ., Перминов В.Н., Перминов Д. В. Система схемотехнического моделированияAVOCAD. Проектирование анолого-цифровых систем накристалле// Электроника: Наука, Технология, Визнес .2004. - №5. - с.72-75.

30. Шерешевский Д.И., Фартуков A.M., Варинов А.В. Система контроля доступа к ПК. Дактилоскопическаяидентификация// Электроника; Наука, Технология, Визнес .2004. №б. - с. 22.

31. BioAPI Consortium. BioAPI Specification Version 1.1. The BioAPI Consortium, March 2001. http;//www.bioapi.org

32. Страуструп В. Язык программирования C++. Специальное издание./Пер. с англ. СПб.: Вином; М. : Невскийдиалект, 2004. 1104 с.

33. Соломон Д., Руссинович М. Внутреннее устройство Microsoft Windows 2000. Мастер-класс./Пер. с англ.СПб.: Питер; М. : Издательско-торговый дом «РусскаяРедакция», 2001. 752 с.

34. Microsoft Corporation. Platform SDK Documentation, Release February 2003.

35. Best Practices in Testing and Reporting Biometric Device Performance, version 2.01, tech. report. United KingdomBiometric Working Group, 2002;http://www.npl.co.uk/scientific software/publications/biometrics/bestprac v2 l.pdf.

36. Maio D., Maltoni D., Cappelli R. , Wayman J.L. and Jain A.K. FVC2000: Fingerprint verification competition//lEEETrans, on Pattern Analysis and Machine Intelligence,2002, vol.24, no.3, pp.402-412.115

37. Maio D., Maltoni D., Cappelli R, , Wayman J.L. and Jain A.K. FVC2002: second fingerprint verificationcompetition//Proc. of Int. Conf. on Pattern Recognition(16th), 2002, vol. 3, pp.811-814.

38. Официальный сайт Национального института стандартов и технологий США: http://www.nist.gov/srd/biomet.htm

39. Фартуков A.M. Формирование дополнительных признаков при сравнении точечных образов отпечатков пальцев человека//«Электроника и информатика 2005». Международнаянаучно-техническая конференция. Тезисы докладов, Москва:МИЭТ, 2005.

40. Фартуков A.M. Метод формирования дополнительных признаков при сравнении точечных образов отпечатковпальцев человека// «XLVIII научная конференция МФТИ».Тезисы докладов, Москва: МФТИ, 2005.

41. Fartukov A.M., Shereshevskii D.I. Alignment-Based Algorithm of Fingerprint Minutiae Matching. PatternRecognition and Image Analysis (MAIKNauka/Interperiodica ) , Vol. 15, No. 2, 2005, pp. 547549.