基于分离轴算法的机场场面飞行器冲突告警研究_吴寿英.pdf

第 40 卷第 3 期计算机应用与软件Vol.40 No 32023 年 3 月Computer Applications and SoftwareMar 2023基于分离轴算法的机场场面飞行器冲突告警研究吴寿英1李炜2*1(四川大学视觉合成图形图像技术国防重点学科实验室四川 成都 610065)2(四川大学空天科学与工程学院四川 成都 610065)收稿日期:2020 07 20。国家重点研发计划项目(2016YFC0802209-2);四川省重点研发项目(2020YFG0134)。吴寿英，硕士生，主研领域:计算机视觉与图像处理，机场场面目标监视。李炜，副研究员。摘要为降低机场场面冲突事件的发生，设计一种机场场面飞机冲突告警系统。机场场面冲突检测过程分为两层:粗略检测层和精细检测层。粗略检测使用类包围球简化模型，精细检测划分飞机模型为 5 个凸多边形。为了提高算法检测速度，提出一种基于最近点的分离轴碰撞检测算法。此外，为降低虚警率，对顶点进行弧形检测。实验结果表明，该算法可有效降低程序时间复杂度，加快检测速度。此设计方案为实现低成本机场场面的冲突事件监控提供了重要参考。关键词机场场面冲突碰撞检测冲突告警中图分类号TP391 9文献标志码ADOI:10 3969/j issn 1000-386x 2023 03 012ESEACH ON AICAFT COLLISION WANING AT AIPOTSCENE BASED ON SEPAATION AXIS ALGOITHMWu Shouying1Li Wei2*1(Visual Synthetic Graphic Image Technology National Defense Key Discipline Laboratory，Sichuan University，Chengdu 610065，Sichuan，China)2(School of Aeronautics and Astronautics，Sichuan University，Chengdu 610065，Sichuan，China)AbstractIn order to reduce the occurrence of conflicts at the airport scene，an aircraft conflict warning system at theairport scene is designed The collision detection process was divided into two layers:the rough detection layer and thefine detection layer The rough detection used a bounding sphere simplified model，and the fine detection divided theaircraft model into 5 convex polygons In order to improve the detection speed of the algorithm，a separation axis collisiondetection algorithm based on the nearest point was proposed Furthermore，in order to reduce the false alarm rate，arcdetection was performed on the vertices of the polygon Experimental results show that this algorithm can effectivelyreduce the time complexity of the program and improve the detection speed The proposed method provides an importantreference for the scene monitoring at the scene of low-cost airportsKeywordsAirport scene conflictCollision detectionConflict alert0引言由于目前机场场面缺少完备的冲突事件检测和告警系统，导致机坪航空器之间的擦碰事件时有发生，造成大量人员航班延误。因为机坪人手不足，地勤和航空器操作员存在视线盲区，导致机坪繁忙阶段特别容易发生航空器之间的擦碰问题。为有效监控与管理场面飞机的安全运行，减少机场地面交通擦碰事件的发生，国内外航空界对此做了较多的研究，提出了一些理论与方法1 2。但总体上都是从硬件设备以及策略方面降低机场飞机之间的碰撞问题。减少航空器间的冲突及碰撞是机场安全运行的重要保证，由于航空器后机会受到前机尾流的影响，所以在地面滑行时保证航空器间的安全距离是有效避免冲突及碰撞的手段，叶右军3 研究了基于航空器间安全距离的碰撞模型，以第 3 期吴寿英，等:基于分离轴算法的机场场面飞行器冲突告警研究73降低航空器之间的碰撞风险。另外，潘卫军等4 分析了机场冲突热点的时空分布特征，通过对机场建模构建航空器的滑行和避让机制，提出基于机场冲突热点时空分布特征的航空器地面滑行路径优化模型，从而降低场面飞机的冲突或碰撞事件。葛亚威等5 利用A-SMGC 系统监视模块与路由规划模块的结合，构建冲突探测系统框架来减少冲突碰撞事件以及提升机场运行安全，类似的研究还有许多6 8。上述这些理论方法虽然在一定程度上对场面航空器冲突预警，但是其虚警率高。牟奇锋等9 通过航空器外形及关键尺寸设计类碰撞盒的可变多边形还原航空器，且考虑航空器在运动过程中对地面空间占用的影响，将其机头保护层沿运动方向前推至一个制动距离，从而降低虚警率。杜金峰等10 使用基于北斗二代定位数据的机场场面短期冲突探测算法，可以根据飞机不同运动状态设定最小安全距离且判定冲突类型从而减少虚警率。机场场面目标危险接近与告警实质上是其在告警区域内的碰撞检测问题。根据监控飞机的地理位置坐标和型号可重建飞机模型，进而获得该飞机模型在 2D场面下的区域坐标范围，从而可以转化为二维场景下的多边形碰撞检测问题。本文设计基于最近点的分离轴碰撞检测算法，重建飞机目标模型，并对模型顶点进行弧形检测，构建模型监控告警区。通过计算机模拟仿真场面飞机危险接近场景，仿真实验结果表明，本文算法可有效降低程序时间复杂度加快冲突检测速度，同时弧形处理可降低虚警率。1重建飞机模型由于飞机是多边形，且常见的载人客机模型轮廓都差不多，所以围绕航空器的外围轮廓，根据其外部形状特征，通过模型关键尺寸即可构建飞机模型基层区域。飞机模型可以用 17 条边包围，如图 1 所示，假设已知的坐标点为飞机头顶点 A0(x0，y0)，则沿顺时针分别将各个顶点坐标标记为 A1，A2，A16。图 1飞机模型编号过顶点 A0作一条中线平分模型，直线与 x 轴夹角为飞机的朝向。设飞机关键尺寸为 hi、wi，当 i 7时，分别为 Ai到 A0顶点的 /2 方向和 方向的两个分量，如图 2 所示。当 i7 时，分别为 +/2 方向和 方向的两个分量，如图 3 所示。图 2飞机模型顶点坐标计算(i 7)图 3飞机模型顶点坐标计算(i7)当 i 7 情况下，飞机朝向和关键尺寸已知，由图 2可知 Ai(xi，yi)顶点的坐标为:xi=x0 myi=y0n(1)式中:m 与 n 分别为 Ai到 A0顶点之间 x 轴和 y 轴投影的距离，根据几何原理可得:m=icos hisinn=isin+hicos(2)则有:xi=x0+hisin wicosyi=y0 hicos wisin(3)同理，当 i7 时，则有:xi=x0 hisin wicosyi=y0+hicos wisin(4)机场场面冲突检测就是防止碰撞，所以要制定安全距离，进行危险接近触发告警机制。危险接近告警就是模拟告警区，对于特定的安全距离阈值可以构造飞机告警区，从而构造飞机之间的安全距离。飞机模型是一个非凸多边形，如果直接计算航空器之间的碰撞关系则会非常复杂，所以把非凸多边形划分为多个凸多边形是自然会想到的解决方法。如图 1 所示，飞机模型被划分为 6 个凸多边形，其中有效多边形为 5个(a e)。接下来是飞机模型安全区域的碰撞检测，本文把检测过程分为粗略检测阶段和精细检测阶段，其中精细检测即直接对飞机凸多边形进行两两检测。74计算机应用与软件2023 年由于场面飞机较多，直接进行精细检测会消耗较多检测时间，所以使用检测速度较快的方法先进行粗略检测可以提高检测速度。如图 4 所示，B 区为粗略检测区，使用类包围球方法，原点为恰好能够把 A 区围住的圆的圆心。A 区为精细检测区，用一个多边形把飞机模型围起来，多边形形状即飞机模型向外制动一个安全距离所得，在顶点部分进行圆滑处理，即以飞机模型顶点为圆心画弧。由于飞机实体较大，若顶点不进行圆滑处理，则会出现机翼顶点区域向外制动的安全距离过长，会导致虚警。设飞机安全距离告警阈值为 SPTP，飞机机头到机尾距离为 d，则有飞机模型对应 B 区的半径为 rB=2 SPTP+d。图 4飞机安全区域及阈值设置具体实现中，目标的冲突检测需先检测 B 区是否碰撞，如果没有则进行下一个目标模型检测，否则再进行 A 区碰撞检测。由于飞机 A 区检测比较复杂，所以用 B 区包起来先进行一次快速粗略检测，这样可以降低检测 A 区的次数，从而很大程度减少程序时间复杂度，增快检测速度。2检测算法描述凸多边形碰撞检测算法使用分离轴定理，若令 K和 L 为两个不相交的非空封闭凸集，其中一个是有界闭集，则存在一个非零向量 v 和实数 r1 r2，有:x1，v r2(x1K)，x2，v r1(x2L)(5)若 K、L 集合都是开放的，则存在一个非零向量 v和实数 r 使得:x1，v r(x1K)，x2，v r(x2L)(6)如图 5 所示，取飞机模型的两个凸多边形 a 与 e为例，把多边形的顶点都投影至一条轴线上。只要找到一条或多条轴(分离轴)，使凸多边在该轴的投影不相交，那就可以说明这两个或多个物体没有发生碰撞。为了方便观察，垂直于分离轴且可以把目标分为左右两边的向量称为分离线。图 5分离轴定理示图分离轴定理所选择的潜在分离轴通常都是凸多边形的边所在的轴线，随着边数的增多，检测的次数会不断增加(如一直未找到潜在分离轴)，只要找到一条不相交的分离轴，程序就会立马停止检测，所以基于分离轴定理的碰撞检测算法属于高效的算法，不过弊端也非常明显，当找不到分离轴的时候，算法复杂度会增加。所以需要一个改进的方案，降低程序寻找分离轴的次数，从而提高计算效率。由于应用场景是场面飞机，而对于精细检测阶段，把 A 区分解成 5 个有效凸边形(此处凸边形是指没有进行顶点圆弧处理的多边形)，则两个飞机 A 区碰撞检测算法最多会被调用 25 次，若飞机数量增加，碰撞算法时间复杂度也会增大，所以碰撞算法的选取显得尤为重要，本文使用基于分离轴定理的碰撞检测算法。多架飞机之间碰撞如果用传统的分离轴定理效率不够高，由于每架飞机有 5 个凸边形 17 条边，逐个查找分离轴最多需要 17 2 次，两架飞机总的查找次数为 5!17 2 即 4 080 次，若有 n 架飞机，则查找次数变为 n!4 080 次。所以传统基于分离轴的碰撞检测算法不适合边数较多的凸多边形。由于两个目标碰撞一定是点和点、点和线、线和线的其中一种情况，即一定包含一个顶点，所以找到这个可能的顶点可以减少碰撞检测次数。首先找到碰撞点序列，再利用折半搜索技术求取最初碰撞的顶点和边。本文利用改进的分离轴碰撞检测算法即基于最近点的碰撞检测。设ai(xi，yi)(i=0，1，16)为飞机的顶点，Tj(j=a，b，c，d，e)为飞机模型里的 5 个凸多边形，则有:Ta=