Cylindrical R F Tomography by K i m Lam B . A . S c , University o f British Columbia, 2001 A T H E S I S S U B M I T T E D IN P A R T I A L F U L F I L M E N T O F THE REQUIREMENTS FORTHE DEGREE OF Masters o f Applied Science in The Faculty o f Graduate Studies Department o f Electrical and Computer Engineering We accept this thesis as conforming to the required standard T H E U N I V E R S I T Y OF BRITISH C O L U M B I A November 2003 Â© K i m Lam, 2003 Library Authorization In presenting this t h e s i s in partial fulfillment of the requirements for a n a d v a n c e d d e g r e e at the University of British C o l u m b i a , I a g r e e that the Library shall m a k e it freely available for reference a n d study. I further a g r e e that p e r m i s s i o n for extensive c o p y i n g of this thesis for scholarly p u r p o s e s m a y be granted by the head of my department or by his or her representatives. It is u n d e r s t o o d that copying or publication of this thesis for financial gain shall not be allowed without my written p e r m i s s i o n . L iWiA -M n \ y OIL N a m e of A u t h o r (please print) Title of T h e s i s : Degree: p( ( y |, j y> L J\S n L | JO Date \{f- J, Year: , -X 6C j Abstract Tomography allows the examination of an object's interior without having to destroy the object. There have been many forms of tomography including MRIs and CT scans. A l l forms of tomography infer the interior of an object from a set of measurements. A n algorithm to infer the features of infinite dielectric cylinders using electromagnetic waves is developed in this thesis. The intended application for this algorithm is the imaging of lumber. The algorithm recovers the dielectric permittivity distribution from an infinite cylinder. It uses Richmond's Method to model the physical behavior of the infinite cylinder. The algorithm uses an iterative non-linear inversion scheme to recover the dielectric permittivity distribution. The non-linear inversion scheme uses a regularization term that minimizes the structure of the permittivity distribution subject to a constraint involving the measured scattered field from the cylinder. It was found that by decreasing the weighting of the regularization, and eventually turning off the regularization, the exact permittivity distribution can be recovered for a noiseless and over-determined system. In the presence of noise, an approximate permittivity distribution can be recovered; however regularization cannot be turned off. Similarly, for an under-determined system, an approximate permittivity distribution can be found, but regularization cannot be turned off. ii Table of contents Abstract Table of contents List of figures List of tables ii iii v vii Chapter 1: Introduction 1.0 Introduction 1.1 Thesis overview 1.2 Novel content 1 8 9 Chapter 2: Examination of a 2-D homogeneous cylinder 2.0 Introduction 2.1 2-D scattering solution 2.2 How to compare observations of different permittivity values 2.3 Numerical results 2.4 Conclusion 11 11 15 15 22 Chapter 3: Mathematical background for the tomography algorithm 3.0 Introduction 3.1 Richmond' s Method 3.2 The development offhe integral equation for Richmond's Method 3.3 The scattered field 3.4 Observations for inversion 3.5 Gridding for the Jacobian calculation 3.6 Derivation of the Jacobian for locations internal to the dielectric body 3.7 Derivation of the Jacobian Matrix for the scattered field 3.8 The Jacobian for multiple frequencies 3.9 The flatness term 3.10 The system of linear equations 3.11 Conclusion 23 24 24 26 26 28 30 31 32 33 34 36 Chapter 4: Implementation of the tomography algorithm 4.0 Introduction 4.1 Tessellating the cylinder 4.2 Calculating the flatness matrix 4.3 Calculating the internal field using Richmond's method 4.4 Generation of the observation matrix 4.5 The Jacobian Calculation 4.6 Inversion function with a single beta value 4.7 Inversion function with multiple beta values 4.8 Summary 37 38 41 45 45 46 51 54 56 Chapter 5: Numerical experiments using the tomography algorithm 5.0 Introduction 57 iii 5.1 5.2 5.3 5.4 5.5 5.6 5.7 5.8 5.9 Setup for the experimental procedure Test cases 1,2 and 3 Norms for assessing the quality of the solution Experimental set 1 Experimental set 2 Experimental set 3 Experimental set 4 Experimental set 5 Conclusion 58 61 64 65 71 76 81 85 88 Chapter 6: Summary and future work 6.0 Summary 6.2 Future work 90 92 Bibliography 93 iv List of figures Figure Figure Figure Figure 1.1 1.2 1.3 1.4 Figure 2.1 Figure 2.2 Figure 2.3 Figure 2.4 Figure 2.5 Figure 2.6 Figure 2.7 Figure 2.8 Abstraction of the scattering from a dielectric body Abstraction of forward modeling process Schematic for linear inversion Schematic for non-linear inversion 1 2 2 3 Geometry of the scattering problem 11 Definition of electromagnetic fields inside and outside of the cylinder. 12 Geometric configuration of observation points 16 Variation surface for permittivities from 1 to 10 17 Variation slices for a homogenous cylinder 18 Zeros of the a <Â£^)-a (s ) for e equals 5 19 Multifrequency variation slices for a homogenous cylinder 21 Multifrequency variation surface for permittivities from 1 to 10 22 n n 2 x Figure 3.1 Arrangement of the multi-frequency observation vector Figure 3.2 Illustration of the mapping concept Figure 3.3 Structure of the multi-frequency Jacobian 27 28 33 Figure 4.1 Flow chart for the complete inversion system Figure 4.2 Illustrative diagram of the discretization concept Figure 4.3 Flow chart for the B a s i c l n v e r s i o n function 37 39 51 Figure 5.1 Inversion cells for Experimental sets 1, 2 and 3 Figure 5.2 Modeling cells for Experimental sets 1, 2 and 3 Figure 5.3 Superposition of modeling regions and inversion regions Figure 5.4 Test case 1 Figure 5.5 Test case 2 Figure 5.6 Test case 3 Figure 5.7 Variation plot for experimental set 1 Figure 5.8 Modeling error plot for experimental set 1 Figure 5.9 Recovered permittivity distribution for experimental set 1, test case 2 and 8 = 0 Figure 5.10 Recovered permittivity distribution for experimental set 1, test case 2 and 8 = 0.001. Figure 5.11 Variation as a function of iteration for experimental set 1, test case 2,8 = 0 and B = 0.001 Figure 5.12 Variation plot for experimental set 2, method 1 Figure 5.13 Variation plot for experimental set 2, method 2 Figure 5.14 Modeling for experimental set 2, method 1 Figure 5.15 Modeling for experimental set 2, method 2 Figure 5.16 Image of permittivity distribution experimental set 2, test case 3, method 1, and iteration 7. Figure 5.17 Image of permittivity distribution 59 60 61 62 63 64 66 67 v 68 69 70 71 72 73 74 75 experimental set 2, test case 3, method 2, and iteration 21. Figure 5.18 Variation plot for experimental set 2 (20% noise), test case 3 Figure 5.19 Modeling error plot for experimental set 2 (20% noise), test case 3 Figure 5.20 Permittivity distribution for experimental set 3, test case 3, and iteration 30 Figure 5.21 Permittivity distribution for experimental set 3, test case 3, and iteration 31 Figure 5.22 Permittivity distribution for experimental set 4 Figure 5.23 Variation plot for experimental set 4, experiment 1 Figure 5.24 Modeling error plot for experimental set 4, experiment 1 Figure 5.25 Permittivity distribution for experimental set 5 Figure 5.26 Variation plot for experimental set 5, experiment 1 Figure 5.27 Modeling error plot for experimental set 5, experiment 1 Figure 5.28 Permittivity distribution for experimental set 5, experiment 1, iteration 41 vi 76 77 78 79 80 81 83 84 85 86 87 88 List of tables Table 2.1 Table 5.1 Table 5.2 Table 5.3 Local minimum values at 4 discrete points Summary of experiments for chapter 5 Parameters for the experimental sets 1, 2 and 3 Parameters for the experimental set 4 vii 18 57 58 82 Chapter 1 Introduction 1.0 Introduction There has been much interest in microwave imaging (MI) otherwise known as microwave tomography. The Greek root 'tomo' means to slice or section, and tomography is a general term for obtaining an image of a slice of a target. Tomography techniques such as CT scans and MRIs are routinely used in medicine [Hendee and Wells, 1997]. MI is based on the measurement of a scattered field from an object illuminated by electromagnetic (EM) waves. A n object is first illuminated with a microwave source. This results in secondary waves, known as the scattered field. M I is the recovery of the permittivity distribution of an object, based on measurements of the scattered field. To recover the distribution, an inversion algorithm is needed. The process of inversion recovers the parameters of an operator when the operator and the scattered field are known. Figure 1.1 shows a schematic of the physical system. Figure 1.2 illustrates the forward modeling problem. The differential operator simulates the physical system mathematically and can simulate the scattered field, when operating on the incident field. The first step in Figure 1.2 illustrates that a mathematical description of the entire system must be generated. It is then inverted to produce an operator that relates the incident field to the scattered field. The second step is to obtain the scattered field. Incident wave Material Parameters Data Figure 1.1: The diagram represents the abstraction of the physical system. The incident wave interacts with the Physical system, denoted by the "Material Parameters" box, and the resulting electromagnetic fields are measured. 1 Step 1: Inverse of operator (equivalent to Green's function) L Differential ' operators including .parameters 1 Step 2: L" 1 Source (incident wave) Solution (predicted data) Figure 1.2: Schematic of the forward modeling process. A differential operator models the characteristics of the physical system. This operator is then inverted and applied to the incident wave to generate a scattered field. Inversion can be separated into linear or non-linear inversion. The linear inverse for MI is obtained by discretization of the integral operator to obtain a linear vectormatrix relationship between the data and the parameters. A generalized matrix inversion is then performed to obtain the parameters. The generalized matrix inversion minimizes an objective function typically interpreted to be a best linear fit, while minimizing a square error. The minimization occurs in a single step. In the case of a square matrix the solution is exact and the objective function is zero. Linear Inverse Data â€¢Parameters Figure 1.3: Schematic for the linear recovery of the material parameters. A linear inverse is first taken. This is applied to the measured scattered field to recover the permittivity values. For non-linear inversion, a direct matrix mapping from data to the parameters cannot be obtained. For this type of inversion an objective function is, also, defined and is either minimized or maximized. This technique is iterative. The objective function approaches its minimum after each iteration. The minimum is reached after several iterations. During each iteration, the parameters are estimated by examining some 2 property of the objective function, either its value or its derivative. Based on the results of the objective function, the inversion algorithm determines the next set of estimated parameters. This set of parameters leads to a better solution. Figure 1.4 illustrates schematically the results of an iteration. Non-Linear operator Data Parameters Figure 1.4: Schematic for non-linear inversion. The Non-Linear operator acts upon the data to give the parameters. The non-linear operator may be iterative in nature or may have multiple parameters as possible solutions. M I can be applied to many problems. Much recent literature [Hagness et al., 1998][Semenov et al., 2002 ] points to medical imaging as a promising area of study. To image biological objects, microwaves travel through material with high dielectric permittivity and high dielectric contrast. A particular biological application of importance is the imaging of trees. Regions of high dielectric permittivity indicate areas of rot, due to the accumulation of water. Therefore, the location of these regions can be found using microwave tomography providing in-vivo and in-situ assessment of the wood quality of the target tree. The author of this thesis is unaware of any previous successful attempts to apply M I to trees. When a microwave travels into an object, part of the wave is trapped inside the object, while part of the wave is scattered from the object. The trapped waves constantly reflect off the boundary of the object. If the object is inhomogeneous, the reflections within the object become more complicated. The trapped waves continuously leak out of the object. These leaked waves form part of the scattered field. The scattered field is, therefore, composed of the leaked and scattered waves. 3 Many techniques have been used to solve the inverse scattering problem, with varying degrees of success. The Born approximation is the simplest imaging method. The Born approximation approximates the internal field of the scatterer with that of the incident field. The total field, exterior to the scatterer, is then assumed to be a linear combination of the incident field and a scattered field. The inverse operator can be calculated using the assumed incident field, yielding a linear inversion algorithm which is solved by a matrix inverse, as described previously. The Born approximation fails when a moderate to high dielectric contrast exists [Slaney et al., 1984]. This failure occurs because of the strong scattering behavior leading to an internal field that is quite different than that of the incident field. This behavior is due to the scatterer behaving like a leaky waveguide structure. More recently, imaging using high bandwidth chirp pulses, and confocal imaging, has been studied [Hagness et al.,1998]. The technique of confocal imaging is based on the idea that the microwave chirp behavior approximates that of rays. Simulations of confocal imaging indicate that structures as small as 2mm [Hagness et al.,1998] can be detected inside breast tissue. The work on confocal imaging has largely been related to breast cancer detection. One of the first researchers in M I [Joanchimowicz et al. 1991] applied non-linear inversion techniques to an E M inverse scattering problem used to detect bone and muscle tissue. Joanchimowicz et al. used a Newton-Kantorovich's procedure to find the minimum of an objective function. Their process was iterative and used multiple illumination angles of the object. 4 Caorsi develops a number of inversion algorithms. Caorsi et al. also builds a physical system for imaging. He uses simulated annealing (SA) [Caorsi et al, 1991] for one of his inversion procedures. The SA method recovers an approximate permittivity distribution, while using multiple illumination angles. Caorsi, also, experiments using a pseudo-inverse technique as an inversion scheme [Caorsi et al., 2003]. The pseudoinverse is the analog of an inverse for a non-square matrix [Golub and Van loan, 1996] [Wilkinson and Peter, 1970]. Chew and Lin [Chew and Lin,1995] explore the use of multiple frequencies for dielectric imaging. Chew and Lin hypothesize that the Born approximation is good for low frequencies. Chew uses the Born approximation to find an approximate distribution at low frequencies and then moving to an optimization scheme at higher frequencies, Chew uses results from a low frequency imaging technique as a starting point for a higher frequency technique. Since only one frequency is used at a time, their technique is known as "frequency hopping". For low frequencies, Chew and Lin uses the distorted Born method [Wang and Chew, 1989] and for high frequencies the conjugate gradient method is used [Borup and Gandi, 1985]. The distorted Born method assumes that the internal field is dependent on the permittivity distribution, compared to the Born method where the internal field is assumed to be that of the incident field. In the Born method, the Green's function for a homogenous background is used, while the distorted Born method employs an approximate Green's function for an inhomogeneous background. Chew and Lin quantitatively recover the permittivity distribution when an object is submerged in water. Submerging the object in water reduces the contrast between the 5 background and the object, leading to less reflection from the surface of the object, resulting in very limited trapped wave energy. â€¢ In 1998, Pastrorino et al. [Pastorino et al., 1998] experiments with using genetic algorithms for solving the inverse scattering problem. He, also, presents an overview of imaging technology for MI. A genetic algorithm is an optimization technique based on the concept of mutation and a fitness function. The fitness function is similar to the objective function previously described and is used to determine the quality of the solution. To obtain a better solution, many sets of random changes are introduced. The set of random changes with the highest fitness value is the solution selected as the starting point for the next iteration. More recently, Semenov et al. [Semenov et al., 2002] builds a 3-D tomography system based on earlier work on 2-D imaging [Souvorov et al.,1998]. It was noted that a 2-D slice method is inappropriate for modeling 3-D structures and an intrinsically 3-D algorithm must be used. Semenov et al. are capable of recovering an approximate distribution of a slice of a dog using their 2-D and 3-D algorithms. A modified Newton iterative scheme is used for their 2-D imaging method [Souvorov et al., 1998]. A gradient method for is used for the 3-D imaging method [Semenov et al.,1999]. Lin et al [Lin and Chui., 2001] produced a 2 step algorithm, similar to that of Chew and Lin [Chew and Lin., 1995]. Lin's method differs from Chew's method because frequency hopping is not used. Lin separates the problem into a linear step and a non-linear step. The Lin algorithm uses the distorted Born approximation to recover an approximate distribution of the dielectric permittivity for the linear step. The approximate distribution is used as a starting point for the conjugate gradient algorithm to 6 find a detailed solution. The conjugate gradient algorithm uses the full non-linear formulation of the E M problem to solve the inverse problem, resulting in a better solution. Their experimental-setup requires that the body be placed in a matching fluid. Their solution allows the recovery of inhomogeneities in the body. Caorsi [Caorsi et al., 2003] recently introduced a multi-scaling scheme that can be applied to any iterative inversion technique. The technique starts with a coarse grid; when an anomaly is detected in a square quadrant of the grid, that quadrant is descretized more finely. Success is achieved in recovering a number of permittivity distributions by coupling this scheme with the conjugate gradient method. The work presented here is different from that of previous work in several regards. First, this work is inspired by work done in the field of geophysics inversion, specifically the work done by the University O f British Columbia Geophysical Inversion Facility (UBC GIF). Second, this work is not focused on medical imaging; instead imaging of trees is the intended application. The imaging of trees poses a difficult problem because of the existence of a high dielectric contrast boundary at the surface of the tree. This creates two problems. The first problem is the large amount of reflection at the boundary of the tree. The second problem is the tendency for waves to be trapped inside the tree. The inclusion of the trapped waves in the inversion algorithm represents a significant departure from previous work [Joanchimowicz et al., 1990]. The U B C GIF is an academic research unit focusing on the development of geophysical forward modeling and inversion methodologies. Their work is based on physical and intuitive ideas for the use of inversion. The U B C GIF view the minimization problem as a problem of minimizing the structure of the solution using the 7 data as constraints. This work applies the regularization term of "Minimizing Structure" [ Farquharson and Oldenburg, 1998] introduced in geophysical optimization. Farquharson goes into extensive detail on L2 norms, and non-L2 norms. This work is limited to L2 norms. Minimizing structure in the solution is an idea that has an associated physical interpretation. Large structural variations, measured by the norm of the first order derivatives, are penalized, resulting in more plausible models. For this work, an objective function based on a linear combination of the norm of the structure of the system and the norm of the difference between predicted data and measured data is defined for this work. This effectively incorporates the idea of minimizing structure, subject to data constraints, into the inversion algorithm. A linear approximation, based on the Taylor expansion of the objective function, will be generated. The linear approximation will be minimized. B y repeating this process many times, an iterative process is created to find the minimum of the objective function. Previous regularization techniques, in fields outside geophysics, used purely mathematical regularization techniques to eliminate the ill-posedness of the problem. Previous work is M I [Ciric and Qin, 1997][Tanaka et a l , 2001] viewed the problem as one of minimizing the difference between the measured scattered field and guessed scattered field. These techniques have little relationship to the actual physical system. 1.1 Thesis overview Chapter 2 will present the solution to scattering from a homogenous circular cylinder illuminated by a plane wave. The solution is based on the Bessel mode expansion of the problem. A n odd scattering behavior is presented. Chapter 2 provided a great deal of insight into the problem of scattering. 8 Chapter 3 presents all the mathematics necessary to perform the inversion. This includes Richmond's Method [Richmond, 1965] for forward modeling. Richmond's Method is used to obtain the scattered field. Next, the Jacobian calculation is derived from Richmond's Method. The concept of "Minimizing Structure" is formally introduced in matrix form as the flatness matrix. The objective function is introduced that includes the flatness matrix and the scattered field. The Jacobian matrix is used to linearize the scattered field and finally, a method to linearize the objective function is shown. Chapter 4 demonstrates the implementation of the algorithm using MatLab. The mapping between Chapter 3 and the source code is presented. Chapter 5: presents results, using the algorithm. This chapter explores the behavior of the algorithm and presents some very promising results. First, the algorithm uses a constant scaling to the regularization. This demonstrates that regularization helps to find the correct solution. Next, decreasing the scaling of the regularization as the iterative process proceeds. B y decreasing the scaling of the regularization, the system is allowed to assume more structure and is analogous to slowly cooling the system in simulated annealing [Caorsi et al., 1991]. The most novel result is that the solution slowly emerges as the amount of regularization is decreased. The algorithm recovers the permittivity distribution in noisy data and in an under constrained system. 1.2 Novel content This thesis demonstrates the successful development of a tomography algorithm, by using electromagnetic waves. The regularization technique is taken from geophysical inversion and has not been applied the electromagnetic scattering problem. The 9 regularization enforces a flat starting model, reducing the choices of starting model. This represents a significant improvement over previous algorithms, where the problem of convergence has been solved, but the equally complicated starting model problem has not been solved. A novel unified modeling-inversion notation has been created through the use of indicator matrices. This thesis, also, introduces a previously unknown scattering behavior. Scattering from homogeneous cylinders with different permittivities can have very similar scattered fields. The difference in permittivities that yields very similar scattered field follows a regular pattern. The approximate non-uniqueness of the scattered field is resolved by using multiple frequencies. 10 C h a p e tr 2: E x a m n ia o itn of a 2-D h o m o g e n e o u s c y n ild e r 2.0 Introduction This chapter examines scattering from a homogenous dielectric circular cylinder, illuminated by a T M wave. This problem is examined to give insight into scattering from an inhomogeneous cylinder. Initially, the solution to scattering from a cylinder is presented. Next, the similarity between the scattering patterns of different permittivity values is examined. This provides insight into the inverse problem. 2.1 2-D Scattering Solution Tjicoming plane wave: Figure 2.1: Geometry of the scattering problem. 11 The geometry of the system is shown in Figure 2.1. The origin, for both Cartesian coordinates and polar coordinates, is at the center of the cylinder. For derivation, the time factor e jwt isassumed and phasor quantities are used. A T M wave, where the E field is parallel to the cylinder axis, is assumed and can be written as Equation 2.1 with k , the wave number, and E\, the amplitude of the z component of the incident field. E\x,y) = E[e- z jkx =E ^ ^ z (2.1) Because the problem involves cylindrical geometry, rewriting Equation 2.1 in a Bessel function expansion makes the problem easier to solve. Rewriting Equation 2.1 as a Bessel function expansion, and using polar coordinates Equation 2.2 is obtained [Harrington, 1961]. E (p,<t>)=Eif j-"J (kp)e "*z i (2.2) J j n n=~<x> The scattering problem can be solved as a boundary value problem. The boundary is defined as the surface of the cylinder. At infinity, the scattered field is expected to be zero. Figure 2.2: Definition of electromagnetic fields inside and outside of the cylinder. 12 The boundary conditions are presented in Equation 2.3a and Equation 2.3b and are applied at the boundary of the cylinder. The tangential components of the total electric(Â£T) and m a g n e t i c ^ field must be continuous across the boundary of the cylinder. nx(H (a,<f>)-H (a,</>)) = 0 (2.3a). Bx(Â£,(fl^)-Â£ (a^)) = 0 (2.3b) ] 2 2 Equation 2.4 is a convenient representation of the resulting field with a known and an unknown portion. The Incident field is the known portion and the scattered field is the unknown portion. E {pj) l = E' "(p,j)+E"*'(p,j) (2.4) , Upon examining Equation 2.3a and Equation 2.3b, it appears that there are 4 unknowns and 2 boundary conditions. To reduce the number of unknowns to 2, Equation 2.5a is used to link E and H. The explicit relationship in polar coordinates is given in Equation 2.5b. VxE = -jo)/u(co)H H = 15Â£. j(op{a>)\â€”: p p dtp (2.5a) dE , (/) dp (2.5b) The scattered field is assumed to be written as Equation 2.6 [Harrington, 1961], with unknown coefficients aâ€ž and the total field exterior to the cylinder satisfies Equation 2.4. The total field inside the cylinder can be represented as Equation 2.7a with the unknown coefficient câ€ž [Harrington, 1961]. In Equation 2.7b, e is the permittivity r inside the cylinder. 13 E^E^raM'me^z (2.6) n=-oo E2=E[f rc J {k p)e^z (2.7a) d=k^s (2.7b) j n n d k r By applying the T M assumption, Equation 2.3b can be rewritten as Equation 2.9a which immediately implies equation 2.9b because the unit vector <f> cannot be zero. hx(E ~E )z ] Â£, - Â£ = px(E 2 -E )z l = -(E -E }p 2 { 2 =0 2 =0 (2.9a) (2.9b) Applying Equation 2.5b to Equation 2.3a, gives Equation 2.10. The normal vector to a circle is p . The term involving p in Equation 2.3a disappears because of the h x operation. dE,\ 8E, ^ 2 J dp _ Q (2.10) dp By plugging Equations 2.6 and 2.7a into Equation 2.9 and Equation 2.10, a system of 2 equations with 2 unknowns is produced. The 2 equations are Equation 2.1 l a and Equation 2.11b. a H^\ka) n a kHl '(ka) 2) n + J (kd) - câ€žJ (k a) = 0 n K + Uâ€ž'(ka)-c k J:(k a) n d (2.1 la) d =0 d (2.11b) The explicit solution for a is given by Equation 2.12. The only coefficient n needed is a because the solution to the field inside the cylinder is not needed. n 14 a =- Â» J ' {Ka)l k aJâ€ž (k a) - j' (kg) I kaJ (kg) e Jâ€ž \k a) I k aJ (k a) - H '(ka) I kaH ' (ka) Â£ J { k a ) d n d d n n ( 2) d d d n d n (2.12) n 2.2 How to compare observations of different permittivity values This thesis is concerned with the inverse scattering problem. The similarities between the scattered fields are now examined as a function of permittivity, yielding insight into the inverse problem. The scattering field is expected to be very similar for permittivity values that are close together and significantly different for permittivity values that are far apart. The variation of the scattered field at different permittivity values is quantified in Equation 2.13, where M i s the number of observations points. M ZI*:(*.)-*:fc)T (2.13) M Equation 2.13 is clearly small when two scattering fields are similar. 2.3 Numerical results Equation 2.13 is examined in this section. The geometric configuration of the observation is a circle. The configuration is shown in Figure 2.3. 15 0.5h -0.5h -0.5 0.5 1.5 Figure 2.3: Geometric configuration of observation points. There are 360 observations points spaced 1 degree apart. Figure 2.4 is a 2-D variation surface computed using Equation 2.13. The x and ; axes represents Â£,and e in Equation 2.13, respectively. The line, where e equals e 2 l represents the global minimum. There are also several bands of local minima approximately parallel to the e equals e line. l 2 16 2 '2 ' Misfit behavior in 2D reference epsilon Figure 2.4: Variation surface for permittivities from 1 to 10. The shading represents the variation value. The line, where Â£, equals Â£ , is the global minimum. 2 Figure 2.5 shows slices of Figure 2.4 by fixing Â£, and varying s 2 from 1 to 10. Examination of a slice of the variation surface at s equals 9.9 shows the existence of x local minima; there are two very deep local minima. The variation equals 0.0359 at the closest local minimum. Because 0.0359 is small, when compared to the maximum variation of approximately 0.8, the two scattered fields are very similar. The foregoing case of E equals 9.9 is shown in the bottom right coiner of Figure 2.5. The other X variation plots exhibit a similar behavior which is tabulated in Table 2.1. 17 Figure 2.5: Variation slices for a homogeneous cylinder of radius lXand observation distance of 1.5 X. Top left, cylinder with permittivity of 2.5, top right, cylinder with permittivity of 5.9, bottom left, cylinder with permittivity 6.9, bottom right, cylinder with permittivity 9.9. The local minima are problematic for inversion using gradient descent search techniques. Choosing a starting permittivity value far from the true permittivity value, the search algorithm may get trapped inside a local minimum. Table 2.1 Local minimum values at 4 discrete points. Permitivity 2.5 5.9 6.9 9.9 Deepest local minimum 0.0997 0.0218 0.0225 0.0359 Equation 2.7 is identical to that of a Discrete Time Fourier Transform(DTFT) if p is fixed, <j) replaces the frequency variable and a replaces the coefficient in the DTFT. n The DTFT has a one-to-one mapping between the infinite set of coefficients and the 18 continuous signal. For Equation 2.13, if the two minima are exactly zero then Equation 2.14a must be true for all n values. B y combining Equation 2.12 and Equation 2.14a, and simplifying, Equation 2.14b is produced. n(e )-aâ€ž(e ) =0 1 Jâ€žM_ 5,J' {a8,) 1 Jâ€ž(<*8 ) 5 J' (a5 ) a l 2 (2.14a) 2 2 n n (2.14b) 2 a = ka (2.14c) (2.14d) S =JÂ£ 2 (2.14e) 2 Distribution of zeros for s = 5 10 Q. 0) 5*- x x -1.0 x -8 n x - a (e ) n X X . X X X X x x x x x x x x - s -4 -6 Figure 2.6: Zeros o f a (e ) satisfied. x 2 for k 10 e x equals 5. The x's mark the location where the equation is 19 Figure 2.6 is an examination of Equation 2.14a with fixed e,. Note that, e does 2 not line up for different n indexes. However, they are close. This implies the local minima behavior seen in Figure 2.5. The deep local minima are problematic for inversion. The multiple minima imply that, in the presence of noise, uniquely determining the permittivity value may not be possible. By adding the variation from multiple frequencies the contrast between the local minima and global minimum can be increased. # = Z> (/,,) ft (2-15) g Figure 2.7 illustrates the use of multiple frequencies. Three values of k are used. The lowest values is 20% below the highest value. The local minimums are significantly higher than those shown in Figure 2.5. For the total variation, the global minimum stays fixed. 20 Figure 2.7: Multifrequency(&=1.67r, 1.8 ir, 2 ir) variation slices for a homogenous cylinder of radius IX and observation distance of 1.5 X. Top left, cylinder with permittivity of 2.5, top right, cylinder with permittivity of 5.9, bottom left, cylinder with permittivity 6.9, bottom right, cylinder with permittivity 9.9 The advantage of using multiple frequencies is illustrated more dramatically in Figure 2.8 Figure 2.8 is a variation surface, similar to that of Figure 2.4, but uses multiple frequencies. Figure 2.4 uses size frequencies, and all the deep local minimums have been eliminated. 21 Figure 2.8: Multifrequency (k = % 10. 1.2T, 1.4TT, 1.67T, 1.87T, 2ir) variation surface for permmitivities from 1 2.4 Conclusion This chapter shows that the use of multiple frequencies is necessary for the recovery of the dielectric constant of a homogenous cylinder. Without the use of multiple frequencies, scattering patterns from different permittivities may look very similar. In the presence of noise, these scattering patterns will be indistinguishable. Using more than one frequency helps make the scattering pattern from different permittivities more distinguishable. Usage of multiple frequencies changes the variation in such a way that the gradient search technique is more likely to work. 22 to C h a p e tr 3: M a h te m a c ita lb a c k g r o u n d for the o tm o g r a p h ya g lo r t h im 3.0 Introduction This chapter is separated into 2 main parts. The first part develops the mathematical background needed for substitution into Equation 3.1. The second part develops a constrained set of linear equations from Equation 3.1. The solution to As' can be found, once the linear system is developed. The solution for As , which forms 1 the basis for the inversion algorithm, is given by d -d{s')-lAe ref mm As' r 0 = N NÂ° f JSJF^' + N~' +AS']' (3.1) In Equation 3.1, J, F and d need to be mathematically derived. d refers to a ref measured scattered field. J and d are derived from Richmond's Method for calculating scattering for an infinite dielectric cylinder, d represents the scattered field, and I represents the Jacobian matrix for the scattered field. F represents a measure of flatness, and is known as a flatness matrix. Equation 3:1 represents the minimization of the difference between a measured scattered field and a guessed scattered field, as represented by the first term, and penalizes large variations of the dielectric permittivity. In Equation 3.1, N represents the number of inversion cells, NÂ° represent the J number of observation locations, and N represents the number of frequencies measured f at each observation location. Each observation is defined by its frequency, resulting in multiple frequency observations at a particular location. 23 A l l the values in Equation 3.1 are real. Because time-harmonic electric fields are complex, the electric fields are separated into real and imaginary parts for the inversion, giving rise to a completely real Equation 3.1. This avoids the need for the complex conjugate operation in Equation 3.1. 3.1 Richmond's Method Richmond's Method [Richmond, 1965] is used to find the scattered field for a single frequency. Richmond's Method is based on the discretization of an integral equation and enforcing the integral equation at a fixed set of points to produce a set of linear equations, leading to a constrained linear system. 3.2 The development of the integral equation for Richmond's Method Richmond's Method constructs the integral equation by first stating the total electric field as a sum of a field due to the dielectric body, the scattered field, E , and the s incident field, E'. The dielectric body is replaced by a current distribution using the volume equivalence theorem [Harrington, 1961]. The replacement procedure is accomplished with Equation 3.2a, which represents the equivalent current of a point in the dielectric filament. The volume equivalence theorem states that a dielectric volume with electric field E gives the same radiated field as a current written in Equation 3.2a. J = jco(s - Â£ )E = jO)(Â£ Â£ Q r Q -s )E = jcos (e 0 0 dE (p) = -jcvdA = - jcop J-M\kp) s p(*,y) = il(x-x'Y+(y-y') JdS' r -\)E (3.2a) (3.3a) (3.3b) 24 Associated with each current filament is a radiated field, shown in Equation 3.3a. Integrating over the current distribution gives an integral equation for the scattered field shown in Equation 3.4. E\x,y) = -(jk 14)\\(s - 2 r l)E{x\y')Hâ„¢(kp)ax'dy To obtain Equation 3.5 the electric field is written as a sum of the incident and scattered(Equation 2.4) field. Equation 3.5 represents the total field electric field at any point in space. E{x,y) = E {x,y)-(jk 14)\\(e -\)E(x\y)H \kp)dx'dy< i 2 (2 r Next, the integral is broken up into N m square regions. Equation 3.5 can be separated into a summation of integrals over each square region. The permittivity and the electric field are assumed to be constant within each square region. The electric field in each region is denoted by E and the permittivity in each region is denoted by s . The n n electric field and the permittivity can be taken out of the integral, resulting in Equation 3.6a. E +(jk 2 m /4)f>â€ž -l]Eâ€ž H Hâ„¢(kp )dx'dy<= E with m n (3.6a) ce P = yl(x -x')+(y -y') (3.6b) 2 m m m The integral can be written in closed form i f the integral over the square region is approximated by an integral over a circular region with the same area. The closed form of the integral for the circular region is written as Equation 3.7. (/*â€¢ /4)fK>Mp',f )Wp^= I Onl^fW-lj] 0 0 25 if n - â€ž(3.7) Enforcing Equation 3.6 at the center of each region gives a constrained linear system. Substituting Equation 3.7 into Equation 3.6 gives the system of linear equations presented in Equation 3.8a. YC / E mn i =E i m n Â»=â€¢ (3.8a) C C mn =l + (en-lXj/2pcanHl mn ={jnkaâ€ž (ka )-2j] ifm=n 2) (3.8b) n I2\s -tyfa.WihpJ) i f m * (3.8c) n 3.3 The scattered field For the scattered field external to the cylinder Equation 3.9a [Richmond, 1965] is used once the electric field, E, has been computed. N M E {x,y) = j(nk 12)2 fe. - l K a J (ka {kp (x, y)) s K x n n (3.9a) n=\ ( ,y)=^( - Y (y-yJ p X X Xn + (3 .9b) 3.4 Observations for inversion There are TV observation locations and A ^ frequencies are measured at each 0 7 location. This gives TV complex observations (TV = N NÂ°). f When the scattered field, E , is separated into the real and imaginary parts, 2N real observations are produced. For storage purposes the real parts are stored at the top of the vector and imaginary parts are stored on the bottom of the vector. The observations are also grouped by frequency. Figure 3.1 shows the structure of the d prd vector. 26 s F s ReÂ£f Ef.N -l)jVÂ° +l J F s prd d ImÂ£f F s Figure 3.1: Arrangement of the multi-frequency observation vector. 1 27 Â© ^ 3 0.8 0.6 0.4 V 3â€”~"2r~-<s 0.2 0 -0.2 -0.4 3 V \ 9 -0.6 Zk -0.8 -0.8 -i_L -0.6 -0.4 -0.2 0.2 0.4 0.6 0.1 Figure 3.2: Illustration of the mapping concept. The small circles represent the center of the modeling cells and the large square regions represent the inversion cells. The lines connect the modeling region to the inversion region. 3.5 Gridding for the Jacobian calculation Before the Jacobian calculation can be derived, the concept of using different inversion grids and modeling grids is introduced. The use of two grids is necessary owing to the competing demands of inversion and modeling. Modeling requires a minimum of 10 squares per wavelength. The finer the grid spacing the smaller the error attributable to modeling when compared to the physical system. This is problematic for inversion. Numerical experiments have shown that the inversion system becomes more unstable as more degrees of freedom are added to the system. A coarse grid works best for inversion. The modeling and inversion use different grids and a mapping is created 28 between the two grids to accommodate the competingdemands of modeling and inversion. This mapping directly effects the Jacobian calculation. Let there be N' inversion cells and N modeling cells. For each inversion cell m there are M" modeling cells mapped to it. M" can be different for different values of the n superscripts. Equation 3.10 must be true. N' N m =Â£M" . (3.10) It is convenient to first introduce the concept of the indicator matrix. The indicator matrix maps the inversion cells to the modeling cells. The indicator matrix satisfies Equation 3.1 la. Where G is an N xN' m matrix. G is a vector of length n N' that makes up a row of G and Gâ€ž is a scalar element of G . The vector e' denotes k the inversion cells and the vector s denotes the modeling cells. Equation 3.1 l c is the representation for the n'th modeling cell as a function of the inversion cells written as a summation. s = Gs' (3.11a) Gj ~" (3.11b) Gâ€ž N' Â«=Y, 'b *b E e (where n=l..N ) G m (3.11c) 6=1 For this thesis the, G vector will contain only one non-zero element and that n value will be 1. The matrix element G is equal to 1 i f and only i f the n'th modeling nk 29 cell maps to the k'th inversion cell. G is sparse because most of the modeling cell do not map into the k'th inversion cell. Equations 3.8a, 3.8b, 3.8c, and 3.8d can be rewritten with the indicator notation. AT Z â€žA=Â£; C C =1+ C mn p (3.12a) 5>XÂ» " I {jl2)[nka H\ \ka )-2j] 2 = {jnka 12) b=\ ^' G n n b nb -1 n J,(ka )Hi \kp ) 2 n mn ifm=n (3.12b) ifm* (3.12c) = J{x -xJ+{y -yâ€ž) (3.i2d) 2 mn m m The permittivity variable is the same for all the modeling cells mapped to the same inversion cell. Equation 3.5 is only for a single frequency. For multiple frequencies the forward modeling needs to be repeated for each frequency. 3.6 Derivation of the Jacobian for locations internal to the dielectric body dE The Jacobian matrix, J, calculates â€”'jds' for all combinations of n and k. Where k k dE ranges from 1 to TV and n ranges from 1 to N . To find â€” \ , Equation 3.13a needs to de m k dE be solved. Solving equation 3.13a will findâ€”'j- for all n simultaneously. The procedure de k needs to be repeated once for each k. There are k sets of linear equations that need to be solved to find all k derivatives for each inversion cell. 30 Sfr*. + i X f ^ ^ â€ž dE ^ dC E ^ T - 7 =- E - - r F =0 (3.13a) n t Â«=1 7 6 * Â«=i (3.13b) n 0Â£ k dC. T = GAjl2)Vka Hl {ka )-2j) ds if 2) m m m = n,G *0 nk (3.13c) k 5C ds f - = G (jnka l2)jXka )H^{kp ) nk n n if m* n,G * 0 mn nk (3.13d) k â€”T 1 =0 otherwise (3.13e) Solving the linear system stated in 3.8a gives the solution t o Â£ â€ž , leaving dE theâ€”^ terms as unknowns in Equation 3.13a. The current system looks similar to the previous system, Equation 3.2, with the right hand side being different and a change of the unknown variables from E to dEâ€ž del Since C is the same in every case, the L U decomposition technique will speed up computation of â€” f , as the same decomposition can be used N +1 times ds ! k 3.7 Derivation of the Jacobian Matrix for the scattered field Next, the scattering equation is examined. Rewriting Equation 3.9a, using indicator notation, results in Equation 3.14. E'(x,y) = j{nk I'2)ff fxG -\\E a J {ka )H {kp {x,y)) 2 ni n n 31 x n 0 n (3.14) Assuming that there are NÂ° observation points results in a set of NÂ° x and y m m coordinates. The subscript m distinguishes between each of the observation points. E (x ,y )=E = l s m m m 12)f( X^Gâ€ž - l k â€ž / , j(nk h Â«=1 ^ (ka )H^{kp n n (x , y m m )) J 6=1 (3.15) The derivative of Equation 3.15 is taken with respect to the A:'th inversion cell giving rise to Equation 3.16. The terms on the right hand side of the equation are all dE known quantities. The term â€”f can be calculated directly from Equation 3.16. de, s ^g^=-y(*/2) (3.16) 6=1 3.8 The Jacobian for multiple frequencies dE The Jacobian matrix, J , requires the calculation of â€”jde s for every k value, and k for every frequency. Figure 3.3 shows the graphical arrangement of the Jacobian matrix. dE The top half of the Jacobian matrix contains the real part of â€”f, the bottom half of the de,. s dE Jacobian matrix contains the imaginary part of â€”f . Each half is further divided into de s k groups of frequencies. A l l the physical observations from a single frequency are stored within consecutive rows. The columns represent the index k. J mn inside J. 32 is a specific element dE[ de[ dEl <> d dF s de( dE' Re ds[ {Nf-\) Â° \ dE N + del dENfNÂ° dEN^NÂ° del Ad=JAs' dE^ ds[ dE Asi As' s x dE . s lm del dEl ds[ dE, dEl. del dE dE ds\ Figure 3.3: Structure of the multi-frequency Jacobian. 3.9 The flatness term There are two ways to handle the flatness term, the one-sided difference method and the central difference method. The flatness term is defined as the first order approximation of the derivative of the permittivity distribution along the x and y directions at a discrete set of points. In this thesis the flatness matrix uses the one-sided difference method to approximate the first order derivatives. The derivative with respect to x, and_y, occur 33 between the centers of the inversion cells. F, the flatness matrix, encodes Equations 3.17 and 3.18. Ss(x,y) _ s(x + h,y)- s(x,y) ^ 3x h de(x,y) _Â£(x,y dy + h)-e(x,y) h | Â°M (- > 0(h ) (3.18) 3 17 2 Since the grid is regularly spaced, and the derivative approximation only involves its neighbors, the flatness matrix is sparse. The central difference approximation is not used because it does not constrain the neighbors, but every other neighbor. This leads to two independent sheets of permittivity values connected at the edge of the cylinder. Examining Equation 3.19a and Equation 3.19b it is clear that e(x,y) is not in the central difference equation, and therefore not linked directly to its neighbors. 5s(x,y) = Â£(x + h,y)-e(x-h,y) 3x de(x,y) / \ + 2 2h = e(x,y + h)- (x,y-h) Â£ Dy v ; ^ / \ 2 2h V 7 ; 3.10 The N system of linear equations 1 From Equation 3.1, N 1 linear equations can be derived to find the minimum of O . If Equation 3.1 is linearized with respect to As , 1 respect to the variable AÂ£ . ! the system becomes quadratic with There is only one minimum in a quadratic system and the minimum occurs at the point where the gradient vector is zero. JV linear equations are 7 produced, by taking the derivative of Equation 3.1 with respect to every Ae' and setting k 34 every equations equal to zero. Using matrix-vector notation and a linear approximation of the term d(s' + As') , Equation 3.20 can be written. The Jacobian matrix represents the first order derivatives of the termd(s'). The foregoing are shown in the equations that follow. min \ As' I dÂ«-d{s' Ae"f j3\\F(s"+As'f + 0 mm As' N NÂ° f 7 {d -d(s')-JAs'J(d-f-d-JAs') N NÂ° p(F(s< rÂ¥ 0 = (3.1a) N + + AS')J(F{S' + As'))' jy~' f (3.20) d dAs[ dAsi 0 = (3.21) dAs'â€ž The minimization problem stated in Equation 3.20, satisfies Equation 3,21 and the solution can be written as Equation 3.22. Equation 3.23 is the equation for updating the epsilon values for the next iteration. The algorithm is shown below: 1. Start with an initial guess to the permittivity 2. Calculate As" from Equation 3.22 ew f As' = JJ * * T N NÂ° f PF'F â€” ^~ {l (d^-d) T X T + N' NN f J c pF Fs> T N' (3.22) 3. Update the permittivity with Equation 3.23. r ew = s' + (3.23) AS' 4. Repeat from 2, until the stopping condition is reached. 35 Equation 3.22 is repeated, using s new as the starting point for the linear approximation each time. The Jacobian matrix and the observations need to be recalculated given the new permittivity, s . new 3.11 Conclusion In this chapter an inversion technique is developed. The technique is based on least squares minimization. The system is minimized with respect to As' and a linear model for scattering. The technique is iterative in nature and successive iterations yield better solutions. This chapter demonstrates how to calculate the Jacobian matrix for the scattered field from Richmond's Method for dielectric modeling and how to incorporate a flatness term into the least squares minimization. The Jacobian calculation requires 2 stages. The first stage is to calculate a Jacobian for the internal field, and the second stage is to calculate the Jacobian matrix for the scattered field. The Jacobian calculation for the scattered field depends only on the internal field parameters. 36 Chapter 4: Implementation of the tomography algorithm 4.0 Introduction The detailed mapping between the code and the equations presented in Chapter 3 is shown in Chapter 4. Setup software (4.1) Tessellate cylinder T Get reference data (4.2) Calculate flafnessjT^trjx^ i ni*| (4.3) Calculate forward model Â» jl (4.4) Calculate scattered field ill : j | (4.5) Calculate Jacobian Calculate As Â«8 M Update wmmM Decrease B No â€¢ â€¢(Stop) Figure 4.1: Flow chart for the complete inversion system. The numbers in brackets represent the section each calculation is presented. Section 4.6 represents the complete non-cooled system. The flow chart for the algorithm is shown in Figure 4.1. This chapter explains how the equations in Chapter 3 are implemented in MatLab code. The code presented works with MatLab 5.3 and is upward compatible. The code is presented in the same order as in the flow chart. The code is presented in the sections that follow: 4.1) Tessellation 37 4.2) Calculating the flatness matrix 4.3) Calculating the internal field 4.4) Generation the observation matrix 4.5) The Jacobian calculation 4.6) Inversion function with a single /J value 4.7) Inversion function with multiple B values 4.1 Tessellating the cylinder Since the problem is two dimensional in nature (infinite cylinder) the tessellation of a circle is sufficient. The circle radius and grid spacing are the only two parameters needed for the automated generation of a uniformly tessellated circle. To create the discretization, a regularly spaced set of squares is superimposed onto a circle. If the center of the square lies within the circle then the square is considered part of the set of squares that make up the circle. This mapping results in two types of tessellation errors. The first error, labeled A in Figure 4.2, is the inclusion of areas that are not part of the circle. The second error, labeled B in Figure 4.2, is the exclusion of areas that are part of the circle. The circle is centered at the origin. Equation 4.1 is used as the test for membership for the set of squares that make up the circle. x +y <p 2 2 (4.1) 2 Figure 4.2 describes the foregoing concept graphically. Listing 4.1, s q u a r e _ g r i d . m, is the MatLab implementation of this mapping. The parameter C i r c l e _ r a d i u s is the radius of the desired circle, and T _ r a d is half the length of the edge of the square. 38 A <^ N / / \ / / \ \ V / \ \ / / / / ' / . y / Ce Is US;ed t o ap proxi matei circ le Figure 4.2: Illustrative diagram of the discretization concept. The cells in grey are used to approximate the circle. The centers of the grey cells all lie within the circle. Notice the staircase effect at the edges. With finer spacing this staircase can be reduced, but.never eliminated. This causes a modeling error because approximate tessellation is never a perfect circle. Listing 4.1 squaregrid.m f u n c t i o n [ G r i d _ p o i n t s ] = S Q U A R E _ G R I D ( C i r c l e _ r a d i u s , T_rad) Y=(-Circle_radius+T_rad):T_rad*2:(Circle_radius+T_rad); %X a n d Y a x i s X=Y; N = s i z e ( X , 2 ) ; % f i n d o u t how many d i v i s i o n s o n t h e a x i s G r i d = zeros(N,N); %Large square G r i d f o r LX = l : N % t e s t i f t h e p o i n t i s on t h e c i r c l e f o r LY = 1:N i f ((X(LX)^2+Y(LY) 2) < Circle_radius*2) G r i d ( L X , L Y ) = 1; end end end [I J ] = i n d 2 s u b ( s i z e ( G r i d ) , f i n d ( G r i d ) ) ; Gridjpoints = [X(I)' Y(J)' ] ; A 39 Related to the s q u a r e _ g r i d function is the n e i g h b o r s function, shown in Listing 4.2. The n e i g h b o r s function generates a list of neighbors for each cell. This function is essential for generating the flatness matrix, F_ . The n e i g h b o r s function takes in the set of squares ( S r c ) and the grid spacing (Trad) as parameters. The output is an 7Yx4 array. Af is the number of squares. Column 1 to 4 represent the neighbors. The first column represents the neighbor to the left (x- Ax), the second column represents the neighbor to the right (x+ Ax), the third column represents the neighbor on top (y+ Ay) and the forth column represents the neighbor below (y- Ay). The n e i g h b o r s function determines i f a cell is a neighboring cell by computing the distance vector to that cell. The algorithm eliminates the cells where the x or y coordinate differs from the reference cell by more than one grid spacing. This leaves 5 candidate cells, one cell for each neighbor and the reference cell. The algorithm then determines the neighbor by examining the direction of the distance vector. Listing 4. 2 Neighbor.m % t h i s f u n c t i o n determines the n e a r e s t n e i g h b o r s %single p o i n t . f u n c t i o n N e i g h L i s t = n e i g h b o r s ( S r c , Trad) to a N = size(Src,1); NeighList = zeros(N, 4); e p s i l o n = 0.01*Trad; for loop = 1 :N %This i s a c o a r s e f i l t e r t h a t e l i m i n a t e s a l o t o f t h e %calculations L i s t l = f i n d ( a b s ( S r c ( : , l ) - S r c ( l o o p , 1 ) ) <= ... (2*Trad+epsilon)); List2temp = f i n d ( a b s ( S r c ( L i s t l , 2 ) - Src(loop,2)) <= ( 2 * T r a d + e p s i l o n ) ) ; List2 = Listl(List2temp); for loop2 = LJ st2 ' L 40 ... Listing 4. 2 Neighbor.m deltax = Src(loop,1) - Src(loop2,1); deltay = Src(loop,2) - Src(loop2,2); r = sqrt(deltax^2 + deltay^2); i f ( r < (2*Trad + e p s i l o n ) ) i f (deltax > epsilon) NeighList(loop,1) = loop2; e l s e i f (deltax < -epsilon) NeighList(loop,2) = loop2; e l s e i f ( deltay > epsilon) NeighList(loop,3) = loop2; e l s e i f ( d e l t a y < -epsilon) NeighList(loop,4) = loop2; end end end end 4.2 Calculating the flatness matrix Once the grid is generated the flatness matrix can be calculated. The flatness matrix implements Equation 3.17 and Equation 3.18, the one-sided difference equations. It requires a list of neighbors generated with the previous function and the grid spacing as parameters. The neighbors list allows for quick identification of the cell to the right of the current cell, and on top of the cell. The x derivatives are encoded in the top half of the matrix and they derivatives are encoded in the bottom half of the matrix. de(x,y) _ s(x + dx h,y)-s(x,y) h o(h ) (3.17) ds(x,y) _ s(x,y + h)-Â£(x,y) + 0(h ) dy h (3.18) 2 + 2 Listing 4. 3 gradientonesided.m %This f u n c t i o n generates f u n c t i o n Generate = g r a d i e n t o n e s i d e d ( N e i g h L i s t , Trad) N =size(NeighList,1); M a t r i x = zeros(2*N, N ) ; %top N f o r x d i r e c t i o n , % bottom N f o r y d i r e c t i o n 41 Listing 4. 3 gradientonesided.nl f o r l o o p = 1:N %This i s the x loop index = loop; i f ( N e i g h L i s t ( i n d e x , 2 ) ~= 0) M a t r i x ( i n d e x , N e i g h L i s t ( i n d e x , 2 ) ) = 1; Matrix(index,index) =-1; end end f o r loop = (N+l):(2*N) % T h i s i s t h e y l o o p i n d e x = l o o p -N; i f ( N e i g h L i s t ( i n d e x , 3 ) -= 0) M a t r i x ( l o o p , N e i g h L i s t ( i n d e x , 3 ) ) = 1; Matrix(loop,index) =-1; end end Generate =Matrix /(2*Trad); 4 . 3 Calculating the internal field using Richmond's method The internal field solution is a two-step procedure. Thefirstpart is the generation of the dielectric permittivity independent portion of the matrix. The second part is the generation of the complete matrix followed by the solution for E . n Y,C E =E' mn n (3.8a) m C in Equation 3.8a can be expanded so the permittivity values are explicit in the equation, resulting in Equation 4.3, obtained from Equation 3.8a. (I + Ddiag(e - l))E = E' (4.3) D is the permittivity independent matrix and only needs to be calculated once for the algorithm. This saves time by not requiring N Bessel functions to be calculated each 2 42 algorithm iteration. This first step, i n i t _ b l o c k _ m a t r i x _ g e n . m, is implemented in listing 4.4. Listing 4. 4 i n i t b l o c k m a t r i x g e n . m ^ r e t u r n s t h e f o r w a r d m a t r i x dependence f u n c t i o n s u c c e s s = i n i t _ b l o c k _ m a t r i x g e n ( L i s t ' C, ... k , T _ r a d , FName) N = s i z e ( L i s t C,1) ; D i a g _ i n d = 1:N+1:N 2; F_mat = zeros(N,N),â€¢ L u m p e d _ C o n s t a n t = j * p i * k * T _ r a d * 0 . 5 . * b e s s e l j (1, k* T _ r a d ) ; f o r l o o p = 1:N p = sqrt((List_C(:,1) - List C(loop,1)). 2 + . . . (List_C(:,2) - L i s t _ C ( l o o p , 2 ) ) . 2) ; F _ m a t ( l o o p , : ) = ... (Lumped_Constant.*besselh(0,2,k.*p)) .' end F_mat ( D i a g _ i n d ) = ( j / 2 ) * ( p i * k * T _ r a d * . . . besselh(l,2,(k*T_rad))-2j); A A A ; s a v e (FName, ' F__mat' ) ; s u c c e s s = 1; The second step calculates the matrix (I + Ddiag(e -1)). This calculation is presented in listing 4.5, b l o c k _ m a t r i x _ g e n . m. After C has been generated, the internal fields can be found. Listing 4.6, s a m p l e l . m, demonstrates how to calculate the internal fields. Listing 4.6 is clearly separated into 3 sections, setup, matrix generation and solving of the internal fields. 43 Listing 4. 5 b l o c k m a t r i x g e n . m ^ r e t u r n s t h e f o r w a r d m a t r i x dependence f u n c t i o n [F_mat] = b l o c k _ m a t r i x _ g e n ( e p s i l o n , FName) load(FName) % l o a d p a r a m e t e r s s t o r e d i n t h e %init_block_matrix_gen function N = size(F_mat,1); f o r l o o p = 1:N F _ m a t ( l o o p , :) = F _ m a t ( l o o p , : ) . * ( e p s i l o n -1) ; end 1 F m a t = F_mat + e y e ( N ) ; %add t h e i d e n t i t y matrix Listing 4.6 sarnplel.niat %sample s c r i p t f o r c a l c u l a t i n g t h e i n t e r n a l f i e l d s %Setup C _ r a d = 1; %cylinder radius T _ r a d = 1/21; %tessellation radius k = 2*pi; %wave number Fname = 'temp'; % D e f i n e f i l e name f o r s t o r i n g s t u f f Grid = square_grid(C_rad, T_rad); ^generate t h e G r i d N = size(Grid, 1); epsilon = 2*ones(N,l); %define p e r m i t t i v i t y d i s t r i b u t i o n E i = PlaneWave(Grid,k); %define the incident f i e l d i n i t _ b l o c k _ m a t r i x _ g e n ( G r i d , k , T _ r a d , Fname); % c a l c u l a t e t h e e p s i l o n independent p a r t o f Cmatrix % g e n e r a t i n g t h e m a t r i x a n d LU d e c o m p o s i n g C_Mat=block_matrix_gen(epsilon, Fname); [L,U] = l u (CJYIat) ; %solving for the internal temp = L \ E i ; E = U\temp; fields. 44 4.4 Generation of the observation matrix The procedure for generating the scattered field is split into step 1, a permittivity independent step, and step 2, a permittivity dependent step. To calculate the scattered field from the internal fields, Equation 3.9a is used. Â£ (x ,y ) s m m = Ank12)X{s n -\)E a J,{ka )H?(kp {x ,y )) H m n H m m (3.9a) Â«=i The solution for the scattered field can be written in the form of Equation 4.4, when B is calculated first, and the actual scattered field is calculated second. E' =Bdiag(e-\)E (4.4) n Listings 4.7, I n i t _ B l o c k _ S c _ f i e l d . m, and Listings 4.8, I n i t _ B l o c k _ S c _ f i e l d . m, implement the two step procedure. The function I n i t _ B l o c k _ S c _ F i e l d , which implements step 1, takes in the g r i d ( L i s t _ S ) , a list of observations points, the wave number(k), the grid spacing(T_r ad), and a filename(FName) as arguments. The filename, FName, is used to store the results temporarily. The B l o c k _ S c _ F i e l d function has the permittivity distribution(epsilon), the internal fields(E) and the filename(FName) as input arguments. B l o c k _ S c function loads the temporary results stored by Init_Block_Sc_Field. Listing 4. 7 I n i t B l o c k S c F i e l d function success = I n i t _ B l o c k _ S c _ F i e l d ( L i s t _ S , L i s t _ 0 , T _ r a d , FName); NO = s i z e ( L i s t _ 0 , 1 ) ; NE = s i z e ( L i s t _ S , 1 ) ; ObsMat = z e r o s ( N O , N E ) ; 45 k, Lumped_Constant = - j * p i * k / 2 * b e s s e l j ( 1 , k * T _ r a d ) * T _ r a d ; f o r l o o p = 1:NO r = sqrt((List_S(:,1) - List_0(loop,1)). 2 +... (List_S(:,2) - L i s t _ 0 ( l o o p , 2 ) ) . 2 ) â€¢ ; ObsMat(loop,:) = Lumped_Constant*besselh(0,2,k*r); end save(FName, ObsMat'); success =1; A A 1 Listing 4. 8 B l o c k s c a t t e r e d f i e l d . m % this function returns the scattered f i e l d at a given % point f u n c t i o n [Es] = B l o c k _ S c a t t e r e d _ f e i l d ( e p s i l o n , E,FName) load(FName); % l o a d s t o r e d c a l c u l a t i o n s Es = O b s M a t * ( ( e p s i l o n - 1 ) .*E) ; 4.5 The Jacobian Calculation The first task is the creation of a mapping between the modeling grid and the inversion grid. This mapping is referred to the G in Equation 3.11a and presented in the output L i s t . The columns of the matrix G are compressed in L i s t . The columns are stored as cell arrays, where the indeces of the non-zero elements of G form the array. The N e t L i s t function maps the modeling cell to the closest inversion cell. It does this in two stages: i) It determines i f the center of the modeling cell is within an inversion cell. This is done with the w i t h i n subfunction, which checks i f a modeling grid cell is within the interval of the inversion cell. The second part maps the cells that haven't been mapped to an inversion cell with w i t h i n . This step finds the closest inversion cell to the given modeling grid cell. Listing 4. 9 NetList.m % T h i s i s a mapping f u n c t i o n f o r a square f u n c t i o n L i s t = N e t L i s t ( C o r s e G r i d , CRad, F G r i d , NC = s i z e ( C o r s e G r i d , 1 ) ; 46 FRad) Listing 4. 9 NetList.m NF = s i z e ( F G r i d , 1 ) ; used = o n e s ( l , N F ) ; List = cell(1,NC); %generate the mapping f o r loopC = l-.NC temp = [] ; f o r loopF = 1:NF if(Within(CorseGrid(loopC,1),CorseGrid(loopC,2) FGrid(loopF,1),FGrid(loopF,2),CRad)) i f (used(loopF) == 1) temp = [temp l o o p F ] ; used(loopF) =0; ^prevents d u p l i c a t e s . end end end L i s t { l o o p C } = temp; end %look f o r any p o i n t s i n the f i n e g r i d t h a t % hasn't been assigned, f o r loopF = 1:NF if (used(loopF) ==1) % f i n d the nearest nieghbor loopC =1; rMax = (CorseGrid(loopC,1) - F G r i d ( l o o p F , 1 ) ) 2 (CorseGrid(loopC,2) - F G r i d ( l o o p F , 2 ) ) 2 ; C l o s e s t = loopC; f o r loopC = 1:NC r 2 = (CorseGrid(loopC,1) - F G r i d ( l o o p F , 1 ) ) 2 +(CorseGrid(loopC,2) - F G r i d ( l o o p F , 2 ) ) 2 ; i f ( r 2 < rMax) C l o s e s t = loopC; rMax = r 2 ; end end List{Closest} = [[List{Closest}] loopF]; A A A A end end %helper f u n c t i o n f u n c t i o n r e s u l t = Within(XI,Yl,X2,Y2,rad) i f ((X2 > (XI - rad)) & (X2 <= (XI + rad)) & (Y2 > (Yl - rad)) & (Y2 <= (Yl + r a d ) ) ) r e s u l t = 1; 47 ... Listing 4. 9 NetList.m else r e s u l t = 0; end The next task, in the Jacobian calculation, is the determination of the derivative of the internal fields as computed by Equation 3.13a. BlockJacNL, in Listing 4.10, has the L U decomposition of C . Since the problem involves many right hand sides for the same matrix, the L U decomposition ,for a given C , can be reused. Listing 4. 10 B I o c k J a c N L . M % T h i s f i l e i s used f o r t h e c a l c u l a t i o n o f t h e J a c o b i a n f o r %a mapped SRC %list. The r e t u r n type w i l l be a N x e p s i l o n m a t r i x . Were %each column r e p r e s e n t ^Parameters %SrcF - l o c a t i o n o f t h e t e s s e l a t i o n p o i n t s %EF - f i e l d s at the t e s s e l a t i o n p o i n t s %LF - lower m a t r i x o f t h e lu(Mat) were Mat r e p r e s e n t s t h e %forward problem %UF - upper m a t r i x o f t h e lu(Mat) were Mat r e p r e s e n t t h e %forward problem % e p s i l o n - the e p s i l o n value of the coarse g r i d . Should be % s t o r e d as a column v e c t o r %NetList %k - wave number 2*pi/larnbda %Crad - corrected radius s q r t ( 4 / p i ) * t e s s e l a t i o n radius function Jac = blockJacNL(SrcF, N e t l i s t , k, Crad,FName); % s t e p a l l o c a t e space NE = s i z e ( e p s i l o n , 1 ) ; NF = s i z e ( S r c F , 1 ) ; Jac = zeros(NF,NE); Map = z e r o s ( N F , 1 ) ; 48 EF, LF,UF, epsilon,... Listing 4 . 1 0 BlockJacNL.M load(FName); f o r l o o p = 1:NE A = Netlist{loop}; Map(A) = l o o p ; end f o r l o o p E = l-.NE rhs = zeros(NF,1); f o r l o o p F e q n = 1:NF f o r l o o p F r h s = 1:NF i f ( M a p ( l o o p F r h s ) == l o o p E ) rhs(loopFeqn) = rhs(loopFeqn) . +F_mat(loopFeqn,loopFrhs)*EF(loopFrhs); end end end temp = - L F \ r h s ; J a c ( : , l o o p E ) = UF\temp; end The last task is the calculation of the Jacobian matrix for the scattered field in Equation 3.16. Equation 3.16 is a simple summation of terms. HG E a J (ka )Hi \kpâ€ž) 2 kn ds' N ( m k Z n n l n + \ N l 2 > X -1 ^a jXkaM\kp {x ,y )) n ) k 0Â£ n m m ) (3.16) The B l o c k a s s e m b l e J a c o b i a n function produces the complex Jacobian matrix. Separating the matrix into real and imaginary parts will be done explicitly in the inversion script. Listing 4 . 1 1 BlockassembleJacobian .m %assemble complex j a c o b i a n f u n c t i o n CJac = B l o c k A s s e m b l e J a c o b i a n ( E J a c , En, e p s i l o n , N e t L i s t , S r c , O b s , k, Crad,FName) NO = s i z e ( O b s , 1 ) ; NE = s i z e ( e p s i l o n , 1 ) ; 49 Listing 4.11 BlockassembleJacobian .m NF = s i z e ( S r c , 1 ) ; CJac = zeros(NO,NE); Map = z e r o s ( N F , 1 ) ; LC = ( j * p i * k / 2 ) * C r a d * b e s s e l j ( l , k * C r a d ) ; load(FName) f o r l o o p l = 1:NE temp = N e t L i s t { l o o p l } ; Map(temp) = l o o p l ; end f o r l o o p E = 1:NE C J a c ( : , l o o p E ) = ObsMat* ,( ( e p s i l o n (Map)-.. . 1).*EJac(:,loopE)); f o r l o o p O = 1:N0 temp = N e t L i s t { l o o p E } ; f o r l o o p F 2 = temp r = sqrt((Src(loopF2,1) -Obs(loopO,1)). 2 +(Src(loopF2,2) -Obs(loopO,2)).^2); CJac(loopO,loopE) = CJac(loopO,loopE) - . LC*En(loopF2)*besselh(0,2,k*r); end end end c l e a r ObsMat; A 50 4.6 Inversion function with a single beta value A l l the steps, as shown in Figure 4.3, are now in place. A l l the elements of the inversion scheme can be placed in a function to simplify the inversion procedure. Listing 4.12 is the function. The function b a s i c l n v e r s i o n essentially runs the inversion algorithm for any single beta value and for a fixed number of iterations that is specified by the user. The loop seen in Figure 4.3 is implemented as a for loop. Cascading the B is done outside this function. Figure 4.3 outlines the algorithm performed in Listing 4.12. Setup software Calculate forward mbde| Calculate scattered field y ; ;i ' ~~~ Calculate jacobian , ,T. t Calculate As Update Â£ Figure 4.3: Flow chart for the B a s i c l n v e r s i o n function. The setup portion of the software includes the encoding of all the parameters that must be chosen. The function loops through the Jacobian calculation and updates the permittivities. The calculation of As 1 is done in Listing 4.12. It is near the bottom and implements Equation 3.22. 51 ccJ (d -d) T As = 1 N NÂ° f + N' ref N NÂ° f J pF Fs' T N' (3.22) Listing 4.12 B a s i c l n v e r s i o n . m %This i san attempt t o a b s t r a c t t h e i n v e r s i o n f u n c t i o n t o %make i t e a s i e r t o r u n b a t c h e s %as w e l l a n a l y z e p e r f o r m a n c e f u n c t i o n [ e p s i l o n C , M i s f i t ] = B a s i c l n v e r s i o n ( R e f _ O b s , ... %This i st h e reference data FileNames, ...%Filename f o r block m a t r i x % t h a t has been p r e - c a l c u l a t e d TempDirectory,... %where t o s t o r e t e m p o r a r y f i l e s CylinderRad,...%Where t o store parameters o f t h e %cylinders Corse_rad,... %The s i z e o f t h e i n v e r s i o n t e s s e l l a t i o n Fine_rad,... %The s i z e o f t h e m o d e l i n g t e s s e l l a t i o n Corse_grid, Fine_grid,. I E t a b l e , .. K a r r a y , ... % a n A r r a y o f wave numbers E p s i l o n C _ i n i t i a l , % s t a r t i n g model t o be d e t e r m i n e %separately O b s _ p t s , ... %Observation P t s N i t e r , . . . INumber o f i t e r a t i o n s picturename,... alpha, beta,FDMatrix) % Part 1 Figure out the size of matrixes and v e c t o r s NK = s i z e ( K a r r a y , 1 ) ; %number o f f r e q u e n c i e s NO = s i z e ( O b s _ p t s , 1 ) ; %number o f o b s e r v a t i o n s p o i n t s NEF = s i z e ( F i n e _ g r i d , 1 ) ; % n u m b e r o f model c e l l s NEC = s i z e ( C o r s e _ g r i d , 1 ) ; %number o f i n v e r s i o n c e l l s CFine_rad = s q r t ( 4 / p i ) * F i n e _ r a d ; %corrected radius f o r %Richmond's method epsilon = z e r o s ( N E F , 1 ) ; % L i n k i n v e r s i o n a n d model c e l l s epsilonC = EpsilonC_initial; % P a r t 1.2 g e n e r a t e f i l e n a m e s % purposes and mappings f o r s t o r a g e % P a r t 1.1 g e n e r a t e some f i l e n a m e s TempFile = c e l l ( N K , l ) ; TempFile2 = c e l l ( N K , 1 ) ; 52 f o r temp d i r e c t o r i e s Listing 4.12 B a s i c l n v e r s i o n . m f o r l o o p K = 1:NK TempFile{loopK} = s p r i n t f ( % s % i ' , T e m p D i r e c t o r y , l o o p K ) ; end f o r l o o p l = 1-.Niter TempFile2{loopl} =sprintf( %sa%ib',picturename,loopl); end % P a r t 1.2 Map t h e p e r m i t t i v i t y f r o m i n v e r s i o n t o m o d e l i n g , f o r l o o p = 1:NEC epsilon(IEtable{loop}) = epsilonC(loop); end 1 1 %Part 2 a l l o c a t e space Misfit = zeros(Niter,1); IObs = z e r o s ( N O * N K , 1 ) ; ObsJacMF = z e r o s ( N O * N K , N E C ) ; % Part 3 setup t h e i t e r a t i v e a l g o r i t h m for iter = l:NIter %3.1 c a l c u l a t e t h e i n t e r n a l f i e l d s f o r l o o p K = 1:NK Mat = b l o c k _ m a t r i x _ g e n ( e p s i l o n , FileNames{loopK,1}); [L,U] = l u ( M a t ) ; E i = PlaneWave(Fine_grid, Karray(loopK)); TempE = L \ E i ; E = U\TempE; ES = .. . Block_Scattered_field(epsilon,E,FileNames{loopK,2}); save(TempFile{loopK},'L','U','E','ES'); i n d e x l = ( l o o p K -1)*N0+1; i n d e x 2 = NO*loopK; I O b s ( i n d e x l : i n d e x 2 ) =ES; end % P a r t 3.2 c a l c u l a t e t h e J a c o b i a n f o r l o o p K = 1:NK load(TempFile{loopK}); i n d e x l = ( l o o p K -1)*N0+1; i n d e x 2 = NO*loopK; % P a r t 3.1.1 J a c o b i a n s t u f f I n t J a c = B l o c k J a c N L ( F i n e _ g r i d , E, L,U, e p s i l o n C , . . . I E t a b l e , K a r r a y ( l o o p K ) , CFine_rad," FileNames{loopK,1}) ; ObsJac = B l o c k A s s e m b l e J a c o b i a n ( I n t J a c , E , epsilonC,... I E t a b l e , F i n e _ g r i d , Obs_pts, K a r r a y (loopK) . . 53 Listing 4.12 B a s i c l n v e r s i o n . m CFine_rad, FileNames{loopK,2}); ObsJacMF(indexl:index2,:) = ObsJac; end %3 .3 now t o s e p a r a t e i n t o r e a l a n d i m a g i n a r y p a r t s delta_obs = Ref_0bs-10bs; M i s f i t ( i t e r ) = sum(abs(delta_obs). 2)/(NO*NK); A % P a r t 3.4 s e p a r a t e J a c o b i a n i n t o r e a l a n d %imaginary p a r t s . RMObs = z e r o s ( 2 * N 0 * N K , 1 ) ; RMJac = z e r o s ( 2 * N 0 * N K , N E C ) ; RMObs(1:(N0*NK),:) = r e a l ( d e l t a _ o b s ) ; RMObs((N0*NK+1):(2*N0*NK),:) = i m a g ( d e l t a _ o b s ) ; RMJac(1:(NO*NK),:) = r e a l ( O b s J a c M F ) ; RMJac((NO*NK + 1 ) : ( 2 * N 0 * N K ) , : ) = i m a g ( O b s J a c M F ) ; %3.5 D e l t a e p s i l o n c a l c u l a t e d h e r e . delta_epsilon = (alpha*RMJac'*RMJac/(NO*NK)+beta*FDmatrix'*FDmatrix/NEC)\... (alpha*RMJac'*RMObs/(NO*NK)-... (beta*FDmatrix'*FDmatrix*epsilonC)/NEC); %3.6 p e r m i t t i v i t y u p d a t e d h e r e . epsilonC = delta_epsilon+epsilonC; f o r l o o p = 1:NEC epsilon(IEtable{loop)) = epsilonC(loop); end save(TempFile2{iter}, epsilonC') 1 end 4.7 Inversion function with multiple beta values Listing 4.13 performs the algorithm shown in Figure 4.1. It uses the B a s i c l n v e r s i o n function for the greyed out box in Figure 4.1. Listing 4.13 complete script c e l l N = 'cascade3'; %load the reference observations searchstring = sprintf('c:\\model\\fourcellobs2.mat') if (-exist(searchstring)) load4_parameters2; end load(searchstring) %generate G r i d s 54 Listing 4.13 complete script r a d i u s =1; I r a d = 1/9; Mrad=l/41 ; Igrid = square_grid(radius, Irad); Mgrid = s q u a r e _ g r i d ( r a d i u s , Mrad); Correct_rad = sqrt(4/pi)*Mrad; ETable = N e t L i s t ( I g r i d , I r a d , Mgrid, NF= s i z e ( M g r i d , 1 ) ; NC= size(Igrid,1); Mrad); %setup matrixes % g e n e r a t e some f i l e n a m e s filename = c e l l ( N K , 2 ) ; for loopK = 1:NK filename{loopK,1} =... s p r i n t f ( ' c:\\model\\FWMAT%02i',loopK) ; filename{loopK,2} =... sprintf('c:\\model\\OBMAT%02i',loopK); end % I n i t i a l i z e function for calculating scattered %and i n t e r n a l f i e l d s for loopK = 1:NK Init_Block_matrix_gen(Mgrid, Karray(loopK),... Correct_rad,filename{loopK,1}); I n i t _ B l o c k _ S c _ f i e l d ( M g r i d , ObsPts, . . . Karray(loopK), Correct_rad, filename{loopK,2}); end % D e c l a r e b e t a v a l u e s t o use BV = [ 1 0 * ( 8 / 9 ) . [0:60] 0 0 0 ] ; NB = s i z e ( B V , 2 ) ; e p s i l o n S t a r t = 2.5*ones(NC,1); %Generate F l a t n e s s m a t r i x NeiList = Neighbors(Igrid,Irad); FDmatrix = g r a d i e n t o n e s i d e d ( N e i L i s t , N i t e r =1; a l p h a = 1; A for Irad); loopB =1:NB beta = BV(loopB); e p s i l o n S t o r e = ... sprintf('C:\\%sOS\\epsilon%05i_ ,cellN,loopB); MisfitStore = ... sprintf( C:\\%sOS\\Misfit%05i',cellN,loopB); 1 1 55 Listing 4.13 complete script -sperform t h e i n v e r s i o n f o r a s i n g l e b e t a [epsilonC, M i s f i t ] . . . =InversionWithFlattessModel(Ref Obs,...% r e f e r e n c e d a t a f i l e n a m e , ... % F i l e n a m e s f o r m a t r i x t h a t h a s %been p r e - c a l c u l a t e d 'c:\\temo',.. .%Where t o s t o r e t e m p o r a r y f i l e s radius,... %Where t o s t o r e p a r a m e t e r s o f t h e cylinders Irad,... %The s i z e o f t h e c o a r s e t e s s e l a t i o n Mrad,... %The s i z e o f t h e f i n e t e s s e l a t i o n Igrid,... Mgrid,... ETable, . . . K a r r a y , ... %An A r r a y o f wave numbers e p s i l o n S t a r t , . . . % S t a r t i n g model t o be %determine s e p a r a t e l y ObsPts, . . . %Observation P t s Niter,... e p s i l o n S t o r e , ...%Number o f i n t e r a c t i o n s alpha, beta, FDmatrix); epsilonStart = epsilonC; %cascading save(MisfitStore,'Misfit'); %store the m i s f i t function %for analysis end 4.8 Summary In this chapter the implementation of the inversion algorithm is presented. The implementation is separated into several functions. The separation of the program into several functions allows for easy debugging and testing of the algorithm. The program has not been optimized for speed or memory, but attempts to reuse calculations where possible. 56 Chapter 5: Numerical experiments using the tomography algorithm 5.0 Introduction In this chapter an investigation of the functional minimization defined in Equation 3.1 is explored. The parameter, B, in this equation is varied in magnitude, as is the number of iterations. B represents the relative weighting between the data misfit term and the flatness in the predicted model. The investigation is separated into experiments. The experiments are organized into 4 sets, each exploring a different aspect of the inversion algorithm. The first three sets of experiments share common parameters, as presented in Section 5.1. The first two sets of experiments will share 3 common test cases. The first set of experiments keeps B constant, as a function of iteration. The second set of experiments decreases B as a function of iteration. Decreasing /3 is analogous to cooling in simulated annealing. The third set of experiments introduces noise to the most complex test cases of the second set of experiments. The fourth set of experiments explores the issue of moving to a case where there are more inversion cells than observations. This is known as the under-determined case. Table 5.1: Summary of experiments for chapter 5 Experimental Permittivity Number of set distributions experiments 1 Figures 5.4, 5.5, 21 5.6 Figures 5.4, 5.5, 5.6 Figure 5.6 Figure 5.22 Description P is fixed in these experiments. P is decreasing in these experiments Noise is added to the signal P is decreasing in these experiments, and a finer tessellation is used. Same as above, but with 2 blobs. Figure 57 5.1 Setup for the experimental procedure For the experiments in Chapter 5, the d ref vectors are numerically generated, using Richmond's Method. The permittivity distributions for the numerically generated scattered fields are chosen such that the permittivity distribution can be described exactly by the inversion tessellations. That is the tessellation is a region consisting only of a collection of squares, approximating a circle. This eliminates any noise that arises from errors caused by the inability of the tessellation cells to model the permittivity distribution exactly. For all experiments, 6 frequencies are used; a circular cylinder with a radius of IX forms the outer boundary of the object. Table 5.2 summarizes the properties in experimental sets 1, 2 and 3. The properties for experimental sets 4 and 5 are presented in Section 5.7 and Section 5.8. Note that all these experiments do not represent far-field scattering. Table 5.2: Parameters for the experimental sets 1, 2 and 3 Parameter Cylinder radius k values Value 1 X 0.80*2TT 0.88*2TT 0.96*2TT 1.04*2TT 1.12*2TT 1.20*2TT 1/9 X 1/41 X Inversion cell tessellation radius Modeling cell tessellation radius Incident wave Jkx e Observation locations -90 to 90 degrees with 6 degrees of separation. p=\.5 X 58 The relevant geometry is shown in Figure 5.1, which represents the cells corresponding to possible permittivity distributions. The permittivity value is assumed to be constant within each region. Each square region represents an inversion cell, with length 2/9A. The regions are generated with the s q u a r e _ g r i d function described in Chapter 4. C e l l s u s e d to approximate cylinder for inversion 1 r | 0.8 â€¢ 0.6 1 . 1 1 1 : , : : 0.4 - - 0.2 CO * n- >i -0.2 -0.4 -0.6 'â€¢ -0.8 â€¢ _1 I -1 ' ' Li -0.5 1 I i I 0 x axis I i_l i 0.5 1 Figure 5.1: Inversion cells for experimental sets 1, 2 and 3. Figure 5.2 represents the same region as Figure 5.1. The cells in Figure 5.2 are used for Richmond's Method for forward modeling. The permittivity and electric field are assumed to be constant in each region. Each square region represents a modeling cell, with length 2/4IX. The regions are generated with the s q u a r e _ g r i d function as described in Chapter 4. 59 Cells used to approximate cylinder for modeling 0.81- I 1 1I I 1 I I | | | 1 1 I I I 1 1 I | I I | | I I 0.4 - FE:EE:EEEEEEEEEE:EE:zE:zzEEzEEzzEzzzEL 0.2 :Ez:zEzzzzzz:zzzzzzzzzzEzzzzzz:zz:zE::z:z x 05 n r U >^ ZZZZZZZZZZZZZZZZZZIZZZIZZZZZZZZIZIIZIIZZZ -0.2 :zzz:zz:zz:zz:z::zzzzz:zzzzzzzz:zzzzz^ -0.4 â€¢ z z z z z z z z z z z z z z z z z z z z z ^ -O.B - -0.8 _i 'izCZZZzEzzEzZzEzzEzZIZZLT-' i i -1 -0.5 II 111 ii 11 II 0 i 0.5 i 1 x axis Figure 5.2: Modeling cells for experimental sets 1, 2 and 3. Figure 5.3 illustrates the superposition of the inversion regions and modeling regions. The figure represents the mapping concept presented in Section 4.1. The square regions represent the inversion cells and the x's represent the centers of the modeling cells. The x's within a given square all share the same permittivity value. 1 0.8 0.6 0.4 X X > X X X X X X X X X X >X X X X 1 XX X X X X Â« yX yX y.) ; X X X X X X X x x x x> X X X X X X X X X X X X >X X X X J X X X X X X X X >X X X X v X 03 0 -0.2 -0.4 -0.6 -0.8 -1 -1 X X x X X X x X X X x X X > ; X X X XXX X ; X X X X i X. X X X X X '. X X X X < X X X X X X X X :x x x x X X < X X X X x x x :x ; x x x x x x x < X X X X X X X X ;x x x x X X X X < X X X XX X X X i X X X X XXX X X > X. X X X X X X > X X X X X % X X" X X X X X < : x x x x"X X X" X ix X > X X X X X X X X > X X X X X X X X < X X x â€¢/â€¢X X X X : x X X >X X X X X X X X > X X X X X X X X iX xxx X X X X : x x '. X X X X X X > X X X X X X X X >- X X X X < X X X X X X X X ; x x x x X X X X , :x x ' X X ^ X V â€”xX y. x : â€¢ â€¢-; y v. y X x > X X X X X X X X >X X X X < X X X X XXX X < X X X X x x x x ;: x x x X X x > X X X X ".XXX/ X X X X < X X X XX X X X X X X X > X X X X X X X X ; X X X X < X X X X X X X X < X X X X x x x x ;I X X X ( X x x x X X X X ! I X X. X X X X X X >X X X X X X X X X X X X X < X X X X X X X X < X X X X X X X X 3: x x x x -\ A A A A X X X X < X X X A. X X X. X I X X X X X X X X J . X X X X x x x x; X X X X X X X X X X X X X < X X X X X X X X < X X X Xx x x x : : x x x x X X X x> X X X X X X X X X X X X X < X X X X X X X X ; x x x x x x x x:: x x x x X X X X > X X X X X X X X > X X X X < X X X XX X X X ; x x x x x x x x :: x x x x X X X X 5 X X X X X X X XV X X X X < X X X X X X X X C X X X X X X X X ' ; x y \- x x x x x; X X X X X X X X > X X X X < X X X XX X X X C X X X X x x x x ;i x x x x X X X x > X X X X X X X X >â€¢ X X X X X X X X X XXX X ; x x x x x x x x:: x x x x X X X > X X X X X X X X >X X X X X X X X X X X X X C X X X X x x x x :; x x x X X X >X X X X X X X X > X X X X X X X X X X X X X <x x x x x x x x : ; x x x A A' 'A 'A X X > X X X X X X X X X X X X X X A" !X"W-X W X' 'A 'A A' X' !X X X X X X XXX X < X X X Xx x x x; X X x x: X X X X X X X x y X X X X X X X X X XXX X <x x x x x x x x : X X X J X X X X X X X x> X X X X X X X X X XXX X < X X X XX X X X I X x > X X X X X X X X > X XXX < X X X X XXX X t x x x x x x x x: X X X X X X X X X > X X X X Â« x x x X X X X <x x x x x x x x : X X X X X X X X > X X X X < X X X X X X X X i X X X X X X X X X X X X X X X J> X X X X <xxxx X X X X < X X X X x x x X X X X X X s< X X X X < X X X X X X X X ; x x x x X X <xxxx v 0.2 X X < < v X X X X > X X X X < xx> X X X X < > X X X X < X X < 1 -0.5 X X X X X X X X X X X X 0 XX XX XX XX XX X ; x x x x XX X X X X X X X 0.5 * 1 x axis Figure 5 . 3 : Superposition of modeling regions and inversion regions 5.2 Test cases 1,2 and 3 Three test cases are used for experimental sets 1 and 2. The proprieties of the test case are summarized in Table 5.1. The first test case is shown in Figure 5.4. It has 1 cell with a permittivity of 1, and 68 cells with a permittivity of 2.5. The distribution is asymmetric. The test case will be used in experimental sets 1, 2, and 3. 61 -0.6 â€¢0.B 0.5 Figure 5.4: Test case 1, background has the permittivity of 2.5 and perturbation has a permittivity of 1. The second test case is shown in Figure 5.5. It has 4 cells with a permittivity of 1, and 65 cells with a permittivity of 2.5. The distribution is asymmetric. The test case will be used in experimental sets 1, 2, and 3. 62 "-1 -0.5 0 0.5 1 Figure 5.5: Test case 2, background has the permittivity of 2.5 and perturbation has a permittivity of 1. Test case 3 is shown in Figure 5.6. It has 9 cells with a permittivity of 1, and 60 cells with a permittivity of 2.5. The distribution is symmetric. The distribution is used i experimental sets 1, 2, 3 and 4. 63 -1 -0.5 0 0.5 1 Figure 5 . 6 : Test case 3, background has the permittivity of 2.5 and perturbation has a permittivity of 1. 5.3 Norms for assessing the quality of the solution Two norms can be defined to help assess the quality of the solution. Because the measured scattered field is simulated, the exact permittivity distribution corresponding to the scattered field is known. B y knowing the permittivity distribution, Equation 5.1 can be defined. Equation 5.1 is a measure of the difference between the recovered permittivity distribution and the exact permittivity distribution. Ideally the value of <t> is zero at the 2 end of the algorithm. This term is called the modeling error. 64 The second norm is a measure of the difference between the measured scattered field and the predicted scattered field. This is known as the variation and is shown in Equation 5.2. d ref -d 2 5.4 Experimental set 1 For the experiments in experimental set 1, /? is held constant as a function of iteration and the algorithm runs for 9 iterations. The parameters in Table 5.2 are used, the modeling regions are descretized according to Figure 5.2, and the inversion cells are descretized according to Figure 5.1. Seven values of B are used for the three test cases described in Section 5.2 for a total of 21 experiments. The values of used are 100, 10, 1, 0.1, 0.01, 0.001 and 0. For all the cases a flat starting model of permittivity of 2.5 is assumed. 65 Variation Plot Figure 5.7: Variation plot after 9 iterations as a function /? for experimental set 1, test cases 1, 2 and 3 . The graph in Figure 5.7 is the plot of the variation for the experiments in experimental set 1 after the ninth iteration. The line connects experiments that share the same test case. The significant features of the graph include the decreasing variation with decreasing /?, and the sudden increase in the variation value when f3 is equal to zero. 66 0^ as a function of (3 0.001 Figure 5.8: Modeling error after 9 iterations as a function /? for experimental set 1, test cases 1, 2 and 3. Figure 5.8 is a plot of the modeling error at the ninth iteration of each experiment. The lines connect experiments that share the same test case. Note the fact that the modeling error decreases as /? decreases, and then suddenly increases when J3 is set to zero. Examination of test case 3 indicates that the variation is not a good measure of divergence. The variation at (3 = 0, is large but finite. The magnitude is of the same order as the value of the variation at /? = 100 . The modeling error at B = 0 is very large. Cleary, the solution has diverged, yet the variation value remains finite. When (3 = 0 the inverse problem is ill-posed. Without regularization the inversion algorithm is expected to diverge when the initial model is significantly different from the true model. This 67 implies that the inclusion of the flatness term in the minimization helps find a stable solution to test case 3. For test case 2, the values of the variation and modeling error are studied as a function of iteration for ft = 0 and fi = 0.001. This case is examined closely because of the sudden increase in modeling error. It is not clear from looking at Figure 5.7 and 5.8, whether test case 2 is converging at fi - 0. Figure 5.9: Recovered permittivity distribution for experimental set 1, test case 2 and fi = 0. Figure 5.9 shows the permittivity distribution recovered in test case 2 at the ninth iteration. The surface is bumpy and the peak permittivity value is about 5. This is quite different than that of the actual permittivity distribution. 68 Figure 5.10: Recovered permittivity distribution for experimental set 1, test case 2 and (3 = 0.001. Figure 5.10 is the recovered permittivity distribution for (3 = 0.001 at the ninth iteration. The scaling of the graph is different than that of Figure 5.9 to accentuate the features of each graph. Figure 5.10 looks much more similar to Figure 5.6, than Figure 5.9. This impli( that the solution produced with a little regularization is better than the solution with no regularization for test case 2. Figure 5.11 examines the behavior of the modeling as a function of iteration for the case of ft = 0 and f3 = 0.001 for test case 2. 69 Q , . V s . iteration Iteration Figure 5.11: Variation as a function of iteration for experimental set /? = 0.001 1, test case 2 , fi â€” 0 and For test case 2, the fi = 0 line does converge, however the fi = 0.001 line converges much more rapidly in Figure 5.11 and the final variation value is lower than that of the fi = 0 line. This further implies that, when fi = 0, a local minimum has been reached. The regularization helps avoid the local minimum because the local minimum has significantly more structure than that of the global minimum. The behavior of the variation suggests that slowly decreasing fi leads to a better solution for test case 2 and test case 3 compared to when fi - 0 . 70 5.5 Experimental set 2 For the second set of experiments (3 decreases as a function of iteration. For each of the three test cases, fi is decreased in 2 ways. For the first method, fi is decreased after every iteration. For the second method, B is decreased after every third iteration. There are a total of six experiments. The values of B used in both methods are 100, 10, 1, 0.1, 0.01, 0.001 and 0. The parameters in Table 5.2 are used for both methods. A flat starting model of permittivity 2.5 is used. O . . V s . Iteration Figure 5.12: Variation plot for experimental set 2, method l(decreasing fi after every iteration). Figure 5.12 is a plot of the variation for the first method of decreasing fi. The variation decreases after every iteration. At the 7 iteration, the variation is not zero, although th from the graph it may appear so. 71 0> Vs iteration M 0.45 test case 1 test case 2 test case 3 0.35 0.3 0.25 5 e 0.2 0.15 -eâ€”e- 0.1 0.05 10 Iteration 12 14 <> ! 16 oâ€”*â€”Â©â€”$â€”1 18 20 Figure 5.13: Variation plot for experimental set 2, method 2(decreasing fi after every third iteration). Figure 5.15 is a plot of the variation for the second method of decreasing fi. The lines represent a specific test case. Similar to Figure 5.14, the variation decreases after every iteration. The variation exhibits large decreases in variation when the value of /? is changed. The variation at the 20 iteration is nearly zero for all three test cases. th 72 <S? 2 Vs. iteration test case 1 - Â© - test case 2 â€”&~ test case 3 iterations Figure 5.14: Modeling for experimental set 2, method l(decreasing /? after every iteration). Figure 5.14 plots the modeling error for the case where f3 is decreased after every iteration. The modeling error decreases after every iteration. The misfit value at the seventh iteration is clearly non-zero for test case three. 73 <D, vs iteration Figure 5.15: Modeling error for experimental set 2 , method 2(decreasing B after every third iteration). Figure 5.15 is a plot of the modeling error for the case where B is decreased after every third iteration. Both methods of decreasing B improve the variation and modeling error when the final solution is generated. For method 2, when B is decreased after every third iteration, the computed solution comes very close the exact solution. The average error in test case 1 is on the order of 10" , with similarly small errors for test cases 2 and 3. 4 The variation and modeling error terms also exhibit the steepest drop when the /? value is changed. The model error changes very little in Figure 5.15 when /? is held constant. This implies that the system reaches a minimum value for that particular B quickly. 74 The first method, where the value of /? decreases after every iteration, has a lager modeling error. Note that the first method requires 3 times less computation than the second method. The solution to method 1 is not as good as the solution to method 2. Method 1 corresponds to cooling the system too fast. Examining the variation and modeling error, these experiments show the same behavior as the first set of experiments, that is the variation and modeling error decreases after every iteration. The final value of modeling error for test case 3 is lower in method 2 than method 1. Figure 5.16: Image of permittivity distribution the experimental set 2, test case 3, method 1, and iteration 7. Figure 5.16 is a surface plot of the permittivity distribution for test case 3 of method 1 at the seventh iteration. The surface looks very rough. The major feature of test case 3 is visible. 75 Figure 5.17: Image o f permittivity distribution experimental set 2, test case 3, method 2, and iteration 21. Figure 5.17 is a surface plot of the permittivity distribution of test case 3 of method 2 at the 21 iteration. The solution resembles the exact solution. st Figure 5.17 resembles Figure 5.6 more than Figure 5.16 and demonstrates that the method where decreasing B slowly can find a better solution than the case where /? is decreased too quickly. 5.6 Experimental set 3 Experimental set 3 uses the same cooling concept as experimental set 2. There is only one experiment in experimental set 3. A noise signal with a standard deviation of 0.2 is added to the scattered field of test case 3. This is approximately 20% of the maximum 76 signal. In the presence of noise the cooling needs to be slower. More/? values are used in this case than experimental set 2. The value of fi decreases after every third iteration. The values 100, 50, 10, 5, 1, 0.5, 0.1, 0.05, 0.01, 0.005, 0.001 and 0 are used. The parameters in Table 5.2 are used. A flat starting model of permittivity 2.5 is used. <D V s . iteration M 15 20 iteration Figure 5.18: Variation plot for experimental set 2 (20% noise), test case 3. Note the nonzero variation value at the last iteration. Figure 5.18 is a plot of the variation. The value of the variation decreases after every iteration with the sharpest decreases when the value of fi changes. Because of noise the value of the variation never reaches zero. When fi is set to zero, the variation exhibits a small increase. For the similar test case in experimental set 2, the variation was near zero. The noise is clearly the cause of this behavior. 77 <I> V s . iteration 2 0.05 h 01 i i 0 5 10 , _J , 15 i i i 20 25 30 j I 35 iteration Figure 5.19: Modeling error plot for experimental set 2 (20% noise), test case 3. Note the jump in modeling error at iteration 30. Figure 5.19 is a plot of the modeling error. When the value of /? is set to zero, a sudden jump occurs in the modeling error. There is a corresponding jump in the variation plot. However, the jump in the variation plot occurs later. 78 Figure 5.20: Permittivity distribution for experimental set 3, test case 3, and iteration 30. Figure 5.20 is a plot of the permittivity distribution at the 30th iteration and Figure 5.21 is a plot of the permittivity distribution at the 31st iteration. Figure 5.20 looks much closer to Figure 5.6 than Figure 5.21. Both permittivity distributions display the major feature of a perturbation in the middle. In the presence of noise, small changes to the distribution are not recoverable. Figure 5.19 clearly illustrates that the regularization parameter cannot be turned off. When the parameter is turned off the system converges to a system completely different from the exact solution. The function 0 2 decreases with iteration, implying the solution is improving. Only when regularization is removed does the <D increase, which 2 is opposite to the desired behavior. In the noiseless experiment the exact solution is found when /? is set to 0; however, in this experiment the exact solution was not 79 recovered, due to the inability of the model to match the scattered field exactly. The regularization cannot be turned off in the presence of noise. Examining the variation in Figure 5.18, it can be seen that the equilibrium variation term is approximately equal to the variation of the noise signal and the data misfit remains small even after B has been set to zero. This is because the permittivity distribution in Figure 5.21 produces a scattered field that matches a noisy scattered field better than that of the scattered field from the permittivity distribution in Figure 5.20. This is expected from the results of Chapter 2. The results from Chapter 2 illustrated that two homogenous cylinders with significantly different permittivies can generate very similar scattered fields. The difference in their permittivity can be smaller than the noise. 2.6 24 22 1.6 1.4 1.2 -1 -1 Figure 5.21: Permittivity distribution for experimental set 3, test case 3, and iteration ion 31. 80 5.7 Experimental set 4 Experimental set 4 explores the case where there are more parameters than data points. There is one experiment in experimental set 4. B is decreased every iteration. Experimental set 4 uses different parameters from the previous three sets of experiments. The permittivity distribution is shown in Figure 5.22. Again, numerically calculated data are used, and the inversion tessellation can represent the distribution exactly. The parameters are presented in Table 5.3. Figure 5.22: Permittivity distribution for experimental set 4. Perturbation has permittivity of 1 and background has permittivity 2.5 The value of B is decreased more slowly than before. The need for more B values is expected in this case because of the higher number of inversion cells causing the system to be more sensitive to small differences. From experimental experience it is 81 known that more B values need to be used. Forty-one B values are used. This provides a slow convergence to the solution. Table 5.3: Parameters for experimental set 4 Parameter Cylinder radius k values Value 1 X 0.80*2TT 0.88*2TT 0.96*2TT 1.04*2* 1.12*2* 1.20*2* 1/19 X 1/51 X Inversion cell tessellation radius Modeling cell tessellation radius Incident wave Jkx e Observation locations -90 to 90 degrees with 6 degrees of separation. p=\.5 X B values 10.0000, 8.7500, 7.6563, 6.6992,5.8618,5.1291, 4.4880,3.9270,3.4361, 3.0066,2.6308,2.3019, 2.0142, 1.7624, 1.5421, 1.3493, 1.1807, 1.0331, 0.9040, 0.7910, 0.6921, 0.6056, 0.5299, 0.4636, 0.4057, 0.3550, 0.3106, 0.2718, 0.2378, 0.2081, 0.1821,0.1593,0.1394 0.1220, 0.1067, 0.0934, 0.0817, 0.0715,0.0626, 0.0547,0.0479 Iterations per B 1 Starting model Flat model of permittivity 2.5 Figure 5.23 is a plot of variation with respect to iteration. The variation decreases with every iteration. 82 <D Vs. iteration M 0.051 , -_, , ^_ , 0.045 - 0.04 - 0.035 - 0.03 0.025 iteration 40 Figure 5.23: Variation plot for experimental set 4, experiment 1. Note at iteration 41, the variation value off the scale presented, but finite and is approximately 0.5. Figure 5.24 is a plot of the modeling error. Notice the sudden increase in the modeling error when J3 is set to zero. 83 <I> Vs. iteration 2 0.05 20 iteration 25 Figure 5.24: Modeling plot for experimental set 4, experiment 1. From Figure 5.24 and 5.25, it can be inferred that the solution is getting closer with each iteration, however when the regularization is dropped to zero, the solution changes rapidly. This is due to the ill-posedness of the problem. If regularization is never turned off, an approximate solution can be recovered. When regularization is turned off the modeling error becomes large, while the data misfit remains relatively small. This is a result of the system being under-determined. The permittivity values become very large. The modeling grid is no longer adequate for the high permittivity values causing Richmond's Method to fail. This is the reason why the variation value remains small. 84 5.8 Experimental set 5 Experimental set 5 is the same as Experimental set 4, but with a different permittivity distribution. The permittivity distribution is shown in Figure 5.25. The permittivity distribution contains two blobs which are different than that of the background. -1 Figure 5.25: -0.8 -0.6 -0.4 -0.2 0 0.2 0.4 0.6 O.i Permittivity distribution with two blobs different than the background. Figure 5.26 the variation demonstrated the same behavior as the previous experiment. The variation decreases until B is turned off. The system diverges when B turned off. 85 d> V s iteration M 0.05 0.045 0.04 0.035 0.03 0.025 0.02 0.015 0.01 0.005 0 10 15 20 Iteration 25 30 35 40 Figure 5.26: Variation plot for 2 blob case. Figure 5.27 is a plot of the modeling error. It exhibits the same behavior as Experimental set 4. The modeling error decreases until 8 is turned off. 86 o 2 V s iteration 0.05 0.045 h 20 25 Iteration Figure 5.27: Modeling error plot for 2 blob case. Figure 5.28 represents the recovered permittivity distribution at the 41 , one st iteration before the regularization is turned off. The major features in the reference distribution are clearly visible. 87 Figure 5.28: Recovered distribution at the 41 iteration st 5.9 Conclusion In this chapter the behavior of the inversion algorithm is examined. It is shown that the addition of the flatness term aids in the search for the solution. In cases where there is a large perturbation from the starting model the regularization yields a better solution than the unregularized solution. It has also been shown that the exact solution can be found for over constrained cases i f /? is slowly decreased. The regularization imposed initially favors a flat starting model. 88 Figure 5.28: Recovered distribution at the 41 iteration st 5.9 Conclusion In this chapter the behavior of the inversion algorithm is examined. It is shown that the addition of the flatness term aids in the search for the solution. In cases where there is a large perturbation from the starting model the regularization yields a better solution than the unregularized solution. It has also been shown that the exact solution can be found for over constrained cases i f /? is slowly decreased. The regularization imposed initially favors a flat starting model. 88 For under constrained cases, where the number of observations are less than the number of inversion cells, the algorithm is still able to recover major features in the permittivity distribution, provided a very slow cooling algorithm is used. 89 C h a p e tr 6: S u m m a y r and f u t u r ew o r k 6.0 Summary This thesis examines the problem of recovering the permittivity distribution of an infinite cylinder. The scattered field is influenced by the permittivity distribution; therefore information can be recovered from the scattered field. A n optimization technique is used to recover this distribution. Many optimization techniques have been applied to the permittivity distribution recovery problem. Each technique has its strengths. The strength of the technique presented in this thesis is that there is a physical interpretation to the regularization, which differs from previous work in this area. The inference, from scattering observations, of the parameters of a homogeneous, infinite, circular cylinder is studied in Chapter 2. To solve the scattering problem a Bessel function expansion is used, and the boundary value problem for each Bessel function mode is solved. A quasi-periodic behavior in the scattered field is discovered. This quasi-periodic behavior is problematic because for a single frequency, two cylinders with different permittivity values can cause similar scattered fields. For optimization this implies that the wrong permittivity value can be found by the algorithm. This nonuniqueness problem is solved by the use of multiple frequencies in the recovery algorithm. In Chapter 3, Richmond's Method for forward modeling is presented and an inverse modeling algorithm is developed. Richmond's Method is used to model the scattering behavior of an inhomogeneous cylinder. From Richmond's Method the Jacobian of the predicted scattered field with respect to a guessed permittivity distribution is calculated. Knowing the Jacobian matrix, a linear approximation to the predicted 90 scattered field can be generated. To develop the inverse modeling algorithm an objective functional is minimized. The objective functional is the sum of two norms. The first norm term is the difference between the measured scattered field and a predicted scattered field. The second norm term is a measurement of the structure in the guessed permittivity distribution. To minimize the objective functional, the predicted scattered field is replaced by a linear approximation. The permittivity distribution that minimizes the objective function with the linearized scattered field can be found with a simple matrix inverse operation. To find the minimum of the original objective functional, this process is repeated using the permittivity distribution obtained from the previous iteration. The iteration process is repeated several times to find the minimum of the objective functional. A minimum of the objective functional occurs at the point where the exact permittivity distribution obtained and the numerically computed permittivity distribution are close to each other. The iterative algorithm is implemented in MatLab and the implementation is presented in Chapter 4. The weighting between the structure in the permittivity distribution and the scattered field is explored in Chapter 5. A homogenous model with permittivity 2.5 is used as the starting model. A constant weighting with respect to iteration is initially explored and it reveals that regularization aids in the convergence of the solution. When the weighting is large, the resulting solution looks flat. When small, a solution close to the exact one is found by the algorithm. Next, the weighting of the model structure with respect to iteration, is decreased, which is analogous to cooling in simulated annealing. The cooled system can now recover the permittivity distribution. When the system cools too quickly, the correct solution is not recovered. Rather, a solution close to the exact 91 solution is found. In the presence of noise or in a case where there are more degrees of freedom than observations, the weighting of the model structure cannot be zero, implying the necessity of a norm-based regularization. 6.2 Future work There are three directions for future work. The first direction is to implement a real system that uses the algorithm to examine long cylindrical structures, such as trees. Such a system currently exists [Dotto, 2003]. There are a number of challenges associated with the measurement of the electric field. These challenges include precision measurement of the incident and scattered fields, precision measurements of the geometry, and simulating the signal received by an antenna. A dipole antenna can be used to simplify the conversion between electric field and received signal. The current algorithm needs to be augmented by weighting the data with the measurement errors and including a x misfit criterion to terminate the inversion iteration. The second direction is to theoretically extend the algorithm. The algorithm can be extended to work with complex permittivity as well as 3 spatial dimensions. The speed of the algorithm can also be improved. One possible way to increase the speed is to explore an iterative technique to the L U decomposition. A different forward modeling algorithm can also be used to reduce the computation time. A third direction is the exploration of non-linear inversion and optimization in different electromagnetic problems, such as antenna design. Different model norms can be used in this type of parametric inversion. 92 Bibliography K. Dotto,"Development of an ultra wide band antenna", Preliminary draft of PHD thesis, unpublished, 2003. E. J. Bond, X . L i , S. C. Hagness, and B. D. Van Veen, "Microwave Imaging via SpaceTime Beamforming for Early Detection of Breast Cancer", IEEE Transactions on Antennas and Propagation, Vol. 51, ppl690-1705, August 2003 S. Caorsi, M . Donelli, D. Franceschini, and A. Massa " A New Methodology Based on an Iterative Multiscaling for Microwave Imaging", IEEE transactions on Microwave theory and technique, vol. 51, pp 1162-1173, April 2003. S. Y. Semenov, R.H. Svenson, A . E. Bulyshev, A . E. Souvorov, A . G . Nazarov, Y . E. Sizov, V . G. Posukh, A . Pavlovsky, P. N . Repin, A. N . Starostin, B. A . Voinov, M . Taran, G. P. Tatsis, and V . Y . Baranov, "Three-Dimensional Micowave Tomgraphy: Initial Experiments Imaging of Animals", IEEE transactions on Biomedical Engineering, Vol. 49, pp. 55-63, January 2002. M . Tanaka and J. Ogata, "Fast Inversion Method for Electromagnetic Imaging of Cylindrical Dielectric Objects with Optimal Regularization Parameter", vol. 84, pp25602565, December 2001 C. J. Lin and C. Chui " Image reconstruction of buried Dielectric Cylinder by TE Wave illumination" IEEE MTT-S LMOC 2001 Proceeding 213-216 (2001) Semenov, S.Y.; Svenson, R.H.; Bulyshev, A.E.; Souvorov, A . E . ; Nazarov, A . G . ; Sizov, Y.E.; Pavlovsky, A . V . ; Borisov, V . Y . ; Voinov, B.A.; Simonova, G.I.; Starostin, A . N . ; Posukh, V . G . ; Tatsis, G.P.; Baranov, V . Y . "Three-dimensional microwave tomography: experimental prototype of the system and vector Born reconstruction method", IEEE transactions on Biomedical Engineering, Vol. 46, pp. 937-946, August 1999. M . Pastorino " Short-Range Microwave Inverse Scattering Techniques for Image reconstruction and Applications", IEEE Transactions on Instrumentation and Measurement 47(6) 1419-1427 (1998) C. G. Farquharson and D.W. Oldenburg, "Non-Linear Inversion Using General Measures of Data Misfit and Model Structure" International Journal of Geophysics, Vol. 134, pp213-227, 1998. S. Hagness, A. Taflove, and J. Bridges. "Two-Dimensional FDTD Analysis of a Pulsed Microwave Confocal System for Breast Cancer Detection: Fixed-Focus and AntennaArray Sensors", IEEE Transactions on Biomedical Engineering, Vol. 45 pp 1470-1479, December 1998 93 A. Souvorov, A . Bulyshev, S. Y . Semenov, R. H . Svenson, A . G. Nazarov, Y . E. Sizov, and G. P. Tatsis "Microwave Tomography: A Two-Dimensional Newton Iterative Scheme", IEEE Transactions on Microwave Theory and Technique, vol. 46 ppl654-1659, November 1998 I. R. Ciric and Y Qin " Self-adaptive Selection of the Regularization parameter for Electromagnetic Imaging." IEEE Transactions on Magnetics, 33(3) 1556-1559 (1997) W. R. Hendee and P. N . T. Wells, The Perception of Visual Information, SpringerVarlag, New York, 1997 G. H . Golub and C. F. Van Loan, Matrix Computations, Third edition Maryland: The John Hopkins University Press, 1996 I. R. Ciric and Y . Liu " A n adaptive Algorithm for Electromagnetic Imaging", IEEE Transactions on Magnetics 32(3) 1303-1305 (1996) W.C. Chew and J. H . Lin " A Frequency-Hopping Approach for Microwave Imaging of Large Inhomogeneous Bodies", IEEE Microwave and Guided Wave Letters 5(2) 439-441 (1995) S. Caorsi, G.l. Gragnani, et al "Microwave Imaging Method Using a Simulated Annealing Approach", IEEE Microwave and Guide Wave Letters 1(11) 331-333 (1991) S. Caorsi, G. L. Gragnani, et al " A Multiview Microwave Imaging System for TwoDimensional Penetrable Objects." IEEE Transactions on Microwave Theory and Techniques 39(5) 845 - 851 (1991) I. Joachimowicz, C. Pichot, and J. Hugonin "Inverse Scattering: A n iterative Numerical Method for electromagnetic Imaging" IEEE Transactions on Antennas and Propagation, 39(12) 1742-1752 (1991) Y . M . Wang and W.C. Chew, " A n Iterative Solution of the Two-Dimensional Electromagnetic Inverse Scattering Problem" International Journal of Imaging Systems and Technology, vol. 1, no. 1, pp 100-108,1989. D.T. Borup and O.P. Gandhi, "Calculation of high resolution S A R distributions in biological bodies using the FFT algorithm and conjugate gradient method," IEEE transactions on microwave theory and technique, vol 33 pp 417-419, may 1985. M . Slaney, A . C. Kak, and L. Larsen, "Limitations of Imaging with First-Order Diffraction Tomography", IEEE Transactions on Microwave Theory and Technique, vol. 32 pp860-874, August 1984 J. H . Wilkinson and G. Peters, "The Least Squares Problem and Pseudo-Inverses," The Computer Journal, Vol. 13, No. 3, August, 1970. 94 J. H . Richmond, "Scattering by a Dielectric Cylinder of Arbitrary Cross-Section Shape," IEEE Transactions on Antennas and Propagation, vol. 13, pp. 334-341, May 1965. R.F. Harrington, "Time-Harmonic Electromagnetic Fields" McGraw-Hill Book Companv Toronto, 1961. ' F 95 y
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Cylindrical RF tomography
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Cylindrical RF tomography Lam, Kim 2003-12-31
pdf
Page Metadata
Item Metadata
Title | Cylindrical RF tomography |
Creator |
Lam, Kim |
Date | 2003 |
Date Issued | 2009-11-17 |
Description | Tomography allows the examination of an object's interior without having to destroy the object. There have been many forms of tomography including MRIs and CT scans. All forms of tomography infer the interior of an object from a set of measurements. An algorithm to infer the features of infinite dielectric cylinders using electromagnetic waves is developed in this thesis. The intended application for this algorithm is the imaging of lumber. The algorithm recovers the dielectric permittivity distribution from an infinite cylinder. It uses Richmond's Method to model the physical behavior of the infinite cylinder. The algorithm uses an iterative non-linear inversion scheme to recover the dielectric permittivity distribution. The non-linear inversion scheme uses a regularization term that minimizes the structure of the permittivity distribution subject to a constraint involving the measured scattered field from the cylinder. It was found that by decreasing the weighting of the regularization, and eventually turning off the regularization, the exact permittivity distribution can be recovered for a noiseless and over-determined system. In the presence of noise, an approximate permittivity distribution can be recovered; however regularization cannot be turned off. Similarly, for an under-determined system, an approximate permittivity distribution can be found, but regularization cannot be turned off. |
Extent | 7467079 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Collection |
Retrospective Theses and Dissertations, 1919-2007 |
Series | UBC Retrospective Theses Digitization Project |
Date Available | 2009-11-17 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065522 |
URI | http://hdl.handle.net/2429/15083 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 2004-05 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- [if-you-see-this-DO-NOT-CLICK]
- ubc_2004-0075.pdf [ 7.12MB ]
- Metadata
- JSON: 1.0065522.json
- JSON-LD: 1.0065522+ld.json
- RDF/XML (Pretty): 1.0065522.xml
- RDF/JSON: 1.0065522+rdf.json
- Turtle: 1.0065522+rdf-turtle.txt
- N-Triples: 1.0065522+rdf-ntriples.txt
- Original Record: 1.0065522 +original-record.json
- Full Text
- 1.0065522.txt
- Citation
- 1.0065522.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Country | Views | Downloads |
---|---|---|
United States | 15 | 0 |
China | 9 | 33 |
Brazil | 7 | 0 |
United Kingdom | 6 | 0 |
Canada | 4 | 0 |
Russia | 3 | 0 |
Japan | 2 | 0 |
City | Views | Downloads |
---|---|---|
Unknown | 8 | 3 |
Shenzhen | 6 | 33 |
Glasgow | 6 | 0 |
Ashburn | 5 | 0 |
Vancouver | 4 | 0 |
Saint Petersburg | 3 | 0 |
San Francisco | 3 | 0 |
Beijing | 3 | 0 |
East Lansing | 2 | 0 |
Tokyo | 2 | 0 |
Absecon | 1 | 0 |
University Park | 1 | 0 |
Columbus | 1 | 0 |
{[{ mDataHeader[type] }]} | {[{ month[type] }]} | {[{ tData[type] }]} |
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065522/manifest