数字图像处理复习

简答题：8’*3
1、图像的数字化过程：采样，分色，量化，编码相关概念。
采样：采样的实质就是用多少点来描述一幅图像，采样结果质量的高低就是图像分辨率，连续图像的空间样本实际上就是用采样函数与连续图像相乘的结果。空间采样函数为：
在这里插入图片描述
分色：指RGB图像数据被转换为最接近等量的青、品红、黄、黑(CMYK)数值的工艺。
量化：量化指将采样后离散图像的值表示为与其幅度成比例的整数。
编码：图像数字化后得到的图像数据量十分巨大，由于图像数据本身固有的冗余性和相关性，可以使用编码将大的图像数据文件转换成较小的图像数据文件。

2、图像压缩算法：给出两个压缩算法（符号编码，统计编码，变换编码，模型编码）各种编码包括哪些，简单描述基本原理。
统计编码：
huffman编码：赫夫曼编码是一种依据变长最佳编码定理，基于统计的无损编码。步骤如下：
(1)将信源符号 $x_i$ 按出现概率从大到小排序;(2)将最小的两个信源相加，重复这一步骤，始终将概率较大的分支放在上部，直到只剩下一个信源符号且概率为1;(3)对每对组合的上边与下边标号1与0;(4)由每个信源到概率1.0处的路径形成的0、1逆序列为赫夫曼编码。
香农-费诺编码：基于统计的变长编码算法：
(1)将信源符号按出现的概率从大到小排列;(2)将信源分成两部分，使两部分的概率尽可能接近，重复直至不可再分;(3)从左至右一次为这两部分标记0、1;(4)将各个部分标记的0、1串拼接起来得到编码。
变换编码：
基本原理：图像数据一般具有较强的相关性，图像经过正交变换后，分散在原空间的图像数据在新的坐标系中得到集中，只要删除接近于0的系数并且对较小的系数进行粗量化，保留包含图像主要信息的系数，以此进行编码。
包括：基于FFT的图像压缩技术、基于DCT 的图像压缩技术、基于哈达玛变换的图像压缩技术

3、形态学运算：膨胀，腐蚀，开运算（先腐蚀，后膨胀），闭运算（先膨胀，后腐蚀）。（解释什么是膨胀算子…）
注：以下-均为圈里-
膨胀：B对A的膨胀实质上就是一个由所有平移量 $z$ 组成的集合，这些平移量满足：当B的反射集平移了 $z$ 之后，与集合A的交集不为空。
膨胀算子：
在这里插入图片描述
腐蚀：B对A的腐蚀即为平移量 $z$ 的集合，这些平移量满足集合B平移 $z$ 之后仍然属于集合A。
腐蚀算子：

开运算：先用结构元素B对A进行腐蚀，再用B对A进行膨胀。可以去除轮廓的毛刺，分离图像轮廓的作用
开运算公式：
在这里插入图片描述
闭运算：先膨胀再腐蚀，可以起到去除图像区域中的小孔，填平轮廓缺口的作用。
闭运算公式：

