Лекция № 16

СИСТЕМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

План:

1.1. Основные понятия

1.2. Формирование образа в технических системах

1.3. Выделение признаков распознавания

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

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

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

- распознавание образов;

- понимание естественного языка;

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

- автоматическое доказательство теорем;

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

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

и ряд других.

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

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

Уже Платон (428-348 гг. до н. э.) ставил вопрос о том, что всякое знание и умение должно быть представлено в виде точных определений и правил [1, с. 31].

Аристотель (384-322 гг. до н. э.) заложил основы формальной логики, разработав силлогистику –систему правил, позволяющих выяснить, когда из некоторой системы утверждений следует определенное заключение, а когда не следует. Однако, он считал, что применение формальных правил возможно не во всех сферах человеческой жизни, т.к. часто приходится обращаться к интуитивным понятиям, которые не могут быть четко и однозначно сформулированы.

Томас Гоббс (1588-1679гг.)в своих работах «Левиафан», «Учение о теле» признавал возможность сведения мышления к формально- логическим и даже арифметическим операциям.

Рене Декарт (1596-1650) считал некорректной постановку вопроса о создании разумных машин. Способность к разумному поведению он связывал с наличием души, которой человек не может снабдить машину. Ему возражал Жюльен Ламерти (1709-1751гг.). В книге «Человек-машина» он утверждает существование только одной субстанции – материи. При этом материю он не считает пассивной. Одна из ее функций – интеллект [2, с. 356].

Готфрид Вильгельм Лейбниц (1646-1716), определив небольшое количество исходных и неопределяемых идей, он попытался установить систему правил, «алгебру», позволяющую сформулировать любое сложное понятие. Его практическим вкладом в решение проблемы ИИ было создание двоичной системы счисления. Это позволило Джорджу Булю (1815-1864гг.) в 1847 г. разработать бинарную алгебру, в которой единица обозначает истину, ноль – ложь, а основными действиями являются операции логические «и», «или», «не». При этом Буль и Лейбниц руководствовались не абстрактными математическими интересами. Их цель была исследовать основные законы разума, на основе которых осуществляется рассуждение.

Чарльз Бебедж (1792-1871гг.) в 1834 году выдвинул проект «аналитической машины», которая была прообразом современного компьютера. Однако проект намного опережал технологические возможности своего времени. Только в 1944 году Х. Айкен построил первую цифровую вычислительную машину «Марк -1».

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

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

Структуру СИИ можно представить схемой, изображенной на рис. 1.

ситуация à ~МО à МПР à МО~ à реакция

Рис. 1 Структура СИИ.

На ней СИИ представлена состоящей из модуля общения (связи) (~ МО), преобразующего внешнюю информацию во внутреннюю, модуля принятия решения (МПР) и модуля общения (МО~), преобразующего внутреннюю информацию во внешнюю информацию либо действия над окружающим СИИ миром.

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

Структура МПР может быть представлена схемой, изображенной на рис. 2. На ней

à БИ à БВР à

| ||

БУЗ à ИБД

Рис. 2. Структура МПР

БИ – блок интерпретации, обеспечивает понимание входной ситуации,

БВР – блок выработки решения, определяет реакцию СИИ на на текущую ситуацию, соответствующую целям функционирования системы,

БУЗ – блок усвоения знаний, обеспечивающий понимание и коррекцию знаний об окружающем мире, уточнение целей поведения,

ИБД – интеллектуальный банк данных.

В состав ИБД входят (рис. 3):

ИБД

| | |

БЦ БЗ БД

Рис. 3. Структура ИБД

БЦ – база целей, БЗ – база знаний, БД – база данных.

База целей определяет цели поведения СИИ, обеспечивает реализацию свойства мотивации, побуждения к действию.

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

База данных содержит описания известных фактов и количественные данные.

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

Развитие искусственного интеллекта, равно как и естественного, начинается с создания БД и БЗ, т.е. с накопления фактов и сведений о внешнем мире. Мотивация и направленность его поведения определяется БЦ.

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

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

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

Заключая обобщенное рассмотрение структуры СИИ можно выделить следующие главные факторы, отличающие СИИ от других автоматических систем.

1. Способность к выводу, генерации конструированию решения, которое в явном и готовом виде не содержится в СИИ.

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

2. Способность пополнения, коррекции и усвоения новых знаний.

СИСТЕМЫ РАСПОЗНАВАНИЯ ОБРАЗОВ

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

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

ОСНОВНЫЕ ПОНЯТИЯ

Образ

Образ представляет собой описание (отражение) некоторого объекта, представляемое в виде сигналов.

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

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

Распознавание образов

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

Именно из-за наличия у конкретных объектов некоторых общих признаков мы объединяем их в классы, обозначаемые тем или иным термином (именем): яблоко, автомобиль, стол и т.п.

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

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

Примеры:

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

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

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

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

Признаки распознавания

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

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

