(29 intermediate revisions by the same user not shown)
Line 5: Line 5:
 
[[Category:image processing]]
 
[[Category:image processing]]
  
−
= [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] in Communication Networks Signal and Image processing (CS) =
+
<br>
−
= [[QE637_sol2012|Question 5, August 2012(Published on May 2017)]], Problem 2 =
+
<center>
 +
<font size="4"> [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] </font>
 +
 
 +
<font size="4"> Communication Networks Signal and Image processing (CS) </font>
 +
 
 +
<font size="4"> [[QE637_sol2012|Question 5, August 2012(Published on May 2017)]]</font>
 +
</center>
 +
 
 +
<font size="4">[[ QE637_sol2012_Q1 | Problem 1]],[[ QE637_sol2012_Q2 |2]]</font>
  
−
:[[QE637_sol2012_Q2| Solution 1]],[[QE637_sol2012_Q2|2]]
 
 
----
 
----
 
===Solution1:===
 
===Solution1:===
  
−
a)<br \>
+
a)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{{a}_{j}}^{{}}\delta (m,n-j)=}{{a}_{n}}^{{}}\delta (m) \\  
+
   & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}{a}_{n}\delta (m) \\  
 
  & \delta (m,n)=\left\{ \begin{matrix}
 
  & \delta (m,n)=\left\{ \begin{matrix}
−
  1_{{}}^{{}}_{{}}^{{}}m=n=0  \\
+
1\quad m=n=0  \\
−
  0_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}O.W  \\
+
0\qquad O.W  \\
−
\end{matrix},_{{}}^{{}} \right.\delta (m,n-j)=\left\{ \begin{matrix}
+
\end{matrix},   \right. \quad \delta (m,n-j)=\left\{ \begin{matrix}
−
  1_{{}}^{{}}_{{}}^{{}}m=0;_{{}}^{{}}n=j  \\
+
1\quad m=0;\ n=j  \\
−
  0_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}_{{}}^{{}}O.W  \\
+
0\qquad O.W  \\
 
\end{matrix} \right. \\  
 
\end{matrix} \right. \\  
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
b)<br \>
+
b)
 +
 
 
<math>
 
<math>
−
h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)}
+
\begin{align}
 +
  & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}{b}_{m}\delta (n) \\
 +
& \delta (m,n)=\left\{ \begin{matrix}
 +
  1\quad m=n=0  \\
 +
  0\qquad O.W  \\
 +
\end{matrix}, \right. \quad \delta (m-i,n)=\left\{ \begin{matrix}
 +
  1\quad m=i;\ n=0  \\
 +
  0\qquad O.W  \\
 +
\end{matrix} \right. \\
 +
\end{align}
 
</math>
 
</math>
  
−
c)<br \>
+
c)
 +
 
 
<math>
 
<math>
 
\begin{align}
 
\begin{align}
−
h(m,n) &= {h_1}(m,n)*{h_2}(m,n)\\
+
  & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}^{{}}\delta (m-i,n-j)}}={{b}_{m}}\ {{a}_{n}} \\  
−
&= (\sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)}) * (\sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)})\\
+
& z(m,n)=\sum\limits_{i=-N}^{N}{{{b}_{i}}\ y(m-i,n)=}\sum\limits_{i=-N}^{N}{{{b}_{i}}\ \left( \sum\limits_{j=-N}^{N}{{{a}_{j}}\ x(m-i,n-j)} \right)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ x(m-i,n-j)}}} \\
−
&= \sum\limits_{j = - N}^N {\sum\limits_{i = - N}^N {{a_j}{b_i}\delta (m - i,n - j)} }
+
& \delta (m-i,n-j)=\left\{ \begin{matrix}
 +
1\quad m=i;\ n=j  \\
 +
0\qquad O.W  \\
 +
\end{matrix} \right. \\
 
\end{align}
 
\end{align}
 
</math>
 
</math>
  
−
d)<br \>
+
d)
−
S1: need 2N+1 multiplies <br \>
+
−
S2: need 2N+1 multiplies <br \>
+
−
To implement the complete system with a single convolution:
+
−
filter <math>h(m,n)</math> is a <math>(2N+1)\times(2N+1)</math> filter, and for each location we need 2 multiplies, so in total, we need <math>2(2N+1)^2</math> multiplies.
+
  
