\documentclass[envcountsect]{beamer}
%\includegraphics[height=6cm](full frame)
\usepackage{times}
\usepackage{amsfonts,eucal}
%\usetheme{JuanLesPins}
\usetheme{Frankfurt}
%Darmstadt
\logo{\includegraphics[height=20px]{img/maa.jpg}}
\title{Compression Algorithms for Digital Images}
\institute{{\large \textbf{Adrian Delgado}, Helmut Knaust}\medskip\\Department of Mathematical Sciences\\The University of Texas at El Paso\\El Paso TX 79968-0514}
\date{{\small Tucson AZ\quad March 31, 2012}}
\setbeamertemplate{theorems}[normal font]
\newtheorem{defi}{Definition}
\newtheorem{con}[defi]{Conjecture}
\newtheorem{thm}[defi]{Theorem}
\newcommand{\field}[1]{\mathbb{#1}}
\newcommand{\nat}{\field{N}}
\newcommand{\zet}{\field{Z}}
\newcommand{\real}{\field{R}}
\newcommand{\rat}{\field{Q}}
\newcommand{\cpl}{\field{C}}
\newcommand{\ilf}[1]{$\displaystyle #1 $}
\newcommand{\sol}[2]{\\{\textcolor{orange}{\textbf{\tiny Solved by #1\hfill#2}}}}
\renewcommand\thefootnote{\fnsymbol{footnote}}

\begin{document}
\begin{frame}
\titlepage
\end{frame}

\begin{frame}
%\tableofcontents[hideallsubsections]
\end{frame}

\section{Basics of Digital Signal Processing}
\subsection{The Problem}
\begin{frame}
\textbf{The Problem:}\medskip\\
We want to transform a digital image 
\begin{enumerate}
\item<2-> minimizing the data storage requirement for the transformed image
\item<3-> while maximizing the quality of the transformed image 
\end{enumerate}
\end{frame}

\begin{frame}
\begin{center}
\includegraphics[width=8cm]{img/schematic.pdf}\smallskip\\
The underlying \textbf{Information Theory} model
\end{center}
\end{frame}

\subsection{Digital Image Storage}
\begin{frame}
Each pixel in a gray-scale image is represented by an integer between $0$ and $255=2^8-1$ (8 bit = 1 byte)\medskip\\
0=black, 255=white
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=4cm]{img/pix1.pdf}
\end{figure}
\column{6cm}
\begin{figure}
\includegraphics[width=6cm]{img/pix2.pdf}
\end{figure}
\end{columns}
\end{frame}

\subsection{Entropy}
\begin{frame}
\begin{itemize}
\item<1->We will measure the information content of a signal/image by its \emph{entropy} as defined by \emph{Claude Shannon}:
\item<2->Given a signal $\vec{v}=\{v_1,v_2,\ldots,v_n\}$, let $p(v_k)$ denote the relative frequency of $v_k$. Then 
\[\mathop{Ent}(\vec{v})=\sum -p(v_k)\log_2(p(v_k))\]
\item<3->Example: For $\vec{v}=\{1,1,2,2,3\}$, \[p(1)=p(2)=2/5,\ p(3)=1/5,\] so $\mathop{Ent}(\vec{v})=2\cdot\left(-2/5\log_2(2/5)\right)-1/5\log_2(1/5)\approx 1.522.$
\end{itemize}
\end{frame}


\begin{frame}
\begin{itemize}
\item<1->The entropy of a signal, measured in bits per data point (pixel), is a theoretical lower bound for the data storage requirement of a signal \textbf{in its current form}.
\item<2->For the example on the previous slide $\vec{v}=\{1,1,2,2,3\}$, $\mathop{Ent}(\vec{v})\approx 1.522$ bits per pixel. Thus the storage requirement is at least $5\cdot 1.522=7.610$ bits.
\item<3->There are encoding algorithms, such as \textbf{Huffman} encoding, that come pretty close to the lower bound given by the entropy. 
\end{itemize}
\end{frame}

\section{The JPEG Algorithm}
\subsection{Transformation}
\begin{frame}
For the \textbf{JPEG algorithm}, the image is split into sub-images of size $8\times8$ pixels and 128 is subtracted from each pixel. 
\begin{center}
\begin{figure}
\includegraphics[width=8cm]{img/ING-ori.png}\\
Original image, entropy: 7.67
\end{figure}
\end{center}
\end{frame}

\begin{frame}Here is a typical $8\times8$ block $B$:
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=4cm]{img/ING-8x8.png}
\end{figure}
\column{6cm}
\begin{figure}
\includegraphics[width=4cm]{img/ING-8x8.pdf}
\end{figure}
\end{columns}
\end{frame}

\begin{frame}
Below is the fixed orthogonal matrix $U$ used by JPEG for image transformation. The matrix is based on the discrete cosine transform (DCT). 
\begin{center}
\begin{figure}
\includegraphics[width=10cm]{img/U.pdf}
\end{figure}
\end{center}
\end{frame}

\begin{frame}
We form the matrix $UBU^T$:
\begin{center}
\includegraphics[width=10cm]{img/UBUT.pdf}
\end{center}
Rounded to integers, its entropy is 3.76.
\end{frame}

\subsection{Quantization}
\begin{frame}
Next is a quantization step. \textbf{This step is not reversible.} We divide each entry of the transformed matrix $UBU^T$ by the corresponding matrix entry of a normalization matrix $Z$, then round to the next integer. One example of $Z$:
\begin{center}
\includegraphics[width=7cm]{img/Z.pdf}
\end{center}
\end{frame}

\begin{frame}
For $UBU^T$, quantization of the block yields the matrix $B'.$  
(Note that the gray values are scaled: 42 is now white, -15 is black.)
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=4cm]{img/Z8.png}
\end{figure}
\column{6cm}
\begin{figure}
\includegraphics[width=4cm]{img/Q.pdf}
\end{figure}
\end{columns}
\end{frame}


\begin{frame}
Doing this for each $8\times 8$ block yields the transformed quantized image. 
Its entropy is 1.40, leading to a compression factor of about 5.5.
\begin{center}
\includegraphics[width=8cm]{img/ING-qt.png}
\end{center}
\end{frame}

\subsection{Image Recovery}
\begin{frame}
\begin{itemize}
\item<1->This matrix is encoded and sent to the receiver.
\item<2-> The receiver multiplies each block pointwise by the transformation matrix $Z$ to obtain a matrix $B''$.
\item<3->The transformation $U$ is applied to obtain $U^TB''U$.
\item<4->Finally 128 is added to each pixel.
\end{itemize}
\end{frame}

\begin{frame}
Here is the recovered image:
\begin{center}
\includegraphics[width=8cm]{img/ING-final.png}
\end{center}
\end{frame}

\subsection{PSNR}
\begin{frame}
\begin{itemize}
\item<1->
To compare the original image to the recovered image, we use a logarithmic scale based on the average square error. For two matrices $A$ and $B$ of dimensions $M\times N$ we define the \textbf{Peak Signal to Noise Ratio}

\[\mathop{PSNR}(A,B)=10 \log_{10}\left(\frac{255^2}{\mathop{Err}(A,B)}\right),\]
where
\[\mathop{Err}(A,B)=\frac{1}{MN}\sum_{i=1}^M\sum_{j=1}^N (A_{ij}-B_{ij})^2.\]
\item<2->In our example the PSNR between the original and the recovered image is 29.4. (If $A=B$, their PSNR is $\infty$.)
\end{itemize}
\end{frame}

\section{The JPEG2000 Algorithm}
\subsection{Transformation}
\begin{frame}
\begin{itemize}
\item<1->The \textbf{JPEG2000 algorithm} applies a biorthogonal wavelet matrix pair to the whole image matrix.
\item<2->The matrices $W$ and $\tilde{W}$ used satisfy the orthogonality condition
\[\tilde{W}^T W=Id.\]
\item<3->The matrices use filters of length 7 and 9, hence their name: \emph{CDF97}.
\end{itemize}
\end{frame}

\begin{frame}
The matrix $W$ has the general shape 
\begin{figure}
\includegraphics[width=11cm]{img/W.pdf}
\end{figure}
\end{frame}

\begin{frame}
The matrix $\tilde{W}$ has the general shape 
\begin{figure}
\includegraphics[width=11cm]{img/Wt.pdf}
\end{figure}
\end{frame}

\begin{frame}
Given the matrix $A$ for our digital image, we form $WA\tilde{W}^T$.
\begin{figure}
\includegraphics[width=8cm]{img/T1.png}
\end{figure}
\end{frame}

\begin{frame}
We then apply the same procedure to the upper left quarter of the matrix.
\begin{figure}
\includegraphics[width=8cm]{img/T2.png}
\end{figure}
\end{frame}

\begin{frame}
\ldots and repeat one more time. (Entropy is 5.82.)
\begin{figure}
\includegraphics[width=8cm]{img/T3.png}
\end{figure}
\end{frame}

\begin{frame}
\begin{itemize}
\item The quantization step is similar to the quantization used in the JPEG algorithm. Once again thresholding and integer rounding is used with weights associated with the various regions of the transformed image. For the remainder we will use a quantized image with entropy 1.37. This is a compression factor of about 5.6.
\item The resulting matrix is encoded and then sent to the receiver.
\item The receiver ``reverses'' the quantization, then recovers the image using the orthogonality relation  $\tilde{W}^T W=Id$.
\end{itemize}
\end{frame}

\begin{frame}
Here is the recovered image:
\begin{center}
\includegraphics[width=8cm]{img/ING-finalwave.png}
\end{center}
The PSNR is about 29.7.
\end{frame}

\section{Conclusion}
\begin{frame}
\textbf{Comparison of JPEG and JPEG2000}
\begin{itemize}
\item<1-> Similar performance for ``normal'' image compression
\item<2-> JPEG is less computationally intensive.
\item<3-> Distribution of JPEG2000 hindered by a patent on the encoding algorithm.
\item<4-> JPEG2000 performs better at larger compression factors; JPEG starts to produce blocking artifacts.
\item<5-> JPEG2000 permits a low-resolution analysis of images.
\end{itemize}
\end{frame}

\begin{frame}
\textbf{References}
\begin{enumerate}
\item David Austin:\emph{ What is JPEG?} Notices of the AMS 55(2), 2008, pp.~226--9.
\item Catherine Beneteau, Patrick Van Fleet:  \emph{Discrete Wavelet Transformations and Undergraduate
Education.} Notices of the AMS 58(5), 2011, pp.~656--66.
\item Patrick van Fleet: \emph{Discrete Wavelet Transformations.} John Wiley \& Sons, 2007.
\end{enumerate}
\end{frame}

\end{document}


\begin{frame}
A color image consists of three color channels: Red, Green and Blue
\begin{figure}
\includegraphics[width=3.5cm]{img/cups.png}
\end{figure}
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsr.png}
\end{figure}
\begin{center}R\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsg.png}
\end{figure}
\begin{center}G\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsb.png}
\end{figure}
\begin{center}B\end{center}
\end{columns}
\end{frame}


\begin{frame}
The Red, Green and Blue color channels can be thought of as grayscale images:
\begin{figure}
\includegraphics[width=3.5cm]{img/cups.png}
\end{figure}
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsr_g.png}
\end{figure}
\begin{center}R\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsg_g.png}
\end{figure}
\begin{center}G\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsb_g.png}
\end{figure}
\begin{center}B\end{center}
\end{columns}
\end{frame}

\begin{frame}
It is more useful to split the color information into a \textbf{luminance} channel (Y) and two \textbf{chrominance} channels (Cb and Cr) instead:
\begin{figure}
\includegraphics[width=3.5cm]{img/cups.png}
\end{figure}
\begin{columns}[c]
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsY.png}
\end{figure}
\begin{center}Y\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsCb.png}
\end{figure}
\begin{center}Cb\end{center}
\column{4cm}
\begin{figure}
\includegraphics[width=3.5cm]{img/cupsCr.png}
\end{figure}
\begin{center}Cr\end{center}
\end{columns}
\end{frame}

