基于改进B?SHOT特征描述符的三维场景重建

汤泉 左韬 陶强

关键词： 三维场景重建; 点云; 特征提取; 特征匹配; 特征描述符; 位姿估计

中图分类号： TN919?34; TP391.41              文献标识码： A                    文章编号： 1004?373X（2019）02?0124?05

3D scene reconstruction based on improved B?SHOT feature descriptor

TANG Quan1， ZUO Tao1，2， TAO Qiang1

（1. School of Information Science and Engineering， Wuhan University of Science and Technology， Wuhan 430081， China;

2. Engineering Research Center for Metallurgical Automation and Measurement Technology of Ministry of Education， Wuhan University of

Science and Technology， Wuhan 430081， China）

Abstract： In allusion to the problem of low matching accuracy caused by information loss when the binary signatures of histograms of orientations （B?SHOT） is used in the 3D scene reconstruction to conduct point cloud feature extraction and matching， an improved binary three?dimensional feature descriptor DB?SHOT is adopted in this paper to conduct feature extraction and matching， so as to establish the corresponding relationships between adjacent point clouds. The random sampling consensus （RANSAC） algorithm is combined to remove the outliers of the point cloud. The interior points of the RANSAC are used to estimate the adjacent pose， so as to integrate the adjacent point clouds. The information loss problem of the B?SHOT is solved and the matching accuracy is improved in this paper on the premise of ensuring the matching speed. An experiment was carried out using the standard data set. The results verified the feasibility and effectiveness of taking DB?SHOT as the 3D scene reconstruction feature descriptor.

Keywords： 3D scene reconstruction; point cloud; feature extraction; feature matching; feature descriptor; pose estimation

0  引  言

随着微软Kinect、华硕Xtion Pro Live等廉价RGB?D传感器的出现，为三维场景重建的研究者们提供了新的思路，许多研究者已开始致力于研究基于深度视觉的三维重建[1]。与传统的通过二维图像，利用先验知识从物体的二维信息中推断出三维模型的建模技术相比，深度视觉的三维重建在重建效率、精度和实时性方面都有较大提高[2?3]。

特征匹配作为三维场景重建中的一个关键步骤，是衔接特征点检测和图像变换之间的关键步骤，而特征点描述则可以看作是匹配的预处理步骤，特征描述符的选取决定着能否快速准确地进行三维场景重建 [4]。目前特征描述符的表述方式有两种：浮点型描述和二进制描述[5]。其中浮点型描述符对尺度、旋转、光照、图像模糊等图像变换具有较好的鲁棒性和可区分性，在大多数情况下具有较高的匹配率[6]。但是由于其特征向量是高维的浮点数，并且用欧氏距离作为特征点之间的度量准则，这将导致巨大的存储开销和计算量，限制了其应用范围[7]。然而二进制描述符可以有效地解决上述问题。二进制描述符获取方法可分为两种：通过机器学习训练出二进制描述符的方法以及直接将浮点型描述符进行二进制化处理的方法。但是通过机器学习训练的二进制描述符需要进行大量的学习和计算，算法复杂。2015年Prakhya 等学者第一次将直接二值化思想应用于3D点云特征描述符SHOT描述符[8]（Signatures of Histograms of Orien Tations）的简化中去，提出了B?SHOT[9]。2016年，该作者在原有算法上做了一些扩展实验，把二值化的思想应用到另外两种最新的描述符RoPS[10]（Rotational Projection Statistic）和FPFH（Fast Point Feature Histograms）中，建立B?RoPS和B?FPFH描述符，并通过三维重建实验对B?SHOT，B?RoPS和B?FPFH进行比较，实验结果表明B?SHOT的综合性能是最好的[11]。但是B?SHOT却存在一定程度信息丢失的问题，将导致出现错误的匹配，使得三维场景重建失败。

本文将针对以上问题，在B?SHOT二值化算法的前提下，增加了B?SHOT二值化算法的规则，并将其命名为DB?SHOT，保证了匹配速度，使得其匹配准确率也得到了提升，并将其应用于三维场景重建中，最后通过实验验证了其可行性与有效性。

1  三维场景重建

本文采用三维场景重建的步骤为：

1） 利用Kinect获取三维点云数据;

2） 进行点云预处理，使用体素网格滤波器来检测特征点，滤波作为点云处理流程的第一步，对后续处理管道影响很大，能在不影响精度的情况下，简化点云数量，提高匹配效率;

