Введение к работе
Актуальность работы. В последнее время широкое распространение получили человеко-машинные интерфейсы, основанные на обработке изображений. В частности, сканирование и автоматический анализ изображения отпечатка пальца нередко применяется для контроля доступа пользователей к ресурсам вычислительных машин и компьютерных сетей. Отпечатки пальцев являются известной и широко применяемой биометрической характеристикой для задач идентификации личности. За последние несколько десятилетий исследование и активное использование алгоритмов, применяемых в дактилоскопических идентификационных системах, улучшило понимание сильных и слабых сторон этого вида распознавания. Проблемами построения алгоритмов для автоматических дактилоскопических идентификационных систем (АДИС) с успехом занимались: Davide Maltoni, Dario Maio, Anil К. Jain, Salil Prabhakar, Raffaele Cappelli и другие. Проводимые ими научные исследования в этой области получили большое внимание.
Для задач идентификации большинство дактилоскопических систем используют так называемые особые точки (точки разветвлений и окончаний) изображения папиллярного узора. При таком подходе можно выделить три основных этапа работы этой системы: получение дактилограммы как изображения в градациях серого, его обработка с построением шаблона отпечатка пальца (который можно представить как список координат особых точек с их возможными атрибутами: тип точки, направление следование гребня и т.д.) и сравнение полученного шаблона с теми, которые хранятся в базе зарегистрированных в системе пользователей. Этап обработки изображения с выделением особенностей рисунка гребней и бороздок является самым важным, так как от появления ложных особенностей, а также от точности определения их местоположения зависит качество работы этапа сравнения, а также всей системы в целом. Именно поэтому к математическому и программному обеспечению, применяемому на данном этапе, предъявляются высокие требования как по сложности, так и по эффективности работы.
Актуальность работы определяется выбором в качестве объекта исследований методов и алгоритмов решения задач выделения особых точек изображения отпечатка пальца, которые эффективно используют
вычислительные ресурсы АДИС и снижают риск получения ложных особенностей в областях дактилограмм, имеющих недостаточное качество для осуществления поиска в них точек разветвлений и окончаний.
Целью диссертационной работы является разработка методов и алгоритмов выделения особых точек бинарного изображения отпечатка пальца и нахождения областей с нарушенной гребневидной структурой.
Этап обработки отпечатка пальца обычно состоит из следующей последовательности шагов: улучшения качества изображения с построением бинарного изображения отпечатка пальца и выделения на нем локальных особенностей. Бинарное изображение отпечатка пальца представляет собой булеву матрицу размера изображения, поступившего от считывающего отпечаток пальца устройства, каждый нулевой элемент которой соответствует области гребней, а каждый единичный - области бороздок изображения папиллярного узора. Для улучшения качества изображения в градациях серого и получения четкой гребневидной структуры применяются различные подходы с применением фильтров1. На практике возможно получение такого изображения, в некоторых сегментах которого нарушения гребневидной структуры носят необратимый характер, поэтому применение фильтра для него невозможно. В таких областях высок риск вьщеления ложных точек разветвлений и окончаний, поэтому до выполнения шага по улучшению качества, как правило, проводят анализ исходного изображения с выделением областей с нарушенной гребневидной структурой. Информация об этих областях далее учитывается при выделении локальных особенностей путем исключения из результирующего шаблона тех особых точек, чьи координаты лежат в областях, нарушения гребневидной структуры в которых носят необратимый характер.
При применении традиционных методов вьщеления точек разветвлений и окончаний, к которым можно отнести метод утонынения линий папиллярного узора2 (МУЛ) и метод анализа контура3 (МАК),
'Hong L., Wan Y., Jain A. Fingerprint Image Enhancement: Algorithm and Performance Evaluation. II IEEE Transactions on Pattern Analysis Machine Intelligence. - 1998. -Vol. 20. -No. 8. -P. 777-789.
2Maltoni D., Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition. - Springer - 2009; Lam L., Lee S., Suen С Y. Thinning Methodologies - A Comprehensive Survey. II IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1992. - Vol. 14. - No. 9. - P. 869-885; Arcelli C, Sanniti di Baja G. A
учитывая вышеизложенные требования, возникает необходимость проведения дополнительного анализа полученных особых точек. Несмотря на их формальную простоту и скорость работы, оказалось, что даже при проведении ряда дополнительных шагов с помощью указанных методов сложно получить действительные особые точки для тех гребней, чья граница имеет ряд неровностей. Это связано с тем, что указанные подходы не учитывают структуру всего гребня при выделении локальных особенностей. Наличие такого дефекта делает эти подходы малопригодными для точного выделения особых точек изображения отпечатка пальца, особенно для областей, где гребни имеют неидеальную форму. В связи с этим возникла проблема создания такого алгоритма выделения особых точек, который, с одной стороны обладал бы теми преимуществами, что и упомянутые выше, а, с другой стороны, результат его работы не сильно зависел от наличия дефектов структуры гребня.
Как показано в ряде работ4, применяемые на практике алгоритмы выделения областей с нарушенной гребневидной структурой, к которым можно отнести алгоритм Хонга и др.5 (АХ) и алгоритм Шена и др.6 (АШ), удовлетворительно решают поставленную задачу, хотя используют сложно вычислимые характеристики для принятия
width independent fast thinning algorithm. II IEEE Transactions on Pattern Analysis Machine Intelligence. - 1984. - Vol. 4. - No. 7. - P. 463^174.
3Shi Z., Govindaraju V. A chaincode based scheme for fingerprint feature extraction. II Pattern Recognition Letters. - 2006. - Vol. 27. - No. 5. - P. 462^168; Govindaraju V., Shi Z., Schneider J. Feature extraction using a chaincoded contour representation of fingerprint images. II International Conference on Audio and Video-Based Biometric Person Authentication. - 2003. - P. 268-275.
4Maltoni D., Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition. - Springer - 2009; Shen L., Kot A., Koo W. Quality Measures of Fingerprint Images. II Third International Conference on Audio- and Video-based Biometric Person Authentication. - 2001. - P. 266-271; Hong L., Wan Y., Jain A. Fingerprint Image Enhancement: Algorithm and Performance Evaluation. II IEEE Transactions on Pattern Analysis Machine Intelligence. - 1998. - Vol. 20. - No. 8. -P. 777-789.
5Hong L., Wan Y., Jain A. Fingerprint Image Enhancement: Algorithm and Performance Evaluation. II IEEE Transactions on Pattern Analysis Machine Intelligence. - 1998. -Vol. 20. -No. 8. -P. 777-789.
6Shen L., Kot A., Koo W. Quality Measures of Fingerprint Images. II Third International Conference on Audio- and Video-based Biometric Person Authentication. -2001. -P. 266-271.
решения. Определение такого рода областей происходит на основе классификации блоков, на которые разбито изображение отпечатка пальца, в соответствии с некоторым критерием. Проблема выбора этого критерия, а также механизма его использования, обеспечивающего приемлемое качество классификации и снижающего время работы, по сравнению с указанными выше подходами, являлась основной задачей, решаемой при построении метода.
Для достижения описанных выше целей автором поставлены и решены следующие задачи:
разработка и реализация метода выделения областей изображения отпечатка пальца с нарушенной или отсутствующей гребневидной структурой;
реализация метода повышения качества дактилограммы и приведения полученного изображения к бинарному виду;
разработка и реализация алгоритма выделения точек разветвлений и окончаний бинарного изображения папиллярного узора с формированием шаблона отпечатка пальца;
реализация алгоритма сравнения шаблона с эталонами, находящимися в базе данных зарегистрированных пользователей;
разработка программного комплекса с использованием средств среды MATLAB для проведения сравнительного анализа, включающего предлагаемые в работе методы и соответствующие им, применяемые на практике;
Используемые методы. В основе разработанного алгоритма выделения особых точек бинарного изображения отпечатка пальца лежат элементы теории графов. Метод выделения областей с нарушенной гребневидной структурой использует ЕМ-алгоритм, применяемый в математической статистике для нахождения оценок максимального правдоподобия параметров вероятностных моделей, а также фундаментальные положения теории вероятностей и математической статистики. Для теоретического обоснования предложенного подхода и практического решения поставленных задач применялся математический аппарат цифровой обработки сигналов и изображений.
Практическая ценность результатов. Предложенный в работе алгоритм выделения локальных особенностей бинарного изображения отпечатка пальца превосходит по быстродействию известные методы
(МУЛ и МАК), применяемые на практике, имея при этом сравнимую с ними точность при нахождении точек разветвлений и окончаний. Решена проблема ложного обнаружения локальных особенностей отпечатков пальцев, присущая алгоритмам, применяемым в дактилоскопии. Метод выделения областей с нарушенной гребневидной структурой превосходит по быстродействию применяемые на практике алгоритмы (АХ и АШ) более чем в два раза, имея при этом высокую надежность. Таким образом, практическая значимость проведенных исследований заключается в повышении точности и быстродействия этапа обработки исходного изображения отпечатка пальца, а, следовательно, и АДИС в целом. Разработанная автором программная реализация методов и алгоритмов работы дактилоскопической системы, может применяться для разработки и исследования дактилоскопических систем на основе локальных особенностей. Предложенные в диссертационной работе решения могут быть применены для разработки на их основе новых методов обработки изображений.
Научная новизна работы. В диссертационной работе предлагаются новый метод выделения особых точек бинарного изображения отпечатка пальца, а также алгоритм выделения областей с нарушенной гребневидной структурой на изображении отпечатка пальца в градациях серого. Их предлагается использовать в дактилоскопических системах, использующих локальные особенности отпечатка пальца. В диссертационной работе разработан программный комплекс исследования алгоритмов АДИС, включающий все основные этапы обработки изображения и этап сравнения шаблонов дактилограмм с эталонами базы данных зарегистрированных в системе пользователей. С использованием разработанного программного комплекса проведено сравнение предложенных в работе метода и алгоритма с другими известными подходами, применяемыми в обработке изображений отпечатков пальцев.
Предложенные в работе метод и алгоритм вносят вклад в развитие математической теории обработки изображений и позволяют повысить качество, а также эффективность работы дактилоскопических систем. В ходе выполнения диссертационной работы получен ряд научных результатов:
1. Разработан метод выделения в изображении отпечатка пальца областей с нарушенной гребневидной структурой на основе классификации блоков изображения.
Разработан алгоритм выделения особых точек бинарного изображения отпечатка пальца, использующий в качестве модели изображения решетчатые графы.
Рассмотренные в работе методы и алгоритмы были реализованы в среде MATLAB; разработан программный комплекс, включающий все основные шаги этапа обработки изображения отпечатка пальца и этап сравнения шаблонов дактилограмм.
Проведен сравнительный анализ с оценкой эффективности работы предложенных методов. Показано, что алгоритм выделения локальных особенностей бинарного изображения отпечатка пальца превосходит по быстродействию метод утонынения линий папиллярного узора и метод анализа контура при сравнимой с ними точности нахождении точек разветвлений и окончаний. Предложенный метод выделения областей с нарушенной гребневидной структурой более эффективно справляется с задачей классификации, чем алгоритм Хонга и алгоритм Шена, работая в среднем более чем в 2 раза быстрее.
Достоверность полученных в работе результатов обеспечена теоретическими выкладками, а также результатами экспериментальных исследований и сравнительного анализа для каждого из предложенных алгоритмов.
На защиту выносятся:
Метод выделения областей с нарушенной гребневидной структурой дактилоскопических изображений, обеспечивающий высокую надежность, значение которой в среднем составляет 0.8824, и скорость классификации. Среднее ускорение процесса классификации 2.3 и 5.96 по сравнению с алгоритмом Хонга и алгоритмом Шена соответственно.
Алгоритм выделения точек разветвлений и окончаний бинарного изображения отпечатка пальца, позволяющий устранить известные недостатки метода утонынения линий папиллярного узора и метода анализа контура по выделению локальных особенностей отпечатка пальца. Предложенный алгоритм работает в среднем в 1.2 и 1.4 раза быстрее, чем метод утонынения линий папиллярного узора и метод анализа контура соответственно.
Публикации. Материалы, отражающие основное содержание диссертационной работы, опубликованы в 4 статьях [1-4] и 4 работах в сборниках тезисов научных докладов [5-8].
Личный вклад автора. Все вынесенные на защиту результаты получены автором лично.
Апробация работы. Основные научные положения и практические результаты диссертационной работы докладывались автором и обсуждались на научно-технических конференциях «Микроэлектроника и информатика-2007» [5], «Микроэлектроника и информатика-2008» [6], «Микроэлектроника и информатика-2011» [7], «Современные информационные технологии и ИТ-образование» [8].
Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, двух приложений и списка цитируемой литературы, включающего 48 наименований. Работа содержит 130 страниц и акт о внедрении в учебный процесс.
