Guten Morgen theoretiker,
sei \(H\in\mathbb{R}^{n\times n}\) ein voll besetzter Filterkern. Ich nehme an, dass Du mit vollbesetzt \(\forall x,y\in H:h(x,y)\neq 0\) meinst. Für die nicht separierte Variante benötigst Du ...
... bei \(5\times 5-\)Filterkernen \(5^2\) Multiplikationen, \(5^2-1\) Additionen und eine Division (Normierung), also \(50\) Operationen.
... bei \(7\times 7-\)Filterkernen \(7^2\) Multiplikationen, \(7^2-1\) Additionen und eine Division (Normierung), also \(98\) Operationen.
... bei \(n\times n-\)Filterkernen \(n^2\) Multiplikationen, \(n^2-1\) Additionen und eine Division (Normierung), also \(n^2+n^2-1+1=2n^2\) Operationen\(\Longrightarrow\mathcal{O}(n^2)\).
Für die separierte Variante benötigst Du ...
... bei \(5\times 5-\)Filterkernen \(5\) Multiplikationen, \(5-1\) Additionen, eine Division (Normierung) und das alles mal \(2\) also \(20\) Operationen.
... bei \(7\times 7-\)Filterkernen \(7\) Multiplikationen, \(7-1\) Additionen, eine Division (Normierung) und das alles mal \(2\) also \(28\) Operationen.
... bei \(n\times n-\)Filterkernen \(n\) Multiplikationen, \(n-1\) Additionen, eine Division (Normierung) und das alles mal \(2\) also \((n+n-1+1)\cdot 2=2n\cdot 2 = 4n\) Operationen\(\Longrightarrow\mathcal{O}(n)\).
Deshalb solltest Du bei der Programmierung von z.B. Fragmentshadern die Filterkerne separieren, da Du dadurch eine Menge Flops sparst. Beachte aber, dass z.B. der Median-Filter nicht separierbar ist (Erosion, Dilatation und die "Symmetrischen" schon).
André
