基于极大化思想的无人机安全避障域识别算法

王家亮 ，董 楷 ,，顾兆军 ，陈 辉 ,，韩 强 ,

（1.中国民航大学计算机科学与技术学院，天津 300300；2.中国民航大学信息安全测评中心，天津 300300）

随着无人机技术发展，四轴飞行器作为典型无人机应用越来越广泛.四轴飞行器在摄影航拍、农业植保、军事侦察、搜索救援、物流运输等领域有着重要应用价值.小型无人机由于具有成本低、飞行灵活等特点，在交通运输领域的桥梁道路检测、辅助交通指挥、交通监控中有着较大的应用优势.无人机自主避障是无人机飞行使用过程中最为基础和关键的技术，因此，无人机自主避障技术成为研究热点.

四轴飞行器主要避障方法可以根据所使用的传感器进行分类，常见用于避障的传感器主要有红外传感器、激光传感器、超声波传感器和视觉传感器等，利用上述传感器获取四轴飞行器与环境之间的距离信息.如林立雄等[1]提出一种利用激光传感器获取位置信息并改进人工势场的局部实时避障算法，解决无人机跟踪目标时避障问题；王梓豪等[2]提出一种基于单目视觉融合多传感器实现无人机集群穿越障碍的技术，在低精度GPS 条件下，利用视觉定位与激光雷达等验证在室外穿越障碍的可行性；Wang 等[3]利用激光传感器测量距离，并采用人工势场的方法完成飞行器室内避障.

基于视觉传感器的避障方法主要是结合图像处理与深度学习等技术处理无人机采集的图像，计算飞行器与障碍物之间的距离远近关系，再进行路径规划以躲避障碍物.如运用图像处理技术中的光流法计算不同障碍物之间的相对远近关系.张小东等[4]提出基于径向光流的单目视觉自主实时障碍物检测方法，解决无人机在室外复杂环境下，传统金字塔LK（Lucas-Kanade）光流法检测障碍物准确性不高、适应性差的问题.付强等[5]提出一种运用稠密光流法，计算视频帧的光流场，将光流信息作为输入量，并设计模糊避障控制器的扑翼飞行器避障方法.Huang 等[6]提出一种利用双目视觉传感器并基于图像特征点提取的障碍物测距方法，优化双目视觉测距，并建立距离估计模型.Lin 等[7]提出基于视觉的四轴飞行器自主导航算法，在飞行器飞行过程中利用光流信息检测障碍物并进行躲避.Dai 等[8]以卷积神经网络（CNN）作为预测机制，利用无人机单目摄像头在室内或者室外未知环境中自主避障.张午阳等[9]基于深度学习，利用目标检测框选出的目标上下边距的长度估计障碍物与无人机之间的距离，再根据距离判断是否进行避障，实现了对人避障.Fu 等[10]提出基于双目视觉的自动避障方法，采用基于深度学习的单次多框检测器（SSD）对图像中的障碍物进行检测，完成扑翼飞行器避障.关震宇等[11]提出一种基于Dubins 路径无人机实时避障算法，在已知障碍物情况下进行路径规划，并能够在未知障碍物信息环境中完成实时避障.李樾等[12]采用传统速度障碍法，建立三维机动障碍的模型，设定系统遇障时的通行法则，将三维环境离散为多个障碍平面，通过障碍平面解决速度障碍法难以处理的三维避障问题.郭行等[13]将动态障碍威胁、控制约束、终端约束等分解处理，设计初始轨迹、规避轨迹、优化轨迹以使最终飞行轨迹具备近似最优特性，并保证动态避障和满足各种约束.Huang 等[14]融合雷达与单目摄像头的数据信息并改进A* 算法，提高了飞行器在农田中的避障能力.Lee等[15]使用Faster R-CNN（faster region-based convolutional neural network）估计障碍物与飞行器之间的距离，解决单目视觉距离信息问题，实现了单目飞行器在室外环境中避障.Ou 等[16]提出一种基于深度学习的四轴飞行器自主避障算法，采用非监督方式从摄像机图像中提取深度信息，并利用Q 学习提高避障能力.张香竹等[17]提出一种利用单目深度估计和目标检测的四轴飞行器避障算法，利用单目深度估计模型与目标检测模型获得图像的深度信息与障碍物位置信息进行避障.Wang等[18]利用深度相机与深度学习技术，通过目标识别算法将识别结果映射到深度图上，提高障碍物识别准确率.

