多媒体和算法重点知识

By钱羽中~完全岀自主观判断，不一定是重点，大家参考参考多媒体：感觉媒体、表示媒体、呈现媒体、存储媒体和传输媒体最早应用报职业：20世纪20年代中末期改进Bartlane,提高质量；60年代信息技术-数字图像；70年代数字图像用于医疗。地理信息系统：气彖学，地形分类，操作卫星图像遥感图像：农业普查，森林覆盖计算，水利工程等军事运用：目标跟踪，隐形飞机，定位轰炸交通监控，自动驾驶印刷电路板检测，指纹识别，面部识别应用领域：通信：图像传输，电视电话，HDTV等。宇宙探测：星体图片处理。遥感：地形、地质、矿藏探查，森林、水利、海洋、农业等资源调查，自然灾害预测，坏境污染的监测，气彖云图。生物医学：CT,NMR,PET,SPECT,DSA,X射线成彖，B超，红外图像，显微图像。工业生产：产品质量检测，生产过程控制，CAD,CAM。军事：军事目标侦察，制导系统，警戒系统，自动火器控制，反伪装等。公安：现场照片，指纹，手迹，印章，人像等处理和鉴别。档案：过期的文字、图片档案的修复和处理。机器人视觉娱乐：电影特技，动画，广告，MTV等。采样与量化连续图像-〉离散化-＞数字图像像素：像素值：灰度级、颜色、高度值、透明度分辨率：显示分辨率和图像分辨率(DPI)像素深度：像素深度是指存储每个像素所用的位数调色盘、真彩色、伪彩色RGE模型、HIS模型、CYMK系统三刺激理论颜色三要素：色调、饱和度和明亮度BMP、GIF、PNG、JPG图像增强灰度级变化、直方图处理、图像平滑、图像锐化f(x,y)-＞处理器g(x,y)L-1L-1EH(s)$1s20L-10(d)1/9*图4-17卷积运算示意图1/9*图4-17卷积运算示意图佩J7)-'灰度非线性变换：动态范I韦I压缩 葩19 像的对数费换关報本章作业1：就是设计一个函数，使得将1一5范围的像素点变为0-15of(x,y)=3*g(x,y)直方图技术：作业2：数像素点，画图，极其简单(lec_4_image3、4页)作业在14页上直方图均衡化：首先假定连续灰度级的情况，推导直方图均衡化变换公式，令r代表灰度级，P(r)为概率密度函数。r值已归一化，最人灰度值为1。Ip(r)dr=Ip(s)ds丿o 丿o作业3：lec_4_image第28上起得例题；p35页的例题也可以看一卞。作业在42页上空间平滑滤波增强：邻域均值法和中值滤波法(lec_5_image：P12)加权和计算:Hl・P1+H2•P2+H3-P3十H4・P4+H5・P5+H6•P6+H7・P7十H8・P8+H9・P9+P5的新值

■1111r飞333z222225555H，经过模板操作后的图象为333337777•T■44444-■JTXX•zJT-;其中数字代表灰度山11111111111111111Box模板1212斗2121Gauss模板通常，模板不允许移岀辺界，所以结果图象会比原图小。例如模板足"1.-00'1.，原图是表示边界上无法进行模板塗作的点，通常的作法是复制原图的灰度值，不进行任何处理.「222设图象为4「222设图象为43，分别用两种平滑模板处理（周圉-•圈元素宜接从原图拷■贝儿采用Box模板采用Box模板■2的结果为4LLd223.113.22ao4.33加565666.234采用高斯模板的结果为L5-—234采用高斯模板的结果为L5-—•.中值滤波:低通滤波（lec_5_imagep27起）4.56622-06 356 566.作业4：作业题lec_5_image第54页，用3*3的中值滤波做，排一个序,重复的只算一次（记忆中是这样的）°1112255233255333334234TOC\o"1-5"\h\z8 7 43 33 3255 4 6255 87 8有一幅图像由于受到干扰，图中有若干个亮点（灰度值为255）。试问此类图像如何处理,并将处理后的图像画出来。梯度算子：基于一阶微分的图像增强lec_6_image：P22梯度是一个矢量，其大小和方向为:gradSy)= =7(#=aircmn J)=arctsan(梯度值正比于像素之差。对于一幅图像中突出的边缘区，其梯度值较人；在平滑区域梯度值小；对于灰度级为常数的区域，梯度为零。作业5:作业题利用Rob^t和中值做了一道题目，具体的记不清了Roberts、SobeRPrewitt基于二阶微分的图像增强：Laplacian：P（49）作业6：作业题：李登辉上次帮老师做的：就是边缘检测，用一个算子，如果是行比较有明显变化的话用算子针对x的，如果是列有明显变化的话，用算子针对y的。即如果每行上的数都差不多，突然一行数值特人，则表明在列上变化较人，用y算子。如-1-2-1：000；121图像分割：非连续性分割（边缘检测和边缘跟踪）相似性分割（阈值分割和区域分裂与合并）图像压缩：1948年香农：信息爛。信息论之父是香农。第一次用数学语言阐明了概率与信息冗余度的关系。IM=log2丽=-log2P（aO-N N力=■力P（s）吨2戸（兔）1=1 1=1信息墻是信息论中用于度量信息量的一个概念，一个系统越有序，信息爛越低，反之，则反。作业7：作业题lec_8_Coding_l:P57答案P58(1)求爛P19(2)画Huffinan树(P42)图像压缩是用算法使图像尽量接近信息爛的极限1948年Shannon编码；1952年Fano编码Huaffinan编码摩尔斯码，出现字母频率，频率越高，则编码越短算法：蛮力法：也即是检查搜索空间中的每一个解直至找到问题的解。选择排序、冒泡排序、插入排序、顺序查找、朴素的字符串匹配等，都是蛮力策略的具体应用。复杂问题常常有很多的可能解，这些可能解构成了问题的解空间。对于人部分问题来说，其解空间的规模为输入规模的指数函数甚至更高。回溯法-＞约束条件(即包含最优解卜〉剪枝：用约束条件剪去得不到可行解的子树：用评估函数剪去得不到最优解的子树。图着色问题：回溯法求解图着色问题，首先把所有顶点的颜色初始化为0,然后依次为每个顶点着色。在图着色问题的解空间树中，如果从根结点到当前结点对应一个部分解，也就是所有的颜色指派都没有冲突，则在当前结点处选择第一棵子树继续搜索，也就是为卜•一个顶点着颜色1,否则，对当前子树的兄弟子树继续搜索，也就是为当前顶点着下一个颜色，如果所有m种颜色都已尝试过并且都发生冲突，则回溯到当前结点的父结点处,上一个顶点的颜色被改变,依此类推。A=1(a)一个无向图2B=2(b)冋溯法搜索空间(a)一个无向图2B=2(b)冋溯法搜索空间图8.8回溯法求解图着色问题示例分支限界法就是这样的一种启发式方法TOC\o"1-5"\h\z分支限界法首先确定一个合理的限界函数，并根据限界函数确定评估函数的界［down,up］。「 芬爰両狂乔僉丽 ［•根据限界函数确定目标函数的界［down,up|； !!2•将待处理结点表PT初始化为空； i!3.对根结点的每个孩子结点x执行下列操作 '；3.1估算结点x的目标函数值value; !!3.2若(value>=down),则将结点x加入表PT中； i(4•循环直到某个叶子结点的H标函数值在表PT屮最大 ；；4.1：=表卩丁中值最大的结点； !!4.2对结点i的每个孩子结点x执行下列操作 i! 4.2.1估算结点x的目标函数值value; )i 4.2.2X(valuc>=down),则将结点x加入表PT中； !! 4.2.3若(结点％是叶子结点且结点x的讪ue值在表PT中最大)， i! 则将结点x对应的解输出，算法结束； *； 4.2.4若(结点x是叶了结点但结点*的value值在表PT中不是最大)，!则令dovvn=valuc,并目•将表PT屮所有小于value的结点删條；i多段图的最短路径问题(没太看懂)分治法的设计思想将一个难以直接解决的大问题，划分成一些规模较小的子问题，以便各个击破，分而治之。更一般地说，将要求解的原问题划分成k个较小规模的子问题，对这k个子问题分别求解。如果子问题的规模仍然不够小，则再将每个子问题划分为k个规模更小的子问题，如此分解卞去，直到问题规模足够小，很容易求出其解为止，再将子问题的解合并为一个更人规模的问题的解，自底向上逐步求出原问题的解。思考•假设你正在管理一条公路的广告牌建设，这条路从西到东M英里。广告牌可能的地点假设为X1,X2,X3…Xru处于［0,M］中。若在Xi放一块广告牌，可以得到门＞0的收益。•国家公路局规定，两块广告牌相对不能小于或等于5英里之内。・如何找