区域选择算法

区域选择算法（精选9篇）

区域选择算法 篇1

无监督视频对象分割对行动识别和视频检索等领域具有重要作用。当前视频对象分割算法主要是在一定时间内对区域或关键点进行跟踪［1，2］, 或是使用外貌或运动线索对所有帧进行低层次的像素分组［3］。然而, 如文献[4]指出, 这些算法对“前景对象的外观如何”缺乏明确概念, 因此经常出现“过分割”问题。最近, 以对象为中心的静态图像分割成为一个热门课题, 并取得巨大进展［5，6］。这些方法以二元轮廓/区域分割形式生成多个对象假设。根据各自分值而得的假设排名表明了这些假设的可信度。使用颜色、纹理和边界等图像线索, 普通的前景对象对该模型进行学习, 然后实现对象类别的独立性。

通过基于物质度指标进行轮廓/区域分割, Vi-cente等人在文献[7]中从数幅静态图像实现“对象联合分割”。Lee等人在文献[4]中将类似思路引入视频图像分割。该文献不仅使用文献[6]中的静态物质度指标, 还使用动态指标来衡量一个区域包含移动对象的概率。他们还指出, 视频中的对象区域的运动方式与周围是不同的。尤其是, 该文献中的指标将区域的光流柱状图与周围区域加以比较。这不需要对摄像机运动做出任何假设, 仍可保持对不同运动幅度的敏感度。对区域打分后, 每个帧中分值最高的K个区域被选出来形成一个候选区域集合C。C中许多区域属于前景对象, 也有可能包括其他区域。对候选区域集合中的每两个区域, 根据非归一化颜色柱状图计算相似度。最后, 进行光谱聚类, 对候选区域集合进行内域/外域划分。每种聚类 ( 内域) 对应于一种前景对象区域假设。然后, 根据成员区域的平均物质度分值, 对获得的聚类进行排名。平均分值越高, 该聚类包含视频主要对象的概率就越大。

然而, 候选区域集合C虽然结合了所有帧中的区域, 但是忽略了每个区域来自哪个帧及区域在该帧中的位置等重要信息。本文将对这些信息加以利用, 以获得更好的区域选择效果。具体方法是, 利用不同帧中区域的二元外观关系, 并对选择的区域施加互斥约束。为公平比较, 我们选择与文献[4]中相同的视频区域物质度定义。文中对视频主要对象区域的选择主要基于以下三种重要观点: ①从派系中选择的区域应该有较高的物质度分值 ( 一元位势) , 且在各视频帧中的外观比较类似 ( 二元位势) ; ②两个相邻帧的对象区域相对来说比较接近, 因为对象的运行一般来说比较平滑; ③主要对象会出现在每一图像帧中。它可能会由于局部遮挡或自我遮挡而改变外观或形状, 但仍会出现在每幅图像帧中。

文中提出了一种新的视频对象分割算法。该算法将区域选择问题表述成在加权图G中寻找约束条件下的最大加权派系 ( MWC) , 其中每个区域对应一个结点。G的相似度矩阵A的对角线元素表示各个结点的物质度分值。非对角线元素表示两个区域间的外观相似度。图G中的最大加权派系就是权重和最大的派系, 这表明一元位势和二元位势均被考虑。在本文算法中, 我们还对最大权重派系加以约束, 以满足非线性互斥约束条件。最后的实验结果也表明了本文算法的有效性。

1 相关工作

视频对象分割问题一直是视频应用领域的研究热点问题, 相继有众多学者提出了一系列方法, 如程淑红等［8］提出了一种基于改进的最小Tsallis交叉熵的视频对象分割算法。该算法在时域中采用帧间变化检测快速区分前景与背景, 在空域中使用改进的最小Tsallis交叉熵设置自适应阈值, 能更准确地对差分图像进行阈值分割, 克服了传统的最小Tsal-lis交叉熵法阈值化容易失效的问题, 然后利用形态学修正和差分交集技术获得精确的视频对象。高韬等［9］提出了一种基于离散冗余小波变换的立体视频对象分割算法。采用离散冗余小波变换提取特征点结合DT网格技术的视差估计方法, 获得了可靠的视差场, 再利用视差信息对立体视频中静止对象进行分割。对于立体视频序列中的运动对象, 采用离散冗余小波提取运动区域的方法进行分割。实验结果表明, 本算法对有重叠的多视频对象具有较好的分割效果, 可同时分割静止物体和运动物体, 具有较好的精确性和鲁棒性。孙季丰等［10］提出了一种基于视频分块处理的CRF视频分割算法。该算法利用像素空间相关性对原视频帧进行分块处理形成新视频帧, 然后使用CRF对新视频帧进行分割, 最后根据初始分割、前一帧分割结果和当前帧CRF分割结果实现最终的分割。实验结果表明, 在不明显增加误分割率的前提下, 文中算法能有效降低时间复杂度。

另外还有, 张晓宇等［11］针对光照变化较大时基于颜色差分直方图的视频分割算法不能有效更新背景, 导致后续输入图像前景目标分割失效的问题, 提出一种基于同态滤波抑制光照变化的视频分割算法。首先利用同态滤波算法对输入和背景图像 ( RGB) 在HSV空间中亮度分量进行同参矫正, 然后将矫正后图像转换到RGB空间, 最后利用颜色差分直方图算法进行视频分割。张洪超等［12］通过在视频空间建立跨时空域的相似性邻接关系, 提出一种新的视频分割图分割模型, 并且采用最大流/最小割算法对相应的模型进行快速求解, 从而实现视频的有效分割。该算法只需用户在视频的关键帧图像上进行少量交互, 便可自动获取整个视频分割结果。并且该分割过程不受前景对象遮挡、快速运动等情况的影响, 具有很好的稳定性。本文在已有工作的基础上, 首次将视频对象分割表述成约束条件下的MWC寻找问题, 然后提出了一种新的优化方法来实现视频对象的有效分割。

2 区域图构建

本文的目标是在不对目标建模的情况下, 对视频前景对象进行分割。由于我们没有对目标对象的尺寸、位置、形状和外观做出任何先验假设, 因此我们首先根据文献[9]为每幅帧生成多个对象“建议”。每条“建议”都是图像中的一个区域。对视频中的每个帧, 检索K个区域 ( 在本文所有实验中设置K = 300) , 对由N个帧组成的视频, 共有K × N个区域。目标就是发现在所有帧中都包含前景对象的一小组区域。构建一个加权图G = ( V, A) , 每个结点对应K × N区域中的一个区域, 且A是其邻接矩阵。结点u的权重A ( u, u) 表示区域u的“物质度”, 结点u和 υ 的权重A ( u, u) 表示两个区域的相似度。

采用文献[4]中的区域“物质度”计算方法, 对区域u有:

式 ( 1) 融合了静态帧内物质度分值sob ( u) 和动态帧间物质度分值mob ( u) 。它反映了区域包含一个通用对象的置信度。使用周围遮挡边界概率及周围像素颜色差异等静态特征来计算这一分值。

在文献[4]中, 引入了动态物质度mob ( u) 为视频静态分值提供补充。该指标可衡量区域u对应于视频中相干运动对象的置信度。在松散配置边界框内对区域u及周围像素计算光流柱状图。该分值的计算方法为:

式 ( 2) 中, 是L1- 归一化光流柱状图间的χ2- 距离。动态分值可以有效描述区域运动与最近邻区域的差别。使用分值在视频所有区域的分布对静态和动态分值做归一化处理。同时使用Lab颜色柱状图来描述各个区域。两个区域u和 υ 间的相似度的计算方法为:

式 ( 3) 中 χ2color ( u, υ) 是u和 υ 非归一化颜色柱状图的 χ2为距离, Ω 表示所有区域的 χ2为距离均值。因此, 如果两个区域的颜色或尺寸相似, 则它们的相似度就会很高。

3 区域间互斥约束

本文工作对视频分割领域的重要贡献之一就是引入了严格的互斥约束。该约束指明了哪些区域不能同时入选分割解, 从而可以避免区域的不合理配置; 由于一元位势A ( u, u) 和二元位势A ( u, u) 可靠性有限, 区域的不合理配置将会导致大规模联合位势。此外, 使用推理框架可以保证所求解满足所有的约束条件。互斥约束基于以下两个观点。

3. 1 帧内互斥约束

