1. 问题描述

从训练集中随机选择 200 张图用以训练，对每一张图提取归一化 RGB颜色直方图（8*8*8=512 维），同时执行问题 2 对其进行图像分割，（分割为 50~70个区域） ，对得到的每一个分割区域提取归一化 RGB 颜色直方图特征（维度为8*8*8=512），将每一个区域的颜色对比度特征定义为区域颜色直方图和全图颜色直方图的拼接，因此区域颜色区域对比度特征的维度为 2*512=1024 维，采用PCA 算法对特征进行降维取前 20 维。 利用选择的 200 张图的所有区域（每个区域 20 维特征） 构建 visual bag of words dictionary （参考 Lecture 12. Visual Bag of Words 内容），单词数（聚类数）设置为 50 个， visual word 的特征设置为聚簇样本的平均特征，每个区域降维后颜色对比度特征（20 维） 和各个 visual word的特征算点积相似性得到 50 个相似性值形成 50 维。将得到的 50 维特征和前面的 20 维颜色对比度特征拼接得到每个区域的 70 维特征表示。 根据问题 2，每个区域可以被标注为类别 1（前景：该区域 50%以上像素为前景）或 0（背景：该区域 50%以上像素为背景）， 选用任意分类算法（SVM， Softmax，随机森林， KNN等）进行学习得到分类模型。最后在测试集上对每一张图的每个区域进行测试（将图像分割为 50~70 个区域，对每个区域提取同样特征并分类） ， 根据测试图像的GT， 分析测试集区域预测的准确率。

2. 求解过程与算法

首先需要将所有图片提取RGB颜色直方图。对于每张图片，统计其不同RGB色彩值像素的个数，最后将结果除以像素的总个数即可归一化。然后将这些图片分区，分区的方法和第二题相同。再统计每个区域的RGB颜色直方图。将每个分区的结果拼接上整张图的结果，共1024维。同时，在分区操作时，我们也能得到每个区域属于前景还是背景，即训练样本的标签。这也是已经通过第二题实现了的部分。

对于上面得到的1024维特征向量，需要通过PCA降维来提取前20维。将所有特征向量作为列向量，横向拼接形成矩阵，记为矩阵。对其进行奇异值分解，有：

其中，。满足：和是和的第个特征向量，。是对角矩阵，对角线上的值为和的特征值开根号，称为奇异值，按降序排列。因为它是对角矩阵，所以：

其中是该对角矩阵的对角线元素个数。

如果将样本中心化则有：，它和矩阵S含有相同特征向量。因此，对做奇异值分解，可以得到样本的主要方向。如果只取特征值矩阵的前20个特征值，最后得到的结果就是PCA降维后的特征值矩阵。

通过上述的PCA操作，我们可以将1024维的特征向量降维到20维。然后，我们对这些向量进行K平均聚类，即K-means操作，从而可以得到一个聚类模型。模型的聚类数量为50。具体实现方法为：在样本集中，随机选取K个点作为中心，计算每个样本到中心点的距离，并将样本划分到离它最近的那个点的集群中。使用变量表示数据样本是否属于集群k：

对于每个集群，用所有样本的平均位置更新中心点的位置：

重复上面的样本分配和中心更新过程，最终就能得到这50个聚类中心。

将上述的聚类中心和每个特征向量计算点积相似性，可以得到50个值。将这50个值加到原来的2维特征向量后，形成了新的70维特征向量，然后用这些向量训练一个KNN模型，即K近邻模型：将测试数据的特征与训练集数据的特征进行比较，找到K个最相似的数据，用这K个数据的标签决定测试数据的标签。

同样将测试数据通过上述计算归一化RGB直方图的操作、用相同的PCA模型进行降维、和上面已经得到的K平均聚类中心点计算点积相似度，最后在KNN模型中就能预测测试样本的标签了。

3. 代码实现与说明

对于上面所述的PCA模型、K-means模型、KNN模型，我使用了python的sklearn库实现。如果没有该库程序运行会报错。

3.1 归一化RGB直方图的计算

首先随机选择200张图片，每张图片计算整体的归一化RGB直方图，再分区后计算每个区域的归一化RGB直方图。因此，需要实现两个功能：给定图片，直接计算直方图，以及给定用像素集合表示的区域，计算这个像素集合的直方图。

计算图片的归一化RGB直方图时，只需要遍历图片的每一处，统计该位置的像素的RGB值，该值对应的RGB值计数加一，即可得到RGB直方图。最后，将所有计数再除以像素总数以归一化：

