张世辉，张钰程

(1．燕山大学信息科学与工程学院，河北秦皇岛066004; 2．河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛066004)



基于单幅深度图像遮挡信息的下一最佳观测方位确定方法

张世辉1，2，张钰程1

(1．燕山大学信息科学与工程学院，河北秦皇岛066004; 2．河北省计算机虚拟技术与系统集成重点实验室，河北秦皇岛066004)

摘要:如何根据当前观测到的信息确定摄像机的下一最佳观测方位是视觉领域一个具有挑战性的问题．本文提出一种基于单幅深度图像利用遮挡信息求解下一最佳观测方位的方法．该方法首先利用当前观测方位下获得的深度图像中的遮挡信息对遮挡区域外接表面进行四边形剖分，从而建立遮挡区域外接表面模型;然后通过综合考虑下一观测过程中的可见四边形信息以及观测损失信息构造下一最佳观测方位模型;最后采用梯度下降法求解所建模型得到下一最佳观测方位．与已有方法相比，所提方法无需将摄像机位置固定于某一表面，也无需获取视觉目标的先验知识．实验结果验证了所提方法的可行性和有效性．

关键词:下一最佳观测方位;深度图像;遮挡信息;遮挡区域外接表面;梯度下降法

1　引言

下一最佳观测方位(Next Best View，NBV)的确定一直是场景探测、三维重建、目标识别等领域重要研究问题之一，它是基于当前观测方位下摄像机获取的信息，确定出摄像机的下一观测方位，使摄像机能够在下一次观测中最大量地获取到当前观测方位下未知的信息．

目前，下一最佳观测方位问题的研究主要基于两种图像:彩色图像和深度图像．基于彩色图像的下一最佳观测方位确定算法相对较少，并且存在一些局限性，算法效率有待提高．代表性的方法有: Bottino［1］提出一种交互式重建方法确定下一最佳观测方位，其基于最优重建条件判断是否需要继续观测，但该方法不适用于复杂表面物体．Haner［2］基于协方差传播理论估计不确定性从而确定下一最佳观测方位，但计算耗时较大．

与彩色图像不同，深度图像中的像素值表示场景中某一点到摄像机成像平面的距离，这意味着基于深度图像更易获取场景的三维信息，故现有的下一最佳观测方位确定算法大多基于深度图像实现．代表性的成果有: Connolly［3］采用八叉树模型描述视觉目标，对每个节点进行标记从而确定出下一最佳观测方位，但该方法未考虑遮挡因素，所以遮挡现象越严重，越无法保证方法的正确性．Maver［4］提出一种利用遮挡信息确定下一最佳观测方位的方法，用多边形近似遮挡区域，但该方法基于特定设备，不具有良好的普适性．Pito［5］基于PS(Positional Space)算法从大量潜在观测方位中确定出下一最佳观测方位，但摄像机位置被限制在固定表面，且PS算法在观测光线的投影过程中会花费大量的时间．Banta［6］提出一种基于体素块的不同标记以及整体观测策略确定下一最佳观测位置的方法，该方法中摄像机的位置同样被限制在固定表面，并且需要预先获取场景的先验知识．Chen［7］提出一种基于模型的利用HG(Hierarchical Genetic)算法和Christofides算法解决视点规划问题的方法，该方法不仅需要获取场景的先验知识，而且计算耗时也较大．Li［8］提出一种基于B样条计算信息熵的视点规划方法，把摄像机能够获得模型最大信息熵的方位作为下一最佳观测方位，但该方法计算出的摄像机位置同文献［5，6］一样也被限定在一个固定表面，且方法耗时受已观测点云数量的影响较大．Scott［9］提出一种基于模型的3M (Modified Measurability Matrix)算法解决视点规划问题，该方法同样需要获取场景的先验知识．Vasquez-Gomez［10］通过效用函数(Utility Function)对生成的候选观测方位进行排序求得下一最佳观测方位，但其视点评价过程需要花费大量的时间．

