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

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

Для служебного пользования Экз. № У

УДК 681.3.06 (082)

ЧЕРНЯВСКИЙ Юрий Александрович

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

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

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

Минск 2000

Работа выполнена в Научно-исследовательском институте прикладных физических проблем им.А.Н.Севченко при БГУ

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

Ревинский Виктор Викентьевич

кандидат технических наук доцент Козловский Николай Иванович

Официальные оппоненты: доктор технических наук профессор

Садыхов Рауф Хосровович

доктор физико-математических наук профессор Харин Юрий Семенович

Оппонирующая организация - Ордена Трудового Красного Знамени

Институт технической кибернетики Национальной академии наук Беларуси

Защита состоится 22 декабря в Ю00 часов на заседании совета по защите диссертаций Д 02.01.14 при Белгосуниверситете (220050 Минск, пр.Ф.Скорины, 4, главный корпус, ауд. 206, телефон ученого секретаря 226-55-41).

Автореферат разослан «_ //» ноября 2000 г.

Ученый секретарь совета по защите диссертаций

О.М.Тихоненко

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

Актуальность темы диссертации

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

Связь работы с крупными научными программами, темами

Диссертация выполнена в рамках межвузовской программы фундаментальных исследований: «Разработать теорию гибких технологий параллельно-кольцевой и табличной обработки измерительной информации и создать на ее основе многофункциональные модульные средства нового поколения с перестраиваемой архитектурой для автоматизации научных исследований и производственно-технологических процессов». (Шифр «Модуль». Утверждена приказом Минобразования от 16.02.96 г. № 60, головная организация-исполнитель НИИ ПФП).

РОССИЙСКАЯ ; ГОСУДАРСТВЕННАЯ '

_ БИБЛИОТЕКА

Цель и задачи исследований

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

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

• усовершенствовать основные этапы классификационного анализа (КА) латентных ДИ и следов, оказывающие решающее влияние на скоростные и качественные характеристики анализа и включающие формирование поля направлений ДИ, скелетизацию, логическую коррекций и пространственно-топологическое кодирование ДИ;

• разработать быстрые алгоритмы сравнения латентного и отдельного файлового ДИ, обеспечивающие высокую степень достоверности результатов сравнения ОП при адаптивном изменении используемых объемов пространственно-топологических кодов сопоставляемых ДИ и регулируемой скорости сравнения;

• разработать способ ускорения поиска в базе данных набора файловых ДИ, имеющих максимальные меры (веса) сходства с анализируемым ДИ;

• оценить качественные характеристики АДИС, включая производительность и достоверность конечных результатов.

Объект и предмет исследования

Объектом исследований являются процессы обработки информации в АДИС. Предмет исследования - скоростные алгоритмы первичной обработки ДИ, кодирования и сравнения ОП, оценка качественных характеристик функционирования АДИС.

Методология и методы проведения исследования

Использовались:

• теория распознавания образов и обработка изображений;

• теория восстановления и реконструкции изображений;

• теория и методы параллельных вычислительных структур;

• математическое моделирование сложных систем;

Научная новизна полученных результатов

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

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

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

4. Разработаны эффективные методы и алгоритмы сравнения латентного и отдельного файлового ДИ, основанные на формировании меры их сходства в рамках многопараметрического критерия, который помимо детального совместного анализа ЛХ требует также сопоставления топологий ДИ. Определена структура арифметико-логического расширителя, предназначенного для выполнения алгоритма сравнения ДИ. Предложена трехуровневая каскадная классификация ДИ по типу узора, его ориентации на плоскости изображений и значению интегральной пространственно-топологической характеристике. На этой основе разработана оригинальная методика ускоренного поиска в базе данных структурно-подобных ДИ.

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

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

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

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

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

Основные положения диссертации, выносимые на защиту

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

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

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

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

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

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

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

6. Комплексная реализация градиентно-релаксационной технологии определения поля направления латентного ДИ, метода кодирования ОП, адаптированного по отношению к объему используемого набора базовых ЛХ и количеству пересечений топологическими линиями базовых радиальных лучей, и алгоритма сравнения ОП на основе многопараметрического критерия идентичности ДИ позволила обеспечить высокую надежность функционирования разработанной АДИС - вероятность правильной идентификации отпечатков, полученная на базе данных НИИ специальной техники МВД РФ, г. Москва из 7x106 ДИ, не менее 0,82, что на 10-15% выше результата для аналогичных систем.

