Визуализация пространственных отношений

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

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

Визуализация пространственных отношений

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

Модель синтеза визуального представления пространственных отношений

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

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

В.Г. Гак определяет пространственное отношение в чистом виде формулой

литерный пространственный визуализация

<S, V, R, L>,

где:

S - локализуемый объект,

V - глагол,

R - конкретный тип локализации, выражаемый, например, предлогом,

L - локализатор, то есть двухмерное или трехмерное пространство, в котором способен помещаться локализуемый объект [Гак, 2000].

В задачи алгоритма синтеза визуального представления ситуации входит:

1. выявление пространственных отношений;

2. построение графического представления.

Требования к входному тексту:

описание пространственной ситуации должно быть конечно;

текст должен описывать статическую ситуацию с точки зрения неподвижного наблюдателя;

описание пространственной ситуации должно быть не противоречивым.

Грамматика входного языка:

< Текст>><S><V><R><L>.<Текст>

< Текст>><R><L><V><S>.<Текст>

< Текст>><S><R><L>.<Текст>

< Текст>><R><L><S>.<Текст>

< Текст>>е

<S>><PS><существительное>

<PS>><PS><прилагательное>

<PS>>е

<S>><местоимение-существительное>

<S>><местоименное прилагательное><PS><существительное>

<R>><AR><отношение>

<AR>><наречие><AR>

<AR>>е

<V>><глагол>

<L>><PL><существительное>

<PL>><PL><прилагательное>

<PL>>е

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

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

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

Модель синтеза визуального представления текстового описания пространственных отношений представлена на рисунке 1 в виде DFD диаграммы.

Блок «Выявление морфологических признаков» использует морфологический словарь ДИАЛИНГ. Его основные характеристики [Диалинг, 2008].

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

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

Тип лексемы:

С1 - сущ. им.

С2 - сущ. не им.

П1 - прил. им.

П2 - прил. не им.

Г - глагол

Н - наречие

П - предлог

ТЧК - знак «точка»

Рис. 1. Потоковая диаграмма алгоритма визуализации описания ситуации

Рис. 2. Граф переходов автомата выявления пространственных отношений

КСЛ - конец списка лексем

Действия:

S` - записать лексему как локализуемый объект

V` - записать лексему как глагол

V* - задать глагол по умолчанию

R` - записать лексему как пространственное отношение

L` - записать лексему как локализатор

AS` - добавить лексему в список атрибутов л-объекта

AL` - добавить лексему в список атрибутов локализатора

AR` - добавить лексему в список атрибутов отношения

ADD - добавить пространственное отношение в таблицу

Задачей блока 3 является построение семантической сети, описывающую ситуацию в виде таблицы концептов и таблицы дуг.

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

3. множеству концептов семантической сети соответствует множество объектов ситуации (локализуемые объекты и локализаторы);

4. множеству дуг семантической сети соответствует множество пространственных отношений;

5. дуга семантической сети направляется от локализуемого объекта к локализатору.

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

Для визуализации каждого пространственного отношения используется рассуждение по прецедентам:

Для оценки близости пространственного отношения <S, V, R, L> и i-того случая из БД прецедентов используется мера f:

a_i,j и f построены на основе нечеткой литерной логики (НЛЛ), описанной в [Прохоров, 2007], используемые операции НЛЛ приведены ниже.

При построении графического представления ситуации происходит геометрическая оптимизация полученной модели - ищется минимум критерия с:

где:

X - множество положений объектов сцены,

P - множество пространственных отношений сцены,

r(p_i) - расстояние между текущим положением локализуемого объекта p_i пространственного отношения и заданным в решении

O - множество объектов сцены,

d(o_i, o_j) - штрафная функция, зависящая от близости i-того и j-того объекта сцены.

Прототип системы был реализован с использованием графической библиотеки «IRRLicht».

Пример работы.

На вход подается описание ситуации «лампа стоит на столе. слева от стола стоит кресло. справа от стола стул. человек стоит за столом.».

Построенная семантическая сеть изображена на рисунке 3.

Результат работы программы приведен на рисунке 4.

Рис. 3. Семантическая сеть, описывающая ситуацию

Рис. 4. Визуальное представление ситуации

Переменная нечеткой литерной логики характеризуется двойкой

,

где U - многомерное позиционное множество символов;

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

В рамках НЛЛ к переменным могут применяться следующие операции:

- конъюнкция; - дизъюнкция; - отрицание.

При осуществлении логического вывода операции применяются слева направо, согласно приоритету: отрицание; конъюнкция; дизъюнкция.

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

Рассмотрим подробно используемые операции.

Операции дизъюнкции.

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

Входом операции является:

- переменные НЛЛ, хранящие разнородные понятия.

Выходом операции является:

- переменная НЛЛ, описывающая объединенное понятие.

Выполнение операции дизъюнкции осуществляется по алгоритму, приведенному на рисунке 5.

Рис. 5. НЛЛ, операция дизъюнкции

Операция сравнения.

Входом операции является: - переменные НЛЛ, хранящие сравниваемые понятия.

Выходом операции является: - степень соответствия понятий.

Выполнение операции дизъюнкции осуществляется по алгоритму, представленному на рисунке 6.

Рис. 6. НЛЛ, операция сравнения

Список литературы

1. Гак В.Г. Пространство вне пространства // Логический анализ языка. Языки пространств. - 2000. - №5.

2. Русский морфологический словарь Диалинг - http://aot.ru/docs/rusmorph.html.

3. Прохоров И.В. Критерии выявления слов иноязычного происхождения / Прохоров И.В., Заболеева-Зотова А.В. // Информационные технологии в науке, образовании, телекоммуникации и бизнесе (IT + S&E`07): Тез. докл. XXXIV междунар. конф., 20-30 мая 2007.

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