I got the BBTouch stuff up into the opentouch project on google code, so now you can check it out from there and you dont have to deal with a lame-ass tar file :-)
Monthly Archive for May, 2008
It is amazing how much faster you can make something when the tight loops get called a zillion times a second.
Anyhow, the blob detector i posted yesterday was the first clean, working version. But it hadnt really been optimized (never optimize before it’s time). So i went back in and looked at the tightest loop: specifically scanSrc in the detector. If you looked at the code you can see that it is written to be more programmer-friendly than fast. I tend to think that whenever you can afford to, programmer-friendliness is a good trade off for minor performance loss. However, in this case there were a few spots that needed to be changed.
The biggest (performance wise) change is the movement of the initial ‘goodness’ check into the loop proper. also instead of calling validLoopPixel, i just put the threshold check right there. It is generally considered bad coding to put the same code in two places. but this is a concession I am willing to make. Just taking out the call to validLoopPixel shaved off 20 or 30% of the time it was taking in that loop (let’s see. 640×480 pixels times 30 frames a second = 9216000 runs through that loop per second. anything you can do to shave off even the tiniest amount of time in that tight loop will yield great performance payback)
So, basically that one change made the biggest performance change, but i changed a few other things too: I added a regionOfInterest rectangle into the mix (to cut down on the number of times through the loop). and added a class method to the image processor to make the ROI rect in the image (ie the black pixel border that keeps the blob detection algorithm from going out of the ROI)
Thats about it as far as code: here is the tar:
Now, this whole tar with an incrementing value in the name is great and all, but it is not a good way to release code. Luckily for me, I had a long iChat with Pawel from the NUIGroup, and he is helping me get this stuff up onto the opentouch google code repository. While I have used SVN before, I havent used the google code repositories yet. I am going to attack that problem later today. I will be putting up the same code that is in BBTouch.2 initially, but then all the updates will go to the google repository.
I am back to work on the OSX Cocoa multi touch thing after being away doing some paying work for a few weeks. I am pretty happy with the prototype, as far as most of the concepts seemed to work OK. The only thing that was a bit iffy was my recursive blob finding algorithm. It works fairly well and fairly quickly, and it was fun to figure it out, but I am sure that it is very sub-optimal. So, i went to find out how the big boys do it. I grabbed the opentouch libs (thanks Pawel for all the great work!) and read the blob detector code.
Now i am a pretty code-savvy guy, i have been coding in C-like languages for a loong time now, but these pixel-level algorithms make my head spin without some direction as to what is really going on. So i had to look further afield. Somewhere in Pawels documentation I came across a reference to this paper:
A Linear-Time Component-Labeling Algorithm Using Contour Tracing Technique
Which is basically what the opentouch algo is based on. So I started from scratch (so i would know how it all worked in the end) and rewrote the algorithm described in the paper in Cocoa. (well, with a few little C bits, but mostly Cocoa). With a nice working blob finder and a nice working sequence grabber and a stack of other design ideas that are scattered through my prototype, i started a new project form scratch to make a proper application. So far what I have is a very stripped down blob detector.
All it does so far is grab images from any firewire cameras and analyze them for blobs based on a simple threshold and background subtraction. It hasnt really been optimized for speed yet, although it is pretty quick. I think the slowest part is just setting the image into the NSImageView. Those views were never really meant to show video, so if you bump the raw camera size up to 640×480 it can get a bit slow. But I will be doing quite a bit of optimization later on. (and for actual blob detection, you really dont need to see the video, and if you did, it would make more sense to use a different view)
There is a pre-process pipeline (sorta) so if you feel the need to add any filters or anything before it gets to the blob detection portion of the show, you can do that easily. The blob detector is currently written to handle NSImages, but it would be fairly trivial to change that for CIImages or CGImages. (or all three)
In any case, here is the code for anyone who wants it:
[UPDATE:] i managed to more than triple the performance of the blob detector last night. I will post more details and the newer code in a new blog post a bit later this morning once i have had some brekky and caffeine. :-)
Latest Comments
RSS