cyang-kth / fmm Goto Github PK

Hello,
It would be nice if fmm can import OSM network data by using libosmium or others.

Sorry to disturb you again.
There's some error in my output. When I checked 'pgeom', I found that some gps point were matched with '0 0'.
Here is the input:
LINESTRING (-8.618643 41.141412,-8.618499 41.141376,-8.620326 41.14251,-8.622153 41.143815,-8.623953 41.144373,-8.62668 41.144778,-8.627373 41.144697,-8.630226 41.14521,-8.632746 41.14692,-8.631738 41.148225,-8.629938 41.150385,-8.62911 41.151213,-8.629128 41.15124,-8.628786 41.152203,-8.628687 41.152374,-8.628759 41.152518,-8.630838 41.15268,-8.632323 41.153022,-8.631144 41.154489,-8.630829 41.154507,-8.630829 41.154516,-8.630829 41.154498,-8.630838 41.154489)
Here is the output:
LINESTRING (-8.61862328389464 41.1414555366075,-8.61849026161021 41.1413952953285,-8.62030524367214 41.1425402664601,-8.622154312869 41.1438113798153,-8.62395062773408 41.144380692548,-8.6266795454238 41.1447604091626,-8.62737261868137 41.1446919580741,-8.63020665338637 41.1452422388008,-8.63283503440671 41.1470000234958,-8.63174708911134 41.1482330307184,-8.62990391694432 41.1503557735519,-8.62913862329367 41.1512383642161,-8.6290736 41.1513117,-8.62881193599271 41.1522096548352,-8.62876464399775 41.1523939459704,-8.62876116165927 41.1524792121554,-8.63084191628064 41.1525937953313, 0 0,
-8.6310274 41.1545682,-8.6307169 41.1544924,-8.6307169 41.1544924,-8.63094107531387 41.1546375359879,-8.63095094005297 41.1546296126295)
I generated my dataset by following the step in https://github.com/cyang-kth/osm_mapmatching.
Then I create input.shp by pyshp. Here is the code:

import shapefile 
import numpy as np
trips=np.load('trips.npy')
w = shapefile.Writer('test')
w.field('id', 'n')
for i in range(len(trips)):
    w.line([trips[i]])
    w.record(i+1)
w.close()

I set the config following https://github.com/cyang-kth/osm_mapmatching/blob/master/ubodt_config.xml and https://github.com/cyang-kth/fmm/blob/master/example/fmm_config.xml. I just changed the k、r and gps error in fmm_config.xml.
What do you think is wrong？Thank you very much!

It seems that map matching becomes very slow when the trajectory is long (contains many points > 100).
And I have two questions.
Whether the number of points contained in the trajectory affects performance？
Is it reasonable to use points/second to measure performance?

Thanks.

Describe the bug
I tried to run the example with default and the osm version configurations of ubodt and fmm, but both got 0% matched percentage on the example. Besides, there is a warning with Boost. I am using MAC with Boost 1.69.0.

Expected behavior
Here is the configuration on the example.

// ubodt_config.xml
<?xml version="1.0" encoding="utf-8"?>
<ubodt_config>
    <input>
        <network>
            <file>../example/data/edges.shp</file>
            <id>id</id>
            <source>source</source>
            <target>target</target>
        </network>
    </input>
    <parameters>
        <delta>0.5</delta>
    </parameters>
    <output>
        <file>ubodt.txt</file>        
    </output>
</ubodt_config>
//fmm_config.xml
<?xml version="1.0" encoding="utf-8"?>
<fmm_config>
  <input>
    <ubodt>
      <file>ubodt.txt</file>
    </ubodt>
    <network>
      <file>../example/data/edges.shp</file>
      <id>id</id>
    </network>
    <gps>
      <file>../example/data/trips.shp</file>
      <id>id</id>
    </gps>
  </input>
  <parameters>
    <k>40</k>
    <r>0.01</r>
    <pf>0</pf>
    <gps_error>0.005</gps_error>
  </parameters>
  <output>
    <fields>
      <all/>
      <!-- <ogeom/> <error/> <opath/> <cpath/> -->
    </fields>
    <file>mr.txt</file>
  </output>
  <other>
    <log_level>2</log_level>
  </other>
</fmm_config>

