Separable Filters

For convolution / cross-correlation, we use kernels.

Application of an mXm kernel normally takes m2 operation. If the kernel is separable, then it takes only 2m operations.

Hence, some kernels K, can be split into UVT.

For any given K, we can determine if we can split it into separable kernel by taking its SVD.

Let u,z,v = SVD(K)
K is separable, if, Z[0]!= 0 and Z[!=0]=0
Then, U = √(Z[0]) X u1 and V = √(Z[0]) X v1T

See the Jupyter Notebook to see the implementation in python :

http://josephkj.in/wp-content/uploads/2017/01/SeparableFilters.html 

Leave a Reply

Your email address will not be published. Required fields are marked *