Tom Frese, June 8, 2001. frese@ecn.purdue.edu


This AWGM software package contains code for
Bayesian tomographic reconstruction using an
Adaptive Wavelet Graph Model (AWGM) prior. 
The prior model and reconstruction algorithm are described
in detail in T. Frese, C. A. Bouman and K. Sauer, 
'Adaptive Wavelet Graph Model for Bayesian Tomographic 
Reconstruction', to appear in IEEE Transactions on 
Image Processing.


Included in the package AWGM.tar.gz is 
a package called AGTREE which contains software
to generate and use agglomerative tree 
classifiers/predictors which are needed by
the AWGM package. See AGTREE/README for
details.


For information on the EXAMPLES supplied,
see the file EXAMPLE/README.EXAMPLES.




This README file contains the following sections:

I.   Overview AWGM model and multiresolution reconstruction
II.  Package contents
III. Using the reconstruction program 'tomo'
IV.  Training the model 
V.   Size of prediction window
VI.  Number of resolution scales
VII. Known problems

---------------------------------------------------------


I. Overview AWGM model and multiresolution reconstruction
---------------------------------------------------------

The adaptive wavelet graph (AWGM) prior model
is a hierarchical image model formulated in
the wavelet domain. The basic idea of the model
is to perform edge-preserving regularization
by adapting the degree of regularization
performed to the local image characteristics.
The AWGM exploits interscale dependencies of wavelet
coefficients. Specifically, the AWGM models the 
conditional distribution of the wavelet coefficients
at each scale and location given a window of scaling 
coefficients at the next coarser scale. 
The conditional distributions of the triplets of 
wavelet coefficients at each scale and location are 
modeled as multivariate Gaussians. These Gaussian 
distributions have space- and scale-varying parameters. 
These parameters specify the mean of the triplet of 
wavelet coefficients as a function of the coarse 
scale scaling coefficients as well as a covariance 
matrix for the triplet. Note, that these parameters
do NOT specify the mean of the wavelet coefficients 
as a number, but instead, the conditional mean 
as a function(!) of the coarse scale data.

The parameters of the Gaussian distributions are 
selected using a non-linear prediction method based
on agglomerative cluster trees (AGTREE package).

The non-linear predictors are obtained in a training
phase. The training requires a set of training images
in matlab format and can be performed with the 'train'
program in this package. 
As supplied, the model is pre-trained and can 
be used for tomographic reconstruction as is.

The tomographic reconstruction (program 'tomo')
is performed in a multiresolution coarse-to-fine
scale fashion. The program first computes a 
maximum-likelihood reconstruction at the coarsest
scale. This reconstruction is fed into the non-linear
tree predictors to obtain the prior parameters for the
next finer scale. Given these prior parameters,
Bayesian MAP reconstruction of the image is performed at
the next finer scale using the wavelet graph prior model
at the coarser scale(s). The reconstruction is then 
again used to initialize the prior parameters and the
reconstruction at the next finer scale. 
This process continues until the
finest scale is reconstructed.

Importantly, for the reconstruction at each scale,
the data values at the coarser scales are NOT fixed.
Instead, only the prior adaptation, i.e. the parameters
of the conditional Gaussian distributions are fixed.

The reconstruction at each scale is performed using an
iterative coordinate descent (ICD) algorithm in the 
space domain, i.e. the optimization is performed 
over the scaling coefficients at the reconstruction scale.
The wavelet graph prior model is taken into account 
using the chain rule. The space-domain optimization
allows for efficient enforcement of pixel positivity.

For a more detailed description, see the paper
'Adaptive Wavelet Graph Model for Bayesian Tomographic 
Reconstruction', to appear IEEE Trans. Image Proc.







II. Package contents
-----------------------------------------------------

The AWGM package contains

1) Source code for reconstruction and training. 
   To compile the code, see README.INSTALL in this
   directory. Compiling the code will
   generate the programs
   AWGM/bin/tomo: program for tomographic reconstruction
   AWGM/bin/train: program to train the model

