Links

Home

Publications

Research

Gallery

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

　

 Image Modeling and Enhancement via Structured Sparse Model Selection

　

Guoshen Yu, Guillermo Sapiro and Stéphane Mallat

　

　

An evolved version of this work:

G.Yu, G. Sapiro, S. Mallat, Solving Inverse Problems with Piecewise Linear Estimators: From Gaussian Mixture Models to Structured Sparsity, submitted to IEEE Trans. on Image Processing, 2010.

　

　

Structured Sparse Model Selection (SSMS) in a few words:

　

Structured sparse model selection (SSMS) is a novel sparse image representation framework. The corresponding modeling dictionary, as illustrated in Fig. 1,  is comprised of a family of learned orthogonal bases. For an image patch, a model is first selected from this dictionary through linear approximation in a best basis, and the signal estimation is then calculated with the selected model.

　

　

  

　

Fig. 1. Sparse signal models. Left: the conventional overcomplete dictionary model. In
this model any sparse set of atoms (columns in gray) can be selected. Right:
the structured sparse model selection model (SSMS). In this model, the dictionary
is comprised of a family of orthogonal bases, only one selected at a time.
The model selection is calculated with linear approximation in a best basis,
i.e., only the first few atoms of one basis (in gray) can be selected.

　

　

     SSMS has the following features:

　

  • Sparse image representation.

As most state-of-the-art image representation models, SSMS provides sparse representations for images.

  • Structured and stable representation.

SSMS is much more structured and therefore more stable than conventional sparse image models.  The degree of freedom in the model selection is equal to the number of the bases, typically about 10 for natural images, and is significantly (>1010 times) lower than with traditional overcomplete dictionary approaches, stabilizing the representation.

  • Fast computation.

Calculation of the SSMS image representation is very fast, in the same order of with an orthogonal transform. For an image patch of size √N ×√N, the computational complexity of the proposed framework is O(N2), typically 2 to 3 orders of magnitude faster than estimation in an overcomplete dictionary.

  • Adapted to the image of interest.

As most state-of-the-art sparse image models, the SSMS dictionary is adapted to image of interest.

  • Optimality.

SSMS denoising estimate is mathmatically near optimal relative to an oracle estimate.

  • Simple and fast SSMS dictionary learning.

The SSMS dictionary is learned with a simple and fast (non-iterative) procedure. Again the dictionary learning procedure is typically 2 to 3 orders of magnitude faster than conventional overcomplete dictionary learning. Moreover, additional image training dataset is not required.

  • Better comprehensibility.

        The orthogonal bases in the SSMS dictionary have clear interpretation. Each basis captures a feature of the image, for example contours at a certain orientation.

  • State-of-the-art image enhancement results.

On the top of all the features above, state-of-the-art image denoising, inpainting, and deblurring have been obtained with SSMS.

　

　

References:

　

Experimental results:

　

I. Denoising

　

Degraded images are contaminated by Gaussian white noise of standard deviation σ. From left to right: original image, noisy image, SSMS denoising results.

　

Lena (original)

　

Noisy (σ=10) 28.13 dB

　

SSMS denoising 35.60 dB

　

Zoom (original)

　

Noisy (σ=10) 27.98 dB

　

SSMS denoising 34.21 dB

　

Barbara (original)

　

Noisy (σ=20) 22.13 dB

　

SSMS denoising 31.24 dB

　

Zoom (original)

　

Noisy (σ=20) 22.15 dB

　

SSMS denoising 30.56 dB

　

　

　

　

　

II. Inpainting

　

Degraded images are randomly masked by 60%. Inpainting seeks to fill the "holes" in the mask. From left to right: original image, masked image, SSMS inpainting results.

　

Lena (original)

　

60% randomly masked 7.90 dB

　

SSMS inpainting 36.02 dB

　

Zoom (original)

　

60% randomly masked 6.28 dB

　

SSMS inpainting 37.12 dB

　

