Программирование, 2020, № 1, стр. 3-14

1. ВВЕДЕНИЕ

В настоящей статье представлены результаты дальнейшего развития подхода к решению проблемы 3D SLAM в динамической сцене, опубликованного авторами в [1]. Некоторое представление о состоянии дел в этом направлении можно получить из работ [2–12], краткий обзор которых сделан в [1]. Была отмечена недостаточная степень универсальности существующих решений и не всегда приемлемая эффективность программно-алгоритмических средств для практических приложений.

В [1] был изложен подход, основанный на применении визуальной одометрии, использовании точечной модели объектов и реализации оригинальной алгоритмической базы для идентификации и обработки статических и динамических объектов (ДО) сцены без априорного знания о “статике”. Под  ДО подразумеваются движущиеся объекты с непредсказуемыми моментами времени появления и исчезновения в сцене. Термин “статика” объединяет все неподвижные объекты в сцене. Однако полученные оценки эффективности первой реализации подхода указали на необходимость совершенствования разработанной алгоритмической базы. Основной недостаток заключался в генерации недостаточного числа точек в формируемых 3D моделях динамических объектов, что сказывалось на точности локализации объектов и качестве реконструируемых поверхностей объектов.

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

2. ОБЩИЙ ПОДХОД

Решается задача идентификации и восстановления движения динамических объектов в априори неизвестной обстановке по изображениям, фиксируемым стереокамерой, установленной на автономном роботе. Предполагается, что в дополнение к оптической информации поступают и данные от 3D сканера (или от его виртуального аналога – программной реализации на базе стереокамеры [13]).

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

– применении точечного представления объектов сцены;

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

– разработке алгоритмической базы, направленной на решение ключевых задач рассматриваемой проблемы, а именно:

– выделение ДО и генерация их 3D точечных моделей,

– выделение статической части сцены и вычисление траектории движения камеры,

– идентификация ДО, сформированных в разные моменты времени (в разных позициях траектории движения камеры),

– вычисление траекторий собственного движения ДО на основе декомпозиции комплексного движения объектов, фиксируемого камерой (движение камеры плюс собственное движение объекта).

Предлагаемое в настоящей работе развитие ранее описанного в [1] подхода состоит в реализации следующих решений:

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

– в дополнение к ранее разработанному алгоритму формирования 3D точечных моделей ДО на основе критерия “жесткости” предлагается алгоритм “затравочного” типа с использованием критерия “связности точек”;

– задача идентификации и вычисления траектории движения решается также и применительно к ДО, изменяющим свою форму при движении.

Для восстановления движения камеры и объектов сцены применяется метод визуальной навигации (авторские реализации его модификаций описаны в [14–16]). Метод следует классической схеме визуальной одометрии:

– установление соответствий 2D точечных особенностей на двух парах снимков, соответствующим двум соседним расчетным позициям на траектории. Для поиска соответствий точечных особенностей на левом и правом снимке стереопары используется широко применяемый детектор SURF (Speeded Up Robust Features) [17]. А для отслеживания точечных особенностей на двух снимках, соответствующих двум соседним расчетным позициям на траектории, применяется известный трекер KLT (Kanade–Lucas–Tomasi feature tracker) [18];

– построение методом триангуляции лучей по сопоставленному на стереопаре текущей позиции множеству точечных особенностей соответствующего множества 3D точек (3D облако). Аналогичным образом строится 3D облако для стереопары предшествующей позиции. Каждое 3D облако описывается в локальной системе координат (СК) позиции (рис. 1);

Рис. 1.

Выделение единого сопоставленного множества особенностей на изображениях двух стереопар. Формирование 2-х 3D облаков.

– вычисление по сопоставленным 3D облакам матрицы геометрического преобразования, описывающего относительное перемещение камеры/робота (6 DOF (degrees of freedom)) в локальной СК.

