Tuesday, January 26, 2010

CS: Mutilevel Bioluminescence tomography based on Radiative Transfer Equation, Measurement Matrix for CS in the presence of Gross Errors

As some of you know, I have a continuing interest in the use of compressive sensing for the linear transport equation or the radiative transfer equation as it is sometimes called in a different field. Here are some of the first few papers taking a stab at it. Let us first note that these papers aim at taking care of difficult geometries. As it turns out this generally means that some slack is given to the need for accuracy. For papers that deal with the RTE with very high accuracy (but in 1-D) see Chuck Siewert's papers especially this one. Anyway, here is the l_1 version of RTE problems, let us hope these can guide us into building relevant sensing hardware:
Multilevel bioluminescence tomography based on radiative transfer equation Part 1: l1 regularization by Hao Gao and Hongkai Zhao. The abstract reads:
In this paper we study an l1-regularized multilevel approach for bioluminescence tomography based on radiative transfer equation with the emphasis on improving imaging resolution and reducing computational time. Simulations are performed to validate that our algorithms are potential for efficient high-resolution imaging. Besides, we study and compare reconstructions with boundary angular-averaged data, boundary angular resolved data and internal angular-averaged data respectively.

Multilevel bioluminescence tomography based on radiative transfer equation Part 2: total variation and l1 data fidelity by Hao Gao and Hongkai Zhao. The abstract:
In this paper we study the regularization with both l1 and total variation norm for bioluminescence tomography based on radiative transfer equation, compare l1 data fidelity with l2 data fidelity for different type of noise, and propose novel interior-point methods for solving related optimization problems. Simulations are performed to show that our approach is not only capable of preserving shapes, details and intensities of bioluminescent sources in the presence of sparse or non-sparse sources with angular-resolved or angular-averaged data, but also robust to noise, and thus is potential for efficient high-resolution imaging with only boundary data.

from that paper:

....As a remedy for poor reconstruction due to forward modeling by DA, we use radiative transfer equation (RTE) [13-16] as the forward model. Physically, RTE is an accurate model for photon migration in tissues. Moreover, with RTE one can utilize much richer data, such as boundary angular-resolved measurements, whose dimension can match that in the interior region. Mathematically, it was shown [17, 18] that the RTE-based inverse source problem with angular-resolved boundary measurements almost always has a unique solution with certain stability. Numerically it means that a better conditioned and less underdetermined system resulted from RTE-based BLT than from DA-based BLT. So in those applications in non-diffusive regime, it is more appropriate to use RTE model and better image
reconstruction is expected....

I need to write down the idea I mentioned earlier on the subject. The solver was featured in A Fast Forward Solver of Radiative Transfer Equation by Hao Gao and Hongkai Zhao. The abstract reads:
In this paper we develop an efficient forward solver for steady-state or frequency-domain radiative transfer equation (RTE) on 2D and 3D structured and unstructured meshes with vacuum boundary condition or reflection boundary condition. In our algorithm we use a direct angular discretization and upwind type of spatial discretization that preserves properties of both scattering and differential operators of RTE. To solve the large linear system after discretization, we construct an efficient iterative scheme based on Gauss-Seidel and proper angular dependent ordering. With this iterative scheme as the relaxation we implement various multigrid methods in both angular and physical space. Our algorithm can deal with different scattering regimes efficiently. Although we emphasize applications in optical imaging, our method may be applied to more general RTEs, e.g., other types of scattering function. Efficiency and accuracy of our algorithm is demonstrated by comparison with both analytical solutions and Monte Carlo solutions, and various numerical tests in optical imaging.

The code can be found here (or here if you are in a country that does not support Google)

