Matching data from different coordinate systems.

[KrasnovPavel]

Hello!

Lets say that I have some track of 2D points measured in meters from some origin, and map graph measured in latitude and longitude. Is there some way to match them without knowing origin's latitude, longitude and azimuth?

May be this matcher is capable of it or you can point to some method. This wolud be very helpfull.

Thanks.

[addy90]

Hi @KrasnovPavel,

Can you provide an example of the data you describe?

In theory, any graph with 2D coordinates and any 2D points can be mapped. This tool allows for both cartesian as well as geographic coordinate systems. Internally the tool works with meters (as this is the standard SI unit). Technically, no SRS is needed, when both data is in cartesian coordinates based on meters...

But there is some advanced transformation between spatial reference systems possible, see help.txt (for example --network-transform-srs). You can for example have the graph in WGS84 longitude latitude and the points in UTM10N and you can convert the points to WGS84 or the graph to UTM10N so both are in the same system. Then the tool works in principal, of course not every combination is tested yet. The SRS conversion is based on PROJ4 internally. So you need PROJ4 strings, see for example on https://epsg.io/4326 for WGS84 the PROJ4 string is '+proj=longlat +datum=WGS84 +no_defs'. So if you have origin data in 2D coordinates in meters, you need at least find out which spatial reference system they come from, then you can let them convert by the tool.

Maybe if you can provide a data example I can tell you the exact CLI command line that is needed - or if not possible maybe find another solution. But in theory, yes, mixing different reference systems is possible when you convert one or both to the same with the given arguments the tool provides.

Also when both are in cartesian system, cartesian distance calculations are used, when both are in geographic coordinate system, geographic distance calculations based on Andoyer are used (default boost::geometry methods).

[KrasnovPavel]

Here is example of track data (x,y,z in meters):

timestamp x y z qw qx qy qz
117150 22.6348 8.41777 20.0105 0.997918 0.00786275 -0.0022486 -0.0639791 
117184 22.6217 8.41973 20.0197 0.997547 0.00783108 -0.0185031 -0.0670483 
117284 22.5754 8.42408 20.0496 0.995566 0.001033 -0.0640501 -0.0688833 
117484 22.4532 8.43339 20.1222 0.985946 -0.000132175 -0.157064 -0.0569268 
117650 22.3357 8.45294 20.2122 0.977612 -0.00927412 -0.201266 -0.060676 
117984 22.1551 8.44522 20.5046 0.991904 -0.0469677 -0.115013 -0.0263118 
118251 22.1495 8.41537 20.7701 0.997495 -0.039601 0.020937 0.0547514 
118450 22.1928 8.425 20.9982 0.989814 -0.00817581 0.111457 0.0881998 
118917 22.43 8.40948 21.4909 0.965929 0.00714077 0.254651 0.0456355 
119251 22.642 8.43456 21.8806 0.952832 -0.0011257 0.302843 -0.0199026 
119651 22.8751 8.41812 22.3077 0.953313 0.0145462 0.300359 -0.0277063 
...

Graph is OSM road network. The main problem is track coordinates uses some local coordinate system and I don't know transform between it and WGS84 or any other global system. Actually my tracker changes local system at every restart.

So I am looking for matching method that can match by track shape.

[addy90]

Thanks for providing the sample, I am not sure but this looks like quaternion data (qw qx qy qz). Unfortunately I cannot process such data. May I ask what tracking device this emits? You say that your tracker has a local system at every restart, so when it does not have a reference to a world location, for example a GPS point, then how can you know at which place on earth the trajectory happened?

This tool only works when both data is in the same reference system or can be converted into the same reference system. When you have a reference system such as the world (OSM road network) and data from another system with the coordinates being relative to a totally different origin, this does not work of course. When both data sets are GPS coordinates, both have the same (0 0) origin. When one data set is in a different coordinate system with a different origin but has a PROJ4 string defined with conversion mathematics, it can be converted into a compatible system that share the same origin. So when you don't know how to convert the origin of your data to the GPS origin (or another origin of a spatial reference system), I think there is no way to map the data with this tool.

