Let C(j,k) represent the number of combinations of j things taken k at a time. From [1], the number of states required in the Viterbi algorithm to find the best set of K completely unmerged paths (no points in common) is M = C(MM,K), where MM is the number of measurements at a particular value of time. Note that this is true for K >= 1, i.e. it is true even for K = 1 in which case C(MM,1) = MM. Our implementation treats K = 1 and K > 1 as separate cases simply to avoid the unnecessary complications of using combinations and permutations when K = 1. If we extend this to allow for missed target events (i.e. target is there, but there is no measurement corresponding to it; all of the measurements are false detections), then the number of states required in the Viterbi algorithm is: M = sum k=0..K { C(MM,k) } This formula is valid for K >= 1, i.e. it is true even for K = 1. Note that for k=0, C(MM,k) is MM!/(MM!*0!) == 1. For K = 1, the formula reduces to C(MM,1) + 1 == MM + 1, and the 1 extra state represents the missed target event. This formula specifies the number of Kalman filters which are required to track the target, and the 1 extra filter for the missed target event uses only its predicted next state, not corrected by any measurements, since there are no corresponding measurements in the missed target event. For K > 1, the C(MM,K) term in the formula represents the states which we would normally have in the K-path Viterbi algorithm with no missed target events. The C(MM,k) terms for 0 < k < K represent states added to account for combinations of up to K-1 missed target events. The C(MM,0) term, which is 1, represents the case where all K targets are missed. With no missed target events, the Viterbi state values are 1..MM and represent measurement indices. In the missed target case with K = 1, state value MM+1, which does not correspond to any real measurement index, is used to represent the missed target event. In the missed target case with K > 1, measurement index MM+1 is used in the combinations of measurement indices represented by the states of the Viterbi algorithm. In the missed target case for K > 1, when more than one target is missed, the associated states seem to violate the condition of the paths being completely unmerged. In these states, some or all of the K paths have the same measurement index, corresponding to missed target measurements. The actual target paths in this case are still really unmerged, since each path is using a separate Kalman filter prediction rather than a measurement value. Examples: Let MM = 4, so we have 4 measurements at some particular time. The measurements indices are 1, 2, 3, 4. For K = 1, with no missed target events, the C(4,1) Viterbi states are: 1 2 3 4 Representing the missed target event as measurement index MM+1, i.e. 5 for this example, the C(4,1)+1 Viterbi states for K = 1 including the missed target event are: 1 2 3 4 5 State 5 does not correspond to any real measurement index. The occurrence of this state is handled by the cost function and Kalman filter procedures used for a particular problem by the Viterbi algorithm. The Viterbi algorithm itself requires no information about what the states represent. The Viterbi algorithm itself does not need to be modified in any way in order to handle missed target events. For K = 2, with no missed target events, the C(4,2) Viterbi states correspond to the following combinations of measurement indices: 1 2 1 3 1 4 2 3 2 4 3 4 The C(4,2)+C(4,1)+C(4,0) Viterbi states including the missed target events correspond to the following combinations of measurement indices: 1 2 1 3 1 4 2 3 2 4 3 4 1 5 2 5 3 5 4 5 5 5 Note that the first six of these combinations are identical to those listed above for K = 2 with no missed target events. The additional combinations use measurement index 5, which does not correspond to any real measurement index, to represent a missed target event. There are four combinations representing one target being missed out of the two targets being tracked, and the final combination represents both targets being missed. Keep in mind that the K-path Viterbi algorithm considers, for each state transition, all possible permutations of the measurement combinations. So, for example, when combination (1,2) is being checked, it checks both (1,2) and (2,1) for possible data association with the preceding state. However, for the final combination of (5,5) representing both targets being missed, both permutations would be the same, i.e. (5,5) and (5,5), and it would be redundant to consider them both. Furthermore, if we kept track of redundant permutations in this case, it would reduce the effectiveness of the L-best part of the algorithm, since redundant permutations with the same cost would be saved in place of other higher cost alternative paths. This is handled in the Kalman cost function implementation by considering only unique permutations of the measurement indices. For K = 3, with no missed target events, the C(4,3) Viterbi states correspond to the following combinations of measurement indices: 1 2 3 1 2 4 1 3 4 2 3 4 The C(4,3)+C(4,2)+C(4,1)+C(4,0) Viterbi states including the missed target events correspond to the following combinations of measurement indices: 1 2 3 1 2 4 1 3 4 2 3 4 1 2 5 1 3 5 1 4 5 2 3 5 2 4 5 3 4 5 1 5 5 2 5 5 3 5 5 4 5 5 5 5 5 Note that the first four of these combinations are identical to those listed above for K = 3 with no missed target events. The additional combinations use measurement index 5, which does not correspond to any real measurement index, to represent a missed target event. There are six combinations representing one target being missed out of the three targets being tracked. There are four combinations representing two targets being missed, and the final combination represents all three targets being missed. For the combinations containing measurement index 5 more than once, only non-redundant permutations are considered by the Kalman cost function implementation. Specifically, as applied to this example with K = 3, the array of permutation indices used is: 1 2 3 1 3 2 2 3 1 2 1 3 3 1 2 3 2 1 These indices specify selections of the three combination indices for all possible permutations. However, when a particular set of combination indices contains repeated values, considering all of these possible permutations leads to redundancy. For example, if we take the 11th combination from the Viterbi states listed above for K = 3 with missed target events, i.e. [1 5 5], and index it using the above permutation indices, we get the following possible permutations: 1 5 5 1 5 5 5 5 1 5 1 5 5 1 5 5 5 1 Since the index 5 occurs twice in the [1 5 5] combination, some of the possible permutations are the same and are redundant. Our implementation avoids this redundancy by maintaining an additional matrix, unique_perms, which specifies all of the unique (non-redundant) permutations for each combination. In this example, for the 11th combination, unique_perms(11) is: 1 3 4 0 0 0 indicating that there are only three unique permutations of [1 5 5], those being permutation numbers 1, 3, and 4 from the list of possible permutations: 1 5 5 5 5 1 5 1 5 The unique_perms matrix uses 0's to represent unused/unneeded permutations. In order to be stored as a matrix, it must have a fixed number of elements in each row, that number being the maximum number of possible unique permutations, which is six in this example. The Kalman cost function, for K > 1, sequentially examines the permutations from the appropriate row of the unique_perms array, and stops when it encounters a 0. References ---------- [1] J. K. Wolf, A. M. Viterbi, and G. S. Dixon, Finding the Best Set of K Paths Through a Trellis with Application to Multitarget Tracking, IEEE AES-25, No. 2, March 1989, pp. 287-296