劉博文，童立靖

（北方工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100144）

基于多視角三維掃描數(shù)據(jù)的圖像配準(zhǔn)

劉博文，童立靖

（北方工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，北京 100144）

三維激光掃描是上世紀(jì)90年代發(fā)展起來(lái)的一門(mén)新興技術(shù)。考慮到測(cè)量設(shè)備測(cè)量范圍的限制和被測(cè)物體外形復(fù)雜性等，單次掃描無(wú)法獲得完整的、精確的模型。從而需要從不同的視點(diǎn)對(duì)被測(cè)物體進(jìn)行掃描。一些高精度的掃描儀除了可以獲得三維點(diǎn)云數(shù)據(jù)，還可以獲得一種散亂的紋理圖像。本文根據(jù)紋理映射的原理和逆向工程的思維，將掃描儀得到的點(diǎn)云數(shù)據(jù)和紋理數(shù)據(jù)通過(guò)一系列步驟提取出圖像信息，再利用仿射變換的原理計(jì)算出二維投影圖像的信息，然后準(zhǔn)確地提取出二維投影圖像。最后，采用基于SURF特征點(diǎn)提取算法，對(duì)提取出的兩幅二維投影圖像進(jìn)行了配準(zhǔn)。

三維掃描；圖像獲取；投影圖像；SURF；圖像配準(zhǔn)

0 引言

隨著計(jì)算機(jī)視覺(jué)技術(shù)的迅速發(fā)展，對(duì)三維圖像數(shù)據(jù)的處理與信息提取越來(lái)越成為計(jì)算機(jī)圖像處理的研究重點(diǎn)與重要的研究方向。原二維圖像中的視角問(wèn)題在三維模型中較易處理，只需要一定的預(yù)處理步驟即可解決。三維模型以空間網(wǎng)格為框架，通過(guò)紋理映射對(duì)網(wǎng)格表面信息進(jìn)行填充，可以獲取投影紋理圖像。

對(duì)于三維模型的二維圖像的配準(zhǔn)技術(shù)，有助于三維重建[1]、三維配準(zhǔn)等方面的進(jìn)一步研究。二維圖像的配準(zhǔn)方法有很多種。有基于灰度信息的配準(zhǔn)方法、基于變換域的配準(zhǔn)方法、基于特征的配準(zhǔn)方法。本課題的方法主要是采用基于特征點(diǎn)的配準(zhǔn)方法。為了解決特征點(diǎn)的自動(dòng)提取方法，許多研究者提出了不同的方法，常用的有Harris特征點(diǎn)[2]配準(zhǔn)算法、尺度不變特征轉(zhuǎn)換（Scale-Invariant Feature Transform，SIFT）特征點(diǎn)[3]配準(zhǔn)算法和加快魯棒特點(diǎn)（Speeded Up Robust Features，SURF）特征點(diǎn)[4]配準(zhǔn)算法。本文采用SURF算法進(jìn)行投影圖像的配準(zhǔn)。

在投影圖像的獲取時(shí)，本文方法是將圖像仿射變換的理論應(yīng)用到三維模型中，以三維空間網(wǎng)格中的每個(gè)三角面片為單位利用其點(diǎn)云與紋理數(shù)據(jù)生成二維投影圖像，此過(guò)程為紋理映射的逆過(guò)程。然后將獲得的投影圖像進(jìn)行圖像的配準(zhǔn)，本文采取的方法為SURF配準(zhǔn)法。SURF算法是SIFT算法的改進(jìn)，在許多方面的性能上都優(yōu)于SIFT算法。SURF由于具有實(shí)時(shí)性、系統(tǒng)匹配識(shí)別效果好、有較好的魯棒性的特點(diǎn)。

1 二維投影圖像獲取

1.1 算法描述

在進(jìn)行二維投影圖像的獲取前，首先采集三維模型，然后對(duì)三維模型數(shù)據(jù)進(jìn)行提取。提取二維投影圖像的整體流程圖如圖1所示。

圖1 提取投影圖像流程圖Fig.1 extract projection image flow chart

1.2 坐標(biāo)歸一化

三維模型中的每個(gè)點(diǎn)坐標(biāo)值為x、y、z表示，而二維圖像僅存在于x、y平面。將原三維模型中全部點(diǎn)的空間坐標(biāo)平移至第一象限，使模型中的空間坐標(biāo)都為正數(shù)，這樣可以保證去除后面計(jì)算中出現(xiàn)重復(fù)點(diǎn)的情況。

