### Spie Press Book

Local Approximation Techniques in Signal and Image ProcessingFormat | Member Price | Non-Member Price |
---|---|---|

GOOD NEWS! Your organization subscribes to the SPIE Digital Library. You may be able to download this paper for free. | Check Access |

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.

Pages: 576

ISBN: 9780819460929

Volume: PM157

- 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