2014-07-25 16:21:11 EbowTang 阅读数 8784
  • 以性别预测为例,谈谈数据挖掘中常见的分类算法

    互联网的迅猛发展,催生了海量数据的产生。如何挖掘数据的深层价值变得尤为重要。然而,数据挖掘复杂的数学内容使很多人望而却步。本议题试图以实例的形式,用尽量通俗的方式,针对性别预测这个分类问题,来谈一下数据挖掘基本的处理流程,常见的算法和算法的选择等。 讲师:王琪,友盟数据挖掘工程师,武汉大学硕士,工作涉及友盟的各类数据挖掘和分析任务。对数据挖掘和分析,自然语言处理和文本检索有多年的理论和实践经验。

    21926 人正在学习 去看看 CSDN讲师

一,背景

 

随着各种数字仪器和数码产品的普及,图像和视频已成为人类活动中最常用的信息载体,它们包含着物体的大量信息,成为人们获取外界原始信息的主要途径。然而在图像的获取、传输和存贮过程中常常会受到各种噪声的干扰和影响而使图像降质,并且图像预处理算法的好坏又直接关系到后续图像处理的效果,如图像分割、目标识别、边缘提取等,所以为了获取高质量数字图像,很有必要对图像进行降噪处理,尽可能的保持原始信息完整性(即主要特征)的同时,又能够去除信号中无用的信息。所以,降噪处理一直是图像处理和计算机视觉研究的热点。

图像视频去噪的最终目的是改善给定的图像,解决实际图像由于噪声干扰而导致图像质量下降的问题。通过去噪技术可以有效地提高图像质量,增大信噪比,更好的体现原来图像所携带的信息,作为一种重要的预处理手段,人们对图像去噪算法进行了广泛的研究。在现有的去噪算法中,有的去噪算法在低维信号图像处理中取得较好的效果,却不适用于高维信号图像处理;或者去噪效果较好,却丢失部分图像边缘信息,或者致力于研究检测图像边缘信息,保留图像细节。如何在抵制噪音和保留细节上找到一个较好的平衡点,成为近年来研究的重点。

 

二,图像去噪理论基础

 

2.1 图像噪声概念

噪声可以理解为“妨碍人们感觉器官对所接收的信源信息理解的因素”。例如,一幅黑白图片,其平面亮度分布假定为f(x,y),那么对其接收起干扰作用的亮度分布R(x,y),即可称为图像噪声。但是,噪声在理论上可以定义为“不可预测,只能用概率统计方法来认识的随机误差”。因此将图像噪声看成是多维随机过程是合适的,因而描述噪声的方法完全可以借用随机过程的描述,即用其概率分布函数和概率密度分布函数。但在很多情况下,这样的描述方法是很复杂的,甚至是不可能的。而实际应用往往也不必要。通常是用其数字特征,即均值方差,相关函数等。因为这些数字特征都可以从某些方面反映出噪声的特征。

 

2.2 常见的图像噪声

在我们的图像中常见的噪声主要有以下几种:

(1),加性噪声

加性嗓声和图像信号强度是不相关的,如图像在传输过程中引进的“信道噪声”电视摄像机扫描图像的噪声的。这类带有噪声的图像g可看成为理想无噪声图像f与噪声n之和,即:

image

(2),乘性噪声

乘性嗓声和图像信号是相关的,往往随图像信号的变化而变化,如飞点扫描图像中的嗓声、电视扫描光栅、胶片颗粒造成等,这类噪声和图像的关系是:

image

(3),量化噪声

量化嗓声是数字图像的主要噪声源,其大小显示出数字图像和原始图像的差异,减少这种嗓声的最好办法就是采用按灰度级概率密度函数选择化级的最优化措施。

(4),“椒盐”噪声

此类嗓声如图像切割引起的即黑图像上的白点,白图像上的黑点噪声,在变换域引入的误差,使图像反变换后造成的变换噪声等。

 

2.3 图像噪声模型

实际获得的图像含有的噪声,根据不同分类可将噪声进行不同的分类。从噪声的概率分情况来看,可分为高斯噪声、瑞利噪声、伽马噪声、指数噪声和均匀噪声。它们对应的概率密度函数(PDF)如下

(1),高斯噪声

在空间域和频域中,由于高斯噪声在数学上的易处理性,这种噪声(也称为正态噪声)模型经常被用在实践中。高斯随机变量Z的PDF由下式给出:

image

其中,z表示灰度值,μ表示z的平均值或期望值,α表示z的标准差。当z服从上述分布时,其值有95%落在[(μ-2σ), (μ+2σ)]范围内。

(2)脉冲噪声(椒盐噪声)

(双极)脉冲噪声的PDF可由下式给出:

image

如果b>a,则灰度值b在图像中将显示为一个亮点,反之则a的值将显示为一个暗点。若Pa或Pb为零,则脉冲称为单极脉冲。如果Pa和Pb均不可能为零,尤其是它们近似相等时,则脉冲噪声值将类似于随机分布在图像上的胡椒和盐粉微粒。由于这个原因,双极脉冲噪声也称为椒盐噪声。

(3)瑞利噪声

image

其均值和方差分别为:

image

(4)伽马噪声

image

其密度的均值和方差为:

image

(5)指数分布噪声

image

其中a>0,概率密度函数的期望值和方差是:

image

(6)均匀噪声

image

其均值和方差分别为:

image

 

2.4 图像去噪算法分类

(1),空间域滤波

空域滤波是在原图像上直接进行数据运算,对像素的灰度值进行处理。常见的空间域图像去噪算法有邻域平均法、中值滤波、低通滤波等。

(2),变换域滤波

图像变换域去噪方法是对图像进行某种变换,将图像从空间域转换到变换域,再对变换域中的变换系数进行处理,再进行反变换将图像从变换域转换到空间域来达到去除图像嗓声的目的。将图像从空间域转换到变换域的变换方法很多,如傅立叶变换、沃尔什-哈达玛变换、余弦变换、K-L变换以及小波变换等。而傅立叶变换和小波变换则是常见的用于图像去噪的变换方法。

