基于SIFT特征检测和三次插值样条的快速曲面重构算法

阳建中，陈慧蓉，胡俐蕊

(1.钦州学院 电信学院，广西 钦州 535011； 2.钦州市电子产品检测实验室，广西 钦州 535011；3.钦州学院 资环学院，广西 钦州 535011)

基于SIFT特征检测和三次插值样条的快速曲面重构算法

阳建中1,2，陈慧蓉3，胡俐蕊1

(1.钦州学院 电信学院，广西 钦州 535011； 2.钦州市电子产品检测实验室，广西 钦州 535011；3.钦州学院 资环学院，广西 钦州 535011)

针对传统的曲面重构算法一直存在重构精度低、效率差的问题，提出新的快速曲面重构算法；基于三次插值样条和改进SIFT特征检测和匹配方法，先对二维图像预处理后，检测其边界点并且拟合，然后将区域按四个象限进行分区，用三次插值样条边界进行曲面重构，同时结合改进的SIFT特征检测和匹配方法，检测各个区域曲面边界的特征点，然后再进行匹配拼接；实验结果表明，该算法得到曲面模型的时间效率有很大的提高，并且曲面效果好，光滑、平顺。

曲面重构；三次插值样条；SIFT特征检测

0 引言

在计算机图形图像技术快速发展中，利用计算机对物体表面进行曲面重构，有较多的方法。目前，主要是大致分为3大类曲面重构算法[1]：(1)基于区域增长的方法。此类方法主要是通过种子来划分三角区域，然后再将这些区域分别一次加入到重构的网格中。(2)基于Delaunay的方法。此方法是基于点云Delaunay三角化，把物体的表面划分成不同三角面片，然后分别对这些三角面片进行处理，此方法能处理一些较复杂点的对象。但是，算法的复杂度高，花费的时间很长，处理速度慢，效率低。(3)隐函数的方法。通过不同的隐函数来表示曲面。

文献[2]提出了一种隐曲面和广义多项式神经网络的曲面重构方法。基于梯度下降法，推倒了神经网络的学习过程，利用网络做了一些简单的实验。文献[3]分析了点云扫描线的位置关系，提出改进扫描线的剖分优化方法，最后进行重建。文献[4]研究了离散点云曲面拟合以及提高曲面品质的方法,通过不同的特征点实现网格控制和精度拟合。主要是生成的图形不完整，有部分缺陷。

本文主要针对上述的一些问题，特别是算法的处理效率低的问题，提出了一种利用三次插值样条，对二维图像检测的边界进行拟合，分区域利用边界进行曲面重构，同时结合SIFT特征检测的方法检测特征点，最后对各个区域曲面进行匹配和拼接。

1 图像的预处理

由于拍摄过程中，有一些背景和噪声，通过灰度化和形态学的方法处理掉背景和噪声。再将图像进行二值化处理，为了便于后面的计算，将二值化的图像前景置为黑色，背景置为白色，如图1。

图1 预处理

2 三次插值样条原理

对插值区间[a,b]进行划分：a≤x0

(1)

则称S(x)为三次样条插值函数。

三次样条插值问题提法：对[a,b]上给定的数表如下求一个分段三次多项式函数S(x)满足插值条件S(xi)=yi(i=0,1,……n)式，并在插值区间[a,b]上有二阶连续导数。

若函数S(x)满足：

1)二阶连续，即s(x)是节点上的二次样条函数；

2)三次分段，即在每一个小区间上是三次多项式；

3)已知通过n+1个插值点，即s(xi)=yi(i=0，1，2，…，n)；

则称S(x)为函数[a,b]上的三次插值样条函数。在构造三次插值样条函数时，为确定s(x)，应根据n+1个插值条件以及给定的边界条件，再利用节点处的一阶导数或二阶导数就，可以构造出三次插值样条函数。那么可以得到：

(2)

它是关于m0,m1, …,mn-1,mn的三对角方程组, 可以看出, 该方程组的系数矩阵是三对角的, 矩阵中所有非零元素都集中在主对角线及其相邻的两条对角线上, 除了这三条对角线上的元素外, 其余元素全为零, 它是一种严格对角占优的稀疏矩阵。为了得到精确的物体的边界，这里通过三次插值样条对图像中边界进行多次分段的拟合和逼近。

图2 边界特征

3 基于SIFT特征检测及描述

本文主要检测了边界图形中的拐点、突变点等特征点，用于后面不同区域曲面模型的匹配。这里采用SIFT特征提取算法对已检测出的边界曲线进行特征点提取。

3.1 特征点检测

