基于改进SOM-K-Means 算法的三维点云分类

邬春学，胡真豪

（上海理工大学 光电信息与计算机工程学院，上海 200093）

0 引言

随着现代科技的逐步发展，人工智能成了各行各界的热点话题与研究对象。在人工智能领域中，图像分类技术［1-2］是一种常见的图像处理方式。目前，基于对二维图像的深入研究，已有为数可观的科研人员都将研究重点转向了三维图像的分类，但是由于三维图像包含的信息比二维图像更加复杂多样，这也导致了三维图像处理过程的时间成本大大增加，同时也给三维点云数据配准技术带来了不小的挑战。

当下，有2 类常见的三维图像分类，分别是：三维几何变换分类方法和三维点云分类方法。其中，三维点云数据具有无序性和稀疏性的等特点［3］。在传统的点云分类方法［4-8］中，是利用点云数据的局部属性来提取人工特征，但是这样的操作方式使得点云分类的精确度并不高。随着计算机技术的发展以及深度学习的兴起，越来越多的研究者尝试将深度神经网络应用于点云数据的分类中［9-14］，现已取得了令人满意的结果。

在早期对三维点云数据的研究中，研究人员是将分散在空间中的杂乱的点云数据经过处理转换为用体素格表示，再通过3 位卷积对处理后的点云数据进行特征提取。2015年，Maturana 等人［15］提出的VoxNet 方法，是将深度学习与图像分类相结合，并且以分布均匀的体素网格作为输入。VoxNet 的思想是用均匀分布的体素网格来代替不规则的点云，每个网格中包含的点的信息都可以用被占的网格信息来代替。VoxNet 的方法虽然能够解决由于点云自身无序所带来的问题，但是关于点云自身旋转变化的问题困扰却依然存在。此后，大量研究者对体素算法［16-18］进行改进，却也未能解决计算量庞大的问题。2017年，Klokov 等人［19］提出了Kd-Net 算法，Kd-Net 的思想就是先将整个三维点云数据模型分层，然后对每一层的点云数据进行特征提取，但是采用分层提取的Kd-Net 算法还是存在一定的局限性，对于旋转变换后的点云模型以及含有较多离群点和噪点的点云数据模型也未能取得较好的优化结果。2017年，Qi 等人［20］也提出了经典的深度学习模型PointNet，该模型将点云数据直接作为模型的输入。算法中，通过对均匀采样后的点云进行训练，利用点对称函数来减少对于点云自身无序性带来的问题影响，并通过引入三维旋转矩阵来解决点云自身的旋转问题。仍需指出，PointNet 算法虽然解决了点云自身的问题，却也仍然存在不足。原始点云经过均匀采样后，在降低计算复杂度的同时，却也丢失了点云的部分，降低了点云分类结果的准确性，且算法仅以三维点云数据的全局特征作为分类标准参考，并没有针对三维点云中更加多样化的局部特征进行处理。2018年，仍是由Qi等人［21］针对PointNet 存在的问题，提出了改进完善的PointNet++网络，采用分组提取特征的方式，只是这种方法并没有保留点云空间分布的特征，且在处理较大规模点云数据时会不可避免地增加计算复杂度。2020年，马京晖等人［22］提出在输入PointNet 网络前先进行点云预处理和点云聚类，再并行通过PointNet 网络，这样就较好地保留了点云的空间分布特性，但是研究中使用了K-Means 聚类，却会对初始的聚类中心和分类数目比较敏感，需要提前做出预设，而且针对不同种类模型预设的分类结果数却都是相同的，对后续的分类效果影响较大。

综上，本文在原有的K-Means-PointNet 网络模型上进行改进优化，提出了基于改进SOM-K-Means算法［23-27］的三维点云分类算法，主要研究内容包括：

（1）对原始点云数据进行预处理，对于点云密集区域进行简化，去除冗余的点和离群点，减少计算复杂度；对于点云稀疏区域进行稠密化操作，在稀疏点云中通过插值法进行稠密化操作，使得稀疏的点云能更好地反映点云模型的特征。针对不同密度的点云采用不同的预处理操作都是为了之后能更好地进行点云分类。