Here is the matching result.
------------ Fast map matching (FMM) ------------
------------ Author: Can Yang ------------
------------ Version: 2020.01.31 ------------
------------ Applicaton: fmm ------------
Start with reading FMM configuration ../example/fmm_config.xml
Finish with reading FMM configuration.
Set log level as 2-info
[info][config.hpp:386] Validating configuration
[warning][config.hpp:417] Overwrite existing result file mr.txt
[info][config.hpp:436] Validating done

FMM Configurations
Network_file: ../example/data/edges.shp
Network id: id
Network source: source
Network target: target
ubodt_file: ubodt.txt
delta: undefined, to be inferred from ubodt file
ubodt format(1 binary, 0 csv): 0
gps_file: ../example/data/trips.shp
gps_id: id
k: 40
radius: 0.01
gps_error: 0.005
penalty_factor: 0
log_level:2-info
result_file:mr.txt
Output fields:
ogeom opath pgeom offset error spdist cpath tpath mgeom ep tp length

[info][network.hpp:74 ] Read network from file ../example/data/edges.shp
[info][network.hpp:172] Read network done edges 17 nodes 30 srid 4326
[info][ubodt.hpp:280] Reading UBODT file (CSV format) from ubodt.txt
[info][ubodt.hpp:316] Finish reading UBODT with rows 0
[info][fmm.cpp:67 ] Delta inferred from ubodt as 0
[info][reader.hpp:81 ] Reading GPS trajectories GDAL format from ../example/data/trips.shp
[info][reader.hpp:109] Geometry type is Line String
[info][reader.hpp:111] Index of id column 0
[info][reader.hpp:112] Total number of trajectories 3
[info][reader.hpp:113] Finish reading meta data
[info][writer.hpp:46 ] Write result to file mr.txt
[info][fmm.cpp:83 ] Total trajectory number 3
[info][fmm.cpp:84 ] Progress report step 10
[info][fmm.cpp:112] Progress 3
[info][fmm.cpp:122] Time takes 0.06, excluding input takes
[info][fmm.cpp:123] Total points 17 matched 0
[info][fmm.cpp:124] Matched percentage: 0
[info][fmm.cpp:127] Point match speed: 0 pt/s (excluding input -nan pt/s)
------------ Program finished ------------

Process finished with exit code 0

Here is the boost warning.

