Документ взят из кэша поисковой машины. Адрес оригинального документа : http://imaging.cs.msu.su/pub/2011.Graphicon.Lebedev_Ignatenko.Light.en.pdf
Дата изменения: Mon Aug 22 14:17:10 2011
Дата индексирования: Sat Apr 9 23:35:45 2016
Кодировка:

Compression of light transport matrix
Andrey Lebedev, Ivan Karpuhin, Andrey Il yin, Alexey Ignatenko Department of Computational Mathematics and Cybernetics Moscow State University, Moscow, Russia {alebedev, ikarpuhin, ailyin, ignatenko}@graphics.cs.msu.ru

Abstract
We address the problem of relighting of three-dimensional scenes and propose a new method based on reconstruction of light transport matrix. The matrix can be reconstructed on-fly from data obtained by some renderer (we use path-tracing algorithm). We compared our method with existing ones. The proposed method achieves better quality compared to others with the same compression ratio. It is suitable not only for diffuse scenes and can be easily parallelized. In future we can use this method as a new global illumination algorithm. Keywords: relighting, photorealistic rendering, light transport matrix, compression.

calculation of light transport matrix, addresses compression and recovery problems of light transport matrix as well as the quality of rendered images.

2. REVIEW OF EXISTING METHODS
Initially the relighting problem was solved for some special cases. Debevec [1] modeled reflective properties and geometry of the human face skin to obtain images in various lighting conditions (relighting skin). Very complicated equipment that measured the reflectance of skin for various light sources and camera position was used to model the reflective properties. A special imagebased method for face geometry reconstruction was developed. Based on geometrical and reflectivity information the authors changed the illumination of face. Several thousand of images were used for full reconstruction of the human face. Later Wenger [9] improved the method for relighting of human face. He used a special camera for measurements and a special set of light sources. Then the author obtained an image for each light source from a special set and relit the face representing a new light source as a linear combination of basis sources. The relit image was equal to the linear combination with the same coefficients of images for light sources from special set. Peers [6] formalized the relighting problem as follows: = ( 1) where - is a vector of image pixel intensities, - is a vector of light source intensities, - light transport matrix. ( , )-element of light transport matrix is a contribution of light source into the intensity of image pixel . Due to the linearity of light we have formula (1). Relighting problem was formalized for a fixed camera position case. Lawrence [4] generalized formula (1) for an arbitrary camera position case considering the light transport matrix as a relationship between light source vector and vertices of polygonal model of the scene. However this approach leads to the problems connected with the calculation of the view-dependent material models. The light transport matrix is usually huge (sometimes it occupies several gigabytes). That is why the most important trend in relighting is matrix compression. Wang [ 8] proposed Nystom algorithm for compressed representation of light transport matrix. In this case instead of the entire matrix we store some of its rows and columns, the rest of the matrix was reconstructed on the basis of these rows and columns. Mahajan [5] compressed light transport matrix using the property of locally low rank of this matrix. He divided the whole image into blocks and each block was reconstructed independently using the method of principal components (PCA). An alternative way to compress light transport matrix is compressed sensing [2]. Sen [7] and Peers [6] investigated the problem of matrix restoration by a small set of measurements. They considered the matrix of light transport in a special basis

1. INTRODUCTION
The relighting problem arises during rendering of threedimensional scenes. It is particular actual for designers as they often have to modify illumination in modeled scene. Aside from modeling and visualization in architectural rendering we should have an opportunity to integrate a building into existing environment (see Figure 1).

Figure 1: Modeled building (top) and integrated into existing environment (bottom). When you change the lighting (or environment) in the scene it is necessary to recalculate the whole image. Calculation of a single image can take from half a minute to several hours, depending on the complexity of scenes, and lighting effects. This article discusses the relighting methods based on a preliminary

(obtained a sparse signal). Then the signal was recovered by compressed sensing methods. In our work we used a standard formulation of the relighting problem by Peers [6], the idea of application of Nystrom algorithm for matrix recovery and local blocks of Mahajan [5]. We have developed a system for scene relighting and provide several algorithms for light transport matrix compression.

Figure 3: Relighting results of the scene with an area light source.

