Skip to main content Accessibility help

We use cookies to distinguish you from other users and to provide you with a better experience on our websites. Close this message to accept cookies or find out how to manage your cookie settings.

Close cookie message
×
Hostname: page-component-745bb68f8f-s22k5 Total loading time: 0 Render date: 2025-02-06T11:29:12.689Z Has data issue: false hasContentIssue false

10 - Set partition coding

Published online by Cambridge University Press:  05 June 2012

William A. Pearlman  and
Amir Said
William A. Pearlman
Affiliation:
Rensselaer Polytechnic Institute, New York
Amir Said
Affiliation:
Hewlett-Packard Laboratories, Palo Alto, California
Get access

Summary

Principles

The storage requirements of samples of data depend on their number of possible values, called alphabet size. Real-valued data theoretically require an unlimited number of bits per sample to store with perfect precision, because their alphabet size is infinite. However, there is some level of noise in every practical measurement of continuous quantities, which means that only some digits in the measured value have actual physical sense. Therefore, they are stored with imperfect, but usually adequate precision using 32 or 64 bits. Only integer-valued data samples can be stored with perfect precision when they have a finite alphabet, as is the case for image data. Therefore, we limit our considerations here to integer data.

Natural representation of integers in a dataset requires a number of bits per sample no less than the base 2 logarithm of the number of possible integer values. For example, the usual monochrome image has integer values from 0 to 255, so we use 8 bits to store every sample. Suppose, however, that we can find a group of samples whose values do not exceed 15. Then every sample in that group needs at most 4 bits to specify its value, which is a saving of at least 4 bits per sample. We of course need location information for the samples in the group. If the location information in bits is less than four times the number of such samples, then we have achieved compression.

Type
Chapter
Information
Digital Signal Compression
Principles and Practice
 , pp. 265 - 312
Publisher: Cambridge University Press
Print publication year: 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1. Said, A. and Pearlman, W. A., “An image multiresolution representation for lossless and lossy compression,” IEEE Trans. Image Process., vol. 5, no. 9, pp. 1303–1310, Sept. 1996.CrossRefGoogle ScholarPubMed
2. Fowler, J. E., “Shape-adaptive coding using binary set splitting with k-d trees,” in Proceedings of the IEEE International Conference on Image Processing, Singapore, Oct. 2004, pp. 1301–1304.Google Scholar
3. Boettcher, J. B. and Fowler, J. E., “Video coding using a complex wavelet transform and set partitioning,” IEEE Signal Process Lett., vol. 14, no. 9, pp. 633–636, Sept. 2007.CrossRefGoogle Scholar
4. Xiong, Z., Guleryuz, O. G., and Orchard, M. T., “A DCT-based embedded image coder,” IEEE Signal Process. Lett., vol. 3, no. 11, pp. 289–290, Nov. 1996.CrossRefGoogle Scholar
5. Said, A. and Pearlman, W. A., “A new, fast, and efficient image codec based on set partitioning in hierarchical trees,” IEEE Trans. Circuits Syst. Video Technol., vol. 6, no. 3, pp. 243–250, Jun. 1996.CrossRefGoogle Scholar
6. Golomb, S. W., “Run-length encodings,” IEEE Trans. Inf. Theory, vol. IT-12, no. 3, pp. 399– 401, Jul. 1966.CrossRefGoogle Scholar
7. Gallager, R. G. and Voorhis, D., “Optimal source codes for geometrically distributed integer alphabets,” IEEE Trans. Inf. Theory, vol. 21, no. 2, pp. 228–230, Mar. 1975.CrossRefGoogle Scholar
8. Yemini, Y. and Pearl, J., “Asymptotic properties of discrete unitary transforms,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 1, no. 4, pp. 366–371, Oct. 1979.CrossRefGoogle ScholarPubMed
9. Said, A. and Pearlman, W. A., “Low-complexity waveform coding via alphabet and sample-set partitioning,” in Proc. SPIE Vol. 3024: Visual Commun. Image Process., San Jose, CA, Feb. 1997, pp. 25–37.Google Scholar
10. Andrew, J., “A simple and efficient hierarchical image coder,” in Proc. IEEE Int. Conf. Image Process., vol. 3, Santa Barbara, CA, Oct. 1997, pp. 658–661.CrossRefGoogle Scholar
11. Islam, A. and Pearlman, W. A., “Embedded and efficient low-complexity hierarchical image coder,” in Proceedings of the SPIE Vol. 3653: Visual Communications Image Processing, San Jose, CA, Jan. 1999, pp. 294–305.Google Scholar
12. Shapiro, J. M., “Embedded image coding using zerotrees of wavelet coefficients,” IEEE Trans. Signal Process., vol. 41, no. 12, pp. 3445–3462, Dec. 1993.CrossRefGoogle Scholar
13. Cho, Y. and Pearlman, W. A., “Quantifying the coding performance of zerotrees of wavelet coefficients: degree-k zerotree,” IEEE Trans. Signal Process., vol. 55, no. 6, pp. 2425–2431, Jun. 2007.CrossRefGoogle Scholar
14. Taubman, D. S. and Marcellin, M. W., JPEG2000: Image Compression Fundamentals, Standards, and Practice. Norwell, MA: Kluwer Academic Publishers. 2002.CrossRefGoogle Scholar
15. Hong, E. S. and Ladner, R. E., “Group testing for image compression,” IEEE Trans. Image Process., vol. 11, no. 8, pp. 901–911, Aug. 2002.CrossRefGoogle ScholarPubMed
Chrysafis, C., Said, A., Drukarev, A., Islam, A., and Pearlman, W. A., “SBHP – a low complexity wavelet coder,” in Proceedings of the IEEE International Conference on Acoustics Speech Signal Processing, vol. 4, Istanbul, Turkey, Jun. 2000, pp. 2035–2038.Google Scholar
Hsiang, S.-T. and Woods, J. W., “Embedded image coding using zeroblocks of subband/wavelet coefficients and context modeling,” in Proceedings of the IEEE International Symposium on Circuits Systems, vol. 3, Geneva, Switzerland, May 2000, pp. 662–665.Google Scholar
Information Technology – JPEG2000 Image Coding System, Part 1: Core Coding System, ISO/IEC Int. Standar. 15444–1, Geneva, Switzerland. 2000.
Information Technology – JPEG2000 Extensions, Part 2: Core Coding System, ISO/IEC Int. Standar. 15444–2, Geneva, Switzerland. 2001.
Munteanu, A., Cornelis, J., Auwera, G. V., and Cristea, P., “Wavelet image compression – the quadtree coding approach,” IEEE Trans. Inf. Technol. Biomed., vol. 3, no. 3, pp. 176–185, Sept. 1999.CrossRefGoogle ScholarPubMed
Pearlman, W. A., Islam, A., Nagaraj, N., and Said, A., “Efficient, low-complexity image coding with a set-partitioning embedded block coder,” IEEE Trans. Circuits Syst. Video Technol., vol. 14, no. 11, pp. 1219–1235, Nov. 2004.CrossRefGoogle Scholar