(3),偏微分方程

偏微分方程是近年来兴起的一种图像处理方法,主要针对低层图像处理并取得了很好的效果。偏微分方程具有各向异性的特点,应用在图像去噪中,可以在去除噪声的同时,很好的保持边缘。偏微分方程的应用主要可以分为两类:一种是基本的迭代格式,通过随时间变化的更新,使得图像向所要得到的效果逐渐逼近,这种算法的代表为Perona和Malik的方程[27],以及对其改进后的后续工作。该方法在确定扩散系数时有很大的选择空间,在前向扩散的同时具有后向扩散的功能,所以,具有平滑图像和将边缘尖锐化的能力。偏微分方程在低噪声密度的图像处理中取得了较好的效果,但是在处理高噪声密度图像时去噪效果不好,而且处理时间明显高出许多。

(4),变分法

另一种利用数学进行图像去噪方法是基于变分法的思想,确定图像的能量函数,通过对能量函数的最小化工作,使得图像达到平滑状态,现在得到广泛应用的全变分TV模型就是这一类。这类方法的关键是找到合适的能量方程,保证演化的稳定性,获得理想的结果。

(5),形态学噪声滤除器

将开与闭结合可用来滤除噪声,首先对有噪声图像进行开运算,可选择结构要素矩阵比噪声尺寸大,因而开运算的结果是将背景噪声去除;再对前一步得到的图像进行闭运算,将图像上的噪声去掉。据此可知,此方法适用的图像类型是图像中的对象尺寸都比较大,且没有微小细节,对这类图像除噪效果会较好。

 

三,几种图像去噪算法介绍

 

3.1 基于空间域的中值滤波

中值滤波器是一种常用的非线性平滑滤波器,基本原理是把数字图像或数字序列中一点的值用该点邻域内各点的中值代换。设f(x,y)表示数字图像像素点(x,y)的灰度值,滤波窗口为A的中值滤波器可以定义为:

image

当n为奇数时,n个数x1,x2,…xn的中值就是按数值大小顺序处于中间的数;当n为偶数时,我们定义两个中间数平均值为中值。

 

3.2 基于小波域的小波阈值去噪

小波萎缩法是目前研究最为广泛的方法,小波萎缩法又分成如下两类:第1类是阈值萎缩,由于阈值萎缩主要基于如下事实,即比较大的小波系数一般都是以实际信号为主,而比较小的系数则很大程度是噪声。因此可通过设定合适的阈值,首先将小于闽值的系数置零,而保留大于闭值的小波系数;然后经过阈值函数映射得到估计系数;最后对估计系数进行逆变换,就可以实现去噪和重建;而另外一种萎缩方法则不同,它是通过判断系数被噪声污染的程度,并为这种程度引入各种度量方法(例如概率和隶属度等),进而确定萎缩的比例,所以这种萎缩方法又被称为比例萎缩。阈值萎缩方法中的两个基本要素是阈值和阈值函数。

阈值的选择:

阈值的确定在阈值萎缩中是最关键的。目前使用的阈值可以分成全局阈值和局部适应阈值两类。其中,全局阈值对各层所有的小波系数或同一层内的小波系数都是统一的;而局部适应阈值是根据当前系数周围的局部情况来确定阈值。目前提出的全局阈值主要有以下几种:

(1),Donoho和Johastone统一阈值(简称DJ阈值):

其中σ为噪声标准方差,N为信号的尺寸或长度。

image

(2),基于零均值正态分布的置信区间阈值:

image

(3),Bayes Shrink阈值和Map Shrink阈值。在小波系数服从广义高斯分布的假设下,Chang等人得出了阈值:

image

其中,(R为噪声标准方差,RB为广义高斯分布的标准方差值)。

(4),最小最大化值:这是Donoho和John Stone在最小最大化意义下得出的阈值与上边的阈值不同,它是依赖于信号的,而且没有显式表达式,在求取时需要预先知道原信号。

(5),理想值:理想阈值是在均方差准则下的最优阈值,同最大最小化阈值一样,也没有显式的表达式,并且这个阈值的计算通常也需先知道信号本身。

阈值函数:

Bruce和Gao。提出了一种半软阈值函数:

image

该方法通过选择合适的阈值T1和12,可以在软阈值方法和硬阈值方法之间达到很好的折中。另外,zhang等人为了对SIJRE误差准则函数进行基于梯度的优化搜索,提出了另外一种阈值函数,这种阈值函数同上边闭值函数所不同的是它拥有更高的导数阶,故其重建图像更为平滑,但该文作者将去噪效果的提高归功于搜索方法,其实,Donoh。和 Johnstone提出的在当前小波系数集合中,搜索最优阈值的方法,对于当前已经是优的了,由此可见,该去噪效果的提高则应归功于阈值函数的选取。

 

3.3 基于PDE的图像去噪

目前,基于PDE的图像处理方法的研究,也是图像去噪的研究热点方向,并且己经取得了一定的理论和实际应用方面的成它的去噪过程为通过建立噪声图像为某非线性PDE的初始条件,然后求解这个PDE,得到在不同时刻的解,即为滤波结果。Perona和Malik提出了基于PDE的非线性扩散滤波方法(以下简称P-M),各向异性的去噪模型根据图像的梯度值决定扩散的速度,使之能兼顾噪声消除和边缘保持两方面的要求。

以P-M模型为代表的这类方法己经在图像增强、图像分割和边缘检测等领域得到了广泛的应用,取得了很好的效果。

P-M是一种非线性的各向异性方法,目的是为了克服线性滤波方法存在的模糊边缘和边缘位置移动的缺点。基本思想是:图像特征强的地方减少扩散系数,图像特征弱的地方增强扩散系数。方程如下:

image

其中u(x,y,t)是随时间变化的图像,image是梯度的模,image扩散系数函数用于控制扩散速度。理想的扩散系数应当使各向异性扩散在灰度变化平缓的区域快速进行,而在灰度变化急剧的位置(即图像特征处)低速扩散乃至不扩散函数,所以,image应具有如下性质:

