Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Multiple target tracking

Subject: Multiple target tracking

From: Sara Julie

Date: 9 Mar, 2011 14:22:21

Message: 1 of 7

can anyone explain the hypothesis conditions in multiple hypothesis tracking?
Do anyone have any sample code for MHT?
Please kindly help


Thank you

Subject: Multiple target tracking

From: David Miguel

Date: 11 Mar, 2011 01:29:07

Message: 2 of 7

Can you please elaborate on what you mean by "hypothesis conditions"?
Could you give details on your particular problem?

If you are new to the MHT(?), an overview of the MHT is like this:
You maintain a tree structure (it can also be a matrix, if you want it
simpler). Each leaf consists of a particular "view" of the world.

In each scan:
 - You receive a data set (ex.: detections on an image).
 - For each leaf, you generate hypotheses (new leaves) on what might
be the source of each detection you received (false alarm, new target,
or the detection of some existing target).
 - You prune the tree, that is, limit the growing number of hypothesis
by removing leaves or whole branches.

To make your algorithm go faster (real time), you can implement
clustering and the Murty's algorithm.
 - Clustering is a way of maintaining separate unrelated hypothesis
trees, typically each tree maintains the state of a group of targets
which is separate from all the other groups of targets.
 - When generating hypothesis for a leaf, there is a combinatorial
explosion because of the Detection->Target possible combinations, this
can even reach the millions of hypotheses, becoming very difficult to
compute. The Murty algorithm gives you the K best hypothesis from
those millions of (useless) possible hypotheses.

Hope I was of some help :)
--david

On Mar 9, 2:22 pm, "Sara Julie" <gsgsar...@gmail.com> wrote:
> can anyone explain the hypothesis conditions in multiple hypothesis tracking?
> Do anyone have any sample code for MHT?
> Please kindly help
>
> Thank you

Subject: Multiple target tracking

From: Sara Julie

Date: 11 Mar, 2011 04:25:05

Message: 3 of 7

Thanks for your help sir...
Ya Iam new to this..
Iam confused in finding hypothesis, how a target is detected as new or known target?
what parameters we need to consider?

Thank you

Subject: Multiple target tracking

From: David Miguel

Date: 11 Mar, 2011 07:47:32

Message: 4 of 7

Well, I don't have an extensive experience is this either :)

First, remember that you are considering multiple hypotheses on the
state of the world. Each hypothesis has a different "version" or
"history" or "view" on the state and history of the world. And each
leaf in the hypothesis tree corresponds to an hypothesis (assuming you
only have one tree).

For example, you may have two leaves containing the state of the world
represented bellow:
======Leaf 1======
 0 1 2 3 4 5 6 7
0
1 T1
2 T3
3
4
5 T2
6
7

======Leaf 2======
 0 1 2 3 4 5 6 7
0
1
2 T1
3
4
5 T2
6
7

According to leaf 1 there are 3 targets in the world, one is at (1,
2), the other at (5, 1), and the 3rd at (6, 5). According to leaf 2,
there are 2 targets at (5, 1) and (7, 5).

Now, consider you receive 3 measurements, for example 3 detections in
a video frame, or in a radar. The measurements are detected at (1, 6),
(5, 5) and (0, 1).

You iterate all the leaves in your hypothesis tree and generate new
hypotheses for each leaf. Lets consider, for example, the hypothesis
generation for leaf 2.

Bellow are the measurements along with the existing targets in leaf 2:
======Leaf 2======
 0 1 2 3 4 5 6 7
0 M3
1 M1
2 T1
3
4
5 M2 T2
6
7

Now, you have to generate the various hypotheses which explain the 3
measurements you received.
Each measurement may be explained as either:
- A detection of an existing target (T1 or T2, in this case).
- A new target.
- A false detection (false alarm).

So, the following hypothesis are possible in the scenario:
M3 is a false alarm (FA(M3)), M1 is a detection of T1 (T1(M1)), M2 is
a new target (T4(M2));
FA(M1), FA(M2), FA(M3);
FA(M1), FA(M2), T4(M3);
FA(M1), FA(M2), T1(M3);
FA(M1), FA(M2), T2(M3);

FA(M1), T4(M2), FA(M3);
FA(M1), T4(M2), T5(M3);
FA(M1), T4(M2), T1(M3);
FA(M1), T4(M2), T2(M3);

FA(M1), T1(M2), FA(M3);
FA(M1), T1(M2), T4(M3);
FA(M1), T1(M2), T2(M3);

FA(M1), T2(M2), FA(M3);
FA(M1), T2(M2), T4(M3);
FA(M1), T2(M2), T1(M3);

T4(M1), FA(M2), FA(M3);
(...)


Now, in your tracking application you will probably predict the next
position of each target, using a motion model, for example using a
kalman filter. So, for each target, you have a predicted position
where you expect it to be. You can use the covariance matrix of the
prediction, which tells you the probability of the target being in
each position, to limit this number of hypothesis. In the example if,
using the prediction, the probability of target T2 being in (0, 1) is
bellow a certain threshold, you simply do not consider the possibility
of M3 being a detection of target T2. The same for the other targets/
measurements.

Each of the new hypothesis (new leaves) will have a probability. This
will be the probability of the parent leaf, multiplied by the
"probability of the new leaf itself". I cannot help you much with the
calculation of these probabilities (you can find them in several
places in the literature), but they will be something like this:

(ProbOfFalseDetections^NumFalseDetections)*(ProbNewTarget^NumNewTarget)*<Probability
of detection of each target>

The probability of detection of each target will take into account how
far it is distanced from the predicted position, and the generic
probability of detecting a target.

P.S.: Side note: although I implemented the MHT several times, I am
not used to implemented exactly the "traditional" manner, thus there
are things in which I may differ from the normal (correct?)
implementation.

P.P.S.: There is a tutorial in multiple hypothesis by Samuel Blackman,
"Multiple hypothesis tracking for multiple target tracking", in IEEE
Aerospace and Electronic Systems Magazine, 2004.

Regards,
--david

On Mar 11, 4:25 am, "Sara Julie" <gsgsar...@gmail.com> wrote:
> Thanks for your help sir...
> Ya Iam new to this..
> Iam confused in finding hypothesis, how a target is detected as new or known target?
> what parameters we need to consider?
>
> Thank you

Subject: Multiple target tracking

From: Sara Julie

Date: 11 Mar, 2011 10:49:04

Message: 5 of 7

thank you very much sir...
 u gave me a detailed explanation. Now i have gained much more knowledge about mht.

Subject: Multiple target tracking

From: Sara Julie

Date: 16 Mar, 2011 03:41:05

Message: 6 of 7

sir can you send me any sample mht code?
thank you sir

Subject: Multiple target tracking

From: Sara Julie

Date: 16 Mar, 2011 08:49:04

Message: 7 of 7

sir can u kindly help me? can you send any sample multiple hypothesis tracking code. I can understand theory sir. but i have some confusions in implementing.
Thank you

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us