智能系统21-22年真题解析

21-22年期末真题

1 Q1

1.1 (a)

由图中给出的系统结构(不得不说这个图画的真丑，而且结构不清晰，连接点也不打黑点)。我们可以得到

$$\begin{cases} X_1(k+1) = Y_1(k)W_{X_1}^{Y_1}+Y_2(k)W_{X_1}^{Y_2}+Y_3(k)W_{X_1}^{Y_3} \\ X_2(k+1) = Y_1(k)W_{X_2}^{Y_1}+Y_2(k)W_{X_2}^{Y_2}+Y_3(k)W_{X_2}^{Y_3} \\ X_3(k+1) = Y_1(k)W_{X_3}^{Y_1}+Y_2(k)W_{X_3}^{Y_2}+Y_3(k)W_{X_3}^{Y_3} \end{cases}$$

以及通过输出与输入状态变量的关系，可以得到

$$\begin{cases} Y_1(k+1) = f[x_1(k+1)] \\ Y_2(k+1) = f[x_2(k+1)] \\ Y_3(k+1) = f[x_3(k+1)] \end{cases}$$

为方便计算(一些计算器有矩阵计算功能)，我们把它写成矩阵形式。

$$\begin{bmatrix} X_1(k+1) \\ X_2(k+1) \\ X_3(k+1) \\ \end{bmatrix}= \begin{bmatrix} W_{X_1}^{Y_1} & W_{X_1}^{Y_2} & W_{X_1}^{Y_3} \\ W_{X_2}^{Y_1} & W_{X_2}^{Y_2} & W_{X_2}^{Y_3} \\ W_{X_3}^{Y_1} & W_{X_3}^{Y_2} & W_{X_3}^{Y_3} \\ \end{bmatrix} \begin{bmatrix} Y_1(k) \\ Y_2(k) \\ Y_3(k) \end{bmatrix}$$

以及

$$\begin{bmatrix} Y_1(k+1) \\ Y_2(k+1) \\ Y_3(k+1) \\ \end{bmatrix}= f\begin{bmatrix} X_1(k+1) \\ X_2(k+1)\\ X_3(k+1) \end{bmatrix}$$

由题目数据，可得

$$\begin{bmatrix} X_1(k+1) \\ X_2(k+1) \\ X_3(k+1) \\ \end{bmatrix}= \begin{bmatrix} 0 & 0.5 & 0.7 \\ 0.3 & 0 & 0.55 \\ 0.01 & 0.1 & 0 \end{bmatrix} \begin{bmatrix} Y_1(k) \\ Y_2(k) \\ Y_3(k) \end{bmatrix}$$

以及

$$f(x) = \frac{1}{1+e^{-x}}$$

由题知，初始状态为0，即

$$\begin{bmatrix} X_1(0) \\ X_2(0) \\ X_3(0) \end{bmatrix} = \begin{bmatrix} Y_1(0) \\ Y_2(0) \\ Y_3(0) \end{bmatrix} = \begin{bmatrix} 0 \\ 0\\ 0 \end{bmatrix}$$

代入方程迭代三次，迭代1

$$\begin{bmatrix} X_1(1) \\ X_2(1) \\ X_3(1) \end{bmatrix} = \begin{bmatrix} 0 & 0.5 & 0.7 \\ 0.3 & 0 & 0.55 \\ 0.01 & 0.1 & 0 \end{bmatrix} \begin{bmatrix} Y_1(0) \\ Y_2(0) \\ Y_3(0) \end{bmatrix}= \begin{bmatrix} 0 \\ 0\\ 0 \end{bmatrix}$$

$$\begin{bmatrix} Y_1(1) \\ Y_2(1) \\ Y_3(1) \\ \end{bmatrix}= f\begin{bmatrix} X_1(1) \\ X_2(1)\\ X_3(1) \end{bmatrix}= \begin{bmatrix} 0.5 \\ 0.5 \\ 0.5 \end{bmatrix}$$

迭代2

$$\begin{bmatrix} X_1(2) \\ X_2(2) \\ X_3(2) \end{bmatrix} = \begin{bmatrix} 0 & 0.5 & 0.7 \\ 0.3 & 0 & 0.55 \\ 0.01 & 0.1 & 0 \end{bmatrix} \begin{bmatrix} Y_1(1) \\ Y_2(1) \\ Y_3(1) \end{bmatrix}= \begin{bmatrix} 0.6 \\ 0.425\\ 0.055 \end{bmatrix}$$

$$\begin{bmatrix} Y_1(2) \\ Y_2(2) \\ Y_3(2) \\ \end{bmatrix}= f\begin{bmatrix} X_1(2) \\ X_2(2)\\ X_3(2) \end{bmatrix}= \begin{bmatrix} 0.6457 \\ 0.6047 \\ 0.5137 \end{bmatrix}$$

迭代3

$$\begin{bmatrix} X_1(3) \\ X_2(3) \\ X_3(3) \end{bmatrix} = \begin{bmatrix} 0 & 0.5 & 0.7 \\ 0.3 & 0 & 0.55 \\ 0.01 & 0.1 & 0 \end{bmatrix} \begin{bmatrix} Y_1(2) \\ Y_2(2) \\ Y_3(2) \end{bmatrix}= \begin{bmatrix} 0.7543 \\ 0.5263\\ 0.0578 \end{bmatrix}$$

$$\begin{bmatrix} Y_1(3) \\ Y_2(3) \\ Y_3(3) \\ \end{bmatrix}= f\begin{bmatrix} X_1(3) \\ X_2(3)\\ X_3(3) \end{bmatrix}= \begin{bmatrix} 1.4703 \\ 1.5908 \\ 1.9438 \end{bmatrix}$$

1.2 (b)

本题考查对神经网络三个层的概念的理解。隐藏层给予模型一个额外的因素，使得神经网络能够对数据中非线性部分建模。

1.3 ©

本题考查分类与拟合的区别。人工神经网络分类器是用来对数据类别进行建模的，要么是0，要么是1。而拟合器将数据输出变量作为连续变量来进行拟合，这个连续变量是有界的。

1.4 (d)

本题考察最常用的训练算法-反向传播。最受欢迎的算法是反向传播算法，它的工作原理是减少预测数据和实际数据之间的误差。一些其它的算法，例如搜索算法中的Newton Raphson算法可以用来拟合模型的参数

2 Q2

2.1 (a)

本题考察Membership function 的由来和作用
Membership function将Membership value分配给对应的概念，它介于0到1之间。Membership Value代表了这个实例多大程度上属于这个集合，完全不属于是0，完全属于是1.通过模糊确切的集合边界，Membership function将不精确的概念进行建模，从crisp set的明确从属关系转变为了fuzzy set的多大程度的从属关系。

例如，对于一场60分及格的考试，令

$$u_A(x)=\begin{cases} 0\quad 0\leq x<40 \\ \frac{1}{20}(x-40)\quad 40\leq x<60 \\ 1\quad 60\leq x\leq 100 \end{cases}$$

越接近60，学生就更大程度上属于及格的集合里，Fuzzy value就会越大，当学生的成绩大于60时，就完全属于及格，此时Fuzzy value 为1.

2.2 (b)

本题考查Fuzzy set的基本运算
由Fuzzy set的运算，Fuzzy set的并集是找集合的最大值，即

$$u_A(x) \cup u_B(x) = \max \{u_A(x),u_B(x)\}$$

则并集

$$A\cup B = \max\{A,B\}$$

Fuzzy set的交集是找最小值，即

$$u_A(x) \cap u_B(x) = \min \{u_A(x),u_B(x)\}$$

则交集

$$A\cap B = \min\{A,B\}$$

则函数应该为一个分段函数，需要找到分段点。令$A=B$

$$e^{-\frac{(x-2)^2}{2}} = e^{-\frac{(x-4)^2}{2}}$$

两侧取对数，得到

$$\begin{aligned} \frac{(x-2)^2}{2} &= \frac{(x-4)^2}{2} \\ \Rightarrow x^2-4x+4 &= x^2-8x+16 \\ \Rightarrow 4x &= 12 \\ \Rightarrow x &= 3 \end{aligned}$$

令$f(x) = e^{-\frac{(x-2)^2}{2}} - e^{-\frac{(x-4)^2}{2}}$, 则$x_0=3$为函数的一个零点。

现证明，在区间$[0,5]$内$x_0$零点唯一。
对$e^{h(x)}$使用Lagrange中值定理，得到

$$\begin{aligned} f(x) &= e^\xi [-\frac{(x-2)^2}{2}+\frac{(x-4)^2}{2}] \\ &=e^\xi [-2x+6] \end{aligned}$$

where $\xi$ is between $-\frac{(x-2)^2}{2}$ and $-\frac{(x-4)^2}{2}$

注意到$e^\xi >0$, 则$f(x)$在区间$[0,5]$上仅存在零点$x_0=3$。
$Q.E.D$

那么，

$$\begin{aligned} A\cup B &= \max\{A,B\} \\ &=\begin{cases} e^{-\frac{(x-2)^2}{2}} \quad x< 3 \\ e^{-\frac{(x-4)^2}{2}} \quad x\geq 3 \end{cases} \end{aligned}$$

$$\begin{aligned} A\cap B &= \min\{A,B\} \\ &=\begin{cases} e^{-\frac{(x-4)^2}{2}} \quad x<3 \\ e^{-\frac{(x-2)^2}{2}} \quad x\geq 3 \end{cases} \end{aligned}$$

2.3©

主要有两种模糊推理机制，第一种是Mamdani，第二种是Sugeno。
对于第一种Mamdani type，要分以下几个步骤

1. 模糊化：将crsip input value模糊化为fuzyy value，即通过制订好的Fuzzy set得到输入对于对应集合的Fuzzy Value。
2. 规则评估：通过事先制订好的前项(antecendents)，即if, and, or, then 规则，对Fuzzy set进行推理运算，得到所有的规则运算下的结果，再根据结果对后项(consequent)Membership function进行$\alpha-cut$.
3. 聚合(Aggregation)输出：将得到的$\alpha-cut$函数拼接在一起聚合输出
4. 去模糊化(Defuzzification)：计算拼接得到的聚合函数的质心。质心的计算公式为

$$COG = \frac{\int_a^b xu_A(x)dx}{\int_a^bu_A(x)dx}$$

或离散情况下

$$COG = \frac{\sum\limits_{x=a}^bxu_A(x)}{\sum\limits_{x=a}^bu_A(x)}$$

对于第二种Sugeno Fuzzy Inference，它与Mamdani方法不同的是输出是后项输出是一个常数，主要是规则评估环节不同，得到前项的推理运算结果之后，我们截断的时候只取单例。最后聚合的时候也是只得到几个单例，而不是一个连续的函数。最后的逆模糊化就是加权平均值

$$WA = \frac{\sum\limits_{i=1}^n u(k_i)k_i}{\sum\limits_{i=1}^n u(k_i)}$$

2.4 (d)

第一种是质心去模糊化(Centroid Defuzzification)，此方法计算模糊集的质心并将该质心用作去模糊化的输出，它通常用于需要精确输出的应用中，比如控制系统。优点是输出精确。
第二种是最大均值去模糊化(Mean of Maximum Defuzzication)，此方法选择模糊集中最大隶属值(Membership value或Fuzzy value)的平均值。它通常用于要考虑运算速度的应用中，因为它是一种快速的去模糊化方法。优点是计算速度快。
第三种是Smallest of Maximum Defuzzification(SOM)，此方法在模糊集中选择最大隶属值中的最小值，通常用于需要保守输出(conservative output)的应用中。

第三种不考

3 Q3

3.1 (a)

本题考查遗传算法中选择和重组的方法。
选择(selection)方法一般有轮盘赌(Roulette Wheel Selection)，排名选择(Rank-based selection)和竞赛选择(Tournament selection)。

1. 轮盘赌选择：此方法根据个体的适应度给群体中的每个个体分配一个概率，具有较高的适应度的个体被选中的概率更大。优点是选择上是基于概率的，则适应度低的个体也是有几率被选中的，这样可以维护种群多样性，缺点是适应度低的个体被留下来可能延缓进化过程。
2. 竞赛选择(Tournament selection):这种方法从种群中随机选择少数个体，然后再从选出来的个体中选择适应度较高的个体。这种方法的优点是实现起来相对简单，并且比轮盘赌运算速度上更快。缺点是会导致种群多样性丧失，因为它只选择了有最高适应度的个体
3. 排名选择(Rank selection):根据个体的适应度为种群中的每个个体分配一个等级，适应度最高的个体获得最高的等级。一个个体被选择的概率就正比于它的排名。优点是收敛速度更快，因为每次都选择适应度相对高的个体，进化过程迅速。缺点是这样做会丢失很多信息，丧失多样性，可能陷入局部最优。

再生方法(regeneration)一般有隔代再生(Generational Reproduction)和稳态再生(Steady-state Reproduction)

1. 隔代再生：整个种群在每一代都有可能被替换掉。它的流程是循环$N/2$此，$N$代表种群大小，每次循环选择两个个体来产生两个子代，最终产生N个。这样做的好处是进化更加快速，缺点是抛弃亲本就可能损失一些重要的信息，例如可能在亲本中的最优基因
2. 稳态：这种做法将两个个体的染色体交叉产生子代后又把他们放回种群，然后去掉适应度最低的个体。一般来讲我们会取亲本的$50\%$和子代的$50\%$，取它们中适应度最高的个体。这样做的好处是亲本中的一些信息被保留了下来，缺点是进化程度可能不够，因为老一代的个体一直在种群中。

3.2 (b)

本题考查遗传算法适应度的概念以及规定的测量适应度函数的计算

3.2.1 (i)

本小问考查适应度的概念和计算。由题知，测量适应度的函数被定义为

$$f(x) = \sum_{i=1}^5 \sin (2\pi x_i)$$

(感觉给的定义不是很准确，遍历求和的应该是基因而不是个体$x_i$)并且定义适应度高的个体是函数值接近0的个体。

个体的基因已经给在条件中了。接下来分别计算每个个体的适应度。

$$\begin{cases} F_{x_1} = \sin (2\pi \times 2.8)+\sin (2\pi \times 0.3)+\sin (2\pi \times 3)+\sin (2\pi \times 1.5)+\sin (2\pi \times 2.8) = -0.9511 \\ F_{x_2} = \sin (2\pi \times 0.4)+\sin (2\pi \times 0.8)+\sin (2\pi \times 0.5)+\sin (2\pi \times 2.5)+\sin (2\pi \times 2.5) = -0.3633 \\ F_{x_3} = \sin (2\pi \times 2.8)+\sin (2\pi \times 1.7)+\sin (2\pi \times 3)+\sin (2\pi \times 0.5)+\sin (2\pi \times 3) = -1.9021 \\ F_{x_4} = \sin (2\pi \times 1.9)+\sin (2\pi \times 3)+\sin (2\pi \times 3)+\sin (2\pi \times 1.3)+\sin (2\pi \times 2) = 0.3633 \\ \end{cases}$$

那么，适应度高的排在前面，适应度低的排在后面，得到排序为

$$x_4=x_2>x_1>x_3$$

3.2.2 (ii)

本题考查交叉产生后代的方法，使用单点交叉。
题目要求交叉适应度排在前两位的个体和适应度排在后两位的个体。首先我们交叉前两位的个体。它们的基因段为

$$\begin{aligned} x_4 = \begin{bmatrix} 1.9 & 3.0 & 3.0 & 1.3 & 2.0 \end{bmatrix}\\ x_2 = \begin{bmatrix} 0.4 & 0.8 & 0.5 & 2.5 & 2.5 \end{bmatrix} \end{aligned}$$

按照要求在第二个元素的位置作为切点交换两个基因片段，则交换后的结果为

$$\begin{aligned} x_a = \begin{bmatrix} 0.4 & 0.8 & 3.0 & 1.3 & 2.0 \end{bmatrix}\\ x_b = \begin{bmatrix} 1.9 & 3.0 & 0.5 & 2.5 & 2.5 \end{bmatrix} \end{aligned}$$

同理，对于后两位的个体

$$\begin{aligned} x_1 = \begin{bmatrix} 2.8 & 0.3 & 3.0 & 1.5 & 2.8 \end{bmatrix}\\ x_3 = \begin{bmatrix} 2.8 & 1.7 & 3.0 & 0.5 & 3.0 \end{bmatrix} \end{aligned}$$

交换后得到

$$\begin{aligned} x_c = \begin{bmatrix} 2.8 & 1.7 & 3.0 & 1.5 & 2.8 \end{bmatrix}\\ x_d = \begin{bmatrix} 2.8 & 0.3 & 3.0 & 0.5 & 3.0 \end{bmatrix} \end{aligned}$$

利用之前的适应度测量函数进行计算，得到

$$\begin{cases} x_a = 0.5878 \\ x_b = -0.5878 \\ x_c = -2.85 \\ x_d = 0 \end{cases}$$

那么适应度的排序应该为

$$x_d>x_a>x_b>x_c$$

在上一代和交换过后的下一代中，精英(适应度最高的个体)分别为上一代的$x_4$和下一代的$x_d$。

使用稳态选择，就选择上一代的$50\%$和下一代的$50\%$，同时应该选择适应度最高的个体，即上一代中排名前二的个体和下一代中排名前二的个体:$\{x_d,x_a,x_4,x_2\}$.

3.3 ©

本题考查卷积神经网络的基本概念，以及应用的场景。
卷积神经网络是一种特别适合处理图像的神经网络，它非常擅长处理具有矩阵结构的数据，比如图像。

一个卷积神经网络包含以下几个层

1. 输入层：这一层接受输入的数据，一般是一个图像
2. 卷积层：这一层在输入数据上做卷积运算。它使用一个小的矩阵在数据上滑动，这个矩阵被称为卷积核或者滤波器，滑动的同时做哈达玛积(Hadamard product, 做法是逐个元素相乘称为新矩阵)并相加(或者表述为逐个元素相乘相加)得到卷积后的结果
3. 池化层：这一层通过选取卷积结果中相邻单元的最大值或者平均值来对卷积结果进行降采样，这样有利于减少数据尺寸并提取到最重要的特征。
4. 全连接层：这一层是标准的全连接神经网络，它将池化层的输出再次映射到我们想要的输出数据结构。

可以将CNN的结构表示如下
输入层 -> 卷积层 -> 池化层 -> 扁平化(flat)输出 -> 全连接层 -> 输出

CNN的主要应用是图像内容的分类和目标识别检测任务。例如图像或视频的对象检测，人脸识别和医学图像分析。也可以将语音转化为梅尔频谱图之后，对梅尔频谱图使用卷积神经网路来进行语音识别等任务。

4 Q4

4.1 (a)

4.1.1 (i)

本题考查人眼视觉功能。如果用白纸盖在眼睛上并且直视太阳，由于透过白纸的太阳光仍然很强，人眼会自动调整自己的瞳孔大小去适应太阳的光线，此时由于白纸本身相对于太阳亮度很低，就会造成看到的白纸的颜色变成了更黑的颜色。所以正确答案是d，亮度适应。

4.1.2 (ii)

本题考查图像的量化，图像的量化包括对灰度和空间位置的量化，所以应该选d，量化一个图像像素能承受的亮度值(注意value在美术里也指亮度)。

4.2 (b)

本题考查图像存储的基本概念。
由题目可得，我们图像的竖直边有1125个像素，又长宽比是$16:9$，那么我们可以得到横边应该有

$$w = 1125\times \frac{16}{9} = 2000$$

则图像是一个$I_{1125\times 2000}$的矩阵。

同时，题目告诉我们图像是彩色的，它的色彩空间是$(R,G,B)$，那么矩阵中每一个元素又是一个三维向量，每个颜色的深度是$8bit$，可以得到，对于一个像素来讲，它有$3\times 8 = 24bits$。

对于单张图像来说，就有

$$1125\times 2000\times 24 = 5.4\times 10^7 bits$$

又一秒包含了30张图像，则一秒钟有

$$5.4\times 10^7\times 30 = 1.62\times 10^9bits$$

两小时即$7200s$，那么需要的比特数为

$$1.62\times 10^9\times 7200 = 1.1664\times 10^{13}bits$$

4.3 ©

本题考查4邻居，8邻居以及4邻接和8邻接的概念。
对于$S_1$和$S_2$两个子集，注意到$S_1$的右下角和$S_2$的左下角的两个1是对角线邻接的。令$p$为$S_1$右下角为1的像素，$q$为$S_2$左下角的像素，则有

$$q\notin N_4(p)$$

注意到，$p,q$是可以通过对角线连接的，意味着p和q是可以8邻接的，即

$$q \in N_8(p)$$

那么这两个集合是8邻接的，而不是4邻接的。

4.4 (d)

本题考查图像基本运算中的减法。
减法的表达为

$$I_1 - I_2$$

这种方法被用来揭示两张图片中有差异的或变化的地方。在检测产品装配中的缺失组件时，"golden image"用作正常产品的参考，那么与其它产品的图片相减时，就能突出显示两个图片中的差异。

从矩阵运算的角度来说，减法就是对每个元素，也就是像素相减，如果像素值一样，那么结果为0，即没有差异，表现为纯黑色；如果像素值不一样，那结果就不为0，就有差异，就不会是纯黑色。在减去的图像上我们就能看出来哪些地方是非纯黑的，那些像素就代表了有差异的地方。

为了利用这个技术来检测不同，应该满足以下条件

1. 两张图片应该大小相同，有相同的分辨率
2. 拍摄角度应该相同，光照也应该相同，如果因为透视、构图和光线的不同造成图片存在差异，我们就无法判断到底是不是部件缺失造成的。
3. "golden image"应该是准确反映产品标准的。

5 Q5

5.1 (a)

graph LR;
    A[Input Image] --> B[Contruct nxn subimage] --> C[Forward transform] --> D[Quantizer] --> E[Symbol encoder] --> F[Compressed Image]

因为是灰度图像，所以我们无需转换色彩空间。

1. 首先以$8\times 8$的大小划分整个图像得到子图，
2. 再对子图做前向变换，也就是离散余弦变换(DCT)，
3. 再之后进行量化，这一步利用量化器，例如Max-Lloyd 最优量化器来量化DCT的系数，这会进一步减少数据量。一般来说，变换后矩阵的左上角，即低频信号包含了大部分有用的信息，就需要更精确的量化，而右下角是高频信号，对于人眼来说作用不大，就使用更粗略的量化，甚至直接置零
4. 最后进行编码，这一步利用Huffman编码方法进一步增加信息密度，使得最终储存量更小

5.2 (b)

5.2.1 (i)

利用表格法进行编码，前向计算生成的二叉树为

Symbol	Probability	1	2	3
$a_2$	0.42	0.42	0.42	0.58
$a_4$	0.30	0.30	0.30	0.42
$a_1$	0.12	0.16	0.28
$a_3$	0.09	0.12
$a_5$	0.07

反向赋予编码为

Symbol	Probability	1	2	3
$a_2$	0.42 $\quad 1$	0.42 $\quad 1$	0.42 $\quad 1$	0.58 $\quad 0$
$a_4$	0.30 $\quad 00$	0.30 $\quad 00$	0.30 $\quad 00$	0.42 $\quad 1$
$a_1$	0.12 $\quad 011$	0.16 $\quad 010$	0.28 $\quad 01$
$a_3$	0.09 $\quad 0100$	0.12 $\quad 011$
$a_5$	0.07 $\quad 0101$

5.2.2 (ii)

平均长度的计算公式为

$$\bar L = \sum\limits_{k=1}^n P(a_k)len(a_k)$$

其中$len(a_k)$是对$a_k$的编码长度，则

$$\begin{aligned} \bar L &= 0.42\times 1+0.3\times 2+ 0.12\times 3+0.09\times 4+0.07\times 4 \\ &=2.02bits \end{aligned}$$

5.2.3 (iii)

对于一个prefix-free编码空间来说，编码过后的各字段放在一起不能产生混淆。显然，对于$s_1=1$,$s_2=0$,$s_3=10$来说，当出现10的时候，会有两种情况，编码的信源可能是$s_1s_2$，也可能是$s_3$，那么就会产生混淆，不能说它是prefix-free的编码

5.3 ©

当仅有三种不同值的时候，记三种值分别为$A,B,C$，进行二叉树编码
Case 1:三个频率相同
此时有

$$P(A) = P(B) = P(C) = \frac{1}{3}$$

则前项二叉树为

symbol	probability	1
A	$1/3$	$2/3$
B	$1/3$	$1/3$
C	$1/3$

反向编码为

symbol	probability	1
A	$1/3$$\quad 1$	$2/3$ $\quad 0$
B	$1/3$ $\quad 00$	$1/3$ $\quad 1$
C	$1/3$ $\quad 01$

且不难发现，轮换三个码元的位置，编码集都是一样的。
Case 2:三个频率不同
此时前项二叉树有

symbol	probability	1
A	$P(A)$	$P(A)或P(B)或P(C)$
B	$P(B)$	$P(A)+P(B)$或$P(B)+P(C)$或$P(A)+P(C)$
C	$P(C)$

注意到，如果要让此时的编码与case 1不同，则$P(A)$必须有最高的概率，且满足

$$P(A) > P(B)+P(C)$$

满足上述不等式时$P(A)$在第二轮重排时才会保持第一位。
那么此时的前项二叉树可以被确定为

symbol	probability	1
A	$P(A)$	$P(A)$
B	$P(B)$	$P(B)+P(C)$
C	$P(C)$

现在进行反向编码

symbol	probability	1
A	$P(A)$ $\quad 0$	$P(A)$ $\quad 0$
B	$P(B)$ $\quad 10$	$P(B)+P(C)$ $\quad 1$
C	$P(C)$ $\quad 11$

现证明，仅上述两种编码为不同的独立的编码。

1. 对于频率不相等的情况，如果不满足$P(A)>P(B)+P(C)$则第二轮排序时$P(A)$会被放到第二位，不难验证此时的编码与case 1相同。

2. 对于频率不相等的情况，如果不满足$P(A)$为最高概率，则

   $$\begin{aligned} P(A) &< \max \{P(B),P(C)\} \\ &< P(B)+P(C) \end{aligned}$$

   since $P(A),P(B),P(C)>0$
   则第二轮重排也一定会排在第二位。

3. 对于$P(B)$和$P(C)$排第一的情况，与$P(A)$对偶。

上述为所有可能情况，则仅之前讨论的两种编码为不同的独立的编码
$Q.E.D.$

综上，不同的编码为$0,11,10$和$1,00,01$

6 Q6

6.1 (a)

6.1.1 (i)

图像恢复就是从观察到的图像中去除退化因素(degradation)从而获得更接近原始图像的过程。图像质量下降可能是因为模糊(blur)，噪声(noise)或者压缩伪象(compression artifacts)。

这个过程可以表示为

1. 原始图像(Original Image)
2. 退化(Degradation),例如模糊与噪声
3. 被观察图像(Observed Image)或者(Degraded Image)
4. 加性噪声(Noise),例如Gaussian noise, salt-and-pepper noise
5. 恢复滤波器(Restoration Filter)，比如Wiener filter
6. 重建后图像(Reconstructed Image)或者(Restored Image)

6.1.2 (ii)

椒盐噪声的PDF为

$$p(z)=\begin{cases} P_s\quad z = 2^k-1 \\ P_p \quad z = 0\\ 1-(P_s+P_p)\quad z=V \end{cases}$$

where

$$V\in (0,2^k-1)$$

and $k$ is the number of bits used to represent the intensity values in an image.

6.1.3 (ii)

显然，第一张的噪声是Gaussian分布的，所以第一张图像的噪声类型是Gaussian Noise

显然，第二张照片的噪声是指数分布的，所以第二张图像的噪声类型是Exponential Noise

显然，第三张照片是均匀分布的，所以第三张图像的噪声类型是Uniform Noise

显然，最后一张照片是冲击噪声，所以第四张照片的噪声类型是salt-and-pepper noise

6.2(b)

6.2.1 (i)

1. 对于条件(1)，单增的函数可以保证输出强度值不会比输入值低，这样就防止了由于强度的反转导致的伪象(artifacts).
   preventing artifacts created by reversals of intensity.
2. 条件(2)保证了输出强度的范围和输入是一样的。

由于$P_r(\omega)$是一个概率密度函数(PDF)，那么函数非负，积分就是单增的。又概率分布函数(CDF)最大值为1，那么$T(r)$最大值也就是$L-1$，最小值则令$r=0$得到为0.

6.2.2 (ii)

对于一个概率分布变换来说，如果$\exists s = T(r)$, $s.t.$,

$$P_r(r) \rightarrow P_s(s)$$

则有以下关系成立

$$P_s(s) = P_r(r)\cdot |\frac{dr}{ds}|$$

注意到

$$\frac{dr}{ds} = \frac{1}{\frac{ds}{dr}}$$

且

$$\begin{aligned} \frac{ds}{dr} &= \frac{d}{dr}(L-1)\int_0^rP_r(\omega)d\omega \\ &= (L-1) P_r(r) \end{aligned}$$

则有

$$\begin{aligned} P_s(s) &= P_r(r)\cdot \frac{1}{(L-1)P_r(r)} &= \frac{1}{L-1} \end{aligned}$$

则变换后的分布是均匀分布，它满足直方图的均衡化。
$Q.E.D.$

6.2.3 (iii)

在变换$s=T(r)$中我们不要求函数$T(r)$是严格单调递增的，则变换的映射不是一对一的(not one-to-one mapping)，这样一来$T(r)$就可能不存在反函数，从而均衡化一般来说是不可逆的。

6.2.4 (iv)

利用公式

$$\begin{aligned} s &= (2-1)\int_0^r (-2\omega+2)d\omega \\ &= -r^2+2r \end{aligned}$$