Monday, October 6, 2014

Robust Digital Image Reconstruction Example

In this post, we discuss how to employ the digital image reconstruction technique of Chandra et al. (2014):

Robust digital image reconstruction via the discrete Fourier slice theorem
S Chandra, N Normand, A Kingston, JP Guedon, I Svalbe
IEEE Sig. Proc. Lett. (2014)

using the FTL (implemented in C, available via LGPL license).

This method takes a sufficient set of discrete (rational angle) projections assuming the Dirac pixel model, i.e. digital image sampling where lines have said to have sampled a pixel iff the line goes through the centre of the pixel, and reconstructs them in O(nlogn), where n=N^2. Sufficiency is classified as those projections meeting the Katz criterion, i.e. basically all bins are sampled at least once and no unambiguous  solution (i.e. a ghost) cannot fit within the image. See also:

Fast Mojette transform for discrete tomography
SS Chandra, N Normand, A Kingston, J Gu├ędon, I Svalbe
arXiv preprint arXiv:1006.1965

Once you have FTL built, you should have four binaries for this method:

  • fmt_angles - Select the angle type and generate the rational angles for given n and N, the image and reconstruction (FFT space) sizes respectively.
  • mt - Compute the discrete (rational angle) projections of the image, also known as the Mojette transform (MT).
  • mt2frt - Convert the projections to those of the FRT/DRT, which are the inverse FFTs of the slices of the 2D FFT.
  • ifrt - To reconstruct the resulting FRT projections in O(nlogn), no relation to the n before.

To illustrate the process we given a tutorial here of the whole process.

1. First, we crop Lena image to a 128x128 image of Lena from the centre:

./crop lena512.pgm 128 128 0 lena128.pgm

2. We create the angle set, we choose the L1 minimal set since it has a nice symmetry:
./fmt_angles 128 256 1 mt_angles_128_in_256.txt
3. Next we compute the MT:
./mt lena128.pgm mt_angles_128_in_256.txt mt_lena128.pgm
    Note that if you already have projections, such as those of a sinogram, then see this Google Groups     discussion. You can find the publication by my colleague Andrew Kingston on how to do this here.
4. Convert the MT projections into FRT space
 ./mt2frt mt_lena128.pgm mt_angles_128_in_256.txt 128 256 1.0 frt_lena128.pgm
5. Invert the FRT projections in O(nlogn) using the discrete Fourier slice theorem
./ifrt frt_lena128.pgm recon_lena128.pgm

This gives our nxn result reconstructed and padded into the NxN space.

EDIT: See my other post about visualising these and FTL (or PGM files) results in general.

Cheers Shakes - L3mming


  1. Hi Shakes,

    I have the following problem: after installing FTL and testing frt:

    ../bin/frt lena128.pgm frt_lena128.pgm
    >| Dyadic Fast RT Program.
    >| Copyright Shekhar Chandra, 2008-9
    >| Machine Integer Size of 64 bits
    >| Using 32-bit mode.
    Opening File: lena128.pgm as ASCII.
    File Type: P5
    File Size: 128x128, Grey Scale Max: 255
    >| Transforming... Done. Time: 3926 usecs.
    >| Isum: 0.
    Opening File: frt_lena128.pgm as ASCII.
    >| Operation Complete

    eog lena128.pgm # original image OK
    eog frt_lena128.pgm # the resulting image is black

    What can be the reason?

    Cheers, Igor.

  2. Thanks for trying out FTL Igor. Most common image viewers read the 8-bit PGM and so can't show the 32-bit integer values that FTL needs (since FRT is sum of p 8-bit values). I have written a quick post on visualising FTL PGMs on this blog:

    That might be of benefit to others.