FAB

FAB

目录

• FAB_MAP算法介绍
• 符号说明
• 理论解释

FAB_MAP算法介绍

  FAB_MAP是经典的回环检测算法，算法的核心是Chow Liu Tree理论。Chow Liu Tree是特殊的一种图。Chow Liu tree理论的本质是考虑各个随机变量的依赖关系。而广泛应用的朴素贝叶斯算法是假设随机变量都是相互独立的。

  利用Chow Liu Tree理论来拟合离散概率分布的效果比朴素贝叶斯理论更好。因此，FAM_MAP算法的效果也更好。

符号说明

  在SLAM系统中，构建map通常是渐进地进行。在时间点 k k k，整个map是由 n k n_k nk​个地点(Location)构成的，记 L k = { L 1 , . . . , L n k } L^k={L_1,...,L_{n_k}} Lk={L1​,...,Lnk​​}，这里的地点指的是连续帧中有代表性的帧。

  对于图像 I k I_k Ik​，利用词袋模型可表示为 Z k Z_k Zk​，矢量量化后的形式为 Z k = { z 1 z 2 . . . z k } Z_k={z_1 _k} Zk​={z1​ z2​...zk​}
这里的 k k k代表的是整个字典的聚类(cluster)的数量，也代表着 k k k种特征。其中 z k {z_k} zk​是二元变量。

  想象一下，对于一张图像，计算机可以用 v v v维特征 Z k Z_k Zk​进行表示。而对于实际的图像 I k I_k Ik​， I k I_k Ik​可能只是由 m m m维特征构成，剩下的 v − m v-m v−m维都不存在，对应的 z j = 0 ( j = m + 1 , . . . , v ) z_{j}=0(j=m+1,...,v) zj​=0(j=m+1,...,v)。如果这样考虑，那么每个 z j z_j zj​都会对应一个隐变量 e j e_j ej​， e j e_j ej​代表对应的特征实际存在或者不存在。

  在时刻 k k k，整个特征集合 Z k = { Z 1 , . . . , Z k } Z^k={Z_1,...,Z_k} Zk={Z1​,...,Zk​}。

理论解释

  在时刻 k k k，有一特征集合 Z k Z^k Zk，考虑此时能检测到回环 L i L_i Li​的概率 p ( L i ∣ Z k ) p(L_i |Z^k) p(Li​∣Zk)

  根据递归贝叶斯公式有：

p ( L i ∣ Z k ) = p ( Z k ∣ L i , Z k − 1 ) p ( L i ∣ Z k − 1 ) p ( Z k ∣ Z k − 1 ) p(L_i |Z^k)=frac{p(Z^k|L_i,Z^{k-1})p(L_i|Z^{k-1})}{p(Z_k|Z^{k-1})} p(Li​∣Zk)=p(Zk​∣Zk−1)p(Zk∣Li​,Zk−1)p(Li​∣Zk−1)​

考虑似然函数 p ( Z k ∣ L i , Z k − 1 ) p(Z^k|L_i,Z^{k-1}) p(Zk∣Li​,Zk−1)

  假设地点当前的观测量与过去的观测量独立，所以有：

p ( Z k ∣ L i , Z k − 1 ) = p ( Z k ∣ L i ) p(Z^k|L_i,Z^{k-1})=p(Z^k|L_i) p(Zk∣Li​,Zk−1)=p(Zk∣Li​)

  根据Chow Liu 估计理论有;

p ( Z k ∣ L i ) ≈ p ( z r ∣ L i ) ∏ q = 2 ∣ v ∣ p ( z q ∣ z p q , L i ) (1) p(Z^k|L_i) approx p(z_r|L_i)prod_{q=2}^{|v|}p(z_q|z_{p_q},L_i)tag{1} p(Zk∣Li​)≈p(zr​∣Li​)q=2∏∣v∣​p(zq​∣zpq​​,Li​)(1)

  这里要说明的事，作者是利用Chow Liu Tree理论估计离散概率分布 p ( z 1 , . . . , z v ) p(z_1,...,z_v) p(z1​,...,zv​)，整个概率分布是一颗树形结构， z r z_r zr​是根节点， z p q z_{p_q} zpq​​是 z q z_q zq​的parent。

  考虑 p ( z q ∣ z p q , L i ) p(z_q|z_{p_q},L_i) p(zq​∣zpq​​,Li​)，根据全概率公式有:

p ( z q ∣ z p q , L i ) = ∑ s e q p ( z q ∣ e q = s e q , z p q , L i ) p ( e q = s e q ∣ z p q , L i ) (2) p(z_q|z_{p_q},L_i)=sum_{s_{eq}}p(z_q|e_q=s_{eq},z_{p_q},L_i)p(e_q=s_{eq}|z_{pq},L_i)tag{2} p(zq​∣zpq​​,Li​)=seq​∑​p(zq​∣eq​=seq​,zpq​​,Li​)p(eq​=seq​∣zpq​,Li​)(2)

  假设 e j e_j ej​与 z i z_i zi​是独立的（ i ≠ j i ne j i​=j）， L i L_i Li​与 z q z_q zq​独立，所以式 2 2 2可表达为：

