Identification and Blind Restoration
by
Rachel Mabanag Chong
A dissertation submitted to the Graduate School of Engineering in partial fulfillment of the requirements
for the degree of
Doctor of Philosophy in Engineering
Department of Electrical and Electronic Engineering Tokyo University of Agriculture and Technology
March 2011
The technological improvements in cameras greatly increased the quality of acquired images. However, hardware limitations and imperfect settings still contribute to its degradation. The blind reconstruction of images involves the determination of the blurring function or point spread function (PSF) and the unblurred or original image. These methods usually assume that blurs are already present and involve processes that are computationally demanding and time consuming. In actual applications, images may not be blurred at all and bypassing reconstruction process can save time and increase processing efficiency. On the other hand when images are blurred, information from edges and transform domain are exploited in order to obtain good estimates of the unblurred image. In this work, it will be shown that extrema also contain information that can be utilized for blur detection, identification, and deconvolution.
The detection and identification of invariant blurs have been accom- plished using spectral nulls or edge information. A newly proposed method that exploits image extrema will be discussed here. This is based on how blurs affect the extrema locations and frequency. Statistical analyses will create the profile of an image and can be used in the detection and identi-
iii
fication processes. This method has been tested on various natural images with different orientations. In order to check the method’s performance, synthetic blurs of various types and degrees have been used. Furthermore, noise with increasing variance has been added to determine its robustness. Experimental results show that the method is effective in detecting blurs even in the presence of noise. Identification accuracy is also consistently high especially for Gaussian, horizontal motion, and out-of-focus (OOF).
Images degraded by motion blurs have most of its maxima locations aligned in the same direction as the motion. This characteristic is also exploited to determine the PSF model based only on the given image. As- suming that the PSF support size is already determined, motion direction is detected by selectively windowing the image based on the maxima loca- tions. Application of some practical PSF characteristics will yield a rough model. Further synthesis with Hough transform will result to the detection of one dominant motion direction. Experiments have been performed on grayscale as well as color images. Accuracy has been shown to be high with larger support sizes.
The PSF modeling by maxima exploitation can be considered as a pre- liminary step in blind deconvolution. Since it will yield a matrix that closely characterizes the PSF in an image, this can be utilized as a reference PSF (RPSF) during estimation. When PSF is being computed, RPSF is intro- duced as a training model. In this way, estimation is more efficient and at the same time less sensitive to noise. The cost function for the recon- struction consists of the fidelity term, total variation (TV) terms for image and PSF, and PSF learning term. It has three regularization parameters
that can be solved using a simpler method that is based on overdetermined system of linear equations. TV terms are expressed in vector-matrix no- tation and are reformulated for color images. Reconstruction experiments on images with synthetic and real blurs show improved image quality and good PSF estimation. Although the criterion for the selection of the regu- larization parameters are different for synthetic and real blurs, the results consistently showed promising results.
The proposed reconstruction method is iterative by nature and involves the selection of the estimated image from set. In this case, it is important to assess the image quality to ensure a reconstructed image that is visually better. Manual inspection is commonly done however, this is only practical for a few iterations. Objective assessment can also be used but most of these require the unblurred image, which is not available in actual applications. In this work, pixel variance and maxima kurtosis of images are utilized for the comparison of images. This can be accomplished by investigating their relationships with those having various degrees of blur. Experimental results show that these are consistent for natural images. The proposed criterion is then applied for the selection of the PSF size, regularization parameters, and the final estimated image. Experiments with synthetic and real blurs show some promising results.
Thanks be to God for his ineffable gift. [2 Corinthians 9:15]
This work would not have been possible without the guidance of my academic supervisor, Dr. Toshihisa Tanaka. I am very grateful for his advice and support that have opened new gates of opportunities and expe- riences. My deepest gratitude also goes to the doctoral committee chaired by Dr. Hitoshi Kitazawa and its members Dr. Masatoshi Sekine, Dr. Aki- nobu Shimizu, and Dr. Ikuko Shimizu. Their questions, comments, and suggestions have greatly helped in the improvement of this work.
I would like to extend my grateful acknowledgement to the Japan Min- istry of Education, Culture, Sports, Science and Technology (MEXT) for their financial support throughout my academic life here in Tokyo. Living in Japan has been more enjoyable through the assistance and guidance of the international center’s staff and Japanese language teachers in Tokyo University of Agriculture and Technology (TUAT). The success of my re- search activities is also credited in part by the financial aid of the Support Center for Advanced Telecommunications Technology Research (SCAT).
Many thanks to Dr. Nicanor Buenconsejo, Jr. for his encouragements. Not to be missed are the help that I have received in many forms from my
vii
colleagues and friends in Cebu Institute of Technology (CIT) specifically the department of Electronics and Communications Engineering (ECE) headed by Engr. Susana A. Tan. My warmest gratitude to my parents, family, and relatives for their love and support especially when I needed it the most. A special mention to my mother, Maximiana Mabanag Chong for nurturing me in my quest for knowledge and my older sister, Miera Mabanag Chong for being my inspiration.
To my long time friends in the Philippines and new found ones in Japan thank you so much for cheering me on when I am down. Special thanks to Ms. Kanako Makino for her patience and assistance especially when I was still settling in Tokyo. Last but definitely not the least, my heartfelt gratitude to my fellow laboratory members for their constant willingness to help and to those that I may have not mentioned but have helped me in one way or another.
I give thanks to my God, with every remembrance of you, always, in all my prayers, making supplication for all of you with joy, [Philippians 1:3-4]
Abstract iii
Acknowledgements vii
List of Tables xiii
List of Figures xv
Nomenclature and Symbols xix
1 Introduction 1
1.1 Background . . . 1
1.2 Scope of the Dissertation . . . 10
1.3 Research Goals . . . 11
1.4 Organization of Dissertation . . . 12
2 Preliminary Concepts 15 2.1 Degraded Images . . . 16
2.2 Parametric Blur Models . . . 19
2.3 Blur Detection and Identification: An Overview . . . 32 ix
2.3.1 Detection with Edges . . . 33
2.3.2 Detection in the Transform Domain . . . 38
2.3.3 Identification in the Spatial Domain . . . 38
2.3.4 Identification in the Transform Domain . . . 41
2.3.5 Detection and Identification in the Frequency Domain 42 2.4 Image Reconstruction: An Overview . . . 43
2.4.1 Classical Iterative Reconstruction Methods . . . 46
2.4.2 Iterative Restoration with Alternating Transformations 48 2.4.3 A New Norm for Iterative Restoration . . . 51
2.5 Quality Assessment Measures . . . 52
3 Blur Detection and Identification with Image Extrema 57 3.1 Introduction . . . 57
3.2 Feature Extraction . . . 62
3.3 Image Discrimination . . . 64
3.4 Experimental Results . . . 65
3.4.1 Description of Experiments . . . 65
3.4.2 Data and Results . . . 70
3.5 Summary . . . 73
4 Blind Deconvolution and Image Maxima Exploitation 75 4.1 Introduction . . . 75
4.2 Smoothness Term: Total Variation (TV) . . . 77
4.2.1 Grayscale . . . 78
4.2.2 Multichannel . . . 80
4.3 PSF Learning from RPSF . . . 81
4.4 Alternating Minimization . . . 86
4.5 Experimental Results . . . 88
4.5.1 Experiment Descriptions . . . 88
4.5.2 Data and Results . . . 91
4.6 Summary . . . 96
5 An Objective Criterion for Comparing Images 111 5.1 Introduction . . . 111
5.2 Image Pixels and Maxima . . . 113
5.3 Experimental Results . . . 117
5.3.1 Experiment Descriptions . . . 117
5.3.2 Data and Results . . . 118
5.4 Summary . . . 126
6 Conclusions and Open Problems 129 6.1 Conclusions . . . 129
6.2 Open Problems . . . 131
A Selection of Regularization Parameters 133
Bibliography 137
List of Publications 151
2.1 Blur detection and identification methods. . . 34
3.1 Comparison of detection accuracy. . . 71
3.2 Comparison of classification accuracy. . . 72
3.3 Details of the classification accuracy for IEXA1. . . 72
3.4 Details of the classification accuracy for IEXA2. . . 72
4.1 Regularization parameters for Expt 1: motion blurs. . . 90
4.2 Regularization parameters for Expt 1: OOF. . . 91
4.3 Regularization parameters for Expt 2. . . 92
4.4 Expt A: Accuracy of detecting the motion direction. . . 93
4.5 Expt B: Accuracy of detecting the motion direction. . . 93
4.6 Expt C: Direction of motion identification accuracy (%) for different PSF sizes. . . 94
4.7 Expt C: Direction of motion identification accuracy (%) for different motion directions. . . 98
4.8 Maximum PSNR for Expt 1: motion blurs (without noise). . 99
4.9 Maximum PSNR for Expt 1: OOF (without noise). . . 102 xiii
4.10 Corresponding MSE for Expt 1: Images 1 and 2 (motion blur
without noise). . . 103
4.11 Corresponding MSE for Expt 1: Image 3 (motion blur with- out noise). . . 104
4.12 Corresponding MSE for Expt 1: OOF (without noise). . . . 104
4.13 Maximum PSNR for MXB in Expt 1: Images 1 and 2 (motion with noise). . . 105
4.14 Maximum PSNR for MXB in Expt 1: Image 3 (motion blur with noise). . . 106
4.15 Corresponding MSE for MXB in Expt 1: Image 1 (motion blur with noise). . . 107
4.16 Corresponding MSE for MXB in Expt 1: Image 2 (motion blur with noise). . . 108
4.17 Corresponding MSE for MXB in Expt 1: Image 3 (motion blur with noise). . . 109
5.1 Conditions for experiments 1 and 2. . . 118
5.2 Condition consistency with image pixels (%). . . 120
5.3 Condition consistency with maxima values(%). . . 120
5.4 Experiment 3: Selection of PSF size and regularization pa- rameters using maximum vk. . . 126
1.1 Reconstruction of bar code images in [2]. . . 3
1.2 Reconstruction of 2D bar code images in [7]. . . 3
1.3 From left to right: original fingerprint, reconstructed finger- print, and overlay of the two images as shown in [8]. . . 4
1.4 Reconstruction for iris recognition systems in [9]. . . 5
1.5 Reconstruction of facial images in [12]. . . 6
1.6 Degraded image (top) and its reconstructed version (bottom) using the method in [13]. . . 7
1.7 Reconstruction of satellite images in [14]. . . 8
1.8 Restoration system proposed in [15]. . . 9
1.9 Relationship between chapters. . . 13
2.1 Image with no blur. . . 21
2.2 Image with Gaussian blur. . . 23
2.3 Image with 0o motion blur. . . 25
2.4 Image with 45o motion blur. . . 26
2.5 Image with 90o motion blur. . . 27
2.6 Image with 135o motion blur. . . 28 xv
2.7 Image with OOF blur. . . 30
2.8 Image with rectangular blur. . . 31
2.9 Wavelet decomposition. . . 35
2.10 Edge Structures. . . 37
2.11 Iterative method by Ayers and Dainty [54]. . . 50
3.1 Sample plots of extrema values in a row. . . 59
3.2 Example of an unblurred image. . . 60
3.3 Example of a Gaussian blurred image. . . 61
3.4 Changes in accuracy with additive Gaussian noise. . . 66
3.5 Sample test images: unblurred and Gaussian . . . 67
3.6 Sample test images: motion and OOF . . . 68
4.1 Maxima locations for images degraded by HM. . . 83
4.2 Maxima locations for images degraded by VM. . . 84
4.3 Overall motion direction identification accuracy. . . 95
4.4 Reconstruction of Image 2 degraded by a synthetic blur with L= 5 and θ = 0o. . . 97
4.5 Reconstruction of Image 1 degraded with a 3 × 3 OOF. . . . 98
4.6 Reconstruction with a real blur: Image 4. . . 100
4.7 Reconstruction with a real blur: Image 5. . . 101
5.1 An unblurred image. . . 115 5.2 Variances and kurtoses for OOF degraded versions of Fig. 5.1.116 5.3 Reconstruction of an image degraded with a 3×3 OOF (s = 3).121
5.4 Reconstruction of an image degraded with a 0◦, L= 3 motion (s = 7). . . 122 5.5 Reconstruction of an image degraded with a 90◦, L= 5 mo-
tion (s = 3). . . 123 5.6 Reconstruction with a real blur: Image 4. . . 124 5.7 Reconstruction with a real blur: Image 5. . . 125
Terms: Definitions or synonyms
blur domain - refers to the vector-matrix form of the degradation model where only the image is in Toeplitz matrix form
blurring function - also known as point spread function (PSF) or blurring operator
blurry image - also known as the blurred or degraded image
deconvolution - also known as deblurring, restoration, reconstruction
distance - the number pixels between extrema values
image domain - refers to the vector-matrix form of the degradation model where only the blurring function is in Toeplitz matrix form
lexicographical order - refers to the rearrangement of the elements in a matrix by scanning it from left to right and top to bottom in order to produce its vector form
plateau - the number of consecutive extrema values xix
rastering - scanning an image from left to right and from top to bottom
spatial domain - the image space where the pixel value is a function of its two-dimensional locations
support - the space occupied by a quantity such as the image and the blurring function in the spatial domain
unblurred image - also known as the original image or estimated image since a perfectly unblurred image is unattainable in most cases
Acronyms
AD - Ayers and Dainty
AM - Alternating Minimization
AMD - Absolute Mean Difference
ARMA - AutoRegressive Moving Average
BCCB - Block-Circulant Circulant-Block
BD - Blur Detection
BDHWT - Blur Detection with Haar Wavelet Transform
BPI - Blur Parameter Identification
BSNR - Blurred Signal to Noise Ratio
BTI - Blur Type Identification
CG - Conjugate Gradient COC - Circle Of Confusion Corr - Correlation coefficient FIR - Finite-Impulse Response FR - Full Reference
HH - horizontal High-pass and vertical High-pass HL - horizontal High-pass and vertical Low-pass HM - Horizontal Motion
HWT - Haar Wavelet Transform IBD - iterative blind deconvolution ICM - Iterated Conditional Modes IEXA - Image EXtrema Analysis
ISNR - Improvement in Signal to Noise Ratio LH - horizontal Low-pass and vertical High-pass LL - horizontal Low-pass and vertical Low-pass MAAD - Maximum Average Square Difference MAE - Mean Absolute Error
MASD - Maximum Average Square Difference
MAX - Maximum Absolute Error
MSE - Mean Square Error
NR - No Reference
PSF - Point Spread Function
OOF - Out-Of-Focus
OSLE - Overdetermined System of Linear Equations
PSNR - Peak Signal to Noise Ratio
RBE - Reinforcement Blur Estimation
RMSE - Root Mean Square Error
ROF - Rudin, Osher, and Fatemi
RPSF - Reference Point Spread Function
RR - Reduced Reference
SNR - Signal to Noise Ratio
VC - Van Crittert
VM - Vertical Motion
WT - Wavelet Transform
List of Symbols
The list below are the symbols used in various mathematical equations throughout this dissertation. The description enclosed by a parenthesis is its alternate usage in a particular chapter or section.
∇ - gradient
˜· - transform domain
¯· - mean value ˆ· - estimated value
∗ - two-dimensional convolution
| · | - absolute value
|| · || - Euclidean norm
α - regularization parameter for PSF smoothness term
β - regularization parameter for PSF learning term (parameter for the method indicated by its subscript in Chapter 2)
γ - additional TV parameter
ǫ - bounding error for the norm of the noise ε- auxiliary variable introduced for TV η - number of binary masks
θ - motion direction in degrees
λ - regularization parameter for image smoothness term µ - mean of image pixels
ξ - standard deviation ρ - selected PSF parameter σ - Gaussian blur parameter ς - noise variance
τ - kurtosis
χ - image rows in the transform domain (vector of unknown values in Appendix A)
ψ - image columns in the transform domain ω - normalizing constant
Θ - a set of blur parameters Ω - image support
a - ratio between the pixel sum of g and ˆf
b - number of bits used in representing an image pixel
c - column-wise direction (vector of given values in Appendix A) d - distance between extrema values
f - original image in vector form
g - degraded image in vector form
h - PSF in vector form (extrema histogram in Chapter 3) i - histogram index
k - iteration count (kurtosis in Chapter 5)
m - used as subscript that indicates matrix form in spatial domain (sub- script that indicates computation with maxima values in Chapter 5) n - noise in vector form (minima in Chapter 3)
o - binary mask
p- index of PSF rows (plateau in Chapter 3; horizontal shift parameter in Section 2.3.3; subscript that indicates computation with pixels values in Chapter 5)
q - index of PSF columns (vertical shift parameter in Section 2.3.3) r - RPSF (OOF radius in Chapter 2 and row-wise direction in Chapter 3) s - number or rows/columns of a square sized PSF (amount of spread in a
rectangular blur in Chapter 2)
t - selected parametric PSF model for RBE
u - subscript that indicates an unconstrained quantity v - variance
w - window from an image (weighting or apodization function in Chapter 2)
x - index of image rows (maxima in Chapter 3)
y - index of image columns
z - index of maxima locations (index of the PSF support size in Chapter 5)
A - matrix of coefficients
B - blue channel
C - colors or channels in an image
E - integral of the difference between original and estimated image
E(·) - expectation operator
F - original image in Toeplitz matrix form
G - green channel
H - PSF in Toeplitz matrix form
I - identity matrix
K - total number of iterations (Gaussian normalizing constant in Chapter 2 and class categories in Chapter 3)
L - motion length in pixels
N - total number of pixels in an image
O - zero matrix
P - total PSF rows Q - total PSF columns R - red channel
S - admissible solution set in Tikhonov-Miller regularization (histogram domain in Chapter 3)
T - matrix transpose
V - gradient operator matrix
W - a matrix whose diagonal elements are the inverse of the gradients X - total image rows
Y - total image columns
Z - total number of maxima in an image
Introduction
1.1 Background
Images are two-dimensional signals that convey a lot of information. The advancement of technology further increases its potential use in emerging technologies. Despite improved imaging systems, these are still plagued by several degradations that are introduced by imperfect acquisition systems or by the environment itself. Degradations are usually unavoidable and come in many forms with noise and blur as the most studied. Blurs render images useless since it makes image understanding difficult or impossible. Due to the wealth of information that images contain, researches have been attempting to remove blurs for decades. This process is known as image restoration or reconstruction. It has been used in various fields of applica- tions. Several methods have been proposed for bar codes [1, 2, 3] and 2D bar codes [4, 5, 6, 7]. Blurs can occur during image acquisition as shown in Figures 1.1(a) and 1.2(a). These make the interpretation of the codes diffi-
1
cult and erroneous. To solve these problems, restoration techniques are first applied resulting to a clearer representation of the codes as shown in Fig- ures 1.1(a) and 1.2(a). These techniques are also required in biometrics such as fingerprint identification [8], iris recognition [9], and face identification [10, 11, 12]. Figures 1.3 to 1.5 show that reconstruction is also important for proper identification just like the bar codes. Other fields of applications include forensics [13] and satellite image analysis [14]. These mainly use restoration in the preprocessing stages in order to get more details. Figures 1.6 and 1.7 show some examples of these applications. In the previously dis- cussed applications, images are first acquired before restoration is applied. In contrast to this, reconstruction is applied on the raw color components in [15] due to the fact that the camera itself introduce the degradation. Its concept is summarized by the diagram shown in Figure 1.8.
Most of the reconstruction algorithms that has been presented assume that blurs are always present. However, this is not the case in real appli- cations. Subjecting an unblurred image to reconstruction will only waste resources like computation time and load. In line with this, the image must first be preprocessed with a blur detection method. Some methods are based on edge information [16] or frequency domain characteristics [17, 18, 19, 20]. A downside to these is its restrictiveness towards image size and orientation. Aside from this, most edge-based methods are only limited to detection and are not capable of identifying the type of degradation. Transform-based methods have promising results but are mostly applicable to non-Gaussian types since these exploits the null patterns. In this work, these limitations can be overcome by using the characteristics of image extrema. This method
(a) degraded image
(b) reconstructed image
Figure 1.1: Reconstruction of bar code images in [2].
(a) degraded image (b) reconstructed image (c) reconstructed code
Figure 1.2: Reconstruction of 2D bar code images in [7].
Figure 1.3: From left to right: original fingerprint, reconstructed fingerprint, and overlay of the two images as shown in [8].
can be applied to images with different sizes and orientation. Additional parameters or settings are not necessary and different types of degradations can be included.
Once the presence of blur is already detected, reconstruction can then follow. This is the process of extracting the unblurred image from a given degraded one. It also involves the identification of the PSF model, which is usually assumed to be parametric. This may be known apriori or not de- pending on the reconstruction algorithm. It can also be shown that image maxima can also be exploited to model the embedded PSF in a degraded image. This can aid to a better estimation of the unblurred image with min- imal inputs from the user. Classical approaches are discussed and compared in [21, 22, 23, 24, 25, 26].
(a) degraded images at 11mm (left) and 24mm (right)
(b) reconstructed versions of 1.4(a)
(c) degraded images at 50mm (left) and 63mm (right)
(d) reconstructed versions of 1.4(c)
Figure 1.4: Reconstruction for iris recognition systems in [9].
the
using
(a) Faces with real blur
(a) degraded images(b) Faces deblurred using FADEIN
(b) reconstructed imagesFigure 1.5: Reconstruction of facial images in [12].
Figure 1.6: Degraded image (top) and its reconstructed version (bottom) using the method in [13].
(a) degraded image
(b) reconstructed image
Figure 1.7: Reconstruction of satellite images in [14].
ter1.Introduction9
Camera optics
Component blurring CMOS sensor
Original scene
Restoration (R)
Restoration (G)
Restoration (B) Saturation
control
Image
reconstruction functions: - CFAI - AWB
- Noise filtering - Sharpening - etc...
sensor plane
PSF, (R) PSF, (G) PSF, (B)
R G1
G2 B
R G1
G2 B R G1
G2 B
R G1
G2 B
Bayer matrix
sampling pattern
Output image
Figure1.8:Restorationsystemproposedin[15].
1.2 Scope of the Dissertation
This section will discuss what will be covered in this work. Since the field of image reconstruction has been studied for decades, a large number of meth- ods have already been proposed and improved. These differ on assumptions, types of PSFs, cost functions, estimation approaches, and others. Thus, in this section the scope and limitations will be described in detail. This also includes the general experimental conditions and the practical assumptions since there are many possible settings such as type of imaging system, image and PSF sizes, among others.
This dissertation deals with the discrete imaging systems. In the real world, original signals are continuous by nature. However, we are consid- ering digital sensors in cameras. Thus, all models are expressed in their approximate digital forms. In particular, a consumer digital camera is used to capture the images that are used in the experiments. These images are captured from natural scenes. Due to the nature of the imaging system, all the image pixels and PSF elements are real, positive, and finite. Ac- quired images are inherently colored thus, we consider the grayscale and multichannel case. For grayscale images, we process only the green channel since this is most detectable to the eye. Additionally, it is assumed that the PSFs are the same for each color channel since the camera uses Bayer filter mosaic. For practical purposes, common characteristics of the blurring function discussed in chapter 2 will also be considered. These facilitates the convergence of alternating minimization (AM) to useful estimates [27]. All PSFs in this work can be modeled mathematically namely, Gaussian, mo-
tion, and out-of-focus (OOF) blurs. These have odd numbered support sizes that are smaller than the image. Finally, blind deconvolution methods will focus on iterative methods specifically those that concern with regulariza- tion of a cost function. Although direct methods have also been proposed, iterative ones have been chosen due to its numerous advantages that will be discussed in the next chapter.
1.3 Research Goals
The main goal of this work is to present a reconstruction algorithm that is robust in the presence of noise. In order to achieve this, specific objectives are added as follows:
• avoid unnecessary image reconstruction by creating a method that detects the presence of blur
• determine this method’s accuracy for various settings such as PSF support size and noise intensity
• design an algorithm that can roughly represent the embedded blur function in an image using only the image itself
• test the accuracy in representing the PSF using synthetically blurred images
• use this representation for image reconstruction by incorporating it on the cost function
• quantitatively evaluate the estimated values for images with artificial and real blurs
1.4 Organization of Dissertation
This dissertation is divided into six chapters. In Chapter 1, some back- ground information regarding this work is discussed. The scope and limi- tations are described and the research goals are also mentioned. Chapter 2 will tackle the preliminary concepts that are important towards understand- ing the consecutive chapters. This is followed by the different techniques for detecting and identifying blurs. Methods for determining the PSF support size is then presented. Chapter 3 shows the technique for blur detection and classification specifically for Gaussian, horizontal motion, and OOF blurs. This involves the analyses of extrema location and quantity to ex- tract feature values that are effective in differentiating various types of blurs. Chapter 4 presents a method for modeling a PSF using only the maxima values. This is applicable for motion and OOF where for the former case Hough transform is employed to remove direction ambiguities. The model is then integrated to a learning based deconvolution effectively eliminat- ing the need for a learning set. The estimated images are then objectively compared by the method in Chapter 5. Lastly, Chapter 6 summarizes the important points discussed in this work.
Figure 1.9: Relationship between chapters.
Preliminary Concepts
This chapter discusses some basic concepts that are essential to understand- ing the consecutive chapters in this work. This begins with the presenta- tion of the different degradation models and some of the pertinent bound- ing conditions. An examination of the parametric blur models will follow. This includes the discussion on commonly used constraints for these mod- els. Their characteristics in the spatial domain are shown and their effects on the image spectrum are illustrated. This is followed by an overview of the image reconstruction algorithms where the general types are briefly discussed. Lastly, some methods, which will be used for evaluating the qual- ity of estimation, are presented. These are the assessment techniques that quantitatively compare the results of the different deconvolution algorithms under consideration.
15
2.1 Degraded Images
Images can be degraded in many ways. Common forms are the noise and blur where the latter will be the focus of this study. Blurs may be caused by the environment or the image acquisition system itself. Environmental factors may include atmospheric turbulence, movements, and other ambient settings. On the other hand, limitations of the image acquisition system can also cause blurs. Examples of which are lens imperfections and shutter speed limits.
In the spatial domain, acquired images that are degraded can be modeled by a two-dimensional convolution,
gm(x, y) = fm(x, y) ∗ hm(x, y) + nm(x, y)
= X
∀(p,q)
fm(p, q)hm(x − p, y − q) + nm(x, y) (2.1)
where g, f , h, and n are variables representing the degraded image, original or unblurred image, blurring function, and noise, respectively. The variables p, q, x, and y are the locations and the subscript m indicates the matrix form in the spatial domain. The symbol ∗ denotes two-dimensional convolution operation. In this equation, the blurring function or otherwise known as point-spread function (PSF) is assumed to be spatially invariant. This means that the whole image is degraded by the same PSF. The variables in equation (2.1) are bounded by the following conditions:
1. Images and noise have real values,
{gm(x, y), fm(x, y), nm(x, y)} ∈ RX×Y∀(x, y) (2.2)
where X × Y indicates the images size.
2. PSF elements are real,
hm(p, q) ∈ RP ×Q∀(p, q) (2.3)
where P × Q is the PSF support size.
3. Locations are positive integer values i.e.,
(p, q) ∈ Z≥, (x, y) ∈ Z>. (2.4)
The convolution operation can be implemented at a faster rate using the Fourier transform. Some blur identification and image restoration methods exploit the Fourier or Z transform domains. In this case, the convolution process is mathematically modeled by
˜
gm(χ, ψ) = ˜fm(χ, ψ)˜hm(χ, ψ) + ˜nm(χ, ψ) (2.5)
where ˜· indicates transformed quantity and (χ, ψ) are locations in the trans- form domain.
In vector-matrix form, image degradation in the image domain can be
represented by
g = Hf + n (2.6)
or equivalently
g = F h + n (2.7)
in the blur domain. The terms image and blur domain are used in [28] to indicate the quantity being estimated and the direction to which the reconstruction cost function is being projected. In this work, these terms and representations will also be adopted to make derivations more succinct. In equations (2.6) and (2.7), the small letters represent lexicographically ordered vectors while capital letters are Toeplitz matrices constructed from their corresponding quantities in equation (2.1 ). For multichannel systems with C channels, the small lettered variables consist of concatenations of the component channel vectors [29]. In the case of color images, the color components or channels are red, green, and blue i.e., C ∈ {R, G, B}. Thus,
g =
gR
gG
gB
, f =
fR
fG
fB
, n=
nR
nG
nB
. (2.8)
On the other hand, the PSF Toeplitz matrix becomes
H =
HRR HRG HRB
HGR HGG HGB
HBR HBG HBB
(2.9)
where the diagonal blocks are within-channel degradations and the off- diagonal blocks are between-channel degradations [29].
The image deconvolution problem is concerned with knowing the un- blurred image and PSF given the degraded image. Based on these equa- tions, the unblurred image can be easily determined when the models for the degraded image and PSF are known. However, this is not the case in actual applications. Images cannot be modeled in a straightforward manner thus, their features and properties are usually utilized. For some applications, probability models are created based on the imaging conditions and type of scenes [30]. On the other hand, blurring functions can be mathematically modeled. Exploiting the characteristics of these models can decrease the complexity of determining the unblurred image. The next section discusses some constraints and common types of blurring functions that have been studied in several deconvolution methods.
2.2 Parametric Blur Models
Blurring operators in a shift-invariant image degradation system are usually modeled analytically. These satisfy three constraints [25]:
1. non-negative values due to the physics underlying the image formation process,
2. real-valued when images are also real-valued,
3. passive operators such that the degradation process do not absorb or
generate energy, i.e.,
X
∀(p,q)
hm(p, q) = 1. (2.10)
The rest of this section will discuss the commonly used blurs used in simulations and algorithm evaluations. Their mathematical models as well as their corresponding parameters will also be presented.
1. No blur
Images that do not exhibit any degradation have no blur. This means that the blurring function is a Dirac delta function. For discrete imag- ing systems, this is approximated by a unit impulse [25]. Thus,
hm(p, q) = δ(p, q) =
1, p = q = 0 0, otherwise
. (2.11)
This indicates that the PSF did not spread out the image pixel values. An example of unblurred image is shown in Figure 2.1. The color image is in Figure 2.1(a) where the convolved PSF is in Figure 2.1(b). The green channel for the image is extracted and shown in Figure 2.1(c) with its corresponding Fourier transform in Figure 2.1(d). It can be observed that in the frequency domain significant components are scattered within the spectrum.
2. Gaussian blur
This type is generally used to model a variety of devices such as cam- eras and optical scopes. In remote sensing and aerial imaging appli- cations, blurs are caused by several factors such as temperature and
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.2 0.4 0.6 0.8 1
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.1(c)
Figure 2.1: Image with no blur.
wind speed among others. For long-term atmospheric exposure, the Gaussian model is usually used. As a result, the term atmospheric turbulence blur is also used in some literatures. Mathematically, this can be defined by
hm(p, q) = K exp
−p
2+ q2
2σ2
(2.12)
where K is a normalizing constant that ensures that equation (2.10) is satisfied and σ is the variance. An image degraded by Gaussian blur is shown in Figure 2.2. In this example, σ = 1.66 and the spread is based on 6σ. In the frequency domain, significant components are mostly concentrated in the lower frequencies.
3. Uniform/Linear Motion blur
This can be observed when the camera or object is moving faster than the camera’s exposure period. For spatially invariant cases, global translation is the most distinguishable effect on the degraded image. This is frequently used with frequency based blur identification and deconvolution algorithms since this is characterized by frequency do- main zeros. It is generally modeled by
hm(p, q) =
1
L, pp2+ q2 < L
2 and p cos θ = q sin θ
0, otherwise
(2.13)
where L is the motion length in pixels and θ is the angle between motion orientation and horizontal axis in degrees. The term horizontal
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.01 0.02 0.03 0.04 0.05 0.06
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.2(c)
Figure 2.2: Image with Gaussian blur.
motion (HM), which is more commonly encountered and used, results when θ = 0. This simplifies equation (2.13) into
hm(p, q) =
1
2L, −L ≤ p ≤ L and q = 0
0, otherwise
(2.14)
In this condition, the frequency domain zeros are located on lines perpendicular to the direction of blur with a spacing determined by L. Images blurred with motion in different directions are shown in Figures 2.3 through 2.6. The parameters are set as L = 7 and θ = {0o,45o,90o,135o}. The frequency domain plots show that the significant components are concentrated mostly on the direction per- pendicular to the motion.
4. Out-of-Focus blur (OOF)
This is typically observable as defocusing in imaging systems. It is caused by the finite size of the camera’s aperture that is assumed to be circular. Thus, a small disk, known as circle of confusion (COC), can be used to describe the image of a point source. A detailed discussion on the relationship between COC, object distance, and lens diameter can be found in [21]. Based on this, the discrete PSF approximation can be expressed as
hm(p, q) =
1
πr2, pp2+ q2 ≤ r 0, otherwise
(2.15)
where r is the radius of the COC. The equation indicates that intensity
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.05 0.1 0.15 0.2
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.3(c)
Figure 2.3: Image with 0o motion blur.
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.05 0.1 0.15 0.2
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.4(c)
Figure 2.4: Image with 45o motion blur.
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.05 0.1 0.15 0.2
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.5(c)
Figure 2.5: Image with 90o motion blur.
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.05 0.1 0.15 0.2
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.6(c)
Figure 2.6: Image with 135o motion blur.
values must be constant and nonzero within COC and must be zero elsewhere. This blur also exhibits frequency domain zeros that can be observed as concentric circles about the origin and is nearly periodic depending on r. An image degraded with OOF is shown in Figure 2.7 with a COC diameter set to 7. In the frequency domain, the significant components are concentrically located. Slightly observable are the spectral zero patterns at higher frequencies.
5. Rectangular blur
This is also known as pillbox or uniform 2D blur. It is used in many simulations and sometimes utilized as a crude approximation of defo- cus blur. It also models sensor pixel integration especially in applica- tions dealing with superresolution restoration. It is modeled by
hm(p, q) =
1
s2, |p| < 2s and |q| < 2s 0, otherwise
(2.16)
where s is the size of the smoothing area. The image in Figure 2.8 is degraded with rectangular blur. Since this blur is a crude approx- imation of OOF, the characteristics of the image in the spatial and transform domain are closely similar to Figure 2.7.
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.005 0.01 0.015 0.02 0.025 0.03 0.035 0.04
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.7(c)
Figure 2.7: Image with OOF blur.
(a) RGB image
-6 -4
-2 0
2 4
6
q -6
-4 -2 0 2 4 6
p 0 0.005 0.01 0.015 0.02 0.025
h
(b) PSF
(c) G channel (d) Fourier Transform of 2.8(c)
Figure 2.8: Image with rectangular blur.
2.3 Blur Detection and Identification: An
Overview
Image deconvolution usually involves processes which are computationally demanding and time consuming. Majority of these methods such as those in [22, 23, 24, 25] exploit the characteristics of a certain blur to reconstruct the original image thus it is always assumed that the given image is degraded by the blur under consideration. In contrast, there are instances during actual applications that images are not blurred at all. In this case, bypassing the restoration process can save time and increase processing efficiency. Aside from this, blur detection can also be used to systematically evaluate the restored images in an iterative algorithm wherein there are several possible solutions. The presence of blurs can be achieved either by hard or soft de- tection techniques. Hard detection is the process of recognizing whether an image is blurred or not. This group of methods extract certain features and employ classifiers to distinguish images. In contrast, soft detection measures the amount of degradation without a definite criteria for classification. This is closely related to some image quality assessment methods wherein evalu- ation is based on the blur that is present. In this case, a numerical value is used to compare images.
Aside from detection, other algorithms are also studied to determine the type of degradation. This refers to blur identification and may involve the determination of the specific blur type, its parameters or both. For blurred images, the proper classification of its degradation can help in the selection for the appropriate deconvolution method thereby resulting to a more ef-
fective reconstruction. This section will discuss some specific methods that detect and/or identify blurs. These methods are grouped according to the image feature that is being exploited. Its details are described below and a brief comparison is shown in Table 2.1.
2.3.1 Detection with Edges
It has been shown that image blur is perceived due to the loss of structures in images or in other words it has a smoothing effect on edges. Thus, the detection of blurs can be attempted by investigating the properties of edges. It has been shown that wavelets can be used to characterize the local shape of irregular structures [43]. This has been exploited by several works to detect and measure the presence of blurs.
The smoothness measure can be computed using the sharpest edge in the wavelet domain[31]. Two-dimensional Haar wavelet is first calculated either by standard or non-standard decomposition as discussed in [44]. In most cases, the scale of decomposition is set to three. Figure 2.9 shows the resulting sub-bands of the image where H stands for high-pass, L for low-pass, and the subscript for the decomposition scale. The first letter characterizes the filter for the horizontal direction while the second for the vertical direction. Transitions are determined by gradients above an empir- ically determined threshold. These gradients are extracted from the wavelet coefficients in the highest resolution scale. Using the significant gradients, Lipschitz exponents are determined and then plotted in a histogram. The presence of blur is then determined through the histogram maximum and
34Chapter2.PreliminaryCon
Table 2.1: Blur detection and identification methods.
Basis of the Method Proponents Image PSF(s) Tested Output(s) gradients from wavelet coefficients [31] grayscale Gaussian, OOF soft BD
edge spread using [32, 33] luminance Gaussian soft BD
vertical Sobel filter
edge activity from high [10] grayscale rectangular soft BD
frequency wavelet coefficients
edge analysis using [16] grayscale unblurred, motion, BD and
wavelet coefficients OOF blur extent
gradient magnitude [34] RGB OOF soft BD
kurtosis of wavelet details [35] grayscale rectangular soft BD kurtosis of image pixels [36] grayscale Gaussian and OOF support size
spatial gradients [37] grayscale Gaussian support size
residual spectrum [38] grayscale Gaussian, motion, BPI
OOF
power cepstrum [39] grayscale same as above BPI
cepstrum null patterns [40] grayscale motion, OOF BTI and BPI
bispectrum central slice [41] grayscale motion BPI
cepstrum and bicepstrum [42] grayscale motion, OOF BPI
frequency coefficients and [17, 18] grayscale unblurred, Gaussian BD, BTI,
neural networks [19, 20] motion, rectangular BPI
Figure 2.9: Wavelet decomposition.
center of gravity with the latter being the most reliable.
The works in [32, 33] measure blur through the spread of edges. Vertical Sobel filter first applied to find the vertical edges in the image. Edge width is measured by counting the pixels between the local extrema locations bounding the edge pixel. The global blur measure is determined by the average of the widths. The value of this measure increases as the amount of degradation increases.
Edges are also characterized by observing the activity of the high fre-
quency wavelet coefficients in [10]. Edge pixel activity is measured for each block in the image. Global activity is then computed using the average of all the blocks. Larger values indicate abundant structures i.e., texture. Values that are moderate indicate edges and small indicate absence of structures or smooth areas. This means that a small value will indicate a highly blurred image while a large one will mean slightly blurred image.
It is also possible to detect as well as measure blurs using edge type and sharpness analysis after a wavelet transform as proposed in [16]. This method takes advantage of the ability of Haar wavelet transform in dis- criminating types of edges and in recovering sharpness. Blur detection is achieved by edge type analysis and the extent is determined by edge sharp- ness analysis. This basically involves the identification of different edge structures across the different decomposition levels. There are three edge structures namely: dirac, step, and roof. Step is further divided into Astep and Gstep depending on whether the change in intensity is gradual or not. The illustrations for the different edge structures are shown in Figure 2.10. In the presence of blurs, both dirac and Astep will disappear while roof and Gstep structures will loose their sharpness. The total number of edge points and different structures are determined. The ratio between the total count for dirac and Astep to the total edge points will indicate an unblurred image if its value is greater than an empirically determined threshold. On the other hand, blur measure is determined using the roof and Gstep.
The work in [34] redefined the edge width by [32, 33]. Gradient maps are created for both vertical and horizontal directions. Using these, gradient orientation and edge magnitude maps are calculated. The standard devia-
(a) Dirac
(b) Roof
(c) Astep
(d) Gstep
tion of the pixels is determined from the gradient orientation map. Using this and the edge magnitude will yield the blur measure.
2.3.2 Detection in the Transform Domain
The Fourier transform has been the most commonly used method to deter- mine the presence of blurs in images. In the frequency domain, blurs are known to suppress high frequency components. This is why degradation is considered as similar to applying a low-pass filter on an image. Null pat- terns have been investigated especially for motion and OOF blurs. For this reason, most Fourier-based methods are dedicated to blur identification.
A newer method in [35] measures the kurtosis in the wavelet domain in order to measure the sharpness of an image. The authors used discrete dyadic wavelet transform due to its stability, completeness, and ease of im- plementation. Kurtosis is computed for both horizontal and vertical details bands. The final metric is the average of the two values. In this case, the lower the value the sharper the image.
2.3.3 Identification in the Spatial Domain
This section deals with the identification of blurs by exploiting the image pixels. A method proposed in [36] utilizes the kurtosis of the pixel distribu- tion. When kurtosis is less than three then the distribution is characterized by a small tail. In this case, larger values indicate smoother data. The method will determine the PSF parameter with its functional form known
or assumed. The degradation is modeled by
gm= fm∗ hm(ρ) + nm (2.17)
where ρ ∈ Θ. The actual parameter is represented by ρ while the space enclosing all the possible parameters is Θ. Reconstruction of the image is computed using several parameters and kurtosis is determined by
τ(f ) = E(f − µ)
4)
ξ4 (2.18)
where τ , µ, and ξ represent the kurtosis, mean, and standard deviation, respectively. The parameter is then selected by
ρτ = min
ρ∈Θτ
n ˆf(ρ)o. (2.19)
The discrete spatial techniques proposed in [37] is also capable of es- timating the blur support. This is based on the practicality of utilizing the (autoregressive moving average) ARMA image model wherein H is a block-circulant circulant-block (BCCB) matrix. When g is convolved with a two-dimensional finite-impulse response (FIR) filter, the resulting model implies that the correlation of this image approaches that of H. Using this, the PSF support identification method requires the computation of the following:
• Maximum average square difference (MASD) estimators can be deter-
mined by
PˆM ASD = arg
p max{R
M ASD(p, 0)}
QˆM ASD = arg
q max{RM ASD(0, q)}
where
RM ASD(p, q) = 1 XY
M
X
x=1 N
X
y=1
[gm(x, y) − gm(x + p, y + n)]2. (2.20)
The estimated quantities, ˆP and ˆQ, represent the blur support in the vertical and horizontal directions, respectively.
• Maximum average absolute difference (MAAD) estimators can be de- termined by
PˆM AAD = arg
p max{RM AAD(p, 0)}
QˆM AAD = arg
q max{RM AAD(0, q)}
where
RM AAD = 1 XY
M
X
x=1 N
X
y=1
|gm(x, y) − gm(x + p, y + n)|. (2.21)
The result in [37] shows that the method can determine the support size for Gaussian blur.
2.3.4 Identification in the Transform Domain
As previously mentioned, Fourier transform is used in the analysis of the frequency nulls to indicate the blur type [22]. This class of method requires the blur kernel to exhibit a periodic frequency null pattern which are only observable for motion and out-of-focus (OOF) blurs. The work in [38] uses residual spectrum for blur estimation. This requires a priori knowledge on the type of blur and second order statistics of the input image and noise, as required in Weiner filtering. Furthermore, a collection of PSFs must be also be provided. Other methods prefer to use the cepstrum such as that in [39] where the blur type is required to be known in order to estimate the blur function. The estimation is then achieved by applying low rank approximation constraints to the power cepstrum of a degraded image. The method proposed in [40] used the cepstral null pattern to determine the blur type and parameter. This is based on the fact that the presence of blur makes the cepstrum pattern anisotropic. By using an edge detector, the cepstrum image is converted into a binary image. The Hough transform is then applied to detect linear patterns for motion and circular for OOF. As shown in [45], this transform can be extended to find general classes of curves in pictures. A significant advantage is its ability to bridge gaps in a line [46]. Thus, it is less affected by noise. Power bicepstrum has also been used due to its ability to suppress additive Gaussian noise. Only the central slice is usually extracted to lessen computational cost [41]. In [42], it was shown that in the presence of large blurs and low SNR values, the use of cepstrum and bicepstrum outperformed the spectrum and bispectrum,
respectively.
2.3.5 Detection and Identification in the Frequency
Domain
The works in [17, 18, 19, 20] use fewer transform coefficients together with a neural network discussed in [47]. The problem involves the recognition of the PSF’s shape from the power spectral density. The neural network is a multi-valued network, which is characterized by complex-valued weights; inputs and output lying on the unit circle; and activation function that maps the complex plane into the unit circle. Since each output of the network is designed to classify one type of PSF, an unblurred image is detected when the outputs reject all types of blurs. This technique utilizes a number of selected coefficients which are projected to the unit circle and used as inputs to the neural network. The blur type, i.e., Gaussian, motion, and rectangular, as well as their corresponding parameter values can be identified however this method requires the image sizes to be fixed. In other words, once the network is designed for a certain image size, it is not suitable for other images with different sizes. In addition to this, the training period demands a great amount of time before convergence can be achieved.
2.4 Image Reconstruction: An Overview
The restoration of images have a rich collection of literatures due to its vast potential applications. For decades, researchers have been unceasingly studying this topic for the challenges it poses. Some of the developed tech- niques are specifically designed for a certain type of image while some are applicable to specific types of blur only. Image and PSF constraints and priori information has been demonstrated to be highly dependent on the imaging system itself as discussed in [48, 27, 49, 50, 51]. In this work, we will focus on blind image restoration techniques. It involves the estimation of the unblurred image and the blurring function. Since this is an ill-posed problem, partial information may also be introduced. There are two major classes of blind deconvolution depending on the blur identification stage as mentioned in [22, 26]. Namely, these are:
1. a priori or disjoint identification techniques
This class of techniques separately performs PSF identification and image deconvolution. The usual approach starts with the identifica- tion of the PSF then this is followed by the application of a classical image restoration algorithm. Parametric blur models may also be used and sometimes assumptions on its characteristics can be made. Exam- ples include PSF symmetry, availability of its parametric form, and complete characterization by edges or frequency nulls. These tech- niques usually have low computational requirements but have limited applicability since it requires the image to possess known special fea- tures and the PSF to have special parametric form. The term myopic
deconvolution [50, 51] is sometimes used when PSF is partially known. This assumes that an estimate of the PSF is not too far from the true one.
2. joint identification techniques
This class determines the PSF and the image either simultaneously or alternately. Because of this, most of which are designed with more complex algorithms. Prior knowledge about the image and the PSF may be incorporated in order to improve the reconstruction perfor- mance. Majority of recently developed methods fall under this class. Several variations have also been proposed with promising results. One of the most popular approach for both classes is the iterative tech- nique. This work will focus on these algorithms due to its numerous advan- tages and the attention that it has been steadily getting. Iterative restora- tion algorithms have been actively studied by several researches, which can be attested by its evolution from the past up to the present. These methods start with some initializations followed by repeated computations until the stopping criteria is achieved. It has been proven in several literatures that this approach can be powerful especially when [21]:
1. prior knowledge about the underlying image is available such as con- straints on allowable restorations;
2. blurring function is approximately known;
3. local information of the image can be used to vary the degree of blur and noise removal.
The popularity of iterative methods is caused by its numerous advantages as reported in [24, 25, 52]. These include:
1. inverse of an operator need not be explicitly implemented;
2. parameters that determine the solution can be updated every itera- tion;
3. performance may be monitored as it progresses so that termination is possible whenever an acceptable result has been achieved;
4. can easily be extended to include all types of priori knowledge such as controlling the effects of noise with certain constraints;
5. spatial adaptivity may be introduced;
6. well suited for images from a variety of degradations due to its flexible framework; and
7. do not require Fourier transforms thus images of arbitrary sizes are also applicable.
This type of algorithms usually gives a visually better solution if its is termi- nated prior to convergence [24]. Some classical methods, which have been further developed, include the works by Van Crittert; Ayers and Dainty; and Rudin, Osher, and Fatemi. Their basic principles will be presented next.
2.4.1 Classical Iterative Reconstruction Methods
The work by Van Crittert is also commonly called as Bially or Landweber iteration due to its multiple independent discovery [21]. It introduced an identity that must hold for all values of the parameter βV C
fˆ= ˆf + βV C
g− H ˆf (2.22)
where 0 < βV C < 2. The application of successive substitution will yield the following iteration:
fˆ0 = βV Cg fˆk+1 = fˆk+ βV C
g− H ˆfk (2.23)
= βV Cg+ (I − βV CH) ˆfk
= βV Cg+ RV Cfˆk
where I is an identity operator and k is the iteration number. The limiting solution is given by
fˆ∞ = lim
k→∞
fˆk = βV C(I − RV C)−1g = H−1g. (2.24)
The convergence of this technique is achievable if
k→∞limR
k+1
V Cg = 0 (2.25)
and if the blurring operator has positive real part for all frequencies. Unfor- tunately, the latter is not satisfied by linear motion and OOF blurs. This led to the introduction of reblurring operation as suggested by other authors.
The work of [53] introduced the use of Bayes’ theorem and iterated conditional modes (ICM) for reconstruction of images. A true but unknown pixel value is reconstructed based on two imperfect sources. First source is a possible multivariate record, which can provide data related to the pixel. Second is the tendency of pixels to have the same color or value if they are located close to each other. The latter being quantified probabilistically by a non-degenerate Markov random field in order to represent the local characteristics of the image. The two sources can then be combined by Bayes’ theorem and reconstruction is done by standard criteria. In the Bayesian framework, these are:
1. maximum a posteriori estimation where the color has overall maxi- mum probability given the records and
2. maximum posterior marginal probability at each pixel, which means that the color at each pixel has maximum probability given the records.
Another closely related work is the Tikhonov-Miller regularization. It defines a criterion to select an approximate solution from a set of admissible solutions, Sǫ. The images in Sǫ bounds the norm of the residual image, i.e.,
||g − H ˆf|| = ||n|| ≤ ǫ (2.26)
where || · || denotes Euclidean norm. The regularized solution minimizes a
![Figure 1.3: From left to right: original fingerprint, reconstructed fingerprint, and overlay of the two images as shown in [8].](https://thumb-ap.123doks.com/thumbv2/123deta/5750472.26707/32.892.139.691.150.410/figure-right-original-fingerprint-reconstructed-fingerprint-overlay-images.webp)
![Figure 1.4: Reconstruction for iris recognition systems in [9].](https://thumb-ap.123doks.com/thumbv2/123deta/5750472.26707/33.892.294.671.142.976/figure-reconstruction-iris-recognition-systems.webp)