2) EXAMPLE subdirectory: this directory contains
   simulated projection data and shell scripts
   that demonstrate the use of the tomo program.
   Also supplied is an example configuration file
   for training the model. See EXAMPLE/README.EXAMPLES
   for more details.

3) The model is pre-trained. The training results
   are stored in the directory AWGM/tree_dat. The
   training information is in ASCII format but not meant
   for manual interpretation. The tomo program
   will automatically read these files.

4) AGTREE package: This package is required by both
   the tomo and train programs. AGTREE must be compiled
   before compiling the AWGM package.

While the general AWGM model can be used with basically
any wavelet basis, the software provided here is limited
to the Haar wavelet decomposition.








III. Using the reconstruction program 'tomo'
-----------------------------------------------------------

   After compilation you will find a file 'AWGM/bin/tomo'
   Typing 'bin/tomo' at the command prompt 
   will return the command-line syntax:
   -------------

   Usage:
   
   tomo [-i no_iter at finest scale (15)] [-r resolution (256)] 
        [-f field_of_view_mm (n_t*delta_t)] 
        [-s regularization parameter (1.0)] 
        [-w relative weight of expected conditional covar (0.001)] 
        [-T attn_file] [-t gound_truth_file] [-d write_wav_decomp] 
        input.mat mask.mat output.mat
  
   Note that parameters in brackets [ ] are optional where
   the value in () is the default used if the parameter is not
   specified in the command line. 
   A detailed description of the syntax is listed below:

1) input.mat
------------
   Filename for file containing the sinogram data 
   (e.g. EXAMPLE/data/mri_sino_m.mat).
   The matlab file must contain the following variables:

   counts	sinogram matrix, rows=displacements, cols=angles  
   
   n_t          number of displacements (#rows in counts)
 
   n_theta      number of projection angles (#cols in counts)

   delta_t      projection spacing (displacement in mm)

   delta_theta  angular projection spacing (in rad)
                typically, delta_theta=pi/n_theta

   scatter      single value for scatter correction
                (this is the value for
                a single projection count, e.g. what would be 
                subtracted from each count before FBP recon).

   t_0          displacement of first projection, i.e. for first 
                row of counts matrix, in mm. For a centered projection array,
                this should be 
                  t_0 = -1.0*(n_t - 1))/2.0 * delta_t;

   theta_0      first projection angle, i.e. angle corresponding to
                first column of counts matrix.




2) mask.mat
------------
   Filename for binary mask specifying approximate support
   of the object to be reconstructed. This mask is necessary
   to compute an amplitude normalization factor that is applied
   before the scaling coefficients are fed into the non-linear
   predictors.

   The file mask.mat should contain a matrix named 'mask'
   with the same size as the specified reconstruction resolution
   and of type double. The data values should be 1 over the
   support of the object to be reconstructed and 0 elsewhere.
   An example is given in EXAMPLE/data/mri_mask_m.mat.

   A mask file can be obtained from an initial reconstruction
   of the phantom. An initial reconstruction can be obtained
   using filtered backprojection (using package CBP_PU) or using the
   tomo program itself. To obtain an initial reconstruction
   using the tomo program, use a mask of all ones and perform only
   1-3 iterations. 
   Once you have an initial reconstruction, you can use the 
   matlab program AWGM/support/support.m to extract the mask.
   See AWGM/support/support.m for comments.


