OpenShot Library | libopenshot  0.3.3
sort.cpp
Go to the documentation of this file.
1 // © OpenShot Studios, LLC
2 //
3 // SPDX-License-Identifier: LGPL-3.0-or-later
4 
5 #include "sort.hpp"
6 
7 using namespace std;
8 
9 // Constructor
10 SortTracker::SortTracker(int max_age, int min_hits)
11 {
12  _min_hits = min_hits;
13  _max_age = max_age;
14  alive_tracker = true;
15 }
16 
17 // Computes IOU between two bounding boxes
18 double SortTracker::GetIOU(cv::Rect_<float> bb_test, cv::Rect_<float> bb_gt)
19 {
20  float in = (bb_test & bb_gt).area();
21  float un = bb_test.area() + bb_gt.area() - in;
22 
23  if (un < DBL_EPSILON)
24  return 0;
25 
26  return (double)(in / un);
27 }
28 
29 // Computes centroid distance between two bounding boxes
31  cv::Rect_<float> bb_test,
32  cv::Rect_<float> bb_gt)
33 {
34  float bb_test_centroid_x = (bb_test.x + bb_test.width / 2);
35  float bb_test_centroid_y = (bb_test.y + bb_test.height / 2);
36 
37  float bb_gt_centroid_x = (bb_gt.x + bb_gt.width / 2);
38  float bb_gt_centroid_y = (bb_gt.y + bb_gt.height / 2);
39 
40  double distance = (double)sqrt(pow(bb_gt_centroid_x - bb_test_centroid_x, 2) + pow(bb_gt_centroid_y - bb_test_centroid_y, 2));
41 
42  return distance;
43 }
44 
45 void SortTracker::update(vector<cv::Rect> detections_cv, int frame_count, double image_diagonal, std::vector<float> confidences, std::vector<int> classIds)
46 {
47  vector<TrackingBox> detections;
48  if (trackers.size() == 0) // the first frame met
49  {
50  alive_tracker = false;
51  // initialize kalman trackers using first detections.
52  for (unsigned int i = 0; i < detections_cv.size(); i++)
53  {
54  TrackingBox tb;
55 
56  tb.box = cv::Rect_<float>(detections_cv[i]);
57  tb.classId = classIds[i];
58  tb.confidence = confidences[i];
59  detections.push_back(tb);
60 
61  KalmanTracker trk = KalmanTracker(detections[i].box, detections[i].confidence, detections[i].classId, i);
62  trackers.push_back(trk);
63  }
64  return;
65  }
66  else
67  {
68  for (unsigned int i = 0; i < detections_cv.size(); i++)
69  {
70  TrackingBox tb;
71  tb.box = cv::Rect_<float>(detections_cv[i]);
72  tb.classId = classIds[i];
73  tb.confidence = confidences[i];
74  detections.push_back(tb);
75  }
76  for (auto it = frameTrackingResult.begin(); it != frameTrackingResult.end(); it++)
77  {
78  int frame_age = frame_count - it->frame;
79  if (frame_age >= _max_age || frame_age < 0)
80  {
81  dead_trackers_id.push_back(it->id);
82  }
83  }
84  }
85 
87  // 3.1. get predicted locations from existing trackers.
88  predictedBoxes.clear();
89  for (unsigned int i = 0; i < trackers.size();)
90  {
91  cv::Rect_<float> pBox = trackers[i].predict();
92  if (pBox.x >= 0 && pBox.y >= 0)
93  {
94  predictedBoxes.push_back(pBox);
95  i++;
96  continue;
97  }
98  trackers.erase(trackers.begin() + i);
99  }
100 
101  trkNum = predictedBoxes.size();
102  detNum = detections.size();
103 
104  centroid_dist_matrix.clear();
105  centroid_dist_matrix.resize(trkNum, vector<double>(detNum, 0));
106 
107  for (unsigned int i = 0; i < trkNum; i++) // compute iou matrix as a distance matrix
108  {
109  for (unsigned int j = 0; j < detNum; j++)
110  {
111  // use 1-iou because the hungarian algorithm computes a minimum-cost assignment.
112  double distance = SortTracker::GetCentroidsDistance(predictedBoxes[i], detections[j].box) / image_diagonal;
113  centroid_dist_matrix[i][j] = distance;
114  }
115  }
116 
117  HungarianAlgorithm HungAlgo;
118  assignment.clear();
119  HungAlgo.Solve(centroid_dist_matrix, assignment);
120  // find matches, unmatched_detections and unmatched_predictions
121  unmatchedTrajectories.clear();
122  unmatchedDetections.clear();
123  allItems.clear();
124  matchedItems.clear();
125 
126  if (detNum > trkNum) // there are unmatched detections
127  {
128  for (unsigned int n = 0; n < detNum; n++)
129  allItems.insert(n);
130 
131  for (unsigned int i = 0; i < trkNum; ++i)
132  matchedItems.insert(assignment[i]);
133 
134  set_difference(allItems.begin(), allItems.end(),
135  matchedItems.begin(), matchedItems.end(),
136  insert_iterator<set<int>>(unmatchedDetections, unmatchedDetections.begin()));
137  }
138  else if (detNum < trkNum) // there are unmatched trajectory/predictions
139  {
140  for (unsigned int i = 0; i < trkNum; ++i)
141  if (assignment[i] == -1) // unassigned label will be set as -1 in the assignment algorithm
142  unmatchedTrajectories.insert(i);
143  }
144  else
145  ;
146 
147  // filter out matched with low IOU
148  matchedPairs.clear();
149  for (unsigned int i = 0; i < trkNum; ++i)
150  {
151  if (assignment[i] == -1) // pass over invalid values
152  continue;
153  if (centroid_dist_matrix[i][assignment[i]] > max_centroid_dist_norm)
154  {
155  unmatchedTrajectories.insert(i);
156  unmatchedDetections.insert(assignment[i]);
157  }
158  else
159  matchedPairs.push_back(cv::Point(i, assignment[i]));
160  }
161 
162  for (unsigned int i = 0; i < matchedPairs.size(); i++)
163  {
164  int trkIdx = matchedPairs[i].x;
165  int detIdx = matchedPairs[i].y;
166  trackers[trkIdx].update(detections[detIdx].box);
167  trackers[trkIdx].classId = detections[detIdx].classId;
168  trackers[trkIdx].confidence = detections[detIdx].confidence;
169  }
170 
171  // create and initialise new trackers for unmatched detections
172  for (auto umd : unmatchedDetections)
173  {
174  KalmanTracker tracker = KalmanTracker(detections[umd].box, detections[umd].confidence, detections[umd].classId, umd);
175  trackers.push_back(tracker);
176  }
177 
178  for (auto it2 = dead_trackers_id.begin(); it2 != dead_trackers_id.end(); it2++)
179  {
180  for (unsigned int i = 0; i < trackers.size();)
181  {
182  if (trackers[i].m_id == (*it2))
183  {
184  trackers.erase(trackers.begin() + i);
185  continue;
186  }
187  i++;
188  }
189  }
190 
191  // get trackers' output
192  frameTrackingResult.clear();
193  for (unsigned int i = 0; i < trackers.size();)
194  {
195  if ((trackers[i].m_time_since_update < 1 && trackers[i].m_hit_streak >= _min_hits) || frame_count <= _min_hits)
196  {
197  alive_tracker = true;
198  TrackingBox res;
199  res.box = trackers[i].get_state();
200  res.id = trackers[i].m_id;
201  res.frame = frame_count;
202  res.classId = trackers[i].classId;
203  res.confidence = trackers[i].confidence;
204  frameTrackingResult.push_back(res);
205  }
206 
207  // remove dead tracklet
208  if (trackers[i].m_time_since_update >= _max_age)
209  {
210  trackers.erase(trackers.begin() + i);
211  continue;
212  }
213  i++;
214  }
215 }
TrackingBox::confidence
float confidence
Definition: sort.hpp:24
HungarianAlgorithm
Definition: Hungarian.h:22
TrackingBox
Definition: sort.hpp:21
TrackingBox::frame
int frame
Definition: sort.hpp:23
SortTracker::GetCentroidsDistance
double GetCentroidsDistance(cv::Rect_< float > bb_test, cv::Rect_< float > bb_gt)
Definition: sort.cpp:30
KalmanTracker
This class represents the internel state of individual tracked objects observed as bounding box.
Definition: KalmanTracker.h:18
SortTracker::SortTracker
SortTracker(int max_age=7, int min_hits=2)
Definition: sort.cpp:10
TrackingBox::classId
int classId
Definition: sort.hpp:25
SortTracker::GetIOU
double GetIOU(cv::Rect_< float > bb_test, cv::Rect_< float > bb_gt)
Definition: sort.cpp:18
TrackingBox::box
cv::Rect_< float > box
Definition: sort.hpp:27
TrackingBox::id
int id
Definition: sort.hpp:26
HungarianAlgorithm::Solve
double Solve(std::vector< std::vector< double >> &DistMatrix, std::vector< int > &Assignment)
Definition: Hungarian.cpp:26
sort.hpp
SortTracker::update
void update(std::vector< cv::Rect > detection, int frame_count, double image_diagonal, std::vector< float > confidences, std::vector< int > classIds)
Definition: sort.cpp:45