Prof. Dr.-Ing. A.

Bruhn
Institute for Visualization and Interactive Systems
Computer Vision Group
University of Stuttgart

Imaging Science – Solution for Self-Test Problems

1
Problem 1 (Fourier and Wavelet transform)

(a) Direct application of the Fourier transform equation gives

 
fˆ0 = √18 1f0 + 1f1 + 1f2 + 1f3 + 1f4 + 1f5 + 1f6 + 1f7
 
fˆ1 = √18 1f0 + 1−i
√ f1 + (−i)f2 + −1−i
2
√ f3 + (−1)f4 + −1+i
2
√ f5 +
2
if 6 + 1+i
√ f
2 7
 
fˆ2 = √18 1f0 + (−i)f1 + (−1)f2 + if3 + 1f4 + (−i)f5 + (−1)f6 + if7
 
fˆ3 = √18 1f0 + −1−i
√ f1 +
2
if 2 + 1−i
√ f
2 3
+ (−1)f 4 + 1+i
√ f
2 5
+ (−i)f 6 + −1+i
√
2 7
f
 
fˆ4 = √18 1f0 + (−1)f1 + 1f2 + (−1)f3 + 1f4 + (−1)f5 + 1f6 + (−1)f7
 
fˆ5 = √18 1f0 + −1+i
√ f1 + (−i)f2 +
2
1+i
√ f3 + (−1)f4 +
2
1−i
√ f5 +
2
if 6 + −1−i
√
2 7
f
 
ˆ √1
f6 = 8 1f0 + if1 + (−1)f2 + (−i)f3 + 1f4 + if5 + (−1)f6 + (−i)f7
 
ˆ √1
f7 = 8 1f0 + 1+i
√ f + −1+i −1−i
if2 + 2 f3 + (−1)f4 + 2 f5 + (−i)f6 +
√ √ 1−i
√ f
2 1 2 7

and therefore
√
fˆ0 = 17
2
2 ≈ 12.02081528
√
√
fˆ1 = − 52 + 23 2 + 3
2
2i ≈ −0.37867966 + 2.12132034i
√ √
fˆ2 = − 21 2 + 1
2
2i ≈ −0.70710678 + 0.70710678i
√
√
fˆ3 = 5
2
+ 2
3
2 − 3
2
2i ≈ 4.62132034 − 2.12132034i
√
fˆ4 = 1
2
2 ≈ 0.70710678
√
√
fˆ5 = 5
2
+ 2
3
2 + 3
2
2i ≈ 4.62132034 + 2.12132034i
√ √
fˆ6 = − 21 2 − 1
2
2i ≈ −0.70710678 − 0.70710678i
√
√
fˆ7 = − 25 + 23 2 − 3
2
2i ≈ −0.37867966 − 2.12132034i

The highest frequency is represented by the coefficient fˆ4 . Elimination and back-
transformation (analogous to forward transform, with complex conjugate coefficients)
yields
 27 5 7 29 3 25 31 9 
f˜ = , , , , , , ,
4 4 4 4 4 4 4 4
≈ (6.75, 1.25, 1.75, 7.25, 0.75, 6.25, 7.75, 2.25) .

2
(b) Starting from

c0,0 = 7, c0,1 = 1, c0,2 = 2, c0,3 = 7, c0,4 = 1, c0,5 = 6, c0,6 = 8, c0,7 = 2

we use the formulae from Lecture 6 to compute

√ 9√ 7√ √
c1,0 = 4 2, c1,1 = 2, c1,2 = 2, c1,3 = 5 2,
2 2
√ 5√ 5√ √
d1,0 = 3 2, d1,1 =− 2, d1,2 =− 2, d1,3 = 3 2,
2 2
17 17
c2,0 = , c2,1 = ,
2 2
1 3
d2,0 =− , d2,1 =− ,
2 2
17 √
c3,0 = 2,
2
d3,0 = 0.

The wavelet representation consists of the scaling coefficient c3,0 and the seven wavelet
coefficients, i.e.

(c3,0 , d3,0 , d2,0 , d2,1 , d1,0 , d1,1 , d1,2 , d1,3 )

17 √ 3 √ 5√ 5√ √
 
1
= 2, 0, − , − , 3 2, − 2, − 2, 3 2
2 2 2 2 2
≈ (12.02081528, 0, −0.5, −1.5,
4.24264069, −3.53553391, −3.53553391, 4.24264069)

The wavelet coefficient with smallest absolute value is d3,0 which is already zero. There-
fore nothing changes by eliminating it. The back-transform therefore reproduces exactly
the above values cj,k and finally restores the original signal.

3
Problem 2 (Derivative Filter)

(a) As usual we abbreviate the derivatives of f at pixel i by fi0 , fi00 , . . . Substituting the
Taylor expansions

