function [xhat_data,Smat]=dd2m(kalmfilex,kalmfiley,xbar,P0,q,r,u,y,timeidx,optpar)
% DD2M
%   This function implements the DD2-filter; a state estimator for nonlinear 
%   systems that is based on second-order polynomial approximations of the 
%   nonlinear mappings. The approximations are derived by using a 
%   multivariable extension of Stirling's interpolation formula. 
%   The function is implemented to handle multiple observation streams.
%   The model of the nonlinear system must be specified in the form:
%               x(k+1) = f[x(k),u(k),v(k)]
%               y1(k)  = g1[x(k),w1(k)]
%                        :
%               yn(k)  = gn[x(k),wn(k)]
%   where 'x' is the state vector, 'u' is a possible input, and 'v' and 'w'
%   are (white) noise sources.
%
% Call
%   [xhat,Smat]=dd2m(xfile,yfile,x0,P0,q,r,u,y,tidx,optpar) 
%
% Input
%   xfile   - File containing the state equations.
%   yfunc   - Cell structure specifying the names of the functions 
%             containing the output equations.
%   x0      - Initial state vector.
%   P0      - Initial covariance matrix (symmetric, nonnegative definite).
%   q       - Covariance matrices for process noise.
%   r       - Cell structure containing the measurement noise cov. matrices. 
%   u       - Input signal. Dimension is [samples x inputs].
%             Use [] if there are no inputs.
%   y       - Cell structure containing the output signals. 
%             Dimension of each stream is [observations x outputs-in-stream].
%   tidx    - Cell structure containing vector with time stamps (in samples) 
%             for the observations in y.
%   optpar  - Data structure containing optional parameters:
%             .vmean: Mean of process noise vector.
%             .wmean: Mean of measurement noise vector (cell structure).
%             .init : Initial parameters for 'xfile', 'yfile'
%                     (use an arbitrary format).
%
% Output
%   xhat    - State estimates. Dimension is [samples+1 x states].
%   Smat    - Matrix where each row contains elements of (the upper triangular
%             part of) the Cholesky factor of the covariance matrix. The 
%             dimension is [samples+1 x 0.5*states*(states+1)]. The individual
%             covariance matrices can later be extracted with SMAT2COV.
%
%  The user must write the two m-functions 'xfile' and 'yfile' containing the
%  state update and the output equation. The function containing the state
%  update should take three arguments:
%       function x=my_xfile(x,u,v)
%
%  while the function containing the output equation should take two
%  arguments:
%       function y=my_yfile(x,w)
%
%  In both cases, an initialization of constant parameters can be 
%  made using the parameter 'optpar.init'. This parameter is passed through
%  x if the functions are called with only one parameter.
%
%  Literature:
%     M. Norgaard, N.K. Poulsen, O. Ravn: Easy and Accurate State Estimation
%        for Nonlinear Systems," 14th IFAC World Conference
%        in Beijing, China, July 5-9, 1999, pp. 343-348.
%
% Written by: Magnus Norgaard, IMM/IAU, Technical University of Denmark
% LastEditDate: Jan. 15, 2000 

% >>>>>>>>>>>>>>>>>>>>>>>>>>>> INITIALIZATIONS <<<<<<<<<<<<<<<<<<<<<<<<<<<
h2    = 3;                 % Squared divided difference step
h     = sqrt(h2);          % Divided difference step
scal1 = 0.5/h;             % Scaling factor
scal2 = sqrt((h2-1)/(4*h2*h2)); % Another scaling factor
nx    = size(P0,1); % # of states
nv    = size(q,1);  % # of process noise sources
if isempty(xbar),          % Set to x0=0 if not specified 
  xbar = zeros(nx,1);
elseif length(xbar)~=nx,
  error('Dimension mismatch between x0 and P0');
end
streams    = length(y);
if ~(iscell(kalmfiley) & iscell(r) & iscell(timeidx) & iscell(y))
  error('"yfunc", "r", "tidx", and "y" must be cell structures');
