0 引言

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

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

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

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

1.1 三維重建圖像要求

    無人機序列影像的三維重建質量主要受到以下因素影響：

    (1)重疊度：無人機所拍攝的序列影像需要具有一定的重疊區(qū)，即具有一定的旁向與縱向重疊度。一般來說，序列影像的重疊度越高，三維重建的質量越高。

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

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

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

    序列影像滿足重疊度要求后，航線規(guī)劃過程中最需要解決的問題是如何最大限度地降低功耗。無人機航線距離越長，任務所需的時間越長，消耗的能量也會越多。同時，文獻[8]提出在相同任務航線距離情況下，轉彎次數越多，所耗費的時間將會越長，能量越多。其原因為無人機轉彎時需要經過減速、變向、加速等過程，相較于直線飛行會花費更多的時間與能量。

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

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

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

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

    任務區(qū)域為多邊形P₁P₂P₃P₄P₅P₆。為了便于規(guī)劃全覆蓋掃描航線，建立坐標系XOY，設定坐標系X軸為任務區(qū)域多邊形某一邊(圖2中邊P₄P₅)，并將整個任務區(qū)域多邊形置于第一象限內。記任務區(qū)域多邊形的頂點P_i的坐標為(x_i，y_i)，其中X方向與Y方向坐標的最大最小值分別記為(x_min，x_max，y_min，y_max)，任務區(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軸方向為無人機飛行的起始航向，無人機掃描航線的航線間距d由旁向重疊度v與無人機圖像視場寬度w確定，計算方式具體如下式：

    以無人機掃描航線的航線間距d作為光柵法的光柵間距，以垂直于無人機起始航向的方向為劃分方向，從距離任務區(qū)域多邊形底邊w/2處起等分坐標系第一象限。其中，任務區(qū)域多邊形覆蓋的光柵帶為有效光柵帶，其余為無效光柵帶。掃描航線的匝數n取決于航線間距d、無人機圖像視場寬w以及掃描方向長度l_s(l_s=y_max-y_min)：

2.2 最佳掃描方向

    由于無人機在轉彎時飛行速度會減慢，并耗費大量的能量，減少轉彎次數能夠有效減少飛行時間，增強序列圖像之間的時間連續(xù)性并降低飛行功耗。由式(2)可知，掃描航線匝數取決于掃描方向l_s的長度，因為航線間距d由圖像與重疊度固定確定。因此，最小化掃描方向l_s的長度，可以使無人機掃描航線的轉彎次數最少化，飛行時間最少，功耗達到最小。

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

    如圖3(a)所示，分別計算任務區(qū)域多邊形各邊到最遠頂點的距離L_i，i∈(1，2，…，6)。其中，選取距離最短的方向作為最佳掃描方向，因為此方向所需要轉彎的次數最少，能夠最大限度減小無人機功耗，提高任務效率。選取最佳掃描方向，按照2.1中光柵法對任務區(qū)域進行掃描航線規(guī)劃，結果如圖3(b)所示。按照最佳掃描方向規(guī)劃航線得出的最佳覆蓋航線的匝數比2.1節(jié)中規(guī)劃的航線匝數少了3匝，轉彎數減少，說明按照最佳掃描方向規(guī)劃航線能夠有效減少無人機的功耗。

3 實驗驗證

    本文基于Gazebo仿真平臺設計實驗驗證本文算法的可行性。Gazebo仿真平臺提供了多種無人機模型，如AscTec Hummingbird、AscTec Pelican、AscTec Firefly等。該平臺同時附帶多類型的模擬傳感器，如IMU、測距傳感器、視覺傳感器等，可模擬安裝在無人機模型上。為證明本文算法所得到的航線較傳統算法的規(guī)劃航線更加有效，統計對比了兩種算法所得航線的轉彎次數、航程距離等參數。

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

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

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

    仿真結果顯示，當航向角為30°時，航線的轉彎次數、與航程距離、飛行時間達到最優(yōu)。

    (2)本文算法

    對比傳統掃描式航線規(guī)劃算法與本文算法的仿真實驗結果，本文算法能夠得出轉彎次數最少、航程距離更短、飛行時間更少的航線。在確保序列影像重疊度的情況下，無人機按照本文算法得到的航線飛行時的飛行時間更短、功耗更小，所獲得的序列影像時間連續(xù)性更強。

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

4 結束語

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

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

參考文獻

[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] 于駟男，周銳，夏潔，等.無人機協同搜索區(qū)域分割與覆蓋[J].北京航空航天大學學報，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ū)域植保無人機航線規(guī)劃算法[J].農業(yè)機械學報，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] 李宏超，黃亞樓，闕嘉嵐，等.基于四叉樹環(huán)境模型的輪式移動機器人平滑路徑生成方法[J].機器人，2001，23(5)：426-430.

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

作者信息:

吳宇豪，安籽鵬

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