综上分析可知，现有下一最佳观测方位确定方法普遍存在摄像机位置受限、需要先验知识或耗时较大等方面的不足．鉴于此，本文提出一种基于深度图像利用遮挡信息确定下一最佳观测方位的方法．该方法首先从当前观测方位下获取一幅深度图像，然后基于遮挡信息构造下一最佳观测方位模型，最后利用梯度下降法求解所建模型得到下一最佳观测方位．实验结果验证了所提方法的可行性和有效性．

2　方法概述

2．1下一最佳观测方位问题分析

观测方位是指摄像机观测视觉目标时的方向和位置．在观测过程中，遮挡现象几乎无处不在．图1为摄像机观测一个由矩形ABCD和矩形GHIJ构成的理想视觉模型的示意图．在当前观测方位下产生了遮挡现象，AB、AD和BC为遮挡边界，五面体ABCFED内的空间区域为遮挡区域，面ADE、面BCF和面ABFE构成遮挡区域的外接表面．为了获取视觉目标遮挡区域内的信息则需要调整摄像机的观测方位进行进一步观测．在所有可能的下一观测方位中，能够最大量观测遮挡区域内未知信息的观测方位即为下一最佳观测方位．

分析可知，摄像机和遮挡区域是下一最佳观测方位问题所涉及的两个主要研究对象．如果以摄像机为研究对象求解下一最佳观测方位问题，则需要预先给出摄像机所有可能的观测方位，因此，为了获取有穷的观测方位集合就需要对摄像机的观测位置加以限制．同时，由于摄像机可能的观测方位一般都比较多，因此在大量可能的观测方位中确定下一最佳观测方位的过程通常耗时较大．但是，如果以遮挡区域为研究对象求解下一最佳观测方位问题，则所需信息主要为当前观测方位下视觉目标的遮挡信息，因此在确定下一最佳观测方位的过程中可以避免上述问题．

由于遮挡区域内的信息在当前观测方位下是未知的，因此需要利用遮挡区域的外接表面信息近似地代表遮挡区域内的信息［4］，根据下一最佳观测方位问题的描述，则求解观测遮挡区域内未知信息的最佳观测方位问题可以近似地转化为求解观测遮挡区域外接表面的最佳观测方位问题．

2.2方法总体思想

基于上述对下一最佳观测方位问题的分析，本文提出一种基于单幅深度图像利用遮挡信息求解下一最佳观测方位的方法．方法总体思想如下:首先，在当前观测方位下获取视觉目标的深度图像．其次，检测和计算深度图像中遮挡信息，并对遮挡区域外接表面进行四边形剖分，同时计算得到各四边形的中心点、法向量和面积．然后，基于四边形信息构造下一最佳观测方位模型．最后，求解所建模型得到下一最佳观测方位．所提方法总体流程如图2所示．

3　基于遮挡信息确定下一最佳观测方位

3.1遮挡区域建模

3.1.1获取与遮挡边界对应的下邻接边界

本文利用深度图像中的遮挡信息确定下一最佳观测方位，由于获取深度图像中遮挡信息的方法已有文献可借鉴［11～13］，故本文不再对获取遮挡信息的遮挡检测过程进行论述，而是重点论述基于遮挡信息的下一最佳观测方位确定过程．获取深度图像中的遮挡边界后，为了确定下一最佳观测方位，下一步需要计算与遮挡边界对应的下邻接边界．以图1中理想视觉模型的遮挡边界AB为例进行分析，AB对应的下邻接边界应为EF，但在真实的三维空间中EF在当前观测方位下并不可见，所以本文选取与EF相邻的可见边界近似作为AB对应的下邻接边界．图3为图1中摄像机获取的深度图像，网状线条为遮挡边界，点状线条为遮挡边界对应的下邻接边界，其中，点A与点E重合，点B与点F重合．

计算深度图像中遮挡边界对应的下邻接边界的具体方法如下．

