Vectorize a per-pixel classification

Hi, I am using the following code to calculate the likelihood of every pixel x in a RGB image, belonging to a given class;

for count=1:height
      for count2=1:width
          %pixel vector x to be classified
          x=[image(count,count2,1);image(count,count2,2);image(count,count2,3)];

             %for each class
              for count3=1:noOfClasses
                detZ = pDet(count3);
                invZ = pInv(:,:,count3);
                y=(pMean(count3,:)');
                %calculate the likelihood
                post= 1/sqrt((2*pi)^2*detZ) * exp(-(x(:,1)-y)'*invZ*(x(:,1)-y)/2);

                ......

The application is classification of video frames and so the current approach using for loops is impractical as it is very slow.

Any suggestions?

thanks, John

Answer 1

[Teja Muppirala]

The key is recognizing that:

diag(R*A*R') == sum(R*A.*R,2);

Try the following code. It does exactly what your code does, using only one loop, and runs 100 times faster.

clc
I = imread('peppers.png'); I = double(I)/255;
[height,width,~] = size(I);
image = I;

noOfClasses = 5;

pDet = rand(noOfClasses,1);
pInv = rand(3,3,noOfClasses);
pMean = rand(noOfClasses,3);

% ----------------------The original way----------------------
disp('First do it the original way...')
tic
post(height,width,noOfClasses) = 0;

for count=1:height
      for count2=1:width
          %pixel vector x to be classified
          x=[image(count,count2,1);image(count,count2,2);image(count,count2,3)];
             %for each class
              for count3=1:noOfClasses
                detZ = pDet(count3);
                invZ = pInv(:,:,count3);
                y=(pMean(count3,:)');
                %calculate the likelihood
                post(count,count2,count3)= 1/sqrt((2*pi)^2*detZ) * exp(-(x(:,1)-y)'*invZ*(x(:,1)-y)/2);
              end
      end
end
originalway = toc

% ----------------------The fast way----------------------
disp('Now do it the fast way...')
RGB = reshape(I,[],3);
%[colorlist, ~, ind] = unique(RGB,'rows');
colorlist = RGB;

C = 1./sqrt((2*pi)^2*pDet);

ncol = size(colorlist,1);
tic
post2(height,width,noOfClasses) = 0;

      for count3=1:noOfClasses
          invZ = pInv(:,:,count3);
          y=(pMean(count3,:)');
          colorlistY = bsxfun(@minus,colorlist,y');
          post2(:,:,count3) = reshape(C(count3) * exp(-sum(colorlistY*invZ.*colorlistY,2)/2) , height, width);
      end
  fasterway = toc
  ARETHEYTHESAME = isequal(post,post2)

[Teja Muppirala]

Yikes... please don't take after my sloppy code. This:

post(height,width,noOfClasses) = 0;

is really a lot safer when written as:

post = zeros(height,width,noOfClasses);

[John]

Dear Teja,

Sorry for the late reply, I only noticed your answer today when I came back to this problem. Thank-you very much for your kind response, it is indeed much faster :-)

John

Answer 2

[Jan]

Move as many operations as possible out of the loops:

C1 = 1 ./ sqrt((2*pi)^2 * pDet);
pMeanT = transpose(pMean);
for count=1:height
  for count2=1:width
     x = reshape(image(count, count2, :), 3, 1);
     for count3=1:noOfClasses
       invZ = pInv(:,:,count3);
       y = pMeanT(:, count3);
       C2 = x - y;
       post = C1(count3) * exp(-C2' * invZ * C2 * 0.5);

I do not expect a dramatic acceleration, but this is a very general method which works in all programming languages.

[John]

Thanks for this Jan, regards, John