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