以上文献通过采用雷达、激光测距仪、双目摄像头等传感器在已知或未知的环境中识别并躲避障碍物，相比于使用其他传感器避障，单目视觉传感器具有结构简单、价格较低和应用范围广的优点，本文针对单目四轴飞行器，从求解图像帧中安全避障域角度解决自主避障问题.角点包含图像中重要的结构信息，可有效地作为图像中的特征点或关键点，通过葛立恒（Graham）算法遍历该区域内的角点，识别障碍物区域.因此，本文提出基于角点聚类与Graham 算法的障碍物区域识别方法，采用极大化思想[19]求解安全避障域.在无人机避障飞行时，较为准确地识别安全区域完成自主避障，提高四轴飞行器自主避障能力.

1 四轴飞行器动力模型

四轴飞行器是一种典型的结构简单、可垂直起降的多旋翼无人机，从结构上可以分为“ × ”型和“+”型，如图1 所示.四轴飞行器对角线上旋翼旋转方向相同，另一组对角线上旋翼旋转方向相反，相互抵消飞行时旋翼产生的反扭矩力.四轴飞行器通过电机带动旋翼产生升力进行飞行.本文采用“ × ”型结构四轴飞行器.飞行器机体坐标系原点在飞行器重心，x、y轴分别为四轴飞行器所在水平面的机头方向、重心指向的左侧，用右手定则确定z轴方向.四轴飞行器的飞行姿态分别用俯仰角θ、滚动角ϕ、偏航角ψ描述.其中，θ为机体轴（沿x轴机头方向）与地平面（水平面）之间的夹角，飞行器抬头时，θ为正，否则为负；ϕ为飞行器绕前后轴线（x轴）转动的角度，机体向右滚时为正，反之为负；ψ为实际航向与计划航向之间的夹角，向右偏航为正.本文对无人机采集到的图像进行处理，得到四轴飞行器避障指令，根据指令与无人机动力模型调整俯仰角、滚动角、偏航角，使无人机完成避障.

通过调整4 个电机的速度改变四轴飞行器4 个旋翼产生的升力差，从而改变3 个角度，并控制飞行器起飞、悬停、前进后退和转弯偏航等动作.飞行器合外气动力矩为

式中：l为旋翼中心与飞行器中心的距离；μ为阻力系数；Γr为第r个旋翼产生的升力，r=1，2，3，4；ωr为第r个旋翼转速.

四轴飞行器总升力 Γ、飞行器合外气动力矩τ和旋翼转速ωr的关系如式（2）所示.

式中：λ 为常数.

2 基于角点聚类与Graham 扫描的障碍物识别算法

无人机避障过程第一步为环境感知，即识别障碍物区域，本文设计的基于角点聚类与Graham 扫描的障碍物识别算法流程如图2 所示.首先，运用Shi-Tomasi 算法计算图像帧中的角点；然后，运用LK 光流法计算该角处的光流，根据距离摄像头近处光流大、距离摄像头远处光流小的特点，剔除一些距离较远的角点，再将剔除后的角点进行聚类；最后，用Graham 扫描算法得到每组点的外包轮廓作为障碍物轮廓.

图2 障碍物识别流程Fig.2 Flow chart of obstacle recognition

2.1 LK 光流法

LK 光流算法是一种基于两帧差分的光流估计算法，光流包含着物体的运动信息，反映四轴飞行器与障碍物之间的相对运动.该算法基于3 个假设：1）亮度恒定，即对于相近的两帧图像运动目标的灰度值不变；2）时间连续性，运动目标在帧间对应的像素点位移较小；3）空间一致性，因为相邻点运动相似，所以对于前后两帧图像中相邻点保持相邻.根据LK 光流法可以得到点 (x,y) 处光流为

式中：(Ixi,Iyi,Iti) 为图像第i个像素点在(x,y,t)（点(x,y)在时刻t处）的梯度.

由于无人机避障实时性，应避免在图像帧每个像素点计算光流花费大量时间，对视频流中相近的两帧图像运用Shi-Tomasi 算法与LK 光流法计算图像角点处光流，并判断障碍物的位置和大小.根据距离近的障碍物角点光流较大、距离远的障碍物角点光流较小的性质，设置合适的阈值f，剔除光流小于f的点，即相对于四轴飞行器较远的点.图3 为光流f取不同值时的实验效果.

图3 障碍物角点识别效果Fig.3 Effect of obstacle corner point recognition