假设一个真正的对象应该会出现在每一幅帧中, 在每个帧中, 只有一个提议区域将被选择。然而, 对象可能被部分遮挡或自我遮挡。因此, 只为每帧选择一个候选对象区域, 对选择优质候选区域具有重要作用, 原因有两点: ①同一帧中的许多区域会出现重叠, 由于光照条件改变等帧间变化因素, 它们的相似度往往会远高于不同帧中的真实对象区域的相似度。因此, 相比于同一派系中混入同一帧的区域相似度, 来自不同帧的区域相似度更有意义。②由于我们保证过为每帧选择一个区域, 被选区域可以进一步用作先验位置。

3. 2 帧间邻近约束

同一对象在相邻帧上的位置变化应该是平滑的, 因此从两个相邻帧中选择的两个区域在空间上的距离不应太远。将这两个约束表述为一个二元互斥矩阵M, 该矩阵定义于图G的所有顶点上:

式 ( 4) 中, C ( u) 和C ( υ) 是两个区域的矩心, d是它们的像素欧几里德距离, τ 是u和 υ 间允许的最大空间位移。我们在所有实验中设置 τ = 100, 以为快速移动对象提供支持。

4 寻找约束条件下的MWC对象

本文将区域选择问题表述为约束条件下的最大权重派系问题。输入为一加权图G = ( V, A) , 其中V = { υ1, …, υn} 表示所有视频帧区域的一组结点, n是结点数量, A是所有元素非负的对称的n × n相似度矩阵, 对所有i, j = 1, …, n有Aij≥0。被选区域用指示向量X = ( x1, …, xn) ∈{ 0, 1}n标识, 对区域vi, 当且只当xi= 1 时才被选择。

对于图形顶点间的对称关系M ⊆ V × V, 将M称为互斥关系, 表示为二元矩阵M ∈ { 0, 1}n ×n。如果M ( i, j) = 1 , 则两个顶点i, j不得属于同一个最大派系。对所有顶点i有M ( i, i) = 0。一般地, 这一要求可被表示为施加于指示向量X ∈ { 0, 1}n上的一个约束: 如果M ( i, j) = 1, 则xi+ xj≤1。这一表述等同于要求XTMX = 0。对给定视频, 通过求解如下优化问题来获得主要对象区域:

使f ( x) = XTAX最大化

式 ( 5) 的目标是从图G中选择一组顶点, 使f最大化, 同时满足互斥约束条件。因为f是被选顶点集合的一元和二元相似度的和, 于是被选集合越大, f值越大。然而, 被选集合的规模受到互斥条件约束。问题 ( 5) 是个NP难解组合优化问题［13］。通过设置W = A - γM且 γ 足够大, 将问题 ( 5) 重新表述为如下对偶形式:

使XTWX = XTAX - γXTMX最大化

最后, 可以将式 ( 6) 松弛为:

使XTWX = XTAX - γXTMX最大化

第6 节将给出式 ( 7) 一种求解算法。在所有视频分割实验中, 均获得了满足所有互斥约束的离散解。

由于使用的最大派系搜索算法会收敛到局部最优, 因此需要多次初始化以提升性能。将图G中的区域根据各自一元分值A ( u, u) 进行排序, 获得排名最高的L个区域。我们每次从这L个区域中选择一个区域u来对最大派系搜索算法初始化。将初始状态表示为X ( 0) , 然后对所有i ≠ u设置 ( X ( 0) ) u=1, ( X ( 0) ) i= 0。从X ( 0) 开始, 用二元向量X*表示已经获得的一个最大派系。X*是满足X* TMX*= 0条件的XTAX的一个局部最大化因子。

因此, 将总共获得L个最大派系, 并根据XTAX选择一个最优。可以发现, 被选区域是这一解的指示向量的元素。因为这一解满足第3 节定义的约束条件M, 于是只从每一帧中选择一个区域, 并保证相邻帧中选择的每两个区域相对比较接近。这些区域反映了每个帧中对象的基本外貌和位置。

5 前景对象分割

视频对象以被选区域形式获得的分割效果并不十分准确。尤其地, 分割误差容易受到候选对象区域的下界约束［6］。出现误差可能是因为初始的超级像素提取或融合不够精确。因此, 本文采取如下策略: 利用被选区域为前景和背景展开外观模型学习。此外, 我们也利用了先验位置信息。在本算法中这一点较为简单, 因为每一帧只有一个对象区域。最后, 本文使用GrabCut［14］算法得出更加准确的像素级对象分割方法。出于效率考虑, 本文没有像文献[4]那样构建空间-时间图, 一次性为三幅连续帧对像素进行标记, 而仅是单独地为每幅帧运行Grab-Cut算法。这在本文中是完全可能的, 因为在下文定义的基于约束条件下MWC获得的数据项, 带有大量重要信息。

将每帧中的像素表示为S = { p1, …, pn} , 各自标记为f = { f1, …, fn} , fi∈ { 0, 1} 且前景时为1, 背景时为0。此时, 极小化能量函数为:

式 ( 8) 中, N由8 个空间相邻的像素组成。对于平滑项V, 使用文献[14]中定义的对比度独立函数, 该函数倾向于为颜色类似的相邻像素分配相同的标记。与文献[4]类似, 本文的数据项Di ( fi) 用标签fi定义了标记像素pi的成本:

式 ( 9) 中Pic ( fi) 是根据外表 ( 颜色) 特征用标签fi定义标记像素pi的概率, Pli ( fi) 是基于先验位置的概率。

为了计算Pic ( fi) , 首先估计RGB颜色空间两个高斯混合模型 ( GMM) , 以对前景和后景外观建模。因为颜色在视频帧中差异太大, 因此需要在所有视频帧上对模型展开学习。前景GMM模型fgcolor根据约束条件下的MWC计算所选择的区域内的像素进行学习。后景GMM模型bgcolor根据所有帧被选区域的补充区域内的像素展开学习。然后根据这两个颜色分布fgcolor和bgcolor, 对每个像素pi定义:

对于位置概率Pli ( fi) 的计算, 利用约束条件下MWC选择的对象区域。给定被选区域后 ( 每个帧, 我们只有一个区域) , 首先计算它的距离变换。设d ( pi) 表示像素pi与被选对象区域的距离。计算:

式 ( 11) 中, σ 表示先验位置的置信度; σ 越大, 置信度越低。另外还需计算Pic ( fi) ·Pli ( fi) 作为前景 ( fi= 1 ) 和后景 ( fi= 0 ) 的概率。在获得数据项D和平滑项V后, 使用文献[3]中的常见方法来确定可以实现式 ( 8) 能量函数最小化的最优f, 进而求得每幅视频帧中的最终前景对象。

6 算法描述

本节将给出一种新的约束条件下MWC确定算法。f ( x) = XTWX表示式 ( 7) 中的目标函数。本算法需访问一组连续点{ y ( k) ∈ [0, 1]n} ( k = 1, 2, …) 。每次迭代k, 文中分两个步骤。首先, 给定y ( k) , 对其任意相邻点y ∈[0, 1]n, 计算f ( y) 的一阶泰勒近似:

式 ( 12) 中的二阶f ( y ( k) ) 不依赖于y, 因此f ( y) 的一阶泰勒近似只依赖于yWy ( k) , 且yWy ( k) 是y的线性函数。这一特点使得式 ( 13) 中的离散最大化因子可以根据式 ( 14) 计算得到:

在第k次迭代的第二步, 需要验证求得的X (k) 能否作为可以使f变大的合法离散解。如果当通过线搜索, 在至y (k) 的线段上实现一维函数最大化, 以此来在连续域上估计f的局部最大化因子。可以看出, h (α) 在式 (15) 中定义的α处达到最大值。同时可以看出, 0<α<1, 这可以保证线搜索不会超出立方体范围。

然后, 本文设置如果对向量X*= y ( k + 1) 的所有坐标i均满足以下停止条件, 则本算法终止:

可以观察到, 因此, (WX*) i>0表示f的上升方向与第i个坐标的方向相同, (WX*) i<0表示方向相反。根据停止条件可知, f (X*) 在f的每种上升方向上均达到了可能的最大值。假设初始分配值y (0) 满足互斥约束, 即y (0) TMy (0) =0。因为A的所有元素非负, 所以这表明f (y (0) ) ≥0。本文算法总结于如下伪代码中:

7 实验结果

