# 数字图像处理 ## 1 绪论 ### 1.1 数字图像与数字图像处理 数字图像的定义：将一幅二维图像用**有限**的**离散点**来表示的图像即称为数字图像 离散点：图像元素（像素） $\rightarrow$ **图像元素（像素）是构成一幅数字图像的最小单元** 数字图像的表示：一幅大小为$M\times N$的数字图像用矩阵表示为图像矩阵$G$。$G$中的每个元素$g_{ij}$具有两个属性： 1. 位置（$i,j$）（对应数组，左上角为（$1,1$）） 2. 像素值（即$g_{ij}$本身的取值，彩色图像通常为表示RGB的一个整数三元组，黑白图像则通常为表示灰度的一个整数） 数字图像处理的定义：利用**计算机**去处理数字图像的过程称为数字图像处理，因此数字图像处理又称计算机图像处理，简单来说包括以下范畴 1. 对数字图像的**增强** 2. 对数字图像的**分割** 3. 对数字图像的**复原** 4. 对数字图像进行**特征提取** 5. 对数字图像进行**几何变换** 6. 对数字图像进行**压缩编码** 8. ...... 数字图像处理的**本质特征**：从图像到图像的过程 ### 1.2 数字图像处理的主要研究内容 1. 图像的获取和表征，分别对应数字图像处理的起始点（图像摄取，光电转换，模拟信号数字化）与终结点（显示，打印，输出） 2. 图像的增强 1. 改善图像的视觉效果（eg：中值滤波降噪） 2. 突出图像中感兴趣的特征 ROI（region of interest） 3. 图像的分割：按一定的规则将数字图像分割成若干个不同的**区域**，将目标对象分割出来的过程称为图像分割（eg：边缘生长，灰度阈值） 4. 图像的几何变换：大小，位置，形状$\rightarrow$缩放，平移，镜像，旋转，错切 5. 图像的压缩编码：分为有损与无损压缩两种，通过对图像采取不同的**数据编码**，起到压缩图像的数据量的效果。 6. 其他... ### 1.3 数字图像处理与相关学科 1. 研究方法：数学，物理学，电子学，计算机科学 2. 研究范围：计算机图形学，模式识别，计算机视觉（机器视觉） ### 1.4 数字图像处理的应用领域（了解） 1. 医学，生物学 2. 地质，农林，水利，气象 3. 防伪、保密通信（嵌入置乱水印） 4. 其他... ### 1.5 数字图像处理系统的基本组成 1. 数字图像处理系统的硬件组成 1. 图像输入设备：图像采集等数字化设备 2. 图像处理计算机：PC或图形/图像工作站 3. 图像输出设备：图像的表征 2. 数字图像处理系统的软件组成 1. 应用软件：photoshop... 2. 数字图像程序开发工具：VC++，opencv，matlab... ## 2 数字图像处理基础 ### 2.1 图像数字化 * 数字化的定义：将连续的模拟图像经过离散化处理，转化为数字形式的过程称为图像数字化 模拟图像$\xrightarrow{离散化}$数字图像 模拟图像是连续的，体现在空间的连续性和灰度的连续性 数字图像是离散的，体现在空间的离散性（空间采样点）和灰度的离散性（整数值） * 数字化的过程涉及到两个重要环节： 1. 采样 连续图像在二维空间上的离散化，用空间上的部分点（即有限的采样点）代替整个图像 * 方法：先水平方向采样后垂直方向采样，反之亦可，得到采样行列进而得到采样点 * 与采样有关的重要参数包括: 1. 采样点总数$M\times N$，即空间分辨率 2. 采样间隔：对于同一幅图像上，采样间隔越小，$M\times N$越大，采样空间分辨率越大，失真度越小，细节越丰富 2. 量化 连续图像在灰度上的离散化，将采样点的灰度从连续量转化成整数值，也称灰度量化 * 方法： 1. 等间隔量化（均匀量化） 灰度范围等间隔分割 2. 非等间隔量化（非均匀量化） 频繁出现的灰度范围用小间隔量化，反之，较少出现的灰度范围则使用大间隔量化 * 与量化有关的重要参数包括： 1. 灰度级$L\rightarrow$灰度分辨率 2. 灰度值范围$0\sim L-1$，$L=2^i$（$i$表示像素灰度值所需的比特位数） 3. 存储灰度值的比特位数越多，灰度量化越精细 * 采样和量化与图像质量的关系 1. 在量化灰度级$L$不变的情况下，采样点总数$M\times N$越多，图像质量越高，反之图像出现出现块状效应，图像质量越低 2. 在采样点总数$M\times N$不变的情况下，量化灰度级$L$越多，图像越细腻，反之图像出现假轮廓，图像质量越低。（事实上$L$最小是$2$） 3. 总体原则： 1. 对于灰度缓变的图像，应采用细量化，避免出现假轮廓 2. 对于细节丰富的图像，应采用细采样，避免出现块状效应 * 采样，量化与图像数据量的关系 已知图像空间分辨率为$M\times N$，灰度级为$L$，则图像数据量为$\frac{M\times N}{8}bytes$ * 补充：数字图像的另一种表示 二维离散亮度函数$\begin{align} f(x,y) & = \left\{\begin{matrix} (x,y) &水平垂直坐标 \\ f & 灰度值 \end{matrix}\right. \end{align}$ * 数字化功能器件 1. 采样孔 2. 扫描机构 3. CCD光电传感器 $光\rightarrow 电$ 4. 量化器 ### 2.2 数字图像的基本类型 1. **灰度图像** 1. 含义：指包含灰度级的图像 2. **无彩色** 3. 灰度图像的表示：一个矩阵，每一个像素的像素值$g_{ij}=灰度值$ 2. 二值图像 1. 一种特殊的灰度图像，只有两种灰度值 2. 表示：一个矩阵，每一个像素的像素值$g_{ij}=\{0,1\}$ 3. 索引图像（带调色板的图像） 调色板：用于定义各种不同颜色的一个颜色表。每种颜色用R,G,B三个分量合成 一行对应一种颜色，不超过256行 表示：两个矩阵： 1. 调色板矩阵（$\leq 256行\times 3 列$） 2. 图像矩阵 $\begin{align} \left\{\begin{matrix} R=[r_{ij}]_{M\times N} \\ G=[g_{ij}]_{M\times N} \\ B=[b_{ij}]_{M\times N} \\ \end{matrix}\right. \ \ \ (0\leq r_{ij}, g_{ij}, b_{ij}\leq255) \end{align}$ 4. RGB图像 1. 每个像素的颜色由红，绿，蓝三分量共同决定 2. 各分量用8bit表示$=2^8 \times 2^8\times 2^8=2^{24}$ 3. 无调色板，每个像素的颜色值直接用R,G,B三个字节表示 4. 表示：三个颜色矩阵，分别表示红，绿，蓝三种颜色各自的深浅程度，叠加在一起显示出彩色图像 ### 2.3 数字图像的基本文件格式（存储格式） #### 2.3.1 BMP(Bitmap)文件格式（位图文件格式） 1. 扩展名：*.bmp 2. 特点： 1. 一个BMP文件只存一幅图像 2. 非压缩$\rightarrow$存储空间大 3. 颜色支持：单色，16色，256色，24位真彩色 4. bmp文件结构 1. 位图文件头 ```cpp typedef struct tagBITMAPFILEHEADER { * WORD bfType;//位图文件类型，必须是字符串"BM" * DWORD bfSize;//位图文件大小，包括这14个字节 WORD bfReserved1;//保留字，设为0 WORD bfReserved2;//保留字，设为0 * DWORD bfOffBits;//从文件头到实际的位图数据的偏移字节数 } BITMAPFILEHEADER; ``` `WORD`占2字节 `DWORD`占4字节 `BITMAPFILEHEADER`共占14字节 2. 位图信息头 ```cpp typedef struct tagBITMAPINFOHEADER{ * DWORD biSize;//本结构所占用字节数，大小为40字节 * LONG biWidth;//位图宽度，单位：字节 * LONG biHeight;//位图高度，单位：字节 WORD biPlanes;//目标设备级别，必须为1 * WORD biBitCount;//表示颜色时每个像素要用到的位数，常用的值为1(黑白二色图), 4(16色图), 8(256色), 24(真彩色图) DWORD biCompression;// 位图是否压缩，其类型是 0(BI_RGB不压缩), 1(BI_RLE8压缩类型)或2(BI_RLE4压缩类型) * DWORD biSizeImage;//实际的位图数据占用的字节数 LONG biXPelsPerMeter;//位图水平分辨率，每米像素数 LONG biYPelsPerMeter;//位图垂直分辨率，每米像素数 * DWORD biClrUsed;//指定本图象实际用到的颜色数，如果该值为零，则用到的颜色数为2^biBitCount个 DWORD biClrImportant;//指定本图象中重要的颜色数，如果该值为零，则认为所有的颜色都是重要的 } BITMAPINFOHEADER; ``` `WORD`占2字节 `DWORD`占4字节 `LONG`占4字节 `BITMAPINFOHEADER`共占40字节 3. 调色板 并非所有BMP文件都有调色板，24位真彩色图像就不需要调色板信息，这也是`BITMAPFILEHEADER.bfOffBits`的意义 调色板是一个数组，有`BITMAPINFOHEADER.biClrUsed`个元素，每个元素类型是`tagRGBQUAD` ```cpp typedef struct tagRGBQUAD { BYTE rgbBlue; //该颜色的蓝色分量(值范围为0-255) BYTE rgbGreen; //该颜色的绿色分量(值范围为0-255) BYTE rgbRed; //该颜色的红色分量(值范围为0-255) BYTE rgbReserved; //保留值，设为0 } RGBQUAD; ``` 4. 图像数据 1. 存储顺序：从下到上，从左到右（倒置） 2. 对于存储颜色$\leq 256$的BMP图像：带调色板的索引图像，每个像素点存对应颜色在调色板中的索引号 单色：1 bit/pixel 16色：4 bit/pixel 256色：8 bit/pixel=1 Byte/pixel 3. 对于24位真彩色的BMP图像：是不带调色板的RGB图像，每个像素点存R,G,B分量的值 3 Byte/pixel 5. 数据段大小关系 | 数据段 | 大小 | | -------- | ---------- | | 文件头 | 14 | | 信息头 | 40 | | 调色板 |bitClrUsed*4/无 | | 图像数据 | | bfOffBits=文件头+信息头+调色板 biSize=信息头 bfSize=文件头+信息头+调色板+图像数据 bfSizeimage=图像数据 #### 2.3.2 GIF（Graphics Interchange Format）文件格式 1. 实质：一种图像传输格式 2. 主要应用于网络环境（动图） 3. 一个gif文件可以存储一幅或多幅图像，其文件内部可以有多个图像数据区 4. 颜色支持最多256种，色彩范围比较局限 5. gif采用无损压缩存储数据 #### 2.3.3 JPEG（Joint Photographic Experts Group）文件格式 1. 实质：一种图像压缩格式 2. 主要应用于网络环境（高压缩率） 3. jpg==jpeg 4. 颜色支持可达24位真彩色 5. jpeg采用有损压缩存储数据 #### 2.3.4 TIFF（Tag Image File Format）文件格式 1. 实质：一种标记图像格式，可以灵活支持不同的颜色格式 2. 主要应用于出版印刷行业（CMYK） ### 2.4 颜色模型 #### 2.4.1 基本概念 颜色分类： 1. 非彩色：黑灰白 2. 彩色：其余所有 颜色属性： 1. 色调 2. 饱和度 3. 亮度 颜色模型： 1. 计算颜色模型，面向理论研究（RGB） 2. 视觉颜色模型，面向色彩处理（HSV/HSI） 3. 工业颜色模型，面向实际以应用（CMYK） #### 2.4.2 RGB模型 1. 使用RGB作为三基色 2. 加色合成法：三基色按不同比例混合得到目标颜色 3. 模型表示：三维空间中的单位立方体（经过了归一化处理）  4. 三元组（RGB）表示一个颜色 5. 灰色线：黑灰白 三分量相等 6. 三补色：黄蓝，品红绿，青红 #### 2.4.3 HSV模型 1. 使用色调，饱和度，色明度作为基本属性 2. 模型表示：圆柱坐标系中的一个倒置圆锥体  3. 色调H：代表颜色的种类；绕过追至中心轴的旋转角度；补色与基色相差180度 4. 饱和度S：表示颜色的纯度；纯光谱完全饱和，添加白光可以稀释饱和度；饱和度越高越鲜艳，饱和度越低越发灰；$0\leq S\leq 1$，0时为非彩色 5. 色明度V：表示颜色明暗程度； 6. 垂直中心轴：灰色线 7. HSV应用于画家配色方法 #### 2.4.4 CMYK模型 1. 应用于工业印刷 2. 减色合成法 3. 三元组（C,M,Y）表示，即三补色 4. **CMY与RGB之间的转换关系** $\begin{align} \begin{bmatrix} C\\M\\Y \end{bmatrix} = \begin{bmatrix} 1\\1\\1 \end{bmatrix}- \begin{bmatrix} R\\G\\B \end{bmatrix} \end{align}$ 5. K表示黑色，在印刷工业中因为黑灰色使用偏多，故直接引入黑色，以减少彩色油墨使用量 ## 3 图像增强  ### 3.1 灰度直方图 1. 含义 1. 是灰度值的函数，一种统计特性 2. 统计具有每种灰度值的像素个数或频率（每种灰度值出现的频数或频率） 2. 计算 已知$r_k$，求$P(r_k)=\frac{n_k}{n}$ 1. 一位数组初始化 2. 循环遍历统计 3. 归一化处理 3. 性质 1. 不保留位置信息，与几何操作无关 2. 图像与直方图之间的关系是**一对多**的，即一幅图像只对应唯一的灰度直方图，但一个灰度直方图可能对应多个不同的图像 3. 相加性：一个图像的灰度直方图等于其多个互不相重叠的多个子区域的灰度直方图的加和 4. 直方图均衡化 1. 作用：提高对比度（提高灰度反差大小，直观的来说就是让图像亮暗部分清晰分明） 2. 基本思想：利用一种灰度变换，将原始图像的直方图变成均匀分布的形式\begin{align}g(x)=T[f(x,y)] \end{align} 1. 扩展像素灰度分布的动态范围（由窄到宽）$\Rightarrow$直方图拉伸 2. 灰度级概率分布平均（令直方图近似均匀平坦） 3. 处理过程 1. 已知原始图像的直方图：$P(r_k)=\frac{n_k}{n}$ 2. 采用**累积分布函数**作灰度变换 $\begin{align}S(k)=T(r_k)\left\{\begin{matrix} 0\leq r_k \leq 1 \ \ \ \ \ \ 0\leq r_k \leq 1 \\ S_k在0\leq r_k \leq 1内单调递增 \end{matrix}\right. \end{align}$ 3. 其离散形式：$S_k=T(r_k)=\sum_{j=0}^{k}\frac{n_j}{n}=\sum_{j=0}^{k}P(r_j)$ $r_k \xrightarrow{映射}S_k$ 将$f(x,y)$中的所有灰度级$r_k$的像素点，当前取灰度级$S_k$得到$g(x,y)$ 4. 将$S_k$转化成标准灰度级值$=round(S_k\times (L-1))$ 5. 说明：原图像当中处于同一灰度级的像素，经过灰度变换以后仍均处于同一灰度级 6. 注意：由于直方图均衡化过程要求原先处于同一灰度级的像素，经过灰度变换以后仍均处于同一灰度级，因此有可能会出现"简并"现象：灰度级减少（即原先出现的灰度级在新图像中没有出现） 4. 例程 ```javascript boy=imread('pout.tif'); [n,m]=size(boy); gcnt=zeros(1,256); after_gcnt=zeros(1,256); tcnt=zeros(1,256); for i=1:256 gcnt(i)=length(find(boy==(i-1)))/(m*n); end tmp=0; for i=1:256 tmp=tmp+gcnt(i); tcnt(i)=tmp; end tcnt=round(tcnt*255); for i=1:256 after_gcnt(i)=sum(gcnt(find( tcnt==(i-1)))); end for i=1:n for j=1:m boy(i,j)=tcnt(boy(i,j)+1); end end bar(0:255,after_gcnt); imshow(boy); ``` ### 3.2 基本的灰度变换 灰度变换：将原始图像的灰度级，经过某种灰度变换函数，映射成新的灰度级 \begin{align} f(x,y)=T[g(x,y)] \end{align} 分类： 1. 直接灰度变换 1. 线性：正比，反比 2. 分段线性 3. 非线性：幂次，对数 2. 直方图修正 1. 均衡化  #### 3.2.1 线性灰度变换 一般式：$S=T(r)=\frac{d-c}{b-a}(r-a)+c$ 1. 正比变换 $S=T(r)=r$ 作用：图像灰度保持不变 2. 反比变换 $S=T(r)=(L-1)-r$ 作用：负像效果 3. 说明：通过调整变换曲线的位置和斜率（即a,b,c,d)四个参数，从而达到**扩展或压缩某些灰度范围（灰度区间）的作用** 4. 效果：灰度范围增大$\Rightarrow$灰度级间隔增大$\Rightarrow$灰度反差增大$\Rightarrow$对比度增加$\Rightarrow$清晰度增加 #### 3.2.2 分段线性灰度变换 应用最多的为三段式 \begin{align} (0,0)\rightarrow (a,c)\rightarrow (b,d)\rightarrow (L-1,L-1)\\ S=T(r)=\left\{\begin{matrix} \frac{c}{a}r&0\leq r<a\\ \frac{d-c}{b-a}(r-a)+c&a\leq r<b\\ \frac{L-1-d}{L-1-b}(r-b)+d&b\leq r<L-1\\ \end{matrix}\right. \end{align} 通过调整折线拐点和分段直线的斜率从而达到**扩展或压缩某些灰度范围（灰度区间）的作用** 事实上我们将兴趣范围锁定在$[a,b]$之间，强化该部分内容的显示效果 #### 3.2.3 幂次变换（$\gamma$变换） 基本式：$S=T(r)=c\cdot r^\gamma$ 令$c=1$，讨论$\gamma$ 1. $\gamma =1$，正比变换 2. $\gamma <1$ 曲线在正比曲线上方，灰度级提高，整幅画面亮度提高 低灰度范围扩展，高灰度范围压缩 4. $\gamma >1$， 曲线在正比曲线下方，灰度级减小，整幅画面亮度降低 低灰度范围压缩，高灰度范围扩展  #### 3.2.4 对数变换 基本式：$S=T(r)=a+\frac{lg(1+r)}{c\cdot lgb}$ ### 3.3 图像噪声 * 含义：对图像正常亮度分布起干扰作用的亮度分布，成为图像噪声$err(x,y)$ \begin{align} f(x,y)=e(x,y)+g(x,y) \end{align} * 表现：原始图像中出现许多随机分布的，亮度不协调的像素点$\rightarrow$**图像模糊甚至淹没图像的特征** * 两种典型噪声： 1. 高斯噪声：服从高斯分布 2. 椒盐噪声：盐噪声（纯白点）与胡椒噪声（纯黑点） * 噪声的三个特点： 1. 随机性：分布，大小不规则 2. 噪声和图像之间的相关性 3. 噪声具有叠加性 * 噪声产生的原因： 1. 系统外部干扰：电磁波形式 2. 系统内部干扰 1. 光电性质引起 2. 元器件的机械运动 3. 元器件本身的质量缺陷 4. 设备内部的电路之间的干扰 * 描述噪声的数学特征量 1. 均方误差 用来描述变换前后图像的差异程度 \begin{align} MSE=\frac{1}{MN}\sum_{x=0}^{M-1}\sum_{y=0}^{N-1}[g(x,y)-f(x,y)]^2 \end{align} 2. 峰值信噪比 用来表示信号最大可能功率和影响它的表示精度的破坏性噪声功率的比值 PSNR越高说明压缩质量越好 \begin{align} PSNR=10\cdot lg(\frac{(max(i))^2}{MSE}) \end{align} ### 3.4 图像平滑 * 图像平滑的主要作用：在保留图像基本特征的前提下，尽可能消除或衰减噪声 * 模板及模板运算 模板，即滤波器，是一个固定大小的矩阵，用来表示邻域的概念，其中的各个元素表示加权平均系数，其中心元素带有$X^*$被称为中央系数 \begin{align} \begin{bmatrix} P1 &P2 &P3 \\ P4 &P5 &P5 \\ P6&P7 &P7 \end{bmatrix}* \begin{bmatrix} H1 &H2 &H3 \\ H4 &H5^* &H5 \\ H6 &H7 &H7 \end{bmatrix}\end{align} 如有模板：\begin{align} \frac{1}{9}\begin{bmatrix} 1 & 1&1 \\ 1& 1^* & 1\\ 1&1 &1 \end{bmatrix} \end{align} 则原图像转换前后为：\begin{align} \begin{bmatrix} 1 &2 &1 & 4 &3 \\ 1 & 2 & 2 & 3 &4 \\ 5& 7& 6 & 8 &8 \\ 5& 6& 7 & 8 &9 \end{bmatrix}\rightarrow \begin{bmatrix} - & - & - & - & -\\ - & 3 &4 &4 & -\\ - & 5 &5 & 5 & -\\ - &- &- &- &- \end{bmatrix} \end{align} 针对边界像素无法处理到的问题，可以采取保持边界像素不变，或是边界像素扩展两种方法处理边界像素 \begin{align} \begin{bmatrix} 1 &2 &1 & 4 &3 \\ 1 & 2 & 2 & 3 &4 \\ 5& 7& 6 & 8 &8 \\ 5& 6& 7 & 8 &9 \end{bmatrix}\rightarrow \begin{bmatrix} 1 & 2 & 1 & 4 &3\\ 1 & 3 &4 &4 & 4\\ 5 & 5 &5 &6 &8\\ 5 &6 &7 &8 &9 \end{bmatrix} \end{align} \begin{align} \begin{bmatrix} 1 &1 &2 &1 &4 &3 &3 \\ 1 & 1 &2 &1 &4 & 3 &3 \\ 1 &1 &2 &2 &3 &4 &4 \\ 5 &5 &7 &6 &8 &8 &8 \\ 5 &5 &6 &7 &8 &9 &9 \\ 5 &5 &6 &7 &8 &9 &9 \end{bmatrix}\rightarrow \begin{bmatrix} 1 & 1 & 2 & 3 &3\\ 3 & 3 &4 &4 & 5\\ 4 & 5 &5 &6 &7\\ 5 &6 &7 &8 &8 \end{bmatrix} \end{align} * 空间域平滑方法 1. 均值滤波（邻域平均法） 模板大小$N\times N$ ，系数均为$\frac{1}{N^2}$，这种模板也被称为box模板 实际上是把每一个像素以其邻域内所有像素的灰度均值代替 在一定程度上可以降低噪声，**但是会造成图像的边缘轮廓细节的模糊**（二者实质上具有共性，噪声像素是与周围不协调的突变像素，但事实上边界像素通常也存在灰度突变的现象，因此也被抑制） 高斯模板常用于**去除高斯噪声**，其考虑了距离当前中间像素距离的影响，即距离当前中心像素越近的点，分配的权重越大 \begin{align} Gauss\ Template: \frac{1}{16}\begin{bmatrix} 1 &2 &1 \\ 2 &4^* & 2\\ 1 &2 &1 \end{bmatrix} \end{align} 2. 中值滤波 将某个像素的灰度值，用以该像素为中心的窗口内的所有像素的灰度中值来代替 窗口的形状各异，一般来说分为线状，十字，方形，菱形，圆形，但都**必须保证窗口内像素总和为奇数个** 中值滤波常用于**去除椒盐（脉冲）噪声**，相比于均值滤波可以**较好的保留图像的边缘轮廓细节** ### 3.5 图像锐化 * 图像锐化的主要目的：突出增强图像中的**边缘轮廓细节**，是模糊的图像变清晰 * 图像模糊的实质：是图像因采集或传播中的各种因素导致其收到了不同程度的平均处理，进而导致边缘细节出现丢失的情况 * 图像锐化空间域上的处理方法 * 梯度算法（基于一阶微分） * 拉普拉斯算法（基于二阶微分） * 梯度算法（基于一阶微分） 1. 梯度的定义 * 在点$(x,y)$处$f(x,y)$的梯度定义为以下矢量（实质上是变化剧烈幅度） \begin{align} \nabla f(x,y)=\begin{bmatrix} G_x\\ G_y \end{bmatrix}=\begin{bmatrix} \frac{\partial f(x,y)}{\partial x}\\ \frac{\partial f(x,y)}{\partial y}\\ \end{bmatrix} \end{align} * 其梯度幅值（即梯度矢量的模）定义为 \begin{align} |\nabla f(x,y)|=\sqrt{G_x^2+G_y^2}=\sqrt{\frac{\partial f(x,y)}{\partial x}^2+\frac{\partial f(x,y)}{\partial y}^2} \end{align} * **重要说明：本课程当中所说的梯度实质上是梯度幅值的简称** * **重要说明：本课程当中所说的梯度幅值一般通过近似计算得到（用绝对值代替平方与平方根运算）** \begin{eqnarray} |\nabla f(x,y)|&=&\sqrt{G_x^2+G_y^2}=\sqrt{\frac{\partial f(x,y)}{\partial x}^2+\frac{\partial f(x,y)}{\partial y}^2}\\ &\approx&|G_x|+|G_y|=|\frac{\partial f(x,y)}{\partial x}|+|\frac{\partial f(x,y)}{\partial y}| \end{eqnarray} 2. 几个典型的梯度算子 * 梯度算子：类似于模板，是大小为$N\times N$的方阵，包含$N^2$个加权系数 * 问题设定：设一个$3\times 3$邻域，$Z_1～Z_9$表示相邻9个像素，求像素点$Z_5$处的梯度。 1. 水平垂直微分法 $\begin{eqnarray} \nabla f_{Z_5}&=&|G_x|+|G_y|=|\frac{\partial f(x,y)}{\partial x}|+|\frac{\partial f(x,y)}{\partial y}|\\ &=&|Z_6-Z_5|+|Z_8-Z_5| \end{eqnarray}$ 上述梯度计算可由两个模板完成，第一个模板用于求梯度的第一项，第二个模板用于求梯度的第二项 $\begin{bmatrix} -1^* &1\\ 0 &0\\ \end{bmatrix}$和$\begin{bmatrix} -1^* &0\\ 1 &0\\ \end{bmatrix}$ 2. 交叉差分法（Roberts差分法） $\begin{eqnarray} \nabla f_{Z_5}&=&|G_x|+|G_y|=|\frac{\partial f(x,y)}{\partial x}|+|\frac{\partial f(x,y)}{\partial y}|\\ &=&|Z_8-Z_6|+|Z_9-Z_5| \end{eqnarray}$ 上述梯度计算可由两个模板完成，第一个模板用于求梯度的第一项，第二个模板用于求梯度的第二项 $\begin{bmatrix} 0* &-1\\ 1 &0\\ \end{bmatrix}$和$\begin{bmatrix} -1^* &0\\ 0 &1\\ \end{bmatrix}$ 3. Prewitt差分法 $\begin{eqnarray} \nabla f_{Z_5}&=&|G_x|+|G_y|=|\frac{\partial f(x,y)}{\partial x}|+|\frac{\partial f(x,y)}{\partial y}|\\ &=&|(Z_3+Z_6+Z_9)-(Z_1+Z_4+Z_7)|\\ &+&|(Z_7+Z_8+Z_9)-(Z_1+Z_2+Z_3)| \end{eqnarray}$ 上述梯度计算可由两个模板完成，第一个模板用于求梯度的第一项，第二个模板用于求梯度的第二项 $\begin{bmatrix} -1 &0 &1\\ -1 &0^* &1\\ -1 &0 &1 \end{bmatrix}$和$\begin{bmatrix} -1 &-1 &-1\\ 0 &0^* &0\\ 1 &1 &1 \end{bmatrix}$ 4. Sobel差分法 $\begin{eqnarray} \nabla f_{Z_5}&=&|G_x|+|G_y|=|\frac{\partial f(x,y)}{\partial x}|+|\frac{\partial f(x,y)}{\partial y}|\\ &=&|(Z_3+2Z_6+Z_9)-(Z_1+2Z_4+Z_7)|\\ &+&|(Z_7+2Z_8+Z_9)-(Z_1+2Z_2+Z_3)| \end{eqnarray}$ 上述梯度计算可由两个模板完成，第一个模板用于求梯度的第一项，第二个模板用于求梯度的第二项 $\begin{bmatrix} -1 &0 &1\\ -2 &0^* &2\\ -1 &0 &1 \end{bmatrix}$和$\begin{bmatrix} -1 &-2 &-1\\ 0 &0^* &0\\ 1 &2 &1 \end{bmatrix}$ * 2\*2梯度算子的主要特点 * 模板大小为偶数，中心位置不明显 * 对噪声敏感 * 3\*3梯度算子的主要特点 * 模板大小为奇数，中心位置明显 * 由于引入了平均因素，对噪声有一定的抑制作用 * Sobel算子突出了最近像素的影响，噪声抑制效果比Prewiitt算子更优 * 梯度算法小结 * 梯度的大小反映了灰度变化的程度 * 灰度均匀无变化，其梯度为0 * 灰度变化平缓，其梯度较小 * 灰度变化剧烈（例如边缘轮廓细节处），其梯度较大 * 主要应用于边缘检测，与后面介绍的拉普拉斯变换算法应用于细节增强各有偏重 * 利用梯度生成梯度增强图像的方式 设$f(x,y)$表示原始图像，$\nabla f(x,y)$表示梯度，$g(x,y)$表示生成的梯度增强图像 * 方式1 直接以梯度值替代 $\begin{align} g(x,y)=\nabla f(x,y) \end{align}$ * 方式2 设定一门限值，小于门限值的用梯度替代 $\begin{align} g(x,y)=\left\{\begin{matrix} \nabla f(x,y) &\nabla f(x,y)\leq T\\ f(x,y) &else \end{matrix}\right. \end{align}$ * 方式3 给边缘设定一个特定灰度级 $\begin{align} g(x,y)=\left\{\begin{matrix} R_1 &\nabla f(x,y)\geq T\\ f(x,y) &else \end{matrix}\right. \end{align}$ * 方式4 给背景设定一个特定灰度级 $\begin{align} g(x,y)=\left\{\begin{matrix} \nabla f(x,y) &\nabla f(x,y)\leq T\\ R_2 &else \end{matrix}\right. \end{align}$ * 方式5 利用梯度二值化图像 $\begin{align} g(x,y)=\left\{\begin{matrix} R_1 &\nabla f(x,y)\leq T\\ R_2 &else \end{matrix}\right. \end{align}$ 这种方式可以形成二值图像 * 拉普拉斯算法（基于二阶微分） * 拉普拉斯变换的定义 在$(x,y)$处$f(x,y)$的拉普拉斯变换定义为 \begin{align} \nabla ^2 f(x,y)=\frac{\partial ^2 f(x,y)}{\partial x^2}+\frac{\partial ^2 f(x,y)}{\partial y^2} \end{align} * 第一种拉普拉斯算子 不考虑对角线方向上使用拉普拉斯变换 $\begin{eqnarray} \nabla^2f_{Z_5}&=&\frac{\partial ^2 f(x,y)}{\partial x^2}+\frac{\partial ^2 f(x,y)}{\partial y^2}\\ &=&[(Z_6-Z_5)-(Z_5-Z_4)]+[(Z_8-Z_5)-(Z_5-Z_2)] \\ &=&Z_2+Z_4+Z_6+Z_8-4Z_5 \\ \end{eqnarray}$ 于是，其也可以通过一个模板去完成求变换结果的过程（非最终图像） $\begin{bmatrix} 0 & 1 &0\\ 1 & -4^* &1\\ 0 & 1 &0\\ \end{bmatrix}$ * 第二种拉普拉斯算子 考虑对角线方向上使用拉普拉斯变换 这里我们直接给出结论 $\begin{eqnarray} \nabla^2f_{Z_5}&=Z_1+Z_2+Z_3+Z_4+Z_6+Z_7+Z_8+Z_9-8Z_5 \end{eqnarray}$ 于是，其也可以通过一个模板去完成求变换结果的过程（非最终图像） $\begin{bmatrix} 1 & 1 &1\\ 1 & -8^* &1\\ 1 & 1 &1\\ \end{bmatrix}$ * 利用拉普拉斯变换生成锐化图像的基本方法 设$f(x,y)$表示原始图像，$\nabla^2 f(x,y)$表示拉普拉斯变换，$g(x,y)$表示生成的梯度增强图像 1. 对于模板中心取负的拉普拉斯算子 $g(x,y)=f(x,y)-\nabla^2 f(x,y)$ * $Z'_5=5Z_5-Z_2-Z_4-Z_6-Z_8$ 于是，其也可以通过一个合成算子模板去完成这一过程 $\begin{bmatrix} 0 & -1 &0\\ -1 & 5^* &-1\\ 0 & -1 &0\\ \end{bmatrix}$ * $Z'_5=9Z_5-Z_1-Z_2-Z_3-Z_4-Z_6-Z_7-Z_8-Z_9$ 于是，其也可以通过一个合成算子模板去完成这一过程 $\begin{bmatrix} -1 & -1 &-1\\ -1 & 9^* &-1\\ -1 & -1 &-1\\ \end{bmatrix}$ 直接在原始图像$f(x,y)$用以上的合成算子作模板运算就可以直接输出图像$g(x,y)$ 2. 对于模板中心取正的拉普拉斯算子 结论同上，不再赘述 ## 4 图像分割 ### 4.1 图像分割的基本概念 1. 图像分割 * 图像分割是根据图像的**灰度**（本章主要强调部分），颜色，纹理和边缘等特征将图像划分成若干个区域的过程，每个区域代表被成像的一个物体（或部分） * 图像分割的基础前提：图像中同一区域内部所考虑的特征是相同的或相近的，但这些特征在不同区域中则是不同的或是存在差异的 2. 区域及其联通性 * 区域：是指一个联通区域，即像素的联通集合 * 像素之间的联通性：在一个联通集合中，任意两个像素之间都存在一条完全由该联通集合中的像素所构成的联通路径 * 数字图像中的两种联通准则：4联通（L，U，R，D）与8联通（L，LU，U，RU，R，RD，D，LD） $ConnectedGraph_4 \subseteq ConnectedGraph_8$ 3. 图像分割方法分类 * 图像分割一般基于相似灰度的两个性质 * 基于相同区域内相邻像素灰度的相似性 * 基于不同区域间相邻像素灰度的不连续性  ### 4.2 灰度阈值分割 * 基本思想： 用一个或几个灰度阈值（也称灰度门限值）将图像的灰度级范围分为几个部分（几个子范围），然后将每个像素的灰度值和阈值相比较，根据比较结果把像素归类——前景目标物体或背景 * 基本步骤 1. **确定阈值** 最为重要，阈值的确定将直接影响分割效果 2. 将像素灰度值与阈值进行比较 3. 将像素归类 * 确定阈值的方法类型 * 全局阈值 选取的阈值仅与各个像素的灰度有关 * 局部阈值 选取的阈值与像素本身及其邻域的某种局部性质有关（充分借助像素及像素邻域的信息） * 动态阈值（自适应阈值） 选取的阈值不仅与局部性质有关，还与像素的位置有关（进一步考虑了像素位置的权重影响） \begin{align} T=T[f(x,y),p(x,y),(x,y)] \end{align} * 确定阈值的常用方法 1. 利用灰度直方图确定阈值 通常可根据相邻两峰的谷底确定**多个**阈值（可能存在多峰）  可以在相邻两峰之间的谷底处选取一个灰度值作为阈值，进行分割 该方法主要适用于目标物体与背景之间存在较高对比度，且二者占据不同的灰度级范围的情况 该方法具有较强的局限性，难以区分开直方图较为平均的情况 分割误差 * 背景错分成目标 * 目标错分成背景 2. 迭代法确定最优阈值 1. 选择一个初始阈值$T_1$ * 当目标物体与背景的面积相当时，可选$T_1=Avg_n$ * 当目标物体与背景的面积相差较大时，可选$T_1=Med_n$ 2. 根据阈值$T_1$，将图像分割为$G_1$，$G_2$两部分 $\forall (x,y) \in G_1, f(x,y)\leq T_1$，$\forall (x,y) \in G_2, f(x,y)> T_1$ 3. 分别计算$G_1$，$G_2$的灰度平均值$\mu_1$，$\mu_2$ 4. 计算新的阈值$T_2=(\mu_1+\mu_2)/2$ 5. 如果$|T_2-T_1|\leq eps$，迭代终止，否则$T_1=T_2$，重复2，3，4，5步 6. 最后输出$T_2$即为所求阈值 3. 利用最小化误差概率确定最优阈值 * 基本思想 有时用某个阈值很难准确地把目标物体与背景分割开，总会出现分割误差，因此选择一个阈值$T$，使得划分像素时所产生的总误差概率最小 即要能构造出阈值$T$与总误差概率之间的函数关系 * 基本原理 * 假设原图像中只包含两个主要的灰度区域（背景和前景目标物体） * 令$z$表示灰度级，$p(z)$表示灰度级概率密度函数 * 设对应于背景的灰度级概率密度函数为$p_1(z)$，对应于目标物体的灰度级概率密度函数为$p_2(z)$ * 设$P_1$为背景像素出现的概率，$P_2$为目标物体像素出现的概率 * 描述图像整体灰度的混合概率密度函数定义为： $p(z)=P_1\cdot p_1(z)+P_2\cdot p_2(z)$ * 若设置阈值$T$，使得灰度值小于$T$的像素化归为背景，使得灰度值大于$T$的像素化归为目标物体 则把目标物体像素化归为背景的误差概率定义为： $E_1(T)=\int_{-\infty}^{T}p_2(z)dz$ 则把背景像素化归为目标物体的误差概率定义为： $E_1(T)=\int_{T}^{+\infty}p_1(z)dz$ * 则总误差概率为 $E(T)=P_2E_1(T)+P_1E_2(T)$ * 求导可得$min(E(T))$在$P_1\cdot p_1(T)=P_2\cdot p_2(T)$取到，此时总误差概率最小 * ATT：当背景与目标的灰度分布均服从于正态分布时，设背景，目标的灰度平均值分别为$\mu_1,\mu_2$，则最优阈值为$\begin{align}\frac{\mu_1+ \mu_2}{2}\end{align}$ 4. 最大类间方差法确定最优阈值（Otsu法） * Otsu法的准则是：使分割后的两个像素类（前景物体与背景）的类间方差最大（事实上等同于错差概率最小） * 基本原理： * 设图像中像素的总个数$N$，灰度级总数为$L$，灰度值为$i$的像素个数为$N_i$ * 灰度级$i$出现的概率$P_i$为：$P_\frac{N_i}{N}$ * 像素总个数满足$N=\sum_{i=0}{L-1}N_i$ * 设阈值$T$将所有像素分为两类，目标物体像素类$C_1$，背景像素类$C_2$， $\forall (x,y) \in C_1, f(x,y)< T$，$\forall (x,y) \in C_2, f(x,y)\geq T$ * 则整幅图像的灰度平均值为： $\begin{align} \mu=\frac{1}{N} \sum_{i=0}^{L-1} i \cdot N_{i}=\sum_{i=0}^{L-1} \frac{i \cdot N_{i}}{N}=\sum_{i=0}^{L-1} i \cdot P_{i} \end{align}$ * $C_1$类像素的灰度平均值为 $\begin{eqnarray} \mu_1&=&\frac{\sum_{i=0}^{T-1}i\cdot N_i}{\sum_{i=0}^{T-1} N_i}\\ &=&\frac{\sum_{i=0}^{T-1}i\cdot P_i}{\omega_1} \end{eqnarray}$ * $C_2$类像素的灰度平均值为 $\begin{eqnarray} \mu_1&=&\frac{\sum_{i=T}^{L-1}i\cdot N_i}{\sum_{i=0}^{T-1} N_i}\\ &=&\frac{\frac{1}{N}(\sum_{i=0}^{L-1}i\cdot N_i-\sum_{i=0}^{T-1}i\cdot N_i)}{\omega_2} \\ &=&\frac{\mu-\sum_{i=0}^{T-1}i\cdot P_i}{\omega_2} \end{eqnarray}$ * $C_1$类像素出现的概率为 $\begin{align} \omega_1=\frac{1}{N}\sum_{i=0}^{T-1}N_i=\sum_{i=0}^{T-1}\frac{N_i}{N}=\sum_{i=0}^{T-1}P_i \end{align}$ * $C_2$类像素出现的概率为 $\begin{align} \omega_2=1-\omega_1 \end{align}$ * 最终我们可以得到类间方差为 $\begin{align} \sigma^2(T)=\omega_1(\mu-\mu_1)^2+\omega_2(\mu-\mu_2)^2 \end{align}$ * 令$T$从$0-L-1$内变换，计算在不同$T$值下的类间方差$\sigma^2(T)$，取其最大值 * 类间方差+类内方差=图像总方差（常数） 在类间方差最大的情况下类内方差取到最小值 5. 直方图变换法 * 问题：当目标物体和背景的面积差别很大时，在灰度直方图上就会表现出较小的一方被较大的一方淹没 * 解决：直方图变换法，利用某种局部性质，使原先的直方图变成具有更深波谷或更突出波峰的直方图，使其更容易被检测到 * 基本原理： * 由微分算子的性质可知，目标与背景内部像素的梯度小而目标与背景之间的边界像素的梯度大。可以根据像素的梯度值或灰度级的平均梯度作出一个加权直方图 * 一个简单的思路就是只作出具有高/低梯度值的像素直方图，分别在峰/谷突出边界像素，其峰/谷主要由边界像素构成，对应峰/谷的灰度级可作为分割阈值 6. 动态阈值法 * 问题：由于各种实际因素，单一的全局阈值对整幅图像进行分割，则某些区域的分割效果好而另一些区域的分割效果可能很差 * 解决：动态阈值法（或自适应阈值法） * 划分成多个小区域，各区域内依然调用上述算法完成运算，效果比较好 ### 4.3 基于区域的分割 1. 区域生长法 * 基本思想 把具有相似性质的像素逐渐结合起来生成区域 * 基本步骤 1. 首先对要分割的区域确定一个种子像素（也称为生长核）作为生长的起点； 2. 根据灰度、颜色、纹理或梯度等特性，确定生长过程中使用的一个相似性准则； 3. 从种子像素开始向外扩张：首先以种子像素构成一个当前集合，然后不断将与当前集合中各个像素连通的（4连通或8连通）、并且满足相似性准则的像素加入到当前集合中。最后直到不再有满足条件的新像素加入到当前集合为止，即再没有可接受的邻域像素时停止生长 2. 区域合并与分裂法 * 基本思想 按照某种一致性准则，不断地分裂或合并区域 通常是先进行分裂再进行合并 * 基本步骤 $R$表示区域，$T$表示一致性准则 1. 将整幅图像作为初始区域开始分割 2. 对于区域$R_i$，若$T(R_i)=false$，则分裂$R_i$为4个区域 3. 不断重复步骤2，直到没有一个子区域可以分割 4. 对任意两个相邻区域$R_i$和$R_j$，若$T(R_i\cup R_j)=true$，则合并这两个区域 5. 不断重复步骤4，直到没有相邻区域可以合并  ### 4.4 边缘检测 * [边缘检测](#35-图像锐化) * 边缘是图像最基本的特征，他是**灰度不连续**的结果，即图像中灰度不连续或急剧变化的地方 * 图像中不同灰度的相邻区域之间总存在边缘，广泛存在于物/物，物/背的交界处 * 沿边缘走向的灰度是缓变或是不变的，而垂直于边缘走向的灰度是突变的 * 常见的边缘类型 * 阶跃型  一种理想的边缘 * 斜坡型  坡度与被模糊的程度成反比，模糊程度高的边缘一般表现为厚边缘 * 线状型  有一个灰度突变 * 屋顶型  两侧的灰度斜坡相对平缓，对应粗边缘 * 常用的边缘检测方法 * 可以利用微分运算进行边缘检测，即借助各类微分算子实现 1. 基于一阶微分的梯度算子 * 正交梯度算子 适用于水平垂直走向的边缘 $\begin{bmatrix} -1* &1\\ 0 &0\\ \end{bmatrix}$和$\begin{bmatrix} -1^* &0\\ 1 &0\\ \end{bmatrix}$ * Roberts梯度算子 适用于斜角45度走向的边缘 $\begin{bmatrix} 0* &-1\\ 1 &0\\ \end{bmatrix}$和$\begin{bmatrix} -1^* &0\\ 0 &1\\ \end{bmatrix}$ * Prewitt算子 $\begin{bmatrix} -1 &0 &1\\ -1 &0^* &1\\ -1 &0 &1 \end{bmatrix}$和$\begin{bmatrix} -1 &-1 &-1\\ 0 &0^* &0\\ 1 &1 &1 \end{bmatrix}$ $\begin{bmatrix} -1 &-1 &0\\ -1 &0^* &1\\ 0 &1 &1 \end{bmatrix}$和$\begin{bmatrix} 0 &1 &1\\ -1 &0^* &1\\ -1 &-1 &0 \end{bmatrix}$ * Sobel算子 $\begin{bmatrix} -1 &0 &1\\ -2 &0^* &2\\ -1 &0 &1 \end{bmatrix}$和$\begin{bmatrix} -1 &-2 &-1\\ 0 &0^* &0\\ 1 &2 &1 \end{bmatrix}$ $\begin{bmatrix} -2 &-1 &0\\ -1 &0^* &1\\ 0 &1 &2 \end{bmatrix}$和$\begin{bmatrix} 0 &1 &2\\ -1 &0^* &1\\ -2 &-1 &0 \end{bmatrix}$ 扩展到了两个对角方向，并可以在对角方向上作出最大响应 * Krisch算子 $\begin{bmatrix} 5 &5 &5\\ -3 &0^* &-3\\ -3 &-3 &-3 \end{bmatrix}$和$\begin{bmatrix} -3 &5 &5\\ -3 &0^* &5\\ -3 &-3 &-3 \end{bmatrix}$ 分别将他们旋转得到各4个，共8个算子 进行边缘检测时选取产生**最大响应的算子**作为当前点的梯度 2. 基于二阶微分的拉普拉斯算子 拉普拉斯算子对噪声非常敏感，一般不直接用于边缘检测 我们引入高斯-拉普拉斯算子 由于拉普拉斯算子对噪声过于敏感，我们可以考虑在边缘检测之前，现对图像进行平滑操作，就得到了这样的合并算子 $\left[\begin{array}{ccccc} -2 & -4 & -4 & -4 & -2 \\ -4 & 0 & 8 & 0 & -4 \\ -4 & 8 & 24^{*} & 8 & -4 \\ -4 & 0 & 8 & 0 & -4 \\ -2 & -4 & -4 & -4 & -2 \end{array}\right]$ ### 4.5 二值图像的轮廓提取与轮廓跟踪 * 轮廓提取与轮廓跟踪的目的 * 获取目标区域的外部轮廓特征，为形状分析和目标识别做准备 * 二值图像的轮廓提取 * 方法：掏空目标区域的内部点 * 基本原理：设一幅二值图像，从上到下，从左至右依次扫描图像中每个像素，若当前像素为黑，且它的8邻域像素也都为黑，说明该像素是目标物体内部点，则将该像素置为白。对所有像素都执行该操作，便可提取出目标物体的轮廓 * 二值图像的轮廓跟踪 * 顺序找出目标区域边界上的像素点以跟踪目标边界，同时记录边界信息（生成边界链码） * 基本原理：基于4/8方向链码跟踪出4/8连通轮廓 1. 按从上到下，从左到右的顺序，扫描图像，寻找没有标记的目标点，给盖点分配一个新的标记 2. 定义搜索方向变量，记录下一个点的搜索方向码，即从方向5开始搜索相邻的下一个边界点 3. 若所有点都不是边界点，则该点为一孤立点，否则把搜索到的边界点作为下一次搜索的起始点 4. 如此递归2，3，直到搜索到的边界点为搜索起始点 * 算法特点： * 无法处理孔洞边界（只能把图像的外界轮廓跟踪出来） * 得到的轮廓是内边界，即把边界点也包含在了目标区域内 ### 4.6 图像匹配之模板匹配 > 此处的模板与图像平滑/锐化等处理模板完全不同！注意区分！ * 模板匹配的基本思想 * 用一幅已知的较小的图像，与一幅大的原始图像进行比较，确定大图像中是否有存在与模板图像相同或相近的部分 * 通过匹配测度去衡量相似性的程度 * 模板匹配的常用方法 * 相关法 设$f(x,y)$为$M×N$的原图像，$t(j, k)$为$J×K$的模板图像$(J≤M, K≤N)$，则模板图像与原图像中对应区域之间的相似性可用下式来衡量 $\begin{aligned} D(x, y) &=\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[f(x+j, y+k)-t(j, k)]^{2}\\ &=\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[f(x+j, y+k)]^{2}\\ &-2 \sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[t(j, k) \cdot f(x+j, y+k)] \\ &+\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[t(j, k)]^{2} \end{aligned}$ 令 $\begin{align}DS(x,y)=\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[f(x+j, y+k)]^{2}\end{align}$ $\begin{align}DST(x,y)=2 \sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[t(j, k) \cdot f(x+j,y+k)]\end{align}$ $\begin{align}DT(x,y)=\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}[t(j, k)]^{2}\end{align}$ 显然DST表示了模板图像与原图像中的互相关性，将$DST(x,y)$做归一化处理，得到对应区域之间的相关系数$\begin{align}R(x,y)=\frac{DST(x,y)}{\sqrt{DS(x,y)\cdot DT(x,y)}}\end{align}$ 暴力匹配，使得$R(x,y)\rightarrow 1$ * 误差法 直接用模板图像与原图像对应区域的误差来作为模板匹配测度 $\begin{align}E(x, y)=\sum_{j=0}^{J-1} \sum_{k=0}^{K-1}|f(x+j, y+k)-t(j, k)|\end{align}$ ## 5 图像几何变换 ### 5.1 图像几何变化基础 * 图像几何变换：是原始图像能够按照需要，产生大小，形状，位置等方面的几何变化 * 本质特征：图像几何变换的目的不是改变图像的像素值，而是改变像素所在的位置 * 图像几何变换分类 * 图像类型 * 二维图像 * 三维图像（包含三维图像向二维图像的投影变换） * 变换性质 * 基本变换 平移，镜像，旋转，比例缩放，错切 * 复合变换 由连续多次的基本变换复合而成 * 齐次坐标 * 二维图像中某像素点的坐标为$(x,y)$，通常表示成齐次坐标$(Hx,Hy,H)$，$H$为一非零实数，当$H=1$时，齐次坐标$(x,y,1)$，通常称为规范化齐次坐标 * 齐次坐标的意义在于可以使图像变换可以简便地通过一个$3\times 3$的变换矩阵去表示 * 二维图像几何变换矩阵 * 二维图像几何变换的一般过程 变换前图像的点集矩阵$\times$变换矩阵=变换后图像的点集矩阵 $T_{2D}=\begin{bmatrix} a &b &p \\ c & d &q \\ l&m &s \end{bmatrix}$ $a,b,c,d$提供旋转，镜像，比例缩放，错切，默认为$\begin{bmatrix} 1 &0 \\ 0 & 1 \end{bmatrix}$ $l,m$提供平移，默认为0 $p,q$提供透视，默认为0 $s$提供全比例，默认为1 ### 5.2 图像平移变换 * 将图像上所有的像素点，按照水平方向和垂直方向给定的偏移量（为整数）移动，像素点只发生了位置上的改变 * 其中$x$方向上的偏移量对应$T_{2D}$矩阵中的$l$，其中$y$方向上的偏移量对应$T_{2D}$矩阵中的$m$ * 逆变换则$l=-l$，$m=-m$，即可 ### 5.3 图像镜像变换 * 镜像变换也称为对称变换（或反射变换），像素点只发生了位置上的改变 * 图像镜像变换具体分为两种形式： * 水平镜像 * 垂直镜像 * 原理：设原图像上某一点$P_0(x_0,y_0)$，镜像后对应像素点$P(x,y)$，图像高度为$fHeight$，高度为$fWidth$，则经过水平/垂直镜像后的$P(x,y)$为 水平：$\left\{\begin{matrix} x=fWidth-x_0\\ y=y_0 \end{matrix}\right.$ 垂直：$\left\{\begin{matrix} x=x_0\\ y=fHeight-y_0 \end{matrix}\right.$ * 齐次坐标变换形式（垂直镜像） $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & -1 & 0 \\ 0 & \text { fHeight } & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ * 齐次坐标变换形式（水平镜像） $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} -1 & 0 & 0 \\ 0 & 1 & 0 \\ \text { fWidth } & 0 & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ * 逆变换与原变换相同 ### 5.4 图像旋转变换 * 将图像上的所有像素点绕图像中心旋转相同角度。规定逆时针旋转角度为正，顺时针旋转角度为负 * 原理：设原图像上某一点$P_0(x_0,y_0)$，旋转后对应像素点$P(x,y)$，图像高度为$fHeight$，高度为$fWidth$，则经过旋转镜像后的$P(x,y)$为 旋转：$\left\{\begin{matrix} x=x_0cos\theta +y_0sin\theta\\ y=-x_0sin\theta +y_0cos\theta \end{matrix}\right.$ * 齐次坐标变换形式 $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} \cos \theta & -\sin \theta & 0 \\ \sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ * 逆变换 $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right] \times\left[\begin{array}{ccc} \cos \theta & \sin \theta & 0 \\ -\sin \theta & \cos \theta & 0 \\ 0 & 0 & 1 \end{array}\right]$ * 可能存在的问题及解决方法 * 计算出的变换后的坐标值为小数 四舍五入取整 * 坐标值所在范围与原图像不同 平移变换，保证所有坐标都是正整数 * 变换后存在的现象及解决方法 * 像素的排列不是完全按原有的相邻关系 * 出现空洞点，会影响图像质量 可以采用插值法来填充空洞点 * 插值法：行/列插值 1. 找出最小/最大空洞点，分别为$(i,k_i)$，$(j,k_j)$ 2. 在$i≤x≤j$，$k_i≤y≤k_j$，内逐行/列扫描，如果遇到空洞点，则将空洞点填充为前一个值  ### 5.5 图像比例缩放变换 * 将原图像在$x$轴方向缩放$f_x$倍，在$y$轴方法缩放$f_y$倍，从而获得一幅新图像 * 当$f_x=f_y=1$时，为恒等变换，图像大小不变 * 当$f_x=f_y>1$时，图像等比例放大 * 当$0<f_x=f_y<1$时，图像等比例缩小 * 当$f_x\neq f_y$，图像产生畸变 * 原理：设原图像上某一点$P_0(x_0,y_0)$，缩放$(f_x,f_y)$倍后，对应像素点$P(x,y)$ 旋转：$\left\{\begin{matrix} x=x_0\cdot f_x\\ y=y_0\cdot f_y \end{matrix}\right.$ * 齐次坐标变换形式 $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} f_x & 0 & 0 \\ 0 & f_y & 0 \\ 0 & 0 & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ 在全比例变换（即$f_x=f_y$）情况下，可以同时约去$f_x$，得到 $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & s \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ 可以得到当$s=1$时，图像大小不变，而当$s>1$时，图像**等比缩小**，反之当$s<1$时，图像**等比放大** * 逆变换 $\left[\begin{array}{lll} x_{0} & y_{0} & 1 \end{array}\right] \times\left[\begin{array}{ccc} 1/f_x & 0 & 0 \\ 0 & 1/f_y & 0 \\ 0 & 0 & 1 \end{array}\right]=\left[\begin{array}{lll} x & y & 1 \end{array}\right]$ * 缩小可能存在的问题及解决方法 * 经过比例缩放后，新图像中的像素点，找不到与原图像对应的点 可以通过灰度插值处理来解决 * 灰度插值处理 * 最邻近插值法 新图像中的像素点$(x,y)$，可能被映射到原图像的非整数点$(x_0,y_0)$，上，即位于四个点之间，因此选择其最邻近的整数点，作为新图像中的像素点$(x,y)$ * 双线性插值法  $f(x_0,y_0)=(1-p)(1-q)f(A)+p(1-q)f(B)+(1-p)qf(C)+pqf(D)$ $p=x_0-[x_0],q=y_0-[y_0]$  * 放大可能存在的问题及解决方法 * 对应复制填充即可，做法近同与缩小 ### 5.6 图像复合变换 * 对原图像连续进行若看次平移，镜像，比例缩放，旋转等基本变换 * 复合变换矩阵等于基本变换矩阵**按变换顺序依次相乘**得到的矩阵乘积 $\begin{align} T=T_1\cdot T_2\cdot T_3\cdot ... \cdot T_n \end{align}$ ## 6 图像压缩编码 $f(x,y)\xrightarrow{Compress} Encoded Data\xrightarrow{Extract} g(x,y)$ ### 6.1 概述 1. 图像压缩的背景： * 不断扩大的图像应用 * 需求增长的同时，对存储空间和传输带宽的要求也逐渐增大 2. 什么是图像压缩 尽量减少**表示数字图像**时所需要的数据量 信息量=数据量-冗余量 压缩的途径： * 保留意义完全的有效信息 * 消除冗余信息与不相干信息 通过对原图像进行压缩编码而后解压还原出一个原始（近似）图像 压缩的分类： * 无损压缩：压缩后的还原图像与原图像相比没有信息损失 * 有损压缩：压缩后的还原图像与原图像相比有信息损失 3. 数据冗余的概念和类型 数据冗余：信息用数据来表示。如果不同的方法为表示给定量的信息使用了不同的数据量，则使用较多数据量的方法中，有些数据必然代表了无用的信息，或者是重复地表示了其它数据已表示过的信息 三种冗余类型： 1. 编码冗余 对图像的灰度级进行编码时，如果使用的编码符号个数多于表示灰度级实际所需要的编码符号个数，则称图像包含编码冗余 2. 像素间冗余 图像相邻像素之间的像素值可能存在强相关性，即可以通过适当的处理（差分等），减少所需的信息位 3. 心理视觉冗余 人眼无法感知，或是不敏感的图像信息则称为心理视觉冗余，可以消除 这是一个**有损压缩的操作**，是不可逆的，会丢失信息 4. 图像保真度准则 图像压缩可能会导致信息损失，因此需要去评价信息损失的程度，来描述恢复出的人图像相对于原始图像的偏离程度 1. 客观保真度准则 1. 均方根误差 一幅图像的总误差为 $\begin{align}\sum_{x=0}^{M-1} \sum_{y=0}^{N-1}[g(x, y)-f(x, y)]\end{align}$ $\begin{align}e_{r m s}=\left[\frac{1}{M N} \sum_{x=0}^{M-1} \sum_{y=0}^{N-1}[g(x, y)-f(x, y)]^{2}\right]^{\frac{1}{2}}\end{align}$ 2. 均方根信噪比 如果将误差视作噪声 $\begin{align}S N R_{r m s}=\sqrt{\frac{\sum_{x=0}^{M-1} \sum_{y=0}^{N-1} g^{2}(x, y)}{\sum_{x = 0}^{M-1} \sum_{y=0}^{N-1}[g(x, y)-f(x, y)]^{2}}}\end{align}$ 2. 主观保真度准则 通过主观评价打分 5. 图像压缩系统的基本组成  1. 信源编码器 用于减少或消除原始图像的数据冗余  转换器：减少像素间冗余，可逆 量化器：减少心理视觉冗余，不可逆 符号编码器：减少编码冗余，可逆 2. 信源解码器  符号解码器：逆操作符号编码器 反向转换器：逆操作转换器 6. 编码效率 设一幅静态数字图像，大小为$M×N$，灰度级总数为$L$，图像中第$k$级灰度出现的概率为$P_k$，第$k$级灰度压缩编码后的码字长度为$B_k$比特，原始图像中每个像素都用$d$比特表示 1. 图像熵$H$ 表示图像的信息量 $\begin{align} H=-\sum_{k=0}^{L-1} P_{k} \log _{2}\left(P_{k}\right)\end{align}$ 2. 平均码长$R$ 表示每个像素平均所需要的比特数 $\begin{align} R=\sum_{k=0}^{L-1} B_{k} P_{k}\end{align}$ 3. 编码效率$\eta$ 图像熵与平均码长之比 $\begin{align} \eta=\frac{H}{R}\times 100\% \end{align}$ 4. 压缩比$C_r$ 原表示像素所需的比特数与现平均码长之比 $\begin{align} C_r=\frac{d}{R}\times 100\% \end{align}$ 7. 常见的无损压缩编码途径与方法 1. 减少编码冗余 1. 哈夫曼编码 2. 香农-范诺编码 3. 算数编码 2. 减少像素间冗余 1. 行程编码 2. LZW编码 ### 6.2 哈夫曼编码 * 基本思想： * 统计信源符号的概率分布，然后按其出现的概率赋予各信源符号不同的码长：出现概率大的信源符号赋予较短的码字，出现概率小的信源符号，赋予较长的码字。则使得最终的平均码字长度为最小 * 基本原理： * 建树 * 统计出各个信源符号出现的概率（比如，对一幅图像进行灰度级概率统计），并对信源符号出现的概率从大到小排列 * 合并概率最小的两个信源符号，形成一个新符号。新符号的概率是这两个信源符号的概率之和 * 新符号的概率与剩余符号的概率形成一个新的概率集合，然后再对新的概率集合重新排列（从大到小） * 重复执行第2、3步，直到最后两个信源符号的概率之和是1为止，也就建出了一颗哈夫曼树 * 分配码字 * 码字分配从最后一步开始反向进行，即从哈夫曼树的根节点开始，反向进行 * 对于每次合并的两个信源符号，要按统一规律分配码元（有利于解码）：概率大的赋0，概率小的赋1（或概率大的赋1，概率小的赋0） * 读出每各信源符号的哈夫曼编码： 由某信源符号开始，一直走到最后的概率和1，将沿路上所遇到的0或1，按最低位到最高位的顺序排列， 即为该信源符号的哈夫曼编码 * 例题 设一幅图像， 共8级灰度，分别为$S_0$、$S_1$、$S_2$、$S_3$、$S_4$、$S_5$、$S_6$、$S_7$，各灰度级出现的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04，现对其进行哈夫曼编码 可得其 $S_0$：1 $S_1$：001 $S_2$：011 $S_3$：0000 $S_4$：0100 $S_5$：0101 $S_6$：00010 $S_7$：00011 * 相关计算： 如上题 平均码字长度$\begin{align}R=\sum_{k=0}^{7}B_kP_k=2.61bits\end{align}$ 图像熵$\begin{align} H=-\sum_{k=0}^{7} P_{k} \log _{2}\left(P_{k}\right)=2.55bits\end{align}$ 编码效率$\begin{align} \eta=\frac{H}{R}\times 100\%=97.7\% \end{align}$ 若原图采用等长编码，显然每个像素需要3比特表示，则压缩比$\begin{align} C_r=\frac{d}{R}\times 100\%=1.15\end{align}$ * 特点： * Huffman编码得出的码字不唯一 * Huffman编码得到的码字不等长，但平均码字长度最小，编码效率高 * Huffman编码依赖于信源符号的统计特性，编码效率与信源符号的概率分布密切相关 ### 6.3 香农-范诺编码 * 基本思想： 信源符号的码字长度Bk由该信源符号出现的概率决定 $\begin{align}-\log _{D} P_{k} \leq B_{k} \leq\left(-\log _{D} P_{k}\right)+1\end{align}$ * 基本原理： * 将信源符号按其出现的概率从大到小排序 * 根据各信源符号的概率，计算对应的码字长度$B_k$ * 计算累加概率$A_k$ * 把各个累加概率$A_k$由十进制转化为二进制 * 取该二进制数的高$B_k$位，作为对应信源符号的码字 * 例题  以$S_1$的计算为例，其$A_k=S_0=0.40$，其$-log_D(0.18)\leq B_k\leq-log_D(0.18)+1\approx 3.47$，因此选定$B_k=3$，则选取其$A_k$对应的二进制的前3位，作为$S_1$的码字 * 二分香农-范诺编码 * 首先统计出每个信源符号出现的概率，并将所有概率从大到小排序 * 从当前概率集合中的某个位置将其分成两个子集合，尽量使两个子集合的概率之和近似相等，给前一个子集合赋值为0，后一个子集合赋值为1 * 重复步骤2，直到各个子集合中只剩一个信源符号为止 * 将每个信源符号所属的子集合的值（0或1）依次串起来，即可得到该信源符号的二分香农-范诺编码  ### 6.4 算数编码 * 典型特点： * 信源符号和码字之间不存在一一对应关系。一个算术码字被赋给整个信源符号序列，码字本身确定0～1之间的一个实数区间。随着序列中信源符号数量的增加，用来代表它的实数区间缩小 * 基本原理： * 统计每个信源符号出现的概率，设置当前区间为[0,1] * 对依次出现的每个信源符号进行如下处理： * 将当前区间分成子区间，子区间的长度正比于信源符号的概率 * 选择一个子区间对应于信源符号序列中的下一个信源符号，并以该子区间作为新的当前区间 * 对序列中的所有信源符号处理完后，输出当前区间中的任意一个实数作为该信源符号序列的算术编码 * 例题 设有一待编码的信源序列为**dacab**，对其进行算术编解码 * 编码： 可以得到$P(a)=0.4、P(b)=0.2、P(c)=0.2、P(d)=0.2$  不断对子区间按照出现比例进行划分，从而收敛上下限即可得到最终的编码序列 0.1101101 $\approx$ 0.8516 * 解码： 首先计算每个符号的子间隔宽度$W(i)$，也就是$P(i)$ 并给出每个符号的最小起始点$I_{start}$，分别为0,0.4,0.6,0.8 $n=0.8516$在d区间，故输出d，$W(d)=0.2$，则$n=(n-d_{start}/W(d)=0.258$ $n=0.258$在a区间，故输出a，$W(a)=0.4$，则$n=(n-a_{start}/W(a)=0.645$ $n=0.645$在c区间，故输出c，$W(c)=0.2$，则$n=(n-c_{start}/W(c)=0.225$ $n=0.225$在a区间，故输出a，$W(a)=0.4$，则$n=(n-a_{start}/W(a)=0.5625$ $n=0.5625$在b区间，故输出b，$W(b)=0.2$，则$n=(n-b_{start}/W(b)=0.8125$ 至此，已经全部完成解码，按序输出**dacab**即可 * 特点： 由于算术编码对整个信源只产生一个码字，故其对错误非常敏感，任何错误都会导致解码无法正常进行 ### 6.5 行程编码 * 基本思想： * 用一个长度序列表示二值图像的每一行，这些长度描绘了黑色像素或白色像素的连续行程，因此，其一般用于二值图像编码 * 基本原理 * 对二值图像进行行扫描 * 将当前扫描行中的像素$f(k,0)...f(k,N-1)$映射为一个行程序列$(g_1,l_1),(g_2,l_2)$，每个$(g_i,l_i)$代表一个行程 * $g_i$表示当前扫描行遇到了第$i$个灰度级，他表示了当前扫描行中的灰度的变化 * $l_i$表示灰度级为$g_i$的行程长度 * 如下的扫描行  可以得到行程编码(1,3),(0,5),(1,4),(0,2),(1,1) * 压缩比计算 * 若某二值图像，大小为340行×1000列，对其进行行程编码后，共得到12166个行程。则每个行程可用多少比特表示，压缩比为？ * 此例中，每个行程$(g_i,l_i)$，$g_i$可以用1比特表示，$l_i$不会超过1000，因此需要10比特表示，则每个行程需要11比特表示，则压缩后的图像大小为12166$\times$ 11 $=$ 133826比特，压缩比为$\frac{12166\times 11}{340\times 1000}=39.4\%$ * 特点 * 若图像中包含**大面积的灰度相同区域**，采用行程编码可达到很高的压缩比 * 若图像中的灰度分布很分散，行程编码不但不能起到压缩作用，反而可能会增加图像数据量 * 所以，行程编码**一般不单独使用**，而与其它编码方法相结合 ### 6.6 LZW编码 * 基本思想 * 将原始数据中的重复字符串建立一个字典，然后利用该重复字符串在字典中的索引代替原始数据，从而达到压缩目的 * 在编码开始前，先构造一个对信源符号进行编码的初始编码本（字典） * 顺序地分析图像像素，凡是字典中没有出现过的灰度值连接序列，将被依次加入到字典中没有使用过的位置上 * 基本原理 1. 按照从左到右，从上到下的顺序依次处理各个像素。用S2表示当前被处理的像素 2. "当前识别序列"是一个可变的灰度值连接序列。用S1表示当前识别序列，初始时为空 3. 从图像块的第一个像素开始，每次读取一个像素，将其赋给S2 4. 判断S1-S2是否已经存在于字典中： * 若字典中已存在S1-S2：S1= S1-S2； * 若字典中不存在S1-S2：输出S1在字典中的位置号（索引），并将S1-S2添加到字典末尾，位置号（索引）顺延，同时S1=S2 5. 重复执行3，4两步，直到所有像素处理完为止 6. 最后，从上到下顺序读出表中的第三列编码，即为该图像块的最终LZW编码