3) output.mat
-------------

   Filename for the reconstruction output. This file will be written at
   the end of the execution of tomo and will contain an 'X0'
   matrix with the Bayesian reconstruction at the finest scale.
   In addition, the file will contain the matrices X1 though X4
   with the reconstructions at the coarser scales.

   Note, that since an orthonormal Haar wavelet decomposition
   is used, the amplitude scaling is different for the different
   scales. For a constant image, the scaling would increase
   by a factor of two from scale to scale.

   Specifying the -d option on the tomo command-line results in 
   additional diagnostic output: 

   Z0_0 - Z3_2 : Zn_k is the matrix of wavelet coefficients of 
                 reconstruction. Zn_k contains the wavelet coeffs at
                 scale n with orientation k (k: 0=vertical,1=horizontal,
                 2=diagonal Haar coefficient). 

   Zm0_0-Z3_2  : Mean values of wavelet coefficients based
                 on last adaptation step and current 
                 coarse scale values.

   Xip0-Xip3   : 'Interpolated images' obtained based on reconstructed
                 next coarser scale and predicted prior mean values.
                 For example, Xip0 is obtained as a single-scale wavelet 
                 reconstruction using X1 and the wavelet coeff. means
                 Zm0_0,Zm0_1,Zm0_2. This is essentially the mean
                 interpolation performed by the prior model (final state).
  
   Zivar0_0-Zivar3_2: Inverse conditional variances of wavelet prior.
                 For example, Zivar0_1 is the inverse prior 
                 (conditional) variance of the wavelet horizontal 
                 wavelet coefficients at scale 0. 
                 The conditional standard deviation of these coefficients
                 is then given by sqrt(1./Zivar0_1) .
                   
   Specifying the -d -t <groundtruth> file option allows to also
   include the wavelet decomposition of a ground truth image 
   into the output file for comparison purposes. The matrices 
   Xt0-Xt4 and Zt0_0-Zt3_2 contain the decomposition of the 
   specified ground-truth image and are the equivalent of 
   of X0-X4 and Z0_0-Z3_2. (Specifying -t without -d will 
   only write Xt0-Xt4. Option -d adds Zt0_0-Zt3_2).
   The optional ground-truth image will not be used for the reconstruction,
   but will only be included into the output file.



4) Options
----------
   -i <value>	Number of ICD reconstruction iterations N_0
                at the finest scale k=0. The number of 
                iterations at the coarser scales k is 
                N_k = N_0*(sqrt(2))^k
                Default is N_0=15 iterations.

   -r <value>   Resolution of the reconstruction (number of pix
                in each direction, e.g. -r 256 will generate a 
                256x256 pixel reconstruction image). 
                The model was trained using 256 x 256 pixel
                images, so reconstruction at that resolution 
                will probably yield the best results. For
                other reconstruction resolutions, it might be
                necessary to retrain the model accordingly.
                The resolution must be a power of
                two or at least contain a factor of 
                2^(PYR_LEVELS-1) = 2^4.
                
   -f <value>   Field of view of the reconstruction in mm. 
                The default (if -f not specified) is 
                to reconstruct the entire field of view of the
                sinogram which is n_t*delta_t.

   -s <value>   Regularization parameter sigma. Higher values
                of sigma mean less smoothing, lower values imply
                more smoothing. Typically, s is chosen to be >= 1.0.
                If you obtain strong blurring for very discrete data
                such as a bar phantom, try a higher sigma value
                such as -s 6. 
                The functionality of the sigma value is to uniformly
                scale the prior variances of the wavelet coefficients.
                If R_0 is the nominal conditional covariance matrix 
                for a given triplet of wavelet coefficients obtained
                from the prediction tree, the scaled covariance 
                which is actually used is R=(sigma^2)*R_0.

   -w <value>   Regularization factor w to increase robustness of
                covariance estimates. The covariance estimates
                obtained during training for each tree node are not
                always robust, particularly, when training is performed
                on binary or discrete-values training images. 
                A more robust estimate is the expected conditional
                covariance over ALL nodes. The w factor allows
                forming a convex combination:

                R = (sigma^2)* ( (1.0-w)*R_1 + w*R_2 )

                where R_1 is the node covariance matrix from the tree
                and R_2 is the expected conditional covariance
                matrix over all nodes 
                (stored in tree_dat/clust_ln.asc_Evar).
 
                The w value must be between 0 and 1.0.
                In most cases a small, fixed value of 0.001 should
                work fine. If the training is performed using 
                binary or discrete data, a larger factor 
                may be necessary (0.1-0.3).
                
                
   -T <fname>   Attenuation correction with sinogram in <fname>.
                fname must specify a .mat file containing a 
                matrix called 'trn'. This matrix must have the
                same dimensions as the 'counts' matrix in the 
                emission data file input.mat. The trn counts
                are typically obtained by forward projecting
                a transmission reconstruction. The trn matrix
                should be such that, for FBP reconstruction,
                one would precorrect the emission data by taking the
                ratio counts/trn. NOTE: FOR Bayesian reconstruction, 
                the emission data should NOT be precorrected! 
                
    -t <fname>  Specify a file containing a ground-truth image whose
                wavelet decomposition should be included in the
                output.mat file. This can be used for testing purposes
                to compare the wavelet decomposition of the 
                reconstruction to that of the true image. The optional
                ground-truth image is not used for the reconstruction.
                The ground-truth file must be a .mat matlab file
                containing a matrix named 'img' of the same size
                as the specified reconstruction resolution.

     -d         Diagnostic output: when this option is used, 
                the output file will not only contain the 
                reconstruction images at
                different resolutions, but also the wavelet 
                coefficients as well as the prior means and 
                covariance matrices. (see section on output file above).


