第十章 基于立体视觉的深度估计

立体视觉

立体成象 我们将场景中同一点在两个不同图像中的投影点称为共轭对 其中的一个投影点是另一个投影点的对应(correspondence) 两幅图像重叠时的共轭对点的位置之差(共轭对点之间的距离)称为视差(disparity) 通过两个摄像机中心并且通过场景特征点的平面称为外极(epipolar)平面 外极平面与图像平面的交线称为外极线．

立体成象

立体成象 由相似三角形可得 合并两项，可得 F是焦距，B是基线距离

立体成象 因此，各种场景点的深度恢复可以通过计算视差来实现． 大角度立体方法 ——提高场景点深度计算精度的有效途径 主要的问题有： 随着基线距离的增加，两个摄像机的共同的可视范围减小 场景点对应的视差值增大，则搜索对应点的范围增大，出现多义性的机会就增大． 由透视投影引起的变形导致两个摄像机获取的两幅图像中不完全相同，这就给确定共轭对带来困难．

立体成像的一般情况 在实际中，两条外极线不一定完全在一条直线上，即垂直视差不为零 两个摄像机的光轴不平行

立体图像校正 立体图像对重新取样，使外极线对应于图像阵列的行

立体图像校正 将两图像投影到一个平面上就能得到理想的极线几何．左(右)摄像机中的每一个像素点分别对应于左(右)摄像机坐标系统中的一条射线。 设Tl和Tr分别表示将左、右摄像机的射线变换到公共平面坐标系的刚体变换，确定每个图像的顶点在公共平面上的位置，创建新的左、右图像网格，将每一个网格点变换回原来的图像上．使用双变量线性内插方法内插像素值可确定公共平面上新的左、右图像中的像素点。

平行光轴立体视觉系统 右图像: 左图像: 目标 参考 景深 Z 高度 Zw Zw=0 左摄像机 右摄像机 视差 基线 进行立体校正后得到平行光轴立体视觉系统，如图所示 景深 Z Zw=0 11

视差公式 视差: dx = xr - xl P(X,Y,Z) pl(xl,yl) 光心 Ol f = 焦距 像平面 f = 焦距 光心 Or pr(xr,yr) 像平面 平行光轴立体视觉系统 景深 视差: dx = xr - xl B = 基线 左摄像机 右摄像机

立体匹配 求解对应问题是立体成象系统的核心内容 求解对应问题极富有挑战性，可以说是立体视觉最困难的一步． 方法 基于特征（点、线）的匹配(稀疏匹配) 基于区域的匹配(稠密匹配)

立体匹配的困难 引入约束，减少搜索范围 场景投影到两幅图像中并不总是一致的 复杂场景因素 摄像机相关 视点相关 图像噪声、不同增益、不同对比度等等... 视点相关 透视畸变 遮挡 镜面反射 复杂场景因素 重复场景 无纹理区域 引入约束，减少搜索范围

外极线约束 一幅图像上的特征点一定位于另一幅图像上对应的外极线上 将二维搜索转会为一维搜索问题 在外极线的一个小邻域内进行搜索

一致性约束 对图像进行规范化处理(Normalization) 设参考摄像机和其它摄像机的图像函数分别为 ，则图像窗内规范化图像函数为： 和 μ是图像窗内光强的平均值, σ是光强分布参数: 相似估价函数为差值绝对值之和

顺序约束 如果在参考图像中点A在点B的左边=> 在目标图像中点A的匹配点也在点B的匹配点的左边 对细小物体不成立 Image from Sun et al. CVPR05

其它约束 唯一性约束 一幅图像(左或右)上的每一个特征点只能与另一幅图像上的唯一一个特征对应． 连续性约束 物体表面一般都是光滑的，因此物体表面上各点在图像上的投影也是连续的，它们的视差也是连续的． 在物体边界处，连续性约束不能成立．

特征匹配——稀疏 在立体图像对中识别兴趣点(interesting point)，而后在两幅图像中匹配相对应的点． 在图像中具有很大变化的区域内寻找兴趣点 在以某一点为中心的窗函数中，计算其在不同方向上的变化量 为避免将多个相邻点选为同一个特征对应的兴趣点，将特征点选在兴趣测度函数具有局部最大值的地方

