一种计算机制全息图快速运算算法

陈慧蓉，付胜豪，王元庆，范科峰

1.南京大学 电子科学与工程学院，南京 210093

2.芜湖职业技术学院 电气工程系，安徽 芜湖 241006

3.中国电子技术标准化研究所，北京 100007

一种计算机制全息图快速运算算法

陈慧蓉1，2，付胜豪1，王元庆1，范科峰3

1.南京大学 电子科学与工程学院，南京 210093

2.芜湖职业技术学院 电气工程系，安徽 芜湖 241006

3.中国电子技术标准化研究所，北京 100007

1 引言

在三维立体显示技术中，全息显示技术是最为理想和最有吸引力的。由于保留了物光波的全部振幅和相位信息，保留了所有的视差深度暗示，故观察全息三维像与现实中所观察的原物具有完全相同的视差效果。最早采用的全息成像方法是光全息[1]，但随着计算机技术以及光电子技术发展，全息技术进一步发展为计算全息[2-3]。计算机制全息图（Computer Generated Hologram，CGH）与光学全息图相比，具有更大灵活性和可操作性，可产生复杂甚至是虚拟物体全息图。将计算机生成的全息图加载于空间光调制器，可实现全息的动态显示。而要将全息三维显示技术实用化达到视频效果，就必须提高计算机制全息图的运算速度。

为了提高全息图计算速度，人们提出了一些快速算法[4-10]。文献[8]提出了一种全息图快速算法，利用三角函数变换，将全息图计算进行分解，分解为水平和垂直方向的独立分量的四则运算组合形式，使计算量大大减少。文献[9-10]提出S-LUT（Split Look-Up Tables，S-LUT）算法，在传统查表算法基础上优化为二步算法，去除大量冗余计算，提高计算速度。但到目前为止，全息图的计算速度仍达不到满意效果。本文根据全息图存在大量冗余信息这一特点，提出了去除大量冗余光波信息，仅计算视窗位置光波即子全息区域，来减少计算量。同时引进二步算法思想，以判断物点列与全息像素列的对应关系来代替逐点判断的低效，使全息图运算速度进一步提高。实验证明，本文所提的算法是有效的。

2 原理

2.1 计算机制全息图基本原理

全息图制作模型如图1所示，全息面记录场景中物体发射或反射光波与参考光波干涉后的光强，此光强包含物光波的相位信息。只有离散数据才能被计算机处理，故计算机制全息图的制作首先将空间物体看做是一系列自发光的空间物点集合，通过模拟物点集发出的光波在全息面处的叠加效果来制取全息图。因此首先要获取空间物点的集合。这一过程可以通过空间扫描仪对真实空间物体进行扫描，也可以借助OpenGL等软件构建虚拟空间物体，并通过读取深度缓冲及相应坐标变换获取。

图1 全息图制作模型图

假设空间物体由N个离散发光点组成，全息面上每一样点都可被每个物点发出的离散光线照亮，全息面上任一点复振幅可表示为：

式中λ为波长，φn为初相位，an为物点(xn，yn，zn)的衍射光波振幅，rn为物点到全息面上(x，y)点的距离。

将参考光与每一物点干涉的全息图进行叠加，即可得多个物点全息图，干涉光强在全息面上分布可表示为：

在完成计算全息平面上的光场分布后，进行计算全息编码，编码为全息图的透过率函数，量化和归一后形成一幅完整的计算机制全息图。

2.2 逐点计算的查表算法不断优化原理

将式（3）进行菲涅尔近似，可得：

对式（4）进一步处理可得：

竖直方向因子：

将式（6）、（7）带入式（5）得：

由式（6）可见，对于空间同一列的物点，H(x)相同，故可以将其作为公因子提出，式（8）可转化为：

其中Nj为j列物点数，k为物点列数。

由式（4）可见，逐点计算的全息图计算方法需计算每个物点到各全息面的距离，进而计算光强分布，大量时间耗在了平方、平方根以及余弦函数值计算，比如对于尺寸为X×Y的全息图，计算每个物点在全息面上的光强分布需要5XY次，n个物点的光强分布就需要5nXY次，可见计算量非常之庞大。

若事先离线制作相位因子查找表，将水平方向H(x)和竖直方向V(y)因子存储于查找表中，这样在线运行计算时，避免了平方和平方根计算，由式（8）可见，其计算量就会由5nXY次下降到2nXY次。但从式（8）的计算过程看出，出现大量有关水平方向和竖直方向冗余计算，因此相息图的计算算法可进一步改进。