Scanning dependencies of target fmm
[ 50%] Building CXX object CMakeFiles/fmm.dir/app/fmm.cpp.o
In file included from /Users/yong/Code/fmm/app/fmm.cpp:17:
In file included from /Users/yong/Code/fmm/app/../src/network.hpp:24:
In file included from /Users/yong/Code/fmm/app/../src/types.hpp:14:
In file included from /Users/yong/Code/fmm/app/../src/geometry_type.hpp:10:
In file included from /Users/yong/Code/fmm/include/boost/geometry/extensions/gis/io/wkb/read_wkb.hpp:18:
In file included from /Users/yong/Code/fmm/include/boost/geometry/extensions/gis/io/wkb/detail/parser.hpp:32:
In file included from /Users/yong/Code/fmm/include/boost/geometry/extensions/gis/io/wkb/detail/endian.hpp:29:
In file included from /usr/local/include/boost/detail/endian.hpp:9:
/usr/local/include/boost/predef/detail/endian_compat.h:11:9: warning: The use of BOOST_ENDIAN and BOOST_BYTE_ORDER is deprecated. Please include <boost/predef/other/endian.h> and use BOOST_ENDIANBYTE instead [-W#pragma-messages]
#pragma message("The use of BOOSTENDIAN and BOOST_BYTE_ORDER is deprecated. Please include <boost/predef/other/endian.h> and use BOOST_ENDIAN_BYTE instead")
^
1 warning generated.
[100%] Linking CXX executable fmm
[100%] Built target fmm

Build finished

I would like to get some attributes from original GPS points (say, timestamp) and link them to matched edge (in cpath). However, if there are some unmatched points ramdomly occured, i could not know the correct order of the matched edge (in opath) related with original GPS points (the order should not be the same as in original GPS points). So, is it possible to get the information from original GPS points linked with matched edge, please?

Sorted by priority

• Implement another algorithm STMATCH using the current framework
• Separate HPP into header and source code and define folders of the codes
• Directly use GPS point CSV file as input
• Move OMP to the argument list instead of separate app
• Directly reading network data from OpenStreetMap
• Add preprocessing trajectory data with line simplification or trajectory smoothing
• Add one-way attribute for the road network instead of preprocessing

We can not use the fmm in the python as we have to use c++ to generate the ubodt.txt file. Is there any method provided in python language?

Hi,

I successfully build the c++. But when I tried to install the python extension and run "cmake ..", it gave me errors about SWIG:

$ cmake ..
-- The C compiler identification is GNU 9.3.0
-- The CXX compiler identification is GNU 9.3.0
-- Check for working C compiler: /usr/bin/cc
-- Check for working C compiler: /usr/bin/cc -- works
-- Detecting C compiler ABI info
-- Detecting C compiler ABI info - done
-- Detecting C compile features
-- Detecting C compile features - done
-- Check for working CXX compiler: /usr/bin/c++.exe
-- Check for working CXX compiler: /usr/bin/c++.exe -- works
-- Detecting CXX compiler ABI info
-- Detecting CXX compiler ABI info - done
-- Detecting CXX compile features
-- Detecting CXX compile features - done
-- Found SWIG: /usr/bin/swig.exe (found version "3.0.12")
-- Found GDAL: /usr/lib/libgdal.dll.a (found suitable version "3.0.4", minimum required is "2.2")
-- Found PythonLibs: /usr/lib/libpython2.7.dll.a (found suitable version "2.7.16", minimum required is "2.7")
-- Boost version: 1.66.0
-- Found the following Boost libraries:
--   serialization
CMake Deprecation Warning at /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:559 (message):
  SWIG_ADD_MODULE is deprecated.  Use SWIG_ADD_LIBRARY instead.
Call Stack (most recent call first):
  CMakeLists.txt:57 (swig_add_module)


CMake Warning (dev) at /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:600 (message):
  Policy CMP0078 is not set: UseSWIG generates standard target names.  Run
  "cmake --help-policy CMP0078" for policy details.  Use the cmake_policy
  command to set the policy and suppress this warning.

Call Stack (most recent call first):
  /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:560 (swig_add_library)
  CMakeLists.txt:57 (swig_add_module)
This warning is for project developers.  Use -Wno-dev to suppress it.

CMake Warning (dev) at /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:460 (message):
  Policy CMP0086 is not set: UseSWIG honors SWIG_MODULE_NAME via -module
  flag.  Run "cmake --help-policy CMP0086" for policy details.  Use the
  cmake_policy command to set the policy and suppress this warning.

Call Stack (most recent call first):
  /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:695 (SWIG_ADD_SOURCE_TO_MODULE)
  /usr/share/cmake-3.14.5/Modules/UseSWIG.cmake:560 (swig_add_library)
  CMakeLists.txt:57 (swig_add_module)
This warning is for project developers.  Use -Wno-dev to suppress it.

-- Creating makefiles for system: CYGWIN-3.1.4(0.340/5/3)
-- Configuring done
-- Generating done
-- Build files have been written to: /cygdrive/d/Google Drive/Research/INRIXData/MD/fmm-master/python/build

I checked the ccmake, but did not find any SWIG_ADD_MODULE or SWIG_ADD_LIBRARY tag.

Thanks!

Program received signal SIGSEGV, Segmentation fault.
MM::TransitionGraph::viterbi (this=0x7fffffffe290, pf=0) at app/../src/transition_graph.hpp:126
126             while ((track_cand=track_cand->prev)!=NULL)
(gdb) bt
#0  MM::TransitionGraph::viterbi (this=0x7fffffffe290, pf=0) at app/../src/transition_graph.hpp:126
#1  0x00005555555590ca in main (argc=<optimized out>, argv=<optimized out>) at app/fmm.cpp:105
(gdb) print track_cand
$1 = (MM::Candidate *) 0x0

I have used a secondary open dataset (top10nl, with a bit preprocessing) as ubodt input. Then I run nwb-renumbered as GPS on top of it.

<fmm_config>
    <input>
        <ubodt>
            <file>ubodt-top10nl-500.txt</file>
            <nhash>999983</nhash>
            <multiplier>1815275</multiplier>
        </ubodt>
        <network>
            <file>top10_edges2.shp</file>
            <id>lokaalid</id>
            <source>x</source>
            <target>y</target>
        </network>
        <gps>
            <file>wegvakken_renumbered_28992.shp</file>
            <id>WVK_ID</id>
        </gps>
    </input>
    <parameters>
        <k>4</k>
        <r>100</r>
        <pf>0</pf>
        <gps_error>0.5</gps_error>
    </parameters>
    <output>
        <mode>1</mode>
        <file>mr.txt</file>
    </output>
</fmm_config>

I have validated that the concept below does not result in a segfault, so I would not say it is the GPS input:

<?xml version="1.0" encoding="utf-8"?>
<fmm_config>
    <input>
        <ubodt>
            <file>ubodt-nwb.txt</file>
            <nhash>999983</nhash>
            <multiplier>1815275</multiplier>
        </ubodt>
        <network>
            <file>wegvakken_renumbered_28992.shp</file>
            <id>WVK_ID</id>
            <source>JTE_ID_BEG</source>
            <target>JTE_ID_END</target>
        </network>
        <gps>
            <file>wegvakken_renumbered_28992.shp</file>
            <id>WVK_ID</id>
        </gps>
    </input>
    <parameters>
        <k>4</k>
        <r>100</r>
        <pf>0</pf>
        <gps_error>0.5</gps_error>
    </parameters>
    <output>
        <mode>1</mode>
        <file>mr.txt</file>
    </output>
</fmm_config>

For some reason the last point in the WKB is 0, 0. I would also be interested where this error comes from.

LINESTRING(15453.4104747247 378339.923357993,15453.4919999987 378340.359999999,15454.7820000015 378347.800000001,15457.2190000005 378361.861000001,15458.5720000006 378367.188999999,15460.8330000006 378371.25,15463.1059999987 378374.
807999998,15465.938000001 378377.506999999,15473.3680000007 378383.057,15479.2659999989 378386.600000002,15481.3099999987 378387.802999999,15483.8409999982 378388.245000001,15486.3850000016 378389.16,15488.3220000006 378389.548,15535
.7569999993 378399.070999999,15539.675999999 378399.857999999,0 0)

LINESTRING(0 0,22601.778 397575.571,22595.76 397568.293,22564.676 397534.956,22555.374 397526.605,22536.228 397513.27,22388.963 397445.265,22387.456 397444.569,22381.37 397437.341,22379.646 397435.294,22373.333 397423.983,22366.321
397411.422,22366.2753544712 397410.972065502)

Including tutorial, resources, developer or debug guide, case study, etc

Hi,

make chooses the first target as default when running:
$ make

which in this case is 'intial'. Please consider making "build: ..." the first target in your Makefile; more intuitive for "make; make install" habituals like me.

Thx!
Tias

also needs 'libboost-serialization-dev', which is absent from the sudo apt-get install instruction on the main page

Although I can use the fmm package (python), fmm needs to use the ubodt_gen(c++) to generate ubodt.txt. I think this is very troublesome，could you provide a python package for ubodt_gen? Or can you integrate ubot_gen into fmm(python)? Thank you!

I used a one direction network file for the map matching, so in the generated ubodt file there is only one direction source to target, and in the map matching it cannot match the opposite direction trajectories. Can it be solved?

The current MM result is exported as a CSV file, which can waste a lot of storage.

Experiments on a dataset of Stockholm containing 27343 trajectories and 310137 points shows that (output: id+opath+cpath+geom)

Add support to writing output directly in geopackage or spatialite format.

If you discovered any problem in map matching related with accuracy where the algorithm fails, you are welcome to report it here. I am also trying to make the algorithm more robust to noises in practice.

Describe the bug
Hi,
Thanks for your amazing map matching tools. I tried to install requirements and C++ program as your tutorials in window 10 with wsl2. After I installed requirements I tried to run cmake, but it appears to a error as followed:
OGRMultiLineString has no member named toUpperClass
Would you please help me why this error appears and how to figure out it?
Thank you very much :)