p ( z q ∣ z p q , L i ) = ∑ s e q p ( z q ∣ e q = s e q , z p q ) p ( e q = s e q ∣ L i ) (3) p(z_q|z_{p_q},L_i)=sum_{s_{eq}}p(z_q|e_q=s_{eq},z_{p_q})p(e_q=s_{eq}|L_i)tag{3} p(zq​∣zpq​​,Li​)=seq​∑​p(zq​∣eq​=seq​,zpq​​)p(eq​=seq​∣Li​)(3)

  其中， p ( z q ∣ e q = s e q , z p q ) = ( 1 + α β ) − 1 p(z_q|e_q=s_{eq},z_{p_q})=(1+frac{alpha}{beta})^{-1} p(zq​∣eq​=seq​,zpq​​)=(1+βα​)−1

α = p ( z q ) p ( z q ˉ ∣ e q ) p ( z q ˉ ∣ z p ) alpha=p(z_q)p(bar{z_q}|e_q)p(bar{z_q}|z_p) α=p(zq​)p(zq​ˉ​∣eq​)p(zq​ˉ​∣zp​)

β = p ( z q ˉ ) p ( z q ∣ e q ) p ( z q ∣ z p ) beta=p(bar{z_q})p({z_q}|e_q)p({z_q}|z_p) β=p(zq​ˉ​)p(zq​∣eq​)p(zq​∣zp​)

考虑先验概率 p ( L i ∣ Z k − 1 ) p(L_i|Z^{k-1}) p(Li​∣Zk−1)

  作者把所以的地点分成两部分，一部分是已经观测过的 M M M，一部分是没有观测过的 M ˉ bar{M} Mˉ。根据全概率公式有：

p ( Z k ∣ Z k − 1 ) = ∑ m ∈ M p ( Z k ∣ L m ) p ( L m ∣ Z k − 1 ) + ∑ u ∈ M p ( Z k ∣ L u ) p ( L u ∣ Z k − 1 ) (4) p(Z_k|Z^{k-1})=sum_{m in M}p(Z_k|L_m)p(L_m|Z^{k-1})+sum_{u in M}p(Z_k|L_u)p(L_u|Z^{k-1})tag{4} p(Zk​∣Zk−1)=m∈M∑​p(Zk​∣Lm​)p(Lm​∣Zk−1)+u∈M∑​p(Zk​∣Lu​)p(Lu​∣Zk−1)(4)

  其中 p ( Z k ∣ L m ) p ( L m ∣ Z k − 1 ) p(Z_k|L_m)p(L_m|Z^{k-1}) p(Zk​∣Lm​)p(Lm​∣Zk−1)可以转换为求似然概率，而 p ( Z k ∣ L u ) p ( L u ∣ Z k − 1 ) p(Z_k|L_u)p(L_u|Z^{k-1}) p(Zk​∣Lu​)p(Lu​∣Zk−1)是无法求解的，因为我们没有"未来的数据"。因此，作者利用随机采样的方法，在 M M M的样本内随机选取 n s n_s ns​个样本代表 M ˉ bar{M} Mˉ。

  所以， ( 4 ) (4) (4)式可进一步近似为：

p ( Z k ∣ Z k − 1 ) ≈ ∑ m ∈ M p ( Z k ∣ L m ) p ( L m ∣ Z k − 1 ) + p ( L n e w ∣ Z k − 1 ) ∑ u = 1 n s p ( Z k ∣ L u ) n s p(Z_k|Z^{k-1})approxsum_{m in M}p(Z_k|L_m)p(L_m|Z^{k-1})+p(L_{new}|Z^{k-1})sum_{u =1}^{n_s}frac{p(Z_k|L_u)}{n_s} p(Zk​∣Zk−1)≈m∈M∑​p(Zk​∣Lm​)p(Lm​∣Zk−1)+p(Lnew​∣Zk−1)u=1∑ns​​ns​p(Zk​∣Lu​)​

   p ( L n e w ∣ Z k − 1 ) p(L_{new}|Z^{k-1}) p(Lnew​∣Zk−1)是先验概率，文中取的是0.9。而 p ( Z k ∣ L u ) p(Z_k|L_u) p(Zk​∣Lu​)可转换为求似然概率。

考虑概率 p ( Z k ∣ Z k − 1 ) p(Z_k|Z^{k-1}) p(Zk​∣Zk−1)

  作者说明了此概率对结果的影响不大，作者取的是常值2800.

总结：
  利用上述结果，可以得到递归贝叶斯的计算公式，值得注意的是，以上的前提是需要利用数据集训练学习得到Chow Liu Tree。而这个学习的过程包括词袋模型的建立，似乎是一个有监督的学习过程。

参考文献：
[1] Cummins M , Newman P . FAB-MAP: Probabilistic Localization and Mapping in the Space of Appearance[J]. s, 2008, 27(6):647-665.