Monthly Archive for March, 2008

Configuration

Published
by
Ben
on March 28, 2008 2:00 pm
in code and multitouch
. 1 Comment

configwindowcap.png

Just a quick ( are these ever quick, i am such a rambler) post about configuration of the surface. This is the super rough config screen for my system so far. Not much to it really. The six values on the upper left are the values that govern how the tracker picks up blobs. The ROI stuff defines the white rectangle that is where I am looking for blobs.

Max and Min Diff are the threshold values for ‘goodness’ in a pixel.  (ie where it is darkest, a pixel only needs to be 7 more than the background to be a blob, but at the lightest areas a pixel needs to be 67 more than the background values.)

Pixel Min and Max are filters for finished blobs, if it has less than 7 pixels, then it is ignored as noise. If it is too big it is also ignored.  The depth limit is just a stopgap on the recursive function.  if you set a sheet of paper or something on the surface, the recursive algo would go too deep and the app would hang.  this keeps the recursion stack to a decent level. and really you shouldn’t have to go too deep.  The depth limit and pixel max is really there to keep you from crashing horribly if you set your thresholds too low and everything becomes a blob.  These will probably go away at some point when I can add some more smarts to the blob filter, but for now they work well as safety valves.

The blob distance threshold is how much distance can be between two blobs and they will still be merged into one.  this works well for making a small cluster of blobs into a bigger blob. Sometimes the smaller finger blobs will break up into a cluster of blobs because of noise and bad illumination. This basically makes those small clusters into a single blob.

The stuff  in the lower section is how you set up the display area.  It lets you visually map the blob ROI rectangle onto the display.

configcap.png

(Above: the resultant display image)

I added the rotation because my super-duper projector mounting job with scrap plywood didnt really go in so square. So, I made the projection slightly bigger than the surface, then use the configure rectangle to line it all up so even tho my display is technically crooked, it renders square with the surface.

Now that I have this done, I need to make a basic app.  I am thinking the standard image browser app where you can rotate and move and resize the images with simple gestures.  If I can get the code for what I have so far cleaned up enough i will post it this weekend.  However i just got the call that we are in night shoots all next week, so there will be little time to work on it until next weekend if i dont get it done in the next few days.

Blob Tracking Algo update

Published
by
Ben
on March 28, 2008 1:38 pm
in code and multitouch
. 0 Comments

I have been giving a great deal of thought (and coding and testing) to the blob tracking algorithm i am using. The first hurdle is simple finding blobs in a bitmap. There are dozens of ways to do this, some more complicated than others. The one I finally settled on is a fairly common (i think) algo that is a combination of iterative pixel-by-pixel scanning and recursive similar-color-pixel-grouping.

