| (9 intermediate revisions by 3 users not shown) | |||
| Line 1: | Line 1: | ||
| − | + | [[Category:ECE]] | |
| + | [[Category:QE]] | ||
| + | [[Category:CNSIP]] | ||
| + | [[Category:problem solving]] | ||
| + | [[Category:image processing]] | ||
| − | = | + | = [[ECE_PhD_Qualifying_Exams|ECE Ph.D. Qualifying Exam]] in Communication Networks Signal and Image processing (CS) = |
| − | + | = [[QE637_T|Question 5, August 2012]], Part 2 = | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| + | :[[ QE637_T_Pro1 | Part 1 ]],[[ QE637_T_Pro2 | 2 ]] | ||
| + | ---- | ||
===Solution:=== | ===Solution:=== | ||
| Line 32: | Line 24: | ||
c)<br \> | c)<br \> | ||
<math> | <math> | ||
| − | \begin{ | + | \begin{align} |
| − | h(m,n) = {h_1}(m,n)*{h_2}(m,n)\\ | + | h(m,n) &= {h_1}(m,n)*{h_2}(m,n)\\ |
| − | + | &= (\sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)}) * (\sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)})\\ | |
| − | + | &= \sum\limits_{j = - N}^N {\sum\limits_{i = - N}^N {{a_j}{b_i}\delta (m - i,n - j)} } | |
| − | \end{ | + | \end{align} |
</math> | </math> | ||
| Line 44: | Line 36: | ||
To implement the complete system with a single convolution: | 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. | 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. | ||
| + | </span> | ||
e) Two systems in sequence: | e) Two systems in sequence: | ||
: advantages: need <math>(2N+1)^2</math> multiplies per output point, so it is computationally better; | : 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. | : 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. | ||
| + | </span> | ||
A single complete system: | A single complete system: | ||
| Line 53: | Line 51: | ||
: disadvantages: need <math>2(2N+1)^2</math> multiplies per output point, so it needs more computation. | : disadvantages: need <math>2(2N+1)^2</math> multiplies per output point, so it needs more computation. | ||
| − | [[ | + | == Solution 2: == |
| + | |||
| + | a)<br \> | ||
| + | <math> | ||
| + | h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)} | ||
| + | </math> | ||
| + | |||
| + | b)<br \> | ||
| + | <math> | ||
| + | h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)} | ||
| + | </math> | ||
| + | |||
| + | c)<br \> | ||
| + | <math> | ||
| + | h(m,n) = \sum\limits_{i = - N}^N {\sum\limits_{j = - N}^N {{b_i}{a_j}\delta (m - i,n - j)} } | ||
| + | </math> | ||
| + | |||
| + | 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. | ||
| + | </span> | ||
| + | |||
| + | e) Implement in sequence: | ||
| + | : Advantage: Less multiplies, faster | ||
| + | : Disadvantage: Need space for intermediate result | ||
| + | |||
| + | Implement a complete system: | ||
| + | : Advantage: Intuitive solution. No intermediate result | ||
| + | : Disadvantage: More multiplies, slower | ||
| + | |||
| + | ---- | ||
| + | ===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 \> | ||
| + | : <math> y(m,n) = h(m,n)* x(m,n). </math> <br \> | ||
| + | The impulse response is given by | ||
| + | : <math> | ||
| + | h(m,n) = \left\{\begin{matrix} | ||
| + | \frac{1}{(2N+1)^2}, for \ |m|\leq N \ and\ |n|\leq N | ||
| + | \\ | ||
| + | 0, \quad\quad\quad\quad\quad otherwise | ||
| + | \end{matrix}\right. | ||
| + | </math> | ||
| + | |||
| + | a) If implement this filter with 2D convolution, how many multiplies are needed per output value? | ||
| + | |||
| + | b) Find a separable decomponsition of <math> h(m,n) </math> so that <br \> | ||
| + | : <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? | ||
| + | |||
| + | |||
| + | ---- | ||
| + | [[ECE_PhD_Qualifying_Exams|Back to ECE QE page]]: | ||
Latest revision as of 10:07, 13 September 2013
Contents
ECE Ph.D. Qualifying Exam in Communication Networks Signal and Image processing (CS)
Question 5, August 2012, Part 2
- Part 1 , 2
Solution:
a)
$ h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)} $
b)
$ h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)} $
c)
$ \begin{align} h(m,n) &= {h_1}(m,n)*{h_2}(m,n)\\ &= (\sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)}) * (\sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)})\\ &= \sum\limits_{j = - N}^N {\sum\limits_{i = - N}^N {{a_j}{b_i}\delta (m - i,n - j)} } \end{align} $
d)
S1: need 2N+1 multiplies
S2: need 2N+1 multiplies
To implement the complete system with a single convolution:
filter $ h(m,n) $ is a $ (2N+1)\times(2N+1) $ filter, and for each location we need 2 multiplies, so in total, we need $ 2(2N+1)^2 $ multiplies.
As $ a_j b_i $ can be calculated offline, if we consider that $ a_j b_i $ are merged in the filter $ h(m,n) $, then will need $ (2N+1)^2 $ multiplies to implement the complete system with a single convolution.
e) Two systems in sequence:
- advantages: need $ (2N+1)^2 $ multiplies per output point, so it is computationally better;
- disadvantages: as there are two systems, may introduce more noise.
Need only $ 2(2N+1) $ multiplies per output point. System S1 is to filter $ x(m,n) $ along one dimension, then we get the intermediate result $ y(m,n) $. System S2 is to filter $ y(m,n) $ along the other dimension. We then obtain $ z(m,n) $. So we only need $ 2(2N+1) $ multiplies per output point when intermediate results have been stored.
A single complete system:
- advantages: more stable, less sensitive to noise;
- disadvantages: need $ 2(2N+1)^2 $ multiplies per output point, so it needs more computation.
Solution 2:
a)
$ h_1(m,n) = \sum\limits_{j = - N}^N {{a_j}\delta(m,n - j)} $
b)
$ h_2(m,n) = \sum\limits_{i = - N}^N {{b_i}\delta(m-i,n)} $
c)
$ h(m,n) = \sum\limits_{i = - N}^N {\sum\limits_{j = - N}^N {{b_i}{a_j}\delta (m - i,n - j)} } $
d)
$ 2N+1 $ multiplies for each of the two individual systems
$ (2N+1)^2 $ multiplies for the complete system with a single convolution
For the complete system with a single convolution, as in each filter location, we will multiply both $ a_j $ and $ b_i $, so we need $ 2(2N+1)^2 $ multiplies in total. But if the student consider that we pre-process the system and calculate the complete filter parameters in advance, then $ (2N+1)^2 $ multiplies is correct.
e) Implement in sequence:
- Advantage: Less multiplies, faster
- Disadvantage: Need space for intermediate result
Implement a complete system:
- Advantage: Intuitive solution. No intermediate result
- Disadvantage: More multiplies, slower
Related Problem
Consider a 2D linear space-invariant filter with input $ x(m,n) $, output $ y(m,n) $, and impulse response $ h(m,n) $, so that
- $ y(m,n) = h(m,n)* x(m,n). $
The impulse response is given by
- $ h(m,n) = \left\{\begin{matrix} \frac{1}{(2N+1)^2}, for \ |m|\leq N \ and\ |n|\leq N \\ 0, \quad\quad\quad\quad\quad otherwise \end{matrix}\right. $
a) If implement this filter with 2D convolution, how many multiplies are needed per output value?
b) Find a separable decomponsition of $ h(m,n) $ so that
- $ h(m,n) = g(m)f(n) $
where $ g(m) $ and $ f(n) $ are 1D functions.
c) How can the functions $ g(m) $ and $ f(n) $ be used to compute $ y(m,n) $. What are the advantage and disadvantage of this approach?
