备案控制台
开发者社区 人工智能 文章 正文

图像处理------K-Means算法演示

2015-07-24 1555
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： <p style="color: rgb(51, 51, 51); font-family: Arial; font-size: 14px; line-height: 26px;"><span style="font-size: 18px;">一：数学原理</span></p><p style="color: rgb(51, 51, 51); font-family: Arial; font

一：数学原理

K-Means算法的作者是MacQueen， 基本的数学原理很容易理解，假设有一个像素

数据集P。我们要根据值不同将它分为两个基本的数据集合Cluster1, Cluster2，使

用K-Means算法大致如下：

假设两个Cluster的RGB值分别为112,225,244和23,34,99则像素集合中的像素点

a(222,212,234), b(198,205,229), c(25,77,52),d(34,55,101)计算每个像素点与这

两个cluster中心点的欧几里德距离，则像素点a, b属于前面一个cluster， c,d属于

后面一个cluster。然后在根据(222+198)/2, (212+205)/2, (234+52)/2更新cluster

的RGB值，对后一个cluster做同样处理。然后再计算每个像素点到cluster中心点

的欧几里德距离。最终值没有变化则得到分类Cluster点集合。

二：算法基本流程


三：算法关键代码解析

初始化cluster中心点代码如下：

[java]  view plain copy
  1. Random random = new Random();  
  2. for (int i = 0; i < numOfCluster; i++)  
  3. {  
  4.     int randomNumber1 = random.nextInt(width);  
  5.     int randomNumber2 = random.nextInt(height);  
  6.     index = randomNumber2 * width + randomNumber1;  
  7.     ClusterCenter cc = new ClusterCenter(randomNumber1, randomNumber2, inPixels[index]);  
  8.     cc.setcIndex(i);  
  9.     clusterCenterList.add(cc);   
  10. }  

初始化所有像素点代码如下：

[java]  view plain copy
  1. // create all cluster point  
  2. for (int row = 0; row < height; ++row)  
  3. {  
  4.     for (int col = 0; col < width; ++col)  
  5.     {  
  6.         index = row * width + col;  
  7.         int color = inPixels[index];  
  8.         pointList.add(new ClusterPoint(row, col, color));  
  9.   
  10.     }  
  11. }  

计算两个像素点之间欧几里德距离的代码如下:

[java]  view plain copy
  1. // int pa = (p.getPixelColor() >> 24) & 0xff;  
  2. int pr = (p.getPixelColor() >> 16) & 0xff;  
  3. int pg = (p.getPixelColor() >> 8) & 0xff;  
  4. int pb = p.getPixelColor() & 0xff;  
  5. // int ca = (c.getPixelColor() >> 24) & 0xff;  
  6. int cr = (c.getPixelColor() >> 16) & 0xff;  
  7. int cg = (c.getPixelColor() >> 8) & 0xff;  
  8. int cb = c.getPixelColor() & 0xff;  
  9.   
  10. return Math.sqrt(Math.pow((pr - cr), 2.0) + Math.pow((pg - cg), 2.0) + Math.pow((pb - cb), 2.0));  
重新计算Cluster中心点RGB值的代码如下：

