Введение

Содержание данной статьи – это развитие темы, представленной предыдущей публикацией автора в настоящем журнале – статьей «Использование интерфейса логического и визуального программирования для анализа изображений геометрических тел» [1]. В указанной публикации обосновывалась актуальность «интеллектуальной» задачи анализа полученных с видеокамеры растровых изображений предметов, находящихся  в поле зрения промышленного робота-манипулятора, целью которого являются: выбор нужного предмета; оценка его размера; его расположения относительно других предметов и планирование своих действий по захвату и переносу этого предмета.

В указанной публикации, в частности, обосновывалась возможность использования совместного применения логического программирования (язык Пролог) и визуального программирования (язык Visual Basic) для анализа совокупности изображений геометрических тел с плоскими гранями.

Были описаны важные этапы анализа, начиная с этапа преобразования тонового (растрового) изображения в векторное изображение (рисунок 1), и заканчивая этапом логического анализа векторного изображения, в результате которого на изображении выявляется точное число тел с рядом характеристик (рисунок 2).

 

Рисунок 1. Пример «картинки», полученной в ходе преобразования растрового изображения в векторное. Показаны номера всех выявленных граней.

 

Рисунок 2. Результат анализа изображения,  представленного на рисунке 1.

 

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

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

координаты условных «центров» выявленных тел (координаты центров прямоугольников, в каждый из которых вписаны изображения всех граней одного многогранника);

условные «размеры» выявленных тел в единицах, пропорциональных площадям указанных в предыдущем пункте (2) прямоугольников;

«объективное» значение цвета каждого тела как значение функции Argb, аргументы которой вычислены как средние значения этой функции для всех граней этого тела, а также «субъективное» значение лингвистической переменной Цвет (red, green и т.д.).

В публикации [1] был представлен сформулированный автором «логико-визуальный» подход к решению задачи анализа изображений геометрических тел с плоскими гранями. Главной составляющей такого подхода является синтаксический (структурный) метод на базе логического программирования [2, 3, 4], которое является частным случаем более широкой парадигмы декларативного программирования [5], принципиально отличной от традиционной парадигмы императивного (операторного) программирования. Рассмотренная в упомянутой публикации задача анализа изображений геометрических тел может служить достаточно ярким примером задач указанного класса. Поэтому, полученные автором результаты по созданию демонстрационного прототипа «интеллектуальной» составляющей системы анализа изображений геометрических тел могут служить хорошей основой для усвоения навыков практического применения декларативного подхода к программированию многих задач искусственного интеллекта [6, 7].

Как было отмечено в публикации [1], опыт использования языков функционального и логического программирования для решения задач символьной обработки привел к пониманию необходимости визуализации результатов решения многих практических задач этого класса. Без визуализации интерпретация этих результатов бывает крайне затруднительной. Для решения проблемы визуализации автором был предложен интерфейс двух языков программирования – языка логического программирования (Пролог) и визуального императивного языка программирования (Visual Basic), точнее, двух систем программирования для указанных языков [8, 9]. Язык Пролог используется для решения основной, «интеллектуальной» части задачи. Язык Visual Basic используется для проведения вычислений, дополняющих логический вывод, а также для формирования наглядного представления результатов этого вывода.

Разумеется, большая доля сведений, которые необходимы «интеллектуальному роботу» для решения задач планирования своих действий, не содержатся в тех результатах, пример которых показан на рисунке 2. Их «видит» человек, но они не «видны» роботу, так как он не обладает метазнаниями, которыми обладает человек. Например, знаниями о взаимном расположении тел, которые могут быть очень важными при принятии решений о захвате нужного предмета (при необходимости его переноса на новое место). Предмет может быть «завален» другими предметами, которые необходимо убрать, чтобы добраться до нужного предмета. И т.д. Например, для захвата и переноса зелёного «ящика» на рисунке 1, необходимо освободить его от покоящегося на нём предмета – пирамиды синего цвета. При этом, робот «знает» лишь то, что пирамид на рисунке две; что одна из них серая, размер её меньше, чем размер другой, синей пирамиды, и что она помещена на самый левый предмет. Разумеется, для решения этой простой для человека задачи роботу надо, как ребёнку, кое-что объяснить – в частности, научить его элементарным приёмам дедукции. В частности, делать такие, например, выводы: «из того, что обе пирамиды разного цвета; серая пирамида находится на красном объекте; зелёный ящик служит опорой для большей пирамиды,  следует, что для освобождения зелёного ящика следует убрать с него синюю пирамиду».

