基于特征聚合的深度霍夫变换法向估计算法-凯发娱乐官网

1. 引言

点云是经由扫描仪器对目标物体进行不规则采样得到的离散三维点集合，其运用领域非常广泛。目前已经开发了许多算法处理点云，如点云形状检测[1]、三维重建[2]、自动驾驶[3]及基于点的渲染[4]等。在上述点云处理过程中，算法性能在很大程度上依赖于点云法向估计的质量，因此法向估计是点云数据分析处理等后续工作的基础。而在点云数据的采集过程中，由于扫描物体本身存在尖锐特征，以及受震动、光线、扫描仪器自身误差等因素干扰，所得数据存在不均匀采样、各向异性偏差等问题，加大了法向估计的难度。

近年来，许多学者对点云法向估计展开了广泛研究并提出了许多不同的方法，大致可将这些方法分为4类：基于voronoi/delauney的方法[5] [6]、基于法向修正的方法[7]-[10]、基于局部拟合的方法[11]-[15]、以及基于深度网络的方法[16] [17]。

基于voronoi/delauney的方法是一类比较早期的用于点云法向估计的算法，由amenta等人[5]提出，该方法主要思想为：对输入点云中的每个点，先通过对其邻域点构建voronoi图，然后对其进行delauney三角剖分，再对每个点通过其所属三角面片来计算法向。在此基础之上，alliez等人[6]将其与pca算法融合，通过拟合每点所在的voronoi格或voronoi格组合内所有点构成的平面从而计算法向。以上基于voronoi/delauney的方法虽可以较好地处理小噪声点云，但对于大噪声以及分布不均匀的点云数据仍存在法向估计不准确等问题。

在基于法向修正的方法中，移动最小二乘法(moving least squares, mls) [7]、局部邻域重组算法(normal estimation with neighborhood reorganization, nenr) [8]以及鲁棒局部核回归(local kernel regression, lkr) [9]等算法先输入点云位置及初始法向信息，再通过拟合曲面的梯度对点云法向进行修正。jones等人[10]提出三维双边滤波器对点云位置及初始法向做加权结合来修正法向和去除噪声。上述基于法向修正的方法虽在点云尖锐特征处表现良好，但其法向估计的精度依赖于初始法向的可靠性，且需要人工调节参数耗费时间。

基于局部拟合的方法由hoppe等人[11]最早提出(principal component analysis, pca)，该算法通过对邻域内的所有点拟合切平面从而计算得到当前点的法向。mitra等人[12]则通过计算曲率、采样密度以及噪声大小来得到最优邻域尺度从而提升法向质量。huang等人[13]提出通过自适应权重来提升对具有非均匀采样及异常值的点云的法向估计的鲁棒性。然而，位于不同曲面上点对拟合结果仍有影响。为了克服该问题，zhang等人[13]提出了通过点之间法向差异对低秩子空间聚类(low rank representation, lrr)算法进行引导，选择最优子邻域拟合局部切平面。liu等人[15]在该算法基础之上，提出了lrr的加速版本(fast low rank representation, lrrfast)，该方法虽可以很好处理点云中的离群点，但在高曲率部分法向估计不理想。

基于深度网络的方法主要是将卷积神经网络结合到点云模型中对其进行法向估计。在基于深度网络的方法中，利用霍夫变换进行法向估计是此类方法中最早的方法。boulch等人[16]利用霍夫变换将切平面与单位球相对应；然后将单位球面划分成面积相近的网格作为球形累加器，再通过对当前邻域随机选取三个邻域点计算候选平面，由候选平面向球形累加器中投票，最后对累加器中投票最多的格子进行平均以此获得预估法向。然而，由于该方法需要对单位球进行离散化，因此估计法向不连续，为了解决该问题，[16]一文采用了多次随机旋转累加器的方法，而此操作显著增加了算法的计算成本并且引入了额外的参数。因此boulch等人[17]在此基础之上，利用卷积神经网络技术(convolutional neural network, cnn)将霍夫变换与卷积神经网络结合(hough transform based convolutional neural network, houghcnn)，通过cnn对法向进行学习，从而克服估计法向不连续的问题。该文将球形累加器替换为与图像更为接近的方形累加器，将候选平面投至方形累加器中，然后将投票结果转化为二维灰度图像直接输入cnn中学习最终法向。虽然该算法可以得到较为准确的法向结果，但在点云尖锐特征处所估计的法向仍有平滑。同时，该算法通过累加器获得的图像作为cnn输入存在一定的特征损失，影响网络的整体性能。