1.3 確定二維投影圖像大小

計(jì)算三維模型中點(diǎn)的坐標(biāo)值。獲取橫縱坐標(biāo)的最大最小值，選取一定的比例關(guān)系，按照以下公式。確定生成的二維投影圖像的大小。

其中，Xmax、Xmin、Ymax、Ymin為三維模型的空間坐標(biāo)平移至第一象限后，橫縱坐標(biāo)的最大最小值。PictureEnlarge為選取一定的擴(kuò)大比例系數(shù)。

1.4 面片頂點(diǎn)像素提取

計(jì)算每一個(gè)頂點(diǎn)在二維投影圖像中的位置。本文中使用的是美國(guó)Artec Spider手持式高精度三維掃描儀掃描得到的OBJ模型，其中的紋理模型為JEPG格式文件，將要存儲(chǔ)的二維投影圖像為BMP格式的文件。由以下公式計(jì)算頂點(diǎn)信息在二維投影圖像中的位置：

PointX、PointY為計(jì)算后頂點(diǎn)像素信息需要保存的位置，VertexU、VertexV為紋理圖片頂點(diǎn)信息的U、V值。JPEGLarge為紋理圖片的長(zhǎng)寬，由上述掃描儀掃描后的模型紋理圖片大小均為正方形。由于U、V值為雙精度浮點(diǎn)數(shù)值，而存儲(chǔ)的像素位置為整數(shù)值，因此在所有有關(guān)計(jì)算像素位置時(shí)，均采用四舍五入的方式。

1.5 三角形內(nèi)部像素判定

三角形面片內(nèi)部像素點(diǎn)填充之前，需要先判斷哪些像素點(diǎn)覆蓋在該三角面片上，哪些不在，不在的點(diǎn)則不需要填充。這就要做一個(gè)判斷，本文采用向量法。用向量法判斷二維投影圖像上的已知點(diǎn)N( x, y)是否在ΔABC上。設(shè)ΔABC三個(gè)點(diǎn)的坐標(biāo)分別為A( xa,ya)、B( xb,yb)、C( xc,yc)，求出向量然后利用向量的叉乘分別計(jì)算

最后對(duì)比叉乘結(jié)果：若三個(gè)叉乘結(jié)果均為同號(hào)，則說(shuō)明該點(diǎn)在三角形內(nèi)部，進(jìn)行像素的填充。若三個(gè)叉乘結(jié)果有異號(hào)，則說(shuō)明該點(diǎn)在三角形內(nèi)部，放棄填充。若三個(gè)叉乘結(jié)果有一個(gè)為零，則說(shuō)明在三角形邊上，則也進(jìn)行該點(diǎn)像素值的填充。

1.6 三角形內(nèi)部像素信息提取

三角形面片內(nèi)部像素信息的提取與保存。整張圖片的大部分像素信息的提取，將在這部分完成。由于三角形面片內(nèi)部的像素信息，在三維模型中并不可獲知。所以采用紋理圖片到生成的二維圖片的仿射變換，來(lái)作像素點(diǎn)的映射。

利用仿射變換求映射關(guān)系矩陣M，用齊次坐標(biāo)形式表示向量和點(diǎn)。以空間三角網(wǎng)格面片為單位，每個(gè)三角面片的三個(gè)頂點(diǎn)坐標(biāo)在二維圖像上的坐標(biāo)(xi′, yi′)已求，其對(duì)應(yīng)紋理坐標(biāo)(ui, vi)可知，利用三個(gè)頂點(diǎn)間的映射關(guān)系求出映射矩陣。根據(jù)映射關(guān)系對(duì)二維圖像內(nèi)的點(diǎn)進(jìn)行像素填充。以空間三角網(wǎng)格面片為單位，由仿射變換的一般特性可知，仿射變換可將平行線(xiàn)轉(zhuǎn)化為平行線(xiàn)、有限點(diǎn)映射到有限點(diǎn)。所以每個(gè)三角面片內(nèi)的像素點(diǎn)都遵從該三角形的映射規(guī)則。

由公式（6）可得如下映射矩陣：

1.7 缺省像素點(diǎn)插值

