# Is there any tracking algorithm utilizing 'assignsd'?

8 views (last 30 days)
Said Kemal on 26 Apr 2023
Commented: Said Kemal on 6 Sep 2023
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?

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.
Thanks,
Prashant
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?

### Categories

Find more on Multi-Object Trackers in Help Center and File Exchange

R2022b

### Community Treasure Hunt

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

Start Hunting!