首先为每一个遮挡边界像素点寻找到一个下邻接边界像素点与之对应．记遮挡边界像素点集合为{ P}O，记下邻接边界像素点集合为{ P}D．在{ P}O中任取一点记为PO，其深度值记为dO，在PO的八邻域内寻找与PO对应的点PD，其深度值记为dD．为了保证集合{ P}O与集合{ P}D中的元素一一对应，需要满足PD既不是遮挡边界像素点，也不与其他遮挡边界像素点对应．同时，考虑到为了确定出最优的下邻接边界，本文定义PO的下邻接边界像素点PD的深度值dD满足dO)．通过上述方法即可求得每一个遮挡边界像素点对应的下邻接边界像素点．所有遮挡边界像素点对应的下邻接边界像素点形成的边界即为遮挡边界对应的下邻接边界．在三维空间中，遮挡边界与其对应的下邻接边界沿摄像机观测方向形成的曲面则为遮挡区域外接表面．

3.1.2基于边界信息建立遮挡区域外接表面模型

为了建立遮挡区域外接表面模型，基于遮挡边界和下邻接边界信息，依次从遮挡边界中取出第i对相邻的两个遮挡边界点POLi、PORi，同时取出两个分别与之对应的下邻接边界点PDLi、PDRi，上述四个点所围成的空间四边形Patchi即为剖分遮挡区域外接表面得到的四边形之一．基于此思想，即可实现对遮挡区域外接表面的四边形剖分．图4给出了对遮挡区域外接表面进行分析的示意图．其中，图4(a)为对遮挡区域外接表面进行四边形剖分后的结果，图4(b)为四边形对应的三维空间结构，图4(c)为四边形对应的深度图像中的结构．

记四边形Patchi的四个顶点的三维坐标分别为，则四边形Patchi的中心点坐标的计算公式定义为

由于空间四边形的四个顶点不一定共面，并且本文前述将深度图像中与遮挡边界相邻的可见边界近似作为与其对应的下邻接边界，故为了减小遮挡区域外接表面建模的误差，本文选取PDLi与PDRi的中点与两个遮挡边界点POLi和PORi组成的三角形的法向量作为四边形Patchi的法向量(见图4(b) )，则四边形法向量vi的计算公式定义为

基于四边形法向量vi的计算公式(2)，则四边形面积Si的计算公式可定义为

则在当前观测方位下遮挡区域外接表面总面积SΣ的计算公式可定义为

式中，n为剖分遮挡区域外接表面所得四边形的个数．

3.2基于遮挡区域外接表面信息构造下一最佳观测方位模型

对遮挡区域外接表面建模后，为了构造下一最佳观测方位模型，需要判断在下一最佳观测方位下剖分所得n个四边形中哪些四边形是可见的，且期望可以最大量地观测到四边形的信息．

记XNV(xNV，yNV，zNV)为下一观测方位下摄像机的位置，向量uNV= (pNV，qNV，tNV)为下一观测方位下摄像机的观测方向，则第i个四边形的中点指向下一观测位置的向量为．若向量ri与第i个四边形的法向量vi的夹角θi，则表明第i个四边形在下一观测方位下是不可见的，故本文定义当向量ri与第i个四边形的法向量vi的夹角时，该四边形在下一观测方位下是可见的．

在观测过程中，若可见的第i个四边形的中点到下一观测方位下摄像机平面的距离远大于或远小于其到当前观测方位下摄像机平面的距离，则意味着在当前观测方位下与下一观测方位下观测到的像素点所代表的三维空间中的真实信息相差较大，如果不加考虑则会导致对两次观测所得像素点进行三维匹配时产生较大的误差．因此，本文首先通过将可见的第i个四边形的中点到下一观测方位下摄像机平面的距离d2i的平方与该点到当前观测方位下摄像机平面的距离d1i的平方的比值减去单位1再求平方的方式衡量两次观测距离的差异．然后利用指数函数的性质对两次观测距离的差异进行归一化，归一化计算公式定义为

由于在相同观测距离下，只有当摄像机观测方向与四边形法向量平行时，摄像机获取的四边形面积最大．若记第i个四边形Patchi的面积为Si，则摄像机在下一观测方位下观测到Patchi的面积可定义为

式中，vi为第i个四边形的法向量为下一观测方位下第i个四边形中点指向下一观测位置的向量，θi为向量ri与第i个四边形的法向量vi的夹角．

