# Homework 5

This notebook includes both coding and written questions. Please hand in this notebook file with all the outputs and your answers to the written questions.

This assignment covers K-Means and HAC methods for clustering.

The autoreload extension is already loaded. To reload it, use:
%reload_ext autoreload

## Introduction

In this assignment, you will use clustering algorithms to segment images. You will then use these segmentations to identify foreground and background objects.

• Clustering algorithms: Implement K-Means clustering and Hierarchical Agglomerative Clustering.
• Pixel-level features: Implement a feature vector that combines color and position information and implement feature normalization.
• Quantitative Evaluation: Evaluate segmentation algorithms with a variety of parameter settings by comparing your computed segmentations against a dataset of ground-truth segmentations.

1. 聚类算法的实现：实现K-Means聚类和层次凝聚聚类
2. 像素级特征：实现结合颜色和位置信息的特征向量以及实现特征归一化。
3. 量化评估：通过将计算出来的分割结果与GroundTruth进行比较，评估具有各种参数设置的分割算法。

## 1 Clustering Algorithms (40 points)

### 1.1 K-Means Clustering (20 points)

As discussed in class, K-Means is one of the most popular clustering algorithms. We have provided skeleton code for K-Means clustering in the file segmentation.py. Your first task is to finish implementing kmeans in segmentation.py. This version uses nested for loops to assign points to the closest centroid and compute new mean of each cluster.

K-Means Wiki

k-平均算法

K-means的步骤：

1. 随机初始化聚类中心
2. 将点分配给最近的中心
3. 计算每个聚类的新的中心
4. 如果聚类的分配不再变动则停止
5. 从第二步继续循环
迭代次数 8
kmeans running time: 0.061108 seconds.

We can use numpy functions and broadcasting to make kmeans faster. Implement kmeans_fast in segmentation.py. This should run at least 10 times faster than the previous implementation.

• np.repeat and np.argmin 有帮助
• 还有一种思路就是向量化了，不做迭代而是放在矩阵里去计算。
kmeans running time: 0.003889 seconds.
15.714531 times faster!

### 1.2 Hierarchical Agglomerative Clustering (20 points)

Another simple clustering algorithm is Hieararchical Agglomerative Clustering, which is somtimes abbreviated as HAC. In this algorithm, each point is initially assigned to its own cluster. Then cluster pairs are merged until we are left with the desired number of predetermined clusters (see Algorithm 1).

Implement hiererachical_clustering in segmentation.py.

1. 初始化每个点为一个簇
2. 迭代直到只剩下K个簇：
• 计算所有簇与簇之间（簇对）的距离
• 合并最近的两个簇

hierarchical_clustering函数将按照这个思路实现。

** 博客推荐 **

Numpy中的距离度量函数

hierarchical_clustering running time: 0.191211 seconds.

• 第一个是善用向量化，用矩阵来计算问题
• 第二个就是善用numpy提供的函数，解决一些需要搜索遍历的问题

## 2 Pixel-Level Features (30 points)

Before we can use a clustering algorithm to segment an image, we must compute some feature vectore for each pixel. The feature vector for each pixel should encode the qualities that we care about in a good segmentation. More concretely, for a pair of pixels $p_i$ and $p_j$ with corresponding feature vectors $f_i$ and $f_j$, the distance between $f_i$ and $f_j$ should be small if we believe that $p_i$ and $p_j$ should be placed in the same segment and large otherwise.

### 2.1 Color Features (15 points)

One of the simplest possible feature vectors for a pixel is simply the vector of colors for that pixel. Implement color_features in segmentation.py. Output should look like the following:

In the cell below, we visualize each segment as the mean color of pixels in the segment.

### 2.2 Color and Position Features (15 points)

Another simple feature vector for a pixel is to concatenate its color and position within the image. In other words, for a pixel of color $(r, g, b)$ located at position $(x, y)$ in the image, its feature vector would be $(r, g, b, x, y)$. However, the color and position features may have drastically different ranges; for example each color channel of an image may be in the range $[0, 1)$, while the position of each pixel may have a much wider range. Uneven scaling between different features in the feature vector may cause clustering algorithms to behave poorly.

One way to correct for uneven scaling between different features is to apply some sort of normalization to the feature vector. One of the simplest types of normalization is to force each feature to have zero mean and unit variance.

