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

ИНСТИТУТ ПРОБЛЕМ ИНФОРМАТИКИ РОССИЙСКОЙ АКАДЕМИИ НАУК

РГб од

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

- '4 •• <■> 1.

УДК 519.218

НОВИКОВ Сергей Олегович

КРИТЕРИИ ОПТИМАЛЬНОСТИ И СПОСОБЫ ПРЕДСТАВЛЕНИЯ ДАННЫХ В ЗАДАЧАХ ИДЕНТИФИКАЦИИ ОТПЕЧАТКОВ ПАЛЬЦЕВ

Специальность 05.13.17 - "Теоретические основы информатики"

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических

наук

Москва -1997

Работа выполнена в Институте проблем информатики РАН.

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

профессор И.Н. Снннцын Официальные оппоненты - член-корреспондент РАН,

профессор А.П. Реутов

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

Н.С.Поликарпова

Ведущая организация - Вычислительный Центр РАН

Защита состоится 13 ноября 1997 года в 14 часов на заседании специализированного Совета Д003.56.01 при Институте проблем информатики РАН (Москва, Вавилова, 30/6).

С диссертацией можно ознакомиться в библиотеке Института проблем информатики РАН.

Автореферат разослан 13 октября 1997 года.

Ученый секретарь специализированного Совета

доктор технических наук

С.Н. Гринченко

Актуальность работы

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

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

Основные этапы решения задачи, сформировавшиеся на современном уровне, перечислены в работе N.K.Ratha, K.Karu, S.Chen и \.KJain, методы, используемые на ранних стадиях предобработки, тредложены в работах B.G.Sherlock, D.M.Monro, K.Millard, B.M.Mehtre, N.N.Murthy, S.Kapoor, B.Chatteijee, некоторые методы ¡ычисления поля направлений и предварительной классификации )тпечатков пальцев (ОГТ) описаны в работах M.Kawagoe и A.Tojo, шализ некоторых методов выделения сингулярных особенностей триведен в работах V.S.Srinivasan и N.N.Murthy, способы оптимальной фхивации дактилоскопической информации рассмотрены в работах 4.0tsu, J.Bradley, C.Brislawn, T.Hopper.

В настоящее время за рубежом широко используются следующие :истемы: "MORPHO" (Франция), "Printrak" (США), "NEC" (Япония). Вследствие слабого развития имеющейся в России технологической 5азы, отечественным разработчикам пришлось довольствоваться )бщедоступными средствами вычислительной техники, что определило сонкурентоспособность российских АДИС на внутреннем рынке. Последнее объясняется опережающими темпами развития дшверсальных схемотехнических решений в стандартных приложениях, ю сравнению со временем реализации сложных технологий на лецпроцессорах. Другим преимуществом отечественных систем шляется их относительная дешевизна, однако, рост себестоимости, (атрат на сервисное обслуживание, связь и т.д, обусловленные общим шдением производительности труда, постепенно приводят к (ыравнивашпо цен. Поэтому, чтобы не допустить отставания хотя бы в

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

Цели и задачи работы

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

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

- выделить и обосновать основные этапы предобработки исходных изображений ОП;

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

- получить максимально полное и при этом устойчивое описание ОП;

- определить эффективную и устойчивую (в рамках балансировки ошибок первого и второго рода) меру сходства двух описаний ОП;

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

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

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

Методы исследования

В работе использованы современные методы цифровой обработки изображений (ЦОИ) и распознавания образов, теории кодирования с устранением избыточности, теории сложности, методы субоптимального решения трудновычислимых задач, а также методы статистического моделирования на ЭВМ.

Научная новизна

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

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

поставлена и решена задача получения поля направлений в каждой точке;

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

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

- получен ряд новых методов классификации ОП;

добавлен новый этап окончательной коррекции скелетона, приводящий к значительному повышению поисковых характеристик :истемы;

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

- разработан алгоритм подавления неравномерности плотности шний;

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

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

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

Апробация работы

Об основных материалах, относящихся к содержанию работы, было доложено на следующих научных конференциях:

- III Всесоюзной конференция "Математические методы распознавания образов", Львов, 1987.

- Международная конференция "DIP-97" , Вена, 1997.

АДИС "УЗОР", в которой реализованы методы и средства, представленные в диссертации, прошла тестирование ВНКЦ МВД РФ.

Публикации

По теме диссертации опубликовано 8 печатных работ.

Структура и объем работы

Диссертация состоит из введения, четырех глав и заключения. Содержание работы изложено на 101 страницах машинописного текста, иллюстрированного 52 рисунками и 3 таблицами. Список использованных источников составляет 44 наименования.

Содержание диссертации

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

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

Щ=<х,,у,,а„!1,а1>, (1)

где х1,у1 - координаты особенности относительно некоторой точки

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

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

1) Предобработка:

1.1) улучшение качества изображения: подавление высокочастотных шумов и неравномерности яркости ПЛ, которая практически всегда имеет место в связи с особенностью нажатия при откатке или приложении отпечатка, особенностями поверхности, на которую наносится отображение отпечатка и т.д.;