−
<span style="color:green"> As <math> a_j b_i </math> can be calculated offline, if we consider that <math> a_j b_i </math> are merged in the filter <math> h(m,n)</math>, then will need <math> (2N+1)^2 </math> multiplies to implement the complete system with a single convolution.
+
Number of multiplies per output point to implement each individual system = 2N+1.
−
</span>
+
So, the number of multiplies per output point to implement each of the two individual systems is 2(2N+1) = 4N+2.
  
−
e) Two systems in sequence:
+
Number of multiplies per output point to implement the complete system with a single convolution is <math>\left( 2N+1 \right)\left( 2N+1 \right)\text{ }=4{{N}^{2}}+4N+1</math>
−
: advantages: need <math>(2N+1)^2</math> multiplies per output point, so it is computationally better;
+
−
: disadvantages: as there are two systems, may introduce more noise.
+
  
−
<span style="color:red"> Need only <math> 2(2N+1) </math> multiplies per output point. System S1 is to filter <math> x(m,n) </math> along one dimension, then we get the intermediate result <math> y(m,n) </math>. System S2 is to filter <math> y(m,n) </math> along the other dimension. We then obtain <math> z(m,n) </math>. So we only need <math> 2(2N+1) </math> multiplies per output point when intermediate results have been stored. 
+
e)  
−
</span>
+
 
 +
Implementing the two systems in sequence requires less computation, but it is more complex and more sensitive to noise.
 +
Implementing the two systems in a single complete system requires more computation, but it is simpler, less sensitive to noise, and more stable.
  
−
A single complete system:
 
−
: advantages: more stable, less sensitive to noise;
 
−
: disadvantages: need <math>2(2N+1)^2</math> multiplies per output point, so it needs more computation.
 
  
 
== Solution 2: ==
 
== Solution 2: ==
  
−
a)<br \>
+
a)
 +
 
 
<math>
 
<math>
−
h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)}
+
\begin{align}
 +
  & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m)\ \delta(n-j)=} {a}_{n}\ \delta (m) \\
 +
\end{align}
 
</math>
 
</math>
  
−
b)<br \>
+
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1) </span>
 +
 
 +
b)
 +
 
 
<math>
 
<math>
−
h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)}
+
\begin{align}
 +
  & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i)\ \delta(n)=}{b}_{m}\ \delta (n) \\
 +
\end{align}
 
</math>
 
</math>
  
−
c)<br \>
+
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1) </span>
 +
 
 +
c)
 +
 
 
<math>
 
<math>
−
h(m,n) = \sum\limits_{i = - N}^N {\sum\limits_{j = - N}^N {{b_i}{a_j}\delta (m - i,n - j)} }
+
\begin{align}
 +
  & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i,n-j)}}=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i)\ \delta (n-j)}}={{b}_{m}}\ {{a}_{n}} \\
 +
\end{align}
 
</math>
 
</math>
 +
 +
<span style="color:green"> The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)  </span>
  
 
d)  
 
d)  
−
<math> 2N+1 </math> multiplies for each of the two individual systems <br \>
 
−
<math>(2N+1)^2</math> multiplies for the complete system with a single convolution
 
  
−
<span style="color:green"> For the complete system with a single convolution, as in each filter location, we will multiply both <math> a_j </math> and <math> b_i </math>, so we need <math> 2(2N+1)^2 </math> multiplies in total. But if the student consider that we pre-process the system and calculate the complete filter parameters in advance, then <math> (2N+1)^2 </math> multiplies is correct. 
+
Individually: <math> 2(2N+1)=4N+2 </math> <br \>
−
</span>
+
Complete system: <math>{( 2N+1)}^{2}=4{{N}^{2}}+4N+1</math>  
  
−
e) Implement in sequence:
+
e)
−
: Advantage: Less multiplies, faster
+
−
: Disadvantage: Need space for intermediate result
+
  
