How does the function imsegkmeans compute distance?

I know imsegkmeans can do color-based clustering but I wonder how it is implemented. Specifically, how does it compte the distance between two pixels in the image? What distance does it use? I tried stepping into the code to see details but found it used an internal function:

images.internal.ocvkmeans(X,k,NumAttempts,MaxIterations,Threshold)

And I couldn't step into the "ocvkmeans" function. Can anyone tell me what distance it uses for distance?

Thanks!

Answer 1

[Sumukh]

Hi @Tao Hu,

Kindly refer to the following MATLAB Answer where a staff member has answered that the “imgsegkmeans” and “kmeans” functions use similar algorithms under the hood:

https://www.mathworks.com/matlabcentral/answers/499445-kmeans-vs-imsegkmeans-what-the-difference?s_tid=srchtitle_site_search_7_imsegkmeans

The functionality of “imgsegkemeans” is to cluster the images based on the colour of each pixel of that image. As it uses k-means clustering to achieve this, you can refer to the following documentation where the algorithm for k-means clustering has been explained along with the way the distances are computed and used:

https://www.mathworks.com/help/releases/R2022b/stats/kmeans.html#buefthh-3

I hope this answers your query.

[Tao Hu]

Thanks but I'm sorry it does not answer my question. The above link only says:

Compute distances from each observation to c1. Denote the distance between cj and the observation m as d(xm,cj).

So what is the distance? That's my question. How does it measure the color distance between two pixel is what I want to know.

[DGM]

I would suspect that it's using euclidean distance (or squared euclidean distance), but my guess probably isn't very helpful. I don't find anything in the documentation, and like you found out, algkmeans() seems to just call a builtin.

[Star Strider]

I agree with @DGM. The Euclidean distance is the general default in various functions, even where options for the distance metric are provided. If it uses the same algorithm as the Statistics and Machine Learning Toolbox kmeans function (as I suspect it does), the various distance metrics, including the default, are described in the kmeans documentation section on Distance.

[DGM]

That, and Euclidean distance in LAB is already a canonical color distance metric (1976 Delta E), so it kind of makes a little extra sense to choose it as a default. That's not to say that we're always using LAB, but I don't know what other simple distance metric would have similar contextual relevance.

[Walter Roberson]

The code is very likely doing

Temp = reshape(TheImage, size(TheImage,1)*size(TheImage,2), []);
[IDX, Centers] = kmeans(Temp);

[DGM]

It reshapes the data, but it calls ocvkmeans()

[Label,NormCen] = images.internal.ocvkmeans(X,k,NumAttempts,MaxIterations,Threshold);

... which appears to be undocumented. IPT internals grabcut() and algkmeans() appear to be the only things that use it.