1.2) построение изображения (поля) направлений, в котором в каждая точка получает значение, равное оценке угла направления потока в достаточно большой окрестности данной точки (примерно ±15 периода структуры по каждому из направлений);

1.3) сегментация изображения с учетом поля направлений;

1.4) отделение фона, неконтрастных и слишком зашумленных частей;

1.5) оценка качества исходного изображения;

1.6) скелетизация сегментов, соответствующих папиллярным линиям.

2) Выделение признаков:

2.1) локализация глобальных сингулярных особенностей (центров-цельт);

2.2) получение интегрального описания (классификации) типа узора;

2.3) корректировка скелетона и выделение и параметризация покальных особенностей.

3) Формирование окончательного описания отпечатка.

4) Определение меры сходства и критерия идентичности.

Во второй главе рассмотрен общий критерий минимальной длины описания (МДО), применимый в широкой области задач обработки и анализа изображений, начиная с этапа описания данных, и заканчивая окончательным представлением информации. В §2.1. приводится иллюстрация техники использования критерия МДО для оценки параметров линейной динамической системы. В §2.2. дается обоснования представления информации об изображении в виде многоуровневой системы, в которой на каждом уровне представление определяется данными (исходной информацией на нулевом уровне и описанием разбиения предыдущего уровня на остальных), характеристической функцией их описания (например, энтропией в :лучае статистически оптимальных кодов Хаффмена) и способом разбиения. При этом прослеживается понижение размерности

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

£(/)=S(/)tog<r1 (/)+(Sr-S(/))logCT2 (/),