image

基于以上的两个性质,P-M提出了如下扩散系数函数:

image

其中k为边缘阈值,用来判断边缘区域和平坦区域。引入通量函数,主要是为了阐明阈值k在扩散操作中的作用,其函数定义如下:

image

尽管P-M方程在抑制噪声与保留图像重要特征方面取得了一定的效果,但却表现出病态且不稳定。Catt等人对该方程进行了改进,他们先用高斯核同图像作卷积,然后取其梯度模作图像边缘信息的估计。文献提出用优化的对称指数滤波器对图像作光滑,然后取其梯度模作图像边缘信息的估计。这两种估计方法的基本思想是降低噪声的干扰,更加真实地提取图像的边缘特征信息,以便利用边缘信息更好地控制P-M方程的扩散行为。

 

3.4 全变分(TV)图像去噪

TV方法是由Rudin Osher and Fatemi提出,它基于变分法的思想,确定图像的能量函数,通过对图像能量函数最小化达到平滑去噪的目的。是现在比较流行的图像复原方法。图像的能量函数方程为:

image

在文献[2]中给出的全变分去噪能量泛函为:

image

为了使得能量函数最小,其欧拉-拉格朗日方程为:

image

其中,梯度算子:

image

正则项:

image

用来减少平坦区域的退化。将整体左边转换成图像中任意像素点中的局部坐标系后,方程可以分解成边缘方向和边缘正交的两个方向,分解后个方向的系数控制着该方向的扩散强度。扩散方向实际上是一个分线性的各向异性的扩散方程,其扩散算子仅沿图像梯度的正交方向扩散,扩散系数为1/|▽μ|,而朝着梯度方向无扩散。这样可以通过图像的梯度来判断边缘位置,使得边缘扩散系数最小,从而降低对边缘的模糊程度,但是也由于边缘的扩散系数小,噪声得不到很好的抑制,而且当|▽μ|>λ的时候,势能函数是非凸的,使得边缘处处理表现不稳定。所以,如何确定扩散参数的值是一个问题。


四,评价图像质量的客观参数

客观评价算法根据其对参考图像的依赖程度, 可分成三类。

(1)全参考:需要和参考图像上的像素点做一一对应的比较;

(2)半参考:只需要和参考图像上的部分统计特征做比较;

(3)无参考:不需要具体的参考图像。其中全参考算法是研究时间最长、发展最成熟的部分

a,PNSR峰值信噪比


b,ENL等效视数


c,SNR信噪比


引用别人的一片博客:

Lin Zhang等人在论文《A COMPREHENSIVEEVALUATION OF FULL REFERENCE IMAGE QUALITY ASSESSMENT ALGORITHMS》中,比较了几种全参考图像质量评价算法,在此记录一下他们的结果。

下表所示是他们所用的图像库,包含了:TID2008databaseCSIQ databaseLIVEdatabaseIVCdatabaseToyama-MICTdatabaseCornell A57 database,以及 WirelessImaging Quality database (WIQ)。从上到下数据库的规模依次下降。


一共比较了如下所列的全参考图像客观质量评价算法:

PeakSignal to Noise Ratio(PSNR)

峰值信噪比。

noise quality measure (NQM) index

参考文献:N. Damera-Venkata, T.D. Kite, W.S. Geisler, B.L. Evans, and A.C.Bovik, “Image quality assessment based on a degradation model,” IEEE Trans. IP,vol. 9, pp. 636-650, 2000.

universal quality index (UQI)

参考文献:Z. Wang and A.C. Bovik, “A universal image quality index,” IEEE SignalProcess. Lett., vol. 9, pp. 81-84, 2002.

structural similarity (SSIM) index

参考文献:Z. Wang, A.C. Bovik, H.R. Sheikh, and E.P. Simoncelli,”Image qualityassessment: from error visibility to structural similarity,” IEEE Trans. IP,vol. 13, pp. 600-612, 2004.

multi-scaleSSIM (MS-SSIM) index

参考文献:Z. Wang, E.P. Simoncelli, and A.C. Bovik, “Multi-scale structuralsimilarity for image quality assessment,” ACSSC’03, pp. 1398-1402, 2003.

information fidelity criterion (IFC) index

参考文献:H.R. Sheikh, A.C. Bovik, and G. de Veciana, “An information fidelitycriterion for image quality assessment using natural scene statistics,” IEEETrans. IP, vol. 14, pp. 2117-2128, 2005.

visual information fidelity (VIF) index

参考文献:H.R. Sheikh and A.C. Bovik, “Image information and visual quality,”IEEE Trans. IP, vol. 15, pp. 430-444, 2006.

visual signal to noise ratio (VSNR) index

参考文献:D.M. Chandler and S.S. Hemami, “VSNR: a wavelet-based visualsignal-to-noise ratio for natural images,” IEEE Trans. IP, vol. 16, pp.2284-2298, 2007.

information content weighted SSIM (IW-SSIM) index

参考文献:Z. Wang and Q. Li, “Information content weighting for perceptualimage quality assessment,” IEEE Trans. IP, vol. 20,

pp. 1185-1198, 2011.

Riesz transforms based feature similarity (RFSIM) index

参考文献:L. Zhang, L. Zhang, and X. Mou, “RFSIM: a feature based imagequality assessment metric using Riesz transforms,” ICIP’10, pp. 321-324, 2010.

feature similarity (FSIM) index

参考文献:L. Zhang, L. Zhang, X. Mou, and D. Zhang, “FSIM: a feature similarityindex for image quality assessment,” IEEE Trans. IP, vol. 20, pp. 2378-2386,2011.

 

统计了每种全参考图像质量评价算法的客观值和主观值之间的相关系数:

斯皮尔曼秩相关系数(Spearman rankorder correlation coefficient,SROCC),肯德尔秩次相关系数(Kendallrank-order correlation coefficient,KROCC),皮尔森线性相关系数(Pearsonlinear correlation coefficient,PLCC)。客观算法的结果和主观评价的结果相关性越高,则以上三个系数的值越接近于1,说明算法越准确。由表可见,FSIM算法的准确度相对来说是最高的,三个系数的取值分分别达到了0.9094,0.7409,0.9050。


