程序代写代做代考 go Excel algorithm Chapter 5 Image Restoration and Reconstruction

Chapter 5 Image Restoration and Reconstruction

Agenda
• Problem definition of image restoration
– Restore image in a degradation model involving a linear, position-invariant system and noise.
• Noise-only degradation
– Arithmetic mean filter, geometric mean filter, median filter, alpha-trimmed mean filter, adaptive median filter
• Restoration for Linear, Position-invariant Degradation with Noise
– Inverse filtering – Wiener filtering
2

Image Restoration
• Aims at restoring or reconstructing the original image that has been degraded based on prior knowledge.
• Image restoration vs. Image enhancement
– Image restoration: Recover an image that has been degraded so that it looks like the original image (based on some objective criteria).
– Image enhancement: More focused on making the image more useful or visually pleasant.
3

Image Restoration Model
• Model the degradation by a process H, then add random
noise:
􏴄 􏴁,􏴂 =􏳿 􏴁,􏴂 ∗h 􏴁,􏴂 +􏵧(􏴁,􏴂)
• The FT equivalent:
􏵘 􏴖,􏴦 =􏴠 􏴖,􏴦 􏴔 􏴖,􏴦 +􏴟(􏴖,􏴦)
4

5.1 Restoration in the Presence of Noise Only
5

Noise-only Degradation Model
• Consider here the degradation is caused by random noise 􏵧 􏴁, 􏴂 only, i.e.,
􏴄􏴁,􏴂 =􏳿􏴁,􏴂 +􏵧􏴁,􏴂 􏵘􏴖,􏴦 =􏴠􏴖,􏴦 +􏴟(􏴖,􏴦)
6

Mean Filters
• ArithmeticMean – Boxcar filter
• Geometric Mean
– Retain more image details. Less blurring.
7

Mean Filters
8

Order-Statistic Filters
• Based on ordering (ranking) pixels in window and replacing central pixel with ranking result.
• Useful spatial filters include
– Median filter
– Alpha trimmed mean filter
9

Median Filter
• Median filter: replace value at central pixel (i,j) by median in a MxN neighbourhood.
– e.g.,
3×3 neighbourhood
• Excellent noise reduction for salt-and- pepper noise with less blurring than spatial
averaging
10

Median Filter
• Median filter does well if the number of corrupted pixels is less than 50% in the neighbourhood.
• Multiple passes of median filtering make further improvement.
11

Alpha-Trimmed Mean Filter
• 􏵨􏴤􏴾 isanm×􏴏imageregion
• Deletethe􏴑/2lowestand􏴑/2highestgreylevels. • 􏴄􏵣(􏵂,􏴌)representstheremaining􏴈􏴏–􏴑pixels.
• If􏴑=0,arithmeticmeanfilter
• If􏴑=􏴈􏴏−1,medianfilter
• Canbeconsideredasahybridofthesetwofilters
12

Noise Removal Examples
Image corrupted by uniform noise
Image further corrupted
by salt-and- pepper noise
Filtering by a 5×5 Arithmetic Mean Filter
Filtering by a 5×5 Geometric Mean Filter
Filtering by a 5×5 Median Filter
Filtering by a 5×5 Alpha-Trimmed Mean Filter (d = 6)
13

Adaptive Filters
• The filters discussed so far are applied to an entire image without any regard for how image characteristics vary from one point to another.
• The behaviour of adaptive filters changes depending on the characteristics of the image inside the filter region.
• We will look at the adaptive median filter.
14

Adaptive Median Filtering
• The median filter performs relatively well on impulse noise if the spatial density of the impulse noise is not large.
• The adaptive median filter can handle much more spatially dense impulse noise, and also performs some smoothing for non-impulse noise.
15

Adaptive Median Filtering
• The key to understanding the algorithm is to remember that the adaptive median filter has three purposes:
– Remove impulse noise
– Reduce distortion (excessive thinning or thickening of object boundaries).
– Provide smoothing of other noise
16

Adaptive Median Filtering
• In the adaptive median filter, the filter size and the output value change depending on the characteristics of the image.
• Notation:
– 􏵨􏴤􏴾 = the support of the filter centred at (x, y) – 􏵩􏵪􏴣􏴫 = the minimum gray level in 􏵨􏴤􏴾
– 􏵩􏵪􏵫􏴤 = the maximum gray level in 􏵨􏴤􏴾
– 􏵩􏵪􏴥􏵬 = the median gray level in 􏵨􏴤􏴾
– 􏵩􏴤􏴾 = grey level at coordinates (x, y)
– 􏵨􏵪􏵫􏴤 = maximum allowed size of 􏵨􏴤􏴾
17

