автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.01, диссертация на тему:Автоматизированная дактилоскопическая система

ВВЕДЕНИЕ.

ГЛАВА 1. СТРУКТУРА ДАКТИЛОСКОПИЧЕСКИХ ИЗОБРАЖЕНИЙ И ПРИЗНАКИ СРАВНЕНИЯ

1.1. Крупномасштабная структура отпечатка и интегральные особенности.

1.2. Папиллярные линии и мелкие особенности.

1.3. Искажения.

1.4. Избирательность и надежность поиска.

1.5. Выводы.

ГЛАВА 2. ОБРАБОТКА ИСХОДНОГО ИЗОБРАЖЕНИЯ И ВЫДЕЛЕНИЕ ОСОБЕННОСТЕЙ.

2.1. Анализ изображения.

2.2. Определение поля направлений.

2.3 Фильтрация поля направлений и восстановление интегральной структуры.

2.4. Выделение линий и мелких особенностей

ГЛАВА 3. ПРЕДСТАВЛЕНИЕ И СРАВНЕНИЕ ДАКТИЛОСКОПИЧЕСКИХ

ИЗОБРАЖЕНИЙ.

3.1 Интегральные особенности.

3.2. Представление папиллярного узора, инвариантное к геометрическим деформациям.

3.3. Координатный метод сравнения.

3.4. Топологическая характеристика особенности.

3.5. Сравнение с использованием топологических характеристик папиллярного узора.

ГЛАВА 4 . РЕАЛИЗАЦИЯ СИСТЕМЫ.

4.1. Общие характеристики.

4.2. Ввод дактилокарт.

4.3. Ввод следов.

4.4. Обработка и кодирование изображений отпечатков и следов.

4.5. Редактирование интегральных особенностей.

4.6. Поиск.'.

4.7. База данных.

4.8. Сервисные программы.

Идентификация человека по отпечаткам пальцев применяется в криминалистике уже более ста лет, но до последнего времени существовало серьёзное ограничение: отпечатки можно было использовать только для подтверждения личности. Поиск человека по оставленному отпечатку был реально невозможен. Причина этого в том, что невозможно построить достаточно подробную классификацию отпечатков, основанную на предварительно вычисляемых признаках. Поэтому поиск похожих отпечатков сводится к непосредственному сравнению изображения запросного отпечатка с каждым изображением из архива. Учитывая большие размеры дактилоскопических архивов, при ручной технологии это была практически неосуществимая задача. Вследствие этого идентификация папиллярных узоров была исторически одной из первых и исключительно важных для практики задач в области распознавания образов и обработки изображений. Новые идеи и методы традиционно апробировались на этой задаче. Длительное время это были интегральные методы сначала оптические, голографические, а затем цифровые методы фильтрации на основе преобразования Фурье. Существенный недостаток интегральных методов -низкая избирательность, делающая их непригодными для целей криминалистики. Реальный успех был достигнут только с разработкой структурных методов анализа и сравнения дактилоскопических изображений, основывающихся на деталях строения папиллярного узора и топологических соотношениях между ними. За последние 10-15 лет появились автоматизированные дактилоскопические информационно-поисковые системы (АДИС), пригодные для практического применения.

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

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

Целью диссертационной работы являлась разработка методов анализа и сравнения папиллярных узоров для использования в автоматизированной дактилоскопической информационно-поисковой системе (АДИС).

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

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

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

-Разработка метода сравнения отпечатков, использующего метрические и топологические характеристики деталей узора;

-Построение программной системы для анализа и сравнения дактилоскопических отпечатков;

-Экспериментальное исследование избирательности и надежности разработанных методов сравнения на больших массивах отпечатков.

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

Научная новизна работы:

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

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

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

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

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

6.Разработана дактилоскопическая информационно-поисковая система.

Практическая ценность.

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

Реализация результатовработы. Результаты диссертационной работы внедрены в рамках НИР, выполненной ФГУП НПП «РУБИН» по заказу департамента радиопромышленности Министерства промышленности РФ.

Диссертационные исследование выполнялись и реализовались так же в ПГУ по грантам Российского фонда фундаментальных исследований проект № 96-01-01363 «Теория признаков распознавания с позиций стохастической геометрии» и проект №00-01-00421 стохастической геометрии», по гранту Министерства Образования России в области кибернетики, автоматики и ВТ «Новая теория и системы генерации признаков распознавания изображений с позиций стохастической геометрии».

Положения, выносимые на защиту:

1. Новый спектральный метод определения поля направлений и его программная реализация.

2. Новый подход к построению интегральной модели изображения и выявлению интегральных особенностей.

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

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

5. Новая программная система для анализа и сравнения дактилоскопических отпечатков.

Теория распознавания образов основанная на