где и(0- количество пиксел со значением Г, S(t) - количество элементов исходного изображения, превосходящих t, Sj - общее количество элементов изображения,

2 (''--"1«))2«(0, /Ч«— Z« «(О, bT-b(t)i=t+j ¿7--H');=/+i

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

В §2.4. показана идентичность критерия МДО и критерия, состоящего в получении максимальной площади прямолинейных сегментов, в случае выделения частных признаков для отождествления канала ствола по выстреленной пуле. В третьей главе подробно рассмотрены информационная технология решения задачи идентификации ОП и способы представления данных. В §3.1. предложены быстрые алгоритмы улучшения качества изображения ОП на начальном этапе с реализацией оператора LG box-фильтрами.

В §3.2. рассмотрен один из основных этапов предобработки ОП,

состоящий в вычислении поля направлений. Изложен традиционный подход к вычислению ПН в ячейках фиксированного разбиения, введено общее определение ПН для оценки ПН в каждой точке по большому плавающему окну, предложены методы предварительной оценки ПН и ее последующего сглаживания по большой окрестности методами медианной фильтрации, главной оси тензора инерции и повышения кратности. Предлагаемые алгоритмы имеют линейную сложность, не зависящую от размера используемой окрестности. В §3.2.4. предложены методы использования ПН для кодирования изображений с высокой степенью сжатия. В §3.3. описан метод бинаризации изображения ОП с использованием направленных фильтров при известном ПН. В §3.4. предложен быстрый алгоритм для организации итеративной процедуры скелетонизащш бинарного изображения, кроме того предложен алгоритм геометрической коррекции для подавления ложных разрьюов с целью увеличения устойчивости к шумам при выделении локальных особенностей. Следует отметить, что в большинстве существующих публикаций, относящихся к задаче обработки бинарных изображений отпечатков пальцев данный этап либо отсутствует, либо по каким-то причинам не освещается, однако использование одной лишь фильтрации по ПН недостаточно для подавления нестабильных (неповторяющихся при предъявлениях одного и того же отпечатка в различных условиях) особенностей и, таким образом, этап подавления ложных разрывов на скелетоне можно считать вторым по важности после вычисления ПН для стадии предобработки.

В §3.5. показано, что для оценки качества исходного изображения на заданном участке более целесообразно оценивать разность энтропии направлений, вычисленных в каждой точке изображения на данном участке до и после усреднения. При хорошем качестве изображения вблизи центра (дельты) значение энтропии будет велико, но изменится незначительно. Данный принцип хорошо зарекомендовал себя на практике применения системы "УЗОР-З", где автоматически определенная оценка качества исходного материала практически всегда совпадает с субъективной оценкой оператора.

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

В §3.7. предложены методы предварительной классификации ОП по общей структуре ПЛ с использованием энергетического спектра преобразования Хафа; траектории приближения к центру при вычислении сингулярной особенности релаксационным методом;

траекторий обхода вдоль ПН, начиная с некоторых точек вблизи центра. Последний метод позволяет с точностью 95% выполнять

классификацию па 15 основных типов узора, прпишых в криминалистической мрикмнче. Кроме того предложен весьма > \¡'.-к; :::■!'!.и": меюд "иесгро! <ч"Г классификации по статистике

••• •• .-.«с:! 'М'МЧ ('••О'" !•.*!!. СОСТОЯЩИЙ !'. с:н"!\''0!4-.'\г. 1'\!1м.1

I.. , .к ,.чи сп. ¡¡V'.;}'¡¡! и, ;мчс (с 'ючноо.! ыо ч„> л^чнч^а

с! пук р 7.1) положение точки отсчета, выберем максимально возможную область вокруг этой точки, которая будет устойчиво повторяться при различных предъявлениях одного н того же отпечатка: для случая чисто идентифицирующих систем - это зона с диаме тром 2540 периодов структуры (ПС). Относительно вычисленной точки отсчета разобьем плоскость на т секторов и в пределах данной зоны введем следующее описание локальных особенностей:

и^«*, ,//,*/>, 0=1,..,п). (2)

где .у. - номер сектора, соответствующего положению точки,

однозначно определяемый координатами (х- , ) в представлении (1).

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

вычислим шетшрамму II(а,!), где - обозначает количество

, доя которых имеет место соответствие: я—л, а^-а, ¡¡=1. Для

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

/|5(а,/). Поскольку при таком способе интегрального описания возникает неопределенность к повороту па к/ £тах, следует вычислить

новее описание тг, по липу (2). по 1:одучещтом\' из (!)

¡¡осле Пу>|1оро1а па ,т/.у , после чего описанным виые способом

получаем ноьую функцию и' («,/). Окончательное описание топологических признаков будет иметь вид:

уа,/Ц(Л4(а,/)+£/(«*,/)) •

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

Действительно, обозначим через Ц - описание

предъявляемого отпечатка, а через Ц' - описание текущего кандидата

из базы данных. Требуется вычислить следующее значение:

0=1 (ЛА.(я,/)-//',(« Л)2 • «,/

¡псдык« по <ч;1!с;и::!1о (2) >'.:.пп раз вычисляем /? ., ••!!;••:.гпя н~(и,1) вычисляются заранее па лапе кодирования и заносятся в

а,1

базу данных, тогда для определения Б достаточно вычислить

I

2 ЕЛ.// = 2 £ 1/ (а.,/.) • Таким образом достаточно п сложении, где л -

/5 5 . 1 5 II '=1

количество локальных особенностей (мишоцнн) в описании отпечатка из базы данных. Данный алгоритм линейный по сложности и вычисляется за время меньшее времени доступа к данным. При адекватном подборе параметров, допусков и ограничении данный способ интегрального описания топологических особенностей дает степень разбиения базы данных более 1000 с вероятностью 98%, что с учетом скорости вычислит:! делает его идеальным для чисто идентифицирующих систем, работающих с полной информацией. Окончательный алгоритм совмещения в общем случае квадратичный по сложности, поэтому его следует использовать на втором этапе, сократив предварительно объем анализируемых данных в 1С00 раз указанным выше образом.

В §3.8. предложен метод выделения п описания локальных особенностей по обработанному скелетону.

В §3.9. предложена эффективная функция оценки меры сходства дт-ух описаний ОГТ, использующая I! основном метрические параметры в описании. Для ее определения необходимо сделать некоторые предположения. Допустим, что в базе данных хранятся описания полностью откатанных отпечатков хорошего качества. Данное условие означает, что при совпадении латентного отпечатка (следа) и кандидата из базы данных, в пределах круговых зон с некоторым радиусом & (различимого участка на следе) в идеальном случае не должно быть ни одной несовпавшей точки кандидата. Величина & зависит от качества следа, однако она в любом случае должна превосходить 1.5 ПС, в противном случае на следе невозможно выделить особенность даже вручную.

Пусть на входе имеется два списка описаний локальных

особенностей вида (1) {т?}"^ и {т?}^, соответствующих следу и кандидату из базы данных. Две особенности считаем совпавшими если расстояние между ними не превосходит некоторой величины 8г

{дг <&), разность углов направлений не превосходит За, а разность топологических параметров не превосходит 31 ■ Величины ограничений задаются заранее и считаются параметрами системы. Обозначим через у(«) индекс особенности из второго списка, совпадающей с 1-й особенностью первого списка и ближайшей к ней (считаем у(/)=0, если такой точки нет).

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

12 1 "1

Цт ,т ;<5г,&,<5а,Я) =-5- X /аЦМ!ЖЩ .¿г (», К«))) -

тахСп^СД))/»! (3)

