0 引言

    隨著無(wú)人機(jī)技術(shù)的發(fā)展,，無(wú)人機(jī)被應(yīng)用到越來(lái)越多的領(lǐng)域，例如搜索或探索^[1],、震后災(zāi)害分析^[2]以及森林,、礦山、空氣質(zhì)量監(jiān)測(cè)^[3]等活動(dòng)中,。利用無(wú)人機(jī)拍攝地面影像進(jìn)行三維重建是一種典型的應(yīng)用,。為了完整重建出任務(wù)區(qū)域的三維模型,，首先要解決的問(wèn)題是合理規(guī)劃出覆蓋任務(wù)區(qū)域的航線。該問(wèn)題屬于覆蓋路徑規(guī)劃問(wèn)題的范疇,。覆蓋路徑規(guī)劃問(wèn)題（coverage path planning）的目的是找到一條路徑,，以完全遍歷任務(wù)區(qū)域。 

    目前,，國(guó)內(nèi)外學(xué)者對(duì)覆蓋路徑規(guī)劃問(wèn)題進(jìn)行了大量的研究,，針對(duì)不同的應(yīng)用場(chǎng)景提出了不同的解決方案，主要的應(yīng)用場(chǎng)景有機(jī)器人軍事偵察^[4],、無(wú)人機(jī)自動(dòng)搜索^[5]植保無(wú)人機(jī)農(nóng)田灌溉^[6]等,。其中，各應(yīng)用中的覆蓋路徑規(guī)劃算法大致可分為單元分解法與柵格法兩種類(lèi)型,。單元分解法中的最為經(jīng)典的算法是LATOMBE J C在1991年提出的Trapezoidal分解法^[7],，對(duì)整個(gè)任務(wù)區(qū)域進(jìn)行分割，形成多個(gè)子區(qū)域,，分別進(jìn)行路徑規(guī)劃,。HUANG W H等人^[8]對(duì)精確單元法提出了改進(jìn)，提出了“Minimal Sum of Altitude(MSA)”算法,。其主要思想是使得覆蓋路徑中的轉(zhuǎn)彎次數(shù)達(dá)到最小,，以減少在轉(zhuǎn)彎時(shí)消耗的能量。柵格法最早由ELFES A和MORAVEC H P提出^[9-10],，是將覆蓋區(qū)域均勻劃分的方法,，目標(biāo)是尋找一條或多條遍歷有效柵格的覆蓋路徑。其中比較有代表性的算法有基于生物激勵(lì)神經(jīng)網(wǎng)絡(luò)的柵格法^[11],、基于生成樹(shù)的柵格法^[12]以及基于四叉樹(shù)的方法^[13],。楊麗春^[14]基于改進(jìn)人工勢(shì)場(chǎng)法實(shí)現(xiàn)了無(wú)人機(jī)在線航線規(guī)劃。

    針對(duì)無(wú)人機(jī)序列影像三維重建的特定要求,，本文主要在不考慮氣象因素的條件下研究了凸多邊形任務(wù)區(qū)域的無(wú)人機(jī)覆蓋航線規(guī)劃問(wèn)題,。融合柵格法的等分思想與掃描航線的特點(diǎn)提出了基于光柵法的無(wú)人機(jī)掃描航線規(guī)劃方法，并通過(guò)計(jì)算最佳掃描方向,，使得轉(zhuǎn)彎次數(shù)最少化且功耗最小,。

1 面向圖像三維重建的無(wú)人機(jī)航線規(guī)劃問(wèn)題

