Содержание к диссертации
Введение
Глава 1. Структура дактилоскопических изображений и признаки сравнения 11
1.1. Крупномасштабная структура отпечатка и интегральные особенности 11
1.2. Папиллярные линии и мелкие особенности 15
1.3. Искажения 18
1.4. Избирательность и надежность поиска 19
1.5. Выводы 22
Глава 2. Обработка исходного изображения и выделение особенностей 2 4
2.1. Анализ изображения 25
2.2. Определение поля направлений 30
2.3 Фильтрация поля направлений и восстановление интегральной структуры 41
2.4. Выделение линий и мелких особенностей 4 4
Глава 3. Представление и сравнение дактилоскопических изображений 4 7
3 .1 Интегральные особенности 4 7
3.2. Представление папиллярного узора, инвариантное к геометрическим деформациям 4 9
3.3. Координатный метод сравнения 52
3.4. Топологическая характеристика особенности. 61
3.5. Сравнение с использованием топологических характеристик папиллярного узора 64
Глава 4 Реализация системы 7 0
4.1. Общие характеристики 70
4.2. Ввод дактилокарт 74
4.3. Ввод следов 75
4.4. Обработка и кодирование изображений отпечатков и следов 7 9
4.5. Редактирование интегральных особенностей 80
4.6. Поиск.' 82
4.7. База данных 85
4.8. Сервисные программы 86
Заключение 90
Литература 92
- Крупномасштабная структура отпечатка и интегральные особенности
- Анализ изображения
- Интегральные особенности
- Общие характеристики
Введение к работе
Идентификация человека по отпечаткам пальцев применяется в криминалистике уже более ста лет, но до последнего времени существовало серьёзное ограничение: отпечатки можно было использовать только для подтверждения личности. Поиск человека по оставленному отпечатку был реально невозможен. Причина этого в том, что невозможно построить достаточно подробную классификацию отпечатков, основанную на предварительно вычисляемых признаках. Поэтому поиск похожих отпечатков сводится к непосредственному сравнению изображения запросного отпечатка с каждым изображением из архива. Учитывая большие размеры дактилоскопических архивов, при ручной технологии это была практически неосуществимая задача. Вследствие этого идентификация папиллярных узоров была исторически одной из первых и исключительно важных для практики задач в области распознавания образов и обработки изображений. Новые идеи и методы традиционно апробировались на этой задаче. Длительное время это были интегральные методы сначала оптические, голографические, а затем цифровые методы фильтрации на основе преобразования Фурье. Существенный недостаток интегральных методов -низкая избирательность, делающая их непригодными для целей криминалистики. Реальный успех был достигнут только с разработкой структурных методов анализа и сравнения дактилоскопических изображений, основывающихся на деталях строения папиллярного узора
и топологических соотношениях между ними. За последние 10-15 лет появились автоматизированные дактилоскопические информационно-поисковые системы (АДИС), пригодные для практического применения.
Действительная избирательность структурных методов ограничена достоверностью обнаружения и распознавания деталей узора и определения их характеристик, а также геометрическими деформациями отпечатка. Большая часть дактилоскопических изображений, с которыми работают криминалисты, имеет низкое качество: на изображении присутствуют высокочастотный шум и крупномасштабные дефекты непропечатки, смазы, включения посторонних объектов. Геометрия изображения сильно зависит от условий получения отпечатка, вообще возможны любые непрерывные деформации. Всё это ограничивает возможности АДИС.
Для повышения эффективности автоматической идентификации требуется дальнейшее развитие методов фильтрации дактилоскопических изображений и выделения деталей узора; разработка методов сравнения, инвариантных к геометрическим искажениям изображения.
Целью диссертационной работы являлась разработка методов анализа и сравнения папиллярных узоров для использования в автоматизированной дактилоскопической информационно-поисковой системе (АДИС).
В соответствии с целью работы при проведении исследований решались следующие задачи:
-Разработка метода анализа дактилоскопических изображений, пригодного для обработки сильно зашумленных изображений;
-Исследование возможности построения метода сравнения дактилоскопических изображений, инвариантного к движениям и непрерывным деформациям изображения;
-Разработка метода сравнения отпечатков, использующего метрические и топологические характеристики деталей узора;
-Построение программной системы для анализа и сравнения дактилоскопических отпечатков;
-Экспериментальное исследование избирательности и надежности разработанных методов сравнения на больших массивах отпечатков.
Методы исследования основаны на применении спектрального анализа, структурных методов анализа изображений, теории графов, методов цифровой обработки изображений.
Научная новизна работы:
1.Предложен новый подход к построению интегральной модели изображения, основанный на реконструкции поля направлений.
2.Разработан метод определения поля направлений, в котором сегментация изображения осуществляется в спектральной плоскости.
З. Разработаны алгоритмы фильтрации и выделения деталей папиллярного узора, использующие интегральную модель изображения
4.Предложено представление папиллярного узора, инвариантное к движениям и непрерывным деформациям изображения.
5.Разработаны алгоритмы сравнения
дактилоскопических отпечатков, использующие
интегральные признаки, метрические и топологические
характеристики деталей узора.
6.Разработана дактилоскопическая информационно-поисковая система.
Практическая ценность.
Разработанные методы фильтрации и анализа изображений обеспечивают высокую достоверность распознавания деталей строения папиллярного узора на низкокачественных отпечатках. Это позволяет использовать их для обработки реальных массивов дактилоскопических изображений. Методы сравнения отпечатков по интегральным признакам и метрическим характеристикам деталей узора позволяют оптимизировать поиск аналога запросного отпечатка при работе с большими массивами отпечатков.
Реализация результатов работы. Результаты
диссертационной работы внедрены в рамках НИР, выполненной ФГУП НПП «РУБИН» по заказу департамента радиопромышленности Министерства промышленности РФ.
Диссертационные исследование выполнялись и реализовались так же в ПГУ по грантам Российского фонда фундаментальных исследований проект № 96-01-01363 «Теория признаков распознавания с позиций стохастической геометрии» и проект №00-01-00421 «Теория распознавания образов, основанная на стохастической геометрии», по гранту Министерства Образования России в области кибернетики, автоматики и ВТ «Новая теория и системы генерации признаков распознавания изображений с позиций стохастической геометрии».
Положения, выносимые на защиту:
Новый спектральный метод определения поля направлений и его программная реализация.
Новый подход к построению интегральной модели изображения и выявлению интегральных особенностей.
Алгоритм и программная реализация фильтрации и определения информативных участков изображений с опорой на интегральную модель.
Алгоритм и программная реализация сравнения дактилоскопических отпечатков по интегральным признакам, метрическим и топологическим характеристикам деталей узора.
Новая программная система для анализа и сравнения дактилоскопических отпечатков.
Апробация работы. Результаты исследований
публиковались в центральных Российских и международных журналах: «Измерительная техника»,
Российско-Американский журнал Pattern Recognition and Image Analysis (Advances in Mathematical Theory and Application); межвузовских сборниках и докладывались на международных и Всероссийских научных конференциях.
Публикации. По теме диссертации опубликовано 7 печатных работ, в том числе 4 статьи и 3 тезиса докладов.
Содержание работы.
Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы и приложения.
В первой главе проанализирована структура изображения папиллярного узора, рассмотрены возможные структурные и метрические искажения изображений, сформулированы требования к методам обработки и сравнения дактилоскопических изображений.
Во второй главе предложены методы обработки исходных дактилоскопических изображений, включающие в себя: определение крупномасштабной структуры узора, фильтрацию изображения, обнаружение интегральных особенностей, классификацию изображения, обнаружение мелких особенностей и определение соотношений между ними. Для анализа крупномасштабной структуры изображения предложено использовать метод поля направлений. Разработаны методы обнаружения интегральных особенностей и фильтрации изображения, использующие поле направлений. Исследована
эффективность различных методов определения поля направлений. Разработан спектральный метод определения поля направлений.
В третьей главе анализируются топологические характеристики деталей папиллярного узора, предложено представление папиллярного узора, инвариантное к движениям и непрерывным деформациям изображения, рассмотрены методы сравнения папиллярных узоров. Приведены результаты экспериментальных исследований разработанных методов сравнения.
В четвертой главе рассматривается устройство и программные средства Автоматизированной Дактилоскопической Информационно-поисковой системы.
В заключении сформулированы основные результаты и выводы диссертационной работы.
Крупномасштабная структура отпечатка и интегральные особенности
Расстояние между соседними линиями сравнимо с их шириной и практически неизменно для данного отпечатка. Радиус кривизны большинства линий существенно превосходит расстояние между ними, т.е. ориентация линий меняется достаточно плавно и каждому участку изображения можно сопоставить некоторое среднее направление линий. Крупномасштабная структура отпечатка (характерный размер - расстояние между линиями) полностью определяется полем направлений папиллярных линий. В папиллярном узоре обычно выделяют две части - рамку и внутренний рисунок ([56,80]). Рамка образована верхним и нижним потоками папиллярных линий, охватывающими внутренний рисунок. Поле направлений рамки непрерывно и не имеет особых точек. Линии, образующие внутренний рисунок, располагаются в виде петель, дуг и завитков. Поле направлений внутреннего рисунка может иметь несколько особых точек, в которых происходит резкое изменение среднего направления папиллярных линий. Особые точки присутствуют также на границе рамки и внутреннего рисунка (дельты). Существует три основных типа особых точек (интегральные особенности) поля направлений: простой центр (центр, или вершина, петли), вырожденный центр (центр завитка) и дельта([5б, 80, 49] ) .
На некоторой части отпечатков положение интегральных особенностей невозможно определить совершенно точно -поле направлений имеет разрыв не в точке, а на некоторой кривой. Погрешность определения координат может составлять несколько средних расстояний между линиями([11]).
Центры, простые и вырожденные, образуются одним потоком линий, имеющим, соответственно, форму петли или кольца; кривизна линий увеличивается по мере приближения к центру. Обычно центр располагается около геометрического центра отпечатка. Кроме координат, важной характеристикой простого центра является направление его осевой линии, т.е. касательной к внутренней линии петли. В действительности не существует строгой границы между простым и вырожденным центрами. Например, сильно вытянутый завиток можно рассматривать как совокупность двух петель с отдельными простыми центрами, которые сольются в один вырожденный при приближении формы завитка к круговой. Эту неоднозначность следует учитывать, особенно при обработке неполных отпечатков.
Дельта образуется тремя потоками папиллярных линий, чаще всего на границе рамки и внутреннего рисунка; кривизна линий в окрестности дельты практически постоянна. Дельты обычно располагаются в нижней части отпечатка по краям внутреннего рисунка; соответственно различают левую и правую дельты.
Более сложных конфигураций поля направлений не существует. Основываясь на картине распределения линий внутреннего рисунка, традиционно проводят классификацию отпечатков по типу узора ([11,49,56,80]). Общая структура поля направлений определяется его особыми точками, следовательно, тип узора однозначно связан с наличием и взаимным расположением интегральных особенностей. Количество рассматриваемых классов узоров зависит от учитываемых характеристик интегральных особенностей. Если учитывать положение и ориентацию интегральных особенностей, классификацию можно расширить до десятков разновидностей ([49]). Такая детальная классификация пригодна только лишь для полных отпечатков (хотя необходимо учитывать, что даже при непрерывной деформации изображения отпечаток может быть отнесен к совершенно другому классу). В действительности запросный отпечаток часто содержит только фрагмент папиллярного узора, и, в общем случае, неизвестно какой. Вследствие этого формализованное описание детальной классификации практически невозможно. Более того, на фрагментарных отпечатках во многих случаях не всегда возможно однозначное определение даже основного типа.
По всей видимости, в АДИС реально работоспособна классификация, использующая только 4 основные типа узора. Как показал наш опыт, эта классификация работает по крайней мере на 80% отпечатков.
Анализ изображения
Попытка обнаружить папиллярную линию непосредственно, независимо от окружения, на большинстве отпечатков не дает удовлетворительных результатов. В то же время, существует сильная корреляция между соседними линиями: если в некотором месте изображения имеется линия, то рядом расположены линии, имеющие близкие значения направления и кривизны; линий, направление которых существенно отличается от окружения, не существует. Общая структура отпечатка также накладывает сильные ограничения на возможные параметры линии для каждого участка изображения. Например, в верхней и нижней частях отпечатка линии имеют преимущественно горизонтальное направление; отрезок, соединяющий центр и дельту, пересекает папиллярные линии под углом, близким к прямому и т.д.
Следовательно, имеет смысл сначала сегментировать изображение на участки с различными направлениями папиллярных линий, а выделение каждой отдельной линии производить с учетом среднего направления соответствующего участка изображения.
Для анализа дактилоскопических изображений была разработана следующая последовательность операций (на рис 2.1 - 2.8 представлены результаты, получаемые на соответствующих стадиях обработки изображения):
1. Для каждого участка изображения определяется наиболее вероятное среднее направление линий и оценивается достоверность полученного направления, т.е. информативность участка (рис 2.1 - исходное полутоновое изображение, 256 уровней серого, разрешение 300 dpi; рис 2.2 - начальная оценка поля направлений и информативности, использован спектральный метод, цветом выделены различные направления, серый цвет - участки с низкой оценкой информативности).
2. Восстанавливается интегральная структура отпечатка, определяется наличие и расположение интегральных особенностей (рис 2.3 - поле направлений отфильтровано, проведен анализ его связности; рис 2.4 общая структура отпечатка, обнаружены и удалены посторонние объекты, обнаружены интегральные особенности).
3. Участки, получившие низкую оценку информативности или имеющие «неправильное» направление, обрабатываются повторно с учетом ограничений, накладываемых интегральной структурой.
4 . Изображение окончательно сегментируется на участки с различным направлением и неинформативные участки, имеющие значительную протяженность (рис 2.5 окончательная оценка поля направлении, информативные участки изображения).
Описанный алгоритм позволяет достоверно обнаруживать крупномасштабные и мелкомасштабные дефекты изображения и обрабатывать сильно зашумленные участки изображения. В некоторых случаях удается даже разделить частично перекрывающиеся отпечатки 2.2. Определение поля направлений.
Изображение дактилоскопического отпечатка представляет собой квазипериодическую структуру, те в каждой малой области изображения функция яркости является приближенно периодической вдоль определенного направления и постоянной - вдоль перпендикулярного направления. Основные параметры области изображения -направление линий и среднее расстояние между ними. Существенной является также величина достоверности оценки поля направлений в данной области, характеризующая информативность изображения.
Характерный размер, на котором существенно изменяются параметры папиллярной линии - кривизна и направление - равен расстоянию между линиями; в поперечном направлении яркость изображения существенно меняется на расстоянии порядка 1/4 расстояния между линиями; таким образом, для достоверной передачи общей структуры папиллярного узора поле направлений достаточно определять с точностью порядка arctg(l/ 4) « 15 .
Интегральные особенности
Для отпечатков с дактилокарт определение типа узора обычно не вызывает затруднений. Если не сделано грубых ошибок при получении отпечатка, на изображении присутствуют и достоверно обнаруживаются интегральные особенности, однозначно определяющие тип узора ([11,49,56,80] ) .
Сложнее обстоит дело со следами, на которых часто представлена только часть папиллярного узора. В зависимости от вида фрагмента, наличие и положение некоторых (или всех) интегральных особенностей можно лишь оценить с некоторой степенью достоверности. При обработке изображений для фрагментарных отпечатков определяются все вероятные типы узора, отбор отпечатков для сравнения производится с учетом этой неоднозначности([49]).
По экспериментальным данным на стандартной выборке следов, использование типа узора позволяет сократить объем последующих сравнений в среднем в 2 раза.
Положение и ориентация интегральных особенностей также могут быть использованы для предварительного сравнения. В среднем, реальная избирательность такого сравнения невелика, так как эти характеристики всегда определяются с некоторой ошибкой даже на полных отпечатках.
С большей эффективностью характеристики интегральных особенностей используются для оценки положения изображений и их масштаба. Наибольшее значение имеет положение центра, его ориентация и ориентация флексорной складки. Например, если у сравниваемых отпечатков известно положение центров, можно оценить взаимный сдвиг изображений; по угловым характеристикам можно оценить взаимный разворот. Достоверность такой оценки определяется точностью измерения метрических характеристик интегральных особенностей. В наиболее благоприятных случаях точность определения положения составляет около двух линий, ориентации - порядка 25.
Предварительная привязка изображений позволяет существенно сократить объем вычислений при сравнении отпечатков (по нашим данным, в некоторых случаях более чем 50 раз).
Для особенности можно определить локальную систему координат, ориентация которой задаётся направлением папиллярных линий. Положение другой особенности в этой системе координат характеризуется полярным углом и расстоянием, выраженным в линиях (рис 3.1) ([1,7])
Матрица Gy инвариантна относительно сдвигов, поворотов и масштабирования изображения и содержит наиболее существенную информацию об отпечатке; например, по ней можно достаточно точно восстановить скелетное изображение отпечатка.
При сравнении изображений необходимо учитывать, что деформации изображения могут заметно менять угол fi(i,j), вследствие чего уникальность, и следовательно значимость для сравнения пары удаленных особенностей незначительна. Кроме того, для удаленных особенностей величина r(i,j) может не оставаться постоянной при деформациях изображения, особенно если соединяющий их отрезок направлен вдоль линий. Наиболее существенными являются связи между близко расположенными особенностями. В разработанном алгоритме сравнения для каждой особенности учитывается не более 8 ближайших соседей; отбор производится по величине r(i,j) (не более 10) и по метрическому расстоянию (не более 10 средних расстояний между линиями).
Сравнение двух отпечатков состоит в установлении взаимно-однозначного соответствия между их особенностями [1-7, 56, 65, 80]. При выборе пар похожих особенностей учитываются локальные характеристики и связи между особенностями. Количество сопоставленных особенностей служит оценкой сходства отпечатков.
Для сравнения отпечатков необходимо найти функцию соответствия С, при которой величина Н максимальна. Точное решение требует перебора всех возможных перестановок и требует больших вычислительных затрат.
Общие характеристики
На основе анализа задач, решаемых криминалистами, можно сформулировать основные требования к АДИС: АДИС должна поддерживать базу данных дактилокарт (10-пальцевые отпечатки, снимаемые в экспертно-криминалистических подразделениях с необходимой сопроводительной текстовой информацией) и следов (как правило, одиночные отпечатки с мест преступления, требующие идентификации). Использование АДИС становится оправданным при базе данных 5000-10000 дактилокарт для уровня района или города. При меньших объемах мала вероятность того, что аналог запросного отпечатка введен в систему. Количество хранимых следов зависит от режима работы системы. Для районного (городского) уровня объем БД дактилокарт должен быть 10000-50000 дактилокарт (100000-500000 отпечатков), объем БД следов - до 10000. АДИС должна обрабатывать запросы на идентификацию дактилокарт - поиск «дактилокарта - след», «дактилокарта - дактилокарта», и следов -поиск «след - дактилокарта» и «след-след». По результатам поиска формируется рекомендательный список наиболее «похожих» отпечатков (дактилокарт), предъявляемый эксперту. Наиболее важные пользовательские характеристики АДИС - надежность и избирательность поиска. АДИС должна обеспечивать надежность поиска, т.е. вероятность включения "своего" отпечатка в рекомендательный список, на уровне 80-90%. Более высокая надежность реально недостижима по организационным причинам, вне зависимости от качества алгоритмов анализа и сравнения отпечатков. 4. Наиболее важным и обычно требующим наибольшего времени является поиск "след - дактилокарта". Время поиска складывается собственно из поиска аналога следа в БД и последующей работы оператора с рекомендательным списком. Разумная длина рекомендательного списка не должна превышать нескольких десятков отпечатков (на самом деле желательно 1 отпечаток), таким образом, избирательность поиска (относительная длина рекомендательного списка) должна быть не хуже 1(Г5 . Кроме информации, используемой для непосредственно для поиска, АДИС должна хранить исходные изображения отпечатков. Отсутствие изображений сильно усложняет работу эксперта и делает систему неработоспособной. Желательно иметь изображения в виде, максимально близком к исходному - разрешение 300 dpi, 256 уровней серого. На бинаризованных или скелетизированных изображениях могут отсутствовать детали, не используемые системой при поиске, но важные для визуального сравнения. При вводе дактилокарт работа оператора должна быть минимальной. В интерактивном режиме допустима только проверка правильности обнаружения интегральных особенностей и определения типа узора. Кодировка мелких особенностей и выделение информативных участков изображения должны осуществляться полностью автоматически. Должна иметься возможность интерактивной прорисовки низкокачественных изображений следов.
Должна иметься возможность работы со следами, имеющими неопределенный масштаб. Система состоит из следующих функциональных модулей (рис 4.1): ? Ввод дактилокарт; ? Ввод следов; ? Обработка и кодирование изображений отпечатков; ? Обработка и кодирование изображений следов; ? Прорисовка следов; ? Редактирование интегральных особенностей; ? Поиск; Дактилокарта представляет собой стандартный бланк, содержащий 10 отпечатков, полученных прокаткой, 10 контрольных оттисков и текстовую установочную информацию (рис 4.2) .
Нормальным для системы является режим автоматического позиционирования, предназначенный для ввода прокаток, расположенных на стандартных местах бланка. Выбор отпечатков и определение их границ происходит без участия оператора. Для обнаружения отпечатков анализируется средний уровень яркости в скользящем окне достаточно большого размера (32x32 пиксела) . Если обнаружены все 10 отпечатков и их взаимное положение соответствует формату бланка, соответствующие участки отсканированного изображения помещаются в БД дактилокарт. В противном случае система переходит в режим ручного позиционирования.
В режиме ручного позиционирования оператор имеет возможность указать положение и границы каждого отпечатка в отдельности. Этот режим используется: при работе с нестандартными бланками; при отсутствии некоторых отпечатков; при низком качестве отпечатка, когда оператор решает использовать контрольный оттиск.
