background
Last week, a product manager at a company asked to change the color of the App’s theme according to the color of the user’s phone case. It is possible that this undisciplined demand angered the programmer, leading to a fight between the programmer and the product manager, who were both fired.
So how do you do this? First you need to get the dominant color in the image.
As an aside, there are still a few things you need to put on your desktop as a programmer.
KMeans algorithm
K-means clustering (K-means clustering) originated as a vector quantization method in signal processing, and is now more popular in data mining as a clustering method. The purpose of K-average clustering is to divide n points (which can be an observation or an instance of the sample) into K clusters, so that each point belongs to the cluster corresponding to the nearest mean (which is the cluster center), and take it as the standard of clustering. This problem will boil down to a matter of dividing the data space into Voronoi Cells.
The idea of KMeans algorithm is: given n data points {x1,x2… ,xn}, K cluster centers {A1, A2… ,aK} to minimize the sum of squares of distance between each data point and its nearest cluster center. This sum of squares of distance is called the objective function, denoted as Wn, and its mathematical expression is:
In this paper, KMeans algorithm is used to cluster image colors.
Basic process of the algorithm: 1. Initial K clustering centers. 2. All samples were classified according to their distance from the cluster center. 3. Recalculate the clustering center to determine whether to exit the condition: if the distance between two clustering centers is small enough, it is deemed to meet the exit condition; If you do not exit, go to Step 2.
Algorithm implementation
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(a)
{
// 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));
}
Copy the codeUsing this algorithm in Android to extract the dominant color:
A complete algorithm implementation can be found at: github.com/imageproces… It’s a typical KMeans algorithm.
In our algorithm, the default value of K is 5, or you can specify it yourself.
The above algorithm takes a long time in demo, but there is room for optimization. For example, you can use RxJava to do complex computing operations in the Computation thread and then switch back to the UI thread. Or you can use Coroutines like Kotlin’s to do complex computations and then switch back to the UI thread.
conclusion
There are other algorithms such as octree for extracting primary colors from an image, which can also be implemented in Android using the Palette API.
Cv4j was an image processing library developed with Hyperborean Fish and ME, with a pure Java implementation, and we had separated an Android version and a Java version.
If you want to watch this series of previous articles can access this corpus: www.jianshu.com/nb/10401400
Finally, as a programmer, you need to work out more.
Java and Android technology stack: weekly updates push original technical articles, welcome to scan the public qr code below and follow, look forward to growing with you and progress together.
