\documentclass [twoside]{article}
\usepackage{epsfig}
\usepackage{amsmath}
\usepackage{array}
\textwidth=6.5in
\topmargin=0in
\evensidemargin=0in
\oddsidemargin=0pt
\textheight=8in
\begin{document}
\hbox to \hsize{\bf CS384G \hfil Homework 1 \hfil Fall 2010}
\begin{center}
\bigskip
\bigskip
{\bf  Name:  $\underline{ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \
\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ }$
}\\
\bigskip
\bigskip
{\bf Sampling theory, image processing, affine transformations \\
Assigned: February 15, 2010 \\
Due: February 24, 2010 \\
(at the beginning of class) }
\end{center}
\vglue 12pt
\noindent
{\bf Directions: Please provide short written answers to the following
questions. Feel free to talk over the problems in general terms with
classmates, but please answer the questions on your own. }

\vglue12pt
\begin{enumerate}
\item (40 points) {\bf Fourier transforms and signal reconstruction}

In this problem, you will take a closer look at convolution, Fourier
transforms and signal reconstruction. We begin with a couple of
preliminaries.
\begin{itemize}
\item[i)] Recall that the box function $\mathrm{II} (x)$ is defined as:

$$\mathrm{II} (x) = \begin{cases}
                 1 & |x| < 1/2,\\
                 1/2 & |x| = 1/2,\\
                 0 & |x| > 1/2.
              \end{cases}$$

and its Fourier transform is $\mathrm{sinc}(s) = \sin(\pi s)/ \pi s$.
Likewise, the Fourier transform of $\mathrm{sinc}(x)$ is $\mathrm{II}(s)$. More
generally, for some constant frequency $\omega_0$, the Fourier transform of
$\mathrm{II}(\omega_0x)$ is $\frac{1}{\omega_0}\mathrm{sinc}(\frac{1}{\omega_0}s)$
Also, we can show that $\mathrm{sinc}(0) = 1$. This transform pair is depicted
graphically in the lecture notes.
\item[ii)] The dirac delta function $\delta(x)$ can be defined as:
\begin{eqnarray*}
  \delta(x) = & 0, & \textrm{ for all } x \neq 0, \\
  \delta(0) = & \infty, & \strut
\end{eqnarray*}
and with the property that $\int^\infty_{-\infty}\delta(x)dx = 1$.

The Fourier transform of $\cos(2\pi f_0 x)$ is

$$\frac{1}{2}\delta(s - f_0) + \frac{1}{2}\delta(s + f_0),$$

and vice-versa. The constant $f_0$ represents the frequency of the
cosine function. This transform pair is also depicted graphically in
the lecture notes.

\item[iii)] If the Fourier transform of $h(x)$ is $H(s)$, then the
Fourier transform of $k h(x)$ is $k H(s)$.

\item[iv)] The hat function, $\wedge(x)$, is defined as:

$$ \wedge(x) = \begin{cases}
                   1 - |x| & |x|\leq 1, \\
                   0       & |x|>1.
               \end{cases} $$
\end{itemize}

\noindent
We sample a function by multiplying with the comb or shah function:

$$
\Hat{f}(x) = f(x)\mathrm{III}(x)=\sum^{i=\infty}_{i=-\infty}f(i)\delta(x-i)
$$

\noindent
We reconstruct by convolving with a reconstruction filter $r(x)$:

$$
\Tilde{f}(x) = r(x)*\Hat{f}(x) = \sum^{i=\infty}_{i=-\infty}\Hat{f}(i)r(x-i)
$$

Now we get to the problems you need to solve. (Hint: There is an easy
way and a hard way to do these problems.  The easy way is to use
various simple properties of the Fourier transform. Try to avoid
setting up involved integration problems.)
\begin{itemize}
\item[a)] Convolution:\\
Given a function $f(x) = \cos(2\pi x) + \cos(8\pi x)$
\begin{itemize}