3） 本文采用DB?SHOT三维特征描述符对所检测到的特征进行3D特征描述来进行特征匹配;

4） 采用RANSAC算法剔除错误点对，找到最终对应关系，并估计出其3D转换矩阵[T];

5） 通过求得的变换矩阵进行点云融合。三维场景重建流程图如图1所示。

2  特征描述

三维场景重建的关键在于对三维点云特征的描述。三维点云特征描述方法也称描述符或者描述子。一个唯一确定的，对噪声、遮挡和复杂场景鲁棒的特征描述符不仅有助于提升特征匹配的效率，还对识别算法的准确性有着重要影响。本文所提出DB?SHOT特征描述方法是对B?SHOT描述方法的一种改进，B?SHOT是对SHOT描述符的二值化，本节将对B?SHOT以及DB?SHOT这两种描述方法做详细介绍。

2.1  B?SHOT特征描述符

B?SHOT特征描述符是将SHOT[8]描述符转化为二进制得来的。其特征点提取过程主要包括特征点检测、生成SHOT特征描述符、将SHOT描述符转化为二进制的B?SHOT特征描述符。SHOT描述符是一个352维的向量，需要占用1 408 B的内存空间，而将其转化为二进制后，则只需要占用352 b的内存空间，降低到[132]，大大提高后续处理的计算速度。将SHOT特征描述符转化为B?SHOT特征描述符的具体步骤如下：

步骤1：将352维的浮点型SHOT描述符[S0，S1，…，S351]每4个分为一组，分为[A1=S0，S1，S2，S3] ，[A2=S4，S5，S6，S7]，[…]，[A88=S348，S349，S350，S351]。

步骤2：分别对每一组计算它们的和。例如，第一组数据[A1]，计算其和为：

[Ssum=S0+S1+S2+S3]      （1）

步骤3：按照一定的编码规则将每一组浮点型数据编码为一组8位的二进制数据。取第一组数据[A1=S0，S1，S2，S3]为例，用[Bi]表示[Si]二值化后的值，定义如下规则：

1） 若满足：

[? Si=0]            （2）

式中，[i∈0，1，2，3]，则[B0=B1=B2=B3=0]。

2） 若式（2）不满足，且：

[?Si>Ssum×90%]         （3）

式中，[i∈0，1，2，3]，则[Bi=1]，其余为0。

3） 若式（2）及式（3）都不满足，且：

[Si+Sj>Ssum×90%]          （4）

式中，[i，j∈0，1，2，3]，则[Bi=Bj=1]，其余为0。

4） 若式（2）～式（4）都不满足，且：

[Si+Sj+Sk>Ssum×90%]        （5）

式中，[i，j，k∈0，1，2，3]，则[Bi=Bj=Bk=1]，剩下的一个为0。

5） 若式（2）～式（5）都不满足，则[B0=B1=B2=B3=1]。

步骤4：将每一组二值化数据组合成一个352维的二进制特征描述符B?SHOT[{B0，B1，…，B351}]。

对剩下的每组都采用上述规则进行转换，即可将SHOT描述符转化为一串二进制的B?SHOT描述符。

2.2  DB?SHOT特征描述符

在将SHOT特征描述符转化为B?SHOT特征描述符时，有可能存在较严重的信息丢失。如：假设有这么一组分组[S0，S1，S2，S3=0.82，0.16，0，0]，由B?SHOT的规则可知，[S0]和[S1]的和超过[S0，S1，S2，S3]总和[Ssum]的90%，所以将[S0]和[S1]编码为1，其余编码为0。对其进行二值化得到：[B0，B1，B2，B3=1，1，0，0]。由此可见，二值化后[B0]和[B1]的值都为1，而实际上原来他们的值相差甚大，即可能存在严重信息丢失的问题。

本文提出一种改进的二进制特征描述符编码方法，在B?SHOT编码规则的基础上增加了一定的规则，解决上述二值化方法存在严重信息丢失的问题，提高二进制描述符的性能。本文提出的二进制描述符编码在B?SHOT编码的基础上增加了4位标志位编码，如将其中一组浮点型数据[S0，S1，S2，S3]编码为[B0，B1，B2，B3，Bl0，Bl1，Bl2，Bl3]， [{B0，B1，B2，B3}]为对应编码位， [{Bl0，Bl1，Bl2，Bl3}]为标志位，长度为原来的两倍，故命名为DB?SHOT。其编码步骤与B?SHOT一致，具体编码规则如下：

