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

Нижегородский государственный технический университет

РОГИНСКНЙ Андрей Викторович

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

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

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

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

6 О»

Нижний Новгород - 1998

Работа выполнена в Нижегородском государственном техническом университете.

Научный руководитель -член-корреспондент РАН профессор Кондратьев В.В.

Официальные оппоненты: доктор технических наук Моругин С.Л. кандидат технических наук Мальцев В.Н.

Ведущая организация -НИИ прикладной математики и кибернетики ННГУ

Защита состоится "ее" 1998 г. в часов на заседании

диссертационного совета Д 063.8д02 Нижегородского государственного технического университета по адресу: 603600, Нижний Новгород, ул. Минина,

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

24.

Автореферат

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

Иванов А.П.

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

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

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

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

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

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

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

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

2. Построение топологическо-геометрического описания на основе оценки ориентации линейных элементов структуры. Разработка алгоритма оценки средней направленности линейных структур на участках изображения.

3. Разработка эффективного способа сжатия линейчато-анизотропных изображений на основе полученного топологическо-геометрического описания.

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

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

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

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

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

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

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

4. Разработан эффективный метод сжатия линейчато-анизотропных изображений на базе зон направленности.

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

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

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

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

Апробация работы Основные положения диссертационной работы докладывались и обсуждались на:

Научно-технической конференции факультета радиоэлектроники и технической кибернетики, посвященной 80-летию НГТУ (Н.Новгород, 1997);

VIII Всероссийской конференции "Математические методы распознавания образов" (Москва, 1997);

LUI научной сессии Российского НТОРЭС им. A.C. Попова, посвященной Дню радио (Москва, 1998);

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

Научно-технической конференции "Применение математического моделирования для решения задач в науке и технике" (Ижевск, 1998).

Публикации. По теме диссертации опубликовано 9 работ.

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

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

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

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

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

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

б

да, так и определение способов предварительной обработки этих изображений.

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

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

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

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

На основе анализа состояния исследуемого вопроса, выполненного в данной главе, сформулированы основные цели и задачи диссертации.

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

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

Кратко изложен представленный в работах В.В. Кондратьева и В.А. Утробина метод раскрытия априорной неопределенности изображения, включающий построение пирамидального описания. Проанализированы характеристики используемого при этом множества операторов преобразования {Vj, j= 1,16}. Установлены базовые свойства, выявляемые ими при описании

структуры линейчатых изображений: кривизна линейных элементов изображения (ЛЭИ) и, отчасти, их взаимное расположение, симметрия на участках изображения.

Наиболее информативными участками структуры линейчатых изображений традиционно считаются места разветвлений и пересечений составляющих линейных элементов, выявляемые вышеуказанными операторами лишь отчасти, вследствие чего требуется дополнение используемого множества операторами, отвечающими внутренней структуре линейчатых изображений. Логическое перемножение операторов {У^ и инверсных им (V]},

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

У^ + У^Уи,

где Ук,Уь Ут,Уп е {У,} и{V]}. В данной работе среди них произведено выделение операторов, соответствующих стандартным отношениям линейных структур изображения, которые совместно с {Vj, j = 1,16} образуют расширенное множество операторов преобразования.

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

щади изображения толщина линейных элементов с!; межлинейное расстояние элементов изображения (толщина фона) Г = с!; наличие для произвольного линейного элемента хотя бы одного соседнего с ним сонаправленного элемента; соотношение 1» <1 для длины 1 линейного элемента, на которой происходит существенное для операторов изменение ориентации.

Исходя из свойств этих изображений и операторов определено

соотношение

¡н > 10Ц4(Ь/С1),

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

Таким образом, имеет место противоречие между эффективным выделением структуры и информационной избыточностью описания, причина которого в том, что у линейчато-анизотропных изображений можно выделить два уровня структурной организации. Для эффективного построения описания предложен подход, основанный на предварительном преобразовании изображения к некоторому более простому образу, состоящему из меньшего числа больших по размеру элементов, определяющих структуру на уровне линейных потоков. При этом помимо преодоления избыточности описания достигается уменьшение трудоемкости обработки, т.к. для нового нижнего уровня пирамиды ¡'н установлено соотношение ¡н-Гн=14-1оё4(к), к> 1.

