How to use angle in map-matching.

[Rejudge-F]

Hi team,I think angle is an important factor in map matching, how can I use it in osrm. I found transition_probability only rely on const auto d_t = std::abs(network_distance - haversine_distance); but I think the angle between pre-current phantom node and trace coordinates should also be taken into, i modified it slightly(the commented part of the code), want to hear team opinion. I tested about 100 angle-related cases, and the accuracy rate has greatly improved.

// include/engine/map_matching/hidden_markov_model.hpp
struct TransitionAngleLogProbability
{
    double sigma_z;
    double log_sigma_z;

    TransitionAngleLogProbability(const double sigma_z) : sigma_z(sigma_z), log_sigma_z(std::log(sigma_z))
    {
    }

    double operator()(const double distance) const
    {
        return -0.5 * (log_2_pi + (distance / sigma_z) * (distance / sigma_z)) - log_sigma_z;
    }
};

// src/engine/routing_algorithms/map_matching.cpp:222
// compute d_t for this timestamp and the next one
for (const auto s: util::irange<std::size_t>(0UL, prev_viterbi.size())) {
if (prev_pruned[s]) {
    continue;
}

for (const auto s_prime: util::irange<std::size_t>(0UL, current_viterbi.size())) {
    const double emission_pr = emission_log_probabilities[t][s_prime];
    double new_value = prev_viterbi[s] + emission_pr;
    if (current_viterbi[s_prime] > new_value) {
        continue;
    }

    double network_distance =
            getNetworkDistance(engine_working_data,
                               facade,
                               forward_heap,
                               reverse_heap,
                               prev_unbroken_timestamps_list[s].phantom_node,
                               current_timestamps_list[s_prime].phantom_node,
                               weight_upper_bound);

    // get distance diff between loc1/2 and locs/s_prime
    const auto d_t = std::abs(network_distance - haversine_distance);

    // very low probability transition -> prune
    if (d_t >= max_distance_delta) {
        continue;
    }

    const double transition_pr = transition_log_probability(d_t);
    new_value += transition_pr;

//                        calculate angle transition probability
//                        const PhantomNodeWithDistance &pre_phantom_node = prev_unbroken_timestamps_list[s];
//                        const PhantomNodeWithDistance &current_phantom_node = current_timestamps_list[s_prime];
//
//                        FixedLongitude translate_longitude =
//                                prev_coordinate.lon - pre_phantom_node.phantom_node.location.lon;
//                        FixedLatitude translate_latitude =
//                                prev_coordinate.lat - pre_phantom_node.phantom_node.location.lat;
//
//                        double transition_angle = util::coordinate_calculation::computeAngle(
//                                util::Coordinate(current_phantom_node.phantom_node.location.lon + translate_longitude,
//                                                 current_phantom_node.phantom_node.location.lat + translate_latitude),
//                                prev_coordinate, current_coordinate);
//
//                        // norm angle to
//                        transition_angle = transition_angle > 180 ? 360 - transition_angle : transition_angle;
//
//                        const double transition_angle_pr = transition_angle_log_probability(transition_angle);
//                        new_value += transition_angle_pr;

    if (new_value > current_viterbi[s_prime]) {
        current_viterbi[s_prime] = new_value;
        current_parents[s_prime] = std::make_pair(prev_unbroken_timestamp, s);
        current_lengths[s_prime] = network_distance;
        current_pruned[s_prime] = false;
        model.breakage[t] = false;
    }
}
}

[SiarheiFedartsou]

Hey @Rejudge-F Not sure about transition cost, but angles can be used as emission cost in quite straightforward way: usually location providers give you so called bearing and this bearing can be compared against bearing of road in order to add additional factor for snapping.

Why you closed it btw?

[Rejudge-F]

Not sure about transition cost, but angles can be used as emission cost in quite straightforward way: usually location providers give you so called bearing and this bearing can be compared against bearing of road in order to add additional factor for snapping.

Why you closed it btw?

I found that map matching is easily affected by the angle of the local noise trajectory. I was worried that it would be misleading, so I temporarily closed the issue. I am looking for some reasonable ways to use the angle. If I find a more reasonable method, I would like to reopen this issue. I think The angle should help the accuracy of map matching.

[Rejudge-F]

@SiarheiFedartsou Sia By the way, I found that tidy will affect the shape of the trajectory and cause it to match to an incorrect trajectory. I am optimizing tidy by angle.

