模板算法

模板算法（精选七篇）

模板算法 篇1

图像旋转、放大、缩小、几何失真校正等变换是常见的空域变换。空域变换会产生图像退化, 但与频域变换相比具有速度优势。图像旋转变换造成的退化给人的最直接视觉感受是图像变得模糊尤其边界处发生侵蚀。图像旋转变换包括几何变换和灰度值插值变换。灰度值插值算法有最近邻点插值、双线性插值、双三次插值[1]、高斯模板插值[2]等。它们对旋转后的图像质量和性能起决定性作用。最近邻插值的定位误差最大是半个像素。这种误差在物体具有直线边界时会显现出来, 在变换后可能会呈现阶梯状;双线性插值可能会引起小的分辨率降低和模糊, 原因在于其平均化的本性。它减轻了在最近邻插值中出现的阶梯状直线边界的问题;双三次插值免除了最近邻插值的阶梯状的问题, 也解决了线性插值的模糊问题。双三次插值很好地保持了图像的细节。但双线性插值和双三次插值的计算速度不能满足实时性需要, 尤其在实时性要求高的场合[3]。因而, 人们对插值算法对图像质量[4,5]和性能[6,7]的影响进行了广泛的研究。

模板通常用于图像滤波、平滑、锐化、图像匹配、边界检测、放缩等[8,9]。高斯模板插值也被用于图像旋转。用模板进行图像处理的一个优势在于其具有很高的性能。但高斯模板使图像产生严重的模糊, 因此本文设计了细粒度亚像素圆模板算法并将其用于图像旋转。该算法消除了模糊, 旋转后的图像质量接近双线性插值, 而具有明显的性能优势。

1图像旋转

图像旋转 (如图1所示) 一般采用逆向旋转获取像素值的方法, 可以避免目标图像产生空洞。即先由源图像区域Ω及其旋转角度θ确定目标图像的图像区域Ω′。对目标图像的每一个像素点P′ (x′, y′) 逆向几何旋转得到点P (x, y) , 如果点P (x, y) ∉Ω, 像素点P′ (x′, y′) 处的像素值C (x′, y′) 等于背景值;否则, 即点P (x, y) ∈Ω, 像素点P′ (x′, y′) 处的像素值可以选用各种灰度插值算法得到。因此灰度插值算法决定了旋转后图像的质量, 几何旋转算法和灰度插值算法的复杂度共同决定了算法的性能。

$\left[\begin{array}{l}x\\ y\end{array}\right]=\left[\begin{array}{l}\cos \theta \sin \theta \\ -\sin \theta \cos \theta \\ \end{array}\right]\left[\begin{array}{l}{x}^{\prime }\\ y^{\prime }\end{array}\right]$

像素点P′ (x′, y′) 和点P (x, y) 的坐标不可能同时取整, 也就是旋转前后的像素点的亮度不是一一对应的关系, 因此需要进行亮度插值。最近邻点插值算法图像连续性差, 但速度快;双线性插值图像连续性好, 但速度慢;高斯模板插值图像的模糊度高, 速度介于前两者之间。本文设计的算法性能和连续性好, 模糊度低。

2细粒度像素分割与亚像素圆模板

2.1细粒度像素分割

图2中, P1, P2, P3, P4, P6, P7, P8, P9是当前像素P5 (正方形ABCD) 的8邻域像素。P5被分割为5×5的子像素Si (i=1, …, 25) , 它们的中心是Oi (i=1, 2, …, 25) 。设像素的边长为1。

亚像素圆模板的几何形状是以子像素Si (i=1, 2, …, 25) 的中心点Oi (i=1, 2, …, 25) 为圆心, 以像素边长一半 (1/2) 为半径的圆, 其面积小于像素面积因而称为亚像素。细粒度是指对当前像素进行5×5分割得到5×5模板, 相对于3×3的模板称为细粒度。

局部相关性假设:设像素点P′ (x′, y′) 反向旋转后的点为P (x, y) 。像素点P′ (x′, y′) 的灰度值 (记为LF) 是以点P (x, y) 为中心的一个小邻域 (亚像素圆) 覆盖的各个像素面积与其灰度值乘积之和。LF要进行归一化处理, 即覆盖面积除以亚像素圆的面积。各像素的灰度值记为Pi (i=1, 2, …, 9) , 各像素被亚像素圆覆盖的面积分别记为Api (i=1, 2, …, 9) 。

对每一个子像素Si求得一个模板Ti, 当源像素点P (x, y) ∈子像素区域Si (i=1, 2, …, 25) 时, 就用相应的模板和卷积公式计算目的像素点P′ (x′, y′) 的灰度值LFi。

2.2求解细粒度亚像素圆模板

根据局部相关性假设求与每一个子像素Si相关的模板Ti和卷积公式。下面以子像素S1为例求说明求解T1和卷积公式 (LF) 的过程, 亚像素圆的面积:

AS=πR2=π (1/2) 2=0.785

以O1为圆心的亚像素圆 (记为圆O1) 与相关像素边的交点为N, K, L, M;圆O1覆盖像素P1, P2, P4, P5的面积分别记为Ap1, AP2, AP4, AP5。以点O1为坐标原点。圆O1的参数方程:

