** **

The convolution operator in (1.18) has a number of properties that are straightforward extensions of 1-D results. Some of the more important are listed below.

Commutativity: The commutativity property states that the output of an LS1 system is not affected when the input and the impulse response interchange roles.

x(n_{1}, n_{2})*y(n_{1},
n_{2})=y(n_{1}, n_{2})*x(n_{1}, n_{2}) (1.19)

Associativity: The associativity property states that a
cascade of two LSI systems with impulse responses h_{1}(n_{1},
n_{2})** **and h_{2}(n_{1}, n_{2}) has the
same input-output relationship as one LSI system with impulse response h_{1}(n_{1},
n_{2})** * **h_{2}(n_{1}, n_{2})**.**

(x(n_{1},
n_{2})** * **y(n_{1}, n_{2})) *** **z(n_{1},
n_{2}) **= **x(n_{1}, n_{2}) * (y(n_{1}, n_{2})
*** **z(n_{1}, n_{2}))** **(1.20)

Distributivity: The distributivity property states that
a parallel combination of two LS1 systems with impulse responses h_{1}(n_{1},
n_{2}) and h_{2}(n_{1}, n_{2})** **has the
same input-output relationship as one LSI system with impulse response given by
h_{1}(n_{1}, n_{2}) + h_{2}(n_{1}, n_{2}).

x(n_{1}, n_{2}) *** **(y(n_{1},
n_{2}) + z(n_{1}, n_{2}))

=(x(n_{1},
n_{2}) *y(n_{1}, n_{2})) + (x(n_{1}, n_{2})**
* **z(n_{1}, n_{2})) (1.21)

Convolution with Shifted impulse : In a special case of
(1.22), when m_{1}**= **m_{2} **= **0, we see that the
impulse response of an identity system is d(n_{1}, n_{2}).

x(n_{1}, n_{2})***** d(n_{1
}- m_{1},n_{2 }- m_{2}) **= **x(n_{1 }-
m_{1},n_{2 }- m_{2}) (1.22)

The convolution of two sequences x(n_{1},
n_{2}) and h(n_{1}, n_{2}) can be obtained by
explicitly evaluating (1.18). It is often simpler and more instructive,
however, to evaluate (1.18) graphically. Specifically, the convolution sum in
(1.18) can be interpreted as multiplying two sequences x(k_{1}, k_{2})
and h(n_{1 }- k_{1}, n, - k_{2}), which are functions
of the variables k_{1 }and k_{2}, and summing the product over
all integer values of k_{1 }and k_{2}. The output, which is a
function of n_{1 }and n_{2} ,** **is the result of
convolving x(n_{1}, n_{2}) and h(n_{1}, n_{2}).**
**

** **

**Figure 1.14 : ** Example
of convolving two sequences

** **

** **

To illustrate, consider the two
sequences x(n_{1}, n_{2}) and h(n_{1}, n_{2}) ** **shown
in Figures 1.14(a) and (b). From x(n_{1}, n_{2})** **and h(n_{1},
n_{2}) , x(k_{1 }, k_{2}) and h(n_{1 }- k_{1},
n_{2} – k_{2}) as functions of k_{1} and k_{2 }can
be obtained, as shown in Figures 1.14(c)—(f). Note that g(k_{1 }– n_{1
}, k_{2 }– n_{2}) is g(k_{1}, k_{2})
shifted in the positive k_{1 }and k_{2} directions by n_{1}
and n_{2} points, respectively. Figures 1.14(d)—(f) show how to obtain
h(n_{1 }- k_{1}, n_{2} **- **k_{2}) as a
function of k_{1} and k_{2 }from h(n_{1}, n_{2})
in three steps. It is useful to remember how to obtain h(n_{1} - k_{1},n_{2}**
- **k_{2}) directly from h(n_{1}, n_{2}).** **One
simple way is to first change the variables n_{1} and n_{2}** **to
k_{1 }and k_{2} flip the sequence with respect to the origin,
and then shift the result in the positive k_{1 }and k_{2}
directions by n_{1} and n_{2}** **points respectively. Once
x(k_{1}, k_{2}) and h(n_{1 }- k_{1}, n_{2 }-
k_{2}) are obtained they can he multiplied and summed over k_{1 }and
k_{2 }to produce the output **at each different value of** (n_{1},
n_{2}). The result is shown in Figure 1.14(g). The graphical method
above is as follows ;

