一种点云法向量计算的DSP并行方法、系统及介质与流程

一种点云法向量计算的dsp并行方法、系统及介质
技术领域
1.本发明涉及图像数据处理技术领域，特别是涉及一种点云法向量计算的ds p并行方法、系统及介质。


背景技术：

2.点云法向量计算广泛应用于人脸识别、虚拟现实、工业自动化、机器人和自动驾驶等三维重建领域。随着激光雷达、深度摄像头、cad模型、slam\sf m等获取点云设备的飞速发展，点云获取的稳定性和精度也得到了很大提升。这就对点云法向量计算的速度和精度提出了更高的要求。由于三维图像处理数据量巨大，运算复杂，单纯依靠通用cpu很难满足现行三维重建实时性的需求。为了降低计算复杂度，现有以下应对方案：
3.现有技术一，cn104123746a公开了一种三维扫描点云实时法向量的计算方法。该方法对点云数据按kd树划分，利用kd树查找i个邻域点，根据主成分分析(pca)对查找的邻域点拟合平面后，求得点云数据各个点的法向量，通过加权平均算法计算出点云数据的每个数据点在半径为r内各个邻域点的法向量加权均值，再设置阈值评估各个点法向量的可信度。该方法从邻域点的选取和法向量计算结果进行加权平均，在边界的一些点更趋向于平滑，但在计算速度上效率不高。
4.现有技术二，cn104200507a公开了一种三维点云点法向量估计方法。该方法在空间邻域中确定各点的k近邻点，根据k近邻点计算各点的初始法向量，拟合平面，根据k近邻点到平面的距离远近选出距离最近60％～80％的k近邻点，在第一次选出的k近邻点中再选出与该点的法向量夹角最小的60％～80％的k近邻点，剔除噪声点，计算选出点的稳定的法向量。该方法先后使用距离判断和方向一致性剔除k近邻中不稳定的点，从而计算得到点云中点的较稳定的法向量，但容易陷入局部最优，无法保留点云的全部特征。
5.综上所述，现有的点云法向量方案大多都是逐点计算针对精度进行提升，计算效率不高。点云法向量计算过程包括选取求解法向量点的领域点进行平面拟合，再通过pca主成分分析方法，求得在三维方向上投影点分布最密集方差最小的法向量。现有方法从邻域点进行平面拟合方向入手，分为剔除噪声点和选取所有点的方法进行精度的提升；也有对求得邻域点的法向量进行加权均值评估。大多数设计者普遍采用的pca主成分分析方法，其中占大量计算的经典svd算法，求得的点云协方差矩阵特征值和特征向量精度不是很高，计算时间开销大。


技术实现要素：

