帧间一致性的八叉树可视外壳三维重建

李 霞

（中国石油山东销售公司 调度运输处，山东 济南 250011）

帧间一致性的八叉树可视外壳三维重建

李 霞

（中国石油山东销售公司 调度运输处，山东 济南 250011）

针对动态物体三维重建计算量大的问题，提出利用帧间一致性的动态物体可视外壳重建算法。算法采用八叉树的存储结构，利用帧间一致性，判断前一帧重建的可视外壳边界体素的邻域体素状态，生成后续帧的可视外壳。相比于每次从八叉树的根节点开始判断的方法，帧间一致性算法减少了判断次数，提高了算法效率。试验结果表明，该算法有效地减少了计算量。

三维重建；可视外壳；帧间一致性；八叉树

基于视频图像的三维重建是虚拟现实、计算机视觉等领域研究的重要内容。可视外壳是由空间物体的所有已知侧影轮廓决定的空间包络，是动态物体实时三维重建的一种有效方法［1－3］。基于体素的重建算法稳定，能够重建拓扑结构复杂的物体，但由于所使用的元素是离散的体素单元，所以只能得到近似的结果。为了获得动态物体的高精度三维模型，需要多个相机和精细的体系，导致计算量大。法国INRIA的GrImage系统使用8台双核PC机组成机群，在640×480的相机分辨率下，重建速度达到30 fps［4］。基于传统八叉树可视外壳算法的动态物体重建过程中，每一帧都是从八叉树的根结点开始计算，算法计算量较大。三维重建过程中，在连续的两帧之间重建的物体相似程度高，因此，可利用帧间的连贯性来减少算法在每一帧中的计算量，以提高算法的效率。

1 基于八叉树的体素可视外壳

可视外壳算法总体上分为两大类：基于体的方法与基于面的方法［5］。基于体的可视外壳方法能够重建具有复杂拓扑结构的物体，算法稳定。基于面的可视外壳方法是直接对可视锥体求交，可直接得到物体的三维网格，但这种方法需要复杂的几何计算，存在数值不稳定的问题。本文采用体素方法重建三维模型。

1.1 体素状态判断

假设体素为V，构成体素的8个顶点表示为Pi（i＝0…7），那么对于顶点Pi在第k个相机里的状态定义为Sk（Pi），计算式如下：

其值为0时表示顶点在物体外，值为1表示顶点在物体内。

当计算体素在相机k中每个顶点的状态后，接着判断体素在相机k里的状态Sk（V），最后可由体素在每个相机中的状态计算体素与物体间的关系S（V），S（V）为1表示体素位于物体内，－1表示体素落在物体外，0表示体素在物体表面上。计算方法如下：

1.2 八叉树算法

基于体素的算法主要采用空间完全剖分和八叉树两种算法实现。前面一种方法首先将物体所在空间完全划分成等大小的体素，重建时需要判断每个体素的状态，最后用边界体素表示物体。

八叉树算法是：首先将整个建模空间作为一个体素V，判断体素状态，若体素在物体边界上（即S（V）＝0），需将体素八等分，再对每个体素重复上述过程，直到体素分解到一定精度为止。如图1所示，（a）为体素分解的图形示意，（b）为相应的八叉树结构，树中节点存在三种情况：黑色节点（值为1）表示对应体素完全落在物体上，白色节点（值为－1）表示对应体素完全落在物体外，灰色节点（值为0）表示体素部分在物体内，部分在物体外。

图1 简单的两层八叉树

完全剖分法数据结构简单，但需要逐个判断体素，计算消耗较大。八叉树法数据结构复杂，只有当体素位于物体边界上才进行分解，因此总的计算消耗明显低于完全剖分法。

对于连续运动物体，现有方法都是每帧采用八叉树算法重建物体，当重建模型精度要求高时，需要更多相机，这样就难以达到实时重建。通过试验可得，如果连续帧间的物体空间位置变化较小时，那么八叉树中节点状态发生变化的个数也较少。为此，连续重建多帧中的物体时，只需要根据前帧中边界体素的状态进行判断，从而减少从根节点开始判断的时间。

2 帧间一致性体素处理

对于一般的低速运动物体而言，连续帧具有一定相关性。这是由于在实时系统中连续帧间隔时间很短，在此短时间内物体移动的范围是有限，这使得前一帧重建的物体与当前帧重建的物体具有较高的重叠率。因此可以从前一帧三维重建的可视外壳边界体素出发，根据物体运动情况，判定下一帧物体的边界体素。

2.1 数据结构

当一帧重建后，用边界体素（叶子节点且S（V）＝0）表示物体模型，后继帧中的边界体素由前帧体素计算。需要计算的前帧中体素包括边界体素及八叉树中的非边界叶子结点体素，分别用两个队列（bQue和lQue）存放这两类体素。当重建第一帧的模型时，采用基本八叉树算法从根节点开始建立八叉树，同时将边界体素及叶子节点分别存放到两个队列中。八叉树和队列中的节点采用同样的数据结构，如图2所示，Data数据域存放体素几何数据，pParent和pSons［］分别存放父亲和孩子节点指针，Satus＝S（V）。

