基于SIFT特征檢測(cè)和三次插值樣條的快速曲面重構(gòu)算法

陽(yáng)建中，陳慧蓉，胡俐蕊

(1.欽州學(xué)院 電信學(xué)院，廣西 欽州 535011； 2.欽州市電子產(chǎn)品檢測(cè)實(shí)驗(yàn)室，廣西 欽州 535011；3.欽州學(xué)院 資環(huán)學(xué)院，廣西 欽州 535011)

基于SIFT特征檢測(cè)和三次插值樣條的快速曲面重構(gòu)算法

陽(yáng)建中1,2，陳慧蓉3，胡俐蕊1

(1.欽州學(xué)院 電信學(xué)院，廣西 欽州 535011； 2.欽州市電子產(chǎn)品檢測(cè)實(shí)驗(yàn)室，廣西 欽州 535011；3.欽州學(xué)院 資環(huán)學(xué)院，廣西 欽州 535011)

針對(duì)傳統(tǒng)的曲面重構(gòu)算法一直存在重構(gòu)精度低、效率差的問(wèn)題，提出新的快速曲面重構(gòu)算法；基于三次插值樣條和改進(jìn)SIFT特征檢測(cè)和匹配方法，先對(duì)二維圖像預(yù)處理后，檢測(cè)其邊界點(diǎn)并且擬合，然后將區(qū)域按四個(gè)象限進(jìn)行分區(qū)，用三次插值樣條邊界進(jìn)行曲面重構(gòu)，同時(shí)結(jié)合改進(jìn)的SIFT特征檢測(cè)和匹配方法，檢測(cè)各個(gè)區(qū)域曲面邊界的特征點(diǎn)，然后再進(jìn)行匹配拼接；實(shí)驗(yàn)結(jié)果表明，該算法得到曲面模型的時(shí)間效率有很大的提高，并且曲面效果好，光滑、平順。

曲面重構(gòu)；三次插值樣條；SIFT特征檢測(cè)

0 引言

在計(jì)算機(jī)圖形圖像技術(shù)快速發(fā)展中，利用計(jì)算機(jī)對(duì)物體表面進(jìn)行曲面重構(gòu)，有較多的方法。目前，主要是大致分為3大類(lèi)曲面重構(gòu)算法[1]：(1)基于區(qū)域增長(zhǎng)的方法。此類(lèi)方法主要是通過(guò)種子來(lái)劃分三角區(qū)域，然后再將這些區(qū)域分別一次加入到重構(gòu)的網(wǎng)格中。(2)基于Delaunay的方法。此方法是基于點(diǎn)云Delaunay三角化，把物體的表面劃分成不同三角面片，然后分別對(duì)這些三角面片進(jìn)行處理，此方法能處理一些較復(fù)雜點(diǎn)的對(duì)象。但是，算法的復(fù)雜度高，花費(fèi)的時(shí)間很長(zhǎng)，處理速度慢，效率低。(3)隱函數(shù)的方法。通過(guò)不同的隱函數(shù)來(lái)表示曲面。

文獻(xiàn)[2]提出了一種隱曲面和廣義多項(xiàng)式神經(jīng)網(wǎng)絡(luò)的曲面重構(gòu)方法。基于梯度下降法，推倒了神經(jīng)網(wǎng)絡(luò)的學(xué)習(xí)過(guò)程，利用網(wǎng)絡(luò)做了一些簡(jiǎn)單的實(shí)驗(yàn)。文獻(xiàn)[3]分析了點(diǎn)云掃描線的位置關(guān)系，提出改進(jìn)掃描線的剖分優(yōu)化方法，最后進(jìn)行重建。文獻(xiàn)[4]研究了離散點(diǎn)云曲面擬合以及提高曲面品質(zhì)的方法,通過(guò)不同的特征點(diǎn)實(shí)現(xiàn)網(wǎng)格控制和精度擬合。主要是生成的圖形不完整，有部分缺陷。