Личный вклад соискателя

Работы по созданию новых средств идентификации ДИ, отличающихся от существующих более высокой производительностью и качеством обработки ДИ, ведутся лабораторией специализированных вычислительных систем НИИ ПФП под руководством д.т.н. В.В. Ре-винского с 1985 года. Соискатель участвовал в этих работах с 1996 года, начиная с выполнения дипломной работы (1996-1997 учебного года) и включая все годы обучения в аспирантуре университета. Основные результаты диссертационной работы получены автором самостоятельно.

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

Совместно с к.ф.-м.н., в.н.с. М.Ю. Селяниновым и с.н.с. С.М. Завгородневым разработан комплекс методологических и программно-алгоритмических средств.

Сравнительный анализ производительности методов обработки бинаризованных ДИ осуществлялся совместно с В.В. Ревинским, Н.И. Козловским, A.A. Колядой и М.Ю. Селяниновым.

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

Апробация результатов диссертации

Результаты диссертации докладывались:

• научной конференции, посвященной 75-летию Белгосуни-верситета, Минск, Белгосуниверситет, 1996 г;

• 8-ой Белорусской математической конференции с международным участием, г.Минск, Белгосуниверситет, 2000 г;

• научных семинарах лаборатории специализированных вычислительных систем НИИ ПФП.

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

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

По теме диссертации опубликовано: 7 статей, 1 тезис доклада на конференции. Общее количество страниц опубликованных материалов составляет 43.

Структура и объем диссертации

Диссертация состоит из введения, общей характеристики работы, четырех глав, выводов и заключения. Она изложена на 123 страницах, содержит 6 иллюстраций, 9 таблиц, список литературы из 42 наименований на 5 страницах, 2 приложения на 18 страницах.

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

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

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

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

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

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

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

Рассмотрена организация процесса идентификации латентного ДИ на основе операции эталонного детектирования топологических структур и геометрических конфигураций ДИ, преобразования выделенных конструкций, извлечения характерных деталей (ЛХ) ДИ, оценки значений векторов числовых параметров, описывающих изображения и их элементы.

Представлены стандартные вычислительные процедуры, используемые в разработанной АБИС:

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

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

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

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

В результате классификации множества ОП по типам узоров с учетом ориентации последних на плоскости изображений формирует-

ся составной квалификационный индекс •/ = {/,„/„,,), где Iи - соответственно индексы типа и ориентации узора.

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

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

На основе комбинированных подходов, использующих специальные модификации градиентного метода и метода оптимизации релаксационного типа, реализуемой при помощи корректирующих центроид с кривизно-подобными весами, разработана грЯдиентно-релаксационная технология формирования градиентного поля латентного ДИ, которая по сравнению с известным способом использования для указанных целей щелевых апертур с оптимальными значениями базовых выборочных статистик обеспечивает более высокую степень адаптивности, большую достоверность поля направлений и, в конечном счете; значительное повышение качества всего процесса КА [1,2].

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

[3].

Формализован и алгоритмизован процесс скелетизации бинарных ДИ на основе операции выделения псевдосвязных множеств, параметризованных по степени их разреженности (связности). Таблич-

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

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

В главе 3 рассмотрена технология идентификации ДИ.

Основополагающими требованиями в процедуре сравнения латентного и отдельного файлового ДИ были в обеспечении:

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

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

- высокой степени достоверности результатов сравнения ОП;

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

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

Перечисленные требования к процедуре сравнения обеспечиваются, прежде всего, реализацией высоконадежного многопараметрического критерия идентичности ДИ, предполагающего сопоставления не только местоположений различных комбинаций ЛХ, но и топологических структур ОП, причем как в локальном, так и в глобальном планах [4]. Осуществляется совместный анализ топологий сопоставляемых отпечатков на трех уровнях: вдоль одноименных радиальных лучей, соединяющих центры с ЛХ, в окрестностях этих лучей и на всех кодируемых областях в целом. Следует особо подчеркнуть, что такая детализация топологического анализа позволяет эффективно ограничивать информативные части сравниваемых ДИ до минимальных областей, обладающих достаточной степенью презентативности. Данное обстоятельство открывает широкие возможности для значительного уменьшения времени выполнения операции сравнения, особенно при хорошем качестве отпечатков. В рамках предложенной

