Image Processing: Fundamentals.Maria Petrou and Panagiota Bosdogianni The Copyright 1999 John Wiley & Sons Ltd Print ISBN 0-471-99883-4 Electronic ISBN 0-470-84190-7 Chapter Image Restoration What is image restoration? Image restoration is the improvement of an image using objective criteria and prior knowledge as to what the image should look like What is the difference between image enhancement and image restoration? In image enhancement we try to improve the image usingsubjective criteria, while in image restoration we are trying to reverse a specific damage suffered by the image, using objective criteria Why may an image require restoration? An image may be degraded because the grey values of individual pixels may be altered, or it may be distorted because the position of individual pixels may be shifted away from their correct position The second case is the subject of geometric lestoration Geometric restoration is also called image registration because it helps in finding corresponding points between two images of the same region taken from different viewing angles Image registration is very important in remote sensing when aerial photographs have to be registered against the map, or two aerial photographs of the same region have to be registered with eachother How may geometric distortion arise? Geometric distortion may arise because of the lens or because of the irregular movement of the sensor during image capture In the former case, the distortion looks regular like those shown in Figure 6.1 The latter case arises, for example, when an aeroplane photographs the surface of the Earthwith a line scan camera As the aeroplane wobbles, the captured image may be inhomogeneously distorted, with pixels displaced by as much as 4-5 interpixel distances away from their true positions 194 Processing: Image The Fundamentals (b) Pincushion distortion (a) Original (c) Barrel distortion Figure 6.1: Examples of geometric distortions caused by the lens X A X Y Corrected image Distorted image Figure 6.2: In this figure the pixels correspond to the nodes of the g rids Pixel A of the corrected grid corresponds to inter-pixel position A’ of the original image How can a geometrically distorted image be restored? We start by creating an empty array of numbers the same size as the distorted image This array will become the corrected image Our purpose is to assign grey values to the elements of this array This can be achieved by performing a two-stage operation: spatial transformation followed by grey level interpolation How we perform the spatial transformation? Suppose that the true position of a pixel is (z, y) and the distorted position is ( g , $ ) (see Figure 6.2 ) In general there will be a transformation which leads from one set of coordinates to the other, say: Image Restoration 195 First we must find to which coordinate position in the distorted image each pixel position of the corrected image corresponds Here we usually make someassumptions For example, we may say that the above transformation has the following form: where cl, c2, ,c8 are some parameters Alternatively, we may assume a more general form, where squares of the coordinates X and y appear on the right hand sides of the above equations The values of parameters c l , ,C8 can be determined from the transformation of known points called tie points For example, in aerial photographs of the surface of the Earth, there are certain landmarkswith exactly known positions There are several such points scattered all over the surface of the Earth We can use, for example, four such points to find the values of the above eight parameters and assume that these transformation equations with the derived parameter values hold inside the whole quadrilateral region defined by these four tie points Then, we apply the transformation to find the position A' of point A of the corrected image, in the distorted image Why is grey level interpolation needed? It is likely that point A' will not have integer coordinates even though the coordinates of point A in the (z, space are integer This means that we not actually know the y) grey level value position A' That is whenthe grey level interpolation process comes at into play The grey level value at position A' can be estimated from the values at its four nearest neighbouring pixels in the (?,G) space, by some method, for example by bilinear interpolation We assume that inside each little square the grey level value is a simple function of the positional coordinates: g(D,jj) = a0 + pjj + y2i.g + where a , , are some parameters We apply this formula to the four corner pixels to derive values of a , p, y and and then use these values to calculate g($, jj) at the position of A' point Figure 6.3 below shows in magnification the neighbourhood of point A' in the distorted image with the four nearest pixels at the neighbouring positions with integer coordinates Simpler as well as more sophisticated methods of interpolation may be employed For example, the simplest method that can be used is the nearest neighbour method where A' gets the grey level value of the pixel which is nearest to it A more sophisticated method is to fit a higher order surface through a larger patch of pixels around A' and find the value at A' from the equation of that surface 196 Processing: Image The Fundamentals Figure 6.3: The non-integer position of point A' is surrounded by four pixels at integer positions, with known grey values ( [ X ] means integer part of X ) Example 6.1 In the figure below the grid on the right is a geometrically distorted image and has to be registered with the reference image on the left using points A, B , C and D as tie points The entries in the image on the left indicate coordinate positions Assuming that the distortion within the rectangle ABCD can be modelled by bilinear interpolation and the grey level value at an interpixel position can be modelled by bilinear interpolation too, find the grey level value at pixel position (2,2) in the reference image Suppose that the position (i, of a pixel in the distorted image is given in terms 6) y of its position (X, ) in the reference image by: W e have the following set of the corresponding coordinates between the two grids using the four tie points: 197 Image Restoration Pixel Pixel Pixel Pixel 4) A B C D Distorted ( , y ) coords.Reference (0,O) (3,1> (1,3) (4, (X,y) coords (090) (390) ((43) (3,3) W e can use these to calculate the values of the parameters cl, ,CS: Pixel A: Pixel B: Pixel C Pixel D }+{ 1=3~2 = 3cs 4=3+3x$+9c3 4=3x++3+9c7 The distorted coordinates, therefore, given by: of any pixel within the square Y ? = a : +y-= - + y , ABDC are X For X = y = we have = + , y = $ + So, the coordinates of pixel (2,2) in the distorted image are (2$, i ) This position is located between pixels in the distorted image and actually between pixels with the following grey level values: 213 W e define a local coordinate system ( ,y”), so that the pixel at the top left corner hascoordinateposition (0,O) thepixelatthetoprightcornerhascoordinates (1,0), the one at the bottom left ( , l ) and the one at the bottom right ( , l ) Assuming that the grey level value between four pixels can be computed from the grey level values in the four corner pixels with bilinear interpolation, we have: Applying this for the four neighbouring pixels we have: 199 Image Restoration We recognize now that equation (6.7) is the convolution between the undegraded image f (z,y) and the point spread function, and therefore we can write it in terms of their Fourier transforms: G(u,W) = F(u,v)H(u,W) (6.8) where G, F and H are the Fourier transforms of functions f , g and h respectively What form does equation (6.5) take for the case of discrete images? N N k=l k We have shown that equation (6.9) can be written in matrix form (see equation (1.25)): g=Hf (6.10) What is the problem of image restoration? The problem of image restoration is: given the degraded image g, recover the original undegraded image f How can the problem of image restoration be solved? The problem of image restoration can be solved if we have prior knowledge of the point spread function or its Fourier transform (the transfer function) of the degradation process How can we obtain information on the transfer function ~ ( u , w ) the of degradation process? From the knowledge of the physical process that caused degradation For example, if the degradation is due to diffraction, H ( u ,W ) can be calculated Similarly, if the degradation is due to atmospheric turbulence or due to motion, it can be modelled and H(u,W) calculated We may try toextract information on k ( u ,W ) or h(a - z, ,B -9) from the image itself; i.e from the effect the process has on the images of some known objects, ignoring the actual nature of the underlying physical process that takes place Processing: Image 200 I The Fundamentals Example 6.2 When a certain static scene was being recorded, the camera underwent planar motion parallel to the image plane (X, ) This motion appeared y as if the scene moved in the X,y directions by distances zo(t) and yo(t) which are functions of time t The shutterof the camera remained open from t = to t = T where T is a constant Write down the equation that expresses the intensity recorded at pixel position (X, ) in terms of y the scene intensity function f (X, ) y The total exposure at any point of the recording medium (say the film) will be T and we shall have for the blurred image: T (6.11) Example 6.3 In Example 6.2, derive the transfer function with which you can model the degradation suffered by the image due to the camera motion, assuming that the degradation linear with a shift invariant point spread is function Consider the Fourier transform of g ( z , y ) defined in Example 6.2 +a +a S_, i*(u,v) = S , g(z, y)e-2"j(uz+uY)d XdY _ (6.12) If we substitute (6.11) into (6.12) we have: W e can exchange the order of integrals: f (X - x o ( t ) y - yo(t))e-2"j(ur+ur)drdy} dt (6.14) , This is the Fourier transfoA of the shifted function by in directions X,y respectively 20, yo Image Restoration 201 W e have shown (see equation (2.67)) that the Fourier transform of a shifted function and the Fourier transform of the unshifted function are related by: ( F T of shifted function) = ( F T of unshifted function)e-2aj(uzo+vyo) Therefore: &(U, v) = I' fi(u, y)e-2?rj(uzo+vy'J)dt where F(u,v) is the Fourier transformof the scene intensity functionf (X, ) , i.e y the unblurred image F ( u , v ) is independent of time, so it can come out of the integral sign: = ) I' ) e-2?rj(uzo(t)+vYo(t))dt Comparing this equation with (6.8) we conclude that: (6.15) Example 6.4 Suppose that the motion in Example 6.2 was in the and with constant speed F, so that yo(t) = 0, zo(t) = transfer function of the motion blurring caused X direction only F Calculate the I n the result of Example 6.3, equation (6.15), substitute yo(t) and xO(t) to obtain: Processing: Image 202 The Fundamentals Example 6.5 (B) It was established that during the time interval T when the shutter was open, the camera moved in such a way that it appeared as if the objects in the scene moved along the positive y axis, with constant acceleration a and initial velocity SO, starting from zero displacement Derive the transfer function of the degradation process for this case In this case x:o(t)= and dY0 % = a + - = a t + b + y o ( t ) = at2 + bt + C dt2 dt where a is half the constant acceleration and b and c some integration constants W e have the following initial conditions: t=O zero shifting i.e c = t = velocity of shifting = SO + b = SO Therefore: yo(t) = at2 + sot W e substitute xo(t) and yo(t) in equation 6.15 f o r H ( u , v ) : H(u,w) = = I’ e-~?rj71(Cd2+Sot)dt LT cos [2.rrvat2 + m s o t ] d t - j I’ We may use the following formulae: S S cos(ax2+bx+c)dx = sin(ax2+bx+c)dx = where S ( x ) and C ( x ) are S ( x )E C ( x )E clx sin t2dt 6lx and they are called Fresnel integrals cos t2dt sin[27rvat2 +2~vsot] dt Image Restoration 249 L(2,O) Jt(2,l) = L(0,2) = -1 i(2,2) = = Jq1,2) = -2 [-4 - + e - Y + 2e-?] = -2 where we have made use of the following: e- = -cos60° + j s i n ° = + d 2 Notethatthefirsteigenvalue of matrix L is Thismeansthatmatrix L is singular, and even though we can diagonalize it using equation (6.101), we cannot invert it by taking the inverse of this equation This should not be surprising as matrix L expresses the Laplacian operator for an image, and we know that from the knowledge of the Laplacian alone we can never recover the original image Applying equation (6.99) we define matrix A for L to be: 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 - 0 0 0 0 Having defined matrices W , W-' and A we can write: L = WAW-l This equation can AW-l: be confirmed by direct substitution First we compute matrix 250 Image Processing: The Fundamentals 0 0 0 0 OK, now we know how to overcome the problem of inverting H ; however, how can we overcome the extreme sensitivity of equation (6.76) to noise? We can it by imposing a smoothness constraint to the solution, so that it does not fluctuate too much Let us say that we would like the second derivative of the reconstructed image to be small overall At each pixel, the sum of the second derivatives of the image along each axis can be approximated by: A2f (i, k) = f (i - 1,k) + f (i, k - 1) + f (i + 1,k) + f ( i ,5 + 1) - f ( i , 5) (6.111) This is the value of the Laplacian at position (i,k) The constraint we choose to impose then is for the sum of the squares of the Laplacian values at each pixel position to be minimal: N - - N [A2f ( i , k)I2 = minimal (6.112) k=1 i=l The value of the Laplacian at each pixel position can be computed by the Laplacian operator which has the form of an N X N matrix acting on the column vector f (of size N X l),Lf Lf is a vector The sum of the squares of its elements are given by (Lf)TLf The constraint then is: (LflTLf = minimal (6.113) Image Restoration 251 How can we incorporate the constraint in the inversion of the matrix? Let us write again in matrix form the equation we want to solve for f: (6.114) g=Hf+v We assume that the noise vector are known; say we know that: U is not known but some of its statistical properties (6.115) uTu = E This quantity E is related to the variance of noise and could be estimated from the image itself using areas of uniform brightness only If we substitute U from (6.114) into (6.115) we have: (g - Hf)T(g- Hf) = E (6.116) The problem then is to minimize (6.113) under the constraint (6.116) The solution of this problem is a filter with Fourier transform: (6.117) By multiplying numerator and denominator by function of the restoration filter as being: H(u,Y), can extract the transfer we (6.118) where y is a constant and ~ ( u , w )the Fourier transform of an N X N matrix L, is with the following property: If we use it to multiply the image from the left, the output will be an array the same size as the image, with an estimate of the value of the Laplacian at each pixel position The role of parameter y is to strike the balance between smoothing the output and paying attention to the data B6.7: Find the solution of the problem: minimize (Lf)TLf with the constraint [ g - H f ]T [ g - Hf] = E According to the method must satisfy: a -[f af T (6.119) of Lagrunge multipliers (see Box B6.9) the solution L T Lf + X(g - Hf)] = (6.120) 252 Image Processing: The Fundamentals where X is a constant This differentiation is with respect t o a vector and it will yield a system of N2 equations (one for each component of vector f ) which with equation (6.116) form a system of N2 equations, for the N unknowns: N the components of f plus X If a is a vector and b another one, then it can be shown (see Example 6.23) that : + + afTa af dbTf -=b af (6.121) -=a (6.122) Also, if A is an N2 X N2 square matrix, then (see Example 6.24): df Af = ( A + AT)f af (6.123) We apply equations (6.121), (6.122) and (6.123) to (6.120) to perform the differentiation: - fT(LTL)f +X(gTg- gTHf - + fTHTg + -l fTHTHf ) =O eqn(6.123) with eqn(6.122) eqn(6.121) with b = HTg with a = HTg A = HTH + (2LTL)f + X(-HTg HTg + 2HTHf) = + (HTH+yLTL)f = HTg - (6.124) i where y Equation (6.124) can easily be solved interms of blockcirculant matrices.Then: f = [ H T H + "iLTL]-lHTg y can be specified by substitution in equation (6.119) (6.125) 253 Image Restoration B6.8 Solve equation (6.124) Since H and L are block circulant matrices (see Examples 6.20, 6.22 and Box B6.6), they can be written as: H T = WAEW-l LT = WAt W-l H = WAhW-' L = WA1W-l (6.126) Then: H ~ +y H ~ + = W A E W - ~ W A ~ W -y ~ ~ ; ~ T ~ ~ = W A ~ A ~ WY ~ h ; ~ l ~ - l - ~ = W(AZAh yAiAl)W-' + l ~ ~ + (6.127) We substitute from (6.126) and (6.127) into (6.124) to obtain: W ( h ; l A h+ 7AZ;Al)W-lf = Wh;/W-lg (6.128) First we multiply both sides of the equation from the left with W - ' , to get: (AEAh + 7ArRl)W-'f = AEW-lg (6.129) Notice that as A;, A;lhh and h;hl are diagonal matrices, this equation expresses a relationship between the corresponding elements of vectors W-lf and W-lg one by one Applying the result of Example 6.26, we can write: A;lhh = N21I?(u,v)I u)I 2 A;Al = N21L(u,u)I and where If,(u, is the Fourier transform of matrix L Also, by applying the results of Example 6.25, we can write: W-'f = @ ( u , v ) and W-lg = G ( u , v ) Finally, we replace A;L by its definition, equation (6.99), so that (6.129) becomes: F(u,w) = - I;T*(u, ) G ( U , U) U II;T(u, ) U + yli(u, (6.130) U)12 l ~ - l Image Processing: The Fundamentals 254 What is the relationship between the Wiener filter and the constrained matrix inversion filter? Both filters look similar (see equations (6.47) and (6.118)), but they ways: differ in many The Wiener filter is designed to optimize the restoration in an average statistical sense over a large ensemble of similar images The constrained matrix inversion deals with one image only and imposes constraints on the solution sought The Wiener filter is based on the assumption that therandom fields involvedare homogeneous with known spectral densities In the constrained matrix inversion it is assumed that we know only some statistical property of the noise In the constraint matrix restoration approach, various filters may be constructed using the same formulation by simply changing the smoothing criterion For example, one may try tominimize the sum of the squares of the first derivatives at all positions as opposed to the second derivatives The only difference from the formula (6.117) will be in matrix L Example 6.23 (B) Differentiation by a vector is defined as differentiation by each of the elements of the vector For vectors a, b and f show that: dfTa ~ af =a Assume that vectors a, b and f are N Use this in: Similarly: and X dfTb ~ af =b Then we have: Image Restoration 255 Example 6.24 (B) If f is an N X vector and A is an N X N matrix, show that df Af = (A + AT)f df Using the results of Example 6.23 we can easily see that: dfT(Af) d(fTA)f df df a(ATf)Tf = Af + df = Af + ATf = (A AT)f - + dfTAf df + ( w e m a k e u s e of the fact that Af and ATf are vectors.) Example 6.25 (B) If g is the column vector that corresponds to a X image G and matrix W-' is defined as in Example 6.18 for N = 3, show that vector W - l g is the discrete Fourier transform G of G Assume that: 256 simplifies somehow So we get: Image Processing: The Fundamentals Image Restoration This shows that W-'g yields the Fourier transform of G, as a column vector Example 6.26 (B) Show that if matrix A is defined by equation (6.99) then A*A is a diag2 onal matrix with its kth element along the diagonal being N'Ifi(k2, k1)l where k2 E kmod N and kl E [X] From the definition of A, equation (6.99), we can write: A = NH(0,O) 0 NH(1,O) NH(2,O) 0 0 0 0 N H ( N - 1,N Then: A* = NH*(O,0) 0 N H * ( l ,0) N H * ( , ) 0 0 0 0 N H * ( N - 1,N - 1) 258 Image Processing: The Fundamentals Obviously ‘NIH(O70)I2 0 Nlfi(k h* h= 0 \ o NIH(2, 0)l2 0 0 N I f i ( N - l , N - 1)12 B6.9 Why does the method of Lagrange multipliers work? Suppose that we wish to satisfy two equations simultaneously: f(z,y) = g(z,y) = 0 (6.131) Let us assume that in the ( ~ , y ) plane the first of these equations is satisfied at point A and other the at point B , so that it is impossible to satisfy both equations exactly for the same value of (X, y) contours of constant values of g(x,y) X We wish to find a point C on the plane where we make the least compromise in violating these two equations The location of this point will depend on how fast the values of f ( z , y) and g(z, y) change from as we move away from points A and B respectively 259 Image Restoration Let us consider the isocontours of f and g around each of the points A and B respectively As the contours grow away from point A, function I f ( z ,y) I takes larger and larger values, while as contours grow away from point B, the values function l g ( X , y)l takes become larger as well Point C where the values of If ( X , y)I and g (X, I are as small aspossible (minimum violation of the constraints which y) demand that If ( ~ , y ) l= Ig(X,y)l = 0), must be the point where an isocontour around A just touches an isocontouraround B, without crossingeach other Whentwocurvesjusttouch each other,theirtangents becomeparallel The tangent vector to a curve along which f =constant is O f , and the tangent vector t o a curve along which g =constant is Vg The two tangent vectors not need t o have the same magnitude for the minimum violation of the constraints It is enough for them to have the same orientation Therefore, we say that point C is determined by the solution of equation Of = pOg where p is some constant thattakescare of the (possibly)differentmagnitudes of the twovectors In other words, the solution to the problem of simultaneous satisfaction of the two incompatible equations (6.131) is the solution of the differential set of equations: Of+XOg=O where X is the Lagrange multiplier, an arbitrary constant Example 6.27 Demonstrate how to apply the constraint matrix inversion in practice, by restoring a motion blurred image To apply the filter given by equation (6.117) to the blurred image of Figure 6.7a, we must first define matrix ~ ( I L , which expresses the constraint v) Following the steps of Example 6.19, we can see that matrix L ( i , j ) with which we have to multiply an N X N image in order to obtain the value of the Laplacian at each position is given by an N X N matrix of the following structure: 260 Image Processing: The Fundamentals m N- unit matrices NxN I matrix L * * * matrices NXN Matrixhasthefollowing r~ form: ~ zeroes f -4 0 -4 1 -4 1 -4 0 0 X L= ( 0 0 0 0 0 0 -4 -4 0 To form the kernel we require, we must take the first column matrix L and wrap of it to form an N X N matrix The first column of matrix L consists of the first column of matrix (N elements) plus the first columns of N - unit matrices of size N X N These N elements have to be written as N columns of size N next to each other, to form an N X N matrix L', say ' -4 1 1 0 0 0 , It is the Fourier transform inversion filter 0 0 of this matrix that appears in the constraint matrix 261 Image Restoration W e calculate the Fourier transform using formula (6.100) with N = 128 Let and us say that the real and the imaginary parts of this transform are L1 (m, n) L2(m,n) respectively Then IQm, )l2 + = L?(m, n> L;(m,n> The transfer function of the filter we must use then is given transfer function (6.33) into equation (6.117): by substituting the Note that for m = we must use: Working as for the case of the Wiener filtering we can find that the real and imaginary parts of the Fourier transform of the original image are given by: Fl(m,n)=N iTsin F2(m,n)= N (m, cos n) sin2 iTTm p (iT-l)?rm - G2 ( m ,n)sin (iT-l)?rm + y (Lf(m,n) + L;(m,n))i$ sin2 N E (iT-l)?rm sin 1(m,n) sin sin2 y (Lf(m, iT?rm n) + + G2(m,n)cos (iT-l)?rm] + L;(m,n))i$ sin2 N E These formulae are valid for < m N - and n N - For m = we must use the formulae: If we take the inverse Fourier transform using functions Fl(m, n) F2(m,n) and as the real and the imaginary parts, we obtain the restored image The results of restoring images 6.7b, 6.8a and ~ shown in Figure 6.11 Note that different are values of 7, i.e different levels of smoothing, have to be used for different levels of noise in the image Image 262 Processing: The Fundamentals I (a) Constraint matrix inversion with y = 0.001 for image 6.7b (realistic blurring) (b) Constraint matrix inversion with y = 0.05 for image 6.8a (realistic blurring and Gaussian noise (a = 10)) (c) Constraint matrix inversion with y = 0.1 for image ~ (realistic blurring and Gaussian noise (a = 20)) Figure 6.11: Restoration with constraint matrix inversion What is the “take home” message of this chapter? This chapter explored some techniques used to correct (i.e restore) the damaged values of an image The problem of restoration requires some prior knowledge concerning the original uncorrupted signal or the imaged scene, and in that way differs from the image enhancement problem Geometric restoration of an image requires knowledge of the correct location of some reference points Grey level restoration of an image requires knowledge of some statistical properties of the corrupting noise, the blurring process and the original image itself Often, we bypass the requirement for knowing the statistical properties of the original image by imposing some spatial smoothness constraints on the solution, based on the heuristic that “the world is largely smooth” Having chosen the correct model for the degradation process and the uncorrupted image, we have then to solve the problem of recovering the original image values The full problem of image restoration is a very difficult one as it is non-linear It can be solved with the help of local or global optimization approaches However, simpler solutions can be found, in the form of convolution filters, if we make the assumption that thedegradation process is shift invariant and if we restrict the domain of the sought solution to that of linear solutions only Figure 6.12 summarizes the results obtained by the various restoration methods discussed, for an image blurred by motion along the horizontal axis Image Restoration 263 7- - - - - - Figure 6.12: (a) Original images (b) Restoration by inverse filtering with omission of all terms beyond the first zero of the filter transfer function (c) Restoration by Wiener filtering (d) Restoration by constraint matrix inversion ... image restoration is: given the degraded image g, recover the original undegraded image f How can the problem of image restoration be solved? The problem of image restoration can be solved if we... from the image itself; i.e from the effect the process has on the images of some known objects, ignoring the actual nature of the underlying physical process that takes place Processing: Image. .. filtering in practice by restoring a motion blurred image 211 Image Restoration Let us consider the image of Figure ~ To imitate the way this image would loot if it were blurred by motion, we