Расширение обобщенного преобразования Хафа для выявления 3D объектов в данных лазерного дальномера

Аннотация

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

ВВЕДЕНИЕ

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

Существующие подходы к выявлению объектов в диапазоне данных можно разделить на две основные категории: управляемые данными подходы и подходы на основе моделей. Управляемые данными подходы основаны главным образом на сегментации (Khoshelham, 2006; Rottensteiner и Briese, 2003; Sithole, 2005), кластеризации (Филин, 2002; Vosselman, 1999) и классификации (Форлани и др., 2006;. Oude Elberink и Маас, 2000). Хотя эти методы обычно применяются к лазерным дальномерам данных 2.5D поверхности, их применение в более сложных сценах 3D является не всегда возможно. Например, в лазерном диапазоне данных промышленных установок многие объекты частично окклюдированные и этими методами не удается правильно определить эти объекты в данных. Модельно управляемые подходы, напротив, являются более надежными в присутствии частичной окклюзии, так как они включают некоторые формы знания о форме объекта. Модель объекта может быть представлена в частности представления в виде набора вокселей шаблонов (Greenspan и Буланже, 1999) или поворачивающимися изображениями (Джонсон и Эбер, 1999), которые сопоставляются с данными или как набор параметров, которые математически определяют объект. В последнем случае, преобразование Хафа (Дуда и Харт, 1972; Хаф, 1962) было использовано для определения параметров модели, а также точек данных, относящихся к объекту (Olson, 2001).

Применение преобразования Хафа ограничивается простыми объектами, которые могут быть представлены несколькими параметрами, такими как самолеты, шары и цилиндры. Vosselman и соавт. (2004) описывают основанные на преобразовании Хафа методы для обнаружения самолетов и сфер в облаке точек. Rabbani (2006) разработала расширение этого метода, который может быть использован для обнаружения цилиндров. На рисунке 1 показано применение преобразования Хафа обнаружения цилиндров в облака точек. Как видно, изогнутые части присоединенные к цилиндрам не были извлечены, потому что эти части не могут быть выражены в параметрической формы с несколькими параметрами.

Эта статья сосредоточена на выявлении 3D-объектов произвольной формы в облаке точек. Целью данной работы является разработка нового расширения преобразования Хафа, которое может быть использовано для обнаружения экземпляров комплексной объектной модели в данных лазерного дальномера, независимо от масштаба и ориентации объекта.

Работа состоит из пяти разделов. В разделе 2 содержится обзор стандартного и обобщенно преобразования Хафа применяемого к 2D изображениям. В разделе 3 описано принципы 3D обобщенного преобразования Хафа. Дискуссия о вычислительной сложности метода представлена в разделе 4. Выводы появляться в разделе 5.

2 Обзор стандартного и обобщённого преобразования Хафа

Преобразование Хафа является хорошо известным методом для обнаружения объектов в 2D изображениях. Стандартное преобразование Хафа применимо к объектам аналитической формы, таким как прямые линии, окружности и эллипсы, тогда как с обобщенным преобразованием Хафа любую произвольную кривую можно обнаружить на 2D-изображении. В следующих разделах кратко описываются стандартные и обобщенные преобразования Хафа.

2.1 Стандартное преобразование Хафа

Идея преобразования Хафя для выявления прямых на изображениях впервые была введена Хафом в 1962. В оригинальном преобразовании Хафа прямая линия параметризировалась как у = aх + b с двумя параметрами a и b. Согласно числу параметров, 2D-пространство параметров сформировано таким образом, что каждой точке в параметрическом пространстве изображения соответствовала линия b = -t + y. Множеству точек изображения, которые лежат на одной линии у = aх + b на исходном изображении соответствует количество линий в пространстве параметров, которые пересекаются в точке (t, b). Поиск этой точки пересечения, таким образом, есть базисом при обнаружении линий в преобразовании Хафа. Параметрическое пространство реализуется в виде дискретного массива аккумулятора, состоящих из нескольких контейнеров, которые получают голоса от граничных пикселей изображения. Точка пересечения определяется путем нахождения контейнера, который получает максимальное количество голосов.

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

2.2 Обобщенное преобразование Хафа

Баллард в 1981 году предложил обобщение преобразование Хафа для выявления непараметрических объектов произвольной формы в насыщенных 2D изображениях. В обобщенном преобразовании Хафа модель объекта хранится в так называемой R-табличном формате. Выбирается произвольная точка отсчета для объекта и для каждого граничного пикселя объекта вычисляется направление градиента так же как длина и направление вектора, соединяющего этот граничный пиксель и точку отсчета (рис. 2).

Направление градиента φ служит в качестве индексов в R-таблицу, чтобы найти длину, r, и направление, β, соединяющих векторов. Таблица 1 иллюстрирует общий вид R-таблицы. Реконструкция модели объекта из R-таблицы очень проста:

