唐 麗

（重慶建筑工程職業(yè)學(xué)院，重慶 400072）

近年來，航空攝影成為攝影測(cè)量領(lǐng)域的熱門發(fā)展方向，其獲取的測(cè)量數(shù)據(jù)也逐步增多，對(duì)我國遙感影像的應(yīng)用起到了重要作用，更加有效地幫助我國研究開發(fā)遙感影像應(yīng)用的其他領(lǐng)域[1]。目前，礦山地質(zhì)所能容納的最大程度被礦山地質(zhì)環(huán)境超越，由此會(huì)誘導(dǎo)大規(guī)模地質(zhì)災(zāi)害，突發(fā)性災(zāi)害居多。在礦山地質(zhì)中，由于地形復(fù)雜，過多測(cè)量數(shù)據(jù)不能精確；在礦山地勢(shì)較平穩(wěn)時(shí)，存在數(shù)據(jù)冗余[2]。傳統(tǒng)測(cè)量數(shù)據(jù)處理方法，計(jì)算方法周期長、精度低、費(fèi)時(shí)。根據(jù)礦山地質(zhì)的性質(zhì)傳統(tǒng)數(shù)據(jù)處理方法不能計(jì)算得面面俱到，為此，本文提出了構(gòu)建環(huán)境測(cè)量數(shù)據(jù)自動(dòng)處理K-D方法，以提高在礦山地質(zhì)環(huán)境監(jiān)測(cè)中航空攝影測(cè)量數(shù)據(jù)處理效率、精度、計(jì)算時(shí)長[3]。

1 礦山地質(zhì)環(huán)境監(jiān)測(cè)中航空攝影測(cè)量數(shù)據(jù)的自動(dòng)處理方法

1.1 構(gòu)建環(huán)境測(cè)量數(shù)據(jù)自動(dòng)處理K-D樹

構(gòu)建環(huán)境測(cè)量數(shù)據(jù)自動(dòng)處理K-D樹屬于遞歸過程。我設(shè)計(jì)的數(shù)據(jù)自動(dòng)處理K-D樹算法含有兩個(gè)部分， K-D樹的構(gòu)建和K-D樹搜索。K-D樹的機(jī)制采用事件鏈為基礎(chǔ)，以事件鏈為機(jī)制的特點(diǎn)：當(dāng)前窗口數(shù)據(jù)點(diǎn)過期，輸出相關(guān)字詞可以規(guī)避計(jì)算skyline，通過排列時(shí)間順序的節(jié)點(diǎn)構(gòu)成的列表稱為事件。以K-D樹進(jìn)行索引，空間的特定區(qū)域，K-D表示每個(gè)非葉節(jié)點(diǎn)；數(shù)據(jù)點(diǎn)用每個(gè)葉節(jié)點(diǎn)表示；LeftChild：存儲(chǔ)節(jié)點(diǎn)左子樹的地址、由位于該節(jié)點(diǎn)分割，包括超平面左子空間內(nèi)所有數(shù)據(jù)點(diǎn)；RightChild ：存儲(chǔ)節(jié)點(diǎn)右子樹的地址、由位于該節(jié)點(diǎn)分割，包括超平面右子空間內(nèi)所有數(shù)據(jù)點(diǎn)，左、右均為空。存儲(chǔ)節(jié)點(diǎn)區(qū)域中，列表中的數(shù)據(jù)點(diǎn)地址根據(jù)數(shù)據(jù)點(diǎn)，進(jìn)行對(duì)應(yīng)時(shí)間排序；當(dāng)作為葉節(jié)點(diǎn)時(shí)，在只含一個(gè)數(shù)據(jù)點(diǎn)的情況下，列表中只有一個(gè)地址。

利用SWDC-5航空攝影技術(shù)獲取礦山地質(zhì)開采正射影像、實(shí)景三維成果。礦山航空影像，結(jié)合礦山歷年開采信息，監(jiān)測(cè)礦山地質(zhì)環(huán)境，構(gòu)建礦山地質(zhì)數(shù)據(jù)[4]。其次建設(shè)航測(cè)系統(tǒng)，完成數(shù)據(jù)庫，達(dá)成設(shè)計(jì)目標(biāo)。

由于 K-D樹算法在數(shù)據(jù)維度較低方面，凸顯出搜索性能優(yōu)勢(shì)，為提高匹配搜索速度，按照“降維”的方式方法，綜合無人機(jī)遙感影像優(yōu)勢(shì)，采用改進(jìn) K-D樹算法，研究出一種利用特征的匹配搜索模式。綜合實(shí)驗(yàn)，此方法優(yōu)點(diǎn)在于劃分?jǐn)?shù)據(jù)精準(zhǔn)，空間范圍用節(jié)點(diǎn)表示，在數(shù)據(jù)集過于密集時(shí)，對(duì)提高匹配搜索效率有很大幫助，數(shù)據(jù)集、向量維度、搜索速度均成正比[5]。

1.2 設(shè)計(jì)測(cè)量數(shù)據(jù)自動(dòng)處理算法

