The University of Texas at Austin
Two-Dimensional Linear Shift-Invariant Systems
Lecture and notes by Prof. Brian L. Evans (UT Austin)
Scribe: Mr. Yue Chen (UT Austin)
Based on notes by Prof. Russell M. Mersereau (Georgia Tech)
Review of Linearity
A system is linear if it is homogeneous and additive.
1. Homogeneity: scaling the input results in scaling the output by the same amount for all possible scaling values
T[ a x(n1, n2) ] = a T[ x(n1, n2) ] for all a
2. Additivity: the response of two signals added together at the input is equal to the sum of the individual responses.
T[ x1(n1, n2) + x2(n1, n2) ] = T[ x1(n1, n2) ] + T[ x2(n1, n2) ]
Shortcut for testing whether or not a system is linear:
1. input a signal that is identically zero for all coordinates (n1, n2), and
2. if the output signal is not identically zero for all coordinates (n1, n2), then it is not linear
What about the following systems? Input is x(n1, n2), and output is y(n1, n2).
1. y(n1, n2) = x(n1, n2) identity
2. y(n1, n2) = x(n1, n2) + 1 add DC offset
3. y(n1, n2) = x2(n1, n2) squarer
4. y(n1, n2) = c(n1, n2) x(n1, n2) spatially-dependent gain c(n1, n2)
Review of Shift Invariance
A system is shift-invariant if a shift in the spatial index results in the same shift on the output, for all possible shifts. For a discrete-time signal, the index is integer-valued.
Shift Invariance: T[ x(n1 ( m1, n2 ( m2) ] = T[ x(n1, n2) ] |
n1= n1 ( m1, n2 = n2 ( m2
1. y(n1, n2) = x(n1, n2)
2. y(n1, n2) = x(n1, n2) + 1
3. y(n1, n2) = x2(n1, n2)
4. y(n1, n2) = c(n1, n2) x(n1, n2)
2-D Linear Shift-Invariant (LSI) Sequences
Advantages
1. Mathematics are tractable and rich.
2. LSI systems are uniquely represented by their 2-D impulse response.
3. Linear transforms. Complex exponentials are eigenfunctions LSI systems, and Laplace and z transforms are based on complex exponential kernels.
4. Additive decompositions are useful.
But:
Superpositions are not quite as useful for images, e.g. occlusion of objects in a scene.
2-D Convolution
• An arbitrary 2-D sequence can be decomposed into a linear combination of shifted impulses.
[pic]
• Applying a linear shift-invariant system T that operates on spatial indices (n1, n2) to the input signal x(n1, n2)
[pic]
Applying addivity,
[pic]
Applying homogeneity with respect to (n1, n2),
[pic]
The term h(n1, n2) = T[δ(n1, n2) ] is the impulse response of the system.
A linear shift-invariant system is uniquely characterized by its impulse response.
Substituting h(n1, n2), we obtain the two-dimensional linear convolution formula:
[pic]
• Two-dimensional linear convolution denoted with two asterisks: [pic]
➢ Conceptually: same as 1-D
➢ Mechanically: a lot more work
Example 2-D linear convolution:
[pic]
[pic]
Shape of output sequence can assume one of five different forms depending on value of (n1,n2).
Case #1 [pic]
Case #2[pic]
Case #3 [pic]
Case #4 [pic]
Case #5 [pic]
[pic]
Validate your answer by checking the value of [pic]at the endpoints of each interval
Note that[pic]is separable.
Theorem:
[pic]
Additional Theorems:
1. [pic]
2.
3.
What is the implicit assumption for these theorems to hold?
Separable Systems:
A system is separable if its impulse response is separable sequence.
[pic]
Separable systems can be implemented faster than non-separable ones by using more memory to store intermediate computations.
[pic][pic]
[pic]
[pic]
Computational Savings:
[pic] 2MN to compute the separable convolution in the two dimensions
(M+N-1)2 to multiply out the separable result
-----------------------
T [ ]
[pic]
[pic]
Figure 1
[pic]
n2
n1
h(n1 , n2)
h(n1-k1, n2-k2)
k1
k2
x(n1 , n2)
n1
n2
N1-1
N2-1
Figure 2:
h(n1,n2) fills quadrant
N1 N2 Samples
x(k1 , k2)
k1
k2
n1
n2
[pic]
N1-1
N2-1
k2
k1
N1-1
N2-1
n1
n21
g
n1
N2-1
N1-1
k1
k2
n21
g**h
N2-1
N1-1
k1
k2
h
g
n2
Figure 7
N2-1
N1-1
k1
k2
n1
Figure 6
Figure 5
Figure 4
[pic]
Figure 3
h
g
h
g+h
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related searches
- university of texas at austin
- university of texas austin tx
- university of texas at austin online
- university of texas at dallas graduate school
- university of texas austin graduate
- university of texas at dallas housing
- university of texas at austin online masters
- university of texas austin graduate school
- university of texas austin nursing
- university of texas at austin athletics
- university of texas austin certificate
- university of texas austin tuition cost