UDN-企业互联网技术人气社区

板块导航

浏览  : 2049
回复  : 0

[其它] 机器学习算法实践——K-Means算法与图像分割

[复制链接]
泡泡兔的头像 楼主
发表于 2016-11-17 11:05:42 | 显示全部楼层 |阅读模式
本帖最后由 泡泡兔 于 2016-11-17 11:15 编辑

  一、理论准备

  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模块,主要是对图像的一些操作:

  模块的头文件
  1. import Image as image
复制代码

  打开图片
  1. fp = open("003.JPG", "rb")
  2. im = image.open(fp)
复制代码

  首先是以二进制文件的形式打开文件,再利用Image模块的open方法导入图片。

  对于如下的图片(圣托里尼):
7.png

  图片的属性
  1. im.format, im.size, im.mode
复制代码

  得到的结果为:JPEG (1600, 1067) RGB

  通道分离:
  1. r,g,b = im.split()
复制代码

  分割成三个通道,此时r,g,b分别为三个图像对象。

  取得像素点的值
  1. im.getpixel((4,4))
复制代码

  由于是RGB三通道的,因此此处的值为:(151, 169, 205)

  改变单个像素点的值
  1. im.putpixel(xy, color)
复制代码

  图像类型转换:
  1. im=im.convert("L")
复制代码

  由RGB的图像转成灰度的图像,其结果为:
6.png

  生成新的图像
  1. Image.new(mode, size)

  2. Image.new(mode, size, color)
复制代码

  如:newImg = Image.new(“GBA”,(640,480),(0,255,0))

  保存图片
  1. im.save("save.gif","GIF")
复制代码

  三、利用K-Means++算法进行图像分割

  3.1、利用K-Means++聚类

  在利用K-Means++算法进行图像分割时,将图像中的每一个像素点作为一个样本,对RGB图像来说,每个样本包括三维:(151, 169, 205),通过归一化,将每个通道的值压缩到[0,1]区间上。数据的导入和处理如下面程序所示:
  1. #coding:UTF-8
  2. import Image as image
  3. import numpy as np
  4. from KMeanspp import run_kmeanspp

  5. def load_data(file_path):
  6.     '''导入数据
  7.     input:  file_path(string):文件的存储位置
  8.     output: data(mat):数据
  9.     '''
  10.     f = open(file_path, "rb")  # 以二进制的方式打开图像文件
  11.     data = []
  12.     im = image.open(f)  # 导入图片
  13.     m, n = im.size  # 得到图片的大小
  14.     print m, n
  15.     for i in xrange(m):
  16.         for j in xrange(n):
  17.             tmp = []
  18.             x, y, z = im.getpixel((i, j))
  19.             tmp.append(x / 256.0)
  20.             tmp.append(y / 256.0)
  21.             tmp.append(z / 256.0)
  22.             data.append(tmp)
  23.     f.close()
  24.     return np.mat(data)
复制代码

  最终保存成矩阵的形式,矩阵的行为样本的个数,列为每一个通道的数值(RGB)。在利用K-Means++算法对样本进行聚类。主函数如下述代码所示:
  1. if __name__ == "__main__":
  2. k = 10#聚类中心的个数
  3. # 1、导入数据
  4. print "---------- 1.load data ------------"
  5. data = load_data("001.jpg")
  6. # 2、利用kMeans++聚类
  7. print "---------- 2.run kmeans++ ------------"
  8. run_kmeanspp(data, k)
  9. k表示的是聚类的个数。K-Means++程序的实现如下面程序所示:

  10. # coding:UTF-8
  11. '''
  12. Date:20160923
  13. @author: zhaozhiyong
  14. '''

  15. import numpy as np
  16. from random import random
  17. from KMeans import distance, kmeans, save_result