[SiarheiFedartsou]

@SiarheiFedartsou Sia By the way, I found that tidy will affect the shape of the trajectory and cause it to match to an incorrect trajectory. I am optimizing tidy by angle.

You mean tidy=true argument? Yes, it changes trajectory itself, but it helps in many cases, because otherwise (with tidy=false) you may face issues: e.g. map matching may fail in case of GPS noise on stops(when position slightly moves backwards - it is difficult to resolve by HMM algorithm currently being used).

[Rejudge-F]

@SiarheiFedartsou Sia By the way, I found that tidy will affect the shape of the trajectory and cause it to match to an incorrect trajectory. I am optimizing tidy by angle.

You mean tidy=true argument? Yes, it changes trajectory itself, but it helps in many cases, because otherwise (with tidy=false) you may face issues: e.g. map matching may fail in case of GPS noise on stops(when position slightly moves backwards - it is difficult to resolve by HMM algorithm currently being used).

Yes, I am wondering if it is possible to preserve the shape points of the route through a certain angle threshold demo like this： At present, the shape of the trajectory can be roughly preserved, and most of the noise points can be removed

// Walk over adjacent (coord, ts)-pairs, with rhs being the candidate to discard or keep
        for (std::size_t current = 0, next = 1; next < params.coordinates.size() - 1; ++current, ++next) {
            auto distance_delta = util::coordinate_calculation::greatCircleDistance(
                    params.coordinates[current], params.coordinates[next]);
            running.distance_in_meters += distance_delta;
            const auto over_distance = running.distance_in_meters >= cfg.distance_in_meters;
            const double angle = (next + 1 < params.coordinates.size()) ? util::coordinate_calculation::computeAngle(
                    params.coordinates[current], params.coordinates[next], params.coordinates[next + 1]) : -1;
            const auto valid_angle = angle >= 0 && !(angle >= 170 && angle <= 190);

            if (uses_timestamps) {
                auto duration_delta = params.timestamps[next] - params.timestamps[current];
                running.duration_in_seconds += duration_delta;
                const auto over_duration = running.duration_in_seconds >= cfg.duration_in_seconds;

                if (over_distance && over_duration) {
                    result.tidied_to_original.push_back(next);
                    running = {0., 0}; // reset running distance and time
                } else {
                    result.can_be_removed.set(next, true);
                }
            } else {
                if (over_distance) {
                    result.tidied_to_original.push_back(next);
                    util::Log(logINFO) << "normal: " << std::setprecision(10) << double(int(params.coordinates[next].lat)) / 1e6 << "," << double(int(params.coordinates[next].lon)) / 1e6 << " " << angle << " " << distance_delta;
                    running = {0., 0}; // reset running distance and time
                } else {
                    if (valid_angle && running.distance_in_meters + distance_delta > 2) {
                        util::Log(logINFO) << "add: " << std::setprecision(10) << double(int(params.coordinates[next].lat)) / 1e6 << "," << double(int(params.coordinates[next].lon)) / 1e6 << " " << angle << " " << distance_delta;
                        result.tidied_to_original.push_back(next);
                        running = {0., 0}; // reset running distance and time
                    } else {
                        util::Log(logINFO) << "delete: " << std::setprecision(10) << double(int(params.coordinates[next].lat)) / 1e6 << "," << double(int(params.coordinates[next].lon)) / 1e6 << " " << angle << " " << distance_delta;
                        result.can_be_removed.set(next, true);
                    }
                }
            }
        }

[SiarheiFedartsou]

Hm, may be, but at glance it seems it may have the same issues on stops as tidy=true is supposed to fix(but less rare though).

One more thing how can tidy=true be improved is using speed values usually available from mobile location providers: e.g. we can just filter out all "stop" locations where speed < 1.0 mps - it probably should do the both: preserve trajectory shape and avoid these problems on stops. The downside here is that you have to obtain these speed values from somewhere.

Also can you may be explain what practical problem you are trying to solve this way? I understand that MM is hard problem and there are a lot of things can be improved, but may be your problem can be solved in much easier way?

[Rejudge-F]

I am trying to match the gps track of the mobile terminal to the electronic map, but the track of the mobile terminal will have large deviation and noise points due to some reasons There will be some Angle issues in the details

[github-actions[bot]]

This issue seems to be stale. It will be closed in 30 days if no further activity occurs.