Fast sub-pixel laser dot detection

Question

I am using XNA to build a project where I can draw "graffiti" on my wall using an LCD projector and a monochrome camera that is filtered to see only hand held laser dot pointers. I want to use any number of laser pointers -- don't really care about differentiating them at this point.

The wall is 10' x 10', and the camera is only 640x480 so I'm attempting to use sub-pixel measurement using a spline curve as outlined here: tpub.com

The camera runs at 120fps (8-bit), so my question to you all is the fastest way to to find that subpixel laser dot center. Currently I'm using a brute force 2D search to find the brightest pixel on the image (0 - 254) before doing the spline interpolation. That method is not very fast and each frame takes longer to computer than they are coming in.

Edit: To clarify, in the end my camera data is represented by a 2D array of bytes indicating pixel brightness.

What I'd like to do is use an XNA shader to crunch the image for me. Is that practical? From what I understand, there really isn't a way to keep persistent variables in a Pixel Shader such as running totals, averages, etc.

But for arguments sake, let's say I found the brightest pixels using brute force, then stored them and their neighboring pixels for the spline curve into X number of vertices using texcoords. Is is practical then to use HLSL to compute a spline curve using texcoords?

I am also open to suggestions outside of my XNA box, be it DX10/DX11, maybe some sort of FPGA, etc. I just don't really have much experience with ways of crunching data in this way. I figure if they can do something like this on a Wii-Mote using 2 AA batteries than I'm probably going about this the wrong way.

Any ideas?

Answer 1

If by Brute-forcing you mean looking at every pixel independently, it is basically the only way of doing it. You will have to scan through all the images pixels, no matter what you want to do with the image. Althought you might not need to find the brightest pixels, you can filter the image by color (ex.: if your using a red laser). This is easily done using a HSV color coded image. If you are looking for some faster algorithms, try OpenCV. It's been optimized again and again for image treatment, and you can use it in C# via a wrapper:

[http://www.codeproject.com/KB/cs/Intel_OpenCV.aspx][1]

OpenCV can also help you easily find the point centers and track each points.

Is there a reason you are using a 120fps camera? you know the human eye can only see about 30fps right? I'm guessing it's to follow very fast laser movements... You might want to consider bringning it down, because real-time processing of 120fps will be very hard to acheive.

Answer 2

running through 640*480 bytes to find the highest byte should run within a ms. Even on slow processors. No need to take the route of shaders.

I would advice to optimize your loop. for instance: this is really slow (because it does a multiplication with every array lookup):

byte highest=0;
foundX=-1, foundY=-1;
for(y=0; y<480; y++)
{
    for(x=0; x<640; x++)
    {
        if(myBytes[x][y] > highest)
        {
            highest = myBytes[x][y];
            foundX = x;
            foundY = y;
        }
    }
}

this is much faster:

byte [] myBytes = new byte[640*480];
//fill it with your image

byte highest=0;
int found=-1, foundX=-1, foundY=-1;
int len = 640*480;
for(i=0; i<len; i++)
{
    if(myBytes[i] > highest)
    {
        highest = myBytes[i];
        found = i;
    }
}
if(found!=-1)
{
    foundX = i%640;
    foundY = i/640;
}

This is off the top of my head so sorry for errors ;^)

Answer 3

You're dealing with some pretty complex maths if you want sub-pixel accuracy. I think this paper is something to consider. Unfortunately, you'll have to pay to see it using that site. If you've got access to a suitable library, they may be able to get hold of it for you.

The link in the original post suggested doing 1000 spline calculations for each axis - it treated x and y independantly, which is OK for circular images but is a bit off if the image is a skewed ellipse. You could use the following to get a reasonable estimate:

x_c = sum (x_n.f(x_n)) / sum (f(x_n))

where x_c is the mean, x_n is the a point along the x-axis and f(x_n) is the value at the point x_n. So for this:

          *
       *  *
       *  *
       *  *
       *  *
       *  *
       *  *  *
    *  *  *  *
    *  *  *  *
 *  *  *  *  *  *
------------------
 2  3  4  5  6  7 

gives:

sum (x_n.f(x_n)) = 1 * 2 + 3 * 3 + 4 * 9 + 5 * 10 + 6 * 4 + 7 * 1

sum (f(x_n)) = 1 + 3 + 9 + 10 + 4 + 1

x_c = 128 / 28 = 4.57

and repeat for the y-axis.

Answer 4

Brute-force is the only real way, however your idea of using a shader is good - you'd be offloading the brute-force check from the CPU, which can only look at a small number of pixels simultaneously (roughly 1 per core), to the GPU, which likely has 100+ dumb cores (pipelines) that can simultaneously compare pixels (your algorithm may need to be modified a bit to work well with the 1 instruction-many cores arrangement of a GPU).

The biggest issue I see is whether or not you can move that data to the GPU fast enough.

Answer 5

Another optimization to consider: if you're drawing, then the current location of the pointer is probably close the last location of the pointer. Remember the last recorded position of the pointer between frames, and only scan a region close to that position... say a 1'x1' area. Only if the pointer isn't found in that area should you scan the whole surface.

Obviously, there will be a tradeoff between how quickly your program can scan, and how quickly you'll be able to move your mouse before the camera "loses" the pointer and has to go to the slow, full-image scan. A little experimentation will probably reveal the optimum value.

Cool project, by the way.

Answer 6

Put the camera slightly out of focus and bitblt against a neutral sample. You can quickly scan rows for non 0 values. Also if you are at 8 bits and pick up 4 bytes at a time you can process the image faster. As other pointed out you might reduce the frame rate. If you have less fidelity than the resulting image there isn't much point in the high scan rate.

(The slight out of focus camera will help get just the brightest points and reduce false positives if you have a busy surface... of course assuming you are not shooting a smooth/flat surface)