复制代码

  FLOAT_MAX = 1e100  # 设置一个较大的值作为初始化的最小的距离
  1. def nearest(point, cluster_centers):
  2.     '''计算point和cluster_centers之间的最小距离
  3.     input:  point(mat):当前的样本点
  4.         cluster_centers(mat):当前已经初始化的聚类中心
  5.     output: min_dist(float):点point和当前的聚类中心之间的最短距离
  6.     '''
  7.     min_dist = FLOAT_MAX
  8.     m = np.shape(cluster_centers)[0]  # 当前已经初始化的聚类中心的个数
  9.     for i in xrange(m):
  10.         # 计算point与每个聚类中心之间的距离
  11.         d = distance(point, cluster_centers[i, ])
  12.         # 选择最短距离
  13.         if min_dist > d:
  14.             min_dist = d
  15.     return min_dist

  16. def get_centroids(points, k):
  17.     '''KMeans++的初始化聚类中心的方法
  18.     input:  points(mat):样本
  19.         k(int):聚类中心的个数
  20.     output: cluster_centers(mat):初始化后的聚类中心
  21.     '''
  22.     m, n = np.shape(points)
  23.     cluster_centers = np.mat(np.zeros((k , n)))
  24.     # 1、随机选择一个样本点为第一个聚类中心
  25.     index = np.random.randint(0, m)
  26.     cluster_centers[0, ] = np.copy(points[index, ])
  27.     # 2、初始化一个距离的序列
  28.     d = [0.0 for _ in xrange(m)]

  29.     for i in xrange(1, k):
  30.         sum_all = 0
  31.         for j in xrange(m):
  32.             # 3、对每一个样本找到最近的聚类中心点
  33.             d[j] = nearest(points[j, ], cluster_centers[0:i, ])
  34.             # 4、将所有的最短距离相加
  35.             sum_all += d[j]
  36.         # 5、取得sum_all之间的随机值
  37.         sum_all *= random()
  38.         # 6、获得距离最远的样本点作为聚类中心点
  39.         for j, di in enumerate(d):
  40.             sum_all -= di
  41.             if sum_all > 0:
  42.                 continue
  43.             cluster_centers[i] = np.copy(points[j, ])
  44.             break
  45.     return cluster_centers

  46. def run_kmeanspp(data, k):
  47.     # 1、KMeans++的聚类中心初始化方法
  48.     print "\t---------- 1.K-Means++ generate centers ------------"
  49.     centroids = get_centroids(data, k)
  50.     # 2、聚类计算
  51.     print "\t---------- 2.kmeans ------------"
  52.     subCenter = kmeans(data, k, centroids)
  53.     # 3、保存所属的类别文件
  54.     print "\t---------- 3.save subCenter ------------"
  55.     save_result("sub_pp", subCenter)
  56.     # 4、保存聚类中心
  57.     print "\t---------- 4.save centroids ------------"
  58. save_result("center_pp", centroids)
