目录

  • 离散Fréchet算法
    • 总结
    • Fréchet算法原理[^1]
    • Fréchet算法实现
    • 参考:

离散Fréchet算法

总结

实现Fréchet算法的过程中巩固递归算法的基本操作,就是终止条件和Max或Min的计算;而且使用尾递归而不是普通的递归在python和C中实现更好的效率。

Fréchet算法原理1

度量空间中两条曲线之间的 Fréchet 距离是曲线之间相似性的度量。 算法的离散实现提供了连续测量的良好近似值,并且可以使用简单的算法有效地计算。

给定度量空间中的两条曲线,它们之间的 Fréchet 距离 δF 可以直观地定义如下。

一个人用皮带牵狗:人可以在一条曲线上移动,而狗在另一条曲线上;两者都可以改变它们的速度,但不允许回溯。足以穿过两条曲线的最短皮带长度是多少? Fréchet 距离是曲线之间相似性的度量,它考虑了沿曲线的点的位置和顺序。因此它通常比众所周知的豪斯多夫距离要好。这个距离函数是由 Fréchet 在 1906 年引入的 。 Alt 和 Godau对 Fréchet 距离的计算特性进行了基础研究。他们给出了一种算法,可以在 O(pq log2 pq) 时间内计算两条多边形曲线之间的精确 Fréchet 距离,其中 p 和 q 是多边形曲线上的段数。该算法相当复杂,因为它使用参数搜索技术。在本文中,描述了多边形曲线的 Fréchet 距离的离散变化。这种变化称为耦合距离δdF。它基于查看多边形曲线的线段端点之间所有可能的耦合的想法。我们证明 δdF 提供了很好的 δF 近似值。具体来说,我们表明 δdF 是 δF 的上限,并且这些度量之间的差异受多边形曲线最长边的长度的限制。我们还表明,可以使用非常简单的算法在 O(pq) 时间内计算 δdF。在这些结果的基础上,以下近似计算两条任意曲线之间的 Fréchet距离的方法不言自明:首先计算曲线的适当多边形近似,然后计算它们的耦合距离,而不是计算它们的精确 Fréchet距离。

Fréchet算法实现

算法的伪代码如下:

算法的python代码实现如下,参考2

# 部分代码参考:https://github.com/spiros/discrete_frechetimport numpy as npdef frechet_distance_recursion(ca, i, j, p, q):if ca[i, j] > -1:return ca[i, j]elif i == 0 and j == 0:ca[i, j] = np.linalg.norm(p[i]-q[j])elif i > 0 and j == 0:ca[i, j] = max(frechet_distance_recursion(ca, i-1, 0, p, q), np.linalg.norm(p[i]-q[j]))elif i == 0 and j > 0:ca[i, j] = max(frechet_distance_recursion(ca, 0, j-1, p, q), np.linalg.norm(p[i]-q[j]))elif i > 0 and j > 0:ca[i, j] = max(min(frechet_distance_recursion(ca, i-1, j, p, q),frechet_distance_recursion(ca, i-1, j-1, p, q),frechet_distance_recursion(ca, i, j-1, p, q)),np.linalg.norm(p[i]-q[j]))else:ca[i, j] = float('inf')return ca[i, j]def frechet_distance(p, q):p = np.array(p, np.float64)q = np.array(q, np.float64)len_p = len(p)len_q = len(q)if len_p == 0 or len_q == 0:raise ValueError('Input curves are empty.')if len_p != len_q or len(p[0]) != len(q[0]):raise ValueError('Input curves do not have the same dimensions.')ca = (np.ones((len_p, len_q), dtype=np.float64) * -1)dist = frechet_distance_recursion(ca, len_p-1, len_q-1, p, q)return distif __name__=='__main__':p=[[1,1], [2,1], [2,2]]q=[[2,2], [0,1], [2,4]]dist = frechet_distance(p, q)  # 2.0

参考:


  1. Eiter T, Mannila H. Computing discrete Fréchet distance[J]. 1994. ↩︎

  2. GitHub - spiros/discrete_frechet: Compute the Fréchet distance between two polygonal curves in Euclidean space. ↩︎