当光流值f=1 像素时，算法同时识别出近处与远处障碍物角点，在计算障碍物轮廓时，会导致安全避障域计算错误；当光流值f=4 像素时，近处障碍物的角点被识别出来，而远处障碍物的角点被剔除，效果较好；当光流值f=8 像素时，无法识别出障碍物的角点，四轴飞行器无法避障.因此，根据实验结果，本文选取阈值f=4 像素.

2.2 基于角点聚类与Graham 扫描的障碍物轮廓

识别算法

首先，根据经过剔除后角点间的距离对角点进行聚类，使得距离相近的角点分为一组，然后通过Graham 扫描算法计算每组角点的外包轮廓，计算出的外包轮廓即为障碍物区域轮廓.

角点聚类时，首先计算角点之间的距离并设置阈值d，使得角点之间距离小于d的聚为一类；然后，剔除角点个数小于3 的组.

分组后对每组角点使用Graham 扫描算法计算轮廓，具体步骤如下：

步骤1选取图像帧中最下方的角点作为原点P0.

步骤2计算各个角点相对于P0的幅角，按从小到大的顺序对各个点排序，排序为P0、P1、…、Pn.

步骤3P0、P1入栈，将P0作为前点、P1为当前点、P2为判断点.

步骤4直线L为栈顶的2 个点连线.判断点如果在直线的右侧，执行步骤5；如果在直线上或者直线的左侧，执行步骤6.

步骤5如果栈顶的元素不是障碍物轮廓上的点，则将栈顶元素出栈，执行步骤4.

步骤6把判断点压入栈，执行步骤7.

步骤7如果栈顶元素是Pn，结束扫描；否则，将下个点作判断点，返回步骤4.

在四轴飞行器前避障区域（3 m）时，确定最小安全通过区域在四轴飞行器拍摄图像中的对应像素位置 (x1,y1) 与 (x2,y2)，根据公式d=(x1,y1)2-(x2,y2)2得到参数d的最小值.通过在不同场景的实验选取满足条件的参数d的值，使得不同大小的障碍物（椅子、大小不同的纸箱、垃圾桶、路障等）都得到合理的障碍物轮廓，因此，参数d适用于多个场景.图4为角点之间距离d取不同值时，用Graham 扫描算法识别出障碍物轮廓的实验效果，蓝色框为系统终端识别出的障碍物区域，余图同.

图4 障碍物轮廓识别效果Fig.4 Recognition effect of obstacle contour

当d=180 时，对于较大的障碍物无法计算出完整轮廓；当d=280 时，识别出近处障碍物完整轮廓；当d=400 时，几个障碍物被认作为一个而得到错误的障碍物轮廓.因此，根据实验结果，本文选取阈值d=280.

3 四轴飞行器安全避障域分析

为控制四轴飞行器躲避障碍物，需要在采集的图像帧上计算可通行区域.将不包含障碍物且面积最大的矩形区域认为是最优通行区域.通过分析图像帧计算最优通行区域，然后控制四轴飞行器经过最优通行区域，躲避障碍物.

本文系统结构如图5，算法运行流程如下：

步骤1系统初始化.系统通过WiFi 与四轴飞行器建立连接，接收四轴飞行器拍摄的视频流信息，然后读取图像帧进行处理.

步骤2基于角点聚类与Graham 扫描的障碍物识别算法.首先，运用LK 光流法计算图像帧中角点处光流，并根据光流的特征剔除距离四轴飞行器较远的点，然后对角点聚类，运用Graham 算法找到每组点的外包轮廓.

步骤3基于极大化思想的安全避障域算法.根据障碍物轮廓在已划分的图像帧上标记障碍物矩形，根据极大化思想计算最优通行区域.

步骤4基于安全避障域识别的四轴飞行器控制算法.计算最优通行区域中心点与图像中心点像素偏差，并通过比例-积分（PD）算法得到控制信息，并发送给四轴飞行器，控制四轴飞行器完成避障.

3.1 基于极大化思想的安全避障域算法