При переходе в распознавании от изображений к их участкам достигается снижение объема обрабатываемой информации при построении описания, кроме того, обработка части вместо целого позволяет прийти к детализации структуры на меньшем уровне пирамиды описания. Проанализированы возможности такого перехода для линейчатых изображений. Введено понятие фрагмента изображения, описываемого пирамидальной структурой, как участка, равного одной из ячеек некоторого уровня пирамиды описания. Выведена формула для уровня извлечения наиболее информативных фрагментов ¡*1 + 1о§4(Ь/4с1).

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

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

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

С его помощью строится новая, более простая по сравнению с полем направлений структура топологическо-геометрического описания - карта зон направленности. Пусть линейчатое изображение разбито на некоторое количество равных прямоугольных участков Каждому из них может быть сопоставлен угловой параметр, представляющий собой среднее значение параметров ориентации элементов, расположенных на участке. Однако, для построения топологического описания нет необходимости точного расчета его величины, достаточно эффективной будет приближенная оценка с заданной погрешностью. Угловые параметры будут принимать значения из множества {а^к = 1,п} начальных углов п равновеликих смежных диапазонов, располагающихся от 0 до ж. Связные области участков с одинаковыми значениями ак будем называть зонами направленности С^.

Выделение зон направлетюсти предложено проводить в две стадии. На первой используется разработанное преобразование, максимально увеличивающее толщину ЛЭИ, расположенных под заданным углом наклона, по отношению к толщине других элементов, не изменяя габаритов и общей структуры исходного изображения \У0. Это преобразование предлагается проводить в три этапа: направленное растяжение Р[, такое, что коэффициент изменения толщины элементов заданной ориентации ак удовлетворяет условию

^(ак) =тах(^(а)); сглаживание Р8, такое, что толщина произвольного ЛЭИ изменяется с <1 на с) - £ и направленное сжатие Р2, такое, что

После преобразования на изображении ^'(а^) = Рг^^^о))) для новой

толщины линейного элемента, имевшего угол ориентации а и исходную толщину ё, выполняется

<!'= <1-8/Г,Сое)

й'(ак) = тах(<Г(а)).

Проанализированы виды отображений, реализующих И], Г2 и Рц. Для общего случая сск * я / 2, сск 0 в качестве Р| предложено использовать отображение косого сдвига, изменяющего координаты точек изображения по схеме

(х,у)-»(х + ру,у). Доказано, что для получения \¥(ак ) должно выполняться условие р = ^а .

Отображение 1'2 при этом реализуется по обратной по отношению к схеме.

На второй стадии производится непосредственно выделение зон направленности {<Зк} по множеству полученных изображений {М^о^):!^ 1,п}. Для выявления принадлежности участка изображения \У<) к той или иной зоне направленности <5, получена формула г: ^иУ(аг)= тах{миу(ак)},

к = 1,п

где ц1П,(ак) - визуальная масса участка wuv на изображении М(ак).

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

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

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

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

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

лизовывать с точностью до центров участков. Проведена формализация условий обрыва и разветвления для произвольного участка \у к( на основе анализа принадлежности участков группы 1=к-1,к+1, j=t-l,t + l к зонам

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

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

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

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

х'-Ь<х<х'+Ь,

где Ь - размер полуокрестности. Введены определения обрыва и разветвления линейного элемента по конкретной ординате в основе которых лежит анализ выполнения ряда условий связности точек и наличия требуемых яркостных характеристик у определенных наборов точек. При этом ИТ будем считать точку, для которой в окрестности заданного размера I = 2Ь имеет место либо обрыв, либо разветвление линейного элемента, которому принадлежит данная точка, по ординате, находящейся в пределах окрестности.

Для произвольной точки введены метки Ь] нЬ,, значения которых зависят от наличия обрывов и разветвлений в левой и правой полуокрестностях, соответственно. Они могут принимать значения из множества {0,1,2} в зависимости от достигаемого по выбранной полуокрестности числа ЛЭИ. Очевидно, что при выполнении неравенства (Ь|,ЬГ) * (1,1) точка является информативной.

