ipa 分區算法分析，圖解

參考

Room Segmentation: Survey, Implementation, and Analysis. 分區算法調查，實現以及評估對比

Morphological Segmentation 形態分割算法

形態分割的主要亮點是算法簡單和計算速度快。

該算法在柵格地圖 $M_1$ 上工作，柵格分為可訪問和不可訪問兩種類型，白色區域代表可訪問性，黑色區域表示不可訪問性。如圖 fig.1 左上角圖片。
對地圖 $M_1$ 可訪問區域（白色區域）進行形態學腐蝕操作，該操作是通過一個像素一圈一圈地重復腐蝕一定次數（用戶設定的參數）。之后得到一些連通區域和分離區域。如圖 fig.1 右上角圖片。
在步驟 2 中，注意一定要一個像素一圈一圈地腐蝕。每次腐蝕后判斷每個分離區域的面積，若分離區域大小在合適范圍內（用戶設定的區域大小上下限內），那么標記該分離區域的所有柵格為房間 $r_i$ 。地圖 $M_2$ 是地圖 $M_1$ ?的拷貝。把分離出來的房間 $r_i$ ?在地圖 $M_2$ 中并標記上不同顏色，并且把? $M_1$ ?中房間 $r_i$ ?區域標記為不可訪問區域。如圖 fig.1 左下角圖片是標記了房間的 $M_2$ 。
重復“腐蝕-分離”操作，就能夠得到一系列分離的房間并標記在地圖 $M_2$ ?中。然后擴散每個房間，直到地圖 $M_2$ ?中的可訪問區域被標記完。如圖 fig.1 右下角。

Distance Transform-based Segmentation 距離變換分割

將柵格地圖用距離變換計算，距離變換值高說明離障礙物遠，距離變換值低說明離障礙物近。柵格數值表示每個可訪問像素（白色）到最近的邊界像素（黑色）的距離。如圖 fig.2 左上角（看起來像 Voronoi 變換）。
距離變換的局部最大值始終位于空間中心。在狹窄的走廊或門處，局部最大值比大房間內的最大值小。通過設置適當的閾值就可以區分出房間的中心。這里濾波的閾值需要用戶根據實際場景設置。如圖 fig.2 右上角。
從高到低地遍歷距離變換值閾值 t，從距離變換地圖中能夠分類出一組分離的空間集合 C。隨著遍歷的進行，該集合 C 的數量會增加，說明找到了更多的離散空間。當閾值等于門處的局部最大距離變換值時候，兩個離散空間會連通起來，空間集合 C 數量會減少。距離變換分割算法要找到一個閾值 t*，使得檢索到的空間集合 C 最大。如圖 fig.2 左下角。

其實就是將柵格地圖用距離變換轉換柵格存儲的數據，再用分水嶺算法得到離散空間，也就是房間。
給找到的離散空間標記上，并擴散這些空間，直到所有可訪問像素都標記上。

距離變換分割與形態分割有一些相似之處，因此某些地圖的分割結果非常相似。計算復雜度與形態分割相當。

分水嶺算法 3D 可視化

下面 3D 圖形通過 py 節點接收 costmap2d 地圖話題，再用 plotly 庫顯示。

地圖話題中，柵格數據表示與障礙物的接近程度，越接近障礙物數值越大，這也是一種距離變換。

柵格數值 100 表示障礙物，-1 表示未知區域，這里把 -1 轉為 100 顯示。

把地圖柵格數據作為 z 軸，得到 costmap2d 的 3d 圖形表示，如圖 fig.2.1 顯示：

按照步驟 2，需要找到一個閾值來篩選出初始的房間中心，這里選擇的閾值 t 是 51。圖 fig.2.3 中圖形 z 軸上的白色輪廓線就是初步篩選出來的房間中心。當 z 軸等于 51 時候，能夠得到 8 個初始房間，即 8 個白色輪廓。

按照步驟 3 需要從高到低調整閾值 t，但根據我們這邊 costmap2d 的距離變換，是從低到高調整閾值 t。接下來“水位上漲”，閾值 t 從 51 開始上升，地圖右下角和左側出現了新的白色輪廓。當閾值 t 達到 62 時候，房間數量達到最大的 10 個。此后閾值繼續上升，當閾值 t 等于 66 時候，左側中間的輪廓與左上角輪廓和中間對角輪廓連通，導致地圖房間數量開始減少，“水位溢出”。如圖 fig.2.4 顯示。

閾值 65 就是步驟 3 要找的目標閾值 t*。此時房間，也就是空間集合 C 數目最大，達到 10 個。如圖 fig.2.5。

Voronoi Graph-based Segmentation Voronoi 圖分割

