Note
Go to the end to download the full example code.
Total variation algorithms#
ASD-POCS and its variants, and their parameters.
Source: Python/demos/d09_Algorithms04.py · MATLAB/Demos/d09_Algorithms04.m
MATLAB version of this demo
%% DEMO 9: Algorithms 04. Total Variation minimization algorithms
%
%
% This demo presents the Total variation algorithms in TIGRE. Total
% variation algorithms try to minimize the variation (gradient) of the
% image, assuming it's piecewise smooth, as most things in nature are (i.e.
% human body).
%
% This set of algorithms is especially well-performing when the noise is
% very big or the number of projections is small, however, they require more
% computational time and memory than the other algorithms to run.
%
%
% This Demo is not fully complete, as several algorithms are not shown
% here, yet are available in TIGRE, namely:
%
% - AwASD_POCS: Edge preserving ASD_POCS (Adaptative weighted).
% - OS_AwASD_POCS: OS-version of the previous algorithm
% - PCSD: A version of ASD_POCS that heuristically select some of the
% parameters, particularly epsilon (maxL2norm)
% - AwPCSD: Edge preserving version of the previous algorithm
% - OS_AwPCSD: block-wise version of the previous
%
% You can use these algorithms in a very similar manner as below examples.
%--------------------------------------------------------------------------
%--------------------------------------------------------------------------
% This file is part of the TIGRE Toolbox
%
% Copyright (c) 2015, University of Bath and
% CERN-European Organization for Nuclear Research
% All rights reserved.
%
% License: Open Source under BSD.
% See the full license at
% https://github.com/CERN/TIGRE/blob/master/LICENSE
%
% Contact: tigre.toolbox@gmail.com
% Codes: https://github.com/CERN/TIGRE/
% Coded by: Ander Biguri
%--------------------------------------------------------------------------
%% Initialize
clear;
close all;
%% Define Geometry
geo=defaultGeometry('nVoxel',[128;128;128]);
%% Load data and generate projections
% see previous demo for explanation
angles=linspace(0,2*pi-2*pi/30,30);
head=headPhantom(geo.nVoxel);
projections=Ax(head,geo,angles,'interpolated');
noise_projections=addCTnoise(projections);
%% Lets create a OS-SART test for comparison
[imgOSSART,errL2OSSART]=OS_SART(noise_projections,geo,angles,60);
%% Total Variation algorithms
%
% ASD-POCS: Adaptative Steepest Descent-Projection On Convex Subsets
% Often called POCS-TV
%==========================================================================
%==========================================================================
% ASD-POCS minimizes At-B and the TV norm separately in each iteration,
% i.e. reconstructs the image first and then reduces the TV norm, every
% iteration. As the other algorithms the mandatory inputs are projections,
% geometry, angles and maximum iterations.
%
% ASD-POCS has a variety of optional arguments, and some of them are crucial
% to determine the behavior of the algorithm. The advantage of ASD-POCS is
% the power to create good images from bad data, but it needs a lot of
% tuning.
%
% Optional parameters that are very relevant:
% ----------------------------------------------
% 'maxL2err' Maximum L2 error to accept an image as valid. This
% parameter is crucial for the algorithm, determines at
% what point an image should not be updated further.
% Default is 20% of the FDK L2 norm.
%
% it's called epsilon in the paper
epsilon=im3Dnorm(Ax(FDK(noise_projections,geo,angles),geo,angles)-noise_projections,'L2')*0.15;
% 'alpha': Defines the TV hyperparameter. Default is 0.002.
% However the paper mentions 0.2 as a good choice
alpha=0.002;
% 'TViter': Defines the amount of TV iterations performed per SART
% iteration. Default is 20
ng=25;
% Other optional parameters
% ----------------------------------------------
% 'lambda': Sets the value of the hyperparameter for the SART iterations.
% Default is 1
%
% 'lambdared': Reduction of lambda Every iteration
% lambda=lambdared*lambda. Default is 0.99
%
lambda=1;
lambdared=0.9999;
% 'alpha_red': Defines the reduction rate of the TV hyperparameter
alpha_red=0.95;
% 'Ratio': The maximum allowed image/TV update ratio. If the TV
% update changes the image more than this, the parameter
% will be reduced. Default is 0.95
ratio=0.94;
% 'Verbose' 1 or 0. Default is 1. Gives information about the
% progress of the algorithm.
verb=true;
imgASDPOCS=ASD_POCS(noise_projections,geo,angles,50,...
'TViter',ng,'maxL2err',epsilon,'alpha',alpha,... % these are very important
'lambda',lambda,'lambda_red',lambdared,'Ratio',ratio,'Verbose',verb); % less important.
% OS_ASD_POCS: Ordered Subset-TV algorithm
%==========================================================================
%==========================================================================
%
% The logical next step to improve ASD-POCS is substituting SART with a
% faster algorithm, such as OS-SART
%
% The parameters are the same as in ASD-POCS, but also have 'BlockSize' and
% @OrderStrategy', taken from OS-SART
imgOSASDPOCS=OS_ASD_POCS(noise_projections,geo,angles,50,...
'TViter',ng,'maxL2err',epsilon,'alpha',alpha,... % these are very important
'lambda',lambda,'lambda_red',lambdared,'Ratio',ratio,'Verbose',verb,...% less important.
'BlockSize',size(angles,2)/10,'OrderStrategy','angularDistance'); %OSC options
% B-ASD-POCS-beta
%==========================================================================
%==========================================================================
% Is another version of ASD-POCS that has uses Bregman iteration, i.e.
% updates the data vector every some ASD-POCS iteration, bringing closer
% the data to the actual image. According to the original article, this
% accelerates convergence rates, giving a better image in the same amount
% of iteratiosn.
%
% It has all the inputs from ASD-POCS, and has 3 extra:
% 'beta' hyperparameter controling the Bragman update. default=1
%
% 'beta_red' reduction of the beta hyperparameter. default =0.75
%
% 'bregman_iter' amount of global bregman iterations. This will define
% how often the bregman iteration is executed. It has to
% be smaller than the number of iterations.
%Note that the number of iteration for TV has changed
imgBASDPOCSbeta=B_ASD_POCS_beta(noise_projections,geo,angles,50,...
'TViter',40,'maxL2err',epsilon,'alpha',alpha,... % these are very important
'lambda',lambda,'lambda_red',lambdared,'Ratio',ratio,'Verbose',verb,... % less important.
'beta',0.5,'beta_red',0.7,'bregman_iter',10); % bregman options
% SART-TV
%==========================================================================
%==========================================================================
%
% This implementation differs more from the others, as it minimizes the
% ROF model, i.e. when minimizing the total variation of the image, it
% also takes into account the information of the image. If only the total
% variation minimization step was run in the rest of the algorithms, the
% result would be a flat image (as that is the minimum total variation
% image), altertatively, the ROF model enforces the image not to change too
% much.
%
% This algirths performs better with more projections, but noisy data, by
% enforncing the TV very little
%
% The optional parameters are for the total variatiot part of the image:
%
%
%
% 'TViter' amount of iteration in theTV step. Default 50
%
% 'TVlambda' hyperparameter in TV iteration. IT gives the ratio of
% importance of the image vs the minimum total variation.
% default is 15. Lower means more TV denoising.
%
imgSARTTV=SART_TV(noise_projections,geo,angles,50,'TViter',100,'TVlambda',50);
% IRN_TV_CGLS
%==========================================================================
%==========================================================================
% CGLS with TV regularization in an inner/outer iteration scheme
%
% 'lambda' hyperparameter in TV norm. It gives the ratio of
% importance of the image vs the minimum total variation.
% default is 15. Lower means less TV denoising.
%
% 'niter_outer' Number of outer iterations. Each outer iteration will
% perform niter number of inner iterations, in the example
% below, 20.Albeit this seems that it does many more
% iterations than the other algorithms, this is an inherently
% faster algorithm, both in convergence and time.
imgIRN_TV_CGLS=IRN_TV_CGLS(noise_projections,geo,angles,20,'lambda',5,'niter_outer',2);
% hybrid_fLSQR_TV
%==========================================================================
%==========================================================================
% flexyble hybrod LSQR. Has TV regularization with reorthogonalization.
%
% 'lambda' hyperparameter in TV norm. It gives the ratio of
% importance of the image vs the minimum total variation.
% default is 15. Lower means less TV denoising.
%
imgflsqr=hybrid_fLSQR_TV(projections,geo,angles,20,'lambda',5);
%% Lets visualize the results
% Notice the smoother images due to TV regularization.
%
% head OS-SART ASD-POCS
%
% OS-ASD-POCS B-ASD-POCS-beta SART-TV
%
% IRN-TV-CGLS hybrid-fLSQR heads
plotImg([imgIRN_TV_CGLS imgflsqr head;
imgOSASDPOCS imgBASDPOCSbeta imgSARTTV;
head, imgOSSART, imgASDPOCS ] ,'Dim','Z','Step',2,'clims',[0 1])
% error
plotImg(abs([head-imgIRN_TV_CGLS head-imgflsqr head-head;
head-imgOSASDPOCS head-imgBASDPOCSbeta head-imgSARTTV;
head-head, head-imgOSSART, head-imgASDPOCS ]) ,'Dim','Z','Slice',64,'clims',[0 0.1])
%%
% Obligatory XKCD reference: https://xkcd.com/833/
Initialize#
import tigre
import numpy as np
from tigre.utilities import sample_loader
from tigre.utilities import CTnoise
import tigre.algorithms as algs
from matplotlib import pyplot as plt
from tigre.utilities.im3Dnorm import im3DNORM
Geometry#
geo = tigre.geometry_default(high_resolution=False)
Load data and generate projections#
# define angles
angles = np.linspace(0, 2 * np.pi, 100, endpoint=False)
# Load thorax phantom data
head = sample_loader.load_head_phantom(geo.nVoxel)
# generate projections
projections = tigre.Ax(head, geo, angles)
# add noise
noise_projections = CTnoise.add(projections, Poisson=1e5, Gaussian=np.array([0, 10]))
Lets create a OS-SART test for comparison#
imgOSSART = algs.ossart(noise_projections, geo, angles, 10)
OSSART algorithm in progress.
Estimated time until completion : 00:00:00
Algorithm will finish at : 16:50:37
Total Variation algorithms#
#
# ASD-POCS: Adaptative Steepest Descent-Projection On Convex Subsets
# Often called POCS
# ==========================================================================
# ==========================================================================
# ASD-POCS minimizes At-B and the TV norm separately in each iteration,
# i.e. reconstructs the image first and then reduces the TV norm, every
# iteration. As the other algorithms the mandatory inputs are projections,
# geometry, angles and maximum iterations.
#
# ASD-POCS has a variety of optional arguments, and some of them are crucial
# to determine the behavior of the algorithm. The advantage of ASD-POCS is
# the power to create good images from bad data, but it needs a lot of
# tuning.
#
# Optional parameters that are very relevant:
# ----------------------------------------------
# 'maxl2err' Maximum L2 error to accept an image as valid. This
# parameter is crucial for the algorithm, determines at
# what point an image should not be updated further.
# Default is 20% of the FDK L2 norm.
#
# it's called epsilon in the paper
epsilon = (
im3DNORM(tigre.Ax(algs.fdk(noise_projections, geo, angles), geo, angles) - noise_projections, 2)
* 0.15
)
# 'alpha': Defines the TV hyperparameter. Default is 0.002.
# However the paper mentions 0.2 as a good choice
alpha = 0.002
# 'tviter': Defines the amount of TV iterations performed per SART
# iteration. Default is 20
ng = 25
# Other optional parameters
# ----------------------------------------------
# 'lmbda': Sets the value of the hyperparameter lambda for the SART
# iterations. Default is 1
#
# 'lmbda_red': Reduction of lambda Every iteration
# lmbda=lmbda_red*lmbda. Default is 0.99
#
lmbda = 1
lambdared = 0.9999 # you generally want 1
# 'alpha_red': Defines the reduction rate of the TV hyperparameter
# alpha=alpha_red*alpha. Default is 0.95
alpha_red = 0.95
# 'rmax': The maximum allowed image/TV update ratio. If the TV
# update changes the image more than this, the parameter
# will be reduced. Default is 0.95
ratio = 0.94
# 'verbose' 1 or 0. Default is 1. Gives information about the
# progress of the algorithm.
verb = True
imgASDPOCS = algs.asd_pocs(
noise_projections,
geo,
angles,
10, # these are very important
tviter=ng,
maxl2err=epsilon,
alpha=alpha, # less important.
lmbda=lmbda,
lmbda_red=lambdared,
rmax=ratio,
verbose=verb,
)
imgPICCS = algs.piccs(
noise_projections,
geo,
angles,
10,
prior = imgOSSART,
tviter=ng,
maxl2err=epsilon,
alpha=alpha, # less important.
lmbda=lmbda,
lmbda_red=lambdared,
rmax=ratio,
verbose=verb,
prior_ratio = 0.5,
)
# OS_ASD_POCS: Ordered Subset-TV algorithm
# ==========================================================================
# ==========================================================================
#
# The logical next step to improve ASD-POCS is substituting SART with a
# faster algorithm, such as OS-SART
#
# The parameters are the same as in ASD-POCS, but also have 'BlockSize'
imgOSASDPOCS = algs.os_asd_pocs(
noise_projections,
geo,
angles,
10, # these are very important
tviter=ng,
maxl2err=epsilon,
alpha=alpha, # less important.
lmbda=lmbda,
lmbda_red=lambdared,
rmax=ratio,
verbose=verb,
# OSC params
blocksize=10,
)
# AwASD_POCS: adaptative weighted ASD_POCS
# ==========================================================================
# ==========================================================================
#
# This is a more edge preserving algorithms than ASD_POCS.
# delta is the cut-off value of a normalized edge exponential weight....
# not super clear, but it controls at which point you accept something as real vs noise edge.
imgAWASDPOCS = algs.awasd_pocs(
noise_projections,
geo,
angles,
10, # these are very important
tviter=ng,
maxl2err=epsilon,
alpha=alpha, # less important.
lmbda=lmbda,
lmbda_red=lambdared,
rmax=ratio,
verbose=verb, # AwASD_POCS params
delta=np.array([-0.005]),
)
# IRN-CGLS-TV: CGLS with TV regularization
# ==========================================================================
# ==========================================================================
#
# Should converge fairly fast to a TV regularized solution
imgCGLSTV=algs.irn_tv_cgls(noise_projections,geo,angles,10,lmbda=5,niter_outer=2)
ASD_POCS algorithm in progress.
Estimated time until completion : 00:00:05
Algorithm will finish at : 16:50:44
Stop criteria met:
c = -0.9973073
beta = 0.9990004498800211
iter = 10
PICCS algorithm in progress.
Estimated time until completion : 00:00:05
Algorithm will finish at : 16:50:50
Stop criteria met:
c = -0.9988894
beta = 0.9990004498800211
iter = 10
OS_ASD_POCS algorithm in progress.
Estimated time until completion : 00:00:00
Algorithm will finish at : 16:50:50
Stop criteria met:
c = -0.84494096
beta = 0.9990004498800211
iter = 10
AWASD_POCS algorithm in progress.
Estimated time until completion : 00:00:04
Algorithm will finish at : 16:50:55
Stop criteria met:
c = -0.9769031
beta = 0.9990004498800211
iter = 10
IRN_TV_CGLS algorithm in progress.
Estimated time until completion : 00:00:00
Algorithm will finish at : 16:50:57
plot results#
# plot images
tigre.plotimg(
np.concatenate([imgAWASDPOCS, imgOSASDPOCS, imgASDPOCS, imgOSSART, imgCGLSTV, imgPICCS], axis=1), dim="z", step=2
)

Total running time of the script: (0 minutes 22.708 seconds)