$\{\begin{array}{l}x=\frac{1}{2}\cos \theta \\ y=\frac{1}{2}\sin \theta \\ \end{array}$

;直线MDK方程:y=$\frac{1}{10}$;直线NDL方程:x=$-\frac{1}{10}$

设交点N, K, L, M的极坐标的角度记为Nθ, Kθ, Lθ, Mθ。

以上*表示卷积。

3实验结果与分析

3.1实验环境与结果

设备环境:Lenovo 昭阳E260 (Centrino 1.5GHz, 256M)

软件环境:MS Windows XP Professional, Visual C++6.0 企业版, 用函数ctime得到时间。

对原始图像图3 (a) 用不同的算法进行旋转, 旋转角度为15度, 连续旋转6次, 共90度。旋转的结果如图3 (b) 最近邻插值算法、 (c) 高斯模板算法、 (d) 双线性插值、 (e) 本文算法。为便于观察, 旋转后的图像反向旋转了90度, 90度的旋转不会使图像质量退化。

从旋转后的图像质量来看, 本文算法接近双线性插值, 明显优于最近邻插值算法和高斯模板算法。最近邻插值算法和高斯模板算法的字迹已经很难辨识。

从计算性能的比较来看, 如表1所示, 双线性插值算法计算时间是本文算法的1.45倍 (图3) 。最近邻插值算法计算最快, 本文算法的计算速度接近高斯模板算法。

3.2实验结果分析

各种算法计算量估计如表2所示。

最近邻插值算法只对坐标值进行简单的几何变换, 没有复杂的灰度插值计算, 因此性能最好。双线性插值:

f (x, y) =[f (1, 0) -f (0, 0) ]x+[f (0, 1) -f (0, 0) ]y+

[f (1, 1) +f (0, 0) -f (1, 0) -f (0, 1) ]xy+f (0, 0)

有4次浮点乘、3次浮点加和5次整数加运算。

高斯模板:

当tan (θ) <1

${\rm T}1=\frac{1}{14}\left[\begin{array}{ccc}1& 1& 1\\ 2& 4& 2\\ 1& 1& 1\end{array}\right]$

当tan (θ) =1

${\rm T}2=\frac{1}{16}\left[\begin{array}{ccc}1& 2& 1\\ 2& 4& 2\\ 1& 2& 1\end{array}\right]$

当tan (θ) >1

${\rm T}3=\frac{1}{14}\left[\begin{array}{ccc}1& 2& 1\\ 1& 4& 1\\ 1& 2& 1\end{array}\right]$

设T1, T2, T3使用的概率为P=1/3, 则整数加法的次数为: (8+8+8) /3=8次;整数乘为: (3+5+3) /3=11/3≈3.7次;整数除为: (1+1+1) /3=1次。

本文的算法, 设Ti (i=1, ……, 25) 的使用概率为P=1/25。则整数加法: (3+3+1+3+3+3+3+1+3+3+1+1+0+1+1+3+3+1+3+3+ 3+3+1+3+3) /25=56/25=2.24次。整数乘为:

(4+4+2+4+4+4+4+2+4+4+2+2+0+2+2+4+4+2+4+4+4+4+2+4+4) /25=80/25=16/5=3.2次。整数除为: (5+5+4+5+5) /25=24/25≈1次。

浮点乘法占用处理器的周期最多, 其次是浮点加法, 然后是整数除法、乘法, 最后是整数加法。高斯模板中的乘2i可用<<i代替, 除2i可用>>i代替, 可以使其整数乘法的速度比整数加法快。因此双线性插值计算复杂度最高。

假设本文算法每个模板加权平均的像素个数为Ni。本文算法的加权平均分三种情况: (1) 不平均 (T13) , N13=0; (2) 两个像素加权平均 (T3, T8, T11, T12, T14, T15, T18, T23) , N3=N8 =N11=N12= N14=N15=N18=N23=2; (3) 四个像素加权平均 (T1, T2, T4, T5, T6, T7, T9, T10, T16, T17, T19, T20, T21, T22, T24, T25) , N1=N2= N4=N5=N6=N7=N9=N10=N16=N17=N19=N20=N21=N22=N24=N25=4。假设每个模板的使用概率相同, 即, Pi=1/25。则E=${\displaystyle \sum _{i=1}^{25}{\rm N}}{}_i\times {\rm P}{}_i$= (2×8+4×16) /25=3.2, 即本文算法是对3.2个像素进行加权平均。因此, 本文算法不会产生明显的模糊。而高斯模板是9个像素进行加权平均, 会产生明显的模糊退化。

4结论

局部相关性假设确保了细粒度亚像素圆模板进行卷积运算时的连续性, 因此可以获得较好得图像质量。图像模糊的主要原因是邻域像素的加权平均造成的。本文的像素分割使得选取的邻域是4像素 (T1, T2, T4, T5等) 、2像素 (T3, T8, T11, T12等) 、1像素 (T13) , 是对3.2个像素进行加权平均, 因而清晰;而高斯模板是对9像素邻域加权平均, 因此造成图像模糊。实验表明, 本文算法的计算速度明显优于双线性插值。可以同时满足较高的实时性和较好的图像空域变换质量的要求。

摘要：旋转图像的质量和性能是需要权衡的一个问题, 提出一种细粒度亚像素圆模板算法。通过像素网格状5x5分割选取圆模板的圆心。邻域像素被圆模板覆盖的面积与圆面积的比值Rs, 相应像素的颜色值Cs, 旋转后像素的颜色值等于Rs和Cs的卷积。实验表明该算法图像旋转质量好于最近邻点插值和高斯模板算法, 清晰度和连续性接近双线性插值, 计算性能明显优于双线性插值。

关键词：细粒度,圆模板,像素分割,亚像素,高斯模板,图像旋转

参考文献

[1]Milazn Sonka, Vaclav Hlavac, Roger Boyle.图像处理、分析与机器视觉[M].人民邮电出版社, 2003, 9.

[2]张显全, 唐振军, 于金辉, 基于高斯模板的图像旋转算法[J].计算机工程与应用, 2005 (34) :79-81.

[3]刘松涛, 周晓东, 沈同圣.基于TMS320C6201的实时图像处理系统[J].计算机工程, 2005, 31 (7) :214-216.

[4]Xin Li.New edge-directed interpolation[J].IEEE transactions on im-age processing, 2001, 10 (10) :521-1527.

[5]Chen Chinghan, Hsieh Shenghsien.Anovel image interpolator based on probabilistic neural network with sharpness/smoothness adaptation[C].ISNN2005, LNCS3497, 2005:698-706.

[6]Uthaichana P, Leelarsmee E.A pipelined bilinear interpolation for real time video image expansion[C].Tencon2004.2004IEEE Region10Conference, Volume D, 2004:21-24.

[7]Grobbon K T, Bailey D G.A Novel Approach to Real-time Bilinear In-terpolation[C].Proceedings of the Second IEEE International Work-shop on Electronic Design, Test and Applications (DELTA’04) , 2004:126-131.

[8]黄翔东, 王兆华, 李文元.二维加窗全相位图像滤波模板的设计[J].中国图象图形学报, 2006, 11 (6) , 811-817, .

集成电路模板提取算法综述 篇2

随着集成电路制造技术的进步和应用需求的增长,整个系统现在已经可以集成在单个芯片之中,片上系统(system on a chip,SoC)已成为集成电路系统设计的重要形式和热点研究内容。然而,当前集成电路设计能力不足已成为制约集成电路工业进一步发展的重要因素。因此必须尽快改进设计方法,不断提高设计能力[12]。

传统的设计方法中忽略了系统描述本身所包含的结构特性。在以数据处理为主的应用描述中往往具有高度的规律性,存在着大量的相似结构,利用其规律性可以实现规则的布图以提高芯片的性能及可制造性。因此,如果能够将基于模板的技术用在集成电路的设计当中,分析和提取电路中相似结构以实现规则性的布图,那么芯片在性能和集成度方面将会有大大改善。

电路模板技术是指将电路中重复出现的子电路抽象出来作为模板,它在电路性能的提高、电路的验证、设计重用、电路划分等领域以及处理高层次综合领域中的调度和分配问题都具有重要的作用[12]。因此对集成电路的规则性提取问题的研究在VLSI自动化设计领域具有深远的意义。

此外,嵌入式多媒体应用程序的一个显著特点也是规则运算很多,运算时间复杂度很高,因此也迫切需要提高性能,降低功耗。

从输入数据流图(data-flow graph,DFG)中提取出图中频繁运用的子图集合或相似子图集合,通过后续模板覆盖、任务划分和调度阶段对原始DFG进行模板覆盖,将相似子程序调度到相同的PE阵列上去,这使得程序的调度更有效,最大可能地复用模块单元实现系统的功能,提高重用性,减少系统的面积。因此,基于模板的技术也是可重构系统任务编译器前端设计中一种较有效的方法。如果能在可重构系统的编译器当中使用模板技术,那么对系统的并行处理及逻辑优化等将会有很大帮助。

无论是对数据通路型集成电路还是对嵌入式多媒体应用程序进行规律性提取时,通常都是将电路的门级网表或者程序转化为对应的DFG表示。因此,本文主要讨论基于图论的模板提取。

2 问题定义

对于一个DFG,结点表示一个简单的操作(比如ADD,SUB等),有向边表示数据流的方向。设G(V,E)表示一个DFG,V为其顶点集,E为其边集,有如下定义。

定义1若图SG(SV,SE)满足SV∈V及SE∈E,则称SG是G子图[16]。

定义2对于G(V,E)中的两个子图G1(V1,E1),G2(V2,E2),如果V1和V2之间存在一一对应的映射关系f:V1→V2,对于vi,vj∈V1,∈E1当且仅当∈E2,并且与的重数相同,那么称G(V,E)的两个子图G1(V1,E1),G2(V2,E2)是同构的[16]。

定义3模板T就是DFG中频繁出现的子图结构,而与此模板结构相同的子图称为该模板的实例,这种子图的个数称为该模板的频数[13]。

定义4若SG(SV,SE)是G(V,E)的一个子图,将SV记为有序的结点集,则SV的第一个结点称为SV或子图SG的起点[12]。

定义5图G(V,E)的顶点平均度,记作

其中,deg(vi)为顶点vi的度,表示与vi相邻顶点的个数[11]。

3 现有模板提取算法分析

目前,国外有些学者提出了一些模板提取的算法,并取得了一定的研究成果,国内研究尚处于初级阶段。下面对一些典型的模板提取算法的思想作一下介绍。

3.1 模板提取算法

3.1.1 TREE和SPOG算法[8]

由Chowdhary等人提出的TREE算法能够提取出单输出和内部没有汇聚的模板。而且其通过两个假设(假设1:把图G的子图集S限制在只包括某些子图,这些子图满足不再是S中任一图的子图,且在S中其频数大于1。假设2:对于G中每一个有入边的结点v,假设其有f条入边,前驱结点分别为u1,u2…uf,每一条边都被赋予一个唯一的索引号,k[ui,v]=i,1≤i≤f)将树形模板的数量减少到v(v-1)/2。算法的基本思想如下:

1)对G的所有结点进行拓扑排序v1,v2…vn。

2)对于任意两个编号的结点vi,vj(1≤i,j≤n),生成以这两个结点为根的功能上相同的最大子图作为一个模板Sm。

3)判断模板库中是否存在于Sm功能上等价的模板。如果不存在,将Sm加入到模板库当中;否则,舍弃Sm。

SPOG算法则是在TREE算法基础上的扩展和改进,将生成的模板扩展到多输出模板。此时SPOG子图的数量可以被限制在v(v-1)。

TREE算法和SPOG算法是典型的模板提取算法,它能够提取出基于两个假设以及各自限制条件之内的所有模板,这对于后续的模板覆盖有很大的帮助,覆盖率较高。但同时此算法也有着很大的不足之处,都适用于分散图,且生成的模板限制在tree形或spog形,算法的复杂度也很高,为O(v5),不适合实际工程的需要。

3.1.2 FAN算法[15]

潘伟涛等人提出的FAN算法通过边权值编码,先生成小规模模板,然后再逐级扩展生成较大规模模板,产生扇形频繁子电路。算法的基本思想如下:

1)统计电路中每种标准单元出现的频率。依据最小支持度确定为各标准单元作标记还是删除它,并计算所有顶点的有效输入权值。

2)搜索所有同构实例,对于每一个同构实例在最左顶点扩展一条边。

3)统计扩展后的扇形子电路的种类和频数。依据最小支持度确定将此子电路标记为模板并进行下一轮的扩展还是将它删除。

FAN算法采用最小支持度对每次扩展生成的子图进行限制,通过比较子电路的出现的频数,有效地避免了子图扩展时一些不必要的冗余扩展,并且此算法采用逐级扩大规模的方法,得到的模板层次化较强,可以对电路进行更好的覆盖实用性较强。

3.1.3 其他算法

Rao and Kurdahi[3]最早关注于数据通路型集成电路的模板提取,它将基于模板的聚类思想应用到数据通路的综合上,这里的模板提取过程也就是基于不同子图(它们可以被复制来覆盖整个DFG)的识别过程。文献[4]在解决模板提取问题时,假设子模块已经生成,主要解决子模块分类问题,但是一般情况下需要自动生成模块。文献[5-6]提出了一些模块生成算法,但均是先选择某一顶点作为一个模块,然后在此模块内不断加入其它的顶点形成新的模块。这几种算法对模块的形式没有限制,但也有其固有的缺点,就是所生成的模块形式依赖于起始模块的选择。文献[11]提出了一种基于顶点的辐射路特征的门级到功能模块级的快速子电路提取算法,解决了宏单元模板自动匹配,通过单个顶点的相似度特征,将子图同构问题转化为顶点之间的匹配问题,算法最差时间复杂度为(其中,n和k为两图结点数,d为原始电路的直径)。文献[12]中算法对DFG的整体结构以及模块的结构没有要求,增强了算法的健壮性,而且生成的模板的层次化较强,模板覆盖率较高,但在同构判断时无针对性,需对所有模板进行一一判断,导致程序复杂性的提高。

3.2 模板提取算法的比较与分析

模板提取算法有以下一些重要性质:1)输入DFG的类型,如连通图、有向图和无环图等;2)遍历策略,如深度优先或者广度优先等;3)候选子图的产生策略,如逐级扩展还是其他;4)对重复图的消除策略,如主动地或被动地;5)生成模板的层次化,如较好或较差。表1详细列出了一些模板提取算法的重要性质,并进行了比较。