At least when you restart your device, you need it to record a GPS position for example. Then you could convert the GPS position into a cartesian coordinate system such as UTM and use the x y meter differences in addition to the recorded origin. This step is also not supported by this tool but could be preprocessed in a small script before.

As this tool maps 2D coordinates, both network and track need to have the same origin and unit. Either from the start or after transformation via PROJ4 strings.

The tool does not search a track location by comparing the data with worldwide roads, this is a very different approach. This tool maps tracks for example from smartphones or GPS tracking devices onto existing road networks by comparing distances, azimuths and it removes measurement noise in this process. It is not for finding a location but for finding a best fitting route in an underlying road network for a given recorded track. Close spatial similarity is needed for the data up to some hundred meters, so typically within the GPS measurement errors.

Maybe you have another export mechanism for your device that gives out GPS data? Or does the tracking device not have any GPS receiver? Then I assume it does not work unfortunately. Of course also GALILEO or GLONASS should work but it is untested, GPS is most common for geographical coordinates. But the tool does not care much about the spatial reference system but some exotic might not work because they are untested. What works is longitude/latitude in degrees and x/y in meters.

[KrasnovPavel]

Thank you for answer.

I am not sure but this looks like quaternion data (qw qx qy qz)

Yes, it is.

May I ask what tracking device this emits?

It is custom SLAM-device.

how can you know at which place on earth the trajectory happened?

I can guarantee that my device will always work only in specific area (about 20km^2) moreover I can guarantee that it will only move over pedestrial roads. So I can download specific part of OSM and expect that all my tracks will be within it.

GPS-deniing is current goal of my experiments. I have experimented with map matching (using FMM) providing conversion from local system to global (by recording GPS location at start of device as you suggested) and I like results. I will definetly try your tool too. But now I want to try even more radical aproach and don't use even initial GPS coordintes. I hoped that your tool can do it but looks like i will need to implement some curve mathing or ICA or some other algorithm.

Also can you provide some instructions how to use this tool as dymanic library?

[addy90]

I see, interesting! Well you can try to match the coordinates with the 20km^2 area and a very large candidate search circle with --radius parameter. Maybe you need to raise --radius-upper-limit, too. You might disable the "adoption" methods as they could make the program very slow with a very large circle, also you might want to disable --adaptive-radius. Also maybe you want to disable the track sanitation methods, for example median-merge and simplify-track as this might change the curve of your recorded track.

Maybe you need to convert the network into a cartesian coordinate system with the --network-transform-srs setting, for example a UTM system. You can then add manually the center point of your 20km^2 area from that SRS to your coordinates and then import your coordinates in my tool by setting --tracks-srs to the same UTM system. So you fake the coordinates being in the center of your area.

You can then set the distance weight to 0.0 with --mdp-distance-factor when you use the MDP or with the corresponding HMM parameter. This will make the matching weighting only the lengths, azimuths and distance changes, maybe you want to tune these weights, too. Then the tool is somehow turned into a curve matching tool that searches for the best road edges fitting to the curve in the area. You see, the distance plays no role anymore, the search radius is to the max of the area, the lengths, azumiths, maybe distance changes as you wish are only left for matching, the data is in a metric cartesian system, the track coordinates are laid somewhere into that area by adding the center coordinates. So the large search circle is around the coordinates of the track that was moved into that area and searches for the best fitting edge no matter how far away it is from the track.

Do you understand what I mean? This is the idea I have in mind straight away. I would be interested if this somehow works. FMM is a tool I compared too extensively, so everything FMM is able to do my tool should more or less also be able to do.

Currently the tool is not directly prepared for usage as a dynamic library, maybe this will be added in the future. The parts of the tool are however designed as static libraries, you can review the main.cpp and associated CMakeLists.txt how the parts of the tool are used together. The main.cpp is not exceptionally nicely written but the idea should become clear. After all it is somehow Work-in-progress still. Without all the parameters, you could use the ingredients of the subparts of the tool in your own software. Beware of the AGPL 3.0 license in that case, please! But it is definitely possible, just not officially well ready-made yet.