4、滤波器（巴特沃斯、理想）及他们的公式。
理想低通滤波器：指可以截断傅里叶变换中的所有处在离变换原点的距离比指定距离 $D_0$ 要远的位置，传递函数：
$\left\{ \begin{array}{lr} 1 & : D(u,v)\le D_0\\ 0 & : D(u,v) > D_0 \end{array} \right.$
$D_0$ 是一个非负整数， $D (u, v)$ 是从点 $(u, v)$ 到频率平面原点的距离， $D(u,v)=\sqrt{u^2+v^2}$ ，“理想”指小于等于 $D_0$ 的频率可以完全不受影响，大于 $D_0$ 的频率则完全不通过， $D_0$ 称为截止频率。
巴特沃斯低通滤波器：物理上可以实现的一种低通滤波器为巴特沃斯低通滤波器，一个阶为 $n$ ，截止频率为 $D_0$ 的巴特沃斯低通滤波器的传递函数为：
$H(u,v)=\frac{1}{1+[D(u,v)/D_0]^{2n}}$
常取使 $H$ 最大值降到某个百分比的频率为截止频率。
理想高通滤波器与巴特沃斯高通滤波器与上述相反：
$\left\{ \begin{array}{lr} 1 & : D(u,v)\ge D_0\\ 0 & : D(u,v) <D_0 \end{array} \right.$
$H(u,v)=\frac{1}{1+[D_0/D(u,v)]^{2n}}$
带通和带阻滤波器：允许一定频率范围内的信号通过而阻止其他频率范围信号通过
公式：
$\left\{ \begin{array}{lr} 1 & : D_1(u,v)\le D_0或D_2(u,v) \le D_0\\ 0 & : 其他 \end{array} \right.$
$D_1(u,v)=\sqrt{(u-u_0)^2+(v-v_0)^2}\\D_2(u,v)=\sqrt{(u+u_0)^2+(v+v_0)^2}$
5、图像的特征描述有哪些（具体说明颜色（直方图）、形状（形状数、形状矩）、纹理（区域傅里叶）、特征点（SIFT SURF））。
颜色：直方图
边界描述：
边界长度：边界所包围区域的轮廓长度
边界的直径：边界上任意两点距离的最大值
形状数：值最小的4链码的一阶差分码。
傅里叶描述子：傅里叶的高频部分对应一些细节，低频分布对应基本形状。统计矩：描述对边界的一维表示。
区域描述：
区域面积：描述区域的大小
区域重心
纹理：
统计法：基于图像的灰度直方图的特性描述纹理
傅里叶频谱法：全局纹理模式在频域中容易得到分辨
不变矩
特征点：
SIFT
SURF
图像增强的方法（灰度增强、直方图均衡化，各个函数（幂函数、对数函数…）的作用，分别增强图像的哪一部分（幂函数增强亮的部分，对数函数增强暗的部分…））
直接灰度变换：
图像求反：适用于增强嵌入于图像暗色区域的白色或灰色细节;
线性灰度变换：用分段线性的方法将需要的图像细节灰度级拉伸，增强对比度，将不需要的图像灰度级进行压缩;
对数变换：增强图像暗的部分，频谱中低值部分;
幂函数：增强图像亮的部分，频谱中高值部分。
直方图均衡化：
将原始图像不均匀的直方图变换成均匀分布的形式，使图像具有高对比度和多变的灰度色调，显示出一幅灰度级丰富且动态范围大的图像。
程序设计题 10’*2
给出XXX算法描述或程序
（快速傅里叶算法（蝶形图）、直方图均衡化算法、算数压缩、canny图像分割）
1、快速傅里叶变换：
图像的二维快速傅里叶变换可以看成先对行都做一次一维快速傅里叶变换再对列做一次一维快速傅里叶变换，所以只需要实现一维快速傅里叶变换。
首先：一维离散傅里叶变换公式为： $F(u)=\sum^{M-1}_{x=0}f(x)e^{-i2\pi ux/M}$ ，其中 $u = 0, 1, 2, . . ., M - 1$
设原始信号序列为 $f (x)$ ，长度为 $L(L=2^N,为2的整数次方)$ ， $x=0,1,2,...,L-1,W^{ux}_{L}=e^{-i2\pi ux/L}=cos(2\pi ux/L)+isin(2\pi ux/L)$ 按 $x$ 奇偶性分为两组：
在这里插入图片描述
则 $F(u)=F_1(u)+W^u_LF_2(u),F(u+L/2)=F_1(u)-W^u_LF_2(u)$
得到蝶形公式

根据上式，计算 $L$ 长度序列时，只需计算 $L / 2$ 长度序列，以此类推，最终只需计算长度为2的序列，通过递归可以求得原信号序列的傅里叶变换。
伪代码：

for i=0:x.lengthreverse x[i]//计算倒序位码
for i=0:log2Nstep=1<<(i+1)factor_step=N>>(i+1)factor_real=1.0factor_imag=0.0for j=0:step/2for k=j;k<N;k+=stepk2=k+step/2//蝶形运算的两个输入temp_real=real[k2]*factor_real-imag[k2]*factor_imagtemp_imag=real[k2]*factor_imag+imag[k2]*factor_real//F+W*Freal[k2]=real[k1]-temp_realimag[k2]=imag[k1]-temp_imag//F-W*Freal[k1]=real[k1]+temp_realimag[k1]=imag[k1]+temp_imagfactor_real=cos(-2*PI*(j+1)*factor_step/N)factor_imag=sin(-2*PI*(j+1)*factor_step/N)

2、直方图均衡化：
1、遍历图像，统计每个灰度级下像素点的个数
2、计算每个灰度级像素所占的比例
3、按照比例重新计算每个灰度级的像素点个数，实现均衡化
4、更新图像灰度值

Mat equalize_hist(Mat &input)
{Mat output=input.clone();int gray_sum=input.rows*input.cols;//统计每个灰度级下像素点个数存储在数组gray[256]for(int i=0;i<input.rows;i++){uchar *p=input.ptr<uchar>(i);for(int j=0;j<input.cols;j++){int value=p[j];gray[value]++;}}//统计出现频率for (int i=0;i<256;i++){gray_prob[i]=(double)gray[i]/sum;}//计算累计密度gray_total[0]=gray_prob[0];for(int i=1;i<256;i++)gray_total[i]=gray_total[i-1]+gray_prob[i];//重新计算灰度值。公式(N-1)*T+0.5for(int i=0;i<256;i++)gray_equ[i]=(uchar)(255*gray_total[i]+0.5);for(int i=0;i<output.rows;i++){uchar *p=output.ptr<uchar>(i);for(int j=0;j<output.cols;j++)p[j]=gray_equ[p[j]];}return output;
}

3、算数压缩：

struct Range{
string code;
double high;
double low;
};
void coding(vector<string>code,vector<double>prob)
{vector<Range>init_code_range;double low=0.0;for(int i=0;i<prob.size();i++){Range temp;temp.code=code[i];temp.low=low;temp.high=temp.low+prob[i];init_code_range.push_back(temp);low=temp.high;}double low=0.0;double range=1.0;double high=1.0;for(int i=0;i<code.size();i++){for(int j=0;j<init_code_range.size();j++){if(code[i]==init_code_tange[j].code){low=low+range*init_code_range[j].low;high=low+range*init_code_range[j].high;range=high-low;}}if(i==code.size()-1)cout<<low;}
}

4、canny图像分割
步骤：
1、利用高斯滤波器平滑图像

for x=0:rowsfor y=0:cols//高斯平滑temp=1/2*pi*sigmag[x][y]=temp*exp(-((x-x0)*(x-x0)+(y-y0)*(y-y0)))/(2*sigma*sigma)
normalize(g)//归一化

2、计算滤波后图像的幅度和方向

for x=0:rowsfor y=0:cols//卷积g[x][y]+=kernel[x][y]*g[x][y]//获得梯度图像g[x][y]=sqrt(img_x[x][y]*img_x[x][y]+img_y[x][y]*img_y[x][y])

3、对梯度幅度应用非极大值抑制，找出图像梯度中的局部极大值点，把其他非局部极大值点置零，得到细化的边缘
将当前像素梯度与沿正负梯度方向上的两个像素进行比较，若大于则保留位边缘点，否则抑制。

if Gp>=Gp1 and Gp>=Gp2Gp maybe an edge
elseGp should be suppressed

4、用双阈值算法检测和边缘连接，使用两个阈值 $T_1和T_2$ ， $T_1$ 用来找到每一条线段； $T_2$ 用来在这些线段的两个方向上延伸寻找边缘断裂处，连接这些边缘点。**

for x=0:rowsfor y=0:colsif g[x][y]<low_thresholdg[x][y]=0;if g[x][y]>high_thresholdg[x][y]=255	else//八连通邻域不为0if eight connected neighborhood is not 0g[x][y]=255elseg[x][y]=0

论述题 13’*3
1、采样定理
设 $f (x)$ 为一带限函数，即 $F(u)=0,|u|>\Omega_M$ 。如果采样频率 $\Omega_s>2\Omega_M$ ，或者采样周期 $T<\frac{1}{2\Omega_M}$ ，其中 $\Omega_s=\frac{1}{T}，T$ 为采样周期，那么 $f (x)$ 就唯一地由其样值 $f_s(x)$ 所确定。临界采样率 $2\Omega_M$ 称为奈奎斯特频率，临界采样间隔 $\frac{1}{2\Omega_M}$ 称为奈奎斯特间隔。
2、卷积定理
函数卷积的傅里叶变换是函数傅里叶变换的乘积，分为时域卷积和频域卷积，时域卷积即时域内的卷积对应频域内的乘积，频域卷积即频域内的卷积对应时域内的乘积。
卷积定理公式： $\mathscr{F}[f(x,y)*h(x,y)]=H(u,v)F(u,v)$
$\mathscr{F}^{-1}[H(u,v)*F(u,v)]=f(x,y)h(x,y)$
卷积公式： $f(x,y)*g(x,y)=\iint f(u,v)g(x-u,y-v)dudv$
3、约束最小二乘滤波
与维纳滤波相比，1、约束最小二乘滤波只要求噪声方差和均值的知识，而这些参数经常能通过一幅给定的退化图像计算出来；2、约束最小二乘滤波所处理的每一幅图像都能产生最优的结果。
一幅图像的输入输出可以表示为 $g (x, y) = H [f (x, y)] + n (x, y)$ ，表达为向量-矩阵形式为g=Hf+n，约束最小二乘滤波的核心是解决退化函数 $H$ 对噪声的敏感性问题，因此，其约束条件为
$||g-H\hat{f}||^2=||n||^2$
最终解得其最优解为
$||n||^2=\sum^{M-1}_{x=0}\sum^{N-1}_{y=0}n^2(x,y)=MN[\sigma^2_n+m^2_n]$
其中
$\sigma^2_n=\frac{1}{MN}\sum^{M-1}_{x=0}\sum^{N-1}_{y=0}[n(x,y)-m_n]^2$
为整幅图像上采用取样平均的方法估计出的噪声方差，
$m_n=\frac{1}{MN}\sum^{M-1}_{x=0}\sum^{N-1}_{y=0}n(x,y)$
为样本均值。
4、运动图像复原
由匀速运动图像的退化函数为
$H(u,v)=\frac{T}{\pi(ua+vb)}sin[\pi(ua+vb)]e^{-j\pi(ua+vb)}$ ，
所以可以使用逆滤波消除运动模糊。
1)求得模糊图像的傅里叶变换 $G (u, v)$
2)观察图像，估计水平方向与垂直方向的移动距离 $a, b$ ，确定退化函数 $H (u, v)$
3)计算复原图像的傅里叶变换 $\hat{F}(u,v)=H^{-1}(u,v)G(u,v)$
4)对 $\hat{F}(u,v)$ 进行傅里叶逆变换，得到复原图像
5、图像量化
图像量化就是将离散的图像的值表示为与其幅度成比例的整数。
一般过程是设立一组判决电平，每一个判决电平覆盖一定的区间，所有判决电平覆盖整个有效区间，若像素点的采样值落在某个判决电平的区间上，则该采样值取这个量化级的代表值。
设量化操作在K维欧几里得空间上进行。A是X的取值空间，即值域，则A的一个N级量化器 $Q=\{Y,\psi\}$ 由三部分组成
1)对A的分割 $\psi=\{R_i|i=1,...,N\}$ 且
$\left\{ \begin{array}{lr} \bigcup^N_{i=1}=A\\ R_i\bigcap R_j=0 :i!=j \end{array} \right.$
2)码本的再生字符集 $Y=\{y_i|i=1,...N\}$
3)量化操作 $Q$ 的映射：
$Q:A→Y\\ y_i=Q(\{x|x∈R_i\})$
当 $K = 1$ 时是标量量化， $K > 1$ 时是向量量化。
6、图像滤波
图像滤波可用与图像增强、图像复原、图像去噪、边缘检测、角点检测、模板匹配等，既可以在空域进行，也可以在频域进行，滤波是一个邻域操作算子，利用给定像素周围的像素值确定此像素值的最终输出。
公式： $O(i,j)=\sum_{m,n}I(i+m,j+n)K(m,n)$
其中 $K$ 为滤波器（核），使用不同的滤波器达到不同的图像处理效果。
1、线性平滑滤波器（均值滤波）：抑制噪声，引起模糊。
2、中值滤波器：抑制噪声。
3、锐化滤波器：使边缘和轮廓线模糊的图像变得清晰，使细节更清晰。
4、低通/高通滤波器（理想、巴特沃斯）：消除噪声/锐化图像。
5、同态滤波器：压缩图像亮度范围，增强对比度。
6、逆滤波复原：适用于无噪声且 $H (u, v)$ 较大的图像复原
7、维纳滤波复原：综合退化函数与噪声统计特性，使得复原图像与原图像均方差最小。
8、约束最小二乘方滤波：仅仅用噪声的均值和方差的只是执行最佳复原算法。
综合应用 20’
用无人机识别森林大火
医学白细胞与红细胞检测