当今主流数字图像缩放技术的算法.doc

当今主流数字图像缩放技术的算法转自：第四章当今主流数字图像缩放技术的算法4.1基于近临插值与邻域取平均的图像缩小算法4.1.1问题引入传统的图像缩放算法中，有的有的失真较小但是算法复杂，如双三次插值；有的运算量小但得到的图像失真较大，如最近邻插值和双线性插值。在对图像进行缩小的时候存在着图像信息的损失，而且缩小的比例越大，损失越大，从而导致图像的失真较大，最主要的是在对图像进行缩小的时候显然会出现原图像的多个像素对应同一个像素点从而会产生像素跃越现象。如何合适的选取目的图像的像素值是图像缩小的最关键的问题。我们可以通过反向变换法来实现。反向变换法从目的图像出发，对于一个目的像素，通过缩放变换的逆变换，找到这个目的像素的原坐标点。但是，存在这样一个问题，即将目的像素的整数坐标通过反向变换后将得到浮点坐标。通常对于一个浮点坐标，其对应的点的周围将有最邻近的四个或八个像素。取哪一个像点的像素值来作为这个目的像素的值呢?从实质上来讲，就是怎样通过邻近的像素值来计算出一个新的像素值，这个新值就是目的像素的值。传统三种算法在进行缩小时候，图像缩小的比例越大，像素跃越现象越明显，显然会产生高频干扰。因此要使得图像不失真必须采用低通滤波的方式将这些高频干扰去除。实际上我们处理的时候是将做反变换和滤波同时进行，这样做的效果更好于是我们运算量与运算结果上都做了考虑得到此种兼顾运算速度与运算质量的图像缩小算法。4.1.2算法实现设原图像的坐标为，该点的像素值为，目标图像的坐标为(x,y)，该点的像素值为。缩小的比例为k,k在(0,1)区间取值。则通过反变得到的一个浮点坐标为(x/k,y/k),对该坐标取整得到一个整数坐标。这种取得原图像坐标方法实际和近邻取样法完全相同。但是我们不直接利用该点的像素值，而是取该点的周围的某些点的平均值来作为目标点的像素值。这样做实际上就是一个低通滤波的过程。我们就称这种算法为近邻取样和邻域平均相结合的算法。邻域平均算法为：令被讨论像素的像素值为，以其为中心，窗口像素组成的点集以A表示，集内像素个数以L表示。经邻域平均滤波后，像素对应的输出为：，用窗口像素的平均值代替原来的像素值。邻域的选取通常有两种方式：以单位距离为半径，为一菱形窗口或单位距离的倍为半径，为一矩形窗口，在本文中我们采取了菱形窗口。具体编程的时候我们使用了如下模板(以距离为5个像素为例)。模板取法如图4.1所示：图4.1邻域平均55模板实际该模板为一个55的矩阵，使用步骤为：(1)将模板中心和通过近邻取样法得到的像素点位置重合；(2)将模板上系数与模板下对应像素值相乘；(3)将所有的乘积相加；(4)将和除以模板各系数之和得到目的图像对应点像素值。在有些情况下，我们还可以使用权值不相同的模板。如我们认为距离中心像素远的点对目的像素的影响小，我们就可以将他们的权值设小一些，相反距离中心像素近的点对目的像素的影响大，就可以将他们的权值设大一些。下面是一个权值和距离成反比的55模板：总的算法流程为：(1)读入原图像，得到图像的高度和宽度；(2)通过缩放比例得到目的图像的高度和宽度，建立空白目的图像；(3)从上到下，从左往右的顺序扫描目的图像；(4)扫描过程中对每一个目的图像的坐标，利用近邻法取样法在原图像中找到模板中心位置；(5)利用设定的模板进行邻域平均得到目的图像扫描点的像素值，如果模板覆盖在原图像的边界，要进行边界处理；(6)扫描完成，图像的缩小处理也就完成了。图4.2权值和距离成反比的55模板4.1.3算法评价本文讨论的近邻取样和邻域平均相结合的方法对图像进行缩小处理，具有算法简单，失真较小的特点。尤其在处理细节单调，背景和物体之间区别明显的图像，而且缩小比例较大的时候，处理效果较好，比较适合处理人的头像。但是在处理轮廓很细的图像的时候，轮廓的颜色失真较大，这方面有待于进一步提高。4.2基于Ferguson曲面插值的图像缩放方法4.2.1问题引入在传统的插值方法中，邻近点插值不能保证插值曲面连续，插值后图像会出现块状化(Jaggies)现象，图像视觉效果不佳，因而在实际的应用极少采用；双线性插值只能达到连续，在插值处只能保证灰度值连续，不能保证导数值连续，因此，在某些要求较高的场合仍不能满足要求。B样条插值方法可以达到连续，在插值处可以保证灰度值和直到二阶导数值连续，因而对一些细节丰富的图像应用双三次样条插值可以得到更好的视觉效果.但由于需要求解线性方程组，其计算时间较长，尤其是在放大倍数很大时，尤为明显.本文将计算机图形学中的Ferguson曲面插值应用于图像缩放中，提出了一种基于Ferguson双三次曲面插值的图像缩放算法.这种方法介于双线性插值和双三次样条插值方法之间，是一种插值方法，插值处灰度值和导数都连续，细节表现清楚，因此，从理论上讲该法优于邻近点插值方法和双线性插值方法.由于它是一种局部插值方法，不需要求解线性方程组，因而计算速度比双三次样条插值要快得多.4.2.2算法实现1.Ferguson双三次曲面给定双三次参数曲面4个角点处的几何信息：位置矢量(i，j=0，1)，沿向的切矢，以及四个角点处的扭矢，则满足以上几何条件的双三次曲面可表示为：(4.1)其中：，由公式(4.1)定义的曲面称为Coons双三次曲面.在实际计算时，4个角点处扭矢不容易确定.如果令上述公式中4个扭矢为零，即令此时由公式(4.1)定义的曲面就称为Ferguson双三次曲面.2.Ferguson双三次曲面插值对于给定的原始图像，在本文的算法中，插值曲面由M*N张Ferguson双三次曲面片组成。(4.2)其中，的含义同上。(4.3)整张插值曲面按如下方式定义：当时令(4.4)在矩阵(4.3)中，左上角代表像素的灰度值，均已知。左下角代表在4个角点处灰度值关于参数的变化率，右上角代表在4个角点处灰度值关于参数的变化率，用向后数值微分来估计这些值，即令(4.5)(4.6)至此，就得到了连续的插值曲面。对其进行重采样，即可得到任意大小的图像。根据上述构造过程，显然插值曲面具有连续性.而且，在构造的过程中，不需要解方程组，因此，计算速度很快。3.基于Ferguson曲面插值的图像缩放方法伪代码实现输入：原始图像FOR()/(s，t)为像素对应的全局参数I=FLOOR(s)；J=FLOOR(t)；/FLOOR代表向下取整的函数u=(s-i)；w=(t-j)；/(u,w)为像素对应的局部参数根据公式(3.2)，公式(3.3)，公式(3.5)，公式(3.6)计算令输出：缩放后的图像4.2.3算法评价Ferguson插值和三次样条插值得到的图像视觉上相差很小，质量都比较好，所生成的图像连续性好，细节清楚，有效地消除了方块效应.相比较而言，本文提出的方法计算速度要比三次样条插值法快得多，因而更加实用.由于该方法可以达到连续，因此，图像的效果比常用的邻近点插值法和双线性插值方法要好.由于采用局部插值方法，不需要求解线性方程组，所以和双三次样条插值方法相比，该算法计算速度有很大提高.综上所述，这是一种非常实用的图像缩放算法.4.3带系数自适应插值算法及其改进114.3.1问题引出在传统的图像插值算法中，双线性插值与最邻近法相比，由于考虑了待采样点周围四个直接邻点对待采样点的影响，因此基本克服了前者灰度不连续的缺点，但其代价是计算量有所增大。但进一步看，由于此方法仅考虑四个直接邻点灰度值的影响，而未考虑到各邻点间灰度值变化率的影响，因此具有低通滤波器的性质，使缩放后图像的高频分量受到损失，图像的轮廓变得较模糊。用此方法缩放后的图像与原图像相比，仍然存在由于计算模型考虑不周而产生的图像质量退化与精度降低的问题。作为对双线性内插法的改进，即不仅考虑到四个直接邻点灰度值的影响，还考虑到各邻点间灰度值变化率的影响，立方卷积法利用了待采样点周围更大邻域内像素的灰度值作三次插值。因此单从图象处理质量上考虑，双三次插值是优于其他两种基本算法的，我们还可以从三次放插值的算法实现上仔细做数学上的推导变可以得出一个规律，从而实现基本算法的最佳插值方法。4.3.2数学推导与算法实现1.数学推导双三次插值算法的插值核函数为：(4.7)插值后的像素灰度计算公式为：(4.8)上式中：我们分析式(4.7)和式(4.8)可以发现：(4.9)令，则，。若令k=0，则式(3.8)的立方卷积法就退化为双线性内插法。因此，可以把用三次多项式插值的立方卷积法看成由两部分组成。其中代表直接邻点的灰度值对待采样点的影响，而k则代表邻点间灰度值的变化率对待采样点的影响。与双线性内插法相比，立方卷积法不仅考虑了直接邻点的灰度值对待采样点的影响，还考虑了邻点间灰度值变化率的影响，因此后者所求得的待采样点灰度值更接近原(采样)值。此方法用进一步增大计算量来换取待采样点精度的进一步提高，但这种方法中的两个部分(即与k)的搭配是否最佳，值得进一步研究。2.算法实现从图(4.3)可以看出在求待采样点的插值时，最近邻点法只考虑直接邻点中距离最近点的影响，其权值为1；双线性内插法考虑了所有直接邻点的影响，各点权值由距待采样点的距离决定，距离近的权值大，距离远的权值小；而立方卷积法不仅考虑了所有直接邻点的影响，还考虑了所有间接邻点的影响，各点权值也由距待采样点的距离决定。通过分析上述几种插值算法可以看到，直接邻点对待采样点的影响是最大的，也是最主要的。同时从对立方卷积法的分析中可以看到，间接邻点通过影响直接邻点的灰度值而影响待采样点的灰度值，这一关系反映在邻点间灰度值的变化率上，因此也是最佳插值算法中必须考虑的因素。在式(3.9)中代表直接邻点的灰度值对待采样点的影响，而k则代表邻点间灰度值的变化率对待采样点的影响。前面几种方法对这两种影响的大小都没有进行优化，因此适当调整两种影响的大小.可以找到一种最佳的插值算法，可以对式(3.9)进行修正。令修正值0，1，将式(4.9)改写为：(4.10)图(4.3)几种插值法的比较当=0时，式(4.10)代表的是双线性内插法；当=1时，式(4.10)代表的是双三次插值法。越大邻点间灰度值变化率的影响权值就越大；越小，直接邻点灰度值的影响权值就越大。经过计算与统计分析可以发现，当取01之间的值时，内插效果优于立方卷积法，这说明立方卷积法中邻点间灰度值变化率的权值过高，即应取小于1的某个值。对于不同的图像，最佳的取值不同。如图(4.3)所示，对不同的图像在立方卷积法和双线性内插法的权值曲线间还有一个最佳的内插曲线，用该曲线求出的权值来处理图像效果比前两者都好。3.改进算法由上面叙述可以知道，根据被处理图像各像素点之间的灰度变化率适当调整系数，可以对图像达到最佳的插值效果。但是，这种算法的缺点有两个：首先，这个是需要有人的互动在里面，系统不可能自己根据像素灰度的变化率做一个系数的自动调整；其次，对于特殊图像比如有的部分像素灰度值变化快，有的变化慢，则该算法不可能做到兼顾全局。因此我们迫切的需要一个可以根据像素灰度值变化率自己做系数调整的改进算法。该算法实现方式如下：(1)设置一个像素灰度值变化临界值d；(该值一般在0.04-0.05之间)(2)假设第点处的像素的灰度值为，假设图像的读取与存贮是从图像的最上端从左至右按行依次进行的所以下一个像素点为，其像素灰度值为。这两个点的灰度差值为，则；(3)如果，明这两个点的像素的颜色变化不大，此时采用最近邻插值；如果，说明这两个点的像素的颜色变化较大，此时采用双三次插值算法，用这种图像插值算法，既保证了图像变化后的质量，又提高了运算速度。4.4基于数字图像边缘提取的插值算法4.4.1问题引入传统的图像插值酸法有着速度快的优点，但是在放大效果方面各有不足。最近邻插值法只是简单地将源像素点最邻近的像素点(最邻近取样)进行复制，其结果是会产生像素块(即马赛克)，使得图像整体不清楚。而双线性插值法则利用了源像素点周围邻近的4个像素点的线性平均权值来计算目标像素点的值，这样虽然可以得到较好的整体效果，但图像的边缘会变得模糊，细节部分不够清晰，双三次插值也存在这样的问题。因此我们在考虑图像边缘的情况下，引入了一种定向插值的插值算法。4.4.2图像定向插值的一般实现方法定向插值放大与一般插值放大的最大不同之处在于其插值过程是沿着图像的边缘而不是跨过边缘插值进行的，因此定向插值要求先找到图像的边缘，或者更进一步地要先确定图像中灰度值梯度变化处每一个像素点的方向。在得到了图像的边缘后，我们就可以选择个合适的插值算法进行插值放大。需要注意的是这里所用的插值算法必须是线性的而不能是双线性的因为如果再用双线性插值就会破坏我们前一步所查找到的图像边缘信息。图4.4 sobel矩阵Sobel矩阵是最常用的查找图像边缘矩阵。单个的Sobel矩阵可以检测水平和垂直方向的边缘，两个Sobel矩阵合在一起就可以得到全面的图像边缘信息。虽然Sobel矩阵有较好的鲁棒性且构造简单，但是在实验中我们发现Sobel矩阵会忽略掉所有通过矩阵中心的一个像素宽的边缘线，包插或的对角线也会被忽略掉。这一缺陷的产生是由于33的像素区域太小，不足以确定穿过矩阵中心的边缘。对这一问题的解决有两种方法可以考虑：一是选用一个更大矩阵，如55的矩阵。这样可以增加插值的参考点，从而取得更好的插值效果。这种方法的优点是计算方法简单，容易实现；缺点则是会加大计算量，不符合图像处理的基本要求。二是用类似图4.5中的方法。以放大两倍为例，先将每一个源像素点都分割成4个目标像素点，从而找到每一个目标像素点的插值配对，对于每个源像素点有4个不同的插值配对(4和0，4和3，4和1，4和l、3的平均值)，这样就可以算出每个源像素点的4个可能的梯度值。图4.5显示了如何分割源图中每次取样得到的9个源像素点。为了计算黑色区域所代表的目标像素插值点方向，要算出0，1，3和4这4个源像素点所组成区域中的最小梯度(用色彩的最小差值可以很好的近似)。这一方法虽可以避免直接增加计算量，但其瓶颈在于如何快速有效地算出取样区域的色彩差值。如果不能采用有效的算法(如所介绍的算法)，其计算量也会非常大，这一点在对24位图像进行处理时表现得尤为明显。4.4.3图像定向插值的简化算法其基本思想和上述方法是一致的，只是在确定图像边缘的过程中作了一定的简化处理。首先我们还是选用33的矩阵作为取样模板，这样可以兼顾处理的速度和精度。接下来查找边缘的方法和上述的逐点计算方向不同，这里我们用一定的阈值将每次取样所确定的源像素区域分为两个部分。大于阈值部分的权值为1，小于阈值部分的权值为0。阈值的选取很重要这一点在后面会进一步说明。最后只要确定目标像素点所对应的源像素点属于哪一部分，将该部分的所有像素点作为计算的取样点，取样点值的平均值就是所求目标像素点的值。这种取平均值的方法实际上是默认所有源像素点的权值，是相同的线性插值，是该简化算法的另一个近似处理。如图