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:
Mahalanabois Distance / Calculating Online Gaussian on a video stream

Subject: Mahalanabois Distance / Calculating Online Gaussian on a video stream

From: Michael Davis

Date: 3 Apr, 2010 16:35:08

Message: 1 of 4

I'm using Online Gaussian for doing background extraction on a video stream (code fragment below). I have 2 questions about this:

1. I have a 3D matrix for the video frame (rows x cols x 3). I need to do a multipication on each pixel triplet in the matrix (r,g,b) [ probably better to change this to (y,u,v) but principle is the same ] to get the Mahalanobis distance at that pixel. Currently I'm looping across every pixel to do the calculation. Is that the most efficient approach?

2. The Mahalanobis distance calculation uses the inverse of the covariance matrix for the pixel ... but if the pixel value doesn't change, the covariance matrix is zero and so doesn't have an inverse. Does anyone know what is the correct thing to do in this case? I was thinking of just using the Euclidean distance for those pixels but I'm not sure if that's correct.

Thanks!

   % Read current frame
   F = aviread(Filename, f);

   % do BG extraction
   % This calculates the square of the Mahalanobis Distance, so the threshold should be
   % set as no. of variances rather than no. of standard deviations:

   D = F - BGM;

   % Calculate Mahalanobis distance for each point separately
   for row = 1:size(F,1)
      for col = 1:size(F,2)
         v = BGV(row,col,:)(:);
         v = inv(diag(v)); % doesn't work if v is zero!
         d = D(row,col,:)(:);
         MahalanobisDist(row,col,:) = d' * v * d;
      end
   end

   G = F .* (MahalanobisDist > Threshold);

   % Write the frame
   addframe(AVI,G);

Subject: Mahalanabois Distance / Calculating Online Gaussian on a video stream

From: Roger Stafford

Date: 3 Apr, 2010 20:32:05

Message: 2 of 4

"Michael Davis" <slithy@yahoo.com> wrote in message <hp7qns$gj4$1@fred.mathworks.com>...
> I'm using Online Gaussian for doing background extraction on a video stream (code fragment below). I have 2 questions about this:
>
> 1. I have a 3D matrix for the video frame (rows x cols x 3). I need to do a multipication on each pixel triplet in the matrix (r,g,b) [ probably better to change this to (y,u,v) but principle is the same ] to get the Mahalanobis distance at that pixel. Currently I'm looping across every pixel to do the calculation. Is that the most efficient approach?
>
> 2. The Mahalanobis distance calculation uses the inverse of the covariance matrix for the pixel ... but if the pixel value doesn't change, the covariance matrix is zero and so doesn't have an inverse. Does anyone know what is the correct thing to do in this case? I was thinking of just using the Euclidean distance for those pixels but I'm not sure if that's correct.
>
> Thanks!
>
> % Read current frame
> F = aviread(Filename, f);
>
> % do BG extraction
> % This calculates the square of the Mahalanobis Distance, so the threshold should be
> % set as no. of variances rather than no. of standard deviations:
>
> D = F - BGM;
>
> % Calculate Mahalanobis distance for each point separately
> for row = 1:size(F,1)
> for col = 1:size(F,2)
> v = BGV(row,col,:)(:);
> v = inv(diag(v)); % doesn't work if v is zero!
> d = D(row,col,:)(:);
> MahalanobisDist(row,col,:) = d' * v * d;
> end
> end
>
> G = F .* (MahalanobisDist > Threshold);
>
> % Write the frame
> addframe(AVI,G);

  I am puzzled by one aspect of your code, Michael. When you write

 v = inv(diag(v));

you are ignoring any cross correlation that might be present between the three colors this way. You ought to be dealing with a complete 3 x 3 color covariance matrix if you are doing true mahalanobis distance computation.

  If c is the full 3 x 3 covariance matrix, you can avoid finding its full inverse by writing the equivalent d'/c*d instead of d'*inv(c)*d.

  For a pixel that has remained strictly constant in each color in the past with consequent zero covariances, calculating mahalanobis distance becomes meaningless. Any slight change would then compute as an infinite distance. That is inherent in the very definition of that concept. Your answer either has to be 'inf' or you must modify to some extent your definition of the distance you are computing. It is analogous to asking for the percentage increase in price of an item that was originally free.

  As to the efficiency of your pixel-by-pixel computation, I suspect your nested for-loops are about as efficient as you are going to get with matlab. If I understand what you are doing correctly, the computation at each pixel is entirely dependent on the past history at that particular pixel only and unrelated to that of any other pixel. Because of the complicated nature of the mahalanobis computation, there would probably be little gained by trying vectorize such an "online" computation.

Roger Stafford

Subject: Mahalanabois Distance / Calculating Online Gaussian on a video stream

From: Michael Davis

Date: 3 Apr, 2010 22:48:21

Message: 3 of 4

Hi Roger,

Thanks for your comments, they were very helpful:

> If I understand what you are doing correctly, the computation at each pixel is entirely dependent on the past
> history at that particular pixel only and unrelated to that of any other pixel.

That is correct. I was afraid that it wasn't going to be possible to run it more efficiently, as it takes quite a long time to run on my PC ...

> I am puzzled by one aspect of your code, Michael. When you write
> v = inv(diag(v));
> you are ignoring any cross correlation that might be present between the three colors this way.
> You ought to be dealing with a complete 3 x 3 color covariance matrix if you are doing true mahalanobis
> distance computation.

Thanks for pointing that out. I have written a new function to update the model, which now allows me to store the full 3x3 covariance matrix rather than just the variances for each colour (see below). So now I'll update the rest of the program to use the full covariance matrix as you suggest (and leave it to run overnight ...)

Michael

function [ M V ] = update_model(oldM, oldV, F, n)
% Parameters:
% oldM - current model: means
% oldV - current model: variances
% F - new frame (N x M x 3)
% n - no. of frames used to learn the Gaussian pdf
%
% Return values:
% M - new model: means (N x M x 3)
% V - new model: variances (N x M x 3 x 3)
%
% For each pixel in F (3 values), we calculate the mean and the 3x3 covariance
% matrix. These are used to update the old models and the updated models are
% returned as M and V

[ rows cols colour ] = size(F);

% alpha is the learning rate
alpha_t = 1 / n;
alpha_t1 = 1 - alpha_t;

% Update means
M = (alpha_t1 .* oldM) + (alpha_t .* F);

% Update variances
mF = F - M;
for r = 1:rows
   for c = 1:cols
      pixel = mF(r,c,:)(:);
      new_covar = pixel * pixel'; % 3 x 3 covariance matrix
      old_covar = reshape(oldV(r,c,:,:),[ 3 3 ]);
      V(r,c,:,:) = (alpha_t1 .* old_covar) + (alpha_t .* new_covar);
   end
end

end

Subject: Mahalanabois Distance / Calculating Online Gaussian on a video stream

From: Michael Davis

Date: 7 Apr, 2010 12:51:09

Message: 4 of 4

Dear Roger,

I did some more research and I managed to find out the following:

1. As you pointed out, my original approach, taking diag(v) does not consider the correlations between colours. After some experimentation, I have concluded that even so, it is still a practical approach. Making the assumption that the colours are independent and have the same variance is not completely accurate, but avoids a costly matrix inversion. On my test videos, I could not discern a difference between using diag(v) and using the full covariance matrix, but the covariance matrix code took many hours longer to run.

2. If the covariance matrix is zero, it is possible to threshold on d directly rather than calculating the Mahalabois distance in that case.

Thanks again for your help!

Michael

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