1、引言
对于如何评价两条曲线的相似度现已经存在许多较为直接有效的方法,诸如基于各种距离测度的距离评判、利用相关系数进行相似度分析等等,其中对于距离测度运用较为广泛便是欧式距离、Hausdorff距离等等。而在1906年法国数学家Maurice René Fréchet提出了一种基于空间路径相似度描述方式[1],其着重将路径空间距离考虑进去,使得其对于有一定空间时序的曲线相似度评价效率相比之下更高,这便是Fréchet distance(弗雷歇距离)。
图1:两条曲线间的Hausdorff距离和Fréchet距离[2]
2、定义
对于其定义其中最为简单直观的一个理解,主人和狗在两条不同的轨迹上运动,主人和狗之间是由狗绳相连接的,Fréchet距离即两者能各自走完整个轨迹的情况下满足条件的狗绳的最短长度。
图2:A为主人行走轨迹,B为狗的运动轨迹,在此情况下可知Fréchet距离为0.25时刻或者0.75时刻人和狗之间的距离
更为严格的Fréchet距离数学表达式如下[3]
对于上述数学表达式的理解为,对于每一对可能的描述函数和我们总能找到整个运动过程中狗绳最长的距离,通过改变和可使得这个最长的狗绳达到最小,这个最小的距离即为Fréchet距离。当然,这个距离也可以是其他形式的距离测度,在这里我们采用欧拉距离。
基于此定义,Eiter 和 Mannila 于1994年提出了离散Fréchet距离的定义[4]。首先我们将上述两轨迹进行离散化,设曲线P是由p个轨迹点所组成,曲线Q是由q个轨迹点所组成。使用和分别表示两轨迹点的顺序集合,则有和。同时,我们可以得到如下序列点对L
其中,, 对于任意 有或和。
P、Q轨迹点之间的序列对之间长度定义为各序列对中欧式距离最大的值,表达式如下
那么其离散Fréchet距离定义如下
可以很容易看出,同时如果,则就有和连续Fréchet距离一样其也满足三角不等式,即
3、连续Fréchet距离和离散Fréchet距离的关系[5]
离散Fréchet距离是连续Fréchet距离的近似,当曲线所选取的离散点足够多时离散Fréchet距离近似等于连续Fréchet距离。
图3:连续Fréchet距离和离散Fréchet距离示意图
4、离散Fréchet距离计算算法[4]
5、代码示例
function dF = DiscreteFrechetDistance(P,Q)%%%initializeSize_P = size(P);Size_Q = size(Q);ca = ones(Size_P(1),Size_Q(1)) .* -1;if Size_P(2) ~= Size_Q(2) error('The input P and Q must be of the same dimension');elseif Size_P(1) == 0 && Size_Q(1) == 0 dF = 0; return;enddF = c(Size_P(1),Size_Q(1));%%%function cfunction c_ij = c(i,j) d = @(u,v) sqrt(sum((u - v).^2)); if ca(i,j) > -1 c_ij = ca(i,j); elseif i==1 && j==1 ca(i,j) = d(P(1,:),Q(1,:)); c_ij = ca(i,j); elseif i > 1 && j == 1 ca(i,j) = max(c(i - 1,1),d(P(i,:),Q(1,:))); c_ij = ca(i,j); elseif i == 1 && j > 1 ca(i,j) = max(c(1,j - 1),d(P(1,:),Q(j,:))); c_ij = ca(i,j); elseif i > 1 && j > 1 ca(i,j) = max(min([c(i - 1,j),c(i - 1,j - 1),c(i,j - 1)]),d(P(i,:),Q(j,:))); c_ij = ca(i,j); else ca(i,j) = inf; endendend
6、参考文献
[1] Fréchet M M. Sur quelques points du calcul fonctionnel[J]. Rendiconti Del Circolo Matematico Di Palermo, 1906, 22(1):1-72.
[2] Wylie T, Zhu B. Intermittent Map Matching with the Discrete Fr\’echet Distance[J]. Eprint Arxiv, 2014.
[3] Alt H, Godau M. Computing the Fréchet Distance between Two Polygonal Curves[J]. International Journal of Computational Geometry & Applications, 1995, 5(01n02):75-91.
[4] Eiter T, Mannila H. Computing discrete Fréchet distance[R]. Tech. Report CD-TR 94/64, Information Systems Department, Technical University of Vienna, 1994.
[5] Timothy, Randall, Wylie. THE DISCRETE FRECHET DISTANCE AND APPLICATIONS[D]. Montana State University Bozeman, 2013,7-8.