реализации время сравнения латентного и отдельного файлового ДИ на компьютере Pentium 2 (330 МГц) при использовании языка С++ в среднем составляет не более 2 мс.

Разработаны способы ускорения процесса идентификации латентного и файловых ДИ на двух уровнях: аппаратном и программно-алгоритмическом [5-7]. На аппаратном уровне повышение-скорости выполнения процесса идентификации достигается распараллеливанием процедуры сравнения ОП за счет совмещения во времени операций совместного анализа векторов основных и пространственно-топологических кодов латентного и файловых ДИ.

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

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

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

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

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

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

• исследование качественных характеристик АДИС.

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

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

Рассмотрены и сопоставлены между собой возможности различных методов стендовых испытаний качественных характеристик АДИС с использованием специально подготовленных дактилоскопических массивов:

• метода оценки эффективности функционирования АДИС на основе сопоставления индексов совпадений запросных и файловых ДИ с пороговыми значениями;

• КА с различными вариантами использования решающего правила Неймана-Пирсона, минимизирующего вероятность пропуска «родного» отпечатка при ограничении вероятности ложного включения чужого отпечатка в рекомендательный список.

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

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

• Применение типового и (или) модифицированных решающих правил Неймана-Пирсона становится неэффективным при обра-

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

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

Оценка надежности поиска ОП осуществлена для АДИС, в которой комплексно реализованы предложенные в работе: градиентно-релаксационной технология определения поля направления латентного ДИ; метод кодирования ОП, адаптированного по отношению к объему используемого набора базовых ЛХ и количеству пересечений топологическими линиями базовых радиальных лучей; алгоритм сравнения ОП на основе многопараметрического критерия идентичности ДИ.

Вероятность правильной идентификации ОП, полученная на базе данных НИИ специальной техники МВД РФ (г. Москва) из 7х10б ДИ, не менее, 0,82 (доверительный интервал с вероятностью 0,95 составляет,0,74-0,90). Полученная оценка надежности поиска на 10-15% выше результатов для известных систем.

ЗАКЛЮЧЕНИЕ

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

1. Разработана градиентно-релаксационная технология формирования поля направлений для ДИ. Ее главными составляющими являются оригинальный метод предварительной оценки направлений выступов и впадин градиентного типа и адаптивные методы оптимизации градиентного поля ДИ, основанные на анализе гистограмм рас-

пределения достоверностей опорных направлений и использовании корректирующих центроид с кривизноподобными весами [1, 2]. Применяемая оптимизационная процедура реализует быстросходящийся рекурсивный процесс релаксационного типа, адекватно адаптирующийся к геометрии и топологии папиллярных линий. Разработанная технология прошла детальную апробацию в АДИС на базе данных объемом 700 тыс. образцов и показала высокую продуктивность по сравнению с известным способом использования для указанных целей щелевых апертур с оптимальными значениями базовых выборочных статистик.

2. Разработана новая табличная технология параллельной обработки ДИ. Ключевыми компонентами этой технологии являются понятие о псевдосвязных множествах, метод анализа структуры и геометрии данных множеств по их проекциям и совокупностям цепей межэлементных связей, а также метод центроидного сжатия множеств [3].

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

3. Реализованный в разработанной АДИС метод кодирования ОП с адаптивным регулированием базового набора ЛХ и количества учитываемых пересечений топологическими линиями радиальных лучей,- идущих от центра ОП по направлению к ЛХ, позволяет выделять на скелетах ДИ области минимальных размеров, селектирующие наиболее существенные признаки соответствующих индивидуумов и не содержащие источников ложной или чувствительной к искажениям информации [4]. Кроме того, предлагаемая процедура кодирования обеспечивает возможность использования в ходе сравнения ДИ не только основных (минимальных), но и расширенных пространственно-топологических кодов. При этом процесс кодирования является полностью автоматическим.

