Figure 6.22 shows the unit circles using the l2 norm, l1 norm, and l0 quasi-norm, respectively. Except for the l2 norm unit circle, the other two unit circles do not look like circles at all. For a “measure” to be qualified as a norm, it needs to satisfy a set of axioms. A quasi-norm is almost a norm except that it does not satisfy an axiom called the triangle inequality.

Fig. 6.22: A unit circle is a trajectory of the points that have a distance 1 from the origin. Left: l2 norm’s unit circle. Middle: l1 norm’s unit circle. Right: l0 quasi-norm’s unit circle.

In theory, the l0 quasi-norm is the best measure to promote the sparsity of ψX and should be used. However, the optimization procedure is not tractable for any lp norm with 0 ≤ p < 1, because its associated objective function is not convex any more. The closest norm that produces a convex objective function is the l1 norm. The l1 norm minimization is nearly optimal, in the sense that its solution is not far from the solution with the much more complicated l0 quasi-norm minimization.

If the derivative of the Bayesian term exists, we can use the one-step late algorithm introduced in Section 6.9.6 to reconstruct the image. Unfortunately, the derivative of the Bayesian term in the objective function (6.88) does not exit. Rather complicated numerical methods are needed to minimize the objective function (6.88), even if the l0 quasi-norm is replaced by the l1 norm.

There is hope. Instead of using l0 quasi-norm and l1 norm, you may have also heard of the TV minimization. The TV (total variation) norm of an image v(x, y) is defined as

$TV(v)={\displaystyle \iint \left|\right|\nabla v(x,y)|{|}_{2}dxdy}={\displaystyle \iint \sqrt{{\left(\frac{\partial v}{\partial x}\right)}^2+{\left(\frac{\partial v}{\partial y}\right)}^2}}dxdy.$

The TV norm minimization enforces a flat image with the gradient being zero in most places. The resultant image tends to be piecewise constant. In practice, a small number ε is introduced to calculate the TV norm as

$TV(v)\approx {\displaystyle \iint \sqrt{{\left(\frac{\partial v}{\partial x}\right)}^2+{\left(\frac{\partial v}{\partial y}\right)}^2+{\epsilon }^2}dxdy}$

so that the TV norm is differentiable. In order to get some intuition about the modified TV norm (6.90) expressed above, let us assume ε2 = 1. Then the above expression is nothing but the surface area formula!

We see that minimizing the modified TV norm is almost equivalent to minimizing the surface area. If a solution has a minimum surface area, it has the least oscillations. TV norm minimization avoids the l0 quasi-norm and l1 norm minimization.

Using Green’s one-step-late method presented in Section 6.9.6, a TV-regulated EM (TV-EM) algorithm can be obtained as

$x_i^{\text{next}}=\frac{x_j^{\text{current}}}{{\displaystyle \sum _j{a}_{ij}+\beta \frac{\partial TV(X^{\text{current}})}{\partial x_j^{\text{current}}}}}{\displaystyle \sum _i{a}_{ij}\frac{p_i}{{\Sigma }_{\widehat{j}}{a}_{i\widehat{j}}{x}_{\widehat{j}}^{\text{current}}}}.$

For a 2D image X, if we express each pixel with double indices as xk,l, then the partial derivative in the above TV-EM algorithm can be given as

$\begin{array}{l}\frac{\partial TV(X)}{\partial x_{k,l}}=\frac{x_{k,l}-x_{k-1,l}}{\sqrt{{\left(x_{k,l}-x_{k-1,l}\right)}^2+{\left(x_{k-1,l+1}-x_{k-1,l}\right)}^2+{\epsilon }^2}}\\ +\frac{x_{k,l}-x_{k,l-1}}{\sqrt{{\left(x_{k+1,l-1}-x_{k,l-1}\right)}^2+{\left(x_{k,l}-x_{k,l-1}\right)}^2+{\epsilon }^2}}\\ -\frac{x_{k+1,l}+x_{k,l+1}-2x_{k,l}}{\sqrt{{\left(x_{k+1,l}-x_{k,l}\right)}^2+{\left(x_{k,l+1}-x_{k,l}\right)}^2+{\epsilon }^2}}.\end{array}$