Expected behavior
A clear and concise description of what you expected to happen.

Screenshots

Trying to follow the installation instructions here: https://github.com/cyang-kth/fmm/tree/master/python

When running cmake .. an error is shown:
CMake Error: The source directory "/home/edi/code/fmm/python" does not appear to contain CMakeLists.txt.

It looks like this file is in .gitignore

I tried to run fmm with city scale graph and one gps trajectory. I ended up with memory corruption.

root@81df69e51c95:/fmm# fmm fmm-config/fmm_config.xml
------------ Fast map matching (FMM) ------------
------------     Author: Can Yang    ------------
------------   Version: 2018.03.09   ------------
------------     Applicaton: fmm     ------------
Validating configuration for map match application:
    Warning, overwrite existing result file.fmm-output/mr.txt
Validating success.
------------------------------------------
Configuration parameters for map matching application:
    Network_file:       data/street_network/edges/edges.shp
    Network id:         osmid
    Network source:     from
    Network target:     to
    ubodt_file:         fmm-output/ubodt.txt
    multiplier:         49966
    nhash:              11311
    delta:              5000
    ubodt format(1 binary, 0 csv): 0
    gps_file:           data/trips/trips.shp
    gps_id:             id
    k:                  4
    radius:             0.01
    gps_error:          0.001
    penalty_factor:     0
    result_file:        fmm-output/mr.txt
    geometry mode:      2(0 no geometry, 1 wkb, 2 wkt)
