第九章-立体视觉ppt课件

第九章第九章 立体视觉立体视觉周文晖计算机学院第九章 立体视觉周文晖D.Marr视觉计算理论：计算机视觉的第三阶段（后期阶段）是获得物体的三维模型表征。如何从图像中自动计算三维几何？如何从图像中自动计算三维几何？如何从图像中自动计算三维几何？如何从图像中自动计算三维几何？换句话说：图像中提供了哪些关于三维信息的线索？图像中提供了哪些关于三维信息的线索？图像中提供了哪些关于三维信息的线索？图像中提供了哪些关于三维信息的线索？从图像中恢复三维从图像中恢复三维D.Marr视觉计算理论：计算机视觉的第三阶段（后期阶段）令人惊讶的令人惊讶的3D3D壁画艺术壁画艺术包含了哪些深度线索呢？包含了哪些深度线索呢？令人惊讶的3D壁画艺术包含了哪些深度线索呢？阴影阴影阴影阴影三维视觉线索三维视觉线索Merle Norman Cosmetics,Los Angeles阴影三维视觉线索Merle Norman Cosmetics阴影 纹理纹理纹理纹理三维视觉线索三维视觉线索The Visual Cliff,by William Vandivert,1960阴影三维视觉线索The Visual Cliff,by W阴影纹理 遮挡遮挡遮挡遮挡三维视觉线索三维视觉线索From The Art of Photography,Canon阴影三维视觉线索From The Art of Photog阴影纹理遮挡 运动运动运动运动三维视觉线索三维视觉线索阴影三维视觉线索阴影纹理遮挡运动 模糊模糊模糊模糊三维视觉线索三维视觉线索阴影三维视觉线索阴影纹理遮挡运动模糊三维视觉线索三维视觉线索其他线索高光轮廓对焦.Shape From XShape From XX=X=阴影、纹理、遮挡、运动、阴影、纹理、遮挡、运动、.阴影三维视觉线索其他线索Shape From XTwo is better than one?Two is better than one?红蓝眼镜偏振光眼镜3D3D电影和电影和3D3D显示显示红蓝眼镜3D电影和3D显示快门眼镜3D3D电影和电影和3D3D显示显示快门眼镜3D电影和3D显示裸眼立体显示系统裸眼立体显示系统裸眼立体显示系统3D3D拍摄拍摄LG Optimus 3D3D拍摄LG Optimus 3D3D3D感知的过程感知的过程Human-Eye Separation(6.5cm)Left 2D ImageRight 2D ImageBrain3D View3D感知的过程Human-Eye Separation(6立体图像对的显示立体图像对的显示http:/ 2D ImageRight 2D ImageBrain3D View采用一对像机代替人眼计算立体视觉Left 2D ImageRight 2D Im计算立体视觉计算立体视觉Left 2D ImageRight 2D ImageBrain3D ViewDisplacement(Stereo Baseline)采用一对像机代替人眼计算立体视觉Left 2D ImageRight 2D Im计算立体视觉计算立体视觉Displacement(Stereo Baseline)Left 2D ImageRight 2D ImageComputer3D View计算立体视觉Displacement(Stereo Bas计算立体视觉计算立体视觉Displacement(Stereo Baseline)Left 2D ImageRight 2D ImageComputer3D View计算立体视觉Displacement(Stereo Bas9.19.1 双目立体视觉几何双目立体视觉几何9.1 双目立体视觉几何光线OP上的任意点都投影在图像平面的p点上。深度感知存在歧义单目视觉单目视觉光线OP上的任意点都投影在图像平面的p点上。单目视觉第二个像机可解决单目存在的深度歧义可通过三角测量获得深度双目视觉双目视觉第二个像机可解决单目存在的深度歧义双目视觉两直线相交于一点三角测量三角测量plpr问题：如何根据问题：如何根据 pl 和和 pr 点获取深度？点获取深度？三角测量plpr问题：如何根据 pl 和 pr 点获取深度？考虑左、右像机光轴平行的特殊情况平行光轴立体视觉系统平行光轴立体视觉系统P(X,Y,Z)pl(xl,yl)光心 Olf=焦距像平面左摄像机左摄像机B=基线深度深度 Zf=焦距光心 Orpr(xr,yr)像平面右摄像机右摄像机考虑左、右像机光轴平行的特殊情况平行光轴立体视觉系统P(X,平行光轴立体视觉系统平行光轴立体视觉系统xzfxCCXBfd d =x x -x x 称为视差称为视差称为视差称为视差思考：该视差公式隐含了什么条件？思考：该视差公式隐含了什么条件？平行光轴立体视觉系统xzfxCCXBfd=x-x通常的立体视觉系统（包括人类视觉系统）都是采用会聚方式。通常的立体视觉系统通常的立体视觉系统field of viewof stereoone pixeluncertainty ofscenepointOptical axes of the two cameras need not be parallel通常的立体视觉系统（包括人类视觉系统）都是采用会聚方式。通常平行光轴立体视觉系统 短基线短基线短基线短基线较大的公共视野区域较大的公共视野区域深度误差（不确定区域）较大深度误差（不确定区域）较大几种立体视觉系统比较几种立体视觉系统比较平行光轴立体视觉系统几种立体视觉系统比较平行光轴立体视觉系统 短基线短基线短基线短基线较大的公共视野区域较大的公共视野区域深度误差（不确定区域）较大深度误差（不确定区域）较大 长基线长基线长基线长基线公共视野区域较小公共视野区域较小深度误差（不确定区域）较小深度误差（不确定区域）较小几种立体视觉系统比较几种立体视觉系统比较平行光轴立体视觉系统几种立体视觉系统比较平行光轴立体视觉系统 短基线短基线短基线短基线较大的公共视野区域较大的公共视野区域深度误差（不确定区域）较大深度误差（不确定区域）较大 长基线长基线长基线长基线公共视野区域较小公共视野区域较小深度误差（不确定区域）较小深度误差（不确定区域）较小 会聚光轴立体视觉系统会聚光轴立体视觉系统会聚光轴立体视觉系统会聚光轴立体视觉系统会聚角度为会聚角度为 公共视野区域大公共视野区域大几种立体视觉系统比较几种立体视觉系统比较可以得到的结论是可以得到的结论是？1 1、基线或聚散度增加导致视野范围减少、基线或聚散度增加导致视野范围减少2 2、基线或聚散度影响三维重建的精度、基线或聚散度影响三维重建的精度平行光轴立体视觉系统几种立体视觉系统比较可以得到的结论是？会聚立体视觉系统能否利会聚立体视觉系统能否利会聚立体视觉系统能否利会聚立体视觉系统能否利 用之前的推导结果？用之前的推导结果？用之前的推导结果？用之前的推导结果？立体视觉中重要的几何约束：极线约束极线约束极线约束极线约束会聚立体视觉系统会聚立体视觉系统会聚立体视觉系统能否利会聚立体视觉系统场景点P在视图中的投影点为像素点p，则在视图 中的投影点p必定满足双目几何约束：必定位于图像平面 与OPO平面的交线上。极线约束极线约束场景点P在视图中的投影点为像素点p，则在视图 中的投影像素点p和p是场景点P在两视图上的投影。像素点p和p称为对应点或匹配点。极线约束极线约束 极平面极平面极平面极平面极点极线基线极点极线极线约束：对应点必定在极线上！极线约束：对应点必定在极线上！像素点p和p是场景点P在两视图上的投影。极线约束 极平面极基线（Baseline）：连接像机中心的直线极点（Epipole）：基线与图像平面的交点极平面（Epipolar plane）：基线和场景点组成的平面极线（Epipolar line）：极平面与图像平面的交线所有的极线相交于极点极线几何术语定义极线几何术语定义思考：极线约束的意义或用处？思考：极线约束的意义或用处？基线（Baseline）：连接像机中心的直线极线几何术语定极线约束例极线约束例极线约束例极线约束例极线约束例极线约束例所有极线水平极点在基线B上的无穷远处左、右图对应极线在同一水平。对应像素点只存在水平坐标差异，不存在垂直坐标差异。即仅有水平视差，垂直视差为0。视视差定差定差定差定义义：d d =x x -x x 平行光轴的极线约束平行光轴的极线约束xzfxCCXBf所有极线水平平行光轴的极线约束xzfxCCXBf 光轴会聚的立体视觉系统光轴会聚的立体视觉系统光轴会聚的立体视觉系统光轴会聚的立体视觉系统能否利用平行光轴的推导能否利用平行光轴的推导能否利用平行光轴的推导能否利用平行光轴的推导结果？结果？结果？结果？立体图像校正将左、右图像平面都投影到平行于基线的公共平面。变换后的对应极线处于同一水平线（共线）。光轴会聚的立体视觉系统光轴会聚的立体视觉系统光轴会聚的立体视觉系统能否利用平行光轴的推导结果？光轴会聚的9.29.2 双目立体图像校正双目立体图像校正9.2 双目立体图像校正校正的目的：输入图像通过透视变换使得外极线水平，且共线。畸变校正，使得成像过程符合小孔成像模型。立体图像校正的目的立体图像校正的目的plprPOlOrXlXrPlPrZlYlZrYrT校正的目的：立体图像校正的目的plprPOlOrXlXrPl校正步骤：将左右图像平面都投影到平行于基线的公共平面。图像行像素重采样。最小化图像畸变。Zhang and Loop,MSR-TR-99-21立体图像校正步骤立体图像校正步骤校正步骤：立体图像校正步骤 立体视觉系统的参数立体视觉系统的参数立体视觉系统的参数立体视觉系统的参数 内部参数内部参数内部参数内部参数对于每个像机，其图像坐标系与像机坐标系间的关系。焦距、光心、畸变系数 外部参数外部参数外部参数外部参数两像机间的相对位置和方向。旋转矩阵R R和平移矢量T T立体图像校正立体图像校正（由双目像机标定获得）（由双目像机标定获得）（由双目像机标定获得）（由双目像机标定获得）plprPOlOrXlXrPlPrflfrZlYlZrYrR,T立体视觉系统的参数立体图像校正（由双目像机标定获得）plpr符号定义：场景点P在左右像机坐标系下的坐标为 Pl=(Xl,Yl,Zl),Pr=(Xr,Yr,Zr)。外部参数平移矢量 T=(Or-Ol)旋转矩阵 R Pr =R(Pl-T)场景点P在左右图像平面上投影pl=(xl,yl,zl),pr=(xr,yr,xr)。对于所有的像素点有立体图像校正立体图像校正zl=fl;zr=frplprPOlOrXlXrPlPrflfrZlYlZrYrR,T符号定义：立体图像校正zl=fl;zr=frplp同时旋转左右像机使得它们具有相同的X轴。定义左像机的旋转矩阵为Rrect。右像机旋转矩阵为 RrectR立体图像校正后 R RrectrectR R？立体图像校正立体图像校正plprPOlOrXlXrPlPrZlYlZrYrT同时旋转左右像机使得它们具有相同的X轴。RrectR？由立体图像标定有，立体图像校正后，有校正目标：即：可得由于R为正交矩阵，有立体图像校正立体图像校正由立体图像标定有，立体图像校正立体图像校正实例立体图像校正实例立体图像校正实例立体图像校正实例立体图像校正实例Stereo pairs before rectification Stereo pairs after rectification 立体图像校正实例Stereo pairs before re立立体体图图像像校校正正实实例例UnrectifiedRectified立体图像校正实例UnrectifiedRectified平行光轴的双目立体视觉立体匹配立体匹配对应点搜索对应点搜索xzfxCCXBf还有问题吗？还有问题吗？还有问题吗？还有问题吗？问题：如何确定对应像素点？问题：如何确定对应像素点？平行光轴的双目立体视觉立体匹配对应点搜索xzfxCC9.39.3 立体匹配立体匹配9.3 立体匹配立体匹配的过程：为左图像的每个像素点(xl,yl)，在右图像中搜索对应点。立体匹配立体匹配对应点搜索对应点搜索(xl,yl)LEFT IMAGELEFT IMAGE问题：在右图像中如何搜索？问题：在右图像中如何搜索？立体匹配的过程：为左图像的每个像素点(xl,yl)，在右图极线约束的意义：将对应点搜索由原来的二维平面上搜索变为在极线上的一维搜索。对于校正后的立体图像：在图像水平方向搜索立体匹配立体匹配对应点搜索对应点搜索极线约束的意义：立体匹配对应点搜索比较右图对应极线上的每个像素，寻找最相似的像素作为对应点。即在右图同一水平方向上的视差范围内视差范围内视差范围内视差范围内搜索。立体匹配立体匹配对应点搜索对应点搜索(xl,yl)RIGHT IMAGERIGHT IMAGE相似度值最大问题问题1 1：以左图为基准图，视差搜索：以左图为基准图，视差搜索 范围如何确定？范围如何确定？问题问题2 2：相似性测度如何选择？：相似性测度如何选择？比较右图对应极线上的每个像素，寻找最相似的像素作为对应点。即匹配基元：参与立体匹配，计算相似测度的基本单元 常用的匹配基元：常用的匹配基元：常用的匹配基元：常用的匹配基元：像素像素像素像素单个像素存在相似性歧义需结合一行或整幅图像的所有像素同时完成匹配 局部窗口区域局部窗口区域局部窗口区域局部窗口区域具有较好的局部独特性隐含假定：窗口内所有像素应能表征中心像素 特征特征特征特征具有较好的独特性稀疏且不均匀分布立体匹配的基元立体匹配的基元匹配基元：参与立体匹配，计算相似测度的基本单元立体匹配的基元根据立体匹配过程中涉及的像素范围，可分为：局部立体匹配局部立体匹配局部立体匹配局部立体匹配通常以基于局部窗口的立体匹配方法为主。匹配基元：局部窗口 全局立体匹配全局立体匹配全局立体匹配全局立体匹配匹配过程中，求解一行或整幅图像中所有像素的相似测度和最大/最小。匹配基元：像素立体匹配分类立体匹配分类根据立体匹配过程中涉及的像素范围，可分为：立体匹配分类根据立体匹配过程中采用的匹配基元，可分为：致密匹配致密匹配致密匹配致密匹配搜索每个像素的对应点，构建致密视差图匹配基元为像素 稀疏匹配稀疏匹配稀疏匹配稀疏匹配仅为特征搜索对应点，构建稀疏的视差图.匹配基元为特征。立体匹配分类立体匹配分类根据立体匹配过程中采用的匹配基元，可分为：立体匹配分类9.3.19.3.1 基于局部窗口的立体匹配基于局部窗口的立体匹配9.3.1 基于局部窗口的立体匹配以基准图的待匹配点为中心创建一个窗口，以在对准图中对应外极线上某一像素点为中心创建同样大小的滑动窗口，窗口内相邻像素的亮度值分布来表征中心像素。比较对准图中每个滑动窗口内容与基准图参考窗口内容的相似程度。基于局部窗口的对应性搜索基于局部窗口的对应性搜索以基准图的待匹配点为中心创建一个窗口，以在对准图中对应外极线基于局部窗口的对应性搜索基于局部窗口的对应性搜索Matching costdisparityLeftRightscanline问题：采用哪种相似性测度？问题：采用哪种相似性测度？对于已校正的双目立体图像对，则在扫描线上搜索。基于局部窗口的对应性搜索Matching costdispa常用的相似性测度包括：距离测度：L1距离、L2距离、.相关系数：NCC、ZNCC非参数化测度：RANK、Census相似性测度相似性测度常用的相似性测度包括：相似性测度像素亮度差的绝对值和(Sum of Absolute Differences,SAD)：像素亮度差的绝对平方和(Sum of Squared Differences,SSD)：距离测度距离测度问题：距离测度越小，相似性越问题：距离测度越小，相似性越？像素亮度差的绝对值和(Sum of Absolute Dif距离测度距离测度LeftRightscanlineSSD距离测度LeftRightscanlineSSD归一化互相关(Normalized Cross-Correlation,NCC)相关系数相关系数问题：相关系数越小，相似性越问题：相关系数越小，相似性越？归一化互相关(Normalized Cross-Correl相关系数相关系数LeftRightscanlineNCC相关系数LeftRightscanlineNCCRANK：非参数化测度非参数化测度统计匹配窗口内像素亮度值小于中心像素的个数。RANK：非参数化测度统计匹配窗口内像素亮度值小于中心像素的Census：非参数化测度非参数化测度是将匹配窗口内像素按一定顺序映射为二进制位串，如像素亮度值大于中心像素则映射为1，反之为0。然后比较左、右匹配窗口二进制位串的汉明距离。问题：问题：RANKRANK和和CensusCensus区别？区别？Census：非参数化测度是将匹配窗口内像素按一定顺序映射为ground truth立体匹配测试图立体匹配测试图问题：视差图灰度级代表的含义？问题：视差图灰度级代表的含义？ground truth立体匹配测试图问题：视差图灰度级代表局局部部窗窗口口立立体体匹匹配配结结果果(a)SAD 匹配结果(b)ZSAD 匹配结果(c)SSD 匹配结果(d)ZSSD 匹配结果(e)NCC 匹配结果(f)ZNCC 匹配结果(g)Rank 匹配结果(h)Census 匹配结果局部窗口立体匹配结果(a)SAD 匹配结果(b)ZSfor(j=line_start;j=line_end;j+)for(i=row_start;I=row_end;i+)/遍历基准图像素 for(d=dpXMin;d=dpXMax;d+)/视差搜索 cov_tmp=0.0;num=0;for(n=j-vradius;n=j+m_vradius;n+)for (m=i-hradius;m 0)?subtmp:-subtmp;区域立体匹配的实现区域立体匹配的实现for(j=line_start;j=lin特点：特点：以窗口内像素亮度值的分布特性表征中心像素以窗口内像素亮度值的分布特性表征中心像素以窗口内像素亮度值的分布特性表征中心像素以窗口内像素亮度值的分布特性表征中心像素单个像素在亮度、色彩上存在歧义单个像素在亮度、色彩上存在歧义 隐含条件：匹配窗口内视差平滑隐含条件：匹配窗口内视差平滑隐含条件：匹配窗口内视差平滑隐含条件：匹配窗口内视差平滑匹配窗口内像素应具有相同的视差值。因此，当匹配窗匹配窗口内像素应具有相同的视差值。因此，当匹配窗口跨越深度不连续区域时就会因违背假设而引起误配。口跨越深度不连续区域时就会因违背假设而引起误配。匹配窗口大小的选择匹配窗口大小的选择匹配窗口大小的选择匹配窗口大小的选择问题问题问题问题区域匹配的特点区域匹配的特点特点：区域匹配的特点 5x5匹配窗口 7x7匹配窗口 11x11匹配窗口 19x19匹配窗口 匹配窗口大小的影响匹配窗口大小的影响匹配窗口变小细节丰富噪声大视差边缘处好匹配窗口变大视差更平滑噪声小视差边缘处差思考：试解释原因？思考：试解释原因？5x5匹配窗口 匹配窗口大小的影响匹配窗口大小的影响Input Ground truth7x7 windowSharp edges are blurred!Adaptive windowSharp edges and less noise3x3 windowToo noisy!匹配窗口大小的影响Input Ground truth7优点：容易实现，只需要考虑局部窗口区域对纹理丰富的区域具有较好匹配性能速度快，只需考虑有限像素易于硬件实现，易于流水线实现缺点：视差不连续、遮挡或边缘区域无法正确估计视差对重复性纹理、无/弱纹理区域无法准确估计视差局部窗口匹配的优缺点局部窗口匹配的优缺点优点：局部窗口匹配的优缺点即使在测试的标准图像中匹配也并非容易重复场景无纹理区域遮挡立体匹配面临的挑战立体匹配面临的挑战右图中右图中右图中右图中B B B B、D D D D被遮挡被遮挡被遮挡被遮挡即使在测试的标准图像中匹配也并非容易立体匹配面临的挑战右图中场景点投影到两幅图像中并不总是一致的像机的影响图像噪声、不同增益、不同对比度等等.视点的影响透视畸变遮挡镜面反射尺度、旋转变化立体匹配面临的挑战立体匹配面临的挑战场景点投影到两幅图像中并不总是一致的立体匹配面临的挑战立立体体匹匹配配面面临临的的挑挑战战立体匹配面临的挑战为克服匹配过程中存在的歧义性，需采用一些常用的匹配约束：极线约束极线约束极线约束极线约束：匹配点必须在极线上 相似性约束相似性约束相似性约束相似性约束：左、右图像的匹配点应具有相似的亮度或颜色。即，假定目标表面符合朗伯漫反射表面。视差范围约束：视差范围约束：视差范围约束：视差范围约束：仅在视差搜索内搜索。思考：视差搜索范围如何确定思考：视差搜索范围如何确定？立体匹配约束立体匹配约束为克服匹配过程中存在的歧义性，需采用一些常用的匹配约束：立体 唯一性约束唯一性约束唯一性约束唯一性约束：一幅图像中的一个像素，在另一幅 图像中最多只有一个对应点像素。立体匹配约束立体匹配约束违反唯一性约束了吗违反唯一性约束了吗违反唯一性约束了吗违反唯一性约束了吗?唯一性约束：一幅图像中的一个像素，在另一幅 顺序约束顺序约束顺序约束顺序约束/单调性约束单调性约束单调性约束单调性约束：若参考图中A点在B点的左边，则另一幅图像中A点匹配点也在B点匹配点的左边。该约束对细小物体不成立该约束对细小物体不成立立体匹配约束立体匹配约束顺序约束/单调性约束：若参考图中A点在B点的左边，则平滑性约束平滑性约束/一致性约束：一致性约束：除了遮挡或视差本身不连续区域外，小邻域范围内视差值变化量应很小或相似。换言之视差曲面应是分段连续的。立体匹配约束立体匹配约束平滑性约束/一致性约束：除了遮挡或视差本身不连续区域外互对应约束：互对应约束：又称左右一致性，若以左图为基准图，左图上一像素点 pl 的搜索到右图上对应点像素为 pr；那么若以右图为基准图，像素 pr 的对应点也应该是左图上的像素点 pl。该约束常用于遮挡区的检测。立体匹配约束立体匹配约束pl pr 互对应约束：又称左右一致性，若以左图为基准图，左图上约束条件极线约束相似性约束视差范围约束唯一性约束顺序约束/单调性约束互对应约束立体匹配约束小结立体匹配约束小结在区域匹配过程中已实现应如何实现？应如何实现？应如何实现？应如何实现？区域匹配中各像素的对应性搜索相互独立的，而约束要求考虑相邻像素间的视差关系。思考：匹配约束如何实现？思考：匹配约束如何实现？约束条件立体匹配约束小结在区域匹配过程中已实现应如何实现？思9.3.29.3.2 全局立体匹配全局立体匹配9.3.2 全局立体匹配根据约束条件作用范围，可分为两大类：一维优化策略，基于动态规划一维优化策略，基于动态规划一维优化策略，基于动态规划一维优化策略，基于动态规划顺序约束和平滑约束优化极线上所有像素点极线上所有像素点的匹配代价。该问题可归结为路径规划问题，即寻找视差空间图的最小代价路径。二维优化策略，基于全局能量函数二维优化策略，基于全局能量函数二维优化策略，基于全局能量函数二维优化策略，基于全局能量函数根据贝叶斯理论及马尔可夫随机场理论，立体视觉问题可以转化为求解全局能量最小问题。全局能量函数为整幅图像所有像素点的匹配代价。全局立体匹配全局立体匹配根据约束条件作用范围，可分为两大类：全局立体匹配基于动态规划的匹配算法并不是孤立孤立孤立孤立地寻找每个像素点的匹配值。优化整条扫描线优化整条扫描线，使得该扫描线上所有像素的匹配代价和最小，并满足顺序和平滑约束。不同扫描线独立完成优化。基于动态规划的立体匹配方法基于动态规划的立体匹配方法左图像右图像pp+dp基于动态规划的匹配算法并不是孤立地寻找每个像素点的匹配值。基匹配过程中关注的是整个扫描线上的所有像素立体匹配约束立体匹配约束Left scanlineRight scanlineMatchMatchMatchLeft occlusionRight occlusion匹配过程中关注的是整个扫描线上的所有像素立体匹配约束Le三种情况：连 续匹配代价，满足顺序约束左遮挡无匹配代价右遮挡无匹配代价立体匹配约束立体匹配约束Left scanlineRight scanlineLeft Occluded PixelsRight occluded Pixels三种情况：立体匹配约束Left scanlineRight 动态规划在视差空间中生成一条最优路径。路径生成满足顺序约束遮挡、匹配搜索方向及其代价示意：视差空间视差空间correspondence要求：寻找匹配代价和最小的一条路径要求：寻找匹配代价和最小的一条路径要求：寻找匹配代价和最小的一条路径要求：寻找匹配代价和最小的一条路径Left Occluded PixelsLeft scanlineRight occluded PixelsRight scanlineStartEnd立体匹配问题转换为最优路径的搜索问题立体匹配问题转换为最优路径的搜索问题动态规划在视差空间中生成一条最优路径。视差空间corresp动态规划是求解连续决策（最优路径）问题的有效方法。总共有多少条路径？总共有多少条路径？动态规划动态规划123123123123i=1i=2i=3t=1t=2t=3t=T状态扫描行像素动态规划是求解连续决策（最优路径）问题的有效方法。动态规划1将整条扫描线匹配过程分解为多阶段决策过程。单个阶段决策的代价为：动态规划动态规划123123123i=1i=2i=3将整条扫描线匹配过程分解为多阶段决策过程。动态规划12312n阶赋值问题的最优理论（体现动态规划方法）：动态规划动态规划123123123此处最小化是全局此处最小化是全局此处最小化是全局此处最小化是全局概念还是局部概念概念还是局部概念概念还是局部概念概念还是局部概念?n阶赋值问题的最优理论（体现动态规划方法）：动态规划1231记录每个节点的父节点动态规划动态规划123123123WhyWhy？记录每个节点的父节点动态规划123123123Why？最优路径搜索的伪代码注：M(i,j)用于记录父节点基于动态规划的立体匹配实现基于动态规划的立体匹配实现correspondence含义？含义？含义？含义？匹配代价匹配代价匹配代价匹配代价左遮挡左遮挡左遮挡左遮挡右遮挡右遮挡右遮挡右遮挡最优路径搜索的伪代码基于动态规划的立体匹配实现corresp最优路径回溯伪代码基于动态规划的立体匹配实现基于动态规划的立体匹配实现遮挡跳过直到找到下一个匹配点最优路径回溯伪代码基于动态规划的立体匹配实现遮挡跳过直到优点优点:保证了一条扫描线上各像素点的优化匹配。缺点：缺点：缺少扫描线间的强制约束无法将水平方向和垂直方向的连续性约束有效融合。局部误差会着扫描线传播。视差结果图中有着很明显的横纹效应。动态规划方法的局限性动态规划方法的局限性优点:动态规划方法的局限性横纹效应明显动态规划的匹配结果动态规划的匹配结果横纹效应明显动态规划的匹配结果 如何评判立体匹配算法性能的优劣如何评判立体匹配算法性能的优劣?匹配质量匹配质量匹配质量匹配质量为每个像素在另一幅图像中寻找到最佳匹配。平滑性平滑性平滑性平滑性若两像素相邻，则它们的视差（通常）相近。二维优化策略二维优化策略思路：定义一个全局能量函数思路：定义一个全局能量函数,并求解该能量函数最小并求解该能量函数最小如何评判立体匹配算法性能的优劣?二维优化策略思路：定义一个全立体匹配的全局能量函数定义：全局能量函数全局能量函数数据项:匹配代价平滑项:平滑代价使得每个像素在另一幅图像中找到一个良好的匹配。相邻像素（通常）应具有相近的视差。立体匹配的全局能量函数定义：全局能量函数数据项:匹配代数据项：平滑项：全局能量函数全局能量函数所有像素的所有像素的匹配代价和匹配代价和4-connected neighborhood8-connected neighborhood邻域像素集邻域像素集数据项：全局能量函数所有像素的匹配代价和4-connecte平滑项：是邻域像素违反平滑性约束的惩罚项。常用模型函数：平滑项函数平滑项函数“Potts model”L1 distance平滑项：是邻域像素违反平滑性约束的惩罚项。平滑项函数“PotY.Boykov,O.Veksler,and R.Zabih,Fast Approximate Energy Minimization via Graph Cuts,PAMI 2001全局能量函数举例全局能量函数举例I1I2DW1(i)W2(i+D(i)D(i)data termsmoothness term(Potts Models)Y.Boykov,O.Veksler,and R.常用能量函数最小求解方法基于图的求解Graph Cuts基于概率的求解Belief Propagation（BP）全局能量函数最小化求解全局能量函数最小化求解常用能量函数最小求解方法全局能量函数最小化求解立立体体匹匹配配算算法法测测评评http:/vision.middlebury.edu/stereo/eval/立体匹配算法测评http:/vision.middlebu9.3.39.3.3 基于特征的立体匹配基于特征的立体匹配9.3.3 基于特征的立体匹配主要思想在左右两幅图像中寻找匹配特征常用特征有：边缘点线段角点基于特征的立体匹配基于特征的立体匹配主要思想基于特征的立体匹配匹配算法在立体图对中抽取特征定义相似度利用相似度和极线几何寻找匹配基于特征的立体匹配基于特征的立体匹配匹配算法基于特征的立体匹配相关匹配方法易于实现对纹理丰富的图像有良好匹配性能，反之误匹配较多可获得致密视差图（用于表面重建）当视点差异较大时，难以正确匹配，这是由于：光照方向发生变化违反了朗伯散射假定特征匹配方法运算速度比相关匹配方法快适用于易于提取特征点的场景获得稀疏视差图，适用于视觉导航等应用对亮度变化相对不敏感特征匹配和相关匹配比较特征匹配和相关匹配比较相关匹配方法特征匹配和相关匹配比较9.49.4 三维重建三维重建9.4 三维重建三维重建的几何关系三维重建的几何关系三维重建的几何关系基于立体视觉的三维地形重建基于立体视觉的三维地形重建基于立体视觉的三维地形重建基于立体视觉的三维地形重建基于立体视觉的三维地形重建基于立体视觉的三维地形重建仿真仿真月表月表环境环境双目双目三维三维重建重建仿真月表环境双目三维重建高分辨率双目三维重建高分辨率双目三维重建高分辨率双目三维重建对于大场景的三维重建，由于系统视场有限，需要对于大场景的三维重建，由于系统视场有限，需要对不同视角下的三维模型进行人工拼接。对不同视角下的三维模型进行人工拼接。三维拼接技术的实质是把在不同的局部坐标系中测三维拼接技术的实质是把在不同的局部坐标系中测量得到的有效数据点云进行坐标变换。量得到的有效数据点云进行坐标变换。双目像机三维场景拼接双目像机三维场景拼接对于大场景的三维重建，由于系统视场有限，需要对不同视角下的三输入图像必须有足够的特征信息前后帧之间应保证一定的重叠率，一般选取在6090为佳。尺度和旋转变化不易太大。双目像机三维场景拼接双目像机三维场景拼接输入图像必须有足够的特征信息双目像机三维场景拼接双目像机三维场景拼接：野外树坑双目像机三维场景拼接：野外树坑双目像机三维场景拼接：野外树坑单目像机三维重建单目像机三维重建三维测量三维测量三维建模三维建模场场景景点云点云pointcloud单目像机三维重建三维测量三维建模场景点云point单目像机三维重建单目像机三维重建单目像机三维重建S.Agarwal,N.Snavely and I.Simon,et al.Building Rome in a Day.in International Conference on Computer Vision.2009.Kyoto,Japan.J.Frahm,P.Georgel and D.Gallup,et al.Building Rome on a Cloudless Day.in 11th European Conference on Computer Vision.2010.Y.Furukawa,B.Curless and S.M.Seitz,et al.Towards Internet-Scale Multi-View Stereo.in IEEE Conference on Computer Vision and Pattern Recognition(CVPR).2010.VideoBuilding Rome in a DayBuilding Rome in a DayS.Agarwal,N.Snavely and I.加拿大物理学家博伊尔（Willard Boyle）和美国科学家史密斯（George E.Smith），因发明数码相机图像感应器“感光半导体电荷耦合器件”(CCD)，2009年10月连同“光纤之父”高锟，荣获诺贝尔物理学奖。写在课程的最后写在课程的最后CCDCCD作为计算机视觉的物质基础作为计算机视觉的物质基础计算机视觉从此获得蓬勃发展计算机视觉从此获得蓬勃发展Who Are They?加拿大物理学家博伊尔（Willard Boyle）和美国科学Rome is not built in a day!A good beginning is half done!Rome is not built in a day!A