一种计算Visual Hull的方法

计算Visual Hull的方法:

A Robust and Accurate Method for Visual Hull Computation [Song Peng 2009]

计算3D bounding box

仅从一组轮廓和投影矩阵计算3D bounding box

可以从每个轮廓的2Dbounding box考虑,使用4个变量

假设有N张图计算3D bounding box,

是第i张图的投影矩阵, 表示其2D边框。透视投影等式如下:

其中,

由于图像i的轮廓必须在其2D边框内,因此有以下四个不等式:

因此需要求出4N个线性不等式的x,y,z的最大值和最小值。使用遗传算法解决这个问题。每个个体是一个3D点(x,y,z)。如果希望计算x的最大值最小值,则相应的目标函数为.适应函数等于目标函数。算法如下:

产生一个满足4N个不等式的初始群体,如果知道目标的大致距离,该步骤会简单很多。
根据其适应性函数选择个体
个体与变异交叉,如果产生了不满足4N不等式的个体,则丢弃
保存此次产生最优的个体。如果最大允许生成数未达到,则转至步骤2;else exit。

建立Visual Hull的八叉树

从Silhouette建立:递归细分,投影测试

从bounding box开始,将等值面上的cube分成八个孩子,迭代。

等值面函数与Visual Hull的表面相关

对于一个给定的3D点v,等值面函数定义为:

Di是对轮廓i边缘的倒角距离变换CDT,负内,正外。

Projection test方法评估一个给定的voxel:

计算该voxel的8个顶点的等值面函数。

如果8个顶点都在visual hull的外部。

投影到所有图像,如果在一幅图像上voxel的投影都在silhouette内部,则类型为in,否则为on。

当8个顶点都在visual hull内部时。

将voxel投影到所有图像上,如果所有图像上voxel的投影都在silhouette内部,则类型为in,否则为on。

当部分顶点在visual hull内部时,类型为on。

事实上,可以仅通过判断voxel的投影与silhouette的相对位置来判断一个voxel的类型。这里使用的是8个顶点的等值面函数来减少计算时间。当部分顶点在visual hull内部时,不需要计算立方体的投影即可判定其类型为on。另一方面,在marching cubes算法中,也需要等值面函数的值。

文中Projection test方法的实现有两个步骤:
计算一个voxel在所有图像上的投影(not esay)

文中方法:将8个顶点投影到图像上,然后计算8个点的投影的凸包(convex hull)。凸包与cube的投影相同

文中证明:一个立方的六个面将3D空间划分成27个半空间:26个外部,一个内部。

从外部的26个半空间观察该立方体的轮廓,可以分为三种情况:1个、2个、3个可见面。因此,该立方的投影与8个顶点的投影的凸包相同。

计算一组给定点的凸包使用的方法是gift wrapping 算法,时间复杂度是O(nh)。N是点的数目,h是凸包上的点数。因此,这里 gift wrapping算法如下:

判断立方体的投影与silhouette的相对位置

如果多边形内所有像素都在目标区域内部,则多边形在silhouette内部;

如果多边形内所有像素都在目标区域外部,则多边形在silhouette外部;

如果部分像素在目标区域内,则多边形与silhouette相交。

使用marching cubes算法计算visual hull

在八叉树重建后,使用marching cubes算法提取visual hull表面。

Voxel占用一个叶节点,使用等值面函数值将其8个顶点编码成8个值。然后做一个距离变换,等值面函数值可以表示到visual hull表面的3D距离:负则在内,正则在外。然后用这些值在于给查找表上去索引,该查找表示预先定义的,定义了voxel内部的表面三角形,将形成最终visual hull mesh的一部分。

孤芳自赏,不必捧场。
分享