面向增强现实的在线视频阴影跟踪检测算法

孔维斌

（四川大学视觉合成图形图像技术国防重点学科实验室，成都　610065)

面向增强现实的在线视频阴影跟踪检测算法

孔维斌

（四川大学视觉合成图形图像技术国防重点学科实验室，成都610065)

0　引言

增强现实（AR，Augmented Reality），是利用软硬件技术的辅助，把计算机生成的虚拟物体无缝逼真地融合到真实的场景中去。随着科技进步，尤其是移动设备的快速发展，增强现实越来越受到广大研究者和企业所关注，其应用领域广泛，如教育、游戏、遗址修复、会展等。

增强现实中的核心问题是如何保持几何一致性、光影一致性[1]和运动一致性。增强现实领域，不仅要求融合的物体自身光影效果表观看起来和在线视频中真实场景看起来和谐一致，高级的增强现实要求考虑虚拟的物体和真实场景中的阴影相互投射影响。然而，目前的大多数研究者都忽略了阴影交互问题。如图1所示，缺少虚实之间的光影相互影响会严重导致融合的不真实，无法达到逼真的效果。因此，越来越多的研究者开始从事阴影交互的研究[2-4]。

模拟虚实之间的阴影交互，第一步需要检测视频真实场景中的阴影。在监控系统中，许多研究者注重视频中人物或者车辆的阴影检测[5-7]。这些方法主要是针对基于固定视点下的视频。在监控系统中固定视点下的阴影检测通常对检测的细节准确性不如增强现实领域要求高。另外，许多现有的方法也很难达到实时在线处理。增强现实领域的阴影检测具有特殊的要求，首先其要求每一帧中阴影必须要实时在线的被检测出来，否则将会严重影响阴影交互，导致整个AR系统的逼真性无法保证。其次，阴影交互对阴影边缘的检测精确性要求很高，每一帧内部和帧与帧之间都必须保持很好的连续性。比起固定摄像机下背景不变物体变化的物体阴影检测，动态视点下的阴影检测有独特的挑战。之前的一些研究者为了保持增强现实下的光影一致性，主要采取的方法是先进行光照估计，然后进行阴影生成模拟。有少部分的研究者进行了固定视点下室外场景实时在线的增强现实光影一致性的研究[8]。

图1　阴影交互对增强现实的影响

本文提出了一种原创的在线阴影检测算法框架。我们假设摄像机的移动是连续的，把每一帧当前帧分为两部分处理：已跟踪区域（Tracked Region，TR）和新增区域（New Region，NR）。TR是可以根据前一帧的信息使用光流跟踪阴影边缘的区域。NR是由于摄像机移动新进入窗口的区域。对于不同的部分，我们采取了不同的处理。TR中使用RANSAC算法进行异常点的剔除，只跟踪准确的阴影边缘信息。对于NR，使用Meanshift算法进行预处理分割，然后进行图像中阴影边缘的检测，最后对误检测信息剔除，提取我们需要的准确信息获得最终的阴影边缘。

我们的算法比起之前的一些算法有明显的优点：第一，算法面向动态摄像机下的增强现实光影一致性问题的阴影检测处理。第二，本文使用跟踪和部分新检测结合，有效避免不必要的重复计算，从而提升了效率，能达到实时在线处理。第三，算法具有很好的稳定性，能适应室内或者室外场景。这些优势保证了本文算法能为增强现实光影一致性的保持做很好的预处理工作。

1　本文算法

如图2所示，在TR中鲁棒地跟踪已检测阴影边缘和在NR中检测新出现的阴影边缘是本文算法框架的核心两部分。

我们的跟踪过程主要是在每一帧对应的3D点云中进行。为了提高数据的可靠性，我们使用RANSAC[10]进行了主要平面（如地面）的拟合，从而去除了很多异常点。对NR，我们进行图像分割，然后进行边缘检测，根据局部连续性，剔除异常点。得到最后的阴影边缘，找到对应3D点加入到跟踪边缘点序列中。本文算法框架中需要对第一帧进行阴影边缘的交互初始化。

图2　算法流程图

对TR部分的阴影边缘的跟踪，我们充分结合了图像像素和对应的场景深度图信息。在我们的系统中，深度图是用RGB-D摄像机Bumblebee2[11]实时记录的，从而可以得到每一帧对应的3D点云。然而，由于软硬件设备的限制，点云信息难免包含很多噪声点，我们使用RANSAC进行边缘点提纯。

如图3，我们先对第一帧阴影边缘进行交互标出，并找到对应的3D点云，提纯后加入跟踪。