特征匹配 对于左图像中的每一个特征… 左图像 线 角点 结构 (0). Essential Equation represents actually the epipolar plane in either the left or the right image (1). Epipolar line in the right image given pl (Epl)Tpr=0 zr = fr extension of the equations in pr = (xr,yr,fr) (2). Epipolar line in the left image given pr (prTE) pl=0 zl = fl 对于左图像中的每一个特征… 20

特征匹配 右图像 角点 线 结构 在右图像中寻找… 当相似度达到最大时的偏移量就是视差 21

特征匹配——稀疏 基于特征的立体匹配算法产生对应于图像特征点的场景稀疏深度图． 仅仅能恢复用于求解共轭对的像素子集对应的特征点深度． 要想得到其它点的深度值，必须通过使用有关计算方法来估算，如内插值技术．

基于边缘特征的立体匹配算法 （1）采用标准的摄像机设置，并利用边缘点作为图像特征。 （2）采用外极约束使匹配过程简化：为求左图像某扫描行上一个边缘点Pil在右图像上的对应点，沿右图像的同一扫描行扫描寻找匹配点即可。根据相容性约束，所求对应点Pir也应为一边缘点，且两个边缘点的幅值和方向应保持一致。

基于边缘特征的立体匹配算法描述 输入图像：左边缘图像el(i,j)， 1≤i≤I,1≤j≤J 右边缘图像er(i,j)， 1≤i≤I,1≤j≤J 输出图像：视差图像d(i,j)， 1≤i≤I,1≤j≤J 若干标记： il 左图像的现行行指标； ir 右图像的现行行指标； jl 左图像的现行列指标； jr 右图像的现行列指标；

基于边缘特征的立体匹配算法描述 算法步骤： （1） 初始化操作：将d(i,j)清零，并置： il=1，ir=1，jl=1和jr=1。 （2） 匹配运算： （2-1）从左边缘图像的第il 行当前列开始，寻找下一个待匹配的边缘点Pil。这里，Pil的列指标由jl指示； （2-2）在右边缘图像的第ir=il 行上，寻找Pil的对应点Pir。方法如下：比较候补边缘点和Pil的幅值和方向，看是否一致。如果需要的话，可引入顺序约束以进一步减少匹配运算。上述过程不断进行直到在右图像上找到具有最大一致性的边缘点为止，并将其定为Pil的对应点Pir。这里，Pir的列指标由jr指示。然后，根据jl和jr的值计算待匹配的边缘点Pil处对应的视差。即置d(il,jl)=jl-jr。

基于边缘特征的立体匹配算法描述 算法步骤(续)： 算法特点：鲁棒，但仅在图像的边缘点处可以获得相应景物的三维位置信息。 一旦右图像上的一个边缘点被定为左图像上的一个边缘点的对应点，则根据唯一性约束，该点以后将不能和左图像上任何别的边缘点相匹配。 （2-3）进行行终止检查。若左图像的现行行上已无待匹配的边缘点，去（3）；否则，回到（2-1）。 （3） 若il=I，去（4）； 否则，置il=il+1、jl=1和jr=1，回到（2-1)； （4） 根据视差图像d(i,j)和摄像机的系统参数，计算各边缘点处的三维坐标。 算法特点：鲁棒，但仅在图像的边缘点处可以获得相应景物的三维位置信息。

基于区域相关性的立体匹配(稠密) 计算一幅图像的一个小窗函数内的像素与另一幅图像中具有同样的潜在对应特征的小窗函数的像素之间的相关值．具有最大相关值的小窗区域就是对应区域． 只有满足外极线约束的区域才能是匹配区域．考虑到垂直视差的存在，应将外极线邻近的像素点也包括在潜在的匹配特征集中．

立体匹配评价函数

立体匹配评价函数

稠密匹配 对参考图像中每一点找到对应于场景中同一点的匹配像素，得到稠密的视差图

导致稠密立体匹配困难的原因 左、右图像的彩色不一致 图像中存在遮挡区域 图像中存在镜面反射现象 图像中存在重复模式 图像中存在无纹理区域

算法评估 以真实视差场为参照，对计算得到的视差场进行评估，统计视差场的准确度，以此反映匹配方法的性能 http://vision.middlebury.edu/stereo

立体匹配算法的几个要素 局部优化 全局优化 特征 约束条件 优化方法 基于滑动窗相关和连续性约束的立体匹配算法 基于滑动窗相关的动态规划立体匹配算法 基于区域特征的图割立体匹配算法 基于置信度传播的区域匹配算法 ……

