Multidimensional system

In mathematical systems theory, a multidimensional system or m-D system is a system in which not only one independent variable exists (like time), but there are several independent variables.

Important problems such as factorization and stability of m-D systems (m > 1) have recently attracted the interest of many researchers and practitioners. The reason is that the factorization and stability 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 of m-D (m > 1) polynomials.

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.^{[1] [2]} There are also some studies combining m-D systems with partial differential equations (PDEs).

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:^{[3] [4]}

Represent the input vector at each point ${\displaystyle (i,j)}${\displaystyle (i,j)} by ${\displaystyle u(i,j)}${\displaystyle u(i,j)}, the output vector by ${\displaystyle y(i,j)}${\displaystyle y(i,j)} the horizontal state vector by ${\displaystyle R(i,j)}${\displaystyle R(i,j)} and the vertical state vector by ${\displaystyle S(i,j)}${\displaystyle S(i,j)}. Then the operation at each point is defined by:

${\displaystyle {\begin{aligned}R(i+1,j)&=A_{1}R(i,j)+A_{2}S(i,j)+B_{1}u(i,j)\\S(i,j+1)&=A_{3}R(i,j)+A_{4}S(i,j)+B_{2}u(i,j)\\y(i,j)&=C_{1}R(i,j)+C_{2}S(i,j)+Du(i,j)\end{aligned}}}${\displaystyle {\begin{aligned}R(i+1,j)&=A_{1}R(i,j)+A_{2}S(i,j)+B_{1}u(i,j)\\S(i,j+1)&=A_{3}R(i,j)+A_{4}S(i,j)+B_{2}u(i,j)\\y(i,j)&=C_{1}R(i,j)+C_{2}S(i,j)+Du(i,j)\end{aligned}}}

where ${\displaystyle A_{1},A_{2},A_{3},A_{4},B_{1},B_{2},C_{1},C_{2}}${\displaystyle A_{1},A_{2},A_{3},A_{4},B_{1},B_{2},C_{1},C_{2}} and ${\displaystyle D}${\displaystyle D} are matrices of appropriate dimensions.

These equations can be written more compactly by combining the matrices:

${\displaystyle {\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}}}${\displaystyle {\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}}}

Given input vectors ${\displaystyle u(i,j)}${\displaystyle u(i,j)} at each point and initial state values, the value of each output vector can be computed by recursively performing the operation above.

A discrete linear two-dimensional system is often described by a partial difference equation in the form: ${\displaystyle \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)}${\displaystyle \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)}

where ${\displaystyle x(i,j)}${\displaystyle x(i,j)} is the input and ${\displaystyle y(i,j)}${\displaystyle y(i,j)} is the output at point ${\displaystyle (i,j)}${\displaystyle (i,j)} and ${\displaystyle a_{p,q}}${\displaystyle a_{p,q}} and ${\displaystyle b_{p,q}}${\displaystyle b_{p,q}} are constant coefficients.

To derive a transfer function for the system the 2d Z-transform is applied to both sides of the equation above.

${\displaystyle \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})}${\displaystyle \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})}

Transposing yields the transfer function ${\displaystyle T(z_{1},z_{2})}${\displaystyle T(z_{1},z_{2})}:

${\displaystyle 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}}}${\displaystyle 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}}}

So given any pattern of input values, the 2d Z-transform of the pattern is computed and then multiplied by the transfer function ${\displaystyle T(z_{1},z_{2})}${\displaystyle T(z_{1},z_{2})} to produce the Z-transform of the system output.

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:

${\displaystyle Y(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}}X(z_{1},z_{2})}${\displaystyle Y(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}}X(z_{1},z_{2})}

Two cases are individually considered 1) the bottom summation is simply the constant 1 2) the top summation is simply a constant ${\displaystyle k}${\displaystyle k}. 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.

${\displaystyle 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})}${\displaystyle 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})}

The state-space vectors will have the following dimensions:

${\displaystyle R(1\times m),\quad S(1\times n),\quad x(1\times 1)}${\displaystyle R(1\times m),\quad S(1\times n),\quad x(1\times 1)} and ${\displaystyle y(1\times 1)}${\displaystyle y(1\times 1)}

Each term in the summation involves a negative (or zero) power of ${\displaystyle z_{1}}${\displaystyle z_{1}} and of ${\displaystyle z_{2}}${\displaystyle z_{2}} which correspond to a delay (or shift) along the respective dimension of the input ${\displaystyle x(i,j)}${\displaystyle x(i,j)}. This delay can be effected by placing ${\displaystyle 1}${\displaystyle 1}’s along the super diagonal in the ${\displaystyle A_{1}}${\displaystyle A_{1}}. and ${\displaystyle A_{4}}${\displaystyle A_{4}} matrices and the multiplying coefficients ${\displaystyle b_{i,j}}${\displaystyle b_{i,j}} in the proper positions in the ${\displaystyle A_{2}}${\displaystyle A_{2}}. The value ${\displaystyle b_{0,0}}${\displaystyle b_{0,0}} is placed in the upper position of the ${\displaystyle B_{1}}${\displaystyle B_{1}} matrix, which will multiply the input ${\displaystyle x(i,j)}${\displaystyle x(i,j)} and add it to the first component of the ${\displaystyle R_{i,j}}${\displaystyle R_{i,j}} vector. Also, a value of ${\displaystyle b_{0,0}}${\displaystyle b_{0,0}} is placed in the ${\displaystyle D}${\displaystyle D} matrix which will multiply the input ${\displaystyle x(i,j)}${\displaystyle x(i,j)} and add it to the output ${\displaystyle y}${\displaystyle y}. The matrices then appear as follows:

${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &1&0\end{bmatrix}}}${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &1&0\end{bmatrix}}}

${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &0&0\end{bmatrix}}}${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &0&0\end{bmatrix}}}

${\displaystyle 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 &\ddots &\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}}}${\displaystyle 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 &\ddots &\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}}}

${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &1&0\end{bmatrix}}}${\displaystyle 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 &\ddots &\vdots &\vdots \0円&0&0&\cdots &0&0\0円&0&0&\cdots &1&0\end{bmatrix}}}

${\displaystyle B_{1}={\begin{bmatrix}1\0円\0円\0円\\\vdots \0円\0円\end{bmatrix}}}${\displaystyle B_{1}={\begin{bmatrix}1\0円\0円\0円\\\vdots \0円\0円\end{bmatrix}}}

${\displaystyle B_{2}={\begin{bmatrix}b_{0,n}\\b_{0,n-1}\\b_{0,n-2}\\\vdots \\b_{0,2}\\b_{0,1}\end{bmatrix}}}${\displaystyle B_{2}={\begin{bmatrix}b_{0,n}\\b_{0,n-1}\\b_{0,n-2}\\\vdots \\b_{0,2}\\b_{0,1}\end{bmatrix}}}

${\displaystyle C_{1}={\begin{bmatrix}b_{1,0}&b_{2,0}&b_{3,0}&\cdots &b_{m-1,0}&b_{m,0}\\\end{bmatrix}}}${\displaystyle C_{1}={\begin{bmatrix}b_{1,0}&b_{2,0}&b_{3,0}&\cdots &b_{m-1,0}&b_{m,0}\\\end{bmatrix}}}

${\displaystyle C_{2}={\begin{bmatrix}0&0&0&\cdots &0&1\\\end{bmatrix}}}${\displaystyle C_{2}={\begin{bmatrix}0&0&0&\cdots &0&1\\\end{bmatrix}}}

${\displaystyle D={\begin{bmatrix}b_{0,0}\end{bmatrix}}}${\displaystyle D={\begin{bmatrix}b_{0,0}\end{bmatrix}}}

^{[3] [4]}

• Digital imaging
• Partial differential equations
• Stability theory
• Multidimensional signal processing

• Articles with short description
• Short description matches Wikidata