Размещено на http://www.allbest.ru/

Структурное распознавание объектов при коммуникациях

А.В. Ганичева,

Тверская государственная сельскохозяйственная академия, г. Тверь

А.В. Ганичев

Тверской государственный технический университет, г. Тверь

Аннотации

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(Г) - язык, порождаемый стохастической грамматикой Г.

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

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

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

Исходя из такого описания, множество терминальных (непроизводных) символов определим так:

< дверь >, < окно >, < стена >, < колесо >.

Начальное множество нетерминальных символов можно определить следующим образом: 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 -заштрихованная часть), который будет воспроизводиться за счет введения рекурсивного нетерминала, т.е. если - цепочка, описывающая заштрихованный фрагмент, то середину салона можно задать правилами:

14. <середина салона > <середина салона >¦ .

Заштрихованный фрагмент можно задать в виде конкатенации

15. <левая часть > <правая часть >, где

16. <правая часть><стена >,

17. <левая часть> <верх левой части > <центр левой части > <низ левой части >, причем

18. <верх левой части ><стена >,

19. <центр левой части ><окно >,

20. <низ левой части ><стена >.

Из анализа рисунков 4, 5 следует, что конец салона должен иметь вид, изображенный на рис. 6.

Поэтому <конец салона > удобно описывать в виде конкатенации:

21. < левая часть конца вагона > < середина конца вагона > < правая часть конца вагона >,

где

22. < левая часть конца салона > < стена >,

23. < середина конца салона >< верхняя часть > < нижняя часть >,

24. < верхняя часть >< стена >,

25. < нижняя часть >< дверь >,

26. < правая часть конца салона >< стена >.

Наконец, < кабину водителя > можно представить в виде (рис. 7)

27. < кабина >< конец кабины > < начало кабины >,

где

28. < конец кабины >< стена >,

29. < начало кабины >< 1-я часть > < 2-часть > < 3-я часть > < 4-я часть> (рис. 7).

На рис. 7 цифрами обозначены части < начала кабины >.

Здесь < 1-я часть > - это < дверь > и < стена сверху >, < 2-я часть >- < стена>,

< 3-я часть > - это < окно >, а сверху и снизу - < стена >, наконец < 4-я часть> - это < стена >.

Следовательно, <начало кабины> можно задать следующей последовательностью правил:

30. < 1-я часть >< дверь > < стена >

31. < 2-я часть >< стена >,

32. < 3-я часть >< низ > < середина > < верх >,

33. < низ >< стена >,

34. < середина >< окно >,

35. < верх >< стена >,

36. < 4-я часть >< стена >.

Построенная грамматика представляет собой КС - грамматику.

Таким образом, имеем трехуровневую систему представления вида сбоку колонны однотипных автобусов. Каждый уровень соответствует своей "матрешке" и описывается последовательностью правил грамматики. Допустим колонна состоит из 4-х автобусов и вид сбоку салона характеризуется шестью окнами между дверьми. Тогда нетрудно видеть, что каждый вывод цепочки x, описывающей данную колонну будут определять 36 правил данной грамматики, причем правило 14, соответствующее описанию шести окон в салоне будет применяться 6 раз, и правило 2, характеризующее колонну 4-х автобусов, применяется 4 раза. Поэтому общее количество цепочек вывода одного автобуса будет равно 41, а для 4-х автобусов соответствующий вывод будет содержать цепочек, т.к. правила 1 и 2 - общие, причем правило 2 повторяется 4 раза.

В случае нечеткой информации каждому правилу сопоставляется вероятность (или мера нечеткости) . Для всех правил построенной грамматики, кроме правил 2 и 14, правая часть правил однозначно определяется по левой. Поэтому согласно определению стохастической грамматики , кроме и . Пусть, например, при правой части равна 0,1, тогда для правой части < середина салона > будет равна 0,9. Значит вероятность (мера нечеткости) порождения рассмотренной цепочки x для одного автобуса будет равна , а для колонны из четырех автобусов эта вероятность фактически равна нулю. И это понятно, т.к. построенная грамматика порождает колонны любого количества автобусов и окон в салонах. Поэтому вероятность порождения каждой фиксированной колонны в общем случае очень маленькая, фактически равная нулю.

Если заменить правило 2 на правила:

<вид сбоку ><прямоугольник > <вид сбоку 1>,

<вид сбоку 1><прямоугольник ><вид сбоку 2>,

<вид сбоку 2 ><прямоугольник > <вид сбоку 3>,

<вид сбоку 3 ><прямоугольник >,

а правило 14 на соответствующие 6 правил

<середина салона >< середина салона 1 >,

