酷酷的.jpg
背景
上周，某公司的产品经理提了一个需求：根据用户手机壳颜色来改变 App 主题颜色。可能是由于这天马行空的需求激怒了程序员，导致程序员和产品经理打了起来，最后双双被公司开除。
那如何实现这个功能呢？首先需要获取图像中的主色。
插一句题外话，作为程序员在桌面上还是要有一些必备的东西需要放的。
程序员桌面必备杯垫.JPG
KMeans 算法
k-平均算法（英文：k-means clustering）源于信号处理中的一种向量量化方法，现在则更多地作为一种聚类分析方法流行于数据挖掘领域。k-平均聚类的目的是：把 n 个点（可以是样本的一次观察或一个实例）划分到k个聚类中，使得每个点都属于离他最近的均值（此即聚类中心）对应的聚类，以之作为聚类的标准。这个问题将归结为一个把数据空间划分为Voronoi cells的问题。
KMeans 算法思想为：给定n个数据点{x1,x2,…,xn},找到K个聚类中心{a1,a2,…,aK},使得每个数据点与它最近的聚类中心的距离平方和最小,并将这个距离平方和称为目标函数,记为Wn,其数学表达式为：
KMeans.png
本文使用 KMeans 算法对图像颜色做聚类。
算法基本流程：
1、初始的 K 个聚类中心。
2、按照距离聚类中心的远近对所有样本进行分类。
3、重新计算聚类中心，判断是否退出条件：
两次聚类中心的距离足够小视为满足退出条件；
不退出则重新回到步骤2。
算法实现
public List<Scalar> extract(ColorProcessor processor) {
// initialization the pixel data
int width = processor.getWidth();
int height = processor.getHeight();
byte[] R = processor.getRed();
byte[] G = processor.getGreen();
byte[] B = processor.getBlue();
//Create random points to use a the cluster center
Random random = new Random();
int index = 0;
for (int i = 0; i < numOfCluster; i++)
{
int randomNumber1 = random.nextInt(width);
int randomNumber2 = random.nextInt(height);
index = randomNumber2 * width + randomNumber1;
ClusterCenter cc = new ClusterCenter(randomNumber1, randomNumber2, R[index]&0xff, G[index]&0xff, B[index]&0xff);
cc.cIndex = i;
clusterCenterList.add(cc);
}
// create all cluster point
for (int row = 0; row < height; ++row)
{
for (int col = 0; col < width; ++col)
{
index = row * width + col;
pointList.add(new ClusterPoint(row, col, R[index]&0xff, G[index]&0xff, B[index]&0xff));
}
}
// initialize the clusters for each point
double[] clusterDisValues = new double[clusterCenterList.size()];
for(int i=0; i<pointList.size(); i++)
{
for(int j=0; j<clusterCenterList.size(); j++)
{
clusterDisValues[j] = calculateEuclideanDistance(pointList.get(i), clusterCenterList.get(j));
}
pointList.get(i).clusterIndex = (getCloserCluster(clusterDisValues));
}
// calculate the old summary
// assign the points to cluster center
// calculate the new cluster center
// computation the delta value
// stop condition--
double[][] oldClusterCenterColors = reCalculateClusterCenters();
int times = 10;
while(true)
{
stepClusters();
double[][] newClusterCenterColors = reCalculateClusterCenters();
if(isStop(oldClusterCenterColors, newClusterCenterColors))
{
break;
}
else
{
oldClusterCenterColors = newClusterCenterColors;
}
if(times > 10) {
break;
}
times++;
}
//update the result image
List<Scalar> colors = new ArrayList<Scalar>();
for(ClusterCenter cc : clusterCenterList) {
colors.add(cc.color);
}
return colors;
}
private boolean isStop(double[][] oldClusterCenterColors, double[][] newClusterCenterColors) {
boolean stop = false;
for (int i = 0; i < oldClusterCenterColors.length; i++) {
if (oldClusterCenterColors[i][0] == newClusterCenterColors[i][0] &&
oldClusterCenterColors[i][1] == newClusterCenterColors[i][1] &&
oldClusterCenterColors[i][2] == newClusterCenterColors[i][2]) {
stop = true;
break;
}
}
return stop;
}
/**
* update the cluster index by distance value
*/
private void stepClusters()
{
// initialize the clusters for each point
double[] clusterDisValues = new double[clusterCenterList.size()];
for(int i=0; i<pointList.size(); i++)
{
for(int j=0; j<clusterCenterList.size(); j++)
{
clusterDisValues[j] = calculateEuclideanDistance(pointList.get(i), clusterCenterList.get(j));
}
pointList.get(i).clusterIndex = (getCloserCluster(clusterDisValues));
}
}
/**
* using cluster color of each point to update cluster center color
*
* @return
*/
private double[][] reCalculateClusterCenters() {
// clear the points now
for(int i=0; i<clusterCenterList.size(); i++)
{
clusterCenterList.get(i).numOfPoints = 0;
}
// recalculate the sum and total of points for each cluster
double[] redSums = new double[numOfCluster];
double[] greenSum = new double[numOfCluster];
double[] blueSum = new double[numOfCluster];
for(int i=0; i<pointList.size(); i++)
{
int cIndex = (int)pointList.get(i).clusterIndex;
clusterCenterList.get(cIndex).numOfPoints++;
int tr = pointList.get(i).pixelColor.red;
int tg = pointList.get(i).pixelColor.green;
int tb = pointList.get(i).pixelColor.blue;
redSums[cIndex] += tr;
greenSum[cIndex] += tg;
blueSum[cIndex] += tb;
}
double[][] oldClusterCentersColors = new double[clusterCenterList.size()][3];
for(int i=0; i<clusterCenterList.size(); i++)
{
double sum = clusterCenterList.get(i).numOfPoints;
int cIndex = clusterCenterList.get(i).cIndex;
int red = (int)(greenSum[cIndex]/sum);
int green = (int)(greenSum[cIndex]/sum);
int blue = (int)(blueSum[cIndex]/sum);
clusterCenterList.get(i).color = new Scalar(red, green, blue);
oldClusterCentersColors[i][0] = red;
oldClusterCentersColors[i][0] = green;
oldClusterCentersColors[i][0] = blue;
}
return oldClusterCentersColors;
}
/**
*
* @param clusterDisValues
* @return
*/
private double getCloserCluster(double[] clusterDisValues)
{
double min = clusterDisValues[0];
int clusterIndex = 0;
for(int i=0; i<clusterDisValues.length; i++)
{
if(min > clusterDisValues[i])
{
min = clusterDisValues[i];
clusterIndex = i;
}
}
return clusterIndex;
}
/**
*
* @param p
* @param c
* @return distance value
*/
private double calculateEuclideanDistance(ClusterPoint p, ClusterCenter c)
{
int pr = p.pixelColor.red;
int pg = p.pixelColor.green;
int pb = p.pixelColor.blue;
int cr = c.color.red;
int cg = c.color.green;
int cb = c.color.blue;
return Math.sqrt(Math.pow((pr - cr), 2.0) + Math.pow((pg - cg), 2.0) + Math.pow((pb - cb), 2.0));
}
在 Android 中使用该算法来提取主色：
demo1.png
demo2.png
完整的算法实现可以在：https://github.com/imageprocessor/cv4j/blob/master/cv4j/src/main/java/com/cv4j/core/pixels/PrincipalColorExtractor.java 找到，它是一个典型的 KMeans 算法。
我们的算法中，K默认值是5，当然也可以自己指定。
以上算法目前在 demo 上耗时蛮久，不过可以有优化空间。例如，可以使用 RxJava 在 computation 线程中做复杂的计算操作然后切换回ui线程。亦或者可以使用类似 Kotlin 的 Coroutines 来做复杂的计算操作然后切换回ui线程。
总结
提取图像中的主色，还有其他算法例如八叉树等，在 Android 中也可以使用 Palette 的 API来实现。
cv4j 是gloomyfish和我一起开发的图像处理库，纯java实现，我们已经分离了一个Android版本和一个Java版本。
如果您想看该系列先前的文章可以访问下面的文集：
https://www.jianshu.com/nb/10401400
最后提醒一句，作为程序员，还是要多健身。
