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

TyreeBaird 3年前
   <h2><strong>一、理论准备</strong></h2>    <h3><strong>1.1、图像分割</strong></h3>    <p>图像分割是图像处理中的一种方法,图像分割是指将一幅图像分解成若干互不相交区域的集合,其实质可以看成是一种像素的聚类过程。通常使用到的图像分割的方法可以分为:</p>    <ul>     <li> <p>基于边缘的技术</p> </li>     <li> <p>基于区域的技术</p> </li>    </ul>    <p>基于聚类算法的图像分割属于基于区域的技术。</p>    <h3><strong>1.2、K-Means算法</strong></h3>    <p>K-Means算法是基于距离相似性的聚类算法,通过比较样本之间的相似性,将形式的样本划分到同一个类别中,K-Means算法的基本过程为:</p>    <ul>     <li> <p>初始化常数 ,随机初始化k个聚类中心</p> </li>     <li> <p>重复计算以下过程,直到聚类中心不再改变</p>      <ul>       <li> <p>计算每个样本与每个聚类中心之间的相似度,将样本划分到最相似的类别中</p> </li>       <li> <p>计算划分到每个类别中的所有样本特征的均值,并将该均值作为每个类新的聚类中心</p> </li>      </ul> </li>     <li> <p>输出最终的聚类中心以及每个样本所属的类别</p> </li>    </ul>    <p>在K-Means算法中,需要随机初始化k个聚类中心,而K-Means算法对初始聚类中心的选取较为敏感,若选择的聚类中心不好,则得到的聚类结果会非常差,因此,对K-Means算法提出了很多的改进的方法,如K-Means++算法,在K-Means++算法中,希望初始化的k个聚类中心之间的距离尽可能的大,其具体过程为:</p>    <ul>     <li> <p>在数据集中随机选择一个样本点作为第一个初始化的聚类中心</p> </li>     <li> <p>选择出其余的聚类中心:</p>      <ul>       <li> <p>计算样本中的每一个样本点与已经初始化的聚类中心之间的距离,并选择其中最短的距离</p> </li>       <li> <p>以概率选择距离最大的样本作为新的聚类中心,重复上述过程,直到 个聚类中心都被确定</p> </li>      </ul> </li>     <li> <p>对k个初始化的聚类中心,利用K-Means算法计算最终的聚类中心。</p> </li>    </ul>    <h2><strong>二、实践准备</strong></h2>    <p>实践中使用Python作为开发语言,使用到的模块包括numpy和Image。numpy模块是python中矩阵计算使用最多的模块。</p>    <p>Image模块是PIL(Python Imaging Library)中的模块,对于Image模块,主要是对图像的一些操作:</p>    <ul>     <li> <p>模块的头文件</p> </li>    </ul>    <p>import Image as image</p>    <ul>     <li> <p>打开图片</p> </li>    </ul>    <pre>  <code class="language-python">fp = open("003.JPG", "rb")     im = image.open(fp)</code></pre>    <p>首先是以二进制文件的形式打开文件,再利用Image模块的open方法导入图片。</p>    <p>对于如下的图片(圣托里尼):</p>    <p><img src="https://simg.open-open.com/show/56b6995696cc9f24ba882fafaedd3b10.jpg"></p>    <ul>     <li> <p>图片的属性</p> </li>    </ul>    <p>im.format, im.size, im.mode</p>    <p>得到的结果为:JPEG (1600, 1067) RGB</p>    <ul>     <li> <p>通道分离:</p> </li>    </ul>    <p>r,g,b = im.split()</p>    <p>分割成三个通道,此时r,g,b分别为三个图像对象。</p>    <ul>     <li> <p>取得像素点的值</p> </li>    </ul>    <p>im.getpixel((4,4))</p>    <p>由于是RGB三通道的,因此此处的值为:(151, 169, 205)</p>    <ul>     <li> <p>改变单个像素点的值</p> </li>    </ul>    <p>im.putpixel(xy, color)</p>    <ul>     <li> <p>图像类型转换:</p> </li>    </ul>    <p>im=im.convert(&quot;L&quot;)</p>    <p>由RGB的图像转成灰度的图像,其结果为:</p>    <p><img src="https://simg.open-open.com/show/4509c6d0ecf0a9f04b5c571961ef9d7e.jpg"></p>    <ul>     <li> <p>生成新的图像</p> </li>    </ul>    <p>Image.new(mode, size)</p>    <p>Image.new(mode, size, color)</p>    <p>如:newImg = Image.new(“GBA”,(640,480),(0,255,0))</p>    <ul>     <li> <p>保存图片</p> </li>    </ul>    <p>im.save(&quot;save.gif&quot;,&quot;GIF&quot;)</p>    <h2><strong>三、利用K-Means++算法进行图像分割</strong></h2>    <h3><strong>3.1、利用K-Means++聚类</strong></h3>    <p>在利用K-Means++算法进行图像分割时,将图像中的每一个像素点作为一个样本,对RGB图像来说,每个样本包括三维:(151, 169, 205),通过归一化,将每个通道的值压缩到[0,1]区间上。数据的导入和处理如下面程序所示:</p>    <pre>  <code class="language-python">#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)</code></pre>    <p>最终保存成矩阵的形式,矩阵的行为样本的个数,列为每一个通道的数值(RGB)。在利用K-Means++算法对样本进行聚类。主函数如下述代码所示:</p>    <pre>  <code class="language-python">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)</code></pre>    <p>k表示的是聚类的个数。K-Means++程序的实现如下面程序所示:</p>    <pre>  <code class="language-python"># 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)</code></pre>    <p>在上述代码中主要是初始化k个聚类中心,K-Means算法的核心程序如下所示:</p>    <pre>  <code class="language-python"># 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()</code></pre>    <h3><strong>3.2、利用聚类结果生成新的图片</strong></h3>    <p>上述的过程中,对每一个像素点进行了聚类,最终利用聚类中心点的RGB值替换原图中每一个像素点的值,便得到了最终的分割后的图片,代码如下所示:</p>    <pre>  <code class="language-python">#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")</code></pre>    <p>对于上述的圣托里尼的图片,取不同的k值,得到如下的一些结果:</p>    <ul>     <li> <p>原图</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/56b6995696cc9f24ba882fafaedd3b10.jpg"></p>    <ul>     <li> <p>k=3</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/cc1ac32b6669e25c63f65a78dbce579b.jpg"></p>    <ul>     <li> <p>k=5</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/0856ca10e8d5f8dd24d8fc314d3f119e.jpg"></p>    <ul>     <li> <p>k=7</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/79f1801644300e62bc9620ff8fab422c.jpg"></p>    <ul>     <li> <p>k=10</p> </li>    </ul>    <p><img src="https://simg.open-open.com/show/6a31a6ee8ccf44643b35d78a1b91acc3.jpg"></p>    <h2><strong>参考文章</strong></h2>    <ul>     <li><a href="/misc/goto?guid=4959722987819879843" rel="nofollow,noindex">Kmeans聚类及图像分割</a></li>     <li><a href="/misc/goto?guid=4959722987914702765" rel="nofollow,noindex">聚类算法研究及在图像分割中的应用</a></li>     <li><a href="/misc/goto?guid=4959722987991742475" rel="nofollow,noindex">基于聚类算法的图像分割综述</a></li>     <li><a href="/misc/goto?guid=4959722988075842891" rel="nofollow,noindex">【图像处理】Python-Image 基本的图像处理操作</a></li>    </ul>    <p> </p>    <p>来自:http://blog.csdn.net/google19890102/article/details/52911835</p>    <p> </p>