缩放算法范文

缩放算法范文（精选7篇）

缩放算法 第1篇

在实际应用中,经常需要对数字图像进行尺度转换,在改变图像尺寸方面,文献[1-8]提出了通过三次样条插值、三次卷积插值、二维快速傅立叶变换进行图像尺寸转换的方法;这些算法比较简单,性能受到了明显的限制。

围绕图像缩放技术,本文对时域内各种算法的性能进行分析比较,并且在频域内研究了二维可分离插值滤波器和不可分离插值滤波器,这两种方法都是将对通带和阻带的要求作为优化的目标,以滤波器的结构为约束条件,将滤波器的设计转化为一个约束优化问题进行解决。

1 时域缩放算法

1.1 最近邻插值

最近邻插值,是用图像中的特定点的像素值填充缩放后的图像,即将原始的信号进行逐点处理,把其中的每一点都用其灰度值进行m次复制(m为缩放倍数),即输出像素的灰度值等于离它所映射到的位置最近的输入像素的灰度值。最邻近插值计算十分简单,在许多情况下,其结果也可令人接受。然而,当图像中包含像素之间灰度级有变化的细微结构时,最邻近插值法会在图像中产生人工的痕迹,出现明显的块状现象,整幅图像十分粗糙。

1.2 双线性插值

线性插值算法由于其较低的计算量和高于最近邻域插值的代数逆合(二阶)而被广泛应用。因为采用线性插值算法在对图像的放大是对行列信号作两次处理后得到的,所以称这种方法为双线性插值。但是,它通常会平滑掉图像中许多重要的高频信息。

双线性插值比最邻近域法产生的图像平滑,但当放大倍数增大时,放大后的图像会出现明显的块状现象。线性插值基本思想就是把目标点附近的原始点的灰度值按一定的权值相加。

1.3 二次插值

二次插值采用对称二次多项式:

1.4 三次插值

三次插值也称三次卷积插值,高精度三次样条插值或者双三次插值[10,11,12,13,14],它是sin x/x的一个近似。其表达式为:

式中a为正则化参数。

1.5 三次B样条插值

三次B样条曲线是由多条三次多项式曲线拼接而成,整条曲线二阶连续可导。对于三次B样条曲线,设其控制点为P0,P1,,Pn。第i段曲线可以用矩阵形式表示为:

在图像放大时,需要由图像上的点反算出B样条控制顶点,这就是B样条曲线的逆问题。讨论三次B样条,从每一小段三次B样条曲线的端点与控制顶点的关系:

用矩阵表示为:

4 22 4 22 4 2熿燀燄燅2 4P0P1Pn-1P熿燀燄n燅=6Q0Q1Qn-1Q熿燀燄n燅(5)

求出控制点P0,P1,,Pn以后,将其代入式(3),用新的采样间隔选取t值,可以得到一组新的采样点作为放大后图像上的点。

1.6 拉格朗日插值

自由度为N-1的拉格朗日插值基函数定义为:

烆0,其他

式中i=j-N/2+1。

1.7 高斯插值

M阶高斯插值基函数:

时域内各种方法性能比较:

通带:最近邻插值和线性插值以及二次插值在通带内偏离理想的矩形形状较大。因此在做插值时图像将被平滑,这些方法仅使适用于没有尖边和局部高对比区域的场景图像。最好的通带特性可以由三次B样条插值、三次插值和具有较大核尺寸的拉格朗日插值及所有的高斯基函数实现。

截止频率:三次B样条插值以及三次插值、拉格朗日、高斯基函数(N>4)具有较好性能。最糟糕的是最近邻插值。考虑到截止标准,应该避免使用线性插值。

阻带:阻带特性影响到混叠和波纹效果。最近邻插值、线性插值、二次插值、44三次插值和拉格朗日插值产生波纹和旁瓣大于1%。截断Gaussian函数低于0.1%。

综合通带、阻带及截止频率的傅里叶分析,最近邻插值和线性插值应该避免,高斯基函数(N较大者)具有较好性能。

2 频域缩放算法

在频域里可以根据对阻带和通带的技术要求进行设计,从而能够保证良好的通阻带特性,以尽量减少在图像缩放时的失真。

2.1 二维快速傅里叶变换法

对于时域数据的频谱图,如果从频谱图中去掉一些频率分量,然后作IFFT,得到时域数据,可以实现对图像的缩小。而如果在频谱中加入一些零值,再作IFFT,得到时域数据,则可实现对图像的放大。二维快速傅里叶变换法是先将时间序列进行傅里叶变换,然后构造一个中间序列,利用这个中间序列进行二维傅里叶逆变换,实现图像缩放[14]。

2.2 二维可分离插值滤波

文献[14]提出一种分离变量的有理因子图像尺寸转换方法,即将图像尺寸的缩放转化为变量可分离的两个一维离散信号的采样率转换来处理:分别沿着图像的水平方向和垂直方向,在离散域独立地进行采样率转换,对图像的列和行进行尺度转换。

在多速率信号处理中,上采样过程和下采样过程分别会带来混叠效应和镜像效应,这些效应会降低图像的质量,因此必须加以抑制。所以上采样之后的信号必须经过一个低通滤波器进行滤波。在下采样之前,用一个低通抗混叠滤波器以限制频带是必不可少的。

理想插值滤波器是截止频率为π/L,通带增益为L的低通滤波器。引进目标函数为:

式中:α,β为权系数;H(ω)为h(n)的傅里叶变换;ε为过渡带宽。

通过求下式优化问题即可实现插值滤波器。

式中:h0(m)为插值滤波器h(n)的第一个多相位分量,第三个条件为正则阶条件,正则阶条件保证了内插尺度滤波器在ω=0附件的平坦性。

抗混叠滤波器g(n)的设计同插值滤波器。

2.3 二维不可分离插值滤波

二维可分离插值滤波器将二维图像信号分为水平方向和垂直方向的一维信号,使问题得到简化,但为了更好地保持图像的重要细节信息,可以采用二维不可分离的插值滤波器进行设计。由于不可分插值滤波器的优化自由度比可分插值滤波器的高得多,在相同通带和阻带性能要求下,不可分插值滤波器支撑区更小,空间局部性更好,从而在图像尺寸转换过程中能够更好地保持原有图像的重要信息[15]。

二维不可分对称插值滤波器设计可以描述成下面一个带线性约束的二次优化问题:

s.t.正则阶约束条件

对称约束条件:

二维可分离和不可分插值滤波器由于需要求解最优函数,因此需要较长的计算时间,对于那些对转换速度要求比较高的场合不太适合,但由于这两种方法由于可以严格保证通带和阻带性能,因此变换后的图像具有较好的质量,因此这两种方法适宜质量要求高,而对速度要求不是太高的场合。

3 图像缩放实例

几种图像尺寸缩放方法的示例如图1所示。从图1中不难看出几种方法的优点和缺点,其中二维不可分离插值滤波器器的方法放大后的图像效果最好。

4 结语

本文从频域和时域出发,简要介绍了几种常见的图像尺寸缩放方法,并指出了它们的优劣。在进行插值方法选择时,应尽量避免使用最近邻插值和线性插值两种方法,而选用高斯插值,若对图像转换质量要求非常高,建议采用二维不可分插值方法。

摘要：时域内常用的几种图像缩放算法有:最近邻插值、线性插值、二次插值、三次插值、拉格朗日插值、高斯插值等,对这些算法的性能进行分析比较,综合通带、阻带及截止频率,最近邻插值和线性插值应该避免,高斯基函数(N较大者)具有较好性能;并且在频域内研究了二维可分离插值滤波器和不可分离插值滤波器,这两种方法以对通带和阻带的要求作为优化目标,以滤波器的结构为约束条件,将滤波器的设计转化为一个约束优化问题进行解决;实验结果表明二维不可分离插值滤波器的方法图像缩放后的效果最好。

自适应图像缩放算法及其硬件设计 第2篇

图像缩放算法是数字图像处理中一个重要的内容。时至今日,数字图像显示设备的图像分辨率随着显示屏尺寸的增大而不断提高。而高分辨率的数字图像具有很大的数据量,其传送和存储都会对硬件系统资源提出很高的要求。所以人们希望能够存储和传输低分辨率图像,而只在显示时展现高分辨率图像。另外,各种各样的数字图像显示设备也要求图像分辨率能够方便地转换。这些都是图像缩放算法的用武之地,多年来,图像缩放算法一直是一个研究的热点。