1） 满足式（2），则[B0=B1=B2=B3=0]，标志位[Bl0=Bl1=Bl2=Bl3=0];

2） 若式（2）不满足但满足式（3），则将该[Si]对应的[Bi]置1，其余置0;标志位的[Bli]置1，其余置0;

3） 若式（2）及式（3）都不满足但满足式（4），则[Bi=Bj=1]，其余置0，其标志位编码遵循如下规则：

① 若[Si≥2Sj]，则[Bli]置1，其余置0;

② 若[Sj≥2Si]，则[Blj]置1，其余置0;

③ 若以上都不成立，则[Bli=Blj=1]，其余置0;

4） 若式（2）～式（4）都不滿足，但满足式（5），则[Bi=Bj=Bk=1]，其余置0。其标志位编码遵循以下规则：

① 若[Si≥2（Sj+Sk）]，则[Bli]置1，其余置0;

② 若[Sj≥2（Si+Sk）]，则[Blj]置1，其余置0;

③ 若[Sk≥2（Si+Sj）]，则[Blk]置1，其余置0;

④ 若[2Si≤Sj]且[2Si≤Sk]，则[Blj=Blk=1]，其余置0;

⑤ 若[2Sj≤Si]且[2Sj≤Sk]，则[Bli=Blk=1]，其余置0;

⑥ 若[2Sk≤Si]且[2Sk≤Sj]，则[Bli=Blj=1]，其余置0;

⑦ 若以上都不成立，则[Bli=Blj=Blk=1]，其余置0。

5） 若以上规则都不成立，则[B0=B1=B2=B3=1]，标志位编码为[Bl0=Bl1=Bl2=Bl3=1]。

通过上述编码规则，便可以有效解决B?SHOT描述符出现信息丢失的问题。如有两组分组[S0，S1，S2，S3=0.82，0.16，0，0]与[S0，S1，S2，S3=0.52，0.47，0，0]，使用B?SHOT编码则都会将其编码为[1，1，0，0]，而使用DB?SHOT则会将前一个编码为[1，1，0，0，1，0，0，0]，而后一个编码为[1，1，0，0，1，1，0，0]，增加了其可区分度，降低了其匹配错误的概率。

3  转换矩阵估计

3.1  转换矩阵的线性估计

假设有2幅点云分别为[I1（x1，y1，z1）]与[I2（x2，y2，z2）]，其对应的投影变换关系为：

[x1y1z11=R3×3 t3×1O1×3 1x2y2z21或I1=TI2]  （6）

式中：[R3×3=R0 R1 R2R3 R4 R5R6 R7 R8]为旋转矩阵;[t3×1=t0t1t2]为平移矩阵;[T=R0 R1 R2 t0R3 R4 R5 t1R6 R7 R8 t20   0   0   1]，有12个自由度，则至少需要6组匹配点才能估计出[T]。

3.2  RANSAC估计转换矩阵

RANSAC充分利用了所有的初步匹配点，根据一个容许误差将所有的匹配对分为内点和外点，利用内点数据比较准确的特点来进行参数估计，从而剔除了不准确的匹配点。

用RANSAC估算转换矩阵[T]的具体步骤如下：

1） 将当前最佳估计内点数目[n0]设置为0。

2） 重复N次随机采样。本文的矩阵[T]估计需要的匹配点为6对，确定一个恰当的采样次数N，以保证此时采样的6对匹配点都是内点的概率足够高。设[p]表示此概率，本文取[p=95]%。设[p1]为任何一对匹配点是内点的概率，则[1-p1]是任一对匹配点为外点的概率，那么采样到N次时应满足：[（1-p31）N=1-p]，则[N=log（1-p）log（1-p31）];

3） 根据6对匹配点计算出转换矩阵[T];

4） 计算每个匹配点经过矩阵[T]变换后到对应匹配点的欧氏距离或汉明距离;

5） 设定一距离阈值[ε]，把满足欧氏距离或汉明距离小于[ε]的匹配点作为内点;

6） 比较当前内点数目[n]与[n0]，若[n>n0]，则将[T]和当前的内点集作为当前最佳估计，更新[n0];若[n=n0]，则选择配准较低的作为当前最佳估计。同时动态估测剩余所需迭代次N，如果当前迭代次数达到N，则保留[T]和当前的内点集并停止迭代。

