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

/

( ооьи 1

ТУРКИН АНДРЕИ ВЛАДИМИРОВИЧ

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

Специальность 05.13.11 - математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

1 6 033

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-математических наук

Москва 2012 г.

005011655

Работа выполнена на кафедре «Вычислительная техника» Национального исследовательского университета «МИЭТ»

Научный руководитель:

кандидат физико-математических наук, доцент

Посыпкин Михаил Анатольевич

Официальные оппоненты:

доктор физико-математических наук, профессор

Селищев Сергей Васильевич

доктор физико-математических наук Колпаков Роман Максимович

Ведущая организация:

Учреждение российской академии наук Институт проблем управления им. В.А. Трапезникова РАН

Защита диссертации состоится « б> » 2012 г. в /т_ часов

на заседании диссертационного совета Д212.4 34.02 при Национальном исследовательском университете «МИЭТ» по адресу: ¡24498, Москва, Зеленоград, МИЭТ.

С диссертацией можно ознакомиться в библиотеке МИЭТ. Автореферат разослан « /jjcjjfyc/jj}. 2012 г.

Ученый секретарь диссертационного совета доктор технических наук, доцент A.B. Гуреев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

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

При применении традиционных методов выделения точек разветвлений и окончаний, к которым можно отнести метод утоньшения линий папиллярного узора" (МУЛ) и метод анализа

'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.

2Maltoni D„ Maio D., Jain A.K., Prabhakar S. Handbook of Fingerprint Recognition. - Springer - 2009; Lam L.. Lee S., Suen C. Y. Thinning Methodologies - A Comprehensive Survey. // IEEE Transactions on Pattern Analysis and Machine

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

Как показано в ряде работ4, применяемые на практике алгоритмы выделения областей с нарушенной гребневидной структурой, к которым можно отнести алгоритм Хонга и др.5 (АХ) и алгоритм Шена и др.6 (АШ), удовлетворительно решают поставленную задачу, хотя

Intelligence. - 1992. ~ Vol. 14. - No. 9. - P. 869-885; 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. 463-474.

3Shi Z., Govindaraju V. A chaincode based scheme for fingerprint feature extraction. // Pattern Recognition Letters. - 2006. - Vol. 27. - No. 5. - P. 462-468; 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.

"Maltoni 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. // 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. // IEEE Transactions on Pattern Analysis Machine Intelligence. - ¡998. - Vol. 20. - No. 8. -P. 777-789.

5Hong 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.

6Shen L., Kot A., Koo W. Quality Measures of Fingerprint Images. // Third international Conference on Audio- and Video-based Biometric Person Authentication. -2001. -P. 266-271.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Публикации. Материалы, отражающие основное содержание диссертационной работы, опубликованы в 4 статьях [1-4] и 4 работах в сборниках тезисов научных докладов [5-8].

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

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

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

СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

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

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

(г) (д)

Рисунок 1. Классы областей

Если рассматривать блок изображения, где присутствует гребневидная структура, гистограмма распределения вероятностей интенсивностей пикселей, построенная по этому блоку, будет выглядеть как два соединенных между собой «колокола» (Рисунок 1 (а)). Один из них соответствует области гребней, второй - области бороздок. В области, где гребневидная структура сильно нарушена или

отсутствует (область фона) гистограмма блока будет иметь уплощенный (Рисунок 1 (6)) или ярко выраженный унимодальный характер (Рисунок 1 (в)) соответственно. Также для таких областей возможно получение гистограмм блоков с двумя «колоколами», значения максимумов которых сильно отличаются друг от друга (Рисунок \(г) или Рисунок \(д)).

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

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

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

дисперсии: = (х;й,,<т), где К> 1 - натуральное число,

/ \ 1 | ц/,...ц/к - нормальные плотности: у/Лх\а,,сг) = — -ехр<~--, г.

