Band Ordering in Lossless Compression of Multispectral Images

UNCG Author/Contributor (non-UNCG co-authors, if there are any, appear on document)
Stephen R. Tate, Professor and Department Head (Creator)
Institution
The University of North Carolina at Greensboro (UNCG )
Web Site: http://library.uncg.edu/

Abstract: In this paper, we consider a model of lossless image compression in which each band of a multispectral image is coded using a prediction function involving values from a previously coded band of the compression, and examine how the ordering of the bands affects the achievable compression. We present an efficient algorithm for computing the optimal band ordering for a multispectral image. This algorithm has time complexity O(n2) for an n-band image, while the naive algorithm takes time Ω(n!). A slight variant of the optimal ordering problem that is motivated by some practical concerns is shown to be NP-hard, and hence, computationally infeasible, in all cases except for the most trivial possibility. In addition, we report on our experimental findings using the algorithms designed in this paper applied to real multispectral satellite data. The results show that the techniques described here hold great promise for application to real-world compression needs.

Additional Information

Publication
IEEE Transactions on Computers, Vol. 46, no. 4, April 1997
Language: English
Date: 1997
Keywords
Compression, Lossless compression, Image compression, Multispectral images, Satellite data, NP-completeness