通過測(cè)量數(shù)據(jù)自動(dòng)處理K-D樹進(jìn)行數(shù)據(jù)管理，利用 K-D樹進(jìn)行索引校準(zhǔn)，設(shè)計(jì)出測(cè)量數(shù)據(jù)自動(dòng)處理算法。設(shè)數(shù)據(jù)集，其中，對(duì)應(yīng)的微簇結(jié)構(gòu)表示數(shù)據(jù)個(gè)數(shù)（本例就是n）；Mc表示中心點(diǎn)或均值，d代表最后一個(gè)非葉節(jié)點(diǎn)，即：

Ms表示平方和統(tǒng)計(jì)（為防止溢出被開方），即：

Md表示方差統(tǒng)計(jì)值，即：

通過以上可知，本文設(shè)計(jì)的K-D樹自動(dòng)處理算法能夠滿足對(duì)數(shù)據(jù)緊湊性和可恢復(fù)性的要求，主要對(duì)龐大的測(cè)量數(shù)據(jù)完成自動(dòng)處理[6]。

1.3 完成測(cè)量數(shù)據(jù)的自動(dòng)處理

航空攝影測(cè)量數(shù)據(jù)的自動(dòng)處理算法是基于距離的聚類算法。攝影測(cè)量數(shù)據(jù)的自動(dòng)處理算法認(rèn)為簇(cluster)是由相鄰近的對(duì)象組成，因此把簇作為目標(biāo)。此算法抽象為：假定樣本為，其中要將樣本聚類成k個(gè)簇，算法過程如下：

數(shù)據(jù)初始化，隨機(jī)選取質(zhì)心點(diǎn)(clustercentroids)，一般選取k個(gè)，u1,u2,...uk，其中

給定任意i(i∈ [ 1,m])根據(jù)Map任務(wù)計(jì)算：得出分類c(i)，設(shè)定為任意類別，

算法終止的依據(jù)：當(dāng)質(zhì)心點(diǎn)穩(wěn)定，數(shù)據(jù)不再變化。

構(gòu)建K-D樹算法在數(shù)據(jù)自動(dòng)處理中是一種常見的算法。算法還包含很多種類，除上述外，K-D樹算法還可以解決：遞歸關(guān)系、神經(jīng)網(wǎng)絡(luò)問題等。但個(gè)別結(jié)構(gòu)框架并不支持K-D樹算法，引入了一些新的問題，例如：靜態(tài)數(shù)據(jù)如果無需在迭代任務(wù)傳遞，能夠使網(wǎng)絡(luò)寬帶小化；輸出中間數(shù)據(jù)的計(jì)算，需要判斷迭代收斂等。

搜索閾值選?。荷煽s略影像的降采樣比為λ，那么范圍閾值應(yīng)滿足關(guān)系：

實(shí)驗(yàn)發(fā)現(xiàn)，取 n = 2 獲得的結(jié)果最佳。即像素外加兩個(gè)擴(kuò)展像素對(duì)應(yīng)的實(shí)際影像作為搜索半徑效果較好。同名像點(diǎn)均在同一搜索區(qū)域，有效避免了由于區(qū)域過大造成資源浪費(fèi)。通常實(shí)際應(yīng)用中，不同影像類型選擇合適閾值。如圖1所示，圓圈即代表像素。

圖1 降采樣比下影像生成合適閾值

上圖中，圓圈即代表像素，通過上述在降采樣比下影像生成合適閾值，完成測(cè)量數(shù)據(jù)K-D樹自動(dòng)處理算法，可知航空攝影測(cè)量數(shù)據(jù)的自動(dòng)處理算法是基于搜索半徑距離的聚類算法，以距離作為評(píng)價(jià)指標(biāo)：距離越近，兩個(gè)數(shù)據(jù)相似度就越大。

2 實(shí)驗(yàn)分析

2.1 實(shí)驗(yàn)準(zhǔn)備數(shù)據(jù)

為了驗(yàn)證本文K-D樹測(cè)量數(shù)據(jù)自動(dòng)處理算法的有效性，我通過公共數(shù)據(jù)集 KDD（CUP）99來構(gòu)建對(duì)應(yīng)的航空攝影數(shù)據(jù)的構(gòu)建與測(cè)試。KDD99 公共數(shù)據(jù)集是來自于某實(shí)驗(yàn)室收集的監(jiān)測(cè)數(shù)據(jù)，后來被整理成規(guī)范的公共數(shù)據(jù)集。實(shí)驗(yàn)系統(tǒng)配置為: Inter Core2 Duo P8600 2.4Gb 處理器、4 Gb 內(nèi)存；編程環(huán)境為: Microsoft Vis-ual Studio 2012。SIFT 和 SURF 特征提取和描述通過 OpenCV 庫函數(shù)實(shí)現(xiàn)。在上述實(shí)驗(yàn)環(huán)境中，K-D樹的快速搜索性能是否有優(yōu)勢(shì)，對(duì)K-D樹自動(dòng)處理算法和傳統(tǒng)窮盡搜索算法兩種算法進(jìn)行了實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行對(duì)比分析為驗(yàn)證。