Плотное 3D точечное представление видимой части сцены в каждый момент времени формируется, как было отмечено выше, за счет объединения двух множеств 3D точек, принадлежащих объектам, – точек, получаемых обработкой изображений стереопар (3D облако), и 3D точек, непосредственно измеряемых 3D сканером, или его виртуальным аналогом. Заметим, что первому множеству 3D точек соответствует сопоставленное множество в предшествующей позиции (построенное по сопоставленным особенностям). Это соответствие используется в алгоритме установления связи/соответствия между ДО соседних позиций. Реализуемое плотное точечное представление дает возможность наряду с другими методами выделения объектов в видеопотоке применять и метод, основанный на критерии “связности”, учитывающим непрерывность поверхности объекта.

3. ПОСТРОЕНИЕ ТОЧЕЧНОЙ МОДЕЛИ ДИНАМИЧЕСКОГО ОБЪЕКТА

Задача построения 3D точечных моделей статических и динамических объектов сцены решается на исходном неструктурированном множестве 3D точек (видимых в данной позиции камеры). Все множество 3D точек в текущей позиции i, в которой должны быть сформированы точечные модели статических и динамических объектов, состоит из трех независимо формируемых 3D множеств (см. рис. 2). Здесь:

Рис. 2.

Объединенное множество исходных 3D точек на текущем шаге: $M_{{i - 1,i}}^{i}$ + ${{R}_{i}}$ + $M_{{}}^{i}$.

G_{i – 1} – множество 2D особенностей, сопоставленных на изображениях стереопары позиции (i – 1) (на предыдущем шаге). G_{i – 1, i} множество 2D особенностей в позиции i, прослеженных от G_{i – 1}. G_i‑множество 2D особенностей, сопоставленных на изображениях стереопары позиции i (на текущем шаге). G_{i, i +1} – множество 2D особенностей в позиции i + 1, прослеженных от G_i. ${{M}^{{i - 1}}}$(G_{i – 1}) – множество 3D точек, построенное в СК позиции (i – 1) по особенностям G_{i – 1} (сформировано на предыдущем шаге). $M_{{i - 1,i}}^{i}$ (G_{i – 1, i}) – множество 3D точек, построенное в СК позиции i по особенностям G_{i – 1, i}. 3D точкам этого множества сопоставлены точки множества ${{M}^{{i - 1}}}$(G_{i – 1}) в силу выполняемого на текущем шаге прослеживания/сопоставления соответствующих 2D особенностей. ${{M}^{i}}$(G_i) – множество 3D точек, построенное на текущем шаге в СК позиции i по 2D особенностям G_i. $M_{{i,i + 1}}^{{i + 1}}$(G_{i, i +1}) – множество 3D точек, которое должно быть построено на следующем шаге в СК позиции (i + 1) по особенностям G_{i, i +1}. 3D точкам этого множества будут сопоставлены точки множества ${{M}^{i}}$(G_i) в силу прослеживания/сопоставления соответствующих 2D особенностей на шаге (i + 1). ${{R}_{i}}$ – плотное множество 3D точек, полученное “дальномером” на текущем шаге в позиции i.

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

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

Следует также отметить, что согласно предлагаемой схеме обработки, формируемое на текущем шаге множество 2D особенностей G_i сохраняется, и используется двояким образом. Во-первых, на текущем шаге по сопоставленным на стереопаре особенностям строится множество 3D точек ${{M}^{i}}$(G_i). А, во-вторых, на следующем шаге (в позиции (i + 1)) эти особенности прослеживаются с помощью KLT и используются для построения множества 3D точек $M_{{i,i + 1}}^{{i + 1}}$, которое будет сопоставлено с Mⁱ. Таким образом, устанавливается связь позиций i и (i + 1), что необходимо для идентификации ДО на протяжении всего времени их движения в поле зрения камеры.

