Tutorials

Tutorial title: Spatially adaptive local approximations in signal and image processing: varying-scale polynomials, anisotropic adaptation, shape-adaptive transforms.

Authors: Alessandro Foi, Vladimir Katkovnik, Karen Egiazarian
Affiliation: Institute of Signal Processing, Tampere University of Technology, Finland

Tutorial will be presented by Alessandro Foi.

Tutorial outline:
We present an overview on modern adaptive solutions for signal reconstruction problems based mainly on combining two independent nonparametric estimation ideas: the local polynomial approximation (LPA) and the intersection of confidence intervals (ICI) rule.
The LPA is a technique that is applied for nonparametric estimation using a polynomial data fit in a sliding window. The ICI rule is a criterion used for the adaptive selection of the size (scale) of this window. The resulting LPA-ICI estimators are nonlinear filters that are adaptive to the unknown smoothness of the signal.
The local polynomial approximation is originated from an old idea known under different names: moving (sliding, windowed) least-square, Savitzky-Golay filter, moment filters, reproducing kernels, singular convolution kernels, etc. However, combined with the new adaptation technique it becomes a novel powerful tool.
The window size, interpreted also as scale, is the key parameter of this technique. The terms "window size", "bandwidth", and "scale" are interchangeable here.
The idea of the ICI scale-adaptation is as follows. The algorithm searches for a largest local vicinity of the point of estimation where the local polynomial approximation assumptions fit well to the data. The estimates are calculated for a number of different scales and compared. The adaptive scale is defined as the largest for which the estimate does not differ significantly from the estimates corresponding to the smaller scales. The ICI rule defines the adaptive scale for each point (pixel, voxel) of the signal. In this way, we arrive to a pointwise-adaptive signal and image processing. Asymptotically, these adaptive estimators allow to get a near-optimal quality of the signal recovery.
The anisotropic implementation of the LPA-ICI, based on the use of multi-directional kernels, gives further improvement to the adaptivity of the method, providing an efficient tool especially for image denoising, differentiation and inverse-imaging problems. The latest development of these techniques goes beyond the traditional fixed-order polynomial models, replacing them with more general transforms defined on arbitrarily-shaped domains. This corresponds to multidimensional local polynomial and non-polynomial approximations with adaptive order and support. The efficient realization of these transforms is illustrated.
We conclude with a short discussion on the ongoing transition from local techniques to non-local ones (e.g., non-local means, patch-based estimators, block-matching 3D filtering), which appears as the latest and very successful trend in image denoising.

Discussion and comparison with other relevant approaches (including anisotropic diffusion, TV minimization, wavelets, curvelets, etc.) is given, highlighting the similarities and differences between the techniques.

The tutorial is accompanied by numerous experimental examples where these methods are applied to competitive image processing problems. Applications include image denoising, deblurring (deconvolution), deblocking and deringing, gradient estimation, edge-detection, inverse-halftoning, and color image processing.

Matlab software, which implements the presented techniques and experiments, is provided.

Content:
local polynomial approximation (theory and methods); linear smoothing and differentiation; adaptive scale selection: intersection of confidence intervals rule; adaptive algorithms; directional LPA; adaptive aggregation of multidimensional estimates, anisotropic LPA-ICI; spatially adaptive anisotropic regularization for deconvolution problems; image deblurring; shape-adaptive transforms, shape-adaptive DCT algorithms; non-local methods.


Information about the authors:



Alessandro Foi has received the M.Sc. and the Ph.D. degrees in mathematics from Universita degli Studi di Milano (Italy) in 2001 and from Politecnico di Milano in 2005, respectively. His research interests include mathematical and statistical methods for signal processing, functional analysis, and harmonic analysis. Currently, he is a researcher at the Institute of Signal Processing, Tampere University of Technology (Finland). His work focuses on spatially adaptive algorithms for denoising and deblurring of digital images and on noise modeling for digital imaging sensors.

Vladimir Katkovnik received the M.Sc., Ph.D., and D.Sc. degrees in technical cybernetics from the Leningrad Polytechnic Institute, Leningrad, Russia, in 1960, 1964, and 1974, respectively. From 1964 to 1991, he held the positions of Associate Professor and Professor at the Department of Mechanics and Control Processes, Leningrad Polytechnic Institute. From 1991 to 1999, he was a Professor of statistics with the Department of the University of South Africa, Pretoria. From 2001 to 2003, he was a Professor of mechatronics with the Kwangju Institute of Science and Technology, Korea. From 2000 to 2001 and since 2003 he is a Research Professor with the Institute of Signal Processing, Tampere University of Technology, Tampere, Finland. He has published seven books and more than 250 papers. His research interests include stochastic signal processing, linear and nonlinear filtering, nonparametric estimation, imaging, nonstationary systems, and time-frequency analysis.

Karen Egiazarian was born in Yerevan, Armenia, in 1959. He received the M.Sc. degree in mathematics from Yerevan State University in 1981, the Ph.D. degree in physics and mathematics from Moscow State University, Moscow, Russia, in 1986, and the D.Tech. degree from the Tampere University of Technology (TUT), Tampere, Finland, in 1994. He has been Senior Researcher with the Department of Digital Signal Processing, Institute of Information Problems and Automation, National Academy of Sciences of Armenia. Since 1996, he has been an Assistant Professor with the Institute of Signal Processing, TUT, where he is currently a Professor, leading the Transforms and Spectral Methods group. His research interests are in the areas of applied mathematics, signal processing, and digital logic.