算法比较（精选10篇）
算法比较 篇1
摘要：基本的算法策略有迭代法、蛮力法、分治法、贪婪法、动态规划等。以整数因子分解为例,试图比较各种算法的优劣,并提出每种算法适合的问题类型。
关键词：穷举法,迭代法,数学模型,分治法,动态规划,比较
0 引言
基本的算法策略有迭代法、蛮力法、分治法、贪婪法、动态规划等。
问题描述:设n是正整数且n>1,求n的所有因子(1与n不考虑)。
1 算法设计
1.1 穷举法,采用2~n-1之间的数试除法
这是最自然的想法,如果n除以在这个范围内的任一数,而余数为0,则这个数就是n的因子。求余数采用取模的方法。
1.2 采用2~sqrt(n)之间的数试除
因为n的最大因子≤n/2,如果求出n在2~n/2范围内的因子i,那么n的另外一个因子就是n/i。但是在这个范围内有重复操作。所以还可缩小范围在2~sqrt(n),这样就避免了重复输出。
1.3 采用迭代法解数学模型
一个合数的所有因子都可以由素数相乘得到。所以只要求出n的所有素数因子就可以相应求出它的所有因子。由此该问题将被分解为整数因子划分和素数测试两个子问题。
数学模型设计:n=P1(Q1)*P2(Q2)………Pn(Qn)
其中,P1
数据结构设计:新增两个一维数组A[N]与B[N],其中A[i]存放素数Pi,B[N]存放该素数的指数Qi因为小于10的4次方的素数有1229,小于10的8次方的素数有5761455个,小于10的12次方的素数有37607912018个。如果n值很大,则相应地N值就会很大,用A[0],B[0]存放实际元素个数。
算法优化:对算法3中的整数划分算法其实就是一个求质数的问题。质数除了2之外,其余的都是奇数,所以可以把2单独考虑,在3~sqrt(n)范围内每次都自增2,而不是自增1,这样又大大缩小了时间复杂度,得到O(log2(n)/2)。
1.4 采用递归法求解数学模型
因为算法3的整数因子划分算法其实是个递推过程,现在把它转换成递归过程。其中数组A[N],B[N],变量L都设置为外部变量,且都初始化为0。
2 算法分析
算法1分析:问题域从2~n-1,基本语句为if(n%i==0),该语句执行次数为n-2次,时间复杂度为O(n)。
算法2分析:其基本语句与算法1相同,语句执行次数为sqrt(n)-1,时间复杂度为O(log2(n))。对于一个正整数n,其位数为m=[log10(n+1)],则算法时间复杂性是O(10m/2)。假设m=40,每次循环只需要1ns,它也需要花费1000年的时间完成。
算法3分析:在整数因子划分算法中采用了迭代法,对每找到一个质数因子i,n的值就变成n/i。其基本语句是n=n/i,时间复杂度为O(log2(n))如果n=24,n的值变化情况如下:24->12->6->3->1。也就是说for循环语句只执行了2次,基本语句n=n/i执行了4次。有两次调用了素数判断算法,该算法只分别执行了1次。所以总共执行了5次,这与算法2:sqrt(n)-1=sqrt(24)-1=3次相比时间复杂度增加,而且还开辟了两个数组,浪费了空间。因此对于n域较小时,直接使用穷举法最合适。若是n域很大,其位数超过16位,显然采用迭代法求解可以将n划分成更小的值,其时间复杂度将大大减小。
算法4分析:算法4的时间复杂度与算法3相当,但是又需要增加栈来操作,所以对该问题递归算法没有递推算法好。这也正好验证了对于大多数实际问题能够采用递推法的时候尽量不要使用递归法。因为分治法与动态规划法都是递归算法思想的应用与扩展,那么采用这两种策略是否能够提高效率。
分治法有一个很重要的特征,就是该问题所分解出的各个子问题是相互独立的,且子问题之间不包含公共的子问题。对于整数因子分解,它显然不满足该特征。首先,它包含公共的子问题:判断素数,其次各子问题之间也不是独立的,都与n,i有关。
动态规划=贪婪策略+递推+存储递推结果。贪婪策略采用的是局部处理法来求解最优解,因此它具有无向性。即后面的过程不会影响前面的状态,只与当前状态有关,从而达到由局部最优解构造出全局最优解。但是整数因子分解并不是个求最优解的过程,所以不适合采用贪婪策略解该问题。
虽然这两种策略不适合该问题,但是它们在实际运用中很广泛。如果采用蛮力法的选择排序与起泡排序,其时间复杂度是O(n(2)),但是采用归并排序与快速排序其时间复杂度可以缩小为O(nlog2(n)),减小了一个数量级。n值越大,分治策略的优越性就越明显。
3 算法策略比较
由以上分析可知,解决该问题最好的策略是迭代法。对于问题域较小又容易解决的问题采用蛮力法。对于需要进行数值计算的问题采用迭代法。对于较复杂难以直接解决,必须进行分解才能解决的的大问题,采用分治法和动态规划法。特别是当这个问题涉及到最优化问题时采用动态规划法。如果这个问题在每一阶段的选择都是当前状态下的最优选择,并且最终能够求得问题的整体最优解,则采用贪心法。
在计算机领域中,最常见的问题有:查找问题、排序问题、图问题、组合问题、几何问题。蛮力法解决这些问题,一般情况下时间复杂度分别为O(n)、O(n*n)、O(n!)、O(2(n))、O(n*n)。它的解题思路简单明了,实现容易,附加空间小,而且经过思考可以对算法进行一定程序的改良。但是对于组合问题,图问题,除非是问题规模非常小的实例,否则蛮力法几乎不实用。分治法解决各种问题比蛮力法更优越,大多情况下时间复杂度均为O(nlog(2(n))。它利用空间复杂度来换取时间效率。因此查找或排序的速度更快。迭代法可进行数学建模,对于问题规模大而且可以设计数学模型的问题来说,它比其它算法更优越。贪婪策略和动态规划策略对图问题,组合问题比其它策略更好。只是动态规划比贪婪策略更通用。因为很多问题采用贪婪策略可能找不到解时,采用动态规划可以解决。如果贪婪策略可以解决,一般采用贪婪策略。
当我们面临实际的各种问题时,应该首先分析它属于上述常见问题中的哪一种。对于查找问题,它在实际运用中主要用于搜索,而且要求时间效率很高。若搜索的内容是已经排好序的线性表,这时应该采用分治法。若搜索的内容是需要进行增、删改的动态查找表,则采用动态规划法。对于排序问题,在实际运用中主要是内排序,排序的目的主要是为了进行快速查找,一般采用分治或减治法提高时间效率。其中二路归并排序,快速排序与堆排序的时间复杂度都可以达到最优值O(nlog2(n))。对于图问题,总是会涉及到最优化问题,所以可针对不同问题的特点,在动态规划法、贪心法、回溯法中选择。对于组合问题,这几种策略都可以用,但是分治法、贪心法的实际运用范围更广。对于几何问题,若涉及到数值计算,选用迭代法。若涉及到最优化问题应该选用分治法或动态规划法。
参考文献
[1]王红梅.算法设计与分析[M].北京:清华大学出版社,2006.
[2]吕国英.算法设计与分析[M].北京:清华大学出版社,2008.
[3]李云清,杨庆红,揭安全.数据结构[M].北京:人民邮电出版社,2006.
算法比较 篇2
摘要：RC5及RC6是两种新型的分组密码。AVR高速嵌入式单片机功能强大，在无线数据传输应用方面很有优势。本文基于Atmega128高速嵌入式单片机，实现RC5和RC6加密及解密算法，并对算法进行汇编语言的优化及改进。根据实验结果。对两种算法的优热点进行比较和分析。
关键词：Atmega128 RC5 RC6 分组密码 混合密钥 Flash
引言
在无线局域网中，传输的介质主要是无线电波和红外线，任何具有接收能力的窍听者都有可能拦截无线信道中的数据，掌握传输的内容，造成数据泄密。因此，对于无线局域网来说，数据的加密是关键技术之一。
AVR高速嵌入式单片机是8位RISC MCU，执行大多数指令只需一个时钟周期，速度快(8MHz AVR的运行速度约等于200MHz C51的运行速度);32个通用寄存器直接与ALU相连，消除和运算瓶颈。内嵌可串行下载或自我编程的Flash和EPPROM，功能繁多，具有多种运行模式。
依照IEEE发布的802.11无线局域网协议标准，采用Atmel公司的Atmega128高速嵌入式单片机，开发无线数据传输装置。为了实现无线数据传输时的安全性，同时尽可能节省成本，采用软件进行加密、解密。这就对算法的简法性、高速性及适应性提出了很高的要求。RC5和RC6两种新型的分组加密算法能够比较好地满足上述的要求。
1 RC5及RC6算法
1.1 RC5及RC6的参数
RC5及RC6是参数变量的分组算法，实际上是由三个参数确定的一个加密算法族。一个特定的RC5或者RC6可以表示为RC5-w/r/b或者RC6-w/r/b。其中这三个参数w、f和b分别按照表1所列定义。
表1 RC5及RC6算法参数定义
参 数定 义常 用w以比特表示的字的尺寸16,32,64r加密轮数0～255b密钥的字节长度0～255
1.2 RC5及RC6字运算部件
RC5及RC6均由三部分组成，分别为混合密钥生成过程、加密过程和解密过程。在这两种算法中，共使用了六种基本运算：
①模2w加法运算，表示为“+”;
②模2w减法运算，表示为“-”;(本网网收集整理)
③逐位异或运算，表示为+;
④循环左移，字a循环左移b比特表示为“a<<
⑤循环右移，字a循环右移b比特表示为“a>>>b”;
⑥模2w乘法，表示为“×”。
RC5算法运用了上述的①～⑤运算部分，RC6算法使用了上述所有的运算部件。
1.3 RC5算法
(1)RC5算法混合密钥生成过程的伪代码表示
S[0]=Pw
for i=1 to t-1 do
S[i]=S[i-1]+Qw
输入比特数大小为8，密钥长度为b的用户密钥K[0]至K[b-1]
转换K[0]至K[b-1]为数组长度为c，比特数为w的L[]数组
i=j=0 x=y=0
do 3×max(t,c)times：
S[i]=(S[i]+x+y)<<<3;X=S[i];i=(i+1)mod t
L[j]=(L[j]+x+y)<<<(x,y);X=L[j];j=(j+1)modC
其中c=[b×8/w]方括号表示上取整运算，t=2r+2，当w分别为16、32、64时，常数Pw、Qw分别如表2所列。
表2 常数Pw、Qw取值表
W163264Pw0xB7E10xB7E151630xB7E151628AED2A6BQw0x9E370x9E3779B90x9E3770B97F4A7C15
(2)RC5加密算法过程的伪代码表示
Input(A,B)
A=A+S(0)B=B+S[1]
for i=1 to r do
A=((A+B)<<
B=((B+A)<<
Output(A,B)
其中初始的A、B分别为要加密的两个比特数为w的数据，最终的A、B分别为加密好的两个比特数为w的数据。
(3)RC5解密算法过程的伪代码表示
Input(A,B)
for i=r down to 1 do
B=((B-S[2i+1])>>>A)+A
A=((A-S[2i])>>>B)+B
A=A-S[0] B=B-S[1]
Output (A,B)
其中初始A、B中的数据就是已经加密了的比特数为w的数据，最终的A、B中的数据为解密后的比特数为w的数据。
1.4 RC6算法
(1)RC6算法混合密钥生成过程伪代码表示
RC6混合密钥生成过程与RC5相同，只是t的取值为2r+4。
(2)RC6加密算法过程伪代码表示
Input(A,B,C,D)
B=B+S[0]D=D+S[1]
for i=1 to r do
t=(B×(2B+1))<<
u=(D×(2D+1))<<<1og2w
A=((A+t)<<
C=((C+u)<<
(A,B,C,D)=(B,C,D,A)
A=A+S[2i+2]C=C+S[2i+3]
Output(A,B,C,D)
其中初始的A、B、C、D分别为要加密的四个比特数为w的.数据，最终的A、B、C、D分别为加密好的四个比特数为w的数据。
(3)RC6解密算法过程的伪代码表示
Input(A,B,C,D)
C=C-S[2i+3]A=A-S[2i+2]
for i=1 to r do
(A,B,C,D)=(D,A,B,C)
u=(D×(2D+1))<<
t=(B×(2B+1))<<
C=((C-S[2(r-i)+3])>>>t)+u
A=((A-S[2(r-i)+2])>>>u)+t
D=D-S[1] B=B-S[0]
Output(A,B,C,D)
其中初始的A、B、C、D分别为已经被加密的四个比特数为w的数据，最终的A、B、C、D分别为解密后的四个比特数为w的数据。
2 RC5和RC6算法的实现及改进
2.1 AVR单片机的RC5和RC6算法流程
RC5及RC6算法加密过程实现流程图如图1所示，解密过程实现流程图如图2所示，总体过程流程图如图3所示。
2.2 AVR单片机RC5和RC6算法的改进
①在进行算法流程的安排时，考虑到AVR高速嵌入式单片机只有32个8位寄存器，为了节省寄存器的使用，应该在混合密钥生成过程执行后，再把待加密的数据赋予寄存器。这样在混合密钥生成过程以前的寄存器都可以被使用，而不会对整个算法的执行结果造成影响。
②在进行RC5及RC6算法参数的选择时，考虑到AVR高速嵌入式单片机指令最多只支持16位数据相加以及程序的简洁化，所以在本程序中选择w为16而没有选择w为32，r和b的值依据Rivest的建议分别取为12和16。
③在执行算法中的左循环或者右循环运算时，考虑到循环移位的效果，实际循环移位的位数应该为要执行移位次数的低1log2w位。在本程序中为要执行移位次数的后四位。
④在执行算法中的模2w加法运算、模2w减法运算、模2w乘法运算时，由于2w的取值为65536,而2个8位寄存器(0～15位)最高可以表示数据的值为65535，数据再大就要向高位进位，所以在本程序执行上述的算法只需要考虑到2个8位寄存器所表达的值就得到了上述运算的最终结果，而不用再进行模2w运算。
⑤为了提高数据加密及解密的速率，可以把混合密钥生成过程提前执行，以使之生成一张混合密钥表。把这个表装入发送数据端Atmega128高速嵌入式单片机和接收数据端Atmega128高速嵌入式单片机的Flash中，从而在以后的加密与解密过程中直接使用混合密钥。值得注意的是，每当用户输入的用户密钥发生改变时，必须重新执行混合密钥生成过程，并且重新给Flash装载重新生成后的混合密钥表。在本程序中，RC5混合密钥表共占据52个8位寄存单元，RC6混合密钥表共占据56个8位存储单元。
⑥在本程序中运用加法运算以及移位运算实现了16位二进制数乘以16位二进制数的无符号运算。该运算的子程序如下：
chengfa:clr result2
clr result3
ldi count1,16
lsr chengshu1
ror chengshu0
chengfa0:
brcc chengfa1
add result2,beichengshu0
adc result3,beichengshu1
chengfa1:
ror result3
ror result2
ror result1
ror result0
dec count1
brne chengfa0
ret
3 RC5及RC6算法实验结果及其比较与分析
RC5及RC6算法实验的混合密钥过程、加密过程、解密过程和总体过程的效果比较如表3、4、5、6所列。
表3 RC5及RC6算法混合密钥过程效果比较
混合密钥生成过程周期计数停止观察/μs程序大小/字ctRC5算法15 2481270.67141826RC6算法15 2461270.50141828
表4 RC5及RC6算法加密过程效果比较
加密过程(不考虑生成混合密钥的时间)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5算法2511209.256632约为152 927RC6算法625295210.7517064约为12 282
表5 RC5及RC6算法解密过程效果比较
解密过程(不考虑生成混合密钥的时间)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5 算法2509209.086832约为153 051RC6 算法625275210.5817664约为12 283
表6 RC5及RC6算法总体过程效果比较
总体算法过程(考虑生成混合密钥的时间，不考虑数据传输所用的)周期计数停止观察/μs程序大小/字共处理数据的位数效率/(位/s)RC5算法20 2601688.3326732约为18 594RC6算法140 27411 689.5045564约为5475
由表3可以发现，RC6算法和RC5算法在混合密钥生成时程序的大小相同，但量RC6算法却比RC5算法省时。这是因为根据混合密钥生在方法在执行循环，最终生成混合密钥时要执行比较操作。当超出了比较范围t时，要对指针地址重新复位。RC6算法t的取值大于RC5算法中t的取值，因此RC6算法执行了较少的复位操作。从而节省了运行周期，故RC6算法比RC5算法在生成混合密钥时省时。
以上所有实验结果均是在AVR Studio4.07仿真软件上选用Atmel公司的Atmega128高速嵌入式单片机为实验设备平台。选取参数w=16、r=12、b=16，并根据计算公式求得c=8，t=26(RC5算法)或者t=28(RC6算法)在12MHz运行速度下模拟所得。
从实验结果所得的表3、表4、表5、表6可以明确得出以下结论。
①从程序的执行效率来看，无论在加密还是在解密过程中，RC5算法都要比RC6算法执行效率高。
因此，在一些非常注重程序执行效率，而对数据安全性要求不是非常高的情况下，应该采用RC5算法。
②从程序的执行时间来看，无论在加密过程不是在解密过程中，RC5算法都要比RC6算法省时。因此，在一些对程序执行时间长短要求很高，对数据安全性要求不是非常高的情况下，可以采用RC5算法。
③从程序的大小来看，无论在加密过程中还是在解密过程中，RC5算法都要比RC6算法更简洁。因此，在一些对程序所用空间大小要求很高，对数据安全性要求不是非常高的情况下，可以采用RC5算法。
④从安全性角度考虑，RC6算法是在RC5算法基础之上针对RC5算法中的漏洞，主要是循环移位的位移量并不取决于要移动次数的所有比特，通过采用引入乘法运算来决定循环移位次数的方法，对RC5算法进行了改进，从而大大提高了RC6算法的安全性。因此，在一些对数据安全性要求很高的情况下，应该采用RC6算法。
结语
几种虹膜定位算法的分析与比较 篇3
关键词:虹膜;离散圆形动态轮廓线法;灰度阈值分割法;圆Hough变换;点Hough变换
1 引言
虹膜定位是虹膜识别处理过程中非常重要的环节,它不仅决定了后续过程能否继续,而且决定了提取特征是否有效,并最终决定虹膜识别结果。虹膜包含纹理的部分是内外两个近似圆形边界之间的部分,虹膜内侧与瞳孔相邻,外侧与眼白相邻。但是,这两个圆不是完全同心的[1],需要分别对内外两个边界进行处理。
本文介绍了离散圆形动态轮廓线法、灰度阈值分割法、圆Hough变换和点Hough变换几种虹膜定位算法,并对各种算法进行了分析和比较。
2 离散圆形动态轮廓线法
离散圆形动态轮廓线法(DCAC:Discrete Circular Active Contours),这种算法使用了先验的信息和统计学的知识,找出虹膜边界和评定这种方法的成功和失败。由于瞳孔-虹膜边界是圆形,需要定义一个圆形的动态轮廓线,假定一个开始点,在图像中定位一个圆[2]。
每个顶点用 vi 来表示,内部力Fint,i被定义为:
(2.1)
是该顶点在完美多边形中的位置。有如下公式:
(2.2)
其中Cr表示当前边界的平均半径,C= (Cx,Cy) 是当前的质心,n是节点数,δ是每次迭代中半径的增加值,质心C被定义为:(2.3)
平均半径Cr被定义为:(2.4)
由图像像素的灰度级提供的图像力把顶点向里推,来平衡轮廓线的内部力。每个顶点 vi 的外部图像力的方向定义为:
(2.5)
大小定义为:
(2.6)
I(vi) 是vi最近顶点的灰度值,这样每个顶点的图像力被定义为:(2.7)
如图2所示:
轮廓线的运动由内部力和图像力之和决定,因此从t到t+1次迭代顶点运动表示为:
(2.8)
β是这两种力的权重。这个运动直到内外力平衡或者达到允许误差范围之内停止。如果当前轮廓线的平均半径的中心和m次迭代前的相同,就认为达到了平衡。这样就确保了即使单个顶点发生震荡移动,轮廓线也能够保持稳定。
离散圆形动态轮廓线法原则上是依靠初始配置能够找到瞳孔-虹膜边界或者虹膜-巩膜边界,因为在每个例子中圆形边界内部的区域更加黑。然而,在真实的眼睛图像中这样的方法会带来几个问题:
首先,DCAC算法搜索瞳孔-虹膜边界的时候频繁地受到来自角膜的镜面反射的影响。这个问题可以通过预处理图像把所有灰度值高于128的部分全部设为128来解决。
第二个问题是在真实的眼睛图像中该算法极度地依赖于公式2.2中δ的取值。如果δ的值太大,轮廓线总是会移出图像;反之如果δ值太小,轮廓线或者维持在开始的地方,距离实际的目标增长得非常缓慢,或者收缩到半径为零。不幸的是,没有适用于广泛的眼睛图像的δ值。
3 灰度阈值分割法
灰度阈值分割法是一种基于区域的技术,这种方法是把每个像素的灰度值与阈值T进行比较,根据它是否超过该阈值而将图像中的像素点分成两类。
一般意义下,阈值运算可以看作是图像中某点的灰度函数,或者该点的某种局部特性(该点的平均灰度)及该点在图像中的位置的检验,这种阈值检验函数可记作:
T (x, y, N ( x, y, )g ( x, y) )(3.1)
式中g( x,y ) 是点( x,y )的灰度值,N( x,y )是点( x,y )的局部邻域特性。如果 g( x,y )>T( x, y, N( x,y ), g( x,y )) (3.2)
则点( x,y )记作物体点,反之则为背景点。若设( x,y )表示阈值处理后的图像,则有:
根据瞳孔和眼白、虹膜之间的关系。从图4所显示的虹膜来看,瞳孔的灰度最为趋向一致,也是图像中灰度值最低的部分,虹膜图像的灰度直方图具有明显的多峰特征,灰度值最低的峰值之后所对应的峰谷就是瞳孔与其他部分分割的阈值。
采用如下步骤进行灰度阈值分割[6]:
(1)先计算出整个图像的灰度直方图。灰度直方图是灰度值的函数,描述的是图像中具有该灰度值的像素的个数。其横坐标表示像素的灰度级别,纵坐标表示该灰度出现的频率(像素的个数)。在实际操作中对整个图像的所有像素进行扫描,建立数组int greyCount[256],用以存储各个灰度值出现的次数。
(2)平滑灰度直方图:采用中值滤波和改进的盐和胡椒滤波两种方法对虹膜图像进行噪声处理。
(3)求可能的阈值点:设灰度直方图的包络线为f(x),则阈值点a是满足下列条件的一个点: 其中δ为一微小增量,用差分代替导数求得阈值点,对于数字图像,可以用一阶差分代替一阶微分:
(3.4)
(3.5)
(4)确定阈值点:求其中第一和第二个波峰之间的波谷对应的灰度值T0,在大部分情况下,直接使用T0作为阈值就可以取得很好的效果,但是有的图像中睫毛或眼眉的灰度要低于瞳孔的灰度,这时求得的阈值偏低,瞳孔会被误认为背景,需要进一步判断:计算T0与第一个波峰对应的灰度值之间的差值,如果差值大于3,则T0就可以作为最后的阈值T1;否则继续在直方图中搜索下一个波峰后的波谷,作为二值化的阈值T1。这些规定,是根据所用虹膜库的虹膜图像为320×280,经过实验和先验知识综合确定的。
求得阈值之后,设阈值为a,则可用下述方法将图像二值化:扫描整个图像,若像素点的灰度值大于a,则赋值为255;若其小于a,则赋值为0。
图5展示了图4的灰度直方图,由图可以看出,它应该有两个主要的峰值,其中的第一个峰值,对应的就是瞳孔区域灰度集中的范围,提取瞳孔的二值化阈值应该选在第一个峰值的右侧。图6显示了对该图进行灰度分割(保留阈值<=35的部分)后的结果。
由此可见,阈值分割不失为一种分离瞳孔的途径,但是应当指出,对于聚焦良好,光照均匀的虹膜图像,可以直接采用投影的方式确定瞳孔的半径和圆心,但是,对于光照不均匀的图像,阈值分割之后会出现许多干扰点,图7是一幅光照不均匀情况下的虹膜图像及其阈值变换,可见光照不均匀的情况下阈值变换后的瞳孔边界有棱角,而且周围有很多干扰点,这对确定虹膜的内边缘增加了不少难度。
虽然阈值分割不能一次分离出完整的环形虹膜,但已经使环形虹膜内外边界明显,为下一步的内外边缘的检测提供了更好的条件。
4 圆Hough变换
Hough变换[4]是一种用于区域边界形状描述的方法,经典的Hough变换常常被用于直线段、圆和椭圆的检测。Hough变换的思想是将图像的空间域变换到参数空间,即将原始图像中给定形状的曲线或直线变换成变换空间的一个点,原始图像中曲线或直线上所有点都集中到变换空间的某个点上形成峰点,这样,把原始图像中给定形状的曲线或直线的检测问题,变成寻找变换空间的峰点问题,也即把检测整体特性(给定曲线的点集)变成检测局部特性的问题。
Hough变换可应用于检测图像空间解析曲线(u,v)=0,其中u为解析曲线上的点(二维矢量),v为参数空间上的点(矢量)。由上述原理,可得圆的Hough变换的方法:在x-y平面上,中心在(ac, bc),半径是 的圆周C上每一点 (x, y) 满足
(4.1)
如果将圆心 (a, b) 看作为变量,则在a-b平面上可以画出中心在 (x, y) 、半径rc的圆Ch。在圆C上的每一点 (xi, yi) ,在a-b平面上有中心在 (xi, yi) 、半径为rc的圆Chi与之对应,且这些圆组成了相交于一点 (ac, bc) 的圆群。进一步把圆的半径r作为变量,在a-b平面得到由不同半径的圆Chi构成的圆环。在a-b-r空间中建立三维数组,数组中元素Pai,bi,ri的值代表a-b平面上通过点 (ai, bi)、半径为ri圆的个数,则数组中的最大值所对应的参量(ai, bi, ri),就是图像空间中圆的圆心和半径。
Hough变换虽然使用广泛,但是因为它要在三维空间内搜索,计算量是非常大的。
5 点Hough变换[5,6]
点Hough变换是Hough变换的改进,它是利用圆周上任意两条不平行弦的中垂线相交于圆心的性质。原理如图8所示,设K、L、M为圆周上的三个点,由圆的几何性质可知,KL的中垂线Lkl与LM的中垂线Llm必然相交于圆C的中心O。设K、L、M三点的坐标分别为 (xk, yk) 、 (xi, yi) 、 (xm, ym) ,则 Lkl 和 Lim 的方程分别为:
(5.1)
(5.2)
利用(5.1)和(5.2)式,计算出圆 C 的圆心 (ac, bc) 和半径 rc:
(5.3)
(5.4)
(5.5)
可见,半径为ri、圆心为 (ai, bi) 的圆周上任意不共线的三点(以下称为点组)对应 a-b-r 空间中的一点(ai, bi, ri),所以称之为点Hough变换(Point Hough Transform)。
用向量表示 a-b-r 空间中的点,则图像中圆 (ai, bi, ri) 上的点组对应于a-b-r空间中的向量。在图像中选取N个点组,得到向量 0、1、…N-1,N组来自同一个圆上的点组对应的向量相同。向量组中不同编号的向量可能相同。向量组中出现次数最多的向量就是图像中圆的参量。用数组P[n] (n=0,…N-1) 表示向量组中向量 出现的次数,则有:
确定数组P[n] 后,就可以找出图像中圆的参量值:
(5.7)
实际上,由于数字化误差的原因将式(5.6)中kk=1的条件由 改为,为一微小增量,更为符合实际条件。PHT不需搜索变量空间,只对选取的点组进行统计,计算复杂性仅跟所选择点组的数目有关。可见,选择适当的点组可以大大降低计算复杂度。
6 结束语
综合以上几种方法的优缺点,结合试验结果分析,点Hough变换无须搜索变量空间,只对选取的点组进行计算,复杂性仅跟点组数有关,因此更适合用于虹膜定位。
参考文献
[1] MANN I. The Development of the Human Eye[M]. New York: Grune and Stratton,1950.
[2] RITTER N J, COOPER R. Locating the Iris :A First Step to Registration and Identification[A]. International Conference on Signal and Image Processing[C]. IASTED, Aug.2003:507-512.
[3] 常海军.虹膜识别算法研究与实现[D].杭州:浙江大学,2005.
[4] 夏良正.数字图像处理(修订版)[M].南京:东南大学出版社,1999.
[5] 林金龙,石青云.用点Hough变换实现圆检测的方法[J].计算机工程,2003,29(11):17-18.
蚁群算法与粒子群算法的比较研究 篇4
由简单个体组成的群落与环境以及个体之间的互动行为称群智能(swarm intelligence)。群智能算法作为一种新兴的演化计算技术已成为越来越多研究者的关注焦点,群智能在没有集中控制且不提供全局模型的前提下,为寻找复杂的分布式问题求解方案提供了基础。目前,群智能理论研究领域主要有两种算法:蚁群算法(Ant Colony Optimization,ACO)和粒子群算法(Particle Swarm Algorithm,PSO),前者是蚂蚁群落食物采集过程的模拟,后者是鸟群觅食过程的模拟。本文对这两种算法的原理、模型、应用等方面进行比较分析,并对这两种算法的改进以及与其它算法的混合做出总结。
一、蚁群算法
蚁群算法是由Colorni、Dorigo和Maniezzo通过对蚁群觅食行为的研究,于1991年提出的一种仿生进化算法[1],利用蚁群在搜索食物源的过程中所体现出来的寻优能力来解决一些离散系统优化中的问题。蚂蚁是一种社会性昆虫,通过一种特有的通信机制,其群体行为展现出高度协作性,能够完成复杂的任务,并且,蚂蚁还能够适应环境变化随时调整搜索路径。作为一种随机搜索处算法,与其他模型进化算法一样,ACO也是通过侯选解组成的群体的进化过程来寻求最优解。
蚁群算法首先被成功应用于旅行商问题(TSP)上,以此为例算法的寻优过程[2]:设有m只蚂蚁,每只蚂蚁根据信息素浓度选择下一个城市(tij(t)为t时刻城市i和j之间路径上残留的信息素浓度,dij(i,j=1,2,...,n)表示城市i和j之间的距离),规定蚂蚁走合法路线,除非周游完成,不允许转到已访问城市。完成周游后,更新蚂蚁访问过的每一条边上的信息素。
初始时刻,各路径的信息量tij(0)相等,m只蚂蚁被放置到不同的城市上。蚂蚁k(k=1,2...,m)在运动过程中,根据各条路径上信息量决定转移方向,表示在t时刻蚂蚁k由位置i转移到j的概率。
其中,allowedk表示蚂蚁k下一步允许转移到的城市集合,随k的行进而改变;信息量τij(t)随时间的推移会逐步衰减,用1-ρ表示它的衰减程度;α,β分别表示蚂蚁在运动过程中积累信息量及启发式因子在蚂蚁选择路径中所起的不同作用;ηij为由城市i转到j的期望程度,可根据某种启发算法而定。
经过n个时刻,蚂蚁k走完所有城市,完成一次循环。此时,根据式(2)一(4)更新各路径的信息素:
其中:ρ表示信息素挥发系数,Δtij表示本次循环中路径ij上的信息量增量,表示蚂蚁k在本次循环中在城市i和j之间留下的信息量,其计算方法根据不同模型而定,最常用的是ant-cycle system:
其中:Lk表示蚂蚁k环游一周的路径长度,Q为常数。
算法流程如图1所示:
二、粒子群算法
Kennedy和Eberhart于1995年受鸟群觅食行为的启发提出了粒子群优化算法(Particle Swarm Optimization,PSO)[3]。PSO中,每个优化问题的解视为d维搜索空间中的一个粒子,粒子在搜索空间中以一定速度飞行,所有的粒子都有一个由被目标函数决定的适应值,并且知道自己到目前为止发现的最好位置,每个粒子利用个体和全局最好位置更新位置和速度。
假设m个粒子组成一个种群并在D维空间搜索,第i个粒子在第t代的位置表示为一个D维的向量Xi(t)=(xi1,,xi2,…,xD),飞翔速度为Vi(t)=(vi1,vi2,...,vD),粒子本身历史最佳位置为Pi(t)=(pi1,pi2,...,pD),群体历史最佳位置为Pg(t)=(pg1,pg2,...,pD)。PSO算法迭代公式如下:
其中,w为惯性权重,使粒子保持运动的惯性,使其有扩展搜索空间的趋势;c1和c2为加速系数,代表了将每个粒子拉向Pi和Pg的随机加速项的权重;r1和r2是两个独立的介于[0,1]之间的随机数,t为进化代数。
算法流程如图2所示:
三、两种算法的比较分析
1算法各自优缺点
(1)由于群智能算法采用的是概率搜索算法,ACO和PSO具有共同的优点[4]:
①鲁棒性:由于算法无集中控制约束,不会因个别个体的故障而影响整个问题的求解。
②扩展性:信息交流方式是非直接的,通信开销少。
③并行分布性:可充分利用多处理器,适合于网络环境下的工作状态。
④优化过程无需依赖具体问题的数学特性,例如可微、线性等。
⑤算法简单容易实现:系统中个体能力简单,执行时间短。
另外,PSO还具有如下优点:
①群体搜索,并具有记忆功能,保留个体和全局的最优信息;
②协同搜索,同时利用个体和全局的最优信息指导进一步搜索。
(2)ACO和PSO也存在着局限性:
①优化性能在很大程度上依赖于参数设定,受初始值影响较大。
②容易产生早熟收敛。
另外,ACO收敛速度慢,只有小部分的ACO算法能够被证明是值收敛的,并且在实际应用中常常出现一种有害的搜索偏向现象,即二级欺骗现象。
PSO局部搜索能力差,搜索精度不高,并在理论研究上尚未完善,缺少算法设计的指导原则。
2应用领域
●ACO本质上适合于求解离散组合优化问题,在旅行商问题上取得成功应用后陆续渗透到其它领域。在指派、调度、子集、带约束满足等组合优化问题时达到了高效的优化性能。并在图着色、电路设计、二次分配问题、数据聚类分析、武器攻击目标分配和优化、大规模集成电路设计、网络路由优化、数据挖掘、车辆路径规划、区域性无线电频率自动分配、集合覆盖等优化领域得到了成功应用。
●PSO本质上适合于处理连续优化问题,但如果对求解问题进行变形或修正速度和位置更新公式也能将其应用于离散优化问题上。并且,鉴于其通用性和有效性,在解决一些典型优化问题时,其性能甚至超过了遗传算法,已成功应用于训练人工神经网络、函数优化、约束优化、多目标优化、动态优化、参数优化、组合优化、模糊系统控制、电力系统、信号处理、模式识别、生物医学等领域中。
3与其它算法混合
由于ACO与PSO具有容易与其它算法结合的特点,根据各算法的优缺点,在算法中结合其它优化技术,以提高算法的优化性能。
①蚁群算法与差分演化结合:针对蚁群算法对参数控制的依赖性、早熟和停滞等现象,以及易与其他算法结合的特点,将差分演化算法应用到蚁群算法的参数选取中,将蚁群算法的参数作为差分演化算法解空间的向量元素,自适应地寻找蚁群算法最优参数组合的同时求解问题的最优解。
②蚁群算法与粒子群算法结合:针对蚁群算法容易出现早熟现象以及算法执行时间过长的缺点,将粒子群算法引入到蚁群算法中,让蚂蚁也具有粒子的特性。
③粒子群算法与模拟退火结合:先利用PSO算法的快速搜索能力得到一个较优的群体,然后利用SA的突跳能力对部分较好的个体进行优化。
④粒子群算法与遗传算法结合:针对PSO容易早熟的缺点,在PSO中引入启发性变异机制,以扩展了算法的搜索区域,提高了算法的速度和精度且不容易陷入局部最优。
⑤粒子群算法与差分演化结合:针对粒子群算法易陷入局部极小点、搜索精度不高等缺点,在算法改进方面引用差分演化算法的变异操作,从而避免算法收敛到局部。
四、展望
群智能算法采用分布式计算机制、鲁棒性强、可扩充性好、优化效率高、并且简单易于实现,为解决实际优化问题提供了新的途径和方法。除了本文提出的ACO和PSO,群智能算法还包括研究蜜蜂通过与环境之间的信息交互实现安排工作的蜂群算法[5]、李晓磊博士通过模拟鱼群觅食行为和生存活动提出的鱼群算法[6]。作为一门新兴领域,群智能算法尚缺乏系统的分析和坚实的数学基础,实现技术不规范,在适应度函数选取、参数设置、收敛理论等方面还需要做进一步研究与探索。在此基础上,对算法加以改进或混合其他技术,以提高算法优化性能也是值得深入研究的一个方向。并且需不断拓宽其应用领域,以进一步推广群智能算法的应用。
参考文献
[1]A.Colorni,M.Dorigo,G.Theraulaz.Swarm intelligence: From natural to artificial systems[M].New York:Oxford Universyty Press,1999.
[2]宋雪梅,李兵.蚁群算法及其应用[J].河北理工学院学报,2006年2月,第28卷第1期:42-45.
[3]Kennedy J,Eberhart R.Particle Swarm Optimization[R].In:IEEE International Conference on Neural Networks,perth,Australia 1995:1942-1948.
算法比较 篇5
关键词:Monte Carlo算法;自主定位;MATLAB
1 介绍
1.1 移动机器人的定位
自主定位是移动机器人研究领域的重要课题。首先赋予机器人一个环境地图知识,然后移动中通过传感器得到的信息估算机器人相对位置的问题,自主定位最关键的问题是全局定位,因为机器人不知道它的初始位置,因此需要全方面定位自己。近几年,粒子滤波器在机器人定位领域中被广泛应用,它作为Monte Carlo方法的一种应用,本文介绍三种蒙特卡罗算法即基本MCL、Dual-MCL和Mixture-MCL,并通过MATLAB软件模拟,实现三种蒙特卡罗算法在机器人全局定位中的设计与分析。
1.2 蒙特卡罗(MCL)算法
通过使用不同表述形式,可以有几种实现概率算法的方法。在这里,我们着眼于Monte Carlo 定位法。首先因为MCL算法相当有效率,我们可以根据计算机的计算能力决定样本数目,其次MCL算法能够应用在非常简单和原始的模型上。
MCL方法是基于Markov假设和Bayes滤波的位置估算自主定位法。通过使用一组离散的带权粒子表示机器人在环境中所处位置的概率分布,利用先验环境地图信息经过初步采样、状态预测、更新权值、重新采样几个步骤递归运算。具体算法如下[1]:
(1)从机器人当前状态信度 Bel ( Xt-1 )随机抽取粒子Xt-1;
(2)根据机器人运动方程,预测粒子Xt-1在下一时刻的位姿Xt,得到该粒子先验概率分布 p(xtxt-1, ut-1);
(1)
(3)通过传感器观测,更新观测模型重要度因子(importance factor)p( ytxt )分派给粒子,得到新样本信度Bel( xt );
(2)
(3)
(4)重复步骤(1)~(3),最后规范新样本信度Bel( xt )的重要度因子,使之相加和为1。
1.3 Dual-MCL算法
基本MCL算法是从前一刻状态和运动模型预测采样粒子,当传感器不是很敏感时效果比较好,而传感器低噪声的时候却会产生很大的误差,这主要是运动模型和观测模型信息非常不匹配造成的[2]。因此Fox和Thrun提出了基于kd-tree的Dual-MCL算法,采样时更多依靠观测模型中传感器的作用。算法如下[3]:
(1)将 bt-1 (St-1 ) 转化为kd-tree;
(2)从预期分布p( ytxt )采样xt ;
(4)
(5)
(3)从分布 p(xtxt-1, ut-1)采样xt-1;
(6)
(7)
(4)在kd-tree中给xt-1加后验概率权值。
(8)
1.4 Mixture-MCL算法
基本MCL算法由于传感器太精确而失效,Dual-MCL由于传感器不敏感失效,结合两种算法的特点,Fox和Thrun又提出了Mixture-MCL算法,即将两种预期分布概率通过公式(9)结合。
(9)
2 仿真实验设计
实验中,设计了如图1的房间,房间尺寸如图所示,即两个20×20m的方形房间中间有一个20×6m的走廊,我们要解决的是房间中移动机器人的全局定位问题。机器人可以在房间中任意移动,并机器人头部安装有激光扫描传感器以获得它的位置数据。同时在房间的每个角A~L都装有数据接收装置,当激光照射到数据接收装置上时,返回的激光具有较大的能量从而使我们获得机器人与接收装置间的距离。
3 程序设计
三种MCL算法虽然具体过程不一样,但都包含了初步采样、状态预测、更新权值、重新采样几个步骤。输入:t-1时刻的带权粒子xt-1,控制输入ut,机器人对环境的观测y,输出:t 时刻的带权粒子xt。
3.1 初始化
设机器人初始信度Bel( x0 ),从Bel( x0 )采样得到m个样本粒子。机器人对自己的初始位置一无所知。在程序中设置如下参数并初始化:
(1) 房间尺寸: Length=Width1=20m,Width2=6m;(2) 粒子总数 m=1000;(3) 所有粒子的初始信度遵循正态分布规律Bel(x0)=1/m;(4) 高斯噪声偏差参数 sensor 和白噪声振幅 Asensor ,这两个参数用来仿真传感器读数; (5) 运动预测模型的平方差 motion 和观察预测模型的平方差observation两者均满足正态分布。(6) 采样时间间隔T=1;
3.2 计算理想路径和模拟传感器读数
通过机器人运动方程计算出机器人可能的位置,我们假设x方向和y方向运动是相互独立的。机器人的任务是从A点出发,沿A到CL中点的斜线运动,进入到走廊后沿走廊中线移动。从目前状态Position(old)得到新的位置Position(new),如下式
Position(new)=Position(old)+T .at+sensor . randn(2,1)(10)
其中at表示移动速度,randn(2,1)产生一个1×2的随机矩阵。
式(11)模拟了增加了高斯噪声和白噪声的实际传感器读数。
sensor_reading=sersor_ideal+sensor . randn(4,1)+A . randn(4,1) (11)
sensor_ideal值为机器人与接收装置间的距离理想值。由于添加了噪声,因此虚拟传感器读数有可能超出范围,在本程序中,给传感器添加了饱和度,即当读数为负值时,我们将值调整为零;当读数超出最大值时,将值调整为最大值。
3.3 初步采样
在基本MCL算法中,程序采用了轮盘赌选择法,即每一个粒子的信度表示轮盘的每一部分,高信度粒子则占有轮盘大比例部分,那么当我们投出一个弹球的时候,就有更多的机会被选到。
Dual-MCL算法和Mixture-MCL算法则采用了kd-tree。
图2给出了轮盘赌选择法流程图。
利用kd-tree采样即抽取等权力粒子构建kd-tree,然后基于kd-tree对其进行分类形成新的粒子簇。可参考中南大学张恒和樊小平的具体算法[4]。
3.4 状态预测
采样后,根据机器人运动模型和当前状态,通过公式预测下一时刻的状态。
(12)
为了防止机器人走出房间,给机器人的位置作了限制。通过选择的粒子计算后验概率 p( ytxt-1 , ut-1 )。
(13)
3.5 观测更新
在3.2中,我们已经得到了模拟的传感器读数,即机器人与接收装置间的距离理想值sensor_reading。但这些数据不能直接告诉我们机器人的位置。在本文中,我们需要从传感器数据往回计算得到机器人的观测位置值。图3给出了机器人位置与传感器读数的几何关系。
通过机器人位置与n个传感器读数的几何关系求得n个位置值,最小二乘法求得机器人位置。
然后得到观测概率密度值 p( ytx ):
(14)
更新信度:
(15)
3.6 权值归一,更新信度
在3.5中,已经得出了j粒子的Bel j( st ),然后将上述过程重复m次,得到m个粒子的St j( st )和。将这些信度归一
经过多轮的迭代之后,权值最大的 st 即是机器人的位置。
4 结果
通过仿真实现,MCL能够简单、快速而较高精度的实现定位问题,且所需计算资源少。图4虚线给出了机器人位置误差变化情况,实线给出了粒子的标准偏差值。
我们发现改进后的Mixture-MCL在少量粒子的概率分布效果要好于基本MCL,图5给出了在只有50个样本粒子情况下基本MCL和Mixture-MCL的信度误差。实验证明了这一现象。
参考文献
[1]Sebastian Thrun, Probabilistic Algorithms in Robotics[J]. AI Magazine, Vol 21, No 4 2000:93-109.
[2]Dieter Fox, Sebastian Thrun, Wolfram Burgard, Frank Dellaert. Particle Filters for Mobile Robot Localization[M]. Springer-Verlag,2001:483.
[3]Dieter Fox, Sebastian Thrun, Wolfram Burgard, Frank Dellaert. Particle Filters for Mobile Robot Localization[M]. Springer-Verlag,2001:485.
[4]张恒,樊晓平,瞿志华.基于多假设跟踪的移动机器人自适应蒙特卡罗定位研究[J].自动化学报,2007(9):941-946.
数值排序算法比较分析 篇6
按照排序的数据规模，可以将排序分为内部排序和外部排序两类[3]。内部排序就是将待排序序列全部加载到内存中一次性排序的过程。外部排序是数据规模超过内存容量而产生的一种多次读取外存数据到内存，分别进行排序后最终整合的排序过程。外部排序本质上是多次内部排序加上多次外存读取的融合，因此，内部排序是排序问题的基础和核心。常用的内部排序算法按照基本思想可以分为插入排序、交换排序、选择排序、归并排序和基数排序等几类，在此选取了常见的7种排序算法，冒泡排序、快速排序、直接插入排序、希尔排序、堆排序和基数排序进行比较分析。
在排序方面的研究和文章已经存在[2,3,4,5]，但是这些研究和数据都是基于C平台和整形数据，而实际应用中Java平台和浮点型数据应用较多。鉴于目前Java计数的广泛应用，在Ja va平台上用7种常用的数值排序算法测试不同规模的整型数据和浮点型数据，为采用何种排序算法提供参考。
1 算法描述和分析
算法描述中的待排记录均用R{R1,R2,R3,R4,R5….Rn}表示，n表示数据规模。
1.1 冒泡排序
1.1.1 基本思想
冒泡排序是一种交换排序算法。基本思想是依次从头到尾依次遍历含有n个元素的待排记录R，比较相邻元素，例如R1,R2，若R1>R2则交换两元素位置。每遍历一次选出最大的元素并且置于排序记录尾位置，为一次冒泡过程。接着排序前n-1个元素序列，进行相同的比较交换过程，选出最大元素置于序列的次尾位置。依次类推，直到待排序列有序位置。通常冒泡排序中会有一个哨兵来记录是否发生了元素交换，当一次遍历中没有发生元素交换时，表明序列已经有序。
1.1.2 时间复杂度
若有n个待排元素，第1次遍历的比较次数为n-1,第二次遍历为n-2,依次类推，第i次为n-i，时间复杂度表示为
冒泡排序的最差时间复杂度为O(f(n))=O(n2)，最优时间复杂度为O(f(n))=O(n)
1.1.3 空间复杂度与稳定性
冒泡排序中只是在元素交换过程中需要一个辅助空间，空间复杂度为O(1)。元素交换只发生在R1>R2的情况下，保持了原序列相同元素的前后位置，所以冒泡排序是一种稳定的排序算法。
1.2 快速排序
1.2.1 基本思想
快速排序是一种交换排序算法。首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面的序列Rleft，所有比它大的数都放到它后面序列Rright，这个过程称为一趟快速排序。接着分别对Rleft和Rright进行同样的快速排序，重复相同的操作，直到序列有序为止。
1.2.2 时间复杂度
每次快速排序是将待排序列分成两个规模较小的子序列接着进行快速排序，即二分问题，形似二叉树问题。其时间复杂度是由快速排序的次数和排序规模决定的，也就是二叉树的树高和元素的个数。
根据树结构理论，快速排序的最优，也是平均时间复杂度为O(f(n))=O(nlog2n)，最差时间复杂度为O(f(n))=O(n2)。
1.2.3 空间复杂度和稳定性
每执行一次快速排序都需要一个辅助空间，若采用递归方式实现需要额外的压栈空间，快速排序的空间复杂度即为执行快速排序的次数，为O(nlog2n)。在排序过程中，不能保证原序列中相同元素的前后位置，是不稳定的。
1.3 插入排序
1.3.1 基本思想
插入排序在这里指直接插入排序，直接插入排序是最简单的插入排序算法。基本思想是把待排记录R按其关键码值的大小逐个插入到一个已经排好序的有序序列RinOrder中，直到所有的元素插入完为止，得到一个新的有序序列。
1.3.2 时间复杂度
插入排序的时间主要消耗在查询待排元素Ri的插入位置过程中，一般采用从后向前顺序遍历序列Rin Order，找到插入位置j,顺序移动Rj(Ri>=Rj）后的元素并将Ri插入到原Rj处。时间消耗由排序序列长度n和和待排元素在原序列中的位置i决定，
最差时间复杂度O(n2)，最优时间复杂度O(n2)，平均时间复杂度O(n2)。
1.3.3 空间复杂度和稳定性
插入排序只需要一个辅助空间，并且插入过程保持了原序列相同元素的前后位置。空间复杂度为O(1)，稳定的排序算法。
1.4 希尔排序[6]
1.4.1 基本思想
希尔排序是一种改进的插入排序算法。首先选取一定的增量d(d<n)将待排记录R进行分组，形成若干个类似分组Ri{Ri,Ri+d,….Ri+jd|i+jd<=n}。在每个小分组里面进行直接插入排序，使得分组记录有序。接着逐渐减小d值，重复相同操作，直到增量d为1，待排记录R有序。
1.4.2 时间复杂度
希尔排序时间复杂度和增量的选取有关，一般采用希尔增量，即初次增量选取待排记录的一半，以后每次减半，直到增量为1。选取希尔增量的时间复杂度为O(n2)，希尔排序时间复杂度的下界为O(nlog2n)。
1.4.3 空间复杂度和稳定性
希尔排序只需要一个辅助空间，空间复杂度为O(1)。希尔排序反复执行了多次插入排序，相同的元素可能在各自的插入排序中移动，所以，插入排序是不稳定的排序。
1.5 堆排序
1.5.1 基本思想
堆排序是一种选择排序算法。堆排序将待排记录R根据元素下标关系看作一棵完全二叉树，并且具有根元素最大或者最小性质，简称大根堆或小根堆。每次排序首先调整大根堆或者小根堆性质，而后交换堆顶R0与最后一个元素Rn(n为待排记录长度，随着排序过程递减)位置，接着在余下待排记录R{R0,…,Rn-1}上进行相同的排序操作，直到只有一个元素R0，排序完成，记录有序。
1.5.2 时间复杂度
堆排序的时间主要消耗在大根堆或小根堆的调整上。堆调整过程是相当于一次完全二叉树的查询过程，整个过程的复杂度为O(nlog2n)。
1.5.3 空间复杂度和稳定性
堆排序过程只需要一个辅助空间用来存放交换过程中的临时变量，但是在交换过程中不能保证原纪录中相同元素的前后位置。空间复杂度为O(1)，算法不稳定。
1.6 归并排序
1.6.1 基本思想
归并排序是一种采用分治思想、建立在归并操作上的有效排序算法。归并操作将已经有序的子序列合并，得到完全有序的序列。通常以每个子序列长度为1开始，两两合并成长度为2的序列，再继续进行归并操作，直到待排记录R完全有序。
1.6.2 时间复杂度
以二路归并为例，每次归并过程都是将两个有序子序列合并为一个有序序列，时间消耗是一个递推的过程。和其他二分递归问题类似，时间复杂度为O(nlog2n)。
1.6.3 空间复杂度和稳定性
归并排序过程需要和待排记录R等大的辅助空间，但是保持了原序列相同元素的前后位置关系。所以，归并排序的空间复杂度为O(n)，稳定的排序算法。
1.7 基数排序
1.7.1 基本思想
基数排序是一种分配式排序算法，也称作桶子法。基数排序根据键值的部分信息（例如数值最高位）将待排记录R分组，而后将分组后的待排记录排序并且按序组合，再按照键值的部分信息（例如数值次高位）分组，继续按序组合。重复相同的过程，直到遍历全部键值信息（例如数值最低位），待排记录R即有序。
1.7.2 时间复杂度
基数排序的时间复杂度和待排记录长度n、采用的键值部分信息（简称关键码d）以及d取值范围r有关，复杂度为O(d(n+r))。空间复
1.7.3 空间复杂度和稳定性
基数排序需要和待排记录R等大的辅助空间来存储原始排序记录，另外仍然需要rd个空间来辅助计数排序的过程。空间复杂度为O(rd+n)，保持了原序列相同元素的顺序，是稳定的排序过程。
2 实验与结果
本实验使用一台装配32位Win7系统，4G内存，core i5CPU的电脑，在Eclipse开发环境下进行。为了验证基本数据类型、数据泛型封装和代码实现（泛型）对算法的影响，实验首先采用正序和逆序的int型序列对算法进行测试，而后调用Java里面的随机函数生成随机待排序列进行实验。
2.1 算法性能测试
为了测试算法实际运行效率实验选取1000-50000间隔为1000的49组正序、逆序、随机的int类型数据进行5轮测试，计算每种算法的时间消耗平均值，绘制得到图1正序序列排序时间消耗图、图2逆序序列排序时间消耗图和图3随机序列排序时间消耗图。
对比3组实验对比折线图，可以看出各个排序算法实际效率和理论分析基本一致。BubbleSort、InsertSort和ShellSort表现出了对序列顺序的敏感性。HeapSort和MergeSort时间消耗比理论要高，甚至在逆序下耗时超过BubbleSort，其原因在于算法实现过程中引入了过多的条件判定操作、分配内存操作以及寻址操作，这些操作增加了算法的复杂度，致使程序本身的复杂度增大。至于HeapSort和BubbleSort效率相当，与序列是随机序列以及HeapSort操作破环了堆的随机性[8]存在关系。
2.2 测试序列数据类型对排序影响
为了观察基本数据类型是否影响算法效率，实验分别选取1000-50000间隔为1000的49组正序、逆序、随机的int、double基本数据类型数据进行5轮测试，计算每种算法的时间消耗平均值，得到表1实验结果。
算法的性能稳定性指的是随着数据规模的改变，时间消耗是否稳定变化，表现为时间消耗折线图的走势是否平滑。根据实验结果显示，BubbleSort、QuickSort和InsertSort性能稳定，其余算法稳定性较差。
基本数据类型影响着排序算法的效率，排序相同规模下的浮点型数据和整形数据，浮点型数据消耗略大于整形数据。
2.3 Java内部封装类对排序算法的影响
为了测试Java内部封装类[9]对排序算法的影响，实验同样进行了5次。每轮实验仍然调用Java随机函数生成50组范围1000-51000间隔为1000的实验数据，类型为Integer、int、Double和double，测试明确指定数据类型的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表2的实验结果。
根据表2中实验数据，可以看出Java内部的封装数据类型对排序算法存在影响，程度因算法而异。InsertSort和Radix Sort受影响较大，封装数据类型和基本类型时间消耗比例达到了4:1,MergeSort受影响最小，浮点类型封装数据Double排序效率超过了基本数据类型double，产生这种现象的原因和Jav对象的存储机制和内存的分配方式有关。总结起来就一般情况而言，封装数据类型会加大排序算法的开销，时间开销是基本数据类型的1.2到4倍。
2.4 泛型编程方式对排序算法影响
为了测试采用泛型[7]方式编写程序对排序算法效率影响，实验进行了5轮重复测试。每轮实验调用随机函数生成50组范围1000-51000间隔为1000的实验数据，数据类型为Inte ger和Double，测试采用泛型方式和非泛型方式编写的7种排序算法。而后，计算5轮实验时间消耗的平均值，得到表3的实验结果
根据表2的实验结果，可以得到采用泛型编写方式对算法效率存在影响，影响程度依据算法的不同存在差异。Insert Sort和HeapSort影响程度较大，MergeSort基本不受影响，产生这种差距的原因和Java自身的运行机制存在一定的关系。总体来说，采用泛型编程方式会加大排序算法的时间开销，约为非泛型编程的1.5-2.4倍。
3 结果分析
通过以上的实验结果，可以得出如下结论：
(1）排序算法的效率在很大程度上由算法的思想决定。
(2）算法的实际运行效率也依赖于书写代码的复杂度以及采用的基本操作类型等外界因素。
(3）排序算法效率和基本类型有关，排序相同排序规模的浮点型数据比整形数据耗时。
(4）使用Java内部封装类会影响排序算法效率，排序相同规模数据的时间消耗增加0.2-3倍。
(5）采用泛型方式编写程序会增加排序算法的时间消耗，为非泛型方式的1.5-2.4倍。
(6）根据实验数据显示，综合多种因素的影响，QuickSor和ShellSort表现出良好运行效率，符合[8]中的描述。
4 结语
排序算法的效率是由多种因素决定的，本实验验证了排序记录数据类型、数据封装以及代码的编写方式对排序算法的影响。但是影响算法效率的因素还有很多，在选择排序算法时应该综合考虑各种因素，以便做出最合理选择。
摘要：排序是计算机科学领域的一个基本问题。从算法时间复杂度、空间复杂度和稳定性的角度对常见的7种内部数值排序算法进行了理论分析。在Java平台下测试了7种算法的执行效率,指出了算法的执行效率不仅和算法设计思想相关,基本数据类型、数据封装,以及代码实现方式都影响算法的执行效率。同时进行了实验对比数据,为排序算法的选择提供一定的参考。
关键词：内部排序算法,效率,数据类型,数据封装
参考文献
[1]Dongarra J.The top 10 algorithms[J].IEEE Computing in Science&Engineering,2000,2(1):22-23.
[2]江燕,周军,等.内部排序算法的表分析[J].电脑编程计数与维护,2014,12:23-24.
[3]吴伟娜,等.常用排序算法的比较分析[J].电脑知识与技术,2013,03:2416-2147.
[4]张静.常用的排序算法的分析与比较[J].河西学院学报,2010,02:26.
[5]淦艳,等.五种排序算法的性能分析[J].重庆文理学院学报,2016,06:45-50.
[6]杨智明.希尔算法实现与分析[J].软件与开发,2010,02:13-14.
[7]Joshua Bloch.Effective Java[M].北京.机械工业出版社,2009:97-102.
[8]Mark Allen Weiss.数据结构与算法分析:Java语言描述[M].北京.机械工业出版社,2008:77-125,183-219.
图像放大算法比较研究 篇7
图像放大是图像处理的基本操作之一,它广泛应用于医学图像、遥感图像、网页制作以及一些商用图像处理软件中。图像放大即将一幅低分辨率的图像转换为高分辨率图像的一种图像处理技术,对一幅图像进行放大,实质上是对图像插值的过程。图像放大目前已经有了很多实用化的方法,它们有各自的特点、优点和不足。图像放大算法的选择直接影响到放大图像的质量,所以寻找合适的算法是提高放大图像质量的关键。目前主要的图像放大方法大致可以分为两类[1]:第一类是常规插值,包括最临近点插值、双线性插值、拉格朗日插值及三次样条插值等,这类方法是根据离散的点建立一个连续函数,用这个重建的函数求出任意位置处的函数值。第二类是利用图像中包含不同的高、低频成分的特点,经过对图像的数学统计特征的分析,采用不同的方式对图像不同部分进行插值的非线性的、移变的插值方法。
1 常规插值算法
1.1 最邻近点插值算法
最临近点插值是最简便的插值算法,它以插值像素点周围离最近的己知像素的灰度值作为插值像素点的灰度值,所以又称为像素复写或零阶保持插值。
如图1所示,设(i,j),(i,j+1),(i+1,j),(i+1,j+1)是灰度插值前的一个四点邻域,其灰度值分别为g(i,j),g(i,j+1),g(i+1,j),g(i+1,j+1)。
最近领域法是比较(u,v)点和(i,j),(i,j+1),(i+1,j),(i+1,j+1)四点之间的距离,然后以与(u,v)点最近的那点的灰度值作为(u,v)点的灰度值[2]。将两点之间的距离记为D[(u,v),(i,j)],则上述四点与(u,v)点最近距离可由下式求得:
求得与(u,v)点距离最近的点(i′,j′)后,由最近邻域法确定(u,v)点的灰度为:
最近邻插值运算简单快速,能够保持插值图像边缘清晰,但边缘轮廓有显著的锯齿现象,图像背景产生马赛克,形成伪边缘,视觉效果差,重构误差较大。
1.2 双线性插值算法
作为对最近邻点法的一种改进,双线性插值算法是“利用周围4个邻点的灰度值在两个方向上做线性内插以得到待采样点的灰度值”,即根据待采样点与相邻点的距离确定相应的权值计算出待采样点的灰度值。其数学表达式为:
图2是双线性插值算法的示意图[3],在图中点(i+u,j+v)为待插值点,点f(i,j),f(i,j+1),f(i+1,j),f(i+1,j+1)是灰度值已知的近邻像素点。先计算A,B两点的灰度值,分别记为f(A),f(B)。则有f(A)=uf(i,j)+(1-u)f(i,j+1),f(B)=vf(i+1,j)+(1-v)f(i+1,j+1)。然后再计算出待插值点的灰度值:
与最邻近法相比,双线性内插法由于考虑了待采样点周围4个直接邻点对待采样点的影响,因此基本克服了前者灰度不连续的缺点,其计算量有所增大。此方法仅考虑4个直接邻点灰度值的影响,而未考虑到各邻点间灰度值变化率的影响,因此具有低通滤波器的性质,使放大后图像的高频分量受到损失,图像的轮廓变得较模糊。
1.3 双三次插值算法
双三次插值是高阶插值算法中常用的方法,它对周围邻近的16个像素点进行插值计算(如图3所示)。这种图像插值算法的优点是可以消除锯齿现象,插值质量高, 效果好,与前面两种方法比较边缘阶梯失真现象得到很大程度的抑制,但放大时边缘模糊现象比较严重。该算法的另一不足之处是计算量大,运算时间长,在需要实时性较高的场合很难实现[4]。
双立方插值算法与双线性插值算法相比,不仅扩大了影响点的范围,还采用了高级的插值算法。双立方插值能够得到较清晰的画面质量,不过计算量也变大。该算法在现在众多的图像处理软件中最为常用,比如Photoshop,After Effects,Avid等。
1.4 三次B样条插值算法
线性插值算法虽然已经考虑了事物之间的连续性,但许多时候,数据之间并不满足线性关系为了进一步改善插值效果,高次插值的思想虽之被引入,三次样条(cubic convolution)插值就是其中的一种,而三次样条插值中应用最多的又是三次B样条插值[5]。
n+1阶B样条插值为[4]:
从计算时间上考虑,次数越低,计算越快,但一次和二次B 样条插值会使图像产生BLOCK 现象,效果不太理想,而三次B 样条基本上可以两者兼顾;在此基础上,又有人引入斜投影算子,都达到了很好的效果。B样条处理的最大优势是将对图像的处理(离散) 转化在连续函数域(样条域)[6] 。
三阶B样条函数如下:
利用它插值放大的图像较为平滑,无明显的锯齿现象。同时可以通过快速算法极大地缩短运算时间。采用该方法对于彩色图象放大时,必须解决图像出现色偏差,边缘细节保持不足够好的问题。
基于三次B样条函数的插值算法,在插值过程中均表现为低通滤波器,在不同程度上抑制了高频成分,当放大倍数较高时,会造成边缘层次模糊和虚假的人工痕迹(锯齿状条纹和方块效应等)。
近年来,随着非线性科学理论的蓬勃发展,小波变换、分形等非线性处理手段亦被应用到图像放缩领域,取得了一些不错的成果,但同时计算复杂度也大大增加。
2 自适应插值算法
现在的自适应插值算法有很多,主要有线性空不变图像插值、距离加偏差图像插值等,目前最新的自适应插值技术还有双信道插值、分形插值、小波插值、定向插值、偏微分方程插值和有理插值等。
2.1 分形插值
分形插值放大主要的物理性依据是“自相似性”,这是分形的基本特征,它反映了自然界中广泛存在的一种现象:(事物)局部与局部、局部与整体在形态、功能、时空等方面具有统计意义上的相似性。一些自然景物,如蓝天、云彩、烟柱和火焰等,图像具有高度的自相似性。分形插值反映了这种自相似性,因而分形插值在计算机视觉技术中有广泛的应用[7]。分形技术用于图像放大有很多优点,如可“较好保留图像的纹理特征,获得高分辨率图像,而对于曲线的插值计算则其有很高的保形性”,“可以主生高分辨率图像,而能保持原图像的纹理特征”。所以有不少学者研究分形放大于静态图像,医学CT图像等方面的作用。分形分为规则分形和随机分形。规则分形是基于某一种函数或规则,按照一定的约定或法则,进行迭代形成。随机分形的构成原则是随机的,更好地描述了自然现象。随机分形的典型数学模型是分数布朗 (Brown)运动,能充分反映图像的统计纹理特性[8]。分形放大的步骤一般可概括为[9]:
(1) 将原图分割为若干子图;
(2) 选择IFS算法,对每一个子图进行运算,提取IFS代码(或称分形参数、特征值等;
(3) 选择重构算法,根据IFS代码,在原图基础上进行分形插值。
(4) 合并新构造的子图,完毕。
2.2 小波插值
小波插值充分利用了图像奇异特征沿小波分解尺度的传播性,能够更准确地重建出高分辨率图像细节。但由于小波系数奇异值的定位涉及精确复杂的边缘检测且小波系数很难跨尺度对准,使得算法实现十分复杂。基于小波插值的算法主要有两种,分别为子带插值和极值外推插值。小波变换本质上是用小波函数作为带通滤波器进行滤波,将原始信号分解为一系列频带上的信号由小波函数簇定义小波变换为:
而小波逆变换则是从分解到各频带的信号进行原始信号的重构:
式中:
子带插值的思想是将原始图像逐级向下拆分成不同分辨率的子图像作为原始图像的小波变换的结果。小波变换用小波函数作为带通滤波器将图像分解为一系列频带上的子图。相应分辨率下3个方向的细节子图分别反映这3个方向上图像的边沿特性,高分辨率下的边沿特性相似于低分辨率下的边沿特性,子带插值算法利用了图像细节沿小波分解尺度的相似性,插值结果的细节清晰。但是,由于采用的相似变换比较粗略,图像插值精度较低。相对于子带插值,极值外推插值采用了更加精确的沿尺度近似变换。它通过考察信号的小波变换系数的极值点的位置和大小沿几个较大尺度的变化,推测出更高分辨率图像的小波变换极值点的位置和大小,从而得到比较精确的更小尺度下的小波分解系数[10]。
2.3 偏微分方程插值
在图像处理和计算机视觉中采用PDE(偏微分方程)方法是近十几年发展起来的一个新的研究方向,显示出了强大的生命力,并成为信息科学中相对独立的一个分支。偏微分方程插值引入总变分最小原则,使插值像素
基于偏微分理论实现图像放大的算法根据扩散填补放大后图像对应像素值的着眼点不同,可以分为两类:一类是以线性扩散PDE模型为基础,另一类是以非线性扩散PDE模型为基础。所谓线性扩散模型,就是扩散机制不考虑图像自身的特点,扩散填补放大后图像对应像素的扩散过程中,扩散系数、扩散强度及扩散速度均在图像的放大过程中始终相同。基于非线性PDE模型的图像放大注重图像的内在本质,分析图像像素点之间的关系,考虑图像拍摄的形成机制和图像的自身内容(如边缘梯度变换较强、等照度线应该足够光顺等),认为放大图像中的待填补像素的值应该根据其周围的像素信息延伸得到[11]。 线性PDE放大方法具有很多优越的数学性质,在放大图像的同时能够平滑噪声,并且保证放大图像不会出现明显的斑点以及亮暗区域偏移现象。但由于其采用高斯热扩散,造成了放大后图像中物体的边缘不够清晰、图像整体看起来过度光滑和亮度不够等视觉缺陷。非线性PDE放大方法在平坦区域有自然的过渡,比较光滑;在边界处有突变,边缘清晰;不会出现明显的斑点、亮暗区域偏移现象;放大后的图像整体看起来比较清晰、明亮。 总的来说,非线性PDE放大方法克服了线性PDE图像放大方法的缺陷,具有更加优秀的放大效果。
2.4 邻域交换内插算法
邻域交换内插法于1990年天津大学的王兆华等人提出。邻域内插法通过交换上下左右像素的较好地解决了屏幕显示中的马赛克效应,也减少了图像模糊。但是由于它是在每一方块中的一部分像素和相邻的上下左右的方块中的一部分像素交换位置,利用人眼的低通滤波特性将相邻像素平均,产生内插效果。但是,它会引起如同点噪声的灰度跃变点。这些灰度跃变点在图像和文本的边缘,由于人眼的视觉效应,显得尤为刺眼。另一方面,该交换算法对笔画单薄的线条、文字,特别是只有单个像素宽或高的线条和文字的显示尤其不利,会产生像素混叠。邻域交换内插法的想法很简单,如图4所示。
图4(d)为原图,有9个像素。图4(e)内带箭头的方框代表交换框内两像素位置的意思。图4(a)是把原图4(d)用重复放大的方法放大4×4倍的结果。现在先考察位于中央的像素块“e”,在图4(a)中已经用虚线框起,在上、下、左、右4个方向把像素“e”与相邻的像素进行交换,即“e”分别与b,h,d,f进行交换,如图4(b)所示。其结果如图4(c)所示。显然图4(c)中的像素块“e”已经没了在图4(a)中那四方的棱角,克服了方块效应。邻域交换内插法是通过交换算子来描述的。邻域交换内插算子有如下几个特征[1]:
(1) 交换算子由“0”和“1”组成;
(2) 如果放大倍数为N×M,则交换算子中“1”的数目等于N×M;
(3) 进行了交换的“1”的数目必然是偶数,而且呈现中心对称性。
邻域交换内插放大算法使每个像素上方的上下左右或对角线上的像素与邻域进行交换,利用人眼的低通滤波特性,将相邻像素平均产生内插效果,从而消除方块效应。它的实现是先插零、再与相应的交换算子卷积。邻域交换放大法会引起如同点噪声的灰度跃变点。利用十字形中值滤波器消除视频信号所携带的点噪声的特性,能消除灰度跃变点,优化邻域交换内插图像放大法。
3 结 语
综上所述,经典插值算法原理基本相同,首先需要找到与输出图像相对应的输入图像点,然后再通过计算该点附近某一像素集合的加权平均值来指定输出像素的灰度值,其他像素都不考虑。对于最近邻插值法来说,输出像素的赋值为当前点的像素点,放大效果较差,其优点就是运算简单;对于双线性插值法来说,输出像素的赋值为其周围4个像素点的值的加权平均,运算比最近邻插值复杂,放大后图像的高频分量受到损失,图像的轮廓变得较模糊;对于双三次插值法来说,输出像素的赋值为其周围16个像素点的值的加权平均,放大效果有一定改善,但运算量较大。对于灰度变化平缓的图像区域,采用常规的插值算法,通常已能达到较好的视觉效果。但是,由于这些插值算法是对观测图像的线性操作,不能拓展图像的有效频率带宽,不能很好地处理图像中剧烈跳变的局部特征,平滑了图像边缘细节信息。导致缩放图像的边缘细节模糊。利用三次B样条插值放大的图像较为平滑,无明显的锯齿现象。同时可以通过快速算法极大地缩短运算时间。采用该方法对于彩色图像放大时,必须解决图像出现色偏差,边缘细节保持不足够好的问题。
自适应图像放大方法通过分析图像局部的频率成分和连续性以调节插值系数,建立局部自适应的空间移变插值算法,从而改善了重建图像的质量;其中分形插值反应了一些事物的自相似性,因而在计算机视觉技术中应用广泛;小波插值充分利用了图像奇异特性沿小波分解尺度的传播性,能够更准确地重建出高分辨率图像细节,但算法实现十分复杂,它是面向全局,更适合于一般多灰度值图像放大[12];PDE算法引入了总变分最小的约束准确描述图像边缘方向,保护了边缘的形态正则性;邻域交换图像放大法使每个像素方块上下左右或对角线上的像素与邻域进行交换,消除了方块效应,它是面向邻域的,对文本放大效果较好[12]。
常规的插值放大与自适应插值放大都有各自的优、缺点,根据被放大图像的特征及放大效果的要求,灵活选择合适的放大方法,以获得最佳的放大效果,是图像放大的一个重要问题。各种图像放大方法也在不断的优化,但都是各有所长,可以通过结合各种算法,达到需要的效果,发挥其优势是一项很有前景的工作。
参考文献
[1]陈冬雪.图像处理技术在大屏幕特种立体电影制作中的应用[D].长春:长春理工大学,2009.
[2]常军.基于图像缩放的新算法研究与应用[D].无锡:江南大学,2008.
[3]张阿珍,刘政林,邹雪城,等.基于双三次插值算法的图像缩放引擎的设计[J].微电子学与计算机,2007,24(1):49-51.
[4]邓海燕.面向超分辨率重建的图像放大与融合方法[D].大连:大连海事大学,2008.
[5]UNSER M,ALDROUBI A,EDEN M.Fast B-spline trans-formfor continuous i mage representation and interpolation[J].IEEE Trans.on Pattern Analysis and Machine Intelli-gence,1991(3):277-285.
[6]杨朝霞,逯峰,关履泰.用B样条的尺度关系来实现图像任意精度的放大缩小[J].计算机辅助设计与图形学学报,2001,13(9):824-827.
[7]杨健君.数字图像放大技术的研究与电视墙图像分配器的研制[D].成都:电子科技大学,2002.
[8]SHEZAF N,ABRAMOV-SEGAL H,SUTSKOVER I,et al.Adaptive low complexity algorithm for i mage zoo-ming at fractional scaling ratio[J].The 21st IEEE Conven-tion of the Electrical and Electronic Engineers.Israel:IEEE,2000:253-256.
[9]尹忠科,杨绍国.分形插值图像放大和压缩编码[J].信号处理,1998,14(1):86-89.
[10]龚奕刚.图像放大算法研究[D].无锡:江南大学,2008.
[11]张慧玉,祝轩,王蕾.基于PDE的图像放大方法研究[J].西安石油大学学报:自然科学版,2009,24(5):79-81.
随机生产模拟算法比较 篇8
随机生产模拟于20世纪60年代末出现, 是电力系统规划工作中的重要工具, 用于模拟发电调度, 预测各发电机组在一段时期内的发电量期望值及燃料消耗量, 同时还可计算出该系统的可靠性指标。
随机生产模拟考虑了发电机组停运、负荷波动等不确定性因素, 很好地描述了电力生产中的随机性。在实际计算中, 有多种算法, 各算法有各自的优点与缺点, 本文将就两类常见的方法介绍对比。
2、随机生产模拟的基本原理
2.1 持续负荷曲线
随机生产模拟是以等效持续负荷曲线为核心的, 各类随机生产模拟的方法都以此为基础发展起来的, 该曲线综合考虑了发电机组的随机停运和负荷随机波动, 将两者结合起来从而形成等效持续负荷曲线。
在引入等效持续负荷曲线之前, 先对持续负荷曲线进行介绍。在得到负荷曲线时, 首先形成持续负荷曲线, 如图1所示的持续负荷曲线, 图中横坐标为系统负荷, 纵坐标为负荷的持续时间, T为模拟周期, 模拟周期根据具体的需要而定, 曲线上任意一点 (x, t) 表示系统负荷大于或等于负荷x的持续时间t, 即t=F (x) 。
用周期T除以上式, 得到
式中P可以看作系统负荷大于或等于x的概率。从而系统总负荷为
相类似的, 式 (2) 除以T, 可以得到负荷的平均值 (又称为期望值)
设系统在模拟周期T内投入运行的发电机总容量为Cs, 由图1得, 系统负荷大于发电机总容量的持续时间为
从而得到电力不足概率LOLP为
而相应的, 系统负荷大于发电机总容量时, 图1中的阴影部分的负荷需求, 从而得到电量不足期望值
2.2 递归卷积法
在实际运行中, 发电机组不完全可靠, 存在着随机停运, 因此, 需要考虑发电机组的随机停运状态, 并对原始持续负荷曲线进行修正, 得到考虑随机停运的等效持续负荷曲线。在修正等效持续负荷曲线时, 引入卷积的概念。式 (1) 为原始的持续负荷曲线f (0) , 设第一台发电机首先带负荷, 其容量为C1, 可用率为p1, 强迫停运率为q1=1-p1。
当该机组处于正常运行状态时, 它和其他发电机组所带的负荷由f (0) (x) 来表示。当机组1故障停运时, 系统负荷将由除去机组1剩下的发电机承担, 相当于机组1和其它发电机组共同承担了的xmax+C1负荷, 即曲线f (0) (x) 向右平移了C1, 即图2[1]中f (0) (x-C1) 曲线。
由于机组1可用率为p1, 强迫停运率为q1, 因此考虑其停运时, 等效持续负荷曲线变为:
同理, 可得到第i台发电机的卷积公式:
式中, Ci为第i台机组的额定容量, pi为第i机组的可用率, qi=1-pi, 为故障停运率。假设系统中有n台发电机, 当所有发电机组全部卷积后, 即可得到最终的等效持续负荷曲线f (n) (x) , 此时最大等效负荷为xmax+Cs, 而如图3[1]所示, 相对应的电量不足期望值和电力不足概率分别为:
3、等效电量函数法
上文阐述了随机生产模拟的基本原理。通过运用卷积法得到等效持续负荷曲线, 但为了保证计算精度, 计算过程需要大量的离散点描述持续负荷曲线, 计算量较大。而下文介绍的等效电量函数法在保证精度的基础上, 能够很好地解决计算量的问题。
3.1 等效电量函数法的基本原理
取机组容量的最大公因子Δx, 将横坐标x轴按Δx分段, 故根据2.2所述电量计算的公式, 可得离散化的电量函数:
式中J=
电力系统负荷的总电量为:
等效电量函数同样是把发电机组停运影响考虑在内的函数, 因此同样需要根据每个机组的可用率来安排其运行。
由2.1已知, 原始持续负荷曲线的概率分布为f (0) (x) , 其对应的电量函数则为E (0) (J) ;故安排完第i-1台发电机组带负荷后得到的等效持续负荷曲线f (i-1) (x) , 所对应的电量函数为E (i-1) (J) 。因此根据 (8) 及 (27) 式, 可得
式中Ki=Ci/Δx。
式 (30) 即为等效电量函数法的卷积计算公式。
同理, 根据 (10) 及 (27) 可得第i台发电机组的发电量为:
式中Ji-1=xi-1/Δx, Ji= (xi-1+Ci) /Δx。
在安排了第i台机组以后, 前i台机组带了区间 (1, Ji) 的负荷, 此时系统尚未满足的负荷电量应为:
式中EDi为前i台机组带负荷后, 系统中尚缺的电量。将式 (30) 代入上式得到:
由 (32) , 可得安排前i-1台机组后尚未满足的系统负荷为
因此 (33) 式中第二项为第i台机组的发电量, 与之前的式 (31) 一致。从而
而系统的电量不足期望值为:
系统的电力不足概率LOLP的计算需要用于2.2中提到的等效持续负荷曲线f (n) (x) 来说明。因为该曲线为单调减小的曲线, 所以LOLP大于其右侧Δx领域内任一点的函数值, 从而也大于该区间内函数f (n) (x) 的平均值, 平均值为:
根据等效电量函数的定义, 上式可以改写为
同理, LOLP小于其左侧Δx领域内任一点的函数值, 从而也小于该区间内, 函数f (n) (x) 的平均值, 故平均值为:
由式 (21) 及 (22) 得到LOLP的上下限:
在很小的区间内, 等效持续负荷曲线可以近似看成线性, 故在用等效电量函数法进行随机生产模拟时, LOLP计算可由下式得到:
4、算例
最后采用IEEEReliabilityTestSystem算例中的数据进行模拟, 机组数为7, 模拟周期为一天 (如表1, 2) 。
等效电量函数法的根据递归卷积法推出的, 将其结果与递归卷积法的对比, 可知, 采用等效电量函数法计算精度上相差不大, 计算得到的各机组发电量都一样, 程序运行时间也较小。因此在进行随机生产模拟时, 采用等效电量函数法比较合适。
5、结语
本文介绍了随机生产模拟的基本原理, 并介绍了两类计算方法, 通过算例比较了它们的优劣。等效电量函数法在计算量和计算精度上都有明显的优势, 因此进行随机生产模拟时, 采用该算法比较合适。
参考文献
[1]王锡凡.电力系统优化规划[M].北京:水利水电出版社, 1990:125-182.
光流算法比较分析研究 篇9
关键词：光流算法,车辆检测,智能交通,计算机视觉
0 引 言
基于视频的运动目标检测的目的就是要在序列图像中将运动目标从场景中提取出来。但是由于光照的影响、风吹、树叶摆动、运动目标阴影、摄像机抖动以及运动目标的遮挡现象给运动目标的正确检测造成了极大的困难。运动目标能否正确检测和分割影响着后续运动目标能否正确跟踪与识别,因此运动目标检测成了计算机视觉中的一项重要课题。传统的运动目标检测方法有光流算法[1,2],帧间差分法[3],背景建模法[4]和运动能量法[5]。背景建模法通过建立背景模型,然后将当前帧中每个像素点与背景模型进行比较来确定背景图像。但是背景往往会随着时间的推移发生变化,需要时刻更新背景图像,需要背景图像自适应的更新。帧间差分法可以适应环境的动态变化,可以实现运动目标的实时检测,但检测出的目标存在空洞严重且不连续。
光流场是指图像灰度模式的表面运动[6],光流是三维运动场在二维图像平面上的投影;研究光流算法是利用图像序列中灰度的时域、空域变化和相关性来确定图像像素的运动矢量,也就是研究图像灰度在时间上变化的大小和方向。研究光流算法的目的就是从图像中得到运动目标的运动矢量。因为光流的计算不需要预先知道场景的信息,不需要在图像中建立起特征之间的对应关系,所以光流计算属于高层次的视觉表述。目前,光流法被广泛地应用于目标检测、跟踪、识别、物体弱运动,步态分析、消除波动性干扰、3D结构恢复以及运动估计等图像处理与模式识别领域,也广泛地应用在智能交通、医疗、导航与制导、海洋、军事和天文等领域。
1 研究现状
光流由Gibson于1950年首先提出,在光流的基本约束方程提出之后得到广泛发展。80年代初期,Horn和Schunck提出建立在光流平滑性假设基础上的使全局能量达到最小化原则的全局光流算法[7],可以得到百分之百的稠密光流场。之后Lucas和Kanade提出了使用局部领域最小二乘法来计算光流的局部光流算法,之后就掀起了光流研究的热潮,提出了很多种方法。根据数学方法和相应理论基础可以将光流算法分为基于梯度的方法、基于区域的方法、基于能量的方法、基于相位的方法和神经动力学法。然而在计算光流的时候,大位移和孔径问题是光流计算的难点,因为从图像灰度的变化不能确定像素的真实运动矢量[8]。
1.1 基于梯度的方法
基于梯度的方法又称为微分法,利用时空梯度函数,使得全局能量泛函达到最小化来计算像素的速度矢量。由于微分法具有强大的数学理论支持,所以得到了广泛研究和应用。常用的代表有Lucas-Kanade局部平滑法[9]、Horn-Schunck全局平滑法[7]、以及Nagel的有向平滑法[10]。Horn-Schunck光流法是在光流基本约束方程的基础上附加了全局平滑假设,使得泛函能量函数达到最小化。Lucas和Kanade使用局部平滑假设,假设一个窗口内的所有像素具有相同的运动矢量。Nagel采用有向平滑约束假设,使用加权Hessian矩阵对梯度进行不同方向上的平滑处理。Black和Anandan提出分段平滑的方法来对多目标进行估计[11]。
微分法假设光流是连续的,再附加一定的约束条件,将光流的计算问题转化成最小化泛函能量的数学极值问题。成熟的数学优化理论为求解光流矢量创造了条件。
1.2 块匹配法
匹配法,也叫区域匹配法,研究的是区域匹配问题,块匹配法认为上一帧中某个区域,在下一帧中会形成对应的模式,块匹配光流定义为相邻两帧中,相应区域块之间产生最佳拟合的位移。假设连续两帧图像f1和f2,对于图像f1中的每个像素点(x,y),以此像素为中心建立一个大小为16×16的相关窗Wc,一般来说16×16大小的块已经可以满足要求了,再围绕图像中对应点(x,y),建立一个图像搜索窗Ws,搜索窗口不能太小也不能太大,可根据最大可能位移的先验知识来确定。相似性度量一般常用像素差平方和(SSD)、平均绝对误差(MAD)以及均方差误差函数(MSE)来进行。可进行各种快速搜索算法如三步搜索法来进行搜索,使得误差函数达最小值的位移就是光流矢量。
1.3 基于能量法的方法
在频率域中设像素点X=(x,y)的速度为V,V=(u,v)T,根据式(1):
进行傅里叶变换,结果如下:
式中δ(⋅)为狄里克利函数。
使用基于能量的方法来计算光流是利用调谐滤波器的输出能量达到最大来计算光流,调谐滤波器是在频域中进行设计的,因而基于能量的方法也叫做基于频率的方法。Heeger等人建立了一个在式(1)和式(2)的基础上,进行局部光流计算的模型[12],成为基于能量法的代表。Heeger在频率空间平面和时空能量上采用最小二乘法拟合来估计光流,使用Gabor滤波器来提取局部能量,Gabor滤波器有多个尺度参数,多个方向,它们是对不同频率和方向的调谐。对于一个简单的平移运动,Gabor滤波器的响应都集中在一个平面上。使式(3)最小化,即可求得光流:
1.4 相位法
相位信息用以计算光流由Fleet和Jepson首次提出[13]。在计算光流的时候图像上的相位信息往往比亮度信息更加可靠。所以利用相位信息获得的光流场更加具有鲁棒性。
将二维图像变换到频率域中,变换如下:
式中n=(sinα,-cosα),α是图像的属性角。
通过带通滤波器,图像的相位为:
式中:ρ为滤波器输出的幅值;为相角。
最后,光流为:
式中:s代表速率;n代表法向单位矢量;为相位梯度。
2 光流的几种计算方法
2.1 HS全局光流算法
Horn-Schunck在光流基本约束方程的基础上,结合光流全局平滑条件,既在相邻像素间光流不会突变,从而解决了孔径问题。其假设光流场同时满足基本方程和全局平滑条件。
全局平滑条件可以用光流矢量梯度平方来表示:
式中:u,v分别是x,y方向上的光流。
这个值越小表示相邻像素间变化越小,光流场越平滑。设ec2为全局平滑表达式为:
光流基本约束方程就是要使得相邻两帧间像素偏差达到最小,设eb2为光流基本约束条件,表达式为:
要求得光流矢量就是要使得ec2和eb2都到达最小,就是要使得式(10)的泛函能量达到最小值。
求解式(10)使得Ehs达到最小值的方法是解欧拉方程,使得Ehs关于u,v的导数为零。采用递归算法最后得到光流值为:
当n=0时就是光流的初始值,这个值影响着光流的收敛速度,当相邻两次迭代后光流值之差小于一个很小的数时,迭代结束,调节λ可以调节平滑约束量的比重。
2.2 LK局部平滑光流算法
局部平滑约束由Lucas和Kanade首次提出,假设图像局部平滑,即假设在一个较小的空间领域Ω上运动矢量保持衡定,通过联立窗口内所有像素,使用最小二乘法估计光流,能得到稀疏光流场,具有较强的鲁棒性。
在一个较小的空间领域Ω上,引入权系数后光流估计误差定义为:
式中:W(x)表示窗口权重函数,窗口中心部分对光流约束的贡献大,权重要高。
通过最小二乘法来求解式(13)可以得到:
但是当ATW2A不可逆的时候,光流场无解。
2.3 BM块匹配光流算法
块匹配光流算法是将视频划分为确定大小的图像子块,每个图像子块中所有像素假设具有相同的位移,也就是说具有相同的光流场,每个图像块只做平移运动,这样只要每个图像子块只要计算一个光流矢量就可以得到整个图像块中的所有像素的运动矢量。当块比较小时,假设图像子块中具有相同的位移是成立的。
2.4 PryLK金字塔光流算法
传统的光流算法只有在小位移的条件下才满足灰度连续性假设,而在大位移下图像灰度将不连续,造成光流估计失败。
为了计算运动目标快速移动情况下的光流,引入了在LK局部平滑光流算法的基础上进行金字塔分层迭代来计算光流场。将图像进行金字塔分层,在金字塔的最上层图像的分辨率最低,这样由最上层开始计算光流值,计算的结果加上上一层的初始值作为下一层的光流初值,再对下一层计算光流场,在除最高层外的其他层进行光流迭代,迭代到最后一层就形成光流矢量。
3 四种光流算法性能分析
通过上述四种光流算法的原理,以路口车辆视频为例,用上述四种光流算法分别进行实验,设计了一个演示界面。实验平台为:VC 6.0,Opencv 1.0,Windows XP,Intel Pentium Dual Cor-e,1.86 GHz(2CPU),1G RAM,测试图像为640×480。实验结果如图1所示。
由图1可知,LK光流算法的计算时间为15 ms,HS光流算法的计算时间为62 ms,PryLK金字塔光流算法的计算时间为15 ms,BM块匹配光流算法的计算时间为16 ms,其中箭头代表光流矢量的方向,横线长度代表光流的大小,通过各种光流算法的计算时间分析可知,HS光流算法消耗的时间最多,PryLK光流算法消耗时间最少,因为HS光流算法是对图像中的每一个像素计算光流场,而PryLK光流算法是对特征点计算金字塔光流场。
各种算法满足实时性要求只是最基本的要求,关键是比较车辆检测的效果,通过观察图1可以得到如下结论:BM块匹配、HS光流算法都有较大的干扰,因为HS光流算法是全局光流算法,对噪声比较敏感,但却能得到稠密的光流场。LK和PryLK光流算法对噪声具有一定的鲁棒性,但只能得到稀疏的光流场,在实验中通过光流场的计算可以得到运动矢量,包括运动速度和运动方向,所以说根据光流算法来进行车辆检测可以得到车辆的速度与方向,这是其他车辆检测技术不可比拟的。利用光流的方向可以在路口进行逆行检测,利用光流速度可以对车辆超速违章进行检测。
4 光流技术的研究方向
光流算法可以得到运动点的速度和方向,通过光流场的分析可以得知光流技术的研究方向有如下几点:
(1)通过光流算法得到全局光流场,对光流场进行聚类分析,检测运动物体。
(2)可以通过分析光流场,解决由于相机抖动,或则树叶的摆动等引起的波动式干扰,因为这些波动式干扰造成光流矢量呈现周期性变化的趋势。
(3)通过光流预测进行运动目标的跟踪。
(4)光流法可以得到亚像素级的运动矢量,可以用光流技术进行步态分析。
(5)由于光流法是计算物体间的相对运动,所以可以用光流技术来实现动态背景下的目标检测与跟踪。
三维重建算法及分析比较 篇10
1 三维重建算法概述
三维重建属于一种技术难点[2], 但其应用价值高、应用广泛, 因而受到广泛重视。在实际应用中, 越是结构复杂的实体造型, 其对于工程技术人员的素质和技能要求越为严格, 因而, 更加深入的二、三维转换算法还在进一步探索和研究之中, 而建立这一算法的应用软件较常用的为AutoCAD。
目前三维重建算法主要包含自顶而下和自底而上两种, 它们各有优劣, 主要根据不同应用情况选用。而在具体识别时, 必须吸取国际最先进的研究成果, 并取众家所长, 综合利用, 以实现高度自动化的数据识别[3]。概述部分笔者分别简述自底而上、利用语义信息辅助、基于体切削、基于专家系统等几种重构方法。
自底而上重构是目前较为主流的一种算法模式。其主要基于从三视图的顶点进行初始化分析的思想, 自底部向上方逐次完成三维模型的构建, 步骤为先顶点、再边线、而后立面……该算法的优势在于适应性较强, 能够较准确的识别出平面、圆柱圆锥面、圆环面、球面等;劣势在于搜索空间相对较宽泛, 运算的时间较长, 空间的复杂程度也比较大, 难以操作和保证工时。
利用语义信息辅助重构算法, 是从识别图形当中标注信息入手, 利用标注信息的相关内容指导对子物体的准确识别;该方法仅为辅助性操作, 其对螺栓、螺孔等的运算和识别较为迅速, 但在重构时主要的三维部件仍需依靠其它方法进行。
基于专家系统重构是指通过三维模型进行机械制图, 也就是通过二维图片转换成为正交二维三视图的逆过程。机械制图必须经过一系列具有规范性的指导标准才能准确完成, 因而在操作过程中必须首先识别所有相关规则, 并进行对应的数学描述;其次, 要全面熟悉和深入掌握机械识图的方法与规律。与重构相关的程序人员只有准确的识别图形, 才能够进一步指导整个程序进行有序化识别。所谓基于专家系统, 就是利用这些规则来建立起规则库, 将三视图中的点、线、面等要素作为资料输入到数据库中, 从而达到利用推理方法输出准确三维模型的目的。
基于体切削重构, 要根据三维视图构建起适当大小的包围盒, 并参照三视图对该包围盒进行持续性的切削, 一直到切削后的三视图与原始模型达到完全一致为止。实际上该算法与模型匹配算法极其相似, 只不过该算法是从最大的模型开始, 但模型匹配算法则是从最小的模型开始。
2 重建模型的检验、存储与输出
三维模型的建立过程相对复杂, 需要保障每一个数据和点、线、面的准确性, 因而在重建过程中最好进行重建检验, 而判断检验结果的准确性, 就是通过三维模型三视图和原本输和的三视图样例进行比较[4]。在设计程序中, 必须具有将三维模型转换成二维图像的模块工具, 来完成对比和检验。当然, 这一方面的技术目前已经较为成熟, 可以直接通过有关算法来完成。而三维模型的表达则相对稍显复杂。
三维模型的表达主要有两种方式, 一为实体模型式, 二为表面模型式。顾名思义, 表面模型即仅用模型边界来进行轮廓性的刻画, 该方法优点在于计算机能够以最快的速度响应和显示, 因而目前多数商用模型都采用此类方法进行存储;而其缺点就在于存储量过大、精确度不够, 对一相应工程机械类加工来说较为困难, 比如较难进行表面模型的数字分析, 而整个存储信息仅由大量的点、线、面组成。实体模型是指将部分简单的图元作为基本构造单位来进行多层次的操作, 同时获得结构相对复杂的模型形式, 相对于表面模型而言, 实体模型的存储量较锁上, 操作更加快捷简便。以后无论模型放大多少倍, 需求哪类精度, 系统都能够根据要求调用出相关指数。实体模型多数情况下仅作为一种概念性模型应用, 其与设计者的理念相适应, 如果想通过电视播放实体模型, 则需于将其转换成表面模型。
目前对于较为复杂的三维实体模型输出尚未形成统一的国际标准规范, 用户可自定义与自己需求相适应的格式进行输出操作。通常情况下较为简便的输出格式为图元, 该类格式化一方面能够较为完整的描绘出三维模型的整体, 另一方面又节省存储空间, 缩短操作时间;但这对计算机的相关浏览软件又提出了相对苛刻的要求, 必须能够对该实体模型的边界能力具有识别性。
3 复杂模型表面重建算法举例与分析比较
多数情况下, 三维重建需要运算的模型表面复杂, 比如岩石、形象物、人物等, 这里举一个重建人体五观的三维操作, 仅供参考。首先要对遇重建人物面部二维表面进行分割, 获取有效的点数据, 并集合在一起[5]。通常情况下, 用户需要根据个人经验来指定数据库相关参数。根据人体面部表情及需进行切割的器官, 首先寻找原始数据进行剪裁, 把最小体数据单独列出, 以减少数据处理的时间和数据量[6]。已经裁剪完成的图像, 使用分割平台提供的各种分割算法来完成预分割操作, 然后再利用数字形态学的相关内容进行结果中小噪声点的运算, 再进行人面部各器官的平滑操作, 使人物表面看起来更生动真实。
利用类似的半自动手工分割方法所获得的数字模型中, 可以较快较准确的获得模型人物的单个器官表面相应点位置信息坐标以及其对应的颜色值。将这些数据统一并形成集合, 存储入表面点集合文件夹中。各个表面点的法向量是通过对表面各点位置信息的相应运算而获得, 而这种法向量的运算将成为整个设计过程中的一个难点, 需要工程技术人员有耐心、有信心。在以上基础上, 就可以通过显卡3D加速功能进行整个人体面部器官三维重建的实 (上接第187页) 时浏览了。
三维重建工作复杂而繁琐, 不仅需要工程技术人员具有足够的耐心与恒心, 还必须具有较强的钻研精神, 要在不断的学习与实践中总结经验, 汲取国内外先进的思想和操作方法, 取众家之长, 从而获得更加准确有效、且简便易懂的运算方法, 来实现二维与三维的快速转换。
摘要：三维模型被广泛应用于机械加工、建筑设计、动画制作等多种领域, 并对据设计图形进行加工建造的工程项目具有十分重要的意义, 这就要求工程技术人员在由二维转换成三维的计算机算法应用时具有熟练性和钻研性。本文简单介绍了三维重建算法的基本情况, 并就复杂物件表面的算法做以举例和分析比较。
关键词：三维重建算法,分析研究,算法比较
参考文献
[1]孔凡树, 王蓓蓓, 贾超.基于等值面拓扑简化的三维重建算法[J].燕山大学学报, 2009, 33 (2) :120-123.
[2]诸葛斌.基于数字人彩色图像的三维重建算法研究[J].计算机工程与应用, 2008, 44 (2) :109-110.
[3]荆海龙, 苏显渝, 刘元坤, 伍凡.基于条纹反射的镜面测量及三维重建算法分析[J].光电工程, 2008, 35 (10) :37-39.
[4]李晓, 朱鹏飞.浅析三维重建算法[J].计算机工程应用技术, 2009, 5 (16) :4299-5301.
[5]谷月霞, 张维忠, 王晓燕, 油世明, 王静.基于未标定图像的三维重建算法, 2010, 36 (8) :214-217.
【算法比较】推荐阅读：
两种算法比较05-27
常用加密算法比较研究07-23
在社会比较和时间比较中的自我认识09-26
扩展算法07-16
蝶形算法07-18
区间算法07-18
搜索算法07-19
矩阵算法05-13
回归算法05-15