劉曉平， 習(xí)雅思

（合肥工業(yè)大學(xué)計(jì)算機(jī)與信息學(xué)院VCC研究室，安徽 合肥 230009）

三維立體圖是一種利用人眼的雙目視覺(jué)特性巧妙設(shè)計(jì)的二維圖像，其紋理在水平方向上保持一定的重復(fù)性，并根據(jù)需要表現(xiàn)的三維模型的形狀做必要的變化。圖像由眾多相關(guān)點(diǎn)組成，每組相關(guān)點(diǎn)都能使人的兩個(gè)眼睛在裸眼狀態(tài)下聚焦到圖像后方一個(gè)預(yù)先設(shè)計(jì)的深度，從而整幅圖像構(gòu)成一個(gè)完整的三維模型。不同于通常的具有透視或者光照和陰影效果的二維圖像，三維立體圖從人眼的雙目立體成像原理出發(fā)，充分利用了人的雙眼對(duì)空間深度信息的感知，從而能夠給人一種更加真實(shí)的立體沉浸感。

1960年，Julesz發(fā)現(xiàn)嵌有立體信息的兩幅圖像，用雙眼可以感知到深度信息[1]，Tyler此基礎(chǔ)上將兩幅隨機(jī)點(diǎn)立體圖像合并到一個(gè)單幅圖像中，得到了所謂的單幅隨機(jī)點(diǎn)立體圖像(Single image random dot stereogram)，即自動(dòng)立體圖(Autostereograms)[2-3]。

自從Tyler[3]提出基本立體圖生成原理以來(lái)，眾多學(xué)者對(duì)立體圖的重影(Echo)[4-5]、隱藏面消除(HSR)[4,6]、隨機(jī)紋理[7]及立體圖的分層效應(yīng)(Stratified character)[8]等問(wèn)題進(jìn)行了深入研究。然而，基本立體圖生成算法，即用射線和三維模型求交的方式生成立體圖的方法，對(duì)任意三維模型生成立體圖，計(jì)算量較大，生成速度緩慢，對(duì)此國(guó)內(nèi)外學(xué)者沒(méi)有進(jìn)行必要的改進(jìn)。本文提出了一種基于降維和篩選的快速立體圖生成方法，該方法通過(guò)降維和篩選大幅度減少計(jì)算量，可以在不影響立體圖效果的情況下獲得較快的生成速度。

1 立體圖基本原理

1.1 立體圖成像原理

三維立體圖是由眾多約束點(diǎn)[4]組成的，所謂的約束點(diǎn)就是一對(duì)相關(guān)的像素點(diǎn)，其顏色值、垂直坐標(biāo)相同，而水平坐標(biāo)不同。圖1是立體圖生成系統(tǒng)的頂視圖，Aleft和Aright是成像平面（立體圖）上的一對(duì)約束點(diǎn)，由于這兩點(diǎn)間距小于人兩眼間距，因此左眼和右眼分別通過(guò)這兩點(diǎn)往成像平面后面看去，兩眼的視線會(huì)聚焦于成像平面后面的一點(diǎn)A。立體圖上存在眾多這樣的約束點(diǎn)，不同的約束點(diǎn)位置和間距不同，如圖2所示，從而人眼聚焦點(diǎn)的位置和遠(yuǎn)近也不同，眾多的聚焦點(diǎn)組成了一個(gè)位于成像平面后面的虛擬的三維模型。由于人的兩眼是用同樣的原理，即雙目立體成像來(lái)感知物體遠(yuǎn)近的，因而立體圖成像原理完全符合人眼視覺(jué)特性，通過(guò)立體圖看到的三維模型具有強(qiáng)烈的立體沉浸感。

1.2 立體圖生成原理

同成像原理——由約束點(diǎn)聚焦到模型——相反，生成立體圖是由模型計(jì)算約束點(diǎn)坐標(biāo)，然后復(fù)制約束點(diǎn)顏色值的過(guò)程[7]。下面以最簡(jiǎn)單的列優(yōu)先從左到右的掃描順序?yàn)槔齺?lái)說(shuō)明。

