Sparse reconstruction of multidimensional light transport signals

Abstract

Path space integration rendering algorithms are capable of synthesising high quality images perceptually indistinguishable from the real world. These algorithms require a huge number of light transport paths to be sampled in order to produce realistic imagery. Sampling a huge number of light paths is computationally demanding and methods are needed to reduce this computation time. The goal of this thesis is to reduce rendering time by reducing the number of sampled light paths and do so by exploiting sparse reconstruction techniques. These techniques allow the recovery of signals even when sampled at unusually low frequencies, in fact, well below the Nyquist limit. This is possible by exploiting some a priori knowledge, namely, the fact that the signal can be sparsely represented in some alternative space, other than the canonical time/space reference frame. Over the last decade sparse reconstruction techniques such as Compressive Sensing and the Sparse Fourier Transform have matured and demonstrated impressive results. This thesis applies sparse reconstruction techniques to the global light transport problem, including path space integration, in order to reduce the number of samples required to render high quality imagery. The Fourier Space is used as the sparse representation space: high dimensional signals (such as path space) are known to require a reduced number of coefficients to be represented in this space. The main contributions of this thesis are: • A sparsity analysis methodology for light transport signals, which allows verifying whether the signals being processed exhibit the properties required for successful sparse reconstruction: these include being dense on the sampling basis and sparse on the representation basis. • A method for efficient integration of multidimensional Fourier signals is proposed. This method treats the integration as a convolution with a box filter and reduces the dimensionality of the problem, calculating the integral values as a lower dimensionality inverse Fourier Transform. This method achieves much lower execution times and memory usage that alternative approaches, both due to the improved algorithmic complexity and the ability to leverage the efficiency of FFT implementations. • A sparse reconstruction pipeline, using the Sparse Fourier Transform, applied to discrete Path Space in primary sample space was developed. Due to the high sample requirements, however, direct reconstruction of Path Space is not as efficient as classical approaches. These sparse reconstructions can also be used as importance maps, providing a global path guiding mechanism for unbiased Monte Carlo integration, achieving local improvements to caustics rendering. • A second sparse reconstruction pipeline, based on Matching Pursuit algorithms (CoSaMP, specifically) is also proposed. Since the time complexity of these algorithms is exponential with the number of dimensions, lower dimensionality spaces were used, namely depth of field and indirect lighting, instead of path space. Direct reconstruction of these signals showed no improvements with respect to classical sampling, for the same execution time - note that executing CoSaMP constitutes an additional optimization step that costs a significant fraction of rendering time. An importance sampling approach was applied as well, providing similar local improvements to the previous approach. A new method is also proposed that uses sparse reconstruction results as a distance metric for a bilateral filtering process, which achieves image quality improvements upon classical approaches for complex scenes.

Os algoritmos de síntese de imagem baseados na integração no espaço dos trajectos de luz (path space) produzem resultados de elevada qualidade, perceptualmente indistinguíveis do mundo real. Esta qualidade, no entanto, é conseguida à custa de um elevado número de amostras; de fato, a qualidade das imagens é directamente proporcional à raiz quadrada do número de amostras: O(√N). O tempo de execução é directamente proporcional ao número de caminhos de transporte de luz amostrados, logo imagens de alta qualidade exigem tempos de processamento elevados. O principal objetivo deste trabalho é reduzir o tempo de síntese de imagens de alta qualidade, reduzindo o número de amostras através da aplicação de técnicas de reconstrução esparsa. Estas técnicas permitem a reconstrução de determinado tipo de sinais mesmo quando a taxa de amostragem é muito baixa, de fato, muito inferior ao limite de Nyquist. Tal é conseguido explorando algum conhecimento prévio sobre o sinal, nomeadamente, o fato de este admitir uma representação esparsa numa base alternativa. Ao longo da última década, técnicas de reconstrução esparsa como Compressive Sensing e a Sparse Fourier Transform ganharam maturidade e demonstraram resultados impressionantes. Esta tese aplica técnicas de reconstrução esparsa ao problema da iluminação global, incluindo integração no espaço dos trajectos de luz, visando a redução o número de amostras necessárias para produzir imagens de elevada qualidade. O espaço de Fourier é usado como base de representação esparsa: sinais de alta dimensionalidade têm sido descritos como aceitando representações com um número reduzido de coeficientes (logo esparsas) neste espaço. As principais contribuições desta tese são: • Uma metodologia para análise de esparsidade de sinais de transporte de luz, que permite verificar se estes exibem as propriedades necessárias para uma reconstrução esparsa eficaz: sinal denso na base de amostragem e esparso na base de representação. • Um método para a integração eficiente de sinais multidimensionais no espaço de Fourier. O processo de integração é tratado como uma convolução por um filtro box-car, reduzindo a dimensionalidade do problema e calculando o integral usando uma transformada de Fourier inversa de menor dimensionalidade. Optimizam-se o tempo de execução e a utilização de memória relativamente a abordagens anteriores, o que é conseguido explorando a eficiência da FFT que resulta numa diminuição da complexidade algoritmica. • Um pipeline de reconstrução esparsa usando a Sparse Fourier Transform (sFT) aplicada ao path space discretizado no espaço primário de amostragem (primary sample space). Devido ao elevado número de amostras exigidos pela sFT a reconstrução direta do sinal não é tão eficiente quanto abordagens clássicas. Reconstruções de menor qualidade, logo usando menos amostras, podem ser usadas como mapas de importância. Estes funcionam como um mecanismo que guia a amostragem do processo de Monte Carlo, exibindo melhorias locais na síntese de cáusticas. • Um segundo pipeline de reconstrução baseado em algoritmos da família do Matchin Pursuit (CoSaMP, especificamente). Dado que a complexidade destes algoritmos é exponencial com o número de dimensões do sinal, foram usados sinais de menor dimensionalidade, nomeadamente depth of field e iluminação indireta. A reconstrução direta destes sinais não atingiu melhorias sobre abordagens clássicas, para o mesmo tempo de execução. A execução do CoSaMP constitui um passo de otimização adicional que representa uma fração significativa do tempo de execução, anulando os ganhos obtidos com a redução do número de amostras. Foi desenvolvida Uma abordagem de amostragem por importância com resultados semelhantes ao ponto anterior. Adicionalmente, propõe-se utilizar os resultados de reconstrução esparsa como uma métrica de distância para um processo de Bilateral Filtering, atingindo melhorias na qualidade da imagem para cenas complexas.