本文首先在SegTrack数据库［15］上评估本文算法。该数据库总共包含了6 个视频 ( 猴子与狗, 小鸟, 女孩, 降落中的小鸟, 跳伞者, 企鹅) 。由于这些视频的主要对象存在较大规模的变形, 而且前景和后景存在重叠, 因此对象分割难度较大。与文献[4]相同, 本文没有在企鹅视频上评估算法, 原因是一组企鹅中只有一个企鹅被识别为前景对象。

给定一个视频后, 首先根据文献[6]为每个帧生成300 个对象候选区域。本文使用Lab空间柱状图来描述每个区域的颜色。每个Lab信道有20 个接收器 ( bin) 。对前景和后景颜色模型, 我们使用RGB颜色空间, 对两个5 成分GMM进行学习, 另外, 本文采用光流柱状图来描述运动, 每x和y方向上有60 个接收器。在计算背景柱状图时, 区域边界盒扩充30 个像素大小。为对最大派系计算初始化, 每次根据A ( u, u) = ob ( u) 从最优的50 个对象区域中选择候选对象。计算Pli ( fi) 时设置 σ = 20。对本文所有实验的图像切割能量函数, 设 δ = 1。由于本文约束条件下MWC算法的高效性, 计算机配置3. 4 GHz、8 GB RAM, 算法在50 个不同初始状态下基于约束条件MWC选择区域只耗时2 min。单帧二元图像切割平均耗时约0. 1 s。

将实验结果与文献[4, 15, 16]中的三种最新算法做比较。文献[4]中的算法与本文算法均是无监督算法。它们可以自动发现图像中的主要对象, 并且自动分割出来。文献[15, 16]中的算法需要一定的人工监督, 在第一帧中需要人工标出对象。表1给出了实验结果。对5 种测试视频, 本文每帧分割平均误差最低。5 个视频中, 本文算法在3 个视频上的分割误差最小。文献[4]与本文算法一样, 对象初始化均不需手工进行, 但是与该算法相比, 本文算法在4 个视频上的实验结果更优。部分分割结果见图1。

表1 给出了相对真实分割结果计算而得的平均每帧像素误差率。具体计算方法与文献[4]相同:

式 ( 17) 中, f是给定视频每个像素的标签, GT是真实数据标签, F是给定视频的帧的总数量。由于所有视频的大小基本相同, 5 个视频的平均误差率计算为所有视频所有帧的平均值, 也就是说, 将5 个视频看成是一个视频然后再应用式 ( 17) 。

如上文所述, 即使没有第5 节描述的基于像素的对象分割, 基于第4 节约束条件下MWC所选择的对象区域也可以作为分割结果。在表2 中, 我们给出了约束条件下MWC区域分割结果的像素误差, 该误差受到文献[9]生成的候选区域准确度下限约束。下限误差计算为候选区域相对真实像素的最低误差。它反映了我们基于约束条件下MWC计算而进行区域选择所能获得的最低分割像素误差。

从图1 可以看出, 对降落的小鸟和猴子小狗视频, 只使用约束条件下MWC获得的区域可以取得非常理想的效果。此外, 除了印度豹外, 像素误差与误差下限非常接近。这表明, 本文提出的约束条件下MWC区域选择算法为视频分割提供了一种强大的工具。

如表3 所示, 如果可以表示时间/空间相干特性的帧间邻近互斥约束没有作为约束条件下MWC优化问题的输入, 则分割误差会有显著上升。本文也在图2 中, 直观阐述了这些互斥约束的重要性。本文在有互斥约束和没有互斥约束两种情况, 对约束条件下MWC区域的矩心轨迹做了对比。矩心重叠显示于第一个视频帧上。从图2 可以看出, 有约束时, 矩心的轨迹非常平滑, 被选区域总是聚集于主要对象, 也就是视频样例里的猴子上。这表明, 互斥约束明显提高了约束条件下MWC优化问题的鲁棒性, 使得我们可以去除来自低可靠性相似关系的不合理的区域选择假设, 因此对选择正确的对象区域具有重要作用。

本文也基于文献[3]中的Yu-Na Kim和Waters-ki两个视频对本文算法进行评估。文献[3]通过动态和外观特性来标识图像中的每个像素, 而本文算法在每帧中可以实现主要对象 ( 即溜冰者和滑水者) 识别和分割的自动化。定性结果见图3。

(白点与黑线相连, 覆盖于第一帧图像上)

8 结束语

本文提出了一种新的视频对象分割算法。该算法引入互斥约束, 以在形状、外观和光照条件发生较大变化时, 也能对前景对象实现可靠分割。视频所有帧的对象区域选择可以同步进行。本文把计算问题看成是区域图中最大权重派系的寻找问题, 并针对该问题提出一种新的求解方法。由于该算法在本文所有实验结果中均产生离散解, 因此不需要后处理也能获得离散解。实验结果表明, 获得的所有解均满足互斥约束。我们下一步研究工作的重点是引入更具甄别性的特征, 如SIFT特征, 进行相似性区域检测, 从而进一步提高视频分割的准确度, 在少量用户交互的前提下提取满足用户需求的前景对象序列。

区域选择算法 篇2

before sort the array:

75 84 30 35 77 60 75 32 64 2

lefy—>0 right—>9 index:0 midNumber :75

lefy—>0 right—>6 index:1 midNumber :32

lefy—>0 right—>1 index:1 midNumber :30

2th max number is———————- 30

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>0 right—>1 index:1 midNumber :2

1th max number is———————- 2

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

3th max number is———————- 32

30 2 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>3 right—>9 index:4 midNumber :84

lefy—>3 right—>8 index:4 midNumber :75

lefy—>3 right—>6 index:5 midNumber :35

lefy—>4 right—>6 index:5 midNumber :75

lefy—>4 right—>5 index:5 midNumber :60

lefy—>5 right—>5 index:5 midNumber :64

6th max number is———————- 64

2 30 32 35 60 64 75 75 77 84

after sort the array:

2 30 32 35 60 64 75 75 77 84

区域选择算法 篇3

在基于点特征的匹配算法中,David Lowe所提出的尺度 不变特征 变换算法[2]( Scale Invariant Feature Transform) 由于具有尺度和旋转不变性,因此在多个领域得到了广泛的应用。但SIFT算法存在灰度非线性畸变和背景噪声干扰等问题,相关学者继而提出SIFT改进算法,如Y Ke等提出的PCASIFT使用主成分分析代替方向直方图规定化图像梯度,具有更好的光照变化不变性[3]; Mikolajczyk等提出的GLOH算法利用同心圆作为特征描述符,通过主元分析降低特征向量维数从而简化计算[4]; Bay等提出的SURF算法进一步加快该算法的计算速度[5]。一般将SIFT算法可以细分为7个步骤, 包括构造高斯金字塔影像、构建差分金字塔影像、局部极值点提取、局部极值点精化、特征点方向计算、特征点向量计算、特征匹配。其中构建高斯金字塔影像、特征向量计算和特征匹配在整个算法的 用时最多[6],因此这三个步骤决定了整个算法消耗的时间。随着遥感大数据时代的开始,遥感大图像的匹配对计算机的硬件条件也越来越高。对于较大图幅的影像进行配准时,目前常用计算机难以满足运算所需的储存空间的需求。

针对以上问题,提出基于区域选择和SIFT结合的遥感配准方法。改进算法首先对遥感图像进行粗配准,将图像按照得到的粗配准系数变换获得图像的重叠区。然后分割重叠图像,利用二维小波分割图像进行变换,统计三个方向的高分辨率能量和,将能量最大的分割图像作为配准的有效子图, 按照SIFT算法对有效子图配准代替对原图像配准, 成功避免了相似特征点的误配,提高了配准正确率,较明显地减少了配准时间。

1 SIFT 配准算法

David Lowe提出的基于SIFT点特征的提取与匹配算法主要有构建尺度空间,提取特征点,计算特征点描述子和特征点匹配四个步骤[7]。

( 1) 构建尺度空间,特征点在各个尺度图像中具有稳定的特征。将待配准遥感图像用fi( x,y) 表示,G( x,y,σ) 为高斯函数,则高斯尺度空间的建立可以用式 ( 1) 表示:

为了在尺度空间内确定稳定观测点的位置, David Lowe提出了高斯差分尺度空间 ( DOG尺度空间) 。DOG尺度空间的各个图像是高斯尺度空间内相邻层图像的插值,通过与不同尺度的高斯差分函数卷积计算得到,如式 ( 2) 所示:

式 ( 2) 中k为不变倍增因子,k = 21 / S。

( 2) 提取特征点。对DOG尺度内所有点与自身尺度内相邻的8个像元及上下相邻尺度上的18个象元进行比较,如果该象元的高斯差分值均大于或小于相邻象元点,则称之为局部极值点。对选出的局部极值点利用曲面拟合及边缘效应准则剔除部分局部极值点,未被剔除的点就是图像的特征点。

( 3) 计算特征点描述子。以特征点为中心,在一定的影像区域内,计算该区域内的每个象元的梯度方向和梯度强度。采用梯度方向直方图统计该区域内的象元的梯度方向,梯度方向直方图的峰值作为该特征点的主方向。

( 4) 特征点匹配,一般采用特征点的特征矢量的欧氏距离作为两幅图像中特征点相似度的判定度量。设参考图像为f1( x,y) ,取出其中一个特征点A,其特征向量为DA,在待配准图像f2( x,y) 上逐个搜索与A距离最近的特征点B和次最近距离的特征点C,其特征向量为DB和DC,称B为A的初始匹配点。然后按照距离比率准则进行特征匹配,当最近距离/次最近距离小于给定的阈值ε时,则称特征点A与B为一对匹配点。

2 结合区域选择和 SIFT 的配准方法

2. 1 区域选择

区域选择的目的是选择信息丰富的重叠区域内的图像代替原图进行配准,选择的标准在于一是分割图像必须属于或大部分属于重叠区内,二是分割图像的图像信息也就是图像特征较为丰富。为获取图像的重叠区,首先对图像进行粗配准。

2. 1. 1 粗配准

通常通过人工选点采用仿射变换模型对影像进行粗配准。仿射变换可以看成由平移、旋转、缩放和剪切变换的组成,因此仿射变换可以分成线性变换和平移变换。若 ( x1,y1) ,( x2,y2) 分别为参考图像和待配准图像中对应的两点,则仿射变换模型如式 ( 3) :

仿射变换中的6个参数可以由任意不共线的三点确定。粗配准时首先选取3对控制点,代入式 ( 3) 计算出变换参数,依据获得的变换参数确定参考图像与待配准图像的重叠区域。

2. 1. 2 图像分割及选取

SIFT算法提取整张图像的特征点数量多,匹配过程计算复杂度大,严重影响了大幅遥感图像的配准速度,而且误配率很高,当图像中含有较为相似的区域时,误配率更高,因此只选取重叠区域的一部分提取特征点进行配准可以有效地降低误配率。采用长江流域的两幅遥感图像,经人工选点粗配准获得的重叠区,如图1所示。

对重叠区域进行图像分割主要依据以下两个原则: 1如果重叠区较小,为能够获得足够的特征点,则不对其分割; 如果重叠区较大,进而特征点较多,为了提高匹配速度和匹配准确度,对其进行分割。2为了能够使得特征点在待配准图像块内均匀分布且拥有足够的数量,分块数量应满足每块分割图像占总重叠区的比例大于等于1 /4。

各个图像块经二维小波变换,分为低频分量LLi和三个方向的高频分量HLi、LHi、HHi,其中低频分量代表了图像的轮廓信息,三个方向的高频分量代表了图像三个方向的细节信息[8],图像细节越丰富也就表示该图像的图像特征也越丰富,将高频分量总和最高的图像块作为有效图进行配准,其中高频分量总和的公式如下:

其中i代表第i个图像块。

2. 2 图像配准

经过区域选择获得了可以代替各个待配准图像的有效图像块,对有效图像块利用SIFT算法进行配准。按照SIFT算法获得了图像之间的特征点对, 从中均匀选取5个特征点,例如从图像四个角及中心各选取一个,将其坐标代入公式 ( 3) ,依据最小二乘原则,解算出仿射变换的6个参数。

综上所述,具体算法流程如图2所示,包括以下步骤: 首先通过人工选取控制点获得影像的粗配准系数,并依此配准系数获取两幅影像的近似重叠区。然后将两幅影像分割,利用二维小波变换得到三个方向的高分辨率能量和,将重叠区内能量最大的分割图作为待配准影像,利用SIFT配准法对分割图进行配准从而获得遥感影像图像之间的配准系数。

3 试验与分析

为了验证改进算法对配准精度和效率的影响, 实验中选取了2组不同传感器获取的影像进行试验,包括TM和无人机CCD影像,采用图像退化模型,对各个传感器获得图像模拟得出一组图像,且图像间的几何变换系数已知,根据变换系数判定匹配精度。对于配准结果采用匹配点的正确率p和均方根误差 ( RMSE) 评价其精度,正确率和均方根误差的公式分别为:

式中,n为正确的匹配点数,N为总的匹配点数; vxi和vyi分别为待配准影像上各个匹配点X方向和Y方向的误差。

实验中选用的分辨率相同的长江地区TM影像和分辨率不同的无人机影像验证本文算法的适用性。通过人工选点可以获得两幅图像的大致重叠区,对重叠区采取图1所示的分割方法得到roi1、roi2、roi3三幅分割图像,对三幅图利用sym4小波进行一层二维离线小波分解并计算其高频分量和, 通过比较将roi3作为待配准子图,对于实验2的重叠区域均匀分成4块,如图3所示,将右上角的分割子图作为待配准子图,且待配准子图的坐标体系和坐标值和其在原图像中的坐标值一样。如图4所示,SIFT算法和本文算法的特征点分布。从图像中可以看出原SIFT算法获取的特征点繁多,使得匹配效率较慢。

通过对SIFT算法及本文算法处理图像的过程及精度统计如表1、表2所示。从表1中可以看出,对匹配点计算均方根误差,本文算法虽然获取了较少的特征点,但配准精度没有下降,相对于原算法有一定的提高,本文算法的配准精度可以控制在1个像素之内,相对于直接利用原图像进行配准精度有了较大的提高。从表2可以看出采用整幅图像提取特征点时,SIFT算法会提取整幅图像的特征点,本文算法只提取部分分割图像的特征点,整幅图像特征点总个数是本文算法提取特征点的近10倍,从而导致冗余信息的产生,从而影响了处理效率,通过对计算时间的统计,本文算法的耗时相当于原SIFT算法的1 /5。并且由于特征点过多导致匹配正确率下降,本文算法匹配正确率优于SIFT算法。通过对重叠区域的分块处理提高了匹配速度及匹配精度 ( 如图5所示) 。实验中还对超大幅图像进行验证改进算法的适用性,原SIFT算法因内存不足导致直接终止程序,采用本文算法解决了大幅遥感图像的配准问题。

4 结论

选择排序算法总结 篇4

运行结果:

before sort the array:

75 84 30 35 77 60 75 32 64 2

lefy—>0 right—>9 index:0 midNumber :75

lefy—>0 right—>6 index:1 midNumber :32

lefy—>0 right—>1 index:1 midNumber :30

2th max number is———————- 30

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>0 right—>1 index:1 midNumber :2

1th max number is———————- 2

2 30 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

3th max number is———————- 32

30 2 32 60 75 64 35 75 84 77

lefy—>0 right—>9 index:0 midNumber :32

lefy—>3 right—>9 index:4 midNumber :84

lefy—>3 right—>8 index:4 midNumber :75

lefy—>3 right—>6 index:5 midNumber :35

lefy—>4 right—>6 index:5 midNumber :75

lefy—>4 right—>5 index:5 midNumber :60

lefy—>5 right—>5 index:5 midNumber :64

6th max number is———————- 64

2 30 32 35 60 64 75 75 77 84

after sort the array:

2 30 32 35 60 64 75 75 77 84

注：本文中的所有代码都在这里

区域求和表算法的改进 篇5