Построения 3D точечных моделей статических и динамических объектов сцены выполняется в несколько этапов. Вначале генерируются т.н. “затравочные” точки, каждая из которых принадлежит какому-то объекту. При этом, возможно, какие-то “затравочные” точки могут принадлежать одному и тому же объекту. Затем выполняется сортировка точек исходного множества по группам (отдельным подмножествам точек), порожденным “затравочными” точками, т.е. генерация 3D точечных моделей объектов. Отбор точек осуществляется применением двух критериев, – критерия “связности” и критерия “жесткости”, о которых говорится ниже. Тот факт, что одному объекту могут принадлежать несколько “затравочных” точек, и, соответственно, несколько отдельных групп точек, не противоречит этой методике, поскольку такие группы объединяются в единую 3D модель объекта на основе критерия “сходства движения”. Поскольку сформированные группы точек могут относиться, как к статическим, так и к динамическим объектам, в последующем изложении будем использовать понятие динамической группы (ДГ), являющейся точечным представлением ДО или его части.

3.3. Алгоритм формирования групп точек по критерию связности

Согласно алгоритму “затравочного” типа обработка точек исходного множества 3D точек начинается с затравочной точки (заведомо принадлежащей объекту). Для каждой пары соседних точек (очередная анализируемая точка и предшествующая точка, получившая статус принадлежности к группе) проверяется выполнение критерия “связности”. Согласно критерию, сравниваются расстояния от камеры до текущей и до предшествующей соседней точки (рис. 3):

Рис. 3.

Проверка принадлежности 3D точки объекту по критерию связности.

Пусть ε (r_k, r_{k – 1}) = |dr|/|dφ|, где dφ – смещение по углу между лучами для двух соседних точек, а |dr| = |r_k – r_{k – 1}|. Тогда величина coherence = ε2 (r_{i + 1}, r_i)/ε1 (r_{i – 1}, r_i) будет характеризовать связность/непрерывность поверхности. Если coherence > пороговой величины, то имеет место разрыв поверхности, т.е. выход на границу объекта. В противном случае текущая точка принадлежит группе (объекту).

3.4. Алгоритм объединения групп точек со сходным движением

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

Исходим из предположения, что в каждой группе присутствуют точки множества ${{R}_{i}}$ и множества $M_{{i - 1,i}}^{i}$. Алгоритм объединения основывается на применении критерия “жесткости”, который позволяет оценить сходство движения точек. Заметим, что алгоритм применим только к сопоставленным в двух позициях точкам (точки множества ${{R}_{i}}$ не сопоставлены). Обозначим множество сформированных на текущем шаге групп через G. Для каждой группы ${{g}_{k}}$ ∈ G ищем на множестве {G – ${{g}_{k}}$} группы со схожим движением, применяя указанный критерий. Пусть группа ${{g}_{l}}$ ∈ G проверяется на предмет объединения с группой ${{g}_{k}}$. Тогда согласно критерию “жесткости” рассматриваются две пары точек (рис. 4). В качестве первой точки в первой паре берется точка ${{P}^{{{{g}_{k}}}}}$ в группе ${{g}_{k}}$, принадлежащая множеству $M_{{i - 1,i}}^{i}$. В качестве второй точки берется точка ${{P}^{{{{g}_{l}}}}}$ в группе ${{g}_{l}}$, также принадлежащая множеству $M_{{i - 1,i}}^{i}$. Во второй паре в качестве первой точки берется точка ${{P}^{{g_{k}^{'}}}}$, являющаяся прообразом точки ${{P}^{{{{g}_{k}}}}}$. А в качестве второй точки берется соответственно точка ${{P}^{{g_{l}^{'}}}}$, являющаяся прообразом точки ${{P}^{{{{g}_{l}}}}}$. Обе точки принадлежат множеству $M_{{i - 1,i}}^{{i - 1}}$, заданному в СК позиции (i – 1). Построим критерий “жесткости”:

$r1 = {\text{|}}{{P}^{{{{g}_{k}}}}} - {{P}^{{{{g}_{l}}}}}{\text{|}},\quad r2 = {\text{|}}{{P}^{{g_{k}^{'}}}} - {{P}^{{g_{l}^{'}}}}{\text{|}}.$

Рис. 4.

Объединение группы ${{g}_{l}}$ с группой ${{g}_{k}}$ по критерию “жесткости”.

