Politecnico di Milano
Dipartimento di Matematica "F. Brioschi"

Dottorato di Ricerca in Ingegneria Matematica, XVII ciclo

Alessandro Foi

Anisotropic nonparametric image processing:
theory, algorithms and applications

April 2005

Defended on May 24, 2005 at the Department of Mathematics, Politecnico di Milano, Milano, Italy.

Examination Commission:    Supervisor:
- Prof. Emilio Barucci (Università degli Studi di Pisa)    - Prof. Karen Egiazarian (Tampere University of Technology)
- Prof. Patrizio Campisi (Università degli Studi di Roma III)    Coordinator:
- Prof. Stefano Tubaro (Politecnico di Milano), Chair of the Commission         - Prof. Marco Fuhrman (Politecnico di Milano)

Download complete thesis as PDF file

(12.3 MB)


When estimating an image from its noisy observations, a trade-off between noise suppression (variance) and smoothing (bias) has to be considered. Common images are nonstationary, often characterized by localized features. Therefore, images should be treated adaptively: for example, one would achieve a higher noise suppression where the original image is smooth, than in the vicinity of sharp transitions such as edges, where oversmoothing should be avoided.
So, the desired balance between variance and bias depends on the image's local features. How to control this balance is a key problem in adaptive signal processing. A novel and original strategy to achieve such adaptation is the main subject of this thesis.
The presented approach is based on the Intersection of Confidence Intervals (ICI) rule for pointwise-adaptive estimation. Originally, the method has been developed for 1D signals. The idea was generalized for 2D image processing, where adaptive-size quadrant windows have been used.
The main intention of these techniques is to obtain - in a data-driven way - a largest local neighborhood of the estimation point in which the underlying model fits the data.
Our main assumption is that this vicinity is a starshaped body which can be approximated by some sectorial decomposition with, say, K non-overlapping sectors. We use special directional kernels defined on a sectorial support. By endowing these kernels with a scale parameter, we are able to use the ICI rule for the pointwise selection of an adaptive scale, which defines the length of the sectorial support.
Anisotropy is enabled by allowing different adaptive scales for different directions. Thus, the ICI rule is exploited K times, once for each sector. In this way, we reduce a complex multidimensional shape adaptation problem, to a number of scalar optimizations.
The directional estimates corresponding to the adaptive-scale sectors are combined into the final anisotropic estimate. The resulting estimator is truly anisotropic, and its support can have quite an exotic shape. It is highly sensitive with respect to change-points, and allow to reveal fine elements of images from noisy observations, thus showing a remarkable advantage in the proposed strategy.
Several algorithms are developed, based on this estimator. Denoising is the main, and most natural application, but also deconvolution, and derivative estimation are problems where the anisotropic adaptation approach can play a significant role in order to achieve an improved restoration performance.


A necessary compromise
The relevance of the work behind this thesis is twofold: not only a quite general theoretical framework for a novel estimator has been developed, but also several algorithmic solutions to concrete problems of applicative interest have been developed, optimized, and compared against other state-of-the-art techniques. In many occasions, the proposed new techniques have proven to outperform the best methods appeared in the literature of our knowledge.
This thesis aims to cover these two rather different aspects, the theoretical and the algorithmical, in order to provide a complete view on the scope of the research that was carried out. In order not to overload the reader, it has been decided not to go too deep into the details of neither of these two aspects. Instead, our motivation was to emphasize the links between the theoretical modeling and the practical implementations. Consequently, in the theoretical exposition some topics are here purposely neglected (e.g. the use of a vector scale-parameter and some convergence analyses that have purely abstract importance), and in the description of the algorithms some aspects are not discussed (e.g. the procedures for the optimization of the algorithm parameters and some computational issues). Likewise, non essential remarks have been dropped or relegated to footnotes.
Nevertheless, we try to keep the exposition on a general-enough level: for example, the local polynomial approximation is presented as a very particular case of the general form of the moving least-squares method, described in the context of Hilbert-space approximations, and the asymptotic accuracy analyses are also done in a rather general way. Although, some finer aspects are eventually and inevitabily "rounded off", the resulting formulas are lean, and allow -- in the author's opinion -- a much easier understanding of the general applicability of the developed methods.
It has been also decided not to follow the standard "definition-theorem-proof-corollary" formalism, typical of most mathematical texts. Instead, a more informal and discoursive style is used.

Structure of the thesis
The thesis is structured in two parts. Firstly, we consider the theoretical background on which the developed technique is based: the LPA, the ICI, and the anisotropic fusing of the directional LPA-ICI estimates are presented. Denoising is considered as the underlying basic problem at which the approach is targeted. A recursive filtering strategy and an extension of the anisotropic denoising method for the gradient estimation problem are also discussed. In the second part we present a number of different algorithms and applications in which the proposed techniques can be successfully exploited: besides denoising, also deblurring, inverse-halftoning and other related problems are considered.