图像缩放最简单的算法就是直接丢弃像素或者复制像素,这种算法尽管简单,但容易引起图像细节的失真。就图像的空间缩放所依赖的模型来说,许多传统的图像放大和缩小方法实质上是对源图像建立连续的数学模型(即二元连续函数),然后按照缩放要求进行重采样,得到目标图像,如学术界最早提出的几何变换、最近邻域插值法(nearest neighbor),双线性内插法(bi-linear interpolation)、三次内插法等等,为改善缩放后的图像质量,学术界先后提出了很多的改进的方法。所有这些方法都可以看成将离散数字图像建成相应的连续数学模型,其优点是快速生成目的图像,视觉效果较好;缺点是物体边沿比较模糊,有锯齿。

1 自适应图像缩放算法

经典的图像缩放算法不加区别地对整副图像的各个区域实行同样的缩放算法。虽然非物体边沿部分图像可以得到比较理想的缩放效果,但是在物体边沿部分图像,边沿线会被模糊化。为此,有许多研究者提出了保存边沿的图像缩放算法。

本文介绍一种基于图像块特征分析的自适应图像缩放算法,该算法通过分析各个图像区域的特征,检测该图像区域中的物体边沿信息。对边沿部分采用特殊的有向插值,对非边沿部分采用普通的双线性插值,以此来保持图像边沿的锐利度。

1.1 图像块分类算法

本算法根据图像区域的特性选择不同的插值算法,所以首先就是要判断图像区域的特性。检测图像区域是否含有边沿信息,如果是,就称该图像块为有向块,否则称为均匀块。

将图像划分成许多的44块,然后判断这个44块是一个有向块还是均匀块。判断方法是:首先要计算每一个44块中16个点的方向。当计算像素(i,j)的方向的时候,需要知道该像素相邻的8个像素的值,计算像素(i,j)在x方向和y方向的梯度如下:

将x和y方向的梯度相除,并作反正切计算得到像素(i,j)的方向如下:

θ=-57.2985*arctan(fy/fx)mod180

再将方向量化到8个量级,如下:

${\rm O}=\left[\frac{\theta -11.25}{22.5}\right]\text{m}\text{o}\text{d}8$

就得到像素点(i,j)的方向。对一个44块中16个点按八个量化方向进行统计,如果8个量化方向中数目最集中的那一个方向的点的数目超过了6,那么就把这个44块定义为有向块,这个方向定为该44有向块的方向。否则定义为无向块。两种不同的44块有不同的滤波算法。

1.2 有向滤波算法

有向图像的数学模型如下:

$f(x,y)={\displaystyle \sum _{j=0}^{d-1}a}{}_j(y\cos \alpha -x\sin \alpha ){}^j$

其中,α是该有向块的方向,αj通过对44块中的像素进行最小平方建模得到。d是该式子的参数维度,在有向块方向为垂直或水平,设定d=4,其他情况下设定d=7。这样可以得到

f(x,y)=h(HTH)-1HTf

其中,f是一个161的矢量,

f=[p0,p1,,p15]T

p0,p1,,p15是44块中的16个像素点,依光栅扫描的顺序排列。H是一个16d的矩阵,每一个元素为:

Hi,j=(yicosα+xisinα)j-1

xi和yi是pi所对应的坐标,如图3所示。h是一个1d的矢量,其元素为:

hi=(ycosα-xsinα)j-1

定义向量z如下:

z(α,x,y)=h(HTH)-1HT

指定x,y得到向量a,b,c如下:

a(α)=z(α,0.5,0.0)

b(α)=z(α,0.0,0.5)

c(α)=z(α,0.5,0.5)

插值的输出是:

O1=p5,O2=a(α)f,

O3=b(α)f,O4=c(α)f

2 硬件架构设计

实现该算法的VLSI硬件架构主要分为梯度计算,方向计算,方向统计和滤波器四个模块。梯度计算模块输出x和y方向的梯度。方向计算模块输出每个像素点的量化方向O,存入RAM中。方向统计模块从RAM中取出像素点,进行统计,得出44方向块的方向,送入滤波器进行滤波。

2.1 方向计算

硬件实现中最大的难点是如何计算反正切函数。这可以采用CORDIC算法设计。CORDIC是利用旋转坐标的方法用简单的加法和移位操作就可以完成三角函数值的计算。

利用正/余弦的和角公式递归进行:

cos(a+b)=cos(a)[cos(b)-tan(a)sin(b)]

sin(a+b)=cos(a)[tan(a)cos(b)+sin(b)]

写成矩阵形式如下:

$\left[\begin{array}{l}\cos (a+b)\\ \sin (a+b)\end{array}\right]=\cos (a)\left[\begin{array}{cc}1& -\tan (a)\\ \tan (a)& 1\end{array}\right]\left[\begin{array}{l}\cos (b)\\ \sin (b)\end{array}\right]$

假设有一个初始点(x(i),y(i)),距离远点l(i),角度z(i)=b,经过一次逆时钟角度增量为a的旋转,得到新的点(x(i+1),y(i+1)),角度z(i+1)=a+b,距离原点l(i+1)。上式可变化为

$\begin{array}{l}\left[\begin{array}{l}x(i+1)\\ y(i+1)\end{array}\right]=\cos (a)*\frac{l(i)}{l(i+1)}\\ \left[\begin{array}{cc}1& -\tan (a)\\ \tan (a)& 1\end{array}\right]\left[\begin{array}{l}x(i)\\ y(i)\end{array}\right]\end{array}$

上式说明,一个初始点的坐标经过变化,可以得到一个新的经过一定角度增量旋转的新的坐标点。取α=arctan(2-k),即tan(α)=2-k,则新坐标点的计算可通过移位和减法来实现。这就是CORDIC算法的原理。

任何角度z在一定的精度要求下都可以表示为

z=s(0)arctan(20)+s(1)arctan(21)++s(n)arctan(2-n)

其中,S(0),S(1),,S(2)取+1或-1(+1可以理解为逆时针转角,-1则相反),利用CORDIC算法和角度的表示方式,可以设计出根据横纵向梯度来计算反正切函数的硬件结构。

将整个44块的方向量化成了8个方向,在第一象限共有四个量化方向,分别是11.25, 33.75, 56.25, 78.75度,它们可以如下表示:

硬件设计如图1所示。

2.2 方向统计

方向统计硬件结构如图2所示。方向统计模块负责统计一个44块中各个像素点在8个量化方向上的分布数量,把16个点的3比特量化方向输入3-8译码器,然后把16个3-8译码器的8根表示8个不同量化方向的输出线,按方向输入8个相应的16-4编码器,这种编码器的功能是统计16根输入信号中有几个信号被拉高了,以得到每个编码器对应的8个量化方向上像素点的数量。最后从这8个量化方向中找出一个最大值。

2.3 滤波器

滤波器得到44块的16个像素点和这个44块的方向后,开始滤波。首先用方向α对ROM表进行检索,检索到a,b,c三个向量。输入三个FIR滤波器与16个像素点进行FIR滤波。

3 仿真和综合结果

评估自适应图像缩放算法的好坏的指标是PSNR和MSE。

评估方法是选取lena,pepper和camera三副512512的图像,首先下采样到128128,然后用最近邻域法,双线性法和自适应法插值到512512。然后比较三种插值算法得到的512512图和原图之间的PSNR和MSE。比较结果见表1和表2。总的来说,新的自适应算法在PSNR和MSE两个指标上都有比较好的表现。

整个硬件代码在Xilinx Vertex4 XC4VFx60上综合,消耗1125Lut资源,综合频率为128MHz。

4 结束语

介绍了一种自适应滤波算法,旨在解决传统的图像缩放算法把物体边沿模糊化的问题。该算法对图像像素块进行分析,能有效识别出图像的边缘特征。然后对边缘部分的图像实行有向滤波,而对非边缘部分的图像实行普通的双线性插值滤波,从而克服一般滤波器边缘模糊化的问题。

本文对该算法进行硬件设计,重点解决了方向计算和滤波器结构的设计。仿真和综合结果显示,该算法缩放性能较好,硬件实现也不复杂。

参考文献