图2 体素数据结构

2.2 队列处理

后继帧中物体的边界体素将由前帧中的b Que和l Que中的体素计算而来，对各自队列中的体素进行不同的处理。

若体素V为l Que队列中的体素，经当前帧测试后有以下3种情况进行处理：

（1）体素状态S（V）不发生变化，V 继续在l Que队列中，如图3中的节点0、5、6；

（2）体素状态S（V）值为－1和1互换，V 继续在lQue队列中，如图3中的节点3、4；

（3）体素状态S（V）值由－1或1变为0，V 从lQue队列中删除，如图3中的节点1；

注意：若不在l Que队列体素V状态S（V）值由0变为－1或1时，V 需添加到lQue队列中，如图3中的节点2。

若体素V（S（V）＝0）为b Que队列中的体素，经当前帧测试后有以下两种情况进行处理：

（1）体素状态S（V）不发生变化，V 继续在b Que队列中；

（2）体素状态S（V）值从0变为－1或1，V 从b Que队列中删除，如图3中的节点23、26、70。

图3 连续帧间的八叉树的局部最低3层变化

2.3 分裂与合并

l Que中体素状态值改为0时，需要分解体素，即需要进行分裂处理。b Que中体素状态值改为非0时，需要合并兄弟体素，即需要进行合并处理。

分裂处理：在删除lQue中的体素时，此体素需要分裂从而产生更细精度的体素，这些体素将需要分别插入到两个队列中。如图4中的节点1的S（V）值由－1变为0时，体素将分裂为八个子体素，若体素达到最高精度时，那么节点10和13将插入到b Que中，其他子节点插入到l Que中。

合并处理：在删除bQue中的体素时，当兄弟节点的S（V）值都不为0且相等时，需要将该体素的兄弟体素全从2个队列中删除，并修改父亲节点的状态，并需要进一步判断兄弟节点的状态。如图4中的节点70的S（V）值由0变为－1时，此时其兄弟体素状态全为－1，需要合并兄弟节点，即修改父亲节点7的状态值为－1，并将节点7添加到l Que中，同时从b Que中删除节点70，从l Que中删除它的兄弟节点。

3 试验结果与分析

可用C＋＋语言在可视外壳仿真计算平台上实现具有帧间一致性的可视外壳生成算法［6］，仿真试验的硬件环境为：主频为2.80GHZ的Pentium（R）Dual－Core E6300双核 CPU、NVIDIA GTX260显卡、2.00GB内存；软件环境为：Windows XP、VC6.0以及三维图形标准库Open GL。利用仿真试验平台提供的接口开发的帧间一致性可视外壳仿真程序运行效果如图4所示，图中左上窗口为模拟可视外壳建模的虚拟环境，左下窗口显示初始状态下获取的相机图像及其侧影轮廓图，右下窗口为模拟相机获取到的图像，右上窗口显示重建的模型（体素采用线框模式绘制）。

图4 仿真平台效果图

仿真试验使用兔子三维模型，获取不同视点的五幅相机图像，分别用基本八叉树和帧间一致性方法重建物体几何模型。采用的体素剖分精度分别为64×64×64、128×128×128、256×256×256，相机图像分辨率分别为512×512，表1分别给出了不同情况下两种算法的运行时间和加速比。

表1 八叉树传统算法与帧间一致性算法时间性能

4 结 论

在已有的基于八叉树动态物体可视外壳算法基础上，提出了一种基于帧间一致性的动态物体可视外壳算法。利用八叉树及双队列结构，通过计算前帧中体素的状态来快速计算当前帧中的边界体素，从而减少体素计算数，试验结果表明，在物体运动速度较小的情况下，算法计算效率得到有效提高，从而在较小计算资源的条件下可实时重建物体三维模型。

［1］ 苏焕焕.安全多面体可视外壳及应用研究［D］.东营：中国石油大学计算机与通信工程学院，2010.

［2］ BO P，GANG Q.Online gesture spotting from visual hull data［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，2011，33（6）：1175－1188.

［3］ LAURENTINI A.The visual hull concept for silhouette based image understanding［J］.IEEE Transactions on Pattern Analysis and Machine Intelligence，1994，16（2）：150－162.

［4］ FRANCO J，BOYER E C，BOYER E，et al.A distributed approach for real time 3D modeling：Proc of the 2004 Conference on Computer Vision and Pattern Recognition［C］.Washington：IEEE Computer Society，2004：31－38.

［5］ 李涛.基于图像的建模技术研究［D］.长沙：国防科学技术大学机电工程与自动化学院，2007.

［6］ 陈国军，牛玉美，申宝明.多视图像的三维重建并行计算仿真平台［J］.系统仿真学报，2012，24（1）：85－88.

TP391.9 < class="emphasis_bold">［文献标识码］A［文章编号］

1673－5935（2012）01－0024－03

2011－12－29

中央高校基本科研业务费专项资金资助项目（09CX04034A）；国家“973”项目（2009CB320805）

李 霞（1983－），女，辽宁灯塔人，中国石油山东销售公司调度运输处助理工程师，主要从事图形图像处理研究。

［责任编辑］ 彭丽娟