Sparse Image Approximation in 3D

This site hosts two different implementations of the Orthogonal Matching Pursuit (OMP) strategy, for the approximation of 3D images. In addition to a standard implementation, here dedicated to operate with separable dictionaries in 3D (OMP3D) the low memory version of the same approach, termed Self-Projected Matching Pursuit is also extended to 3D (SPMP3D). Both implementations have been shown appropriate for the simultaneous approximation of colour images. By approximating a classic data set, this project demonstrated that the sparsity achieved by the simultaneous approximation of three colour channels is significantly higher than that achieved by approximating each channel independently. The gain in sparsity comes at expenses of computational complexity. Hence, since the approximation is carried out on a partition of the image, the possibility of massive palletization with GPU was investigated.

The project was developed by Daniel Whitehouse, as dissertation for his the BSc (Hons) Computer Science and Mathematics degree, at Aston University. It was supervised by Laura Rebollo-Neira (Mathematics Department) and George Vogiatzis (Computer Science Department). The main deliveries are:

• Production of C++ MATLAB executables for the SPMP3D and OMP3D approaches, which significantly increased performance compared to the stand alone MATLAB implementation.

• An original investigation into the benefit of approximating 3 channel colour images simultaneously, instead of approximating each colour independently.

• A study into the feasibility of using the GPU and fast-access memory for the SPMP3D routine.

• Development of a CUDA enabled command line application for calculating the sparsity ratio of a given image using the plain Matching Pursuit algorithm dedicated to 3D (MP3D). In addition, an extension to fully support the SPMP3D algorithm has been outlined.

The full report can be downloaded here.

Below is an example of an approximation made with SPMP3D when the projection is taking place at every iteration. This is equivalent to the OMP3D method. The target PSNR is 47dB with a square block size of 8 x 8. The achieved Sparsity Ratio (SR) was 19.6 when processing the 3 colours simultaneously with a dictionary of redundancy 125.

Original Image

heic1209a.png courtesy of the ESA - https://www.spacetelescope.org/

Approximated Image

Other Approximations:

PNSR : 40dB - Sparsity Ratio : 64.61166

PNSR : 45dB - Sparsity Ratio : 32.5186

PNSR : 55dB - Sparsity Ratio : 6.1855

PNSR : 75dB - Sparsity Ratio : 2.239

Licence:

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. See http://www.gnu.org/licenses/.

SIA_3D