It basically goes like this:
starting at pixel 0,0 start scanning across the bitmap, going down a row when you get to the end (simple raster) for every pixel check first to see if it is marked. (you will have to have some data structure to keep your marked flags, I am using another bitmap that i can then display to see what is going on) then check to see if it is ‘good’ (ie is blob-worthy. more on goodness later) if it is ‘good’ then hand it off to a recursive method that checks all the neighbors (ie the 8 surrounding pixels) to see if they are also ‘good’ and adding those pixels to a blob (more on blobs later). any non-good pixels it finds, mark them so the raster can ignore them, as well as marking the good ones so the raster will ignore them.
This should give you a nice group of blobs in fairly short order. After this step, I filter the blobs by size (if it is too small, i presume it is a false positive) I also check for blob intersections within a certain distance (ie two smaller blobs might not technically intersect, but if they are close enough together they are probably part of a small cluster that is just a poorly-lit blob, so i merge those based on a configurable minimum distance between them.

dsc_2061.jpg

(Above: the first time i got the blobtracker and the display all coordinated, hand-modeled by my lovely girlfriend, Leonie. Doesnt have much to do with the blobtrackign algo, i just wanted to post it)

Of course, the real meat of the algo above is what constitutes ‘goodness’ in a pixel? In order to look at the way i have done it, i need to lay out some background thinking that I have done: First, as a general rule, i want to make any algorithm as simple as possible. This is nice for so many reasons, but the big ones are maintainability (ie figuring out what it does in six months when I come back to it) and speed, simpler is (almost) always faster. As for this specific problem, I wanted to avoid using any type of image filter. Why? because if I can pick out the blobs with my own eyes, then there is no need to do any complicated filtering to make them ‘more findable’ by the machine. This does not hold true for all machine vision goals, but for this one i think it does. (that and I spend a great deal of time using quartz composer to generate a filtered image that performed better than just a ‘raw’ image and nothing made it work the cycles to do)

photo-59.jpg
(Above: a raw image from the IR camera under the surface)

With that in mind, i set out to make the simplest ‘goodness’ test that I could.

My original goodness test was basically this: Take the source pixel (ie what the cam is seeing right now) and subtract the background pixel in the same position. If the resulting difference pixel is above a configurable threshold value, then it is good.
This actually works quite well. One thing i really really like about it is that is is very very simple, and very very fast. (computationally) This is basically a difference matte with a threshold applied across the image.
The problem that was plaguing me (and it seems many other DI surface builders) is that this method works really well if you have a really nice even diffused IR lighting (thus making all your blobs nicely the same intensity). However, it would seem that in practice this is never the case (or at least it sure ins’t in my case). However, after spending two weeks tweaking my lighting to make it cover as much as possible, it still sucked in the corners and I am too lazy to go buy more IR illuminators.
Now, being a software guy, i am surprised it took me that long to decide i should be able to fix it in software (stupid hardware, always needing fixing :-). So i came up with a slightly (tho only very) more complicated scheme for blobby goodness.

The idea is this: take your pixel, subtract the background, and then instead of applying a constant threshold across the entire image, use a luminance map to hint the threshold into a value appropriate to the illumination level in that area. I had some ideas as to where to generate the lumi-map, first off being getting something that had a roughly similar IR reflectance as my fingers and cover the whole surface, and take an image. This would give a nice reference image. However, trying to keep things simple, i decided to start with just the background image as a rough lumi-map (since I am illuminating the diffuser (ie tracing paper) and that should give me a nice relative level of illumination.

Now the algorithm for goodness goes something like this: I have a configurable maximum threshold and minimum threshold. The max to be used at the brightest area and the min at the darkest (and smoothly transition for the inbetween areas. So when you take a background shot, quickly analyze it for max and minumum values. Those map to the max and min thresholds. for each pixel, find the difference between source and background, then compare that to the threshold the maps to that background color.

This seems to be 100% better than the straight difference matte + threshold. Until i find something better, I will be sticking with it.

Multitouch code testing

Published
by
Ben
on March 26, 2008 10:39 am
in code and multitouch
. 0 Comments

So, a bit more about the software the i am writing to run the multi-touch table that I am building (have kinda built a prototype of).

I just spent a few days getting the ‘SG Settings’ to work properly. I have been writing Cocoa for too long now and I am woefully unfamiliar with the Carbon stuff (ie all the old quicktime calls). I thought about using QTCapture, but it doesnt support IIDC settings like changeing the exposure from the code, so I am stuck (for now) with the Sequence Grabber Carbon stuff. Which just means wading through tons of sample code and docs to figure out what i need. In any case, now I can set the various exposure/gain/etc for the camera and have it save and come back when i load the program next.

This is immensely good.

The biggest problem i was having previous to this minor breakthrough was just that the camera driver (or camera itself maybe) does the auto-exposure/auto-brightness thing. So, the more fingers you put down, the more the xposure/brightness would change (albeit slightly, but slightly enough to mess up my thresholding stuff). Doesn’t matter now, all fixed.

The next step is getting my configuration ’system’ all worked out and the interface made as well as getting a nice generic coordinate-conversion thing working nice (right now it is pretty rough and inelegant) so that the underside of the surface that the camera looks at maps properly to the top of the surface that the computer is generating. Right now it is mostly just hard-coded for this specific setup. I need to make it configurable. This week hopefully.

Also, i successfully ran it on my old G, and it performed the same as the macbookpro, so that is good. I still havent done any optimizing yet, so I am fairly happy that the performance is good even in this very early stage. (my first few attempts at region-growing blob detection algos were horribly processor intensive)

The Second Prototype

Published
by
Ben
on March 24, 2008 1:24 pm
in FTO xpost and multitouch
. 0 Comments

Having settled on DI instead of FTIR for the time being, I went ahead and built a bigger, but still fairly small prototype table that i could use to develop the software (as opposed to a full-size one, since i dont have that much room in my office. The full size will come later when I have the software working well, and have written a few apps for it).

So, here is the second prototype (sans camera, i haven’t mounted it in there yet, but it goes just in front of the mirror. I had it sitting on some books for the testing I have done up to this point, i took it out to take IR photos of single malt scotch for my previous post, and I forgot to put it back in for these, so you will have to use your imagination)

dsc_2055.jpg
The Table is only 640mm high, and fits under my desk. I may even put wheels on it to make it easier to move out of the way when I am not using it.

dsc_2058.jpg

The surface is just tracing paper, and the plexiglass is cut to fit one sheet exactly.

dsc_2057.jpg

The plexi is actually two layers of 3mm (since it was easily purchased form the local hardware store). I haven’t yet got around to buying a new sheet of 6mm or better. The double layer works fine for DI, i dont think it would work very well for FTIR tho. If you press hard, there is still a bit of bowing in the center, I dont really recommend the double layer, but it works if you dont have a single sheet of the right thickness.

dsc_2050.jpg

dsc_2049.jpg

The two IR illuminators, which are 840nm, are just in the right range for the fire-i camera. They are 12v, powered by my 5/12v experimenting supply. Eventually i will just by a 12V wall wart for them. Altho they have a pretty purple color here, (thanks to my digital camera) to the naked eye you can only see a very dim red glow when they are on (since they are so close to the visible spectrum at 840nm). I have put some of the tracing paper into the glass covers to make them more diffuse, I also taped over the photosensitive resistor so that they are always on (they were originally for nighttime illumination for CCTV cameras)

They are actually a bit close to the surface here, and they give a very spotlight-like coverage (even with the diffuser) which isnt exactly what you want. it makes the illumination very uneven, which causes the threshold filter to lose the blobs in the dark areas even though they are perfectly visible. This seems to be the big problem with the DI setup, nice even light coverage. I spent a great deal of time tweaking it before i came to the conclusion that i should be able to deal with the uneven coverage in software. Like a variable threshold.

My thought is that if i put something that has roughly the same IR reflectance and my fingers (the cardboard back of the tracing pad is pretty close) and use that to cover the whole surface, then i can take a snapshot of that and use that to analyze the coverage of the IR lights. Once i have a lighting brightness map, i can use that to scale the threshold values accordingly and hopefully be able to easily pick out the blobs i want even as they pass from light to dark. More on that later, once i have tried it out.

dsc_2053.jpg

The projector is a ViewSonic PJ556d (which has a latency of about 1/20th of a second according to my tests, which is a bit slower than i want, but still passable). You can also see my super-duper-pro-plywood-scrap projector mount and adjustable rotation mirror. As crappy as it looks, it works fairly well, I can move the mirror back and forth to adjust the image on the surface. The surface is not 4×3 (obviously) and at the distance I have right now, my projection is just wide enough to cover the whole surface (the whole exposed surface i should say, since there is a 43mm border all around from the wood i used.) but i have spill on the top and bottom, which i use the mirror adjustment to put where i want (generally so I can see the menu bar on top). The projector has a native rez of 1024×768, so that is also nice. It can go as high as 1280 × 1024 (or maybe even higher) but that seems silly, since it is just scaling the image, and looks terrible. I am sticking to 1024×768.

As for control, I am using my powerbook g4 12″ (not hooked up in the images), which also has a native rez of 1024×768, so i can easily run it in mirror mode when i am testing, or run as a second monitor so i can see all the config stuff on the powerbook and still get the ‘real’ image on the surface. I am actually doing all the development on a macbookpro hooked to a cinema display, which is why I am using the 12″ for the control. I cant give up the big display to use the macbook for testing :-) Plus this way I also wont rely to heavily on the speed of the macbookpro. If i cant get the software to run perfectly fast on the G4 i am doing something wrong. there is no reason that simply blob detection should take very much processor power. (more on how i am blob detecting in a later post)

Unibrain fire-i IR

Published
by
Ben
on March 24, 2008 12:40 pm
in FTO xpost and multitouch
. 2 Comments

After much waiting (like four days, they were actually very quick, but as i have mentioned, i am very impatient) I got the fire-i camera:

dsc_2046.jpg

There it is, with my 3-ply film-negative visible light filter professionally taped onto the 4.3/no IR lens.

Here are the obligatory IR shots:
First, here is the apple remote illuminating me making a silly face. Here is a hint tho: maybe dont use the apple remote when doing this kind of shot. iTunes went mad, and i found out if you hold down the play/pause button for too long, your computer will go to sleep.
photo-56.jpg

And here is the standard: ‘Hey IR makes liquids look clear! shot’, usually done with a cola of some sort. Shown here to also work with single malt scotch.

photo-57.jpg

Quick review: the unibrain fire-i is a pretty damn good camera. I highly recommend it for any of your fire-wire camera needs. One thing however, it is not autofocus. (which in this case, is a good thing) but you can see form the above images if you are just waving the thing around and not focusing it, then it can get a bit blurry. However, in the multitouch table it is fantastic. (and another problem i had with the iSight: autofocus. It wouldnt shut off! and since i had remove some of the optics, it could never find a good focus so it would constantly go from end to end of its focal length, which was quite annoying. You can turn that stuff off, but it is a giant pain in the ass. Just get the fire-i)

Multitouch recognition software

Published
by
Ben
on March 24, 2008 12:27 pm
in FTO xpost, code and multitouch
. 2 Comments

Ok, So I am a mac guy. Not a zealot mind you, but I develop software for the mac, it is what i do for a living. But, why reinvent the wheel? there is a great library for machine vision stuff already available: touchlib. I suggest if you are doing any multitouch stuff, to start there. . Also, if you are a mac person, you should check out the Mac Touchlib Install Tutorial at nuigroup.

This is where i started. however, step one (download and install darwinports) was taking too long (i am very impatient :-) so i started writing my own blob detector. By the time i got to step 4 I already had a working (albeit very very poorly) blob detector using my crummy modified iSight as the input source. (note: i didn’t really start from scratch. I had already done some firewire capture projects based around this excellent and easy to use framework: CocoaSequenceGrabber by Tim Omernick. So really all i did was take a quick background capture, subtract it from the source image, and then do a simple threshold to get my blobs, this took all of about 20 minutes. of course, that is the easy bit :-)

Anyhow, since I was already going down the path of doing it myself, i figured i might as well do it all the way, so I abandonded the touchlib and started my own Obj-C/Cocoa multi-touch project. (which i will post once it is in a form that I feel OK letting into the wild).

Here is a screengrab of a very very early version (let’s call it 0.01 beta :-)

picture-2.png

All it does right now is does some basic image processing to get the blobs in a nice findable state (ie monochrome, difference matte, threshold) then identifies them with a simple raster/recursive algorithm, and then build a blob event list based on how far they have moved, whether they are ‘new’ or whatever. (ie if they havent moved too far in one frame they are considered the same blob, otherwise they are new etc..)

I am currently working on a configuration program now that I have the basic blob detection working.

The FTIR Prototype

Published
by
Ben
on March 24, 2008 12:04 pm
in FTO xpost and multitouch
. 0 Comments

First off, I wanted to do an FTIR surface. I wanted to start small, make an experimental surface just for testing and such. My first surface only measured 280mm x 190mm.
dsc_2043.jpg

As far as a camera, I was being very very impatient, and since I had some old external iSight cameras laying around, i decided to use one of those. One of the more important parts of the camera setup is the visible light filter. According to many good sources gleaned from the helpful forums at nuigroup.com, one good cheap way to do a visible light filter is to find some old film negatives and use the black bits at the end of the roll where they have basically been processed with no light exposure (ie a full black frame, like taking a picture of the inside of your lens cap). The hardest part of this was finding some old film. I havent used a film camera for 10 years or more. Luckily, my lovely girlfriend is a bit less of a techno-nerd than I so she still had some old photo laying about and I managed to scavenge 3 whole 35mm frames of black goodness. I taped those to the front of the iSight and got ready to go!

Now, unfortunately, while the iSight CCD is in fact quite sensitive to IR, it does have an IR filter inside it’s optics. After doing some web searches to see if anyone had any experience removing the IR filter from an iSight i did run across a few people who said that there was one in there, but it was hard to get to (and had i read further i would have also noticed the advice that removing the IR optics bit resulted in an unusably short focal length, but I didnt) NOTE: if you have an external iSight, do NOT (i repeat: DO NOT) use it for FTIR or IR in general. you will be very disappointed.
I did however persevere and (since i have two of the externals and I am too lazy to sell them on eBay) went ahead and dissected my iSight. If for some reason you MUST use your iSight as an IR sensitive camera (don’t) then here is how you do it briefly: take the thing apart. It is pretty self-explanatory. Remove lots of tiny screws, pry those little tabs etc.. once you get the actual CCD (the little black cube on the little daughterboard) you need to take the screws off the bottom of that as well, and pull teh little cube apart. There is a tiny chunk of coated glass about 3mm on a side, and about 2mm thick, it has a slight red sheen, that is the IR filter, take it out. (if i havent made it clear that this will really screw up your focus, take note: this will screw up your focus (ie can only focus very very close to the camera)).. once you have removed that, you can re-assemble and you are ‘good to go’ (ie it will suck)

Ok, on to the lighting. Since the local Bunnings (hardware store in Melbourne, AU) only had plexiglass that is about 2 mils (and you really want something thicker than 5 for FTIR) I had to switch gears mid-prototype and go with a Diffused Illumination scheme.

Here is a very early shot of the small surface with two IR illuminators and the modified iSight with film-negative filter:

photo-43.jpg

Luckily, the small surface was fairly close to the modified iSight, so it isn’t too out of focus. It was at this point that I ordered a unibrain fire-i OEM Board camera. I also got the 4.3mm lens without the IR coating and a wide lense (just to see). But while i waited on that, my extracraptacular prototype was ready for me to write some software…

multi-touch beginning

Published
by
Ben
on March 24, 2008 11:35 am
in FTO xpost and multitouch
. 0 Comments

So, awhile back i saw this cool thing by Jef Han. And it turns out the genius of it is that doing that isn’t actually that expensive or difficult, so much that there is a budding international community of DYI Multitouchers (sounds kinky, i know).

Since machine vision has always been a fascination of mine (i even started a visual gesture recognition project using the isight so you could do jedi-style gestures to control the computer, but i never finished it) I decided to give this multi-touch thing a go.

This was about a month ago. Now that the second prototype is nearly done (and kinda sorta working) i decided to blather on about it on here so that I maybe my experience will help others who are trying the same things.

blogg’n

Published
by
Ben
on March 24, 2008 11:03 am
in meta and multitouch
. 0 Comments

So, i guess to ‘have a blog’ means that you actually need to write some things on it from time to time. sigh.  I  guess I am just really a hermit at heart, and dont want to share anything with you people. But I guess I should put up all the work I have been doing on my multitouch thing.  More to come soon.