Adaptive Median Filtering
18

Adaptive Median Filtering
• Stage A determines whether the output of the median filter 􏵩􏵪􏴥􏵬 is an impulse or not (black or white).
• If it is not an impulse, go to stage B.
• If it is an impulse, the window size is increased. Another check on whether z_med is an impulse is carried out again until the window size reaches 􏵨􏵪􏵫􏴤.
• Note that there is no guarantee that 􏵩􏵪􏴥􏵬 will not be an
impulse. This is less possible with a smaller density of
the noise is and a larger 􏵨 . 􏵪􏵫􏴤
19

Adaptive Median Filtering
• Stage B determines whether 􏵩􏴤􏴾 is an impulse or not (black or white).
• Ifitisnotanimpulse,thealgorithmoutputsthe unchanged pixel value 􏵩􏴤􏴾. As compared to the
median filter that always outputs 􏵩􏵪􏴥􏵬, the distortion is reduced in the filtered image.
• Ifitisanimpulsethealgorithmoutputsthemedian
􏵩􏵪􏴥􏵬.
20

Adaptive Median Filtering
Image corrupted by salt-and-pepper noise. A total of 50% of pixels are corrupted (25% white, 25% black)
Adaptive median filtering preserves sharpness and details, e.g., the connector fingers.
21

Periodic Noise
• Typicallyarisesdueto electrical or electromagnetic interference.
• Givesrisetoregular noise patterns in an image.
• Notch filter can be used to remove periodic noise
22

Notch Filters for Removing Periodic Noise
• Thegeneralformof notch filters:
􏴔 􏴖,􏴦 􏴲
Ideal
= 􏴱􏴔􏴰(􏴖,􏴦)􏴔􏴘􏴰(􏴖,􏴦)
􏴰􏴳􏴬
where􏴔􏴰 􏴖,􏴦 and 􏴔􏴘􏴰(􏴖,􏴦) are highpass filters centred at (􏴖􏴰,􏴦􏴰) and −􏴖􏴰,−􏴦􏴰 , respectively.
Gaussian
Butterworth
23

Notch Filter Example
Original Image
Frequency spectrum with enhancement corresponding to the sinusoid
Ideal Notch Filter
Output Image
24

5.2 Restoration for Linear, Position-invariant Degradation with Noise
25

Linear, Position-invariant Degradation with Noise
• Model the degradation by a process H, then add random
noise:
􏴄 􏴁,􏴂 =􏳿 􏴁,􏴂 ∗h 􏴁,􏴂 +􏵧(􏴁,􏴂)
where h(x, y) is the impulse response of the degradation function.
• The convolution implies that the degradation mechanism is linear and position-invariant
26

Linear, Position-Invariant System
• Linear
􏳿[􏴁,􏴂] H 􏳿􏴀[􏴁,􏴂]
H􏴓􏳿􏴬􏴁,􏴂+􏵭􏳿􏴩 􏴁,􏴂 =􏴓H􏳿􏴬􏴁,􏴂 +􏵭H(􏳿􏴩􏴁,􏴂)
• Position-Invariant
IfH􏳿􏴁,􏴂 =􏳿􏴀􏴁,􏴂,then H􏳿􏴁−􏴓,􏴂−􏵭 =􏳿􏴀􏴁−􏴓,􏴂−􏵭
27

Linear, Position-Invariant System
• 􏳿 􏴁, 􏴂 can be expressed as a linear combination of impulses with different spatial shifts: 􏵛 􏵛
􏳿􏴁,􏴂 = 􏵮 􏵮 􏳿􏴈,􏴏􏵜􏵪􏴫[􏴁,􏴂] 􏵪􏴳􏴘􏵛 􏴫􏴳􏴘􏵛
where 􏵜􏵪􏴫 􏴁, 􏴂 = 􏵜 function centred at 􏴈, 􏴏 = 􏴮1, 􏴊􏳿 􏴁 = 􏴈, 􏴂 = 􏴏
0, 􏴒􏴌h􏴍􏴎􏵯􏴊􏵂􏴍
28

