基于增量式高次布尔能量最小化的视频前后景分割方法

摘要

基于增量式高次布尔能量最小化的视频前后景分割方法属于视频处理领域；该方法输入视频；再构建当前帧的高次布尔能量函数；通过Ishikawa等价变换，将高次布尔能量函数等效变换为二次布尔能量函数；利用二次布尔能量函数，构建高次布尔能量函数对应的s/t图模型；计算当前帧高次布尔能量函数对应的剩余s/t图；计算当前帧高次布尔能量函数对应的剩余s/t图最大流；输出该剩余s/t图最大流对应的前后景分割后的视频帧；逐帧进行以上操作直至最后一帧；本发明既能利用高次布尔能量函数表示复杂的视觉信息，又能减少高次布尔能量最小化过程中的重复运算，从而达到比二次布尔能量函数更精确和比独立帧高次布尔能量最小化更高效的效果。

说明书

技术领域

基于增量式高次布尔能量最小化的视频前后景分割方法属于视频处理领域，具体涉及一种视频前后景的分割方法。

背景技术

视频前后景分割一直是机器视觉领域的研究热点，是进一步进行目标识别和目标跟踪的必要步骤。近年来，此方面的研究成果不断丰富，涌现出了各式各样的前后景分割方法，基于布尔能量最小化的前后景分割是其中的一种有效方法。

Y.Boykov等人（IEEE Transactions on Pattern Analysis and Machine Intelligence,23(11):1222-1239,2001）和C.Couprie等人（IEEE Transactions on Pattern Analysis and MachineIntelligence,33(7):1384-1399,2011）的研究成果表明，基于二次布尔能量（即交叉项最高次为二次的多元0-1多项式）最小化的前后景分割方法一般应用于单幅或少量图像处理的任务中。实验证明，图割算法是求解二次布尔能量最小化的最有效的方法之一。图割算法通常将图像中的每个像素看作一个布尔变量，按照一定的规则构建二次布尔能量函数，然后根据能量函数构建相应的s/t图，二次布尔能量函数中每一布尔变量对应s/t图的一个节点，再利用最小割/最大流算法（IEEE Transactions on Pattern Analysis and MachineIntelligence,26(9):1124-1137,2004）切割s/t图得到s/t图的最小割。V.Kolmogorov等人（IEEE Transactions on Pattern Analysis and Machine Intelligence,26(2):147-159,2004）的研究成果表明s/t图最小割时s/t图各节点对应变量的取值使得二次布尔能量最小化。在单幅图像的前后景分割任务（International Journal of Computer Vision,70(2):109-131,2006）中，将二次布尔能量最小化时取值为1的布尔变量相对应的像素标为前景，取值为0的布尔能量对应的像素标为背景，便得到了最优的前后景分割方式。视频是图像的有序序列，将以上方法直接应用在视频的前后景分割中时面临以下问题：(1)需每一帧都独立的求解布尔能量最小化，时间复杂度太高；(2)传统的二次布尔能量函数最多只能描述二维关系，即两个变量之间的差异，能量函数包含的信息不够丰富，对于更为复杂的视觉信息无法描述。

为解决连续帧独立求解最小二次布尔能量时复杂度高的问题，Kohli考虑了视频帧序列中前后两帧之间的关联性，利用前一帧的二次布尔能量最小化结果构建当前帧的s/t图，避免了每一帧都独立求解二次布尔能量最小化中的重复运算（IEEE Transactions on PatternAnalysis and Machine Intelligence,29(12):2079-2088,2007）。但是这种方法中的二次布尔能量无法刻画复杂的视觉信息。

近年来，布尔能量的广义模型——高次布尔能量（即交叉项最高次大于二次的多元0-1多项式）越来越多的应用于复杂视觉信息的建模。Kohli等人提出了基于Potts模型的高次能量最小化方法（IEEE Transactions on Pattern Analysis and Machine Intelligence,31(9):1645-1656,2009）。Ishikawa提出了一种将高次项变换为二次项的方法（IEEE Transactionson Pattern Analysis and Machine Intelligence,33(6):1234-1249,2011），从而使得高次能量最小化问题可以转化为二次能量最小化问题。研究资料表明，目前的高次布尔能量主要应用于单幅或少量图像中的复杂视觉信息刻画，若将其应用于视频帧序列的前后景分割中，则仍需每一帧都独立的求解高次布尔能量最小化。这种独立帧处理方式没有考虑视频前后帧之间的关联信息，重复运算量大，处理效率低。

发明内容

