Transcript PPT - West Virginia University

Patch-based Image
Interpolation: Algorithms
and Applications
Xin Li
Lane Dept. of CSEE
West Virginia University
Where Does Patch Come from?


Neuroscience: receptive
fields of neighboring
cells in human vision
system have severe
overlapping
Engineering: patch has
been under the disguise
of many different names
such as windows in digital
filters, blocks in JPEG
and the support of
wavelet bases,
Cited from D. Hubel, “Eye, Brain and
Vision”, 1988
Patch-based Image Models

Local models



Markov Random Field (MRF) and higher-order extensions
(e.g., Field-of-Expert)
Transform-based: PCA, DCT, wavelets
Nonlocal models






Bilateral filtering (Tomasi et al. ICCV’1998)
Texture synthesis via Nonparametric resampling
(Efros&Leung ICCV’1999)
Exemplar-based inpainting (Criminisi et al. TIP’2004)
Nonlocal mean denoising (Buades et al.’ CVPR’2005)
Total Least-Square denoising (Hirakawa&Parks TIP’2006)
Block-matching 3D denoising (Dabov et al. TIP’2007)
A Bayesian Formulation of Image
Interpolation Problem
Likelihood
(our focus here)
Image prior
(e.g., sparsity-based)
p(y | x, H ) p(x | H )
p(x | y, H ) 
p(y | H )
Unobservable
data
Observable
data
Model class
(e.g., local vs. nonlocal)
A Simple Extension of BM3D
x  T 1 (S[T (x) |  ])
Hard thresholding
3D transform of similar patches
Basic idea: combine BM3D with progressive thresholding (Guleryuz TIP’2006)
Interpolation of LR Images
x
y
bicubic
NEDI1
this work
31.76dB
32.36dB
32.63dB
34.71dB
34.45dB
37.35dB
28.70dB6
27.34dB
28.19dB
18.81dB 15.37dB 16.45dB
1X. Li and M. Orchard, “New edge directed interpolation”, IEEE TIP, 2001
Go Back to Biology
rods
cone
Spatially random distribution of rod/cone cells keeps
aliasing artifacts out of our vision
Interpolation of Nonuniformlysampled Images
x
y
DT
29.06dB
28.46dB
KR
this work
31.56dB
34.96dB
31.16dB
36.51dB
26.04dB
24.63dB
29.91dB
17.90dB
18.49dB
29.25dB
DT- Delauney
Triangle-based
(griddata under
MATLAB)
KR- Kernal
Regression-based
(Takeda et al.
IEEE TIP 2007)
Modeling Spatial Randomness


Extensively studied in geostatistics and
environmental statistics (e.g., spatial distribution
of animals and plants)
Mathematically modeled by homogeneous
Poisson process (density parameterλ)
Lack of positional differentiation
 Lack of scale differentiation


Empirically there exist quadrant-based and
distance-based randomness metrics
Monte-Carlo Based Optimization
The lower energy
the more random
Iterative procedure: randomly pick two locations (one black and the other white), if
swapping them decreases the energy, accept it; otherwise accept it with some probability
Importance of Locations
after optimization
In biological world:
evolution + development
before optimization
Identical reconstruction algorithm; only differ on sampling locations
Application into
Compressive Imaging
Random
Sampling
Pattern
S
quantization
channel
interpolation
sensor node
How is it different from conventional image coding system?
No bits are spent on coding the location information (random=no cost).
Coding Results
R=0.21bpp
original
ours
SPIHT
PSNR=27.85dB PSNR=28.82dB
SSIM=0.8750 SSIM=0.8637
R=0.81bpp
original
ours
SPIHT
PSNR=28.10dB PSNR=22.98dB
SSIM=0.9182 SSIM=0.7512
Error Resilience Results
Conclusions



A good image prior is useful to many processing tasks
involving incomplete or noisy observation
As we move from local to nonlocal models, the location
of sampling points becomes important – “location
(address) and intensity (data) are the same thing” cited
from T. Kohonen “Self-Organization and Associative
Memory”
Image processing is at the intersection of science and
engineering- will BM3D lead to a new class of SOM?