Efficient way of using ssim() function in Matlab for comparing image structures (or any other alternative)

I'm given the task of reordering a number of randomly placed video frames into the right order. I've managed to do this by using each frame as a reference once, and find the the two closest frames in terms of structure for that reference frame..presumably that these two closest frames would be the ones behind and after that frame in the video. After finding the two closest frames for each video frame, I would then compute a possible path.

My problem however is when it comes to performance, particularly when scoring. It's very inefficient unfortunately,and run time alone for 72 frames (320x240) is approx 80 seconds on just the scoring. I'm not too familiar with Matlab (or any similar language) but this is what I am doing for scoring right now:

for i =1: n_images,
current_image = Images{1,i};

%obtain score pairs image similarity
for j = 1:n_images,
    if i ~= j,
        scores(1,j) = ssim(Images{1,j}, current_image);                
    end
end      
[svalues, index] = sort(scores,'descend');
Closest(1,i) = index(1,1);
Closest(2,i) = index(1,2);
%Closest consists of a 2 x n_images matrix, where for each frame index, there are two 
%column values, which are the indexes of the closest frames. 
end

Could anyone give me some pointers for optimizations, or else suggestions for a better way of scoring?

Note, images are normalized and converted to grayscale. I've tried parrallel pool, and of course it does improve performance, however I need to create a standalone executable program.

Answer 1

[Patrick]

Never mind, here I'm going through all image pairs, twice (switched parameters), which is not needed.So it is possible to reduce the speed by n-1/2.

If you want efficiency over accuracy (which in my case, it is), finding the score from the correlation of histograms is the way to go.

It took me 55 seconds to process 72 frames with ssim(), while only 1.2 seconds with difference of histograms.