采用极大化思想解决如何在包含障碍物的图像帧中计算最优通行区域问题.将图像帧分为3 600 个长、宽像素值分别为16、12 像素的小矩形，并对包含障碍物区域的小矩形进行标记.划分小矩形的数量过多，会导致计算量增加，从而影响避障实时性；反之，则会导致障碍物部分区域未被标记，影响通行区域的计算.为保证实时性，算法首先遍历每行小矩形的下边界，每隔5 像素判断一次该像素是否在障碍物轮廓内，若在障碍物轮廓内，则标记此小矩形，如图6（a）中情形1 所示，小矩形只有下边界有像素点在障碍物轮廓内；再遍历每列小矩形的右边界，判断是否有障碍物穿过，若该矩形未被标记，则每隔5 像素判断一次该矩形右边界上像素是否在障碍物轮廓内，若在障碍物轮廓内，则标记此小矩形，如图6（a）情形2 小矩形只有右边界有像素在障碍物轮廓内；因为每隔5 像素点判断一次，且只判断小矩形右边界与下边界，所以可能出现恰好小矩形包含障碍物，却未标记的情形，如图6（a）情形3 所示.情形3 中未被标记的小矩形一定是障碍物轮廓边缘，而且由于划分的小矩形大小合适，所以并不会因为这部分矩形未被标记而影响计算通行区域，如图6（b）中椅子的边缘并未标记却并不影响四轴飞行器避障.

图6 标记障碍物矩形Fig.6 Marked obstacle rectangle

分析图像帧中可通行区域，通行区域边界有2 种情形：1）通行区域边界部分与障碍物边界重合（图7（a）情形1）；2）通行区域边界与障碍物边界重合或者图像帧边界重合（图7（a）情形2）；当通行区域为图像帧底端时，四轴飞行器距离障碍物还有一段距离，地面可能会被认为是通行区域（图7（a）情形3），此时，距离障碍物较远，四轴飞行器继续向前飞行.对于图像帧中每一个通行区域都可以通过图像中一列小矩形左右移动得到，如图7（b）中以橙色矩形为下端点的一列黄色小矩形，可以通过左右移动得到整个绿色通行区域.左右能移动的最大范围由这一列黄色矩形上每个小矩形距离障碍物或边界的最小值确定.通行区域面积就是这一列黄色小矩形高度与左右能移动最大距离的乘积.所以，为找到最优通行区域，需要枚举出图像帧上所有通行区域，然后找到其中的最大值.

以图像帧中划分的每个矩形分别作为端点，计算不同高度的通行区域面积，并找到最大值作为包含该点处的最大通行区域，遍历整个图像帧中所有小矩形，得到最大通行区域.

首先，对图像帧建立如图7（b）所示坐标系；然后，计算图像帧中没有被标记的任意小矩形(w,h)左、右侧到标记矩形或边界的最远距离，并分别记为L[w,h]和R[w,h] ；最后，递归法算出每个小矩形处的最大通行区域面积.

左侧最远距离Dl[w,h] 为当前左侧最远距离L[w,h]与这一列小矩形的下一个小矩形左侧最远距离Dl[w,h-1] 的较小值，即

右侧最远距离Dr[w,h] 为当前右侧最远距离R[w,h]与这一列小矩形的下一个小矩形右侧最远距离Dr[w,h-1] 的较小值，即

通行区域高度H[w,h] 为此列小矩形的个数：

通行区域面积A[w,h] 为通行区域高度与通行区域左右最远距离和的乘积：

根据得到的最大通行区域左上角和右下角坐标，画出通行区域矩形和通行区域中心点（如图8 所示），对应图中的绿色框和绿色点，余图同.

图8 通行区域分析结果Fig.8 Passing domain analysis result

安全避障域识别算法伪代码如下：

3.2 基于安全避障域识别的四轴飞行器控制算法

在系统处理完图像帧找到通行区域后，采用PD 算法控制无人机飞行躲避障碍物.PD 控制是比例积分微分（PID）控制的一种，是线性控制方法[20].

首先，确定是否有四轴飞行器可通行区域，如果通行区域面积小于四轴飞行器可通过最小面积，则向四轴飞行器发送降落指令；如果有可通过的区域，则分别计算最优通行区域中心点（绿色中心点）与当前图像帧的中心点（黑色中心点）的水平像素偏差d1与垂直像素偏差d2，如图9 所示.根据PD 算法，分别以d1、d2作为偏差值，得到水平控制量u1(t)和垂直控制量u2(t)，再将u1(t)与u2(t)作为飞控算法输入，控制无人机完成避障飞行.

图9 PD 控制避障示意Fig.9 Obstacle avoidance by PD control

4 实验与结果分析

4.1 实验平台

采用深圳睿炽科技的Tello 四轴飞行器作为实验平台，该飞行器搭载大疆公司的飞控技术和英特尔Movidius 芯片，并配有500 万像素的摄像头.电脑终端配置为Intel（R）Core（TM）i5-7300HQ 处理器，显卡为NVIDIA GeForce 1050Ti，网卡为Intel Dual Band Wireless-AC 3168.