Finally, here is another very nice paper: On the Systematic Measurement Matrix for Compressed Sensing in the Presence of Gross Errors by Zhi Li, Feng Wu and John Wright. The abstract reads:
Inspired by syndrome source coding using linear error-correcting codes, we explore a new form of measurement matrix for compressed sensing. The proposed matrix is constructed in the systematic form [A I], where A is a randomly generated submatrix with elements distributed according to i.i.d. Gaussian, and I is the identity matrix. In the noiseless setting, this systematic construction retains similar property as the conventional Gaussian ensemble achieves. However, in the noisy setting with gross errors of arbitrary magnitude, where Gaussian ensemble fails catastrophically, systematic construction displays strong stability. In this paper, we prove its stable reconstruction property. We further show its l_1-norm sparsity recovery property by proving its restricted isometry property (RIP). We also demonstrate how the systematic matrix can be used to design a family of lossy-to-lossless compressed sensing schemes where the number of measurements trades off the reconstruction distortions.
The proof in the paper are here.

3 comments:

JackD said...

In connection with the last paper mentioned in your post, if I'm not wrong, a RIP analysis of matrix [Phi I] (and even [Phi Omega] for any MxM orthonormal matrix Omega) has been realized before in:

Jason Laska, Mark Davenport, and Richard Baraniuk, Exact signal recovery from sparsely corrupted measurements through the pursuit of justice. (Asilomar Conf. on Signals, Systems, and Computers, Pacific Grove, California, November 2009) (see Theorem 2 inside)
http://dsp.rice.edu/files/publications/conference-paper/2009/ldb-asilomar-2009.pdf


and used here:

Mark Davenport, Jason Laska, Petros Boufounos, and Richard Baraniuk, A simple proof that random matrices are democratic. (Rice University ECE Department Technical Report TREE-0906, November 2009)
http://dsp.rice.edu/files/publications/report/2009/dlbr-tr-2009.pdf

It seems that Zhi Li, Feng Wu and John Wright do not know these (previous/simultaneous?) works, and they reproved RIP for [Phi I] in their Section V. It seems however that their proof is slightly different from that of Davenport et al., and the bound on the minimal number of measurement not exactly the same. Notice also that Davenport et al. proved this result for any RIP matrix enlarged with the identity, and not only enlarged Gaussian matrices.

Best regards,
Laurent

JackD said...

sorry, in my comment, there is an inversion in the "realized before in" and "used here" references.

Dick Gordon said...

re: Inverse radiative transfer and melanoma

Here’s some more prior literature on the inverse radiative transfer problem:

Chandrasekhar, S. (1960). Radiative Transfer. New York, Dover Publications.

Nevoscopy, the 3D imaging of nevi (beauty marks), which are all potential skin melanomas, has been addressed from the point of view of forward and inverse radiative transfer:

Patwardhan, S.V., A.P. Dhawan & P.A. Relue (2003). Monte Carlo simulation of light-tissue interaction: three-dimensional simulation for trans-illumination-based imaging of skin lesions. IEEE Transactions on Biomedical Engineering 52(7), 1227-1236.

Kini, P. & A.P. Dhawan (1992). Reconstruction of embedded absorbers in random media with applications in non-invasive 3D imaging of skin lesions. Proc. SPIE 1767, 360-371.

The initial approach was standard 3D computed tomography, albeit from only 3 views:

Dhawan, A.P., R. Gordon & R.M. Rangayyan (1984). Nevoscopy: three-dimensional computed tomography for nevi and melanomas in situ by transillumination. IEEE Trans. Med. Imaging MI-3(2), 54-61.

The intent is to obtain the nevus thickness, which is the most prognostic factor for metastasis: once the melanoma penetrates the dermis, cure rate on excision drops from 95% to 5%. Differences in thickness of 0.1mm matter, so this is not something your partner can detect. Actual shape doesn’t matter much, making this an ideal CS application. I’d like to see nevoscopy developed into a whole body robotic skin scanner for detecting premetastasis melanoma. Contact me at gordonr@cc.umanitoba.ca if interested. Thanks.
Yours, -Dick Gordon

Printfriendly