结合上述分析，若同时考虑摄像机在下一观测方位下能够最大量地观测到遮挡区域外接表面剖分所得四边形且能够最大量地降低观测误差两方面因素，则可以把公式(5)中归一化的结果作为公式(6)中面积的权值，也就是说，将摄像机观测方位信息作为其获取到的第i个四边形面积的权值．基于此思想，本文最终构造出的下一最佳观测方位模型为

式中，X(xNBV，yNBV，zNBV)为下一最佳观测方位下摄像机的位置，向量u = (pNBV，qNBV，tNBV)为下一最佳观测方位下摄像机的观测方向．

3.3下一最佳观测方位模型求解

分析式(7)模型可知其并非一个凸模型，故很难直接利用凸优化方法得到其全局最优解．可行的解法有随机法、填充函数法、积分水平集法、区域分割法、遗传算法、梯度下降法等．这些方法中，有的理论上就不能得到真正的全局最优解，如随机法、填充函数法、遗传算法和梯度下降法;有的虽然在理论上可得到全局最优解，但需要非常大的计算量，如积分水平集法和区域分割法．就已有方法而言，除了某些特殊的非凸问题能够求得全局最优解外，对于一般的非凸问题，尚无求解全局最优的有效手段．考虑到该模型较易计算梯度，且梯度下降法在迭代过程中需要的存储单元相对较少，在很大程度上可减少算法的空间复杂度，故综合考虑方法的可行性和时间消耗，本文采用梯度下降法求解式(7)的下一最佳观测方位模型．

为了采用梯度下降法求解式(7)模型，首先需要选取较好的初始迭代方位．在不考虑摄像机视角场和物体型面的理想情况下，遮挡区域外接表面剖分所得所有四边形法向量之和的反方向应为最优的初始迭代方向．相应地，初始迭代位置也应在此方向上选取．为了确定初始迭代位置，以当前观测方位下所有已观测点的重心为起点，在初始迭代方向u0上求得一点，使点X0到已观测点重心的距离与当前观测位置到已观测点重心的距离相等．基于上述思路即可得到初始迭代方位(X0，u0)．

初始迭代方位(X0，u0)确定后，即可基于式(7)模型对其六个变量分别求梯度．若记迭代次数为k，迭代步长为λ，则其六个变量沿梯度方向的更新迭代公式为

3.4下一最佳观测方位确定算法

4　实验及分析

4.1实验环境

为了验证本文方法的效果，我们基于http: / /range．informatik．uni-stuttgart．de/htdocs/html上Stuttgart Range Image Database(简称SRID)中提供的三维物体模型进行了实验．实验硬件环境为CPU Intel(R) Core(TM) i7-3770 3.40GHz，内存8.00GB．采用C + +实现下一最佳观测方位确定程序，并结合OpenGL实现摄像机观测物体模型获取深度图像的过程．获取深度图像过程中，设置OpenGL投影矩阵的参数为(60，1，200，600)，窗口大小为400×400.

4.2实验及分析

基于本文所提方法，我们对SRID中不同的三维物体模型进行了实验．实验过程中，遮挡边界检测采用文献［13］中所提方法实现，设定摄像机相对于观测中心点的距离为250mm，步长λ采用固定步长0.1，迭代过程中当的差值小于0.01或迭代次数大于2000则终止(步长0.1、差值0.01和迭代次数2000均为经验值)．图5给出了部分实验结果．其中，图5(a)为视觉目标名称，图5(b)为当前观测方位下视觉目标的深度图像，图5(c)为遮挡边界(白色线条)及下邻接边界(黑色线条)，图5(d)为遮挡区域外接表面各四边形对应的法向量(白色线条)，图5(e)为下一最佳观测方位下可见的四边形集合(白色区域)，图5(f)为所求下一最佳观测方位下视觉目标的深度图像．

分析图5的实验结果可知，对视觉目标Duck而言，由于其遮挡现象并不明显，故在所求下一最佳观测方位下观测到的可见四边形区域并不是很大，即在所求下一最佳观测方位下会观测到较多的已观测点．但对视觉目标Rocker、Mole、Bunny和Dragon而言，由于其遮挡现象比较明显且越来越严重，故在所求下一最佳观测方位下观测到的可见四边形区域越来越大，也就是说，遮挡现象越严重，本文方法效果越好．同时，对照图5(b)和图5(f)中各视觉目标的深度图像可知，本文方法求得的下一最佳观测方位符合人类视觉的观测习惯．