1.1 三維重建圖像要求

    無(wú)人機(jī)序列影像的三維重建質(zhì)量主要受到以下因素影響：

    (1)重疊度：無(wú)人機(jī)所拍攝的序列影像需要具有一定的重疊區(qū)，即具有一定的旁向與縱向重疊度,。一般來(lái)說(shuō),，序列影像的重疊度越高，三維重建的質(zhì)量越高,。

    (2)時(shí)間連續(xù)性：由于環(huán)境因素會(huì)隨時(shí)間產(chǎn)生變化,，從而導(dǎo)致任務(wù)區(qū)域的表面特征發(fā)生改變。因此,，為了獲得更好的重建結(jié)果,，需在盡可能短的時(shí)間內(nèi)完成序列影像的獲取,。

    為了對(duì)任務(wù)范圍進(jìn)行完整的三維重建，需要規(guī)劃設(shè)計(jì)一條或多條無(wú)人機(jī)全覆蓋航線并且所拍攝的序列影像盡可能滿(mǎn)足上述條件,。

1.2 任務(wù)航線規(guī)劃方式

    序列影像滿(mǎn)足重疊度要求后，航線規(guī)劃過(guò)程中最需要解決的問(wèn)題是如何最大限度地降低功耗,。無(wú)人機(jī)航線距離越長(zhǎng),，任務(wù)所需的時(shí)間越長(zhǎng)，消耗的能量也會(huì)越多,。同時(shí),，文獻(xiàn)[8]提出在相同任務(wù)航線距離情況下，轉(zhuǎn)彎次數(shù)越多,，所耗費(fèi)的時(shí)間將會(huì)越長(zhǎng),，能量越多。其原因?yàn)闊o(wú)人機(jī)轉(zhuǎn)彎時(shí)需要經(jīng)過(guò)減速,、變向,、加速等過(guò)程，相較于直線飛行會(huì)花費(fèi)更多的時(shí)間與能量,。

    掃描式航線是一種解決全覆蓋問(wèn)題的典型覆蓋方法,，具有航程較短、轉(zhuǎn)彎次數(shù)少等優(yōu)點(diǎn),。其主要飛行方式如圖1所示,，無(wú)人機(jī)起飛之后，按一定的航向沿直線飛行,，到達(dá)轉(zhuǎn)向點(diǎn)后轉(zhuǎn)向,，隨后按與之前航向平行但相反的方向飛行至下一轉(zhuǎn)向點(diǎn)，依次循環(huán)覆蓋任務(wù)區(qū)域,。飛行過(guò)程中,，設(shè)定相機(jī)方向?yàn)樨Q直向下，成像角度在整個(gè)飛行過(guò)程中不變,。每一張無(wú)人機(jī)圖像所拍攝的區(qū)域?qū)嶋H寬為w,，長(zhǎng)為l。相鄰兩張相片之間的旁向重疊度為v,，縱向重疊度為h,。

2 覆蓋凸多邊形任務(wù)區(qū)域的掃描航線

2.1 基于光柵法的掃描航線規(guī)劃方法

    無(wú)人機(jī)實(shí)際作業(yè)的過(guò)程中，任務(wù)區(qū)域往往是不規(guī)則的多邊形,，其中凸多邊形區(qū)域是較為常見(jiàn)的一種,。針對(duì)凸多邊形任務(wù)區(qū)域，重點(diǎn)考慮序列圖像的重疊度要求,，本文提出融合柵格法等分思想與掃描航線特點(diǎn)的光柵法,，如圖2所示,，其規(guī)劃過(guò)程如下。

    任務(wù)區(qū)域?yàn)槎噙呅蜳₁P₂P₃P₄P₅P₆,。為了便于規(guī)劃全覆蓋掃描航線,，建立坐標(biāo)系XOY，設(shè)定坐標(biāo)系X軸為任務(wù)區(qū)域多邊形某一邊(圖2中邊P₄P₅),，并將整個(gè)任務(wù)區(qū)域多邊形置于第一象限內(nèi),。記任務(wù)區(qū)域多邊形的頂點(diǎn)P_i的坐標(biāo)為(x_i，y_i),，其中X方向與Y方向坐標(biāo)的最大最小值分別記為(x_min,，x_max，y_min,，y_max),，任務(wù)區(qū)域的邊界P_iP_i+1可表示為(y-y_i+1)(x_i-x_i+1)=(x-x_i+1)(y_i-y_i+1)，i=(1,，2,，…，6),。以X軸方向?yàn)闊o(wú)人機(jī)飛行的起始航向,，無(wú)人機(jī)掃描航線的航線間距d由旁向重疊度v與無(wú)人機(jī)圖像視場(chǎng)寬度w確定，計(jì)算方式具體如下式：

    以無(wú)人機(jī)掃描航線的航線間距d作為光柵法的光柵間距,，以垂直于無(wú)人機(jī)起始航向的方向?yàn)閯澐址较?，從距離任務(wù)區(qū)域多邊形底邊w/2處起等分坐標(biāo)系第一象限。其中,，任務(wù)區(qū)域多邊形覆蓋的光柵帶為有效光柵帶,，其余為無(wú)效光柵帶。掃描航線的匝數(shù)n取決于航線間距d,、無(wú)人機(jī)圖像視場(chǎng)寬w以及掃描方向長(zhǎng)度l_s(l_s=y_max-y_min)：

