Государственное образовательное



Скачать 310.47 Kb.

Дата07.04.2017
Размер310.47 Kb.
Просмотров53
Скачиваний0

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ
ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ
УЧРЕЖДЕНИЕ
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ
«ВОРОНЕЖСКИЙ ГОСУДАРСТВЕННЫЙ
УНИВЕРСИТЕТ»
СТРУКТУРНОЕ РАСПОЗНАВАНИЕ
ОБРАЗОВ
Учебно-методическое пособие для вузов


Составитель
Н.М. Новикова









Издательско-полиграфический центр
Воронежского государственного университета
2008

2
Утверждено научно-методическим советом факультета прикладной математики, информатики и механики 24 апреля 2008 г., протокол № 8
Пособие подготовлено на кафедре технической кибернетики и автоматиче- ского регулирования факультета прикладной математики, информатики и механики Воронежского государственного университета.
Рекомендуется для студентов 4 курса дневного отделения.
Для направления: 010200 – Математика. Прикладная математика
(бакалавриат). ДС. 06

3
Введение
Способность «распознавать» считается основным свойством человеческих существ, как, впрочем, и других живых организмов. Образ представляет собой описание объекта. В каждое мгновение нашего бодрствования мы совершаем акты распознавания. Мы опознаем окружающие нас объекты и в соответствии с этим перемещаемся и совершаем определенные действия. Мы можем заметить в толпе друга и понять, что он говорит, можем узнать голос знакомого, прочесть руко- пись и идентифицировать отпечатки пальцев, можем отличить улыбку от злобной гримасы. Человеческое существо представляет собой очень сложную информационную систему – в определенной степени это определяется чрезвычайно развитыми у человека способностями распознавать образы.
В соответствии с характером распознаваемых образов акты распознавания можно разделить на два основных типа: распознавание конкретных объектов и распознавание абстрактных объектов.
Мы распознаем символы, рисунки, музыку и предметы, нас окружающие.
Процесс, включающий распознавание зрительных и слуховых образов, можно определить как «сенсорное» распознавание. Процессы этого типа обеспечивают идентификацию и классификацию пространствен- ных и временных образов. Примерами пространственных образов служат символы, отпечатки пальцев, синоптические карты, физические объек- ты и рисунки. Примерами временных образов являются: речь, сигна- лы, электрокардиограммы, характеристики цели в радиолокации и вре- менные ряды. С другой стороны, мы в состоянии с закрытыми ушами и глазами опознать старый довод или найти решение задачи. Подобные процессы обеспечивают распознавание абстрактных объектов и их можно определить как «понятийное» распознавание в отличие от зрительного или слухового распознавания.
Основные понятия теории распознавания образов
Определение 1. Под классом образов понимается некоторая категория, определяемая рядом свойств, общих для всех ее элементов.
Определение 2. Образ – это описание любого элемента как представителя соответствующего класса образов.
В случае, когда множество образов разделяется на непересекающие- ся классы, желательно использовать для отнесения этих образов к соот- ветствующим классам какое-либо автоматическое устройство. Считы- вание и обработка погашенных банковских чеков являются примером задачи распознавания образов. Подобные задачи могут выполняться и

