Truncated Signed Distance Function

Truncated Signed Distance Function (TSDF, усечённая знаковая функция расстояния) — это трёхмерная скалярная функция, используемая в компьютерной графике, компьютерном зрении и робототехнике для представления геометрии поверхностей объектов. TSDF задаёт для каждой точки пространства знаковое расстояние до ближайшей поверхности, ограниченное порогом усечения. Функция широко применяется в задачах трёхмерной реконструкции, построения карт глубины, слияния данных с датчиков (например, RGB-D камер) и в системах одновременной локализации и построения карт (SLAM).

Определение и математическая основа

TSDF является модификацией классической знаковой функции расстояния (Signed Distance Function, SDF). В SDF значение в каждой точке трёхмерного пространства равно расстоянию до ближайшей поверхности, причём знак указывает, находится ли точка внутри или снаружи объекта (обычно положительное значение — снаружи, отрицательное — внутри). В TSDF это расстояние ограничивается фиксированным порогом усечения \( \delta \), что позволяет хранить и обрабатывать данные только вблизи поверхности, экономя вычислительные ресурсы и память.

Формально, для точки \( \mathbf{p} \in \mathbb{R}^3 \) TSDF определяется как:

\[ \text{TSDF}(\mathbf{p}) = \begin{cases} \text{sign}(d(\mathbf{p})) \cdot \min(|d(\mathbf{p})|, \delta), & \text{если } |d(\mathbf{p})| \leq \delta, \\ \text{null}, & \text{иначе}, \end{cases} \]

где \( d(\mathbf{p}) \) — знаковое расстояние до ближайшей поверхности, \( \delta \) — порог усечения, а null обозначает отсутствие данных (обычно кодируется как 0 или специальное значение). Значение TSDF лежит в диапазоне от \( -\delta \) до \( \delta \), причём нулевое значение соответствует точкам на поверхности.

История и развитие

Концепция знаковых функций расстояния известна в математике и физике с середины XX века, однако её применение в компьютерной графике началось в 1990-х годах. В 1996 году Брайан Керли и Левой Марк предложили использовать SDF для представления трёхмерных моделей в своей работе «A Volumetric Method for Building Complex Models from Range Images». Они ввели понятие объёмного представления, где каждая ячейка воксельной сетки хранит знаковое расстояние.

В 2001 году Ричард Ньюкомб и его коллеги из Microsoft Research разработали метод KinectFusion, который впервые применил TSDF для обработки данных с RGB-D камеры Kinect. В этой работе TSDF использовалась для слияния множества кадров глубины в единую трёхмерную модель в реальном времени. Метод стал основой для многих последующих систем трёхмерной реконструкции, включая ElasticFusion, InfiniTAM и BundleFusion.

С 2010-х годов TSDF активно применяется в робототехнике для построения карт окружающей среды, а также в нейросетевых подходах, таких как DeepSDF и Occupancy Networks, где TSDF используется как целевая функция для обучения генеративных моделей трёхмерных форм.

Представление и хранение

Воксельная сетка

Наиболее распространённый способ хранения TSDF — трёхмерная воксельная сетка (voxel grid). Пространство разбивается на кубические ячейки (воксели) фиксированного размера, каждый из которых хранит значение TSDF и вес (обычно число измерений, которые внесли вклад в данную ячейку). Размер вокселя определяет разрешение модели: чем меньше воксель, тем выше детализация, но больше требуемая память.

Для оптимизации памяти используются различные структуры данных:

• Разреженные воксельные сетки (sparse voxel grids) — хранят только ячейки, содержащие ненулевые значения TSDF, что особенно эффективно для больших пространств с пустыми областями.
• Октри (octrees) — иерархические структуры, которые адаптивно разбивают пространство на подобласти, позволяя хранить данные с переменным разрешением.
• Хэш-таблицы — используются в методах, таких как Voxel Hashing, где каждая ячейка адресуется по хэшу её координат.

Усечение и вес

Порог усечения \( \delta \) выбирается в зависимости от задачи. Обычно он составляет от нескольких миллиметров до нескольких сантиметров. Значения TSDF за пределами порога не хранятся, что позволяет ограничить область вычислений узкой полосой вокруг поверхности. Вес каждой ячейки обновляется при интеграции новых данных, что позволяет усреднять шум и повышать точность.