2.2 對(duì)比數(shù)據(jù)處理點(diǎn)云離散度

本實(shí)驗(yàn)采用模擬方法。數(shù)據(jù)生成方式為: 以維度為128維、規(guī)模為500 個(gè)點(diǎn)為例，建立500×128 大小的二維數(shù)組，生成數(shù)組元素，再生成一個(gè)等維度、規(guī)模為M的數(shù)據(jù)集，代表進(jìn)行了M次不同的搜索。為減少對(duì)結(jié)果的影響，實(shí)驗(yàn)中M 取10 000。對(duì)查詢和待匹配數(shù)據(jù)集進(jìn)行匹配搜索，得到總匹配時(shí)間，再除以查詢數(shù)據(jù)集的規(guī)模M，計(jì)算出平均單次匹配搜索所用時(shí)長。在不同的維度、規(guī)模、流速下，獲取若干數(shù)據(jù)集，對(duì)兩種算法進(jìn)行以下分析，如圖2所示。

圖2 兩種算法在不同數(shù)據(jù)集規(guī)模下搜索數(shù)據(jù)時(shí)長

在不同數(shù)據(jù)規(guī)模下兩種數(shù)據(jù)處理算法的搜索時(shí)間，K-D樹處理算法比傳統(tǒng)窮盡搜索算法存在較大的性能優(yōu)勢(shì)。面對(duì)數(shù)據(jù)集較多匹配時(shí)，K-D樹對(duì)數(shù)據(jù)的處理速度較快。相同數(shù)據(jù)集數(shù)量下，K-D樹算法搜索數(shù)據(jù)時(shí)長較常規(guī)算法比較，是常規(guī)算法的3倍，并且K-D樹算法使對(duì)數(shù)據(jù)的處理更加精確。外界環(huán)境在測(cè)量中，存在很大影響，K-D樹的搜索時(shí)長對(duì)點(diǎn)云數(shù)據(jù)也存在相應(yīng)影響，因此，會(huì)導(dǎo)致采集的點(diǎn)云數(shù)據(jù)有一定不足，表現(xiàn)在數(shù)據(jù)稍顯集中，大部分?jǐn)?shù)據(jù)呈現(xiàn)集中性偏離，即主體：點(diǎn)云之外的點(diǎn)。分布的規(guī)律一般表現(xiàn)在：零散、不均勻地分布在點(diǎn)云周圍。經(jīng)研究分析發(fā)現(xiàn)，用一個(gè)分布點(diǎn)做分布圖，根據(jù)其在空間區(qū)域的分布，計(jì)算出到相鄰最近一點(diǎn)的距離，得出高斯分布，根據(jù)高斯分布可知，曲線形狀被影響，分析可知其兩個(gè)影響因素：均值的大小、標(biāo)準(zhǔn)差的變動(dòng)。由上述得出，離群點(diǎn)是平均距離大于標(biāo)準(zhǔn)范圍的點(diǎn)。研究發(fā)現(xiàn)濾波的統(tǒng)計(jì)，點(diǎn)云數(shù)據(jù)中任意一點(diǎn)，得到它相鄰區(qū)域內(nèi)所有點(diǎn)距離平均值，滿足高斯分布的條件。統(tǒng)計(jì)分析離散點(diǎn)是否受航空維度影響，在半徑濾波后存在不明顯波動(dòng)，數(shù)據(jù)波動(dòng)較??；在數(shù)據(jù)下采樣以后，數(shù)據(jù)波動(dòng)較大，數(shù)據(jù)量減少的較迅速。從計(jì)算上述算法的時(shí)長分析，K-D樹算法相對(duì)較快且準(zhǔn)確，對(duì)點(diǎn)云數(shù)據(jù)的處理效率有很大幫助。

由上述實(shí)驗(yàn)可知，我設(shè)計(jì)的K-D樹自動(dòng)處理算法較傳統(tǒng)窮盡搜索算法比，在數(shù)據(jù)集密集中有著較好的性能表現(xiàn)，呈現(xiàn)出良好適應(yīng)性和對(duì)數(shù)據(jù)的自動(dòng)處理能力。

3 結(jié)語

本文對(duì)測(cè)量數(shù)據(jù)的自動(dòng)處理算方法進(jìn)行了研究，設(shè)計(jì)了構(gòu)建環(huán)境測(cè)量數(shù)據(jù)自動(dòng)處理K-D樹方法，有效的提高了航空攝影測(cè)量數(shù)據(jù)體量大，解決了在礦山地質(zhì)環(huán)境中數(shù)據(jù)計(jì)算周期長、計(jì)算精度低等問題。但此測(cè)量數(shù)據(jù)的自動(dòng)處理算法還存在不足之處，構(gòu)建K-D樹時(shí)間相對(duì)較長，在礦山地質(zhì)低維度環(huán)境下，搜索效率相對(duì)較低，因此，在未來的研究中，應(yīng)加強(qiáng)該算法在地質(zhì)低維度環(huán)境中構(gòu)建K-D樹的時(shí)長，對(duì)數(shù)據(jù)集處理的搜索效率進(jìn)行提升。