Local Approximations in Signal and Image Processing (original) (raw)

Local Approximations in Signal and Image Processing (LASIP) is a project dedicated to investigations in a wide class of novel efficient adaptive signal processing techniques. Statistical methods for restoration from noisy and blurred observations of one-dimensional signals, images, 3D microscopy, and video were recently developed.

Introduction

We propose effective 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 which 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 which 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. The resulting adaptive estimator is always nonlinear even for the linear local polynomial approximation as the nonlinearity of the method is incorporated in the ICI rule itself.

Asymptotically, these adaptive estimators allow to get a near-optimal quality of the signal recovery.

These new methods can be exploited as independent tools as well as jointly with conventional techniques, such as maximum likelihood and quasi-likelihood.

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 new approach and new algorithms are mainly illustrated for image processing applications. However, they are quite general in nature and can be applied to multidimensional data.

Experiments demonstrate the state-of-art performance of the new algorithms which on many occasions visually and quantitatively outperform the best existing methods.

Historically, the nonparametric regression is a predecessor of wavelets.
In its modern development in the area of adaptive estimation this technique demonstrates tremendous new methods almost unknown to signal processing community dominated by the wavelet paradigm.

A web-presentation introducing the basic ideas of the LPA-ICI technique and showing its application to various kinds of image restoration problems is available here.

BookThe concepts, theory, and methodology of the modern spatially adaptive (nonparametric regression based) signal and image processing are presented in the new book: Local Approximation Techniques in Signal and Image Processing by V. Katkovnik, K. Egiazarian, and J. Astola, SPIE Press, Monograph Vol. PM157, September 2006. Hardcover, 576 pages, ISBN 0-8194-6092-3 Table of contents and preface Sample Pages (PDF, 209 KB)

Software

LASIP is also a set of MATLAB routines for signal and image processing.
They implement a recent new development in the area of statistical scale-adaptive local approximation techniques.LASIP provides flexible tools for the design of filters equipped with scale (window size) parameters. Directional filters can also be designed. The adaptivity of these filters is enabled by special statistical rules for a pointwise-adaptive selection of the scale values. The multidirectional versions these filters are especially efficient for anisotropic data.

The main algorithms are prepared as demos, so that they can be executed in a straightforward manner.
These demos reproduce figures and results from the publications by the authors of the LASIP project and their collaborators.

All the provided demos are open-source, and may be modified and tuned to be exploited with other data.
In this sense, we completely support the principle of reproducible research:“An article about computational science in a scientific publication is not the scholarship itself, it is merely advertising of the scholarship. The actual scholarship is the complete software development environment and the complete set of instructions which generated the figures” [Buckheit & Donoho, 1995].

The LASIP routines are available free-of-charge for educational and non-profit scientific research, enabling others researchers to understand and reproduce our work.

Any unauthorized use of the LASIP routines for industrial or profit-oriented activities is expressively prohibited. Please read the LASIP limited license before you proceed with downloading the files.

The LASIP routines can be downloaded as four self-contained sets:

Related work & advanced applications

The LASIP routines for Multiframe Blind Deconvolution are used for restoration of an image from its multiple blurred and noisy observations.

This section provides LASIP routines for the Fitted Local Likelihood (FLL) technique. The FLL is a novel statistical multiple hypothesis testing rule based on the local maximum likelihood estimation. This proposed statistics provides better performance for both Gaussian and non-Gaussian imaging (Gaussian, Poisson, Bernoulli models).

We propose a novel image denoising strategy based on an enhanced sparse representation in transform-domain. The enhancement of the sparsity is achieved by grouping similar 2D image fragments (e.g. blocks) into 3D data arrays which we call "groups". Collaborative filtering is a special procedure developed to deal with these 3D groups. We realize it using the three successive steps: 3D transformation of 3D group, shrinkage of transform spectrum, and inverse 3D transformation. The result is a 3D estimate that consists of the jointly filtered grouped image blocks. By attenuating the noise, the collaborative filtering reveals even the finest details shared by grouped blocks and at the same time it preserves the essential unique features of each individual block. The filtered blocks are then returned to their original positions.

