Share Email Print

Spie Press Book

Local Approximation Techniques in Signal and Image Processing
Author(s): Vladimir Katkovnik; Karen Egiazarian; Jaakko Astola
Format Member Price Non-Member Price
cover GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. Check Access

Book Description

This book deals with a wide class of novel and efficient adaptive signal processing techniques developed to restore signals from noisy and degraded observations. These signals include those acquired from still or video cameras, electron microscopes, radar, x rays, or ultrasound devices, and are used for various purposes, including entertainment, medical, business, industrial, military, civil, security, and scientific applications.

In many cases useful information and high quality must be extracted from the imaging. However, often raw signals are not directly suitable for this purpose and must be processed in some way. Such processing is called signal reconstruction. This book is devoted to a recent and original approach to signal reconstruction based on combining two independent ideas: local polynomial approximation and the intersection of confidence interval rule.


Book Details

Date Published: 26 September 2006
Pages: 576
ISBN: 9780819460929
Volume: PM157

Table of Contents
SHOW Table of Contents | HIDE Table of Contents
Preface xi
Notations and Abbreviations xv
1 Introduction 1
1.1 Linear Local Approximation 2
1.1.1 Windowing 2
1.1.2 Nonparametric estimation 3
1.1.3 Scale 5
1.1.4 Ideal scale 8
1.1.5 Adaptive varying scale 9
1.2 Anisotropy 11
1.2.1 Univariate case 11
1.2.2 Multivariate case 12
1.3 Nonlinear Local Approximation 14
1.3.1 Likelihood and quasi-likelihood 14
1.3.2 Robust M-estimation 16
1.3.3 Adaptive varying scale 16
1.4 Multiresolution Analysis 17
1.5 Imaging Applications 17
1.6 Overview of the Book 18
2 Discrete LPA 21
2.1 Introduction 22
2.1.1 Observation modeling 22
2.1.2 Classes of signals 23
2.1.3 Multi-index notation 26
2.2 Basis of LPA 28
2.2.1 Idea of LPA 28
2.2.2 Windowing and scale 34
2.2.3 Estimate calculation 36
2.2.4 Multivariate estimates 37
2.2.5 Examples 38
2.3 Kernel LPA Estimates 47
2.3.1 Estimate of signal 47
2.3.2 Estimate of derivative 48
2.3.3 Reproducing polynomial kernels 48
2.4 Nonparametric Regression 50
2.4.1 Regression function 50
2.4.2 Nadaraya-Watson estimate 51
2.5 Nonparametric Interpolation 53
3 Shift-Invariant LPA Kernels 57
3.1 Regular Grid Kernels 57
3.2 Vanishing Moments 60
3.3 Frequency Domain 62
3.3.1 Frequency response 62
3.3.2 Discrete-Time Fourier transform 65
3.3.3 Vanishing moments 67
3.3.4 Discrete Fourier transform 68
3.3.5 Examples 71
3.4 Numerical Shift-Invariant Kernels 75
3.4.1 Square uniform window 76
3.4.2 Gaussian window 80
3.5 Numerical Differentiation 83
3.5.1 Univariate differentiation 84
3.5.2 Multivariate differentiation 87
4 Integral LPA 91
4.1 Integral Kernel Estimators 91
4.1.1 Integral LPA 91
4.1.2 Multivariate kernels and estimates 96
4.1.3 Limit LPA estimates 97
4.1.4 Frequency domain 97
4.2 Analytical Kernels 100
4.2.1 1D case 100
4.2.2 2D case 104
4.3 Generalized Singular Functions* 107
4.3.1 Gaussian smoothing kernels 107
4.3.2 Univariate Dirac delta function 108
4.3.3 Multivariate Dirac delta function 110
4.3.4 Dirac's delta sequences 111
4.4 Potential Derivative Estimates 114
5 Discrete LPA Accuracy 121
5.1 Bias and Variance of Estimates 122
5.1.1 Main results 122
5.1.2 Discussion 125
5.2 Ideal Scale 126
5.2.1 Varying scale 126
5.2.2 Invariant scale 131
5.2.3 Example 132
5.3 Accuracy of Potential Differentiators* 136
6 Adaptive-Scale Selection 137
6.1 ICI Rule 139
6.1.1 Foundations 139
6.1.2 LPA-ICI algorithm 145
6.1.3 Complexity 147
6.1.4 Convergence 147
6.1.5 Threshold adjustment 148
6.2 Multiple-Window Estimation 151
6.2.1 Multiwindow estimate 152
6.2.2 Combined-window estimate 153
6.3 Denoising Experiments 154
6.3.1 Univariate signals 154
6.3.2 Binary imaging 167
7 Anisotropic LPA 173
7.1 Directional Signal Processing 173
7.1.1 Recent developments 173
7.1.2 Directional LPA-ICI approach 180
7.2 Directional LPA 187
7.2.1 Polynomials 188
7.2.2 Directional windowing 189
7.2.3 Rotation 190
7.2.4 Calculations 193
7.2.5 Shift-invariant kernels 194
7.2.6 Frequency domain 196
7.3 Numerical Directional Kernels 198
7.3.1 Sectorial kernels 198
7.3.2 Line-wise kernels 205
8 Anisotropic LPA-ICI Algorithms 207
8.1 Accuracy Analysis* 207
8.1.1 Polynomial smoothness 207
8.1.2 Vanishing moments 211
8.1.3 Taylor series 212
8.1.4 Basic estimates 213
8.1.5 Rotated estimates 217
8.2 Adaptive-Scale Algorithms 219
8.2.1 Calculations 219
8.2.2 Recursive algorithms 221
8.2.3 Algorithm complexity 224
8.3 Directional Image Denoising 224
8.3.1 Criteria and algorithms 224
8.3.2 Experiments 227
8.4 Directional Differentiation 236
8.4.1 Anisotropic gradient 237
8.4.2 Examples 242
8.5 Shading from Depth 253
8.6 Optical Flow Estimation 256
8.6.1 Optical flow equation 257
8.6.2 Velocity estimation 259
8.6.3 Experiments 261
9 Image Reconstruction 263
9.1 Image Deblurring 264
9.1.1 Blur modeling and deblurring 264
9.1.2 LPA deblurring 267
9.2 LPA-ICI Deblurring Algorithms 273
9.2.1 ICI adaptive scale 273
9.2.2 Algorithms 274
9.2.3 Performance study 277
9.3 Motion Deblurring 280
9.4 Super-Resolution Imaging 282
9.5 Inverse Halftoning 285
9.5.1 Error diffusion 286
9.5.2 Linear model of error diffusion 287
9.5.3 Anisotropic deconvolution 289
9.5.4 Simulation results 291
9.6 3D Inverse 294
9.6.1 Sectioning microscopy 294
9.6.2 Observation model 295
9.6.3 3D spatially adaptive inverse 299
9.6.4 Simulation 304
10 Nonlinear Methods 307
10.1 Why Nonlinear Methods? 307
10.1.1 Basic hypotheses 307
10.1.2 M-estimation 309
10.1.3 Statistical approach 311
10.1.4 Some distributions 312
10.2 Robust M-Estimation 319
10.2.1 Median estimates 320
10.2.2 Performance of M-estimates 323
10.2.3 Median in Gaussian noise (simulation) 326
10.2.4 Theory of minimax estimation* 330
10.2.5 Median in non-Gaussian noise (simulation) 337
10.3 LPA-ICI Robust M-Estimates 339
10.3.1 Performance of LPA M-estimates 340
10.3.2 ICI algorithm for M-estimates 342
10.4 Nonlinear Transform Methods 343
10.4.1 Model simplification 343
10.4.2 Variance stabilization 345
11 Likelihood and Quasi-Likelihood 351
11.1 Local Maximum Likelihood 351
11.1.1 Parametric ML 351
11.1.2 Nonparametric ML 353
11.1.3 Theory for local ML 355
11.1.4 LPA-ICI algorithms 358
11.2 Binary and Counting Observations 361
11.2.1 Bernoulli regression 361
11.2.2 Poisson regression 364
11.3 Local Quasi-Likelihood 366
11.3.1 Parametric quasi-likelihood 367
11.3.2 Nonparametric quasi-likelihood 369
11.4 Quasi-Likelihood LPA-ICI Algorithms 371
11.4.1 Zero-order regression 371
11.4.2 High-order regression 372
12 Photon Imaging 379
12.1 Direct Poisson Observations 381
12.1.1 Anscombe transform 381
12.1.2 Local quasi-likelihood 382
12.1.3 Recursive LPA-ICI(AV) algorithm 382
12.1.4 Numerical experiments 386
12.2 Indirect Poisson Observations 390
12.2.1 ML pure inverse 390
12.2.2 Richardson-Lucy method 391
12.2.3 EM pure inverse 393
12.2.4 Regularized inverse 396
12.2.5 LPA-ICI filtering 397
12.3 Local ML Poisson Inverse 400
12.3.1 Local ML for indirect observations 400
12.3.2 Linear inverse plus LPA-ICI filtering 401
12.3.3 Numerical experiments 405
12.4 Computerized Tomography 407
12.4.1 Emission tomography 407
12.4.2 Transmission tomography 410
12.4.3 Adaptive LPA-ICI algorithms 422
13 Multiresolution Analysis 427
13.1 MR Analysis: Basic Concepts 427
13.1.1 Orthogonal series 428
13.1.2 Wavelets 430
13.2 Nonparametric LPA Spectrum 440
13.2.1 Finite-difference LPA spectrum 441
13.2.2 Linear independence 443
13.2.3 Gram-Schmidt orthogonalization 444
13.2.4 Orthogonal LPA spectrum analysis 445
13.2.5 Perfect reconstruction 446
13.2.6 MR analysis for differentiation 449
13.2.7 Examples of MR kernels 449
13.3 Thresholding 452
13.3.1 Basic concepts 452
13.3.2 Control of error rate 457
13.3.3 Image processing 458
13.4 Parallels with Wavelets 463
14 Appendix 467
14.1 Analytical Regular Grid Kernels 467
14.1.1 1D kernels 467
14.1.2 2D kernels 475
14.2 LPA Accuracy 480
14.2.1 Proof of Proposition 4 480
14.2.2 Proof of Proposition 7 481
14.3 ICI Rule 487
14.3.1 Proof of Proposition 10 487
14.4 Cross Validation 490
14.4.1 Basic approach 491
14.4.2 Algorithm 492
14.4.3 Shift-invariant kernels 495
14.5 Directional LPA Accuracy 496
14.5.1 Proof of Proposition 12 496
14.5.2 Convergence rate for signal estimation 502
14.5.3 Convergence rate for derivative estimation 506
14.6 Random Processes 510
14.6.1 Spectrum of random process 510
14.6.2 Minimization in frequency domain 512
14.6.3 Vector random processes 513
14.7 3D inverse 516
14.7.1 Regularized inverse 517
14.7.2 LPA regularized inverse 517
14.7.3 LPA regularized Wiener inverse 519
14.8 Nonlinear Methods 521
14.8.1 Proof of Proposition 13 521
14.8.2 Proof of Proposition 14 524
14.8.3 Proof of Proposition 15 529
References 535
Index 547