为了解决上述问题，本发明公开了一种基于增量式高次布尔能量最小化的视频前后景分割方法，该方法既能利用高次布尔能量函数表示复杂的视觉信息，又能减少高次布尔能量最小化过程中的重复运算，从而达到比二次布尔能量函数更精确和比独立帧高次布尔能量最小化更高效的效果。

本发明的目的是这样实现的：

基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于包括以下步骤：

步骤a、输入视频；

步骤b、构建当前帧的高次布尔能量函数；

步骤c、通过Ishikawa等价变换，将步骤b得到的高次布尔能量函数等效变换为二次布尔能量函数；

步骤d、利用步骤c得到的二次布尔能量函数，构建步骤b中高次布尔能量函数对应的s/t图模型；

步骤e、计算当前帧高次布尔能量函数对应的剩余s/t图；

步骤f、计算当前帧高次布尔能量函数对应的剩余s/t图最大流；

步骤g、输出前后景分割后的视频。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于所述的步骤b具体为：

在首帧用线段简略标明前景和背景的区域，线段上划到的少量像素作为已知分割结果的像素点，然后按照如下公式进行计算，

$>E\left(x\right)=\underset{i\in v}{\Sigma }{\psi }_i\left(x_i\right)+\underset{i\in v,j\in N_i}{\Sigma }{\psi }_{i,j}(x_i,x_j)+\underset{c\in C}{\Sigma }{\psi }_c\left(x_c\right)$>

式中，N_i是像素D_i的邻域，变量ν={1,2,...,N}，变量x={x₁,x₂,...,xN}，变量x中的元素x_i代表像素D_i，且x_i∈{1,2,...,N_s}，其中N_s为将要划分为的区域数，对于前后景分割来说，N_s为2；一次项ψ_i(x_i)由RGB分布H_α,α=1,...,N_s详细描述，具体为：

ψ_i(x_i)=-logp(D_i|H_α),x_i=α

二次项ψ_i,j(x_i,x_j)表示某邻域内两像素间的不一致性，ψ_i,j(x_i,x_j)的值具体为：

$>{\psi }_{i,j}\left(x_{i,}{x}_j\right)=\left(\begin{array}{ccc}{\lambda }_1+{\lambda }_2\exp \left(\frac{{-g}^2(i,j)}{2{\sigma }^2}\right)& \mathrm{if}& x_i\ne x_j\\ 0,& \mathrm{if}& x_i=x_j\end{array}\right)$>

式中，λ₁，λ₂，σ为一些参数，σ²为图像中噪声的方差，g(i,j)代表像素D_i和D_j之间RGB值之间的差异；ψ_c(x_c)是高次项，反映多个变量之间的不一致性，其中c是代表图像D分区D_c={D_i,i∈c}中的一个子集，C是所有子集的集合，ψ_c(x_c)具体为：

$>{\psi }_c\left(x_c\right)=\left(\begin{array}{cc}{\lambda }_{3}G(c,s),& \mathrm{if}{x}_i=s,\forall i\in c\\ {\lambda }_4,& \mathrm{otherwise}\end{array}\right)$>

式中，s∈{1,2,...,N_s}，G(c,s)是分区D_c和所有属于P_s的分区中RGB值的最小不同，P_s表示N_p×N_p的RGB分区，可以看到以上能量函数倾向于让P_s中与分区D_c相似的分区取值为s；变量x不同的取值方式代表了不同的分割方式，而最优的前后景分割方式对应高次布尔能量的最小化结果。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于所述的步骤c具体为：

利用下式进行计算：

$>{\mathrm{ax}}_1{x}_2{x}_3...x_n=\left(\begin{array}{cc}\underset{w\in B}{\min }\mathrm{aw}\{s_1-(d-1)\}& a<0\\ a\underset{w_1,...w_{n_d}\in B}{\min }\underset{i=1}{\overset{n_d}{\Sigma }}{w}_i(c_{i,d}(-s_1+2i)-1)+{\mathrm{as}}_2& a>0\end{array}\right)$>

式中，B为二进制标签集合，B={0,1}，x₁,x₂,...,x_n为二进制变量，代表图像中的像素，w和w_i为增加的辅助变量，a为常数，d为奇数，s₁和s₂的值分别为：

$>s_1=\underset{i=1}{\overset{d}{\Sigma }}{x}_i$>

$>s_2=\underset{i=1}{\overset{d-1}{\Sigma }}\underset{j=i+1}{\overset{d}{\Sigma }}{x}_i{x}_j=\frac{s_1(s_1-1)}{2}$>

其中：

上述基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于所述的步骤d具体为：