[1]Deprettere E,Dewilde P,Udo R.Pipelined CORDIC Architecture forFast VLSI Filtering and Array Processing[Z].Proe.ICASSP’84,1984:41-61,64.

[2]Wang Y,Mitra S K.Image representation using block pattern modelsand its image processing applications[J].IEEE Trans.Pattern Anal.Machine Intell.,1993,15:321-336.

[3]张新楼.图像缩放算法的研究及其在FPGA上的实现[D].兰州大学2005届硕士学位论文.

[4]霍宏涛.数字图像处理[M].北京理工大学出版社,2002,9(1).

缩放算法 第3篇

用户利用网络共享数据源, 通过浏览器调用执行相关程序即时生成需要的图幅, 称为实时绘图。它与传统的CAD绘图相比有如下优势:实时性, 用户可随时绘制需要的图幅;独立性, 用户不需要依赖于计算机专业技术人员, 即可完成绘图工作;节省磁盘空间, 用户可根据需要随时绘制输出图幅, 不必对形成的图幅进行存储。

二、无极缩放算法的实现

无极放大:选中要放大的区域, 在图幅窗口中按下左键并拖动出现一个矩形框, 释放左键, 即可放大指定位置上的图幅, 这种操作可以执行任意次, 所以称为无极放大。

无极缩小:在图幅窗口中按下左键并在任意方向拖动一段距离, 释放左键, 程序即可按照该距离长度作比例缩小图幅。

2.1无极缩放算法设计

2.1.1 传统井位图一般绘图步骤。

(1) 根据给定所有井点的坐标数据, 求出横坐标的极值Xmax、Xmin, 纵坐标Ymax、Ymin。 (2) 根据上述坐标极值及屏幕窗口尺寸width, high求出绘图比例尺。

(3) 把所有实际坐标点换算成屏幕坐标, 并把换算后的结果及井号分别存储在三个一维数组x[]、y[]、jh[]中。

(4) 利用换算后的坐标在屏幕上绘图。

2.1.2 无极缩放算法的数据存储结构。

按照上述方法绘制的图幅无法进行无极放大、缩小, 可以把以上的三个一维数组的信息存储在一个二维数组jh[x][y]中, 数组的下标即是该井换算之后的屏幕坐标, 数组的值即是该井的井号。

2.1.3 求出矩形框左上角点的原始屏幕坐标。

当鼠标点下左键时, 利用mouse Down () 方法可获得该点的目前屏幕坐标x和y, 之后可根据该点的当前屏幕坐标及当前图幅的比例尺、起始点坐标三项数据求出该点的原始屏幕坐标。

2.1.4 求出矩形框右下角点的原始屏幕坐标。

当鼠标拖拽出一个矩形后释放左键时, 利用mouse Up () 方法可获得该点的当前屏幕坐标x和y, 之后可根据该点的当前屏幕坐标、当前图幅的比例尺、起始点坐标, 计算出该点的原始屏幕坐标。

2.1.5 计算出矩形框的两个关键点的原始坐标后的操作。

计算出矩形框的两个关键点的原始坐标和新的比例尺后, 即可利用paint () 方法绘制放大后的图幅, 具体方法是按照新的比例尺在屏幕范围内绘制所选矩形框内的所有井点, 其它井点不予绘制。至此, 无极缩放的算法全部实现。

三、结论

无极缩放功能的实现, 解决了大型实时图幅的屏幕浏览问题。本文以java绘制的井位图为例, 但该算法同样适用于其它编程工具, 唯一的要求是所选开发工具应具有屏幕交互功能;该算法也同样适用于其它基于地理坐标的图幅, 比如等值线图、套损图, 开采现状图等, 因此本文提供的算法具有广泛的适应性。

摘要：油田开发工作中, 技术人员有必要实现图幅的无极放大、缩小、漫游功能, 使用户即可以清楚地看到图幅的每一个细节又可以纵览图幅的全貌。本文介绍了无极缩放算法, 并以Java语言编制的井位图为例, 给出了具体实现方法和技术。

缩放算法 第4篇

美国学者Lansey和Eusuff于2003年提出一种结合模因进化算法(memetic algorithm,MA)和粒子群算法(particle swarm optimization,PSO)优点的新型仿生物学智能优化算法———混合蛙跳算法(shuffled frog leaping algorithm,SFLA)。混合蛙跳算法不仅概念简单、容易实现,而且具有全局搜索能力强的特点,广泛应用于各种优化问题中[1,2,3,4]。但其容易收敛于局部最优解,收敛速度不快且求解精度较低,在解决高维复杂优化问题时效果不理想,主要原因是粒子种群的多样性在算法进化后期快速下降,且局部搜索能力较弱。为了改善混合蛙跳算法性能,国内外学者进行了大量研究。文献[5]在子群局部搜索过程中引入“搜索加速因子”,使算法的全局寻优能力在一定程度上得到了提高。文献[6]在子群局部搜索策略中结合吸引排斥机制,有效提高了算法局部寻优能力。文献[7]把可调整变异尺度的变异算子引入到全局迭代中,提高了算法的求解精度。文献[8]结合高斯变异和柯西变异优点,提出了一种自适应混合变异蛙跳算法,增强了算法后期跳出局部极值的能力。

本文在传统混合蛙跳算法更新策略中引入自适应缩放因子和欧式距离,避免了算法早熟现象发生,将传统算法中的随机更新操作改为可调控制参数产生新个体方法,从而提高了算法收敛速度。仿真实验结果表明,与传统混合蛙跳算法相比,本改进算法在收敛速度和精度上效果更好、性能更优。

1 混合蛙跳算法

混合蛙跳算法属于协同进化算法,它受自然界生物模仿启示而产生。算法中每只青蛙代表问题的一个解,不同青蛙个体之间相互交流,从而实现模因进化。混合蛙跳算法先随机产生一组初始解(种群),再将整个种群分成规模相同的多个子群,每个子群按照一定的搜索策略执行局部搜索。在达到一定次数的局部搜索后,又混合所有青蛙,再划分子群,使各个子群间的信息获得全局交换。当满足收敛条件或达到最大进化代数时,各子群局部搜索和全局信息交换才停止。

混合蛙跳算法基本步骤[9]:

(1)生成初始种群。随机生成P只青蛙作为初始种群,假设空间维数为D,则第i只青蛙的坐标为Xi=(x1i,x2i,…,xDi)。

(2)排序。首先根据公式计算出每只青蛙的适应度值,然后按照计算结果降序排列P只青蛙,整个种群中适应度最优的蛙用Fg表示。

(3)划分子群。将整个种群划分为m个子群,每个子群中包含n个青蛙,显然满足P=m*n。划分过程中,序号为1的青蛙分入第1个子群,序号为2的青蛙分入第2个子群,分配直到序号为m的青蛙分入第m个子群。之后,序号为m+1的青蛙又分入到第1个子群,序号为m+2的青蛙分入到第2个子群,依次重复,直到分配完P只青蛙。图1体现了划分结果,每个方框表示一个子群,共m个子群,每个子群内有n个个体。

(4)局部搜索。用Fb表示每个子群中适应度最好的蛙,Fw表示适应度最差的蛙。混合蛙跳算法规定只对每个子群中适应度最差的蛙Fw进行更新。图2为青蛙更新策略示意图,表达式如式(1)所示。

其中:r表示0到1之间的随机数,F′是根据式(1)计算出的新蛙。如果F′的适应度优于Fw的适应度,则Fw会被F′代替,否则用Fg替换Fb重复执行式(1)。如果F′仍不能优于Fw,则采用随机生成方法产生一个新蛙取代Fw。以上操作在每个子群内重复循环执行,直到满足指定的局部搜索次数为止。

(5)全局信息交换。当所有子群的局部搜索计算完成后,合并所有子群中的青蛙,然后根据适应度值重新排序并再次划分子群,最后返回步骤(4),如此反复直到满足算法结束条件为止。

2 改进的混合蛙跳算法

2.1 更新策略改进

由图(2)可知,传统混合蛙跳算法中子群最差蛙Fw经更新后不可能优于Fb,而且不难发现,更新后的位置受限于它的当前位置与子群最优蛙Fb的位置。因此,局部搜索空间在很大程度上被限制了。此外,由式(1)可知,子群最差蛙Fw的模因信息只学习了子群最优蛙Fb,这必然导致局部搜索过程中Fb几乎不更新,算法的收敛速度会因为上述问题的存在而降低,更容易陷入局部最优,从而发生早熟现象。

