Understanding Sensor Fusion and Tracking, Part 5: How to Track Multiple Objects at Once

Summary

This video delves into the complexities of multi-object tracking, contrasting it with single-object tracking and highlighting the challenges of data association and track maintenance. The host, Brian, discusses various algorithms, such as the Global Nearest Neighbor (GNN) and Joint Probabilistic Data Association (JPDA), for solving these issues, emphasizing the importance of selecting the right method based on the specific tracking scenario. He also touches on the practical aspects of implementing these algorithms in MATLAB, showcasing their performance through an example.

Takeaways

• 🚀 The video discusses expanding single object tracking to multiple object tracking, emphasizing the additional complexities involved.
• 🔍 Multi-object tracking introduces challenges such as data association, where measurements must be correctly matched to the corresponding tracked object.
• 📊 Tracking algorithms must account for uncertainty in both object observations and predictions of their paths, blending uncertain measurements with uncertain predictions.
• 🤖 The video introduces the concept of an estimation filter, which is used to correct predictions with actual measurements, highlighting its importance in tracking.
• 🔄 The number of objects being tracked can change, requiring the creation and deletion of tracks based on observations, introducing the track maintenance problem.
• 📐 The Global Nearest Neighbor (GNN) is a simple assignment algorithm that matches observations to tracks based on probabilistic distance, not just geometric distance.
• 🔎 The Joint Probabilistic Data Association (JPDA) algorithm is introduced as an alternative to GNN, which makes weighted combinations of all neighboring observations, better suited for clustered objects.
• 🛠️ The video suggests that track maintenance involves careful deletion and creation of tracks to avoid premature actions that could clutter the tracking view or decrease effectiveness.
• 📈 Track deletion can be managed conservatively by setting parameters for the number of times a track must not be assigned to a detection before being removed.
• 🛑 Tentative tracks can be created for unassigned observations, maintained in the background, and only confirmed as real objects after being detected a certain number of times.
• 🚫 Gating is a technique to ignore observations outside a defined region for each track, which can speed up the assignment process and save computational resources.

Q & A

What is the main focus of the video?

The video focuses on expanding the concept of tracking a single object to tracking multiple objects at once, discussing the complexities and solutions involved in multi-object tracking.

Why can't we simply apply a single-object tracking algorithm to each object in a multi-object tracking scenario?

Applying a single-object tracking algorithm to each object individually doesn't account for the additional complexities in multi-object tracking, such as data association, track creation and deletion, and the handling of uncertainty in observations and predictions.

What is the 'data association problem' in multi-object tracking?

The data association problem refers to the challenge of correctly matching observations (detections) with the correct tracked objects, especially when objects are close to each other or when observations are uncertain.

How does the Global Nearest Neighbor (GNN) algorithm handle assignment in multi-object tracking?

The GNN algorithm assigns an observation to the track with the nearest probabilistic distance, such as the Mahalanobis distance, rather than the nearest Euclidean distance.

What is the Joint Probabilistic Data Association (JPDA) algorithm, and how does it differ from GNN?

The JPDA algorithm makes a weighted combination of all neighboring observations with tracks, giving higher weights to closer observations. Unlike GNN, which makes a hard assignment, JPDA does not fully commit to a single observation, allowing it to handle situations where objects are clustered more effectively.

What are the criteria for creating and deleting object tracks in multi-object tracking?

Tracks can be created when a detection doesn't match any existing object, and deleted if a track has not been assigned to a detection for a certain number of updates. However, care must be taken to avoid false positives and premature deletions.

Why is track maintenance important in multi-object tracking?

Track maintenance is important to ensure that the tracking system does not create tracks prematurely, which could clutter the view, or delete tracks too early, which could decrease tracking effectiveness.

What is the purpose of gating in the context of multi-object tracking?

Gating is a screening mechanism used to determine which detections are valid candidates for assignment and which should be ignored, thus speeding up the assignment process and conserving computational resources.

How does the video demonstrate the effectiveness of different multi-object tracking algorithms?

The video shows an example in MATLAB where two objects are tracked using different algorithms, illustrating how each algorithm performs under conditions where objects are close to each other and detections overlap.

What should one consider when choosing a multi-object tracking algorithm?

When choosing a multi-object tracking algorithm, one should consider the specific requirements and conditions of their tracking scenario, such as the number of objects, the accuracy needed, computational resources available, and the expected behavior of the objects.

Outlines

00:00

🚀 Introduction to Multi-Object Tracking Challenges

The video begins by addressing the complexities of transitioning from tracking a single object to multiple objects simultaneously. It highlights that while it may seem straightforward to apply a single-object tracking algorithm to each object, additional considerations are necessary. The speaker, Brian, introduces the video's aim to provide an overview of multi-object tracking, emphasizing the importance of understanding the unique challenges and the art of selecting or developing algorithms tailored to specific tracking scenarios. The discussion sets the stage for exploring the issues stemming from uncertainty in object observations and predictions, which are central to the multi-object tracking problem.

05:03

🔍 Understanding the Data Association Problem

This paragraph delves into the intricacies of the data association problem, where the challenge lies in correctly matching observations to their corresponding tracked objects, especially when objects are close together or observations are uncertain. The paragraph explains that simple nearest neighbor approaches may not suffice in cluttered environments and introduces the concept of probabilistic distance, such as the Mahalanobis distance, for more accurate data association. It also touches on the Joint Probabilistic Data Association (JPDA) algorithm, which provides a weighted combination of observations to improve tracking accuracy in complex scenarios.

10:07

🛰️ Track Maintenance: Creation and Deletion of Tracks

