K均值(k-means)聚类算法，顾名思义首先给定K个初始均值作为聚类中心，然后通过分析其他n-k个点同K个聚类中心的距离进行分类，然后对集群求取新的均值作为聚类中心，由此迭代，知道K个不同类别之间的类间距离满足设定阈值条件为止，可应用于一维数据分析和语义分割场景
算法原理及过程：
输入：n个样本的集合
输出：样本集合的聚类
过程：
（1）初始化。随机选择k的样本作为初始聚类的中心。
（2）对样本进行聚类。针对初始化时选择的聚类中心，计算所有样本到每个中心的距离，默认欧式距离，将每个样本聚集到与其最近的中心的类中，构成聚类结果。
（3）计算聚类后的类中心，计算每个类的质心，即每个类中样本的均值，作为新的类中心。
（4）然后重新执行步骤（2）（3），直到聚类结果不再发生改变。
K均值聚类算法的时间复杂度是O(nmk),n表示样本个数，m表示样本维数，k表示类别个数。
来自百度百科：
先随机选取K个对象作为初始的聚类中心。然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。一旦全部对象都被分配了，每个聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是以下任何一个：
1)没有（或最小数目）对象被重新分配给不同的聚类。
2)没有（或最小数目）聚类中心再发生变化。
3)误差平方和局部最小。
伪代码： 选择k个点作为初始质心。 repeat 将每个点指派到最近的质心，形成k个簇 重新计算每个簇的质心 until 质心不发生变化
#python实现
import numpy as np
import pandas as pd
import random
import sys
import time
class KMeansClusterer:
def __init__(self,ndarray,cluster_num):
self.ndarray = ndarray
self.cluster_num = cluster_num
self.points=self.__pick_start_point(ndarray,cluster_num)
def cluster(self):
result = []
for i in range(self.cluster_num):
result.append([])
for item in self.ndarray:
distance_min = sys.maxsize
index=-1
for i in range(len(self.points)):
distance = self.__distance(item,self.points[i])
if distance < distance_min:
distance_min = distance
index = i
result[index] = result[index] + [item.tolist()]
new_center=[]
for item in result:
new_center.append(self.__center(item).tolist())
# 中心点未改变，说明达到稳态，结束递归
if (self.points==new_center).all():
return result
self.points=np.array(new_center)
return self.cluster()
def __center(self,list):
'''计算一组坐标的中心点
'''
# 计算每一列的平均值
return np.array(list).mean(axis=0)
def __distance(self,p1,p2):
'''计算两点间距
'''
tmp=0
for i in range(len(p1)):
tmp += pow(p1[i]-p2[i],2)
return pow(tmp,0.5)
def __pick_start_point(self,ndarray,cluster_num):
if cluster_num <0 or cluster_num > ndarray.shape[0]:
raise Exception("簇数设置有误")
# 随机点的下标
indexes=random.sample(np.arange(0,ndarray.shape[0],step=1).tolist(),cluster_num)
points=[]
for index in indexes:
points.append(ndarray[index].tolist())
return np.array(points)
3.对二维图像像素值进行K均值聚类
需求：
针对某张包含几种颜色的图像，分别统计每类颜色的数量占比，最后将其占比通过饼状图绘制出来，饼状图颜色设置为原图中每类像素的颜色
通过python+opencv实现算法
函数原型： retval, bestLabels, centers = kmeans(data, K, bestLabels, criteria, attempts, flags, centers=None) 函数参数： data: 需要分类数据，最好是np.float32的数据，每个特征放一列。 K: 聚类个数 bestLabels：预设的分类标签或者None criteria：迭代停止的模式选择，这是一个含有三个元素的元组型数。格式为（type, max_iter, epsilon） 其中，type有如下模式： cv2.TERM_CRITERIA_EPS ：精确度（误差）满足epsilon，则停止。 cv2.TERM_CRITERIA_MAX_ITER：迭代次数超过max_iter，则停止。 cv2.TERM_CRITERIA_EPS+cv2.TERM_CRITERIA_MAX_ITER：两者结合，满足任意一个结束。 attempts：重复试验kmeans算法次数，将会返回最好的一次结果 flags：初始中心选择，可选以下两种： v2.KMEANS_PP_CENTERS：使用kmeans++算法的中心初始化算法，即初始中心的选择使眼色相差最大.详细可查阅kmeans++算法。(Use kmeans++ center initialization by Arthur and Vassilvitskii) cv2.KMEANS_RANDOM_CENTERS：每次随机选择初始中心（Select random initial centers in each attempt.） 返回值： compactness：紧密度，返回每个点到相应重心的距离的平方和 labels：结果标记，每个成员被标记为分组的序号，如 0,1,2,3,4...等 centers：由聚类的中心组成的数组
from glob import glob
import cv2
import numpy as np
import matplotlib.pyplot as plt
def get_pixcelstats(name,k_):
# 读取原始图像
#img = cv2.imread('./seg/1.jpg')
img = cv2.imread(name)
img=cv2.cvtColor(img,cv2.COLOR_BGR2RGB)
img = cv2.resize(img, (img.shape[1] // 4, img.shape[0] // 4))
print(img.shape)
# (486, 654, 3)
# 图像二维像素转换为一维
# 转换成3列
data = img.reshape((-1, 3))
print("data.shape = ", data.shape)
data = np.float32(data)
# 定义终止条件 (type,max_iter,epsilon)
criteria = (cv2.TERM_CRITERIA_EPS +
cv2.TERM_CRITERIA_MAX_ITER, 500, 0.1)
#设置类别数
k=k_
# K-Means聚类 聚集成4类
compactness, labels, centers = cv2.kmeans(data, k, None, criteria, 10, cv2.KMEANS_RANDOM_CENTERS)
print("类别数 = ", len(labels))
print("聚类中心数：", len(centers))
print("centers = ", centers)
labs = np.uint8(labels)
lab = labs.reshape((img.shape[0], img.shape[1]))
print("label:",lab.shape)
label = cv2.cvtColor(lab,cv2.COLOR_GRAY2BGR)
#cv2.imshow("l", label)
# 图像转换回uint8二维类型
centers = np.uint8(centers)
res = centers[labels.flatten()]
dst = res.reshape((img.shape))
#cv2.imshow("img", dst)
nums = [];#定义空列表，长度为类别数，初始化为0
for i in range(k):
nums.append(0)
#统计每个类别像素数量
for i in range(lab.shape[0]):
for j in range(lab.shape[1]):
for t in range(k):
if lab[i, j] == t:
nums[t] = nums[t] + 1;
print("nums = ", nums)
#计算每类像素占比
total = lab.shape[0] * lab.shape[1]
name = [];
data = [];
colors = [];
for i in range(k):
col = ()
name.append(str(i))
data.append(nums[i] / total)#计算占比
cen = centers[i] / 255#聚类中心像素归一化
col = (cen[0], cen[1], cen[2])
colors.append(col)#颜色值保存到列表中
print("data = ", data)
#print("col = ", colors)
data1=[]
colors1=[]
name1=[]
#去除白色和黑色
for i in range(len(data)):
if data[i]>0.02 and data[i]<0.5:
name1.append(i)
data1.append(data[i])
colors1.append(colors[i])
plt.subplot(121)
plt.imshow(img)
plt.title("Src")
plt.subplot(122)
#plt.pie(data, labels=name, colors=colors, autopct='%0.2f%%',wedgeprops={'linewidth': 1, 'edgecolor': "black"})
plt.pie(data1, labels=name1, colors=colors1, autopct='%0.2f%%', wedgeprops={'linewidth': 1, 'edgecolor': "black"})
plt.title("Percentage of pixels")
plt.show()
#图像路径
jpg_list = glob(r'.fengeseg*.jpg')
nums_class=[6,7,7,7,7,6,6,8]#预先定义类别数
for i in range(len(jpg_list)):
print("图像路径：",jpg_list[i])
get_pixcelstats(jpg_list[i],nums_class[i])
4.C++ opencv应用举例：饼状图的label值为每一个类别的索引值，python调试无法灵活查看标签值，C++调试可以看
注：opencv读取图像颜色通道是BGR，而matplot绘图颜色是RGB，所以要保证颜色统一需要提前对图像使用cv2.COLOR_BGR2RGB
算法实现：
medianBlur(gray, gray, 5); int width = gray.cols; int height = gray.rows; int sampleCount = width * height; Mat sample_data = gray.reshape(1, sampleCount); Mat data; sample_data.convertTo(data, CV_32FC1); //k均值分类 int num = k;//类别数 Mat label; TermCriteria critera = TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 0.1); kmeans(data, num, label, critera, 8, KMEANS_RANDOM_CENTERS); Mat label_ = label.reshape(1,height);//标签图像 Mat mask(gray.size(), CV_8UC3, Scalar::all(0)); mask.setTo(Scalar(255, 255, 0), label_ == 1); mask.setTo(Scalar(0, 255, 255), label_ == 2);