下表将上表的数值进行了一下排名。排在前面的有FSIM,IW-SSIM,RFSIM,MS-SSIM。猛然发现:PSNR真的是好不准啊~~

下表反映了每种全参考质量评价算法的耗时,耗时越短,说明算法速度越快。


总体说来FSIM,IW-SSIM,RFSIM这三种比较新的图像质量评价算法准确性比较高




五,总结

随着科技的发展和工作生活的需要,数字图像滤波应用将越来越广泛,要求也将越来越高。到目前为止,仍有很多去噪方面的新思想、新方法出现,不断的充实图像去噪方法。而且,噪声的研究范围也在不断扩大,由高斯噪声到非高斯噪声。去噪技术有很广泛的应用和研究的前景,而且,研究领域也在不断的拓展。

本文主要的内容是对图像的去噪技术做一个简单的介绍。全文对图像去噪技术进行了概述,包括噪声的概念和去噪原理,并对一些基本的图像去噪方法做了介绍。由于时间关系,并且这是导论课程的论文作业,就没有进行深入细致的研究。

 

参考文献

[1] GonzalesRC,WoodsRE.DigitalImageProeessing,SeeondEdition Beijing Eleetronieand Industrial Press,2002

[2] Leonid I. Rudin 1, Stanley Osher and Emad Fatemi Nonlinear total variation based noise removal algorithms 1992

[3] W.Luo,An efficient detail preserving approach for removing impulse noise in images,IEEE Signal Proeess.Lett.,2006,13(7):413-416.

[4] http://blog.csdn.net/coloriy/article/details/46532171

2017-07-20 21:56:43 shinian1987 阅读数 2813
  • 以性别预测为例,谈谈数据挖掘中常见的分类算法

    互联网的迅猛发展,催生了海量数据的产生。如何挖掘数据的深层价值变得尤为重要。然而,数据挖掘复杂的数学内容使很多人望而却步。本议题试图以实例的形式,用尽量通俗的方式,针对性别预测这个分类问题,来谈一下数据挖掘基本的处理流程,常见的算法和算法的选择等。 讲师:王琪,友盟数据挖掘工程师,武汉大学硕士,工作涉及友盟的各类数据挖掘和分析任务。对数据挖掘和分析,自然语言处理和文本检索有多年的理论和实践经验。

    21926 人正在学习 去看看 CSDN讲师

从最开始接触图像处理,到现在,也有很多年了,现在回过来看以前学的很多东西,会开始慢慢尝试理解现象背后的本质,以前只是单纯地从技术的角度去学习图像处理的很多算法,随着知识的积累,会感到很多算法的背后其实都有着看似简单却又深刻的数学与物理原理。今天简单介绍图像中常用的一个统计–直方图。

直方图统计是图像处理中非常基本的一种统计,简单来说,就是给定一张图像 I[0,255],我们要统计这张图像里,像素值为 0 的像素有多少个,像素值为 1 的有多少个,以此类推,直到像素值为 255,我们可以假设图像总的像素个数为 N,像素值为 i 的像素个数为 ni, 那么我们有:

N=i=0255ni

我们以前学概率的时候,都知道一个经典的抛硬币的思想实验,抛硬币是二分类 {0, 1} 的情形,还有一个经典的抛骰子的实验,这是多分类的情形 {1, …, 6},我们可以把这个思想实验再进一步的拓展,考虑更多分类的情形,比如 {0, 1, 2, …, 255},这样的话,就是 256 种情况。每一个像素值,都相当于一个类别,一张图像总的像素数就是一个样本总体,我们想知道每一个像素值所占的比重,或者说概率,就用这个像素值的像素个数除以总的像素数,即:

pi=niN

所以说,直方图,反映的其实是像素值的一种概率密度分布。

我们以前学过,给定概率密度函数 p(x),想求某一个区间的概率,可以用如下的积分表达式:

p(x(a,b))=bap(x)dx

对于离散概率分布,我们可以直接用求和的表达式:

p(x(a,b))=abp(x)

所以说,要求直方图某一段像素值区间的累积概率,可以表示为:

p(i(a,b))=i=abpi

而这个就是我们常说的累积直方图,一般我们都是从 0 开始, 比如说,我们要求像素值 0 到 k 之间的累积直方图,可以表示为:

ck=i=0kpi

现在我们有了直方图,有了累积直方图,接下来,我们来看看直方图均衡,直方图均衡是图像动态范围拉伸的一种方法,我们知道,要将一个区间 [a, b] 映射到另外一个区间 [c, d], 最简单的方法是线性映射:

y=xaba×(dc)+c,x[a,b],y[c,d]

目前最常用的图像编码都是 8 bits,所以图像的动态范围都是 [0, 255],一个图像的对比度要好,动态范围要尽可能地大,同时直方图的分布不能太窄,如果都挤在一起,图像的对比度肯定不好。直方图均衡是图像处理中,非常经典的一个拉伸动态范围调整图像对比度的算法。就是利用累积直方图的性质,我们知道累积直方图的区间为 [0, 1],并且是单调递增的,我们假设图像原来的灰度值为 i,其对应的累积直方图为 ci0ci1, 那么我们可以求出其映射到新的灰度值为:

y=ci010×(2550)+0=ci255

其实,就是将累积直方图的区间 [0, 1] 映射到新的区间 [0, 255],利用累积直方图单调递增的特性,保证了映射前后灰度值的大小关系没有发生改变,就是说映射前 i<j,那么映射后的灰度值同样满足 yi<yj, 我们来看一小段程序:

import numpy as np
import matplotlib.pyplot as plt
from skimage import data

img = data.moon()

rows, cols = img.shape
N = rows * cols - 1

Hist_ori = np.zeros((256, 1))
Hist_cmu = np.zeros((256, 1))

