Tuesday, April 10, 2012

FPGA-Accelerated 3D Reconstruction Using Compressive Sensing (Hardware)

Here is an implementation that caught my eye: A reconstruction solver using an FPGA. It is not so new per se, but what caught my eye is how sparsity is rearing its head in the algorithmic implementation. First, the minimization is enforced on a combination of TV and EM arguments.on top of a positivity constraint. More work on that line of research can be found in references [1][2] and [3], as one can see, there is no sparsity enforcement from the get go. Here is the paper: FPGA-Accelerated 3D Reconstruction Using Compressive Sensing by Jianwen Chen, Jason Cong, Ming Yan and Yi Zou. The abstract reads:
The radiation dose associated with computerized tomography (CT) is significant. Optimization-based iterative reconstruction approaches, e.g., compressive sensing provide ways to reduce the radiation exposure, without sacrificing image quality. However, the computational requirement such algorithms is much higher than that of the conventional Filtered Back Projection (FBP) reconstruction algorithm. This paper describes an FPGA implementation of one important iterative kernel called EM, which is the major computation kernel of a recent EM+TV reconstruction algorithm. We show that a hybrid approach (CPU+GPU+FPGA) can deliver a better performance and energy efficiency than GPU-only solutions, providing 13X boost of throughput than a dual-core CPU implementation.

So, how is sparsity enforced ?
3.5 Reducing the Data Accesses via Sparsity
The final output image of the compressive sensing algorithm is sparse. Also we know that the image voxel value is non-negative. Based on these two facts, we develop a simple heuristic to reduce the amount of data access. In the beginning of the iteration, we perform a single forward projection. If any accumulated sinogram value falls below a threshold, we conclude that any image value on that ray shall be close to zero. Based on this, we build a mask of the image called image_denote. When we do the backward projection, we only update the voxels that are not masked. Note that this mask only need 1-bit data, so we merge this 1-bit data into the imageData array. Through this way, we reduce the number of data access in the backward projection. Figure 6 shows the modified pseudo code.

uh, heuristics! Two thoughts come to my mind:

  1. In [1], one can see that sparsity enforcement is not obvious, i.e. there is just a TV+EM+positivity minimization/constraint, how come one can get already good subsampling results ? Is the EM+TV enforcing sparsity in a way that is not obvious ?
  2. Using heuristics like this would make it an ideal algorithm for a GraphLab implementation. If it can be implemented on the Cloud, it will always beat an FPGA/GPU implementation. 

[2] EM+TV for Reconstruction of Cone-beam CT with Curved Detectors using GPU by  Jianwen Chen ,  Ming Yan ,  Luminita A. VeseJohn Villasenor, Alex Bui, and Jason Cong
[3] EM+TV Based Reconstruction for Cone-Beam CT with Reduced Radiation by  Ming Yan ,  Jianwen Chen ,  Luminita A. Vese, John Villasenor, Alex Bui, and Jason Cong


Ming Yan said...

Dear Igor,

Because the image is black for outside region, so it is better to find some convex region to be reconstructed, and the outside will be all zero. It can be done because the sensing matrix is discrete Radon transform with each row describing a line integral. If the line integral is zero, then the pixels intersected with this line are zero.

andry yudha prawira said...

related to the article, may be a reference to the link below

thank you

Igor said...


how is this related to the hardware implementation. It looks like a reference for doing CT ?