kalman filtering

[avriette]

Anyone written kalman filter algorithms before? I'm looking to pick objects out of a 640x480 camera doing 24fps. Kind of trying to figure out how much HP is required to do that.

[Sabre]

Depends on what it's written in (as I'm sure you know

Honestly, Matlab is ideal for it, but it's a little too much overhead for what I think you might be thinking of doing. You're best bet is to find a lib in C or ASM to do it.

[scheherazade]

In real time?
A lot... (a lot-lot)
If you want it to be realistically possible, you'll probably need your app multi threaded, simd, and written very carefully (i.e. row vs column major, etc).


Is the camera stationary or moving?

If it's stationary, you don't need the filter. You can just average N background frames, the errors go away and you get a crisp background image.
Then you just diff any further images against background, and drop anything under a certain delta.

That will bring out any foreground objects.

You might want to do it in HSV space to avoid issues with time of day, or judge the brightness and have a set of backgrounds for each brightness level.

Alternatively, you can differentiate the image pixel values, and then run a non maxima suppression filter on the image to get a good edge trace.
Then you can convolve a template against your edge map to try to find a best match.

Scale will be an issue, since there is no easy way to match any-scale objects.

You're actually talking about a non-solved problem.

Look into using convolutions, kernels, cross correlation, covariance.

I have slides on a lot of this crap if you need it.

Also, you might be trying to do something that's already implemented in OpenCV.
http://opencv.willowgarage.com/wiki/

Edit : This might be useful : http://en.wikipedia.org/wiki/Hough_transform
Demo : http://users.cs.cf.ac.uk/Paul.Rosin/CM0 ... hough.html
Basically an accumulator buffer is used to build up areas of high probability of an object being there.

-scheherazade

edit : No, never written a kalman filter... but just today I was talking about it as a possible method to assist in path prediction.

[ElZorro]

Yea, agree that depending on the conditions Kalman filtering may be overkill. There are tons of open source projects on the web for object detection in images and video, if you don't have to I wouldn't reinvent the wheel.

[scheherazade]

Whatever you choose to do, you can always improve speed by iterating a few times over sub-sampled images.

ex.

sub sample to 64x64,
find candidate matches
put candidates into a list of candidate locations.

sub sample to 128x128,
for the candidate location list from the previous iteration, search an area around the candidate locations
for these areas, put the best match into a new list

sub sample to 256x256,
for the candidate location list from the previous iteration, search a SMALLER area around the candidate locations
for these areas, put the best match into a new list

sub sample to 512x512,
for the candidate location list from the previous iteration, search an EVEN SMALLER area around the candidate locations
for these areas, put the best match into a new list

...

And so on and so forth, until you're up to max rez, and you're just fine-aligning within a couple pixels.

The difference in speed between this approach, and just working in full rez all the time, is dramaic. (Orders of magnitude improvement in speed).





You can do a similar approach to your templates. If you want to find an object in any orientation, have a sub-set of images for a few poses.
Match those to each spot, then if you've got a decent match score, look up (or generate) other similar poses, and try to match those.
And repeat again with more similar poses to your best matches from the last iteration, each time generating poses that are less and less different.


In 3d this is a bit easier because you can employ 'spin images' to do a pose irrespective (and to an extent resolution irrespective) signature of a set of points.
http://www.cs.cmu.edu/~dhuber/projects/ ... indep.html

I maybe you could re-work that method for 2d, but I've never done it...



Computer vision is actually one of the most fun and satisfying things I've ever worked on. I hope you have as much fun with it as I did

-scheherazade

[avriette]

Depends on what it's written in (as I'm sure you know )

Honestly, Matlab is ideal for it, but it's a little too much overhead for what I think you might be thinking of doing. You're best bet is to find a lib in C or ASM to do it.

It's an embedded device. An embedded, open but specific-to-the-hardware C is the flavor. I'm wondering if I'll need to farm off compute to a slave SBC or another microcontroller that understands it via APIC or something. It strikes me as something done frequently, although not something that would often result in a COTS product.

Camera is moving. I'll look around on the webbernets and see if there's a lib I can use or something, but I've got this wonky C, so I'm not sure I'll be able to compile anything down like that.