因此，为了进一步提升cnn的特征输入，优化现有的法向估计效果，本文在论文[17]的基础之上，受到论文[18]的启发，提出了基于特征聚合的深度霍夫变换法向估计算法。该算法与文献[17]类似，在切平面经过当前点的假设下，利用霍夫变换将所有切平面与单位正方形对应。然后对单位正方形进行均匀划分得到方形累加器进而得到潜在切平面集，将点特征转化为潜在切平面特征来填充方形累加器作为cnn输入，从而减少霍夫变换过程中的特征损失，提升整体网络学习法向估计的能力。实验结果表明，特征聚合的加入提升了整体网络学习的性能，可以获得更高质量的法向，在不同尺度的噪声下也更具鲁棒性。

2. 算法流程

本文设计了基于特征聚合的深度霍夫变换法向估计算法，该算法的输入为带有噪声的点云p及其对应的初始法向n (初始法向由pca估计所得)。对于给定的当前点p i 及邻域p i ={ p i j | p i j 属于 p i 的k近邻 } ，其对应法向集合记为n i ={ n i j | n i j 为 p i j 对应的法向, p i j ∈ p i } ，在本文实现中，邻域尺度k=256 。首先在2.1节中介绍了如何使用深度霍夫变换进行法向估计，并分析了该方法的问题所在。然后，在2.2节中介绍了文本设计的特征聚合，并在2.3节中详细阐述了本文的网络流程，最后在2.4节中描述了本文的损失函数。

2.1. 基于深度霍夫变换的法向估计

cnn在物体存在遮挡时对于物体分类和检测等任务[19]都非常有效。因此，文献[17]将霍夫变换与cnn相结合得到了深度霍夫变换网络进而学习法向估计。

利用霍夫变换可将切平面与点作对应。假设切平面经过当前点p i ，先将单位球划分为面积相近的网格可得到文献[16]中使用的球形累加器，如图1(a)所示。为了易于转化为cnn的输入形式，文献[17]提出方形累加器将球形累加器与二维平面作对应，如图1(b)所示。对于给定法向n=( n x , n y , n z ) ，将该法向经由ϕ 映射至霍夫空间中得到投票法向n ˙ =( n ˙ x , n ˙ y ) 。假设方形累加器的大小为m=m×m ，方形累加器定义形式为：

ϕ( n )= n ˙ ,(1)

( n ˙ x , n ˙ y )=( n x 1 2 *m, n y 1 2 *m ) ,(2)

其中∗ 为乘法。在本实验中，m设置为33。

由此，通过霍夫变换可以将切平面与方形累加器中的二维网格内的点对应。再通过在p i 内随机选取三个点计算随机切平面来对方形累加器进行投票，从而得到一个灰度图，三点组数的上界[16]为

t= 1 2 δ 2 ln( 2m 1−α ) ，其中α∈[ 0,1 ] 为置信阈值，δ∈[ 0,1 ] 。再将该灰度图输入至cnn中学习法向估计，最终直接得到估计法向。

但该算法是通过人为提取的二维灰度图作为cnn输入，在其过程中存在一定的特征损失，影响了网络整体学习估计法向的性能。对此本文提出特征聚合，直接将点特征转化为潜在切平面特征与二维网格对应从而填充方形累加器，再将其输入至cnn中学习法向。该方法可以通过降低霍夫变换过程中的特征损失来提升cnn的输入进而提升整体网络性能。

figure 1. diagram of the accumulators of different shapes

图1. 不同形状累加器示意图

2.2. 特征聚合

方形累加器中每个格子都对应一个潜在切平面。在此以方形图像累加器中的格子a为例，使用格子a所对应的法向n a =( x a , y a , z a ) 及当前点p i 可以计算出潜在切平面s a ，如图2示意图中所示，其表达式为：

x a x y a y z a z− x i ∗ x a − y i ∗ y a − z i ∗ z a =0 .(3)