5) Projection matrix computation
---------------------------------

   The tomo reconstruction algorithm computes
   the tomographic projection matrix not using 
   line integrals, but rather, assuming a triangular
   projection kernel of width 2.34mm. 
   
   The integrals of the projection kernel 
   over the pixel area are (pre-)computed 
   by subsampling the pixels by a factor of 15 in
   each direction and summing the values of the
   projection shape function at the centers of the
   subsamples multiplied by their area.

   The width of the triangular projection profile can
   be set by modifying the define statement
      #define PRJ_WIDTH 2.34
   in ansi_lib_loc/A_comp_dbl_storeflt.c.
 
   The shape can be changed by modifying the 
   subroutine 'proj_shape' in ansi_lib_loc/A_comp_dbl_storeflt.c.




IV.  Training the model 
---------------------------------------------------------------

1) Description of training process 
----------------------------------

  The AWGM/bin/train program can be used to (re-)train the
  model. The train program requires a set of training images
  and associated masks that specify the object support in these
  images. The train routine calculates the wavelet decomposition
  of the training images to extract training vectors. A training
  vector is extracted for each triplet of wavelet coefficients
  at each scale and location. The training vector for each triplet
  consists of the scaling coefficients in the coarse scale 
  prediction window centered over the triplet (x-part of vector) 
  and the triplet of wavelet coefficients (y-part of vector). 
  The sets of training vectors are written to disk
  separately for each scale (see code in src/interface_agtree.c). 
  The set of training vectors for each scale is split up into two 
  sets of approximately equal size, one for training and one 
  for pruning of the classification/prediction trees (AGTREE).
  The train routine then calls the 'make_agtree' exported
  in AGTREE/libagt.a (see AGTREE/agtree.h) to determine the nonlinear
  tree classifiers separately for each scale.

  NOTE: Training on binary or noise-less, discrete-valued
  data does typically not yield very good results. The reason
  is that such training produces non-linear predictors that 
  do not respond favorably to the noisy, continuous-valued 
  input vectors encountered during tomographic reconstruction.


