Groups | Search | Server Info | Keyboard shortcuts | Login | Register

Groups > comp.graphics.algorithms > #886

Data structures for image processing of moving blobs

Show all headers | View raw

Hi there,

I've been looking at various nearest neighbour query algos to track many
moving objects from a camera. There's a bunch of fancy papers out there,
most of them are using variants of R-trees, Bx-Trees, etc.
I've kinda ended up with the R-tree but am still not happy with rather
complex tree reorganisations that are triggered by certain conditions.
So I'm generally heading towards something referred to as "kinetic data
structures", where plausible movements are taken into account.

But let me describe the general problem first:
I am getting a sequence of camera images with
local brightness maxima. Those can be distributed arbitrarely over the
image. Normally they are dots of a small ROI (rectangular region of
interest), but there can be artefacts such that many blobs can suddenly
(dis-)appear at once. All the ROIs move arbitrarely and can collide
(which causes special events).
A preprocessing step already extracts the maxima blobs and labels them
with an incrementing index value (in order of appearance, see also below).

There are a few special rules:
1. ROIs (boundary boxes around the blobs) are coming from the
preprocessor, sorted in (Y then X) direction due to the line scanning
procedure
2. ROIs can appear and disappear at any time
3. Some ROIs are "good" and have a known ID (verified over several
frames), some are artefacts ("bad") to be eliminated at runtime.
4. No floating point arithmetics. Delaunay/Voronoi procedures are
therefore too expensive (for the global image at least).
5. Up to 2000 blobs are expected/processed, the number of finally
matching ROI should not exceed ~500.

So far, I haven't found any descriptions with respect to the special
case of raster scanned image data where the objects are a priori
found and sorted, but not uniquely identifiable.

Any ideas from the experts?

Cheers,

- Martin

Back to comp.graphics.algorithms | Previous | Next | Find similar

Thread

Data structures for image processing of moving blobs Martin Strubel <hackfin-removethis-@section5.ch> - 2012-06-25 18:03 +0200

csiph-web