基于降维和筛选的立体图快速生成算法

刘晓平， 习雅思

（合肥工业大学计算机与信息学院VCC研究室，安徽 合肥 230009）

三维立体图是一种利用人眼的双目视觉特性巧妙设计的二维图像，其纹理在水平方向上保持一定的重复性，并根据需要表现的三维模型的形状做必要的变化。图像由众多相关点组成，每组相关点都能使人的两个眼睛在裸眼状态下聚焦到图像后方一个预先设计的深度，从而整幅图像构成一个完整的三维模型。不同于通常的具有透视或者光照和阴影效果的二维图像，三维立体图从人眼的双目立体成像原理出发，充分利用了人的双眼对空间深度信息的感知，从而能够给人一种更加真实的立体沉浸感。

1960年，Julesz发现嵌有立体信息的两幅图像，用双眼可以感知到深度信息[1]，Tyler此基础上将两幅随机点立体图像合并到一个单幅图像中，得到了所谓的单幅随机点立体图像(Single image random dot stereogram)，即自动立体图(Autostereograms)[2-3]。

自从Tyler[3]提出基本立体图生成原理以来，众多学者对立体图的重影(Echo)[4-5]、隐藏面消除(HSR)[4,6]、随机纹理[7]及立体图的分层效应(Stratified character)[8]等问题进行了深入研究。然而，基本立体图生成算法，即用射线和三维模型求交的方式生成立体图的方法，对任意三维模型生成立体图，计算量较大，生成速度缓慢，对此国内外学者没有进行必要的改进。本文提出了一种基于降维和筛选的快速立体图生成方法，该方法通过降维和筛选大幅度减少计算量，可以在不影响立体图效果的情况下获得较快的生成速度。

1 立体图基本原理

1.1 立体图成像原理

三维立体图是由众多约束点[4]组成的，所谓的约束点就是一对相关的像素点，其颜色值、垂直坐标相同，而水平坐标不同。图1是立体图生成系统的顶视图，Aleft和Aright是成像平面（立体图）上的一对约束点，由于这两点间距小于人两眼间距，因此左眼和右眼分别通过这两点往成像平面后面看去，两眼的视线会聚焦于成像平面后面的一点A。立体图上存在众多这样的约束点，不同的约束点位置和间距不同，如图2所示，从而人眼聚焦点的位置和远近也不同，众多的聚焦点组成了一个位于成像平面后面的虚拟的三维模型。由于人的两眼是用同样的原理，即双目立体成像来感知物体远近的，因而立体图成像原理完全符合人眼视觉特性，通过立体图看到的三维模型具有强烈的立体沉浸感。

1.2 立体图生成原理

同成像原理——由约束点聚焦到模型——相反，生成立体图是由模型计算约束点坐标，然后复制约束点颜色值的过程[7]。下面以最简单的列优先从左到右的扫描顺序为例来说明。

图 1 立体图原理

图 2 约束点的颜色复制

按照从左到右的扫描顺序，当前扫描点以及该点右侧所有的点的颜色是未知的，而当前扫描点左侧所有点的颜色是已知的，初始纹理图——立体图中将重复出现的纹理——紧靠在立体图的左侧。如图1所示，若当前扫描点是Bright，从右眼到Bright点做一条射线并与模型或背景平面相交于B点，B点和左眼的连线交成像平面于Bleft点，该点就是Bright的约束点，将Bleft点的颜色值复制给Bright点。对于图中A点的情形，Aright的约束点Aleft不在立体图范围内，而位于其左侧的初始纹理图中，这时，将初始纹理图中Aleft处的颜色复制到Aright点。对立体图中所有像素点按照列优先的顺序从下到上、从左到右依次扫描，并使用上述方法计算约束点坐标、复制约束点颜色值，就得到了一幅立体图。

2 基于降维和筛选的加速算法

基于求交测试的方法是通过人眼与成像平面像素点的连线和模型求交，并反求约束点来生成立体图的，由于每生成一个像素点，都要对模型中所有三角面片进行求交测试，因而该方法存在计算速度慢的致命缺点。为此，本文提出一种基于降维和筛选的立体图快速生成算法。算法描述如下：

预处理 对模型进行降维；