复制代码

  在上述代码中主要是初始化k个聚类中心,K-Means算法的核心程序如下所示:
  1. # coding:UTF-8
  2. '''
  3. Date:20160923
  4. @author: zhaozhiyong
  5. '''
  6. import numpy as np

  7. def distance(vecA, vecB):
  8.     '''计算vecA与vecB之间的欧式距离的平方
  9.     input:  vecA(mat)A点坐标
  10.         vecB(mat)B点坐标
  11.     output: dist[0, 0](float)A点与B点距离的平方
  12.     '''
  13.     dist = (vecA - vecB) * (vecA - vecB).T
  14.     return dist[0, 0]

  15. def randCent(data, k):
  16.     '''随机初始化聚类中心
  17.     input:  data(mat):训练数据
  18.         k(int):类别个数
  19.     output: centroids(mat):聚类中心
  20.     '''
  21.     n = np.shape(data)[1]  # 属性的个数
  22.     centroids = np.mat(np.zeros((k, n)))  # 初始化k个聚类中心
  23.     for j in xrange(n):  # 初始化聚类中心每一维的坐标
  24.         minJ = np.min(data[:, j])
  25.         rangeJ = np.max(data[:, j]) - minJ
  26.         # 在最大值和最小值之间随机初始化
  27.         centroids[:, j] = minJ * np.mat(np.ones((k , 1))) + np.random.rand(k, 1) * rangeJ
  28.     return centroids

  29. def kmeans(data, k, centroids):
  30.     '''根据KMeans算法求解聚类中心
  31.     input:  data(mat):训练数据
  32.         k(int):类别个数
  33.         centroids(mat):随机初始化的聚类中心
  34.     output: centroids(mat):训练完成的聚类中心
  35.         subCenter(mat):每一个样本所属的类别
  36.     '''
  37.     m, n = np.shape(data)  # m:样本的个数,n:特征的维度
  38.     subCenter = np.mat(np.zeros((m, 2)))  # 初始化每一个样本所属的类别
  39.     change = True  # 判断是否需要重新计算聚类中心
  40.     while change == True:
  41.         change = False  # 重置
  42.         for i in xrange(m):
  43.             minDist = np.inf  # 设置样本与聚类中心之间的最小的距离,初始值为争取穷
  44.             minIndex = 0  # 所属的类别
  45.             for j in xrange(k):
  46.                 # 计算i和每个聚类中心之间的距离
  47.                 dist = distance(data[i, ], centroids[j, ])
  48.                 if dist < minDist:
  49.                     minDist = dist
  50.                     minIndex = j
  51.             # 判断是否需要改变
  52.             if subCenter[i, 0] <> minIndex:  # 需要改变
  53.                 change = True
  54.                 subCenter[i, ] = np.mat([minIndex, minDist])
  55.         # 重新计算聚类中心
  56.         for j in xrange(k):
  57.             sum_all = np.mat(np.zeros((1, n)))
  58.             r = 0  # 每个类别中的样本的个数
  59.             for i in xrange(m):
  60.                 if subCenter[i, 0] == j:  # 计算第j个类别
  61.                 sum_all += data[i, ]
  62.                 r += 1
  63.             for z in xrange(n):
  64.                 try:
  65.                     centroids[j, z] = sum_all[0, z] / r
  66.                     print r
  67.                 except:
  68.                     print " r is zero"   
  69.     return subCenter

  70. def save_result(file_name, source):
  71.     '''保存source中的结果到file_name文件中
  72.     input:  file_name(string):文件名
  73.         source(mat):需要保存的数据
  74.     output:
  75.     '''
  76.     m, n = np.shape(source)
  77.     f = open(file_name, "w")
  78.     for i in xrange(m):
  79.         tmp = []
  80.         for j in xrange(n):
  81.             tmp.append(str(source[i, j]))
  82.         f.write("\t".join(tmp) + "\n")
  83.     f.close()
复制代码

  3.2、利用聚类结果生成新的图片

  上述的过程中,对每一个像素点进行了聚类,最终利用聚类中心点的RGB值替换原图中每一个像素点的值,便得到了最终的分割后的图片,代码如下所示:
  1. #coding:UTF-8

  2. import Image as image

  3. f_center = open("center_pp")

  4. center = []
  5. for line in f_center.readlines():
  6.     lines = line.strip().split("\t")
  7.     tmp = []
  8.     for x in lines:
  9.         tmp.append(int(float(x) * 256))
  10.     center.append(tuple(tmp))
  11. print center
  12. f_center.close()

  13. fp = open("001.jpg", "rb")
  14. im = image.open(fp)
  15. # 新建一个图片
  16. m, n = im.size
  17. pic_new = image.new("RGB", (m, n))

  18. f_sub = open("sub_pp")
  19. i = 0
  20. for line in f_sub.readlines():
  21.     index = float((line.strip().split("\t"))[0])
  22.     index_n = int(index)
  23.     pic_new.putpixel(((i/n),(i % n)),center[index_n])
  24.     i = i + 1
  25. f_sub.close()

  26. pic_new.save("result.jpg", "JPEG")      
复制代码

  对于上述的圣托里尼的图片,取不同的k值,得到如下的一些结果:

  原图
5.png

  k=3
4.png

  k=5
3.png

  k=7
2.png

  k=10
11.png


原文作者:zhiyong_will 来源:http://blog.csdn.net/
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

关于我们
联系我们
  • 电话:010-86393388
  • 邮件:udn@yonyou.com
  • 地址:北京市海淀区北清路68号
移动客户端下载
关注我们
  • 微信公众号:yonyouudn
  • 扫描右侧二维码关注我们
  • 专注企业互联网的技术社区
版权所有:用友网络科技股份有限公司82041 京ICP备05007539号-11 京公网网备安1101080209224 Powered by Discuz!
快速回复 返回列表 返回顶部