Contents
ECE Ph.D. Qualifying Exam in Communication Networks Signal and Image processing (CS)
Question 5, August 2012(Published on May 2017), Problem 2
- Solution 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\qquad m=n=0 \\ 0\quad O.W \\ \end{matrix}, \right. \delta (m,n-j)=\left\{ \begin{matrix} 1\qquad n=j \\ 0\qquad O.W \\ \end{matrix} \right. \\ \end{align} $
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?
