HOME
PDF

Analysis of HYPR

Nasser M. Abbasi

California State University, Fullerton. Summer 2008 page compiled on July 1, 2015 at 10:08pm

Contents

1 Terminologies
2 Introduction
3 Review of HYPR
 3.1 High level schematic of original HYPR with many projections per time frame
4 HYPR mathematical formulation
 4.1 Original HYPR
  4.1.1 Schematic diagram of original HYPR algorithm
 4.2 Wright HYPR
  4.2.1 Schematic diagram of Wright HYPR algorithm
  4.2.2 On the difference between original HYPR and Wright-HYPR
 4.3 I-HYPR
  4.3.1 Schematic diagram of I-HYPR algorithm
5 WI-HYPR (Iiterative HYPR based on Wright-HYPR flow)
 5.1 Schematic diagram of WI-HYPR

1 Terminologies

Let I  be a 2D image. Let R 𝜃(t)   be the forward projection matrix (implemented as Radon transformation in practice) which when applied to the image I  at some projection angle 𝜃  at time t  will result in a 1D projection image P (t)  .

Since the image itself will change with time (blood flows, etc...) therefore we need to associated a time index t  as well with the 2D image itself. Hence we write I (t)  from now on, to indicate the 2D image at time     t  . Notice that the image as a whole does not move (relative to fixed initerial frame of reference) but the image content can change as described above.

To avoid confusion in what follows, I will use the notation of ⊛ to indicate a multiplication between 2 matrices element by element and will use ∗ to indicate the normal matrix by matrix or matrix by vector multiplication. And will use ∕.  to indicate division between vectors or matrices being done element by element.

2 Introduction

We will analyze the following HYPR algorithms: Original HYPR, Wright-Hyper, I-HYPR and a new variation of I-HYPR  based on on the Wright-HYPR. This new variation is different from I-HYPR since in I-HYPR the iteration is made on a composite image based on the Original HYPR construction while in this variation, the composite image is constructed is with the Write-HYPR algorithm. We will call this variation IW-HYPR.

For each algorithm we show the schematic flow chart and the mathematical description based on matrix formulation and an algorithm for the implementation. At the end, we will run a simulation of each of the above 4 algorithm from the same set of images and attempt to describe the finding and compare the results.

In the mathematical formula we derive an expression of the HYPR image as a function of the set of original images I (t)  and the set of the forward projection matrices R𝜃(t)   .

Before we discuss the Mathematical formulation, we need to better undertstand how to generate a set of projections from a well defined image which we can express mathematically. For this purpose the following diagram shows the 3 possible cases in which projections can occure at.

We need to generate an analytical expression as a function of time of a simple object shape for each of the following 3 cases.

PIC

3 Review of HYPR

Given a set of projections P (t)  over a number of time frames say M  and assuming there are N  projections generated per a time frame, the data  set will consists of M  ∗ N  projections in total. Within one time frame, a number of projections can be collected. These projections within each time frame will generate one HYPR frame using the HYPR algorithm. A time frame can have only one projection, but normally a time frame will have much larger number of projections.

For example, assuming there are M  = 10  time frames, and N  = 20  projections generated by time frame, then the total number of projections is 200.  In this case, we will obtain 10  HYPR frame images at the end.

HYPR starts by constructing a composite image from all the projections in the data set (200  in the above example). This is done by computing the filtered backprojection of all the M  ∗ N  projections into one image called C  .

Next, we process the projections from each time frame. For each time frame we generate a set of N  projections from C  by perform a radon tranform (forward projection) on C  at the same angle corresponding to the projection being processed. This will generate set of projections called the P
 c  projections. Hence there will be N  such projections per each time time.

Next the ratio of the each P  projection over the corresponding Pc  projection is found. This ratio is done pixel by pixel. Then each such ratio is multiplied by the composite image C  generating a a new set of size M  ∗ N  of weighted composite images. Now to generate a HYPR frame image, the average of these weighted compsite images is taken. The average is carried over each time frame at a time. Hence the first N  weighted compsite images will generate one HYPR frame, and the next N  weighted compsite images will generate the next HYPR frame and so on, resulting in M  HYPR frames.

3.1 High level schematic of original HYPR with many projections per time frame

The following diagram illustrates the above where we used the original HYPR algorithm. Later on, we describe in detailes the different HYPR algorithms variations. In the following diagram we show 4 projections per time frame and a total of 3 time frames. This results in 3 HYPR frames.

PIC

4 HYPR mathematical formulation

4.1 Original HYPR

The projection P (t)  is obtained by applying forward projection on the image I (t)  , Hence we write

P (t) = R 𝜃(t)[I (t)]

Next, the set of {P (t)} are combined and a filtered backprojection is applied to the result to generate a composite image C

          [M∑∗N            ]
C =  FBP        R𝜃(t)[I (ti)]
            i=1    i

Where FBP  is operator for the filtered backprojection.

The composite image C  can be written as

pict

Where N  in the number of projections. Now applying forward projection to C  at angle 𝜃i  will generate a projection Pci,  Hence

Pci = Ai ∗ C

