当前位置:文档之家› 北理工贾云德《计算机视觉》chapter04区域分析

北理工贾云德《计算机视觉》chapter04区域分析

北理工贾云德《计算机视觉》chapter04区域分析
北理工贾云德《计算机视觉》chapter04区域分析

第四章 区域分析

图像中的区域是指相互连结的具有相似特性的一组像素.由于区域可能对应场景中的物体,因此,区域的检测对于图像解释十分重要.一幅图像可能包含若干个物体,而每一个物体又可能包含对应于物体不同部位的若干个区域.为了精确解释一幅图像,首先要把一幅图像划分成对应于不同物体或物体不同部位的区域.

4.1 区域和边缘

图像区域划分有两种方法:一种是基于区域的方法,另一种是使用边缘检测的轮廓预估方法.在基于区域的方法中,把所有对应于一个物体的像素组合在一起,并进行标记,以表示它们属于一个区域,这一处理过程称为分割.在某一评判标准下,把像素分配给某一区域,就可以把这些像素同图像其余部分分开.图像分割中的两个最基本的原则是数值相似性和空间接近性.如果两个像素具有相似的强度特性,或它们之间十分靠近,则可以把它们分配到同一区域,例如,两个像素之间的数值相似性度量可以是它们的灰度值之差,也可以是区域灰度值分布;它们的空间接近性度量可以是欧几里德距离,也可以是区域致密度. 相似性和接近性原则来源于如下假设:同一物体上的点投影到图像上得到的像素点在空间上十分靠近,且具有相似的灰度值.很显然,这一假设并不是在任何情况下都成立.然而可以使用这一假设来组合图像中的像素,然后利用相关域知识来匹配物体模型和区域.在简单的情况下,可以通过阈值法和连通成份标记法来进行图像分割,这一点在第三章讨论过了.对于复杂的图像,可以使用更高级的方法实现图像分割.

分割也可以通过求取区域边界上的像素来进行.这些像素点(也称为边缘)可以通过搜寻邻近像素的方法来得到.由于边缘像素是在边界上,在边界两边的区域具有不同的灰度值,这样,区域的边界可以通过测量邻近像素差值来求取.尽管边缘检测可能使用诱导特性(如纹理和运动)来检测边缘.但大多数边缘检测器仅使用强度特性作为边缘检测的基础. 在理想的图像中,一个区域是由一条封闭轮廓线包围着.原则上,区域分割和边缘检测应该产生相同的结果,即使用边界跟踪算法可以得到区域的边缘(或封闭的轮廓线);反过来,使用区域填充算法也可以得到边缘所包围的区域.但在实际的图像中,很少能够从区域中得到正确的边缘,反之亦然.由于噪声和其它因素的影响,不论是区域分割还是边缘检测,都无法提供完整的信息.

本章将讨论区域的基本概念,主要集中在两个问题上:图像分割和区域表示.

4.2 分割

