Is there any tracking algorithm utilizing 'assignsd'?

8 views (last 30 days)
trackerGNN utilizes the assignment algorithms such as matchpairs, Munkres, Jonker-Volgenant, Auction which solve 2-D assignment problem. Also, we have Custom assignment algorithm option. But, I don't think it allows me to do multi-dimensional assignment in my way, because the cost matrices are arranged in 2-D. trackFuser also use GNN by assuming each tracks are coming from a single source by reducing dimension in trackFuser --> Core Algorithm --> distance().
trackerTOMHT utilizes the assignTOMHT algorithm which does only gating as far as I understand.
In addition, we have another method for assignment assignsd or assignkbestsd which is introduced in
  1. Deb, S., Yeddanapudi, M., Pattipati, K., and Bar-Shalom, Y. (1997). A generalized SD assignment algorithm for multisensor-multitarget state estimation.
However, even we have multi-sensor or multi track source, none of above algorithms calls assignsd or assignkbestsd. Is there any use case for S-D assignment problem? Does any tracking algorithm do multi-dimensional assignment at once not pretending the problem is 2-D? If not, why?

Accepted Answer

Prashant Arora
Prashant Arora on 26 Apr 2023
Hi Said,
You are right that assignment between tracks and measurements/tracks from multiple sources can be formulated as a S-D assignment problem. Here the first dimension will refer to "tracks", and the subsequent dimensions refer to measurements from S-1 sensors. The S-D assignment has much higher complexity than 2-D assignment problems. I believe the complexity grows linearly with maximum number of iterations and the number of dimensions. It is also a suboptimal algorithm and often requires parallel computing resources when number of sensors > 3.
The tracking algorithms (trackerGNN, trackerJPDA, and trackerTOMHT) do not use S-D assignment as of R2023a. These trackers use an "iterated-corrector" approach for multi-sensor fusion, which is a popular method in literature.
  1. trackerGNN uses 2-D assignment for each sensor. Technically, it is possible to use the best solution to S-D assignment for a GNN tracker at the cost of increased computation and possible sub-optimality at each sensor.
  2. trackerJPDA generates feasible events from 2-D assignment problems to compute data association probabilities. The literature is sparse for generating feasible events using S-D assignment problems. The number of feasible events from a S-D assignment can be really high, hurting the efficiency of JPDA algorithm. A possible alternate can be to use m-best solutions to S-D assignment problem for data association probabilities. However, it will again be much slower as compared to iterated 2-D problems for practical applications.
  3. trackerTOMHT generates all assignment hypothesis (based on gating thresholds) at the track-level. It does not solve a global assignment problem for that. Instead, it first generates track-level assignment hypothesis, which are then used to define global hypothesis. A hypothesis-oriented MHT (HOMHT) may use 2-D or S-D assignment to generate global hypothesis.
The S-D assignment is also popular for "static fusion". "Static fusion" aims to associate detections from multiple synchronous sensors to each other. See some examples here:
If you would like to use S-D assignment for multi-sensor object tracking, consider using building blocks offered by the toolbox. These include:
  1. Tracking filters (trackingEKF, trackingUKF etc.) - They offer estimation + association likelihood/distance methods.
  2. S-D assignment algorithms (assignsd, assignkbestsd)
  3. Track management logics (trackHistoryLogic, trackScoreLogic) - They offer ways to know when to confirm, initialize and delete tracks.
  4. Filter initialization functions (initcvekf, initcaekf etc.) - They offer ways to initialize a filter from a measurement.
Hope this helps.
  1 Comment
Said Kemal
Said Kemal on 6 Sep 2023
Hi again, I revisited your comment and wanted to ask one more question. You have mentioned about computational complexity of s-D assignment methods as well as their sub-optimality.
  1. Are not s-D assignment techniques able to achieve more accurate results in dense and complex scenarios?
  2. If s-D assignment techniques are more accurate but more computationally complex, is it more trouble than it is worth?
Thanks for your valuable comments.

Sign in to comment.

More Answers (0)




Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!