4  实验结果与分析

本文实验包括三方面：第一，测试本文所提出的二值描述符与 SHOT以及B?SHOT 分别在特征点数目为 200，1 500，3 000，4 500时，特征的计算和匹配时间;第二，测试本文所提出的二值描述符DB?SHOT和 SHOT以及B?SHOT 在标准数据库上的匹配准确率;第三，测试本文所提出的二值描述符在三维场景重建中的应用。上述实验均在 Intel[?] CoreTM i5?3230M，CPU 2.60 GHz，8.00 GB内存的PC上采用C++语言实现，所有测试均为单线程执行完成。

场景重建测试采用的标准数据库是http：//vision.deis.unibo.it/research/80?shot中用来测试三维场景重建的Kinect Views数据集。该数据集是通过微软Kinect传感器获取的，它是由2个物体（Duck和Flog）的几个视图组成的，其中Duck数据集由16组视图组成，本文实验将采用Duck来进行场景重建测试描述子性能。

4.1  匹配速度测试

为了测试本文所提出描述方法与 SHOT，B?SHOT在特征匹配速度方面的性能。对Duck数据集中点云视图进行两两匹配，分别提取两个点云视图上特征点的特征，然后执行特征匹配。当特征点数n分别为200，1 500，3 000，4 500时的特征匹配平均时间如表1所示。

由表1可知，各种特征描述方法的特征匹配时间均随特征点的增多而增大。在匹配速度方面，虽然本文所提出的方法相比于B?SHOT描述方法匹配速度有所降低，但是相比于SHOT描述方法来说匹配速度却大大提高，匹配时间大约为SHOT匹配时间的[18]。

4.2  匹配准确率测试

为了测试本文所提出方法与SHOT，B?SHOT在匹配准确率方面的性能，分别测试了SHOT，B?SHOT和DB?SHOT对Duck数据集中2个视图（见图2）的匹配效果。当特征点数n分别为200，1 500，3 000，4 500时，经过RANSAC算法去除错误匹配后匹配结果如图3所示。其匹配准确率如图4所示。其中：

图3a）～图3d）分别为特征点数为200，1 500，3 000，4 500时的匹配效果图。其中左边为SHOT匹配效果;中间为B?SHOT匹配效果;右边为DB?SHOT匹配效果。由图3以及图4可以看出，随着特征点数的增多，SHOT，B?SHOT與DB?SHOT的匹配准确率都会提升，但是DB?SHOT的匹配准确率相比于B?SHOT却大大提升了，这是由于B?SHOT描述符存在信息丢失的问题，出现了一些错误的匹配，使得RANSAC算法计算出现错误，而DB?SHOT则较好地解决了这些问题。

4.3 三维场景重建测试

转换矩阵[T]能否准确地计算出来关系着三维场景能否准确地进行重建。为了测试本文所提出方法能否准确的进行三维场景的重建，对Duck数据集中每幅点云使用B?SHOT，DB?SHOT求得的转换矩阵[T]分别与使用SHOT求得的转换矩阵[TSHOT]进行比较，求得两者之差的二范数[norm]，即：

[norm=TSHOT-T2]

由于二范数[norm]可以很好地表示2个矩阵之间的空间直线距离，则二范数值越小，表明其空间直线距离越小，那么其求得的转换矩阵[T]与SHOT描述符求得的转换矩阵[T]就越接近。其[norm]比较结果如表2所示。

由表2可以看出，随着特征点数的增多，B?SHOT与DB?SHOT求得的转换矩阵[T]就会越接近通过SHOT描述符求得的转换矩阵[T]，但是DB?SHOT求得的转换矩阵[T]相比于B?SHOT求得的转换矩阵[T]更接近于使用SHOT描述符求得的结果。在特征点为3 000个时，分别利用DB?SHOT与B?SHOT进行特征描述，再对Duck数据集中的相邻三维点云进行特征匹配，利用RANSAC算法去除错误的匹配，进行相邻位姿估计出转换矩阵[T]，最后进行点云融合，得到的场景重建点云图像如图5所示。图5a）为利用本文所提出特征描述方法DB?SHOT进行特征描述重构的点云图;图5b）为利用B?SHOT进行特征描述重构的点云图。图中左侧为左视图;中间为主视图;右侧为俯视图。由图5可以看出，利用B?SHOT进行特征描述时重构的点云存在较多的冗余点，而利用本文所提出方法DB?SHOT进行特征描述时冗余点较少。这是因为B?SHOT存在着信息丢失的问题，进行相邻两帧位姿估计时，出现较大误差，然后误差会进行累积，使得重构场景失败。而利用本文所提出方法进行特征描述后，能够准确地进行特征匹配，求得准确的转换矩阵，从而能够准确地重构场景。说明本文所提出方法能够很好地应用于三维场景重建中。

