第三章几何运算

1、第三章第三章 几何运算几何运算几何运算可改变图象中各物体之间的空间几何运算可改变图象中各物体之间的空间关系。该运算可看成是将（各）物体在图象内关系。该运算可看成是将（各）物体在图象内移动。其效果类似在一块橡皮板上画图，拉伸移动。其效果类似在一块橡皮板上画图，拉伸该橡皮板，图形会随之变化。该橡皮板，图形会随之变化。几何变换不改变图象的象素值，只是在图几何变换不改变图象的象素值，只是在图象平面上进行象素的重新排列。象平面上进行象素的重新排列。一个几何运算需要两个独立的算法：一个几何运算需要两个独立的算法：（1）空间变换。）空间变换。（2）灰度插值。）灰度插值。3.1 几何变换几何变换一、基本变换一

2、、基本变换 基本几何变换的定义基本几何变换的定义 一般变换距阵一般变换距阵 常用的基本几何变换常用的基本几何变换 平移变换平移变换 旋转变换旋转变换 镜像变换：水平镜像、垂直镜像镜像变换：水平镜像、垂直镜像 放缩变换放缩变换 拉伸变换拉伸变换 离散几何变换的计算离散几何变换的计算1、基本几何变换的定义、基本几何变换的定义对于原图象对于原图象f(u,v)，坐标变换函数，坐标变换函数x = X(u,v); y = Y(u,v)唯一确定了几何变换：唯一确定了几何变换：g(x, y) = g(X(u,v), Y(u,v) g(x,y)是目标图象。是目标图象。表面看没有值的改变。表面看没有值的改变。 变

3、换函数变换函数X、Y唯一地描述了空间变唯一地描述了空间变换。若它们是连续的，则连通关系将在换。若它们是连续的，则连通关系将在图象中得到保持。图象中得到保持。2、一般变换矩阵、一般变换矩阵很多简单的空间变换都可用一个很多简单的空间变换都可用一个33变换矩阵来变换矩阵来表示：表示：其中其中T称为一般变换矩阵。称为一般变换矩阵。向量向量 和和 中引入了第三个坐标分量中引入了第三个坐标分量w，这样构成的坐标称为，这样构成的坐标称为齐次坐标齐次坐标。当变换阵当变换阵T中的系数取不同值时，可产生变倍、剪中的系数取不同值时，可产生变倍、剪切、旋转、反射、平移及透视等多种变换。切、旋转、反射、平移及透视等多种

4、变换。 Twvuwyx,333231232221131211aaaaaaaaaTwxxwyywyx,wvu,*齐次坐标齐次坐标齐次坐标是计算机视觉和图形学中一个十分有用齐次坐标是计算机视觉和图形学中一个十分有用的工具，利用它可以统一完美地表达许多重要的几的工具，利用它可以统一完美地表达许多重要的几何变换。所谓齐次坐标表示就是用何变换。所谓齐次坐标表示就是用n+1维向量表示一维向量表示一个个n维向量，含有冗余信息：笛卡尔维向量，含有冗余信息：笛卡尔n维空间中的一维空间中的一点可以用齐次（点可以用齐次（n+1）空间中的一条直线来表示。因）空间中的一条直线来表示。因此，对一个笛卡尔空间的物理坐标点，

5、在齐次空间此，对一个笛卡尔空间的物理坐标点，在齐次空间中不存在唯一的表示。中不存在唯一的表示。如：如：3D空间中的点空间中的点(xw, yw, zw)T的齐次坐标是一的齐次坐标是一个个4*1维矢量维矢量(kxw, kyw, kzw, k )T，k为非零任意常数。为非零任意常数。作用：作用：通过矢量空间维数的增加，可将几何变换通过矢量空间维数的增加，可将几何变换中的非线性关系转换为线性关系中的非线性关系转换为线性关系。3、仿射变换、仿射变换(Affine Transformation)仿射变换的一般表达式为：仿射变换的一般表达式为：按线性变换定义，若变换按线性变换定义，若变换L满足：满足：其中其

6、中c为常数。则为常数。则L称为线性变换。称为线性变换。将仿射变换表达式展开：将仿射变换表达式展开： 1001 ,1 ,323122211211aaaaaavuyx)()(xcLcxL)()()(yLxLyxL322212312111avauayavauax显然，在一般情况下，仿射变换不是线性变换。显然，在一般情况下，仿射变换不是线性变换。只有当只有当 时，仿射变换蜕化为线性变换。因时，仿射变换蜕化为线性变换。因此，仿射变换又可表示为：此，仿射变换又可表示为：其中其中A为仿射变换，为仿射变换，t为常数。为常数。仿射变换的性质：仿射变换的性质：（1）仿射变换将平行直线映射成平行直线；将三角形）仿射

7、变换将平行直线映射成平行直线；将三角形映射成三角形。映射成三角形。（2）仿射变换的乘积和逆变换仍是仿射变换。）仿射变换的乘积和逆变换仍是仿射变换。但是仿射变换不能保证四边形到四边形的映射。但是仿射变换不能保证四边形到四边形的映射。03231 aatxLxA)()(几种典型的仿射变换几种典型的仿射变换（1）平移变换）平移变换将所有点的坐标将所有点的坐标u和和v分别加上分别加上Tu和和Tv平移到一个平移到一个新的位置上。新的位置上。10100011 ,1 ,vuTTvuyx（2）旋转变换）旋转变换将将uv平面上的所有点相对原点逆时针旋转平面上的所有点相对原点逆时针旋转 角（注角（注意旋转中心的选取

8、）。意旋转中心的选取）。1000cossin0sincos1 ,1 ,vuyx（3）缩放变换）缩放变换当当su，sv大于大于1时，图象被放大；小于时，图象被放大；小于1时被缩小。时被缩小。10000001 ,1 ,vussvuyx（4）剪切变换（）剪切变换（Shear Transform）又称又称“错切变换错切变换”，指的是类似于四边形不稳定，指的是类似于四边形不稳定性那种性质，方形变平行四边形，任意一边都可以被性那种性质，方形变平行四边形，任意一边都可以被拉长的过程。拉长的过程。沿沿u轴的剪切变换可表示为：轴的剪切变换可表示为：沿沿v轴的剪切变换可表示为：轴的剪切变换可表示为： 100010

9、011 ,1 ,vHvuyx 100010011 ,1 ,uHvuyx100010001T100010001T100010001T*对称变换（反射变换或镜象变换）对称变换（反射变换或镜象变换）(a)对称于对称于Y轴轴变换矩阵为：(b)对称于对称于X轴轴变换矩阵为：(c)对称于原点对称于原点变换矩阵为：100001010T100001010T(d)对称于直线对称于直线y=x变换矩阵为：(e)对称于直线对称于直线y=-x变换矩阵为：4、透视变换、透视变换透视变换（亦称投影映射），可表示为：透视变换（亦称投影映射），可表示为：其中：其中：透视变换与仿射变换有许多相同的特性。如透视变换与仿射变换有许多

10、相同的特性。如：它它们都是平面映射，因此其向前和逆变换都是单值的；们都是平面映射，因此其向前和逆变换都是单值的；它们可以保证任意方向的直线变换后仍为直线。但是它们可以保证任意方向的直线变换后仍为直线。但是透视变换有透视变换有8个自由度，可以满足平面四边形到四边形个自由度，可以满足平面四边形到四边形的映射（四角映射），而仿射变换只有的映射（四角映射），而仿射变换只有6个自由度，不个自由度，不能实现四角映射。能实现四角映射。3332312322211312111 ,1 ,aaaaaaaaavuyx013a023a不失一般性，可以将一般距阵不失一般性，可以将一般距阵T中的中的a33作归一化处作归一化

11、处理，这样透视变换中的系数便降为理，这样透视变换中的系数便降为8个。利用这个。利用这8个系个系数，便可建立输入与输出图象中数，便可建立输入与输出图象中4个点的映射关系。个点的映射关系。假设假设 与与 （k=0，1，2，3）分别为输）分别为输入图象和输出图象中对应的四个点，由它们构成的点入图象和输出图象中对应的四个点，由它们构成的点对称为控制点对。将其代入变换式得：对称为控制点对。将其代入变换式得： 为一由为一由8个方程构成的方程组，求解便可得到个方程构成的方程组，求解便可得到8个系数个系数的值。从而得到平面四边形到平面四边形映射的一般的值。从而得到平面四边形到平面四边形映射的一般解。以下就一些

12、特殊情况作一讨论。解。以下就一些特殊情况作一讨论。kkvu ,kkyx ,vxauxaavauax2313312111vyauyaavauay2313322212（1）单位正方形到四边形的映射）单位正方形到四边形的映射考虑将考虑将uv平面的单位正方形映射成平面的单位正方形映射成xy平面的任意平面的任意四边形。其四个控制点对之间的关系如下：四边形。其四个控制点对之间的关系如下： 代入方程组，可得解（略）。代入方程组，可得解（略）。),()1 ,1(),()1 ,0(),()0,1(),()0,0(33221100yxyxyxyx（2）四边形到单位正方形的映射）四边形到单位正方形的映射是（是（1）

13、中问题的逆。）中问题的逆。（3）四边形到四边形映射）四边形到四边形映射一般四边形到四边形映射问题称为四角映一般四边形到四边形映射问题称为四角映射（射（four corner mapping）。透视变换提供了）。透视变换提供了平面四角映射问题的解。可分两步：首先将四平面四角映射问题的解。可分两步：首先将四边形映射成单位正方形；然后再将单位正方形边形映射成单位正方形；然后再将单位正方形映射成最终的四边形（如上图）。映射成最终的四边形（如上图）。5、多项式变换、多项式变换多项式变换的一般形式可表示为：多项式变换的一般形式可表示为：多项式变换最早用于遥感图象的几何校正。在实多项式变换最早用于遥感图象的

14、几何校正。在实际应用中，一般不直接给出多项式的系数，而是给出际应用中，一般不直接给出多项式的系数，而是给出输入、输出图象中一些位置已精确给定的控制点，利输入、输出图象中一些位置已精确给定的控制点，利用控制点来推导多项式的系数。用控制点来推导多项式的系数。用一般变换矩阵表示的所有变换都可用一阶多项用一般变换矩阵表示的所有变换都可用一阶多项式变换得到。当多项式阶数升高时，所能实现的变换式变换得到。当多项式阶数升高时，所能实现的变换种类和任意性也相应增加，但也会带来一些负作用。种类和任意性也相应增加，但也会带来一些负作用。 NiiNjjiijyxau00 NiiNjjiijyxbv00二、灰度级插值

15、二、灰度级插值几何运算的第二个要求是有进行灰度插值几何运算的第二个要求是有进行灰度插值的算法。在输入图象的算法。在输入图象u，v中，灰度值仅在整中，灰度值仅在整数位置上有定义。然而，输出图象数位置上有定义。然而，输出图象x，y的灰的灰度值一般由处在非整数坐标上的（度值一般由处在非整数坐标上的（u，v）值来）值来决定。因此，若将几何运算看成是一个从决定。因此，若将几何运算看成是一个从u，v到到x，y的映射，则的映射，则u，v中的一个象素可能中的一个象素可能会映射到会映射到x，y中几个象素之间的位置；反过中几个象素之间的位置；反过来也是如此。来也是如此。灰度插值有一些常用算法，它们完成的功灰度插值

16、有一些常用算法，它们完成的功能相同，可从中选择一个。而每个特定的几何能相同，可从中选择一个。而每个特定的几何运算是由空间变换算法决定的。运算是由空间变换算法决定的。插值算法插值算法插值是确定某个函数在两个采样值之间的插值是确定某个函数在两个采样值之间的数值时采用的运算过程。通常是利用曲线拟合数值时采用的运算过程。通常是利用曲线拟合的方法，通过离散的采样点建立一个连续函数，的方法，通过离散的采样点建立一个连续函数，用该重建的函数便可求出任意位置的函数值。用该重建的函数便可求出任意位置的函数值。对有限带宽的信号采样会产生无限带宽信对有限带宽的信号采样会产生无限带宽信号。插值过程正好相反，它通过对离

17、散信号作号。插值过程正好相反，它通过对离散信号作低通滤波处理，减小了信号带宽。其对采样数低通滤波处理，减小了信号带宽。其对采样数值的平滑作用，恢复了在采样过程中丢失的信值的平滑作用，恢复了在采样过程中丢失的信息。因此，插值可看作采样的逆过程。息。因此，插值可看作采样的逆过程。对于等间隔采样数据，插值可表示为：对于等间隔采样数据，插值可表示为：式中，式中，h为插值核，为插值核，Ci为权系数，卷积对为权系数，卷积对k个数据作处个数据作处理。在实际应用中，理。在实际应用中，h总是对称的，即：总是对称的，即： ， Ci为采样值。为采样值。插值核的性质可通过其频域特性来评估。理想的插值核的性质可通过其频

18、域特性来评估。理想的插值核在带通区具有单位增益，在带阻区有插值核在带通区具有单位增益，在带阻区有0增益，因增益，因此可以有效地通过和抑制不同频率的信号成分。此可以有效地通过和抑制不同频率的信号成分。插值算法的数值精度及计算复杂性直接与插值核插值算法的数值精度及计算复杂性直接与插值核有关。因此，插值核的设计与评价是插值算法的核心。有关。因此，插值核的设计与评价是插值算法的核心。以下讨论一维问题，其结果很容易推广到二维。以下讨论一维问题，其结果很容易推广到二维。10)()(kiiixxhCxf)()(xhxh常用的插值核常用的插值核1、最近邻域法、最近邻域法其插值核定义为：其插值核定义为：)()(

19、kxfxf2211kkkkxxxxx01)(xh5 . 00 xx5 . 0用该方法作放大处理时，在图象中可能出现明显的块状效应2、线性插值、线性插值线性插值多项式为：线性插值多项式为：其插值核为：其插值核为：01)(axaxf 01)(xxh10 xx13、三次样条插值、三次样条插值首先给定一组控制点：首先给定一组控制点：其中其中 ， ，要求构造，要求构造一个函数一个函数F（x），满足以下三个条件：），满足以下三个条件：（1）F（x），），F（x），），F”（x），在），在a，b上连续；上连续；（2）F（x）在每个子区间上是不高于三次的多项式；）在每个子区间上是不高于三次的多项式；（3） ，

20、（，（i = 0，1，-，n-1）),( ,),(),(111100nnyxyxyx)(xfy bxxxxan1210iiyxF)(4、双线性插值（二维情况）、双线性插值（二维情况）令令f（x，y）为两个变量的函数，其在单位正方形）为两个变量的函数，其在单位正方形顶点的值已知。假设我们希望通过插值得到正方形内顶点的值已知。假设我们希望通过插值得到正方形内任意点的函数值。则可由双线性方程任意点的函数值。则可由双线性方程 （1）来定义的一个双曲抛物面与四个已知点拟合。来定义的一个双曲抛物面与四个已知点拟合。首先对上端的两个顶点进行线性插值得：首先对上端的两个顶点进行线性插值得： （2）类似地，再对

21、底端的两个顶点进行线性插值有：类似地，再对底端的两个顶点进行线性插值有： （3）最后，做垂直方向的线性插值，以确定：最后，做垂直方向的线性插值，以确定： （4）dcxybyaxyxf),()0 , 0()0 , 1 ()0 , 0()0 ,(ffxfxf)1 , 0() 1 , 1 () 1 , 0() 1 ,(ffxfxf)0 ,() 1 ,()0 ,(),(xfxfyxfyxf整理得：（5）)0 , 0()0 , 1 () 1 , 0()0 , 0() 1 , 1 ()0 , 0() 1 , 0()0 , 0()0 , 1 (),(fxyffffyffxffyxf三、算法的实现三、算法的实

22、现1、向前映射法、向前映射法可以将几何运算想象成一次一个象素地转移可以将几何运算想象成一次一个象素地转移到输出图象中。如果一个输入象素被映射到四到输出图象中。如果一个输入象素被映射到四个输出象素之间的位置，则其灰度值就按插值个输出象素之间的位置，则其灰度值就按插值算法在算法在4个输出象素之间进行分配。称为向前映个输出象素之间进行分配。称为向前映射法，或象素移交影射。射法，或象素移交影射。注：注：从原图象坐标计算出目标图象坐标从原图象坐标计算出目标图象坐标 镜像、平移变换使用这种计算方法镜像、平移变换使用这种计算方法2、向后映射法、向后映射法向后映射法（或象素填充算法）是输出象向后映射法（或象素

23、填充算法）是输出象素一次一个地映射回到输入象素中，以便确定素一次一个地映射回到输入象素中，以便确定其灰度级。如果一个输出象素被映射到其灰度级。如果一个输出象素被映射到4个输个输入象素之间，则其灰度值插值决定，向后空间入象素之间，则其灰度值插值决定，向后空间变换是向前变换的逆。变换是向前变换的逆。注：注：从结果图象的坐标计算原图象的坐标从结果图象的坐标计算原图象的坐标 旋转、拉伸、放缩可以使用旋转、拉伸、放缩可以使用 解决了漏点的问题，出现了马赛克解决了漏点的问题，出现了马赛克由于许多输入象素可能映射到输出图象的边界由于许多输入象素可能映射到输出图象的边界之外，故向前映射算法有些浪费。而且，每个

24、输出之外，故向前映射算法有些浪费。而且，每个输出象素的灰度值可能要由许多输入象素的灰度值来决象素的灰度值可能要由许多输入象素的灰度值来决定，因而要涉及多次运算。如果空间变换中包括缩定，因而要涉及多次运算。如果空间变换中包括缩小处理，则会有小处理，则会有4个以上的输入象素来决定一个输个以上的输入象素来决定一个输出象素的灰度值（出象素的灰度值（重叠问题重叠问题）。如果含有放大处理，）。如果含有放大处理，则一些输出象素可能被漏掉（如果没有输入象素被则一些输出象素可能被漏掉（如果没有输入象素被映射到它们附近位置的话，会产生映射到它们附近位置的话，会产生“孔洞现象孔洞现象”）。）。而向后映射是逐象素、逐行地产生输出图象。而向后映射是逐象素、逐行地产生输出图象。每个象素的灰度值最多由每个象素的灰度值最多由4个输入象素参与的插值个输入象素参与的插值所唯一确定。当然，输入图象必须允许按空间变换所唯一确定。当然，输入图象必须允许按空间变换所定义的方式随机访问，因此可能有些复杂。但向所定义的方式随机访问，因此可能有些复杂。但向后映射法对一般的应用更为切实可行。后映射法对一般的应用更为切实可行。 3.2图象重采样 3.3抗混叠技术*几何运算的应用1、几何校正2、图象校直3、图象配准4、图象样式转换5、地图投影6、数字图象变形作业：下载一幅单色图象，用C语言编