Notation and conventionsxiii
ITheoretical background and basic methods1
1Local approximations, the moving least-squares method, and the local polynomial approximation (LPA)  3
1.1Analysis, reconstruction and approximation in Hilbert spaces3
1.1.1Projection onto an orthonormal basis4
1.1.2Non-orthogonal case: frames4
1.2The space L^2 with a windowing measure6
1.2.1Definition of the space6
1.2.2Best approximation in L^2(R^d,mu)7
1.3Pointwise evaluation of the approximation and its kernel representation.8
1.4Moving least-squares (MLS) method10
1.4.2Moving least-squares denoising11
1.5Local polynomial approximation (LPA)12
1.5.1Characterization of an LPA12
1.5.2Function and derivative estimation kernels12
1.5.3Vanishing moments14
1.5.4Zero-order LPA14
1.6Finite case andmatrix notation14
1.6.1Best approximation (weighted least-squares solution)15
1.6.2Pointwise evalution of the best approximation and corresponding kernel15
1.6.3Vector form for LPA function and derivative estimation kernels16
1.7Some examples of LPA kernels16
2Adaptive nonparametric estimation19
2.1Parametric vs. nonparametric estimation19
2.2.1LPA kernels as smoothers21
2.3Accuracy analysis of the LPA kernels21
2.3.1Bias and variance22
2.3.2Asymptotic error analysis23
2.3.3Ideal scale24
2.4Intersection of Confidence Intervals (ICI) rule25
2.4.1The idea25
2.4.2ICI adaptive-scale selection rule26
2.4.3ICI algorithmpseudo-code27
2.4.4Choice of Gamma28
2.4.5Examples with symmetric windows29
3Directional LPA33
3.2Directional LPA: a general definition34
3.3Discrete directional-LPA kernel construction35
3.4Peculiarities of the directional-LPA kernel design35
3.5Some examples of directional-LPA kernels36
4Anisotropic LPA-ICI39
4.1Motivation and idea39
4.1.1Estimates with support optimization40
4.1.2Estimates with kernel-scale optimization42
4.2Anisotropic estimator based on directional adaptive-scale43
4.2.1Anisotropic LPA-ICI estimator43
4.2.2Adaptive anisotropic kernel and adaptive anisotropic neighborhood44
4.2.3Anisotropic estimation: formal modelling45
4.3Anisotropic LPA-ICI pseudo-code49
4.5Fusing: why sigma^-2?51
4.5.1Fusing unbiased estimates54
4.5.2Uniform kernels for a uniform anisotropic kernel55
4.6Ideal scale h and the use of ICI for fused estimates56
4.6.1Practical impact of the Gamma parameter56
4.6.2MSE of the anisotropic fused estimate57
4.6.3A simplified analysis58
4.6.4Speculations and results on the value of Gamma59
4.7Uniform fusing for overlapping discrete kernels60
4.8Variance of the fused estimate62
4.8.1Non-overlapping kernels63
4.8.2Origin-overlapping kernels63
4.8.3Uniform fusing64
4.9Robust ICI for anisotropic estimation64
4.9.1WOS filters65
4.9.2Anisotropic LPA-ICI WOS filters66
4.9.3Binary WOS as thresholding of a linear filter67
4.10Algorithm complexity and implementation issues68
4.10.2Implementation aspects68
5LPA-ICI for signal-dependant or space-variant noise 71
5.1Signal-dependant noise71
5.1.1Poisson observations72
5.2Space-variant noise73
5.2.1Variance for heteroskedastic observations74
5.2.2Variance's asymptotics74
5.2.3Confidence intervals for non-Gaussian distributed estimates74
6Recursive anisotropic LPA-ICI77
6.1An iterative system77
6.2Estimation neighborhoods' enlargement78
6.3Variance of l-th iteration's directional estimates79
7Directional derivative estimation and anisotropic gradient81
7.1Derivative estimation81
7.1.1Derivative estimation LPA kernels82
7.2Anisotropic gradient estimation86
7.2.2An illustrative example in the continuous domain89
7.2.3The same example in the discrete domain91
7.2.4Continuous domain anisotropic gradient94
7.2.5Discrete domain anisotropic gradient97
7.2.6More examples99
IIAlgorithms, applications and further examples107
8.1Additive white Gaussian noise109
8.2Recursive LPA-ICI implementation109
8.3Signal-dependant noise113
8.3.1Recursive variance update114
8.3.2Poisson denoising experiments116
8.3.3Simulation results118
8.3.4Other types of noise120
9.1Additive white Gaussian noise125
9.1.2Adaptive RI-RWI deblurring algorithm126
9.1.3Derivative estimation and edge detection from noisy blurred observations128
9.2Poisson deconvolution128
9.2.2Poissonian RI-RWI algorithm.130
9.2.3Linear inverse with directional adaptive LPA-ICI filtering130
9.2.4Poissonian RI inverse131
9.2.5Poissonian RWI inverse132
9.2.7Numerical experiments133
9.3Inverse halftoning134
9.3.1Halftoning and inverse halftoning136
9.3.2Error diffusion137
9.3.3Linear model of error diffusion138
9.3.4Anisotropic LPA-ICI inverse-halftoning140
9.3.5Simulation results143
10Other applications147
10.1Video denoising147
10.1.2Coordinate system148
10.1.3Video-denoising simulation148
10.2Shading from depth map: Z-buffer shading150
11Hybrid methods: LPA-ICI SA-DCT155

Download complete PDF file (12.3 MB)
Foi, A., Anisotropic nonparametric image processing: theory, algorithms and applications, Tesi di Dottorato (Ph.D. Thesis), Dip. di Matematica, Politecnico di Milano, April 2005.