В настоящей статье описана попытка дополнения системы анализа изображений указанного класса, представленного в предыдущей статье, компонентом обучения. Обучение предполагается в режиме общения с человеком – «учителем», который на ограниченном естественном языке интерпретирует полученные на предыдущем этапе результаты.

Например, относительно изображения, показанного на рисунке 1, «учитель» может на ограниченном естественном языке (ОЕЯ) ввести в базу данных логической части программы анализа изображений (на языке логического программирования Пролог) следующие  утверждения:

Big blue pyramid is on the green box. (Большая синяя пирамида находится на зелёной коробке.)

Little grey pyramid is on the red object. (Маленькая серая пирамида стоит на красном предмете.)

Large object is to the right and behind the small object. (Большой объект расположен справа и позади маленького объекта.)

Big green object has the rectangular notch. (Большой зелёный объект имеет выемку.)

A red object does not have specificity. (Маленький красный объект не имеет особенностей.)

All four bodies highlighted on the right. (Все четыре тела освещены справа.)

And the like. (И тому подобное.)

После ввода указанных фраз на ОЕЯ в виде списков Пролога, представляющих анализируемые цепочки языка, происходит их синтаксический анализа в соответствии с некоторой порождающей грамматикой. После чего, в БД (базе данных Пролога) должны появиться новые факты. Эти факты будут представлены в форме так называемых глубинных (канонических) структур – некоторых утверждений (statements),  например, для приведённых выше фраз – это следующие факты Пролога:

