張宇，劉坡，楊敏華，龔建華，3，黃明詳

（1.中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長沙 410083；2.中國科學(xué)院遙感與數(shù)字地球研究所遙感科學(xué)國家重點實驗室，北京 100101；3.浙江中科空間信息技術(shù)應(yīng)用研發(fā)中心，浙江 嘉興 314100；4.環(huán)境保護(hù)部信息中心，北京 100101）

0 引言

空間聚類作為聚類分析的一個研究方向，是指將空間數(shù)據(jù)集中的對象分成由相似對象組成的類，同類中的對象間具有較高的相似度，而不同類中的對象間差異較大［1］。空間聚類分析是空間數(shù)據(jù)挖掘與知識發(fā)現(xiàn)的主要手段之一，已廣泛應(yīng)用于地理學(xué)、地質(zhì)學(xué)、氣象學(xué)、地圖學(xué)、天文學(xué)及公共衛(wèi)生等諸多領(lǐng)域。但是由于空間數(shù)據(jù)的多尺度、高維度、模糊性等特點，造成空間聚類算法的創(chuàng)新研究困難較大。

二部圖聚類算法作為空間聚類算法的一種，以圖的形式表明數(shù)據(jù)集中數(shù)據(jù)間的關(guān)系，用以尋找不同要素間的對應(yīng)關(guān)系。要素集合根據(jù)不同的原則分割成2個不同的候選集合，候選集中每個要素具有相近的空間關(guān)系或者非空間關(guān)系，二部圖聚類算法旨在探究兩個或多個要素集中要素間的相關(guān)性，廣泛應(yīng)用于文本查詢和檢索等領(lǐng)域［2，3］。二部圖也應(yīng)用于解決空間聚類問題，利用距離、邊距以及相應(yīng)的B矩陣來獲得空間聚類知識，利用圖嵌入方法進(jìn)行影像分類［4］。利用二部圖聯(lián)合聚類分割可以解決異質(zhì)數(shù)據(jù)的聯(lián)合聚類分割問題［5，6］。海量空間數(shù)據(jù)的本身需要大量運算，現(xiàn)有的基于CPU的串行計算很難達(dá)到實時計算的要求，傳統(tǒng)的采用建立空間索引的方法來加速搜索效率［7－9］，如文獻(xiàn)［10］中提出了基于空間聯(lián)合索引計算鄰接矩陣的方法來計算空間聚類簇，該方法基于頁訪問序列，利用了限制的緩沖空間，通過啟發(fā)式的對稱聚類等方法獲得類別空間信息。GPU的出現(xiàn)，帶來了高性能計算的時代，統(tǒng)一計算設(shè)備架構(gòu)（CUDA）的推出，為高性能計算開創(chuàng)了新時代［11，12］。文獻(xiàn)［13］將 GPU 引入 K均值聚類算法中，利用GPU高度并行的特點可以明顯提高聚類的速度。

多源空間數(shù)據(jù)的匹配，是空間數(shù)據(jù)合并、更新的基礎(chǔ)，具有巨大的研究價值，而且多源空間數(shù)據(jù)匹配問題本身就是空間數(shù)據(jù)聚類的問題［14］。本文將GPU引入二部圖匹配的聯(lián)合聚類算法的過程中，以多源空間數(shù)據(jù)的匹配為例，首先將空間數(shù)據(jù)的匹配分解成一個二部圖匹配的問題，進(jìn)而驗證GPU并行計算對空間聚類算法效率的影響和不同儲存器對計算效率的影響。

1 二部圖聯(lián)合聚類

二部圖G（V，E）表示要素間的空間關(guān)系，其中V用于表示空間要素索引的節(jié)點，E用于表示有關(guān)系空間要素索引的連線。如果空間中的兩個要素集中要素存在關(guān)系，則有E≠0，E將這兩個空間要素連接起來。如圖1a、圖1b所示，用A、B兩個地理要素集合表示同一個地區(qū)不同時相的數(shù)據(jù)，數(shù)據(jù)集A中包含有要素（A1，A2，A3），數(shù)據(jù)集B 中包含有要素（B1，B2，B3），可以用圖1c表示要素之間的疊置關(guān)系。該問題是一個典型的二部圖聯(lián)合聚類問題，可用二部圖聚類算法判定空間要素間的對應(yīng)關(guān)系。

