数字图像处理概述 (27).ppt

27 链码和傅里叶描述子1链码 链码（又称为Freeman码）是用曲线起始点的坐标和边界点方向代码来描述曲线或边界的方法，常被用来在图像处理、计算机图形学、模式识别等领域中表示曲线和区域边界。它是一种边界的编码表示法，将图像中像素的绝对位置转换成了相对位置，用边界方向作为编码依据，为简化边界的描述，一般描述的是边界点集。27 链码和傅里叶描述子 根据链的斜率不同，常用的有4方向和8方向链码，其方向定义分别如图1(a)、(b)所示。在4方向链码中，四个方向码的长度都是一个像素单位；在8方向链码中，水平和垂直方向的方向码的长度都是一个像素单位，而对角线方向的四个方向码为 倍的像素单位。它们的共同特点是直线段的长度固定，方向数有限，因此可以利用一系列具有这些特点的相连的直线段来表示目标的边界，这样只有边界的起点需要用绝对坐标表示，其余点都可只用接续方向来代表偏移量。图1 链码值与方向的对应关系 从在物体边界上任意选取的某个起始点坐标开始，跟踪边界并赋给每两个相邻像素的连线一个方向值，最后按照逆时针方向沿着边界将这些方向码连接起来，就可以得到链码。链码的起始位置和链码完整地包含了目标的形状和位置信息。例如，在图2所示的以a为起点、箭头为走向的闭合边界，其8方向链码为：001711222433445676656。27 链码和傅里叶描述子a图2 以a为起点、箭头为走向的闭合边界 归一化链码 使用链码时，起点的选择很关键的。对同一个边界，如用不同的边界点作为链码的起点，得到的链码则是不同的。为解决这个问题可把链码归一化，具体做法如下：给定一个从任意点开始产生的链码，把它看作一个由各方向数构成的自然数。首先，将这些方向数依一个方向循环，以使它们所构成的自然数的值最小；然后，将这样转换后所对应的链码起点作为这个边界的归一化链码的起点。27 链码和傅里叶描述子 链码的旋转不变性 用链码表示给定目标的边界时，如果目标平移，链码不会发生变化，而如果目标旋转，则链码会发生变化。为解决这个问题，可利用链码的一阶差分来重新构造一个表示原链码各段之间方向变化的新序列，这相当于把链码进行旋转归一化。差分可用相邻两个方向数按反方向相减（后一个减去前一个）得到。27 链码和傅里叶描述子 如图3所示，上面一行为原链码（括号中为最右一个方向数循环到左边），下面一行为上面一行的数两两相减得到的差分码。左边的目标在逆时针旋转90后成为右边的形状，可见，原链码发生了变化，但差分码并没有变化。27 链码和傅里叶描述子图3 链码旋转归一化 27 链码和傅里叶描述子 2 傅里叶描述子 傅里叶描述子是一种图像特征，具体来说，是一个用来描述轮廓的特征参数。其基本思想是用物体边界信息的傅里叶变换作为形状特征，将轮廓特征从空间域变换到频域内，提取频域信息作为图像的特征向量。即用一个向量代表一个轮廓，将轮廓数字化，从而能更好地区分不同的轮廓，进而达到识别物体的目的。27 链码和傅里叶描述子 对边界的离散傅立叶变换表达，可以作为定量描述边界形状的基础。采用傅立叶描述的一个优点是将二维问题简化为一维问题。即将x-y平面中的曲线段转化为一维函数f(r)(在r-f(r)平面上)，也可将x-y平面中的曲线段转化为复平面上的一个序列。具体就是将 x-y平面与复平面 u-v重合，其中，实部 u轴与 x轴重合，虚部 v轴与 y轴重合。这样可用复数u+jv的形式来表示给定边界上的每个点(x，y)。这两种表示在本质上是一致的，是点点对应的，如图所示。图 1 边界点的两种表示方法 对于xy平面上一个由K个点组成的边界来说，任意选取一个起始点，然后沿着顺时针方向绕行一周，可以得到一个点序列：，。如果记，并把它们用复数形式表示，则得到一个坐标序列：s(k)=x(k)+jy(k)k=0,1,K-1（1）s(k)的离散傅立叶变换是：u=0,1,K-1（2）27 链码和傅里叶描述子其中，傅立叶系数S(u)可称为边界的傅立叶描述子，它的傅立叶逆变换是：k=0，1，K-1（3）由于傅立叶变换的高频分量对应一些细节，而低频分量对应基本形状，因此只利用S(u)的前M个系数来重构原来的图像，从而可以得到对s(k)的一个近似而不改变其基本形状，即：k=0，1，K-1（4）注意：式（4）中k的范围不变，即在近似边界上的点数不变，但u的范围缩小了，即为重建边界点所用的频率项少了。27 链码和傅里叶描述子27 链码和傅里叶描述子 傅立叶描述子可以很好地描述轮廓特征，并且只需少量的描述子（即向量中的数不需要太多）即可大致代表整个轮廓。其次，对傅立叶描述字进行简单的归一化操作后，即可使描述子具有平移、旋转、尺度不变性，即不受轮廓在图像中的位置、角度及轮廓的缩放等影响，是一个鲁棒性较好的图像特征。27 链码和傅里叶描述子傅立叶描述子傅立叶描述子