Применение

Трёхмерная реконструкция

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

Примеры систем:

• KinectFusion (Microsoft, 2011) — первая система реального времени, использующая TSDF для реконструкции сцены с помощью Kinect.
• ElasticFusion (2015) — расширение для динамических сцен с возможностью коррекции траектории камеры.
• BundleFusion (2017) — метод, сочетающий TSDF с техникой bundle adjustment для высокоточных реконструкций.

SLAM (Simultaneous Localization and Mapping)

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

Компьютерная графика и визуализация

TSDF применяется для рендеринга трёхмерных моделей, особенно в задачах извлечения поверхностей. Для получения полигональной сетки из TSDF используется алгоритм Marching Cubes, который находит изоповерхность на нулевом уровне (значение TSDF = 0). Этот метод широко используется в медицинской визуализации, научной визуализации и игровой индустрии.

Нейросетевые методы

С развитием глубокого обучения TSDF стала использоваться как представление для обучения нейронных сетей. Например, модель DeepSDF (2019) обучается предсказывать TSDF для заданной трёхмерной формы, что позволяет генерировать новые формы и выполнять интерполяцию между ними. Другие подходы, такие как Occupancy Networks и Neural Radiance Fields (NeRF), используют TSDF как вспомогательное представление для улучшения качества реконструкции.

Преимущества и недостатки

Преимущества

• Высокая точность — TSDF позволяет хранить информацию о поверхности с субвоксельной точностью благодаря интерполяции.
• Устойчивость к шуму — взвешенное усреднение множества измерений снижает влияние случайных ошибок.
• Эффективность — усечение ограничивает область вычислений, что снижает требования к памяти и производительности.
• Простота интеграции — новые данные легко добавляются в существующую модель.

Недостатки

• Потребление памяти — даже с разреженными структурами, TSDF требует значительного объёма памяти для больших сцен (например, целые здания).
• Ограничение по разрешению — фиксированный размер вокселя не позволяет адаптироваться к деталям разного масштаба.
• Чувствительность к движению — при быстром движении камеры или динамических объектах могут возникать артефакты.
• Сложность обработки динамики — TSDF плохо подходит для сцен с движущимися объектами без специальных модификаций.

Примеры реализации

KinectFusion (Microsoft)

Оригинальная реализация KinectFusion использует фиксированную воксельную сетку размером 512×512×512 вокселей с размером вокселя 3 мм, что даёт объём модели около 1.5×1.5×1.5 метра. Каждый воксель хранит 16-битное значение TSDF и 16-битный вес. Система работает на GPU с частотой 30 кадров в секунду.

InfiniTAM (Имперский колледж Лондона)

Открытая библиотека InfiniTAM реализует TSDF с использованием разреженных воксельных сеток и октри, что позволяет обрабатывать сцены неограниченного размера. Она поддерживает как CPU, так и GPU вычисления.

Open3D

Библиотека Open3D (Intel Labs) включает модуль для работы с TSDF, включая интеграцию кадров глубины, извлечение поверхностей и визуализацию. Она широко используется в исследованиях и промышленности.

Источники

• Curless, B., & Levoy, M. (1996). A Volumetric Method for Building Complex Models from Range Images. Proceedings of SIGGRAPH.
• Newcombe, R. A., et al. (2011). KinectFusion: Real-Time Dense Surface Mapping and Tracking. IEEE International Symposium on Mixed and Augmented Reality (ISMAR).
• Whelan, T., et al. (2015). ElasticFusion: Dense SLAM Without a Pose Graph. Robotics: Science and Systems (RSS).
• Park, J. J., et al. (2019). DeepSDF: Learning Continuous Signed Distance Functions for Shape Representation. Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR).
• Zach, C., Pock, T., & Bischof, H. (2007). A Globally Optimal Algorithm for Robust TV-L1 Range Image Integration. IEEE International Conference on Computer Vision (ICCV).
• Open3D Documentation. (2023). Truncated Signed Distance Function. Intel Labs.