基于距离统计的有序纹理点云离群点检测

黄旺华 王钦若

摘要：三维数据的离群点检测是纹理点云数据处理的重要内容之一，为了有效快速地检测离群点，根据纹理点云的有序结构特征，提出了基于距离统计的检测算法。首先在每个点到其K邻域中其他点距离的基础上计算出K邻域距离;然后根据有序点云中该距离符合正态分布的特点和正态分布3u定理，将超出3倍方差范圍的点认定为离群点。实验结果显示算法采用曼哈顿一最大距离进行检测，当K为4时可以更加快速准确地将有序点云中的离群点检测出来。由此得出，基于距离统计的算法可以有效地将离群点检测出来，同时成功地应用于纹理点云的离群点检测。

关键词：离群点检测;距离统计;K邻域距离;正态分布3cr定理;有序点云

中图法分类：TP391.72

文献标识码：A

自然界中如木纹、皮革和石纹等纹理，具有细微、相似但不完全相同等特征，由于其美轮美奂的形状，经常应用于工业设计、艺术设计、服饰设计和模具设计等方面[1'2]。纹理的数字化是获取纹理数据的主要手段之一，可以通过视觉技术进行获取，数据形式主要有二维平面[3，4]和三维空间[5'6]。三维的纹理数据不但可以具有颜色信息，更主要有空间信息，可以提高纹理的设计和展示效果。

采用线激光扫描技术对纹理物体进行三维数据的扫描是常用的三维纹理数据获取手段之一，但由于受到各种因素影响，特别是皮革的光滑表面，经常出现一些不可预测的离群数据[7]。在对三维数据进行处理之前需要将这些离群点进行识别和处理，称为离群点检测。离群点检测是数据处理中的热点研究内容[8-12]，是数据挖掘技术[13，14]中主要的任务之一，主要用于从某一数据集中识别出与整体不相符的小部分异常数据，广泛应用于各种领域的安全监测，检测出异常的数据。

离群点检测技术大概可分为5种[15，16]，分别为基于统计、距离、密度、聚类和深度的离群检测。基于统计的检测是指数据符合某个分布模型，比如正态或泊松分布，将处于低分布概率的数据定义为离群点[17]。基于距离的检测主要判断点到数据集中大部分或K邻域的距离是否大于某个阀值这[18，19]。基于密度的检测是在计算点的局部密度和相对密度的基础上，判断该点是否是离群点[20]。Bhattacharyac21]提出类似于密度的相邻秩次偏差将数据空间划分为正常数据可异常数据。基于聚类是根据某条件将数据分成几类。Daneshpazhouh[22]提出基于模糊聚类的半监督离群点检测方法，该方法应用于存在正常数据并不标签的情况下，首先通过KNN算法识别出非正常的数据，然后使用模糊聚类将数据划分为正常数据和非正常数据。在深度离群点检测中，认定中心点为正常点，然后计算数据每个点到中心点的深度值，值越大说明是处在边缘的离群点[23]。

在对细纹理进行线激光扫描过程中，采用激光三角法获取深度信息，而两水平方向的取值是分别是均匀间隔取值，最终获取有序的点云数据。由于扫描对象皮革等光滑的表面，获取的点云数据中存在个别离群点。为了有效利用点云的有序特点，提高数据的处理速度，文中根据相邻点的距离符合正态分布的现象，采用距离和统计分布结合的离群点检测方法。

论文主要结构如下：第1节讨论了有序点的距离统计离群点检测的相关理论工作;第2节主要介绍了本文的离群点检测方法;第3节对文中的检测方法进行实验验证和分析;最后一节是讨论和结论。

1 相关理论

1.1 有序点云K邻域距离

定义1：有序点云P（M，N），表示M行Ⅳ列的网格点云数据集，其中点p（m，n）ED（M，Ⅳ），每个点包含三维空间坐标，p（m，n）：=[x，y，z]。

由正态分布的30-定理可知，数值分布在3倍方差范围内的概率为99.74%，超出该范围的数值可以被认定为是异常数据。

2 有序纹理点云的离群点检测算法

2.1 算法描述

一般情况下，纹理是附着在物体表面比较细微的痕迹，通过激光扫描所获取的点云数据主要集中在一定的平面内，但在扫描过程中，由于环境和扫描对象光滑表面的影响。如图1所示为某小部分有序纹理点云数据，存在离群点偏离了正常范围，如在图l（a）中尖峰位置对于的点，其中图l（b）是图l（a）的其中一条线激光提取的点云，在正常值上方和下方都存在离群点点，如图l（b）中圆圈标注，其他是正常取值点。

