Kinect Augmented Reality – Part 3

Following on from Kinect Augmented Reality – Part 2 we’re now looking at drawing contours using our point cloud data.

Achieving this is rather difficult, and after lots of researching an algorithm kept popping up – the Marching Squares Algorithm.

Marching Squares is a algorithm for generating contour lines using a 2d array.

I wanted to give this a go in-browser using JavaScript but this may change in the future, and may be done in Python. For this to work we need to convert our point cloud data into a 2d array format that our marching squares algorithm can understand, as in a 2d array which is an array of arrays which represent a column that contains many row arrays. This is like the grid shown below

The value of each child item in the array is the depth at which the particle is. Once we have the data in this format, we are then able to run marching squares over it which returns arrays of coordinates representing closed polygons, thus our contours.

Once we have the contour shape data, we’re then able to draw shapes within three.js. Here is a screenshot directly after we’ve run marching squares for the first time. Note that you can see the outline of our sandbox, however it currently does not have sand in it and we’re using some objects (boxes etc) to create the contours.

As you can see, this is doing the right thing, but we’re getting lots of interference and dead spots from the Kinect (this is a well known issue) that we need to filter out, so we went and researched signal processing. We looked over different techniques,  and finally decided on a Python library called SciPy. The library has many algorithms, and the one we were interested in was the Median Filter. Simply by passing our data through this, we were able to achieve a much better contour representation of our sandbox.

Our contours in the middle are much smoother now, with no interference. We now need to be able to define our sandbox area in three.js, as it is picking up a lot of unwanted points around the edge of the sandbox.

Join me in part 4 where we start calibrating our sandbox and colouring our contours!