Linear, Position-Invariant System
• Define impulse response (also known as point spread function):
h 􏴁, 􏴂 ≜ H 􏵜􏴜􏴜 􏴁, 􏴂 • Since H is position-invariant,
H􏵜􏵪􏴫􏴁,􏴂 =h􏴁−􏴈,􏴂−􏴏 —(5.1)
• If input is an impulse shifted by m and n, respectively, in the x and y directions, the output is the impulse response shifted by the same amount.
29

Linear, Position-Invariant System
• By linearity:
􏵛􏵛
􏳿􏴀􏴤,􏴾=H􏳿􏴁,􏴂 =􏵮 􏵮􏳿􏴈,􏴏H􏵜􏵪􏴫􏴁,􏴂 􏵪􏴳􏴘􏵛 􏴫􏴳􏴘􏵛
• Using Eqn. (5.1)
􏵛􏵛
􏳿􏴀􏴁,􏴂=􏵮 􏵮􏳿􏴈,􏴏h􏴁−􏴈,􏴂−􏴏
􏵪􏴳􏴘􏵛 􏴫􏴳􏴘􏵛 = 􏳿 ∗ h 􏴁, 􏴂
30

Estimating the Impulse Response
• In what follows, we consider that the impulse response (IR) of the degradation model is known.
• If the IR is not known, it is estimated by one of the following three approaches:
– By observation
– By experimentation – By modeling
31

Estimation by Image Observation
• Choose a region with high-contrast. Denote the subimage to be 􏴄􏵰[􏴁, 􏴂].
• Process the image so that it becomes more visually pleasing. The processed
􏵱 image is denoted by 􏳿􏵰[􏴁, 􏴂].
• Then,
􏴔􏴖,􏴦 =􏵘􏵰 􏴖,􏴦
• Need many trial and error, therefore tedious.
􏵱
􏴠􏵰 􏴖,􏴦
32

Estimation by Experimentation
• Using the same or a similar imaging system, take a picture of a bright dot (i.e., an impulse). Denote the FT of this picture as􏵘 􏴖,􏴦 .
• Then,􏴔 􏴖,􏴦 =􏵲 􏴚,􏴧 ,where􏵴isthe 􏵳
strength of the bright dot.
􏳿(􏴁, 􏴂) = 􏵴􏵜(􏴁, 􏴂)
􏴄􏴁,􏴂 =􏵴h(􏴁,􏴂)
33

Estimation by Modeling
Atmospheric turbulence
􏴔(􏴖, 􏴦) = 􏴍􏴘􏴰 􏴚􏴨􏵠􏵵􏴨
􏵶􏵷
34

Estimation by Modeling
Planar Motion
• 􏴁􏴜(􏴌) and 􏴂􏴜(􏴌) are the time-varying components of motion at each pixel.
• The total exposure at any pixel is obtained by integrating the instantaneous exposure over the time the shutter is open.
• Assumption: the shutter opening and closing is instantaneous.
• If 􏵸 is the duration of the exposure, the recorded image is expressed by:
(
)
35

Estimation by Modeling
() ()
36

Estimation by Modeling
The transfer function becomes:
37

Estimation by Modeling
38

Inverse Filtering
• The simplest approach to undoing the degradation is 􏵘 􏴖, 􏴦
􏴠􏵹 􏴖 , 􏴦 = 􏴔 􏴖 , 􏴦
• Issue is that we also enhance the noise:
􏴠􏵹 􏴖 , 􏴦 = 􏴠 􏴖 , 􏴦 + 􏴟 􏴖 , 􏴦 􏴔 􏴖,􏴦
• The issue is prominent at regions where 􏴔(􏴖, 􏴦) is close to 0.
39

Inverse Filtering
40

Inverse Filtering
• Apply the inverse filter only at the low frequencies:
41

Inverse Filtering
42

Wiener Filtering
• Wiener Filtering = Mean Squared Error (MSE) Filtering
• Incorporates both:
– Degradation function
– Statistical characteristics of noise
• Optimizes the filter so that the MSE is minimized:
43

Wiener Filtering
• Theminimumoftheerrorfunctionisgiveninthe frequency domain by the expression:
where 􏴩 􏵨􏵺 􏴖,􏴦 = 􏴟 􏴖,􏴦
= Power spectrum of the noise
􏵨􏵙 􏴖,􏴦 = 􏴠 􏴖,􏴦 􏴩 =Powerspectrumofthe undegraded signal
44