为了将有序点云的离群点快速的检测出来，文中充分利用点云的有序性和在扫描过程中的规则网格特点。有序点云P（M，N）中的离群点检测方法如下：

1、计算点p_i（m_i，n_i）的K邻域中K个点的欧氏距离或曼哈顿距离。

2、计算点p_i的K邻域距离，求取点p_i的K个距离的平均距离或最大距离。

3、计算点云所有点K邻域距离的均值和方差，当d（p_i，P，k）>μ+3σ或d（p_i，P，k）<μ- 3σ判定该点为离群点。

2.2 时间复杂度分析

本算法充分利用了线激光扫描获取的点云数据有序性和X-Y平面网格特点，在计算点的K领域距离时，根据点云体素在X-Y平面位置的相邻关系，直接获取点的K领域的所有点，避免了传统离群点检测算法中最差复杂度0（n2）的K邻近点搜索过程。算法主要分成三部分，首先计算每个点到邻域K个点的距离，在该部分的时间频度可以记为T（K*n）。第二部分是求取K邻域距离，不管是平均距离还是最大距离，时间频度记为T（n）。最后是对每个点进行判断，时间频度也记为T（n）。整个算法的时间频度为T（（K+2）*n），则其时间复杂度为O（n）。

3 实验结果及分析

为了验证该有序点云的距离统计离群点算法的检测有效性、精度和效率，采用实验室自主研发的高精密三维扫描设备对纹理皮革进行扫描，将获取的点云数据作为测试数据[24]。算法将在Windows7（64位）+MATLAB的软件环境中进行验证，硬件配置为Intel 13 2.4GHz的CPU和8G的内存。在实验中将本文的算法与LOF[20]和LDOF[19]进行离群点的检测效果比较和分析，同时对算法中的K值进行分析。

3.1 实验环境及数据

如图2（a）是本实验室专门用于扫描细纹理的高精密三维扫描设备，设备主要包括计算机、运动控制平台、工业相机和激光器等。当扫描物件大小超出相机的有效视场时，需要多次对其进行多次不同区域的扫描，如图2（b）是一次性扫描纹理皮革的Z轴数据生成的平面圖像。点云数据在X方向最大的宽度为1536体素，体素间X方向的距离为0.015毫米（如图1所示），而在Y方向由运动控制平台和工业相机，每0.015毫米间隔系统提取一条激光线的深度值作为Z方向的取值。在Z方向，根据激光三角法计算光条中心，为方便运行由系统设定正常纹理皮革的取值为3毫米左右，当由于皮革表面光滑及其他外界因素的影响，偏离正常光条线的点取值约为2.5毫米或3.5毫米。如果离群点主要是由表面光滑原因引起，一般情况下，该区域出现离群点团，如图l（a）右边区域，上边和下面均出现有离群点团。

在本实验中，虽如图l（b）中样本数据的有序点云的大小为3338x1536体素，但为了方便展示算法的效果，文中将只展示某一区域的检测效果进行测试、比较和分析。

3.2 实验结果及分析

一）与LOF和LDOF检测效果对比

如图3是采用本文算法对如图3（a）带有离群点的点云数据进行检测的效果对比图。图3（a）是图2（b）样本数据中的一小部分，大小为300x150，图中的下方存在个别的离群点和多个离群点形成的离群点团。图3（b）是本文算法的离群点检测效果，算法中采用欧氏距离计算点与点之间的距离，然后在K=8领域中求取平均值作为点的邻域距离，剔除339个点。计算结果与原始数据相比较可以发现，在点云数据下方已不存在离群点，但也在数据中出现空白区域。图3（c）和图3（d）分别是采用LOF和LDOF算法对原始点云进行离群点检测的效果，算法中的K邻近点取值均为8，剔除离群点数分别为22和19，在点云的下方还存在比较多离群点。

从图3（a）中可以发现，该部分点云数据中不但包含了零散的离群点，还包括由于光滑表面影响产生的离群点团。对于在点云中的离群点团，如果采用目前比较热门的局部离群点检测方法，如LOF和LDOF不能很好的将所有的离群点检测出来，如图3（c）和图3（d）的效果所示。采用本文的算法不仅能将零散的离群点检测出来，同时还能将离群点团也检测出来，效果如图3（b）。

二）不同类型K邻域距离的比较

