 上传我的文档
 下载
 收藏
该文档贡献者很忙，什么也没留下。
 下载此文档
正在努力加载中...
利用弗雷歇距离及网格化 方法挖掘轨迹通道
下载积分：1000
内容提示：利用弗雷歇距离及网格化 方法挖掘轨迹通道
文档格式：PDF|
浏览次数：16|
上传日期： 14:47:49|
文档星级：
全文阅读已结束，如果下载本文需要使用
 1000 积分
下载此文档
该用户还上传了这些文档
利用弗雷歇距离及网格化 方法挖掘轨迹通道
官方公共微信如何理解弗雷歇距离（Fréchetdistanc；作者：陈郁葱；定义；设二元组??,??是一个度量空间，其中??是??；定义1如果定义在单位区间0,1上的映射??:0,；定义2如果从单位区间到其自身的映射??，即函数?；??1=1；定义3设??和??是??上的两条连续曲线，即??；????,??=infmax????????,?；其中??是??上的度量函数；
如何理解弗雷歇距离（Fréchet distance）
作者：陈郁葱
是一个度量空间，其中 ?? 是 ?? 上的度量函数，在无需指明度量函数的情况下，我们把度量空间简称为 ??。
如果定义在单位区间
上的映射 ??: 0,1 →?? 是连续映射，则称 ?? 为 ?? 上的连续曲线。
如果从单位区间到其自身的映射 ??，即函数 ??: 0,1 → 0,1 ，满足如下三个条件：1 ?? 是连续的，2 ?? 是非降的，○○即对于任意 ??,??∈ 0,1 ，且 ??≤??，都有 ?? ?? ≤?? ??
成3 ?? 是满射，则称函数 ?? 为单位区间
的重参数化函数，且此时有 ?? 0 =0，立，○
?? 1 =1。特别地，当 ?? 为恒等函数 ?? ?? =?? 时，称 ?? 为平凡重参数化函数，否则，称 ?? 为非平凡重参数化函数。显然，单位区间的重参数化函数有无穷多个。 有了以上设定，我们来正式定义度量空间中两条曲线之间的弗雷歇距离。
设 ?? 和 ?? 是 ?? 上的两条连续曲线，即 ??: 0,1 →??，??: 0,1 →??；又设 ?? 和 ?? 是单位区间的两个重参数化函数，即 ??: 0,1 → 0,1 ，??: 0,1 → 0,1 ；则曲线 ?? 与曲线 ?? 的弗雷歇距离 ?? ??,??
?? ??,?? =infmax ?? ?? ?? ??
??,????∈ 0,1
其中 ?? 是 ?? 上的度量函数。
为了更好地理解弗雷歇距离，我们先引入如下几个概念与命题。
对于度量空间 ?? 上的任一连续曲线 ??: 0,1 →??，我们称 ?? 0
为该曲线的起点，称 ?? 1
为该曲线的终点；如果参数 ??,??∈ 0,1 ，且 ??≤??，则称 ?? ??
的前面，也称 ?? ??
连续曲线上某点是起点，当且仅当它在所有点的前面；连续曲线上某点是终点，当且仅当它在所有点的后面。
证明：命题显然为真，证略。?
设度量空间 ?? 上有一连续曲线 ??: 0,1 →??，单位区间上有一重参数化函数 ??: 0,1 → 0,1 ，我们把复合映射 ??°??: 0,1 →?? 称为曲线 ?? 在重参数化函数 ?? 作用下的重参数化曲线 ??′，即 ??′=??°ζ。
度量空间中连续曲线的重参数化曲线不改变原曲线上各点的前后关系。
证明：设连续曲线为 ??，任取参数 ??,??∈ 0,1 ，且 ??≤??，则 ?? ??
的前面。又设重参数化函数为 ??，则重参数化曲线为 ??′=??°??，故参数 ?? 与 ?? 在 ??′ 上对应的点分别为 ??′ ?? = ??°??
?? =?? ?? ??
与 ??′ ?? = ??°??
?? =?? ?? ??
，又由重参数化函数的性质可知，?? ?? ,?? ?? ∈ 0,1 ，且 ?? ?? ≤?? ?? ，故 ?? ?? ??
在 ?? ?? ??
的前面，即 ??′ ??
的前面，因此参数 ?? 与 ?? 在 ?? 与 ??′ 上对应两点之间的前后关系保持一致，又因为参数 ??,?? 是任取的，所以重参数化曲线不改变原曲线上各点的前后关系，证毕。? 推论
度量空间中连续曲线的重参数化曲线不改变原曲线的起点与终点。
证明：由命题1知，原曲线的起点在原曲线上所有点的前面，故由命题2可知，位于重参数化曲线上与原曲线起点参数对应的点也在重参数化曲线上所有点的前面，再由命题1即可知该点就是重参数化曲线的起点，因此连续曲线的重参数化曲线不改变原曲线的起点；终点的证明同理；证毕。?
理解弗雷歇距离
下面我们回到定义3中对弗雷歇距离的定义中来，为了更加直观的理解，我们用图1中二维欧氏平面上的两条曲线来解释弗雷歇距离。
图1 二维欧氏平面上两条曲线之间的弗雷歇距离的计算示意图
按照定义3，曲线 ?? 与曲线 ?? 的弗雷歇距离 ?? ??,??
?? ??,?? =infmax ?? ?? ?? ??
??,????∈ 0,1
其中 ?? 是 ?? 上的度量函数。
在 ?? ??,??
的计算公式中，先固定最外层的 ?? 与 ??，也就是对每一个选定的 ?? 与 ?? 的组合，计算下式：
????,?? ??,?? =max ?? ?? ?? ??
上式中 ??,??,??,??,?? 均视为被固定住的已知函数，只将 ?? 当作变量。此时，由于变量 ?? 将在单位区间
内遍历所有连续取值（无穷多个），为了便于直观理解，我们将该区间作离散化处理，即在该区间采样若干个点来作分析，然后通过逐渐增加采样点的个数来提高精度，最后通过求极限的思想来理解两条曲线的弗雷歇距离。
数列在原曲线上的点列
+1在单位区间
中任意抽取由
个互不相同的数构成单调递增数列
???? ??使得 ??=0，
??0=0，????+1=1，且满足 ????&????+1。
??=0 分别称为数列
???? ????=0 分别在曲线 ?? 与 ?? 上的点列。其??+1??+1
中，?? ??0 （即?? 0 ）与 ?? ????+1 （即?? 1 ）分别是曲线 ?? 的起点与终点，?? ??0 （即?? 0 ）与 ?? ????+1 （即?? 1 ）分别是曲线 ?? 的起点与终点。 ?? ????
??=0 在图1中由黑点标出。
??=0 相互对应的点，即 ?? ????
与 ?? ????
连接，即图1中两曲线之间的黑色连接线，?? ????
与 ?? ????
之间的距离为 ?? ?? ???? ,?? ????
。 ??+1??+1??+1??+1
数列在重参数化曲线上的点列
现在引入曲线的重参数化函数，设作用于曲线 ??,?? 的重参数化函数分别是 ??,??，它们对应的重参数化曲线分别为 ??′,??′，则 ??′=??°??，??′=??°??。
类似地，将
??=0（即 ?? ?? ????
??=0（即 ?? ?? ????
??=0） 分别称
+1??+1为数列
???? ????=0 分别在重参数化曲线 ??′ 与 ??′ 上的点列，或分别称为数列
???? ??=0 分别
在重参数化函数分别是 ?? 与 ?? 的曲线 ?? 与 ?? 上的点列。两曲线的重参数化点列
??=0 在图1中由红点标出。
类似地，分别连接
??=0 相互对应的点，即 ??′ ????
与 ??′ ????
连接，即图1中两曲线之间的红色连接线，??′ ????
与 ??′ ????
之间的距离为 ?? ??′ ???? ,??′ ????
，也即 ?? ?? ?? ????
,?? ?? ????
。 ??+1??+1??+1??+1
重参数化前后点列之间的关系
+1由命题2及其推论可知，数列
???? ????=0 在每条曲线重参数化前后的点列保持了各点之间的
前后关系，即图1中每条曲线上的红点的排列顺序与黑点的排列顺序保持一致。
用极限思想理解弗雷歇距离
????,?? ??,??
的离散化计算公式为
?? ???? ?? ?? ?? ??
,?? ??,?? =max??+1??∈ ???? ??=0
因此，?? ??,??
的离散化计算公式为
?? ?? ??,?? =inf ?? ????,?? ??,??
=inf max ?? ?? ?? ??
的极限就是 ?? ??,??
再令 ??→∞，max??∈ 0,…,??
?????????+1
???? ??,?? =lim??→∞
??∈ 0,…,?? ??∈ ???? ??=0max
?????????+1
??∈ 0,…,?? ??→∞??,??max
?????????+1
→0lim inf max ?? ?? ?? ??
??+1??∈ ???? ??=0
用两串珠子理解弗雷歇距离
将图1中的两条曲线 ??,?? 设想为两条坚硬的、被固定住的、不会变形的钢丝，每条钢丝都串上同样数目的 ?? 个珠子（即图1中的黑点），再用可任意无限自由伸缩的橡皮筋把两串珠子上对应的珠子连接起来（即图1中两曲线之间连接两曲线上黑点的黑线），最后再用橡皮筋连接两条钢丝对应的端点（如图1所示）。此时即为初始状态。
接下来准备好纸、笔和尺子，我们开始操作、测量和记录：
? 首先，测量初始状态下各条橡皮筋的长度，并记录下它们中的最大值 ??0；
? 用手任意挪动两条钢丝上的若干珠子使其到达新位置（即图1中的红点）（注意：每条钢丝上的珠子之间都是不能相互跨越的），测量各条橡皮筋的长度，并记录下它们中的最大值 ??1；
? 再重复上一步 (???1) 次（?? 足够大）；
最后共得到 (??+1) 个值
???? ??=0，它们的最小值 min?? ????
即可作为曲线 ?? 与曲线 ?? 的弗雷歇距离 ?? ??,??
的近似值。
为了提高近似值的准确度，可以增大 ?? 与 ?? 的值。
三亿文库包含各类专业文献、幼儿教育、小学教育、文学作品欣赏、生活休闲娱乐、外语学习资料、行业资料、专业论文、中学教育、如何理解弗雷歇距离(Fréchet distance)51等内容。　婉君:曲线比较Frechet距离算法 - 苏小败在路上
- CSDN.NET - 全球最大中文IT社区，为IT专业技术人员提供最全面的信息传播和服务平台()
2369人阅读
放在这里以备以后自己需要：
CompareGesture: function(line1, line2){/frechet距离算法
var fval = 0;
var ca = [];
for(var i=0;i&line1.i++){
ca.push([]);
for(var j=0;j&line2.j++){
ca[i][j] = -1;
fval = Utils.CalDistance(line1, line2, ca, line1.length-1, line2.length-1);
CalDistance: function(line1, line2, arr, i, j){
if (arr[i][j] & -1){
return arr[i][j];
}else if (i==0 && j==0){
arr[i][j] = Utils.DisP(line1[0], line2[0]);/两点的距离
}else if (i&0 && j==0){
arr[i][j] = Math.max(Utils.CalDistance(line1,line2,arr,i-1,0), Utils.DisP(line1[i],line2[0]));
}else if (i==0 && j&0){
arr[i][j] = Math.max(Utils.CalDistance(line1,line2,arr,0,j-1), Utils.DisP(line1[0],line2[j]));
}else if (i&0 && j&0){
arr[i][j] = Math.max(Math.min(
Utils.CalDistance(line1,line2,arr,i-1,j),
Utils.CalDistance(line1,line2,arr,i-1,j-1),
Utils.CalDistance(line1,line2,arr,i,j-1)),
Utils.DisP(line1[i], line2[j])
arr[i][j] = Number.MAX_VALUE;
return arr[i][j];
&&相关文章推荐
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：55982次
排名：千里之外
原创：36篇
评论：81条
(2)(2)(2)(2)(1)(4)(3)(4)(4)(4)(9)当前位置： >>
>> 如何理解弗雷歇距离(Fréchet distance)
<img src="/v1/docconvert5708/wk/2d692b394cec58cdfaacb4/0.png?responseContentType=image%2Fpng&responseCacheControl=max-age%3D10&responseExpires=Tue%2C%2022%20A
ug%9%3A55%3A53%20%2B0800&authorization=bce-auth-v1%2Ffa1fa7cc8e%2FT11%3A55%3A43Z%2F-1%2Fhost%2Fca70c734f98ade5bbb01766bbdaa887a2de1f7ff56&x-bce-range=0-&token=dbbef48d0cdd91d3881b23ecff3f02f8df4&expire=T11:55:43Z" style="width: 100%;">如何理解弗雷歇距离（Fréchet distance）作者：陈郁葱定义设二元组 ,
是一个度量空间，其中
上的度量函数，在无需指明度量函数的情 况下，我们把度量空间简称为 。 定义 1 如果定义在单位区间 0,1 上的映射
是连续映射， 则称
上的 连续曲线。 定义 2 如果从单位区间到其自身的映射
: 0,1 → 0,1 ，满足如下三个条件： 1
是连续的，○ 2
是非降的，即对于任意
∈ 0,1 ，且
是满射，则称函数
为单位区间 0,1 的重参数化函数，且此时有
0 = 0， 立，○
1 = 1。特别地，当
为恒等函数
为平凡重参数化函数，否则，称
为非平凡重参数化函数。显然，单位区间的重参数化函数有无穷多个。 有了以上设定，我们来正式定义度量空间中两条曲线之间的弗雷歇距离。 定义 3 设
上的两条连续曲线，即 : 0,1 → ，: 0,1 → ；又设
是单位区间的两个重参数化函数，即 : 0,1 → 0,1 ， : 0,1 → 0,1 ；则曲线
的弗雷歇距离
, ∈ 0,1其中
上的度量函数。几个引理为了更好地理解弗雷歇距离，我们先引入如下几个概念与命题。 定义 4 对于度量空间
上的任一连续曲线
: 0,1 → ，我们称
0 为该曲线的起点， 称
1 为该曲线的终点；如果参数
∈ 0,1 ，且
的前面， 也称
的后面。 命题 1 连续曲线上某点是起点，当且仅当它在所有点的前面；连续曲线上某点是终点，当 且仅当它在所有点的后面。 证明：命题显然为真，证略。? 定义 5 设度量空间
上有一连续曲线
，单位区间上有一重参数化函数
: 0,1 → 0,1 ， 我们把复合映射
? : 0,1 →
在重参数化函数
作用下的 重参数化曲线 ′，即
? ζ。 命题 2 度量空间中连续曲线的重参数化曲线不改变原曲线上各点的前后关系。 证明：设连续曲线为 ，任取参数 ,
∈ 0,1 ，且
的前面。又设 重参数化函数为
，则重参数化曲线为
在 ′ 上对应的点分别 为
，又由重参数化函数的性 质可知，
∈ 0,1 ，且
的前面，即
的前面，因此参数
与 ′ 上对应两点之间的前后关系保持一致，又因 为参数
是任取的，所以重参数化曲线不改变原曲线上各点的前后关系，证毕。? 推论 度量空间中连续曲线的重参数化曲线不改变原曲线的起点与终点。 证明：由命题 1 知，原曲线的起点在原曲线上所有点的前面，故由命题 2 可知，位于重参数 化曲线上与原曲线起点参数对应的点也在重参数化曲线上所有点的前面， 再由命题 1 即可知 该点就是重参数化曲线的起点， 因此连续曲线的重参数化曲线不改变原曲线的起点； 终点的 证明同理；证毕。?理解弗雷歇距离下面我们回到定义 3 中对弗雷歇距离的定义中来， 为了更加直观的理解， 我们用图 1 中二维 欧氏平面上的两条曲线来解释弗雷歇距离。图 1 二维欧氏平面上两条曲线之间的弗雷歇距离的计算示意图思想按照定义 3，曲线
的弗雷歇距离
, ∈ 0,1其中
上的度量函数。 在
的计算公式中，先固定最外层的
，也就是对每一个选定的
的 组合，计算下式：
∈ 0,1上式中
均视为被固定住的已知函数，只将
当作变量。此时，由于变量
将 在单位区间 0,1 内遍历所有连续取值（无穷多个） ，为了便于直观理解，我们将该区间作 离散化处理， 即在该区间采样若干个点来作分析， 然后通过逐渐增加采样点的个数来提高精 度，最后通过求极限的思想来理解两条曲线的弗雷歇距离。数列在原曲线上的点列在单位区间 0,1 中任意抽取由
+ 2 个互不相同的数构成单调递增数列
0 = 0， +1 = 1，且满足
=0分别称为数列
=0分别在曲线
上的点列。其中， 0 （即 0 ）与
+1 （即 1 ）分别是曲线
的起点与终点， 0 （即 0 ） 与
+1 （即 1 ）分别是曲线
的起点与终点。
中由黑点标出。 分别连接
=0在图 1与
=0相互对应的点，即
连接，即图 1 中两曲线之间的黑色连接线，
之间的距离为
。数列在重参数化曲线上的点列现在引入曲线的重参数化函数，设作用于曲线 ,
的重参数化函数分别是 ,
，它们对应 的重参数化曲线分别为 ′ , ′，则 ′ =
。 类似地，将 ′
=0） 与 ′
=0） 分别称+1
=0 分别在重参数化曲线 ′ 与 ′ 上的点列，或分别称为数列
=0 分别 在重参数化函数分别是
上的点列。两曲线的重参数化点列′
=0在图 1 中由红点标出。 与 ′
=0类似地， 分别连接 ′
=0相互对应的点， 即 ′
连接， 之间的距离为
，也即图 1 中两曲线之间的红色连接线，′
。与 ′ 重参数化前后点列之间的关系+1 由命题 2 及其推论可知，数列
=0 在每条曲线重参数化前后的点列保持了各点之间的 前后关系，即图 1 中每条曲线上的红点的排列顺序与黑点的排列顺序保持一致。用极限思想理解弗雷歇距离 , ,
的离散化计算公式为
=0因此， ,
的离散化计算公式为
,= inf ,∈
→ ∞，max∈ 0,…,
+1 lim→ 0，
的极限就是
, ∈ 0,…,→∞
+1 →0=∈ 0,…,max→∞
+1 →0liminf∈
+1 =0用两串珠子理解弗雷歇距离将图 1 中的两条曲线 ,
设想为两条坚硬的、被固定住的、不会变形的钢丝，每条钢丝都 串上同样数目的
个珠子（即图 1 中的黑点） ，再用可任意无限自由伸缩的橡皮筋把两串 珠子上对应的珠子连接起来（即图 1 中两曲线之间连接两曲线上黑点的黑线） ，最后再用橡 皮筋连接两条钢丝对应的端点（如图 1 所示） 。此时即为初始状态。 接下来准备好纸、笔和尺子，我们开始操作、测量和记录： ? 首先，测量初始状态下各条橡皮筋的长度，并记录下它们中的最大值 0 ； ? 用手任意挪动两条钢丝上的若干珠子使其到达新位置（即图 1 中的红点） （注意：每条 钢丝上的珠子之间都是不能相互跨越的） ，测量各条橡皮筋的长度，并记录下它们中的 最大值 1 ； ? 再重复上一步 ( ? 1) 次（ 足够大） ； 最后共得到 ( + 1) 个值
=0， 它们的最小值 min 即可作为曲线
的弗雷歇距离
的近似值。 为了提高近似值的准确度，可以增大
相关文档：
更多相关文章：
更多相关标签：
copyright &copyright 。非常超级学习网内容来自网络，如有侵犯请联系客服。|