一种基于最邻近搜索的光流并行加速方法

摘要

本发明公开了一种基于最邻近搜索的光流并行加速方法，对Barnes最邻近算法的光流修正算法进行修改，采用梯度下降法修正光流，提高了效率；同时对光流的传播过程进行修改，使其易于在GPU上实现并行运算来进行加速。将本发明用于光流计算，可明显提高运算速度，同时保证一定的精确度。

权利要求

1.一种基于最邻近搜索的光流并行加速方法，其特征在于，包括以下步骤：

步骤1：输入两帧图像，转化为灰度图，并进行高斯滤波，以减少图像噪声；

步骤2：分别为滤波后的两幅图像进行金字塔式分层，按照分辨率从小到大的顺序排列，并随机地初始化分辨率最小层的图像的光流场为(0,1)之间的均匀分布，并将其光流场图像作为当前层图像；

步骤3：计算当前层图像的梯度值，包括x方向梯度值与y方向梯度值，并对得出的梯度值进行高斯滤波；

步骤4：利用Barnes算法，对当前层图像的光流场，采用改进的传播修正的方法进行多次改进的传播修正，每次传播时，每行或每列的传播过程是并行的，传播修正过程中采用梯度值作为匹配准则，采用梯度下降法修正光流场，得到修正后的光流场图像；改进的传播修正的方法为：对每一层图像的光流场，都进行四次不同方向的传播修正，方向依次为从左到右，从上到下，从右到左，从下到上，在传播修正时，当前块的计算仅依赖于相邻的一个块，同时将好的结果也只传播给相邻的一个块，从而使得每一行或每一列的传播变得独立，容易在GPU上并行实现；步骤5：将得到的光流场放大至图像金字塔中的相邻层图像的尺寸大小，放大过程中使用双三次插值；

步骤6：将放大后的光流场图像作为当前层图像，重复步骤3、4和5，直到光流场图像尺寸达到原始图像大小。

2.根据权利要求1所述的一种基于最邻近搜索的光流并行加速方法，其特征在于：在步骤4中，梯度下降法修正光流场的过程为：经传播后某点光流矢量为(u,v)，误差函数为E(u,v)，则修正光流矢量为：其中，u，v是光流矢量，分别表示横纵坐标；Δu和Δv分别为横纵坐标的微分，取0.001，α为步长，采用动态步长的策略，步长α设置为金字塔层数的函数：其中l为当前金字塔层数，L为图像金字塔总层数。

说明书

一种基于最邻近搜索的光流并行加速方法

技术领域

[0001] 本发明属于图像处理技术领域，具体涉及一种基于最邻近搜索的光流并行加速方法。

背景技术

[0002] 光流(Optical Flow)的概念是Gibson于1950年首先提出的，它是由相机和场景相对运动产生的，表示的是图像中各像素瞬时相对运动的速度情况。光流场是指图像灰度模式的表面运动。光流计算是当今计算机视觉的热点之一，光流算法被广泛应用于运动目标检测与跟踪、机器人导航、三维重建等领域。80年代初期，Horn和Schunck提出了建立在光流平滑性假设基础上的稠密光流算法，为光流计算的发展起了奠基性作用，之后学者们相继提出了多种计算光流的算法。根据数学方法和相应的理论基础，计算光流的方法分为基于梯度的方法、基于块匹配的方法、基于能量的方法和基于相位的方法。

[0003] 与其他计算光流的方法相比，基于块匹配的光流法具有运算速度快、易于硬件实现的优点。块匹配是图像处理中很常见的一种问题，尤其在视频编码中的运动估计中应用广泛，许多年来，学者们已经提出了许多块匹配的算法，如三步法、四步法、菱形法等。为了进一步提高运算速度，学者们提出了近似块匹配算法，如局部搜索，降低维度等，虽然这些方法得到的结果只是精确匹配的近似，但由于其大大减少了运算量而被广泛应用于各种高层图像处理中。

[0004] 光流是一种简单实用的图像运动的表达方式，定义为动态图像的几何变化和辐射度变化的全面表示。光流的研究是利用图像序列中的像素强度数据的时域变化和相关性来确定各自像素位置的“运动”，即研究图像灰度在时间上的变化与景象中物体结构及其运动的关系。

[0005] 光流法检测运动物体的基本原理是：给图像中的每一个像素点赋予一个速度矢量，这就形成了一个图像运动场，在运动的一个特定时刻，图像上的点与三维物体上的点一一对应，这种对应关系可由投影关系得到，根据各个像素点的速度矢量特征，可以对图像进行动态分析。如果图像中没有运动物体，则光流矢量在整个图像区域是连续变化的。当图像中有运动物体时，目标和图像背景存在相对运动，运动物体所形成的速度矢量必然和邻域背景速度矢量不同，从而检测出运动物体及位置。

[0006] 目前大多数的光流计算方法相当复杂，计算量巨大，耗时长，实时性和实用性都较差。本发明对光流的计算实行并行加速办法，能够在保证精度的同时提高运算速度。

发明内容

[0007] 本发明的技术解决方案：为克服目前光流场计算耗时长的不足，提供一种基于最邻近搜索的并行加速光流方法，该方法通过利用GPU并行化计算进行加速计算，同时能够保证一定精确度。

[0008] 本发明采用的技术方案为：一种基于最邻近搜索的光流并行加速方法，包括下列步骤：

[0009] 步骤1：输入两帧图像，转化为灰度图，并进行高斯滤波，以减少图像噪声；

[0010] 步骤2：分别为滤波后的两幅图像进行金字塔式分层，按照分辨率从小到大的顺序排列，并随机地初始化分辨率最小层的图像的光流场为(0,1)之间的均匀分布，并将其光流场图像作为当前层图像；

