Hello,
I am still trying to understand the image compression example. What I understood so far:
- find top 16 colours to represent the image or find 16 data points which best represent the 16384 colors (128 x 128 pixels) in X_img using K=16 centroids
- X_img is a 2d matrix with shape (16384, 3) or 16384 x 3
- idx is a 1d vector with shape (16384, ) or 16384 x 1 representing one of 16 centroids
- each pixel of X_img will be assigned to the closest centroid (~ 16 x 3 colour room) stored in centroids
After running “run_kMeans” why do we run find_closest_centroids again? How does idx, centroids and X_recovered work together? I don’t understand centroids[idx, :]? Where is the assignment of the old 24bit colour to the new 4bit color?
centroids[idx, :] will return you an array of length (16384, 3), because it “recursively” takes the centroid for each pixel out of the centroids array.
Source: Week 1 lab 1 : About image compression - #2 by rmwkwok
Hello Daniel,
It just happens that I can’t open the lab on Coursera so I am unable to run code and verify my response, but if you have time, please make sure to check.
I will base my response on just reading the code.
Firstly, I think you were asking about section 4.2.
The run_kMeans function loops over two main steps: (i) get idx by assigning each sample to the closest centroid (ii) get a new set of centroids by averaging over their members. The problem is that after the last (ii), it leaves idx at the version that is associated with the old set of centroids. This is why we need one more find_closest_centroids to also get the new version of idx.
To understand, you need to know how “numpy array indexing” works. Please read the “Integer array indexing” section of this numpy tutorial.
Remember that idx is an integer array, so we are using this integer array to do array indexing. This is why the tutorial is relevant.
It is exactly centroids[idx, :].
Please read the tutorial first. Then compare the examples in the tutorial with centroids[idx, :]. When you compare, a few print to look at the content of arrays centroids and idx may be needed.
After you clear the tutorial, try to make sense of these statements
- the first element in
idx is the centroid ID of the first pixel
centroids is an array of the 4bit colors- we index the
centroids array with the first pixel’s centroid ID to get the first pixel’s new 4bit color.
- The first element of the resulting array of
centroids[idx, :] is the first pixel’s new 4bit color.
Cheers,
Raymond
Hi Raymond, thank you very much for your prompt answer! I think I could understand it now: We want to map a 16384 x 3 matrix with 1-16384 original colors (flattened) to a 16384 x 3 matrix with 1-16 colors only (flattened) using 16 centroids of clusters only (store 2^4=16 colors in 4 bits compared to store 255 x 255 x 255 = 16.581.375 colors in 24 bits with 2^24 combinations).
# Find the closest centroid of each pixel and store its number in idx (list of color clusters' centroids)
#
# X_img (ndarray): (16384, 3) or 16384 x 3 matrix for data points of original colors (flattened)
# - e.g. X_img[7,:]*255 --> rgb(228, 187, 114)
# centroids (ndarray): (16, 3) or 16 x 3 matrix for data points of color clusters' centroid
# - e.g. centroids[7,:]*255 --> ~ rgb(227, 190, 123)
# idx (ndarray): (16384,) or 16384 x 1 vector wheras each data point has its specific final centroid assigned
idx = find_closest_centroids(X_img, centroids)
# Replace each pixel with the color of the closest centroid
# or each data point of X_recovered (= X_img is restored with 0 - 15 data points only) will receive a new color
# from the closest centroid
#
# X_recovered (ndarray): (16384, 3) or 16384 x 3 matrix
# - e.g. X_recovered[0,:]*255 --> ~ rgb(227, 190, 123)
# - e.g. X_recovered[1,:]*255 --> ~ rgb(227, 190, 123)
# - e.g. X_recovered[2,:]*255 --> ~ rgb(227, 190, 123)
# - e.g. X_recovered[3,:]*255 --> ~ rgb(227, 190, 123)
# - e.g. X_recovered[4,:]*255 --> ~ rgb(227, 190, 123)
X_recovered = centroids[idx, :]
What I also found out is that their can be centroids of clusters with similar RGB values in the centroids matrix because in the picture there are for example black areas in the bottom left and top right.
This image compression example is really nice!
Thank you,
BR, Daniel
1 Like
Yes, except that if I understand you correctly, “1-16 colors” seems not corresponding to “1-16384 original colors” but “1-16.581.375 original colors”.
Yes, this is totally possible, especially when we use too many centroids. We are using 16 now, but why 16? Right?
Indeed! This example helped me learn K-means back then, too!
Cheers,
Raymond
I will fine tune my sentence:
We want to map a 16384 x 3 matrix with 1-16384 original colors (flattened) out of a 255 x 255 x 255 or 16.581.375 color’s space to a 16384 x 3 matrix with 1-16 colors only (flattened) using 16 centroids of clusters only (store 2^4=16 colors in 4 bits compared to store 255 x 255 x 255 = 16.581.375 colors in 24 bits with 2^24 combinations).
The 16 centroids are stored in 16384 data points (flattened, 128 x 128 colors) using their closest centroid.