但是由于纹理过滤需要读取许多像素的信息所以很难精确的降低其计算规模, 为了避免实时和重复的计算, 一个较好的方法是查找表技术。由于纹理映射与物体表面的形状有关, 对不同的可见景物表面, 像素内的可见表面区域在纹理平面上往往映射为不同大小、不同形状的曲边四变形, 因此很难实时精确求解这些曲边四边形区域内的平均纹理颜色。查找表技术的思想就是试图采用一些简单形状的区域如正方形、长方形、椭圆等来逼近这些曲边四边形, 从而使得计算该区域的平均纹理颜色变得容易。目前常用的查找表技术有Mipmap技术和区域求和表技术。Mipmap是现在应用最为广泛的一种, 它用正方形来近似表示每一像素在纹理平面上的映射区域, 并预先使用一系列表格来代表具有不同分辨率的纹理图像[1]。区域求和表则允许滤波器的形状为任意长方形, 并建立起一张查找表, 该查找表上的每一个值代表由纹理图像左下角和当前点所确定的长方形区域的纹理值之和, 它在相同性能的情况下能提供比mipmap过滤算法更好的视觉效果。但由于该算法需要更多的内存空间和内存读写次数, 目前还未见其硬件实现。本文对区域求和表算法进行了改进, 使其更加适合于硬件实现。

1区域求和表技术的原理

Mipmap查找表技术基于下述假设:任一个像素在纹理空间中的映射区域可近似地表示为一正方形, 即假定纹理图案映射到景物表面并投影到屏幕上后, 在屏幕的x, y方向被均匀的压缩或放大。但由于纹理映射过程涉及到纹理空间至景物空间及景物空间到屏幕空间的变换, 映射后的纹理图案在屏幕的x, y方向上的压缩和变形一般来说是非均匀的, 因而上述假设在许多情形下并不成立。这会影响映射的精度[2,3], 使结果看起来非常模糊。区域求和表技术对此进行了改进, 它对Mipmap技术加以推广, 允许滤波器的形状为任意长方形, 并建立起一个与纹理大小相同的查找表, 该查找表上的每一点 (x, y) 的值S (x, y) 表示以 (x, y) 为顶点, 以纹理图案的原点为对角顶点所构成的长方形区域内的纹理颜色之和[1], 即

undefined (如图1) 。表中最右下角的元素存储了整个纹理图像中所有纹理像素颜色值之和。

根据这张查找表可以方便的求出与纹理多边形的边平行的任一个长方形的平均颜色构成, 具体的只需要通过从这张表读取四个纹理值进行计算就可以得到。让荤们看一个例子:有一个长方形, 其四个顶点分别为: (x, y) , (x+a, y) , (x, y+b) 和 (x+a, y+b) (如图2) 。

于是长方形区域ab的纹理颜色之和Sab可表示为:

Sab=S (x+a, y+b) -S (x+a, y) -S (x, y+b) +S (x, y) , 具体计算过程如图3:

因此该区域的平均颜色构成等于Sab除以长方形的面积, 即undefined, 长方形的面积等于ab。

综上所述, 区域求和表是一种各向异性的纹理过滤技术, 同时由于区域求和表技术只用到了那些在长方形内的像素[4], 因此它会产生比Mipmap过滤技术更尖锐更精确的视觉效果。

2区域求和表算法的改进

2.1算法存在的问题

由上面的讨论可看出, 区域求和表技术明显的提高了硬件绘制的视觉效果, 使绘制的图形更加逼真。但其巨大的内存需求量, 却是硬件实现的一大难题。如果原纹理图像的每个颜色用8位表示, 那么一张1024×1024的区域求和表就会需要28位来表示每一个颜色值 (实际应用中我们一般用32位来表示每一个颜色值) 。其存储量是原纹理图像的3至4倍, 这主要是由于区域纹理表中每个元素存放的是相应矩形区域内所有纹理像素的纹理颜色之和, 因而每个元素不可能象原纹理图像那样只占8bit。特别地, 区域纹理查找表最右下角的元素为整个纹理图像中所有纹理像素颜色值之和, 其值非常大, 往往需占用28～32位才能存放。

2.2算法的改进

为了降低原算法的内存需求量, 减少其内存读取, 本文对算法进行了优化, 使之更适合于硬件实现。具体方法如下:

如上所述, 如果原纹理图像的每个颜色用8位表示, 那么一张1024×1024的区域求和表就会需要32位来表示每一个颜色值。问题是最终的结果是否真正需要32位, 下面我们对这个问题进行分析;要求与纹理多边形的边平行的每一个长方形的平均颜色构成, 只需要从查找表读取长方形4个顶点的值进行计算, 由于对于每一个顶点的值被除以长方形的面积 (TA) , 因此那些比undefined层次更低的位, 在最终的结果中并没有本质的改变 (最大范围在+/-2) 。并且结果的值将在0到255之间, 因此那些比undefined的层次高的位, 也不具有重要的信息。最终的结果最多需要9位undefined。由于这个结果只是面积的和, 因此必须除以TA。但是这个面积和已经被undefined除了, 这只是做了一个右移, 因此它还必须除以undefined。这个除法对于特殊的硬件设备是一个非常简单的运算, 它类似于一个浮点的除法, 因此用硬件实现起来非常容易。由上面的分析可见, 最终的结果最多只需要9位就可以了, 这样区域求和表每一个颜色值的内存读取量几乎和原始纹理图像的读取量相等, 极大地降低了内存的需求量, 非常适合于硬件实现。

3改进算法的效率分析

由以上讨论可知, 区域求和表技术用长方形区域来逼近屏幕像素在纹理空间中的映射区域, 且这些长方形的长宽比可以取任意值, 因而, 较之基于正方形滤波器的Mipmap技术, 区域求和表算法在求解精度上有很大改善。由于纹理过滤算法的效率取决于内存空间的占用量, 内存的读取和计算的复杂度。下面具体讨论区域求和表技术的效率。

3.1存储效率

区域求和表与预先产生的Mipmap纹理算法有一点不同。它具有和原始纹理图像相同的点, 但是其色深度却多于5, 6或者8位。精度越高, 所需存贮量越大。因此需要的额外内存空间是变化的, 它的范围从原始纹理图像的undefined倍到4倍之间甚至是更多。如果原始的纹理图像用32位存储, 这意味着红、绿、蓝各占8位, 剩余的8位没有被使用, 这时区域求和表只使用了48位 (16/16/16位) , 额外的内存空间只有原始纹理图像的undefined。同时由于进行了改进, 区域求和表一个颜色值的内存读取量和原始纹理图像的读取量相等, 非常适合于硬件实现。

3.2运算效率

由于一次双线性插值可分解为三次线性插值, 而一次线性插值需执行一次乘法、二次加法运算, 故一次双线性插值需执行三次乘法和六次加法运算。由前面的讨论知, 在一般情况下, 区域求和表技术需用双线性插值计算长方形四个顶点所对应区域的纹理颜色之和, 因而计算一个屏幕像素内可见表面像素内可见表面的平均颜色值需查取16个元素, 执行14次乘法和27次加法运算。若屏幕像素在纹理平面上的映射区域面积较大, 在求取长方形四顶点对应的区域纹理值时, 可以不做双线性插值, 这时所需的计算量为:查取四个元素, 做二次乘法和三次加法运算, 算法的效率大大提高。

4结束语

本文探讨了区域求和表的硬件实现。与Mipmap过滤技术相比, 区域求和表技术明显的提高了绘制的视觉效果, 但由于其巨大的内存需求量和太多的内存读取使得它不适合直接用硬件来实现。针对这一问题, 本文对区域求和表算法进行了分析, 并加以改进。经过优化的区域求和表算法, 内存需求量和内存读取次数明显地减少, 更适合于用硬件实现。

摘要：查找表技术可以使纹理过滤变得容易处理, 其计算精度不再依赖于纹理的密度。目前常用的有Mipmap技术和区域求和表技术。区域求和表技术使用一张预先计算的表格, 该表格的每一个值代表由纹理图像左下角和当前点所确定的长方形区域的纹理值之和, 它在相同性能的情况下能提供比mipmap过滤算法更好的视觉效果。由于该算法需要更多的内存空间和内存读写次数, 本文对算法进行了改进, 使之更适合于硬件实现。

关键词：计算机图形,纹理过滤,mipmaP过滤,面积求和表

参考文献

[1] L.WILLIAMS.Pyramidal parametrics", Computer Graphics, 1983, 17 (3) :1-11

[2] HECKBERT, PAUL S.Texture mapping polygons in perspective.Technical Memo.13, NYITComputer Graphics Lab, 1983.

[3] SZIRMAY-KALOS, L偄SZL幃 (editor) .Theory of three dimensional computer graphics.Publishing House of the Hungarian Academyof Sciences, 1995

