Содержание к диссертации
Введение
Глава I. Морфологические методы в задачах анализа изображений 20
I. Основы морфологического анализа изображений 20
1 Форма изображения, как элемента линейного пространства функций 20
2 Разбиение изображений на подмножества поля зрения 26
3 Теоремы о проекторах 29
4 Форма изображения, как оператор проектирования.. 33
2. Морфологические методы в задачах выделения идентификации и совмещения 36
1 Задачи идентификации и совмещения 36
2 Задача выделения объекта неизвестной формы 38
3 Частичный морфологический, анализ 44
3. Морфологические методы квантования изображений.. 47
Психофизический критерий верности воспроизведения
Глава II. Морфологические методы анализа папиллярных узоров 58
1. Обнаружение интегральных особых точек... 59
2. Отслеживание регулярной части папиллярных узоров 69
Глава III. Цветные изображения 88
1. Морфологический анализ цветных изображений 88
2. Форма цветного изображения 91
Заключение.. 100
Литература 102
- Форма изображения, как элемента линейного пространства функций
- Задача выделения объекта неизвестной формы
- Отслеживание регулярной части папиллярных узоров
- Морфологический анализ цветных изображений
Введение к работе
Проблема цифровой обработки изображений привлекает внимание в связи с задачами аэрокосмических исследований, работами по созданию роботов и искусственному интелекту, в физике высоких энергий при автоматической обработке фильмовой информации, в биологии и медицине, в связи с задачами анализа биологических структур, классификации хромосом, идентификации патологических клеток, анализа рентгенограмм и термограмм и т.д.
Чаще всего изображение является носителем информации об объекте исследования, которую требуется извлечь и проанализировать, однако в некоторых задачах изображение само является предметом анализа. Огромное количество информации, содержащееся в изображении делает цифровую обработку изображений одним из сложнейших направлений обработки сигналов, требующим мощной вычислительной техники и хорошо развитой периферии. Существуют и иные возможности при обработке и анализе изображений, из которых наиболее перспективные основаны на достижениях когерентной и некогерентной оптики. Для них характерно большое быстродействие, но цифровые системы по сравнению с оптическими обладают большей гибкостью в выполнении алгоритмов нелинейной обработки, итеративных процедур и решающих алгоритмов.
Обработке изображений предшествует процесс формирования изображений фотографический, электронно-оптический, типографический и т.п.
Наиболее распространенным и совершенным является фотографический способ. Регистрация изображения на фотографической пленке основана на светочувствительных свойствах галогенидов сере бра. При освещении кристаллы галогенидов серебра изменяют свое состояние и образуют скрытое изображение. Под действием веществ, называемых проявителями, выделяется свободное метал- лическое серебро, Хатер и Дриффельд [3] нашли эксперименталь-но, что масса выделившегося серебра пропорциональна логарифму полной экспозиции '= J- , где I - интенсивность света, І - время экспозиции. Пропорциональность нарушается при большой экспозиции, когда при проявлении выделяется все серебро, имеющееся в светочувствительном слое (наступает насыщение), и при слабой экспозиции, когда независимо от величины экспозиции выделяется некоторое количество серебра образующее вуаль. Эти зависимости описываются кривой JD - JP(&2fJ, где J} - оптическая плотность, определяемая равенством >- у (li/lA* в котором, її - интенсивность света, падающего на проявленную пленку, а 1л - интенсивность прошедшего сквозь нее света; всегда Ii> I& . Типичная кривая, называемая характеристической, показана на рис.1
ч
Рис.1
Предположим, что экспозиция соответствует линейному участку (d) ft) характеристической кривой. Тогда интенсивность света, прошедшего сквозь нее, согласно закону Бутера-Ламберта [2] , равна где к - коэффициент поглощения, Же - масса серебра на единицу площади, выделившаяся при проявлении. При соответствующем Определении І И УПо 9 > = \C'\Yla и таким образом при подстановке в (I) на линейном участке I&~li e*p(~V) , Т>~ f&jf ~>с , где у -наклон линейного участка. Если интенсивность света за время экспозиции была постоянной, то F^lo't , где Т0 - интенсивность света создающего изображение. Положим і - , тогда получим ІГ- h ^Ур Ы ^ +&*) * ^ (То) г
Как видно, интенсивность света, прошедшего через пленку, является нелинейным преобразованием исходного распределения интенсивности вида 1л - Р (Tt>) для каждой точки на изображении.
Из уравнения (2) следует, что фотопленка является нелинейным средством записи распределения интенсивности света. Фотографический шум обусловлен случайным характером образования зерен серебра. Во-первых, размер и форма зерен случайны. Во-вторых, одинаковые зерна не обязательно обусловлены одинаковой экспозицией или одинаковой степенью проявления. Такая случайное процесса образования зерен вызывает случайные флуктуации локальной плотности серебра - это явление называется шумом зернистости. Флуктуации плотности относительно ее среднего значения, связанные с зернистостью, могут быть приближенно описаны случайной величиной с гауссовым распределением [4] Флуктуации представляют собой очень высокочастотный случайный процесс или случайный процесс типа "белый шум". Важно отметить, что шум зернистости аддитивен относительно плотности , а не интенсивности.
Предложено много математических моделей зернистой структуры. Рассмотрим одну из них, предложенную Писенбоно [б] .
В рамках этой модели предполагается: а) зерна круглые и их центры расположены на -плоскости случайным образом независи- мо друг от друга; б) центры зерен распределены по закону Пуассона, т.е. вероятность того, что на площади ^ имеется %* зерен, определяется выражением где 3\. () плотность заполнения площади зернами, а размеры зерен подчиняются закону распределения вида
Данная модель позволяет получить передаточную функцию сканирующей системы где р - радиус сканирующей диафрагмы, а также корреляционную функцию Ufl > O^iJjf у & - радиус зерна и~Іо *?/ > F( «// ~ свеРтка ДВУХ аппертур, которая является основной характеристикой зернистости.
Модель хорошо согласуется с данными для реальных зернистых структур, имеющимися в литературе [1,3] .
Другим примером регистрации изображений являются видикон-ные камеры, диссекторы и аналогичные устройства, используемые в тех случаях, когда требуется визуализация в реальном времени, быстрый произвольный доступ в любую точку изображения или обработка изображений, наблюдаемых через увеличительные системы. Эти устройства используются в таких областях, как теленаблюдение объектов, недоступных или опасных для непосредственных наблюдений, обследование физических объектов в реальном масштабе времени, подсчет частиц и т.п.
Следующий способ регистрации использует электронно-лучевые трубки. При дискретизации изображений, а также при их записи, устройства этого типа используются для освещения выбранных точек изображения, а фоточувствительный детектор измеряет количество света, прошедшее через образец. При записи электронный луч модулируется по интенсивности и используется для экспонирования пленки или другого светочувствительного материала.
Приборы этого типа ипаяльно подходят для считывания знаков в оптических устройствах распознавания знаков, для вывода изображений из ЭВМ на микрофильм, т.е. там, где можно использовать преимущества произвольного доступа к изображению, но не требуется высокая геометрическая точность и хорошее разрешение по плоскости.
Электромеханические устройства имеют высокую скорость сканирования, широкий динамический диапазон плотностей, большую разрешающую способность и высокую позиционную точность, но они не обеспечивают быстрого произвольного доступа, какой позволяют получить электронные устройства.
Реальная необходимость в применении автоматизированных систем кодирования отпечатков пальцев способствовала появлению большого количества работ в этой области. Только наиболее интересные из этих работ будут рассмотрены ниже.
По данным работы [19] идентификация отпечатка производится по координатам 50 его мелких особенностей, являющихся кодом. Для обеспечения достоверности решения 0.98, при вероятности ошибочного вычисления координаты одной мелкой особенности Р=0.03, идентификация требует анализа I.28-j-q7 адресов при 2 ошибочных координатах. Иначе говоря, количество отпечатков, подлежащих дальнейшей проверке с целью принятия.решения, возрастает не порядок при увеличении на I числа ошибочно указанных особенностей. С учетом этого факта машинная идентификация по совокупности мелких особенностей требует, как правило, 50-100 таких особенностей на отпечаток. При этом, если для кодирования характеристик одной мелкой особенности использовать всего 20 бит информации, то для одного отпечатка окажется необходимым хранение 1000-2000 бит информации.
Естественно, что хранение и обработка подобных количеств информации потребует значительных объемов памяти ЭВМ, и значительных затрат машинного времени на вычисление и сопоставление координат мелких особенностей дактилокарты.
В работе /"20] в качестве кода предложены параметры углов наклона папиллярных линий на различных фрагментах отпечатка. Описание отпечатка при этом производится посредством наложения квадратной сетки (18x18, 32x32), вычисления усредненных по отдельным фрагментам сетки углов наклона и сведения их в таблицу. Такая таблица является в конечном счете кодом отпечатка.
Кодирование отпечатков до донной методике позволяет сократить объем информации до 1000 бит.
Однако при этом существенно падает разрешающая способность кодирования, что ограничивает возможность работы с дактилотеками большого объема.
Е.Марам [21], ВДОрват, И.Холеман и С.Леманд [22] обратили внимание на возможность использования оптической техники для классификации отпечатков пальцев. Марам предложил поперечную корреляцию отпечатков, которая осуществляется с применением прецизионных фильтров. Это позволяет выявить все детали отпечатков пальцев, однако, требуется слишком много прецизионных фильтров, что замедляет обработку, и классификация, основанная только на этих отпечатках, недостаточно совершенна. В работе [22] обсуждается классификация с применением голографии. В этом случае, кроме длительности процесса и необходимости применения большого числа фильтров, необходима строжайшая тщательность. Необходимая тщательность проведения голо.^ графии такова, что осуществление классификации становится практически невозможной.
Хотя применение оптической техники имеет преимущества перед цифровыми вычислительными машинами по быстродействию, однако, необходимость приготовления прозрачных образцов, возникновение обратного изображения и различие в размерах является основным препятствием для внедрения такого типа классификации.
Фирма mo donebl duglas изготовила опытный образец для идентификации отпечатков пальцев с использованием средств когерентной оптики. Сравнение папиллярных узоров выполняется по известному принципу корреляционного пятна. Устройство было опробовано на массиве 10 тыс.дактилокарт [23].
Авторами сделан вывод о нецелесообразности продолжения работ в этом направлении в связи с крайне жесткими требованиями к аппарату- - II - ре (допуски оптических параметров, параметров фотоматериалов и т.д.) и значительной трудоемкостью.
Построение информативного описывающего кода не слишком большого объема было предложено посредством использования совокупности данных о координатах ядра, дельты, мелких особенностей и угловых направлений папиллярных линий и рассмотрено в работах [26,27,28].
Б целях повышения инвариантности кодирования к сдвигам и поворотам в системе автоматической классификации отпечатков пальцев FINGERPRINT АШЮМ. CLASS. МЄЛКИЄ ОСОбеННОСТИ ЗЭДаЮТСЯ ПОСрвД- ством указания гребневого счета линий между данной мелкой особенностью и каждой из остальных. При этом таблица кодирования отпечатка представляет собой матрицу, каждый элемент которой есть значение гребневого счета между соответствующими мелкими особенностями. Предполагается использование координат ядра и дельты, к которым производится привязка системы координат.
Прошла опытную эксплуатацию экспериментальная система "finder " фирмы calspan [24J . Это наиболее перспективный из имеющихся на сегодня образцов аппаратуры для автоматизированной обработки пальцевых отпечатков. В состав системы входят ЭВМ IBM 370/45, специализированное устройство оптико-электронного считывания, устройства видеоконтроля и корректировки изображений, специализированный предпроцессор на базе мини ЭВМ типа pdp -9 для предварительной обработки узоров перед их вводом в ЭВМ. В системе используется принцип кодирования папиллярных узоров по мелким особенностям. По составу аппаратуры, совокупности решаемых задач и рабочим характеристикам система " finder " является наиболее перспективной.
Фирма ARGONNE NATIONEL LABORATORY Провела ОПЫТНУЮ ЭКСПЛуа- тацию системы "alice", использующей модифицированную классификационную систему Гальтона-Генри [25J . Имеются сведения о появлении опытных образцов систем в Англии [гВ^Японии [29І , Франции,
Швеции, ФРГ и других странах. Отмечаются весьма большие затраты машинного времени на идентификацию отпечатков. Так в системе " finder " обработка информации об одном пальце занимала 1.75 часа на ЭВМ IBM 360/65 при I млн. опер, в сек. Это обстоятельство заставило прибегнуть к построению специального предпроцессора, который выполняет тот же объем вычислений за 0.5 сек.
Выше перечисленные методы кодирования папиллярных узоров являются основными. Синтаксический метод для классификации образцов отпечатков пальцев рассмотрен в работе [зо] .
Образцы отпечатков пальцев заключаются в прямоугольники для выделения отличительных признаков. Для описания отпечатков пальцев используется бесконтекстный язык. Распознавание отпечатков пальцев завершается с помощью последовательного грамматического разбора для уменьшения машинного времени. Применение некоторых отличительных черт бесконтекстного стохастического языка предназначено для дальнейшей классификации отпечатков пальцев.
Обычный древовидный язык использован для классификации образцов отпечатков пальцев и древовидные типы автоматов применены для распознавания закодированных отпечатков. Для определения структурных конфигураций отпечатков пальцев, не подвергавшихся кодированию, разработана обобщенная грамматическая система. Эта система основана на применении эталонов, относящихся к различным субструктурам, и использовании соответствующей матрицы. При расшифровке очень сложных структур работу выполняет оператор.
В работе Г 311 предложена так называемая топологическая кодировка, построенная с использованием принципов классической системы Баттла . Идентификационный код представляет собой упорядоченный набор символов типа "Т" ( тор ), " ь " (left), "R" ( rigt ),"В" (bottom), n0" (zerro) и т.д. Эти символы используются для обозначения верхних, нижних, крайних левых и крайних правых точек папил- - ІЗ - лярных линий, называемых в совокупности "узлами", рис.2. С помощью такой символики узоры описываются топологическими кодовыми словами,после чего идет описание. Например, LOOP RIGT T(R) T(R) T(IR) T(LI(R)) RI(R) Т(ЪШО)
Означает правую петлю,содержащую перечисленные мелкие особенности.
В работе [зі] рассмотрен метод топологического кодирования использующий описание отпечатка в виде графа рис. 3.
Сложность данных систем кодирования,неоднозначность описаний, затрудняют их реализацию на T(R) T(LO) T(LR) T(b(LR)R(LR)) T(L(LI(L)LI)R)
Рис. 2 Кодирование отпечатков с помощью топологических кодовых слов
А В С Д E
А 0 10 0 0
В I 0 I I 0
С 0 I 0 I 0
Д 0 I I 0 I
Е 0 0 0 0 0 матрица
Рис. 3 Топологическое:кодирование с помощью матриц и инцидентность - вершина
Целью работы является развитие методов морфологического анализа изображений и создание математического обеспечения для решения задач: а) идентификации и выделения объектов неизвестной формы; б) автоматического кодирования папиллярных узоров, включаю щих обнаружение интегральных особых точек, отслешшаїше регу лярной части и определение типа интегральных особых точек; в) частичного морфологического анализа, когда речь идет о морфологии не всего изображения, а некоторой его части, пред ставляющей интерес; г) синтеза цветных изображений и удаления теней на цвет- ных снимках; д) изучения психофизического критерия точности аппроксимации изображения, используемого в том случае, когда качество аппроксимации оценивается зрительной системой человека.
Первая глава состоит из 3-х параграфов и содержит обзор и развитие методов морфологического анализа изображения. Во многих задачах анализа изображения предает исследования составляют не дельные изображения, а определенным образом построенные классы изображений. В частности, в:многочисленных прикладных задачах, в которых основным является морфологический аспект, предметом анализа являются классы изображений, получаемых при иных вариациях условий регистрации, таких, например, как условия освещения, величина экспозиции и т.п. В таких задачах основным является понятие формы изображения.
В первом параграфе обсуждается понятие формы изображения на подмножестве поля зрения и приведены необходимые сведения об операторах проектирования.
Во втором параграфе рассмотрены методы морфологического анализа в задачах идентификации сцен по их изображениям. Здесь же рассмотрены задачи совмещения изображений, искаженных при регистрации и задачи выделения объектов на фоне изображения с известной формой.
При идентификации сцен по их изображениям в ряде случаев нет оснований считать сцены полностью идентичными. Речь идет о тех или иных объектах, которые могут присутствовать на одной из сцен и отсутствовать на другой. Если такие объекты представляют интерес, то возникает задача выделения объектов, обуславливающих различия сцен, причем предъявляемые изображения сцен искажены различными условиями регистрации.
Реализация схемы выделения отличии требует достаточно точного совмещения, по сравнению с размерами минимальной детали изображения, поскольку ошибка в совмещении проявляется как дополнительный дефект.
В разделе ? развита теория частичного морфологического анализа.
Среди различных задач анализа изображений задачи морфологического анализа редко встречаются в чистом виде. В большинстве задач требуется лишь частичный морфологический анализ. По существу это обстоятельство отражено в определении формы на подмножестве поля зрения, в котором речь идет о морфологии не всего изображения, а лишь некоторой его части, представляющей интерес. Остальная часть изображения может вообще не иметь отношения к делу и в большиетве своем считается произвольной. Например, задачи навигации, наведения, дефектоскопии интегральных схем и т.п.
Хорошо известно, что представления о форме объекта тесно связано с наблюдаемыми скачками яркости на границах, причем часто сама граница рассматривается как множество точек резкого изменения яркости. Во многих задачах объект считается заданным, если-задана его граница. Будем называть данные минимальными морфологическими данными. Последние тесно связаны с рассмотренными в I разбиениями поля зрения.
Однако, в ряде случаев полученные ранее результаты не позволяют решать ряда задач совмещения изображений, в которых в конечном счете, требуется совмещение границ объектов, для этого дается определение Є - формы границы.
В 3 рассмотрен морфологический метод квантования изображения и связанный с ним психофизический критерий верности вое- произведения. Прикладные методы анализа изображений в основном ориентированы на дискретное представление изображений. Известно решение задач дискретного приближения изображений кусочно-постоянными функциями при заданном числе уровне квантования, заданном разбиении поля зрения и заданном числе множеств искомого разбиения. Но каждая задача имеет ограниченный интерес в связи с психофизическими оценками точности аппроксимации, когда окончательная оценка качества дается человеком.
Простейшее предположение может состоять в том, что порог обнаружения погрешностей квантования при психофизической оценке контролируется законом сохранения вида /дAX/S/^ Є » где АЛ - характерный линейный размер, на протяжении которого яркость меняется на 4 (Пайпер).
Для реальных изображений не может быть указана форма функ-циональной зависимости, поэтому разработан алгоритмический метод, в результате которого мы получаем последовательность точек
Сі <*Сл 4 Ct**C^квантования (оптической плотности) и последовательность соответствующих множеств (дискретизации) JjLK I
В параграфе рассмотрен ассимптотический закон равноточного квантования оптического клина.
Вторая глава, состоящая из двух параграфов, посвящена морфологическим методам анализа папиллярных узоров.
Актуальность "задачи автоматического анализа папиллярных узоров определяется прежде всего проблемой идентификации и верификации личности по отпечаткам пальцев, кроме того, результаты последних исследований показывают, что отпечатки пальцев могут служить основой диагностики состояния точности и, в частности, таких патологий, как шизофрения, лейкемия, монголизм и т.п.
В последнее время серьезно изучаются генетические причины, связывающие рисунок кожных борозд с различными хромосомными нарушениями. С этими фактами связан еще один антропологический аспект задачи автоматического анализа папиллярного узора. Хорошо известная система классификации папиллярных узоров, предложенная Ф.Гальтоном -и модифицированная Е.Генри, характеризует общее топологические свойства узора и расположения характерных особых точек. Согласно этой системе код отпечатка содержит положение особых точек узора - "ядра" и "дельты", тип "ядра" петлевой, завитковий, дуговой и параметры их относительного расположения-гребневой счет.
В I рассмотрена задача обнаружения узоров типа "дельта" и "петля" и определения их параметров, дано определение формы папиллярного узора.
Для применения полученных результатов по обнаружению узоров данного типа и определения их параметров на практике необходим надежный алгоритм, позволяющий быстро определять окрестности особенностей.
В 2 рассмотрен морфологический метод отслеживания регулярной части папиллярных узоров. Окрестности особенностей определяются как та часть узора, которая не может быть отслежена оператором. Оператор Д , отслеживающий регулярную часть, яеляєтся оператором ортогонального проектирования.
Доказано, что' оператор Л. будет оператором наилучшего приближения для регулярной части папиллярного узора. Если, вычесть из изображения отпечатка его наилучшую аппроксимацию, получим мелкие особенности. Мелкими особенностями могут быть разрывы, раздвоения папиллярных линий и т.п. Оператор устроен так, что любой участок линии, содержащий мелкую особенность, он наилуч- - T9 - шим образом приближает участком линии без особенности. Там, где особенности нет, его приближение совпадает с приближением линии.
Разработанные методы и алгоритмы применены для решения задачи выделения окрестности особенностей типа "дельта" и "ядро" на реальных отпечатках.
Третья глава состоит из двух параграфов, где рассматриваются морфологические метода анализа цветных изображений. Два обстоятельства указывают на необходимость развития морфологических методов анализа цветных изображений.
Во-первых, в задаче выделения объекта последний, как правило, прежде всего цветом отличается'от фона. Во-вторых, характе-ризация формы в терминах цвета позволяет практически устранить эффект теней и влияние неопределенности в распределении интенсивности освещения.
В 1-м рассматриваются некоторые аспекты теории цвета и дается определение формы цветного изображения.
В 2 рассматриваются примеры по совмещению многозональных снимков и удалению теней на цветных изображениях.
Разработанные методы алгоритмов эффективны при анализе и синтезе цветных изображений.
Форма изображения, как элемента линейного пространства функций
Первая глава состоит из 3-х параграфов и содержит обзор и развитие методов морфологического анализа изображения. Во многих задачах анализа изображения предает исследования составляют не дельные изображения, а определенным образом построенные классы изображений. В частности, в:многочисленных прикладных задачах, в которых основным является морфологический аспект, предметом анализа являются классы изображений, получаемых при иных вариациях условий регистрации, таких, например, как условия освещения, величина экспозиции и т.п. В таких задачах основным является понятие формы изображения.
В первом параграфе обсуждается понятие формы изображения на подмножестве поля зрения и приведены необходимые сведения об операторах проектирования.
Во втором параграфе рассмотрены методы морфологического анализа в задачах идентификации сцен по их изображениям. Здесь же рассмотрены задачи совмещения изображений, искаженных при регистрации и задачи выделения объектов на фоне изображения с известной формой.
При идентификации сцен по их изображениям в ряде случаев нет оснований считать сцены полностью идентичными. Речь идет о тех или иных объектах, которые могут присутствовать на одной из сцен и отсутствовать на другой. Если такие объекты представляют интерес, то возникает задача выделения объектов, обуславливающих различия сцен, причем предъявляемые изображения сцен искажены различными условиями регистрации.
Реализация схемы выделения отличии требует достаточно точного совмещения, по сравнению с размерами минимальной детали изображения, поскольку ошибка в совмещении проявляется как дополнительный дефект.
Среди различных задач анализа изображений задачи морфологического анализа редко встречаются в чистом виде. В большинстве задач требуется лишь частичный морфологический анализ. По существу это обстоятельство отражено в определении формы на подмножестве поля зрения, в котором речь идет о морфологии не всего изображения, а лишь некоторой его части, представляющей интерес. Остальная часть изображения может вообще не иметь отношения к делу и в большиетве своем считается произвольной. Например, задачи навигации, наведения, дефектоскопии интегральных схем и т.п.
Хорошо известно, что представления о форме объекта тесно связано с наблюдаемыми скачками яркости на границах, причем часто сама граница рассматривается как множество точек резкого изменения яркости. Во многих задачах объект считается заданным, если-задана его граница. Будем называть данные минимальными морфологическими данными. Последние тесно связаны с рассмотренными в I разбиениями поля зрения.
Однако, в ряде случаев полученные ранее результаты не позволяют решать ряда задач совмещения изображений, в которых в конечном счете, требуется совмещение границ объектов, для этого дается определение Є - формы границы.
В 3 рассмотрен морфологический метод квантования изображения и связанный с ним психофизический критерий верности воспроизведения. Прикладные методы анализа изображений в основном ориентированы на дискретное представление изображений. Известно решение задач дискретного приближения изображений кусочно-постоянными функциями при заданном числе уровне квантования, заданном разбиении поля зрения и заданном числе множеств искомого разбиения. Но каждая задача имеет ограниченный интерес в связи с психофизическими оценками точности аппроксимации, когда окончательная оценка качества дается человеком.
Простейшее предположение может состоять в том, что порог обнаружения погрешностей квантования при психофизической оценке контролируется законом сохранения вида /дAX/S/ Є » где АЛ - характерный линейный размер, на протяжении которого яркость меняется на 4 (Пайпер).
Для реальных изображений не может быть указана форма функ-циональной зависимости, поэтому разработан алгоритмический метод, в результате которого мы получаем последовательность точекквантования (оптической плотности) и последовательность соответствующих множеств (дискретизации) JjLK I
В параграфе рассмотрен ассимптотический закон равноточного квантования оптического клина. Вторая глава, состоящая из двух параграфов, посвящена морфологическим методам анализа папиллярных узоров.
Актуальность "задачи автоматического анализа папиллярных узоров определяется прежде всего проблемой идентификации и верификации личности по отпечаткам пальцев, кроме того, результаты последних исследований показывают, что отпечатки пальцев могут служить основой диагностики состояния точности и, в частности, таких патологий, как шизофрения, лейкемия, монголизм и т.п.
В последнее время серьезно изучаются генетические причины, связывающие рисунок кожных борозд с различными хромосомными нарушениями. С этими фактами связан еще один антропологический аспект задачи автоматического анализа папиллярного узора. Хорошо известная система классификации папиллярных узоров, предложенная Ф.Гальтоном -и модифицированная Е.Генри, характеризует общее топологические свойства узора и расположения характерных особых точек. Согласно этой системе код отпечатка содержит положение особых точек узора - "ядра" и "дельты", тип "ядра" петлевой, завитковий, дуговой и параметры их относительного расположения-гребневой счет. В I рассмотрена задача обнаружения узоров типа "дельта" и "петля" и определения их параметров, дано определение формы папиллярного узора.
Задача выделения объекта неизвестной формы
Хорошо известно, что рисунок отпечатков пальцев однозначно определяет личность человека, настолько он уникален и стабилен на протяжении всей жизни. Однако реальная возможность установления личности по отпечаткам пальцев основана на том, что изменчивость рисунка отпечатка не безгранична, и каждый отпечаток в целом может быть охарактеризован в терминах несколько стандартных типов узоров. Актуальность задачи автоматического анализа папиллярных узоров определяется прежде всего проблемой идентификации и верификации личности по отпечаткам пальцев.
Результаты по:следних исследований показывают, что отпечатки пальцев могут служить основой диагностики состояния личности, и в частности, таких патологий как шизофрения, монголизм и т.д. Одна из таких наследственных форм олигофрении, связанная с аномалией набора хромосом и известная как болезнь Дауна,ди-агностицируется по форме борозд на ладонях 16 J В последнее время серьёзно изучаются генетические причины, связывающие рисунок кожных борозд с различными хромосомными нарушениями I 17 1 . С этими фактами связан ещё один, антропологический,аспект задачи автоматического анализа папиллярного узора.
Возможность установления личности по отпечаткам пальцев.основана на том, что изменчивость рисунка отпечатка пальцев не безгранична и каждый отпечаток в целом может быть охарактеризован в терминах нескольких стандартных типов узоров. На этой основе создана система классификации Гальтона-Генри 18 J . Эта система ,использует две так называемые интегральные особенности узоровуоб-разуемые общим потоком папиллярных линий: петлю и дельту. Вершиной петли является точка, вокруг которой поток линий меняет направление условного движения на противоположное. Дельта образуется в области касания трех потоков. На основе взаимного положения особенностей составляется так называемая формула классификации. Недостатком данной системы классификации является неравномерность заполения картотеки по классам.
Рассмотрим морфологический метод распознавания отпечатков пальцев. Для понимания задачи остановимся на способах регистрации отпечатков.
Как известно, при образовании отпечатка невозможно жестко контролировать все факторы, определяющие изменение узора. Понятно, что результат будет существенно зависеть от силы давления пальца, от возможного проскальзования, типа краски и т.п.Всли за этим следует процесс фотографического копирования, то возникают дополнительные искажения в передаче степени почернения. Следовательно,задачу идентификации отпечатков нельзя понимать как задачу идентификации узоров. Одному и тому же пальцу могут соответствовать различные изображения узора, даже в том случае, когда условия получения отпечатка можно считать одинаковыми. Если принять во внимание, что решать задачу идентификации приходится и для отпечатков, оставленных на различных предметах, то решение оказывается не однозначным. Кроме того, существует проблема совмещения изображений относительно сдвигов и поворота. Существуют отпечатки отличающиеся, только мелкими особенностями, т.е. прерыванием или раздвоением линий,пунктирами и т.п. которые являются единственными отличиями, тогда в задаче идентификации возникает подзадача выделения на изображении этих особенностей, обуславливающих различия.
Таким образом, задачу анализа отпечатков пальцев можно разбить на несколько подзадач: 1. Отслеживание параллельных линий, содержащихся во всех отпечатках, т.е. выделение регулярных частей узора, что позволяет локализовать интегральные особые точки "ядро" и "дельту". 2. Определение типа интегральных особых точек и их координат. 3. Определение координат мелких особенностей. Для формализации и решения перечисленных задач в диссертации развиты методы морфологического анализа, использующие харак-теризацию изображений в терминах, инвариантных относительно некоторых условий регистрации. Для распознования важно разбиение плоскости на области с по стоянными яркостями, а геометрия областей интуитивно осознается как форма узора (глава 1, I). Если произвести разбиение интегральной особой точки типа "петля", то получим рис.4. Как видно из рис.2 яркости на множествах подчиняются некоторому закону периодичности с э-сг Сз с . В общем случае можно за форму изображения принять геометрию разбиения и плюс ещё условия яркости. Далее получим более содержательное определение формы, метрические характеристики которой будут рассмотрены в тексте.
Отслеживание регулярной части папиллярных узоров
Граници и размеры множествен А были сделаны переменными, с условием Atffli-S. Границы множества At могли перемещаться относительно центра оператора 0 вправо и влево, размеры множества At могли принимать значения IіLi-k \
Движение оператора отслеживания по отпечатку осуществлялось следующим образом: первоначально грубо определялось направление движения оператоа, для чего проводился дискретный пововот поля ярения Х- на угол Vf с шагом 17 /\%,, По максимуму сигнала, снимаемого с оператора ( т.е. проводился подсчёт Функционалов вида ( 13 ) и ( 17 ) определялось начальное направление движения.
Относительно этого направления осуществлялся поиск более точного направления линии. Для этого 5 раз осуществлялся поворот на угол А ь = .1. и по максимуму сигнала определялось направление. Далее в этом направлении оператор делал шаг нак- = 5 клеток и уже трижды определял направление. По максимуму сигнала, при условии, что он превосходит пороговый уровень, определяется напревление, оператор делает шаг на "R = 7.5. клеток и просто сравнивает новый сигнал с порогом. Если сигнал ( порог ), то оператор двигается дальше, если $& , то оператор возвращается на шаг назад, шаг меняется на V. - 5 клеток, и опять поворот поля зрения и т.д.
Блок - схема программы осуществляющей отслеживание и "выметание" регулярной части узора приведена на стр.87 . Хотя задача обнаружения изображения ставится как задача проверки гипотезы И против альтернативы 1С , где Н -однородный фон, а в задаче отслеживания линий" приходится выбирать между правильной и неправильной ориентацией оператора отслеживания, эксперимент показывает, что оператор реагирует на линии, перпендикулярные его ориентации, как на однородный фон с шумом. Сигнал оператора, подсчитываемый при помощи функционала ( 13 ), когда его ориентация перпендикулярна направлению линии был равен 0.02 0. 05. Значение порога для ( 17 ) вычис-ленное по таблицам распределения сгЛ Сб при о( «= 0.01 равно 0.037. Значение порога $ 0 для функционала ( 13 ) и ( 17 ) определялось экспериментально с помощью подсчёта функционалов на " нерегулярных " частях отпечатка. Эксперимент провдился с различными пороговыми значениями. Лучшие значения полусились для порога SP- D1 + 0JS для ( 13 ) $,0= QU С& для ( 17 ) Заметим, что значение &0 при котором верно определяется направление линий и выделяются особенности, значительно выше сигнала, подсчитываемого в направлении, перпендикулярном ориентации линии. Исследовалось поведение оператора в зависимости от характеристик множеств Аі и Ai 1. Границы множества hi подвижны, размеры ( площадь ) множества Ai и, соответственно, At могут изменяться. В этом случае оператор хорошо реагирует на значительные изменения " регулярной формы " линии, т.е. на "дельту", "петлю", но почти всегда проскакивает мелкие особенности. 2. Границы множества Л подвижны, но размеры Ai и hi постоянны. Оператор такой конфигурации достаточно хорошо обнаруживает мелкие особенности. При пороге & O.I3 оператор с подсчётом функционала ( 13 ) не пропустил ни одного раздвоения или достаточного сужения или расширения линий. 3. Границы множества At неподвижны. В этом случае для точного отслеживания линий необходимо выставлять порого с большой точностью,нежели в случаях I и 2. Оператор такой конфи гурации расчитан на отслеживание линий, толщина которых прак тически неизменена, а направление меняется очень медленно, ши рина между линиями тоже практически постоянна. Для отпечатка эти требования, естественно не выполняются. Даже незначительное снижение порогового уровня может привести к неверному отсле живанию линий, а в результате к неверному выделению особен ностей, чего в случаях I и 2 не происходит. После того, ка оператор отследил заданные линии, запоминаются все те точки отпечатка, где он был. Так как после обнаружения оператором начала " дельты" или " петли " он останавливается и переходит на другую линию, то в памяти остаются координаты центра оператора и угол поворота в тех точках, где отслеживание произошло. Затем отслеженные части линий стираются и, таким образом, остается только "нерегулярная часть" отпечатка. По этому принципу "выметания" регулярной части узора можно выделять любые другие особенности узоров, т.е. анализировать узор любого типа. Задачи точного обнаружения особенностей типа " петли ", " дельты " и т.п. являются самостоятельными и реализуются специальным морфологическим оператором, настроенным на форму " дельты " и т.п.
Сочетание этих двух задач приводит к автоматизированной обработке отпечатков, позволяющей безошибочно определять параметры классификации папиллярных узоров системы Гальтона-Генри.
Морфологический анализ цветных изображений
Е.Марам [21], ВДОрват, И.Холеман и С.Леманд [22] обратили внимание на возможность использования оптической техники для классификации отпечатков пальцев. Марам предложил поперечную корреляцию отпечатков, которая осуществляется с применением прецизионных фильтров. Это позволяет выявить все детали отпечатков пальцев, однако, требуется слишком много прецизионных фильтров, что замедляет обработку, и классификация, основанная только на этих отпечатках, недостаточно совершенна. В работе [22] обсуждается классификация с применением голографии. В этом случае, кроме длительности процесса и необходимости применения большого числа фильтров, необходима строжайшая тщательность. Необходимая тщательность проведения голо. графии такова, что осуществление классификации становится практически невозможной.
Хотя применение оптической техники имеет преимущества перед цифровыми вычислительными машинами по быстродействию, однако, необходимость приготовления прозрачных образцов, возникновение обратного изображения и различие в размерах является основным препятствием для внедрения такого типа классификации.
Фирма MO DONEBL DUGLAS изготовила опытный образец для идентификации отпечатков пальцев с использованием средств когерентной оптики. Сравнение папиллярных узоров выполняется по известному принципу корреляционного пятна. Устройство было опробовано на массиве 10 тыс.дактилокарт [23].
Авторами сделан вывод о нецелесообразности продолжения работ в этом направлении в связи с крайне жесткими требованиями к аппаратуре (допуски оптических параметров, параметров фотоматериалов и т.д.) и значительной трудоемкостью. Построение информативного описывающего кода не слишком большого объема было предложено посредством использования совокупности данных о координатах ядра, дельты, мелких особенностей и угловых направлений папиллярных линий и рассмотрено в работах [26,27,28].
Б целях повышения инвариантности кодирования к сдвигам и поворотам в системе автоматической классификации отпечатков пальцев fingerprint ашюм. class. мєлкиє особенности зэдаются посрвд ством указания гребневого счета линий между данной мелкой особенностью и каждой из остальных. При этом таблица кодирования отпечатка представляет собой матрицу, каждый элемент которой есть значение гребневого счета между соответствующими мелкими особенностями. Предполагается использование координат ядра и дельты, к которым производится привязка системы координат.
Прошла опытную эксплуатацию экспериментальная система "FINDER " фирмы CALSPAN [24J . Это наиболее перспективный из имеющихся на сегодня образцов аппаратуры для автоматизированной обработки пальцевых отпечатков. В состав системы входят ЭВМ IBM 370/45, специализированное устройство оптико-электронного считывания, устройства видеоконтроля и корректировки изображений, специализированный предпроцессор на базе мини ЭВМ типа PDP -9 для предварительной обработки узоров перед их вводом в ЭВМ. В системе используется принцип кодирования папиллярных узоров по мелким особенностям. По составу аппаратуры, совокупности решаемых задач и рабочим характеристикам система " FINDER " является наиболее перспективной.
Фирма ARGONNE NATIONEL LABORATORY Провела ОПЫТНУЮ ЭКСПЛуа тацию системы "ALICE", использующей модифицированную классификационную систему Гальтона-Генри [25J . Имеются сведения о появлении опытных образцов систем в Англии [гВ Японии [29І , Франции, Швеции, ФРГ и других странах. Отмечаются весьма большие затраты машинного времени на идентификацию отпечатков. Так в системе " FINDER " обработка информации об одном пальце занимала 1.75 часа на ЭВМ IBM 360/65 при I млн. опер, в сек. Это обстоятельство заставило прибегнуть к построению специального предпроцессора, который выполняет тот же объем вычислений за 0.5 сек.
Выше перечисленные методы кодирования папиллярных узоров являются основными. Синтаксический метод для классификации образцов отпечатков пальцев рассмотрен в работе [зо] .
Образцы отпечатков пальцев заключаются в прямоугольники для выделения отличительных признаков. Для описания отпечатков пальцев используется бесконтекстный язык. Распознавание отпечатков пальцев завершается с помощью последовательного грамматического разбора для уменьшения машинного времени. Применение некоторых отличительных черт бесконтекстного стохастического языка предназначено для дальнейшей классификации отпечатков пальцев.
Обычный древовидный язык использован для классификации образцов отпечатков пальцев и древовидные типы автоматов применены для распознавания закодированных отпечатков. Для определения структурных конфигураций отпечатков пальцев, не подвергавшихся кодированию, разработана обобщенная грамматическая система. Эта система основана на применении эталонов, относящихся к различным субструктурам, и использовании соответствующей матрицы. При расшифровке очень сложных структур работу выполняет оператор.
В работе Г 311 предложена так называемая топологическая кодировка, построенная с использованием принципов классической системы Баттла . Идентификационный код представляет собой упорядоченный набор символов типа "Т" ( ТОР ), " ь " (LEFT), "R" ( RIGT ),"В" (BOTTOM), n0" (ZERRO) и т.д. Эти символы используются для обозначения верхних, нижних, крайних левых и крайних правых точек папиллярных линий, называемых в совокупности "узлами", рис.2. С помощью такой символики узоры описываются топологическими кодовыми словами,после чего идет описание.