4
людьми; машина, однако, справляется с ними много быстрее. С другой стороны, некоторые задачи распознавания таковы, что человек едва ли в состоянии решать их. Примером задач такого рода служит выделение из множества морских сигналов и шумов тона подводной лодки посредст- вом анализа подводных звуковых сигналов.
Очевидное, но совсем уж «бесхитростное» решение задачи распознавания заключается в применении к отдельным предъявленным образам ряда простых тестов для выделения признаков каждого класса.
Совокупность этих тестов должна различать все допустимые образы из разных классов. Например, рассмотрим пять английских букв: COINS. Эти буквы можно классифицировать, применив тесты на наличие таких при- знаков, как замкнутая кривая, изгиб, двойной изгиб, вертикальный от- резок, короткий отрезок.
Если следовать такому интуитивному подходу, то построение ав- томатической системы распознавания образов может показаться довольно простой задачей. Не существует, однако, общей теории, позволяющей определить, какие из всего множества мыслимых тестов следует применить к предъявленным образам. Очень ограниченное количество или небреж- ный выбор тестов не дадут возможности получить характеристики предъявленных для распознавания образов, достаточные для отнесения их к соответствующим классам. Слишком много тестов, с другой стороны, необоснованно усложняют вычисления, осуществляемые в процес- се дальнейшего анализа. Отсутствует какое-либо общее правило для по- лучения неких ориентиров, способствующих определению набора таких тестов. Подобный подход чрезмерно зависит от опыта и технической ин- туиции разработчика и поэтому часто не дает удовлетворительного решения задач распознавания образов, встречающихся в практической деятельности.
Основные задачи, возникающие при разработке систем
распознавания образов
Задачи, возникающие при построении автоматической системы рас- познавания образов, можно обычно отнести к нескольким основным облас- тям.
Первая задача связана с представлением исходных данных, полу- ченных как результаты измерений для подлежащего распознаванию объек- та. Это – проблема чувствительности. Каждая измеренная величина явля- ется некоторой характеристикой образа или объекта. Допустим, напри- мер, что образами являются буквенно-цифровые символы. В таком случае в датчике может быть успешно использована измерительная сетчатка. Если сетчатка состоит из п элементов, то результаты измерений можно предста- вить в виде вектора измерений или вектора образа
где каждый элемент
i
x принимает, например, значение 1, если через i-ю ячейку п
сетчатки проходит изображение символа, и 0 в ротивном случае.
Векторы образов содержат всю информацию об образах, поддаю- щуюся измерению. Процесс измерения, которому подвергаются объекты определенного класса образов, можно рассматривать как процесс кодиро- вания, заключающийся в присвоении каждой характеристике образа символа из множества элементов алфавита
}
{
i
x . Когда измерения приво- дят к информации, представленной действительными числами, часто оказывается полезным рассматривать векторы образов в качестве точек
n-мерного пространства измерений. Соответствующий простой пример приведен на рис. В.1. для случая двух классов, обозначенных
1
ω
и
2
ω
. В этом примере предполагается, что классы
1
ω
и
2
ω
представляют соответст- венно группы футболистов-профессионалов и жокеев. Каждый "образ" характеризуется результатом двух измерений: ростом и весом. Векторы образов имеют, следовательно, вид
2 1
)
,
(
x
x
x
=
, где параметр
1
x – рост, а '
параметр х
2
вес. Каждый вектор образа можно считать точкой двумерно- го пространства. Как следует из рис. В.1, эти два класса образуют непересекающиеся множества, что объясняется характером измерявшихся параметров.
Рис. В.1 Два класса, образующие непересекающиеся множества
В практических ситуациях, однако, далеко не всегда удается вы- брать измеряемые параметры так, чтобы получить строго непересекаю-
5

6
щиеся множества. В частности, если в качестве критериев разбиения вы- бран рост и вес, может наблюдаться существенное пересечение классов, представляющих профессиональных футболистов и баскетболистов.
Вторая задача распознавания образов связана с выделением харак- терных признаков или свойств из полученных исходных данных и сни- жением размерности векторов образов. Эту задачу часто определяют как задачу предварительной обработки и выбора признаков.
Признаки классов образов представляют собой характерные свойст- ва, общие для всех образов данного класса. Признаки, характеризую- щие различия между отдельными классами, можно интерпретировать как межклассовые признаки. Внутриклассовые признаки, общие для всех рассматриваемых классов, не несут полезной информации с точки зрения распознавания и могут не приниматься во внимание. Выбор признаков считается одной из важных задач, связанных с построением распознаю- щих систем. Если результаты измерений позволяют получить полный на- бор различительных признаков для всех классов, собственно распознава- ние и классификация образов не вызовут особых затруднений. Автомати- ческое распознавание тогда сведется к процессу простого сопоставления или процедурам типа просмотра таблиц. В большинстве практических за- дач распознавания, однако, определение полного набора различитель- ных признаков оказывается делом исключительно трудным, если вообще не невозможным. К счастью, из исходных данных обычно удается из- влечь некоторые из различительных признаков и использовать их для уп- рощения процесса автоматического распознавания образов. В частности, размерность векторов измерений можно снизить с помощью преобра- зований, обеспечивающих минимизацию потери информации.
Третья задача, связанная с построением систем распознавания об- разов, состоит в отыскании оптимальных решающих процедур, необхо- димых при идентификации и классификации. После того, как данные, со- бранные о подлежащих распознаванию образах, представлены точками и векторами измерений в пространстве образов, предоставим выяснить, какому классу образов эти данные соответствуют.
Одним из решений задачи распознавания образов является струк- турный или синтаксический метод.
Синтаксический подход распознаванию образов
к
Большинство различных математических методов решения задач распознавания образов распадается на две группы, одну из которых можно трактовать с позиций теории решений (дискриминантный подход), а дру- гую – в рамках синтаксического (или структурного) подхода. В первом подходе объекты характеризуются наборами чисел – результатов некото- рого множества измерений, характеризующих объекты, называемые при- знаками. Распознавание образов (отнесение каждого объекта к некоторому

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

8
языков. В рамках синтаксического подхода считается, что образы стро- ятся из соединенных различными способами подобразов, так же как фразы и предложения строятся путем соединения слов, а слова соединя- ются из букв. Очевидно, что такой подход полезен только в том случае, когда распознать выбранные простейшие подобразы, называемые не- производными элементами, легче, чем сами образы.
Определение 3. «Язык», который обеспечивает структурное описа- ние образов в терминах множества непроизводных элементов и опера- ций композиции этих элементов, называют «языком описания образов».
Правила композиции непроизводных элементов обычно задают при помощи грамматики языка описания образов.
Процесс распознавания осуществляется после идентификации в объ- екте непроизводных элементов и составлении описания объекта. Распо- знавание состоит в синтаксическом анализе, или грамматическом разбо- ре, «предложения», описывающего данный объект. Эта процедура уста- навливает, является ли это предложение синтаксически (или граммати- чески) правильным по отношению к заданной грамматике. Параллельно синтаксический анализ дает некоторое структурное описание предложе- ния (обычно в виде древовидной структуры).
Синтаксический подход к распознаванию образов дает возможность описывать большое множество сложных объектов путем использования небольшого множества непроизводных элементов и грамматических правил. Грамматическое правило (правило подстановки) может быть применено любое число раз, так что оказывается возможным очень ком- пактно выразить некоторые основные, структурные характеристики бес- конечного множества предложений. Одним из наиболее привлекатель- ных аспектов этой возможности является использование рекурсивной природы грамматик. Практическая полезность такого подхода зависит, конечно, от способности распознавать непроизводные элементы образов и их взаимные отношения, выраженные операциями композиции.
Различные отношения, определенные между подобразами, или операции композиции, обычно могут быть выражены логическими и
(или) математическими операциями. Если, например, в качестве единст- венного отношения (операции композиции) для описания образов вы- брать конкатенацию» (конкатенацией элементов а и b называется со- ставл из них цепочка аb), то при непроизводных элементах
«
енная


прямоугольник будет представлен цепочкой aaabbсcсdd. Точнее, если ис- пользовать знак плюс для обозначения операции «конкатенация начала льник одного элемента к концу другого», то прямоуго дложением а + а + а + b + b + c + с + с + d
будет представлен
+ d.
Древовидная структура этого предложения: ать бо-
Пример 2. На рис. 3 показан граф отношений изображения F (рис. 1). пре
9
Другим представлением структурной информации образа служит «граф отношений». Путем использования графа отношений для описания образов можно расширить класс допустимых отношений, включив в него любое отношение, которое удобно определяется из образа. Заметим, что, во- первых, конкатенация – единственная естественная операция для одномер- ных языков и, во-вторых, что граф, вообще говоря, содержит циклы, тогда как дерево их не содержит. Поэтому при помощи графа можно выраж лее богатые описания, чем с помощью древовидных структур.

Рис. 3
Использование древовидных структур позволяет непосредствен- но приспособить методы теории формальных языков к задаче компактного представления и анализа образов, имеющих существенное структурное содержание. Синтаксический подход называют лингвистическим по- тому, что в нем используются методы теории формальных языков.
Система синтаксического распознавания образов
Систему синтаксического распознавания образов можно считать со- стоящей из трех основных частей, а именно: из блока предобработки, блока описания или представления объекта и блока синтаксического анализа. Блок предобработки осуществляет, во-первых, функции кодирования и аппрок- симации и, во-вторых, функции фильтрации, восстановления и улучшения объекта. Исходный объект сначала кодируется или аппроксимируется так, чтобы это было удобно для дальнейшей обработки. Черно-белое изо- бражение, например, можно кодировать при помощи решетки (или матри- цы), состоящей из нулей и единиц, а кривую можно аппроксимировать от- счетами в дискретные моменты времени или конечным набором коэффи- циентов Фурье. Затем используют методы фильтрации, восстановления и
(или) улучшения для ликвидации шума, восстановления искажений и (или) улучшения качества закодированных (или аппроксимированных) объектов.
Обычно предполагают, что на выходе предпроцессора имеются объекты относительно «хорошего качества». Каждый подвергнутый предобработке объект затем представляют в виде структуры языкового типа (например, цепочки). Этот процесс представления объекта состоит, во-первых, из сег- ментации и, во-вторых, из выделения непроизводных элементов (признаков).
Чтобы представить объект через его подобразы, нужно этот объект сегменти- ровать и в то же время идентифицировать (или выделить) в нем непроизвод- ные элементы. Другими словами, каждый подвергнутый предобработке объ- ект разделяется на части и непроизводные элементы на основе заранее задан- ных синтаксических операций (или операций композиции).
10

11
Каждая выделенная часть в свою очередь идентифицируется от- носительно заданного множества непроизводных элементов. На этой стадии каждый объект получает свое представление через множество не- производных элементов и определенные синтаксические операции. На- пример, если задана операция конкатенации, то каждый объект пред- ставляется цепочкой примыкающих непроизводных элементов. Решение о том, является ли представление объекта синтаксически правильным (т. е. принадлежит ли он классу образов, описываемых данным синтаксисом или данной грамматикой), принимается «блоком синтаксического анализа» или «блоком грамматического разбора». По ходу синтаксического анали- за или грамматического разбора этот блок обычно может давать пол- ное синтаксическое описание объекта в терминах грамматических единиц или дерева грамматического разбора, если представление объекта синтак- сически правильно. В противном случае объект либо исключают из рассмотрения, либо анализируют на основе других заданных грамма- тик, которые, быть может, описывают другие возможные классы рас- сматриваемых образов.
Простейшей формой распознавания является, по-видимому, «срав- нение с эталоном». Цепочка непроизводных элементов, представляющая исходный объект, сравнивается с цепочками непроизводных элементов, представляющих каждый эталонный образ. Из этих образов выбирается тот, который наиболее «согласован» или «близок» к исходному объекту в соответствии с некоторым заданным критерием. При этом иерархиче- ская, структурная информация игнорируется. С другой стороны, при полном грамматическом разборе цепочки, представляющей исходный объект, исследуется полное структурное описание. Между этими крайностями существует ряд промежуточных подходов. Например, мо- гут быть сконструированы последовательности тестов для проверки на- личия определенных подобразов либо определенных комбинаций подобра- зов (или непроизводных элементов). Результаты тестов, полученные, на- пример, с помощью просмотра таблицы, дерева решений или логических операций, используются для классификации. Каждый тест может быть схемой сравнения с эталоном или грамматическим разбором поддерева, представляющего подобраз. Выбор подхода зависит от задачи. Если для распознавания требуется полное описание объекта, то необходим грамма- тический разбор. В противном случае можно обойтись без полного грам- матического разбора и для увеличения эффективности использовать более простые подходы.
Для того чтобы получить грамматику, описывающую структурную информацию класса образов, необходимо устройство вывода грамматики, позволяющее восстановить ее по заданному множеству объектов в виде, подобном языковому. Функции этого устройства аналогичны процессу
«обучения» в дискриминантных системах распознавания образов.

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

Теорема 1. Пусть преобразование Фурье функции f(t) равно нулю вне интервала
W
W



ω
. Тогда f(t) может быть точно восстанов- лена по ее значениям, взятым на расстоянии, не большем, чем
(1/2)W, друг от друга.

Теорема 2. Пусть преобразование Фурье функции
f (х,у) равно нулю вне ограниченной области
В частотной плоскости. Пусть далее
(а,b) и (с,d) – такие точки, что для любых двух пар целых чисел
(т,п) и (р,q) множества, получаемые путем сдвига В на величи- ны
(т(а + с)), (п(b + d)) и (р(а + с)), (q(b + d)) соответственно не имеют общих точек. Пусть также
(s,t) и (и,v) таковы, что
аs + bt = си + dv = 2
π
, аи + bv = сs + dt = 0. Тогда функция f(х,у) может быть точно восстановлена по ее значениям в отсчетных точках
(hs + ku, t + kv), где h и k – целые числа.
На практике обычно преобразование Фурье функции вне интервала
(W, W) близко к нулю. Поэтому в результате восстановления функции по отсчетам будет получена лишь ее аппроксимация.
Другим видом аппроксимации является квантование. В этом случае дей- ствительное значение функции аппроксимируется с использованием конеч- ного множества значений, называемых уровнем квантования. Проще ис- пользовать равномерно расположенные уровни квантования. Однако ино- гда неравномерно расположенные уровни квантования предпочтительнее.
Предположим, например, что на изображении уровни яркости в опре- деленном диапазоне встречаются чаще, чем в других диапазонах. В этом случае может оказаться удобным использовать уровни квантования, рас-
12
положенные в этом диапазоне плотнее, чем в других. В результате увели- чится средняя точность квантования без увеличения числа исполь- зуемых уровней. Точки отсчета или уровни квантования не обязатель- но должны быть заданы заранее. Их выбор может зависеть от природы ап- проксимируемых объектов. В этом случае, конечно, потребуется более сложная схема дискретизации или квантования. После дискретизации и квантования объекта уровень квантования в каждой точке отсчета коди- руют. Пусть
m – число возможных уровней квантования. Тогда для пред- ставления любого заданного уровня необходимо по крайне мере
би-
m
2
log тов информации. Если вероятность появления каждого из возможных уровней известна заранее, то можно построить более эффективный код, сни- зив среднее число бит на один уровень. Основная идея построения таких кодов состоит в том, чтобы использовать короткие коды для наиболее часто встречающихся уровней квантования.
2. Фильтрация, восстановление и улучшение

Для того чтобы «отфильтровать» объект с целью обнаружения в нем за- данной конфигурации (сравнение с эталоном) или «восстановить» перво- начальный объект, который был испорчен в результате аппроксимации или выполнения других операций подобного рода, можно использовать опера- ции, инвариантные к времени и к изменению положения (т. е. инвари- антные к сдвигу). Эти операции используются также для повышения каче- ства посредством «сглаживания» или, наоборот, «повышения контраста».
Пусть
F – множество функций, каждая из которых задает объект, а
Т – операция переноса (сдвига) во времени или пространстве, опреде- ленная на F. Операция называется инвариантной по отношению к из- менению момента времени (или к изменению положения в пространст- ве), если она коммутирует с любой операцией
Т во времени (или в про- странстве). Иными словами,
))
(
(
))
(
(
f
T
f
T
ϕ
ϕ
=
для всех
F
f
∈ .
Такие операции обладают тем свойством, что их действие на значение функции в любой данный момент времени, или в любой точке простран- ства, не зависит от этого момента и от положения этой точки. К этой кате- гории относятся операции сдвига, точечные операции (
( )
f
ϕ
в точке за- висят только от значений функции f в этой точке) и локальные операции
(
( )
f
ϕ
в точке зависят только от значений функции f в некотором интер- вале или окрестности этой точки). Типичными примерами линейных операций, инвариантных по отношению к изменению момента времени или положения служат одномерное или двумерное преобразование
Фурье, передаточная функция. В результате вторичного преобразования
Фурье будет получено повернутое исходное изображение.
13

В двумерном непрерывном случае результат операции
( )
f
ϕ
можно представить в виде свертки двух функций f и g
( ( , ))
(
,
) ( , )
* .
f x y
g x u y v f u v dudv
f g
φ
φ
φ
∞ ∞
−∞ −∞
=


=
∫ ∫
Функция
называется импульсной функцией рассеивания операции
ϕ
g
ϕ
Часто необходимо определить, насколько точно два объекта согласу- ются друг с другом (насколько они похожи), или обнаружить сходство од- ного объекта с частью другого. Подсчет взаимной корреляции между дву- мя функциями f и g служит одним из простых методов установления иден- тичности двух объектов с точностью до переноса и умножения их на кон- станту. Этот метод может быть очень полезным в тех задачах распознава- ния образов или их непроизводных элементов, в которых легко задать про- типы или эталоны этих образов. При этом задача распознавания сводится к подсчету взаимной корреляции исходного объекта с каждым из эталонов.
Другой способ сравнения объекта с эталоном состоит в подсчете не свертки, а произведения фурье-преобразований объектов и в дальнейшем вычислении обратного фурье-преобразования полученного произведения.
В этом случае операция сравнения определена не на оси времени или в пространстве, а в области частот или пространственных частот.
Для подавления присутствующего в объекте шума часто применяют операцию сглаживания. Сглаживание можно осуществить простой заменой значений функции в каждой точке средним значением, взятым по некото- рой окрестности этой точки.
3. Сегментация
Определение 4. Сегментация – это разбиение изображения на фраг- менты. Универсального метода сегментации изображения на фрагменты не существует. В зависимости от характера требуемого описания могут быть полезны разные типы фрагментов изображения. Основным мето- дом ограничения какого-либо фрагмента является применение к данно- му изображению пороговой операции. Фрагменты можно определить при помощи простого сравнения самого изображения с порогом. Фраг- ментом может быть совокупность точек, яркость которых больше или, наоборот, меньше порога, или лежит между двумя пороговыми значе- ниями. Например, в задаче распознавания знаков или рисунков, состоя- щих из линий, сами эти знаки или рисунки представлены совокупностью
«черных», а бумага или фон – совокупностью белых точек. При помощи простой пороговой операции можно отделить черную фигуру от белого фона. Пороговую операцию можно комбинировать с другими операция- ми предварительной обработки, например с сглаживанием, подчеркива- нием и с согласованной фильтрацией.
14

Существенная трудность, возникающая при использовании пороговой операции, состоит в выборе значения порога. Иногда можно найти удач- ный порог в результате исследования распределения яркостей точек изо- бражения. Например, если известна приблизительная площадь желаемого фрагмента, то можно выбрать нижний (или верхний) порог так, чтобы площадь фрагмента, в точках которого яркость превосходит порог, была меньше (или больше) предсказанной доли площади всего изображе- ния (метод процентилей). В других случаях, когда, например, требуемый фрагмент содержит точки другого интервала яркости, чем остальные точки изображения, распределение яркости обычно имеет пик, соответствующий яркости фрагмента. Тогда для выделения фрагмента нужно выбрать поро- ги, соответствующие локальным минимумам распределения, расположен- ным по обе стороны от этого пика (метод моды). Другой метод определе- ния порога состоит в последовательной проверке точек на их принадлеж- ность к фрагменту. Этот метод позволяет варьировать значение порога в зависимости от характера уже проверенных точек. Разумеется, результат такой процедуры зависит от того, какая последовательность будет выбрана.
Другой подход к задаче выделения фрагментов состоит в прослежива- нии границ (или контуров). При обработке изображений знаков и вообще рисунков применение метода отслеживания границ позволяет не только выделять фрагменты, но и получать информацию о форме изображений.
Простой способ отслеживания границ на двухградационном изображении состоит в систематическом просмотре до тех пор, пока не встретится пара точек или клеток растра разной яркости. Предположим, что в процессе движения вдоль границы между белыми (скажем, слева) и черными (спра- ва) клетками, достигается «распутье» следующего типа:
Тогда в зависимости от значений яркостей х и у «следующая» гранич- ная точка выбирается в соответствии с правилом где 0белое, а 1 – черное. Эта процедура позволяет отслеживать связные области черных клеток в направлении часовой стрелки. Ее можно обобщить на случай полутоновых изображений, если задать критерий существования границы. Таким критерием может быть, например, наличие соседних клеток, разница яркостей которых превышает некоторый порог. Отслеживать
15

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

17
Как показано на рис. 5, множества точек (l, m), находящихся на расстоянии от заданной точки (i, j), не меньшем порога r, имеют разную форму в зависимости от вида функции расстояния. Множество точек, на ко- торых достигается локальный максимум образуют остов. Нахождение осто- вов – один из подходов к решению задачи утоньшения. Остов также исполь- зуют для получения информации о форме фрагментов. На изображениях можно выделять фрагменты по заданной форме или заданному направ- лению. Фрагменты рисунка выделяют при помощи маркировки то- чек символами, обозначающими приблизительное направление кри- вой, проходящей через точку. Для сегментации кривой или границы, или края выделяют точки расчленения (позиционные экстремумы, точки пере- гиба). Для дальнейшего описания выделенного фрагмента изображения вычисляют его параметры. Эти параметры могут быть выражены числами
(функции) или логическими высказываниями (предикаты).
Рис. 5. Расстояние от клетки (i,j) : ромб, r = 2; квадрат, r = 2; восьмиугольник,
R = 2
Языки описания образов
1. Выбор непроизводных элементов
Первый этап построения синтаксической модели образов состоит в определении множества непроизводных элементов, при помощи которых можно эти образы описать. Это определение существенно зависит от природы образов, от специфики рассматриваемой области применения и от характера доступных технологических средств. Общего решения про- блемы выбора непроизводных элементов пока не найдено. Обычно при этом выборе стараются выполнить следующие требования:
1.
Непроизводные элементы должны служить основными элементами образов и обеспечивать адекватное и сжатое описание исходных данных в терминах заданных структурных отношений (например, отношение конкатенации).
2.
Поскольку структурная информация в непроизводных элементах не важна, и они считаются простыми и компактными образами, их выде-
ление и распознавание должны легко осуществляться существующими несинтаксическими методами.
Для речевых образов и для отношения конкатенации «хорошим» множеством непроизводных элементов считают совокупность фонем. Для описания рукописного текста в качестве непроизводных элементов было предложено использовать штрихи. Однако вообще для изображений не найдено «универсальных» элементов, аналогичных штрихам в рукопис- ном тексте и фонемам в речи. В ряде случаев для обеспечения адекватно- го описания образов требуют, чтобы непроизводные элементы содержали информацию, важную для данного конкретного приложения. Например, если в задаче распознавания важен размер, или форма, или положение, то в не- производных элементах должна быть информация о размере (форме или по- ложении), чтобы классы объектов были различимы при любом методе ана- лиза описаний. Разные постановки задачи, даже при одних и тех же исход- ных данных, обуславливают выбор разных непроизводных элементов.
Пример.
Пусть необходимо отличать прямоугольники (разного раз- мера) от не прямоугольников. Тогда выбирают следующие непроизвод- ные элементы:
a′ – горизонтальный отрезок;
b′ – вертикальный отрезок;
c′ – горизонтальный отрезок;
d ′ – вертикальный отрезок.
Множество всех прямоугольников (разного размера) можно представить одним предложением или цепочкой abcd ′ .
Если задача состоит в различении прямоугольников разного размера, то это описание не годится. В этом случае в качестве непроизводных элементов нужно выбрать отрезки единичной длины:
Тогда множество прямоугольников разного размера можно описать при помощи языка:
{
}
,...
2
,
1
,
/
=
=
m
n
d
c
b
a
L
m
n
m
n
Требование (2) часто вступает в противоречие с требованием (1), по- скольку выбранные в соответствии с (1) непроизводные элементы не всегда легко распознать при помощи соответствующих методов. С другой стороны, в соответствии с требованием (2) можно выбирать довольно сложные не-
18
производные элементы, лишь бы они были доступны распознаванию.
Чем сложнее непроизводные элементы, тем проще могут быть структур- ные описания, т. е. они могут укладываться в рамки простых грамматик. В реализации распознающей системы достижение компромисса между ука- занными требованиями может стать весьма важной задачей.
2. Выделение непроизводных элементов на границах
Множество непроизводных элементов, которые обычно используют для описания границ и остовов, получают по схеме цепного кодирования, предло- женной Фрименом. На двумерное изображение накладывают прямоугольную сетку, и узлы сетки, которые наиболее близки к точкам изображения, соеди- няют отрезками прямых. Каждому такому отрезку в соответствии с наклоном присваивают восьмеричное число. Таким образом, изображение представляет- ся цепью (последовательностью) или цепями восьмеричных чисел.
На рис. 6 показано множество начальных элементов и кодовая цепочка, описывающая кривую. Эта схема обладает рядом полезных свойств.
Например, поворот изображения на угол, кратный 45°, сводится к прибав- лению восьмеричного числа (сложение по модулю 8) к каждому числу це- почки. Конечно, при этом изображение может исказиться. Только поворот на угол, кратный 90°, никогда не приводит к искажениям изображения. Из- меняя зернистость сетки, накладываемой на изображение, можно полу- чить любое желаемое разрешение. Этот метод не ограничен изображения- ми с односвязными замкнутыми границами. Его можно применять для опи- сания произвольных двумерных фигур, составленных из прямых и кривых линий и отрезков.
19
Рис. 6. Цепной код Фримена. Непроизводные элементы и кодовая цепочка
кривой 7600212212



Языки и порождающие грамматики
Допустим, что рассматриваемая задача выделения непроизводных элементов может быть удовлетворительно решена. Следующий шаг со- стоит в построении грамматики, порождающей язык для описания ис- следуемых образов. При построении структурного описания объекта, т. е. при порождении соответствующего языка в рамках выбранной или заданной грамматики, исходным элементом служит начальный символ I, входящий в множество вспомогательных символов W. Правило, принад- лежащее набору правил R данной грамматики, позволяет преобразовать начальный символ I в цепочку символов, например,
aA
I

, где
V A
a

∈ ,
W
, что соответствует замене символа I символами аА. Некото- рые символы этой цепочки могут входить в множество вспомогательных символов W, а другие – принадлежать множеству непроизводных эле- ментов V. Вспомогательные символы, входящие в преобразованную це- почку, могут снова подвергнуться преобразованиям в соответствии с правилами грамматики, а вспомогательные символы, появляющиеся в цепочках, полученных в результате очередного преобразования, подвер- гаться преобразованиям и т. д. Предложение (язык) считается сформи- рованным, если представляющая его цепочка содержит только непроиз- водные элементы.
Более строго, порождающая грамматика G есть четверка
G = (V,W,I,R),
где V – множество непроизводных элементов;
W – ожество вспомогательных символов;
I – начальный символ (
W
I
∈ );
R – конечное множество правил вывода или правил подстановки.
Язык, порождаемый грамматикой G, есть
{
}
x
I
что
цепочка
такая
x
V
x
x
G
L



=
,
,
/
)
(
Считается, что порождающая грамматика неоднозначна, если суще- ствует цепочка
)
(G
L
x

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



20

Пример 1
.
}
,
,
{
},
,
,
{
)
,
,
,
(
_
B
A
S
W
c
b
a
V
при
R
S
W
V
G
=
=
=
)
(
:
0 0
е
предложени
пустое
S
S
aB
aaA
aB
Bb
bB
Bbcc
Ac
bA
Ab
aAbc
S
R







Эта неограниченная грамматика порождает предложение вида
2 2
+
+
=
n
n
n
c
b
a
x
, где
0 означает длину цепочки символов. Например,

n
для порождения цепочки х = bbсс мы применим первые четыре правила и затем последнее, т. е. S => аАbс => аbАс => аbВbсс => аВbbсс => bbсс.
Последнее правило допустимо лишь в неограниченных грамматиках.
Грамматики типа 1
(грамматики непосредственно составляющих) харак- теризуются правилами вида
2 1
2 1
βα
α
α
α

A
, где
W
A
∈ . Эта грамматика допускает замещение вспомогательного символа А цепочкой толь-
+
V
β
ко в том случае, если А появляется в контексте
2 1
α
α
A
, составленном из цепочек
*
2 1
V
и

α
α
,...})
,
, ab
aa
,
,
,
,
,
{
},
,
{
(
0
*
ba
b
a
b
a
S
V
то
b
a
V
=
=
{
,...}
,
,
V
ba
ab
aa
=
+
Пример 2
}
,
,
{
},
,
,
{
)
,
,
,
(
_
B
A
S
W
c
b
a
V
при
R
S
W
V
G
=
=
=
abc
S
R

:
aAbc
S

bA
Ab

Bbcc
Ac

Bb
bB

aaA
aB

aa
aB

порождает предложение вида
n
n
n
c
b
a
x
=
, где
1

n
Грамматики типа 2
(бесконтекстные грамматики) характеризуются правилами подстановки вида
β

A
, где
,
A W
V
β
+


Само название «бес- контекстная» указывает на то, что переменная А может замещаться цепоч- кой
β
независимо от контекста, в котором появляется А.
Пример 3.
Бесконтекстная грамматика
G
}
{
},
,
{
)
,
,
,
(V W S R при V
W
b
a
S
=
=
=
abc
S
R

:
aSb
S

порождает цепочки вида
n
n
b
a
x
=
, где
1

n
21

Другим методом описания вывода в бесконтекстной грамматике явля- ется использование деревьев вывода. Дерево вывода для бесконтекстной грамматики G = (V,W,S,R) может быть построено следующим образом.
1)
Каждая вершина дерева имеет в качестве метки символ из алфавита
W и V.
2)
Корень дерева имеет метку S.
3)
Если вершина с меткой А имеет хотя бы одну подчиненную верши- ну, то
W
A
∈ .
4)
Если вершины
r
n прямо подчинены вершине n (с меткой А)
n
n
,..,
,
2 1
и помечены (слева направо)
k
A , то правило
k
A
A
должно
A
,...,
1
A
1