（2）对于预处理后的点云数据输入到SOM-KMeans 算法模型，由SOM 神经网络先进行粗聚类，得出输入点云数据的分类数和初始聚类中心，再用K-Means 聚类进行精细化聚类。

（3）为了能够完整保留三维点云数据的特性，采用并行方式将点云输入PointNet 网络进行特征提取。这种并行输入的方式也有利于减少算法的时间。

1 网络结构介绍

1.1 PointNet 结构介绍

PointNet 算法是将原始点云经过均匀采样，将采样后得到的所有点云数据作为算法的输入，输入的点云数据第一步操作时与空间变换旋转矩阵TNet相乘来对齐点云数据，以此来处理点云自身无序的问题。然后将输入的点云数据交给感知机，在由感知机提取多次特征后，就将与一个空间变换旋转矩阵T-Net相乘来对提取到的点云特征进行第二次的对齐。紧接着，整合感知机在各个维度上提取到的点云特征，由最大池化操作来得到点云的全局特征。最后，将全局特征通过mlp 来预测分类任务最后的分类数k，这里k是最后一层的输出数量，代表分类的个数，每个类别会对应于点云的分类得分。

对于PointNet 网络的优点，文中可做重点阐述如下：

（1）对原始点云数据进行处理，保留了原始点云的空间结构特征。

（2）通过学习到的T -Net空间变换矩阵来对齐点云，解决了点云自身旋转的问题，并且通过添加损失函数来保证点云的完整性以及对齐后点云的优越性。

（3）卷积神经网络在提取了每个维度的点云特征后，通过最大池化层将特征整合成点云的全局特征，这就有效地解决了点云自身无序的问题。虽然在提取特征时进行了降维操作，但是在整合后依旧保留了原有的特征。

不仅如此，PointNet 网络除了表现出更多优点外，同时却也存在着不足：保留了局部特征、却未做有效利用，仅以全局特征作为分类参考，缺少局部特征的参考，降低了点云数据分类的准确性。

故而，研究团队就在此基础上进行了二次优化，提出了PointNet++网络，解决了忽略局部特征的问题，但是由于局部特征是PointNet++网络在将点云分层后才提取的特征，而点云数据分层操作却增加了计算复杂度，从而增加了算法运行时间。这里给出了PointNet 算法流程的设计步骤，顺次表述如下。

输入一个N×3 的2D 张量

输出最后的分类结果

步骤1将输入的点云数据通过一个T-Net学习到的旋转矩阵来对齐点云。

步骤2将对齐后的点云经过最大池化操作进行特征提取。

步骤3使用T-Net对提取到的特征进行对齐。

步骤4将对齐后的特征进行最大池化。

步骤5将全局特征通过最大池化预测最后分类数；将局部特征和全局特征串联，通过最大池化得到每个数据点的分类结果。

1.2 本文算法结构研究

本文提出的算法考虑到PointNet 网络自身原有的优势并将其保留，保留空间旋转变换矩阵T-Net来解决点云自身旋转不变性的问题，保留最大池化层将各维度特征整合为全局特征的优势，在此基础上将聚类算法与点云特征相结合，减少运算量，加快运算速度。

首先对原始的点云数据进行预处理操作，将离群点和噪点剔除，将稠密点稀疏化，稀疏点云插值，将预处理过后的点云数据输入到SOM 神经网络中进行聚类，输出分类种数以及粗糙的分类结果。将输出的分类数目作为k值，执行K-Means 算法进行聚类，并对分类后的点云数据进行点云提取，多个类的点云同时进行特征提取，由于此过程为并行运算，并不会额外增加算法的运算量。此后通过最大池化层将提取到的点云特征进行整合，最后将整合的点云特征输入全连接网络，得到分类类别。