1 2

I1-!2 7 Ч>(0

1,2 1,2

где м>+, \1>_, \1>а, - положительные весовые коэффициенты; п\ (&) - обозначает количество особенностей кандидата в пределах зоны различимости следа; и''2- количество совпавших особенностей;

п= в {у шах(«[, п\ (&)) — и''2) - количество несовпадений с учетом возможного наличия ложных особенностей (скажем, если точность описания составляет 90%, то у = 0.9). 6(х) - в -функция;

/•( = +СУ/1)2 • ¿г0>(0) обозначает расстояние между точками

(х},у!) и (<0,у10)); ¿/а - определяет разность углов; fa- функция

соответствия атрибутов типа особенностей, принимающая следующие значения:

О, если у(/) = 0,

/<,('. КО) =

1.15, если а,'=а2

КО' 1 ^

0.85, если а,

Оптимальные значения /а были подобраны эмпирически и, как

видно, дают незначительный вклад в общий функционал, поскольку классификация по типам особенностей в значительной степени субъективна. Принципиальное значение в определении (3) имеет функция (7, определяющая качество соответствия двух конкретных особенностей. Поскольку имеет место определенная особенность реальных деформаций, состоящая в том, что при повторном

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

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

, J% 2 d d 2 ÍA2

s(r,d)=—arceos----, r -1 — I

* 2r 2лг \ W '

В качестве G(r^) можно взять s(rtg(ac ),d) при d<2r и 0 в остальных

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

(£-1)2 s(rtg(ac),d)--

G(r,d)=^=- f е v di;, \ 2тгег о

При выборе <т=0.5 достигается повьппение степени разбиения базы данных примерно на порядок.

Поскольку центры отсчетов могут быть смещены (и весьма существенно) окончательно мера сходства (при фиксированных ориентации и масштабе) определяется итеративно. Считаем на нулевом шаге m1 (0) = m1 • Пусть на шаге t в соответствии с (3)

вычислена ¿(w^f)^). Обозначим через /¿(/) индекс особенности из второго списка, совпадающей с /-й особенностью списка /и1 (í) в окрестности с радиусом 5R>Sr и ближайшей к ней (считаем //(«') =0, если такой точки нет). Вычисляем вектор смещения с координатами

S «•»kcH«)! Z 0(f(i))\yl(i)-y}(t)]

dx=—-^--, dyj^-JJ-:-- .

ÍOÍK 0) Í<Kf¿(0)

«=1 i=l

Сформируем новый список т1 (/ +1) совпадающий с т1 (?) по всем компонентам, кроме координат, которые сдвигаются в направлении вектора смещения:

*;(/ + !) = у]Ц + \) = у,,+(1у. (4)

Вычислим новое значение Ь(тх (7 +1), т2). Если использовать чисто градиентный метод, то следует выбрать следующую процедуру

А

для определения меры сходства при оптимальном совмещении!,: если Ь{тхЦ + \),т2)> Цт\0,т2) переходим к следующему ша шагу

итерации; в противном случае итерации прекращаются и Ь принимается равным Ь(тх^),т2)- Однако в большинстве случаев достигается локальный максимум на расстоянии до 2ПС независимо от величины > поэтому в случае неопределенного центра следует применить процедуру, аналогичную имитации отжига. При этом поскольку общая тенденция сдвига практически всегда сохраняется, несколько видоизменим (4):

*; (*+1)=х;+у{1)ск, у; (1+1)=у;+

где у(/) - функция, плавно спадающая, начиная с некоторой достаточно большой величины (скажем - 4) до 1. Сдвиг принимается всегда, когда