Если r1 = r2 (с определенной пороговой погрешностью) для нескольких точек ${{P}^{{{{g}_{l}}}}}$, то считаем, что обе группы принадлежат “статике” или одному ДО, и, соответственно, могут быть объединены.

Если в группе ${{g}_{k}}$ отсутствуют точки множества $M_{{i - 1,i}}^{i}$, то считаем, что эта группа точек принадлежит новому ДО. Таким образом, используя сопоставленные пары 3D облаков предыдущей и текущей позиции, определяем одинаковые группы со схожими движениями. После работы “алгоритма объединения” должны остаться только группы, каждая из которых полностью представляет ДО.

4. СОПОСТАВЛЕНИЕ ДИНАМИЧЕСКИХ ГРУПП ТОЧЕК СОСЕДНИХ ПОЗИЦИЙ

Поскольку формирование динамических групп (ДГ) выполняется независимо при обработке каждой позиции траектории камеры, необходимо решать задачу идентификации каждой группы по отношению к группам предыдущей позиции. Т.е. необходимо устанавливать соответствие двух ДГ, фиксируемых/наблюдаемых в разные моменты времени, но представляющих один и тот же объект. Это требуется для расчета траектории движения каждого объекта на протяжении всего времени и для построения его анимационной 3D модели. Трудность заключается в том, что в каждой позиции формирование ДГ точек, принадлежащих ДО, выполняется безотносительно к предшествующей позиции. Дополнительная трудность – непредсказуемое появление новых ДО и исчезновение из сцены прежних ДО, а также необходимость различать недеформируемые и деформируемые ДО. В рассматриваемых ниже алгоритмах установления соответствия между ДГ соседних позиций используется локальная матрица геометрического преобразования, описывающая относительное совместное движение объекта и камеры. Здесь следует заметить, что вычисление этой матрицы делается по-разному для недеформируемых и деформируемых ДО.

4.3. Алгоритм идентификации динамических групп точек в текущей позиции

Как было отмечено выше, для прослеживания всех ДГ на протяжении всего времени наблюдения/съемки необходимо идентифицировать каждую из ДГ на каждом очередном шаге. Это означает, что для сформированной в новой позиции ДГ требуется установить ее соответствие с одной из ДГ, сформированной в предшествующей позиции. Поскольку сформированные в каждой позиции ДГ уже разделены на два типа – недеформируемые и деформируемые группы, то поиск соответствия для сформированной в новой позиции недеформируемой ДГ осуществляется на множестве ДГ этого же типа предшествующей позиции. То же самое справедливо и для деформируемых ДГ. Такое соответствие для недеформируемой ДГ, сформированной в позиции (i), может быть установлено двумя способами. Первый способ – соответствие устанавливается алгоритмом, основанным на сравнении вычисляемых интегральных оценок геометрической близости точек этой ДГ к пространственным оболочкам ДГ в позиции (i – 1). Второй способ – соответствие устанавливается проверкой наличия сопоставленных 3D точек в двух анализируемых ДГ. Недостаток алгоритма оценки геометрической близости – вычислительная трудоемкость. Поэтому был выбран способ решения, основанный на выявлении в сравниваемых ДГ сопоставленных 3D точек, которые служат “маркерами”. Наличие таких точек в обеих группах, принадлежащих, соответственно, сопоставленным множествам $M_{{i - 1,i}}^{{i - 1}}$ и $M_{{i - 1,i}}^{i}$, подтверждает, что обе точечные модели представляют один и тот же ДО. Поэтому алгоритм идентификации некоторой ДГ в текущей позиции i по отношению к предыдущей позиции состоит в последовательной проверке всех ДГ в предыдущей позиции на наличие в обеих группах общих сопоставленных точек, принадлежащих указанным множествам. Иллюстрация к работе алгоритма показана на рис. 5. В случае успешного сопоставления тестируемой ДГ в позиции i ей присваивается идентификатор ее прообраза в позиции (i – 1). Одновременно по принципу унаследования свойств определяется и тип ДО – “недеформируемый” или “деформируемый”. Если такого сопоставления не обнаружено, то это значит, что ДГ относится к новому ДО. Заметим, что возможно применение обоих рассмотренных критериев (алгоритмов) для повышения достоверности идентификации ДГ.