л/2я-сг [ 2с1 \ в -вектор параметров: в - (/?, ...рк, ...ак,сг), р, + р2 +... + рк = 1, р, > 0 , сг > 0 , х,р!,й/,а ей.

Решение задачи восстановления функции плотности предусматривает решение двух задач: определения количества компонентов смеси и оценки ее параметров по реализациям случайной величины £ , представленным вектором л: = (хи...,х„).

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

правдоподобия. В рассматриваемом случае требовалось определить

процедуру, позволяющую находить максимум (по параметру в и при

фиксированном К - количестве компонентов смеси) логарифмической

функции правдоподобия, т.е. необходимо было решить

» (К, )

оптимизационную задачу вида: ^/^(д^ау.ст) -> тах . В

>=1 1/=1 ) р< • а1-а

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

{0(т)}„ы параметра в :

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

Задача оценки наименьшего количества компонентов смеси была решена путем выполнения последовательного поиска оптимального количества параметров. Для этого были рассмотрены следующие

гипотезы: первая гипотеза Н1 определяла согласие заранее найденной функции плотности с выборкой х при 2К параметрах смеси, а гипотеза Нг определяла согласие с выборкой при 2{к + \) параметрах смеси, где АГ = I,..АГтах — I, где -^тах - выбранное заранее максимально возможное количество компонентов в смеси. Для проверки этих гипотез был применен байесовский информационный критерий. В соответствии с этим критерием решение задачи об оптимальном значении числа компонент смеси имеет вид:

Ктт = агётш{- 2\оёь{х-, вк)+ {2К)\щп\ где и£ — оценка

к

максимального правдоподобия параметра 9 для некоторого значения К компонентов смеси, построенная с применением ЕМ-алгоритма по ВеКТОру = .

Приведена общая схема решения задачи восстановления функции плотности некоторого класса: вначале строится оценка параметра вк и 9К+, для последовательности фиксированных значений К = 1,..., -1. Затем, с помощью байесовского информационного критерия, эти оценки сравниваются с вынесением решения о продолжении или прекращении процесса оценивания параметров с выбором оптимального значения Копт в качестве оценки для неизвестного числа компонент смеси.

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

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

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

В' результате сравнительного анализа сделаны следующие заключения:

1. Предложенный метод более эффективно справляется с задачей классификации по сравнению с алгоритмом Хонга (средняя надежность классификации - 0.8102) и алгоритмом Шена (средняя надежность классификации -

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

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

В качестве модели для описания бинарного изображения отпечатка пальца был выбран решетчатый граф С . Множество вершин этого графа взаимно-однозначно соответствует множеству нулевых элементов матрицы В : К(О) = {(/,у): = 0,1 << М,\< ] < /V), где В

- бинарное изображение отпечатка пальца размера М на N, е {0,1}, 1 < / < М , I < у < N . Множество ребер графа С состоит из

пар вершин, находящихся на расстоянии 1 или 2 и определяется следующим соотношением:

= {{^1, }: V,, у2 е К(С), , ) = 1 или ,) = 2}.

Расстояние между вершинами V, =(/,,7,) и у2=(/2,у2)

определяется как р{у1,у2) = 0\ -'г)2 +(]\ _Л)2-

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

Начальная вершина /

І І'.'.О! І

і «іхіу'*';'"' "ліш:......а<ш пшц