圖 1 立體圖原理

圖 2 約束點(diǎn)的顏色復(fù)制

按照從左到右的掃描順序，當(dāng)前掃描點(diǎn)以及該點(diǎn)右側(cè)所有的點(diǎn)的顏色是未知的，而當(dāng)前掃描點(diǎn)左側(cè)所有點(diǎn)的顏色是已知的，初始紋理圖——立體圖中將重復(fù)出現(xiàn)的紋理——緊靠在立體圖的左側(cè)。如圖1所示，若當(dāng)前掃描點(diǎn)是Bright，從右眼到Bright點(diǎn)做一條射線并與模型或背景平面相交于B點(diǎn)，B點(diǎn)和左眼的連線交成像平面于Bleft點(diǎn)，該點(diǎn)就是Bright的約束點(diǎn)，將Bleft點(diǎn)的顏色值復(fù)制給Bright點(diǎn)。對(duì)于圖中A點(diǎn)的情形，Aright的約束點(diǎn)Aleft不在立體圖范圍內(nèi)，而位于其左側(cè)的初始紋理圖中，這時(shí)，將初始紋理圖中Aleft處的顏色復(fù)制到Aright點(diǎn)。對(duì)立體圖中所有像素點(diǎn)按照列優(yōu)先的順序從下到上、從左到右依次掃描，并使用上述方法計(jì)算約束點(diǎn)坐標(biāo)、復(fù)制約束點(diǎn)顏色值，就得到了一幅立體圖。

2 基于降維和篩選的加速算法

基于求交測(cè)試的方法是通過(guò)人眼與成像平面像素點(diǎn)的連線和模型求交，并反求約束點(diǎn)來(lái)生成立體圖的，由于每生成一個(gè)像素點(diǎn)，都要對(duì)模型中所有三角面片進(jìn)行求交測(cè)試，因而該方法存在計(jì)算速度慢的致命缺點(diǎn)。為此，本文提出一種基于降維和篩選的立體圖快速生成算法。算法描述如下：

預(yù)處理 對(duì)模型進(jìn)行降維；

