Mercurial Hosting > traffic-intelligence

annotate trajectorymanagement/src/DTWMetric.h @ 1250:77fbd0e2ba7d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
dltrack works with moving average filtering
author Nicolas Saunier <nicolas.saunier@polymtl.ca>
date Thu, 15 Feb 2024 22:04:35 -0500
parents e1e7acef8eab
children
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
1159
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
1 #ifndef DTWMETRIC_H_
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
2 #define DTWMETRIC_H_
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
3
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
4 #include "Metric.h"
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
5
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
6 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
7 * DTWMetric class.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
8 *
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
9 * The Dynamic Time Warping metric measures the similarity between two trajectories.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
10 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
11 template<typename Tr, typename To>
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
12 class DTWMetric: public Metric<Tr, To>
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
13 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
14 public:
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
15 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
16 * Constructor.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
17 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
18 DTWMetric()
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
19 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
20 maxDTWValue = (std::numeric_limits<To>::max()) / To(2);
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
21 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
22
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
23 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
24 * Set maximum value that occurs during the calculation process.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
25 *
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
26 * @param[in] maxDTWValue maximum value
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
27 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
28 bool setMaxDTWValue(To maxDTWValue)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
29 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
30 if (maxDTWValue >= 0.0)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
31 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
32 this->maxDTWValue = maxDTWValue;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
33 return true;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
34 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
35 return false;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
36 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
37
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
38 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
39 * Set maximum value that occurs during the calculation process.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
40 *
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
41 * @param[in] imgSize image size
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
42 * @param[in] eps machine epsilon
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
43 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
44 bool setMaxDTWValue(CvSize &imgSize, double eps)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
45 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
46 if (imgSize.width > 0 && imgSize.height > 0 && eps > 0)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
47 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
48 cv::Point_<int> p(imgSize.width, imgSize.height);
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
49 maxDTWValue = std::numeric_limits<To>::max() - norm(p) - eps;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
50 return true;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
51 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
52 return false;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
53 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
54
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
55 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
56 * Compute similarity between two trajectories.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
57 *
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
58 * @param[in] a input trajectory
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
59 * @param[in] b input trajectory
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
60 * @param[out] result distance between two trajectories.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
61 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
62 void distance(const Trajectory<Tr> *a, const Trajectory<Tr> *b, To &result, unsigned int nbOfPoints = std::numeric_limits<unsigned int>::max())
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
63 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
64 To DTW[a->size() + 1][b->size() + 1];
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
65
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
66 { //initialization
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
67 for (unsigned int i = 0; i <= a->size(); ++i)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
68 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
69 DTW[i][0] = maxDTWValue;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
70 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
71
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
72 for (unsigned int j = 0; j <= b->size(); ++j)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
73 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
74 DTW[0][j] = maxDTWValue;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
75 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
76
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
77 DTW[0][0] = 0.0;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
78 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
79
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
80 { //algorithm
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
81 for (unsigned int i = 1; i <= a->size(); ++i)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
82 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
83 for (unsigned int j = 1; j <= b->size(); ++j)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
84 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
85 To smallest = min(DTW[i - 1][j], DTW[i][j - 1], DTW[i - 1][j - 1]);
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
86 cv::Point3_<typeof(static_cast<Tr>(a->getPoint(i-1)).x)> p(a->getPoint(i - 1) - b->getPoint(j - 1));
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
87 To distance = std::sqrt(std::pow(p.x, 2) + std::pow(p.y, 2) + std::pow(p.z, 2));
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
88 DTW[i][j] = std::min(smallest + distance, maxDTWValue);
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
89 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
90 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
91 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
92
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
93 result = DTW[a->size()][b->size()];
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
94 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
95
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
96 private:
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
97 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
98 * Maximum value that occurs during the calculation process.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
99 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
100 To maxDTWValue;
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
101
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
102 /**
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
103 * Compute the minimum of \a a, \a b and \c c.
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
104 *
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
105 * @param[in] a input parameter
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
106 * @param[in] b input parameter
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
107 * @param[in] c input parameter
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
108 */
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
109 To min(To a, To b, To c)
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
110 {
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
111 return std::min(std::min(a, b), c);
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
112 }
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
113 };
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
114
e1e7acef8eab moved trajectory management library into Traffic Intelligence
Nicolas Saunier <nicolas.saunier@polymtl.ca>
parents:
diff changeset
115 #endif /* DTWMETRIC_H_ */