3
$\begingroup$

I want to fuse objects coming from several sensors, with different (sometimes overlapping!) fields of view. Having object lists, how can I determine whether some objects observed by different sensors are in fact the same object? Only then I can truly write an algorithm to predict future state of such an object. In other words, I want to associate properly those lists.

$\endgroup$
  • $\begingroup$ This is a common problem in the implementation of Extended Kalman Filters. Perhaps use Voronoi graphs? There are some publications by Professor Howie Choset in this area. The clearest way to do this would still be particle filters though. $\endgroup$ – Naresh Apr 8 '13 at 4:37
  • $\begingroup$ @Naresh how can a particle filter be applied to this problem of data association? i'm very interested in this problem! $\endgroup$ – nkint Apr 8 '13 at 7:28
  • $\begingroup$ I'm not an expert in this field. I've just read a few publications and made an implementation. The easiest way to understand this would be to start reading up on these things. However, your particular problem would be a problem while utilizing Kalman Filters as well. I know this because I tried working it out as well. $\endgroup$ – Naresh Apr 8 '13 at 7:42
4
$\begingroup$

There are many different algorithms or theories to tackle your problem.

  • As suggested in the comments, Kalman filters (in a regular or extended implementation) ore often tried in this case.
  • If you are in a discrete world (I guess so from your question), you can try to solve your problem in a discrete setting with (for example) the Hungarian algorithm.
  • If your detections come with associated confidence or plausibility (likelihood) measurements and if you are not afraid by the maths, you can try the popular Dempster-Shafer evidence theory (or one of its variants).
  • Etc. (correlations between tracks, a variant of sparse regression...).

Fusion with Kalman filtering

Let's say you know that you have one object, with the corresponding state vector (e.g., position, or position + velocity).

Now, suppose that you are observing this state with 2 different sensors or algorithms. For example, a robot or a UAV can have a first position estimation coming form an inertial measurement unit (IMU) and another positoin estimated via computer vision by detecting its pose with respect to known points of interests.

The Kalman filter with solve the problem of providing an estimate of the true state (position) accoridng to these two inputs. It will solve it in a least squares sense taking into account the intrinsic precision of the two sources. Note that it is not different to using it for tracking (in time) a single object: in the fusion case, the only difference is that all the observations were acquired at the same time.

Your inputs to the Kalman filters are the previous position + the 2 estimated positions, and the output is a single position (ideally the "true" one). The observation matrix produces a position given the sensor inputs. In this example (input=position, output=position) it would be the identity. You incorporate knowledge about the precision of each sensor in the variance matrix of the filter.

Here is an example application that I have found.

$\endgroup$
  • $\begingroup$ how to apply kalman filter (or for non gaussian, the particle filter)? i thought those filters are for smoothing noisy data, how can you apply to data association problem? i'm very interesting in this solution (i asked something similar in a past question never answered) $\endgroup$ – nkint Apr 8 '13 at 7:31
  • $\begingroup$ However, Kalman Filters do not exactly solve the problem he has specified. For example, a Kalman Filter may recognize the same object/feature as different when it approaches from a different direction due to accumalated errors during travel. Professor Howie Choset tries to rectify this using Voronoi Graphs in addition to Kalman Filters(using Kalman Filters for 'near' localization and Voronoi Graphs for 'far' localization. $\endgroup$ – Naresh Apr 8 '13 at 10:49
  • $\begingroup$ True, there is a two-tier problem here: first determining the number of objects (an assignemnt problem), and second obtaining good estimates of each object state given (possibly) several measuerments (a fusion problem). $\endgroup$ – sansuiso Apr 8 '13 at 11:06
0
$\begingroup$

Let's say that at time $t_k$ you know the state vector $X_k=[p_k,v_k]$ of your obect and the associated covariance matric $P_k$.

At time $t_{k+1}$ you have three sensor giving you the object's position $p_{k+1}^1,p_{k+1}^2,p_{k+1}^3$ and their associates covariances matrixes $R_{k+1}^1,R_{k+1}^2,R_{k+1}^3$.

You'll fuse these informations using a kalman filter with the following observation process :

$$ Y_{k+1}=H_{k+1}X_{k+1}+R_{k+1} $$ with $$ H_{k+1}X_{k+1}= \left( \begin{array}{ccc} p_{k+1}^1 & 0 & 0 \\ 0 & p_{k+1}^2 & 0 \\ 0 & 0 & p_{k+1}^3 \end{array} \right) $$

$$ R_{k+1}= \left( \begin{array}{ccc} R_{k+1}^1 & 0 & 0 \\ 0 & R_{k+1}^2 & 0 \\ 0 & 0 & R_{k+1}^3 \end{array} \right) $$

I let you do all the combersome formulations for the kalman filter's implementation, but you got the idea.

You will run a different Kalman filter for each time step because you won't have the same number of sensor detecting the object, but it is a non issue as you have the object's state covariance independantly from the number of sensor.

If there is a time step where you don't have any observation at all, you just run the prediction step without the update.

If you have more than one object and/or false alarm, this become much more complicated and you'll want to google multi-target tracking, data association, multiple hypothesis tracker, probability hypothesis density filter.

If you have one object and false alarm this may be a bit more simpler and try googling joint probabilistic data association filter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.