**METHOD I : **Graphical Method 1

**METHOD II : **Graphical Method 2

y(n_{1}, n_{2})=0 outside 0
£ n_{1 }£ 3 , 0 £ n_{2 }£ 3 (Because N=3 , M=2 , N+M-1 = 3+2-1 = **4**)

The result is

y(n_{1}, n_{2})=y(1,0)+ y(1,1)+ y(1,2)+
y(1,3) +y(2,0) +y(2,1)+ y(2,2)+ y(2,3)+ y(2,0)+ y(2,1)+ y(2,2)+ y(3,0)+y(3,1)
+y(3,2)+y(3,3) +y(4,0)+y(4,1)+y(4,2)+y(4,3)

This means the sum of 9 graphs sampled above which is as in Figure 1.16(c);

**METHOD III :**Mathematical
Method

_{}

** **

Let’s find the value of _{} at (2,2) ;

y(2,2)_{}10

_{}

For each value of
n_{1 }and n_{2 } we calculate _{} using the same method. The result is the sum of all results.

Note that because of the commutativity property x(n_{1},
n_{2})*y(n_{1}, n_{2})=y(n_{1}, n_{2})*x(n_{1},
n_{2}) we calculate the same result if we use

_{}

instead of

_{}

An LSI system is said to be separable, if its
impulse response h(n_{1}, n_{2})** **is a separable
sequence. For a separable system, it is possible to reduce the number of
arithmetic operations required to compute the convolution sum. For large**-**amounts
of data. as typically found in images, the computational reduction can be
considerable. To illustrate this, consider an input sequence x(n_{1}, n_{2})
of N x N points and an impulse response h(n_{1}, n_{2}) of M x
M points:

x(n_{1}, n_{2}) **= **0 outside 0 £ n_{1 }£ N –** **1 , 0 £ n_{2} £ N –** **1 (1.23)

and

h(n_{1}, n_{2})** = **0 outside 0 £ n_{1} £ M – 1 , 0 £ n_{2 }£ M - 1

where N » M in typical cases. The regions of (n_{1}, n_{2})**
**where x(n_{1}, n_{2})** **and h(n_{1}, n_{2})
can have nonzero amplitudes are shown in Figures 1.17(a) and (b). The output of
the system y(n_{1}, n_{2}), can be expressed as

_{}
(1.24)

The region of (n_{1}, n_{2}) where y(n_{1},
n_{2}) has nonzero amplitude is shown in Figure 1.17(c).

x(n_{1}, n_{2})
has N_{1} x N_{2} elements, where _{} and _{} .

x(n_{1}, n_{2}) = 0 outside _{} , _{} (1.25)

It can also be expressed as ;

x(n_{1}, n_{2}) = 0 outside _{} , _{} (1.26)

In the same manner
we can say that h(n_{1}, n_{2}) has M_{1} x M_{2}
elements _{} and
_{}.

h(n_{1}, n_{2}) = 0 outside _{} , _{} (1.27)

It can also be expressed as ;

h(n_{1}, n_{2}) = 0 outside _{} , _{} (1.28)

The notation _{} and _{} represents minimum
and maximum values of n_{1} given.

In this case the graphical limits
of y(n_{1}, n_{2}) is defined as ;

having _{}x_{} elements and

y(n_{1}, n_{2})=0
outside _{} ,
_{}