3.2 Global compression of light transport
The main problem of the basic implementation is the large size of the light transport matrix. For a scene with an area source in Figure 3 the matrix size was 9 GB. There are problems with matrix storage, slow work with the disk that significantly reduces the relighting speed. Wang [8] proposed to compress the light transport matrix using Nystrom method. Also it was considered an algorithm for rows and columns retrieval for Nystrom method from images of real scenes. By analogy with [8] we have developed several versions of the algorithm for rows and columns selection:

·

Algorithm 1. Choose arbitrary rows, consider them as a set of columns with dimension , clusterize vectors using -means method. Centers of the clusters are needed columns (see Fig. 4 - marked in green). Algorithm 2. Choose arbitrary lines using -means. Algorithm 3. Choose random columns. Algorithm 4. Choose lines using -means. obtain new lines, union of all rows and columns, calculate columns and random

· · ·
Figure 2: Results of relighting (Conference Room).

arbitrary columns, calculate Then choose other columns etc. As an output we obtain the columns.

3. DESCRIPTION OF RELIGHTING SYSTEM 3.1 Basic implementation
The developed system reconstructs light transport matrix for arbitrary three-dimensional scene and relights this scene using equation (1). Light transport matrix is calculated using path tracing algorithm [3]. Note that the total work time of path tracing algorithm for light transport calculation is practically the same one as for rendering of one image because for all backward ray tracing algorithms we need to compute all paths from camera to various points of scene. Relighting step is based on equation (1). We used CUDA programming technology to accelerate matrix multiplication. Figure 2 shows the results of relighting of benchmark Conference room scene. The rendering time is less than 1 second for 1024 by 768 resolution on NVIDIA 240M GPU. 20 light sources were used in this scene. In Fig.3 we can see the result of relighting of scene with complex light effects using area light source (resolution - 32 by 32).

Figure 4: Scheme for rows and columns selection. In [8] Wang also proposed to use a nonlinear transformation of light transport matrix to maximize compression. Our tests show

that the algorithm with a nonlinear transformation is not resistant to noisy images obtained by path tracing. Also it works well on a number of specific scenes (with diffuse materials and blurred caustics). In scenes with bright reflections, visible light source and bright caustics the algorithm generates artifacts (see Fig.5). To remove artifacts we should significantly increase the number of rows and columns.

Figure 5: Artifacts of nonlinear transformation algorithm.

3.3 Local compression of light transport
Mahajan in [5] showed the benefits of reconstruction of independent light transport matrices for the different image blocks. We have also implemented algorithms for matrix reconstruction independently for each image block. Local compression of the light transport matrix can adaptively compress the matrix, i.e. use a different number of rows and columns for reconstruction of different blocks. For example, blocks with a uniform illumination usually require fewer rows and columns than the blocks with bright reflection (or caustics). Another advantage of this approach is the ability to paralleliz e the algorithm, since image blocks can be processed independently.

Figure 6: Dependency of average PSNR on number of columns (a - diffuse scene, b reflections, c caustics, d mixed scene). Also, we have compared our algorithm with a nonlinear algorithm of Wang [8]. Earlier in the section 3.2 were mentioned the main problems of nonlinear algorithm. In [ 8] light transport matrix for diffuse scene was compressed 4000 times. This was achieved by using a huge resolution of the light source. We showed that increasing the resolution of the light source does not lead to the increase of the matrix rank (it remains constant). This is because the new columns of light transport matrix are actually the result of interpolation (i.e., linear combination) of the old ones. We compared the compression ratios of our algorithm and the nonlinear one [8], using a light source with resolution 64 by 64 (see Fig. 9).

3.4 The pr oposed algorithm
We propose the following algorithm to compress the light transport matrix. First of all, the entire image is divided into blocks. For each block, we use Algorithm 4 for selecting rows and columns (see section 3.2). For on-fly reconstruction of full matrix we use Nystrom method [8]. In the next section, we analyze the algorithms described in section 3.2, and compare them with the proposed one.