[java]  view plain copy
  1. private double[] reCalculateClusterCenters() {  
  2.       
  3.     // clear the points now  
  4.     for(int i=0; i<clusterCenterList.size(); i++)  
  5.     {  
  6.          clusterCenterList.get(i).setNumOfPoints(0);  
  7.     }  
  8.       
  9.     // recalculate the sum and total of points for each cluster  
  10.     double[] redSums = new double[3];  
  11.     double[] greenSum = new double[3];  
  12.     double[] blueSum = new double[3];  
  13.     for(int i=0; i<pointList.size(); i++)  
  14.     {  
  15.         int cIndex = (int)pointList.get(i).getClusterIndex();  
  16.         clusterCenterList.get(cIndex).addPoints();  
  17.         int ta = (pointList.get(i).getPixelColor() >> 24) & 0xff;  
  18.         int tr = (pointList.get(i).getPixelColor() >> 16) & 0xff;  
  19.         int tg = (pointList.get(i).getPixelColor() >> 8) & 0xff;  
  20.         int tb = pointList.get(i).getPixelColor() & 0xff;  
  21.         ta = 255;  
  22.         redSums[cIndex] += tr;  
  23.         greenSum[cIndex] += tg;  
  24.         blueSum[cIndex] += tb;  
  25.     }  
  26.       
  27.     double[] oldClusterCentersColors = new double[clusterCenterList.size()];  
  28.     for(int i=0; i<clusterCenterList.size(); i++)  
  29.     {  
  30.         double sum  = clusterCenterList.get(i).getNumOfPoints();  
  31.         int cIndex = clusterCenterList.get(i).getcIndex();  
  32.         int red = (int)(greenSum[cIndex]/sum);  
  33.         int green = (int)(greenSum[cIndex]/sum);  
  34.         int blue = (int)(blueSum[cIndex]/sum);  
  35.         System.out.println("red = " + red + " green = " + green + " blue = " + blue);  
  36.         int clusterColor = (255 << 24) | (red << 16) | (green << 8) | blue;  
  37.         clusterCenterList.get(i).setPixelColor(clusterColor);  
  38.         oldClusterCentersColors[i] = clusterColor;  
  39.     }  
  40.       
  41.     return oldClusterCentersColors;  
  42. }  

四：运行效果


五：K-Means算法源代码

