基于CUDA的海量點云數據kNN查詢算法

楊 銘，陳建峰

(上海市測繪院浦東分院，上海200129)

一、引 言

傳統的kNN查詢算法一般都是首先通過空間層次結構找到待查詢點所處節點及其周圍節點，然后對這些節點內的采樣點進行距離計算，以此減少參與查詢的采樣點個數，從而提高查詢效率。此類算法通常都是串行算法，比較適合傳統的單核CPU系統，其查詢效率能在一定程度上滿足應用需要。然而隨著三維激光掃描技術的不斷發展，所能獲得的點云數據量越來越大，原有的基于單核CPU的kNN查詢算法的實現效率已經遠遠無法滿足海量點云數據后處理的要求。近年來，GPU硬件性能得到了飛速提升，而nVIDIA公司推出的CUDA技術更使得我們可以利用GPU高性能的并行計算能力解決許多原來無法解決的問題。據此，本文提出了一種基于CUDA的海量點云數據快速kNN查詢算法。

二、CUDA編程技術

CUDA是nVIDIA公司于2007年6月推出的一種將GPU作為數據并行計算設備的軟硬件體系，其是第一種不需要借助圖形學API就可以使用類C語言進行通用計算的開放環境與軟件系統。由于其在性能、成本和開發時間上較傳統的CPU解決方案有明顯優勢，CUDA的推出在學術界和產業界引起了強烈反響。現在，CUDA已經在天文學、信號處理、圖像處理、模式識別、視頻壓縮等領域獲得廣泛應用，并取得了豐碩成果。

CUDA的開發十分簡單，其采用了比較容易掌握的類C語言進行開發，而不需要借助任何圖形學API。熟悉C語言的開發人員能夠比較平穩的從CPU過渡到GPU，而不必重新學習語法。CUDA編程技術主要包含3個方面的內容：CUDA編程模型、CUDA存儲器模型及CUDA軟件體系。其中，CUDA編程模型將CPU作為主機，將GPU作為設備或協處理器(如圖1(a)所示)，在該模型中，CPU與GPU各司其職，協同工作，它們各自擁有相互獨立的存儲器地址空間：主機端的內存和設備端的顯存。除了編程模型，CUDA也規定了存儲器模型。在程序運行期間，CUDA線程可以訪問處于多個不同存儲器空間中的數據(如圖1(b)所示)。CUDA的軟件體系則由3個層次構成：CUDA driver API、CUDA runtime API和 CUDA Library(如圖 1(c)所示)。CUDA軟件體系的核心是CUDA C語言，其包含C語言的最小擴展集和一個運行時庫，使用這些擴展與運行時庫的源文件必須通過nvcc編譯器進行編譯。

三、基于CUDA的窮舉式kNN查詢

kNN查詢算法雖然經過多年研究已基本發展成熟，但在某些情況下其效率仍然不盡如人意。近年來，隨著GPU硬件的快速發展，基于GPU的通用計算技術已被廣泛應用于眾多計算密集型領域。本章將根據 GPU軟硬件的特性，提出一種通過CUDA實現的窮舉式kNN查詢算法。

1．算法基本流程

假設R為一個包含有m個點的d維參考點集，而Q是一個在同一空間中包含有n個點的查詢點集。kNN查詢的任務就是根據某一距離計算原則，在點集R中找到每個查詢點的k個最近鄰域點。對于窮舉式kNN算法(以下簡稱BF-kNN)，其基本流程如圖2所示。

圖1 CUDA編程技術

圖2 窮舉式kNN算法的基本流程

不難發現，上述算法的時間復雜度非常巨大：進行n×m次距離計算的時間復雜度為O(nmd)，而n次排序操作的時間復雜度為O(nmlogm)。然而窮舉式kNN算法具有高度的并行特性，即各點的距離計算以及排序操作相互獨立，能夠同時進行，這與GPU的并行計算特性十分吻合，利用GPU實現窮舉式kNN算法可以充分利用當前GPU強大的并行計算能力。

2．排序算法

窮舉式kNN查詢算法的第2步是對距離值進行排序。對于點云數據，kNN查詢只關心前k個最小的距離值，而一般情況下k值遠遠小于參考點個數m。基于這一點，本文使用了一種適合于GPU實現的排序算法——改進的插入排序算法。

插入排序算法是一種簡單直觀的排序算法，其基本思想是將一個元素插入到已排好序的有序表中，從而得到一個新的、元素數量增一的有序表。為了只獲得前k個最小值，本文對基本的插入排序算法做了一些修改，具體實現步驟如下。

1)根據基本的插入排序算法對數列中的前k個元素進行排序。

2)訪問數列中的第k+1個元素，從后到前逐個判斷其與前k個元素的大小，當找到第1個比其小的元素后，將其插入到該元素之后。

3)遍歷第k+1個元素之后的所有元素，重復步驟2)。

改進的插入排序算法易于實現，當k值較小時能獲得較快的查詢速度。

3．CUDA實現

鑒于該查詢算法由距離計算和排序兩部分組成，本文將CUDA的實現分為兩個階段(即兩個kernels函數)。

