第1页 / 共10页
第2页 / 共10页
第3页 / 共10页
第4页 / 共10页
第5页 / 共10页
第6页 / 共10页
第7页 / 共10页
第8页 / 共10页
LK算法的金字塔实现.docx
1.问题描述
2.跟踪算法描述
2.1图像金字塔表示法
2.2金字塔特征追踪
2.3迭代的光流计算（迭代的LK算法）
2.4金字塔追踪算法总结
2.5子像素计算
2.6跟踪靠近图片边缘的特征点
2.7声明特征丢失
3 特征选取
参考文献
Pyramidal Implementation of the Lucas Kanade Feature Tracker
Description of the algorithm
1. 问题描述
设 I 和 J 为两张 2 维灰度图像，I(x) = I(x, y)和 J(x) = J(x, y)为这两张图片在点 x=[x, y]T 的
灰度值，x 和 y 是图片上的点 x 的像素坐标。I 一般用来做第一张图片，而 J 一般用来当做
第二章图片。在实际问题中，图片 I 和 J 是离散函数（或数组），定义左上角的像素坐标向
量为[0 0]T，设 nx 和 ny 为这两张图片的宽度和 高度。则右下角的像素坐标向量为[nx-1 ny-1]T。
假设一个点 u = [ux uy]T 为第一张图片 I 上的一个点。特征点追踪的目标是在第二张图片
J 找到一个点 v 使得 v = u + d = [ux+dx uy+dy]T，就好比 I(u)和 J(v)是相似的。向量 d=[dx dy]T
是 x 点的图片速度，也就是众所周知的 x 点的光流。由于孔径问题，定义二维临近相似度的
概念就是十分必要的了。设 wx 和 wy 是两个整数。我们定义图片速率 d（x 点的光流）是用
来最小化差异函数的向量，定义如下：
u w
y
y
u w
x
x
x u w y u w
w
x
x
y
( )
d
(
,
d d
x
y
)
( ( ,
I x y
)
(
J x d y d
,
x
2
))
y
(1)
由这个定义可以得知，近似函数是通过图片的邻居大小 (2
w
x
1)
(2
w
y
1)
来测量的，
这个图片邻居也被称为集成窗口。一般 wx 和 wy 的取值为 2,3,4,5,6,7 个像素。
2. 跟踪算法描述
任何特征跟踪的两个重要因素是准确度和稳定性。准确度是跟去在追踪时局部子像素的
准确性来决定的。从直观上来看，为了不去平滑图片消除细节问题，一个小的集成窗口是比
较合适的，也就是说 wx 和 wy 的值较小。尤其是在两个有着完全不同图片速度的区域，这是
非常必要的。
稳定性因素需要考虑光照变化，图像运动时对尺寸变化的敏感性等问题。尤其是为了解
决大矢量运动，从直观上来看，选取一个较大的集成窗口更好。确实，根据公式 1，使
d
w 更好。因此在选择集成窗口大小的时候就要在准确度和稳定性中做一个折
d
,
w
x
x
y
y
衷。为了解决这样一个问题，我们提出一个金字塔实现的经典 LK 算法。LK 光流算法的迭
代实现可以提供效率高的局部跟踪准确率。
2.1 图像金字塔表示法
n
我们为一张图片 I 定义一个金字塔表示，大小为 x
n 。设 0L
y
L 是第 0 层图片。这
张图片的分辨率最高（原始图像），并把长宽分别定义为 0
n
x
n 、 0
n
y
x
n 。然后用一种递
y
归方式建立金字塔：利用 0I 计算 1I ，然后利用 1I 计算 2I ，以此类推。设 L 为金字塔层数，
则 1LI 为 L-1 层图片， 1L
xn 和 1L
yn 分别为 1LI 的宽和高。图片 1LI 定义如下：
I
L
( ,
x y
)
L
1
I
4
1 (
I
8
1 (
16
1
(2 ,2 )
y
x
L
1
(2
x
1,2 )
y
I
L
1
(2
x
1,2 )
y
I
L
1
(2 ,2
x
y
1)
I
L
1
(2 ,2
x
y
1))
I
L
1
(2
x
1,2
y
1)
I
L
1
(2
x
1,2
y
1)
I
L
1
(2
x
1,2
y
1)
I
L
1
(2
x
1,2
y
1)).
(2)
为了简化符号，我们定义不存在于图像 1LI
0
x
（
1
L
n
x
1
，
0
1
L
y n
y
1
）上的
点：
公式 2 只是定义了 x 和 y 的值
0 2
x
1
L
n
x
1
,
0 2
1
L
y n
y
1
。因此 LI 的宽度 L
xn
和高度 L
yn 最大时要满足以下两个条件：
(3),(4)
公式(2),(3),(4)是用来递归的构建图片 I 和 J 的金字塔表示，
{ }
L
I
L
0,...,
L
m
和
{
J
L
}
L
。
0,...,
L
m
mL 是金字塔的高度。通常 mL 的值为 2,3,4。对一般图像的大小来说，4 层以上的金字塔就没
有太大意义了。举例来说，一个图片 I 的大小为 640*480，则 1I 、 2I 、 3I 和 4I 的大小分别
为 320*240、160*120、80*60 和 40*30。超过四层在大多数情况下没有多大意义。金字塔表
示法的主要作用是能够处理大像素移动（超过集成窗口的大小）。所以，金字塔高度的选取
也要根据图像中的最大预期光流。下一部分江西的讲述了跟踪操作，让我们对概念的理解更
好。最后观察公式 2，低通滤波[1/4 1/2 1/4]*[1/4 1/2 1/4]T 是在图像二次抽样之前用来做图像
反走样。但是在实际情况下（比如 C 代码中）用一个更大的反走样滤波核心来构造金字塔
结构，形式上是一样的。
2.2 金字塔特征追踪
回想特征追踪的目标：根据给定图像 I 中的一个点 u，找到在图像 J 中相应的位置 v=u+d
或者迭代得到它的像素位移向量 d。
L
u u ，为点 u 金字塔每一层中对应的坐标。根据上述定
x
，定义 uL=[
0,..., m
L
对于
L
L
y
]
义的金字塔表示公式(2),(3),(4)，计算向量 uL 如下：
L
u
u
2
L
(5)
在公式(5)中的除法算子分别独立的应用于横竖坐标。特别的， 0u
u 。
整个的金字塔跟踪过程如下：首先，在最深层（最顶层） mL 计算光流；然后，计算得
到的结果用一种对像素位移的初始化猜测传递给上一层
1mL 。由于初始化了一个猜测，就
能很精确的计算出
1mL 层的光流，然后再传递给
mL 直到传递给最高层，也就是原始
2
图像。
现在我们用更多数学的分析来描述一下两层 1L 和 L 之间的递归操作。假设为 L 层光
从 1L 层计算结果得到传递给 L 层。然后，为了计算
流初始化一个猜测，
g
[
L
L
g g
x
]
L T
y
在 L 层的光流，就有必要去找到偏移向量
L
d
[
L
d d
x
]
L T
y
来最小化新的图像匹配错误函数：
L
(
d
L
)
(
L
,
d d
x
L
y
)
L
u w
y
y
L
u w
x
x
x u w y u w
x
L
x
L
y
(
I
L
( ,
x y
)
J
L
(
x g
L
x
d
L
x
,
y g
L
y
d
L
y
))
2
(6)
y
可以看到无论 L 的值是多少集成窗口的大小总是不变的，注意到初始化的猜测流向量
Lg 用来预先处理第二张图片块。这样，剩余的流向量
L
d
[
L
d d
x
]
L T
y
就会很小，因此可以
很容易的通过标准的 LK 算法计算出来。
剩余光流向量
L
d
[
L
d d
x
]
L T
y
的计算细节将在 2.3 节描述。现在让我们来假设这个向量
已经计算得到。然后计算的结果传递给下一层 1L ，而且传递初始化猜测 1Lg ，表达式如
下：
g
L
1
2(
g
L
d
L
)
(7)
通过相同的步骤计算出下一层的光流剩余向量 1Ld 。这个通过光流计算得到的向量来
最小化错误匹配函数 1
Ld
(
L
1
)
（公式 6），直到
0L 。算法开始时，设置最高层初始化向
量 mL 为 0（即在最高层金字塔时没有初始化猜测）。
mL
g
T
[0 0]
最后的光流结果 d（根据公式 1）经过光流计算得到：
d
0
g
d
0
也可以记为如下形式：
d
mL
L
0
L
L
2
d
(8)
(9)
(10)
金字塔实现明显的好处就是当计算一个大的整个的像素位移向量 d 时，每一个剩余光
流向量 Ld 都可以保持一个很小的值。假设每一个基本的光流计算可以处理的像素移动最大
为 maxd ，则金字塔实现可以处理的整个像素移动就变为了
d
max
final
(2
mL
1
1)
d
max
。举例
说明，如果金字塔深度 mL 为 3，这就意味着最大的像素位移可以达到 15！这就是在处理大
像素移动的同时也能保持集成窗口非常的小。
2.3 迭代的光流计算（迭代的 LK 算法）
现在让我们来描述一下核心的光流计算。在金字塔中的每一层，目的都是找到向量 Ld 去
最小化公式 6 中定义的匹配函数 L 。由于每一种操作的执行时都是相同的，所以让我们去
掉上标 L 然后定义新的图片 A 和 B ，如下：
p
1]
( ,
x y
1],
1,
1,
w
w
p
)
[
[
p w
x
x
p w
x
x
y
y
y
y
( ,
x y
)
[
p w p w
x
x
,
x
x
( ,
A x y
)
I
L
( ,
x y
)
]
[
p
y
w p
,
y
w
y
],
y
( ,
B x y
)
J
L
(
x g y g
,
L
x
(11)
(12)
L
y
)
注 意 到 ( ,
A x y 和 ( ,
B x y 的 定 义 域 是 有 些 不 同 的 ， 确 实 ， ( ,
A x y 的 窗 口 大 小 是
)
)
)
(2
w
x
3)
(2
w
y
而不是 (2
3)
w
x
1)
(2
w
y
1)
。这个差异将会在利用中心差异算子计算
A x y 的空间衍生物时体现出来。为了更清楚，我们定义偏移向量 [
( ,
v
)
v v
x
]T
y
L
，同
d
时 也 定 义 坐 标 向 量
p
[
p p
x
y
]T
。 根 据 新 的 符 号 ， 算 法 目 标 是 去 找 到 偏 移 向 量
L
u
v
[
v v
x
y
]T
，来最小化匹配函数。
标准的迭代 LK 算法可以用来解决这个问题。在最好的情况下，第一个的衍生
物对 v 求导为 0：
展开这个衍生物后，我们得到：
(14)
现在我们在 [0 0]T
v
用一阶泰勒展开式来代替 ( ,
B x y （在这里就可以有了一
)
个好的机会来近似我们所期望的很小的位移向量）。
观察到 ( ,
A x y
)
( ,
B x y
)
可以被当做是图片在点[ ,
x y 的暂时衍生物：
]T
而矩阵
B B
x
y
仅仅是图片的梯度向量。让我们对这个向量做一个小小的变换。
观察到图片衍生物 xI 和 yI 可能是直接来之第一张图片 ( ,
A x y 在
)
(2
w
x
1)
(2
w
y
的临近点 p ，而且无所谓 ( ,
1)
B x y （这个观察结果的重要性将会
)
在描述硫酸法的迭代版本时体现出来）。如果用中心差异算子来计算衍生物，两张衍
生图像就会有如下表达式：
实际上，Sharr 算子是用来计算图片衍生物的（跟中心差异算子相似）。
根据新的符号，公式 15 可以重写为：
定义：
公式 22 就可以写为：
因此根据公式 14，最佳光流向量就为：
optv
1
G b
(25)
只有当矩阵 G 可逆时，这个表达式才是有效的。就等于说 ( ,
A x y 在 x 和 y 方向
)
的临近点 p 都包含了梯度信息。
这就是标准的 LK 光流算法公式，这个公式只有在像素位移很小的时候才有效。
实际上，为了得到一个正确的解决办法，就有必要在这个流程上多次迭代。
现在我们已经介绍了数学背景，让我们给出迭代算法版本的具体细节。回想算法
目标：找到向量 v 来最小化在公式 13 中提到的错误函数 ( )v 。
设 k 为迭代索引，在开始时初始化为 1。让我们来描述算法的循环过程：在第 1k
次迭代时，假设通过前面的计算为向量偏移 v 得到了初始化猜测
v
k
1
1
[
v
k
x
v
k
y
1
]
T
。
设 kB 为根据猜测
1kv
得到的新的变换图像。
目标是计算剩余运动向量
]
T
来最小化错误函数：
x
k
y
[
最小化的解决办法可以通过计算 LK 光流得到
其中这个 2 1 维向量 kb （也叫做图像误匹配向量）：
第 k 个图片差异 kI 定义如下：
可以看到空间衍生物 xI 和 yI （在所有点的邻居 p 中）只在迭代开始时通过公式
19 和 20 只计算一次，因此 2 2 的矩阵 G 在迭代过程中也始终不变。这就带来了一
kb ，而且这个参数携
个很明显的好处。只有一个参数需要在迭代中反复计算，就是
带了很多图片块根据向量
1kv
移动之后的差异。一旦剩余光流
k 用公式 28 计算出来
之后，一个猜测新的像素位移猜测
kv 就可以计算出来了：
这个迭代过程一直进行直到
k 小于一个阈值（比如说 0.03 个像素）或达到了最
大的迭代次数（比如 20）之后停止。平均来说，5 次迭代就足够达到收敛了，在第一
次迭代时（k=1）初始化猜测置为 0：
假设为达到收敛进行 K 次迭代是必须的，则最后的光流向量
v d 为：
L
这个向量用来最小化错误函数在公式 13 中描述（或公式 6）。也用来终止迭代
LK 光流计算。向量 Ld 是用在公式 7，整个过程在每一个子层 1,
L
L
2,...,0
重复进
行（见 2.2 节）。
2.4 金字塔追踪算法总结
见原文档。
2.5 子像素计算
在计算的过程中很明显要将所有计算都在亚像素精度层进行。因此要可以计算在整形像
素之间计算亮度值就很必要了。为了在亚像素位置计算图像亮度，我们提出使用双线性插值
的方法。
设 L 为金字塔的一层，假设我们需要一个图像值 ( ,
LI
x y 且 x 和 y 不是整形。设 ox 和
)
oy 是 x 和 y 的整形部分（小于 x 和 y ），设 x 和 y 为保留值（0 到 1 之间）：
x
y
x
x
o
y
y
o
我们观察一下亚像素计算。根据 2.4 节给出的总结。当在点 ( ,
x y 的邻居
)
[
p w p w
x
x
,
x
x
]
[
p
y
w p
,
y
y
计算两个图像的衍生物 ( ,
xI x y 和 ( ,
yI
w
]
)
x y 时，就有
)
y
必要在点 ( ,
x y 的邻居[
)
p w
x
x
1,
p w
x
x
1]
[
p
w
y
1,
p
y
w
y
y
1]
得到亮度值。当
然中心 p 坐标不一定是整形，称
oxp 和
oyp 是 xp 和 yp 的整形部分。然后我们可以得到：
xp
和 yp
是小数部分。因此为了通过双线性插值在点 ( ,
x y 的邻居
)
[
p w
x
x
1,
p w
x
x
1]
[
p
w
y
1,
p
y
w
y
y
[
p w
x
x
1,
p w
x
x
2]
[
p
w
y
1,
p
y
w
y
y
计算 ( ,
1]
LI
x y ，就有必要在一个整数框
)
使用原始亮度序列的值 ( ,
2]
LI
x y 。
)
2.6 跟踪靠近图片边缘的特征点
观察到以下内容是很有用的：可能我们要处理一些离图片边界很近的点，我们就要把这
些点超出图片的集成窗口按比例缩小。如果金字塔层数很大的话，这个理解就变得更有意义
了。确实，如果我们为了追踪图片总是使用完整的 (2
w
x
1)
(2
w
y
1)
，那么就会在整个
图片宽度 xw 处存在禁止区。如果 mL 为金字塔的高度，那么就意味着有一个宽度为 2 mL
xw 的
禁止区在整张原始图片上。如果 mL 、 xw 和 yw 的值比较下，就可能不会带来一个影响很大
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
