Transcript Rebinning - UCLA.edu

Click to edit Master title style
Progress Update
An FPGA Infrastructure for
Real-Time 3-D Tomographic Imaging
Henry Chen
August 26, 2011
Click to edit Master title style
Review
Computed Tomography
Tomography
 Basis for CAT scan, MRI, PET, SPECT, etc.
 Greek “tomos”: part or section
 Cross-sectional imaging
technique using transmission
or reflection data from
multiple angles
Computed Tomography (CT)
 A form of tomographic reconstruction on computers
 Usually refers to X-ray CT
– Positron (PET)
– Gamma rays (SPECT)
Cross-Sections by X-Ray Projections
 Project X-ray through biological tissue;
measure total absorption of ray by tissue
 Projection Pθ(t) is the Radon
transform of object function
f(x,y):
P  t   



 
f  x, y    x cos   y sin   t  dxdy
 Total set of projections called
sinogram
X-Ray Projection Example
Phantom and Sinogram
Shepp-Logan Phantom
CT Reconstruction
 Restore image from projection data
 Inverse Radon transform
 Most common algorithm is filtered backprojection
– “Smear” each projection over image plane
Backprojection Result
 Need filtering (high-pass), interpolation
FBP Algorithm
 Input: sinogram sino(θ, N)
 Output: image img(x,y)
for each θ
filter sino(θ,*)
for each x
for each y
n = x cos θ + y sin θ
img(x,y) = sino(θ, n) + img(x,y)
 O(N3) algorithm
– But highly parallelizable, given sufficient memory
bandwidth; not computationally intensive
Click to edit Master title style
Review
Single-Slice Rebinning Method
for Helical Cone-Beam CT
(Noo, et. al., 1999)
3-D Tomography
 Construct 3-D image using sequence of
cross sectional images
 Requires many passes of ionizing x-ray radiation
Helical Cone-Beam Scanner
 Helical traversal reduces total number of passes;
increases scanning speed and reduces x-ray
exposure
 However, need to convert
cone-beam data into stack
of fan-beam slice images
Rebinning
 Maps projection data into fan-beam slices
 Virtual fan source mapped to surface of cone source
 Each slice requires CB projections from 1 revolution
centered on that slice (+/- 0.5P)
Rebinning
 Fan-beam “projection” estimated from value of conebeam projection in same vertical plane
 Use closest cone-beam source directly above or
below virtual fan-beam source
 Use oblique ray passing through M
Rebinning Geometry
Rebinning Equation
 Each fan-beam value is just weighted version of
cone-beam projection data
fan-beam projection length
fan sino
pz  , u 
u 2  D2
u v  D
2
2
2
g  u, v  CB sino
cone-beam projection length
u 2  D2
v
z
RD
Click to edit Master title style
FPGA Implementation
Reconstruction Flow
Projections
Converts cone-beam helical
projections into sequence
of fan-beam slices
Rebin
Normalize
Map fan-beam data into
parallel-beam projections
F2P
FBP
Reconstruct 3-D image
Apply Parker weights
to remove fan-beam
redundant data
Z-Interpolate
Filtered backprojection
to recover 2-D image slices
Reconstruction Flow
Rebin
Filter
Backproject
Backprojection
Rebin
Filter
Backproject
BRAM
Buffer
Addressing
xcosθ+ysinθ
xy
Sinogram
Buffer
DP/QDR SRAM
Image
Accumulation
Buffer
Backprojection Memory
n = x cos θ + y sin θ
img(x,y) = sino(θ, n) + img(x,y)
 BRAM buffers for filtered sinogram slice; small (~N)
but need low-latency random access
 Dual-ported memory (BRAM, QDR SRAM) wellsuited for write-after-read operation in accumulation
 If step sequentially through img(x,y), no write
hazards
Hardware Backprojection
200x200, 96 projection angles
Filtering
Rebin
Filter
Backproject
ROM
Filter
Coefficients
FFT
FFT
Frequency-Domain Filter
FFT
Coefficient Multiplication
IFFT
 CASPER library biplex pipelined streaming FFT
 Filter coefficients in ROM; can be runtime-loadable
HW Filter Imperfection
 Need to tweak wordlength, binary point, downshift
Hardware Filtered Backprojection
200x200, 96 projection angles
FPGA Resource Utilization
 Xilinx Virtex-5 SX95T DSP-optimized FPGA




Slice Registers:
Slice LUTs:
DSP48Es:
BlockRAMs:
21,416
17,549
60
100
out of
out of
out of
out of
58,880 (36%)
58,880 (29%)
640 (9%)
244 (40%)
 256 kB off-chip SRAM (QDR) used for image accumulation
 Fixed 18-bit filtering, 24-bit accumulation
– No fixed-point precision optimization performed yet
Rebinning
Rebin
Filter
Backproject
DRAM
Indices
SRAM
Rev0
Buffer
Rev1
Buffer
Rev2
Buffer
Weights
Rebinning Operation
 Every 3 scan-revolutions can be used to rebin 32
image slices
– Implemented as circular buffer with correction factor
applied to rebinning index
 Rebinning pattern period with every 32 image slices
 Rebinning, Parker normalization just weighting;
fan-to-parallel conversion requires weight-and-sum
Rebinning Indexing
 SW implementation assumed full data (sinos,
weights) accessibility not practical in HW
 Normalize one ordering to another  reduces
buffering from 2M to 64k
Fairly sequential
Locally sequential only
Rebinning Architecture
Weights,
Indices
BRAM
Latency Weight
Match
DRAM
BRAM
Circ.
Buffer
Map
Index
Fan-to-Parallel Folding
QDR
SRAM
Projection data
Z-2
Rebinning Memory
 200x200 image from 288x192 scanner geometry
 Indices: 2 × 32 × 192 × 200
– 2x 21-bit address space (2x 2M words → 16 MB?)
– Write-once, sequential read; DRAM
 Weights: 2 × 32 × 192 × 200
– 2x 21-bit address space (2x 2M words → 16 MB?)
– Write-once, sequential read; DRAM
 Projections: 3 × 192 × 288
– 18-bit address space (256k words → 1 MB)
– Sequential write, random read; ideally ZBT SRAM
Rebinning Data Access
 Low duty cycles; bottleneck at backprojection
– Write 192 × 200 samples every 32 × 192 × 2002 cycles
– Read 200 samples every 2002 cycles
 Still needs high-bandwidth bursts; provide all data
for a single image, then wait for FBP
Current Status
 Backprojection: HW done, tested
 Filtering: HW done, tested; needs optimization
 Rebinning: HW done, debugging
– Indices, weights reading out of DRAM
– Circular buffer, weighting, folding still testing
Eventual Target
 Expand geometries 4x
 Parallelization
References
 http://en.wikipedia.org/wiki/Tomography
 http://en.wikipedia.org/wiki/Computed_tomography
 Kak, A. C., Slaney, M., Principles of Computerized Tomographic Imaging,
IEEE Press, 1988
 Noo, F., Defrise, M., Clackdoyle, R., “Single-Slice Rebinning Method for
Helical Cone-Beam CT,” Physics in Medicine and Biology, vol 44, 1999