A new algorithm for discrete tomography

E. Gouillart, F. Krzakala, M. Mezard, L. Zdeborova, Belief propagation reconstruction for discrete tomography, Inverse Problems 29, 3, 035003 (2013)

X-ray tomography is a widely used imaging technique that allows one to produce internal images in materials science or medical applications. An X-ray beam is transmitted through the sample and the projection is recorded on a detector at different angles. The most widely used reconstruction algorithm of the original image from these measurements approximates the inversion of the tomographic inverse linear problem. However, it provides satisfying results only for a well-determined system, with a large number of projections. In order to reduce the acquisition time or the total dose absorbed by the patient, tomography users need other reconstruction algorithms that incorporate known properties of the original image. For example, images with a discrete set of absorption values and few interfaces are frequently encountered in materials science. Using such prior information can make up for the lack of measurements and result in a high-precision reconstruction, an idea popularized by the field of compressed sensing.

 

Inspired by results from statistical physics and graphical models, we have proposed a novel message-passing algorithm for discrete tomography that allows for an efficient computation of pixel expectations under the Bayesian posterior distribution. The algorithm works on two levels: it is iteratively sending probabilistic messages between the different light rays and different set of messages within each light ray in order to satisfy the observed values of measurements. The resulting algorithm is fast, and entirely distributed. We showed that for binary images an accurate reconstruction is obtained for highly undersampled measures, and, equally importantly, the performance is robust to Gaussian measurement noise.

mezard_krzakala