for ii in range(256):
    mask_1 = (img == ii)
    Hist_ori[ii] = np.sum(mask_1) * 1.0 / N
    if ii == 0:
        Hist_cmu[ii] = Hist_ori[ii]
    else:
        Hist_cmu[ii] = Hist_cmu[ii-1] + Hist_ori[ii]

Hist_eq = np.zeros((256, 1))
img_out = img.copy()

for ii in range(rows):
    for jj in range(cols):
        img_out[ii, jj] = math.floor(Hist_cmu[img[ii, jj]] * 255.0)
        Hist_eq[img_out[ii, jj]] = Hist_eq[img_out[ii, jj]] + 1

plt.figure()
plt.axis('off')
plt.subplot(1,2,1)
plt.imshow(img, plt.cm.gray)
plt.subplot(1,2,2)
plt.imshow(img_out, plt.cm.gray)
plt.subplot(2,2,3)
plt.plot(Hist_ori)
plt.subplot(2,2,4)
plt.plot(Hist_eq*1.0/N)

plt.show()

看看效果图:

这里写图片描述

可以看到直方图被明显的拉伸开来了。

2017-12-10 22:13:31 KevinBetterQ 阅读数 3251
  • 以性别预测为例,谈谈数据挖掘中常见的分类算法

    互联网的迅猛发展,催生了海量数据的产生。如何挖掘数据的深层价值变得尤为重要。然而,数据挖掘复杂的数学内容使很多人望而却步。本议题试图以实例的形式,用尽量通俗的方式,针对性别预测这个分类问题,来谈一下数据挖掘基本的处理流程,常见的算法和算法的选择等。 讲师:王琪,友盟数据挖掘工程师,武汉大学硕士,工作涉及友盟的各类数据挖掘和分析任务。对数据挖掘和分析,自然语言处理和文本检索有多年的理论和实践经验。

    21926 人正在学习 去看看 CSDN讲师

#《数学建模算法与应用》方法概述


序言:学习司守奎《数学建模算法与应用》第2版过程中,给出一个内容的提纲,希望可以在回忆复习时快速建立知识结构。包含了数学建模所需用到的一些方法和常见问题类型。
本文仅仅建立一个学习过程中的知识框图,后续会将具体算法理解与Matlab实践整理出来。
其中前半部分“方法类”为一些常用数学建模方法,单独拿出来介绍
后半部分为总结的“问题类”,主要为规划、分类、优化、评价和预测,也总结了网络类和图像处理类问题


—————— 方法类 ——————

一、Matlab求解规划类和极值问题

数学规划为在约束条件下追求效益而做的安排。
Matlab知识负责实现数学计算,目标函数和约束条件还是需要自己去寻找关系建立方程。
多目标规划:针对多目标,加权系数法和优先等级法。

二、插值和拟合

根据一组数据构造一个函数作为近似
插值曲线要过数据点,拟合曲线整体效果更好。

三、偏最小二乘回归分析

一般研究两组变量间的相互关系

四、微分方程

需要了解研究问题领域相关规律
规律列方程——>Matlab求解微分方程

五、数理统计(需对概率论很熟悉)

利用样本来估计总体时,需要数理统计
参数估计、假设检验 ——> 方差分析、回归分析
Bootstrap扩充样本

六、时间序列

通过构造过去的时间序列并处理来研究其变化规律

  1. 移动平均法:直接平均
  2. 指数平滑法:加权平均
  3. 差分指数平滑法:增量的加权平均
  4. 季节性时间序列预测:对季节求系数

ARMA(自回归移动平均序列)构建及预报

七、支持向量机

找到一个超平面,使得其尽可能多地将两类数据点分开
线性可分SVM、线性SVM、可分SVM

—————— 问题类 ——————

一、规划类

寻找目标函数和约束条件 ——> Matlab求解

二、多元分析类(分类、聚类和相关性分析)

(主要是针对多个变量的统计分析)

  1. 聚类分析
    对样本的Q型聚类
    对指标的R型聚类
    (利用相似距离进行聚类)
  2. 主成分分析
    将多个指标转化为少数几个不相关的综合指标
    标准化 -> 相关系数矩阵 -> 特征值和特征向量 -> 组成新指标 -> 选取主成分 -> 得到贡献率
  3. 因子分析
    类似主成分分析,但通过计算初等载荷矩阵选择主因子
  4. 判别分析
    利用统计方法根据研究个体的观测指标进行归类
  5. 典型相关分析
    研究两组变量间的相关方法。
    思想:分别找出两组变量的各自的某个线性组合,讨论之间相关关系。
  6. 对应分析
    R-Q型因子分析,在同一因子平面上对变量和样本一块进行分类。
    行点和列点用同一二维关系表示,绘于同一散布图。
  7. 多维标度法
    在指标个数和本身不清晰,仅知道客体间某种距离情况下,研究客体间的结构关系。

三、优化类

求组合优化问题的全局最优解。不断迭代产生新解直到最优。

  • 模拟退火:“状态转换”
  • 遗传算法:“逐代进化”
  • 改进遗传算法

区别:产生新解方式不同

四、评价类(评价与决策)

(关键点在确定评价指标的权重上)

  1. 理想解法(TOPSIS法)
    找出虚拟正理想解和负理想解,测距找最优
  2. 模糊综合评价法
    针对考核指标难以量化,以等级制解决。可以多层次评判,权重主观。
  3. 数据包络分析
    多指标输入和多指标输出。(针对发展情况的评价较为方便)
    无需假设权重
  4. 灰度关联分析(主观)
    计算评价对象和评价标准的关联系数及关联度
  5. 主成分分析
    指标转化,利用特征值和特征向量
  6. 秩和比综合评价法
    利用秩和比进行优劣排序