已知一幅图像像素集I 和一个一致性谓词)(?P ,求图像I 表示成n 个区域i R 集合的一种划分:

I R

n i i == 1 (4.1)

一致性谓词和图像划分具有如下特性,即任何区域满足如下谓词:

True )(=i R P (4.2)

任何两个相邻区域不能合并成单一区域,必满足谓词:

False )(=j i R R P (4.3)

一致性谓词)(?P 定义了在区域i R 上的所有点与区域模型的相似程度.

把一幅灰度图像转换成二值图像是图像分割的最简单形式.用于求取二值图像的阈值算法可以推广到求取多值图像,其中的阈值算法已经在第三章中讨论过了.为了在各种变化的场景中都能得到鲁棒的图像分割,阈值分割算法应能根据图像强度取样来自动选取合适的阈值.阈值分割法不要过分依赖于物体的灰度知识,且使用有关灰度值的相对特性来选取合适的阈值.这一简单的思想在许多计算机视觉算法中十分有用.

4.2.1 自动阈值化法

为了使分割更加鲁棒,系统应能自动选择阈值.基于场景中的物体、环境和应用域等知识的图像分割算法比基于固定阈值算法更具有普遍性.这些知识包括:对应于物体的图像灰度特性,物体的尺寸,物体在图像中所占的比例,图像中不同类型物体的数量等.图像灰度直方图就是一种灰度特性,它是指图像所有灰度值出现的相对频率.

使用上述知识并在无人介入的情况下自动选取阈值的方法称为自动阈值化方法.自动阈值化算法通常使用灰度直方图来分析图像中灰度值的分布,并使用特定应用域知识来选取最合适的阈值.由于所用的知识具有普遍性,因此大大增加了算法的应用范围.

假设一幅图像中包含有n 个物体n O O O ,,,21???,包括背景,并假设不同的区域n πππ,,,21???的灰度值具有概率分布函数)(,),(),(21z p z p z p n ???.在许多应用中,物体在图像中出现的概率n ,P ,,P P ???21也许是已知的.使用这些知识来严格地计算阈值是完全可能的.由于场景中的照明控制着图像中强度值的概率分布函数)(z p i , 因此预先计算阈值是不可能的.我们将要看到,大多数自动阈值的选取算法使用了物体尺寸和出现概率,并通过计算灰度直方图估算强度分布.

下面将讨论几种常用的自动阈值化方法.为了简化表示,我们将遵循物体在图像中的表示惯例,即物体相对于光亮背景是黑的.也就是说,低于某一阈值的灰度值属于物体,而高于这一阈值的灰度值属于背景.下面将要讨论的算法稍作改动就可以应用到其它场合,如光亮物体相对于黑暗背景,灰暗物体相对于光亮和黑暗背景,光亮或黑暗物体相对于灰暗背景.一些算法还可以推广到由任意像素值集合组成的物体.

(1) 模态方法

如果图像中的物体具有同一灰度值,背景具有另一个灰度值,图像被零均值高斯噪声污染,那么就可以假定灰度分布曲线是由两个正态分布函数),(),(2

22211σμσμ和叠加而成.图像直方图将会出现两个分离的峰值,如图4.1所示.在理想恒定灰度值情况下,021==σσ,其直方图为两条线分别对应两个峰值,这时的阈值可以设置在两个最大值之间的任何位置.在实际应用中,两个最大值并不是分得很开,此时需要检测直方图曲线的波谷和波峰,并把阈值设置成波谷对应的像素值.可以证明,当物体的尺寸和背景相等时,这样选取阈值可使误分类概率达到极小值.在大多数情况下,由于直方图在波谷附近的像素很稀疏,因此,阈值的选取对图像分割影响不大.

这一方法可推广到具有不同灰度均值的多物体图像中.假设有n 个物体,其强度值的正态分布参数为),(,),,(),,(2222211n n σμσμσμ???,背景也服从正态分布),(200σμ.如果这些均值明显的不同,方差值很小,且没有小尺寸物体,那么图像直方图将包含n+1个波峰,并可确定波谷的位置n T T T ,...,,21,落入每一个间隔),(1+i i T T 中的所有像素被分配给对应的物体,如图4.2所示.

图4.1(a) 理想情况下,背景和物体的灰度值可以分的很开.

(b)大多数情况下,物体和背景的强度值相互重叠.

图4.2 具有不同灰度值的多物体图像直方图

(2) 迭代式阈值选择

迭代式阈值选择方法如下:首先选择一个近似阈值作为估计值的初始值,然后连续不断地改进这一估计值.比如,使用初始阈值生成子图像,并根据子图像的特性来选取新的阈值,再用新阈值分割图像,这样做的效果将好于用初始阈值分割的图像.阈值的改进策略是这一方法的关键.算法4.1给出了这一方法的步骤.

算法4.1 迭代式阈值选择算法

选择一个初始阈值的估算值T ,比如,图像强度均值就是一个较好的初始值. 利用阈值T 把图像分割成两组,1R 和2R .

计算区域1R 和2R 的均值21,μμ.

选择新的阈值T

)(2

121μμ+=T 重复2-4步,直到1μ和2μ的均值不再变化.

(3) 自适应阈值化方法

如果场景中的照明不均匀,那么上述的自动阈值化方法就不能使用.显然,在这种情况下,一个阈值无法满足整幅图像的分割要求。处理不均匀照明或不均匀灰度分布背景的直接方法是首先把图像分成一个个小区域,或子图像,然后分析每一个子图像,并求出子图像的阈值。比如,把图像分成m m ?个子图像,并基于第ij 子图像的直方图来选择该子图像的阈值ij T (m j i ≤≤,1),图像分割的最后结果是所有子图像分割区域的逻辑并。这一算法如图

4.3所示.

图4.3 基于子图像(直方图的自适应阈值化处理示意图)

(4) 变量阈值化方法

在不均匀照明条件下的另一种实用的阈值化方法是使用简单的函数,如平面、二次曲面等,来逼近不均匀照明下的物体图象与背景图象之间的分界面。分界面在很大程度上是由背景灰度值确定的。例如,图4.4(a )是在不均匀照明下获取的图像,其中物体上一部分点的灰度值大于背景点的灰度值,而物体的另一部分点的灰度值则小于背景点的灰度值,图

4.4(d )和(e )是取直方图的两个波谷值85=T 和165=T 作为阈值得到的二幅二值图象。显然,不存在一个阈值可以很好地分割图像。如果用一个平面来拟合背景灰度值,则目标很容易从背景中分离出来,如图 4.4(f )—(j )所示.原图像与背景拟合平面之差形成规范化图像,在规范化图像中,目标的灰度值大于背景灰度值,即图像直方图有显著的波谷存在,因此,目标很容易从背景图像中分离出来.

图4.4 用变量阈值化方法处理图4.3(a)的结果.(a)原始图像和平面近似函数的差值图像(即规范化图像),(b)规范化图像直方图,(c)阈值化图像T=53,(d)阈值化图像T=80

(5) 双阈值方法

在许多应用中,属于物体的某些灰度值是已知的.然而,可能还有一些灰度值或者属于物体,或者属于背景.在这种情况下,人们可能使用一个保守一点的阈值

T来分离物体图

1

像,称之为物体图像核,然后,使用有关算法来增长物体图像.增长物体图像的方法取决于特定的应用,通常使用另一个阈值来吸收那些图像核像素的邻接像素,或用图像强度特性(如直方图)来决定属于物体区域上的那些点,一种简单的方法是吸收低于第二个阈值

T并且

2

与原先物体图像点相连结的所有点.算法4.2概括了这一算法.

算法4.2 区域增长的双阈值算法

1.选择两个阈值1T和2T.

2.把图像分割成三个区域:1R,包含所有灰度值低于阈值1T的像素;2R,包含所

有灰度值位于阈值

T和2T之间的像素;3R,包含所有灰度值高于阈值2T的像素.

1

3.查看分配给区域2R中的每一个像素.如果某一像素邻接区域1R,则把这一像素

重新分配给

R.

1

4.重复步骤3直到没有像素被重新分配.

5.把区域

R剩下的所有像素重新分配给3R.

2

在算法4.2中,区域

R是区域核,区域2R是边缘区(也称中间区或过渡区),区域3R

1

是背景.把边缘区域中邻接核区域的像素点归并到核区域,使核区域得到增长.核区域增长结束后,剩下哪些不属于核区域的像素为背景像素.区域增长的双重阈值算法体现了灰度相似性和空间接近性.边缘区的像素灰度值十分接近核区域像素灰度值是由于两个区域的像素点集合在直方图意义下是相邻的,而边缘区的像素在空间上接近核区域像素是由于它们是邻接点.

4.2.2 直方图方法的局限性

我们已经讨论了用图像直方图信息来选择用于图像分割的阈值.这一方法在物体图像具有恒定灰度值的情况下特别有用.如果场景中不同部分具有不同的照明,那么,即使图像中仅包含有一个物体,也无法用一个阈值来分割图像.在这种情况下,我们应该使用有效的分割方法,或者说,在每一个子图像中独立地选择阈值.现在也有一些基于图像直方图的启发式方法.但对于复杂的图像,这些方法仍然不能适用.

基于直方图的图像分割方法没有利用图像强度的空间信息,因此,在本质上存在着局限性.直方图仅描述了图像强度分布,因此具有不同灰度空间分布的图像可能具有类似的直方图.例如,用直方图无法区分随机分布的黑白点图像、黑白棋格图像和黑白各半的图像.直方图的全局特性限制了其在复杂图像中的应用.直方图完全没有考虑由于物体表面的连续性而使得物体图像点常常在空间上非常密集这一特点.

4.3 区域表示

区域有许多应用,也有许多种表示方法.不同的表示方法有着不同的应用.一些应用只需计算单个区域,而另一些则需要计算图像各区域的关系.本节将讨论几种区域表示方法并研究它们的特性.需要指出,区域完全可以表示成封闭轮廓,有关表示方法将在第七章讨论.大多数区域表示方法可以归纳为下面三种类型:阵列表示,层级表示,基于特征的区域表示.

4.3.1 阵列表示

区域表示的基本形式是一个与原始图像一样大小的阵列,阵列元素表示像素所属区域.这样,如果阵列元[i,j]具有标记a,那么对应的图像像素就属于区域a.这种表示的最简单例子是二值图像,其中每个像素属于区域0或属于区域1.

另一种表示方法是使用模板(mask)或比特位图(bitmap).每一个区域对应一个二值图像,称之为模板,表示图像中哪些像素属于该区域.把模板重叠在原始图像上,可以求得对应区域的强度特性.这种方法的一个优点是可以处理不确定性问题,即像素的区域属性不能确切地定义时,允许该像素属于一个或一个以上的区域.在一个以上的区域(模板)中,该像素值皆为1.阵列表示方法包含了图画或图像中的区域信息,而符号信息没有被明显地表示出来.

4.3.2 层级表示

图像可以用多种不同的分辨率来表示.显然,降低图像的分辨率可以降低阵列的尺寸,但要丢失一些信息,使得信息恢复工作比较困难.然而,降低分辨率可以降低对存储器容量和计算速度的要求.图像的层级表示可以是多分辨率表示.在许多应用中,首先在低分辨率下进行图像特性计算,然后在高分辨率上对图像某一选定区域再进行精细计算.多级图像表示也在图像浏览中得到了广泛地应用.下面我们给出两种常用的图像层级表示方法,金字塔型和四叉树型.

(1)金字塔型

n?阵列图像的金字塔型(pyramid)表示包含了原图像和原图像的k个递减图像,其n

中n是2的指数幂,其它图像分别是2/

4/n

n?, ..., 1

n?, 4/

2/n

1?阵列.在图像的金字塔型表示中,L层的像素是通过对1

+

L层的若干像素组合得到的.在顶层或0层,图像表示为单一像素;而底层则是原始图像或未被递减的图像.某一层的一个像素表示下一层的几个像素的合成信息.图4.5所示的是一幅图像及其金字塔型递减图像.其中金字塔型图像是通过求简单的2

2?邻域的均值得到.当然,构想其它策略来获取递减分辨率图像是完全可能的.同样,以非线性的方法来构造金字塔型表示方法也是可能的.需要补充说明的是,整

?.

个金字塔型图像满足维数为2的线性阵列)