对于空间同一列的物点，水平因子H(x)相同，故在计算空间某一列上物点在全息面的光强分布时，可将其作为公因子提取出来，不必每次都参与计算，可减少运算量。由式（9）可见，全息图的计算分成两步，第一步是计算各列的全息图光强分布，第二步是将各列物点在全息图上进行叠加，故这种查表优化算法也称为二步算法。此算法由于去除了一些冗余计算，使全息图的计算次数再次下降，计算量就会由2nXY次降为2nX+XY次。

2.3 去除冗余的子全息图计算原理

在传统全息显示中，为了重建三维空间中的物体，使用整个空间光调制器记录全息信息，重建光波范围远大于瞳孔大小，故存在大量的无用信息。由于全息图破碎为碎片后，全息图的每个碎片均能重建原始场景，故可采用去除冗余的子全息图方案，即用空间光调制器的一部分即子全息图编码全息信息，重建人眼位置（视窗）附近光波。

如图2所示，对于空间某一物点，视窗附近的光波是有效的，图中阴影部分，除此以外就是大量冗余光波。可见，采用去除大范围及大量冗余光波信息的子全息图计算方案可以大大减少计算量。对于子全息区域的确定，采用瞳孔跟踪技术[11]实时获取人眼位置信息也就是视窗位置，这样可保证视窗附近小区域光波正确性，准确确定出子全息图范围。

图2 空间冗余光波示意图

对于子全息图的计算，采用二步算法以加快全息图的运算速度。其算法原理为：以物点列和全息像素列为单位，通过空间物点列确定该物点列对应的全息像素列范围，由全息面上像素列确定对其有贡献的物点列集合，这样无需遍历空间所有物点来确定对全息图上各像素点有贡献的物点集合，避免逐点判断引起的低计算效率。设某一空间物点列对应的全息像素列为x列(x＜X)，其计算量降为查表逐点算法的x/X倍，采用二步算法的子全息图计算量再次下降，降为2nx+xY次，计算速度得到大幅度提高。

3 实验验证

采用图像处理单元（Graphic Processing Unit，GPU）处理技术的CUDA[12]并行计算，采用C++语言编写程序，在PC机（处理器为英特尔Core2Duo E5300，内存2 GB，英伟达GT240显卡；win7操作系统，vs2010编译环境，CUDA4.0通用开发包）上进行实验，分别用三种方案进行计算，即式（8）的查表逐点计算，式（9）的二步算法计算，本文所提的去除冗余光波的子全息图查表优化算法计算。首先研究全息图尺寸固定，物点数变化时，进行三种算法的实验观察。全息图尺寸为1 024点×1 024点，物点数分别为100、1 000、3 000、5 000、65 535点，实验结果如图3所示。

图3 物点数变化时计算时间比较

可见，随着物点数的增加，加速越大，当物点数在5 000点时，去除冗余的子全息图查表优化算法与二步算法计算速度比在2倍左右，但当物点数增加到60 000点时，其速度比稳定在10倍左右。

接下来研究物点数固定，全息图尺寸变化时，三种算法的实验观察。取65 536个空间物点，实验结果如图4所示。对于采用查表逐点算法计算全息图的运算时间应是图中显示数据的10倍。可见二步算法是查表逐点算法的优化，计算速度大大提高，而本文提出的去除冗余的优化算法进一步提高了全息图的计算时间，它与二步算法的速度比稳定在10倍左右。

图4 不同全息图尺寸计算时间比较

最后，使用OpenGL构建一个立方体，如图5（a）所示，将读取的空间物点信息规整到虚拟空间网格中，采用基于GPU的CUDA并行计算计算出全息图如图5（b）所示。全息图尺寸为1 024点×1 024点，物点数为500点，采用二步算法计算时间为1.187 s，而采用本文所提的去除冗余的子全息图查表优化算法计算时间仅为0.882 s，计算速度明显提高。

图5 正方体及其全息图

4 结束语

计算机制全息图的大计算量和长的计算时间直接影响了其全息三维显示的实用化。由于传统全息图存在大量冗余信息，忽略大量冗余光波的数据处理，只计算视窗位置对应的子全息图，并采用人眼跟踪技术能实时调整子全息图，以保证视窗位置光波正确性，在子全息的计算中引入二步算法思想，全息图的计算量减少，计算速度大幅度上升。实验表明，去除冗余的子全息图查表优化算法比二步算法计算速度提高了10倍左右，随着空间物点数的增多，计算速度提高越明显。

