专栏名称: Hic Rhodus, hic salta

路径相似性描述：Fréchet distance

Hic Rhodus, hic salta · 知乎专栏 · AI · 2015-08-13 23:20

正文

请到「今天看啥」查看全文

Fréchet distance(弗雷歇距离)是法国数学家 Maurice René Fréchet 在1906年提出的一种路径空间相似形描述( 此外还在这篇论文里定义了度量空间)，这种描述同时还考虑进路径空间距离的因素[1]，对于空间路径的相似性比较适用。

直观的理解，Fréchet distance就是狗绳距离：主人走路径A，狗走路径B，各自走完这两条路径过程中所需要的 最短狗绳长度 。

严格的数学定义 如下：

设二元组 $(\boldsymbol{S},d)$ 是一个度量空间，其中 $d$ 是 $\boldsymbol{S}$ 上的度量函数.

1. 在单位区间 $[0, 1]$ 上的映射 $\gamma :[0,1]\rightarrow \boldsymbol{S}$ 是连续映射，则称 $\gamma$ 为 $\boldsymbol{S}$ 上的连续曲线。

2. 从单位区间到其自身的映射 $\zeta :[0, 1]\rightarrow [0,1]$ ，满足如下三个条件：1) $\zeta$ 是连续的，2) $\zeta$ 是非降的，即对于任意 $x,y\in [0, 1]$ ，且 $x\leq y$ ，都有 $\zeta (x)\leq \zeta (y)$ 成立，3) $\zeta$ 是满射，则称函数 $\zeta$ 为单位区间 $[0, 1]$ 的重参数化函数，且此时有 $\zeta (0)=0$ ， $\zeta (1)=1$ . 特别地，当 $\zeta$ 为恒等函数 $\zeta (x)=x$ 时，称 $\zeta$ 为平凡重参数化函数，否则，称 $\zeta$ 为非平凡重参数化函数。显然的，单位区间的重参数化函数有无穷多个。

3. 设 $A$ 和 $B$ 是 $\boldsymbol{S}$ 上的两条连续曲线，即 $A :[0, 1]\rightarrow \boldsymbol{S}$ ， $B :[0, 1]\rightarrow \boldsymbol{S}$ . 又设 α 和 β 是单位区间的两个重参数化函数，即 $\alpha :[0, 1]\rightarrow \boldsymbol{S}$ ， $\beta :[0, 1]\rightarrow \boldsymbol{S}$ . 则曲线 $A$ 与曲线 $B$ 的弗雷歇距离 $F(A, B)$ 定义为

$F(A, B)=\inf_{\alpha,\beta}\max_{t\in [0, 1]} \{d (A(\alpha (t)), B(\beta (t))) \}$

其中 $d$ 是 $\boldsymbol{S}$ 上的度量函数.

数字化/离散化

设定 $t$ 是时间点，该时刻，曲线 $A$ 上的采样点为 $A(\alpha (t))$ , 曲线 $B$ 上采样点为 $B(\alpha (t))$ . 如果使用欧氏距离，则容易定义 $d (A(\alpha (t)), B(\beta (t)))$ . 在每次采样中 $t$ 离散的遍历区间 $[0,1]$ , 得到该种采样下的最大距离 $\max_{t\in [0, 1]} \{d (A(\alpha (t)), B(\beta (t))) \}$ . 弗雷歇距离就是使该最大距离最小化的采样方式下的值。

易于理解的，在离散方式下，我们不可能得到真实的弗雷歇距离，而可以无限的趋近。但是越精确的值需要越大的计算量。

$F(A, B)=\lim_{n\rightarrow \infty ,max{\left | t_k - t_{k+1})\right |}\rightarrow 0} {\widetilde{F}^{n}(A,B)}=\lim_{n\rightarrow \infty ,max{\left | t_k - t_{k+1})\right |}\rightarrow 0}\inf_{\alpha,\beta}\max_{t\in \{t_k\}} \{d (A(\alpha (t)), B(\beta (t))) \}$

基于该离散思想，对应的两条空间(3D)路径弗雷歇距离matlab代码如下：

%% Frechet Distance between two curves (3D)

%%

function f = frechet3D(P1,P2,varargin)

X1=P1(:,1);

X2=P2(:,1);

Y1=P1(:,2);

Y2=P2(:,2);

Z1=P1(:,3);

Z2=P2(:,3);

%get path point length

L1=length(X1);

L2=length(X2);

%check vector lengths

if or(L1~=length(Y1),L2~=length(Y2))

    error('Paired input vectors (Xi,Yi) must be the same length.')

end

%check for column inputs

if or(or(size(X1,1)<=1,size(Y1,1)<=1),or(size(X2,1)<=1,size(Y2,1)<=1))

    error('Input vectors must be column vectors.')

end

%create maxtrix forms

X1_mat=ones(L2,1)*X1';

Y1_mat=ones(L2,1)*Y1';

Z1_mat=ones(L2,1)*Z1';

X2_mat=X2*ones(1,L1);

Y2_mat=Y2*ones(1,L1);

Z2_mat=Z2*ones(1,L1);

%calculate frechet distance matrix

frechet1=sqrt((X1_mat-X2_mat).^2+(Y1_mat-Y2_mat).^2+(Z1_mat-Z2_mat).^2);

fmin=min(frechet1(:));

fmax=max(frechet1(:));

%handle resolution

if ~isempty(varargin)

    res=varargin{1};

    if res<=0

        error('The resolution parameter must be greater than zero.')

    elseif ((fmax-fmin)/res)>10000

        warning('Given these two curves, and that resolution, this might take a while.')

    elseif res>=(fmax-fmin)

        warning('The resolution is too low given these curves to compute anything meaningful.')

        f=fmax;

        return

    end

else

    res=(fmax-fmin)/100;

end

%compute frechet distance

clear f

for q3=fmin:res:fmax

    im1=bwlabel(frechet1<=q3);

%get region number of beginning and end points

    if and(im1(1,1)~=0,im1(1,1)==im1(end,end))

        f=q3;

        break

    end

end

if (~(exist ('f')))

    f=fmax;

end

% disp(f)

return

--------

[1] Fréchet, M. Maurice. "Sur quelques points du calcul fonctionnel." Rendiconti del Circolo Matematico di Palermo (1884-1940) 22.1 (1906): 1-72.