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

1.南京大學(xué) 電子科學(xué)與工程學(xué)院，南京 210093

2.蕪湖職業(yè)技術(shù)學(xué)院 電氣工程系，安徽 蕪湖 241006

3.中國電子技術(shù)標(biāo)準(zhǔn)化研究所，北京 100007

一種計(jì)算機(jī)制全息圖快速運(yùn)算算法

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

1.南京大學(xué) 電子科學(xué)與工程學(xué)院，南京 210093

2.蕪湖職業(yè)技術(shù)學(xué)院 電氣工程系，安徽 蕪湖 241006

3.中國電子技術(shù)標(biāo)準(zhǔn)化研究所，北京 100007

1 引言

在三維立體顯示技術(shù)中，全息顯示技術(shù)是最為理想和最有吸引力的。由于保留了物光波的全部振幅和相位信息，保留了所有的視差深度暗示，故觀察全息三維像與現(xiàn)實(shí)中所觀察的原物具有完全相同的視差效果。最早采用的全息成像方法是光全息[1]，但隨著計(jì)算機(jī)技術(shù)以及光電子技術(shù)發(fā)展，全息技術(shù)進(jìn)一步發(fā)展為計(jì)算全息[2-3]。計(jì)算機(jī)制全息圖（Computer Generated Hologram，CGH）與光學(xué)全息圖相比，具有更大靈活性和可操作性，可產(chǎn)生復(fù)雜甚至是虛擬物體全息圖。將計(jì)算機(jī)生成的全息圖加載于空間光調(diào)制器，可實(shí)現(xiàn)全息的動(dòng)態(tài)顯示。而要將全息三維顯示技術(shù)實(shí)用化達(dá)到視頻效果，就必須提高計(jì)算機(jī)制全息圖的運(yùn)算速度。

為了提高全息圖計(jì)算速度，人們提出了一些快速算法[4-10]。文獻(xiàn)[8]提出了一種全息圖快速算法，利用三角函數(shù)變換，將全息圖計(jì)算進(jìn)行分解，分解為水平和垂直方向的獨(dú)立分量的四則運(yùn)算組合形式，使計(jì)算量大大減少。文獻(xiàn)[9-10]提出S-LUT（Split Look-Up Tables，S-LUT）算法，在傳統(tǒng)查表算法基礎(chǔ)上優(yōu)化為二步算法，去除大量冗余計(jì)算，提高計(jì)算速度。但到目前為止，全息圖的計(jì)算速度仍達(dá)不到滿意效果。本文根據(jù)全息圖存在大量冗余信息這一特點(diǎn)，提出了去除大量冗余光波信息，僅計(jì)算視窗位置光波即子全息區(qū)域，來減少計(jì)算量。同時(shí)引進(jìn)二步算法思想，以判斷物點(diǎn)列與全息像素列的對(duì)應(yīng)關(guān)系來代替逐點(diǎn)判斷的低效，使全息圖運(yùn)算速度進(jìn)一步提高。實(shí)驗(yàn)證明，本文所提的算法是有效的。

2 原理

2.1 計(jì)算機(jī)制全息圖基本原理

全息圖制作模型如圖1所示，全息面記錄場景中物體發(fā)射或反射光波與參考光波干涉后的光強(qiáng)，此光強(qiáng)包含物光波的相位信息。只有離散數(shù)據(jù)才能被計(jì)算機(jī)處理，故計(jì)算機(jī)制全息圖的制作首先將空間物體看做是一系列自發(fā)光的空間物點(diǎn)集合，通過模擬物點(diǎn)集發(fā)出的光波在全息面處的疊加效果來制取全息圖。因此首先要獲取空間物點(diǎn)的集合。這一過程可以通過空間掃描儀對(duì)真實(shí)空間物體進(jìn)行掃描，也可以借助OpenGL等軟件構(gòu)建虛擬空間物體，并通過讀取深度緩沖及相應(yīng)坐標(biāo)變換獲取。

圖1 全息圖制作模型圖