statement( location( is( on), object( piramid1, char( size( big), color( blue), _), object( box1, char( size( _), color( green), _))).

statement( location( is( on), object( piramid2, char( size( little), color( grey), _), object( box2, char( size( _), color( blue), _))).

statement( location( is( right), object( box1, char( size( big), color( _), _), object( box2, char( size( little), color( _), _))).

statement( location( is( behind), object( box1, char( size( big),color( _), _), object( box2, char( size( little), color(  _), _))).

statement( object( box1, char( size( big), color( green), spec( notch)))).

statement( object( box2, char( size( little), color( red), spec( no)))).

statement( object( all, char( number( 4),  lighting( right)))).

Здесь «_» – анонимная неозначенная переменная Пролога, char – сокращение от слова characteristics (характеристики), в данном случае, это характеристики объекта. Характеристик несколько: size(размер), color(цвет), spec – сокращение от слова specific (особенность).

Отметим, что число структур (здесь их 7) может не совпадать с числом исходных фраз на ОЕЯ (здесь их 6).

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

«Учитель» может «попросить» программу ответить на вопросы, сформулированные также на ОЕЯ:

How many objects in the image? (Сколько предметов на изображении?)

What color is the big object? (Какого цвета большая коробка )

What is left of the green object? (Что находится слева от зелёного объекта?)

What color is the body near a small body? (Какого цвета тело, находящееся рядом с маленьким телом?)

Less if red body green body? (Меньше ли красное тело зелёного тела?)

And the like. (И тому подобное.)

После введения указанных фраз (вопросов) на ОЕЯ и их синтаксического анализа в базе данных Пролога должны появиться новые факты в форме так называемых «глубинных структур» вопросов (questions), например, для приведённых выше:

question ( object( all, char( number( X),  _))).

question ( object( box1, char( size( big), color( X), _))).

question (  location( is( left),  object( Name1, Char1), object( Name2,  char( _, color( green), _)))).

question ( location( is( on), object( Name1, char( _, color( Color1), _)), object( Name2, char( size( little), _, _)))).

question ( compar( less( Size1, Size2), object( Name1, char( size( Size1)_, color( red), _), object( Name2, char( size( Size2, color( green),  _)))).

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

Например, на 3-й вопрос из представленного списка: question( location( is( left), object( Name1, Char1), object( Name2, char( _, color( green), _)))) («Что находится слева от зелёного объекта?») неожиданно может последовать «расширенный» ответ Пролога: statement( location( is( left), object( box2, char( size( little), color( red), spec( no))), object( box1, char( size( big), color( green), spec( notch)))). («Слева от большого зелёного объекта с именем box1, имеющего особенность (выемку), находится маленький красный объект с именем box2, не имеющий особенностей»).

Отметим, что, «между прочим», Пролог «самостоятельно уточнил»: исходный зелёный объект (1) имеет большой размер, (2) имеет имя box1 и (3) имеет особенность (выемку). Хорошо это, или плохо – получать избыточную информацию – судить пользователю.

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

1.1. Использование разностных списков для повышения эффективности нисходящего синтаксического анализа на Прологе

Синтаксический анализ является важным приложением логического программирования (в целом) и языка Пролог (в частности).

Напомним представленные в разд. 1.1 статьи [1] определения: порождающей грамматики; формального языка, порождаемого такой грамматикой, а также мест, которые занимают контекстно-свободные и контекстно-зависимые грамматики в классификации формальных грамматик. (Классическую формализацию порождающих грамматик впервые предложил Ноам Хомский в 1950-х годах. [Википедия: https://en.wikipedia.org/wiki/Formal_grammar]).

Формальная грамматика – это следующая «четвёрка»:

G = <VT, VN, S, P>,

где VT и VN – терминальный и нетерминальный словари, P = {a_i  → b_i} – множество правил вывода, a_i – цепочка, содержащая нетерминальный символ, b_i – произвольная цепочка из терминальных и нетерминальных символов, S – начальный символ.

Непосредственным порождением называется отношение

l  ⇒ m,

где   l = d₁ a_i  d₂,      m = d₁  b_i  d₂     и существует правило:  a_i → b_i.

Порождением называется отношение

g ⇒* g_n,          n = 1, 2, ...

если существует последовательность отношений

g  ⇒  g₁ ⇒ ... ⇒ g_n.

Языком, порождаемым грамматикой G, называется следующее множество:

L(G) = {g | S ⇒* g}.

(множество терминальных цепочек g – цепочек, состоящих только из символов терминального словаря VT).

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

Типы формальных грамматик:

Если нетерминальный символ в левой части какого-либо правила грамматики находится в окружении других символов (терминальных и/или нетерминальных), то такая грамматика называется контекстно-зависимой.

Грамматика называется контекстно-свободной, если левая часть каждого правила вывода этой грамматики – это цепочка, состоящая из единственного нетерминального символа.

Контекстно-свободная грамматика называется автоматной, если каждое правило вывода этой грамматики имеет следующий вид:

А → аВ  или А → а  или А → l,

где A, B – нетерминальные символы, a – терминальный символ,

λ – пустая цепочка.

Типы формальных языков:

Язык называется автоматным, если для его порождения можно построить автоматную грамматику. (Разумеется, для порождения этого языка можно построить грамматики и других типов.)

Язык называется контекстно-свободным, если для его порождения можно построить контекстно-свободную грамматику, но нельзя построить автоматную грамматику.

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

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

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

Как выяснилось, можно обойтись без неэффективного предиката append/3, использование которого «напрашивается» для недетерминированного разбиения цепочки на подцепочки. Для этого следует воспользоваться понятием разностного списка [3, 4] или (что эквивалентно) ввести дополнительный аргумент в предикаты анализатора.

Разностный список – это структура инфиксного типа с именем \ (косая черта с наклоном влево)  и двумя компонентами: списком [A1, …, An | T] и списком T:

[A1, …, An | T] \ T.

Эта структура эквивалентна «обычному» списку, содержащему n элементов: [A1, …, An]. Но в записи разностного списка есть переменная T, значением которой может быть любой список. Можно привести аналогию: любое число, например 5, равно значению выражения (5 + X) – X, содержащего переменную X с любым значением.

Использование понятия «разностный список» позволяет существенно повысить эффективность работы многих предикатов обработки списков – в нашем случае, предиката append/3 (конкатенации или «склеивания»). Вместо определения

append([], L, L).

append([H|T], L, [H|R]) :- append(T, L, R).

можно воспользоваться гораздо более эффективным определением:

append_dl(X\Y, Y\Z, X\Z).

Иллюстрация данного определения – на рисунке 3.

 

Рисунок 3. Иллюстрация конкатенации разностных списков:  append_dl(X\Y, Y\Z, X\Z).

 

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

Пример 1.1.  

Рассмотрим два списка: L1 = [a, b, c];  L2 = [d, e, f]. Необходимо найти конкатенацию этих списков. 

Вызов ?- append([a, b, c], [d, e, f], Z).

приводит к необходимости трёх рекурсивных вызовов, дающих искомый результат

Z = [a, b, c, d, e, f].

Вызов ?- append_dl([a, b, c|X] \ X,   [d, e, f] \ [],   Z).

дает тот же результат  Z = [a, b, c, d, e, f] \ []  за единственный шаг логического вывода.

Эксперимент в системе Win Prolog LPA [8] демонстрирует следующий листинг как многострочный комментарий – фрагмент текста программы на Прологе, обрамлённый скобками /* и */.

 

Листинг 1

 

Пример 1.2.

Рассмотрим программу на Прологе, реализующую анализатор для фрагмента контекстно-свободной грамматики, порождающей фразы типа:

Маленькая серая пирамида располагается на красном ящике.

На красном ящике располагается маленькая серая пирамида.

с использованием разностных списков вместо предиката append/3.

Сначала, рассмотрим неэффективный вариант этого анализатора с использованием предиката append/3.

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

Желательно составить «минимальную» порождающую грамматику, которая обеспечивала бы генерацию фраз языка, не выходящих за рамки типов примера 1.2. Порождающая грамматика для анализа приведенных выше цепочек типов (1) и (2), может быть такой, которая представлена следующим листингом:

 

Листинг 2

 

Это контекстно-зависимая грамматика, так как члены предложения должны быть связаны по роду, числу и падежу. Контекстную зависимость можно реализовать с помощью переменных. Например так, как в двух изменённых строках листинга 2:

 

Листинг 3

 

Значения переменных K1 и K2 – это контекст, например, в рассмотренном примере:

K1 = k(падеж(именительный), род(мужской)) и K2 = k(падеж(родительный), род(мужской))  – для фраз типа (1);

K1 = k(падеж(родительный), род(женский)) и K2 = k(падеж(именительный), род(мужской)) – для фраз типа (2).

Связь по контексту K1 реализуется между нетерминальными символами NGr и Verb в начале фразы (1), а по контексту K2 – в конце фразы (2).

А теперь, главное: о замене неэффективно работающего предиката append/3 разностными списками.

Листинг 4 представляет анализатор на Прологе с квази недетерминированным, медленно работающим предикатом append/3 (пока, без привлечения разностных списков и механизма DCG).

 

Листинг 4

 

В этой программе на Прологе предполагается, что анализируемые цепочки ОЕЯ представляются в виде списков лексем. Здесь, это следующие списки:

[большой, зелёный, ящик, находится, правее, маленького, предмета];

[левее, зелёной, коробки, расположен, красный, объект].

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

            DList = [A1, …, An | T] \ T.

Этот список эквивалентен «обычному» списку [A1, …, An].

Использование разностных списков вместо «обычных» списков позволяет существенно сократить время перебора вариантов недетерминированного разбиения цепочки, представленной в виде списка лексем, на подцепочки. Известно [2, 6, 7], что на таком разбиении основан алгоритм нисходящего синтаксического разбора (синтаксического анализа), реализованный в логическом программировании вообще, и на Прологе, в частности. Разностные списки позволяют избавиться от предиката append/3 в правилах синтаксического анализатора следующим образом:

Пример 1.3. Пусть имеется грамматическое правило с тремя нетерминальными символами в правой части: S → A B C. При реализации нисходящего синтаксического анализатора на Прологе это правило требует разбиения исходной цепочки на 3 цепочки:

 

Листинг 5

 

Как было отмечено выше, использование предиката конкатенации двух списков (или разбиения одного списка на два) описывается без рекурсивных правил: append_dl(X\Y, Y\Z, X\Z). Это позволяет производить недетерминированное разбиение списков на подсписки без дорогостоящих рекурсивных вызовов – только на уровне отождествления структур данных.

Реально, представленное выше правило в анализаторе будет выглядеть так:

 

Листинг 6

 

Указанное включение понятия разностного списка в реализованные на Прологе синтаксические анализаторы, позволил создателям многочисленных современных версий этого языка включать в эти версии специально разработанный около 40 лет  назад [2] механизм DCG, подробно описанный в следующем разделе 1.2.

1.2. DCG – встроенный в Пролог механизм синтаксического анализа, реализующий идею разностных списков

Реализацией разностных списков является встроенный в любую Пролог систему механизм DCG.

В классической монографии Стерлинга и Шапиро [7] отмечено (с. 203): «Происхождение Пролога связано с попыткой использовать логику для выражения грамматических правил и формализации процесса синтаксического разбора. Наиболее распространённым подходом к реализации синтаксического разбора средствами Пролога является использование грамматик, задаваемых определительными предложениями (definite clause grammar, DCG). Такие грамматики являются некоторым обобщением контекстно-свободных грамматик. Они представляют собой нотационный вариант определённого класса программ на Прологе и потому являются исполняемыми».

DCG как нотационный вариант программ класса «нисходящих синтаксических анализаторов» на Прологе, в которых «напрямую» записаны правила порождающих грамматик, декларируется следующими правилами нотации :

1.      Связка Пролога :- («обратная импликация»), которая читается как слово «if» («если»), между левой и правой частями правила Пролога, заменяется связкой -->, соответствующей стрелке порождающей грамматики.

2.      Предикаты как левой части правила (до связки -->), так и правой части правила (после связки -->) в нотации DCG не должны содержать в явном виде (в виде входных параметров) ни входной цепочки (списка лексем), ни остатка этой цепочки, оставшейся после её анализа в соответствии с данным правилом грамматики.

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

4.      Все сопровождающие синтаксический анализ дополнительные действия (например, арифметические вычисления), производимые с аргументами предикатов, должны обрамляться фигурными скобками: { и }.

5.      Терминальные символы в правых частях грамматических правил должны быть представлены списками. В частности, если «читается» один символ, например, лексема, это список из одного элемента.

Пример 1.4.

Рассмотрим листинг 6 – программу синтаксического анализа в соответствии с правилом грамматики S → A B C. В единственном правиле этой программы, как в левой, так и в правой его части у всех предикатов только один входной параметр, представленный разностным списком. Поэтому в нотации DCG данное правило будет иметь следующий вид:

 

Листинг 7

 

Допустим, данное правило используется для анализа языка {aⁿ b^m c^k}, n>0, m>0, k>0. Это контекстно-свободный язык, поэтому не требует использования переменных для реализации контекстной зависимости.

Для написания анализатора с выдачей значения трёх выходных параметров N, M и K добавим к листингу 7 дополнительные правила в нотации DCG:

 

Листинг 8

 

И, наконец, внесём ещё одно усложнение: равенство значений переменных N, M и K. Это ограничение превращает язык в контекстно-зависимый язык {aⁿ bⁿ cⁿ}, n>0.

Для реализации анализатора этого языка в нотации DCG достаточно изменить только первое правило:

 

Листинг 9

 

Анализатор на Прологе для рассмотренного в разделе 1.1 Примера 2  (Листинг 4) без предиката append/3 и с привлечением механизма DCG представлен листингом 10:

 

Листинг 10

 

В заключение данного раздела рассмотрим, в какое правило в традиционной нотации Пролога автоматически преобразуется правило в нотации DCG. На этот вопрос отвечает запрос: ?- listing(<имя предиката>/<арность предиката>). Этот запрос следует ввести после компиляции предиката, введённого в нотации DCG.

Например, вызовем указанный запрос после компиляции определения предиката an_S/1, введённого в нотации DCG (листинг11), и после проверки работы этого предиката (листинг 12):

 

Листинг 11

 

Листинг 12

 

Отметим, что использование встроенного предиката 'C'/3, который применяется только для выделения «головы» (Head) и «хвоста» (Tail) списка (List), демонстрирует применение  разностных списков для синтаксического анализа. Его определение: 'C'( [Head|Tail], Head, Tail).

Переопределим имена переменных, сформированных системой (системные имена A, B, C, D, E, F, G), на более содержательные (мнемонические имена).

В первом правиле заменим: A на N; B на Input; C на Rest; D на L1; E на N1; F на L2; G на N3. Во втором правиле заменим: A на Input;  B на Rest; C на L1; D на L2.

Заменим также встроенный предикат 'C'/3 в соответствии с его определением.

После чего получим:

 

Листинг 13

 

При трансляции из нотации DCG в нотацию Пролога система автоматически проводит дополнительную оптимизацию этих правил:

 

Листинг 14

 

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

2. Технология практической реализации и полученные результаты

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

Пример 2.1.

Пусть анализируемое тоновое изображение после его преобразования в векторную форму (процесс преобразования описан в статье автора [1]) демонстрирует пять тел разного цвета с плоскими гранями (рисунок 4):

 

Рисунок 4. Пример векторного изображения пяти многогранников, полученного путём обработки исходного тонового изображения. Числа на рисунке – номера граней (полигонов одинакового цвета)

 

Система анализа изображения, описанная в упомянутой выше статье [1], не только преобразует тоновое изображение в векторное, выделяет вершины и рёбра представленных на изображении многогранников с помощью визуального языка Visual Basic, но и вычисляет некий результат с помощью программы на языке Пролог. Исходные данные и результат визуализируются на экранной форме. На рисунке 5 демонстрируется вид этой формы для данного примера.

 

 

Рисунок 5. Пример экранной формы приложения, в котором реализован интерфейс программ на языках Visual Basic и Prolog. На форме видны как исходные данные, так и результаты анализа изображения: выявленный список тел (многогранников) с их характеристиками

 

Тела на рисунке 4 находятся в очевидных для неискушенного зрителя пространственных отношениях. Эти отношения человек (наблюдатель) в соответствии со своей традиционной моделью мира может легко интерпретировать, например, следующим образом:

·         на рисунке зафиксирован предмет, который можно назвать «столом» коричневого цвета»;

·         на «столе» расположены две «коробки» красного и зелёного цвета;

·         под «столом» находится «ящик» синего цвета»;

·         на зелёной «коробке» лежит белая «книга».

Как было сказано в предыдущей статье автора на рассматриваемую тему [1], конечной целью системы распознавания изображений данного класса может быть планирование действий интеллектуального робота по захвату и переносу предметов, зафиксированных видеокамерой робота. Программа планирования, разумеется, должна работать вместе с программой анализа изображений.

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

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

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

Назначение данной программы – преобразование выражения поверхностных структур ограниченного естественного языка (ОЕЯ) в выражения  на языке глубинных структур (ЯГС), которые, в силу своей жёсткой и однозначно интерпретируемой формальной основы, могут быть легко использованы интеллектуальным роботом при его планировании своих действий с выявленными на изображении телами.

Пример: преобразование поверхностной структуры (списка лексем ОЕЯ):

[четвёртое, тело, находится, под, третьим, телом] в структуру:

st( 6, location( is( under), object( box3, char( size( middle), color( blue))), object( table, char( size( big), color( brown))))).

Начало программы на Прологе (точнее, кода в смешанной нотации «чистого» Пролога встроенного в Пролог языка DCG) представлено в следующем листинге:

 

Листинг 15

 

После комментария – интерпретируемая часть кода:

 

Листинг 16

 

В качестве тестовой базы данных Пролога в данной программе представлены факты, соответствующие изображению на рисунке 4:

 

Листинг 17

 

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

Далее – лишь небольшой фрагмент программы.

В частности, это демонстрация проверки работоспособности процедуры присвоения новых, более выразительных имён тел, выявленных на изображении, – в поверхностных структурах ОЕЯ – как в утверждениях, так и в вопросах. Например:

·        новое_имя( ящик1) → старое_имя( первое, тело);

·        новое_имя( ящик2) → старое_имя( второе, тело);

·        новое_имя( стол) → старое_имя( третье, тело);

·        новое_имя( ящик3) → старое_имя( четвёртое, тело);

·        новое_имя( книга) → старое_имя( пятое, тело).

Процедура на следующем листинге:

 

Листинг 18

 

Результат проверки – на следующем листинге:

 

Листинг 19

 

После проведённого присвоения имён всем телам на изображении в базу данных Пролога заносятся следующие структуры – факты-утверждения и факты-вопросы с присвоенными им номерами:

 

Листинг 20

 

После вызова цели: | ?- setof(N, s(N), L). были получены следующие результаты (на консоли интерпретатора Пролога фирмы LPA [8]) – утверждения в виде канонических глубинных структур:

 

Листинг 21

 

В полученном списке следует отметить следующее:

·         во всех утверждениях (а их не 16, а только 11, так как 5 утверждений-дубликатов автоматически удалены);

·         в обработанных утверждениях автоматически означены все переменные.

После вызова цели | ?- setof(N, q(N), L). во всех десяти вопросах переменные, так же, как в утверждениях, означены в результате работы программы. Вопросы приобрели следующий канонический вид (вид глубинных структур):

 

Листинг 22

 

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

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

1.      Microsoft .NET – версия 4 (в частности, версия 4.0, Visual Studio 2010 и поддерживаемый ей язык Visual Basic 2010);

2.      Windows Prolog – версии интерпретаторов-компиляторов языка Пролог, разрабатываемые и поддерживаемые фирмой LPA [8].

Переносимость на другие платформы в настоящее время представляется неактуальной, так как рассмотренные выше платформы являются популярными и доступными. В частности, более поздние версии платформы Microsoft .NET являются совместимыми с версией 4.0, а фирма LPA в настоящее время продолжает совершенствование и коммерческое распространение ориентированных на операционную систему Windows интерпретаторов-компиляторов языка Пролог.

Функциональные возможности для пользователя демонстрирует следующее замечание.

Рассмотренный в данной статье блок обучения, реализованный на языке Пролог, можно легко включить в систему анализа изображений, описанную в предыдущей статье автора [1]. Для этого достаточно включить в меню этой системы команду, вызывающую появление новой экранной формы.

На этой форме, показанной на рисунке 6, в двух окнах демонстрируются исходные данные – тестовые утверждения и вопросы относительно характеристик и взаимного расположения геометрических тел на изображении. В третьем окне показаны полученные в результате обучения глубинные структуры ответов на все тестовые вопросы.

 

Рисунок 6. Экранная форма с результатами обработки обучающих тестов, вызываемая, в процессе работы системы анализа изображений

 

Государственная регистрация программы

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

Эта система прошла государственную регистрацию в 2015 году, а автор получил свидетельство об указанной государственной регистрации соответствующей программы для ЭВМ «Демонстрационная программа по анализу изображений тел с плоскими гранями» № 2015611531 (дата регистрации 30 января 2015 г.) [10].

Заключение

Рассмотрена принципиальная возможность дополнения системы анализа изображений, в которой совмещены средства логического (структурного) подхода со средствами визуального программирования, описанной в публикации [1], блоком обучения. В этом блоке предлагается реализовать общение программы с человеком на ограниченном естественном языке с использованием реализованного автором на языке Пролог синтаксического анализатора. Цель указанного обучения – получение системой знаний о взаимном расположении тел. Эти знания должны помочь роботу, оснащенному системой анализа изображений, планировать свои действия, связанные с захватом и переносом тел, выявленных на изображении.

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

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

 

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

1.      Volchenkov N.G. The application logical and visual programming interface for image analysis of the geometric bodies. «Scientific Visualization». National Research Nuclear University MEPhI, 2015. Q3, V7, N3. Pages 84 – 97. [Электронный ресурс]. URL: http://sv-journal.org/2015-3/09.php?lang=eng (дата обращения 03.12.2017).

2.      Warren D.H.D., Pereira L.M., Pereira F. PROLOG – the language and its implementation. Proceedings of the Symposium on Artificial Intelligence. SIGPLAN Notes, 12(8), 1977.

3.      Волченков Н.Г. Логическое программирование. Язык Пролог: Тексты лекций. Изд. второе, испр. и доп. – М.: МИФИ, 2015. – 160 с.

4.      Сергиевский Г.М., Волченков Н.Г. Функциональное и логическое программирование: Учеб. пособие для студ. высших учеб. заведений. – М.: Издательский центр «Академия», 2010. – 320 с.

5.      Волченков Н.Г. Использование современных информационных технологий в обучении студентов по направлению «Информатика и вычислительная техника», различным парадигмам программирования: «Современные научные исследования и инновации». 2015. № 3 [Электронный ресурс]. URL: http://web.snauka.ru/issues/2015/03/47345 (дата обращения 28.03.2015).

6.      Братко Иван. Алгоритмы искусственного интеллекта на языке PROLOG, 3-е издание.: Пер. с англ. – М.: Издательский дом «Вильямс», 2004. – 640 с

7.      Стерлинг Л., Шапиро Э. Искусство программирования на языке Пролог. – М.: Мир, 1990. – 235 с.

8.      Сайт компании Logic Programming Associates Ltd. [Электронный ресурс]. URL: http://www.lpa.co.uk/ (дата обращения 21.03.2015).

9.      Зиборов В.В. Visual Basic 2010 на примерах. – СПб.: БХВ-Петербург, 2010. – 336 с.

10.  Свидетельство о гос. регистрации программы для ЭВМ № 2015611531 «Демонстрационная программа по анализу изображений тел с плоскими гранями». Автор: Волченков Н.Г. (RU). [Электронный ресурс]. URL: http://www1.fips.ru/Archive/EVM/2015/2015.02.20/DOC/RUNW/000/002/015/611/531/document.pdf (дата обращения 07.04.2015).

11.  Волченков Н.Г. Синтаксический анализ изображений совокупности тел некоторого класса, использующий интерфейс логического и императивного визуального языков программирования. Журнал «Новые информационные технологии», ФГУП «ЦНИЛОТ», 2010, № 1, с.58 – 62.

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

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

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

П1. Начало кода (комментарии)

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

Итак, начало кода, интерпретируемого Прологом:

 

Листинг П1

П2. Интерпретируемая часть кода

После комментариев – интерпретируемая часть кода:

 

Листинг П2

 

 

 

 

 

 

 

---

The image analysis of the geometric bodies with supplemental interactive block for training new knowledge in a limited natural language

Authors: N.G. Volchenkov

NRNU «MEPhI», Moscow, Russia

ORCID: 0000-0002-1474-6853, NGVolchenkov@mephi.ru

 

Abstract

The prototype of the system for image analysis of geometric bodies, using the interface of logical and visual programming, was developed by the author for experiments with an intelligent robot that is equipped with a video camera. It is assumed that the robot is designed to plan its actions - capture and transfer of bodies. The class of bodies considered by the author is colored polyhedra in local colors. The drawback of the results obtained in the author's previous publication is the absence of an analysis of the relative location of the identified set of polyhedra. Obvious are the difficulties that can arise when trying to automatically (without the participation of a person) to identify the mutual arrangement of bodies. The task is facilitated by the inclusion in the system of the block of interactive training of the robot by man. This person is an operator - a person who can formulate his description of a specific image in a limited natural language. The form of this description is the so-called surface structures of natural language phrases. In this article, the author presents the program of syntactic analysis of surface structures necessary for this purpose. This program is implemented on Prolog - the language of logical programming. To illustrate the results of the training block implemented on Prolog, the author, like in his previous publication, offers a visual programming interface (Visual Basic language) and logical programming (Prolog language). The article presents an example of a concrete image, on which 5 bodies of different colors are revealed. This example allowed us to demonstrate the most typical cases of the relative positioning of bodies, their description on the surface structures proposed by the author and the syntactic analysis of the phrases of this language. An important side effect of syntactic analysis is also presented - the construction of deep structures of a limited natural language. These structures are represented in the form of structures of the language Prolog - on the developed by the author language of deep structures. This view can later be used by the robot directly to plan its actions.

 

Keywords: logical programming (LP); language Prolog; visual programming; the Visual Basic language; database of Prolog; limited natural language (LNL); the surface structure of the phrase on the LNL; learning as introducing new knowledge into the Prolog database; syntactic analysis of the LNL; the language of deep structures (DSL); the definite clause grammar (DCG) – the mechanism in Prolog.

References

               

1.      Volchenkov N.G. The application logical and visual programming interface for image analysis of the geometric bodies. «Scientific Visualization». National Research Nuclear University MEPhI, 2015. Q3, V7, N3. Pages 84 – 97. [Electronic resource]. URL: http://sv-journal.org/2015-3/09.php?lang=eng (circulation date 03.12.2017).

2.      Warren D.H.D., Pereira L.M., Pereira F. PROLOG – the language and its implementation. Proceedings of the Symposium on Artificial Intelligence. SIGPLAN Notes, 12(8), 1977.

3.      Volchenkov, N.G. Logicheskoe programmirovanie. YAzyk Prolog: Teksty lektsij. [Logical programming. Language Prologue: Texts of lectures.] Ed. second, corrected. and additional. - Moscow: MEPhI, 2015. – 160 p. [In Russian]

4.      Sergievsky G.M, Volchenkov N.G. Funktsional'noe i logicheskoe programmirovanie: Ucheb. posobie dlya stud. vysshikh ucheb. zavedenij. [Functional and logical programming: Proc. allowance for stud. higher education.] - Moscow: Publishing Center "Academy", 2010. - 320 p. [In Russian]

5.      Volchenkov, NG. Ispol'zovanie sovremennykh informatsionnykh tekhnologij v obuchenii studentov po napravleniyu «Informatika i vychislitel'naya tekhnika», razlichnym paradigmam programmirovaniya: «Sovremennye nauchnye issledovaniya i innovatsii». [The use of modern information technologies in teaching students in the field of "Informatics and computer technology", various programming paradigms: "Modern scientific research and innovation."] 2015. № 3 [Electronic resource]. URL: http://web.snauka.ru/issues/2015/03/47345 (circulation date 28.03.2015). [In Russian]

6.      Bratko Ivan. Аlgoritmy iskusstvennogo intellekta na yazyke PROLOG, 3-e izdanie.: Per. s angl. [Algorithms of artificial intelligence in the language PROLOG, 3rd edition .: Trans. English.] - Moscow: Williams Publishing House, 2004. - 640 pages

7.      Sterling L., Shapiro E. Iskusstvo programmirovaniya na yazyke Prolog. [The art of programming in the language Prolog.] - Moscow: Mir, 1990. - 235 p. [In Russian]

8.      The website of Logic Programming Associates Ltd. [Electronic resource]. URL: http://www.lpa.co.uk (circulation date: 21/03/2015).

9.      Ziborov V.V. Visual Basic 2010 na primerakh [Visual Basic 2010 on examples.] - St. Petersburg .: BHV-Petersburg, 2010. - 336 p. [In Russian]

10.  Certificate of state. registration of the computer program № 2015611531 "Demonstration program for the analysis of images of bodies with flat faces." Author: Volchenkov N.G. (RU). [Electronic resource]. URL: http://www1.fips.ru/Archive/EVM/2015/2015.02.20/DOC/RUNW/000/002/015/611/531/ document.pdf (circulation date 07/04/2015). [In Russian]

11.  Volchenkov, N.G. Sintaksicheskij analiz izobrazhenij sovokupnosti tel nekotorogo klassa, ispol'zuyushhij interfejs logicheskogo i imperativnogo vizual'nogo yazykov programmirovaniya. [Syntactic analysis of images of a set of bodies of a certain class, using the interface of logical and imperative visual programming languages.] Journal of New Information Technologies, FSUE "TsNILOT", 2010, No. 1, p.58 - 62. [In Russian]