经典相关窗法 左图像 (xl, yl) 对参考图像中每个点 (xl, yl)定义以它为中心的窗口 35

经典相关窗法 右图像 (xl, yl) 在目标图像中一定范围搜索匹配点… 36

经典相关窗法 右图像 (xr, yr) dx (xl, yl) …视差就是当相关值达到最大时的偏移量 37

基于相关窗的立体匹配算法 使用特征： 右图所示组合特征 匹配度计算： 误差函数

基于相关窗的立体匹配算法 使用特征： 右图所示组合特征 匹配度计算： 相关函数

基于相关窗的立体匹配算法 输入图像： 左灰度图像fl(i,j)， 1≤i≤I,1≤j≤J 右灰度图像fr(i,j)， 1≤i≤I,1≤j≤J 输出图像： 视差图像d(i,j)， 1≤i≤I,1≤j≤J 若干标记： il 左图像的现行行指标； ir 右图像的现行行指标； jl 左图像的现行列指标； jr 右图像的现行列指标； w 固定窗口的宽度指标； v 固定窗口的高度指标；

基于相关窗的立体匹配算法 算法步骤： （1）初始化操作：将d(i,j)清零，并置il=v+1，ir=v+1和jl=w+1。 （2）匹配运算： （2-1）在右图像的第ir=il行上寻找与左图像上的当前像素Pil=fl(il,jl)最相似的对应点Pir。方法如下：以固定尺寸的窗口套住当前像素Pil，并让同一尺寸的窗口顺序滑过右图像的第ir行，在每一个像素位置，计算所定义的误差函数E(il,jl,d)（也可计算所定义的相关函数R(il,jl,d)）,直到在右图像上找到最相似的像素点Pir为止。并将Pir定为Pil的对应点。若Pir的列指标由jr指示，那么，置d(il,jl)=jl-jr。一旦右图像上的一个像素点被定为左图像上的一个像素点的对应点，则根据唯一性约束，该点以后将不能和左图像上任何别的像素点相匹配。同样，也可引入顺序约束以进一步减少匹配运算。 （2-2）做行终止检查：若jl=J-w，去（3）；否则，置jl=jl+1，回到（2-1）。 （3）若il=I-v，去（4）；否则，置il=il+1、ir=ir+1和jl=w+1，回到（2-1）。 （4）根据视差图像d(i,j)和摄像机的系统参数，计算各边缘点处的三维坐标。

基于相关窗的立体匹配算法 算法特点： 可获得稠密视差 误匹配可能较多。 误匹配的原因： 重复场景 遮挡 局部优化 （各类匹配算法的共同问题）

经典相关窗法结果

自适应支持权值法 格式塔心理学 根据相似性和接近性设计邻近像素对匹配窗中心像素的权值[Yoon CVPR05] 相似性准则 接近性准则 2005年Yoon和Kweon提出

自适应支持权值法 在CIE Lab颜色空间的相似性: 接近性:欧氏空间距离 Weights: 匹配代价累积公式

自适应支持权值法结果

自适应支持权值法结果

自适应窗口加权法结果

马尔科夫随机场 “贴标签”，标签就是视差 给特定像素分配一个标签有分配代价 给临近像素分配一对标签有分离代价 找到总的分配代价和分离代价之和最小 图割算法 置信传播算法

图割算法 通过计算赋权图的最小割集求能量最小化 以割代价为能量，求得的割集就是标签, 通过最大流算法使能量迅速减少 运行时间与像素数和标签数成线性关系 近似地说, 低维多项式

图割算法 s t cut L(p) p “cut” x y 标签 视差标签

图割算法结果 在能量中包括遮挡项[Kolmogorov ICCV01]

置信传播算法 在马尔可夫网络上传播消息的迭代推导算法 对树结构有精确解，对有环图有较好的近似解 消息:反映邻近站点变量取值对该站点变量取值的影响 对树结构有精确解，对有环图有较好的近似解 D V 每个站点从其邻近站点接收消息以调整其每个变量值的置信度，算法迭代传递消息以调整各站点每个变量值的置信度，不断减小能量值。 当所有站点各个变量值的置信度趋于稳定时，算法选择置信度最大的变量值作为每个站点变量的取值。 53

对称置信传播算法结果 Middlebury评估网站排名第一 (June 2005)

对称置信传播算法结果

对称置信传播算法结果 Middlebury评估网站排名第一 (June 2005)