假设邻域中每个点p i j 都有一个点特征f i j ，利用点特征加权组合得到切平面特征：

f a = ∑ w i j ⋅ f i j ,(4)

其中⋅ 为内积，w i j 为距离权重，由邻域点p i j 向切平面s a 中投影得到：

w i j =exp( − ( p i j ⋅ n a ) 2 ( 0.01 ) 2 ) .(5)

权重的大小在一定程度上反映了邻域点与当前点结构关系的相似性，距离越近的点与当前点相似度越高，权重就越大，反之相似度越小，权重也就越小。

特征聚合通过邻域点与切平面的距离来刻画邻域点的重要性，从而聚合邻域点特征得到切平面特征，与文献[17]中随机选点计算切平面来填充累加器相比，该过程不仅使用网络来提取点特征，还考虑到了邻域点特征及其所处结构，减少了霍夫变换以及人为提取特征过程中的损失。

figure 2. diagram of the distance between the neighborhood points and the tangent plane

图2. 邻域点与切平面距离示意图

figure 3. algorithm flowchart

图3. 算法流程图

2.3. 网络流程

本文算法流程如图3所示。首先，对于3d点云及其法向，为了减少模式变化并促进网络学习，将其进行旋转，如图1中的3d空间所示：将三维坐标系中的z轴旋转与由pca求得p i 的最小特征向量对齐。

接下来，将初始法向进行霍夫变换使法向与平面对应，通过均匀划分平面得到方形累加器，使得每个格子中均对应一个法向。然后将点云输入至pointnet [20]中提取每点特征f i j ，再通过特征聚合将点特征转化为潜在切平面特征：假设切平面均经过当前点，故可通过每个格子的对应法向与当前点计算每个格子的潜在切平面从而得到潜在切平面集，并利用邻域点与切平面距离作为权重，再将点特征与权重做加权组合得到每一潜在切平面特征。

然后，经过上述操作，我们得到的网格中的每一个格子都对应一个潜在切平面特征，再将填充后的网格输入到cnn中。本文的cnn由两个卷积层组成：先经过卷积核为5×5 的图像卷积层1，并由relu函数激活，再经过卷积核为1×1 的图像卷积层2，最终得到一个灰度图像。对灰度图像缩放像素值，使得最高强度像素为白色，其对应坐标为( x,y ) ，对其进行反向映射ϕ −1 所得法向n ^ i =( n ^ i x , n ^ i y , n ^ i z ) ，即为当前点p i 的预测法向：

( n ^ i x , n ^ i y )= ϕ −1 ( x,y ) ,(6)

n ^ i z = 1−( ( n ^ i x ) 2 ( n ^ i y y ) 2 ) ,(7)

其中，ϕ −1 为ϕ 的逆映射。

2.4. 损失函数

本文损失函数由预测法向n ^ i 与真实法向n ¯ i 组成，用于测定预测法向与真实法向之间的差异，并反馈和训练网络。由于法向并非定向，故将损失函数设计为：

los s n = ∑ p i ∈p min( ‖ n ^ i − n ¯ i ‖ 2 , ‖ n ^ i n ¯ i ‖ 2 ) | p | ,(8)

其中，| | 表示集合p中元素个数，‖ ‖ 表示向量的二范数。

3. 实验

首先，在3.1节中描述了用于实验训练以及测试的数据库；在3.2节中给出了评价指标；基于此，在3.3节中详细描述了本文法向估计的性能，通过与现有的几种法向估计算法相比较，给出了定量结果，并在3.4节中给出了定性分析。本文算法在pytorch上实现，使用cuda编程实现深度霍夫变换，并在单个nvidia gtx 1080ti上进行训练和测试。

3.1. 数据库

对于训练和测试，本文使用了pcpnet形状数据集[21]。训练数据集由4个cad模型和4个高质量扫描小雕像组成，每个模型的采样点数均为100 k。在给定干净模型的情况下，通过添加中心高斯噪声来合成相应的噪声模型，其标准差定义为原始模型边界框直径的0.012，0.006，0.00125，从而生成包含32个模型的训练数据库。测试数据集由22个形状组成，包括小雕像、cad模型以及解析形状。

3.2. 评价指标

