|
|
| Line 1: |
Line 1: |
| {{expert-subject|Mathematics|ex2=Systems|date=February 2010}}
| | Not much to write about me at all.<br>Lovely to be a member of wmflabs.org.<br>I really wish Im useful in one way .<br><br>Here is my weblog :: [http://www.winkgames.org/profile/552446/la91q Choosing the right ride for you mountain bike sizing.] |
| By the term '''multidimensional systems''' or '''m-D systems''' we mean the branch of (mathematical) [[systems theory]] where not only one [[Variable (mathematics)|variable]] exists (like time), but several independent variables.
| |
| Important problems like [[factorization]] and [[Stability theory|stability]] have recently attracted the interest of many researchers and practitioners.
| |
| | |
| The reason is that the factorization and stability of m-D systems (''m'' > 1) is not a straightforward extension of the factorization and stability of 1-D systems because for example the [[fundamental theorem of algebra]] does not exist in the [[Ring (mathematics)|ring]] of m-D (''m'' > 1) [[polynomials]].
| |
| | |
| == Applications ==
| |
| Multidimensional systems or m-D systems are the necessary mathematical background for modern [[digital image processing]] with many applications in [[biomedicine]], [[X-ray technology]] and [[satellite communications]]<ref>{{cite book|editor-last=Bose|editor-first=N.K.|title=Multidimensional Systems Theory, Progress, Directions and Open Problems in Multidimensional Systems|publisher=D. Reidel Publishing Company|location=Dordrecht, Holland|year=1985}}</ref>
| |
| .<ref>{{cite book|editor-last=Bose|editor-first=N.K.|title=Multidimensional Systems: Theory and Applications|publisher=IEEE Press|year=1979}}</ref>
| |
| There are also some studies combining m-D systems with [[partial differential equations]] (PDEs).
| |
| | |
| == Linear Multidimensional State-Space Model ==
| |
| | |
| A state-space model is a representation of a system in which the effect of all "prior" input values is contained by a state vector. In the case of an m-d system, each dimension has a state vector that contains the effect of prior inputs relative to that dimension. The collection of all such dimensional state vectors at a point constitutes the total state vector at the point.
| |
| | |
| Consider a uniform discrete space linear two-dimensional (2d) system that is space invariant and causal. It can be represented in matrix-vector form as follows:<ref name=Tzafestas>{{cite book|editor-last=Tzafestas|editor-first=S.G.|title=Multidimensional Systems: Techniques and Applications|publisher=Marcel-Dekker|location=New York|year=1986}}</ref><ref name=Kaczorek>{{cite book|last=Kaczorek|first=T.|title=Two-Dimensional Linear Systems|publisher=Springer-Verlag|series=Lecture Notes Contr. and Inform. Sciences|volume=68|year=1985}}</ref>
| |
| | |
| Represent the input vector at each point <math>(i,j)</math> by <math>u(i,j)</math>, the output vector by <math>y(i,j)</math> the horizontal state vector by <math>R(i,j)</math> and the vertical state vector by <math>S(i,j)</math>. Then the operation at each point is defined by:
| |
| | |
| <math>
| |
| \begin{array}{rcl}
| |
| R(i+1,j) = A_1R(i,j) + A_2S(i,j) + B_1u(i,j) \\
| |
| S(i,j+1) = A_3R(i,j) + A_4S(i,j) + B_2u(i,j) \\
| |
| y(i,j) = C_1R(i,j) +C_2S(i,j) + Du(i,j)
| |
| \end{array}
| |
| </math>
| |
| | |
| where <math>A_1, A_2, A_3, A_4, B_1, B_2, C_1, C_2</math> and <math>D</math> are matrices of appropriate dimensions.
| |
| | |
| These equations can be written more compactly by combining the matrices:
| |
| | |
| <math>
| |
| \begin{bmatrix}
| |
| R(i+1,j) \\
| |
| S(i,j+1) \\
| |
| y(i,j) \\
| |
| \end{bmatrix}
| |
| =
| |
| \begin{bmatrix}
| |
| A_1 & A_2 & B_1 \\
| |
| A_3 & A_4 & B_2 \\
| |
| C_1 & C_2 & D \\
| |
| \end{bmatrix}
| |
| \begin{bmatrix}
| |
| R(i,j) \\
| |
| S(i,j) \\
| |
| u(i,j) \\
| |
| \end{bmatrix}
| |
| </math>
| |
| | |
| Given input vectors <math>u(i,j)</math> at each point and initial state values, the value of each output vector can be computed by recursively performing the operation above.
| |
| | |
| == Multidimensional Transfer Function ==
| |
| | |
| A discrete linear two-dimensional system is often described by a partial difference equation in the form:
| |
| <math>\sum_{p,q=0,0}^{m,n}a_{p,q}y(i-p,j-q) = \sum_{p,q=0,0}^{m,n}b_{p,q}x(i-p,j-q)</math>
| |
| | |
| where <math>x(i,j)</math> is the input and <math>y(i,j)</math> is the output at point <math>(i,j)</math> and <math>a_{p,q}</math> and <math>b_{p,q}</math> are constant coefficients.
| |
| | |
| To derive a transfer function for the system the 2d '''Z'''-transform is applied to both sides of the equation above.
| |
| | |
| <math>\sum_{p,q=0,0}^{m,n}a_{p,q}z_1^{-p}z_2^{-q}Y(z_1,z_2) = \sum_{p,q=0,0}^{m,n}b_{p,q}z_1^{-p}z_2^{-q}X(z_1,z_2)</math>
| |
| | |
| Transposing yields the transfer function <math>T(z_1,z_2)</math>:
| |
| | |
| <math>T(z_1,z_2) = {Y(z_1,z_2) \over X(z_1,z_2)} = {\sum_{p,q=0,0}^{m,n}b_{p,q}z_1^{-p}z_2^{-q} \over \sum_{p,q=0,0}^{m,n}a_{p,q}z_1^{-p}z_2^{-q}}</math>
| |
| | |
| So given any pattern of input values, the 2d '''Z'''-transform of the pattern is computed and then multiplied by the transfer function <math>T(z_1,z_2)</math> to produce the '''Z'''-transform of the system output.
| |
| | |
| == Realization of a 2d Transfer Function ==
| |
| | |
| Often an image processing or other md computational task is described by a transfer function that has certain filtering properties, but it is desired to convert it to state-space form for more direct computation. Such conversion is referred to as realization of the transfer function.
| |
| | |
| Consider a 2d linear spatially invariant causal system having an input-output relationship described by:
| |
| | |
| <math>Y(z_1,z_2) = {\sum_{p,q=0,0}^{m,n}b_{p,q}z_1^{-p}z_2^{-q} \over \sum_{i,j=0,0}^{m,n}a_{p,q}z_1^{-p}z_2^{-q}}X(z_1,z_2)</math>
| |
| | |
| Two cases are individually considered 1) the bottom summation is simply the constant '''1''' 2)the top summation is simply a constant <math>k</math>. Case 1 is often called the “all-zero” or “finite impulse response” case, whereas case 2 is called the “all-pole” or “infinite impulse response” case. The general situation can be implemented as a cascade of the two individual cases. The solution for case 1 is considerably simpler than case 2 and is shown below.
| |
| | |
| === Case 1 - all zero or finite impulse response<ref name=Tzafestas /><ref name=Kaczorek /> ===
| |
| | |
| <math>Y(z_1,z_2) = \sum_{p,q=0,0}^{m,n}b_{p,q}z_1^{-p}z_2^{-q}X(z_1,z_2)</math>
| |
| | |
| The state-space vectors will have the following dimensions:
| |
| | |
| <math>R (1 \times m), S (1 \times n), x (1 \times 1)</math> and <math>y (1 \times 1)</math>
| |
| | |
| Each term in the summation involves a negative (or zero) power of <math>z_1</math> and of <math>z_2</math> which correspond to a delay (or shift) along the respective dimension of the input <math>x(i,j)</math>. This delay can be effected by placing <math>1</math>’s along the super diagonal in the <math>A_1</math>. and <math>A_4</math> matrices and the multiplying coefficients <math>b_{i,j}</math> in the proper positions in the <math>A_2</math>. The value <math>b_{0,0}</math> is placed in the upper position of the <math>B_1</math> matrix, which will multiply the input <math>x(i,j)</math> and add it to the first component of the <math>R_{i,j}</math> vector. Also, a value of <math> b_{0,0}</math> is placed in the <math>D</math> matrix which will multiply the input <math>x(i,j)</math> and add it to the output <math>y</math>.
| |
| The matrices then appear as follows:
| |
| | |
| <math>A_1 = \begin{bmatrix}0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 1 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 1 & 0 & \cdots & 0 & 0 \\
| |
| \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 0 & 0 & \cdots & 1 & 0 \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>A_2 = \begin{bmatrix}0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>A_3 = \begin{bmatrix}
| |
| b_{1,n} & b_{2,n} & b_{3,n} & \cdots & b_{m-1,n} & b_{m,n} \\
| |
| b_{1,n-1} & b_{2,n-1} & b_{3,n-1} & \cdots & b_{m-1, n-1} & b_{m,n-1} \\
| |
| b_{1,n-2} & b_{2,n-2} & b_{3,n-2} & \cdots & b_{m-1, n-2} & b_{m,n-2} \\
| |
| \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
| |
| b_{1,2} & b_{2,2} & b_{3,2} & \cdots & b_{m-1,2} & b_{m,2} \\
| |
| b_{1,1} & b_{2,1} & b_{3,1} & \cdots & b_{m-1,1} & b_{m,1} \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>A_4 = \begin{bmatrix}0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 1 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 1 & 0 & \cdots & 0 & 0 \\
| |
| \vdots & \vdots & \vdots & \vdots & \vdots & \vdots \\
| |
| 0 & 0 & 0 & \cdots & 0 & 0 \\
| |
| 0 & 0 & 0 & \cdots & 1 & 0 \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>B_1 = \begin{bmatrix}1 \\
| |
| 0 \\
| |
| 0\\
| |
| 0\\
| |
| \vdots \\
| |
| 0 \\
| |
| 0 \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>B_2 = \begin{bmatrix}
| |
| b_{0,n} \\
| |
| b_{0,n-1} \\
| |
| b_{0,n-2} \\
| |
| \vdots \\
| |
| b_{0,2} \\
| |
| b_{0,1} \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>C_1 = \begin{bmatrix} b_{1,0} & b_{2,0} & b_{3,0} & \cdots & b_{m-1,0} & b_{m,0} \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>C_2 = \begin{bmatrix}0 & 0 & 0 & \cdots & 0 & 1 \\
| |
| \end{bmatrix}</math>
| |
| | |
| <math>D = \begin{bmatrix}b_{0,0} \end{bmatrix}</math>
| |
| | |
| == References ==
| |
| {{reflist}}
| |
| | |
| [[Category:Digital imaging]]
| |
| [[Category:Partial differential equations]]
| |
| [[Category:Stability theory]]
| |