R

Пример 4.
N = 2
Грамматики типа 3
(автоматные или регулярные) – это грамматики с правилом подстановок вида
aB
A

или
a
A
→ , где
,
A B W

Альтерна- тивными допустимыми правилами подстановки являются
Ba
A

и
A
a
→ . Выбор одного из этих двух типов правил исключает, однако, при- менение правил другого типа.
Пример 5.
Регулярная грамматика
G
}
{
},
,
{
)
,
,
,
(V W S R при V
W
b
a
S
=
=
=
a
S
R

:
b
S

b
S
→ порождает цепочки из а и b.
Из определений четырех типов грамматики ясно, что каждая автомат- ная грамматика является бесконтекстной, бесконтекстная грамматика – грамматика непосредственно составляющих, а грамматика непосредствен- но составляющих принадлежит типу 0.
При описании образов цепочками используется лишь одно отноше- ние – конкатенация. Это означает, что каждый подобраз или непроизвод-
22
ный элемент можно сочленять с остальными только один раз слева.
Для описания двухмерных или трехмерных образов это одномерное отно- шение недостаточно эффективно. Естественно применить более общий формализм, включающий другие полезные отношения.
Пусть R – множество n-арных отношений (n > 1). Тот факт, что непро- изводные элементы удовлетворяют отношению
n
x
x
x
,...,
,
2 1
R
r

обозна- чают через
)
,...,
n
x
,
(
2 1
x
x
r
Например, запись ТРЕУГОЛЬНИК (а, b, с) означает, что три отрезка линии а, b, с, удовлетворяют тренарному отношению ТРЕУГОЛЬНИК, а запись НАД (Х, Y) означает, что элемент X находится над элементом Y.
Рассмотрим пример, иллюстрирующий применение этого формализма к описанию образов.
Пример 6.
Математическое выражение (а+b)/с может быть описано предложением : НАД ( НАД ( СЛЕВА (а , СЛЕВА (+, b)), – ), с), где запись СЛЕВА (Х,Y) означает, что элемент X находится слева от элемента Y .
Для описания двумерных отношений используется и другая полезная методика, основанная на древовидных структурах.
Дерево – это конечное множество, состоящее из одного или более уз- лов, таких что

существует один выделенный узел, называемый корнем дерева;

остальные узлы разделены на m > = 0 непересекающихся мно- жеств, каждое из которых, в свою очередь, является деревом.
Эти деревья называются поддеревьями корня. Представление образа в виде дерева называется деревом образа.
Использование деревьев для описания многомерных структур до- вольно простая процедура. В сущности, любая иерархическая упоря доченная схема ведет к представлению объекта в виде дерева. Например, пусть упорядочение состоит в группировке областей, где область b нахо- дится в области а, в свою очередь находящейся в области r (рис. 7). Обозна- чив корень дерева символом r, получаем древовидную структуру:
23

Рис. 7
Обработка изображений

1. Классы изображений
Обработка изображений связана с решением таких задач, в которых и входные, и выходные данные являются изображениями. Говоря об обработ- ке изображений с помощью компьютера целесообразно выделять четыре класса изображений. Эта классификация связана не столько с природой зри- тельного восприятия изображений, сколько с подходом к их представлению и обработке.
Класс 1. Тоновые и цветные изображения
24
В класс 1 входят изображения, имеющие вид обычных телевизион- ных изображений. Они обеспечивают довольно точное воспроизведение
«реальности» и представляются матрицами с целочисленными элементами
(для обозначения последних обычно используют термины элемент изо-
бражения, пиксел, пэл). В большинстве прикладных задач эти матрицы имеют очень большие размеры (512*512), являющиеся наиболее обще- принятыми. В связи с этим представлением матрицы не всегда хранятся в памяти в виде обычных матриц – часто используются более изощренные разновидности структур данных. Цветные изображения могут представляться либо при помощи трех матриц (для красного, зеленого и синего цветов), либо с помощью одной матрицы таким образом, что отдельные биты каждого элемента представляют различные цвета. Поскольку человеческий глаз обычно не в состоянии различать уровни освещенности, отличающиеся друг от друга менее чем на 1 % , то для представления цветного изображения дос- таточно затрачивать по одному байту на цвет на пиксел. Но приемлемых ре- зультатов удается добиться, используя по 3 бита для передачи каждого из двух цветов, и 2 бита для передачи третьего так, что в конечном счете для хранения изображения в памяти затрачивается лишь по одному байту на пиксел. С математической точки зрения иногда удобнее рассматривать цвет- ные изображения как матрицы трехмерных векторов.

25
Класс 2. Двухуровневые или представляемые в нескольких цветах
изображения
Изображение книжной страницы служит типичным примером пред- ставителя класса 2 – черно-белого изображения. Подобные изображения можно представлять матрицами, затрачивая по одному биту на элемент, а также в виде «карт», так как на этих изображениях имеются хорошо раз- личимые области одного цвета. Поэтому и объединяются в один класс изо- бражения, представленные в нескольких цветах, и двухуровневые изобра- жения, несмотря на то, что представление с затратой одного бита на элемент матрицы удачно лишь для двухуровневых изображений.
Класс 3. Непрерывные кривые и линии
Примерами изображений класса 3 служат контуры областей, сигналы и диаграммы (графики). Соответствующие данные являются последователь- ностями точек, допускающих представление через координаты (х, у). Од- нако этот метод представления довольно неэффективен, причем то же са- мое относится к представлению, основанному на использовании разностей значений координат у соседних точек. Более эффективным является пред- ставление с помощью цепных кодов, при использовании которых вектору, соединяющему две соседние точки, ставится в соответствии один символ, принадлежащий некоторому конечному множеству. Представление с по- мощью цепного кода требует затраты лишь трех битов на точку.
Класс 4. Точки или многоугольники
Изображения класса 4 состоят из множеств отдельных точек, отстоящих друг от друга столь далеко, что для их представления цепным кодом пользоваться нельзя. Вместо него следует применять матрицу, содержащую координаты (х, у). Соответствующая аппаратура отображения позволяет соединять точки прямыми или простыми кривыми. Различие между классами
4 и 3, как и между предыдущими классами, довольно неопределенное и при- обретает смысл лишь при обращении к способу, используемому для пред- ставления изображения. Для представления точек, далеко отстоящих друг от друга, можно применять и цепные коды, требующие затраты более од- ного кодового символа на точку, причем выбор одной из форм представле- ния должен основываться на характере распределения вероятностей рас- стояний между точками.
2. Ввод изображений
Изображение, представленное в аналоговой форме, необходимо преобра- зовать в некоторую числовую матрицу, прежде чем приступать к его обра- ботке на компьютере. Процесс такого преобразования называется дискрети- зацией и состоит из двух процессов: выборки и квантования. Первый из них заключается в выборе на поле наблюдения некоторого множества точек.
В каждой выбранной точке измеряются характеристики изображения, кото-

26
рые используются на всех последующих этапах обработки изображения.
Результаты полученных измерений необходимо описать конечным числом символов: соответствующая процедура называется процессом квантования.
Характеризуя плотность размещения выбранных точек, часто говорят о про- странственном разрешении, а характеризуя точность представления резуль- татов указанных измерений, о тоновом ( или цветовом) разрешении.
3. Преобразование изображений
Преобразование изображения класса 1 в изображение класса 2. Этот про- цесс называется сегментацией и обеспечивает выделение областей приблизи- тельно одинаковых цвета и/или яркости.
Преобразование изображения класса 2 в изображение класса 3. Одним из допустимых преобразований этого типа является построение (отслеживание) контура, а другим, прореживание. Первое обеспечивает отражение заданной области в некоторую замкнутую кривую, а второе – отображение области в некоторый граф, называемый остовом области.
Преобразование изображения класса 3 в изображение класса 4. Процесс такого преобразования, называемый иногда сегментацией кривых, предна- значен для отыскания критических точек контура. В случае многоугольников этими точками являются углы.
Преобразование изображения класса 4 в изображение класса 3. Это пре- образование включает процессы интерполирования, обеспечивающего про- ведение гладкой кривой через некоторое множество точек, и аппроксимации, обеспечивающей проведение гладкой кривой вблизи некоторого множества точек.
Преобразование изображения класса 3 в изображение класса 2. Если в ка- честве входной информации задается контур, то возникает задача заполнения
контура, которая часто рассматривается как задача штриховки. В последнем случае яркость или цвет некоторой области не остаются одинаковыми, а из- меняются в соответствии с определенными правилами. Если входной инфор- мацией служит остов, то для восстановления области следует использовать процедуру расширения.
Преобразование изображения класса 2 в изображение класса 1. Изобра- жение, воспроизведенное на экране в нескольких цветах, часто оказывается ущербным в эстетическом отношении, так как глаз человека легко обнаружи- вает контуры.
Задания для выполнения лабораторных работ
Лабораторная работа № 1
Задание
Разработать алгоритм и реализовать программу
«Распознавание простых геометрических фигур» (круг, квадрат, треугольник,

27
прямоугольник, эллипс) методом сравнения с эталоном.
Измерить время выполнения алгоритма.
Лабораторная работа № 2
Задание 1
Разработать алгоритм и реализовать программу
«Распознавание простых геометрических фигур» (круг, квадрат, треуголь- ник, прямоугольник, эллипс) структурным методом.
Представление фигур осуществить в виде дерева.
Измерить время выполнения алгоритма.
Задание 2
Разработать алгоритм и реализовать программу
«Распознавание простых геометрических фигур» (круг, квадрат, треуголь- ник, прямоугольник, эллипс) структурным методом.
Представление фигур осуществить в виде кода Фримена.
Измерить время выполнения алгоритма.
Задание 3
1. Сравнить результаты выполнения программы заданий 1 и 2.
2. Сравнить результаты выполнения программы лабораторных работ 1 и 2.
3. Сделать выводы.
Лабораторная работа № 3
Задание 1
Разработать алгоритм и реализовать программу
«Распознавание сложных изображений (кораблей)» структурным методом.
Представление изображений осуществить в виде кода Фримена.
Задание 2
Разработать алгоритм и реализовать программу
«Распознавание сложных изображений (кораблей)» структурным методом.
Представление изображений осуществить в виде матрицы.
Задание 3
1. Сравнить результаты выполнения программы заданий 1 и 2.
2. Сделать выводы.
По лабораторным работам сделать отчет в электронном и печатном виде.
Отчет по лабораторной работе должен содержать:
1.
Постановку задачи.
2.
Программную реализацию алгоритма.
3.
Сохраненные на переносном носителе информации файлы про- граммной реализации.
4.
Вывод о проделанной лабораторной работе.

28
Литература
1.
Фу К. Структурные методы в распознавании образов / К. Фу ; пер. с англ. Н.В. Завалишина ; под ред. М.А. Айзермана. – М. : Мир,
1977. – 319 с.
2.
Журавлёв Ю.И. Распознавание образов и анализ изображений /
Ю.И. Журавлёв, И.Б. Гуревич // Искусственный интеллект: Модели и методы. Т. 1. – М. : Радио и связь, 2000. – 310 с.
3.
Павлидис Т. Алгоритмы машинной графики и обработки изображе- ний / Т. Павлидис ; пер. с англ. Н.В. Петрова ; под ред. М.С. Гуреви- ча. – М. : Радио и связь, 1986. – 400 с.
Содержание
Введение………………………………………………………………………..3
Основные понятия распознавания образов……………………………………..3
Основные задачи, возникающие при разработке систем распознавания об- разов…………………………………………………………….……..……......4
Синтаксический подход к распознаванию образов……………………….…6
Система синтаксического распознавания образов……………………………10
Методы предобработки……………………………………………………..….12
Языки описания образов…………………………………………………….….17
Языки и порождающие грамматики……………………………………………20
Обработка изображений………………………………………….……….….24
Задания для выполнения лабораторных работ……………………………...26
Литература………………………………………………………..………..….28

29

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

СТРУКТУРНОЕ РАСПОЗНАВАНИЕ ОБРАЗОВ
Учебное пособие для вузов
Составитель:
Новикова
Нелля Михайловна
Редактор И.Г. Валынкина
Подписано в печать 14.07.08. 60×84/16. Усл. печ. л. 1,6.
Тираж 25 экз. Заказ 1047.
Издательско-полиграфический центр
Воронежского государственного университета.
394000, г. Воронеж, пл. им. Ленина, 10. Тел. 208-298, 598-026 (факс) http://www.ppc.vsu.ru; e-mail: pp_center@ppc.vsu.ru
Отпечатано в типографии Издательско-полиграфического центра
Воронежского государственного университета.
394000, г. Воронеж, ул. Пушкинская, 3. Тел. 204-133.

30

Document Outline

  • Синтаксический подход к распознаванию образов
  • Система синтаксического распознавания образов
    • Языки описания образов
      • 2. Выделение непроизводных элементов на границах
        • Обработка изображений
          • Класс 1. Тоновые и цветные изображения
          • Класс 4. Точки или многоугольники
        • Задания для выполнения лабораторных работ
    • Задание
    • Задание 1
    • Задание 2
      • Задание 3
    • Задание 1
    • Задание 2
      • Задание 3
        • Литература
        • Содержание


Поделитесь с Вашими друзьями:


База данных защищена авторским правом ©nethash.ru 2017
обратиться к администрации

войти | регистрация
    Главная страница


загрузить материал