[發明專利]應用維度混洗變換的實時三維空間搜索與點云配準的方法與系統

有效

• 申請號: 201880035588.0
• 申請日: 2018-03-29
• 公開（公告）號: CN110945499B
• 公開（公告）日: 2023-08-04
• 發明（設計）人: 牟志京
• 申請（專利權）人: 牟志京
• 主分類號: G06T7/30
• 分類號: G06T7/30;G06V20/64;G06V10/50;G06V10/42
• 代理公司: 北京英創嘉友知識產權代理事務所(普通合伙) 11447
• 代理人: 南毅寧

本文件涉及維度混洗變換(DST)，它將三維空間映射到一維空間，并在遞歸層次結構中在一維近鄰關系中保留三維近鄰關系。通過DST，將對三維子空間中的點的搜索轉化為變換后的一維空間中的一個或多個搜索。通過將由變換索引的三維空間遞歸分解為子空間，利用變換后的空間結構，或通過直接索引到感興趣的區域，來執行搜索。對遞歸分解產生的子空間的搜索完全彼此獨立，從而為各種并行的基于DST的搜索方法提供了很多的機會。DST為快速且高效的點云壓縮提供了基礎，同時避免了對樹形數據結構的構建和遍歷。

相關申請的交叉參考

本公開要求2017年3月29日提交的申請號為62/478,422的臨時申請的權益。

技術領域

本公開涉及能夠在包括點云配準的諸多問題域中獲得顯著計算與熱力效率的計算變換、搜索、數據采樣以及其它操作。

背景技術

點云是由各種傳感器收集的三維數據集，各種傳感器諸如是激光探測與測距“LiDAR”傳感器、深度相機(Depth?Camera)或其它設備。點云配準(Point?CloudRegistration)迭代地將三維數據集的新的幀與之前對準了的幀進行對準，亦稱為“地圖(Map)”配準。在許多應用場景中，傳感器在三維空間中以六個自由度進行移動，而且每個新的幀通過空間變換而與先前的幀或者與先前對準了的幀的集合建立關聯。對三維數據集的一系列幀的配準是尋找剛性變換的過程，其中剛性變換包括位移和旋轉并用于在選定的坐標系中將幀進行對準。

點云配準在許多領域中具有廣泛的應用，包括計算機視覺、同時定位與地圖構建(Simultaneous?Localization?and?Mapping，“SLAM”)、機器人行動規劃、自動駕駛、對象識別、醫學成像、磁共振成像、虛擬與增強現實以及遙感三維建模。近年來，由于傳感和計算技術的飛速發展，許多新的應用已經成為可能，這使得三維數據集配準正成為許多科學、技術、商業應用和領域中越來越重要的組成部分。

迭代最近點(Iterative?Closest?Point，“ICP”)和廣義迭代最近點(“GICP”)是被廣泛應用于點云配準的方法。顧名思義，ICP依賴于三維空間的迭代搜索，因此實際上，它的性能主要由搜索的成本決定。基于K-d樹和其它樹的方法被用于對最近點進行搜索，而且這些基于樹的方法涉及昂貴的樹遍歷。實驗測試已經表明，通過采用任何已知的基于樹的方法進行三維空間搜索來執行實時點云配準都是不切實際的。

點云幀一般通過采樣進行壓縮以在幀對準之前減小它的基數(cardinality)，從而降低處理成本。為了確保壓縮不會導致大幅的精度下降，許多壓縮技術被設計，以從選定大小的每個三維體素中移除超出閾值數據點數的任意數據點。八叉樹(Octree)已經被提議用來實現這些壓縮技術，其要求存儲空間的大小與三個維度中每個維度的空間坐標范圍的乘積成比例，并且要求對于每個被檢查的點而言處理時間與八叉樹的大小的對數成比例。通過點云配準產生的對準后的點云幀或者說地圖被存儲在數據庫中。該數據庫隨著每一新的幀的處理而逐步建立，而且同時需要針對每一幀中的每一點予以搜索。

如熟悉科學技術的人所熟知的，在計算機系統中，方法或子系統的計算效率可用完成特定任務所使用的被處理指令的數量和存儲大小來衡量，并直接影響計算機系統的熱力效率，且是機電計算系統的重要的現實物理特性。計算機系統中方法或子系統的時間效率與物理計算機系統的實際性能直接相關，并且經常是實際應用中計算機系統實用性的重要決定因素。與應用、技術或系統的任何重要組成部分一樣，研究人員、設計人員、開發人員、制造商和銷售商都不斷地尋求更高效更快速的三維數據集配準方法與系統，并且在許多其它相關的應用和問題域中尋求改善的效率。

發明內容