图3　阴影边缘初始化

由于稠密光流的计算耗时，所以我们使用传统的稀疏光流算法[12]计算帧间的光流变化情况，从而获得NR。算法选取N个特征点，N大小由我们指定。我们把每一个特征点的光流变化向量记为VOF（i）=（x，y），i= 1，…，N。摄像机移动的情况主要有以下几种情况：上下、左右、前后、旋转。由于帧间差异性较小，所以我们选取了所有特征点变化响亮的中位数Vmedian表示场景变化情况，并且计算摄像机旋转角度。从而获得旋转平移矩阵T：

用上一帧图像It-1变换矩阵相乘，得到两帧图像重叠区域：ηIt-1T。η是尺寸因子，不小于1，例如，当为2时，部门重叠区域会被认为是新增区域，这样的好处少量的重复计算保证新增阴影边缘连续性很好的保持。

为了减少不必要的计算，我们根据阴影边缘走势和光流向量分量来判断新增区域的进入方向。如果旋转角度很小的话，我们则认为其只进行了平移变换。

Meanshift是一种特征分析方法[13]，其基本思想是通过反复迭代搜索特征空间中样本点最密集的区域，搜索点沿着样本点密度增加的方向“漂移”到局部密度极大点。相比起传统的一些图像分割算法，均值漂移算法原理简单、迭代效率高。

Meanshift的核心两点是，密度估计（Density Estimation）和模点（mode）搜索。对于图像数据，因为其分布无固定模式，所以密度估计必须用非参数估计，选用的是具有平滑效果的核密度估计。通常，我们把一幅图像直观表示为一个具有p维矢量的二维网格，每个网格点代表一个像素。p=1时，表示这是灰度图像；p=3表示为彩色图像。网格所在的空间称为坐标空间，灰度、色彩、光谱信息所在的空间称为颜色空间。统一考虑图像的坐标信息和色彩信息，组成一个p+2维的向量x，这样每个图像像素就可以用向量X=（XS，Xr）来表示，其中：XS表示像素的位置坐标，Xr表示该像素的色彩特征。设mh（x）表示p+2维空间上的均值漂移迭代公式，其定义为：

式中：x表示被平滑像素点的像素值；xi（i=1，2，…，n）表示以被平滑点为中心，边长为 2hs（hs称为空域带宽）的正方形区域内的像素点的值，正方形区域内的所有像素点称为采样点；h为带宽；G（x）为核函数，常用的2种核函数为单位核函数和高斯核函数；w（xi）≥0，是每个采样点xi的权重值。

均值漂移算法的主要步骤如下：

步骤1：给定初始条件，包括一个初始像素点x，核函数 G（x），带宽h，每个采样点的权重w（xi）和容许误差 ε；步骤 2：根据式（2）计算像素点 x的mh（x）值；步骤 3：如果|mh（x）-x|＞ε，将mh（x）赋给x，并返回到步骤2。如果|mh（x）-x|＜ε，结束该像素点的迭代，顺序选取下一个像素点；步骤4：重复步骤（2）～步骤（3），直至整个图像遍历结束。

对于图像的分割包含图像平滑、合并相似区域。最后能得到不同的区域分块。得到大体的图像分割结果。

在我们分割了每一帧新增图像之后，我们进行了边缘检测，边缘检测算法，本文用了经典的Canny边缘检测算法。得到的阴影边缘难免因为分割的无语义性，导致很多是非阴影区域的边缘。所以我们必须进行阴影边缘点的提纯，去除不必要的误检测边缘。

在获得了图像中新阴影边缘对应的3D点信息之后，我们结合前一帧的边缘信息来获取最后我们需要的边缘点。在实验测试视频中，我们只追踪一条阴影边缘，我们把图像中每一个阴影点表示成一个向量：

其中，Gix和Giy是像素的梯度。覫i是梯度偏向角。Bi是像素的亮度值。Xi-1表示上一帧存储最有一个边缘点或者当前帧存储的最后一个边缘点。为了选取连续的阴影边缘点，消除误检测点，我们考虑了Xi和Xi-1边缘点的相似性和连续性两个主要特性，同时结合2D像素信息和对应的3D点云信息，估计函数如下：

其中，cos＜Xi-Xi-1＞是两个向量之间的分别减去均值向量来校正过的余弦相似度：

其中ρ是正则化因子。F2D（i，i-1）估计的是图像像素点之间的相似度与连续性程度，F3D（i，i-1）估计的是对应3D空间中点之间的连续性。函数中的DE（i，i-1）和DE（Pi，P（i-1））分别表示2D图像中像素点和对应3D空间中的欧氏距离。

处理完当前帧所有阴影点，然后我们就把提取出来的点加入到跟踪序列中。

当我们处理新出现的帧时，很多阴影边缘信息已经被计算过。为了提升效率，我们根据光流信息的变化判断场景移动方向，我们不需要重复计算那些已经拍摄过的场景的阴影边缘信息。

由于帧间差异性很小，所以我们设置了帧步长S和光流向量的分量阈值β来提高效率。由于帧间差异很小，我们可以每3帧或5帧计算场景新阴影，从而可以大幅度提高效率。如果光流向量某个分量小于β，我们则认为该方向上几乎没变化，无需计算该方向上的新阴影边缘。图4展示了新增区域边缘的检测过程。

图4　检测过程

2　实验结果

为了验证算法中利用3D信息进行跟踪边缘信息的有效性和准确性，我们把实验结果和文献L.Bao[14]只基于2D像素信息的最新的光流跟踪算法进行了对比。图5展示了对比结果。如图所示，文献[14]的方法在紧邻的两帧之间跟踪表现很好。但在长视频序列中，随着帧数的增加，累积跟踪误差也越来越大。相比而言，本文算法不尽在紧邻帧间的跟踪能取得同样的效果，在长序列中也能进行稳定的跟踪。

通过实验我们发现，主要有三个参数因子影响我们算法的高效性：帧步长S，光流分量阈值β，和光流跟踪的特征点选取数量N。为了分析各参数的影响，我们固定其中两个变量，从而改变某变量，得出实验结果如表1所示。针对分辨率为400x300的视频，当设置S=1，N=100，β=4时，处理平均帧率能达到24 fps。视频分辨率更小时，帧率能高达满足实时增强现实的要求。我们的运行环境是：Intel Core i5-4440,CPU 3.1GHz,RAM 8.00GB,GPU NVIDIA GeForce GTX750.一般而言，算法效率与图像尺寸及分辨率有关，但是每帧新出现区域的大小是主要影响因素。

由于场景深度图数据具有噪声信息，尽管我们采取了提纯措施，仍然无法避免的会有一些错误。如图6所示，在实验视频的第30帧，跟踪的阴影边缘与真实边缘约有4像素的漂移。

表1　不同分辨率视频不同参数下帧率对比

在检测了阴影边缘之后，我们就可以利用光照估计的信息，沿阴影边缘逆向生成阴影投射区域。从而可以放置虚拟物体，渲染之后，进行虚实融合了。为了展示阴影交互效果，我们把虚拟的球体置于场景不同地方，实验结果图如图7所示。

图5　不同分辨率视频跟踪稳定性对比

图6　由于设备缺陷导致的漂移现象

图7　增强现实示例图

3　结语

本文提出了一种原创的针对室外场景实时视频的阴影检测算法框架。我们充分利用了2D和3D信息。跟踪过程比只基于图像信息的跟踪更加稳定高效。用高效的均值漂移算法进行图像分割，为阴影边缘的检测提高了准确性，很好地避免了直接进行边缘检测的大量误检测，也避免了大量的人工交互。最后我们的提纯算法边缘点筛选继续对检测的阴影边缘进行处理。算法优化计算从而大大提升了效率，满足增强现实的实时性需求。

虽然我们的方法取得了不错的实验效果，但是仍然有一些不足和限制需要我们继续研究解决。一方面，我们目前能处理的阴影不够复杂，尤其针对软影的处理难度较大。另一方面，我们的算法暂时不能处理场景中各种物体移动阴影变换剧烈的情况，我们主要是针对摄像机移动，光照变化不大静态场景的情况。当光照变化强烈的时候，我们需要探索一些实时光照估计的算法，诸如文献[15]提到的方法。当光照强度和方向均变化时，问题的挑战性会加大。场景的光照必须很好地考虑到，这是我们未来的工作方向。

[1]G.Xing,X.Zhou,Y.Liu,X.Qin,Q.Peng,Online Illumination Estimation of Outdoor Scenes Based on Videos Containing no Shadow Area,Science China Information Sciences,56(3)(2013)1-11.doi:10.1007/s11432-012-4780-7.

[2]Q.Zhao.A Survey on Virtual Reality,Science in China Series F:Information Sciences，52(3)(2009)348-400.

[3]K.Jacobs,C.Loscos,Classification of Illumination Methods for Mixed Reality,in:Computer Graphics Forum,Vol.25,Wiley Online Library,2006,pp.29–51.

[4]G.Xing,X.Zhou,Q.Peng,Y.Liu,X.Qin,Lighting Simulation of Augmented Outdoor Scene Based on a Legacy Photograph,in:Computer Graphics Forum,Vol.32,Wiley Online Library,2013,pp.101-110.

[5]J.Dai,D.Han,Region-Based Moving Shadow Detection Using Affinity Propagation.

[6]E.Bullkich,I.Ilan,Y.Moshe,Y.Hel-Or,H.Hel-Or,Moving Shadow Detection by Nonlinear Tone-Mapping,in:Systems,Signals and Image Processing(IWSSIP),2012 19th International Conference on,IEEE,2012,pp.146-149.

[7]S.Nadimi,B.Bhanu,Physical Models for Moving Shadow and Object Detection in Video,Pattern Analysis and Machine Intelligence, IEEE Transactions on，26(8)(2004)1079-1087.

[8]B.V.Lu,T.Kakuta,R.Kawakami,T.Oishi,K.Ikeuchi,Foreground and Shadow Occlusion Handling for Outdoor Augmented Reality, in:Mixed and Augmented Reality(ISMAR),2010 9th IEEE International Symposium on,IEEE,2010,pp.109-118.

[9]C.B.Madsen,B.B.Lal,Estimating Outdoor Illumination Conditions Based on Detection of Dynamic Shadows,in:Computer Vision, Imaging and Computer Graphics.Theory and Applications,Springer,2013,pp.33-52.

[10]R.Raguram,J.-M.Frahm,M.Pollefeys,A Comparative Analysis of Ransac Techniques Leading to Adaptive Real-Time Random Sample Consensus,in:Computer Vision-ECCV 2008,Springer,2008,pp.500-513.

[11]http://www.ptgrey.com.

[12]J.Bouguet,Pyramidal Implementation of the Lucas-Kanade Feature Tracker:Description of the Algorithm,Opencv Documenttation,Santa Clara,CA:Intel Corp.,Microprocessor Research Labs.

[13]Comaniciu D,Meer P.Mean shift:A Robust Approach Toward Feature Space Analysis[J].Pattern Analysis and Machine Intelligence, IEEE Transactions on,2002,24(5):603-619.

[14]L.Bao,Q.Yang,H.Jin,Fast Edge-Preserving Patchmatch for Large Displacement Optical Flow,in:Computer Vision and Pattern Recognition(CVPR),2014 IEEE Conference on,IEEE,2014,pp.3534-3541.

[15]Y.Liu,X.Granier,Online Tracking of Outdoor Lighting Variations for Augmented Reality with Moving Cameras,Visualization and Computer Graphics,IEEE Transactions on，18(4)(2012)：573-580.

Augmented Reality;Shadow Detection;Meanshift;Shadow Interaction

Online Shadow Tracking and Detection Framework for Augmented Reality

KONG Wei-bin
（National Key Laboratory of Fundamental Science on Synthetic Vision,Sichuan University,Chengdu 610065）

1007-1423（2016）02-0062-06

10.3969/j.issn.1007-1423.2016.02.015

孔维斌（1991-），男，云南曲靖人，硕士研究生，研究方向为计算机视觉和图形图像技术

2015-12-02

2015-12-29

在增强现实领域，光影一致性的保持十分重要，之前的研究者们主要集中在光照估计然后模拟生成阴影。大多需要知道物体的投射物体的具体形状，很少考虑真实场景阴影和虚拟物体之间的光影相互影响。提出一种原创的面向增强现实的阴影检测算法。首先利用Meanshift算法进行图像预分割，检测阴影边缘。然后有效结合2D和3D信息，基于局部一致性进行误检测去除，最后得到理想的阴影边缘，从而可以逆向生成阴影区域，更好地模拟阴影交互。实验结果证明算法的有效性。

增强现实；阴影检测；Meanshift；阴影交互

In Augmented Reality(AR),keeping the illumination consistency is very important.Most previous AR techniques about shadow processing mainly focus on illumination estimation and then generate the shadow of the virtual objects.Mostly,the shadow interaction between the virtual objects and the real scene has been ignored.Proposes a novel shadow detection algorithm for AR.Firstly,every frame will be segmented with mean-shift method,and then the shadow edges will be detected.The method based on local consistency refines the shadow edges combining the 2D information and 3D information effectively.Then,the virtual shadow can be generated from the shadow edges reverse.Experiments demonstrate the stability and effectiveness of our method.