12.2.2.     ГРАФЫ ОТНОШЕНИЙ

Во многих задачах анализа сцен нас интересует описание «на словах», т. е. символически, структуры конкретной сцены. Мы только что видели, что в таких ситуациях могут применяться формальные синтаксические методы; другим средством составления символических описаний являются графы отношений.

Вместо того чтобы открывать эту тему формальным определением, возьмемся за нее с помощью примера. На рис. 12.3 мы показали дерево грамматического разбора для сцены рис. 12.1. Узлы дерева помечены как части сцены; дуги дерева (дуги представляют собой соединения между узлами) не помечены. Хотя эти дуги не имеют точных меток, мы можем заметить, что вкладываемый в них смысл сводится к тому, что узел на нижнем конце дуги «является частью» узла на ее верхнем конце *). Другими словами, дуги дерева грамматического разбора задают определенное отношение между узлами, которые они связывают.

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

В качестве иллюстрации предположим, что мы перерабатываем дерево разбора рис. 12.3 в более полное описание сцены рис. 12.1 графом отношений. Мы условимся применять выбранные произвольно отношения «являться частью», «являться видом», «прилегать к», «находиться слева от», «находиться справа от», «находиться над» и «находиться под». Одно из описаний этой сцены графом отношений показано на рис. 12.6. Для удобства мы поместили стрелки на каждой из дуг, чтобы показать смысл отношения, и превратили тем самым граф отношений в направленный граф. Направления стрелок были выбраны таким образом, что, если прочесть сначала метку узла в хвосте стрелки, затем метку стрелки и, наконец, метку узла в голове стрелки, получится грубый «перевод на русский язык» г). Заметим, что показанный граф отношений можно сделать более информативным, даже не вводя дополнительных отношений; так, например, круглая поверхность и кривая поверхность цилиндра связаны не только отношением «прилегать к», но и симметричной парой отношений «находиться над» и «находиться под». Это еще один пример существенного произвола в выборе количества информации, которую мы хотим включить в любое данное описание.