在本算法中，点与点之间的距离可以通过欧氏距离或曼哈顿距离进行计算，同时任一点的K邻域距离可以通过计算该点到K邻域中K个点的平均距离或最大值距离算取。如表1是在某包含45000体素的点云中，当K=8时，采用不同距离组合算法检测出离群点的个数、比例和运行时间。

从表1可以发现，根据本算法思路采用不同距离算法检测结果虽相近，但也存在可循规律的不同。首先采用最大值计算K邻域距离比采用平均值检测出的离群点稍多，其主要是因为最大值计算K邻域距离将真正离群点邻域内的所有点都认定为离群点。比如欧氏距离时，采用最大值检测到358个离群点，而均值检测的离群点为339，对应离群点比例分别为0.8%和0.75%;曼哈顿距离计算点与点距离时，采用最大值检测到364个离群点，而均值检测到的离群点为348，对应离群点比例分别为0.81%和0.77%。其次采用马哈顿计算点与点之间的距离在时耗方面比采用欧氏距离比较少，主要原因是曼哈顿距离是一次方运算，而欧氏距离是二次方运算。同样采用均值法计算K邻域距离时，曼哈顿距离花费时间比欧氏距离少1.13秒，而最大值法的则少0.87秒。

三）K值的影响

该部分实验主要验证K值对文中算法的影响，如表2同样是在某包含45000体素的点云中，当采用曼哈顿一最大值的K邻域距离时，在不同K值的情况下的离群点检测结果。

首先从表2中可以清楚的发现随着K值的增加，不管检测到的离群点还是所耗费的时间都是随之增加的。其次根据正态分布的3u定理，当K邻域距离在3倍方差范围内的分布概率为99.74%，超出该范围的数值可以被认定为是离群，即有0.26%的点是离群点。表2中即使最小的K值对应的离群点比例都已超出了理论值，说明算法不但将离群点检测出，还将少部分非离群点也认定为离群点，但所占比例不高，特别当K值比较小时。

4 结论

针对有序纹理点云数据中离群点检测的问题，由于点云在X-Y平面坐标的有序和间隙相等的特征，提出根据点K邻域距离的正态分布概率情况，判断该点是否为离群点的算法。K邻域距离由该点到K邻域中每个点的欧氏距离或曼哈顿距离的平均值、加权值或最大值，根据正态分布的30-定理，如果K邻域距离处在3倍方差范围外，将被认定为是离群点。

由于皮革表面光滑等原因，实验室扫描设备获取的皮革纹理点云数据中存在离群点，使用该点云数据对文中提出的算法进行了三次实验进行验证。第一个实验中与传统检测算法LOF和LDOF进行检测效果比较，当K=8，传统算法的不能检测所有离群点的情况下，而文中算法能将所有离群点检测出来。传统算法效果不佳主要有两个原因，一是传统算法采用K最近邻算法，是空间中的最近点，而本算法的K邻域是X-Y平面坐标内的邻域，是有序点云的最近点。二是传统算法是基于空间密度的检测算法，当离群点团内的点数大于K值时，该离群点团将视为正常点云。本算法对离群点团的判断并不直接取决于K值，而是只要该点的K邻域内有一个是正常点，则可检测为离群点。

第二个实验是不同类型K邻域距离的比较，算法中需要计算点与点之间的距离和点到K邻域距离。当点与点之间的距离为曼哈顿距离时所检测到的离群点比欧氏距离多，其主要原因是当Z轴方向的值变化时对曼哈顿距离的影响比欧氏距离大。当使用最大值计算点到K邻域的K邻域距离检测出的离群点比使用平均值所检测的离群点多，因为只要点的K邻域中存在一个离群点，该点就会被检测为离群点。 K值是算法中唯一需要预先设定的参数，该参数跟K最近邻算法中的K值选择有所不同，K最近邻算法中的K值可以是任一自然数，而本算法中的K值为4、8、16或24。从最后一个实验的结果和分析可知，即便K值取最小值4时，所检测出离群点的比率已超出理论分布值。

通过上述对本算法的讨论，主要有如下特点：

1）本算法适用于有序点云数据中的离群点检测;

2）采用K邻域代替传统的K最近邻算法;

3）离群点判断的依据是所有点的K邻域距离大小符合正态分布。

在实验结果中发现算法亦有不尽人意的地方，比如两点之间的距离需要计算两次，特别是采用欧氏距离计算，将耗费大量的时间;其次就是某正常点的K邻域如果存在离群点，那么该点也可能被判定为离群点，出现过度检测的问题。接下来将就有关方面继续进行研究，将本算法进一步优化。

