\section{Data Compression}

% -----------------------------------------------------------------
\begin{slide}{}

   Data must be encoded into a message. Compression is concerned with
   with removing {\it redundancy} from that encoding. There are two
   classes of compression:

   \begin{sitem}
      \item Lossless: ensures that the data recovered from the 
            compression/decompression process is exactly the
            same as the original data. Commonly used to compress 
            executable code, text files, and numeric data.

      \item Lossy: does not promise that the data received is exactly 
            the same as the data sent; removes removes information that
            it cannot later restore. (Hopefully, no one will notice.)
            Commonly used to compress digital imagery, including video.
   \end{sitem}

   Note: The compression/decompression process takes time. Whether or
   not you compress data (and how much you compress it) depends on whether
   you have more cycles (for compression) or bandwidth (for transmission).
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Loss-Less Compression Algorithms}

   \begin{sitem}
      \item Run Length Encoding (RLE)
      \begin{sitem}
         \item example: AAABBCDDDD encoded as 3A2B1C4D
         \item good for scanned text (8-to-1 compression ratio)
         \item can increase size for data with variation (e.g., some images)
      \end{sitem}
      \item Differential Pulse Code Modulation (DPCM)
      \begin{sitem}
         \item example: AAABBCDDDD encoded as A0001123333
         \item change reference symbol if delta becomes too large
         \item works better than RLE for many digital images (1.5-to-1)
      \end{sitem}
      \item Dictionary-Based Methods
      \begin{sitem}
         \item build dictionary of common terms (variable length strings)
         \item transmit index into dictionary for each term       
         \item Lempel-Ziv (LZ) compression is the best-known example
         \item commonly achieve 2-to-1 ration on text
         \item variation of LZ used to compress GIF images
         \begin{sitem}
            \item first reduce 24-bit color to 8-bit color
            \item treat common sequences of pixels as terms in dictionary
            \item not uncommon to achieve 10-to-1 compression ($\times$3)
         \end{sitem}
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Image Compression}

   \begin{sitem}
      \item JPEG: Joint Photographic Expert Group (ISO/ITU)
      \item Lossy still image compression
      \item Three phase process      

      \pichere{jpeg.eps,height=1in}

      \begin{sitem}
         \item process in 8$\times$8 block chunks (macroblock)
         \item greyscale: each pixel is a single value
         \item color: each pixel is three values (YUV)
         \item DCT: transforms signal from spatial domain into an 
               equivalent signal in the frequency domain (loss-less)
         \item apply a quantization to the results (lossy)
         \item RLE-like encoding (loss-less)
      \end{sitem}
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   Quantization Phase

\[ {\tt QuantizedValue}(i,j) = {\tt IntegerRound}(DCT(i,j) / {\tt Quantum}(i,j)) \]



\[ {\tt IntegerRound}(x) = \left\{ 
				\begin{array}{ll}
				\lfloor{x + 0.5}\rfloor & \mbox{if $x \ge 0$}\\
				\lfloor{x - 0.5}\rfloor & \mbox{if $x < 0$}
				\end{array}
			   \right. \]

   Decompression is then simply defined as

\[ DCT(i,j) = {\tt QuantizedValue}(i,j) \times {\tt Quantum}(i,j) \]



\begin{center}
\begin{displaymath}
{\tt Quantum} = \left[ \begin{array}{llllllll}
 3 &  5 &  7 &  9 & 11 & 13 & 15 & 17\\
 5 &  7 &  9 & 11 & 13 & 15 & 17 & 19\\
 7 &  9 & 11 & 13 & 15 & 17 & 19 & 21\\
 9 & 11 & 13 & 15 & 17 & 19 & 21 & 23\\
11 & 13 & 15 & 17 & 19 & 21 & 23 & 25\\
13 & 15 & 17 & 19 & 21 & 23 & 25 & 27\\
15 & 17 & 19 & 21 & 23 & 25 & 27 & 29\\
17 & 19 & 21 & 23 & 25 & 27 & 29 & 31
\end{array} \right]
\end{displaymath}
\end{center}

\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   Encoding Phase

   \pichere{zigzag.eps,height=2in}

\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \subsection{Video Compression}

   \begin{sitem}
      \item MPEG: Motion Picture Expert Group
      \item Lossy compression of video
      \item First approximation: JPEG on each frame
      \item Added compression: remove inter-frame redundancy
      \item Frame types
      \begin{sitem}
         \item I frames: intrapicture
         \item P frames: predicted picture
         \item B frames: bidirectional predicted picture
      \end{sitem}
      \pichere{mpeg.eps,height=3in}
      \item Example sequence transmitted as I P B B I B B
   \end{sitem}
\end{slide}
% -----------------------------------------------------------------
\begin{slide}{}

   \begin{sitem}
      \item B and P frames
      \begin{sitem}
         \item coordinate for the macroblock in the frame
         \item motion vector relative to previous reference frame
         \item motion vector relative to subsequent reference frame (B only)
         \item delta for each pixel in the macro block
      \end{sitem}
      \item Effectiveness
      \begin{sitem}
         \item typically 90-to-1
         \item as high as 150-to-1
         \item 30-to-1 for I frames
         \item P \& B frames get another 3 to 5$\times$ 
      \end{sitem}
   \end{sitem}
\end{slide}