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

Карпов В.Э.

ОБ ОДНОМ МЕХАНИЗМЕ РЕКОНСТРУКЦИИ СЦЕН

Введение

навигация трехмерный сцена реконструкция

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

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

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

Далее мы рассмотрим один из механизмов реконструкции сцен.

1. Общая схема реконструкции

Пусть мир, в котором действует робот, представлен некоторым множеством объектов Щ. Назовем это множество генеральным. Генеральное множество определяется рецепторными возможностями робота. Предположим далее, что между этими объектами существуют некоторые отношения S(Щ), в простейшем случае, например, геометрические. Для простоты будем полагать, что эти отношения не зависят от времени (мир статичен).

В каждый момент времени восприятие робота ограничено некоторым подмножеством наблюдаемых объектов O(t) и множеством наблюдаемых отношений между ними R(t). Это и есть наблюдаемая роботом текущая сцена. Важно то, что характер отношений между наблюдаемыми объектами может меняться. Например, в зависимости от местоположения робота или текущего ракурса.

Задача состоит в том, чтобы, исходя из наблюдаемых объектов O(t) и отношений R(t) реконструировать всю сцену - генеральное множество объектов Щ и множество отношений S(Щ).

Общая схема реконструкции включает в себя следующие шаги:

1. Выделение множества объектов O(t) в момент времени t.

2. Идентификация наблюдаемых объектов.

3. Определение текущих отношений между объектами R(t)=g(O(t),t).

4. Доопределение фундаментального множества отношений S(t)=f(S(t-1), R(t), O(t)).

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

2. Реконструкция трехмерной сцены в СТЗ

Задача реконструкции сцены является весьма типичной для создания системы навигации роботов. Обычно речь идет о том, что пространственные характеристики объектов определяются исходя из ряда изображений, на которых сцена видна с различных ракурсов. Из последовательности таких изображений можно извлечь пространственные характеристики объектов, рассматривая смещение соответствующих точек. Среди "классической" литературы, посвященной этому вопросу, отметим [Дуда и др., 1976] и [Марр, 1987], современное состояние вопроса представлено в [Назиров, 2011].

Частным, наиболее хорошо исследованным вопросом, является реконструкция поверхности трехмерной сцены по нескольким перспективным снимкам, полученным под разными ракурсами. "Типичное" решение данной проблемы состоит из следующих этапов [Абрамов и др., 1998]:

· Идентификация и оценивание координат сопряженных точек (одни и те же точки поверхности на разных снимках).

· Нормализация (выпрямление) изображений, используя найденные сопряженные точки.

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

· Реконструкция точек поверхности на основе триангуляционной процедуры (восстановление пространственных координат).

При этом постоянно оцениваются внешние и внутренние геометрические параметры камеры.

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

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

3. Схема реконструкции

Далее мы рассмотрим более подробно этапы реконструкции, для наглядности проводя аналогии с реконструкцией некоторой простой трехмерной сцены, приведенной на рис.1.

Рис.1. Изображение сцены

3.1 Выделение множества объектов

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

3.2 Идентификация наблюдаемых объектов

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

Предположим, что условия задачи не подразумевают однозначной идентификации объектов (на кубиках нет уникальных идентификаторов, как на рис.1).

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

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

Определение подобного рода сопряженных объектов - это сама по себе весьма сложная задача, особенно если мы можем идентифицировать объекты, исходя лишь из множества выявленных между ними отношений. На рис.2 представлены в виде графов отношения между объектами, видимыми с разных ракурсов.

Рис.2. Объекты и отношения, определенные для разных ракурсов

Если мы определили для некоторого ракурса множество объектов O₁={A, B, C, D, R}, а наблюдая эту сцену с другого ракурса, мы выделили множество O₂={F, G, H, I, J}, то идентификация означает установление того, что объект F соответствует объекту A, B - это G и т.д.

Если удастся описать каждый объект множеством атрибутов a_i, каждый из которых характеризует некоторое отношение между этим объектом и объектом i, то задача сведется к следующему:

Пусть имеется объект A={a₁, a₂, …, a_m}, наблюдаемый в ракурсе 1, и объект B={b₁, b₂, …, b_k}, наблюдаемый в ракурсе 2. Необходимо оценить, насколько близки объекты (множества) A и B.

Для определения степени близости двух множеств можно воспользоваться следующими соображениями.

Пусть даны два подмножества A и B, причем A R и B R. Здесь R - это некоторое базовое множество. Степень близости (сходства) подмножеств можно определить следующим образом [Карпова, 2001]:

, (1)

где К = |AB| - количество совпадающих элементов в подмножествах А и В, L = |А| - мощность подмножества А, К_b = |A| - K - количество элементов в подмножестве В, которых нет в А.

Величина находится в диапазоне от 0 (полное несходство) до 1 (полное совпадение). Операция определения сходства двух множеств может являться базовой для процедуры идентификации.

3.3 Определение текущих отношений между объектами

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

Изобразим систему отношений между объектами для нашего ракурса в виде матрицы R:

Рис.3. Наблюдаемые отношения