圖1 基于疊置關(guān)系的空間聚類Fig.1 Co－clustering based on overlay relationship

二部圖聚類算法主要的流程如圖2所示：1）計算要素間的空間關(guān)系，本文以疊置關(guān)系為判斷依據(jù)。2）根據(jù)要素的空間關(guān)系，構(gòu)建二部圖關(guān)系，即構(gòu)建關(guān)系矩陣及鄰接矩陣。3）根據(jù)鄰接矩陣，進(jìn)行二部圖聯(lián)合聚類，每次聚類后計算判斷矩陣中非0要素的數(shù)目的變化，直到要素的數(shù)目不變?yōu)橹埂?）根據(jù)最終的聯(lián)合聚類結(jié)果，提取不同要素間的對應(yīng)關(guān)系。

圖2 二部圖聚類Fig.2 Bipartite graph co－clustering

1.1 空間關(guān)系

確定兩個要素集間的拓?fù)潢P(guān)系和權(quán)重是構(gòu)建二部圖的基礎(chǔ)?？臻g拓?fù)潢P(guān)系一般采用9交模型描述空間數(shù)據(jù)的拓?fù)潢P(guān)系［15］。為了加快計算的速度，可利用plane－sweep［7］、TR＊樹［8］和R樹［9］等算法建立空間索引以加快要素空間關(guān)系的搜索，本文主要計算要素之間的疊置關(guān)系。

1.2 構(gòu)建二部圖

確定兩個地理要素集中每個要素的對應(yīng)關(guān)系之后，需要進(jìn)一步將有關(guān)系的要素都集中到同一個空間要素簇下。Huh等提出利用鄰接關(guān)系矩陣計算空間要素的聚類集［14］?？臻g數(shù)據(jù)之間多對多關(guān)系由于涉及兩個要素集中的多個要素，較難確定聚類集。這可以通過如下的過程來判斷：假設(shè)一個要素集中的要素與另一個要素集中的多個要素重疊，則將多個要素合并為一個連續(xù)要素，如果這個合并要素又與前一個要素集中的多個要素重疊，多個重疊要素同樣進(jìn)行合并，反復(fù)進(jìn)行這個過程直到得到合并要素的關(guān)系為1∶1為止［14］。假定兩個地理要素集分別為Ai（i＝0，1，2，3，…，m），Bj（j＝0，1，2，…，n），對于每個地理要素集中的要素，都有Ai∈A，Bj∈B。如果兩個要素存在疊置關(guān)系，則Ai與Bj在二部圖上存在邊，Ai與Bj的地理編碼可視為連接邊兩端的節(jié)點。假設(shè)二部圖中兩地理要素集中要素間的邊權(quán)重都為1，構(gòu)建關(guān)系矩陣C。其中，C中每一行表示要素集A中每個要素的地理編碼，C中每一列表示要素集B中每個要素的地理編碼，用于表示Ai與Bj的疊置關(guān)系，可表示為：

在圖1中，假設(shè)數(shù)據(jù)集A和B中要素間對應(yīng)關(guān)系為（A1，B2，B3），（A2，A3，B3），由于要素集A 中要素記錄為矩陣C中的行，要素集B中要素記錄為矩陣C中的列，矩陣C表示為：

構(gòu)建鄰接矩陣C′，其中I為單位矩陣，C′表示節(jié)點間所有的鄰接關(guān)系（包括自相鄰關(guān)系）：

1.3 矩陣運算和確定關(guān)系

對鄰接矩陣C′連續(xù)自乘，直到所有為0的元素值不再發(fā)生變化，便可得到結(jié)果矩陣，其中每一行非0實體表現(xiàn)出要素間的鄰接關(guān)系。圖1中的鄰接矩陣C′自乘3次后，矩陣元素為0的位置不再發(fā)生變化。為了簡化計算結(jié)果，將矩陣中所有的非0元素表示為1，結(jié)果矩陣C″表示C′自乘3次之后的結(jié)果，如式（4）所示：

其中：C″的第一行表示得到空間聚類簇（A1，A2，A3）與（B2，B3）間3∶2的對應(yīng)關(guān)系。第四行中，只有一個要素，其余位置處均為0，對應(yīng)的要素為B1，表示要素集A中沒有任何要素與B1對應(yīng)。

2 GPU并行算法設(shè)計

