in this video we're gonna take what we've learned about tracking a single
object and expand it to tracking multiple objects all at once and at
first glance it doesn't seem like this problem is that much harder than
tracking a single object for example can't we just take the tracking
algorithm like the IMM from the last video and apply one to each object and
be done well as you might expect based on the way I asked that question the
answer is no not really at least there are some additional things we need to
consider with multi object tracking and that's what we're gonna talk about in
this video so I hope you stick around for it I'm Brian and welcome to a MATLAB
Tech Talk now I'm gonna highlight a general outline so that you get an idea
of how these problems can be solved but by no means do I want you to think that
there's only one way or one algorithm to get the job done every problem is
different because you know they have things like different number of objects
or you have access to different measured data and information or maybe different
expectations on how close the objects will be to each other and you're gonna
have different computational resources at your disposal or different
requirements on how accurate you need to be and so on there's a bunch and in a
way figuring out how to tackle your particular problem is more of an art
than a hard science so the thing I hope you take away from this video is to
understand the types of things you should be aware of when selecting or
developing your own algorithms for multi object tracking and not necessarily how
to solve your exact problem ok enough of this disclaimer let's get to it to begin
let's talk about what makes multi object tracking difficult and then we'll circle
back around and talk about how we can approach solving these issues all of the
problems we're gonna have stemmed from our uncertainty this is uncertainty in
the observations or detection of the objects and uncertainty in our
predictions of the paths that the objects are taking remember from the
last video that an estimation filter like a common filter works by blending
and uncertain measurement with an uncertain prediction and we looked at
tracking an airplane with a radar station we predicted where the airplane
would be in the future and then we corrected it with a noisy radar
measurement but now instead of a single object we have lots of objects each with
their own uncertain prediction that we need to correct with its corresponding
uncertain measurement so already we come to our first problem we don't want to
correct a prediction of one object using the measurement of another but if
there's no identifying information that comes with the detection like an
airplane tail number or some other unique signature how do we know which
object we've just detected for example of all of the airplanes we're tracking
have similar radar cross-sections and this is all the information we have
access to how can we match an arbitrary ping with the appropriate tracked object
now this isn't too much of a problem if all of the objects are sparsely
distributed and the observations are relatively reliable it would be a simple
matter to claim that an observation is of the object that it's closest to in
this case we would just assign the measurement to the nearest object and
run the estimation filter for it like we would when tracking a single object
the tricky part however comes when objects are close enough to each other
or our uncertainty is great enough that a measurement could be of more than one
object now we have some figuring out to do and this is the data Association
problem we have to associate the detections with the right objects all
right so that's one problem but another thing we need to consider is that the
number of objects being tracked is not fixed
sometimes tracks need to be created or removed based on what we observe we may
add a new track when an airplane flies into the radar range and similarly we
may delete a track when one flies out now this creation and deletion doesn't
just happen along the edge of the field of view of the sensors we may have to
create and delete tracks anywhere for example an airplane may land or takeoff
within the radar range so we need to think about the criteria for creating
and deleting object tracks and a basic way to approach this is to add a track
whenever there is a detection that doesn't match an existing object and
then just delete a track if an existing object is not detected
the thing that complicates this is that sometimes sensors have false positive
measurements they detect something that isn't actually there and sometimes
sensors fail a few times in a row to detect an object that is actually there
so we need to be careful here so that we aren't creating tracks prematurely which
clutters our view of what's actually there and we aren't deleting tracks
prematurely which decreases the effectiveness of tracking in the first
place this is the track maintenance problem so that's what we're gonna cover
for the rest of this video when tracking multiple objects what are some ways that
we can approach data Association and what are some ways that we can address
track maintenance and this brings us back to the flowchart that I briefly
showed at the beginning of this video and while your particular approach might
not result in a functional structure that looks exactly like this it's going
to provide a convenient way for me to talk about each of these sections so
let's just walk through it and we're going to start with observations an
observation of an object may contain measured quantities like range range
rate or line-of-sight these are quantities that represent the kinematic
nature of the object but observations could also contain measured attributes
like target type ID number and object shape and this is what I was hinting at
earlier when I said that you might get the tail number of an aircraft or some
other identifying information with an observation getting a tail number is
pretty unambiguous for data Association but other types of attributes might
still require some interpretation for example you might collect micro Doppler
radar fluctuations and from that be able to determine the type of aircraft you're
tracking in the uncertainty in the observation depends on the degree of
separation between the two objects a helicopter might look completely
different from a jet aircraft because of the large rotating propellers whereas a
bird and a quadcopter might have similar Doppler signatures
other things to consider with observations is that if the tracked
object is a point target then the observation would contain at most one
detection so we have to associate one detection with one object but if the
target object is large in the sensor has sufficient resolution like with lidar
for instance there may be more than one detection per target and we need to
consider this when determining how we're going to handle associating this data
also if the resolution of the sensor is low then it's possible that two objects
may exist within a single detection in this case both objects have been
observed so we don't want to stop tracking either of them but they show up
as only a single detection so our track deletion algorithm will have to handle
these situations going forward in this video we're only going to be talking
about the case where we expect one detection for each tracked object and
where this is handled is in the assignment step which is next assignment
is the process of matching an observation to attract object or if
you're into the whole brevity thing it's matching it to a track and possibly the
simplest assignment algorithm to think about is the GNN
the global nearest neighbor this simply assigns a track to the nearest
observation but the interesting thing here is that it's not necessarily the
nearest Euclidean or geometric distance but the nearest probabilistic distance
like you get with the Mahalanobis distance and here's why with a
probability distribution like we have with both our predictions and our
measurements the lowest Euclidean distance doesn't always indicate that a
prediction and a measurement are the best fit this is because we have more
confidence in our predictions measurements in the directions with
lower standard deviations for example in this simple image we have a prediction
for the location of two different objects and a single detection that lies
between them if we used Euclidean distance we'd assume that the detection
is of object two since it's closer but if we look at the probability
distributions of the two predictions then we can see that it's more probable
that the detection is of object one and this is what the Mahalanobis distance
does for us it's the distance normalized by the standard deviation now GNN works
well for sparsely distributed objects but for
cluttered objects another assignment algorithm like the J PDA or joint
probabilistic data Association algorithm will be better the J PDA doesn't make a
hard assignment between one observation and one track instead it makes a
weighted combination of all of the neighboring observations with closer
observations being weighted higher than further once and this is an improvement
over GNN because if there are two observations that could be the object
the J PDA won't fully commit to one possibly the wrong one so if the Trax
objects are clustered near each other and the observations are all clustered
near them too this algorithm can handle that by blending a few of them together
rather than jumping around between right and wrong
detection z' now there's many more assignment algorithms and you can create
your own based on your tracking situation but the bottom line is that
you're just trying to figure out how to associate an observation with a track
not all observations get assigned and not all tracks have observations this is
where track maintenance comes in in the form of deleting and creating tracks but
as I said before we have to be careful so we don't do anything prematurely so
let's start with one way to delete tracks in a conservative way rather than
saying an object is gone as soon as we miss a single observation we could
delete tracks only if a track has not been assigned to a detection at least P
times during the last hour updates in this case p and r are parameters that
you can tune to your situation so you might say delete a track if it hasn't
been detected at least four times in the last six updates now on the other hand
creating a track is a little trickier because you don't know if a single
unassigned observation is a new object right away but you still have to pay
attention to it so that you can figure out overtime if it's worth tracking one
way to handle this is to create a tentative track one that you maintain
and pretend like it's a real object but you don't actually believe is a real
object you just maintain that track in the background once the tentative track
has been detected M times in the last in updates then you move that track to
confirmed which means that you think it is a real object
and we can remove a tentative track with the same logic as removing a confirmed
track so in this way you may have dozens of tentative tracks that you are
maintaining due to false positive measurements but are deleting before
they ever become confirmed so with the tracks created and removed and with the
observations assigned we can run a set of estimation filters and this part is
identical to single object tracking where we had choices like the
interacting multiple model filter or the single model calman filter the predicted
state of each tracked object that is assigned in observation and that's both
tentative and confirmed objects they get updated with their respective
observation and then the whole process starts anew we get more observations and
then they're assigned to tracks and tracks are created and deleted and then
the filters run again however it would be computationally foolish to look at
every single observation and consider how likely it is to be assigned to every
single track therefore we may choose to ignore observations outside of a defined
region for each track and this is called gating and it's a screening mechanism
that determines which detections are valid candidates to look at for
assignment and which should just be flat-out ignored for example with JPD a
an observation that's really far away from the tracked object would
statistically contribute very little to the overall solution
so why spin the computational resources to even calculate this miniscule amount
and this is especially true if you're tracking dozens or hundreds of objects
this can be extremely wasteful but by ignoring observations outside of a
specific region outside of this gate we can speed up the assignment process
all right this is where I'm gonna leave this video but before I end it I want to
quickly show you an example in MATLAB that shows the results of two different
multi object tracking algorithms in this example there's two objects that are
moving independent of each other and we're observing them through a tracking
radar the black triangles are the true positions of the objects and the circles
are what are being detected with the radar station notice that when the two
objects get close to each other the detections overlap and it becomes
difficult to tell where the objects are in this region of ambiguity so this is
the data we have to work with and let's try the algorithms and see how they do
for the first one I'm using global nearest neighbor for data Association
and an IMM for the estimation filter since these objects are maneuvering
notice that when the objects are far from each other it's obvious which
objects and detections go together and the G&N algorithm does a pretty good job
object 1 is assigned to track 1 and object 2 is assigned to track 2 this is
what GNN is good at matching data with tracked objects when they are sparse but
when the objects are close to each other it doesn't do so well you can see that
one track was deleted and a new track was added a few detections later
so the algorithm got confused as to how many objects there were at one point in
fact it jumped from track number 2 to track number 8 which means there were
five other tentative tracks that it was maintaining before confirming the sixth
one as track eight all right let's upgrade our assignment algorithm to the
joint probabilistic data Association algorithm and see if it fares any better
well it's interesting the two tracks are maintained through the whole maneuver
but in the region of ambiguity there's still a lot more error than anywhere
else but this is to be expected since the data overlaps in this region so much
it's amazing that these algorithms can pull anything out from a situation like
this now there is additional cost and complexity with J PDA over GNN so it's
worth assessing what your requirements are rather than just implementing the
most accurate and complex algorithms if the objects always were far away from
each other then I'd prefer the simple GNN approach since it works fine in
those situations and it's much easier to interpret and implement so that's the
overall gist of the types of things that we need to think about and the kinds of
problems we have to solve when tracking multiple objects at once and I want to
stress again that there's no one way to accomplish this it's completely
dependent on each unique situation but hopefully with this general overview
you'll be in a better position to understand how to tackle your next multi
object tracking problem alright if you don't want to miss the next Tech Talk
video don't forget to subscribe to this channel also if you want to check out my
channel control system lectures I cover more control theory topics there as well
thanks for watching and I'll see you next time