fi−3 = fi − 3hfi0 + 9 2 00
2
h fi − 9 3 000
2
h fi + 27 4 0000
8
h fi + O(h5 )
fi−2 = fi − 2hfi0 + 2h2 fi00 − 4 3 000
3
h fi + 2 4 0000
3
h fi + O(h5 )
fi−1 = fi − hfi0 + 1 2 00
2
h fi − 1 3 000
6
h fi + 1 4 0000
24
h fi + O(h5 )
fi = fi

into an ansatz
fi00 = α−3 fi−3 + α−2 fi−2 + α−1 fi−1 + α0 fi
and neglecting the higher order error terms, we obtain

fi00 = (α−3 + α−2 + α−1 + α0 )fi

+ (−3α−3 − 2α−2 − α−1 )hfi0
+ ( 29 α−3 + 2α−2 + 12 α−1 )h2 fi00
+ (− 29 α−3 + − 43 α−2 − 16 α−1 )h3 fi000
+ ( 27 α + 32 α−2 + 24
8 −3
1
α−1 )h4 fi0000

and by comparing coefficients the desired system of equations, in matrix notation:

  
1 1 1 1 α−3
 −3h −2h −h 0 α−2 

 9 2 1
   = 0 0 1 0
 h
2
2h2 2
h2 0 α−1 
9 3 4 3 1 3
−2h −3h −6h 0 α0

or equivalently
  
1 1 1 1 α−3
 −3 −2 −1 0 α−2  = 0 0 2h−2 0
 


 9 4 1 0 α−1 
−27 −8 −1 0 α0

If we solve this linear system of equations (this was not asked in the assignment), we
obtain the following filter coefficients:
1 4
α−3 = − , α−2 = ,
h2 h2
5 2
α−1 = − 2, α0 = .
h h2

4
(b) Note: If we compare the coefficients from part (a) with the given filter, we see that our
task is actually to determine the order of consistency of our filter derived in (a).

Plugging the Taylor expansions into the approximation and reordering the coefficients
gives
1 4 5 2
− 2
fi−3 + 2 fi−2 − 2 fi−1 + 2 fi
h h h h
1
= (−1 + 4 − 5 + 2) 2 fi
| {z }h
=0
h
+ (3 − 8 + 5 + 0) 2 fi0
| {z }h
=0
1 h2 00
+ (−9 + 16 − 5 + 0) 2 fi
| {z 2 h}
=1
1 h3 000
+ (27 − 32 + 5 − 0) f
| {z } 6 h2 i
=0
1 h4 (4)
+ (−81 + 64 − 5 + 0) f
| {z } 24 h2 i
=−226=0
3
+ O(h )
00 22 (4)
= fi − h2 fi + O(h3 )
24
00
= fi + O(h2 ) ,

which shows that the order of consistency of the approximation is 2.

5
Problem 3 (Variational Approaches)

(a) In analogy to the functional considered in (1), we write down a discrete version of
E(u1 , u2 , u3 ) as follows:
N 3 N −1 3
1 XX 2 α X X (uc,k+1 − uc,k )2
E(u1 , u2 , u3 ) := (uc,k − fc,k ) + .
2 k=1 c=1 2 k=1 c=1 h2

Here, we assume that the finite forward difference and the length of the signal f , i.e.,
N = b−a
h
, depend on the pixel distance h > 0, which is often set to 1 in practice.

(b) The minimiser of the discrete functional E(u1 , u2 , u3 ) necessarily satisfies the linear
systems of equations
∂E(u)
=0
∂uc,k
for all c = 1, 2, 3 and k = 1, . . . , N . Thus, we have to calculate partial derivatives for
each colour channel c = 1, 2, 3 distinguishing boundary pixels from inner pixels. This
yields

∂E(u1 , u2 , u3 ) uc,2 − uc,1

= uc,1 − fc,1 − α , (for k = 1),
∂uc,1 h2
∂E(u1 , u2 , u3 ) uc,k+1 − 2uc,k + uc,k−1
= uc,k − fc,k − α , (for k = 2, . . . , N − 1),
∂uc,k h2
∂E(u1 , u2 , u3 ) uc,N −1 − uc,N
= uc,N − fc,N − α . (for k = N ),
∂uc,N h2

for c = 1, 2, 3. Evidently, we obtain three linear systems of equations that can be solved
independently: one system for each colour channel.

6
Problem 4 (Morphological operations)

The correspondence is

(A) =
ˆ (1), (B) =
ˆ (3), (C) =
ˆ (2)

Image (A) shows a dilation. The bright areas of the owl spread such that only at the wings
small dark areas remain where large dark areas can be found in (O). Furthermore, the dark
circle in the background is shrinked as the bright area behind it spreads.

Image (B) shows a white top hat filter. It is clearly the difference between (O) and the
opening operation display in (C).

Image (C) shows the result of an opening operation. First, an erosion is applied such that
only the large and bright eyes of the owl remain as small dots. Then these small dots are
dilated again such that the eyes become as large as in the original image.