Методы и алгоритмы обработки изображений в дактилоскопической системе на основе локальных особенностей тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат физико-математических наук Туркин, Андрей Владимирович

• Туркин, Андрей Владимирович
• кандидат физико-математических наук
• 2011

Оглавление диссертации кандидат физико-математических наук Туркин, Андрей Владимирович

Оглавление

ВВЕДЕНИЕ

ГЛАВА 1. АВТОМАТИЧЕСКИЕ ДАКТИЛОСКОПИЧЕСКИЕ ИДЕНТИФИКАЦИОННЫЕ СИСТЕМЫ

1.1 Введение

1.2 Тенденции развития современных математических и программных средств

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

ГЛАВА 2. ВЫДЕЛЕНИЕ ОБЛАСТЕЙ С НАРУШЕННОЙ ГРЕБНЕВИДНОЙ СТРУКТУРОЙ

2.1 постановка задачи

2.2 Этап обучения

2.2.1 Восстановление функции плотности классов

2.2.2 Представление функции плотности вероятностного распределения в виде смеси нормальных

2.2.3 Оценка параметров функций плотности классов

2.2.4 ЕМ - алгоритм

2.2.5 Оценка количества параметров функции плотности

2.3 этап классификации

2.4 Оценка надежности алгоритма классификации

2.5 Сравнительный анализ

2.5.1 Оценка качества блоков изображения отпечатка пальца на основе поля направлений

2.5.2 Оценка качества блоков изображения отпечатка пальца с использованием функции Габора

2.5.3 Сравнение предложенного метода с АХ и АШ

2.6 Результаты

ГЛАВА 3. ВЫДЕЛЕНИЕ ЛОКАЛЬНЫХ ОСОБЕННОСТЕЙ ОТПЕЧАТКА ПАЛЬЦА

3.1 Введение

3.1.1 Локальные особенности отпечатка пальца

3.1.2 Бинарное изображение отпечатка пальца

3.2 Алгоритм выделения точек разветвлений и окончаний бинарного изображения отпечатка пальца

3.2.1 Предварительные замечания

3.2.2 Разметка решетчатого графа

3.2.3 Построение графа событий

3.2.4 Построение шаблона отпечатка пальца

3.3 Сравнительный анализ

3.3.1 Метод анализа контура (МАК)

3.3.2 Метод утоньшения линий папиллярного узора (МУЛ)

3.3.3 Сравнение предложенного метода с МАК и МУЛ

3.4 Результаты

ГЛАВА 4. ПРОГРАММНЫЙ КОМПЛЕКС ИССЛЕДОВАНИЯ АЛГОРИТМОВ

ДАКТИЛОСКОПИЧЕСКОЙ СИСТЕМЫ

4.1 Введение

4.2 Структура программного обеспечения дактилоскопической системы на основе локальных особенностей отпечатка пальца

4.3 выделение областей с нарушенной гребневидной структурой

4.4 Улучшение качества изображения отпечатка пальца

4.4.1 Поле направлений

4.4.2 Поле частот

4.4.3 Улучшение качества изображения с применением Фильтра Габора

4.5 Выделение локальных особенностей отпечатка пальца

4.5.1 Программная реализация алгоритма

4.6 Сравнение шаблонов дактилограмм

4.6.1 Введение

4.6.2 Алгоритм сравнения образца с эталоном

4.7 Результаты

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ 1. ТЕКСТ ПРОГРАММЫ ВЫДЕЛЕНИЯ ОБЛАСТЕЙ С НАРУШЕННОЙ ГРЕБНЕВИДНОЙ СТРУКТУРОЙ

ПРИЛОЖЕНИЕ 2 ТЕКСТ ПРОГРАММЫ ВЫДЕЛЕНИЯ ЛОКАЛЬНЫХ ОСОБЕННОСТЕЙ С ПОСТРОЕНИЕМ ШАБЛОНА ОТПЕЧАТКА ПАЛЬЦА

Введение диссертации (часть автореферата) на тему «Методы и алгоритмы обработки изображений в дактилоскопической системе на основе локальных особенностей»

Введение

В последнее время широкое распространение получили человеко-машинные интерфейсы, основанные на обработке изображений. В частности, сканирование и автоматический анализ изображения отпечатка пальца нередко применяется для контроля доступа пользователей к ресурсам вычислительных машин и компьютерных сетей. Отпечатки пальцев являются известной и широко применяемой биометрической характеристикой для задач идентификации личности. За последние несколько десятилетий исследование и активное использование алгоритмов, применяемых в дактилоскопических идентификационных системах, улучшило понимание сильных и слабых сторон этого вида распознавания. Проблемами построения алгоритмов для автоматических дактилоскопических идентификационных систем (АДИС) с успехом занимались: Davide Maltoni, Dario Maio, Anil К. Jain, Salil Prabhakar, Raffaele Cappelli и другие. Проводимые ими научные исследования в этой области получили большое внимание.

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

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