------------------------------------------
Read network shp file from data/street_network/edges/edges.shp
Id column osmid
	Number of edges in file: 76108
	SHP ID idx: 11
	SHP source idx: 2
	SHP target idx: 14
	Geometry type is Line String
	SRID is 4326
Read network finish.
	The maximum node ID is 2039118004
	Total number of edges read 76108
Start to construct boost rtree
Finish construct boost rtree
Reading UBODT file (CSV format) from: fmm-output/ubodt.txt
    Header line skipped.
Read rows: 1000000
    Number of rows read 1627795
    Estimated load factor #elements/#tablebuckets 5425.98
    *** Warning, load factor is too large.
Finish reading UBODT.
Reading meta data of GPS trajectories from: data/trips/trips.shp
    Index of ID column: 0
    Total number of trajectories: 1
Finish reading meta data
Write result to file: fmm-output/mr.txt
Start to map match trajectories with total number 1
Progress 0 / 1

=============================
MM process finished
Time takes 2.071
Time takes excluding input 0.006
Finish map match total points 136 and points matched 0
Matched percentage: 0
Point match speed:0pt/s
Point match speed (excluding input): 0pt/s
Clean UBODT
*** Error in `fmm': double free or corruption (out): 0x0000000001804610 ***
======= Backtrace: =========
/lib/x86_64-linux-gnu/libc.so.6(+0x777e5)[0x7f85583917e5]
/lib/x86_64-linux-gnu/libc.so.6(+0x8037a)[0x7f855839a37a]
/lib/x86_64-linux-gnu/libc.so.6(cfree+0x4c)[0x7f855839e53c]
fmm[0x409c9e]
fmm[0x4058cd]
/lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xf0)[0x7f855833a830]
fmm[0x4066e9]
======= Memory map: ========
00400000-00436000 r-xp 00000000 08:01 1740679                            /root/bin/fmm
00635000-00636000 r--p 00035000 08:01 1740679                            /root/bin/fmm
00636000-00637000 rw-p 00036000 08:01 1740679                            /root/bin/fmm
00cc0000-062bd000 rw-p 00000000 00:00 0                                  [heap]
7f8540000000-7f8540021000 rw-p 00000000 00:00 0
...
Aborted

I generated the network using osmnx:

location_point = (24.6946907, 46.72079802)
city = ox.graph_from_point(location_point, distance=10000)
ox.save_graph_shapefile(city, filename='street_network')

GPS as WKT (generated using GeoPandas):

'LINESTRING (46.64934397 24.73307848, 46.64477348 24.7419405, 46.64470911 24.74213362, 46.64129734 24.74874258, 46.64112568 24.74918246, 46.64093256 24.74953651, 46.63610458 24.76218581, 46.63799286 24.76747513, 46.64007425 24.77189541, 46.64063215 24.77313995, 46.64082527 24.77354765, 46.64101839 24.77396607, 46.64119005 24.77436304, 46.64241314 24.7773993, 46.64234877 24.77742076, 46.64224148 24.77733493, 46.63973093 24.77704525, 46.63960218 24.77693796, 46.63958073 24.77692723, 46.63174868 24.79223728, 46.63170576 24.79221582, 46.63170576 24.7922051, 46.63170576 24.79221582, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.63170576 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.7922051, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.6316843 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79219437, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.63166285 24.79218364, 46.6316843 24.79230165, 46.6316843 24.79236603, 46.6316843 24.79237676, 46.6316843 24.79241967, 46.6316843 24.79244113, 46.6316843 24.79245186, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79244113, 46.6316843 24.79245186, 46.6316843 24.79245186, 46.63164139 24.79249477, 46.63164139 24.79252696, 46.63159847 24.79254842, 46.63159847 24.79260206, 46.63157701 24.79265571, 46.63155556 24.79273081, 46.6315341 24.79278445, 46.63078308 24.7942543, 46.63258553 24.79436159, 46.63331509 24.79476929, 46.63352966 24.79485512, 46.63352966 24.79485512, 46.63374424 24.79495168, 46.63374424 24.79495168, 46.63395882 24.79503751, 46.63395882 24.79504824, 46.63417339 24.79513407, 46.63417339 24.7951448, 46.63436651 24.79523063, 46.63438797 24.79523063, 46.63458109 24.79531646, 46.63460255 24.79532719, 46.63479567 24.79541302, 46.63481712 24.79542375, 46.63501024 24.79549885, 46.63522482 24.79559541, 46.63503170000001 24.79552031, 46.63524628 24.79560614, 46.6354394 24.79569197, 46.63546085 24.7957027, 46.63565397 24.7957778, 46.63567543 24.79579926, 46.63329363 24.79504824, 46.63331509 24.79500532, 46.63333654 24.79498386, 46.633358 24.79497313, 46.633358 24.79496241, 46.633358 24.79496241, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.633358 24.79495168, 46.63337946 24.79495168, 46.63337946 24.79495168, 46.63342237 24.79495168, 46.63361549 24.79502678, 46.63365841 24.79504824, 46.63370132 24.79505897, 46.63372278 24.79506969, 46.6337657 24.79509115, 46.63380861 24.79510188, 46.63129807 24.80053067, 46.63116932 24.80078816, 46.63116932 24.80079889, 46.63101912 24.80105639, 46.63065434 24.80177522, 46.63050413 24.80204344, 46.63037539 24.80231166, 46.63022518 24.80257988, 46.63009644 24.8028481, 46.63007498 24.80286956, 46.62994623 24.80310559, 46.62981749 24.80337381, 46.62979603 24.80359912, 46.62962437 24.80404973, 46.62955999 24.80416775, 46.62951708 24.80427504, 46.62945271 24.80439305, 46.62936687 24.80451107, 46.6293025 24.80463982, 46.62923813 24.80477929, 46.62917376 24.80489731, 46.62827253 24.80658174)'

1. Handle network node with big ID. A map can be built for the node id attribute and its index. How to ensure the consistency of mapping in ubodt_gen and fmm
2. Automatically computation of the nhash and multiplier used in fmm

Hi

When I run fmm it says Segmentation fault(Core Dumped).

`$ fmm fmm_config.xml
------------ Fast map matching (FMM) ------------
------------ Author: Can Yang ------------
------------ Version: 2018.03.09 ------------
------------ Applicaton: fmm ------------
Start reading FMM configuration
Finish with reading FMM configuration
Validating configuration for map match application:
Warning, overwrite existing result file.mr.txt
Validating success.

