Map-matching without losing the additional points' data

[MHarbi]

Hello Sebastian, Thanks for your great contribution on this project! I have done offline map-matching for some tracking GPS points and got a great result. The final result indicates the accurate trajectory in terms of a sequence of points that are much less that the number of the sample. In my project, it is important to preserve some data associated with the original points, including time and speed. Is there any way to snap the points on streets with its associated data?

This is my code:

Matcher matcher = new Matcher(map, new Dijkstra<Road, RoadPoint>(), 
                            new TimePriority(),
                            new Geography());

String json = new String(
      Files.readAllBytes(
              Paths.get(jsonFile)),
              Charset.defaultCharset());

JSONArray jsonsamples = new JSONArray(json);
List<MatcherSample> samples = new LinkedList<>();

for (int i = 0; i < jsonsamples.length(); ++i) {
  samples.add(new MatcherSample(jsonsamples.getJSONObject(i)));
}

MatcherKState state = matcher.mmatch(samples, minDistance, minInterval);

OutputFormatter output = new GeoJSONOutputFormatter();
PrintWriter out = new PrintWriter("./matching.json");
out.println(output.format(json, state));
out.close();

System.out.println("Samples: " + samples.size());
System.out.println("States:" + state.sequence().size());

[jongiddy]

The method state.samples() returns the sample points that match the candidate points. In the above code, you should be able to add state.samples().size() and get the same number as state.sequence().size().

To preserve the additional data about time and speed, create a subclass of MatcherSample and add the data as extra fields. Pass a list of this subclass to mmatch. The list returned by state.samples() returns instances from the input samples, so these can be downcast to the subclass to retrieve the additional data.

If you need to reinsert the original points that were dropped, add a candidate field to the subclass and leave it as null. Iterate through the state.samples() and state.sequence() lists together, setting each sample candidate field to the next item from the sequence list. Since the objects in the original sample list and the objects returned by state.samples() are the same objects, the original sample list should then have all the sample points, with some having non-null map-matched points.

[smattheis]

A short addition: minDistance and minInterval are the main parameters to influence dropping samples and serve as a minimal mechanism to do data cleaning. Setting both values to zero avoids dropping mostly but may result in distortions if samples have high frequency but also measurement errors such that samples oscillate around positions and "confuse" the map matching algorithm. In that sense, after setting both parameters to zero some samples will still be dropped if positions of two consecutive samples are in opposite direction as the rest of the trace and distance is within GPS standard error. This avoids unnecessary detours in the matched result if position measurements oscillate around a position although the object actually just stands at the same position for some time.

[MHarbi]

@jongiddy Thanks for your quick response. I have tried applying you suggestion, which is creating a subclass of MatcherSample and adding those additional fields, but it failed; it said:

incompatible types: java.util.List cannot be converted to java.util.List

Also, could you explain your idea about reinserting the dropped points in more details? I didn't get that.

[MHarbi]

@smattheis I appreciate your reply. My data has tracking GPS points for cars in each 10-15 secs. Those cars stationed in a garage for a period of time, which cause noisy in the data. I have tuned those parameters to zero to avoid dropping some points, but I ended up having inaccurate trajectory due to the noisy data. My objective is to map each coordinate to its road without dropping any points. What do suggest?

[jongiddy]

incompatible types: java.util.List cannot be converted to java.util.List

Sorry, my original description was ambiguous. Your list must be type java.util.List<com.bmwcarit.barefoot.matcher.MatcherSample>.

So your code could look something like:

class EntendedMatcherSample extends MatcherSample {
    public double speed;
    ExtendedMatcherSample(JSONObject json) {
        super(json);
        speed = json.getDouble("speed");
    }
}

List<MatcherSample> samples = new LinkedList<>();

for (int i = 0; i < jsonsamples.length(); ++i) {
  samples.add(new ExtendedMatcherSample(jsonsamples.getJSONObject(i)));
}

MatcherKState state = matcher.mmatch(samples, minDistance, minInterval);

List<MatcherSample> outputSamples = state.samples();
for (MatcherSample s: state.samples()) {
    // Downcast required to get additional data
    ExtendedMatcherSample ext = (ExtendedMatcherSample)s; 
    System.out.println("Speed: " + ext.speed);
}

[jongiddy]

Also, could you explain your idea about reinserting the dropped points in more details?

Let me try to change the code above to demonstrate it. Note that I have never actually done this. In my experience, points that are dropped are anomalies that don't provide useful information.

class EntendedMatcherSample extends MatcherSample {
    public MatcherCandidate candidate;
    ExtendedMatcherSample(JSONObject json) {
        super(json);
    }
}

List<MatcherSample> samples = new LinkedList<>();

for (int i = 0; i < jsonsamples.length(); ++i) {
  samples.add(new ExtendedMatcherSample(jsonsamples.getJSONObject(i)));
}

MatcherKState state = matcher.mmatch(samples, minDistance, minInterval);

List<MatcherCandidate> candidates = state.sequence();
if (candidates != null) {
    Iterator<MatcherCandidate> cs = candidates.iterator();
    Iterator<MatcherSample> ss = state.samples().iterator();
    while (cs.hasNext() && ss.hasNext()) {
        ExtendedMatcherSample ext = (ExtendedMatcherSample)ss.next();
        // add candidate to a matched ExtendedMatcherSample instance
        ext.candidate = cs.next();
    }
    // at this point, both iterators should be exhausted and all matched samples have
    // their candidate field populated with the matched candidate
}
// Now we can iterate through the original samples list, which has all the samples, 
// some of which have matched points - for example this code should print a line
// like ...MMMM.MMM..MMMM to indicate matched and non-matched points.
for (ExtendedMatcherSample s: samples) {
    if (s.candidate != null) {
        System.out.print('M');
    } else {
        System.out.print('.');
    }
    System.out.println();
}

[smattheis]

I have tuned those parameters to zero to avoid dropping some points, but I ended up having inaccurate trajectory due to the noisy data. My objective is to map each coordinate to its road without dropping any points.

I see the following solutions:

The simple solution: First, I think you should switch back to the parameters you used before because it does what it should, i.e., cleaning data to increase robustness of the map matching. This is, of course, a down-sampling of your data because it eliminates noise with an extremely simple but still valid heuristic that eliminates measurements that would imply some measurement resolution that is below the standard error of GPS and would require more complex solutions (see below). After that, you could then either use the down-sampled data or match the original data by up-sampling the map matched subset of the samples and align it with your original data. To do that, you could follow the approach that Jon suggests and assign the samples a consecutive range of identifiers before the matching to see which sample has been matched and which was dropped. The assumption is then that dropped samples are "noise" which means you assume that the position of your object hasn't changed since the last matched sample such that you transfer the position from each matched sample to all subsequent samples that have been dropped.

The difficult solution: In principle, we can determine positions with higher resolution than GPS error as, e.g., multiple measurements of the same position can be aggregated to a single more accurate position measurement. However, here it's different because we have no evidence that the object stays at the same position but objects move such that we would need to solve an optimization problem that incorporates a set of measurements and a motion model. In the end, this is a different map matching approach. The technical solution may use methods for solving spring-mass-models, as in graph-based SLAM. However, that's for now beyond the scope of the library.

[MHarbi]

@jongiddy @smattheis Thanks for your suggestion. I really appreciate your feedback.