This book deals with a wide class of novel and efficient adaptive signal processing techniques developed to restore signals from noisy and degraded observations. Imaging provides a clear example of this type of problem. Digital images produced by a variety of physical units, including still/video cameras, electron microscopes, radar, x-rays, ultrasound devices, etc. are used for various purposes, including entertainment, medical, business, industrial, military, civil, security, and scientific. In today's computer networks, the number of circulating digital images is enormous and continues to increase rapidly. Digital images can become distorted for many reasons, such as blurring and changes in illumination, motion, and processing, including transmission, quantization, smoothing, compression, and geometric transformations.

In many cases useful information and high quality must be extracted from the imaging. However, often raw signals are not directly suitable for this purpose and must be processed in some way. Such processing is called signal reconstruction. This book is devoted to a recent and original approach to signal reconstruction based on combining two independent ideas: local polynomial approximation and the intersection of confidence interval rule. Local polynomial approximation is applied for linear and nonlinear estimation using a polynomial data fit in a sliding window. The window size, which is also interpreted as a scale, is one of the key parameters of this technique. The terms "window size," "bandwidth," and "scale" are synonymous here.

The local polynomial approximation is combined with an adaptive window size selection procedure called the intersection of confidence interval rule. The idea of this adaptation is as follows. The algorithm searches for the largest local area of the point of estimation where the local polynomial approximation assumptions fit well to the data. The estimates are calculated for a grid of window sizes and compared. The adaptive window size is defined as the largest of those windows in the set for which the estimate does not differ significantly from the estimators corresponding to the smaller window sizes.