5  结  语

本文采用DB?SHOT，解决了B?SHOT在三维场景重建中进行点云特征提取与匹配时存在信息丢失的问题。虽然本文提出的方法相比于B?SHOT在匹配时间略有降低，但是匹配准确率却得到了较大的提升。实验验证了该方法的可行性与有效性。为了进一步提高该方法的实用性，未来将对特征提取算法做出一定的改进，使得其匹配时间得到改善，并将其应用于SLAM中。

参考文献

[1] ZOU R， GE X， WANG G. Applications of RGB?D data for 3D reconstruction in the indoor environment [C]// Proceedings of Chinese Guidance， Navigation and Control Conference. Nanjing： IEEE， 2017： 375?378.

[2] 艾达，王苗，倪国斌.基于FPFH特征的三维场景重建[J].计算机测量与控制，2016，24（7）：232?236.

AI Da， WANG Miao， NI Guobin. Research and realization of 3D reconstruction based on FPFH [J]. Computer measurement & control， 2016， 24（7）： 232?236.

[3] 孙新领，谭志伟，杨观赐.双目立体视觉在人形机器人三维重建中的应用[J].现代电子技术，2016，39（8）：80?84.

SUN Xinling， TAN Zhiwei， YANG Guanci. Application of binocular stereo vision in 3D reconstruction of humanoid robot [J]. Modern electronics technique， 2016， 39（8）： 80?84.

[4] 余妹兰，叶群，鲍方云.拼接优化SIFT算法的虚拟场景绘制模型[J].科技通报，2017，33（7）：133?136.

YU Meilan， YE Qun， BAO Fangyun. Based on the stitching optimal SIFT algorithm model of the virtual scene rendering [J]. Bulletin of science and technology， 2017， 33（7）： 133?136.

[5] 张洋，吕强，林辉灿，等.一种基于改进ORB的视觉SLAM图像匹配算法[J].装甲兵工程学院学报，2016，30（6）：82?88.

ZHANG Yang， L? Qiang， LIN Huican， et al. An improved image matching algorithm based on ORB for visual SLAM [J]. Journal of Academy of Armored Force Engineering， 2016， 30（6）： 82?88.

[6] 白丰，张明路，张小俊，等.局部二进制特征描述算法综述[J].电子测量与仪器学报，2016，30（2）：165?178.

BAI Feng， ZHANG Minglu， ZHANG Xiaojun， et al. Summarization of local binary feature description algorithm [J]. Journal of electronic measurement and instrumentation， 2016， 30（2）： 165?178.

[7] 李倩，江泽涛.二值化的SIFT特征描述子及图像拼接优化[J].中国图象图形学报，2016，21（12）：1593?1601.

LI Qian， JIANG Zetao. Binary quantized SIFT feature descriptors for optimized image stitching [J]. Journal of image and graphics， 2016， 21（12）： 1593?1601.

[8] SALTI S， TOMBARI F， STEFANO L D. SHOT： unique signatures of histograms for surface and texture description [J]. Computer vision and image understanding， 2014， 125： 251?264.

[9] PRAKHYA S M， LIU B， LIN W. B?SHOT： A binary feature descriptor for fast and efficient keypoint matching on 3D point clouds [C]// Proceedings of IEEE/RSJ International Conference on Intelligent Robots and Systems. Hamburg： IEEE， 2015： 1929?1934.

[10] GUO Y， SOHEL F A， BENNAMOUN M， et al. RoPS： a local feature descriptor for 3D rigid objects based on rotational projection statistics [C]// Proceedings of 1st International Conference on Communications， Signal Processing， and Their Applications. Sharjah： IEEE， 2013： 1?6.

[11] PRAKHYA S M， LIU B， LIN W， et al. B?SHOT： a binary 3D feature descriptor for fast keypoint matching on 3D point clouds [J]. Autonomous robots， 2017， 41（7）： 1501?1520.