前言:
眼前看官们对“近似椭圆算法”大概比较关注,大家都想要分析一些“近似椭圆算法”的相关文章。那么小编同时在网摘上网罗了一些有关“近似椭圆算法””的相关内容,希望小伙伴们能喜欢,小伙伴们一起来学习一下吧!1. K均值算法(K-Means)
是一种无监督的聚类学习算法,它尝试找到样本数据的自然类别,分类K是由用户自己定义的,它在不需要任何其它先验知识的情况下,依据算法的迭代规则,把样本划分为K类,通过不断跌代和移动质心来完成分类。是一种硬分类的方法:即以距离为依据,离哪个点距离越近,它就应该标记为哪个编号,计算两个点之间的距离,有可能是向量(x,y)或(x,y,z)。不断的迭代,中心点不断的变换,使得逐渐接近真实的结果,最后要求取前后两次中心点的差值,或到达一定的迭代次数就结束。
API参数:
参数1:输入的数据集合,可以是一维或多维,它是浮点数。参数2:K 为分类的数目。参数3:分类的标签,分类索引编号。参数4:停止条件,可以用迭代的次数或者我们指定的精度阈值。参数5:attempts 尝试几次,有时候为了获得最佳的分类效果,算法要用不同的初始分类进行尝试。参数6:flags 表示用哪一种方法进行初始化,最常用的是随机选择。
例子代码:
#include<opencv2/opencv.hpp>#include<iostream>using namespace std;using namespace cv;void test(){ Mat srcImg; srcImg = imread("toux.jpg"); if (srcImg.empty()) { cout << "could not load image...\n" << endl; } namedWindow("Original image", CV_WINDOW_AUTOSIZE); imshow("Original image", srcImg); //预定义分割的一些颜色 Scalar colorTab[] = { Scalar(0, 0, 255), Scalar(0, 255, 0), Scalar(0, 0, 0), Scalar(255, 0, 0), Scalar(255, 0, 255), }; //首先获取图像的宽和高,每一个像素对应一个数据点,要把数据进行转换, //kmeans 输入参数是以所有的数据点为每一行,列为数据的维度(图像为3 RGB颜色通道) int width = srcImg.cols; int height = srcImg.rows; int dims = srcImg.channels(); int sampleCount = width*height; //总像素 int clusterCount = 4; //分为 4 类 //数据点,即把所有样本装到一个数据点(一行),每一行只有一个数据 Mat points(sampleCount, dims, CV_32F, Scalar(10)); Mat labels; Mat centers(clusterCount, 1, points.type()); //中心点 //将 RGB 数据转换到样本数据 int index = 0; for (int i = 0; i < height; i++) //循环把每个样本找出来 { for (int j = 0; j < width; j++) { index = i*width + j; Vec3b bgr = srcImg.at<Vec3b>(i, j); //获取图像上点像素的值 //把只作为样本传进去 points.at<float>(index, 0) = static_cast<int>(bgr[0]); //把数据转换 points.at<float>(index, 1) = static_cast<int>(bgr[1]); points.at<float>(index, 2) = static_cast<int>(bgr[2]); } } //运行 kmeans TermCriteria cirteria = TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1); kmeans(points, clusterCount, labels, cirteria, 3, KMEANS_PP_CENTERS, centers); //显示分类的结果 Mat result = Mat::zeros(srcImg.size(), srcImg.type()); for (int i = 0; i < height; i++) { for (int j = 0; j < width; j++) { index = i*width + j; //把二维数组转换到一维数组,找它里面的index //结果显示通过label 获取,根据聚类的编号 int label = labels.at<int>(index, 0); result.at<Vec3b>(i, j)[0] = colorTab[label][0]; result.at<Vec3b>(i, j)[1] = colorTab[label][1]; result.at<Vec3b>(i, j)[2] = colorTab[label][2]; } } for (int i = 0; i < centers.rows; i++) { int x = centers.at<float>(i, 0); int y = centers.at<float>(i, 0); cout << "center = " << i <<" "<< "c.x: " << x <<"\t"<< "c.y: " << y << endl; } imshow("KMeans", result);}
效果图:
2.高斯混合模型(GMM)2.1 一些概念理解2.1.1 协方差
统计学里最基本的就是样本的均值、方差和标准差。在一个含有n个样本的集合X={X1 ,…,Xn}。
均值:
标准差:
方差:
均值描述的是样本集合的中间点,它告诉我们的信息是很有限的,而标准差描述的是样本集合的各个样本点到均值的距离之平均。以这两个集合为例,[0,8,12,20]和[8,9,11,12],两个集合的均值都是10,但显然两个集合差别是很大的,计算两者的标准差,前者是8.3,后者是1.8,显然后者较为集中,所以标准差小一点,标准差描述的就是这种“散布度”。之所以除以n-1而不是除以n,是因为这样能使我们以较小的样本集更好的逼近总体的标准差,即统计上所谓的“无偏估计”。方差则仅仅是标准差的平方。
为什么需要协方差?上面几个统计量看似已经描述的差不多了,但注意到,标准差和方差一般是用来描述一维数据的,现实生活我们常常遇到含有多维数据的数据集,例如要统计多个学科的考试成绩。面对这样的数据集,可以按照每一维独立的计算其方差,但是通常我们还想了解更多,比如,一个男孩子的猥琐程度跟他受女孩子欢迎程度是否存在一些联系啊,嘿嘿~协方差就是这样一种用来度量两个随机变量关系的统计量,我们可以仿照方差的定义:
来度量各个维度偏离其均值的程度,标准差可以这么来定义:
如果协方差的结果的结果为正值,则说明两者是正相关的(从协方差可以引出“相关系数”的定义),也就是说一个人越猥琐就越受女孩子欢迎,结果为负值就说明负相关的,越猥琐女孩子越讨厌,可能吗?如果为0,也是就是统计上说的“相互独立”。
2.1.2 高斯函数(模型)
高斯一维函数:
高斯概率分布函数:
2.1.3 EM 算法
MLE 是用来求模型参数的,核心是“模型已知,求取参数”,模型的意思就是数据符合什么函数,比如我们硬币的正反就是二项分布模型,再比如我们平时随机生成的一类数据符合高斯模型,公式如下:
L(Θ):联合概率分布函数,就是每个样本出现的概率乘积。x1,x2,x3….xn : 样本Θ:模型的参数(比如高斯模型的两个参数:μ、σ)p(xi ; Θ):第i个样本的概率模型xi: 第i个样本
平时使用的时候取对数,完全为了求解方便:
ê 为平均对数似然。而我们平时所称的最大似然为最大的对数平均似然,即:
举个例子:抛硬币的简单例子,现在有一个正反面不是很匀称的硬币,如果正面朝上记为H,方面朝上记为T,抛10次的结果如下:
求这个硬币正面朝上的概率有多大?很显然这个概率是0.2。现在我们用MLE的思想去求解它。我们知道每次抛硬币都是一次二项分布,设正面朝上的概率是μ;那么似然函数为:
x=1表示正面朝上,x=0表示方面朝上。那么有:
求导:
令导数为0,很容易得到:
也就是0.2 。
再举个例子:
假如我们有一组连续变量的采样值(x1,x2,…,xn),我们知道这组数据服从正态分布,标准差已知。请问这个正态分布的期望值为多少时,产生这个已有数据的概率最大?
P(Data | M) = ?
根据公式:
可得:
对μ求导可得:
则最大似然估计的结果为μ=(x1+x2+…+xn) / n
总结:其实我们用的很多函数都可以说是一个最大似然函数,比如符合y = x2、y = kx…都可以当做一个模型去求解一个极大似然函数,只不过我们得到的数据不符合这些模型而已。只要是求概率的问题,都会写出一个函数,这个函数其实就是最大似然函数,可以说是目标函数,也可以说是似然函数,把每个数据出现的概率相乘就是似然函数,再求对数,再求均值,再求最值,这就是极大似然了,就是一个名字而已!
EM算法核心:猜(E-step),反思(M-step),重复;
算法理解:
问题一:
现在一个班里有50个男生,50个女生,且男生站左,女生站右。我们假定男生的身高服从正态分布:
N(μ1,σ1²)
女生的身高则服从另一个正态分布:
N(μ2,σ2²)
这时候我们可以用极大似然法(MLE),分别通过这50个男生和50个女生的样本来估计这两个正态分布的参数。
问题二:
但现在我们让情况复杂一点,就是这50个男生和50个女生混在一起了。我们拥有100个人的身高数据,却不知道这100个人每一个是男生还是女生。这时候情况就有点尴尬,因为通常来说,我们只有知道了精确的男女身高的正态分布参数我们才能知道每一个人更有可能是男生还是女生。但从另一方面去考量,我们只有知道了每个人是男生还是女生才能尽可能准确地估计男女各自身高的正态分布的参数。
问题二需要求解两个问题:
假设a=(第k个样本是男生还是女生)假设b=(高斯模型的参数)
如果知道a,那用问题一的方法就可以求解b,如果知道b那也就可以分类a了,但是前提是两个都不知道,比如y=x+1,现在让你求解x和y的值,怎么办?
解决:
总结:其实EM算法就是先通过假设的参数把数据进行分类,然后通过分类的数据计算参数,接着对比计算的参数和假设的参数是否满足精度,不满足就返回去,满足就结束。EM是一种思想,而不是像K-means等是一种算法。
高斯混合函数的原理:(1)单高斯分布模型GSM:多维变量X服从高斯分布时,它的概率密度函数为:
x是维度为d的列向量,u是模型期望,Σ是模型方差。在实际应用中u通常用样本均值来代替,Σ通常用样本方差来代替。很容易判断一个样x本是否属于类别C。因为每个类别都有自己的u和Σ,把x代入(1)式,当概率大于一定阈值时我们就认为x属于C类。从几何上讲,单高斯分布模型在二维空间应该近似于椭圆,在三维空间上近似于椭球。遗憾的是在很多分类问题中,属于同一类别的样本点并不满足“椭圆”分布的特性。这就引入了高斯混合模型。
高斯混合模型GMM:GMM认为数据是从几个GSM中生成出来的,即:
K需要事先确定好,就像K-means中的K一样。πk是权值因子。其中的任意一个高斯分布N(x;uk,Σk)叫作这个模型的一个component。这里有个问题,为什么我们要假设数据是由若干个高斯分布组合而成的,而不假设是其他分布呢?实际上不管是什么分布,只K取得足够大,这个XX Mixture Model就会变得足够复杂,就可以用来逼近任意连续的概率密度分布。只是因为高斯函数具有良好的计算性能,所GMM被广泛地应用。
样本分类已知情况下的GMM:当每个样本所属分类已知时,GMM的参数非常好确定,直接利用Maximum Likelihood。设样本容量为N,属于K个分类的样本数量分别是N1,N2,…,Nk,属于第k个分类的样本集合是L(k)。
样本分类未知情况下的GMM:
EM求解:
例子代码:
#include<opencv2/opencv.hpp>#include<iostream>using namespace std;using namespace cv;//高斯混合方法using namespace cv::ml;void test(){ Mat srcImg; srcImg = imread("toux.jpg"); if (srcImg.empty()) { cout << "could not load image...\n" << endl; } namedWindow("Original image", CV_WINDOW_NORMAL); imshow("Original image", srcImg); //预定义分割的一些颜色 Scalar colors[] = { Scalar(0, 0, 255), //红 Scalar(0, 255, 0), //绿 Scalar(255, 0, 0), //蓝 Scalar(0, 255, 255), // 黄 Scalar(255, 0, 255), //品红 }; //首先获取图像的宽和高,每一个像素对应一个数据点,要把数据进行转换, //kmeans 输入参数是以所有的数据点为每一行,列为数据的维度(图像为3 RGB颜色通道) int width = srcImg.cols; int height = srcImg.rows; int dims = srcImg.channels(); int numCount = width*height; //总像素点数 int numCluster = 3; //分为 3 类 //数据点,即把所有样本装到一个数据点(一行),每一行只有一个数据 Mat points(numCount, dims, CV_64FC1); Mat labels; //将图像 RGB 数据转换为样本数据 int index = 0; for (int row = 0; row < height; row++) //这里的步骤与 KMeans 是一样的 { for (int col = 0; col < width; col++) { index = row*width + col; Vec3b rgb = srcImg.at<Vec3b>(row, col); //获取图像上点像素的rgb值 //把只作为样本传进去 points.at<double>(index, 0) = static_cast<int>(rgb[0]); points.at<double>(index, 1) = static_cast<int>(rgb[1]); points.at<double>(index, 2) = static_cast<int>(rgb[2]); } } // EM 训练 Ptr<EM>emModel = EM::create(); //生成 EM 期望最大化,起图像分割的方式是基于机器学习的方式 emModel->setClustersNumber(numCluster); //设置分类数 emModel->setCovarianceMatrixType(EM::COV_MAT_SPHERICAL); //协方差矩阵的类型 //迭代条件,EM 训练比 KMeans 耗时,可能会不收敛,所以迭代次数设大点 emModel->setTermCriteria(TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1)); //EM 训练,获得分类结果,参数 labels 与 KMeans 的 labels 参数意思一样,速度比 KMeans 要慢很多 emModel->trainEM(points, noArray(), labels, noArray()); //对每个像素标记颜色与显示 Mat resultNoPredict = Mat::zeros(srcImg.size(), CV_8UC3); Mat resultPredict = Mat::zeros(srcImg.size(), CV_8UC3); Mat sample(dims, 1, CV_64FC1); double time = getTickCount(); int r = 0, g = 0, b = 0; //预言会用到 for (int row = 0; row < height; row++) { for (int col = 0; col < width; col++) { //获取训练的分类结果,放到 result 中 index = row*width + col; //把二维数组转换到一维数组,找它里面的index //结果显示通过label 获取,根据聚类的编号 int label = labels.at<int>(index, 0); Scalar c = colors[label]; //label 上已经有颜色了 resultNoPredict.at<Vec3b>(row, col)[0] = c[0]; resultNoPredict.at<Vec3b>(row, col)[1] = c[1]; resultNoPredict.at<Vec3b>(row, col)[2] = c[2]; //通过预言获得分类结果,因为 EM 训练用的是 srcImg 的颜色数据,所以用 srcImg 的颜色数据做预言, //得到的结果与 result 是一模一样的 b = srcImg.at<Vec3b>(row, col)[0]; g = srcImg.at<Vec3b>(row, col)[1]; r = srcImg.at<Vec3b>(row, col)[2]; sample.at<double>(0) = b; sample.at<double>(1) = g; sample.at<double>(2) = r; //预言 int response = cvRound(emModel->predict2(sample, noArray())[1]); Scalar c2 = colors[response]; resultPredict.at<Vec3b>(row, col)[0] = c2[0]; resultPredict.at<Vec3b>(row, col)[1] = c2[1]; resultPredict.at<Vec3b>(row, col)[2] = c2[2]; } } //打印所需要的时间 cout << "execution time(ms):" << (getTickCount() - time) / getTickFrequency() * 1000 << endl; namedWindow("EM-Segmentation nopredict", CV_WINDOW_NORMAL); imshow("EM-Segmentation nopredict", resultNoPredict); namedWindow("EM-Segmentation predict", CV_WINDOW_NORMAL); imshow("EM-Segmentation predict", resultPredict);}int main(){ test(); waitKey(0); return 0;}
效果图:
遇到的问题:
我的解决办法:
更换 OpenCV 版本:报错时用的是3.1版本,更换成3.3版本,这里要注意 OpenCV 版本与 VS 之间的对应版本即可。
标签: #近似椭圆算法