为解决上述问题,本文改进了传统算法中的青蛙更新策略,在青蛙模因交流过程中引入自适应缩放因子及欧式距离,改进后的更新策略为:

其中:Fj表示子群中的第j个蛙(j=1,2,3,…,n);r为0~1之间的随机数;c1表示子群最差蛙Fw学习子群中其它蛙的学习系数,设在1~2之间;c2表示子群最差蛙Fw学习种群最优蛙Fg的学习系数,在区间[0,ASF]内变化。ASF称为自适应缩放因子,在执行更新操作前被确定。ASF的值越小则搜索过程越慢,从而降低了算法收敛速度。ASF值越大则加快搜索过程,但会使种群多样性快速下降,容易导致算法陷入局部最优。对于ASF取值,本文采用Rechenberg的1/5规则,这个规则具体描述如下:

如果式(2)和式(3)成功进化的次数与当前局部搜索次数的比(c2(k))大于1/5,则ASF的值将减小。如果c2(k)小于1/5,则ASF的值将增大,从而提高搜索速度。改进后的更新策略中,进化过程由c1和ASF控制,提高了局部搜索空间,维持了种群多样性,避免了早熟现象发生。

式(2)中,子群第j个蛙与最差蛙Fw的欧式距离用E(Fj,Fw)表示,两个不同个体X与Y在D维空间中的欧式距离可按下式计算:

对子群最差蛙Fw按照式(2)和式(3)进行更新(第一次更新时j=1),在F′的适应度值优于Fw的适应度值情况下,用F′代替Fw继续下一次更新,否则下一次更新直接进行,直到j=n的条件满足为止。如果满足结束条件后仍然没有改进,则用Fg代替Fj重复执行式(2),还没有改进时,传统混合蛙跳算法采用随机方法生成一个新蛙取代Fw。

新的更新策略中子群中最差蛙Fw不仅学习种群最优蛙Pg的模因信息,而且学习子群中其它所有个体的模因信息,这样可以有效避免早熟现象发生,从而提高算法收敛速度。此外,由于引入了自适应缩放因子和欧式距离,故而提高了算法的寻优精度。

2.2 随机产生个体改进

传统混合蛙跳算法中,如果Fw经过更新后没有得到改善,则在定义域内采用随机生成方法产生一个新的个体取代原来的Fw。这种随机产生个体的做法不仅增加了算法的盲目性,而且降低了算法的收敛速度。为了克服这个问题,本文提出一种新的产生个体方法:

其中:C表示可调控制参数,其数值在0~1之间变化。在最初迭代时,每个青蛙之间存在较大差异,如果新产生的青蛙个体能够充分学习全局最优蛙Fg的模因信息,那么算法收敛速度必然会提高,故此时C应该取更大的值。随着迭代次数的进行,青蛙个体之间在后期的差异将越来越小。如果C的取值维持不变,则算法很容易陷入局部最优解,为了防止这种现象发生,本文对C定义如下:

其中:t表示当前全局迭代次数,tmax表示最大全局迭代次数,L为大于1的整数。控制参数C随L变化的函数曲线如图3所示,青蛙群体规模和最大全局迭代次数决定了L的取值(本文取L=10)。

由图3不难发现,控制参数C的值在迭代初期非常大,接近于1,因此新产生的个体能够向全局最优蛙学习到充分的模因信息,从而使算法快速向全局最优处收敛;控制参数C的值在迭代后期逐渐减小,从而新产生的个体与全局最优蛙存在很大的差异,提高了种群的多样性,一定程度上避免了算法陷入局部最优。

2.3 改进后的混合蛙跳算法流程

设青蛙种群规模为P,子群数为m,每个子群的个体数为n,最大子群内部搜索次数为I,最大全局信息交换次数为G,本文提出的基于自适应缩放因子和欧式距离的改进混合蛙跳算法(ISFLA)流程如图4所示。

3 仿真实验

3.1 仿真实验

为了验证改进算法性能,将ISFLA与SFLA、文献[5]提出的MSFLA作对比,仿真实验选择了4个测试函数:Sphere函数f1、Rastrigin函数f2、Griewank函数f3、Schaffer函数f4,这4个测试函数的表达式如下:

其中:D代表解的维数,Sphere函数是简单的单峰函数,其余3个函数都是复杂的多峰函数,4个测试函数的理论最优值均为0。算法参数设置为:青蛙初始种群规模P=600,子群数m=30,子群内迭代次数I=10,全局迭代次数G=500。

在MATLAB中,采用3种算法分别对4个测试函数进行实验。为了得到准确结果,针对每个函数独立进行100次实验,取50次最好实验结果的平均最优适应度作为寻优结果。4个测试函数使用3种算法在不同维数下的平均最优适应度如表1所示。

3.2 性能分析

由表1可以看出,对于单峰函数f1,在不同维数下3种算法的表现都很优秀,收敛精度都很高;而对于多峰函数,ISFLA的性能与SFLA和MSFLA相比大不相同,特别是在40维时,ISFLA的寻优能力明显优于SFLA和MSFLA。为了进一步比较3种算法的局部搜索能力,参考文献[8]提出求解成功率概念,即每个算法独立运行相同的次数,如果算法所得最优解在允许误差范围内,则为成功,否则为失败,求解成功率等于所有成功次数与总的实验次数的比值。为此,设定空间维数为40,针对4个测试函数,每个算法单独运行100次,实验结果如表2所示。

由表2可知,对于4个测试函数,在允许误差内,ISF-LA的求解成功率都能达到90%以上。相比于SFLA和MSFLA,ISFLA在求解高维复杂优化问题中体现出更高的可靠性和实用性。

当测试函数维数设定为40时,3种算法在不同测试函数上的平均最优适应度值曲线如图4-图7所示,横坐标代表算法进化代数,纵坐标代表函数独立运行100次的平均最优适应度值的常用对数。

由图5~图8可以看出,ISFLA算法与MSFLA、SF-LA算法相比,ISFLA算法收敛精度明显优于另外两种算法,能以最快的速度收敛到理论最优值附近,具有较好的收敛性,同时避免了早熟现象的发生。显然,对于高维复杂优化问题,改进的混合蛙跳算法性能更佳。

4 结语

本文提出了一种改进的混合蛙跳算法,把自适应缩放因子和欧式距离引入到传统算法的更新策略中,并对传统混合蛙跳算法中的随机更新策略进行了改进,增强了算法的局部搜索能力,提高了算法收敛速度。仿真实验结果表明:改进算法在寻优精度、收敛速度和求解成功率上有明显改善,对高维复杂优化问题表现出更好的性能。

参考文献

[1]EUSUFF M M,LANSEY K.Optimization of water distribution network design using shuffled frog leaping algorithm[J].Journal of Water Resources Planning and Management,2003,129(3):210-225.

[2]RAHIMI-VAHED A,MIRZAEI A H.Solvinga bi-criteria permutationflow-shop problem using shuffled frog-leaping algorithm[J].Soft Computer,2008,39(12):435-452.

[3]EBRAHIMI J,HOSSEINIAN S H,GHAREHPETIAN G B.Unit commitment problem solution using shuffled frog leaping algorithm[J].Power Systems,2011,26(1):573-581.

[4]葛宇,王学平,梁静.自适应混沌变异算法[J].计算机应用研究,2011,28(3):945-947.

[5]ELBELTAGI E,HEGAZY T,GRIERSON D.A modified shuffled frog leaping optimization algorithm:applications to project management[J].Structure and Infrastructure Engineering,2007,3(1):53-60.

[6]赵鹏军,刘三阳.求解复杂函数优化问题的混合蛙跳算法[J].计算机应用研究,2009,26(7):35-37.

[7]葛宇,王学平,梁静.改进的混合蛙跳算法[J].计算机应用,2012,32(1):234-237.

[8]李晶晶,戴月明.自适应混合变异的蛙跳算法[J].计算机工程与应用,2013,49(10):58-61.

缩放算法 第5篇

