Последнее десятилетие характеризуется существенным прогрессом в области технологии производства интегральных схем. Это привело к появлению принципиально нового класса СБИС «систем на кристалле» (СНК), степень интеграции которых составляет не менее 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. 205 213.
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 Audioand 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. «Устройство для определения различия между несколькими обработанными цифровыми изображениями, полученными из исходного», патент № 223 413, приоритет от 26.12.2002., зарегистрирован: 10 августа 2004 г. Авт.: Шерешевский Д. И., Мишуровский М. Н., Перминов В. Н., Фартуков A.M.