Алгоритм поиска ИТ базируется на нахождении для каждой из анализируемых точек однозначно соответствующего набора из четырех особых точек, которые назовем левая верхняя, левая нижняя, правая верхняя и правая нижняя точки, обобщенно - крайние точки. Они принадлежат множеству точек, связных с анализируемой по уровню яркости ц = 0 и находящихся в ее заданной окрестности. Эти точки выявляются процедурой прослеживания контуров ЛЭИ из анализируемой точки, при заданных параметрах Ь = {-1,1}

I V = {-1,1}, определяющих направления горизонтального и вертикального фослеживания, соответственно.

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

Координаты крайних точек служат основой для определения меток I Ьг, соответствующих исходной точке. Свидетельством досрочного кончания прослеживания контура по данному направлению является выпол-[ение неравенства хь * М>+ х',

де хь - ордината крайней точки. Если для пары сопряженных по горизон-альному направлению крайних точек это имеет место, то фиксируется обрыв 1ЭИ и соответствующей метке присваивается нулевое значение. В противном лучае, для определения Ц либо Ьт анализируется множество точек, распо-оженных между нижней и верхней точками по вертикали. Рассчитывается тношение

ъ = £ц(х,у)/п, я

де Я - вышеупомянутое множество точек, а п - его мощность. В зависимости т соотношения г и некоторого заданного порога метке присваиваются качения из набора {1,2}. По полученным меткам исследованной точке при-ваивается единая метка информативности Ь.

Определены интервал дискретизации для отбора на изображении обра-атывамых точек в зависимости от средней толщины линейных элементов ля заданного вида изображений, а также величина исследуемой окрестности, [редложен способ сравнения изображений при помощи представленного писания по информативным точкам. Получаемые результаты представляют-я в виде матрицы ||Цк,1)||, в которой элементы Ь(1,^ равны значению меток , для обработанных точек. Введена специальная операция (обозначена как ) над матрицами сравниваемых изображений, результат которой определяет еру их сходства

К = ||ь1(к,1)||.||ь2(к,1)||т= Ь(и)'Ь2(у).

¡=1,1^=1,1

При этом для двух элементов матриц результат операции определяете;

как

= ^ --

где е - допустимая величина взаимного смещения изображений.

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

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

Будем рассматривать множество классов {N¡,1 = 1,п}, каждый из которых включает в себя лишь один эталон. Предполагается, однако, что все эталоны могут быть поделены на некоторое количество ш классов {М^ j = 1, ш}. т « п на основе гипотезы компактности. На первом этапе алгоритма проводится предварительное отнесение распознаваемого изображения к одному из ш классов {М^ и его результаты предлагается трактовать не как точно установленное соответствие классу Мр а как предпочтение, оказанное этому

классу, с дальнейшей идентификацией по всему множеству эталонов.

Суть термина "предпочтение" показана на следующем примере. Пусть имеем изображение \¥0, отнесенное на первом этапе к классу М8, и два эталонных изображения - и \У2, такие, что е М5, \У2 <£ М5. Пусть евклидовы расстояния И. между их описаниями таковы, что '

И^'оЛУО-К^о.Уу'г) = ДК, ДЯ > 0. Предложено использовать на втором этапе новую меру расстояния Р(Г(М5),Я), где Г(М8) - некоторая мера предпочтения для класса М8, такую, что

1^0,^/2) = ДЛ', ДЯ/сДЯ, и в частном случае ДИ'< 0. Таким образом, \У0 "притягивается" к ^ еМ5 и в частном случае становится ближе к \У1( чем к \\'2, что'является выражением предпочтения, оказанного классу М£. 14

Для используемого множества признаков {х;Л=1, р} на каждом из лассов может быть определен набор весов {>. ^}, такой, что \y~IiCMj),

це 1( (Mj) - информативность признака X; на классе М^ Доказано, что ука-анный набор весов как раз и будет являться мерой предпочтения, обес-ечивающей "притягивание" распознаваемого изображения к множеству изо-ражений выбранного на первом этапе класса. При этом мера Я' будет пред-гавлять собой взвешенное по {Я,у} евклидово расстояние.

Рассмотрен пример для двух признаков XI и х2, двух классов М! и Л2> таких, что 1](М^) > 12(М|), и для изображения, отнесенного на предва-ительном этапе в класс М |, а по евклидову расстоянию равноудаленного от гих классов. Расстояние от изображения до центров классов М) и М2 в ространстве признаков по осям Х),х2 равно с, ,с2 и с 3 ,с4, соответственно, ¡ыявлено, что "притягивание" изображения с однозначным его отнесением на тором этапе к классу М 5 будет происходить при выполнении условия С| /с2 < с3 /с4.

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