Scaler是广泛应用于显示系统中的缩放引擎, 缩放 (scaling) 实际上就是改变图像的水平和垂直分辨率, 以使视频内容适合于显示屏分辨率, 得以正常显示。图像缩放的算法很多, 目前Scaler中普遍采用内插算法, 常用的内插算法包括最邻近内插算法 (Nearest neighbor interpolation) 、双线性内插算法 (Bi-linear interpolation) 、双立方内插算法 (Bi-cubic interpolation) 。上述三种算法对于缩放比例较小 (0.5～4.0) 的情况有较好的图像缩放效果。然而, 对于缩放比例较大的情况, 尤其在图像缩小 (downscaling) 比例较大时, 上述内插算法会产生严重的混叠现象, 必须进行优化。

本文在分析三种内插算法的基础上, 提出了基于抗混叠滤波器的内插算法的优化方案, 并将优化后的三种算法做了进一步的实验分析与比较, 得出最为可行的Scaler算法方案。

1 三种内插算法

1.1 最邻近内插算法

最邻近内插算法 (Nearest neighbor interpolation) 的思想很简单, 对于每一个非整数的坐标点, 将与其邻近的4个整数坐标点位置进行比较, 选取距离最近的整数坐标点的像素值作为其像素值。

该算法是最简单也是速度最快的一种算法, 空间代价小, 仅需存储两行图像数据。但是该算法会带来明显的失真, 相邻整数坐标点中点处的像素值会突然出现一个跳跃, 这就是出现马赛克和锯齿等明显走样的原因。故在缩放比例较大情况下无法直接应用。

1.2 双线性内插算法

双线性内插算法 (Bi-linear interpolation) 的描述为:设原始图像的4个像素点坐标分别为 (x, y) , (x+1, y) , (x, y+1) 和 (x+1, y+1) , 缩放后的目标像素点坐标为 (x+dx, y+dy) , 其中x, y均为非负整数, dx, dy分别是目标像素点与原始图像中的邻近点的水平和垂直坐标方向上的两个增量, 即为[0, 1) 区间的浮点数。则目标内插点的像素值表达式为:

f (x+dx, y+dy) = (1-dx) (1-dy)

f (x, y) + (1-dx) dyf (x, y+1) +

dx (1-dy) f (x+1, y) +dxdy

f (x+1, y+1) (1)

其中, f (x, y) 表示原始图像 (x, y) 处的像素值。利用这一公式, 对于每一个非整数的坐标点, 其像素值皆可由与其邻近的4个整数坐标点的像素值计算得到。

该算法为一阶算法, 与最邻近内插算法相比, 空间代价相同 (存储两行图像数据) , 计算量大。 但是, 经该算法缩放后的图像质量高, 不会出现像素值不连续的的情况。另外, 由于双线性内插算法具有低通滤波器的性质, 使高频分量受损, 所以可能会使图像轮廓在一定程度上变得模糊。

1.3 双立方内插算法

双立方内插算法 (Bi-cubic interpolation) 与双线性内插算法类似, 对目标内插点, 扩大到由邻近的16个整像素点的像素值计算得到。一维计算方法为:设缩放后的目标像素点坐标为x+а, 其像素值表达式为:

f (x+а) =u (1+а) f (x-1) +

u (а) f (x) +u (1-а) f (x+1)

u (2-а) f (x+2) (2)

其中, a是目标像素点与原始图像中邻近点的增量, 即为[0, 1) 区间的浮点数;f (x) 表示源图像x处的像素值;u (s) 函数为立方卷积内插核。

根据核函数u (s) 的不同选取, 双立方内插算法会产生不同的低通滤波或高通滤波效果, 其中一种最常用的类型为Keys双立方插值算法, 其u (s) 函数如下:

二维情况下的双立方插值可以先在Y方向上做四次一维双立方插值, 然后再用这些结果在X方向上做一次一维双立方插值。

该算法为三阶算法, 与前两种算法相比, 双立方内插算法采用的像素点更多, 相应的计算复杂度也更高, 且空间代价较大, 需要存储4行图像数据。 但是, 该算法的插值效果明显优于前两种算法, 能够得到相对清晰的画面质量, 而且可根据需要选取不同的内插核, 产生低通滤波或高通滤波效果, 比较灵活。该算法在目前各种Scaler中最为常用。

三种内插算法的比较总结如表1所示。

2 抗混叠优化

2.1 抗混叠优化的必要性

对图像进行缩放, 相当于对图像信号 (数字信号) 进行采样率转换处理, 一个数字信号x (n) 按因子L/M进行采样率转换的一般过程如图1所示。

对一个信号下M采样时, 由于下M采样后的信号频谱是对原信号频谱作M倍拓展形成的, 所以进入插值滤波器的信号undefined (n) 的截止频率undefinedc必须满足条件:

undefinedcM<π 即undefined

才能避免混叠现象。

当图像缩小比例较大 (即降采样因子M较大) 时, 若不进行预滤波, 混叠现象将十分明显, 且随缩小比例的增大而越发严重。即使内插效果最佳的双立方内插算法亦无法满足需求。

2.2 抗混叠滤波器设计

由以上分析可知, 所需的抗混叠滤波器的理想频率响应Hd (ejw) 满足:

且必须满足以下约束条件:

①线性相位, 即hd (n) =hd (-n)

②正则阶, 即∑n (-1) nnkhd (n) =0, k=0, 1, , N-1

根据缩放比例可以确定抗混叠滤波器的截止频率wh, 根据Scaler所应用的系统内存需求可以确定滤波器阶数N, 从而计算得到滤波器系数。

2.3 内插算法的抗混叠优化

当前Scaler多应用于嵌入式系统中, 考虑到嵌入式系统内存资源的稀缺, Scaler算法的优化应存储尽量少的图像数据。以二维内插所需的最小数据行为单位, 先滤波, 再内插。设滤波器的阶数为N (一般N取奇数, N=2n+1) , 基本内插算法需要的数据行数为P (最邻近内插和双线性内插需要2行, 双立方内插需要4行) , 抗混叠优化后的内插算法过程如下:

①确定内插所需的图像数据行, 如图2 (a) 所示的中间1-P行。

②依次滤波该P行数据, 每滤波一行, 需要存储该行邻近的N行原始图像数据, 如图2 (a) 所示上方n行, 下方n行, 以及该行自身。

③得到滤波后的P行数据, 如图2 (b) 所示。

④内插计算得到目标数据, 如图2 (c) 所示。以此类推。

由以上分析可知, 优化后的Scaler内插算法总结如下:

①根据缩放比例和效果要求, 确定合适的抗混叠滤波器 (可预存若干组滤波器系数, 根据不同需求选择) 。

②以基本内插算法所需存储的最小数据行为单位, 先滤波, 再内插。

③算法优化后的Scaler需要存储N+P行图像数据。

3 仿真实验

3.1 抗混叠效果客观比较

实验采用原始大小为30002000的测试图像glassman.bmp, 分别利用优化前和优化后的内插算法缩小 (downscaling) 至目标图像320240, 再放大至原始图像大小, 比较该优化方案对性能的影响。

在客观比较中, 采用以下三个指标对图像质量进行衡量:

①MSE (mean square error, 均方误差) 。

②PSNR (peak signal to noise ratio, 峰值信噪比) 。

③SNR (signal to noise ratio, 信噪比) 。

设f (x, y) 为原始图像在坐标 (x-y) 的像素值, h (x, y) 为重建图像在坐标 (x, y) 的像素值, MN是图像大小。上述三个指标的计算公式如下:

undefined

优化前后的性能比较结果如表3, 表4所示。可以看出, 将本文设计的抗混叠优化方案应用于三种内插算法后, 图像缩放性能均有提高。

3.2 抗混叠效果主观比较

主观比较即将同一幅测试图像分别进行相同倍数的缩小或放大, 然后比较缩放后目标图像的视觉效果。原始测试图像glassman.bmp (大小为30002000) , 如图3所示, 分别利用优化前和优化后的内插算法进行缩小 (downscaling) , 得到的目标图像 (大小为320240) , 缩放比例接近0.1, 如图4所示。

其中, 图4 (a) 组是采用最邻近内插算法, 图4 (b) 组是采用最双线性内插算法, 图4 (c) 组是采用双立方内插算法。可以看到, 将本文设计的抗混叠优化方案应用于三种内插算法后, 图像缩放效果均有提高。其中, 双线性内插算法和双立法内插算法经优化后, 已基本符合视觉欣赏要求, 而最邻近内插算法经优化后, 在缩放比例较大 (10倍以上) 的情况下, 图像质量仍然不高。