In the approach considered in this book, the intersection of confidence interval rule defines the best scale for each point/pixel of the signal. In this way, we arrive at a varying adaptive-scale signal processing (imaging) with a pointwise adaptivescale selection. The adaptive estimator is always nonlinear, even for a linear local polynomial approximation, because the nonlinearity of the method is incorporated in the intersection of the confidence interval rule itself. It is proved that these adaptive estimators allow one to get a near-optimal quality of the signal recovery.

The local polynomial approximation (LPA) plus the intersection of confidence interval (ICI) rule is an efficient tool for signal (image) processing, especially for denoising, interpolation, differentiation, and inverse problems.

The local approximation (nonparametric regression) techniques considered here signify that no prior limit is placed on the number of unknown parameters used to model the signal. Such theories of estimation are necessarily quite different from traditional (parametric regression) statistical models with a small number of parameters specified in advance.

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 technique is a predecessor of wavelets. It demonstrates a tremendous breakthrough in adaptive methods overall. This current development is almost unknown to the signal processing community, which is mainly dominated by the wavelet paradigm.

In this book we present basic concepts, methodology, and theory of this modern, spatially adaptive (nonparametric-regression-based) signal and image processing. The advanced performance of the algorithms is illustrated by applications to various image processing problems.

We present and interpret the nonparametric regression LPA as a filter design technique.

