Skip to main content
Source Link
Dirk
  • 12.7k
  • 6
  • 54
  • 97

$\newcommand{\RR}{\mathbb{R}}$Filtering an image $u\in\RR^{n\times m}$ by some filter $h\in \RR^{2r+1\times 2s+1}$ means computing $$ \sum_{k=-r}^r\sum_{l=-s}^s u_{i+k,j+l}h_{k,l} $$ at every pixel $(i,j)$. This is basically a convolution (up the reflection of $h$). To compute one pixel of the filtered image, one needs $O((2r+1)(2s+1))$ operations. If the filter is separable, i.e. it is of the form $h=ab^T$ with $a\in\RR^{2r+1}$ and $b\in\RR^{2s+1}$, the filtering can be done by filtering with $a$ first and then with $b$ and the amount of operations is $O((2r+1)+(2s+1))$ which may be much smaller. Of course, a separable filter is just a rank-one matrix, so some software uses the SVD of the filter to check, how good the filter $h$ can be approximated by a rank-one matrix.

One can get a little more: Using the SVD one can write $$ h = \sigma_1 a_1b_i^T + \cdots + \sigma_k a_k b_k^T $$ and represent $h$ as the sum of $k$ separable filters and, depending on $k$, using this representation may still save a few computations (and, of course one may just omit very small singular valued $\sigma_j$ to same more).

Post Made Community Wiki by Dirk