误差扩散算法（精选3篇）
误差扩散算法 篇1
数字半色调处理是将连续色调图像转换成二值图像的一个重要过程[1,2,3,4]。当使用有限色彩的打印机打印灰度图像或彩色图像时, 该处理过程是必须的。对于灰度图像, 半色调处理仅使用黑色和白色像素再现原灰度图像的色调和细节。对于彩色图像, 先将彩色分层, 半色调处理将每一层颜色进行二值化处理。最为人们熟知的半色调处理算法是误差扩散法[5], 它将每一个像素的二值化误差乘以一定的系数后扩散到相邻的未处理的像素上。
本文的主要贡献是提出了一种基于误差扩散法的图像隐藏算法。假设有3幅尺寸相同的灰度图像A, B和C, 本文提出的算法是使用误差扩散法对这3幅图像分别进行半色调处理, 处理后的半色调图像记为A’, B’和C’, 并且C’图像在效果上等同于A’和B’的重合图像。更确切地讲, 对于C’中的像素, 当它为白色时, A’和B’中对应位置的像素必须为白色。图1举例显示了A’, B’和C’的关系。如果将A’和B’打印在透明纸上, 当重合A’和B’时即可看到C’图像。为了得到C’, 必须同时有A’和B’, 2幅图像缺一不可。
本文提出的图像隐藏算法有2类用途:一类可以用作水印处理, 比如图像A’是需要传播的图像, 图像C’是需要隐藏的图像以此来标明图像A’的版权, 图像B’则相当于一把秘钥用来查看C’。另一类可用作娱乐目的: (1) 图像A’和B’是母图, 图像C’是子图。图像C’隐藏在图像A’和B’中, 当重合母图时即可看到子图。 (2) 使用图像A’做猜谜游戏, 假设有3个选项B1’, B2’和B3’, 其中B2’是猜谜游戏的正确答案, 则重合A’和B2’可看到一幅特别图像。
1 半色调处理和图像隐藏
假设有一幅尺寸为n×n的灰度图像, 其中表示位置在 (i, j) (0≤i, j≤n-1) 该处的像素值, 该值的取值范围为[0, 1]。为了简便, 本文假设图像都是正方形的, 完全可以扩展到非正方形图像的情况。对图像A进行半色调处理的目的是获得一幅与A尺寸相同的二值图像, 这里只能取值0 (表示黑色) 或者1 (表示白色) 。
误差扩散法是一种非常流行的半色调处理算法, 该算法将每一个像素的量化误差乘以一定的系数后加到邻边未处理的像素上。误差扩散法对图像的处理是按照从上到下、从左到右的顺序进行的。它将灰度图像的每一个像素都与固定阈值0.5比较, 如果像素值大于阈值, 则该像素量化为1, 否则量化为0。换句话说, 二值图像的像素值由如下方式决定:
显然, 量化误差为。注意, 量化阈值选为0.5的原因是它可以将量化误差最小化, 这个观点将使用到本文提出的基于误差扩散法的图像隐藏算法中。
误差扩散法的关键是补偿量化误差, 补偿的方法就是将量化误差按照一定比例扩散到邻边未处理的像素上。Floyd和Steiberg提出了如下的误差扩散系数:
使用这组系数, 邻边像素的值更新如下:这组系数的总和为1, 因此, 量化误差e扩散到了邻边的4个像素上。
假设有3幅尺寸为n×n的灰度图像A, B和C, 本文的目标是获得该3幅图像对应的二值化图像A’, B’和C’, 使其满足如下条件:
(1) 二值化图像A’, B’和C’能够再现灰度图像A, B和C的色调。
(2) 二值图像C’是A’和B’的重合图像, 即在所有位置 (i, j) (0≤i, j≤n-1) 处满足。
换句话说, 如果和中任一项为0 (即黑色) , 那么就是0;如果和均为1 (即白色) , 那么也是1。图1列出了满足条件2的一个例子。如果将图像A’和B’都打印在透明纸上, 则重合时便可看到图像C’。
2 基于误差扩散的图像隐藏算法
这一部分将详细介绍本文提出的图像隐藏算法, 该算法对灰度图像A, B和C进行二值化处理, 得到对应的二值图像A’, B’和C’, 且其满足以上条件1和条件2。本文提出的算法包含以下2个步骤:
(1) 调整灰度图像A, B和C的像素值范围。
(2) 使用基于误差扩散的半色调技术对已调灰度图像A, B和C进行二值化处理, 得到二值化图像A’, B’和C’。
2.1 调整灰度图像的像素值范围
这一部分将显示如何调整灰度图像的像素值范围并述说理由。令R表示尺寸为n×n的图像中的一个包含m个像素的小区域, 则R (A’) , R (B’) 和R (C’) 分别表示图像A’, B’和C’中的相应区域的子图。很明显, 为了满足条件2, 如果R (A’) 和R (B’) 分别包含x个和y个黑色像素, 则R (C’) 包含的黑色像素的个数必然在如下范围内[max (x, y) , min (m, x+y) ]。假设R (A’) 和R (B’) 包含的黑色像素的个数都在范围[α, β] (α≤β) 内。如果R (A’) 和R (B’) 均包含α个黑色像素, 则R (C’) 包含的黑色像素个数在范围[α, min (m, 2α) ]内。同理, 如果R (A’) 和R (B’) 均包含个黑色像素, 则R (C’) 包含的黑色像素个数在范围[β, min (m, 2β) ]内。因此, 如果β≤min (m, 2α) , 可以确保R (C’) 包含的黑色像素个数在范围[β, min (m, 2α) ]内, 本文取和以最大化R (A’) , R (B’) 和R (C’) 包含的黑色像素的个数范围, 在这种情况下, R (A’) 和R (B’) 包含的黑色像素的个数在范围内, R (C’) 包含的黑色像素的个数在范围内。这就意味着需要将灰度图像A和B的像素值范围调整为[0.25, 0.5], 将C的范围调整为[0, 0.25]。因此, 本文对灰度图像A和B的像素值x作调整如下, 对C作调整如下。图2显示了调整函数f和g, 显然f的取值范围为[0.25, 0.5], g的取值范围为[0, 0.25]。
2.2 使用基于误差扩散的半色调算法产生3幅二值图像
这一部分将介绍基于误差扩散的半色调算法。假设图像A, B和C的像素值已经用以上方法调整过了, 令和为已经调整过的灰度图像。以下将介绍如何使用基于误差扩散的半色调算法得到二值图像和。
和常规误差扩散法类似, 二值图像A’, B’和C’的像素也是按照从上到下、从左到右的顺序获得的。常规误差扩散法选择固定量化阈值0.5, 旨在最小化量化误差。本文算法的中心思想是将常规误差扩散法的这种策略延伸到3幅图像中, 即二值像素, 和的选择要能最小化3幅图像的量化误差总和。为了满足条件2, 像素组合 () 的可能取值只能是以下4种情况之一: (0, 0, 0) , (0, 1, 0) , (1, 0, 0) 和 (1, 1, 1) 。3幅图像的量化误差总和定义为:
像素组合 () 的选择要能最小化误差E () 。灰度图像A, B和C的量化误差分别为和, 它们将在乘以由Floyd和Steiberg提出的误差扩散系数后分别加到各自的邻边未处理像素上。比如, 对其中的灰度图像A, 量化误差扩散如下:对图像B和C用相同的方法扩散量化误差eb和ec。
3 实验结果
在这一部分本文将给出一组实验结果。图3显示了由本文所提的基于误差扩散的半色调算法生成的3幅二值图像A’, B’和C’, 这3幅图像具有相同的尺寸256×256。其中图像A’和B’是直接由本文提出的半色调算法生成的, 它们中都隐藏了图像C’的部分信息, 而图像C’是图像A’和B’的重合图像。在图像A’和B’中, 看不到任何影藏痕迹, 从图像C’也可以看到隐藏图像可以被清晰地再现。由实验结果可见, 本文提出的基于误差扩散的图像隐藏算法不仅可以成功隐藏图像, 而且也可以很生动地再现隐藏图像。
4 结语
本文介绍了一种新的基于误差扩散的半色调算法, 该算法可将1幅二值图像隐藏到另外2幅二值图像中, 并且通过图像重合可以再现隐藏图像。因为本文的图像隐藏算法需要对原始灰度图像的像素值范围进行压缩, 以至于得到的二值图像对比度比较低。笔者的下一个目标是改进本文算法以提高结果图像的对比度。
摘要：数字半色调处理是将连续色调图像转换成二值图像的一个重要过程。使用有限色彩的打印机打印灰度图像或彩色图像时, 该处理过程是必须的。文章的主要贡献是提出一种基于数字半色调处理的图像隐藏算法, 该算法将1幅二值图像隐藏到其他2幅二值图像中。实验结果显示, 文章提出的算法可以很好地隐藏和再现秘密图像, 因此, 该算法既可应用于水印技术, 也可应用于娱乐目的。
关键词：数字图像,半色调,误差扩散,水印,图像隐藏
参考文献
[1]Y.Ito and K.Nakano.Fm screening by the local exhaustive search, with hardware acceleration.In Proc.of Workshop on Advances in Parallel and Distributed Computatinal Models (CD-ROMof International Parallel and Distributed Processing Symposium) , 2004.
[2]Y.Ito and K.Nakano.FM screening by the local exhaustive search, with hardware acceleration.International Journal of Computer Science, 2005.
[3]D.Lau and G.Arce.Modern Digital Halftoning.Marcel Dekker, 2001.
[4]X.Zhuge, Y.Hirano, and K.Nakano.A new hybrid multitoning based on the direct binary search.In Proc.of International Multi Conference of Engineers and Computer Scientists, 2008.
[5]R.Floyd and L.Steinberg.An adaptive algorithm for spatial gray scale.SID 75 Digest, Society for information display, 1975.
误差扩散算法 篇2
数字半色调技术(又称数字加网技术)是基于人眼的视觉特性和图像的成色特性,利用数学、计算机等工具,在二值设备或多色二值设备上实现图像再现的一门技术,是将连续色调图像经过处理后再输出以实现图像阶调再现的基础性研究[1,2]。
数字半色调技术的原理是将具有连续色调的图像转化为二值图像阵列,并打印到打印介质上,使输出的二值图像阵列给人造成一种视觉上的连续色调效果。它充分利用人眼的低通滤波特性,当人近距离观看打印输出的二值图像时,由于可以看到单个的点,所以视觉效果不连续,但如果在远距离观看,就察觉不到单个点的存在,打印出的半色调图像局部平均灰度值近似于原始图像的局部平均灰度值,从而在整体上产生了输出图像中的多种灰度感觉,在视觉上形成连续色调的效果。
数字半色调算法中处理性能最好的是误差扩散算法。其优点是获得的半色调图像效果好、色调丰富、像素点的分布具有各向异性。然而误差扩散算法中,由于未考虑人的视觉系统模型(HVS模型)对图像的识别情况以及采用固定的分散系数,高光和暗调部位出现与半色调处理方向相关的滞后现象造成了图像轮廓的失真。为了更好的使图像在频带上很好的过渡,在本算法中引入了双向反馈的思想。而由于最终判定图像的是人的眼睛,因此把HVS 模型对图像的影响引入本算法中。在这个算法中使用了两个滤波器,其中一个滤波器借助了基于HVS模型的误差核,另一个滤波器根据当前像素与领域像素的特征情况确定分散系数,而在考虑再现图像特征时不仅再现图像的灰度特征,而且再现图像的HVS特征。
2 传统的误差扩散算法的基本原理
误差扩散算法[3]由 Floyd 和 Steinberg 于1976年首次提出 ,其基本思想为先阈值量化图像像素,然后将量化的误差扩散到相邻的未处理的像素上。其原理和误差滤波器的权系数如图1所示。其中每个象素的误差扩散过程包括如下三个步骤。第一,将原始象素值加上扩散到此处的误差作为当前输入;第二,将当前输入进行阈值处理得到一个输出 ( 0 或 1,半色调研究中灰度值一般都归一化);第三,将输入与输出的误差值按照一定的规律扩散到未经处理的区域。
n为当前处理的图像单元,0为已处理的单元, h(1,0),h(1,1),h(0,1),h(-1,1)为未处理单元。滤波器的脉冲响应h(1,0)=7/16,h(1,1)=1/16,h(0,1)=5/16, h(-1,1)=3/16 ,其滤波过程也就是将当前处理像素的量化误差以上述权重传递给未处理的像素的过程。
观察图5(b),经过 Floyd-Steinberg 半色调处理后,获得的半色调图像效果好、色调丰富、像素点的分布具有各向异性,灰度过渡比较自然,具有很好的细节再现能力;但也存在以下不足:如在半色调图像中诸多网点处存在“龟纹”和“网点”现象,在高光和暗调部位出现的与半色调处理方向相关的滞后现象,边缘部位不连续的过渡现象以及处理速度相对较慢。
3 基于双向反馈的误差扩散算法
3.1 算法原理
通过分析传统的误差扩散半色调算法,其实质上是进行了高通滤波和低通滤波的处理 ,因此造成了“龟纹”和“伪轮廓”的出现,现在我们通过研究,在高频与低频中加入中间频带,这样图像在频带上具有很好的过渡,图像质量总体上来说应该更好。因此,我们在经典的误差扩散的单反馈的思想上,通过引入双向反馈,提出了基于双向反馈的误差扩散半色调算法。
双向反馈误差扩散半色调原理如图2所示。
其流程如下:
u(m,n)=x(m,n)-undefinedh(k,l)e(m-k,n-l)
g(m,n)=u(m,n)+undefined
undefined
此基于双向反馈误差扩散半色调算法与传统误差扩散算法相比,采用了两个误差滤波器,误差分散滤波器h和反馈滤波器 w。其中w采用了基于HVS模型的误差分散核,并且对误差扩散滤波器 w 继续进行小幅度的随机抖动,从而使得到的图像的视觉效果更好。而h采用了一与领域特征相关的滤波器,从而在一定程度上减轻了方向性纹理和人工纹理的出现。
3.2 HVS 模型
半色调之所以能够模拟连续色调图像是依赖于人眼视觉系统 ( human visual system, HVS) 的低通或带通滤波器的特性,如将图像从空间域变换到频域,那么频率越高,人眼的分辨能力就越低;频率越低,人眼的分辨能力就越高,这就是HVS的频域特性[4]。由人眼对高频细节敏感性较低可知,人眼相当于一个低通滤波器[5]。由于图像最终的服务对象是人的眼睛,尤其是半色调技术,判定一个算法优劣的标准最终由人眼决定,因此在半色调算法中引入HVS 具有重要意义。目前,对于数字半色调技术,Nasanen 的 HVS 模型具有最好的低通特性,通过它产生的半色调图像具有最好的主观视觉效果。又因为 Gaussian 函数具有许多适合半色调处理的特征,如光滑的单峰曲线使其具有很理想的低通特性,其滤波器的傅立叶反变换也是高斯的等,实际应用中常使用Gaussian 低通滤波器近似表示 Nasanen 模型。
3.2.1 HVS模型在频域中的表示
HVS 模型具有不同的表示方法,在频域中HVS 模型[5]可以定义为
undefined
式中:L 为每平方米亮度均值,其单位为 cd/m2,u和ν为朝向视网膜的单位角度内的光线周期变化频率,(u2+ν2)1/2则为光线的频率;□的值为角度的变化频率,定义为□=a·tan(u/ν);其它常数s(□)被定义为a=131.6;b=0.3188;c=0.525;d=3.91;s(□)=0.15×cos(4□)+0.85。
HVS函数具有以下三个方面的特征:①在频率域中,它是一个递减函数;②它沿45°线的响应是水平和垂直线响应的2～1/2;③在所有的频率域中,该函数值大于零。
3.2.2 HVS模型的亮度特性
人类视网膜由两大类视觉细胞构成,一类叫视杆体(rods),在暗光环境下特别敏感;另一类叫视锥体(cones),在亮光环境下特别敏感。实验表明,人们对物体亮度的感觉同进入人眼的光强成对数关系,但人们对物体亮度的感觉并不完全由物体本身亮度所决定,还与物体所处的背景亮度有关[6]。人眼主观上刚可察觉的最小亮度差,称为亮度的可见度阈值 (threshold),可见度阈值与背景亮度间的关系的示意曲线如图3所示,对于不同的物理亮度水平,此阈值的响应曲线呈现分段、非线性特点(移变非线性),这就是人眼的亮度适应性,它产生的根源是视细胞非线性地把接收到的光信号转换成电信号。当背景亮度大于10cd/m2时,亮度适应性可用著名的weber一Fencher定律描述,阈值与背景亮度为对数非线性关系;当背景亮度处于10cd/m2以下,阈值与背景亮度为平方根(或立方根)关系。由于感知亮度的非线性压缩作用,在高亮度区,视觉感知可以允许较大的图像误差,表现出亮度掩盖效应[7]。
3.3 反馈滤波器w和分散滤波器h
3.3.1 反馈滤波器w
由于图像最终的服务对象是人的眼睛,所以如果使用基于HVS模型的分散核作为反馈系数,则最终的视觉效果将会更好。在此算法中为了克服固定的反馈系数造成方向滞后的现象,对滤波器w进行了小幅度的随机抖动。
3.3.1.1 基于HVS模型的误差核
误差分散系统本身是一个非线性的模型,为了便于分析及对误差分散半调系统进行最优化处理,使用一种附加了噪声的线性增益模型,这一模型由Ardalan和Paulos[5]在一维的情况下使用,这里将其应用到误差分散系统。
在一维向量中由图1(a)知误差图像可由下式来表示:
e(n)=Q(u(n))-u(n) (1)
因为e(n)与x(n)相关,x(n)与u(n)相关,因此e(n)与u(n)相关。从式中可知Q(u(n))一u(n)与u(n)有关,对此相关性用下式来表示
Q(u(n))=K u(n)+m(n) (2)
其中,K是常数,m(n)是与原图无关的白噪声。将量化过程Q(.)建模成为线性增益K与无关白噪声源m(n)的叠加。
输出半调图中的噪声部分在Z域中表示如下:
Bz(z)=(I一H(z))N(z) (3)
对上式进行逆变换就可以得到输出噪声在空域中的表达式:
bm(n)=(1一h(n))*m(n) (4)
令v(n)表示一个完整的HVS模型,则(v(n)*bm(n))表示输出半调图中
的加权噪声能量。用函数J表示它的期望值,形式如下:
J=E[‖v(n)*(1-h(n))*m(n)‖2] (5)
由上式可确定基于人眼视觉模型的误差核[8]:
undefined
本算法采用的基于HVS模型的误差扩散系数矩阵[9]为
undefined
3.3.1.2 本算法中对此误差核的处理方式
基于HVS模型的分散系数的扩散原理和权重分配系数如表1所示:
其中**代表了当前点像素位置,其它位置的算术比值代表了与当前像素相对位置上的误差扩散权重,取值范围在[0,1],且满足:2×w1+4×w2+2×w3+2×w4+2×w1+5∈[0,1]。
一般情况下我们分配如下的权重系数:W1=1/134, W2=5/134, W3=12/134, W4=12/134, W5=32/134。对误差扩散滤波器 w 继续进行小幅度的随机抖动 ,其处理方法如下:
wrand=(r(i,j)/rand_max-0.5)×cDither[10]
w′1=w1+wrand
w′2=w2+wrand
w′3=w3+wrand
w′4=w4+wrand
w′5=w5+wrand
其中, wrand为抖动微调参数; r(i,j)为当前扫描点随机参数, rand_max为随机参数r(i,j)的最大值 , cDither为抖动幅度调整系数。w′1～w′5为误差扩散滤波器 w 小幅随机抖动后的权重分配系数。
3.3.2滤波器h
3.3.2.1 图像特征函数
图像的特征函数反映了再现图像的特征信息,在实现过程中,若需要再现图像的不同特征,应选取不同的特征函数。在此算法中主要考虑再现图像的灰度特征和HVS特征。所以在实现过程中选取了两个特征函数。在这里这两个特征函数采用加权求和的方式得到一个反映图像特征信息的复合函数。设图像的复合特征函数为F(x,y),图像的两个单个特征函数分别为f1(x,y),f2(x,y)则该图像的复合特征函数表示为F(x,y)=w1·f1(x,y)+w2·f2(x,y)。其中,w1,w2分别是图像不同特征函数的权值,且w1+w2=1,其值的大小可由用户根据再现图像特征信息的需要进行不同的设置。
a、灰度特征函数
将图像的每个像素的灰度值作为反映图像灰度特征的函数,以再现图像的灰度特征。
b、视觉特征函数
(1)利用3.2中HVS函数计算出H(u,v) (u∈[1,2,3…],v∈[1,2,3…])在频域中的值;
(2)将(l)的HVS函数H(u,v)进行反傅立叶变换,得到空间域中的相应函数h(x,y) (x∈[1,2,3…],y∈[1,2,3…])其变换方法为:
设待处理频率域中的二维离散化的函数为H(u,v),则该函数的反傅立叶变换的关系为:
undefinedundefinedH(u,v)ej(2π/M)xuej(2π/N)yv (1)
其中:x=0,1,2,…,M-1;y=0,1,2,…,N-1。
利用公式(1),在空间域中计算h(x,y) (x∈[1,2,3…],y∈[1,2,3…])函数的函数值,选取所得值的实数部分作为缘检测模板系数,利用这些模板系数与原图像进行卷积。根据卷积的结果,选取合适的系数,对原图像进行相应的线性变换,即得到具有HVS特征的特征图像。
3.3.2.2 滤波器组成
滤波器h由两部分来组成,如图4所示
在Hwang[11]算法中仅是考虑当前象素的灰度特征,在本算法中我把图像的视觉特征考虑进来。则图4中D(i,j) 和G(i,j)分别由如下公式得到:
undefinedundefined
undefined
其中D(i,j)为原图像中当前像素特征值与领域特征平均值的差,在此考虑领域为一3×3的窗口。G(i,j)为一权函数,其值与D(i,j)的符号相关。D(i,j)值为0时表示当前像素与领域像素具有相似的特征,说明这一领域的阶调变化是平缓的,因此经半色调得到的二进制图像中这一区域的阶调变化也是平缓的,因此可以采用图像中的分散系数;D(i,j)值为一正值时说明当前像素与领域像素相比其特征变化是剧烈的;D(i,j)值为一负值时说明当前像素与领域像素相比其特征变化同样是剧烈的,只不过与D(i,j)为正值相比,其走向是不同的。权函数G(i,j)中的a控制着边缘重建时的强调级别,b保护边缘以免被陡峭的阶调变化过分强调。
4 实验结果
在 MATLAB7.1环境下,对256级灰度256 ×256 分辨率的Lena图 (图5(a)),用本算法进行仿真试验。在此选用a=2.5,b=0.02,而复合函数中wi值较大些。从图5(b)、(c)可以看出,与标准误差扩散算法相比较经本算法处理后方向性纹理得到明显改善,图像的细节更加显现,更加符合人眼对于原图的视觉效果。
5 结论
与以往的误差扩散半色调算法相比,本文提出的基于双向反馈及HVS模型的误差扩散算法,处理后的图像很大程度上减少了“伪轮廓”和“龟纹”现象。由于图像最终的服务对象是人的眼睛,所以在分散滤波器与反馈滤波器的设置上均使用到了HVS模型。在本算法中分散滤波器采用了根据当前像素与领域像素的特征(灰度特征和视觉特征)确定分散系数;反馈滤波器采用了基于HVS模型的分散核,并在此基础上进行了小幅抖动。从而很好地克服了以往误差扩散滤波器中由于固定系数扩散所产生的方向性纹理缺陷,使图像的整体视觉效果更好。
摘要：针对传统误差扩散中的“龟纹”和“伪轮廓”现象,在基于标准误差扩散算法的基础上,提出一种基于双向反馈的误差扩散半色调算法。它不仅在误差扩散后的高频和低频成分中依据HVS模型加入了中间频带,使图像更趋于均匀和柔和,并且根据领域图像灰度特征和HVS特征动态修改误差扩散滤波器系数,尽可能的克服了由于固定系数扩散所产生的方向性纹理缺陷。
关键词：数字半色调,误差扩散,HVS模型,双向反馈
参考文献
[1]R.A.Ulichney,Digital Halftoning[M].The MIT Press,1987.
[2]D.Anastassion,K.Pennigton,Digital halftoning of image[C],IBMJ.Res.Devel,Vol.26.pp:687-697,1982.
[3]R.W.Floyd and L.Steinberg.An adaptive algo-rithm for spatial grayscale[C].Proceeding Of the society for Information Display,1976,Vol.17,No.2,PP:75-77.
[4]李晓东.非线性逆误差分散应用研究[D].西安:西安建筑科技大学,2008.
[5]S.Ardalan and J.Paulos.An analysis of nonlin-ear behavior in delta一sigmamodulators[J].IEEE Trans.Circuits Syst.,Vol.34,June1987.pp.593-603.
[6]侯志强,韩崇昭,郑林,肖李珍.一种基于视觉模型的边缘检测阈值选择策略[J].光电工程2004年,第31卷第2期,PP:59-62.
[7]曹圣群,黄普明,鞠德航.HVS模型及其在静止图像压缩质量评价中的应用[J].中国图像图形学报,APr2003,Vol.8(A),No.4,pp.379一385.
[8]袁龙飞.基于人眼视觉系统模型的彩色半调算法[D].西安:西安建筑科技大学,2007.
[9]ZHANG XIAOHUA,L IU FANG,J IAO LCHENG.An effective image halftoning and in-verse halftoning technique based on HVS[C]∥Proceedings of the fifth international conference on computational intelligence and multimedia applications.Xi’an:IEEE Computer Society Press,2003,441-445.
[10]钟平,钟建军,张伟,潘涌.基于双向反馈的自适应误差扩散半色调算法[J].应用激光,2008年,第28卷第4期:327-331.
基于扩散方向的图像修补算法 篇3
数字图像修复技术就属于图像修补的研究范畴,是图像处理领域的一个分支,也是当前的一个研究热点,在文物保护、影视特技制作、虚拟现实、多余物体剔除(如视频图像中删除部分人物、文字、小标题等)等方面有很高的应用价值。
数字图像处理的研究已经发展了很多成熟的模型,主要包括基于偏微分方程图像修补模型和基于整体变分模型。比较有代表性的前者如Bertalmio提出的BSCB模型,后者如T.Chan等人于2002年提出基于TV模型。本文通过对上述两种模型的研究,然后综合考虑BSCB模型、TV模型的扩散方向,并结合方向扩散提出同时考虑法向及切向扩散的多方向性统一修补模型。
1 基于偏微分方程的BSCB模型
受到专业人士手工修补方法的启示,Bertalmin等人在2000年的SIGGRAPH会议上提出BSCB图像修补模型,并发表了他们的研究成果,明确地提出图像修补的定义、预期目的及应用分类,并使用了基于偏微分方程的分析方法,促进了这个领域的研究。
在BSCB方法中,修补的过程是一个基于扩散的过程。它的主要思想是将到达修补区域的边缘以原有的角度延伸到区域里面,即沿边缘做切向扩散。
假设待修补的图像为I0(i,j),图像修补的过程就是不断对污损图像的迭代、改善过程,将该迭代过程产生的一系列中间结果看作一组图像序列I(i,j,n),其中I0(i,j)=I(i,j,n),该迭代过程用数学语一言描述如下:
其中,上标n表示当前修补次数,(i,j)表示像素坐标,⊿t是迭代的速率,表示本次图像的更新量。需要注意的是,该迭代过程只对待修补区域Ω内的像素进行,不改变其它区域的像素值,即只对待修补区域内部的点进行修补。随着迭代过程的进行,图像的修补效果越来越好,下一幅迭代图像都是以相应的更新量对本幅图像进行更新的结果。因此,如何设计更新量就显得至关重要。
依据人工修补的原则,我们需要将Ω外部的有用信息平滑地传播到内部。令Ln(i,j)表示需要传播的信息,并按拉普拉斯算式计算。令表示传播的方向,随着迭代次数n的增加,传播量Ln(i,j)就逐渐地扩散进待修补区域内,直至相邻的两次修补效果相差不大时停止,此时,。
接下来要确定的是传播方向。在该模型中,传播方向取等照度线方向。我们知道,梯度对应于图像灰度变化最大的方向,而垂直于梯度的方向则是灰度变化最小的方向。因此,使用梯度方向的90度旋转作为等照度线方向。修补过程中,只要沿着等照度线的方向进行修补即可,修补效果跟对梯度方向进行顺时针还是逆时针旋转关系不大,只要保证是灰度值变化最小的方向即可。
为了修补过程中图像的正确演化,需要在修补过程中穿插进行扩散。同时为保持边缘的锐利性,在扩散过程中采取各向同性非线性扩散方程。
其中,Ωε表示对Ω区域以半径为ε的结构元进行形态学膨胀后的区域;k(x,y,t)表示等照度线的欧几里德曲率;当(x,y)∈Ω时,gε(x,y)取值为1,当时,gε(x,y)取值为0,这就相当于只更新待修补区内的像素值。
2 基于整体变分的TV模型
图像修补的目的就是要借助待修补区的邻域信息来修补该图像,并使修补后的图像尽可能的逼真,使观察者不易察觉。TV模型主要是寻找代修补区域及周边区域上的一个代价函数,然后通过最小化该代价函数来实现对图像的修补。
将原图记为u。,修补后的图像记为u,定义代价函数为:
满足如下噪声约束条件:
其中,A(E)为区域E的面积,E内初始图像值uo被高斯噪声污染,σ是白噪声的标准方差。可见上述公式式是为了使待修补区域及其边界尽可能地平滑,同时保证该模型对噪声的鲁棒性。
为了保证能够修补断裂的边缘,需要选择合适的r(.)函数形式。在边缘上▽u是一个一维冲击函数δ,因此要求代价函数R[u]有限。通过变换展开可得出经典TV图像修补模型,形式如下:
上式同样受到噪声条件约束。
根据变分理论,无约束条件的极值问题更容易求解。因此,为将有约束条件的极值问题转化为无约束条件的极值问题,我们采用Lagrange数乘法,推得新的代价函数为:
根据计算函数极值的变分方法可知,求解能量泛函极值的问题可以归结为求解相应的Euler方程:
其中,F为二维函数,E为所求解的能量泛函。
当于取F=|▽u|,最终使得E达到最小的u应该满足条件:
这就是图像修补的整体变分模型。
3 多方向统一修补模型
上述两个模型的修补方法都是非线性扩散方法,其区别就在于扩散方向以及传导系数的取值方式。我们应考虑两个方向的修补,对图像先进行m次沿着ε方向的扩散,再进行n次沿着η方向的扩散,然后再重复这两个过程,直到图像变化不大为止。
因而,我们从两个方向分别选取修补模型:
3.1 ε方向的扩散
从基于BSCB修补模型出发,修补过程主要是收集信息并沿等照度线方向修补,扩散过程则是为了防止等照度线的交叉。修补过程可看作沿ε方向的信息扩散过程,而扩散过程采取非线性扩散方程:
上式中所有参数含义与BSCB修补模型公式式相同。上述公式实质上相当于沿着方向(垂直于梯度方向)的扩散。
3.2 η方向的扩散
从基于TV方法的模型出发,考虑到对修补速率以及修补效果的影响,直接使用TV模型完成ε方向的扩散。
综上所述,我们对ε方向和η方向交织扩散的多方向统一修补模型包括三个步骤:
1)对污损区进行“相关随机初始化”;
2)使用TV模型对图像进行m次n方向的扩散修补;
3)使用方向扩散对图像进行n次ε方向的扩散修补。
实际计算过程中,需注意以下事项:
1)m和n的次数可以根据需要选取
2)迭代阂值的设定
多方向统一修补模型的数值离散化方案:
它主要是基于方向扩散的一种离散化方案,根据方向扩散方程,代入参数值可得:
其中I为代修补图像,x、y为图像坐标。
采用中心差分进行离散化近似,根据时间t和空间x、y的一阶偏导数可得出相应二阶偏导数为:
以上各式中的Δx、Δy表示空域采样间隔。在图像处理中不失一般性可令Δx=Δy=1。于是,显式方案可表达为:
式中表示利用n层数据的中心差分求得的方向扩散公式右边在(i,j)网格点上的值。
4 实验结果
统一模型在文字去除、污损图片修补方面整体修补效果比较自然,但由于该模型使用扩散方程来实现,因此个别污损较大的区域也会存在模糊的痕迹。
下面我们比较对于同一污损图,使用的多方向统一修补模型和基于整体变分的TV修补模型在停止修补时的相关数据如表1。
由上表可以看出,在设定同一迭代停止条件(指数均方差条件)MSE=e0.0012的前提下,两种模型停止迭代时的修补次数相差不大,但统一模型用时较短。
另外,将两种模型分别对污损图进行50次修补的MSE值表示如图1。
图1中实线表示统一模型,虚线表示TV模型
可以看出,两个模型的MSE变化曲线有着如下规律:在修补开始的一段时间内,统一模型具有较大的MSE值,由于MSE衡量的是每两次修补结果之间的均方差异,表明该模型在这段时间内扩散速度较快,经过一段短暂的非稳定期后,前后两次修补结果之间的MSE越来越小,修补结果趋于稳定,而此时,TV模型对应的MSE也比较稳定,但其MSE值却比统一模型的MSE值大。可进一步得出结论:与TV模型相比,统一模型的修补效率较高。
5 结束语
本文提出的模型结合了方向扩散理论,综合了基于偏微分方程和整体变分方程模型的修补方法,具备了更高的修补效率和修补效果。不足之处在于修补污损区域较大时,容易造成模糊现象,因此下一步工作要在此模型基础上采用基于图像分解的修补技术,同时要多考虑其它方向上的相关性,比如45°,135°方向。从而在修补大范围污损区域时到达更好的效果。
参考文献
[1]Bertalmio M,SaPiro G,CasellesV,etal,lmage inPainting[C]//Proceedings of International Conference on ComPuter GraPhics and Interac-tive Techniques.NeOrleans,Luisiana,USA,2000:417-424.
[2]Rudin L,Osher S,Fatemi E,Nonlinear total variation based noise removal algorithms[J].Physica D,1992,60:259-268.
[3]Chan T F,Shen J H,Mathematical models for local non-exture inPainting[J].SIAM Journal of Applied Mathematics,2001,62(3):1019-1043.
[4]王大凯.图像处理中的偏微分方程方法[M].北京:科学出版社,2005,
[5]Perona P,Malik J.Scale一space and edge detection using anisotropic diffusion[J].IEEE PAMI,1990,12:629-639.
[6]Catte F,Lions P L,Morel J M,et al.Image selective smoothing and edge detection by nonlinear diffusion[J].SIAM J.Numer.Anal.,1992(29):182-193.
[7]Osher S,Sethian J.Fronts Propagating with curvature dependent speed:algorithms based on Hamilton-Jacobi for mulations[J].Joumal ofComputational Physies,1988,79:12-49.
[8]Marquina A,Osher S.Explicit algorithms for a new time dependent model based on level set motion for nonlinear debluring and noiseremoval[R].UCLA CAM Report99-5,1999.
[9]Sapiro G,Caselles V.Histogram modification via differential equations[J].Diff,Equat,1997,135:238-268.
[10]Caselles V.Shape一Preserving local contrast enhancement[J].IEEE IP,1999,8:220-230.