Transcript Convolution - University of Wisconsin–Stout

Origins and Interpretations of the Concept of
Convolutions
Presented
By
{
Craig Rykal
John Rivera
Justin Malaise
Jeff Swanson
Ben Rougier
From
{
University of Wisconsin
STOUT
Under the direction of Dr. Steve Deckelman
Abstract
The convolution of two functions is an important concept in a number of areas of
pure and applied mathematics such as Fourier Analysis, Differential Equations,
Approximation Theory, and Image Processing. Nevertheless convolutions often
seem unintuitive and difficult to grasp for beginners. This project explores the
origins of the convolution concept as well as some computer graphic and physical
interpretations of convolution which illustrate various ways the technique of
smoothing can be used to solve some real world problems.
Convolutions
F (t )   f ( x)k (t  x)dx
R
Convolutions can be thought of as a method of
averaging unruly functions.
Unruly Functions include:
• Functions with sharp or jagged edges
• Discontinuous functions
Origin of Convolutions
n
 y
Weighted Averages
j 1
Substitute
j
j
n
y  f (x) into the function to receive

j 1
n
Now we need

j 1
j
f (x j )
f (x j )
to return a function
Therefore we create a new function
n

j 1
Which returns a function
j
j
f (x  x j )
One more substitution of
Gives us the function:
 j  g j (x)
n
g
j 1
j
( x) f ( x  x j )
This function will give us a new discrete function, but we
need this function in continuous form
To accomplish this, change the function to an integration
This gives us:
 g (t ) f ( x  t )dt
R
Which is a Convolution!
Examples
Take the function
0 for x  -h

f ( x)  1 for  h  x  h
0 for h  x

Convolve the function with itself to receive the new function
0
t  2h

F (t )  
2 h  t
0
for
t  2h
for  2h  t  0
for 0  t  2h
for 2h  t
One more convolution gives use the continuous function
0

2
(
t

3
h
)
/2


G (t )   t 2  3h 2
(t  3h) 2 / 2

0
t  3h
 3h  t  h
h t  h
h  t  3h
3h  t
Convolutions are also useful in smoothing functions of more
than one dimension
F (s, t )   f ( x, y)k (s  x, t  y)dxdy
RR
Antialiasing
Aliasing
Blurred
Deconvolution
Radius of the Earth


A
Sun
Eratosthenes
Earth
  7.2
Length ( A)  787 KM
Circumference
c
230 B.C
Alexandria, Egypt
787 7.2

c
360 
767 * 360 
c
7.2
c
r
2
r  6103 .59
Figuring out the Distance of The Earth to the Sun
Using Parallax
Parallax - any alteration in the relative apparent positions of objects
SUN
produced by a shift in the position of the observer.
R = radius of Earth.
q = angle between observation points with relation to the center of the
Earth.
P & Q are observation points on the Earth.
X = distance between the center of the sun and the center of the Earth.
X
P
How To find the Distance:
If we know |PQ| =>
/
2
R/
X
|PQ| = Rq

q = |PQ| / R
 q  angle of center of sun to P & Q
= Cos (q)
=> X =
R/
Cos (q)
Q
q
= R(Sec (q)
The only problem is that there must be a very accurate measurement of q in
order to get an accurate distance. Hipparchus (130 BC) and Ptolemy (150 AD)
used the value of the diameter of the earth given by Eratosthenes ( 195 BC) and
estimated the distance to be 10 million miles. We know that the distance is 93
million miles away. Thus, even close but not precise values give huge errors.
R
Earth
The Diameter of a Star
WE SEE:

TRUE IMAGE(shape):
  (x inside disc)
f ( x)  
otherwise.
0
x0
f ( x)   D(
x  x0

)
Note: , x0,  are all unknown quantities.
Where D(x) is the characteristic function of the unit circle.
D( x)  1
for x  1,
D( x)  0
for x  1
Fundamental Problem:
Calculate  from f
The Photographic Plate

X
O
 
X Y

|| Y ||

Y
Let
 : “Brightness” at point source O
 ': “Brightness” at point source Y
 K t ( X ) : “Brightness” at X
 ' K t ( X  Y ) : “Brightness” at X arising from point source Y.
K t ( X ) : Apparent Brightness (At time t)
True Brightness
We Get:
n
A(x) " Brightnessat X"    j K t ( X  Y j )
 ,  ,...,n 
1
2
Y ,Y
1
2
j1
“Brightness” of Yj given point sources
,...,Y n 
Point sources of light
||Y || ,||Y || ,...,||Y ||n 
1
2
Given are very small
Let’s pass from discrete to the continuous model:
n
 K ( X
j 1
j
f (Y ) :
dA(Y ) :
t
 Y j)
to
 f (Y ) K ( X  Y )dA(Y )
Brightness at point Y.
Kt (X
Integrate with respect to Y.
TRUE IMAGE(brightness) = f(x)
ACTUAL IMAGE = f*Kt
t
 Y ) : Blurring
effect(kernel) of
the atmosphere at
time t.
earth
q
1 a.u. = distance from the sun to the earth
q is found experimentally
sun
star
1 a.u.
d
q
earth
d = sec(q)
Knowing d and  will allow us to find the
diameter of the star.
The Fundamental Problem:
Extract f from f*Kt where Kt
is an unknown random function.
Labeyrie’s Idea:
Use Averaging and Fourier Transforms
1. Averaging Kt:
To get a fixed Kt or the “Average Blur”:
Average the image received at various times,
~
K 1 K
t (1), t (2),...,t (n)
n
j 1
n
t( j)
: AVERAGE BLUR
Average the Convolutions,
n
~
1
1 n

f
*

f * K t( j)
K t( j)  f * K

n
j

1
n j 1
2. Using the Convolution Theorem for Fourier Transforms:

 f * K t : FOURIER TRANSFORM of our image(convolution)
t



t
 f

K
t
: Under the Convolution Theorem for Fourier Transforms

Take the sequence:


 , ,
t (1)
t ( 2)

t ( 3)
,...,
t (n)


t( j)
is RANDOM, due to Kt being RANDOM.

The only zeros(roots) the

t( j)
‘s


will have in common with all other

‘s
t( j)
Are the zeros of

Superimposing

t( j)
n
forms

(ζ)   

Clearly the zeros of
j 1
n
t( j)
(ζ)   f (ζ)
f (ζ )
Will stand out as the zeros of

(ζ )
j 1

K
t( j)
f
!

x  x0  2 π iζ x
f (ζ )    D(
)e
dA( x)
ε
2

Substitute y = x – x0

y  2π i(y  x )
f (ζ )    D( ) e
dA( y )
ε
2
0

Move out the constants

f (ζ )  
e
 2 π i ζ x0
y  2 π iζ y
2 D( ε ) e dA( y)

Substitute w = y/ , y = w

f (ζ )  
2 π i ζ x0
εe
2
2 π iζ ε w
 D(w) e
dA( w)
2

By the definition of Fourier Transforms
2 π iζ ε w
 D(w) e
2


dA( w)  D(εζ)

f (ζ)  
2 π i ζ x0 
εe
2
D(εζ)

We see that the zeros of

f (ζ ) Are the same as the zeros of D(εζ )
TO COMPUTE , we need to know the location of the rings of zeros of

D(εζ)
The zeros occur on the circle of radius z = r0,
i.e.

D (εζ )  0
When z = r0
Which should be visually evident from our

D (ζ ) 
 picture.
2π J 1 ( ζ )
ζ
Where J1 is the first order Bessel function
3
5
7
9
x
x
x
x
x
J 1 ( x)  2  231!2!  25 2!3!  27 3!4!  29 4!5!    
The zeros Occur on the circle of radius z = r1

i.e. D (ζ )  0
When z = r1
NOTE: r1 can be found analytically.
So If


D (ε r 0 )  0
then
D ( r1)  0
and
ε r r
0
And thus
r
ε
r
1
1
0
Accuracy:
• Labeyrie’s method gives results consistent to
Michelson’s interferometer results.
• The method has been applied to over 30 stars already.
References
• “Fourier Analysis” by T.W. Korner,
Cambridge University Press, 1988
• “Convolutions and Computer Graphics”
by Anne M. Burns, College Mathematics
Journal, 1992
• Dr. Steve Deckelman