2) Usage of the train program
-----------------------------

  By typing 'bin/train' at the command-prompt in the AWGM directory, 
  you can obtain the syntax of the train program:
  -------------

  Usage:
  train [-r reg-factor (0.011)] cmdfile

  -------------

  cmdfile: Specifies the name of an ascii file containing the
           filenames of the training images and their masks. 
           See AWGM/EXAMPLE/data/train_img_list for an example of
           a cmdfile. 
           The first line in the cmdfile must contain the total number
           of training images. Each remaining line in cmdfile 
           contains 2 entries: The filename of the training image followed by
           the filename of the mask file for this training image.

           The training images must be matlab-format .mat files 
           containing a matrix named 'img' with a rectangular training
           image (type double). The mask file must be a .mat file 
           containing a matrix named 'mask' as described above for mask.mat
           for the tomo program. Training images can have different
           sizes, however, the masks must have same size as their associated
           training image.

  -r option: The -r option specifies a regularization factor for the
           merging of tree nodes during the training process. 
           Typically, the default of 0.011 should work fine. 
           For more details, see the file AGTREE/README, section
           I.2 (technical description on merging) and section
           IV.1, paragraph on params.alpha. The parameter specified
           by the -r option of train is params.alpha.


  Depending on the size of your training set, you might need
  to adjust the number of initial clusters (=leaves) of the 
  agglomerative prediction tree (see AGTREE/README, sec. IV.1, 
  params.nb_clusters). Specifically, for small training sets 
  you might get errors such as 
 
  "Error: Training set too small for specified number of 
   initial clusters (=leaves). .." 

  or 

  "Error: The train data set does not have enough
   distinct data points for specified number
   of initial clusters (leaves)."

  In general, you would want at least an average of 5-10 data
  points for each initial cluster (see screen output when
  running train). 

  To change the number of leaves/initial clusters, edit
  AWGM/train.c, line 51: 

  int initial_nb_clusters[PYR_LEVELS-1] = {150,150,150,100};
 
  The default line above specifies 150 initial leaves for 
  scales 0,1,2 and 100 leaves for scale 3. (This has been
  chosen for 40 training images, each of size 256 x 256 pixels).
  Due to the image decimation at coarser scales, you will have fewer
  training vectors for the coarser scales. Thus, the number
  of leaves for the coarse scales should typically be smaller
  than that for the finer scales.

  After editing train.c, go to AWGM/src and type 'make' to
  recompile the code.

  




V.   Size of prediction window
---------------------------------------------------------------
  
  The size of the window of scaling coefficients used for the
  conditional distribution of the wavelet coefficients can be
  adjusted in the header of AWGM/include/tomo_defs.h:

  #define WINDOW_SIZE 3

  The default setting of 3 specifies a window of scaling coefficients
  of size 3 by 3. (Since we only use the differences of scaling coeffs.
  to the center coefficient in the window, this results in a vector 
  of size 8 used for the conditioning and for the input vector to the
  non-linear tree predictors).

  The window size must be an odd number. 

  We have found a larger window size of 5 to produce fewer blocking 
  artifacts on relatively smooth data.
  However, a larger window size means more model-parameters and 
  thus requires more training. To obtain a more robust model,
  the default is set to 3. If you change the window size,
  you will need to recompile the train and tomo programs 
  (go to AWGM/src and type 'make clean' followed by 'make').
  and you will need to re-train the model.



VI. Number of resolution scales
--------------------------------

  The number of resolution scales can be set in 
  in the header of AWGM/include/tomo_defs.h:

  #define PYR_LEVELS 5

  The default is set to 5 levels (scale 0-4), which, for
  a reconstruction resolution of 256 x 256 pixels results in
  a resolution of 16 by 16 scaling coefficients at the coarsest
  scale 4.
  
  If you change this entry, you will need to recompile the AWGM code.
  If you increase the number of levels, you will have to 
  re-train the model.



VII. Known problems
---------------------------------------------------------------

  1) Dependence on randomseed: As described in 
     AGTREE/README, the training of the non-linear 
     tree predictors is somewhat dependent on the 
     randomseed (/tmp/randomseed_agtree) used for the initial 
     k-means clustering of the make_agtree routine. The
     effect is small but noticeable in the reconstructions.

  2) The routine 'ansi_lib_loc/pseudoinvert.c' for inversion 
     of the covariance matrices relies on 'ansi_lib_loc/svdcmp.c'
     taken from numerical recipes in C.
     For some matrices, the svdcmp.c routine produces
     slightly inaccurate results. If you have problems with 
     this, you might want to comment out the '#define PINV'
     in AGTREE/agtree.h. For the training, this will revert to a regular 
     matrix inversion (to avoid problems with singular matrices, 
     a small constant INVCONST defined in agtree.h will be added 
     to the diagonal before calling invert).
     Note, that pseudoinvert is also used in src.tomo.c. If you
     have problems, this can be should be changed to a regular
     matrix inversion.


