Прореживание облака точек

Задача

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

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

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

Решение

Основываясь на предварительных предположениях о свойствах исходных данных, разработчики компании "Программные технологии" выбрали для прореживания один из алгоритмов итеративного упрощения, описанный в статье «Meshfree thinning of 3D point cloud» (Dyn and Iske, 2007). Сущность этого алгоритма заключается в следующем: мы последовательно удаляем из массива точек наименее значимые точки. Определение наименее значимых точек происходит в процессе итеративной процедуры утоньшения нижеследующим образом.

1. Для каждой точки вычисляем аппроксимацию касательной плотности в окрестности этой точки, используя широко известный метод главных компонент (principal component analysis).
2. Реконструируем локальную поверхность с центром в данной точке, используя только активные (т.е. неотфильтрованные нашим процессом на более ранних этапах) близкие точки. Здесь применяется метод радиально-базисных функций (radial basis functions).
3. Вычисляем меру значимости данной точки как отклонение построенной локальной аппроксимации поверхности от текущей точки, а также от близких к ней точек, удаленных в процессе утоньшения.

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

Компьютерная реализация этого процесса требует использования дополнительных структур данных, а именно красно-черного сбалансированного двоичного дерева, упорядочивающего точки по их значимостям, которое удобно для быстрого поиска и удаления минимального элемента; и трехмерного kd-дерева, которое хранит точки для быстрого нахождения соседей. Кроме того, на каждом шаге мы должны пересчитывать максимальную кубическую плотность данных (количество точек на квадратный метр) и сравнивать ее с требуемой плотностью.

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

Также в процессе процедуры мы на первом шаге отфильтровываем точки границы, используя критерий открытого угла (open-angle criterion). Согласно ему точка считается граничной, если в проекции ее окрестности на построенную касательную плоскость проекции близких точек лежат внутри сегмента с достаточно большим углом (например, 160 градусов). Для иллюстрации см. нижеприведенный рисунок.