楊 銘，陳建峰

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

一、引 言

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

二、CUDA編程技術(shù)

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

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

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

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

1．算法基本流程

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

圖1 CUDA編程技術(shù)

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

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

2．排序算法

窮舉式kNN查詢算法的第2步是對距離值進行排序。對于點云數(shù)據(jù)，kNN查詢只關(guān)心前k個最小的距離值，而一般情況下k值遠遠小于參考點個數(shù)m?；谶@一點，本文使用了一種適合于GPU實現(xiàn)的排序算法——改進的插入排序算法。

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

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

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

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

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

3．CUDA實現(xiàn)

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

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

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

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

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

四、基于外存的kNN查詢

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

1．雙層查詢結(jié)構(gòu)

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

圖3 基于CUDA的窮舉式kNN查詢算法的實現(xiàn)流程

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

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

2．具體實現(xiàn)

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

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

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

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

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

五、試驗與分析

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

表1 實際采集數(shù)據(jù)相關(guān)信息

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

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

試驗結(jié)果表明：當所有數(shù)據(jù)全部導(dǎo)入到內(nèi)存后，基于CUDA的kNN算法的查詢速度較基于ANN的kNN算法有大幅提升，特別是當數(shù)據(jù)量較大時，查詢速度增幅顯著。

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

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

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

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

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

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

六、結(jié)束語

本文根據(jù)點云數(shù)據(jù)的特點以及當前GPU硬件的特性，提出了一種通過CUDA實現(xiàn)的窮舉式kNN查詢算法。然后將該算法與傳統(tǒng)的層次查詢算法相結(jié)合，設(shè)計了一種基于外存的雙層查詢結(jié)構(gòu)，從而實現(xiàn)了海量點云數(shù)據(jù)的快速kNN查詢。試驗證明，筆者的方法與傳統(tǒng)算法相比在效率上有明顯提升，其為海量點云數(shù)據(jù)的后處理工作奠定了較好的基礎(chǔ)。然而，本文提出的窮舉式kNN查詢算法雖然充分利用了GPU強大的并行計算能力，但是其算法自身的時間復(fù)雜度過高，當點云數(shù)據(jù)量過大時其查詢效率顯著下降。因此，在今后的工作中有必要設(shè)計一種時間復(fù)雜度更低的并行查詢算法，以實現(xiàn)更為高效的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的通用并行計算庫的設(shè)計與研究[D]．成都：西南石油大學，2007．

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

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