1)第1個kernels函數負責大小為m×n的距離矩陣計算。由于各點之間的距離計算完全獨立，距離矩陣的計算可完全并行完成，每個線程根據所給的查詢點qi和參考點rj獨立完成距離計算。

研究發現，MYB基因的表達可受多種非生物脅迫誘導而出現節律性的晝夜變化[39]，如遮光處理會抑制花青素苷合成通路中結構基因的表達，影響花被片著色[40]。光照處理后，‘索邦’花蕾中LhsorMYB12的表達量明顯高于黑暗處理，說明該基因的表達受到光照調節。啟動子分析結果顯示，LhsorMYB12序列上存在多個光響應元件，推測這些光響應元件可能與光照誘導LhsorMYB12表達上調相關。此外，光照處理4 h后 LhsorMYB12的表達量低于處理2 h和8 h時的表達量，說明該基因的表達可能還受到其他因子的調控，其啟動子中存在的參與晝夜節律調控的元件可能與LhsorMYB12表達量的變化相關。

2)第2個kernels函數對計算好的距離矩陣進行排序。由于每個查詢點的距離排序完全獨立，n個查詢點各自的排序操作可完全并行完成，每個線程負責一個查詢點的距離排序操作。

CUDA程序一般由主機端代碼與設備端代碼組成，基于CUDA的窮舉式kNN查詢的實現流程如圖3所示。

四、基于外存的kNN查詢

海量點云數據一般無法完全導入到內存中，因此只能將大部分數據存入硬盤。針對這一情況有必要設計一種通過CUDA實現的基于外存的kNN查詢算法，從而實現海量點云數據高效的 kNN查詢。

1．雙層查詢結構

傳統的kNN查詢算法為了提高查詢效率，往往通過空間層次結構建立，并只考慮查詢點周圍節點內的采樣點，計算它們與查詢點的距離。此類算法一般情況下只需要少量計算便可得到最終的結果，具有不錯的效率。但對于海量點云，由于其無法將所有的數據都放入內存，過深的層次結構不僅會增加建樹時間，還會因節點過多增加磁盤數據訪問延遲，從而降低查詢效率;而過于簡化的層次結構又會增加參與距離計算的采樣點個數，同樣也會影響查詢效率。

圖3 基于CUDA的窮舉式kNN查詢算法的實現流程

反觀基于CUDA的窮舉式kNN查詢算法，由于其充分利用了GPU強大的并行計算能力，因此其查詢效率與傳統的查詢算法相比優勢巨大。然而對于海量點云數據(特別是上千萬甚至過億的點云數據)，單純依靠該算法同樣也會造成巨大的時間消耗，因此需要做相關改進。

通過以上分析不難發現單純依靠GPU或單純依靠空間層次結構都不能較好的實現海量點云數據的高效kNN查詢，因此本文將這兩種方法進行有機結合，提出了一種雙層查詢結構。基本做法為：對整個點云數據進行遍歷，以較大的劃分閾值建立空間層級結構，其中閾值可根據點云數據量的大小確定(對于5000萬的點云，閾值大小可設為100萬)。在查詢時只需要進行少量的節點訪問便能獲得要進行距離計算的節點，然后根據窮舉式kNN查詢算法，利用GPU強大的并行計算能力對這些節點中的采樣點進行鄰域計算，快速獲得最近鄰域點，從而完成整個查詢操作。

2．具體實現

對于通過空間劃分獲得的，且具有顯式層次信息的點云多分辨率層次結構，在進行查詢時首先對該結構進行遍歷，確定查詢點所處葉子節點;然后利用窮舉式kNN查詢算法找到該葉子節點中與查詢點最近鄰的點。具體流程如下。

1)對于某個查詢點首先訪問層次結構的根節點，計算查詢點到根節點包圍盒的距離，并將其放入到節點包圍盒隊列(pqBoxes)中。

2)從pqBoxes中彈出第1個元素并對其進行訪問(第1次訪問時為根節點)，遍歷其所有子節點，計算它們的包圍盒與查詢點間的距離，然后逐個加入到pqBoxes中。

4)當pqKNN不為空后，判斷其最小距離值(對應的隊列元素記為pqKNN．top)是否小于pqBoxes中的最小距離值，如果是，則pqKNN中的最小距離值所對應的采樣點就是當前情況下的最近鄰點;如果不是，則繼續遍歷pqBoxes中的元素，重復步驟3)和步驟4)。

5)對于第2個查詢點，首先判斷其是否處于pqBoxes所維護的各個節點中，如果是，則只需重新計算查詢點與各節點間的距離并重新放入pqBoxes中，然后重復步驟3)和步驟4)即可;如果不是，則得首先訪問根節點，重復步驟1)～步驟4)。

五、試驗與分析

本節將根據上文提出的算法設計相關試驗，通過對比分析驗證算法的有效性。試驗平臺基本性能如下：Intel Core2 Q8200處理器(頻率2．33GHz)，3GB DDRⅡ內存，GeForce 9800 GT顯卡。試驗數據為實際采集數據，具體信息如表1所示。

