×

Parallel computing with block-iterative image reconstruction algorithms. (English) Zbl 0727.65118

The image reconstruction problem consists of maximizing the entropy function subject to linear equality constraints with a block structure. Proceeding from a special block-iterative algorithm based on optimality criteria, several vectorization and parallelization procedures are investigated. In particular parallelism within a block, and with independent blocks is tested. Numerical examples are taken from image reconstruction of a head section with up to 1024\(\times 1024\) variables. The results show a dramatic improvement of calculation time on a CRAY X- MP compared to a SUN-3 workstation.

MSC:

65R10 Numerical methods for integral transforms
65R30 Numerical methods for ill-posed problems for integral equations
65Y05 Parallel numerical computation
65K05 Numerical mathematical programming methods
90C90 Applications of mathematical programming
94A12 Signal theory (characterization, reconstruction, filtering, etc.)
92C55 Biomedical imaging and signal processing
90C06 Large-scale problems in mathematical programming
44A12 Radon transform

Software:

BLAS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Multitasking user guide, CRAY Computer Systems Tech. Note SN-0222 (1986), Mendota Heights, MN
[2] SNARKK77 user’s manual, Version 2, MIPG (1978), Department of Radiology, Hospital of the University of Pennsylvania: Department of Radiology, Hospital of the University of Pennsylvania Philadelphia, PA
[3] Censor, Y., Parallel application of block-iterative methods in medical imaging and radiation therapy, Math. Programming, 42, 307-326 (1988) · Zbl 0658.90099
[4] Censor, Y., Row-action methods for huge and sparse systems and their applications, SIAM Rev., 23, 444-464 (1981) · Zbl 0469.65037
[5] Censor, Y.; Herman, G. T., On some optimization techniques for image reconstruction from projections, Appl. Numer. Math, 3, 365-391 (1987) · Zbl 0655.65140
[6] Censor, Y.; Segman, J., On block-iterative entropy maximization, J. Inform. Optimization Sci., 8, 275-291 (1987) · Zbl 0631.90087
[7] Chen, S. S., Large-scale and high-speed multiprocessor system for scientific applications, (Kowalik, J. S., High Speed Computation, 7 (1984), Springer: Springer Berlin), NATO ASI Series F
[8] Dongarra, J. J.; DuCroz, J.; Hammarling, S.; Hanson, R. J., An extended set of FORTRAN basic linear algebra subprograms, ACM Trans. Math. Software, 14, 1-17 (1988) · Zbl 0639.65016
[9] Elfving, T., An algorithm for maximum entropy image reconstruction from noisy data, Math. Comput. Modeling, 12, 729-745 (1989) · Zbl 0691.68102
[10] Frieden, B. R., Restoring with maximum likelihood and maximum entropy, J. Opt. Soc. Amer, 62, 511-518 (1972)
[11] Herman, G. T., Image Reconstruction from Projections: The Fundamentals of Computerized Tomography (1980), Academic Press: Academic Press New York · Zbl 0538.92005
[12] Herman, G. T.; Levkowitz, H., Initial performance of block-iterative reconstruction algorithms, (Viergever, M. A.; Todd-Pokropek, A., Mathematics and Computer Science in Medical Imaging (1988), Springer: Springer Berlin), 305-318
[13] Herman, G. T.; Levkowitz, H.; Tuy, H. K.; McCormick, S., Multilevel image reconstruction, (Rosenfeld, A., Multiresolution Image Processing and Analysis (1984), Springer: Springer Berlin), 121-135
[14] Herman, G. T.; Odhner, D.; Toennies, K.; Zenios, S. A., A parallelized algorithm for image reconstruction from noisy projections, (Coleman, T.; Yi, Y., Large Scale Numerical Optimization (1990), SIAM: SIAM Philadelphia, PA) · Zbl 0726.90095
[15] Kak, A. C.; Slaney, M., Principles of Computerized Tomographic Imaging (1987), IEEE Press: IEEE Press New York · Zbl 0721.92011
[16] Kapur, J. N., Twenty-five years of maximum entropy principle, J. Math. Phys. Sci., 17, 103-156 (1983) · Zbl 0516.94001
[17] Louis, A. K.; Natterer, F., Mathematical problems of computerized tomography, Proc. IEEE, 71, 379-389 (1983)
[18] (Meyer, R. R.; Zenios, S. A., Parallel Optimization on Novel Computer Architectures. Parallel Optimization on Novel Computer Architectures, Annals of Operations Research, 14 (1988), Baltzer Scientific Publishing Co: Baltzer Scientific Publishing Co Switzerland) · Zbl 0703.68011
[19] Shepp, L. A.; Logan, B. F., The fourier reconstruction of a head section, IEEE Trans. Nucl. Sci., 21, 21-43 (1976)
[20] (Smith, C. R.; Grandy, W. T., Maximum-Entropy and Bayesian Methods in Inverse Problems (1985), Reidel: Reidel Dordrecht, Netherlands)
[21] Zenios, S. A.; Mulvey, J. M., Vectorization and multitasking of nonlinear network programming algorithms, Math. Programming, 42, 449-470 (1988) · Zbl 0665.90095
[22] Zenios, S. A., Parallel numerical optimization: current status and an annotated bibliography, ORSA J. Comput., 1, 20-43 (1989) · Zbl 0825.65049
[23] Zenios, S. A.; Censor, Y., Vectorization and multitasking of block iterative algorithms for image reconstruction, (Science and Engineering on Cray Supercomputers—Proceedings of the Fourth International Symposium (1988), Cray Research, Inc: Cray Research, Inc Minneapolis, MN), 241-264
[24] Zhuang, X.; Ostevold, E.; Haralick, R. M., The principle of maximum entropy in image recovery, (Satrk, H., Image Recovery: Theory and Applications (1985), Academic Press: Academic Press New York), 157-193
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.