五、预测类

  1. 微分方程预测模型
    基于相关原理规律的因果预测法,大多为物理和几何方面。
  2. 灰度预测
    不仅利用原始数据序列,而且对原始数据做累加或其它处理得到近似的指数规律再进行建模
  3. 差分方程
    (解得问题觉得更像高中应用题)
  4. 马尔可夫预测
    系统未来时刻的情况只与现在有关,而与过去历史无直接关系
  5. 时间序列 (根据趋势进行预测)
    通过构造过去的时间序列并处理来研究其变化规律
  6. 插值和拟合 (根据趋势进行预测)
    根据一组数据构造一个函数作为近似
    插值曲线要过数据点,拟合曲线整体效果更好。
  7. 神经元网络(根据参数预测)
    BP神经网络:反馈式地不断调整学习参数。
    BPF神经网络:把网络看成对未知函数的逼近

六、图与网络类

对于图与网络模型,无论是什么情景,方法总逃不出以下内容

1、最短路问题

  • Dijkstra算法:单源最短路
  • Floyd算法 :任意两点间的最短路

2、最小生成树

  • 加边
  • 加点

3、最大流、最小费用流

4、旅行商问题
改良圈算法

5、统筹

  • 计划网络图
  • 关键路径

七、数字图像处理

  • 图像表示
    采样 + 量化 = 数字图像的矩阵表示
    图像类型:二值、灰度、RGB彩色图像
  • 处理方法
    亮度转换、空间滤波、频域变换
  • 应用
    水印、加密式隐藏……
2016-07-29 18:11:03 Cdd2xd 阅读数 1820
  • 以性别预测为例,谈谈数据挖掘中常见的分类算法

    互联网的迅猛发展,催生了海量数据的产生。如何挖掘数据的深层价值变得尤为重要。然而,数据挖掘复杂的数学内容使很多人望而却步。本议题试图以实例的形式,用尽量通俗的方式,针对性别预测这个分类问题,来谈一下数据挖掘基本的处理流程,常见的算法和算法的选择等。 讲师:王琪,友盟数据挖掘工程师,武汉大学硕士,工作涉及友盟的各类数据挖掘和分析任务。对数据挖掘和分析,自然语言处理和文本检索有多年的理论和实践经验。

    21926 人正在学习 去看看 CSDN讲师

序言
在图像处理方面,我们从自然中汲取了大量灵感,例如射线、重力、水流等等物理学模型。其中最为常用的,似乎还是热力学模型,其抽象而简洁地描述了热传播、热均衡的过程。本文将对热力学模型展开细致讨论,不止揭露数学之美,更有自然之美。

目录

1. 热力学模型

热传递的规律

T(x,t)t=α2T(x,t)2x

热力学模型使用了上述公式对热传递过程进行描述。其中,α 表示热扩散速率,第一个简单系数,由介质材料决定; T(x,t) 函数表示空间 xt 时刻的整个温度分布,x 可以为任意维度的空间。这个简单的公式,建立了温度分布在时间和空间上的直接关系;即空间中某一点的温度随时间的变化趋势由该点在空间中温度分布曲率直接决定。

这里举一个简单的热传递实例。假设 x 为一维空间,且 T(x,t=0)=sin(x);即整个系统在初始情况下,温度在空间中正好是正弦分布。那么,整个系统的温度在下一个时刻如何变化呢?T(x,t=0)t=α2T(x,t=0)2x=α2sin(x)2x=α sin(x),变化方向正好与现在分布相反。也就是说,当前温度为正的区域温度将会下降,温度为负的区域温度将会上升,而且温度越高或者越低则变化幅度越大;这与我们的生活常识一致。热传递在一些复杂空间和复杂分布的系统中可以变得极其复杂,但是本质上却是非常简单的。

热力迭代

了解热力流动的规律有什么意义呢?掌握了规律,我们就可以对整个热力系统沿时间轴进行推演。所有的热力学模型应用都基于此。

Tnext=Tprevious+ΔT=Tprevious+ΔtTt

热力系统的迭代过程如上式所述。每一个时刻,我们求出热力系统中接下来的温度变化量,从而不停地把整个系统推向下一时刻。这里的温度变化量由时间差 Δt 和温度变化率 Tt 共同决定;前者是一个重要的模拟参数,决定系统迭代的步幅;后者则由之前的热传递公式求出。

标准热力系统

一个标准的系统由3部分构成:

  • Initial Condition
    T(x,t=0)=F(x)

  • Boundary Condition
    T(xboundary)=Φ(x,t)

  • Heat Equation
    T(x,t)t=2T(x,t)2x

也就是说,除了热力学方程外(上述公式传导系数 α 被设为1而消去),我们还需要设置系统的初始状态,以及系统的边界条件。系统的边界条件有很多不同的选择,常用的是Dirichlet条件,就是让系统边界固定在一个温度,如零度上。
总的来说,热力学模型,就是在确定初始热力空间分布以及空间边界条件的情况下,通过热力传递公式,选定合适时间步幅,沿时间轴递推演进热力空间分布的过程。

2. 常见滤镜

热力学在图片上最为常见的俩个应用为:
- isotropic diffusion (各向同性扩散)
- anisotropic diffusion (各向异性扩散)

这都是把图片的intensity(灰度值)视作初始温度,把图片边框的1像素固定为边界,边界温度维持不变;然后在图片上迭代推演热力传递公式,扩散热力,更新各个像素温度。(作为边框的1像素最后将被丢弃)

各向同性扩散与高斯模糊

各向同性扩散完全等价于高斯模糊以及低通滤波。

高斯模糊

高斯模糊是一种常用的去噪或者模糊图片方法,其具体方法是对原始图片和一个高斯模板进行卷积。核心在于高斯模板,这是一个至少3*3的奇数边长的矩阵,从中心点到四周数值呈现各向同性(即convariance matrix为值一致的对角矩阵)高斯分布;另外,模板所有值和为 1(normalize)。本文不作更多讨论。

ITemplate=F1{F(I)F(Template)},原图与模板的卷积等效于原图和模板在傅里叶空间中之间相乘并进行傅里叶逆变换;高斯模板在傅里叶空间中仍是一个高斯分布(标准差变倒数),傅里叶空间中的高斯模板将会强化低频信号并滤过高频信号,高斯模糊完全等价于低通滤波。

等价的各向同性扩散