LOWE在2004年提出了SIFT特征提取算法[6-8]，其主要是在DOG尺度空间来检测局部的极值作为特征点，而这些特征点又具有良好的独特性和稳定性。用L表示图像的尺度空间，I(x,y)表示图像在(x,y)图像的像素值， DOG算子是利用不同尺度的高斯分核与图像卷积而得。为了检测不同象限旋转所得的曲面的特征，图形边界是通过三次插值样条合成，因此，为了更加准确的定位特征点(包括拐点、型值点、控制点等)，需要先得到特征点的拟合函数，同时利用判断该点是否为伪特征点，若是，则需要不断的修正X，获得局部最优点，删掉特征弱的伪特征点。否则，计算出该特征点的法向量，用于实现特征点的精确匹配，减少误配。

3.2 特征描述符的生成

特征描述符主要是特征点的方向，其能够在匹配的时候用于更加准确的进行配准。为了匹配更加准确，设特征点位中心，从4个方向进行梯度运算，由于边界是线条，检测的窗口选择3×3，计算4个方向的梯度，3×3共9个点描述，每个点有4个方向，因此，方向的信息量为3×3×4=36个信息。其中，点(x,y)匹配的方向如图2所示，梯度计算公式为：

(3)

通过上述方法，检测出的特征点如图4，图中的特征点基本都被检测出来，这些点将被用于不同区域间曲面的匹配。

图3 检测方向

图4 提取特征点

4 表面三维重构的步骤

通过三次插值样条曲线，可以得到图像的边界曲线，将这些边缘通过旋转的方式可以得到物体的表面模型，如图5所示。

图5 区域和旋转示意图

通常情况，可以通过绕中心轴旋转360度就可以得到物体的表面模型，为了加快处理速度，在这里将模型分成四个区域，分别为第I象限、第II象限、第III象限以及第IV象限，在进行旋转的时候，边界线同时在每个象限进行的生存曲面模型，这样可以将曲面模型的生成速度提高大约4倍。

算法的步骤：

(1)获得图像边界。先对图像进行预处理，去除孔洞等，再通过三次插值算法获得相关图像的边界和轮廓。

(2)将边界分别置于四个象限的起始位置，分别称为edge1,edge2,edge3以及edge4,分别按顺势时针方向旋转得到每个象限的曲面S1,S2,S3,S4。

(3)检测特征点。使用SIFT特征检测各个曲面边界的特征点，同时计算出特征点的法向量以及各法向量之间的夹角。

(4)曲面匹配。先判断两个曲面特征点和，若法向量方向为平行，则判断夹角，然后进行特征匹配和融合；否则找下一个特征点。

5 实验结果及分析

本文的实验所使用的硬件、操作系统及编译环境为：以VC++和matlab作为开发语言，在WIN7、内存为2GB、显卡为Intel G41 Express Chipset。对不同的模型用本文和文献[6]的算法分别进行测试，主要是针对算法的时间进行一些改进和优化。

从大量的实验中选出了几个图形，如图6所示。从实验效果分析，本文算法重建效果相比文献[6]是根据点云的几何与形状特征进行分类，对网格进行布局重构，最后，再修补拓扑和几何错误，有效地解决了一些小细节问题，如孔洞、点分布不均匀等，不存在有孔洞和点分布不均的效果。而与文献[6]中相比较，重构的效果图，没有光线照射的不均衡等。

图6 效果图

序号参数 abcd体积1．5834e+0072．1602e+0072．0937e+0071．7260e+007表面积2．3456e+0052．8376e+0052．4625e+0052．6372e+005

6 结论

本文提出了一种基于SIFT特征检测和三次样条曲线拟合的方法。在曲面重构的过程中，对曲面进行不同的分区，在同时使用边界旋转的方法同时在四个区域进行曲面合成，最后进行不同区域曲面进行匹配拼接。算法的生成曲面效果良好，主要在算法时间效率上有了很大的提高，后续工作可以对曲面进一步优化。

[1] 孙国辉,包 宏,等.三维物体表面重建方法的分析[J].计算机应用研究，2004,4(12):253-255.

[2] 肖秀春，姜孝华,等.基于广义多项式神经网络的点云数据隐式曲面重构方法[J].计算机应用,2009,29(8):2043-2045.

[3] 肖 华，张三元,等.基于点云几何与形状特征的曲面重构算法[J].计算机工程,2010,36(13):193-195.

[4] 张玉香,张兴军.采用激光扫描点云拟合自由曲面的重构特性研究[J].激光与红外,2011,41(3):351-355.

[5] 王 磊.旋转视图的三维重构[D].合肥：安徽大学,2007.

[6] 梁群仙，许宏丽.一种基于点云数据的快速曲面重构方法[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