1
$\begingroup$

I am using the image below.

noisy test image

I want to run a simple ClusteringComponents, using the KMeans method and EuclideanDistance DistanceFunction. Just to make sure there is no problem with the implementation of ClusteringComponents with images, I use the data of the Image and operate on the second level of the list obtained via ImageData. So my call to ClusteringComponents looks like this:

ClusteringComponents[
  ImageData[ImageResize[image, 500, Resampling -> "NearestLeft"]], 4, 
  2, Method -> "KMeans", 
  DistanceFunction -> EuclideanDistance] // Colorize

with image being the image below and the ImageResize is just here for reference, because the resolution in x-direction should already be 500. The result is not what I expect and what it should be when using EuclideanDistance:

output1

And here comes the surprising right result: As the KMeans-algorithm should be invariant under duplication operation, i.e. just instering every entry multiple times, the following code (which is due to ImageResize with Resampling->"NearestLeft" just inserting every entry 4 times) should give the same result as the code before just with twice the resolution:

ClusteringComponents[
  ImageData[ImageResize[image, 1000, Resampling -> "NearestLeft"]], 4, 
  2, Method -> "KMeans", 
  DistanceFunction -> EuclideanDistance] // Colorize

Output: output2

At least on my Mac (Mac OS X Mavericks, Mathematica 10.0.0) the results are surprisingly not the same, the second piece of code yielding the "right" result, while the first one is not. Am I missing something or is this a bug?

$\endgroup$
  • 1
    $\begingroup$ The k-means algorithm can get trapped in a local minimum during optimisation, so try using the "RandomSeed" option of ClusteringComponents to vary its initial guess. I found that "RandomSeed" -> 12345 makes the results the same in both cases. $\endgroup$ – Stephen Luttrell Sep 21 '14 at 17:23
2
$\begingroup$

Since my above comment appears to have answered the question, I'll upgrade it to an answer.

The k-means algorithm can get trapped in a local minimum during optimisation - see here - so try using the "RandomSeed" option of ClusteringComponents to vary its initial guess.

For instance, this gives the result that one would expect:

image = <your image>;

ClusteringComponents[
  ImageData[ImageResize[image, 500, Resampling -> "NearestLeft"]], 4, 
  2, Method -> "KMeans", DistanceFunction -> EuclideanDistance, 
  "RandomSeed" -> 12345] // Colorize
|improve this answer|||||
$\endgroup$
  • $\begingroup$ Thanks, I am actually feeling a little bit dumb, that I did not think of that myself. Can anyone think of a similar method that does not run into local optimums (I know that RandomSeed helps, but it has still a random component in it)? $\endgroup$ – Wizard Sep 22 '14 at 9:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.