Результаты исследований публиковались в центральных Российских и и международных журналах: «Измерительная техника»

Российско-Американский журнал Pattern Recognition and Image Analysis (Advances in Mathematical Theory and Application); межвузовских сборниках и докладывались на международных и Всероссийских научных конференциях.

Публикации. По теме диссертации опубликовано 7 печатных работ, в том числе 4 статьи и 3 тезиса докладов.

Содержание работы.

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

ЗАКЛЮЧЕНИЕ.

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

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

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

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

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

5. Разработаны алгоритмы и программная реализация сравнения дактилоскопических отпечатков:

-по интегральным признакам,

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

-по топологическим характеристикам деталей узора.

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

6. На основе разработанных программ анализа и сравнения дактилоскопических изображений была создана Автоматизированная Дактилоскопическая Информационно-поисковая система.

7 Система была протестирована и прошла опытную эксплуатацию. Результаты испытаний показали эффективность ее практического применения для оперативных банков данных объемом до 200000 отпечатков.

1. Asai К., Kato Y., Noshino Y. (Nippon Electric Co.) Automatic fingerprint identification // 1.aging Application for Automated Industrial Inspection. SPIE, vol. 182.

2. Fingerprint Indentification. Federal Bureau of Investigation. U.S. Government Printing Office, Washington. D.C. 1992.

3. Hironori Yahagi, Selgo Igaki, Fumio Yamagishi (FUJITSU LABORATORIES LTD) Moving window algorithm for fast fingerprint verification. IEEE Southeastcon 90.

4. Martelli A. Sulla elaborazione di immagini me-diante la transformata di fourier bidimesionale. CAL-COLO, Supplemento n. 1. 1968, vol. V.

5. Noshino Y., Kato Y., Kiji R. Automatic Reading and Matching for Single Fingerprint Identification // The 65th International Association for Identification Conference. Ottawa, Canada, 1990.

6. Mokhtarian F. Fingerprint Theorm for Curvature and Torsion Zero-Crossing. IEEE, 1989.

7. Parshin N.M. Methods for Representation and Comparison of Fingerprints. // Pattern Recognition and Image Analysis. 1998, vol. 8. - No 3. - P. 439 - 441.

8. Janeseac K. Papillary Patterns // Imaging Application for Automated Industrial Inspection. SPIE, vol. 182.

9. Zhuravlev Yu.I., Gurevich I.В., Smetanin Yu.G. On the use of Entropy Base Feature in Image Recognition // Pattern Recognition and Image Analysis. 1995, vol. 5 . - № 4 .

10. Shen Xuening, Cheng Minde, Shi Qingyun. A New Automated Fingerprint Identification System // J. of Comput. Sci&Tecnol. 1989, vol. 4. - No 4.

11. Журнал Системы Папилон. Вып. 1. Миасс. 1994 .

12. Moran P.А.P. Measuring the length of a curve. // Biometrika. 1966, vol. 53. - P. 359-364.

13. Levine M. D. Feature extraction: a survey // Proc. IEEE, 57, 1391-1407 (August 1969) Русский перевод в журнале Труды ИИЭР, 57. 1969. - №8.

14. Davies E.R., Plummer А. P. Thinning Algorithms // Pattern Recognition. 1981, vol. 14. - № 1.

15. Nilson N. Adaptive pattern recognition: a survey // Bionics Symposium, Dayton, Ohio. May 1966.

16. Selfndge 0. G. Pattern recognition and modern computers. // Proc. Western Joint Compuler Conf. March 1955. P. 91 - 93.

17. Selfridge 0. G., Neisser U. Pattern recognition by machine in Compuiers and Thought. / E. A. Feigenbaum and J. Feldman eds. New York: McGraw-Hill. - 1963. -P.237 - 250.

18. Steinhaus H. Length, shape and area // Colloq. Math. 1954, vol. 3. - Р. 1 - 13.

19. Абезгауз Г.Г., Тронь А.П., Копенкин Ю.Н., Коровина И. А. Справочник по вероятностным расчетам. М.: Воениздат, 1966. - 408 с.

20. Амбарцумян Р.В., Мекке Й., Штойян Д. Введение в стохастическую геометрию. М.: Наука, 1989. - 400 с.

21. Анисимов Б.В., Курганов В.Д., Злобин В.К. Распознавание и цифровая обработка изображений. М. : Высшая школа, 1983. - 295 с.

22. Бакут П.А., Колмогоров В.И. Сегментация изображений: Методы выделения границ областей. // Зарубежная радиоэлектроника. 1987. - №10. - с. 25-47.

23. Бакут П.А., Колмогоров П.С., Ворновицкий И.Э. Сегментация изображений: Методы пороговой обработки. // Зарубежная радиоэлектроника. 1987. - №10. - с.6-24.