The Block-Matching and 3D Filtering (BM3D) algorithm is a computationally scalable algorithm based on this novel denoising strategy. It achieves state-of-the-art denoising performance in terms of both peak signal-to-noise ratio and subjective visual quality. Papers and Matlab implementation available.

We introduce a new approach to image reconstruction from highly incomplete data. The available data are assumed to be a small collection of spectral coefficients of an arbitrary linear transform. This reconstruction problem is the subject of intensive study in the recent field of “compressed sensing” (also known as “compressive sampling”). Our approach is based on a quite specific recursive filtering procedure. At every iteration the algorithm is excited by injection of random noise in the unobserved portion of the spectrum and a spatially adaptive image denoising filter, working in the image domain, is exploited to attenuate the noise and reveal new features and details out of the incomplete and degraded observations. This recursive algorithm can be interpreted as a special type of the Robbins-Monro stochastic approximation procedure with regularization enabled by a spatially adaptive filter. Overall, we replace the conventional parametric modeling used in compressed sensing by a nonparametric one.

Demo for the paper _ V. Katkovnik, J. Astola, K. Egiazarian, “Phase local approximation (PhaseLa) technique for phase unwrap from noisy data,” IEEE Trans. Image Process., vol. 17, no. 6, pp. 833-846, June 2008._We apply the local polynomial approximation (LPA) in order to estimate the absolute phase as the argument of cos and sin. The LPA is a nonparametric regression technique with pointwise estimation in a sliding window. Using the intersection of confidence interval (ICI) algorithm the window size is selected as adaptive pointwise varying. This adaptation gives the phase estimate with the accuracy close to optimal in mean squared sense. For calculation we use a Gauss-Newton recursive procedure initiated by the phase estimates obtained for the neighboring points. This initialization enables tracking properties of the algorithm and its ability to go beyond the principal interval [0,2pi ) and to reconstruct the absolute phase from wrapped phase observations even when the magnitude of the phase difference takes quite large values. The algorithm demonstrates a very good accuracy of the phase reconstruction which on many occasion overcomes the accuracy of the state-of-the-art algorithms developed for noisy phase unwrap. The theoretical analysis produced for the accuracy of the pointwise estimates is used for justification of the ICI adaptation rule.

The LASIP routines for Color Filter Array Interpolation based on LPA-ICI: - CFAI for noiseless data; - adaptation for noisy data; - CFAI for noisy data based on directional cross-color filters.

We consider a complex-valued wavefield reconstruction in an object plane from data in a sensor plane. A digital modeling for the forward propagation is presented in the algebraic matrix form M-DDT. The inverse propagation is formalized as an inverse problem. The main algorithm of the complex-valued wavefield reconstruction with the proposed Matrix Discrete Diffraction Transform (M-DDT) is prepared as a Matlab demo.

People

The LASIP project is run by Karen Egiazarian, Vladimir Katkovnik, Jaakko Astola,Alessandro Foi, and Dmitriy Paliy.
Currently, also Kostadin Dabov is contributing to the project.

Publications

2009

Katkovnik, V., A. Foi, K. Egiazarian, and J. Astola, “From local kernel to nonlocal multiple-model image denoising”, preprint (July 2009), to appear Int. J. Computer Vision.
Katkovnik, V., A. Migukin, and J. Astola, “Backward discrete wavefield propagation modeling as an inverse problem: toward perfect reconstruction of wavefield distributions”, submitted to Applied Optics, 2009.

2008

