当前位置：首页 > news >正文

三维空间中的离散曲线段匹配方法

news 来源：原创 2025/9/19 6:50:59

基于离散 $Fr\'{e}chet$ 距离实现工程中的三维曲线段匹配

在自动驾驶系统中, 准确匹配相邻车道线是实现安全导航, 变道决策和路径规划的核心任务. 由于道路网络存在交叉口, 弯道, 多车道并行等复杂场景, 如何衡量目标车道曲线与其他候选车道线的空间关系, 成为高精度定位的关键技术挑战. 本文将以离散 $Fr\'{e}chet$ 距离为核心, 解析其在三维道路曲线匹配中的原理, 计算方法及Python实现.

文章目录

基于离散 $Fr\'{e}chet$ 距离实现工程中的三维曲线段匹配
- 一问题实例: 自动驾驶中的车道线匹配挑战
- - 1.1 邻车道匹配的意义
  - 1.2 技术难点
- 二离散 $Fr\'{e}chet$ 距离: 定义与优势
- - 2.1 直观理解: 狗绳距离
  - 2.2 数学定义
  - 2.3 为何选择 $Fr\'{e}chet$ 而非Hausdorff？
- 三离散 $Fr\'{e}chet$ 距离的算法实现
- - 3.1 动态规划解法
  - - 步骤1: 构建距离矩阵
    - 步骤2: 动态规划递推
- 四 Python中的实现方案
- - 4.1 现有库推荐
  - 4.2 自定义实现 (三维支持)
- 五实际应用中的小技巧
- 六性能对比

一问题实例: 自动驾驶中的车道线匹配挑战

1.1 邻车道匹配的意义

在动态交通环境中, 车辆需实时判断自身车道与相邻车道的位置关系, 以实现以下功能:

变道决策: 判断相邻车道是否存在足够安全空间
路径纠偏: 识别车辆是否意外偏离当前车道
路口导航: 在交叉口匹配转向车道的几何形态

1.2 技术难点

几何复杂性: 车道线可能存在垂直交叉 (如十字路口) , 非均匀曲率 (如匝道)
投影失效: 曲线段间作垂线, 垂足可能落在线段外, 传统欧氏距离失效
计算效率: 需在毫秒级时间内处理高密度点云数据

二离散 $Fr\'{e}chet$ 距离: 定义与优势

2.1 直观理解: 狗绳距离

离散 $Fr\'{e}chet$ 距离的经典类比是牵狗模型: 主人和狗分别沿两条曲线行走, 可调整各自速度但不允许后退. $Fr\'{e}chet$ 距离即定义为所需狗绳的最短长度. 这一度量强制考虑曲线的顺序性和方向性, 尤其适合车道线的连续性特征.

2.2 数学定义

给定两条点列曲线 $P = \{p_1, p_2, ..., p_m\}$ 和 $Q = \{q_1, q_2, ..., q_n\}$ , 其离散 $Fr\'{e}chet$ 距离定义为:

$\delta_{dF}(P,Q) = \min_{\text{coupling}} \left( \max_{(i,j) \in \text{coupling}} \|p_i - q_j\| \right)$

其中, coupling为同向排列的点对序列.

2.3 为何选择 $Fr\'{e}chet$ 而非Hausdorff？

顺序敏感: Hausdorff距离忽略点序, 可能高估交叉车道的相似性 (如垂直路口)
噪声鲁棒: $Fr\'{e}chet$ 的最大最小距离机制对局部扰动更稳健

三离散 $Fr\'{e}chet$ 距离的算法实现

3.1 动态规划解法

Eiter和Mannila提出的动态规划算法是主流实现方案, 时间复杂度为 $O (mn)$ . 核心步骤如下:

步骤1: 构建距离矩阵

计算所有点对间的欧氏距离:

def euc_dist(p, q):return np.sqrt(np.sum((p - q)**2, axis=1))  # 支持三维坐标(x,y,z)
distance_matrix = [[euc_dist(pi, qj) for qj in Q] for pi in P]

步骤2: 动态规划递推

初始化边界条件, 递推填充代价矩阵 $C$ :

$\max \left( d(p_i, q_j), \min \left( C(i-1,j), C(i,j-1), C(i-1,j-1) \right) \right)$

