基于降維和篩選的立體圖快速生成算法

劉曉平， 習(xí)雅思

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

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

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

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

1 立體圖基本原理

1.1 立體圖成像原理

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

1.2 立體圖生成原理

同成像原理——由約束點聚焦到模型——相反，生成立體圖是由模型計算約束點坐標(biāo)，然后復(fù)制約束點顏色值的過程[7]。下面以最簡單的列優(yōu)先從左到右的掃描順序為例來說明。

圖 1 立體圖原理

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

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

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

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

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

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

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

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

2.1 降維預(yù)處理

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

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

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

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

2.2 篩選操作

圖3 降維預(yù)處理

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

3 實驗結(jié)果與分析

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

圖4 “人頭”模型

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

圖5 “人頭”立體圖

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

表1 加速效果

4 總結(jié)與展望

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

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