Configuration parameters for map matching application:
Network_file: data/edges_small.shp
Network id: id
Network source: source
Network target: target
ubodt_file: ubodt.txt
multiplier: 100
nhash: 23100
delta: undefined, to be inferred from ubodt file
ubodt format(1 binary, 0 csv): 0
gps_file: data/trips_small.shp
gps_id: id
k: 10
radius: 4
gps_error: 50
penalty_factor: 0
result_file: mr.txt
Output fields:
ogeom
opath
pgeom
offset
error
spdist
cpath
tpath
mgeom

Read network shp file from data/edges_small.shp
Id column id
Number of edges in file: 52
SHP ID idx: 0
SHP source idx: 1
SHP target idx: 2
Geometry type is Line String
SRID is 4326
Read network finish.
The maximum node ID is 686801
Total number of edges read 52
Start to construct boost rtree
Finish construct boost rtree
Reading UBODT file (CSV format) from: ubodt.txt
Header line skipped.
Number of rows read 310
Estimated load factor #elements/#tablebuckets 0.0134199
Finish reading UBODT.
Delta inferred from ubodt as 0.00980391
Reading meta data of GPS trajectories from: data/trips_small.shp
Index of ID column: 0
Total number of trajectories: 81
Finish reading meta data
Write result to file: mr.txt
Start to map match trajectories with total number 81
Progress 0 / 81
Segmentation fault (core dumped)
`
Ubodt worked fine

`$ ubodt_gen ubodt_config.xml
------------ Fast map matching (FMM) ------------
------------ Author: Can Yang ------------
------------ Version: 2018.03.09 ------------
------------Application: ubodt_gen_opt------------
Read configuration from xml file: ubodt_config.xml
Validating configuration for UBODT construction:
Warning, overwrite existing result file.ubodt.txt
Validating success.