Рассмотрено определение информативности признака как функции вух дополнительно вводимых величин - устойчивости и характерности при-нака для заданного класса. Для расчета этих величин предложено использо-ать статистические параметры эталонных выборок заданного объема из формированных на первом этапе классов {М^. В результате, для определе-ия весов признаков предложена формула ^ = ^Ав /вщахМ + кг^шкО) ^¡5, де - выборочное стандартное отклонение, а - среднее межклассовое асстояние по признаку x¡ для класса М8, 0тах(5) = шах{0;5}, тахф = тах{8^}, к 1 и к2 - дополнительные коэффициенты.

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

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

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

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

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

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

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

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

В заключении сформулированы основные результаты работы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

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

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

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

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

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

ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Колебанов C.B., Рогинский A.B. Алгоритмическое обеспечение пирамидальной системы распознавания изображений // Труды конференции "Применение математического моделирования для решения задач в науке и технике",- Ижевск, 1998,- С. 45-54.

2. Кондратьев В.В., Рогинский A.B. Метод снижения информационной избыточности локально-анизотропных изображений // LII Научная сессия, посвященная дню Радио: Тез. докл.-М., 1998,-С. 147-148.

3. Кондратьев В.В., Рогинский A.B. Новый метод обработки локально-анизотропных изображений //Автометрия.- 1998,- №6.

4. Кондратьев В.В., Рогинский A.B., Утробин В.А. Автоматизированная система распознавания дактилоскопической информации // Математические методы распознавания образов: Тез. докл. 8-й Всеросс. конф,- М., 1997.- С. 166-167.

5. Кондратьев В.В., Утробин В.А., Рогинский A.B. Двухэтапный алгоритм распознавания отпечатков пальцев // Научно-техническая конференция факультета радиоэлектроники и технической кибернетики, посвященная 80-летию НГТУ: Тез. докл.- Н. Новгород, 1997. - С. 35-36.

6. Кондратьев В.В., Утробин В.А., Рогинский A.B. Идентификация отпечатков пальцев с использованием пирамидальной системы операторов преобразования // Системы обработки информации и управления,- Н. Новгород,

1997. - С. 53-58.

7. Рогинский A.B. Выделение характерных точек на линейчато-составных изображений // Научно-техническая конференция факультета информационных систем и технологий: Тез. докл.- Н. Новгород, 1998,- С. 48-49.

8. Рогинский A.B. Распознавание изображений по матрице характерных точек, выявленных локальным отслеживанием контуров // Труды конференции "Применение математического моделирования для решения задач в науке и технике".- Ижевск, 1998.- С. 72-77.

9. Рогинский A.B. Особенности пирамидальной системы распознавания локально-анизотропных изображений II Научно-техническая конференция факультета информационных систем и технологий: Тез. докл.- Н. Новгород,

1998.-С. 47-48,-

Нижегородский государственный технический университет

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

РОГИНСКИЙ АНДРЕЙ ВИКТОРОВИЧ

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

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

Диссертация на соискание ученой степени кандидата технических наук

Научный руководитель -член-корреспондент РАН профессор В.В. Кондратьев

Нижний Новгород 1998

СОДЕРЖАНИЕ