Implement color_position_features in segmentation.py.

Output segmentation should look like the following:

$$feature_{new} = \frac{(feature - Mean(feature))}{Std (feature)}$$

Numpy中stack()，hstack()，vstack()函数详解

### Extra Credit: Implement Your Own Feature

For this programming assignment we have asked you to implement a very simple feature transform for each pixel. While it is not required, you should feel free to experiment with other feature transforms. Could your final segmentations be improved by adding gradients, edges, SIFT descriptors, or other information to your feature vectors? Could a different type of normalization give better results?

Implement your feature extractor my_features in segmentation.py

Depending on the creativity of your approach and the quality of your writeup, implementing extra feature vectors can be worth extra credit (up to 5% of total points).

## 3 Quantitative Evaluation (30 points)

Looking at images is a good way to get an idea for how well an algorithm is working, but the best way to evaluate an algorithm is to have some quantitative measure of its performance.

For this project we have supplied a small dataset of cat images and ground truth segmentations of these images into foreground (cats) and background (everything else). We will quantitatively evaluate different segmentation methods (features and clustering methods) on this dataset.

We can cast the segmentation task into a binary classification problem, where we need to classify each pixel in an image into either foreground (positive) or background (negative). Given the ground-truth labels, the accuracy of a segmentation is $(TP+TN)/(P+N)$.

Implement compute_accuracy in segmentation.py.

Accuracy: 0.97

You can use the script below to evaluate a segmentation method’s ability to separate foreground from background on the entire provided dataset. Use this script as a starting point to evaluate a variety of segmentation parameters.

1. 加载数据集，包括原图和分割结果真值
2. 调用之前实现的聚类分割算法进行分割
3. 将真值和分割结果进行比对，计算准确率

/home/ubuntu/anaconda3/lib/python3.6/site-packages/skimage/transform/_warps.py:84: UserWarning: The default mode, 'constant', will be changed to 'reflect' in skimage 0.15.
warn("The default mode, 'constant', will be changed to 'reflect' in "

Accuracy for image 0: 0.8330
Accuracy for image 1: 0.9221
Accuracy for image 2: 0.9859
Accuracy for image 3: 0.8517
Accuracy for image 4: 0.6973
Accuracy for image 5: 0.7073
Accuracy for image 6: 0.6290
Accuracy for image 7: 0.5707
Accuracy for image 8: 0.9028
Accuracy for image 9: 0.9225
Accuracy for image 10: 0.8701
Accuracy for image 11: 0.6352
Accuracy for image 12: 0.8259
Accuracy for image 13: 0.6570
Accuracy for image 14: 0.7508
Accuracy for image 15: 0.6221
Mean accuracy: 0.7740

Include a detailed evaluation of the effect of varying segmentation parameters (feature transform, clustering method, number of clusters, resize) on the mean accuracy of foreground-background segmentations on the provided dataset. You should test a minimum of 10 combinations of parameters. To present your results, add rows to the table below (you may delete the first row).

Feature Transform Clustering Method Number of segments Scale Mean Accuracy
Color K-Means 3 0.5 0.7979
Color K-Means 4 0.5 0.7664
Color K-Means 2 0.5 0.7609
Color K-Means 3 0.4 0.7904
Color K-Means 3 0.6 0.7935
Color K-Means 3 0.8 0.7963
Color K-Means 3 1 0.7974
Color-Postion K-Means 3 1 0.7767
Color-Postion K-Means 3 0.5 0.7883
... ... ... ... ...

1. Based on your quantitative experiments, how do each of the segmentation parameters affect the quality of the final foreground-background segmentation?
2. Are some images simply more difficult to segment correctly than others? If so, what are the qualities of these images that cause the segmentation algorithms to perform poorly?
3. Also feel free to point out or discuss any other interesting observations that you made.

Write your analysis in the cell below.

1. 基于对结果的观察：

1. 基于颜色-位置特征的聚类效果比基于颜色特征的聚类效果差
2. 聚类数目3个就是最好的了，增大减小都影响效果
3. 尺度是越接近原图，也就是越接近1，准确度越高
2. 的确存在一些图更难识别。这些图的一些特性包括

1. 背景较为复杂
2. 前景颜色、亮度都与背景较为接近
3. 我发现在基于颜色-位置特征的聚类中，尺度并不是越大越好，可能是我做的实验次数不够多。