《图像缩放的双线性插值原理及DSP下的优化(常用版).doc》由会员分享，可在线阅读，更多相关《图像缩放的双线性插值原理及DSP下的优化(常用版).doc（62页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、图像缩放的双线性插值原理及DSP下的优化（常用版）(可以直接使用，可编辑 完整版资料，欢迎下载）图像缩放的双线性插值原理及DSP下的优化目录图目录31案例描述21.1图像缩放模块处理函数的实现方式21.2双线性缩放原理41.3DSP上的双线性缩放的实现8通用双线性的实现8快速双线性的实现102案例分析123解决过程124解决结果125总结12 图目录图表 1 基本的任意位置缩放效果图2图表 2 帧格式目的图像的缩放效果图2图表 3 场格式的目的图像缩放效果图3图表 4 原始图片7图表 5 最临近插值放大的效果图7图表 6双线型内插值放大图片7 关键词：双线性插值 dm6446 内联指令 YUV
2、格式摘 要：本文描述了双线性插值的基本原理，同时介绍了其在YUV格式图像缩放中的应用及优化。1 案例描述1.1 图像缩放模块处理函数的实现方式422缩放、420的缩放以及两者之间相互缩放，在Resizer模块中都是采用双线性原理实现的，唯一不同的就是根据图像的格式不同，取数据和拼数据的方式稍有不同，另外在实现缩放的同时也加入了根据用户输入的信息在目的图像周围加上任意颜色的边框的功能。图像缩放原理示意图如下：图表 1 基本的任意位置缩放效果图下面是目的图像为帧格式时加边框之后的效果：图表 2 帧格式目的图像的缩放效果图下面是目的图像为场格式时加边框之后的效果：图表 3 场格式的目的图像缩放效果图
3、为了提高效率，将相同尺寸的图像直接进行拷贝，所以每种类型的转换都存在拷贝和缩放两类函数。对于源是420的图像，由于Y、U、V分量数据是分段连续的，为了提高效率，对于两倍以内的缩小及各种尺寸的放大还提供了优化快速算法，快速算法效率为通用算法效率的3/5。另外，由于本模块的所有算法中，都参考了Stride参数，这样每个模块只需要重点实现帧到帧的拷贝和缩放函数即可，其他类型的转换分别可以通过调用这两个函数即可实现。例如：场到场的转换可以通过调用两次帧到帧即可实现；场到帧，可以也是通过调用两次帧到帧实现，这时只需要在每次调用的时候，将目的图像的Stride改为原来的两倍即可，这时第一场就会放在目的图像
4、的奇数行，第二场图像就会放在目的图像的偶数行；帧到场的转换也类似，将源图像的Stride改为原来的两倍，这样就可以通过，先将源图像的奇数行图像缩放到目的图像的第一场，然后将源图像的偶数行数据放在目的图像的第二场，调用两次帧到帧的缩放即可实现。1.2 双线性缩放原理图像的缩放很好理解,就是图像的放大和缩小。传统的绘画工具中,有一种叫做“放大尺”的绘画工具，画家常用它来放大图画。当然，在计算机上，我们不再需要用放大尺去放大或缩小图像了，把这个工作交给程序来完成就可以了。下面就来讲讲计算机怎么来放大缩小图象；在本文中，我们所说的图像都是指点阵图，也就是用一个像素矩阵来描述图像的方法，对于另一种图像：
5、用函数来描述图像的矢量图，不在本文讨论之列。越是简单的模型越适合用来举例子，我们就举个简单的图像：3X3 的256级灰度图，也就是高为3个象素，宽也是3个象素的图像，每个象素的取值可以是 0255，代表该像素的亮度，255代表最亮，也就是白色，0代表最暗，即黑色 。假如图像的象素矩阵如下图所示（这个原始图把它叫做源图，Source）：234 382267 44 1289 65 63这个矩阵中，元素坐标(x,y)是这样确定的，x从左到右，从0开始，y从上到下，也是从零开始，这是图象处理中最常用的坐标系，就是这样一个坐标： -X|Y如果想把这副图放大为 4X4大小的图像，那么该怎么做呢？那么第一步
6、肯定想到的是先把4X4的矩阵先画出来再说，好了矩阵画出来了，如下所示，当然，矩阵的每个像素都是未知数，等待着我们去填充（这个将要被填充的图的叫做目标图,Destination）：? ? ? ? ? ? ? ? ? ? ? ? ?然后要往这个空的矩阵里面填值了，要填的值从哪里来呢？是从源图中来。好，先填写目标图最左上角的象素，坐标为（0，0），那么该坐标对应源图中的坐标可以由如下公式得出：srcX=dstX* (srcWidth/dstWidth) , srcY = dstY * (srcHeight/dstHeight)好了，套用公式，就可以找到对应的原图的坐标了(0*(3/4),0*(3/4
7、)=(0*0.75,0*0.75)=(0,0),找到了源图的对应坐标,就可以把源图中坐标为(0,0)处的234象素值填进去目标图的(0,0)这个位置了。接下来,如法炮制,寻找目标图中坐标为(1,0)的象素对应源图中的坐标,套用公式:(1*0.75,0*0.75)=(0.75,0)结果发现,得到的坐标里面竟然有小数,这可怎么办?计算机里的图像可是数字图像,象素就是最小单位了,象素的坐标都是整数,从来没有小数坐标。这时候采用的一种策略就是采用四舍五入的方法（也可以采用直接舍掉小数位的方法），把非整数坐标转换成整数，好，那么按照四舍五入的方法就得到坐标（1，0），完整的运算过程就是这样的：(1*0.
8、75,0*0.75)=(0.75,0)=(1,0)那么就可以再填一个象素到目标矩阵中了，同样是把源图中坐标为(1,0)处的像素值38填入目标图中的坐标。依次填完每个象素，一幅放大后的图像就诞生了，像素矩阵如下所示：234 38 22 22 67 44 12 12 89 65 63 63 89 65 63 63 这种放大图像的方法叫做最临近插值算法，这是一种最基本、最简单的图像缩放算法，效果也是最不好的，放大后的图像有很严重的马赛克，缩小后的图像有很严重的失真；效果不好的根源就是其简单的最临近插值方法引入了严重的图像失真，比如，当由目标图的坐标反推得到的源图的坐标是一个浮点数的时候，采用了四舍五
9、入的方法，直接采用了和这个浮点数最接近的象素的值，这种方法是很不科学的，当推得坐标值为 0.75的时候，不应该就简单的取为1，既然是0.75，比1要小0.25 ，比0要大0.75 ,那么目标象素值其实应该根据这个源图中虚拟的点四周的四个真实的点来按照一定的规律计算出来的，这样才能达到更好的缩放效果。双线型内插值算法就是一种比较好的图像缩放算法，它充分的利用了源图中虚拟点四周的四个真实存在的像素值来共同决定目标图中的一个像素值，因此缩放效果比简单的最邻近插值要好很多。双线性内插值算法描述如下:对于一个目的像素，设置坐标通过反向变换得到的浮点坐标为(i+u,j+v) (其中i、j均为浮点坐标的整数
10、部分，u、v为浮点坐标的小数部分，是取值0,1)区间的浮点数)，则这个像素得值 f(i+u,j+v) 可由原图像中坐标为 (i,j)、(i+1,j)、(i,j+1)、(i+1,j+1)所对应的周围四个像素的值决定，即：f(i+u,j+v) = (1-u)(1-v)f(i,j) + (1-u)vf(i,j+1) + u(1-v)f(i+1,j) + uvf(i+1,j+1) 公式1其中f(i,j)表示源图像(i,j)处的的像素值，以此类推。比如，象刚才的例子，现在假如目标图的象素坐标为（1，1），那么反推得到的对应于源图的坐标是（0.75 , 0.75）, 这其实只是一个概念上的虚拟象素,实际在
11、源图中并不存在这样一个象素,那么目标图的象素（1，1）的取值不能够由这个虚拟象素来决定，而只能由源图的这四个象素共同决定：（0，0）（0，1）（1，0）（1，1），而由于（0.75,0.75）离（1，1）要更近一些，那么（1,1）所起的决定作用更大一些，这从公式1中的系数uv=0.750.75就可以体现出来，而（0.75,0.75）离（0，0）最远，所以（0，0）所起的决定作用就要小一些，公式中系数为(1-u)(1-v)=0.250.25也体现出了这一特点；最邻近插值和双向性内插值缩放图片的效果对比：图表 4 原始图片图表 5 最临近插值放大的效果图图表 6双线型内插值放大图片由上面两幅放大之
12、后的图像效果可见双线性插值相对于临近点复制，图像质量还是有比较明显的改进。1.3 DSP上的双线性缩放的实现1.3.1 通用双线性的实现上面的原理介绍中，实现上是采用浮点数的方式实现的，这种方式并不适合在DSP上实现，为了便于在DSP上实现，在实现中，采用了将浮点数进行定点化的方式实现，目的图像的整数点位置由32位数的高16位表示，小数位置由32位数的低16位实现，这里为了便于优化并保证不溢出，根据人眼区分的尺度大概在1/2个像素左右，这里只取了小数位的高三位，也即精确到0.125位置。具体实现方法如下：每次对于XY的步进值如此计算得到：u32XStride = (l32SrcWidth -
13、1) 16) / (l32DstWidth - 1);u32YStride = (l32SrcHeight - 1) 16;u32WY2 = _extu(u32YPositionTmp, 16, 29);u32WY1 = 8 - u32WY2Tmp;上面的u32Ysrc就是源图像中的整数位置，u32WY1就是第一行数据的权重，u32WY2就是第二行数据的权重，对于X方向的整数位置和权重也是类似的方法得到：u32XPosition += u32XStride; u32Xsrc = u32XPosition 16; u32WX2 = _extu(u32XPosition, 16, 29);u32W
14、X1 = 8 - u32WX2;对于上面的权重采用如下的打包方式： /0 1 2 3u32WY1 = _pack2(u32WY1, u32WY1); /Y1 0 Y1 0u32WY2 = _pack2(u32WY2, u32WY2); /Y2 0 Y2 0u32WY1 = _packl4(u32WY2, u32WY1);/Y1 Y1 Y2 Y2X方向类似：/ 0 1 2 3u32WX1 = _pack2(u32WX2, u32WX1); / X1 0 X2 0u32WX1 = _packl4(u32WX1, u32WX1);/ X1 X2 X1 X2将XY综合打包如下：d64Weight =
15、_mpyu4(u32WX1, u32WY1);/ X1*Y1 0 X2*Y1 0/ X1*Y2 0 X2*Y2 0u32Weight3210 = _packl4(_hi(d64Weight), _lo(d64Weight);/ X1*Y1 X2*Y1 X1*Y2 X2*Y2这样就得到原理中的四个系数，与取得的四个点数据相乘即可得到最终的双线性插值结果：/得到源图目标映射点周围4点u32V10 = _mem4(pu8SrcLine1 + u32Xsrc);u32V32 = _mem4(pu8SrcLine2 + u32Xsrc);u32v3210 = _pack2(u32V32, u32V10)
16、;/权加求目标值u32Res = _dotpu4(u32v3210, u32Weight3210);*pu8Dst+ = (u32Res 6);至此得到目的图像的一点数据，其余类似。对于420格式的图像和422格式的图像，区别主要时在数据排列上不同，因此，主要是打包和组包的方式不同，另外，对于422图像，由于是YUV数据时交叉在一起的，所以，一组循环尽量把YUV数据一起处理，才能保证够高效。1.3.2 快速双线性的实现对于420图像的快速算法，是利用尽量减少数据读取而优化下来的，由于核心循环的瓶颈其实是在数据读写上面，计算单元其实还有很大空余，上面一次读取四点数据，当缩放比例在两倍或者两倍以内
17、的时候，上面一次读取的数据至少可以供两次计算使用，利用这个规律，我们采用数据不动，移动对应系数的方式来减少数据读取，同时利用行权重在一行中不变的特性，一次出两行的两点数据。具体实现方式如下：Y的两行权重的计算方法：u32YPosition += u32YStride;u32WY1 = _extu(u32YPosition, 16, 29);u32WY2 = 8 - u32WY1;u32WeightY1 = _pack2(u32WY1, u32WY2);u32YPosition += u32YStride;u32WY1 = _extu(u32YPositionTmp, 16, 29);u32WY
18、2 = 8 - u32WY1;u32WeightY2 = _pack2(u32WY1, u32WY2);X方向的权重值计算方法如下：u32XPosition += u32XStride;u32WX2 = _extu(u32XPosition, 16, 29);u32WX1 = 8 - u32WX2;u32WeightX1 = (u32WX2 16;u32WX2 = _extu(u32XPosition, 16, 29);u32WX1 = 8 - u32WX2;u32WeightX2 = (u32WX2 8) | u32WX1;/对应到源图(或者权值)的步进(对于12倍的缩放,该值为1或2)，这
19、里就不用再次取源数据u32XDelta = (u32XSrc2 - u32XSrc)3;u32WeightX2 = u32XDelta;u32VTemp2 = _pack2(_dotpu4(u32SrcLine2Tmp, u32WeightX2), _dotpu4(u32SrcLine1Tmp, u32WeightX2);u32CTemp2 = _pack2(_dotpu4(u32SrcLine4Tmp, u32WeightX2), _dotpu4(u32SrcLine3Tmp, u32WeightX2);与Y方向上的权重进行点乘，即可得到最终的结果数据：*pu8DstLine1+ = _do
20、tprsu2(u32VTemp1, u32WeightY1);*pu8DstLine1+ = _dotprsu2(u32VTemp2, u32WeightY1);*pu8DstLine2+ = _dotprsu2(u32CTemp1, u32WeightY2);*pu8DstLine2+ = _dotprsu2(u32CTemp2, u32WeightY2);至此快速双线性算法完成，由于在核心循环中数据读取减少，结果通过ii值比较发现快速双线性的效率为通用双线性算法的3/5。2 案例分析略3 解决过程略4 解决结果略5 总结1. 双线性缩放可以做到平滑缩放2. 由于双线性缩放只是参考到周围的四
21、点数据，所以对于缩小比例较大的效果不是很理想，需要进行更好的滤波算法来减少锯齿和不连续效应3. 双线性插值是一种思想，除可以用来做420，422YUV格式图像以外的其他格式图像的缩放，如RGB图像的缩放独 创 性 声 明本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其它人已经发表或撰写过的研究成果，也不包含为获得山东理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。研究生签名：时间：年月日关于论文使用授权的说明本人完全了解山东理工大
22、学有关保留、使用学位论文的规定，即：学校有权保留送交论文的复印件和磁盘，允许论文被查阅和借阅；学校可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内容，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。(保密的学位论文在解密后应遵守此协议)研究生签名：导师签名：时间：时间：年年月月日日万方数据山东理工大学硕士学位论文摘 要摘 要精确罚函数方法是求解非线性约束优化问题的一种重要方法。理论上，精确罚函数方法只需求解罚参数取某一有限值的罚问题，就可得到约束优化问题的解，从而避免了当罚参数的值趋于无穷大时产生病态的缺点。精确罚函数又分为不可微精确罚函数和连续可微精确罚函数。通常情况下，简单
23、精确罚函数一定是不可微的，从而会在一些快速算法中阻止局部快速收敛，产生 “ Maratos效应”。连续可微精确罚函数就克服了上述缺点，因此具有更好地性质。增广拉格朗日函数就是这样一种特殊的连续可微精确罚函数。对于一般的非线性约束优化模型，本文将提出一种新的非线性 Lagrange函数 ,讨论该函数在 KKT 点处的性质，并证明在适当条件下，基于该函数的对偶算法产生的迭代点列具有局部收敛性，然后给出与罚参数有关的解的误差估计。这为解决非线性约束优化问题又提供了一种新途径。然后对非光滑罚函数进行二阶可微光滑逼近，并给出原优化问题、相应的非光滑罚函数、光滑罚函数最优值间的误差估计，然后设计基于该光滑
24、罚函数的算法，并证明在适当条件下它具有全局收敛性，最后再利用数值实验来说明算法的有效性。最后对于锥优化问题，运用增广拉格朗日函数这一特殊的精确罚函数，给出一种迭代算法，并证明这种算法具有一种较弱的全局收敛性，即提出一种 -全局最优解，对于每一次迭代 k ，得到相应的 k -全局最优解，该序列都收敛到原问题的 -全局最优解，从而证明算法具有 -全局收敛性。关键词： 非线性约束优化问题，精确罚函数，光滑逼近，增广拉格朗日函数I万方数据山东理工大学硕士学位论文AbstractAbstractThe exact penalty function method is an important metho
25、d for solvingnonlinear constrained optimization problem. In theory, the exact penalty functionmethod only need to solve the penalty problem when the parameter take a finitevalue, then we can get the solution of the constrained optimization problem, thusavoid the shortcomings of morbid when the value
26、 of the penalty parameter tends toinfinity. Exact penalty function is divided into nondifferentiable exact penaltyfunction and continuously differentiable exact penalty function. Under normalcircumstances, the simple exact penalty function must be nondifferentiable, whichwill prevent the local fast
27、convergence of some fast algorithm, and result in the“Maratos effect”. Continuously differentiable exact penalty function overcomesthe above shortcomings, it has better properties. Augmented Lagrangian functionis a special kind of continuously differentiable exact penalty function.First， for a gener
28、al nonlinear constrained optimization model, this paper willpropose a new nonlinear Lagrangian function to discuss the properties of thefunction at the KKT point, and prove that under wild conditions, the iteratedpoints based on the dual algorithm of the function are local convergent, and thengive t
29、he error estimates of the solution about the penalty parameter. This providesa new way for solving nonlinear constrained optimization problem.Then we make a second order differentiable smooth approximation for thenonsmooth penalty function of the above model, and give the error estimates of theoptim
30、al values of the original optimization problem, the corresponding nonsmoothpenalty function and the smooth penalty function, and design the algorithm basedon the smooth penalty function, then prove that under wild conditions, it isglobally convergent, and finally numerical experiments are given to i
31、llustrate theeffectiveness of the algorithm.Finally, for the cone optimization problem, we use the augmented Lagrangianfunction, which is a special exact penalty function, give an iterative algorithm, andprove that the algorithm has a weak global convergence, that is, propose a -global optimal solut
32、ion, then for each iteration k , we get the correspondingII万方数据山东理工大学硕士学位论文Abstract k -global optimal solution, which converge to the -global optimal solution, thusthe -global convergence of the algorithm is proved.Key words: Nonlinear constrained optimization problem, exact penalty function,smooth
33、approximation, augmented Lagrangian functionIII万方数据山东理工大学硕士学位论文目录目 录摘 要 .IAbstract. II第一章绪 论. 11.1 精确罚函数方法的研究意义 . 11.2 精确罚函数方法的研究现状及其发展 . 11.3 本文的研究内容和主要工作 . 3第二章预备知识. 42.1 问题的引入 . 42.2 符号说明及定义 . 5第三章一类非线性Lagrange函数. 83.1 函数定义及对偶算法 . 83.2 主要结论 . 8 非线性 Lagrange函数 G( x, u, ) 的性质 . 8 基于非线性Lagrange 函数 G( x, u, ) 的对偶算法的收敛性 . 9第四章光滑逼近低阶精确罚函数. 154.1 低阶精确罚函数的二阶可微光滑逼近 . 154.2 算法 . 184.3 数值实验 . 19第五章一类具有全局收敛性的增广Lagrangian方法及其算法 . 225.1 算法 . 225.2 -全局收敛性. 23第六章总结与展望. 266.1 总结 . 266.2 展望 . 26致谢 . 27参考文献 . 28攻读硕士学位期间发表的论文 .