Recovery of images from few pixels
Branch: master
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
pics
.gitignore
LICENSE
README.md
demoIT.ipynb
demo_image_compression.ipynb
pit.py

README.md

pit --- Pictures: Iterative Thresholding algorithms

A compressed sensing based image recovery demonstration

Author: Martin Kliesch

A simple and fast implementation of the iterative hard and soft threosholding algorithms (IHT and ISTA) for image recovery. It provides:

  • Reconstructions of images from few of their pixels (masked images) (see the Jupyter notebook demoIHT.ipynb for a working example)
  • It relies on the images being sparse under
  • Possible thresholding operations:
    • Hard thresholding (IHT)
    • Soft thresholding (ISTA)
  • A demonstration of the functioning of image compression is included (Jupyter notebook demo_image_compression.ipynb)

How to run it

A simple example can be found in the Jupyter notebook demoIHT.ipynb.

Description of what it does

Given a picture (left image) we remove a large number of its pixels (middle image). Then we can reconstructs the image (right image) from the middle one; see the Jupyter notebook demo_image_compression.ipynb on how it is done.

Given picture 95% of its pixels removed Reconstruction

How it works (theory)

Images are compressible (see demo_image_compression.ipynb for an illustration). Effectively, the reconstruction algorithms of pit search for an image in the space of compressed images that is compatible with the given pixels.

Mathematical description

Let T be an invertible transformation taking images to vectors so that the vectors are sparse (i.e., many coefficients are zero) and let iT be the inverse of T. Examples for such a T are the DCT and many versions of the WT. Moreover, let TO be a thresholding operator (hard or soft thresholding).

Suppose we are given a subset of pixels Xsub of an image Xorig and the indices mask of these pixels. Then the reconstruction algorithm pit.estimate essentially does the following iteration:

X = Xsub
repeat
    x = TO( T(X) )
    X = iT(x)
until a stopping criterion is met

For certain transformations T this algorithm essentially solves the problem:

minimize     norm( T(X), L1 )
subject to   norm( X(mask) - Xsub, Frobenius) <= eta

In order to rigorously guarantee this procedure to work T needs to satisfy certain properties. If X is sparse and there are enough pixels in Xsub (depending on the sparsity of X) then the minimum is attained for Xrec that is eta-close to X in Frobenius norm.

Acknowledgment

I thank Stephan Wäldchen for discussions. This project has been funded by the National Science Centre, Poland (Polonez 2015/19/P/ST2/03001), i.e., This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No. 665778.

 

References

  • S. Foucart and H. Rauhut, A mathematical introduction to compressive sensing (Birkhäuser, 2013)
  • J. Bobin, J.-L. Starck, and R. Ottensamer, Compressed Sensing in Astronomy, arXiv:0802.0131
  • A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2(1), 183–202 (2009)