стр.

Введение 5

Глава 1. Состояние вопроса. Основные цели и задачи 11 диссертационной работы.

1.1. Состояние вопроса. 11

1.1.1. Структурно-иерархическое описание. 14

1.1.2. Топологическо-геометрическое описание. 15

1.1.3. Сжатие изображений. 17

1.1.4. Точечное описание. 18

1.1.5. Алгоритмы распознавания. 19

1.1.6. Выводы. 20

1.2. Основные цели и задачи диссертационной работы. 21 Глава 2. Применение модели пирамидального описания к 23

линейчатым изображениям.

2.1. Формирование пирамидального описания 24 линейчатых изображений.

2.1.1. Постановка задачи. 24

2.1.2. Решение задачи. 27

2.2. Особенности пирамидального описания 30 линейчато-анизотропных изображений.

2.2.1. Постановка задачи. 30

2.2.2. Решение задачи. 32

2.3. Выделение участков изображений как объектов 37 пирамидального описания.

2.3.1. Постановка задачи. 37

2.3.2. Решение задачи. 39

2.4. Основные результаты главы. 45

Глава 3. Новая структура топологическо-геометрического 47 описания линейчатых изображений и ее использование.

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

3.1.1. Постановка задачи. 48

3.1.2. Решение задачи. 50

3.1.3. Пример конкретной реализации. 59

3.2. Использование зон направленности изображения 61 для формирования структур описания.

3.2.1. Постановка задачи. 62

3.2.2. Решение задачи. 64

3.2.3. Пример конкретной реализации. 70

3.3. Основные результаты главы. 72 Глава 4. Новый подход к выделению информативных точек 74

линейчатого изображения.

4.1. Алгоритм выделения информативных точек 75 линейчатого изображения.

4.1.1. Постановка задачи. 75

4.1.2. Решение задачи. 77

4.1.3. Пример конкретной реализации. 87

4.2. Основные результаты главы. 89 Глава 5. Двухэтапный алгоритм классификации с новым 91

методом использования результатов предварительного этапа.

5.1. Метод использования результатов предварительной 92 классификации в виде формирования меры предпочтения.

5.1.1. Постановка задачи. 92

5.1.2. Решение задачи. 95

5.1.3. Определение набора весов признаков. 100

5.1.4. Практические данные и пример численного 103 расчета.

5.2. Построение предварительного этапа для 106 предложенного алгоритма классификации.

5.2.1. Постановка задачи. 106

5.2.2. Решение задачи. 106

5.2.3. Пример численного расчета. 112

5.3. Основные результаты главы. 114 Глава 6. Практическая реализация системы 116

распознавания линейчатых изображений.

6.1. Практическая реализация разработанной системы 116 распознавания.

6.1.1. Структурная схема системы. 117

6.1.2. Функциональная схема системы. 119

6.1.3. Оценка результатов работы системы. 124

6.2. Основные результаты главы. 128 Заключение 129 Литература 131 Приложение. Документы о практической реализации 143

результатов диссертации

ВВЕДЕНИЕ

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

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

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

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

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

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

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

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

2. Построение топологическо-геометрического описания на основе оценки ориентации линейных элементов структуры. Разработка алгоритма оценки средней направленности линейных структур на участках изображения.

3. Разработка эффективного способа сжатия линейчато-анизотропных изображений на основе полученного топологическо-геометрического описания.

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

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

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

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

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

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

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

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

4. Разработан эффективный метод сжатия линейчато-анизо-тропных изображений на базе зон направленности.

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

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

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

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

масском РОВД. Экономический эффект определяется сокращением времени обработки и распознавания отпечатков пальцев и подписей по сравнению с неавтоматизированной работой эксперта. Теоретические и практические результаты, полученные автором, использованы в научном и учебном процессе НГТУ.

Апробация работы Основные положения диссертационной работы докладывались и обсуждались на:

Научно-технической конференции факультета радиоэлектроники и технической кибернетики, посвященной 80-летию НГТУ (Н.Новгород, 1997);