在对应的s/t图模型中，顶点s和t分别代表前景和背景，除s和t外的每一个节点代表能量函数中的一个变量，其中能量函数中一次项系数为节点与顶点之间连边(t-link)的容量，表示视频帧中像素点划为前景或背景所付出的代价，二次项系数为某邻域内节点之间连边(n-link)的容量，表示某邻域内像素点之间的不一致性。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于所述的步骤e具体为：

将当前帧高次能量函数对应的s/t图各个连边的容量减去前一帧高次能量函数对应的最大流，得到当前帧剩余s/t图各个连边的容量；如果

当前帧的剩余s/t图的连边容量满足边界容量和质量平衡约束（即剩余图各连边容量全为正），则当前帧的剩余s/t图无须改变，可以继续到下一步处理；

当前帧的剩余s/t图连边容量不满足边界容量和质量平衡约束（即剩余图各连边容量有负值），则通过动态算法进行再参数化，使得剩余s/t图的连边容量更新，从而得到与负容量剩余s/t图等价的非负容量剩余s/t图，并且以此非负容量剩余s/t图作为当前帧的剩余s/t图。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，其特征在于所述的步骤f具体为：

利用最小割/最大流法计算出当前帧剩余s/t图的最大流（视频首帧直接求解其s/t图最大流即可），从而得到当前帧的高次布尔能量的最优解；最优解为1的变量对应的像素被分割为前景，最优解为0的像素被分割为后景，当前帧的前景和后景像素得以分割。

本发明方法首先输入视频；然后构建当前帧的高次布尔能量函数；再通过Ishikawa等价变换，将高次布尔能量函数等效变换为二次布尔能量函数；利用二次布尔能量函数，构建高次布尔能量函数对应的s/t图模型；计算当前帧高次布尔能量函数对应的剩余s/t图；计算当前帧高次布尔能量函数对应的剩余s/t图最大流；最后输出前后景分割后的视频；本发明方法，既能利用高次布尔能量函数表示复杂的视觉信息，又能减少高次布尔能量最小化过程中的重复运算，从而达到比二次布尔能量函数更精确和比独立帧高次布尔能量最小化更高效的效果。

附图说明

图1是本发明方法流程图。

图2是具体实施例所用的图像。

图3是二次布尔能量函数构建高次布尔能量函数对应的s/t图。

具体实施方式

下面结合附图对本发明具体实施方式作进一步详细描述。

本实施例的基于增量式高次布尔能量最小化的视频前后景分割方法，流程图如图1所示，该方法包括以下步骤：

步骤a、输入视频；

步骤b、构建当前帧的高次布尔能量函数；

步骤c、通过Ishikawa等价变换，将步骤b得到的高次布尔能量函数等效变换为二次布尔能量函数；

步骤d、利用步骤c得到的二次布尔能量函数，构建步骤a中高次布尔能量函数对应的s/t图模型；

步骤e、计算当前帧高次布尔能量函数对应的剩余s/t图；

步骤f、计算当前帧高次布尔能量函数对应的剩余s/t图最大流；

步骤g、输出前后景分割后的视频。

本实施例以图2所示的图片为例，所述的步骤b具体为：

加载步骤a得到的视频后，在首帧用线段简略标明前景和背景的区域，线段上划到的少量像素作为已知分割结果的像素点，图2中人体上划线的少量像素被分割为已知前景像素，背景上两条划线上的少量像素被分割为已知背景像素，按照如下公式进行计算，

$>E\left(x\right)=\underset{i\in v}{\Sigma }{\psi }_i\left(x_i\right)+\underset{i\in v,j\in N_i}{\Sigma }{\psi }_{i,j}(x_i,x_j)+\underset{c\in C}{\Sigma }{\psi }_c\left(x_c\right)$>

式中，N_i是像素D_i的邻域，变量ν={1,2,...,N}，变量x={x₁,x₂,...,x_N}，变量x中的元素x_i代表像素D_i，且x_i∈{1,2,...,N_s}，其中N_s为将要划分为的区域数，对于前后景分割来说，N_s为2；一次项ψ_i(x_i)由RGB分布H_α,α=1,...,N_s详细描述，具体为：

ψ_i(x_i)=-logp(D_i|H_α),x_i=α

二次项ψ_i,j(x_i,x_j)表示某邻域内两像素间的不一致性，ψ_i,j(x_i,x_j)的值具体为：

$>{\psi }_{i,j}\left(x_{i,}{x}_j\right)=\left(\begin{array}{ccc}{\lambda }_1+{\lambda }_2\exp \left(\frac{{-g}^2(i,j)}{2{\sigma }^2}\right)& \mathrm{if}& x_i\ne x_j\\ 0,& \mathrm{if}& x_i=x_j\end{array}\right)$>