24. Бейтс Р.Х.Т., Гарден К.Г., Питере Т.М. Реконструктивная вычислительная томография: Современные достижения и перспективы развития // ТИИЭР. -198 3. №3.

25. Бейтс Р.Х. Реконструкция и восстановление изображений. М.: Мир, 1989.

26. Белозерский Л.А. Основы построения систем распознавания образов. / Курс лекций, Донецкий Государственный Институт Искусственного Интеллекта. 1997.

27. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов. М.: Мир, 1989. - 448 с.

28. Блум Г. Ассоциативная машина, опознающая зрительные образы. В сб. Проблема бионики. -М. : Мир, 1965.

29. Брандт 3. Статистические методы анализа наблюдений. М.:Мир, 1975.

30. Бутаков В.А., Островский В.И., Фадеев И.Л. Обработка изображений на ЭВМ. М. : Радио и связь, 1987.- 240 с.

31. Быков Р., Гуревич Б. Анализ и обработка цветных и объемных изображений. М: РиС, 1984.

32. Быстрые алгоритмы в цифровой обработке изображений / Под ред. Хуанга Т.С. М.: Радио и связь, 1984.- 182 с.

33. Бэрроу X. Дж., Тененбаум Дж. М. Алгоритмическое зрение. // ТИИЭР. 1981. - №5.

34. Васильев В.И. Распознающие системы. / Справочник. Киев: Наукова думка, 1983. - 422 с.

35. Вентцель Е.С. Теория вероятностей. М. : Физ-матгиз. - 1958. - 464 с.

36. Воробьев H.H. Теория рядов. М. : Наука, 1979.- 408 с.

37. Вудс Р.Э., Гонсалес P.C. Цифровые методы улучшения изображения в реальном времени. // ТИИЭР. 1981.- № 5.

38. Выгодский М.Я. Справочник по высшей математике.- М.: Наука, 1966.

39. Гельфанд И.М., Граев М.И., Виленкин Н.Я. Интегральная геометрия и связанные с ней вопросы теории представлений. М.: Физматгиз., 1962. - 656 с.

40. Горелик А.Л., Гуревич И.В., Скрипкин В.А. Современное состояние проблемы распознавания. М. : Радио и связь, 1985. - 160 с.

41. Горелик А.Л., Скрипкин В.А. Методы распознавания. М.: Высшая школа, 1989. - 232 с.

42. Гренандер У. Лекции по теории образов: В 3-х томах. М.: Мир, 1979. -1983.

43. Гудмен Дж. Введение в фурье-оптику. М.: Мир, 1970 .

44. Даджион Д., Мерсеро Р. Цифровая обработка многомерных сигналов. М.: Мир, 198 8. - 488 с.

45. Девис М.Х.А. Линейное оценивание и стохастическое управление. М.: Наука, 1984. - 208 с.

46. Джайн А.К. Успехи в области математических моделей для обработки изображений. // ТИИЭР. 1981. - № 5 .

47. Дуда Р., Харт П. Распознавание образов и анализ сцен. М.: Мир, 1976.

48. Ерош И.Л. Применение преобразований Крестенсона для определения параметров положения объектов по плоским проекциям. // Техническая кибернетика. 1981.3 .

49. Журнал Системы Папилон. Вып. 2. Миасс. 1996.

50. Иванова В.М., Калинина В.Н., Нешумова Л.А., Решетникова И.О. Математическая статистика. М. : Высшая школа, 1975. - 367 с.

51. Ильясова Н.Ю. Методы и алгоритмы оценивания геометрических параметров диагностических изображений.- Самара, 1999.

52. Карасев А.И. Теория вероятностей и математическая статистика. М.: Статистика, 1979. - 279 с.

53. Кассандрова О.Н., Лебедев В. В. Обработка результатов наблюдений. М.: Наука, 1970. - 104 с.

54. Кендал М., Моран П. Геометрические вероятности.- М.: Наука, 1972. 192 с.

55. Кимбл Дж. И., Джармези Н. Обнаружение пороговых сигналов и принятие решения.

56. Краткое пособие по дактилоскопии.- Киев, 1969.

57. Лабунец В.Г., Чернина С.Д. Теория и применение преобразования Хо. // Зарубежная радиоэлектроника. 1987. №10.

58. Луитт P.M. Алгоритмы реконструкции с использованием интегральных преобразований. // ТИИЭР. 1983.3 .

59. Марпл С.Л. Цифровой спектральный анализ. М. : Мир, 1990.

60. Марр Д. Зрение: информационный подход к изучению представления и обработки зрительных образов. М. : Радио и связь, 1987. - 400 с.