[4] CROW, FRANKLIN C.Summed area tables fof texture mapping.Computer Graphics.1984, 18 (3) , (Proc.SIGGRAPH84) :137~145

[5]彭群生, 鲍虎军, 金小刚.计算机真实感图形的算法基础.北京:科学出版社.1999.

基于区域的图像检索算法 篇6

基于区域的图像检索技术是一门被广泛研究的信息检索技术。该项检索技术由系统对图像进行提取与识别, 解决了传统的基于关键词检索中的各种问题。特别是随着网络技术与多媒体技术、数据库技术相互融合, 检索系统开发需求的不断扩大, 是一个颇具生命力的研究方向, 针对这一方向深入研究, 将具有很大的理论价值和广泛的应用前景。

1 基于区域图像检索综述

常用的图像检索技术大致可以分为基于边界检测和基于区域两种方法。包括:边界检测分割法和区域检测法。边界法先检测出图像中的边缘点, 然后按照一定的策略把这些边缘点连接成轮廓, 封闭边界所包围的像素就组成了相应的区域。

基于区域的方法是把图像中的各个像素依据一定的规则分到各个区域中, 这些区域的外围像素就会构成了区域的边界, 所以关键是如何确定像素分类的规则。实际规则中应用的区域分割技术主要有两种:一种是阈值化算法, 另一种是特征空间聚类。特征空间聚类的方法是对阈值分割的一种推广方式。它采用特征空间点来表示图像空间中的元素, 通过将特征空间的点聚集成团, 然后再将它们映射回原图像空间, 来达到取得分割的结果。通常在高维特征空间的聚类, 如果只用一个特征往往不能解决的问题, 所以, 特征空间聚类通常采用多个特征。通常采用的方法有K-均值、模糊聚类、ISODATA聚类、概率聚类等。区域分割技术有两种基本形式, 一种是根据单个像素, 逐渐合并以形成所需的分割区域, 另一种是从全局的出发, 逐渐分裂切割到所需的分割区域, 对应的两种典型算法分别是区域生长和分裂合并。

2 基于区域的图像特征的提取

在众多提取参数中, 可以选择颜色特征作为K-均值聚类的中心, 根据每一个小的区域的颜色的均值和标准差的平均值, 可以计算出它的纹理特征, 进而对图像进行提取, 计算的步骤如下:

(1) 在图像中, 选择一个点作为提取点, 然后将其他点都设置为黑色。

(2) 通过转换, 将图像的颜色模式转变成灰度图像。

(3) 在刚才的灰度图像上, 根据算法, 作四层小波变换。

(4) 在变换后的每个高频子带上, 计算他们的平均能量, 如公式1所示。

(5) 做四层小波变换后, 获得的12个能量值, 用合适的比例, 组成一个纹理特征向量。

式中, X (i, j) 表示纹理图像, E表示能量, M、N是纹理图像的维数。

每一个单体特征可以定义为, 如公式2所示:

式中, rij表示在区域j特征i的向量, 维数为K。

图像的特征定义为, 如公式3所示:

3 基于区域的图像特征的相似性检测

在进行图像匹配的时候, 可以获得各种不同的特征值, 但是对于图像检索的共享大小不同, 所以我们需要对他们进行进一步的归一化处理, 规定相似度S都在0到1之间, 并且在某个特征rij内部进行。并且, 在计算S之前, 同时要求将特征向量的各分量rijk (表示第i种方法, 第j个区域, 第k个分量) 统一进行归一化操作, 否则采用S的线性组合来计算总体相似度S就变得没有意义。把这种对rijk的归一化称为特征内的归一化。

特征内部的归一化可以使特征向量rij与的各分量与rijk具有同等的重要性。因为特征向量的不同分量, 都具有不太相同的含义, 所以, 经过归一化之后, 它们各自的变化幅度也可能有很大不同, 如果直接用来计算相似度就会引起很大偏差。所以必须要将特征向量的各分量, 都统一的归一化到一定的范围中去。所以, 我们定义特征向量V=rij, 则每一特征向量rij的归一化过程可以如下:

假设数据库中共M幅素材, 而m为素材的索引值, 可以这样定义, 如公式4所示:

表示第m幅素材的特征向量, 而K是特征向量V=rij的维数。如果我们将所有素材的Vm累积在一起, 就能获得维数为M×K的矩阵, 如公式5所示:

其中vm, k是特征向量Vm (对应于第m幅素材) 的第k个分量。为了保证个分量能有相同的重要性, 矩阵的第k列是维数为M的一个列向量, 记为vk。最终将每列中的元索, 都统一归一化到指定的值域标准内, 这样就可以保证在计算两个向量之间的相似度。

根据以上计算, 如果能够融合高斯归一化方法, 可以获得更好的结果。假设列向量vk是一个高斯数列, 可以首先计算该数列的标准方差σk和平均值声μk, 然后式6来实现高斯归一化, 公式定义如公式6所示:

通过结果分析, 将公式6的分母部分, 都替换为经过σk单独归一化后, 数列中的某个值位于区间[-1, 1]范围中的概率大约为68%。如果用式6, 则根据高斯归化后, 其数值在区间[-1, 1]范围中的概率已经达到了99%。所以可以认为数列, 通过该方法所有值都己经在[-1, 1]范围中了, 高斯归一化方法的优点在于, 即便是数列中存在一些异常的数值, 比如过大或者过小, 在计算向量间的相似度时, 也不会导致分量rijk重要性有所偏差, 达到了预期的效果。

4 结束语

通过使用的图像库SIMPLIcity系统提供的测试集。它是从Core图像库中抽取的500幅图像, 分为:人、医疗器械、建筑物、老虎、山峰、食物等, 每类一百幅。分别是使用基于区域的方法对其进行检索, 结果均达到了理想的要求。

摘要：本论文主要针对现在日益增长的多媒体信息检索需求, 以及目前国内外现有的基于区域的图像检索算法的局限性, 深入地探讨了基于区域的图像检索的通用技术问题, 提出了解决方案, 着重于新的图像特征描述方法, 相似度检测、特征提取与快速检索算法等方面的研究, 构建了一个基于区域的图像检索通用模型, 通过大量实验, 验证了方案的合理性。

关键词：基于区域的图像检索,特征提取与匹配,图像分割方法

参考文献

[1]吕英华, 唐昌华, 孔俊, 等.A Content-Based Image Retrieval System Using RBF Neural Network[C]//DCDIS国际会议.2007, 10.

[2]章毓晋.图象工程——图象理解与计算机视觉[M].北京:清华大学出版社, 2000.

简单选择排序算法的改进算法 篇7

排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。排序是将数据元素的任一序列, 重新排列成一个关键字有序的序列。基于比较和移动的排序算法具有通用性, 包括插入排序、选择排序、交换排序、归并排序、基数排序等等。各种排序的算法各具有优缺点, 但就其全面性能而言, 很难提出一种被公认的最好的方法。判断一个排序算法优劣的标准一般为时间复杂度、空间复杂度和稳定性。

一、简单选择排序算法

1、排序方法

选择排序 (Selection Sort) 是最符合人们思维习惯的一种排序方法。基本思路是每次从待排文件中挑选一个key值最小的 (或最大的) 记录放置于它应所在的位置。若待排文件长度为n, 则选择n-1趟便达到排序目的。选择排序一般又分为“直接选择排序”和“堆选择排序”。

2、直接选择排序的C语言算法

对上述算法进行优化, 在一趟中找到key, 如果该key就是i位置上的记录, 就不用交换。算法如下:

3、直接选择排序的算法分析

设排序文件的记录长度为n。算法中共进行了n-1趟选择, 每趟选择一个当前最小key的记录, 要经过n-i (1≤i≤n-1) 次的key比较, 故总的key比较次数C为:

另外, 当文件按key正序时, 记录移动次数等于0。而完全逆序时, 每趟选择后有3次记录移动, 所以最多移动次数为3 (n-1) 。故直接选择排序的时间复杂度T (n) =O (n2) 。直接选择排序属于稳定排序。

二、简单选择排序算法的改进算法

1、排序方法

基本思路是每次从待排文件中挑选一个key值最小的和一个key值最大的记录, 最小的放置于最前面, 最大的放置于最后面的位置。若待排文件长度为n, 则选择n/2趟便达到排序目的。

2、改进算法的C语言算法

3、改进算法的算法分析