2(2级数

(a)

(b)

图4.5 图像多分辨率表示示意图。(a)递减分辨率的图像是通过求

四个像素的平均值得到的;(b) 原图像为512×512的多分辨率表示(2)四叉树型

四叉树(quad tree)被认为是二值图像金字塔型表示的扩展,它包含了三种类型的节点:白、黑和灰度.一个四叉树是通过不断地分裂图像得到的.一个区域可以分裂成大小一样的四个子区域,如图4.6所示.对于每一个子区域,如果其所有点或者是黑的,或者是白的,则该区域不再进行分裂;但如果同时包含有黑白两种点,则认为该区域是灰度区域,可以进一步分裂成四个子区域.通过这种不断分裂得到的图像就可用树型结构表示.分裂过程不断进行,直到树中没有灰度区域.树结构中的每一个节点或者是一个树叶,或者包含有四个子节点,故称为四叉树.

四叉树在立体数据库中的应用在不断地增加.把一幅光栅图转化为一个四叉树以及把一个四叉树转化为一幅光栅图的算法也有若干.最近几年人们致力于用代码表示四叉树,以减少指针对存储空间的需求.

图4.6 建立四叉树.(a) 原始图像;(b) 把原始图像分裂成为四个子区域;(c)分裂图像(b)中的灰度区域成为四个子区域;(d) 分裂最后一个灰度区域,得到最后的四叉树.

4.3.3 基于特征的区域表示

一个区域可以使用其特征来表示.一些常用的特征有:最小外接矩形、中心、矩、欧拉数等.其它的图像特征也经常在图像区域表示中使用,如,灰度均值、方差等.另外,与应用有关的区域特征也可以用来表示区域.如果我们要解释一幅图像,则图像的表示还应该包含有相邻区域的关系.

4.3.4 图像分割数据结构

为了实现用于图像分割的区域合并和分裂算法(见4.4节),所生成的区域必须以某种数据结构保存.合并和分裂运算要使用区域之间的边界信息以及区域的总体特性,因此,为了更容易地处理区域特征,人们提出许多相应的数据结构.在本节,我们将讨论几种用于区

域合并和分裂的数据结构.

(1)区域邻接图

区域邻接图(region adjacency graphs, RAG )表示图像中区域与区域之间的关系,它主要强调由区域构成的图像的划分和每一个划分的特性.区域的不同特性可以存贮在不同的节点数据结构中.RAG (见图4.7)中的节点表示区域,节点之间的弧线表示区域的公共边界.RAG 强调区域的邻接性,因此在图像分割中起着关键的作用.RAG 形成的基本过程是:在进行基于灰度值等基元特性的初始分割后,将分割结果表示为RAG ,然后,可以再组合区域以得到更好的分割.算法4.3给出了产生RAG 的步骤.

算法4.3 区域邻接图生成算法

扫描阵列a 并在每一个像素角标],[j i 完成下列各步,

让 ],[1j i a r =,

查看像素在],[j i 的邻接像素],[l k . 对每一个邻近像素,进行下一步,

让],[2l k a r =, 如果21r r ≠,在区域邻接图的节点1r 和2r 之间增加一条弧线. 在某些场合,也可能用到区域邻近图的对偶图.在对偶图的表示中,节点表示边界,而弧线则表示被边界分割的区域.

图4.7 用于图像分割的区域邻接图.左图:已分割的图像,右图:区域邻接图

(2)超级网格

在某些应用中,希望把分割信息存贮在图像阵列中.在这种情况下表示边界会遇到一些问题.直观地看,边界应位于两个邻接区域的像素之间.然而,在图像阵列表示中,边界只能用实际的像素来表示.解决这一问题的方法是引进超级网格,如图4.8所示.如果原始图像是n n ?,那么超级网格就是)12()12(+?+n n 阵列.每一个像素被八个位于超级网格上的非像素点包围.非像素点用来表示两个像素之间的边界,以及边界的方向.这就大大简化了合并和分裂运算.

图4.8 超级网格区域表示.左:图像网格;中:传统的边界表示;右:超级网格表示

4.4 分裂和合并

具有恒定灰度的区域,阈值化算法的输出也常常包含有许多额外的区域.造成这一问题的主要原因是高频噪声和不同区域灰度值的缓变.

在基于灰度特征进行区域的初始分割后,所得到的区域可能需要进一步细化分割或修正处理.目前已经有了许多种处理的方法,其中的一些方法是使用了相关域知识,另一些方法则使用了图像处理知识.区域的进一步细化分割可以由人通过计算机界面交互地进行,也可以由计算机自动来完成.在计算机自动细化分割中,必须使用有关物体的特性、图像的特性等知识.

使用分裂和合并的组合算法可以实现自动细化分割运算.分裂和合并运算是通过合并属于同一物体的邻接区域来消除错误的边界和虚假的区域,同时可以通过分裂属于不同物体的区域来增添丢失的边界.

4.4.1 区域合并

合并运算就是把相似的区域组合起来.算法4.4是一种合并运算的高层算法,该算法可以用于各种相似区域的测量.

算法4.4 区域合并算法

使用阈值法(或其它简单的方法)进行图像的初始区域分割,然后进行连通域标记,

建立图像的RAG ,

对于图像中的每一个区域,完成下列步骤:

a .查看是否与邻接区域相似,

b .合并相似的区域,并修改RAG ,

重复步骤3,直到没有区域可以合并.

然而,当使用这一简单算法时,也可能遇上麻烦.例如,一幅图像具有三个邻接区域A 、B 、C ,相似性谓词分别确定A 和B 是相似的,B 和C 是相似的,但A 和C 不相似.在合并相似区域时,尽管A 和C 这两个区域并不相似,但分别合并A 、B 和B 、C 这样的局部决策会把三个区域合并成单一区域.在这种情况下,我们必须在区域合并前,考虑附加的区域特征.

合并算法中最重要的运算是确定两个区域的相似性.评判区域相似性方法有许多.广义地说,评判相似性的方法可以基于区域的灰度值,也可以基于区域边界的强弱性,也许还包含着这些区域的空间邻近性.

评价邻接区域的相似性有两种方法:

1. 比较它们的灰度均值.如果灰度均值无法用预先设置的灰度值来区分,则可以认

为它们相似,并确定为合并的候选区域. 这一方法的改进形式是使用曲面拟合方法,以便确定是否存在一个曲面来逼近区域.

2. 假设灰度值服从概率分布,根据相邻区域是否具有相同的概率分布函数考虑是否

合并它们.这一方法使用了假设-检验方法来评判邻接区域的相似性(下面将详细讨论).

(1)合并统计意义下的相似区域

这种方法将考虑两个相邻区域的统计特性,以便决定是否合并它们.假设图像中的区域具有恒定灰度值,并且被独立、加性和零均值高斯噪声污染,所以灰度值服从正态分布.假定两个相邻区域R 1和R 2分别包含有m 1,m 2个点,有两种可能的假设:

0H :两个区域属于同一物体.在这种情况下,两个区域的灰度值都服从单一高斯分布),(2

00σμ.

1H : 属于不同物体的区域.在这种情况下,每一个区域的灰度值服从不同的高斯分布

),(),(222211σμσμ和.

一般情况下,上面所述参数是未知的,但可以使用样本来估计.例如,当区域包含有n 个像素,每个像素灰度值为n i g i ,...,2,1,=, 服从正态分布: .21)(22)(σμσπ--=

i g i e g p (4.4)

这些参数的最大似然估计方程为: ∑==n i i g n 1

1?μ (4.5) ∑=-=n i i g n 1

22.)?(1?μσ (4.6) 在假设0H 下,所有的像素独立服从同一个分布),(200σu N .在0H 下的联合概率密度是:

2

)

(02)(012)(10021212

1021120212102

02121)2(1

.)2(121),(),,,(m m m m g m m m m i g m m i i m m e e e H g p H g g g p m m i i i +-+--++=--+=+=∑=

==

???+=∏∏σπσπσ

πσμσμ (4.7)

在假设H 1下,属于区域R 1的1m 个像素服从分布),(211σu N ,属于区域R 2的2m 个像素服从分布),(222σu N .在这一假设下,联合分布密度函数为:

2221112122112111)2(1)

2(1

)|,,,,,,(m m m m m m m m e e H g g g g g p --++=??????σπσπ (4.8)

似然比L 定义为两种假设下的概率密度之比: 2

121210

021121.)

