数字图像处理题库 5:计算问题 ③
前言
这是我在学习数字图像处理这门课程时,从网络上以及相关书籍中搜集到的一些题目, 这些题目主要是针对期末考试的。 做题之前你需要注意以下几点:
- 这篇文章整理了第5种题型,即计算题的第3部分。
- 由于题目或答案中会出现许多的公式,重新编写很费时间,因此,我会将整个题目或答案截成图片来代替。
- 为了提高复习的效率,这篇文章从考试可能涉及到的各个考点出发, 将题目按照考点归类,每一个考点中包括知识点回顾、经典例题、举一反三这3个部分。
- 如果你需要举一反三中练习题的答案,可以前往我的个人主页下载对应的资源(整理不易,希望大家支持)。
考点21:香农—范诺编码
知识点回顾
香农—范诺(Shannon-Fannon)编码也是一种典型的可变字长编码。与哈夫曼编码相似,当信源符号出现的概率正好为2的负幂次方时,香农—范诺编码的编码效率可以达到100%。
香农—范诺编码的理论基础是符号的码字长度N i完全由该符号出现的概率来决定,对于二进制编码即有
编码步骤
- 将信源符号按其出现的概率由大到小顺序排列,若两个符号的概率相等,则相等概率的字符顺序可以任 意排列;
- 计算出各概率符号所对应的码字长度N i;
- 将各符号的概率累加,计算累加概率P,即:
- 把各个累加概率P由十进制转换为二进制;
- 取二进制累加概率前N i位的数字,并省去小数点前的“0.”字符
- 即为对应信源符号的香农—范诺编码码字
经典例题
设一幅灰度级为8的图像中,各灰度级分别用S0、S1、S2、S3、S4、S5、S6、S7表示,对应的概率分别为0.40、0.18、0.10、0.10、0.07、0.06、0.05、0.04,对其进行香农—范诺编码。并分别计算图像信息熵,平均码字长,效率以及信息冗余度
将信源符号按其出现概率由大到小顺序排列,为0.40,0.18,0.10,0.10,0.07,0.06,0.05,0.04;
(2) 对于概率0.40对应的符号S0,根据(8-11)计算N0=2,将累加概率0.00转换位二进制小数为0.00,取前N0=2位,并去除小数点前的字符,即S0字符编码为00;
(3) 对于概率0.18对应的符号S1,根据(8-11)计算N1=3,将累加概率0.40转换位二进制小数为0.0110,取前N1=3位,并去除小数点前的字符,即S1字符编码为011;
(4) 对于概率0.10对应的符号S2,根据(8-11)计算N2=4,将累加概率0.58转换位二进制小数为0.10010,取前N2=4位,并去除小数点前的字符,即S2字符编码为1001;
(5) 对于概率0.10对应的符号S3,根据(8-111)计算N3=4,将累加概率0.68转换位二进制小数为0.10100,取前N3=4位,并去除小数点前的字符,即S3字符编码为1010;
(6) 对于概率0.07对应的符号S4,根据(8-11)计算N4=4,将累加概率0.78转换位二进制小数为0.11000,取前N4=4位,并去除小数点前的字符,即S4字符编码为1100;
(7) 对于概率0.06对应的符号S5,根据(8-11)计算N5=5,将累加概率0.85转换位二进制小数为0.1101100,取前N5=5位,并去除小数点前的字符,即S5字符编码为11011;
(8) 对于概率0.05对应的符号S6,根据(8-11)计算N6=5,将累加概率0.91转换位二进制小数为0.1110100,取前N6=5位,并去除小数点前的字符,即S6字符编码为11101;
(9) 对于概率0.04对应的符号S7,根据(8-11)计算N7=5,将累加概率0.68转换位二进制小数为0.11110100,取前N7=5位,并去除小数点前的字符,即S7字符编码为11110;
综上所述,S1-S7的香农—范诺编码如下:
灰度级 |
S0 |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
编码 |
00 |
011 |
1001 |
1010 |
1100 |
11011 |
11101 |
11110 |
考点22:费诺—仙农编码
知识点回顾
费诺—仙农编码与Huffman编码相反,采用从上到下的方法。
香农-范诺编码算法步骤:
(1)按照符号出现的概率减少的顺序将待编码的符号排成序列。
(2)将符号分成两组,使这两组符号概率和相等或几乎相等。
(3)将第一组赋值为0,第二组赋值为1。
(4)对每一组,重复步骤2的操作。
经典例题
设一幅灰度级为8的图象中,各灰度所对应的概率如下表,要求对其进行费诺.仙侬编码。
灰度值 |
S0 |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
出现频率 |
0.40 |
0.18 |
0.10 |
0.10 |
0.07 |
0.06 |
0.05 |
0.04 |
解:根据费诺—仙农编码的方法进行分组和赋值如下图所示
所得编码结果如下表
灰度值 |
S0 |
S1 |
S2 |
S3 |
S4 |
S5 |
S6 |
S7 |
费诺—仙农码 |
00 |
01 |
100 |
101 |
1100 |
1101 |
1110 |
1111 |
考点23:LZW编码
知识点回顾
前几节中所覆盖的技术集中在消除编码冗余上。在这一节中,我们考虑一种致力于图像中的空间冗余的无误差压缩方法。称为Lempel-Ziv-Welch(LZW)编码的这种技术将定长码字分配给变长信源符号序列。
在第一定理的证明中,山农使用了信源符号编码序列这一思想,而不是单个信源符号。LZW 编码的关键特点是它不需要被编码符号出现的概率的先验知识。
LZW编码的原理
LZW 编码在概念上非常简单。
在编码过程的开始阶段,先构建一个包含被编码信源符号的码书或字典。对于8比特单色图像,字典中的前 256个字被分配给灰度值O.1.2,……,255。
当编码器顺序地分析图像像素时,不在字典中的灰度序列被放置在算法确定的位置(即下一个未用的位置)。
例如,如果图像的前两个像素为白色,则序列"255-255"可能被分配到 256 的位置,该位置后面的地址保留给灰度级 0 到 255。下次遇到两个连续的白色像素时,就用码字 256(即包含序列 255-255的位置的地址)来表示它们。
如果在编码过程中采用个9 比特、512字的字典,则最初用于表示这两个像素的(8+8)比特被单个9 比特码字替代。
很明显,字典的大小是一个很重要的系统参数。
- 如果字典太小,则匹配灰度级序列的检测将变得不太可能。
- 如果字典太大,则码字的大小反而会影响压缩性能。
LZW编码的特点
LZW 编码的一个独特的特点是,编码字典或码书是在对数据进行编码的同时创建的。很明显,在 LZW解码器对编码数据流进行解码的同时建立一个同样的解压缩字典。
多数实际应用都需要—种处理字典溢出的策略。一种简单的解决办法是,当字典已满时,刷新或重新初始化该字典,并使用一个新初始化后的字典继续编码。另一种复杂的选择是,监控压缩性能,并在性能变得低下或不可接受时刷新字典。此外,需要时,可跟踪并替换那些使用最少的字典词条。
经典例题
【冈萨雷斯《数字图像处理》第3版 P352 例题8.7】
考虑下列大小为 4x4的8比特垂直边缘图像,并假设一个512字带有下列初始内容的字典(位置256到511开始时未使用)
下表中详细给出了对其16个像素进行编码的步骤。
图像按从左到右、从上到下处理其像素的方法来进行编码。每个连续的灰度值与表中称之为"当前可识别的序列"的第 1 列的一个变量链接。就像我们能看到的那样,该变量最初为空。
对每一个链接的序列搜索字典,如果找到了,如表中第一行的情况,则用新链接且可识别的序列(即位于字典中的序列)替代它。这可在第2行的第1列中实现。这既不产生输出代码,也不更改字典。
然而,如果没有找到链接的序列,则将当前可识别序列的地址作为下一个编码值输出,并将链接但不可识别的序列添加到字典中,当前可识别的序列则初始化为当前的像素值。这出现在表中的第 2 行。
最后两列详细给出了扫描整个4x4 图像时添加到了字典中的灰度序列。定义了9个附加的码字。编码结束时,字典包含 256个码字,且LZW算法成功地识别了几个重复的灰度序列,平衡它们将 128 比特的原图像降到了90 比特(即 10个9比特码)。从上到下读取第3列即可得到编码输出。得到的压缩率是1.42∶1(128:90)。
举一反三
【类似于 冈萨雷斯《数字图像处理》第3版 P400 例题8.19】
1、使用LZW编码算法,对7比特ASCII码字符串"aaaaaaaaaaa”进行编码
【冈萨雷斯《数字图像处理》第3版 P400 例题8.20】
2、为例8.7的LZW编码输出的解码操作设计一种算法。由于编码期间使用的字典此时不能使用,所以在对输出进行解码时必须重新生成码书。
考点24:压缩率
经典例题
对于扫描结果:aaaabbbccdeeeeefffffff,若对其进行霍夫曼编码之后的结果是:f=01 e=11 a=10 b=001 c=0001 d=0000。
- 若使用行程编码和霍夫曼编码的混合编码,压缩率是否能够比单纯使用霍夫曼编码有所提高?
- 若使用行程编码和霍夫曼编码的混合编码,压缩率是否能够比单纯使用行程编码有所提高?
原始扫描结果所占空间为:22*8=176(bits)
单纯霍夫曼编码的结果是:10101010001001001000100010000111111111101010101010101,共占53(bits)。压缩比为176:53.
单纯行程编码的结果是:4a3b2c1d5e7f,共占6(3+8)=66(bits).压缩比为176:66
Hufman与行程编码混合:41030012000110000511701 ,共占3+2+3+3+3+4+3+4+3+2+3+2=35(bits),压缩比为176:35. 即两个压缩比都有所提高。
举一反三
1、一图像大小为640×480 ,256 色。用软件工具SEA(version 1、3)将其分别转成24位色BMP,24位色 JPEG,GIF(只能转成256 色)压缩格式,24位色 TI FF压缩格式,24位色TGA压缩格式,得到的文件大小分别为:921,654 字节;17,707 字节;177,152 字节;923,044 字节;768,136 字节。分别计算每种压缩图像的压缩比。
2、某视频图像为每秒 30 帧,每帧大小为 512×512,32 位真彩色。现有 40 GB 的可用硬盘空间,可以存储多少秒的该视频图像?若采用隔行扫描且压缩比为 10 的压缩方法,又能存储多少秒的该视频图像?
考点25:区域分割、区域增长
知识点回顾
状态法(峰谷法、灰度阈值法)
基本思想:
- 确定一个合适的阈值T。
- 将大于等于阈值的像素作为物体或背景,生成一个二值图像。
- 阈值的选定可以通过如下图中灰度直方图确定。
方法:首先统计最简单图像的灰度直方图,若直方图呈双峰且有明显的谷,则将谷所对应的灰度值T作为阈值,按图右侧的等式进行二值化,就可将目标从图像中分割出来。
这种方法适用于目标和背景的灰度差较大、有明显谷的情况。
在四邻域中有背景的像素,既是边界像素。
简单区域扩张法
步骤:以图像的某个像素为生长点,比较相邻像素的特征,将特征相似的相邻像素合并为同一区域;以合并的像素为生长点,继续重复以上的操作,最终形成具有相似特征的像素是最大连通集合。这种方法称简单(单一型)区域扩张法。
具体步骤:
- 从图像最左上角开始,对图像进行光栅扫描,找到不属于任何的像素。
- 把这个像素灰度同其周围(4邻域或8邻域)不属于其他区域的像素的灰度值和已存在区域的像素灰度 平均值进行比较,若灰度差值小于阈值,则合并到同一区域,并对合并的像素赋予标记。
- 从新合并的像素开始,反复进行(2)的操作。
- 反复进行(2)、(3)的操作,直至不能再合并。
- 返回(1)操作,寻找新区域出发点的像素。
分裂合并法(基于四叉树思想的方法)
- 对于图像中灰度级不同的区域,均分为四个子区域。
- 如果相邻的子区域所有像素的灰度级相同,则将其合并。
反复进行上两步操作,直至不再有新的分裂与合并为止。
经典例题
1) 统计图象1各灰度级出现的频率结果为
p(0) = 5/64≈0.078 p(1)=12/64≈0.188 p(2)=16/64=0.25 p(3)=9/64≈0.141
p(4)=1/64≈0.016 P(5)=7/64≈0.109 p(6)=10/64≈0.156 p(7)=4/64≈0.063
信息量为
2) 对于二值化图象,
若采用4-连接,则连接成分数为4,孔数为1,欧拉数为4-1=3;
若采用8-连接,则连接成分数为2,孔数为2,欧拉数为2-2=0;
2、对下图采用基于区域生长的方法进行图像分割,种子像素选为图中斜线画出的像素,给出生长准则为:邻近像素与当前区域灰度差值T<=2,选用8邻域,请画出这两种情况下的分割结果,重新作图,将分割出来的目标区域用斜线标明。
3、已知二值图像,如右图所示。 (1)对该图像使用四叉树进行划分; (2)用四叉树表达该图像。
举一反三
1、对下面的图像用状态法进行二值化,并计算二值图像的欧拉数(图1)
2、对下面的图像采用简单区域生长法进行区域生长,给出灰度差值 ①T = 1;②T = 3;③T = 8三种情况下的分割图像。(图2)
3、用分裂合并法分割图像,并给出对应分割结果的四叉树。(图3)
考点26:膨胀和腐蚀
知识点回顾
★ 膨胀
膨胀就是把二值图像各1像素连接成分的边界扩大一层的处理。
膨胀的原理:设二值图像为F,结构元素为B,Bs代表B关于原点对称的结构元素。当结构元素Bs的原点移到(x,y)处时,结构元素用表示。则图像F被结构元素B膨胀的定义式为:
含义:当结构元素Bs的原点移动到(x,y)位置时,如果所覆盖范围内的F的子图像与结构元素相应位置上至少有一个元素相同且不为0,则把该子图像中与的原点位置对应的(x,y)点的那个像素位置标注为1,否则为0。图像F上标注出的所有这样的像素组成的集合,即为膨胀运算的结果。
膨胀运算的基本过程是:
- 求结构元素B关于其原点的反射集合Bs;
- 每当结构元素在目标图像F上平移后,结构元素Bs与其覆盖的子图像中至少有一个元素相交时,就将 目标图像中与结构元素Bs的原点对应的那个位置的像素值置为“1”,否则置为0。
注意:
结构元素中原点位置所对应的目标图像子图像位置处的值是0时,仍可进行膨胀运算,无需强求是1。当结构元素在目标图像上平移时,允许结构元素中的非原点像素超出目标图像范围。
结构元素形状对膨胀运算结果的影响:当目标图像不变,但所给的结构元素的形状改变时;或结构元素的形状不变,而其原点位置改变时,膨胀运算的结果会发生改变。
★ 腐蚀(或收缩)
腐蚀是把二值图像各1像素连接成分的边界点去掉从而缩小一层的处理。
腐蚀的原理:设F为目标图像,B为结构元素,则目标图像F被结构元素B腐蚀可定义为
含义:当结构元素B的原点移动到目标图像F中的(x,y)位置时,如果(x,y)处像素值为1,并且Bxy所覆盖范围内的F的子图像的其他像素能够包含Bxy的其他像素或与Bxy的其他像素完全相同,则保留该子图像中与Bxy的原点位置对应的(x,y)点的像素值1,否则均为0。图像F上保留的所有这样值为1的像素组成的集合,即为腐蚀运算的结果。
这里的“包含”是指结构元素B和目标图像F的子图像中值为1的像素两两之间的对应关系。
腐蚀运算的基本过程是:
把结构元素B看作为一个卷积模板,每当结构元素平移到其原点位置与目标图像F中那些像素值为“1”的位置重合时,就判断被结构元素覆盖的子图像的其它像素的值是否都与结构元素相应位置的像素值相同;只有当其都相同时,就将结果图像中的那个与原点位置对应的像素位置的值置为“1”,否则置为0。
注意:
结构元素中的原点位置处的像素值可以不为1,但要求目标图像中的子图像与结构元素B的原点对应的那个位置的像素值是1。
当结构元素在目标图像上平移时,结构元素中的任何元素不能超出目标图像的范围。
腐蚀运算的结果不仅与结构元素的形状(矩形、圆形、菱形等)选取有关,而且还与原点位置的选取有关。
★ 膨胀和腐蚀的作用
膨胀的作用是使孔洞收缩,目标扩大。对消除图像目标中的小颗粒噪声和填补凹陷非常有效。
腐蚀的作用是使目标收缩,孔洞扩大。对去除图像小颗粒噪声和目标之间的粘连非常有效。
★ 开运算V.S 闭运算
A、开运算(先腐蚀再膨胀):
作用:光滑目标轮廓、消除小目标(毛刺和孤立点等),在纤细点处分离物体,同时并不明显改变目标面积;
B、闭运算(先膨胀再腐蚀):
作用:在保持原目标的大小与形态的同时,填充凹陷、弥合孔洞和裂缝。
经典例题
1、用结构元素B对目标图像F进行腐蚀运算。结构元素B中红色为原点。(图1)
2、结构元素不同时的腐蚀运算(图2)、结构元素原点不同时的腐蚀运算(图3)
3、用结构元素B对目标图像F进行膨胀运算。结构元素B中红色为原点(图1)。
4、结构元素不同时的膨胀运算(图2)、结构元素原点不同时的膨胀运算(图3)
举一反三
1、请对下列左侧二值图片做开操作,其中深色代表1,浅色代表0,右侧为采用的结构元素。
2、请对下列左侧二值图片分别做开操作、闭操作,右侧为采用的结构元素。
3、请对下列左侧图片分别做腐蚀操作、膨胀操作,右侧为采用的结构元素。
4、已知二值图象f3,写出用结构元素S(阴影处为原点)对其分别进行腐蚀和膨胀运算结果。
5、请采用适当的方法使下列图片中只保留竖直方向的米粒
6、请采用适当的方法去除下列左侧图片中的一些线段,使最后图片的效果如右图所示
考点27:提取边缘
经典例题
写出一个使用形态学算法提取边缘的方法,并用该方法提取下图 A 的边缘,给出步骤并画出结果图
举一反三
请采用适当方法提取下列图片中物体的轮廓边缘。
其他一些题目
1、下图给出了一幅二值图像,用八方向链码对图像中的边界进行链码表述(起点是 S 点),
(1)写出它的八链码(沿顺时钟),并对该链码进行起点归一化,
(2)说明起点归一化链码与起点无关的原因。
(3)写出其一阶差分码,并说明其与边界的旋转无关;
(4)写出其形状数,并说明阶数。
2、求出链码0101030303323232212111的一阶差分
3、求下图中目标的形状数和形状数的阶。
4、已知一个2X2的图片框的各方向投影如图所示,试求图片框内各像素的灰度值。
5、若灰度相似准则 V={1},试按四连通和八连通分别标出题图所示图像的目标物区域边界。
6、设工业检测中工件的图像受到零均值、与图像不相关噪声的影响。假设图像采集装置每秒可采集 30 幅图,若采用图像平均法将噪声的均方差减小到原来的 1/10,则工件需固定在采集装置前多长时间?
7、求下列数字图像块的二维 DHT(离散哈特莱变换)、二维 DWT(离散小波变换)
8、考虑在 x 方向均匀加速导致的图像模糊问题。如果图像在 t = 0 静止,并用均匀加速x0(t) = 1/2 at^2加速,对于时间 T, 找出模糊函数 H(u,v),可以假设快门开关时间忽略不计。
9、一个大小为 24mm×36mm 的 135 底片。在 36mm 方向上每隔Dmm 交替出现黑条和白条。你有一个 640×480 像素的数字化器。
- 对整个底片数字化能达到的最小像素间距是多少?
- 如果条纹为正弦型且 D=0.15mm,你能否对其数字化且没有混叠问题?
- 如 D=0.3mm,你能否使用2 倍过多采样?倍过多采样?
- 如 D=1mm,并且条纹是非正弦型的,能否计算其频谱到八次谐波(即 Sm=8×条纹的频率)?
10、某信号的功率谱为 Ps ( s ) = 10/∣s∣,噪声是白的并且不相关,其谱幅度为 2。画出维纳滤波器传递函数 H(s),及信噪功率比 R(s),(∣s∣< 20)。这是一个低通,带通,还是高通滤波器?
11、假设图像的灰度级概率密度如题图 7.2 所示。其中 p1( z)对应于目标,p2 (z )对应于背景。如果P1=P2,试求分割目标与背景的最佳门限。
12、某一线性移不变系统,其点扩展函数 h(x,y)是输入为 时系统的输出,求下述情况下的调制转移函数 H(u,v)。
推荐阅读
-
数字图像处理题库 5:计算问题 ③
-
数字图像处理题库 5:计算题 ②
-
数字图像处理题库
-
MATLAB 数字图像处理实验室 5:形态学图像处理
-
贵州师范大学数字图像处理--期末考试题及答案,分享几个实用检索问题和学习工具
-
数字图像处理大作业 Python 项目 数字图像处理程序问题
-
epoll简介及触发模式(accept、read、send)-epoll的简单介绍 epoll在LT和ET模式下的读写方式 一、epoll的接口非常简单,一共就三个函数:1. int epoll_create(int size);创建一个epoll的句柄,size用来告诉内核这个监听的数目一共有多大。这个参数不同于select中的第一个参数,给出最大监听的fd+1的值。需要注意的是,当创建好epoll句柄后,它就是会占用一个fd值,在linux下如果查看/proc/进程id/fd/,是能够看到这个fd的,所以在使用完epoll后,必须调用close关闭,否则可能导致fd被耗尽。2. int epoll_ctl(int epfd, int op, int fd, struct epoll_event *event);epoll的事件注册函数,它不同与select是在监听事件时告诉内核要监听什么类型的事件,而是在这里先注册要监听的事件类型。第一个参数是epoll_create的返回值,第二个参数表示动作,用三个宏来表示:EPOLL_CTL_ADD:注册新的fd到epfd中;EPOLL_CTL_MOD:修改已经注册的fd的监听事件;EPOLL_CTL_DEL:从epfd中删除一个fd;第三个参数是需要监听的fd,第四个参数是告诉内核需要监听什么事,struct epoll_event结构如下:struct epoll_event { __uint32_t events; /* Epoll events */ epoll_data_t data; /* User data variable */};events可以是以下几个宏的集合:EPOLLIN :表示对应的文件描述符可以读(包括对端SOCKET正常关闭); EPOLLIN事件:EPOLLIN事件则只有当对端有数据写入时才会触发,所以触发一次后需要不断读取所有数据直到读完EAGAIN为止。否则剩下的数据只有在下次对端有写入时才能一起取出来了。现在明白为什么说epoll必须要求异步socket了吧?如果同步socket,而且要求读完所有数据,那么最终就会在堵死在阻塞里。 EPOLLOUT:表示对应的文件描述符可以写; EPOLLOUT事件:EPOLLOUT事件只有在连接时触发一次,表示可写,其他时候想要触发,那要先准备好下面条件:1.某次write,写满了发送缓冲区,返回错误码为EAGAIN。2.对端读取了一些数据,又重新可写了,此时会触发EPOLLOUT。简单地说:EPOLLOUT事件只有在不可写到可写的转变时刻,才会触发一次,所以叫边缘触发,这叫法没错的!其实,如果真的想强制触发一次,也是有办法的,直接调用epoll_ctl重新设置一下event就可以了,event跟原来的设置一模一样都行(但必须包含EPOLLOUT),关键是重新设置,就会马上触发一次EPOLLOUT事件。1. 缓冲区由满变空.2.同时注册EPOLLIN | EPOLLOUT事件,也会触发一次EPOLLOUT事件这个两个也会触发EPOLLOUT事件 EPOLLPRI:表示对应的文件描述符有紧急的数据可读(这里应该表示有带外数据到来);EPOLLERR:表示对应的文件描述符发生错误;EPOLLHUP:表示对应的文件描述符被挂断;EPOLLET: 将EPOLL设为边缘触发(Edge Triggered)模式,这是相对于水平触发(Level Triggered)来说的。EPOLLONESHOT:只监听一次事件,当监听完这次事件之后,如果还需要继续监听这个socket的话,需要再次把这个socket加入到EPOLL队列里3. int epoll_wait(int epfd, struct epoll_event * events, int maxevents, int timeout);等待事件的产生,类似于select调用。参数events用来从内核得到事件的集合,maxevents告之内核这个events有多大,这个maxevents的值不能大于创建epoll_create时的size,参数timeout是超时时间(毫秒,0会立即返回,-1将不确定,也有说法说是永久阻塞)。该函数返回需要处理的事件数目,如返回0表示已超时。-------------------------------------------------------------------------------------------- 从man手册中,得到ET和LT的具体描述如下EPOLL事件有两种模型:Edge Triggered (ET)Level Triggered (LT)假如有这样一个例子:1. 我们已经把一个用来从管道中读取数据的文件句柄(RFD)添加到epoll描述符2. 这个时候从管道的另一端被写入了2KB的数据3. 调用epoll_wait(2),并且它会返回RFD,说明它已经准备好读取操作4. 然后我们读取了1KB的数据5. 调用epoll_wait(2)......Edge Triggered 工作模式:如果我们在第1步将RFD添加到epoll描述符的时候使用了EPOLLET标志,那么在第5步调用epoll_wait(2)之后将有可能会挂起,因为剩余的数据还存在于文件的输入缓冲区内,而且数据发出端还在等待一个针对已经发出数据的反馈信息。只有在监视的文件句柄上发生了某个事件的时候 ET 工作模式才会汇报事件。因此在第5步的时候,调用者可能会放弃等待仍在存在于文件输入缓冲区内的剩余数据。在上面的例子中,会有一个事件产生在RFD句柄上,因为在第2步执行了一个写操作,然后,事件将会在第3步被销毁。因为第4步的读取操作没有读空文件输入缓冲区内的数据,因此我们在第5步调用 epoll_wait(2)完成后,是否挂起是不确定的。epoll工作在ET模式的时候,必须使用非阻塞套接口,以避免由于一个文件句柄的阻塞读/阻塞写操作把处理多个文件描述符的任务饿死。最好以下面的方式调用ET模式的epoll接口,在后面会介绍避免可能的缺陷。 i 基于非阻塞文件句柄 ii 只有当read(2)或者write(2)返回EAGAIN时才需要挂起,等待。但这并不是说每次read时都需要循环读,直到读到产生一个EAGAIN才认为此次事件处理完成,当read返回的读到的数据长度小于请求的数据长度时,就可以确定此时缓冲中已没有数据了,也就可以认为此事读事件已处理完成。Level Triggered 工作模式相反的,以LT方式调用epoll接口的时候,它就相当于一个速度比较快的poll(2),并且无论后面的数据是否被使用,因此他们具有同样的职能。因为即使使用ET模式的epoll,在收到多个chunk的数据的时候仍然会产生多个事件。调用者可以设定EPOLLONESHOT标志,在 epoll_wait(2)收到事件后epoll会与事件关联的文件句柄从epoll描述符中禁止掉。因此当EPOLLONESHOT设定后,使用带有 EPOLL_CTL_MOD标志的epoll_ctl(2)处理文件句柄就成为调用者必须作的事情。然后详细解释ET, LT:LT(level triggered)是缺省的工作方式,并且同时支持block和no-block socket.在这种做法中,内核告诉你一个文件描述符是否就绪了,然后你可以对这个就绪的fd进行IO操作。如果你不作任何操作,内核还是会继续通知你的,所以,这种模式编程出错误可能性要小一点。传统的select/poll都是这种模型的代表.ET(edge-triggered)是高速工作方式,只支持no-block socket。在这种模式下,当描述符从未就绪变为就绪时,内核通过epoll告诉你。然后它会假设你知道文件描述符已经就绪,并且不会再为那个文件描述符发送更多的就绪通知,直到你做了某些操作导致那个文件描述符不再为就绪状态了(比如,你在发送,接收或者接收请求,或者发送接收的数据少于一定量时导致了一个EWOULDBLOCK 错误)。但是请注意,如果一直不对这个fd作IO操作(从而导致它再次变成未就绪),内核不会发送更多的通知(only once),不过在TCP协议中,ET模式的加速效用仍需要更多的benchmark确认(这句话不理解)。在许多测试中我们会看到如果没有大量的idle -connection或者dead-connection,epoll的效率并不会比select/poll高很多,但是当我们遇到大量的idle- connection(例如WAN环境中存在大量的慢速连接),就会发现epoll的效率大大高于select/poll。(未测试)另外,当使用epoll的ET模型来工作时,当产生了一个EPOLLIN事件后,读数据的时候需要考虑的是当recv返回的大小如果等于请求的大小,那么很有可能是缓冲区还有数据未读完,也意味着该次事件还没有处理完,所以还需要再次读取: 这里只是说明思路(参考《UNIX网络编程》) while(rs) {buflen = recv(activeevents[i].data.fd, buf, sizeof(buf), 0);if(buflen < 0){// 由于是非阻塞的模式,所以当errno为EAGAIN时,表示当前缓冲区已无数据可读// 在这里就当作是该次事件已处理处.if(errno == EAGAIN)break; else return; }else if(buflen == 0) { // 这里表示对端的socket已正常关闭. } if(buflen == sizeof(buf) rs = 1; // 需要再次读取 else rs = 0; } 还有,假如发送端流量大于接收端的流量(意思是epoll所在的程序读比转发的socket要快),由于是非阻塞的socket,那么send函数虽然返回,但实际缓冲区的数据并未真正发给接收端,这样不断的读和发,当缓冲区满后会产生EAGAIN错误(参考man send),同时,不理会这次请求发送的数据.所以,需要封装socket_send的函数用来处理这种情况,该函数会尽量将数据写完再返回,返回-1表示出错。在socket_send内部,当写缓冲已满(send返回-1,且errno为EAGAIN),那么会等待后再重试.这种方式并不很完美,在理论上可能会长时间的阻塞在socket_send内部,但暂没有更好的办法. ssize_t socket_send(int sockfd, const char* buffer, size_t buflen) { ssize_t tmp; size_t total = buflen; const char *p = buffer; while(1) { tmp = send(sockfd, p, total, 0); if(tmp < 0) { // 当send收到信号时,可以继续写,但这里返回-1. if(errno == EINTR) return -1; // 当socket是非阻塞时,如返回此错误,表示写缓冲队列已满, // 在这里做延时后再重试. if(errno == EAGAIN) { usleep(1000); continue; } return -1; } if((size_t)tmp == total) return buflen; total -= tmp; p += tmp; } return tmp; } 二、epoll在LT和ET模式下的读写方式 在一个非阻塞的socket上调用read/write函数, 返回EAGAIN或者EWOULDBLOCK(注: EAGAIN就是EWOULDBLOCK) 从字面上看, 意思是: * EAGAIN: 再试一次 * EWOULDBLOCK: 如果这是一个阻塞socket, 操作将被block * perror输出: Resource temporarily unavailable 总结: 这个错误表示资源暂时不够, 可能read时, 读缓冲区没有数据, 或者, write时,写缓冲区满了 。 遇到这种情况, 如果是阻塞socket, read/write就要阻塞掉。 而如果是非阻塞socket, read/write立即返回-1, 同 时errno设置为EAGAIN. 所以, 对于阻塞socket, read/write返回-1代表网络出错了. 但对于非阻塞socket, read/write返回-1不一定网络真的出错了. 可能是Resource temporarily unavailable. 这时你应该再试, 直到Resource available. 综上, 对于non-blocking的socket, 正确的读写操作为: 读: 忽略掉errno = EAGAIN的错误, 下次继续读 写: 忽略掉errno = EAGAIN的错误, 下次继续写 对于select和epoll的LT模式, 这种读写方式是没有问题的. 但对于epoll的ET模式, 这种方式还有漏洞. epoll的两种模式 LT 和 ET
-
NeurIPS 2022 | 最强斗地主AI!网易互娱AI Lab提出基于完美信息蒸馏的方法-完美信息蒸馏(PTIE) 在斗地主游戏中,非完美信息的引入主要是由于三位玩家均不能看到别人的手牌,对于任意一位玩家而言,仅可知道其余两位玩家当前手牌的并集,而难于精准判断每位玩家当前手牌。完美信息蒸馏的思路是针对这种非完美问题,构建一个第三方角色,该角色可以看到三位玩家的手牌,该角色在不告知每位玩家完美信息的情况下通过信息蒸馏的方式引导玩家打出当前情况下合理的出牌。 以强化学习常用的 Actor-Critic 算法为例,PTIE 在 Actor-Critic 算法的应用中可以利用 Critic 的 Value 输出作为蒸馏手段来提升 Actor 的表现。具体而言即在训练中 Critic 的输入为完美信息(包含所有玩家的手牌信息),Actor 的输入为非完美信息(仅包含自己手牌信息),此种情况下 Critic 给予的 Value 值包含了完美信息,可以更好地帮助 Actor 学习到更好的策略。 从更新公式上来看,正常的 Actor-Critic 算法 Actor 更新的方式如下: 在 PTIE 模式下,对于每个非完美信息状态 h,我们可以在 Critic 中构建对应的完美信息状态 D(h),并用 Critic 的输出来更新 Actor 的策略梯度,从而达到完美信息蒸馏的效果。 PTIE 框架的整体结构如下图所示: 无论是训练还是执行过程中智能体都不会直接使用完美信息,在训练中通过蒸馏将完美信息用于提升策略,从而帮助智能体达到一个更高的强度。 PTIE 的另一种蒸馏方式是将完美信息奖励引入到奖励值函数的训练中,PerfectDou 提出了基于阵营设计的完美信息奖励 node reward,以引导智能体学习到斗地主游戏中的合作策略,其定义如下: 如上所示,完美信息部分 代表 t 时刻地主手牌最少几步可以出完,在斗地主游戏中可以近似理解为是距游戏获胜的距离, 代表 t 时刻地主阵营和农民阵营距游戏获胜的距离之差, 为调节系数。通过此种奖励设计,在训练时既可以一定程度地引入各玩家的手牌信息(出完的步数需要知道具体手牌才能计算),同时也鼓励农民以阵营的角度做出决策,提升农民的合作性。 特征构建: PerfectDou 针对牌类游戏的特点主要构建了两部分特征:牌局状态特征和动作特征。其中牌局状态特征主要包括当前玩家手牌牌型特征、当前玩家打出的卡牌牌型特征、玩家角色、玩家手牌数目等常用特征,动作特征主要用于刻画当前状态下玩家的所有可能出牌,包括了每种出牌动作的牌型特征、动作的卡牌数目、是否为最大动作等特征。 牌型特征为 12 * 15 的矩阵,如下图所示: 该矩阵前 4 行代表对应每种卡牌的张数,5-12 行代表该种卡牌的种类和对应位置。 网络结构和动作空间设计 针对斗地主游戏出牌组合数较多的问题,PerfectDou 基于 RLCard 的工作上对动作空间进行了简化,对占比最大的两个出牌牌型:飞机带翅膀和四带二进行了动作压缩,将整体动作空间由 27472 种缩减到 621 种。 PerfectDou 策略网络结构如下图所示: 策略网络结构同样分为两部分:状态特征部分和动作特征部分。 在状态特征部分,LSTM 网络用于提取玩家的历史行为特征,当前牌局状态特征和提取后的行为特征会再通过多层的 MLP 网络输出当前的状态信息 embedding。 在动作特征部分,每个可行动作同样会经过多层 MLP 网络进行编码,编码后的动作特征会与其对应的状态信息 embedding 经过一层 MLP 网络计算两者间的相似度,并经由 softmax 函数输出对应的动作概率。 实验结果
-
ClearView 题库 - C 程序设计第 5 版程序设计问题解析 (2)
-
ClearView 题库 - C 程序设计第 5 版程序设计问题解析 (3)