4 总结和展望

随着集成电路产业的发展,迫切地需要提高芯片的性能,而利用集成电路自身的规律性可以实现规则的布图。因此,基于模板的技术将会对提高芯片的性能及可制造性有很大的帮助。本文归纳了基于图论的模板提取的各种算法,目前在这方面的研究已经取得了很大成绩,并被应用到一些实际的系统中。本文重点介绍了TREE、SPOG和FAN等典型的模板提取算法,并对其他算法进行了简要介绍。归纳出模板提取算法的一些重要性质,并对现有各算法进行了比较。

虽然目前存在的算法较多,且执行效率较高,但我们觉得还可以在以下方面加以改进或做进一步的研究:

1)现实生活中有各种各样的图形:有向图,无向图,加权图,无连通图等,但目前的算法大部分都是针对连通图的提取,对加权图有环图等的提取算法很少,因此对加权图有环图等的提取算法的研究也是一个重要的研究方向。

2)现有方法优势还主要集中在对小规模集成电路的提取上,集成电路产业的发展要求我们能够对大规模甚至超大规模集成电路进行提取,因此需要研究大规模集成电路的提取方法。

3)模板提取评测方法的研究。目前主要是靠算法复杂度的评估以及模板覆盖率等,在模板覆盖阶段,现有最大模板优先和最频繁模板优先的方法,但这样不能达到对系统最好覆盖,因此我们应该考虑如何在模板的规模和频数之间进行权衡,以利用所提取的模板达到对系统的最完美覆盖,最大程度地减小系统面积开销。

摘要：数据通路型集成电路中存在着高度的规律性,利用其规律性可以实现规则的布图以提高芯片的性能。该文介绍了基于图论的集成电路模板提取算法的研究进展情况,给出了TREE、SPOG和FAN等典型模板提取算法的思想,综合分析了各算法的优缺点及其适用情况,总结并比较了模板提取算法的一些重要性质,并对未来模板提取技术作了一下展望。

特征模板图像的提取算法及实现 篇3

在基于结构光的三维视觉重建系统中, 除了实现结构光边缘图像的提取外, 还要实现模板图像中标定圆重心的提取, 待处理的模板图像见图1。图像中圆、椭圆等中心对称目标进行定位的常用方法有形心法和灰度重心法。这两种算法只对灰度对称分布的目标效果理想, 当目标平面和摄像机光轴有较大夹角时, 目标的重心会发生偏移, 对图像二值化后使用形心法或者用灰灰度重心法将产生较大误差。本文中模板图像标定圆重心的提取用到是一种中心对称目标的定位算法-物理重心法[1]。

2 物理重心定位算法

程序需要实现的任务是提取模板图像上一定数量圆点的圆心坐标 (实为重心) 。根据物理上重心的概念, 中心对称图形圆的重心表示如下:

3 模板图像中标定圆重心提取的实现

特征提取, 即需要通过数字图像处理手段, 获取图像上特征点的坐标值。我们将整个提取过程划分成搜索的初始值输入、数据提取、数据输出三个主要模块。

3.1 搜索的初始值输入

通过手工的鼠标点选, 可以缩小搜索范围, 加快特征提取的速度。利用MATLAB提供了一个ginput函数[2], 调用该函数用于获取鼠标点击位置对应的二维坐标, 就可以得到搜索的初始值。

3.2 数据提取

数据处理过程主要为对输入的图像进行滤波去噪处理[3], 然后转换成二值图像, 调用重心搜索函数来实现特征提取, 这个模块通过调用独立的脚本或函数分别实现模块的功能。

3.3 数据输出

这个模块主要实现两个功能:首先分别在独立的窗口中显示已经提取了特征点的图像;其次, 由于要将提取的特征点坐标用于进一步的标定样本数据的生成, 因此考虑将每幅图像的二维坐标值导入到文本文件中, 便于之后的使用。

4 程序实现流程

程序实现流程详见图2, 程序可以选择对载入图像进行圆心的提取, 也可以选择其中的几幅进行处理。由用户在模板图像上用鼠标点击可以构成一个正四边形的四个圆心 (见图3) , 得到四个圆心坐标的初始值, 以此位置为中心, 根据灰度值的变化情况在其领域内调用一个centerfinder函数搜寻圆心的精确坐标值, 然后计算透视投影矩阵, 再根据模板的世界坐标计算出模板圆心的图像坐标, 以此为初值, 利用数字图像技术寻找模板图像上点选范围内所有圆点圆心的精确坐标值。

圆心的提取结果如图所示, 其中图3所示即用鼠标手工点选以及根据输入的每条边上的圆点数目, 获得点选的正四边形范围内所有圆点重心的大致位置。图4所示即调用重心搜索函数后取得的这些圆点重心更精确的二维坐标。

提取得到的图像坐标数据和世界坐标数据按照阵列的形式存放在文本文件中, 通过后期数据处理得到的标定样本数据, 并用此样本数据来训练所建立的神经网络[4]视觉检测模型。训练的结果发现模型收敛速度较快, 说明通过以上方法获取的模板图像圆心提取的算法有较高的精度和抗干扰能力

摘要：本文通过使用MATLAB工具, 来实现特征图像圆心坐标数据的提取, 检验了一种中心对称图像的重心检测算法。

关键词：模板图像,数据提取,检测算法

参考文献

[1]张浩翼, 曾德山, 邢渊.反向工程中三维光学测量系统参考点的设计和图像处理识别技术研究[J].模具工业, 2004, Vol.279 (5) :43-46

[2]张志涌等.精通MATLAB6.5版[M].北京:北京航空航天大学出版社, 2003, 36-39

[3]李辉, 蒋秀明, 高殿斌等.Matlab语言在数字图像中值滤波中的应用研究[J].天津工业大学学报, 2003, 22 (1) :87-88

基于模板的图割立体匹配算法 篇4

近些年来, 已有越来越多的立体匹配算法涌现出来, 这些算法的基本构架是:在基元相似的条件下, 找到一种约束的匹配规则进行最优搜索, 并且保证这种搜索能最终找到近似的最优解。但是立体匹配问题的解决本身就存在着模糊性, 比如:噪声干扰、弱纹理区域、遮挡区域、重复纹理区域和深度不连续性。

立体匹配的算法性能依赖于三个因素:准确的匹配基元、与基元相对应的匹配准则、构建能够准确匹配所选基元的稳定算法[1]。

2001年, Tao et al.提出了一个基于色彩分割的立体匹配算法的框架[2], 该框架建立在一种重要的假设之上, 即:实现分割的区域之内是没有较大视差变化的。其主要思想是:如果假设的视差值是正确的, 则根据这个视差值将参考图像变换到另外一个视角, 即匹配图像中, 使其呈现出能够与匹配图像相匹配的效果。因为, 立体匹配问题就是通过最小化全局图像的能量函数而得到解决的。图像的色彩分割表示法旨在减少解决问题的步骤, 且可以强化区域内的视差的平滑性约束。通过邻近视差值假设的方法提出的贪婪区域的搜索机制进一步缩减卷积代价、为不匹配区域找到更好的视差值。

Boykov et al.和Kolmogorov连同Zabin提出了基于Graph cuts的立体匹配算法[3,4], 以找到与观察到的数据相一致的光滑视差图像。在其提出的算法中, 立体匹配问题可等价为一个能量最小化的问题, 能量方程中通常包含:

(1) 衡量在相邻像素对之间视差值平滑性的平滑项Es;

(2) 衡量给予像素的标签不一致性的数据项Ed。

找到能量方程后, 就可以据此方程建立一个带权图, 在这个图中, 结点代表像素, 图的标签集或者是说终点与所有可能的视差值 (或者是视差范围区间内的任何一个具体值) 且图中的边的权值与已经定义好的能量方程中的项相一致。Graph cuts算法机制可以得到近似的优化解, 这个优化解就是将视差值 (标签) 分配到对应的像素 (图中的结点) 上。

综合基于色彩的分割算法和Graph cuts的思想, 本文提出了基于模板的图割立体匹配算法 (TGC) 。在TGC算法中, 参考图像可分割为不重叠、无交集的一个个的图像部分, 而要找到一个假设的视差值的集合, 场景结构则近似地等价为视差空间内的平面集合, 且这些平面不必是相互平行的。那么立体匹配算法就成为将视差空间中的平面与分割后的参考图像的部分相匹配的问题, 这样做的目的是因为在分割后的小区域内建立能量评价函数更为容易。

TGC使用与Boykov et al.论文中Graph cuts类似的方式来找到能量方程的近似最优解, 但是在建立图像时图像中的结点代表的是分割后的图像部分而非像素点。所以, 在大多数立体匹配处理的图像中, 图像分割后的部分数是远远少于像素点数的, 这就直接使建立得到的图像简单且会有更快的计算速度。另外, 跟Birchfiel和Tomasi提出的算法思想类似[5], TGC使用平滑视差项代表被加强了分段连续性的视差连续的区域, 但是遮挡区域通常会在合并之后进行处理, 并且是在分割部分的区域内建立图像, 正因为此, 将降低Graph cuts阶段的计算的复杂度。

1 参考图像的分割

TGC则建立于如下假设上:立体匹配算法处理的图片的大的视差的不连续仅仅会在分割后的部分与部分之间的边界处。严格地将视差连续性加强在区域内, 次分割部分由于在分割后的部分与部分之间的平滑性约束 (定义为能量方程中的Esmoth项) 在很大程度上被容忍。

2 视差平面估计