4. Разработан алгоритм сравнения ДИ, требующий сопоставления пространственно-топологических структур ОП на основе многопараметрического критерия идентичности, использующий адаптивное сужение анализируемых частей ДИ при одновременном сохранении достаточной степени информативности оставшейся анализируемой области ДИ [4]. Разработанная программа сравнения ДИ по кодовым

характеристикам внедрена в Национальную АДИС Республики Беларусь.

Созданный для ускорения общего процесса идентификации латентного ОП в АДИС комплекс методологических и программно-алгоритмических средств, позволяет в рамках трехуровневой каскадной классификации множества всех ОП эффективно организовать направленный поиск в базе данных последовательностей файловых ДИ для процедуры сравнения [7]. Производимая классификация реализует разбиение на классы множества всех ДИ, путем их ранжирования в пределах подмножеств, каждое из которых отвечает своему типу узора, его ориентации на плоскости изображений и интегральной пространственно-топологической характеристике. По предварительным оценкам при осуществляемой классификации среднее число классов каждого нижнего (третьего) уровня составляет не менее 50. В результате идентификация одного латентного ОП в системе на базе ПЭВМ типа Pentium (350 МГц) при суммарном количестве файловых ДИ 250 тысяч осуществляется за время не более 10 с.

5. Предложена тестовая методика оценки качества работы АДИС на основе анализа результатов эксплуатации системы с реальными дактилоскопическими массивами, позволяющая получить статистически достоверную величину надежности АДИС и определить с заданной вероятностью доверительный интервал этой величины [8].

6. В рамках разработанных концепций на базе созданного комплекса методов, алгоритмических и программных средств быстрой и достоверной обработки дактилоскопической информации [2-7] создан находящийся в настоящее время в эксплуатации вариант АДИС, который апробирован на реальной базе данных НИИ специальной техники МВД РФ (г. Москва) из 7x106 ДИ. Вероятность правильной идентификации ОП составила 0,82; при этом доверительный интервал с вероятностью 0,95 составил 0,74-0,90. Полученная оценка надежности поиска на 10-15% выше результатов известных систем. Результаты экспериментальных испытаний созданной АДИС подтверждают высокую эффективность и перспективность разработанных подходов.

Синтезированный комплекс компьютерных средств идентификации ДИ ориентирован на арифметику в целых числах и широкое применение табличного метода вычислений [5,6], как на этапе предварительной обработки, так и на этапе сравнения ОП. Весь предварительный этап обработки (256х256)-точечного латентного ОП, включая кодирование с помощью синтезированного алгоритмического ком-

плекса на ПЭВМ типа Pentium (350 МГц), реализуется не более чем за 1 сек.

СПИСОК РАБОТ ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи

1. Гордей Д.Л., Завгороднев С.М., Зубаха B.C., Коляда A.A., Кремнев В.А., Ревинский В.В., Селянинов М.Ю., Чернявский Ю.А. Проблемы развития теоретико-методологических и алгоритмических основ базовой технологии обработки отпечатков пальца и следов. // Методы, алгоритмы и программное обеспечение гибких информационных технологий для автоматизированных идентификационных систем: Сб. науч. ст.- Мн.: БГУ,- 1999. С. 18-28.

2. Корзюк В.И., Коляда A.A., Ревинский В.В., Селянинов М.Ю., Чернявский Ю.А. Градиентно-релаксационная технология формирования поля направлений для дактилоскопических изображений // Известия HAH Беларуси. Серия ф.-м. Наук.- 2000.- №1.- С. 117-122.

' '3. Корзюк В.И., Коляда A.A., Ревинский В.В., Селянинов М.Ю., -Чернявский Ю.А. Параллельная обработка дактилоскопических изображений в бинарно-векторной упаковке. // Известия HAH Беларуси. Серия физико-математических наук.- 2000.- №2,- С. 117-125.

4. Боков A.C., Коляда A.A., Завгороднев С.М., Зубаха B.C., Ревинский В.В., Чернявский Ю.А. Методы и алгоритмы сравнения дактилоскопических изображений. // Методы, алгоритмы и программное обеспечение гибких информационных технологий для автоматизированных идентификационных систем: Сб. науч. ст.- Мн.: БГУ,- 1999.-С. 91-97.