Save book to Kindle

To save this book to your Kindle, first ensure [email protected] is added to your Approved Personal Document E-mail List under your Personal Document Settings on the Manage Your Content and Devices page of your Amazon account. Then enter the ‘name’ part of your Kindle email address below. Find out more about saving to your Kindle.

Note you can select to save to either the @free.kindle.com or @kindle.com variations. ‘@free.kindle.com’ emails are free but can only be saved to your device when it is connected to wi-fi. ‘@kindle.com’ emails can be delivered even when you are not connected to wi-fi, but note that service fees apply.

Find out more about the Kindle Personal Document Service.

  • Set partition coding
  • William A. Pearlman, Rensselaer Polytechnic Institute, New York, Amir Said, Hewlett-Packard Laboratories, Palo Alto, California
  • Book: Digital Signal Compression
  • Online publication: 05 June 2012
  • Chapter DOI: https://doi.org/10.1017/CBO9780511984655.011
Available formats
×

Save book to Dropbox

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Dropbox.

  • Set partition coding
  • William A. Pearlman, Rensselaer Polytechnic Institute, New York, Amir Said, Hewlett-Packard Laboratories, Palo Alto, California
  • Book: Digital Signal Compression
  • Online publication: 05 June 2012
  • Chapter DOI: https://doi.org/10.1017/CBO9780511984655.011
Available formats
×

Save book to Google Drive

To save content items to your account, please confirm that you agree to abide by our usage policies. If this is the first time you use this feature, you will be asked to authorise Cambridge Core to connect with your account. Find out more about saving content to Google Drive.

  • Set partition coding
  • William A. Pearlman, Rensselaer Polytechnic Institute, New York, Amir Said, Hewlett-Packard Laboratories, Palo Alto, California
  • Book: Digital Signal Compression
  • Online publication: 05 June 2012
  • Chapter DOI: https://doi.org/10.1017/CBO9780511984655.011
Available formats
×