由于目前并不存在下一最佳观测方位评测方面的标准对照图(Ground Truth)，又由于不同方法各有特点，所以很难设定统一的标准对比分析不同下一最佳观测方位算法的优劣．为了进一步验证本文方法的可行性和有效性，我们仅基于本文方法特点对图5的实验结果进行了量化分析．分析结果如表1所示．

表1中，NCV为当前观测方位下获取到的视觉目标表面点的个数，NNBV为所求下一最佳观测方位下获取到的视觉目表面点个数，NOVERLAP为两次观测中重复观测到的视觉目标表面点个数，RNEW为新增率，计算公式为1－NOVERLAP/NNBV，SΣ为公式(4)计算结果，表示当前观测方位下视觉目标遮挡区域外接表面的总面积，SNBV为基于梯度下降法求解公式(7)所得结果，表示在所求下一最佳观测方位下可见的四边形面积加权求和的结果，T为求解下一最佳观测方位所需的时间消耗．每个视觉目标对应的时间消耗为10次实验结果的平均值．

表1　下一最佳观测方位实验结果量化评估

由表1可以看出，摄像机在下一最佳观测方位下获取到的视觉目标上的点具有较高的新增率，并且当遮挡现象越严重，即遮挡区域外接表面面积和SΣ越大时，本文所求下一最佳观测方位下获取到的视觉目标点的新增率越高．结合图5与表1进一步分析可知，对于四边形法向量分布相对分散的视觉目标如Duck、Mole、Bunny和Dragon而言，当遮挡现象越严重时，本文所建模型计算出的SNBV的值也越大，说明摄像机在所求下一观测方位下的确可以获取到大量的当前观测方位下获取不到的信息．同时，对于四边形法向量分布相对集中的视觉目标Rocker而言，虽然其遮挡区域外接表面面积小于视觉目标Mole的遮挡区域外接表面面积，但本文所建模型计算出的Rocker的SNBV的值却比Mole 的SNBV的值大，这一现象反映了本文所建模型对遮挡区域分布较为集中的视觉目标具有更好的响应．

此外，为了评估本文方法的时间消耗，我们将其与同样基于深度图像且考虑了遮挡因素的文献［6］和文献［8］中的方法在相同环境下做了对比实验，实验结果如表2所示．

表2　不同方法确定下一最佳观测方位的时间消耗

由表2的时间消耗可知，图5中所有视觉目标计算下一最佳观测方位的平均耗时为58.30ms，而本文采用文献［13］方法检测遮挡过程的平均耗时为47.41ms，故即使将检测遮挡的耗时也考虑在内，本文方法求解下一最佳观测方位的平均耗时也仅为105.71ms，与文献［6］、文献［8］方法求解下一最佳观测方位的耗时8213.38ms、3236.59ms相比，本文方法明显具有较好的实时性．

5　结论

本文提出一种基于单幅深度图像利用遮挡信息确定下一最佳观测方位的方法．主要贡献在于: (1)提出一种对遮挡区域外接表面进行四边形剖分的遮挡区域建模方法，该方法提供了一种基于可靠的已观测点对未知区域进行建模的思路; (2)提出一种基于四边形法向量和面积信息构造下一最佳观测方位模型的方法，该方法提供了一种根据摄像机观测距离量化观测损失的思路，从而更利于获得合理的候选观测方位; (3)针对发生遮挡现象的视觉目标，给出了一种高效的下一最佳观测方位确定方法，该方法采用梯度下降法求解下一最佳观测方位模型，避免了寻求非凸模型全局最优解的复杂问题．本文方法适用于不同型面的视觉目标，具有较好的通用性和实时性，且遮挡现象越严重，本文方法效果越好．未来我们将对如何自适应地计算遮挡现象的严重性进行进一步研究．

参考文献

［1］Bottino A，Laurentini A．What＇s NEXT? An interactive next best view approach［J］．Pattern Recognition，2006，39(1) : 126－132．