基于 Voronoi 圖的分割采用更復雜的啟發式實現最后的合并步驟，這些啟發式方法偏向于分割完整的房間。

計算廣義 Voronoi 圖，并通過將葉邊緣折疊到其原點的節點中來修剪主骨架。如圖 fig.3 左上角。
在 Voronoi 圖上，如果某個 Voronoi 點恰好有兩個最近障礙物像素（就是說該 Voronoi 點的最近兩個障礙物像素點距離相等（這里必須是兩個，因為后面要計算夾角！）。那么這個 Voronoi 點就有可能是兩個房間之間的關鍵點。將這些關鍵點存儲在集合 P 中。如圖 fig.3 右上角。
繪制關鍵線：將集合 P 中的關鍵點與其最近障礙物點連接起來。關鍵線與墻體圍成多個封閉區域，其中可能會存在緊密嵌套的封閉區，需要過濾掉多余封閉區，只保留外圈。封閉區的關鍵點處的夾角，姑且稱為關鍵夾角。在角落中的關鍵夾角往往會比較小（小于 90°），可以移除掉。大角度的關鍵夾角經常出現在門口或通道處。經過關鍵線劃分后得到的封閉區，把它稱為 Voronoi 單元。盡管有過濾操作，仍會有一些零散的小單元。如圖 fig.3 左下角。

這里緊密嵌套的 Voronoi 單元過濾是比較關鍵的，論文只是一句話帶過：

The angle between both line segments is important if there are too many critical lines within an area.?
這部分的處理應該要看 Voronoi 圖分割算法的原論文才有更詳細的描述。??????
論文用以下啟發式方法將 Voronoi 單元合并到類似房間的結構中：
1. 單元面積小于閾值 (例如 12.5 平方米) ，且只有一個相鄰單元，且該單元 75% 的邊界不接觸墻體。那么該單元就會與其相鄰單元合并。
2. 單元面積小于閾值 (例如 2 平方米) ，若其相鄰單元有至少 20% 的邊界接觸墻體，該小單元合并進相鄰單元。
3. 合并以下區域（這個操作目的是連接同一房間內的兩個部分）：
  
  合并當前單元及其相鄰單元 ni。
  1. 相鄰的單元 ni 最多只有 2 個相鄰單元。
  2. 當前這個單元的邊界至少 50% 接觸墻壁。
    這里感覺有點歧義，丟個原文吧：
    3) Merge regions with (i) exactly one neighbor that has maximal 2 neighbors and with (ii) at least 50% of the perimeter touching walls (this connects two parts inside the same room).
4. 合并共享大部分邊界的區域。例如小單元和大單元相鄰，其中小單元至少 20%的邊界與大單元接觸，這部分邊界又至少占大單元邊界 10% 。
5. 一個單元超過 40% 的邊界接觸相鄰單元 nm，合并該單元與相鄰單元 nm。（用于合并有離散障礙物的區域）。

應用所有合并規則后得到分割圖。如圖 fig.3 右下角。

！！！注意！！！

如果步驟 2 中，Voronoi 圖上的點總是有多個（3或4個）最近障礙物點，那么步驟 3 中計算關鍵夾角就無法進行。需要增加策略過濾掉一些關鍵線，才能計算夾角。

GVD 分割單元

下面畫圖大概表述下步驟 3 的流程：

圖 fig.3.1 一個簡單的示例場景地圖。黑色是墻體。

圖 fig.3.2 通過計算得到地圖的廣義 voronoi 圖，用綠色標記。這里我只是畫了大概的 GVD。

圖 fig.3.3 中紅色點是有 2 處最近障礙物點的關鍵點，紫色是有 3 處最近障礙物點的 GVD 點，是要丟棄的！

圖 fig.3.4 用關鍵點連接最近障礙物得到關鍵線，標記為藍色像素。關鍵線與墻體圍成封閉區，紅線表示封閉區。

圖 fig.3.5 通過關鍵點密度及其圍成的封閉區是否嵌套來過濾掉部分關鍵線。黃色點是最后剩下的關鍵線數據點。它們與墻體圍成了 voronoi 單元。

Feature-based Segmentation 特征/語義分割

在地圖的每個可訪問像素位置放置一個模擬的 360° 激光掃描儀，通過掃描一圈地圖，得到相應位置的基本特征數據。如圖 fig.4 左邊。
這些基本特征數據可以計算出一組 33 個簡單的幾何特征，例如光線長度差或平均光線長度等。再用 AdaBoost 分類器將特征向量分類出房間標簽，例如辦公室或走廊。最后，合并具有相同標簽的所有相鄰點。為了獲得良好的分區結果，需要用足夠量的代表性數據來訓練分類器。不同環境可能需要重新訓練對應的分類器。