CUDA的基本思想是將應(yīng)用程序映射到GPU以獲得較大的性能提升，盡量的開發(fā)線程級并行算法，將GPU作為超大規(guī)模數(shù)據(jù)并行協(xié)處理器，讓GPU運行一些能夠被高度線程化的程序，充分發(fā)揮GPU并行處理能力并極大提高單個計算節(jié)點的計算性能。CUDA采用單指令多線程（SIMT）執(zhí)行模型，執(zhí)行數(shù)據(jù)寬度將作為硬件細(xì)節(jié)被隱藏起來，硬件可以自動地適應(yīng)不同執(zhí)行寬度，而且每個線程的寄存器是私有的，線程間只能通過共享存儲器和同步機(jī)制通信。GPU采用的是由硬件管理的輕量級線程，實現(xiàn)零開銷線程切換，用計算隱藏延遲。

2.1 并行算法設(shè)計分析

由于空間數(shù)據(jù)計算數(shù)量的擴(kuò)大，導(dǎo)致構(gòu)建鄰接矩陣的維度增大，計算速度降低。采用GPU并行加速算法，計算時間和電腦資源的開銷將會減少?？梢岳肎PU高度并行的特點快速提高二部圖聚類算法過程中的鄰接矩陣運算效率，主要包括矩陣自乘和計算矩陣中非0的個數(shù)。

2.1.1 矩陣自乘并行性分析 假設(shè)一個M×N大小的關(guān)系矩陣C，其鄰接矩陣C′大小為（M＋N）×（M＋N）。對于矩陣自乘，由于每個要素都是獨立計算的，理論上可同時運行（M＋N）×（M＋N）線程來同步計算，但是由于硬件的限制，每次啟動的線程塊和每個塊中線程的數(shù)量都有限制。每一個內(nèi)核的配置項包括問題的分塊數(shù)griddim及每個塊內(nèi)的線程數(shù)目blockdim，增加線程塊中線程數(shù)目可能會降低在多處理器中投入運行的實際線程塊數(shù)，降低并行度。假設(shè)矩陣計算中每個塊的大小為Width×Length，鄰接矩陣可以劃分為（M＋Width－1）／16×（N＋Length－1）／16個塊，每個塊中有Width×Length線程執(zhí)行計算。

GPU以warp為單位調(diào)度和執(zhí)行，每個warp擁有32個線程，若線程調(diào)度數(shù)目不足32個，則會因warp塊填充不足而造成計算資源的浪費，損失部分效率。而對于存儲器的訪問，是以half－warp為單位進(jìn)行的，因此提高運算效率就要使劃分的線程矩陣維度為16的倍數(shù)。對于GeForce 9800GT，由于每個SM（流多處理器）中最多有768個線程，8個SP（流處理器），處理效率最佳時，線程塊的數(shù)目應(yīng)滿足768／（Width×Length）＜8。

2.1.2 計算矩陣非0元素并行性分析 當(dāng)鄰接矩陣相乘次數(shù)大于等于2時，需要判斷矩陣中非0元素的個數(shù)。對于（M＋N）×（M＋N）要素的鄰接矩陣非0元素個數(shù)的計算，可視為并行歸約的過程?？梢詫⒃撗h(huán)計算分解為（M＋N）×（M＋N）線程以完成計算，考慮不同的分塊和分線程完成計算，假設(shè)每個塊中有512個線程，過程如下：第一次循環(huán)，只有i＝0，2，4，…，510線程執(zhí)行計算，即每個線程與其后跨度為1的元素加操作；第二次循環(huán)，只有i＝0，4，8，12，…，508線程執(zhí)行計算，即每個要素與其后跨度為2的元素加操作；依次類推……直到最后一次循環(huán)，即i＝0線程執(zhí)行計算。此時線程i＝0中記錄的結(jié)果即為要素中非0元素的個數(shù)。

2.2 并行算法設(shè)計優(yōu)化

CUDA內(nèi)部存在6種存儲器，分別是寄存器、局部存儲器、共享存儲器、全局存儲器、常數(shù)存儲器和紋理存儲器，應(yīng)依據(jù)具體研究內(nèi)容選擇合適的存儲設(shè)備從而最大限度地提高算法的效率，本文探討采用全局存儲器和共享存儲器完成計算。