[KrasnovPavel]

Thanks for you advise! I will definetly try it tomorrow.

I think I got your idea but for now not really understand meanings of some parameters. What is difference between --mdp-azimuth-factor and --mdp-direction-factor? Am I unerstand it correctly? So if I will disable --mdp-direction-factor, --mdp-distance-factor and set big radius then tool will rotate and translate my track all over the network?

I would be interested if this somehow works.

I will let you know when i get some results.

Beware of the AGPL 3.0 license in that case, please!

Of course!

[addy90]

Hi, yeah some parameters are not quite intuitive, I tried things out during development and so there are many knobs to turn... some are difficult to describe, some may not work perfectly in combination yet.... some might vanish in future again, happened to A*-shortest path algorithm for example as it was slower than Dijkstra with my caching technique. Please feel free to ask if something is unclear!

So concerning the four weight parameters, maybe this little graphic helps (all fame goes to paint for the great quality): In blue are road network edges, in red a recorded track to match.

Distance is the distance between a track point and the street edge on its closest line, here in gray. You see when you disable distance by setting the weight to 0.0 then the matching algorithm does not care about the match being near to the track. This in combination with a large search circle should allow the curve to be found within the road graph. Length is for the length differences of two matched segments, here in green. Azimuth is on the circle from 0 to 360 degree like on a compass the clockwise angle (bearing) of the segment, so a segment that goes to north has azimuth 0, a segment to east has 90 degree, segment to south 180 and segment to west 270 degree roughly, here in violet. Direction is the difference of two adjacent azimuths, so either from 0 to 180 degree to the left or from 0 to -180 degree to the right, direction is always meant als direction change, so the angle between two adjacent segments, here in orange. For more information you can also read the paper that is linked in the main readme: Evolving map matching with markov decision processes

All these information are available with only 2D points, no heading, z-axis, timestamps or so are needed, only a list of 2D points, then lengths, azimuths (bearings) and direction changes between any two adjacent segments can be computed. I am not sure if disabling direction factor is good because it showed quite good results for tracks on streets in combination with length and azimuth. Changing directions gives the most information which edges of a network fit best together for matching a track, but the lengths, azimuths and distances are also important for knowing the position. But when you have a curve, the direction changes are a key aspect of the curve when to match it to a map, at least this is what I measured, which is why the weight is higher on direction changes than on lengths and azimuths alone. Still the weights are not perfectly tuned yet, I am sure they will change in the future, but the combination showed quite some robustness. After all, we are talking about stochastic methods that never guarantee a perfect solution as in the "right" solution, just an optimal solution to their metrics and models. Still, just try it out! Different weights, maybe set everything to 0.0 except lengths, then it is similar to FMM that also uses lengths (and distances, but we want to disable those) for comparing, or only use azimuths or directions. If the tool crashes in any situation, please let me know!

I hope this helps! I have no idea how fast the software works in such a case as yours, at least it looks like I made enough tuning parameters so that your case is nearly already possible, at least in theory :-D

Oh yeah maybe some of the unit tests under tests directory help in an easy or quicker way how to use the static sublibraries in a thirdparty tool. There mostly fixed settings are used which facilitates the usage of the sublibrary methods for matching.

[KrasnovPavel]

Thanks, now I've got it. I just thought that azimuth is difference between two directions. I'm not into cartographics but I thought this is the definition of azimuth, and it has one most common case when one of directions pointed to north.

[addy90]

I defined the azimuth after how it is defined in cartography, so yes: https://en.wikipedia.org/wiki/Azimuth#In_cartography "the azimuth is clockwise relative to the north" it says there. boost::geometry does it exactly like this when I call the azimuth algorithm. So I used direction for the change between two succeeding azimuths. If this is the perfect naming convention, I am not sure, but it was currently my best idea.