Ж7ДІ йц„ , .„а<ї, ■ ■ Тбїіг'''!"! ' Вд]

«І.'.я : 125.2.» ; ' (24.2.1) : ЯШ І І'-3'" І

Рисунок 2. Разметка решетчатого графа

Формально определены понятия потока, фронта потока и времени его жизни, необходимые для построения графа событий. Пометка , приписанная вершине V графа С, является трехэлементным кортежем = , где - дискретное время,

(V) - номер потока, 93(У) - номер материнского потока (Рисунок 2).

Потоком с номером / названо множество вершин решетчатого графа, определяемое соотношением F/={veV(G):q2(v) = l}. Вводится понятие времени жизни потока с некоторым номером /, под которым понимают величину 7) = max q\(v)~ min ¡?,(v). Фронтом потока с

vel'i vef'i

номером / в момент времени / названо множество вершин решетчатого графа, определяемое соотношением

Ф/(0 = {v є V(G) :<7](v) = t,q2(v) = /}. Первым фронтом потока /•} называется фронт этого потока в момент времени min^v).

уєУ-

Последним фронтом потока /*) называется фронт этого потока в момент времени тах(7,(у). Центром фронта называется вершина

кє/'і

решетчатого графа, расположенная на минимальном расстоянии от

(и).

ТОЧКИ (1,1), где 1 =

min(;J+max(/,„)

min(j„,) + max(j„,)

при

т = м=|ф/(/)|, (/т,у'га)бФ,(/). Центр последнего фронта

некоторого потока определяет возможное местоположение точки разветвления или окончания на папиллярном узоре бинарного изображения.

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

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

некоторому отпечатков.

изображению из заранее сформированной базы

Начальная вершина'

Рисунок 3. Построение графа событий

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

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

В результате проведенного сравнительного анализа были сделаны следующие выводы:

1. Алгоритм превосходит по быстродействию методы, которые участвовали в сравнительном анализе (время работы в среднем в 1.2 раза меньше, чем время работы метода утоньшения линий папиллярного узора и в 1.4 раза меньше, чем время работы метода анализа контура), при сравнимой с ними точности нахождении точек разветвлений и окончаний.

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

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

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

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

G(x,y,<Pc,>fu) = ™V

2 2 Xfr; , Уфа

СГХ <Гу

COS^VcXpJ,

=xcos<pa+ysm<pG, у 9а =~xs'm(Pa +ycosipG, где ^-направление фильтра Габора, /¡; - частота косинусной волны функции Габора,

ау и ау - среднеквадратические отклонения функции Гаусса вдоль осей х и у соответственно.

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

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

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

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

3. Сотников A.B., Туркин A.B. Оценка качества дактилограмм в системах распознавания отпечатков пальцев. // Моделирование, алгоритмизация и программирование при проектировании информационно-управляющих систем: Сборник научных трудов. / Под ред. В.А. Бархоткина. - 2008. - С. 27-36.

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

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

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

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

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

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

Заказ № £. Тираж-/С'Оэкз. Уч.-изд.л.1,35. Формат 60x84 1/16. Отпечатано в типографии МИЭТ(ТУ). 124498, Москва, МИЭТ(ТУ).

61 12-1/537

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

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

/ ,

(

ТУРКИН АНДРЕЙ ВЛАДИМИРОВИЧ

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

ОСОБЕННОСТЕЙ

Специальность : 05.13.11 - математическое и программное обеспечение

вычислительных машин, комплексов и компьютерных сетей

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

Научный руководитель : кандидат физико-математических наук,

доцент

Посыпкин М.А.

Москва, 2011 г.

Оглавление

ВВЕДЕНИЕ.....................................................................................................................................................................4

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

1.1 Введение...........................................................................................................................................................11

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

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

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

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

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

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

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

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

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

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

2.3 этап классификации.....................................................................................................................................3 8

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

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

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

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

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

2.6 Результаты.......................................................................................................................................................50

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

3.1 Введение...........................................................................................................................................................52

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

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

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

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

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

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

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

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

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

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

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

3.4 Результаты.......................................................................................................................................................75

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

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

4.1 Введение...........................................................................................................................................................77

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

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

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

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

4.4.2 Поле частот............................................................................................................................................87

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

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

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

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

4.6.1 Введение...................................................................................................................................................99

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

4.7 Результаты.....................................................................................................................................................106

ЗАКЛЮЧЕНИЕ..........................................................................................................................................................107

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

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

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

Введение

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