IUPUI CSCI448Color-based image segmentation clustering

Perform k-means color clustering in two photos you will take, and detect skin regions. These two images should depict your hand on different backgrounds.

The scopes of this assignment: (1) to identify qualitatively/visually, what data (images) can make processing easier, including resolution, distance from target, background complexity, lighting, etc.; (2) to evaluate the computational challenges; (3) to study a simple clustering method in image region segmentation and be able to identify alternative solutions.  

Specifically:

0. take two photos of your hand in a setting you define (lighting, background, distance from camera), each with a different background.
1. implement “repetitive” k-means, as described below; use k = {2, 3, 5} (number of clusters).
2. cluster the image pixels with respect to color {R,G,B}, and display the corresponding k probability maps (for each of the three k-values).
3. threshold the probabilities to detect skin regions (binary outcome for each pixel): each pixel will have k (for a given k-value) probability values; for a pixel to be considered as skin region, the highest among its k probability values should correspond to the skin color cluster(s) and should be over a threshold.

Repetitive k-means:
Every execution of k-means is an iterative process, from start to convergence, using k randomly chosen cluster centroids during initialization: pick k random pixels, and use their {R,G,B}-values. Consider an execution (from initialization to convergence) as a single instance in a “bigger” repetitive process, where you will execute k-means several times, each with different randomly chosen centroids/pixel {R,G,B} values.  The output should be probability maps.

For example, for k=3, and 100 repetitions, the output should be three maps:
P(x belongs to cluster i) | {Rx,Gx,Bx} ), for i={1,2,3} ({Rx,Gx,Bx} are the chromatic values of x). That is, calculate P(x belongs to cluster 1) | {Rx,Gx,Bx} ), P(x belongs to cluster 2) | {Rx,Gx,Bx} ), and P(x belongs to cluster 3) | {Rx,Gx,Bx} ). After the 100 executions of k-means, each with different initialization, you will observe each pixel (the corresponding {R,G,B}) how many times it is assigned to cluster 1, to cluster 2, and to cluster 3. For each pixel, convert the frequency of assignment (to cluster 1, 2, and 3) into percentage: e.g., a% found in cluster 1, b% found in cluster 2, c% found in cluster 3, with a+b+c = 100.

Example: routine M = my_rep_kmeans(X, k)

step 0: Define k value

step 1: load image into variable X (of size h x w x 3) since it is a color image (you may have to convert the {R,G,B} values into double precision if they are in a different format, e.g., “uint8” in Matlab)

step 1.5: numofexec = 1 (counts how many times you execute k-means (see below); initialize to 1)

step 2: randomly choose k pixels and use their color as initialization in the color space; i.e., {C1, …, Ck}, where C1, …, Ck are 3×1 (or 1×3) matrices {R,G,B}-values. The random choice of k pixels can be based on cartesian coordinates: for each initial centroid, use the {R,G,B}-value of a randomly chosen pixel X(i,j) with coordinates i in [1,h] and j in [1,w].

step 3: perform k-means: Xout = somekmeansfun(X, k, [C1, …, Ck]) ==> notice the input: variable k, and random centroids. The output Xout should be of size h x w x 1. For more compact representation (see below), M( : , : , numofexec) = Xout.  See notes below.

step 3.5: align cluster numbers for consistency throughout all repetitions based on a fixed rule, e.g., sort clusters based on the {R,G,B}-values of their centroids (say, cluster 1 is the cluster with the lowest R-value, etc.)

step 4: numofexec = numofexec + 1; Repeat step 2 ; repeat step 3, repeat step 3.5. 

step 5: At the end, you will have a 3-dimensional matrix M: size(M) = [h, w, numofexec].  You can visualize the cluster assignments of each pixel X(i, j) as: v = M(i, j, 🙂 ==> size(v) = [1, numofexec]   (1 x numofexec) ==> plot it. For each pixel, you can calculate the frequency of its assignment to each cluster using v.

step 5: Calculate P1 = P( all hxw pixels belong to cluster 1), P2 = P( all hxw pixels belong to cluster 2), …, Pk = P( all hxw pixels belong to cluster k). Note that P1, P2, …, Pk are 2D matrices (hxw).

step 6: Display as color/heat maps the 2D matrices/probability maps P1, P2, …, Pk.

The whole procedure should be done three times, for the three different values of k =2, 3, 5.