Python实现核心逻辑:

for i in range(1, m):for j in range(1, n):C[i][j] = max(distance_matrix[i][j], min(C[i-1][j], C[i][j-1], C[i-1][j-1]))

一些可能有用的加速方法:

降采样: 对车道线点云进行均匀采样, 减少计算量
空间索引: 利用KD-Tree加速最近邻搜索
并行计算: 将距离矩阵分块, 利用GPU加速 (如CuPy库)

四 Python中的实现方案

4.1 现有库推荐

Shapely库 shapely.frechet_distance可直接计算二维线段的 $Fr\'{e}chet$ 距离, 支持 densify参数提升精度. 但目前仅可直接计算二维空间的线段距离:

from shapely import LineString, frechet_distance
line1 = LineString([(0,0), (1,2), (3,1)])
line2 = LineString([(0,1), (2,0), (3,2)])
print(frechet_distance(line1, line2, densify=0.5))

第三方库 frechetdist
支持三维点云, 需自行安装:

pip install frechetdist

使用示例:

 from frechetdist import frdistimport numpy as npP = np.array([[1,2,0], [3,4,0.1], [5,6,0.2]])Q = np.array([[2,3,0], [4,5,0.15], [6,7,0.25]])print(frdist(P, Q))

4.2 自定义实现 (三维支持)

针对自动驾驶的三维点云 (含高程信息) , 可扩展动态规划方法:

import numpy as npdef discrete_frechet_3d(P, Q):m, n = len(P), len(Q)C = np.zeros((m, n))# 初始化首行首列C[0,0] = np.linalg.norm(P[0]-Q[0])for i in range(1, m):C[i,0] = max(C[i-1,0], np.linalg.norm(P[i]-Q[0]))for j in range(1, n):C[0,j] = max(C[0,j-1], np.linalg.norm(P[0]-Q[j]))# 递推填充矩阵for i in range(1, m):for j in range(1, n):C[i,j] = max(np.linalg.norm(P[i]-Q[j]),min(C[i-1,j], C[i,j-1], C[i-1,j-1]))return C[-1,-1]# 示例: 两条三维车道线
P = np.array([[1,2,0], [3,4,0.1], [5,6,0.2]])
Q = np.array([[2,3,0], [4,5,0.15], [6,7,0.25]])
print(discrete_frechet_3d(P, Q))

五实际应用中的小技巧

多尺度加权

在交叉口等高曲率区域增加权重:

$w_i = 1 + \kappa(p_i)$

其中曲率 $\kappa$ 可通过相邻点夹角计算:

def compute_curvature(P):curvatures = []for i in range(1, len(P)-1):v1 = P[i] - P[i-1]v2 = P[i+1] - P[i]angle = np.arccos(np.dot(v1,v2)/(np.linalg.norm(v1)*np.linalg.norm(v2)))curvatures.append(angle)return np.array(curvatures)

预先计算线段方向

取两段待比较曲线点列各自起始和末尾的两个点, 计算向量的点积, 根据点积的正负, 就可以确定两段待比较曲线的同向顺序.

六性能对比

方法	时间复杂度	三维支持	适用场景
动态规划原生实现	O(mn)	是	精确匹配, 离线计算
Shapely库	O(mn)	否	二维实时匹配
frechetdist	O(mn)	是	三维在线计算
曲率加权优化	O(mn + m)	是	复杂道路结构

三维空间中的离散曲线段匹配方法

基于离散 F r e ˊ c h e t Fr\{e}chet Freˊchet距离实现工程中的三维曲线段匹配在自动驾驶系统中, 准确匹配相邻车道线是实现安全导航, 变道决策和路径规划的核心任务. 由于道路网络存在交叉口, 弯道, 多车道并行等复杂场景, 如何衡量目标车道曲线与其他候选车道线的空间关…...

编程日记 2025/9/19 6:50:59

HTML的Canvas元素

<Canvas>元素 <Canvas>元素是HTML5引入的一个强大的绘图元素，它允许通过 JavaScript 在网页上动态绘制图形、动画和交互式内容。需要注意的是，<Canvas>元素只是图形的一个容器，绘制图形必须使用Javascript。空画布 <…...

