Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
dct2

Subject: dct2

From: astro mmi

Date: 28 Apr, 2010 00:40:24

Message: 1 of 7

Hi everyone,
   This is how I am trying to inplement the dct2 function using the equation for dct. I am not able to understand why the program runs into an infinite loop when i execute the code. Pls let me know where the error is and how I can enhance the speed of the program...
Thanx in advance


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

%To evaluate Discrete Cosine Transform
siz=size(i);
a=zeros(1,siz(1));
b=zeros(1,siz(1));
c=zeros(siz(1),siz(2));
for x=1:siz(1)
    for y=1:siz(2)
        for u=1:siz(1)
            for v=1:siz(2)
                if(u==1)
                    a(u)=sqrt(1/siz(1));
                else
                    a(u)=sqrt(2/siz(1));
                end
                b=a;
                c(u,v)=a(u)*b(v)*sum(sum(i(x,y)*cos(((2*x+1)*pi*u)/(2*siz(1)))*cos(((2*y+1)*pi*v)/(2*siz(1)))));
           end
        end
    end
end

Subject: dct2

From: astro mmi

Date: 28 Apr, 2010 00:54:05

Message: 2 of 7

Also I see that when I reduce the size of the image, it works and i am getting the dct.........which implies my for loops are running too long...........pls let me know how this efficiency can be enhanced and how my code can be made to run faster.......
Thanx in advance

"astro mmi" <pyarsa_madhu@yahoo.co.in> wrote in message <hr805o$gmh$1@fred.mathworks.com>...
> Hi everyone,
> This is how I am trying to inplement the dct2 function using the equation for dct. I am not able to understand why the program runs into an infinite loop when i execute the code. Pls let me know where the error is and how I can enhance the speed of the program...
> Thanx in advance
>
>
> i=imread('p_6_1.jpg');
> figure,imshow(i)
> title('Original image')
>
> %To evaluate Discrete Cosine Transform
> siz=size(i);
> a=zeros(1,siz(1));
> b=zeros(1,siz(1));
> c=zeros(siz(1),siz(2));
> for x=1:siz(1)
> for y=1:siz(2)
> for u=1:siz(1)
> for v=1:siz(2)
> if(u==1)
> a(u)=sqrt(1/siz(1));
> else
> a(u)=sqrt(2/siz(1));
> end
> b=a;
> c(u,v)=a(u)*b(v)*sum(sum(i(x,y)*cos(((2*x+1)*pi*u)/(2*siz(1)))*cos(((2*y+1)*pi*v)/(2*siz(1)))));
> end
> end
> end
> end

Subject: dct2

From: Roger Stafford

Date: 28 Apr, 2010 23:32:05

Message: 3 of 7

"astro mmi" <pyarsa_madhu@yahoo.co.in> wrote in message <hr805o$gmh$1@fred.mathworks.com>...
> Hi everyone,
> This is how I am trying to inplement the dct2 function using the equation for dct. I am not able to understand why the program runs into an infinite loop when i execute the code. Pls let me know where the error is and how I can enhance the speed of the program...
> Thanx in advance
>
> i=imread('p_6_1.jpg');
> figure,imshow(i)
> title('Original image')
>
> %To evaluate Discrete Cosine Transform
> siz=size(i);
> a=zeros(1,siz(1));
> b=zeros(1,siz(1));
> c=zeros(siz(1),siz(2));
> for x=1:siz(1)
> for y=1:siz(2)
> for u=1:siz(1)
> for v=1:siz(2)
> if(u==1)
> a(u)=sqrt(1/siz(1));
> else
> a(u)=sqrt(2/siz(1));
> end
> b=a;
> c(u,v)=a(u)*b(v)*sum(sum(i(x,y)*cos(((2*x+1)*pi*u)/(2*siz(1)))*cos(((2*y+1)*pi*v)/(2*siz(1)))));
> end
> end
> end
> end
------------
  I don't think this is doing what you want at all. When you compute c(u,v) there is no summing done since the x, y, u, v are all single values at this point and not vectors. If you are doing it with nested loops, the u- and v-loops should be on the outside:

 for u = 1:m
  for v = 1:n
   Calculate c(u,v) here by summing with respect to x and y
  end
 end

  However, you really ought to be able to do all this without any for-loops using just matrix products. That would probably give the fastest results, since matrix multiplication is what matlab specializes in.

Roger Stafford

Subject: dct2

From: Roger Stafford

Date: 29 Apr, 2010 03:37:04

Message: 4 of 7

  I would like to point out that an efficient algorithm should take advantage of the fact that in two-dimensional DCT, as a bare minimum, the periodic cosine function needs only to be called for the m-1 values

 cos(pi/2*1/m), cos(pi/2*2/m), cos(pi/2*3/m), ..., cos(pi/2*(m-1)/m)

and the n-1 values

 cos(pi/2*1/n), cos(pi/2*2/n), cos(pi/2*3/n), ..., cos(pi/2*(n-1)/n)

for an m by n image, a total of m+n-2 times altogether. All other cosine values can be obtained from these from periodicity and symmetry, and it is a waste of computation time calling the 'cos' function directly for each of the argument values occurring in the DCT formula.

  I notice that in your code you called 'cos' a total of 2*m^2*n^2 times, which for an image of appreciable size is an immense number of times and is undoubtedly large part of the reason it was taking so long.

Roger Stafford

Subject: dct2

From: astro mmi

Date: 29 Apr, 2010 15:52:04

Message: 5 of 7

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.


"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <hrausv$dht$1@fred.mathworks.com>...
> I would like to point out that an efficient algorithm should take advantage of the fact that in two-dimensional DCT, as a bare minimum, the periodic cosine function needs only to be called for the m-1 values
>
> cos(pi/2*1/m), cos(pi/2*2/m), cos(pi/2*3/m), ..., cos(pi/2*(m-1)/m)
>
> and the n-1 values
>
> cos(pi/2*1/n), cos(pi/2*2/n), cos(pi/2*3/n), ..., cos(pi/2*(n-1)/n)
>
> for an m by n image, a total of m+n-2 times altogether. All other cosine values can be obtained from these from periodicity and symmetry, and it is a waste of computation time calling the 'cos' function directly for each of the argument values occurring in the DCT formula.
>
> I notice that in your code you called 'cos' a total of 2*m^2*n^2 times, which for an image of appreciable size is an immense number of times and is undoubtedly large part of the reason it was taking so long.
>
> Roger Stafford

Subject: dct2

From: Roger Stafford

Date: 29 Apr, 2010 20:40:22

Message: 6 of 7

"astro mmi" <pyarsa_madhu@yahoo.co.in> wrote in message <hrc9v4$jpc$1@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

Subject: dct2

From: astro mmi

Date: 29 Apr, 2010 21:47:03

Message: 7 of 7

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@mindspring.com.invalid> wrote in message <hrcqrm$78$1@fred.mathworks.com>...
> "astro mmi" <pyarsa_madhu@yahoo.co.in> wrote in message <hrc9v4$jpc$1@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

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us