Например, такими свойствами (признаками) являются

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

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

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

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

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

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

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

ФОРМИРОВАНИЕ ОБРАЗА

В ТЕХНИЧЕСКИХ СИСТЕМАХ РАСПОЗНАВАНИЯ

Выбор физических эффектов и стратегии распознавания

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

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

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

Вектор образа

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

Такой подход к формализованному представлению образа достаточно универсален.

Если первичная информация поступает от сенсорной сетчатки (например, светочувствительной), состоящей из n элементов, то результаты измерений можно представить вектором

x = (x ₁, …, x_i,…., x_n),

где x_i - интенсивность сигнала от i – го элемента сетчатки. При этом вектор x – вектор образа.

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

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

ВЫДЕЛЕНИЕ ПРИЗНАКОВ РАСПОЗНАВАНИЯ

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

Эвристическое выделение признаков.

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

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

В качестве первого признака распознавания x ₁ можно использовать отношение периметра внешнего контура фигуры к расстоянию от центра фигуры до максимально удаленной от него точки фигуры. Это отношение для круга равно 2 pi = 6,28; для квадрата 8*2^-1/2 = 5,66; для кольца 2 pi = 6,28.

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

В качестве второго признака x ₂ можно использовать отношение квадрата периметра внешнего контура фигуры к ее площади. Это отношение для круга равно 4 pi = 12,56; для квадрата 16; для кольца > 4p.

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

В геометрической интерпретации каждому из рассматриваемых образов соответствует точка на плоскости (x ₁, x ₂). Классу образов «квадрат» - точка (8*2^-1/2; 16). Классу «круг» - точка (2 pi; 4 pi). Классу «кольцо» - отрезок [2 pi; (2 pi, бесконечность)].

На практике используют приближенное определение перечисленных классов, как окрестностей указанных точек и отрезка. Такое определение класса позволяет игнорировать малые отклонения координат x ₁, x ₂ от их идеальных значений, вызванные неидеальностью формы, а также влиянием ошибок округления и помех на результат вычисления признаков реально наблюдаемой фигуры.

Очевидно, каждой точке плоскости x ₁, x ₂ соответствует своя фигура.

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

Типовые процедуры выделения признаков.

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

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

на основе Фурье - преобразований

Пусть имеется черно-белое полутоновое изображение, содержащее распознаваемый образ. При этом F ₁(ф) – функция изменения яркости изображения при обходе замкнутого контура в виде окружности с радиусом r ₁ и центром, совпадающим с центром распознаваемого образа, ф - угол в полярной системе координат, определяющий положение точки на окружности с радиусом r ₁. Функция F ₁(ф) – периодическая функция с периодом 2 pi. Аппроксимируем F ₁(ф) отрезком ряда Фурье:

F ₁ ^* (ф)= C ₁₁sin(ф+фо₁₁)+ C ₁₂sin(2ф+фо₁₂)+… C_{i 1}sin(i ф+фо _{i 1})+…+ C _{1 N} sin(2ф+фо_{1 N} )=

=sum[ C_{i 1}sin(i ф+фо _{i 1})], i= 1,…, N.

Использование нескольких контуров с радиусами r ₁,…, r_j,…, r_M позволяет по значениям соответствующих им коэффициентов C_ij различать соответствующие образы.

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

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

При помещении начала координат в центре распознаваемой фигуры, значения признаков становятся инвариантными к смещению рамки экрана относительно изображения, т.к. при этом система координат остается “привязанной” к одной и той же точке изображения и, следовательно, неизменными остаются графики функций F_j (ф) и значения коэффициентов C_ij.

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

Для обеспечения независимости процедуры распознавания от общей яркости картинки вместо функции яркости картинки F_j (ф) целесообразно использовать нормализованную функцию

F ^н _j (ф) = F_j (ф)/ F_j ^max,

где F_j ^max – наибольшее значение функции F_j (ф) при обходе j -гоконтура.

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

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

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

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

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

На применении таких признаков базируются лингвистические (грамматические) методы распознавания образов.

Формирование лингвистических признаков распознавания

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

Рассмотрим пример формирования признаков для лингвистического описания и распознавания буквы А.

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

1. Разделение по порогу яркости или степени зачерненности изображения. Если зачернение выше порогового уровня, компоненту относят к образу, если ниже, то к фону.

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

3. Разделение изображения на области с одинаковыми значениями зачерненности.

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

На втором этапе каждой точке изображения в соответствии с геометрическими свойствами ее окрестности приписывается определенный код. Код учитывает как направлена линия, проходящая через эту точку. При этом коды L, N, R, E означают соответственно направления: вверх и влево (le F t), вверх = (на север(north)), вверх и вправо (right), влево = (на восток(east)). Инверсии указанных кодов ~L, ~N, ~R, ~E указывают соответственно противоположные направления. Данный этап называют маркировкой изображения.

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

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

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

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

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

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

Дата добавления: 2014-01-14