湯泉 左韜 陶強

關鍵詞： 三維場景重建; 點云; 特征提取; 特征匹配; 特征描述符; 位姿估計

中圖分類號： 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傳感器的出現(xiàn)，為三維場景重建的研究者們提供了新的思路，許多研究者已開始致力于研究基于深度視覺的三維重建[1]。與傳統(tǒng)的通過二維圖像，利用先驗知識從物體的二維信息中推斷出三維模型的建模技術相比，深度視覺的三維重建在重建效率、精度和實時性方面都有較大提高[2?3]。

特征匹配作為三維場景重建中的一個關鍵步驟，是銜接特征點檢測和圖像變換之間的關鍵步驟，而特征點描述則可以看作是匹配的預處理步驟，特征描述符的選取決定著能否快速準確地進行三維場景重建 [4]。目前特征描述符的表述方式有兩種：浮點型描述和二進制描述[5]。其中浮點型描述符對尺度、旋轉、光照、圖像模糊等圖像變換具有較好的魯棒性和可區(qū)分性，在大多數情況下具有較高的匹配率[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卻存在一定程度信息丟失的問題，將導致出現(xiàn)錯誤的匹配，使得三維場景重建失敗。

本文將針對以上問題，在B?SHOT二值化算法的前提下，增加了B?SHOT二值化算法的規(guī)則，并將其命名為DB?SHOT，保證了匹配速度，使得其匹配準確率也得到了提升，并將其應用于三維場景重建中，最后通過實驗驗證了其可行性與有效性。

1 ?三維場景重建

本文采用三維場景重建的步驟為：

1） 利用Kinect獲取三維點云數據;

2） 進行點云預處理，使用體素網格濾波器來檢測特征點，濾波作為點云處理流程的第一步，對后續(xù)處理管道影響很大，能在不影響精度的情況下，簡化點云數量，提高匹配效率;

3） 本文采用DB?SHOT三維特征描述符對所檢測到的特征進行3D特征描述來進行特征匹配;

4） 采用RANSAC算法剔除錯誤點對，找到最終對應關系，并估計出其3D轉換矩陣[T];

5） 通過求得的變換矩陣進行點云融合。三維場景重建流程圖如圖1所示。

2 ?特征描述

三維場景重建的關鍵在于對三維點云特征的描述。三維點云特征描述方法也稱描述符或者描述子。一個唯一確定的，對噪聲、遮擋和復雜場景魯棒的特征描述符不僅有助于提升特征匹配的效率，還對識別算法的準確性有著重要影響。本文所提出DB?SHOT特征描述方法是對B?SHOT描述方法的一種改進，B?SHOT是對SHOT描述符的二值化，本節(jié)將對B?SHOT以及DB?SHOT這兩種描述方法做詳細介紹。

2.1 ?B?SHOT特征描述符

B?SHOT特征描述符是將SHOT[8]描述符轉化為二進制得來的。其特征點提取過程主要包括特征點檢測、生成SHOT特征描述符、將SHOT描述符轉化為二進制的B?SHOT特征描述符。SHOT描述符是一個352維的向量，需要占用1 408 B的內存空間，而將其轉化為二進制后，則只需要占用352 b的內存空間，降低到[132]，大大提高后續(xù)處理的計算速度。將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：按照一定的編碼規(guī)則將每一組浮點型數據編碼為一組8位的二進制數據。取第一組數據[A1=S0，S1，S2，S3]為例，用[Bi]表示[Si]二值化后的值，定義如下規(guī)則：

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}]。

對剩下的每組都采用上述規(guī)則進行轉換，即可將SHOT描述符轉化為一串二進制的B?SHOT描述符。

2.2 ?DB?SHOT特征描述符

在將SHOT特征描述符轉化為B?SHOT特征描述符時，有可能存在較嚴重的信息丟失。如：假設有這么一組分組[S0，S1，S2，S3=0.82，0.16，0，0]，由B?SHOT的規(guī)則可知，[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編碼規(guī)則的基礎上增加了一定的規(guī)則，解決上述二值化方法存在嚴重信息丟失的問題，提高二進制描述符的性能。本文提出的二進制描述符編碼在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一致，具體編碼規(guī)則如下：

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，其標志位編碼遵循如下規(guī)則：

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

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

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

4） 若式（2）～式（4）都不滿足，但滿足式（5），則[Bi=Bj=Bk=1]，其余置0。其標志位編碼遵循以下規(guī)則：

① 若[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） 若以上規(guī)則都不成立，則[B0=B1=B2=B3=1]，標志位編碼為[Bl0=Bl1=Bl2=Bl3=1]。

通過上述編碼規(guī)則，便可以有效解決B?SHOT描述符出現(xiàn)信息丟失的問題。如有兩組分組[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]，增加了其可區(qū)分度，降低了其匹配錯誤的概率。

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]，則選擇配準較低的作為當前最佳估計。同時動態(tài)估測剩余所需迭代次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++語言實現(xiàn)，所有測試均為單線程執(zhí)行完成。

場景重建測試采用的標準數據庫是http：//vision.deis.unibo.it/research/80?shot中用來測試三維場景重建的Kinect Views數據集。該數據集是通過微軟Kinect傳感器獲取的，它是由2個物體（Duck和Flog）的幾個視圖組成的，其中Duck數據集由16組視圖組成，本文實驗將采用Duck來進行場景重建測試描述子性能。

4.1 ?匹配速度測試

為了測試本文所提出描述方法與 SHOT，B?SHOT在特征匹配速度方面的性能。對Duck數據集中點云視圖進行兩兩匹配，分別提取兩個點云視圖上特征點的特征，然后執(zhí)行特征匹配。當特征點數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描述符存在信息丟失的問題，出現(xiàn)了一些錯誤的匹配，使得RANSAC算法計算出現(xiàn)錯誤，而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存在著信息丟失的問題，進行相鄰兩幀位姿估計時，出現(xiàn)較大誤差，然后誤差會進行累積，使得重構場景失敗。而利用本文所提出方法進行特征描述后，能夠準確地進行特征匹配，求得準確的轉換矩陣，從而能夠準確地重構場景。說明本文所提出方法能夠很好地應用于三維場景重建中。

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].現(xiàn)代電子技術，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] 余妹蘭，葉群，鮑方云.拼接優(yōu)化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特征描述子及圖像拼接優(yōu)化[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.