设排序文件的记录长度为n。算法中共进行了n/2趟选择, 每趟选择一个当前最小key和最大key的记录, 要经过2 (n-2i) (1≤i≤n/2) 次的key比较, 故总的key比较次数C为:

C和=直ni∑/=1接2 (2选n择-排2i序) 的算法相比, 时间复杂度仍为T (n) =O (n2) , 但选择趟数减少了一半, 比较次数因为内循环中比较了2次, 和直接选择排序比较次数相当。

结束语

本文作者提出的上述改进的选择排序算法, 已通过在VC++6.0环境进行正确性测试。该算法是在简单选择排序的基础上提出来的改进算法, 提高效率是显而易见的。

摘要：排序算法是一种被广泛使用的算法, 在计算机软件领域发挥着重要作用。经典的排序包括:冒泡排序、选择排序、插入排序等等。本文以简单选择排序算法为基础, 对其进行改进, 得出与之具有更高的排序效率。

关键词：选择排序,改进算法

参考文献

[1]严蔚敏等:《数据结构 (C语言版) 》, 清华大学出版社, 2005.7。

[2]潭浩强:《C程序设计》, 清华清华大学出版社, 1999.4。

[3]方同祝、胡正国、田铮、金文凯:《一种节省空间的排序算法》, 《小型微型计算机系统》, Vol.26 No.7 July 2005。

[4]王敏:《改进的双向选择排序算法》, 《信息技术》, 2010年第9期。

区域选择算法 篇8

关键词：计算机图形学,圆,区域填充,Bresenham算法

计算机图形学是研究如何用计算机生成、处理和显示图形的一门学科[1,2]。随着计算机图形学的不断发展, 其应用范围日趋广泛。在计算机显示器屏幕上生成的任何图形都是像素点的集合。圆内区域填充的过程实质上就是寻找最佳逼近给定圆心和半径的圆周范围内的像素点序列, 并向图形卡帧缓存器的相应单元填入颜色数据的过程。作为最低层的计算机图形、图像处理算法, 圆内区域填充算法大量应用于计算机辅助设计与制造、计算机软件用户接口、计算机动画和艺术等领域。因此, 对圆内区域填充算法进行研究, 有着非常重要的意义。

1 基于种子点的圆内区域填充的递归算法

1.1 算法的基本思想[1,2]

基于种子点的圆内区域填充的递归算法是比较经典的算法。其基本思想是:先将圆内区域的一点赋予指定的颜色, 然后将该颜色递归地扩展到整个圆内区域。该算法要求区域是四连通区域和八连通区域。即要求从区域上一点出发, 通过上下左右4个方向的移动组合或上下左右、左上、右上、左下、右下8个方向的移动组合, 在不越出区域的前提下, 能到达区域内的任意像素点。

圆内区域可用内点 (圆内区域的像素点) 表示或边界 (圆周线上的像素点) 表示。因此, 基于种子点的圆内区域填充的递归算法对当前点是否需要进行递归填充的判断标准有两种:一是当前点是旧颜色的内点, 则对它进行递归填充;二是当前点既非已填充为新颜色的内点也非边界点, 则对它进行递归填充。

基于种子点的圆内区域填充的递归算法可以分为四种:内点表示的四连通区域递归填充算法、内点表示的八连通区域递归填充算法、边界表示的四连通区域递归填充算法、边界表示的八连通区域递归填充算法。由于八连通区域的递归填充算法过程非常缓慢, 且有可能出现所填像素点出界的现象[2], 所以, 实际常用四连通区域的两种递归填充算法。

1.2 算法的函数实现

1.2.1 内点表示的四连通区域的递归填充算法

假设 (x, y) 为圆内区域内的一点, oldcolor为圆内区域填充前的颜色, 需将整个圆内区域填充为新颜色newcolor。内点表示的四连通区域的递归填充算法的实现函数如下:

1.2.2 边界表示的四连通区域的递归填充算法

假设 (x, y) 为圆内区域内部的一点, boundarycolor为原圆内区域边界的颜色, 需要将整个圆内区域填充为新的颜色newcolor, 则可以构造边界表示的四连通区域的递归填充算法的实现函数如下:

对于内点表示的八连通区域以及边界表示的八连通区域的递归填充算法的实现函数只需要将上述两段四连通区域的递归填充算法的实现函数代码中增加左上、左下、右上、右下四个方向相邻的像素点的递归调用函数即可。

1.3 算法的不足

递归算法实现时, 计算机系统自动设置和管理系统堆栈。每调用一次递归函数就“入栈”一次, 函数执行完一次, 结果就“出栈”一次。圆内区域填充的递归算法函数的递归调用次数由需要填充的像素点数目决定。所需要填充的区域越广, 所覆盖像素点越多, 函数递归调用次数就越多, 系统“入栈”和“出栈”操作越多, 所消耗的内存空间等系统资源越多, 执行时间就越长。当递归调用次数达到一定数目时, 就会耗尽系统资源, 导致应用程序无法运行。

实际应用中, 对圆内区域进行填充时, 所覆盖的像素点数目一般至少是成百上千、甚至是成千上万的。因此, 用基于种子点的圆内区域填充的递归算法填充时, 不但速度慢, 而且还有可能导致程序无法运行、填充任务无法完成的情况发生。因此, 基于种子点的圆内区域填充的递归算法的应用只局限于需要填充区域较小的情况。

2 基于改进的Bresenham圆生成算法的圆内区域填充新算法

2.1 圆的八对称性

圆心位于原点的圆有四条对称轴x=0, y=0, x=y和x=-y。如果已知圆心在 (xc, yc) 的圆弧上一点 (x, y) , 可以得到该点关于上述四条对称轴的其它7个点 (xc+x, yc+y) 、 (xc-x, yc+y) 、 (xc+x, yc-y) 、 (xc-x, yc-y) 、 (xc+y, yc+x) 、 (xc-y, yc+x) 、 (xc+y, y c-x) 、 (xc-y, yc-x) 。这种性质称为圆的八对称性。由圆的八对称性可知, 生成一个圆时, 只要扫描转换生成该圆上1/8段的圆弧, 就可以求得构成整个圆的像素点集合。

目前, 经典的圆生成算法都基于圆的八对称性。对圆心在原点 (0, 0) 、半径为r的圆, 经典的圆生成算法首先考虑以 (0, r) 为起点, 按顺时针方向生成第一向限的1/8段圆弧的情况。然后, 再根据圆的八对称性, 生成整个圆。生成圆心在 (xc, yc) 、半径为r的圆, 则只需将圆心在原点 (0, 0) 、半径为r的圆作平移就可得到。

2.2 Bresenham圆生成算法的基本思想[1,2]

在经典的Bresenham圆生成算法中, 将圆表示为:y2=r2-x2。如图1所示, 在第一向限的1/8段圆弧上取当前像素点为 (xi, yi) , 那么要取的下一个用于近似精确交点Q (xi+1, y) 的像素点是垂线x=xi+1上的点P 1 (xi+1, yi) 或P 2 (xi+1, yi-1) 。

选择P1或P2的原则是P1与P2中与Q距离最小者。由于距离为正值, 用距离的平方代替距离不影响P1或P2的选择, 所以, 为了提高运算效率, 可以避免开方运算。具体计算式为:

令距离差pi=d1-d2, 并代入d1, d2, 则有:

(1) 若pi≤0, 说明P1与Q距离近, 则应取P1为下一个近似像素点。此时, 下一步以P1 (xi+1, yi) 为当前点时, 再求下一个近似像素点的pi的递推式为:

(2) 若pi>0, 说明P2与Q距离近, 则应取P2为下一个近似像素点。此时, 下一步以P2 (xi+1, yi-1) 为当前点时, 再求下一个近似像素点的pi的递推式为:

(3) 根据起点 (0, r) , 得pi的初始值为:

2.3 Bresenham算法的函数实现

pl ot_ci rc le_po int s (xc, y c, x, y, c) ;

2.4 圆内区域填充新算法的基本思想

使用Bresenham圆生成算法生成圆心在 (xc, yc) 、半径分别由零依次增加一个像素点, 最后变为给定的半径r的多个圆的效果实际就相当对给定圆心 (xc, yc) 和半径r的圆内区域进行填充的效果。因此, 基于Bresenham算法的圆内区域填充新算法的基本设计思想很简单, 只需要设计FOR循环, 从零开始每次增加一个像素点, 直到变为指定要填充的圆半径为止。循环体中直接调用Bresenham算法生成循环控制变量为半径的圆即可。

