基于半全局和全局算法的立体匹配研究
基于半全局和全局算法的立体匹配研究
摘要：
传统的基于像素点的匹配算法常常是算出初始匹配代价后直接采用贪心策略求取视差，虽然速度较快，但往往是局部最优的，以至精确度很低。针对这一问题，目前策略主要有：（1）半全局优化算法：扫描线算法和动态规划算法；（2）全局优化算法：置信度算法和图割算法。本文旨在通过详细讨论这四种算法原理本质，算法步骤与算法运行，从而深刻分析各自的优点与缺点，为进一步改进其不足，进而研究新的算法打下基础。 关键词：半全局优化，全局优化，扫描线，动态规划，置信度，图割 一．立体匹配介绍
图像的立体匹配即给定同一场景的两幅图像,寻找同一场景点投影到图像中的像素之间的对应关系。根据考虑的是基于像素点的还是基于区域块，可以分为基于像素点的匹配与基于区域的匹配。立体匹配算法通常是通过构建能量函数试图获得图像的某些全局性质,即全局能量最小化，但通常很难获得能量函数的全局最小化，鉴于此,很多学者更倾向于寻找局部小的求解.然而在一般情形下,局部小不能带来任何的全局性，所以匹配效果较差，准确率较低，基于像素点的匹配就是一种局部小的解，所以若想提高精度，研究的多是一种半全局或全局优化策略的区域匹配算法。
立体匹配的通常包括以下四步：
1) 图像预处理(Preprocessing)—由于拍摄照片的时候难免会有传感器的噪声
（sensor noise ）和光度的扭曲（photometric distortions ）而这都会对视差的计算带来
严重影响，常用的解决方法有，高斯拉普拉斯滤波(Laplacian of Gaussian (LoG) filtering )[1]
直方图均衡化(Histogram Equalization/Matching)，中值滤波 (Subtraction of mean
values computed in the neighbours of each pixel)[2]双边滤波(Bilateral filtering)[3]
。 2) 匹配代价计算（Matching cost computation ）—对匹配代价的计算通常有四种方法AD （1-1）、SAD （1-2）、SD （1-3）与SSD （1-4），计算公式，从而能得到元素的不同视差匹配代价所组成的初始视差空间。
))()(()(x R L x AD d x I x I abs d Cdata +-= (1-1)
2))()(()(x R L x SD d x I x I d Cdata +-= (1-2) ∑∈+-=W
x x R L x SAD d x I x I abs d Cdata ))()(()( (1-3)
2
))()(()(∑∈+-=W
x x R L x SSD d x I x I d Cdata (1-4)
3) 视差的计算(Disparity computation)—真实的像素视差是指这两个像素点具有高的相似性，传统的WTA （Winner Takes All ）算法就是每个像素点选取最小的代价来求取视差，是仅仅考虑一个像素的基于像素点匹配算法。如图(1)所示
Matching cost
Matching cost
4）视差的优化(disparity refinement.）—大多数立体匹配算法计算出来的视差是离散的，常常视差值都是整数，然而世界实际上是连续的，若想将立体匹配算法用在较高精度的场合，如机器人视觉，精密三维重建，这种离散的视差值不进行后续处理就无法达到令人满意的效果。针对这一问题，在获取初始视差后可以采用一些措施对视差进行细化，非整数视差，如匹配代价的曲线拟合如图 2 所示，或者直接采用亚像素精度法(sub-pixel disparity Estimate)，即将原图像进行水平拉伸，再对行像素点进行模糊。
本文将详细研究的就是立体匹配的视差计算阶段，就是在初步计算出来的视差空间中进行半全局或全局优化，从而求出更好的视差值。
与基于像素点的匹配方法不同，基于半全局或全局的算法通常是将匹配问题转换为一个能量方程，然后通过求解该能量方程的最小值来求取视差值。能量方程通常具有以下的形式
∑=
-+
=
W
x
x
x
x
d
d
V
d
Cdata
E
1
1
))
,
(
)
(
((1-5)
其中Cdata(d x)是数据项用来约束像素点在偏移前后的变化尽量小,V(d x,d x-1)是光滑项，约束像素点在偏移前后与周围像素点的关系变化尽量小。不同的优化算法的数据项和光滑项的定义不同，本文采取的数据项计算方法为AD。而光滑项则根据不同的算法用不同的模型方法。
二．匹配算法与实现
2.1扫面线优化方法
SO(Scanline Optimization)方法属于一种半全局能量最小化优化算法，比基于像素点匹配的算法有更好的适应性，通过最小化自身的能量方程来求得像素对应的视差，但是由于其只考虑一行的最优，并未考虑所有的像素点，所以本文称之为半全局能量最小化算法。
2.1.1算法原理：
SO的能量方程的光滑项通常为：
??
?==---others
_0)(1
1smooth opt d d if d d V x x x x (2-1) ??
?>?=others enalty opt_grad_p *opt_smooth
hresh opt_grad_t
opt_smooth _x I smooth opt (2-2) 其中opt_smooth 表示图片中像素点x 的光滑值，opt_grad_penalt 用来对同纹理区域(灰度梯度
值小于给定的阈值opt_grad_penalty )的区域进行惩罚的系数，从而不会在同纹理区域由于匹配代价相同而导致视差计算错误。SO 是逐行考虑的算法，本质就是计算从每一行第一个像素点到当前像素点x 在视差为d x 时候的匹配代价，用sumcost(x,d x )表示，
?
?
?
+==others x d x t sum x )Cdata(d )bestcost(d 1)Cdata(d ),(cos x x x (2-3) 其中
))(min()d (cos x x d Cost t best = (2-4)
而Cost(d x )表示从前一个像素点视差为d x-1到当前像素点在视差为d x 时候的匹配代价。
)(),(cos )(11---+=x x x x d d V d x t sum d Cost (2-5)
当保存到本行最后一列元素x=W 时候，此时sumcost 保存了x=W 处的所有视差对应的最小匹
配代价，选取最小的sumcost ，进行回溯，此时即得到本行最优视差路径。然后同理计算下一行元素。从而能得出所有像素点的视差值，而SO 的最小化能量方程转化为：
max))...,3,2,1,(cos min(min arg d d W t sum E == (2-6)
2.1.2算法步骤：
(1) 初始化第一列元素(x=1):
令sumcost(x ; 1,2,3,…,dmax)=Cdata(d x=1,2,3,…,dmax )；
(2) 从下一列(x=x+1)开始,取不同的视差d=1，2,3…dmax,计算像素x-1从不同的视差
d x-1=1,2,…,dmax 到当前具有视差d 的像素x 所对应的最小代价bestcost ，从而得出该元素的sumcost(x,d x ),并且保存x 各个视差所对应的前一个像素的视差值best_d 。判断若x<=W 则转步骤（2）否则继续；
(3) 此时的sumcost(w;1,2,…d max )保存了从第一列到当前列的最小能量，则此时从
min(sumcost(x;1,2,3,…,d max ))所对应的d 开始回溯,根据之前保存的各个像素对应的best_d 来得到本行的视差集；
(4) 考虑下一行元素，同样采取这样的方法。 2.1.3算法运行详解：
为简单起见设一行仅含有5个像素点，视差的范围为d=1,2,3,4。边的权值表示从像素点x-1的各个视差到像素点x 所对应的视差d 的最小能量代价bestcost(x,d)。如图 3 每个点记录了从x=1到当前像素点在视差d 时候的最佳匹配代价sumcost(x,d x )，例如在x=2,d=2处一共有四条路径(路径1，路径2，路径3，路径4)从中选取bestcost(2)所对应的路径(路径4)。最后在x=5处求出最小的匹配代价即min(sumcost(5,d=1,2,3,4))，此时进行回溯则找到图中的红色路径即为该行的最佳视差即d=(4,2,2,4,1)。
图 3 SO 算法运行图 Figure 3 SO Algorithm diagram
X =
d =1
2
3
4
图3 SO 算法运行图 Figure3 SO Algorithm diagram
比起基于像素点的立体匹配，它能保证在一行是最优的，速度快，而且与下面的动态规划相比，允许相邻匹配点拥有更大的视差变化范围。不足是，首先它仅仅对水平扫描线进行优化寻径，造成扫描线间的视差不连续；其次，它使用固定的视差搜索范围，导致一定的冗余计算。目前的改进方法是添加更多的约束条件，来减少冗余的视差扫描，同时点使扫描线间的视差也有一定的约束作用。
2.2 动态规划优化方法
在实际应用中通常立体视觉匹配算法要具有较高的准确性和实时性。为了提高立体匹配的精度，一般采用全局算法。它使用全局约束来解决匹配问题，通常利是用全局优化算法来最小化能量函数，但全局算法的时间消耗异常的大，而动态规划(Dynamic Programming)是属于半全局算法中的一种优化方法，它避免了NP 问题，而且具有计算效率高、匹配效果较
好的特点，因而这种算法在实际场合中是最常被使用。
动态规划立体匹配算法分为两个阶段：
1）计算左右两幅图像的原始匹配代价，建立视差空间图像；
2）在视差空间图像上运用动态规划算法进行优化，基于动态规划的立体匹配算法的实质就是要在视差空间图像上，考虑各种视差变化情况下，求出一条最优路径，使能量函数E取值最小，从而求取视差。
为进一步限制路径搜索的范围，降低算法的复杂度，文献[4]引入了唯一性约束和顺序性约束，从而限定了从前一阶段到当前阶段的转换只有7 种可能的形式，如图 4 所示。分别用m、l、r 表示前一阶段(pre_state)的匹配点、左遮挡点（即只能在参考图中被看到）、右遮挡点（即只能在匹配图中看到），用M、L、R 表示当前阶段(current_state)的匹配点、左遮挡点、右遮挡点。我们称此动态规划为三状态动态规划。
123456
7
R
m
形
式
图4 7种形式转换图
Figure4 7 forms conversion chart
2.2.1算法原理
对于DP算法的核心部分就是从每一行第一个像素点到当前像素点x在视差为d，状态为current_state时候的最小匹配代价，用sumcost(d,x,current_state)表示。
())(
pre_state)
pre_x,
e_d,
sumcost(pr
min
ate)
current_st
x,
sumcost(d,t
Cost
+
=(2-7）其中sumcost(pre_d,pre_x,pre_state)表示像素点x的前一个位置(此时的视差为pre_d,状态为pre_state,位置为pre_x)最小匹配代价。Cost表示从前一个位置到当前位置的转移代价，转移代价参考图 5 ，则可得计算方法为
?
?
?
?
?
?
?
=
-
+
=
=
=
=
-
7
4
)
(
)
Cdata(d
6
5
CoccR
3
2
CoccL
1
)
Cdata(d
)(
1
x
x
或者
或者
或者
t
d
d
V
t
t
t
t
Cost
x
x
(2-8) CoccL与CoccR为左遮挡和右遮挡的惩罚代价，光滑约束项V(d x,d x-1)的定义与SO算法相同。
图5 代价转换
Figure 5 Cost of transition
直到本行最后一列元素x=W 时候，此时sumcost(d,W,current_state)共保存了dmax 个最小匹配代价即sumcost(d=1,2,…,dmax,W,current_state)，与SO 算法相同，选取最小的匹配代价集min(sumcost(d=1,2,3,…,dmax,W,current_state))，进行回溯，此时即得到本行最优视差路径,然后同理计算下一行元素。
与上面的SO 算法不同的是，DP 在计算匹配代价的时候考虑了遮挡问题,从而添加了遮挡惩罚代价，能较好的处理遮挡问题。对常规能量方程式使用动态规划求的最佳路径可转化为：
))1_,max,,...,3,2,1(cos min(min arg ===state current W d d t sum E (2-9)
2.2.2算法步骤：
(1) 初始化的第一个点x=1的sumcost ，设置其为匹配状态；
(2) 转到x 的下一个位置,讨论从前一个像素点位置pre_x 到当前像位置x 的变换方式t 与从第一个点到当前点的匹配代价sumcost 。方法为：根据前一个像素点位置pre_x ，状态pre_state 与视差pre_d 讨论像素点pre_x 到像素点x 的变换t ，计算出转换代价Cost(t)，从而得到第一个像素点到当前像素点的最小匹配代价sumcost(d,x,current_state);并且保存x 各个视差所对应的pre_x 处的最佳转换方式best_t 。若x (3) 回溯寻找最优的路径,先求出最后一列元素即x=W 时的最小匹配代价（注意默认其为无遮挡匹配像素）sumcost(d,W,current_state=1)根据当前的d,计算出从前一个像素点到当前像素点的转换方式best_t;从而根据转换度，得出前一个位置的视差pre_d 注意，若当前的状态为匹配则视差值设置为d ，否则标志其为空洞，即： ?? ?==others occLable 1ate current_st d dispMap (4) 填充空洞，根据回溯时候的视差dispMap，若当前像素点为遮挡点occLable，则使其视差值为最近一处非遮挡点的视差值。 2.2.3 算法运行详解： 如图所示，假设有六个像素点，视差d=1,2,3,在最末处x=6处寻找最小的 sumcost(d=1,2,3,6,current=1)，然后进行回溯，根据保存的best_t寻找x=5处的视差，以此类推，最后得到一条从x=1到x=6的路径，即得到的视差为d={1,1,1,2,3,2,1,1},而x=3,x=4处为左遮挡区域，x=5处为右遮挡区域其余为匹配点。 d=2 d=0 图6 DP算法运行图 Figure 6 DP Algorithm diagram DP不仅能保证在一行是最优的，速度快，而且能考虑到遮挡区域。但是由于每一条扫描线被单独地处理，缺少了扫描线之间的约束限制，所以该算法和SO算法一样存在条纹瑕疵改进方法常常是利用扫描线间的相关信息来约束动态规划过程，使得处理每一条扫描线时都能充分利用以前扫描线的匹配信息。例如Step hen[5]等引入了控制点修正技术，改善了视差图质量，大大减少了条纹瑕疵.；Gong and Yang[6]提出了一个基于可靠性的二通道的DP 算法，它沿着水平和垂直路径利用动态规划，充分利用了像素间信息；Coxet al[7]提出了利用扫描线间的一致性约束，实现了二维的内聚性。虽然这些改进对DP都起到了一定的优化作用，但在优化的同时常常会引进新的缺点，所以都不是很理想。 2.3置信度优化方法 2.3.1算法原理： 很多计算机视觉问题都具有不适定性，处理这类问题要引入合适的先验约束，把它转化为适定的问题。其中马尔科夫随机场是描述计算机视觉问题的常用方法。2003年Sun[8]等人将置信传播算法(Belief Propagation)用在立体匹配中，取得了异常好的效果，此后基于置信度传播的立体匹配算法成为人们研究的热点。BP算法任然是将视差表示成标号形式,为匹配问题构建能量函数,在适当的约束下,通过邻接及转移关系建立马尔可夫网络,巧妙的使能量与网络中的信任度关联。最后通过求取全局能量函数的最小值来求取视差。 由于基于置信传播算法的立体匹配不是单单一行，所以其能量模型应变为(2-10)： ∑∑N ∈+ =),(),()(j i j i p p d d V d D E （2-10） N 表示相邻像素对的集合，P 表示所有的像素点集合 对式子两边进行指数变换可得 ? ??? ? ??+-=??? ??-∑∑N ∈σσ)),()((exp exp ),(j i j i p p d d V d Cdata E （2-11） 令 ??? ? ??-=??? ??-=??? ??-=σψσφσ),(exp ),(,)(exp )(,exp )(,j i j i j i x p p d d V d d d Cdata d E I Cdata P 则能量方程可变为 )(),()(,) ,(p p p j i j i j i d d d I Cdata P φψ∏∏= （2-12） 从而可以将立体匹配全局能量最小化问题转化为最大积马尔科夫随机场问题，从而利用 置信传播算法求解立体匹配问题的全局近似最优解。 BP 算法的主要思想是消息的迭代传输，假设x s 在x t 的左边，用m st i+1 (x s ,x t )表示第i 次迭代中节点x s 传递给x t 的左消息，记作m st i+1 (x leftmessage ）,传递信息计算参考图 7 ,b s (x s )记为结点x s 的置信度，要不断的更新，更新方式如图 8。其计算方法分别为： i e downmessag i upmessage i ge rightmessa i e prawmessag s t st x e leftmessag i st m m m m x x x m s ****),(max )(1ψ= + （2-13） 即得到x t 点处的左信息矩阵x leftmessage e leftm essag e downm essag upm essage ge rightm essa e prawm essag s s m m m m m x b ****)(= （2-14） 其中m prawmessage ，m rightmessage ，m leftmessage ，m upmessage ，m downmessage 分别表示x s 处，节点的信息， 右信息，左信息，上信息和下信息 最后x s 点的置信度为 )(max arg k s x opt s x b x k = （2-15） 2.3.2 算法步骤 (1) 初始化四个存储信息传递矩阵，初始值均设置为1即Leftmessage,当信息从 左向右传播时候，保存左信息；rightmessage,当信息从右向左传播时候，保存右信息；upmessage,当信息从上向下传播时候，保存上信息；downmessage 当信息从下向上传播时候，保存下信息；prawmessage,源信息矩阵，即为初始匹配代价； (2) 根据公式（2-13）更新每个点的信息矩阵，即右信息矩阵m rightmessage ，左信息矩 阵m leftmessage ，上信息矩阵m upmessage 和下信息矩阵m downmessage 。 (3) 根据公式（2-14）计算节点的最佳置信度x s opt 同时记录下各元素的最大的置信 度（2-15）所对应的视差d ，此时便求得该处的视差值。最后判断若达到迭代次数则停止否则转(3) 2.3.3 算法运行详解： 如图显示了在Markov Network 网络中消息传递的方式，在最大 积算法中，消息传递从x6到x7便为x7的leftmessage ，即 )m *m *m *m *),(max( 66,106,56,2767,6x x m new ψ= 同理求出x7处的rightmessage,upmessage,downmessage,则可以得到x7处的信 任度b 7为 11,73,77,87,677m *m *m *m *m =b 此时根据最小的b 7所对应的视差来得出x 7处的视差值best_d 。 x9 图 9 BP 算法运行图 BP 算法的优点是目标函数的凹凸性不受限制, 计算复杂度高,获得的全局最优路径与 真实路径有一定差距。目前针对BP 的不足改进方法有：Felzenszwalb [9] 等人采用的分层等 技术对SBP 加速，使得全局能量能够较快收敛；Yang [10] 等人利用快速收敛策略也使算法能够 较快的执行；Belief Prog [11] 算法利用极值位置关系进行加速处理，能使运行效率大约提高了30％~60%。 2.4图割优化方法 GC(Graphic Cut)[12] 图割算法是另外一种全局优化算法，即用标号表示视差,建立能量函数,把匹配问题转化为能量函数最小化问题，再通过构造网络,使能量与网络的割的容量相联系，最后利用图的网络流理论给出能量函数的最小化,从而获得图像匹配的视差数据，根据图的构造方式不同，图割算法共有两个即Swap 算法与ansion exp -α算法 2.4.1 Swap 算法原理 Swap 的思想是通过不断的选取两个不同的视差βα,，通过其构造网格来与能量方程想关联，P 为所有元素的集合，而P αβ是视差为βα,的元素集合，网格构成如图 11 所示，图的构成元素有： 顶点集{}αββα P = ,,V 边集 {}? ?????=N ∈P ∈ε ε βα } ,{},{p , q p q p p p t t ， βα,为顶点，P αβ中的元素分别与βα,相连接构成t-link 边，而P αβ中内部元素相 连接构成n-link 边,权值赋值的方式分别为 αβ αβ β αβ αβ α ββααP ∈+=P ∈+=∑∑?∈?∈p f V p f V p q Np q q p f p q Np q q p f D t D t ) ,()() ,()( (t-link) αββαP ∈N ∈=q p q p V e q p ,},{),(} ,{ (n-link) 则割集 ∑∑∑∑∑∑P ∈N ∈P ∈P ?N ∈P ∈P ?N ∈P ∈+ = + + =αβ αβ αβ αβ αβ αβ porq q p c q c p p C p p q p q p c q c p p q p q c q c p p C p p f f f D f f f f f D V V V C },{},{},{) , ()(), (),()( 即 K E C f c -=)( 其中∑ ∑=P N ∈P ?+ = φ αβαβ },{},{),( )(q p q p c q c p p C p p f f f D V K 则将最小割集与能量函数连接了起来，求出最小割集则为最小的能量，同时也能得出视差集。 2.4.2 swap 算法步骤 （1） 用简单的方法比如WTA 方式获得初始视差集labels 也可以默认都为1， （2） 设置标志success=0 （3） 从labels 中任意选出两种视差βα,，将原来的视差为α的像素点和 视差值为β的像素点形成一个标号集f ，并用此标号集按照swap 构造方法构造一个网格，计算出此标号集下f 的能量方程值E ，将能量方程对应到这个网格中，求出此网格的最小割，此时与源source 相连接的像素点视差为α，与源sink 相连接的像素点的视差为β，此时得到一个新的标号集f’，计算在此情况下的能量方程新的值E’ 若E’ （4） 判断若success=1则转步骤（2），否则表示能量已经不能再减小 优化完毕，则停止循环 2.4.3 swap 算法运行详解： 假设已经由简单的匹配算法如WTA 获得初始视差，每个像素点获得相应 的标号与视差值 标号集 L={f1,f2,f3,…,f12} 视差集 P={1,2,3,4} f1 f2 f3 f4f5 f6 f7 f8像素点的标号 像素点的视差值 图 10 带初始视差的像素点 随机选取交换的视差α=3与β=2，从而构成新的标号集L’={f4,f5,f7,f`10,f12} 而视差集即为P’={3,2} f4 source β-sink 最小割集C 图 11 Swap 算法运行图 对应于此例如图所示,求出此时的最小割集C ，即为求的最小的能量E ’ 若此时的E ’ 点的视差值均为α=3，f7,f10与β相连则该两个像素点的视差均为β=2，其中f12的视差得到了修正 2.4.4 ansion exp -α算法原理： ansion exp -α的思想是通过对视差集中的每一个视差α，通过其构造网格 来与能量方程想关联，如图所示，图的构成有 顶点集?? ? ???????=≠N ∈a q p fq fp q p L V },{},{ ，，，αα 边集 {} ?? ??? ?? ? ?? ==N ∈≠N ∈P ∈e t t q p fq fp q p q p fq fp q p p p } ,{},{},{},{p ,, εε ααα ， L 中的元素分别与αα,相连接构成t-link 边，而L 中元素相连接构成n-link 边 权值赋值的方式分别为 t-link αα P ∈∞=f t f αα P ?=f f D t p p f ) ( αα αP ∈=f D t f f ) ( f f f f t q p q p a q p V ≠ N ∈=, },{), ( n-link f f f e q p p a p q p V ≠ N ∈=, },{),(} ,{α f f f e q p q q q p V ≠ N ∈=, },{), (} ,{αα f f f e q p p q p q p V = N ∈=, },{),(} ,{α 则割集 )(), ( )(},{f f f f D c q p c q c p p C p p E V C =+ =∑ ∑N ∈P ∈ 即 )(f c E C = 则将最小割集与能量函数连接了起来，求出最小割集则为最小的能量，同时得出视差集。 2.4.5 ansion exp -α算法步骤 （1）用简单的方法比如WTA 方式获得初始视差集labels 也可以默认都为1， （2） 设置标志success=0 （3）对于P 中每一个视差α，将原来的视差为α的像素点和其他视差值的像素点形成一个标号集f ，并用此标号集构造一个网格，计算出此时的能量方程值E 将能量方程对应到这个网格中，与swap 不同的是以前只是考虑两种视差之间的变换，现在是视差为α的像素点与其他所有α像素点之间的变换，而且添加了辅助结点，求出此网格的最小割，此时与源source 相连接的像素点视差为α，与源sink 相连接的像素点的视差为α，此时得到一个新的标号集f’，计算在此情况下的能量方程新的值E’ 若E’ （4）判断若success=1则转步骤（2），否则表示能量已经不能再减小 优化完毕，则停止循环 2.4.6 ansion exp -α算法运行详解： 仍然假设已经由简单的匹配算法如WTA 获得初始视差，每个像素点获得 相应的标号与视差值 标号集 L={f1,f2,f3,…,f12} 视差集 P={1,2,3,4} 如上图所示 对于视差集中每一个视差α， 图 12 ansion exp -α 算法运行图 对应于此例如图所示,求出此时的最小割集C ，即为求的最小的能量E ’ 若此时的E ’ f4,f11与β相连则该两个像素点的视差保持不变 f12的视差得到了修正 由于GC 是全局优化，计算量相当的大，所以在时间和空间的消耗上都比半全局优化大 的多。针对效率的改进方法很多，例如国内的一种受限α-扩展(α-expansion)操作[13] ,该操作根据灰度连通性和特征点匹配的结果对每次网络构造的顶点进行控制,减少网络中顶点和边的数目,可有效提高计算效率。 三 实验分析 3.1 参数定义与设置： 本文用文献[14] 的方法来评估算法的性能，即分别对各自算法总的错误像素点百分比bad_pixels_all ，无纹理区域 T 错误像素点百分比bad_pixels_textureless ，不连续区域 D 错误像素点百分比bad_pixels_discont 做了统计。 )),(),((N 1 _all bad_pixels ),(d all y x T c y x d y x d δ>-= ∑∈ (3-1) )),(),((N 1 ss _texturele bad_pixels ),(d T y x T c y x d y x d δ>-= ∑∈ (3-2) )),(),((N 1 _discont bad_pixels ),(d D y x T c y x d y x d δ>-= ∑∈ (3-3) d C (x,y)为算法计算所得的视差，d T (x,y)为真实的视差； d δ（eval_bad_thresh ）为容许的视差错误，在本实验取值为1.0； 无纹理区域 T 即为在指定大小的方形区域(宽度为eval_textureless_width )内视差平均值小于给定的阈值(eval_textureless_thresh )； 本实验指定eval_textureless_width =3, eval_textureless_thresh=4 不连续区域 D 即为在像素点的视差与其相邻(eval discont width ）.的视差值大于给定的阈值(eval disp gap)； 本实验指定eval_discont_width=9，eval_disp_gap=2; 此外由于很多算法没有考虑边界问题，所以本文在比较算法的时候除去了边界像素点，边界定义的宽度为eval_ignore_border=18; 本文图片来自https://www.wendangku.net/doc/a616715999.html,/网站的数据集，选用了tsukuba 图片与 均为经过校正的图片，去除了干扰噪声，从而能将注意力放在算法的本身性能。 3.2 首先对tsukuba 图片进行评估 对于SO 算法关键的参数就是对于数据项Cdata 计算时候的截断值Truncation ，与计算光 滑项时候用到的opt_smooth ，对这两个参数分别做实验 左图 右图 102030 4050607080 1012 14 16 18 20 22 Truncation p i x e l p e r c e n t a g e opt Smooth p i x e l p e r c e n t a g e DP 算法 102030 4050607080 8101214161820 2224Truncation p i x e l p e r c e n t a g e 100 200 300 400500600700 800 900 1000 opt Smooth p i x e l p e r c e n t a g e Occ p i x e l p e r c e n t a g e 根据DP 算法的原理可以知道opt_smooth 的值越高，视差图就越平滑，同时也会丢失一些细节信息；opt_smooth 的值越低，视差图就更精细，但是会引入更多的异常值。CoccR/L 的作用是控制视差图中允许的遮挡数量，过高会导致一些正确的遮挡丢失，相反，如果过低，那么视差图中会出现一些多余的遮挡。 BP 算法 BP 算法是通过迭代来进行优化的，由于BP 算法每次迭代都非常耗时，所以希望迭代次数越少越好，实验证明tsukuba 仅仅迭代3~4次已经能达到收敛 iteriter p i x e l p e r c e n t a g e BP 算法的截断函数与前面的不同，采用了 相位匹配及实现方法 实验证明，只有具有特定偏振方向的线偏振光，以某一特定角度入射晶体时，才能获得良好的倍频效果，而以其他角度入射时，则倍频效果很差，甚至完全不出倍频光。根据倍频转换效率的定义 ω ω 2ηP P =， （15） 经理论推导可得 2ω 22 2)2/()2/(sin ηE L d k L k L ???????∝。 （16） η与L??k/2关系曲线见图1。图中可看出，要获得最大的转换效率，就要使L??k/2＝0，L 是倍频晶体的通光长度，不等于0，故应?k ＝0，即 0)n n (4221 21=-λπ= -=?ωω k k k ， （17） 就是使 ωω=2n n ， （18） n ω和n 2ω分别为晶体对基频光和倍频光的折射率。也就是只有当基频光和倍频光的折射率相等时，才能产生好的倍频效果，式（18）是提高倍频效率的必要条件，称作相位匹配条件。 由于v ω＝c/n ω，v 2ω＝c/n 2ω，v ω和v 2ω分别是基频光和倍频光在晶体中的传播速度。满足（18）式，就是要求基频光和倍频光在晶体中的传播速度相等。从这里我们可以清楚地看出，所谓相位匹配条件的物理实质就是使基频光在晶体中沿途各点激发的倍频光传播到出射面时，都具有相同的相位，这样可相互干涉增强，从而达到好的倍频效果。 实现相位匹配条件的方法：由于一般介质存在正常色散效果，即高频光的折射率大于低频光的折射率，如n 2ω―n ω大约为10－2数量级。?k ≠0。但对于各向同性晶体，由于存在双折射，我们则可利用不同偏振光间的折射率关系，寻找到相位匹配条件，实现?k ＝0。此方法常用于负单轴晶体，下面以负单轴晶体为例说明。图2中画出了晶体中基频光和倍频光的两种不同偏振态折射率面间的关系。图中实线球面为基频光折射率面，虚线球面为倍频光折射率面，球面为o 光折射率面，椭球面为e 光折射率面，z 轴为光轴。 图1 倍频效率与L ??k/2的关系 相对光强 -2π 2π π -π L ??k/2 模式匹配的KMP算法详解 模式匹配的KMP算法详解 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KMP算法。大概学过信息学的都知道，是个比较难理解的算法，今天特把它搞个彻彻底底明明白白。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？回溯，没错，注意到(1)句，为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 为什么会发生这样的情况？这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为abcdef这样的，大没有回溯的必要。 关于快速高效的模式匹配算法的剖析与改进 摘要：模式匹配算法是现代化网络入侵检测中的关键环节，本文主要介绍了几种常用的模式匹配算法，并在此基础上，提出一种更快捷、更高效的改进方法，以提高模式匹配的效率与质量，确保网络安全。 关键词：模式匹配入侵检测改进 随着我国计算机与网络技术的飞速发展，网络应用已涉及到人们生产、生活的各个领域，其重要性日益凸显。随之而来的网络攻击问题也备受关注，给网络安全性带来挑战。传统的网络防御模式，主要采取身份认证、防火墙、数据加密等技术，但是与当前网络发展不适应。在此背景下，入侵检测技术营运而生，并建立在模式匹配基础上，确保检测的快捷性、准确性，应用越来越广泛。 1、模式匹配原理概述 模式匹配是入侵检测领域的重要概念，源自入侵信号的层次性。结合网络入侵检测的底层审计事件，从中提取更高层次的内容。通过高层事件形成的入侵信号，遵循一定的结构关系，将入侵信号的抽象层次进行具体划分。入侵领域大师kumar将这种入侵信号划分为四大层次，并将每一个层次与匹配模式相对应。以下将分别对四大层次进行分析： (1)存在。只要存在审计事项，就可以证明入侵行为的发生，并深层次挖掘入侵企图。存在主要对应的匹配模式就是“存在模式”。可以说，存在模式就是在固定的时间内，检查系统中的特定状态， 同时判断系统状态。 (2)序列。一些入侵的发生，是遵循一定的顺序，而组成的各种行为。具体表现在一组事件的秩序上。序列对应的是“序列模式”，在应用序列模式检测入侵时，主要关注间隔的时间与持续的时间。 (3)规则。规则表示的是一种可以扩展的表达方式，主要通过and 逻辑表达来连接一系列的描述事件规则。一般适用于这种模式的攻击信号由相关活动组成，这些活动之间往往不存在事件的顺序关系。 (4)其他。其他模式是不包含前面几种方法的攻击，在具体应用过程中，难以与其他入侵信号进行模式匹配，大多为部分实现方式。 2、几种常用的模式匹配算法 2.1 ac算法 ac算法（aho-corasick）是一种可以同时搜索若干个模式的匹配算法，最早时期在图书馆书目查询系统中应用，效果良好。通过使用ac算法，实现了利用有限状态自动机结构对所有字符串的接收过程。自动机具有结构性特征，且每一个前缀都利用唯一状态显示，甚至可同时应用于多个模式的前缀中。如果文本中的某一个字符不属于模式中预期的下一个字符范围内，或者可能出现错误链接的指向状态等，那么最长模式的前缀同时也可作为当前状态相对应的后缀。ac算法的复杂性在于o（n），预处理阶段的复杂性则在于o（m）。在采取ac算法的有限状态自动机中，应该在每一个字符的模式串中分别建立节点，提高该算法的使用效率与质量。目前，应用有限 在前面的图文中，我们讲了“串”这种数据结构，其中有求“子串在主串中的位置”（字符串的模式匹配）这样的算法。解决这类问题，通常我们的方法是枚举从A串（主串）的什么位置起开始与B串（子串）匹配，然后验证是否匹配。假设A串长度为n，B串长度为m，那么这种方法的复杂度是O(m*n)的。虽然很多时候复杂度达不到m*n（验证时只看头一两个字母就发现不匹配了），但是我们有许多“最坏情况”，比如： A=“aaaaaaaaaaaaaaaaaaaaaaaaab”，B=“aaaaaaaab”。 大家可以忍受朴素模式匹配算法（前缀暴力匹配算法）的低效吗？也许可以，也许无所谓。 有三位前辈D.E.Knuth、J.H.Morris、V.R.Pratt发表一个模式匹配算法，最坏情况下是O(m+n)，可以大大避免重复遍历的情况，我们把它称之为克努特-莫里斯-普拉特算法，简称KMP算法。 假如，A=“abababaababacb”，B=“ababacb”，我们来看看KMP是怎样工作的。我们用两个指针i和j分别表示，。也就是说，i是不断增加的，随着i 的增加j相应地变化，且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前j个字符（j当然越大越好），现在需要检验A[i+1]和B[j+1]的关系。 例子： S=“abcdefgab” T=“abcdex” 对于要匹配的子串T来说，“abcdex”首字符“a”与后面的串“bcdex”中任意一个字符都不相等。也就是说，既然“a”不与自己后面的子串中任何一字符相等，那么对于主串S来说，前5位字符分别相等，意味着子串T的首字符“a”不可能与S串的第2到第5位的字符相等。朴素算法步骤2,3,4,5的判断都是多余，下次的起始位置就是第6个字符。 例子： S=“abcabcabc” T=“abcabx” 传播优秀Word 版文档 ，希望对您有帮助，可双击去除！ 相位匹配及实现方法 实验证明，只有具有特定偏振方向的线偏振光，以某一特定角度入射晶体时，才能获得良好的倍频效果，而以其他角度入射时，则倍频效果很差，甚至完全不出倍频光。根据倍频转换效率的定义 ω ω 2ηP P =， （15） 经理论推导可得 2ω 22 2)2/()2/(sin ηE L d k L k L ???????∝。 （16） η与L??k/2关系曲线见图1。图中可看出，要获得最大的转换效率，就要使L??k/2＝0，L 是倍频晶体的通光长度，不等于0，故应?k ＝0，即 0)n n (4221 21=-λπ= -=?ωω k k k ， （17） 就是使 ωω=2n n ， （18） n ω和n 2ω分别为晶体对基频光和倍频光的折射率。也就是只有当基频光和倍频光的折射率相等时，才能产生好的倍频效果，式（18）是提高倍频效率的必要条件，称作相位匹配条件。 由于v ω＝c/n ω，v 2ω＝c/n 2ω，v ω和v 2ω分别是基频光和倍频光在晶体中的传播速度。满足（18）式，就是要求基频光和倍频光在晶体中的传播速度相等。从这里我们可以清楚地看出，所谓相位匹配条件的物理实质就是使基频光在晶体中沿途各点激发的倍频光传播到出射面时，都具有相同的相位，这样可相互干涉增强，从而达到好的倍频效果。 实现相位匹配条件的方法：由于一般介质存在正常色散效果，即高频光的折射率大于低频光的折射率，如n 2ω―n ω大约为10－2数量级。?k ≠0。但对于各向同性晶体，由于存在双折射，我们则可利用不同偏振光间的折射率关系，寻找到相位匹配条件，实现?k ＝0。此方法常用于负单轴晶体，下面以负单轴晶体为例说明。图2中画出了晶体中基频光和倍频光的两种不同偏振态折射率面间的关系。图中实线球面为基频光折射率面，虚线球面为倍频光折射率面，球面为o 光折射率面，椭球面为e 光折射率面，z 轴为光轴。 图1 倍频效率与L ??k/2的关系 相对光强 -2π 2π π -π L ??k/2 实验四：KMP算法实验报告 一、问题描述 模式匹配两个串。 二、设计思想 这种由D.E.Knuth,J.H.Morris和V.R.Pratt同时发现的改进的模式匹配算法简称为KM P算法。 注意到这是一个改进的算法，所以有必要把原来的模式匹配算法拿出来，其实理解的关键就在这里，一般的匹配算法： int Index(String S,String T,int pos)//参考《数据结构》中的程序 { i=pos;j=1;//这里的串的第1个元素下标是1 while(i<=S.Length && j<=T.Length) { if(S[i]==T[j]){++i;++j;} else{i=i-j+2;j=1;}//**************(1) } if(j>T.Length) return i-T.Length;//匹配成功 else return 0; } 匹配的过程非常清晰，关键是当‘失配’的时候程序是如何处理的？为什么要回溯，看下面的例子： S:aaaaabababcaaa T:ababc aaaaabababcaaa ababc.(.表示前一个已经失配) 回溯的结果就是 aaaaabababcaaa a.(babc) 如果不回溯就是 aaaaabababcaaa aba.bc 这样就漏了一个可能匹配成功的情况 aaaaabababcaaa ababc 这是由T串本身的性质决定的，是因为T串本身有前后'部分匹配'的性质。如果T为a bcdef这样的，大没有回溯的必要。 改进的地方也就是这里，我们从T串本身出发，事先就找准了T自身前后部分匹配的位置，那就可以改进算法。 如果不用回溯，那T串下一个位置从哪里开始呢？ 还是上面那个例子，T为ababc，如果c失配，那就可以往前移到aba最后一个a的位置，像这样： 实验三串的模式匹配 一、实验目的 1．利用顺序结构存储串，并实现串的匹配算法。 2．掌握简单模式匹配思想，熟悉KMP算法。 二、实验要求 1．认真理解简单模式匹配思想，高效实现简单模式匹配； 2．结合参考程序调试KMP算法，努力算法思想； 3．保存程序的运行结果，并结合程序进行分析。 三、实验内容 1、通过键盘初始化目标串和模式串，通过简单模式匹配算法实现串的模式匹配，匹配成功后要求输出模式串在目标串中的位置； 2、参考程序给出了两种不同形式的next数组的计算方法，请完善程序从键盘初始化一目标串并设计匹配算法完整调试KMP算法，并与简单模式匹配算法进行比较。 参考程序: #include "stdio.h" void GetNext1(char *t,int next[])/*求模式t的next值并寸入next数组中*/ { int i=1,j=0; next[1]=0; while(i<=9)//t[0] { if(j==0||t[i]==t[j]) {++i; ++j; next[i]=j; } else j=next[j]; } } void GetNext2(char *t , int next[])/* 求模式t 的next值并放入数组next中 */ { int i=1, j = 0; next[1]= 0; /* 初始化 */ while (i<=9) /* 计算next[i+1] t[0]*/ { while (j>=1 && t[i] != t[j] ) j = next[j]; i++; j++; if(t[i]==t[j]) next[i] = next[j]; else next[i] = j; } } void main() { char *p="abcaababc"; int i,str[10]; GetNext1(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); GetNext2(p,str); printf("\n"); for(i=1;i<10;i++) printf("%d",str[i]); printf("\n\n"); } 二次谐波的应用 二次谐波成像是近年发展起来的一种三维光学成像技术，具有非线性光学成像所特有的高空间分辨率和高成像深度，可避免双光子荧光成像中的荧光漂白效应。 此外二次谐波信号对组织的结构对称性变化高度敏感，因此二次谐波成像对于某些疾病的早期诊断或术后治疗监测具有很好的生物医学应用前景. 二次谐波英文名称：second harmonic component 定义：将非正弦周期信号按傅里叶级数展开，频率为原信号频率两倍的正弦分量。 SHG的一个必要条件是需要没要反演对称的介质其次是必须满足相位匹配，传播中的倍频光波和不断昌盛的倍频极化波保持了相位的一致性. 谐波产生的根本原因是由于非线性负载所致。当电流流经负载时，与所加的电压不呈线性关系，就形成非正弦电流，从而产生谐波。 ＳＨＧ实验装置ＳＨＧ实验装置按二次谐波信号收集方式可分为前向和后向，图２为前向和后向二次谐波产生的实验装置示意图．以图２（ａ）为例：由激光器产生的角频率为的入射基频光，经过物镜聚焦到样品上，产生频率为２的二次谐波，由另一个高数值孔径的物镜收集，滤光片（一般为窄带滤光片）滤掉激发光和可能产生的荧光和其他背景光，再用探测器件（如ＰＭＴ）和计算机系统进行信号的采集、存储、分析和显示．要实现二次谐波微成像需要对以下因素进行最优化考虑：超短脉冲激光、高数值孑Ｌ径的显微物镜、高灵敏度的非解扫面探测器、准相位匹配和具有高二阶非线性的样品Ｊ．激光器：掺Ｔｉ蓝宝石飞秒激光器因具有高重复频率（８０ＭＨｚ）和高峰值功率，单脉冲能量低且町在整个近红外区（７００～１０００ｎｍ）内连续调谐，所以是二次谐波显微成像的理想光源．激光的重复频率对ＳＨＧ也有影响，如果提高激发光的重复频率，激发光的平均功率可相应提高，二次谐波信号也得到增强．物镜：一般情况下，二次谐波主要非轴向发射，即信号收集时必须有一个足够大的数值孑Ｌ径来有效接收整个二次谐波信号．滤光片：为保证所收集的信号为二次谐波信号，必须使用滤光片．一般采用一长波滤光片和窄带滤光片（带宽１０ｎｍ）组合以过滤任何干扰信号．信号收集系统：为尽晕减少二次谐波信号在系统中的损失，提高系统的探测灵敏度，最好采用非解扫（ｎｏｎ．ｄｅｓｃａｎｎｅｄ）的信号．信号收集系统中的主要部件是ＰＭＴ探测器．首先，为收集整个二次谐波信号，需要探测器的接收面足够宽．其次，对于由可调谐Ｔｉ：蓝宝石飞秒激光器，要接收的二次谐波信号处于３５０～５００ｎｍ波段，故可采用双碱阴极光电倍增管．由于激发光波长离探测器的响应区很远，故可有效探Ｎ－－次谐波信号．除了使用不同的滤光片外，二次谐波显微成像和双光子激发荧光显微成像在系统结构上是完全兼容的．已有人成功地将激光扫描共聚焦显微镜改造成双光子系统９，同样，也可以方便的用改造后的系统进行两者的复合成像 二次谐波显微成像技术的发展及其在生物医学中的应用. 细胞膜电压的测量对理解细胞信号传递过程有重要作用. 使用合适的膜染剂进行标记, 通过对染剂分子的二次谐波显微成像, 信号强度变化便能反映膜电压的大小. 近年来, 二次谐波显微成像的一个主要领域, 就是发展具有高时空分辨率及高灵敏度的活细胞中横跨膜电压的光学测量方法. ＳＨＧ成像用于膜电压测量细胞膜电压的测量对理解细胞信号传递过程有重要作用．使用合适的膜染剂进行标记，通过对染剂分子的二次谐波显微成像，信号强度变化便能反映膜电压的大小．近年来，二次谐波显微成像的一个主要领域，就是发展具有高时空分辨率及高灵敏度的活细胞中横跨膜电压的光学测量方法．１９９３年，ＯＢｏｕｅｖｉｔｃｈ等人¨证明，所加电场可强烈地调制ＳＨＧ强度．１９９９年，ＰＪＣａｍｐａｇｎｏ！ａ等人则证明了ＳＨＧ信号随膜电压变化．实验结果表明，激发波长为 竭诚为您提供优质文档/双击可除串的模式匹配算法实验报告 篇一：串的模式匹配算法 串的匹配算法——bruteForce(bF)算法 匹配模式的定义 设有主串s和子串T，子串T的定位就是要在主串s中找到一个与子串T相等的子串。通常把主串s称为目标串，把子串T称为模式串，因此定位也称作模式匹配。模式匹配成功是指在目标串s中找到一个模式串T；不成功则指目标串s中不存在模式串T。bF算法 brute-Force算法简称为bF算法，其基本思路是：从目标串s的第一个字符开始和模式串T中的第一个字符比较，若相等，则继续逐个比较后续的字符；否则从目标串s的第二个字符开始重新与模式串T的第一个字符进行比较。以此类推，若从模式串T的第i个字符开始，每个字符依次和目标串s中的对应字符相等，则匹配成功，该算法返回i；否则，匹配失败，算法返回0。 实现代码如下： /*返回子串T在主串s中第pos个字符之后的位置。若不存在，则函数返回值为0./*T非空。 intindex(strings,stringT,intpos) { inti=pos;//用于主串s中当前位置下标，若pos不为1则从pos位置开始匹配intj=1;//j用于子串T中当前位置下标值while(i j=1； } if(j>T[0]) returni-T[0]; else return0; } } bF算法的时间复杂度 若n为主串长度，m为子串长度则 最好的情况是：一配就中，只比较了m次。 最坏的情况是：主串前面n-m个位置都部分匹配到子串的最后一位，即这n-m位比较了m次，最后m位也各比较了一次，还要加上m,所以总次数为：(n-m)*m+m=(n-m+1)*m从最好到最坏情况统计总的比较次数，然后取平均，得到一般情况是o(n+m). 立体匹配算法的可行性分析报告 1 立体匹配算法的分类 根据匹配算法使用的约束信息的不同，立体匹配算法总体上分为局域算法和全局算法两种。局域算法利用的是对应点本身以及邻近的局部区域的约束信息，局域算法的优点是效率高，但是它对局部的一些由于遮挡和纹理单一等造成的模糊比较敏感，易造成误匹配。全局算法利用了图像的全局约束信息，对局部图像的模糊不敏感，但是它的计算代价很高。根据匹配基元的不同，局域算法分为区域匹配、特征匹配和相位匹配3种。区域匹配直接利用图像的灰度信息，主要用于表面光滑以及具有明显纹理特征的图像，使用区域匹配可以直接获得稠密的深度图，但是对于缺乏纹理和深度不连续的情况，适应性较差，且这种方法的计算量很大，匹配精度较差。 特征匹配基于图像的几何特征，如边缘、轮廓、拐点、线段等对图像进行匹配，由于几何特征的稀疏性和不连续性，因此特征匹配只能得到稀疏的深度图，需要通过内插方法才能得到稠密的深度图，特征匹配以几何特征为基元，不易受光线的影响，因此鲁棒性较好，而且计算量小，速度快。相位匹配是在假设两幅图像中对应点的局部相位相等的条件下，对带通滤波信号的相位信息进行处理而得到视差图。相位匹配依据的原理为傅立叶平移原理，即信号在空间域上的平移产生频率域上成比例的相位平移，由于相位本身反映的是信号的结构信息，因此相位匹配对图像的高频噪音有很好的抑制作用，同时对几何畸变和辐射畸变有很好的抑制作用，能获得亚像素级的致密视差。 全局匹配算法一般有动态规划的算法和图切割的算法，最常用的全局匹配算法是动态规划算法，动态规划的思想就是把求解整个图像深度值的过程分解为一些子过程，从而减少了 Brute Force(BF或蛮力搜索) 算法： 这是世界上最简单的算法了。 首先将匹配串和模式串左对齐，然后从左向右一个一个进行比较，如果不成功则模式串向右移动一个单位。 速度最慢。 那么，怎么改进呢？ 我们注意到Brute Force 算法是每次移动一个单位，一个一个单位移动显然太慢，是不是可以找到一些办法，让每次能够让模式串多移动一些位置呢？ 当然是可以的。 我们也注意到，Brute Force 是很不intelligent 的，每次匹配不成功的时候，前面匹配成功的信息都被当作废物丢弃了，当然，就如现在的变废为宝一样，我们也同样可以将前面匹配成功的信息利用起来，极大地减少计算机的处理时间，节省成本。^_^ 注意，蛮力搜索算法虽然速度慢，但其很通用，文章最后会有一些更多的关于蛮力搜索的信息。 KMP算法 首先介绍的就是KMP 算法。 这个算法实在是太有名了，大学上的算法课程除了最笨的Brute Force 算法，然后就介绍了KMP 算法。也难怪，呵呵。谁让Knuth D.E. 这么world famous 呢，不仅拿了图灵奖，而且还写出了计算机界的Bible 东方企业文化·百家论坛 2011年9月 163 高效的多模式匹配算法 马 力 （重庆青年职业技术学院，重庆，400712） 摘 要：本文提出一种新的多模式匹配算法，以提高匹配检测的执行速度和效率。该算法采用了基于集合的多模式匹配思想，重新构造了HASH 函数以便在处理大规模模式集时执行时间能比传统的匹配算法的执行时间要少。经过实验证明，运用该算法不仅具有时间复杂度较低的优点，且与传统算法相比具有更为优越的性能，同时在实际工作状态下的检测能力也更强大。 关键词：多模式匹配 HASH 函数 中图分类号：TP393 文献标识码：A 文章编号：1672—7355（2011）09—0163—01 一、算法描述 通常在自然文本中，经常会发生所谓的坏字符移动。此时会极大提高Boyer-Moore 算法的检测效率。但是当文本与多个模式进行匹配时，文本中的多数字符都可能与某些模式的最后一个字符相匹配（即匹配冲突），这时发生坏字符移动的可能性就非常小了。本文提出的算法解决了如何在上述情况下继续保持Boyer-Moore 算法的实质与效率的问题，采用散列（Hash ）技术和高效过滤等方法，减小了匹配冲突对算法执行效率的影响。算法描述如下： 首先，算法需要计算出模式的最小长度，设其值为m ，为简化算法描述，假定所有模式均具有相同的长度，同时保证最小长度合理以免影响匹配效率。 假设P 为模式的集合，P={P 1P 2……P K }，K=|P|，P 中所有模式的长度均为m 。T 为网络数据包，T=t 1t 2……t n （n ≧m ）。 选取Q 为足够大空间的常数，定义长度为m 的支字符串R=r 1r 2……r m ，则构造出R 的Hash 函数：∑=?=m i i m i S r Q R Hash 1mod )(，其中S 为上文所提的模式的P 集合。 二、算法流程设计 1. 预处理阶段 首先需要对模式进行排序，形成有序模式链表；然后主要完成三张表（SHIFT 表、HASH 表和PREFIX 表）的创建。SHIFT 表主要用于确定扫描文本时可移动的字符数。根据SHIFT 表中的取值分为两种处理情况：SHIFT[i ]≠0：直接根据SHIFT[i ]中的取值，确定移动的字符数。SHIFT[i ]=0：即前面提到的匹配冲突。此时需要根据HASH 表和PREFIX 表确定匹配的候选模式并最终核实该模式。 （1）SHIFT 表的创建在此处起到与Boyer-Moore 算法中相同的移动指示作用，只不过移动字符的数目基于长度为B 的字符块。假设SHIFT 表中包含了每个大小为B 的字符串的入口，那么它的大小为|∑|B 。为了减少表存储空间，采用了散列函数，将每个长度为B 的字符串映像为一个索引SHIFT 表的整数。设X=x 1x 2……x b 为文本中的b 个字符串，并假设X 已经被映像为SHIFT 表中的一个入口，则过程SHIFT Table Set Value （）有以下两种情况： X 不属于substring （P ） ：SHIFT[i]=m-B+I ； X 属于substring （P ） ：SHIFT[i]=m-q ； （q 为P i 中X 发生匹配的最右端位置）。 SHIFT 表中的所有初始值均为m-B+1，考虑每个模式 P=P 1P 2……P K ，将每个大小为i j B j B j P p p p B )(21"+?+?的子 串映像到SHIFT 表中。 通常情况下，SHIFT 表项的取值总是大于0，因此能够成功地跳过文本块并继续扫描文本。但是当模式数量增多时，情况就完全不同了。当模式数量增多时，SHIFT 表项取值为0的概率也呈线性递增趋势，即发生匹配冲突的可能性越来越大。本文设计的该算法的核心思想就是采用散列技术来最小化需要处理模式的数目，避免与模式链表中的每个模式逐一进行匹配，同时结合PREFIX 表的过滤作用，加速搜索过程。 （2）HASH 表的创建创建HASH 表，并使用前面计算出的用于索引SHIFT 表的B 个字符串映像整数作为该表的索引。设HASH 表的第i 个入口为HASH[i]，它包含了一个指向最后B 个字符散列值为i 的模式链表的指针。链表PAT_POINT 用于存储指向模式的指针，每个模式按其最后B 个字符的散列值大小排序。设h 为文本当前后缀的散列值，并假设SHIFT[i ]=0，此时HASH[h]的取值指针p 指向散列值为h 的模式链表首部。为查找链表尾，指针不断递增直至它等于HASH[h+1]。如果SHIFT[i ]≠0，则有HASH[h]= HASH[h+1]，因为不存在后缀散列值为h 的模式。 （3）PREFIX 表的创建多模式中肯定会出现相同后缀的情况，导致HASH 表冲突，即所有具有相同后缀的模式将映像到HASH 表中的同一入口。为了加快在相同后缀中查找确切匹配模式的速度，算法还引入了用于区分这些模式的一个称为PREFIX 的表。除了将所有模式的后B 个字符做一映像之外，还须将所有模式的前B 个字符映像到PREFIX 表中。 如果发现SHIFT 值为0，并且要在HASH 表中确定是否存在匹配，那么就在PREFIX 表中检查该值。对每个后缀而言，HASH 表不仅包含具有所有此后缀的模式，而且还包含了他们相应的前缀。可以通过左移m-B 个位置计算出文本中的相应前缀，并用它来过滤那些后缀相同但是前缀不同的模式。 2. 扫描阶段 扫描阶段的流程如下：（1）计算tm-B+1到tm 的基于文本当前B 个字符的散列值h ；（2）检查SHIFT[h]的取值，如大于0，移动文本返回（1），否则转至（3）；（3）从当前位置向左m 个字符处开始计算文本中的前缀散列值，称为文本前缀；（4）检查每个p ，SHIFT[h]≦p ＜HASH[h+1]，是否有PREFIX[P]=text-prefix 。如果相等，那么就直接检查与文本相对应的实际模式（由PAT_POINT[p]给出）。 参考文献： [1] Crosbie ， Gene Spafford. Defending a Computer System using Autonomous Agent[R].COAST Technical Report No.95-022， March 1994. [2] Aho A ， Corasick M. Efficient String Matching an Aid to Bibliographic Search [J]. Communication of the ACM ， 1975， 18（6） ： 333-340. 相位匹配及实现方法 Document serial number【UU89WT-UU98YT-UU8CB-UUUT-UUT108】 相位匹配及实现方法 实验证明，只有具有特定偏振方向的线偏振光，以某一特定角度入射晶体时，才能获得良好的倍频效果，而以其他角度入射时，则倍频效果很差，甚至完全不出倍频光。根据倍频转换效率的定义 ω ω 2ηP P =， （15） 经理论推导可得 2ω 22 2)2/()2/(sin ηE L d k L k L ???????∝。 （16） η与L?k/2关系曲线见图1。图中可看出，要获得最大的转换效率，就要使L?k/2＝0，L 是倍频晶体的通光长度，不等于0，故应k ＝0，即 0)n n (4221 21=-λπ= -=?ωω k k k ， （17） 就是使 ωω=2n n ， （18） n ω和n 2ω分别为晶体对基频光和倍频光的折射率。也就是只有当基频光和倍频光的折射率相等时，才能产生好的倍频效果，式（18）是提高倍频效率的必要条件，称作相位匹配条件。 由于v ω＝c/n ω，v 2ω＝c/n 2ω，v ω和v 2ω分别是基频光和倍频光在晶体中的传播速度。满足（18）式，就是要求基频光和倍频光在晶体中的传播速度相等。从这里我们可以清楚地看出，所谓相位匹配条件的物理实质就是使基频光在晶体中沿途各点激发的倍频光传播到出射面时，都具有相同的相位，这样可相互干涉增强，从而达到好的倍频效果。 实现相位匹配条件的方法：由于一般介质存在正常色散效果，即高频光的折射率大于低频光的折射率，如n 2ω―n ω大约为10－2数量级。k ≠0。但对于各向同性晶体，由于存在双折射，我们则可利用不同偏振光间的折射率关系，寻找到相位匹配条件，实现k ＝0。此方法常用于负单轴晶体，下面以负单轴晶体为例说明。图2中画出了晶体中基频光和倍频光的两种不同偏振态折射率面间的关系。图中实线球面为基频光折射率 图1 倍频效率与L k/2的 相对光强 -22π π -π L k/2 //算法功能：串的朴素模式匹配是最简单的一种模式匹配算法，又称为 Brute Force 算法，简称为BF算法 #include int main() { SString S, T; int m; char strs1[MAXL]; //建立主串S char strs2[MAXL]; //建立模式串T printf("请输入主串和子串:\n"); printf("主串S: "); scanf("%s", strs1); printf("子串T: "); scanf("%s", strs2); StrAssign(S, strs1); StrAssign(T, strs2); m = Index(S, T, 1); if(m) printf("主串 S = {%s}\n子串 T = {%s}\n在第 %d 个位置开始匹配！\n", strs1, strs2, m); else printf("主串 S = {%s}\n子串 T = {%s}\n匹配不成功！\n", strs1, strs2); return 0; } 立体匹配十大概念综述 一、概念 立体匹配算法主要是通过建立一个能量代价函数，通过此能量代价函数最小化来估计像素点视差值。立体匹配算法的实质就是一个最优化求解问题，通过建立合理的能量函数，增加一些约束，采用最优化理论的方法进行方程求解，这也是所有的病态问题求解方法。 二、主要立体匹配算法分类 1）根据采用图像表示的基元不同，立体匹配算法分为： A、区域立体匹配算法（可获取稠密视差图。缺点：受图像的仿射畸变和辐射畸变影响较大；像素点约束窗口的大小与形状选择比较困难，选择过大，在深度不连续处，视差图中会出现过度平滑现象；选择过小，对像素点的约束比较少，图像信息没有得到充分利用，容易产生误匹配。） B、基于特征的立体匹配算法（可获得稀疏的视差图，经差值估计可获得稠密视差图。可提取点、线、面等局部特征，也可提取多边形和图像结构等全局特征。缺点：特征提取易受遮挡、光线、重复纹理等影响较大；差值估计计算量大） C、基于相位立体匹配算法（假定在图像对应点中，其频率范围内，其局部相位是相等的，在频率范围内进行视差估计） 2）依据采用最优化理论方法的不同，立体匹配算法可以分为： A、局部的立体匹配算法 B、全局的立体匹配算法 三、匹配基元（match primitive） 目前匹配算法中所采用的匹配基元可以分成两大类： 1）在所有图像像素点上抽取量测描述子 A、像素灰度值（最简单、直接，但必须在同一光照条件下获得） B、局部区域灰度函数（主要是利用求得在各种大小不同窗口中灰度分布的导数信息，描述像素点周围的结构矢量。） C、卷积图像符号（利用各种大小算子与图象进行卷积，用灰度梯度局部极大值或极小值作为特征信息，描述整个图像） 2）图像特征 A、过零点 B、边缘（由于边缘是图像特征位置的标志，对灰度值的变化不敏感，边缘是图像匹配的重要特征和描述子） C、角点（虽然其没有明确的数学定义，但大家普遍认为角点，即二维图像亮度变化剧烈的点或边缘曲线上曲率极值点） 四、区域匹配算法 基本原理是给定在一幅图像上的某一点，选取该像素点邻域内的一个子窗口，在另一幅图像中的一个区域内，根据某种相似性判断依据，寻找与子窗口图像最为相似的子图，而其匹配的子图中对应的像素点就为该像素的匹配点。 一般单纯的区域匹配都遇到如下限制： 1）针对弱纹理或存在重复纹理的区域，匹配结果不好 2）该算法不适应于深度变化剧烈的场景 3）对光照、对比度和噪声比较敏感 第29卷第4期吉林大学学报（信息科学版）Vol．29No．4 2011年7月Journal of Jilin University（Information Science Edition）July2011 文章编号：1671-5896（2011）04-0383-05 基于WM算法改进的多模式匹配算法 董迎亮a，玄雪花a，王德民b （吉林大学a．计算机科学与技术学院；b．网络中心，长春130012） 摘要：为提高入侵检测系统整体的性能和效率，在研究经典的WM（Wu-Manber）多模式匹配算法的基础上，提出一种改进的WM多模式匹配算法。该算法使用后缀表方法，减少了匹配过程中模式字符串与文本的比较 次数。实验结果表明，该算法有效提高了入侵检测系统匹配的速度和效率。 关键词：入侵检测；多模式匹配；Wu-Manber算法 中图分类号：TP393.08文献标识码：A Improved Multiple Patterns Matching Algorithm Based on WM Algorithm DONG Ying-liang a，XUAN Xue-hua a，WANG De-min b （a．College of Computer Science and Technology；b．Network Center，Jilin University，Changchun130012，China） Abstract：To improve the efficiency of intrusion detection system，we analyzed WM（Wu-Manber）multiple patterns matching algorithms，and then presented an improved patterns matching algorithm．This algorithm uses trail table to decrease the comparison times in matching process．The experiment result shows that it improves the intrusion detection system matching efficiency． Key words：intrusion detection；multiple patterns matching；Wu-Manber algorithm 0引言 随着计算机网络技术的飞速发展，网络安全也受到人们越来越多的关注。为了更全面地保护网络环境，仅靠传统的防火墙技术已经不能完全满足网络安全的需求。入侵检测技术被公认为是防火墙之后的第二道安全闸门，可以弥补防火墙技术明显的不足，为网络安全提供实时的入侵检测以及相应的防护手段。 在高速网络环境中，如果模式匹配算法不能满足处理大量实时网络数据包的要求，入侵检测系统必然会丢弃部分网络数据包，而这些被丢弃的数据包中就可能包含入侵信息。由于模式匹配算法的性能直接影响入侵检测系统的检测效率，笔者将以基于误用检测技术的模式匹配算法为研究目标，提出一种改进后的WM多模式匹配算法。该算法与原WM（Wu-Manber）算法相比具有运算效率高的优点。 1模式匹配算法 模式匹配［1-7］是指在给定长度为n的文本串T=T［1］T［2］…T［n］中查找长度为m的模式串P= P［1］P［2］…P［m］的首次出现或多次出现的过程，其中T［i］（1≤i≤n），P［j］（1≤j≤m）∈∑（字符集）。若在T中能找到P的出现，则称匹配成功；否则称匹配失败。一次在文本中只能对一个模式串进行匹配的算法，称为单模式匹配算法，可同时对多个模式串进行匹配的算法称多模式匹配算法。 收稿日期：2011-04-13 作者简介：董迎亮（1982—），男，长春人，吉林大学硕士研究生，主要从事计算机网络安全研究，（Tel）86-136********（E-mail）liangdyl @https://www.wendangku.net/doc/a616715999.html,；王德民（1958—），男，长春人，吉林大学教授，硕士生导师，主要从事智能网络与数据库、网络安全研究 （Tel）86-138********（E-mail）wdm@https://www.wendangku.net/doc/a616715999.html,。 二次谐 波的应用 二次谐波成像是近年发展起来的一种三维光学成像技术，具有非线性光学成像所特有的高空间分辨率和高成像深度，可避免双光子荧光成像中的荧光漂白效应。 此外二次谐波信号对组织的结构对称性变化高度敏感，因此二次谐波成像对于某些疾病的早期诊断或术后治疗监测具有很好的生物医学应用前景. 二次谐波英文名称：second harmonic component 定义：将非正弦周期信号按傅里叶级数展开，频率为原信号频率两倍的正弦分量。SHG的一个必要条件是需要没要反演对称的介质其次是必须满足相位匹配，传播中的倍频光波和不断昌盛的倍频极化波保持了相位的一致性. 谐波产生的根本原因是由于非线性负载所致。当电流流经负载时，与所加的电压不呈线性关系，就形成非正弦电流，从而产生谐波。 ＳＨＧ实验装置ＳＨＧ实验装置按二次谐波信号收集方式可分为前向和后向，图２为前向和后向二次谐波产生的实验装置示意图．以图２（ａ）为例：由激光器产生的角频率为的入射基频光，经过物镜聚焦到样品上，产生频率为２的二次谐波，由另一个高数值孔径的物镜收集，滤光片（一般为窄带滤光片）滤掉激发光和可能产生的荧光和其他背景光，再用探测器件（如ＰＭＴ）和计算机系统进行信号的采集、存储、分析和显示．要实现二次谐波微成像需要对以下因素进行最优化考虑：超短脉冲激光、高数值孑Ｌ径的显微物镜、高灵敏度的非解扫面探测器、准相位匹配和具有高二阶非线性的样品Ｊ．激光器：掺Ｔｉ蓝宝石飞秒激光器因具有高重复频率（８０ＭＨｚ）和高峰值功率，单脉冲能量低且町在整个近红外区（７００～１０００ｎｍ）内连续调谐，所以是二次谐波显微成像的理想光源．激光的重复频率对ＳＨＧ也有影响，如果提相位匹配及实现方法
模式匹配的KMP算法详解
关于快速高效的模式匹配算法的剖析与改进
字符串的模式匹配算法
相位匹配及实现方法Word版
模式匹配KMP算法实验报告
实验三____串的模式匹配
二次谐波 相位匹配及其实现方法
串的模式匹配算法实验报告
立体匹配算法可行性分析报告
字符串匹配算法总结
高效的多模式匹配算法
相位匹配及实现方法
串的朴素模式匹配算法(BF算法)
立体匹配十大概念综述
基于WM算法改进的多模式匹配算法
二次谐波相位匹配及其实现方法