[java]  view plain copy
  1. package com.gloomyfish.segmentation.kmeans;  
  2.   
  3. import java.awt.image.BufferedImage;  
  4. import java.util.ArrayList;  
  5. import java.util.List;  
  6. import java.util.Random;  
  7.   
  8. import com.gloomyfish.filter.study.AbstractBufferedImageOp;  
  9. import com.gloomyfish.segmentation.fuzzycmeans.ClusterPoint;  
  10.   
  11. public class KMeansProcessor extends AbstractBufferedImageOp {  
  12.     private List<ClusterCenter> clusterCenterList;  
  13.     private List<ClusterPoint> pointList;  
  14.       
  15.     private int numOfCluster;  
  16.       
  17.     public KMeansProcessor(int clusters)  
  18.     {  
  19.         this.numOfCluster = clusters;  
  20.         pointList = new ArrayList<ClusterPoint>();  
  21.         this.clusterCenterList = new ArrayList<ClusterCenter>();  
  22.     }  
  23.   
  24.     @Override  
  25.     public BufferedImage filter(BufferedImage src, BufferedImage dest) {  
  26.         // initialization the pixel data  
  27.         int width = src.getWidth();  
  28.         int height = src.getHeight();  
  29.         int[] inPixels = new int[width*height];  
  30.         src.getRGB( 0, 0, width, height, inPixels, 0, width );  
  31.         int index = 0;  
  32.           
  33.         //Create random points to use a the cluster center  
  34.         Random random = new Random();  
  35.         for (int i = 0; i < numOfCluster; i++)  
  36.         {  
  37.             int randomNumber1 = random.nextInt(width);  
  38.             int randomNumber2 = random.nextInt(height);  
  39.             index = randomNumber2 * width + randomNumber1;  
  40.             ClusterCenter cc = new ClusterCenter(randomNumber1, randomNumber2, inPixels[index]);  
  41.             cc.setcIndex(i);  
  42.             clusterCenterList.add(cc);   
  43.         }  
  44.           
  45.         // create all cluster point  
  46.         for (int row = 0; row < height; ++row)  
  47.         {  
  48.             for (int col = 0; col < width; ++col)  
  49.             {  
  50.                 index = row * width + col;  
  51.                 int color = inPixels[index];  
  52.                 pointList.add(new ClusterPoint(row, col, color));  
  53.   
  54.             }  
  55.         }  
  56.           
  57.         // initialize the clusters for each point  
  58.         double[] clusterDisValues = new double[clusterCenterList.size()];  
  59.         for(int i=0; i<pointList.size(); i++)  
  60.         {  
  61.             for(int j=0; j<clusterCenterList.size(); j++)  
  62.             {  
  63.                 clusterDisValues[j] = calculateEuclideanDistance(pointList.get(i), clusterCenterList.get(j));  
  64.             }  
  65.             pointList.get(i).setClusterIndex(getCloserCluster(clusterDisValues));  
  66.         }  
  67.           
  68.         // calculate the old summary  
  69.         // assign the points to cluster center  
  70.         // calculate the new cluster center  
  71.         // computation the delta value  
  72.         // stop condition--  
  73.         double[] oldClusterCenterColors = reCalculateClusterCenters();  
  74.         while(true)  
  75.         {  
  76.             stepClusters();  
  77.             double[] newClusterCenterColors = reCalculateClusterCenters();  
  78.             if(isStop(oldClusterCenterColors, newClusterCenterColors))  
  79.             {                 
  80.                 break;  
  81.             }   
  82.             else  
  83.             {  
  84.                 oldClusterCenterColors = newClusterCenterColors;  
  85.             }  
  86.         }  
  87.           
  88.         //update the result image  
  89.         dest = createCompatibleDestImage(src, null );  
  90.         index = 0;  
  91.         int[] outPixels = new int[width*height];         
  92.         for (int j = 0; j < pointList.size(); j++)  
  93.         {  
  94.             for (int i = 0; i < clusterCenterList.size(); i++)  
  95.             {  
  96.                 ClusterPoint p = this.pointList.get(j);  
  97.                 if (clusterCenterList.get(i).getcIndex() == p.getClusterIndex())  
  98.                 {  
  99.                     int row = (int)p.getX(); // row  
  100.                     int col = (int)p.getY(); // column  
  101.                     index = row * width + col;  
  102.                     outPixels[index] = clusterCenterList.get(i).getPixelColor();  
  103.                 }  
  104.             }  
  105.         }  
  106.           
  107.         // fill the pixel data  
  108.         setRGB( dest, 0, 0, width, height, outPixels );  
  109.         return dest;  
  110.     }  
  111.       
  112.     private boolean isStop(double[] oldClusterCenterColors, double[] newClusterCenterColors) {  
  113.         for(int i=0; i<oldClusterCenterColors.length; i++)  
  114.         {  
  115.             System.out.println("cluster " + i + " old : " + oldClusterCenterColors[i] + ", new : " + newClusterCenterColors[i]);  
  116.             if(oldClusterCenterColors[i]  != newClusterCenterColors[i])   
  117.             {  
  118.                 return false;  
  119.             }  
  120.         }  
  121.         System.out.println();  
  122.         return true;  
  123.     }  
  124.   
  125.     /** 
  126.      * update the cluster index by distance value 
  127.      */  
  128.     private void stepClusters()   
  129.     {  
  130.         // initialize the clusters for each point  
  131.         double[] clusterDisValues = new double[clusterCenterList.size()];  
  132.         for(int i=0; i<pointList.size(); i++)  
  133.         {  
  134.             for(int j=0; j<clusterCenterList.size(); j++)  
  135.             {  
  136.                 clusterDisValues[j] = calculateEuclideanDistance(pointList.get(i), clusterCenterList.get(j));  
  137.             }  
  138.             pointList.get(i).setClusterIndex(getCloserCluster(clusterDisValues));  
  139.         }  
  140.           
  141.     }  
  142.   
  143.     /** 
  144.      * using cluster color of each point to update cluster center color 
  145.      *  
  146.      * @return 
  147.      */  
  148.     private double[] reCalculateClusterCenters() {  
  149.           
  150.         // clear the points now  
  151.         for(int i=0; i<clusterCenterList.size(); i++)  
  152.         {  
  153.              clusterCenterList.get(i).setNumOfPoints(0);  
  154.         }  
  155.           
  156.         // recalculate the sum and total of points for each cluster  
  157.         double[] redSums = new double[3];  
  158.         double[] greenSum = new double[3];  
  159.         double[] blueSum = new double[3];  
  160.         for(int i=0; i<pointList.size(); i++)  
  161.         {  
  162.             int cIndex = (int)pointList.get(i).getClusterIndex();  
  163.             clusterCenterList.get(cIndex).addPoints();  
  164.             int ta = (pointList.get(i).getPixelColor() >> 24) & 0xff;  
  165.             int tr = (pointList.get(i).getPixelColor() >> 16) & 0xff;  
  166.             int tg = (pointList.get(i).getPixelColor() >> 8) & 0xff;  
  167.             int tb = pointList.get(i).getPixelColor() & 0xff;  
  168.             ta = 255;  
  169.             redSums[cIndex] += tr;  
  170.             greenSum[cIndex] += tg;  
  171.             blueSum[cIndex] += tb;  
  172.         }  
  173.           
  174.         double[] oldClusterCentersColors = new double[clusterCenterList.size()];  
  175.         for(int i=0; i<clusterCenterList.size(); i++)  
  176.         {  
  177.             double sum  = clusterCenterList.get(i).getNumOfPoints();  
  178.             int cIndex = clusterCenterList.get(i).getcIndex();  
  179.             int red = (int)(greenSum[cIndex]/sum);  
  180.             int green = (int)(greenSum[cIndex]/sum);  
  181.             int blue = (int)(blueSum[cIndex]/sum);  
  182.             System.out.println("red = " + red + " green = " + green + " blue = " + blue);  
  183.             int clusterColor = (255 << 24) | (red << 16) | (green << 8) | blue;  
  184.             clusterCenterList.get(i).setPixelColor(clusterColor);  
  185.             oldClusterCentersColors[i] = clusterColor;  
  186.         }  
  187.           
  188.         return oldClusterCentersColors;  
  189.     }  
  190.       
  191.       
  192.   
  193.     /** 
  194.      *  
  195.      * @param clusterDisValues 
  196.      * @return 
  197.      */  
  198.     private double getCloserCluster(double[] clusterDisValues)  
  199.     {  
  200.         double min = clusterDisValues[0];  
  201.         int clusterIndex = 0;  
  202.         for(int i=0; i<clusterDisValues.length; i++)  
  203.         {  
  204.             if(min > clusterDisValues[i])  
  205.             {  
  206.                 min = clusterDisValues[i];  
  207.                 clusterIndex = i;  
  208.             }  
  209.         }  
  210.         return clusterIndex;  
  211.     }  
  212.   
  213.     /** 
  214.      *  
  215.      * @param point 
  216.      * @param cluster 
  217.      * @return distance value 
  218.      */  
  219.     private double calculateEuclideanDistance(ClusterPoint p, ClusterCenter c)   
  220.     {  
  221.         // int pa = (p.getPixelColor() >> 24) & 0xff;  
  222.         int pr = (p.getPixelColor() >> 16) & 0xff;  
  223.         int pg = (p.getPixelColor() >> 8) & 0xff;  
  224.         int pb = p.getPixelColor() & 0xff;  
  225.         // int ca = (c.getPixelColor() >> 24) & 0xff;  
  226.         int cr = (c.getPixelColor() >> 16) & 0xff;  
  227.         int cg = (c.getPixelColor() >> 8) & 0xff;  
  228.         int cb = c.getPixelColor() & 0xff;  
  229.           
  230.         return Math.sqrt(Math.pow((pr - cr), 2.0) + Math.pow((pg - cg), 2.0) + Math.pow((pb - cb), 2.0));  
  231.     }  
  232.   
  233. }  
