如何理解弗雷歇距离(fréchet distance)

《如何理解弗雷歇距离(fréchet distance)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、如何理解弗雷歇距离（Fréchetdistance）作者：陈郁葱定义设二元组S,d是一个度量空间，其中d是S上的度量函数，在无需指明度量函数的情况下，我们把度量空间简称为S。定义1如果定义在单位区间0,1上的映射γ:0,1→S是连续映射，则称γ为S上的连续曲线。定义2如果从单位区间到其自身的映射ζ，即函数ζ:0,1→0,1，满足如下三个条件：ζ是连续的，ζ是非降的，即对于任意x,y∈0,1，且x≤y，都有ζx≤ζy成立，ζ是满射，则称函数ζ为单位区间0,1的重参数化函数，且此时有ζ0=0，ζ1=1。特别地，当ζ为恒等函数ζx=x时，称ζ为平凡重参数化函数，否则，称ζ为非平凡重参数化函

2、数。显然，单位区间的重参数化函数有无穷多个。有了以上设定，我们来正式定义度量空间中两条曲线之间的弗雷歇距离。定义3设A和B是S上的两条连续曲线，即A:0,1→S，B:0,1→S；又设α和β是单位区间的两个重参数化函数，即α:0,1→0,1，β:0,1→0,1；则曲线A与曲线B的弗雷歇距离FA,B定义为：FA,B=infα,βmaxt∈0,1dAαt,Bβt其中d是S上的度量函数。几个引理为了更好地理解弗雷歇距离，我们先引入如下几个概念与命题。定义4对于度量空间S上的任一连续曲线γ:0,1→S，我们称γ0为该曲线的起点，称γ1为该曲线的终点；如果参数η,ξ∈0,1，且η≤ξ，则称γη在

3、γξ的前面，也称γξ在γη的后面。命题1连续曲线上某点是起点，当且仅当它在所有点的前面；连续曲线上某点是终点，当且仅当它在所有点的后面。证明：命题显然为真，证略。∎定义5设度量空间S上有一连续曲线γ:0,1→S，单位区间上有一重参数化函数ζ:0,1→0,1，我们把复合映射γ∘ζ:0,1→S称为曲线γ在重参数化函数ζ作用下的重参数化曲线γ'，即γ'=γ∘ζ。命题2度量空间中连续曲线的重参数化曲线不改变原曲线上各点的前后关系。证明：设连续曲线为γ，任取参数η,ξ∈0,1，且η≤ξ，则γη在γξ的前面。又设重参数化函数为ζ，则重参数化曲线为γ'=γ∘ζ，故参数η与ξ在γ'上对应的点分别为γ

4、'η=γ∘ζη=γζη与γ'ξ=γ∘ζξ=γζξ，又由重参数化函数的性质可知，ζη,ζξ∈0,1，且ζη≤ζξ，故γζη在γζξ的前面，即γ'η在γ'ξ的前面，因此参数η与ξ在γ与γ'上对应两点之间的前后关系保持一致，又因为参数η,ξ是任取的，所以重参数化曲线不改变原曲线上各点的前后关系，证毕。∎推论度量空间中连续曲线的重参数化曲线不改变原曲线的起点与终点。证明：由命题1知，原曲线的起点在原曲线上所有点的前面，故由命题2可知，位于重参数化曲线上与原曲线起点参数对应的点也在重参数化曲线上所有点的前面，再由命题1即可知该点就是重参数化曲线的起点，因此连续曲线的重参数化曲线不改变原曲线的起

5、点；终点的证明同理；证毕。∎理解弗雷歇距离下面我们回到定义3中对弗雷歇距离的定义中来，为了更加直观的理解，我们用图1中二维欧氏平面上的两条曲线来解释弗雷歇距离。图1二维欧氏平面上两条曲线之间的弗雷歇距离的计算示意图思想按照定义3，曲线A与曲线B的弗雷歇距离FA,B定义为：FA,B=infα,βmaxt∈0,1dAαt,Bβt其中d是S上的度量函数。在FA,B的计算公式中，先固定最外层的α与β，也就是对每一个选定的α与β的组合，计算下式：Fα,βA,B=maxt∈0,1dAαt,Bβt上式中d,A,α,B,β均视为被固定住的已知函数，只将t当作变量。此时，由于变量t将在单位区间0,1内

6、遍历所有连续取值（无穷多个），为了便于直观理解，我们将该区间作离散化处理，即在该区间采样若干个点来作分析，然后通过逐渐增加采样点的个数来提高精度，最后通过求极限的思想来理解两条曲线的弗雷歇距离。数列在原曲线上的点列在单位区间0,1中任意抽取由n+2个互不相同的数构成单调递增数列tkk=0n+1，使得t0=0，tn+1=1，且满足tk

7、1与Btkk=0n+1在图1中由黑点标出。分别连接Atkk=0n+1与Btkk=0n+1相互对应的点，即Atk与Btk连接，即图1中两曲线之间的黑色连接线，Atk与Btk之间的距离为dAtk,Btk。数列在重参数化曲线上的点列现在引入曲线的重参数化函数，设作用于曲线A,B的重参数化函数分别是α,β，它们对应的重参数化曲线分别为A',B'，则A'=A∘α，B'=B∘β。类似地，将A'tkk=0n+1（即Aαtkk=0n+1）与B'tkk=0n+1（即Bβtk