static int computeKmeans()

in imagecore/image/colorpalette.cpp [359:418]
54 lines of code
13 McCabe index (conditional complexity)

static int computeKmeans(imagecore::ImageRGBA *frameImage, unsigned int numCluster, RGBA* colorPalette, double* colorPct) {
	SECURE_ASSERT(frameImage != NULL);
	SECURE_ASSERT(numCluster >= 2 && numCluster <= 10); // don't want large numbers for k
	unsigned int width = frameImage->getWidth();
	unsigned int height = frameImage->getHeight();
	vector<colorSample> samples;
	unsigned int framePitch;
	uint8_t* buffer = frameImage->lockRect(width, height, framePitch);

	// get all the samples (whose alpha value is > 128)
	for( unsigned int y = 0; y < height; y++ ) {
		for( unsigned int x = 0; x < width; x++ ) {
			const RGBA rgba = *(RGBA*)(&buffer[y * framePitch + x * 4]);
			if( rgba.a > 128 ) {
				float3 lab = ColorSpace::srgbToLab(ColorSpace::byteToFloat(rgba));
				colorSample sample(rgba, lab, -1, 0);
				samples.push_back(sample);
			}
		}
	}
	SECURE_ASSERT(samples.size() > 0 && samples.size() <= width * height);

	vector<colorSample> centroids = initializeCentroids(numCluster, samples);
	// main loop for k-means clustering
	for( unsigned int iteration = 0; iteration < MAX_ITERATIONS; iteration++ ) {
		sampleLabeling(samples, centroids);
		vector<colorSample> newCentroids = getCentroids(samples, numCluster);
		//if newCentroids are closed enough to old centroids, stop iteration
		bool closeEnough = true;
		for( unsigned int k = 0; k < numCluster; k++ ) {
			if( squaredDist(centroids[k], newCentroids[k]) > DELTA_LIMIT ) {
				closeEnough = false;
			}
		}
		if( closeEnough ) {
			break;
		}
		centroids = newCentroids;
	}

	sort(centroids.begin(), centroids.end());
	unsigned int totalSize = width * height;
	unsigned int numOutColors = 0;
	colorPalette[numOutColors] = centroids[numCluster-1].rgba;
	colorPct[numOutColors] = (double)centroids[numCluster - 1].clusterSize / totalSize;
	for( int k = numCluster - 2; k >= 0; k-- ) {
		double pct = (double)centroids[k].clusterSize / totalSize;
		if( pct < 0.001f)  {
			continue;
		}
		if( centroids[k].rgba == colorPalette[numOutColors] ) {
			colorPct[numOutColors] += pct;
		} else {
			numOutColors++;
			colorPalette[numOutColors] = centroids[k].rgba;
			colorPct[numOutColors] = pct;
		}
	}
	return numOutColors + 1;
}