著录项信息
专利名称 | 基于走行方向的有损道路形状融合方法 |
申请号 | CN201110245219.4 | 申请日期 | 2011-08-25 |
法律状态 | 暂无 | 申报国家 | 中国 |
公开/公告日 | 2012-03-14 | 公开/公告号 | CN102374866A |
优先权 | 暂无 | 优先权号 | 暂无 |
主分类号 | G06F19/00 | IPC分类号 | G;0;6;F;1;9;/;0;0查看分类表>
|
申请人 | 光庭导航数据(武汉)有限公司 | 申请人地址 | 湖北省武汉市东湖新技术开发区软件园中路4号光谷软件园六期2栋7层01室
变更
专利地址、主体等相关变化,请及时变更,防止失效 |
权利人 | 武汉中海庭数据技术有限公司 | 当前权利人 | 武汉中海庭数据技术有限公司 |
发明人 | 朱敦尧;宋向勃 |
代理机构 | 武汉开元知识产权代理有限公司 | 代理人 | 唐正玉 |
摘要
本发明提出了一种基于走行方向的有损道路形状融合方法,其步骤包括:1)走行方向分组,即按照浮动车的走行方向对轨迹形状点进行分组;2)首点匹配,即找到待融合轨迹共同的起始部分;3)形状融合,即对每个走行方向上匹配的各个轨迹的形状点,按照走行方向进行融合;4)平滑处理,即对融合后的轨迹形状进行平滑处理,去掉噪声点;5)形状点压缩,即在保持道路基本形状的基础上,去掉不必要的形状点。通过该方法,在浮动车走行轨迹数据挖掘过程中,随着浮动车轨迹数量的增加,虽然每条轨迹形状都有较大的失真,但是通过使用本方法对各个轨迹的形状进行融合能够得到较真实的轨迹形状。
1.一种基于走行方向的有损道路形状融合方法,以浮动车行走轨迹线作为对象进行处理和判定,轨迹线上具有多个用来表示道路或轨迹形状的形状点,其中,所述的有损道路形状为带有一定形状损失的道路形状信息,其特征在于包括以下步骤:
步骤一、走行方向分组,即按照浮动车的走行方向对轨迹形状点进行分组;所述步骤一具体分为两个步骤:
1.1)将平面坐标系分为八个方向:上、下、左、右、左上、左下、右上、右下,将轨迹按照相邻两个形状点之间的前进方向,确定为上述八方向中的某一种;
1.2)将连续相同的走行方向形成一组;
步骤二、首点匹配,即找到待融合轨迹共同的起始部分;所述步骤二具体包括:
2.1)分别选择各个轨迹的第一个形状点,在其他的轨迹中寻找第一个和该形状点具有共同方向形状点,得到一个匹配点对;
2.2)在所有的匹配点对中选择位置和序号最接近的点对,作为相应轨迹的匹配首点对;
步骤三、形状融合,即对每个走行方向上匹配的各个轨迹的形状点,按照走行方向进行融合;所述步骤三具体包括如下:
3.1)存储匹配首点对之前的形状,即如果匹配首点对中有某一个点不是所在轨迹的第一个形状点,则将该点之前的形状点依次添加到融合轨迹中;
3.2)取匹配首点对作为当前点对;
3.3)按照走行方向判断当前点对中两个点的出现顺序;
3.4)如果当前点对中有一个点先出现,则将先出现的形状点添加到融合轨迹中;如果当前点对中两个点位置基本一致,则将这两个点的位置做加权平均处理,得到新的形状点,并将新形状点添加到融合轨迹中;
3.5)移动到下一个形状点,更新当前点对,直到所有形状点被添加到融合轨迹中;
步骤四、平滑处理,即对融合后的轨迹形状进行平滑处理,去掉噪声点;
步骤五、形状点压缩,即采用形状点压缩算法,在保持道路基本形状的基础上,去掉不必要的形状点。
2、根据权利要求1所述的基于走行方向的有损道路形状融合方法,其特征在于:所述步骤2.1)中共同方向认定为右上、左上、右下、左下均按照两个方向看待,和相应的单一方向有共同方向。
3、根据权利要求1所述的基于走行方向的有损道路形状融合方法,其特征在于:所述步骤四中去噪的具体方法为:依次检查融合轨迹中每一个形状点,判断其是否为噪声点,如果是噪声点,则将该点去除,否则,保留该形状点。
4、根据权利要求1所述的基于走行方向的有损道路形状融合方法,其特征在于:所述步骤五中形状点压缩算法为道格拉斯形状点压缩算法。
基于走行方向的有损道路形状融合方法\n技术领域\n[0001] 本发明涉及一种基于走行方向的有损道路形状融合方法,特别是涉及一种对浮动车走行轨迹进行数据挖掘的过程,属于导航、电子地图、智能交通系统和数据挖掘的交叉领域。\n背景技术\n[0002] 为了获得用户行为习惯和路况信息,提供更精准、更安全、更有针对性的导航服务,各大车厂均增强了对浮动车走行轨迹的收集以及进一步进行数据挖掘的研究。但是,浮动车采集的行车轨迹只是在离散时间点上采集的位置信息,因此会导致采集的行车轨迹产生随机的形状损失(形状损失程度与采集的时间间隔和车速有关),尤其在弯道部分,可能带来非常严重的失真。这种失真严重影响轨迹的显示、和电子地图道路的匹配以及对浮动车信息的有效归类、挖掘,并严重影响基于浮动车采集信息对电子地图数据进行修正的高级应用。\n[0003] 相关名词解释:\n[0004] 1.浮动车\n[0005] 带有各种传感器、能采集相关信息的在道路上实际行驶的汽车。\n[0006] 2.有损道路形状\n[0007] 带有一定形状损失的道路形状信息,如图1,虚线所示为真实的道路形状,实线所示为有损道路形状.\n[0008] 3.形状点\n[0009] 用来表示道路或行车轨迹形状的坐标点。\n[0010] 4.行车轨迹\n[0011] 浮动车在走行过程中采集的、用一系列形状点表示的轨迹形状。\n[0012] 5.形状点压缩\n[0013] 为了在道路形状和数据容量之间取得一个平衡,需要用形状点压缩算法去除不必要的形状点。现在常用的形状点压缩算法有道格拉斯形状点压缩算法和距离限差形状点压缩算法。\n[0014] 6.匹配点对\n[0015] 选择各个轨迹的第一个形状点,在其他的轨迹中寻找第一个和该形状点具有共同方向的形状点,即得到一个匹配点对。\n[0016] 7.匹配首点对\n[0017] 在所有的匹配点对中选择位置和序号最接近的点对,作为相应轨迹的匹配首点对。\n发明内容\n[0018] 本发明所要解决的问题是:提供一种基于走行方向的有损道路形状融方法,使用该方法在对浮动车行走轨迹进行数据挖掘的过程中能有效利用多条浮动车轨迹互相补充损失的信息,得到较好的道路形状,从而为进一步的数据挖掘、知识发现打下良好的基础。\n[0019] 本发明所采用的技术方案以浮动车行走轨迹线作为对象进行处理和判定,轨迹线上具有多个用来表示道路或轨迹形状的形状点,包括以下步骤:\n[0020] 步骤一、走行方向分组,即按照浮动车的走行方向对轨迹形状点进行分组;\n[0021] 步骤二、首点匹配,即找到待融合轨迹共同的起始部分;\n[0022] 步骤三、形状融合,即对每个走行方向上匹配的各个轨迹的形状点,按照走行方向进行融合;\n[0023] 步骤四、平滑处理,即对融合后的轨迹形状进行平滑处理,去掉噪声点;\n[0024] 步骤五、形状点压缩,即采用形状点压缩算法,在保持道路基本形状的基础上,去掉不必要的形状点。\n[0025] 优选的,上述步骤一具体分为两个步骤:\n[0026] 1.1)将平面坐标系分为八个方向:上、下、左、右、左上、左下、右上、右下,将轨迹按照相邻两个形状点之间的前进方向,确定为上述八方向中的某一种;\n[0027] 1.2)将连续相同的走行方向形成一组。\n[0028] 优选的,上述步骤二具体包括:\n[0029] 2.1)分别选择各个轨迹的第一个形状点,在其他的轨迹中寻找第一个和该形状点具有共同方向形状点,得到一个匹配点对;\n[0030] 2.2)在所有的匹配点对中选择位置和序号最接近的点对,作为相应轨迹的匹配首点对。\n[0031] 优选的,上述步骤2.1)中共同方向认定为右上、左上、右下、左下均按照两个方向看待,和相应的单一方向有共同方向。\n[0032] 优选的,上述步骤三具体包括如下:\n[0033] 3.1)存储匹配首点对之前的形状,即如果匹配首点对中有某一个点不是所在轨迹的第一个形状点,则将该点之前的形状点依次添加到融合轨迹中;;\n[0034] 3.2)取匹配首点对作为当前点对;\n[0035] 3.3)按照走行方向判断当前点对中两个点的出现顺序;\n[0036] 3.4)如果当前点对中有一个点先出现,则将先出现的形状点添加到融合轨迹中;\n如果当前点对中两个点位置基本一致,则将这两个点的位置做加权平均处理,得到新的形状点,并将新形状点添加到融合轨迹中;\n[0037] 3.5)移动到下一个形状点,更新当前点对,直到所有形状点被添加到融合轨迹中。\n[0038] 优选的,上述步骤四中去噪的具体方法为:依次检查融合轨迹中每一个形状点,判断其是否为噪声点,如果是噪声点,则将该点去除,否则,保留该形状点。\n[0039] 优选的,上述步骤五中形状点压缩算法为道格拉斯形状点压缩算法。\n[0040] 本发明的优点是:随着浮动车轨迹数量的增加,虽然每条轨迹形状都有较大的失真,但是通过使用本方法对各个轨迹的形状进行融合能够得到较真实的轨迹形状。前提假设:本发明的假设前提是待融合的各个轨迹已经被判断为可以融合的情况。\n附图说明\n[0041] 图1是有损道路形状概念例子示意图;\n[0042] 图2是本发明的融合算法实施流程图;\n[0043] 图3是按照走行方向分组中8方向的示意图;\n[0044] 图4是按照走行方向分组的示意图;\n[0045] 图5是形状融合步骤的算法流程图;\n[0046] 图6是平滑处理的示例说明示意图;\n[0047] 图7是利用本算法实际融合效果图(两条虚线是待融合轨迹形状,实线是融合后轨迹形状)。\n具体实施方式\n[0048] 为了便于本领域普通技术人员理解和实施本发明,下面结合附图及具体实施方式对本发明作进一步的详细描述。\n[0049] 如图2所示,本发明的实现方式,在开始之后包括以下步骤:\n[0050] 1)走行方向分组\n[0051] 走行方向分组的目的是将每条浮动车行走轨迹按照行走方向进行分组,从而为进一步确定待融合的两条轨迹中相匹配的部分并进而融合匹配部分的形状形成基础。\n[0052] 走行方向分组的方法如下:\n[0053] 将平面坐标系分为八个方向(如图3):上、下、左、右、左上、左下、右上、右下,将轨迹按照相邻两个形状点之间的前进方向,确定为上述八方向中的某一种,连续相同的走行方向形成一组。\n[0054] 比如取阈值α为10°,则图3所示的八个方向依次如下:\n[0055] 右方向:-10°~10°\n[0056] 右上方向:10°~80°\n[0057] 上方向:80°~100°\n[0058] 左上方向:100°~170°\n[0059] 左方向:170°~190°\n[0060] 左下方向:190°~260°\n[0061] 下方向:260°~280°\n[0062] 右下方向:280°~350°。\n[0063] 对于图4所示轨迹,按照上述走行方向分组方法,可得到下述分组:\n[0064] 左上:形状点0~形状点2;\n[0065] 右上:形状点2~形状点5;\n[0066] 上:形状点5~形状点6;\n[0067] 右:形状点6~形状点7;\n[0068] 右下:形状点7~形状点9;\n[0069] 下:形状点9~形状点10;\n[0070] 左下:形状点10~形状点11;\n[0071] 左:形状点11~形状点13。\n[0072] 2)首点匹配\n[0073] 首点匹配的目的是找到待融合轨迹共同的起始部分。\n[0074] 首点匹配的方法是分别选择各个轨迹的第一个形状点,在其他的轨迹中寻找第一个和该形状点具有共同方向(右上、左上、右下、左下均按照两个方向看待,可以认为和相应的单一方向有共同方向)形状点,得到一个匹配点对,在所有的匹配点对中选择位置和序号最接近的点对,作为相应轨迹的匹配首点对。\n[0075] 3)形状融合\n[0076] 形状融合的目的是将各个轨迹的形状点按照其在走行方向上出现的顺序进行合并,从而得到更高精度、更为逼真的轨迹形状。\n[0077] 形状融合的方法如下(流程图见图5):\n[0078] 以两条轨迹融合为例(多条轨迹可以两两融合),记其中一条轨迹为轨迹a,另外一条轨迹为轨迹b。\n[0079] a)存储匹配首点对之前的形状\n[0080] 如果匹配首点对中有某一个点不是所在轨迹的第一个形状点,则将该点之前的形状点依次添加到融合轨迹中。\n[0081] b)取出当前点对\n[0082] 分别取轨迹a和轨迹b的匹配首点对作为当前点对,记做点a和点b。\n[0083] c)按照走行方向判断当前点对中两个点的出现顺序\n[0084] 根据点a和点b所属走行方向分组判断两个点的出现顺序。选择点a和点b分别所属的走行方向分组的共同方向(右上、左上、右下、左下均按照两个方向看待),比如共同方向为右下,则点a和点b中更靠近左侧的点为先出现的点。如果点a或点b是两个走行方向分组的衔接点,比如1)中例子的点3,则需要对两个走行方向分别判断,如果两个走行方向判断结果不一致,则将点a和点b作为位置基本一致处理。\n[0085] d)添加形状点到融合轨迹中\n[0086] 如果点a和点b中有一个先出现,则将先出现的形状点添加到融合轨迹中;\n[0087] 如果点a和点b位置基本一致,则将点a和点b的位置做加权平均处理,得到点c,并将点c添加到融合轨迹中。\n[0088] e)移动到下一个形状点\n[0089] 如果点a和点b中有一个先出现,且如果先出现形状点不是所在轨迹的最后一个形状点,则取先出现形状点的下一个形状点作为新的点a或点b(取决于先出现形状点是哪一个),并返回步骤c);如果先出现形状点是所在轨迹的最后一个形状点,则将另外一条轨迹中剩余的所有形状点依次添加到融合轨迹中,处理结束。\n[0090] 如果点a和点b位置基本一致,且点a和点b均不是轨迹a和轨迹b的最后一个形状点,则取它们的下一个形状点作为新的点a和点b,返回步骤c);如果点a或点b有一个是所在轨迹的最后一个形状点,则把另外一条轨迹中当前点之后的所有剩余形状点依次添加到融合轨迹中,处理结束;如果点a和点b都是所在轨迹的最后一个形状点,则处理结束。\n[0091] 4)平滑处理\n[0092] 平滑处理的目的将融合轨迹中的噪声点去掉,得到比较平滑、合理的轨迹形状。\n[0093] 平滑处理的方法如下:\n[0094] 依次检查融合轨迹中每一个形状点,判断其是否为噪声点,如果是噪声点,则将该点去除,否则,保留该形状点。\n[0095] 判断一个形状点是否为噪声点的规则为:该点与前一个形状点或后一个形状点的距离小于阈值(阈值的设定与形状的精度有关,本文取阈值为20个像素),而且以该点为顶点的轨迹夹角为锐角。\n[0096] 图6为一条带噪声点(形状点3)的轨迹平滑前后的示例说明。\n[0097] 5)形状点压缩\n[0098] 形状点压缩的目的是在保持轨迹形状的基础上,尽量删除冗余的形状点,从而达到削减数据容量的目的。本发明采用通用的道格拉斯形状点压缩算法进行形状点压缩。\n[0099] 以上所述,仅是用以说明本发明的具体实施案例而已,并非用以限定本发明的可实施范围,举凡本领域熟练技术人员在未脱离本发明所指示的精神与原理下所完成的一切等效改变或修饰,仍应由本发明权利要求的范围所覆盖。
法律信息
- 2016-12-14
专利权的转移
登记生效日: 2016.11.21
专利权人由武汉光庭信息技术股份有限公司变更为武汉中海庭数据技术有限公司
地址由430073 湖北省武汉市东湖开发区光谷软件园一期以西、南湖南路以南光谷软件园六期2幢8层208号变更为430073 湖北省武汉市东湖新技术开发区软件园中路4号光谷软件园六期2栋7层01室
- 2016-04-20
专利权人的姓名或者名称、地址的变更
专利权人由武汉光庭信息技术有限公司变更为武汉光庭信息技术股份有限公司
地址由430074 湖北省武汉市东湖新技术开发区软件园中路4号光谷E城2号楼8F变更为430073 湖北省武汉市东湖开发区光谷软件园一期以西、南湖南路以南光谷软件园六期2幢8层208号
- 2013-03-13
- 2012-11-14
专利申请权的转移
登记生效日: 2012.09.29
申请人由光庭导航数据(武汉)有限公司变更为武汉光庭信息技术有限公司
地址由430074 湖北省武汉市东湖开发区关山一路1号光谷软件园C6栋2楼210室变更为430074 湖北省武汉市东湖新技术开发区软件园中路4号光谷E城2号楼8F
- 2012-04-25
实质审查的生效
IPC(主分类): G01C 21/26
专利申请号: 201110245219.4
申请日: 2011.08.25
- 2012-03-14
引用专利(该专利引用了哪些专利)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 |
1
| |
2009-11-11
|
2009-06-17
| | |
2
| |
2009-11-25
|
2009-07-03
| | |
3
| |
2007-05-09
|
2006-11-17
| | |
4
| |
2008-12-17
|
2008-07-29
| | |
5
| |
2010-09-08
|
2010-04-16
| | |
6
| |
2007-04-18
|
2006-08-25
| | |
被引用专利(该专利被哪些专利引用)
序号 | 公开(公告)号 | 公开(公告)日 | 申请日 | 专利名称 | 申请人 | 该专利没有被任何外部专利所引用! |