VIII Всероссийской конференции "Математические методы распознавания образов" (Москва, 1997);

LUI научной сессии Российского НТОРЭС им. A.C. Попова, посвященной Дню радио (Москва, 1998);

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

Научно-технической конференции "Применение математического моделирования для решения задач в науке и технике" (Ижевск, 1998).

Публикации. По теме диссертации опубликовано 9 работ [31,32,33,34,41,42,57,58,59].

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

наименования, изложенных на 142 страницах, а также приложения на 3 страницах.

ГЛАВА 1. СОСТОЯНИЕ ВОПРОСА. ОСНОВНЫЕ ЦЕЛИ И ЗАДАЧИ ДИССЕРТАЦИОННОЙ РАБОТЫ

1.1. Состояние вопроса.

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

V

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

К настоящему времени существует более или менее единая классификация направлений в распознавании образов [15,19,56], каждое из которых включает в себя ряд поднаправлений, проработанных в большей или меньшей степени, согласованы общие вопросы методологии построения и реализации систем распознавания [15,19,24,56,64]. Важнейшими аспектами создания таких систем являются, во-первых, определение структуры описания и разработка процедур его построения, т.е. переход от объекта к набору признаков, а, во-вторых, разработка распознающих алгоритмов.

Алгоритмы распознавания работают, как правило, с абстрактными наборами признаков и, соответственно, не привязаны к конкретным видам образов. Они представлены в настоящее время двумя основными семействами. Статистические алгоритмы [12,19,24,25] работают преимущественно с числовыми признаками и используют

методы статистического анализа. Лингвистические (структурные) алгоритмы [66,67,71] работают со структурными признаками и используют методы грамматического описания и разбора.

Если построение распознающих алгоритмов относится к распознаванию образов в целом, то решение задач выбора системы признаков и построения описания существенным образом зависит от вида объекта (изображение, звук, природные явления, социальные и экономические процессы и т.д.). Наиболее значимой и, соответственно, наиболее развитой областью распознавания относительно видов образов является распознавание изображений [19,28,55,60,66,72, 73], тесно связанное с вопросами моделирования зрительного восприятия [48,60,70].

Следует, однако, учесть, что изображения представлены широким многообразием существенно различающихся классов. Например, в [15] выделяются классы тоновых и многоцветных, бинарных изображений, непрерывных кривых и линий, точек и многоугольников. Изображения различаются и по другим параметрам: плоские и трехмерные, статические и динамические и т.д. Следовательно, должны иметь место особенности подходов к их распознаванию, особенно на стадии описания.

Как отмечено в [67], "при разработке любого инструмента естественно в максимальной степени учитывать свойства того класса предметов, для обработки которого этот инструмент предназначен". В очень многих работах по распознаванию и, в частности, по формированию системы признаков имеют место две крайности: либо речь идет об абстрактных изображениях вообще, либо учитываются отдельные частные свойства изображений. В то же время представляется важным учесть всю совокупность базовых свойств, внутренне

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

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

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

1.1.1. Структурно-иерархическое описание.

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

Широко распространенным вариантом иерархического описания является пирамидальное представление изображений [69,86,98]. Его достоинством является простая и упорядоченная процедура получения описания. Такое описание на верхних уровнях пирамиды может служить для определения общей структуры изображения или для локализации присутствующих на нем отдельных объектов, а на нижних уровнях - для выделения индивидуальных особенностей его участков. Однако, пирамидальное представление с одинаковой степенью подробности описывает все участки изображения, тогда как они не обладают равной информационной ценностью при распознавании.

В работах В.В. Кондратьева и В.А. Утробина [35,36,37,38,39, 40], в отличие от методов, изложенных в [10,46,86,98], предлагается использование двух пирамидальных структур. Пирамида исходного описания дает интегральную оценку визуальных масс участков изображения, аналогично процедурам локального усреднения [96]. Пирамида окончательного описания, полученная применением к исходной специальной системы операторов преобразования, дает дифференциальную оценку структуры по распределению визуальной массы.

Преимуществом такого метода является одномоментность выявления структуры изобра