61. Матерон Ж. Случайные множества и интегральная геометрия. М.: Мир, 1978. - 318 с.

62. Мучник И.Б. Алгоритмы формирования признаков для зрительных образов. Т.10. АиТ. - 1966.

63. Надь Г. Распознавание образов. Обзор. // ТИИЭР. № 5. - 1968. - С. 57 - 86.

64. Павлидис Т. Алгоритмы машинной графики и обработки изображений. М.: Радио и связь, 1986. - 400 с.

65. Паршин Н.М. Автоматизированная дактилоскопическая система // Измерительная техника. 1997. - № 9. -С.22 - 24 .

66. Паршин Н.М. Использование интегральной модели для обнаружения и распознавания объектов на сильно за-шумленных изображениях // Международный симпозиум «Надежность и качество 2001». Сборник докладов. Пенза, 2001. - С.375 - 376.

67. Паршин Н.М. Методы представления и сравнения дактилоскопических отпечатков // III Международная конференция «Распознавание образов и анализ изображений: новые информационные технологии» (РОЛИ'97). Сборник докладов. Нижний Новгород, 1997. - С.278 - 280.

68. Паршин. Н.М. Алгоритм быстрого сравнения дактилоскопических отпечатков // Новые информационные технологии и системы. / Материалы II Международной научно-практической конференции. Часть I. - Пенза, 1996. -С.31 - 32.

69. Патрик Э. Основы теории распознавания образов. М.:Радио и связь, 1980. - 408 с.

70. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. М.: Мир, 1989. - 478с.

71. Применение методов Фурье-оптики / Под ред. Старка Г. М.: Радио и связь, 1988. - 536 с.

72. Прэтт У. Цифровая обработка изображений. В 2 кн. М.: Мир, 1982. - 790 с.

73. Пугачев B.C. Теория вероятностей и математическая статистика. М.: Наука, 1979. - 496 с.

74. Роджерс Д. Алгоритмические основы машинной графики. М. : Мир, 198 9.

75. Розенфельд А. Распознавание и обработка изображений. М.: Мир, 1972. - 230 с.

76. Розенфельд А. Распознавание и обработка изображения с помощью вычислительных машин. М.: Мир, 1972. - 231с.

77. Розенфельд А. Распознавание изображений. // ТИИЭР. 1981. - № 5.

78. Сантало JI.A. Интегральная геометрия и геометрические вероятности. М.: Наука, 1983. - 360 с.

79. Солодовников А.И., Спиваковский A.M. Основы теории и методы спектральной обработки информации.1. Л.: Изд. ЛГУ, 1986.

80. Теория и практика дактилоскопической экспертизы. М., 1971.

81. Технические и программные средства комплексов ввода и цифровой обработки изображений. Под. ред. Прохорова Н.Л. Сб. научных трудов Ин-та электр. управл. машин. - М., 1989. - 124 с.

82. Трофимов Б.Е., Куликовский О. В. Передача изображений в цифровой форме. М.: Связь, 1980. - 120 с.

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

84. Файн B.C. Опознавание изображений. М.: Наука,1970. 296 с.

85. Федотов Н.Г. Методы стохастической геометрии в распознавании образов. М.: Радио и связь, 1990. - 144 с.

86. Федотов Н.Г., Кадыров А. А, Паршин Н.М. Возможности стохастической геометрии для распознавания изображений // Цифровые модели в проектировании и производстве РЭС / Межвузовский сборник научных трудов. Пенза, 1996. С.117 - 120.

87. Харалик P.M., Келли C.JI. Использование методов распознавания образов и автоматической классификации для анализа многокомпонентных изображений. // ТИИЭР. -1969. № 4. - С.316 - 339.

88. Хелгасон С. Группы и геометрический анализ. -М.: Мир, 1987. 736 с.

89. Хорн Б.К. Зрение роботов. М.: Мир, 1989.

90. Ценсор Я. Методы реконструкции изображений, основанные на разложении в конечные ряды. // ТИИЭР. 1983. №3.

91. Шведов A.M., Шмидт A.A., Я кубович В.А. Инвариантные системы признаков в распознавании образов. // Автоматика и телемеханика. 197 9. - № 3.

92. Дактилоскопическая экспертиза. М., 1969.

93. Яншин В., Калинин Г. Обработка изображений на языке С для IBM PC. М.: Мир, 1994.

94. Ярославский Л.П. Быстрые алгоритмы в цифровой обработке изображений / Под ред. Хуанга. М.: Радио и связь, 1984.

95. Ярославский Л.П. Введение в цифровую обработку изображений. М.: Сов. радио, 1979.

96. Иванов А.И. Биометрическая идентификация личности по динамике подсознательных движений: монография. -Пенза, Изд ПГУ, 2000.