假設(shè)空間物體由N個(gè)離散發(fā)光點(diǎn)組成，全息面上每一樣點(diǎn)都可被每個(gè)物點(diǎn)發(fā)出的離散光線照亮，全息面上任一點(diǎn)復(fù)振幅可表示為：

式中λ為波長，φn為初相位，an為物點(diǎn)(xn，yn，zn)的衍射光波振幅，rn為物點(diǎn)到全息面上(x，y)點(diǎn)的距離。

將參考光與每一物點(diǎn)干涉的全息圖進(jìn)行疊加，即可得多個(gè)物點(diǎn)全息圖，干涉光強(qiáng)在全息面上分布可表示為：

在完成計(jì)算全息平面上的光場分布后，進(jìn)行計(jì)算全息編碼，編碼為全息圖的透過率函數(shù)，量化和歸一后形成一幅完整的計(jì)算機(jī)制全息圖。

2.2 逐點(diǎn)計(jì)算的查表算法不斷優(yōu)化原理

將式（3）進(jìn)行菲涅爾近似，可得：

對(duì)式（4）進(jìn)一步處理可得：

豎直方向因子：

將式（6）、（7）帶入式（5）得：

由式（6）可見，對(duì)于空間同一列的物點(diǎn)，H(x)相同，故可以將其作為公因子提出，式（8）可轉(zhuǎn)化為：

其中Nj為j列物點(diǎn)數(shù)，k為物點(diǎn)列數(shù)。

由式（4）可見，逐點(diǎn)計(jì)算的全息圖計(jì)算方法需計(jì)算每個(gè)物點(diǎn)到各全息面的距離，進(jìn)而計(jì)算光強(qiáng)分布，大量時(shí)間耗在了平方、平方根以及余弦函數(shù)值計(jì)算，比如對(duì)于尺寸為X×Y的全息圖，計(jì)算每個(gè)物點(diǎn)在全息面上的光強(qiáng)分布需要5XY次，n個(gè)物點(diǎn)的光強(qiáng)分布就需要5nXY次，可見計(jì)算量非常之龐大。

若事先離線制作相位因子查找表，將水平方向H(x)和豎直方向V(y)因子存儲(chǔ)于查找表中，這樣在線運(yùn)行計(jì)算時(shí)，避免了平方和平方根計(jì)算，由式（8）可見，其計(jì)算量就會(huì)由5nXY次下降到2nXY次。但從式（8）的計(jì)算過程看出，出現(xiàn)大量有關(guān)水平方向和豎直方向冗余計(jì)算，因此相息圖的計(jì)算算法可進(jìn)一步改進(jìn)。

對(duì)于空間同一列的物點(diǎn)，水平因子H(x)相同，故在計(jì)算空間某一列上物點(diǎn)在全息面的光強(qiáng)分布時(shí)，可將其作為公因子提取出來，不必每次都參與計(jì)算，可減少運(yùn)算量。由式（9）可見，全息圖的計(jì)算分成兩步，第一步是計(jì)算各列的全息圖光強(qiáng)分布，第二步是將各列物點(diǎn)在全息圖上進(jìn)行疊加，故這種查表優(yōu)化算法也稱為二步算法。此算法由于去除了一些冗余計(jì)算，使全息圖的計(jì)算次數(shù)再次下降，計(jì)算量就會(huì)由2nXY次降為2nX+XY次。

2.3 去除冗余的子全息圖計(jì)算原理

在傳統(tǒng)全息顯示中，為了重建三維空間中的物體，使用整個(gè)空間光調(diào)制器記錄全息信息，重建光波范圍遠(yuǎn)大于瞳孔大小，故存在大量的無用信息。由于全息圖破碎為碎片后，全息圖的每個(gè)碎片均能重建原始場景，故可采用去除冗余的子全息圖方案，即用空間光調(diào)制器的一部分即子全息圖編碼全息信息，重建人眼位置（視窗）附近光波。