[0011] 步骤3：计算当前层图像的梯度值，包括x方向梯度值与y方向梯度值，并对得出的梯度值进行高斯滤波；

[0012] 步骤4：利用Barnes算法，对当前层图像的光流场，采用改进的传播修正的方法进行多次改进的传播修正，每次传播时，每行或每列的传播过程是并行的，传播修正过程中采用梯度值作为匹配准则，采用梯度下降法修正光流，得到修正后的光流场图像；

[0013] 步骤5：将得到的光流场放大至图像金字塔中的相邻层图像的尺寸大小，放大过程中使用双三次插值；

[0014] 步骤6：将放大后的光流场图像作为当前层图像，重复步骤3、4和5，直到光流场图像尺寸达到原始图像大小。

[0015] 在步骤4中，改进的传播修正的方法为：

[0016] 为了得到误差函数最小时的运动矢量，即真正的光流失量，使用最优化算法中常用的梯度下降法。假设经传播后某点光流矢量为(u,v)，误差函数为E(u,v)，那么修正光流矢量为：

[0017]

[0018] 其中，△u和△v分别为横纵坐标的微分，取0.001，α为步长，本发明采用动态步长的策略，步长α可以设置为金字塔层数的函数：

[0019]

[0020] 其中l为当前金字塔层数，L为图像金字塔总层数。

[0021] 在步骤4中，改进的可以并行计算传播修正的方法为：

[0022] 对每一层图像的光流场，都进行四次不同方向的传播修正，方向依次为从左到右，从上到下，从右到左，从下到上。在传播修正时，当前块的计算仅依赖于相邻的一个块，同时将好的结果也只传播给相邻的一个块，从而使得每一行或每一列的传播变得独立，容易在GPU上并行实现。

[0023] 综上所述，由于采用了上述技术方案，本发明的有益效果为：本发明在对光流场进行迭代修正的过程中仅使用传播的方式，通过设置在不同分辨率下梯度下降法中的不同步长，提高了光流修正的效率。对每一层的光流场传播，使用四次单一方向，使得该过程可以并行运算，有利于实现利用GPU并行计算的加速过程。

附图说明

[0024] 图1为本发明方法实现流程图；

[0025] 图2本发明中传播过程示意图。

具体实施方式

[0026] 为使本发明的目的与技术方案更加清楚，下面结合实施方式与示意图，对本发明作进一步详细描述。

[0027] 如图1所示，本发明具体实现如下：

[0028] 步骤1：读入待处理的两帧图像，将其转换为灰度图，并进行高斯滤波，以减少噪声。

[0029] 步骤2：分别为滤波后的两幅图像进行金字塔式分层，每层图像的尺寸均为上一层的0.9倍，视原图的尺寸将其划分为20至30层。

[0030] 步骤3：随机初始化最底层图像的光流场，使其为(0,1)之间的均匀分布。

[0031] 步骤4：分别计算该层图像的x方向与y方向的梯度值，并对计算结果进行高斯滤波。

[0032] 步骤5：对该层图像的光流场，分别进行四次不同方向的传播修正，方向分别为从左到右、从上到下、从右到左、从下到上，每次传播时，各行或各列的传播是并行进行的。传播过程中采用梯度值作为匹配准则，采用梯度下降法修正光流。如图2所示，例如进行从上到下的传播时，3列图像块中的每一列的传播都是独立的，与其他列无关，因而可以并行地计算这三列的传播过程。

[0033] 步骤6：采用梯度值匹配的准则为：

[0034] 将图像中两个像素点的灰度表示为与时间、空间位置的函数形式，即：

[0035] G1(x,y)＝f(x,y,t)

[0036] G0(x+u,y+v)＝f(x+u,y+v,t+△t)

[0037] 使用泰勒公式将展开，忽略高阶无穷小项并认为时间无限趋近于0，得到：

[0038]

[0039] 移项后得到：

[0040]

[0041] 设图像块的大小是M×N，则图像块的梯度运动矢量(u，v)定义为：

[0042]

[0043] 要求上式的最小值，可以用最小二乘法得到关于(u,v)T的非齐次方程组，然后得到新的匹配准则：

[0044]

[0045] 其中m(i,j)代表窗口权重，表示了块中每个像素点对匹配结果的影响，在实际计算中，一般用以ρ为半径的高斯函数代替，并计算高斯函数与图像序列梯度差值之间的卷积。

[0046] 步骤7：修正光流的梯度下降法为：

[0047] 对于某个块来说，其匹配误差可以看成是其运动矢量的函数，其真实的光流矢量就是使误差函数最小时的运动矢量。假设经传播后某点光流矢量为(u,v)，误差函数为E(u,v)，那么修正光流矢量为：

[0048]

[0049] 其中，△u和△v取0.001，α为步长，本发明采用动态步长的策略，在接近图像金字塔顶层时，误差一般较大，将步长设置大一些；当接近金字塔底层时，步长设置小一些。步长α设置为金字塔层数的函数：

[0050]

[0051] 其中l为当前金字塔层数，L为图像金字塔总层数。

[0052] 步骤8：将得到的光流场放大至上一层图像的尺寸，放大过程中使用双三次插值，函数f在点(x,y)处的值通过矩形网格中最近的16个点的加权平均值得到，其计算公式为：

[0053] 步骤9：重复步骤4～8，直到光流场达到原始图像的尺寸，即得到整幅图像的光流场。光流算法结束。

[0054] 提供以上实施例仅仅是为了描述本发明的目的，而并非要限制本发明的范围。本发明的范围由所附权利要求限定。不脱离本发明的精神和原理而做出的各种等同替换和修改，均应涵盖在本发明的范围之内。