The third paragraph discusses the dynamic nature of multi-object tracking, where the number of objects is not static, and tracks must be created or deleted based on observations. The speaker outlines a conservative approach to track deletion, suggesting that tracks should only be removed after failing to be assigned an observation multiple times. Conversely, creating a track is approached with tentative tracks that are maintained in the background and only confirmed after being detected multiple times. This approach helps in managing false positives and ensures that the tracking system does not prematurely create or delete tracks, thus maintaining the effectiveness of the tracking process.

15:07

📊 Multi-Object Tracking Algorithms Demonstration and Conclusion

The final paragraph wraps up the video with a practical demonstration of multi-object tracking algorithms in MATLAB, showcasing the performance of Global Nearest Neighbor (GNN) and Joint Probabilistic Data Association (JPDA) algorithms in tracking two independently moving objects. The demonstration highlights the challenges faced when objects are in close proximity and the respective strengths and weaknesses of each algorithm. The speaker concludes by emphasizing the importance of understanding the unique requirements of each tracking scenario and selecting the most appropriate algorithm, rather than opting for the most complex solution.

Keywords

💡Multi-Object Tracking

Multi-Object Tracking refers to the process of simultaneously tracking multiple objects using sensors or algorithms. In the context of the video, this is the central theme where the speaker discusses the complexities of tracking more than one object at a time, as opposed to single object tracking. The script mentions the need to expand tracking algorithms to handle multiple objects and the various challenges that arise from this, such as data association and track maintenance.

💡IMM (Interacting Multiple Model)

IMM is a type of estimation filter used in tracking systems that allows for multiple models to represent different motion modes of an object. The video script mentions the IMM in the context of applying a tracking algorithm to multiple objects, suggesting that one could theoretically apply the IMM to each object for tracking. However, the speaker also points out that additional considerations are necessary when tracking multiple objects.

💡Data Association

Data Association is the problem of matching observations (sensor detections) to the correct tracks (ongoing object tracking). The script discusses this as a significant challenge in multi-object tracking, especially when objects are close to each other or when there is a high level of uncertainty. The video describes how data association is critical to avoid using the measurement of one object to update the prediction of another.

💡Track Maintenance

Track Maintenance involves the creation and deletion of tracks based on observations. The script explains that the number of objects being tracked is not fixed and that algorithms must handle the creation of new tracks when objects enter the radar range and deletion when they exit or land, considering the possibility of false positives and sensor failures.

💡Estimation Filter

An Estimation Filter is a statistical tool used to predict the state of a system based on uncertain measurements and predictions. The video script refers to estimation filters like the IMM and the Kalman filter, which are used to blend uncertain predictions with actual measurements to update the state of tracked objects.

💡GNN (Global Nearest Neighbor)

GNN is an assignment algorithm that matches each observation to the track that is closest to it in a probabilistic sense. The video script uses GNN as an example of a simple assignment algorithm that works well when objects are sparsely distributed but may struggle when objects are close together, leading to potential mismatches.

💡JPDA (Joint Probabilistic Data Association)

JPDA is an advanced assignment algorithm that makes a weighted combination of all neighboring observations, giving higher weights to closer observations. The script contrasts JPDA with GNN, showing that JPDA can better handle situations where objects are clustered closely together by not committing to a single observation-to-track match.

💡Mahalanobis Distance

Mahalanobis Distance is a measure of the distance between a point and a distribution, taking into account the covariance of the distribution. The video script explains that this distance is used in GNN to determine the best match between a prediction and a measurement, as it accounts for the uncertainty in the predictions and measurements.

💡Track Creation

Track Creation is the process of initiating a new track for an object that has not been previously tracked. The script discusses the criteria for creating tracks, such as when a detection does not match any existing object, and the caution needed to avoid creating tracks from false positive measurements.

💡Track Deletion

Track Deletion is the process of removing a track when an object is no longer detected or when a track is confirmed to be a false positive. The video script suggests a conservative approach to track deletion, such as only deleting a track if it has not been assigned a detection multiple times over several updates.

💡Gating

Gating is a screening mechanism used to determine which detections are valid candidates for assignment to tracks. The script mentions gating as a way to ignore observations outside a defined region for each track, thus speeding up the assignment process and conserving computational resources.

Highlights

Introduction to expanding single object tracking to multiple objects using algorithms like IMM, with considerations for additional complexities in multi-object scenarios.

The importance of understanding the art of selecting or developing algorithms for multi-object tracking due to the variability in problem specifics.

Challenges in multi-object tracking arising from uncertainty in object observations and predictions of their paths.

The problem of data association in matching observations to tracked objects without unique identifiers.

Situations where objects are close, leading to difficulties in data association due to overlapping measurements.

The dynamic nature of multi-object tracking, including the creation and deletion of tracks based on observations.

Strategies for track maintenance to avoid premature creation or deletion of tracks due to false positives or sensor failures.

Different assignment algorithms for data association, including GNN and JPDA, and their respective advantages and limitations.

The concept of gating to ignore observations outside a defined region for each track, enhancing computational efficiency.

The use of Mahalanobis distance in GNN for matching observations to tracks based on probabilistic distance rather than Euclidean distance.

JPDA's approach to data association by making a weighted combination of all neighboring observations.

Criteria for creating tracks, such as maintaining tentative tracks and confirming them based on detection frequency.

Criteria for deleting tracks, using parameters like P times in R updates to avoid premature deletion.

The process of updating tracked objects with estimation filters after assigning observations to tracks.

MATLAB example demonstrating the performance of GNN and JPDA algorithms in tracking two maneuvering objects.

Comparison of GNN and JPDA algorithms, showing the benefits and drawbacks of each in different tracking scenarios.

The necessity of assessing requirements before implementing complex tracking algorithms to balance accuracy and complexity.

Transcripts

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