Федеральная служба по интеллектуальной собственности Российской Федерации выдала свидетельство о государственной регистрации программы для ЭВМ № 2025692376 на «Систему иерархического разбиения облака точек», разработанную сотрудником Нижегородского государственного технического университета им. Р.Е. Алексеева (НГТУ) Глумовой Екатериной Сергеевной.
Программа реализует алгоритм разбиения трехмерного пространства, представленного набором точек (облака точек), на семантически-ориентированные блоки. Алгоритм разбиения адаптируется к локальной плотности распределения точек и местному распределению точек вдоль одной из осей (чаще всего, ось OZ).
В основе системы лежит алгоритм иерархического разбиения трехмерного пространства, который чаще всего используется при трассировке лучей. Облако точек подвергается сначала равномерному разбиению, затем полученные блоки объединяются на основе критерия распределения плотности. Процедура оценки локальной плотности в каждом блоке и объединение некоторых блоков приводит к формированию кластеров, границы которых ближе к естественным границам объектов, описываемых облаком точек.
Для разбиения облака точек также используются алгоритмы кластеризации, например, K-Means и DBSCAN. Но данные алгоритмы требуют больших вычислительных ресурсов и слабо подвергаются масштабированию для использования для облаков точек большого битового объема (например, для облаков точек промышленных зданий).
Также стандартизированной практикой является использование пространственных структур разбиения пространства, таких как octree-дерево и модификации их построения.
Решение данной задачи направлено на повышение степени автоматизации обработки данных лазерного сканирования. Полученные облака точек легче подвергаются процессам сегментации и извлечения примитивов, что важно для задач моделирования.
