20.4. МЕТОДЫ, ИСПОЛЬЗУЮЩИЕ ОТНОШЕНИЯ МЕЖДУ ОБЪЕКТАМИ

Дерево грамматического разбора, описанное в предыдущем разделе, дает лишь грубое описание сцены с использованием связей между его терминальными и нетерминальными символами. Часто бывает доступна и другая, более подробная информация. Например, может быть известно, что объект  расположен выше объекта  и что область  окружает оба объекта. Информацию такого типа можно представить в виде графа отношений, в котором ребра, соединяющие символы дерева разбора, размечены по типу связи и пространственных отношений между символами. На рис. 20.4.1 приведен соответствующий пример. Стрелки на ребрах показывают направление отношения; например, КРЫША выше СТЕНЫ. Граф отношений с такими указателями называется направленным. Теоретический анализ методов, основанных на системах отношений, отсутствует. Остановимся на конкретных подходах к разработке систем понимания изображений, в которых явно или неявно используются эти отношения.

Рис. 20.4.1. Пример направленного графа отношений.

Впервые знания об отношениях между объектами были использованы для построения системы понимания изображений в работе Робертса [22], который разработал довольно полную систему программ анализа сцен, содержащих многогранники с плоскими поверхностями. Логично начать анализ сцен именно с многогранников, так как их можно относительно легко описать и пространственные отношения между ними четко определены. В системе, предложенной Робертсом, анализ начинается с представления многогранника в виде контурного рисунка, который заносится в память в виде списка прямолинейных отрезков, заданных декартовыми координатами концевых точек. Этот список анализируется с целью обнаружения соединенных линейных отрезков, формирующих многоугольники. Рис. 20.4.2 иллюстрирует три типа многоугольников, которые могут находиться в сцене: выпуклый многоугольник, невыпуклый многоугольник и многоугольник, образованный границами изображения многогранника. На следующем этапе обработки множество вершин многоугольника сопоставляется с множеством вершин простых моделей объекта для того, чтобы разбить исходный объект на составные элементы, как показано в примере на рис. 20.4.3. Если найдено, что модель простого объекта является частью исходного объекта, то эта часть исключается из исходного объекта путем вычеркивания из списка и добавления соответствующих отрезков линий.

Рис 20.4.2. Составление изображения многогранника из многоугольников

а - Объект; б — многоугольник, образованный внешним контуром; в — невыпуклый  многоугольник; г - выпуклый многоугольник.

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

Идея Робертса относительно разбиения сложного многогранника на простые объекты породила направление исследовательских работ, которые теперь называются анализом блочных схем. Гузман [23] и Фальк [24] продолжили исследования сцен, содержащих «непрозрачные» объекты и представленных в виде неполного контурного рисунка. В предложенных ими системах выделение областей изображения, соответствующих плоским поверхностям сцены, осуществляется по специальным эвристическим правилам. Уинстон [5, стр. 5] предложил методы обучения, с помощью которых информация, полученная из анализируемых сцен, используется для наращивания набора зрительных моделей сцен.

Рис. 20.4.3. Разборка многогранника а – объект; б – призма; в – основание в форме параллелепипеда; г – спинка в форме параллелепипеда.

Модели запоминаются в виде направленного графа отношений, в котором дуги помечены простыми отношениями типа «соседство» и «опора» между объектами. На рис. 20.4.4 приведены направленный граф для сцены, состоящей из арки, и несколько примеров ее построения. Ключевым элементом работы Уинстона является понятие «почти то». В примере арки «почти то» может означать, что два объекта типа «опора» не могут быть смежными.