5. Коляда A.A., Ревинский В.В., Селянинов М.Ю., Завгороднев С.М., Чернявский Ю.А. Метод сверхбыстрого умножения чисел в минимально избыточных модулярных системах счисления. // Современные вопросы оптики, радиационного материаловедения информатики, радиофизики и электроники: Сб. науч. ст.- Мн.: БГУ,-1996,-С. 16-21.

6. Коляда A.A., Ревинский В.В., Селянинов М.Ю., Завгороднев С.М., Чернявский Ю.А. Метод декомпозиции дискретного преобразования Фурье с помощью систем счисления. // Современные вопросы

оптики радиационного материаловедения, информатики, радиофизики и электроники: Сб. науч. ст-. Мн,: БГУ,- 1996.- С. 36-41.

7. Боков A.C., Коляда A.A., Завгороднев С.М., Зубаха B.C., Ре-винский В.В., Чернявский Ю.А. Организация общего процесса идентификации латентного отпечатка. // Методы, алгоритмы и программное обеспечение гибких информационных технологий для автоматизированных идентификационных систем: Сб. науч. ст.- Мн.: БГУ, 1999,-С. 97-104.

Тезисы докладов конференций:

8. Козловский Н.И., Коляда A.A., Ревинский В.В., Селянинов М.Ю., Чернявский Ю.А. О производительности методов обработки дактилоскопических изображений. // Тезисы докладов 8-ой Белорусской математической конференции,- Минск, 2000.-Ч.З.- С. 118.

РЕЗЮМЕ

Чернявский Юрий Александрович

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

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

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

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

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

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

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

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

ABSTRACT

Chernyvski Yuri Alexanderovich

Methods and algorithms for image treatment in automatic dactyloscopic systems.

Keywords-, dactyloscopy, dactyloscopic registration, fingerprint, trace, dactyloscopic map, dactyloscopic image, image treatment, classification analysis, identification of dactyloscopic images, dactyloscopic identification system.

Methods and computer procedures to transform information during the main steps of the classification analysis in automatic dactyloscopic identification systems, which determine identification speed and identification quality characteristics of dactyloscopic images, are developed.

• Gradient relaxation technology to form the field of the protrusions and depressions of the fingerprints is proposed.

• Algorithm for the high-speed parallel treatment of dactyloscopic images is developed, which uses binary vector representation of the information and skeletonization of the binary images basing on the selection procedure of the parametrized according to their rarefication (connectivity) pseudoconnected ensembles.

• Methods to code and form compressed analogs of the dactyloscopic images are proposed, which enable adaptive narrowing and at the same time to conserve sufficient degree of informativity of the analyzed areas of the image.

• Basing on the principle of three-level cascade classification we developed original method for faster search in the database of candidate's dactyloscopic images. Efficient methods and algorithms are proposed for comparison of latent and filed dactyloscopic images, which anticipate implementation of the comparison procedure of the local characteristics as well as image topologies in the framework of the multiple parametric criterion.

The method to evaluate operation quality of the dactyloscopic identification systems is proposed, which in the case of real dactyloscopic images delivers statistically accurate value of the system operation reliability and enables determination of the confidence interval of this value with the required probability.

РЭЗЮМЭ

Чарняусю Юрый Лляксандрав1ч

Метады 1 алгарытмы апрацоую адлюстраванняу у аутаматызаваных дактыласкатчных астэмах

Ключавыя словы: дактыласкатя, дактыласкатчны улж, адбпак пальца, дактылакарта, дактыласкашчныя адлюстраванш, апрацоука адлюстраванняу, клаафжацыйны анал1з, ¡дентыфкацыя дактыласкатчных адлюстраванняу, дактыласкатчная 1дэнтыфкацыйная астэма.

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

- Прапанавана градыентна-рэлаксацыйная тэхналопя фар-м1равання поля напрамкау выступау 1 упадзш на адбгаах папьцау.

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

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

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

Для ацэнк1 якасщ работы дактыласкатчных щэнтыфкацыйных астэм прапанавана методыка, дазваляючая пры працы з рэальным1 дактыласкатчным1 мас1вам1 атрымоуваць стытыстычна дакладную

ве:пчыню падзейнасщ работы слстэм i вызначыць з зададзенай ¡мавернасцю даверальны ¡нтэрвал гэтай вел1чыш.