недостаточное качество для осуществления поиска в них точек разветвлений и окончаний.

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

Этап обработки отпечатка пальца обычно состоит из следующей последовательности шагов: улучшения качества изображения с построением бинарного изображения отпечатка пальца и выделения на нем локальных особенностей. Бинарное изображение отпечатка пальца представляет собой булеву матрицу размера изображения, поступившего от считывающего отпечаток пальца устройства, каждый нулевой элемент которой соответствует области гребней, а каждый единичный - области бороздок изображения папиллярного узора. Для улучшения качества изображения в градациях серого и получения четкой гребневидной структуры применяются различные подходы с применением фильтров [1]. На практике возможно получение такого изображения, в некоторых сегментах которого нарушения гребневидной структуры носят необратимый характер, поэтому применение фильтра для него невозможно. В таких областях высок риск выделения ложных точек разветвлений и окончаний, поэтому до выполнения шага по улучшению качества, как правило, проводят анализ исходного изображения с выделением областей с нарушенной гребневидной структурой. Информация об этих областях далее учитывается при выделении локальных особенностей путем исключения из результирующего шаблона тех особых точек, чьи координаты лежат в областях, нарушения гребневидной структуры в которых носят необратимый характер.

При применении традиционных методов выделения точек разветвлений и окончаний, к которым можно отнести метод утоньшения линий папиллярного узора [2, 3, 4] (МУЛ) и метод анализа контура [5, 6] (МАК), учитывая вышеизложенные требования, возникает необходимость проведения дополнительного анализа полученных особых точек. Несмотря на их формальную простоту и скорость работы, оказалось, что даже при проведении ряда дополнительных шагов с помощью указанных методов сложно получить действительные особые точки для тех гребней, чья граница имеет ряд неровностей. Это связано с тем, что указанные подходы не

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

Как показано в ряде работ [2, 7, 1], применяемые на практике алгоритмы выделения областей с нарушенной гребневидной структурой, к которым можно отнести алгоритм Хонга и др. [1] (АХ) и алгоритм Шена и др. [7] (АШ), удовлетворительно решают поставленную задачу, хотя используют сложно вычислимые характеристики для принятия решения. Определение такого рода областей происходит на основе классификации блоков, на которые разбито изображение отпечатка пальца, в соответствии с некоторым критерием. Проблема выбора этого критерия, а также механизма его использования, обеспечивающего приемлемое качество классификации и снижающего время работы, по сравнению с указанными выше подходами, являлась основной задачей, решаемой при построении метода.

Для достижения описанных выше целей автором поставлены и решены следующие задачи:

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

- реализация метода повышения качества дактилограммы и приведения полученного изображения к бинарному виду;

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

- реализация алгоритма сравнения шаблона с эталонами, находящимися в базе данных зарегистрированных пользователей;

- разработка программного комплекса с использованием средств среды МАТЬАВ для проведения сравнительного анализа, включающего

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

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

Практическая ценность результатов. Предложенный в работе алгоритм выделения локальных особенностей бинарного изображения отпечатка пальца превосходит по быстродействию известные методы (МУЛ и МАК), применяемые на практике, имея при этом сравнимую с ними точность при нахождении точек разветвлений и окончаний. Решена проблема ложного обнаружения локальных особенностей отпечатков пальцев, присущая алгоритмам, применяемым в дактилоскопии. Метод выделения областей с нарушенной гребневидной структурой превосходит по быстродействию применяемые на практике алгоритмы (АХ и АШ) более чем в два раза, имея при этом высокую надежность. Таким образом, практическая значимость проведенных исследований заключается в повышении точности и быстродействия этапа обработки исходного изображения отпечатка пальца, а, следовательно, и АДИС в целом. Разработанная автором программная реализация методов и алгоритмов работы дактилоскопической системы, может применяться для разработки и исследования дактилоскопических систем на основе локальных особенностей. Предложенные в диссертационной работе решения могут быть применены для разработки на их основе новых методов обработки изображений.

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

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

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

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

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

3. Рассмотренные в работе методы и алгоритмы были реализованы в среде МАТЬАВ; разработан программный комплекс, включающий все основные шаги этапа обработки изображения отпечатка пальца и этап сравнения шаблонов дактилограмм.

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

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

На защиту выносятся:

1. Метод выделения областей с нарушенной гребневидной структурой дактилоскопических изображений, обеспечивающий высокую надежность, значение которой в среднем составляет 0.8824, и скорость классификации. Среднее ускорение процесса классификации 2.3 и 5.96 по сравнению с алгоритмом Хонга и алгоритмом Шена соответственно.

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

Публикации. Материалы, отражающие основное содержание диссертационной работы, опубликованы в 4 статьях [8, 9, 10, 11] и 4 работах в сборниках тезисов научных докладов [12, 13, 14, 15].

Личный вклад автора. Все вынесенные на защиту результаты получены автором лично.

Апробация работы. Основные научные положения и практические результаты диссертационной работы докладывались автором и обсуждались на научно-технических конференциях «Микроэлектроника и информатика-2007» [12], «Микроэлектроника и информатика-2008» [13], «Микроэлектроника и информатика-2011» [14], «Современные информационные технологии и ИТ-образование» [15].

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

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

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

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

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

В четвертой главе описан программный комплекс для исследования алгоритмов АДИС. Являясь многокомпонентной системой, дактилоскопическая системы включает в себя ряд методов и алгоритмов, работа которых зависит от параметров, требующих оценки до момента ввода системы в эксплуатацию. В среде МАТЬАВ был разработан программный комплекс, позволяющий визуализировать процесс обработки дактилограмм и производить настройку параметров этой системы, сделав возможным полный анализ входящих в его состав алгоритмов.

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

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

и

Заключение диссертации по теме «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», Туркин, Андрей Владимирович

Заключение

При работе над диссертацией были получены следующие научные и практические результаты:

1. Разработан метод выделения областей изображения отпечатка пальца с сильно нарушенной или отсутствующей гребневидной структурой. Проведен сравнительный анализ разработанного метода с алгоритмом Хонга и алгоритмом Шена, которые применяются на практике, с оценкой ошибки классификации и времени работы. Предложенный в работе метод работает в среднем более чем в 2 раза быстрее (максимальное ускорение процесса классификации по сравнению с алгоритмом Хонга -2.31, максимальное ускорение по сравнению с алгоритмом Шена - 6.0). Предложенный метод более эффективно справляется с задачей классификации по сравнению с алгоритмом Хонга (средняя надежность классификации - 0.8102) и алгоритмом Шена (средняя надежность классификации - 0.8119), показывая надежность классификации в среднем 0.8824.

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

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

109

Список литературы диссертационного исследования кандидат физико-математических наук Туркин, Андрей Владимирович, 2011 год

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

[1] Hong L., Wan Y., Jain A. Fingerprint Image Enhancement: Algorithm and Performance Evaluation. // IEEE Transactions on Pattern Analysis Machine Intelligence. - 1998. - Vol. 20. -No. 8. - P.777-789.

[2] Maltoni D., Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition. - Springer -2009.-p.512.

[3] Lam L., Lee S., Suen C. Y. Thinning Methodologies - A Comprehensive Survey. // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1992. - Vol. 14. - No. 9. - P. 869-885.

[4] Arcelli C., Sanniti di Baja G. A width independent fast thinning algorithm. // IEEE Transactions on Pattern Analysis Machine Intelligence. - 1984. - Vol. 4. - No. 7. - P. 463474.

[5] Shi Z., Govindaraju V. A chaincode based scheme for fingerprint feature extraction. // Pattern Recognition Letters. - 2006. - Vol. 27. - No. 5. - P. 462^168.

[6] Govindaraju V., Shi Z., Schneider J. Feature extraction using a chaincoded contour representation of fingerprint images. // International Conference on Audio and Video-Based Biometric Person Authentication. - 2003. - P. 268-275.

[7] Shen L., Kot A., Koo W. Quality Measures of Fingerprint Images. // Third International Conference on Audio- and Video-based Biometric Person Authentication. - 2001. - P. 266271.

[8] Туркин A.B. Выделение локальных особенностей бинарного изображения отпечатка пальца. //Известия высших учебных заведений. Электроника. - 2012. - №1. - С.59-66.

[9] Сотников А.В., Туркин А.В. Система биометрической идентификации по локальным особенностям отпечатков пальцев. //Известия высших учебных заведений. Электроника. - 2007. - №2. - С.60-67.

[10] Сотников А.В., Туркин А.В. Оценка качества дактилограмм в системах распознавания отпечатков пальцев. // Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем. - 2008. - С. 27-36.

[11]Посыпкин М.А., Туркин А.В. Алгоритм выделения областей с нарушенной гребневидной структурой. // Информационные технологии и вычислительные системы. -2012.

[12] Сотников A.B., Туркин A.B. Оценка качества дактилограмм в автоматических дактилоскопических идентификационных системах (АДИС). // Микроэлектроника и информатика - 2007. Тезисы докладов. - М.-.МИЭТ, 2007 - 436с. - С.162.

[13] Сотников A.B., Туркин A.B. Об одном методе выделения локальных особенностей отпечатка пальца. // Микроэлектроника и информатика - 2008. Тезисы докладов. - М.: МИЭТ, 2008 - 360с. - С. 142.

[14] Туркин A.B. Алгоритм выделения особых точек бинарного изображения отпечатка пальца. // Микроэлектроника и информатика - 2011. Тезисы докладов. - М.: МИЭТ, 2011 -340с.-С. 132.