6.本发明的主要目的为：为了加快点云法向量计算的速度，本发明提供一种点云法向量计算的dsp并行实现方法，能够更快地处理三维图像数据，实时地完成点云的三维重建。
7.为实现上述目的，本发明采用的一个技术方案是：提供一种点云法向量计算的dsp并行方法，包括以下步骤：
8.s1，读取点云数据；设一个三维点云的集合p，p中点的个数为n；
9.s2，取点云数据的每个数据点在半径为r的k个邻域点；
10.s3，利用simd方法对邻域点求平均拟合得到平面，求中心点；
11.s4，利用simd方法对邻域点集去中心化；
12.s5，利用simd方法并行计算协方差矩阵；
13.s6，缩放协方差矩阵，利用行列式求解特征值；
14.s7，将特征值带入行列式求得对应的特征向量；
15.s8，根据主成分分析法得到法向量；
16.s9，法向量定向，据特征值求得拟合平面的曲率，完成法向量计算。
17.作为一种改进方案，所述步骤s2进一步包括：对于点云数据p中的每个数据点pi(xi,yi,zi),i＝1,2,
…
,n，以数据点为中心在半径为r查找k个邻域点构成邻域点集合b＝{bi},i＝1,2,
…
,k。
18.作为一种改进方案，所述步骤s3进一步包括：调用主元分析法对所述步骤s2查找到的领域点拟合出一个平面，计算拟合平面的中心
19.作为一种改进方案，所述步骤s4进一步包括：对拟合平面去中心化b-μb；
[0020][0021]
作为一种改进方案，所述步骤s5进一步包括：对去中心化后的拟合平面求自协方差矩阵σ；
[0022][0023]
作为一种改进方案，所述步骤s6进一步包括：对σ进行归一化，使其中各个值∈[-1,1]，得到矩阵m：
[0024]
c＝max(|∑
ij
|)
[0025][0026]
作为一种改进方案，所述步骤s7进一步包括：
[0027]
对缩放后的协方差矩阵m利用对称特性求行列式|λe-m|＝0；
[0028][0029]
作为一种改进方案，所述步骤s8进一步包括：
[0030]
s81，利用三角解法求得特征值λ1,λ2,λ3；
[0031][0032][0033][0034]
其中
[0035][0036]
s82，将特征值分别代入行列式求得对应的特征向量；
[0037]
s83，根据主成分分析法，特征值最小对应的特征向量即法向量。
[0038]
本发明还提供一种点云法向量计算的dsp并行系统，包括：包括：获取模块、构建模块和计算模块；
[0039]
所述获取模块用于读取点云数据并发送至所述构建模块；
[0040]
所述构建模块用于取点云数据的每个数据点在半径为r的k个邻域点，构建邻域点集合；
[0041]
所述计算模块用于执行法向量计算，所述法向量计算包括：利用simd方法对邻域点求平均拟合得到平面，求中心点；利用simd方法对邻域点集去中心化；利用simd方法并行计算协方差矩阵；缩放协方差矩阵，利用行列式求解特征值；将特征值带入行列式求得对应的特征向量；根据主成分分析法得到法向量；根据特征值求得拟合平面的曲率，完成法向量计算。
[0042]
本发明还提供一种计算机可读存储介质，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现所述dsp并行方法的步骤。
[0043]
本发明的有益效果是：
[0044]
1、本发明所述的点云法向量计算的dsp并行方法，利用协方差矩阵实对称的特性和dsp并行的simd方法，在同频率下加快点云法向量计算的速度，利用3x3自协方差矩阵实对称的特性和三角解法，提升法向量计算的精度，在选取所有点和剔除噪声点的情况下均能获得更好的结果。
[0045]
2、本发明所述的点云法向量计算的dsp并行系统，利用simd方法求三维点云的协方差矩阵，取多个数据点同时进行计算，在同频率下算法效率更高；利用自协方差矩阵实对称的特性和三角解法，能够更精确地计算得到特征值和特征向量，获得更准确的三维点云法向量的计算结果。
[0046]
3、本发明所述的计算机可读存储介质，能够更快地处理三维图像数据，实时地完成点云的三维重建。
附图说明
[0047]
为了更清楚地说明本发明具体实施方式或现有技术中的技术方案，下面将对具体实施方式或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图是本发明的一些实施方式，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
[0048]
图1是本发明实施例1所述点云法向量计算的dsp并行方法的流程示意图；
[0049]
图2是本发明实施例1所述点云法向量计算的dsp并行方法中步骤s5与现有技术中采用标量运算的效果对比图；
[0050]
图3是本发明实施例2所述点云法向量计算的dsp并行系统的架构图。
具体实施方式
[0051]
下面结合附图对本发明的较佳实施例进行详细阐述，以使本发明的优点和特征能更易于被本领域技术人员理解，从而对本发明的保护范围做出更为清楚明确的界定。
[0052]
在本发明的描述中，需要说明的是，本发明所描述的实施例是本发明一部分实施例，而不是全部的实施例；基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
[0053]
在本发明的描述中，需要说明的是：
[0054]
dsp：数字信号处理技术；
[0055]
simd方法：simd是指单指令多数据流，即一条指令处理多个数据，sim d方法即指基于simd的并行处理方法；
[0056]
pca：主成分分析方法。
[0057]
实施例1
[0058]
本实施例提供一种点云法向量计算的dsp并行方法，以所有点均为有效点，且选取每个数据点在半径为r的k个近邻点为例说明本方案；如图1所示，具体包括以下步骤：
[0059]
s1，读取点云数据，具体为：设一个三维点云的集合p，p中点的个数为n；
[0060]
s2，取点云数据的每个数据点在半径为r的k个邻域点，具体为：对于点云数据p中的每个数据点pi(xi,yi,zi),i＝1,2,
…
,n，以数据点为中心在半径为r查找k个邻域点构成邻域点集合b＝{bi},i＝1,2,
…
,k，k的取值为区间[5,16]；
[0061]
s3，利用simd方法对邻域点求平均拟合得到平面，求中心点；具体为：调用主元分析法(pca)对上述查找的领域点拟合出一个平面，计算拟合平面的中心
[0062]
s4，利用simd方法对邻域点集去中心化；具体表示为：对拟合平面去中心化b-μb；
[0063][0064]
s5，利用simd方法并行计算协方差矩阵；具体包括以下步骤：
[0065]
对去中心化后的拟合平面求自协方差矩阵σ；
[0066][0067]
simd(single instruction multiple data)即单指令多数据流，同时对一组数据向量中的每一个分量分别执行相同的操作，从而实现并行。由上式可知自协方差矩阵是实对称矩阵，可以简化计算σ上三角矩阵的值，并且自协方差矩阵σ的计算过程中，元素可以利用simd方法，最大可同时处理16个点的计算，独立分块计算的同时减少分块矩阵乘法的局部存储量，节省内存开销，并行计算提高效率，在同频率下算法效率更高。如图2所示，使用标量运算一次只能对一对数据执行乘法操作，利用simd乘法指令可以同时对8对数据同时执行乘法操作，并对结果求和求得
[0068]
s6，缩放协方差矩阵，利用行列式求解特征值；具体为：
[0069]
对σ进行归一化，使其中各个值∈[-1,1]，得到矩阵m：
[0070]
c＝max(|∑
ij
|)
[0071][0072]
s7，将特征值带入行列式求得对应的特征向量；具体为：
[0073]
对缩放后的协方差矩阵m利用对称特性求行列式|λe-m|＝0:
[0074][0075]
s8，根据主成分分析法得到法向量；
[0076]
s9，法向量定向；根据特征值求得拟合平面的曲率，完成法向量计算。在本实施例中，步骤s8具体的操作步骤如下：
[0077]
s81，利用三角解法求得特征值λ1,λ2,λ3：
[0078][0079][0080][0081]
其中
[0082][0083]
s82，将特征值分别代入行列式求得对应的特征向量；
[0084]
s83，根据主成分分析法，特征值最小对应的特征向量即法向量。
[0085]
实施例2
[0086]
本实施例基于与实施例1中所述的一种点云法向量计算的dsp并行方法相同的发明构思，提供一种点云法向量计算的dsp并行系统，如图3所示，包括：获取模块、构建模块和计算模块；所述获取模块用于读取点云数据并发送至所述构建模块，所述构建模块用于取点云数据的每个数据点在半径为r的k个邻域点，构建邻域点集合；所述计算模块用于执行法向量计算，所述法向量计算包括：利用simd方法对邻域点求平均拟合得到平面，求中心点；利用simd方法对邻域点集去中心化；利用simd方法并行计算协方差矩阵；缩放协方差矩阵，利用行列式求解特征值；将特征值带入行列式求得对应的特征向量；根据主成分分析法得到法向量；根据特征值求得拟合平面的曲率，完成法向量计算。
[0087]
实施例3
[0088]
本实施例提供一种计算机可读存储介质，包括：
[0089]
所述存储介质用于储存将上述实施例1所述的点云法向量计算的dsp并行方法实现所用的计算机软件指令，其包含用于执行上述为所述点云法向量计算的dsp并行方法所设置的程序；具体的，该可执行程序可以内置在实施例2所述的点云法向量计算的dsp并行系统中，这样，点云法向量计算的dsp并行系统就可以通过执行内置的可执行程序实现所述实施例1所述的点云法向量计算的dsp并行方法。
[0090]
此外，本实施例具有的计算机可读存储介质可以采用一个或多个可读存储介质的任意组合，其中，可读存储介质包括电、光、电磁、红外线或半导体的系统、装置或器件，或者以上任意组合。
[0091]
区别于现有技术，采用本技术一种点云法向量计算的dsp并行方法、系统及介质，利用simd方法求三维点云的协方差矩阵，取多个数据点同时进行计算，在同频率下算法效率更高；利用自协方差矩阵实对称的特性和三角解法，能够更精确地计算得到特征值和特征向量，获得更准确的三维点云法向量的计算结果，最终弥补了现有技术的不足，具有极高
的应用价值和前瞻性。
[0092]
上述本发明实施例公开实施例序号仅仅为了描述，不代表实施例的优劣。
[0093]
本领域普通技术人员可以理解实现上述实施例的全部或部分步骤可以通过硬件来完成，也可以通过程序来指令相关的硬件完成的程序可以存储于一种计算机可读存储介质中，上述提到的存储介质可以是只读存储器，磁盘或光盘等。
[0094]
以上所述仅为本发明的实施例，并非因此限制本发明的专利范围，凡是利用本发明说明书及附图内容所作的等效结构或等效流程变换，或直接或间接运用在其他相关的技术领域，均同理包括在本发明的专利保护范围内。