4.2 实验结果分析

为验证算法是否有效，用纸箱、椅子和垃圾桶作为障碍物，通过在室内与室外布置的3 个实验场景验证算法的避障效果，如图10 所示.实验1 为多组障碍物障碍实验，实验2、3 为复杂程度不同的复杂障碍物避障实验.

图10 实验场景Fig.10 Experimental scenes

设定四轴飞行器的前进速度为0.42 m/s，单目相机采集频率为30 帧/s，算法执行周期为1 s.实验场景尺寸为：箱子53 cm × 32 cm × 56 cm、路障65 cm ×27 cm × 27 cm、书包45 cm × 30 cm × 12 cm、椅子85 cm × 50 cm × 43 cm.

4.2.1 多组障碍物避障实验（实验1）

按照图10（a）所示场景进行避障测试，四轴飞行器起飞后向前飞行，飞行过程中在t11、t12、t13时刻依次躲避3 组障碍物，实验结果如图11 所示.

图11 躲避多组障碍物实验（实验1）Fig.11 Experiment of avoiding multiple groups of obstacles (experiment 1)

对四轴飞行器飞行过程中记录的俯仰角和滚动角数据信息进行分析，如图12 所示.实验过程中，系统终端通过处理四轴飞行器所拍摄的图像得到控制指令，再将控制指令发送给四轴飞行器.四轴飞行器在俯仰角 θ ＜0 的范围内波动（θ ＜0 表示四轴飞行器向前飞行）.在第0～16 帧，滚动角 ϕ=0，此时，四轴飞行器距离障碍物较远，所以，滚动角并未改变；在第17～40 帧，ϕ ＜0，表示四轴飞行器向左移动躲避第1 组障碍物；在第41～57 帧，ϕ ＞0，表示四轴飞行器向右飞行躲避第2 组障碍物；第58～71 帧内，四轴飞行器 ϕ ＜0，表示四轴飞行器向左飞行躲避第3 组障碍物.由于起飞时四轴飞行器距离第1 组障碍物较远，所以滚动角变化范围较小.3 组障碍物之间距离较小，所以，滚动角变化范围较大.

图12 四轴飞行器数据结果（实验1）Fig.12 Quad-rotor helicopter data results (experiment 1)

4.2.2 复杂障碍物避障实验（实验2、3）

按照图11（b）、（c）所示场景进行复杂障碍物避障实验，结果分别如图13、14 所示.

图13 复杂障碍物避障实验（实验2）Fig.13 Experiment of avoiding complex obstacles (experiment 2)

图14 复杂障碍物避障实验（实验3）Fig.14 Experiment of avoiding complex obstacles (experiment 3)

为检验本文算法的避障准确性和实时性，将安全避障域面积与计算时间作为评价指标，与改进的基于贝叶斯估计与区域划分遍历[21]的避障路径规划算法（BR 算法）进行对比分析.本文算法与BR 算法计算时间对比如图15 所示.在处理每帧图像平均用时上，前者0.17 s，后者0.13 s 左右，本文算法虽然处理图像时间增加，但仍满足无人机避障实时性要求.将通行区域所包含像素个数作为通行区域面积评价指标，2 种算法对比结果如图16 所示.在第15～58 帧、第64～168 帧，本文算法求解出的避障域比BR 算法更准确；在其余帧，2 种算法求解避障域面积相同，则只显示本文算法面积.在障碍物识别时，BR 算法使用贝叶斯估计与背景差分法，本文算法采用基于角点聚类与Graham 扫描的障碍物识别算法；在计算安全避障域时，BR 算法虽然找到无人机安全通行区域，但并不一定是最优安全避障域.本文算法基于极大化思想，在计算最优安全避障域的同时，兼顾准确性和实时性.

图15 处理时间对比Fig.15 Comparison of processing time

图16 通行区域面积对比Fig.16 Comparison of passing domain area

5 总结

本文针对单目四轴飞行器自主避障中障碍物识别与计算安全通行区域问题，分别提出基于角点聚类与Graham 扫描的障碍物识别算法和基于极大化思想的安全避障域算法.在Tello 四轴飞行器上对安全避障域识别算法进行测试实验，结果表明，算法能够合理识别障碍物并使四轴飞行器完成避障，同时算法满足准确性与实时性要求.下一步将使用机载计算机平台或融合其他传感器进行相关研究.