改进后的算法克服了原PointNet 网络忽略局部特征的问题，有效利用了局部特征，大大提高了目标点云分类的准确性。由于局部特征提取的过程为并行计算，所以不额外增加算法运算时间，在运算时间上优于PointNet++网络。本文算法流程如图1 所示。

图1 本文算法流程图Fig.1 The flow chart of the algorithm in this paper

1.2.1 点云数据预处理

原始的点云数据集中点云数据是杂乱的，是分布不均匀的，因此对点云数据进行预处理操作是有必要的。PointNet 网络模型采用了均匀采样的方式，忽略点云数据的不规则性，有可能降低最后的分类结果准确率。为了能够避免这一可能，本文借鉴数据分析的方法，在预处理阶段对不同密度状态下的点云进行不同的预处理操作，当点云数据在一个区域内过于密集时，就删减冗余的点云来降低点云密度，缩短运算时间；当局部点云数据过于稀疏时则进行三维点云稠密重建，通过点云插值以保证局部点云形态的完整性，提高分类的精度。本文预处理的设计流程如图2 所示。

图2 点云筛选流程图Fig.2 Flow chart of point cloud screening

1.2.1.1 部分点云高度集中

对于点云密集区域，为了将冗余的点云数据去除，采用等间隔的采样方法，计算采样后的点云数据量，判断是否超过目标阈值T0。由于本文改进的算法将与PointNet 算法进行比较验证，可将目标阈值T0与PointNet 网络保持一致，设置为2 048。

当采样后的点云数量大于T0时，计算当前点云数量与T0之间的差值，并且计算当前点云（xs，ys，zs）与其他点云之间的距离，计算距离时采用的距离为欧氏距离D1，对此可表示为：

假设点云中的点为圆心，R为半径划分区域，按照点云区域内点云数量的大小进行排序，将包含最大数量的点云区域与差值进行比较，若不小于差值，则从点云中删除差值大小的点云，保留其他的点云；若小于差值则不对当前点云进行操作，然后重复以上操作，直到点云数量等于阈值T0。

通过此方法可以有效地减少原始点云数据中的冗余点云，实验室效果如图3 所示。图3（a）是原始的点云，点云数为19 686；图3（b）是经过处理后的点云图，点云数为2 048。由图3 可知，此方法可以有效剔除点云集中区域内的冗余点云，且保持点云原有的三维形态。

图3 点云筛选对比图Fig.3 Point cloud screening comparison chart

1.2.1.2 部分点云区域稀疏

稀疏性是点云自身无法避免的缺陷，如图4 所示。由于数据集中所包含的点云数量过少，即便可以保持三维点云的外观形态，但是过于稀少的点云不利于后续的点云分类操作。

图4 稀疏点云示意图Fig.4 Schematic diagram of sparse point cloud

为了后续点云分类的正确性，需要对稀疏点云进行插值重建，既保持原始三维点云的外观形态，又确保有足够的点云数据用于点云分类操作，本文使用的插值重建方法是三角形内部插值法，三角形内部线性插值示意如图5 所示。

图5 三角形内部线性插值示意图Fig.5 Schematic diagram of internal linear interpolation in the triangle

假设三角形的3 个定点分别为P1，P2，P3，在三角形内部插入点P，并且存在3 个自由度，即u＝使得：

其中，u+v+w＝1。

稀疏点云重建实验的结果如图6 所示，对稀疏的点云进行空间插值重建，使点云尽可能地在点云空间中均匀分布。图6 的实验结果表明，该方法可以有效地克服点云稀疏导致三维点云外轮廓模糊的缺点，促使点云在点云空间中实现均匀分布，有利于后续点云分类计算。

图6 稀疏点云插值后的结果示意图Fig.6 Schematic diagram of results after sparse point cloud interpolation

1.2.2 基于SOM-K-Means 聚类的三维点云分类

本文在对原始点云进行预处理后，将处理后的点云数据进行SOM-K-Means 聚类运算，目的是通过聚类算法将点云先做粗分类，同时将点云数据自身的局部特征加以有效合理的利用，同时也避免了PointNet++网络将点云特征进行分层提取所带来的增加时间复杂度的问题。本文提出的点云分类网络，如图7 所示。

