Role of the rank of the filter mask matrix in image processing?

Question

I'm reading a material where it says that a filter mask or kernel can be separable if the matrix of the filter mask has a rank 1. The two slides which describes this are as below:

Reading these slides it seems to me that it's trying to mean that the averaging filter can be separable, while Laplacian of Gaussian(LoG) is not. But it doesn't make sense to me, because LoG is the combination of two filters, laplacian and gaussian while in the contrary the averaging filter is just one filter, how can an averaging filter be separable?

I'm really confused on this matter. It would be helpful if you can make any sense out of this and explain me. Thanks.

Answer 1

Separable just means you can do it in the x-direction and then in the y-direction and have it come out the same as if you did it in both dimensions simultaneously to begin with. It's not too hard to see that this will work for an average filter. If the filter is averaging over a 3x3 grid then in the 2-d case you take an average of nine values. In the separable filter case you first take three averages of three values. Then you average those three averages together. In both cases you get the same answer.

The separable case is much faster because you get to reuse some of the work you did in the x-dimension when you are doing the y-direction. In other words, each average of three values you computed in the x-direction will be used multiple times when filtering in the y-direction. The filters that can be made separable are precisely those whose matrix rank is one.

Answer 2

Theoretical filters for image processing are naturally 2D functions. Yet, since discrete images are sampled along a rectangular grid, and 2D convolutions used to be very expensive, a lot of standard discrete 2D filters are compact support and fast to compute. This includes being able to filter along rows or columns, in an independent fashion. And separability is a way to do that. For background, one can check How to find out if a transform matrix is separable?.

In the given examples of rank 1 (Average, Gaussian, Sobel):

• the average is evident: a non-zero constant matrix is rank $1$ (all rows or colums repeat one single row or col)
• Sobel is a tensor product of $3$-point discrete derivative $[1,\,0,\,-1]$ and $3$-point discrete Gaussian approximation $[1,\,2,\,1]$
• "Gaussian" is a tensor product of $3$-point discrete Gaussian approximations $[1,\,2,\,1]$

Those have a $3\times 3$ support. They are combination of 1D discretized operators (separable). A lot of other classicaly-taught operators are $3\times 3$, like the two Laplacian operators:

$$ \begin{bmatrix}0 &1 & 0\\1&-4 & 1\\0 &1 & 0\end{bmatrix} $$ and $$ \begin{bmatrix}1 &1 & 1\\1&-8 & 1\\1 &1 & 1\end{bmatrix} $$

They have higher rank, since they derive from some limited-support approximations of the genuine 2D, continuous opeator. For instance, you can find wider kernels ($5\times 5$, $7\times 7$), see for instance: Laplacian/Laplacian of Gaussian or Laplacian of Gaussian (LoG). More technical details can be found in Farid and Simoncelli or Kroon.