关键词：
一、理论准备
1.1、图像分割
图像分割是图像处理中的一种方法，图像分割是指将一幅图像分解成若干互不相交区域的集合，其实质可以看成是一种像素的聚类过程。通常使用到的图像分割的方法可以分为：
- 基于边缘的技术
- 基于区域的技术
基于聚类算法的图像分割属于基于区域的技术。
1.2、K-Means算法
K-Means算法是基于距离相似性的聚类算法，通过比较样本之间的相似性，将形式的样本划分到同一个类别中，K-Means算法的基本过程为：
- 初始化常数 ，随机初始化k个聚类中心
- 重复计算以下过程，直到聚类中心不再改变
- 计算每个样本与每个聚类中心之间的相似度，将样本划分到最相似的类别中
- 计算划分到每个类别中的所有样本特征的均值，并将该均值作为每个类新的聚类中心
- 输出最终的聚类中心以及每个样本所属的类别
在K-Means算法中，需要随机初始化k个聚类中心，而K-Means算法对初始聚类中心的选取较为敏感，若选择的聚类中心不好，则得到的聚类结果会非常差，因此，对K-Means算法提出了很多的改进的方法，如K-Means++算法，在K-Means++算法中，希望初始化的k个聚类中心之间的距离尽可能的大，其具体过程为：
- 在数据集中随机选择一个样本点作为第一个初始化的聚类中心
- 选择出其余的聚类中心：
- 计算样本中的每一个样本点与已经初始化的聚类中心之间的距离，并选择其中最短的距离
- 以概率选择距离最大的样本作为新的聚类中心，重复上述过程，直到 个聚类中心都被确定
- 对k个初始化的聚类中心，利用K-Means算法计算最终的聚类中心。
对于K-Means算法的具体过程可以参考博文简单易学的机器学习算法——kMeans，K-Means++算法的具体过程稍后会补充。
二、实践准备
实践中使用Python作为开发语言，使用到的模块包括numpy和Image。numpy模块是python中矩阵计算使用最多的模块。
Image模块是PIL(Python Imaging Library)中的模块，对于Image模块，主要是对图像的一些操作：
- 模块的头文件
import Image as image
- 打开图片
fp = open("003.JPG", "rb")
im = image.open(fp)
首先是以二进制文件的形式打开文件，再利用Image模块的open方法导入图片。
对于如下的图片(圣托里尼)：
- 图片的属性
im.format, im.size, im.mode
得到的结果为：JPEG (1600, 1067) RGB
- 通道分离：
r,g,b = im.split()
分割成三个通道，此时r,g,b分别为三个图像对象。
- 取得像素点的值
im.getpixel((4,4))
由于是RGB三通道的，因此此处的值为：(151, 169, 205)
- 改变单个像素点的值
im.putpixel(xy, color)
- 图像类型转换：
im=im.convert("L")
由RGB的图像转成灰度的图像，其结果为：
- 生成新的图像
Image.new(mode, size)
Image.new(mode, size, color)
如：newImg = Image.new(“GBA”,(640,480),(0,255,0))
- 保存图片
im.save("save.gif","GIF")
三、利用K-Means++算法进行图像分割
3.1、利用K-Means++聚类
在利用K-Means++算法进行图像分割时，将图像中的每一个像素点作为一个样本，对RGB图像来说，每个样本包括三维：(151, 169, 205)，通过归一化，将每个通道的值压缩到[0,1]区间上。数据的导入和处理如下面程序所示：
#coding:UTF-8
import Image as image
import numpy as np
from KMeanspp import run_kmeanspp
def load_data(file_path):
'''导入数据
input: file_path(string):文件的存储位置
output: data(mat):数据
'''
f = open(file_path, "rb") # 以二进制的方式打开图像文件
data = []
im = image.open(f) # 导入图片
m, n = im.size # 得到图片的大小
print m, n
for i in xrange(m):
for j in xrange(n):
tmp = []
x, y, z = im.getpixel((i, j))
tmp.append(x / 256.0)
tmp.append(y / 256.0)
tmp.append(z / 256.0)
data.append(tmp)
f.close()
return np.mat(data)
最终保存成矩阵的形式，矩阵的行为样本的个数，列为每一个通道的数值(RGB)。在利用K-Means++算法对样本进行聚类。主函数如下述代码所示：
if __name__ == "__main__":
k = 10#聚类中心的个数
# 1、导入数据
print "---------- 1.load data ------------"
data = load_data("001.jpg")
# 2、利用kMeans++聚类
print "---------- 2.run kmeans++ ------------"
run_kmeanspp(data, k)
k表示的是聚类的个数。K-Means++程序的实现如下面程序所示：
# coding:UTF-8
'''
Date:20160923
@author: zhaozhiyong
'''
import numpy as np
from random import random
from KMeans import distance, kmeans, save_result
FLOAT_MAX = 1e100 # 设置一个较大的值作为初始化的最小的距离
def nearest(point, cluster_centers):
'''计算point和cluster_centers之间的最小距离
input: point(mat):当前的样本点
cluster_centers(mat):当前已经初始化的聚类中心
output: min_dist(float):点point和当前的聚类中心之间的最短距离
'''
min_dist = FLOAT_MAX
m = np.shape(cluster_centers)[0] # 当前已经初始化的聚类中心的个数
for i in xrange(m):
# 计算point与每个聚类中心之间的距离
d = distance(point, cluster_centers[i, ])
# 选择最短距离
if min_dist > d:
min_dist = d
return min_dist
def get_centroids(points, k):
'''KMeans++的初始化聚类中心的方法
input: points(mat):样本
k(int):聚类中心的个数
output: cluster_centers(mat):初始化后的聚类中心
'''
m, n = np.shape(points)
cluster_centers = np.mat(np.zeros((k , n)))
# 1、随机选择一个样本点为第一个聚类中心
index = np.random.randint(0, m)
cluster_centers[0, ] = np.copy(points[index, ])
# 2、初始化一个距离的序列
d = [0.0 for _ in xrange(m)]
for i in xrange(1, k):
sum_all = 0
for j in xrange(m):
# 3、对每一个样本找到最近的聚类中心点
d[j] = nearest(points[j, ], cluster_centers[0:i, ])
# 4、将所有的最短距离相加
sum_all += d[j]
# 5、取得sum_all之间的随机值
sum_all *= random()
# 6、获得距离最远的样本点作为聚类中心点
for j, di in enumerate(d):
sum_all -= di
if sum_all > 0:
continue
cluster_centers[i] = np.copy(points[j, ])
break
return cluster_centers
def run_kmeanspp(data, k):
# 1、KMeans++的聚类中心初始化方法
print "\t---------- 1.K-Means++ generate centers ------------"
centroids = get_centroids(data, k)
# 2、聚类计算
print "\t---------- 2.kmeans ------------"
subCenter = kmeans(data, k, centroids)
# 3、保存所属的类别文件
print "\t---------- 3.save subCenter ------------"
save_result("sub_pp", subCenter)
# 4、保存聚类中心
print "\t---------- 4.save centroids ------------"
save_result("center_pp", centroids)
在上述代码中主要是初始化k个聚类中心，K-Means算法的核心程序如下所示：
# coding:UTF-8
'''
Date:20160923
@author: zhaozhiyong
'''
import numpy as np
def distance(vecA, vecB):
'''计算vecA与vecB之间的欧式距离的平方
input: vecA(mat)A点坐标
vecB(mat)B点坐标
output: dist[0, 0](float)A点与B点距离的平方
'''
dist = (vecA - vecB) * (vecA - vecB).T
return dist[0, 0]
def randCent(data, k):
'''随机初始化聚类中心
input: data(mat):训练数据
k(int):类别个数
output: centroids(mat):聚类中心
'''
n = np.shape(data)[1] # 属性的个数
centroids = np.mat(np.zeros((k, n))) # 初始化k个聚类中心
for j in xrange(n): # 初始化聚类中心每一维的坐标
minJ = np.min(data[:, j])
rangeJ = np.max(data[:, j]) - minJ
# 在最大值和最小值之间随机初始化
centroids[:, j] = minJ * np.mat(np.ones((k , 1))) + np.random.rand(k, 1) * rangeJ
return centroids
def kmeans(data, k, centroids):
'''根据KMeans算法求解聚类中心
input: data(mat):训练数据
k(int):类别个数
centroids(mat):随机初始化的聚类中心
output: centroids(mat):训练完成的聚类中心
subCenter(mat):每一个样本所属的类别
'''
m, n = np.shape(data) # m：样本的个数，n：特征的维度
subCenter = np.mat(np.zeros((m, 2))) # 初始化每一个样本所属的类别
change = True # 判断是否需要重新计算聚类中心
while change == True:
change = False # 重置
for i in xrange(m):
minDist = np.inf # 设置样本与聚类中心之间的最小的距离，初始值为争取穷
minIndex = 0 # 所属的类别
for j in xrange(k):
# 计算i和每个聚类中心之间的距离
dist = distance(data[i, ], centroids[j, ])
if dist < minDist:
minDist = dist
minIndex = j
# 判断是否需要改变
if subCenter[i, 0] <> minIndex: # 需要改变
change = True
subCenter[i, ] = np.mat([minIndex, minDist])
# 重新计算聚类中心
for j in xrange(k):
sum_all = np.mat(np.zeros((1, n)))
r = 0 # 每个类别中的样本的个数
for i in xrange(m):
if subCenter[i, 0] == j: # 计算第j个类别
sum_all += data[i, ]
r += 1
for z in xrange(n):
try:
centroids[j, z] = sum_all[0, z] / r
print r
except:
print " r is zero"
return subCenter
def save_result(file_name, source):
'''保存source中的结果到file_name文件中
input: file_name(string):文件名
source(mat):需要保存的数据
output:
'''
m, n = np.shape(source)
f = open(file_name, "w")
for i in xrange(m):
tmp = []
for j in xrange(n):
tmp.append(str(source[i, j]))
f.write("\t".join(tmp) + "\n")
f.close()
3.2、利用聚类结果生成新的图片
上述的过程中，对每一个像素点进行了聚类，最终利用聚类中心点的RGB值替换原图中每一个像素点的值，便得到了最终的分割后的图片，代码如下所示：
#coding:UTF-8
import Image as image
f_center = open("center_pp")
center = []
for line in f_center.readlines():
lines = line.strip().split("\t")
tmp = []
for x in lines:
tmp.append(int(float(x) * 256))
center.append(tuple(tmp))
print center
f_center.close()
fp = open("001.jpg", "rb")
im = image.open(fp)
# 新建一个图片
m, n = im.size
pic_new = image.new("RGB", (m, n))
f_sub = open("sub_pp")
i = 0
for line in f_sub.readlines():
index = float((line.strip().split("\t"))[0])
index_n = int(index)
pic_new.putpixel(((i/n),(i % n)),center[index_n])
i = i + 1
f_sub.close()
pic_new.save("result.jpg", "JPEG")
对于上述的圣托里尼的图片，取不同的k值，得到如下的一些结果：
- 原图
- k=3
- k=5
- k=7
- k=10
参考文章
机器学习应用：颜色量化实现示例(代码片段)
...用pythonOpenCV和scikit-learn实现了它。怎么运作的？k-means是机器学习中使用的聚类算法，其中一组数据点将被分类为“k”组。它适用于简单的距离计算。随机选择‘k‘个点（不一定来自数据集）。将每个数据点分配给最近的聚类。... 查看详情
机器学习聚类算法（实战）(代码片段)
聚类算法（实战）目录一、不同聚类算法的执行效果和所用时间二、准备工作（设置jupyternotebook中的字体大小样式等）三、Kmeans算法1、构建样本数据2、基于样本数据构建分类器3、绘制决策边界4、演示k-means算法... 查看详情
《分布式机器学习：算法理论与实践》——re
分布式机器学习：算法、理论与实践——【1】分布式机器学习：算法、理论与实践2）——【2】 《分布式机器学习：算法、理论与实践》——【RE】 查看详情
机器学习之k-means算法
前言 以下内容是个人学习之后的感悟，转载请注明出处~ 简介 在之前发表的线性回归、逻辑回归、神经网络、SVM支持向量机等算法都是监督学习算法，需要样本进行训练，且样本的类别是... 查看详情
机器学习笔记聚类算法及实践（k-means,dbscan,dpeak,spectral_clustering）
...这回我们来讲一讲聚类算法哈。首先，我们知道，主要的机器学习方法分为监督学习和无监督学习。监督学习主要是指我们已经给出了数据和分类，基于这些我们训练我们的分类器以期达到比较好的分类效果，比如我们前面讲的... 查看详情
python与机器学习
文章目录机器学习的目标机器学习分类pythonscikit-learnscikit-learn常用函数sklearn库的简介无监督学习聚类clustering欧式距离曼哈顿距离马氏距离夹角余弦降维k-means聚类算法DBSCAN密度聚类PCA方法及其应用非负矩阵分解（NMF）基... 查看详情
机器学习---算法---k-means算法
转自：https://blog.csdn.net/zhihua_oba/article/details/73832614 k-means算法详解主要内容k-means算法简介k-means算法详解k-means算法优缺点分析k-means算法改进算法k-means++1、k-means算法简介??k-means算法是一种聚类算法，所谓聚类，即根据相似性... 查看详情
机器学习算法原理详细推导与实现:k-means算法(代码片段)
【机器学习】算法原理详细推导与实现(六):k-means算法之前几个章节都是介绍有监督学习，这个章节介绍无监督学习，这是一个被称为k-means的聚类算法，也叫做k均值聚类算法。聚类算法在讲监督学习的时候，通常会画这样一张图... 查看详情
机器学习实战4：基于马尔科夫随机场的图像分割(附python代码)
...ython实现5.1计算能量函数5.2退火优化5.3效果展示0写在前面机器学习强基计划聚焦深度和广度，加深对机器学习模型的理解与应用。“深”在详细推导算法模型背后的数学原理；“广”在分析多个机器学习模型：决策树... 查看详情
机器学习k-means聚类算法与em算法
初始目的 将样本分成K个类，其实说白了就是求一个样本例的隐含类别y，然后利用隐含类别将x归类。由于我们事先不知道类别y，那么我们首先可以对每个样例假定一个y吧，但是怎么知道假定的对不对呢？怎样评价假定的好... 查看详情
机器学习k-means算法优化
K-Means算法优化学习目标1.Canopy算法配合初始聚类1.1Canopy算法配合初始聚类实现流程1.2Canopy算法的优缺点2.K-means++3.二分k-means4.k-medoids（k-中心聚类算法）5.Kernelk-means6.ISODATA7.MiniBatchK-Means8.小结学习目标知道K-means算法的... 查看详情
图像分割算法总结
...算法做个总结。 接触机器学习和深度学习时间已经不短了。期间看过各种相关知识但从未总结过。本文过后我会尽可能详细的从工程角度来总结，从传统机器学习算法，传统计算机视觉库算法... 查看详情
常用机器学习算法knn原理与实践
推荐两篇讲解与实践KNN比较好博客，感谢原作者总结http://blog.csdn.net/u012162613/article/details/41768407http://www.cnblogs.com/ybjourney/p/4702562.html 查看详情
基于k-means聚类算法的图像分割
参考技术A实际上，无论是从算法思想，还是具体实现上，K-means算法是一种很简单的算法。它属于无监督分类，通过按照一定的方式度量样本之间的相似度，通过迭代更新聚类中心，当聚类中心不再移动或移动差值小于阈值时，... 查看详情
《分布式机器学习：算法理论与实践》pdf+刘铁岩+资料学习
《分布式机器学习：算法、理论与实践》旨在全面介绍分布式机器学习的现状，深入分析其中的核心技术问题，并且讨论该领域未来的发展方向。下载：https://pan.baidu.com/s/1XeOGCQK5qWCba8VK0KU21w《分布式机器学习：算法、理论与实践... 查看详情
机器学习笔记之一深入浅出学习k-means算法
摘要：在数据挖掘中，K-Means算法是一种clusteranalysis的算法，其主要是来计算数据聚集的算法，主要通过不断地取离种子点最近均值的算法。在数据挖掘中，K-Means算法是一种clusteranalysis的算法，其主要是来计算数据聚集的算法，... 查看详情
机器学习算法与编程实践之中文文本分类
这周学习了机器学习算法与编程实践第二章——中文文本分类的部分内容。该章以文本挖掘为大背景，以文本分类算法为中心，详细介绍了中文文本分类项目的相关知识点。一、文本挖掘与文本分类的概念被普遍认可的文本挖掘... 查看详情
机器学习机器学习入门08-聚类与聚类算法k-means(代码片段)
时间过得很快，这篇文章已经是机器学习入门系列的最后一篇了。短短八周的时间里，虽然对机器学习并没有太多应用和熟悉的机会，但对于机器学习一些基本概念已经差不多有了一个提纲挈领的了解，如分类和回归，损失函数... 查看详情