function [D] = edit_distance(reference_pattern,test_pattern)
% EDIT_DISTANCE - computes the edit distance using dynamic programming
% 
% we place the reference_pattern on the x or I axis
% we place the test_pattern      on the y or J axis
% 
% Written by:
% -- 
% John L. Weatherwax                2005-08-04
% 
% email: wax@alum.mit.edu
% 
% Please send comments and especially bug reports to the
% above email address.
% 
%-----

I = length(reference_pattern);
J = length(test_pattern);

D = zeros(I+1,J+1);
D(1,1) = 0;
D(:,1) = 0:I;
D(1,:) = 0:J;
for ii=2:I+1,
  for jj=2:J+1,
    c1 = D(ii-1,jj-1) + transition_cost( ii,jj, ii-1,jj-1, reference_pattern, test_pattern );
    c2 = D(ii-1,jj) + 1;
    c3 = D(ii,jj-1) + 1;
    D(ii,jj) = min( [c1,c2,c3] );
  end
end