The Engineer Speaks

Ok, so we were thinking about how to make video clips look like animation. Interesting problem no? After some googling, we found this site, but it wasn't very impressive. More impressive was the movie, Waking Life, which looks like an interesting movie in its own right, which had really interesting video to animation conversions. Even Microsoft's got it's own take on the problem.

So what characterises a animation-like video from a real-life video? We reduced it to two properties - homogeneous colour and distinct outlines. To achieve homogeneous colour, I toyed with the idea of some region growing algorithm, taking a moving average of each growing region and classifying regions as separate when the averages are far apart. But in the end, I hit on k-means clustering, which should work fairly nicely as the colours are quantised to the k colours. And hooray, I have actually implemented k-means clustering as part of a computational biology class (pardon the bad indenting, some how it dies when i cut and paste it in)!

function [clusterVector, clusters] = KMeansCluster(dataset, k, centers)
% KMEANSCLUSTER performs the K-means clustering algorithm
% [CLUSTERVECTOR, CLUSTERS] = KMEANSCLUSTER(DATASET, K, CENTERS) returns the cluster that each protein
% in the DATASET belongs to in CLUSTERVECTOR, as well as the data representing the clusters in CLUSTERS.
% K indicates the number of clusters and CENTERS specifies the initial cluster centers. If CENTERS is
% [], random centers are chosen within the ranges of each dimension of the data vectors.
% Maximum number of iterations
MAX_ITERATION = 50;
[row, col] = size(dataset);
%Generate random centers
if length(centers) == 0
centers = zeros(k, col);
for i = 1:k
for j = 1:col
centers(i,j) = rand*(max(dataset(:,j))-min(dataset(:,j)))+min(dataset(:,j));
end;
end;
end;
clusters = centers;
clusterVector = zeros(row,1);
%Iteration for convergence
for i = 1:MAX_ITERATION
oldClusterVector = clusterVector;
for j = 1:row
distVector = zeros(k,2);
for m = 1:k
distVector(m,1) = norm(dataset(j,:)-clusters(m,:));
distVector(m,2) = m;
end;
%Assign data point to nearest cluster
distVector = sortrows(distVector,[1]);
clusterVector(j) = distVector(1,2);
end;
clusters = zeros(k,col);
clustercount = zeros(k,1);
for j = 1:row
clusters(clusterVector(j),:) = clusters(clusterVector(j),:)+dataset(j,:);
clustercount(clusterVector(j)) = clustercount(clusterVector(j))+1;
end;
for j = 1:k
if clustercount(j) ~= 0
%Find average of clustered vectors to find new center
clusters(j,:) = clusters(j,:)./clustercount(j);
else
%Randomly pick new center if cluster has no members
for m = 1:col
clusters(j,m) = rand*(max(dataset(:,m))-min(dataset(:,m)))+min(dataset(:,m));
end;
end;
end;
%Break if no change
if norm(clusterVector-oldClusterVector) == zeros(row,1)
break;
end;
end;

However, that doesn't solve the problem of 'holes', or small regions of pixels with different k-clustered colours from their surrounding regions. But some dilation erosion should fix that.

Achieving distinct outlines I think will be a lot more tricky, since it involves image segmentation and edge detection. But hopefully with the colours homogenised from the previous step, edge detection should be a lot easier.

But alas, I've lost my copy of Matlab, so no trying this out till tomorrow.

So how am I to be a policy wonk like this?