2.2 最佳掃描方向

    由于無(wú)人機(jī)在轉(zhuǎn)彎時(shí)飛行速度會(huì)減慢,，并耗費(fèi)大量的能量，減少轉(zhuǎn)彎次數(shù)能夠有效減少飛行時(shí)間,，增強(qiáng)序列圖像之間的時(shí)間連續(xù)性并降低飛行功耗,。由式(2)可知，掃描航線匝數(shù)取決于掃描方向l_s的長(zhǎng)度,，因?yàn)楹骄€間距d由圖像與重疊度固定確定,。因此，最小化掃描方向l_s的長(zhǎng)度,，可以使無(wú)人機(jī)掃描航線的轉(zhuǎn)彎次數(shù)最少化,，飛行時(shí)間最少，功耗達(dá)到最小。

    傳統(tǒng)的航線規(guī)劃算法在確立最佳掃描方向時(shí)采用枚舉的方式進(jìn)行,，設(shè)定計(jì)算步長(zhǎng)r°,，航向角α的取值為(0°，r°,2r°,，…,，nr°，180°),，取其中匝數(shù)最少的作為最優(yōu)航線,。該方法作業(yè)效率低，且精度與步長(zhǎng)r°的取值有關(guān),。為了確定最佳掃描方向獲得最小化的航線匝數(shù)，本文提出垂線法以確立最佳掃描方向,，如圖3所示,。

    如圖3(a)所示，分別計(jì)算任務(wù)區(qū)域多邊形各邊到最遠(yuǎn)頂點(diǎn)的距離L_i,，i∈(1,，2，…,，6),。其中，選取距離最短的方向作為最佳掃描方向,，因?yàn)榇朔较蛩枰D(zhuǎn)彎的次數(shù)最少,，能夠最大限度減小無(wú)人機(jī)功耗，提高任務(wù)效率,。選取最佳掃描方向,，按照2.1中光柵法對(duì)任務(wù)區(qū)域進(jìn)行掃描航線規(guī)劃，結(jié)果如圖3(b)所示,。按照最佳掃描方向規(guī)劃航線得出的最佳覆蓋航線的匝數(shù)比2.1節(jié)中規(guī)劃的航線匝數(shù)少了3匝,，轉(zhuǎn)彎數(shù)減少，說(shuō)明按照最佳掃描方向規(guī)劃航線能夠有效減少無(wú)人機(jī)的功耗,。