如圖2所示，對(duì)于空間某一物點(diǎn)，視窗附近的光波是有效的，圖中陰影部分，除此以外就是大量冗余光波。可見，采用去除大范圍及大量冗余光波信息的子全息圖計(jì)算方案可以大大減少計(jì)算量。對(duì)于子全息區(qū)域的確定，采用瞳孔跟蹤技術(shù)[11]實(shí)時(shí)獲取人眼位置信息也就是視窗位置，這樣可保證視窗附近小區(qū)域光波正確性，準(zhǔn)確確定出子全息圖范圍。

圖2 空間冗余光波示意圖

對(duì)于子全息圖的計(jì)算，采用二步算法以加快全息圖的運(yùn)算速度。其算法原理為：以物點(diǎn)列和全息像素列為單位，通過空間物點(diǎn)列確定該物點(diǎn)列對(duì)應(yīng)的全息像素列范圍，由全息面上像素列確定對(duì)其有貢獻(xiàn)的物點(diǎn)列集合，這樣無需遍歷空間所有物點(diǎn)來確定對(duì)全息圖上各像素點(diǎn)有貢獻(xiàn)的物點(diǎn)集合，避免逐點(diǎn)判斷引起的低計(jì)算效率。設(shè)某一空間物點(diǎn)列對(duì)應(yīng)的全息像素列為x列(x＜X)，其計(jì)算量降為查表逐點(diǎn)算法的x/X倍，采用二步算法的子全息圖計(jì)算量再次下降，降為2nx+xY次，計(jì)算速度得到大幅度提高。

3 實(shí)驗(yàn)驗(yàn)證

采用圖像處理單元（Graphic Processing Unit，GPU）處理技術(shù)的CUDA[12]并行計(jì)算，采用C++語言編寫程序，在PC機(jī)（處理器為英特爾Core2Duo E5300，內(nèi)存2 GB，英偉達(dá)GT240顯卡；win7操作系統(tǒng)，vs2010編譯環(huán)境，CUDA4.0通用開發(fā)包）上進(jìn)行實(shí)驗(yàn)，分別用三種方案進(jìn)行計(jì)算，即式（8）的查表逐點(diǎn)計(jì)算，式（9）的二步算法計(jì)算，本文所提的去除冗余光波的子全息圖查表優(yōu)化算法計(jì)算。首先研究全息圖尺寸固定，物點(diǎn)數(shù)變化時(shí)，進(jìn)行三種算法的實(shí)驗(yàn)觀察。全息圖尺寸為1 024點(diǎn)×1 024點(diǎn)，物點(diǎn)數(shù)分別為100、1 000、3 000、5 000、65 535點(diǎn)，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 物點(diǎn)數(shù)變化時(shí)計(jì)算時(shí)間比較

可見，隨著物點(diǎn)數(shù)的增加，加速越大，當(dāng)物點(diǎn)數(shù)在5 000點(diǎn)時(shí)，去除冗余的子全息圖查表優(yōu)化算法與二步算法計(jì)算速度比在2倍左右，但當(dāng)物點(diǎn)數(shù)增加到60 000點(diǎn)時(shí)，其速度比穩(wěn)定在10倍左右。

接下來研究物點(diǎn)數(shù)固定，全息圖尺寸變化時(shí)，三種算法的實(shí)驗(yàn)觀察。取65 536個(gè)空間物點(diǎn)，實(shí)驗(yàn)結(jié)果如圖4所示。對(duì)于采用查表逐點(diǎn)算法計(jì)算全息圖的運(yùn)算時(shí)間應(yīng)是圖中顯示數(shù)據(jù)的10倍?？梢姸剿惴ㄊ遣楸碇瘘c(diǎn)算法的優(yōu)化，計(jì)算速度大大提高，而本文提出的去除冗余的優(yōu)化算法進(jìn)一步提高了全息圖的計(jì)算時(shí)間，它與二步算法的速度比穩(wěn)定在10倍左右。

圖4 不同全息圖尺寸計(jì)算時(shí)間比較