\item[i)] What is its Fourier transform (in equation form)? Plot the
magnitude of the Fourier transform, with properly labeled axes.
\vfill
\item[ii)] Given a convolution filter $h(x) = \mathrm{sinc}(5x)$, what is the
function that results from convolving $f(x)$ with $h(x)$?
\vfill
\end{itemize}

\item[b)] Sampling and Reconstruction:\\
Given the same function $f(x) = \cos(2\pi x) + \cos(8\pi x)$

\begin{itemize}
\item[i)] Plot this function.
\vfill
\item[ii)] If we sample this signal at points 0, 1/8, 2/8, 3/8, ., and
then reconstruct it with a linear reconstruction kernel, $h(x) = \wedge(8x)$,
what is the plot of the reconstructed signal? Is this signal the same
as the original signal $f(x)$? Discuss why or why not.
\end{itemize}
\end{itemize}
\vfill
\newpage
\item (20 points) {\bf Pre-filtering to minimize aliasing during sampling} \\
%(note: This is the hardest problem on the assignment)

This problem considers the use of pre-filtering to reduce the
high-frequency content of a signal prior to sampling it.  By
pre-filtering, we can reduce or eliminate the aliasing introduced by
sampling.

To keep the problem simple, we are considering 1D sampling of audio
(temporal) signals rather than 2D sampling of image (spatial)
signals. Thus, in the Fourier domain the units are Hz (temporal
cycles/second). But these same ideas are also used for 2D and 3D
sampling in computer graphics.

Digital telephone systems sample audio signals at a rate of 8kHz.

\begin{itemize}

\item[a)] What is the highest audio frequency that can be sampled by a
telephone system without aliasing?
\vfill

\item[b)] Humans can hear frequencies up to approximately 20 kHz. For
the sake of simplicity, assume that the audio signal that we are
sampling has a flat frequency spectrum from 0 to 20KHz. To avoid
aliasing when we sample this signal, we are going to first pre-filter
it with an analog filter to reduce the amount of energy in the signal
above the frequency found in part (a).  Our filter operates in the
time domain (equivalent to the spatial domain for images). Our filter
is implemented as convolution with a kernel we will design
%Gaussian
in the time domain. Describe a filter that will eliminate all
frequencies above the Nyquist limit.
Express the filter mathematically in both the time domain
and the frequency domain. i.e. what is $h(t)$ and what is $H(s)$?
% The
%width of $h(t)$ should be expressed in terms of a standard deviation $\sigma$.
\vfill

%\item[c)] Because the Gaussian never becomes exactly zero, we cannot use a
%Gaussian as a perfect pre-filter. But, if we choose the width of the
%Gaussian well it can be a good filter. Suppose that we want to insure
%that 98\% of the energy in the sampled signal is not aliased (i.e. 98\%
%of the energy in the sampled signal comes from frequencies that were
%below the Nyquist frequency in the original audio signal).
%What width of Gaussian should we use? (Hint, you are going to have
%to consider area under the curve $H(\omega)$.)
%\vfill

%\item[d)] With the filter from part (c), what fraction of the original signal
%energy {\em below} the Nyquist frequency are we discarding? Ideally the
%answer would be 0\%, but the answer is higher than that because the
%Gaussian is not a perfect low-pass filter.
%\vfill
\end{itemize}
\newpage
\item (20 points) {\bf Image processing}

Describe the effect of each of the following filters. In addition,
indicate which filter will cause the most blurring and which, when
convolved with a solid (positive) intensity image, will produce the
brightest image and which will produce the darkest image. Justify your
answers.

