| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | // This file is part of INSTINCT, the INS Toolkit for Integrated | ||
| 2 | // Navigation Concepts and Training by the Institute of Navigation of | ||
| 3 | // the University of Stuttgart, Germany. | ||
| 4 | // | ||
| 5 | // This Source Code Form is subject to the terms of the Mozilla Public | ||
| 6 | // License, v. 2.0. If a copy of the MPL was not distributed with this | ||
| 7 | // file, You can obtain one at https://mozilla.org/MPL/2.0/. | ||
| 8 | |||
| 9 | /// @file PolynomialCycleSlipDetector.hpp | ||
| 10 | /// @brief Polynomial Cycle-slip detection algorithm | ||
| 11 | /// @author T. Topp (topp@ins.uni-stuttgart.de) | ||
| 12 | /// @date 2023-10-30 | ||
| 13 | |||
| 14 | #pragma once | ||
| 15 | |||
| 16 | #include <vector> | ||
| 17 | #include <utility> | ||
| 18 | #include <optional> | ||
| 19 | |||
| 20 | #include "Navigation/GNSS/Core/SatelliteIdentifier.hpp" | ||
| 21 | #include "Navigation/Math/PolynomialRegressor.hpp" | ||
| 22 | #include "Navigation/Time/InsTime.hpp" | ||
| 23 | #include "util/Container/Unordered_map.hpp" | ||
| 24 | #include "util/Container/Pair.hpp" | ||
| 25 | |||
| 26 | #include "internal/gui/widgets/imgui_ex.hpp" | ||
| 27 | #include "internal/gui/widgets/EnumCombo.hpp" | ||
| 28 | |||
| 29 | namespace NAV | ||
| 30 | { | ||
| 31 | |||
| 32 | /// GnssAnalyzer forward declaration | ||
| 33 | class GnssAnalyzer; | ||
| 34 | /// CycleSlipDetector forward declaration | ||
| 35 | class CycleSlipDetector; | ||
| 36 | |||
| 37 | /// Cycle-slip detection result type | ||
| 38 | enum class PolynomialCycleSlipDetectorResult : uint8_t | ||
| 39 | { | ||
| 40 | Disabled, ///< The cycle-slip detector is disabled | ||
| 41 | LessDataThanWindowSize, ///< Less data than the specified window size (cannot predict cycle-slip yet) | ||
| 42 | NoCycleSlip, ///< No cycle-slip found | ||
| 43 | CycleSlip, ///< Cycle-slip found | ||
| 44 | }; | ||
| 45 | |||
| 46 | /// @brief Cycle-slip detection | ||
| 47 | template<typename Key> | ||
| 48 | class PolynomialCycleSlipDetector | ||
| 49 | { | ||
| 50 | public: | ||
| 51 | /// @brief Constructor | ||
| 52 | /// @param[in] windowSize Amount of points to use for the fit (sliding window) | ||
| 53 | /// @param[in] polyDegree Polynomial degree to fit | ||
| 54 | /// @param[in] enabled Whether the detector is enabled | ||
| 55 | 1043 | explicit PolynomialCycleSlipDetector(size_t windowSize, size_t polyDegree, bool enabled = true) | |
| 56 | 1043 | : _enabled(enabled), _windowSize(windowSize), _polyDegree(polyDegree) {} | |
| 57 | |||
| 58 | /// @brief Checks for a cycle slip | ||
| 59 | /// @param[in] key Key of the detector | ||
| 60 | /// @param[in] insTime Time of the measurement | ||
| 61 | /// @param[in] measurementDifference Measurement difference | ||
| 62 | /// @param[in] threshold Threshold to categorize a measurement as cycle slip | ||
| 63 | /// @return Cycle-slip result | ||
| 64 | 190055 | [[nodiscard]] PolynomialCycleSlipDetectorResult checkForCycleSlip(const Key& key, InsTime insTime, double measurementDifference, double threshold) | |
| 65 | { | ||
| 66 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 95031 times.
|
190055 | if (!_enabled) { return PolynomialCycleSlipDetectorResult::Disabled; } |
| 67 |
3/4✓ Branch 1 taken 95031 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 175 times.
✓ Branch 4 taken 94856 times.
|
190055 | if (!_detectors.contains(key)) |
| 68 | { | ||
| 69 |
1/2✓ Branch 1 taken 175 times.
✗ Branch 2 not taken.
|
349 | addMeasurement(key, insTime, measurementDifference); |
| 70 | 349 | return PolynomialCycleSlipDetectorResult::LessDataThanWindowSize; | |
| 71 | } | ||
| 72 | |||
| 73 |
1/2✓ Branch 1 taken 94856 times.
✗ Branch 2 not taken.
|
189706 | const auto& detector = _detectors.at(key); |
| 74 |
3/4✓ Branch 1 taken 94856 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 310 times.
✓ Branch 4 taken 94546 times.
|
189706 | if (!detector.polyReg.windowSizeReached()) |
| 75 | { | ||
| 76 |
1/2✓ Branch 1 taken 310 times.
✗ Branch 2 not taken.
|
616 | addMeasurement(key, insTime, measurementDifference); |
| 77 | 616 | return PolynomialCycleSlipDetectorResult::LessDataThanWindowSize; | |
| 78 | } | ||
| 79 | |||
| 80 |
1/2✓ Branch 1 taken 94546 times.
✗ Branch 2 not taken.
|
189090 | auto polynomial = detector.polyReg.calcPolynomial(); |
| 81 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 94546 times.
|
189090 | if (!polynomial) |
| 82 | { | ||
| 83 | ✗ | addMeasurement(key, insTime, measurementDifference); | |
| 84 | ✗ | return PolynomialCycleSlipDetectorResult::LessDataThanWindowSize; | |
| 85 | } | ||
| 86 |
2/4✓ Branch 2 taken 94546 times.
✗ Branch 3 not taken.
✓ Branch 5 taken 94546 times.
✗ Branch 6 not taken.
|
189090 | auto predictedValue = polynomial->f(calcRelativeTime(insTime, detector)); |
| 87 | |||
| 88 |
2/2✓ Branch 1 taken 1 times.
✓ Branch 2 taken 94545 times.
|
189090 | if (std::abs(measurementDifference - predictedValue) > threshold) |
| 89 | { | ||
| 90 |
2/4✓ Branch 0 taken 1 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 1 times.
✗ Branch 4 not taken.
|
1 | if (_resetAfterCycleSlip) { reset(key); } |
| 91 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | addMeasurement(key, insTime, measurementDifference); |
| 92 | 1 | return PolynomialCycleSlipDetectorResult::CycleSlip; | |
| 93 | } | ||
| 94 |
1/2✓ Branch 1 taken 94545 times.
✗ Branch 2 not taken.
|
189089 | addMeasurement(key, insTime, measurementDifference); |
| 95 | 189089 | return PolynomialCycleSlipDetectorResult::NoCycleSlip; | |
| 96 | 189090 | } | |
| 97 | |||
| 98 | /// Empties the collected polynomials | ||
| 99 | 24 | void clear() | |
| 100 | { | ||
| 101 | 24 | _detectors.clear(); | |
| 102 | 24 | } | |
| 103 | |||
| 104 | /// @brief Reset the polynomial for the given combination | ||
| 105 | /// @param[in] key Key of the detector | ||
| 106 | 1 | void reset(const Key& key) | |
| 107 | { | ||
| 108 |
1/2✓ Branch 1 taken 1 times.
✗ Branch 2 not taken.
|
1 | if (_detectors.contains(key)) |
| 109 | { | ||
| 110 | 1 | _detectors.erase(key); | |
| 111 | } | ||
| 112 | 1 | } | |
| 113 | |||
| 114 | /// @brief Is the cycle-slip detector enabled? | ||
| 115 | ✗ | [[nodiscard]] bool isEnabled() const | |
| 116 | { | ||
| 117 | ✗ | return _enabled; | |
| 118 | } | ||
| 119 | /// @brief Sets the enabled state | ||
| 120 | /// @param[in] enabled Whether to enabled or not | ||
| 121 | 8 | void setEnabled(bool enabled) | |
| 122 | { | ||
| 123 | 8 | _enabled = enabled; | |
| 124 | 8 | } | |
| 125 | |||
| 126 | /// @brief Whether to discard all data after a cycle-slip | ||
| 127 | ✗ | [[nodiscard]] bool resetAfterCycleSlip() const | |
| 128 | { | ||
| 129 | ✗ | return _resetAfterCycleSlip; | |
| 130 | } | ||
| 131 | /// @brief Sets whether to discard all data after a cycle-slip | ||
| 132 | /// @param[in] reset Whether to reset or not | ||
| 133 | ✗ | void setResetAfterCycleSlip(bool reset) | |
| 134 | { | ||
| 135 | ✗ | _resetAfterCycleSlip = reset; | |
| 136 | ✗ | } | |
| 137 | |||
| 138 | /// @brief Get the window size for the polynomial fit | ||
| 139 | ✗ | [[nodiscard]] size_t getWindowSize() const { return _windowSize; } | |
| 140 | /// @brief Sets the amount of points used for the fit (sliding window) | ||
| 141 | /// @param[in] windowSize Amount of points to use for the fit | ||
| 142 | 8 | void setWindowSize(size_t windowSize) | |
| 143 | { | ||
| 144 | 8 | _windowSize = windowSize; | |
| 145 |
1/2✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
|
8 | for (auto& detector : _detectors) |
| 146 | { | ||
| 147 | ✗ | detector.second.polyReg.setWindowSize(windowSize); | |
| 148 | } | ||
| 149 | 8 | } | |
| 150 | |||
| 151 | /// @brief Get the degree of the polynomial which is used for fitting | ||
| 152 | ✗ | [[nodiscard]] size_t getPolynomialDegree() const { return _polyDegree; } | |
| 153 | /// @brief Sets the degree of the polynomial which is used for fitting | ||
| 154 | /// @param[in] polyDegree Polynomial degree to fit | ||
| 155 | 8 | void setPolynomialDegree(size_t polyDegree) | |
| 156 | { | ||
| 157 | 8 | _polyDegree = polyDegree; | |
| 158 |
1/2✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
|
8 | for (auto& detector : _detectors) |
| 159 | { | ||
| 160 | ✗ | detector.second.polyReg.setPolynomialDegree(polyDegree); | |
| 161 | } | ||
| 162 | 8 | } | |
| 163 | |||
| 164 | /// Strategies for fitting | ||
| 165 | using Strategy = PolynomialRegressor<>::Strategy; | ||
| 166 | |||
| 167 | /// @brief Get the strategy used for fitting | ||
| 168 | ✗ | [[nodiscard]] Strategy getFitStrategy() const { return _strategy; } | |
| 169 | /// @brief Sets the strategy used for fitting | ||
| 170 | /// @param[in] strategy Strategy for fitting | ||
| 171 | 8 | void setFitStrategy(Strategy strategy) | |
| 172 | { | ||
| 173 | 8 | _strategy = strategy; | |
| 174 |
1/2✗ Branch 5 not taken.
✓ Branch 6 taken 4 times.
|
8 | for (auto& detector : _detectors) |
| 175 | { | ||
| 176 | ✗ | detector.second.polyReg.setStrategy(strategy); | |
| 177 | } | ||
| 178 | 8 | } | |
| 179 | |||
| 180 | /// @brief Get the amount of data collected | ||
| 181 | /// @param[in] key Key of the detector | ||
| 182 | [[nodiscard]] std::optional<size_t> getDataSize(const Key& key) const | ||
| 183 | { | ||
| 184 | if (!_detectors.contains(key)) { return {}; } | ||
| 185 | |||
| 186 | return _detectors.at(key).polyReg.data().size(); | ||
| 187 | } | ||
| 188 | |||
| 189 | private: | ||
| 190 | /// @brief Signal Detector struct | ||
| 191 | struct SignalDetector | ||
| 192 | { | ||
| 193 | /// @brief Constructor | ||
| 194 | /// @param[in] startTime Time when the first message for this detector was received | ||
| 195 | /// @param[in] windowSize Window size for the sliding window | ||
| 196 | /// @param[in] polyDegree Polynomial degree to fit | ||
| 197 | /// @param[in] strategy Strategy for fitting | ||
| 198 | 190055 | SignalDetector(InsTime startTime, size_t windowSize, size_t polyDegree, Strategy strategy) | |
| 199 | 190055 | : startTime(startTime), polyReg(polyDegree, windowSize, strategy) {} | |
| 200 | |||
| 201 | InsTime startTime; ///< Time when the first message for this detector was received | ||
| 202 | PolynomialRegressor<double> polyReg; ///< Polynomial Regressor | ||
| 203 | }; | ||
| 204 | |||
| 205 | bool _enabled = true; ///< Whether the cycle-slip detector is enabled | ||
| 206 | bool _resetAfterCycleSlip = true; ///< Whether to discard all data after a cycle-slip | ||
| 207 | size_t _windowSize; ///< Window size for the sliding window | ||
| 208 | size_t _polyDegree = 2; ///< Polynomial degree to fit | ||
| 209 | Strategy _strategy = Strategy::HouseholderQR; ///< Strategy used for fitting | ||
| 210 | unordered_map<Key, SignalDetector> _detectors; ///< Detectors, one for each key | ||
| 211 | |||
| 212 | /// @brief Calculate the relative time to the start time of the detector | ||
| 213 | /// @param[in] insTime Time of the measurement | ||
| 214 | /// @param[in] detector Detector to use | ||
| 215 | 379145 | [[nodiscard]] static double calcRelativeTime(const InsTime& insTime, const SignalDetector& detector) | |
| 216 | { | ||
| 217 |
1/2✓ Branch 1 taken 189577 times.
✗ Branch 2 not taken.
|
379145 | return static_cast<double>((insTime - detector.startTime).count()); |
| 218 | } | ||
| 219 | /// @brief Calculate the relative time to the start time of the detector | ||
| 220 | /// @param[in] key Key of the detector | ||
| 221 | /// @param[in] insTime Time of the measurement | ||
| 222 | ✗ | [[nodiscard]] std::optional<double> calcRelativeTime(const Key& key, const InsTime& insTime) const | |
| 223 | { | ||
| 224 | ✗ | if (!_detectors.contains(key)) { return {}; } | |
| 225 | |||
| 226 | ✗ | return calcRelativeTime(insTime, _detectors.at(key)); | |
| 227 | } | ||
| 228 | |||
| 229 | /// @brief Predicts a value from the collected data and polynomial fit | ||
| 230 | /// @param[in] key Key of the detector | ||
| 231 | /// @param[in] insTime Time of the measurement | ||
| 232 | ✗ | [[nodiscard]] std::optional<double> predictValue(const Key& key, const InsTime& insTime) const | |
| 233 | { | ||
| 234 | ✗ | if (!_detectors.contains(key)) { return {}; } | |
| 235 | |||
| 236 | ✗ | const auto& detector = _detectors.at(key); | |
| 237 | |||
| 238 | ✗ | auto polynomial = detector.polyReg.calcPolynomial(); | |
| 239 | ✗ | if (!polynomial) { return {}; } | |
| 240 | ✗ | return polynomial->f(calcRelativeTime(insTime, detector)); | |
| 241 | ✗ | } | |
| 242 | |||
| 243 | /// @brief Calculates the polynomial from the collected data | ||
| 244 | /// @param[in] key Key of the detector | ||
| 245 | ✗ | [[nodiscard]] std::optional<Polynomial<double>> calcPolynomial(const Key& key) const | |
| 246 | { | ||
| 247 | ✗ | if (!_detectors.contains(key)) { return {}; } | |
| 248 | |||
| 249 | ✗ | return _detectors.at(key).polyReg.calcPolynomial(); | |
| 250 | } | ||
| 251 | |||
| 252 | /// @brief Add a measurement to the polynomial fit | ||
| 253 | /// @param[in] key Key of the detector | ||
| 254 | /// @param[in] insTime Time of the measurement | ||
| 255 | /// @param[in] measurementDifference Measurement difference | ||
| 256 | 190055 | void addMeasurement(const Key& key, InsTime insTime, double measurementDifference) | |
| 257 | { | ||
| 258 |
1/2✗ Branch 0 not taken.
✓ Branch 1 taken 95031 times.
|
190055 | if (!_enabled) { return; } |
| 259 |
2/7✓ Branch 1 taken 95031 times.
✗ Branch 2 not taken.
✗ Branch 4 not taken.
✓ Branch 5 taken 95031 times.
✗ Branch 6 not taken.
✗ Branch 7 not taken.
✗ Branch 8 not taken.
|
190055 | auto& detector = _detectors.insert({ key, SignalDetector(insTime, _windowSize, _polyDegree, _strategy) }).first->second; |
| 260 | |||
| 261 |
2/4✓ Branch 1 taken 95031 times.
✗ Branch 2 not taken.
✓ Branch 4 taken 95031 times.
✗ Branch 5 not taken.
|
190055 | detector.polyReg.push_back(calcRelativeTime(insTime, detector), measurementDifference); |
| 262 | } | ||
| 263 | |||
| 264 | friend class GnssAnalyzer; | ||
| 265 | friend class CycleSlipDetector; | ||
| 266 | }; | ||
| 267 | |||
| 268 | /// @brief Shows a GUI for advanced configuration of the PolynomialCycleSlipDetector | ||
| 269 | /// @param[in] label Label to show beside the combo box. This has to be a unique id for ImGui. | ||
| 270 | /// @param[in] polynomialCycleSlipDetector Reference to the cycle-slip detector to configure | ||
| 271 | /// @param[in] width Width of the widget | ||
| 272 | template<typename Key> | ||
| 273 | ✗ | bool PolynomialCycleSlipDetectorGui(const char* label, PolynomialCycleSlipDetector<Key>& polynomialCycleSlipDetector, float width = 0.0F) | |
| 274 | { | ||
| 275 | ✗ | bool changed = false; | |
| 276 | |||
| 277 | ✗ | bool enabled = polynomialCycleSlipDetector.isEnabled(); | |
| 278 | ✗ | if (ImGui::Checkbox(fmt::format("Enabled##{}", label).c_str(), &enabled)) | |
| 279 | { | ||
| 280 | ✗ | changed = true; | |
| 281 | ✗ | polynomialCycleSlipDetector.setEnabled(enabled); | |
| 282 | } | ||
| 283 | |||
| 284 | ✗ | if (!enabled) { ImGui::BeginDisabled(); } | |
| 285 | |||
| 286 | ✗ | ImGui::SetNextItemWidth(width); | |
| 287 | ✗ | if (int windowSize = static_cast<int>(polynomialCycleSlipDetector.getWindowSize()); | |
| 288 | ✗ | ImGui::InputIntL(fmt::format("Window size##{}", label).c_str(), &windowSize, | |
| 289 | ✗ | std::max(1, static_cast<int>(polynomialCycleSlipDetector.getPolynomialDegree()) + 1))) | |
| 290 | { | ||
| 291 | ✗ | changed = true; | |
| 292 | ✗ | polynomialCycleSlipDetector.setWindowSize(static_cast<size_t>(windowSize)); | |
| 293 | } | ||
| 294 | |||
| 295 | ✗ | ImGui::SetNextItemWidth(width); | |
| 296 | ✗ | if (int polyDegree = static_cast<int>(polynomialCycleSlipDetector.getPolynomialDegree()); | |
| 297 | ✗ | ImGui::InputIntL(fmt::format("Polynomial Degree##{}", label).c_str(), &polyDegree, | |
| 298 | ✗ | 0, std::min(static_cast<int>(polynomialCycleSlipDetector.getWindowSize()) - 1, std::numeric_limits<int>::max()))) | |
| 299 | { | ||
| 300 | ✗ | changed = true; | |
| 301 | ✗ | polynomialCycleSlipDetector.setPolynomialDegree(static_cast<size_t>(polyDegree)); | |
| 302 | } | ||
| 303 | |||
| 304 | ✗ | ImGui::SetNextItemWidth(width); | |
| 305 | ✗ | if (auto strategy = polynomialCycleSlipDetector.getFitStrategy(); | |
| 306 | ✗ | gui::widgets::EnumCombo(fmt::format("Strategy##{}", label).c_str(), strategy)) | |
| 307 | { | ||
| 308 | ✗ | changed = true; | |
| 309 | ✗ | polynomialCycleSlipDetector.setFitStrategy(strategy); | |
| 310 | } | ||
| 311 | ✗ | if (auto resetAfterCycleSlip = polynomialCycleSlipDetector.resetAfterCycleSlip(); | |
| 312 | ✗ | ImGui::Checkbox(fmt::format("Reset after cycle-slip##{}", label).c_str(), &resetAfterCycleSlip)) | |
| 313 | { | ||
| 314 | ✗ | changed = true; | |
| 315 | ✗ | polynomialCycleSlipDetector.setResetAfterCycleSlip(resetAfterCycleSlip); | |
| 316 | } | ||
| 317 | |||
| 318 | ✗ | if (!enabled) { ImGui::EndDisabled(); } | |
| 319 | |||
| 320 | ✗ | return changed; | |
| 321 | } | ||
| 322 | |||
| 323 | /// @brief Write info to a json object | ||
| 324 | /// @param[out] j Json output | ||
| 325 | /// @param[in] data Object to read info from | ||
| 326 | template<typename Key> | ||
| 327 | ✗ | void to_json(json& j, const PolynomialCycleSlipDetector<Key>& data) | |
| 328 | { | ||
| 329 | ✗ | j = json{ | |
| 330 | ✗ | { "enabled", data.isEnabled() }, | |
| 331 | ✗ | { "windowSize", data.getWindowSize() }, | |
| 332 | ✗ | { "polynomialDegree", data.getPolynomialDegree() }, | |
| 333 | ✗ | { "strategy", data.getFitStrategy() }, | |
| 334 | ✗ | { "resetAfterCycleSlip", data.resetAfterCycleSlip() }, | |
| 335 | }; | ||
| 336 | ✗ | } | |
| 337 | /// @brief Read info from a json object | ||
| 338 | /// @param[in] j Json variable to read info from | ||
| 339 | /// @param[out] data Output object | ||
| 340 | template<typename Key> | ||
| 341 | 8 | void from_json(const json& j, PolynomialCycleSlipDetector<Key>& data) | |
| 342 | { | ||
| 343 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
8 | if (j.contains("enabled")) |
| 344 | { | ||
| 345 | 8 | auto enabled = j.at("enabled").get<bool>(); | |
| 346 | 8 | data.setEnabled(enabled); | |
| 347 | } | ||
| 348 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
8 | if (j.contains("windowSize")) |
| 349 | { | ||
| 350 | 8 | auto windowSize = j.at("windowSize").get<size_t>(); | |
| 351 | 8 | data.setWindowSize(windowSize); | |
| 352 | } | ||
| 353 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
8 | if (j.contains("polynomialDegree")) |
| 354 | { | ||
| 355 | 8 | auto polynomialDegree = j.at("polynomialDegree").get<size_t>(); | |
| 356 | 8 | data.setPolynomialDegree(polynomialDegree); | |
| 357 | } | ||
| 358 |
1/2✓ Branch 1 taken 4 times.
✗ Branch 2 not taken.
|
8 | if (j.contains("strategy")) |
| 359 | { | ||
| 360 | 8 | auto strategy = j.at("strategy").get<size_t>(); | |
| 361 | 8 | data.setFitStrategy(static_cast<typename PolynomialCycleSlipDetector<Key>::Strategy>(strategy)); | |
| 362 | } | ||
| 363 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 4 times.
|
8 | if (j.contains("resetAfterCycleSlip")) |
| 364 | { | ||
| 365 | ✗ | auto reset = j.at("resetAfterCycleSlip").get<bool>(); | |
| 366 | ✗ | data.setResetAfterCycleSlip(reset); | |
| 367 | } | ||
| 368 | 8 | } | |
| 369 | |||
| 370 | } // namespace NAV | ||
| 371 |