zbMATH — the first resource for mathematics

Medical image compression and vector quantization. (English) Zbl 0960.92018
Summary: We describe a particular set of algorithms for clustering and show how they lead to codes which can be used to compress images. The approach is called tree-structured vector quantization (TSVQ) and amounts to a binary tree-structured two-means clustering, very much in the spirit of CART. This coding is thereafter put into the larger framework of information theory. Finally, we report the methodology for how image compression was applied in a clinical setting, where the medical issue was the measurement of major blood vessels in the chest and the technology was magnetic resonance (MR) imaging.
Measuring the sizes of blood vessels, of other organs and of tumors is fundamental to evaluating aneurysms, especially prior to surgery. We argue for digital approaches to imaging in general, two benefits being improved archiving and transmission, and another improved clinical usefulness through the application of digital image processing. These goals seem particularly appropriate for technologies like MR that are inherently digital. However, even in this modern age, archiving the images of a busy radiological service is not possible without substantially compressing them. This means that the codes by which images are stored digitally, whether they arise from TSVQ or not, need to be “lossy”, that is, not invertible. Since lossy coding necessarily entails the loss of digital information, it behooves those who recommend it to demonstrate that the quality of medicine practiced is not diminished thereby
There is a growing literature concerning the impact of lossy compression upon tasks that involve detection. However, we are not aware of similar studies of measurement. We feel that the study reported here of 30 scans compressed to 5 different levels, with measurements being made by 3 accomplished radiologists, is consistent with 16:1 lossy compression as we practice it being acceptable for the problem at hand.