Рис. 5.

Идентификация ДГ. Группа точек ДО $DG_{i}^{{i{{d}_{{gr}}}}}$, сформированная в позиции i, сопоставлена с $DG_{{i - 1}}^{k}$ в позиции (i – 1) и не сопоставлена с $DG_{{i - 1}}^{l}$.

Для нового ДО необходимо определить его тип. Определение типа делается алгоритмом, основанным на применении к точкам сформированной ДГ критерия “жесткости”. Точки ДГ проверяются критерием на сходство движения. Для проверки используются точки, принадлежащие сопоставленным множествам $M_{{i - 1,i}}^{{i - 1}}$ и $M_{{i - 1,i}}^{i}$.

При сходстве движения точек квалифицируем ДО как “недеформируемый”, в противном случае – как “деформируемый”.

5. О ВЫЧИСЛЕНИИ ТРАЕКТОРИЙ И РЕКОНСТРУКЦИИ ДИНАМИЧЕСКИХ ОБЪЕКТОВ

Каждый ДО характеризуется своим временем жизни в сцене от момента времени его появления в сцене t_b до момента времени выхода его из сцены t_e. С моментом времени t_b связана начальная система координат данного объекта. В этой СК будет описываться собственное движение объекта, безотносительно к движению камеры. Также в этой СК будет выполняться генерация полной 3D модели этого объекта – т.е. в нее будут помещены все полученные виды объекта с последующим объединением. В качестве такой начальной СК объекта выберем (без ущерба общности) локальную СК камеры/робота в позиции b. Координаты точек ДО из его начальной позиции b (а также из других позиций) могут быть преобразованы согласно методу визуальной одометрии в СК начальной позиции траектории робота (t₀). В свою очередь, при наличии преобразования, связывающего СК начальной позиции траектории робота с некоторой внешней системой координат, можно получить координаты объектов сцены во внешней системе координат. Назовем эту внешнюю СК мировой системой координат (МСК). В качестве МСК часто используют (без ущерба общности) СК робота в начальной позиции, предполагая, что упомянутое выше преобразование во внешнюю СК известно. Собственное относительное перемещение ДО за время [t_{i – 1}, t_i] будем оценивать вычислением локальной матрицы геометрического преобразования на шаге [(i – 1), i] (см. (1)).

Вычисление траектории ДО. В качестве траектории ДО можно рассматривать траекторию движения любой его точки из начальной позиции b (момент времени t_b) в конечную позицию e (момент времени t_e). Построить такую траекторию можно вычисляя последовательно локальные матрицы геометрического преобразования $H_{{i - 1,i}}^{{i{{d}_{{gr}}}}}$ (рис. 6), которые определяют собственное движение ДО в интервалах времени t_b – t₁, t₁ – t₂, … t_{i – 1} – t_i, … t_{e – 1} – t_e.

Рис. 6.

Вычисление матриц геометрического преобразования, определяющих собственное движение динамического объекта. Позиция b – начало движения ДО в сцене.

Из (1) следует:

То есть, по вычисленному движению камеры ($H_{{i - 1,i}}^{{camera}}$) и совместному движению объекта $и$ камеры ($H_{{i - 1,i}}^{{joint,i{{d}_{{gr}}}}}$) мы можем вычислить матрицу геометрического преобразования координат $H_{{i - 1,i}}^{{i{{d}_{{gr}}}}}$, определяющую собственное локальное перемещение ДО. Тогда преобразование 3D координат точки $P_{l}^{{i{{d}_{{gr}}}}}$ объекта $i{{d}_{{gr}}}$ на шаге [(i – 1), i] определяется соотношением:

