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?

Back to ECE QE page: