ScienceDirect计算设计与工程杂志5（2018）337：体素膨胀、中间对象和RKGA的视图规划优化

可在ScienceDirect上获得目录列表计算设计与工程杂志首页：www.elsevier.com/locate/jcde计算设计与工程学报5（2018）337基于体素膨胀、中间对象和随机密钥遗传算法魏静a，b，周伟，岛田健二aa卡内基梅隆大学机械工程系，5000 Forbes Ave，Pittsburgh，PA 15213，USAb计算科学系，高性能计算研究所，1 Fusionopolis Way，138632，新加坡阿提奇莱因福奥文章历史记录：2017年6月16日收到2017年10月16日收到修订版，2017年在线发布2017年保留字：视图规划MedialObjects UAV随机密钥遗传算法体素膨胀A B S T R A C T基于模型的视图规划是寻找覆盖目标几何模型表面的近似最优视点集它已被应用于许多建筑物的检查和监视应用与无人机（UAV）。在过去的几十年中提出的先前的方法遭受几个局限性：他们中的许多人专门针对2D问题工作，在3D环境中仅生成针对目标表面的次优视图集合，和/或在3D环境中生成仅覆盖目标表面的一部分的视图集合 本文提出了一种新的两步计算方法，寻找接近最佳的意见，以覆盖目标建筑物集的表面，使用体素膨胀，中间对象（MO），和随机密钥遗传算法（RKGA）。 在第一步中，所提出的方法膨胀的建筑物表面体素膨胀，以定义一个子体积周围的建筑物。然后计算该子体积的MO，并且使用围绕MO表面的高斯采样对候选视点进行在第二步中，一个优化问题被公式化为（部分）集合覆盖问题，并通过使用RKGA和贪婪搜索搜索通过候选视点来解决。通过几个算例对所提出的两步计算方法的性能进行了测试，并将其性能与两种先前提出的方法：最优扫描区域方法和基于随机采样的方法进行了比较实验结果表明，该方法在较少的视点和较高的覆盖率下，找到了更好的解决方案，优于以往的方法。©2017计算设计与工程学会Elsevier的出版服务这是一个开放在CC BY-NC-ND许可证（http://creativecommons.org/licenses/by-nc-nd/4.0/）下访问文章1. 介绍建筑物检查和监督应用（Bircher等人，2015; Jing，Polden，Lin，&Shimada，2016）与无人机（UAV）的结合近年来引起了越来越多的关注，这是由于无人机技术的快速发展。这些应用程序的第一步是确定必要视点的有效计划，以实现所需的检查和监视目标。规划这些视点的过程通常被称为视图规划问题，在一些文献中也被称为传感器规划问题（Tarabanis，Tsai，Kaul，1996）或传感器放置问题（Son Lee，2003视图规划是找到一组视点，包括位置和方位。由计算设计与工程学会负责进行同行评审。*通讯作者：卡内基梅隆大学，5000福布斯大道，匹兹堡，PA 15213，美国。电 子 邮 件 地 址 ： wj@andrew.cmu.edu ， jing_wei@ihpc.a-star.edu.sg （ W 。Jing），shimada@cmu.edu（K. Shimada）。该方案覆盖了目标物体的所需表面区域（Scott，Roth，Rivest，2003; Tarbox Gottschlich，1995），其中视觉传感器由机器人携带。在视图规划的检查和监视应用中（Chen，Li，&Kwok，2011;Jing，Polden，Lin等人，2016），常见的优化目标通常是减少视点的数量并增加表面区域的覆盖率。典型的视觉传感器（诸如常规相机、深度相机、热感相机）可以附接到固定结构、安装在机器人臂上或安装在无人驾驶车辆上。例如，在建筑物的热检测中（Martinez-De Dios Ollero，2006），带有热成像相机的无人机在建筑物周围飞行，以检查建筑物表面的热损失另一个类似的应用是在被自然灾害破坏的城市区域中的搜索和救援操作（Gentilini等人， 2012年），无人机被派去拍摄一组图像以寻找幸存者。视图规划问题可以分为两组：(1) - 基于模型的视图规划，其中，在规划之前，目标对象的至少粗略几何模型是可用的，以及(2) 非基于模型的视图规划，其中没有此类模型https://doi.org/10.1016/j.jcde.2017.11.0132288-4300/©2017计算设计与工程学会Elsevier的出版服务这是一个在CC BY-NC-ND许可证下的开放获取文章（http://creativecommons.org/licenses/by-nc-nd/4.0/）。338W. Jing，K.Shimada/ Journal of Computational Design and Engineering 5（2018）337available.在本文中，我们专注于基于模型的视图规划问题，特别是建筑物检查和监视应用（程，凯勒，库马尔，2008年;尼尔森，奥格伦，&Thunberg，2008年）与无人机。如图1所示，建筑物检查和监视应用是对附近建筑物的表面进行测量的任务（Bircher等人，2015; Geng，Zhang，Wang，Fuh，&Teo，2013）。由于目标建筑物的几何形状保持不变，检查和监视任务经常定期重复，因此将建筑物检查和监视应用程序制定为基于模型的视图规划问题是合适在这些应用中，视点的数量和表面覆盖率是主要的关注点，而计算成本可能不是一个问题，因为规划过程可以离线执行。在本文中，我们提出了一个新的两步计算方法，基于模型的视图规划的建筑物检查和监督的应用。我们的工作的主要贡献是使用两种几何方法，体素膨胀和MO，以及高斯采样方法来生成一组高质量的候选视点，这导致了一组更少的视点，从而产生更高的目标建筑物表面的覆盖率。结合贪婪搜索和随机密钥遗传算法也被用来解决制定的部分集合覆盖问题在后面的步骤。本文其余部分的结构如下。第2节讨论了以前的工作，包括两种方法，最佳扫描区域的方法和基于采样的方法，这是用来衡量所提出的计算方法。第3节详细定义了建筑物检查和监督任务的视图规划问题，第4节解释了提出的第5节介绍了基准研究的结果结论和对未来工作的建议见第6节。2. 以前的工作在基于模型的视图规划中，由于视点搜索空间大，覆盖问题往往是NP困难的，因此寻找具有完全覆盖率或高覆盖率的近最优视点集是一项艰巨的任务。自20世纪80年代以来，研究人员提出了不同的近似方法来寻找解决方案。大多数以前的工作使用两步“生成测试”方法（Scott等人， 2003年），只有少数例外。20世纪90年代初的工作（Tarabanis，Tsai，Allen，1995）不是该方法采用视景可见性模型寻找曲面片的可见区域，并选择重叠最多的视点，直至实现全覆盖。在这项工作之后，“生成测试”方法（Scott等人 ，2003 年 ， 成 为 流 行 。 1995 年 ， 研 究 人 员 （ TarboxGottschlich，1995）引入了可测性矩阵，并从包围目标物体的视球表面生成的候选视点集中找到了最优解。后来，研究人员（Scott，2009）提出了一种对可测性矩阵进行了修正，将视景规划问题转化为一个集合覆盖问题（SCP），并采用内线性规划方法求解最近，一种基于随机抽样的方法（Jing，Polden，Lin等人， 2016）生成目标建筑物周围的候选视点，然后采用贪婪搜索算法求解SCP问题。先前提出的方法和其他相关方法的更多细节在几篇调查论文中描述：（ Chen 等 人 ， 2011; Galceran &Carreras ， 2013; Mavrinac&Chen ， 2013; Scott 等 人 ， 2003;Tarabanis ， Allen ， &Tsai ，1995）。许多研究人员已经研究了建筑物检查和监视应用（Geng等人，2013; Jing，Polden，Lin等人，2016; Nilsson等人， 2008年）。视图规划对于最小化检查和监督成本起着无人地面车辆（UGV）用于监测建筑物（Nilsson等人， 2008），其中视点位置在2D环境中。提出了一种使用无人机执行监视任务的规划方法，该方法仅考虑了三维城市环境中建筑物的顶面（Semsch、Jakob、Pavlicek、Pechoucek，2009年）。最近，研究人员（Geng等人， 2013）也报道了同样在3D城市环境中的基于进化算法的视图规划方法，但是该方法仅考虑覆盖建筑物的顶表面，例如屋顶和地面。大多数用于检测和监视应用的先前视图规划方法集中于2D视图规划或部分3D视图规划，其中视点的姿态用少于6个自由度（DOF）表示。此外，这些方法倾向于生成比所需更多数量的视点，和/或视点错过目标表面的相对大的部分。 为了找到产生高覆盖率的少量视点，流行的两步“生成-测试”方法（Scott等人，2003年;斯科特，2009年）可以应用，但该方法最初是为具有相对简单的几何形状的单个对象设计的。当应用于由多个建筑物组成的复杂目标时，以前的Fig. 1.建筑物检查和监视：带有视觉传感器的无人机围绕建筑物（蓝色显示）飞行，以获取建筑物的表面信息。视觉传感器具有由视场（FOV）和景深（FOD）限定的可见区域。膨胀体积由建筑物（以绿色显示）、地面（以黑色显示）和建筑物曲面（以橙色显示）的偏移曲面界定。红色虚线表示扩张体积的MOW. Jing，K. Shimada/ Journal of Computational Design and Engineering 5（2018）337339Xð Þð2016年12月28日图二、该方法分为两步：第一步寻找一组候选视点，第二步寻找覆盖目标建筑物所有表面的候选视点的最优子集该方法可能不能在“生成”步骤中生成合适的候选视点。这是因为以前的基于随机抽样的方法（Englot Hover，2013; Jing，Polden，Tao，Lin，Shimada，2016）通常效果更好，但在太空探索方面仍然不够有效3. 问题公式化如图1所示，对于本文所讨论的建筑物检查和监视应用，UAV围绕建筑物飞行以利用视觉传感器获取建筑物的表面信息。目标是找到传感器的最小视点集，以便它们完全覆盖目标建筑物的表面。在该应用中，视觉传感器的6-DOF位置和取向可以通过UAV的运动以及与传感器附接的平移-倾斜机构来实现。传感器的可见区域由参数、视场（FOV）和景深指定。目标是城市街区的一组建筑。由于这是一个基于模型的视图规划问题，我们假设建筑物的形状是已知的，它们被表示为多边形表面补丁。我们将我们的视图规划问题公式化为受约束的组合优化问题：nminx ix i2 f 0; 1 g;1/1时间：S¼[fpi·xi对于所有我，其中，S1/4 =1;s1;... Smm是目标建筑物的表面块;n是候选视点的数目;xi指示候选视点是否应包括在所选择的视点集合中以覆盖目标建筑物;xi1/4 1表示包括该视点，而xi1/40表示不包括该视点pi是位置，函数f将视点映射到曲面片的集合或S的子集。Fpi是根据预定义的可见性准则定义从视点pi可见哪些表面片的映射。例如，如果三个曲面片s5、s6和s7从第三个candi可见日期视点，则f x3s5;s6;s7。在这个公式中，目标是找到一组覆盖目标建筑物的所有表面块的最少视点。4. 建议的计算方法在本文中，我们提出了一种新的基于计算模型的视图规划方法，用于建筑物检查和监控应用。该方法结合了几何方法和组合优化方法，生成的视图规划结果具有较高的覆盖率和较少的视点，覆盖要求。该方法首先采用体素膨胀和中间对象（MO）两种几何方法，结合高斯采样方法生成候选视点。第二步从候选视点集合中寻找近优视点子集，通过建立部分集合覆盖问题（SCP）的数学模型，并采用随机密钥遗传算法和贪婪搜索方法求解SCP图 2总结了所提出的视图规划方法的过程流程。与以前的工作相比（Chen &Li，2004; Jing，Polden，Lin等人，2016年;斯科特，2009年），它也利用了两步优化，包括候选视点的生成和最终视点的选择。如第4.1节所述，所提出的方法在视点生成步骤中使用体素膨胀、MO和高斯采样而不是简单的偏移或随机采样，在第4.2节所述的第二步中产生更好的结果。4.1. 候选视点集第一步的目的是采样一组具有良好质量的候选视点。跳过这一步骤并试图直接找到最佳视点集将需要在高维空间中进行优化，这需要不切实际的高计算成本。预先选择候选视点缩小了搜索空间，并显着降低了计算成本。高质量的候选视点应满足以下条件：候选视点应该具有高覆盖率。这是因为在第二步骤中选择的候选视点的子集的覆盖率被候选视点的覆盖率封顶。候选视点应包括可以看到目标建筑物的凹入边缘和拐角的视点。候选视点的数量应该与曲面片的数量过多的候选视点将导致不必要的高计算成本，而过少的候选视点将导致低覆盖率和不太理想的结果。如图3所示，所提出的方法通过以下方式生成这样的高质量候选视点：（1）体素化建筑物形状并膨胀体素化的建筑物形状，（2）生成膨胀体积的MO，（3）去除位于仅由膨胀表面定义的MO子集上的MO点，以及（4）在MO上使用高斯采样对候选视点进行采样，并使用局部势场方法生成观看方向。这些步骤的详细说明见第4.1.1●●●340W. Jing，K.Shimada/ Journal of Computational Design and Engineering 5（2018）337ðÞ图三. 使用体素膨胀和MO生成高质量的候选视点。(a) 原始模型，A;和膨胀遮罩，B。(b)扩张体积（以黑色显示）。见图4。 3D扩张的横截面示例。4.1.1. 二元体素膨胀二进制膨胀，也称为Haralick，Sternberg和Zhuang（1987），是数学形态学中的一种基本运算。它是3D空间中的类似卷积的操作，并生成如图所示的膨胀对象。 四、膨胀在计算机图形学、运动规划、图像处理和计算几何中有着广泛的应用在欧几里得空间中，二进制膨胀被定义为：一 B¼ fab ja 2A;b 2B g：在所提出的方法中，目标对象的二进制体素膨胀用于生成膨胀体积（图4（b）中右图的黑色部分），其MO然后将用于在稍后的步骤中生成可膨胀的视点集。通过用原始目标对象减去扩张对象来本文针对建筑物检测和监视应用中，要求覆盖除底面以外的所有模型面为了更好地融合离散体素空间，在我们的实现中，立方体而不是球体用于膨胀。具有不同扩张尺寸的扩张模型的示例如图所示。五、扩张的大小由视觉传感器的FOD确定通常，当观察距离接近FOD的最大值时，传感器的观察区域最大化。在所提出的方法中，我们实验发现，我们的目标物体的传感器FOD的最大值的约1.4至1.6倍的扩张产生良好的效果。然后，从扩张体积产生的MO位于距目标建筑物表面的传感器FOD的最大值的约0.7至0.8倍的距离处。4.1.2. 中间对象生成如图6所示，在文献中也称为中轴变换（MAT）（Price，Stops，&Butlin，1995）的内侧对象（MO）是目标对象的骨架，并且由与原始目标对象边界上的至少两个点具有相同最近距离的所有点组成（Blum& Nagel，1978; Price等人，1995年）。MO的一个重要性质是它降低了原模型的维数，并保持了原模型的几何信息。在过去的几年中，基于MO的方法已经用于机器人位姿规划（Wilmarth，Amato，&Stiller ， 1999; Yeh ， Denny ， Lindsey ， Thomas ， Amato ，2014），以提高探索空间的效率。然而，据我们所知，这是第一次使用MO覆盖规划问题的体素膨胀和高斯采样，在无人机检查和监视应用。在本文中，我们使用&MO定义为：S<$fs2 Vj 9a;b2d V;a-b;其中S是MO的点集;V是原始模型;dV是原始模型的边界;Dx;y是两点之间的欧几里得距离。为了减少计算量，我们对MO点进行均匀重采样，删除与目标物体表面无关的MO点W. Jing，K. Shimada/ Journal of Computational Design and Engineering 5（2018）337341267ðÞ4523四分之二]2vp-p补丁恩¨4.2.1. 细分目标对象模型对于优化问题公式化，另一个任务是将目标对象的表面细分成三角形表面片的网格，这被认为是对表面进行采样细分的表面与合理的补丁大小和保持其原始形状是在这项工作中的一个重要任务;如果补丁大小太大，结果可能无法完全覆盖的表面，因为可见性测试检查的中心点的三角形;如果补丁大小太小，计算成本可以变得不切实际的高。在本文中，我们使用Shimada和Gossard（1995）的方法来生成一个形状良好的三角形网格，保持原来的形状很好，并保持补丁的均匀性。图7显示了网格划分结果。(c) 扩张20体素（d）扩张30体素图五. 原始对象和放大对象。4.2.2. 用可见性矩阵在该方法中，建立了一个可见性模型，以决定是否可以从一个视点看到一个曲面片。在模型中，如果满足以下所有条件，则曲面片从视点可见：从视点看，曲面片必须在传感器的视场（FOV）内从视点看，曲面片必须在传感器的深度场（FOD）内。dminpvp-p patch·nvpdmax<<视角b必须在由传感器规格预测的一定范围内。arccos。我是副总裁我是补丁！B贴片(a)原始模型（b）原始模型见图6。 3D模型的中间对象示例。4.1.3.使用高斯采样对中间对象周围的视点进行采样为了从MO获得视点，对MO执行采样过程。我们执行高斯分布的采样，平均值在中间对象上，协方差矩阵为rIR3×3。确定视点位置，通过随机选择MO上的一个点，并使用所选MO点上的平均值执行高斯采样策略（Boor，Overmars，van der Stappen，1999）。高斯采样作为一种有偏采样方法被应用，由于MO周围的空间携带了更多有意义的目标物体的几何信息，因此对MO进行有偏采样将比随机采样方法更有效。因此，采用高斯抽样方法可以得到更好的规划结果.除视点位置外，还利用概率局部势场法得到了视点的观察方向。正如我们以前的工作（Jing，Polden，Lin等人，2016），该方法假设存在来自目标建筑物表面的吸引力，并且在某个视点上的总吸引力的方向是该视点的观看方向。4.2. 用组合优化方法选择视点由于将视点映射到曲面片的可见性函数是非参数集到集映射，因此该问题必须被公式化为组合优化问题。前一步使用几何信息来减少视图规划问题中的视点和曲面片的数量，使其对于这一步中的组合问题来说是合理的必须没有遮挡，这意味着曲面片和视点之间没有实体这个条件是使用射线-三角形相交算法（Möller Trumbore，1997年）的修改版本计算的，该算法的运行时间为O mn2，其中m是视点的数量，n是曲面片的数量该算法用一条线段连接视点和曲面片，并检查该线段是否与目标物体的其它三角形相交。在本文中，我们使用经典的针孔摄像机模型和投影矩阵（HartleyZisserman，2003）来模拟FOV可见性。通过将偏斜参数设置为0，针孔相机的理想固有矩阵为：ax0px=2K¼ 0 aypy=22R3×3;001其中ax;ay是焦距，以x上的像素尺寸表示和y轴;px;py是x和y轴上的像素数。外矩阵由位置T和方向给定视点的R：E¼½R;T]2R3×4：然后给出了摄像机的内、外矩阵，计算点px;y;z; 1TR4×1在图像平面上的投影：u<$ K·E · p：为了保证可见性，给定点的投影必须在相机的像素范围因此，对于给定的点，如果(a)原始模型(b)膨胀10个体素●●●●bmin

下载后可阅读完整内容，剩余1页未读，立即下载