基于分割区域的算法 隐含假设 通常步骤 颜色平滑的区域内部视差能够用平滑的视差模型（常数、平面等等）代替 视差不连续处与分割区域边缘相一致 图像分割 初始视差计算 根据初始视差估计每个视差平面参数 根据定义能量以分割区域为整体采用合适算法优化 图像分割可以对一幅或两幅图像进行分割 57

基于分割区域的算法 优点 缺点 区域内的平滑是被强制执行的 单眼线索所获得的视差边界在很多时候比单纯由视差估计的边界更为准确 对遮挡区域匹配的鲁棒性也得到改善 效率更高 缺点 基于分割区域的方法的分割假设并不一定总是正确的 视差模型可能并不能表示区域真正的视差 目前评测网站上的前7种算法都是基于分割区域的算法

基于区域间协同优化的立体匹配算法 由于GC和BP等优化算法都是基于“贴标签（labelling）”的优化算法，为了限制最终优化时的标签数，这些算法在优化前通常需要在视差平面参数空间中对区域进行聚类分层以减少最终优化时的标签数。但这样做会使得算法的通用性降低，而且最终优化时被用来作为标签的视差平面参数是不变化的，如果最终优化前视差平面参数估计不准确，在优化过程中不能被修正。

均值偏移(Mean Shift)图像分割算法

不同带宽对立体匹配的影响 由结果可以看出，如果空域和色彩域带宽太大，会使部分不同视差区域被误分到同一区域，造成匹配失败。但如果空域和色彩域带宽太小，也会使部分区域及其邻域包含信息量过小，造成匹配困难。因此选择合适的分割带宽对匹配质量的好坏有一定影响

不同带宽对立体匹配的影响

鲁棒的视差平面拟合算法 RANSAC 随机地从数据集S中选择s个数据点组成一个样本作为模型的一个例示 确定在模型距离阈值t内的数据点集为一致集 经过N次试验，选择最大一致集，并用的所有点重估模型

经过RANSAC平面拟合后的视差图

基于投票的鲁棒视差平面拟合算法 通过对同一行的一对点计算 ，可以得到平面参数a的一个估计 将所有同一行的估计值在一维的a参数空间进行投票，并对投票结果进行高斯平滑后从中选出得票最多的值作为参数a的最终估计 对同一列的点通过计算　 ，可以得到参数b的估计 由上式可算出c，采用类似的投票方法可确定参数c 采用上述算法，可以有效地去除离群数据的影响，使结果具有鲁棒性

RANSAC方法和投票方法平面拟合结果的比较。其中，红色横线表示投票方法的拟合错误率，蓝色折线表示RANSAC方法的拟合错误率

经过投票平面拟合后的视差图 采用基于投票的平面拟合法得到的视差图

协同优化算法的基本原理 R1 R3 R2 R4 R5 R7 R8 R9 R10 R6 协同优化结果使每一变量在相关的每一子目标函数中的取值取得一致

协同优化算法的基本原理 为了使各子目标函数之间的优化结果能够保持一致，协同优化算法在优化每一子目标函数的时候，考虑与之相关联的其它子目标函数的优化结果对其的影响。 协同优化结果使每一变量在相关的每一子目标函数中的取值取得一致 其中， 表示合作强度，而 则用于刻画传播的力度。

协同优化算法的基本原理 协同优化算法的迭代方程 迭代过程不断进行直至算法收敛或执行完规定的迭代次数。由于对每一个区域的优化结果会在下一次迭代中向周边传播，经过若干次迭代后每一个优化变量在相关子目标函数中的最终取值将会取得一致。 协同优化结果使每一变量在相关的每一子目标函数中的取值取得一致

基于区域间协同优化的立体匹配 每个区域能量项定义 其中，第1项是数据能量，第2项是遮挡能量，而第3项是平滑能量。 其中，Vl和Vr分别表示当前区域在左右图像上的可见像素集，pVl、qVr为左右图像上相匹配的两个对应像素，r、g、b表示相应像素的RGB颜色值。各像素的RGB颜色值如下得到：根据所估计的当前区域的视差平面参数计算与参考图像（本文选为左图像，下同）上的像素p对应的被匹配图像（本文选为右图像，下同）上的像素q，并获取其RGB颜色值。由于计算得到的视差是浮点型的，所以像素q一般并不正好处于整数像素位置上，故其RGB颜色值一般不能直接从图像中获得。在本文的算法中，其值由被匹配图像上q的四个近邻像素的RGB颜色值经过插值得到。计算数据能量时考虑了可视性准则[41]，即要求用来计算数据能量的像素在左右图像对中都是可见的。