\setlength{\extrarowheight}{4pt}
\begin{center}
\begin{tabular}{|c | c | c |}
\hline
0.1 & 0.1 & 0.1 \\
\hline
0.1 & 0.1 & 0.1 \\
\hline
0.1 & 0.1 & 0.1 \\
\hline
\end{tabular}
\end{center}
\vfill
\begin{center}
\begin{tabular}{|c | c | c |}
\hline
0 & 0 & 1 \\
\hline
0 & -2 & 0 \\
\hline
1 & 0 & 0 \\
\hline
\end{tabular}
\end{center}
\vfill
\begin{center}
\begin{tabular}{|c | c | c |}
\hline
0 & 0.2 & 0 \\
\hline
0.2 & 0.4 & 0.2 \\
\hline
0 & 0.2 & 0 \\
\hline
\end{tabular}
\end{center}
\vfill
\begin{center}
\begin{tabular}{|c | c | c |}
\hline
0 & -1 & 0 \\
\hline
0 & 3 & 0 \\
\hline
0 & -1 & 0 \\
\hline
\end{tabular}
\end{center}
\vfill
\newpage
\item (20 points) {\bf Affine Transformations}

\begin{itemize}

\item[a)] As discussed in class, any three-dimensional affine
transformation can be represented with a $4\times4$ matrix.  Match each of
the matrices below to exactly one of the following transformations
(not all blanks will be filled):

\begin{itemize}
\item[\_\_\_\_] Differential (Non-Uniform) Scaling
\item[\_\_\_\_] Reflection
\item[\_\_\_\_] Rotation about the z-axis with non-uniform scaling
\item[\_\_\_\_] Rotation about the y-axis with non-uniform scaling
\item[\_\_\_\_] Translation
\item[\_\_\_\_] Rotation about the x-axis
\item[\_\_\_\_] Rotation about the y-axis
\item[\_\_\_\_] Rotation about the z-axis
\item[\_\_\_\_] Shearing along z with respect to the x-y plane (z=0 plane unchanged by shear)
\item[\_\_\_\_] Shearing along x with respect to the y-z plane (x=0 plane unchanged by shear)
\item[\_\_\_\_] Rotation about the x-axis and translation
\item[\_\_\_\_] Uniform scaling
\item[\_\_\_\_] Reflection with non-uniform scaling
\end{itemize}

$$
\begin{array}{lll}
A = \left[\begin{array}{cccc} 1 & 0 & 0 & 6 \\
                          0 & 1 & 0 & 3 \\
                          0 & 0 & 1 & 2 \\
                          0 & 0 & 0 & 1
      \end{array}\right] & 
B = \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\
                          0 & 0 & 1 & 0 \\
                          0 & -1 & 0 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] &
C = \left[\begin{array}{cccc} 0 & -1 & 0 & 0 \\
                          1 & 0 & 0 & 0 \\
                          0 & 0 & 1 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] \\
\bigskip \\
D = \left[\begin{array}{cccc} 2 & 0 & 0 & 0 \\
                          0 & 2 & 0 & 0 \\
                          0 & 0 & 2 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] &
E = \left[\begin{array}{cccc} 2 & 0 & 0 & 0 \\
                          0 & 3 & 0 & 0 \\
                          0 & 0 & 2 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] &
F = \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\
                          1 & 1 & 0 & 0 \\
                          0 & 0 & 1 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] \\
\bigskip \\
G = \left[\begin{array}{cccc} 1 & 0 & 0 & 0 \\
                          0 & 1 & 0 & 0 \\
                          0 & 0 & -1 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] &
H = \left[\begin{array}{cccc} 1 & 0 & -1 & 0 \\
                          0 & 1 & 0 & 0 \\
                          1 & 0 & 1 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right] &
I = \left[\begin{array}{cccc} 1 & 0 & 0 & 1 \\
                          0 & 0.6 & 0.8 & 0 \\
                          0 & -0.8 & 0.6 & 0 \\
                          0 & 0 & 0 & 1
      \end{array}\right]
\end{array}
$$
\vfill
\item[b)] Consider a line that passes through a point
${\bf p} = (p_x, p_y, p_z)$ in the direction
 $v = (\cos(\alpha), 0, \sin(\alpha))$. Write out the product of
matrices that would perform a rotation by $\theta$ about this line. You
should not multiply these matrices out, but you do need to write out
all of the elements in these matrices.
\vfill
\end{itemize}
\end{enumerate}
\end{document}