2.2.1 全局存儲器 全局存儲器使用的是普通的顯存，存儲內(nèi)核中輸入輸出數(shù)據(jù)，容量較大，整個網(wǎng)格中的任意線程都能讀寫全局存儲器的任意位置。在計算能力較低的GPU設(shè)備中，缺少對數(shù)據(jù)的緩存，采用全局存儲器操作數(shù)據(jù)時將導(dǎo)致400～600個時鐘周期的延遲，而且在計算過程中有許多重復(fù)的數(shù)據(jù)存儲訪問。因此，必須最小化對全局存儲器的訪問并應(yīng)設(shè)計考慮SM中數(shù)據(jù)重用。

使用全局存儲器進(jìn)行鄰接矩陣運算時，GPU可實現(xiàn)在GPU－DRAM的任何位置讀取到GPU中的聚集操作。如果計算的矩陣大小不超過GPU的計算能力，可利用CUDA的API中的cudaMemcpy（）一次性將鄰接矩陣數(shù)據(jù)由內(nèi)存全部加載到GPU全局存儲器中。

2.2.2 共享存儲器 共享存儲器位于每個SM內(nèi)，同一個SM上的線程可訪問一個共享存儲器，實現(xiàn)高速數(shù)據(jù)交換。通過線程間的合作，可以將全局存儲器的流量減少到原來的1／16，避免了數(shù)據(jù)的重復(fù)讀取和存儲，提高了運算效率。共享存儲器位于GPU片內(nèi)，速度比局部存儲器、全局存儲器快很多。在不發(fā)生bank沖突的情況下，共享存儲器的延遲幾乎只有局部存儲器或全局存儲器的1／100，訪問速度和寄存器相當(dāng)。對共享存儲器的訪問是以半個warp為單位，訪問將會以前16個線程或后16個線程的方式進(jìn)行。半warp中的線程訪問的數(shù)組元素分別屬于不同bank時，不會發(fā)生訪問沖突；當(dāng)半warp中的線程訪問的數(shù)據(jù)元素處于同一個bank時，其讀寫操作不能同時進(jìn)行，發(fā)生訪問沖突，造成運算錯誤?？紤]到每個程序中字節(jié)的大小，算法以4的倍數(shù)設(shè)置進(jìn)行等間隔的訪問以避免沖突。

共享存儲器在每個流處理器中只有16KB的存儲空間，算法要考慮到共享存儲器的大小。設(shè)計每個線程塊的共享空間大小為16×16，對于實驗中處理的int類型的變量，每個共享存儲空間中的數(shù)據(jù)小于16KB。若鄰接矩陣不超過GPU的運算能力，則將鄰接矩陣全部調(diào)入全局存儲器中，每個SM中的共享存儲器分別對應(yīng)處理一個矩陣塊。根據(jù)矩陣元素的標(biāo)識將相應(yīng)的數(shù)據(jù)調(diào)入對應(yīng)的共享存儲器中進(jìn)行運算，用矩陣塊Ai中的每一行乘以矩陣塊Bj中的每一列，并將計算結(jié)果按照數(shù)據(jù)對應(yīng)行列進(jìn)行相加計算，接著依次對該行列中相應(yīng)的矩陣塊相加，將結(jié)果保存在矩陣C中的相應(yīng)位置處。由于同一個線程塊共用一個共享存儲器，因此，每個線程塊中各線程可以重復(fù)利用加載到共享存儲器中的數(shù)據(jù)，減少了數(shù)據(jù)的重復(fù)存取。最后將運算結(jié)果由全局存儲器載入到內(nèi)存中。

3 實驗及分析

實驗采用GeForce 9800GT顯卡，顯存容量為1 G，計算能力為1.1，時鐘頻率為1.50GHz，有12個流多處理器，每個流多處理器中有8個流處理器，每個流處理器中有16KB的共享存儲器。采用浙江海鹽地區(qū)不同時相的多尺度數(shù)據(jù)，驗證本文的算法和不同配置情況下的GPU運行效率。對于不同來源的空間數(shù)據(jù)，首先將其投影到統(tǒng)一的空間坐標(biāo)體系下，然后確定不同空間數(shù)據(jù)集間的拓?fù)浏B置關(guān)系，根據(jù)式（3）構(gòu)建鄰接矩陣，通過GPU并行計算確定要素之間的關(guān)系，得到空間聚類結(jié)果。實驗在vs2008.net環(huán)境下，利用 ArcEngine 9.3，CUDA Toolkit 5.0工具包開發(fā)，并將并行算法封裝為動態(tài)鏈接庫（DLL），完成整個實驗過程。