TGC使用一个视差连续的表面表示场景结构, 近似地可以认为每一个表面均是一个平面, 而不是不规则的曲面, 但是这种平面是可以想象为任何复杂的曲面的。当然, 这种近似的平面也会使得在计算时, 视差的准确度相应地有所降低。但是这种近似使得模型得到简化, 同时也能够应用于更多的领域, 如:视觉合成、三维重建等。在这个部分中, 使用下面的步骤估计场景中的视差平面。首先, 使用区域立体匹配的规则找到初始的粗糙视差值。其后, 为每一个分割后得到的模板找到表示模板函数的内部参数, 在这里计算时, 将跳过分割得到的太小的模板。最后, 在得到的模板参数描述的基础上, 对相似模板通过拟合操作, 以进一步减少模板数目, 并且在下一部分使用Graph cuts算法而建立了简单图, 由此达到提高算法效率的目的。

2.1 像素级的区域匹配

在标准的立体匹配研究中, 所有的立体匹配图像都是已经完成对极处理的。因此, 一对匹配点, 若在参考图像I中的点 (x, y) , 其匹配点在匹配图像中I'中为 (x', y') , 自然可以得到公式 (1) :

这里的视差d (x, y) 是来自视差区域[dmin, dmax]中任何一个具体值[6]。在TGC算法中, 使用c (x, y, d) 表示参考图像I中的点 (x, y) 与视差值d的匹配代价。在算法实现过程中, 使用了大小为3×3的窗口, 计算所有像素的平均像素强度差, 具体如公式 (2) 所示:

对于所有的可能的视差值, 均需计算其匹配代价, 最后, 得到的最小的匹配代价对应的视差值d即为该像素点处的视差值, 可记为d^ (x, y) 。

2.2 从单一的模板中拟合出初始视差平面

在Tao等的文章中已经将如何从单一模板的初始视差中拟合得到视差平面的算法给出了框架。在此部分中, 就使用了这样的算法框架。首先, 对于分割得到的模板使用一个视差平面来代表整个模板中的连续视差, 这个视差平面可以使用公式 (3) 来表示:

式 (3) 中, [a, b, c]表示视差平面的参数, 而d则表示像素点 (x, y) 的相应视差。文中使用最小二乘法即可以求得这个线性方程的解[a, b, c], 如公式 (4) 所示:

在这个线性方程中, 矩阵A中的第i行为[xi, yi, 1], 其含义表明为某一像素, 在以列向量表示的矩阵B中, 对应着该像素的就是第i列像素值即d (xi, yi) 。

在对初始视差模板拟合之后, 使用迭代的步骤来更新模板。在每一次迭代中, 像素视差的改变是在已经拟合的初始视差平面的一定的范围之内, 且得到的视差平面的拟合参数也是随之而相应变化的[7]。

TGC加入了一些机制增加视差模板的拟合算法的鲁棒性。分析如下:

(1) 公式 (4) 中线性方程的解可能由于计算得到不可靠视差的像素点 (这样的点称为离群点) 而存在着偏差, 因此在TGC算法中, 只是使用在初始视差计算中得到的可靠视差的像素点。离群点是通过Realtime算法中使用的交叉验证流程检测出来的。假设匹配图像中的一点 (x', y') 在初始视差值d^ (x, y) 的基础上与参考图像中的点 (x, y) 相匹配, 并且定义d^' (x', y') 作为匹配图像中像素点 (x', y') 的视差值, 如果这两个视差值满足公式 (5) , 即认为是离群点。

(2) 考虑到最小二乘法可以应用到迭代过程中, 该拟合的视差平面则是由公式 (4) 计算得到的。在公式 (4) 中, 每个方程的权值均是根据估计模板的像素初始视差值的最接近的数值而得到的。例如:w (βi) =e-2*βi, 其中, βi=|c1xi+c2yi+c3-d^ (x, y) |。这里模板参数多是随着权值的变化而发生变动的。

(3) 在算法中, 分割后非常小的模板即忽略掉, 因为在这种小的模板中不能提供足够多的可靠点来支持计算。

从分割后的模板计算出的视差平面, 只是在已有的视差平面集合中没有与此平面相似的平面的时候, 才将这一新的平面放进该集合中。所以, 通常情况下, 在算法中平面集合中的视差平面的个数要比分割后的模板数少得多。

2.3 从多个分割的模板中重新拟合平面

在这个步骤中, 目的并不是找到对应于每个分割模板的最好的视差平面, 而是在这个图像中找到尽可能多的视差平面。因此, 能够在一个场景结构中准确地提取出一个视差平面的集合即是算法的关键。但是在这一步骤中的从多个分割的模板中重新拟合的视差平面就可以解决这个问题。原因在于:正象上面提到的那样, 一些小的未被处理到的分割模板在此一步骤中得到了拼接, 由此能够提供足够的可靠点, 从而可以加入到线性方程 (4) 中。实施的步骤如下所示:

(1) 为视差平面集合中的每一个平面计算出模板的匹配代价;

(2) 为每一个分割后的模板分配一个能使其匹配代价达到最小的那个视差平面的值;

(3) 近邻的分割模板之间如果不能确定使用哪一个视差平面的情况下, 即使用一个可以确定的模板的对应的视差平面来标定这些模板;

(4) 在每一次多个分割的模板中应用视差平面模板的拟合方法。

步骤 (2) 、 (3) 、 (4) 是要重复进行的。当运行完成之后, 就需要衡量分割的模板与对应的视差平面的匹配代价。很自然, 最简单的方法就是将每个分割的模板中的各个像素的匹配代价加和, 如公式6所示:

式中, S代表分割后的模板, P代表视差平面之一, d=c1Px+c2Py+c3P, 其中的c1P、c2P、c3P是视差平面P的参数。

但是, 在这个部分的算法处理中, 仍有几个问题需要探讨。首先, 遮挡区域的像素会很容易误导分割模板的匹配代价, 尤其是遮挡区域占据了一个模板的大部分或者遮挡区域存在于一个光滑且低纹理的区域的情况下;第二, 在一个区域中累积每个像素的匹配视差可以解决匹配的模糊性, 虽然并未获得真正解决, 尤其是在低纹理区域[8]。

鉴于以上的问题, TGC提出了对算法的一些补充。首先, 在计算分割后的模板的匹配代价时, 排除所有可能的被遮挡的像素。第二, 在算法中通过不支持视差平面的像素百分比增加像素匹配代价的和。

在算法的更多细节中, 仅仅将纹理区域的离群点视为最为可能遮挡像素。在这里重新定义带有不可靠估计的初始视差值的像素为离群点, 这些离群点可以通过交叉验证的方法检测出来。简单地可以看到, 在文中的定义下遮挡像素就是离群点。将光滑的低纹理区域的离群点不再视为遮挡像素的原因有两个:

(1) 光滑的低纹理区域像素往往会在交叉验证方法中失效, 这就造成了匹配的歧义性, 而不是遮挡现象;

(2) 遮挡现象通常发生在图像中物体的边缘, 而在这些边缘的区域则是高纹理的。

在TGC中, 所有的非遮挡像素中, 确认某个像素是支持其对应视差平面的, 仅仅当该像素的最初估计视差是在这个视差平面的所有视差值的范围内的。否则, 即认为该像素是不支持该视差模板的。

在一个分割后的模板S中, 假设n表示其中的非遮挡的像素点的个数, 且s表明的是分割后的模板S相对于视差平面P的支持像素点的个数。分割后的模板的匹配代价记为公式 (7) :

此处, O表示在分割后的模板S中的遮挡部分。

可以看到, 匹配代价方程由两个部分组成的:

(1) 前述公式 (6) 定义的一个非遮挡像素点的匹配代价的加和;

(2) 随着在分割模板中不支持视差平面的像素百分比的增长而增长的一个指数函数。

显然, 这里定义的匹配代价函数对于那些有越低的加和以及越大面积的支持像素区域是有利的。因此定义的匹配代价的公式对于处理低纹理的图像尤其有用。正像在一整幅图像分割后的所有模板中, 而公式的第一部分将会与所有的视差平面相比较, 如此比较的结果就是对于那些有着很高的支持像素百分比的视差平面更为有利, 而这一结果正是减少了歧义性。对于高纹理的区域, 公式 (7) 中的第一部分正是可以在众多的视差平面中区分出匹配该分割模板的最佳视差平面;而公式中的第二部分的作用则是拉大匹配代价之间的差别, 因为可以正确匹配该分割后的模板的视差平面将会有更大的支持像素百分比。

3 使用Graph cut的方法为视差平面分配标签

TGC算法的这一部分将详细描述基于模板的立体匹配算法作为能量最小化的问题解决时的形式化以及应对方式, 也就是对每一个分割后的模板通过Graph cuts算法为其分配一个视差平面作为标签。

设R为一个参考图像分割之后的模板的集合, D是估计的视差平面的集合。此处算法的目的就是找到一个标签映射函数f, 这个函数使得R中的每一个模板都能在D中找到一个匹配的视差平面, 函数f是分段光滑且是与观测到的数据一致。在分割后的模板中, 将这个函数f建立起来, 并使用能量最小化方法加以解决, 如公式 (8) 所示:

式 (8) 中, Edata是一个包含着匹配到分割模板上的视差平面和模板之间的与数据相关的能量项, 具体如公式 (9) 所示:

式中, C (S, f (S) ) 使用的是公式 (7) 的定义。

式 (8) 中, Esmooth (f) 项通过惩罚分割模板与视差平面之间的不一致性, 而加强得到视差的平滑性。如:假如将不同的视差平面分配到相邻的分割模板中, 就要在这一项上添加更多的惩罚项。光滑项Esmooth (f) 如公式 (10) 所示:

式中, S与S'是相邻的分割模板, uS, S'则与相邻模板S与S'的共同边界的长度成正比, δ (f (S) ≠f (S') ) 是一个二值函数, 如果f (S) ≠f (S') , 则其值为1, 否则为0。

总体上, 要找到公式 (8) 的最小值是很难的。但是, 近来提出了几种基于图割的算法能够有效解决某种能量最小化的问题。在光滑项Esmooth中体现的不一致性是一个Potts模型, 如:任何一对标签之间的视差会被惩罚而与标签之间的不同的程度是无关的。首先建立一个图G, 而后应用Graph cuts找到能量方程的近似全局最小[9]。在TGC中, 建立得到的图像中的结点表示了分割的模板而不是像素点本身, 且标签集是由所有估计的视差平面组成的而不是视差序列所有可能的具体视差值。算法步骤如下:

(1) 算法是始于随机的标签f;

(2) 使success:=0;

(3) 选择一个视差平面中的一个随机序列P∈D

(a) 在所有f'找到在f的α-expansion使f^=argmin E (f') ;

(b) 如果E (f^)

(4) 如果success==1转回2) ;

(5) 否则返回f。

经过实验, 该算法通常在2~3次迭代之后, 就会收敛。

4 实验结果及分析

TGC算法是在CPU为Intel (R) Core (TM) 2 Duo 2.10GHz的PC机上实现并运行的, 操作系统为Windows XP, 编程工具为VC++6.0和Matlab。选取Middlebury图片库中的经典图片, Tsukuba、Sawtooth、Venus和Map, 作为测试数据, 这4幅图片可以代表立体匹配问题中的四种典型背景[10], 如图1所示。

图1显示了实验中使用的图片、视差的ground truth和最终得到的视差图像, 其中第一列是原始图像, 第二列是使用TGC算法得到的视差图像, 第三列是对应于原始图像的ground truth。在每个实验的图片中可以明显地看到, 使用TGC算法最终得到的视差图像能给出比标准视差图像更多的原始图像中的信息。

该算法定性的结果体现在图1中, 定量的结果呈现在表2中。表2中是将本部分的算法与其他五种常用算法 (WTA、Realtime、DP、SA、GC) 在PBM值和运行时间进行了比较。各算法的运行参数如表1所示。

由表2可以看出, 本文提出的TGC算法无论在PBM值还是运行时间上都取得了较好的结果。

5 结束语

立体匹配是计算机视觉研究领域最为活跃的一个热点问题, 并且立体匹配在三维重建、视觉组合等领域也是一个重要步骤。但由于立体匹配本身是NP难问题, 使得最终获得准确的视差值就一直成为极富挑战性的工作, 尤其是在低纹理区域、视差不连续的区域和遮挡区域等这些特殊区域内。本文综合基于色彩的分割算法和graph cuts的思想, 提出了一种新的基于模板思想的立体匹配算法。实验结果表明该算法取得了较好的效果, 为立体匹配领域的实际应用和后续算法的研发提供了有益参考。

参考文献

[1]SCHARSTEIN D, SZELISKI R.A taxonomy and evaluation of dense two_frame stereo correspondence algorithms[J].IJCV, 2002, 47 (1) :7-12.

[2]TAO H, SAWHNEY H S, KUMAR R.A global matching framework for stereo computation[C]//ICCV, 2001:532-539.

[3]BOYKOV Y, VEKSLER O, ZABIH R.Fast approximate energy minimization via graph cuts.IEEE Trans, 2001, PAM I223 (11) :1222-1239.

[4]KOLMOGDROV V, ZABIN R.Computing visual correspondence with occlusion using Graph cuts[C]∥Proc.Int’l conf.Computer Vision2001.

[5]BIRCHFIELD S, TOMASI C.Multiway cut for stereo and motion with slanted surfaces[C]//Proc.Int’l conf.Computer Vision, 2001:489-495.

[6]SZEISKI R, GOUNEL P.Stereo matching with transparency and matting[J].IJCV, 32 (1) :45-61.

[7]GENNERY D.Modeling the environment of an exploring vehicle by means of stereo vision[D].Stanford:Stanford University, 1980.

[8]KUTULAKOS K, SEITZ S.A theory of shape by space carving[J].IJCV, 38 (3) :199-218.

[9]SEITZ S, DYER C.Photorealistic scene reconstruction by voxel coloring[J].IJCV, 35 (2) :151-173.

模板算法 篇5

在视频压缩编码中,时域冗余主要通过运动估计和运动补偿来消除,它也是整个编码器比较耗时的部分。针对运动估计最先提出的全搜索算法[1]:在参考帧预先定义好的搜索区域中,将当前帧与搜索区域中所有的候选块进行比较,最小匹配误差的块为最优块。全搜索法(FS)能够获得非常高的搜索精度,但运算量十分巨大,之后的运动搜索算法都以在不影响精度的同时减少计算量为目标。三步搜索法(TSS)、两维对数法(LOGS)、十字型搜索法(CS)、四步搜索法(FSS)、梯度下降法(BBGDS)[2]、钻石搜索法(DS)[3]和六边形搜索法(HEXBS)[4]等的搜索速度比全搜索有了提高,但它们没有充分考虑时间和空间上相邻块的信息,搜索时容易陷入局部最小值,从而导致匹配精度差。之后提出的运动估计算法主要集中于以下几个方面:充分考虑时间和空间上的相邻宏块信息,针对视频中静止宏块较多的情况提出自适应提前终止策略,改变搜索模板,根据初始预测运动矢量自适应修改搜索区域大小等。例如MPEG-4标准第7部分已经采用的MV-FAST[5]和改进算法PMVFAST[6]。

基于上述研究,H.264标准采用了UMHexagon S算法[7],该算法能同时适应小运动和大运动情况下的运动估计,并能得到与全搜索基本一样的精度和率失真特性,同时最多能比全搜索节省90%的时间。因此,H.264/AVC标准采纳了该运动估计算法。文献[8]中UMHexagon S算法改变了搜索模板,一定程度上减少了运动估计时间。

2 UMHexagon S算法

非对称十字型多层次六边形格点搜索算法(UMH-exagon S)搜索步骤[1]如下:

1)初始搜索点预测。取对应费用函数最小的点为初始搜索点(预测搜索法包括针对空间相关性的中值预测、上层预测、前一帧对应块预测和邻近参考帧预测),然后判断是否提前截止。

2)非对称十字型搜索。由于一般物体水平方向运动要比垂直方向运动剧烈,所以将垂直方向设置为水平方向搜索范围的一半,判断是否提前终止搜索。

3)非均匀多层次六边形格点搜索分步进行5×5小矩形窗全搜索和扩展的多层次六边形格点搜索,同时也要判断是否提前终止搜索。

4)采用扩展多层次六边形格点搜索和小菱形搜索模式循环进行搜索,持续搜索到最小费用函数值的点位于菱形搜索窗口的中心点为止。

该算法充分考虑了空间和时间的相关性以及H.264采用的宏块划分技术中不同尺寸块的运动矢量相关性,进行初始点预测,针对运动幅度的大小采用自适应的六边形格点搜索和菱形搜索,具有很强的内容适应性,同时应用提前终止策略避免了不必要的运算,这些都取得了很好的效果。

3 改进UMHexagon S算法

要保证同样的编码效果,同时进一步减小UMHexagon S算法的运算量,笔者提出了改进方法,主要使初始运动矢量更准确,减少5×5全搜索点数,通过精确的运动矢量确定搜索方向并改用扩展的梯形格点进行搜索。

3.1 初始运动矢量改进

在原算法4种初始搜索点预测模式基础上提出第5种预测模式:当前块的左、上、右上块的运动矢量分别为MV1,MV2,MV3,参考帧同位置块的运动矢量为MV1′,MV2′,MV3′。

1)中值预测。PMV1=mediam(MV1,MV2,MV3),PMV2=mediam(MV1′,MV2′,MV3′),取两者中的最小SAD作为初始MV。

2)PMV=mediam(MV1,MV2,MV3,MV′1,MV′2,MV′3)。

3)Weighted预测。PMV1=0.375(MV1+MV2)+0.25MV3,PMV2=0.375(MV1′+MV2′)+0.25MV3′,取两者中的最小SAD做为初始MV。

对上述3种方法进行实验测试证明第3种方法比较好,则本算法采用Weighted预测。

3.2 5×5全搜索改进

5×5模式因为采用了全搜索模式,所以需要计算25个搜索点,运算量相对较大。在文献[8]中,笔者对常用视频序列的运动矢量做了详细的统计分析,发现运动矢量大部分落于[-2,2]区域中,且以不同比例集中分布在中心附近的特定区域内。如图1所示,有大约81.8%的运动矢量分布在中心附近范围±2的正方形区域内(25个点),大约77.52%的运动矢量分布在中心附近范围±2的菱形区域内(13个点),大约74.76%的运动矢量集中分布在中心附近范围±2的十字形区域内(9个点),而且匹配点在中心点的概率最高,其次为中心点上、下、左、右4个点,而在周围右上、左上、右下、左下对角点概率相对较小。本算法参考以上研究结果,在基本保持搜索精度的情况下,通过采用六边形、八边形或大小菱形相结合等方法进行比较实验测试后共采用17个点(如图2中的小三角形)代替5×5全搜索(如图2中的小三角形和小圆点)模式25个点,减少了32%的运算量。

3.3 六边形格点搜索改进

首先根据3.1节中得到的最优初始运动矢量(MVx,MVy)计算Mv Ratio=MVx/MVy,根据Mv Ratio判断运动矢量所在的区域,采用可变搜索模板进行搜索从而减少搜索点。比如(MVx,MVy)=(1,2),则Mv Ratio=0.5,用不断扩大搜索模板搜索第1,2象限;(MVx,MVy)=(-2,1),则用不断扩大的搜索模板搜索第2,3象限。在进行搜索模板的选择时,对半六边形、三角形、梯形和矩形等模板进行实验测试,在考虑搜索精度和时间的情况下,最终选择梯形模板。非对称六边形要搜索16个点,而本算法的梯形只需搜索7个点,在保证搜索质量的同时能减少56.25%的运算量。图3为改进UMHexagon S算法的搜索步骤。