Zoom (original)

　

60% randomly masked 6.86 dB

　

SSMS inpainting 35.65 dB

　

Barbara (original)

　

60% randomly masked 8.64 dB

　

SSMS inpainting 34.50 dB

　

Zoom (original)

　

60% randomly masked 10.14 dB

　

SSMS inpainting 33.31 dB

　

　

　

　

III. Deblurring

　

Degraded images are blurred by a Gaussian kernel of standard deviation σb and contaminated by Gaussian white noise of standard deviation σn. Image boundaries of width 8 are cropped to avoid border effect. From left to right: original image, blurred and noisy image, SSMS deblurring results.

　

Zoom (original)

　

Blurred and noisy (σb=1, σn=5) 30.61 dB

　

SSMS deblurring 34.20dB

　

Zoom (original)

　

Blurred and noisy (σb=1, σn=5) 30.26 dB

　

SSMS deblurring 34.76 dB

　

Zoom (original)

　

Blurred and noisy (σb=1, σn=5) 28.30 dB

　

SSMS deblurring 32.11 dB

　

Zoom (original)

　

Blurred and noisy (σb=1, σn=5) 28.26 dB

　

SSMS deblurring 33.00 dB

　

　

　

　

Comparison with state-of-the-art methods

　

I. Denoising

　

　

　

　

Denoising performance (in PSNR). Top left: NLmeans [2]. Top
right: GSM [8]. Bottom left: learned overcomplete dictionary [3]. Bottom
right: the proposed SSMS denoising [1] . In each set the best result is in bold.

　

　

II. Inpaiting

　

　

Inpainting performance (in PSNR). Top left: [5]. Top right:
EM [9]. Bottom left: MCA [4]. Bottom right: the proposed SSMS inpainting [1] .
In each set the best result is in bold.

　

III. Deblurring

　

　

Deblurring performance (in PSNR). The left column specifies the
std of the Gaussian blur kernel σb and of the Gaussian white noise σn. Top
left: ForWaRD [7]. Top right: the proposed SSMS deblurring (without super-resolution) [1] .
Bottom left: DSD [6]. Bottom right: the proposed SSMS super-resolution
deblurring [1]. In each set the best result is in bold.

　

　

　

　

References

[1] G.Yu, G. Sapiro and S. Mallat, Image enhancement via structured sparse model selection, submitted to IEEE International Conference on Image Processing (ICIP), 2010.

[2] A. Buades, B. Coll, and J.M. Morel. A review of image denoising algorithms, with a new one. SIAM MMS, 4(2):490–530, 2006.

[3] M. Elad and M. Aharon. Image denoising via sparse and redundant representations over learned dictionaries. IEEE Trans on Image Processing, 15(12):3736–3745, 2006.

[4] M. Elad, J.L. Starck, P. Querre, and DL Donoho. Simultaneous cartoon and texture image inpainting using morphological component analysis (MCA). ACHA, 19(3):340–358, 2005.

[5] O.G. Guleryuz. Nonlinear approximation based image recovery using adaptive sparse reconstructions and iterated denoising-Part II: Adaptive algorithms. IEEE Trans on Image Processing, 15, 2006.

[6] Y. Lou, A. Bertozzi, and S. Soatto. Direct sparse deblurring. Technical Report, CAM-UCLA, 2009.

[7] R. Neelamani, H. Choi, and R. Baraniuk. Forward: Fourier-wavelet regularized deconvolution for ill-conditioned systems. IEEE Trans on signal processing, 52(2):418–433, 2004.

[8] J. Portilla, V. Strela, M.J. Wainwright, and E.P. Simoncelli. Image denoising using scale mixtures of Gaussians in the wavelet domain. IEEE Trans on Image Processing, 12(11):1338–1351, 2003.

[9] M.J. Fadili, J.L. Starck, and F. Murtagh. Inpainting and zooming using sparse representations. The Computer J, 52(1):64, 2009.