K-means算法原理理论+opencv实现
写在前面：之前想分类图像的时候有看过k-means算法，当时一知半解的去使用，不懂原理不懂使用规则。。。显然最后失败了，然后看了《机器学习》这本书对k-means算法有了理论的认识，现在通过贾志刚老师的视频有了实际应用的理解。
k-means算法原理
注：还是和之前一样，核心都是别人的，我只是知识的搬运工并且加上了自己的理解。弄完之后发现理论部分都是别人的~~没办法这算法太简单了。。。
k-means含义：无监督的聚类算法。
无监督：就是不需要人干预，拿来一大批东西直接放进算法就可以进行分类。svm和神经网络都是需要提前训练好然后再进行分类这样就是监督学习。而k-means和k近邻都是无监督学习。
聚类：通过一个中心聚在一起的分类，比如给你一批数据让你分成三类，那就是三个中心，那这三个中心代表的意思就是三个类。
k-means步骤：
从上图中，我们可以看到，a，b，c，d，e是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以k=2。
然后，k-means的算法如下：
随机在图中取k（这里k=2）个种子点。
然后对图中的所有点求到这k个种子点的距离，假如点pi离种子点si最近，那么pi属于si点群。（上图中，我们可以看到a，b属于上面的种子点，c，d，e属于下面中部的种子点）
接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了a，b，c，下面的种子点聚合了d，e）。
这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”。
求点群中心的算法
一般来说，求点群中心点的算法你可以很简的使用各个点的x/y坐标的平均值。不过，我这里想告诉大家另三个求中心点的的公式：
minkowski distance公式——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。
euclidean distance公式——也就是第一个公式λ=2的情况
cityblock distance公式——也就是第一个公式λ=1的情况
k-means的缺点：
在 k-means 算法中 k 是事先给定的，这个 k 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 k-means 算法的一个不足。
在 k-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 k-means算法的一个主要问题。
从 k-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
opencv+k-means
没什么好写的，因为这个k-means比较简单，主要说的就是函数参数的应用而已：
voidrng::fill(inputoutputarraymat, intdisttype, inputarraya, inputarrayb, boolsaturaterange=false)
这个函数是对矩阵mat填充随机数，随机数的产生方式有参数2来决定，如果为参数2的类型为rng::uniform，则表示产生均一分布的随机数，如果为rng::normal则表示产生高斯分布的随机数。对应的参数3和参数4为上面两种随机数产生模型的参数。比如说如果随机数产生模型为均匀分布，则参数a表示均匀分布的下限，参数b表示上限。如果随机数产生模型为高斯模型，则参数a表示均值，参数b表示方程。参数5只有当随机数产生方式为均匀分布时才有效，表示的是是否产生的数据要布满整个范围（没用过，所以也没仔细去研究）。另外，需要注意的是用来保存随机数的矩阵mat可以是多维的，也可以是多通道的，目前最多只能支持4个通道。
voidrandshuffle(inputoutputarraydst, doubleiterfactor=1.,rng*rng=0)
该函数表示随机打乱1d数组dst里面的数据，随机打乱的方式由随机数发生器rng决定。iterfactor为随机打乱数据对数的因子，总共打乱的数据对数为：dst.rows*dst.cols*iterfactor，因此如果为0，表示没有打乱数据。
class termcriteria
类termcriteria 一般表示迭代终止的条件，如果为cv_termcrit_iter，则用最大迭代次数作为终止条件，如果为cv_termcrit_eps则用精度作为迭代条件，如果为cv_termcrit_iter+cv_termcrit_eps则用最大迭代次数或者精度作为迭代条件，看哪个条件先满足。
doublekmeans(inputarraydata, intk, inputoutputarraybestlabels, termcriteriacriteria, intattempts, intflags, outputarraycenters=noarray())
该函数为kmeans聚类算法实现函数。参数data表示需要被聚类的原始数据集合，一行表示一个数据样本，每一个样本的每一列都是一个属性；参数k表示需要被聚类的个数；参数bestlabels表示每一个样本的类的标签，是一个整数，从0开始的索引整数；参数criteria表示的是算法迭代终止条件；参数attempts表示运行kmeans的次数，取结果最好的那次聚类为最终的聚类，要配合下一个参数flages来使用；参数flags表示的是聚类初始化的条件。其取值有3种情况，如果为kmeans_random_centers，则表示为随机选取初始化中心点，如果为kmeans_pp_centers则表示使用某一种算法来确定初始聚类的点；如果为kmeans_use_initial_labels，则表示使用用户自定义的初始点，但是如果此时的attempts大于1，则后面的聚类初始点依旧使用随机的方式；参数centers表示的是聚类后的中心点存放矩阵。该函数返回的是聚类结果的紧凑性，其计算公式为：
注意点一：
这是说个我自己不理解的地方：fill(inputoutputarraymat, intdisttype, inputarraya, inputarrayb, boolsaturaterange=false)
这里的inputarraya, inputarrayb------>>>分别用了scalar(center.x, center.y, 0, 0), scalar(img.cols*0.05, img.rows*0.05, 0, 0)去替换
去查了一下手册：inputarray这个接口类可以是mat、mat_、mat_、vector、vector、vector。没有提到scalar()可以使用
特意定义了一个：inputarray test = scalar(1,1);这个又是可以的，定义mat不行，vector也不行，这个真的不知道什么原因，有时间得去看源码a,b的使用。
//----下面的定义都是错误的，运行的结果都不对，原因暂时不知道
mat a = (mat_(1, 2) << center.x, center.y);
mat b = (mat_(1, 2) << img.cols*0.05, img.rows*0.05);
inputarray a1 = scalar(center.x, center.y);
inputarray b1 = scalar(img.cols*0.05, img.rows*0.05);
mat a2 = a1.getmat();
mat b2 = b1.getmat();
mat c(1, 2, cv_8uc1);
c = scalar(center.x, center.y);
mat c1(1, 2, cv_8uc1);
c1 = scalar(img.cols*0.05, img.rows*0.05);
rng.fill(pointchunk, rng::normal, a, b, 0);
注意点二：
kmeans()函数的输入只接受data0.dims 0 ，
第一个dims一般都不会越界（三维不行）
第二个参数cv_32f == float，千万别带入cv_8u == uchar
第三个参数不用说了，设置的种类肯定是大于0的
注意点三：
opencv里面k-means函数的样本数据、标签、中心点的存储：
#include
#include
using namespace cv;
using namespace std;
int main(int argc, char** argv) {
mat img(500, 500, cv_8uc3);
rng rng(12345);
const int max_ncluster = 5;
scalar colortab[] = {
scalar(0, 0, 255),
scalar(0, 255, 0),
scalar(255, 0, 0),
scalar(0, 255, 255),
scalar(255, 0, 255)
};
//inputarray a = scalar(1,1);
int numcluster = rng.uniform(2, max_ncluster + 1);//随机类数
int samplecount = rng.uniform(5, 1000);//样本点数量
mat matpoints(samplecount, 1, cv_32fc2);//样本点矩阵：samplecount x 2
mat labels;
mat centers;
// 生成随机数
for (int k = 0; k < numcluster; k++) {
point center;//随机产生中心点
center.x = rng.uniform(0, img.cols);
center.y = rng.uniform(0, img.rows);
mat pointchunk = matpoints.rowrange( k*samplecount / numcluster,
(k + 1)*samplecount / numcluster);
//-----这句话的意思我不明白作用是什么，没意义啊！
/*mat pointchunk = matpoints.rowrange(k*samplecount / numcluster,
k == numcluster - 1 ? samplecount : (k + 1)*samplecount / numcluster);*/
//-----符合高斯分布的随机高斯
rng.fill(pointchunk, rng::normal, scalar(center.x, center.y, 0, 0), scalar(img.cols*0.05, img.rows*0.05, 0, 0));
}
randshuffle(matpoints, 1, &rng);//打乱高斯生成的数据点顺序
// 使用kmeans
kmeans(matpoints, numcluster, labels, termcriteria(termcriteria::eps + termcriteria::count, 10, 0.1), 3, kmeans_pp_centers, centers);
// 用不同颜色显示分类
img = scalar::all(255);
for (int i = 0; i < samplecount; i++) {
int index = labels.at(i);
point p = matpoints.at(i);
circle(img, p, 2, colortab[index], -1, 8);
}
// 每个聚类的中心来绘制圆
for (int i = 0; i < centers.rows; i++) {
int x = centers.at(i, 0);
int y = centers.at(i, 1);
printf(c.x= %d, c.y=%d, x, y);
circle(img, point(x, y), 40, colortab[i], 1, line_aa);
}
imshow(kmeans-data-demo, img);
waitkey(0);
return 0;
}
分类代码：
#include
#include
using namespace cv;
using namespace std;
rng rng(12345);
const int max_ncluster = 5;
int main(int argc, char** argv) {
//mat img(500, 500, cv_8uc3);
mat inputimage = imread(1.jpg);
assert(!inputimage.data);
scalar colortab[] = {
scalar(0, 0, 255),
scalar(0, 255, 0),
scalar(255, 0, 0),
scalar(0, 255, 255),
scalar(255, 0, 255)
};
mat matdata = mat::zeros(size(inputimage.channels(), inputimage.rows*inputimage.cols), cv_32fc1);
int ncluster = 5; //rng.uniform(2, max_ncluster + 1);//聚类数量
mat label;//聚类标签
mat centers(ncluster, 1, matdata.type());
for (size_t i = 0; i < inputimage.rows; i++)//把图像存储到样本容器
{
uchar* ptr = inputimage.ptr(i);
for (size_t j = 0; j < inputimage.cols; j++)
{
matdata.at(i*inputimage.cols + j, 0) = ptr[j*inputimage.channels()];
matdata.at(i*inputimage.cols + j, 1) = ptr[j*inputimage.channels() +1];
matdata.at(i*inputimage.cols + j, 2) = ptr[j*inputimage.channels() +2];
}
}
mat result = mat::zeros(inputimage.size(), inputimage.type());
termcriteria criteria = termcriteria(termcriteria::eps + termcriteria::count, 20, 0.1);
kmeans(matdata, ncluster, label, criteria, 3, kmeans_pp_centers, centers);
for (size_t i = 0; i < inputimage.rows; i++)
{
for (size_t j = 0; j < inputimage.cols; j ++)
{
int index = label.at(i*inputimage.cols + j,0);
result.at(i, j)[0] = colortab[index][0];
result.at(i, j)[1] = colortab[index][1];
result.at(i, j)[2] = colortab[index][2];
}
}
imshow(12, result);
waitkey(0);
return 0;
}
电力监控系统在生产厂房四期扩建项目的应用
安森美半导体用于白家电各功能模块的高能效方案
全球产品领导奖！云电脑界的显眼包来啦
无线耳机市场蓬勃发展 2016年有望超有线耳机市场
高压分压器接线方法-使用方法
K-means算法原理理论+opencv实现
荣耀V9评测：华为荣耀V9对比一加3t、华为Mate9、小米MIX、小米6，你会选购哪一部？
AR技术在铁路交通运输行业的作用
华为首款NAS家庭存储发布
央视点名某些APP青少年模式形同虚设
模拟电路设计师是否有必要？
雷达的基本工作原理
心型LED电路的制作
苹果新技术将为我们带来可感受的触摸屏键盘
华为携手伙伴打造联合创新解决方案,助力新基建的落地
多种电子元器件检验要求与方法
美国是否暂缓华为禁令？美国总统特朗普：由于国家安全问题，他不想与华为做生意
基于人工智能的图纸检测与识别方案
自动驾驶公司智行者科技获评“国家知识产权优势企业”
LM4912左、右双声道的放大电路图
k-means算法原理
注：还是和之前一样，核心都是别人的，我只是知识的搬运工并且加上了自己的理解。弄完之后发现理论部分都是别人的~~没办法这算法太简单了。。。
k-means含义：无监督的聚类算法。
无监督：就是不需要人干预，拿来一大批东西直接放进算法就可以进行分类。svm和神经网络都是需要提前训练好然后再进行分类这样就是监督学习。而k-means和k近邻都是无监督学习。
聚类：通过一个中心聚在一起的分类，比如给你一批数据让你分成三类，那就是三个中心，那这三个中心代表的意思就是三个类。
k-means步骤：
从上图中，我们可以看到，a，b，c，d，e是五个在图中点。而灰色的点是我们的种子点，也就是我们用来找点群的点。有两个种子点，所以k=2。
然后，k-means的算法如下：
随机在图中取k（这里k=2）个种子点。
然后对图中的所有点求到这k个种子点的距离，假如点pi离种子点si最近，那么pi属于si点群。（上图中，我们可以看到a，b属于上面的种子点，c，d，e属于下面中部的种子点）
接下来，我们要移动种子点到属于他的“点群”的中心。（见图上的第三步）
然后重复第2）和第3）步，直到，种子点没有移动（我们可以看到图中的第四步上面的种子点聚合了a，b，c，下面的种子点聚合了d，e）。
这个算法很简单，但是有些细节我要提一下，求距离的公式我不说了，大家有初中毕业水平的人都应该知道怎么算的。我重点想说一下“求点群中心的算法”。
求点群中心的算法
一般来说，求点群中心点的算法你可以很简的使用各个点的x/y坐标的平均值。不过，我这里想告诉大家另三个求中心点的的公式：
minkowski distance公式——λ可以随意取值，可以是负数，也可以是正数，或是无穷大。
euclidean distance公式——也就是第一个公式λ=2的情况
cityblock distance公式——也就是第一个公式λ=1的情况
k-means的缺点：
在 k-means 算法中 k 是事先给定的，这个 k 值的选定是非常难以估计的。很多时候，事先并不知道给定的数据集应该分成多少个类别才最合适。这也是 k-means 算法的一个不足。
在 k-means 算法中，首先需要根据初始聚类中心来确定一个初始划分，然后对初始划分进行优化。这个初始聚类中心的选择对聚类结果有较大的影响，一旦初始值选择的不好，可能无法得到有效的聚类结果，这也成为 k-means算法的一个主要问题。
从 k-means 算法框架可以看出，该算法需要不断地进行样本分类调整，不断地计算调整后的新的聚类中心，因此当数据量非常大时，算法的时间开销是非常大的。
opencv+k-means
没什么好写的，因为这个k-means比较简单，主要说的就是函数参数的应用而已：
voidrng::fill(inputoutputarraymat, intdisttype, inputarraya, inputarrayb, boolsaturaterange=false)
这个函数是对矩阵mat填充随机数，随机数的产生方式有参数2来决定，如果为参数2的类型为rng::uniform，则表示产生均一分布的随机数，如果为rng::normal则表示产生高斯分布的随机数。对应的参数3和参数4为上面两种随机数产生模型的参数。比如说如果随机数产生模型为均匀分布，则参数a表示均匀分布的下限，参数b表示上限。如果随机数产生模型为高斯模型，则参数a表示均值，参数b表示方程。参数5只有当随机数产生方式为均匀分布时才有效，表示的是是否产生的数据要布满整个范围（没用过，所以也没仔细去研究）。另外，需要注意的是用来保存随机数的矩阵mat可以是多维的，也可以是多通道的，目前最多只能支持4个通道。
voidrandshuffle(inputoutputarraydst, doubleiterfactor=1.,rng*rng=0)
该函数表示随机打乱1d数组dst里面的数据，随机打乱的方式由随机数发生器rng决定。iterfactor为随机打乱数据对数的因子，总共打乱的数据对数为：dst.rows*dst.cols*iterfactor，因此如果为0，表示没有打乱数据。
class termcriteria
类termcriteria 一般表示迭代终止的条件，如果为cv_termcrit_iter，则用最大迭代次数作为终止条件，如果为cv_termcrit_eps则用精度作为迭代条件，如果为cv_termcrit_iter+cv_termcrit_eps则用最大迭代次数或者精度作为迭代条件，看哪个条件先满足。
doublekmeans(inputarraydata, intk, inputoutputarraybestlabels, termcriteriacriteria, intattempts, intflags, outputarraycenters=noarray())
该函数为kmeans聚类算法实现函数。参数data表示需要被聚类的原始数据集合，一行表示一个数据样本，每一个样本的每一列都是一个属性；参数k表示需要被聚类的个数；参数bestlabels表示每一个样本的类的标签，是一个整数，从0开始的索引整数；参数criteria表示的是算法迭代终止条件；参数attempts表示运行kmeans的次数，取结果最好的那次聚类为最终的聚类，要配合下一个参数flages来使用；参数flags表示的是聚类初始化的条件。其取值有3种情况，如果为kmeans_random_centers，则表示为随机选取初始化中心点，如果为kmeans_pp_centers则表示使用某一种算法来确定初始聚类的点；如果为kmeans_use_initial_labels，则表示使用用户自定义的初始点，但是如果此时的attempts大于1，则后面的聚类初始点依旧使用随机的方式；参数centers表示的是聚类后的中心点存放矩阵。该函数返回的是聚类结果的紧凑性，其计算公式为：
注意点一：
这是说个我自己不理解的地方：fill(inputoutputarraymat, intdisttype, inputarraya, inputarrayb, boolsaturaterange=false)
这里的inputarraya, inputarrayb------>>>分别用了scalar(center.x, center.y, 0, 0), scalar(img.cols*0.05, img.rows*0.05, 0, 0)去替换
去查了一下手册：inputarray这个接口类可以是mat、mat_、mat_、vector、vector、vector。没有提到scalar()可以使用
特意定义了一个：inputarray test = scalar(1,1);这个又是可以的，定义mat不行，vector也不行，这个真的不知道什么原因，有时间得去看源码a,b的使用。
//----下面的定义都是错误的，运行的结果都不对，原因暂时不知道
mat a = (mat_(1, 2) << center.x, center.y);
mat b = (mat_(1, 2) << img.cols*0.05, img.rows*0.05);
inputarray a1 = scalar(center.x, center.y);
inputarray b1 = scalar(img.cols*0.05, img.rows*0.05);
mat a2 = a1.getmat();
mat b2 = b1.getmat();
mat c(1, 2, cv_8uc1);
c = scalar(center.x, center.y);
mat c1(1, 2, cv_8uc1);
c1 = scalar(img.cols*0.05, img.rows*0.05);
rng.fill(pointchunk, rng::normal, a, b, 0);
注意点二：
kmeans()函数的输入只接受data0.dims 0 ，
第一个dims一般都不会越界（三维不行）
第二个参数cv_32f == float，千万别带入cv_8u == uchar
第三个参数不用说了，设置的种类肯定是大于0的
注意点三：
opencv里面k-means函数的样本数据、标签、中心点的存储：
#include
#include
using namespace cv;
using namespace std;
int main(int argc, char** argv) {
mat img(500, 500, cv_8uc3);
rng rng(12345);
const int max_ncluster = 5;
scalar colortab[] = {
scalar(0, 0, 255),
scalar(0, 255, 0),
scalar(255, 0, 0),
scalar(0, 255, 255),
scalar(255, 0, 255)
};
//inputarray a = scalar(1,1);
int numcluster = rng.uniform(2, max_ncluster + 1);//随机类数
int samplecount = rng.uniform(5, 1000);//样本点数量
mat matpoints(samplecount, 1, cv_32fc2);//样本点矩阵：samplecount x 2
mat labels;
mat centers;
// 生成随机数
for (int k = 0; k < numcluster; k++) {
point center;//随机产生中心点
center.x = rng.uniform(0, img.cols);
center.y = rng.uniform(0, img.rows);
mat pointchunk = matpoints.rowrange( k*samplecount / numcluster,
(k + 1)*samplecount / numcluster);
//-----这句话的意思我不明白作用是什么，没意义啊！
/*mat pointchunk = matpoints.rowrange(k*samplecount / numcluster,
k == numcluster - 1 ? samplecount : (k + 1)*samplecount / numcluster);*/
//-----符合高斯分布的随机高斯
rng.fill(pointchunk, rng::normal, scalar(center.x, center.y, 0, 0), scalar(img.cols*0.05, img.rows*0.05, 0, 0));
}
randshuffle(matpoints, 1, &rng);//打乱高斯生成的数据点顺序
// 使用kmeans
kmeans(matpoints, numcluster, labels, termcriteria(termcriteria::eps + termcriteria::count, 10, 0.1), 3, kmeans_pp_centers, centers);
// 用不同颜色显示分类
img = scalar::all(255);
for (int i = 0; i < samplecount; i++) {
int index = labels.at(i);
point p = matpoints.at(i);
circle(img, p, 2, colortab[index], -1, 8);
}
// 每个聚类的中心来绘制圆
for (int i = 0; i < centers.rows; i++) {
int x = centers.at(i, 0);
int y = centers.at(i, 1);
printf(c.x= %d, c.y=%d, x, y);
circle(img, point(x, y), 40, colortab[i], 1, line_aa);
}
imshow(kmeans-data-demo, img);
waitkey(0);
return 0;
}
分类代码：
#include
#include
using namespace cv;
using namespace std;
rng rng(12345);
const int max_ncluster = 5;
int main(int argc, char** argv) {
//mat img(500, 500, cv_8uc3);
mat inputimage = imread(1.jpg);
assert(!inputimage.data);
scalar colortab[] = {
scalar(0, 0, 255),
scalar(0, 255, 0),
scalar(255, 0, 0),
scalar(0, 255, 255),
scalar(255, 0, 255)
};
mat matdata = mat::zeros(size(inputimage.channels(), inputimage.rows*inputimage.cols), cv_32fc1);
int ncluster = 5; //rng.uniform(2, max_ncluster + 1);//聚类数量
mat label;//聚类标签
mat centers(ncluster, 1, matdata.type());
for (size_t i = 0; i < inputimage.rows; i++)//把图像存储到样本容器
{
uchar* ptr = inputimage.ptr(i);
for (size_t j = 0; j < inputimage.cols; j++)
{
matdata.at(i*inputimage.cols + j, 0) = ptr[j*inputimage.channels()];
matdata.at(i*inputimage.cols + j, 1) = ptr[j*inputimage.channels() +1];
matdata.at(i*inputimage.cols + j, 2) = ptr[j*inputimage.channels() +2];
}
}
mat result = mat::zeros(inputimage.size(), inputimage.type());
termcriteria criteria = termcriteria(termcriteria::eps + termcriteria::count, 20, 0.1);
kmeans(matdata, ncluster, label, criteria, 3, kmeans_pp_centers, centers);
for (size_t i = 0; i < inputimage.rows; i++)
{
for (size_t j = 0; j < inputimage.cols; j ++)
{
int index = label.at(i*inputimage.cols + j,0);
result.at(i, j)[0] = colortab[index][0];
result.at(i, j)[1] = colortab[index][1];
result.at(i, j)[2] = colortab[index][2];
}
}
imshow(12, result);
waitkey(0);
return 0;
}
电力监控系统在生产厂房四期扩建项目的应用
安森美半导体用于白家电各功能模块的高能效方案
全球产品领导奖！云电脑界的显眼包来啦
无线耳机市场蓬勃发展 2016年有望超有线耳机市场
高压分压器接线方法-使用方法
K-means算法原理理论+opencv实现
荣耀V9评测：华为荣耀V9对比一加3t、华为Mate9、小米MIX、小米6，你会选购哪一部？
AR技术在铁路交通运输行业的作用
华为首款NAS家庭存储发布
央视点名某些APP青少年模式形同虚设
模拟电路设计师是否有必要？
雷达的基本工作原理
心型LED电路的制作
苹果新技术将为我们带来可感受的触摸屏键盘
华为携手伙伴打造联合创新解决方案,助力新基建的落地
多种电子元器件检验要求与方法
美国是否暂缓华为禁令？美国总统特朗普：由于国家安全问题，他不想与华为做生意
基于人工智能的图纸检测与识别方案
自动驾驶公司智行者科技获评“国家知识产权优势企业”
LM4912左、右双声道的放大电路图