[G4]image deblurring, seeing the invisible

2. 2 CG Lab., POSTECH

3. Blur?
Degrade image/video quality
Shot/record under dim light circumstance
Long exposure!
3 CG Lab., POSTECH

4. Blur
Various kinds of blur
Camera shake (Camera motion blur)
Out of focus (Defocus blur) Others (Wind, vibration, etc.)
Object movements (Object motion blur)
4 CG Lab., POSTECH

5. Deblurring?
Remove blur and restore a sharp image
Input blurred image Deblurring result
5 CG Lab., POSTECH

6. Importance
Image/video in our daily lives
But, sometimes a retake is difficult
Strong demand for high quality
E.g. CCTV, car’s black box, medical imaging
6 CG Lab., POSTECH

7. Contents
Fast Motion Deblurring
Sunghyun Cho and Seungyong Lee (POSTECH)
ACM SIGGRAPH Asia 2009

Text Image Deblurring Using Text-Specific Properties
Hojin Cho (POSTECH), Jue Wang (Adobe), and Seungyong
Lee (POSTECH)
ECCV 2012 (to appear)
7 CG Lab., POSTECH

8. Sunghyun Cho Seungyong Lee


POSTECH

ACM SIGGRAPH Asia 2009

9. Motion blur
Camera jitters
Blurred image Latent sharp image
9 CG Lab., POSTECH

10. Image formation model
Convolution
Motion blur kernel
Trace of a sensor
Latent sharp image Blur kernel Blurred image
* : convolution operator
10 CG Lab., POSTECH

11. Deblurring
Non-blind deconvolution
Ill-posed (Due to the loss of information caused by motion blur)




Blind deconvolution
Severely ill-posed
Latent image PSF Blurred image
Latent image PSF Blurred image
11 CG Lab., POSTECH

12. Blind deconvolution
Severely ill-posed problem
No unique solution
Blurred image
Possible solutions
12 CG Lab., POSTECH

13. Related work
Parametric kernels
Ex) 1D linear motion blur
[Yitzhakey et al. 1998], [Rav-Acha and Peleg 2005], [Cho et
al. 2007], [Money and Kang 2008], …

Blurred image Latent sharp image PSF
13 CG Lab., POSTECH

14. Related work
More complex motion blur
[Fergus et al. 2006], [Jia 2007], [Shan et al. 2008]
Excessive amount of computation
Blurred image Latent sharp image PSF
14 CG Lab., POSTECH

15. Motivation
Computation time  Important for practical
purpose
Previous methods are slow


Image size: 640 x 480
kernel size: 25 x 25
[Fergus et al. 2006] took 1 hr 25 min.
[Shan et al. 2008] took 4 min 48 sec.
Our method took 5.766 sec. in CPU
and 0.734 sec. using GPU accel.
15 CG Lab., POSTECH

16. Contributions
Fast motion deblurring
Only a few sec.
Fast latent image estimation
Fast blur kernel estimation
 40x ~ 60x faster than [Shan et al. 2008]

GPU acceleration
 600x ~ 800x faster than [Shan et al. 2008]
16 CG Lab., POSTECH

17. Motion deblurring: Common framework
Iteratively solve
1.Estimate a PSF




2.Estimate a latent sharp image using a complex image
prior
Latent image PSF Blurred image
Latent image PSF Blurred image
17 CG Lab., POSTECH

18. Motion deblurring: Common framework
Blur model




Energy function NKLB * 2
( , ) * ( ) ( )f L K B L K q L r K   
* : convolution operator
q(L), r(K) : regularization terms or priors for L, K
Latent image L Blur kernel K Blurred image B Noise N
18 CG Lab., POSTECH

19. Motion deblurring: Common framework
Latent image estimation 2
argmin * )' (
L
BLKLL q   Kernel estimation 2
argmin * )' (
K
BLK K K r  
Blurred image
Deblurred result
19 CG Lab., POSTECH