基于区域间协同优化的立体匹配 其中，Vl和Vr分别表示当前区域在左右图像上的可见像素集，p、q为左右图像上相匹配的两个对应像素，r、g、b表示相应像素的RGB值。 其中，Vl和Vr分别表示当前区域在左右图像上的可见像素集，pVl、qVr为左右图像上相匹配的两个对应像素，r、g、b表示相应像素的RGB颜色值。各像素的RGB颜色值如下得到：根据所估计的当前区域的视差平面参数计算与参考图像（本文选为左图像，下同）上的像素p对应的被匹配图像（本文选为右图像，下同）上的像素q，并获取其RGB颜色值。由于计算得到的视差是浮点型的，所以像素q一般并不正好处于整数像素位置上，故其RGB颜色值一般不能直接从图像中获得。在本文的算法中，其值由被匹配图像上q的四个近邻像素的RGB颜色值经过插值得到。计算数据能量时考虑了可视性准则[41]，即要求用来计算数据能量的像素在左右图像对中都是可见的。

基于区域间协同优化的立体匹配 这里，Bc表示参考图像上当前区域的边界点集，N表示和Bc近邻的其它区域上的边界点集，Bc中的p 、N中的q为四连通意义上的两个近邻像素，d(p)、d(q)为像素p、q的视差，而ldisp为所设置的平滑惩罚常量。 其中，Vl和Vr分别表示当前区域在左右图像上的可见像素集，pVl、qVr为左右图像上相匹配的两个对应像素，r、g、b表示相应像素的RGB颜色值。各像素的RGB颜色值如下得到：根据所估计的当前区域的视差平面参数计算与参考图像（本文选为左图像，下同）上的像素p对应的被匹配图像（本文选为右图像，下同）上的像素q，并获取其RGB颜色值。由于计算得到的视差是浮点型的，所以像素q一般并不正好处于整数像素位置上，故其RGB颜色值一般不能直接从图像中获得。在本文的算法中，其值由被匹配图像上q的四个近邻像素的RGB颜色值经过插值得到。计算数据能量时考虑了可视性准则[41]，即要求用来计算数据能量的像素在左右图像对中都是可见的。

基于区域间协同优化的立体匹配 首先根据当前的视差计算结果将左图像上相关的各区域映射到右图像，然后在右图像上检查映射情况；如果某个像素被重复映射，则将该像素记为左遮挡；如果某个像素未被映射，则将该像素记为右遮挡。Occl和occr分别表示左遮挡和右遮挡像素的个数，而remda表示所设置的遮挡惩罚常量 考虑参考图像上的两个相邻区域A和B，A在B的右边。当A区域在相邻边界处的视差大于其左邻域B的视差时，那么根据当前的视差计算结果将A和B映射到右图像时，B’的一部分（图中的D区域）将被A’所遮挡（左遮挡），而当A区域在相邻边界处的视差小于其左邻域B的视差时，映射到右图像后的两个区域A’和B’之间将会出现空隙（图中的C区域），相当于右图像上A’区域有一部分在左图像上被遮挡了（右遮挡）。

基于区域间协同优化的立体匹配 其中， 和 分别表示左遮挡和右遮挡像素的个数，而λocc表示所设置的遮挡惩罚常量。 首先根据当前的视差计算结果将左图像上相关的各区域映射到右图像，然后在右图像上检查映射情况；如果某个像素被重复映射，则将该像素记为左遮挡；如果某个像素未被映射，则将该像素记为右遮挡。Occl和occr分别表示左遮挡和右遮挡像素的个数，而remda表示所设置的遮挡惩罚常量

基于区域间协同优化的立体匹配

基于区域间协同优化的立体匹配 计算完每个区域的能量后，选用局部优化方法对所有区域的视差平面参数进行迭代优化 当一个区域的平面参数变化时，它不仅会影响本身区域的能量，同时也会对邻域的能量产生影响。 这里的邻域包括所有可能带来能量变化的区域，即在视差搜索范围内的所有邻域

协同优化算法应用于标准图像对Tsukuba

基于区域间协同优化的立体匹配

实拍图像