本文主要針對(duì)上述的一些問(wèn)題，特別是算法的處理效率低的問(wèn)題，提出了一種利用三次插值樣條，對(duì)二維圖像檢測(cè)的邊界進(jìn)行擬合，分區(qū)域利用邊界進(jìn)行曲面重構(gòu)，同時(shí)結(jié)合SIFT特征檢測(cè)的方法檢測(cè)特征點(diǎn)，最后對(duì)各個(gè)區(qū)域曲面進(jìn)行匹配和拼接。

1 圖像的預(yù)處理

由于拍攝過(guò)程中，有一些背景和噪聲，通過(guò)灰度化和形態(tài)學(xué)的方法處理掉背景和噪聲。再將圖像進(jìn)行二值化處理，為了便于后面的計(jì)算，將二值化的圖像前景置為黑色，背景置為白色，如圖1。

圖1 預(yù)處理

2 三次插值樣條原理

對(duì)插值區(qū)間[a,b]進(jìn)行劃分：a≤x0

(1)

則稱(chēng)S(x)為三次樣條插值函數(shù)。

三次樣條插值問(wèn)題提法：對(duì)[a,b]上給定的數(shù)表如下求一個(gè)分段三次多項(xiàng)式函數(shù)S(x)滿(mǎn)足插值條件S(xi)=yi(i=0,1,……n)式，并在插值區(qū)間[a,b]上有二階連續(xù)導(dǎo)數(shù)。

若函數(shù)S(x)滿(mǎn)足：

1)二階連續(xù)，即s(x)是節(jié)點(diǎn)上的二次樣條函數(shù)；

2)三次分段，即在每一個(gè)小區(qū)間上是三次多項(xiàng)式；

3)已知通過(guò)n+1個(gè)插值點(diǎn)，即s(xi)=yi(i=0，1，2，…，n)；

則稱(chēng)S(x)為函數(shù)[a,b]上的三次插值樣條函數(shù)。在構(gòu)造三次插值樣條函數(shù)時(shí)，為確定s(x)，應(yīng)根據(jù)n+1個(gè)插值條件以及給定的邊界條件，再利用節(jié)點(diǎn)處的一階導(dǎo)數(shù)或二階導(dǎo)數(shù)就，可以構(gòu)造出三次插值樣條函數(shù)。那么可以得到：

(2)

它是關(guān)于m0,m1, …,mn-1,mn的三對(duì)角方程組, 可以看出, 該方程組的系數(shù)矩陣是三對(duì)角的, 矩陣中所有非零元素都集中在主對(duì)角線及其相鄰的兩條對(duì)角線上, 除了這三條對(duì)角線上的元素外, 其余元素全為零, 它是一種嚴(yán)格對(duì)角占優(yōu)的稀疏矩陣。為了得到精確的物體的邊界，這里通過(guò)三次插值樣條對(duì)圖像中邊界進(jìn)行多次分段的擬合和逼近。

圖2 邊界特征

3 基于SIFT特征檢測(cè)及描述

本文主要檢測(cè)了邊界圖形中的拐點(diǎn)、突變點(diǎn)等特征點(diǎn)，用于后面不同區(qū)域曲面模型的匹配。這里采用SIFT特征提取算法對(duì)已檢測(cè)出的邊界曲線進(jìn)行特征點(diǎn)提取。

3.1 特征點(diǎn)檢測(cè)

LOWE在2004年提出了SIFT特征提取算法[6-8]，其主要是在DOG尺度空間來(lái)檢測(cè)局部的極值作為特征點(diǎn)，而這些特征點(diǎn)又具有良好的獨(dú)特性和穩(wěn)定性。用L表示圖像的尺度空間，I(x,y)表示圖像在(x,y)圖像的像素值， DOG算子是利用不同尺度的高斯分核與圖像卷積而得。為了檢測(cè)不同象限旋轉(zhuǎn)所得的曲面的特征，圖形邊界是通過(guò)三次插值樣條合成，因此，為了更加準(zhǔn)確的定位特征點(diǎn)(包括拐點(diǎn)、型值點(diǎn)、控制點(diǎn)等)，需要先得到特征點(diǎn)的擬合函數(shù)，同時(shí)利用判斷該點(diǎn)是否為偽特征點(diǎn)，若是，則需要不斷的修正X，獲得局部最優(yōu)點(diǎn)，刪掉特征弱的偽特征點(diǎn)。否則，計(jì)算出該特征點(diǎn)的法向量，用于實(shí)現(xiàn)特征點(diǎn)的精確匹配，減少誤配。

