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 0
e
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