For(按序掃描的立體圖中每列像素點(diǎn)){

篩選1：對(duì)該列進(jìn)行篩選操作得到三角面片集合U1；

該算法的關(guān)鍵在于降維預(yù)處理和對(duì)三角面片的篩選兩項(xiàng)操作，下面對(duì)其分別進(jìn)行介紹。

2.1 降維預(yù)處理

如圖3，計(jì)算任一像素點(diǎn)I1的顏色值，用右眼P 和I1的連線同模型中的每個(gè)三角面片 △ V0V1V2求交點(diǎn)。空間三角形△ V0V1V2、射線 PI1的表示及二者交點(diǎn)的參數(shù)計(jì)算分別如下

這里需要P、I1、V0、V1、V2五個(gè)線性無(wú)關(guān)的三維向量，數(shù)據(jù)維數(shù)是15。

本文算法的降維預(yù)處理是指在進(jìn)行真正的三維求交測(cè)試之前，將模型中每個(gè)空間三角形 △ V0V1V2映射為成像平面上的平面三角形 △，繼而將△ V0′V1′V2′用其包圍盒的4 個(gè) 參數(shù)(xmin, ymin, xmax, ymax)來(lái)表示，同時(shí)將射線1PI 用成像平面上的二維點(diǎn)I1'來(lái)表示。即

如圖3，P 點(diǎn)和空間三角形△ V0V1V2頂點(diǎn)的三條連線分別交成像平面于、、三點(diǎn)，得到平面三角形△。對(duì)I1點(diǎn)只取其在成像平 面上的二維坐標(biāo)，得到I1'點(diǎn)。由此，數(shù)據(jù)的維數(shù)從原先的15 維降到了6 維，其目的在于降低下面的篩選操作的計(jì)算復(fù)雜度。

2.2 篩選操作

圖3 降維預(yù)處理

相比式(3)，式(4)只需四次大小比較，計(jì)算量遠(yuǎn)小于前者，因而篩選操作本身的耗時(shí)遠(yuǎn)小于三維求交。同時(shí)，由于符合篩選條件的三角形只是模型中所有三角形的一小部分，篩選出的集合的元素個(gè)數(shù)遠(yuǎn)小于篩選前的三角形個(gè)數(shù)，因而，真正進(jìn)行的三維求交的計(jì)算次數(shù)大幅度降低。

3 實(shí)驗(yàn)結(jié)果與分析

圖4 和圖5 分別是一個(gè)三維模型和對(duì)該模型應(yīng)用本文算法生成的三維立體圖，由圖5 可見(jiàn)其三維效果良好。使用加速算法，計(jì)算得到的約束點(diǎn)坐標(biāo)和傳統(tǒng)算法是相同的，并不影響最終的立體圖效果。

圖4 “人頭”模型

使用多個(gè)三維模型，按照1000×800 的分辨率進(jìn)行多次實(shí)驗(yàn)，平均耗時(shí)數(shù)據(jù)如表1 所示。從中可見(jiàn)，當(dāng)模型的三角面片數(shù)較多時(shí)，用本文算法生成同樣分辨率的立體圖，耗時(shí)比基本算法顯著減少（表中前兩列）；當(dāng)模型的三角面片較少時(shí)，加速比較低（第3～5 列）；而當(dāng)模型的三角面片非常少時(shí)，則可能出現(xiàn)本文算法的耗時(shí)略大于基本算法的情況（最后一列）。

圖5 “人頭”立體圖

本文算法之所以能夠?qū)αⅢw圖生成過(guò)程進(jìn)行加速，原因在于：在進(jìn)行傳統(tǒng)的空間射線和三角形求交運(yùn)算之前，進(jìn)行了篩選操作，使得參與求交運(yùn)算的空間三角形數(shù)目顯著減少；同時(shí)，篩選操作本身只需要進(jìn)行四次標(biāo)量的大小比較，其計(jì)算量遠(yuǎn)小于空間射線和三角形求交運(yùn)算。由于模型中的三角面片不可能是均勻分布的，不同的模型中的三角面片的密度也不相同，因此本文算法的加速比同模型的三角面片數(shù)目沒(méi)有嚴(yán)格的比例關(guān)系，而只有概率意義上的趨勢(shì) ——三維模型中包含的三角面片越多，加速效果越顯著——這一點(diǎn)從表1 中可以看出。當(dāng)模型中的三角面片非常少時(shí)，篩選前和篩選后的參與求交運(yùn)算的三角面片數(shù)目相差不多，二者的求交運(yùn)算時(shí)間差別不大，但本文算法還需要進(jìn)行降維預(yù)處理，所以，有可能本文算法的耗時(shí)反而略大于基本算法，表1 最后一列使用單個(gè)三角形的極端情況說(shuō)明了這一點(diǎn)。

表1 加速效果

4 總結(jié)與展望

三維立體圖利用人眼的雙目立體成像原理，在裸眼觀看的情況下，使用單幅平面圖像給觀看者帶來(lái)強(qiáng)烈的立體沉浸感，是一種獨(dú)特的可視化手段。本文針對(duì)基于求交測(cè)試的立體圖生成過(guò)程中的速度慢的問(wèn)題，提出了一種基于降維和篩選的快速算法，在不影響立體圖效果的情況下，顯著提高了立體圖的生成速度，同時(shí)分析了模型中三角面片數(shù)目對(duì)加速效果的影響。如何根據(jù)模型中三角面片的數(shù)目和分布情況，確定更加靈活的像素點(diǎn)掃描順序和篩選策略，使得篩選得到的集合最小，是可以進(jìn)一步開(kāi)展的工作。

[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.