编程日记 2025/9/18 22:28:55

Django学习记录-2-数据库

Django学习记录-2-数据库文章目录 Django学习记录-2-数据库参考贴连接数据库后台查看数据库后台改为中文 table增删改查Python使用hash保持一致虽然网上教程都很多，但是感觉自己记录一下才属于自己，之后想找也方面一点，文采不佳看的不爽可绕…...

编程日记 2025/9/9 14:38:52

qq邮箱群发程序

1.界面设计 1.1 环境配置在外部工具位置进行配置 1.2 UI界面设计 1.2.1 进入QT的UI设计界面在pycharm中按顺序点击，进入UI编辑界面： 点击第三步后进入QT的UI设计界面，通过点击按钮进行界面设计，设计后进行保存到当前Pycharm…...

编程日记 2025/9/19 0:58:08

spring mvc 中 RestTemplate 全面详解及示例

RestTemplate 全面详解及示例 1. RestTemplate 简介定义：Spring 提供的同步 HTTP 客户端，支持多种 HTTP 方法（GET/POST/PUT/DELETE 等），用于调用 RESTful API。核心特性： 支持请求头、请求体、URI 参数的…...

编程日记 2025/9/15 11:20:10

openEuler-22.03-LTS-SP3 编译安装 Greenplum-db 6.20.0

openEuler-22.03-LTS-SP3 编译安装 Greenplum-db 6.20.0 1、配置 yum 华为源2、安装依赖3、源码安装 openssl 1.0.1u3.1、openssl 1.1.1 降级到 openssl 1.0.1 4、源码安装 python 2.75、使用 pip3 安装 Python 相关依赖6、编译安装 Greenplum-db 6.20.06.1、修改配置6.2、基于…...

编程日记 2025/9/19 4:52:13

天锐蓝盾多模式加密技术，构筑企业数据安全堡垒

一旦企业发生数据泄露，将遭受严重的经济损失，声誉也会一落千丈，甚至可能在激烈的竞争中陷入绝境。那么，企业究竟该如何守护敏感数据，筑牢数据安全的 “护城河” 呢？天锐蓝盾数据泄露防护系统给出了全面且专…...

编程日记 2025/9/18 22:44:11

可编辑37页PPT | 建筑行业DeepSeek日常实操培训

荐言摘要：随着人工智能技术的快速发展，DeepSeek作为一款具有创新性的AI工具，正逐步渗透到建筑行业的各个环节。为帮助建筑行业从业者掌握DeepSeek的核心功能与应用技巧，提升工作效率与决策能力，特推出本次建筑行业Deep…...

编程日记 2025/9/19 1:50:10

C语言指针和函数

文章目录 C语言指针和函数一、指针与函数1.传递指针给函数2.指针函数3.函数指针4.回调函数二、多级指针三、空指针四、野指针 C语言指针和函数在C语言的编程领域中，指针是一把强大而又危险的“双刃剑”。它不仅能够直接操作内存，提升程序的运行效率&a…...

编程日记 2025/9/5 10:52:40

左右开弓策略思路

一、策略概述本策略是一种基于多种技术指标的复杂交易策略，包括自定义指标计算、过滤平滑处理以及交易信号生成。该策略通过不同的交易平台代码段实现，旨在通过分析历史价格数据来预测未来价格走势，并据此生成交易信号。二、主要技术指标…...

编程日记 2025/9/19 6:49:37

mapbox基础，加载F4Map二维地图

👨‍⚕️ 主页： gis分享者 👨‍⚕️ 感谢各位大佬点赞👍 收藏⭐ 留言📝 加关注✅! 👨‍⚕️ 收录于专栏：mapbox 从入门到精通文章目录一、🍀前言1.1 ☘️mapboxgl.Map 地图对象1.2 ☘️mapboxgl.Map style属性二、🍀F4Map 简介2.1 ☘️技术特点2.2 ☘️核…...

编程日记 2025/9/12 18:00:08

doxygen自动生成文档，注释容易错位的补充

开发过程中，为了简化api开发文档的编写工作，我们可以使用doxygen的标注来进行文档注释，最后自动化的生成相关文档： 参考：https://developer.aliyun.com/article/935529 参考：https://blog.csdn.net/qq_3459…...