92C55 Biomedical imaging and signal processing
94A08 Image processing (compression, reconstruction, etc.) in information and communication theory
Full Text: DOI
[1] Abay a, E. and Wise, G. L. (1981). Some notes on optimal quantization. In Proceedings of the International Conference on Communications 2 30.7.1-30.7.5. IEEE Press, Piscataway, NJ.
[2] Adams, C. N. (1998). Ph.D. dissertation, Dept. Electrical Engineering, Stanford Univ.
[3] Ahumada, A. J., Jr. (1993). Computational image-quality metrics: a review. SID ’93 Digest of Technical Papers 305- 308.
[4] Bennett, W. R. (1948). Spectra of quantized signals. Bell Sy stems Technical Journal 27 446-472.
[5] Boncelet, C., Cobbs, J. and Moser, A. (1988). Error free compression of medical x-ray images. In Proc. SPIE Visual Communications and Image Processing 269-276. International Society of Optical Engineers.
[6] Bramble, J. (1989). Comparison of information-preserving and information-losing data-compression algorithms for CT images. Radiology 170 453-455.
[7] Bramble, J., Cook, L., Murphey, M., Martin, N., Ander son, W. and Hensley, K. (1989). Image data compression in magnification hand radiographs. Radiology 170 133- 136.
[8] Brandenburg, R., Fuster, V., Giuliani, E. and McGoon, D.
[9] . Cardiology: Fundamentals and Practice. Year Book Medical, Chicago.
[10] Breiman, L., Friedman, J. H., Olshen, R. A. and Stone,
[11] C. J. (1984). Classification and Regression Trees. Wadsworth, Belmont, CA. · Zbl 0541.62042
[12] Budrikus, Z. L. (1972). Visual fidelity criteria and modeling. Proceedings of the IEEE 60 771-779.
[13] Chen, D. T. S. (1977). On two or more dimensional optimum quantizers. In Proceedings of the International Conference on Acoustics, Speech, and Signal Processing 640- 643. IEEE Press, Piscataway, NJ.
[14] Chou, P. A., Lookabaugh, T. and Gray, R. M. (1989). Optimal pruning with applications to tree-structured source coding and modeling. IEEE Trans. Inform. Theory 35 299-315.
[15] Chou, P. A., Lookabaugh, T. and Gray, R. M. (1989). Entropy-constrained vector quantization. IEEE Transactions Acoustics, Speech, and Signal Processing 37 31-42.
[16] Chou, P. A., Lookabaugh, T. and Gray, R. M. (1989). Entropy-constrained vector quantization. IEEE Transactions on Acoustics, Speech, and Signal Processing 37 31- 42.
[17] Cosman, P. C. (1993). Perceptual aspects of vector quantization. Ph.D. dissertation, Stanford Univ.
[18] Cosman, P., Davidson, H., Bergin, C., Tseng, C., Olshen,
[19] R., Moses, L., Riskin, E. and Gray, R. (1994). The effect of lossy image compression on diagnostic accuracy of thoracic CT images. Radiology 190 517-524.
[20] Cosman, P., Gray, R. and Olshen, R. (1994). Evaluating quality of compressed medical images: SNR, subjective rating, and diagnostic accuracy. Proceedings of the IEEE 82 919-932. · Zbl 0811.45004
[21] Cosman, P., Tseng, C., Gray, R., Olshen, R., Moses, L.,
[22] Davidson, H., Bergin, C. and Riskin, E. (1993). Treestructured vector quantization of CT chest scans: image quality and diagnostic accuracy. IEEE Transactions on Medical Imaging 12 727-739.
[23] Cover, T. M. and Thomas, J. A. (1991). Elements of Information Theory. Wiley, New York. · Zbl 0762.94001
[24] Cox, D. R. (1957). Note on grouping. J. Amer. Statist. Assoc. 52 543-547. · Zbl 0088.35402
[25] Dalenius, T. (1950). The problem of optimum stratification. Skandinavisk Aktuarietidskrift 33 201-213. · Zbl 0041.46302
[26] Dalenius, T. and Gurney, M. (1951). The problem of optimum stratification II. Skandinavisk Aktuarietidskrift 34 203-213. · Zbl 0044.34103
[27] Daly, S. (1992). Visible differences predictor: an algorithm for the assessment of image fidelity. SPIE Proceedings 1666 2-14.
[28] Efron, B. and Tibshirani, R. J. (1993). An Introduction to the Bootstrap. Chapman and Hall, London. · Zbl 0835.62038
[29] Elias, P. (1955). Predictive coding I and II. IRE Transactions on Information Theory 1 16-33. · Zbl 0628.94010
[30] Eskicioglu, A. M. and Fisher, P. S. (1995). Image quality measures and their performance. IEEE Transactions on Communications 43 2959-2965.
[31] Eskicioglu, A. M. and Fisher, P. S. (1993). A survey of quality measures for gray scale image compression. Computing in AeroSpace 9 304-313.
[32] Flury, B. A. (1990). Principal points. Biometrika 77 31-41. JSTOR: · Zbl 0691.62053
[33] Forgey, E. (1965). Cluster analysis of multivariate data: efficiency vs. interpretability of classification. Biometrics 21 768. (Abstract.)
[34] Gardner, W. R. and Rao, B. D. (1995). Theoretical analysis of the high-rate vector quantization of LPC parameters. IEEE Transactions on Speech and Audio Processing 3 367-381.
[35] Gersho, A. (1979). Asy mptotically optimal block quantization. IEEE Trans. Inform. Theory 25 373-380. · Zbl 0409.94013
[36] Gersho, A. and Gray, R. M. (1992). Vector Quantization and Signal Compression. Kluwer, Boston. · Zbl 0782.94001
[37] Gray, R. M., Cosman, P. C. and Oehler, K. (1993). Incorporating visual factors into vector quantization for image compression. In Digital Images and Human Vision (B. Watson, ed.) 35-52. MIT Press.
[38] Gray, R. M. and Karnin, E. (1981). Multiple local optima in vector quantizers. IEEE Trans. Inform. Theory 28 708- 721. · Zbl 0476.94011
[39] Halpern, E. J., Newhouse, J. H., Amis, E. S., Levy, H. M.
[40] and Lubetsky, H. W. (1989). Evaluation of a quadtreebased compression algorithm with digitized urograms. Radiology 171 259-263.
[41] Hartigan, J. A. (1975). Clustering Algorithms. Wiley, New York. · Zbl 0372.62040
[42] Hilbert, E. E. (1977). Cluster compression algorithm: a joint clustering/data compression concept. Publication 7743, Jet Propulsion Lab, Pasadena, CA.
[43] Ibragimov, I. A. (1956). On the composition of unimodal distributions. Theory Probab. Appl. 1 255-260. · Zbl 0073.12501
[44] Karlin, S. (1968). Total Positivity. Stanford Univ. Press. · Zbl 0219.47030
[45] Karlin, S. (1982). Some results on optimal partitioning of variance and monotonicity with truncation level. In Statistics and Probability: Essay s in Honor of C. R. Rao (G. Kallianpur, P. R. Krishnaiah and J. K. Ghosh, eds.) 375-382. North-Holland, Amsterdam. · Zbl 0487.62010
[46] Lee, J., Sagel, S. and Stanley, R. (1989). Computed Body Tomography with MRI Correlation 2, 2nd ed. Raven, New York.
[47] Li, J., Chaddha, N. and Gray, R. M. (1997). Asy mptotic performance of vector quantizers with a perceptual distortion measure. Paper presented at 1997 IEEE International Sy mposium on Information Theory. (Full paper submitted for possible publication. Preprint available at http://www-isl.stanford.edu/ gray/ compression.html.) URL: · Zbl 0959.94011
[48] Linde, Y., Buzo, A. and Gray, R. M. (1980). An algorithm for vector quantizer design. IEEE Transactions on Communications COM-28 84-95.
[49] Lloy d, S. P. (1957). Least squares quantization in PCM. Technical note, Bell Laboratories. (Portions presented at the Institute of Mathematical Statistics Meeting Atlantic City, New Jersey, September 1957. Published in the March 1982 special issue on quantization, IEEE Trans. Inform. Theory.) · Zbl 0504.94015
[50] Lookabaugh, T., Riskin, E., Chou, P. and Gray, R. (1993). Variable rate vector quantization for speech, image, and · Zbl 0775.94078
[51] Lukas, F. X. J. and Budrikis, Z. L. (1982). Picture quality prediction based on visual model. IEEE Transactions on Communications COM-30 1679-1692.
[52] Lukaszewicz, J. and Steinhaus, H. (1955). On measuring by comparison. Zastosowania Matematy ki 2 225-231. (In Polish.) · Zbl 0068.13002
[53] MacMahon, H., Doi, K., Sanada, S., Montner, S., Giger, M., Metz, C., Nakamori, N., Yin, F., Xu, X., Yonekawa,
[54] H. and Takeuchi, H. (1991). Data compression: effect on diagnostic accuracy in digital chest radiographs. Radiology 178 175-179.
[55] MacQueen, J. (1967). Some methods for classification and analysis of multivariate observations. Proc. Fifth Berkeley Sy mp. Math. Statist. Probab. 1 281-296. Univ. California Press, Berkeley. · Zbl 0214.46201
[56] Mannos, I. L. and Sakrison, D. J. (1974). The effects of a visual fidelity criterion on the encoding of images. IEEE Trans. Inform. Theory IT-20 525-536. · Zbl 0295.94044
[57] Marmolin, H. (1986). Subjective MSE measures. IEEE Trans. Sy stems Man Cy bernet. 16 486-489.
[58] Max, J. (1960). Quantizing for minimum distortion. IEEE Trans. Inform. Theory 6 7-12.
[59] Na, S. and Neuhoff, D. L. (1995). Bennett’s integral for vector quantizers. IEEE Trans. Inform. Theory 41 886- 900. · Zbl 0833.94005
[60] Nill, N. B. (1985). A visual model weighted cosine transform for image compression and quality assessment. IEEE Transactions on Communications COM-33 551-557.
[61] Nill, N. B. and Bouxas, B. H. (1992). Objective image quality measure derived from digital image power spectra. Optical Engineering 31 813-825.
[62] Oehler, K. L. and Gray, R. M. (1995). Combining image compression and classification using vector quantization. IEEE Transactions on Pattern Analy sis and Machine Intelligence 17 461-473.
[63] Perlmutter, K. O., Perlmutter, S. M., Gray, R. M.,
[64] Olshen, R. A. and Oehler, K. L. (1996). Bay es risk weighted vector quantization with posterior estimation for image compression and classification. IEEE Transactions on Image Processing 5 347-360.
[65] Peterson, H. A., Peng, H., Morgan, J. H. and Pennebaker,
[66] W. B. (1991). Quantization of color image components in the DCT domain. Proceedings SPIE 1453 210-222.
[67] Poggi, G. and Olshen, R. A. (1995). Pruned tree-structured vector quantization of medical images with segmentation and improved prediction. IEEE Transactions on Image Processing 4 734-742.
[68] Redfern, A. and Hines, E. (1989). Medical image data compression techniques. In Proceedings of the Third International Conference on Image Processing and Its Applications 307 558-562. IEE, London.
[69] Rhodes, M., Quinn, J. and Silvester, J. (1985). Locally optimal run-length compression applied to CT images. IEEE Transactions on Medical Imaging MI-4 84-90.
[70] Riskin, E. A. and Gray, R. M. (1991). A greedy tree growing algorithm for the design of variable rate vector quantizers. IEEE Transactions Signal Processing 39 2500-2507.
[71] Sagrhi, J. A., Cheatham, P. S. and Habibi, A. (1989). Image quality measure based on a human visual sy stem model. Optical Engineering 28 813-818.
[72] Say re, J., Aberle, D. R., Boechat, M. I., Hall, T. R., Huang, H. K., Ho, B. K., Kashfian, P. and Rahbar, G.
[73] . Effect of data compression on diagnostic accuracy in digital hand and chest radiography. In Proceedings of Medical Imaging VI: Image Capture, Formatting, and Display 1653 232-240. SPIE, Bellingham, WA.
[74] ScheffĂ©, H. (1959). The Analy sis of Variance. Wiley, New York. · Zbl 0086.34603
[75] Shannon, C. E. (1948). A mathematical theory of communication. Bell Sy stems Technical Journal 27 379-423, 623- 656. · Zbl 1154.94303
[76] Shannon, C. E. (1959). Coding theorems for a discrete source with a fidelity criterion. In IRE National Convention Record, Part 4 142-163 IEEE Press, Piscataway, NJ.
[77] Stark, D. and Bradley, J. W. G. (1992). Magnetic Resonance Imaging, 2nd ed. Mosby-Year Book, St. Louis.
[78] Stockham, T. G., Jr. (1972). Image processing in the context of a visual model. Proceedings of the IEEE 60 828- 842.
[79] Tarpey, T., Li, L. and Flury, B. D. (1995). Principal points and self-consistent points of elliptical distributions. Ann. Statist. 23 103-112. · Zbl 0822.62042
[80] Trushkin, A. V. (1982). Sufficient conditions for uniqueness of a locally optimal quantizer for a class of convex error weighting functions. IEEE Trans. Inform. Theory IT-28 187-198. · Zbl 0476.94012
[81] Tukey, J. W. (1949). One degree of freedom for nonadditivity. Biometrics 5 232-242.
[82] Weinstein, M. and Fineberg, H. (1980). Clinical Decision Analy sis. Saunders, Philadelphia.
[83] Yamada, Y., Tazaki, S. and Gray, R. M. (1980). Asy mptotic performance of block quantizers with a difference distortion measure. IEEE Trans. Inform. Theory 26 6-14. · Zbl 0429.94014
[84] Zador, P. L. (1963). Topics in the asy mptotic quantization of continuous random variables. Memorandum, Bell Laboratories.
[85] Zador, P. L. (1963). Development and evaluation of procedures for quantizing multivariate distributions. Ph.D. dissertation, University Microfilm 64-9855, Dept. Statistics, Stanford Univ.
[86] Zador, P. L. (1982). Asy mptotic quantization error of continuous signals and the quantization dimension. IEEE Trans. Inform. Theory 28 139-148. · Zbl 0476.94008
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.