【ORB-SLAM2】探索之旅 第 7 天 : 馬上搞懂區域四叉樹 (Region Quad Tree)

上一篇文章，「第 6 天 : 實作關鍵點 (Key Point) 提取功能」提到，單純提取關鍵點，會造成過度密集、數量太多的情況，產生冗餘關鍵點，降低系統穩定度。

因此，我們透過「 區域四叉樹 (Region Quad Tree) 」資料結構，實現關鍵點均勻化 (Key Points Distribution)，篩選、保留品質好的關鍵點。

【備註】區域四叉樹 (Region Quad Tree) 程式碼已上傳至 Github 。

章節目標

理解區域四叉樹 (Region Quad Tree) 原理，篩選、保留品質好的關鍵點。

均勻化流程

以下動畫展示，用區域四叉樹 (Region Quad Tree) 實現關鍵點均勻化 (Distribution)。

圖解關鍵點均勻化 (Key Points Distribution)

步驟一、準備一張影像，假設目標提取 20 關鍵點。

步驟二、提取關鍵點，此時四叉樹 (Quad Tree) 有 1 個節點 (Node)。

步驟三、對於超過 1 關鍵點的 Node，一分為四，此時 4 Nodes。

步驟四、對於超過 1 關鍵點的 Node，一分為四，此時 16 Nodes。

步驟五、凍結只有 1 關鍵點的 Nodes，不得再分裂。

步驟六、丟棄空的 Nodes，此時 10 Nodes。

步驟七、Node 數將超過 20，從最多點的 Node 開始，一分為四，產生 34 Nodes。

步驟八、凍結只有 1 關鍵點的 Nodes，不得再分裂。

步驟九、丟棄空的 Nodes，此時 22 Nodes。

步驟十、Node 數達標，不必再分裂。對於多關鍵點的 Nodes，留下品質最好的點。

步驟十一、剩 22 關鍵點。

步驟十二、關鍵點均勻化完成。

實際情況

以上是圖解均勻化。注意第 7 步，可於分裂至 20 Nodes 時停止。若拋棄空 Nodes 後，剩餘 Node 數未達標，可繼續分裂。

實際上，每張影像應提取 2000 關鍵點，才能使系統順利定位。以下為真實均勻化效果，左邊原圖、右邊均勻化 :

結語

下一章節，會探討四叉樹 (Quad Tree) 資料結構、均勻化演算法的撰寫 !