20. Blurry input Latent image
estimation of
[Shan et al. 2008]
Latent image estimation:
Analysis of prev. methods
Two important properties
Restoration of strong edges
Inspecting around strong edges,
we can find a blur kernel
Noise suppression in
smooth regions
Avoids the effect of noise
on kernel estimation
Deblurred result Blurred image Latent image
estimation
Kernel
estimation
20 CG Lab., POSTECH
Edge of a sharp image Edge of a blurred image

21. Latent image estimation:
Analysis of prev. methods
Two important properties
Restoration of strong edges
Inspecting around strong edges,
we can find a blur kernel
Noise suppression in
smooth regions
Avoids the effect of noise
on kernel estimation
Blurry input Latent image
estimation of
[Shan et al. 2008]
Deblurred result Blurred image Latent image
estimation
Kernel
estimation
21 CG Lab., POSTECH

22. Latent image estimation:
Analysis of prev. methods
Two important properties
Restoration of strong edges
Inspecting around strong edges,
we can find a blur kernel
Noise suppression in
smooth regions
Avoids the effect of noise
on kernel estimation
Computationally expensive priors for q(L)
2
argmin * )' (
L
BLKLL q  
Blurry input Latent image
estimation of
[Shan et al. 2008]
Deblurred result Blurred image Latent image
estimation
Kernel
estimation
22 CG Lab., POSTECH

23. Latent image estimation:
Basic idea for acceleration
Simple Deconvolution
Removes blur quickly
Low-quality results
Prediction
Restores strong edges
Removes noise
Simple image processing tools
We divide…
Latent image estimation
Deblurred result Blurred image Latent image
estimation
Kernel
estimation
23 CG Lab., POSTECH

24. Latent image estimation:
Basic idea for acceleration
Simple Deconvolution Prediction
Updated kernel Current kernel
Deblurred result Blurred image Latent image
estimation
Kernel
estimation
24 CG Lab., POSTECH

25. Deblurred result
Blurred image
Deblurring process
Final
deconvolution
Kernel estimation Prediction Deconvolution
* Deconvolution + prediction = latent image estimation
25 CG Lab., POSTECH

26. Results
26
Image size Blur kernel size
Processing time
(CPU)
Processing time
(GPU)
1024 x 768 49 x 47 18.656 sec. 2.125 sec.
Blurry input Our result Blur
kernel
26 CG Lab., POSTECH

27. Results
27
Image size Blur kernel size
Processing time
(CPU)
Processing time
(GPU)
972 x 966 65 x 93 18.813 sec. 5.766 sec.
Blurry input Our result Blur kernel
27 CG Lab., POSTECH

28. Results
28
Image size Blur kernel size
Processing time
(CPU)
Processing time
(GPU)
858 x 558 61 x 43 8.969 sec. 0.703 sec.
Blurry input Our result Blur kernel
28 CG Lab., POSTECH

29. Comparison (quality)
Blurry input
[Yuan et al. 2007]
* This method uses two input images.
[Shan et al. 2008] our method
29 CG Lab., POSTECH

30. Implementation Details
Requirements?
Vector/matrix calculus
Fast Fourier transform (FFT)
Image filters (bilateral, shock)
Convex optimization
Solver: Conjugate gradient method
30 CG Lab., POSTECH

31. Hojin Cho
1
Jue Wang
2
Seungyong Lee
1

1
POSTECH
2
Adobe

12th European Conference on Computer Vision (ECCV)
(to appear)

32. Introduction
Common blur model
32 CG Lab., POSTECH
Latent image l b=k*l + n Blurred image b
= ∗
Convolution
operator
Kernel k

33. Introduction
Image deblurring
33 CG Lab., POSTECH
Synthetic blurred image Deblurring result of [Levin et al. CVPR 2011]

34. Introduction
Image deblurring
34 CG Lab., POSTECH
Synthetic blurred image Deblurring result of [Levin et al. CVPR 2011]

35. Difficulties
Why is handling text difficult?
(1) Different statistics against natural images
(2) Spatial distribution of text is highly regulated
35 CG Lab., POSTECH
Natural image Text image
Log-scale
gradient histogram
Gradient
magnitude
Log-scale
gradient histogram
Gradient
magnitude
Directly applying a natural image deblurring method to a text image
will result in an erroneous result!

