assignDetectionsToTracks

Assign detections to tracks for multiobject tracking

Syntax

[assignments,unassignedTracks,unassignedDetections] = assignDetectionsToTracks(costMatrix,costOfNonAssignment)

[assignments,unassignedTracks,unassignedDetections] = assignDetectionsToTracks(costMatrix, unassignedTrackCost,unassignedDetectionCost)

Description

[assignments,unassignedTracks,unassignedDetections] = assignDetectionsToTracks(costMatrix,costOfNonAssignment) assigns detections to tracks in the context of multiple object tracking using the James Munkres's variant of the Hungarian assignment algorithm. It also determines which tracks are missing and which detections should begin new tracks. It returns the indices of assigned and unassigned tracks, and unassigned detections. The costMatrix must be an M-by-N matrix. In this matrix, M represents the number of tracks, and N is the number of detections. Each value represents the cost of assigning the N^th detection to the M^th track. The lower the cost, the more likely that a detection gets assigned to a track. The costOfNonAssignment scalar input represents the cost of a track or a detection remaining unassigned.

[assignments,unassignedTracks,unassignedDetections] = assignDetectionsToTracks(costMatrix, unassignedTrackCost,unassignedDetectionCost) specifies the cost of unassigned tracks and detections separately. The unassignedTrackCost must be a scalar value, or an M-element vector, where M represents the number of tracks. For the M-element vector, each element represents the cost of not assigning any detection to that track. The unassignedDetectionCost must be a scalar value or an N-element vector, where N represents the number of detections.

Examples

Assign Detections to Tracks in a Single Video Frame

This example shows you how to assign a detection to a track for a single video frame.

Set the predicted locations of objects in the current frame. Obtain predictions using the Kalman filter System object.

predictions = [1,1;2,2];

Set the locations of the objects detected in the current frame. For this example, there are 2 tracks and 3 new detections. Thus, at least one of the detections is unmatched, which can indicate a new track.

detections = [1.1,1.1;2.1,2.1;1.5,3];

Preallocate a cost matrix.

cost = zeros(size(predictions,1),size(detections,1));

Compute the cost of each prediction matching a detection. The cost here, is defined as the Euclidean distance between the prediction and the detection.

for i = 1:size(predictions, 1)
      diff = detections - repmat(predictions(i,:),[size(detections,1),1]);
      cost(i, :) = sqrt(sum(diff .^ 2,2));
end

Associate detections with predictions. Detection 1 should match to track 1, and detection 2 should match to track 2. Detection 3 should be unmatched.

[assignment,unassignedTracks,unassignedDetections] = ...
            assignDetectionsToTracks(cost,0.2);
  figure;
  plot(predictions(:,1),predictions(:,2),'*',detections(:,1),...
            detections(:,2),'ro');
  hold on;
  legend('predictions','detections');
  for i = 1:size(assignment,1)
    text(predictions(assignment(i, 1),1)+0.1,...
            predictions(assignment(i,1),2)-0.1,num2str(i));
    text(detections(assignment(i, 2),1)+0.1,...
            detections(assignment(i,2),2)-0.1,num2str(i));
  end
  for i = 1:length(unassignedDetections)
    text(detections(unassignedDetections(i),1)+0.1,...
            detections(unassignedDetections(i),2)+0.1,'unassigned');
  end
  xlim([0,4]);
  ylim([0,4]);

Input Arguments

costMatrix — Cost of assigning detection to track

M-by-N matrix

Cost of assigning a detection to a track, specified as an M-by-N matrix, where M represents the number of tracks, and N is the number of detections. The cost matrix value must be real, nonsparse, and numeric. The lower the cost, the more likely that a detection gets assigned to a track. Each value represents the cost of assigning the N^th detection to the M^th track. If there is no likelihood of an assignment between a detection and a track, the costMatrix input is set to Inf. Internally, this function pads the cost matrix with dummy rows and columns to account for the possibility of unassigned tracks and detections. The padded rows represent detections not assigned to any tracks. The padded columns represent tracks not associated with any detections. The function applies the Hungarian assignment algorithm to the padded matrix.

Data Types: int8 | uint8 | int16 | uint16 | int32 | uint32 | single | double