Представление многогранников в виде контурных рисунков не может быть произвольным; некоторые комбинации прямых линий и вершин не допускаются при контурном представлении многогранников. Клоуз [25] и Хаффман [26] разработали процедуры, позволяющие выяснить, реальные или нереальные (бессмысленные) объекты представлены на контурном рисунке. Уолц [5, стр. 19] продолжил разработку этого подхода, установив 11 категорий для разметки контурных линий (рис. 20.4.5). Если две или больше линий сходятся в некоторой вершине, то должны быть выполнены определенные ограничения. Например, в узле типа  градиенты тени, соответствующие двум линиям, должны быть одинаково направлены. Анализ всевозможных комбинаций разметок показал, что большая их часть физически не допустима. Полное число реальных типов вершин для многогранников составляет лишь несколько тысяч. В системе Уолца анализ начинается с разметки линий, выходящих из каждой вершины. Затем программа «фильтр» проверяет последовательность линейных меток связанных между собой вершин и исключает несовместимые метки. На следующем этапе с помощью набора комбинационных правил согласовываются неоднозначные метки. Их, число в дальнейшем может быть ограничено при анализе типов смежных вершин.

Рис. 20.4.4. Пример направленного графа отношений для арки [5]: а — направленный граф отношений; б — примеры.

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

Рис. 20.4.5. Типы линий, образующих контуры многогранников [5].

Сираи [5, стр. 93, 27] развил другой подход к анализу сцен из многогранников, при котором реальные сцены анализируются непосредственно как массивы точек изображения. Программа Сираи — это первая программа, которая пытается выполнить гетерархический анализ осмысленных сцен. Знание типа объектов, с которыми она встречается, используется для управления поиском слабых перепадов яркости, соответствующих вогнутостям поверхностям объектов.

Важный шаг в направлении анализа сцен, содержащих тела с криволинейными поверхностями, сделан Хорном [5, стр. 115], а также Биифордом, Эйджипом и Невейшиа [28—30]. Хорн использовал светотень освещенных объектов с гладкими криволинейными поверхностями для определения их физической формы. Работа Бинфорда, Эйджина и Невейшиа направлена на получение трехмерных описаний формы объектов; при этом были использованы срединноосные остовы и системы конических сечений объектов.

Одной из первых попыток анализа достаточно сложных реальных сцен с привлечением информации об отношениях между объектами была работа, выполненная Брайсом и Феннема 1311. В их системе первый этап обработки состоит в сегментации изображения по принципу наращивания областей. Затем граница каждой выделенной области аппроксимируется отрезками прямых. Далее на этапе анализа для группировки областей и распознавания объектов используются семантические знания. Например, в сцене «служебное помещение» семантические знания представляют собой следующие факты: пол находится в нижней части сцены, стена — на краю сцены, картина — на стене. Барроу и Поппльстоун [32] также разработали систему анализа сцен, основанную на сегментации метода наращивания областей. В их системе векторы признаков измеряются для каждой сегментированной области; при этом используются такие признаки, как форма, толщина, размер и отношение к соседним областям, а именно: выше, ниже, слева и т. д. Вектор признаков каждой области затем сопоставляется с наборами векторов признаков областей в зрительной модели класса сцен, подлежащих анализу. В некоторых случаях при сопоставлении возникают трудности, вызванные тенями и преградами.

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

Келли [33] сделал важное предложение: использовать планирование анализа сцен как способ ограничения размерности задач поиска по дереву. По схеме Келли признаки и символы выделяются сначала из изображения сцены, полученной с малым разрешением. Затем распознаются и размечаются объекты и вырабатывается гипотетическая модель сцены. Далее для выделения признаков и символов выполняется управляемый моделью поиск областей на картинке, полученной с полным разрешением.

Продолжая исследования Келли, Тененбаум и др. [34] предложили систему анализа, которая включает два этапа: ознакомление и обоснование. На этапе ознакомления исследуются простые характеристики изображения, основанные на зрительной модели; при этом для управления поиском используется информация о содержании сцены. Например, в сцене служебного помещения поиск первоначально направлен на обнаружение плоской поверхности в средней части изображения, где предполагается наличие верхней поверхности письменного стола. Затем поиск продолжается в пределах этой поверхности для обнаружения интересующих нас объектов, которые анализируются и предварительно классифицируются. На этапе обоснования выполняется более тщательная обработка для выделения по возможности более надежных признаков в окрестности, где предполагается наличие объектов.

Полученная информация анализируется для определения правильности выдвинутой гипотезы. Таким образом ресурсы «дорогой» системы обработки информации можно распределить более эффективно.

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

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