3.1 CPU串行和GPU并行比較

針對同一個地區(qū)的多尺度和多時相的兩個地理要素集做空間聯(lián)合聚類運算，先執(zhí)行CPU串行計算，再分別執(zhí)行基于GPU全局存儲器和基于GPU共享存儲器的并行計算，計算時間統(tǒng)計如表1所示。

由表1可以看出，基于GPU共享存儲器的計算效率最高，其次是基于GPU全局存儲器的計算效率，而基于CPU串行計算的效率最低。利用GPU并行計算比利用CPU串行計算的執(zhí)行效率高。此實驗中的鄰接矩陣大小為1 103×1 103，矩陣自乘次數(shù)為12次，矩陣元素類型為整型，處理數(shù)據(jù)量大小為55.69MB，分別計算這三者的計算速率：1）GPU全局存儲器并行計算：55.69MB÷13.726s≈4.1 MB／s；2）GPU 共享存儲器并行計算：55.69MB÷0.9935s≈56.1MB／s；3）CPU串行計算：55.69MB÷853s≈0.065MB／s?？梢钥闯觯珿PU共享存儲器運算效率是GPU全局存儲器運算效率的14倍，是CPU串行計算效率的858倍。在此類情況下，GPU并行計算應(yīng)使用共享存儲器提高算法的效率。

表2是不同空間二部圖聯(lián)合聚類中，執(zhí)行GPU共享存儲器計算與執(zhí)行CPU串行計算的時間和加速比。從表中可以看出，隨著矩陣維度的擴(kuò)大，對應(yīng)的循環(huán)次數(shù)不確定，并且加速比有增大的趨勢，但是達(dá)到一定的維度后，趨于穩(wěn)定。其中在矩陣維度為1 103時，加速比最大，表明此時GPU共享存儲器運算效率是CPU串行計算效率的858倍。

表2 不同維度下的串并行性能比較Table 2 Comparison of serial and parallel performance under different dimensional

3.2 GPU在處理不同數(shù)據(jù)量時的效率

使用GPU共享存儲器在處理不同數(shù)據(jù)量時，進(jìn)行空間聚類并行計算的效率有明顯的不同，實驗選取同一地區(qū)的多時相、多尺度數(shù)據(jù)進(jìn)行空間二部圖聯(lián)合聚類，統(tǒng)計結(jié)果如表3所示。由表3可知，由于空間要素聚類關(guān)系的多樣性，構(gòu)建的鄰接矩陣的維度明顯不同，鄰接矩陣的循環(huán)次數(shù)也表現(xiàn)出無規(guī)律性。但隨著矩陣維度的增大，并行計算中單次循環(huán)平均耗時也越來越多。運算效率不僅與維度相關(guān)，還與循環(huán)次數(shù)相關(guān)。如果兩個要素集中要素間存在疊置關(guān)系，則對應(yīng)鄰接矩陣中的權(quán)重為1，矩陣中權(quán)重為1的矩陣元素的數(shù)目決定著矩陣的復(fù)雜度以及最終的運算效率。直到所有的關(guān)系要素都合并為1∶1，得到最終的空間聚類簇。

表3 不同維度下GPU共享存儲器運算結(jié)果Table 3 Calculation result of GPU shared memory under the different dimensional

3.3 Warp占有率對GPU運算效率的影響

通過實驗對經(jīng)過優(yōu)化的并行二分圖聚類算法在設(shè)計中的各種參數(shù)對于系統(tǒng)性能的影響進(jìn)行分析。圖3表示的是每個線程塊中不同線程數(shù)量對warp占有率的影響，其中三角形標(biāo)記處是設(shè)計的線程模塊的分配大小，每個線程塊中有256個線程，此時warp占有率最高。圖4表示的是不同寄存器數(shù)量對warp占有率的影響，其中三角形標(biāo)記處是每個線程分配的寄存器個數(shù)，每個線程中擁有的寄存器數(shù)量為8，此時warp占有率最高。在每個線程的寄存器數(shù)量多于32個時，每個SM中最多有8 129個寄存器文件，此時warp占有率為0。圖5表示的是不同的共享內(nèi)存對warp占有率的影響，其中三角形標(biāo)記處是每個塊分配的共享存儲器大小，每個線程塊中擁有的共享內(nèi)存大小為1 024bytes，此時warp占有率最高。當(dāng)共享內(nèi)存大小大于16KB時，由于每個SM中最多有16KB共享內(nèi)存，此時warp占有率將降為0。本文中線程的劃分正好滿足此類條件，warp占有率最佳。

