CN103162702B - Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling - Google Patents
Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling Download PDFInfo
- Publication number
- CN103162702B CN103162702B CN201310070036.2A CN201310070036A CN103162702B CN 103162702 B CN103162702 B CN 103162702B CN 201310070036 A CN201310070036 A CN 201310070036A CN 103162702 B CN103162702 B CN 103162702B
- Authority
- CN
- China
- Prior art keywords
- probability
- vehicle driving
- driving trace
- search
- sparse sampling
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Active
Links
- 238000005070 sampling Methods 0.000 title claims abstract description 35
- 238000000034 method Methods 0.000 title claims abstract description 21
- 230000008878 coupling Effects 0.000 title claims description 29
- 238000010168 coupling process Methods 0.000 title claims description 29
- 238000005859 coupling reaction Methods 0.000 title claims description 29
- 238000004458 analytical method Methods 0.000 claims description 4
- 241001269238 Data Species 0.000 claims description 2
- 238000010586 diagram Methods 0.000 description 5
- 230000000694 effects Effects 0.000 description 2
- 238000005516 engineering process Methods 0.000 description 2
- 230000001149 cognitive effect Effects 0.000 description 1
- 238000005315 distribution function Methods 0.000 description 1
- 238000007689 inspection Methods 0.000 description 1
- 230000013011 mating Effects 0.000 description 1
- 238000012544 monitoring process Methods 0.000 description 1
- 238000003672 processing method Methods 0.000 description 1
- 238000010937 topological data analysis Methods 0.000 description 1
Landscapes
- Traffic Control Systems (AREA)
- Navigation (AREA)
Abstract
The vehicle driving trace reconstructing method that the present invention is mated based on multiple probability under proposing a kind of sparse sampling, first the method utilizes historical data to add up the distribution of sparse sampling point tolerance, and determines region of search; Then in region of search, find candidate matches object (section or crossing), polytype is divided into according to candidate target feature, if without match objects in region of search, do not consider this sampled point, if only have unique object in region of search, sampled point is matched to unique object, if there is multiple candidate target in region of search, utilizes double-deck probability match model to process further; Double-deck probability match model, according to the select probability of the matching probability of sampled point with the Rational Path of its composition, calculates the matching probability of each possibility track, chooses the reconstruct track of track as sparse sampling point of maximum possible probability.The present invention reduces the matching error of sparse sampling data, effectively improve precision and the speed of vehicle driving trace reconstruct in complicated road network.
Description
Technical field
The present invention relates to traffic geography areas of information technology, more specifically, relate to a kind of vehicle driving trace reconstructing method based on multiple probability coupling be applied in complicated road network under sparse sampling.
Background technology
Urban road network complex structure, viaduct complex ground high at road mileage is often difficult to accurate match locator data, especially when sampled point is sparse, and when positioning precision is not high, considerably increases the difficulty of vehicle driving trace reconstruct especially.
The method of Current vehicle driving trace reconstruct can be divided into two classes: a class is matched a little or line by sampled point by map match, then forms vehicle driving trace by shortest path algorithm is connected; Another kind of is overall vehicle driving trace matching algorithm, considers connective while each sampled point of coupling, obtains a series of section series.First kind method, when mating sampled point, generally adopts geometric match, topological analysis, weight coupling etc., and sparse sampled point is difficult to the accuracy ensureing sampled point coupling, and the precision of sampled point coupling have impact on again the precision of vehicle driving trace reconstruct further.Equations of The Second Kind method improves precision by introducing probability match model, delay match model, parallel road Matching Model etc., and complexity is higher; If a certain positional fault coupling, is easy to the matching error causing subsequent sampling point; Due to simple consideration sampled point data characteristics, do not consider the housing choice behavior of the creator driver of vehicle driving trace, time between the especially overhead and common road of road network in the face of complexity, vehicle driving trace quality reconstruction is undesirable.
Summary of the invention
In order to reduce the coupling error caused because sampled point is sparse and precision is not enough in complicated road network, accurately and rapidly reconstruct vehicle driving trace, the vehicle driving trace reconstructing method mated based on multiple probability under the invention provides a kind of sparse sampling.
To achieve these goals, technical scheme of the present invention is:
Based on a vehicle driving trace reconstructing method for multiple probability coupling under sparse sampling, comprise following steps:
S1. gather enough sampled point historical datas and carry out error statistics analysis;
S2. based on the error distribution of historical data statistics sparse sampling point, region of search is determined;
S3. in appointed area, search for candidate matches object, determine match objects type;
S4. the matching probability of calculated candidate match objects and the routing probability of Rational Path;
S5. by double-deck probability match algorithm, most probable vehicle driving trace is determined.
Preferably, the statistical history sampled point data error in described step S1 is with normal distribution matching sampled point error.
Preferably, in described step S2, determine that region of search is centered by sampled point, draw circle with fiducial interval radius for radius and search for.
Preferably, the candidate matches object in described step S3 is: all objects within the scope of the region of search that step S2 determines, are divided three classes according to candidate matches characteristics of objects: zero match objects, single match objects and many match objects.
Preferably, in described step S4, connect each candidate matches object with shortest path algorithm, determine the Rational Path between sampled point, calculate the matching probability of each candidate matches object and the routing probability of Rational Path.
Preferably, in described step S5, adopt double-deck Probability Choice Model, the routing probability of comprehensively sampling Point matching probability and Rational Path thereof, choose most probable track as final reconstruction result.
Compared with prior art, advantage of the present invention is mainly reflected in the following aspects:
1) low to sampled point data demand, Data Source is extensive.With sparse sampling point for data supporting, be applicable to the vehicle driving trace reconstruct under the multiple sampled form such as GPS, base station, radar, video, the testimony of a witness.
2) road network applicability is strong.Be applicable to various road network especially urban complex road network, solve the matching problem of complex cross mouth and through street.
3) matching precision is high.Easily occur that the crossing of matching error is by as single match objects, and take into full account the housing choice behavior of driver, determine vehicle driving trace accurately by double-deck probability model.
4) algorithm complex is low.Algorithm connects candidate matches object with shortest path, only calculates the routing probability of Rational Path, avoid complicated road network especially overpass locate switching problem repeatedly with ordinary road.
Accompanying drawing explanation
Fig. 1 is sampled point error burst statistical graph.
Fig. 2-7 is the candidate matches object schematic diagram of different characteristic.
Fig. 8-10 is the coupling schematic diagram in section in a specific embodiment.
Figure 11-13 be with Milky Way passenger station, Guangzhou to railway station, Guangzhou between go out certain driving trace quality reconstruction schematic diagram of hiring a car.
Embodiment
Below in conjunction with accompanying drawing, the present invention will be further described, but embodiments of the present invention are not limited to this.
Sampling generally refers to the process continuous quantity of time domain or spatial domain being changed into discrete magnitude.Sampling in the present invention refers to process enquiry data sampled as sample size in time domain or the enterprising between-line spacing of spatial domain.The sparse degree difference of sampled result that different sampling rates is corresponding, can ensure reduce sampling number under the condition of data in fidelity range, reduce restructing operation amount by sampling processing.The present invention is devoted to be reconstructed vehicle driving trace under different sampling rate in conjunction with multiple probability Matching Model, invention can either process the reconstructing path problem of general data amount, also can obtain good trajectory reconstruction effect in sparse sampling data situation simultaneously.
Below in conjunction with accompanying drawing, the present invention is further described.
In a particular application, sampled data can be obtained by modes such as GPS, base station, radar, video, the testimony of a witnesies.In example, the vehicle GPS of Guangzhou taxi is utilized to carry out data acquisition.Because sampling time interval is about 20 seconds, the GPS point obtained often miss out some section in track, belongs to sparse sampling.Select the GPS sampled point of certain taxi on July 6th, 2011 from Milky Way passenger station to railway station, Guangzhou and carry out trajectory reconstruction.Whole vehicle driving trace reconstructing method is mainly divided into five steps:
Step 1: the error statistics analysis of sampled point historical data.First the historical data that random acquisition is enough, uses rational probability density function to carry out error statistics analysis and matching distribution function curve, and wherein set μ as vehicle location point distance road axis or intersection node distance expectation value, σ is standard deviation.Example utilizes 4200, Guangzhou GPS data from taxi to carry out statistical study.Through inspection, Guangzhou taxi GPS point and road axis distance error are variable, and it obeys most widely used probability density-normal distribution N (μ, σ
2) function, expectation value μ is 5.5846m, and standard deviation sigma is 14.876m, and distribution plan is shown in Fig. 1.
Step 2: the determination of sampled point region of search.According to the feature of normal distribution, the probabilistic law of the stochastic variable of Normal Distribution is: the probability of the value of more contiguous μ is larger, and from μ more away from the probability of value less.Therefore, in order to cover all matching characteristics as far as possible, invention have selected 99.7% for fiducial interval, and 3 σ are fiducial interval radius, are then set to the center of circle with sample, and fiducial interval radius is justified, search match objects.In example, when standard deviation sigma is 14.876m, when prestige value μ is 5.5846m, fiducial interval radius is 44.628m.So σ fiducial interval in μ ± 3 is (-39.628m ,+49.628m), conveniently calculates, getting interval (-50m ,+50m) is fiducial interval, and now probability is 98%, namely the data point of 98% is in (-50m ,+50m) interval.Therefore by the interval (-50m ,+50m) acceptable area as sparse sampling Point matching error.With GPS point for the center of circle, 50m radius is justified, and the traffic elements such as the path in circle or crossing are candidate matches object.
Step 3: determine sampled point type.Feature according to candidate matches object can be divided three classes: zero match objects, single match objects and many match objects.When sampled point coupling is less than during any traffic element being zero coupling, matching probability is 0; When sampled point matches unique section or unique point of crossing, belong to single coupling, matching probability is 100%; If when candidate matches object is more than 1, be many couplings.According to statistics, different sampled point candidate matches object number proportion is different, as shown in table 1, and single coupling accounting example is 77.05%, only has the sampled data of 21.59% for many couplings.Need to utilize double-deck probability model to screen further.As illustrated in figs. 2-7, Fig. 2 is zero coupling, and Fig. 3,4 is single match objects, Fig. 5,6 and 7 match objects be two or more, be many couplings.
Table 1 object type statistical form
Step 4: sampled point matching probability calculates.Shortest path algorithm is adopted to connect each candidate matches object, be that (H is extensive factor to Rational Path by the H of the bee-line be less than between neighbouring sample point between candidate matches object path definition doubly, desirable 2.0), in routing, only Rational Path is calculated.Make P
kfor kth paths select probability, use multinomial logit model determination routing probability, shown in (1), wherein θ is model parameter, L
kfor the distance impedance of path candidate k, M is candidate road section sum, L
mit is the distance impedance in m article of section.
When N represents the number of the candidate matches object of t sampled point, n represents the n-th candidate matches object, and f (n) represents the Density Function of Normal Distribution that error distributes, so
be the probability that t sampled point is matched on the candidate matches object of k place, path, shown in (2),
As seen in figs. 8-10, in Fig. 8, G
1an object section a is only had, so a is single match objects in point search region; In like manner G
2point matches n completely
1crossing, its shortest path l
11for Rational Path; G
3having two objects in point search territory, is many match objects: crossing n
2with viaduct h, due to n
1the n that distance to h is greater than 2 times
1to n
2distance, therefore l
21for Rational Path, l
22for unreasonable path; In like manner, G is released
4g
6each point Rational Path; Finally obtain a path candidate, its matching probability is 100%.
Fig. 9 is the schematic diagram of sampled point, and Figure 10 is matching characteristic schematic diagram.
Step 5: vehicle operating trajectory reconstruction.Double-deck preference pattern is used to determine different route selection probability, shown in (3).
P in formula (3)
kfor kth paths select probability during many match objects,
the matching probability of the object of t point on k path during many couplings, T represents the number of many match objects point.Finally select P
k' middle maximum probability person is the vehicle driving trace of reconstruct.By 35 GPS sparse sampling G in example
1g
2g
35composition.As G
1for single match point, match objects is crossing 1089, G
2for single match point, match objects is section 827 (Tian Yuan road).G
34many couplings, match objects has inner ring road A Xian Hehuanshi West Road.Fortune is for being Rational Path with the matching probability of formula 1 and 2 calculating path select probability and point and double-deck preference pattern known inner ring road A line.Determine sparse sampling point G successively
1g
35matching probability between each point, as shown in Figure 11,12.Finally reconstruct rational vehicle driving trace, the vehicle driving trace effect constructed as shown in figure 13.
First the present invention adds up the error distributed area of sparse sampling point, utilizes this interval to search for the road element alternatively match objects that may mate.Mate completely for belonging to during single match objects in interval; If candidate matches object is more than one, as crossing has many sections to intersect or place parallel with surface road, viaduct, multinomial Logit path Choice Model then in conjunction with the cognitive impedance of traveler calculates, comprehensive candidate matches object matching probability is selected with the Rational Path being connected candidate matches object, obtains final route matching probability.Single match objects accounts for more than 3/4ths according to statistics, reduces the possible path number connecting candidate matches object, ensure that the precision of coupling simultaneously.Data processing method of the present invention fast, rationally, and can take into full account the housing choice behavior of driver, is adapted at carrying out vehicle driving trace reconstruct to sparse sampling point in urban complex road network, can be widely used in the fields such as navigation, monitoring, traffic behavior research.
Above-described embodiments of the present invention, do not form limiting the scope of the present invention.Any make within spiritual principles of the present invention amendment, equivalent to replace and improvement etc., all should be included within claims of the present invention.
Claims (6)
1. under sparse sampling based on multiple probability coupling a vehicle driving trace reconstructing method, it is characterized in that, comprise following steps:
S1. gather enough sampled point historical datas and carry out error statistics analysis;
S2. based on the error distribution of historical data statistics sparse sampling point, region of search is determined;
S3. in appointed area, search for candidate matches object, determine match objects type;
S4. the matching probability of calculated candidate match objects and the routing probability of Rational Path;
Make P
kfor kth paths select probability, use multinomial logit model determination routing probability, shown in (1), wherein θ is model parameter, L
kfor the distance impedance of path candidate k, M is candidate road section sum, L
mit is the distance impedance in m article of section;
When N represents the number of the candidate matches object of t sampled point, n represents the n-th candidate matches object, and f (n) represents the Density Function of Normal Distribution that error distributes, so
be the probability that t sampled point is matched on the candidate target of k place, path, shown in (2),
S5. by double-deck probability match algorithm, most probable vehicle driving trace is determined;
Double-deck preference pattern is used to determine different route selection probability, shown in (3);
P in formula (3)
kfor kth paths select probability during many match objects,
the matching probability of the object of t point on k path during many couplings, T represents the number of many match objects point.
2. under sparse sampling according to claim 1 based on multiple probability coupling vehicle driving trace reconstructing method, it is characterized in that, the statistical history sampled point data error in described step S1 is with normal distribution matching sampled point error.
3. under sparse sampling according to claim 1 based on multiple probability coupling vehicle driving trace reconstructing method, it is characterized in that, in described step S2, determine that region of search is centered by sampled point, with fiducial interval radius for radius draw circle search for.
4. under sparse sampling according to claim 1 based on multiple probability coupling vehicle driving trace reconstructing method, it is characterized in that, candidate matches object in described step S3 is: all objects within the scope of the region of search that step S2 determines, are divided three classes according to candidate matches characteristics of objects: zero match objects, single match objects and many match objects.
5. under sparse sampling according to claim 1 based on multiple probability coupling vehicle driving trace reconstructing method, it is characterized in that, in described step S4, each candidate matches object is connected with shortest path algorithm, determine the Rational Path between sampled point, calculate the matching probability of each candidate matches object and the routing probability of Rational Path.
6. under sparse sampling according to claim 1 based on multiple probability coupling vehicle driving trace reconstructing method, it is characterized in that, in described step S5, adopt double-deck Probability Choice Model, the routing probability of comprehensively sampling Point matching probability and Rational Path thereof, chooses most probable track as final reconstruction result.
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310070036.2A CN103162702B (en) | 2013-03-05 | 2013-03-05 | Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201310070036.2A CN103162702B (en) | 2013-03-05 | 2013-03-05 | Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling |
Publications (2)
| Publication Number | Publication Date |
|---|---|
| CN103162702A CN103162702A (en) | 2013-06-19 |
| CN103162702B true CN103162702B (en) | 2016-04-06 |
Family
ID=48585982
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201310070036.2A Active CN103162702B (en) | 2013-03-05 | 2013-03-05 | Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN103162702B (en) |
Families Citing this family (17)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN103745300B (en) * | 2013-12-16 | 2017-12-15 | 交控科技股份有限公司 | A kind of wire examination method and equipment |
| CN104050832B (en) * | 2014-05-23 | 2017-06-20 | 北京中交兴路信息科技有限公司 | The complementing method and device of positional information |
| CN105222768A (en) * | 2014-06-30 | 2016-01-06 | 奇点新源国际技术开发(北京)有限公司 | A kind of positioning track Forecasting Methodology and device |
| CN105335597B (en) * | 2014-07-30 | 2019-04-16 | 国际商业机器公司 | For obtaining the method and system of the trajectory model of route |
| CN105371863B (en) * | 2014-08-27 | 2019-01-04 | 中国移动通信集团公司 | A kind of information cuing method and device |
| US10013508B2 (en) * | 2014-10-07 | 2018-07-03 | Toyota Motor Engineering & Manufacturing North America, Inc. | Joint probabilistic modeling and inference of intersection structure |
| CN106326254B (en) * | 2015-06-25 | 2019-08-30 | 阿里巴巴集团控股有限公司 | The restorative procedure and device of planning driving path |
| CN105788252B (en) * | 2016-03-22 | 2018-05-01 | 连云港杰瑞电子有限公司 | Arterial street track of vehicle reconstructing method based on fixed point detector and signal timing dial data fusion |
| CN106023587B (en) * | 2016-05-25 | 2018-07-27 | 电子科技大学 | Track data road network fine matching method based on Multi-information acquisition |
| CN106023589B (en) * | 2016-06-16 | 2018-04-10 | 北京航空航天大学 | A kind of track of vehicle reconstructing method based on bayonet socket data |
| CN106407378B (en) * | 2016-09-11 | 2020-05-26 | 复旦大学 | Method for re-representing road network track data |
| US10691129B2 (en) * | 2018-01-31 | 2020-06-23 | Baidu Usa Llc | Dynamically adjustable reference line sampling point density for autonomous vehicles |
| CN110160541B (en) * | 2018-08-06 | 2022-02-22 | 腾讯大地通途（北京）科技有限公司 | Method and device for reconstructing motion trail, storage medium and electronic device |
| CN110006439B (en) * | 2019-04-12 | 2021-01-29 | 北京百度网讯科技有限公司 | Map track data matching method, map track data matching device, server and storage medium |
| CN111060112A (en) * | 2019-12-12 | 2020-04-24 | 南京航空航天大学 | Vehicle track map matching method and system based on direction angle |
| CN111982141B (en) * | 2020-07-31 | 2022-09-13 | 长安大学 | Method, equipment and storage medium for path inference for low-frequency vehicle trajectory data |
| CN113587944B (en) * | 2021-06-24 | 2024-03-29 | 深圳市跨越新科技有限公司 | Quasi-real-time vehicle driving route generation method, system and equipment |
Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1948913A (en) * | 2006-08-25 | 2007-04-18 | 北京航空航天大学 | Heuristic path culculating method for treating large scale floating vehicle data |
-
2013
- 2013-03-05 CN CN201310070036.2A patent/CN103162702B/en active Active
Patent Citations (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN1948913A (en) * | 2006-08-25 | 2007-04-18 | 北京航空航天大学 | Heuristic path culculating method for treating large scale floating vehicle data |
Non-Patent Citations (2)
| Title |
|---|
| Dial交通量分配模型和选择概率问题的研究;程琳等;《交通运输系统工程与信息》;20020831;第2卷(第3期);29-32 * |
| GPS导航系统中的地图匹配算法;王敏等;《计算机工程》;20120731;第3卷(第14期);259-261 * |
Also Published As
| Publication number | Publication date |
|---|---|
| CN103162702A (en) | 2013-06-19 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| CN103162702B (en) | Based on the vehicle driving trace reconstructing method of multiple probability coupling under sparse sampling | |
| CN105138779B (en) | Vehicle GPS space-time track big data method for optimizing and system | |
| CN102183256B (en) | Map matching method for marching fleet | |
| CN105628033B (en) | A kind of map-matching method based on path connected relationship | |
| CN104700617B (en) | Based on the high precision track information extracting method of low precision GPS track data | |
| US7516041B2 (en) | System and method for identifying road features | |
| CN110008872B (en) | Road network extraction method combining vehicle track and remote sensing image | |
| CN104121915B (en) | A kind of road real-time navigation method and system | |
| CN108036794A (en) | A kind of high accuracy map generation system and generation method | |
| CN104197945A (en) | Global voting map matching method based on low-sampling-rate floating vehicle data | |
| CN106197460B (en) | A method of it is predicted with carrying out trip purpose using GPS trip data | |
| CN108170793A (en) | Dwell point analysis method and its system based on vehicle semanteme track data | |
| CN105203116A (en) | Map matching method based on conditional random fields and low-sampling-frequency floating car data | |
| CN105241465A (en) | Road update method | |
| CN105489004B (en) | The bayonet and floating car data fusion method calculated towards road real-time speed | |
| CN103680127A (en) | A method for calculating signal lamp control road intersection delays through the utilization of low sampling rate floating vehicle data | |
| CN106781478A (en) | A kind of trace tracking method based on LTE signaling datas | |
| CN110285817B (en) | Complex road network map matching method based on self-adaptive D-S evidence theory | |
| CN110555992A (en) | taxi driving path information extraction method based on GPS track data | |
| CN108253974A (en) | Floating Car location data automatic adaptation cushion route matching system and method | |
| CN108765961A (en) | A kind of floating car data processing method based on modified amplitude limit average filter | |
| CN106705976A (en) | Road network matching method and road network matching device | |
| CN107484139A (en) | A kind of car networking Cooperative Localization Method and device based on geographical location information | |
| CN106980129A (en) | A kind of movement locus comparison method based on position encoded map | |
| CN107452207B (en) | Floating car data source evaluation method, device and system |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| C06 | Publication | ||
| PB01 | Publication | ||
| C10 | Entry into substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| C14 | Grant of patent or utility model | ||
| GR01 | Patent grant |