[1]科利尔.光全息学[M].盛尔镇，孙明经，译.北京：机械工业出版社，1983：32-36.

[2]Lee S W.Hampled fourier transform hologram generated by computer[J].App Opt，1970，9（3）：639-643.

[3]虞祖良，金国藩.计算机制全息图[M].北京：清华大学出版社，1984.

[4]Matsushima K，Takaim.Fast computation of fresnel holograms employing difference[J].App Opt，2000，39（35）：6587-6594.

[5]金洪震，李勇，王辉.实现相息图快速计算的一种方法[J].应用激光，2002，22（1）：13-14.

[6]Ito T，Shimobaba T.One-unit system for electrohologra-phy by use of a special-purpose computational chip with a high-resolution liquid-crystal display toward a three-dimensional television[J].Optics Express，2004，12（9）：1788-1793.

[7]Masudan，Ito T，Tanaka T，et al.Computer generated holography using a graphics processing unit[J].Opt Express，2006，14：603-608.

[8]李勇，许富洋，金洪震.一种菲涅尔全息图的快速算法[J].光子学报，2010，39（3）：529-531.

[9]Pan Yuechao，Xu Xuewu，Solanki S，et al.Fast CGH computation using S-LUTS on GPU[J].Optics Express，2009，17（21）：18543-18555.

[10]Xu Xuewu，Solanki S.Computer-generated holography for display of 3D objects with full parallax[J].The International Journal of Virtual Reality，2009，8（2）：33-38.

[11]Yan Chao，Wang Y.Robust real-time multi-user pupil detection and tracking under various illumination and large-scale head motion[J].Computer Vision and Image Understanding，2011，115（8）：1223-1238.

[12]孙迎红，童元满，王志英.RSA算法的CUDA高效实现技术[J].计算机工程与应用，2011，47（2）：84-87.

CHEN Huirong1，2,FU Shenghao1,WANG Yuanqing1,FAN Kefeng3

1.School of Electronic Science and Engineering,Nanjing University,Nanjing 210093,China
2.Department of Electrical Engineering,Wuhu Vocational Institute of Technology,Wuhu,Anhui 241006,China
3.China Electronics Standardization Institute,Beijing 100007,China

The generation speed of the Computer Generated Hologram（CGH）affects the application of holographic three-dimensional display technology.Hence,an effective and fast computation method is proposed.Through the analyzing of the traditional hologram,a lot of redundant information is found in it.The combination of spatial redundancy light wave removal algorithm and tracking of the human eyes methods determines the scope of sub-holograms.Furthermore,a method for sub-hologram that ranks contribution component is calculated by two-step algorithm is applied.Calculation of sub-hologram which ignores a large number of redundant data and application of two-step algorithm which removes redundant computation loosen the computational amount of CGH and thus increase the speed.The experimental results show that the algorithm is effective and the speed is accelerated about ten times by the two-step algorithm.

Computer Generated Hologram（CGH）;sub-hologram;fast computation;redundant lightwave

计算机制全息图的计算速度影响了全息三维显示技术的实用化。鉴于此，提出了一种计算机制全息图快速计算方法。通过分析发现传统全息图存在大量冗余信息，采用空间冗余光波去除方法，利用人眼跟踪技术实时确定子全息图范围，并将二步算法思想用于子全息图计算，计算行列贡献分量。由于仅计算子全息图，将大范围冗余光波数据忽略，大大减少了全息图计算量，同时二步算法的引入去除了大量冗余计算，全息图的运算速度明显提高。实验证明，这种算法是行之有效的，且计算速度比二步算法提高了10倍左右。

计算机制全息；子全息；快速计算；冗余光波

A

TP391

10.3778/j.issn.1002-8331.1303-0348

CHEN Huirong,FU Shenghao,WANG Yuanqing,et al.Fast computation method for CGH.Computer Engineering and Applications,2013,49（18）：142-144.

国家自然科学基金重点项目资助（No.608320036）；科技部对欧盟科技合作专项（No.0817）；国家质检公益性行业科研专项经费资助项目（No.201110233）。

陈慧蓉（1972—），女，副教授，研究领域为计算机全息及全息显示，自动控制；付胜豪（1988—），男，硕士研究生，研究领域为计算机图像生成；王元庆（1964—），男，教授，博士生导师。E-mail：chr1972@126.com

2013-03-22

2013-05-27

1002-8331（2013）18-0142-03