MSU LIBRARIES .—:—-. RETURNING MATERIALS: Place in book drop to remove this checkout from your record. FINES wiII be charged if book is returned after the date stamped below. SYN'IIIESIS AND RECONSTRUCTION OF FUNCTIONS SATISFYING SIMULI'ANEOUS TIME AND FREQUENCY DOMAIN CONSIRAINIS USING ALIERNATING CONVEX PROJECTIONS WITH OVERELAXATION: AN APPLICATION IN IMAGE DESIGN By Dong. 100 Ken; A IBEIS Submitted to {ichigen State University in pertial fulfillment of the requirements - for the degree of MASTER OF SCIEN CE Department of Electrical Engineering and System Science 1985 ACKNOWLEDGEEENT I wish to express my sincere gratitude to Professor Soheil I. Sayegh for his expert guidance and stimulating advice throughout the course of this research. This research could not have been accom- plished without his encouragement and support. I would like to thank my father and my mother whose support and love have encouraged me to make this thesis possible. TABLE OF CONTENTS Chapter 1 mmooucrlon ............................ . ...... ' ..... 2 MATHEMATICAL FORMULATION ............................ 2.1 General algorithm description ................. 2.2 Mathematical formulation for imaging system ... 2.3 Incoherent case ..... ..... . .................... 2.3.1 Sets and Projection Operators ............... 2.4 Coherent case ................................. 2.4.1 Sets and Projection operators ............... 3 RESULTS AND DESCRIPTION ...... ....................... 3.1 Parameters specification ....... . .............. 3.2 Description of image synthesis results ........ 3.3 Numerical results for the phase restoration of an 1-D bandlimited function ..... ...... .. 4 CONCLUSIONS. DISCUSSIONS AND FURTHEI RESEARCH ....... APPENDIX A ................................................... APPENDIX B ................................................... APPENDIX C ................................................... FIGURES ................................................... REFERENCES OOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOO 10 14 15 20 20 22 23 26 28 3O 36 51 68 ABSTRACT SINIIIESIS AND RECONSTRUCTION OF FUNCTIONS SATISFYING SIMULTANEOUS TIME AND FREQUENCY DOMAIN CONSTRAINTS USING ALTERNATING CONVEX PROJECTIONS wmI OVERRELAXATION: AN APPLICATION IN IMAGE DESIGN By Bong. Joo Ueng A method of alternating projections with overrelaxation is employed for synthesizing images that are band-limited in the frequen- cy domain and with predetermined threshold crossings in the space domain. This problem is encountered when we want to generate a pres- cribed binary image at the output of a diffraction-limited imaging system with high contrast recording. Such an imaging system is modeled as a linear band-limited system followed by a noninvertible point nonlinesrity. Some of the important applications of image syn- thesis are the construction of masks for microlithOgraphy. laser printing. fabrication of surface acoustic wave devices and the storage of data using optical techniques. With a suitable choice of the over- relaxation parameter for the algorithm. it is found that the number of iterations required for this method is several orders Of magnitude smaller than that required for the Gerchberg-Papoulis type algorithm. This improvement is very important in designing images that are much more complex and of practical interest. Both incoherent imaging and coherent imaging systems are investigated. CHAPTER 1 INTRODUCTION There are many problems of great interest in, science and engineering where one wishes to reconstruct or synthesize functions which are specified partially in the time (or space) domain and par- tially in the frequency domain (Fourier domain). The task of finding functions satisfying such simultaneous constraints is a difficult one and depends on the constraints themselves. The problem however is very important as it arises in numerous situations. An example is the extrapolation of band-limited functions where only a finite segment of a band-limited function is given and it is desired to find the value of the function everywhere [8]. Another example is the recovery of a real nonnegative signal from the knowledge of the magnitude only of its Fourier Transform. Such a problem arises in X-ray crystallography. Fourier Transform spectrosco- py and imaging through atmospheric turbulence using interferometer data [9]. Still some other problems dealing with certain constraints are blind deconvolution [10]. computer holography [11). kinoforms [12]. design of radar signals. antenna arrays [13] and digital filters [14]. One may divide the problems of searching for functions satisfying simultaneous time and frequency domain constrains into two classes restoration and synthesis problems. In restoration problems. one wants to reconstruct a function (or a close replica of it) given that the function satisfies certain constraints. By the very nature of the problem. a solution must exist. In the synthesis problems. one wants to construct a function satisfying some specified constraints. A solution. however. may or may not exist. For example. one cannot con- struct a function that is of finite time extent and. at the same time. of finite frequency extent. Another important point is the question of uniqueness of the solution. If a whole class of functions satis- fies the given constraints in a restoration problem. we have to determine which function within the class is the solution. In the synthesis problem. on the other hand. one may be interested only in finding a solution. For example. when designing filters with certain time and frequency domain specifications. the primary concern is in finding some function satisfying all the given requirements. Later one may (or may not) choose to seek an 'Optimum' choice. Therefore the uniqueness question is of more concern in restoration problems than in synthesis problems. In this thesis. I deal with the problem of 'synthesis of images through a diffraction-limited imaging system with high contrast recording'. This is to generate a prescribed binary image at the out- put of an imaging system. Some important applications of this image synthesis problem are the design of masks for microlithography. the fabrication of surface acoustic wave devices. the storage of data using Optical techniques. laser printing and so forth. The models for the imaging system I will deal with are showni in Figure 2.1 and Figure 2.2 for the incoherent and coherent system respectively. These are adequate models for a microphotographic sys- tem where the linear system represents a diffraction-limited microcamera Operating near its resolution limit and the noninvertible hard-limiter represents a very high contrast recording film [5]. In mathematical terms. the output 3 must be band-limited and after pass- ing through the nonlinear device (noninvertible hardrlimiter). will produce a binary image according to the white (black) regions Of the binary desired image g that we want to construct. In other words. the overall purpose of the image synthesis problmm is to synthesize 3 such that it satisfies the Fourier domain constraint which is band-limited and the space domain constraint corresponding to predetermined thres- hold crossings. Some ad hoc methods for the solution Of this image construction problem have been proposed [3.4]. An example is corrections being deliberately introduced in the original masks to compensate for the distortions caused by the microcamera itself. More recently. it was shown that this problem can be reduced to a linear prOgramming problem which can be solved by using well known techniques [6.7]. Although the linear programming approach is superior to the ad hoc technique proposed earlier. it still suffers from the heavy amount Of computa- tion required, which prohibits its use on real images except for some very simple patterns. Another method for finding the solution is a variation of the Gerchberg-Papoulis algorithm (also refered to as the Gerchberg-Saxton algorithm) [1]. The algorithm itself is an iterative one. with an initial guess for the solution consistent with the given information (constraint) in one domain. repeated transformations are performed between the space domain and the frequency domain. In each domain. the known information (contraints) is incorporated into the current estimate Of the desired function (solution). forcing the esti- mate to satisfy the constraints corresponding tO the information specified in both domains. Depending upon the constraints themselves. the algorithm may converge or fail to converge at all. The method presented in this thesis is the method Of alternating projections with overrelaxation over closed convex sets in Kilbcrt space [2]. The concept is that the function f which we want to syn- thesize is belonging to the intersection C0 of m well-defined closed convex sets Ci's. i=19m. That is , the known properties (given infor- mation or constraints) Of the function f form m well-defined closed convex sets Ci's. i=19m. and such that m ffic0= 0 Ci' 1:1 Note that the intersection C0 is also a closed convex set con- tainiug f. If the desired function f does satisfy the above constraints. then the problem of synthesizing f from its m prOperties is included in that of finding at least one point (one function) belonging to C0, In chapter 2, both the incoherent and coherent models for the imaging system mentioned previously and the known properties (con- straints) corresponding to the closed convex sets of the function which we want to construct are mathematically formulated. The algor- ithm for finding the fixed point (solution) belonging to the intersection Co which is closed and convex of the image design problem will be considered in great detail. In chapter 3. some examples of 2-dimensional patterns that were designed using the algorithm presented in chapter 2 are presented. A comparison based on convergence rate is made between this algorithm and the Gerchberg-Papoulis type algorithm presented in [1]. Besides. numerical results of an 1-dimensional example for reconstructing the phase of a band-limited function using the method proposed in chapter 2 are also presented. In chapter 4. some discussions and suggestions are made for the image design problems in the future. CHAPTER 2 MATHEMATICAL FORMULATION 2.1 General algorithm description The image synthesis problem is closely related to the well known problem of image restoration. The main difference between these two problems is the existence of a solution. In image restoration. by the very nature of the problem. a solution must exist. While in the image synthesis problem. the solution does not necessary exist. An example is that one cannot synthesize a function that is time-limited as well as band-limited. In the image restoration problem. the Observed properties of the output function restrict the input function f to have certain proper- ties (given information or constraints). If every known prOperty of the input function f form a well-defined closed convex set Ci. ialém. in Hilbert space R. then m such properties place f in the intersection of the corresponding closed convex sets C1.C2....C The intersection m. Co is also closed and convex and contains f. Consequently. irrespec- tive of whether Co contains elements other than f. the problem of restoring the function f from its m prOperties is included in that of finding at least one point (one function) belonging to C0, Therefore. if the Operator P0 projecting onto C0 is known. the problem is solved. for then PoxeCo for every xefl. However. C0 in general can be consid- erably more complex in structure than any of the Ci's corresponding to the constraints and a direct realization of P0 is usually not feasi- ble. An alternate approach [2] for solving the problem is to consider every known prOperty of the function f that places it in a well-defined closed convex subset. and search for the intersection. If th’ projection °P°ttt°r3 Pi's on its respective Ci's. i.e.. PixaCi. for xaH and Pixax for xeCi. is effectively realizable. i-lém. then to find a point (function) satisfying the m given prOperties. a composi- tion operator T will be defined as follows: T=PnPu-me_3....P1. The operator T is in general not the projection operator onto Co, but every point of Co is a fixed point for every Pi and therefore of T. i.e.. if xeCo, then xeCi. Pix=x. i-19m and szx. With the initial guess other than the points belonging to Co, the iterative scheme has been developed for the generation of fixed points of T by the standard recursion Xn+xaTnX . where X : the arbitrary initial guess. u : the number of iterations. It has been shown that [2] a nonexpansive mapping T:H9H of a Hilbert space onto itself is a reasonable wanderer and .a fortiori. asymptoti- cally regular. and the sequence [Tnx} converges weakly to a fixed point of T. However. if the Hilbert space is of finite dimension. the sequence [Tax] will converge strongly to For for every er. What is needed then is to define nonexpansive projection opera- tors Pi's. i=19m. on the the respective Ci's. for a composition of two or more nonexpansive mappings is also nonexpansive. Lemma 1 [16] [17] : Let C denote any closed convex subset of Hilbert space H. then there exists a unique geC such that 3;; ns-xu = ur-sn . Now. the projection Operator Pi onto Ci is defined as follows: \. That is. the projection assigns to every feH its nearest neighbor Pif 8 min f-x xEIk in Ci. This defines a nonlinear projection Operator Pizfléci unambigu- ously by means of the minimality criterion. The projection Operators Pi's. ialém. defined above can be shown to be nonexpansive and continuous [2]. However the convergence rate using the composition of these Operators is not at a geometric rate. The convergence can be speeded up considerably if we replace Pi by Ti-1+§i(Pi-1). {i=192 (overrelaxation) with a proper choice of the Si [2]. It can also be shown that [2] the operators Ti's are nongxp‘n- sive. 2.2 Mathematical formulation for the imaging system Image construction involves determing the Object distribution which produces a prescribed image at the output of a given imaging system. The imaging system I deal with in this thesis is a diffrac- tion-limited imaging system with a high contrast recording device. Such an imaging system is modeled as a linear band-limited system fol- lowed by a bard-limiting point nonlinearity (clipper). The overall system is mathematically represented by the operator 6. where the input and the output image f and g. are related by g=Gf. The system G is known and a prescribed image g is to be generated at the output of the system. 2.3 Incoherent case The mathematical model for an incoherent diffraction-limited imaging system with high contrast recording device is shown in Figure 2.1. This is an adequate model for a microphotographic system where 10 the linear system represents a diffraction-limited microcamera Operat- ing near its resolution limit and the hard-limiter represents a very high contrast film [5]. The input function represents the intensity distribution which is a nonnegative valued function. Referring to this figure. we note that the value of g (intensity distribution) will be equal to 1 whenever 3 is above the threshold 7 and will be equal 0 when 2 is below 7. The value of y is determined by the recording material characteristics. Because practical systems are not expected to exhibit the infinitely sharp characteristics of the hard-limiter shown in Figure 2.1. a forbidden zone (-e.e) has been introduced about the threshold. Without loss of generality. we shall take 7 to be equal to zero since the threshold can be adjusted without affecting g by simply introducing a dc bias in the input function f. 2.3.1 Sets (constraints or known properties) and projection operators 1] C1: The subset of all functions band-limited to b rads/s. i.e.. faC1 iff F(m)=0 almost everywhere (a.e.) in lul>b. It is obvious that C1 is a closed convex set devoid Of interior points. Given an arbi- trary feH. its projection onto C1 is realized by 11 Plf e——>Pb(u)F(m) .where 1. [m]$b. Pb(m)={ o. lul>b. .} f¢—-——+F(m). 2] C2: The subset of all functions with predetermined threshold crossings and being the same as those of the desired given functiOn and the absolute value is greater than s. Th demonstrate closure of this set we must show that given a sequence {fa} with limit f (written fnéf) that [fn]eC2 implies feCz. Let f be the limit of the sequence (fn}' then we can write [Ilia-tl‘dxayeo. This requires that f have the same threshold crossing as those of the desired given function g and the absolute value be greater than c. and C2 be closed as claimed. The set is also convex. for £1 and fzeCZ. nf1+(1-u)f2eC2 for 0e P2f(l)= sign(g(x))e. f(x) is of different sign as g(x) :or [f]§;:o-jank/Ne-jZnnllN is the two-dimensional (cartesian) discrete Fourier Transform (2-D DFT) of the sequence [f(m.n)]. W" is the inverse 2-D DFT. and BT[F(k.l)]=F(k.l).H(k.l). 13 where K(k.l) is an ideal low-pass filter in frequency domain taking values zero and one only. Using overrelaxation. we form the function f'(m.n)=(1‘€1)f(m.n)+§1P1[f(m.n)]-T1[f(m.n)]. Then. f'(m.n). f'(m.n).g(m.n) is positive and [f'(m.n)IZe P2[f'(m.n)]= g(m.n)e. f'(m.n).g(m.n) is negative or lf’(m.n)lb fi—me). 2] C2: The subset of all functions whose square magnitude will have 16 the predetermined threshold crossings and being the same as those of the desired given image and does not fall in the region (y-e.y+e). For the purpose of convexity. the negative values of the function will never be smaller than -(7-e)‘/’. Since. refering to the figure shown below. if the negative values are allowed to be smaller than -(1-s)‘/3. then for two points. say x1 and x2 where x2 is negative. the magnitude square for these two points is above the threshold. HO'OVGI P11+(1-p)x2. for 0(n(1. will fall in the region ['(7)‘/’.(7)‘/:]. where the magnitude square is below threshold. and violate the convexity. As in the incoherent case. this set also can be shown to be closed. j-(y+e) «Y i-(y-e) 4) x1 .. (7+e)1/3 ‘:(1*e)1/’ O "'(y-e)‘/’ «-*/‘ .b {2 «-(.-a> lI-Y v-(7+e) Figure 1. 17 Th0 projection operator 92 on this set is defined as c f(x). lf(x)l$(7-e)1/1 and lg(x)]$(y-e)‘/‘ f(‘)' f(l)>(7+¢)1/3 and lg(x)|2(y+e)‘/3 1’2”“)13L (7+8)1/3. lg(x)]2(y+¢)‘/’ and f(x)<(y+¢)1/3 (7“)‘II- [8(8)]$(7-e)‘/' and f(x)2(y-e)‘/‘ L'(7")x/z' |8(x)]S(1-e)‘/3 and f(x)<-(y-e)1/' where g(x) is the desired given function and y is the threshold value. In discrete-time form. the algorithm is implemented as follows: P1[f(m.n)=[W’1BTW]f(m.n) where W[f(m.n)]=F(k,1)=§:::2§;:f(m'n)e-j2nmk/Ne-j2nnl/N is the 2-D DFT of the sequence [f(m.n)]. W" is the 2-D DFT. and 18 BT[F(k.l)]=F(k.l).H(k.l). where H(k.l) is an ideal low-pass filter in frequency domain taking values zero and one only. Using overrelaxation. we form the function I y’l awn-14- f'(m.n)=(1-€1)f(m.n)+§1P1[f(m.n)]=T1[f(m.n)]. Then. rf'(m.n). g(m.n)ao f'(m.n). g(m.n)=1 P2[f(m.n)]=i(7+e)‘/'. g(m.n)-1 (y-e)1/z. g(m.n)=O L-(y-e)"3. g(m.n)=0 and [f'(m.n)l $(y-s)U3 and [f'(m.n)]2(7+e)‘/1 and lf'(m.n)z|$(y+e)‘/z and f'(m.n)2(y-e)‘/' and f'(m.n)I-(y-e)‘/’ where g(m.n). the desired output function. takes the values 0 and 1 only corresponding to the white and black regions respectively of the desired given function. and 7 is the threshold value. Using overre- laxation. we form the function 19 f1(m.n)=(l-§2)f'(m.n)+§2P2[f'(m.n)] 'T§[f'(m.n)]. The nth iteration step proceeds as follows: fnaTIf (m.n)]=Tn[f(m.n)]. I!“ where f(m.n) is the initial guess. T1'1+§1(Pl‘1)‘(1‘§1)*§1P1 T231+é2(P2-1)8(1-§2)+§2P2e CHAPTER 3 RESULTS AND DESCRIPTIONS Five two-dimensional patterns were designed for the incoherent imaging system using the algorithm presented in this thesis. 3.1 Parameters specification The parameters listed below are needed to specify the images and the algorithm. N: The number of pixels sampled on the pattern along each dimension. M: logzN LWP: The bandwidth of the low pass filter along each dimension corresponding to the diffraction-limited microcamera. ti: The overrelaxation constant for the algorithm. a: The value for the forbidden zone about the threshold. 20 21 The values Of the parameters for the program (Appendix C) imple- mented on the PRIME 750 digital computer are as follows: For patterns 1. 2 and 3 N=32 u-s §1=§2=1.99s e80.001 6 :for pattern 1 LW 11 :for pattern 2 11 :for pattern 3. For patterns 4 and 5 N364 5:86 €13§2=1.995 830.001 17 :for pattern 4 LWP= 26 ;for pattern 5 22 3.2 Description of image synthesis results Figure 3a represents the desired image which we want to construct at the output of the imaging system of Figure 2.1. If we feed this image to the input of the imaging system. the output from the clipper will be as shown in Figure 3b. Clearly. it is highly distorded by the imaging system and therefore the straightforward approach consisting of using the desired pattern itself as an input is not appropriate. Using the algorithm proposed in this thesis. I succeeded in find- ing the solution (required input image) that will produce an exact replica of the desired pattern after passing through the imaging sys- tem. The value of the solution (required input image) is then quantized into 10 gray levels and shown in Figure 3c. Figure 4 to Figure 7 are presented in the same format as Figure 3. The number Of iterations required to find the solutions for each of the images are listed below in Table 1. In addition. the number of iterations required for the Gerchberg-Papoulis algorithm [1] is also included. It can be seen that the algorithm presented here gives great improvements over the Gerchberg-Papoulis algorithm. 23 3.3 Numerical results for the phase restoration of an 1-D bandlimited function The numerical results presented in Table 2 represent the sum of square error when I try to use the algorithm presented here to recover the phase in the time domain of a one-dimensional band-limited func- tion.The magnitude and phase of the function are known a priori. The phase of the function is then thrown away and the function goes through the algorithm with initial random phase and the original known magnitude. It is found that. for the 1-D case. the sum Of square error is very small after a certain number of iterations. even though the phase restoration leads to a nonconvex projection problem. 24 Tabble 1 Number of iterations to reach convergence Convex projections Gerchberg-Papoulis with overrelaxation algorithm [1] Pattern 1 19 414 Pattern 2 14 216 Pattern 3 20 613 Pattern 4 13 ee Pattern 5 80 “ Table 2 (The values presented below represent the sum of square error of recovering the phase of an 1-D bandlimited function with N-128) LWP=28 The value for t 1.50 1.70 1.74 0 110.86 110.86 110.86 10 2.672 2.62 2.61 50 0.645 0.358 0.47 no. of iterations 100 0.296 7.68:10" 0.138 150 0.173 s.10:10" 7.90:10" 200 0.116 4.20:10“ 7.38:10” 250 7.39:10" 4.09:10" 6.99:10" 299 4.75:10" 4.03:10“ 7.07:10" 25 Table 2 (continue) LWP=30 The value for t 1.75 1.84 1.85 0 115.93 115.92 115.92 10 3.502 3.880 3.939 50 1.485 0.816 0.971 no. of iterations 100 7.34x10" 8.00:10” 8.96:10" 150 2.70:10" 2.56:10“ 8.95:10“ 200 1.35:10" 7.57:10" 8.95:10“ 250 8.82:10" 3.21:10“ 8.95:10“ 299 6.37:10" 1.64:10" 8.13:10“ Lfl2231 The value for t 1.85 1.865 1.87 0 119.847 119.847 119.947 10 1.105 1.110 1.113 50 1.18:10" 1.09:10" 5.18:10“ no. of iterations 100 4.27:10" 1.69:10" 7.32:10“ 150 1.19:10" 1.16:10" 7.52:10" 200 1.12:10" 1.12:10" 5.66:10" 250 1.10:10" 1.09:10" 7.47:10“ 299 1.07:10" 1.07:10" 5.58:10" CHAPTER 4 CONCLUSIONS. DISCUSSIONS AND FURTHER RESEARCH By using the alternating projections method and appropriately defining the closed convex sets corresponding to the constraints of the functions which we want to construct. we can find a solution whenever the solution exists. Furthermore. with the particular choice Of §1=§2=l.995. the number of iterations required is several orders of magnitude smaller than that for the method of Gerchberg-Papoulis. This improvement is of great practical importance when we want to design more complex images. As mentioned in chapter 2 . for the case of coherent imaging. the input function f represents field distribution and as such is a com- plex function. By extending the class of inputs to include complex inputs as well, we hOpe to have better resolution. Invoking the sampling theorem. to completely determine a real function [I]. band-limited to mo. we need Zwo samples/sec. To represent a complex function ITIeJQ? which is band-limited to ml, we need Zwl complex samples/sec or equivalently 4u1 real samples/sec. Therefore 33 1038 as “1 is not smaller than wO/Z. it may be possible to find a phase QT such that lT]eJQI is band-limited to m1, For the two-dimensional case. a similar argument shows that m1 would have to be larger than uo/(2)1/3. 26 27 The above arguments show that it may indeed be possible to obtain better resolution using coherent imaging system with complex input and it provides limits on what we could hope to achieve. However. the problem of synthesis of the phase for a nonnegative function will lead itself to a nonconvex set problem (this is similar to the well known problem of recovering the phase from magnitude). The method prOposed here cannot handle this problem and will not converge to the solution. An investigation of the alteration of this method or finding another algorithm is necessary for solving this problem. Another constraint on the input function that is of great interest is the Object itself being restricted to be of binary nature or to be quantized to a finite number of intensity levels. This res- triction is very important. because of physical implementation considerations. Another example is computer holography [11] where the magnitude of the function is given and the coefficient of its Fourier Transform must be chosen from a set of quantized values (because of the limitations of the display device and the materials used to syn- thesize the hologram). However. the Operation of quantizing a signal is not equivalent to projection onto a convex set. and therefore can- not be handled by this method. Further research is necessary to resolve this issue. APPENDIX A 93 'nitio I —n A DIFFRACTION-LIMITED optical imaging system is one which blocks the high frequency components of the input Object. A mapping TzDCLRNekN is nonexpansive on a set DOC.B if llTX-TYH i‘lX-YH X.YeDo .............. (l) and strictly nonexpansive 03 Do if strictly inequality holds in (1) whenever X#Y. nginition 3 A point X. in the domain of T is called a fixed point of T if Tx‘sx . Dgfinition g A sequence [fa] is said to converge strongly to f if 4-4 and is said to converge weakly to f if ll 0 lim n90 Iimngactn.g)=(f.g) 28 29 for every geRN, where (f.g) is the inner product operation of f and g. Note that strong convergence to f always implies weak convergence to f. In a finite-dimensional linear vector space. the converse is also true. De 'nitio ; A subset D 0f RN is said to be convex if. together with x1 and x2. it contains nx1+(l-p)x2 for all u. OSpS. It is closed if it con- tains all its strong limit points. De ' it'o g A mapping T:DC-RN9RN is said to be asymptotically regular if for every xeD. Tax-Tn*‘x90 as n90. [‘4 De ' ' 'on A mapping T:DC’.RN-)RN is said to be a reasonable wanderer if for every xeD. Tnx-TRI‘x‘ 1(G. 22.. It is evident that a reasonable wanderer is automatically asymtotical- ly regular. APPENDIX B Ihgogem 1 [2] Let PC:RN9C is a operator projecting RN onto C. CeRN and such that f-x amin um where feRN, then Pc is nonexpansive. PROOF: goggllgry 1 : Let C be a closed convex subset of R". Then for any xeRN (x-ch.y-ch)$0. all yeC. ................(2) In this guise it can be interpreted to mean that the vector x-ch is supporting to C at the point cheC. As Figure A suggests. x-ch is "normal" to the "tangent plane" to C erected at the point ch. This plane has C and x on opposite sides. and therefore separates one from the other. Note also that the angle 9 between the vectors x-Pc; and Y‘Pcy is never less than 90°. 30 31 tangent plane Figure A. Corollary 2: Let C be any closed convex set. Then for every pair of elements x and y in R”, l PrOOfi Since ch and Pcy both belong to C. it follows from (2) that ‘$(x-y.pcx-Pcy). ..............<3) Pox-Pcy (x-ch.Pcy-ch)$O . ..... ........ .......(4) and (y-Pcy.ch-Pcy)$0. . .... ............ ...(5) and (3) is Obtained by addition of (4) and (5). Now. Schwarz's inequality applied to (3). we will get.for every x and y in R“, I \. Therefore. the Operator Pc is nonexpansive. ch-Pcy i-y\\. ............ (6) 32 Theorem 2 [2] For 0$§i$2. the operator Ti=l+§i(Pi-l)=(1-éi)+éiPi is nonexpan- sive. where the Operator Pi is nonexpansive. Proof: The assertion is obviously correct for OSgifil. For l<§i$2. it is found that. with the aid of (3) and (6). l‘Tix-Tiyuz=u(l‘§i)(x-y)+§i(Pix-Piy)H3 ............... .(7) .(1'éi)3”x-y“1+2§i(l-§i)(x-y.Pix-Piy)+€i‘“Pix-Piyuz ....(8) 5(1-ti)’Hi-yu’+<¢i’+2¢i(i-§i)inpix-piyu‘ °'---'--‘9’ 3(1‘Ci)zHX’yu3+§i(2'§i)HPiX‘Pin3 ... ............ (10) $(§i(2-¢i)+(1-¢i)')“x-y”‘-Hx-y“’ ... ............. (11) and nonexpansive is established. Thus. TaTmTh_1....T1 is also nonex- pensive. Ihggggg A; [17] Let T:C9C be an asymtotically regular nonexpansive Operator with closed convex domain CCZH. and let its set of fixed points A¢ZC be nonempty. Then for xeC. the sequence {Tax} is weakly convergent to an element of A. Moreover. the convergence is strong iff at least one subsequence of [Tax] converges strongly. 33 Theogem 3 [2] The Operator T=Tme_1 ..... T1 is a reasonable wanderer for O<§i<2‘ i=19m. proof: For m=1. we have T=T1, Coacl and ||x-Ix“‘=§1‘\x-Ple‘. .. ........... . ................ (12) Moreover. for any yeCo. TyaPly'y and |\Ix-y“’=“x—y+¢1(pl-nu’ .. ........................... (13) =“X‘YH3+2§1(x'Y.P1x-x)+§g1‘x-P1xnz .. ............ (14) =Hx-YH’-§1(2-§1>Hx-P1xu‘+2tl(x-Pli.y-plx) ....... (15) SHx-y“‘-§1(2-§1)Hx-Plx“’ ........................ (16) since the last term in (15) is nonpositive. Thus by combining (12) and (16). it is found that llx-Tx ‘:$§1(Hx-yH3f\Tx‘y“z)/(2'§1) ............... (17) for O<él<2. For arbitrary m21. a straightforward induction on m yields the inequality I lx-Tx ’sbm.2m"( x-y Tx-y‘z) ................. (18) ‘2- 34 where yeCo and bm= sup [fit/(Z-éi)] . (Clearly. (17) subsumes the case m=1.) In fact. let TaThK where and observe that for m22. ii-Iiu‘=Hx-xx+xi-riH’ $(“x-K;H+Hxx-Ii“)‘ $2(“x-Kxu’+“Ki-Ix“’) $2(“x-KxH1+2m-1HKx-TthHz). .................. (19) Thus. by induction hypothesis ((bnlfin)/(2-§m) and bmz‘uPISiSm-1[§i/(2'§i]‘ Note also that yeCo implies y Ci and yeCm). x-y x-Txuzibm.2(2m-z XX'Y “3+2m- 1 ‘2_zu-a Kx-ynz-Zm'zHTx-y“z) abn.2°"(\x-yH’-Hri-yu’). ................... ..(20) the desired inequality. It now follows immediately from (20) that Ins-I“*‘ 3 m-l sbmz \‘=_-au_gm cae=_n (Id _ _ _ A Emmmxm wcwwmew mconozoo N.N onnwmm '[Illi'lll _ . . TM e o “ ET... . Ill—IL) H . . Ax w 0 3m 3: . (mommacoz mmfiom _ . . N A3: I Emmmxm memmefiapcmm manm>cfiimwacm nmomwa '[II'E IIIII' I III. Ill U I'll-I'll I'll I ll'lll U Ax: 53 Figure 3a. Desired Pattern (Pattern l) Figure 3b. Constructed pattern when the object in Figure 3a. is used as an input to the imaging system in Figure 2.1. 55 // // Input pattern found by our iterative procedure which has been quantized into 10 gray levels. Figure 3c. 56 Figure 48. (Pattern 2) 57 Figure 4b. 58 : . / 74/ . V7 4 , . / W W/W W ”H 7, 7% 7, .7 W7 7/77fl/7/W/7H , WW WWW/W 777 ,.///7 7 / . W W/W“ , ,, 7 W W/ W /W / / / /W7/ / 7 7 7 777/ W,/ . ”WW. // . W/W 777% / / / / mn//// WW Imvwflm /. / /7 W 777/7 7 7 .7. //7 U/J/ / W/VW W .. /.fi..,..fl7 Figure 4c. Figure 5a. (Pattern 3) 6O Figure 5b. 7..7 r / .. 7 ; 127 ..7 77.7, 7... 77 . ..r. //7.77. . 7777.7... ../ 7, . .. . 7 . I . 7. ,/ . . 7 7. 7 7 7 . ..777 77...... 7.. 77 .. . .7. ... ....37/7/ .. .7.. . .7. .5/. 1.7.7. 7, H7/7777. . ./ . . . .7. 7.7777777 7777.7: ,./ I 77. I a: ,. [1.7/8 ,/ 7 7.. 1.1 7.... / 7747.747I? . A)“ . .7 ... , ..7 7. ... 7 . . 7. 4.. . .1. .7.... 777.77.... 7. .77.. 77/// . .. 7 7 Wflfimm . 47.. :W . ?WE.¢H.7. [WW .7 .777. ../......./77/ .7... .. . ///...,/«7.. I 7.7 7 /7,.7. . / 7 / 7/7/ I . 7 7c ...7/ 7W ...7/ . W...7. , 7. 77 77/77.../..W..77.. / I/ / / / 7//7/7 w7.W/ 7. /./_. Figure 5c. 62 Figure 6a. (Pattern 4) Surface acoustic wave device 63 Tw-I—r' 85“? " @‘HFTIE "PE ".3 an m&-! in! In lanai E .Q . %amn ta “-fia Figure 6b. 64 /CK/73C/' /C//OC/7’ /C//C//9’ /7C//9C/ /DC//9C/ /7r pp I NTx: 777777 ////// ////// ////// ////// // 7'7 ////// ////// ////// ////// ////// // 770/ /VC€//%Zé/ /%Z£//790/ 7OCK/VOC/ /04//%Z%/ /QCK/7Wh/ /QC/ //7793%Z/%z¥£/ /Z%&b¢4%/ /%%Z¢%&///77%%W2é/ /%&W7A%% /%Z/ /WM/‘VW WW WWW/ /7¢NIIB% AZWflaHZIEyzWWWaRWaIaflLfi/flleyfixflllfifl/WEE’HHNWC”zgggé/ /%Z%/ /¢%&ZVW%%/ /WZ%/%%%%/ /O€%%Z%Zh’ /%ZW%/%&W/ WWWZZWW’ /Oe§/ /V’ 73%/7€%/ /€%//7%2/ /064/70’ /%64/7%W/ /¢%//70’ /90/ 76/ /OC//QC/ /704/706/ xfiK/VOC/ /94/76//9’ /04/704/ /9’ /7’ /77904/ /79006/ /99064/ /9044// /90066/ // Figure 6c. 67 // '/ ////// / \“ . y / 1;. 7”. ’ I, -’7 7 r. 7 ill/(W Iz— 2&3; , .4 , w '7 /, IWWfiW 7’7 - I1 . - ’2' (’7’!) , Z7] , r. W ' ~ / 7 / ll . .7, ' . . - 7 W :7 .f—’ . 7 ,_ «r ' 7 2 / 475/7} 1'”; ‘/’ 77777 7 , WWW/77 AW], .7 "WWW/1n Figure 7c.. [1] [2] [3] [4] [5] [6] [7] [8] REFERENCES Y. Kok. Synthesis of images through a diffraction-limited sys- tem with high contrast recording. M.S. thesis. Michigan State University. E. Lansing. 1983. D.C. Youla and H. Webb. Image restoration by the method of convex projections: Part I-Theory. IEEE Trans. on Medical Imag- ing. Vol. MI-l. pp. 81-94. 1982. B.E.A. Saleh and S.I. Sayegh. Reduction of errors of micrOphotographic reproductions by optimal corrections of origi- nal mask. Opt. Eng.. Vol. 20. pp. 781-784. Sept. 1981. Eastman Kodak Co.. Techniques of microphotography. Publications NO. P-52. Rochester. New York. 1967. G.W.W. Stevens. MIcrophotOgraphy. Butler and Tanner. London. 1968. S.I. Sayegh. B.E.A. Saleh and K.M. Nashold. Image design: Generation of prescribed image through a diffraction-limited sys- tem with high contrast recording. to be published. S.I. Sayegh. Image restoration and image design in nonlinear optical system. Ph.D. thesis. University of Wisconsin. Madison. 1982. A. Papoulis. A new algorithm in spectral analysis and bandlim- ited extrapolation. IEEE Trans. Circuits and Syst.. Vol. CAS-22. PP. 735-742. 1975. 68 [9] [10] [11] [12] [13] [l4] [15] [16] [17] 69 1.R. Fienup. Iterative method applied to image reconstruction and to computer-generated hologram. Opt. Eng.. Vol. 19. pp. 297-305. 1980. A.V. Oppenheim and 1.8. Lim. The importance of phase in sig- nals. Proc. IEEE. Vol. 69. pp. 529-541. 1981. R.A. Gabel and B. Lin. Minimization of reconstruction error with computer-generated binary hologram. Appl. Opt. Vol. 9. pp. 1180-1190. 1970. N.C. Gallagher and B. Lin. Method for computing kinoforms that reduces image reconstruction error. Appl. Opt.. Vol. 12. pp. 2328-2335. 1973. R.S. Elliot. Synthesis Of rectangular planer arrays for sum patterns with ring side lobes of arbitrary topography. Radio Sci- ence. Vol. 12. pp. 653-657. 1977. L.R. Rabiner. Linear prOgram design of finite impulse response (FIR) digital filters. IEEE Trans. on Audio and Electroacoustic. Vol. Au-20. pp. 280-288. 1972. 1. Goodman. Introduction to Fourier Optics. McGraw-Hill. 1968. N.I. Akhiezer and I.M. Glazman. Theory of linear operators in Hilbert space. Vol. 1. New York: Ungar. 1978. D.C. Youla. Image restoration by the method of projections onto convex sets-Part 1. POLY-MRI 1420-81. Dec. 1981. ")fiifilflfllfljlifllfltflfijflfflifihimAMI)” 5 4859