然而, 实例运行结果显示圆内区域存在较多像素点没被填充到。经过仔细分析, 发现其原因在于:用Bresenham算法生成圆时, 得到当前像素点P (xi, yi) 后, 后继点 (xi+1, yi+1) 只考虑了取P 1 (xi+1, yi) 和P 2 (xi+1, yi-1) 的两种情况。而取P2为后继点时, 中间存在漏点现象。实际上, 在取P2之前, 点P1 (xi+1, yi) 或P3 (xi, yi-1) 也可能是圆弧上的点。如图2所示。

如果P1到圆弧的距离小于P3到圆弧的距离, 则P1为漏点, 应该补上P1;反之, 应该补上P3。现令d3为P3到圆弧距离的平方, 则有:

那么, P1到圆弧的距离平方d1与P3到圆弧的距离平方d3之差为:

当d1-d3>0时, 需要补上的漏点是P3, 否则, 需要补上P1。

2.5 改进Bresenham算法的函数实现

2.6 圆内区域填充新算法的函数实现

由以上两个函数可知, 基于改进Bresenham算法的圆内区域填充新算法只需做整数加法、整数乘2和整数乘4的运算, 并且涉及到的数据结构很简单, 所以, 算法运行速度很快, 适宜于在硬件上实现。

3 实例分析

3.1 实例及其运行结果

给定圆心在 (200, 200) 、半径为100和45的两个圆, 分别使用基于种子点的递归算法、基于Br es en ha m算法和基于改进Bresenham算法的圆内区域填充新算法将此圆内区域填充为白色。假设对应三种算法, 实例分别取名为实例1、实例2、实例3。在酷睿双核2.4G CPU、4G内存的机器上的Turbo C2.0中运行实例1、实例2、实例3。其运行结果如表1、表2所示。

3.2 运行结果比较分析

根据表1和表2对实例运行结果进行比较分析如下。

(1) 表1中实例1运行失败, 体现了基于种子点的圆内区域填充的递归算法的局限性。失败原因是因为半径为100的圆区域所覆盖像素点较多, 函数递归调用次数达到极限, 耗尽系统资源, 导致程序实例无法成功运行。表2中对半径为100的圆区域填充时, 实例1虽然运行成功, 但运行时间远比实例2和实例3多很多。说明算法运行速度显著慢于实例2和实例3。

(2) 表1和表2中实例2的运行结果表明:用基于Bresenham算法的圆内区域填充新算法进行填充时, 虽然运行时间短, 算法运行速度快, 但是随着所需要填充圆内区域的半径增大, 未被填充到的像素点 (显示为黑色的点) 逐渐增多。

(3) 表1和表2中实例3的运行结果表明:用基于改进Bresenham算法的圆内区域填充新算法进行填充时, 运行时间只稍多于实例2, 但是圆内区域能全部被填满。说明该算法不但运行速度快, 而且即使所需要填充圆半径增大, 圆内区域的所有像素点全部能被填充到。

(4) 笔者经过多次尝试发现, 圆半径大于49时, 实例1就无法成功运行, 系统就会提示“TC NTVDM CPU遇到无效的指令选择‘关闭’终止应用程序”。然而, 实例2和实例3即使圆半径取为TC中整型变量的最大值216-1=32767, 都能运行成功, 并且运行速度都很快。

综上所述, 基于改进Bresenham算法的圆内区域填充新算法相对于基于种子点的圆内区域填充的递归算法而言, 具有简单、运行速度快、占用内存空间等系统资源少的优点。

参考文献

[1]潘云鹤, 董金祥, 陈德人.计算机图形学——原理、方法及应用 (修订版) [M].北京:高等教育出版社, 2003, 12:26～37.

两种区域内外测试算法的研究 篇9

奇-偶规则和非零环绕数规则比传统的扫描线算法更高效，在时间复杂度和空间复杂度上都有所减少。但是这两种方法还存在问题：对普通的多边形两种方法都适用，但是对复杂多边形来说奇-偶规则就不太适用;这两种方法，没有对特殊情况作出解决方法，例如，当水平射线与多边形顶点相交，当水平射线与多变形的边相交等情况上对填充点的点亮问题没有给出合适的解决方法。由于奇-偶规则和非零环绕数规则在有关文献和研究成果并不多见，本文就这两种方法做详细的介绍，并对实际的应用情况作相应的比较。

1 两种算法的概念

1.1 奇-偶规则

奇-偶规则是从任意位置p作一条水平射线，若与该射线相交的多边形边的数目为奇数，则p是多边形内部点，否则是外部点。对于内部的点，用颜色值来点亮，外部点，则用背景色点之。利用奇-偶规则来判定一个点是内点还是外点，也有特殊的情况。如图1，对基本的情况，用奇-偶规则的定义很明显的就能判定出来，但是对于特殊情况就要进行讨论并做特殊的处理：当任意位置作出的水平射线与多边形的两条边都相交，两条边分别落在水平射线的两边，这时，交点的个数算一个。若两条边同时落在了水平射线的一边，此时，交点的个数作为零;当从任意点引的水平射线与多边形底边重合，对多变形的水平边通常不作考虑。

1.2 非零环绕数规则

非零环绕数规则使多边形的边变为矢量，将环绕数初始化为零，再从任意位置p作一条射线。当从p点沿射线方向移动时，对在每个方向上穿过射线的边计数，当多边形的边从右到左穿过射线时，环绕数加1，从左到右时，环绕数减1。处理完多边形的所有相关边之后，若环绕数为非零，则p为内部点，否则，p是外部点。具体的说明如图1。

图(a)，从点P引出一条水平射线，该射线与多边形的两边相交，由于多边形的边已经矢量化，所以对于CD边，是从射线的左到右，此时环绕数减一。对于AB边，是从射线的右到左，此时环绕数加一。最后环绕数累计为0，点P为外部点;图(b)，从P点引出的水平射线与多边形的AB边相交，从射线的右边到左边，环绕数加一，最后累计环绕数为1非0,P为内部点。非零环绕数的实现方法描述如下：

第一种方法叉乘法，向量S是多边形的一条边向量，S1,S2分别是该边的两个端点的向量，则S的边向量表示为为S1-S2，转化成坐标为(Sx,Sy)。从P点引出的射线向量为(Px,Py)，则S与P的叉乘为PxSy-PySx;从P点出发的射线向量与穿过射线的每条边的边向量S叉乘，如果叉乘的结果为正，则说明边是从射线的右边穿到左边，环绕数此时加一。否则，环绕数减一;第二种方法引入垂直于射线向量的向量U，设置该向量时最好是从点P沿着射线向量方向看是从右到左指向的向量，射线向量为(Px,Py)，所以垂直于该向量的元素有(-Px,Py)，于是判定条件可以转化为：从点P引出的水平射线向量的垂直向量与该射线的相交边向量的点乘为正，则环绕数加一，否则，环绕数减一。

2 程序实现

为了简化程序，减少时间复杂度，把奇-偶规则和非零环绕数规则结合在一起。相互弥补两种规则的不足。其中cross()判断水平射线是否与多边形的某边相交,参数P1,P2为多边形两顶头坐标,P为待判定的点。isinner()点坐标是否位于内部区域,参数num为多边形的顶点数,px()为一数组,各元素均为POINT类型,存放多边形各顶点坐标。

3 结束语

论文介绍了鉴别物体内部点的方法。对规则的(即不自交)多边形或者简单的形状，非零环绕数规则和奇-偶规则都能给出相同的判定结果;但是对于比较复杂的情况，这两种规则可能会产生不同的内部和外部区域，而且对于非零环绕数规则，如果是规则的多边形或者简单的形状，采用平面向量的计算方法就可以，但是对于复杂的空间的多边形，则要采用空间向量的计算方法。一般来说，非零环绕数规则比奇-偶规则更为通用。

参考文献

[1]孙家广.计算机图形学[M].北京:清华大学出版社,2000:178-182.

[2]柳朝阳,周晓平.计算机图形学-图形的计算与显示原理[M].西安:西安电子科技大学出版社,2005:46-56.

[3]孙正兴,周良,郑宏源.计算机图形学基础教程[M].北京:清华大学出版社,2004:68-70.