技术特征：
1.一种点云法向量计算的dsp并行方法，其特征在于，包括以下步骤：s1，读取点云数据；设一个三维点云的集合p，p中点的个数为n；s2，取点云数据的每个数据点在半径为r的k个邻域点；s3，利用simd方法对邻域点求平均拟合得到平面，求中心点；s4，利用simd方法对邻域点集去中心化；s5，利用simd方法并行计算协方差矩阵；s6，缩放协方差矩阵，利用行列式求解特征值；s7，将特征值带入行列式求得对应的特征向量；s8，根据主成分分析法得到法向量；s9，法向量定向，据特征值求得拟合平面的曲率，完成法向量计算。2.根据权利要求1所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s2进一步包括：对于点云数据p中的每个数据点p
i
(x
i
,y
i
,z
i
),i＝1,2,
…
,n，以数据点为中心在半径为r查找k个邻域点构成邻域点集合b＝{b
i
},i＝1,2,
…
,k。3.根据权利要求2所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s3进一步包括：调用主元分析法对所述步骤s2查找到的领域点拟合出一个平面，计算拟合平面的中心4.根据权利要求3所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s4进一步包括：对拟合平面去中心化b-μ
b
；5.根据权利要求4所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s5进一步包括：对去中心化后的拟合平面求自协方差矩阵σ；6.根据权利要求5所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s6进一步包括：对σ进行归一化，使其中各个值∈[-1,1]，得到矩阵m：c＝max(|∑
ij
|)7.根据权利要求6所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤
s7进一步包括：对缩放后的协方差矩阵m利用对称特性求行列式|λe-m|＝0；8.根据权利要求7所述的一种点云法向量计算的dsp并行方法，其特征在于：所述步骤s8进一步包括：s81，利用三角解法求得特征值λ1,λ2,λ3；；；其中其中s82，将特征值分别代入行列式求得对应的特征向量；s83，根据主成分分析法，特征值最小对应的特征向量即法向量。9.基于权利要求1～8中任一项所述的一种点云法向量计算的dsp并行方法的dsp并行系统，其特征在于，包括：获取模块、构建模块和计算模块；所述获取模块用于读取点云数据并发送至所述构建模块；所述构建模块用于取点云数据的每个数据点在半径为r的k个邻域点，构建邻域点集合；所述计算模块用于执行法向量计算，所述法向量计算包括：利用simd方法对邻域点求平均拟合得到平面，求中心点；利用simd方法对邻域点集去中心化；利用simd方法并行计算协方差矩阵；缩放协方差矩阵，利用行列式求解特征值；将特征值带入行列式求得对应的特征向量；根据主成分分析法得到法向量；根据特征值求得拟合平面的曲率，完成法向量计算。10.一种计算机可读存储介质，其特征在于，所述计算机可读存储介质上存储有计算机程序，所述计算机程序被处理器执行时实现权利要求1～8中任一项所述dsp并行方法的步骤。

技术总结
本发明公开了一种点云法向量计算的DSP并行方法、系统及介质，所述方法包括以下步骤：读取点云数据；取点云数据的每个数据点在半径为r的k个邻域点；利用SIMD方法对邻域点求平均拟合得到平面，求中心点；利用SIMD方法对邻域点集去中心化；利用SIMD方法并行计算协方差矩阵；缩放协方差矩阵，利用行列式求解特征值；将特征值带入行列式求得对应的特征向量；根据主成分分析法得到法向量；据特征值求得拟合平面的曲率，完成法向量计算；本发明利用SIMD方法求三维点云的协方差矩阵，算法效率高；利用自协方差矩阵实对称的特性和三角解法，能够更精确地计算得到特征值和特征向量，获得更准确的三维点云法向量的计算结果。三维点云法向量的计算结果。三维点云法向量的计算结果。


技术研发人员：周文良
受保护的技术使用者：中科融合感知智能研究院（苏州工业园区）有限公司
技术研发日：2023.07.05
技术公布日：2023/10/11