1(т1(( + 1),т2)>Цт1(0,т2), и с вероятностью

ехр^ои'о-*-0.»') -¿0»'(0.«'») в противном случае"

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

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

Именно первое слагаемое в правой части (3) обеспечивает "мягкость" функционала меры сходства и, как следствие, устойчивость к деформациям "резинового листа" и фиксированному диапазону

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

В § 3.10 рассмотрены стандартные способы архивации исходных изображений ОП.

В § 3.11. изложены последние перспективные результаты, относящиеся к моделированию естественных процессов порождения ОП и регенерации ОП на поврежденных участках. Предложен механизм порождения поля направлений из хаотического вихря, наложенного на фоновое поле, определяемое только формой пальца. Рассмотрен направленный вариант оператора Марра (Г.Н. Глущенко) дня моделирования порождения локальных особенностей при заданном ПН, однако он включает в себя два масштабных параметра, определяемых локальным ПС. Для адаптации к периоду структуры в каждой точке предложен другой метод, состоящий в следующем: считаем, что исходное бинарное изображение имеет два уровня -1 и 1; в каждой точке для оптического профиля, определяемого отрезком с центром в данной точке и направленного перпендикулярно ПН в этой точке, вычисляется гармоника максимальной мощности в пределах заданного диапазона частот, результатом преобразования будет изображение, определяемое резонансом соответствующих гармоник по всему полю изображения, затем производится сглаживание вдоль ПН и бинаризация по нулевому уровню. Данная последовательность операций итеративно повторяется несколько раз (количество итераций определяется степенью искажения). Примеры восстановления отпечатка адаптивно-резонансным методом приведены на Рис. 1. В некоторых случаях появляются ложные особенности, однако они имеют неустойчивый характер (перемычки, островки) и могут быть исключены на этапе выделения локальных особенностей.

Используя предложенную модель, были получены следующие результаты, которые могут оказаться полезными и для криминалистики:

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

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

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

а*

(в) (г)

Рис. 1. Иллюстрация восстановления и регенерации отпечатка адаптивно-резонансным методом: (а)- изображение с 50% белым шумом и 20% площади отсутствующей части; (б) - результат восстановления изображения (а); (в) - изображение с 50% площади отсутствующей части; (г) - результат восстановления изображения (в).

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

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

6) используя ту же итеративную модель усреднения, можно восстанавливать поле направлений на искаженных или отсутствующих участках площадью до 50% от всего изображения;

7) искусственно порожденные направленным оператором Марра изображения восстанавливаются (с точностью до особенностей!) на полосах, площадью до 50% от площади всего изображения, возможно

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

В главе 4 приведены основные характеристики программных реализаций методов и алгоритмов, предложенных в диссертации, в поисковых системах класса "УЗОР" и систем идентификации личности и санкционированного доступа класса "TIP".

Основные результаты работы

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

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

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

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

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

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

сифицируются как шумовые.

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

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

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

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

Разработанные методы и средства были реализованы в реальных системах идентификации, в частности, в идентифицирующей системе "TIP" и в АДИС "УЗОР", находящейся в эксплуатации с 1995 г. в ГУВД и в ЭКО ЮЗАО г. Москвы.

Основные опубликованные работы по теме диссертации

1. Новиков С. О. Перспективы использования методов кодирования изображений, основанных на априорной информации специального вида// Тезисы докладов III Всесоюзной конференции "Математические методы распознавания образов". Львов, 1987.

2. Новиков С. О. Критерии оптимальности в задачах представления видеоданных// в кн. Системы и средства информатики. М.: Наука. 1989. Вып. 1. С. 98-106.

3. Новиков С.О. Идентификация локальных особенностей изображений в условиях сильных шумов и непараметризуемых деформаций// в кн. Системы и средства информатики. М.: Наука, 1992, Вып.З. С. 134-145.

4. Новиков С.О. Комбинированный метод сжатия информации с использованием оптимального переквантования//в кн. Системы и средства информатики. М.: Наука, 1993, Вып.4. С. 154-162.

5. Новиков С. О. Программа кодирования и поиска отпечатков пальцев// Свидетельство об официальной регистрации программы для ЭВМ No 950336, Российское агенство по правовой охране программ, баз данных и топологий интегральных микросхем (РосАПО), 1995.

6. Новиков С. О. Программа кодирования, поиска и совмещения оцифрованных изображений разверток поверхностей стреляных пуль// Свидетельство об официальной регистрации программы для ЭВМ No 960546, Российское агенство по правовой охране программ, баз данных и топологий интегральных микросхем (РосАПО), 1996.