三维重建计算机视觉 (8).pdf
Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用Courtesy of Oxford Visual Geometry GroupStructure from Motion(sfm)运动恢复结构问题通过三维场景的多张图象，恢复出该场景的三维结构信息以及每张图片对应的摄像机参数运动恢复结构问题!#$已知:n个3D点!在张图像中的对应点的像素坐标!(=1,=1,)且#$=!其中，)为第i张图片对应的摄像机的投影矩阵=1,;=1,运动恢复结构问题!#$已知:n个3D点!在张图像中的对应点的像素坐标且#$=!其中，)为第i张图片对应的摄像机的投影矩阵=1,;=1,求解：m个摄像机投影矩阵)(=1,);n个三维点=1,的坐标。!(=1,=1,)运动恢复结构问题!#$已知:n个3D点!在张图像中的对应点的像素坐标结构（structure）且#$=!其中，)为第i张图片对应的摄像机的投影矩阵=1,;=1,求解：m个摄像机投影矩阵)(=1,);n个三维点=1,的坐标。运动（motion）!(=1,=1,)运动恢复结构问题!#$已知:n个3D点!在张图像中的对应点的像素坐标结构（structure）且#$=!其中，)为第i张图片对应的摄像机的投影矩阵=1,;=1,求解：m个摄像机投影矩阵)(=1,);n个三维点=1,的坐标。运动（motion）!(=1,=1,)因此，该类问题也称为“运动恢复结构问题”！欧式结构恢复（摄像机内参数已知，外参数未知）仿射结构恢复（摄像机为仿射相机，内、外参数均未知）透视结构恢复（摄像机为透视相机，内、外参数均未知）三种典型的运动恢复结构任务Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用已知已知:n个三维点=1,在张图像中的对应点的像素坐标)m张图像对应的摄像机的内参数矩阵)(=1,)欧式结构恢复问题且=1,;=1,#$=!=!图像个数3D点个数其中，)，)，)为第i张图片对应的摄像机的投影矩阵、内参数及外参数矩阵已知已知:n个三维点=1,在张图像中的对应点的像素坐标)m张图像对应的摄像机的内参数矩阵)(=1,)欧式结构恢复问题且=1,;=1,#$=!=!图像个数3D点个数其中，)，)，)为第i张图片对应的摄像机的投影矩阵、内参数及外参数矩阵求解：求解：n个三维点=1,的坐标；m个摄像机的外参数)及)(=1,)已知已知:n个三维点=1,在张图像中的对应点的像素坐标)m张图像对应的摄像机的内参数矩阵)(=1,)欧式结构恢复问题且=1,;=1,#$=!=!图像个数3D点个数其中，)，)，)为第i张图片对应的摄像机的投影矩阵、内参数及外参数矩阵求解：求解：n个三维点=1,的坐标；m个摄像机的外参数)及)(=1,)？欧式结构恢复问题（两视图）欧式结构恢复问题（两视图）O1O2!R,T#%$=%0!&$=&!求解求解:1.求解基础矩阵F2.利用F与摄像机内参数求解本质矩阵E3.分解本质矩阵获得R与T4.三角化求解三维点坐标欧式结构恢复问题（两视图）%$=%!=%0!&$=&!=&!问题问题:=&%归一化八点法=argmin+!,!+(#,#)、=1,本质矩阵分解找到一个策略把 因式分解为两个组成部分=本质矩阵分解找到一个策略把 因式分解为两个组成部分=567567=0无法确定的符号及尺度；或者都满足上式所以，也无法确定的符号及尺度重要说明：本质矩阵分解=定义两个矩阵：=010100001=010100000本质矩阵分解=定义两个矩阵：=010100001=010100000=diag 1,1,0 =diag(1,1,0)A重要性质：相差一个正负号的情况下本质矩阵分解定义两个矩阵：=010100001=010100000可以写成：=A其中，是单位正交矩阵。=diag 1,1,0 =diag(1,1,0)A重要性质：相差一个正负号的情况下=本质矩阵分解定义两个矩阵：=010100001=010100000可以写成：=A其中，是单位正交矩阵。=diag 1,1,0 =diag(1,1,0)A重要性质：相差一个正负号的情况下=A=diag 1,1,0 A=diag 1,1,0 AA不考虑符号、尺度=本质矩阵分解=-=diag 1,1,0-=diag 1,1,0-本质矩阵分解=diag 1,1,0 A=diag 1,1,0(A)=-=diag 1,1,0-=diag 1,1,0-本质矩阵分解=diag(1,1,0)ASVD分解=本质矩阵分解=diag 1,1,0 A=diag 1,1,0(A)=diag(1,1,0)ASVD分解比较=-=diag 1,1,0-=diag 1,1,0-本质矩阵分解=diag 1,1,0 A=diag 1,1,0(A)=diag(1,1,0)ASVD分解比较A=A=-=diag 1,1,0-=diag 1,1,0-本质矩阵分解=diag 1,1,0 A=diag 1,1,0(A)=diag(1,1,0)ASVD分解比较A=A=AA=-=diag 1,1,0-=diag 1,1,0-本质矩阵分解=diag 1,1,0 A=diag 1,1,0(A)=diag(1,1,0)ASVD分解比较A=A=AA=-=diag 1,1,0-=diag 1,1,0-=A同理：=diag(1,1,0)-注意:的这个因式分解只保证了矩阵 A或 AA是正交的。其为旋转矩阵还需确保行列式的值为正：=Aor AA=det AA或(det AA)AA本质矩阵分解=A=0T=H(的第三列)本质矩阵分解四种潜在,对：l 选择一个点三角化，正确的一组解能保证该点在两个摄像机的z坐标均为正。l 对多个点进行三角化，选择在两个摄像机系下z坐标均为正的个数最多的那组R、T。（更鲁棒）=det-=.=det-=.=det-=.=(det-)-=.（图片来自于 Hartley and Zisserman 书第 260 页）本质矩阵分解（总结）=diag(1,1,0)A步骤1：SVD分解T=H=010100001=det AA或(det AA)AA步骤2：步骤3：步骤4：通过重建单个或多个点找出正确解=det-=.=det-=.=det-=.=(det-)-=.求解求解:1.求解基础矩阵F2.利用F与摄像机内参数求解本质矩阵E3.分解本质矩阵获得R与T4.三角化求解三维点坐标欧式结构恢复（2视图）%$=%!=%0!&$=&!=&!问题问题:=&%归一化八点法=argmin+!,!+(#,#)、#=1,例子：仅凭下图能否估计场景的绝对尺度？欧式结构恢复歧义 例子：仅凭下图能否估计场景的绝对尺度？欧式结构恢复歧义显然不能！欧式结构恢复歧义 例子：仅凭下图能否估计场景的绝对尺度？需要其他先验信息！恢复出来的欧式结构与真实场景之间相差一个相似变换（旋转，平移，缩放）欧式结构恢复歧义Similarity 恢复出来的欧式结构与真实场景之间相差一个相似变换（旋转，平移，缩放）恢复的场景与真实场景之间仅存在相似变换的重构称为度量重构度量重构欧式结构恢复歧义Similarity欧式结构恢复歧义R.Hartley and A.Zisserman,Multiple View Geometry in Computer Vision,2nd edition,2003=Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用放大率透视仿射=NOH=NOH=1=NOHP=(NH,OH)A=NOH=OHON0NH1=NOH=NO0001P=(N,O)A=1=P+P=仿射摄像机.=1=1,；=1,且仿射结构恢复问题QR=ST+S图像个数3D点个数问题：已知n个三维点=1,在张图像中的对应点的像素坐标)图像1图像i)=)01其中，),)组成了第i张图片对应的仿射摄像机的投影矩阵=1,；=1,且仿射结构恢复问题QR=ST+S图像个数3D点个数问题：已知n个三维点=1,在张图像中的对应点的像素坐标)图像1图像i)=)01其中，),)组成了第i张图片对应的仿射摄像机的投影矩阵问题：公式中各个元素的维度？=1,；=1,且仿射结构恢复问题QR=ST+S图像个数3D点个数求解：n个三维点=1,的坐标 m个仿射摄像机的投影矩阵)与)(=1,)问题：已知n个三维点=1,在张图像中的对应点的像素坐标)图像1图像i)=)01其中，),)组成了第i张图片对应的仿射摄像机的投影矩阵两种方法：-代数方法-因式分解法仿射结构恢复问题两种方法：-代数方法-因式分解法仿射结构恢复问题 数据中心化 因式分解中心化：减去图像点的质心:!=!)=1X/0!1)/数据中心化#$=!+图像1 S图像i中心化：减去图像点的质心:!=!)=1X/0!1)/数据中心化#$=!+图像1 S图像i:!=!1?()%*(=!+1?()%*(1?()%*中心化：减去图像点的质心:!=!)=1X/0!1)/数据中心化#$=!+Y图像1 S图像i:!=!1?()%*(=!+1?()%*(1?()%*=)1X/0!1/=)Y=)Z中心化：减去图像点的质心:!=!)=1X/0!1)/数据中心化#$=!+Y图像1 S图像i:!=!1?()%*(=!+1?()%*(1?()%*=)1X/0!1/=)Y=)Z如果3D点的质心 世界参考系中心中心化：减去图像点的质心:!=!)=1X/0!1)/数据中心化#$=!+Y图像1 S图像i:!=!1?()%*(=!+1?()%*(1?()%*=)1X/0!1/=)Y=)Z如果3D点的质心 世界坐标系的中心K ST=SLT=ST(2)每个K ST是一个21向量!=K NNK NOK ONK OOK NK OK NK OK 因式分解把去均值以后的个测量值写成矩阵的形式:=(77(75(57(55(7(5(7A(5A(A=7575A摄像机(23)点(3n)(2)MSS是 23 维，T是 31 维测量矩阵 D=MS 秩为3（它是 23 矩阵和 3n 矩阵的乘积）因式分解2m n 维的数据(测量值)矩阵:2m3测量测量D=运动运动M结构结构SnD=MSn3因式分解怎么分解D?通过计算D的奇异值分解！=2mnnnnnDUWVT因式分解=2mnnnnnDUWVT因式分解3333由于 rank(D)=3,理想情况下这里只有三个非零的奇异值 1,2 和 3其中H=N000O000H.-=2mnD因式分解3333.-=2mnD因式分解3333.-M=运动(摄像机)=S =结构仿射结构恢复问题计算步骤：1.创建一个 2m n 维的数据(测量值)矩阵D2.分解矩阵=，=及=求解：n个三维点=1,的坐标 m个投影矩阵)（即)与)）(=1,)问题：已知n个三维点=1,在张图像中的对应点的像素坐标)=2mnD问题：这样分解可以吗？3333.-=运动？=结构？=DMS仿射结构恢复歧义 分解不唯一。通过以下变换可以得到相同的D:M*=MH S*=H-1S其中 H 是任意可逆的33矩阵 必须利用其他约束条件来解决歧义=DMSHH-1M*S*仿射结构恢复歧义S*=H-1SA*=AHA*=AHAAS仿射结构恢复歧义仿射结构恢复歧义R.Hartley and A.Zisserman,Multiple View Geometry in Computer Vision,2nd edition,2003=仿射结构恢复问题计算步骤：1.创建一个 2m n 维的数据(测量值)矩阵D2.分解矩阵=，=及=求解：n个三维点=1,的坐标 m个投影矩阵)（即)与)）(=1,)问题：已知n个三维点=1,在张图像中的对应点的像素坐标)问题：给定m个相机，n个三维点，我们有多少个等式，多少个未知量？仿射结构恢复问题计算步骤：1.创建一个 2m n 维的数据(测量值)矩阵D2.分解矩阵=，=及=求解：n个三维点=1,的坐标 m个投影矩阵)（即)与)）(=1,)问题：已知n个三维点=1,在张图像中的对应点的像素坐标)问题：给定m个相机，n个三维点，我们有多少个等式，多少个未知量？回答：2mn个等式，8m+3n-8个未知量Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用放大率透视仿射=NOH=NOHP=(NH,OH)A=NOH=OHON0NH1=NOH=NO0001P=(N,O)A=1=P+P=透视摄像机=1=NOH=NNNONHONOOOHHNHOHHNO1问题：已知n个三维点=1,在张图像中的对应点的像素坐标)；透视结构恢复问题且=1,;=1,QR=ST图像个数3D点个数其中，)为第i张图片对应的摄像机的投影矩阵!#$.问题：已知n个三维点=1,在张图像中的对应点的像素坐标)；透视结构恢复问题且=1,;=1,QR=ST图像个数3D点个数其中，)为第i张图片对应的摄像机的投影矩阵!#$.求解：求解：n个三维点=1,的坐标;m个摄像机投影矩阵)(=1,)。!=!Projective透视结构恢复歧义#=$%!=!歧义由任意可逆44变换表示GProjectiveHG=HG=(HI7)(G)=透视结构恢复歧义#=$%SaN=透视结构恢复歧义R.Hartley and A.Zisserman,Multiple View Geometry in Computer Vision,2nd edition,2003 代数方法(通过基础矩阵)因式分解法(通过SVD)在相差一个44的可逆变换的情况下恢复摄像机运动与场景结构 捆绑调整透视结构恢复方法 代数方法(通过基础矩阵)因式分解法(通过SVD)捆绑调整透视结构恢复方法在相差一个44的可逆变换的情况下恢复摄像机运动与场景结构代数方法(两视图情况)!#NR=NTOR=OT1.求解基础矩阵 F 归一化八点法2.利用 F 估计摄像机矩阵F N,O3.三角化计算三维点坐标代数方法(两视图情况)!#NR=NTOR=OT!=argmin,%!,%!+(&!,&!)1.求解基础矩阵 F 归一化八点法2.利用 F 估计摄像机矩阵F N,O3.三角化计算三维点坐标代数方法(两视图情况)!#NR=NTOR=OT!=argmin,%!,%!+(&!,&!)!#NR=NTOR=OT=1,3D点个数由于透视歧义存在，我们总是可以找到一个可逆矩阵H，使得：NaN=0OaN=利用 F 估计摄像机矩阵 表示表示3D点 将和-分别称为摄像机1和2的对应观测值利用 F 估计摄像机矩阵cd!=!4!=0 d#=#4!=i=N=NaN=0=O=OaN=-=R=R%R&R.1=0R%R&R.1+=0R+=+表示表示3D点 将和-分别称为摄像机1和2的对应观测值利用 F 估计摄像机矩阵cd!=!4!=0 d#=#4!=i=N=NaN=0=O=OaN=-=R=R%R&R.1=0R%R&R.1+=0R+=+表示表示3D点 将和-分别称为摄像机1和2的对应观测值-=+=U-=-U =0-=0-=利用 F 估计摄像机矩阵cd!=!4!=0 d#=#4!=i=N=NaN=0=O=OaN=-=R=R%R&R.1=0R%R&R.1+=0R+=+表示表示3D点 将和-分别称为摄像机1和2的对应观测值-=+=U-=-U =0-=0-=利用 F 估计摄像机矩阵cd!=!4!=0 d#=#4!=i=N=NaN=0=O=OaN=j=基本矩阵!-=R=R%R&R.1=0R%R&R.1+=0R+=+表示表示3D点 将和-分别称为摄像机1和2的对应观测值-=+=U-=-U =0-=0-=利用 F 估计摄像机矩阵cd!=!4!=0 d#=#4!=i=N=NaN=0=O=OaN=j=基本矩阵!利用 F 估计摄像机矩阵=6=0已知：1.计算b:考虑乘积利用 F 估计摄像机矩阵=6=0已知：U =U =U =U =01.计算b:考虑乘积利用 F 估计摄像机矩阵=6=0已知：U =U =U =U =0-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=0已知：U =U =U =U =0-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:-=已知：U =U =U =U =0-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:-=+=+U =-=已知：U =U =U =U =0-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:因此，=-=-=+=+U =-=已知：U =U =U =U =0-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:因此，=-=-=+=+U =-=已知：U =U =U =U =0cN=0 cO=摄像机矩阵：-=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:因此，=-=-=+=+U =-=已知：问题：这里是什么？U =U =U =U =0cN=0 cO=摄像机矩阵：-=0O1O2pPpee=-是-对应的极线-=是对应的极线=0，-=0是奇异的(秩2)的DOF为7ll极几何约束#=01.计算b:考虑乘积 为矩阵最小奇异值的右奇异向量，且=1利用 F 估计摄像机矩阵=6=02.计算A A:定义：验证-等于:因此，=-=-=+=+U =-=已知：问题：这里是什么？回答：是一个极点U =U =U =U =0cN=0 cO=摄像机矩阵：-=01.求解基础矩阵 F 归一化八点法2.利用 F 估计摄像机矩阵3.三角化计算三维点坐标代数方法(两视图情况)!#NR=NTOR=OT!=argmin,%!,%!+(&!,&!)c%=0 c&=分别对每一个图像对l与m计算运动与结构l与md,d,e代数方法(N 视图情况)!#.#.!.增量法！增量法！代数方法(通过基础矩阵)因式分解法(通过SVD)捆绑调整透视结构恢复方法因式分解法假定所有点都是可见的，所以下述场合不可用：存在遮挡 建立对应点关系失败代数法应用于2视图重建代数法与分解法的局限性能够用于构建观测矩阵D的点少，重建点数少！易出现误差累积！=%!%!#%#!%#%&!%&#%!%#%&恢复结构和运动的非线性方法O2重构点O1Om真实值,=eSnNeTnN(ST,ST)O捆绑调整$!#!#$最小化重投影误差：.-牛顿法 与 列文伯格-马夸尔特法（L-M方法）参数,=eSnNeTnN(ST,ST)O测量值捆绑调整非线性最小化问题-牛顿法 与 列文伯格-马夸尔特法（L-M方法）参数,=eSnNeTnN(ST,ST)O测量值捆绑调整非线性最小化问题优势 同时处理大量视图 处理丢失的数据-牛顿法 与 列文伯格-马夸尔特法（L-M方法）参数,=eSnNeTnN(ST,ST)O测量值捆绑调整非线性最小化问题优势 同时处理大量视图 处理丢失的数据局限性 大量参数的最小化问题 需要良好的初始条件-牛顿法 与 列文伯格-马夸尔特法（L-M方法）参数,=eSnNeTnN(ST,ST)O测量值捆绑调整非线性最小化问题优势 同时处理大量视图 处理丢失的数据局限性 大量参数的最小化问题 需要良好的初始条件实际操作：常用作SFM的最后一步，分解或代数方法可作为优化问题的初始解Lecture 6多视图几何 运动恢复结构问题 欧式结构恢复 仿射结构恢复 透视结构恢复 应用Courtesy of Oxford Visual Geometry GroupLevoy et al.,00Hartley&Zisserman,00 Dellaert et al.,00 Rusinkiewic et al.,02 Nistr,04Brown&Lowe,04 Schindler et al,04 Lourakis&Argyros,04 Colombo et al.05Golparvar-Fard,et al.JAEI 10Pandey et al.IFAC,2010 Pandey et al.ICRA 2011 Microsofts PhotoSynth Snavely et al.,06-08 Schindler et al.,08 Agarwal et al.,09Frahm et al.,10Lucas&Kanade,81 Chen&Medioni,92 Debevec et al.,96 Levoy&Hanrahan,96 Fitzgibbon&Zisserman,98Triggs et al.,99 Pollefeys et al.,99 Kutulakos&Seitz,99运动恢复结构问题建筑场景的增量重构Initial pair 2168&Complete Set 62,323 points,160 imagesGolparvar-Fard.Pena-Mora,Savarese 200863重构场景与摄像机位姿Noah Snavely,Steven M.Seitz,Richard Szeliski,Photo tourism:Exploring photo collections in 3D,ACM Transactions on Graphics(SIGGRAPH Proceedings),2006,结果与应用Lecture 6多视图几何 运动恢复结构问题（完）欧式结构恢复（完）仿射结构恢复（完）透视结构恢复（完）应用（完）
