第4期 张飞，等：基于改进D*算法的无人机室内路径规划 ·663· Stentz-1首次提出了D*路径规划算法，用 利用OPENCV和ARUCO库可以生成使用的 于自主机器人在部分已知或完全未知环境中通过 二维码。首先，通过选择aruco模块中一个预定 局部修正路径，减少计算量，实时获得一条次优 义的字典来创建一个字典对象，具体而言，这个 路径。Hrabar针对使用立体视觉导航的无人机 字典是由250个marker组成的，每个marker的大 提出了一种将D*算法与随机路线图法结合的路 小为(7×7)bit。然而利用语句cv:aruco:drawMark 径规划方法，通过该方法可以实现无人机在未知 er(dictionary,i,200,markerImage,l)生成ID编号 环境下三维空间避让障碍物的路径规划。郑昌 为1的二维码。其中，第1个参数为之前创建的 文]利用稀疏A*算法实现了离线的三维航迹规 字典对象，第3个参数为输出marker的大小，第 划，并通过对稀疏A*算法的动态化实现了无人机 4个参数为输出图像。 遇到未知威胁时的动态轨迹重规划。符小卫等叫 二维码的识别步骤主要有4步： 研究了基于Voronoi图和Dijkstra算法的三次样 1)图像分割：提取灰度图像中最突出的轮 条曲线和序列二次规划的方法。这些研究大多是 廓。采用局部自适应阈值的方法来分割marker 基于D*算法的无人机三维空间避让障碍物的路 (图2(b)。 径规划，未考虑无人机在轨迹移动时如果距离障 2)轮廓提取和过滤：使用Suzuki等1算法对 碍物较近时会发生与障碍物碰撞或者穿越的情 阈值图像进行轮廓提取。它产生一组图像轮廓， 况，不利于无人机室内高精度导航。 其中大部分与检测目标无关（见图2（©）)。然后， 本文以通过增加碰撞因子改进D*算法实现 使用Douglas-Peucker叨算法进行多边形近似。由 了无人机的室内路径规划，并通过布置室内二维 于标记被包围在矩形轮廓中，所以没有近似于 码数组图像对改进D*算法进行了试验，验证了改 4顶点多边形的那些被丢弃。最后，简化了附近 进D*算法对于无人机室内路径规划的适用性。 的轮廓，只留下外部轮廓。图2()显示了从该过 程得到的多边形。 1 ArUco码的识别和位置求解 l.1 ArUco码的识别 本文采用ArUco码作为地面二维标志来设计 定位阵列，ArUco系统1由Cordoba大学AVA 团队设计并提供面向全平台的SDK,ArUco码（下 (a)输入图片 (b)边缘检测结果 文简称二维码)由7×7方块阵列，二维码边框为黑 色其余方块可以是白色(1)或黑色(0)。 四 一个ArUco标记是一种合成的方形标记，由 一个宽的黑色边框和内部的二进制矩阵构成，这 决定了它的标识符(D)。标记的大小决定了内部 (©)四边形检测结果 维码识别结果 矩阵的大小。Aruco码能被当作7×7的布尔居 中，外环被黑色充满，能被图像快速检测 (e)透视度()编码 ArUco码内部数据信息量为(5×5)bit,最大的编码 换和网络化提取 数量为1024个，每一行使用2bit进行编号，使用 图2 ArUco码检测步骤 另外3bit进行纠错能在任意方向识别出唯一码 Fig.2 ArUco code detection steps 号，如图1所示解码结果为(0000100101)即为 3)标记代码提取：分析这些轮廓的内部区域 37号。 以提取其内部代码。首先，通过计算单应性矩阵 标记代码 来消除透视投影（图2(e)。使用Otsu的方法1阁对 二进制 所得到的图像进行阈值化，其提供了图像分布是 00 双峰的（在这种情况下是正确的）最佳图像阈 00 10 01 0 值。然后，二值化图像被划分为规则网格，并且 01 每个元素根据其中的大多数像素的值被分配值 01 0或1（图5）。第1个测试包括检测黑色边框的存 图1No.37 ArUco二维码 在。如果边界的所有位为0，则使用下述方法分 Fig.1 No.37 ArUco QR code 析内部网格。Stentz[10-11] 首次提出了 D*路径规划算法，用 于自主机器人在部分已知或完全未知环境中通过 局部修正路径，减少计算量，实时获得一条次优 路径。Hrabar[12] 针对使用立体视觉导航的无人机 提出了一种将 D*算法与随机路线图法结合的路 径规划方法，通过该方法可以实现无人机在未知 环境下三维空间避让障碍物的路径规划。郑昌 文 [13] 利用稀疏 A*算法实现了离线的三维航迹规 划，并通过对稀疏 A*算法的动态化实现了无人机 遇到未知威胁时的动态轨迹重规划。符小卫等[14] 研究了基于 Voronoi 图和 Dijkstra 算法的三次样 条曲线和序列二次规划的方法。这些研究大多是 基于 D*算法的无人机三维空间避让障碍物的路 径规划，未考虑无人机在轨迹移动时如果距离障 碍物较近时会发生与障碍物碰撞或者穿越的情 况，不利于无人机室内高精度导航。 本文以通过增加碰撞因子改进 D*算法实现 了无人机的室内路径规划，并通过布置室内二维 码数组图像对改进 D*算法进行了试验，验证了改 进 D*算法对于无人机室内路径规划的适用性。 1 ArUco 码的识别和位置求解 1.1 ArUco 码的识别 本文采用 ArUco 码作为地面二维标志来设计 定位阵列，ArUco 系统[15] 由 Cordoba 大学 AVA 团队设计并提供面向全平台的 SDK，ArUco 码 (下 文简称二维码) 由 7×7 方块阵列，二维码边框为黑 色其余方块可以是白色 (1) 或黑色 (0)。 一个 ArUco 标记是一种合成的方形标记，由 一个宽的黑色边框和内部的二进制矩阵构成，这 决定了它的标识符 (ID)。标记的大小决定了内部 矩阵的大小。Aruco 码能被当作 7×7 的布尔居 中，外环被黑色充满，能被图像快速检 测 ArUco 码内部数据信息量为 (5×5)bit，最大的编码 数量为 1 024 个，每一行使用 2bit 进行编号，使用 另外 3bit 进行纠错能在任意方向识别出唯一码 号，如图 1 所示解码结果为 (00 00 10 01 01) 即为 37 号。 二进制 标记代码 00 00 10 01 01 1 1 0 1 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 0 0 0 0 0 0 图 1 No.37 ArUco 二维码 Fig. 1 No.37 ArUco QR code 利用 OPENCV 和 ARUCO 库可以生成使用的 二维码。首先，通过选择 aruco 模块中一个预定 义的字典来创建一个字典对象，具体而言，这个 字典是由 250 个 marker 组成的，每个 marker 的大 小为 (7×7)bit。然而利用语句 cv::aruco::drawMark￾er(dictionary, i, 200, markerImage, 1) 生成 ID 编号 为 i 的二维码。其中，第 1 个参数为之前创建的 字典对象，第 3 个参数为输出 marker 的大小，第 4 个参数为输出图像。 二维码的识别步骤主要有 4 步： 1) 图像分割：提取灰度图像中最突出的轮 廓。采用局部自适应阈值的方法来分割 marker (图 2(b))。 2) 轮廓提取和过滤：使用 Suzuki 等 [16] 算法对 阈值图像进行轮廓提取。 它产生一组图像轮廓， 其中大部分与检测目标无关 (见图 2(c))。然后， 使用 Douglas-Peucker[17] 算法进行多边形近似。由 于标记被包围在矩形轮廓中，所以没有近似于 4 顶点多边形的那些被丢弃。最后，简化了附近 的轮廓，只留下外部轮廓。图 2(d) 显示了从该过 程得到的多边形。 (a) 输入图片 (b) 边缘检测结果 (c) 四边形检测结果 (d) 二维码识别结果 (f) 编码 提取 (e) 透视度 换和网络化 图 2 ArUco 码检测步骤 Fig. 2 ArUco code detection steps 3) 标记代码提取：分析这些轮廓的内部区域 以提取其内部代码。首先，通过计算单应性矩阵 来消除透视投影 (图 2(e))。使用 Otsu 的方法[18] 对 所得到的图像进行阈值化，其提供了图像分布是 双峰的 (在这种情况下是正确的) 最佳图像阈 值。然后，二值化图像被划分为规则网格，并且 每个元素根据其中的大多数像素的值被分配值 0 或 1(图 5)。第 1 个测试包括检测黑色边框的存 在。如果边界的所有位为 0，则使用下述方法分 析内部网格。 第 4 期 张飞，等：基于改进 D*算法的无人机室内路径规划 ·663·