卢卡斯-卡纳德-托马希特征追踪[ 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
=
∂
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}
h
1
{\displaystyle h_{1}}
实作卢卡斯-卡纳德-托马希特征追踪需要计算加权和
F
′
G
,
{\displaystyle F'G,}
F
′
F
,
{\displaystyle F'F,}
(
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} }
线性近似:
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
![{\displaystyle {\sqrt {\sum _{x\in R}\left[F(x+h)-G(x)\right]^{2}}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d44abb1d7b3bf12c18c2bdd36e9c41ea693c10b7)
![{\displaystyle h={\dfrac {\sum _{x}{\dfrac {w(x)\left[G(x)-F(x)\right]}{F'(x)}}}{\sum _{x}w(x)}}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c53c0fb38c40a5bc9e192b43688b133e726567a4)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c82973c751393a5abdb7dcb06996bab9889cdbd0)
![{\displaystyle E=\sum _{x}\left[F(x+h)-G(x)\right]^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bba1ca4c1682dd5d75f44601b8dfa23f172b0d84)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5a0f2d977ee2b5c5c6010f009a9565ae83501a23)
![{\displaystyle \Rightarrow h\approx {\dfrac {\sum _{x}F'(x)[G(x)-F(x)]}{\sum _{x}F'(x)^{2}}}\,}](https://wikimedia.org/api/rest_v1/media/math/render/svg/33dfdb7fa73a7e636bca7d2e75e7e29034f5c165)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/89ded00819ca6831632e66244820517080bf67fb)
![{\displaystyle E=\sum _{\mathbf {x} \in R}\left[F(\mathbf {x} +\mathbf {h} )-G(\mathbf {x} )\right]^{2},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/48baa98889ed2f8017fcbd8649f2492981b26c53)
![{\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/891dbcce1425f50830f7fda84fdbf8a72e202baf)
![{\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},}](https://wikimedia.org/api/rest_v1/media/math/render/svg/bec2f162d82fee8d1f10c5f58442652a1375fe59)
![{\displaystyle E=\sum _{x}\left[F(Ax+h)-G(x)\right]^{2}.}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1e092da7844dc2ae3ef456b78368b1279066f922)
![{\displaystyle E=\sum _{x}\left[F(Ax+h)-(\alpha G(x)+\beta )\right]^{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c0653f7f9650c2fbbf298ed548e65d352db423df)
