Структурное распознавание объектов при коммуникациях
А.В. Ганичева,
Тверская государственная сельскохозяйственная академия, г. Тверь
А.В. Ганичев
Тверской государственный технический университет, г. Тверь
Аннотации
Structural recognition of objects at communications
A.V. Ganicheva, A.V. Ganichev
Tver State Agricultural Academy, Tver
Tver State Technical University, Tver
Ключевые слова: стохастическая грамматика, цепочка (слово), стохастический язык, признак, образ
Keywords: stochastic grammar, a chain (word), stochastic language, an attribute, an image
В работе предложен новый метод структурного распознавания объектов при передаче и приеме информации с учетом структурированного и статистического характера коммуникационного процесса.
In work the new method of structural recognition of objects is offered by transfer and reception of the information in view of structured and a statistical property of communication process.
В настоящее время синтаксический (лингвистический, структурный) метод распознавания образов применяется для решения многих важных прикладных задач коммуникационных процессов (обработка изображений, рукописных текстов, иероглифов, жестов человека, речевых сигналов и т.д.). Одним из основных вопросов этого метода является структурное описание образов, что дает возможность провести аналогию между структурой объектов и синтаксисом языка. Поэтому при описании и распознавании образов можно использовать аппарат математической лингвистики (теории формальных грамматик и языков). математический лингвистика грамматика
Существуют различные подходы к проблеме структурного (синтаксического) описания и распознавания объектов (Фу, 1977: 1-319, Хант, 1978: 172-216, Фор, 1989: 182-193, Дуда, 1976: 454-463, Ту, 1978: 336-379, Горелик, 1984: 154-172, Новикова, 2008: 1-29). Используются графовые грамматики, грамматики деревьев, стохастические программные и индексные грамматики, специальные языки описания изображений, например PDL (Picture Description Language), плекс-грамматики, Веб-грамматики и другие.
Следует отметить, что хотя первые работы по структурному распознаванию появились достаточно давно и рассмотрены многие сферы его практического применения, в настоящее время теоретические вопросы построения грамматик объектов сложной формы, а также распознавание по стохастическим данным и нечеткой информации рассмотрены недостаточно полно.
В статьях (Ганичева, 1999: 64-71, Ганичева, 2000: 125-132, Ганичева, 2001: 204-226) разработан метод структурного распознавания, который продемонстрирован на примерах из информационных технологий, систем классификации образов и сложных объектов. Сущность метода заключается в рассмотрении объекта, во-первых, как соответствующее соединение содержательных частей, во-вторых, как соединение соответствующих геометрических образований на основе правил, предполагающих представление каждого плоскостного объекта и каждой его части в виде соединения левой, правой, верхней, нижней и центральной части, в том числе с учетом их размеров и нечеткой информации как о частях, так и размерах. Поскольку при описании трехмерных объектов можно использовать плоскостные изображения: вид сбоку, спереди, сзади, сверху, снизу - описанный метод можно использовать для описания и распознавания объемных объектов. Более того, предложенный метод можно применять и непосредственно для задачи распознавания трехмерных объектов, без перехода к плоскостным проекциям.
В работе (Ганичева и др., 2009: 111-120) изложен метод структурно-стохастической обработки нечеткой информации относительно объектов, их частях и размерах. В работе (Ганичев, 2011: 449-457) рассматривается новый метод структурного распознавания объектов, особенно удобный для описания, анализа и распознавания иерархических систем. Сформулированы правила метода. Построен формальный язык, порождаемый грамматикой, описывающей иерархическую систему функционирования предприятия.
Целью данной работы является разработка метода, образно говоря, "матрешечного вложения" уровней информации при коммуникациях, реализованного на основе структурно-стохастического описания этапов ее передачи и восприятия.
Рассмотрим основные понятия математической лингвистики из (Гладкий, 1973: 25-39, Патапов, 2010: 55-64).
Пусть V - непустое конечное множество символов, которое называется словарем. Произвольная конечная последовательность элементов V называется цепочкой или словом в алфавите V.
Порождающая грамматика - это упорядочная четверка Г=<>, где:
V - основной (терминальный) алфавит;
W - вспомогательный (нетерминальный) алфавит;
I - начальный символ;
R - совокупность правил ввода.
Каждое правило из R имеет вид
r =ц>ш,
причем называется левой, а - правой частью правила r.
Пусть r - правило грамматики Г и 1 2, 1 ш 2 - цепочки в словаре VW. Тогда говорят, что получается из применением правила r. Если цепочка получается из применением какого-либо правила Г, то говорят, что непосредственно выводима из в Г и используется запись .
Последовательность цепочек D= (n) называется выводом в Г, если для каждого 1i последующая цепочка непосредственно выводима из предыдущей, т.е. имеет место . Множество цепочек в основном словаре V грамматики Г, выводимых из ее начального символа, называется языком, порождаемым грамматикой Г.
Грамматика Г=<V,W,I,R> называется грамматикой составляющих или НС- грамматикой, если каждое правило имеет вид 1212, где 1 - произвольные цепочки в словаре VW, AW, - произвольная непустая цепочка в VW. Если в каждом правиле Л, где Л - пустая цепочка, т. е. цепочка, не содержащая символов, то правило называется бесконтекстным, грамматика, все правила которой бесконтекстны, называется бесконтекстной или КС-грамматикой, язык - КС - языком или бесконтекстным (контекстно-свободным).
Нетерминальный символ называется рекурсивным, если в грамматике имеется правило . Само правило при этом тоже называется рекурсивным.
Если нетерминальные символы рассматривать как отрезки заданной длины, изображенные на рисунке 1, то с помощью грамматики Г=<V,W,I,R> при W=, V= и множестве правил можно получить три описания прямоугольников одинаковой высоты "b", но разной ширины: одна условная единица (a), две условных единицы (aa), три условных единицы (aaa) (рис. 2).
Предположим, что имеется два класса образов и и пусть образы этих классов могут быть построены из признаков, принадлежащих некоторому конечному множеству. Назовем эти признаки терминальными и обозначим это множество через V. Каждый образ может рассматриваться как цепочка или предложение, поскольку он составлен из терминалов множества V.
Допустим, существует грамматика Г, такая, что порождаемый ей язык состоит из предложений (образов), принадлежащих исключительно одному из классов, например . Очевидно, эта грамматика может быть использована в целях классификации образов, так как заданный образ неизвестной природы может быть отнесен к , если он является предложением языка L(Г). В противном случае образ приписывается классу .
Процедура, используемая для определения, является или нет цепочка выводимой в данной грамматике, называется грамматическим разбором. Вывод представляет собой так называемый грамматический разбор сверху вниз, который начинается с начального символа I и состоит из последовательности подстановок правил, порождающих подходящие символы. Главной целью является вывод из I данного слова. Делается предположение, что анализируемое слово принадлежит языку данной грамматики. Поэтому на первом этапе выясняется, можно ли анализируемую цепочку свести к правой части некоторого правила
.
Это выясняется следующим образом. Применение данного правила подстановки в случае когда - основной символ, возможно, если цепочка начинается с этого символа. Если же - вспомогательный символ, ставится подзадача: можно ли какое-нибудь начало цепочки свести к . Если это оказывается возможным, таким же образом проверяется , затем и т.д. Если же для некоторого не удается найти подходящего места в выводе цепочки, то надо попробовать применить другое правило подстановки:
и т.д.
Грамматический разбор сверху вниз удобно применять для анализа цепочек, принадлежащих языку данной грамматики.
Для того чтобы показать, что данная цепочка не принадлежит языку данной грамматики, удобней использовать грамматический разбор снизу вверх, сущность которого заключается в следующем. При таком разборе цепочка свертывается до начального символа грамматики. Для этого в ней отыскиваются подцепочки, совпадающие с правыми частями правил подстановки, затем заменяются соответствующими левыми частями.
Для придания статистического характера структурным моделям каждому правилу ставится в соответствие некоторая вероятностная (или нечеткая) мера. Эта мера определяется на основе экспериментальных данных или путем экспертного оценивания. В результате получается стохастическая (вероятностная) грамматика Г=<>, где Q - множество вероятностных (нечетких) мер, заданных на множестве правил R.
Если терминальная цепочка x выводится из I применением последовательности правил т.е. и P(ri) - вероятность применения правила ri, то вероятность порождения (мера вывода) цепочки x определяется как произведение вероятностей (мер) используемых в ее выводе правил:
,
где - условная вероятность, поставленная в соответствие правилу ri при предварительном применении правил . Если имеется несколько правил с одинаковой левой частью, то сумма вероятностей применения этих правил равна единице.
Стохастический язык L(Г) - язык, порождаемый стохастической грамматикой Г.
Процесс передачи и приема информации можно рассматривать как процесс в многоуровневой иерархической системе. Начальный (нулевой) уровень соответствует начальному, самому общему представлению об образе объекта. Образно говоря, это "самая большая матрешка данных". Следующий уровень системы детализирует предыдущий, соответствует "более маленькой матрешке" по сравнению с предыдущей. Аналогию можно привести из биологии или ботаники, где рассматриваются классы, типы, виды изучаемых объектов. Каждый уровень системы описывается соответствующей последовательностью правил стохастической грамматики согласно имеющейся на данном уровне информации об образе рассматриваемого (изучаемого) объекта.
Решение: Остановимся подробнее на выборе терминальных и нетерминальных символов. Строгих правил выбора здесь нет. Но поскольку вид сбоку колонны определяется видом сбоку одного автобуса в случае идентичности автобусов, то, естественно, определить вид сбоку одного автобуса. Очевидно, вид сбоку каждого автобуса определяется стеной и находящимися на ней дверями и несколькими окнами. Предположим, что окна и двери, согласно виду сбоку и слева направо по направлению движения чередуются следующим образом: окно, дверь, несколько окон, дверь - это салон, затем дверь и окно - кабина водителя. Предположим, что нулевой уровень системы связан с представлением колонны автобусов в виде последовательности прямоугольников. Слева у каждого правила будем указывать его номер согласно порядку применения в выводе. Стена видна в промежутках между окнами и дверями, сверху над каждой дверью и окном, а также слева от левого окна и справа от правого и снизу под окнами.
Исходя из такого описания, множество терминальных (непроизводных) символов определим так:
< дверь >, < окно >, < стена >, < колесо >.
Начальное множество нетерминальных символов можно определить следующим образом: I - начальный символ, < вид сбоку>, < автобус >, <начало автобуса >, < середина автобуса >, < конец автобуса >.
Остальные символы будем добавлять к начальному списку в ходе описания объекта. Зададим начальное правило:
1. I< вид сбоку >.
Заметим, что < вид сбоку > можно интерпретировать последовательностью прямоугольников, которые соответствуют автобусам. Тогда
2. < вид сбоку >< прямоугольник > <вид сбоку >¦< прямоугольник >,
где
3. < прямоугольник >> < автобус >.
На следующем уровне конкретизируем образ автобуса при помощи правил:
4. < автобус >>< верхняя часть автобуса > < нижняя часть автобуса >.
5. < верхняя часть автобуса >>< салон автобуса > <кабина водителя >.
6. < нижняя часть автобуса >>< пустой промежуток > {< колесо > <пустой промежуток >}3,
здесь степень 3 показывает, что данная цепочка повторяется 3 раза,
7. < пустой промежуток >>.
Для описания<прямоугольника > и скомбинированных из него фигур можно использовать добавочные грамматики примеров из (А.В. Ганичева, 1999: 64 - 71).
На следующем уровне происходит конкретизация структурных составляющих вида сбоку автобуса: салона и кабины водителя. Начнем, например, анализ с описания начала салона автобуса. Начало салона автобуса можно определить состоящим из 4-х элементов (рис. 4).
Поскольку < стена> и < дверь > являются терминальными символами, то удобно< начало вагона > представить в виде конкатенации трех цепочек:
8. < начало салона >< левая часть начала салона > < правая часть начала салона >,
где
9. < левая часть начала салона >< стена >,
10. < правая часть начала салона >< стена >,
а < центральную часть начала салона > для описания <стены > и <двери > можно представить в виде:
11. < центральная часть начала салона >< верх центральной части начала салона > < низ центральной части начала салона >,
где
12. < верх центральной части начала салона ><стена >,
13. < низ центральной части начала салона ><дверь >.
Аналогично вводятся нетерминалы для описания <середины салона > (рис. 5).
Поскольку середина вагона состоит из окон, разделенных стенными промежутками, то удобно выделить повторяющейся фрагмент (на рис. 5 -заштрихованная часть), который будет воспроизводиться за счет введения рекурсивного нетерминала, т.е. если - цепочка, описывающая заштрихованный фрагмент, то середину салона можно задать правилами: