王 浩，王 旭，王黎征

(1.南陽(yáng)理工學(xué)院數(shù)字媒體與藝術(shù)設(shè)計(jì)學(xué)院 河南 南陽(yáng) 473004；2.南陽(yáng)高等醫(yī)學(xué)?？茖W(xué)校第一附屬醫(yī)院 河南 南陽(yáng) 473000)

0 引言

在場(chǎng)景理解系統(tǒng)中，RGB圖像或者遙感衛(wèi)星圖像等二維空間的圖像僅僅提供了目標(biāo)的顏色、紋理、角點(diǎn)等關(guān)鍵信息和數(shù)據(jù)，由于缺少空間上的深度信息，在三維場(chǎng)景下，因光照不均勻、目標(biāo)易遮擋和位置易變化等原因，通常無(wú)法提取三維空間坐標(biāo)和目標(biāo)的重要空間信息。因此，學(xué)者們更加關(guān)注構(gòu)建3D場(chǎng)景理解技術(shù)來(lái)開發(fā)3D場(chǎng)景理解[1-3]方面的研究和實(shí)踐工作。因此，如何構(gòu)建三維場(chǎng)景數(shù)據(jù)集是非常關(guān)鍵的基礎(chǔ)性工作。

本文擬利用三維點(diǎn)云傳感器，運(yùn)用三維數(shù)據(jù)采集設(shè)備(如圖1所示)，發(fā)揮三維點(diǎn)云提供空間感知距離的優(yōu)勢(shì)，完成三維空間下對(duì)城市環(huán)境中目標(biāo)的三維圖像數(shù)據(jù)收集，這已經(jīng)成為三維點(diǎn)云目標(biāo)檢測(cè)、三維場(chǎng)景目標(biāo)分割，以及利用現(xiàn)有的人工智能算法實(shí)現(xiàn)三維目標(biāo)匹配的基礎(chǔ)。

圖1 三維數(shù)據(jù)采集設(shè)備

本文擬采用計(jì)算機(jī)視覺(jué)和激光雷達(dá)相結(jié)合的方式，并運(yùn)用雷達(dá)成像和高清影像技術(shù)來(lái)收集三維點(diǎn)云數(shù)據(jù)。在圖1中，構(gòu)建城市三維場(chǎng)景圖像的硬件設(shè)備可以分為如下幾種：(a)帶有傳感設(shè)備的三維數(shù)據(jù)采集車。其中包含采用基于激光掃描與全景影像相結(jié)合的車載移動(dòng)系統(tǒng)；(b)為含激光雷達(dá)的手推式采集車；(c)為三維深度攝像機(jī)及其支架；(d)為固定掃描儀；(e)采集人員背負(fù)采集設(shè)備。這些雷達(dá)成像和高清影像相結(jié)合的三維數(shù)據(jù)采集方式有3個(gè)方面的優(yōu)勢(shì)：第一、雷達(dá)掃描技術(shù)可以快速、準(zhǔn)確地識(shí)別遠(yuǎn)距離的三維空間信息，也就是，這可以得到大型、復(fù)雜、標(biāo)準(zhǔn)或不標(biāo)準(zhǔn)的實(shí)景3D空間幾何信息；第二、數(shù)據(jù)采集車或者背負(fù)式背包，移動(dòng)覆蓋范圍廣，且探測(cè)距離比Kinect的視野范圍要遠(yuǎn)很多；第三、志愿者背負(fù)式采集系統(tǒng)攜帶靈活方便且效果好，不受地理位置空間限制。

如圖1所示，既可以通過(guò)信息采集車遠(yuǎn)距離合成雷達(dá)成像和高清影像的方式得到三維點(diǎn)云圖，也可以背著3D采集設(shè)備得到近距離的三維點(diǎn)云圖，甚至全景路線圖也可以得到。

1 群智感知的數(shù)據(jù)采集方法

