Multidimensional system explained

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.

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

Represent the input vector at each point

(i,j) by u(i,j) , the output vector by y(i,j) the horizontal state vector by R(i,j) and the vertical state vector by S(i,j) . Then the operation at each point is defined by:\begin{align} 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{align}

where

A _{1,} A _{2,} A _{3,} A _{4,} B _{1,} B _{2,} C _{1,} C _{2} and D are matrices of appropriate dimensions.

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

\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

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.

Multidimensional transfer function

A discrete linear two-dimensional system is often described by a partial difference equation in the form:

\sum ^{m,n} _{p,q =0 , 0} a _{p,q} y(i - p,j - q) = \sum ^{m,n} _{p,q =0 , 0} b _{p,q} x(i - p,j - q)

where

x(i,j) is the input and y(i,j) is the output at point (i,j) and a _{p,q} and 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.

\sum ^{m,n} _{p,q =0 , 0} a _{p,q} z ^{- p} _{1} z ^{- q} _{2} Y(z _{1,z} _{2)} = \sum ^{m,n} _{p,q =0 , 0} b _{p,q} z ^{- p} _{1} z ^{- q} _{2} X(z _{1,z} _{2)}

Transposing yields the transfer function

T(z _{1,z} _{2)} :T(z _{1,z} _{2)} = {Y(z _{1,z} _{2)} \over X(z _{1,z} _{2)}} = {\sum ^{m,n} _{p,q =0 , 0} b _{p,q} z ^{- p} _{1} z ^{- q} _{2} \over \sum ^{m,n} _{p,q =0 , 0} a _{p,q} z ^{- p} _{1} z ^{- q} _{2} }

So given any pattern of input values, the 2d Z-transform of the pattern is computed and then multiplied by the transfer function

T(z _{1,z} _{2)} 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:

Y(z _{1,z} _{2)} = {\sum ^{m,n} _{p,q =0 , 0} b _{p,q} z ^{- p} _{1} z ^{- q} _{2} \over \sum ^{m,n} _{p,q =0 , 0} a _{p,q} z ^{- p} _{1} z ^{- q} _{2} }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

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.

Example: all zero or finite impulse response

Y(z _{1,z} _{2)} = \sum ^{m,n} _{p,q =0 , 0} b _{p,q} z ^{- p} _{1} z ^{- q} _{2} X(z _{1,z} _{2)}

The state-space vectors will have the following dimensions:

R ( 1 x m), S ( 1 x n), x ( 1 x 1 ) and y ( 1 x 1 )

Each term in the summation involves a negative (or zero) power of

z _{1} and of z _{2} which correspond to a delay (or shift) along the respective dimension of the input x(i,j) . This delay can be effected by placing 1 ’s along the super diagonal in the A _{1} . and A _{4} matrices and the multiplying coefficients b _{i,j} in the proper positions in the A _{2} . The value b _{0,0} is placed in the upper position of the B _{1} matrix, which will multiply the input x(i,j) and add it to the first component of the R _{i,j} vector. Also, a value of b _{0,0} is placed in the D matrix which will multiply the input x(i,j) and add it to the output y .The matrices then appear as follows:A _{1} = \begin{bmatrix} 0 & 0 & 0 & … & 0 & 0 \\ 1 & 0 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & … & 0 & 0 \\ 0 & 0 & 0 & … & 1 & 0 \end{bmatrix} A _{2} = \begin{bmatrix} 0 & 0 & 0 & … & 0 & 0 \\ 0 & 0 & 0 & … & 0 & 0 \\ 0 & 0 & 0 & … & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & … & 0 & 0 \\ 0 & 0 & 0 & … & 0 & 0 \end{bmatrix} A _{3} = \begin{bmatrix} b _{1,n} & b _{2,n} & b _{3,n} & … & b _{m-1,n} & b _{m,n} \\ b _{1,n-1} & b _{2,n-1} & b _{3,n-1} & … & b _{m-1,} & b _{m,n-1} \\ b _{1,n-2} & b _{2,n-2} & b _{3,n-2} & … & b _{m-1,} & b _{m,n-2} \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ b _{1,2} & b _{2,2} & b _{3,2} & … & b _{m-1,2} & b _{m,2} \\ b _{1,1} & b _{2,1} & b _{3,1} & … & b _{m-1,1} & b _{m,1} \end{bmatrix} A _{4} = \begin{bmatrix} 0 & 0 & 0 & … & 0 & 0 \\ 1 & 0 & 0 & … & 0 & 0 \\ 0 & 1 & 0 & … & 0 & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots \\ 0 & 0 & 0 & … & 0 & 0 \\ 0 & 0 & 0 & … & 1 & 0 \end{bmatrix} B _{1} = \begin{bmatrix} 1 \\ 0 \\ 0 \\ 0 \\ \vdots \\ 0 \\ 0 \end{bmatrix} B _{2} = \begin{bmatrix} b _{0,n} \\ b _{0,n-1} \\ b _{0,n-2} \\ \vdots \\ b _{0,2} \\ b _{0,1} \end{bmatrix} C _{1} = \begin{bmatrix} b _{1,0} & b _{2,0} & b _{3,0} & … & b _{m-1,0} & b _{m,0} \\ \end{bmatrix} C _{2} = \begin{bmatrix} 0 & 0 & 0 & … & 0 & 1 \\ \end{bmatrix} D = \begin{bmatrix}b _{0,0} \end{bmatrix}

Notes and References

1. Book: Bose. N.K.. Multidimensional Systems Theory, Progress, Directions and Open Problems in Multidimensional Systems. D. Reidel Publishing Company. Dordre http, Holland. 1985.
2. Book: Bose . N.K.. Multidimensional Systems: Theory and Applications. IEEE Press. 1979.
3. Book: Tzafestas. S.G.. Multidimensional Systems: Techniques and Applications. Marcel-Dekker. New York. 1986.
4. Book: Kaczorek, T.. Two-Dimensional Linear Systems. Springer-Verlag. Lecture Notes Contr. and Inform. Sciences. 68. 1985.