If (1.24) is used directly to compute y(n_{1}, n_{2}),
approximately (N + M-1)^{2}M^{2 }arithmetic operations (one
arithmetic operation **= **one multiplication and one addition) are required
since the number of nonzero output points is (N + M-1)^{2} and
computing each output point requires approximately M^{2 }arithmetic
operations. If h(n_{1}, n_{2})** **is a separable sequence,
it can be expressed as

h(n_{1}, n_{2}) **=**
h_{1}(n_{1}) h_{2}(n_{2})

h_{1}(n_{1}) **= **0 outside 0 £ n_{1 }£ M –** **1 , (1.29)

h_{2}(n_{2}) = 0 outside 0 £ n_{2} £ M – 1 ,

From (1.24) and (1.29) ,

_{} (1.30)

For a fixed _{} in (1.26) is a 1-D
convolution of x(k_{1},n_{2}) and h_{2}(n_{2}).

For example, using the notation

_{} (1.31)

f(0, n_{2}) is the result of 1-D convolution of x(0, n_{2})
with h_{2}(n_{2}). as shown in Figure 1.15. Since there are N
different values of k_{1 }for which x(k_{1}, k_{2}) is
nonzero, computing f(k_{1}, k_{2})** **requires N 1-D
convolutions and therefore requires approximately NM(N + M - 1) arithmetic
operations. Once f(k_{1}, n_{2})** **is computed, y(n_{1},
n_{2}) can be computed from (1.30) and (1.31) by

_{}** **(1.32)

** **

From (1.32), for a fixed n_{2}** , **y(n_{1},
n_{2}) is a 1-D convolution of h_{1}(n_{1}) and f(n_{1},
n_{2}). For example. y(n_{1}, 1) is the result of a 1-D
convolution of f(n_{1}, 1) and h_{1}(n_{1}). as shown
in Figure 1.18. where f(n_{1}, n_{2}) is obtained from f(k_{1},
n_{2}) by a simple change of variables. Since there are N + M - 1
different values of n_{2} ,computing y(n_{1}, n_{2})
from f(k_{1}, n_{2}) requires N + M - 1 1-D convolutions thus
approximately M(N + M - 1)^{2} arithmetic operations. Computing y(n_{1},
n_{2}) from (1.27) and (1.28), exploiting the separability of h(n_{1},
n_{2}), requires approximately NM(N + M — 1) + M(N + M **- **1)^{2}
arithmetic operations. This can be a considerable computational saving over (N
+ M — 1)^{2 }M^{2}. If we assume N» M, exploiting the
separability of h(n_{1}, n_{2}) reduces the number of
arithmetic operations by approximately a factor of M/2.

As an example, consider x(n_{1},n_{2})
and h(n_{1},n_{2}), shown in Figures 1.19(a) and (b). The
sequence h(n_{1},n_{2}) can he expressed as h_{1}(n_{1})h_{2}(n_{2}).
where h_{1}(n_{1}) and h_{2}(n_{2}) are shown
in Figures 1.19(c) and (d), respectively. The sequences f(n_{1},n_{2})
and y(n_{1},n_{2}) are shown in Figures 1.19(e) and (f).

In the above discussion, we
performed a 1-D convolution first for each column of x(n_{1},n_{2})
with h_{2}(n_{2}) and then a 1-D convolution for each row of
f(n_{1},n_{2})** **with h_{1}(n_{1}). By
changing the order of the two summations in (1.30) and following the same
procedure. it is simple to show that y(n_{1},n_{2}) can be
computed by performing a 1-D convolution first for each row of x(n_{1},n_{2})**
**with h_{1}(n_{1}) and then a 1-D convolution for each
column of the result with h_{2}(n_{2}). in the above
discussion, we have assumed that x(n_{1},n_{2}) and h(n_{1},n_{2})
are N_{1 }x N_{2}-point and M_{1 }X M_{2}-point
sequences respectively with N_{1 }= N_{2 }and M_{1 }= M_{2}
We note that the results discussed above can be generalized straightforwardly
to the case when N_{1} ¹ N_{2} and M_{1 }¹ M_{2}.