[15] Посыпкин М.А., Туркин A.B. Оценка качества дактилоскопического изображения. Современные информационные технологии и ИТ-образование. VI Международная научно-практическая конференция: Сборник трудов, 2011. - С. 731-741.

[16] Atmel FingerChip Thermal Fingerprint Sweep Sensor Hardware Based, Navigation and Click Function, SPI Interface [Электронный ресурс], 2008. - Режим доступа: http://www.atmel.com/dyn/resources/prod_documents/doc5347.pdf, свободный.

[17] Винер Н. Интеграл Фурье и некоторые его приложения. - М.: Физматгиз, 1963. - 256 с.

[18] Чистяков В.П. Курс теории вероятностей. - СПб.: Лань, 2003. - 269 с.

[19] Вентцель Е.С. Теория вероятностей. - М.: Наука. - 1969 - 576 с.

[20] Айвазян С.А., Енюков И.С., Мешалкин Л.Д. Прикладная статистика: Основы моделирования и первичная обработка данных. - М.: Финансы и статистика. - 1983. -471 с.

[21] Titterington D.M., Smith A.F.M., Makov U.E. Statistical analysis of finite mixture distributions - John Wiley & Sons Inc. - 1986. - p.254.

[22] Айвазян C.A., Бухштабер B.M., Енюков И.С. Прикладная статистика: Классификация и снижение размерности. - М.: Финансы статистика. - 1989. - 607 с.

[23] McLachlan G.J. Krishnan Т. The ЕМ Algorithm and extensions. - John Wiley & Sons Inc. -2008.-p.304.

[24] Hastie Т., Tibshirani R., Friedman J. The Elements of Statistical Learning: Data Mining, Inference and Prediction. - Springer. - 2009. - 2nd ed. - p.768.

[25] Королев В.Ю. EM-алгоритм, его модификации и их применение к задаче разделения смесей вероятностных распределений. Теоретический обзор. - М.: ИПИ РАН. - 2007. -102 с.

[26] Вентцель Е.С, Овчаров Л.А. Теория вероятностей и ее инженерные приложения. - М.:

Высшая школа. - 2000. - 480 с.

[27] McLachlan G.J. Peel D. Finite Mixture Models. - John Wiley & Sons Inc. - 2000. - p.456.

[28] Kass R.E., Raftery A.E. Bayes Factors. // Journal of the American Statistical Association. -1995. - Vol. 90. - No. 430. - P. 773-795.

[29] Schwartz G. Estimating the dimension of a model. //The Annals of Statistics. - 1978. - Vol. 6. -P. 461-464.

[30] Боровков А.А. Математическая статистика. - Новосибирск: Наука. - 1997. - 772 с.

[31] Колмогоров А.Н. Основные понятия теории вероятностей. - М.: Наука. - 1974. - 120 с.

[32] Левин Б.Р. Теоретические основы статистической радиотехники. - М.: Радио и связь. -1989.-656 с.

[33] Гуров С.И. Оценка надежности классифицирующих алгоритмов. - М.: Издательский отдел факультета Вычислительной математики и кибернетики МГУ им. М.В. Ломоносова. - 2002. - 45 с.

[34] Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир. - 1978. - 412 с.

[35] Movellan J.R. Tutorial on Gabor Filters. - 2008. - Technical report- Режим доступа: http://mplab.ucsd.edu/tutorials/gabor.pdf, свободный.

[36] Ratha N., Bolle R. Automatic fingerprint recognition systems. - Springer. - 2004. - 460 c.

[37] Trier В., Jain A. Goal-Directed Evaluation of Binarization Methods. // IEEE Transactions on Pattern Analysis and Machine Intelligence. - 1995. - Vol. 17. - No. 12. - P. 1191-1201.

[38] Niblack W. An Introduction to Digital Image Processing. - Prentice Hall. - 1986. - p.215.

[39] Lee C. Y. An Algorithm for Path Connections and Its Applications. //IRE Transactions on Electronic Computers. - 1961. - Vol. 10. - No. 2 - P. 364—365..

[40] Камерон П., Ван Линт Дж. Теория графов, теория кодирования и блок-схемы. - М.: Наука. - 1980- 144 с.

[41] Харари Ф., Палмер Э. Перечисление графов. - М.:МИР. - 1977. - 326 с.

[42] Yang J, Liu L., Jiang Т., Fan Y. A modified Gabor filter design method for fingerprint image enhancement. //PatternRecognition Letters. -2003. - Vol.24. -No.12. -P.1805-1817.

[43] Грузман И.С., Киричук B.C. и др. Цифровая обработка изображений в информационных системах. - Новосибирск: РГТУ. - 2002. - 352 с.

