Masking - decompose convolution

Hi,
my project for master Eng. involves image masking. it uses A mask of size 8x8. i wish to make the masking process faster(if possible).

with this mask I need 64 MAC per point. I tried thinking of FFT but it does not make the process less in my case. I then I though if it is possible to break down the mask as below:
G(8x8)=original mask
Ga=? (smaller than 8x8)
Gb=? (smaller than 8x8)
Ga*Gb=G

I don’t know if it is possible and how it is possible. would you please help me with this.
PS: My matrix is symmetrical only over one axis so I am not expecting a row and a column matrix. but something smaller than 8x8 that saves some process is good enough for me.
PS2: below is a MATLAB code that produces and illustrates the mask
-------------------------
clc;clear;close all
hw=4;

G=zeros(2*hw);%Gaussian
X=zeros(2*hw);%linear
for row=0:7
for col=0:7
trow=row-4+.5;
tcol=col-4+.5;
t=trow^2/2+tcol^2/2;
g=exp(-t);
G(row+1,col+1)=g;
end
end
for i=-hw+1:hw
for j=-hw+1:hw
X(i+hw, j+hw)=j-.5;
end
end

mask = G .* X;%final mask is the element wise product of X and Guassian

%show:
surf(mask);title('8x8 mask');
mask,
%figure;surf(G);title('Gaussian');
%figure;surf(X);title('X');
-----------------
maks 1e-3*
[
-0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403 0.0167
-0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261 0.3364
-2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606 2.4856
-6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355 6.7566
-6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355 6.7566
-2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606 2.4856
-0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261 0.3364
-0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403 0.0167
];
with thanks
kian zarrin Start a New Thread

Your mask is separable along the horizontal and vertical axes. Try svd(mask)
to verify that there is only one non-zero singular value. That means that
you can decompose your mask into a column vector and a row vector, and
reduce the number of multiplications and additions to 16 instead of 64.
Cheers,

Patrick

On Mon, Feb 23, 2009 at 6:58 AM, wrote:

> Hi,
> my project for master Eng. involves image masking. it uses A mask of size
> 8x8. i wish to make the masking process faster(if possible).
>
> with this mask I need 64 MAC per point. I tried thinking of FFT but it does
> not make the process less in my case. I then I though if it is possible to
> break down the mask as below:
> G(8x8)=original mask
> Ga=? (smaller than 8x8)
> Gb=? (smaller than 8x8)
> Ga*Gb=G
>
> I don't know if it is possible and how it is possible. would you please
> help me with this.
> PS: My matrix is symmetrical only over one axis so I am not expecting a row
> and a column matrix. but something smaller than 8x8 that saves some process
> is good enough for me.
> PS2: below is a MATLAB code that produces and illustrates the mask
> -------------------------
> clc;clear;close all
> hw=4;
>
> G=zeros(2*hw);%Gaussian
> X=zeros(2*hw);%linear
> for row=0:7
> for col=0:7
> trow=row-4+.5;
> tcol=col-4+.5;
> t=trow^2/2+tcol^2/2;
> g=exp(-t);
> G(row+1,col+1)=g;
> end
> end
> for i=-hw+1:hw
> for j=-hw+1:hw
> X(i+hw, j+hw)=j-.5;
> end
> end
>
> mask = G .* X;%final mask is the element wise product of X and Guassian
>
> %show:
> surf(mask);title('8x8 mask');
> mask,
> %figure;surf(G);title('Gaussian');
> %figure;surf(X);title('X');
> -----------------
> maks > 1e-3*
> [
> -0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403
> 0.0167
> -0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261
> 0.3364
> -2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606
> 2.4856
> -6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355
> 6.7566
> -6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355
> 6.7566
> -2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606
> 2.4856
> -0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261
> 0.3364
> -0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403
> 0.0167
> ];
> with thanks
> kian zarrin Start a New Thread

Thank you so much for your help :)
for those who want to follow this case
i found wikipedia>>singular matrix decomposition>>applications>>seperable usefull. my matrix has a single svd and therefore saperable to a row and column vector. for matrixes that has less than N (where N is size of mask) svd computation can be simplified ([?]i guess).
regards
kian
Hi,
>my project for master Eng. involves image masking. it uses A mask of size 8x8. i wish to make the masking process faster(if possible).
>
>with this mask I need 64 MAC per point. I tried thinking of FFT but it does not make the process less in my case. I then I though if it is possible to break down the mask as below:
>G(8x8)=original mask
>Ga=? (smaller than 8x8)
>Gb=? (smaller than 8x8)
>Ga*Gb=G
>
>I don’t know if it is possible and how it is possible. would you please help me with this.
>PS: My matrix is symmetrical only over one axis so I am not expecting a row and a column matrix. but something smaller than 8x8 that saves some process is good enough for me.
>PS2: below is a MATLAB code that produces and illustrates the mask
>-------------------------
>clc;clear;close all
>hw=4;
>
>G=zeros(2*hw);%Gaussian
>X=zeros(2*hw);%linear
>for row=0:7
> for col=0:7
> trow=row-4+.5;
> tcol=col-4+.5;
> t=trow^2/2+tcol^2/2;
> g=exp(-t);
> G(row+1,col+1)=g;
> end
>end
>for i=-hw+1:hw
> for j=-hw+1:hw
> X(i+hw, j+hw)=j-.5;
> end
>end
>
>mask = G .* X;%final mask is the element wise product of X and Guassian
>
>%show:
>surf(mask);title('8x8 mask');
>mask,
>%figure;surf(G);title('Gaussian');
>%figure;surf(X);title('X');
>-----------------
>maks >1e-3*
>[
> -0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403 0.0167
> -0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261 0.3364
> -2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606 2.4856
> -6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355 6.7566
> -6.7566 -96.9355 -429.7572 -389.4004 389.4004 429.7572 96.9355 6.7566
> -2.4856 -35.6606 -158.0988 -143.2524 143.2524 158.0988 35.6606 2.4856
> -0.3364 -4.8261 -21.3964 -19.3871 19.3871 21.3964 4.8261 0.3364
> -0.0167 -0.2403 -1.0653 -0.9652 0.9652 1.0653 0.2403 0.0167
>];
>with thanks
>kian zarrin Start a New Thread