由于計(jì)算像素點(diǎn)的精度的丟失、三角形邊緣部分點(diǎn)的判斷的一定誤差和自適應(yīng)調(diào)整確定的二維圖片大小等原因。會(huì)導(dǎo)致最終存儲(chǔ)下來(lái)的圖片，會(huì)有部分點(diǎn)的像素沒(méi)有填充。主要成單點(diǎn)狀，長(zhǎng)條狀。因此，需要進(jìn)行缺省像素點(diǎn)的插值。由于需要插值的點(diǎn)較少，本文采用用四鄰域法，進(jìn)行像素點(diǎn)的插值。

2 二維投影圖像配準(zhǔn)

2.1 圖像配準(zhǔn)簡(jiǎn)述

到目前為止，在國(guó)內(nèi)外的圖像處理研究領(lǐng)域，已報(bào)道過(guò)相當(dāng)多圖像配準(zhǔn)研究理論，產(chǎn)生了不少圖像配準(zhǔn)方法。每一種方法都是面向一定范圍的應(yīng)用領(lǐng)域，也具有每種方法的特點(diǎn)，如文獻(xiàn)[5][6]中提到的圖像配準(zhǔn)算法。目前，圖像配準(zhǔn)方法中利用的圖像信息區(qū)別可將圖像配準(zhǔn)方法分為三個(gè)類(lèi)別：基于灰度信息法、變換域法和基于特征法[7]，其中基于特征法又可以根據(jù)所用的特征屬性的不同而細(xì)分為若干種。

對(duì)于本文中所提取的多視角二維投影圖像，比較適用的方法有基于點(diǎn)特征的SIFT算法和SURF算法。Dvad G.Lowe在2004年總結(jié)了現(xiàn)有的基于不變量技術(shù)的特征檢測(cè)方法，并正式提出一種基于尺度空間的、對(duì)圖像縮放、旋轉(zhuǎn)甚至仿射變換保持不變性的圖像局部特征描述算子--SIFT算子[2]，其全稱(chēng)是Scale invariant Feature Transform，即尺度不變特征變換。SIFT算法對(duì)圖像旋轉(zhuǎn)、尺度縮放、亮度變化保持不變性比較好。對(duì)視角變化、仿射變換、噪聲也保持了一定程度的穩(wěn)定性。同時(shí)獨(dú)特性較好，適用于在大量特征數(shù)據(jù)中進(jìn)行快速并且準(zhǔn)確的匹配。因此這類(lèi)基于點(diǎn)特征的圖像算法適用于本文中多視角三維模型中提取二維投影圖像的配準(zhǔn)。

SURF算法是SIFT算法的改進(jìn)，在許多方面的性能上都由于SIFT算法。SURF由于具有實(shí)時(shí)性、系統(tǒng)匹配識(shí)別效果好、具有較好的魯棒性的特點(diǎn)。因此本文使用基于SURF的算法對(duì)獲取的投影圖像進(jìn)行匹配處理。

2.2 SURF算法描述

SURF檢測(cè)算法的整體思想流程同SIFT類(lèi)似，但在整個(gè)過(guò)程中采用了與SIFT不同的方法。

1）特征檢測(cè)

特征^點(diǎn)的檢測(cè)主要基于尺度空間理論。在投影圖像中x=（x, y）處的點(diǎn)在尺度σ上的定義Hessian矩陣。Bay[8]等人提出用方框鋁箔近似替代二階高斯濾波，用積分圖像[37]來(lái)加速卷積以提高計(jì)算速度。在原始投影圖像上通過(guò)擴(kuò)大正方形的大小形成不同尺度的投影圖像金字塔的9×9正方形濾波模版值。

用類(lèi)似SIFT的方法構(gòu)成了金字塔圖像在每一階中選擇4層尺度的圖像，如果圖像尺寸大于模板大小很多，那么繼續(xù)增加階數(shù)。例如，濾波模板大小為N×N，則對(duì)應(yīng)的尺度s=1.2×N/9，然后用Hessian矩陣求出極值后，在3× 3× 3的立體鄰域內(nèi)進(jìn)行非極大值擬制，只有最近26個(gè)鄰域值都大或者都小的極值點(diǎn)，才能作為待選的特征點(diǎn)。最后，在尺度空間和圖像空間中進(jìn)行插值計(jì)算，來(lái)得到穩(wěn)定的特征點(diǎn)坐標(biāo)及所在的尺度值大小。

2）方向確定