elseif (streams~=length(r) | streams~=length(timeidx) | ...
                                 streams~=length(kalmfiley))
  error('"yfunc", "r", "tidx", and "y" must have same number of cells');
end
ny         = 0;                % Total number of observations
lastsample = 0;                % Number of sample containing last observation
idx1 = zeros(streams,1);       % Index to start of each stream in ybar
idx2 = zeros(streams,1);       % Index to end of each stream in ybar
for n=1:streams,               % Wrap information about observation stream 
  obs(n).yfunc = kalmfiley{n}; % into data structure
  obs(n).y     = y{n};
  obs(n).tidx  = timeidx{n};
  obs(n).ny    = size(obs(n).y,2);
  obs(n).nobs  = size(obs(n).y,1);
  [v,d]        = eig(r{n});
  obs(n).nw    = size(r{n},1);  
  obs(n).Sw    = real(v*sqrt(d));  % Cholesky factor of measurement noise cov.
  obs(n).Syw   = zeros(obs(n).ny,obs(n).nw);
  obs(n).Syx   = zeros(obs(n).ny,nx);
  obs(n).Syx2  = zeros(obs(n).ny,nx);
  obs(n).Syw2  = zeros(obs(n).ny,obs(n).nw);
  if (obs(n).nobs~=size(obs(n).tidx,1)),
    error('Dimension mismatch between y and tidx');
  end
  ny = ny + obs(n).ny;
  if obs(n).tidx(end)>lastsample,
     lastsample=obs(n).tidx(end);
  end
  idx1(n) = ny - obs(n).ny + 1;
  idx2(n) = ny;
end
if isempty(u),             % No inputs
  nu = 0; samples = lastsample; uk1 = [];
else
  [samples,nu] = size(u);  % # of samples and inputs
end

