点云生成是 3D 视觉和图形学里的基础任务但真正要把点云生成做到结构可控、层次清晰并不是简单训练一个回归网络就能解决的。最近读到一篇以 Tessellate 为核心思想的点云生成论文整体思路很有启发与其让模型直接预测每个点的坐标不如让模型学会把空间递归地切分成更小的子区域再在子区域内生成点。这种思路本质上把“生成点云”转换成了“学习空间划分策略”。本文会从点云生成的基本问题出发拆解递归谱分割Recursive Spectral Partitioning的核心原理并给出可运行的 Python 示例。即使你不打算复现原论文这套层次化划分思路也能用到点云采样、数据增强和三维形状分析中。1. 背景为什么点云生成需要“细分”这个动作1.1 点云生成是什么点云是一组在三维空间中无序排列的坐标点集用来表示物体表面或场景几何。点云生成的目标是让模型根据某种条件类别、图像、文本或仅仅是一个随机噪声向量输出一组能代表目标形状的三维点。听起来像是“从噪声生成坐标”的问题但实际落地时会遇到两个明显困难点云没有固定顺序。同一个形状改变点的排列顺序后仍是同一个点云这导致传统序列生成模型很难直接处理。点云不同区域的密度不是均匀的。在平面区域少量点就能表达在棱角、边缘、细节区域则需要更多点来保持锐利。因此点云生成模型不仅要学会输出正确的坐标范围还要学会在哪些地方投入更多点。1.2 Tessellate 在三维生成中的含义Tessellate 是计算机图形学中的常用词中文通常翻译为“细分”或“镶嵌”。它指把一个多边形、曲面或空间区域分割成更小的单元这些单元拼接起来后仍然覆盖原来的整体。在三维重建里最典型的细分是三角网格剖分把复杂表面拆成许多小三角形用足够多的小三角片逼近真实曲面。把这种思想移植到点云生成中可以理解为先确定一个大的空间范围递归地把空间划分成多个子区域根据每个子区域的形状复杂度放置数量不等的点最终所有子区域的点合并起来形成完整的点云。这样做的好处是生成过程从“直接找点”变成“先划分再在每个局部区域找点”。划分本身是一种强结构约束可以让生成结果在空间分布上更均匀、更符合形状拓扑。1.3 直接回归坐标的瓶颈很多早期的点云生成方法特别是基于 Autoencoder 或 GAN 的模型倾向于让网络直接输出 N 个点的 xyz 坐标。这种方案虽然简单但存在几个瓶颈点与点之间缺少显式的空间关系。网络虽然能输出符合坐标范围的点但点之间的相对位置和密度关系很难控制。容易产生“点聚堆”现象。当损失函数只是 Chamfer Distance 或 EMD 时模型倾向于把点放在容易降低距离误差的位置导致某些区域点非常密集某些区域几乎为空。难以表达多尺度结构。一把椅子有椅背、椅座、椅腿每条椅腿又是一个细长结构。如果所有点都从同一个全局特征生成局部几何细节很容易被平均掉。递归谱分割的出发点就是想把这种“先整体后局部、逐层细化”的建模方式显式地引入到生成流程中。2. 递归谱分割核心原理2.1 图拉普拉斯与谱分割谱分割是谱聚类的基础操作。假设我们有一组点要把它分成两个子集并且希望两个子集内部的点尽量接近、两个子集之间的距离尽量远。一种经典做法是把点看作图的顶点根据点与点之间的距离构建带权邻接矩阵 W计算度矩阵 D 和图拉普拉斯矩阵 L D - W对 L 做特征分解取第二小特征值对应的特征向量即 Fiedler 向量根据 Fiedler 向量的符号或中位数将点分成两组。Fiedler 向量是谱分割里非常关键的概念。图拉普拉斯矩阵的第二小特征值也叫代数连通度它刻画了图被切成两部分时所需的最小割代价。对应的特征向量能反映每个顶点在“最优二分”中更偏向哪一侧。2.2 递归二分的思路递归谱分割的思想很直接对当前点集执行一次谱二分得到左右两个子集然后对每个子集继续执行同样的二分操作直到子集规模满足停止条件。这个过程等价于构造一棵二叉划分树根节点是完整点集每次向下分裂时用谱分割把父节点分成两个孩子树的叶子节点就是最终保留的小规模点簇。对于点云生成来说递归谱分割不是最终目的而是作为空间划分工具。模型可以在每一步学习如何选择相似度度量、划分边界和停止条件。叶子节点对应的是“该放点的小区域”整个点云则通过这些区域内采样的点拼接而成。2.3 为什么谱分割适合点云生成相比均匀网格划分或者随机空间切分谱分割有几点非常适合点云场景能感知密度。谱分割基于点与点之间的相似度点密集的区域在图结构上连接更紧密更容易被划分到同一侧。能保持局部连通性。划分结果通常不会在几何上过于破碎因为拉普拉斯约束会让分割边界尽量走在“低相似度”的位置也就是形状的凹槽或弱连接处。具备层次性。每次划分只负责局部区域天然适合多尺度建模。与图结构兼容。点云本身就可以表示成图谱分割可以直接在点云的近邻图上运行。因此在“先划分再生成”的框架里递归谱分割是一种比较合理的空间结构化工具。3. 环境准备与版本说明在实际编写代码之前先把环境准备好。本文的示例以 Python 为主核心库是 NumPy 和 SciPy。后续如果要用深度学习方式复现论文还会用到 PyTorch。3.1 环境依赖建议使用 Python 3.8 及以上版本安装以下依赖numpy1.21.0 scipy1.7.0 matplotlib3.4.0如果准备做深度学习实验可以追加torch1.10.0版本需要根据你的项目实际情况调整。本文示例以常见环境为例重点演示算法思路而不是绑定某个特定版本。3.2 建议的项目结构为了后续扩展方便建议按下面的文件结构组织代码recursive_tessellation/ ├── main.py ├── spectral_utils.py ├── partition_tree.py └── visualization.pyspectral_utils.py负责构建邻接矩阵、计算图拉普拉斯、执行谱二分。partition_tree.py实现递归划分与点云采样。visualization.py负责可视化。main.py入口脚本。4. 实战用递归谱分割生成结构化的二维点云为了把原理讲清楚我们先不直接跳到三维而是实现一个二维示例。二维点云更容易可视化算法逻辑也可以直接复用到三维。4.1 生成输入点集谱分割本身是针对已有集合进行划分。为了演示点云生成我们先用一个形状比如两个重叠的圆环生成密集候选点然后通过递归谱分割把候选点分成若干结构块再从每个结构块中采样最终的点云。打开spectral_utils.py先实现相似度矩阵和图拉普拉斯# 文件路径recursive_tessellation/spectral_utils.py import numpy as np from scipy.spatial.distance import pdist, squareform def build_knn_similarity(points, k8, sigma1.0): 基于 KNN 构建相似度矩阵 W并做对称化。 参数 points: 形状为 [N, D] 的点集 k: 每个点的邻居数量 sigma: 高斯核带宽 dists squareform(pdist(points, metriceuclidean)) # 高斯核相似度 W np.exp(-(dists ** 2) / (2 * sigma ** 2)) # 只保留每个点最近的 k 个邻居其他置 0 for i in range(points.shape[0]): row W[i].copy() nbr_indices np.argsort(row)[::-1][:k] mask np.zeros_like(row, dtypebool) mask[nbr_indices] True row[~mask] 0.0 W[i] row # 对称化保证 W[i, j] W[j, i] W (W W.T) / 2.0 return W def spectral_bisection(points, k8, sigma1.0): 对点集执行一次谱二分。 返回 labels: 0/1 数组表示每个点属于左子集还是右子集 fiedler: Fiedler 向量 W build_knn_similarity(points, kk, sigmasigma) D np.diag(W.sum(axis1)) L D - W # 计算最大特征值用于后续归一化这里直接做完整特征分解 eigvals, eigvecs np.linalg.eigh(L) fiedler eigvecs[:, 1] # 第二小特征值对应的特征向量 # 用中位数作为划分阈值避免偏向某一侧 threshold np.median(fiedler) labels (fiedler threshold).astype(int) return labels, fiedler这里要重点解释两个地方为什么不直接用距离矩阵而要转成相似度矩阵因为谱分割是在图结构上切分图边的权重需要表达“点与点之间的接近程度”高斯核是比较常用的选择。为什么对称化因为无向图的邻接矩阵必须是对称的否则拉普拉斯矩阵的性质不成立特征分解结果会失真。4.2 递归细分与点云采样接着在partition_tree.py中定义递归划分树。我们用递归深度和叶子节点最小点数作为停止条件# 文件路径recursive_tessellation/partition_tree.py import numpy as np from spectral_utils import spectral_bisection class RecursiveSpectralPartition: 递归谱分割器。 输入一个点集输出多个子区域对应的点簇。 def __init__(self, min_leaf_size32, max_depth5, k8, sigma1.0): self.min_leaf_size min_leaf_size self.max_depth max_depth self.k k self.sigma sigma def partition(self, points, depth0): # 如果点数过少或深度达到上限停止划分 if len(points) self.min_leaf_size or depth self.max_depth: return [points] labels, _ spectral_bisection(points, kself.k, sigmaself.sigma) group_a points[labels 0] group_b points[labels 1] # 防御如果划分退化强制停止 if len(group_a) 0 or len(group_b) 0: return [points] result [] result.extend(self.partition(group_a, depth 1)) result.extend(self.partition(group_b, depth 1)) return result def sample_from_candidates(candidates, num_points1024, min_leaf_size32, max_depth5, k8, sigma1.0): 先用递归谱分割把候选点分成多个子区域 再从每个子区域中采样点生成最终点云。 partitioner RecursiveSpectralPartition( min_leaf_sizemin_leaf_size, max_depthmax_depth, kk, sigmasigma ) leaf_clusters partitioner.partition(candidates) # 从每个叶子节点中均匀采样 sampled_parts [] quota_per_cluster max(1, num_points // len(leaf_clusters)) for cluster in leaf_clusters: count min(quota_per_cluster, len(cluster)) indices np.random.choice(len(cluster), sizecount, replaceFalse) sampled_parts.append(cluster[indices]) # 如果因为取整导致数量不够则从剩余点中补足 result np.concatenate(sampled_parts, axis0) if len(result) num_points: extra candidates[np.random.choice(len(candidates), sizenum_points - len(result), replaceFalse)] result np.concatenate([result, extra], axis0) return result这里有一个容易踩坑的点如果叶子节点特别多num_points // len(leaf_clusters)可能小于 1导致某些叶子不采样。所以代码里用max(1, ...)保证每个叶子至少取 1 个点最后再补足总数。4.3 生成测试数据并可视化下面是main.py的完整示例。我们生成一个“两个圆环”形状的候选点集然后调用递归谱分割生成点云并用 Matplotlib 可视化。# 文件路径recursive_tessellation/main.py import numpy as np import matplotlib.pyplot as plt from partition_tree import sample_from_candidates def make_ring_candidates(n4000, seed42): 生成两个圆环形状的候选点集。 rng np.random.default_rng(seed) theta rng.uniform(0, 2 * np.pi, sizen) radius rng.uniform(0.8, 1.2, sizen) x radius * np.cos(theta) y radius * np.sin(theta) theta2 rng.uniform(0, 2 * np.pi, sizen) radius2 rng.uniform(0.8, 1.2, sizen) x2 radius2 * np.cos(theta2) 3.0 y2 radius2 * np.sin(theta2) points np.stack([np.concatenate([x, x2]), np.concatenate([y, y2])], axis1) return points def visualize_generated(points, leavesNone): plt.figure(figsize(6, 6)) plt.scatter(points[:, 0], points[:, 1], s2, csteelblue) plt.axis(equal) plt.title(Generated Point Cloud by Recursive Spectral Partitioning) plt.show() if __name__ __main__: candidates make_ring_candidates(n4000, seed42) result sample_from_candidates( candidates, num_points1024, min_leaf_size32, max_depth5, k8, sigma1.0 ) print(生成点云数量:, len(result)) visualize_generated(result)运行脚本cd recursive_tessellation python main.py预期结果生成 1024 个点整体保持两个圆环的形状但点的分布会呈现出块状结构不同区域之间的边界相对清晰。4.4 结果说明从生成效果上看递归谱分割输出的点云不是完全均匀的。它会把候选点集合按图的连通性切成若干子簇每个子簇内的点来自形状的某一个局部区域。这样做的好处是如果你用生成结果去做分类、分割或重建模型能更明显地感知到局部几何结构。当然二维示例只是验证算法流程。实际点云生成任务要处理三维点但核心逻辑完全一致只是相似度矩阵改用三维欧氏距离可视化时需要投影或使用三维绘图工具候选点集需要来自目标三维形状表面。5. 从谱分割到“Learning to Tessellate”的研究思路5.1 让网络学习划分策略传统的递归谱分割是确定性的给定点集特征分解结果就决定了怎么切。但论文标题中的 “Learning to Tessellate” 强调了“学习”二字。换句话说我们希望网络不只是执行固定的谱分割而是能够学习如何为不同形状选择更好的划分方式。这里可以理解为两个层面底层划分仍然保留谱分割的层次结构上层的划分策略、相似度度量、阈值或停止条件都是由网络预测出来的。例如网络可以学习构造一个更适合当前形状的邻接矩阵而不是固定使用欧氏距离加高斯核。这样在分割细节区域时网络可以选择更小的带宽在平坦区域时可以选择更大的带宽。5.2 与主流点云生成方法的对照目前点云生成的研究主流大致有几条路线基于 GAN 的方法生成器输出点集判别器判断真假。优点是生成速度快缺点是不稳定。基于 CVAE 或扩散模型的方法从隐变量逐步恢复点云。优点是质量高缺点是采样速度慢。基于 Transformer 的方法把点云看作序列用自回归方式逐个生成点。优点是可以建模全局依赖缺点是训练开销大。基于空间递归划分的方法像本文讨论的思路一样把点云生成分层化每次生成一个子区域内的点。优点是可解释性强、结构可控缺点是复杂度更高。“Learning to Tessellate” 更接近最后一种路线。它的价值在于给点云生成增加了一层显式的空间结构先验。在点云比较稀疏或者存在明显拓扑边界时这种先验能明显改善生成形状的完整性。5.3 训练稳定性和损失设计如果想把这个思路落地成可训练的模型需要处理几个关键问题划分操作要可微。谱分解本身是不可导的用于训练时通常需要近似。一种办法是用 Gumbel-Softmax 得到软划分结果另一种办法是让网络直接预测每个点的归属概率再通过可微聚类近似谱分割。损失函数需要同时权衡划分质量和重建质量。可以设计一个组合损失重建损失最终点云与真实点云的 Chamfer Distance划分一致性损失同一子区域内的点特征尽量接近平衡损失避免某个子区域占用过多点。下面给出一个最小的 PyTorch 伪代码展示可微二分类划分离子import torch import torch.nn as nn class LearnablePartitionLayer(nn.Module): 可微划分层 输入每个点的特征输出该点属于左右子区域的概率。 这里只是演示思路并非论文原始结构。 def __init__(self, in_channels3, hidden_channels64): super().__init__() self.mlp nn.Sequential( nn.Linear(in_channels, hidden_channels), nn.ReLU(), nn.Linear(hidden_channels, 2) ) def forward(self, point_features): # point_features: [N, C] logits self.mlp(point_features) # [N, 2] probs torch.softmax(logits, dim-1) # [N, 2] return probs if __name__ __main__: # 随机生成 128 个点的特征每个点 3 维坐标 points torch.randn(128, 3) layer LearnablePartitionLayer(in_channels3) assignment layer(points) # [128, 2] # 通过概率权重聚合左右子区域的点 left_points assignment[:, 0].unsqueeze(-1) * points right_points assignment[:, 1].unsqueeze(-1) * points print(左子区域聚合点形状:, left_points.shape) print(右子区域聚合点形状:, right_points.shape)在这个示例里每个点都被赋予了左右两个子区域的软归属权重。虽然这不是严格的谱分割但它给模型提供了一种可微的分割决策方式。真正复现论文时需要把这种软划分与谱分割的强结构约束结合起来。6. 常见问题与排查思路6.1 特征向量符号不稳定谱分解得到的特征向量方向不唯一可能出现两次运行同一算法但 Fiedler 向量符号完全相反的情况。比如第一次运行第 i 个点被分到左侧第二次却被分到右侧。问题现象常见原因解决思路分割结果左右交换特征向量符号不确定统一约定符号比如让最大绝对值的分量恒为正划分结果震荡邻居数 k 过小或 sigma 不合适增大 k或用自适应距离阈值调整相似度建议在实现里增加一个符号归一化步骤# 统一 Fiedler 向量符号 if np.abs(np.min(fiedler)) np.abs(np.max(fiedler)): fiedler -fiedler6.2 分割结果不均衡递归谱分割可能把大部分点分到一侧另一侧只有很少的点。这样会破坏生成点云的均衡性。常见原因有两个相似度矩阵中的 sigma 设置不当导致点的连接关系过于密集或过于稀疏点云本身存在不均匀分布谱分割如实反映了几何密度差异。解决方法动态调整 sigma例如按照 k 近邻距离的中位数设置在递归划分后增加“最小子集规模”约束如果某个子集过小则停止继续划分。6.3 递归过深导致子区域为空递归划分时如果 k 太大、sigma 太大点之间的连接会非常密集容易出现退化划分大部分点连接到一起Fiedler 向量噪声很大划分结果可能把某一侧分成空集。问题现象常见原因解决思路group_a 或 group_b 为空相似度矩阵过于稠密降低 k减小 sigma或增加阈值判断递归无法终止没有设置深度或最小点数限制同时使用 max_depth 和 min_leaf_size 两个停止条件代码里一定要加上防御逻辑也就是上一节中的if len(group_a) 0 or len(group_b) 0: return [points]。6.4 高维点云计算开销大谱分割需要对 N x N 的拉普拉斯矩阵做特征分解当候选点数量达到数万甚至数十万时完整分解会非常慢甚至内存溢出。场景数据规模推荐方案小型点云N 5000直接使用 numpy.linalg.eigh中大型点云N 10000使用 scipy.sparse.linalg.eigsh 只计算少量特征向量超大点云点云生成训练集先用 FPS 或体素降采样再递归划分在工程实现中应优先使用稀疏矩阵。把build_knn_similarity返回的 W 转换为稀疏矩阵后可以用eigsh只计算前几个特征值大幅降低开销。7. 最佳实践与工程建议7.1 数据预处理与归一化谱分割对距离尺度非常敏感。如果点云坐标范围太大高斯核的 sigma 就很难选。建议在输入之前先做归一化def normalize_point_cloud(points): center points.mean(axis0) points points - center scale np.max(np.linalg.norm(points, axis1)) points points / scale return points这样做有两个好处不同形状的取值范围统一便于设置固定 sigma训练深度学习模型时数值更稳定。7.2 邻接矩阵与相似度度量选择实际工程中不要盲目使用“完整高斯核矩阵”。随着点数量增加稠密矩阵会快速耗尽内存。通常建议使用 KNN 图k 取 6 到 16 之间比较常见对于三维点云还可以使用半径搜索代替 KNNsigma 建议根据每个点的 k 近邻距离来估计而不是手工指定。一个比较稳的 sigma 估计方法def estimate_sigma(points, k8): dists squareform(pdist(points, metriceuclidean)) knn_dists np.sort(dists, axis1)[:, 1:k1] median_dist np.median(knn_dists) return median_dist7.3 递归深度与停止条件递归深度要结合点云复杂度设置简单形状球体、圆柱深度 3 到 4 足够复杂形状人体、家具、车辆深度 5 到 7 才能保留局部细节每个叶子节点的点数建议在 16 到 64 之间。太深的递归会带来两个问题计算量指数增长以及点云被切得过于碎片化反而破坏整体结构。7.4 与深度生成模型结合时的建议如果要把递归谱分割嵌入生成模型有几点工程建议使用软划分替代硬划分。硬划分不可微软划分可以避免训练时梯度断裂。保留层次中间结果。不要把每个叶子独立看待父节点的特征可以注入到子区域帮助子区域理解全局上下文。加入平衡正则化。避免网络把所有点都划分到同一个子区域。尽量固定候选点数量。递归划分后每个子区域点数量不同训练时需要使用 FPS 或随机采样统一每个 batch 的点数。8. 总结与学习路线8.1 本文核心收获通过这篇文章你至少应该掌握以下几点点云生成不仅是坐标回归问题也是空间划分问题Tessellate 的核心思想是把完整空间逐层剖分成子区域再生成点递归谱分割利用图拉普拉斯矩阵的特征向量对点集进行层次化二分在代码层面我给出了从相似度矩阵、谱二分到递归生成点云的完整 Python 示例在深度学习方向可微划分是让模型“学会细分”的关键一步。8.2 下一步深入研究方向如果你对这个方向感兴趣可以沿着以下路线继续深入先复习谱聚类和谱图理论弄清楚 Fiedler 向量为什么能切出低割边然后尝试把二维示例改成三维点云加入 FPS 降采样和距离归一化再尝试用一个简单的 PointNet 特征提取器替代固定的相似度矩阵让网络预测划分概率最后对比 Chamfer Distance、EMD 等损失函数在不同递归深度下的表现。建议你从二维示例开始跑通再逐步替换成三维数据。动手实践时可以重点观察递归深度、k 近邻数和 sigma 对生成结果的影响。把这些参数调明白你对谱划分和点云结构的理解会扎实很多。如果本文对你有帮助可以收藏备用后续遇到点云生成相关问题也方便查阅。这篇文章就写到这里希望它能帮你把“递归谱分割”这条思路真正变成可上手、可实验的方法。