[44] Гонсалес Р., Вудс Р., Эддинс С. Цифровая обработка изображений в среде MATLAB. -М.: Техносфера. - 2006. - 616 с.

[45] Хуанг Т.С. Быстрые алгоритмы в цифровой обработке изображений. - М.: Радио и связь.

-1984.-224 с.

[46] Прэтт У. Цифровая обработка изображений. - М.: Мир. - 1982. - Кн.1 - 312 с.

[47] Сойфер В.А. Методы компьютерной обработки изображений. - М.:Физматлит. - 2003. -784 с.

[48] Гонсалес Р., Вудс Р. Цифровая обработка изображений. - М.:Техносфера. - 2005. - 1072 с.

Приложение 1. Текст программы выделения областей с нарушенной гребневидной

структурой

Этап обучения

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

function [Weights Mus Sigma] = GetMixtureParameters(X)

MaxK = 10; k = 1;

р = zeros(MaxK,MaxK) ; mu = zeros(MaxK,MaxK); sigma = zeros(MaxK,1); BIC = zeros(MaxK, 1);

[p(l,l:k) mu(l,l:k) sigma(1) BIC(l)] = ComputeMixtureParameters(k,X) ; for k =2:MaxK

[p(k,l:k) mu(k,l:k) sigma(k) BIC(k)] = ComputeMixtureParameters(k,X); if(BIC(k) > BlC(k-l)) k = k - 1; Weights = p(k,l:k); Mus = mu (k, 1 : k) ; Sigma = sigma(k); break;

end;

end;

lend function GetMixtureParameters

function [p mu sigma bic] = ComputeMixtureParameters(NumberOfComponents, Data) options = statset('Maxlter', 10000);

Object = gmdistribution.fit(Data, NumberOfComponents, 'Replicates', 10,1SharedCov1,true,

'Options', options);

p = Object.PComponents; mu = Object.mu; sigma = Object.Sigma; bic = Object.BIC;

%end function ComputeMixtereParameters

Этап классификации

Информация, полученная на этапе обучения, применяется для осуществления классификации блоков изображения отпечатка пальца. Глобальная переменная TrainingData, представляющая собой структуру, содержит параметры смесей. Параметрами, представленной ниже функции классификации блоков, являются изображение отпечатка пальца (image) и размер блока (N).

function QualityMask = Classification(Image, N)

QualityMask = blockproc(Intlmage,[N N],QlmageClassification);

%end function Classification

function ResultBlock = ImageClassification(block_struct) Block = block_struct.data(:); res = BlockClassification(Block); if(res ~= 1)

ResultBlock = ones(size(block_struct.data))*BlockClassification(imscale(Block));

else

ResultBlock = ones(size(block_struct.data));

end;

%end function ImageClassification

function Quality = BlockClassification(Block)

global TrainingData;

X = Block(:)* 2 5 5; W = zeros(size(TrainingData)); j = 0;

for i= 1:length(W(1,:))

if(~isempty(TrainingData(i).Parameters)) WT = 0;

for k = 1:length(TrainingData(i).Parameters.P) WT = WT +

TrainingData(i).Parameters.P(k)*

normpdf(X,TrainingData(i).Parameters.Mu(k),...

sqrt(TrainingData(i).Parameters.Sigma));

end;

W(i) = sum(log(WT)); j = j + i;

else

W(i) = -Inf;

end;

end;

if (j>l)

[M Quality] = max(W);

end;

lend function Classification

function y =

imscale(x)

mn = min(min(x)); mx = max(max(x)); у = (x-mn)/(mx-mn);

end function imscale

Приложение 2 Текст программы выделения локальных особенностей с построением

шаблона отпечатка пальца.

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

Function Minutiae = FeaturesExtraction(Image) global EndPoints global BifurcationPoints global PASS_POINT global LatticeGraph

Globallnitialization();

LatticeGraph = intl6(Image); StartPoint = struct('x',0,' y',0); nHeight = length(Image(:,1));

nWidth = length(Image(1, :));

for i = 1:nHeight

for j = 1:nWidth

if(LatticeGraph(i,j) == PASS_POINT) StartPoint.x = j; StartPoint.y = i; PropagateWave(StartPoint) ;

end;

end

end;

Minutiae = struct('EndPoints', EndPoints,...

'BifurcationPoints', BifurcationPoints);

%end function GetFeatureas

1 1U

function PropagateWave(StartPoint)

global START_POINT

global LatticeGraph

global WaveStack

global WF

global BiffurcationPointID

global EndPoints

global BifurcationPoints

FirstBifurcation = false;

LatticeGraph(StartPoint.y,StartPoint.x) = START_POINT;

OneWave = struct (' spisok1 , struct ( 1 data_x ' , StartPoint. x, ' data_y ' , StartPoint.y,

'wave_number', 0),

'nWave',3,

