1、周文晖计算机学院D.Marr视觉计算理论：计算机视觉的第三阶段（后期阶段）是获得物体的三维模型表征。换句话说：Merle Norman Cosmetics,Los Angeles阴影The Visual Cliff,by William Vandivert,1960阴影纹理From The Art of Photography,Canon阴影纹理遮挡阴影纹理遮挡运动阴影纹理遮挡运动模糊其他线索高光轮廓对焦.Shape From XShape From XX=X=阴影、纹理、遮挡、运动、阴影、纹理、遮挡、运动、.Two is better than one?红蓝眼镜偏振光眼镜快门眼镜LG Opt
2、imus 3DHuman-Eye Separation(6.5cm)Left 2D ImageRight 2D ImageBrain3D Viewhttp:/ 2D ImageRight 2D ImageBrain3D View采用一对像机代替人眼Left 2D ImageRight 2D ImageBrain3D ViewDisplacement(Stereo Baseline)采用一对像机代替人眼Displacement(Stereo Baseline)Left 2D ImageRight 2D ImageComputer3D ViewDisplacement(Stereo Baselin
3、e)Left 2D ImageRight 2D ImageComputer3D View光线OP上的任意点都投影在图像平面的p点上。深度感知存在歧义第二个像机可解决单目存在的深度歧义可通过三角测量获得深度两直线相交于一点plpr考虑左、右像机光轴平行的特殊情况P(X,Y,Z)pl(xl,yl)光心 Olf=焦距像平面左摄像机左摄像机B=基线深度深度 Zf=焦距光心 Orpr(xr,yr)像平面右摄像机右摄像机xzfxCCXBfxxfBzdxxB fzd通常的立体视觉系统（包括人类视觉系统）都是采用会聚方式。field of viewof stereoone pixeluncertainty o
4、fscenepointOptical axes of the two cameras need not be parallel平行光轴立体视觉系统 较大的公共视野区域较大的公共视野区域 深度误差（不确定区域）较大深度误差（不确定区域）较大平行光轴立体视觉系统 较大的公共视野区域较大的公共视野区域 深度误差（不确定区域）较大深度误差（不确定区域）较大 公共视野区域较小公共视野区域较小 深度误差（不确定区域）较小深度误差（不确定区域）较小平行光轴立体视觉系统 较大的公共视野区域较大的公共视野区域 深度误差（不确定区域）较大深度误差（不确定区域）较大 公共视野区域较小公共视野区域较小 深度误差（不确
5、定区域）较小深度误差（不确定区域）较小 会聚角度为会聚角度为 公共视野区域大公共视野区域大立体视觉中重要的几何约束：场景点P在视图中的投影点为像素点p，则在视图 中的投影点p必定满足双目几何约束：必定位于图像平面 与OPO平面的交线上。像素点p和p是场景点P在两视图上的投影。像素点p和p称为对应点或匹配点。极点极线基线极点极线基线（Baseline）：连接像机中心的直线极点（Epipole）：基线与图像平面的交点极平面（Epipolar plane）：基线和场景点组成的平面极线（Epipolar line）：极平面与图像平面的交线所有的极线相交于极点所有极线水平极点在基线B上的无穷远处左、右图
6、对应极线在同一水平。对应像素点只存在水平坐标差异，不存在垂直坐标差异。即仅有水平视差，垂直视差为0。xzfxCCXBf立体图像校正 将左、右图像平面都投影到平行于基线的公共平面。变换后的对应极线处于同一水平线（共线）。校正的目的：输入图像通过透视变换使得外极线水平，且共线。畸变校正，使得成像过程符合小孔成像模型。plprPOlOrXlXrPlPrZlYlZrYrT校正步骤：将左右图像平面都投影到平行于基线的公共平面。图像行像素重采样。最小化图像畸变。Zhang and Loop,MSR-TR-99-21 对于每个像机，其图像坐标系与像机坐标系间的关系。焦距、光心、畸变系数 两像机间的相对位置和
7、方向。旋转矩阵R R和平移矢量T TplprPOlOrXlXrPlPrflfrZlYlZrYrR,T符号定义：场景点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=frllllrrrrfZfZpPpPplprPOlOrXlXrPlPrflfrZlYlZrYrR,T同时旋转左右像机使得它们具有相同的X轴。定义左像机的旋转矩阵为Rrect。右像机旋转矩阵为 RrectR
8、立体图像校正后plprPOlOrXlXrPlPrZlYlZrYrT,0,0rlB TPPT由立体图像标定有，立体图像校正后，有校正目标：即：可得由于R为正交矩阵，有rlPR PT11llllllrrrrrr PR PPR PPR PPR P,0,0rlB TPPT111rrllrrlrR PR R PTPR RR PR RT11rlrlR RRIRR RrlRR RStereo pairs before rectification Stereo pairs after rectification UnrectifiedRectified平行光轴的双目立体视觉xzfxCCXBfB fzddxx立
9、体匹配的过程：为左图像的每个像素点(xl,yl)，在右图像中搜索对应点。(xl,yl)极线约束的意义：将对应点搜索由原来的二维平面上搜索变为在极线上的一维搜索。对于校正后的立体图像：在图像水平方向搜索比较右图对应极线上的每个像素，寻找最相似的像素作为对应点。即在右图同一水平方向上的搜索。(xl,yl)相似度值最大匹配基元：参与立体匹配，计算相似测度的基本单元 单个像素存在相似性歧义 需结合一行或整幅图像的所有像素同时完成匹配 具有较好的局部独特性 隐含假定：窗口内所有像素应能表征中心像素 具有较好的独特性 稀疏且不均匀分布根据立体匹配过程中涉及的像素范围，可分为：通常以基于局部窗口的立体匹配方
10、法为主。匹配基元：局部窗口 匹配过程中，求解一行或整幅图像中所有像素的相似测度和最大/最小。匹配基元：像素根据立体匹配过程中采用的匹配基元，可分为：搜索每个像素的对应点，构建致密视差图 匹配基元为像素 仅为特征搜索对应点，构建稀疏的视差图.匹配基元为特征。以基准图的待匹配点为中心创建一个窗口，以在对准图中对应外极线上某一像素点为中心创建同样大小的滑动窗口，窗口内相邻像素的亮度值分布来表征中心像素。比较对准图中每个滑动窗口内容与基准图参考窗口内容的相似程度。PPR Ri ig gh ht t e ep pi ip po ol la ar r l li in ne eS Se ea ar rc c
11、h h R Ra an ng ge eL Le ef ft t e ep pi ip po ol la ar r l li in ne e基于局部窗口的对应性搜索基于局部窗口的对应性搜索Matching costdisparityLeftRightscanline对于已校正的双目立体图像对，则在扫描线上搜索。常用的相似性测度包括：距离测度：L1距离、L2距离、.相关系数：NCC、ZNCC 非参数化测度：RANK、Census像素亮度差的绝对值和(Sum of Absolute Differences,SAD)：像素亮度差的绝对平方和(Sum of Squared Differences,SSD
12、)：,(,)(,)pSADlru vWCI u vI ud v2,(,)(,)pSSDlru vWCI u vI ud vLeftRightscanlineSSD归一化互相关(Normalized Cross-Correlation,NCC),22,(,)(,)(,)(,)ppplru vWNCClru vWu vWI u vI ud vCIu vIud v,22,(,)(,)(,)(,)pppllrru vWZNCCllrru vWu vWI u vII ud vICI u vII ud vILeftRightscanlineNCCRANK：,(,)pRanklru vWCIu vIud v
13、,pkkkm nWIu vIm nIu v统计匹配窗口内像素亮度值小于中心像素的个数。,kIu vCensus：,pCensuslRu vWCHAMMING Iu vIud v,kkkm nWpIu vBITSTRINGIm nIu v是将匹配窗口内像素按一定顺序映射为二进制位串，如像素亮度值大于中心像素则映射为1，反之为0。然后比较左、右匹配窗口二进制位串的汉明距离。ground truth(a)SAD 匹配结果(b)ZSAD 匹配结果(c)SSD 匹配结果(d)ZSSD 匹配结果(e)NCC 匹配结果(f)ZNCC 匹配结果(g)Rank 匹配结果(h)Census 匹配结果for(j=l
14、ine_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;特点：特点：单个像素在亮度、色彩上存在歧义单个像素在亮度、色彩上存在歧义 匹配窗口内像素应具有相同的视差值。因此，当匹配窗匹配窗口内像素应具有相同的视差值。因此，当匹配窗口跨越深度不连续区域时就会因违背假设而引起误配。口跨越深度不连续区域
15、时就会因违背假设而引起误配。5x5匹配窗口 7x7匹配窗口 11x11匹配窗口 19x19匹配窗口 匹配窗口变小细节丰富噪声大视差边缘处好匹配窗口变大视差更平滑噪声小视差边缘处差Input Ground truth7x7 windowSharp edges are blurred!Adaptive windowSharp edges and less noise3x3 windowToo noisy!优点：容易实现，只需要考虑局部窗口区域 对纹理丰富的区域具有较好匹配性能 速度快，只需考虑有限像素 易于硬件实现，易于流水线实现缺点：视差不连续、遮挡或边缘区域无法正确估计视差 对重复性纹理、无/
16、弱纹理区域无法准确估计视差即使在测试的标准图像中匹配也并非容易 重复场景 无纹理区域 遮挡场景点投影到两幅图像中并不总是一致的 像机的影响 图像噪声、不同增益、不同对比度等等.视点的影响 透视畸变 遮挡 镜面反射 尺度、旋转变化为克服匹配过程中存在的歧义性，需采用一些常用的匹配约束：匹配点必须在极线上：左、右图像的匹配点应具有相似的亮度或颜色。即，假定目标表面符合朗伯漫反射表面。仅在视差搜索内搜索。思考：视差搜索范围如何确定思考：视差搜索范围如何确定？：一幅图像中的一个像素，在另一幅 图像中最多只有一个对应点像素。：若参考图中A点在B点的左边，则另一幅图像中A点匹配点也在B点匹配点的左边。该约
17、束对细小物体不成立该约束对细小物体不成立平滑性约束平滑性约束/一致性约束：一致性约束：除了遮挡或视差本身不连续区域外，小邻域范围内视差值变化量应很小或相似。换言之视差曲面应是分段连续的。互对应约束：互对应约束：又称左右一致性，若以左图为基准图，左图上一像素点 pl 的搜索到右图上对应点像素为 pr；那么若以右图为基准图，像素 pr 的对应点也应该是左图上的像素点 pl。该约束常用于遮挡区的检测。pl pr 约束条件 极线约束 相似性约束 视差范围约束 唯一性约束 顺序约束/单调性约束 互对应约束在区域匹配过程中已实现区域匹配中各像素的对应性搜索相互独立的，而约束要求考虑相邻像素间的视差关系。根
18、据约束条件作用范围，可分为两大类：顺序约束和平滑约束优化的匹配代价。该问题可归结为路径规划问题，即寻找视差空间图的最小代价路径。根据贝叶斯理论及马尔可夫随机场理论，立体视觉问题可以转化为求解全局能量最小问题。全局能量函数为整幅图像所有像素点的匹配代价。基于动态规划的匹配算法并不是地寻找每个像素点的匹配值。优化整条扫描线优化整条扫描线，使得该扫描线上所有像素的匹配代价和最小，并满足顺序和平滑约束。不同扫描线独立完成优化。左图像右图像leftSrightSpp+dp匹配过程中关注的是整个扫描线上的所有像素Left scanlineRight scanlineMatchMatchMatchLeft
19、occlusionRight occlusion三种情况：连 续匹配代价，满足顺序约束 左遮挡无匹配代价 右遮挡无匹配代价Left scanlineRight scanlineLeft Occluded PixelsRight occluded Pixels动态规划在视差空间中生成一条最优路径。路径生成满足顺序约束遮挡、匹配搜索方向及其代价示意：correspondence left OcclC right OcclC,leftrightppdist IILeft Occluded PixelsLeft scanlineRight occluded PixelsRight scanlineSt
20、artEnd动态规划是求解连续决策（最优路径）问题的有效方法。总共有多少条路径？总共有多少条路径？123123123123i=1i=2i=3t=1t=2t=3t=T3T状态扫描行像素将整条扫描线匹配过程分解为多阶段决策过程。单个阶段决策的代价为：1231231231tCtC1tC122232i=1i=2i=3jiij state to state from going ofCost n阶赋值问题的最优理论（体现动态规划方法）：1231231231tCtC1tC1222322j1i2i3i)(min)(1iCjCtijit记录每个节点的父节点1231231231tCtC1tC2)2(tb)(mi
21、narg)()(min)(11iCjbiCjCtijittijit2j1i2i3i最优路径搜索的伪代码注：M(i,j)用于记录父节点correspondence left OcclC right OcclC,leftrightppdist II最优路径回溯伪代码遮挡跳过直到找到下一个匹配点优点优点:保证了一条扫描线上各像素点的优化匹配。缺点：缺点：缺少扫描线间的强制约束 无法将水平方向和垂直方向的连续性约束有效融合。局部误差会着扫描线传播。视差结果图中有着很明显的横纹效应。横纹效应明显 为每个像素在另一幅图像中寻找到最佳匹配。若两像素相邻，则它们的视差（通常）相近。立体匹配的全局能量函数定义：
22、数据项:匹配代价平滑项:平滑代价使得每个像素在另一幅图像中找到一个良好的匹配。相邻像素（通常）应具有相近的视差。数据项：平滑项：所有像素的所有像素的匹配代价和匹配代价和4-connected neighborhood8-connected neighborhood邻域像素集邻域像素集平滑项：是邻域像素违反平滑性约束的惩罚项。常用模型函数：“Potts model”L1 distanceY.Boykov,O.Veksler,and R.Zabih,Fast Approximate Energy Minimization via Graph Cuts,PAMI 2001I1I2DW1(i)W2(i
23、+D(i)D(i)jiijDiDiDiWiWDE,neighbors221)()()()()(data termsmoothness term(Potts Models)常用能量函数最小求解方法 基于图的求解 Graph Cuts 基于概率的求解 Belief Propagation（BP）主要思想在左右两幅图像中寻找匹配特征常用特征有：边缘点线段角点匹配算法 在立体图对中抽取特征 定义相似度 利用相似度和极线几何寻找匹配相关匹配方法 易于实现 对纹理丰富的图像有良好匹配性能，反之误匹配较多 可获得致密视差图（用于表面重建）当视点差异较大时，难以正确匹配，这是由于：光照方向发生变化 违反了朗伯
24、散射假定特征匹配方法 运算速度比相关匹配方法快 适用于易于提取特征点的场景 获得稀疏视差图，适用于视觉导航等应用 对亮度变化相对不敏感对于大场景的三维重建，由于系统视场有限，需要对于大场景的三维重建，由于系统视场有限，需要对不同视角下的三维模型进行人工拼接。对不同视角下的三维模型进行人工拼接。三维拼接技术的实质是把在不同的局部坐标系中测三维拼接技术的实质是把在不同的局部坐标系中测量得到的有效数据点云进行坐标变换。量得到的有效数据点云进行坐标变换。输入图像必须有足够的特征信息前后帧之间应保证一定的重叠率，一般选取在6090为佳。尺度和旋转变化不易太大。三维测量三维测量三维建模三维建模场场景景点云
25、点云pointcloudS.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.Video加拿大物理学家博伊尔（Willard Boyle）和美国科学家史密斯（George E.Smith），因发明数码相机图像感应器“感光半导体电荷耦合器件”(CCD)，2009年10月连同“光纤之父”高锟，荣获诺贝尔物理学奖。
