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

Question

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?

Edit: Images are normalized and converted to grayscale

Edit #2: I've tried using threads by adding parfor in the scoring loop, which improved performance by around 50%, however the problem is that I need to create an executable, and i'm not sure I'd achieve the same performance..

Answer 1

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 one possible way.

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