在计算机视觉领域，光流算法是用于估计图像序列中像素点运动的一种技术。本文将介绍一种基于多项式基的密集光流计算算法，该算法能够快速计算出图像序列中每个像素点的运动向量。
在先前的文章中，已经了解到图像的局部邻域可以通过多项式基来表示。利用这种表示方法，可以在图像的每个点上估计出密集光流。本文将详细描述一种快速计算密集光流的算法，该算法基于文献[4]中的描述。
多项式基是假设在平移过程中多项式如何变换的一种方法。通过从当前帧和前一帧中导出的多项式展开系数，可以估计出位移向量。多项式展开的思想是用多项式来近似2D函数中某点的邻域。考虑二次多项式基：
1, x^2, y^2, x, y, xy
图像邻域中的像素值可以表示为：
f(x) = x^T A x + b^T x + c
其中A是一个对称矩阵，b是一个向量，c是一个标量。系数可以通过加权最小二乘估计邻域中的像素值来估计，如之前文章中所见。与所有光流算法一样，假设亮度恒定，即相邻帧中图像路径的亮度是恒定的。
考虑在图像中的点(\(x,y\))遇到一个平移运动\(d\)。可以通过等同两个多项式的系数来获得位移向量，这是基于亮度恒定假设的。假设A是非奇异的，可以得到：
d = -0.5 * A^-1 * (b_2 - b_1)
通过等同多项式的系数，可以在图像的每个点上获得位移向量，假设相邻帧中感兴趣区域有重叠。
可以使用迭代方案来获得更好的位移向量估计。在每次迭代中，可以得到更好的位移向量估计。迭代可以在位移向量的变化低于阈值或完成特定次数的迭代后终止。初始位移向量的估计假设为(0,0)，这意味着当前帧和前一帧的图像块是相同的。
以下是用于更新多项式系数的函数的伪代码实现：
void updatePoly(
const float *ptr1,
const float *ptr2,
Point2f d,
bool flag,
float *M,
Point p,
Size s)
{
int x = p.x;
int y = p.y;
const int BORDER = 5;
static const float border[BORDER] = {0.14f, 0.14f, 0.4472f, 0.4472f, 0.4472f};
float r[5];
float r2, r3, r4, r5, r6;
if (flag == true)
{
// average A_1 and A_2
r4 = (ptr1[2] + ptr2[2]) * 0.5;
r5 = (ptr1[3] + ptr2[3]) * 0.5;
r6 = (ptr1[4] + ptr2[4]) * 0.25;
}
else
{
r[0] = 0.f;
r[1] = 0.f;
r[2] = ptr1[2];
r[3] = ptr1[3];
r[4] = ptr1[4] * 0.5;
r2 = r[0];
r3 = r[1];
r4 = r[2];
r5 = r[3];
r6 = ptr1[4] * 0.5;
}
// computing -(b1-b2)
r2 = (ptr1[0] - ptr2[0]) * 0.5;
r3 = (ptr1[1] - ptr2[1]) * 0.5;
// sum for iterative estimation b2=b2+\bar{b2}
r2 += r4*d.y + r6*d.x;
r3 += r6*d.y + r5*d.x;
r2 += r4*d.x + r6*d.y;
r3 += r6*d.x + r5*d.y;
if ((unsigned)(x - BORDER) >= (unsigned)(s.width - BORDER*2) ||
(unsigned)(y - BORDER) >= (unsigned)(s.height - BORDER*2))
{
float scale = (x < BORDER ? border[x] :
1.f) *
(x >= s.width - BORDER ? border[s.width - x - 1] :
1.f) *
(y < BORDER ? border[y] :
1.f) *
(y >= s.height - BORDER ? border[s.height - y - 1] :
1.f);
r2 *= scale; r3 *= scale; r4 *= scale;
r5 *= scale; r6 *= scale;
}
// computing final displacement d=A^-1(b2-b1)*0.5
M[0] = r4*r4 + r6*r6;
M[1] = (r4 + r5)*r6;
M[2] = r5*r5 + r6*r6;
M[3] = r4*r2 + r6*r3;
M[4] = r6*r2 + r5*r3;
}
该函数计算了光流位移向量。它接受两个多项式基分量数组的指针、当前点的位移向量估计、一个标志位指示是否为边界像素、输出数组的指针以及当前点的坐标和窗口大小。
在处理大位移的情况下，可以采用多尺度估计方法。首先在最小分辨率下计算光流场，然后在较低分辨率下计算得到的位移用于在较高分辨率下进行光流场计算。
本文介绍了基于文献[4]的密集光流算法的理论和实现细节。该算法的代码可以在GitHub仓库https://github.com/pi19404/OpenVision中的DenseOf.cpp和DenseOf.hpp文件中找到。在未来的文章中，将探讨使用SSE、NEON和OpenCL优化来实现密集光流场的实时计算。
Kenneth Andersson 和 Hans Knutsson. Continuous normalized convolution. In: ICME (1). IEEE, 2002, pp. 725-728. isbn: 0-7803-7304-9. url: http://dblp.uni-trier.de/db/conf/icmcs/icme2002-1.html
Kenneth Andersson, Carl-Fredrik Westin, 和 Hans Knutsson. Prediction from o-grid samples using continuous normalized convolution. In: Signal Processing 87.3 (Mar. 22, 2007), pp. 353-365. url: http://dblp.uni-trier.de/db/journals/sigpro/sigpro87.html
Gunnar Farnebäck. Motion-based Segmentation of Image Sequences . LiTH-ISY-EX-1596. MA thesis. SE-581 83 Linköping, Sweden: Linköping University, 1996.