图7 基于SOM-K-Means 聚类的三维点云分类Fig.7 Classification of 3D point cloud based on SOM-K-Means clustering

图7中，网络输入为原始点云经过预处理后的2 048个点，在这2 048个点上使用本文设计的SOMK-Means 聚类算法，目的是将这些点划分为K个不同的类别，且这K个类中每个类别都包含着不等的点云个数，但是这些类别中的点云个数的差距并不大，因为过大的点云数量差距会对后续的计算结果产生较大的影响。然后将这K个类的点云数据并行输入到PointNet 网络中进行每个类的特征提取。最后利用最大池化层将由这K个类中提取到的点云特征进行融合生成全局特征，并将生成的包含局部特征的全局特征输入到感知机中进行分类学习，输出运行的分类结果、即分类类别数s。

1.2.2.1 K-Means 算法

在数据分析领域中，K-Means 聚类算法是一种常见的算法，该算法可以将数据进行快速有效的粗分类。K-Means 算法的本质就是在所有数据点中随机选择k个点作为初始的簇中心点，再对其余样本点到这些簇中心点的距离进行计算，将距离同一个簇中心点较近的点都分配到一个簇中，每分配一个样本点，簇中心点都会根据簇中现有的所有点再做一次重新计算。向簇中分配样本点会一直持续到没有剩余的样本点可供分配，此时簇中心点的位置将不会再发生变化。

该算法的优点是算法简单、收敛速度快。缺点是对初始的聚类中心比较敏感，对于预估合适的k值是非常困难的。

1.2.2.2 SOM 算法

自组织映射（SOM）算法是一种高维可视化的无监督学习的聚类算法。SOM 神经网络是由输入层和竞争层组成，需要最终聚集的不同类在竞争层中表现为一个个的节点。竞争学习是SOM 网络采用的训练网络的方式，每个输入的样例在竞争层都会与本身相似度最高的节点进行匹配，并将这个匹配度最高的节点称为该输入样例的激活节点。接下来会更新激活节点的参数，并且和激活节点相邻近的点也会根据其与激活节点的欧氏距离来对参数进行适当更新。

该算法的优点是，不需要提前预设分类数便可以进行自动聚类，并且容错性高，对异常值和噪声不敏感。缺点是，在训练神经元时会出现个别神经元始终不能胜出、成为节点的情况，导致分类结果的准确性降低，并且SOM 神经网络收敛效率较低。

1.2.2.3 SOM-K-Means 模型算法

结合SOM 算法和K-Means 算法的优缺点，研究者提出了将二者结合的构想并加以实现。由于SOM 算法并不需要提前预设分类数，但是在网络收敛时表现不理想；而K-Means 算法收敛速度快，但是初始聚类中心和k值很难提前预估。因此本文采用SOM-K-Means 算法、就是SOM 的优化算法，既解决了SOM 神经网络收敛效率低、分类结果不准确的问题，又克服了K-Means 聚类中心和k值的预设问题。SOM-K-Means 算法步骤具体如下。

输入点云数据

输出聚类结果

步骤1将点云数据输入到SOM 神经网络中进行聚类，输出分类数目以及初步分类结果。

步骤2将步骤1 中得到的初期分类结果作为k值，在预处理过后的点云数据中随机选择k个点作为初始的簇中心点，再利用K-Means 算法进行聚类。

SOM-K-Means 聚类算法的结果经过可视化操作后如图8 所示。

图8 聚类可视化结果及其对应SSE 曲线Fig.8 Clustering visualization results and the corresponding SSE curves

1.2.2.4k值的验证

手肘法是用来判断K-Means 算法是否合理的方法之一，计算簇中所有的点到该簇中心点的距离和、即SSE值，可以画出k -SSE曲线，在折线图中找到所画曲线的拐点。一般来说，曲线拐点就是K-Means算法的最佳k值，SSE结果示意见图8。此处需用到的数学公式为：