利用群智感知機(jī)制來(lái)完成三維場(chǎng)景下目標(biāo)點(diǎn)云收據(jù)收集，受到眾多學(xué)者的青睞[1-4]。他們從不同的機(jī)制、方案和模型角度，提出來(lái)各種各樣的算法和技術(shù)。然而，不同的算法和模型對(duì)應(yīng)的優(yōu)化參數(shù)各不相同。例如，在機(jī)會(huì)網(wǎng)絡(luò)的背景下，由于能夠容忍延時(shí)數(shù)據(jù)，群智感知平臺(tái)收集這些數(shù)據(jù)往往讓參與者有意識(shí)或者無(wú)意識(shí)地完成三維數(shù)據(jù)收集，或者分配相應(yīng)的任務(wù)。通常會(huì)感知或預(yù)測(cè)參與任務(wù)收集的志愿者，并且分析他們的行走路徑，進(jìn)而設(shè)計(jì)任務(wù)分配方案，這類情形的目標(biāo)往往是最小化完成任務(wù)的人數(shù)[4]，或者最大化完成任務(wù)的數(shù)量[5]，或者最小化總體的成本。本文關(guān)注在時(shí)間敏感的數(shù)據(jù)收集背景下，如何讓參與者有意識(shí)地移動(dòng)到指定地點(diǎn)并完成數(shù)據(jù)收集任務(wù)，優(yōu)化目標(biāo)使移動(dòng)距離最小化[6]，也就是，總體時(shí)間最小化來(lái)實(shí)現(xiàn)高效的數(shù)據(jù)收集。

群智感知的數(shù)據(jù)收集方式，在現(xiàn)有的數(shù)據(jù)收集機(jī)制中廣泛存在。例如，有的學(xué)者從模型的角度分析應(yīng)用背景，提出拍賣的任務(wù)方案和模型，讓更多的人來(lái)參與數(shù)據(jù)收集和任務(wù)分配；而原有的學(xué)者，從優(yōu)化目標(biāo)的角度出發(fā)，關(guān)注不同背景下的任務(wù)優(yōu)化目標(biāo)，在延時(shí)容忍的數(shù)據(jù)收集目標(biāo)下，群智平臺(tái)往往關(guān)注數(shù)據(jù)收集的志愿者無(wú)意識(shí)或者有意識(shí)地收集數(shù)據(jù)，也會(huì)預(yù)測(cè)志愿者的路徑，進(jìn)而設(shè)計(jì)任務(wù)分配方案，其目標(biāo)往往是優(yōu)化完成任務(wù)的開銷。

2 研究現(xiàn)狀

就實(shí)現(xiàn)最大任務(wù)最小化的目標(biāo)而言，本文工作的關(guān)注點(diǎn)和距離優(yōu)化的相關(guān)成果最相似，例如：Soylu等人提出的GVNS算法[6,7]，在該算法中他們[6]設(shè)計(jì)出總體長(zhǎng)度最小化的總體優(yōu)化目標(biāo)，其應(yīng)用背景是土耳其某城市的網(wǎng)絡(luò)信號(hào)燈故障檢查問(wèn)題，由10名相關(guān)志愿員共同合作，完成將近200個(gè)故障信號(hào)燈的訪問(wèn),他們?cè)O(shè)計(jì)的GVNS 算法能夠?qū)崿F(xiàn)總體任務(wù)的成本開銷最小，通過(guò)變領(lǐng)域搜索機(jī)制來(lái)交換相鄰區(qū)域的任務(wù)分配。此外，該算法利用多個(gè)鄰居之間的移動(dòng)位置交換，實(shí)現(xiàn)重新調(diào)整相鄰區(qū)域之間的任務(wù)分配，他們采用的具體算法有 n點(diǎn)移動(dòng)、3-opt移動(dòng)、2-opt最優(yōu)點(diǎn)移動(dòng)、3-opt點(diǎn)移動(dòng)和 2-opt 等多種任務(wù)交換的方式[8,9]實(shí)現(xiàn)有機(jī)的任務(wù)分配機(jī)制。Wang等人[7]分析了在時(shí)間約束情形下，多旅行商問(wèn)題(MTSP)及其變化模式，設(shè)計(jì)的任務(wù)分配平臺(tái)是參與者從原點(diǎn)出發(fā)，并最終回到原出發(fā)點(diǎn)的任務(wù)分配情形，并確定了最長(zhǎng)距離最小化的優(yōu)化目標(biāo)。

3 基于密目的單項(xiàng)變鄰域算法

首先，本文分析任務(wù)分布的異構(gòu)性特征，群智感知平臺(tái)的任務(wù)分布往往是零散的，換句話說(shuō)，有的任務(wù)地點(diǎn)分布稀疏；有的任務(wù)地點(diǎn)分布稠密。通常情況下，任務(wù)分布稀疏的區(qū)域，收集任務(wù)的參與者付出較長(zhǎng)的行走時(shí)間，完成任務(wù)收集的數(shù)量卻較少；然而，任務(wù)分布稠密的區(qū)域，任務(wù)收集的參與者付出較短的行走時(shí)間，完成任務(wù)收集的數(shù)量卻較多，群智感知平臺(tái)的任務(wù)分布具有非均勻分布特性，也就稱為任務(wù)分布的異構(gòu)性特征[10,11]。