|,,,()|,,,(m m m m H g g p H g g p L σσσ?=??????=

+ (4.9) 在上面方程中,参数210,,σσσ可由方程4.5 和4.6通过使用21m m +个像素估计得到,其中1m 、2m 分别是区域R 1和R 2的像素.如果似然比低于某一阈值,说明这两个区域可以合并为一个区域.

这一方法也可用于边缘检测.由于似然比可以指出两个区域是否分离,因此,也就指示出两个区域之间是否存在一条边界.对于边缘检测,一个像素点任意一侧区域的似然比可用来探测边缘的存在.

现在有许多似然比的修正公式,并在许多应用中起着十分重要的作用.似然比是在区域为恒定灰度值的假设下推导出来的,恒定灰度值(由于噪声)服从正态分布.也可以假设灰度分布不是恒定值,而是平面分布或是二次曲面分布,由此推导似然比,并可得到类似的应用.

4.4.2区域分裂

如果区域的某些特性不是恒定的,则区域应该分裂.基于分裂方法的图像分割过程是从最大的区域开始,在许多情况下,常常把整个图像作为起始分裂的图像.算法4.5给出了图像分裂的一种算法.

区域分裂前,必须明确二个问题,一是确定什么情况下区域的特性不恒定,二是如何分裂这样的区域,使得分裂后的子区域特性值恒定.这些问题与应用域有关,须在特定应用领域中有关区域特性的基础上讨论.在某些应用场合,灰度的变化量常常作为灰度值接近恒值程度的度量.在其它的一些应用中,可用拟合函数来逼近灰度值,拟合函数与实际的灰度值之差可作为区域相似度的度量.

分裂区域要比确定区域灰度值是否恒定难的多.一种用于区域分割的最佳边界确定方法是在区域内考虑边缘强度测量.最容易的区域分裂方法是把区域分割成固定数量的等尺度区域,称为常规分解方法.在4.3.2节讨论的四叉树图像表示方法就是常规分解方法的一个例子.

算法4.5 区域分裂算法

形成初始区域

对图像的每一个区域,连续执行下面两步:

(a )计算区域灰度值方差

(b )如果方差值大于某一阈值,则沿着某一合适的边界分裂区域.

需要指出,四叉树方法不能直接用于非二值图像的分割,必须经过修正后才能使用.也就是说,决定区域是否分裂的基础不是黑白区域,而是图像方差.一般说来,区域分裂比其合并更困难.

4.4.3分裂和合并

分裂和合并运算可以同时进行,也就是说,用阈值化方法预分割后,连续进行分裂和合并,最后得到图像的精确分割.分裂和合并组合算法对分割复杂的场景图像十分有用.引入应用域知识,可以提高分裂和合并算法的有效性.

假定把一幅图像分割成为若干区域,形成区域集,}{k R ,m k ,,2,1 =,按照有关区域的谓词逻辑P 的性质,区域上的所有像素将是一致的.谓词表示了区域中像素之间的相似性.例如,在区域中使用灰度方差来定义谓词:

?

??=其它方差小于某一值01)(R P (4.10) 区域分割的分裂和合并算法见算法4.6

算法4.6 区域分割的分裂与并合算法:

设整幅图像为初始区域

选一个区域R ,如果)(R P 错误,则把该区域分裂成四个子区域

考虑图像中任意两个或更多的邻接子区域n R R R ,,21???,

如果)(11n R R R P ???正确,则把这n 个区域合并成一个区域.

重复以上各步,直到不能再进行区域分裂和合并.

4.5 区域增长

在许多图像中,单个区域内的灰度值不是完全恒定的,因此需要更复杂的算法来进行

图像分割.其中最好的算法是那些基于如下假设的算法,即图像可以划分成区域,而区域可以用简单函数模型化.将这种想法用于图像分割是很自然的.

由第4.2节提出的分割问题可导出如下算法:寻找初始区域核,并从区域核开始,逐渐增长核区域,形成满足一定约束的较大的区域.例如,一致性谓词是基于区域灰度的平面或二次曲面函数拟合.然而,在一般情况下,一致性谓词是基于图像区域的特征,如,平均强度、方差、纹理和颜色等.这一算法概括在算法4.7.

该算法首先把图像分割成n n ?个区域,其中n 的典型值为5到9.如果一个平面函数或一个二次曲面函数可以同时拟合两个相邻区域,则并合这两个区域.平面和二次曲面模型是一些基函数的线性组合,其中基函数包含了各阶双变量多项式.所以,模型可以表示为:

∑≤+=

m j i i i ij y x a

m a y x f ),,,( (4.11) 其中模型的阶数m 限制在02≤≤m 也就是说,区域的模型只有平面和二次曲面函数. 一致性谓词是基于区域中点与区域模型之间的距离: ∑∈=

R y c m a y x d m a R ,22),,,(),,(χ (4.12)

其中距离是通常的 欧几里德距离:

.)],,,(),([),,,(22m a y x f y x g m a y x d -= (4.13)

在图像平面中,点(x, y)处的灰度值g(x, y)是图像在那一位置的像素灰度值.已知点集R ,求解模型的阶数m 和模型参数a 使得误差函数χ2(,,)R a m 最小.实际上这是一个最小二乘法问题,可以通过奇异值分解求解.关于奇异值分解的详细讨论见文献[196].

算法4.7 基于平面和二次曲面模型的区域增长算法

1. 把图像划分成初始区域核

2. 用平面模型拟合每一个区域核.如果χ2误差足够小,则接收这一区域核及其模型,否则,拒绝接收.

3. 对每一个区域,通过区域模型向邻接区域外插,求取与该区域兼容的所有点.兼容点定义为:

}4),(),,,(|),{()

()(2)(邻域的一个是且-≤=k i k i k i C R y x m a y x d y x C ε 其中ε是兼容阈值

4. 如果没有兼容点,则增加模型阶数,m<--m+1.如果模型阶数大于最大的模型阶数,停止区域增长;否则,回到第三步,继续区域增长.

5. 形成新的区域,重新用相同阶数的模型拟合新区域,计算拟合最佳度),,()1(2m a R k i +χ.

6. 计算区域模型的新老拟合最佳度之差:

),,(),,()()(2)1()1(2)1(k i k k i k k R a m R a m χχρ-=+++

7. 如果1)1(T k <+ρ, 回到第三步,继续区域增长.

8. 增加模型阶数,1+←m m .如果模型阶数大于最大的模型阶数,停止区域增长.

9. 用新的模型阶数再拟合区域模型.如果拟合误差增加,接收新的模型阶数,回到第3步,继续区域增长,否则,停止区域增长.

在对组合点集进行曲面拟合前,必须检测点对曲面片的兼容性,主要原因是最小二乘法拟合对局外点(outlier )十分敏感.如果在拟合前,把一个局外点加到区域中,则曲面片会由于局外点发生严重变形,以至于无法拟合那些真正属于区域的点.

一般说来,事先不可能知道如何把一幅图像分割成几个可用明显不同的曲面片模型化的区域,因为这是分割本身要解决的问题,但是求取区域核的方法有许多,可以使用严格的方法来保守地求取区域核,可以使用保守的阈值化方法求取区域核,可以使用域知识和图像的特性建立复杂的方法来求取初始区域核,例如在距离图像中,微分几何特性可以用来求取初始区域核.使用一些图像的一般特性来识别这些区域核也是一种有效的方法,比如,可以首先把图像分割成77?的区域核,然后用曲面片拟合这些区域核,根据曲面片拟合的2χ误差

函数决定是否接收这一区域核.如果一个77?曲面片被拒绝,那么可以用一个55?曲面片来代替,以便得到高的分辨率.区域增长是通过接收兼容点来实现的.如果区域的曲面片可以扩展到包容距离曲面片不远的一些点,则这些点与区域是兼容的,得到区域兼容点后,曲面片可以重新拟合由原区域和兼容点共同组成的新区域.

一个点可能属于一个或一个以上的区域,这一不确定性问题通过选择模型后处理过程来解决.在区域增长的经典方法中,要求每一个点最多只能属于一个区域.体现这一约束的途径是修改现有算法,使得一个区域接收来自另一个区域的点可以同时改善这两个区域曲面片模型的拟合效果.更精确地说,把一个点从一个区域分配到另一个区域的条件是这两个区域的表面拟合组合误差最低.

早先讨论的经典区域分割方法可以认为是区域增长技术,其中曲面片仅限于常数.换句话说,所用的假设条件是图像中的区域几乎是常数,图像可以划分成分段常数图像强度区域.推广这一假设条件到变化的图像强度场合,可以得到更复杂的分割算法,可以处理由于阴影而产生的更真实的图像强度变化.

北京理工大学《数据结构与算法设计》实验报告实验四

《数据结构与算法设计》 实验报告 ——实验四 学院: 班级: 学号: 姓名:

一、实验目的 1. 通过实验实践、巩固线性表的相关操作; 2. 熟悉VC 环境,加强编程、调试的练习; 3. 用C 语言实现线性表的抽象数据类型,实现线性表构造、插入、取数据等基本操作; 4. 理论知识与实际问题相结合,利用上述基本操作实现三种排序并输出。 二、实验内容 从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={|,1,2,,,0}i i a a ElemSet i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: InPut(SqList &L) 操作结果:构造一个线性表L 。 OutPut(SqList L) 初始条件:线性表L 已存在。 操作结果:按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序, 调用OutPut(L)函数显示排序结果。调用QuickSort(L)函数进行交换排序,调用OutPut(L) 函数显示排序结果。调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序 结果。 ⑶模块调用关系 由主函数模块调用创建顺序表模块,排序模块与显示输出模块。

北京理工大学2012-2013学年第一学期工科数学分析期末试题(A卷)试题2012-2(A)

1 北京理工大学2012-2013学年第一学期 工科数学分析期末试题(A 卷) 一. 填空题(每小题2分, 共10分) 1. 设?????<≥++=01arctan 01)(x x x x a x f 是连续函数,则=a ___________. 2. 曲线θρe 2=上0=θ的点处的切线方程为_______________________________. 3. 已知),(cos 4422x o bx ax e x x ++=- 则_,__________=a .______________=b 4. 微分方程1cos 2=+y dx dy x 的通解为=y __________________________________. 5. 质量为m 的质点从液面由静止开始在液体中下降, 假定液体的阻力与速度v 成正比, 则质点下降的速度)(t v v =所满足的微分方程为_______________________________. 二. (9分) 求极限 21 0)sin (cos lim x x x x x +→. 三. (9分) 求不定积分?+dx e x x x x )1arctan (12. 四. (9分) 求322)2()(x x x f -=在区间]3,1[-上的最大值和最小值. 五. (8分) 判断2 12arcsin arctan )(x x x x f ++= )1(≥x 是否恒为常数. 六. (9分) 设)ln(21arctan 22y x x y +=确定函数)(x y y =, 求22,dx y d dx dy . 七. (10分) 求下列反常积分. (1);)1(1 22?--∞+x x dx (2) .1)2(1 0?--x x dx 八. (8分) 一垂直立于水中的等腰梯形闸门, 其上底为3m, 下底为2m, 高为2m, 梯形的上底与水面齐平, 求此闸门所受 到的水压力. (要求画出带有坐标系的图形) 九. (10分) 求微分方程x e x y y y 3)1(96+=+'-''的通解. 十. (10分) 设)(x f 可导, 且满足方程a dt t f x x x f x a +=+?)())((2 ()0(>a , 求)(x f 的表达式. 又若曲线 )(x f y =与直线0,1,0===y x x 所围成的图形绕x 轴旋转一周所得旋转体的体积为,6 7π 求a 的值. 十一. (8分) 设)(x f 在]2,0[上可导, 且,0)2()0(==f f ,1sin )(1 21 =?xdx x f 证明在)2,0(内存在ξ 使 .1)(='ξf

孙志忠北京理工大学偏微分方程数值解上机作业

偏微分方程数值解大作业

目录 第一题 (3) 第二题 (7) 第三题 (16) 第四题 (20) 第五题 (26) 第六题(附加题1) (39) 第七题(附加题2) (45) 第八题(附加题3) (51)

第一题 习题1 3. (1)解曲线图 图1 (2)误差曲线图

图2 (3)表格 表1 部分点处精确解和取不同步长时所得的数值解 表2 取不同步长时部分结点处数值解的误差的绝对值和数值解的最大误差

(4)MATLAB源代码 M=64; a=0; b=pi/2; h=(b-a)/M; x=[a+h:h:b-h]; u=zeros(M-1,M-1); u(1,1)=(2/h^2)+(x(1)-1/2)^2; u(1,2)=-(1/h^2); u(M-1,M-1)=(2/h^2)+(x(M-1)-1/2)^2; u(M-1,M-2)=-(1/h^2); for i=2:M-2 u(i,i-1)=-(1/h^2); u(i,i)=(2/h^2)+(x(i)-1/2)^2; u(i,i+1)=-(1/h^2); end f=zeros(M-1,1) f(1)=(x(1).*x(1)-x(1)+5/4).*sin(x(1)); f(M-1)=(x(M-1).*x(M-1)-x(M-1)+5/4).*sin(x(M-1))+1/h^2; for j=2:M-2 f(j)=(x(j).*x(j)-x(j)+5/4).*sin(x(j)); end

y=inv(u)*f; true=sin(x); plot(x,y'-true)

北京理工大学数据结构编程练习答案

1.一元多项式相加(10分) 成绩: 10 / 折扣: 0.8 题目说明: 编写一元多项式加法运算程序。要求用线性链表存储一元多项式(参照 课本)。该程序有以下几个功能: 1. 多项式求和 输入:输入三个多项式,建立三个多项式链表Pa、Pb、Pc (提示:调用CreatePolyn(polynomial &P,int m)。 输出:显示三个输入多项式Pa、Pb、Pc、和多项式Pa+Pb、多项式Pa+Pb+Pc (提示:调用AddPolyn(polynomial &Pa, polynomial Pb), 调用 PrintPolyn(polynomial P))。 0. 退出 输入: 根据所选功能的不同,输入格式要求如下所示(第一个数据是功能选择编号,参见测试 用例): ? 1 多项式A包含的项数,以指数递增的顺序输入多项式A各项的系数(整数)、指数(整数) 多项式B包含的项数,以指数递增的顺序输入多项式B各项的系数(整数)、指数(整数) 多项式C包含的项数,以指数递增的顺序输入多项式C各项的系数(整数)、指数(整数) ?0 ---操作终止,退出。 输出: 对应一组输入,输出一次操作的结果(参见测试用例)。 ? 1 多项式输出格式:以指数递增的顺序输出: <系数,指数>,<系数,指数>,<系数,指数>,参见测试用例。零多项式的输出格式为<0,0> ?0 无输出 1.

#include #include using std::cin; using std::cout; using std::endl; struct date { int a; int b; struct date* pnext; }; typedef struct date DATE; typedef struct date* PDATE; void output(PDATE p) { int f=0; p=p->pnext; while(p!=NULL) { if(p->a!=0) { f=1; cout<<"<"<a<<","<b<<">"; if(p->pnext==NULL) cout<pnext; } if(f==0) cout<<"<0,0>"<

北京理工大学2017-2018学年工数上期末试题A及标准答案

课程编号:H0172103 北京理工大学2017-2018学年第一学期 工科数学分析(上)期末试题(A 卷) 座号 _______ 班级_____________ 学号_____________ 姓名_____________ (试卷共6页,十个大题. 解答题必须有过程. 试卷后面空白纸撕下做草稿纸. 试卷不得拆散.) 1.若 e x x kx x 1 )2( lim =-∞ → ,则=k . 2.已知,arctan 2111ln 41x x x y --+= 则=dx dy . 3. =-+?dx xe x e x x 1 02 ) 1() 1( . 4 . =?xdx x sin 2 . 5. 设x y y cos =+',则=y . 二、计算题(每小题5分,共20分) 1.求极限 ).2 sin 211(sin lim 3n n n n -∞→ 2. 设 x x y x 2sin sin +=,求dy . 3. 计算 dx x x x x ? -++1 1 2 211cos 2-. 4.求)cos(y x dx dy +=的通解. 三、(8分)已知0)-1(lim 2 =-+-+∞ →b ax x x x ,试确定常数a 和b 的值. 四、(6分)已知,...).2,1)((21,0,011=+= >>+n b b b b b b n n n 证明: 数列{}n b 极限存在;并求此极限. 五、(8分)求函数2) 1(42 -+= x x y 的单调区间和极值,凹凸区间和拐点,渐近线. 六、(8分)设曲线2x y =,x y =围成一平面图形D .

(1) 求平面图形D 的面积; (2) 求平面图形D 绕y 轴旋转所得旋转体的体积. 七、(8分)设一长为l 的均匀细杆,线密度为μ,在杆的一端的延长线上有一质量为m 的质点,质点与该端的距离为a . (1)求细杆与质点间的引力; (2)分别求如果将质点由距离杆端a 处移到b 处(b a >)与无穷远处时克服引力所 做的功. 八、(8分)设)(x f 在]1,1[-上具有三阶连续导数,且,0)0(,1)1(,0)1('===-f f f 证明在开区间)1,1(-内至少存在一点ξ,使3)()3(=ξf . 九、(8分)设?-+ =x x dt t f t x xe x f 0)()()(, 其中)(x f 连续,求)(x f 的表达式. 十、(6分)已知)(x f 在闭区间[]6,1上连续,在开区间)6,1(内可导,且 ,5)1(=f ,1)5(=f .12)6(=f 证明:存在)6,1(∈ξ,使 22)()(=-+'ξξξf f 成立. 北京理工大学2017-2018学年第一学期《工科数学分析》(上)期末试题(A 卷) 标准答案及评分标准 2018年1月12日 一、填空(每小题4分,共20分) 1. 21 2.42 1x x - 3. )(,不收敛+∞∞ 4 . C x x x x x +++-cos 2sin 2cos 2 5. x ce x x y -++= )cos (sin 2 1 二、计算题(每小题5分,共20分) 1. 解:)2 sin 211(sin lim 3x x x x -∞→ 3 12sin 211sin lim x x x x -=∞→ x t 1=令 30) 2sin(21 sin lim t t t t -=→ …………. 2分 2 0cos 1sin lim t t t t t -?=→21= …………. 4分 2 1 )2sin 211(sin lim 3=-∴∞→n n n n …………. 5分

北京理工大学数学专业数值计算方法Ⅰ期末试题2010级B卷(MTH17170)

一. (10分) 用三角分解(LU 分解)求解下方程组,要求写出L,U 矩阵: 1232644145361182x x x -?????? ? ? ? -= ? ? ? ? ? ?-???? ??. 二. (10分) 已知矩阵6 37398785A -?? ? =- ? ?--?? ,求1cond()A 和cond()A ∞,要求计算过程保留三位 有效数字,并简要分析所得结果. 三. (10分) 设矩阵1001005a A b b a ?? ? = ? ??? ,且0det()A ≠,试求用,a b 表示的求解线性方程组 Ax d =的Jacobi 及Gauss-Seidel 迭代法收敛的充分必要条件. 四. (10分) 试确定下求积公式中的待定参数,使求积公式的代数精确度尽量高,并指明所确定的求积公式具有的代数精确度 []20 002 '' ()()()()()h h f x dx f f h h f f h α??≈ ++-??? . 五. (10分) 已知非线性方程240x x +-=在014.x =附近有根,试构造一种收敛的迭代格式,并说明理由. 六. (10分) 求形如e (,)bx y a a b =为常数的经验公式,使它能和下表给出的数据相拟合 x 1 2 3 4 5 6 7 8 y 15.3 20.5 27.4 36.6 49.1 65.6 87.8 117.6 七. (10分) 分别用Euler 法和改进Euler 法求解下问题的数值解,取01.h =,计算过程保留四位小数. 00201',., (). y x y x y =+≤≤?? =? 八. (15分) 用下数据表构造不超过3次的插值多项式,建立导数型插值误差公式,并证明.

北理工889数据结构考纲

889数据结构 考试内容: 数据结构主要考查考生以下几个方面: 1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为: 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 (一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 三、树与二叉树 (一)树的概念 (二)二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 (三)树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树的应用 1.等价类问题 2.哈夫曼(Huffman)树和哈夫曼编码 四、图 (一)图的概念 (二)图的存储及基本操作 1.邻接矩阵法

2.邻接表法 (三)图的遍历 1.深度优先搜索 2.广度优先搜索 (四)图的基本应用及其复杂度分析 1.最小(代价)生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 (一)查找的基本概念 (二)顺序查找法 (三)折半查找法 (四)B-树 (五)散列(Hash)表及其查找 (六)查找算法的分析及应用 六、内部排序 (一)排序的基本概念 (二)插入排序 1.直接插入排序 2.折半插入排序 (三)起泡排序(bubble sort) (四)简单选择排序 (五)希尔排序(shell sort) (六)快速排序 (七)堆排序 (八)二路归并排序(merge sort) (九)基数排序 (十)各种内部排序算法的比较 (十一)内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构(C语言版)严蔚敏吴伟民清华大学出版社

北京理工大学 离散数学I 期末测试

课程编号:MTH07034 北京理工大学2015-2016学年第二学期 2015级离散数学期末试题(A卷) 班级学号姓名成绩 1.选择题(共10题, 每题1分) 1)设p:我有时间,q:我去旅游,下面哪个命题可以符号化为p→q?( ) A. 除非我有时间,我才去旅游. B. 除非我去旅游,否则我没时间. C. 只有我有时间,我才去旅游. D. 我去旅游仅当我有时间. 2)设C(x)表示x是运动员,G(x)表示x是强壮的,则命题“没有运动员不是 强壮的”符号化为哪个公式?( ) A. ??x(C(x)∧?G(x)) B.??x(C(x)→?G(x)) C. ??x(C(x)∧?G(x)) D.??x(C(x)→?G(x)) 3)设F(x)表示x是火车,G(y)表示y是汽车,H(x,y)表示x比y快,则命题“有 的汽车比所有的火车快”符号化为下面哪个公式?( ) A. ?y(G(y)→?x(F(x)∧H(x,y))) B. ?y(G(y)∧?x(F(x)→H(y,x))) C. ?x?y(G(y)→(F(x)∧H(x,y))) D. ?y(G(y)→?x(F(x)→H(x,y))) 4)下列推理哪个是不正确的?( ) A. 前提:?p∨ (q→r), ?s∨p, q结论:s→r B. 前提:(p∨q)→ (r∧s), (s∨t)→u结论:p→u C. 前提:(p∧q) →r, r→s, ?s∧p结论:q D. 前提:p→ (q→r), p , q结论:r∨s 5)下面哪个命题公式是永真式?( ) A. (p∨q) →?r B. (q→p)∧q→p C. ?(?p∨q)∧q