文章标签：
算法
Java
计算机视觉
关键词：
k-means算法
算法k-means
图像处理算法
算法图像处理
图像处理k-means算法
毛毛虫的爹
目录
相关文章
爱吃糖的范同学
|
1天前
|
数据采集 机器学习/深度学习 人工智能
【机器学习】在使用K-means算法之前，如何预处理数据？
【5月更文挑战第12天】【机器学习】在使用K-means算法之前，如何预处理数据？
爱吃糖的范同学
11 3
爱吃糖的范同学
|
1天前
|
机器学习/深度学习 算法 数据可视化
【机器学习】比较分层聚类（Hierarchical Clustering）和K-means聚类算法
【5月更文挑战第12天】【机器学习】比较分层聚类（Hierarchical Clustering）和K-means聚类算法
爱吃糖的范同学
9 2
爱吃糖的范同学
|
3天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】在使用K-means聚类算法时，如何选择K的值？
【5月更文挑战第11天】【机器学习】在使用K-means聚类算法时，如何选择K的值？
爱吃糖的范同学
81 9
爱吃糖的范同学
|
3天前
|
机器学习/深度学习 算法 数据挖掘
【机器学习】为什么K-means算法使用欧式距离度量？
【5月更文挑战第11天】【机器学习】为什么K-means算法使用欧式距离度量？
爱吃糖的范同学
74 8
爱吃糖的范同学
|
3天前
|
机器学习/深度学习 算法 数据可视化
【机器学习】描述K-means算法的步骤
【5月更文挑战第11天】【机器学习】描述K-means算法的步骤
爱吃糖的范同学
69 10
爱吃糖的范同学
|
3天前
|
机器学习/深度学习 人工智能 算法
【机器学习】K-means和KNN算法有什么区别？
【5月更文挑战第11天】【机器学习】K-means和KNN算法有什么区别？
爱吃糖的范同学
53 8
桃李春风一杯酒
|
14天前
|
机器学习/深度学习 算法 数据挖掘
【Python 机器学习专栏】K-means 聚类算法在 Python 中的实现
【4月更文挑战第30天】K-means 是一种常见的聚类算法，用于将数据集划分为 K 个簇。其基本流程包括初始化簇中心、分配数据点、更新簇中心并重复此过程直到收敛。在 Python 中实现 K-means 包括数据准备、定义距离函数、初始化、迭代和输出结果。虽然算法简单高效，但它需要预先设定 K 值，且对初始点选择敏感，可能陷入局部最优。广泛应用在市场分析、图像分割等场景。理解原理与实现对应用聚类分析至关重要。
桃李春风一杯酒
15 1
拓端数据部落
|
15天前
|
机器学习/深度学习 数据采集 SQL
R语言K-Means(K均值聚类）和层次聚类算法对微博用户特征数据研究
R语言K-Means(K均值聚类）和层次聚类算法对微博用户特征数据研究
拓端数据部落
19 0
拓端数据部落
|
15天前
|
算法 数据可视化 数据挖掘
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
数据分享|R语言改进的K-MEANS(K-均值)聚类算法分析股票盈利能力和可视化
拓端数据部落
19 0
拓端数据部落
|
16天前
|
数据采集 机器学习/深度学习 存储
MATLAB用改进K-Means(K-均值)聚类算法数据挖掘高校学生的期末考试成绩
MATLAB用改进K-Means(K-均值)聚类算法数据挖掘高校学生的期末考试成绩
拓端数据部落
19 0

热门文章

最新文章

  • 1
    MVVM模型，虚拟DOM和diff算法
  • 2
    使用Python实现图像处理中的边缘检测算法
  • 3
    利用机器学习算法改善电商推荐系统的效率
  • 4
    使用python实现FP-Growth算法
  • 5
    探索数据结构在算法优化中的关键作用
  • 6
    Python基础算法解析：支持向量机（SVM）
  • 7
    视觉智能平台常见问题之算法私有化部署交付给公司内部运行如何解决
  • 8
    视觉智能平台常见问题之其他算法定制化开发如何解决
  • 9
    Opencv(C++)学习系列---Canny边缘检测算法
  • 10
    基于yolov2深度学习网络的视频手部检测算法matlab仿真
  • 1
    MVVM模型，虚拟DOM和diff算法
    197
  • 2
    Opencv（C++）学习系列---Laplacian拉普拉斯边缘检测算法
    72
  • 3
    Opencv(C++)学习系列---Canny边缘检测算法
    78
  • 4
    使用python实现FP-Growth算法
    90
  • 5
    使用C语言实现DES算法代码
    35
  • 6
    ICLR 2024：近似最优的最大损失函数量子优化算法
    43
  • 7
    基于yolov2深度学习网络的视频手部检测算法matlab仿真
    73
  • 8
    Python基础算法解析：支持向量机（SVM）
    86
  • 9
    探索数据结构在算法优化中的关键作用
    85
  • 10
    视觉智能平台常见问题之算法私有化部署交付给公司内部运行如何解决
    84

    • 相关课程

    更多
  • 相册服务中的故事生成算法介绍
  • Go语言核心编程 - 数据结构和算法
  • 神经网络概览及算法详解

    • 相关电子书

    更多
  • 数据+算法定义新世界
  • 袋鼠云基于实时计算的反黄牛算法
  • Alink：基于Apache Flink的算法平台

    • 相关实验场景

    更多
  • TLS1.3的后量子算法集成
  • RSA非对称加密算法
    • 下一篇
    2024年阿里云免费云服务器及学生云服务器申请教程参考