3.2 特征描述符的生成

特征描述符主要是特征點(diǎn)的方向，其能夠在匹配的時(shí)候用于更加準(zhǔn)確的進(jìn)行配準(zhǔn)。為了匹配更加準(zhǔn)確，設(shè)特征點(diǎn)位中心，從4個(gè)方向進(jìn)行梯度運(yùn)算，由于邊界是線條，檢測(cè)的窗口選擇3×3，計(jì)算4個(gè)方向的梯度，3×3共9個(gè)點(diǎn)描述，每個(gè)點(diǎn)有4個(gè)方向，因此，方向的信息量為3×3×4=36個(gè)信息。其中，點(diǎn)(x,y)匹配的方向如圖2所示，梯度計(jì)算公式為：

(3)

通過(guò)上述方法，檢測(cè)出的特征點(diǎn)如圖4，圖中的特征點(diǎn)基本都被檢測(cè)出來(lái)，這些點(diǎn)將被用于不同區(qū)域間曲面的匹配。

圖3 檢測(cè)方向

圖4 提取特征點(diǎn)

4 表面三維重構(gòu)的步驟

通過(guò)三次插值樣條曲線，可以得到圖像的邊界曲線，將這些邊緣通過(guò)旋轉(zhuǎn)的方式可以得到物體的表面模型，如圖5所示。

圖5 區(qū)域和旋轉(zhuǎn)示意圖

通常情況，可以通過(guò)繞中心軸旋轉(zhuǎn)360度就可以得到物體的表面模型，為了加快處理速度，在這里將模型分成四個(gè)區(qū)域，分別為第I象限、第II象限、第III象限以及第IV象限，在進(jìn)行旋轉(zhuǎn)的時(shí)候，邊界線同時(shí)在每個(gè)象限進(jìn)行的生存曲面模型，這樣可以將曲面模型的生成速度提高大約4倍。

算法的步驟：

(1)獲得圖像邊界。先對(duì)圖像進(jìn)行預(yù)處理，去除孔洞等，再通過(guò)三次插值算法獲得相關(guān)圖像的邊界和輪廓。

(2)將邊界分別置于四個(gè)象限的起始位置，分別稱(chēng)為edge1,edge2,edge3以及edge4,分別按順勢(shì)時(shí)針?lè)较蛐D(zhuǎn)得到每個(gè)象限的曲面S1,S2,S3,S4。

(3)檢測(cè)特征點(diǎn)。使用SIFT特征檢測(cè)各個(gè)曲面邊界的特征點(diǎn)，同時(shí)計(jì)算出特征點(diǎn)的法向量以及各法向量之間的夾角。

(4)曲面匹配。先判斷兩個(gè)曲面特征點(diǎn)和，若法向量方向?yàn)槠叫校瑒t判斷夾角，然后進(jìn)行特征匹配和融合；否則找下一個(gè)特征點(diǎn)。

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

本文的實(shí)驗(yàn)所使用的硬件、操作系統(tǒng)及編譯環(huán)境為：以VC++和matlab作為開(kāi)發(fā)語(yǔ)言，在WIN7、內(nèi)存為2GB、顯卡為Intel G41 Express Chipset。對(duì)不同的模型用本文和文獻(xiàn)[6]的算法分別進(jìn)行測(cè)試，主要是針對(duì)算法的時(shí)間進(jìn)行一些改進(jìn)和優(yōu)化。

從大量的實(shí)驗(yàn)中選出了幾個(gè)圖形，如圖6所示。從實(shí)驗(yàn)效果分析，本文算法重建效果相比文獻(xiàn)[6]是根據(jù)點(diǎn)云的幾何與形狀特征進(jìn)行分類(lèi)，對(duì)網(wǎng)格進(jìn)行布局重構(gòu)，最后，再修補(bǔ)拓?fù)浜蛶缀五e(cuò)誤，有效地解決了一些小細(xì)節(jié)問(wèn)題，如孔洞、點(diǎn)分布不均勻等，不存在有孔洞和點(diǎn)分布不均的效果。而與文獻(xiàn)[6]中相比較，重構(gòu)的效果圖，沒(méi)有光線照射的不均衡等。