北京理工大学2008级数值分析试题及答案

课程编号:12000044 北京理工大学2009-2010学年第二学期 2008级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意:① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上,计算题答在答题纸上。 一、 填空题(每空2分,共30分) 1. 设函数f (x )区间[a ,b]内有二阶连续导数,且f (a )f (b )<0, 当 时,用双点 弦截法产生的解序列收敛到方程f (x )=0的根。 2. n 个求积节点的插值型求积公式的代数精确度至少为______次,n 个求积节点的高斯 求积公式的代数精度为 。 3. 已知a =3.201,b =0.57是经过四舍五入后得到的近似值,则a ?b 有 位有 效数字,a +b 有 位有效数字。 4. 当x =1,-1,2时,对应的函数值分别为f (-1)=0,f (0)=2,f (4)=10,则f (x )的拉格朗 日插值多项式是 。 5. 设有矩阵?? ????-=4032A ,则‖A ‖1=_______。 6. 要使...472135.420=的近似值的相对误差小于0.2%,至少要取 位有效数字。 7. 对任意初始向量0()X 和常数项N ,有迭代公式1()()k k x Mx N +=+产生的向量序列 {}() k X 收敛的充分必要条件是 。 8. 已知n=3时的牛顿-科特斯系数,8 3,81)3(1) 3(0 ==C C 则=) 4(2C ,=) 3(3C 。 9. 三次样条函数是在各个子区间上的 次多项式。 10. 用松弛法 (9.0=ω)解方程组??? ??=+-=++--=++3 1032202412 25322 321321x x x x x x x x x 的迭代公式是 。

北京理工大学2013级数据结构B试题(A卷)-答案

一、选择题 1、从逻辑结构上可以把数据结构分为【 C 】。 A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 2、在一个长度为n的顺序存储的线性表中,向第i个元素(1≤i≤n+1)之前插入一个新元素时,需要从后向前依次后移【 B 】个元素。 A、n-i B、n-i+1 C、n-i-1 D、i 3、链表结构不具有下列【 B 】特点。 A、插入和删除无需移动元素 B、可随机访问链表中的任意元素 C、无需实现分配存储空间 D、所需空间与结点个数成正比。 4、在一个单链表中,已知q所指结点是p所指结点的前驱结点,若在q和p之间插入s结点,则执行【 C 】。 A、s->next = p->next; p->next = s; B、p->next = s->next; s->next = p; C、q->next = s; s->next = p; D、p->next = s; s->next = q; 5、一个栈的入栈序列是1,2,3,4,5,则栈不可能输出的序列是【C 】。 A、54321 B、45321 C、43512 D、12345 6、判断一个队列Q(元素最多为M个)为空的条件是【 C 】。 A、Q->rear – Q->front = M B、Q->rear – Q->front -1 ==M C、Q->rear == Q->front D、Q->rear + 1 == Q->front 7、在一个链队列中,假设f和r分别指向队首和队尾,则插入s所指结点的运算是【A 】。 A、r->next = s; r=s; B、f->next = s; f=s; C、s->next = r; r=s; D、s->next = f; f=s; 8、深度为5的二叉树至多有【 A 】个结点。 A、31 B、32 C、16 D、10 9、在一非空二叉树的中序遍历序列中,根结点的右边【A 】。

北京理工大学数学专业数值计算方法Ⅰ期末试题2013级B卷,2015级A卷(MTH17170)

北京理工大学2014-2015学年第二学期 2013级数值代数与数值分析期末试题B 卷 一、(10 31.953=有5位有效数字,试求方程233204 x x -+ =的两个根,使它们至少有4位有效数字。 二、(10分)已知矩阵100024024A ?? ?= ? ?-?? ,求A 的1-范数,∞-范数,F-范数,2-范数。 三、(15分)用LU 分解求解方程组12321374321261513x x x ?????? ??? ?= ??? ? ??? ??????? ,要求写出LU 矩阵。 四、(15分)用迭代公式()1,0,1,k k k x x Ax b k α+=+-= 求解方程组12323121x x ??????= ? ? ?-???? ??,求α的范围使迭代收敛。 五、(10分)用插值多项式理论证明:00n n i k k i x k x i i k ==≠??- ?= ?- ???∑∏。 六、(10分)已知下面的数据表,写出用最小二乘法求形如2 y a bx =+的经验公式的正则方程组。 七、(15分)已知方程1552sin 0x x -+=在03x =附近有根,试构造一种收敛的迭代格式,并说明理由。 八、( 3次的插值多项式,建立导数型插值误差公式,并证明。 注:本课程自2014级起改为大二上学期必修和大三上学期选修两部分,名称分别为数值计算方法Ⅰ和数值计算方法Ⅱ。

北京理工大学2016-2017学年第一学期 2015级数值计算方法Ⅰ期末试题A 卷 一、(10 30.952=有5位有效数字,试求方程233104 x x -+ =的两个根,使它们至少有4位有效数字。 二、(10分)已知矩阵100024024A ?? ?= ? ?-?? ,求A 的1-范数,2-范数,1-条件数,2-条件数。 三、(15分)用LU 分解求解方程组123212124312261526x x x ?????? ??? ?= ??? ? ??? ??????? ,要求写出LU 矩阵。 四、(10分)已知{}k α收敛于a ,且1lim 0k k k a c a αα+→∞-=≠-,试构造一种收敛速度更快的序列。 五、(15分)用收敛的迭代法解下列线性方程组,要求写出迭代矩阵。 (1)12312251112022143x x x -?????? ??? ?= ??? ? ??? ??????? ; (2)12311116101210211012x x x --?????? ??? ?-= ??? ? ??? ?-??????。 六、(15分)用迭代公式()1,0,1,k k k x x Ax b k α+=+-= 求解方程组12323121x x ??????= ? ? ?-??????,求α的范围使迭代收敛。 七、(10分)用插值多项式理论证明:00n n i k k i x k x i i k ==≠??- ?= ?- ???∑∏。 八、(20分)用下表数据构造不超过3次的插值多项式,建立导数型插值误差公式,并证明。 2015级题目的分值不保证正确。

北理工《实用数据结构与算法》在线作业

北理工《实用数据结构与算法》在线作业 一、单选题: 1.(单选题)当两个元素比较出现反序时就相互交换位置的排序方法称为()。 (满分 A归并排序 B选择排序 C交换排序 D插入排序 正确:C 2.(单选题)设数组Data[0..m]作为循环队列SQ的存储空间,front为队头指针,rear为队尾指针,则执行出队操作的语句为() (满分 Afront=front+1 Bfront=(front+1)%m Crear=(rear+1)%m Dfront=(front+1)%(m+1) 正确:D 3.(单选题)快速排序方法在()情况下最不利于发挥其长处。 (满分 A被排序的数据量太大 B被排序数据中含有多个相同值 C被排序数据已基本有序 D被排序数据数目为奇数 正确:C 4.(单选题)具有65个结点的完全二叉树其深度为(根的层次号为1)()。 (满分 A8 B7 C6 D5 正确: 5.(单选题)稀疏矩阵一般的压缩存储方法有两种,即()。 (满分 A二维数组和三维数组 B三元组表和散列表 C三元组表和十字链表 D散列表和十字链表 正确: 6.(单选题)从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为()排序法。 (满分:) A插入 B选择 C交换 D二路归并 正确: 7.(单选题)下列排序方法中效率最高的排序方法是()。 (满分:) A起泡排序 B堆排序 C快速排序 D直接插入排序 正确: 8.(单选题)栈与一般的线性表的区别在于()。 (满分:) A数据元素的类型不同 B运算是否受限制 C数据元素的个数不同

北京理工大学 级数值分析试题及答案

课程编号:12000044 北京理工大学2010-2011学年第一学期 2009级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 注意:① 答题方式为闭卷。 ② 可以使用计算器。 请将填空题和选择题的答案直接填在试卷上,计算题答在答题纸上。 一、 填空题 (2 0×2′) 1. 设x =0.231是精确值x *=0.229的近似值,则x 有 位有效数字。 2. 设 ?? ????-=? ?????-=32,1223X A ,‖A ‖∞=___ ____,‖X ‖∞=__ _____, ‖AX ‖∞≤____ ___ (注意:不计算‖AX ‖∞的值) 。 3. 非线性方程f (x )=0的迭代函数x =?(x )在有解区间满足 ,则使用该迭代函 数的迭代解法一定是局部收敛的。 4. 若f (x )=x 7-x 3+1,则f [20,21,22,23,24,25,26,27]= , f [20,21,22,23,24,25,26,27,28]= 。 5. 区间[a ,b ]上的三次样条插值函数S (x )在[a ,b ]上具有直到 阶的连续导数。 6. 当插值节点为等距分布时,若所求节点靠近首节点,应该选用等距节点下牛顿差商 公式的 (填写前插公式、后插公式或中心差分公式),若 所求节点靠近尾节点,应该选用等距节点下牛顿差商公式的 (填写前插公式、后插公式或中心差分公式);如果要估计结果的舍入误差,应该选用插值公式中的 。 7. 拉格朗日插值公式中f (x i )的系数a i (x )的特点是:=∑=n i i x a 0)( ;所以当 系数a i (x )满足 ,计算时不会放大f (x i )的误差。 8. 要使 20的近似值的相对误差小于0.1%,至少要取 位有效数字。 9. 对任意初始向量X (0)及任意向量g ,线性方程组的迭代公式x (k +1)=Bx (k )+g (k =0,1,…)收 敛于方程组的精确解x *的充分必要条件是 。 10. 由下列数据所确定的插值多项式的次数最高是 。

2019 北京理工大学 889《数据结构》 考试大纲

2019年北京理工大学889《数据结构》考试大纲 考试内容: 数据结构主要考查考生以下几个方面: 1.理解数据结构的基本概念;掌握数据的逻辑结构、存储结构及其差异,以及各种基本操作的实现。 2.掌握基本的数据处理原理和方法的基础上,能够对算法进行设计与分析。 3.能够选择合适的数据结构和方法进行问题求解。 应掌握的具体内容为: 一、线性表 (一)线性表的定义和基本操作 (二)线性表的实现 1.顺序存储结构 2.链式存储结构 3.线性表的应用 二、栈、队列和数组 (一)栈和队列的基本概念 (二)栈和队列的顺序存储结构 (三)栈和队列的链式存储结构 (四)栈和队列的应用 (五)特殊矩阵的压缩存储 三、树与二叉树 (一)树的概念 (二)二叉树 1.二叉树的定义及其主要特征 2.二叉树的顺序存储结构和链式存储结构 3.二叉树的遍历 4.线索二叉树的基本概念和构造 5.二叉排序树 6.平衡二叉树 (三)树、森林 1.书的存储结构 2.森林与二叉树的转换 3.树和森林的遍历 (四)树的应用 1.等价类问题 2.哈夫曼(Huffman)树和哈夫曼编码 四、图 (一)图的概念

(二)图的存储及基本操作 1.邻接矩阵法 2.邻接表法 (三)图的遍历 1.深度优先搜索 2.广度优先搜索 (四)图的基本应用及其复杂度分析 1.最小(代价)生成树 2.最短路径 3.拓扑排序 4.关键路径 五、查找 (一)查找的基本概念 (二)顺序查找法 (三)折半查找法 (四)B-树 (五)散列(Hash)表及其查找 (六)查找算法的分析及应用 六、内部排序 (一)排序的基本概念 (二)插入排序 1.直接插入排序 2.折半插入排序 (三)起泡排序(bubble sort) (四)简单选择排序 (五)希尔排序(shell sort) (六)快速排序 (七)堆排序 (八)二路归并排序(merge sort) (九)基数排序 (十)各种内部排序算法的比较 (十一)内部排序算法的应用 题型和分值 填空题20分、选择题30分、问答题70分、算法题30分 参考书目 数据结构(C语言版)严蔚敏吴伟民清华大学出版社

北理工数值分析大作业

数值分析上机作业

第 1 章 1.1计算积分,n=9。(要求计算结果具有6位有效数字) 程序: n=1:19; I=zeros(1,19); I(19)=1/2*((exp(-1)/20)+(1/20)); I(18)=1/2*((exp(-1)/19)+(1/19)); for i=2:10 I(19-i)=1/(20-i)*(1-I(20-i)); end format long disp(I(1:19)) 结果截图及分析:在MATLAB中运行以上代码,得到结果如下图所示:当计算到数列的第10项时,所得的结果即为n=9时的准确积分值。取6位有效数字可得.

1.2分别将区间[-10.10]分为100,200,400等份,利用mesh或surf 命令画出二元函数 z= 的三维图形。 程序: >> x = -10:0.1:10; y = -10:0.1:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长0.1') >> x = -10:0.2:10; y = -10:0.2:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长 0.2') >>x = -10:0.05:10; y = -10:0.05:10; [X,Y] = meshgrid(x,y); Z = exp(-abs(X))+cos(X+Y)+1./(X.^2+Y.^2+1); subplot(2,2,1); mesh(X,Y,Z); title('步长0.05')

北京理工大学2019年成教期末考试题

2016-2017第一学期模拟题一 闭卷120分钟,每题2分,满分100分。 1. 单选:图灵在计算机科学方面的主要贡献有两个:一是建立图灵机模型,奠定了()理论的基础;二是提出图灵测试,阐述了机器智能的概念。 A 可计算; B 可推导; C 可进化; D 可预知 2. 单选:冯.诺依曼在EDVAC中采用了()的概念,以此为基础的各类计算机统称为冯.诺依曼计算机。 A 存储数据; B 核心计算; C 存储程序; D 进程 3. 单选:目前,大家公认的第一台电子计算机是在1946年2月由宾夕法尼亚大学研制的()。 A ALPHA; B BETA; C ENIAC; D FAST 4. 单选:第三代电子计算机是()计算机。 A 电子管; B 晶体管; C 逻辑管; D 集成电路 5. 单选:1971年intel公司的马西安.霍夫,制成世界上第一片4位微处理器intel ()。 A 4004; B 8086; C 6800; D 8051 6. 单选:计算机由5个基本部分构成:运算器、()、存储器、输入设备、输出设备。 A 控制器; B 计时器; C 寄存器; D 计数器 7. 单选:运算器的主要功能是进行算术和()运算。 A 关系; B 逻辑; C 布尔; D 顺序 8. 单选:各种内存储中,断电后,RAM中的信息将全部消失,而()中的信息不会丢失。 A CACHE; B HDD; C SSD; D ROM 9.

单选:外部存储器,又称为外存或者辅存,主要用来存放()的程序和数据。 A 暂时不用; B 正在执行; C 容量较大; D 格式复杂 10. 单选:()既属于输入设备,又属于输出设备。 A 显示器; B 扫描仪; C 触摸屏; D 打印机 11. 单选:一台计算机的所有指令的集合称为该计算机的()。 A 程序系统; B 指令系统; C 运算系统; D 核心系统 12. 单选:某进制数数制中每一固定位置对应的单位值称为()。 A 幂; B 位权; C 指数; D 尾数 13. 单选:不同数制都使用()表示法,即处于不同位置的数码所代表的值不同,与它所在位置的权值有关。 A 位置; B 补码; C 内码; D 反码 14. 单选:1001B转换为十进制数为()。 A 7; B 8; C 9; D 10 15. 单选:11010111B转换为十进制数为()。 A 127; B 215; C 512; D 217 16. 单选:1011.11B转换为十进制数为()。 A 113; B 0B.3; C 47; D 11.75 17. 单选:操作系统将裸机改造成一台(),使用户无需了解软硬件细节就能使用计算机,提高工作效率。 A 虚拟机; B 家用机; C 商用机; D 超级计算机 18. 单选:windows操作系统属于()操作系统。 A 命令行; B 单任务; C 图形用户界面; D 单机 19. 单选:unix操作系统属于()操作系统。 A 单用户单任务; B 多用户多任务; C 单用户多任务; D 多用户单任务

北理工考博数值分析——试卷

一、填空题:(共20分) 1.非奇异矩阵的条件数为,条件数的大小反映了方程组的 。 2.的相对误差和的相对误差之间的关系是。 3.给出一个求解对任意初值都收敛的迭代公式 ,说明如何获得及收敛理由。 4. 设为互异节点,为对应节点上的拉格朗日插值基函数,则, 。 5.设互异,则当时,;。 6.数值积分公式的代数精确度 是,____ Gauss型求积公式。 二、(10分)设阶矩阵对称正定,用迭代公式 求解。问实数取何值时迭代收敛? 三、(13分)设有线性方程组, (1)将系数矩阵A分解为 ,求;(2)求解方程组。

四、(10分)用最小二乘法确定中的参数和,使该函数曲线 拟合于下 列形式的数据(推导满足的正则方程组)。 五、(10分)求四次插值多项式,使其满足条件 ,并写出插值余项。 六、(10分)设,考虑方程,证明求解该方程的牛 顿法产生的序列(其中)是收敛的;并求,使得 。 七、(15分)对于积分,当要求误差小于时,用复化梯 形公式及 复化抛物线公式计算近似值时,所需节点数及步长分别为多少?计算满足精度要求的 近似值。 八、(12分)试求系数,使3步公式 的阶数尽可能高,并写出其局部截断误差的主项。

一、(12分)设有线性方程组, (1)将系数矩阵A分解为L和U的乘积,其中L是单位下三角阵,U是上三角阵; (2)解线性方程组。 二、(18分) (1)已知数据: 试分别用线性及二次插值计算的近似值,并估计误差。 (2)设,试求三次插值多项式使得 , 并对任一写出误差估计式。 三、(20分) (1)设线性方程组的系数矩阵

试写出收敛的迭代计算公式; (2)若线性方程组的系数矩阵,用表示 迭代法和迭代法收敛的充分必要条件。四、(15分) (1)若用复化梯形、复化辛普森公式计算积分的近似值,要求计算结果有5位有效数字,分别应取多大? (2)选一复化求积公式计算积分的近似值,要求截断误差小于。 五、(10)确定,使求积公式 的代数精确度尽可能高,并指出是否是型求积公式。 六、(15分)试用法推导出求近似值的迭代 格式, 并用导出的公式计算的近似值,要求误差不超过。 七、(10分)已有求解常微分方程的二步公式: 欲使此格式的整体截断误差达到最高阶,应取何值,并说明公式是几阶方法。

数值分析

2008级计算机学院《数值分析》期末试卷A 卷 班级 学号 姓名 成绩 一、 填空题(每空2分,共30分) 1. 设函数f (x )区间[a ,b]内有二阶连续导数,且f (a )f (b )<0, 当 时,用双点 弦截法产生的解序列收敛到方程f (x )=0的根。 2. n 个求积节点的插值型求积公式的代数精确度至少为______次,n 个求积节点的高斯 求积公式的代数精度为 。 3. 已知a =3.201,b =0.57是经过四舍五入后得到的近似值,则a ?b 有 位有 效数字,a +b 有 位有效数字。 4. 当x =1,-1,2时,对应的函数值分别为f (-1)=0,f (0)=2,f (4)=10,则f (x )的拉格朗 日插值多项式是 。 5. 设有矩阵?? ????-=4032A ,则‖A ‖1=_______。 6. 要使...472135.420=的近似值的相对误差小于0.2%,至少要取 位有效数字。 7. 对任意初始向量0()X 和常数项N ,有迭代公式1()()k k x Mx N +=+产生的向量序列 {}() k X 收敛的充分必要条件是 。 8. 已知n=3时的牛顿-科特斯系数,8 3,81)3(1) 3(0 ==C C 则=) 4(2 C ,=) 3(3C 。 9. 三次样条函数是在各个子区间上的 次多项式。 10. 用松弛法 (9.0=ω)解方程组??? ??=+-=++--=++3 1032202412 25322 321321x x x x x x x x x 的迭代公式是 。 11. 用牛顿下山法求解方程03 3 =-x x 根的迭代公式是 ,下山条件是 。

北理工考研复试班-北京理工大学电子与通信工程考研复试经验分享

北理工考研复试班-北京理工大学电子与通信工程考研复试经验分享北京理工大学1940年诞生于延安,是中国共产党创办的第一所理工科大学,是新中国成立以来国家历批次重点建设的高校,首批进入国家“211工程”和“985工程”,首批进入“世界一流大学”建设高校A类行列。毛泽东同志亲自题写校名,李富春、徐特立、李强等老一辈无产阶级革命家先后担任学校主要领导。在英国QS教育集团公布的2018世界大学排行榜中,学校位居世界第389名、亚洲第76名、中国大陆第17名。学校现隶属于工业和信息化部,全体师生员工正对标国家“两个一百年”奋斗目标,全力朝着中国特色世界一流大学的建设目标迈进。 启道考研复试班根据历年辅导经验,编辑整理以下关于考研复试相关内容,希望能对广大复试学子有所帮助,提前预祝大家复试金榜题名! 专业介绍 电子通信工程英文名为Electronics and Communication Engineering,是电子科学与技术和信息技术相结合,构建现代信息社会的工程领域,利用电子科学与技术和信息技术的基本理论解决电子元器件、集成电路、电子控制、仪器仪表、计算机设计与制造及与电子和通信工程相关领域的技术问题,研究电子信息的检测、传输、交换、处理和显示的理论和技术。其工程硕士学位授权单位培养从事信号与信息处理、通讯与信息系统、电路与系统、电磁场与微波技术、电子元器件、集成电路等工程技术的高级工程技术人才。研修的主要课程有:政治理论课、外语课、矩阵论、泛函分析、数值分析、半导体光电子学导论、半导体器件物理、固体电子学、电子信息材料与技术、现代材料分析技术、电路设计自动化、电路优化设计、数字信息处理、信息检测与估值理论、导波原理与方法、导波光学、微波电路理论、高等电磁场理论、应用信息论基础、数字通讯、系统通信网络理论基础、现代管理学基础等。 招生人数与考试科目 电子线路(含数电与模电两科内容)或C语言程序设计(上机)。 复试时间地点

北京理工大学数据结构实验报告4

《数据结构与算法统计》 实验报告 ——实验四 学院: 班级: 学号: 姓名:

一、实验目的 1、熟悉VC 环境,学会使用C 语言利用顺序表解决实际问题。 2、通过上机、编程调试,加强对线性表的理解和运用的能力。 3、锻炼动手编程,独立思考的能力。 二、实验内容 从键盘输入10个数,编程实现分别用插入排序、交换排序、选择排序算法进行排序,输出排序后的序列。 三、程序设计 1、概要设计 为了实现排序的功能,需要将输入的数字放入线性表中,进行进一步的排序操作。 (1)抽象数据类型: ADT SqList{ 数据对象:D={|,1,2,,,0}i i a a Elem Set i n n ∈=≥ 数据关系:R1=11{,|,,1,2,,}i i i i a a a a D i n --<>∈= 基本操作: InPut(SqList &L) 操作结果:构造一个线性表L 。 OutPut(SqList L) 初始条件:线性表L 已存在。 操作结果:按顺序在屏幕上输出L 的数据元素。 InsertSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行插入排序。 QuickSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行快速排序。 SelectSort(SqList &L) 初始条件:线性表L 已存在。 操作结果:对L 的数据元素进行选择排序。 }ADT SqList ⑵主程序流程 由主程序首先调用InPut(L)函数创建顺序表,调用InsertSort(L)函数进行插入排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用QuickSort(L)函数进行交换排序,调用OutPut(L)函数显示排序结果。 再由主程序首先调用InPut(L)函数创建顺序表,调用SelectSort(L)函数进行选择排序,调用OutPut(L)函数显示排序结果。 ⑶模块调用关系

相关主题
相关文档 最新文档