I M A G E P R O C E S S I N G by A N D Y B I N G - B I L L C H A N B . S c , The University of Br i t i sh Columbia , 1993 A T H E S I S S U B M I T T E D I N P A R T I A L F U L F I L L M E N T O F T H E R E Q U I R E M E N T S F O R T H E D E G R E E O F M A S T E R O F S C I E N C E in T H E F A C U L T Y O F G R A D U A T E S T U D I E S Department of Statistics We accept this thesis as conforming to ^he required standard T H E U N I V E R S I T Y O F B R I T I S H C O L U M B I A A p r i l 1995 © A n d y B i n g - B i l l Chan, 1995 In p resen t ing this thesis in partial fu l f i lment of t h e r e q u i r e m e n t s fo r an advanced d e g r e e at the Univers i ty o f British C o l u m b i a , I agree tha t t h e Library shall make it f reely available f o r re ference and s tudy. I fu r ther agree that pe rmiss ion f o r ex tens ive c o p y i n g of this thesis f o r scholar ly pu rposes may be g r a n t e d by the head o f m y d e p a r t m e n t or by his o r her representat ives. It is u n d e r s t o o d that c o p y i n g o r pub l i ca t i on o f this thesis fo r f inancial gain shall n o t be a l l o w e d w i t h o u t m y w r i t t e n pe rmiss ion . D e p a r t m e n t o f The Univers i ty o f Brit ish C o l u m b i a Vancouver , Canada Date DE-6 (2788) ABSTRACT In this thesis, we consider the restoration of multiple grey levels image. The problem is to clean up or restore the dirty picture, that is, to construct an estimate of the true image from a noisy picture of that true image. Following a method proposed by Meloche and Zamar (1994), we estimate the colour at each site by a function of the data available in a neighbourhood of that site. In this approach, the local characteristics of that image, that is, the frequency with which each pattern appears in the true unobserved image are particularly important. We will propose a family of unbiased estimates of the pattern distribution and the noise level which are used in the restoration process. We will use our estimates of the pattern distribution in an attempt to select the best neighbourhood shape for the restoration process. ii CONTENTS Abstract " Table of Contents iii List of Tables iv List of Figures v Acknowledgements vii 1 Introduction 1 2 Estimations of Q 10 2.1 Introduction 10 2.2 Unbiased Estimations of Q 10 2.3 A Simple Representation for Q 21 3 Joint Estimations of Q and a 29 3.1 Introduction 29 3.2 Estimation of a using Estimating Equation derived from E{\ £" = 1 *i2) 2 9 3.3 Estimation of a using Estimating Equation derived from E(\ J2i=i 3 3 4 Neighbourhood Shapes 35 5 Conclusions 3§ References 40 i n LIST OF TABLES Table 1.1 Frequency distribution (r = 1) 5 Table 1.2 Frequency distribution (r = 2) 5 Table 1.3 Frequency distribution (r = 5) 7 Table 2.1 Pattern distribution with r = 1, h n 1 & We now extend this idea for estimating Q based on indicator functions to a colour set with more than 2 grey levels. We will notice from the following examples that the bias matrix A r that needs to be inverted may not have a simple structure. Example 2.1 : Suppose C = {0,1,2} and r = 1. Now let l) and define n t e l n . = 1 2 n«=i ",=i 2 2 Giro = ^Ev(2,«)=^i:i{«>|} n t=i n i=i ^ After carrying out some calculations, and letting a = $ ( 5 7 ) , b = $ ( 3 7 ) , c = $(=jj-),d = *(£) " = *(£) " * ( £ ) , / = - = 1" *(£)> * = 1 " = 1 — $ ( ^ 7 ) , we obtain ' & ( 0 ) ' ' a b c ^ ( Qi(0) y E = d e f Qi(i) ^ 0l(2) , K g h i j ^ Gi(2) j or, in matrix notation, EQi = AiQx. When r = 2 (linear 2-site neighbourhoods), there are 32 = 9 possible patterns, namely, 00, 01, 02, 10, 11, 12, 20, 21, and 22. And again by carrying out some calculations, we obtain 15 E ' Q 2 ( o o ) N ^ aa ab ac ba bb be ca cb cc) ' g 2 (oo) > g 2(oi) ad ae af bd be bf cd ce cf Q 2 ( o i ) B ^ anB aJ2B ... aimB ^ a2iB a22B ... a2mB y apiB ap2B 16 According to Anderson (1984), (A 0 B) - 1 = A - 1 0 B - 1 , (7) that is, the inverse of a Kronecker product of 2 matrices is the Kronecker product of the inverses of the 2 matrices. In what follows, A^r) denotes the r-fold Kronecker product of A, that is A ( r ) = A 0 A 0 • • • 0 A. (8) Since 6 and 7 are r-dimensional, we can write the (£,7) entry of A(r) as AV(6n) = flA(6i,7i). (9) »=i In case of binary images, we denote the matrix (bias part) of the 1-site case by Ai, the matrix of the 2-site case by A 2, and the matrix of the 3-site case by A 3 . Take a closer look at Ai, and A 2. a b b a \ A 1 = A 2 = V aa ab ba bb ab aa bb ba ba bb aa ab bb ba ab aa ' aAi bAi > ^ 6A1 aAi j By Definition 2.1, A 2 is a 2-fold Kronecker product of Ai. Similarly, A 3 is a 3-fold Kronecker product of Ai. Note that in Example 2.4, for the colour set of 3 grey levels, A 2 is a 2-fold Kronecker 17 product of A i . Also note that AT1(6,7) in equation (6) is the (6,7) entry of the r-fold Kronecker product of Aj"1 for the case of binary images. Given a function

