一种线性迭代非刚体射影重建方法

彭亚丽,刘侍刚,裘国永

(1.陕西师范大学现代教学技术教育部重点实验室,710062,西安;2.西安交通大学电子与信息工程学院,710049,西安;3.陕西师范大学计算机科学学院,710119,西安)



一种线性迭代非刚体射影重建方法

彭亚丽1,2,刘侍刚1,2,裘国永2,3

(1.陕西师范大学现代教学技术教育部重点实验室,710062,西安;2.西安交通大学电子与信息工程学院,710049,西安;3.陕西师范大学计算机科学学院,710119,西安)

为了从非标定图像序列中重建出三维非刚体的射影结构,提出了一种线性迭代非刚体射影重建方法。该方法将所有图像点放入一个图像矩阵中,利用图像矩阵具有低秩的特性,通过因式分解构造一个线性迭代算法来求解图像点的深度因子,最终通过奇异值分解实现非刚体的射影重建。该方法的优点是:射影重建过程都是线性求解,且将所有图像及图像点都平等地对待,并没有倚重某些图像及图像点。模拟实验结果表明,所提重建方法比经典的Alessio方法重投影误差小18%,比Brand方法小27%;最后的真实实验结果表明,所提的重建方法重投影误差只有1.28个像素,从而验证了所提方法的有效性。

射影重建;非刚体;因式分解

基于图像序列的三维重建一直是计算机视觉研究的热点问题之一,而射影重建又是三维重建过程中一个必不可少的阶段,其精度影响最终的重建结果[1-2]。如果没有任何先验知识,从图像序列中仅能实现射影重建[3]。

由于刚体运动的简单性,三维重建的早期研究工作大都基于物体是刚体的假设[4-5]。然而,现实世界中大多数物体都具有柔性,它们的运动都属于非刚体运动。为了重建非刚体物体,Bregler等人首先提出了非刚体可以由若干个刚体基组成的假设[6],并重建了非刚体的运动,但是该计算过程非常繁琐,导致其应用受到很大限制。后来的许多非刚体重建方法都是基于Bregler的假设[7-8],其中Valmadre采用动态规划的方法进行非刚体重建[9],但是该方法鲁棒性较差。为了提高重建算法的鲁棒性,Tao等学者混合先验知识对非刚体进行了重建[10-11],但在许多情况下很难获得非刚体的先验知识。有部分学者采用了光流法对非刚体进行重建[12-14],并获得了较好的重建效果,但这些非刚体重建方法都是假设相机为正投影模型,但正投影模型要求物体的景深远小于相机到物体的距离,当条件不满足时,误差比较大。针孔模型相对于正投影模型更加符合真实情况,因此重建精度更高。

本文假定相机为针孔模型,提出了一种线性迭代非刚体射影重建方法,该方法利用图像矩阵具有低秩的特性,通过因式分解构造一个线性迭代算法来求解图像点的深度因子,最后实现非刚体的射影重建。

1 相机模型

假定相机为针孔模型,成像过程可表示为

(1)

式中表示三维空间点的非齐次坐标为对应的图像平面点的齐次坐标;K为相机的内参矩阵;R、t分别为相机在拍摄位置对应的旋转矩阵和平移向量,即相机的外参矩阵;λ为深度因子。

若令

(2)

式中:P称为投影矩阵。则式(1)可以简写为

(3)

假设有m幅图像,每幅图像上有n个图像点,对于第i幅图像上的第j个图像点可表示为

(4)

2 非刚体射影重建

对于第i幅图像,由式(4)得

(5)

当物体做非刚体运动时,[Xi,1Xi,2…Xi,n]在运动过程中是变化的,可以认为由l个刚性基组成[6],即

(6)

式中:βi,k为权值;Bk为刚性基。

将式(6)代入式(5),可得

(7)

令

(8)

式中:Qi是Pi的前3列;pi是Pi的第4列。

将式(8)代入式(7),可得

(9)

整理可得