图8（a）～（d）中，k -SSE曲线的横轴为目标聚类数，纵轴为各簇内点到簇中心的距离和。点云数据的分类准确度与聚类数是强相关的，也就是说结果类别越多，点云数据的分类准确度就越高。当预测的k值小于实际的最佳分类数时，SSE的曲线形状相对陡峭；当预测的k值大于实际的最佳分类数时，SSE的曲线形状相对平缓，而在陡峭与平缓之间的拐点对应的k值就是该样本数据最佳的分类数。以Car 模型验证k值举例说明，本例中手肘肘部对应的k值为6。对本例数据单独采用K-Means算法进行聚类，并画出k -SSE曲线，由图8（c）可以清晰地看到，当k＝6时，该点为曲线的拐点，即经过SOM 神经网络得出的分类数是有实际意义的。

2 实验及结果分析

为了对本文算法的分类效果做出评估，选用和马京晖团队［22］相同的数据集进行实验，用于训练与测试的数据集来自于公开的数据集ModelNet10 和ModelNet40。

2.1 实验条件

实验设备及软件环境见表1。

表1 实验配置Tab.1 Experimental configuration

2.2 实验结果对比分析

本文将运用相同的数据集，并在相同的条件下开展实验，对不同算法的分类准确率和算法的运行时间进行记录，再进行对比分析。

2.2.1 准确率比较

本文将模型在相同数据集上的分类准确率与之前的研究者使用的方法进行对比，结果见表2。从表2 记录的实验数据中可以看出，本文算法通过原始点数据的预处理，减少了作为输入的点云数量，减少了算法的运算复杂度，有效降低了计算量。K-Means-PointNet方法是将k设定为统一的固定值进行聚类，再进行特征提取，试验结果表明本文算法在ModelNet10／40 数据集上对于三维点云分类任务能有效地提高分类准确度，说明对于原始点云的预处理和预处理后的点云数据率先进行聚类，将有助于提升点云分类任务的精度。本文的方法是不固定每个点云数据的分类数，并由SOM 神经网络分析得出适合输入点云的分类数后再进行K-means 聚类精化，将聚类后的点云数据并行通过PointNet 网络，对每个簇中的点云实现提取特征，相比于其他算法，本文提出算法的准确度要更高。将本文算法与K-Means-PointNet算法进行对比可以看出，本文提出由SOM 神经网络计算出合适的分类数比预先设定k值对分类精度的细化，能够取得更好的结果。

表2 分类准确率Tab.2 Classification accuracy

2.2.2 算法用时比较

本文在数据集ModelNet40 上通过对比5 种算法训练网络分别需要的时间，来预估每种算法的计算时间成本，结果见表3。

表3 训练时间Tab.3 Training time

通过表3 中的数据可以得出，本文算法在K-Means-PointNet的基础上进行改进，但是将点云数据并行通过PointNet 网络并不影响训练时间，因此本文中提及的网络的训练时间与PointNet 接近。避免了PointNet++和Kd-Net 算法多次分层导致计算量庞大、且模型训练时间过长的问题。同时，还避免了K-Means-PointNet对k值和初始中心的敏感带来的计算量庞大、训练时间增加的问题，证明本文的改进算法能有效地减少计算量。

3 结束语

本文提出的算法是在K-Means-PointNet 网络的基础上实现了改进，对原始点云数据进行关键的预处理，而后为了充分利用点云的局部特侦，采用SOM-K-Means 算法将点云进行分类处理，相比于分层提取点云，多个类别的点云并行提取点云特征也不会显著增加其运算时间，所以本文算法在保证运算时间的前提下，有效提高了算法在ModelNet10／40 数据集上分类任务的准确度，仿真实验运行后得到的准确度分别为94.8%和93.1%。研究可知，在同等条件下，本文算法的准确度要高于其他算法模型，与原有的K-Means-PointNet 网络相比也有着一定的优化和提升。