圖3 線程數(shù)對warp占有率的影響Fig.3 The affection of threads to warp occupancy

圖4 寄存器對warp占有率的影響Fig.4 The affection of registers to warp occupancy

圖5 共享內(nèi)存對warp占有率的影響Fig.5 The affection of shared memory to warp occupancy

4 結(jié)論

空間聚類算法是一個計算密集型算法，對計算資源有著巨大的需求，對于有潛在并行的算法，GPU的并行計算可以顯著提高聚類的計算效率。根據(jù)GPU硬件特征和研究對象的不同劃定GPU線程的大小，使運算效率最優(yōu)化。特別是海量空間數(shù)據(jù)聚類，GPU并行計算將會有明顯的優(yōu)勢。本文將GPU并行計算運用到二部圖聯(lián)合聚類算法中，實驗結(jié)果表明，基于GPU的并行計算將會給空間聯(lián)合聚類算法的效率帶來顯著的提升。此外，空間索引也是提高數(shù)據(jù)處理速度的一種有效的手段，如何將空間數(shù)據(jù)索引與GPU并行計算結(jié)合，將是下一步研究的方向。

［1］ 席景科，譚海樵.空間聚類分析及評價方法［J］.計算機(jī)工程與設(shè)計，2009（7）：1712－1715.

［2］ 張軍偉，王念濱，黃少濱，等.二分K均值聚類算法優(yōu)化及并行化研究［J］.計算機(jī)工程，2011（17）：23－25.

［3］ ZHA H，HE X，DING C，et al.，Bipartite graph partitioning and data clustering［A］.Proceedings of the Tenth International Conference on Information and Knowledge Management［C］.2001.25－32.

［4］ CZECH W.Invariants of distance K－graphs for graph embedding［J］.Pattern Recognition Letters，2012，33（15）：1968－1979.

［5］ FERN X Z，BRODLEY C E.Solving cluster ensemble problems by bipartite graph partitioning［A］.Proceedings of the Twenty－First International Conference on Machine Learning［C］.2004.36.

［6］ REGE M，DONG M，F(xiàn)OTOUHI F.Bipartite isoperimetric graph partitioning for data co－clustering［J］.Data Mine Knowledge Discovery，2008，16（3）：276－312.

［7］ BRINKHOFF T，KRIEGEL H P，SCHNEIDER R，et al.Multistep processing of spatial joins［J］.ACM，1994，23（2）：197－208.

［8］ ZHANG J，YOU S，GRUENWALD L.High－Performance Spatial Join Processing on GPUs with Applications to Large－Scale Taxi Trip Data［R］.2012.

［9］ BRINKHOFF T，KRIEGEL H P，SEEGER B.Parallel processing of spatial joins using R－trees，data engineering［A］.Proceedings of the Twelfth International Conference，IEEE［C］.1996.258－265.

［10］ SHEKHAR S，LU C T，CHAWLA S，et al.Efficient join－index－based spatial－join processing：A clustering approach［J］.IEEE Transactions on Knowledge and Data Engineering，2002，14（6）：1400－1421.

［11］ OWENS J D，HOUSTON M，LUEBKE D，et al.GPU computing［A］.Proceedings of the IEEE［C］.2008，96（5）：879－899.

［12］ 肖漢，周清雷，張祖勛.基于多GPU的Harris角點檢測并行算法［J］.武漢大學(xué)學(xué)報（信息科學(xué)版），2012（7）：876－881.

［13］ FARIVAR R，REBOLLEDO D，CHAN E，et al.A parallel implementation of K－Means clustering on GPUs［A］.Proceedings of International Conference on Parallel and Distributed Processing Techniques and Applications（PDPTA）［C］.Las Vegas，Nevada，USA，F(xiàn)，2008.340－345.

［14］ HUH Y，YU K，HEO J.Detecting conjugate－point pairs for map alignment between two polygon datasets［J］.Computers，Environment and Urban Systems，2011，35（3）：250－262.

［15］ 李成名，陳軍.空間關(guān)系描述的9－交模型［J］.武漢測繪科技大學(xué)學(xué)報，1997，22（3）：207－211.