'BiffurcationPointID', BiffurcationPointID);

WaveStack = [];

WaveStack = [WaveStack; OneWave]; while(-isempty(WaveStack))

OneWave = WaveStack(length(WaveStack(:, 1)),:) ; WaveStack(length(WaveStack(1)),:) = [];

Output = GoPropagation(OneWave.spisok,OneWave.nWave,OneWave.BiffurcationPointID );

if(-isempty(Output))

pCP(WF.NOCP) = struct('x',0,'y',0); if( -FirstBifurcation ) if( WF.NOCP > 2 )

BifurcationPoints = [BifurcationPoints; struct('x',WF.CentralPixel.x,'y',WF.CentralPixel.y, ... 'BiffurcationPointID', BiffurcationPointID,... 'NumberOfDaughters *,WF.NOCP - 1)]; if( WF.WaveLength > 15)

EndPoints = [EndPoints; struct('xStartPoint.x,1yStartPoint.y)];

end;

else

if( WF.WaveLength > 15)

BifurcationPoints = [BifurcationPoints; struct('x',WF.CentralPixel.x,'y',WF.CentralPixel.y,... •BiffurcationPointID*, BiffurcationPointID,... 'NumberOfDaughters',WF.NOCP)]; EndPoints = [EndPoints; struct('x1,StartPoint.x,'yStartPoint.y)];

end;

end;

FirstBifurcation = true;

else

if( ~WF.Meeting )

BifurcationPoints = [BifurcationPoints;

struct('x*,WF.CentralPixel.x,'y',WF.CentralPixel.y,...

'BiffurcationPointID', BiffurcationPointID,... 1NumberOfDaughters',WF.NOCP)];

end;

end;

pCP = AddToStack(Output,pCP,BiffurcationPointID); BiffurcationPointID = BiffurcationPointID + 1;

else

if(~FirstBifurcation)

EndPoints = [EndPoints; struct('xStartPoint.x,'yStartPoint.y)];

end;

if(WF.Meeting))

if(WF.WaveLength < 2)

Index = FindBiffurcationPointWithID(WF.BiffurcationPointID); if(Index ~= -1)

if(BifurcationPoints(Index).NumberOfDaughters > 2) BifurcationPoints(Index).NumberOfDaughters = BifurcationPoints(Index).NumberOfDaughters - 1;

else

BifurcationPoints(Index) = [];

else

EndPoints = [EndPoints;

struct('x',WF.CentralPixel.x,'y',WF.CentralPixel.y)];

end;

else

EndPoints = [EndPoints;

struct('x',WF.CentralPixel.x,'y',WF.CentralPixel.y)];

end;

end;

end;

end;

%end function PropagateWave

function Globallnitialization()

global NOPASS_POINT

global PASS_POTNT

global START_POINT

global PASSED_POINT

NOPASS_POINT PASS_POINT START_POINT PASSED_POINT

global nWidth

global nHeight

global WF

global BiffurcationPointID

global nWave;

global nWavePoints;

global LatticeGraph

global Points

global WaveStack

= 0; = 1; = 2; =-1;

global EndPoints global BifurcationPoints global Image

global CentralPointsCounter global OutCentralPointsCounter

nWidth = 0; nHeight = 0;

WF = struct('WaveLength0,...

'WaveNumber1,0,... 'Division',false,... 'NOCP',0,...

'CentralPixel',struct('x',0,'y',0),... 'Meeting', false,... 'BiffurcationPointID', 0); BiffurcationPointID = 0; nWave = 0; nWavePoints = 0; LatticeGraph = 0; Points = 0; WaveStack = 0; EndPoints = []; BifurcationPoints = []; Image = [] ;

CentralPointsCounter = 0; OutCentralPointsCounter = 0; %end function Globallnitialization

function Index = FindBiffurcationPointWithID(BiffurcationPointID) global BifurcationPoints for i = 1:length(BifurcationPoints)

if(BifurcationPoints(i).BiffurcationPointID == BiffurcationPointID) Index = i; return;

end;

end;

Index = -1; %end function FindBiffurcationPointWithID

function CentralPoints = AddToStack(InputArray, CentralPoints,BiffurcationPointID) global WaveStack global WF

Count = 1;

OneWave = struct('spisok', [],...

'nWave1, 0,...

'BiffurcationPointID', 0); OneWave . nWave = WF. WaveNumber+lr-

OneWave . Bif furcationPointID = BiffurcationPointID; for i = 1:length(InputArray)

if(InputArray(i).wave_number == Count)

OneWave.spisok = [OneWave.spisok; struct('data x', InputArray(i).data_x,...

'data_y', InputArray(i).data_y,... 'wave_number', 0)];

else

WaveStack = [WaveStack; OneWave];

CentralPoints(Count).x = OneWave.spisok(intl6(length(OneWave.spisok)/2)).data_x; CentralPoints(Count).y = OneWave.spisok(intl6(length(OneWave.spisok)/2)).data_y; OneWave.spisok = [];

OneWave.spisok = [OneWave.spisok; struct('data_x', InputArray(i).data_x,...

'data y', InputArray(i).data_y,... 'wave_number', 0)];

OneWave.nWave = WF.WaveNumber+1;

OneWave.BiffurcationPointID = BiffurcationPointID; Count = Count + 1;

end

end

WaveStack = [WaveStack; OneWave];

CentralPoints(Count).x = OneWave.spisok(intl6(length(OneWave.spisok)/2)).data_x; CentralPoints(Count).y = OneWave.spisok(intl6(length(OneWave.spisok)/2)).data y;

%end function AddïoStack

function ReturnedPoints = GoPropagation(generation, Num, BiffurcationPointID)

global PASSED_POINT

global nWave

global WF

global LatticeGraph

global Points

global nWavePoints

Points = generation; nWavePoints = length(Points);

if(LatticeGraph(Points(nWavePoints).data_y, Points(nWavePoints).data_x) == PASSED_POINT) LatticeGraph = RestoreLattice(LatticeGraph,Points,Num - 1);

end;

nWave = Num;

MarkCenterPixels(Points) ;

WF.WaveLength = 0; WF.Meeting = false;

WF.BiffurcationPointID = BiffurcationPointID; while(~GenerateWave()) nWave = nWave + 1 ;

end;

ReturnedPoints = Points;

%end function WavePropagation

function LatticeGraph = RestoreLattice(LatticeGraph, InputArray, type)

for i=l: length(InputArray)

LatticeGraph(InputArray(i).data_y, InputArray(i).data_x) = type;

%end function RestoreLattice

function MarkCenterPixels(InputArray)

global WF

global Image

global CentralPointsCounter

global OutCentralPointsCounter

X = [InputArray(:).data_x]; Y = [InputArray(:).data_y];

WF.CentralPixel.x = round((min(X)+max(X))/2); WF. CentralPixel. y = round ( (min (Y) -t-max (Y) ) /2) ; CentralPointsCounter = CentralPointsCounter + 1; if Image(WF.CentralPixel.y, WF.CentralPixel.x) == 0

OutCentralPointsCounter = OutCentralPointsCounter + 1;

end;

%end function MarkCentralPixels

function Result = GenerateWave()

global WF; global nWave global Points global nWavePoints global LatticeGraph global PASSED_POINT

TempPoints = WaveTransmission(Points,nWavePoints);

if((nWavePoints == 0))

if(WF.Meeting == true)

LatticeGraph = RestoreLattice(LatticeGraph,Points,PASSED_POINT);

end;

Points = []; Result = true; return;

end

WF.WaveLength = WF.WaveLength + 1; WF.WaveNumber = nWave; WF.Division = false; WF.NOCP = 0;

TempPoints = RegulateWaveWP(TempPoints,nWavePoints); if((~WF.Division))

MarkCenterPixels(TempPoints);

LatticeGraph = RestoreLattice(LatticeGraph,TempPoints, nWave);

else

Points = TempPoints;

LatticeGraph = RestoreLattice(LatticeGraph,TempPoints,PASSED_POINT);

Result = true;

return;

end

Points = Result =

%end function

TempPoints; false;

GenerateWave

function OutputArray = RegulateWaveWP(InputArray, ArrayLength) global LatticeGraph global WF

OutputArray = [ ] ;

CurrentPixel = struct('x0y0) ; SomePixel = struct('x1,0,*y',0);

StartPosition = 1; WaveNumber = 1;

CurrentPixel.x = InputArray(Startposition).data_x; CurrentPixel.y = InputArray(Startposition).data_y;

r = ItemSearch(InputArray, CurrentPixel.x,CurrentPixel.y); InputArray(r) = [];

OutputArray = [OutputArray; struct ('data__x', CurrentPixel. x, .. .

'data_y', CurrentPixel.y,... 'wave_number', WaveNumber)]; LatticeGraph(CurrentPixel.y,CurrentPixel.x) = 0;

while(true)

[Result CurrentPixel InputArray] = NeighbourPixels(CurrentPixel,InputArray,true); if(Result == true)

OutputArray = [OutputArray;

struct('data x', CurrentPixel.x,'datay', CurrentPixel.y,... 'wave_number', WaveNumber)]; LatticeGraph(CurrentPixel.y,CurrentPixel.x) = 0;

else

if(length(OutputArray) == ArrayLength) WF.NOCP = WaveNumber; break;

else

SomePixel.x = OutputArray(Startposition).data_x; SomePixel.y = OutputArray(Startposition).data_y; CurrentPixel.x = SomePixel.x; CurrentPixel.y = SomePixel.y;

[Result SomePixel OutputArray] = NeighbourPixels(SomePixel,OutputArray,false); if(Result)

OutputArray = Turn(OutputArray,Startposition);

else

WF.Division = true;

WaveNumber = WaveNumber + 1;

StartPosition = length(OutputArray) + 1; CurrentPixel.x = InputArray(1).data_x; CurrentPixel.y = InputArray(1).data_y; OutputArray = [OutputArray;...

struct('data_x', CurrentPixel.x,'data_y',... CurrentPixel.y,'wave_number1, WaveNumber)]; InputArray(1) = [];

LatticeGraph(CurrentPixel.y,CurrentPixel.x) = 0;

end

end

end

end

%end function RegulateWave

function InputArray = Turn(InputArray, FromPosition)

pointl = struct('data x1, 0,'data y', 0,'wave number', 0) ; point2 = struct ('data__x', 0,'data__y', 0, ' wave_number 1, 0) ;

n = length(InputArray) ; if(FromPosition == 0)

for i = 0:intl6(n/2)

pointl.data_x = InputArray(n - i).data_x;

pointl.data_y = InputArray(n - i).data_y;

point1.wave_number = InputArray(n - i).wave_number;

point2.data_x = InputArray(i).data_x;

point2.data_y = InputArray(i).data_y;

point2.wave_number = InputArray(i).wave_number;

InputArray(i) = pointl; InputArray(n - i) = point2;

end;

l^O

End = intl6(ceil((n - 1 - FromPosition)/2)); k = 0;

for i = FromPosition:FromPosition + End

pointl.data_x = InputArray(n - k),data_x;

pointl.data_y = InputArray(n - k).data_y;

pointl.wave_number = InputArray(n - k).wave_number;

point2.data_x = InputArray(i).data_x;

point2.data_y = InputArray(i).data_y;

point2.wave_number = InputArray(i).wave_number;

InputArray(i) = pointl; InputArray(n - k) = point2; k = k + 1;

end

end

•lend function Turn

function Result = ItemSearch(InputArray, x, y)

for i=l:length(InputArray)

if((InputArray(i).data_x == x) && (InputArray(i).data_y == y)) Result = i; return;

end;

end;

Result = -1;

lend function ItemSearch

function [Result Pixel InputArray] = NeighbourPixels(Pixel,InputArray,del) global nWave global LatticeGraph

NULLCounter = 0;

X. s

x = Pixel.x; y = Pixel.y;

dx = [0 1 0 -1 -1 1 1 -1]; dy = [-1 0 1 0 -1 -1 1 1];

for m=l:8

x = x + dx (m) ; y = y + dy (m) ;

Element = LatticeGraph(y,x); if((Element == nWave) && (Element ~= 0)) if(del == true)

n = ItemSearch(InputArray,x,y); InputArray(n) = [];

end;

Pixel.x = x; Pixel.y = y; Result = true; return;

end;

x = x - dx (m) ; Y = Y " dy(m);

end;

Result = false; lend function NeighbourPixels

function OutputArray = WaveTransmission(InputArray, ArrayLength) global LatticeGraph; global PASS_POINT global PASSED_POINT global nWave global WF global nWavePoints

OutputArray = [];

directions =8;

dx = [010-1-111 -1];

dy = [-1 0 1 0 -1 -1 1 1];

for i = 1 :ArrayLength

temp = InputArray(i); for m = 1:directions

data_x = temp.data_x + dx (m) ; data_y = temp.data_y + dy (m) ; point = LatticeGraph(data_y,data_x); if (point == PASS_POINT)

LatticeGraph(data_y,data_x) = nWave;

OutputArray = [OutputArray; struct('data_x', data_x,'data_y', data_y,..•

'wave number', 0)];

end;

if (point == PASSED_POINT) WF.Meeting = true;

end;

end;

end;

nWavePoints = length(OutputArray);

%end function WaveTransmission

НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ «МИЭТ»

о внедрении результатов кандидатской диссертационной работы Туркина Андрея Владимировича

Мы, нижеподписавшиеся, заведующий кафедрой ВТ, д.т.н., проф., Бархоткин В.А. и профессор кафедры ВТ, к.т.н. Лупин С.А., составили настоящий акт о том, что результаты диссертационной работы Туркина A.B. на тему «Методы и алгоритмы обработки изображений в дактилоскопической системе на основе локальных особенностей» внедрены на кафедре Вычислительная техника.

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

Использование результатов диссертационной работы Туркина A.B. позволяет повысить качество подготовки студентов по направлению «Информатика и вычислительная техника».

Заведующий кафедры ВТ,

"УТВЕРЖДАЮ" одаучной работе д.т.н., профессор

С.А. Гаврилов

АКТ

д.т.н., профессор

/В.А. Бархоткин/

Профессор кафедры ВТ, к.т.н., профессор

/С.А. Лупин/