Technology Sharing

Deepsort's predecessor is sorting algorithm, and the core of sorting algorithm is Kalman filter algorithm and Hungarian algorithm.

Function of Kalman filter algorithm: The main function of this algorithm is to predict the motion variables at the next moment with a series of current motion variables, but the first detection result is used to initialize the motion variables of Kalman filter.

The function of Hungarian algorithm: Simply put, it is to solve the allocation problem, that is, to allocate a group of detection boxes and the boxes predicted by Kalman, and the boxes predicted by Jeancard find the detection boxes that match them best, so as to achieve the tracking effect.

The sorting workflow is shown in the following figure:

Detection is a frame detected by a target. Trajectory is trajectory information.

The workflow of the whole algorithm is as follows:

(1) Create a corresponding trajectory for the detection result of the first frame. Initialize the motion variables of the Kalman filter, and use the Kalman filter to predict its corresponding frames.

(2) Match the target detection frames with the track prediction frames one by one, and then calculate the cost matrix (calculation method is1-IOU) according to the matching result of iou.

(3) Take all the cost matrices obtained in (2) as the input of Hungarian algorithm, and get the linear matching result. At this time, we get three results. The first is the unmatched tracks, and we directly delete the unmatched tracks. The second is mismatch detection, which we initialize as new Tracks. The third is that the detection frame matches the prediction frame successfully, that is, the previous frame and the next frame are tracked successfully, and the corresponding detection updates its corresponding trajectory variables through Kalman filtering.

(4) Repeat steps (2)-(3) until the video frame ends.

Thirdly, the flow of depth sorting algorithm.

Because the sorting algorithm is still a rough tracking algorithm, when the object is blocked, it is particularly easy to lose the ID. The depth sorting algorithm adds a matching cascade to the sorting algorithm and determines a new trajectory. Trajectory is divided into confirmed state and unconfirmed state, and the newly generated trajectory is unconfirmed state. The track in unconfirmed state must continuously match the detection for a certain number of times (3 times by default) before it can be converted to confirmed state. Tracks in the "Confirmed" state must be deleted for a certain number of consecutive times (default is 30 times) and do not match the detection.

The workflow of the depth sorting algorithm is shown in the following figure:

The workflow of the whole algorithm is as follows:

(1) Creates a corresponding trajectory for the results detected in the first frame. Initialize the motion variables of the Kalman filter, and use the Kalman filter to predict its corresponding frames. The track must be unconfirmed at this time.

(2) Match the target detection frames in this frame with the trajectory prediction frames in the previous frame one by one, and then calculate the cost matrix according to the matching result of IOU (the calculation method is 1-IOU).

(3) Take all the cost matrices obtained in (2) as the input of Hungarian algorithm, and get the linear matching result. At this time, we get three results. The first is the unmatched track, and we directly delete the unmatched track (because this track is in an uncertain state, and if it is in a certain state, it can only be deleted after reaching a certain number of consecutive times (the default is 30 times)); The second is mismatch detection, which we initialize as new Tracks. The third is that the detection frame matches the prediction frame successfully, that is, the previous frame and the next frame are tracked successfully, and the corresponding detection updates its corresponding trajectory variables through Kalman filtering.

(4) Repeat steps (2)-(3) until the confirmed track appears or the video frame ends.

(5) Using Kalman filter to predict the frames corresponding to the confirmed state track and the unconfirmed state track. The confirmed trajectory and the detected frame are matched in cascade (in the past, as long as the trajectory matches, the appearance features and motion information of the detection will be saved every time, and the previous 100 frame is saved by default, and the appearance features and motion information and detection are used for cascade matching, because it is more likely to confirm the trajectory and detect the matching).

(6) There are three possible results after cascade matching. The first is track matching, and the corresponding track variables are updated by Kalman filter. The second and third types are mismatches between detection and tracking. At this time, the previously unconfirmed trajectory and unmatched trajectory are matched with the unmatched detection one by one, and then the cost matrix is calculated by the result of IOU matching (the calculation method is 1-IOU).

(7) Take all the cost matrices obtained in (6) as the input of Hungarian algorithm, and get the linear matching result. At this time, we get three results. The first is the unmatched track, and we directly delete the unmatched track (because this track is in an uncertain state, and if it is in a certain state, it can only be deleted after reaching a certain number of consecutive times (the default is 30 times)); The second is mismatch detection, which we initialize as new Tracks. The third is that the detection frame matches the prediction frame successfully, that is, the previous frame and the next frame are tracked successfully, and the corresponding detection updates its corresponding trajectory variables through Kalman filtering.

(8) Repeat steps (5)-(7) until the video frame ends.