4 实验结果与分析

为了验证改进UMHexagon S算法的有效性,采用JVT参考软件JM8.6进行仿真实验。实验采用不同运动类型的标准视频序列bus_cif,mobile_cif,flower_cif,stefan_cif,foreman_cif,coastguard_cif等作为测试序列。表1是本实验采用的JM代码的编码控制参数。

本实验分别采用标准算法和改进算法对不同视频序列的前28帧进行编码。表2给出了两种方法的运动估计总耗时并进行比较,表3给出了两种算法的亮度平均峰值信噪比。从两表中可以看出,采用改进算法的PSNR基本不变,在保持图像质量的同时有效降低了运动估计时间,对运动很缓慢的序列效果提高不大,但对剧烈运动序列效果很明显。表4给出了两种算法的平均比特率的比较,可以看出改进算法经过视频编码后的比特数有极其微小的增加。综上所述,改进算法在降低运动估计时间的同时非常好地保持了原算法的率失真性能,码率基本不变,对图像质量没有影响。

5 小结

笔者对运动估计经典算法和H.264采用的UMHexagon S算法进行了简单的分析,并提出了一种改进算法。该算法同时考虑了视频序列的时域和空域的相关性,使初始运动矢量预测更准确,减少5×5全搜索中的相对不重要搜索点和运算量,根据初始运动矢量的方向使用可变方向的梯形模型搜索,加快搜索速度。在不影响搜索精度,码率基本不变的情况下大幅减少运动估计的运算量,取得了很好的效果。

摘要：对UMHexagonS算法的搜索步骤和特点进行了分析,提出了一种改进的方法,改进初始运动矢量预测精度,去掉UMHexagonS算法中5×5全搜索中的相对不重要点,根据初始运动矢量的方向采用梯形格点搜索代替全六边形格点搜索,这在一定程度上减少了计算量,同时能更快地搜索到最佳运动矢量。实验结果表明,在保证PSNR和码率基本不变的前提下,可以有效地降低运动估计时间。

关键词：视频编码,H.264/AVC,运动估计,UMHexagonS算法

参考文献

[1]毕厚杰.新一代视频压缩编码标准——H.264/AVC[M].北京:人民邮电出版社,2005.

[2]LIU L K,FEIG E.A block-based gradient descent search algori-thm for block motion estimation in video coding[J].IEEE Trans.Circuits and Systems for Video Technology,1996,6(4):419-422.

[3]ZHU S,MA K K.A new diamond search algorithm for fast block-matching motion estimation[J].IEEE Trans.Image Processing,2000,9(2):287-290.

[4]ZHU C,LIN X,CHAU L.Enhanced hexagonal search for fastblock motion estimation[J].IEEE Trans.Circuits and Systems forVideo Technology,2004,14(10):1210-1214.

[5]ISO/IEC JEC1/SC29/WG11 M5453,Report on performance of fastmotion estimation using motion vector field adaptive searchtechni-que(MVFAST)[S].1999.

[6]TOURAPIS A M,AU O C,LIOU M L.Predictive motion vectorfield adaptive search technique-enhancing block based motionestimation[EB/OL].[2009-11-09].http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.17.9457&rep=rep1&type=pdf.

[7]CHEN Z B,XU J F,HE Y,et al.Fast integerpel and frac-tionalpel motion estimation for H.264/AVC[EB/OL].[2009-11-09].http://linkinghub.elsevier.com/retrieve/pii/S1047320305000787.

模板算法 篇6

模板匹配[1]是指在目标图像中寻找与给定模板相同或相似区域的过程，是计算机视觉基础方法之一，并且在自动导航、目标跟踪、医疗诊断等多个领域中得到了广泛的运用。模板匹配方法主要分为两类:一类为基于灰度方法的匹配;另一类为基于特征方法的匹配。前者基于灰度值，通过不同准则检测模板与目标图像部分相似性;后者通过提取两幅或多幅图像的颜色、纹理、形状等特征，并进行描述，然后根据描述参数匹配。基于特征方法匹配适合具有明显特征图像，但匹配精度不高[2]。基于灰度方法匹配精度较高，其中归一化互相关算法NCC，抗噪性强、性能稳定[3]，但计算公式复杂，匹配时间长，严重制约其应用。

随着群智能优化算法的发展，粒子群PSO[4,5]算法因其易实现、控制参数少、收敛速度快等特点，逐渐被应用到图像处理中。文献[6]提出一种基于量子空间PSO的图像分割算法(QDPSO)，该方法通过最优阈值来划分像素，实现图像分割，经试验分析，该分割方法适应性强，分割效果稳定。文献[7]使用改进PSO算法对中值滤波优化，相比普通中值滤波提高了抗噪性能。文献[8]将标准PSO与SAD模板匹配算法相结合，虽然增加绝对精确匹配率，但没有考虑标准PSO缺陷与噪声影响。文献[9]将标准PSO与灰色关联分析相结合，提出了GPSO图像匹配算法，提高了模板匹配的抗噪性能，但是没有考虑标准PSO容易陷入局部最优的缺陷。本文基于标准PSO算法，引入附属粒子群引导主粒子群收敛，使用黑名单机制防止粒子群再次陷入局部最优，并加入随机扰动算子减小匹配误差，然后将改进后PSO结合NCC算法提出NPSO模板匹配算法。

1 基于标准粒子群NCC模板匹配算法

1.1 NCC模板匹配算法

设目标图像大小为M×N，模板图像大小为A×B,(M≥A,N≥B)。NCC匹配算法将模板图像左上角在目标图像中逐行逐列移动，移动范围为row∈[1,M-A+1],col∈[1,N-B+1]，并使用式(1)计算归一化系数，其中T表示模板图像，Ii,j表示在移动过程中被T覆盖的目标图像部分，T-与I-i,j分别表示对应灰度均值，计算方法如式(2)与式(3)。式(1)得到的NCC系数范围为[0,1]，模板与覆盖图像相似度越高，归一化系数越大，1表示完全匹配。

1.2 标准粒子群算法

粒子群算法[4,5]是1995年Kennedy和Eberhart博士根据鸟群觅食行为提出的一种群智能优化算法，其中鸟为粒子，食物为全局最优解，粒子群算法就是模拟鸟群寻找食物的过程。首先初始化N个M维粒子，初始位置为Xi=(xi1,xi2，…，xiM)，初始速度为Vi=(vi1,vi2，…，viM),i=(1,2，…，N)。然后使用适应度函数根据位置Xi计算出适应度值Fi。记录每个粒子每维历史最优值(使适应度值最大或最小的位置)Oi(oi1,oi2，…，oiM)，并找出所有粒子中每维最优值，即全局最优值Og(og1,og2，…，ogM)。然后使用式(4)、式(5)更新速度与位置。

其中ω叫作惯性权重，表示保持上一次速度系数;Vkid表示第i个粒子第d维进化k次之后的速度;c1、c2为学习因子，分别表示自我认知与社会认知，通常取值为2;r1、r2为[0,1]之间的随机数;Okid表示第i个粒子第d维在进化k次之后的个体最优位置，Okgd表示粒子群的全局最优位置;Xkid表示第i个粒子第d维进化k次之后的位置;η为约束因子，通常取值为1。

因为NCC模板匹配算法取值范围确定，且为寻找全局最优解问题，所以可抽象为以匹配范围内像素点坐标为输入粒子，以式(1)为适应度函数的优化问题。其中粒子维数为2，即Xi=(xi1,xi2)，取值范围为:

2 标准粒子群算法的改进

虽然标准粒子群算法具有计算灵活、简单易用、收敛速度较快的优点，但随着模板减小，模板与目标图像相似区域增多，NCC系数接近最优值极值增多，而标准PSO初始化随机性强，且缺乏跳出局部最优的能力，极易陷入局部最优解，导致模板匹配位置错误。

以图1细胞图像与模板为例，图2表示模板在目标图像NCC系数三维图。因为图1中与模板相似区域较多，所以图2中NCC系数值接近全局最优值1的局部极值较多。

本文根据模板匹配特点，引入基于区域的附属粒子群，引导主粒子群收敛至全局最优，建立黑名单机制，使粒子群迅速跳出全局最优，并引入随机扰动算子，减小匹配误差，极大提高了模板匹配准确度。

2.1 基于区域的附属粒子群

模板尺寸越大，与目标图片相似区域越少，粒子群搜索范围也越小，NCC系数极值也相对越少，粒子群越容易收敛至全局最优解。基于上述分析，目标图像固定，模板尺寸越大，粒子群越容易找到全局最优解，但目标图像与模板相对位置未知，所以没有可利用的先验知识扩大模板尺寸。由于目标图像匹配范围已知，因此可以将匹配区域分割，增加模板尺寸所占比例，并在每个分割区域内分配粒子群并行寻找最优解。其中分割区域中的粒子群叫作附属粒子群，全局范围内的粒子群叫作主粒子群。以图1为例，将其匹配区域分割为四个，即:

在附属粒子群并行搜索所在区域得到最优解后，使用附属粒子群最优解(使适应度函数值最大位置)，引导主粒子群收敛，如式(15)，其中vidk+1表示主粒子群的速度，opd表示附属种群最优位置。最优位置所属区域即为最优附属区域。

2.2 黑名单机制

当最优解进化E代不变时，粒子群可能陷入局部最优，为了快速跳出局部最优，直接初始化粒子群，并总保留最优解为全局进化最优解。然后将主群粒子以大概率事件初始化在最优附属区域内，如式(16)。在跳出局部最优的同时，增加了种群多样性。

为避免再次陷入已经得到的局部最优解，根据禁忌搜索思想[10]，将适应度值小于全局进化最优解的局部最优解加入黑名单。

2.3 随机扰动算子

