Multidimensional system

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:

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

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

where ${\displaystyle A_1,A_2,A_3,A_4,B_1,B_2,C_1,C_2}$ and ${\displaystyle D}$ are matrices of appropriate dimensions.

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

${\displaystyle \left[\begin{array}{c}R(i+1,j)\\ S(i,j+1)\\ y(i,j)\end{array}\right]=\left[\begin{array}{ccc}{A}_1& A_2& B_1\\ A_3& A_4& B_2\\ C_1& C_2& D\end{array}\right]\left[\begin{array}{c}R(i,j)\\ S(i,j)\\ u(i,j)\end{array}\right]}$

Given input vectors ${\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.

Multidimensional transfer function

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)}$

where ${\displaystyle x(i,j)}$ is the input and ${\displaystyle y(i,j)}$ is the output at point ${\displaystyle (i,j)}$ and ${\displaystyle a_{p,q}}$ and ${\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)}$

Transposing yields the transfer function ${\displaystyle T(z_1,z_2)}$:

${\displaystyle T(z_1,z_2)=\frac{Y(z_1,z_2)}{X(z_1,z_2)}=\frac{\sum _{p,q=0,0}^{m,n}{b}_{p,q}{z}_1^{-p}{z}_2^{-q}}{\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)}$ 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:

${\displaystyle Y(z_1,z_2)=\frac{\sum _{p,q=0,0}^{m,n}{b}_{p,q}{z}_1^{-p}{z}_2^{-q}}{\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}$. 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

${\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),S(1\times n),x(1\times 1)}$ and ${\displaystyle y(1\times 1)}$

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

${\displaystyle A_1=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& 0\\ 1& 0& 0& \cdots & 0& 0\\ 0& 1& 0& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 0& 0\\ 0& 0& 0& \cdots & 1& 0\end{array}\right]}$

${\displaystyle A_2=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& 0\\ 0& 0& 0& \cdots & 0& 0\\ 0& 0& 0& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 0& 0\\ 0& 0& 0& \cdots & 0& 0\end{array}\right]}$

${\displaystyle A_3=\left[\begin{array}{cccccc}{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}\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 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{array}\right]}$

${\displaystyle A_4=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& 0\\ 1& 0& 0& \cdots & 0& 0\\ 0& 1& 0& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & 0& 0\\ 0& 0& 0& \cdots & 1& 0\end{array}\right]}$

${\displaystyle B_1=\left[\begin{array}{c}1\\ 0\\ 0\\ 0\\ ⋮\\ 0\\ 0\end{array}\right]}$

${\displaystyle B_2=\left[\begin{array}{c}{b}_{0,n}\\ b_{0,n-1}\\ b_{0,n-2}\\ ⋮\\ b_{0,2}\\ b_{0,1}\end{array}\right]}$

${\displaystyle C_1=\left[\begin{array}{cccccc}{b}_{1,0}& b_{2,0}& b_{3,0}& \cdots & b_{m-1,0}& b_{m,0}\end{array}\right]}$

${\displaystyle C_2=\left[\begin{array}{cccccc}0& 0& 0& \cdots & 0& 1\end{array}\right]}$

${\displaystyle D=\left[\begin{array}{c}{b}_{0,0}\end{array}\right]}$