• Random space: Generating 12 random integer in the range [0, 255] as one initial codeword or cluster centroid. Repeat this for all 256 centroids.
• Random sample: Generating one random integer in the range [0, numBlock), where numBlock is the number of 2x2 blocks in the color image. Use this number as the block number and copy the 12-D vector from this block as the initial centroid of one cluster. Repeat this 256 times.

• We loop over the rows of vectors array, i.e. we pick one row (vector from one 2x2 block) at a time, and calculate the Euclidean distances from this vector to all 256 centroids (recall the each centroid is one row in the codebook array). We assign this vector to the cluster with the smallest distance. One simple approach is to allocate one 1-D array with length numBlock to keep track the cluster's index (row number in the codebook) for all vectors (2x2 blocks).
• After all rows in the vectors array has been checked and assigned to their nearest clusters, the centroids needs be updated by add all vectors in each cluster and divided the sum (one 12-D array!) with the count of vectors in it (be careful to check if the count is zero and avoid divide-by-zero error).
• Repeat the previous etsps until maximum iterations is reached or the vectors' assignments not changing (this can be simply done by using extra array to store the assignment of vectors in the previous iteration and comparing the two assignment tacking arrays).

ccorra15 wrote:

• Can you go over the difference between a centroid and a cluster? This whole time I thought they were the same thing
• Is it possible for two or more clusters to be same (same 12 rgb values) due to choosing randomly?
• Can you give a hint on how to approach the decoding process?

I attached an example image. The clusters are the divisions shown while the centroid is the points in the middle. in our case we have 256 different clusters, hence 256 centroids. It is almost impossible for two centroids to have the same 12 RGB values if you assign each value randomly, using the random space method. ( we have 12 numbers and each is randomly choosing between 0 to 255.) Hope my response was helpful.

ccorra15 wrote:

So each rgb value is randomly chosen to create a vector to represent a cluster?

My program chooses a random vector (from the original image) and uses that as a cluster. Am I doing this wrong? I heard the professor say that our answers might be a little different due to the randomization and my answer compared to his sample result are very close.

He said we can either use random space which is randomly choosing the 12 RGB values for each or use a random sample, which randomly choosing one of the blocks and copies it for the centroid. It sounds like you used a random sample, either one works fine as long as your K-means clustering is working. I'm not sure which the proff. used to implement his program.

When choosing initial centroid randomly from samples, it's quite possible that two centroid having the same values. One simple approach to handle this issue is as follows: for the current cluster k, assign one random sample as its initial centroid ck, then compare ck with all previous clusters' centroids, re-assign a new random sample if it's the same as one previous centroid until reaching one re-assignment attempt limit (e.g. 5/10 times). The purpoe of this limit is to avoid infinite loop, i.e. the whole image only has a few different patterns.

From the sample results, you could see I actually implemented both approaches when generating initial codebook. :-)