式中，λ₁，λ₂，σ为一些参数，σ²为图像中噪声的方差，g(i,j)代表像素D_i和D_j之间RGB值之间的差异；ψ_c(x_c)是高次项，反映多个变量之间的不一致性，其中c是代表图像D分区D_c={D_i,i∈c}中的一个子集，C是所有子集的集合，ψ_c(x_c)具体为：

$>{\psi }_c\left(x_c\right)=\left(\begin{array}{cc}{\lambda }_{3}G(c,s),& \mathrm{if}{x}_i=s,\forall i\in c\\ {\lambda }_4,& \mathrm{otherwise}\end{array}\right)$>

式中，s∈{1,2,...,N_s}，G(c,s)是分区D_c和所有属于P_s的分区中RGB值的最小不同，P_s表示N_p×N_p的RGB分区，可以看到以上能量函数倾向于让P_s中与分区D_c相似的分区取值为s；变量x不同的取值方式代表了不同的分割方式，而最优的前后景分割方式对应高次布尔能量的最小化结果。

高次项构造方法记载于：IEEE Transactions on Pattern Analysis and Machine Intelligence,31(9):1645-1656,2009。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，所述的步骤c具体为：

利用下式进行计算：

$>{\mathrm{ax}}_1{x}_2{x}_3...x_n=\left(\begin{array}{cc}\underset{w\in B}{\min }\mathrm{aw}\{s_1-(d-1)\}& a<0\\ a\underset{w_1,...w_{n_d}\in B}{\min }\underset{i=1}{\overset{n_d}{\Sigma }}{w}_i(c_{i,d}(-s_1+2i)-1)+{\mathrm{as}}_2& a>0\end{array}\right)$>

式中，B为二进制标签集合，B={0,1}，x₁,x₂,...,x_n为二进制变量，代表图像中的像素，w和w_i为增加的辅助变量，a为常数，d为奇数，s₁和s₂的值分别为：

$>s_1=\underset{i=1}{\overset{d}{\Sigma }}{x}_i$>

$>s_2=\underset{i=1}{\overset{d-1}{\Sigma }}\underset{j=i+1}{\overset{d}{\Sigma }}{x}_i{x}_j=\frac{s_1(s_1-1)}{2}$>

其中：

经Ishikawa等价变换，同变量数且同次数的不同能量函数具有相同数目的变量，为构造剩余s/t图提供条件。

Ishikawa等价变换方法记载于：IEEE Transactions on Pattern Analysis and MachineIntelligence,33(6):1234-1249,2011。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，所述的步骤d具体为：

高次布尔能量函数经Ishikawa等价变换后变为二次布尔能量函数后，就可以按照现有技术方法二次布尔能量函数构建s/t图模型的方式构建s/t图模型，如图3所示。现有技术方法记载于：IEEE Transactions on Pattern Analysis and Machine Intelligence,26(2):147-159,2004。

在对应的s/t图模型中，顶点s和t分别代表前景和背景，除s和t外的每一个节点代表能量函数中的一个变量，其中能量函数中一次项系数为节点与顶点之间连边(t-link)的容量，表示视频帧中像素点划为前景或背景所付出的代价，二次项系数为某邻域内节点之间连边(n-link)的容量，表示某邻域内像素点之间的不一致性。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，所述的步骤e具体为：

将当前帧高次能量函数对应的s/t图各个连边的容量减去前一帧高次能量函数对应的最大流，得到当前帧剩余s/t图各个连边的容量；如果

当前帧的剩余s/t图的连边容量满足边界容量和质量平衡约束（即剩余图各连边容量全为正），则当前帧的剩余s/t图无须改变，可以继续到下一步处理；

当前帧的剩余s/t图连边容量不满足边界容量和质量平衡约束（即剩余图各连边容量有负值），则通过动态算法进行再参数化，使得剩余s/t图的连边容量更新，从而得到与负容量剩余s/t图等价的非负容量剩余s/t图，并且以此非负容量剩余s/t图作为当前帧的剩余s/t图。

所述的动态算法记载于：IEEE Transactions on Pattern Analysis and Machine Intelligence,29(12):2079-2088,2007。

上述基于增量式高次布尔能量最小化的视频前后景分割方法，所述的步骤f具体为：

利用最小割/最大流法计算出当前帧剩余s/t图的最大流（视频首帧直接求解其s/t图最大流即可），从而得到当前帧的高次布尔能量的最优解；最优解为1的变量对应的像素被分割为前景，最优解为0的像素被分割为后景，当前帧的前景和后景像素得以分割。所述的最小割/最大流算法记载于：IEEE Transactions on Pattern Analysis and MachineIntelligence,31(9):1645-1656,2009。