基于粒子群的模板匹配为组合优化问题，即坐标点只能取整数，在对最优值取整时可能与最佳位置稍有偏差，所以在迭代过程中，遇到黑名单中局部最优值时，直接对现有粒子速度加入随机值，如式(17)，其中φ∈[0,1]，|Regionid|为第i个粒子d维的取值范围大小。减少粒子群在局部最优解花费时间，并增强对局部最优解周围区域搜索。

2.4 NPSO算法执行步骤

根据以上优化，将NPSO算法步骤总结如下:

1)在式(6)范围内随机挑选P个粒子作为主粒子群。确定匹配区域分割个数，并分别在各自范围内随机生成P个粒子作为附属粒子群。初始化每个粒子群位置为Xi1=(x1i1,x1i2)，速度为Vi1=(v1i1,v1i2),i=(1,2，…，P)，使用式(1)计算其适应度值。并记录附属粒子群最优值。

2)判断附属粒子群是否全部收敛至最优值(最优值连续E带不变)，是则执行4)，否则执行3)。

3)以式(4)、式(5)更新附属粒子群速度与位置。

4)判断主粒子群适应度值是否连续E带不变，是则执行5)，否则执行9)。

5)主粒子群收敛适应度值是否小于附属粒子群最优适应度值，是则执行6)，否则执行7)。

6)将主粒子群收敛位置加入黑名单，转至8)。

7)将附属粒子群最优位值加入黑名单，并将主粒子群收敛适应度值与位置赋值给附属粒子群最优值。转至8)。

8)在式(16)表示区域重新初始化主粒子群。

9)判断主粒子群是否陷入黑名单，是则转10)，否则转11)。

10)以式(17)、式(5)更新速度与位置，转12)。

11)以式(15)、式(5)更新速度与位置，转12)。

12)如此次迭代最优解适应度值小于上一次最优适应度值，则将上一次最优解赋值给此次最优解。

13)是否达到最大迭代次数，是则结束，否则转2)。

3 实验结果与比较

实验环境为Core i5 3.10GHz,MATLAB 7.11。

3.1 模板匹配精度

以图1为目标图像，其中黑框图像为模板图像，尺寸为32×32。分别使用NPSO与基于标准PSO的NCC算法进行模板匹配。两种算法种群个数P=30,w=1,c1=2,c2=2,r1=1,r2=1，η=1，迭代次数为80。其中NPSO算法中c3=2,r3=1,,E=10。附属粒子群为4个，取值范围如式(7)-式(10)。

图3为两种算法分别独立运行100次求均值后的收敛曲线。

由于NPSO控制参数较多，导致前期运行速度较慢，并且总运行时间高于PSO。但NPSO最终收敛至0.98，基于标准PSO的NCC模板匹配算法最终收敛至0.85。由于NPSO的黑名单机制，平均每次运行结束跳出局部最优次数为10次，且进化具有多样性，加上随机扰动算子的增加收敛精准性，找到匹配最优解能力明显高于标准PSO算法。

图4为两种算法每次运行结束得到的最佳匹配位置与模板在目标图像中标准位置的街区距离。

可以看出NPSO的绝对精确匹配率为84%，误差小于等于1的精确匹配率为92%。而基于标准PSO的NCC算法绝对精确匹配率为15%，误差小于等于1的精确匹配率为16%。NPSO相比PSO算法匹配精度提高了79%。

表1为标准PSO与NPSO在图1中不同模板尺寸(保持模板左上角位置不变)匹配精度。

由表1可以看出，模板越大，NPSO匹配精度越高。模板越小，NPSO相对于标准PSO匹配精度提升比例越大，充分说明NPSO在多极值情况下增加了收敛准确性。

3.2 匹配时间与抗噪性能

(1)运行时间比较

表2为不同模板尺寸下NCC算法、SSDA算法运行时间与基于标准PSO的NCC算法、NPSO算法收敛至最优解所使用时间比较。其中SSDA阈值取3，最大匹配点数为100。

当模板大小为16×16、32×32、64×64时标准PSO与NPSO迭代次数为80次，当模板大小为128×128时标准PSO迭代20次、NPSO迭代10次便可达到最佳收敛状态。因为NPSO的附属粒子群机制，收敛至最佳值的迭代次数相比标准PSO减少10次。

由表2可以看出，NCC与SSDA运行时间较长，PSO与NPSO在运行时间上占有优势，但NPSO相比PSO运行时间略有增加，是因为NPSO牺牲部分时间增加收敛准确性。综合表1表2可以看出，NPSO算法相对于标准PSO的NCC模板匹配算法在小模板尺寸下增加27%、26%、21%的运行时间的同时，分别使定位精度提高900%、409%与60%。

(2)抗噪性能比较

图5(a)与黑框中图像分别表示原图与模板图像。图5(b)、(c)、(d)分别在原图中加入方差为0.01、0.02、0.03高斯噪声。

提取图5(a)中模板，其尺寸为32×32。使用上述四种算法在图5(b)、(c)、(d)中寻找模板位置，并分别独立执行100次。实验结果如表3所示。

由于模板灰度值与图像其地地方灰度差异较大，所以NCC系数接近于1的极值较少，加上NCC算法抗噪能力较强的特点，NCC算法、基于标准PSO匹配算法与NPSO算法都不容易受噪声干扰，其中NCC算法匹配准确度达到100%,NPSO算法准确度接近100%，而标准PSO算法匹配准确度只有18%左右。SSDA算法虽然可以减少运行次数，但匹配精度随噪声强度增加而降低，鲁棒性不佳。NPSO基于NCC算法，具有较强抗噪性能。

4 结语

文中使用附属粒子群、黑名单机制、随机扰动算子对标准PSO方法改进，结合NCC算法，提出了NPSO模板匹配算法。该算法克服了标准PSO算法容易陷入局部最优解的缺点，不仅提高了模板匹配精度，而且具有很强的抗噪能力。

增加模板尺寸、粒子群总群个数和附属粒子群个数都可以增加绝对精确匹配率，经多次试验，NPSO模板匹配精度与NCC系数极大值个数和粒子移动速度也有很大关系。当极大值较多时，应当适当降低粒子移动速度;当极大值较少时，应当加快粒子移动速度。使种群多样性与收敛速度达到最佳值，使得增加匹配准确度的同时加快收敛速度。

摘要：针对灰度模板匹配中速度慢、抗噪性差的缺陷,基于NCC(Normalized Cross-Correlation)算法,提出一种基于优化粒子群的模板匹配算法——NPSO。该算法加入附属粒子群,引导主粒子群向全局最优解收敛;根据禁忌搜索思想,提出黑名单概念,使粒子群快速跳出局部最优;并引入随机扰动算子,增加粒子群向全局最优解收敛准确性。通过Matlab仿真实验,不同模板尺寸下NPSO精确匹配率比基于标准粒子群模板匹配算法分别提高了45%、79%、36%、2%,且对噪声不敏感。说明NPSO不容易陷入局部最优,且匹配精度高、抗噪能力强。

关键词：模板匹配,粒子群算法,归一化互相关算法,附属粒子群,黑名单机制,随机扰动算子

参考文献

[1]Brunelli R.Template matching techniques in computer vision:Theory and Practice[M].Britain:Wiley and Sons,2009.

[2]Lin D M,Tsai C T.Fast normalized cross correlation for defect detection[J].Pattern Recognition Letters,2003,24(15):2625-2631.

[3]Yong S H,Kyoung M L,Sang U L.Robust stereo matching using adaptive normalized cross-correlation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2011,33(4):807-822.

[4]Eberhart R,Kennedy J.A new optimizer using particle swarm theory[C]//Nagoya,Japan:Proceedings of the Sixth International Symposium on Micro Machine and Human Science,1995.

[5]Kennedy J,Eberhart R.Particle swarm optimization[C]//Perth,Australi:IEEE International Conference on Neural Network,1995.

[6]朱霞.基于量子空间的粒子群算法在图像分割中的应用研究[J].计算机应用与软件,2012,29(6):256-259.

[7]武装.一种基于改进粒子群的图像滤波方法[J].计算机应用与软件,2013,30(2):86-88,156.

[8]王维真,熊义军,魏开平,等.基于粒子群算法的灰度相关图像匹配技术[J].计算机工程与应用,2010,46(12):169-171.

[9]鹿艳晶,马苗.基于灰色粒子群优化的快速图像匹配算法[J].计算机工程与应用,2009,45(10):157-159.

模板算法 篇7

数字图像修复技术被广泛的应用于图像译码以及图像网络传输(例如恢复丢失块)、特效处理(例如移除图像中的某个物体)和图像的恢复(例如擦痕的移除),并且数字图像修复技术对于使用传统修复技术的博物馆或是艺术家,也有重要的意义。为了解决这个问题,近年来学者们进行了许多有意义的探索和研究。

图像修复算法主要分为两类,一类是基于偏微分方程(PDE)的修复算法,典型的方法包括Bertalmio[1]用三阶PDE模拟平滑传输过程;Chan-Shen[2]用三阶PDE模拟CDD(curvature driven diffusions);全变分(total variation,TV)模型[3]以及综合了Bertalmio模型沿辐透线传输信息以及CDD(以及TV)模型垂直于辐透线扩散信息两种方式的Euler's elastica模型[4]。这些方法都基于偏微分方程,偏微分方程是依据图像特征沿特定的方向将周边已知的图像信息一个像素一个像素扩散填充到未知区域中,能够很好地保留图像的线性结构,适用于修复图像中的划痕等一些较小尺度的损伤,但修复较大的区域时就会有很明显的模糊效果。

另外一种是基于块的纹理合成技术,该种算法的主要思想是,从待修复区域的边界上选取一个像素点,以这个像素点为中心确定一个一定大小的模块,然后在周围的已知区域中寻找与之最相近的纹理匹配块来代替该模块。早些年研究的算法包括在文献[5-6]中都有提及。这些算法适用于修复大面积缺损图像,能够很好地恢复图像的纹理信息但却丢失了结构信息。目前对这种方法的研究较多。

