即時資料驅動描繪之參數表示式與張量近似演算法

Abstract

過去幾十年來，電腦繪圖領域之專家學者致力於開發各式各樣特殊新穎的視覺效果，以期能夠利用電腦合成出如同真實相片般之影像。為了達到高畫質擬真影像輸出，許多被稱為資料驅動描繪之進階繪圖演算法，會事先運用複雜程序處理輸入之三維場景以獲得必要資訊，抑或從真實世界當中預先擷取影像資訊，以便於執行時期能藉由這些視覺資訊快速重建出所希望描繪之視覺特效。然而隨著人類對於影像逼真程度之需求日益增高，預先採樣資訊之資料量也隨之水漲船高，不但耗費大量的儲存空間，也同時增加執行時期之資料存取時間以及描繪運算量。

為了解決上述問題，我們可以透過簡潔的表示式來有效率地描述預先採樣資訊，並應用精密複雜的壓縮方法以進一步減少資料儲存量。然而從以往相關研究成果卻可以觀察到，要能夠大幅度減少資料量，同時保有即時運算效能，是相當困難的一項挑戰，因為此兩項主要目標之間經常具有互斥性質。有鑑於此，我們於本論文當中將特別著重相關議題之探討，針對資料之表示式與近似演算法兩大主題，研究兩者於即時視覺資訊描繪之發展與應用。關於資料表示式，本論文將介紹兩項特殊參數表示式：單變量以及多變量球面輻射基底函數，主要用以描述視覺資訊中常見的輻射與照明度函數，同時更可以進一步拓展至各種於球表面採樣之資訊。而資料壓縮方面，本論文則提出兩項嶄新張量近似演算法：叢集以及稀疏叢集張量近似法，不但能夠充分利用視覺資訊之相依性關係，達到資料量減少與即時快速重建皆可兼顧之目的，也能夠延伸至各式高維度大型科學資料之壓縮、分析、或描述。

本論文最終更將深入研討如何透過所提出之方法來近似與重建預先採樣資訊，以期能於計算量、壓縮誤差、以及儲存空間三者之間達到最佳平衡點，同時更選取於電腦繪圖與視覺領域中具代表性之數項應用作為實驗基礎。實驗成果充分驗證本論文所提方法之可行性與可塑性，不但能夠有效保留原始資訊當中之視覺特徵，同時也能輕易達到即時描繪速率。如此一來，高畫質之擬真影像合成便可以於現今一般個人電腦上實現，不再是超級電腦或電影製作所專屬之權益。

Over the last decades, computer graphics and vision researchers have focused on developing novel visual effects for computer-generated photo-realistic images. To achieve high-quality output, many state-of-the-art rendering algorithms, which are known as data-driven rendering, pre-process an input three-dimensional scene with complex procedures to obtain necessary data, or pre-capture the real world with a set of images. The desired visual effects are then reconstructed from the pre-sampled observations for efficient run-time rendering. Nevertheless, with the increasing demand of more and more photo-realistic image synthesis, the amount of pre-sampled data expands accordingly. It not only consumes a great deal of storage space, but also increases data access time and rendering costs at run-time.

In order to solve this issue, we can adopt a compact representation to efficiently describe the pre-sampled observations and further apply sophisticated approximation methods to reduce the amount of data, but achieving real-time performance at the same time is frequently another challenging problem. In this dissertation, we thus focus on data representations and approximation algorithms for real-time rendering of visual data sets. Two novel parametric representations, univariate and multivariate \emph{spherical radial basis functions} (SRBFs), and two sophisticated tensor approximation algorithms, \emph{clustered tensor approximation} (CTA) and \emph{K-clustered tensor approximation} (K-CTA), are proposed to exploit the coherence in visual data sets. The univariate and multivariate SRBFs are especially suitable for modeling radiance and illumination data sets that are common and ubiquitous in computer graphics and vision. Additionally, SRBFs also can be applied to represent various kinds of observations on the unit hyper-sphere. As for CTA and K-CTA, they are developed based on tensor approximation to simultaneously achieve high compression ratios and real-time rendering performance for multi-dimensional visual data sets. CTA and K-CTA are also general approximation algorithms that are not restricted to specific applications. They can be employed to compress, analyze, or represent other large-scale scientific data sets that intrinsically exhibit multi-dimensional structures.

Last but not the least, we also investigate how to approximate and reconstruct the pre-sampled observations with a trade-off among computational costs, compression errors, and storage space. The proposed methods are further applied to various representative applications in computer graphics and vision. Our experiments show promising results in which important features of visual data sets are well-preserved after approximation and rendered at real-time rates. As a result, high-quality photo-realistic image synthesis can be efficiently realized on modern personal computers, not privileged to supercomputers or film production anymore.