最后，使用OpenGL構(gòu)建一個(gè)立方體，如圖5（a）所示，將讀取的空間物點(diǎn)信息規(guī)整到虛擬空間網(wǎng)格中，采用基于GPU的CUDA并行計(jì)算計(jì)算出全息圖如圖5（b）所示。全息圖尺寸為1 024點(diǎn)×1 024點(diǎn)，物點(diǎn)數(shù)為500點(diǎn)，采用二步算法計(jì)算時(shí)間為1.187 s，而采用本文所提的去除冗余的子全息圖查表優(yōu)化算法計(jì)算時(shí)間僅為0.882 s，計(jì)算速度明顯提高。

圖5 正方體及其全息圖

4 結(jié)束語

計(jì)算機(jī)制全息圖的大計(jì)算量和長的計(jì)算時(shí)間直接影響了其全息三維顯示的實(shí)用化。由于傳統(tǒng)全息圖存在大量冗余信息，忽略大量冗余光波的數(shù)據(jù)處理，只計(jì)算視窗位置對(duì)應(yīng)的子全息圖，并采用人眼跟蹤技術(shù)能實(shí)時(shí)調(diào)整子全息圖，以保證視窗位置光波正確性，在子全息的計(jì)算中引入二步算法思想，全息圖的計(jì)算量減少，計(jì)算速度大幅度上升。實(shí)驗(yàn)表明，去除冗余的子全息圖查表優(yōu)化算法比二步算法計(jì)算速度提高了10倍左右，隨著空間物點(diǎn)數(shù)的增多，計(jì)算速度提高越明顯。

[1]科利爾.光全息學(xué)[M].盛爾鎮(zhèn)，孫明經(jīng)，譯.北京：機(jī)械工業(yè)出版社，1983：32-36.

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

[3]虞祖良，金國藩.計(jì)算機(jī)制全息圖[M].北京：清華大學(xué)出版社，1984.

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

[5]金洪震，李勇，王輝.實(shí)現(xiàn)相息圖快速計(jì)算的一種方法[J].應(yīng)用激光，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].光子學(xué)報(bào)，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高效實(shí)現(xiàn)技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用，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

計(jì)算機(jī)制全息圖的計(jì)算速度影響了全息三維顯示技術(shù)的實(shí)用化。鑒于此，提出了一種計(jì)算機(jī)制全息圖快速計(jì)算方法。通過分析發(fā)現(xiàn)傳統(tǒng)全息圖存在大量冗余信息，采用空間冗余光波去除方法，利用人眼跟蹤技術(shù)實(shí)時(shí)確定子全息圖范圍，并將二步算法思想用于子全息圖計(jì)算，計(jì)算行列貢獻(xiàn)分量。由于僅計(jì)算子全息圖，將大范圍冗余光波數(shù)據(jù)忽略，大大減少了全息圖計(jì)算量，同時(shí)二步算法的引入去除了大量冗余計(jì)算，全息圖的運(yùn)算速度明顯提高。實(shí)驗(yàn)證明，這種算法是行之有效的，且計(jì)算速度比二步算法提高了10倍左右。

計(jì)算機(jī)制全息；子全息；快速計(jì)算；冗余光波

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.

國家自然科學(xué)基金重點(diǎn)項(xiàng)目資助（No.608320036）；科技部對(duì)歐盟科技合作專項(xiàng)（No.0817）；國家質(zhì)檢公益性行業(yè)科研專項(xiàng)經(jīng)費(fèi)資助項(xiàng)目（No.201110233）。

陳慧蓉（1972—），女，副教授，研究領(lǐng)域?yàn)橛?jì)算機(jī)全息及全息顯示，自動(dòng)控制；付勝豪（1988—），男，碩士研究生，研究領(lǐng)域?yàn)橛?jì)算機(jī)圖像生成；王元慶（1964—），男，教授，博士生導(dǎo)師。E-mail：chr1972@126.com

2013-03-22

2013-05-27

1002-8331（2013）18-0142-03