−
Implement a complete system:
+
Fewer multipliers are required when implementing individually, but the system is more complicated.
−
: Advantage: Intuitive solution. No intermediate result
+
 
−
: Disadvantage: More multiplies, slower
+
More complete for the complete system.
 +
 
 +
<span style="color:green"> The Student didn't mention advantage/disadvantage of the complete system, it is just mentioned that "More complete for the complete system". (See Solution 1)  </span>
  
 
----
 
----
 
===Related Problem===
 
===Related Problem===
−
Consider a 2D linear space-invariant filter with input <math> x(m,n) </math>, output <math> y(m,n) </math>, and impulse response <math> h(m,n) </math>, so that <br \>
+
Consider the following 2-D LSI systems. The first system (S1) has input x(m, n) and output y(m, n), and the second system (S2) has input y(m, n) and output z(m, n).
−
: <math> y(m,n) = h(m,n)* x(m,n). </math> <br \>
+
−
The impulse response is given by
+
<center> <math>\begin{align}
−
: <math>
+
  & y(m,n)=ay(m,n-1)+x(m,n)\qquad (S1) \\
−
h(m,n) = \left\{\begin{matrix}
+
& z(m,n)=bz(m-1,n)+y(m,n)\qquad (S2) \\
−
\frac{1}{(2N+1)^2}, for \  |m|\leq N \  and\  |n|\leq N
+
\end{align}</math></center>  
−
\\
+
−
0, \quad\quad\quad\quad\quad otherwise
+
The third system (S3) is formed by the composition of (S1) and (S2) with input x(m, n) and output z(m,n) and impulse response <math>{{h}_{3}}(m,n)</math>.
−
\end{matrix}\right.
+
 
−
</math>
+
a) Calculate the 2-D impulse response, <math>{{h}_{1}}(m,n)</math>, of the first system (S1).
 +
 
 +
b) Calculate the 2-D impulse response, <math>{{h}_{2}}(m,n)</math>, of the second system (S2).
  
−
a) If implement this filter with 2D convolution, how many multiplies are needed per output value?
+
c) Calculate the 2-D impulse response, <math>{{h}_{3}}(m,n)</math>, of the complete system (S3).
  
−
b) Find a separable decomponsition of <math> h(m,n) </math> so that <br \>
+
d) Calculate the 2-D transfer function, <math>{{H}_{1}}({z}_{1},{z}_{2})</math>, of the first system (S1).
−
: <math> h(m,n) = g(m)f(n) </math> <br \>
+
−
where <math> g(m)</math> and <math> f(n)</math> are 1D functions.
+
  
−
c) How can the functions <math> g(m)</math> and <math> f(n)</math> be used to compute <math> y(m,n)</math>. What are the advantage and disadvantage of this approach?
+
e) Calculate the 2-D transfer function, <math>{{H}_{3}}({z}_{1},{z}_{2})</math>, of the first system (S3).  
  
 +
Refer to  [https://engineering.purdue.edu/~bouman/ece637/previous/ece637S2014/exams/exam1/exam.pdf <u>ECE637 Spring 2014 Exam1 Problem1</u>].<br>
  
 
----
 
----
 
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]:
 
[[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]:

Latest revision as of 19:43, 2 May 2017



ECE Ph.D. Qualifying Exam

Communication Networks Signal and Image processing (CS)

Question 5, August 2012(Published on May 2017)

Problem 1,2

Solution1:

a)

$ \begin{align} & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}{a}_{n}\delta (m) \\ & \delta (m,n)=\left\{ \begin{matrix} 1\quad m=n=0 \\ 0\qquad O.W \\ \end{matrix}, \right. \quad \delta (m,n-j)=\left\{ \begin{matrix} 1\quad m=0;\ n=j \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

b)

$ \begin{align} & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}{b}_{m}\delta (n) \\ & \delta (m,n)=\left\{ \begin{matrix} 1\quad m=n=0 \\ 0\qquad O.W \\ \end{matrix}, \right. \quad \delta (m-i,n)=\left\{ \begin{matrix} 1\quad m=i;\ n=0 \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

c)

$ \begin{align} & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}^{{}}\delta (m-i,n-j)}}={{b}_{m}}\ {{a}_{n}} \\ & z(m,n)=\sum\limits_{i=-N}^{N}{{{b}_{i}}\ y(m-i,n)=}\sum\limits_{i=-N}^{N}{{{b}_{i}}\ \left( \sum\limits_{j=-N}^{N}{{{a}_{j}}\ x(m-i,n-j)} \right)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ x(m-i,n-j)}}} \\ & \delta (m-i,n-j)=\left\{ \begin{matrix} 1\quad m=i;\ n=j \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $

d)