為達(dá)到保證旋轉(zhuǎn)不變性的目的，首以特征點(diǎn)為中心，計(jì)算半徑為6 s（s為特征點(diǎn)所在的尺度值）區(qū)域內(nèi)的點(diǎn)在x，y方向的Haar小波響應(yīng)，并且給這些值賦高斯權(quán)重系數(shù)，使得靠近特征點(diǎn)的響應(yīng)貢獻(xiàn)大，遠(yuǎn)離特征點(diǎn)的響應(yīng)貢獻(xiàn)小，這樣符合客觀實(shí)際；然后對(duì)60度范圍內(nèi)的響應(yīng)作加法以形成新的矢量，遍歷整個(gè)圓形，選一個(gè)最長(zhǎng)矢量的方向作為此特征點(diǎn)的主方向，按照此方法，通過(guò)對(duì)每個(gè)特征點(diǎn)進(jìn)行計(jì)算從而得到每一個(gè)特征點(diǎn)的主方向。

3）描述子形成

描述子的形成首先以特征點(diǎn)為中心，將坐標(biāo)軸挪到主方向的位置，選則長(zhǎng)為20 s的正方形區(qū)域，將該區(qū)域劃分成4×4的小區(qū)域，在每個(gè)小區(qū)域內(nèi)計(jì)算5 s×5 s的小波響應(yīng)，對(duì)于主方向上的水平、垂直方向Haar小波響應(yīng)記做xxd d，賦予同樣響應(yīng)值，這樣可以增加幾何變換的魯棒性；然后將每個(gè)小區(qū)域的響應(yīng)和其絕對(duì)值相加形成這樣，在每個(gè)小區(qū)域形成四維分量矢量sumV=。對(duì)每一特征點(diǎn)則形成4× 4 464×=維的描述向量，最后再進(jìn)行向量的歸一化。

SURF為本文獲取的投影圖像配準(zhǔn)提供了自動(dòng)提取特征的方法。由于SURF特征點(diǎn)相對(duì)于幾何變換和光亮度的不變性，該特征對(duì)于獲取的投影圖像之間的差異具有較好的容錯(cuò)性。通過(guò)對(duì)提取出的特征進(jìn)行局部區(qū)域描述，特征點(diǎn)的獨(dú)特性非常好，有利于進(jìn)一步的匹配。

3 實(shí)驗(yàn)結(jié)果及分析

3.1 算法測(cè)試環(huán)境

本算法在Microsoft Visual Studio 2005環(huán)境下基于OpenGL和OpenCV，采用MFC實(shí)現(xiàn)，軟件運(yùn)行環(huán)境為：Inter(R) Core(TM) i7-4710MQ CPU @ 2.50 GHz，8 GB內(nèi)存，Windows 7 64位操作系統(tǒng)。本實(shí)驗(yàn)主要針對(duì)三維模型的數(shù)據(jù)處理。實(shí)驗(yàn)?zāi)Ｐ蛠?lái)源于美國(guó)Artec Spider手持式高精度三維掃描儀掃描得到的三維模型。

3.2 實(shí)驗(yàn)結(jié)果分析

首先本系統(tǒng)對(duì)掃描儀獲取的三維數(shù)據(jù)進(jìn)行處理。其中原始三維模型數(shù)據(jù)如圖2、圖3所示。

圖2 原始三維模型數(shù)據(jù)1Fig.2 original 3D model data 1

圖3 原始三維模型數(shù)據(jù)2Fig.3 original 3D model data 2

對(duì)數(shù)據(jù)進(jìn)行處理。得到的規(guī)則二維圖片如圖4、圖5所示。

圖4 提取的二維投影圖像1Fig.4 extracted 2D projection image 1

圖5 提取的二維投影圖像2Fig.5 extracted 2D projection image 2

對(duì)獲取的兩幅二維投影圖像，進(jìn)行基于SURF的配準(zhǔn)。配準(zhǔn)情況如圖6。將投影圖像中，匹配成功的對(duì)應(yīng)點(diǎn)對(duì)用黑色點(diǎn)打出并且連線(xiàn)。

圖6 配準(zhǔn)的二維投影圖像Fig.6 2D projection image after registration

4 結(jié)論