4. RESULTS AND COMPARISON
In the first stage, we compared our algorithm with block versions of algorithms 1-3 (see section 3.2). The comparison was performed using different types of scenes: diffuse, with caustics, reflections and mixed scenes. To assess the quality of synthesized images we used PSNR metric between the images generated using full light transport matrix and its compressed form. Calculating the PSNR we considered different light sources (different color, position and size), then PSNRs were averaged. Fig. 6 presents the results of algorithm comparison of average PSNRs for all types of scenes. All the algorithms show the same result on diffuse scene. Our algorithm shows much better results than the other ones on the scenes with reflections, caustics and visible light source. Figs. 7-8 present rendering results of our algorithm on all types of scenes.

Figure 7: Rendering results of our algorithm on different types of scenes: diffuse and specular (left obtained by full matrix, right by our compressed form). The comparison was made for the diffuse scene and the algorithms behave the same way. However, for other types of scenes a nonlinear algorithm is much worse.

Figure 8: Rendering results of our algorithm on different types of scenes: caustics and general (left obtained by full matrix, right by our compressed form).

[4] Lawrence J., Stamminger M., Huang F., Ramamoorthi R. Sparsely precomputing the light transport matrix for real-time rendering. Computer Graphics Forum 29, 4 (2010), 1335-1345. [5] Mahajan D., Shlizerman I.K., Ramamoorthi R., Belhumeur P. A theory of locally low dimensional light transport. ACM Transactions on Graphics 26, 3 (2007). [6] Peers P., Mahajan D. K., Lamond B., Ghosh A., Matusik W., Ramamoorthi R., Debevec, P. Compressive light transport sensing. ACM Transactions on Graphics 28, 1 (2009), 3:13:18. [7] Sen P., Darabi S. Compressive Rendering: A Rendering Application of Compressed Sensing. IEEE Transactions on Visualization and Computer Graphics, 99 (2010), 1-14. [8] Wang J., Dong Y., Tong X., Lin Z., Guo B. Kernel Nystrom method for light transport. ACM Transactions on Graphics 28, 3 (2009), 1-10. [9] Wenger A., Gardner A., Tchou C., Unger J., Hawkins T., Debevec P. Performance relighting and reflectance transformation with time-multiplexed illumination. ACM Transactions on Graphics 24, 3 (2005), 756764.

About the authors
Andrey Lebedev is a Ph.D. student at Moscow State University, Department of Computational Mathematics and Cybernetics. To get more information about him visit http://lebedev.as. Ivan Karpuhin is a student at Moscow State University, Department of Computational Mathematics and Cybernetics. Andrey Ilyin is a research Department of Computational research interests include 3D computer vision and image ailyin@graphics.cs.msu.ru. Figure 9: Dependency of average PSNR on compression ratio for our method and nonlinear one. er at Moscow State University, Mathematics and Cybernetics. His reconstruction, camera calibration, processing. His contact e-mail is

5. CONCLUSION AND FUTURE PLANS
We proposed a new algorithm to compress light transport matrix. The results of algorithm analysis and comparison with other ones show that the proposed algorithm works better than others on some types of scenes, more resistant to noise and it can be easily parallelized. Our results can be used as a new algorithm for ray tracing with higher convergence rate than available ones. Algorithm for selection of rows and columns obtains the most important for ray tracing paths from the light source to camera. Also we are going to explore the issue of ray tracing acceleration.

Alexey Ignatenko is a researcher at Moscow State University, Department of Computational Mathematics and Cybernetics. His research interests include photorealistic 3D rendering, 3D modeling and reconstruction, image-based rendering and adjacent fields. His contact e-mail is ignatenko@graphics.cs.msu.ru.

6. LITERATURE
[1] Debevec P., Hawkins T., Tchou C., Duiker H.-P., Sarokin W., Sagar, M. Acquiring the reflectance field of a human face. In Proceedings of ACM SIGGRAPH 2000, Computer Graphics Proceedings, Annual Conference Series (2000), 145156. [2] Donoho D.L. Compressed sensing. IEEE Transactions on Information Theory 52, 4 (2006), 1289-1306. [3] Kajiya J. The rendering equation. ACM SIGGRAPH Computer Graphics, 20, 4 (1986), 143-150.