Título: Efficient and Approximate High-Dimensional Filtering for Image and Video Processing
Linha de Pesquisa: Computação Gráfica

Data: 03/10/2013
Horário: 8h30min
Local: Sala 220 (conselhos). Prédio 43412 – Instituto de Informática

Banca Examinadora:
Prof. Dr. Alexandre Xavier Falcão (UNICAMP)
Prof. Dr. João Luiz Dihl Comba (UFRGS)
Prof. Dr. Cláudio Rosito Jung (UFRGS)

Presidente da Banca: Prof. Dr. Manuel Menezes de Oliveira Neto

Resumo:

Filtering is arguably the single most important operation in image and video processing. In particular, high-dimensional filters are a fundamental building block for several applications (FATTAL, 2009; FARBMAN; FATTAL; LISCHINSKI, 2010), having received considerable attention from the research community over the last two decades. Unfortunately, naive implementations of such an important class of filters are too slow for many practical uses, specially in light of the ever increasing resolution of digitally captured images (80-megapixel digital cameras are already available on the market, as of 2013). This dissertation describes two novel approaches to efficiently perform high-dimensional filtering: the domain transform, and the adaptive manifolds.The domain transform defines an isometry between curves on the 2D image manifold in 5D and the real line. It preserves the geodesic distance between points on these curves, adaptively warping the input signal so that high-dimensional geodesic filtering can be efficiently performed in linear time. This approach has several desirable features: the use of simple operations leads to considerable speedups over existing techniques and potential memory savings; its computational cost is not affected by the choice of the filter parameters; and it is the first filter of its kind to work on color images at arbitrary scales in real time, without resorting to subsampling or quantization.The adaptive manifolds compute the filter’s response at a reduced set of sampling points, and uses these for interpolation at all input pixels, so that high-dimensional Euclidean filtering can be efficiently performed in linear time. We show that for a proper choice of sampling points, the total cost of the filtering operation is linear both in the number of pixels and in the dimension of the space in which the filter operates. As such, ours is the first high-dimensional filter with such a complexity. We present formal derivations for the equations that define our filter, as well as for an algorithm to compute the sampling points. This provides a sound theoretical justification for our method and for its properties. The resulting filter is quite flexible, being capable of producing responses that approximate either standard Gaussian, bilateral, or non-local-means filters. Such flexibility also allows us to demonstrate the first hybrid Euclidean-geodesic filter that runs in a single pass.The high-dimensional filters we propose provide the fastest performance (on both CPU and GPU) for a variety of real-world applications. Thus, our filters provide a valuable tool for the image and video processing, computer graphics, computer vision, and computational photography communities.

Palavras chave: Filtragem em altas dimensões, filtros Euclidianos, filtros geodésicos, filtro híbrido Euclidiano-geodésico, filtro bilateral, filtro non-local-means