What does the integer in Kmeans in Image.quantize mean?

[AeroDEmi]

I'm having trouble understanding the Integer argument of Kmeans in Image.quantize

[Yay295]

So the C quantize function passes the kmeans value to the ImagingQuantize function,

Pillow/src/_imaging.c

Lines 1685 to 1700 in ca97370

	static PyObject *
	_quantize(ImagingObject *self, PyObject *args) {
	int colours = 256;
	int method = 0;
	int kmeans = 0;
	if (!PyArg_ParseTuple(args, "|iii", &colours, &method, &kmeans)) {
	return NULL;
	}
	if (!self->image->xsize || !self->image->ysize) {
	/* no content; return an empty image */
	return PyImagingNew(ImagingNew("P", self->image->xsize, self->image->ysize));
	}
	return PyImagingNew(ImagingQuantize(self->image, colours, method, kmeans));
	}

which passes it to the quantize or quantize2 functions,

Pillow/src/libImaging/Quant.c

Lines 1761 to 1782 in ca97370

	case 0:
	/* median cut */
	result = quantize(
	p,
	im->xsize * im->ysize,
	colors,
	&palette,
	&paletteLength,
	&newData,
	kmeans);
	break;
	case 1:
	/* maximum coverage */
	result = quantize2(
	p,
	im->xsize * im->ysize,
	colors,
	&palette,
	&paletteLength,
	&newData,
	kmeans);
	break;

which each do the same thing - check if it's 0, and if not, subtract 1 as they pass it to the k_means function.

Pillow/src/libImaging/Quant.c

Lines 1474 to 1476 in ca97370

	if (kmeans) {
	k_means(pixelData, nPixels, p, nPaletteEntries, qp, kmeans - 1);
	}

In the k_means function the value is now called threshold,

Pillow/src/libImaging/Quant.c

Lines 1158 to 1165 in ca97370

	static int
	k_means(
	Pixel *pixelData,
	uint32_t nPixels,
	Pixel *paletteData,
	uint32_t nPaletteEntries,
	uint32_t *qp,
	int threshold) {

and it determines the number of pixel changes that are allowed during each loop of the k-means quantization algorithm, ending when the number of changes is less than or equal to the threshold.

[Yay295]

It should probably be mentioned that dither is only used when palette is given, and if palette is given then colors, method, and kmeans are ignored.

[radarhere]

It should probably be mentioned that dither is only used when palette is given

#5836 is actually an open issue that expects this not to be the case.

if palette is given then... method... are ignored.

That's not quite true at the moment. Even if a palette is provided, an RGBA image with a method of MEDIANCUT or MAXCOVERAGE will raise an error.

[Yay295]

It looks like kmeans needs to be non-negative, but I don't see a check for that. I think it would get stuck in an infinite loop. It also seems like it might be possible to get stuck in a loop if kmeans is small and the number of changes in each loop never gets below that value.

[Yay295]

To answer your original question @AeroDEmi, the kmeans parameter determines how the quantization uses k-means clustering. If it's 0, then it doesn't use k-means clustering at all. Otherwise, kmeans should be an integer from 1 though the number of pixels in your image, with smaller values meaning that it will try harder to find the best color palette to use.

[AeroDEmi]

Awesome, Thank you!
Yeah it seems that kmeans=0 the n_colors is given by the count and if kmeans>0 it will find the different clusters.
FYI If you put something <0 it gets stuck in an infinite loop.

[radarhere]

I've created #7891 to fix the infinite loop.

Otherwise, your question has been answered?