圖6 效果圖

序號(hào)參數(shù) abcd體積1．5834e+0072．1602e+0072．0937e+0071．7260e+007表面積2．3456e+0052．8376e+0052．4625e+0052．6372e+005

6 結(jié)論

本文提出了一種基于SIFT特征檢測(cè)和三次樣條曲線擬合的方法。在曲面重構(gòu)的過(guò)程中，對(duì)曲面進(jìn)行不同的分區(qū)，在同時(shí)使用邊界旋轉(zhuǎn)的方法同時(shí)在四個(gè)區(qū)域進(jìn)行曲面合成，最后進(jìn)行不同區(qū)域曲面進(jìn)行匹配拼接。算法的生成曲面效果良好，主要在算法時(shí)間效率上有了很大的提高，后續(xù)工作可以對(duì)曲面進(jìn)一步優(yōu)化。

[1] 孫國(guó)輝,包 宏,等.三維物體表面重建方法的分析[J].計(jì)算機(jī)應(yīng)用研究，2004,4(12):253-255.

[2] 肖秀春，姜孝華,等.基于廣義多項(xiàng)式神經(jīng)網(wǎng)絡(luò)的點(diǎn)云數(shù)據(jù)隱式曲面重構(gòu)方法[J].計(jì)算機(jī)應(yīng)用,2009,29(8):2043-2045.

[3] 肖 華，張三元,等.基于點(diǎn)云幾何與形狀特征的曲面重構(gòu)算法[J].計(jì)算機(jī)工程,2010,36(13):193-195.

[4] 張玉香,張興軍.采用激光掃描點(diǎn)云擬合自由曲面的重構(gòu)特性研究[J].激光與紅外,2011,41(3):351-355.

[5] 王 磊.旋轉(zhuǎn)視圖的三維重構(gòu)[D].合肥：安徽大學(xué),2007.

[6] 梁群仙，許宏麗.一種基于點(diǎn)云數(shù)據(jù)的快速曲面重構(gòu)方法[J].計(jì)算機(jī)工程,2013,39(2):238-240.

[7] 藺海峰，馬宇峰,等.基于SIFT特征目標(biāo)跟蹤算法研究[J].自動(dòng)化學(xué)報(bào),2010,36(8):1025-1028.

[8] 單好民. 一種改進(jìn)的壓縮感知信號(hào)重建算法在WSN中的研究[J]. 計(jì)算機(jī)測(cè)量與控制, 2015, 23(11):3766-3768.

Fast Mesh Reconstruction Algorithm Based on SIFT Features Detection and Cubic Spline Curve Fitting

Yang Jianzhong1,2,Chen Huirong3,Hu Lirui1

(1.School Of Electronics and Information, Qinzhou University;Qinzhou 535011,China; 2.Qinzhou Key Laboratory of Electronic Product Testing, Qinzhou 535011,China; 3.School Of Resources and Environmental, Qinzhou University;Qinzhou 535011,China)

Aiming at the problem of low reconstruction precision and poor efficiency, a new method of fast surface reconstruction is proposed. Based on the three spline interpolation and improved SIFT feature detection and matching method, first to two-dimensional image after pretreatment, detection of the boundary points and fitting, and then the area is partitioned by four quadrants, surface reconstruction with three interpolation spline boundary feature points, combined with improved SIFT feature detection and matching method detection of each region boundary surface, and then matching stitching. Experimental results show that the proposed algorithm can improve the time efficiency of the surface model, and the surface effect is good, smooth and smooth.

mesh reconstruction; SIFT features detection; cubic spline curve fitting

2016-10-15；

2016-11-21。

廣西教育廳高校科研項(xiàng)目(KY2015YB314;KY2016LX434)。

陽(yáng)建中(1984-)，男，江西九江人，碩士研究生，講師，主要從事出像處理與模式識(shí)別方向的研究。

1671-4598(2017)01-0185-03

10.16526/j.cnki.11-4762/tp.2017.01.052

TP391.7

A