Configuration parameters for UBODT construction:
Network_file: data/edges_small.shp
Network id: id
Network source: source
Network target: target
delta: 0.01
Output file: ubodt.txt
Output format(1 binary, 0 csv): 0

Write UBODT to file ubodt.txt
Read network shp file from data/edges_small.shp
Id column id
Number of edges in file: 52
SHP ID idx: 0
SHP source idx: 1
SHP target idx: 2
Geometry type is Line String
SRID is 4326
Read network finish.
The maximum node ID is 686801
Total number of edges read 52
Construct graph from network edges start
Network edges :52
Graph nodes 53
Construct graph from network edges end
Upperbound config (delta): 0.01
Start to generate UBODT with delta 0.01
Output format csv
Progress 0 / 53
Progress 10 / 53
Progress 20 / 53
Progress 30 / 53
Progress 40 / 53
Progress 50 / 53
Time takes 0.007
Cleaning network
Cleaning network finished
------------ Program finished ------------
`

Can you please tell me where is my issue. In attached is my data

Best regards,
Michael
example_small.zip

For a large road network, the product of source and target node in UBODT insertation and query can be surpass the range of integer, which would cause an overflow problem.

The current program requires the node ID to be continuously distributed as in BGL the graph is created with vertice index starting from 0. One solution is to renumber the vertex ID, which can be tedious.

Another solution would be to store the discontinuous node ID as the vertex property and maintain a hash map to record the index of nodes incrementally during the graph creation, which is under development now.

Design a Python interface similar to the one in Caffe
https://github.com/BVLC/caffe/blob/master/python/caffe/_caffe.cpp

Hi Can,

I download the newversion and when i rebuild the model there is an error appeared. So how can i solve it. Thanks.
###########
app/ubodt_gen.cpp:9:22: fatal error: config.hpp: No such file or directory
#include "config.hpp"
^
compilation terminated.
make: *** [build_ubodt_gen] Error 1
----- Copy executables to home/bin -----
cp dist/fmm /home/x/bin
cp dist/ubodt_gen /home/x/bin
cp: cannot stat 'dist/ubodt_gen': No such file or directory
make: *** [install] Error 1
################

Describe the bug
I cannot understand deep enough what is the exact format of the shapefile that needs to be provided for ubodt_gen program.

Expected behavior
a csv file from which the edges.shp file can be generated with ogr2ogr binary is available.

Configuration can be further split into

• GPSConfig
• FMMConfig
• UBODTConfig
• STMATCHConfig
• OutputConfig
• NetworkConfig

If the geometry of shapefile is mulilinestring, the ubodt_gen will show a segment fault error.

Sorry to disturb you again.
I met some problem while installing the python extension:
My environment is
Ubuntu 16.04
swig 4.0.0
Python 2.7
When I run python fmm_test.py ,I met the following problem:

Traceback (most recent call last):
File "../fmm/web_demo/fmm_web_app.py", line 14, in
from fmm import MapMatcher
File "/home/project/test_map/fmm/python/build/fmm.py", line 17, in
_fmm = swig_import_helper()
File "/home/project/test_map/fmm/python/build/fmm.py", line 16, in swig_import_helper
return importlib.import_module('_fmm')
File "/home/anaconda3/envs/python27/lib/python2.7/importlib/init.py", line 37, in import_module
import(name)
ImportError: dynamic module does not define init function (init_fmm)

I've build _fmm.so and add the build folder to the environment variable.

I've installed the C++ extension. In fact, I just want to get the link id (cpath). It seems that I got id of dual road netwok by following the step in osm_mapmatching. Should I use edge.shp as input directly if I want each segment of road appear only once ?
Now I have 7000 trips , shall I make them into one trip.shp file (Because I want the same road segment in each trip have the same id)? Besides, I saved these data in csv file and list data structure in python, do you have some suggesstions on changing the data into 'trip.shp' and 'trip.shx'?

Thank you very much!

Roads in the real world have different levels, such as highways, trunk, motorway, and residential roads. Can this algorithm handle different road priorities?

Hi
When I run fmm it doesn't find any matches, the result is empty
fmm.zip

Describe the bug
When the UBODT file is too big, about 3.6 GB and contains about 1.2 G rows. The hashtable size is not correctly calculated.

Expected behavior
The ubodt table bucket should increase with that number.

Hi Can,

Sorry to disturb you again. I get the edges file via osmnx, but when i change the network type from drive to the drive_service (1787354 edges), this error(segmentation fault) occurred. I am sure that all other parameter are the same. Could you please give me some suggestion? Thanks in advanced.
############
When run fmm_config.xml
Number of rows read 237211786
Estimated load factor #elements/#tablebuckets 2.13491
Finish reading UBODT.
Delta inferred from ubodt as 0.1
Reading meta data of GPS trajectories from: data/trips0306.shp
Index of ID column: 0
Total number of trajectories: 33
Finish reading meta data
Write result to file: mr0.1_0.1_0.01.txt
Start to map match trajectories with total number 33
Segmentation fault (core dumped)
###############

Sean

In your paper in section 4.2.4 you mentioned four modes of FMM that affect the accuracy and performance of the algorithm (modes are: brute force, optimized, UBODT, Dijkstra). Which mode was implemented in the source code? Is it possible to set it as optimized mode?

Thank you!

Hi,

Does there have some codes to visualise the matching results? Just like the figure of input.pnd and output.png? In addition, for my case, when i set the mode to 2, there is no geo information in the mr.txt, could you give me some guidelines? Thank you very much.

Sean

Hi,
First of all, thank you for such an amazing package. I am trying to achieve the following - I have about 1 million GPS points with speed, latitude, longitude and timestamp. I want to perform map matching on these with OSM roadways data(a shapefile with linestrings) for a particular region, the file structure in example folder is quite confusing to me, could you please explain what would be the nodes.shp and edges.shp file in this case, and also what about the trips.shp file, what does that represent?

When the graph is small but one node in it is extremely large, e.g., 300000, a large graph is created with that 300000 number of nodes where the iteration in ubodt_gen checks the entire graph.

What could be the cause for not matching 100% of the points, if all points are from the original dataset?

=============================
MM process finished
Time takes 275.757
Finish map match total points 4999688 and points matched 4999524
Matched percentage: 0.999967
Point match speed:18130.2pt/s
Clean UBODT
Clean UBODT finished
Cleaning network
Cleaning network finished

<?xml version="1.0" encoding="utf-8"?>
<fmm_config>
    <input>
        <ubodt>
            <file>ubodt-nwb.txt</file>
            <nhash>999983</nhash>
            <multiplier>1815275</multiplier>
        </ubodt>
        <network>
            <file>wegvakken_renumbered_28992.shp</file>
            <id>WVK_ID</id>
            <source>JTE_ID_BEG</source>
            <target>JTE_ID_END</target>
        </network>
        <gps>
            <file>wegvakken_renumbered_28992.shp</file>
            <id>WVK_ID</id>
        </gps>
    </input>
    <parameters>
        <k>4</k>
        <r>100</r>
        <pf>0</pf>
        <gps_error>0.5</gps_error>
    </parameters>
    <output>
        <mode>1</mode>
        <file>mr.txt</file>
    </output>
</fmm_config>

Since i have many cases to run map matching model (C++), bat file would be my basic needs. I have little knowledge on programming. As far as i search the bat script to run cygwin might look like the follows:
"C:\cygwin64\bin\mintty /bin/bash -l c:\path\to\your\script"

However after i run, program just stop and show only the header:

------------ Fast map matching (FMM) ------------
------------ Author: Can Yang ------------
------------ Version: 2018.03.09 ------------
------------ Application: ubodt_gen ------------
Read configuration from xml file: ubodt_config.xml

could you please help on this issue.

Hi,

Thanks for the quick response earlier.

It seems that, even though the README suggests to use a 'delta' of 0.01, that supplying a floating-point delta is not read by the ubodt config. Instead, if you enter something like 0.01 or 3.1 then it falls back to the default of '5000' (which is gigantic in case of degrees...)

Thanks,
Tias