一种基于双向加权聚合的实时立体匹配方法，包括以下步骤：(1)计算图像对中各个像素点的匹配代价函数值；(2)对(1)步骤中计算出的匹配代价函数进行行列双向的加权聚合，仅以颜色相似度作为权值参数，设计了一种权值可信度评估机制降低行列双向加权聚合产生的误差；(3)对(2)步骤的聚合结果沿行方向选择视差，设计了一种动态规划与贪心策略相结合的选择策略。实验证明，本发明提出的方法在保证实时性的前提下达到了较高的匹配精度。本发明可应用于各种形式的交互类应用，在科研、教育、娱乐领域均有较为广阔的应用前景。
1.一种基于双向加权聚合的实时立体匹配方法，其特征在于实现步骤如下：（1）根据匹配代价函数计算图像对中各个像素点的匹配代价函数值，计算公式为：其中，d为左右图像的视差，p，为在视差为d的情况下左右图像中的对应点，Ir(p)，Ig(p)，Ib(p)分别表示左图像在点p处的r，g,b值， 分别表示右图像在点 处的r，g,b值，匹配代价函数即为左右图像中对应点的r，g，b值之差的绝对值的和；
对每一个视差di，dmin≤di≤dmax,dmax，dmin为整幅图像的视差范围，对图像中每一点均计算C(p,di)；
（2）对于左图像中的每一个点c，将其周围边长为w1的正方形作为支持窗口，该正方形以c点为中心，w1为预设的支持窗口大小，支持窗口边长均设为33，除c点外支持窗口内所有点叫做c的支持点，用p表示左图像中的支持点；对于右图像中的每一个点 即点c在视差为d时的对应点，将其周围边长为w1的正方形作为支持窗口，该正方形以 点为中心，除点外支持窗口内所有点叫做 的支持点，用 表示右图像中的支持点；在视差为d的情况下，对每一个点c，将其支持窗口内所有匹配代价函数值C(p,d)先后进行行方向和列方向的加权聚合，具体过程如下：A.行方向的加权聚合
先将支持窗口内所有点向该行中心点加权聚合，每行中心点设为c′，行方向加权聚合过程中权值Wh(c′,p)的计算公式为：其中，
其中 为在视差为d时c′的对应点，dis(p1,p2)为p1，p2两个点的颜色相似度，即颜色空间中的距离，T(x)为可信度评估函数，用于对聚合过程中的权值做一个评估，权值越大，可信度越高；权值越小，可信度越低，Tw1，Tw2为预设参数，分别取0.3和0.6；
其中，Hc′表示点c′在支持窗口内所在行的所有点组成的集合；
对于每一个视差d,为图像中所有点进行一次上述的行方向的加权聚合，将这个聚合的结果，作为下一步列方向加权聚合的输入；
对行方向加权聚合的结果进行列方向的加权聚合，列方向加权聚合过程中权值Wv(c,c′)的计算公式为：其中，
T(x)和dis(p1,p2)与行方向聚合过程中的含义及计算方法相同；
其中，Vc表示点c在支持窗口内所在列的所有点组成的集合，CH(c′,d)为行方向加权聚合的结果；
对每一个视差di，dmin≤di≤dmax，对图像中的每一点先后执行上述行方向、列方向的加权聚合过程，最终求得C′W(c,di)；
（3）通过运用步骤（2）的所有列方向的加权聚合结果C′W(c,di)，分别对图像的每一行进行视差选择，所述视差选择采用动态规划与贪心策略相结合的选择策略，具体过程如下：对一行中横坐标为0的点x0，即最左边的点，定义函数F(x0,di)＝C′w(x0,di)；
其中，γ为预设参数，取值为3.27， 为贪心策略选择出的x0点的视差，也就是使C′w(x0,di)取得最小值的di；
为贪心策略选择出的x1点的视差，也就是使C′w(x1,di)取得最小值的di；
以此类推，对于横坐标为w的点xw，w为图像的宽度，xw为一行中最右边的点，选 择 使 F(xw,di) 取 得 最 小 的 di 为 xw 的 视 差 dw，此 时 满 足 公 式中的d作为xw-1的视差dw-1；
以此类推，从右至左选择视差，最终求得x0的视差，得到整行每个像素点的视差值；
通过对每一行进行上述视差选择，最终得到整幅图像的视差图；
（4）对步骤（3）得到的视差图进行噪声过滤，过程如下：当某点c的上、下、左、右四个点的视差均为d时，则将c点的视差置为d;（5）由步骤（4）得到的视差图以及视差范围dmax，dmin求出深度图，过程如下：某点c的深度 其中dc为点c的视差，dmax，dmin为整幅图像的视差范围，点c的视差范围为[0,255]。
一种基于双向加权聚合的实时立体匹配方法
技术领域
[0001] 本发明涉及一种基于行列双向聚合和可变权值的实时立体匹配方法，应用在双目立体视觉领域中，通过立体匹配计算图像对中像素点的视差，进而求得像素点的深度信息，属于计算机图形学和计算机视觉领域。
背景技术
[0002] 立体匹配技术是从多视点图像中求取深度信息的主要方法之一。立体匹配的目标是在给定校正的立体图像之后，寻找参考图像中每个像素点处的视差，即与其在目标图像中对应点之间的列坐标之差。立体匹配技术是计算机图形学、计算机视觉、人工智能、机器人等领域的重要研究方向。
[0003] 总体上，立体匹配方法可以分为全局匹配法和局部匹配法。全局匹配法是通过建立一个全局能量函数来求解每个像素点深度。其优点是匹配精度高，错误率低，但缺点是计算复杂度较高，计算速度较慢，难以达到实时要求。局部匹配法通过引入支持窗口的概念，匹配根据支持窗口进行，优点是运行速度较快，缺点是容易受到噪声点和无纹理区域的影响，匹配精度较低，且支持窗口的大小对算法性能有较大影响，不易确定最优值。实时立体匹配的应用中，一般采用局部立体匹配的方法。
[0004] 基于可变权值的局部算法是一种精度较高的立体匹配算法，该方法取得了接近于全局算法的效果，但时间复杂度较高。有些方法将支持窗口设为一维的纵向窗口，聚合过程中只对匹配代价进行一次纵向聚合，然后利用沿行的动态规划进行视差选择。该方法通过并行编程可以达到实时，但由于匹配代价的纵向聚合不能充分描述位于同一行上的相邻像素点间的相关性，导致该算法的匹配精度比原算法下降了很多。
发明内容
[0005] 本发明的技术解决问题：克服立体匹配算法时间效率提高后精度降低的问题，提出了一种基于支持窗口和可变权值的实时立体匹配方法，该方法在保证实时性的前提下达到了较高的匹配精度。
[0006] 本发明所采取的技术方案是：一种基于支持窗口和可变权值的实时立体匹配方法，步骤如下：
[0007] （1）根据匹配代价函数计算出图像中各点的匹配代价；
[0008] （2）完成（1）步骤后，对支持窗口内的代价函数值先后进行行列加权聚合以提高匹配精度；支持窗口内各点权值仅由该点与中心点颜色相似度决定；聚合过程中设计了一种可信度评估机制，提高匹配结果的可信度，降低由于两次聚合造成的误差的概率和范围；
[0009] （3）根据步骤（2）的聚合结果，在扫描行方向进行动态规划和贪心策略相结合的视差选择；
[0010] （4）完成步骤（3）后，对得到的整幅图像的视差进行优化，去除噪声点，使整个视差选择的结果更加精确；
[0011] （5）由各点视差图以及整幅图像的视差范围求出各点深度。
[0012] 本发明的原理是：
[0013] 所述的立体匹配过程中，通过将行列双向聚合应用于加权聚合中，降低了加权聚合的时间复杂度，提高了算法的并行度，使算法能够使用GPU并行加速，从而实现实时。
[0014] 所述的在聚合过程采用的行列双向聚合，将对一个二维支持窗口的加权聚合转化为对两个相互垂直的一维支持窗口的加权聚合，由于所有像素点在行方向聚合与列方向聚合这两个过程中分别是相互独立的，所以可以并行执行。首先所有的像素点并行执行行方向加权聚合，待聚合完毕后再进行并行的列方向加权聚合，从而大大降低了加权聚合过程的并行度以及时间消耗，为立体匹配算法的实时化提供了可能。
[0015] 所述的权值计算公式，只使用颜色相似度作为权值参数，去除了其他因素对权值的干扰，而且降低了计算量。
[0016] 所述的可信度评估机制对行列双向加权聚合过程中产生的误差进行控制，减小了误差产生的概率和范围。
[0017] 所述的动态规划与贪心相结合的视差选择，在保持动态规划在行方向上平滑的优点的同时，贪心策略的适时介入将使视差跳变处的视差选择更为准确。
[0018] 与现有技术相比，本发明的优点是：
[0019] （1）本发明通过行列双向聚合和可变权值聚合的结合，一方面降低了算法的时间复杂度，另一方面通过一种可信度评估机制降低两者结合带来的精度损失。通过GPU加速，对于320*240大小的图像，本算法已实现实时。本算法在一个实时应用中的截图如图7所示，其中7(a)为两幅图像中的左图像，7(b)为实时求取的深度图；
[0020] （2）本发明中的视差选择采用了动态规划和贪心策略相结合的方法。这种结合的策略在保留动态规划算法取得行方向上平滑性较好的优点的同时，又避免了由此带来的过度平滑以至于造成视差边界模糊的不足。在动态规划选择视差的过程中，贪心策略的适时介入不仅不会增加算法的复杂度，而且在视差跳变处取得更准确的视差值，本算法在middlebury平台上的测试结果如表1所示。其中tuskuba，venus，teddy，cones是middlebury平台上提供的4组dataset，nonocc，all，disc为三种不同的误差计算方式，AdaptiveWeight，RealTimeABW，RealTimeBP，RealTime Var，RTCensus，Real-Time GPU为middlebury上的实时算法。Average Rank为算法四组dataset的平均排名，Average Error为四组dataset的平均误差率。误差率是图像中视差错误的像素点的个数占图像总像素点的比例。
[0021] 表1 middlebury平台的测评数据
[0022]
[0023] （3）本发明中的权值的计算方式，在颜色相似度、空间距离、颜色变化连续性等众多可选择因素中，只选择颜色相似度作为权值的影响因素，去除了其他因素对权值计算的影响，既降低了计算复杂度，又大大降低了聚合过程中的噪声干扰，使聚合结果更能反映窗口的相似度，使得视差选择更加精确。实验表明，本发明的匹配精度接近于非实时的可变权值算法的精度，利用本发明对middlebury上的4组dataset求得的深度图如图6所示，其中，(a)为两幅图像中的左图像，(b)为ground truths，(c)为本算法求得的深度图。
附图说明
[0024] 图1是本发明方法的实现流程图；
[0025] 图2是本发明中加权聚合的示意图；
[0026] 图3是本发明中行列双向加权聚合的示意图；
[0027] 图4是本发明中颜色空间中三个点的位置示意图；
[0028] 图5是本发明中动态规划与贪心策略相结合的视差选择过程示意图；
[0029] 图6是根据本发明对middlebury平台的dataset的匹配结果示意图；从上之下分别为middlybury平台上的tuskuba，venus，teddy，cones。(a)为两幅图像中的左图像，(b)为ground truths，(c)为本算法求得的深度图；
[0030] 图7是根据本发明在一个实时立体匹配的应用中某时刻的截图,7(a)为左图像，7(b)为深度图。
具体实施方式
[0031] 本发明分为五个部分，如图1所示。
[0032] 第一，匹配代价函数的计算。
[0033] 本发明采用的匹配代价函数为：
[0034]
[0035] 其中，d为左右图像的视差，p，为在视差为d的情况下左右图像中的对应点，Ir(p)，Ig(p)，Ib(p)分别表示左图像在点p处的r，g，b值， 分别表示右图像在点 处的r，g，b值。匹配代价函数即为左右图像中对应点的r，g，b值之差的绝对值的和。理论上，左右图像对应的像素点的匹配代价为0。由于在实际图像中，存在着噪声等干扰因素，会影响匹配代价函数的精确度，因此一般选取匹配代价最小时对应的视差。
[0036] 对每一个视差di（dmin≤di≤dmax）,对图像中每一点计算C(p,di)。
[0037] 第二，匹配代价的双向加权聚合。
[0038] 为了降低噪声等因素的干扰，匹配代价一般不直接作为选择视差的依据，通常需要首先在一个支持窗口内进行聚合，然后根据聚合后的结果进行匹配求解。对于左图像中的每一个点c，将其周围边长为w1的正方形作为支持窗口（该正方形以c点为中心，w1为预设的支持窗口大小，本专利中支持窗口边长均设为33），支持窗口内所有点（除c点外）叫做c的支持点，用p表示左图像中的支持点。对于右图像中的每一个点（点c的对应点），将其周围边长为w1的正方形作为支持窗口（该正方形以 点为中心），支持窗口内所有点（除 点外）叫做 的支持点，用 表示右图像中的支持点。
[0039] 对支持窗口内各点进行加权聚合的公式为：
[0040]
[0041] 其中，c和 为左右图像中视差为d时的对应点，p与 分别是位于c、支持窗口内的点，w(c,p)， 分别表示对p对c，对 的支持权值（下一节中会有详细说明），Wc为以c为中心点的支持窗口中所有点组成的集合，如图2所示。2
[0042] 公式2的时间复杂度为O(whd)，w和h分别为图像的横向和纵向的像素点个数，d为支持窗口的边长。为了降低计算的复杂度，将双向聚合的策略应用于加权聚合的过程中，将聚合时所用的二维支持窗口改为两个相互垂直的一维支持窗口，从而将整个的聚合过程分为行方向和列方向两步进行。
[0043] 对每一对对应点c和 在视差为d的情况下将其支持窗口内所有匹配代价函数值C(p,d)先后进行行方向和列方向的加权聚合，具体过程如下：
[0044] 1.行方向的加权聚合
[0045] 先将支持窗口内所有点向该行中心点加权聚合，每行中心点设为c′，如图3(a)所示。行方向加权聚合过程中权值Wh(c′,p)的计算公式为：
[0046]
[0047] 其中，
[0048]
[0049]
[0050]
[0051] 其中 为在视差为d时c′的对应点，dis(p1,p2)为p1，p2两个点的颜色相似度（颜色空间中的距离），T(x)为本发明设计的一个可信度评估函数，用于对聚合过程中的权值做一个评估，权值越大，可信度越高；权值越小，可信度越低，Tw1，Tw2为预设参数，分别取0.3和0.6，T(x)可以取值为0、0.5或1。
[0052] 行方向加权聚合的公式为：
[0053]
[0054] 其中，Hc′表示点c′在支持窗口内所在行的所有点组成的集合。
[0055] 对于每一个视差d，为图像中所有点进行一次上述的行方向的加权聚合，该过程的示意图如图3(a)所示。将这个聚合的结果，作为下一步列方向加权聚合的输入。
[0056] 2.列方向的加权聚合
[0057] 列方向加权聚合过程中权值Wv(c,c′)的计算公式为：
[0058]
[0059] 其中，
[0060]
[0061] T(x)和dis(p1,p2)与行方向聚合过程中的含义及计算方法一样。列方向加权聚合的公式为：
[0062]
[0063] 其中，Vc表示点c在支持窗口内所在列的所有点组成的集合，CH(c′,d)为行方向加权聚合的结果。列方向加权聚合过程的示意图如图3(b)所示。
[0064] 对每一个视差di（dmin≤di≤dmax），对图像中的每一点先后执行上述行方向、列方向的加权聚合过程，最终求得C′W(c,di)。
[0065] 公式12的时间复杂度为O(whd)，其中，w和h分别为图像的横向和纵向的像素点个数，d为支持窗口的边长。
[0066] 第三，根据聚合后的匹配代价选择视差。
[0067] 1.用动态规划的方法选择一行的视差
[0068] 动态规划在立体视觉中应用非常广泛，许多实时方法均采用动态规划策略进行视差选择。原因是动态规划方法一方面可以得到行方向较平滑的结果，另一方面较低的时间复杂度。
[0069] 定义动态规划的递推公式为：
[0070]j
[0071] 对于任一点c(x，y)和对应于c点的视差d(c)，遍历点c(x-1，y)对应的所有视j j差值，求解相应的F(c，d)与d 和c的平滑度|γ*(d(c)-d)|,其中，γ为预设参数，取值为3.27。
[0072] 2.动态规划中加入视差平滑约束
[0073] 视差平滑约束是指像素点的视差值与其周围像素点的视差通常相差不大。对于点c(x，y)，设其视差为d(c)，则与其相邻的8个像素点的视差范围是[d(p)-1,d(p)+1]，因此j若求解点p(x，y)在视差为d时的耗费F(c，d)，不需要遍历所有视差值对应的F(c)，只需考虑d(c)-1，d(c)，d(c)+1三种情况，相应的递推公式改为：
[0074]
[0075] 3.在动态规划中加入贪心策略
[0076] 动态规划的缺点也显而易见，由于追求全局最优，因此计算的结果往往是相邻像素点的视差很接近，行方向视差渐变，在视差变化较大的边界处造成边界模糊。
[0077] WTA(winner-take-all)是贪心策略在立体视觉中的一种应用。其基本原理是选择视差时只考虑该点的匹配代价函数的聚合结果，从中选择代价最小的视差。WTA可以选择出各点的最优视差，但由于噪声等因素的干扰，容易造成一些离散的噪声点。
[0078] 基于以上考虑，将两种策略结合起来用于选择视差。递推公式相应改为：
[0079]
[0080] 其中，dWTA为使C′w(cj,d)取得最小值的视差d。
[0081] 视差选择过程的示意图如图4所示。在从左往右求解的过程中，当搜索到图4中第4列的时候，除了比较视差为2、3、4时的能量函数F(c,2)F(c,3)F(c,4)的值之外，还应考虑在该点取最优视差，即d＝1时能量函数F(c，1)的值，从这四个视差中根据公式15选择最优视差。如果只用动态规划策略，则图5对应的视差应为：2,2,3,3,3,2。使用动态规划和贪心策略相结合的策略选择的视差为：2,2,3,3,1,0。由此可见，单纯动态规划在视差跳变处只能取得渐变视差，加入贪心策略之后，可以使同一行中视差呈现跳变的特点。
[0082] 第四，噪声视差点的过滤。
[0083] 在进行沿行的动态规划后得到的视差图可能会包含较明显的噪声点，可以通过简单的滤波方法去掉。具体的做法为：如果一个像素点上下左右邻域像素的视差均为d，则将该像素的视差值置为d；其它情况保持视差值不变。
[0084] 第五，求取深度图。
[0085] 由第四步得到的视差图以及视差范围dmax，dmin求出深度图，过程如下：某点c的深度 其中dc为点c的视差，dmax，dmin为整幅图像的视差范围。点c的视差范围为[0,255]。
[0086] 实验证明，本发明提出的方法在保证实时性的前提下达到了较高的匹配精度。本发明可应用于各种形式的交互类应用，在科研、教育、娱乐领域均有较为广阔的应用前景。
[0087] 本发明未详细阐述部分属于本领域公知技术。