<середина салона i >< середина салона i+1 >, ,

<середина салона 5 >,

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

Любая цепочка непрямоугольного вида не является цепочкой, порождаемой данной грамматикой. В самом деле, данная грамматика устроена таким образом, что сначала всегда применяются начальные правила 1-4. Участвующие в этих правилах нетерминалы несут соответствующую смысловую нагрузку. А поэтому описываемый объект должен состоять из нескольких идентичных прямоугольников. Внутреннее строение каждого прямоугольника зависит от определенной последовательности дверей и окон, которая описывается соответствующими правилами грамматики, которые не предусматривают никакое другое внутреннее строение, например типа вариантов, изображенных на рис. 8.

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

Литература

1. Дуда Р., Харт П. Распознавание образов и анализ сцен. - М.: Мир, 1976. - 118 с.

2. Ганичева А.В. Некоторые примеры структурного распознавания образов. - Деп. В ЦСИФ, выпуск 54, серия Б, №B 48, 2000.

3. Ганичева А.В. Об одном методе структурного распознавания сложных объектов. - Тверь: ТФ МЭСИ. Сборник научных трудов, 2001.

4. Ганичева А.В. Применение структурного метода в информационных технологиях. - Тезисы научно-методической конференции. - Тверь, ВА ПВ, 1999. - С. 19 - 23.Фу К. Структурные методы в распознавании образов. - М: Мир, 1977. - 511 с.

5. Ганичева А.В., Ганичев А.В., Виноградов Г.П. Структурное распознавание сложных объектов на основе стохастических грамматик (статья). Третья Всероссийская научная конференция "Нечетные системы и мягкие вычисления". Сборник статей, том II, Волгоград, 2009.

6. Ганичев А.В. Структурный метод описания иерархических систем. В мире научных открытий, № 8, 2011. - С. 15 - 17.

7. Гладкий А.В. Формальные грамматики и языки. - М.: Наука, 1973. - 215 с.

8. Горелик А.Л., Скрипкин В.А., Методы распознавания. - М.: Высшая школа, 1984. - 315 с.

9. Новикова Н.М. Структурное распознавание образов. Учебное пособие. - Воронежский государственный университет: Издательско-полиграфический центр, 2008. - 135 с.

10. Патапов А.С. Технологии искусственного интеллекта. - СПб: СПбГУ ИТМО, 2010. - 195 с.

11. Ту Дж., Гонсалес Р. Принципы распознавания образов. - М.: Мир, 1978. - 255 с.

12. Фор А. Восприятие и распознавание образов. - М.: Машиностроение, 1989. - 155 с.

13. Хант Э. Искусственный интеллект. - М: Мир, 1978. - 215 с.

1. Duda R., Hart P. Pattern recognition and scene analysis. - New York: Wiley, 1976. - 118 p.

2. Ganicheva A.V. Some examples of structural pattern recognition. - Dep. In CSIF, Issue 54, Series B, № B 48, 2000.

3. Ganicheva A.V. On a method of structural recognition of complex objects. - Tver: TB MIES. Collection of Scientific Papers, 2001.

4. Ganicheva A.V. Application of the structural method in information technology. - Abstracts of scientific conference. - Tver, MA AD, 1999. - p. 19-23. Fu K. Structural methods in pattern recognition. - Moscow: Mir, 1977. - 511 p.

5. Ganicheva A.V., Ganichev A.V., Vinogradov G.P. Structural recognition of complex objects based on stochastic grammars (article). Third All-Russian Scientific Conference "Odd Systems and Soft Computing." Collected papers, Volume II, Volgograd, 2009.

6. Ganichev A.V. Structured method of describing hierarchical systems. In the world of scientific discoveries, № 8, 2011. - p. 15-17.

7. Gladkiy A.V. Formal grammars and languages??. - Moscow: Nauka, 1973. - 215 p.

8. Gorelik A.L., Skripkin V.A. Recognition methods. - Moscow: Higher School, 1984. - 315 p.

9. Novikova N.M. Structural pattern recognition. Textbook. - Voronezh State University: Publishing center, 2008. - 135 p.

10. Patapov A.S. Artificial intelligence technology. - St. Petersburg: St. Petersburg State University of Information Technologies, 2010. - 195 p.

11. Tu, J., Gonzalez R. Principles of pattern recognition. - New York: Wiley, 1978. - 255 p.

12. Fort A. Perception and pattern recognition. - M.: Mechanical Engineering, 1989. - 155 p.

13. Hunt E. Artificial Intelligence. - Moscow: Mir, 1978. - 215 p.

Размещено на Allbest.ru