本文根據(jù)紋理映射仿射變換的原理和逆向工程的思維，將掃描儀得到的點(diǎn)云數(shù)據(jù)和紋理數(shù)據(jù)通過(guò)模型數(shù)據(jù)坐標(biāo)歸一化、確定二維投影圖像大小、三角形網(wǎng)格頂點(diǎn)像素信息提取等步驟提取二維投影圖像信息，再利用仿射變換關(guān)系計(jì)算整理二維圖像數(shù)據(jù)并補(bǔ)充像素丟失點(diǎn)，最后準(zhǔn)確地提取出了二維投影圖像。然后，根據(jù)提取出的兩幅二維投影圖像，基于SURF特征點(diǎn)提取算法，對(duì)兩幅投影圖像進(jìn)行了配準(zhǔn)。本文研究結(jié)果為基于二維圖像特征點(diǎn)的三維模型重建和配準(zhǔn)奠定了一定基礎(chǔ)。因此對(duì)基于二維圖像特征點(diǎn)的三維模型重建和配準(zhǔn)將是下一步工作的研究重點(diǎn)和研究方向。

致謝

本文受北方工業(yè)大學(xué)2016年度學(xué)生科技活動(dòng)項(xiàng)目的資助，在此鳴謝！

[1] 張志強(qiáng). 一種對(duì)扭曲景象序列三維重建迭代方法. 軟件, 2013, 34(10): 100-101. ZHANG Z Q. An iterative for 3D reconstruction of distorted image sequences. Software, 2013, 34(10): 100-101.

[2] HARRIS C, STEPHENS M. A combined corner and edge detector[C]// Proceedings of the 4thAlvey Vision Conference, Manchester: [S. n.], 1998, 15: 147-151.

[3] LOWE D G. Distinctive image features from scale-invariant key-points[J]. International Journal of Computer Vision, 2004, 60(2): 91-110.

[4] HERBERT B, ANDREAS E, TINNE T, et al. SURF: Speeded Up Robust Features[J]. Computer Vision and Image Understanding, 2008, 110(3): 346-359.

[5] 趙龍, 韋群. 改進(jìn)ICP算法用于多組圖像的點(diǎn)云拼接與融合[J]. 軟件, 2014, 35(3): 80-85. ZHAO L, WEI Q. Improved ICP algorithm for multi group image point cloud registration and fusion[J]. Software, 2014, 35(3): 80-85.

[6] 羅佳宇, 田會(huì)永等. 基于角點(diǎn)特征的自動(dòng)圖像配準(zhǔn). 軟件, 2011, 32(2): 67-70. LUO J Y, TIAN H Y. Automatic image registration based on corner feature. Software, 2011, 32(2): 67-70.

[7] 殷伶. 圖像匹配技術(shù)的研究[D]. 西安電子科技大學(xué), 2010. YIN L. Research on image matching technology[D]. Xidian University, 2010.

[8] BAY H, TUVTELLARS T, GOOL L Van. SURF: speeded up roust features[C]// Proceedings of the European Conference on Computer Vision, 2006: 404-414.

Image Registration Based on Multi View 3D Scanning Data

LIU Bo-wen, TONG Li-jing
(College of Computer, North China University of Technology, Beijing 100144, China)

Three dimensional laser scanning is a new technology developed in the last century in 90s. Taking into account the limits of measurement equipment measurement range and the complexity of the measured object, single scan can not get the complete and accurate model. So it is needed to scan the measured object from different viewpoints. Some high precision scanner can not only get the 3D point cloud data, but also get a scattered texture image. This paper is based on the principle of texture mapping and reverse engineering thinking. Through a series of steps, the image information is extracted from the point cloud data and texture data obtained by the scanner. Then, based on the principle of affine transformation, the information of 2D projection image is calculated. And the 2D projection image is extracted accurately. Finally, based on the SURF feature point extraction algorithm, two 2D projection images are registered.

3D scanning; Image acquisition; Projection image; SURF; Image registration

TP391

A

10.3969/j.issn.1003-6970.2016.09.007

北方工業(yè)大學(xué)2016年度學(xué)生科技活動(dòng)項(xiàng)目

劉博文(1992-)，男，碩士研究生，主要研究方向：數(shù)字圖像處理、三維重建。童立靖(1972-)，男，副教授，主要研究方向：數(shù)字圖像處理、計(jì)算機(jī)圖形學(xué)等。

童立靖，副教授，主要研究方向：數(shù)字圖像處理、計(jì)算機(jī)圖形學(xué)等。

本文著錄格式：劉博文，童立靖. 基于多視角三維掃描數(shù)據(jù)的圖像配準(zhǔn)[J]. 軟件，2016，37（9）：29-32