# 计算图片的归一化RGB直方图
def getPictureHistogram(img):
    img_array = np.array(img)
    histogram = np.zeros((8,8,8))
    for i in range(img_array.shape[0]):
        for j in range(img_array.shape[1]):
            histogram[img_array[i][j][0]//32,img_array[i][j][1]//32,img_array[i][j][2]//32] += 1
    histogram /= np.sum(histogram)  # 归一化
    return histogram.reshape(-1)

计算像素集合的归一化RGB直方图大同小异，只是遍历方式由图片的坐标遍历改为了对集合的遍历：

num = 0
for seg in SEG_GROUP.keys():
    black = 0
    white = 0
    for pixel in SEG_GROUP[seg]:
        if ground_array[pixel[0],pixel[1]] == 1:
            white += 1
        else:
            black += 1
            histograms[num,img_array[pixel[0],pixel[1],0]//32,            img_array[pixel[0],pixel[1],1]//32,img_array[pixel[0],pixel[1],2]//32] += 1
    histograms[num] /= np.sum(histograms[num])  # 直方图归一化

3.2 初始数据的生成

生成初始数据即将200张图，并分区，计算整张图与各个区域的归一化RGB直方图并进行变形和拼接，得到初始的训练样本与标签。这里需要花费大量的时间，因此我在程序入口处加入了一个变量控制数据生成：

gen_new_data = False    # 是否新生成训练数据

该变量为True时，会进行数据的生成，并且在最后保存生成的初始数据：

np.save('statistics\\histograms_total.npy',histograms_total)
np.save('statistics\\labels_total.npy',labels_total)

该变量为False时，可以直接读入之前运行程序生成好的训练数据，从而加速运行：

histograms_total = np.load('statistics\\histograms_total.npy')
labels_total = np.load('statistics\\labels_total.npy')

整个程序的运行过程，有两个矩阵存储数据。histograms_total用于存储训练数据，其维度为，其中num为训练样本数，即这200张图分区后的区域总数，1024为每个样本的维数。labels_total用于存储训练样本对应的标签，第一维的下标与histograms_total一一对应，每个样本对应一个一维的标签，标签为1表示前景，否则为0，表示背景。

对于每张图，通过调用下面的函数分别得到整张图的直方图和该图各个分区的直方图与标签：

img = Image.open("data\\imgs\\"+str(pic_id)+".png")       # 原图
ground = Image.open("data\\gt\\"+str(pic_id)+".png").convert('1')    # 前景背景图，转化为黑白图
histogram = getPictureHistogram(img)   # 获取整幅图的归一颜色直方图
histograms, labels = segment(img, ground)   # 分区并获取各个区域的颜色直方图和标签

其中segment函数和第二题基本一致，只是后面加上了对区域求RGB直方图和标签的代码，不再赘述。变量histogram和labels分别表示当前图片得到的训练样本和标签。将二者进行变形后，就可以加入总的样本矩阵中：

# 将直方图转换为特征向量
for i in range(histograms.shape[0]):
    tmp = np.hstack((histograms[i].reshape(-1),histogram))
    histograms_total = np.vstack((histograms_total,tmp))
labels_total = np.vstack((labels_total,labels.reshape(-1,1)))

3.3 PCA、K-means和KNN模型的建立

这里的模型都通过调用sklearn库建立与训练。

首先是PCA操作，通过fit_transform能同时进行PCA模型的训练和将训练数据转换成降维结果，将原本的1024维降维到20维：

pca = decomposition.PCA(n_components=20)
histograms_total = pca.fit_transform(histograms_total)

然后通过K-means模型，将样本分为50类：

# 使用K-means将样本分为50类
kmeans = KMeans(n_clusters=50)
kmeans.fit(histograms_total)
cluster_centers = kmeans.cluster_centers_.copy()# 获取分类中心

计算每个样本和分类中心的点积相似性，即余弦相似度，得到50维结果，加到原本的20维特征向量中，形成70维特征向量：

# 计算余弦相似度
cosine_sim = np.dot(histograms_total, cluster_centers.reshape(20,50)) / \
np.dot(np.linalg.norm(histograms_total, axis=1).reshape(-1,1), np.linalg.norm(cluster_centers, axis=1).reshape(1,-1))
# 将50维余弦相似度加到20维对比度后，形成70维特征
histograms_total = np.hstack((histograms_total, cosine_sim))    
    

最后，用这些特征向量与它们对应的标签，训练KNN模型：

# 将50维余弦相似度加到20维对比度后，形成70维特征
histograms_total = np.hstack((histograms_total, cosine_sim))    
# 用这些样本与标签建立KNN模型
knn = KNeighborsClassifier()
knn.fit(histograms_total, labels_total.reshape(-1))

3.4 测试样本的处理与测试

为了方便程序执行，我在做第二问的时候，将每一张图片的SEG_GROUP结果都保存下来了，只需要将分区结果读入就能很快进行RGB直方图的计算而不需要重新分区：

seg_group=np.load('statistics\\SEG_GROUP_'+str(i)+'.npy',allow_pickle=True).item()      

测试图片获取RGB直方图特征的方法与训练图片一致，不再赘述。测试样本与标签分别被存储在矩阵test_samples和test_labels中，格式与上面的测试样本与标签一致。

因为模型都已经训练好，我们只需要用这些模型依次处理测试样本，就能得到最终的预测结果：

# 用训练好的pca模型降维
test_samples = pca.transform(test_samples)
# 计算余弦相似度
cosine_sim = np.dot(test_samples, cluster_centers.reshape(20,50)) / \
np.dot(np.linalg.norm(test_samples, axis=1).reshape(-1,1), np.linalg.norm(cluster_centers, axis=1).reshape(1,-1))
# 将50维余弦相似度加到20维对比度后，形成70维特征
test_samples = np.hstack((test_samples, cosine_sim))
# 用训练好的knn模型预测结果
predict_labels = knn.predict(test_samples)

最后比较预测结果与实际标签即可：

total = predict_labels.shape[0]
right = np.sum(test_labels.reshape(-1) == predict_labels)
print('总计有'+str(total)+'个区域，其中前景背景预测正确的有'+str(right)+'个')
print('准确率为：',right/total)

3.5 结果展示与分析

最终得到的结果如下：