For(按序扫描的立体图中每列像素点){

筛选1：对该列进行筛选操作得到三角面片集合U1；

该算法的关键在于降维预处理和对三角面片的筛选两项操作，下面对其分别进行介绍。

2.1 降维预处理

如图3，计算任一像素点I1的颜色值，用右眼P 和I1的连线同模型中的每个三角面片 △ V0V1V2求交点。空间三角形△ V0V1V2、射线 PI1的表示及二者交点的参数计算分别如下

这里需要P、I1、V0、V1、V2五个线性无关的三维向量，数据维数是15。

本文算法的降维预处理是指在进行真正的三维求交测试之前，将模型中每个空间三角形 △ V0V1V2映射为成像平面上的平面三角形 △，继而将△ V0′V1′V2′用其包围盒的4 个 参数(xmin, ymin, xmax, ymax)来表示，同时将射线1PI 用成像平面上的二维点I1'来表示。即

如图3，P 点和空间三角形△ V0V1V2顶点的三条连线分别交成像平面于、、三点，得到平面三角形△。对I1点只取其在成像平 面上的二维坐标，得到I1'点。由此，数据的维数从原先的15 维降到了6 维，其目的在于降低下面的筛选操作的计算复杂度。

2.2 筛选操作

图3 降维预处理

相比式(3)，式(4)只需四次大小比较，计算量远小于前者，因而筛选操作本身的耗时远小于三维求交。同时，由于符合筛选条件的三角形只是模型中所有三角形的一小部分，筛选出的集合的元素个数远小于筛选前的三角形个数，因而，真正进行的三维求交的计算次数大幅度降低。

3 实验结果与分析

图4 和图5 分别是一个三维模型和对该模型应用本文算法生成的三维立体图，由图5 可见其三维效果良好。使用加速算法，计算得到的约束点坐标和传统算法是相同的，并不影响最终的立体图效果。

图4 “人头”模型

使用多个三维模型，按照1000×800 的分辨率进行多次实验，平均耗时数据如表1 所示。从中可见，当模型的三角面片数较多时，用本文算法生成同样分辨率的立体图，耗时比基本算法显著减少（表中前两列）；当模型的三角面片较少时，加速比较低（第3～5 列）；而当模型的三角面片非常少时，则可能出现本文算法的耗时略大于基本算法的情况（最后一列）。

图5 “人头”立体图

本文算法之所以能够对立体图生成过程进行加速，原因在于：在进行传统的空间射线和三角形求交运算之前，进行了筛选操作，使得参与求交运算的空间三角形数目显著减少；同时，筛选操作本身只需要进行四次标量的大小比较，其计算量远小于空间射线和三角形求交运算。由于模型中的三角面片不可能是均匀分布的，不同的模型中的三角面片的密度也不相同，因此本文算法的加速比同模型的三角面片数目没有严格的比例关系，而只有概率意义上的趋势 ——三维模型中包含的三角面片越多，加速效果越显著——这一点从表1 中可以看出。当模型中的三角面片非常少时，筛选前和筛选后的参与求交运算的三角面片数目相差不多，二者的求交运算时间差别不大，但本文算法还需要进行降维预处理，所以，有可能本文算法的耗时反而略大于基本算法，表1 最后一列使用单个三角形的极端情况说明了这一点。

表1 加速效果

4 总结与展望

三维立体图利用人眼的双目立体成像原理，在裸眼观看的情况下，使用单幅平面图像给观看者带来强烈的立体沉浸感，是一种独特的可视化手段。本文针对基于求交测试的立体图生成过程中的速度慢的问题，提出了一种基于降维和筛选的快速算法，在不影响立体图效果的情况下，显著提高了立体图的生成速度，同时分析了模型中三角面片数目对加速效果的影响。如何根据模型中三角面片的数目和分布情况，确定更加灵活的像素点扫描顺序和筛选策略，使得筛选得到的集合最小，是可以进一步开展的工作。

[1] Julesz B, Miller J E. Automatic stereoscopic presentation of functions of two variables [J]. Bell System Technical, 1962, 41： 663-676.

[2] Tyler C W, Chang J J. Visual echoes： the perception in repetition in random patterns [J]. Vision Research, 1977, 17： 109-116.

[3] Tyler C W, Clarke M B. The autostereogram [J]. SPIE Stereoscopic Displays and Applications, 1990, 1258： 182-196.

[4] Thimbleby H W, Inglis S, Witten I H. Displaying 3D images： algorithms for single-image random-dot stereograms [J]. Computer, 1994, 27(10)： 38-48.

[5] Mark S K Lau, Kwong C P. Analysis of echoes in single-image random-dot stereograms [C]//IEEE International Conference on Acoustics Speech and Signal Proceedings, 2001： 1677-1680.

[6] Minh S T, Fazekas K, Gschwindt A. The presentation of three-dimensional objects with single image stereogram [C]//IEEE Transactions on Instrumentation and Measurement, 2002, 51(5)： 955-961.

[7] Gonzalez H J, Cernuschi-Frias B. Generation of single image stereograms based on stochastic textures [C]//International Conference on Image Processing Proceedings, 1996： 153-156.

[8] JACQUES NINIO. The science and craft of autostereograms [J]. Spatial Vision, 2007, 21 (1-2)： 185-200.