法律状态公告日
法律状态信息
法律状态
2022-07-05
授权
发明专利权授予
技术领域
本发明涉及计算机数据处理技术领域，尤其涉及一种基于豪斯多夫距离和 平均投影距离局部熵的点云精简方法。
背景技术
随着科学技术的发展，激光扫描设备不停地更新换代推陈出新，三维实物 可以通过激光扫描设备将几何信息保存至存储设备中。随着三维激光扫描仪精 度的不断提高，单次扫描所获得的点云模型的数据量成倍增长，与此同时带来 的问题是密集的点云数据中存在的大量冗余数据。这些冗余数据的存在将极大 地增加了三维模型点云数据进行存储、传输及计算等任务处理的开销，且给后 续进行曲面拟合和模型重建等相关工作带来了巨大挑战。因此需要提高对三维 模型点云数据的精简效果。
发明内容
本发明的目的在于提供一种基于豪斯多夫距离和平均投影距离局部熵的点 云精简方法，提高对三维模型点云数据的精简效果。
为实现上述目的，本发明提供了一种基于豪斯多夫距离和平均投影距离局 部熵的点云精简方法，包括以下步骤：
对获取的原始点云数据进行降采样处理，并搜索到多个近邻点后，利用主 成分分析法计算出每个点云对应的平均投影距离；
将所述原始点云数据划分为边缘点云集和待精简点云集，并计算出所述待 精简点云集对应的第一豪斯多夫距离平均值和所述平均投影的信息熵值；
基于细分准则利用八叉树对所述待精简点云集进行剖分，并计算出每个子 立方体对应的第二豪斯多夫距离平均值；
将所述第一豪斯多夫距离平均值与所述第二豪斯多夫距离平均值的比值与 设定的多个判断阈值进行比较，根据比较结果和所述信息熵值对所述待精简点 云集进行精简；
将所述边缘点云集和精简后的点云进行合并拼接，得到对应的三维模型。
其中，将所述原始点云数据划分为边缘点云集和待精简点云集，并计算出 所述待精简点云集对应的第一豪斯多夫距离平均值和所述平均投影的信息熵 值，包括：
根据多个所述近邻点构建最小二乘平面，并将所述近邻点投影到所述最小 二乘平面上，将得到对应的多个投影点对应的比值与设定的第一阈值进行比较， 得到第一边缘点；
利用设定的第二阈值对点云密度直方图进行划分，并对提取出的点云数据 进行降采样处理，得到第二边缘点；
将所述第一边缘点和所述第二边缘点划分为边缘点云集，将所述原始点云 数据中除所述边缘点云集的点云划分为待精简点云集；
计算出所述待精简点云集对应的第一豪斯多夫距离平均值和所述平均投影 的信息熵值。
其中，计算出所述待精简点云集对应的第一豪斯多夫距离平均值和所述平 均投影的信息熵值，包括：
计算出所述待精简点云集中每个点云对应的第三豪斯多夫距离，并将所述 第三豪斯多夫距离按照降序排列后，将第一个所述第三豪斯多夫距离作为第一 豪斯多夫距离，并根据所述第一豪斯多夫距离计算出对应的第一豪斯多夫距离 平均值；
基于信息熵公式，计算出所述平均投影距离的信息熵值，并将所述信息熵 值按照降序进行排列。
其中，基于细分准则利用八叉树对所述待精简点云集进行剖分，并计算出 每个子立方体对应的第二豪斯多夫距离平均值，包括：
基于细分准则，利用八叉树法对构建的立方体进行剖分，直至得到的子立 方体中的点云数量小于剖分阈值；
计算出每个所述子立方体对应的第二豪斯多夫距离平均值。
其中，计算出每个所述子立方体对应的第二豪斯多夫距离平均值，包括：
计算出每个所述子立方体中所有点云对应的第四豪斯多夫距离，并将所述 第四豪斯多夫距离按照降序排列后，将第一个所述第四豪斯多夫距离作为第二 豪斯多夫距离，并计算出对应的第二豪斯多夫距离平均值。
其中，将所述第一豪斯多夫距离平均值与所述第二豪斯多夫距离平均值的 比值与设定的多个判断阈值进行比较，根据比较结果和所述信息熵值对所述待 精简点云集进行精简，包括：
计算所述第一豪斯多夫距离平均值与所述第二豪斯多夫距离平均值的比 值，并将所述比值对设定的多个判断阈值进行比较，得到点云简化因子；
若所述比值大于设定的多个所述判断阈值，则根据所述点云简化因子推算 出所述子立方体内需精简点云的数量，并根据所述信息熵值大小进行精简；
若所述比值均小于所有的所述判断阈值，则利用设定数量个的点云对立方 体内的所述待精简点云集进行替换。
其中，若所述比值大于设定的多个所述判断阈值，则根据所述信息熵值大 小进行精简，包括：
若所述比值大于任一所述判断阈值，则根据所述点云简化因子推算出所述 子立方体内需精简点云的数量，并根据对应的所述信息熵值对所述待精简点云 集进行精简；
若所述比值大于多个所述判断阈值中的至少一个所述判断阈值，则将对应 的所述信息熵值进行降序排列，并按照排列顺序对所述待精简点云集进行精简。
本发明的一种基于豪斯多夫距离和平均投影距离局部熵的点云精简方法， 对获取的原始点云数据进行降采样处理，并搜索到多个近邻点后，利用主成分 分析法计算出每个点云对应的平均投影距离和所述平均投影的信息熵值；将所 述原始点云数据划分为边缘点云集和待精简点云集，并计算出对应的第一豪斯 多夫距离平均值；基于细分准则利用八叉树对所述待精简点云集进行剖分，并 计算出每个子立方体对应的第二豪斯多夫距离平均值；将所述第一豪斯多夫距 离平均值与所述第二豪斯多夫距离平均值的比值与设定的多个判断阈值进行比 较，根据比较结果和所述信息熵值对所述待精简点云集进行精简；将所述边缘 点云集和精简后的点云进行合并拼接，得到对应的三维模型，提高对三维模型点云数据的精简效果。
附图说明
为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施 例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述 中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付 出创造性劳动的前提下，还可以根据这些附图获得其他的附图。
图1是本发明提供的一种基于豪斯多夫距离和平均投影距离局部熵的点云精 简方法的步骤示意图。
图2是本发明提供的一种基于豪斯多夫距离和平均投影距离局部熵的点云精 简方法的流程示意图。
图3是本发明提供的计算投影距离的示意图。
图4是本发明提供的投影点检测原理的示意图。
图5是本发明提供的进行口腔模型边缘轮廓点提取保留效果的示意图。
图6是本发明提供的口腔模型精简结果的示意图。
图7是本发明提供的进行兔和龙边缘轮廓点提取保留效果的示意图。
图8是本发明提供的对兔子模型的点云精简效果图。
图9是本发明提供的对龙模型的点云精简效果图。
具体实施方式
下面详细描述本发明的实施例，所述实施例的示例在附图中示出，其中自 始至终相同或类似的标号表示相同或类似的元件或具有相同或类似功能的元 件。下面通过参考附图描述的实施例是示例性的，旨在用于解释本发明，而不 能理解为对本发明的限制。
在本发明的描述中，“多个”的含义是两个或两个以上，除非另有明确具 体的限定。
请参阅图，本发明提供一种基于豪斯多夫距离和平均投影距离局部熵的点 云精简方法，包括以下步骤：
S101、对获取的原始点云数据进行降采样处理，并搜索到多个近邻点后， 利用主成分分析法计算出每个点云对应的平均投影距离。
具体的，获取三维模型原始点云数据，通过点云降采样样处理实现三维模 型点云的初次简化，建立k-d树搜索每个数据点的k个近邻点，使用主成分分 析法(PCA)计算每个点云的法向量，并计算出其平均投影距离值。
平均投影距离可较好地体现曲面凹凸状况，而局部分布密度可较好地体现 空间区域点云疏密情况。设样本点为p，其k个近邻点为p
其中，样本点为p，其k个近邻点p
d为拟合平面到坐标原点的空间距离。
C为半正定的协方差矩阵，由计算公式(2)即求解半正定的协方差矩阵C， 可得到不同的特征值：λ
式(3)符号的具体解释为：
ni为样本点p的第i个近邻点的法向量(即带方向的向量)，为向量1；
(p-pi)为样本点p与近邻点pi两点的三维坐标进行相减 (x1-x2,y1-y2,y1-y2)，可确定一个向量，为向量2；
|n
然后,求取样本点到每个近邻点所在拟合平面的投影距离，最后进行求平 均。
计算公式为：(分子:所有投影距离进行累加
公式(4)解释：
构建一个最小包围球体，包围k个近邻点。其中，k为近邻点的个数，r为 包围球体的半径，π为圆周率。因此，计算密度公式如式子(4)，密度ρ
S102、将所述原始点云数据划分为边缘点云集和待精简点云集，并计算出 对应的第一豪斯多夫距离平均值和所述平均投影的信息熵值。
具体的，根据多个所述近邻点构建最小二乘平面，并将所述近邻点投影到 所述最小二乘平面上，得到对应的多个投影点，将所述投影点在所述最小二乘 平面两侧的数量之差与多个所述近邻点数量之间的比值，与设定的第一阈值进 行比较，从而判断该样本点是否为边缘点。若比值大于所述第一阈值，得到第 一边缘点。
基于点云局部分布密度情况，利用设定的第二阈值对点云密度直方图进行 划分，并对提取出的点云数据进行降采样处理，得到第二边缘点，当使用在口 腔模型中时，所述第二边缘点云为牙齿间隙点云。第二边缘点云的提取及相应 降采样样处理步骤仅针对特定模型：口腔模型中进行。
将所述第一边缘点和所述第二边缘点划分为边缘点云集，将所述原始点云 数据中除所述边缘点云集的点云划分为待精简点云集。
利用点云的主曲率的豪斯多夫(Hausdorff)距离来确定点集之间的相似性， 从而确定点云所在局部区域内数据点的特征程度。计算出所述待精简点云集中 所有点云对应的第三豪斯多夫距离，Hausdorff距离计算如下：
其中，设样本点p的主曲率为ki,kj，而样本点p的任一近邻点的主曲率为 ki’，kj’，然后，计算得到豪斯多夫距离数值为H1，此为单次进行豪斯多夫 距离计算过程。
将所述第三豪斯多夫距离按照降序排列后，将第一个所述第三豪斯多夫距 离作为第一豪斯多夫距离，即取所述第三豪斯多夫距离的最大值作为样本点的 第一豪斯多夫距离，计算如下：
H
其中，由于样本点p具有k个近邻点，对每一个近邻点都重复一次上述豪 斯多夫距离计算过程，即公式(5)计算得到豪斯多夫距离的数值的符号表示分 别为H2,H3,...,Hk。然后，取其最大值为样本点p豪斯多夫距离的数值，符号 表示为Hp。
S103、基于细分准则利用八叉树对所述待精简点云集进行剖分，并计算出 每个子立方体对应的第二豪斯多夫距离平均值。
具体的，基于细分准则，利用八叉树法对构建的立方体进行剖分，直至得 到的子立方体中的点云数量小于剖分阈值，具体为：为了能获得各小立方体， 首先生成一个能包含三维模型的剩余点云的最小立方体V
L＝Max((X
利用八叉树进行空间分割，根据点云所在空间位置坐标将其纳入到不同的 子立方体空间中。设定八叉树终止剖分条件为子立方体的点云数量小于剖分阈 值u，因此，当子立方体没有点云，或者点云数量大于剖分阈值u，则继续进行 八叉树剖分；反之，则停止八叉树剖分。
计算出每个所述子立方体中所有点云对应的第四豪斯多夫距离，并将所述 第四豪斯多夫距离按照降序排列后，将第一个所述第四豪斯多夫距离作为第二 豪斯多夫距离，并计算出对应的第二豪斯多夫距离平均值，其中，所述第四豪 斯多夫距离可以为步骤S102中的第三豪斯多夫距离，第四豪斯多夫距离的计算 公式为：
其中，设样本点p的主曲率为ki,kj，而样本点p的任一近邻点的主曲率为 ki’，kj’，然后，计算得到豪斯多夫距离数值为H1，此为单次进行豪斯多夫 距离计算过程。
第二豪斯多夫距离的计算公式为：
H
其中，由于样本点p具有k个近邻点，对每一个近邻点都重复一次上述豪 斯多夫距离计算过程，即公式(5)计算得到豪斯多夫距离的数值的符号表示分 别为H2,H3,...,Hk。然后，取其最大值为样本点p豪斯多夫距离的数值，符号 表示为Hp。
将平均投影距离与信息熵理论相结合，某一数据点的信息熵值可表示为对 某类特征的隶属程度。信息熵定量表达如下：
其中，K为某个固定正的常数，
Pi为事件Xi出现的对应概率，
且
设数据点p为样本点，则该点对应平均投影距离的信息熵值计算如下：
其中，w与w
在一定程度上，平均投影距离信息熵值能反映三维模型表面的几何特征情 况。熵值越大，点云所在区域越趋近于平面特征；反之，则表示点云所在区域 越趋近于曲面特征，若该点云被精简，模型表面区域的几何特征信息将会丢失。 因此，本发明计算点云的平均投影距离局部熵并根据熵值大小进行排序后，将 优先简化熵值较大的点云，以保留局部熵值较小的点云作为特征点。
S104、将所述第一豪斯多夫距离平均值与所述第二豪斯多夫距离平均值的 比值与设定的多个判断阈值进行比较，根据比较结果和所述信息熵值对所述待 精简点云集进行精简。
具体的，由于立方体所包含的特征点云数量不相同，可认为立方体具有不 同的特征程度。本发明设定多级点云简化准则，内容包括多个判断阈值 λ
计算各个所述子立方体内所述第一豪斯多夫距离平均值与所述第二豪斯多 夫距离平均值的比值λ，并将所述比值对设定的多个判断阈值λ
步骤1，若比值λ大于任一某个判断阈值λ
步骤2，若比值λ皆小于所有的所述判断阈值λ
设所有非特征立方体的点云总数为num
以八叉树的任意一个子立方体为例，设该立方体为非特征立方体，其包含 的点云数为n，则该立方体内点云保留数量n
其中，
例：当λ大于λ
其中，点云集的“点云分布重心”位置坐标的计算方法：设三个点云坐标 为(x1,y1,z1),(x2,y2,z2),(x3,y3,z3),则点云分布重心空间坐标为：
S105将所述边缘点云集和精简后的点云进行合并拼接，得到对应的三维模 型。
具体的，将精简后的点云、边缘点云集进行合并拼接输出，进而得到三维 模型最终精简后的点云。
下面通过实验对上述过程及结果进行说明。
表1为不同算法的简化率和运行时间，图6为相应的口腔模型精简结果， 其中，图6中(a)为非均匀降采样样后的点云，(b)为本发明算法，(c)为基于八 叉树的简化方法，(d)为基于Hausdorff距离的简化方法，(e)为基于权积局部 熵的简化方法。图7为相应的口腔模型重建结果，其中，图7中(a)为非均匀降 采样样后的点云，(b)为本发明算法，(c)为基于八叉树的简化方法，(d)为基于 Hausdorff距离的简化方法，(e)为基于权积局部熵的简化方法。
表1不同算法的简化率和运行时间
由表1及图6可知：在相近的点云简化度情况下，相比于图6(c)和图6(d)， 图6(b)本发明算法对牙齿间隙点云(第二边缘点云)数量保留更少，而在牙齿 轮廓及牙齿结构等特征区域保留了更多的点，且合理简化平坦区域的点云。图 6(b)的本发明算法对特征点提取和非特征点简化显得更为合理。
在相近的点云简度情况下，本发明算法能准确地提取牙齿轮廓、牙齿结构 等区域点，很好地保留口腔模型的细节特征。同时，对牙齿间隙点云的非均匀 降采样样及对平坦区域点云的合理简化，可有效地避免孔洞的发生。
而其他对比算法在一定程度上存在着不能很好地适用于口腔模型的情况， 主要原因为算法没有考虑实验对象的点云特性导致步骤设计不合理或存在错 误。比如图6(e)的基于权积局部熵的简化方法，权值积局部熵值不能很好地体 现点云在模型区域的几何特征属性，且通过单个点云的权值积局部熵值与簇内 点云局部熵平均值进行比较的方式判定提取特征点云保留，容易造成强特征区 域点云过度简化。对于具有大量复杂特征的三维模型来说，容易导致模型表面 几何特征严重丢失。而本发明算法根据口腔模型点云特征分析合理设置多级简 化准则，通过对立方体进行特征程度评估以衡量确定对应点云简化因子，实现 非特征点云合理简化与特征点有效提取。在口腔模型进行点云特性分析的基础上，完成本发明算法的算法步骤设计，因此，本发明算法能很好地适用于曲面 复杂、点云数据量庞大、采样不均匀的口腔模型，在点云简化结果及重建结果 上都具有良好的表现。
由于本发明算法能够更好地保留口腔模型中牙齿轮廓和牙齿结构等特征区 域点云，合理简化平坦区域点云，并对牙齿间隙点云进行非均匀降采样样处理。 口腔模型的细节特征具有良好的保持效果，平坦区域没有产生孔洞且牙齿间隙 仅存在少量且面积较小的孔洞。经过本发明算法进行简化处理后的点云在后续 的三维重建任务中仍具有较好的重建结果。
综上所述，本发明算法提出了一种基于Hausdorff距离和平均投影距离局 部熵的点云精简算法。实验证明，在一定的简化程度条件下，本发明算法能更 好地保持口腔模型的细节特征，口腔模型点云精简结果及重建结果皆优于其他 对比算法。因此，本发明算法具有一定的有效性及优越性。
为了验证本发明算法的有效性，将其算法除第二边缘点云提取及降采样样 处理外的其他关键步骤应用于兔子模型与龙模型中，进行精简实验，分别得到 以下的点云简化情况结果表与点云处理效果图。
表2为本文算法的点云简化情况结果表，图7为兔子模型与龙模型的边缘 轮廓点提取效果图，图8和图9分别为兔子模型与龙模型的精简结果。图8(a) 兔子模型原始点云，图8(b)～(d)分别为兔子模型不同简化率下点云简化结果； 图9(a)和图9(b)分别为龙模型的原始点云及降采样样后的点云，图9(c)～(e) 分别龙模型为不同简化率下点云简化结果。简化率为被简化的点云数量占降采 样样后的点云数量的比值。
表2本文算法点云简化情况
结合表2及图8可知：本算法能在兔子模型的细节特征部分，例如耳朵， 脖子等部位保留更多的点，而在兔子腿部及背部等平坦区域保留的点数较少。
结合表2及图9可知：本算法能在龙模型的细节特征部分，例如龙的触角， 尾巴，脚以及身体边界等部位能保留更多的点，而在相对平滑的区域如龙的身 体保留较少的点。
通过上述实验，我们可以发现：在较高简化率的情况下，本算法能较好地 保持三维模型的众多细节特征，且能有效简化模型平坦区域的点云，不出现孔 洞现象，在精度上有一定的优势。
在实际应用中，本发明算法可根据实际简度及精度要求，对多级点云简化 准则的多个阈值及点云简化因子进行灵活调整，以更好地应用于不同类型的三 维模型。
本发明的一种基于豪斯多夫距离和平均投影距离局部熵的点云精简方法， 对获取的原始点云数据进行降采样处理，并搜索到多个近邻点后，利用主成分 分析法计算出每个点云对应的平均投影距离；将所述原始点云数据划分为边缘 点云集和待精简点云集，并计算出对应的第一豪斯多夫距离平均值；基于细分 准则利用八叉树对所述待精简点云集进行剖分，并计算出每个子立方体对应的 第二豪斯多夫距离平均值和所述平均投影的信息熵值；将所述第一豪斯多夫距 离平均值与所述第二豪斯多夫距离平均值的比值与设定的多个判断阈值进行比 较，根据比较结果和所述信息熵值对所述待精简点云集进行精简；将所述边缘 点云集和精简后的点云进行合并拼接，得到对应的三维模型，提高对三维模型点云数据的精简效果。
以上所揭露的仅为本发明一种较佳实施例而已，当然不能以此来限定本发 明之权利范围，本领域普通技术人员可以理解实现上述实施例的全部或部分流 程，并依本发明权利要求所作的等同变化，仍属于发明所涵盖的范围。
