CN107289961A - 一种基于分区和总结生成便于用户理解的导航信息的方法 - Google Patents
一种基于分区和总结生成便于用户理解的导航信息的方法 Download PDFInfo
- Publication number
- CN107289961A CN107289961A CN201710586815.6A CN201710586815A CN107289961A CN 107289961 A CN107289961 A CN 107289961A CN 201710586815 A CN201710586815 A CN 201710586815A CN 107289961 A CN107289961 A CN 107289961A
- Authority
- CN
- China
- Prior art keywords
- mrow
- msub
- mover
- trajectory
- feature
- 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.)
- Pending
Links
- 238000000034 method Methods 0.000 title claims abstract description 20
- 238000005192 partition Methods 0.000 claims abstract description 80
- 238000010606 normalization Methods 0.000 claims description 9
- 239000013598 vector Substances 0.000 claims description 9
- 238000004364 calculation method Methods 0.000 claims description 7
- 238000010276 construction Methods 0.000 claims description 3
- 230000001788 irregular Effects 0.000 description 8
- 238000011161 development Methods 0.000 description 3
- 239000012634 fragment Substances 0.000 description 3
- 238000000638 solvent extraction Methods 0.000 description 3
- 238000005516 engineering process Methods 0.000 description 2
- 238000012986 modification Methods 0.000 description 2
- 230000004048 modification Effects 0.000 description 2
- 230000002776 aggregation Effects 0.000 description 1
- 238000004220 aggregation Methods 0.000 description 1
- 230000009286 beneficial effect Effects 0.000 description 1
- 238000004891 communication Methods 0.000 description 1
- 230000007812 deficiency Effects 0.000 description 1
- 238000013461 design Methods 0.000 description 1
- 238000002474 experimental method Methods 0.000 description 1
- 230000006698 induction Effects 0.000 description 1
- 230000008447 perception Effects 0.000 description 1
- 238000013519 translation Methods 0.000 description 1
Classifications
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3407—Route searching; Route guidance specially adapted for specific applications
- G01C21/3415—Dynamic re-routing, e.g. recalculating the route when the user deviates from calculated route or after detecting real-time traffic data or accidents
-
- G—PHYSICS
- G01—MEASURING; TESTING
- G01C—MEASURING DISTANCES, LEVELS OR BEARINGS; SURVEYING; NAVIGATION; GYROSCOPIC INSTRUMENTS; PHOTOGRAMMETRY OR VIDEOGRAMMETRY
- G01C21/00—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00
- G01C21/26—Navigation; Navigational instruments not provided for in groups G01C1/00 - G01C19/00 specially adapted for navigation in a road network
- G01C21/34—Route searching; Route guidance
- G01C21/3446—Details of route searching algorithms, e.g. Dijkstra, A*, arc-flags or using precalculated routes
Landscapes
- Engineering & Computer Science (AREA)
- Radar, Positioning & Navigation (AREA)
- Remote Sensing (AREA)
- Automation & Control Theory (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Navigation (AREA)
Abstract
本发明公开了一种基于分区和总结生成便于用户理解的导航信息的方法，包括：S1：将原始轨迹转换为符号轨迹；S2：将符号轨迹进行划分，形成轨迹分区；S3：在每个轨迹分区中选择最有意义的特征来描述物体的运动情况；S4：将选取的特征插入预先定义好的模板中，形成对轨迹进行有效描述的文本。本发明将在轨迹分区划分阶段，定义每个轨迹分区的一系列特征，然后产生一个最佳分区，使每个分区内的运动行为尽可能地相似，在文本总结阶段，通过比较历史轨迹的相似行为，我们在每个分区内选取了最有意义的特征，并对这些特征生成了简洁的文本描述，文本清晰、简洁，便于人们理解运动的细节特征。
Description
技术领域
本发明涉及导航技术领域，尤其涉及是一种基于分区和总结生成便于用户理解的导航信息的方法。
背景技术
导航应用是一种在路网中找到最佳路线和相应的转弯方向的应用。现有导航应用提供的由转弯方向(turn-by-turn)构成的导航服务，是专门从底端路网中提取信息而得来的。所以，它很容易被转换成物理世界的信息去讲述(多远/多久转方向)。但是这种翻译，忽略了人类对地理空间的认知，对于了解地理区域的司机来说，往往很冗长。大多数道路上的司机都有良好的城市知识和熟悉道路网络中的某些部分，他们采取的路线，(例如，路线从家到附近的公路，可以被一句话概述：从家到XXX公路；而不是：前面XX米左转，……)。因此，如果对司机熟悉的部分道路，也使用现有导航应用的转弯方向导航，那么实际上导航系统将是十分冗余和复杂的，相应的导航程序对资源的需求也高，导致导航应用的开发成本和运营成本也高。并且，如果一直使用逐转方向导航，用户接收到的信息通常是“前方XX米左转、前方XX米右转、前方直行XX米左转，……”，用户接收到的导航信息单一，难以满足个性化的导航需求。尤其是随着移动互联网技术的发展，移动设备和车载导航系统的导航应用地不断增长，积累了大量的用户生成的轨迹数据，使用这些大数据产生更有效的、更容易被人理解的导航信息是非常有用的。
由于GPS和无线通信技术的快速发展，描述运动物体的运动历史的空间轨迹正在以前所未有的速度形成和累积。由时间戳位置(经度、纬度和时间)顺序形成的原始轨迹对于人们来说是没有任何意义的，因为人们并不能理解其代表什么含义。为了解决这一问题，本申请提出了轨迹划分和文本归纳框架，最终将简洁的、有代表性的导航信息发送给用户。
发明内容
本发明的目的在于克服现有技术的不足，提供种基于分区和总结生成便于用户理解的导航信息的方法，向用户发送简洁的、有代表性的导航信息。
本发明的目的是通过以下技术方案来实现的：一种基于分区和总结生成便于用户理解的导航信息的方法，包括：
S1：将原始轨迹T转换为符号轨迹
S2：将符号轨迹进行划分，形成轨迹分区
S3：在每个轨迹分区中选择最有意义的特征来描述物体的运动情况；
S4：将选取的特征插入预先定义好的模板中，形成对轨迹进行有效描述的文本。
进一步地，在步骤S2中，包括如下步骤：
S21：将符号轨迹划分成个轨迹片段
S22：归一化的每个特征，为使每个特征的归一化值在0和1之间，归一化常量n为该分区内所有特征的最大值；
S23：在步骤二中完成归一化后，轨迹片段的所有特征F形成了一个|F|维的向量用户指定每个特征的权重为w，所有特征的权重w形成了一个|F|维的向量用以下公式计算两个向量之间的相似性：
其中，和分别代表和的特征向量；和分别代表第j维的值，即第j个特征fj的值，代表特征fj的权重；
S24：在无向图G(V,E)上定义CRF模型公式，计算：
其中，
Ca是由用户指定的正常数，反映了地标意义的重要性，使该等式值为最大，得到Xi的最佳序列Xopt，将轨迹片段的Xi值相同的轨迹片段划分为一个分区，从而得到轨迹的最佳分区；
S25：找到最佳的k分区，用户指定将轨迹划分为k个分区，用(i,j)代表在i个轨迹片段分成了j个分区后，前i个轨迹片段的的最小值，即：
令(1，1)＝0，X1＝1，若时，则Xi＝Xi-1+1；若时，则Xi＝Xi-1；
其中(i,i)代表每个轨迹片段都是一个分区；(i,1)代表前i个轨迹片段都属于同一个分区；再按照步骤四中求最佳分区的步骤求得Xi的最佳序列Xopt；
将相同Xi的轨迹片段划分为同一分区，从而得到最佳的k分区。
进一步地，在步骤S24中：计算前i个轨迹片段的的最小值，即用(i)表示：
令(1)＝0，X1＝1，若时，Xi＝Xi-1+1；
若时，则Xi＝Xi-1。
进一步地，所述计算最佳序列Xopt，等价于计算的最大值；
所述计算的最大值，等价于计算的最小值。
进一步地，在步骤S3中，包括：选择路线特征和选择运动特征。
进一步地，所述的选择路线特征，包括如下步骤：
S301：从历史轨迹中提取
S302：将路线特征f归一化得到特征序列
其中， 是采集的轨迹特征集合；
并且，将的路线特征归一化得到特征序列
S303：计算轨迹片段的不规则率转化为计算和的距离，利用下列公式求得和的距离
其中，rest(·)返回特征值序列除了第一个特征值外的其余所有特征值，head(·)返回特征值序列第一个特征值；
S304：计算路线特征f的不规则率
其中，wf是用户指定的特征f的权重；length(·)是集合序列中元素的个数；
进一步地，在步骤S304中：
对于可数字化的路线特征f：
对于分种类的路线特征f：
进一步地，所述的选择运动特征，包括如下步骤：
S311：在每个轨迹分区下，从历史轨迹中提取出每个特征的值，使用有向图G(V,E)表示历史轨迹特征图，用于归纳两个地标之间的特征f，然后构建历史轨迹特征地图；
S312：使用如下公式计算每个轨迹分区下的每个运动特征的不规则率
其中，wf是用户指定的特征f的权重，norm(·)返回的是归一化值，归一化常量n为该分区内所有轨迹片段中的特征f的最大值；是的特征f的平均值，直接从历史轨迹特征地图上得到，是轨迹片段在特征f上的值，是该分区中轨迹片段的个数。
进一步地，在步骤S311中，所述的构建历史轨迹特征地图，包括如下子步骤：
S3111：给定地标集，历史符号轨迹数据集和选定的运动物体的特征f；
S3112：将地标集中的每个地标添加到历史轨迹特征图的顶点集V中；
S3113：添加有向边，如果在历史符号轨迹数据集中存在从li到lj的轨迹那么添加一条从li指向lj的有向边e(li,lj)；
S3114：用轨迹T(li→lj)的特征f的平均值标注每条边。
本发明的有益效果是：
(1)将选取的特征插入预先定义好的模板中，形成对轨迹进行有效描述的文本。该文本清晰、简洁，便于人们理解运动的细节特征。
(2)本发明在轨迹分区划分阶段，定义每个轨迹分区的一系列特征，然后产生一个最佳分区，使每个分区内的运动行为尽可能地相似，在文本总结阶段，通过比较历史轨迹的相似行为，我们在每个分区内选取了最有意义的特征，并对这些特征生成了简洁的文本描述。
(3)本发明通过将原始轨迹符号化后形成符号轨迹，并将符号轨迹作为该算法的输入，输出为轨迹划分的结果，可以将导航路径分成几个部分，从而使得导航仪在每个路段分别向用户提供更加准确的反馈信息。
(4)本发明在每个分区的起始地和目的地都是非常知名的，或者是比较重要的地标，使每个分区的起始地和目的地的路标最有意义。由于在同一分区内的轨迹片段具有相似特征，使每个分区的运动特征和路线特征信息聚合达到最大，最终使同一分区内的运动特征和路线特征差异达到最小。
(5)基于本发明的路径划分方法，利用历史轨迹数据，可以提供个性化的转弯方向，向城市通勤者提供个性化的导航方向，可以降低路径导航冗余，在真实和合成的轨迹数据集上进行了大量的实验，结果表明，适当数量的已知路线，可以减少冗余导航的数量超过60％，同时仍然能提供足够的信息，为用户引导路线。
(6)本发明通过在每个轨迹分区里选取了最不规则的运动特征来描述运动行为，既简洁扼要、便于用户理解，又能将该轨迹分区里最主要的运动特征表现出来；将每个轨迹分区的所有的运动特征作为算法的输入，输出为用于描述该轨迹分区的运动特征，该算法可以使导航仪将该路段最具代表性的运动特征呈现给用户。选取的运动特征是不规则运动特征，这些不规则特征的值不同于正常情况下的值，本发明主要解决了选取最不规则的运动特征来描述每一轨迹分区的运动行为的技术问题。
(7)本发明通过在每个轨迹分区里选取了最不则的路线特征来描述运动行为，既简洁扼要、便于用户理解，又能将该轨迹分区里最主要的路线特征表现出来；将每个轨迹分区的所有的路线特征作为算法的输入，输出为用于描述该轨迹分区的路线特征，可以使导航仪将该路段最具代表性的路线特征呈现给用户；所选取的运动特征是不规则运动特征，这些不规则特征的值不同于正常情况下的值，解决了选取最不规则的运动特征来描述每一轨迹分区的运动行为的技术问题。
附图说明
图1为本发明的方法步骤流程图。
具体实施方式
下面结合附图进一步详细描述本发明的技术方案，但本发明的保护范围不局限于以下所述。
实施例一
概念定义和符号表示：
原始轨迹T：是由从运动物体的运动路线抽样得到的坐标和与之对应的时间戳构成的一个有穷序列，即：T＝[(p1,t1),(p2,t2),…,(pn,tn)]。
地标l：是空间中的一个地理位置，它是稳定的、独立于轨迹。
符号轨迹是由地标和与之对应的时间戳构成的一个序列，即
轨迹片段轨迹中连接两个相邻地标li和li+1的子轨迹称为
轨迹分区由一些连续的轨迹片段组成的子轨迹。
地标意义l.s：衡量人们对地标l的熟悉度。
f：轨迹的一个特征。
轨迹的所有相关特征。
轨迹片段的特征f的值。
从li到li+j的最流行的历史路线。
轨迹中地标的数量。
特征分为路线特征和运动特征。路线特征包括路的等级、路宽和方向，运动特征包括速度、停留次数和U型急转弯次数。详细信息如下表：
为了使归纳总结文本既简洁、便于用户理解，又满足用户的需求。故选取的特征应该是最不规则的特征。不规则率比用户指定的阈值高的所有特征都应被写入总结归纳中。我们分别设计了路线特征和运动特征的不规则率的方法。
如图1所示，一种基于分区和总结生成便于用户理解的导航信息的方法，包括：
S1：将原始轨迹T转换为符号轨迹
S2：将符号轨迹进行划分，形成轨迹分区
S3：在每个轨迹分区中选择最有意义的特征来描述物体的运动情况；
S4：将选取的特征插入预先定义好的模板中，形成对轨迹进行有效描述的文本。
进一步地，在步骤S2中，包括如下步骤：
S21：将符号轨迹划分成个轨迹片段
S22：归一化的每个特征，为使每个特征的归一化值在0和1之间，归一化常量n为该分区内所有特征的最大值；
S23：在步骤二中完成归一化后，轨迹片段的所有特征F形成了一个|F|维的向量用户指定每个特征的权重为w，所有特征的权重w形成了一个|F|维的向量用以下公式计算两个向量之间的相似性：
其中，和分别代表和的特征向量；和分别代表第j维的值，即第j个特征fj的值，代表特征fj的权重；
S24：在无向图G(V,E)上定义CRF模型公式，计算：
其中，
Ca是由用户指定的正常数，反映了地标意义的重要性，使该等式值为最大，得到Xi的最佳序列Xopt，将轨迹片段的Xi值相同的轨迹片段划分为一个分区，从而得到轨迹的最佳分区；
S25：找到最佳的k分区，用户指定将轨迹划分为k个分区，用(i,j)代表在i个轨迹片段分成了j个分区后，前i个轨迹片段的的最小值，即：
令(1，1)＝0，X1＝1，若时，则Xi＝Xi-1+1；若时，则Xi＝Xi-1；
其中(i,i)代表每个轨迹片段都是一个分区；(i,1)代表前i个轨迹片段都属于同一个分区；再按照步骤四中求最佳分区的步骤求得Xi的最佳序列Xopt；
将相同Xi的轨迹片段划分为同一分区，从而得到最佳的k分区。
进一步地，在步骤S24中：计算前i个轨迹片段的的最小值，即用(i)表示：
令(1)＝0，X1＝1，若时，Xi＝Xi-1+1；
若时，则Xi＝Xi-1。
进一步地，所述计算最佳序列Xopt，等价于计算的最大值；
所述计算的最大值，等价于计算的最小值。
进一步地，在步骤S3中，包括：选择路线特征和选择运动特征。
进一步地，所述的选择路线特征，包括如下步骤：
S301：从历史轨迹中提取
S302：将路线特征f归一化得到特征序列
其中， 是采集的轨迹特征集合；
并且，将的路线特征归一化得到特征序列
S303：计算轨迹片段的不规则率转化为计算和的距离，利用下列公式求得和的距离
其中，rest(·)返回特征值序列除了第一个特征值外的其余所有特征值，head(·)返回特征值序列第一个特征值。
S304：计算路线特征f的不规则率
其中，wf是用户指定的特征f的权重；length(·)是集合序列中元素的个数。
进一步地，在步骤S304中：
对于可数字化的路线特征f：
对于分种类的路线特征f：
进一步地，所述的选择运动特征，包括如下步骤：
S311：在每个轨迹分区下，从历史轨迹中提取出每个特征的值，使用有向图G(V,E)表示历史轨迹特征图，用于归纳两个地标之间的特征f，然后构建历史轨迹特征地图；
S312：使用如下公式计算每个轨迹分区下的每个运动特征的不规则率
其中，wf是用户指定的特征f的权重，norm(·)返回的是归一化值，归一化常量n为该分区内所有轨迹片段中的特征f的最大值；是的特征f的平均值，直接从历史轨迹特征地图上得到，是轨迹片段在特征f上的值，是该分区中轨迹片段的个数。
进一步地，在步骤S311中，所述的构建历史轨迹特征地图，包括如下子步骤：
S3111：给定地标集，历史符号轨迹数据集和选定的运动物体的特征f；
S3112：将地标集中的每个地标添加到历史轨迹特征图的顶点集V中；
S3113：添加有向边，如果在历史符号轨迹数据集中存在从li到lj的轨迹那么添加一条从li指向lj的有向边e(li,lj)；
S3114：用轨迹T(li→lj)的特征f的平均值标注每条边。
本申请中，head(.)，length(.)等是现有技术中标准的编辑距离(edit distance)的表示方法，例如表示和的距离。
以上所述仅是本发明的优选实施方式，应当理解本发明并非局限于本文所披露的形式，不应看作是对其他实施例的排除，而可用于各种其他组合、修改和环境，并能够在本文所述构想范围内，通过上述教导或相关领域的技术或知识进行改动。而本领域人员所进行的改动和变化不脱离本发明的精神和范围，则都应在本发明所附权利要求的保护范围内。
Claims (9)
1.一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于，包括：
S1：将原始轨迹T转换为符号轨迹
S2：将符号轨迹进行划分，形成轨迹分区
S3：在每个轨迹分区中选择最有意义的特征来描述物体的运动情况；
S4：将选取的特征插入预先定义好的模板中，形成对轨迹进行有效描述的文本。
2.根据权利要求1所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于，在步骤S2中，包括如下步骤：
S21：将符号轨迹划分成个轨迹片段
S22：归一化的每个特征，为使每个特征的归一化值在0和1之间，归一化常量n为该分区内所有特征的最大值；
S23：在步骤二中完成归一化后，轨迹片段的所有特征F形成了一个|F|维的向量用户指定每个特征的权重为w，所有特征的权重w形成了一个|F|维的向量用以下公式计算两个向量之间的相似性：
<mrow>
<mi>S</mi>
<mrow>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mfrac>
<mn>1</mn>
<mn>2</mn>
</mfrac>
<mo>&CenterDot;</mo>
<mrow>
<mo>(</mo>
<mfrac>
<mrow>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mo>|</mo>
<mi>F</mi>
<mo>|</mo>
</mrow>
</munderover>
<msub>
<mover>
<mi>w</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
</msub>
<mo>&CenterDot;</mo>
<msub>
<mover>
<mi>u</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
</msub>
<mo>&CenterDot;</mo>
<msub>
<mover>
<mi>v</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
</msub>
</mrow>
<mrow>
<msqrt>
<mrow>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mo>|</mo>
<mi>F</mi>
<mo>|</mo>
</mrow>
</munderover>
<msub>
<mover>
<mi>w</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
</msub>
<mo>&CenterDot;</mo>
<msubsup>
<mover>
<mi>u</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
<mn>2</mn>
</msubsup>
</mrow>
</msqrt>
<mo>&CenterDot;</mo>
<msqrt>
<mrow>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>j</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mo>|</mo>
<mi>F</mi>
<mo>|</mo>
</mrow>
</munderover>
<msub>
<mover>
<mi>w</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
</msub>
<mo>&CenterDot;</mo>
<msubsup>
<mover>
<mi>v</mi>
<mo>&RightArrow;</mo>
</mover>
<mi>j</mi>
<mn>2</mn>
</msubsup>
</mrow>
</msqrt>
</mrow>
</mfrac>
<mo>+</mo>
<mn>1</mn>
<mo>)</mo>
</mrow>
</mrow>
其中，和分别代表和的特征向量；和分别代表 第j维的值，即第j个特征fj的值，代表特征fj的权重；
S24：在无向图G(V,E)上定义CRF模型公式，计算：
<mrow>
<mi>Pr</mi>
<mrow>
<mo>(</mo>
<mi>X</mi>
<mo>|</mo>
<mover>
<mi>T</mi>
<mo>&OverBar;</mo>
</mover>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mfrac>
<mn>1</mn>
<mi>Z</mi>
</mfrac>
<mi>exp</mi>
<mo>{</mo>
<mo>-</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mo>|</mo>
<mover>
<mi>T</mi>
<mo>&OverBar;</mo>
</mover>
<mo>|</mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</munderover>
<mi>&Phi;</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>X</mi>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mi>X</mi>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>)</mo>
</mrow>
<mo>}</mo>
<mo>,</mo>
<mi>Z</mi>
<mo>=</mo>
<munder>
<mo>&Sigma;</mo>
<msub>
<mi>X</mi>
<mi>i</mi>
</msub>
</munder>
<mi>exp</mi>
<mo>{</mo>
<mo>-</mo>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>i</mi>
<mo>=</mo>
<mn>1</mn>
</mrow>
<mrow>
<mo>|</mo>
<mover>
<mi>T</mi>
<mo>&OverBar;</mo>
</mover>
<mo>|</mo>
<mo>-</mo>
<mn>1</mn>
</mrow>
</munderover>
<mi>&Phi;</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>X</mi>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mi>X</mi>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>i</mi>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>)</mo>
</mrow>
<mo>}</mo>
</mrow>
其中，
Ca是由用户指定的正常数，反映了地标意义li·s的重要性，使该等式值为最大，得到Xi的最佳序列Xopt，将轨迹片段的Xi值相同的轨迹片段划分为一个分区，从而得到轨迹的最佳分区；
S25：找到最佳的k分区，用户指定将轨迹划分为k个分区，用(i,j)代表在i个轨迹片段分成了j个分区后，前i个轨迹片段的的最小值，即：
令(1，1)＝0，X1＝1，若(i，j)＝(i-1,j-1)-Ca·li·s时，则Xi＝Xi-1+1；若时，则Xi＝Xi-1；
其中(i,i)代表每个轨迹片段都是一个分区；(i,1)代表前i个轨迹片段都属于同一个分区；再按照步骤四中求最佳分区的步骤求得Xi的最佳序列Xopt；
将相同Xi的轨迹片段划分为同一分区，从而得到最佳的k分区。
3.根据权利要求2所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于，在步骤S24中：计算前i个轨迹片段的的最小值，即用(i)表示：
<mrow>
<mo>(</mo>
<mi>i</mi>
<mo>)</mo>
<mo>=</mo>
<mi>m</mi>
<mi>i</mi>
<mi>n</mi>
<mfenced open = "{" close = "">
<mtable>
<mtr>
<mtd>
<mo>(</mo>
<mi>i</mi>
<mo>-</mo>
<mn>1</mn>
<mo>)</mo>
<mo>-</mo>
<msub>
<mi>C</mi>
<mi>a</mi>
</msub>
<mo>&CenterDot;</mo>
<msub>
<mi>l</mi>
<mrow>
<mi>i</mi>
<mo>&CenterDot;</mo>
</mrow>
</msub>
<mi>s</mi>
</mtd>
</mtr>
<mtr>
<mtd>
<mo>(</mo>
<mi>i</mi>
<mo>-</mo>
<mn>1</mn>
<mo>)</mo>
<mo>-</mo>
<mi>S</mi>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>,</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>i</mi>
</msub>
<mo>)</mo>
</mtd>
</mtr>
</mtable>
</mfenced>
</mrow>
令(1)＝0，X1＝1，若(i)＝(i-1)-Ca·li·s时，Xi＝Xi-1+1；
若时，则Xi＝Xi-1。
4.根据权利要求2所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于：所述计算最佳序列Xopt，等价于计算的最大值；
所述计算的最大值，等价于计算的最小值。
5.根据权利要求1所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于：在步骤S3中，包括：选择路线特征和选择运动特征。
6.根据权利要求5所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于，所述的选择路线特征，包括如下步骤：
S301：从历史轨迹中提取
S302：将路线特征f归一化得到特征序列
<mrow>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>=</mo>
<mo>&lsqb;</mo>
<mi>n</mi>
<mi>o</mi>
<mi>r</mi>
<mi>m</mi>
<mrow>
<mo>(</mo>
<mrow>
<mi>f</mi>
<mrow>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>i</mi>
</msub>
<mo>)</mo>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
<mo>,</mo>
<mi>n</mi>
<mi>o</mi>
<mi>r</mi>
<mi>m</mi>
<mrow>
<mo>(</mo>
<mrow>
<mi>f</mi>
<mrow>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>)</mo>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
<mo>,</mo>
<mn>...</mn>
<mo>,</mo>
<mi>n</mi>
<mi>o</mi>
<mi>r</mi>
<mi>m</mi>
<mrow>
<mo>(</mo>
<mrow>
<mi>f</mi>
<mrow>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mi>j</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</msub>
<mo>)</mo>
</mrow>
</mrow>
<mo>)</mo>
</mrow>
<mo>&rsqb;</mo>
</mrow>
其中， 是采集的轨迹特征集合；
并且，将的路线特征归一化得到特征序列
S303：计算轨迹片段的不规则率转化为计算和的距离，利用下列公式求得和的距离
其中，rest(·)返回特征值序列除了第一个特征值外的其余所有特征值，head(·)返回特征值序列第一个特征值；
S304：计算路线特征f的不规则率
<mrow>
<msub>
<mi>&Gamma;</mi>
<mi>f</mi>
</msub>
<mrow>
<mo>(</mo>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mfrac>
<mrow>
<msub>
<mi>w</mi>
<mi>f</mi>
</msub>
<mo>&CenterDot;</mo>
<mi>d</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>,</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>P</mi>
<mi>R</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
</mrow>
</mrow>
<mrow>
<mi>m</mi>
<mi>a</mi>
<mi>x</mi>
<mrow>
<mo>(</mo>
<mi>l</mi>
<mi>e</mi>
<mi>n</mi>
<mi>g</mi>
<mi>t</mi>
<mi>h</mi>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
<mo>,</mo>
<mi>l</mi>
<mi>e</mi>
<mi>n</mi>
<mi>g</mi>
<mi>t</mi>
<mi>h</mi>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>P</mi>
<mi>R</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
<mo>)</mo>
</mrow>
</mrow>
</mfrac>
</mrow>
其中，wf是用户指定的特征f的权重；length(·)是集合序列中元素的个数。
7.根据权利要求6所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于：
在步骤S304中：
对于可数字化的路线特征f：
<mrow>
<mi>cos</mi>
<mi> </mi>
<mi>t</mi>
<mrow>
<mo>(</mo>
<mi>h</mi>
<mi>e</mi>
<mi>a</mi>
<mi>d</mi>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
<mo>,</mo>
<mi>h</mi>
<mi>e</mi>
<mi>a</mi>
<mi>d</mi>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>P</mi>
<mi>R</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
<mo>)</mo>
</mrow>
<mo>=</mo>
<mo>|</mo>
<mi>h</mi>
<mi>e</mi>
<mi>a</mi>
<mi>d</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
</mrow>
<mo>-</mo>
<mi>h</mi>
<mi>e</mi>
<mi>a</mi>
<mi>d</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>F</mi>
<mover>
<mrow>
<mi>P</mi>
<mi>R</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
</msub>
<mo>)</mo>
</mrow>
<mo>|</mo>
<mo>;</mo>
</mrow>
对于分种类的路线特征f：
其中，是head(·)返回特征值序列第一个特征值，表示和的距离。
8.根据权利要求1所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于，所述的选择运动特征，包括如下步骤：
S311：在每个轨迹分区下，从历史轨迹中提取出每个特征的值，使用有向图G(V,E)表示历史轨迹特征图，用于归纳两个地标之间的特征f，然后构建历史轨迹特征地图；
S312：使用如下公式计算每个轨迹分区下的每个运动特征的不规则率
<mrow>
<msub>
<mi>&Gamma;</mi>
<mi>f</mi>
</msub>
<mrow>
<mo>(</mo>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mo>)</mo>
</mrow>
<mo>=</mo>
<msub>
<mi>w</mi>
<mi>f</mi>
</msub>
<mo>&CenterDot;</mo>
<mfrac>
<mrow>
<munderover>
<mo>&Sigma;</mo>
<mrow>
<mi>t</mi>
<mo>=</mo>
<mi>i</mi>
</mrow>
<mrow>
<mi>i</mi>
<mo>+</mo>
<mi>j</mi>
<mo>-</mo>
<mn>1</mn>
</mrow>
</munderover>
<mo>|</mo>
<mi>n</mi>
<mi>o</mi>
<mi>r</mi>
<mi>m</mi>
<mrow>
<mo>(</mo>
<mi>f</mi>
<mo>(</mo>
<msub>
<mover>
<mrow>
<mi>T</mi>
<mi>S</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mi>t</mi>
</msub>
<mo>)</mo>
<mo>)</mo>
</mrow>
<mo>-</mo>
<mi>n</mi>
<mi>o</mi>
<mi>r</mi>
<mi>m</mi>
<mrow>
<mo>(</mo>
<msub>
<mi>r</mi>
<mrow>
<msub>
<mi>l</mi>
<mi>t</mi>
</msub>
<mo>&RightArrow;</mo>
<msub>
<mi>l</mi>
<mrow>
<mi>t</mi>
<mo>+</mo>
<mn>1</mn>
</mrow>
</msub>
</mrow>
</msub>
<mo>)</mo>
</mrow>
<mo>|</mo>
</mrow>
<mrow>
<mo>|</mo>
<mover>
<mrow>
<mi>T</mi>
<mi>P</mi>
</mrow>
<mo>&OverBar;</mo>
</mover>
<mo>|</mo>
</mrow>
</mfrac>
</mrow>
其中，wf是用户指定的特征f的权重，norm(·)返回的是归一化值，归一化常量n为该分区内所有轨迹片段中的特征f的最大值；是的特征f的平均值，直接从历史轨迹特征地图上得到，是轨迹片段在特征f上的值，是该分区中轨迹片段的个数。
9.根据权利要求1所述的一种基于分区和总结生成便于用户理解的导航信息的方法，其特征在于：在步骤S311中，所述的构建历史轨迹特征地图，包括如下子步骤：
S3111：给定地标集，历史符号轨迹数据集和选定的运动物体的特征f；
S3112：将地标集中的每个地标添加到历史轨迹特征图的顶点集V中；
S3113：添加有向边，如果在历史符号轨迹数据集中存在从li到lj的轨迹那么添加一条从li指向lj的有向边e(li,lj)；
S3114：用轨迹T(li→lj)的特征f的平均值标注每条边。
Priority Applications (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710586815.6A CN107289961A (zh) | 2017-07-18 | 2017-07-18 | 一种基于分区和总结生成便于用户理解的导航信息的方法 |
Applications Claiming Priority (1)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| CN201710586815.6A CN107289961A (zh) | 2017-07-18 | 2017-07-18 | 一种基于分区和总结生成便于用户理解的导航信息的方法 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| CN107289961A true CN107289961A (zh) | 2017-10-24 |
Family
ID=60101188
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| CN201710586815.6A Pending CN107289961A (zh) | 2017-07-18 | 2017-07-18 | 一种基于分区和总结生成便于用户理解的导航信息的方法 |
Country Status (1)
| Country | Link |
|---|---|
| CN (1) | CN107289961A (zh) |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109099904A (zh) * | 2018-07-23 | 2018-12-28 | 国网浙江杭州市萧山区供电有限公司 | 一种基于人体刚性指标的室内设备找寻方法及系统 |
Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101512616A (zh) * | 2006-06-27 | 2009-08-19 | 维里逊实验室公司 | 具有地标数据的驾驶路线指引 |
| CN103575283A (zh) * | 2012-07-27 | 2014-02-12 | 联想(北京)有限公司 | 一种导航方法及电子设备 |
| CN106605123A (zh) * | 2014-08-29 | 2017-04-26 | 三星电子株式会社 | 用于确定入口位置和感兴趣区域的系统 |
| CN106931986A (zh) * | 2017-04-26 | 2017-07-07 | 电子科技大学 | 个性化路径导航方法和系统 |
-
2017
- 2017-07-18 CN CN201710586815.6A patent/CN107289961A/zh active Pending
Patent Citations (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN101512616A (zh) * | 2006-06-27 | 2009-08-19 | 维里逊实验室公司 | 具有地标数据的驾驶路线指引 |
| CN103575283A (zh) * | 2012-07-27 | 2014-02-12 | 联想(北京)有限公司 | 一种导航方法及电子设备 |
| CN106605123A (zh) * | 2014-08-29 | 2017-04-26 | 三星电子株式会社 | 用于确定入口位置和感兴趣区域的系统 |
| CN106931986A (zh) * | 2017-04-26 | 2017-07-07 | 电子科技大学 | 个性化路径导航方法和系统 |
Non-Patent Citations (3)
| Title |
|---|
| HAN SU等: "Making Sense of Trajectory Data: A Partition-and-Summarization Approach", 《2015 IEEE 31ST INTERNATIONAL CONFERENCE ON DATA ENGINEERING》 * |
| YAGUANG LI: "PaRE:A System for Personalized Route Guidance", 《2017 INTERNATIONAL WORLD WIDE WEB CONFERENCE COMMITTEE》 * |
| YAGUANG LI: "PerNav:A Route Summarization Framework for Personalized Navigation", 《SIGMOD"16》 * |
Cited By (1)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| CN109099904A (zh) * | 2018-07-23 | 2018-12-28 | 国网浙江杭州市萧山区供电有限公司 | 一种基于人体刚性指标的室内设备找寻方法及系统 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| Chen et al. | Map-matching algorithm for large-scale low-frequency floating car data | |
| Liu et al. | Identifying spatial interaction patterns of vehicle movements on urban road networks by topic modelling | |
| US10629069B2 (en) | Method and apparatus for providing a localized link-centric metric for directional traffic propagation | |
| Zou et al. | An improved distance metric for the interpolation of link-based traffic data using kriging: a case study of a large-scale urban road network | |
| CN1967524B (zh) | 路况信息收集和查询系统及其方法 | |
| CN106840178A (zh) | 一种基于ArcGIS的地图创建与智能车辆自主导航方法及系统 | |
| CN108304559A (zh) | 一种区域地理空间数据融合方法 | |
| CN105841707A (zh) | 采用地图机制的导航系统及其操作方法 | |
| CN106197460A (zh) | 一种应用gps出行数据进行出行目的地预测的方法 | |
| JP2013529291A (ja) | 場所を表すデータからその場所を解決する方法 | |
| Li et al. | Path-finding through flexible hierarchical road networks: An experiential approach using taxi trajectory data | |
| CN104634352A (zh) | 一种基于浮动车移动轨迹与电子地图融合的道路匹配方法 | |
| CN105723242A (zh) | 测量路网中的交通速度 | |
| US10538250B2 (en) | Road geometry generation from sparse data | |
| US20150019127A1 (en) | Systems and Methods for Displaying Navigational Information | |
| CA2942581A1 (en) | Synthetic data collection for vehicle controller | |
| CN106296488A (zh) | 一种基于众包模式的智慧旅游系统及方法 | |
| Huang et al. | Frequent pattern-based map-matching on low sampling rate trajectories | |
| Lyu et al. | OD morphing: Balancing simplicity with faithfulness for OD bundling | |
| Alizadeh et al. | On the role of bridges as anchor points in route choice modeling | |
| CN107289961A (zh) | 一种基于分区和总结生成便于用户理解的导航信息的方法 | |
| CN106844642A (zh) | 一种基于gis计算路网网格中人口密度的方法 | |
| Demiryurek et al. | TransDec: A spatiotemporal query processing framework for transportation systems | |
| CN107340000A (zh) | 一种从历史轨迹中提取运动特征的方法 | |
| CN107356257A (zh) | 一种从历史轨迹中提取路线特征的方法 |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| PB01 | Publication | ||
| PB01 | Publication | ||
| SE01 | Entry into force of request for substantive examination | ||
| SE01 | Entry into force of request for substantive examination | ||
| RJ01 | Rejection of invention patent application after publication |
Application publication date: 20171024 |
|
| RJ01 | Rejection of invention patent application after publication |