Katkovnik, V., J. Astola, and K. Egiazarian, “Discrete diffraction transform for propagation, reconstruction, and design of wavefield distributions”, Applied Optics, vol. 47, no. 19, pp. 3481-3493, July 2008.
Katkovnik, V., A. Foi, K. Dabov, and K. Egiazarian, “Spatially adaptive support as a leading model-selection tool for image filtering”, Proc. First Workshop Inf. Th. Methods Sci. Eng., WITMSE, Tampere, August 2008.
Katkovnik, V., and V. Spokoiny, “Spatially Adaptive Estimation via Fitted Local Likelihood Techniques”, IEEE Transactions on Image Processing, vol. 56, no. 3, pp. 873-886, March 2008.
Katkovnik, V., J. Astola, and K. Egiazarian, “Phase local approximation (PhaseLa) technique for phase unwrap from noisy data”, IEEE Transactions on Image Processing, vol. 17, no. 6, pp. 833-846, June 2008.
Paliy, D., A. Foi, R. Bilcu, V. Katkovnik, “Denoising and Interpolation of Noisy Bayer Data with Adaptive Cross-Color Filters”, SPIE-IS&T Electronic Imaging, Visual Communications and Image Processing 2008, vol. 6822, San Jose, CA, January 2008.

2007

Katkovnik, V., J. Astola, and K. Egiazarian, “Noisy phase unwrap for holographic techniques: adaptive local polynomial approximations”, Proceedings 3DTV Conference, Kos, Island, Greece, 2007.
Foi, A., Pointwise shape-adaptive DCT image filtering and signal-dependent noise estimation, Tampere University of Technology, Publication 710, ISBN 978-952-15-1922-2, December 2007.
Paliy, D., Local Approximations in Demosaicing and Deblurring of Digital Sensor Data, Tampere University of Technology, Publication 708, ISSN 1459-2045, December 2007.
Paliy, D., V. Katkovnik, R. Bilcu, S. Alenius, K. Egiazarian, “Spatially Adaptive Color Filter Array Interpolation for Noiseless and Noisy Data”, International Journal of Imaging Systems and Technology (IJISP), Special Issue on Applied Color Image Processing, vol. 17, iss. 3, pp. 105-122, October 2007.
Paliy, D., V. Katkovnik, S. Alenius, K. Egiazarian, “Selection of Varying Spatially Adaptive Regularization Parameter for Image Deconvolution”, Proc. Int. TICSP International Workshop on Spectral Methods & Multirate Signal Processing, SMMSP 2007, Moscow, September, 2007.
Foi, A., V. Katkovnik, and K. Egiazarian, “Signal-dependent noise removal in Pointwise Shape-Adaptive DCT domain with locally adaptive variance”, Proc. 15th European Signal Process. Conf., EUSIPCO 2007, Poznan, September 2007.
Foi, A., “Spatially adaptive local approximations in signal and image processing: varying-scale polynomials, anisotropic adaptation, shape-adaptive transforms”, Lecture notes of the tutorial given at the 15th European Signal Process. Conf., EUSIPCO 2007, Poznan, September 2007.
Katkovnik, V., A. Foi, K. Egiazarian, “Mix-distribution modeling for overcomplete denoising”, Proc. 9th workshop on Adaptation and Learning in Control and Signal Processing (ALCOSP'07), St. Petersburg, Russia, August, 29-31, 2007.
Foi, A., V. Katkovnik, and K. Egiazarian, “Pointwise Shape-Adaptive DCT for High-Quality Denoising and Deblocking of Grayscale and Color Images”, IEEE Trans. Image Process., vol. 16, no. 5, pp. 1395-1411, May 2007.
Paliy D., R. Bilcu, V. Katkovnik, M. Vehvilainen, “Color Filter Array Interpolation Based on Spatial Adaptivity”, Proc. of SPIE-IS&T Electronic Imaging 2007, Computational Imaging IV, Vol. 6497, 649707, San Jose, CA, January 2007.
Paliy D., M. Trimeche, V. Katkovnik, S. Alenius, “Demosaicing of Noisy Data: Spatially Adaptive Approach”, Proc. of SPIE-IS&T Electronic Imaging 2007, Computational Imaging IV, Vol. 6497, 649720, San Jose, CA, January 2007.

2006

Katkovnik, V., K. Egiazarian, and J. Astola, Local Approximation Techniques in Signal and Image Processing, SPIE Press, Monograph Vol. PM157, September 2006.
Katkovnik V., and V. Spokoiny, “Spatially Adaptive Non-Gaussian Imaging via Fitted Local Likelihood Technique”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2006, Florence, September 2006.
Foi, A., V. Katkovnik, and K. Egiazarian, “Pointwise Shape-Adaptive DCT for high-quality deblocking of compressed color images”, Proc. 14th European Signal Process. Conf., EUSIPCO 2006, Florence, September 2006.
Foi, A., and V. Katkovnik, “From local polynomial approximation to pointwise shape-adaptive transforms: an evolutionary nonparametric regression perspective”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2006, Florence, September 2006.
Foi, A., S. Alenius, M. Trimeche, and V. Katkovnik, “Adaptive-size block transforms for Poissonian image deblurring”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2006, Florence, September 2006.
Dabov, K., A. Foi, V. Katkovnik, and K. Egiazarian, “Inverse halftoning by pointwise shape-adaptive DCT regularized deconvolution”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2006, Florence, September 2006.
Foi, A., R. Bilcu, V. Katkovnik, and K. Egiazarian, “Adaptive-size block transforms for signal-dependent noise removal”, Proc. 7th Nordic Signal Processing Symposium, NORSIG 2006, Reykjavik, Iceland, June 7-9, 2006.
Katkovnik V., D. Paliy, K. Egiazarian, and J. Astola, “Frequency domain blind deconvolution in multiframe imaging using anisotropic spatially-adaptive denoising”, Proc. 14th European Signal Process. Conf., EUSIPCO 2006, Florence, September 2006.
Katkovnik V., K. Egiazarian, J. Astola, “Novel spatially adaptive anisotropic local approximation techniques in image processing”, Electronic Imaging Conference, (EI-2006), Lecture notes for Short Course, January 17 2006 San Jose, USA.
Foi, A., K. Dabov, V. Katkovnik, and K. Egiazarian, “Shape-Adaptive DCT for denoising and image reconstruction”, Proc. SPIE Electronic Imaging 2006, Image Processing: Algorithms and Systems V, 6064A-18, San Jose, CA, January 2006.
Foi, A., V. Katkovnik, and K. Egiazarian, “Pointwise Shape-Adaptive DCT denoising with structure Preservation in Luminance-Chrominance Space”, Proc. of the 2nd Int. Workshop on Video Process. and Quality Metrics for Consumer Electronics, VPQM2006, Scottsdale, AZ, January 2006.
Paliy, D., V. Katkovnik, and K. Egiazarian, “Spatially adaptive 3D inverse for optical sectioning”, Proc. SPIE Electronic Imaging 2006, Computational Imaging IV, 6065-11, San Jose, CA, January 2006.
Boev, A., A. Foi, K. Egiazarian, and V. Katkovnik, “Adaptive scales as a structural similarity indicator for image quality assessment”, Proc. of the 2nd Int. Workshop on Video Process. and Quality Metrics for Consumer Electronics, VPQM2006, Scottsdale, AZ, January 2006.

2005

Foi, A., Anisotropic nonparametric image processing: theory, algorithms and applications, Ph.D. Thesis, Dip. di Matematica, Politecnico di Milano, April 2005.
Introduction and Table of Contents (html)
Foi, A., S. Alenius, M. Trimeche, V. Katkovnik, and K. Egiazarian, “A spatially adaptive Poissonian image deblurring”, Proc. of IEEE 2005 Int. Conf. Image Processing, ICIP 2005, Genova, September 2005.
Foi, A., R. Bilcu, V. Katkovnik, and K. Egiazarian, “Anisotropic local approximations for pointwise adaptive signal-dependent noise removal”, Proc. XIII European Signal Process. Conf., EUSIPCO 2005, Antalya, September 2005.
Katkovnik, V., A. Foi, K. Egiazarian, and J. Astola, “Anisotropic local likelihood: theory, algorithms, applications”, Proc. of El. Imaging 2005: Image Processing: Algorithms and Systems IV, 5672-19, 2005.
Foi, A., V. Katkovnik, and K. Egiazarian, “Pointwise Shape-Adaptive DCT as an overcomplete denoising tool”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2005, Riga, 2005.
Ercole, C., A. Foi, V. Katkovnik, and K. Egiazarian, “Spatio-temporal pointwise adaptive denoising of video: 3D non-parametric approach”, Proc. of the 1st Int. Workshop on Video Process. and Quality Metrics for Consumer Electronics, VPQM2005, 2005.
Paliy, D., V. Katkovnik, and K. Egiazarian, “Scale-Adaptive Inverse in 3D Imaging”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2005, Riga, 2005.
Trimeche, M., D. Paliy, M. Vehvilainen M., and V. Katkovnik, “Multi-Channel Image Deblurring of Raw Color Components”, Proceedings of SPIE, Volume 5674, Computational Imaging III, pp. 169-178, March 2005.
Katkovnik, V., K. Egiazarian, and J. Astola, “A Spatially Adaptive Nonparametric Regression Image Deblurring”, IEEE Trans. Image Process., vol. 14, no. 10, pp. 1469-1478, October 2005.
Katkovnik, V., “Multiresolution local polynomial regression: a new approach to pointwise spatial adaptation”, Digital Signal Process., vol. 15, pp. 73-116, 2005.

2004

Foi, A., V. Katkovnik, K. Egiazarian, and J. Astola, “A novel anisotropic local polynomial estimator based on directional multiscale optimizations”, Proc. of the 6th IMA Int. Conf. Math. in Signal Processing, Cirencester (UK), pp. 79-82, 2004.
Foi, A., V. Katkovnik, K. Egiazarian, and J. Astola, “Inverse halftoning based on the anisotropic LPA-ICI deconvolution”, Proc. Int. TICSP Workshop Spectral Meth. Multirate Signal Process., SMMSP 2004, Vienna, pp. 49-56, 2004.
Katkovnik, V., A. Foi, K. Egiazarian, and J. Astola, “Directional varying scale approximations for anisotropic signal processing”, Proc. of XII European Signal Process. Conf., EUSIPCO 2004, pp. 101-104, 2004.

2003...

Katkovnik, V., K. Egiazarian, and J. Astola, Adaptive varying scale methods in image processing, Tampere International Center for Signal Processing, TICSP Series, no. 19, Tampere, TTY, Monistamo, 2003.
Katkovnik, V., K. Egiazarian, and J. Astola, “Adaptive window size image de-noising based on intersection of confidence intervals (ICI) rule”, J. of Math. Imaging and Vision, vol. 16, no. 3, pp. 223-235, 2002.
Öktem, H., V. Katkovnik, K. Egiazarian, and J. Astola, “Local adaptive transform based image de-noising with varying window size”, Proc. IEEE Int. Conf. Image Process., ICIP 2001, Thessaloniki, Greece, pp. 273-276, October 2001.
Egiazarian, K., V. Katkovnik, and J. Astola, “Local transform-based image de-noising with adaptive window size selection”, Proc. SPIE Image and Signal Processing for Remote Sensing VI, vol. 4170, 4170-4, January 2001.
Nikolaev, N., A. Gotchev, K. Egiazarian, and Z. Nikolov, “Suppression of electromyogram interference on the electrocardiogram by transform domain denoising”, Medical & Biological Engineering and Computing, vol. 39, pp. 649-655, 2001.
Katkovnik, V., “A new method for varying adaptive bandwidth selection”, IEEE Trans. on Signal Proc., vol. 47, no. 9, pp. 2567-2571, 1999.

back to top of page