盧卡斯-卡納德-托馬希特徵追蹤[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)
