Prev: PSNR of edge and noisy edge
Next: Reading a 2D array from a mat file in C++
From: Roger Stafford on 29 Apr 2010 16:40
"astro mmi" <pyarsa_madhu(a)yahoo.co.in> wrote in message <hrc9v4$jpc$1(a)fred.mathworks.com>...
> Thank you Sir. I am having another query now. If I try to write the cos terms as matrix, then each time x and y is varied, there is still a dependency on u and v value which also keep varying. In the definition of DCT2 both x and u are appearing within the cosine and how canI separate them.
- - - - - - -
In answer to your question of varying x and u independently and also y and v, you can use the matlab 'kron' function for this purpose. Also the 'meshgrid' or 'ndgrid' functions could equally well have been used. The following shows the two-dimensional DCT done first along the lines I think you intended, adding terms one at a time using four nested loops, and then done using 'kron' in a vectorized manner. Note that I haven't bothered to include the normalizing terms - that is your a and b - here.

The difference in time of execution for the two methods with the values of m and n given here is very great indeed. This is not only because of the vectorization, however. It is also due to the fact that in the four nested loop method the same cosine values are being repeatedly called, whereas this does not happen in the vectorized method. By actual count the first method calls on 'cos' a total of 2*m^2*n^2 = 1,280,000 times versus m^2+n^2 = 1649 times in the second method, a factor of 776 to 1. This ratio rapidly gets worse for larger values of m and n, which is why you thought you were in an infinite loop.

You should be aware that there is a fast cosine transform method analogous to the fast fourier transform algorithm which is much more efficient that either of these methods but I won't attempt to go into that here.

----------
clear
m = 32; n = 25;
img = randn(m,n);

% First Method
tic
c1 = zeros(m,n);
for u = 1:m
for v = 1:n
s = 0;
for x = 1:m
for y = 1:n
s = s + img(x,y) * cos(pi/(2*m)*(2*x-1)*(u-1)) * cos(pi/(2*n)*(2*y-1)*(v-1));
end
end
c1(u,v) = s;
end
end
toc

% Second Method
tic
c2 = cos(pi/(2*m)*kron(1:2:2*m-1,(0:m-1)')) * img * ...
cos(pi/(2*n)*kron((1:2:2*n-1)',0:n-1));
toc

format long
disp(max(max(abs(c-c2))))
----------

Roger Stafford
From: astro mmi on 29 Apr 2010 17:47
Suppose I tried to modify my code as instructed by you to use matrices. This is how the code looks like

i=imread('p_6_1.jpg');
figure,imshow(i)
title('Original image')

siz=size(i);
a=zeros(1,siz(1));
b=zeros(1,siz(1));
c=zeros(siz(1),siz(2));

t=zeros(256,256);
for u=1:siz(1)
for x=1:siz(1)
t(u,x)=cos(((2*x+1)*pi*u)/(2*siz(1)));
end
end
p=zeros(256,256);
for v=1:siz(1)
for y=1:siz(1)
p(v,y)=cos(((2*y+1)*pi*v)/(2*siz(1)));
end
end

for u=1:siz(1)
if (u==1)
a(u)=sqrt(1/siz(1));
else
a(u)=sqrt(2/siz(1));
end
end

for v=1:siz(1)
if (v==1)
b(v)=sqrt(1/siz(1));
else
b(v)=sqrt(2/siz(1));
end
end

h1=double(i)*t*p;
j=b'*a;
o=j*h1;
figure,imshow(o)

The final image just appears to be a black and white image. I think I am missing out on the correct datatype. I have tried using the matrix method as suggested by you sir. Pls help. Thanx in advance
"Roger Stafford" <ellieandrogerxyzzy(a)mindspring.com.invalid> wrote in message <hrcqrm$78$1(a)fred.mathworks.com>...
> "astro mmi" <pyarsa_madhu(a)yahoo.co.in> wrote in message <hrc9v4$jpc$1(a)fred.mathworks.com>...
> > Thank you Sir. I am having another query now. If I try to write the cos terms as matrix, then each time x and y is varied, there is still a dependency on u and v value which also keep varying. In the definition of DCT2 both x and u are appearing within the cosine and how canI separate them.
> - - - - - - -
> In answer to your question of varying x and u independently and also y and v, you can use the matlab 'kron' function for this purpose. Also the 'meshgrid' or 'ndgrid' functions could equally well have been used. The following shows the two-dimensional DCT done first along the lines I think you intended, adding terms one at a time using four nested loops, and then done using 'kron' in a vectorized manner. Note that I haven't bothered to include the normalizing terms - that is your a and b - here.
>
> The difference in time of execution for the two methods with the values of m and n given here is very great indeed. This is not only because of the vectorization, however. It is also due to the fact that in the four nested loop method the same cosine values are being repeatedly called, whereas this does not happen in the vectorized method. By actual count the first method calls on 'cos' a total of 2*m^2*n^2 = 1,280,000 times versus m^2+n^2 = 1649 times in the second method, a factor of 776 to 1. This ratio rapidly gets worse for larger values of m and n, which is why you thought you were in an infinite loop.
>
> You should be aware that there is a fast cosine transform method analogous to the fast fourier transform algorithm which is much more efficient that either of these methods but I won't attempt to go into that here.
>
> ----------
> clear
> m = 32; n = 25;
> img = randn(m,n);
>
> % First Method
> tic
> c1 = zeros(m,n);
> for u = 1:m
> for v = 1:n
> s = 0;
> for x = 1:m
> for y = 1:n
> s = s + img(x,y) * cos(pi/(2*m)*(2*x-1)*(u-1)) * cos(pi/(2*n)*(2*y-1)*(v-1));
> end
> end
> c1(u,v) = s;
> end
> end
> toc
>
> % Second Method
> tic
> c2 = cos(pi/(2*m)*kron(1:2:2*m-1,(0:m-1)')) * img * ...
> cos(pi/(2*n)*kron((1:2:2*n-1)',0:n-1));
> toc
>
> format long
> disp(max(max(abs(c-c2))))
> ----------
>
> Roger Stafford
First  |  Prev  | 
Pages: 1 2
Prev: PSNR of edge and noisy edge
Next: Reading a 2D array from a mat file in C++