编程日记 2025/9/16 1:59:04

git操作0409

git init git add. git commit -m "Initial commit" git checkout 7890abc # 切换到旧版本代码（只读） git checkout master # 切回最新版本 git checkout -b new_branch 789abcd # 或 git checkout -b new_branch HEAD~3 很重点 git reflog …...

编程日记 2025/9/6 18:32:27

电阻的额定功率与额定电压详解

一、基本定义额定功率（Rated Power） 定义：电阻在长期安全工作时允许消耗的最大功率，超过此值可能导致过热甚至烧毁。公式： P I R 或 P V / R （I：电流，V：电压&#…...

编程日记 2025/9/2 22:22:26

【后端开发】SpringBoot与Spring MVC

文章目录创建项目目录介绍Spring MVCservletMVCSpring MVCSpringboot与Spring MVC的区别Spring MVC交互创建项目新建一个Springboot项目对应描述目录介绍 src/main/java：Java 源代码 src/main/resources：为静态资源或配置⽂件： ----…...

编程日记 2025/9/17 18:24:14

如何禁用 PyCharm 的测试功能

如何禁用 PyCharm 的测试功能？ PyCharm 的测试功能默认会自动检测项目中符合命名规则的测试文件（如以 test_ 开头的文件）并关联测试框架。若需禁用该功能，可通过以下方法操作： 方法一：全局禁用默认测试框架…...

编程日记 2025/9/9 19:52:53

【Spiffo】光速项目：LVGL v9框架下的MIPI简易相机_Part2

简介本期接上回的工程部署讲一下整个工程的框架逻辑以及相关的模块作用机制，包括mipi抓图像以及后续传递到显示屏的链路逻辑等。一、核心逻辑 1、如何抓到图像数据并显示首先能够从摄像头捕获画面并显示是一个相机最起码要能实现的功能。所以先要搞清楚整个链…...

编程日记 2025/9/10 1:28:31

pycharm编译部署智能合约（solcx与web3搭配）

solcx 是一个 python 库，提供了 solidity 编译器的 python 绑定。它使开发者能够直接从 python 中编译 solidity 源代码，生成以太坊智能合约的字节码（Bytecode）和 ABI（Application Binary Interface）。这个库通常用于与 Web3 库配合使用，帮助开发者进行智能合约的部署、…...

编程日记 2025/9/15 3:12:29

微信小程序中的openid的作用

微信小程序中的openid的作用引言在当今数字化时代，用户体验成为了产品成功与否的关键因素之一。微信小程序作为连接用户与服务的重要桥梁，在提升用户体验方面发挥着重要作用。其中， openid（开放身份标识符）是微信小…...

编程日记 2025/9/11 18:09:07

AAAI 2025新研究！大语言模型+MARL=论文新思路？

最新研究显示，多智能体强化学习（MARL）正迎来一系列技术革新，让AI系统真正具备“群体智能”。同济大学团队提出的动态图通信网络（TGCNet），通过Transformer建模智能体间的动态协作关系&#xff0c…...

编程日记 2025/9/7 18:50:18

旅行世界宠物养殖合成游戏源码

旅行世界宠物养殖合成游戏源码，游戏养成类系统，用户能够通过养狗和参加其他活动获取算力，每日任务不断更新，完结即可收取算力，算力能够兑换现金红包。邀请好友得两级活跃收益提成，徒弟B100.%，徒…...

编程日记 2025/9/11 19:04:52

列表之链表_C

数据结构（邓俊辉）：列表及相关概念_listnodeposi-CSDN博客 #include <stdio.h> #include <stdlib.h>// 定义Rank类型为int typedef int Rank;// 定义ListNode结构体 typedef struct ListNode {int data;struct ListNode* pred;st…...

编程日记 2025/8/31 11:23:46

图解Java设计模式

1、设计模式面试题 2、设计模式的重要性 3、7大设计原则介绍...

编程日记 2025/9/7 14:42:59

CCF GESP Python编程四级认证真题 2025年3月

Python 四级 2025 年 03 月题号 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 答案 D C B C D C A A D B D A C B C 1 单选题（每题 2 分，共 30 分） 第 1 题 2025年春节有两件轰动全球的事件，一个是DeepSeek横空出世，另一个是…...