( * , * ) ( 1 0 ) n ,=1 Qr(6) = ^f:^(61,Yi,1)(p(82,Yi,2)...(0,y) = 1 (2,y) = y2 19 and as usual 1 ^ •=i For instance, $ 3 ( 0 , 0 , 0 ) Q 3 ( i , i , i ) $ 3 ( 2 , 2 , 2 ) 1 n - V l - 1 - 1 = 1 1 n — £ *»M ' *«'.2 ' ^.3 7 t «=1 Obviously, Q3 is biased for Q 3 . Just notice, for instance, that $ 3 ( 0 , 0 , 0 ) = 1 indepen-dently from the records. By definition, Ax ( 6 , 7 ) = E(p(8,~f + ere), we have Ax(0, 7) = £ l = l Ai(l,7) = J5(7 + ae) = 7 Ax(2, 7) = £ ( 7 + at) 2 = 7 2 + cr2 By Proposition 2 . 1 , Q3 = (A_i)^C»3 is unbiased for Q 3 , where A 1 = 1 Ax(0,0) Ax(0,l) Ax(0,2) N Ax(l,0) Ax(l,l) Ai(l,2) ^ ( 2 , 0 ) Ax(2,l) Ax(2,2) J 1 0 1 2 and Ax"^ 1 _ 2 i =3 I 1 2 2 2 CT 2 2 - 1 —a 2 -1 2 1 / 20 Now, we express Q3 = (A_i)(3)Q3 in matrix form. ' $ 3 ( 0 , 0 , 0 ) > t $ 3 ( 0 , 0 , 1 ) $ 3 ( 0 , 0 , 2 ) ( 1 - £)2(f) 2 > V 2 ( l - - d ) V ) ( i - ^ ) 2 ( 2 ) / $ 3 ( 0 , 0 , 0 ) ^ $ 3 ( 0 , 0 , 1 ) $ 3 ( 0 , 0 , 2 ) \ 2.3 A Simple Representation for Qr Proposition 2 . 1 provides a class of unbiased estimates Qr of Qr. The proposed esti-mates have the form Qr = (A-1)(r)Qr, where Qr(6) = -J2^{6i,Yi^{S2,Yia)...9{6r,Yi,r). 7 1 ,=1 The matrix (A-1)(r) is the r-fold Kronecker product of Ai, and when we have a large colour set, C, and a big r, (A-1)(r) is a large matrix. In this section, we show that Qr can be expressed as 1 ^ Qr(6) = - £ m, >5.l)*(«2. Y*) • • • * ( « r . * > ) ni=l (14) for some \&(t\ y)'s. Proposition 2.2 : If we define Qr(S) = -Ev&,YM63,Yu)---tp(6T,Yi,r), then EQr = A(r)Qr, where A^ r^ is the r-fold Kronecker product of the bias matrix Ai, and by definition, Ai(£,7) = Etp{6,i + at) (Af0 is |C| r x |C]r). If |Ai| > 0, then 2 1 Q r = (A 1)^r^Qr is unbiased and consistent for Q r, and 7 '' can be expressed as Qr(6) = -it*(6uYi,1)---y(6r,Yi,r) n i=i where *(*,y) = E^V(7,y).« Proof: 7 '' 71 7r = £ • • • E f t • • • A i \ r ^ £ V ( T I , no • • • noi 71 7r 11 1=1 = ^E{E---Eft^(7l,ni)-"^r>(7r,nr)]} U 1=1 71 7 r = ^E{(E^7^(7i5ni))-:-(E^^(7r,nr))} n i = l 71 7 r = -fyil{8uYi,i)...^{8T,Yi2) • • • \P(cy, Yi>r) 1 A n = - E H** = ^ } i { ^ . , 2 = s2}--. i{Zi t=i i n = Qr(6). Note that since Qr(6) is an average of an r-dependent sequence, it converges to its mean. Therefore, Qr{6) is an unbiased and consistent estimate of Qr(6).» Example 2.2 (Continued) : Recall that ip(0,y) = l,c?(l,y) = y,ip(2,y) = y2. By equation (17), f *(o,y)' ( 1 "2 - 3 1 2 2 1 ^ 2 '¥>(0,y) ^ * ( i , y ) = CT 2 2 -1 v ( i > y ) < * ( 2 > y ) > - 0. Take any (p : C x R —• R, and then define A as the |C| x |C|(= k x k) bias matrix with elements As*, = E 0, then define Qr(6) = if; *(*i,ni)*(fc.na) •••*(*, no where * ( W = £ ^ V ( W i Then QT(S) is an unbiased and consistent estimate of Qr(S). Example 2.3 : We use Figure 2.1 as the true and unobserved image, and Figure 2.2 as the noisy and observed image. The colour set C is {0,1,2}, r is the neighbourhood size, and cr = 0.50. The following tables shows how far away the biased Q r is from the true Q r, and how good and close the unbiased Q r is to the true Q r. 24 Table 2.1: Pattern distribution with r = 1, a denotes the r-dimensional normal density with mean zero and covariance o~2IT, and 6C denotes the colour/pattern at the center of the neighbourhood. Figures 2.5a to 2.5h are the restored images based on different neighbourhood shapes and sizes, and different estimations of the pattern distributions.* 28 3 Joint Estimations of Q and a. 3.1 Introduction Meloche and Zamar (1994) propose estimating z,- by Z% Us MY,- - 6)Qr(6) ' where <5C denotes the colour/pattern at the center of the neighbourhood, and (f>„ is the normal density with mean zero and variance cr2. Furthermore, our proposed estimation of Qr involves cr, and we have been assuming that a is known. Equation (16) states that The subscript a indicates that Qr{6) involves a. But a is likely to be unknown and must be estimated from the noisy image. Ideally, we want to estimate both Qr and cr, but we will focus on the estimations of Qx and cr. Once a is estimated, Qr can also be estimated. For the rest of this thesis, we write Q instead of Qi. In this chapter, we propose some estimating equations for cr. 3.2 Estimation of a using Estimating Equation derived from E(^Yli=i Note that n t i ni=i = lj^E{Zi + cre)2 = -TE(z2 + 2ziae + a2e2) ni=i 29 S ni=l = v2+ ^62Q(8). Thus, if Q \ -(ci -c 3 ) (a 2 - c x c 3 ) -(ci - c3)(cx + c3) (cx - c3) v (ci - c2)(a2 - cic2) (ci - c2)(ci + c2) -(ci - c2) ) 31 where | A| = —(ci — c2)(ci — c3)(c2 — c3). We can write equation (20) in matrix form. Let X(a) = a2-(a2 + ,Z62Q(S)) + ^t62EQa(6) S 6 = a2-cr2 + '£62EQa(6)-Y;S2Q(S). s s Therefore, A(o) = a 2 - a 2 + ATA:1AaQ + ATQ = a2 - a2 + AT(A:1 Aa -I 3)Q, where I Vc 2 C 3 - C l C 2+cJ - C l C 3 / v C 2 C 3 - C l C 2 + c J - C l C 3 ) - ( C 2 C 3 - C l C 2 +cj - C l C 3 — C l C 3 + C l C 2 + C 2 C 3 - C ? , I / a 2 - < 7 * \ ^ - C 1 C 3 + C 1 C 2 + C 3 - C 2 C 3 - C i C 3 + C l C 2 + C 2 C 3 - C ^ / a 2 - c / 2 * - C l C 3 + C l C 2 + C ? - C 2 C 3 - C i C 3 + C l C 2 + C 2 C 3 - C ^ V - C l C 3 + C l C 2 + c i - C 2 C 3 / and -c2(a2 - a2) + c\{a2 - a2) C 2 C 3 — C aC 2 + q — CiC3 —CiC3 + CiC2 + c 2 c 3 — c| -clo*2-*2) -C1C3 + cic 2 + ci - C 2C 3 = -(a2 - a2). As a result, A(a) = a2 - a2 - (a2 - a2) = 0. Thus, when |C| = 3, A(a) defined by equation (20) is identically zero. To get an estimate of a2 when |C| = 3, one possibility is to derive a different estimating equation starting from higher moments of Y{. For example, we start from Y*. 32 3.3 Estimation of a using Estimating Equation derived from E(^YZ=\ Y4) By simple computation, E{-IZY4) = 3cr4 + 6 ) + £ tf4^*) - - £ 1? (23) and taking expectation of equation (23), A(a) = 3a4 + 6a2 £ *2£0„(*) + £ ^.(tf) - £( - £ 1?). (24) 6 6 n i = l According to equation (22), a is one of the root of A(a). By equation (14), Oaiei) = D(c2 - C3)(a2 - c2C3) + (4 - 4)Yi - -& ( < * ) = T ^ D C c i - ^ - C ^ ^ l A l n , = l Then note that An(a) and A(a) defined by equations (23) and (24) are second degree polynomials in a2. As a result, A(a) has 2 roots. The smaller of which is a2. In general, a2 can be estimated as the smallest root of A„(a). In particular, when C = {0,1,2}, $•(0) = ^tli1 - + ( T ) Y i + ( \ ) Y A Qa(l) = iD(«2)l + (2)15 + (-1)1?] n ,=1 4.(2) = ^ D ( ^ ) i + (y)^ + (^ 2] 33 By solving An(a) = 0, we have 1 n 7 n «=i 6 N a2 + Q(l) + 40(2) - - ± \/(Q(l) + 4Q(2) - ^)2. We can conclude that for the colour set {0,1,2}, cr2 can be estimated as i n 7 «=i Although «T2 may not be unbiased, it is consistent. The estimate of a can be obtained by taking the square root of a2. In general, we can derive an estimating equation for cr2 with an arbitrary colour set in a similar fashion when Q r is derived from power functions. 34 4 Neighbourhood Shapes. We have seen in the previous examples that the bigger the neighbourhood size, the better the restoration performance. But this will no longer hold if the neighbourhood size is big while the image is small. Sometimes a good and small neighbourhood may result in better performance in restoration than a big and bad one. The performance of the estimates zi,...,zn can be measured by the average expected square error: 'AMSE = - JT E(Bi - Zi)2 n ,=i According to the theorem by Chan and Meloche (1995), AMSE = - Y, E(z{ - zi)2 = (7,v), 1 such that Qr(6) = - £ n0*(*2, ^,2) • • • * ( * r , K > ) " ,=1 is an unbiased and consistent estimate of Qr(6). At the moment, we lack the theoretical results on judging which set of $(6, y)'s give the best and the most accurate estimate of Q r -We have addressed the problem of estimating a by proposing some estimating equa-tions for a. We have derived an estimating equation from E(^2~27=i Y?) f ° r a colour set with |C| = 2. By solving A„(a) = 0, we have obtained an estimate of a2 for any colour set with |C| = 2. But the estimating equation derived from 2~2?=i Y?) does not work for a bigger colour set when Q r is derived fron power functions. So we have derived another estimating equation from Z)"=i Y*) f ° r a colour set with |C| = 3. Again, by solving An(a) = 0, 38 we have obtained an estimate of a1 for any colour set with | C | = 3. To estimate a2 when | C | > 3, we can derive a different equation starting from a higher moment of Y{. In general, we estimate a2 by deriving an estimating equation for a2 in this fashion. The esimate may not be unbiased, but it is consistent. By taking the square root of a2, we obtain the estimate of a. When Q r is derived from indicator functions, the empirical evidence suggests that A(a) has 2 solutions for a," and the smaller of which is cr. Irrespective of the colour set C, estimating equation (18) always works. Therefore, we do not have to consider higher moments of Y,. But theoretical results have not been reached yet. 39 REFERENCES Anderson, T.W. (1984) An Introduction to Multivariate Statistical Analysis. Wiley. Chan, A., Meloche, J. (1995) Estimation of a Gaussian Mean and Image Restoration. To be submitted for publication. Meloche, J., Zamar, R. (1994) Black and White Image Restoration. The Canadian Journal of Statistics. 22, 3, 335-355. 40 Figure 2.2: Noisy Image (Observed) ^ ?, s ! * y h ' '« - < j k $ M m * * s V - ^ • 41 Figure 2.3: Pattern distribution with r = 3, and (i) (p(8, y) = Indicator functions (a) Q3(S) vs 8 (b) QZ{S) vs 8 (c) Qz{8) vs 8 42 Figure 2.3: Pattern distribution with r = 3, and (ii) (6, y) = Indicator functions (a) Q5(S) vs 6 LL—tn. & -—- » , ...»X.« (b) &() vs £ •*—* - -»•• t (c) vs 6 44 Figure 2.4: Pattern distribution with r = 5, and (ii) ip(6,y) = Power functions (d)Qs(6)vs6 (e) Q5(S) vs 8 t } (f) Q5(6) vs ,5 45 Figure 2.5: Restored Image, ip(6,y) = Ind ica to r Figure 2.5: Restored Image,