这里我们从数学上来证明这个等价。
首先注意到空间曲率在离散空间上的求解:

T(x) 2T(x) =T(x+1)T(x)1=T(x1)T(x)1=T(x+1)+T(x1)2T(x)
这实际上也是拉普拉斯算子(Laplacian operator),具体展开在二维空间的话:
2T(x,y)=T(x+1,y)+T(x1,y)+T(x,y+1)+T(x,y1)4T(x,y)
所以,各向同性扩散的热力迭代可以展开如下:
T(x,y,t=1)=T(x,y,t=0)+ΔT=T(x,y,t=0)+Δt2T(x,y)=ΔtT(x+1,y)+ΔtT(x1,y)+ΔtT(x,y+1)+ΔtT(x,y1)+(14Δt)T(x,y)
显然,这个迭代式表示的就是原图片与一个3*3的高斯模板进行卷积,其中 Δt 应该小于0.25以确保迭代稳定。

各向异性扩散与美颜滤镜

Anisotropic diffusion(各向异性扩散)是常用的图片加强算法。它在各向同性扩散的基础上前进了一步,在模糊图片的同时保持住图片中的边缘锐度,达到有选择的模糊。这一方法常见于美颜相机中,它可以保持住脸部的线条同时通过模糊消除斑点,让皮肤看起来整洁、细腻、柔和。另外,也是非常好的图片去噪方法。

算法原理

算法的关键是在扩散中保护边缘信息(即图片中物体的轮廓)。轮廓往往和其周围环境是有强烈对比度的,这种时候,其温度的空间梯度 T(x,t)x 将是一个较大的值。所以我们利用这一点来构造各向异性扩散,抑制高温差之间的热传递,以保护高温差代表的轮廓信息。

这里我们使用一个函数求取扩散抑制系数:

k(x) g(x) =g(T(x))=ex2q2
x为空间二维向量;g(x)是一个值域(0,1]的单调递减函数,所以温差越高,扩散系数 k 越小。这里还有一个抑制敏感度参数 qq 越小,函数就对温差越敏感,即使很小的温差也触发明显的抑制;q 越大,则越迟钝。我们的温度范围是 [0,255],所以 q 参数一般是[10,100]。

基于上一节推导的拉普拉斯算子,进行变化:

2T(x,y) 2T(x,y) Gn Gs Gw Ge =T(x+1,y)+T(x1,y)+T(x,y+1)+T(x,y1)4T(x,y)=Gn+Gs+Gw+Ge=T(x)=T(x1,y)T(x,y)=T(x)=T(x+1,y)T(x,y)=T(y)=T(x,y1)T(x,y)=T(y)=T(x,y+1)T(x,y)

最终,各向异性扩散的热力迭代可以展开如下:

T(x,y,t=1)=T(x,y,t=0)+ΔT=T(x,y,t=0)+Δt2T(x,y)=T(x,y,t=0)+Δt{k(Gn)Gn+k(Gs)Gs+k(Gw)Gw+k(Ge)Ge}

Python代码实现

def anisotropic(image, time_gap=0.15, iterations=20, q=10):
    img = image.copy().astype(np.int)
    deno = q ** 2
    s = img.shape
    tmp = np.zeros(s, img.dtype)
    for i in range(iterations):
        for x in range(1, s[0] - 1):
            for y in range(1, s[1] - 1):
                NI = img[x - 1, y] - img[x, y]
                SI = img[x + 1, y] - img[x, y]
                WI = img[x, y - 1] - img[x, y]
                EI = img[x, y + 1] - img[x, y]
                cN = math.exp(-NI ** 2 / deno)
                cS = math.exp(-SI ** 2 / deno)
                cW = math.exp(-WI ** 2 / deno)
                cE = math.exp(-EI ** 2 / deno)
                tmp[x, y] = img[x, y] + time_gap * (cN * NI + cS * SI + cE * EI + cW * WI)
        img = tmp
    return img

3 图像分割

热力学还有着更为复杂和有趣的应用,特别是在图像分割上,这一点后续再做整理

2016-07-26 09:49:21 qq_19891827 阅读数 1181
  • 以性别预测为例,谈谈数据挖掘中常见的分类算法

    互联网的迅猛发展,催生了海量数据的产生。如何挖掘数据的深层价值变得尤为重要。然而,数据挖掘复杂的数学内容使很多人望而却步。本议题试图以实例的形式,用尽量通俗的方式,针对性别预测这个分类问题,来谈一下数据挖掘基本的处理流程,常见的算法和算法的选择等。 讲师:王琪,友盟数据挖掘工程师,武汉大学硕士,工作涉及友盟的各类数据挖掘和分析任务。对数据挖掘和分析,自然语言处理和文本检索有多年的理论和实践经验。

    21926 人正在学习 去看看 CSDN讲师
图像处理,听起来是个十分高深的学问,貌似需要用到一些很深奥的数学知识,让人望而却步。其实在前端角度看,利用html5的canvas技术即可实现简单的图像处理,同时不需要很高深的数学知识,只要你有高中以上的数学水平,足矣。本篇博文主要探讨利用canvas技术,查找图像边缘的算法思路,同时贴出本人写出的查找边缘算法的详细代码。

在正式开始之前首先介绍两个处理图像问题常用的html5的API:

一、处理图像问题常用的html5的API.
(1).HTML5 canvas getImageData() 方法;
getImageData() 方法返回一个 ImageData 对象,该方法下的data对象,以一维数组的方式拷贝了画布指定矩形的像素数据。
对于 ImageData 对象中的每个像素,都存在着四方面的信息,即 RGBA 值:
R - 红色 (0-255)
G - 绿色 (0-255)
B - 蓝色 (0-255)
A - alpha 通道 (0-255; 0 是透明的,255 是完全可见的)。
简单来说,图像画面在网页中是以像素作为最小单位的,每幅图像以网格形式分为若干像素块,每一像素块上只有一种颜色,足够大量这样的像素块拼凑在一起形成了一幅完整的图像。以下图(左)中一朵花为例,将其放大一定倍数得到下图(右),可以看到图2中花朵被以网格形式分成若干块,这里的每一个块就是一个像素。



