Хмари точок (Point Clouds) — це колекції точок даних, які представляють 3D форми або об'єкти, і можуть містити мільйони чи мільярди точок. Хоча ці деталі можуть бути корисними, їх обробка та візуалізація ускладнюється. Для вирішення цієї проблеми часто використовують методи зменшення кількості точок (downsampling), зменшуючи їх кількість, але зберігаючи загальну структуру. Існують різні методи зменшення кількості точок, кожен з яких має свої переваги та недоліки, але всі вони намагаються зберегти цілісність оригінальних даних. Тут я розгляну 4 таких методи.
- Випадкове зменшення кількості точок (Random Downsampling)
- Зменшення кількості точок за допомогою воксельної сітки (Voxel Grid Downsampling)
- Однорідне підвибірку (Uniform Grid Subsampling)
- Збереження кривизни при вибірці (Curvature-Preserving Sampling)
Figure 1: Зменшення кількості точок. Джерело: - Link
Спочатку припустимо, що у нас є шлях до файлу PLY, з якого ми можемо витягнути його основні властивості за допомогою наступної функції. (Джерело: 3DGSGit_)
class BasicPointCloud(NamedTuple):
points : np.array
colors : np.array
normals : np.array
def fetchPly(path):
plydata = PlyData.read(path)
vertices = plydata['vertex']
positions = np.vstack([vertices['x'], vertices['y'], vertices['z']]).T
colors = np.vstack([vertices['red'], vertices['green'], vertices['blue']]).T / 255.0
normals = np.vstack([vertices['nx'], vertices['ny'], vertices['nz']]).T
return BasicPointCloud(points=positions, colors=colors, normals=normals)
1. Випадкове зменшення кількості точок (Random Downsampling)
Це простий метод для випадкового вибору підмножини точок. Однак, якщо ми надто зменшимо кількість точок, можемо втратити ключові властивості структури, оскільки точки вибираються випадковим чином. Хоч цей метод і простий, він не позбавлений певних ризиків. Крім того, цей метод є обчислювально ефективним.
def downsample_random(point_cloud: BasicPointCloud, ratio: float) -> BasicPointCloud:
"""Зменшує кількість точок у хмарі точок за вказаним коефіцієнтом."""
num_points = point_cloud.points.shape[0]
sample_size = int(num_points * ratio)
indices = np.random.choice(num_points, sample_size, replace=False)
return BasicPointCloud(points=point_cloud.points[indices],
colors=point_cloud.colors[indices],
normals=point_cloud.normals[indices])
“ratio” — це значення типу float, яке лежить між 0 і 1. Наприклад, якщо коефіцієнт дорівнює 0.2, це означає, що збережеться 20% точок.
2. Зменшення кількості точок за допомогою воксельної сітки (Voxel Grid Downsampling)
Цей метод ділить 3D простір на сітку фіксованих кубів, відомих як вокселі (voxels), і зберігає лише одну репрезентативну точку для кожного вокселя. Цей підхід ефективно зберігає загальну структуру даних, одночасно зменшуючи загальну кількість точок. Залишкові точки відображають середнє положення всіх точок у відповідному вокселі, яке обчислюється як середнє значення точок, що містяться в кожному вокселі. Додатково вибір точок можна здійснювати двома альтернативними способами: вибираючи першу точку, що потрапила у воксель, або вибираючи центроїд вокселя (якщо в ньому є точки). Спосіб вибору точки можна налаштувати відповідно до конкретних вимог.
Figure 2: Оригінальна хмара точок та зменшена хмара точок, використовуючи метод воксельної сітки.
Джерело: Link_
import open3d as o3d
def downsample_voxel_grid(point_cloud: BasicPointCloud, voxel_size: float) -> BasicPointCloud:
"""Зменшує кількість точок у хмарі точок за допомогою фільтрації воксельною сіткою."""
# Перетворюємо BasicPointCloud у формат Open3D
o3d_cloud = o3d.geometry.PointCloud()
o3d_cloud.points = o3d.utility.Vector3dVector(point_cloud.points)
o3d_cloud.colors = o3d.utility.Vector3dVector(point_cloud.colors)
o3d_cloud.normals = o3d.utility.Vector3dVector(point_cloud.normals)
# Застосовуємо зменшення кількості точок за допомогою воксельної сітки
downsampled_cloud = o3d_cloud.voxel_down_sample(voxel_size=voxel_size)
# Перетворюємо назад у BasicPointCloud
return BasicPointCloud(points=np.asarray(downsampled_cloud.points),
colors=np.asarray(downsampled_cloud.colors),
normals=np.asarray(downsampled_cloud.normals))
“Voxelsize” — це розмір вокселя, який використовується для зменшення кількості точок. Для більш високих роздільних здатностей можна вибирати менші розміри вокселів. Однак є кілька моментів, на які потрібно звернути увагу перед вибором “voxelsize”.
- Якщо хмара точок представляє великий об'єкт або середовище (кімната чи ландшафт), використовуйте більший розмір вокселя.
- Якщо хмара точок представляє маленький об'єкт з дрібними деталями, використовуйте менший розмір вокселя.
Типові значення
- Малий, детализований об'єкт: використовуйте розмір вокселя 0.001 до 0.01 одиниць.
- Об'єкти середнього розміру (меблі або транспортні засоби) : використовуйте розмір вокселя 0.01 до 0.05 одиниць.
- Великомасштабні середовища (будівлі або відкриті сцени) : використовуйте розмір вокселя 0.1 до 0.5 одиниць.
Як приклад,
0.005 до 0.01: зберігає дрібні деталі для малих об'єктів або локалізованих структур.
0.02 до 0.05: корисно для загального зменшення кількості точок для середніх сцен.
0.1 або більше: значно зменшує кількість точок для великомасштабних сцен, зберігаючи загальну структуру.
3. Однорідне підвибірку (Uniform Grid Subsampling)
Простір ділиться на 3D сітку з фіксованими розмірами клітин, і для кожної клітини вибирається одна точка, що обчислюється як середнє значення. Однак цей підхід призводить до більш рівномірного просторового розподілу по всій хмарі точок. Пулінг на основі сітки часто спеціально розроблений для просторової регулярності і надає пріоритет рівномірності, що може призвести до втрати деяких дрібних структурних деталей у порівнянні з методом воксельної сітки.
import numpy as np
def uniform_grid_subsample(point_cloud: BasicPointCloud, grid_size: float) -> BasicPointCloud:
"""Однорідне підвибірку хмари точок."""
points = point_cloud.points
colors = point_cloud.colors
normals = point_cloud.normals
# Обчислюємо індекси сітки для кожної точки
grid_indices = np.floor(points / grid_size).astype(np.int32)
# Створюємо словник для зберігання точок за клітинками сітки
grid_dict = {}
for i, idx in enumerate(grid_indices):
key = tuple(idx)
if key not in grid_dict:
grid_dict[key] = (points[i], colors[i], normals[i], 1)
else:
pos, col, norm, count = grid_dict[key]
# Накопичуємо значення для обчислення середнього
grid_dict[key] = (pos + points[i], col + colors[i], norm + normals[i], count + 1)
# Обчислюємо середні значення для кожної клітинки сітки
downsampled_points = []
downsampled_colors = []
downsampled_normals = []
for pos, col, norm, count in grid_dict.values():
downsampled_points.append(pos / count)
downsampled_colors.append(col / count)
downsampled_normals.append(norm / count)
return BasicPointCloud(points=np.array(downsampled_points),
colors=np.array(downsampled_colors),
normals=np.array(downsampled_normals))
Тут “grid_size” визначає розмір кожної клітинки сітки. Більші значення призводять до більшого зменшення кількості точок.
4. Збереження кривизни при вибірці (Curvature-Preserving Sampling)
Цей метод зосереджений на збереженні точок з високою кривизною, таких як краї та кути, які головним чином сприяють загальній формі об'єкта. Кривизну можна оцінити, аналізуючи власні значення матриці ковариації в сусідстві точки.
Отже, порівняно з попередніми методами, цей підхід трохи інший.
Як це працює?
- Спочатку вибираються найближчі сусіди для точки (наприклад, 5).
- Потім обчислюється середнє значення для сусідів (середня точка для 5 сусідів).
- Далі обчислюється матриця ковариації за допомогою нормованих позицій сусідів. (Тут ми очікуємо матрицю ковариації розміром 5 на 5, обчислену за допомогою нормованих позицій (точка — середня_точка))
Рівняння ковариації
- Потім обчислюються власні значення матриці ковариації. Співвідношення мінімального власного значення до суми всіх власних значень визначається як кривизна.
Кривизна
- Після сортування точок за їхніми значеннями кривизни вибирається набір точок з найвищою кривизною для зменшеної хмари точок. Це дозволяє зберегти ключові структурні елементи.
import open3d as o3d
import numpy as np
def curvature_preserving_sampling(point_cloud: BasicPointCloud, k_neighbors=20, fraction=0.2) -> BasicPointCloud:
"""Зменшення кількості точок з збереженням кривизни за допомогою оцінки кривизни на основі власних значень."""
o3d_cloud = o3d.geometry.PointCloud()
o3d_cloud.points = o3d.utility.Vector3dVector(point_cloud.points)
# Обчислюємо кривизну за допомогою пошуку найближчих сусідів у Open3D
o3d_cloud.estimate_normals(search_param=o3d.geometry.KDTreeSearchParamKNN(knn=k_neighbors))
# Обчислюємо кривизну як функцію власних значень
curvatures = []
kdtree = o3d.geometry.KDTreeFlann(o3d_cloud)
for i in range(len(point_cloud.points)):
_, idx, _ = kdtree.search_knn_vector_3d(o3d_cloud.points[i], k_neighbors)
neighbors = np.asarray(o3d_cloud.points)[idx]
cov = np.cov(neighbors, rowvar=False)
eigenvalues, _ = np.linalg.eigh(cov)
curvature = eigenvalues[0] / sum(eigenvalues)
curvatures.append(curvature)
# Сортуємо точки за кривизною та вибираємо верхню частину
sorted_indices = np.argsort(curvatures)[::-1]
num_samples = int(len(point_cloud.points) * fraction)
selected_indices = sorted_indices[:num_samples]
return BasicPointCloud(points=point_cloud.points[selected_indices],
colors=point_cloud.colors[selected_indices],
normals=point_cloud.normals[selected_indices])
“k_neighbors”: кількість сусідів, які використовуються для оцінки кривизни.
“Fraction”: частка точок, які слід зберегти.
Порівняння
Рисунок 3: Порівняння
Перекладено з: Point Cloud Downsampling Methods and Python Implementations