参考文献

[1]孙宁.线状动物纹理特征及其皮革面料设计应用[J]中国皮革，2016（03）：64-68.

[2] OJALA T， PIETIKAINEN M，MAENPAA T. Multiresolution gray-scale and rotation invariant texture classification with local binarypatterns[J]. Ieee Transactions on Pattern Analysis and MachineIntelligence， 2002， 24（7）：971-987.

[3]贺福强.大面积皮革表面的视觉检测技术与应用研究[D].杭州：浙江大学，2012.

[4] MANJUNATH B S，MA W-Y. Texture features for browsing andretrieval of image data[J].Ieee Transactions on Pattem Analysisand Machine Intelligence， 1996， 18（8）：837-842.

[5]张建鹏，新型皮革纹理扫描仪控制系统的设计与实现[D].成都：电子科技大学，2014.

[6]CULAOG，DANAK J.3D texture recognition using bidirectionalfeature histograms[J].International Joumal of Computer Vision，2004，59（1）：33-60.

[7]HAWKINS D M.Identification of outliers[M].Vol. 11， Springer，1980.

[8]FILZMOSER P.Identification of multivariate outliers：A perfor-mance study[J]. Austrian Journal of Statistics，2016，34 （2）：127-138.

[9]PIT-CLAIDEL C， MARIET Z， HARDINC R.Outlier detection inheterogeneous datasets using automatic tuple expansion [OL].Technical Report MIT -CSAIL -TR -2016 -002， CSAIL， MIT， 32Vassar Street， Cambridge MA 02139 February 2016.

[10] SHEVLYAKOV G，SMIRNOV P. Robust estimation of the corre-lation coefficient： An attempt of survey[J]. Austrian Journal ofStatistics， 2016， 40（ 1&2）： 147-156.

[11] AKOGLU L， TONG H， KOUTRA D.Graph based anomaly detec-tion and description：A survey [J]. Data Mining and KnowledgeDiscovery， 2015， 29（3）：626-688.

[12]CHANDOLA V，BANERJEE A，KUMAR V.Anomaly detection：A survey [J]. ACM Computing Surveys

（CSUR）， 2009， 41（3）： 15.

[13]薛安榮，鞠时光，何伟华，等，局部离群点挖掘算法研究[J]计算机学报，2007（08）：1455-1463.

[14]薛安荣，姚林，鞠时光，等.离群点挖掘方法综述[J]计算机科学，2008（11）： 13-18+27.

[15]刘靖，复杂数据类型的离群检测方法研究[D].广州：华南理工大学，2014.

[16] HA J， SEOK S， LEE J-S.A precise ranking method for outlier de-tection[J]_Information Sciences， 2015， 324： 88-107.

[17]HIDO S， TSUBOIY， KASHIMAH，et al.Statistical outlier detec-tion using direct density ratio estimation [J]. Knowledge and In-formation Systems， 2011， 26（2）：309-336.

[18] KNORREM，NCRT，TucakovV. Distance-based outliers： algo-rithms and applications[J].The VLDB Journal-The InternationalJournal on Very Large Data Bases， 2000，8（3-4）： 237-253.

[19] ZHANG K， HUTTER M， JIN H.A new local distance-based out-lier detection approach for scattered real-world data[C]. in Pacif-ic-Asia Conference on Knowledge Discovery and Data Mining，Springer.2009.

[20] BREUNIC M M，KRIEGEL H-P， NC R T，et al.Lof： Identifyingdensity-based local outliers[C].in ACM Sigmod Record ，ACM，2000.

[21] BHA'ITACHARYA G，GHOSH K，CHOWDHURY A S.Outlierdetection using neighborhood rank difference[J].Pattern Recog-nition Letters， 2015， 60： 24-31.

[22]DANESHPAZHOUH A， SAMI A.Semi-supervised outlier detec-tion with only positive and unlabeled data based on fuzzy cluster-ing [J]. International Joumal on Artificial Intelligence Tools，2015，24（03）：1550003.

[23] CHEN Y，DANG X，PENG H，et al.Outlier detection with thekemelized spatial depth function[J].Ieee Transactions on PatternAnalysis and Machine Intelligence， 2009， 31（2）：288-305.

[24]黄旺华，王钦若，徐维超，等，对椒盐噪声稳健的数字图像斯皮尔曼秩次相关法[J].光学精密工程，2015，23（6）：1800-1806.