filter - Technische Universiteit Eindhoven

Video processing
for multimedia systems
G. de Haan
technische universiteit eindhoven
W
2
Schedule lectures 5P530
Week 1
Week 2
Week 3
Week 4
Basics
(Ch 2, 3)
Filtering
(Ch 4)
Video Enhancement
(Ch 5)
Picture-Rate
Conversion (Ch 7)
Week 5
Week 6
Week 7
Week 8
De-interlacing
(Ch 8)
Motion Estimation
(Ch 10)
Object Detection
(Ch 11)
X
technische universiteit eindhoven
W
2
3
Arithmetical
operations on
discrete images
technische universiteit eindhoven
W
3
4
What if we average an image with a shifted version?
=
Original image
2 pel shifted image
average image
•A frequency is suppressed if we shift over
180 degree.
+
•Therefore, the frequency has a complete
cycle of 4 pixels
•In other words, suppression occurs at a
quarter of the sampling frequency
technische universiteit eindhoven
W
4
=
2 pel
5
What if we subtract an image with a shifted version?
Averaging with a 2
Original image
pel diagonally
shifted image
•Subtraction suppresses DC (coarse spatial
detail
Subtraction with a
2 pel diagonally
shifted image
=
•A frequency with a complete cycle of 4
pixels doubles in amplitude
•In other words, enhancement occurs at a
quarter of the sampling frequency
technische universiteit eindhoven
W
5
2 pel
6
Linear filtering of
discrete images
technische universiteit eindhoven
W
6
7
What is a linear filter?
•
A linear filter is a system with an input and an output that:
•
Contains delays, multipliers and adders
• Connected such that the output results as a weighted sum of
delayed copies of the input signal and the output signal
technische universiteit eindhoven
W
7
8
Example linear filter
Input
w1
delay
delay
w3
w2
sum
y[k ]   wn x[k  n]
n
technische universiteit eindhoven
W
8
delay
w4
Output
9
Simple notation
•
•
We shall assume that a (1, 2, 1) filter outputs a weighted sum of
horizontally neighbouring pixels in an image
 1
 
We shall assume that a  2  filter outputs a weighted sum
 1
 
of vertically neighbouring pixels in an image
•
Vertically shifting the image requires a line-delay
• Orders of magnitude more expensive than a pixel-delay
•
Analogously, temporal filtering requires picture-delays
• Again orders of magnitude more expensive
technische universiteit eindhoven
W
9
10
From horizontal to vertical filtering
•
•
If we increase the delay from 1 to # pixels/line, the pixels
combined in the filter output are vertical neighbours
A delay is now implemented with a “line-memory”
Input
¼
Line delay
0
Line delay
½
sum
technische universiteit eindhoven
W
10
Line delay
¼
Output
11
What if we re-use output samples? Recursive filtering
Input
w1
delay
delay
w3
w2
delay
w4
Output
sum
wr4
delay
wr3
wr2
delay
wr1
delay
y[k ]   wn .x[k  n]   wmr . y[k  m]
n
m
technische universiteit eindhoven
W
11
12
Calculating with
impulse
responses
technische universiteit eindhoven
W
12
13
Some impulse responses
(1,2,1)
(1,1)
 1 1 1


 1 1 1
 1 1 1


Single white
pixel input
1
 
 0
1
 
(1,0,1)
technische universiteit eindhoven
W
13
The cascading of two (1, 1) filters
14
1
A
time
A
½
½
time
A
¼
1
½
¼
1
1
1
------------------------------ +
1
2
1
technische universiteit eindhoven
W
14
time
15
Simple calculation of impulse response of cascade
•
•
Cascade of (1,1) and (1, 1):
•
•
•
•
•
•
•
•
1
1
1
1
-------------------1
2
1
technische universiteit eindhoven
W
Cascade of 121 and 11:
15
1
2
1
1
2
1
--------------------------1
3
3
1
16
Simple calculation of impulse response of cascade
•
Cascade of 11 and 101
1
1
0
0
1
1
---------------------------1
1
1
1
•
¼ fs
Cascade of 121 and 121 (cascade of 11 and 11 and 11 and 11):
1
1
4
2
1
2
1
----------------------------------1
4
6
4
1
2
2
¼ fs
technische universiteit eindhoven
W
½ fs
16
½ fs
17
Simple calculation of impulse response of cascade
•
1
Cascade of (horizontal) 11 and a(vertical)  
1
1
1
•
1
1
 1
 
Cascade of (horizontal) 121 and a (vertical) 2 
 1
 
1
2
1
2
4
2
1
2
1
technische universiteit eindhoven
W
17
18
Qualitative
analysis of linear
filters
technische universiteit eindhoven
W
18
19
Qualitative filter behaviour in the frequency domain
Transfer of filter
Spectrum input image
A
H
A

0
f
f
f
f
Band-pass
=
f
0
technische universiteit eindhoven
W
0
A

f
High-pass
=
0
H
A
f
A

0
0
H
f
Low-pass
=
0
A
0
Spectrum of output image
19
0
f
20
Filtering images
•
Move the coefficient matrix (impulse response) over each
pixel in the image, multiply the entries by the pixels, and
sum together
•
•
•
E.g. 3x3 “box”-filter
Effect is averaging
1 1 1
1
1 1 1

9
1 1 1
Formal name for this procedure is convolution of the
image data with the filter “mask” or “kernel”
technische universiteit eindhoven
W
20
21
Illustration of 1D convolution (box filter and block
pattern)
technische universiteit eindhoven
W
21
22
Effect of the box filter on a natural image
Original (input)
Box-filter output
technische universiteit eindhoven
W
22
23
1 1 1
1
1 1 1

9
1 1 1
Box Filter
•
•
•
Box filters smooth by averaging neighbouring pixels
In the frequency domain, the box-filter leaves low
frequencies unaltered and attenuates (reduces) high
frequencies
So, the box filter is clearly a low-pass filter
A
0
Spatial: Box
H
0
pos
Frequency domain: sinc-function
technische universiteit eindhoven
W
f
23
24
What about the image boundaries?
Foutput[ x][ y ] 
•
k /2
k /2
 F
i  k / 2 j  k / 2
input
[ x  i ][ y  j ]w[i  k / 2][ j  k / 2]
At (0,0) for instance, you need pixel data for (-1,-1),
which doesn’t exist
•
Option 1: Make the output image smaller – don’t evaluate pixels
you don’t have all the input for
•
Option 2: Replicate the edge pixels
• Equivalent to: pos = x + i; if ( pos < 0 ) pos = 0; same for y
•
Option 3: Reflect image about edge
• Equivalent to: pos = x + i; if ( pos < 0 ) pos = -pos; same for y
technische universiteit eindhoven
W
24
25
1
2
1 
3
81 
2
1
Bartlett Filter
•
•
•
Triangle shaped filter in spatial domain
Cascade of two box filters
So in frequency domain; attenuates high frequencies
more than a box-filter
A
0
H
0
pos
Spatial: Triangle (BoxBox)
technische universiteit eindhoven
W
25
Frequency: sinc2
f
2 3 2 1
4 6 4 2

6 9 6 3

4 6 4 2
2 3 2 1
26
Effect of the Bartlett filter on a natural image
Original (input)
Bartlett-filter output
technische universiteit eindhoven
W
26
27
High-pass filters
•
A high-pass filter can be obtained from a low-pass filter
•
•
•
If we subtract the smoothed image from the original, we
must be subtracting out the low frequencies
What remains must contain only the high frequencies
High-pass masks come from matrix subtraction:
•
eg: 3x3 Box:
0 0 0 
1 1 1
 1  1  1
0 1 0  1 1 1 1  1  1 8  1

 9
 9

0 0 0
1 1 1
 1  1  1
technische universiteit eindhoven
W
27
28
Effect of the high-pass filter on a natural image
Original (input)
High-pass filter output +128
technische universiteit eindhoven
W
28
29
Edge Enhancement
•
High-pass filters give high values at edges, low values in
constant regions
•
Adding high frequencies back into the image enhances
edges
•
Possible approach:
•
Image = Image + [Image – smooth(Image)]
Low-pass
High-pass
technische universiteit eindhoven
W
29
30
Effect of the edge-enhance, or peaking, filter
[]
-1 -1 -1
-1 12 -1 x1/4
-1 -1 -1
technische universiteit eindhoven
W
30
31
Edge enhancement, peaking, or unsharp masking
technische universiteit eindhoven
W
31
32
Negative filter coefficients may lead to problems!
•
The negative values in high-pass filters can lead to
negative image values
•
Most image formats don’t support this, and if they do, we
cannot image negative light from the display….
•
Also, the boosting effect on high frequencies may lead to
values higher than peak-white
•
Solutions:
•
•
•
Clipping: Chop off values below min or above max
Offset: Add a constant to move the min value to 0
Re-scale: Rescale the image values to fill the range (0,max)
technische universiteit eindhoven
W
32
Video processing
for multimedia systems
G. de Haan
technische universiteit eindhoven
W
34
The purpose of
filters
technische universiteit eindhoven
W
34
35
Purpose of filters
•
•
•
•
Removal of spectral components
•
E.g. for alias prevention, or removal of interference signal
Enhancement of spectral components
•
Edge/feature enhancement
Removal of noise
•
Balance between noise suppression and suppression of
relevant image components
Interpolation
•
Image up- and down-scaling, geometrical deformations
technische universiteit eindhoven
W
35
36
Noise removal
V-LPF
H-LPF
technische universiteit eindhoven
W
36
37
Alias prevention
technische universiteit eindhoven
W
37
38
Filtering and image
re--sizing (1D case)
re
technische universiteit eindhoven
W
38
39
The simple way. Pixel repetition and dropping.
Original pixels:
1
Required lower
density grid:
1
Required higher
density grid:
1
2
3
2
1
2
4
5
3
3
3
4
4
Repeated pixels!
technische universiteit eindhoven
W
39
6
4
7
6
5
6
8
9
7
7
7
8
8
8
9
Drop pixel 5!
40
Spatial scaling
Scaled using
pixel repetition
and pixel
dropping
Scaled with
proper filters
technische universiteit eindhoven
W
40
41
2 tap linear interpolation
•
The filter size is 2, and we need a sample at x=4.75
•
We need the filter output, F(x), from x=4, x=5
•
We need the filter coefficient, H(s), at s=-0.75, and s=0.25
•
We compute: F(4)*H(-0.75)+F(5)*H(0.25)+F(6)*H(1.25)
•
Result is: 0.25F(4) + 0.75 F(5)
1.0
0.75
0.25
4
5
x
technische universiteit eindhoven
W
41
42
Interpolation with the Bartlett filter
•
•
•
Place a Bartlett filter at the required position
Multiply the value of the neighbouring pixel by the
corresponding filter value, and accumulate the result
•
Convolution with discrete samples
The filter size is a parameter
4
•
6
Assume the filter size is 3, and we need a sample at x=4.75
•
We need the image samples, F(x), from x=4, x=5 and x=6
•
We need the filter value, H(s), at s=-0.75, s=0.25 and s=1.25
•
We compute: F(4)*H(-0.75)+F(5)*H(0.25)+F(6)*H(1.25)
technische universiteit eindhoven
W
5
42
x
43
What are the effects of the filter length?
technische universiteit eindhoven
W
43
44
This was an example
Does theory provide any requirements
for the interpolation filter?
technische universiteit eindhoven
W
44
45
Re-sampling
•
Making an image larger is like sampling the original signal at a higher
density
•
You need more pixels to represent the same thing, so a higher pixel density
should result from the procedure:
Original
•
•
•
•
More samples
Reducing an image in size is like sampling at lower density
Generating new samples of the “same” function is called re-sampling
In theory, 2 steps:
•
•
Reconstruction of the continuous signal
Followed by sampling with the new sampling frequency
In practice: sample rate conversion in the discrete domain
technische universiteit eindhoven
W
Original spacing = bigger
45
46
The sampling theorem
0
fs
2
fs frequency
Ts
time
We have a continuous signal
We sample it to obtain a discrete representation
Sampling theorem: we can reconstruct the continuous signal
from its discrete representation, provided it contained no
frequencies above half the sampling frequency
technische universiteit eindhoven
W
46
47
The general principle of sample rate conversion
Input
grid
interpolator
Intermediate
grid
decimator
Output
grid
Sampling-rate converter
As a consequence of the time-discrete nature of the processing,
the input and output sampling frequency have a rational relation.
Output results from an integer up-sampling and an integer sub-sampling
technische universiteit eindhoven
W
47
48
Spectra in sampling rate conversion (down-sampling)
Input
0
fs1
2fs1
frequency
Repeat on output rate will overlap
with base-band…
Output 1
0
frequency
fs2
Alias!
…unless the interpolating LPF
suppresses part of spectrum
Output 2
0
frequency
fs2
technische universiteit eindhoven
W
48
49
Signals in sample rate conversion (down-sampling)
input
Interp.
output
technische universiteit eindhoven
W
49
50
Spectra in sample rate conversion (up-sampling)
Input
0
fs1
2fs1
Repeats at input rate must be
suppressed without suppressing
base-band…
Intermed.
0
fs2 frequency
…to prevent alias or blur at
output rate
Output
0
fs3
technische universiteit eindhoven
W
frequency
3fs1
50
frequency
51
Signals in sample rate conversion (up-sampling)
input
Interp.
output
technische universiteit eindhoven
W
51
52
Requirements for the interpolation (scaling) filter
F(nT)
Input signal
Output signal
Interpolation
filter
1
2
3
4
nT
1 2 3 456 7 8
•
Up-sampling: LPF passes base-band signal and suppresses the
input repeat spectra where possible at intermediate rate
•
Down-sampling: LPF suppresses part of the base-band and
repeat spectra to avoid folding into the new base-band output
spectrum
technische universiteit eindhoven
W
52
nT
53
Poly-phase filtering: the filter is designed at the intermediate
frequency, at the output frequency a varying set of coefficients
is used
C-6 C-5 C-4 C-3 C-2 C-1 C0 C1 C2 C3 C4 C5 C6
C-6 C-5 C-4 C-3 C-2 C-1 C0 C1 C2 C3 C4 C5 C6
technische universiteit eindhoven
W
53
54
Poly-phase filtering
Original
pixels:
1
2
a X
4
3
b X
c X
5
6
7
d X
e X
f X
8
9

Required pixel on
other density grid:
4 n 5
The filter coefficients, a b c d e f.., depend on
the position of the required pixel n
technische universiteit eindhoven
W
54
55
Application:
Aspect ratio
conversion
technische universiteit eindhoven
W
55
56
4:3 image on a wide-screen (16:9) picture tube
Linear scaling options:
Accept side-panels
Accept geometrical distortion
technische universiteit eindhoven
W
56
57
4:3 image on a wide-screen (16:9) picture tube
Non-linear scaling options:
Panorama view
Accept geometrical distortion
technische universiteit eindhoven
W
57
58
Wide-screen image on a 4:3 picture tube
Linear scaling options:
Accept letter-box
Geometrical distortion
technische universiteit eindhoven
W
58
Partial image loss
59
Wide-screen image on a 4:3 picture tube
Non-linear scaling options:
Amaronap view
technische universiteit eindhoven
W
59
Options in wide-screen conversion
magnification
60
1.33
Distortions
concentrated
in side panels
Distortions
evenly distributed
Usually magnification between 0.5 and 2.0
Panorama
Constant horizontal stretch
1.0
0.75
Constant horizontal compress
Amaronap
Horizontal position
technische universiteit eindhoven
W
60
Video processing
for multimedia systems
G. de Haan
technische universiteit eindhoven
W
62
Non-linear
Nonfilters
technische universiteit eindhoven
W
62
63
Different filter types
•
Linear filters
•
Rank-order filters
•
Hybrid filters
•
Morphological filtering
•
Adaptive filters
technische universiteit eindhoven
W
63
64
Linear filters not very effective against shot noise
•
Linear filters fine in case small
noise values are more frequent than
high noise values
•
•
Shot noise (salt and pepper
noise,..) is characterized by
relatively few extreme noise values
and (almost) no small noise values
•
•
E.g. Gaussian noise
E.g. impulses from ignition of
combustion engines, or film defects
To know if a pixel is extreme we
have to rank adjacent pixel values
technische universiteit eindhoven
W
64
65
Linear and rank-order filters – The difference
This is what a linear filter outputs:
y  w1 x1  w2 x2  ....  wn xn
Let the filter support (vector) define the input pixels used:
S( x)  ( x1 , x2 ,...., xn ) T
and the coefficient vector defines the weighting:
W  ( w1 , w2 ,...., wn )
Now we can briefly define the filtered output pixel as:
y( x)  W.S( x)
technische universiteit eindhoven
W
65
66
Linear and rank-order filters – The difference
So, the linear filter is defined as:
y( x)  W.S( x)
If we now define the ordered (ranked) support:
S r ( x)  ( x(1) , x( 2) ,...., x( n ) ) T
with:
x(1)  x( 2)  ....  x( n )
Then the rank-order filter is defined by:
y( x)  Wr .S r ( x)
technische universiteit eindhoven
W
66
67
Linear and rank-order filters – The difference
•
The pixel-weights in a linear filter are determined by the spatiotemporal position of the pixel relative to the output position
•
The pixel-weights in a rank-order filter are determined by the
rank number of the pixel after ordering all values in the support.
Examples:
•
•
•
•
•
minimum,
maximum,
midpoint = (max + min)/2
median,
α-trimmed mean
technische universiteit eindhoven
W
67
68
Effectiveness against shot noise
3x3 box
Original
3x3 median
Median filter, especially effective for shot noise:
y ( x)  Wmed .S r ( x)
Wmed  (0,....... 1,......., 0)
technische universiteit eindhoven
W
68
69
Less extreme distributions: The α-trimmed-mean filter
The general rank-order filter is defined by:
y( x)  Wr .S r ( x)
The median filter, especially effective for shot noise:
Wmed  (0,....... 1,......., 0)
The α-trimmed-mean filter, long-tail distributed noise, but less extreme:
W  (0,....... 0,1,1,1,1,1,0......., 0)
α-central pixels
are averaged,
extremes ignored
technische universiteit eindhoven
W
69
70
Shot noise + Gaussian noise reduction
Original
3x3 median
3x3 box
3x3 -trimmed mean
technische universiteit eindhoven
W
70
71
Combination of linear and rank-order: The hybrid filter
If we concatenate the linear and ranked supports:
S h ( x)  ( x1 , x2 ,...., xn , x(1) , x( 2) ,...., x( n ) ) T
and also the coefficient vectors defines the weighting:
Wh  ( w1 , w2 ,...., wn , wr1 , wr 2 ,...., wrn )
Then the hybrid filter is defined by:
y ( x)  Wh .S h ( x)
•LMS-optimization is possible to find coefficients
technische universiteit eindhoven
W
71
72
Combination of linear and rank-order: The bilateral filter
In the linear filter, weights depend on position relative to centre:
wk  f1 (c  k )
In the rank-order filter, they depend on the “similarity” with current pixel:
wk  f 2 (| xk  xc |)
In the bilateral filter the weight is defined by:
wk  N . f1 (c  k ). f 2 (| xk  xc |)
Where N is selected such that the sum of the coefficients is 1
Functions f1 and f2 may be e.g. Gaussian or triangular functions
technische universiteit eindhoven
W
72
73
The max and min filter (morphological filtering)
Original motion
detection signal
5x5 max filter
(dilation)
technische universiteit eindhoven
W
73
5x5 max- cascaded
with 5x5 min-filter
(closing)
74
The max and min filter (morphological filtering)
Original motion
detection signal
5x5 min filter
(erosion)
technische universiteit eindhoven
W
74
5x5 min- cascaded
with 5x5 max-filter
(opening)
75
Filter optimization
technische universiteit eindhoven
W
75
76
Optimization is often a problem
Play enhanced video
Store video
Subjective assessment
Program enhancement
algorithm
Subjective assessment is time consuming
Huge design space requires automatic optimization…
technische universiteit eindhoven
W
76
77
It seems straightforward…
Desired output
Processing output
(a-b)2
1/N.
S
Minimize a sum of squared pixel differences by
varying all parameters…
technische universiteit eindhoven
W
77
MSE
78
Bottleneck eliminated?
Play enhanced video
Store video
MSE optimization
Program enhancement
algorithm
technische universiteit eindhoven
W
78
79
MSE-optimal (non-recursive) linear filtering
•
•Cross-correlation matrix
•
The linear filter is defined by:
•Auto-correlation matrix
y  w1 x1  w2 x2  w3 x3  ...  wn xn
Compare the output with original image to know error:
•
For a minimal MSE, the first derivative should be zero:
e  yo  y
 e 
e 2
e  2 xi e  0
 2
wi
 wi 
•
 X 11
X
 21
 ...

 X n1
If we now define:
X ji  xi x j
Yi  xi yo
We then get:
technische universiteit eindhoven
W
79
X 12
X 22
...
...
...
...
X n 2 ...
X 1n   w1   Y1 
X 2 n   w2  Y 2 
    
...   ...   ... 
   
X nn   wn   Yn 
80
MSE-optimal (non-recursive) linear filtering
•
We have to solve the following equation:
 X 11
X
 21
 ...

 X n1
X 12
X 22
...
...
...
...
X n 2 ...
X 1n   w1   Y1 
X 2 n   w2  Y 2 
    
...   ...   ... 
   
X nn   wn   Yn 
•
We thereto write:
•
And conclude upon the following optimal weights:
X.W  Y
W  X1X.W  X1Y
technische universiteit eindhoven
W
80
81
We can use this for noise reduction
Original noisy image
13-taps filter support
13-taps averaging filter
13-taps LMSE-filter
technische universiteit eindhoven
W
81
82
We may also use it for de-blurring noisy images
Original blurred noisy image
Conclusion: LMSE-filter
enhances noise less
•
Therefore, also reduces the
blur less…
•
MSE-best compromise
3x3 peaking-filter
3x3LMSE-filter
technische universiteit eindhoven
W
•
82
83
How does this compare with “inverse filtering”?
•
•
We shall see later that it is also possible to calculate the
inverse filter for perfect de-blurring, which turns out to be a
recursive filter
The inverse filter has an infinitely high gain if the blurring
filter has a zero response for a given frequency
•
Consequence is that noise will be amplified unlimited…
Original blurred noisy image
De-blurring with inverse filter
technische universiteit eindhoven
W
83
84
Problem with
LMSE--filters
LMSE
technische universiteit eindhoven
W
84
85
Images with identical MSE
Blurred
Noisy
Blurred
Noisy
Sharpened
Compressed
Compressed
Sharpened
technische universiteit eindhoven
W
85
Video processing
for multimedia systems
G. de Haan
technische universiteit eindhoven
W
87
Adaptive filtering
technische universiteit eindhoven
W
87
88
Trained Filters
(optimizing
adaptive filters)
technische universiteit eindhoven
W
88
89
Images with identical MSE
Blurred
Noisy
Blurred
Noisy
Sharpened
Compressed
Compressed
Sharpened
technische universiteit eindhoven
W
89
90
What’s wrong with MSE?
•
The mistake is in the averaging!
•
Some picture parts get a lot better with a method
that is poor on the average!
•
 characterize image parts that can be treated
identically…
•
…and individually optimize (MSE) parts with the
same character!
technische universiteit eindhoven
W
90
91
Classification based filtering
LUT
Classification
Support with input
pixels
x1 x2 x3
x4
x5
x6
x7
x8
x9
Linear
filtering
y  w1c x1  w2c x2c  ....  wnc xn
technische universiteit eindhoven
W
91
y
92
Classification
examples
technische universiteit eindhoven
W
92
93
Local edge direction classification
Image
Edge directions (colour)
10o
technische universiteit eindhoven
W
93
50o 90o 130o 170o
94
Local contrast classification
Image
Local contrast (colour)
Low
technische universiteit eindhoven
W
94

High
95
Local sharpness classification
Image
Local sharpness (colour)
Low
technische universiteit eindhoven
W
95

High
96
Coding the local structure to classify support data
Classification code is concatenation of pixels reduced to single bit:
 1 , ( x  xav )
ADRC( x)  
 0 , ( x  xav )
with
xav  1
i n
n
i 1
xi
technische universiteit eindhoven
W
96
97
Not only linear
filtering
technische universiteit eindhoven
W
97
98
Architecture of the hybrid filter
Classification
Input
LUT
Non-linear
filtering
Output
Concept can be extended to trained rank-order and bilateral filters
technische universiteit eindhoven
W
98
99
Not only
filtering
technische universiteit eindhoven
W
99
100
Trained Mixing of processing options
metrics
Classification
LUT
Processing
option 1
Input
Processing
option 2
Processing
option 2
technische universiteit eindhoven
W
100
Mixer
Output
101
Application
examples
technische universiteit eindhoven
W
101
102
Sharpening and de-noising
Trained Filter output
Noise filter without classification
technische universiteit eindhoven
W
102
103
PixelPlus
Up-scaling combined with sharpening
Standard up-scaling
Trained Filter output
technische universiteit eindhoven
W
103
104
Interlace artifact removal
Line-average input
Output Trained Filter
technische universiteit eindhoven
W
104
105
Enhancement of digital video
Input
Trained Filter output
technische universiteit eindhoven
W
105
106
Microscopy resolution enhancement
Input: RED
Output: RED GREEN BLUE
technische universiteit eindhoven
W
106
107
Up-scaling of MRI-images
MSE (%)
100
80
60
MSE
40
20
0
HD
BiLin Fourier
technische universiteit eindhoven
W
107
TF
108
Conclusions
Classification
In
LUT
Filter
• Similar architecture for many functions
• Design methodology replaces heuristics
technische universiteit eindhoven
W
108
Out
109
The value of trained filtering
•
•
Automatic optimization
•
•
Design methodology replaces heuristics for tuning
No thinking  faster
Researcher can focus on creatively finding the
relevant classes
technische universiteit eindhoven
W
109
110
Neighbourhood
Selection
technische universiteit eindhoven
W
110
111
Neighbourhood selection
•
So far, we assumed that ALL pixels in the support are combined
under ALL circumstances
•
We may also propose to adapt the set of pixels that are
“combined” to expectations about local correlation, using a socalled neighbourhood selection technique
•
A neighbourhood shall be defined as a sub-set of the support
•
•
Various options exist to exclude pixels from the support
• K-nearest, sigma nearest, symmetrical nearest,…
Pixels in the neighbourhood are then combined
•
Weighted averaging, rank-order, etc.
technische universiteit eindhoven
W
111
112
Adaptive filtering: Neighbourhood Selection
Input
Select
Combine pixels
neighbourhood
in
from support
neighbourhood
•
support
E.g. only
• Linear filter
pixels similar
• Weighted average
to current
neighbourhood
pixel
• Rank-order filter
•
technische universiteit eindhoven
W
Output
112
Min, max, median
Support and neighbourhood
113
Example 1
Example 2
Neighbourhhood
Neighbourhhood
}
Rank no.
max
Support: 3x3
min
technische universiteit eindhoven
W
113
Non-adaptive: Standard neighbourhood
Rank no.
114
I
II
technische universiteit eindhoven
W
114
115
Effect of the standard neighbourhood selection (5x5)
technische universiteit eindhoven
W
115
116
Neighbourhood selection: K (2) nearest neighbours
II
Rank no.
I
technische universiteit eindhoven
W
116
117
Effect of the k (12) nearest neighbourhood selection (5x5)
technische universiteit eindhoven
W
117
Neighbourhood selection: Sigma nearest neighbours
Rank no.
118
I
II
σ
σ
-σ
-σ
technische universiteit eindhoven
W
118
119
Effect of the sigma nearest selection (5x5)
technische universiteit eindhoven
W
119
Neighbourhood selection: Symmetric nearest neighbours
Grey-level
120
Position
technische universiteit eindhoven
W
120
121
The effect of symmetric nearest neighbour filtering (5x5)
technische universiteit eindhoven
W
121
122
The effect of symmetric nearest neighbour filtering (5x5)
technische universiteit eindhoven
W
122
123
Adaptive filtering: Neighbourhood Selection
Input
Select
Combine pixels
neighbourhood
in
from support
neighbourhood
•
support
E.g. only
pixels close to
current pixel
•
neighbourhood
•
technische universiteit eindhoven
W
123
Output
Linear filter
•
Weighted average
Rank-order filter
•
Min, max, median
124
Prepare yourself for the exam…
•
•
Last week: Chapter 2 and Chapter 3
Today: Chapter 4
•
I recommend you read the text
•
And try the exercises in the book:
•
•
•
•
Book available at Pt9:24
Chapter 2-3
Chapter 4
You have to download VidProc (w3.ics.ele.tue.nl/~dehaan/ )
• Send me e-mail for password ([email protected])
technische universiteit eindhoven
W
124
125
Quantitative
analysis of linear
filters
technische universiteit eindhoven
W
125
126
Frequency response of a linear filter
Input
H(0)
delay
delay
H(1)
H(N)
sum
y[k ]   h(i ) x[k  i ]
i
technische universiteit eindhoven
W
126
Output
127
Frequency response of a linear filter
•
Given a system with impulse response h(i)
•
Given an input signal = complex sinusoid
x(k )  e
•
jk
Input transfer
,  k  
The output signal is:
y (k )   h(i ).x(k  i )   h(i ).e j ( k i ) e jk  h(i ).e  ji
•
i
i
And the frequency response:
H (e )   h(i ).e
j
i
technische universiteit eindhoven
W
i
127
 jwi