在本文中，我們關(guān)注高效數(shù)據(jù)收集問(wèn)題，這可以形式化為公式(1)：最小化時(shí)間消耗集合T(Γ)，這是由下面集合的最小值決定的{T(Γ1),T(Γ2),…,T(Γi),…,T(Γn)}。其中 |Γi| 的和應(yīng)該等于 |Γ|，因?yàn)棣＠锼腥蝿?wù)都要求參與者來(lái)完成。另外，針對(duì)某個(gè)具體的任務(wù)t∈Γ， 應(yīng)當(dāng)僅由一個(gè)參與者來(lái)完成，這主要避免任務(wù)重復(fù)分配。?Γi,Γi′∈{Γ1,Γ2 ,…,Γi,…,Γn},Γi∩Γi′ = ??？傊?，MMT 問(wèn)題可以表示如下

MMT:-MaxminT(Ti)

1

(1)

3.1 單區(qū)域?qū)ふ衣窂?/h3>

按照任務(wù)聚集點(diǎn)之間的距離，我們用 K-means 算法把所有任務(wù)聚類為n個(gè)區(qū)域，每個(gè)區(qū)域?qū)?yīng)一個(gè)參與者,單個(gè)區(qū)域內(nèi)時(shí)間消耗如圖2所示。

圖2 單區(qū)域任務(wù)收集模式

該時(shí)間消耗主要由兩部分組成：志愿者在指定路徑行走消耗的路徑時(shí)間和對(duì)三維目標(biāo)的數(shù)據(jù)采集消耗的收集時(shí)間。我們盡可能尋找單個(gè)區(qū)域內(nèi)耗總時(shí)間最小的路徑，讓其對(duì)應(yīng)的任務(wù)采集者按照某個(gè)指定區(qū)域所規(guī)劃的路徑，移動(dòng)并收集數(shù)據(jù)，進(jìn)而完成三維目標(biāo)的拍攝任務(wù)。

該算法的具體步驟描述如下：

第一步：隨機(jī)選擇本單個(gè)區(qū)域中三維任務(wù)收集點(diǎn)對(duì)應(yīng)的位置信息。

第二步：隨機(jī)選擇若干個(gè)位置(lt)，與之最近的位置，其距離可以從Dijkstra 算法的變形求得簡(jiǎn)單的結(jié)果，得到最近的位置lt+1，這是局部最優(yōu)的結(jié)果。如果L 中存在和序列l(wèi)1,l2,…,lt+1的局部序列相同，那么，該算法區(qū)選擇次近(次優(yōu))的位置任務(wù)，這樣就得到路徑中的最優(yōu)下一個(gè)位置，求解過(guò)程也是通過(guò) Dijkstra 算法及其變形依次求得。

第三步：刪除序列l(wèi)1,l2,…,lt+1的局部序列中的相同或者相近最優(yōu)解，這表示lt+1已經(jīng)加入l1,l2,…,lt+1序列，運(yùn)行Dijkstra 算法及其變形模式的結(jié)果，并返回第二步，直到增加所有任務(wù)點(diǎn)到 L 序列中。

第四步：為防止過(guò)早收斂，該算法使用2-opt和3-opt相結(jié)合的算法分析方式，刪除{l1,l2,…,lt,…} 序列中連續(xù)3個(gè)緊鄰節(jié)點(diǎn)之間的非相連弧。

第五步：我們?cè)黾有蛄衶l1,l2,…,lt,…} 逐步增加高效的序列及其組合，直到滿足L的前置條件。

從遺傳算法的自然適應(yīng)和選擇角度，不斷地選擇自適應(yīng)函數(shù)調(diào)整比率，如公式(2)所示

(2)

經(jīng)過(guò)數(shù)代的Meme選擇，子孫后代比父代具有更優(yōu)秀的遺傳基因，進(jìn)而選擇更優(yōu)的路徑實(shí)現(xiàn)路徑選擇。公示(2)中的適應(yīng)度函數(shù)可以用來(lái)評(píng)價(jià)路徑個(gè)體之間的優(yōu)劣程度，進(jìn)而判斷下一步選擇的路徑。具有較高適應(yīng)度F函數(shù)值的路徑，在下一代選擇中具有更高的繼承概率的個(gè)體。

3.2 區(qū)域之間的任務(wù)調(diào)整

