Методы и алгоритмы обработки изображений в дактилоскопической системе на основе локальных особенностей

В последнее время широкое распространение получили человеко-машинные интерфейсы, основанные на обработке изображений. В частности, сканирование и автоматический анализ изображения отпечатка пальца нередко применяется для контроля доступа пользователей к ресурсам вычислительных машин и компьютерных сетей. Отпечатки пальцев являются известной и широко применяемой биометрической характеристикой для задач идентификации личности. За последние несколько десятилетий исследование и активное использование алгоритмов, применяемых в дактилоскопических идентификационных системах, улучшило понимание сильных и слабых сторон этого вида распознавания. Проблемами построения алгоритмов для автоматических дактилоскопических идентификационных систем (АДИС) с успехом занимались: 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 страниц и акт о внедрении в учебный процесс.

Заключение

.

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

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

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

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