3 實(shí)驗(yàn)驗(yàn)證

    本文基于Gazebo仿真平臺(tái)設(shè)計(jì)實(shí)驗(yàn)驗(yàn)證本文算法的可行性,。Gazebo仿真平臺(tái)提供了多種無(wú)人機(jī)模型，如AscTec Hummingbird,、AscTec Pelican,、AscTec Firefly等。該平臺(tái)同時(shí)附帶多類(lèi)型的模擬傳感器,，如IMU,、測(cè)距傳感器、視覺(jué)傳感器等，可模擬安裝在無(wú)人機(jī)模型上,。為證明本文算法所得到的航線較傳統(tǒng)算法的規(guī)劃航線更加有效,，統(tǒng)計(jì)對(duì)比了兩種算法所得航線的轉(zhuǎn)彎次數(shù)、航程距離等參數(shù),。

    實(shí)驗(yàn)過(guò)程中,，構(gòu)建仿真環(huán)境，如圖4所示,，依照DEM構(gòu)建基本地形,，并添加樹(shù)木、房子等地物,。仿真無(wú)人機(jī)采用AscTec Firefly六旋翼無(wú)人機(jī),，并攜帶視覺(jué)傳感器。設(shè)定無(wú)人機(jī)航高為50 m,，視場(chǎng)寬度w=170 m,，長(zhǎng)度l=255 m，旁向重疊度h=80%,，縱向重疊度v=70%,。按順序選取任務(wù)點(diǎn){P₁，P₂,，P₃,，P₄，P₅,，P₆},，連接各點(diǎn)構(gòu)成任務(wù)區(qū)域，如圖5(a)所示,。

    (1)傳統(tǒng)掃描式航線規(guī)劃算法

按照傳統(tǒng)掃描航線的規(guī)劃方式,，設(shè)定航向角α的計(jì)算步長(zhǎng)為10°，取值范圍為(0°,，10°,，20°，…,，170°,，180°)。統(tǒng)計(jì)不同航向角時(shí),，航線的匝數(shù)與航程距離,，部分統(tǒng)計(jì)結(jié)果如表1所示。

    仿真結(jié)果顯示,，當(dāng)航向角為30°時(shí),，航線的轉(zhuǎn)彎次數(shù)、與航程距離、飛行時(shí)間達(dá)到最優(yōu),。

    (2)本文算法

    對(duì)比傳統(tǒng)掃描式航線規(guī)劃算法與本文算法的仿真實(shí)驗(yàn)結(jié)果,，本文算法能夠得出轉(zhuǎn)彎次數(shù)最少、航程距離更短,、飛行時(shí)間更少的航線,。在確保序列影像重疊度的情況下，無(wú)人機(jī)按照本文算法得到的航線飛行時(shí)的飛行時(shí)間更短,、功耗更小,，所獲得的序列影像時(shí)間連續(xù)性更強(qiáng)。

    借助開(kāi)源三維重建庫(kù)openMVG(open Multiple View Geometry)對(duì)所拍攝的無(wú)人機(jī)序列影像進(jìn)行三維重建,，分別生成稀疏點(diǎn)云,、稠密點(diǎn)云以及貼合紋理的三維模型，如圖6所示,。通過(guò)觀察模型,，發(fā)現(xiàn)整個(gè)任務(wù)區(qū)域得到了完整的三維重建，貼合紋理的三維模型能夠展現(xiàn)任務(wù)區(qū)域的表面特征,，證明本文算法規(guī)劃的掃描航線能夠用于圖像三維重建。

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

    新形勢(shì)下,，面向無(wú)人機(jī)序列影像三維重建的覆蓋航線規(guī)劃問(wèn)題尤為重要,。本文針對(duì)凸多邊形任務(wù)區(qū)域，提出了無(wú)風(fēng)環(huán)境下面向無(wú)人機(jī)序列影像三維重建的覆蓋航線規(guī)劃算法,。該算法的主要?jiǎng)?chuàng)新內(nèi)容有兩個(gè)方面：(1)結(jié)合柵格等分思想,，提出基于光柵法的掃描航線規(guī)劃方法，確保了序列影像之間的重疊度要求,；(2)提出垂線法用于尋找最佳掃描方向,，確保了無(wú)人機(jī)序列影像之間具有較好的時(shí)間連續(xù)性，同時(shí)使得無(wú)人機(jī)的飛行功耗更小,。

    通過(guò)搭建仿真環(huán)境,，實(shí)驗(yàn)驗(yàn)證了本文算法得出的掃描航線能夠完全覆蓋任務(wù)區(qū)域，得到的航線要優(yōu)于傳統(tǒng)航線,，所拍攝的序列影像滿(mǎn)足整個(gè)任務(wù)區(qū)域三維重建的要求,。為系統(tǒng)研究實(shí)際環(huán)境下面向圖像三維重建的無(wú)人機(jī)航線規(guī)劃問(wèn)題，今后的工作將進(jìn)一步考慮地形,、風(fēng)速,、風(fēng)向、單架次無(wú)人機(jī)最大飛行距離等因素對(duì)航線規(guī)劃問(wèn)題的影響,。

