Give your gizmo the gift of sight
I've been experimenting with using an Arduino-powered vision system to detect and locate point light sources in an environment. The hardware setup is an Arduino Duemilanove, a Centeye Stonyman image sensor chip, and a printed pinhole. The Arduino acquires a 16x16 window of pixels centered underneath the pinhole, which covers a good part of the hemisphere field of view in front of the sensor. (This setup is part of a new ArduEye system that will be released soon...)
The algorithm determines that a pixel is a point light source if the four following conditions are met: First, the pixel must be brighter than it's eight neighbors. Second, the pixel's intensity must be greater than an "intensity threshold". Third, the pixel must be brighter, by a "convexity threshold", than the average of it's upper and lower neighbors. Fourth, the pixel must similarly be brighter, by the same threshold, than the average of it's left and right neighbors. The algorithm detects up to ten points of light. The Arduino script then dumps the detected light locations to the Arduino serial monitor.
A 16x16 resolution may not seem like much when spread out over a wide field of view. So to boost accuracy we use a well-known "hyperacuity" technique to refine the pixel position estimate to a precision of about a tenth of a pixel. The picture below shows the technique: If a point of light exists at a pixel, the algorithm constructs a curve using that pixel's intensity and the left and right intensities, then interpolates using a second order Lagrange polynomial, and computes the maxima of that polynomial. This gives us "h", a subpixel refinement value that we then add to the pixel's whole-valued horizontal position. The algorithm then does something similar to refine the vertical position using the intensities above and below the pixel in question. (Those of you who have studied SIFT feature descriptors should recognize this technique.)
The algorithm takes about 30 milliseconds to acquire a 16x16 image and another 2 or 3 milliseconds to locate the lights.
The first video shows detection of a single point light source, both with and without hyperacuity position refinement. When I add a flashlight, a second point is detected. The second video shows detection of three lights (dining room pendant lamps) including when they are dimmed way down.
The ability to detect and ultimately track point light sources would be useful for some robotic hacks- A light source could serve as a landmark or a destination. Another possibility is for LEDs to be mounted on different robots, to allow the robots to see and maybe track (and pursue?) each other.
SOURCE CODE AND PCB FILES:
The main Arduino sketch file can be found here: LightTracker_v1.zip
You will still need library files to run it. I've put these, as well as support documentation and Eagle files for the PCBs, in the downloads section of a Google Code project file, located here: http://code.google.com/p/ardueye-rocket-libraries/downloads/list