Reconstruction with highly undersampled data is a Bayesian reconstruction problem. Performing the sparsifying transform ψX is one way to extract the prior knowledge from the image X. If other prior information about the image X is available, it should be included in the objective function as well.

6.11Worked examples

Example 1: For an arbitrary matrix A, its generalized inverse matrix A+ must satisfy the following four properties:

$\begin{array}{l}A{A}^{+}A=A,\\ A^{+}A{A}^{+}=A,\\ {(}^{A^{+}}=A^{+}A,\\ {(}^A=A{A}^{+}.\end{array}$

Here M∗ is the Hermitian transpose (also called conjugate transpose) of a matrix M. For a real matrix, it is simply the transpose. In the following, we assume that matrix A is real.

Please verify that if (ATA)–1 exists, then A+ =(ATA)–1 AT is a generalized inverse matrix of A. Please also verify that if (AAT)–1 exists, then A+ = AT(AAT)–1 is a generalized inverse matrix of A.

Proof.

Case 1 : $\text{If}{(A^{T}A)}^{-1}\text{exists},A^{+}={(A^{T}A)}^{-1}{A}^T.$

Property 1:

$\text{Left}=A{A}^{+}A=A{(A^{T}A)}^{-1}{A}^{T}A=A{(A^{T}A)}^{-1}(A^{T}A)=A=\text{Right}$

Property 2:

$\begin{array}{l}\text{Left}=A^{+}A{A}^{+}={\left(A^{T}A\right)}^{-1}{A}^{T}A{\left(A^{T}A\right)}^{-1}{A}^T={\left(A^{T}A\right)}^{-1}\left(A^{T}A\right){\left(A^{T}A\right)}^{-1}{A}^T\\ ={\left(A^{T}A\right)}^{-1}{A}^T=A^{+}=\text{Right}\end{array}$

Property 3:

$\begin{array}{l}\text{Left}={(}^{A^{+}}={(}^{{(}^{A^T}}={(}^{{(}^{A^T}}=I\\ \text{Right}=A^{+}A={(}^{A^T}{A}^{T}A={(}^{A^T}(A^{T}A)=I\end{array}$

Property 4:

$\begin{array}{l}\text{Left}={(}^A={(}^A=A{(}^{{(}^{A^T}}{A}^T\\ =A{(}^{{(}^{A^T}}{A}^T=A{(}^{A^T}{A}^T=A{A}^{+}=\text{Right}\end{array}$

Case 2 : $\text{If}{(A{A}^T)}^{-1}\text{exits,}{A}^{+}=A^T{(A{A}^T)}^{-1}.$

Property 1:

$\text{Left}=A{A}^{+}A=A{A}^T{(A{A}^T)}^{-1}A=(A{A}^T)(A{A}^T)A=A=\text{Right}$

Property 2:

$\begin{array}{l}\text{Left}=A^{+}AA=A^T{(}^{A}A{A}^T(A{A}^T)=A^T{(}^A(A{A}^T){(}^A\\ =A^T{(}^A=A^{+}=\text{Right}\end{array}$

Property 3:

$\begin{array}{l}\text{Left}={(}^{A^{+}}={(}^{A^T}=A^T{(}^{{(}^A}A\\ =A^T{(}^{{(}^A}A=A^T(A{A}^T)A=A^{+}A=\text{Right}\end{array}$

Property 4:

$\begin{array}{l}\text{Left}={(}^A={(}^A={(}^{(}=I\\ \text{Right}=A{A}^{+}=A{A}^T{(}^{A^T}=(A{A}^T){(}^{A^T}=I\end{array}$

Example 2: In Section 6.1, we used SVD to decompose matrix $A_{m\times n}\text{into}{A}_{m\times n}=U_{m\times m}\Sigma V_{n\times n}^T$ and defined $A^{+}=V{\Sigma }^{+}{U}^T$ and $D_r,=\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}.\text{Is}{A}^{+}=V{\Sigma }^{+}{U}^T$ a generalized inverse of matrix A according the four properties stated in Example 1? Find the condition under which A+ = VG+UT is a generalized inverse of matrix A.

Solution

Let us apply the first property to $A^{+}=V{\Sigma }^{+}{U}^T\text{and}{A}_{m\times n}=U_{m\times m}\Sigma V_{n\times n}^T:$

$A{A}^{+}A=U\Sigma V^{T}V{\Sigma }^{+}{U}^{T}U\Sigma V^T=U\Sigma (V^{T}V){\Sigma }^{+}(U^{T}U)\Sigma V^T=U\Sigma {\Sigma }^{+}\Sigma V^T.$

In order to have AA+A = A+, we must have

$\Sigma {\Sigma }^{+}\Sigma =\Sigma ,$

which is equivalent to

$\begin{array}{l}\text{diag{}{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,\dots ,{\sigma }_m\}\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}\text{diag{}{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,\dots ,{\sigma }_m\}\\ =\text{diag{}{\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r,\dots {\sigma }_m\},\end{array}$

or

${\sigma }_{r+1}=\cdots ={\sigma }_m=0.$

Since

${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_l\ge \cdots \ge 0,$

Property 1 is equivalent to

$\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}=\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}.$

Now let us look at Property 2:

$A^{+}A{A}^{+}=A^{+},$

which is equivalent to

$\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}=\text{diag}\left\{\frac{1}{{\sigma }_1},\frac{1}{{\sigma }_2},\dots ,\frac{1}{{\sigma }_r},0,\dots ,0\right\}.$

This property is always satisfied.

Property 3 (A+A ∗) = A+A and Property 4 AA+ ∗ = AA+ both imply that

$\text{diag{1,1,}\dots \text{,1,0,}\dots \text{,0}}=\text{diag{1,1,}\dots \text{,1,0,}\dots \text{,0},}$

which is always satisfied.

To summarize the above discussion, the condition under which $A^{+}=V{\Sigma }^{+}{U}^T$ generalized inverse of matrix A is

${\sigma }_{r+1}=0\text{and}{\sigma }_r>0.$

However, in practice, a cutoff index much smaller than this r is used to obtain a stable solution.

Example 3: None of the following images match the measured projections. Which one is the best solution among the three solutions in Figure 6.23? (Compare χ2)

Solution

$\begin{array}{l}\text{i)}{\chi }^2=0^2+0^2+1^2+1^2=2,(\leftarrow \text{Best})\\ \text{ii)}{\chi }^2=0^2+0^2+2^2+0^2=4,\\ \text{iii)}{\chi }^2=1^2+0^2+1^2+2^2=6.\end{array}$

Example 4: Find a least-squares reconstruction to the imaging problem shown in Figure 6.24.

Solution

The imaging matrix A for this problem AX = P is given as

$A=\left[\begin{array}{cccc}1& 0& 1& 0\\ 0& 1& 0& 1\\ 1& 1& 0& 0\\ 0& 0& 1& 1\end{array}\right].$

The rank of A is 3. The system AX = P is also not consistent. Therefore, there is no solution for this problem. We can use SVD-based method to find a pseudo-solution. Using Matlab with X = pinv(A) ∗ P, we get x1 =2.25, x2 =1.75, x3 =1.75, and x4 =1.25.

Example 5: Let $A=\left[\begin{array}{cc}2& 0\\ 0& 1\end{array}\right].$ Find the conjugate direction ${\stackrel{\rightharpoonup }{u}}_1\text{of}{\stackrel{\rightharpoonup }{u}}_0=\left[\begin{array}{l}1\\ 1\end{array}\right].$

Solution

The conjugate direction is defined by this relationship: ${\stackrel{\rightharpoonup }{u}}_0\cdot (A^{T}A){\stackrel{\rightharpoonup }{u}}_1=0,$, where

$A^{T}A=\left[\begin{array}{cc}2& 0\\ 0& 1\end{array}\right]\left[\begin{array}{cc}2& 0\\ 0& 1\end{array}\right]=\left[\begin{array}{cc}4& 0\\ 0& 1\end{array}\right].$

Fig. 6.23: Three images try to match the projections.

Fig. 6.24: A2 × 2 image reconstruction problem.

Fig. 6.25: Conjugate directions.

We also know

$\left[\begin{array}{l}1\\ 1\end{array}\right]\cdot \left[\begin{array}{l}1\\ -1\end{array}\right]=0.$

Thus $\left[\begin{array}{cc}4& 0\\ 0& 1\end{array}\right]{\stackrel{\rightharpoonup }{u}}_1=\left[\begin{array}{l}1\\ -1\end{array}\right],$which leads to

${\stackrel{\rightharpoonup }{u}}_1=\left[\begin{array}{cc}1/4& 0\\ 0& 1\end{array}\right]\left[\begin{array}{l}1\\ -1\end{array}\right]=\left[\begin{array}{l}1/4\\ -1\end{array}\right].$

(If you want, you could normalize 1 and make it a unit vector.)

The matrix ATA defines a quadratic form, which is an ellipse in our case. The point of this example is as follows: For any initial direction 0, draw an ellipse specified by the quadratic form ATA such that 0 is a tangential direction. If you travel along the conjugate direction 1, you will reach the center of the ellipse (see Figure 6.25).

Example 6: Compute one iteration of the ML-EM algorithm with the initial image and projections given in Figure 6.26.

Fig. 6.26: Initial image and projection data for Example 6.

Solution

Step 1: Find the forward projections.

Step 2: Find the ratios of given (i.e., measured) projections and the forward projections of the current image.

Step 3: Backproject the ratios.

Step 4: Backproject a constant 1 from all rays.

Step 5: Find pixel-by-pixel ratio of the backprojected image obtained from Step 3 and the backprojected image from Step 4.

Step 6: Pixel-by-pixel update the current image (using point-by-point multiplication, not matrix multiplication).

Example 7: Use a Bayesian method to find a stable solution of the system

$\{\begin{array}{l}{x}_1+0.01x_2=1.2\\ x_1+0.001x_2=1.\end{array}$

Solution

If we consider the potential measurement errors, the system of equations can be written as

$\{\begin{array}{l}{x}_1+0.01x_2=1.2+{\delta }_1\\ x_2+0.001x_2=1+{\delta }_2.\end{array}$

The solution of this modified system is given as

$\{\begin{array}{l}{x}_1=0.978-0.111{\delta }_1+1.11{\delta }_2\\ x_2=22.22+111.1{\delta }_1-111.1{\delta }_2.\end{array}$

It is seen that x2 is sensitive to measurement noise. Let us assume a priori that “x1 and x2 are close” and solve this problem using the Bayesian method. Here, a prior is a probability distribution representing knowledge or belief about an unknown quantity a priori, that is, before any data have been observed. First, we set up an objective function and use the prior knowledge as a penalty term:

$F(x_1,x_2)={(x_1+0.01x_2-1.2-{\delta }_1)}^2+{(x_1+0.001x_2-1-{\delta }_2)}^2+\beta {(x_1+x_2)}^2.$

Note that β in this expression is not a Lagrange multiplier, but a preassigned constant. To minimize This results in a different problem:

$\left[\begin{array}{l}2+\beta 0.011-\beta \\ 0.011-\beta {0.01}^2+{0.001}^2+\beta \end{array}\right]\left[\begin{array}{l}{x}_1\\ x_2\end{array}\right]=\left[\begin{array}{l}(1.2+{\delta }_1)+(1+{\delta }_2)\\ (0.01)(1.2+{\delta }_1)+(0.001)(1+{\delta }_2)\end{array}\right]$

The solution of this system depends on the value of β, as well as the values of δ1 and δ2. Some MAP solutions are listed in the following two tables:

Case 1: Noiseless $({\delta }_1={\delta }_2=0)$

Case 2: Noisy $({\delta }_1=-{\delta }_2=0.2)$

The system becomes more stable with an additional prior term in the objective function. The stability is reflected by much smaller condition numbers. This example also tells us that using a prior changes the original problem. Even for noiseless data, the MAP solutions may be different from the true solution. The Bayesian constraint β(x1 – x2)2 in eq. (6.124) is not a good one, and a better constraint should have been used. When you plan to use the Bayesian method, be careful and be sure that your prior knowledge is reasonable.

Example 8: Show that for the ML-EM algorithm at each iteration, the total number of the counts of the forward projections is the same as the total number of the counts of the original projection data:

${\displaystyle \sum _i\left({\displaystyle \sum _j{a}_{ij}{x}_j}\right)}={\displaystyle \sum _j{p}_i}.$

Proof.

$\begin{array}{l}{\displaystyle {\sum }_i{\displaystyle {\sum }_j{a}_{ij}{x}_j=}}{\displaystyle {\sum }_i{\displaystyle {\sum }_j{a}_{ij}}}\left(\frac{x_j^{\text{old}}}{{\displaystyle {\sum }_n{a}_{nj}}}{\displaystyle {\sum }_n{a}_{nj}}\frac{p_n}{{\displaystyle {\sum }_k{a}_{nk}{x}_k^{\text{old}}}}\right)\\ ={\displaystyle {\sum }_j{x}_j^{\text{old}}\frac{{\displaystyle {\sum }_i{a}_{ij}}}{{\displaystyle {\sum }_n{a}_{nj}}}}{\displaystyle {\sum }_n{a}_{nj}}\frac{p_n}{{\displaystyle {\sum }_k{a}_{nk}{x}_k^{\text{old}}}}[\text{change}\text{the}\text{oder}\text{of}\text{summations}.]\\ ={\displaystyle {\sum }_j{x}_j^{\text{old}}}{\displaystyle {\sum }_n{a}_{nj}}\frac{p_n}{{\displaystyle {\sum }_k{a}_{nk}{x}_k^{\text{old}}}}[\because {\displaystyle {\sum }_i{a}_{ij}}={\displaystyle {\sum }_n{a}_{nj}}]\\ ={{\displaystyle {\sum }_{n}p}}_n\frac{{{\displaystyle {\sum }_{j}a}}_{nj}{x}_j^{old}}{{\displaystyle {\sum }_k{a}_{nk}{x}_k^{\text{old}}}}[\therefore {\displaystyle {\sum }_i{a}_{ij}}={\displaystyle {\sum }_n{a}_{nj}}]\\ ={\displaystyle {\sum }_j{p}_n.}\end{array}$

Example 9: Use a computer simulation to demonstrate that the resolution recover rate is location dependent in the ML-EM algorithm.

Solution

A 2D computer-generated phantom shown in Figure 6.27 is used to generate projection data with and without Poisson noise. In data generation, attenuation, system blurring, and photon scattering are not included. That is, the projections are ideal line integrals of the object. The image size is 256 × 256, and 256 views uniformly distributed over 360° are used for projection data generation.

Fig. 6.27: The true image (a mathematical phantom).

Fig. 6.28: Iterative ML-EM reconstructions.

The iterative ML-EM algorithm is used for image reconstruction. Two reconstructed images are shown in Figure 6.28, one of which is obtained after 25 iterations, and the other is obtained after 250 iterations.

After 250 iterations, the algorithm has almost converged, and the resolution throughout the image is uniform. When the algorithm is stopped early at the 25th iteration, the resolution is not uniformly recovered. Higher resolution can be observed at the edge of the object. The resolution recovery rate is slower at the center. The motivation of early stopping is to regulate the noise. This is demonstrated with the noisy data reconstructions as shown in Figure 6.29, where two images are displayed. One of the images is obtained after 25 iterations and the other is obtained after 250 iterations.

The image with 250 iterations is noisier than that with 25 iterations. If we apply a low-pass filter to the noisy image obtained with 250 iterations, the image becomes less noisy and still maintains the uniform resolution throughout the image (see Figure 6.30). Therefore, it is a good strategy to over-iterate and then to apply a low-pass filter to control noise.

On the other hand, if the projections are ideal line integrals, the 2D parallel-beam FPB algorithm can provide images with uniform resolution (see Figure 6.31). However, if the imaging system has a spatially variant resolution and sensitivity, the conventional FBP algorithms are unable to model the system accurately and cannot provide uniform resolution in their reconstructions.

Fig. 6.29: Iterative ML-EM reconstructions with the same noisy projection data.

Fig. 6.30: Applying a low-pass filter to the image reconstructed with 250 iterations of ML-EM results in uniform resolution and reduced noise.

Fig. 6.31: Filtered backprojection reconstructions with noise-less and noisy data.

Fig. 6.32: Illustration of 2-pixel solutions with the minimum l2 norm, l1 norm, and l0 quasi-norm.