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,
( o , t f ) 1 n 1 n . = i 10 and Qi to be the vector (Qi(0), Qi(l))T. This Qi is a biased estimate of Qi because, for example, EQl{0) = £ ± E 1 { * ; - < n I = -EPf>,- + ere,- < -) n 2 = ^E{P(e,- < ±-)\{zi = 0 } + P(c- < £)l{zi = 1 } } = IE1{Z,- = 0}$(i-) + ± E 1 { * = 1 } * ( ^ ) n la n la Similarly, EQx(l) = $(^ -)<2i(0) + $(±)Qi(l), where $(•) is the cumulative distribution function of a N(0,1) random variable. Now we let a = b — $ ( 5 7 ) , then we can write the above in matrix notation. £Qi = AiQi where Ax = t a b b a So, an unbiased estimate can be obtained by inverting Ai and defining Qi = Ax 1 Q 1 , so that EQi = Af^Qi = A^AiQi = Qx. That is, and Qi is unbiased for Qi. 11 Using the same colour set C, we now consider linear 3-site neighbourhoods, that is, 3 pixels in a row, either vertically or horizontally, with C = {0,1}. As we have just mentioned in Example 1.1, there are 23 = 8 possible patterns, namely 000, 001, . . . , 111. Recall from equations (1) and (2) in Chapter 1 that 1 n Qsi^l, <$2, fa) = - 53 Hzi,l ~ fa,zi,2 = fa, Z,,3 = fa}, where <5,- = 0,1, i — 1,2,3. Following the same idea as above, define 03(000) = ±Y:i{Yi,i<\}HYi,2<\}l{Yi>3<\} $3(001) = I^i{y;.1I} W i l ) = ^HYi^lMY^^^Wt^^}. Again, we write Q3 for the vector (g3(000), $3(001), $3(010),..., <23(111))T. In the case of 2 grey levels, we use two indicator functions, \{Yi < |} for black pixel, and l{Yi > |} for white pixel (for single-site neighbourhoods). That is, if Y{ < | , then we say that the colour at site i is black. And if Yi > | then we say that the colour at site i is white. Observe that there is a relationship between Qi and Q3. In the case of linear 3-site neighbourhoods, we use products of 3 indicators chosen from l{Yi < |}, l{Yi > |}. So Qi and Q3 have similar structure. Since Qi is biased for Qi, we would expect that Q 3 is also biased for Q3. Now, we can compute the expectations of Q3(6i, 62, S3)'s. For example, EQ3(000) = E^l{Yitl < \}\{Yia < l-}l{Yi<3 < \) 12 = < \)P(Yia < \)P(Yii3 < i ) = ±p{[P{eitl < =0} + Pfa < = 1}] x [ ^ , 3 < ^ ) l k 3 = 0} + P ( e ^ < ^ ) l h 3 = l}]}. Performing similar calculations for the other seven expectations, and letting a be and 6 be $ ( 5 7 ) , we get E ' 03(000) > 3 a26 a2b ab2 a2b ab2 ab2 b3 > ( Q3(000) > 3(ooi) a26 a3 ab2 a2b ab2 a2b b3 ab2 3(001) Qs(OlO) a26 ab2 a3 a2b ab2 b3 a2b ab2 Qs(OlO) <33(011) a62 a2b a2b a3 b3 ab2 ab2 a2b Q3(0ll) Q 3 ( i o o ) a26 ab2 ab2 b3 a3 a?b a?b ab2 Q 3 ( i o o ) g 3 ( i o i ) ab2 a2b b3 ab2 a2b a3 ab2 a2b 3 ( ioi) Q 3 ( n o ) ab2 b3 a2b ab2 a2b ab2 a3 a2b Q 3 ( n o ) ^ $ 3 ( 1 1 1 ) , v 6 3 ab2 ab2 a2b ab2 a2b a2b , 03(111) J In matrix notation, we can write the above as £Q 3 = A 3 Q 3 As before, we obtain an unbiased estimate of Q3 by defining Q3 = A 3 1 Q 3 . As shown in Meloche and Zamar (1994), the above matrices Ai, A 3 (as well as the corresponding ones for all r) can be analytically inverted. Meloche and Zamar (1994) show that, in general, EQT — A r Q r with A R ( 6 \ 7 ) H«) # (* , 7W~ # (* , 7 ), 13 (5) where A r ( £ , 7 ) is the ( £ , 7 ) entry of A r , and # ( £ , 7 ) = 9 Sk = 7*:) is the number of k such that 6k = "fk, for k = 1,2,..., r, and that Ar-1(^,7) = (-1) (62 - a2)r (6) where a = $ ( 5 7 ) , 6 = $ ( 2 7 ) - Equation (6) is valid for all r-site neighbourhoods, where r is arbitrary and finite, with C = {0,1}. As an application of equations (5) and (6) in the case of 2-site neighbourhoods, an unbiased estimate of Q2 is f $ 2 ( 0 0 ) N ( aa ab ba u\ - 1 ' g2(oo) ^ Q2(01) ab aa bb ba Q2(oi) 2 (10) ba bb aa ab $ 2 ( 1 0 ) ^ 0 2 (H) j K bb ba ab aa j ^ $ 2 ( 1 1 ) j where Q2(00) = ^Wa < \}W,2 < \} g2(oi) = -vm* < hma > 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 ) 2(02) ag ah ai bg bh bi eg ch ci Q 2 (02) 2(io) da db dc ea eb ec fa fb fc Q 2 (10) Q 2 ( H ) = dd de df ed ee ef fd fe ff 0 2 ( i i ) 02(12) dg dh di eg eh ei fg fh fi Q 2 (12) 02(20) ga gb gc ha hb he ia ib ic Q 2 (20) 2(21) gd ge 9f hd he hf id ie if g 2(2i) ^ 02(22) j \ 99 gh hg hh hi ig ih ii j < S2(22) j or EQ2 = A 2 Q 2 in matrix notation: But now, A 2 does not seem to have a simple structure.* In the case of binary images, observe that the two bias matrices, Ai, A 2 are closely related. In fact A 2 is a 2-fold Kronecker product of Ai. Definition 2.1 (Kronecker product of matrices) : Let A = (a,j) be a p x m martix and B = (bap) be a q x n matrix. The pq x mn matrix with aijbap as the element in the i,ath row and the j,/?th column is called the Kronecker or direct product of A and B and is denoted by A ® B; that is, A ( * , * ) ( 1 0 ) n ,=1 Qr(6) = ^f:^(61,Yi,1)(p(82,Yi,2)... ) then £ Q r = A * r ) Q r (12) where A\(8,7) = Eip(8,~f + ere), and A ^ is the r-fold Kronecker product of A i . A ^ is a |C| r x |C| r matrix, where |C| is the size of the colour set. Furthermore, if | A i | > 0, then Q r = (Af 1 ) ^ Q r is an unbiased estimate of Q r .» Proof : We start the proof by expressing the equation EQr = A r Q r . We need to show . EQT{6) = Y,M6,l)Qr{l) (13) 7 for all 6. Note that 18 EQT{6) = E-J2v(^YiA)---V(SriYitr) n i^i = - £ %>(*!, E 1{*M = 7l} • • • K>) E 1{*> = 7r} 7 1 i = l 71 7r 1 " = -EEH^.l = 7l}^ V(<5l,7l + ^ 0---E1{^,r = -yr}E (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,Yi 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 (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,