本发明提出一种基于搜索窗口自适应的视差估计方法，本方法属于双目数字图像处理领域，涉及一种搜索窗口自适应的视差估计方法。该方法为对水平摄像机组同步拍摄的两幅图像分别进行以不同大小块为单位的遍历扫描，求出块大小不同时的匹配误差和视差矢量，然后选取匹配误差最小的视差矢量作为最终视差的方法。首先分别以左右图像为目标图像，并先后将其分成不同大小的块，在参考图像中搜索目标图像每一块的最佳匹配结果，当块大小不同时，最佳匹配块位置并不完全一致，按照一定准则对每一块的匹配模式进行选择，最终得到准确视差场。本发明所述方法，较固定块匹配方案提高了视差估计的准确性，能得到适用于压缩编码和虚拟视点绘制的准确视差场。
1.一种基于搜索窗口自适应的视差估计方法，其特征在于实现步骤如下：
（1）读入两幅初始图像，并按照视差估计的要求对读入的两幅初始图像进行预处理；
（2）令预处理后的两幅图像中的一幅图像为目标图像，另一幅图像为参考图像，首先将目标图像分成尺寸均为M×N像素的块，在参考图像中一定范围内搜索每一个块的最佳匹配块，并记录每一个块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d；然后将目标图像分成尺寸均为(M/2)×(N/2)像素的块，按照相同过程搜索每一个块的最佳匹配块，并记录每一块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d；
（3）按照最小SAD准则，对目标图像的每一个位置进行判断，依据最小SAD准则选择最终的匹配结果，所述匹配结果是M×N块的搜索结果和(M/2)×(N/2)块的搜索结果之一，并将以块为单位的视差扩展至以像素为单位，形成与读入的初始图像尺寸相同的视差场。
2.根据权利要求1所述的一种基于搜索窗口自适应的视差估计方法，其特征在于：所述步骤（1）具体为：（1.1）读入两幅初始图像，所述两幅初始图像由水平摄像机组在同一时刻拍摄自同一场景，使这两幅初始图像仅在拍摄视角上存在差异；
（1.2）判断两幅初始图像的宽度和高度是否相同，若不同，则无法进行匹配，提示报错并跳出；若相同，继续执行步骤（1.3）；
（1.3）若两幅初始图像为彩色图像，则分别将其转化为灰度图像，然后执行步骤（2）；若两幅输入图像为灰度图像，则执行步骤（2）。
3.根据权利要求1所述的一种基于搜索窗口自适应的视差估计方法，其特征在于：所述步骤（2）中的具体实现如下：（2.1）对参考图像进行扩边处理，在参考图像的左右各增加b个像素，b须满足包含所有双目视图中只存在于一幅视图的场景内容，并令增加的像素灰度值为0，参考图像高度不变，宽度增加2×b个单位，且增加的部分为黑色；
（2.2）首先将目标图像分为M×N的块，称为宏块，其中M为每块宽度，N为长度，求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，SAD定义为目标图像块与参考图像块之间的绝对值误差和，计算方法如下：其中块的大小为M×N，T(m,n)为目标图像中某一块的左上角点，(m,n)为T的位置坐标；R(p,q)为参考图像中某一块的左上角点，(p,q)为R的位置坐标；GT、GR分别为目标图像和参考图像在某一坐标点的灰度值；i、j为遍历参数，分别依次取从1到M和从1到N之间的整数；
（2.3）对目标图像中某一块在参考图像中寻找最接近块，将搜索起点设置为目标图像中待匹配块的左上角点T(m,n)，在区间[m-b,m+b]内进行匹配，求出[m-b,m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 其中上标M×N代表所使用块的宽度乘以高度，代表尺寸；下标min代表这个SAD是所有匹配位置得到的SAD的最小值；当块的尺寸为正方形，即M＝N时，将这个SAD最小值记为将搜索到的最佳匹配块位置记录下来，并求出目标块与最佳匹配块之间的位移矢量，即视差，记作
其中上标M×N代表所使用块的宽度乘以高度，表示尺寸；下标(m,n)代表待匹配的目标块的左上角坐标，等式右边的(m-p,n-q)表示视差矢量值，即水平方向和垂直方向上目标块和最佳匹配块的相对位移；当块的尺寸为正方形，即M＝N时，同一块的视差值记作如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M,H-N)，其中W、H分别为目标图像宽和高，M、N分别为匹配块的宽和高，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤（2.3）；
（2.4）将目标图像重新分块，分为(M/2)×(N/2)的块，称为子块，其中每块宽度为M/2，长度为N/2，求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，然后依据如下公式计算每个(M/2)×(N/2)大小块的SAD：公式中参数除了块的高度和宽度分别变为步骤（2.2）公式中块高度和宽度的1/2之外，其它参数不变；
（2.5）按照步骤（2.3）中对目标图像中的每一个块在参考图像中寻找最接近块的方法，将搜索起点设置为目标图像中待匹配块的左上角点T'(m,n)，在区间[m-b,m+b]内进行匹配，求出[m-b,m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 将搜索到的最佳匹配块位置记录下来，并求出每一个目标块与最佳匹配块之间的视差矢量；此时块的宽和高分别变为步骤（2.3）中块高度和宽度的1/2；
如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M/2,H-N/2)，其中W、H分别为目标图像宽和高，M/2、N/2分别为匹配块的宽和高，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤（2.4）。
4.根据权利要求1所述的一种基于搜索窗口自适应的视差估计方法，其特征在于：所述步骤（3）中的具体实现如下：（3.1）第一次分块时块的宽和高均为第二次分块的两倍，1个宏块在第二次分块中被分为4个子块；1个宏块与4个子块在位置上是对应的；在自适应选择宏块视差还是子块视差时，使用SAD最小准则，即比较1个M×N大小的宏块与最佳匹配块之间的SAD值 和4个(M/2)×(N/2)大小的子块与它们各自的最佳匹配块之间的SAD值之和，记为 如果 则选择宏块视
其中(m,n)表示4个子块中最左上角的坐标；符号[·]4表示子块
视差矩阵由与宏块位置对应的4个子块组成；i、j为遍历参数：
（3.2）将以块为单位的视差扩展至以像素为单位，形成与输入图像尺寸相同的视差场，对目标图像中的某一宏块，如果在步骤（3.1）中选择了宏块视差 则令宏块中每一点的视差矢量 其中(x,y)为图像坐标系中某点坐标；如果在步骤（3.1）中选择了子块视差矩阵 则令每个子块中的每一点的视差矢量
分别等于这些点所在子块的视差矢量 从而得到两幅由水平摄像
一种基于搜索窗口自适应的视差估计方法
技术领域
[0001] 本方法属于双目数字图像处理领域，涉及一种搜索窗口自适应的视差估计方法。
背景技术
[0002] 交互式立体视频，由于其与单目视频相比，增加了景物深度信息表征，因而在视频会议、自动导航、远程教育、立体电视、虚拟现实等领域有广泛应用前景。由于增加了临场感的代价是增加了若干倍的信息量，所以对多目摄像机组拍摄的数据进行存储、传输及合适的表达成为当前多媒体领域研究的热点问题。
[0003] 视差估计(Disparity Estimation)技术，着眼点在于摄像机组对景物进行同步拍摄后，不同视点之间对象位置的几何对应关系，是立体视频技术中的重要基础。一方面，在立体视频编码中，视差估计技术可以与视差补偿预测(DCP)结合，以去除立体图像对间的相关性，从而对立体视频的多个视角的视频数据进行高比率压缩，去除冗余，使其传输、存储成为可能；另一方面，在虚拟绘制当中，视差估计得到的结果提供了视点之间的几何约束关系，和对应像素的位置规律，使得基于图像直接进行虚拟视点合成变得可行。
[0004] 根据匹配基元的不同，可以把视差估计简单的分为基于区域(参见Parisa Moslemi，Zeynab Mirzadeh.An Efficient Disparity Algorithm Based on Adaptive Window Selection for 3D Reconstruction in Stereo[C].The 10th International Conference on Information Science，Signal Processing and their Applications，2010，pp.113-116.)和基于特征两大类。基于区域的视差估计在平坦而纹理丰富的区域可以获得比较高的精度，并且匹配的结果不受特征检测精度和密度的影响，可以获得稠密的视差场。基于特征的视差估计与基于区域的方法相比，优点在于可以很好的解决歧义性问题，且对因光线、对比度变化而发生的变化不是很敏感。但与此同时，特征点的提取本身是比较困难的，准确度较低，导致基于特征的视差估计准确度比较不理想；并且由于特征点数量较少，得到的视差场是比较稀疏的，如果要通过插值得到较稠密视差场，那么视差准确度就会进一步降低。由于这两类视差估计方法的特点，目前人们的目光主要集中在基于区域的视差估计方法上。
[0005] 基于区域的视差估计方法中，Yihua Xu等人提出的方法根据初始视差的分布来确定窗口内各像素的支持权值，该方法有赖于初始视差估计的准确性(参见Xu Yi-hua，Wang Dong-sheng，Feng Tao，Shum Heung-Yeung.Stereo Computation Using Radial Adaptive Windows[C].16th International Conference on Pattern Recognition，2002，vol.3，pp.595-598.)；吕朝辉的方法调整对匹配窗口内每一像素的支持权值，使与待匹配点位于同一区域的像素权值增大，从而获得最终视差，但这种对于多纹理区域的匹配并不理想，固有遮挡问题也未作考虑(参见吕朝晖，袁惇.一种基于自适应权值的立体匹配方法[J].光学技术，2007，vol.33，no.4，pp.501-504.)；Zheng Jiali提出基于比例偏差最优化函数自动选择视差匹配模式的方法，该方法克服了视差估计缺乏鲁棒性的缺点，但同时引进了巨大的数据量(参见Zheng Jia-li，Qin Tuan-fa.Adaptive Disparity Estimation for Stereoscopic Video Coding[C].IEEE Youth Conference on Information Computing and Telecommunications(YC-ICT)，2010，pp.214-217.)。
[0006] 基于以上介绍可以得知，视差估计作为多视点系统中不可或缺的技术，已经得到越来越多的重视和关注，各种算法也在近几年相继提出。但目前视差估计技术仍未成熟，没有一种具有普适性的视差估计方法，能够对所有多目数据的视差信息进行估计；同时，目前的视差估计技术在快速性方面仍有所欠缺，基本不能达到视觉系统实时性的要求。
发明内容
[0007] 本发明要解决的技术问题是：为克服现有问题的不足，本发明提供一种基于搜索窗口自适应的视差估计方法，在运算复杂度降低，视差估计速度提高的同时，得到较好的视差图，能够用于多目视频编码和虚拟绘制等领域。
[0008] 本发明解决其技术问题所采用的技术方案包括：
[0009] 一种基于搜索窗口自适应的视差估计方法，其特征在于实现步骤如下：
[0010] (1)读入两幅初始图像，并按照视差估计的要求对读入的两幅初始图像进行预处理；
[0011] (2)令预处理后的两幅图像中的一幅图像为目标图像，另一幅图像为参考图像，首先将目标图像分成尺寸均为M×N像素的块，在参考图像中一定范围内搜索每一个块的最佳匹配块，并记录每一个块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d；然后将目标图像分成尺寸均为(M/2)×(N/2)像素的块，按照相同过程搜索每一个块的最佳匹配块，并记录每一块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d；
[0012] (3)按照最小SAD准则，对目标图像的每一个位置进行判断，依据最小SAD准则选择最终的匹配结果，所述匹配结果是M×N块的搜索结果和(M/2)×(N/2)块的搜索结果之一，并将以块为单位的视差扩展至以像素为单位，形成与读入的初始图像尺寸相同的视差场。
[0013] 所述步骤(1)中，在视差估计之前对输入的两幅图像进行预处理的具体实现如下：
[0014] (1.1)读入两幅初始图像，所述两幅初始图像由水平摄像机组在同一时刻拍摄自同一场景，使这两幅初始图像仅在拍摄视角上存在差异；
[0015] (1.2)判断两幅初始图像的宽度和高度是否相同，若不同，则无法进行匹配，提示报错并跳出；若相同，继续执行步骤(1.3)；
[0016] (1.3)若两幅输入图像为彩色图像，则分别将其转化为灰度图像，然后执行步骤(2)；若两幅输入图像为灰度图像，则执行步骤(2)；
[0017] 所述步骤(2)中，对目标图像中的每一个块，在参考图像一定范围内搜索最佳匹配块的步骤具体为：
[0018] (2.1)对参考图像进行扩边处理，在参考图像的左右各增加b个像素，b须满足包含所有双目视图中只存在于一幅视图的场景内容，并令增加的像素灰度值为0，参考图像高度不变，宽度增加2×b个单位，且增加的部分为黑色；
[0019] (2.2)首先将目标图像分为M×N的块，称为宏块，其中M为每块宽度，N为长度，求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，SAD定义为目标图像块与参考图像块之间的绝对值误差和，计算方法如下：
[0020]
[0021] 为其中块的大小为M×N，T(m，n)为目标图像中某一块的左上角点，(m，n)为T的位置坐标；R(p，q)为参考图像中某一块的左上角点，(p，q)为R的位置坐标；GT、GR分别为目标图像和参考图像在某一坐标点的灰度值；i、j为遍历参数，分别依次取从0到M-1和从0到N-1之间的整数；
[0022] (2.3)对目标图像中某一块在参考图像中寻找最接近块，将搜索起点设置为目标图像中待匹配块的左上角点T(m，n)，在区间[m-b，m+b]内进行匹配，求出[m-b，m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 其中上标M×N代表所使用块的宽度乘以高度，代表尺寸；下标min代表这个SAD是所有匹配位置得到的SAD的最小值；当块的尺寸为正方形，即M＝N时，将这个SAD最小值记为
[0023] 将搜索到的最佳匹配块位置记录下来，并求出目标块与最佳匹配块之间的位移矢量，即视差，记作
[0024]
[0025] 其中上标M×N代表所使用块的宽度乘以高度，表示尺寸；下标(m，n)代表待匹配的目标块的左上角坐标，(i，j)表示视差矢量值，即水平方向和垂直方向上目标块和最佳匹配块的相对位移；当块的尺寸为正方形，即M＝N时，同一块的视差值记作
[0026] 如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M，H-N)(其中W、H分别为目标图像宽和高，M、N分别为匹配块的宽和高)，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤(2.3)；
[0027] (2.4)将目标图像重新分块，分为(M/2)×(N/2)的块，称为子块，其中每块宽度为M/2，长度为N/2，求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，然后依据如下公式计算每个(M/2)×(N/2)大小块的SAD：
[0028]
[0029] 公式中参数除了块的高度和宽度分别变为步骤(2.2)公式中块高度和宽度的1/2之外，其它参数不变；
[0030] (2.5)按照步骤(2.3)中对目标图像中的每一个块在参考图像中寻找最接近块的方法，将搜索起点设置为目标图像中待匹配块的左上角点T′(m，n)，在区间[m-b，m+b]内进行匹配，求出[m-b，m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 将搜索到的最佳匹配块位置记录下来，，并求出每一个目标块与最佳匹配块之间视差矢量。此时块的宽和高分别变为步骤(2.3)中块高度和宽度的1/2；
[0031] 如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M/2，H-N/2)，其中W、H分别为目标图像宽和高，M/2、N/2分别为匹配块的宽和高，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤(2.5)；
[0032] 上述步骤(3)中，选择较好匹配模式的步骤具体为：
[0033] (3.1)第一次分块时块的宽和高均为第二次分块的两倍，1个宏块在第二次分块中被分为4个子块；1个宏块与4个子块在位置上是对应的；在自适应选择宏块视差还是子块视差时，使用SAD最小准则，即比较1个M×N大小的宏块与最佳匹配块之间的SAD值 和4个(M/2)×(N/2)大小的子块与它们各自的最佳匹配块之间的SAD值之和，记为 如果 则选择宏
块视差 如果 则选择子块视差矩阵，记为
其中(m，n)表示4个子块中最左上角的坐标；符号[·]4表示子块视
差矩阵由与宏块位置对应的4个子块组成：
[0034]
[0035] (3.2)将以块为单位的视差扩展至以像素为单位，形成与输入图像尺寸相同的视差场，对目标图像中的某一宏块，如果在步骤(3.1)中选择了宏块视差 则令宏块中每一点的视差矢量 其中(x，y)为图像坐标系中某点坐标；如果在步骤(3.1)中选择了子块视差矩阵 则令每个子块中的每一点的视差
矢量分别等于这些点所在子块的视差矢量 从而得到两幅由水平
摄像机组，在同一时刻拍摄的两幅图像的视差图。
[0036] 本发明与现有技术相比所具有的优点：
[0037] (1)本发明能够自适应的选择视图匹配窗口，根据输入图像的纹理信息，以匹配误差作为度量，选择较为准确的视差矢量，准确度较固定块搜索方案有较大提升；
[0038] (2)本发明依据双目视觉原理，针对水平摄像机组得到的图像理论上不存在垂直方向视差这一特点进行视差估计，仅对水平方向进行匹配，大大减小了搜索范围，从而减少了运算量，减少了算法运行时间。
[0039] (3)本发明在实际应用中能得到较好的视差图。
附图说明
[0040] 图1所示为本发明的基于搜索窗口自适应的视差估计方法流程图。
[0041] 图2所示分别为标准视频序列“ballroom.yuv”中第3、4视点的第60帧。
[0042] 图3所示分别为对两幅读入图像进行灰度化和扩边处理后的结果。
[0043] 图4所示为使用单一块匹配模式(M×N)的搜索流程图，块大小为16×16。
[0044] 图5所示为本发明所使用自适应块匹配视差估计算法所得结果。
[0045] 图6所示分别为使用固定块匹配方法对相同输入视图进行视差估计所得结果，其中(a)图块大小为16×16；(b)图块大小为8×8。
具体实施方式
[0046] 本发明为一种基于搜索窗口自适应的视差估计方法，属于双目数字图像处理领域的视差估计范畴，具体为对水平摄像机组同步拍摄的两幅图像分别进行以不同大小块为单位的遍历扫描，求出块大小不同时的匹配误差和视差矢量，然后选取匹配误差最小的视差矢量作为最终视差。
[0047] 本实例中所有“视图”、“图像”均指数字位图，横坐标为从左至右，纵坐标为从上至下，均为从0为初始计数点，像素点表示形式为(x，y)。图1所示为本发明的基于搜索窗口自适应的视差估计方法流程图。本发明具体实施步骤如下：
[0048] (1)读入两幅初始图像，并按照视差估计的要求对读入的两幅初始图像进行预处理，这一步骤的具体实施过程包括如下三个步骤：
[0049] (1.1)读入标准视频序列“ballroom.yuv”中第3、4视点的第60帧作为初始图像，以下分别称为左视图和右视图。所述两幅初始图像满足由水平摄像机组在同一时刻拍摄自同一场景的条件，仅在拍摄视角上存在差异(参见图2)。对一组初始图像的以上要求满足双目原理，分别相当于用“左右眼”对场景进行观察和记录。而本发明的目的在于搜索计算得出两幅满足条件视图之间的视点差异造成的，同一对象在不同视点下位置的差异，即视差矢量图；
[0050] (1.2)判断两幅输入图像的宽度和高度是否相同，若不同，则无法进行匹配，提示报错并跳出；若相同，继续执行步骤(1.3)；
[0051] (1.3)若两幅输入图像为彩色图像，则分别将其转化为灰度图像，然后执行步骤(2)；若两幅输入图像为灰度图像，则直接执行步骤(2)。在灰度转化过程中，每个像素点的灰度值按照如下公式对RGB三个色彩分量进行加权得到：
[0052] gray(x，y)＝0.11R(x，y)+0.59G(x，y)+0.30B(x，y)
[0053] 其中(x，y)表示某一像素点位置，gray、R、G、B分别表示位于同一位置的像素点的灰度值、红色分量、绿色分量和蓝色分量。
[0054] (2)令预处理后的两幅图像中的右视图为目标图像，左视图为参考图像，所要求的视差图即是从左到右的视差。首先将目标图像分成尺寸均为M×N像素的块，在参考图像中一定范围内搜索每一个块的最佳匹配块，并记录每一个块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d；然后将目标图像分成尺寸均为(M/2)×(N/2)像素的块，按照相同过程搜索每一个块的最佳匹配块，并记录每一块与最佳匹配块之间的最小绝对值误差和MSAD和位移矢量d，在本例中，为保证块大小有一定纹理容量，且达到对整幅图像的整数次匹配，选用M＝N＝16。这一步具体执行步骤如下：
[0055] (2.1)对参考图像进行扩边处理，在参考图像的左右各增加b个像素，b须满足包含所有双目视图中只存在于一幅视图的场景内容，并令增加的像素灰度值为0，即参考图像高度不变，宽度增加2×b个单位，且增加的部分为黑色。经试验，本实例中取b＝50，既能满足包含所有双目视图中只存在于一副视图的场景内容，又能将搜索点控制在一定范围内，减小计算量和误匹配的可能性。对读入的左视图和右视图进行灰度处理后扩边的结果见图3；
[0056] (2.2)首先将目标图像分为M×N的块，称为宏块，其中M为每块宽度，N为长度，本例中取M＝N＝16。求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，SAD定义为目标图像块与参考图像块之间的绝对值误差和，计算方法如下：
[0057]
[0058] 为其中块的大小为M×N，T(m，n)为目标图像中某一块的左上角点，(m，n)为T的位置坐标；R(p，q)为参考图像中某一块的左上角点，(p，q)为R的位置坐标；GT、GR分别为目标图像和参考图像在某一坐标点的灰度值；i、j为遍历参数，分别依次取从0到M-1和从0到N-1之间的整数；
[0059] 该定义对下文中所有SAD均适用；
[0060] (2.3)对目标图像中某一块在参考图像中寻找最接近块，将搜索起点设置为目标图像中待匹配块的左上角点T(m，n)，在区间[m-b，m+b]内进行匹配，求出[m-b，m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 其中上标M×N代表所使用块的宽度乘以高度，代表尺寸；下标min代表这个SAD是所有匹配位置得到的SAD的最小值；当块的尺寸为正方形，即M＝N时，将这个SAD最小值记为
[0061] 将搜索到的最佳匹配块位置记录下来，并求出目标块与最佳匹配块之间的位移矢量，即视差，记作
[0062]
[0063] 其中上标M×N代表所使用块的宽度乘以高度，表示尺寸；下标(m，n)代表待匹配的目标块的左上角坐标，(i，j)表示视差矢量值，即水平方向和垂直方向上目标块和最佳匹配块的相对位移；当块的尺寸为正方形，即M＝N时，同一块的视差值记作
[0064] 如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M，H-N)(其中W、H分别为目标图像宽和高，M、N分别为匹配块的宽和高)，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤(2.3)。采用这种方法，对目标图像进行遍历之后，将可以得到以M×N块为单位的固定块匹配视差估计结果。使用M×N块进行最佳匹配块搜索的具体步骤参见图4；
[0065] (2.4)将目标图像重新分块，分为(M/2)×(N/2)的块，称为子块，其中每块宽度为M/2，长度为N/2，求出目标图像与参考图像对应位置块的SAD，作为搜索时用于比较的初始值，然后依据如下公式计算每个(M/2)×(N/2)大小块的SAD：
[0066]
[0067] 公式中参数除了块的高度和宽度分别变为步骤(2.2)公式中块高度和宽度的1/2之外，其它参数不变。
[0068] (2.5)按照步骤(2.3)中对目标图像中的每一个块在参考图像中寻找最接近块的方法，将搜索起点设置为目标图像中待匹配块的左上角点T′(m，n)，在区间[m-b，m+b]内进行匹配，求出[m-b，m+b]内每个匹配位置与待匹配块之间的SAD，使SAD值取得最小的参考图像对应位置即为最佳匹配块，并保留这个SAD最小值，记为 将搜索到的最佳匹配块位置记录下来，并求出每一个目标块与最佳匹配块之间视差矢量。此时块的宽和高分别变为步骤(2.3)中块高度和宽度的1/2；
[0069] 如果接受匹配的是目标图像中位于右下角的块，即待匹配块左上角坐标为(W-M/2，H-N/2)(其中W、H分别为目标图像宽和高，M/2、N/2分别为匹配块的宽和高)，则结束匹配，保存所有位置的SAD最小值和对应位置的视差矢量；否则，找到下一个待匹配的目标图像块，返回步骤(2.4)。采用这种方法，对目标图像进行遍历之后，将可以得到以(M/2)×(N/2)块为单位的固定块匹配视差估计结果。块大小分别为M×N和(M/2)×(N/2)时，即为两种不同的匹配模式，下面的步骤将通过判断绝对值误差和SAD的值，来确定对每一个像素点，最终选择哪一种匹配模式。
[0070] (3)按照最小SAD准则，对目标图像的每一个位置进行判断，依据最小SAD准则选择最终的匹配结果，所述匹配结果是M×N块的搜索结果和(M/2)×(N/2)块的搜索结果之一，并将以块为单位的视差扩展至以像素为单位，形成与输入图像尺寸相同的视差场。这一步具体执行步骤如下：
[0071] (3.1)第一次分块时块的宽和高均为第二次分块的两倍，1个宏块在第二次分块中被分为4个子块；1个宏块与4个子块在位置上是对应的；在自适应选择宏块视差还是子块视差时，使用SAD最小准则，即比较1个M×N大小的宏块与最佳匹配块之间的SAD值 和4个(M/2)×(N/2)大小的子块与它们各自的最佳匹配块之间的SAD值之和，记为 如果 则选择宏
块视差 如果 则选择子块视差矩阵，记为
其中(m，n)表示4个子块中最左上角的坐标；符号[·]4表示子块视
差矩阵由与宏块位置对应的4个子块组成：
[0072]
[0073] (3.2)将以块为单位的视差扩展至以像素为单位，形成与输入图像尺寸相同的视差场，对目标图像中的某一宏块，如果在步骤(3.1)中选择了宏块视差 则令宏块中每一点的视差矢量 其中(x，y)为图像坐标系中某点坐标；如果在步骤(3.1)中选择了子块视差矩阵 则令每个子块中的每一点的视差
矢量分别等于这些点所在子块的视差矢量 从而得到两幅由水
平摄像机组，在同一时刻拍摄的两幅图像的视差图。
[0074] 将本发明提出的算法与固定块匹配算法进行比较，可以明显看出，本发明方法得到的视差图较有立体感，能够完整表达因深度不同造成的轮廓边缘，并且运行时间基本等同于固定块匹配算法，因而本发明方法优于固定块匹配算法。输入图像相同，均为标准视频序列“ballroom.yuv”中第3、4视点的第60帧，本发明方法得到的视差图见图5，固定块匹配算法对得到的视差图见图6。由图可见，在固定块匹配算法得到的结果中，使用16×16块进行块匹配，将无法得到视差的细节信息；使用8×8块进行匹配，则由于对纹理信息的容量有限，造成了大量错误匹配。而本发明方法能较好的结合这两种匹配模式的优点，从而得到较好的匹配结果。该视差估计匹配结果的精度，足以应用于双目视频压缩编码，以及虚拟视点绘制。