(10)

若将所有的图像点放在一起,则有

W=MB

(11)

从式(11)可以看出,W矩阵为低秩矩阵,其秩为3l+1。同时,对于任何非奇异矩阵A都有

W=MB=M′B′

(12)

式中:M′=MA-1;B′=AB。

从式(12)可以看出,如果没有任何先验知识,所有的重建可以相差一个变换A,因此该重建不是落在欧氏空间,而是落在射影空间。

3 迭代射影重建算法

如果已知深度因子λi,j,可以对W进行奇异值分解,即

W=SVDT

(13)

式中:S、D为正交矩阵;V为对角矩阵。

由于图像中含有噪声,因此不可能保证V中对角线上刚好只有前3l+1个元素为非0,但可以令对角线元素以外的其他元素为0。

式(13)可化简为

W=S′V′D′T

(14)

因此,令射影重建为

(15)

式(14)表明,W的列向量在矩阵S′所生成的子空间的正交补空间的投影为0[15],即

(16)

式中:T=I-S′(S′TS′)-1S′T。

λ1,ju1,jt1+λ1,jv1,jt2+…+λm,jvm,jt3m-1+λm,jt3m=0

(17)

整理得

[(u1,jt1+v1,jt2+t3)…(um,jt3m-2+vm,jt3m-1+

(18)

式(18)为线性方程,因此λi,j可以线性求解。

最初并不知道λi,j的值,因此无法通过式(13)完成因式分解,但通过分析知,可以构造一个线性迭代算法来求解λi,j。即初始假设所有的λi,j=1,通过式(14)可以求得S′,通过式(18)可以求得λi,j,此时的深度因子比上一步的深度因子更加接近真实值,经多次迭代后可以求得λi,j。

4 算法总结及运算量分析

本文算法的步骤如下。

步骤1:令ε1为无穷小的正数,k=1;

步骤3:利用式(13),对W奇异值分解,并令S′为S的前3l+1列;

步骤4:利用式(16)构造投影矩阵T;

步骤5:利用式(18)线性求取深度因子λi,j;

步骤7:利用式(15),实现射影重建。

本文运算量主要来自式(13)对矩阵W奇异值分解及式(18)求取深度因子。对矩阵W奇异值分解的计算量[15]为3mn2,式(18)求深度因子的运算量为3m3,总共有n组深度因子,因此求深度因子的总运算量为3m3n。从上面分析可以看出,本文运算量主要来自深度因子的求解,为3m3n。

5 实 验

5.1 仿真实验

为了验证本文方法的收敛性能,本文在一个单位球随机产生200个空间点,并将这些空间点分别分成3个和4个非刚体的刚性基。当分成3个刚性基时,第1个刚性基由前80个空间点组成,第2个和第3个刚性基各由60个空间点组成;当分成4个刚性基时,第1个刚性基由前80个空间点组成,后面3个刚性基各由40个空间点组成。模拟产生相机的内参数,变化相机外参以产生150幅图像,并在图像中分别加入0、0.5、1、1.5像素的高斯噪声。用本文的方法进行非刚体射影重建,并用v3l+2的值来衡量算法的收敛性能,在理想情况下,v3l+2的值应该为0,算法收敛性能如图1、图2所示。

图1 v11随迭代次数变化图

图2 v14随迭代次数变化图

最后,为了比较本文方法和Alessio方法[14]、Brand方法[16]的重建精度,用上述方法产生150幅图像,并在图像中加入0～2像素的高斯噪声,分别用本文方法、Alessio方法和Brand方法进行重建,在每个图像噪声下各运行200次,计算重投影误差,然后求平均值,模拟实验结果如图3所示。

图3 本文方法、Alessio方法和Brand方法比较

从图3可以看出,在3个、4个刚性基的情况下,本文方法的重投影误差比Alessio方法和Brand方法要小,约比Alessio方法小18%,比Brand方法小27%,说明本文方法比Alessio方法和Brand方法重建精度都要高。其原因是由于Alessio方法和Brand方法假设相机为正投影模型,当物体的景深远小于相机到物体的距离时,正投影模型能够较好地表示物体的成像过程,当该条件不满足时,重建误差比较大,而本文假设相机为针孔模型,该模型相对正投影模型更加符合实际情况,因此本文方法的重建精度要比Alessio方法的精度高,但非刚性基越多,两种方法的重投影误差都会增加。

5.2 真实实验

为了验证本文方法的正确性,本文获得一个200帧的恐龙图像序列,其中的2帧如图4所示。在该图像序列中,提取并跟踪了49个特征点(如图中+所示)。从图像序列中可以看出,由于恐龙的运动比较复杂,故它的运动不能当作刚体运动,只能当作非刚体运动。利用这些特征点,用本文方法进行非刚体射影重建,而且为了衡量本文方法的重建精度,本文对这些重建点进行重投影(如图中○所示)。

(a)第75帧

(b)第125帧图4 恐龙图像序列

从图4可以看出,提取的特征点和重投影点基本重合,说明本文方法具有较高的重建精度。同时,计算出平均重投影误差为1.28像素,具有较小的重投影误差。

6 结 论

本文提出了一种线性迭代非刚体射影重建方法,该方法利用图像矩阵具有低秩的特性,通过构造一个线性迭代算法求解图像点的深度因子,最终实现非刚体的射影重建。该方法的优点是:射影重建过程都是线性求解,且将所有图像及图像点都平等地对待。实验结果表明,该方法具有良好的收敛性,且具有较高的重建精度。本文方法非常适合于图像点位置为高斯噪声的情况,而且现实中提取的图像点位置也非常符合高斯噪声分布,但对于图像点位置为其他噪声的情况(如出格数据等),本文方法性能急骤下降,这是目前三维重建的一个研究热点问题,也是本文下一步的研究重点。

[1] SHEN S. Accurate multiple view 3D reconstruction using patch-based stereo for large-scale scenes [J]. IEEE Transactions on Image Processing, 2013, 22(5): 1901-1914.

[2] LEE M, CHOI C. Real-time facial shape recovery from a single image under general, unknown lighting by rank relaxation [J]. Computer Vision and Image Understanding, 2014, 120(3): 59-69.

[3] WU F, ZHANG M, HU Z. Self-calibration under the Cayley framework [J]. International Journal of Computer Vision, 2013, 103(3): 372-398.

[4] BASTIAN G, MATHIEU A, KALIN K, et al. A super-resolution framework for high-accuracy multiview reconstruction [J]. International Journal of Computer Vision, 2014, 106(2): 172-191.

[5] PENG Y, LIU S, LIU F. Projective reconstruction with occlusions [J]. Opto-Electronics Review, 2010, 18(2): 150-154.

[6] BREGLER C, HERTZMANN A, BIERMANN H. Recovering non-rigid 3D shape from image streams [C]∥IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2000: 690-696.

[7] NOGUER F, FUA P. Stochastic exploration of ambiguities for nonrigid shape recovery [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(2): 463-475.

[8] LIU S, PENG Y, ZENG Z, et al. An iterative method based on 1D subspace for projective reconstruction [J]. Opto-Electronics Review, 2011, 19(1): 89-94.

[9] VALMADRE J, ZHU Y, SRIDHARAN S, et al. Efficient articulated trajectory reconstruction using dynamic programming and filters [C]∥12th European Conference on Computer Vision. Berlin, Germany: Springer, 2012: 72-85.

[10]TAO L, MEIN S, QUAN W, et al. Recursive non-rigid structure from motion with online learned shape prior [J]. Computer Vision and Image Understanding, 2013, 117(10): 1287-1298.

[11]VALMADRE J, LUCEY S. General trajectory prior for non-rigid reconstruction [C]∥IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2012: 1394-1401.

[12]AKHTER I, SHEIKH Y, KHAN S, et al. Trajectory space: a dual representation for nonrigid structure from motion [J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2011, 33(7): 1442-1456.

[13]GARG R, ROUSSOS A, AGAPITO L. A variational approach to video registration with subspace constraints [J]. International Journal of Computer Vision, 2013, 104(3): 286-314.

[14]ALESSIO D. Adaptive non-rigid registration and structure from motion from image trajectories [J]. International Journal of Computer Vision, 2013, 103(2): 226-239.

[15]王永茂, 刘德友. 矩阵分析基础 [M]. 北京: 清华大学出版社, 2012.

[16]BRAND M. A direct method for 3D factorization of non-rigid motion observed in 2D [C]∥IEEE Conference on Computer Vision and Pattern Recognition. Piscataway, NJ, USA: IEEE, 2005: 122-128.

[本刊相关文献链接]

陈德祥,徐自力.多重网格在黏性流动最小二乘等几何模拟中的应用.2014,48(11):122-127.[doi:10.7652/xjtuxb2014 11021]

杜辉,王宇平,董晓盼.采用万有引力定律自动确定类数的K均值算法.2014,48(10):115-119.[doi:10.7652/xjtuxb 201410018]

蒲伟,王家序,周广武,等.卷吸速度方向与椭圆短轴成一夹角的弹流润滑渐近网格加密算法.2014,48(9):95-100.[doi:10.7652/xjtuxb201409016]

郭涛,李国君.内嵌晃荡液体减振的流固耦合分析.2014,48(9):117-122.[doi:10.7652/xjtuxb201409020]

任茂栋,梁晋,唐正宗,等.数字图像相关法中的优化插值滤波器.2014,48(7):65-70.[doi:10.7652/xjtuxb201407012]

刘骁,王小鑫,胡红利,等.改进型离线迭代在线重构算法的电容层析成像技术研究.2014,48(4):35-40.[doi:10.7652/xjtuxb201404007]

张思文,吴九汇,刘彰宜.黏弹阻尼对一维杆状声子晶体能带结构频移的影响.2014,48(3):22-27.[doi:10.7652/xjtuxb 201403005]

吴仁斌,姚敏立,贾维敏,等.采用幅度响应约束的鲁棒自适应波束形成算法.2014,48(4):109-114.[doi:10.7652/xjtuxb 201404019]

(编辑 赵炜)

A Linearly Iterative Method for Non-Rigid Projective Reconstruction

PENG Yali1,2,LIU Shigang1,2,QIU Guoyong2,3

(1. Key Laboratory of Modern Teaching Technology, Ministry of Education, Shaanxi Normal University, Xi’an 710062, China; 2. School of Electronics and Information Engineering, Xi’an Jiaotong University, Xi’an 710049, China; 3. School of Computer Science, Shaanxi Normal University, Xi’an 710119, China)

A linearly iterative method for reconstruction of 3D non-rigid projection is presented to reconstruct the 3D non-rigid projective structure from an un-calibrated image sequence. All the image points are placed into an image matrix, and the linearly iterative method that employs the singular value decomposition is used to get the depth factors of the image points by using the low rank property of the image matrix. Then the projective reconstruction is realized through the singular value decomposition. The innovations of the proposed method are that the projective reconstruction is linear, all the image points are treated fairly, and it does not rely on certain image or image points. Experiment results with simulation data show that the proposed method is 18% and 27% smaller in re-projective error than Alessio’s method and Brand’s method, respectively. A real experiment shows that the method has only 1.28 pixels error, and hence efficient.

projective reconstruction; non-rigid; factorization

2014-06-02。

彭亚丽(1979—),女,讲师;刘侍刚(通信作者),男,副教授。

国家自然科学基金资助项目(61402274);陕西师范大学中央高校基本科研业务费资助项目(GK201402040,GK201302029);陕西师范大学学习科学交叉学科培育计划资助项目。

10.7652/xjtuxb201501017

TP391.41;P232

A

0253-987X(2015)01-0102-05