36. Our Approach
Exploit desired “general” properties of text images
Introduce a new optimization framework to
incorporate the text properties in deblurring
Utilizing domain-specific properties
36 CG Lab., POSTECH
Real blurred image Our result

37. Desired Properties of Latent Text Images – 1/3
Text boundary
High contrasts along the texts’ boundary
37 CG Lab., POSTECH

38. Desired Properties of Latent Text Images – 2/3
Character color
Near-uniform color inside characters
38 CG Lab., POSTECH
POSTECH
1)Near-uniform color
2)Gradients are close to zero

39. Desired Properties of Latent Text Images – 3/3
Background gradients
Too restrictive to assume a single background color (e.g.,
advertisements or posters)
Similar to the natural image
39 CG Lab., POSTECH

40. Optimization Framework
Deblurring problem
40 CG Lab., POSTECH 2
,
argmin*()()
lk
lk
bkllk ()
l
l ()
k
k
: A prior for the latent image
: A prior for the motion blur kernel 22
,,
argmin*()(( ))
l k a
lka
bkllkala ()
a
a
: prior for the auxiliary (reference) image a
: reflects the text properties a b= k*l + n
Blur model

41. Deblurring Algorithm

41 CG Lab., POSTECH
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image b
Computing l Computing a
Final Deconvolution
Result image l
•Estimating l
Restore sharp edges along the boundaries of texts
considering the text properties 1 and 2
•Estimating k
Compute the blur kernel (camera’s trajectory)
•Final deconvolution
Restores texts and background using k & b

42. Deblurring Algorithm

42 CG Lab., POSTECH
Blurred image b
Computing l
Computing a
Result image l
Blur kernel k
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image b
Computing l Computing a
Final Deconvolution
Result image l

43. Algorithm Details
Step 1: Computing l
a reflects the text properties
The text properties soak into l by solving:
43 CG Lab., POSTECH 22
argmin * ( )
l
l
b k l l l a   
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image
a plays a role as a guidance(reference) image 1 ()()()
()()(1)()()
l
kba
l
kk



 



Can be solved efficiently using FFTs and component-wise operators(multiplication/division)

44. Algorithm Details
Step 2: Computing a
Initialize a by refining l computed from Step 1
Reduce ringing artifacts and noise caused by simple deconvolution
through L0 gradient minimization
44 CG Lab., POSTECH
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image
Bilateral filter Total variation (TV) L0 gradient minimization
The result of L0 gradient minimization can provide a good initial for a
[Property 1] The boundaries of texts have large gradient values
[Property 2] Gradients inside characters are close to zero
Noise and ringing artifacts generally have small magnitudes, thus being reduced
* The figures are provided in [Xu et al., SIGGRAPH Asia 2011]

45. Step 2: Computing a
With the initial a, we iteratively solve:
Algorithm Details
45 CG Lab., POSTECH 2
argmin( )
a
a
ala ()
a
a
: a cost function which is minimized when a satisfies the text image properties
: a data term to penalize non-similarity between a and l 2
la P
MAX
0 if =
()
otherwise
ii
ai
aa
a
d



 P
a
: an ideal image satisfying the text image properties 1 & 2 completely.
For each pixel at i,
After minimizing the equation,
a will reflect the text image properties while preserving the similarity against l
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image

46. Computing the ideal image a
P
:
Detect text regions from l using the stroke width transform (SWT)






For detected text regions (connected strokes), we force the pixels
to have the same color value
Algorithm Details
46 CG Lab., POSTECH
Typical stroke Searching in the direction
of the gradient at edges
Detected stroke width
Through the SWT and re-coloring, the ideal image satisfies the following properties:
[Property 1] The large gradient around the boundaries of text characters
[Property 2] Colors are near uniform inside text characters
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image

47. Algorithm Details
47 CG Lab., POSTECH 2
argmin( )
a
a
ala ()
a
a
: a cost function which is minimized when a satisfies the text image properties
: a data term to penalize non-similarity between a and l 2
la
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image P
MAX
0 if =
()
otherwise
ii
ai
aa
a
d




where 2
PP
* MAX
if
otherwis

e
i i i
i
i
a d l a
a
l






For each pixel at i,
Solution