Матрица результирующего преобразования ДО с именем $i{{d}_{{gr}}}$ за время [t_b, t_i] (собственное относительное движение) получается перемножением соответствующих локальных матриц:

С учетом (4) координаты точек объекта $i{{d}_{{gr}}}$ в момент времени t_i связаны с координатами точек в начальной СК этого объекта матрицей $H_{{b,i}}^{{i{{d}_{{gr}}}}}$:

Для помещения всех ДО и траекторий их движения в единую СК, которой является МСК, необходимо иметь преобразование из начальной СК ДО в МСК. Поскольку в качестве МСК мы рассматриваем локальную систему координат камеры в начальный момент времени, то $H_{{WCS,b}}^{{camera}}$ = $\mathop \prod \limits_{k = 0}^{k = b - 1} H_{{k,k + 1}}^{{camera}}$. Соответственно, координаты рассматриваемой точки $P_{l}^{{{{t}_{i}},i{{d}_{{gr}}}}}$ в МСК могут быть получены как:

3D реконструкция ДО. Чтобы построить 3D модель объекта по видам объекта, полученным из разных позиций камеры (в разные моменты времени), необходимо совместить эти виды в СК начальной позиции этого ДО. Это реализуется с помощью следующих операций:

1) Из каждой позиции i траектории камеры видимые точки $P_{n}^{{С{{К}^{i}},i{{d}_{{gr}}}}}$ объекта $i{{d}_{{gr}}}$, построенные по стереопаре в СКⁱ, помещаются в СК начальной позиции этого ДО, т.е. в СК позиции b камеры (момент появления в сцене этого ДО). Это делается с помощью матрицы $H_{{b,i}}^{{joint,i{{d}_{{gr}}}}}$, которая учитывает и движение камеры, и преобразование координат точек ДО, связанное с его перемещением:

$P_{n}^{{С{{К}^{{i,b}}},i{{d}_{{gr}}}}}$ – 3D точка с номером n объекта $i{{d}_{{gr}}}$, преобразованная из СКⁱ в СК^b.

Матрица $H_{{b,i}}^{{joint,i{{d}_{{gr}}}}}$ согласно методу визуальной одометрии получается перемножением соответствующих локальных матриц:

$H_{{b,i}}^{{joint,i{{d}_{{gr}}}}}$ = $\mathop \prod \limits_{k = b}^{k = i - 1} H_{{k,k + 1}}^{{joint,i{{d}_{{gr}}}}}$, где локальная матрица $H_{{k,k + 1}}^{{joint,i{{d}_{{gr}}}}}$ определяет совместное движение камеры и ДО из позиции k в позицию (k + 1).

2) Чтобы получить координаты точек объектов всех видов (ракурсов) в МСК необходимо применить преобразование ($H_{{WCS,b}}^{{camera}}$)^–1, где $H_{{WCS,b}}^{{camera}}$ = $\mathop \prod \limits_{k = 0}^{k = b - 1} H_{{k,k + 1}}^{{camera}}$.

Таким образом, возможность пересчета координат точек каждого ДО в МСК позволяет реконструировать их траектории и 3D модели в едином координатном пространстве мировой системы координат.

6. СХЕМА ОБРАБОТКИ ДАННЫХ В ЗАДАЧЕ ИДЕНТИФИКАЦИИ И ВОССТАНОВЛЕНИЯ ДВИЖЕНИЯ ДИНАМИЧЕСКИХ ОБЪЕКТОВ ПО ИЗОБРАЖЕНИЯМ

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

Вычислительная схема обработки данных на текущем шаге траектории, согласно предлагаемому подходу, состоит из выполнения следующих этапов (рис. 7):

Рис. 7.

Вычислительная схема обработки данных на текущем шаге траектории.

1. Прослеживание с помощью трекера KLT 2D множества особенностей ${{G}_{{i - 1}}}$, сформированного в позиции (i – 1) на предыдущем шаге. Построение соответствующего 3D множества $M_{{i - 1,i}}^{i}$, сопоставленного с ${{M}^{{i - 1}}}$.