离散Fréchet算法相关推荐

  1. 离散Fréchet(弗雷歇) 距离评价曲线相似度

    离散Fréchet(弗雷歇) 距离评价曲线相似度 1.引言 对于如何评价两条曲线的相似度现已经存在许多较为直接有效的方法,诸如基于各种距离测度的距离评判.利用相关系数进行相似度分析等等,其中对于距离测 ...

  2. Chirp信号公式与对离散生成算法之间的差异

    讨论产生线性频率变化的公式和它的离散公式之间的差异,并提出Chirp信号的修改方案. Chirp信号的公式 对于固定频率f1f_1f1​的信号,它的表达式为:r(t)=cos⁡(2π⋅f1⋅t)r\l ...

  3. 理解快速离散傅里叶变换算法(FFT)

    本文是视频The Fast Fourier Transform (FFT): Most Ingenious Algorithm Ever?的整理. 离散傅里叶变换的用法 FFT是一个非常快速的离散傅里 ...

  4. 网格离散曲率算法(二次曲面拟合)

    方法引进 很多情况下离散网格计算曲率是必要的,在浙江大学方惠兰学姐的硕士论文网格曲面上离散曲率计算方法的比较与研究中,对各种不同计算网格曲率的方法做了总结,我这里是借鉴MATLAB论坛中的一篇D.Kr ...

  5. 离散ziggurat算法python实现_一种基于LWE采样算法的实现与优化

    一种基于 LWE 采样算法的实现与优化 王柯翔,黎 琳,彭双和 [摘 要] 基于带错误学习问题 (Learning With Errors , LWE) 构造的密码体制 能够抵御量子攻击,它的应用效率 ...

  6. Discrete Fourier Transform离散傅里叶变换算法

    DFT 公式: Ak=∑n=0N−1e−i2πNknan,k∈{0,1,...N−1}A_k = \sum_{n=0}^{N-1}e^{-i\frac{2\pi}{N}kn}a_n , k\in \{ ...

  7. 离散免疫算法求解旅行商问题(源码实现)

    旅行商问题     旅行商问题(TSP 问题).假设有一个旅行商人要拜访全国31个省会城市,他需要选择所要走的路径,路径的限制是每个城市只能拜访-一次, 而且最后要回到原来出发的城市.路径的选择要求是 ...

  8. No.03 色散补偿 FSM算法 频域离散采样算法 MATLAB Python 代码实现

    色散系统的频域传输方程如下 G ( z , w ) = e D λ 2 z j 4 π c ω 2 G(z,w)=e^{\frac{D\lambda^2z}{j4\pi c}\omega^2} G(z ...

  9. 离散ziggurat算法python实现_花式生成正态分布

    ◆◆ ◆ 前言 "So much of life, it seems to me, is determined by pure randomness." – Sidney Poit ...

最新文章

  1. 应届生求职数据分析师指南
  2. java criteria and_criteria用法
  3. 舒尔特注意力训练表格_舒尔特注意力训练,舒尔特方格练习入口
  4. 微服务的隔离和熔断机制
  5. hdu 2553 N皇后问题
  6. ipython快捷键
  7. web 页面间传值 js 封装方法
  8. lpop 原子_从夸克到原子,到元素周期表
  9. 各大搜索引擎提交入口
  10. 亲测免费下载知网论文方法
  11. springboot/vue 前后端分离项目搭建流程
  12. 『尼罗河魅影之谜』的故事模式与推理内核
  13. 什么是动态代理,动态代理的应用有哪些
  14. python spring框架_Spring Python
  15. df pd 属性_DataFrame 常用方法属性
  16. rt-thread物联网开发板mqtt实验
  17. R6034错误的解决(转)
  18. react 学习(三) 组件更新
  19. 【控制系统数字仿真与CAD——实验报告】实验四:黄金分割法最优化PI调节器参数(文末附完整代码 + 实验结果)
  20. plsql-数据查询(二、条件查询)

热门文章

  1. word2019 添加 mathtype 加载项
  2. 拳王虚拟项目公社:如何利用信息差在闲鱼赚钱,闲鱼月入十万的小白怎么玩?
  3. 第6版PMBOK,PMP备考(组织过程资产)
  4. 多用户小程序商城系统优势是什么?jsudo
  5. 让算法互掐的炸飞机游戏平台
  6. LayoutInflater.from(this)、inflate 详解
  7. 【91xcz】通过闪存盘启动电脑进行Windows 8系统安装
  8. 互联网进入千兆时代,智能路由器PK焦点是谁更快?
  9. Android重启应用和重启手机
  10. 深富策略:北交所首秀抢眼 沪深指数微跌