128
Example: the 1 2 1 filter
•
•
•
Following the definition:
H (e j )   h(i ).e  jwi  e  jw1  2e 0  e  jw1
Substituting:
We get:
i
e  jw  cos t  j sin t
H ( )  cos(t )  j sin( t )  2  cost  j sin t
•
Which simplifies to:
H ( )  2  2 cost
4
½.fs
f
technische universiteit eindhoven
W
128
129
For all filters with a symmetric impulse response
•
•
•
Symmetric: h(i)=h(-i), i=1..L
L
The frequency response is
j
H (e ) 
L
 h(i).e
 j .i
i  L
 ...   ai . cos(.i )
i 0
•
Real-valued (=zero-phase) transfer function
•
This translates into a constant delay for all frequencies
technische universiteit eindhoven
W
L
129
i
130
Example: the (1 1) - filter
•
•
•
Following the definition:
H (e j )   h(i ).e  jwi  e 0  e  jw1
i
 jw
Substituting:
e  cos t  j sin t
We get a complex frequency transfer (non-zero phase):
H ( )  1  cost  j sin t
•
We can calculate the magnitude of the transfer:
|| H ( ) || R 2  I 2  1  cos 2 t  2 cos t  sin 2 t
technische universiteit eindhoven
W
130
131
Example: the 1 1 filter
•
•
So, we have:
|| H ( ) || 1  cos 2 t  2 cos t  sin 2 t
This simplifies to:
|| H ( ) || 2  2 cos t
•
And we remember from modulation:
2 cos  cos   cos(   )  cos(   ) 
4 cos 2 (t / 2)  2  2 cos t
•
So, we conclude:
|| H ( ) ||| 2 cos(t / 2) |
2
½.fs
technische universiteit eindhoven
W
131
f
132
What if we re-use output samples? Recursive filtering
Input
delay
delay
h(1)
h(0)
delay
h(N)
Output
sum
hr(M)
hr(1)
delay
delay
delay
y (k )   h(i ).x(k  i )   hr (m). y (k  m)
i
m
technische universiteit eindhoven
W
132
133
What about a recursive filter?
•
•
Now the output signal is:
N
M
i 0
m 1
y (k )   h(i ).x(k  i )   hr (m). y (k  m)
or:
M
•
(1   hr (m)). y (k )   h(i )). x(k  i )
m 1
i
 h( n)
