BUILDING A CHEAP INDOOR LOCALIZATION SYSTEM
This is a cheap, fast, and (relatively) easy way to build a system that can localize the 3D position of a small, lightweight beacon in real time. Might be useful to people hacking around with mobile robots or active-badge systems: you could use it to track several objects simultaneously, with some constraints. We did some experiments with open-source and commercial indoor (non-GPS) localization systems that use RF signals (802.11 and ultra-wideband) and found that they suffered a lot in our building from reflections off of exposed metal ductwork and walls. The blips on our screen kept jumping around within a normal room (~400 square feet), and the refresh rate (~10 Hz) wasn't quite fluid enough. So we built our own.
HARDWARE: IR SENSORS (CAMS) AND BEACONS (LEDS)
There's a MAKE project that talks about hacking a "night vision" CVS cam. Most CCDs (in webcams) are sensitive to near-infrared light (between 700-900nm). It's just that they come with filters to block it; so if you remove the IR-blocking filters, and add a visible-block filter (like exposed color camera film), you can see some sources of IR light. That principle is the core of this system.
Putting two such "IR cams" together gives you enough information to do basic triangulation on a bright IR beacon. You need line-of-sight, but in practice, we've found that most RF systems do too. On the plus side, there's little need for fancy Bayesian inference, since the confidence of the angular measurements coming from such a cam is very*high (compared to, say, RF localization). (Multiple target tracking's another matter--more on that later.) But how well would this work indoors? We ordered a couple of FireWire webcams from The 1394 Store and some replacement lenses*without* IR filters; and a dozen or so different IR LEDs from Digi-Key; and tried it out. We could almost see a single IR LED across the room (~20 ft) with this basic setup, but we figured we could affordably boost performance with a better filter, a better IR source, and some rudimentary background subtraction.
A $5 polyester filter was marginally better than the exposed film, but we finally gave in and bought a $50 narrow-bandpass filter for each camera: 880 nm peak, which matched our highest-spread LEDs (880 nm) perfectly. This brought the cost of our black-and-white camera+filter setups to about $180 each. Cost of the IR beacons and 3V coin-cell batteries is negligible (a few bucks apiece). Using groups of 3 LEDs, and sanding the LEDs to give better diffusion, helped with seeing the beacon(s) from odd angles.
SOFTWARE: PROCESSING AND QT/OPENGL/V3GA LIBRARIES
Processing (www.processing.org) comes with libraries to handle QuickTime and OpenGL, which gave us a single platform to build all the way from the FireWire camera feeds to a visible model of the system working in real-time. Plus, a fellow named v3ga's published an open-source blob-detection library, which we used to derive XY coords in camera space from the (background-subtracted) IR feeds.
Deriving angles from the on-CCD (x,y) coordinates is a matter of knowing some trig and your camera positions and orientations. Luckily, our office floor has carpet tiles exactly 0.5m wide :-) so that made the measurements and calibration a little easier. (Hint: centering the cams on a known 'origin' is an easy way to figure out their pitch and yaw, once you know their location.)
We built up a world model in Processing in several stages, allowing us to sanity check calculations of camera position/orientation, blob detection, and angular derivations. There's a bunch of Java classes involved that we hope to publish soon. Hopefully this outline so far is, however, useful.
PERFORMANCE AND COST
The finished system runs in real-time on a G4 1.8Ghz. Sensors are about $180 apiece (we used four, but you can get away with two or three depending on your space and intended usage). Cabling is about $100 for four cameras. Compare that to a commercial UWB RF system which can cost up to $10,000 for about the same amount of spatial coverage. Plus ours runs at 30Hz (vs 10Hz) and has much better accuracy and precision (you can see cm-level movements accurately, if you're close enough to the cams).
ADDENDUM: MULTIPLE TARGET TRACKING (MTT)
It turns out that the hard parts of the problem are now: (a) tracking a beacon from frame to frame; and (b) linking a beacon to known ID. We last tried using particle filters (a known AI technique) and broadcasting binary IDs using repetition codes. Our conclusion is that transport layers don't get enough credit these days, and that there really is something to the whole MTT problem, so, good luck to everyone working on that! There are other edge cases: when there are multiple beacons close together, it's tough to differentiate them; and when the two cameras triangulating a beacon are nearly aimed at each other, you don't get much precision.