Порядок выполнения работы. 1. Ознакомление с теоретической частью лабораторной работы. ?тересным приложением лингвистических понятий в распознавании образов является язык PDL (Picture Description Language) – язык описания изображений. ?тересным приложение

 

1. Ознакомление с теоретической частью лабораторной работы.

2. Реализация распознавания объектов синтаксическими методами.

3. Оформление отчета по выполненному заданию.

 

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

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

Формально грамматика может быть задана следующей записью:

где – нетерминальный словарь, – терминальный словарь, – множество правил подстановки, – начальная аксиома

Для грамматики характерны следующие соотношения:

– словарь, ,

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

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

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

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

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

1. . Это правило заменяет начальный символ терминальным элементом , расположенным над некоторым неопределенным объектом .

2. Правило заменяет нетерминальный объект неопределенным объектом , расположенным над горизонтальным отрезком .

3. . заменяется на два вертикальных терминальных элемента.

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

Интересным приложением лингвистических понятий в распознавании образов является язык PDL (Picture Description Language) – язык описания изображений. Терминальным элементом PDL служит любая n-мерная структура с двумя выделенными точками: хвостовой и головной.

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

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

Рис. 6. Правила соединения терминалов

 

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

={ a, b, c, d, e };

={ S, T, Основание, Сторона, Пара плеч, Правая часть, Левая часть, Плечо }.

На рис. 7 изображены терминальные элементы хромосом { a, b, c, d, e }, на
рис. 8 – типичный вид телоцентрической и V-образной хромосом. Оператор «», используемый при построении правил грамматики, означает связность отдельных частей хромосомы, фиксируемую при продвижении вдоль ее границы по направлению часовой стрелки.

 

Рис. 7. Терминальные элементы хромосом

 

 

Рис. 8. Телоцентрическая и V-образная хромосомы

P: S Пара плеч Пара плеч,

T Основание Пара плеч,

Пара плеч Сторона Пара плеч,

Пара плеч Пара плеч Сторона,

Пара плеч Плечо Правая часть,

Пара плеч Левая часть Плечо,

Левая часть Плечо с,

Правая часть с Плечо,

Основание b Основание,

Основание Основание b,

Основание е,

Сторона b Сторона,

Сторона Сторона b,

Сторона b,

Сторона d,

Плечо b Плечо,

Плечо Плечо b,

Плечо а.

 

Начальные символы S и T представляют телоцентрические и V-образные хромосомы. Для разделения на два класса используется одна грамматика с двумя начальными символами. Если грамматический разбор снизу приводит к начальному символу Т, хромосому относят в класс V-образных. Если же разбор приводит к S, хромосома классифицируется как телоцентрическая. В силу схожести поставленных задач целесообразно их решать в рамках одной грамматики. На рис.9 приведено дерево, отражающее порядок разбора предложения.

Рис. 9. Восходящий грамматический разбор хромосомы

В качестве первого шага на пути распознавания заданного цифрового изображения хромосомы необходимо найти точку на границе хромосомы и затем осуществлять продвижение вдоль границы по направлению часовой стрелки. По мере продвижения система процедур распознавания обеспечит обнаружение терминальных элементов {a, b, c, d, e}. В результате такого отслеживания границы хромосома оказывается эффективно сведенной к цепочке терминальных элементов и образует терминальное предложение, как показано на рис. 8. После сведения хромосомы к терминальному предложению начинается его синтаксическое распознавание. Рассмотрим предложение для телоцентрической хромосомы и применим к нему разбор снизу вверх. Будет происходить обратный порядок применения правил подстановки, начиная с правила Плечо а.

Рассмотрим алгоритм проверки классификации хромосомы.

1-й шаг. Анализатор находит а и выдает нетерминал Плечо. Символ а находится 4 раза, что приводит к появлению четырех нетерминалов Плечо на первом уровне поиска, считая снизу.

2-й шаг. Сочетание Плечо с терминалом b.

3-й шаг. Порождение Плеч.

4-й шаг. Порождение нетерминала Сторона при помощи символов d и b.

5-й шаг. Комбинация Плеча и с порождает Правую часть.

6-й шаг. Правая часть и Плечо порождают Пару плеч.

7-й шаг. Пара Плеч и Сторона порождают два символа Пара Плеч.

8-й шаг. Объединение двух Пар Плеч в S.

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

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

 

 

ЛИТЕРАТУРА

1. Фор А. Восприятие и распознавание образов: Пер. с фр. – М.: Машиностроение, 1989. – 272с.

2. Ту Дж., Гонсалес Р. Принципы распознавания образов: Пер. с англ. – М.: Мир, 1978. – 412с.

Св.план 2006, поз. 57

 

 

Учебное издание

 

бочкарёва Лия Валентиновна,

Кирейцев Максим Валерьевич