The ICI adaptive-scale selection concerns adaptive neighborhood filtering. The ICI as well as the nonparametric regression approach overall admit the derivation of the adaptive algorithms from the optimization of the estimation accuracy. In this way we develop a regular approach to the adaptive neighborhood filtering design that is universally applicable to various problems.

We focus on material that we believe is fundamental and has a scope of applications that is not limited to solutions of specialized problems. Therefore, the book is prepared for a broad readership. To avoid mathematical technicalities, we prefer to postpone the presentation of proofs until the Appendix.

In addition to explanations of the formal mathematics required for background, all methods are discussed in light of their implementations and applications.

Local polynomial approximation is an old idea. However, when combined with the new adaptation technique, it becomes a novel and powerful tool. The new approach and new algorithms are mainly illustrated for imaging applications. However, they are quite general in nature and can be applied to any scalar or multidimensional data. These new methods can be exploited as independent tools as well as jointly with conventional techniques.

The emphasis of the book is on multivariate problems. However, the introduction guides the reader through the most important ideas and techniques relating to univariate signals.

The mathematics used in the book is motivated by and restricted to the necessity of making the ideas and algorithms clear. Its complexity remains at a level well within the grasp of college seniors and first-year graduate students who have had courses in mathematical analysis, vectors, matrices, probability, and statistics. All statements are explained in the text, and the proofs presented in the Appendix are not necessary for understanding the algorithms. The more formal mathematical sections marked by asterisks may be omitted on a first reading.

The book is written as a self-contained text and includes review comments on the basic literature in each of the subjects treated.

Numerical experiments are necessary to fully understand the algorithms and methods developed in this book.We provideMATLAB1 implementation of the basic algorithms presented as well as programs used in the illustrating examples. These programs are available at http://www.cs.tut.fi/~lasip. We support this software by updating the programs and including those programs that implement newalgorithms and methods.

We hope that readers will find this book highly valuable in their research, data processing and analysis, and data interpretation.

The primary target readers are researchers, engineers, and graduate and postgraduate students working in signal and image processing fields who develop and study methods and algorithms. We trust that the book will be interesting to those coming to the area for the first time as well as to readers who are more familiar with the field. The book can be useful for teaching in electrical engineering departments. The secondary beneficiaries of the book are readers who develop and use algorithms for specific applications, in particular, specialists working in the areas of signal and image processing, communications, geoscience and remote sensing, medicine, and biology imaging.

The aim of this book is to advocate the modern adaptive nonparametric techniques that have proven efficient for image and signal processing and to provoke further research in both theory and applications.

Many people have been of great help to our work on this book. In particular, we thank Professors Alexandre Tsybakov (University 6, Paris) and Vladimir Spokoiny (Weierstrass-Institute, Berlin) for fruitful discussions.

We especially thank our students, Alessandro Foi and Dmitry Paliy, for dedicated participation in the book project. We note the significant contribution of Alessandro Foi for developing ideas and algorithms for directional anisotropic and recursive image processing.

Tampere, Finland
April 2006

V. Katkovnik
K. Egiazarian
J. Astola


© SPIE. Terms of Use
Back to Top