［2］Haner S，Heyden A．Covariance propagation and next best view planning for 3D reconstruction［A］．Proceedings of the 12th European Conference on Computer Vision［C］．Heidelberg，Germany: Springer Verlag，2012．545－556．

［3］Connolly C．The determination of next best views［A］．Proceedings of the IEEE International Conference on Robotics and Automation［C］．Washington，DC，USA: IEEE，1985．432－435．

［4］Maver J，Bajcsy R．Occlusion as a guide for planning the next view［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，1993，15(5) : 417－432．

［5］Pito R．Solution to the next best view problem for automated surface acquisition［J］．IEEE Transactions on Pattern Analysis and Machine Intelligence，1999，21 (10) : 1016 －1030．

［6］Banta J E，Wong L M，Dumont C，et al．Next-best-view system for autonomous 3-D object reconstruction［J］．IEEE Transactions on Systems，Man，and Cybernetics，Part A: Systems and Humans，2000，30(5) : 589－598．

［7］Chen S Y，Li Y F．Automatic sensor placement for modelbased robot vision［J］．IEEE Transactions on Systems，Man，and Cybernetics，Part B: Cybernetics，2004，34(1) : 393－408．

［8］Li Y F，Liu Z G．Information entropy-based viewpoint planning for 3-D object reconstruction［J］．IEEE Transactions on Robotics，2005，21(3) : 324－337．

［9］Scott W R．Model-based view planning［J］．Machine Vision and Applications，2009，20(1) : 47－69．

［10］Vasquez-Gomez J I，Sucar L E，Murrieta-Cid R．Hierarchical ray tracing for fast volumetric next-best-view plan-ning［A］．Proceedings of the International Conference on Computer and Robot Vision［C］．Washington，DC，USA: IEEE，2013．181－187．

［11］Zhang S，Gao F，Kong L．A self-occlusion detection approach based on range image of vision object［J］．ICIC Express Letters，2011，5(6) : 2041－2046．

［12］Zhang S，Yan S．Depth estimation and occlusion boundary recovery from a single outdoor image［J］．Optical Engineering，2012，51(8) : 087003: 1－11．

［13］Zhang S，Liu J．A self-occlusion detection approach based on depth image using SVM［J］．International Journal of Advanced Robotic Systems，2012，9(12) : 230: 1－8．

张世辉男，1973年生于河北赞皇，燕山大学信息科学与工程学院教授、博士生导师．主要研究方向为视觉信息处理、模式识别，人工智能．

E-mail: sshhzz@ ysu．edu．cn

张钰程男，1990年生于河北廊坊，燕山大学硕士研究生．主要研究方向为计算机视觉和模式识别．

E-mail: zycysucv@ gmail．com

Determining Next Best View Based on Occlusion Information of a Single Depth Image

ZHANG Shi-hui1，2，ZHANG Yu-cheng1
(1．School of Information Science and Technology，Yanshan University，Qinhuangdao，Hebei 066004，China; 2．The Key Laboratory for Computer Virtual Technology and System Integration of Hebei Province，Qinhuangdao，Hebei 066004，China)

Abstract:How to determine camera＇s next best view based on current information is a challenging problem in visual field．A next best view approach was proposed based on the occlusion information of a single depth image．Firstly，to establish the model for occlusion region external surface，the quadrilateral meshes for occlusion region external surface were obtained according to the occlusion information of a depth image in initial view．Secondly，the model for next best view was constructed by considering both the visible quadrangle and the loss information in next view．Finally，the next best view was achieved by solving the model with gradient descent method．Compared with the existing methods，the proposed approach does not limit the camera position on a fixed surface or need the priori knowledge of visual object．Experimental results demonstrate its feasibility and effectiveness．

Key words:next best view; depth image; occlusion information; external surface of occlusion region; gradient descent method

作者简介

基金项目:国家自然科学基金(No．61379065) ;河北省自然科学基金(No．F2014203119)

收稿日期:2014-08-08;修回日期: 2014-11-21;责任编辑:马兰英

DOI:电子学报URL: http: / /www．ejournal．org．cn10．3969/j．issn．0372-2112．2016．02．028

中图分类号:TP391

文献标识码:A

文章编号:0372-2112 (2016) 02-0445-08