% FDMS.m implements a fast version of the dynamic mean shift discussed in the paper
% <Accelerated convergence using dynamic mean shift>, by grouping the data
% into clusters and treating the clusters instead of the individual sample set.
% Each cluster is represented by the cluster center and the number of points
% in that cluster.
% Input:
% data: n-by-dim
% m: number of clusters used for approximating the whole data. The larger,
% the more accurate but the slower the method.
% H: the bandwidth used in the gaussian kernel exp(-||x||^2/H)
% threshold: stopping criteria
% Output:
% converged_data: converged data after the dynamic mean shift iteration (n-by-dim).
function converged_data = FDMS(data, m, H, threshold);
[n,dim] = size(data);
[idx, center] = kmeans(data, m,'MaxIter',10);
P = zeros(1,m);
for i = 1:m;
P(i) = length(find(idx == i));
end;
for t = 1:1e3;
err = 0;
for i = 1:m;
x0 = zeros(1, dim);
c0 = 0;
c = 0;
for j = 1:m;
v = center(j,:) - center(i,:);
c0 = exp(-v * v'/H);
x0 = x0 + c0 * P(j) * center(j,:);
c = c + c0 * P(j);
end;
new_center(i,:) = x0/c;
err = err + norm(new_center(i,:) - center(i,:));
end;
err
if err <= threshold;
break;
end;
center = new_center;
end;
converged_data = zeros(n,dim);
for i = 1:n;
converged_data(i,:) = center(idx(i),:);
end;