下面介绍一下图像颜色,网页中图像多以RGB颜色模式来呈现的,在RGB模式下图像通过3种颜色,R - 红色 (0-255),G - 绿色 (0-255),B - 蓝色 (0-255),将这3种颜色按不同比例混合后会得到其他任何颜色。
回到getImageData() 方法,该方法下data对象以一维数组形式保存了画布中所有图像的像素数据,每个像素中都保存着四个信息,除上面介绍的RGB颜色信息外,还保存了A - alpha 通道,也就是像素块的透明度情况.以画布中前两个像素为例,在data数组中的存储方式如下:data[0]="R(第一个像素点红色颜色值)",data[1]="G(第一个像素点绿色颜色值)",data[2]="B(第一个像素点蓝色颜色值)",data[3]="A(第一个像素点透明度信息)",data[4]="R(第二个像素点红色颜色值)",data[5]="G(第二个像素点绿色颜色值)",data[6]="B(第二个像素点蓝色颜色值)",data[7]="A(第二个像素点透明度信息)"......以此类推保存画布中图像的所有像素点信息。
语法:var imgData=context.getImageData(x,y,width,height);

参数 描述
x 开始复制的左上角位置的 x 坐标。
y 开始复制的左上角位置的 y 坐标。
width 将要复制的矩形区域的宽度。
height 将要复制的矩形区域的宽度

(2).putImageData() 方法:

将图像数据(从指定的 ImageData 对象)放回画布上。即将包含图像所有像素RGBA信息的对象,绘制为真实图像。
语法:context.putImageData(imgData,x,y,dirtyX,dirtyY,dirtyWidth,dirtyHeight);

参数 描述
imgData
规定要放回画布的 ImageData 对象。
x ImageData 对象左上角的 x 坐标。
y
ImageData 对象左上角的 y 坐标。
dirtyX
水平值,在画布上放置图像的位置。
dirtyY
水平值(y),在画布上放置图像的位置
dirtyWidth
在画布上绘制图像所使用的宽度
dirtyHeight
在画布上绘制图像所使用的高度

二、查找图像边缘算法思路
(1)黑白二值化:首先对图像进行黑白二值化处理,通过getImageData()方法获取画布中图像的所有像素的RGBA信息,以128为界,与data数组中每个RGBA值作对比,低于128则将其数值变为0,高于128将其数值变为255,经过此阶段处理后,图像中只保留黑、白两个颜色,图像的集合性质只与像素值为0或255的点的位置有关,不再涉及像素的多级值,使处理变得简单,而且数据的处理和压缩量小。下图(左)为原图,下图(右)为经黑白二值化处理后的图像。

               
具体前端javascript代码如下:
    

var cvs=document.getElementById('canvas');
    var HEIGHT=cvs.height;
    var WIDTH=cvs.width;
    var ctx=cvs.getContext('2d');
    var pixel = null;
    var opixel=null;
    var xpixel=null;
    var edge=[];
    var img=new Image();
    img.src='http://ui.yidaochn.com/test/zz.jpg';
    img.onload=function(){
        ctx.drawImage(img,0,0,WIDTH,HEIGHT);
        pixel = (ctx.getImageData(0, 0, WIDTH, HEIGHT));
        whiteBlack();
    };


 //黑白二值化
    function whiteBlack(){
        var red=0;
        var green=0;
        var blue=0;
        var index=null;
        var average=null;
        for(var i=0;i<HEIGHT;i++) {
            for (var j = 0; j < WIDTH; j++) {
                index=(pixel.width*i+j)*4;
                red=index;
                green=index+1;
                blue=index+2;
                average=Math.round((pixel.data[red]+pixel.data[green]+pixel.data[blue])/3);
                if(average>=128){
                    pixel.data[red]=255;
                    pixel.data[green]=255;
                    pixel.data[blue]=255;
                }else{
                    pixel.data[red]=0;
                    pixel.data[green]=0;
                    pixel.data[blue]=0;
                }
            }
        }
        ctx.putImageData(pixel,0,0);
    }


(2)边缘查找:经过黑白二值化处理后的图像仅保留两种颜色(黑、白),对存有该图像RGBA值信息的data数组进行遍历,每个像素点上的RGB值一定为黑色(0,0,0)或白色(255,255,255)。所以这里我们仅仅比较每一像素点上R值(红色值)与其上、下、左、右相邻像素点的R值是否相等即可,如改点与上下左右4个点的R值相同说明该点不是图像图形的边缘,如该点与至少上下左右4个点其中一个点R值不同,则说明该点为图形边缘,以此类推遍历所有颜色值数据即可得到图像边缘。

具体前端javascript代码如下:(为便于观察,已将边缘颜色填充为红色)
   

function imageEdge(){
        opixel=ctx.getImageData(0,0,WIDTH,HEIGHT);
        var red=0;
        var index=null;
        var redVal=null;
        var prevRedVal=null;
        var nextRedVal=null;
        var topRedVal=null;
        var bottomRedVal=null;


        for(var i=0;i<HEIGHT;i++){
            for(var j=0;j<WIDTH;j++){
                index=(pixel.width*i+j)*4;
                red=index;
                redVal=pixel.data[red];
                prevRedVal=red-4>=0?pixel.data[red-4]:pixel.data[red];
                nextRedVal=pixel.data[red+4];
                topRedVal=(red-WIDTH*4)>=0?pixel.data[red-WIDTH*4]:pixel.data[red];
                bottomRedVal=pixel.data[red+WIDTH*4];


                if(redVal!=nextRedVal||redVal!=topRedVal||redVal!=prevRedVal||redVal!=bottomRedVal){
                    opixel.data[red]=255;
                    edge.push(red);
                }
            }
        }
        ctx.putImageData(opixel,0,0);
    }

经查找边缘操作后的图像如下图所示(边缘已标红),是不是觉得算法是如此简单,有种豁然开朗的感觉。


没有更多推荐了,返回首页