卢卡斯-卡纳德-托马希特征追踪[ 1] 是建立在两篇论文的研究成果,在第一篇,卢卡斯和卡纳德提出用影像的二次微分当作权重来对影像作局部搜寻
如果
h
{\displaystyle h}
是两张影像的位移,那么
F
(
x
)
{\displaystyle F(x)}
和
G
(
x
)
=
F
(
x
+
h
)
{\displaystyle G(x)=F(x+h)}
就能以下列的式子近似:
F
′
(
x
)
≈
F
(
x
+
h
)
−
F
(
x
)
h
=
G
(
x
)
−
F
(
x
)
h
{\displaystyle F'(x)\approx {\dfrac {F(x+h)-F(x)}{h}}={\dfrac {G(x)-F(x)}{h}}\,}
于是
h
≈
G
(
x
)
−
F
(
x
)
F
′
(
x
)
{\displaystyle h\approx {\dfrac {G(x)-F(x)}{F'(x)}}\,}
然而通常这个近似只有在位移
h
{\displaystyle h}
不是太大的时候准确,因为在这个近似里,不同的
x
{\displaystyle x}
值会影响
h
{\displaystyle h}
,因此我们通常会对
h
{\displaystyle h}
取平均:
h
≈
∑
x
G
(
x
)
−
F
(
x
)
F
′
(
x
)
∑
x
1
.
{\displaystyle h\approx {\dfrac {\sum _{x}{\dfrac {G(x)-F(x)}{F'(x)}}}{\sum _{x}1}}.}
平均也可以更进一步写成下列的形式
|
F
″
(
x
)
|
{\displaystyle \left\vert F''(x)\right\vert }
成反比,
F
″
(
x
)
≈
G
′
(
x
)
−
F
′
(
x
)
h
.
{\displaystyle F''(x)\approx {\dfrac {G'(x)-F'(x)}{h}}.}
另外我们可以定一个权重函式让表达更方面:
w
(
x
)
=
1
|
G
′
(
x
)
−
F
′
(
x
)
|
.
{\displaystyle w(x)={\dfrac {1}{\left\vert G'(x)-F'(x)\right\vert }}.}
因此
h
{\displaystyle h}
也可以写成:
h
=
∑
x
w
(
x
)
[
G
(
x
)
−
F
(
x
)
]
F
′
(
x
)
∑
x
w
(
x
)
.
{\displaystyle h={\dfrac {\sum _{x}{\dfrac {w(x)\left[G(x)-F(x)\right]}{F'(x)}}}{\sum _{x}w(x)}}.}
接着,可以运用牛顿法的写出下列的递回式,这个序列最后会收敛到最佳的
h
{\displaystyle h}
{
h
0
=
0
h
k
+
1
=
h
k
+
∑
x
w
(
x
)
[
G
(
x
)
−
F
(
x
+
h
k
)
]
F
′
(
x
+
h
k
)
∑
x
w
(
x
)
{\displaystyle {\begin{cases}h_{0}=0\\h_{k+1}=h_{k}+{\dfrac {\sum _{x}{\dfrac {w(x)\left[G(x)-F(x+h_{k})\right]}{F'(x+h_{k})}}}{\sum _{x}w(x)}}\end{cases}}}
上述的推导无法被一般化因为二维的线性近似不太一样,因此近似要改成下列的式子:
F
(
x
+
h
)
≈
F
(
x
)
+
h
F
′
(
x
)
,
{\displaystyle F(x+h)\approx F(x)+hF'(x),}
l2 泛数形式的误差可以写成下列
E
=
∑
x
[
F
(
x
+
h
)
−
G
(
x
)
]
2
.
{\displaystyle E=\sum _{x}\left[F(x+h)-G(x)\right]^{2}.}
为了得到找到慧满足最小误差的
h
{\displaystyle h}
,对
E
{\displaystyle E}
作偏微分并令为0:
0
=
∂
E
∂
h
≈
∂
∂
h
∑
x
[
F
(
x
)
+
h
F
′
(
x
)
−
G
(
x
)
]
2
=
∑
x
2
F
′
(
x
)
[
F
(
x
)
+
h
F
′
(
x
)
−
G
(
x
)
]
{\displaystyle {\begin{aligned}0&={\dfrac {\partial E}{\partial h}}\\&\approx {\dfrac {\partial }{\partial h}}\sum _{x}\left[F(x)+hF'(x)-G(x)\right]^{2}\\&=\sum _{x}2F'(x)\left[F(x)+hF'(x)-G(x)\right]\end{aligned}}}
,
⇒
h
≈
∑
x
F
′
(
x
)
[
G
(
x
)
−
F
(
x
)
]
∑
x
F
′
(
x
)
2
{\displaystyle \Rightarrow h\approx {\dfrac {\sum _{x}F'(x)[G(x)-F(x)]}{\sum _{x}F'(x)^{2}}}\,}
这个步骤基本上跟一维的实例是一样的,只是权重函式必须写成
w
(
x
)
=
F
′
(
x
)
2
.
{\displaystyle w(x)=F'(x)^{2}.}
所以递回关系可以表达成:
{
h
0
=
0
h
k
+
1
=
h
k
+
∑
x
w
(
x
)
F
′
(
x
+
h
k
)
[
G
(
x
)
−
F
(
x
+
h
k
)
]
∑
x
w
(
x
)
F
′
(
x
+
h
k
)
2
{\displaystyle {\begin{cases}h_{0}=0\\h_{k+1}=h_{k}+{\dfrac {\sum _{x}w(x)F'(x+h_{k})\left[G(x)-F(x+h_{k})\right]}{\sum _{x}w(x)F'(x+h_{k})^{2}}}\end{cases}}}
在评估这个算法的效能时,我们通常会好奇
h
k
{\displaystyle h_{k}}
'可以多快收敛到真正的
h
{\displaystyle h}
。
如果我们看看下面这个例子:
F
(
x
)
=
sin
x
,
{\displaystyle F(x)=\sin x,}
G
(
x
)
=
F
(
x
+
h
)
=
sin
(
x
+
h
)
.
{\displaystyle G(x)=F(x+h)=\sin(x+h).}
当
|
h
|
<
π
{\displaystyle \left\vert h\right\vert <\pi }
,两种版本的配准算法都会收敛到正确的
h
{\displaystyle h}
。我们利用压抑影像中的高频来改进收敛的范围,也就是对影像作平滑化,当然同时一些细节也会丧失。但要注意的是,如果选用的平滑窗格比匹配的物体的大小大太多,物件可能会被压缩太多,使得找不到对应的匹配。
由于经过低通滤波器的影像可以用更低的分辨率去取样,我们采用由粗到精的层次化匹配策略。一张平滑化的低分辨率影像可以用来近似匹配,而之后再把算法用在高分辨率影像即可以让前面算出的匹配更准。
权重函式加速了收敛速度也增加了近似的准度,如果没有加权且
F
(
x
)
=
sin
x
{\displaystyle F(x)=\sin x}
,当位移接近0.5个波长,计算出来的
h
1
{\displaystyle h_{1}}
便会来第一个递回变成0。
实作卢卡斯-卡纳德-托马希特征追踪需要计算加权和
F
′
G
,
{\displaystyle F'G,}
F
′
F
,
{\displaystyle F'F,}
and
(
F
′
)
2
{\displaystyle (F')^{2}}
,虽然
F
′
(
x
)
{\displaystyle F'(x)}
没办法准确地算出,却可以用下式估计:
F
′
(
x
)
≈
F
(
x
+
Δ
x
)
−
F
(
x
)
Δ
x
,
{\displaystyle F'(x)\approx {\dfrac {F(x+\Delta x)-F(x)}{\Delta x}},}
一维和二维的配准算法可以延伸到多维,同样地,我们也需要去最小化L2 泛数
E
=
∑
x
∈
R
[
F
(
x
+
h
)
−
G
(
x
)
]
2
,
{\displaystyle E=\sum _{\mathbf {x} \in R}\left[F(\mathbf {x} +\mathbf {h} )-G(\mathbf {x} )\right]^{2},}
x
{\displaystyle \mathbf {x} }
和
h
{\displaystyle \mathbf {h} }
代表n维的行向量
线性近似:
F
(
x
+
h
)
≈
F
(
x
)
+
h
(
∂
∂
x
F
(
x
)
)
T
.
{\displaystyle F(\mathbf {x} +\mathbf {h} )\approx F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial }{\partial \mathbf {x} }}F(\mathbf {x} )\right)^{T}.}
接着将
E
{\displaystyle E}
对
h
{\displaystyle \mathbf {h} }
作偏微分:
0
=
∂
E
∂
h
≈
∂
∂
h
∑
x
[
F
(
x
)
+
h
(
∂
F
∂
x
)
T
−
G
(
x
)
]
2
=
∑
x
2
[
F
(
x
)
+
h
(
∂
F
∂
x
)
T
−
G
(
x
)
]
(
∂
F
∂
x
)
{\displaystyle {\begin{aligned}0&={\dfrac {\partial E}{\partial \mathbf {h} }}\\&\approx {\dfrac {\partial }{\partial \mathbf {h} }}\sum _{\mathbf {x} }\left[F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}-G(\mathbf {x} )\right]^{2}\\&=\sum _{\mathbf {x} }2\left[F(\mathbf {x} )+\mathbf {h} \left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}-G(\mathbf {x} )\right]\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\end{aligned}}}
,
⇒
h
≈
[
∑
x
[
G
(
x
)
−
F
(
x
)
]
(
∂
F
∂
x
)
]
[
∑
x
(
∂
F
∂
x
)
T
(
∂
F
∂
x
)
]
−
1
,
{\displaystyle \Rightarrow \mathbf {h} \approx \left[\sum _{\mathbf {x} }\left[G(\mathbf {x} )-F(\mathbf {x} )\right]\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\right]\left[\sum _{\mathbf {x} }\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)^{T}\left({\dfrac {\partial F}{\partial \mathbf {x} }}\right)\right]^{-1},}
过程其实跟一维的推导很像。
此方法也可以延伸到更复杂的矩阵变换,例如转动、放大缩小、剪切
G
(
x
)
=
F
(
A
x
+
h
)
,
{\displaystyle G(x)=F(Ax+h),}
A
{\displaystyle A}
是一个线性转换,误差可以表示成下列的式子:
E
=
∑
x
[
F
(
A
x
+
h
)
−
G
(
x
)
]
2
.
{\displaystyle E=\sum _{x}\left[F(Ax+h)-G(x)\right]^{2}.}
接着可以再次利用线性估计来决定
Δ
A
{\displaystyle \Delta A}
和
Δ
h
{\displaystyle \Delta h}
的值:
F
(
x
(
A
+
Δ
A
)
+
(
h
+
Δ
h
)
)
{\displaystyle F(x(A+\Delta A)+(h+\Delta h))}
≈
F
(
A
x
+
h
)
+
(
Δ
A
x
+
Δ
h
)
∂
∂
x
F
(
x
)
.
{\displaystyle \approx F(Ax+h)+(\Delta Ax+\Delta h){\dfrac {\partial }{\partial x}}F(x).}
上述类似的近似手法也可以用来找误差表达式,在这里是个二次方程式,因此可借由微分寻找最小值。
当两张不同视角影像的亮度不同时,需要将线性转换假设成
F
(
x
)
=
α
G
(
x
)
+
β
,
{\displaystyle F(x)=\alpha G(x)+\beta ,}
α
{\displaystyle \alpha }
代表对比度调整而
β
{\displaystyle \beta }
代表亮度调整
将此式与一般的线性转换结合后,即可得
E
=
∑
x
[
F
(
A
x
+
h
)
−
(
α
G
(
x
)
+
β
)
]
2
{\displaystyle E=\sum _{x}\left[F(Ax+h)-(\alpha G(x)+\beta )\right]^{2}}
所以我们可以用
α
,
{\displaystyle \alpha ,}
β
,
{\displaystyle \beta ,}
A
,
{\displaystyle A,}
和
h
{\displaystyle h}
去最小化E