📄 339-341.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="1558515682"><META name=vstitle content="Java Digital Signal Processing"><META name=vsauthor content="Douglas A. Lyon"><META name=vsimprint content="M&T Books"><META name=vspublisher content="IDG Books Worldwide, Inc."><META name=vspubdate content="11/01/97"><META name=vscategory content="Web and Software Development: Programming, Scripting, and Markup Languages: Java"><TITLE>Java Digital Signal Processing:Digital Images and Image Formats</TITLE>
<!-- HEADER --><STYLE type="text/css"> <!-- A:hover { color : Red; } --></STYLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW">
<!--ISBN=1558515682//-->
<!--TITLE=Java Digital Signal Processing//-->
<!--AUTHOR=Douglas A. Lyon//-->
<!--PUBLISHER=IDG Books Worldwide, Inc.//-->
<!--IMPRINT=M & T Books//-->
<!--CHAPTER=8//-->
<!--PAGES=339-341//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="336-339.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="341-345.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P><FONT SIZE="+1"><B>Run Length Encoding</B></FONT></P>
<P>Run length encoding (RLE) is a general compression method that encodes sequences of a character compactly as a number and the character.
</P>
<P>For example:</P>
<!-- CODE SNIP //-->
<PRE>
AAAAAAAAAABC
</PRE>
<!-- END CODE SNIP //-->
<P>could be coded as:
</P>
<!-- CODE SNIP //-->
<PRE>
10A1B1C
</PRE>
<!-- END CODE SNIP //-->
<P>The number 10 is the run count, and the letter A is the run value. If each ASCII character takes 1 byte of storage, the original uncompressed string takes 12 bytes, whereas the compressed string takes 7 bytes. Notice that even a run length of 1 requires a minimum of two characters.
</P>
<P>For binary character encoding, there are several choices. You can encode on a bit basis (looking for runs of bits), on a byte basis, or on a pixel basis, where a pixel can take numerous bytes. The overhead of storing a run length for each run value can cause a file to be larger than the original, something that is termed <I>negative compression</I>. One method to minimize the effect of the run length code for small runs is to encode a bit at the beginning of each block that enables run length interpretation for that block. In other words, if the enable bit is set to 1, the block is interpreted as run length encoded. If the enable bit is set to 0, the ensuing data is interpreted as unencoded, or literal, data.</P>
<P>With 2-D bitmap data, you have the freedom to encode data along rows, which are referred to as <I>scanlines</I>, along columns, or along some other portion of the data</P>
<P><FONT SIZE="+1"><B>Lempel, Ziv, and Welch Compression</B></FONT></P>
<P>A widely used algorithm for data compression was invented by Lempel, Ziv, and Welch and is known as LZW. Actually, there are several algorithms. LZ77, LZ78, and LZW are all patented so their use may be subject to licensing fees and legal headaches. It is possible to adapt LZ77 so that you do not infringe on its patent (see the discussion of PKZIP later). Unfortunately, several widespread programs and formats, such as the Compuserve GIF file format, used these patented algorithms. In a backlash against having to pay for what used to be in the public domain, several alternatives to the patented LZW algorithms were developed and offered to the public. The popular archiving compressor PKZIP replaced the original LZW compressor with one based on an adapted, non-infringing variation of the LZ77 algorithm. GIF is encumbered by infringement problems, but the world is still full of GIF images. There are many freeware utilities to convert GIF files to other formats, such as PPM. The PNG graphics format was created as an alternative to GIF and is also based on a non-infringing variation of the LZ77 algorithm. DiffCAD avoids infringement of these patents by leaving the image processing features unimplemented. A programmer must alter the <I>lyon.ipl.license.java</I> file in order to implement the image processing feature.</P>
<P>How does LZW work? The LZ family of compressors are <I>dictionary-based</I> encoding algorithms. As data is read by a compressor, a table, or <I>data dictionary,</I> is built that has entries for patterns that occur in the input data stream. If new data is not in the dictionary, a new entry is made for it. When data is read that has a dictionary entry, the entry, which is smaller than the original data, is copied to the output (compressed) data stream. A key feature of LZW is that the dictionary need not be stored for the decoder; because of the way the data is organized, the decoder will be able to reconstruct the dictionary. This arrangement can save a lot of overhead and space. LZW is a lossless compression scheme.</P>
<P><FONT SIZE="+1"><B>Huffman Encoding</B></FONT></P>
<P>Like LZW, Huffman encoding is based on code words. Here, shorter codes are chosen to represent the most commonly occurring sequences in a data stream; longer codes are used for less frequent sequences. For example, the letter <I>A</I>, if used frequently in input text, may be coded with 2 bits instead of the usual ASCII 8 bits, whereas the letter <I>Q</I>, which occurs infrequently, may be coded with 12 bits. For the decoder to do its work, it must have the dictionary used for encoding. There is no on-the-fly construction of a dictionary as in the LZW compressor. The data stream that is produced by Huffman encoding has a subtle requirement: No code word can be the prefix of any other code word. In this way, a decoder can uniquely determine each entry of the table based on a sequential read of the data stream. An improvement on Huffman encoding is arithmetic encoding, which is discussed next. Both Huffman encoding and arithmetic encoding are lossless compression schemes.</P>
<P><FONT SIZE="+1"><B>Arithmetic Encoding</B></FONT></P>
<P>Arithmetic encoding, or <I>entropy coding,</I> improves on Huffman encoding in a couple of ways. First, you can have fractional codes—that is, you can have a 4.18-bit code (this is defined in a statistical way). Second, more-complex statistics are used. Context information is analyzed to derive a code for an input pattern. A <I>U</I> may be assigned a long code because it does not occur very often, whereas a <I>U</I> following a <I>Q</I> may be assigned a short code because a <I>U</I> is very likely to follow a <I>Q</I>. A brand of arithmetic encoding, called Q-coder is patented by IBM and AT&T and is subject to licensing considerations. An extension of the JPEG compression standard uses Q-coder.</P>
<P><FONT SIZE="+1"><B>DCT-Based Compression</B></FONT></P>
<P>The (DCT) method converts image data to the frequency domain. DCT is much like the DFT (Discrete Fourier Transform), which is discussed at length in Chapter 9. The DCT is a special case of the DFT [Netravali et al.]. The transform yields a set of values that correspond to magnitudes of frequency components. The human eye cannot distinguish very high frequency color changes, and this information can be discarded without much loss of detail in an image. Also, transform values that are zero or close to zero can be effectively compressed with a lossless compression scheme such as Huffman encoding, as can be done in JPEG. The overall JPEG compression method is lossy.
</P><P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="336-339.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="341-345.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<hr width="90%" size="1" noshade><div align="center"><font face="Verdana,sans-serif" size="1">Copyright © <a href="/reference/idgbooks00001.html">IDG Books Worldwide, Inc.</a></font></div>
<!-- all of the reference materials (books) have the footer and subfoot reveresed --><!-- reference_subfoot = footer --><!-- reference_footer = subfoot --></BODY></HTML><!-- END FOOTER -->
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -