图像处理与识别-11近邻法

1Email：[e-mail]:Student.feng2010.12图像处理与识别DigitalImageProcessing&Recognition主讲人：封筠石家庄铁道大学信息学院210.1引言10.2模式相似性测度的基本概念10.3最近邻法10.4K-近邻法第10章近邻法（Nearest-NeighborMethod）310.1引言自动分类的基本方法将特征空间划分成决策域：确定判别函数或确定分界面方程。模板匹配：将待分类样本与标准模板进行比较，看跟哪个模板匹配度更好些，从而确定待测试样本的分类。410.1引言自动分类的基本方法近邻法则在原理上属于模板匹配。它将训练样本集中的每个样本都作为模板，用测试样本与每个模板做比较，看与哪个模板最相似(即为近邻),就按最近似的模板的类别作为自己的类别。510.1引言自动分类的基本方法最小距离分类器将各类训练样本划分成若干子类，并在每个子类中确定代表点，一般用子类的质心或邻近质心的某一样本为代表点。测试样本的类别则以其与这些代表点距离最近作决策。该法的缺点是所选择的代表点并不一定能很好地代表各类，其后果将使错误率增加。610.1引言自动分类的基本方法增加代表点的数量有没有可能获得性能好的分类器呢?一种极端的情况是以全部训练样本作为“代表点”，计算测试样本与这些“代表点”，即所有样本的距离，并以最近邻者的类别作为决策。这种方法就是近邻法的基本思想。最初的近邻法是由Cover和Hart于1968年提出的，随后得到理论上深入的分析与研究，是非参数法中最重要的方法之一。710.2模式相似性测度的基本概念样本与样本间的距离这两个样本可能在同一个类中，如图（a），也可能在不同的类中，如图（b）。因此，可以计算同一个类内样本与样本之间的距离，也可以计算属于不同类样本与样本之间的距离。810.2模式相似性测度的基本概念样本与样本间的距离计算距离方法样品间距离计算公式说明欧式距离nkjkikjijiTjiijxxXXXXXXD1222Dij越小，则两个样品距离越近，就越相似马氏距离NiiTiNiijiTjiijXNXXXXXNSXXSXXD11121)(11Dij越小，则两个样品距离越近，就越相似夹角余弦距离jijTijiXXXXXXScos),(S值越大，则相似度越大特征是二值时的夹角余弦))((cos),(jTjiTijTijiXXXXXXXXS要求Xi，Xj向量的各个特征都是以二值表示，S越大越相似具有二值特征的Tanimoto测度jTijTjiTijTijiXXXXXXXXXXS),(要求Xi，Xj向量的各个特征都是以二值表示，S越大越相似910.2模式相似性测度的基本概念样本与类之间的距离样本与类之间距离的计算方法有两种。①计算该样本到ω类内各个样本之间的距离，将这些距离求和，取平均值作为样本与类之间的距离。样本与类之间的距离可描述为211)()(1221),(1),(NinkikkiNixxNXXDNXD1010.2模式相似性测度的基本概念样本与类之间的距离②计算ω类的中心点M（ω），以ω中的所有样本特征的平均值作为类中心，然后计算待测样本X到ω的中心点M(ω)的距离。1110.2模式相似性测度的基本概念类内距离1210.2模式相似性测度的基本概念类内距离类内距离是指同一个类内任意样品之间距离之和的平均值。如图所示，类内点集{Xi,i=1,2,…,N}各点之间的内部距离平方为}){},({2jiXXD，（i,j=1,2,…,N,i≠j）,从集内一固定点Xi到所有其它的N-1个点Xj之间的距离平方是NijjnkjkikjixxNXXD1122)(11}){,(。同样道理，取ω内所有N个点的平均距离以表示其类内距离：NiNijinkjkikNiNjnkjkikjixxNNxxNNXXD111211122)()1(1)(111}){},({1310.2模式相似性测度的基本概念类与类之间的距离14距离方法距离定义说明最短距离法规定两个类间相距最近的两个点之间的距离，为两类的距离Di,j=min(dij)Dij=||Xi-Xj||,Xi∈ωi,Xj∈ωj最长距离法规定两个类间相距最远的两个点之间的距离，为两类的距离Di,j=max(dij)Dij=||Xi-Xj||,Xi∈ωi,Xj∈ωj重心法求各类中所有样品的平均值作为类的重心，两类的重心间的距离为两类的距离)()(,jiwwjiXXDiiwxiwXNX1)(jjwxjwXNX1)(Ni,Nj分别是ωi,ωj类中样品的个数平均距离法计算两类间所有样品的距离，求和，取距离的平均值作为两类间的距离jjiiwxwxjijijiXXNND1,10.2模式相似性测度的基本概念类与类之间的距离1510.3最近邻法决策规则将与测试样本最近邻样本的类别作为决策的方法称为最近邻法。对一个C类别问题，每类有Ni个样本，i＝1，…，C式中用‖·‖表示距离，可以采用某种相似性的度量，如欧氏距离。ωi类判别函数iikikikiNkxxxxg,...,1,,min)(决策规则：if)(min)(,...,1xgxgicijthenX∈ωj1610.3最近邻法错误率分析(渐进分析)结论：PccPPP121其中：P·为贝叶斯错误率P1为样本无穷多时最近邻法的错误率（渐近平均错误率）前提：样本集独立同分布1710.4K-近邻法(KNN)决策规则k近邻一般采用k为奇数，跟投票表决一样，避免因两种票数相等而难以决策。最近邻法（一近邻法）的推广：找出x的k个近邻，看其中多属于哪一类，则把x分到哪一类。一般表示：c类ωi，i=1,…,c,N个样本。ki，i=1,…,c为x的k个近邻中属于ωi的样本数判别函数：cikxgii,...,1,)(决策规则：ificijkxg,...,1max)(thenX∈ωj1810.4K-近邻法(KNN)渐进平均错误率的界N无穷大时，k越大，Pk的上限越低（越靠近下限）。但k应始终是N中的一小部分，保证k个近邻均充分接近x。否则这一关系不成立。一般来说，总有PccPPPk12或者简化为PPPk21910.4K-近邻法(KNN)问题：1.存储量和计算量2.票数接近时风险较大，有噪声时风险加大3.有限样本下性能如何？改进：1.减少计算量和存储量2.引入拒绝机制3.根据实际问题修正投票方式，如加权投票，否决票等；如距离加权，考虑样本比例及先验概率等问题与改进20实验三：图像恢复与压缩实验目的（1）理解图像恢复的含义，熟悉无约束恢复与有约束恢复的基本思路，掌握逆滤波与维纳滤波方法；（2）理解无损压缩编码与有损压缩编码的含义，掌握图像熵概念，熟悉常用的编码客观质量评价准则；（3）理解变换编码的基本思想，熟悉掌握基于FFT变换的图像压缩技术与基于DCT变换的图像压缩技术；（4）进一步熟悉Matlab语言及图像处理工具箱IPT。实验类型：设计性21实验三：图像恢复与压缩实验内容（1）模糊加噪图像仿真生成a.运动模糊加噪b.圆盘状模糊加噪c.钝化模糊加噪（2）无约束恢复——逆滤波（3）有约束恢复——维纳滤波22实验三：图像恢复与压缩实验内容（4）图像信号基本指标的计算a.均方根误差b.基本信噪比c.压缩比d.图像的熵（5）变换编码a.基于FFT变换的图像压缩技术b.基于DCT变换的图像压缩技术23实验三：图像恢复与压缩实验步骤模糊加噪图像仿真生成对milkdrop.bmp图像仿真生成三个具有不同数量级方差水平的运动模糊加噪图像，另外生成二个不同模糊类型（如圆盘状模糊、钝化模糊）的加噪图像，噪声类型可选为椒盐、高斯等。所生成的模糊加噪图像将作为恢复处理的对象。24实验三：图像恢复与压缩I=imread('milkdrop.bmp');subplot(2,3,1);imshow(I);H=fspecial(‘motion’,50,45);%运动模糊PSFMotionBlur=imfilter(I,H);H=fspecial(‘disk’,10);%圆盘状模糊PSFBlurred=imfilter(I,H);H=fspecial(‘unsharp’);%钝化模糊PSFSharpened=imfilter(I,H);noise1=imnoise(zeros(size(I)),'gaussian',0,0.009);MotionBlur_Noise1=uint8(double(MotionBlur)+noise1);subplot(2,3,4);imshow(MotionBlur_Noise1);imwrite(MotionBlur_Noise1,'Milkdrop_MotionBlurNoise1.bmp');Blurred_Noise=uint8(double(Blurred)+noise1);subplot(2,3,2);imshow(Blurred_Noise);imwrite(Blurred_Noise,'Milkdrop_BlurredNoise.bmp');Sharpened_Noise=uint8(double(Sharpened)+noise1);subplot(2,3,3);imshow(Sharpened_Noise);imwrite(Sharpened_Noise,'Milkdrop_SharpenedNoise.bmp');noise2=imnoise(zeros(size(I)),'gaussian',0,0.09);noise3=imnoise(zeros(size(I)),'gaussian',0,0.9);MotionBlur_Noise2=uint8(double(MotionBlur)+noise2);subplot(2,3,5);imshow(MotionBlur_Noise2);imwrite(MotionBlur_Noise2,'Milkdrop_MotionBlurNoise2.bmp');MotionBlur_Noise3=uint8(double(MotionBlur)+noise3);subplot(2,3,6);imshow(MotionBlur_Noise3);imwrite(MotionBlur_Noise3,'Milkdrop_MotionBlurNoise3.bmp');25实验三：图像恢复与压缩实验步骤逆滤波与维纳滤波（1）由原始人工图像checkerboard生成相应的运动模糊加噪退化图像，加入的是高斯噪声。分别利用逆滤波与维纳滤波进行恢复，比较其恢复效果。逆滤波：fr=deconvwnr(g,PSF)维纳滤波：fr=deconvwnr(g,PSF,NSR)其中g是退化图像，PSF是退化模型的点扩散函数，NSR是噪信比，fr是恢复图像。26实验三：图像恢复与压缩%建立原始图像F=checkerboard(24);figure(1);imshow(F);Len=20;%设置运动位移为20个像素Theta=45;%设置运动角度为45度%建立二维仿真线性滤波器PSFPSF=fspecial('motion',Len,Theta);%用PSF产生退化图像，选项circular用来减少边界效应MF=imfilter(F,PSF,'circular');noise=imnoise(zeros(size(F)),'gaussian',0,0.001);%生成运动模糊+高斯噪声图像MFNMFN=MF+noise;figure(2);imshow(MFN);%计算噪信比NSR=sum(noise(:).^2)/sum(