Let zi  be the ratio Pi∕.Pci   where this division is being carried out element by element between the two projections.

Hence

pict

Now apply unfiltered backprojection on the above projection ratio to obtain an unfiltered 2D image and then mutiply that with the composit image to obtain a HYPR frame F
  i

pict

Hence HYPR image is

pict

We see that the above expression for HYPR image depends only on fi  and Ai  .

Therefore, given a set of images fi  and a set of projection angles 𝜃i  we can compute the forward projection matrices A
 i  (analytically we can do this for simple shapes such as a disk rotating around a unit circle for example). And once the set of matrices Ai  is computed, equation (1) could then be computed to obtain a HYPR image.

We can then generate the same HYPR images by performing backprojection (filtered an unfiltered) using the Fourier transform method. The algorithm for the backprojection (filtered) is known and given on page 62 of Kak and Slaney book which I will post a scan of.  Or we could simply use the radon/iradon for the implementaion of Ai  ,  T   +
A i ,A i  , where Ai  corresponds to applying radon on image f  at angle 𝜃i,  and      T
    Ai  corresponds to applying iradon on gi  with filter 'none' and  +
Ai  corresponds to applying iradon on projection gi  with a specified filter.

4.1.1 Schematic diagram of original HYPR algorithm

PIC

4.2 Wright HYPR

The projection gi  is obtained by applying forward projection on the image f  at time i.  Hence we write

g = A  ∗ f
 i    i   i

Where in the above the 2D image fi  needs to be first converted to a 1D vector as was done in the first assignment by folding the 2D image into a 1D column vector.

Let A+i  be an psudoinverse of Ai  which performs a filtered backprojection when applied on a projection vector gi  and let AT
  i  be the transpose of the matrix Ai  which performs an unfiltered backprojection on gi  .

The composite image C  can be written as

pict

where N  in the number of projections. Now, each unfiltered backprojection is

pict

Now applying forward projection to C  at angle 𝜃i  will generate a projection, call it ri

Hence

r = A  ∗ C
 i    i

Now applying an unfiltered backprojection on ri  will result in Pci   hence

pict

Let zi  be the ratio Pi∕.Pci   where this division is being carried out element by element between the two images.

Hence

pict

Hence one HYPR frame i  is

pict

Hence HYPR image is

pict

4.2.1 Schematic diagram of Wright HYPR algorithm

PIC

4.2.2 On the difference between original HYPR and Wright-HYPR

The difference between the original HYPR and Wright-HYPR can be seen in the following simplified diagram. We see than in the original HYPR, the ratio P ∕P C  is performed on the 1-D projections, then the unfiltered backprojection is applied on the resulting 1-D set of images. In the Wright-HYPR algorithm, the unfiltered backprojection is first applied to the set of the 1-D projections and then the ratio is performed on the result 2-D set of images.

PIC

4.3 I-HYPR

This is an iterative method where the composite image itself is updated and a new HYPR image determined with the hope of obtaining a better HYPR image (how to determine how many iterations? need to read more on this) as more iterations are performed. Let the number of iterations by M  therefore this algorithm will generate C1, C2,⋅⋅⋅,CM  composite images.

This is the mathematical formulation for I-HYPR

The projection Pi  is obtained by applying forward projection on the image f  at time i.  In the original HYPR, g
 i  is what is refered to P
  i  projection. Hence we write

P =  A  ∗ f
 i    i   i

The composite image C  at iteration (1) can be written as

       N
C  =  ∑  A+  ∗ P
  1        i    i
      i=1

Where N  in the number of projections. Now applying forward projection to C  at angle 𝜃i  will generate a projection Pci

Hence

Pc(1)i = Ai ∗ C1

Let zi  be the ratio Pi∕.Pci   where this division is being carried out element by element between the two projections.

Hence

pict

Now apply unfiltered backprojection on the above projection ratio to obtain an unfiltered 2D image and then mutiply that with the composit image to obtain a HYPR frame Fi

pict

Hence HYPR image at interation (1) is

pict

Now use I1   as the composite image for the next iteration, we obtain

C2 = I1

Hence

P    =  A  ∗ C
 c(2)i    i    2

and

pict

Now apply unfiltered backprojection on the above projection ratio to obtain an unfiltered 2D image and then mutiply that with the composit image to obtain a HYPR frame Fi

pict

Hence HYPR image at interation (2) is

pict

But             ∑N       (                     )
C2 =  I1 = 1-   C1 ⊛  ATi ∗ [Pi ∕. (Ai ∗ C1)]
           N i=1 hence the above becomes

pict

But       N
      ∑    +
C1 =     A i ∗ Pi
      i=1  , hence the above becomes

pict

Repeate this processes by setting C3 = I2   and generate I3   . Continue untill IM  where M  is number of iterations or untill some other convergence criteria is achived.

4.3.1 Schematic diagram of I-HYPR algorithm
Simplied version of the schematic diagram 

PIC

5 WI-HYPR (Iiterative HYPR based on Wright-HYPR flow)

The mathematics (TODO)

5.1 Schematic diagram of WI-HYPR

PIC