Number of multiplies per output point to implement each individual system = 2N+1. So, the number of multiplies per output point to implement each of the two individual systems is 2(2N+1) = 4N+2.

Number of multiplies per output point to implement the complete system with a single convolution is $ \left( 2N+1 \right)\left( 2N+1 \right)\text{ }=4{{N}^{2}}+4N+1 $

e)

Implementing the two systems in sequence requires less computation, but it is more complex and more sensitive to noise. Implementing the two systems in a single complete system requires more computation, but it is simpler, less sensitive to noise, and more stable.


Solution 2:

a)

$ \begin{align} & {{h}_{1}}(m,n)=\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m,n-j)=}\sum\limits_{j=-N}^{N}{{a}_{j}\delta (m)\ \delta(n-j)=} {a}_{n}\ \delta (m) \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

b)

$ \begin{align} & {{h}_{2}}(m,n)=\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i,n)=}\sum\limits_{i=-N}^{N}{{b}_{i}\delta (m-i)\ \delta(n)=}{b}_{m}\ \delta (n) \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

c)

$ \begin{align} & h(m,n)=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i,n-j)}}=\sum\limits_{i=-N}^{N}{\sum\limits_{j=-N}^{N}{{{b}_{i}}\ {{a}_{j}}\ \delta (m-i)\ \delta (n-j)}}={{b}_{m}}\ {{a}_{n}} \\ \end{align} $

The answer is correct, but it's not obvious how the solution is derived. (See Solution 1)

d)

Individually: $ 2(2N+1)=4N+2 $
Complete system: $ {( 2N+1)}^{2}=4{{N}^{2}}+4N+1 $

e)

Fewer multipliers are required when implementing individually, but the system is more complicated.

More complete for the complete system.

The Student didn't mention advantage/disadvantage of the complete system, it is just mentioned that "More complete for the complete system". (See Solution 1)

Related Problem

Consider the following 2-D LSI systems. The first system (S1) has input x(m, n) and output y(m, n), and the second system (S2) has input y(m, n) and output z(m, n).

$ \begin{align} & y(m,n)=ay(m,n-1)+x(m,n)\qquad (S1) \\ & z(m,n)=bz(m-1,n)+y(m,n)\qquad (S2) \\ \end{align} $

The third system (S3) is formed by the composition of (S1) and (S2) with input x(m, n) and output z(m,n) and impulse response $ {{h}_{3}}(m,n) $.

a) Calculate the 2-D impulse response, $ {{h}_{1}}(m,n) $, of the first system (S1).

b) Calculate the 2-D impulse response, $ {{h}_{2}}(m,n) $, of the second system (S2).

c) Calculate the 2-D impulse response, $ {{h}_{3}}(m,n) $, of the complete system (S3).

d) Calculate the 2-D transfer function, $ {{H}_{1}}({z}_{1},{z}_{2}) $, of the first system (S1).

e) Calculate the 2-D transfer function, $ {{H}_{3}}({z}_{1},{z}_{2}) $, of the first system (S3).

Refer to ECE637 Spring 2014 Exam1 Problem1.

Back to ECE QE page:

Retrieved from "https://www.projectrhea.org/rhea/index.php?title=QE637_sol2012_Q2&oldid=73130"
Shortcuts
Help Main Wiki Page Random Page Special Pages Log in
Search

Alumni Liaison

Basic linear algebra uncovers and clarifies very important geometry and algebra.

Dr. Paul Garrett