Image approximation

Example to illustrate the use of the method Hierarchized Block-Wise Orthogonal Matching Pursuit (HBW-OMP), for approximating images. The details of the algorithm are given in the paper:

'Hierarchized block wise image approximation by greedy pursuit strategies'
by Laura Rebollo-Neira and Ryszard Maciol and Shabnam Bibi

The method is suitable for approximating partitions on a transformed image. It evolves by selecting, at each iteration step, i)the elements for approximating each of the blocks partitioning the image and ii) the hierarchized sequence in which the blocks are approximated to reach the required global condition on sparsity.

For images which are highly compressible in the wavelet domain the improvement produced by HBW-OMP , in relation to standard block independent OMP, is massive . Moreover, as illustrated by the examples below, approximations by blocking in the wavelet domain avoid visually unpleasant blocking artifacts in the intensity image.

All the source files of the routines to run examples in MATLAB applying the HBW-OMP and HBW-MP methods with a separable dictionary (HBW-OMP2D and HBW-MP2D) are available in the archive HBW.zip. A C++ MEX version of HBW-OMP2D is also provided. The script Example_HBW.m, runs the example on the "butterfly" image, kindly provided by national geographic website.

The dictionary used in this example is composed of a Redundant Discrete Cosine component and a Dirac Basis (RDCDB) dictionary.

script Example_HBW
%Example of the approximation of an image, in the wavelet, domain using HBW-OMP2D and HBW-MP2D.
%The execution times resulting from running this example using a laptop with 3GB of
%RAM  with a 2.2 GHz Intel Processor are shown below.
%HBW-OMP2D (MATLAB implementation dedicated to separable dictionaries, method = 1):11.61. seconds
%HBW-OMP2D_Mex (C++ Mex File for faster implementation of HBW-OMP2D:11.61. seconds

% Path to the image to be approximated
    ImagePath = 'butterflies-zebra.jpg';

% HBW-Method for approximation: 1 is HBW-OMP, 2 is HBW-MP.
    method = 1;

%Side of blocks in the partition
    BlockWidth = 8;

% MaxNum is total number of atoms for the approximation
% If SR is the desired Sparsity Radio then  MaxNum=ImageSize/SR 
MaxNum =18575;


% Approximate the image
    Example_HBW.;

Results of approximation taking 11.68 seconds (  if the Mex file is used)
Sparsity Ratio (SR) -> 14.47 
Peak Signal to Noise Ratio (PSNR) -> 45.0dB

The images below are the outcomes of approximations, up to 45.0dB, with the simple 
RDCDB dictionary.  Notice that, in addition to being significantly 
less sparse, the approximations in the pixel domain are affected by noticeable
blocking artifacts.
Butterfly image approximated  by HBW-OMP in the wavelet domain (SR=14.47) 

Butterfly image approximated by HBW-OMP  in the pixel domain (SR=12.7)

Original grey levels Butterfly image

Planet image approximated by HBW-OMP in the wavelet domain (SR=92.9) 

Planet image approximated  by HBW-OMP in the pixel domain (SR=31.0)

Original grey levels Planet image

Flower image approximated  by HBW-OMP in the wavelet domain (SR=181.5)

Flower image approximated  by HBW-OMP in the pixel domain (SR=43.9)

Original grey levels Flower image

Highly Nonlinear Approximations for Sparse Signal Representation

Image approximation