陽建中，陳慧蓉，胡俐蕊

(1.欽州學院 電信學院，廣西 欽州 535011； 2.欽州市電子產品檢測實驗室，廣西 欽州 535011；3.欽州學院 資環(huán)學院，廣西 欽州 535011)

基于SIFT特征檢測和三次插值樣條的快速曲面重構算法

陽建中1,2，陳慧蓉3，胡俐蕊1

(1.欽州學院 電信學院，廣西 欽州 535011； 2.欽州市電子產品檢測實驗室，廣西 欽州 535011；3.欽州學院 資環(huán)學院，廣西 欽州 535011)

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

曲面重構；三次插值樣條；SIFT特征檢測

0 引言

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

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

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

1 圖像的預處理

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

圖1 預處理

2 三次插值樣條原理

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

(1)

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

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

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

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

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

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

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

(2)

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

圖2 邊界特征

3 基于SIFT特征檢測及描述

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

3.1 特征點檢測

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

3.2 特征描述符的生成

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

(3)

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

圖3 檢測方向

圖4 提取特征點

4 表面三維重構的步驟

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

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

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

算法的步驟：

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

(2)將邊界分別置于四個象限的起始位置，分別稱為edge1,edge2,edge3以及edge4,分別按順勢時針方向旋轉得到每個象限的曲面S1,S2,S3,S4。

(3)檢測特征點。使用SIFT特征檢測各個曲面邊界的特征點，同時計算出特征點的法向量以及各法向量之間的夾角。

(4)曲面匹配。先判斷兩個曲面特征點和，若法向量方向為平行，則判斷夾角，然后進行特征匹配和融合；否則找下一個特征點。

5 實驗結果及分析

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

從大量的實驗中選出了幾個圖形，如圖6所示。從實驗效果分析，本文算法重建效果相比文獻[6]是根據點云的幾何與形狀特征進行分類，對網格進行布局重構，最后，再修補拓撲和幾何錯誤，有效地解決了一些小細節(jié)問題，如孔洞、點分布不均勻等，不存在有孔洞和點分布不均的效果。而與文獻[6]中相比較，重構的效果圖，沒有光線照射的不均衡等。

圖6 效果圖

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

6 結論

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

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

[2] 肖秀春，姜孝華,等.基于廣義多項式神經網絡的點云數(shù)據隱式曲面重構方法[J].計算機應用,2009,29(8):2043-2045.

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

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

[5] 王 磊.旋轉視圖的三維重構[D].合肥：安徽大學,2007.

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

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

[8] 單好民. 一種改進的壓縮感知信號重建算法在WSN中的研究[J]. 計算機測量與控制, 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。

廣西教育廳高?？蒲许椖?KY2015YB314;KY2016LX434)。

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

1671-4598(2017)01-0185-03

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

TP391.7

A