2. Формирование на стереопаре изображений множества 2D особенностей ${{G}_{i}}$ и построение соответствующего 3D облака точек Mⁱ.

3. Формирование “дальномерного” плотного множества 3D точек ${{R}_{i}}$.

4. Формирование на объединенном множестве {$M_{{i - 1,i}}^{i}$ + ${{R}_{i}}$ + Mⁱ} связных групп точек затравочным алгоритмом (на критерии связности). Группы объединяют точки видимых поверхностей разных объектов или разных частей одного и того же объекта.

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

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

6. Идентификация группы точек статических объектов. Вычисление методом визуальной одометрии матрицы локального перемещения камеры по сопоставленным точкам статической части сцены (принадлежащим множествам ${{M}^{{i - 1}}}$ и $M_{{i - 1,i}}^{i}$).

Исключая из всех полученных групп группу “статика”, получаем ДГ, т.е. группы точек, принадлежащие ДО (недеформируемым и деформируемым).

7. Идентификация ДГ по отношению к ДГ предыдущей позиции.

8. Разделение деформируемых и недеформируемых ДО.

9. Вычисление собственного движения ДО.

Обработка первых двух позиций траектории отличается от приведенной схемы тем, что для позиции 1 отсутствует предыдущий шаг, и, соответственно сегментация точек по группам выполняется на множествах ${{R}_{1}}$ + $M_{{1,2}}^{1}$.

7. ВЫЧИСЛИТЕЛЬНЫЕ ЭКСПЕРИМЕНТЫ

Тестирование описанных алгоритмов осуществлялось на подводных виртуальных сценах, в которых съемка ведется с автономного подводного робота (АПР). Пример одной из сцен показан на рис. 8. В сцене присутствуют три ДО (“подводный аппарат”, “батискаф” и “дельфин”). Алгоритм формирования групп точек по критерию связности сформировал 9 групп 3D точек для данного вида (рис. 9). После работы алгоритма объединения групп точек со сходным движением сформированы 3 группы точек, принадлежащие 3-м указанным динамическим объектам и группа точек, относящаяся к рельефу дна (рис. 10). Данные объекты были прослежены с шагом = 1 кадр на сцене протяженностью в 120 кадров, длительностью 12 сек. Робот/камера и все ДО двигались по прямолинейным траекториям с разными скоростями под разными углами. Время наблюдения объектов (пребывания их в сцене) составило от 2.6 сек (26 кадров) до 6.4 сек (64 кадра).

Рис. 8.

Снимок подводной сцены в одной из позиций траектории АПР: в поле зрения камеры находятся 3 динамических объекта.

Рис. 9.

Показана проекция “вид сбоку”. Каждая из 9 сформированных групп 3D точек выделена прямоугольником.

Рис. 10.

Выделены 3 группы точек, относящихся к ДО и группа точек, представляющих рельеф дна (после работы алгоритма объединения).

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

На втором этапе оценивалась эффективность всей вычислительной схемы, в том числе, с учетом ошибок, вносимых на этапе обработки стереопар снимков (табл. 2).

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

8. ЗАКЛЮЧЕНИЕ

Рассмотрена модификация ранее предложенного авторами подхода к решению 3D SLAM задачи для динамических сцен, основанного на точечном представлении объектов. Модификация заключается в реализации более эффективной алгоритмической основы, чем это было в начальной версии, а также в реализованных возможностях генерации расширенного точечного представления (за счет применения “виртуального дальномера”) и идентификации динамических объектов с неизменяемой и изменяемой формой.

Расширенное точечное представление позволяет получать более плотные точечные модели ДО. Результаты вычислительных экспериментов на модельных сценах подтвердили правильность выбранных решений. Дальнейшее развитие работы предполагает: совершенствование алгоритмической базы; тестирование программ на разных наборах данных; решение задачи 3D реконструкции ДО с использованием вычисляемых траекторий объектов.

9. БЛАГОДАРНОСТИ

Работа выполнена при частичной финансовой поддержке РФФИ (проект № 18-07-00165).