12.2.2. ГРАФЫ ОТНОШЕНИЙ
Во многих задачах анализа сцен нас интересует описание «на словах», т. е. символически, структуры конкретной сцены. Мы только что видели, что в таких ситуациях могут применяться формальные синтаксические методы; другим средством составления символических описаний являются графы отношений.
Вместо того чтобы открывать эту тему формальным определением, возьмемся за нее с помощью примера. На рис. 12.3 мы показали дерево грамматического разбора для сцены рис. 12.1. Узлы дерева помечены как части сцены; дуги дерева (дуги представляют собой соединения между узлами) не помечены. Хотя эти дуги не имеют точных меток, мы можем заметить, что вкладываемый в них смысл сводится к тому, что узел на нижнем конце дуги «является частью» узла на ее верхнем конце. Другими словами, дуги дерева грамматического разбора задают определенное отношение между узлами, которые они связывают.
(см. скан)
Рис. 12.6. Граф отношений.
Основную идею использования дуги для обозначения отношения можно обобщить несколькими очевидными способами. Во-первых, мы можем расширить класс разрешенных отношений с тем, чтобы включить в него каждое отношение, которое удобно устанавливать по изображению. Мы можем также рассматривать не деревья, а графы отношений, чтобы можно было задавать отношения между двумя произвольными узлами. (Граф в общем случае содержит замкнутые петли, а дерево их не содержит.) С помощью этих обобщений мы можем составлять более богатые описания, чем с помощью простых деревьев грамматического разбора.
В качестве иллюстрации предположим, что мы перерабатываем дерево разбора рис. 12.3 в более полное описание сцены рис. 12.1 графом отношений. Мы условимся применять выбранные произвольно отношения «являться частью», «являться видом», «прилегать к», «находиться слева от», «находиться справа от», «находиться над» и «находиться под». Одно из описаний этой сцены графом отношений показано на рис. 12.6. Для удобства мы поместили стрелки на каждой из дуг, чтобы показать смысл отношения, и превратили тем самым граф отношений в направленный граф. Направления стрелок были выбраны таким образом, что, если прочесть сначала метку узла в хвосте стрелки, затем метку стрелки и, наконец, метку узла в голове стрелки, получится грубый «перевод на русский язык». Заметим, что показанный граф отношений можно сделать более информативным, даже не вводя дополнительных отношений; так, например, круглая поверхность и кривая поверхность цилиндра связаны не только отношением «прилегать к», но и симметричной парой отношений «находиться над» и «находиться под». Это еще один пример существенного произвола в выборе количества информации, которую мы хотим включить в любое данное описание.
