Page Menu
Home
c4science
Search
Configure Global Search
Log In
Files
F104926562
1_2Dsp.tex
No One
Temporary
Actions
Download File
Edit File
Delete File
View Transforms
Subscribe
Mute Notifications
Award Token
Subscribers
None
File Metadata
Details
File Info
Storage
Attached
Created
Thu, Mar 13, 10:24
Size
9 KB
Mime Type
text/x-tex
Expires
Sat, Mar 15, 10:24 (1 d, 20 h)
Engine
blob
Format
Raw Data
Handle
24882048
Attached To
R2653 epfl
1_2Dsp.tex
View Options
\documentclass
[aspectratio=169]
{
beamer
}
\def\stylepath
{
../styles
}
\usepackage
{
\stylepath
/com202
}
\usepackage
{
pst-3dplot
}
\usepackage
{
pst-tree
}
\begin
{
document
}
\intertitle
{
two-dimensional signal processing
}
\def\var
{
5
}
\begin
{
frame
}
\frametitle
{
Two-dimensional discrete-space signals
}
\begin
{
columns
}
\begin
{
column
}{
0.55
\paperwidth
}
\begin
{
itemize
}
\item
notation:
$
x
[
n_
1
, n_
2
]
$
,
$
n_
1
, n_
2
\in
\mathbb
{Z}
$
\item
indexes
$
n_
1
, n_
2
$
locate a point on a grid
\item
grid is usually regularly spaced
\end
{
itemize
}
\end
{
column
}
\begin
{
column
}{
0.45
\paperwidth
}
\begin
{
figure
}
\begin
{
center
}
\psset
{
unit=1.4mm
}
\begin
{
pspicture
}
(-5,-5)(5,15)
\psset
{
Beta=15
}
\psplotThreeD
[hiddenLine=true,plotstyle=curve,drawStyle=yLines,
% is the default anyway
yPlotpoints=29,xPlotpoints=29,linewidth=0.6pt](-14,14)(-14,14)
{
%
x x mul y y mul add -2
\var
\var
mul mul div 2.71828 exch exp 10 mul
}
\pstThreeDCoor
[linecolor=darkgray,xMin=-15,xMax=16,nameX={$n_1$},yMin=-15,yMax=16,nameY={$n_2$},zMin=0,zMax=13,nameZ={$x[n_1,n_2]
$
}
]
\end
{pspicture}
\end
{center}
\end
{figure}
\end
{column}
\end
{columns}
\end
{frame}
\begin
{frame}
\frametitle
{
2
D signals: support representation}
\begin
{columns}
\begin
{column}{
0
.
45
\paperwidth
}
\begin
{itemize}
\item
show coordinates of nonzero values
\item
values may be written alongside position
\item
example: the
2
D discrete
-
space impulse:
\[
\delta
[
n_
1
, n_
2
]
=
\begin
{cases}
1
&
\mbox
{if
$
n
_
1= n
_
2 = 0
$
}
\\
0
&
\mbox
{otherwise}
\end
{cases}
\]
\end
{itemize}
\end
{column}
\begin
{column}{
0
.
45
\paperwidth
}
\begin
{figure}
\begin
{center}
\begin
{dspCP}
[
width
=
5
cm,xticks
=
5
,yticks
=
5
,xout
=
true,xlabel
=
{
$
n
_
1
$
},ylabel
=
{
$
n
_
2
$
}
]
{
-
6
,
6
}{
-
6
,
6
}
\moocStyle
\dspPoints
{
0
0
}
\uput
{
1
ex}
[
45
]
{
0
}
(
0
,
0
)
{
\tiny
$
1
$
}
\end
{dspCP}
\end
{center}
\end
{figure}
\end
{column}
\end
{columns}
\end
{frame}
\begin
{frame}
\frametitle
{The
2
D discrete
-
space rect}
\begin
{columns}
\begin
{column}{
0
.
45
\paperwidth
}
\[
\rect\left
(
\frac
{n_
1
}{
2
N_
1
},
\frac
{n_
2
}{
2
N_
2
}
\right
)
=
\begin
{cases}
1
&
\parbox
[
t
]
{
10
em}{if
$
|n
_
1| < N
_
1
$
\\
and
$
|n
_
2| < N
_
2
$
}
\\
\\
0
&
\mbox
{otherwise}
\end
{cases}
\]
\end
{column}
\begin
{column}{
0
.
45
\paperwidth
}
\begin
{figure}
\begin
{center}
\begin
{dspCP}
[
width
=
5
cm,xticks
=
5
,yticks
=
5
,xout
=
true
]
{
-
6
,
6
}{
-
6
,
6
}
\moocStyle
\dspPoints
{
-
3
2
-
2
2
-
1
2
0
2
1
2
2
2
3
2
-
3
1
-
2
1
-
1
1
0
1
1
1
2
1
3
1
-
3
0
-
2
0
-
1
0
0
0
1
0
2
0
3
0
-
3
-
1
-
2
-
1
-
1
-
1
0
-
1
1
-
1
2
-
1
3
-
1
-
3
-
2
-
2
-
2
-
1
-
2
0
-
2
1
-
2
2
-
2
3
-
2
}
\end
{dspCP}
\end
{center}
\end
{figure}
\end
{column}
\end
{columns}
\end
{frame}
\begin
{frame}
\frametitle
{A new concept: separability}
\centering
A separable
2
D signal can be decomposed as the product of two
1
D signals:
\[
x
[
n_
1
, n_
2
]
=
x_
1
[
n_
1
]
x_
2
[
n_
2
]
\]
\end
{frame}
\begin
{frame}
\frametitle
{Examples of separable signals}
\[
\delta
[
n_
1
, n_
2
]
=
\delta
[
n_
1
]
\delta
[
n_
2
]
\]
\vspace
{
2
em}
\[
\rect\left
(
\frac
{n_
1
}{
2
N_
1
},
\frac
{n_
2
}{
2
N_
2
}
\right
)
=
\rect\left
(
\frac
{n_
1
}{
2
N_
1
}
\right
)
\rect\left
(
\frac
{n_
2
}{
2
N_
2
}
\right
)
.
\]
\end
{frame}
\begin
{frame}
\frametitle
{Nonseparable signal}
\begin
{columns}
\begin
{column}{
0
.
45
\paperwidth
}
\[
x
[
n_
1
, n_
2
]
=
\begin
{cases}
1
&
\mbox
{if
$
|n
_
1| + |n
_
2| < N
$
}
\\
0
&
\mbox
{otherwise}
\end
{cases}
\]
\end
{column}
\begin
{column}{
0
.
45
\paperwidth
}
\begin
{figure}
\begin
{center}
\begin
{dspCP}
[
width
=
5
cm,xticks
=
5
,yticks
=
5
,xout
=
true
]
{
-
6
,
6
}{
-
6
,
6
}
\moocStyle
\dspPoints
{
0
2
-
1
1
0
1
1
1
-
2
0
-
1
0
0
0
1
0
2
0
-
1
-
1
0
-
1
1
-
1
0
-
2
}
\end
{dspCP}
\end
{center}
\end
{figure}
\end
{column}
\end
{columns}
\end
{frame}
\begin
{frame}
\frametitle
{Nonseparable signal}
\begin
{columns}
\begin
{column}{
0
.
45
\paperwidth
}
\[
x
[
n_
1
, n_
2
]
=
\rect\left
(
\frac
{n_
1
}{
2
N_
1
},
\frac
{n_
2
}{
2
N_
2
}
\right
)
-
\rect\left
(
\frac
{n_
1
}{
2
M_
1
},
\frac
{n_
2
}{
2
M_
2
}
\right
)
\]
\end
{column}
\begin
{column}{
0
.
45
\paperwidth
}
\begin
{figure}
\begin
{center}
\begin
{dspCP}
[
width
=
5
cm,xticks
=
5
,yticks
=
5
,xout
=
true
]
{
-
6
,
6
}{
-
6
,
6
}
\moocStyle
\dspPoints
{
-
3
3
-
2
3
-
1
3
0
3
1
3
2
3
3
3
-
3
2
-
2
2
-
1
2
0
2
1
2
2
2
3
2
-
3
1
-
2
1
2
1
3
1
-
3
0
-
2
0
2
0
3
0
-
3
-
1
-
2
-
1
2
-
1
3
-
1
-
3
-
2
-
2
-
2
-
1
-
2
0
-
2
1
-
2
2
-
2
3
-
2
-
3
-
3
-
2
-
3
-
1
-
3
0
-
3
1
-
3
2
-
3
3
-
3
}
\end
{dspCP}
\end
{center}
\end
{figure}
\end
{column}
\end
{columns}
\end
{frame}
\begin
{frame}
\frametitle
{Two
-
dimensional filters}
\[
y
[
n_
1
, n_
2
]
=
\mathcal
{H}
\{
x
[
n_
1
, n_
2
]
\}
\]
\vspace
{
2
em}
\begin
{itemize}
\item
linearity:
$
\mathcal
{
H
}
\{
a x[n
_
1, n
_
2] + b w[n
_
1, n
_
2]
\}
= a
\mathcal
{
H
}
\{
x[n
_
1, n
_
2]
\}
+ b
\mathcal
{
H
}
\{
w[n
_
1, n
_
2]
\}
$
\item
space invariance:
$
\mathcal
{
H
}
\{
x[n
_
1 - d
_
1, n
_
2 - d
_
2]
\}
= y[n
_
1-d
_
1, n
_
2-d
_
2]
$
\item
impulse response
$
h[n
_
1, n
_
2] =
\mathcal
{
H
}
\{\delta
[n_1, n_2]
\}
$
\end
{itemize}
\end
{frame}
\begin
{frame}
\frametitle
{Two
-
dimensional filters}
\centering
A linear, space
-
invariant
2
D filter implements a
2
D convolution:
\[
(
x
\ast
h
)[
n_
1
, n_
2
]
=
\sum
_{k_
1
=
-
\infty
}^{
\infty
}
\sum
_{k_
2
=
-
\infty
}^{
\infty
} x
[
k_
1
,k_
2
]
h
[
n_
1
-
k_
1
,n_
2
-
k_
2
]
\]
\end
{frame}
\begin
{frame}
\frametitle
{
2
D convolution for separable signals}
\centering
If
$
h[n
_
1, n
_
2] = h
_
1[n
_
1]h
_
2[n
_
2]
$
:
\[
(
x
\ast
h
)[
n_
1
, n_
2
]
=
\sum
_{k_
1
=
-
\infty
}^{
\infty
}h_
1
[
n_
1
-
k_
1
]
\sum
_{k_
2
=
-
\infty
}^{
\infty
} x
[
k_
1
,k_
2
]
h_
2
[
n_
2
-
k_
2
]
\]
\vspace
{
1
em}
\begin
{itemize}
\item
each column of
$
x[n
_
1, n
_
2]
$
is a
1
D signal
$
x
_{
n
_
1
}
[n]
$
\item
convolve each column
$
x
_{
n
_
1
}
[n]
$
with
$
h
_
2[n]
$
to obtain the
2
D intermediate signal
$
c[n
_
1, n
_
2]
$
\item
each row of
$
c[n
_
1, n
_
2]
$
is a
1
D signal
$
c
_{
n
_
2
}
[n]
$
\item
convolve each row
$
c
_{
n
_
2
}
[n]
$
with
$
h
_
1[n]
$
to obtain the final output
\end
{itemize}
\end
{frame}
\begin
{frame}
\frametitle
{
2
D convolution for separable signals}
If
$
h[n
_
1, n
_
2]
$
is an
$
M
_
1
\times
M
_
2
$
finite
-
support signal:
\begin
{itemize}
\item
non
-
separable convolution:
$
M
_
1 M
_
2
$
operations per output sample
\item
separable convolution:
$
M
_
1 + M
_
2
$
operations per output sample
!
\end
{itemize}
\end
{frame}
\begin
{frame}
\frametitle
{The two
-
dimensional Discrete Fourier Transform}
Straightforward extension of th
1
D
-
DFT to two dimensions:
\begin
{itemize}
\item
an
$
N
_
1
\times
N
_
2
$
signal
$
x[n
_
1,n
_
2]
$
yields
$
N
_
1 N
_
2
$
DFT coefficients
\item
DFT computes the similarity between
$
x[n
_
1,n
_
2]
$
and the DFT basis vectors
\item
the
$
N
_
1 N
_
2
$
basis vectors are
$
N
_
1
\times
N
_
2
$
sinusoidal signals
\end
{itemize}
\end
{frame}
\begin
{frame}
\frametitle
{
2
D
-
DFT: analysis and synthesis}
Analysis formula:
\[
X
[
k_
1
, k_
2
]
=
\sum
_{n_
1
=
0
}^{N_
1
-
1
}
\sum
_{n_
2
=
0
}^{N_
2
-
1
} x
[
n_
1
,n_
2
]
e^{
-
j
\frac
{
2
\pi
}{N_
1
} n_
1
k_
1
} e^{
-
j
\frac
{
2
\pi
}{N_
2
} n_
2
k_
2
}
\]
\vspace
{
1
em}
Synthesis formula:
\[
x
[
n_
1
,n_
2
]
=
\frac
{
1
}{N_
1
N_
2
}
\sum
_{k_
1
=
0
}^{N_
1
-
1
}
\sum
_{k_
2
=
0
}^{N_
2
-
1
} X
[
k_
1
, k_
2
]
e^{j
\frac
{
2
\pi
}{N_
1
} n_
1
k_
1
} e^{j
\frac
{
2
\pi
}{N_
2
} n_
2
k_
2
}
\]
\end
{frame}
\begin
{frame}
\frametitle
{
2
D
-
DFT basis vectors}
\centering
There are
$
N
_
1 N
_
2
$
orthogonal basis vectors for an
$
N
_
1
\times
N
_
2
$
image:
\[
w_{k_
1
,k_
2
}
[
n_
1
,n_
2
]
=
e^{j
\frac
{
2
\pi
}{N_
1
} n_
1
k_
1
} e^{j
\frac
{
2
\pi
}{N_
2
} n_
2
k_
2
}
\]
\vspace
{
1
em}
for
$
n
_
1, k
_
1 = 0, 1,
\ldots
, N
_
1-1
$
and
$
n
_
2, k
_
2 = 0, 1,
\ldots
, N
_
2-1
$
\end
{frame}
\def\dftbv
#
1
#
2
#
3
#
4
{
\psset
{unit
=
0
.
4
mm}
\begin
{pspicture}
(-
70
,
-
75
)(
70
,
10
)
\psset
{Alpha
=
40
,Beta
=
30
}
\psplotThreeD
[
hiddenLine
=
true,plotstyle
=
line,drawStyle
=
xyLines,yPlotpoints
=
100
,xPlotpoints
=
100
,linewidth
=
0
.
5
pt
](
0
,
100
)(
0
,
100
)
{
%
x
3
.
60
mul #
1
mul y
3
.
6
mul #
2
mul add cos
5
mul}
\pstThreeDPut
(
30
,
-
40
,
0
)
{
\small
$
k
_
1=#3, k
_
2=#4
$
}
\end
{pspicture}}
\begin
{frame}
\frametitle
{
2
D
-
DFT basis vectors
(
real part
)
}
\centering
\begin
{tabular}{ccc}
\dftbv
{
1
}{
0
}{
1
}{
0
} &
\hspace
{
3
em} &
\dftbv
{
0
}{
1
}{
0
}{
1
}
\\
\dftbv
{
4
}{
0
}{
4
}{
0
} & &
\dftbv
{
0
}{
4
}{
0
}{
4
}
\end
{tabular}
\end
{frame}
\begin
{frame}
\frametitle
{
2
D
-
DFT basis vectors
(
real part
)
}
\centering
\begin
{tabular}{ccc}
\dftbv
{
1
}{
2
}{
1
}{
2
} &
\hspace
{
3
em} &
\dftbv
{
1
}{
98
}{
1
}{N_
2
-
1
}
\\
\dftbv
{
90
}{
2
}{N
-
10
}{
2
} & &
\dftbv
{
5
}{
93
}{
5
}{N
-
7
}
\end
{tabular}
\end
{frame}
\begin
{frame}
\frametitle
{
2
D DFT}
\psset
{linecolor
=
darkred}
2
D
-
DFT basis vectors are separable, and so is the
2
D
-
DFT:
\[
X
[
k_
1
, k_
2
]
=
%
\hlBox
{t
1
}{green
!
30
}{
\displaystyle
\sum
_{n_
1
=
0
}^{N_
1
-
1
}
\left
[
\hlBox
{t
2
}{blue
!
30
}{
\displaystyle
\sum
_{n_
2
=
0
}^{N_
2
-
1
}
x
[
n_
1
,n_
2
]
e^{
-
j
\frac
{
2
\pi
}{N_
2
} n_
2
k_
2
}}
\right
]
e^{
-
j
\frac
{
2
\pi
}{N_
1
} n_
1
k_
1
}}
\]
\begin
{itemize}
\item
1
D
-
DFT along
$
n
_
2
$
\rnode
[
rc
]
{T
2
}{
(
the columns
)
~~}
\item
1
D
-
DFT along
$
n
_
1
$
\rnode
[
rc
]
{T
1
}{
(
the rows
)
~~}
\end
{itemize}
{
\nccurve
[
angleB
=-
90
]
{
-
>}{T
2
}{t
2
}}
{
\nccurve
[
angleB
=-
45
]
{
-
>}{T
1
}{t
1
}}
\end
{frame}
\end
{document}
Event Timeline
Log In to Comment