为了对本文算法的法向估计性能进行定量分析，本文使用了两种不同的评价指标：无定向的均方根误差(rmse) [22]以及偏差小于给定角度的点数在总点数中的百分比(pgp) [23]。其中，rmse定义为：

rmse= 1 | p | ∑ p i ∈p 〈 n ¯ i , n ^ i 〉 2 ,(9)

该值越低则表示法向估计效果越好。同时，通过使用pgp评价指标来分析在给定角度阈值情况下，好点(即偏差小于给定角度的点)所占比例以及所处结构位置。

3.3. 定量比较

对于法向估计效果，为了能够更好验证本文方法的有效性，将本文方法与hf-cubes [16]、houghcnn [17]以及lrrfast [15]三种算法进行比较。表1展示了这三种算法与本文算法所估计法向与真实法向之间的rmse误差结果。从表中可以看出，从整体效果来看lrrfast算法的法向估计效果优于houghcnn算法，而houghcnn算法的法向估计效果又优于hf-cubes算法。对于本文算法，在噪声变化情况下，无论是无噪声还是小、中、大噪声，本文算法的rmse值均低于其他三种算法，即本文的法向估计效果均优于这三种方法。并且在噪声变化时，houghcnn算法的rmse值波动较大，在大噪声时甚至达到33.39，即该算法容易受到噪声变化的干扰。而本文算法在大噪声时的法向估计效果较houghcnn方法提升了8.39，并随着噪声增大其rmse值没有较大波动，说明了本文算法设计的鲁棒性。在密度变化情况下，对于梯度和条状密度变化，本文法向估计效果与其他三种算法相比均有提升，表明了本文算法在点云数据缺失或分布不规则等情况下具有更强的适应性以及稳定性。

table 1. comparison of rmse values for various normal estimation algorithms

表1. 各类法向估计算法的rmse值比较

3.4. 定性分析

图4展示了在无噪声、条状密度变化、梯度密度变化以及0.01、0.05、0.1三种噪声尺度下本文算法对“cylinder”、“cup”、“boxy_smooth”以及“boxunion”四种模型的可视化结果。其中点的颜色表示该点估计法向与真实法向之间的角度差异，角度差异大于等于20˚的点被渲染为红色，小于20˚的点则被渲染为蓝色，并在每个图形下标出其小于20˚点所占比例。

figure 4. visualization of normal estimation results for different shapes using our algorithm

图4. 本文算法对于不同形状法向估计结果的可视化

首先，从图4中第四行到第六行观察可知，随着噪声逐渐增大，红点数量有所增加。但仔细观察细节处，如尖锐边缘和角点部位，这些位置增加的红点是局部且有限的，同时平坦区域的红点数量增加较少，表明本文算法在平坦区域能获得较好质量的法向。其次，观察第二行与第三行，在条状密度变化以及梯度密度变化情况下，与第一行的无噪声情况下可视化结果相近，其pgp值也非常相近，表明本文算法在物体存在遮挡情况下也能保持较好的法向估计效果，体现了本文算法在点云数据缺失或分布不规则时具有一定适应性和稳定性。最后，在小、中噪声情况下，如图3中第四、五行，从左至右，随着形状复杂程度增大，红点数量变化波动较小，pgp值变化波动也较小，表明本文算法在小、中噪声情况下对形状复杂变化具有一定的适应能力，能够较为稳定地估计出法向结果。

4. 结语

本文提出了一种基于特征聚合的深度霍夫变换法向估计网络。该网络在houghcnn基础上加入了特征聚合，通过将点特征转换为切平面特征来减少霍夫变换过程中的特征损失，从而提升cnn的输入，进而提高网络整体的法向估计质量。实验表明，本文在添加特征聚合后，法向估计效果有明显提升，对于不同尺度噪声也具有鲁棒性。此外，本文方法在点云数据缺失或分布不均匀情况下也能取得较好的法向。

对于未来工作，可以对更多形式的特征聚合的有效性进行研究，优化特征聚合，提升卷积神经网络的输入。也可以尝试将特征聚合与更多法向估计网络相结合，进一步提升现有法向估计网络的性能。

基金项目

国家自然科学基金(62076115, 61702245)；辽宁省教育厅基金面上项目(ljkmz20221434)。

notes

^*通讯作者。

参考文献