THESE; ‘.WP m” wwww _w _,t,”

 
   
  

«p— — x
.- \ 1
(I . ' . I
”it VF“ Vw"? - Va Y x

EAL: H 1

E i 1

I‘ i

. I ‘73- “l- l 1

[A y o (2“ t a . '2‘... :1."- I; ’ It"? I 1‘ a 6e ‘1

$3 5375‘ ,. ‘5' '- .~. u. _ ~~ ._. .
~ 6‘ (E‘ A
“7; ‘ mm :16: a“ r at. ~
5 133.319 38: 1.. em ‘0» 1,

raj-12:. 3:

v §' u ~ v 4- % At!)

This is to certify that the

dissertation entitled

Synthesis of Images Through a Diffraction
Limited System with High Contrast Recording

presented by

Yon-Lin Kok

has been accepted towards fulfillment
of the requirements for

M.S.

 

degree in Eiec. Engr.

 

 

Date l\/\/%3

MSU is an Affirmative Action/Equal Opportunity Institution 0-12771

MSU

LIBRARIES

 

RETURNING MATERIALS:
Piace in book drop to
remove this checkout from
your record. FINES wiII
be charged if book is
returned after the date
stamped beIow.

 

SYNTHESIS OF IMAGES THROUGH A OIFFRACTION
LIMITED SYSTEM WITH HIGH CONTRAST RECORDING

By

Yon-Lin Kok

A THESIS

Submitted to
Michigan State University
in partiai fulfillment of the requirements
for the degree of

MASTER OF SCIENCE

Department of Eiectrica] Engineering
and Systems Science

1983

ABSTRACT

SYNTHESIS OF IMAGES THROUGH A DIFFRACTION
LIMITED SYSTEM WITH HIGH CONTRAST RECORDING

BY

Yon-Lin Kok

Image synthesis aims at determining the object distribution of the
input image which when distorted by an imaging system (e.g. a display
device) produces a prescribed image at the output of the given system.
The image synthesis problem is encountered in the design of masks for
microphotography, microlithography, laser printing and aids for the
visually impaired. In this thesis, we solve the problem of generating
the prescribed 2-dimensional images through an imaging system that is
modeled by a linear bandlimited (diffraction limited) system followed
by a noninvertible point nonlinearity (high contrast recording). It
is shown that the iterative algorithm presented in the thesis to solve
this problem always converges to a solution whenever one exists. The
problem of existence of solutions is examined while several patterns
of the prescribed output images are successfully produced by using the

algorithm with computer simulations.

ACKNOWLEDGEMENT

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 accomplished
without his encouragement and support. Sincere appreciation is also
extended to Division of Engineering Research, Michigan State University,
for its offer of financial support. I would like to thank my father
and my mother whose support and love have encouraged me to make this

thesis possible.

To my mother and father

TABLE OF CONTENTS

Chapter Page
l INTRODUCTION ................ . . . l
2 MATHEMATICAL FORMULATION ............ 4
2.1 Problem Formulation ............. 4
2.2 Description of the Algorithm ......... 5
2.3 Proof of Convergence ........... . . 6
3 THE EXISTENCE OF SOLUTIONS . . . . ........ lO
3.1 Problem Formulation ............. lO
3.2 Methold of Eliminations . . . ........ l2
4 EXAMPLES ON IMAGE DESIGN . . . . ..... . . . . 15
4.l Parameter Specifications . .......... 15
4.2 Description of Results ............ l6
5 CONCLUSIONS AND FURTHER RESEARCH ......... 18
APPENDIX A ......................... l9
APPENDIX B . . . ...... . . . . . . . . ........ 2l
APPENDIX C-l . .......... . ............ 26
APPENDIX C-2 ........... . . . . ......... 34

FIGURES ........................... 37
REFERENCES ......................... 66

 

CHAPTER I
INTRODUCTION

This thesis investigates a new image processing problem, which
may be called "image design” (or, perhaps, "image synthesis"). Consider
a nonideal imaging system, e.g., a microfilming camera, a laser printing
system, or an image display device. An ”input” image is fed to the
system and the "output" image is generated (displayed). The goal of
image design is to determine the input image that generates a prescribed
desired output image.

An example of some ad hoc image design procedures which have
been adopted in the past by the microprinting and microphotographic
industry, are the corrections usually made in the original masks.

These corrections are deliberately introduced to compensate for the
distortions caused by the microcamera itself. Serifs are introduced
around corners to remove rounding effects, and sharp local reductions
of thickness are made in intersecting lines to prevent the formation
of fillers [1,2]. For instance, Kodak recommends the addition of
triangular serifs to corners, the dimension of which were determined
by a process of trial and error [2].

At first sight it appears that this problem of “image design“
is mathematically identical to the well known problem of image
restoration, the difference between them being mainly one of motive.

One subtle difference, however, has to do with the existence of a

solution. In an image restoration problem, the measured output results

from an actual, albeit unknown, input. In the absence of measured
error or noise, at least one solution must exist. In an image design
problem, on the other hand, it is possible that no input image is able
to produce the desired output image. Therefore, in image design, a
problem of great concern is that of existence of a solution. If more
than one solution exists, the choice among such solutions is only a
matter of convenience. In an image restoration problem, one is usually
concerned with uniqueness. Typically, more than one input image could
produce the measured output image, and a choice is usually based on

a priori statistical information.

The imaging system that I will be dealing with in this thesis
is a linear low pass system followed by a hard-limiter (clipper) as
shown in Figure l. This is an adequate model of a microphotographic
system where the linear system represents a diffraction limited micro-
camera operating near its resolution limit and the hard-limiter re-
presents a very high contrast film. E3

Image design can be applied to fabrication of masks for inte-
grated circuits, the fabrication of precision optical instruments
like reticles, ronchi rulings and resolution charts (Figure 2,3).
Another potential area is in optical data storage (Figure 4). There
is no doubt that many other applications will surface as the area of
image design becomes more mature.

In Chapter 2 of this thesis, the image design problem mentioned
above is mathematically formulated and an algorithm is presented for

its solution.

The question of existence of solutions is examined in Chapter 3.

In chapter 4 I give some examples of 2-dimensional patterns
that were designed by using the algorithm presented in Chapter 2.
Chapter 5 concludes this thesis with a brief summary and directions

for further research.

CHAPTER 2
MATHEMATICAL FORMULATION

2.l Problem Formulation

Image design involves determining the object distribution which
produces a prescribed image at the output of a given imaging system.
The imaging system as mentioned in Chapter I, is a linear system h
followed by a hardlimiting point nonlinearity ®(-) which is not
invertible. The overall system is mathematically represented by the
Operator G, whose input and output images, f(x) and g(x), are re-
lated by g = Gf, as illustrated schematically in Figure l. The system
G is known. A prescribed image 9 is to be generated at the output

of the system. We would like to address the following questions:

(i) Is it possible to find an input image f'E F, which satisfies
given properties or conditions represented by the set F, such

that the output Gf = g?
(ii) If "yes“, how may f be determined?

(iii) If “no”, how to determine an appropriate input image f' which
produces an output 9' = Gf' that is closer to the desired 9
according to some criterion (metric)?

The question of existence of solutions will be examined in the

next chapter. In this chapter I present an algorithn1that will find

a solution whenever one exists. Referring to Figure l we note that
the value of g will be equal l whenever g is above a threshold
y (determined by the filn1characteristics) and will be equal to 0
when a is below y.
Without loss of generality we shall take y to be equal to zero
since the threshold can always be adjusted without affecting g by

simply introducing a dc bias in the input function f.

2.2 Description of the algorithm

The proposed method is an iterative one starting with the

transform

of the desired output function g(x) = go(x).

The n-th iteration step proceeds as follows: We form the function

l,|w|<w0

(w)p (w) where P (w) =
WO {0 , otherwise

n = l,2,--

obtained by truncating Gn_1(w) (Figure 5.8) and compute its inverse

transform

fn(><)

ll
\——3
l E

C)
"Tl
A
E
v
(D
.1.
E
X
C].
E
\
l\)
:1

We next form the functions

 

where fn(x) = |fn(x)| , for lfn(x)| > e > O
i e; , otherwise

O<)\<l

(Refer to Figure 5)

I am going to prove in the next section that the function
gn(x) tends to be a bandlimited function with the same zero crossings
and polarity as the desired output function g(x) as n + w. Therefore,
a solution to the image design problem is obtained in the form of

g(x) in Figure l.

2.3 Proof of Convergence

In the N-dimensional space, LRN, equipped with the Eudidean
norm (tz-norm), we define the mappings a, 13, TO and FB as follows:

(1') c1: Ef(n)] = |f(n)l mm. 0 < n < N-l

where D(n) is the prescribed output function

(11') T6 [f(n)1= Maxte,f(n)1, 0 < n < N—l

(iii) TO[A(n)] = |A(n)| , O < n < N-l

. _ -l
(1v) FB - W BTW

where W and W'] denote the discrete Fourier Transform and

its inverse respectively.

BT[A(n)] = {A(n) , n é'IB
0 , ne IB , 18c {o,~-,N-1l

Since these four mappings are nonexpansive (Appendix B) we
are able to define the composite mapping G by

G = ¢T€ TOFB

where G is nonexpansive on a closed subset D0 of RN, this subset

D0 is specified by the prescribed output function D(n) as follows:

RN is divided into 2N polyhedrants.

(a polyhedrant is the N-dimensional generalization of the quadrant)

N

D is the polyhedrant that contains the point D(n) E R .

0
Let DO denote this closed convex set, then GD0 C1DO. The iterative

algorithm presented in Section 2.2 can be written as

AK+](n) = XAK(n) + (1-A)GAK<n> , K = 0:l’--- (1)

The convexity of DO ensures that the above sequence AK(n) is well
defined and remains in D0.
Suppose A* is a fixed point of G in DO’ then using

Euclidean norm,

- A*H2

HA “MK-1V + <1-neAan

K+l

XZHAK-AHI2 + (1-i)2HGAK-A*H2

+ 2X(l- x) (GAK A) )T(-Ak -A) (2)

“AK-GAKHZ = “AK-A*n2 + neAK-A*H2-2<GAK-A*)T(AK-A*) (3)

Multiply (3) by X(l-X) and add to (2), we have

HAK+1-A*H2 + A(1-A>HAK-GAKH2 = AHAK-A*“2 + (1-x)HGAK-A*H2

IA

“AK-A*u2

For any m 3 O

x(l-X) i HAK-GAKH2 5 I [HAK-A*V2-HA A*H21

K=O K=O K+l

uAO-A*u2 — nAm,,-A*u2

' *
hAO-A H2

I /\

Therefore, the series ) “AK-GAKH2 on the left side is bounded and
each term “AK-GAKH2 is nonnegative, it converges for m + w, in
particular,

lim “AK—GAKH2 = o
K+oo

Since “A

K+]-A*“ 5 HAK-A*H 5 HAj-A*H 5 “AO-A*“

VK>O,j<K , (4)

the sequence {AK} is bounded in the sense of Euclidean norm and hence

there is a convergent subsequence {AK } which, by the closedness of
1

*
00’ must have its limit point B in 00'

Equation (l) shows that

lim (A -B*)=lim (A -B ) + (l-X) lim (GA -A )
1.... Ki“ we K1 1+0. K1 K1
= 0
By the continuity of G
68* G 1' A 1‘ GA 1' A 8*
= 1m = 1m = 1m =
W K1.+l W K1.+l W K1.+l

*
i.e. the limit point B is itself a fixed point of G.

* *
Equation (4) holds with 8 instead of A and accordingly the whole

*
sequence {AK} converges to the fixed point B .

Therefore if a solution (limit point ) exists, the algorithm will

converge to this sloution (limit point).

CHAPTER 3
THE EXISTENCE OF SOLUTIONS

3.l Problem Formulation

Consider the function g(x) at the output of the low pass

filter H(w) (Figure l). Let G(K) denote its Discrete Fourier

A

Transform. We have the following conditions on G(K), K = O,l,...N-l

. N-l . -i-2—"kn

G(K) = E g(n)e N , K=O,l,...,N-l (5)
n=0

G(K) = 0 , K 6 18 = {B+l,~',N-B-lI

where g > B 3 O

A

On the other hand, there are requirements imposed on G(K)
by the point nonlinearities such that the prescribed output function

g(n), n = O,l,...,N-l is generated. These requirements are

1 N-l , 1%.K
N KZO G(K)e 3 e- if g(n) > O (6)

-E “If g(n) < 0

I A

n = O,l,...,N-l
From formulas (5), (6) we can write down the conditions that G(K)

should satisfy in terms of a system of inequalities.

lO

ll

G(O)+2{Re[G(l)e ]+Re[G(2)e ]+o--+Re[G(B)e I}
3 Ne:, if g(n) > o (7)

-Ne, if g(n) < 0

IA

.Zn

. . ‘N‘nK

Let G(K) = XK + 1yK and e = AnK + J an
K = 0,1, ,8
n = O,l, ,N-l

(Note that y0 = O, bn0 = O, An0 = l)

Therefore, inequality (7) becomes
AnOXO+2{(Aanl-bnlyl)+(An2X2-bn2y2)+°°°+(AnBXB-anyB)}
3N6 if g(n) > O (8)
E -N€ If g(n) < 0.

We multiply those inequalities corresponding to g(n) < O by a factor

(-l), then inequality (8) becomes

CjoKo + CjiKi +"'+ Cj,ZBKZB 3 C (9)

-2b. ., C= N€>O

where CjO = l, C.. = 2A.., Cj,i+B = 3,1

J1 J1

2b--,C=N€>O

and K = X

12

i = l,2,...,B
- O,l,...,N-l

Ll.
l

Formula (9) forms a system of N linear inequalities with
(28+l) unknowns which are real parts and imaginary parts of the
Discrete Fourier Transform of the bandlimited function g(n). We shall
present a method to check for the solvability or consistency of this

system in the following section.

3.2 Method of Eliminations

For a system of linear inequalities with (28+l) unknowns,

the set of solutions, denoted by S 5), forms a convex set in the
l

(
(28+l) dimensional hyperspace R<2B+ ). An indexed K of real numbers

(R K ..,K

O’ 1,. ) 5 8(5) if all the inequalities

28

K

C. K +~~+C K > C j: O,l,...,(N-l)

C 31 1 j,28 28 —

jO 0’ +

are true statements.
Consider legal linear combinations of the given system of linear

inequalities (9)

dOKO + d1K] +...+ dZBKZB 3 d (10)
N-l
where d1 = Z UQCRi , 1 = O,l,...,ZB.
2-0
N-l
d = C 220 U2 - UN , 2 = O,l,...,N.
and U > O.

A

13

Since the process of eliminations either yields a solution for
S or exhibits the inequality O-KO + O-K1 +---+ 0-KZB > O as a legal
linear combination of the inequalities of S, the process of elimination

proceeds as follows:

(1) Separate the N inequalities of the system into three classes
by observing the coefficient CjO’ j = O,l,...N-l ‘
Class I: where CjO > 0
Class II: where CJ.0 < 0
Class III: where CjO = O
(2) Define a new system S' of inequalities in the unknowns

 

 

K0, K1,...,K28 by

0 KO + 0 K1 +.--+ 0 K28 > -1
c. c... C.. c...

M0 + (C_J_,1 _ C1 ,1 ) K] +.... (#— EL’Z—BWB 2E _ E"
jl’o jll,0 jl,0 :jll,O J'I,O j”,0

(11)
for all pairs j and j' with Cj'O > 0, Ci”,0 < O ,
O"<0 + C3"".1'K1‘L'”+ Cj“'2BKZB > C

for all J w1th Cj”',0 = O

(3) In case that all the coefficients of K0 are of the same sign
then we can set CJ.0 = 0, j = 0,...,N—l (i e. there always exists
a real number K0 such that formula (l0) is a true statement).

(4) Repeat steps (l) (2) (3) with the coefficient le’ j = 0,...,N-l

and then Cjza CJ-39"'9CJ',(ZB_])'

14

This process must end after (28) steps. The right hand side

of equation (ll) is always positive (since C = N 6 > O, Cj.0 > O, Cj" 0 <0).

Therefore, the system is solvable or consistent if the coefficients
(after EB eliminations) of KZB are of the same sign. On the other
hand, if there are any two coefficients of K28 among these n in-
equalities differing in signs then the system is not solvable. (1.6.

solution does not exist.)

CHAPTER 4
EXAMPLES ON IMAGE DESIGN

Six 2-dimensional exampleson the image design problem previously

mentioned are presented in this chapter. Iterative solutions based on

A (n) = AA (n) + (l—X)G AK(n)

K+l K

where G = ¢ RE TO FB

n = O,l,...,N-l

are illustrated from Figure 6 to Figure ll.

4.l Parameter Specifications

Let N = the number of points sampled on the desired output pattern
along each dimension (or axis).
M = log2 N
LN = the bandwidth of the low pass filter along each dimension
(or axis).
X = the relaxation constant defined in the above equation.
Computer simulations by means of FORTRAN programs are implemented
digitally with the following parameter values:
N = 32
M = 5

l6

 

LN = {l2 , for pattern l,2 .
( 8 , for pattern 3 -
6 , for pattern 4,5.
‘ 4 , for pattern 6 .
X = 0.5

The numerical values of the iterative solution are computed
by PROGRAM SETKD (Appendix C-l), where 2-dimensional Discrete Fourier
Transform is used (SUBROUTINE FFTZD). These output data are then
quantized into l0 levels and each level is assigned a degree of grayness.

The graphical representations of the 2-dimensional output data are

obtained by PROGRAM GRAF (Appendix C-2).

4.2 Decription of Results

I would‘Jike to define R(n) as the ratio of the energy of the
image (signal) after n-th iteration within the low pass band of the
filter to the total energy of the image (signal). Since R(n) appears
as a measure of the rate of convergence of the iterative algorithm,
it is always helpful to keep track of R(n) as the iterations are

going on.

Table 4.l shows some values of R(n) relevant to our results.

 

 

 

 

 

 

 

 

Patterns LN Starting Intermediate Final Figures
ratio; R(O) ratio ratio
l l2 0.78572 R(8) = 0.99935 R(40) = 0.999985 6
2 l2 0.80872 R(8) = 0.99818 R(80) = 0.99997 7
3 8 0.86962 R(8) = 0.99955 R(80) = 0.99997 8
4 6 0.77806 R(40) = 0.99925 R(300) = 0.99995 9
5 6 0.90792 R(8) = 0.99946 R(40) = 0.99999 l0
6 4 0.80940 R(8) = 0.99794 R(80) = 0.99999 ll

 

 

17

Consider the iterations that pattern I takes (Figure 6). Figure
6.a shows the pattern we want to design. Figure 6.b shows the output
pattern from the clipper if the image shown in Figure 6.a is fed into
the imaging system. Clearly, Figure 6.b is not the required pattern
and therefore the straightforward approach consisting of using the
desired pattern as an input is not apprOpriate. Using our algorithm
we obtain the pattern shown in Figure 6.c after 8 iterations. Clearly,
this is an improvement over Figure 6.b. After forty iterations we
succeed in finding the required input image (Figure 6.d) that generates
an exact replica of the desired pattern in Figure 6.a. Referring to
Table 4.l we see that 99.9985 percent of the energy in the image (Pattern l)
falls in the band of the low pass filter.

Pattern 2 to pattern 6 are shown from Figure 7 to Figure ll
respectively. The figures for each pattern come in the same order as

stated above.

CHAPTER 5
CONCLUSIONS AND FURTHER RESEARCH

The image design problem that I addressed in this thesis consists
of finding the input image that should be fed to a known imaging system
to generate a prescribed desired output. I have presented an algorithm
that solves this problem and I successfully designed several patterns
using the algorithm. I also gave a proof of convergence of this algorithm
and examinedthe question of solvability of this problem.

There are many interesting questions that still need to be
examined. The first one is whether we can improve on the rate of
convergence of the algorithm. The second is to attempt to find easier
methods to check for the existence of solutions. The third one is to
study the performance of the algorithm when the problem is known to
have no exact solution. Finally we can attempt to design images using
other imaging systems. Microlithography, optical data storage and
laser printing are only a few of the potential areas of application of

image design.

18

APPENDIX

A.

Definition 1

 

A mapping G: D CIRN + RN is nonexpansive on a set 00 C10'

if
HGX-GYH g H X-YH vx, Y e 00 (1)

and strictly nonexpansive on 00 if strictly inequality holds in (1)
whenever X # Y.
. * . . o * * c
Any p01nt X in the domain of G for wh1ch X = GX 15

called a fixed point of G.

Definition 2

 

A mapping F: D ClRN + RN is contractive on a set 00 CiD

if there is an a < I such that

Hex - GYH 5 allX-YH vx, YE DO (2)

Theorem l

Suppose underEuclideannorm G: D<:_RN‘+ RN is nonexpansive

on the closed, convex set 00 C10. Assume, further, that GDO ClDO

and that 0 contains a fixed point of G. Then for any X 6 (0,1)

0

and X06 00’ the iteration

19

20

X = XX + (1-X)GX

K+1 K K’

Converges to a fixed point of G in D0'

K = 0,1,...

21

N

In N-dimensional hyperspace R with Euclidean norm, the

following four mappings a, T5, T0, and F are nonexpansive:

B

(i) ¢[X(n)] = |X(n)l- g(n) , O < n < N-l

where g(n) is given as the prescribed output function, (Image) and

(ll) Té[X(n)] MaxLE, X(n)] , 0 < n < N-l

where e > 0 (G = 0.05 for our imaging system)

(iii) TOIX(n)] |X(n)l , 0 g n 5 N-l

. _ -1
(1v) FB — W BTW

where W and W'1 denote the Discrete Fourier Transform and its

inverse respectively.

BT[X(K)] = { 0 , Ke IBC{0,--~, N-ll

X(K) , Otherwise

Proof:

¢LX(n)] = |X(n)| g(n), 0 f n < N-l

where |g(n)| = l.

(IX—1H2 -

l
M
X
A
5
v
I
_<
A
3
v
N

n=0

N-l 2
> I | |X(n)l - |Y(n)ll
n=0

N-l 2
= I | |X(n)t9(n) - |Y(n)|°9(n)l
n=0

N-1

= 21¢ mm - ¢[Y(n)1|2
n=0
= 11¢<x> - MHZ
=> HX-YH 3 HMX) - <1>(Y)H

Equality holds if X(n)-Y(x) 3 0 v tie {o,--o, N-1}

é ¢ is nonexpansive.

(ii) Te [X(n)] Max[e , X(n)]

5;] 1m 36 [X(n)] , o < n < N-l

E
(3) Tm[X(n)J = MaxtO. X(n)1
2 ”‘1 2
For (I) (2). HX-YH = )0 IX(n)-Y(n)l
n:
N-l 2
= 2 ILX(O)'EJ'[Y(D)’EJI

94>

_ 2
{ l|S€(X)-$€(Y)H
-l -l 2
HSE (X) SE (0“
Equality holds for all X,Y 6 RN
Se, s; are nonexpansive.
2 _ 2
For (3), Hx-YH - ) |X(N)-Y(n)| + C |X(n)-Y(n
neIX neIX
where X(n) 5 0 if neIX
X(n) 3 0 if ne 1;
. . . c
(a) Part1t1on IX 1nto IxY and IXY
where y(n) 5 0 if n e-IXY
c
y(n) > 0 if n e IXY
2 _ 2 2
E |X(n)-Y(n)| — E |X(n)-Y(n)| + E c |X(n)-Y(n)|
neIX neIXY neIXY
3 C (X(n)-v<n)12: 2C |Y(n)|2
neIXY neIXY
= E |Tm[X(n)1- Tm[Y(n)]|2
neI

(b) Partition I into I c and ICC

where y(n) < 0

23

X

X Y X Y
1f 11 e IXCY

. c
if n e IXcY

24

zcnwrwmfi= : nmrwmfi+ I umrwmfi
neIX neIXcY nef§c¥
3 |X(n)|2 + c: |X(n)-v(n)12
neIXcY tieIXcY

I [Tm[X(n)] - Tm[Y(n)]|2
nsIXc

From (a) (b), we have

HX-YH2 3 HTm(X) - T (Y)H2

m

or HX-YH 3 HTm(X) - Tm(Y)H

é> Tm is nonexpansive.

1

Therefore, the composite mapping T5 = 8; TmSe is nonexpansive.

(iii) T0£X(n)1 = |X(n)l . 0 5 n 5 N-l

N-1 N-1
Hx-YHZ = 2 Mn) - v<n>12 2 2 1mm - 1v<n>112
n=0 n=0
N-1 2
= “20 |T0[X(n)] - T0[Y(n)]|
2

HTO<X) - 10(1)“
HX-YH 3 H10(x) - T0(Y)H

=9’T0 is nonexpansive.

FB = w BTW
Let X(K) =
Then HX-YH2

25

N-l -1%§k n
E x(n)e , O _<n : N-l
n=0
N-l N-l
= E |X(n)-Y(n)l2 = %- ) |X(Kl-Y(K)|2
n=0 K=0
11-1
3-‘N— I l|X(K)l-IY(K)||2
K=O
UN I 11x<K>1-IY<K>112+‘N z (0001-1100112
KEIB KQIB
3,1,— ; Hum-11w?
kgIB .
1 ieX(K 16Y(K) 2
W 1 ||X(K)le - (Y(KHe I
KeelB

=> HX-YH 3 llFB(X)-FB(Y)H

Equality holds if X(K) = Y(K)

for

1(6 IB'

From (i) (ii) (iii) (iv) we can define the composite mapping

9 FB is nonexpansive.
G :‘SEIOFB
and GDO C100, where 00

g(n)

such that G is nonexpansive on a closed subset D0 ClR

associated with the mapping ¢.

N

is specified by the given image function

89
3O

26
C-l: 2-dimensional zero-crossing Algorithm

PROGRAM SETKD (INPUT, OUTPUT, TAPE 1, TAPE 6 = OUTPUT)
COMPLEX A(32,32), E(32,32)

REAL F(32,32) , T(32,32)

INTEGER D(32,32)

COMMON/FF/A

READ (1,1) M,N,LN,JIT

FORMAT (413)

N1 = N/2 + 1
LN1 = LN/2-1
LNLT = N1-LN1
LNLZ = LNLT-l
LNRT = N1 + LN1
LNRZ = LNRT + 1

READ (1,2) ((D(I,J), J = 1,N), I = 1,N)
FORMAT (3212)

DO 3 I = 1, N

DO 3 J = 1, N

F(I,J) = FLOAT (D(I,J))
A(I,J) = CMPLX(F(I,J),0.0)
IV = O

IN = 0

DO 30 J = 1, N

WRITE (6,37)F(1,J),F(2,J),F(3,J),F(4,J),F(5,J)
C F(6,J),F(7,J),F(8,J)

37

32

33
34

36

35

31

O

28

27

27

FORMAT (1X,8(E9.3))

DO 32 J = 1,N

WRITE (6,33)F(9,J),F(10,J),F(11,J),F(12,J),F(13,J),
F(l4,J) ,F(15,J) ,F(l6,J)

FORMAT(1X,8(E9.3))

DO 34 J = 1,N

WRITE (6,36)F(17,J),F(18,J),F(19,J),F(20,J),F(21,J),
F(22,J),F(23,J),F(24,J)

FORMAT(1X,8(E9.3))

DO 35 J = 1,N

WRITE (6,31)F(25,J),F(26,J),F(27,J),F(28,J),F(29,J),
F(30,J),F(31,J),F(32,J)

FORMAT(1X,8(E9.3))

IN = IN + 1

IF(IN.EQ.4)GO TO 39

IF(IN.GT.1) GO TO 98

DO 9 I = 1,N

DO 9 J = 1,N

T(I,J) = REAL(A(I,J))
SIGN = 1.0

CALL FFTD2(N,M,SIGN)

DO 27 I 1, LNLZ
DO 28 J = 1, LNLZ
A(I,J) = 0.0

DO 27 J = LNRZ,N

A(I,J) = 0.0
DO 41 I = LNRZ,N
DO 42 J = 1, LNLZ

42

41

10

11

98

29

28

A(I,J) = 0.0

DO 41 J = LNRZ,N
A(I,J) = 0.0

SIGN = -1.0

CALL FFTD2 (N,M,SIGN)
IV = IV + 1

IF (IV.EQ.1) GO TO 10
IF (IV.EQ.8) GO TO 10

GO TO 98
DO 11 I = 1,N
DO 11 I = 1,N

F(I,J) = REAL(A(I,J))

GO TO 89
DO 29 I = 1,N
DO 29 J = 1,N

E(I,J) = CONJG(A(I,J))
E(I,J) = E(I,J)*A(I,J)
E(I,J) =C$QRT(E(I,J))
REAL(E(I,J))

-n
A
H

U
C...
V
II

RE = F(I,J)
IF(RE.LT. 0.0S)F(I,J) = 0.05

F(I,J) F(I,J)*D(I,J)
F(I,J) = (T(I,J)+F(I,J))/2.0

IF(IV.EQ.80) GO TO 89

DO 38 I 1,N

DO 38 J 1,N

38

39

29

A(I,J) = CMPLX(F(I,J),0.0)
GO TO 8

STOP

END

4o

41

42

43

44

45

46

SUBROUTINE FFTD2(N,M,SIGN)
COMPLEX A(32,32),X(32),Y(32)
COMMON/FF/A

CALL SHIFT2(N)
IF(SIGN.LT.0.0) GO TO 43

DO 42 J 1,N

DO 41 I 1,N

X(I) = A(I,J)

CALL FFT2(X,Y,SIGN,M)

DO 42 I = 1,N

A(I,J) = Y(I)
IF(SIGN.LT.0.0) GO TO 46

1,N

DO 45 I

DO 44 J 1,N

X(J) = A(I,J)

CALL FFT2(X,Y,SIGN,M)

DO 45 J = 1,N

A(I,J) = Y(J)
IF(SIGN.LT.0.0) GO TO 40
CALL SHIFT2(N)

RETURN

END

30

47

31

SUBROUTINE SHIFT2(N)
COMPLEX A(32,32)
COMMON/FF/A

COE = -1.0

DO 47 I 1,N

DO 47 J

1,N

IPOW = I + J

CO = COE**IPOW
A(I,J) = A(I,J)*C0
RETURN

END

48

32

SUBROUTINE FFT2(X,G,SIG,M)
DIMENSION X(1),G(1)
COMPLEX X,G,W

INTEGER R

SIGN = -1*SIG

N = 2**M

N2 = N/2

FLTN = N

PHIZN = 2.*3.1415926536/DBLE(FLTN)
DO 49 J = 1,M

N2J = N/(2**J)

NR = N2J
N1 = (2**J)/2
DO 48 I = 1,N1

INZJ = (Irl)*N2J

FLIN2J = IN2J

TEMP = FLIN2J*PH12N*SIGN
W = CEXP(CMPLX(0.0, TEMP))
DO 48 R = 1,NR

ISUB = R + IN2J

ISUB1 = R + IN2J*2
ISUBZ = ISUB1 + N2J
ISUBB = ISUB + N2

G(ISUB) = X(ISUBl) + W*X(ISU82)
G(ISUBB) = X(ISUBl)-W*X(ISUB2)
CONTINUE

 

 

49

50

51
52

33

DO 49 R = 1,N

IF(SIGN.LT.0.0) GO TO 51

DO 50 R = 1,N
G(R) = G(R)/FLTN

RETURN

DO 52 I = 1,N
G(I) = X(I)
RETURN

END

C-2:

21

22

23

24

26

34

PROGRAM GRAF(DATA,TAPE1 = DATA)

DIMENSION A(32,32),X(6),Y(6),IBUF(1025)

IN = 1

CALL PLOTS(IBUF, 1025,3, PAPER = 15/VEL PEN1 = 2/BLACK

PEN2 = NOT USED PEN3 = NOT USED USER = KOK YON-LIN PHONE =
3559078', 90.0,84)

CALL SYMBOL(-0.5, -1.0, 0.112, ”PAPER = 15/VELPEN1 = 2/BLACK
PEN2 = NOT USED PEN3 = NOT USED USER = KOK YON-LIN PHONE = 3559078')
CALL PLIMIT (65.0)

VX 0.84
VY = 0.0

READ(1,21)((A(I,J),I 1,8), J = 1,32)

FORMAT (8E9.3)
READ(1,22)((A(I,J),I

9,16), J = 1,32)
FORMAT (8E9.3)

READ(1,23)((A(I,J),I 17,24), J = 1,32)
FORMAT (8E9.3)

READ(1,24)((A(I,J),I

25,32),J 1,32)

FORMAT (8E9.3)

GO TO 8
VX = 15.0
VY = 0.0

READ(1,26)((A(I,J),I = 1,8),J = 1,32)
FORMAT(8E9.3)

READ(1,27)((A(I,J),I 9,16), J

H
.—l
v
(A)
N
v

 

27

28

29

35

FORMAT (8E9.3)

READ(1,28)((A(I,J),I = 17,24),J = 1,32)
FORMAT(8E9.3)
READ(1,29)((A(I,J),I = 25,32),J = 1,32)

FORMAT(8E9.3)

IF(IN.EQ.4) GO TO 5

DO 4 I = 1,32

00 4 J = 1,32
IF(A(1,J).GT.0.0) GO TO 7
A(I,J) = -2.0

GO TO 4

A(I,J) = 2.0

CONTINUE

CALL PLOT(VX,VY,—3)

EX = 0.3536
00 2 I = 1,32
00 2 J = 1,32
IV = 33-1

JV = J

1V1 = IV-1
JV1 = JV-1

(1 V*EX

X)
X() (l)
X(2) = JV1*EX
X)
X)

.—
—
—
-

.1:

(A)

(

J
X

= X(2)
(5 = 0

.0

36

X(6 = 1.0

Y(l = IV*EX
Y(2 = Y(l)
Y(

= Y(3)

)
)
)
3) = IV1*EX
)
) 0.0
)

1.0

S = (A(I,J)+2)/0.4
S = S+1

IF(S.LT.1)S = 1.0
IF(S.GT.10)S = 10.0
K = A1NT(S)

D = 0.5/K

CALL SHADE(X,Y,4,1,D,45.0,0)
IN = IN+1
1F(IN.EQ.5) GO TO 6
GO TO 3

CALL PLOT(0,0,+999)
STOP

END

37

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.o Empmxm mcwmmEH ._ wcsmwd
IllllllllllllllllllIlllllJ
o _
L--- _
MP A <_. .TT
Cam 3% E: _ Q:
I Empmam umpwew_ucam
A; w 3:822:02 ”ESQ ucmEmZTtEm Laws: _
v _
Ill lllllllllllllllllllL

 

 

@ 1111111111111111111111111111

+

1111101111111
n\

llllllll

Figure 3

 

 

 

 

39

RETICLES

ALIGNMENT TARGETS

RONCHI RUUNGS
SUTS AND APERTURES

LINEAR SCALES

RESOLUTION CHARTS

 

Figure 4

'40

Li!"- '.Z:.'."- 'J' 1':-
. 3:51' '4' {Jag-1.?
:‘HI: u-Jv-I.

Jud...

:..-'".:-'_-.1. Via" '35:;-

.0 1 I o,- 1 a 1': 11-144 9 o c'nu'nn'o 0'”

41

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 5

 

 

 

       
   
  

WW
2, ‘ 23/] 23/ //% 2%

 

 

 

 

 

 

 

 

 

%%/ 7/ //7///////%

WWW
/
/%

y/ /%/////// /%//% /%/%/%
2 /

 

 

  

 

/

// , /% //////’//
// / yfl

/////////// / / 2

4.
b

 

 

 

   

WWW

    
 
  

/ fl /
//

 

 

 

 

46

 

 

,/ // ////%l

      
   

_ _
\\ \\\\\S
\\\\\\\\
§ .
\\\\\\\\\S\

\\\\\\§

\\\\§

3
\\\\\§\

\.

\\
\\

/

/
2 //.

\

s\‘\\\

{§
§‘\\

§§

%

/

\
$8

3

S\\\\\
\§
\\

§
\\\\\\\

\\\\\\\

/ I

7 // 2) /
y//2////% ///¢
”/7 /”

I ////
l”/ a %/ /
,%
//3

/

‘\
\

\\ \\
\\\\\\§

\\\\\\\\\\\\§

/

\

/

\ ‘\
\§\\

/

\\\\
\\

\ is

/

\\\\\\\\\\\\\\
XS
S
3
\,

\\

 

 

Figure 7a.

47

2222222222

22222

222222

222222

/
222
22222

2

22222222222

 

2
2/

2

2222/22/22/2

22

222

222/2222222222222/

2222

22

 

2222222222222222222222222///

/22

 

1
i 3 '
5 l

22

222/2222

222/22

2

2222/22/22

222/7

.22
2222222222
2 22/2
./2222 //2///

2222

22 2
22 222/2222222222222

222

2

/2/////

//

22/

222/22222222

 

 

Figure 7b.

 

 

 

22 2

22222222222222
/

22222222222

222/222

2222/

22222222
222222222
22 222222222

2222222222222

/

222/222222222222

2
/

222/22/

////2/
22222222222222

//22////

22222222222222
/

22/2/

2

2/

222
22222

 

 

  

222222222
2222, 2222222222222 2222
222 222222

2222 22222

%22
222%2/

,/’//2/2,
222
;’///2/22/2
22
22222

222222222

2222;;

 

22
/222/22

. 622,

Figure 7c.

%,2

2 2222

2//////222

222/2222

49

 

 

222222222 2222222222222 2222222222222222222
2222222222222 2 2 2222222 22222222222222
2222222222 222/2222 2222 222222222222
222222222222 22 222 2222 2222/ 222222222222 .22
2222222222 2 2 2 2.222 2 2222/22/22

22

/// / /.2/ /
// 222/,//2,/2272/2//A2%%22A/2flm
2/222222/2/2/22/2/22222/22/2222/ 2222/22.
222 2222 22 2 2 222222 222222 222
22222 2222/2222 2222/ 2 22222222
2222222222222 222222222222 222222
2222222222222 222222222222222222222 2222
2 22222222222222222222 22
/

2NW22//,22
2/21; 22222222222
2 222/222222222222,fl7m22WW/2
222/22222222222222
2222/22/2222/2 222222222 22222222 2 222222 2272
22 22/22/2/22/222222/ 2/22 2 2 222 2/2 22 22222
222222 2/22 2222 2222/22/22 22 22
/22 222222222222 2222222222222 2 222.222 222 H
/ . / . . ./2 // / . / ./ 2 /
22 222 22 222222222 2222 2

/ . // // . /

2222222222 2 2
2

 

.// // / 2 .
2222222222 / 22222222222222 2 2 2
22222222222222 222/22222222222222

 

_ . 2 2
22.22222222222222222/222222.22,22222222222222/2222222

Figure 7d.

 

22
2

/

      
 

222/22222/2

 

22222222222222 /2
2

 

 

 

 

 

 

’2

2 %%/2

\\\\\\\\\
\\\\\\\\\\

\\
\\
\\
\\\§\\

\\
\\

\\
\\

\\
\\\
\\\\\\\\
\\\\\\\\\

\\\\\\\\\
\\\\

\\

2

   
 
 

22222222222

\\

\\

 

 

 

 

22

     

2222222222

22222222

/

222% 2

222 //2

2/
2

2

22

/2

2
22222222222222

22

2

//22

 

 

 

 

 

  
       

                     

2222/ 22. 2 2 22222222222
@2222 /%/22M22227/ fl/W/mw% H22

     

  

  

 

  

22/ 2222222. //2222. . H 2222 /2/
2 222/2222:: 22.2. . / /. 22

/ .2 . . / / .
/ 2 / / 2 / / / // 2
222222222222222222 2
/ 2/22// 22/ 22 222 2222/ 2/2 222 2
2222222 2/ 2222/2. 22222222222 22
/ 22222222 .2 2 2222/ 2222222222222
2/2 2 2 2 /2/222/// 22222222222222. 2
22 22222222262222 22222222222 //

2222 222/222 . /// 22/2/222222222222222/

2. 22222. / 22222 2222/ 222222222222/222 2
2222222222 222/22222222222222.2222 H

  

 

 

54

 

     

 

 

    

/////// . /
2//2%

2///////////

22//

 

 

 

%/

////

 

/

 

22/

/2
//22/

22 2,

22 2222222

22222222222222

2

/

 

e

V:

U

IL 9
\blw“‘ ..I
F

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

22/////2/’///

 

x
;
§

 

\\

 

 

 

 

 

 

2/

 

 

m

 

\\

\ x
\
\

s
s
\s
$

Vv
S
s
s
s
s

 

/

V // / ///

222222222 // 227///7
//////// ///////
V/////// ////////
//////// //// ///
222272 22222
222222 222222
/////// 7 '//////
////// / . .//////
2222222/ 272%
2722/;/ .2222
222227 22222
2222222' 222222
2m22 22 22 222
222722 227222
222227' 2222
2222'// >422222
2222 /. .. yé2222
22222222 2/222272
2222222 22222222
2%222’7222222722'22722
///// Z%/////////4%%' //////
////// ,%2/////////,A/ //////
2722/ 2222222222 22222
22222 222222222/222222»
22222222222222722222222

Q \
\ \\\\\
\Q\
\\ \>‘\
\Qx
QQx
\®v\
\\5\§
_\\\
\V‘
‘\\Q
\XA
\
\\
\\
\\
\\
\\
\ \
\\
fix
$
Qx
%
$
$
\é
\
<5
$
$
\

\\ \\§\T‘
\\
%v
Q%
$Q
Qx

\
$$
\\
2.$Q
$$
%v
%Q
$$
$Q
QQ
Qv
QQ
$$

$

$
Q\
\\
\\
\\
\\
Q>
$§
QQ\
$$\
\®i
%
$§
\%
\%
\Q
\Q
\%
\$
QQ
$§\
\\

72 2 2' ,2
2’////2
22222
77772
27/222222

/222222
/222277777
2/222222222
.2 222222222
277777777777
//2 /222222
/§2// 222222

+
\\\ \1

it
\\
\\
Q
\\
\
\\ w
§
\
\
\~
\
fib

%+
Q
Q
\
E
$
$
Q

\
\
S
s
s
s
%
$
\

  
 
 
 
 
  
  
   
  
    
 
   
    

/ .

   
   
    
   
  

 

 

Figure 10d.

~

 

 

 

 

 

/ I

l
L_ /2,// ,, /2
Figure 11a.

   

 

 

 

 

 

\

 

 

 

 

 

6S

 

 

   

2222., 2222222222/// 2222222222222 _ , ,
2222222222222. . _ 2/ 222222222222 ./
////////// 2 2.///////////
2222222 2/ ..... / 2222222222. . .
2222222222 2. . . . 2 2 2222222222V
22222222222 _ _ . 222/2222222222222
22222222 /2 _ _ ./2222222222222222
22222222.//2/2/ . . 222222222222222
222222222 / 22 . . 222222222222222
222222/2 / 22
2/

2 2222/ 22222222222222 /2222
////72/,fi//2 .../////////.. 7/
fl///2 . / 22222. / 7//
222222222222/ 2 2222 22222 222 22
2/22/2222/22/2222/ . . . /22/2 / 2
2222/2 22222222 2222
///22 2 . 2222
22 22
2/
2/
//
/2

                                 

   

      

  

/
/2/

      
       

7 , 22

H M 222222

//2/2 . .
2227/22/27 . . . 222
2222222 222/2
7222/22/ 222 /

2222222222/27 “2222/2222 22/ 2 ,

. . . . . . . . / .2 .2
22222 722/ g/ ./ 22222222 2. ..
222222222222 2222222... 222222222/ 222
22222222/2222 2 2 2

/
. 2 . . 22222222 22 22222
/2 /2/22222222222222222
2 222

    

 

22222222 .
222222222/ 22222222222

/ 2222 2
2222222222 2 . . . 2.2222222222222222 .
222222222222 _ . I /2/22222222222 /
222222222222/ 2 2222222222/
2,22222222222272222222222222227

   
  

IIIIIIIIIIII

 

 

 

Figure 11d.

 

l0.

ll.

l2.

REFERENCES

B.E.A. Saleh and 5.1. Sayegh, "Reduction of errors of microphoto—
graphic reproductions by optimal corrections of original masks,"
Opt. Eng., Vol. 20, p. 781-784, Sept. l98l.

Eastman Kodak Co., Techniques of Microphotography. Publications
No. P-52, Rochester, New York, I967.

G.N.w. Stevens, Microphotography, Butler and Tanner, London, 1968.

L;

.M. Ortega and w.c. Rheinboldt, Iterivative solution of nonlinear
equations in several variables, Computer Science and Applied
Mathematics.

. Papoulis, ”A New Algorithm in Spectral Analysis and Bandlimited
Extrapolation,“ IEEE Trans. Circuits Syst. CAS-22, 735 (l975).

3;

'50

.J. Marks II, "Gerchberg's Extrapolation Algorithm in Two Dimension,”
IEEE Trans. Applied Optics, Vol. 20, No. lO, l8l5 (l98l).

W

.W. Shafer, R.M. Mersereau and M.A. Richards, "Constrained Iterative
Restoration Algorithms," Proceedings of the IEEE, Vol. 69, No. 4,
432, April l98l.

L;

.H. McClellan and T.w. Parks, ”Eigenvalue and Eigenvector Decomposition
of the Discrete Fourier Transform,” IEEE Trans. Audio and
Electroacoustics Au-ZO, No. l, (66) March l972.

<

.T. Tom, T.F. Quatieri, M.H. Hayes and J.H. McClellan, ”Convergence
of Iterative Nonexpansive Signal Reconstruction Algorithms”
IEEE Trans Accoustics, Speech and Signal Processing, ASSP-29,
No. 5, (1052) October l98l.

(f)

.I. Sayegh and B.E.A. Saleh, ”Image Design: Generation of a
Prescribed Image at the Output of a Band-Limited System," IEEE
Trans. Pattern Analysis and Machine Intelligence, Vol. PAMI-5
No. 4, (44l) July l983.

Kuhn, Harold w., "Solvability and Consistency for Systems of Linear
Equations and Inequalities," The American Mathematical Monthly,
April l956, Vol. 63, No. 4, P. 217-232.

Jackson, James R., "On the Existence Problem of Linear Programming”,

Pacific Journal of Mathematics, March l954, Vol. 4, No. l, P.
29-36.

66

 

l3.

l4.

l5.

l6.

l7.

l8.

T9.

20.

67

Blumenthal, Leonard M., "Two Existence Theorems for Systems of Linear
Inequalities", Pacific Journal of Mathematics, Dec. 1952, Vol. 2,
No. 4, p. 523-53l.

Gaddum, Jerry M., ”A Theorem on Convex Cones with Applications
to Linear Inequalities," Proceedings of the American Mathematical
Society, Dec. 1952, Vol. 3, No. 6, l957-960.

Motzkin, Theodore S., "The Probability of Solvability of Linear
Inequalities," Proceedings of the Second Symposium in Linear
Programming, Vol. II.

L.R. Rabiner and Bernard Gold, Theory and Application of Digital
Signal Processing, New Jersey: Prentice Hall, Inc., 1975.

Joseph W. Goodman, Introduction to Fourier Optics, New York:
McGraw-Hill, l968.

Alan V. Oppenheim and Ronald w. Schafer, Digital Signal Processing,
New Jersey: Prentice-Hall, Inc., l975.

Soheil I. Sayegh, “Image Restoration and Image Design in Nonlinear
Optical System," Ph.D. thesis at the University of Wisconsin-
Madison, l982.

Michigan State University Computer Laboratory, ”Plotting and Graphics
Reference Manual”, l979.