近几年来,Bertalmio et al又提出了同时进行纹理合成和图像修补的算法[7],该算法首先将图像分解成结构信息和纹理信息两个部分,然后采用Bertalmio之前提出的图像修补算法[2]。修复结构部分,通过纹理综合来修复纹理信息,最后合并修复后的结构信息和纹理信息,但是由于模糊效果仍存在,该算法局限于小面积缺损图像的修复。这是一种综合两类图像修复算法优点的一种早期尝试。

后来,Criminisi[8]首先将纹理合成技术与图像修补技术统一起来,结合在了一个修复过程中,继承了两者的优点。文章中指出基于块的纹理合成技术在修复时若能充分考虑修复顺序的影响便能够提高图像的修复质量,而修复顺序依据的是图像修补技术中的扩散方式,因为这类算法中的扩散方式充分考虑了待修复像素点周围的图像特征,能够保留图像的结构信息。

本文沿着Criminisi的思路,在充分理解图像修补技术[1,2,3,4]的扩散原理的基础上,分析AIEI[8]和CIEI[9]算法的思想,提出了新的优先权计算方法。

1 AIEI和CIEI的填充过程

基于纹理合成的数字图形修复算法的基本流程,如图1所示。

AIEI(Along Isopotes Exemplar-based Inpainting)算法基于这种架构并在优先权上做出了自己的贡献,AIEI优先权的计算基于Bertalmio et al[2]的修补原理,主要思想是位于辐透线(或边界线)上的点具有较高的优先权,首先被填充。AIEI算法优先权计算公式如下:

其中:

C(p)表示模板的置信项,模板中已知信息的含量,Ψ是以p为中心的模板,I是指整幅图像,Ψ是受损区域。D(p)表示模板的数据项。np是边界线在p点的单位法向量,Δup⊥代表p点处的辐透线(Isophotes)强度和方向。由公式可以看出,辐透线上的点|Δup⊥|值较大,优先权值相应较高,故会首先被填充。

一旦优先权计算完毕,则首先填充优先权最高的模板。方法是从源区域取样,寻找和该模板最匹配的模板,计算公式为:

其中,d(Ψa,Ψb)表示两模板Ψa和Ψb间对应像素差的平方和(Sum of Squared Difference,SSD)。然后将相应的像素点复制填充到目标区域的模板中,同时更新模板内像素的置信项的值。

在AIEI算法的基础上,Wu提出了CIEI(Cross Isophotes Exemplar-based Inpainting)数字图像修复算法。CIEI算法相对于AIEL算法,唯一不同的是优先权中数据项的计算,CIEI算法将TV模型的扩散算子ut[3]作为优先权中的数据,计算公式如下:

其中,ξ是辐透线的切线方向,uξξ是在边界Ψ处的二阶方向导数,它决定了扩散的方向。从公式中可以看出数据项的值与辐透线强度成反比,辐透度的大小在数值上与梯度的大小相同,辐射度越大意味着在该像素所在的块中,图像信息的变化也越大,也即像素变化越小的块,具有越大的优先权。

2 优先权计算的改进

像素点的修复顺序直接影响图像的恢复质量,本文通过分析推导提出了两种优先权计算方法。

优先权改进方法1:

选择局部正交坐标系,其中η轴是在该点垂直于辐透线的方向,ξ轴是在改点沿着辐透线。利用二阶方向导数方法,推导出局部坐标下,p-Laplace算子[10]表达式为:

其中:

是扩散方向,各自的扩散系数是|Δu|p-2和(p-1)|Δu|p-2。

基于p-Laplace算子的图像修补方法的扩散方程为:

实质是一个非线性各向异性扩散方程,只要合理选择p,就能控制扩散方程的扩散行为,达到某种扩散目的。

讨论:

当p≡1时,Δ1u=|Δu|-1 uξξ,这是TV模型,将其作为数据项,即变为CIEI算法,在光滑区域,有可能将平坦的部分变为分段平坦的。

当p≡2时,Δ2u=uξξ+uηη,是一个各向同性的扩散,光滑图像的同时模糊了边缘。

选择1

本文将其作为新的数据项。

可见,优先权的计算不仅由|Δu|-1/2辐透线强度大小决定,而且沿辐透线方向和垂直于辐透线方向两个方向的二阶导数也起着决定作用。这样,块的填充顺序将顾及两个方向的图像特征,而不是单一的沿辐透线方向(AIEI)或者垂直于辐透线方向(CIEI),其他步骤同AIEI算法,此算法对于结构复杂的图片有很好的填充效果,实验仿真结果见下文。

优先权改进方法2:

Masnou and Morel通过分析弹性能量(elastica energy),提出了基于elastica的变分图像修补模型。Chan&Shen[5]在此基础上,进一步对这个模型的数字实现做出了贡献,并且对前面提到的图像修补模型[2,3,4,5]的属性(property)和连续性(connection)在elastica的变分理论下做了进一步的诠释。其扩散方程为:

其中:

表示的是沿辐透线方向,表示的是垂直于辐透线方向(即梯度方向),由两个部分组成,且令Φ(κ)=g(κ)=a+bκ2,b≡1,则有:

对应于CDD扩散模型[2]。

对应于Bertalmio et al.的修补(inpainting)模型。

可见Euler's elastica填充算法结合了沿辐透线修补和垂直辐透线修补两种模型,形成了一种更灵活可行的修补算法。

本文由此提出了一种权衡AIEI和CIEI两种算法的优先权计算方法,计算公式如下:

通过调节p的值,可以调节填充顺序在两个方向转换,达到对复杂结构图像的修复。对于上面提到的优先权改进方法1,是将像素周围两个方向的图像特征都考虑了,相对CIEI考虑单一方向的图像特征更全面了,而优先权改进方法2是将两个沿单一方向的修复算法AIEI和CIEI综合了,修复时根据p的大小决定修复的具体方向,更具灵活性,效果更明显。

3 实验仿真

优先权改进方法1:

对图像的操作结果及与AIEI和CIEI的比较,从图2中可以看出,AIEI和CIEI在修复过程中虽然将衣服的线条恢复出来了,但是这不是我们所要的结果,而在本文提出的新的优先权值作用下,头发恢复的比较理想。这是因为优先权改进方法1同时考虑了两个方向的图像特征,更加全面的情况下,头发的结构信息没有丢失,完整地恢复了出来。

优先权改进方法2:

对图片的处理结果及与AIEI和CIEI的比较结果如下图3所示,通过比较可以发现本算恢复的图像不仅屋檐的边缘恢复得很清晰,而且屋顶的细节也恢复得很好。通过图3(b)可以发现沿辐透线方向的AIEI算法,将屋顶信息恢复的较完整,但却多出了一些不希望有的部分,3(c)图显示的CIEI算法垂直于辐透线方向修复,可以发现本来应该是填充屋顶信息的部分,却被填充了另一方向上的天空信息,而图3(d)优先权改进方法2通过p的调节让算法兼顾两个方向进行修复,修复结果显示即没有了多余的屋顶信息,也没有错误的被天空信息填充,效果得到了很大的改进。

4 结束语

本文分析了各种图像修补模型,介绍了已有的基于块的纹理合成算法AIEI和CIEI,在对优先权中数据项的理解基础上提出了两种优先权的计算方法,分别是基于图像修补模型P-Laplace和Euler's Elastica的,并且给出了仿真结果以及与AIEI和CIEI的修复效果进行了比较,可以发现修复效果有了很大的改进。

图像的修复质量不仅依赖于修复块的合成顺序,而且待修复块的大小以及搜索匹配块的范围和方式对图像的修复质量也有影响,可以在这方面做进一步的研究工作。

摘要：研究了基于块填充的图像修复算法,修复图像的质量容易受到待修复区域边界像素修复顺序的影响,通过分析待修复区域像素点所在模块的图像特征,改进了填充算法的优先权,分别是基于P-Laplace算子和Euler’s elastica模型的优先权计算方法的改进。实验结果证实了文中所介绍算法能有效提高重建图像的感知质量。

关键词：图像修复,优先权,P-Laplace算子,Euler’s elastica模型

参考文献

[1]Bertalmio M,Sapiro G,Caselles V,et al.Image Inpainting[C]//In-ternational Conference on Computer Graphics and Interactive Tech-niques,New York:ACM Press,2000:417-424.

[2]Chan T F,Shen J H.Non-Texture Inpainting by Curvature-Driven Diffu-sions(CDD)[J].J.Visual Comm.Image Rep.,2001,12(4):436-449.

[3]Chan T F,Shen J H.Mathematic Models for Local Non-Texture In-painting[J].SIAM J.Appl.Math,2001,62(3):1019-1043.

[4]Chan T F,Kang S H,Shen J H.Euler’s Elastica and Curvature BasedInpainting[J].SIAM J.Appl.Math.,2002,63(2):564-592.

[5]Efros A,Freeman W T.Image quilting for texture synthesis and transfer[C]//Proc.ACM Conf.Computer Graphics(SIGGRAPH),Aug.2001:341-346.

[6]Liang L,Liu C,Xu Y Q,et al.Real-time texture synthesis by patch-based sampling[J].ACM,Trans.Graphics,2001.

[7]Bertalmio M,Vese L,Sapiro G,et al.Simultaneous structure and tex-ture image inpainting[C].Proc.Conf.Comp.Vision Pattern Rec.,Madison,WI,2003.

[8]Criminisi P Perez,Toyama K.Region filling and object removal byexemplar-based image inpainting[J].IEEE.Trans.Image Processing,2004,13(9).

[9]Jiying Wu,Qiuqi Ruan.Object Removal By Cross Isophotes Exemplar-based Inpainting[C].IEEE,the 18th international conference on pat-tern recognition,2006.