To analyse or not to analyse conected components

So to figure out the location of independent blobs one has to first figure out which pixels belong to what blob.  This is usually reffered to as connected component analysis/labeling.  The standard algorithm do do this starts in one corner of an image and then looks at the next pixel until it reaches opposite corner (connected component labeling)This doesn’t really work on the gpu, because everything happens in parallel.

I have been playing around with a couple ideas of how to cope with this.  Some of which use alternative algorithm to label the individual components  Here is a screenshot of a really naive approach that actually works better than i thought it would.  It marks the horizontal and vertical middle pixel red and green respectively for each row/column.  The center point becomes yellow.  The idea is that if i have an image with just single pixels representing the center of each blob I can find them quickly on the gpu by processing e.g. each 10×10 block by a separate geometry shader thread.  Then I could easily produce variable length output to store the coordinates and only transfer back to the cpu what is really needed.

I’m pretty convinced that this approach is too naiive to work well, but it kind of looked cool.  We’ll see what else we can come up with.

Cross Platform & Shader Coding

I haven’t installed windows for quite while and I was quite suprised by how long it took me to set everything up.  For one the windows XP installer takes ages compared to e.g. the latest ubuntu installer.  And getting everything set up for development took a lot longer than I am used to on Linux as well (you just kind of fall in love with apt after a while i suppose; it makes installing things so easy and fast).

Anyways, enough complaining. I just submitted some more changes to svn and so the project now compiles on Windows as well.

Now on to some more shader programming.  I started working on shaders for dilating and eroding the image.  I can use those for a highpass filter, but I have also been trying to write a shader that converts the image into the frequency domain (ala Fourier transform) that would make a highpass filter really easy and also allows one to combine certain filters more efficiently.

Next week I also get to meet with a graphics prof at my university.  I was talking to him about the project and he is going to help me work out the best (we can come up with) way of detecting and tracking the blobs.  The usual approaches to connected component analysis dont work well on the GPU, as they rely sequential scans of the image array and information from pixels visited before the current one.  On the GPU the computations are perfomed in parallel instead…but I’m pretty sure we can work some GPU magic with the geometry shaders that are supported by newer graphics cards

first svn commit

I uploaded some code to svn.  Google code project is here: http://code.google.com/p/gputracker

I’ll add some documentation in the days to come. I need to also make the user interface for filter chain configuration better and get the blob detection and tracking working.

Hello World

Hello World. the default WordPress title is quite fitting. This blog is meant to document my google summer of code project. I am working on implementing gpu accelerated blob tracking for nuigroup. NUIgroup is awesome community made up from people around the world sharing a common interest in natural user interfaces and next generation human computer interaction.

I have started coding and am working on adding camera support for a couple of different camera types. USB and ieee1394 work great on windows through DSLib and the CMU driver. I have gotten firewire support to work on OSX and Linux as well through libdc1394 but I still have quite some work to do with the cameras. I will see how far I can get this weekend. I am getting eager to write some glsl code for the image processing.

I will upload some code to svn after playing a bit more with the various camera interfaces so that people can actually use it with the hardware they have.