一種計算機制全息圖快速運算算法

陳慧蓉，付勝豪，王元慶，范科峰

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