costOfNonAssignment — Cost of not assigning detection to any track or track to any detection

scalar | finite

Cost of not assigning detection to any track or track to detection. You can specify this value as a scalar value representing the cost of a track or a detection remaining unassigned. An unassigned detection may become the start of a new track. If a track is unassigned, the object does not appear. The higher the costOfNonAssignment value, the higher the likelihood that every track will be assigned a detection.

Internally, this function pads the cost matrix with dummy rows and columns to account for the possibility of unassigned tracks and detections. The padded rows represent detections not assigned to any tracks. The padded columns represent tracks not associated with any detections. To apply the same value to all elements in both the rows and columns, use the syntax with the costOfNonAssignment input. To vary the values for different detections or tracks, use the syntax with the unassignedTrackCost and unassignedDetectionCost inputs.

Data Types: int8 | uint8 | int16 | uint16 | int32 | uint32 | single | double

unassignedTrackCost — Cost or likelihood of an unassigned track

M-element vector | scalar | finite

Cost or likelihood of an unassigned track. You can specify this value as a scalar value, or an M-element vector, where M represents the number of tracks. For the M-element vector, each element represents the cost of not assigning any detection to that track. A scalar input represents the same cost of being unassigned for all tracks. The cost may vary depending on what you know about each track and the scene. For example, if an object is about to leave the field of view, the cost of the corresponding track being unassigned should be low.

Internally, this function pads the cost matrix with dummy rows and columns to account for the possibility of unassigned tracks and detections. The padded rows represent detections not assigned to any tracks. The padded columns represent tracks not associated with any detections. To vary the values for different detections or tracks, use the syntax with the unassignedTrackCost and unassignedDetectionCost inputs. To apply the same value to all elements in both the rows and columns, use the syntax with the costOfNonAssignment input.

Data Types: int8 | uint8 | int16 | uint16 | int32 | uint32 | single | double

unassignedDetectionCost — Cost of unassigned detection

N-element vector | scalar | finite

Cost of unassigned detection, specified as a scalar value or an N-element vector, where N represents the number of detections. For the N- element vector, each element represents the cost of starting a new track for that detection. A scalar input represents the same cost of being unassigned for all tracks. The cost may vary depending on what you know about each detection and the scene. For example, if a detection appears close to the edge of the image, it is more likely to be a new object.

Internally, this function pads the cost matrix with dummy rows and columns to account for the possibility of unassigned tracks and detections. The padded rows represent detections not assigned to any tracks. The padded columns represent tracks not associated with any detections. To vary the values for different detections or tracks, use the syntax with the unassignedTrackCost and unassignedDetectionCost inputs. To apply the same value to all elements in both the rows and columns, use the syntax with the costOfNonAssignment input.

Data Types: int8 | uint8 | int16 | uint16 | int32 | uint32 | single | double

Output Arguments

assignments — Index pairs of tracks and corresponding detections

L-by-2 matrix

Index pairs of tracks and corresponding detections. This value is returned as an L-by-2 matrix of index pairs, with L number of pairs. The first column represents the track index and the second column represents the detection index.

Data Types: uint32

unassignedTracks — Unassigned tracks

P-element vector

Unassigned tracks, returned as a P-element vector. P represents the number of unassigned tracks. Each element represents a track to which no detections are assigned.

Data Types: uint32

unassignedDetections — Unassigned detections

Q-element vector

Unassigned detections, returned as a Q-element vector, where Q represents the number of unassigned detections. Each element represents a detection that was not assigned to any tracks. These detections can begin new tracks.

Data Types: uint32

References

[1] Miller, Matt L., Harold S. Stone, and Ingemar J. Cox, “Optimizing Murty's Ranked Assignment Method,” IEEE Transactions on Aerospace and Electronic Systems, 33(3), 1997.

[2] Munkres, James, “Algorithms for Assignment and Transportation Problems,” Journal of the Society for Industrial and Applied Mathematics, Volume 5, Number 1, March, 1957.

Extended Capabilities

C/C++ Code Generation
Generate C and C++ code using MATLAB® Coder™.

Version History

Introduced in R2012b