我們所提出的MMT問(wèn)題，根本目標(biāo)是讓最大時(shí)間消耗的參與者花費(fèi)最少的代價(jià)，然而，這種代價(jià)由距離和任務(wù)分布特征，以及區(qū)域內(nèi)任務(wù)數(shù)量來(lái)決定。實(shí)際上，單位區(qū)域內(nèi)任務(wù)數(shù)量對(duì)總目標(biāo)MMT的實(shí)現(xiàn)，在時(shí)間消耗方面只是局部因素，因?yàn)橥瓿扇蝿?wù)的總時(shí)間開銷是MMT的重要組成部分。

本算法提出雙向變鄰域搜索結(jié)構(gòu)，交換相鄰區(qū)域任務(wù)，這不僅可以移動(dòng)相鄰任務(wù)采集點(diǎn)到某個(gè)區(qū)域，而且分析將其從相鄰區(qū)域把任務(wù)采集點(diǎn)劃分到本區(qū)域，以此達(dá)到局部最優(yōu)的目標(biāo)。如圖4左圖所示，在普通的變鄰域結(jié)構(gòu)中，算法僅僅根據(jù)任務(wù)分配的特點(diǎn)和采集數(shù)據(jù)的屬性，交換相鄰結(jié)構(gòu)中的一個(gè)或者兩個(gè)任務(wù)，從而改變路徑和任務(wù)分配方案。這樣的缺點(diǎn)非常明顯，只考慮單項(xiàng)的任務(wù)分配結(jié)構(gòu)和任務(wù)點(diǎn)的交換，這導(dǎo)致算法所考慮的任務(wù)分配結(jié)構(gòu)減少了很大的搜索空間。但是，在圖3的右圖中，我們利用BGVNS算法來(lái)調(diào)整邊界上的任務(wù)，考慮多個(gè)任務(wù)點(diǎn)的重新分配任務(wù)和路徑規(guī)劃，增大了搜索空間，考慮更加廣闊的搜索空間，這有利于算法準(zhǔn)確性的提高。

圖3 單向變鄰域任務(wù)搜索結(jié)構(gòu)

圖4 不同算法的定位誤差對(duì)比

4 實(shí)驗(yàn)

在本實(shí)驗(yàn)中，為了實(shí)現(xiàn)公平對(duì)比，GB-GVNS算法網(wǎng)絡(luò)邊長(zhǎng)在2000～3500 m的范圍內(nèi)進(jìn)行性能模擬測(cè)試，我們采用文獻(xiàn)[8]的地圖，針對(duì)城市中采用均勻分布/非均勻任務(wù)異構(gòu)分布的特征，通過(guò)實(shí)驗(yàn)對(duì)比參與者個(gè)數(shù)M對(duì)時(shí)間開銷的影響。在圖4的實(shí)驗(yàn)中，收集任務(wù)招募的志愿者個(gè)數(shù)都設(shè)置為6。 我們測(cè)試了網(wǎng)格邊長(zhǎng)對(duì)定位誤差的影響。由圖4可知，GB-GVNS算法整體性能較好，定位誤差較其他同類算法要低，且隨著網(wǎng)格邊上M的增大，定位誤差隨之降低，但變化不明顯。

在時(shí)間開銷中，我們根據(jù)具體的場(chǎng)景，用不同算法進(jìn)行試驗(yàn)。為了驗(yàn)證算法的可用性，本部分采用完整的數(shù)據(jù)采集方案，在不同背景下分配任務(wù)，進(jìn)而按照時(shí)間的節(jié)點(diǎn)，給出時(shí)間開銷，因此，我們采用不同的應(yīng)用場(chǎng)景在運(yùn)行算法，比較時(shí)間開銷，相同的任務(wù)數(shù)量，時(shí)間開銷越小，運(yùn)行的效率越高。在表1中，GB-GVNS算法的時(shí)間開銷比同類算法的時(shí)間開銷都小，這是因?yàn)椴捎秒p向變鄰域的方案，增加了搜索空間，找到更加優(yōu)化的任務(wù)分配方式。

表1 不同算法在不同背景下的時(shí)間開銷對(duì)比

5 結(jié)束語(yǔ)

在群智感知的任務(wù)收集方式中，本文針對(duì)三維場(chǎng)景的任務(wù)收集時(shí)間開銷大的現(xiàn)象，提出了GBGVNS算法來(lái)解決數(shù)據(jù)收集低效問(wèn)題，并設(shè)計(jì)基于群智感知機(jī)制的解決方案，實(shí)現(xiàn)任務(wù)總體時(shí)間開銷最小化目標(biāo)，在同類算法中，定位誤差和時(shí)間開銷都取得了較好的實(shí)驗(yàn)結(jié)果。