Separierbarkeit

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Das Wort Separierbarkeit bezeichnet in der Bildverarbeitung die Eigenschaft, dass sich die Impulsantwort eines zweidimensionalen Filters durch die Multiplikation zweier eindimensionalen Operatoren darstellen lässt. Somit kann die zweidimensionale Faltung zu zwei eindimensionalen Operationen reduziert werden, indem der zweite auf das Zwischenergebnis des ersten angewendet wird. In der Bildverarbeitung wird der ursprüngliche 2D-Filter in einen x- und y- Kern zerlegt, die dann hintereinander auf das Ursprungsbild angewandt werden. Eine Separierung einer 3 × 3 Matrix in zwei 1D-Vektoren muss folgendermaßen aussehen:


\alpha
\begin{bmatrix} 
    N' \\
    Z' \\
    S'
\end{bmatrix} 
*
\alpha '
\begin{bmatrix} 
    W & Z & O
\end{bmatrix}

=

\alpha \alpha '
\begin{bmatrix} 
    N'W & N'Z & N'O \\ 
    Z'W & Z'Z & Z'O \\
    S'W & S'Z & S'O
\end{bmatrix}

Es ist aber auch möglich, andere Eingabe- und Ausgabegrößen zu verwenden. So kann ein 5 × 5 Filter in zwei 3 × 3 Matrizen separiert werden.

Das Ziel der Separierung ist eine Einsparung von Rechenzeit. Die Anwendung von einem 2D N × N Filter benötigt  N^2 Lesezugriffe und Multiplikationen, sowie  N^2 -1 Additionen. Durch die Separierung kann der Rechenaufwand auf 2N Lesezugriffe und Multiplikationen und  2 (N-1) Additionen reduziert werden.

Eigenschaften[Bearbeiten]

Eine separierbare 3x3 Matrix A hat folgende Eigenschaft:

  • Rang(A) = dim(SR) = dim(ZR) = 1
  • ZR(A) ist orthogonal zum NR(A)

Beispiele[Bearbeiten]

1. Ein zweidimensionaler Glättungsfilter wird in diesem Beispiel separiert:


\frac{1}{3}
\begin{bmatrix} 
    1 \\ 1 \\ 1  
\end{bmatrix} 
*
\frac{1}{3}
\begin{bmatrix} 
    1 & 1 & 1
\end{bmatrix}

=

\frac{1}{9}
\begin{bmatrix} 
    1 & 1 & 1 \\ 
    1 & 1 & 1 \\
    1 & 1 & 1
\end{bmatrix}

2. Der Gauß-Filter (Weichzeichner)


\frac{1}{4}
\begin{bmatrix} 
    1 \\ 2 \\ 1  
\end{bmatrix} 
*
\frac{1}{4}
\begin{bmatrix} 
    1 & 2 & 1
\end{bmatrix}

=

\frac{1}{16}
\begin{bmatrix} 
    1 & 2 & 1 \\ 
    2 & 4 & 2 \\
    1 & 2 & 1
\end{bmatrix}

3. Der Sobel-Operator (Kantendetektion)


\mathbf{G_x} = \begin{bmatrix} 
\quad~ & \quad~ & \quad~ \\[-2.5ex]
1 & 0 & -1 \\
2 & 0 & -2 \\
1 & 0 & -1 
\end{bmatrix} * A =
\begin{bmatrix} 
    1 \\ 2 \\ 1  
\end{bmatrix} *
\begin{bmatrix} 
    +1 & 0 & -1
\end{bmatrix} * A

Dies funktioniert auch beim Prewitt-Operator.

Siehe auch[Bearbeiten]

Die Lineare Separierbarkeit (Klassifizierbarkeit) bezieht sich auf mathematische Relationen und sollte nicht mit Separierbarkeit in der Bildverarbeitung verwechselt werden.