48. Algorithm Details
Computing k
Adopted from [Shan et al. SIGGRAPH 2008] and [Cho and
Lee, SIGGRAPH Asia 2009]




The auxiliary image a is used instead of the latent image l
a contains less ringing artifacts and noise due to the L0 gradient
minimization
48 CG Lab., POSTECH { , , , , }
x y xx xy yy
       *
*
2 2
**
()
() * ,Ek bk a k



Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image

49. Algorithm Details
Final deconvolution
Given the estimate kernel and the input blurred image, we
minimize:
49 CG Lab., POSTECH { | ( ) 0}
ai
T i a 2 2 2 0.8
1 2 3
()*
i ii i
iT iT iT
Elbkllla l 
  

(1)
(1): [Property 1 & 2] Gradient values inside each character should be close to zero
(2)
(2): [Property 1 & 2] Each character has a near-uniform color
(3)
(3): [Property 3] Gradient values of background are sparse
Estimating l
Kernel Estimation
Estimating k
Input
Blurred image
Computing l Computing a
Final Deconvolution
Result image l
: Set of pixel indices for text regions

50. Results
Synthetic example
50 CG Lab., POSTECH
Deblurring result of [Levin et al. CVPR 2011] Our result

51. 51
Original image
Synthetic blurred image
Fast motion deblurring result
Our result

52. Results on Real Photographs (1/4)

52
Blurred image
Our result

53. Results on Real Photographs (2/4)

53
Blurred image Our result

54. Results on Real Photographs (3/4)

54
Blurred image Our result

55. Results on Real Photographs (4/4)

55
Blurred image
Our result (very large blur: 105x105)

56. Comparison – Real Images

Fergus et al.
SIGGRAPH 2006
Shan et al.
SIGGRAPH 2008
Cho and Lee
SIGGRAPH Asia 2009
Xu and Jia
ECCV 2010
Levin et al.
CVPR 2011
Our method
Blurred image
Chen et al.
CVPR 2011
56 CG Lab., POSTECH

57. Comparison – Real Images

Fergus et al.
SIGGRAPH 2006
Shan et al.
SIGGRAPH 2008
Cho and Lee
SIGGRAPH Asia 2009
Xu and Jia
ECCV 2010
Levin et al.
CVPR 2011
Our method
Blurred image
Chen et al.
CVPR 2011
57 CG Lab., POSTECH

58. Comparison – Real Images

Fergus et al.
SIGGRAPH 2006
Shan et al.
SIGGRAPH 2008
Cho and Lee
SIGGRAPH Asia 2009
Xu and Jia
ECCV 2010
Levin et al.
CVPR 2011
Our method
Blurred image
* Since Chen et al.’s approach requires training, re-implementing it is impossible without having the training data.
Chen et al.
CVPR 2011
Not available

59. Comparison – Real Images

* Since Chen et al.’s approach requires training, re-implementing it is impossible without having the training data.
Not available
Fergus et al.
SIGGRAPH 2006
Shan et al.
SIGGRAPH 2008
Cho and Lee
SIGGRAPH Asia 2009
Xu and Jia
ECCV 2010
Levin et al.
CVPR 2011
Our method
Blurred image
Chen et al.
CVPR 2011

60. Comparison – Real Images

Not available
Not available Not available
* The methods of Shan et al. and Levin et al. could not handle this image.
* Since Chen et al.’s approach requires training, re-implementing it is impossible without having the training data.
Fergus et al.
SIGGRAPH 2006
Shan et al.
SIGGRAPH 2008
Cho and Lee
SIGGRAPH Asia 2009
Xu and Jia
ECCV 2010
Levin et al.
CVPR 2011
Our method
Blurred image
Chen et al.
CVPR 2011

61. Conclusion
Previous natural image deblurring methods do not work well
for text images
Due to the lack of consideration of text-specific properties
We analyzed the desired properties for latent text images
We proposed a novel text image deblurring algorithm which
explicitly incorporates the text-specific properties into the
optimization framework
61 CG Lab., POSTECH

62. Applications

62 CG Lab., POSTECH

63. Q & A
http://cg.postech.ac.kr