где (Xc, Yc) и (Xp, Yp) соответственно координаты точки отсчета и точки на границе объекта. Однако при обнаружении модели объекта на изображении координаты точки отсчета не известны. Двухмерный массив аккумулятор, впрочем, состоит с двух параметров точки отсчёта, так же как и оси координат. Для каждого пикселя изображения получаем направление градиента и далее смотрим в R-таблицу. Соответствующие наборы r и β значений используются для вычислений в формуле 1 и в результате полученные Xс и Yc значения указывают на ячейки аккумуляторного массива, которые должны получить право голоса (то есть увеличить своё значение). После завершения этого процесса для всех граничных пикселей изображения, ячейка аккумуляторного массива с максимальным значением указывает на точку отсчета и количество пикселей искомого объекта, проголосовавших за неё.

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

2.3 Модификации преобразования Хафа

Было предложено несколько измененных вариантов преобразования Хафа для повышения эффективности этого метода. Иллингворт и Киттлер в 1988 году предоставили обзор этих методов. Дуда и Харт в 1972 году предложили модификацию стандартного преобразования Хафа путем замены оригинальной склон-перехват параметризации прямых на полярную, угол-радиус параметризацию. Полярная параметризация ведет к ограничению пространства параметров, в отличие от оригинальной параметризации, и, следовательно, к большей вычислительной эффективности. Они также показали, что стандартное преобразование Хафа может быть использовано для обнаружения более общих кривых на изображении. Градиент взвешенное преобразование Хафа как это указано в обобщении Балларда, было впервые введено O'Gorman и Clowes в 1976 году. Вывод информации ориентации края устанавливает очень малые вычислительные затраты, но значительно повышает эффективность метода. Другие методы, которые были показаны, чтобы повысить эффективность преобразования Хафа, включают Адаптивное преобразование Хафа (Иллингворт и Киттлер, 1987), Иерархическое преобразование Хафа (Princen и соавт., 1990) и Рандомизированное преобразование Хафа (Xu и соавт., 1990).

3. Расширение обобщённого преобразования Хафа к 3D-данным

В этом разделе мы представляем расширение обобщенного преобразования Хафа до 3D данных. В последующих частях статьи метод будет называться 3D GHT. 3D GHT следует тому же принципу, как обобщенное преобразование Хафа, как описано в разделе 2.2. Основным отличием является то, что вектор градиента заменяется вектором нормали поверхности. Вектор нормали может быть получен за счет триангуляции поверхности объекта или подгонкой плоскостей к небольшому множеству точек в локальной окрестности. Векторы подключают каждый треугольник к произвольной опорной точке (точке отсчёта), которая хранится в R-таблице как функция координат вектора нормали. Вектор нормали ограничен единичной длиной и, следовательно, определяется двумя углами ориентации, φ и ψ, как показано на рисунке 3.

Подключенный вектор определяется двумя углами ориентации, α и β, также длиной R. Эти параметры могут быть получены из координат точки отсчета и граничной точки объекта:

Это оформляет результаты в 2D R-таблицу, где все подключенные вектора R хранятся в ячейках, координатами которых есть углы ориентации векторов нормали. Реконструкция модели объекта из R-таблицы осуществляется путем расширения формулы (1) к 3D пространству:

где α и β обозначают углы ориентации вектора, который соединяет точку P (точка объекта) с опорной точкой S. Для выявления 3D-модели объекта в облаке точек трех координат опорной точки имеем неизвестные параметры. Таким образом, формулы, приведенным в (3) преобразуем так, чтобы выразить неизвестные параметры в как функцию от известных величин:

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

1. Построить 3D-аккумуляторный массив с тремя параметрами точки отсчёта в качестве осей;
2. Вычислить вектор нормали для каждой точки облака точек и поднять R векторов с координатами (φ, ψ) в 2D R-таблице;
3. Оценить уравнение (4) с соответствующими наборами R, α и β значениями для получения Xс, Yс и Zс;
4. Отдать голос (прирост) в ячейку накопительного массива, соответствующую каждому набору Xc, Yc и Zc величин;
5. Повторить процесс голосования для всех точек облака точек;
6. Ячейка с максимальным количеством голосов указывает на точку отсчета, 3D-точки, которые проголосовали за эту ячейку, принадлежат экземпляру искомого объекта в облаке точек.

На практике объект отображается в диапазоне данных с произвольным углом вращения и изменяющимся масштабом. Чтобы дополнительно учесть параметры вращения и масштаба, уравнение (4) изменяется следующим образом:

где c = (Xc, Yc, Zc )^T, p = (Xp , Yp, Zp)^T, r = (R*sin(α)*cos(β), R*sin(α) sin(β), r*cos(α))^T, s – фактор масштаба, Mx, My и Mz – матрицы поворота вокруг осей x, y, z соответственно. Присоединение фактора масштаба и трех параметров вращения приводит к увеличению пространства Хафа до семи мерного. Для оценки уравнения (5) и голосов для ячеек аккумулятора, 4D пространство учитывает весь диапазон коэффициентов масштабирования и углов поворота. Это означает, что применение классического метода 3D GHT к обнаружению объектов может быть очень ресурсоёмким. Таким образом, стратегии снижения затрат, такие как адаптивные, иерархические и смешанные схемы голосования, имеют большое значение в алгоритме 3D GHT.