Wiener Filtering
• Note that if
– 􏵨􏵺 = 0, the Wiener filter reduces to the inverse filter.
– 􏵨􏵺 is large, the Wiener filter approaches 0.
45

Derivation of Wiener Filter
• ByParseval’sTheorem,minimizingMSEinspatial domain is the same as minimization in the frequency domain: 1
􏵮􏵮􏳿􏴁,􏴂 −􏳿􏵻􏴁,􏴂 􏴩=􏴇􏴟􏵮􏵮􏴠􏴖,􏴦 −􏴠􏵹􏴖,􏴦 􏴩 􏴤􏴾 􏴚􏴧
• Wejustneedtominimize:
􏴩
• Needtofindafilter􏵽(􏴖,􏴦),whenappliedtothe
􏵼 = 􏵮 􏵮 􏴠 􏴖 , 􏴦 − 􏴠􏵹 􏴖 , 􏴦 􏴚􏴧
corrupted signal 􏵘(􏴖, 􏴦) would minimize the error: 􏴠􏵹 􏴖 , 􏴦 = 􏵽 􏴖 , 􏴦 􏵘 ( 􏴖 , 􏴦 )
46

Derivation of Wiener Filter
The reconstructed signal is:
􏴠􏵹=􏵽􏵘=􏵽 􏴔􏴠+􏴟 =􏵽􏴔􏴠+􏵽􏴟 􏴠 − 􏴠􏵹 = 1 − 􏵽 􏴔 􏴠 − 􏵽 􏴟
􏵼=􏵮􏵮 1−􏵽􏴔􏴠−􏵽􏴟􏴩 􏴚􏴧
Noting that F and N are uncorrelated:
􏵼=􏵮􏵮 1−􏵽􏴔􏴠􏴩+􏵽􏴟􏴩=􏵮􏵮􏵼􏴚􏴧 􏴚􏴧 􏴚􏴧
47

Derivation of Wiener Filter
• Set 􏵾􏵿􏶀􏶁 = 0 for each (􏴖, 􏴦) to get the optimized 􏵽, 􏵾􏶂 ∗
denoted by 􏵽 . 􏵾 ∗ ∗
• Using the result 􏵾􏶃 􏵩􏵩 = 2􏵩 , we have:
􏶄 1−􏵽􏴔 􏴠􏴩 =􏶄 1−􏵽􏴔 􏴠􏴩⋅􏶄 1−􏵽􏴔 􏴠
􏵾􏵿
= 2 􏵽∗􏴔∗ − 1 􏴔 􏴠 􏴩
􏶄􏵽 􏶄 1−􏵽􏴔 􏴠 􏶄􏵽 =21−􏵽∗􏴔∗ 􏴠∗⋅−􏴔􏴠
• 􏶀􏶁 = 2 􏵽∗􏴔∗ − 1 􏴔 􏴠 􏴩 + 2 􏴟 􏴩􏵽∗ 􏵾􏶂 􏴨
• 􏵾􏵿􏶀􏶁=0→􏵽∗= 􏶅􏶆
􏵾􏶂 ∗ 􏴩􏶅􏴨􏶆􏴨􏵠􏶇􏴨∗ 􏴩
􏵽=􏴔􏴠=􏴔=1􏴔
􏴔􏴩􏴠􏴩+􏴟􏴩 􏴔􏴩+􏴟􏴩 􏴔 􏴔􏴩+􏴟􏴩 􏴠􏴩 􏴠􏴩
48

Practical Issue of Wiener Filter
• We do not know 􏵨􏵺(􏴖, 􏴦) and 􏵨􏵙(􏴖, 􏴦) in advance:
– Usually we assume white noise, so 􏵨􏵺 (􏴖, 􏴦) = 􏴟􏴖,􏴦 􏴩isaconstant.
– However, we do not usually know the spectrum of
the undegraded image 􏴠 􏴖, 􏴦
􏴩
• Solution: Approximate an average signal-to- noise ratio, denoted by 􏵨􏴟􏶈, used across all (u,v):
49

Example
• Radially limited inverse filter
• Wiener filter
SNR is estimated interactively.
50