Publicado em: 23/05/2016

Tese do PPGC agraciada no ACM SIGGRAPH 2016

Tese de Doutorado de Eduardo Gastal agraciada com o ACM SIGGRAPH Outstanding Doctoral Dissertation Award

A tese de doutorado de Eduardo Simões Lopes Gastal, intitulada “Efficient high-dimensional filtering for image and video processing”, orientada pelo professor do Instituto de Informática da UFRGS, Manuel Menezes de Oliveira Neto, foi agraciada com ACM SIGGRAPH Outstanding Doctoral Dissertation Award. A escolha do júri foi unânime: “In recognition of the potential impact and the notable contributions you have made during your doctoral studies, the committee has unanimously selected you to receive the inaugural ACM SIGGRAPH Outstanding Doctoral Dissertation Award at this year’s SIGGRAPH”. A tese foi desenvolvida integralmente no PPGC-UFRGS e defendida em 2015/1.

A cerimônia de premiação ocorrerá durante o ACM SIGGRAPH 2016 que ocorrerá em Anaheim, Califórnia, em julho de 2016. 

Mais informações em: http://s2016.siggraph.org/content/acm-siggraph-awards

Resumo das contribuições da Tese do Eduardo.

High-dimensional filtering (HDF) is a fundamental building block for many applications, including detail manipulation, denoising, tone mapping, photon-mapping filtering, upscaling, spatio-temporal filtering, recoloring, and stylization, just to name a few. Prior to Eduardo’s PhD work, high-dimensional filtering techniques were able to produce good results in many practical situations, but were not computationally efficie nt. For instance, the well-known bilateral filter has cost O(2^dN), considering an input with N samples in a d-dimensional space. For an RGB image, d = 5 (i.e., XYRGB), preventing the use of the technique in real-time applications, and making its use impractical for higher-dimensional images and videos. This has motivated the appearance of a large number of acceleration techniques that had to rely on monochromatic images, quantization, and use of a predefined set of filter scales.

Eduardo’s thesis completely changed this scenario by introducing three fundamentally novel and efficient ways of looking at and understanding the high-dimensional filtering problem, all based on solid mathematical ground. The first technique, called Domain Transform, offers an O(N) solution for performing high-dimensional (an)isotropic filtering using a geodesic metric. The thesis also introduces three filters (with distinct impulse responses) for performing signal reconstruction and intended for different applications. The Domain Transform was published at SIGGRAPH 2011 and is currently the fastest geodesic HDF technique available both for CPU and GPU. It has been well-received by practitioners and researchers. A third-party implementation has been included in OpenCV, and according to Google Scholar the paper has over 225 citations.

The second technique, called Adaptive Manifolds, introduced an O(N)-time solution for (an)isotropic HDF using a Euclidean metric. This work provided the first demonstration of a single-pass hybrid Euclidean-geodesic filter. The Adaptive Manifolds technique was published at SIGGRAPH 2012. Like the Domain Transform, it is the fasted Euclidean HDF technique available for both CPU and GPU, has an independent OpenCV implementation, and has been well cited.

The third significant contribution is a discrete-time O(rN) mathematical formulation for applying arbitrary recursive filters to non-uniformly sampled signals. Here, r is the order of the filter. This is a major accomplishment. Note that while many applications are better defined using non-uniform sampling (e.g., global illumination, edge-aware image processing, alias-free signal processing, etc.), standard filtering tools, such as FFT, convolutions, and recursive filters, assume uniform sampling. This called for the development of a new mathematical formulation, and it should impact other areas in signal processing. The work also introduced two normalization schemes for filtering non-uniformly sampled signals. In edge-aware filtering applications, these normalization schemes provide control over the filter’s response to signal discontinuities (i.e., edges). This was previously only possible for finite impulse response (FIR) filters. The thesis then provided the first linear-time edge-aware demonstrations of several low/high/band-pass filters, including Gaussian, Laplacian of Gaussian, and Butterworth. This technique was presented at EUROGRAPHICS 2015, where it received the Best Paper Award Honorable Mention.

In summary, Eduardo’s thesis introduced three optimal (i.e., linear time) solutions for different aspects of HDF and changed our understanding about this fundamental problem.