第五讲 中层视觉(3)正交变换与运动估计.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第五讲 中层视觉,(3),图象处理中的正交变换,运动的理解与估值,1.,图象处理中的正交变换,图像的各种变换尤其是正交变换在图像处理中有着广泛的应用，如图象的特征提取，图像的压缩编码，图象的增强和滤波等。它的主要思想就是将原来在空间域上的图像信号，通过一系列数学变换（如,富里叶变换，余弦变换等,），变换到变换域（频率域，正交矢量空间），用变换系数来描述图像，这些系数反映了图像的某些特征，,时域和频域之间的变换可用数学公式表示如下：,完成这种变换，一般采用的方法是线性正交变换。,(7-2),为能同时表示信号的振幅和相位，通常采用复数表示法，因此上式可用复数表示为,1,）富里叶变换,富里叶变换（,Fourier Transformation,）是线性系统分析一个有力的工具，它使我们定量分析系统与信号的一个手段,频域分析方法。,一维连续富里叶变换（回顾）,1,）离散富里叶变换,如果,f,i,是一个长度为,N,的序列，比如从对一个连续函数进行等间隔采样得到的，则离散富里叶变换（,DFT,）就是序列,F,n,：,其中：,由欧拉公式可知,并利用,cos,(,)=,cos(,),，,可得,(7-10),可见，离散序列的傅立叶变换仍是一个离散的序列，每一个,n,对应的傅立叶变换结果是所有输入序列,f,i,的加权和（每一个,f,i,都乘以不同频率的正弦和余弦值），,n,决定了每个,傅立叶变换结果的频率。,通常傅立叶变换为复数形式，即,式中，,R,n,和,I,n,分别是,F,n,的实部和虚部。上式也可表示成指数形式：,其中,通常称,|,F,n,|,为,f,(,x,),的频谱或傅立叶幅度谱，,n,为,f,(,x,),的相位谱。,频谱的平方称为能量谱或功率谱，它表示为,考虑到两个变量，就很容易将一维离散傅立叶变换推广到二维。如果,f,(,i,k,),是一个,N,N,的数组，则它的二维离散傅立叶变换对,定义为,二维离散富里叶变换,二维离散富里叶变换的计算,上式的指数可被分解，从而变换可写成,依次将二维,DFT分解为水平和垂直两部分运算，方括号中项表示在图象行上计算的,DFT,，方括号外边的求和则实现结果数组在列上的,DFT,。这种分解是我们可以用一维,FFT,来实现二维,DFT,。,矩阵表示：,DFT,用矩阵表示可以写成,二维离散富里叶变换的计算,其中：,是一个,NxN,的复酉矩阵，即矩阵的逆是它的复共轭的转置,G,-1,=(G,*,),T,.,要得到一个酉矩阵的逆，只要简单地交换行和列位置，并改变每个元素虚部的符号。由于,G,是对称的，所以可以省掉转置。,定义,|F(m,n)|,2,=,F(m,n,)F*(,m,n,),为图象,f(i,j,),的功率谱，即,F(m,n,),的实部平方加虚部平方功率谱是图像的重要特征，反映图像的灰度分布。例如具有精细结构的图像，其高频分量较为丰富。如果图像中目标形状排列呈现某种方向性，那么具有较高值的功率谱也呈现出与图像目标方向正交的方向分布。,二维离散富里叶变换的计算,f(x,y,),y,x,|F(u,v)|,2,u,v,图像模式延伸方向与功率谱高值的模式方向互相垂直,例如，假设图像,f(x,y,),灰度分布模式延,y,轴伸展,1/X,1/Y,二维离散富里叶变换的计算,f(x,y,),的,FT,由于,功率谱函数模式延,u,轴延伸,因此，图像功率谱模式延伸方向与原图像灰度分布延伸方向相互正交。一般来说，若,f,的,FT,为,F,则有：,二维离散富里叶变换,由于富里叶变换的物理意义明确、直观，加上有快速算法，近年来又出现了大规模集成电路的专用芯片，因此它是图像数字变换中最常用的方法。,实践中，除了,DFT,变换之外，还采用许多其他的正交变换。例如：,Karhunen_Loeve,变换，离散余弦变换、沃尔什,-,哈达玛变换、,K-L,变换等，下面将对常用的变换作一简要介绍。,2.,离散余弦变换（,DCT,）,离散余弦变换（,Discrete Cosine Transform,，,DCT,）的变换核为余弦函数。,DCT,除了具有一般的正交变换性质外，它的变换阵的基向量能很好地描述人类语音信号和图像信号的相关特征。因此，在对语音信号、图像信号的变换中，,DCT,变换被认为是一种准最佳变换。近年颁布的一系列视频压缩编码的国际标准建议中，都把,DCT,作为其中的一个基本处理模块。除此之外，,DCT,还是一种可分离的变换。,一维离散余弦变换,一维,DCT,的变换核定义为,式中，,x,u,=0,1,2,N,1,；,式中，,u,x,=0,1,2,N,1,。,将变换式展开整理后，可以写成矩阵的形式，即,F=,Gf,其中,一维,DCT,的逆变换,IDCT,定义为,式中，,x,u=0,1,2,N,1,。一维,DCT,的逆变换核与正变换核是相同的。,二维离散余弦变换,考虑到两个变量，很容易将一维,DCT,的定义推广到二维,DCT,。,其正变换核为,式中，,C,(,u,),和,C,(,v,),的定义相同，见上式；,x,u,=0,1,2,M,1,；,y,v,=0,1,2,N,1,。,二维,DCT,定义如下：设,f,(,x,y,),为,M,N,的数字图像矩阵，则,离散沃尔什,-,哈达玛变换（,WHT,）,一维离散沃尔什,-,哈达玛变换,沃尔什函数是,1923,年由美国数学家沃尔什提出的。沃尔什函数系是一个完备正交函数系，其值只能取,1,和,1,。按照哈达玛排列来定义的沃尔什函数是由,2,n,（,n=0,，,1,，,2,，,）阶哈达玛矩阵（,Hadamard,Matrix,）得到的，而哈达玛矩阵的最大优点在于它具有,简单的递推关系，即高阶矩阵可用两个低阶矩阵的克罗内克积求得。,N=2,n,(n=0,1,2,),阶哈达玛矩阵每一行的符号变化规律对应于某一个沃尔什函数的符号变化规律，即,N=2,n,(n=0,1,2,),阶哈达玛矩阵的每一行对应于一个离散沃尔什函数，,2,n,阶哈达玛矩阵有如下形式：,离散沃尔什,-,哈达玛变换（,WHT,）,哈达玛矩阵的阶数是按,N,2,n,(,n,0,1,2,),规律排列的，阶数较高的哈达玛矩阵，可以,利用矩阵的克罗内克积运算，由低阶哈达玛矩阵递推得到，即,矩阵的克罗内克积,(,Kronecker,Product),运算用符号记作,A,B,，,其运算规律如下：,设,则,则,2.,离散沃尔什,-,哈达玛变换,一维离散沃尔什变换定义为,一维离散沃尔什逆变换定义为,式中，,Walsh(,u,x,),为沃尔什函数。若将,Walsh(,u,x,),用哈达玛矩阵表示，并将变换表达式写成,矩阵形式，则上两式分别为,和,式中，,H,N,为,N,阶哈达玛矩阵。,由哈达玛矩阵的特点可知，沃尔什,-,哈达玛变换的本质上是将离散序列,f,(,x,),的各项值的符号按一定规律改变后，进行加减运算，因此，它比采用复数运算的,DFT,和采用余弦运算的,DCT,要简单得多。,二维离散沃尔什变换,很容易将一维,WHT,的定义推广到二维,WHT,。,二维,WHT,的正变换核和逆变换核分别为,和,式中：,x,u,=0,1,2,M1,；,y,v,=0,1,2,N,1,。,二维离散沃尔什变换,图像数据为,f,正变换为：,逆变换为：,和,求下面两个信号的二维,WHT,。,N,=4,，,二维,WHT,变换核为,所以,由此可见，二维图像数据经过,Walsh,变换后，仅在七左上部保留了一些元素，而其他的大部分位置上元素取值为,0,，因此说二维,WHT,具有能量集中的特性，而且原始数据中数字越是均匀分布，经变换后的数据越集中于矩阵的边角上。,因此，,WHT,在图像压缩，雷达、通信、生物医学等得到了广泛的应用。,2.,二维运动估计,自然界的一切景物都在运动着，静止只是相对的，利用种种观测器取得的二维图像序列只是记录了景物的某一侧面某一局部、某一时间内各时刻的灰度图像。从二维图像序列检测景物运动，提取运动参数，分析景物的运动规律；或者获取立体景物的深度、遮盖和表面主方向等信息是图像序列分析的主要研究内容。例如，从运动物体的图像序列提取物体（如飞行器、交叉路口的汽车、传送带上的机器零件等）的平移、旋转等运动参数，从卫星云图提取某地区上空各云团中心的运动规律。从一个心动周期的超声波图像序列，检测心内膜位置，从而计算心脏排血量等对诊断心脏病有重要价值的参数。,二维运动估计,如果同一个观测器，在相邻两时刻,t,k-1,和,t,k,获得的同一个三维景物图像为,f(x,y,t,k-1,),帧与,f(x,y,t,k,),，而景物中某物体的特征（例如飞行器的前端）在这两幅图像上的相对位置是不同的，我们称这种位置的差为视差。它是三维景物的运动反映在二维图像上的位移向量（包括大小和方向）,.,视差除以时间,t,k,，称为瞬时位置速度,.,在图象序列反映的景物中，各物体或部分的运动是不同的，形成众多的瞬时位置速度向量，这些不同的瞬时位置速度向量分布在图像上形成的向量场称为,瞬时位置速度场,，也称为,光流场,。根据视差大小和方向可以推断立体景物物体表面上各点与观测器之间的距离或深度，从而获得距离版图；也可以推断多个物体相互遮盖边界位置和物体表面各点的表面主方向。,二维运动估计,在运动检测、运动参数提取、运动分析、距离版图获取、遮盖物体边界古迹、物体表面主方向估计中，视差的估计是十分重要的。,图像序列分析的应用领域包括工业（生产过程动态监视），办公自动化（电视会议，可视电话的频带压缩）遥感（云的运动和高度估计），生物医学，交通管理等,摄象机和场景运动运动分析分为四种 模式模式：,摄象机静止,/,物体静止：简单的静态场景分析,摄像机静止,/,场景运动：一类非常重要的动态场景分析，包括运动目标检测、目标运动特性估计等，主要用于预警、监视、目标跟踪等场合。,摄象机运动,/,物体静止：重要的动态场景分析，包括基于运动的场景分析、理解，三维运动分析等，主要用于视觉导航、目标自动锁定与识别等,摄象机运动,/,物体运动：最一般的情况，也是最难的问题，目前对该问题研究的还很少,图象序列，视差，瞬时位置速度场和光流场,图象序列又称动态图象，它由一系列图象组成，它们具有给定的或假设的相对次序，并给出相邻两图象获取的时间间隔关系。它的一般表示可以写成,i,j,=0,1,.,n-1,所谓相对次序一般是指 时刻在 之后（,k=1,2,n-1,）。相邻两图象获取的时间间隔定义为,=-,k,=1,2,.,n,-1,(k=1,2,.,n-1),可以不等也可以相等，一般取为相等,也就是说所有的图象的获取时间间隔均相等。,图象序列的每一幅，引用电视机技术术语也称为一祯。,在动态景物中，组成景物的各个运动物体在不同的时刻其空间位置是不同的。假设,oxyz,是空间物体,P,点的空间位置坐标系，它构成物体空间。,OXY,是图象空间，它是一个平面，也就是观测器对物体点,P,进行观测获取的图象形成的位置。,O,与,O,相距,F,（观测器的焦距），,oyz,与,OYZ,位于同一平面（见下图。,P,点在时刻 物体空间的坐标为 ，时刻 的坐标为 。它们在图象空间的坐标分别为 和 ，,记,空间物体点,P,从,运动到,，反映在图象平面上，从,位置运动到,。这是我们通过观测器观测三维景物运动记录下来并得到的信息。,移位到,，其位移量为,我们称物体表面的点在相邻两时刻图象上相应的位置的移位为视差，视差的估计称为视差问题。,物体点,P,从,运动到,的时间间隔为,。把图象平面上物体图象相应位置的速度记为,，那么,的大小和方向分别为,从,1,）运动检测和估计的傅立叶方法,用傅立叶变换，可以检测和估计运动物体的二维平移，旋转和尺度变化,1,。物体图象平移的检测和估计,假设在时刻,运动物体点在图象空间的位置为（,x,y,），到时刻,，它的位置移到,，如下图所示。我们要对,和,作出估计。,一般我们可以假设从时刻,到,物体点的灰度保持不变，也就是说,的傅立叶变换为,的傅立叶变换为,=,=,上,式表示：时刻,和,两帧图象的傅立叶变换相位角之差为,=,而,由变量的可分离性，,与,分别表示为,和,在,X,轴的投影，亦即,=,=,和,分别为,和,的傅立叶变换，那么它们的相位角之差为,=,在频率域，关于,u,，求得,从而可解得,同理，求,与,在,y,轴投影，并求得它们的傅立叶变换的相位角之差,而我们可以得到,就是从时刻,到,运动物体点,P,在图象上的位移量。,2,）物体图象旋转和尺度变化的检测和估计,用傅立叶变换检测运动物体可以分别处理平移，旋转和尺度变化。,由纹理分析数字变换技术中的傅立叶方法可知，对于图象空间的线形模式（例如直的边缘），经傅立叶变换以后，它的功率谱也呈线性分布，且通过（,u,v,）平面的原点；它的方向与图象空间域上的线形模式方向正交。,物体图象的尺度变化，反映在傅立叶频率域则是频率高低的变化。在图象空间域上物体区域尺寸变大，在频率域上功率谱的低频分量增大，反之若物体区域尺寸变小，那么频率域上功率谱的高频分量增大。,物体图象在空间域上的平移并不改变频域的功率谱。,估计物体图象的旋转和尺度变化的具体方法可如下进行,物体图象旋转的估计,取不同时刻（例如相邻两时刻）的两祯图象,与,，分别对它们施行,FFT,，并求它们的功率谱,在频率域，功率谱时间序列,和,寻找具有明显相似结构的直线模式（都通过原点）（见下图）,和,。,在,上的投影记为,与,的夹角,就是我们所求的运动物体二维旋转的角度。,中,物体图象尺度变化的估计,在,和,中，寻找方向相同的一对线性结构,和,，,在,平面上的投影记为,和,的最长直径，,和,（见下图），计算,如果,R,1,，即,，那么从时刻,到,运动物体图象的尺寸增大了，增大倍数为,1/R,。如果,R,1,，即,，那么从时刻,到,运动物体图象的尺寸变小了，其减小倍数为,R,。,测量,分别得到,差分图像,f(x,y,j,),帧与,f(x,y,k,),帧之间的变化可用一个二值差分图像表示：式中,T,是阈值,目标运动差分图象,物体运动引起的图像变化示意图,光照变化引起变化的差分图象,(a),和,(b),是取自光照变化的图像序列的两帧图像，,(c),是它们的差分图像,(T=80),基于块的运动分析,基于块,(Block-based),的运动分析在图像运动估计和其它图像处理和分析中得到了广泛的应用，比如在数字视频压缩技术中，国际标准,MPEG1-2,采用了基于块的运动分析和补偿算法,块运动估计与光流计算不同，它无需计算每一个像素的运动，而只是计算由若干像素组成的像素块的运动，对于许多图像分析和估计应用来说，块运动分析是一种很好的近似,块运动模型,基于块的运动模型 假设图像运动可以用块运动来表征块运动通常分为平移、旋转、仿射、透视等运动形式，通常块运动是这些运动的组合，称为变形运动,(1),平移运动,相邻两帧的平移变换公式,:,块中平移的所有像素则,:,块的平移运动具有广泛的应用，主要原因是它无需向光流那样，计算每一个像素的运动，而是只计算一个块的运动，这种计算对于许多应用都是一种很好的近似，同时计算极其简单和有效，非常适合于,VLSI,并行处理但这种算法不适合旋转运动、图像的缩放运动和图像局部变形运动。,块匹配方法块匹配方法,各种块匹配算法的差异主要体现在如下几个方面：,匹配准则,搜索策略,I,块尺寸选择方法,典型的匹配准则有：最大互相关准则，最小均方差准则，最小平均绝对值差，最大匹配像素数量准则等,End,