2022/8/29研究進度 -- 重叡

# 2022/8/29研究進度 -- 重叡 ###### tags: `進度報告` `SOLab` [TOC] ## 進度 :::info **本次進度** - [x] 研究低重疊地圖的合併方法 ::: ### 前言 - 此篇論文[^1]提出在相對較小的重疊區域中具有未知初始對應關係的間接地圖合併方法。 - 本文提出了一種基於Radon變換的地圖合併算法。 - 不需要機器人之間的預定會合，地圖之間沒有共同的地標 - 不需要地圖之間重疊區域的先驗信息。 - 使用公共數據集進行實驗 - 公共數據集 RADISH Fort AP Hill 數據集[^2]用於評估所提出的地圖合併算法 ### 方法 - 二維空間中的網格圖M可以看成是$n_r$行$n_c$列的矩陣。矩陣中的每個單元格都包含有關M中網格位置的信息。. - 映射變換矩陣 (MTM) - 為了方便地圖變換，將M的對偶形式$M^d$定義為一個三行矩陣和M中佔用的網格數。$M^d$的第一行和第二行分別表示佔用網格的x和y坐標. $M^d$的最後一行是虛擬的，以便於計算映射變換矩陣。給定兩個網格映射$M_1$和$M_2$，映射變換矩陣$T$，在 x 坐標方向平移 Δx，在 y 坐標方向平移 Δy，逆時針旋轉 Δθ 定義如下： $\begin{equation*}{\mathbf{T}}\left({{\Delta _x},{\Delta _y},{\Delta _\theta }}\right) = \left[ {\begin{array}{ccc} {\cos {\Delta _\theta }}&{ - \sin {\Delta _\theta }}&{{\Delta _x}} \\ {\sin {\Delta _\theta }}&{\cos {\Delta _\theta }}&{{\Delta _y}} \\ 0&0&1 \end{array}} \right]\tag{1}\end{equation*}$ ${\mathbf{M}}_2^{\prime d} = {\mathbf{TM}}_2^d$。 ${\mathbf{M}}_2^{\prime d}$是從 $M_2$ 旋轉和平移的對偶圖，它與 $M_1$ 在同一坐標系中表示。 - 重疊區域的問題 - 提出了一種新的地圖合併算法，該算法使用通過Radon變換提取的正弦圖，可以在沒有任何直接信息的情況下以相對較小的重疊區域成功進行。 - ![](https://i.imgur.com/mjqUNsk.gif) #### 基於正弦圖的地圖合併 - Radon 變換是一種積分變換，它由函數在直線上的積分組成。Radon 變換數據通常被稱為正弦圖。令$f ( x,y )$ 是在$R^2$中某個大圓盤外消失的連續函數。直線$L$參數化為 $( x ( t ) ,y ( t )) = (( t sin α + s cos α ),(− t cos α + s sin α ))$其中$t$是$L$的參數形式的參數，並且$s$是$L$到原點的距離，$α$是法向量到$L$與x軸的夾角。 - ![](https://i.imgur.com/26v4jUB.png) - Radon 變換$RT_f$是定義在直線空間上的函數$R^2$中的$L$由沿每條此類線的線積分得出： $\begin{align*}& {R{T_f}(s,\alpha )} \\ & { = \int_{ - \infty }^\infty f (x(t),y(t)){\text{d}}t} \\ & { = \mathop \smallint \infty f((t\sin \alpha + s\cos \alpha ),( - t\cos \alpha + s\sin \alpha )){\text{d}}t} \tag{2}\end{align*}$ - RADISH AP Hill 數據集 [^2] 獲得的全圖的兩張圖。 M1和M2之間有一個重疊區域![](https://i.imgur.com/VSRkaEs.gif) - M1 和 M2 的正弦圖 (a) M1 正弦圖的最大強度出現在 (413,91°) (b) M2 正弦圖的最大強度出現在(921,106°)。![](https://i.imgur.com/gQew3yQ.gif) #### 旋轉角度的估計 - 根據正弦圖中的α逐列水平變化可以顯示網格圖的形狀。網格圖最細長的方向是$α_{max} − 90°$，其中$α_{max}$對應於最大水平。因此，我們可以說兩個網格圖之間的旋轉角度可以通過比較它們的正弦圖中指示最大級別的位置來估計。 - 令$M_1$和$M_2$的大小分別為$n_1 × m_1$和$n_2 × m_2$。然後，針對 $0° ≤ α ≤ 180°$ 生成$M_1$的正弦圖如下：$R{T_{{{\mathbf{M}}_1}}}(s,\alpha )$ where - γ 1 ≤ s ≤ γ 1。對於 $0° ≤ α ≤ 180°$，生成$M_2$的正弦圖如下：$R{T_{{{\mathbf{M}}_2}}}(s,\alpha )$where - γ 2 ≤ s ≤ γ 2。這裡，γ 1和γ 2分別是正弦圖中的最大s值，計算如下： \begin{align*} & {\gamma _1} = \left\lceil {\sqrt {{{\left({{n_1} - n_1^{\ast}}\right)}^2} + {{\left({{m_1} - m_1^{\ast}}\right)}^2}} } \right\rceil + 1\tag{3} \\ & {\gamma _2} = \left\lceil {\sqrt {{{\left({{n_2} - n_2^{\ast}}\right)}^2} + {{\left({{m_2} - m_2^{\ast}}\right)}^2}} } \right\rceil + 1\tag{4}\end{align*} $(n_1^{\ast},m_1^{\ast})$和$(n_2^{\ast},m_2^{\ast})$分別是$M_1$和$M_2$的中心點。 - 根據兩個正弦圖中的最大能級的位置可以得到：$( s_{1 ,max} ,α_{1 ,max} )$和$( s_{2 ,max} ,α_{2 ,max} )$ ，$M_1$和$M_2$可以估計如下： $\begin{equation*}{\Delta _\theta } = {\alpha _{2,max}} - {\alpha _{1,max}}\tag{5}\end{equation*}$ #### XY 平移的估計 - 由於本文中的平移估計是在地圖旋轉完成後進行的，因此其中一個部分地圖旋轉了上一步估計的旋轉角度。給定估計的旋轉角 ∆ θ，$\widetilde {{\mathbf{M}}_2^d}$通過旋轉獲得${\mathbf{M}}_2^d$如下： $\begin{equation*}\widetilde {{\mathbf{M}}_2^d} = {\mathbf{T}}\left({0,0,{\Delta _\theta }}\right){\mathbf{M}}_2^d\tag{6}\end{equation*}$ $\widetilde {{\mathbf{M}}_2^d}$和${\mathbf{M}}_2^d$是$\widetilde {{\mathbf{M}}_2}$和${\mathbf{M}}_2$的對偶。${\mathbf{M}}_2$的大小是$\widetilde{n_2}×\widetilde{m_2}$. 對於 $0° ≤ α ≤ 180°$，正弦圖$\widetilde {{\mathbf{M}}_2^d}$生成如下：$R{T_{\widetilde {{{\text{M}}_2}}}}(s,\alpha )$where $-\widetilde{γ2}≤ s ≤\widetilde{γ2}$. 這裡，$\widetilde{γ2}$是正弦圖的最大s值$\widetilde {{{\mathbf{M}}_2}}$併計算如下： $\begin{equation*}{\tilde \gamma _2} = \left\lceil {\sqrt {{{\left({{{\tilde n}_2} - \tilde n_2^{\ast}}\right)}^2} + {{\left({{{\tilde m}_2} - \tilde m_2^{\ast}}\right)}^2}} } \right\rceil + 1\tag{7}\end{equation*}$ 和$(\widetilde {n_2^{\ast}},\widetilde {m_2^{\ast}})$分別是$\widetilde {{\mathbf{M}}_2^d}$的中心點。 - 可以通過找到s值來估計每個平移，該 s 值使對應於某個α值的兩個譜向量之間的互相關最大化。這個譜向量表示網格沿α方向的分佈，也就是說，譜向量是α值對應的s的分佈。給定${{\mathbf{S}}_{{{\mathbf{M}}_n}}}$有$2ρ_n+1$行和$φ_n$列，從具有 $r_n$ 行和 $c_n$ 列的第 n 個部分映射 $M_n$ 生成，我們將與α '-value對應的譜向量定義為α '的方向譜如下： $\begin{equation*} {\mathbf{DS}}_{{{\mathbf{M}}_n}}^{{\alpha ^\prime }}(t) = R{T_{{{\mathbf{M}}_n}}}\left({t - {\gamma _n} - 1,{\alpha ^\prime }}\right),\quad 0 < t \leq 2{\gamma _n} + 1\tag{8}\end{equation*}$ 其中$γ_n$是$M_n$的正弦圖的最大s值。x軸和y軸的方向譜可以通過下式計算${\mathbf{DS}}_{{{\mathbf{M}}_n}}^{{{180}^\circ }}(s)$和${\mathbf{DS}}_{{{\mathbf{M}}_n}}^{{{90}^\circ }}(s)$. - 然而，由於部分映射的大小通常不同，如$M_1$和$\widetilde {{{\mathbf{M}}_2}}$，光譜應該用相同的維度來表示。最大行數和最大列數作為部分映射的最大尺寸$M_1$和$\widetilde {{{\mathbf{M}}_2}}$如下：${n_{max}} = \max \left({{n_1},{{\tilde n}_2}}\right)$和${m_{max}} = \max \left({{m_1},{{\tilde m}_2}}\right)$。$M_1$的X和Y光譜分別重新定義為 $\begin{align*} & {\mathbf{X}}{{\mathbf{S}}_{{{\mathbf{M}}_1}}}(i) = {\mathbf{DS}}_{{{\mathbf{M}}_1}}^{{{180}^\circ }}\left({i + \gamma _1^{\ast} - {m_{ma{x^{\ast}}}}}\right)\tag{9} \\ & {\mathbf{Y}}{{\mathbf{S}}_{{{\mathbf{M}}_1}}}(j) = {\mathbf{DS}}_{{{\mathbf{M}}_1}}^{{{90}^\circ }}\left({j + \gamma _1^{\ast} - {n_{ma{x^{\ast}}}}}\right)\tag{10}\end{align*}$ where$\gamma_{1}^{*}=\left\lceil\frac{2 \rho_{1}+1}{2}\right\rceil$ - $\widetilde {{{\mathbf{M}}_2}}$的X光譜和Y光譜同樣被重新定義。第一個局部映射$M_1$和第二個旋轉局部映射$\widetilde {{{\mathbf{M}}_2}}$之間的x - y平移可以通過找到使它們的光譜之間的互相關最大化的參數來估計。對於x - y軸，它們之間的互相關分別定義為 1 ≤ τ ≤ m max和 1 ≤ τ ≤ n max如下： $\begin{align*} & {\mathbf{CC}}{{\mathbf{X}}_{{{\mathbf{M}}_1}{{{\mathbf{\tilde M}}}_2}}}(\tau ) = \sum\limits_{k = - \infty }^\infty {{\mathbf{X}}{{\mathbf{S}}_{{{\mathbf{M}}_1}}}} (k + \tau ){\text{X}}{{\text{S}}_{{{\overline {\text{M}} }_2}}}(k)\tag{11} \\ & {\mathbf{CC}}{{\mathbf{Y}}_{{{\mathbf{M}}_1}{{{\mathbf{\tilde M}}}_2}}}(v) = \sum\limits_{l = - \infty }^\infty {{\mathbf{Y}}{{\mathbf{S}}_{{{\mathbf{M}}_1}}}} (l + v){\mathbf{Y}}{{\mathbf{S}}_{{{{\mathbf{\tilde M}}}_2}}}(l)\tag{12}\end{align*}$ - 最後，通過選擇最大化X光譜的互相關性的參數來獲得各個網格圖之間的x平移，如下所示： $\begin{equation*}{\Delta _x} = \mathop {\arg \max }\limits_\tau {\mathbf{CC}}{{\mathbf{X}}_{{{\mathbf{M}}_1}{{{\mathbf{\tilde M}}}_2}}}(\tau )\tag{13}\end{equation*}$ - 同樣地，各個網格圖之間的y平移是通過選擇使Y譜的互相關最大化的參數獲得的，如下所示： \begin{equation*}{\Delta _y} = \mathop {\arg \max }\limits_v {\mathbf{CC}}{{\mathbf{Y}}_{{{\mathbf{M}}_1}{{{\mathbf{\tilde M}}}_2}}}(v)\tag{14}\end{equation*} - 得到X光譜、Y光譜及其互相關 ![](https://i.imgur.com/weDeUZ9.gif) ## 小結如果地圖之間的重疊區域不足，現有的地圖合併方法無法合併地圖。本文提出了一種新的使用正弦圖的地圖合併算法，該算法可以在較小的重疊區域下進行。本文是在未知初始位置的情況進行，在了解現有地圖合併的package之後，想嘗試應用於重複特徵地圖已知初始位置的情況 :::danger 下次預期目標： 1. 了解現有地圖合併的package 2. 繼續找相關論文 ::: # Reference [^1]:H. Lee and S. Lee, "Grid Map Merging with Insufficient Overlapping Areas for Efficient Multi-Robot Systems with Unknown Initial Correspondences," 2020 IEEE International Conference on Systems, Man, and Cybernetics (SMC), 2020, pp. 1427-1432, doi: 10.1109/SMC42975.2020.9282932. [^2]:[online] Available: http://radish.sourceforge.net.