编程日记 2025/9/11 20:53:14

2025最新系统 Git 教程（四）

2.6 Git 基础 - 打标签打标签像其他版本控制系统（VCS）一样，Git 可以给仓库历史中的某一个提交打上标签，以示重要。比较有代表性的是人们会使用这个功能来标记发布结点（ v1.0 、 v2.0 等等）。在本节中…...

编程日记 2025/9/15 1:39:01

数学知识——欧拉函数

欧拉函数 1 ∼ N 1∼N 1∼N 中与 N N N互质的数的个数被称为欧拉函数，记为 ϕ ( N ) \phi(N) ϕ(N)。欧拉函数对于 N p 1 α 1 p 2 α 2 p 3 α 3 . . . p k α k Np_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}...p_k^{\alpha_k} Np1α1p2α2p3α3…...

编程日记 2025/9/18 21:16:24

Dify 识别 “subject“ and “intention“ 的提示词

Dify 识别 "subject" and "intention" 的提示词内容如下： You need to decompose the users input into "subject" and "intention" in order to accurately figure out what the users input language actually is. Not…...

编程日记 2025/9/17 19:10:58

Hi168云平台部署Ansible学习环境

前言之前发布的文章已经介绍过了在Hi168云平台部署openEuler学习环境，那么既然能部署openEuler了，其他的各类学习环境自然也就可以部署了。 Ansible简介 Ansible 是一个运维自动化工具，可以通过 SSH 协议对远程主机进行管理，对…...

编程日记 2025/9/18 12:27:30

Anacond虚拟环境里安装GPU版本Pytorch

CUDA/cudnn/CUDAToolkit简单区分 pytorch与cuda关系简单介绍 pytorch是一个深度学习的框架，能够调用cuda进行gpu加速。一般来说你的电脑里是有相关cuda的驱动的（可用nvidia-smi命令验证，能运行就说明有，不能运行去搜索安装&#…...

编程日记 2025/9/19 2:16:33

FRP的proxies只是建立通道，相当于建立与服务器沟通的不同通道而不是直接将路由器与服务器云端沟通

没有更好的办法了吗，我看frpc.toml的里面可以设置两个proxies那我esp32的监听端口设置在frpc.toml里面它不也能跟云服务器建立联系吗，比如远程与本地端口都配置为5112那云服务器接收到的5112访问会以frp配置的本地端口5112转发到frp客户端的路由器&#…...

编程日记 2025/9/15 10:16:12

Android开发鸿蒙环境问题记录

Android开发鸿蒙环境问题记录 （用于记录开发中鸿蒙环境差异及问题，持续更新） 2025.4.9 问题使用android.intent.action.TIME_TICK广播时，动态注册在鸿蒙4.0系统正常，但在鸿蒙3.0系统无法接收广播。解决方案在An…...

编程日记 2025/9/12 21:00:37

在 WSL2的 Ubuntu 20.04 中安装 Docker

WSL1升级到WSL2参考：WSL1升级到WSL2注意事项-CSDN博客 1. 更新系统包首先，确保系统包是最新的： sudo apt update sudo apt upgrade -y sudo apt upgrade -y 是 Ubuntu/Debian Linux 系统中的一条命令，用于升级所有已安装的软…...

编程日记 2025/9/15 22:01:04

LeetCode 252 会议室题全解析：Swift 实现 + 场景还原

文章目录摘要描述题解答案题解代码分析示例测试及结果时间复杂度空间复杂度总结摘要在这篇文章中，我们将深入探讨LeetCode第252题“会议室”的问题，提供一个用Swift编写的解决方案，并结合实际场景进行分析。通过这篇文章，你将…...

编程日记 2025/9/14 4:00:07

Postman的内网使用教程

在软件开发和测试过程中，接口测试是确保系统间通信正常的重要环节。当处于内网环境，无法直接访问外网资源时，如何高效地使用Postman进行接口测试也逐渐成为许多开发者关心的问题。前期准备安装Postman 从官方网站下载并安装最新版本的Pos…...

编程日记 2025/9/17 23:36:18