參考文獻(xiàn)

[1] BALIYARASIMHUNI S,，SOUSA J B，PEREIRA F L.UAVs and AUVs coordination for ocean exploration[C].Oceans.IEEE，2009.

[2] XU Z,，YANG J,，PENG C，et al.Development of an UAS for post-earthquake disaster surveying and its application in Ms7.0 Lushan Earthquake,，Sichuan,，China[J].Computers & Geosciences，2014,，68：22-30.

[3] WATTS A C,，AMBROSIA V G，HINKLEY E A.Unmanned aircraft systems in remote sensing and scientific research：classification and considerations of use[J].Remote Sensing,，2012,，4(6)：1671-1692.

[4] 于駟男，周銳,，夏潔,，等.無(wú)人機(jī)協(xié)同搜索區(qū)域分割與覆蓋[J].北京航空航天大學(xué)學(xué)報(bào)，2015,，41(1)：167-173.

[5] WAGNER A,，ARKIN R C.Multi-robot communication-sensitive reconnaissance[C].IEEE International Conference on Robotics and Automation，2004.Proceedings.ICRA.IEEE,，2003,，5：4674-4681.

[6] 徐博，陳立平,，徐旻,，等.多作業(yè)區(qū)域植保無(wú)人機(jī)航線規(guī)劃算法[J].農(nóng)業(yè)機(jī)械學(xué)報(bào)，2017,，48(2)：75-81.

[7] LATOMBE J C.Exact cell decomposition[J].The Springer International Series in Engineering and Computer Science,，1991，124：200-247.

[8] HUANG W H.Optimal line-sweep-based decompositions for coverage algorithms[C].IEEE International Conference on Robotics & Automation.IEEE,，2001.

[9] ELFES A.Sonar-based real-world mapping and navigation[J].IEEE Journal on Robotics & Automation,，1987，3(3)：249-265.

[10] MORAVEC H P,，ELFES A.High resolution maps from angle sonar[C].IEEE International Conference on Robotics and Automation,，1985：116-121.

[11] HODGKIN A L，HUXLEY A F.A quantitative description of membrane current and its application to conduction and excitation in nerve[J].The Journal of Physiology,，1952,，117(4)：500-544.

[12] GABRIELY Y，RIMON E.Competitive on-line coverage of grid environments by a mobile robot[J].Computational Geometry：Theory and Applications,，2003,，24(3)：197-224.

[13] 李宏超,，黃亞樓，闕嘉嵐,，等.基于四叉樹(shù)環(huán)境模型的輪式移動(dòng)機(jī)器人平滑路徑生成方法[J].機(jī)器人,，2001，23(5)：426-430.

[14] 楊麗春,，顧穎彥,，白宇.基于改進(jìn)人工勢(shì)場(chǎng)法的無(wú)人機(jī)在線航路規(guī)劃算法[J].電子技術(shù)應(yīng)用，2018,，44(4)：5-9.

作者信息:

吳宇豪,，安籽鵬

（信息工程大學(xué) 地理空間信息學(xué)院，河南 鄭州450000）