Наблюдаемые объекты могут быть разбиты на классы. Например, класс кубиков (объекты c_i) и клетки поля (объекты f_i). Тогда подматрица CC будет определять отношения между кубиками, а остальные элементы R - расположение кубиков в клетках поля.

3.4 Доопределение фундаментального множества отношений

Пусть имеются идентифицированные в моменты времени t и t+1 (ракурс t и ракурс t+1) объекты o_i и o_j. Если в момент времени t между ними было определено некоторое отношение r(t, o_i, o_j), а в момент времени t+1 отношение r не зафиксировано, то мы полагаем, что отношение r было ложным и оно удаляется из фундаментальной матрицы отношений S. Для предотвращения повторных возникновений ложных отношений это поле может быть закрыто по записи.

Таким образом, мы получаем следующее соотношение:

(2)

Здесь R_i - текущая матрица отношений для ракурса i, а - некоторая операция сопоставления отношений.

В простейшем случае операцией сопоставления может быть логическое И:

(3)

4. Применение метода для реконструкции трехмерной сцены

Ниже мы рассмотрим упрощенный вариант реконструкции, предполагая, что сцена представляет собой плоскость, на которой расположены несколько объектов определенной формы, например, кубиков c_i. Будем также полагать, что объекты могут располагаться на некоторой сетке фиксированного шага, т.е. в фиксированных позициях - клетках - f_i, количество которых невелико. Несмотря на такие сильные упрощения, эта ситуация вполне уместна, когда мы говорим, например, о рабочей зоне некоторого робота-манипулятора.

Для простоты изложения будем считать, что имеется три кубика A, B и C, а поля называются f₁, f₂, …, f₉, см. рис.1.

Таким образом, мы имеем следующее генеральное множество:

Щ={A, B, C, f₁, f₂, …, f₉}

Выделение множества объектов. Будем выделять объекты, наблюдая сцену под разными ракурсами, рис.4. Для наглядности ракурсы выбраны с углом поворота примерно 90.

Рис.4. Различные ракурсы сцены

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

Идентификация объектов. Как уже говорилось, в общем случае идентификация является самой сложной операцией. Но в нашей задаче вполне можно переложить почти всю эту работу на систему предварительной обработки и выделения объектов. Ряд идентифицирующих признаков можно определить, исходя из геометрических соображений. Например, целесообразно учесть некоторые инвариантные, не зависящие от ракурса отношения, такие, как:

· отношение "левее/правее" для объектов, находящихся на одном уровне;

· отношение "быть сверху" и т.п.

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

Тем не менее, будем полагать, что у нас однозначно, на всех ракурсах идентифицируются все наблюдаемые объекты.

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

Например, на ракурсе 4, рис.3., кубик C вовсе не виден, а на ракурсе 1, рис.3., понять, что кубик C находится на кубике A в поле f₅ можно лишь при:

1) выборе более удачного ракурса (например, вид сверху);

2) определив множество ракурсов "вокруг".

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

Таким образом, мы строим отношения, которые по природе своей могут быть неоднозначными:

Рис.5. Отношения, соответствующие ракурсам 1-4

Символом 'X' отмечены поля, означающие отношение "находиться на". Символ 'u' означает отношение "быть над". Это - уже отношения между кубиками. Отношения, как уже говорилось, могут быть неоднозначными. Например, для ракурса R(1) наличие в строке двух элементов 'X' означает неопределенность: объект A может находиться как в поле f₅, так и в поле f₈. Это обусловлено неоднозначностью проекции: никто ведь не запрещает кубику A находиться "в воздухе". Все это - результат неявно заданных геометрических отношений, которые определяют множество вариантов расположения объектов c_j относительно f_i и друг друга.

Доопределение фундаментального множества отношений. Устранение этих неоднозначностей позволяет определить фундаментальное множество отношений S. Для этого воспользуемся формулой (3) и получим в результате:

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

Заключение

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

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

Литература

1. [Абрамов и др., 1998] Абрамов В.В., Киричук В.С., Косых В.П., Перетягин Г.И., Попов С.А. Реконструкция трехмерных поверхностей по двум проекциям при отслеживании камерой заданной точки сцены. //Автометрия, 1998, №5, с. 3-16.

2. [Дуда и др., 1976] Дуда Р., Харт П. Распознавание образов и анализ сцен: Пер. с англ. -М.: Мир, 1976, 511 с.

3. [Карпова, 2001] Карпова И.П. Анализ ответов обучаемого в автоматизированных обучающих системах // Информационные системы, 2001, № 11. - с. 49-55.

4. [Марр, 1987] Марр Д. Зрение. Информационный подход к изучению представления и обработки зрительных образов: Пер. с англ. -М.: Радио и связь, 1987, 400 с.

5. [Назиров, 2011] Техническое зрение в системах управления мобильными объектами-2010: Труды научно-технической конференции-семинара. Вып. 4 / Под ред. Р.Р. Назирова.-- М. : КДУ, 2011.-- 328 с.

6. «Интегрированные модели и мягкие вычисления в искусственном интеллекте». Сб. научных трудов VI-й Международной научно-практической конференции (Коломна, 16-19 мая 2011). В 2-х томах. Т.1. -М.: Физматлит, 2011, с.407-415

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