3.3 加入抗混叠优化的代价考虑

加入抗混叠优化后, 有以下两方面的代价值得考虑。

首先是计算复杂度, 结合了抗混叠滤波的内插算法, 与原先基本内插算法相比, 计算复杂度提高, 必然导致运算速度降低和硬件实现的面积增大。

其次是存储代价, 从2.3节的分析中可知, 算法优化后的Scaler需要存储N+P行图像数据。假设抗混叠滤波器为5阶 (N=5) , 那么对大小为30002000的测试图像进行处理, 最邻近内插算法和双线性内插算法皆需要存储7行, 即 (5+2) 3k=21k bytes, 比优化前增加15k bytes;双立方内插算法需要存储9行, 即 (5+4) 3k=27k bytes, 亦比优化前增加15k bytes。

4 结束语

通过实验结果可以看出, 本文设计的内插算法的抗混叠优化方案对图像缩放效果有一定提升。结合考虑该优化方案的代价, 可以进一步得出结论:最邻近内插算法优化后缩放比例仍有一定限制, 图像质量不佳;而双线性内插算法和双立方内插算法优化后的效果近似, 均可满足视觉要求, 考虑到双立方内插算法的计算复杂度较高, 所耗内存较大, 故采用优化后的双线性内插算法是较为可行的Scaler算法方案。

摘要：对Scaler中常用的三种图像缩放内插算法 (最邻近内插, 双线性内插和双立方内插) 进行了比较研究, 提出了基于抗混叠滤波器的内插算法的优化方案。针对缩放比例较大情况下出现的严重混叠现象, 该方案可以起到抗混叠作用。实验表明了方案的有效性, 并进一步表明优化后的双线性内插算法更具可行性。

关键词：Scaler,最邻近内插算法,双线性内插算法,双立方内插算法,抗混叠

参考文献

[1]Kian Kee Teoh, Ibrahim H, Bejo S K.Investigation on several basic in-terpolation methods for the use in remote sensing application[J].IEEE, 12-13 July 2008:60-65.

[2]Dumic E, Grgic S, Grgic M.Hidden influences on image quality whencomparing interpolation methods[J].IEEE, 25-28 June 2008:367-372.

[3]Qi Li, Sato I, Murakami Y.Interpolation Effects on Accuracy of MutualInformation Based Image Registration[J].IEEE, July 31 Aug.4 2006:180-183.

[4]肖建平, 邹雪城, 刘政林, 等.基于LCD定标器的文本型图像缩放算法研究[J].华中科技大学学报:自然科学版, 2006, 33 (5) :46-48.

[5]郑啸, 兰家隆.图像放大中的两种FIR内插滤波器实现结构及其抗混叠效果比较[J].国外电子元器件, 2006, 12:29-31.

缩放算法 第6篇

随着多媒体与网络技术的迅速发展,在数字音像文化市场中,盗版现象愈演愈烈。于是版权保护成为一个重要的研究方向,近几年来数字水印已成为解决这一问题的有效方法。通过在原始数据中嵌入水印来证明多媒体作品的所有权。

目前已经提出了许多的数字水印的方法[1,2],而现有的数字水印技术大多难以抵抗几何变换类攻击,如旋转,平移和尺度变换等,其中一个最主要的原因是:几何变换虽然并未去除图象中的水印信息,但却使水印的检测与嵌入之间失去同步,从而导致水印检测的失效。因此除非在检测水印之前能使受到几何攻击的水印图像恢复到与原始图像具有同样大小和位置,也就是恢复已失去的同步信息。所以同步问题被认为是抗几何攻击水印技术中需要解决的关键技术。频域里抗几何攻击的水印算法主要有O’Ruanaidh等人[3]提出的基于Fourier- Mellin变换的算法,基于Radon变换的抗几何攻击算法[4], 而这些方法或多或少对图像的空域信息和频域信息做了一定的修改,这样造成原始图像的质量急剧下降。而零水印很好的解决了这一问题,它不需要修改原始图像的任何信息,主要是利用图像的重要特征来构造水印信息,这样使其鲁棒性和安全得到加强。文献[5]首先提出了零水印的概念,该算法利用了高阶累积量提取图像的特征来构造零水印,通过实验来证明这种方法的零水印有很好的性能。但它只能抵抗加噪,滤波,JPEG压缩,剪切非几何攻击,对于旋转的几何攻击鲁棒性较差,而本文的算法在DCT域零水印的基础之上做了一定的改进可以有效的抵抗旋转,缩放造成的几何攻击,同时对于加噪,滤波,JPEG压缩,剪切攻击也具有有很好的鲁棒性。

1 数字图像的分块DCT变换和图像置乱

1.1 数字图像的88分块DCT变换

设数字图像为f(x,y),其中0iN-1,0jN-1,fm(i,j)为f(x,y)的一个88块,0i7,0j7,m=0,1,,(N2/64)-1,则fm(i,j)的DCT变换定义如下:

$F(u,v)=\frac{1}{4}C(u)C(v){\displaystyle \sum _{i=0}^7{\displaystyle \sum _{j=0}^{7}f}}{}_m(i,j)\cos [\frac{(2i+1)u\pi }{16}]\cos [\frac{(2j+1)v\pi }{16}]$

相应的逆变换为:

$f{}_m(i,j)=\frac{1}{4}C(u)C(v){\displaystyle \sum _{i=0}^7{\displaystyle \sum _{j=0}^{7}F}}(u,v)\cos [\frac{(2i+1)u\pi }{16}]\cos [\frac{(2j+1)v\pi }{16}]$

其中:

$C(u)=C(v)=\{\begin{array}{c}1,\text{其}\text{他}\hfill \\ \frac{1}{\sqrt{2}}‚\text{u}=v=0\hfill \end{array}$

fm(i,j)为数字图像的m块的第(i,j)像素的灰度值。即F(u,v)即为相应DCT系数,其中F(0,0)为直流系数,其他为交流系数。二维离散余弦变换具有可分离性,可分为一维行变换和列变换[6,7]。

1.2 仿射变换置乱

在水印嵌入之前,为了增强水印图像安全性,要对嵌入水印的图像进行置乱。常见的置乱变换有Arnold变换(又称猫脸变换),排列变换,Fibonacci变换,这些置乱图像后的直观效果各不相同,但其计算复杂度是基本一致的,因为它们均存在取模运算,使得在作置乱时较费时间,而且除了Arnold变换的逆变换易求外,其余变换的逆变换不易求出。基于以上考虑本文对水印图像的置乱变换采用仿射变换。

仿射变换的一般形式:

$\{\begin{array}{c}x{}^{\text{'}}=ax+by+e\hfill \\ y{}^{\text{'}}=cx+dy+f\hfill \end{array}\Delta =|\begin{array}{c}a\hfill \\ c\hfill \end{array}\begin{array}{c}b\hfill \\ d\hfill \end{array}|\ne 0(1)$

其矩阵形式为

其中,为原始坐标,为变换后的坐标。a,b,c,d,e,f分别为变换的参数系数。该变换通过像素点的位置的置换来置乱图像。当遍历完所有的原始图像像素点之后,便进行了一次完整的仿射变换置乱。

本算法采用的仿射变换正变换:

当x<y时:

当x≥y时:

其逆变换为:

当x'+y'N+1时:

当x'+y'>N+1时:

用上述方法对128128,256级灰度的baboon水印图像进行置乱的效果如图1所示。

(n为水印图像置乱时迭代的次数,可以作为水印置乱的密钥)

2 尺度变换与旋转不变的实现

令f(x,y)表示笛卡儿坐标系(x,y)上的原图象,沿顺时针方向旋转φ角度,缩放σ-1倍

fsr(x,y)=f(σ-1(xcosφ+ysinφ),σ-1(ycosφ-xsinφ)) (7)

对数极坐标映射(LPM):

令 x=eρcosθ,y=eρsinθ 0θ<2πρ∈R2 (8)

将(2)式代入(1)式:

fsr(eρcosθ,eρsinθ)=f(eρ-lnσ[(cosθcosφ+sinθsinφ),(sinθcosφ-eρcosθsinφ)])=f(eρ-lnσcos(θ-φ),eρsin(θ-φ)) (9)

(3)式可以简写为

Ir(ρ,θ)=I(ρ-lnσ,θ-φ) (10)

ρ,θ分别为极轴,极角的采样个数。

从(4)式可以看出原图象在笛卡儿坐标系旋转φ 个角度,图像会在LPM系里沿着极角θ方向平移φ个单位。

对于缩放攻击的分析:

一般参考文献中缩放尺度的为[0.5-2](缩放倍数)范围内,缩放过大或过小都会使得图像失去本身利用的价值。而在此范围内经过LPM后缩放几乎对原始图像不会产生太大影响,例如:图像缩小0.5倍,相当于在LPM下图像沿着坐标轴平移ln0.5=-0.6931个单位,图像放大2倍,相当于在LPM下图像沿着坐标轴平移ln2=0.6931个单位,图像放大1.5倍,相当于在LPM下图像沿着坐标轴平移ln1.5=0.4055个单位,所以由以上可知这些缩放如果转换成平移问题,它们均未达到平移一个像素单位,因此近似认为它们没有发生平移,这样在以后的水印检测中方便处理。

对于循环平移后的图象,在水印检测时我们可以使用遍历搜索的方法来检测载体图像是否包含水印信息,通过以上的算法实现旋转,缩放不变性的目的。

3 水印嵌入和检测原理框图

(1)水印嵌入原理框图,见图2所示。

(2)水印检测原理框图,见图3所示。

(N=1,2,3,4ρ。 ρ为极角的采样个数,S为相似度,T为阈值门限)

4 嵌入水印算法和水印提取过程

4.1 嵌入水印算法和加密算法

下面以256256的256级灰度Lena图像作为载体图像,6464的baboon图像作为水印图像来说明水印的嵌入过程。步骤如下:

(1)考虑到一般图像在受到旋转几何攻击之后图像大小会发生改变,这样使得水印的嵌入和检测失去同步,我们通过加黑背景使得256256的256级灰度Lena图像大小为384384,目的是保持载体图像在受到旋转几何攻击之后的基本信息不受损失。从而实现水印嵌入和检测之间同步。

(2)对大小为384384的Lena图像进行对数极坐标转换(LPM),极轴和极角的采样个数都为512,即LPM以后的图象大小为512512。(如图(5)所示)

(3)对LPM以后的512512图像进行DCT变换,将其分成互不覆盖的88块,记为$f{}_m(x,y),x=0,1,2\cdots ,7,y=0,1,2\cdots 7,m=0,1,\cdots ,\frac{{\rm N}{\rm N}}{88}-1$,对每一块进行DCT变换,结果为Fm(u,v),u=0,1,2,7,v=0,1,2,7。

(4)提取各个子块的直流分量重新排列成一幅矩阵记为M。

(5)对大小为6464的baboon图像利用置乱密钥进行置乱,得到置乱后的图像W。

(6)将直流分量M和置乱后的图像W的灰度值取整(matlab下使用round函数)后化为二进制数。

(7)直流分量M的二进制灰度值记为Mx,y, 置乱后的图像W的二进制灰度值记为Wx,y,Mx,y 表示在的灰度值,Wx,y表示在的灰度值。

(8)水印嵌入公式: M'x,y=Mx,yΛWx,y,Λ为异或运算符号。M'x,y为得到的密钥图像的二进制灰度值。

(9)对每个M'x,y灰度值进行二进制循环移位得到加密后的图像M${}_{x,y}^{\text{'}\text{'}}$。每个M'x,y灰度值进行二进制循环移位的次数可以通过查循环移位密码表获得。循环移位的计算方法:N=2(R-1)+3(C-1),R表示灰度值矩阵行数,C表示列数,N表示移位的次数。

4.2 水印提取过程

步骤如下:

(1):对测试图像进行对数极坐标转换和DCT88分块,这一步同嵌入水印算法和加密算法中的步骤(2),(3),(4),(6),(7)得到Mx,y。

(2):对照循环右移次数密码表对加密后的图像每个M${}_{x,y}^{\text{'}\text{'}}$进行循环左移(解密的过程)得到M'x,y。

(3):Wx,y=Mx,yΛM'x,y,Λ为异或运算符号,Wx,y为置乱后的图像。

(4):利用置乱密钥对Wx,y进行图像重构得到重构的水印图像W。

(5):将重构的水印图象和原始水印图象做相似度的计算。若相似度高于阈值门限,则判定水印存在,若低于门限则进行搜索遍历。

(6):循环搜索遍历:将对数极坐标转换后的图象沿着极角的方向平移i个单位(i=1,2,3ρ),继续进行(1)(5)步骤的操作。如果i>ρ,判定水印不存在

5 实验仿真过程

在实验仿真的过程中,我们选取的图像都是256级的灰度图像,其中水印图像为256256的baboon图像,原始载体图像为384384的Lena图像。对于图像的视觉质量的定量描述,我们使用常用的基于像素的差分失真度量方法PSNR.。

${\rm M}SE=\frac{1}{{\rm M}{\rm N}}{\displaystyle \sum _{x,y}(}{\rm I}(x,y)-{\rm I}{}^{\text{'}}(x,y)){}^2(11)$

PSNR=10lg(2552/MSN) (12)

MSE表示两幅图像之间的均方误差。I(x,y)和I'(x,y)分别表示在(x,y)处的灰度值。

sim=$\frac{{\displaystyle \sum _{x,y}{\rm I}}{}^2(x,y)}{{\displaystyle \sum _{x,y}{\rm I}}(x,y){\rm I}{}^{\text{'}}(x,y)}(13)$

sim 表示两幅图像之间的相似度。为了验证算法的有效性,本文进行了以下实验,实验1是在正常情况下,在原始Lena载体图像嵌入水印图像baboon,结果见图4;实验2是对图像Lena进行各种角度的旋转和缩放后进行水印检测,结果见表2;实验3是对图像Lena进行加噪、滤噪后、剪切后进行水印检测,实验结果见表3;实验4是对Lena图像进行JPEG压缩,然后进行水印检测,实验结果见表4;为了验证本文算法的可靠性,对于其他没有嵌入水印图像是否会出现误判的情况,实验5以其他不同的载体图像作虚警率验证实验。载体图像分别选取pepper ,plane 和baboon三幅图像,实验结果见图5。由实验结果可以看出,本文算法对图像的旋转、缩放、加噪、滤噪、JPEG压缩、剪切具有很强的鲁棒性,通过虚警率实验可以看出本文算法具有很好的检测精度。

(sim=1)

6 结束语

本文提出了一种基于分块DCT变换的抗旋转,缩放攻击零水印算法,通过对该算法进行的一系列仿真实验,发现该算法对各种不同角度的旋转,缩放攻击有很强的鲁棒性,同时我们也做了加噪,滤波,JPEG压缩,剪切,虚警率分析实验,发现该算法也具有较强的鲁棒性,对于没有嵌入水印的图像错误检测的概率很小。而且该算法还可以推广到其他数字图象信息的隐藏中,并非仅局限于水印。

摘要：大多数基于DCT变换域的零水印算法没有抵抗几何攻击的能力,例如将图像旋转微小角度即可导致水印检测的失败。为了提高基于DCT变换域的零水印算法抵抗图像抗旋转,缩放攻击的能力,本文提出了一种基于分块DCT变换的抗旋转,缩放攻击零水印算法。对于旋转,缩放造成的几何攻击,我们可以通过对数极坐标系将笛卡尔坐标系中的旋转,缩放变换转换为循环平移的性质,对于循环平移后的图像,在水印检测时我们可以使用穷举遍历的方法来检测测试图像是否包含水印信息。实验结果证明,该方法可以获得良好的图象视觉效果,同时对于加噪,滤波,JPEG压缩,剪切攻击也具有有很好的鲁棒性。

关键词：零水印,对数极坐标,鲁棒性

参考文献

[1]潘蓉,高有行.基于小波变换的图像水印嵌入方法[J].中国图像图形学报,2002,7(7):667-671

[2]Lin C Y,Wu M,Bloom J A,et al.Rotation,Scale,and Translation resilient watermarking for images.IEEE Transactions on Im-age Processing,2001,10(5):765-782

[3]J.J.K.O'Ruanaidh,T.Pun,Rotation,scale and translation invariant spread spectrum digital image watermarking.Signal Pro-cessing,1998,66(3):303-317

[4]Cai Lian,Du Si dan,Gao Dun tang,Geometrically invariant watermarking based on Radon transformation,Journal of electronics(china),2005,22(5):300-306

[5]温泉,孙锬锋,王树勋.零水印的概念与应用[J].电子学报.2003,31(2):214-216

[6]D.Yu,F.Sattar,K.K.Ma,Watermark detection and extraction using independent component analysismethod,EURASIP Journal on Applied Signal Processing,2002,1(4):92-104

[7]D.Zheng,J.Zhao,and A.El Saddik,RSTinvariant digital image watermarking based on log-polar mappingand phase correla-tion,IEEE Transaction on Circuits and System for Video Technology,Special Issue on Authentication,Copyright Protection and Information Hiding,2003,13(8):753-765

[8]俞龙江,牛夏牧,孙圣和.一种旋转尺度变换和平移鲁棒水印算法.电子学报,2003,31(12):2071-2073

[9]柏森,曹长修,柏林.基于仿射变换的数字图像置乱技术,计算机工程与应用2002,2(10):74-78

[10]马建糊,何甲兴.基于小波变换的零水印算法[J].中国图像图形学报,2007,12(4):582-585

缩放算法 第7篇

从频率的角度, 音频可以被看作是由不断改变的正弦波组成的离散信号。音乐信号可以看成一个短期 (一般为10~30毫秒) 的平滑信号。它在一段时间内的相对稳定和简单的。同时这种语音在主观上是单调的声音。由于音乐的这种稳定特性, 短时傅立叶变换 (STFT) [2]被广泛使用。这种信号通常被称为一段时期内的一帧。该信号采用窗口移动方法, 可以拦截所有的时间帧。

2. 时间/频率改变算法

改变音频的音调, 就是改变包含了音频波的频率。音调转换算法正是基于这一思想的。双波频, 它在理论上将增加音调音乐的G-8度。然而, 纯间距在频域的改变, 使每个阶段的不一致。并且它会产生回声效果。此外, 在理论上, 因为有限的窗口长度, 频率不能被严格区分开来, 即频谱走样。这个理由使我们不能在波谱中准确地分析波的组成。频率泄漏和频谱走样是一个问题的两个报表。本文不区分上述两种报表。

短时傅里叶变换 (SFFT) 分析综合法是一个有效解决相位不连续的解决方案。这种方法利用了窗口增量, 傅里叶变换, 频率/相匹配, 综合了窗口和堆放的过程[3]。有效地消除了回音效果, 这被称为相合成。

2.1 改进相合成算法

传统的相位模型包括四个过程。有窗口信号傅立叶变换, 频率和相位相匹配, 综合窗口和输出叠加[4]。在本文中, 我们使用海明窗作为一个离散傅立叶变换操作。之后比较不同的音频样本。发现效果优于布莱克曼窗。实验还表明, 海明窗在抑制频率泄漏有较好的效果。序列在窗函数后需要重建, 以恢复其原有的能源。Blackman窗和海明窗, 重建的过程中可以使用相同的窗函数。通过使用综合叠加的方法, 它可以恢复时域信号。

布莱克曼窗

海明窗

通过比较, 海明窗将信号频率限制在一个的接近100赫兹的很窄的区域。信号采用海明窗口呈现出更窄的主要豆、能量集中和更准确的频率等特征, 这将提高性能变调过程功能。布莱克曼窗显然在能量泄漏方面有更广泛的主豆。同时, 应该指出采用海明窗的信号在实验中有更多的旁瓣, 这在一定程度上抵消了狭窄主豆的浓度效应。通常, 在频率泄漏的约束方面海明窗优于布莱克曼窗。

2.2 时域窗口及其复位

海明窗离散傅里叶变换

以下方程是窗重建序列.这里f (n) 代表重建窗

2.3 恢复音高改变能量

音高变换处理后, 时域窗口的范围也发生了变化。为了准确地回复能量, 公式 (5) 修改了重建窗口。

这里hp音调变系数。p是尺度因子窗口.如果用wm来代替hp, 然后, 它可以产生海明重建窗口的系数。fp可以通过比率乘以f来构造.这和重建一个重建系数一样。

在实际处理中, 由于序列的状态可能会被正在处理的改变, 综合窗口和堆的处理不能保证恢复所有的能量。但在特定情况下[5], 这个过程可以恢复大部分的能量。实验结果表明, 海明窗口比起布莱克曼窗在抑制频率泄漏上更好。在改进算法中, 我们使用海明窗口作为分析和综合处理的卷积窗。

2.4 分析/合成处理

我们可以使用一个FIFO队列接收音频输入序列。输入队列的长度相当于窗口的长度。输入队列处理在分析每段时间后促进R样品。为了抑制频谱走样, 它需要窗处理输入队列的顺序。窗口顺序在被处理后将被改变成一个新的序列~xw (n) 。并且新的序列在再次窗计算以恢复原来的信号能量后, 将被堆积起来到最后一次移位输出缓冲区。重建的信号是~x (n) 。相声码器[6]算法使用常数4作为重建系数。信号能量在音调改变前后之间不同。使用一个定值不会有一个好的匹配性。改进后的算法引入一个音调因子作为校正因子。它在听感纠正了改变的能量。

2.5 采用快速傅里叶变换进行音频处理

在音频处理中傅立叶变换是最常见的转化形式。傅里叶变换将信号从时域转换到频域, , 而傅里叶逆变换则将信号从频域转换到时域。在用计算机处理音频时, 是无法衡量和计算无限长的信号。正确的方法在傅里叶变换之前是剪取一段时间帧然后运用定期延续的方法去获得一个虚拟的有限信号。截断的信号通过混叠效应传播其能量, 这也叫做频率泄漏。在最小化频率泄露方面用海明窗作为傅里叶变换作为操作元比布莱克曼窗具有更好的性能。在这个过程中, 数字音频是模拟信号的离散抽样结果。所以我们一般所说傅里叶变换是指离散傅里叶变换 (DFT) .并且其逆方程如下: (7) 傅里叶变换. (8) 逆傅里叶变换.

2.6 频率/相匹配处理

这是改变音调的核心。傅立叶变换后的序列被称为复序列。映射到复平面成为直角坐标。音调变换基于频率改变和相位调制, 复杂的序列被表示为模/相极坐标是很有必要的[7]。

变换的目的是为了推算光谱成分的两个样品分析序列相的差。这两个样本是差异R样本。音调变系数乘以相位差产生一个新的相。用这个新相位重组频率复序列[8]。并映射这个新序列到全面频谱缓冲区。

2.7 主观特征和M窗口长度以及跳过样品数R三者之间的关系

M值越大, 窗口覆盖的范围越大。并且光谱分析的转换错误越小[9]。实验表明, 人类的耳朵对高音调音乐中的频率错误是很敏感的。一个大窗口可以增加频谱分析的准确性。在44.1 KHz的音频中, 当M>2048将音高参数调到在1到2之间可以获得一个较好的效果。当音高系数等于1的时候音频音乐保存原来的音高未改变。

2.8 频率调制算法的推广

音频音高变化和时间伸缩 (音高不变) 可视为一个问题[10]。一段双采样的音频, 当播放音频音高将提高八度, 反之亦然。要确保时间改变而音高没有改变, 或音高改变而时间没有改变, 都必须修改原始音频[11]。一个简单的例子是, 播放已提高八度的音乐采用用一半的采样率速度。音高和原来一样, 但时间需要两倍。当改变音频的音高时, 采用相结合算法然后线性插值或采样, 可以得到同样的音高。但是, 用新时间范围除以原音频频率可以得到的音频等于原音高变化因子。实验表明, 通过相合成它也能达到令人满意的结果[12]。

3. 总结

2倍波的低频率部分在相位声码器[4]音高转换算法会被丢失。改进后的算法体现了原波的低频和组成一个新的波形, 该波形是原本的两倍。将音乐分为背景声和语音。对于音调上升, 如果用频率调制方法将乐器混响直接加到背景音乐则会产生回音效果。对人类的声音可以显然地听到声音的重复;对于音调下降, 当用频率调制到两帧之间的连接处时, 它会产生的噪音。有效地解决这两个问题的方法是相组成音调变换算法。声音的平滑通过相位声码器可以被减低[4]。改进算法保持了在主观音乐改变前后之间音乐的响度一致。语音的质量明显地提高了。