基于压缩型EKF的SLAM改进算法
第21卷第18期 系
统 仿 真 学 报? V ol. 21 No. 18
2009年9月 Journal of System Simulation Sep., 2009
基于压缩型EKF 的SLAM 改进算法
张海强，窦丽华，方 浩，陈 杰
(北京理工大学信息科学与技术学院自动控制系，北京 100081)
摘 要：针对基于压缩型扩展卡尔曼滤波(CEKF)的SLAM 算法在状态增广和地图管理两方面的不
足，提出了一种改进算法(ICEKF 算法)。该算法通过增广辅助系数矩阵即可快速完成状态增广，计算复杂度由O(N 2)降低为O(N A )，其中N 和N A 分别为全局和局部地图中的路标数。在地图管理上，ICEKF 算法采用一种基于欧氏距离的局部地图动态选择方法，避免了CEKF 算法对全局地图进行预先划分带来的路标分配等问题。仿真表明ICEKF 算法在估计结果上与EKF 算法具有一致的最优性，与CEKF 算法相比计算量大大降低。
关键词：同步定位和地图创建(SLAM)；压缩型扩展卡尔曼滤波；状态增广；计算复杂度 中图分类号：TP242 文献标识码：A 文章编号：1004-731X (2009) 18-5668-04
Improved SLAM Algorithm Based on Compressed-EKF
ZHANG Hai-qiang, DOU Li-hua, F ANG Hao, CHEN Jie
(Department of Automatic Control, School of Information Science and Technology, Beijing Institute of Technology, Beijing 100081, China)
Abstract: The compressed extended Kalman filter(CEKF)-based algorithm for simultaneous localization and mapping (SLAM) has low efficiency on state augment and map management. An improved algorithm (ICEKF) was proposed. The ICEKF algorithm achieves the state augment by only augmenting one auxiliary coefficient matrix, and the computational complexity is reduced from O(N 2) to O(N A ), where N and N A denote the number of the landmarks in the global and local maps respectively. A Euclidian distance-based method for map management was presented which selects the local map dynamically . In this way, the landmarks assignment and other problems issued from dividing the global map before the SLAM starts as in the CEKF algorithm were avoided. Simulations show that the ICEKF algorithm obtaines the same optimal results as the EKF algorithm, and its computational cost is greatly reduced in comparion with the CEKF algorithm.
Key words: simultaneous localization and mapping (SLAM); compressed extended Kalman filter; state augment; computational complexity
引 言
同步定位和地图创建(SLAM)是指移动机器人在未知环境中从未知位置出发，通过适当的控制策略在环境中运动并观察环境，逐步建立起周围环境的地图并确定自身在当前环境中的位姿[1]。SLAM 是移动机器人真正具备自主性的关键因素，因此成为目前移动机器人领域的研究热点[2,3]。
基于扩展卡尔曼滤波的SLAM 算法[4]是一种经典方法，虽然该方法计算复杂度高且无法处理“闭环”问题，但其收敛性是目前所有算法中最好的[5,6]，因此至今仍在陆地、水下及空中等场合得到广泛的应用。为了提高EKF-SLAM 算法的实时性，众多学者提出各种优化或保守的方法，中心思想是将SLAM 问题重新形式化或者在估计效果与实时性之间进行折中，例如解耦随机地图、局部地图序列法、稀疏扩展信息滤波器、相对路标表示等。其中，Guivant 等研究了如何利用SLAM 问题中矩阵的稀疏性、感知范围有限性等约束来降低计算复杂度，并提出一系列基于压缩型扩展卡尔曼滤波(CEKF)的算法[7-9]。CEKF 算法可以得到与EKF 算法相同的估计结果，而当移动机器人工作在某一局部区域内
收稿日期：2008-04-15 修回日期：2008-6-18
基金项目：北京市教育委员会共建基金 (100070522) 作者简介：张海强(1982-), 男, 山东人, 博士生, 研究方向为移动机器人,同步定位和地图创建, 机器视觉；窦丽华(1961-), 女, 北京人, 博士, 教授, 研究方向为模式识别与人工智能, 智能机器人。
时，计算复杂度仅为2()A O N ，其中A N 为局部地图中的路标数。但是当需要进行全局更新时(例如状态增广、重新划分局部地图等时刻)，CEKF 算法需要进行计算复杂度为2()O N 的运算，其中N 为全局地图中的路标数。
本文针对CEKF 算法中的状态增广方法计算复杂度高或者需要改变滤波公式的初始条件的不足，提出一种快速状态增广方法，计算代价仅为()A O N 且无损估计结果的最优性。此外，提出了一种基于欧氏距离的局部地图动态划分方法，可高效地完成地图管理。
1 SLAM 的描述
假设移动机器人在二维平面上运动，其位姿在全局坐标
系中表示为[,,]v v v v T X x y θ ，起始坐标0
[0,0,0]v
T X =。环境中散布着静态点路标，各个路标由其在全局坐标系中的坐标表示：[,]i i i F F F T X x y 。系统状态向量k X 由两部分组成：
系统当前时刻的机器人位姿估计[,,]v v v v T k k
k k X x y θ=和已被观察到的所有路标的估计构成的集合
12[(),(),,()]N
N F F T F T F T T k k k k X X X X ="，即：
12[(),(),(),,()]N v T F T F T F T T k k k k k X X X X X " (1)
因此需要估计的变量为k X 及其协方差矩阵k P 。假设
()T
k k P P =，初始状态000v
X X ==，00
00
0v v
X X P P ==。此外，
移动机器人的运动模型记为：1()v v k k X f X + ，其外部传感器
2009年9月 张海强，等：基于压缩型EKF 的SLAM 改进算法 Sep., 2009
的观测模型记为：(,)i i F v F k k z h X X =。
2 CEKF-SLAM 算法
由于外部传感器的观测距离是有限的，因此当移动机器人在某一局部区域内运动时，只会观测到该区域内部和附近的路标，而不会观测到远处的路标。据此，CEKF-SLAM 算法将系统状态向量k X 划分为两部分[() ()]A T B T T k k X X ，其中A
k
X 中包含v k
X 和当前局部地图中的路标，B k
X 由其余的路标
组成。
当移动机器人在当前局部区域内运动时，在k 到
(0)k t t +≥的每个时间步上对A X 和A
P 的估计按照常规
EKF 方法进行，同时递推地计算辅助系数矩阵,ΦΩΨ和：
()()()(1)()(I ),A k t k t k t k t k J I ζ++++?Φ=???ΦΦ=且 (2)
()(1)(1)()()()(1)()()() ,0T A T
k t k t k t k t A k t k t k t k J J κ++?+?++++?Ω=Ω+Φ??
??ΦΩ=且 (3)
()(1)(1)()1()
()()()()() (),0T A T k t k t k t k t A T k t k t k t k J H ?υ++?+?+?+++Ψ=Ψ+Φ??
??Ψ=且 (4) 其中()A k i J +和()A
k i H +分别是k i +时刻运动模型和观测模型的
雅可比矩阵，()k i υ+是k i +时刻的新息，()k i R +是k i +时刻
的观测噪声协方差矩阵，
T
()()(|1)()()()A AA A k i k i k i k i k i k i H P H R ?++++?++=??+， 1()()()()()()A T A k i k i k i k i H H κ??++++=??，
()(|1)()AA k i k i k i k i P ζκ+++?+=?。
如果在k t +时刻需要进行全局状态更新，则可按照式(5)~(7)利用辅助系数矩阵()k t +Φ、()k t +Ω和()k t +Ψ一次性地将
(|)(|),B AB k k k k X P 和(|)BB
k k P 更新为k t +时刻的估计：
(|)(|)(|)()(|)()BB BB AB T AB
k t k t k k k k k t k k P P P P +++=??Ω? (5) (|)
(|)
(|)()()B
B AB T k t k t k k k k k t X
X
P
+++=+?Ψ (6)
(|)()(|)AB AB k t k t k t k k P P +++=Φ? (7) 由此可见，如果移动机器人在当前局部区域内运动(即对系统状态向量的划分不变)且没有观察到新的路标时，
CEKF-SLAM 算法把,,BB B AB P X P 三项的更新信息压缩进了三个易于计算的辅助系数矩阵中，从而大大地降低了计算复
杂度；而当需要进行全局状态更新时，只需要一次计算量为2()O N 的运算即可完成。
为了使CEKF-SLAM 算法得到与EKF-SLAM 算法一致的最优估计，必须采用可靠的地图管理方法完成局部地图的划分并决定是否需要重新划分，以保证移动机器人不会观测到B X 中的路标。在CEKF-SLAM 算法中，地图管理采用一种预先划分的方式，即在SLAM 过程开始前将全局地图固定划分为合适大小的方格阵列，机器人所在的方格区域及其邻接方格构成当前的局部地图。因此该地图管理方法需要额外的策略来防止机器人在方格边界往返运动导致的频繁局部地图切换，并且需要随时为每个方格维护一个列表来记录
其内部的路标，即路标分配。
另外一个CEKF-SLAM 算法面临的问题发生在机器人观察到一个新路标时，此时不可避免地需要将新路标加入到系统状态X 和P 中，即进行状态增广。通常状态增广通过首先进行一次全局更新，然后进行增广实现，两个步骤的计算复杂度分别为2()O N 和()O N ，随着地图中路标数目的增加，状态增广将逐渐成为CEKF-SLAM 实时性的瓶颈。
3 CEKF-SLAM 算法的改进
3.1 快速状态增广
为降低状态增广的计算复杂度，在ICEKF-SLAM 中我们证明并采用一种新的状态增广的方法。定理1给出了只有一个新路标情况下的快速状态增广方法，如果同时观测到多个新路标，可按照定理1逐个进行增广。
定理1：假设在k i +时刻移动机器人观测到了一个新路标new X ，则在更新得到(|)(|),A A
k i k i k i k i X P ++++以及辅助系数矩阵()()(),,k i k i k i +++ΦΩΨ后，通过对(|)(|),A A
k i k i k i k i X P ++++进行状态增广 并将()k i +Φ增广为()()(1:3,:)k i v k i G ++Φ?????Φ???
?即可完成状态增广，该方 法不损失任何关于新路标的信息，且保持后续对,B B X P 及辅助系数矩阵的递推计算形式不变，其计算复杂度仅为
()A O N 。其中(|)
new
v v k i k i X G X ++?=?，()
(1:3,:)
k i +Φ为()k i +Φ的前3行
元素，A N 为当前局部地图中的路标数。
证明：首先，按照常规状态增广的方法得到在k i +时
刻增广后的系统状态变量k i X +HJ G
和k i P +H G ：
(|)
(|)
(|)(|)()A k i k i new
k i k i k k k k k i X X
X X P +++++????
??=??+?Ψ????
I
(8) ()(|)T (|)1
()(|)
1
23
T
T (|)()3(|)(|)()(|)X k i k i AA AB k i k i k i k k BA BB BA AB k k k i k k k k k i k k P P P P P P P P P P P P +++++++??
Φ??
?
??=??
???Φ??Ω???
I (9) 其中:
1(|)
(1:3,:)AA
v k i k i P G P ++=?；
T
T
2(|)
()v
X v k i k i v z k i z P G P
G G R G +++=??+??，new
z X G z
?=?；
3()
(|)(1:3,:)
AB v k i k k P G P +=?Φ?。
将状态增广后的A X 记作：[() ()]A A T new T T X X X =I
，则
(|)1(|)
12AA T
k i k i AA
k i k i P P P
P P ++++??=?
???
I I
， ()(|)(|)
3AB
k i k k AB
k i k i P P
P +++??Φ?=????
I
2009年9月 系 统 仿
真 学 报 Sep., 2009
而,B B X P 在状态增广前后保持不变。
然后，经过一个时间步到达1k i ++时刻，按照常规EKF 方法可以得到(1|1)
A
k i k i X ++++I 和(1|1)
AA
k i k i P
++++I I ，对(1|1)
AB
k i k i P
++++I
经推导
可知：
(1|1)
()(1)(1)(|)()(1:3,:)(1)(|)
()AB
k i k i k i A AB
k i k i k k v k i AB
k i k k P
I J P G P ζ++++++++++++=
Φ?
??????
??Φ????
Φ?I
I (10)
比较式(10)与式(2)可知，只要将()k i +Φ增广为()()(1:3,:)k i v k i G ++Φ?
????Φ
???
?
即可保持Φ的递推计算形式，同时对AB
P 由k 时刻到1k i ++时刻的更新公式形式不变，而AB P I
中关于新路标的信息将无损地在增广后的Φ中传递。通过推导
(1|1)BB k i k i P ++++、(1|1)B
k i k i X ++++的计算形式可知该结论对Ω和Ψ同
样成立。
因此在k i +时刻的状态增广可通过对(|)
(|)
,A
A
k i k i k i k i X
P
++++进行状态增广、并将()k i +Φ进行上述增广完成。该增广方法既保留了所有关于新路标的信息，又保持了辅助系数矩阵的递推计算形式不受影响，对B X 相关项的更新和增广将通过增广后的辅助系数矩阵完成。
由于()k i +Φ为11M M ×的矩阵，
其中123A M N =+、A N 为局部地图中的路标数目，所以对()k i +Φ的增广需要19M 次乘法运算，其计算复杂度为()A O N 。对,A A X P 进行增广按照常规状态增广进行，由于此时两者已经是更新后的估计，所以增广需要的乘法次数为16M ，其计算量同样为()A O N 。快速状态增广由上述两步完成，因此该快速状态增广的计算复杂度为()A O N 。
证毕
3.2 地图管理
在ICEKF-SLAM 中的地图管理方式更为直观，地图管理负责确定何时进行局部地图的重新划分，并根据局部地图划分原则将X 划分为,A B X X 两部分。
假设传感器的最大观测距离为R ，
如果以某时刻的机器人所在位置O 作为圆心，
将机器人的活动范围限制在半径为1k R ?的圆内(图1中细实线圆)，则在忽略估计不确定性的条件下，传感器不会观测到221(1)k R k k ?≥+范围(粗实线圆)外的路标点，所以2k R ?是活动范围为1k R ?条件下的最小局部地图范围。其中1k 的确定需要考虑可用的计算资源：1k 越大则局部地图的范围越大，在每一步内的计算量随之增加，但是局部地图切换频率随着1k 增大而降低，
从而降低需要进行全局更新的频率。2k 的选择与环境中路标的疏密程度、机器人位姿和路标的不确定性大小有关。较大的2k 导致局部地图内冗余信息的增大、降低压缩效果，但是可以更可靠地保证不观测到局部地图外的路标。
确定12,k k 后，当机器人在当前的1k R ?范围内运动时，局部地图保持不变。当机器人运动到该范围的边界附近(如
O')时，将当前的机器人位置O'作为新局部地图范围的原点，即将机器人活动范围限制在虚细线圆内，局部地图区域更改为粗虚线圆指示的区域。在保持X 不确定性较小的前提下
按照欧氏距离即可重新划分A B X X 、，实现局部地图的重新划分。
图1 局部地图的重新划分
4 仿真实验
为验证ICEKF-SLAM 算法的估计结果和时间性能，构建了一套完整的程序来仿真配有激光传感器的非完整约束移动机器人进行SLAM 的过程。程序以Matlab?为平台，可自由设定环境中的路标数目和分布。通过预先在环境中设置的一系列路点来引导移动机器人逐个经过路点，实现探索路径的规划。由于在仿真环境下可以准确地得到系统状态变量在每个时间步上的真实值，同时对噪声序列具有可控性，因此通过仿真比对ICEKF 与CEKF/EKF 间的估计结果可以排除实验环境下的各种难以测定和消除的系统误差等因素，从而有效地衡量ICEKF 算法的性能。
4.1 模型
在仿真中采用的运动模型是以MobileRobots?公司的Pioneer-3型移动机器人为原型的滑动转向模型，观测模型是
以SICK?LMS200为原型的朝向-距离模型。
其他相关参数，例如控制与观测噪声、数据关联、运动规划等均根据实际设备参数和运行情况设定，通过改变参数可以有效地分析各参数对SLAM 过程的影响。
4.2 仿真结果
图2为某次仿真的结果，图中蓝线表示移动机器人的真实路径，红线表示对机器人路径的估计；星号为路标的真实位置，`+`表示路标位置的估计值，其周围的椭圆表示估计的协方差大小；蓝色的对三角表示真实的机器人位姿，而红色的表示其估计值。移动机器人的当前局部区域为较小的圆覆盖的范围，所有位于大圆内的路标组成当前局部地图。
为验证ICEKF 算法的估计结果与EKF/CEKF 算法的估计结果的一致性，图3对比两种算法在SLAM 过程结束后对路标位置估计的误差，可见两者对环境中路标位置的最终
2009年9月 张海强，等：基于压缩型EKF 的SLAM 改进算法 Sep., 2009
图2 ICEKF-SLAM 仿真结果
图3 估计误差比较
估计值是一致的。对系统状态协方差的最终估计结果的比较给出相同的结论。
为验证ICEKF 算法在各个时间步上的估计结果，对位置在[26.259,2.5962]T
处的路标的位置估计和不确定性估计随时间步的变化进行跟踪(如图4和图5)。由于在开始的一段时间内该路标位于局部地图内，所以对该路标的位置和不确定性估计在每一个时间步上均执行，ICEKF 与EKF 的估计结果是重合的。当该路标不再处于局部地图内时，采用
图4 位置估计的跟踪比较
图5 不确定性估计的跟踪比较
ICEKF 算法对该路标的估计只发生在局部地图切换的时间
步上，因此对该路标的估计呈现阶梯状不连续，在跳变处两种算法给出相同的估计值，所以ICEKF 算法可以保持与EKF 算法一致的估计最优性。
图6对比了CEKF 算法中的常规状态增广方法和ICEKF 算法中的快速状态增广方法的时间性能。在该仿真中共有32次状态增广，图中曲线是多次运行该仿真得到的状态增
广时间的平均值。可见，在开始一段时间内由于路标数目较少，两种方法性能相当；随着路标数目的增加，常规方法的计算代价按照2()O N 上升，而快速状态增广方法则保持()A O N 的计算代价。
图6 时间性能
ICEKF-SLAM 算法中地图管理方法在合理设定系数
12,k k 的情况下其可靠性是显而易见的。由于采用欧氏距离
作为划分准则，因此地图划分可以快速完成。在某次SLAM 过程总时间为33.16秒的仿真中，判断是否需要重新划分局部地图耗时0.195s ，划分操作耗时0.169s ，由此可见该地图管理方式是快速有效的。
5 结论
本文提出了一种基于压缩型扩展卡尔曼滤波(CEKF)的SLAM 改进算法(ICEKF 算法)。首先，针对CEKF 算法进行
状态增广时计算复杂度高或者需要改变滤波初始条件的不足，提出了一种快速状态增广方法，通过对局部状态向量进行增广并增广一个辅助系数矩阵即可无损估计最优性地完成状态增广，其计算复杂度仅与局部地图中的路标数目呈线性关系。其次，ICEKF 算法使用一种基于欧氏距离的局部地图动态划分方法，只利用当前的状态变量进行距离判断即可快速可靠地完成局部地图的重新选择，避免了CEKF 算法对
全局地图进行范围的假设和预先划分带来的路标分配、局部地图切换控制等问题。
构建了一套完整的仿真程序(见https://www.wendangku.net/doc/8b9284294.html, 中的CEKF-SLAM 项目)验证ICEKF 算法的估计结果和时间性能。
仿真结果表明ICEKF 算法在估计结果上与基于EKF 的
SLAM 算法具有相同的估计最优性。由于改进了CEKF 算法
中的状态增广和地图管理方法，因此ICEKF 算法的计算量与CEKF 算法相比大大降低。 x/meter
-20
4030y /m e t e r
20100-10
-10
1020 30
40
10
20 30 40
50 60 70
80
0.7 0.5 0.3 0.1
-0.1 -0.3 -0.5
Landmarks positions index E s t i m a t i o n e r r o r /m e t e r
EKF ICEKF 0
5
10 1520
25
30Time step (×102)
26.36 26.33 26.30 26.27
E s t i m a t i o n o f x /m e t e r
EKF
ICEKF 0
5
10 15 20 25
30
Time step (×102)
1.8
2.02.22.42.6
U n c e r t a i n t y
×10
-2
510
15 20 25 30 35
Landmark index
12
345×10
-4
T i m e /s
Rapid state augment
Regular state augment
EKF
ICEKF
2009年9月系统仿真学报 Sep., 2009
3 结论
本文主要针对三种不同结构的副室，通过二维数值模拟研究了脉冲爆震发动机的起爆过程。研究表明：
(1) 电火花塞的能量不足以直接点燃爆震波，爆震波是在经历了激波与反射激波的相互作用以及激波在传播过程中与火焰阵面的耦合等一系列相互作用后最终形成的。因此在设计点火位置的时候，火花塞要尽可能地靠近壁面和拐角，目的是为了产生高强度的反射激波和横波。
(2) 激波向爆震波转捩(SDT)过程的快慢与副室传入主爆震室的已燃气体的压力和速度大小有直接关系，相同条件下，已燃气体的压力和速度大则形成爆震波的时间短，压力和速度小则形成爆震波的时间长，而传入主爆震室的已燃气体的压力和速度大小又与副室的结构有直接关系，将三种情况下的模拟结果进行对比，得出了SDT时间距离最短的最佳副室结构，即算例1扩张副室。
(3) C-J爆震波的能量大小也与副室的结构有关，由数值模拟结果可知，对于通过SDT过程所形成的爆震波，算例1的爆震波能量最大，即扩张副室的效果最好。
本文对脉冲爆震发动机起爆过程的数值模拟是基于单次循环过程，因此，以上结论适用于单次脉冲爆震循环。
参考文献：
[1] 严传俊, 范玮. 脉冲爆震发动机原理及关键技术[M]. 西安: 西北
工业大学出版社, 2005, 10.
[2] 严传俊, 范玮, 黄希桥, 等. 新概念脉冲爆震发动机的探索性研究
[J]. 自然科学进展, 2002, 12(10): 1021-1025.
[3] 韩启祥, 王家骅, 王波. 预混气爆震管中爆燃到爆震转捩距离的
研究[J]. 推进技术, 2003, 24(1): 63-66.
[4] Cooper M, Jackson S, Austin J, et al. Direct experimental impulse
measurements for detonation and deflagration [J]. Journal of Propulsion and Power (S0748-4658), 2002, 18(5): 1033-1041.
[5] 王福军. 计算流体动力学分析—CFD软件原理与应用[M]. 北京:
清华大学出版社, 2004, 9.
[6] 刘云峰, 余荣国, 王健平. 脉冲爆震发动机快起爆的二维数值模
拟[J]. 推进技术
, 2004, 25(5): 454-457.
(上接第5671页)
参考文献:
[1] M W M Dissanayake G, Newman P, Clark S, et al. A solution to the
simultaneous localization and map building (SLAM) problem [J].
IEEE Transactions on Robotics and Automation (S0018-9286), 2001,
17(3): 229-241.
[2] Durrant-Whyte H, Tim B. Simultaneous localization and mapping:
part I [J]. IEEE Robotics and Automation Magazine (S1070-9932), 2006, 13(2): 99-110.
[3] 鞠纯纯, 何波, 刘保龙, 等. 基于粒子滤波器的SLAM的仿真研
究[J]. 系统仿真学报, 2007, 19(16): 3715-3718. (JU Chun-chun, HE
Bo, LIU Bao-long, et al. Simulation Research on Simultaneous Robot
Localization and Mapping Based on Particle Filter [J]. Journal of System Simulation (S1004-731X), 2007, 19(16): 3715-3718.)
[4] Randall S, Matthew S, Peter C. Estimating Uncertain Spatial
Relationships in Robotics [J]. Uncertainty in Artificial Intelligence (S0218-4885), 1988, 2(8): 435-461. [5] Thrun S. Robotic Mapping: A Survey [R]// School of Computer
Science, Carnegie Mellon University. No. CMU-CS-02-111, 2002.
USA: School of Computer Science, Carnegie Mellon University, 2002.
[6] Shoudong H, Dissanayake G. Convergence and Consistency Analysis
for Extended Kalman Filter Based SLAM [J]. IEEE Transactions on Robotics (S0018-9286), 2007, 23(5): 1036-1049.
[7] Guivant J, Nebot E. Optimization of the Simultaneous Localization
and Map-building Algorithm for Real-time Implementation [J]. IEEE Trans. on Robotics and Automation (S0018-9286), 2001, 17(3): 242-257.
[8] Guivant J. Efficient Simultaneous Localisation and Mapping in Large
Environments [D]. Australia: The University of Sydney, 2002.
[9] Guivant J, Nebot E. Solving computational and memory requirements
of feature-based simultaneous localization and mapping algorithms [J]. IEEE Transactions on Robotics and Automation (S0018-9286),
2003, 19(4): 749-755.
(上接第5676页)
参考文献：
[1] M Stemm, R H Katz. Measuring and Reducing Energy Consumption
of Network Interfaces in Handheld Devices [J]. IEICE Transactions on Communications, Science (S1913-3723), 1997, E80-B(8): 1125-1131.
[2] R Powers. Batteries for Low Power Electronics [C]// Proceedings of
the IEEE. USA: IEEE, 1995, 83(4): 687-693.
[3] Deng Pan, Yuanyuan Yang. FIFO-Based Multicast Scheduling
Algorithm for Virtual Output Queued Packet Switches [J]. IEEE Trans. Computers, Science (S0190-3918), 2005, 54(10): 1283-1297. [4] A Bianco, G Galante, E Leonardi, F Neri, A Nucci. Scheduling
algorithms for multicast service in TDM/WDM networks with arbitrary tuning latencies [J]. Computer Networks, Science (S1389- 1286), 2003, 41(6): 727-742.
[5] H Lin, C Wang. Minimizing the Number of Multicast Transmission in
Single-Hop WDM Networks [C]// IEEE ICC’00, New Orleans, LA, USA, July 2000. USA: IEEE, 2000. [6] Yunnan Wu, Philip A Chou, Sun-Yuan Kung. Minimum-Energy
Multicast in Mobile Ad Hoc Networks Using Network Coding [J].
IEEE Transactions on communications, Science (S0090-6778), 2005, 53(11): 1906-1918.
[7] P Floreen, P Kaski, J Kohonen, P Orponen. Multicast time
maximization in energy-constrained wireless networks [J]. IEEE Journal on Selected Areas in Communications, Science (S0733-8761), 2005, 23(1): 117-126.
[8] R Cohen, R Rizzi. On the trade-off between energy and multicast
efficiency in 802.16e-like mobile networks [C]// IEEE Transaxtions.
USA: IEEE, 2008, 7(3): 346-357.
[9] A Singhal, C Buckley, M Mitra. Pivoted document length
normalization [J]. Research and Development in Information Retrieval, 1996: 21-29.
[10] 胡海波, 王林. 幂率分布研究简史[J]. 西安理工大学学报. 2005,
34(12): 889-896.
[11] 石磊, 卫琳, 古志民等. 利用ZIPF定律建立有效的WEB对象缓存
机制[J]. 计算机工程与应用, 2004, 40(35): 61-63.
最大公约数的三种算法 复杂度分析 时间计算
昆明理工大学信息工程与自动化学院学生实验报告 （2011 —2012 学年第 1 学期） 课程名称：算法设计与分析开课实验室：信自楼机房444 2011 年10月 12日 一、上机目的及内容 1.上机内容 求两个自然数m和n的最大公约数。 2.上机目的 （1）复习数据结构课程的相关知识，实现课程间的平滑过渡； （2）掌握并应用算法的数学分析和后验分析方法； （3）理解这样一个观点：不同的算法能够解决相同的问题，这些算法的解题思路不同，复杂程度不同，解题效率也不同。 二、实验原理及基本技术路线图（方框原理图或程序流程图） （1）至少设计出三个版本的求最大公约数算法； （2）对所设计的算法采用大O符号进行时间复杂性分析； （3）上机实现算法，并用计数法和计时法分别测算算法的运行时间； （4）通过分析对比，得出自己的结论。 三、所用仪器、材料（设备名称、型号、规格等或使用软件） 1台PC及VISUAL C++6.0软件 四、实验方法、步骤（或：程序代码或操作过程） 实验采用三种方法求最大公约数
1、连续整数检测法。 2、欧几里得算法 3、分解质因数算法 根据实现提示写代码并分析代码的时间复杂度： 方法一： int f1(int m,int n) { int t; if(m>n)t=n; else t=m; while(t) { if(m%t==0&&n%t==0)break; else t=t-1; } return t; } 根据代码考虑最坏情况他们的最大公约数是1，循环做了t-1次，最好情况是只做了1次，可以得出O（n）=n/2; 方法二：int f2(int m,int n) { int r; r=m%n; while(r!=0) { m=n; n=r; r=m%n; } return n; } 根据代码辗转相除得到欧几里得的O(n)= log n 方法三： int f3(int m,int n) { int i=2,j=0,h=0; int a[N],b[N],c[N]; while(i 几种视频压缩技术概述 （返回） （一）、JPEG——静止图像压缩标准 1、 JPEG 国际标准化组织（ID）和国际电报电话咨询委员会（CCITT）联合成立的专家组织JPEG （Joint Photographic experts group经过五年艰苦细致地工作后，于是1991年3月 提出了ISO CDIO918号建议草案：多灰度静止图像的数字压缩编码（简称JPEG标准）。 这是一个适用于彩色和单多多灰度或连续色调静止数字图像的压缩标准。它包括基于 DPCM（差分脉冲编码调制）、DCT（离散余弦变换）和Huffman编码的有损压缩算法两个 部分。前者不会产生失真，但压缩比很小；后一种算法进行图像压缩住处虽有损失但压 缩比可以很大，压缩20倍左右时，人眼基本上看不出失真。JPEG标准有三个范畴： A、基本顺序过程Baseline sequential processes实现有损图像压缩。重建图像质量达 到人眼难以实现图像质量达到人眼难以观察出损失的要求。采用8*8像素自适应DCT算 法、量化及H uffman型的熵编码器。 B、基于DCT的扩展过程（Extended DCT Based Process）使用累进行工作方式，采用自 适应算术的编码过程。 C、无失真过程（Lossless Process）采用预测编码及Huffman（或算术编码），可保 证重建图像数据与原始图像数据完全相同。 基中的基本顺序过程是JPEG最基本的压缩过程：符合JPEG标准的硬软件编码/解码器都 必须支持和实现这个过程。另两个过程是可选扩展，对一些特定的应用项目有很大实用 价值。 （1）、JPEG算法 基本JPEG算法操作可分成以下三个步骤：通过离散余弦变换（DCT）去除数据冗余；使 用量化表对DCT系数进行量化，量化表是根据人类礼堂系统和压缩图像类型的特点进行 优化的量化系数矩阵；对量化后的DCT系数时行编码使其熵达到最小，熵编码采用 Huffman可变字长编码 （2）、离散余弦变换 JPEG采用8*8子块的二维离散余弦变换算法。在编者按码器的输入端，把原始图像（对 网络摄像机和视频服务器作为网络应用的新型产品，适应网络传输的要求也必然成为产品开发的重要因素，而这其中视频图像的技术又成为关键。在目前中国网络摄像机和视频服务器的产品市场上，各种压缩技术百花齐放，且各有优势，为用户提供了很大的选择空间。 JPEG 、M-JPEG 有相当一部分国内外网络摄像机和视频服务器都是采用JPEG，Motion-JPEG压缩技术，JPEG、M-JPEG采用的是帧内压缩方式，图像清晰、稳定，适于视频编辑，而且可以灵活设置每路的视频清晰度和压缩帧数。另外，因其压缩后的格式可以读取单一画面，因此可以任意剪接，特别适用与安防取证的用途。 Wavelet Transform 小波变换也属于帧内压缩技术，由于这种压缩方式移除了图像的高频成分，仅保留单帧图像信号，特别适用于画面变更频繁的场合，且压缩比也得到了一定的提高，因此也被一些网络摄像机和视频服务器所采用，例如，BOSCH推出的NetCam-4系列数字网络摄像机，深圳缔佳生产的NETCAM系列网络摄像机等。 H.263 H.263是一个较为成熟的标准，它是帧间预测和变换编码的混合算法，压缩比较高，尤其适用低带宽上传输活动视频。采用H.263技术生产的网络型产品，其成本较为适中，软/硬件丰富，适合集中监控数量较多的需求，如深圳大学通信技术研究所开发的SF－10网络摄像机和SF-20视频服务器，深圳新文鼎开发的W750视频服务器和W74GM网络摄像机等采用的都是这一压缩技术。 MPEG-4 MPEG-4的着眼点在于解决低带宽上音视频的传输问题，在164KHZ的带宽上，MPEG-4平均可传5－7帧/秒。采用MPEG-4压缩技术的网络型产品可使用带宽较低的网络，如PSTN，ISDN,ADSL等，大大节省了网络费用。另外，MPEG-4的最高分辨率可达720×576，接近DVD 画面效果，基于图像压缩的模式决定了它对运动物体可以保证有良好的清晰度。MPEG-4所有的这些优点，使它成为当前网络产品生产厂商开发的重要趋势之一。 另外，也有部分厂商采用的是MPEG-1,MPEG-2压缩格式，除此之外，有的厂商还采用多种压缩技术相结合的方式，例如，有些国外推出的网络摄像机，其压缩方式就是MPEG-4,与JPEG 相结合，在可以看到JPEG静止图像的同时，利用MPEG-4高级压缩功能，令到高质量的动态图像也能在低带宽上传输。 纵观以上这些压缩技术，虽然MPEG-4以其良好的图像压缩性能，可支持非常低的宽带上达到视频会议的质量，从而成为未来网络型产品开发的主流方向，但就现在市场的应用情况来看，MPEG-4暂时还没有占到主导地位，究其原因，主要是由于虽然MPEG-4的国际标准已经制定，但MPEG-4的算法是公开的因而厂商各自为政，良莠不齐，对后续的二次开发带来了严重的影响，另外，MPEG－4在图像质量上也有待提高，在复杂的网路环境中，数据流 算法论文 基于huffman编码的图像压缩技术 姓名：康凯 学院：计算机学院 专业：网络工程1102 学号：201126680208 摘要 随着多媒体技术和通讯技术的不断发展, 多媒体娱乐、信息高速公路等不断对信息数据的存储和传输提出了更高的要求, 也给现有的有限带宽以严峻的考验, 特别是具有庞大数据量的数字图像通信, 更难以传输和存储, 极大地制约了图像通信的发展, 因此图像压缩技术受到了越来越多的关注。图像压缩的目的就是把原来较大的图像用尽量少的字节表示和传输,并且要求复原图像有较好的质量。利用图像压缩, 可以减轻图像存储和传输的负担, 使图像在网络上实现快速传输和实时处理。 本文主要介绍数字图像处理的发展概况，图像压缩处理的原理和特点，对多种压缩编码方法进行描述和比较，详细讨论了Huffman编码的图像压缩处理的原理和应用。 关键词：图像处理,图像压缩,压缩算法,图像编码,霍夫曼编码 Abstract With the developing of multimedia technology and communication technology, multimedia entertainment, information, information highway have kept on data storage and transmission put forward higher requirements, but also to the limited bandwidth available to a severe test, especially with large data amount of digital image communication, more difficult to transport and storage, greatly restricted the development of image communication, image compression techniques are therefore more and more attention. The purpose of image compression is to exhaust the original image less the larger the bytes and transmission, and requires better quality of 数据结构课程设计报告 实验一：计算器 设计要求 1、问题描述：设计一个计算器，可以实现计算器的简单运算，输出并检验结果的正确性，以及检验运算表达式的正确性。 2、输入：不含变量的数学表达式的中缀形式，可以接受的操作符包括+、-、*、/、%、(、)。 具体事例如下： 3、输出：如果表达式正确，则输出表达式的正确结果；如果表达式非法，则输出错误信息。 具体事例如下： 知识点：堆栈、队列 实际输入输出情况： 正确的表达式 对负数的处理 表达式括号不匹配 表达式出现非法字符 表达式中操作符位置错误 求余操作符左右出现非整数 其他输入错误 数据结构与算法描述 解决问题的整体思路： 将用户输入的中缀表达式转换成后缀表达式，再利用转换后的后缀表达式进行计算得出结果。 解决本问题所需要的数据结构与算法： 用到的数据结构是堆栈。主要算法描述如下： A．将中缀表达式转换为后缀表达式： 1. 将中缀表达式从头逐个字符扫描，在此过程中，遇到的字符有以下几种情况： 1）数字 2）小数点 3）合法操作符+ - * / % 4）左括号 5）右括号 6）非法字符 2. 首先为操作符初始化一个map 实验报告 课程名称操作系统 实验项目名______LRU算法模拟 班级与班级代码 实验室名称（或课室） 专业 任课教师 学号： 姓名： 实验日期：2012 年 5 月20 日 制 姓名实验报告成绩 评语： 指导教师（签名） 年月日说明：指导教师评分后，学年论文交院（系）办公室保存。 实验八 LRU算法模拟 一、实验目的 （1）模拟实现LRU算法。 （2）模拟实现Clock算法。 （3）比较分析LRU算法、Clock算法。 二、实验内容 （1）算法实现。 （2）拟定测试数据对算法的正确性进行测试。 （3）对比分析LRU算法和Clock算法各自的优缺点。 三、实验环境 硬件要求：P4 2.0G 1G内存60G硬盘以上电脑 软件要求：C、C++编程环境，Java编程环境 四、实验步骤 1.LRU算法 （1）预备知识 最近最久未使用(LRU)的页面置换算法，是根据页面调入内存后的使用情况进行决策的。由于无法预测各页面将来的使用情况，只能利用“最近的过去”作为“最近的将来”的近似，因此，LRU置换算法是选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问 以来所经历的时间t ，当须淘汰一个页面时，选择现有页面中其t 值最大的，即最近最久未使用的页面予以淘汰。 （2）LRU 的实现（需要“堆栈”支持） 可利用一个特殊的栈来保存当前使用的各个页面的页面号。每当进程访问某页面时，便将该页面的页面号从栈中移出，将它压入栈顶。因此，栈顶始终是最新被访问页面的编号，而栈底则是最近最久未使用页面的页面号。假定现有一进程所访问的页面序列为： 4，7，0，7，1，0，1，2，1，2，6 随着进程的访问，栈中页面号的变化情况如图所示。在访问页面6时发生了缺页，此时页面4是最近最久未被访问的页，应将它置换出去。 （2）具体的操作代码及其结果如下： #include 各种音频编码方式的对比 内容简介：文章介绍了PCM编码、WMA编码、ADPCM编码、LPC编码、MP3编码、AAC编码、CELP编码等，包括优缺点对比和主要应用领域。 PCM编码(原始数字音频信号流) 类型：Audio 制定者：ITU-T 所需频宽： Kbps 特性：音源信息完整，但冗余度过大 优点：音源信息保存完整,音质好 缺点：信息量大，体积大，冗余度过大 应用领域：voip 版税方式：Free 备注：在计算机应用中，能够达到最高保真水平的就是PCM编码，被广泛用于素材保存及音乐欣赏，CD、DVD以及我们常见的WAV文件中均有应用。因此，PCM约定俗成了无损编码，因为PCM代表了数字音频中最佳的保真水准，并不意味着PCM就能够确保信号绝对保真，PCM也只能做到最大程度的无限接近。要算一个PCM音频流的码率是一件很轻松的事情，采样率值×采样大小值×声道数bps。一个采样率为，采样大小为16bit，双声道的PCM编码的WAV文件，它的数据速率则为×16×2 =。我们常见的Audio CD 就采用了PCM编码，一张光盘的容量只能容纳72分钟的音乐信息。 WMA(Windows Media Audio) 类型：Audio 制定者：微软公司 所需频宽：320～112kbps（压缩10～12倍） 特性：当Bitrate小于128K时，WMA几乎在同级别的所有有损编码格式中表现得最出色，但似乎128k 是WMA一个槛，当Bitrate再往上提升时，不会有太多的音质改变。 优点：当Bitrate小于128K时，WMA最为出色且编码后得到的音频文件很小。 缺点：当Bitrate大于128K时，WMA音质损失过大。WMA标准不开放，由微软掌握。 应用领域：voip 版税方式：按个收取 备注：WMA的全称是Windows Media Audio，它是微软公司推出的与MP3格式齐名的一种新的音频格式。由于WMA在压缩比和音质方面都超过了MP3，更是远胜于RA(Real Audio)，即使在较低的采样频率下也能产生较好的音质，再加上WMA有微软的Windows Media Player做其强大的后盾，所以一经推出就赢得一片喝彩。 ADPCM( 自适应差分PCM) 类型：Audio 制定者：ITU-T 所需频宽：32Kbps 特性：ADPCM(adaptive difference pulse code modulation)综合了APCM的自适应特性和DPCM系统的差分特性，是一种性能比较好的波形编码。 它的核心想法是： ①利用自适应的思想改变量化阶的大小，即使用小的量化阶(step-size)去编码小的差值，使用大的量化阶去编码大的差值； ②使用过去的样本值估算下一个输入样本的预测值，使实际样本值和预测值之间的差值总是最小。 优点：算法复杂度低，压缩比小（CD音质>400kbps），编解码延时最短（相对其它技术） 缺点：声音质量一般 应用领域：voip 多媒体技术及应用 JPEG图像压缩算法及其实现 罗群书 0411102班 2011211684 一、JEPG压缩算法（标准） (一)JPEG压缩标准 JPEG(Joint Photographic Experts Group)是一个由ISO/IEC JTC1/SC2/WG8和CCITT VIII/NIC于1986年底联合组成的一个专家组，负责制定静态的数字图像数据压缩编码标准。迄今为止，该组织已经指定了3个静止图像编码标准，分别为JPEG、JPEG-LS和JPEG2000。这个专家组于1991年前后指定完毕第一个静止图像压缩标准JPEG标准，并且成为国际上通用的标准。JPEG标准是一个适用范围很广的静态图像数据压缩标准，既可用于灰度图像又可用于彩色图像。 JPEG专家组开发了两种基本的静止图像压缩算法，一种是采用以离散余弦变换(Discrete Cosine Transform, DCT)为基础的有损压缩算法，另一种是采用以预测技术为基础的无损压缩算法。使用无损压缩算法时，其压缩比比较低，但可保证图像不失真。使用有损压缩算法时，其算法实现较为复杂，但其压缩比大，按25：1压缩后还原得到的图像与原始图像相比较，非图像专家难于找出它们之间的区别，因此得到了广泛的应用。 JPEG有4种工作模式，分别为顺序编码，渐近编码，无失真编码和分层编码，他们有各自的应用场合，其中基于顺序编码工作模式的JPEG压缩系统也称为基本系统，该系统采用单遍扫描完成一个图像分量的编码，扫描次序从左到右、从上到下，基本系统要求图像像素的各个色彩分量都是8bit，并可通过量化线性地改变DCT系统的量化结果来调整图像质量和压缩比。下面介绍图像压缩采用基于DCT的顺序模式有损压缩算法，该算法下的JPEG压缩为基本系统。 (二)JPEG压缩基本系统编码器 JPEG压缩是有损压缩，它利用了人的视觉系统的特性，将量化和无损压缩编码相结合来去掉视觉的冗余信息和数据本身的冗余信息。基于基本系统的JPEG压缩编码器框图如图1所示，该编码器是对单个图像分量的处理，对于多个分量的图像，则首先应将图像多分量按照一定顺序和比例组成若干个最小压缩单元（MCU），然后同样按该编码器对每个MCU各个分量进行独立编码处理，最终图像压缩数据将由多个MCU压缩数据组成。 图1 JPEG压缩编码器结构框图 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 设计过程在硬件与软件方面进行同步设计。硬件方面从功能考虑，首先选择内部存储资源丰富的AT89C51单片机，输入采用4×4矩阵键盘。显示采用3位7段共阴极LED动态显示。软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C 语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C51芯片、汇编语言、数码管、加减乘除 目录 摘要 (01) 引言 (01) 一、设计任务和要求............................. 1、1 设计要求 1、2 性能指标 1、3 设计方案的确定 二、单片机简要原理............................. 2、1 AT89C51的介绍 2、2 单片机最小系统 2、3 七段共阳极数码管 三、硬件设计................................... 3、1 键盘电路的设计 3、2 显示电路的设计 四、软件设计................................... 4、1 系统设计 4、2 显示电路的设计 五、调试与仿真................................. 5、1 Keil C51单片机软件开发系统 5、2 proteus的操作 六、心得体会.................................... 参考文献......................................... 附录1 系统硬件电路图............................ 附录2 程序清单.................................. 时钟置换算法（CLOCK）例题： 一个作业的物理块数为3，此作业的页面走向为：内存及控制信息输入串指针移动情况及帧替换信息是否缺页？ 内存访 问 位 指针 3 内存中没有3，需要找到一个帧放 入3， 指针所指的位置恰好有访问位为 0的， 于是就淘汰这个帧，指针下移 √0← 内存访 问 位 指针 4 内存中没有4，需要找到一个帧放 入4， 指针所指的位置恰好有访问位为 0的， 于是就淘汰这个帧，指针下移 √ 31 0← 内存访 问 位 指针 2 内存中没有2，需要找到一个帧放 入2， 指针所指的位置恰好有访问位为 0的， 于是就淘汰这个帧，指针下移 √ 31 41 0← 内存访 问 位 指针 6 内存中没有6，需要找到一个帧放 入6， 指针所指的位置的访问位为1， 将其变成0，再下移√ 31←41 21 内存访 问 位 指针 指针所指的位置的访问位仍为1， 将其变成0，再下移 30 41←21 内存访 问 位 指针 指针所指的位置的访问位仍为1， 将其变成0，再下移（回到开头） 30 40 21← 内存访 问 位 指针 指针所指的位置恰好有访问位为 0的， 于是就淘汰这个帧，指针下移 30←40 20 内存访 问 位 指针 4 内存中有4，于是4所在帧的访问 位变为1， 指针下移 × 61 40←20 内存访 问 位 指针 3 内存中没有3，需要找到一个帧放 入3， 指针所指的位置恰好有访问位为 0的， 于是就淘汰这个帧，指针下移 √ 61 41 20← 内存访 问 位 指针 7 内存中没有7，需要找到一个帧放 入7， 指针所指的位置的访问位为1， 将其变成0，再下移 √ 61← 五种压缩软件（WinRAR、7Z、好压、快压和360压缩）之比拼 除了老牌的WinRAR和7Z压缩软件外，新近又出现了多款国产压缩软件，各自都称其为自主知识产权，最高压缩比，现就WinRAR、7Z、好压、快压和360压缩等五款压缩软件的功能进行一次大比拼。 一、压缩功能之比拼 本人用GHO映像文件、rmvb视频文件和JPG图像文件进行了压缩测试。 1、用GHO映像文件829MB测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 12分58秒830M 7Z ZIP 2分13秒826M 2 WinRAR rar 15分22秒824M WinRAR ZIP 1分7秒825M 3 快压kz 12分52秒829M 快压ZIP 4 好压7z 好压ZIP 1分20秒825M 5 360压缩7z 360压缩ZIP 1分55秒826M 从上表看出，在压缩GHO映像文件时，号称最高压缩比的7Z和快压居然毫无建树，7Z压缩文件居然比GHO映像文件还大，原因是因为GHO映像文件也是压缩文件的一种。唯有最老牌的ZIP压缩效果最好，速度最快，压缩比最高。 2、用rmvb视频文件175MB测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 3分32秒173M 7Z ZIP 4分00秒173M 2 WinRAR rar 3分10秒173M WinRAR ZIP 15秒173M 3 快压kz 21秒173M 快压ZIP 3分57秒173M 4 好压7z 20秒173M 好压ZIP 173M 5 360压缩7z 3分23秒173M 360压缩ZIP 30秒175M 从上表看出，5种压缩软件的各种压缩格式对rmvb视频文件的压缩比都很小，因为rmvb视频文件是用可变码率编码的一种高压缩视频编码算法，可压缩的空间很小，用压缩软件压缩rmvb视频文件是没有必要的。但仍然是ZIP的压缩速度最快。 3、用JPG图像文件32.2M测试 软件编号软件压缩格式用时压缩文件大小备注 1 7Z 7z 24秒28.6M JPEG2000图像压缩算法标准 摘要：JPEG2000是为适应不断发展的图像压缩应用而出现的新的静止图像压缩标准。本文介绍了JPEG2000图像编码系统的实现过程, 对其中采用的基本算法和关键技术进行了描述，介绍了这一新标准的特点及应用场合，并对其性能进行了分析。 关键词：JPEG2000；图像压缩；基本原理；感兴趣区域 引言 随着多媒体技术的不断运用，图像压缩要求更高的性能和新的特征。为了满足静止图像在特殊领域编码的需求，JPEG2000作为一个新的标准处于不断的发展中。它不仅希望提供优于现行标准的失真率和个人图像压缩性能，而且还可以提供一些现行标准不能有效地实现甚至在很多情况下完全无法实现的功能和特性。这种新的标准更加注重图像的可伸缩表述。所以就可以在任意给定的分辨率级别上来提供一个低质量的图像恢复，或者在要求的分辨率和信噪比的情况下提取图像的部分区域。 1.JPEG2000的基本介绍及优势 相信大家对JPEG这种图像格式都非常熟悉，在我们日常所接触的图像中，绝大多数都是JPEG格式的。JPEG的全称为Joint Photographic Experts Group，它是一个在国际标准组织(ISO)下从事静态图像压缩标准制定的委员会，它制定出了第一套国际静态图像压缩标准：ISO 10918－1，俗称JPEG。由于相对于BMP等格式而言，品质相差无己的JPEG格式能让图像文件“苗条”很多，无论是传送还是保存都非常方便，因此JPEG格式在推出后大受欢迎。随着网络的发展，JPEG的应用更加广泛，目前网站上80％的图像都采用JPEG格式。 但是，随着多媒体应用领域的快速增长，传统JPEG压缩技术已无法满足人们对数字化多媒体图像资料的要求：网上JPEG图像只能一行一行地下载，直到全部下载完毕，才可以看到整个图像，如果只对图像的局部感兴趣也只能将整个图片载下来再处理；JPEG格式的图像文件体积仍然嫌大；JPEG格式属于有损压缩，当被压缩的图像上有大片近似颜色时，会出现马赛克现象；同样由于有损压缩的原因，许多对图像质量要求较高的应用JPEG无法胜任。 JPEG2000是为21世纪准备的压缩标准，它采用改进的压缩技术来提供更高的解像度，其伸缩能力可以为一个文件提供从无损到有损的多种画质和解像选择。JPEG2000被认为是互联网和无线接入应用的理想影像编码解决方案。 “高压缩、低比特速率”是JPEG2000的目标。在压缩率相同的情况下，JPEG2000的信噪比将比JPEG提高30%左右。JPEG2000拥有5种层次的编码形式：彩色静态画面采用的JPEG 编码、2值图像采用的JBIG、低压缩率图像采用JPEGLS等，成为应对各种图像的通用编码方式。在编码算法上，JPEG2000采用离散小波变换（DWT）和bit plain算术编码（MQ coder）。此外，JPEG2000还能根据用户的线路速度以及利用方式(是在个人电脑上观看还是在PDA上观看)，以不同的分辨率及压缩率发送图像。 JPEG2000的制定始于1997年3月，但因为无法很快确定算法，因此耽误了不少时间，直到2000年 3 月，规定基本编码系统的最终协议草案才出台。目前JPEG2000已由ISO和 微机课程设计报告 题目简易计算器仿真 学院（部）信息学院 专业通信工程 班级2011240401 学生姓名张静 学号33 12 月14 日至12 月27 日共2 周 指导教师（签字）吴向东宋蓓蓓 单片机十进制加法计算器设计 摘要 本设计是基于51系列的单片机进行的十进制计算器系统设计，可以完成计 算器的键盘输入，进行加、减、乘、除3位无符号数字的简单四则运算，并在LED上相应的显示结果。 软件方面从分析计算器功能、流程图设计，再到程序的编写进行系统设计。编程语言方面从程序总体设计以及高效性和功能性对C语言和汇编语言进行比较分析，针对计算器四则运算算法特别是乘法和除法运算的实现，最终选用全球编译效率最高的KEIL公司的μVision3软件，采用汇编语言进行编程，并用proteus仿真。 引言 十进制加法计算器的原理与设计是单片机课程设计课题中的一个。在完成理论学习和必要的实验后，我们掌握了单片机的基本原理以及编程和各种基本功能的应用，但对单片机的硬件实际应用设计和单片机完整的用户程序设计还不清楚，实际动手能力不够，因此对该课程进行一次课程设计是有必要的。 单片机课程设计既要让学生巩固课本学到的理论，还要让学生学习单片机硬件电路设计和用户程序设计，使所学的知识更深一层的理解，十进制加法计算器原理与硬软件的课程设计主要是通过学生独立设计方案并自己动手用计算机电路设计软件，编写和调试，最后仿真用户程序，来加深对单片机的认识，充分发挥学生的个人创新能力，并提高学生对单片机的兴趣，同时学习查阅资料、参考资料的方法。 关键词：单片机、计算器、AT89C52芯片、汇编语言、数码管、加减乘除 几种视频压缩标准简介 3. 基于嵌入式视频服务器的网络化数字视频监控 3.1 什么是网络数字监控 简单的说，网络数字监控就是将传统的模拟视频信号转换为数字信号，通过计算机网络来传输，通过智能化的计算机软件来处理。 系统将传统的视频、音频及控制信号数字化，以IP包的形式在网络上传输，实现了视频/音频的数字化、系统的网络化、应用的多媒体化以及管理的智能化。 3.2 几种视频压缩标准简介 1）MJPEG MJPEG 是指Motion JPEG，即动态JPEG，按照25帧/秒速度使用JPEG 算法压缩视频信号，完成动态视频的压缩。是由JPEG专家组制订的，其图像格式是对每一帧进行压缩，通常可达到6：1的压缩率，但这个比率相对来说仍然不足。就像每一帧都是独立的图像一样。MJPEG图象流的单元就是一帧一帧的JPEG画片。因为每帧都可任意存取，所以MJPEG 常被用于视频编辑系统。动态JPEG能产生高质量、全屏、全运动的视频，但是，它需要依赖附加的硬件。而且，由于MJPEG不是一个标准化的格式，各厂家都有自己版本的MJPEG，双方的文件无法互相识别。 MJPEG的优点是画质还比较清晰，缺点是压缩率低，占用带宽很大。一般单路占用带宽2M左右。 2）H.263 H.263 视频编码标准是专为中高质量运动图像压缩所设计的低码率图像压缩标准。 H.263 采用运动视频编码中常见的编码方法，将编码过程分为帧内编码和帧间编码两个部分。埃帧内用改进的DCT 变换并量化，在帧间采用1/2 象素运动矢量预测补偿技术，使运动补偿更加精确，量化后适用改进的变长编码表（VLC）地量化数据进行熵编码，得到最终的编码系数。 H.263标准压缩率较高，CIF格式全实时模式下单路占用带宽一般在几百左右，具体占用带宽视画面运动量多少而不同。缺点是画质相对差一些，占用带宽随画面运动的复杂度而大幅变化。 3）MPEG-1 VCD标准。 《算法设计与分析》课程报告 姓名：文亮 学号：201322220254 学院：信息与软件工程学院 老师：屈老师；王老师 算法实现与应用——《算法设计与分析》课程报告 一． 基本要求 1. 题目: 图像压缩 2. 问题描述 掌握基于DCT 变换的图像压缩的基本原理及其实现步骤；对同一幅原 始图像进行压缩，进一步掌握DCT 和图像压缩。 3. 算法基本思想 图像数据压缩的目的是在满足一定图像质量的条件下，用尽可能少的比特数来表示原始图像，以提高图像传输的效率和减少图像存储的容量，在信息论中称为信源编码。图像压缩是通过删除图像数据中冗余的或者不必要的部分来减小图像数据量的技术，压缩过程就是编码过程，解压缩过程就是解码过程。压缩技术分为无损压缩和有损压缩两大类，前者在解码时可以精确地恢复原图像，没有任何损失；后者在解码时只能近似原图像，不能无失真地恢复原图像。 假设有一个无记忆的信源,它产生的消息为{}N ≤≤i a i 1,其出现的概率是已知的,记为()i a p 。则其信息量定义为: ()()i i a p a log -=I 由此可见一个消息出现的可能性越小，其信息量就越多，其出现对信息的贡献量越大，反之亦然。 信源的平均信息量称为“熵”（entropy ），可以表示为： ()()[]()()∑∑==-=?=H N i i i N i i i a p a p a p I a p 1 1 log 对上式取以2为底的对数时，单位为比特（bits ）： ()()∑=-=H N i i i a p a p 1log 根据香农（Shannon ）无噪声编码定理，对于熵为H 的信号源，对其进行无 安卓应用程序设计 ——简易计算器的实现院（系）名称 专业名称 学生姓名 学生学号 课程名称 2016年6月日 1.系统需求分析 Android是以Linux为核心的手机操作平台，作为一款开放式的操作系统，随着Android 的快速发展，如今已允许开发者使用多种编程语言来开发Android应用程序，而不再是以前只能使用Java开发Android应用程序的单一局面，因而受到众多开发者的欢迎，成为真正意义上的开放式操作系统。计算器通过算法实行简单的数学计算从而提高了数学计算的效率，实现计算器的界面优化，使界面更加友好，操作更加方便。基于android的计算器的设计,系统具有良好的界面；必要的交互信息；简约美观的效果。使用人员能快捷简单地进行操作，即可单机按钮进行操作，即时准确地获得需要的计算的结果，充分降低了数字计算的难度和节约了时间。 2.系统概要设计 2.1计算器功能概要设计 根据需求，符合用户的实际要求，系统应实现以下功能：计算器界面友好，方便使用，，具有基本的加、减、乘、除功能，能够判断用户输入运算数是否正确，支持小数运算，具有清除功能。 图2.1系统功能图 整个程序基于Android技术开发，除总体模块外主要分为输入模块、显示模块以及计算模块这三大部分。在整个系统中总体模块控制系统的生命周期，输入模块部分负责读取用户输入的数据，显示模块部分负责显示用户之前输入的数据以及显示最终的计算结果，计算模块部分负责进行数据的运算以及一些其他的功能。具体的说，总体模块的作用主要是生成应用程序的主类，控制应用程序的生命周期。 输入模块主要描述了计算器键盘以及键盘的监听即主要负责读取用户的键盘输入以及 响应触屏的按键，需要监听手机动作以及用指针事件处理方法处理触屏的单击动作。同时提供了较为直观的键盘图形用户界面。 显示模块描述了计算器的显示区，即该区域用于显示用户输入的数据以及最终的计算结 实验四页面置换算法 一、实验目的 本实验主要对操作系统中请求分页式内存管理及其应用的一些关键算法进行模拟。学生通过设计与实现Clock算法，能够加强对相应理论的理解，并对了解操作系统内部的基本处理原理与过程也有很多益处。 二、实验要求 基本要求：描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。 1）初始化：输入作业可占用的总页框数，初始化置空。 2）输入请求序列：输入一个作业页号访问请求序列，依次占用相应页框，直至全部占用； 3）Clock算法：当页框全部占用后，对于后续新的页号访问请求，执行Clock算法，淘汰1个页面后装入新的页号。 4）显示当前分配淘汰序列：显示淘汰的页号序列。 描述Clock算法的基本原理、必要的数据结构、算法执行流程图、编码实现。 三、实验内容 1)基本原理 时钟页面置换算法是把所有的页面都保存在一个类似钟面的环形链表中，一个表针指向最老的页面， 如图所示。 当发生缺页中断时，算法首先检查表针指向的页面，如果它的R位是0就淘汰该页面，并把新的页面插入这个位置，然后把表针前移一个位置；如果R位是1就清除R位并把表针前移一个位置，重复这个过程直到找到了一个R位为0的页面为止。 2)算法流程设计 主函数流程: STEP1:输入分配的页框数，页面访问次数和要访问的页面号序列 STEP2:内存页面初始化。内存中页面的数据结构为单循环链表，含有页号值yehao和访问位值a。 开始时页号均为-1，访问位为0. STEP3：测试数据。具体算法是依要访问的页面号，调用find()函数查找是否已经存在于内存中。 若存在，则修改其访问位为1.若不存在，触发缺页中断，调用tihuan()函数。最后，打印当前内存状态。如此循环直至测试串都访问完毕。 3)主要函数实现 a)Makenode(double)函数：用于初始化一个节点。 b)Find（double）函数：依据输入的页号，查询内存中是否已存在此页面。若存在返回值1， 不存在返回值0. c)Tihuan（double）函数：在发生缺页中断时，时钟指针查找访问位为0的页面进行替换，指 针扫过的页面访问位置0，新加入的页面访问位置1。替换后指针下移。 d)Print_state()函数：打印当前内存中存在的页面的状态以及当前时钟指针所指向的页面位 置。 4)测试数据 输入： 输入分配的页框数 3 输入页面访问次数 15 输入要访问的页面号序列 3 4 2 6 4 3 7 4 3 6 3 4 8 4 6 输出（仅最后一项）： 5)结果分析 以下是clock算法对应输入页面号序列3 4 2 6 4 3 7 4 3 6 3 4 8 4 6的分析表 各种音频编码方式的对比 各种音频编码方式的对比 内容简介：文章介绍了PCM编码、WMA编码、ADPCM 编码、LPC编码、MP3编码、AAC编码、CELP编码等，包括优缺点对比和主要应用领域。 PCM编码(原始数字音频信号流) 类型：Audio 制定者：ITU-T 所需频宽：1411.2 Kbps 特性：音源信息完整，但冗余度过大 优点：音源信息保存完整,音质好 缺点：信息量大，体积大，冗余度过大 应用领域：voip 版税方式：Free 备注：在计算机应用中，能够达到最高保真水平的就是PCM编码，被广泛用于素材保存及音乐欣赏，CD、DVD 以及我们常见的WAV文件中均有应用。因此，PCM 约定俗成了无损编码，因为PCM代表了数字音频中最佳的保真水准，并不意味着PCM就能够确保信号绝对保真，PCM也只能做到最大程度的无限接近。要算一个PCM音频流的码率是一件很轻松的事情，采样率值×采样大小值×声道数bps。一个采样率为44.1KHz， 采样大小为16bit，双声道的PCM编码的WAV文件，它的数据速率则为44.1K×16×2 =1411.2Kbps。我们常见的Audio CD就采用了PCM编码，一张光盘的容量只能容纳72分钟的音乐信息。 WMA(Windows Media Audio) 类型：Audio 制定者：微软公司 所需频宽：320～112kbps（压缩10～12倍） 特性：当Bitrate小于128K时，WMA几乎在同级别的所有有损编码格式中表现得最出色，但似乎128k是WMA一个槛，当Bitrate再往上提升时，不会有太多的音质改变。 优点：当Bitrate小于128K时，WMA最为出色且编码后得到的音频文件很小。 缺点：当Bitrate大于128K时，WMA音质损失过大。WMA标准不开放，由微软掌握。 应用领域：voip 版税方式：按个收取 备注：WMA的全称是Windows Media Audio，它是微软公司推出的与MP3格式齐名的一种新的音频格式。由于WMA在压缩比和音质方面都超过了MP3，更是远胜于RA(Real Audio)，即使在较低的采样频率下也能产生较好的音质，再加上WMA有微软的 VB应用程序的设计方法 ——“简易计算器”教学设计 揭阳第一中学卢嘉圳 教学内容：利用所学知识制作Visual Basic程序“简易计算器” 教学目标：能熟练运用CommandButton控件及TextBox控件进行Visual Basic(以下简称VB)程序的设计，能熟练运用条件语句编写代码 教学重点:运用开发VB程序一般过程的思路来开发“简易计算器” 教学难点:分析得出实现“简易计算器”各运算功能的算法。 教材分析： 当我刚开始进行程序设计的教学时，便感觉比较难教。这是因为程序设计本身枯燥、严谨，较难理解，而且学生大多数都是初学者，没有相应的知识基础。对于《程序设计实例》，我们选用的教材是广东教育出版社出版的《信息技术》第四册，该书采用的程序设计语言是VB，而学生是仅学过了一点点简单的QB编程之后就进入《程序设计实例》的学习的。 教材为我们总结了设计VB程序的一般步骤：创建用户界面；设置控件属性；编写事件程序代码；运行应用程序。我总结了一下，其实VB程序设计可分为设计用户界面及编写程序代码两个环节。 教学过程： 一、引入新课 任务：让学生按照书上提示完成一个非常简单的VB程序——“计算器”（仅包含开方、平方、求绝对值功能）的制作。 目的：加强对CommandButton控件及TextBox控件的掌握，复习对开方、求绝对值函数的使用。 引入本节课的学习任务：设计一个简易计算器，包含加、减、乘、除、开方、平方等运算。程序界面可参考下图。 具体功能为：在Text1中输入一个数值，然后单击代表运算符的按钮则运算结果会在text2中显示出来；比如在text1中输入一个2，然后按“+”按钮，再输入一个3按“-”按钮，再输入一个-4按“*”按钮，则实际为(2-3)*(-4)；最后在text2中显示结果为4。几种视频压缩技术概述
视频格式和压缩标准大全
图像压缩算法论文
数据结构课程设计计算器
LRU算法 与CLOCK算法
各种音频编码方式的对比
JPEG图像压缩算法及其实现
简易计算器
时钟置换算法CLOCK(答案参考)
五种压缩软件比较
JPEG2000图像压缩算法标准剖析
微机课设简易计算器
几种视频压缩标准
图像压缩算法
基于安卓的计算器的设计与实现
操作系统实验报告(clock算法)
各种音频编码方式的对比
计算器制作