y (k ) 
.x ( k )
1   h ( m)
or:
n
r
m
•
and finally:
H ( j ) 
jn
h
(
n
).
e

n
1   hr (m).e jm
m
technische universiteit eindhoven
W
133
x(k )  e jk
134
Inverse filtering
•
Assume a signal has been filtered with a (½ ½) - filter
•
Can we invert the operation (de-blur)?
H (11) (e j )   h(i ).e  jwi  0.5e 0  0.5e  jw1
•
i
We are looking for H-1(ejω), i.e.:
H
•
1
(11)
1
2
2
(e ) 
 0  jw1 
 jwi
 jw1
h
(
i
).
e
e

e
1

(

e
)
 (11)
j
i
This is a recursive filter!:
technische universiteit eindhoven
W
134
135
The inverse of a (½ ½) - filter
Input
H(0)=2
delay
delay
H(1)
delay
H(N)
Output
sum
hr(M)
delay
hr(1)=-1
delay
delay
technische universiteit eindhoven
W
135
136
So this is equivalent to a copper wire:
Input
delay
½
½
1
2
sum
+
-1
1
½.fs
f
delay
f
½.fs
Since the (½ ½) – filter has a zero transfer for the Nyquist
frequency, the inverse filter has an infinite gain there!
technische universiteit eindhoven
W
136
Output
137
Consequences of infinite gain inverse filter
Result of cascade:
Same noise, but inverse of ½ 0 ½
But if there was some noise:
Worse than the noisy blurred:
technische universiteit eindhoven
W
137
138
Solutions for de-blurring noisy images
•
The value of the inverse filter is limited because of noise
amplification
•
•
The noise easily dominates the perception if blurring process
suppresses parts of the spectrum significantly
Norbert Wiener (1894-1964) proposed the MSE-optimal
solution by adding a noise-depending term in the
denominator
•
•
The result is commonly referred to as the Wiener Filter
MSE-best solution modelling blur AND noise
technische universiteit eindhoven
W
138
139
Prepare yourself for the exam…
•
•
Last week: Chapter 2 and Chapter 3
Today: Chapter 4
•
I recommend you read the text
•
And try the exercises in the book:
•
•
•
•
Book available at Pt9:24
Chapter 2-3
Chapter 4
You have to download VidProc (w3.ics.ele.tue.nl/~dehaan/ )
• Send me e-mail for password ([email protected])
technische universiteit eindhoven
W
139
140
Questions. Part 4. Video filtering
1. Calculate the impulse response of the cascade of a horizontal (¼, ½, ¼)-filter
and a horizontal (½, 0, ½) filter
1.
Confirm your calculations experimentally with VidProc
2. Calculate an edge image of the Bicycle using a 2D edge-filter, e.g. central
coefficient 4, diagonal coefficients –1
1.
Add the edge image to the original bicycle image, and describe the result image
1.
Use the inverse filter to de-blur your output image
1.
2.
Try to de-blur this noisy image with the inverse filter
Train a Wiener filter (13 taps diamond shaped kernel) to “restore” the image
1.
Does the support affect the output with a sigma- or K-nearest algorithm? Test!
3. Blur the bicycle sequence with a 3x3 box-filter
4. Add Gaussian noise (tab “Noise”, level 20) to the blurred Bicycle image
5. What is the difference between filter support and filter neighbourhood?
6. Consider shot noise. What do you expect from the K-nearest neighbourhood
selection process, the sigma neighbourhood and the median filter?
1.
Confirm your expectations using VidProc
7. Consider detail blur. Will the K-nearest neighbourhood selection process or
the sigma neighbourhood selection process be best? Why?
1.
Confirm your expectations using the software
technische universiteit eindhoven
W
140
141
Adaptive filtering
•
Global, or context free, or position invariant
adaptation of the filter
•
•
•
E.g. (estimated) noise level dependent
E.g. (estimated) blur-level dependent
Local, or context sensitive, or position variant
adaptation of the filter
•
•
•
Edge/motion dependent
Neighbourhood Selection
Trained Filters
technische universiteit eindhoven
W
141

Download Report