⽔平集（LevelSet）的基本⽅法
⽔平集（Level Set）的基本⽅法
⽔平集（Level Set）的基本⽅法-曲线演化的直观解释 映射 C(p), p\in [a,b] : R→R^2定义了⼀个平⾯的曲线， p是参数，对属于区间 [a,b]内的每⼀个 p_0，我们得到曲线上的⼀点：C(p_0)=[x(p_0),y(p_0))
正则曲线：如果
例：单位圆
曲线的切线
弧长参数
如果曲线的参数满⾜
p表⽰曲线上以某⼀点为标准的弧长.
弧长.
.
对弧长参数
.
.
假设T表⽰切线，N表⽰法线，则
.
Frenet公式
⽔平集（Level Set）的基本⽅法-数学基础－曲线的微分⼏何
曲率的其他定义
假设θ为切线T与x轴之间的夹⾓，则
.
隐式曲线的曲率
⽔平集（Level Set）的基本⽅法-数学直观
隐式曲线的法向量 .
.
因为切向量T和法向量N互相垂直，所以平⾯上任何曲线都可以⽤曲线上任何⼀点的T和N的线性组合来表⽰
.
⽔平集（Level Set）的基本⽅法-曲线演化的直观解释
如果只考虑⼏何形状的变化，那其变化只跟法线⽅向的变化有关系，则有
.
例：沿着曲率变化最⼤⽅向的曲线变形
.
最后变化为曲率都为常数的曲线停⽌，即圆.
⽔平集（Level Set）的基本⽅法-曲⾯演化的直观解释
平均曲率和⾼斯曲率
每个正则曲⾯都有两个主曲率
两个主曲率的平均值就是平均曲率
两个主曲率的积是⾼斯曲率
⽔平集（Level Set）的基本⽅法-数学基础－隐函数
隐函数(implicit function):⾃变量和因变量之间的法则是由⼀个⽅程式所确定.
.
例⼦
.
⽔平集（Level Set）的基本⽅法-数学基础－距离场函数
距离函数定.
.
距离函数的性质
.
科学计算可视化作为计算机应⽤学科中的⼀个分⽀，已⼴泛应⽤于医疗卫⽣、地质勘探、⽓象分析等与⼈类⽣活息息相关的重要领域，其主要⽬标就是把实际采样或模拟仿真得到的三维体数据通过体绘制技术，转化为⼈眼视觉容易感知的⼆维图像。我们在本次报告中，主要介绍⽔平集在地质数据可视化中的应⽤，图中出⽰了地质数据的⽰意图： 从图中可以看出，由于受到噪⾳的⼲扰，地质数据可视化是⼀个烦琐⽽具有挑战性的课题，主要存在如下两⽅⾯的挑战： Challenges of Seismic Visualization （1）An important component of oil and gas exploration （2）Difficult to segment the 3D bounding surface of many complex geologic features 为了更好的刻画地质数据中的断层、河道以及相⼲体信息，我们采⽤了⽔平集的⽅法进⾏分割处理，如图所⽰：
Level Set Method Implicit function { (x1,…,xn) | f(x1,…,xn) = c } where c is a constant. It is the set where the function takes on a given constant value. Implicit surface The point set represented by implicit function
The level set equation 如公式所⽰：
Dynamic implicit surfaces (in motion) Produce physically realizable surface models Modeling, simulation, and segmentation Implicit handling of complex topologies deformed by operations without destroying the representation
地质数据的绘制总体流程如图所⽰：
====== 第⼆节 Level Set ⽅法概念 ======
Level Set －⽔平集
Level set 的数学定义:
假设隐函数φ(x,t)表⽰⼀个⾼维空间的⽅程其在低维空间上的接触⾯为φ(x,t)=0，
其中
则level set表⽰为⽅程Γ(t)有如下性质，
其中接触⾯表⽰为：共青团是党领导的
φ(x,t)<0 for x∈Ω
φ(x,t)>0 for x∉‾Ω
φ(x,t)=0 for x∈∂Ω=Γ(t)
Level set 的运动表⽰
假设 则有
Level Set⽅法的⼏何意义
1）给定⼀个⾼维空间在低维空间（n维）定义上的接触⾯，分析和计算其边界在速度v下的运动轨迹
2）速度v是与位置，时间和接触⾯的⼏何形状有关的（如平均曲率，法向），还有外部的物理作⽤⼒。
(UCLA的Osher和Sethian⾸先提出了这个⽅法)
⼩结
Level set ⽅法实际上就是求解⼀个随时间变化的偏微分⽅程
其中Vn表⽰可以是任何关于时间，位置，⼏何等量的函数。
有时提到Level set ⽅法是指其数值解⽅法
应⽤Level set⽅法需要解决两个问题：
a 如何列出有意义的⽅程求解实际问题
b 如何能快速、稳定地求出⽅程的数值解
速度F成份
1.与曲率相关的所谓扩散项起到保持曲线的光滑性的作⽤
2.对流项为曲线演化提供动⼒⽀持
3.速度衰减因⼦使速度在边缘轮廓处停⽌
Level set 的主要优点就是其考虑了物体⼏何的⼀些更本质的特征（如曲率，梯度等），
太阳能浴室所以得到的结果能够⽐已有的⼀些其他⽅法要好。
Level Set的数值解法
应⽤Level Set的数值解法需要解决的两个问题
1. 列出对求解实际问题具有意义的⽅程；
2. 快速、⾼效，稳定的求解⽅程；
⼏种数值解法
1. Upwind差分法
基本思想：
稳定条件：
优缺点：算法简单，精度偏低，计算速度较慢
2. Hamilton-Jacobi ENO
基本思想 ：
⽤尽量光滑的多项式插值ψ，然后求解ψ(x)，使⽤HJ ENO⽅法
可以更精确地估计ψ(x)相关值 以及
3. Hamilton-Jacobi WENO
当采⽤三阶的HJ ENO⽅法，在计算 时，该算法需要知道 ，共有
三种⽅法⽤于估计 ，如果定义如下式⼦：
，则HJ-ENO算法的三种估计如右式：
HJ-ENO算法的主要⽬的就是从上述三个估计中选择⼀个最光滑的多项式逼近。由于HJ-ENO算法仅具有三阶精度，因此为了提⾼该算法的精度，
通过将三种进⾏加权，从⽽得到HJ-WENO算法，该算法的加权形式如下：
，
可以证明，该算法对光滑区域能够达到5阶的精度。
二维傅里叶变换4. TVD Runge-Kutta⽅法
上述三种算法中，HJ-ENO与HJWENO能够分别提供3阶，5阶精度，⽽Upwind算法仅能达到1阶的精度。相较于前三种算法，TVD Runge-Kutta算法能够提供更好的精度。
在TVD RK算法中，⼀阶TVD RK就是向前Euler算法(即Upwind算法)；
⼆阶TVD RK与⼆阶RK算法相似；
⽽三阶TVD RK算法，其形式如右式：
数值⽅法⼩结
Level Set的⼀般表现形式： ，
其中， 称为对流项， 称为曲率。
⼀般⽽⾔，求解该⽅程可以分三步⾛：
腾飞电开水器
1. ⽤ENO,WENO或upwind⽅法求解对流项；
2. ⽤中⼼差分的⽅法估算曲率；
3. ⽤TVD RK⽅法求解。
如下所⽰：
第三节⽔平集（Level Set）的建模⽅法与应⽤举例
背景: 借鉴⼀些流体中的重要思想，1988年，Osher和Sethian⾸次提出了⽔平集算法，这是⼀种有效解决曲线演化问题的数值⽅法，并且计算稳定，适宜任意维数空间。随后，Osher等⼈对⽔平集算法做出扩展和总结，Giga也做了相关的理论扩展。 90年代以来，许多学者纷纷加⼊Level Set⽅法的研究队伍，使得Level Set⽅法被⼴泛应⽤于计算机图形学、计算物理、图像处理、计算机视觉、化学、控制理论等众多领域。下⾯是⼀些在图形学⽅⾯的应⽤。海员培训
1 图像轮廓提取
1.1 边界检测和轮廓线提取
* 隐式动态轮廓模型。
* ⽤隐式模型可以跟踪拓扑变化的轮廓。
* 隐式轮廓线的微分⽅程表达为。
1.2 不⽤边界表达的动态轮廓线算法
其导数为：
边界长度可以表⽰为：
⽆边界表达的优化⽅程为：
实验结果如下：
2 图像分割
2.1 What is image segmentation?
* Definition:Separate the original image into regions that
are meaningful for a specific task. ( shape recovery)
2.2 Image Segmentation
2.3 基于Fast Marching技术的图像分割
* 算法框架
2.4 Mumford-Shah 图像分割
* Mumford-Shah模型
实验结果如下：
3 图像修复
3.1 图像填补(inpainting)
假设原始图像为图像填补算法将恢复⼀序列图像使得：即表达式为：其中是由⼀些规则定义的。
3.2 演化规则的定义
* 假设图像是光滑的
* 演化应该保持边界
3.3 演化的数学表达式
3.4 实验结果如下：
4 运动分析
(a)只有两个区域需要区分：前景和背景.
(b)I为输⼊图像由组成.
©是对图像的⼀个分割.
(d)是两个区域的公共边界.
* 边界表⽰物价指数
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议