表1 實際采集數據相關信息

1)試驗1為基于CUDA的窮舉式kNN查詢算法與ANN[1]查詢算法在查詢效率方面的比較。其是基于內存實現的，即所有數據都導入內存，對比試驗結果(k=20)如表2所示。

表2 窮舉式kNN查詢算法與ANN查詢算法的試驗結果對比 ms

試驗結果表明：當所有數據全部導入到內存后，基于CUDA的kNN算法的查詢速度較基于ANN的kNN算法有大幅提升，特別是當數據量較大時，查詢速度增幅顯著。

2)試驗2基于CUDA的雙層查詢算法與普通的基于外存查詢算法在查詢效率上的比較。其主要針對海量點云數據的kNN查詢。改進的雙層查詢算法與基本算法的區別在于：在kNN查詢的第2階段，改進算法是利用基于CUDA的窮舉式kNN查詢算法獲得葉子節點中的k個最近鄰點;而基本算法是利用ANN類庫來實現k最近鄰域查詢。當nmax為65 536，k為20時，對比試驗結果如表3所示。

表3 基本kNN查詢算法與改進查詢算法的實驗結果對比ms

試驗結果表明：本文提出的改進算法較基本算法在查詢速度上有所提升，但增幅較試驗1有明顯下降。究其原因主要是頻繁的數據調度產生了較大的訪問延遲，其對查詢速度的影響已經成為制約kNN查詢效率的首要影響因素。

在基于外存的kNN查詢算法中，節點大小是查詢效率的重要影響因子，以下試驗展示了不同節點大小(即不同的nmax值)對kNN查詢效率的影響。如圖4所示。

圖4 不同節點大小對kNN查詢效率的影響

試驗結果表明：對于基本算法，其查詢時間在開始階段隨nmax值的增大逐漸減少，當達到某個值后開始反向增加;而對于改進算法，其查詢時間隨著nmax值的增大持續減少。究其原因主要是改進算法所使用的基于CUDA的kNN查詢算法較一般的層次查詢算法在查詢速度上有明顯提升，這使得對于較大的nmax值該算法仍能獲得較快的查詢速度，而此時層級結構的深度較小，節點數據的訪問次數相對較少，訪問延遲有所降低，從而提高了查詢效率。值得注意的是，改進算法的查詢時間也并非一直減少，在nmax值增大過程中也會出現一個最小值。所以，在進行kNN查詢時應當根據點云數據的實際情況選擇合適的劃分閾值。

六、結束語

本文根據點云數據的特點以及當前GPU硬件的特性，提出了一種通過CUDA實現的窮舉式kNN查詢算法。然后將該算法與傳統的層次查詢算法相結合，設計了一種基于外存的雙層查詢結構，從而實現了海量點云數據的快速kNN查詢。試驗證明，筆者的方法與傳統算法相比在效率上有明顯提升，其為海量點云數據的后處理工作奠定了較好的基礎。然而，本文提出的窮舉式kNN查詢算法雖然充分利用了GPU強大的并行計算能力，但是其算法自身的時間復雜度過高，當點云數據量過大時其查詢效率顯著下降。因此，在今后的工作中有必要設計一種時間復雜度更低的并行查詢算法，以實現更為高效的kNN查詢。

[1]ARYA S，MOUNT D M，NETANYAHU N S．An Optimal Algorithm for Approximate Nearest Neighbor Searching[J]．Journal of the ACM，1998，45(6)：891-923．

[2]CEDERMAN D，TSIGAS P．GPU-quicksort：A Practical Quicksort Algorithm for Graphics Processors[C]∥Proceedings of the 16th Annual European Symposium on Algorithms．New York：[s．n．]，2008：246-258．

[3]CLARKSON K L．Fast Algorithm for the all Nearest Neighbors Problem[C]∥Proceedings of IEEE symposium on foundations of computer science．[S．l．]：Gengaga Learning Business Press，1983：226-232．

[4]GARCIA V，DEBREUVE E，BARLAUDM．Fast k Nearest Neighbor Search Using Gpu[C]∥Proceedings of IEEE computer society conference on CVPR．[S．l．]：[s．n．]，2008：1107-1112．

[5]ROUSSOPOULOS N，KELLEY S，VINCENT F．Nearest Neighbor Queries[C]∥Proceedings of the ACM SIGMOD conference．New York：[s．n．]，1995：71-79．

[6]SANKARANARAYANAN J，SAMET H，VARSHNEY A．A Fast All Nearest Neighbor Algorithm for Applications Involving Large Point-clouds[J]．Computers ＆ Graphics，2007，31(2)：157-174．

[7]丁鵬．基于 GPU的通用并行計算庫的設計與研究[D]．成都：西南石油大學，2007．

[8]黃淼，張海朝，李超．基于八叉樹空間分割的k近鄰搜索算 法[J]．計 算 機 應 用，2008，28(8)：2046-2048，2051．

[9]張舒，褚艷利．GPU高性能計算之CUDA[M]．北京：中國水利水電出版社，2009．