【软件测试】Postman中如何搭建Mock服务

在 Postman 中，Mock 服务是一项非常有用的功能，允许你在没有实际后端服务器的情况下模拟 API 响应。通过创建 Mock 服务，你可以在开发阶段或测试中模拟 API 的行为，帮助团队成员进行前端开发、API 测试和集成测试等工作。 Mock 服…...

编程日记 2025/9/14 17:28:27

【NLP 57、LLM通用能力评价方式】

人生如题，放下，是最优雅的解法 —— 25.4.9 目前，我们通过一些特殊的“集合”来评价大语言模型效果一、MMLU 集合测量大规模多任务语言理解评估模型在57个学科领域的综合知识理解能力，覆盖人文、社科、STEM&…...

编程日记 2025/9/14 11:47:07

centos7.9升级OpenSSL 1.1.1

centos7.9升级openssl 人工智能已经很准了： 问题： [rootcentos01 ~]# openssl version OpenSSL 1.0.2k-fips 26 Jan 2017 [rootcentos01 ~]# cat /etc/redhat-release CentOS Linux release 7.9.2009 (Core) 需要升级OpenSSL，请给出具体…...

编程日记 2025/9/8 1:30:43

10A 大电流 DCDC 降流芯片 WD5030

10A 大电流 DCDC 降压芯片 WD5030 在电子设备的电源管理领域，高效稳定的 DCDC 芯片至关重要。今天我们来深入探讨一款性能卓越的 10A 大电流 DCDC 降流芯片 ——WD5030。它在众多电子应用场景中展现出了强大的优势，为各类设备的稳定供电提供了可靠保障。…...

编程日记 2025/9/16 21:52:15

# 基于BERT的文本分类

基于BERT的文本分类项目的实现一、项目背景该文本分类项目主要是情感分析，二分类问题，以下是大致流程及部分代码示例： 二、数据集介绍 2.1 数据集基本信息数据集自定义类型二分类（正面/负面）样本量训练集验证…...

编程日记 2025/9/10 13:19:05

Verilog学习-1.模块的结构

module aoi(a,b,c,d,f);/*模块名为aoi，端口列表a、b、c、d、f*/ input a,b,c,d;/*模块的输入端口为a,b,c,d*/ output f;;/*模块的输出端口为f*/ wire a,b,c,d,f;/*定义信号的数据类型*/ assign f~((a&b)|(~(c&d)));/*逻辑功能描述*/ endmoduleveirlog hdl 程…...

编程日记 2025/9/11 16:38:46

界面控件DevExpress WPF v25.1新功能预览 - 数据网格、报表性能增强

DevExpress WPF拥有120个控件和库，将帮助您交付满足甚至超出企业需求的高性能业务应用程序。通过DevExpress WPF能创建有着强大互动功能的XAML基础应用程序，这些应用程序专注于当代客户的需求和构建未来新一代支持触摸的解决方案。无论是Office办公软件…...

编程日记 2025/9/11 9:02:33

【创新实训个人博客】prompt嵌入

通过对camel技术的理解，修改了项目内容能够初步实现广告内容相关的文本修改了typing.py中的定义 class RoleType(Enum): ASSISTANT "assistant" USER "user" CRITIC "critic" EMBODIMENT "embodiment" DEFAULT &q…...

编程日记 2025/9/13 21:41:07

Linux 进程的替换

进程程序替换要讲好这个我为大家准备了五个步骤 1. 先用代码给大家展示一下现象 2.解释原理 3.将代码改成多进程版 4.使用所有的方法，并认识函数参数的含义。 5.其他我们现在开始第一个 1. 先用代码给大家展示一下现象关于进程的替换一共有七个函数&…...

编程日记 2025/9/9 15:22:59

netty启用websocket的压缩机制

netty启用websocket的压缩机制 package com.aerotop.connector.websocket.base;import io.netty.channel.ChannelInitializer; import io.netty.channel.ChannelPipeline; import io.netty.channel.socket.SocketChannel; import io.netty.handler.codec.compression.JZlibDec…...

编程日记 2025/9/3 14:03:21

基于离散 F r e ˊ c h e t Fr\'{e}chet Freˊchet距离实现工程中的三维曲线段匹配