xhat_data = zeros(samples+1,nx); % Matrix for storing state estimates
Smat      = zeros(samples+1,0.5*nx*(nx+1)); % Matrix for storing cov. matrices
[I,J]     = find(triu(reshape(1:nx*nx,nx,nx))'); % Index to elem. in Sx
sidx      = sub2ind([nx nx],J,I); 
ybar      = zeros(ny,1);
y0        = zeros(ny,1);
yidx      = ones(streams,1);% Index into y-vectors 


% ----- Initialize state+output equations and linearization -----
if nargin<10,              % No optional parameters passed
   optpar = [];
end
if isfield(optpar,'init')  % Parameters for m-functions
   initpar = optpar.init;
else
   initpar = [];
end
if isfield(optpar,'vmean'),% Mean of process noise
   vmean = optpar.vmean;
else
   vmean = zeros(nv,1);
end
if isfield(optpar,'wmean'),% Mean of measurement noise
   if ~iscell(optpar.wmean),
      error('"optpar.wmean" must be a cell structure');
   elseif streams~=length(optpar.wmean),
      error('"optpar.wmean" has a wrong number of cells');
   end
   for n=1:streams,
      obs(n).wmean = optpar.wmean{n};
   end
else
   for n=1:streams,
      obs(n).wmean = zeros(obs(n).nw,1);
   end
end

feval(kalmfilex,initpar);       % Initialize state equation
for n=1:streams,
   feval(obs(n).yfunc,initpar); % Initialize output equations
end
counter = 0;               % Counts the progress of the filtering
waithandle=waitbar(0,'Filtering in progress');  % Initialize waitbar

[v,d] = eig(P0);           % Cholesky factor of initial state covariance
Sxbar = triag(real(v*sqrt(d)));
[v,d] = eig(q);            % Cholesky factor of process noise covariance
Sv    = real(v*sqrt(d));
Sxx   = zeros(nx,nx);
Sxv   = zeros(nx,nv);
Sxx2  = zeros(nx,nx);
Sxv2  = zeros(nx,nv);


% >>>>>>>>>>>>>>>>>>>>>>>>>>>>>> FILTERING <<<<<<<<<<<<<<<<<<<<<<<<<<<<<
for k=0:samples,

  % --- Measurement update (a posteriori update) ---
  for n=1:streams,
    y0(idx1(n):idx2(n)) = feval(obs(n).yfunc,xbar,obs(n).wmean);
    ybar(idx1(n):idx2(n)) = ((h2-nx-obs(n).nw)/h2)*y0(idx1(n):idx2(n));
    if (k<=obs(n).tidx(end) & obs(n).tidx(yidx(n))==k),
      for kx=1:nx,
        syp = feval(obs(n).yfunc,xbar+h*Sxbar(:,kx),obs(n).wmean);
        sym = feval(obs(n).yfunc,xbar-h*Sxbar(:,kx),obs(n).wmean);
        obs(n).Syx(:,kx) = scal1*(syp-sym);
	obs(n).Syx2(:,kx)= scal2*(syp+sym-2*y0(idx1(n):idx2(n)));
	ybar(idx1(n):idx2(n)) = ybar(idx1(n):idx2(n)) + (syp+sym)/(2*h2);    
      end
      for kw=1:obs(n).nw,
        swp = feval(obs(n).yfunc,xbar,obs(n).wmean+h*obs(n).Sw(:,kw));
        swm = feval(obs(n).yfunc,xbar,obs(n).wmean-h*obs(n).Sw(:,kw));
        obs(n).Syw(:,kw) = scal1*(swp-swm);
	obs(n).Syw2(:,kw)= scal2*(swp+swm-2*y0(idx1(n):idx2(n)));
	ybar(idx1(n):idx2(n)) = ybar(idx1(n):idx2(n)) + (swp+swm)/(2*h2);
      end
      
      % Cholesky factor of a'posteriori output estimation error covariance
      Sy   = triag([obs(n).Syx obs(n).Syw obs(n).Syx2 obs(n).Syw2]);

      % Kalman gain
      K    = (Sxbar*obs(n).Syx')/(Sy*Sy');
      
      % State estimate
      xbar = xbar + K*[obs(n).y(yidx(n),:)'-ybar(idx1(n):idx2(n))];
      
      % Cholesky factor of a'posteriori estimation error covariance
      Sxbar= triag([Sxbar-K*obs(n).Syx K*obs(n).Syw K*obs(n).Syx2 K*obs(n).Syw2]);

      yidx(n) = yidx(n) + 1;              % Update index in time vector
    end
  end
  xhat = xbar;
  Sx   = Sxbar;


  % --- Time update (a'priori update) of state and covariance ---
  if k<samples, 
    if nu>0 uk1 = u(k+1,:)'; end
    fxbar = feval(kalmfilex,xhat,uk1,vmean);
    xbar = ((h2-nx-nv)/h2)*fxbar;
    for kx=1:nx,
      sxp = feval(kalmfilex,xhat+h*Sx(:,kx),uk1,vmean);
      sxm = feval(kalmfilex,xhat-h*Sx(:,kx),uk1,vmean);
      Sxx(:,kx) = scal1*(sxp-sxm);
      Sxx2(:,kx)= scal2*(sxp+sxm-2*fxbar);
      xbar      = xbar + (sxp+sxm)/(2*h2);
    end
    for kv=1:nv,
      svp = feval(kalmfilex,xhat,uk1,vmean+h*Sv(:,kv));
      svm = feval(kalmfilex,xhat,uk1,vmean-h*Sv(:,kv));
      Sxv(:,kv) = scal1*(svp-svm);
      Sxv2(:,kv)= scal2*(svp+svm-2*fxbar);
      xbar      = xbar + (svp+svm)/(2*h2);
    end

    % Cholesky factor of a'priori estimation error covariance
    Sxbar = triag([Sxx Sxv Sxx2 Sxv2]);
  end


  % --- Store results ---
  xhat_data(k+1,:) = xhat';
  Smat(k+1,:)      = Sx(sidx)';
    
  % --- How much longer? ---
  if (counter+0.01<= k/samples),
     counter = k/samples;
     waitbar(k/samples,waithandle);
  end
end
close(waithandle);
