当前位置:网站首页>Opencv4 machine learning (VI): principle and implementation of k-means

Opencv4 machine learning (VI): principle and implementation of k-means

2021-09-15 04:06:13 AI bacteria

Preface :

This column mainly combines OpenCV4, To realize some basic image processing operations 、 Classical machine learning algorithms ( such as K-Means、KNN、SVM、 Decision tree 、 Bayesian classifier, etc ), And common deep learning algorithms .

Series articles , Continuous updating :


One 、 Basic introduction

K-means, namely K mean value , It is an iterative clustering algorithm . Clustering is a process of classifying and organizing data members that are similar in some aspects , Clustering is a technology to discover this internal structure , Clustering technology is often called unsupervised learning .

K Mean clustering is the most famous partition clustering algorithm , Because of its simplicity and efficiency, it has become the most widely used of all clustering algorithms . Given a set of data points and the number of clusters required K,K Specified by the user ,K The mean value algorithm divides the data into K In cluster .

Two 、 Algorithm principle

For a given data set , adopt K-means The process of clustering is as follows :

  • initialization K Cluster centers .
  • Sample allocation . Place each sample in the set with its nearest category Center . Determine which center the sample is closest to through the set distance function , And put it into the corresponding sample . The distance function is generally : Euclidean distance 、 Manhattan distance 、 Minkowski distance 、 Hamming distance .
  • Update category Center . To assign samples in each set , Find the sample mean , And as the current category Center .
  • Judge the termination condition . Judge whether the category label reaches the convergence accuracy or the number of training rounds .

3、 ... and 、 Function interpretation

stay OpenCV4 in ,cv::kmeans Function implemented K-means, The algorithm finds K The center of a category , The input samples around the category are grouped .

cv::kmeans The function is defined as follows :

double cv::kmeans(InputArray data,  // sample 
				  int K, // Number of categories 
				  InputOutputArray bestLabels,  // Output integer array , The cluster category index used to store each sample 
				  TermCriteria criteria,  // Algorithm termination conditions : The maximum number of iterations or the required accuracy 
				  int attempts,  // Used to specify the number of times the algorithm is executed with different initial tags 
				  int flags,  // Method of initializing mean point 
				  OutputArray centers = noArray()  // The output matrix of the cluster center , Each cluster center occupies one row 
				  )

Four 、 Actual demonstration

Here is an example , use OpenCV Medium kmeans() Methods cluster two-dimensional coordinate point sets .

#include<iostream>
#include<opencv.hpp>
using namespace std;
using namespace cv;

int main() {
    
	const int MAX_CLUSTERS = 5; // Maximum number of categories 
	Scalar colorTab[] = {
       // Drawing colors 
						 Scalar(0, 0, 255),
						 Scalar(0, 255, 0),
						 Scalar(255, 100, 100),
						 Scalar(255, 0, 255),
						 Scalar(0, 255, 255)
						};

	Mat img(500, 500, CV_8UC3); // New canvas 
	img = Scalar::all(255); // Set the canvas to white 
	RNG rng(35345); // Random number generator 

	// Number of initialization categories 
	int clusterCount = rng.uniform(2, MAX_CLUSTERS + 1);
	// In the specified interval , Randomly generate an integer , Sample size 
	int sampleCount = rng.uniform(1, 1001);
	// Enter the sample matrix :sampleCount That's ok x1 Column ,  floating-point ,2 passageway 
	Mat points(sampleCount, 1, CV_32FC2);
	Mat labels; 
	// Number of cluster categories  <  Sample size 
	clusterCount = MIN(clusterCount, sampleCount); 

	// Clustering result index matrix 
	vector<Point2f> centers;

	// Randomly generate samples with multi Gaussian distribution 
	//for (int k = 0; k < clusterCount; k++) {
    
	Point center;
	center.x = rng.uniform(0, img.cols);
	center.y = rng.uniform(0, img.rows);

	// On the sample points Specify the assignment 
	Mat pointChunk = points.rowRange(0, sampleCount / clusterCount);
			
	// With center Centered , Generate random points with Gaussian distribution , Save the coordinate points in  pointChunk  in 
	rng.fill(pointChunk, RNG::NORMAL, Scalar(center.x, center.y), Scalar(img.cols*0.05, img.rows*0.05));
	// Upset points The value in 
	randShuffle(points, 1, &rng);

	// perform k-means
	double compactness = kmeans(points,  // sample 
								clusterCount, // Number of categories 
								labels,  // Output integer array , The cluster category index used to store each sample 
								TermCriteria(TermCriteria::EPS + TermCriteria::COUNT, 10, 1.0),  // Algorithm termination conditions : The maximum number of iterations or the required accuracy 
								3, // Used to specify the number of times the algorithm is executed with different initial tags 
								KMEANS_PP_CENTERS, // Method of initializing mean point 
								centers); // The output matrix of the cluster center , Each cluster center occupies one row 
			
	// Draw or output clustering results 
	for (int i = 0; i < sampleCount; i++) {
    
		int clusterIdx = labels.at<int>(i);

		Point ipt = points.at<Point2f>(i);
		circle(img, ipt, 2, colorTab[clusterIdx], FILLED, LINE_AA);
	}

	// Draw a circle with the cluster center as the center of the circle 
	for (int i = 0; i < (int)centers.size(); ++i) {
    
		Point2f c = centers[i];
		circle(img, c, 40, colorTab[i], 1, LINE_AA);
	}

	cout << "Compactness: " << compactness << endl;
	imshow("clusters", img);
	waitKey(0);

	return 0;
}

The clustering results are shown in the figure below :
 Insert picture description here


All the complete code for this column will be in my GitHub Update on warehouse , Welcome to learn :

Get into GitHub Warehouse , Click on star ( Red arrow ), Get dry goods at the first time :
 Insert picture description here

The best relationship is Each achievement , Everyone 「 Three even 」 Namely 【AI bacteria 】 The greatest power of creation , See you next time !

版权声明
本文为[AI bacteria]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/09/20210909111002623d.html

随机推荐