使用kmeans算法分割图像背景

k均值聚类算法（k-means clustering algorithm）是一种迭代求解的聚类分析算法，其步骤是，预将数据分为K组，则随机选取K个对象作为初始的聚类中心，然后计算每个对象与各个种子聚类中心之间的距离，把每个对象分配给距离它最近的聚类中心。聚类中心以及分配给它们的对象就代表一个聚类。每分配一个样本，聚类的聚类中心会根据聚类中现有的对象被重新计算。这个过程将不断重复直到满足某个终止条件。终止条件可以是没有（或最小数目）对象被重新分配给不同的聚类，没有（或最小数目）聚类中心再发生变化，误差平方和局部最小。

在使用opencv的kmeans算法分割图像背景，网上有很多相关的示例代码。例如

利用Python-opencv进行图像分割：Kmeans的使用（含源码）_叔均的博客-CSDN博客_python图像分割kmeans

但是我对这篇文章中的最后的总结并不太赞同

“kmeans算法对图像分割，是基于灰度分割，所以对光照敏感”

在代码中我们并没看到转为灰度相关的代码，根据这段代码发现还是BGR格式的数据。

data = img.reshape((-1,3))

但是为什么opencv 实现的kmeans算法确实会对光照敏感，为了探究其中的缘由，我们来看看opencv的官方文档。

OpenCV: K-Means Clustering in OpenCV

OpenCV: Clustering

在官方文档中介绍中，数据到中心点距离计算公式为：

个人认为这实际上是欧式距离计算公式，是否开平方不影响数据到中心点的排序，但是在计算中可以节约开平方的时间。

所以我们可以简单的理解，opencv实现的kmeans算法距离公式使用的是欧氏距离。这样就不难理解为什么kmeans算法会对光照敏感

假设第一种淡蓝色color1的brg数值为（255，0，0）

后来它受光照影响颜色比较暗，成了暗蓝色color2，bgr数值为（127, 0, 0）

这时来了第三种未知的颜色color3，bgr数值为（200, 50, 100）

我们发现color1与color2的欧式距离为128，而color1与color3的欧式距离为124。于是kmeans算法会将color1与color3归为一类，而color2归为一类，但是color2理论上和color1都是蓝色啊。

下面为使用python代码简单的验证

def euclidean_distance2(data, centers):
    distance=np.sqrt(np.sum((data-centers)**2))
    return distance

color1 = np.array([255, 0, 0])
color2 = np.array([127, 0, 0])
color3 = np.array([200, 50, 100])
print(euclidean_distance2(color1,color2))
print(euclidean_distance2(color1,color3))
im1=np.zeros([300,300,3],dtype=np.uint8)
im2=np.zeros([300,300,3],dtype=np.uint8)
im3=np.zeros([300,300,3],dtype=np.uint8)
im1[:,:]=color1
im2[:,:]=color2
im3[:,:]=color3
cv2.imshow('color1',im1)
cv2.imshow('color2',im2)
cv2.imshow('color3',im3)
cv2.waitKey(0)

那么怎么才能减少光照对结果的影响呢？我第一反应是使用余弦夹角计算距离公式，于是我依据网上kmeans算法的实现修改了距离计算公式

def kmeans(data, k=3, limit=5000):
    def euclidean_distance(data, centers):
        # 欧式距离
        #441.6729559300637=根号(255**2 *3)，用于归一化
        distance = np.sqrt(((data[:, :, None] - centers.T[None, :, :]) ** 2).sum(axis=1)) / 441.6729559300637
        return distance

    def cos_distance(data, centers):
        #余弦距离
        v1, v2 = data[:, :, None], centers.T[None, :, :]
        num = np.dot(v1.squeeze(), v2.squeeze())  # 向量点乘
        denom = np.linalg.norm(v1, axis=1).reshape(-1, 1) * np.linalg.norm(v2, axis=1)  # 求模长的乘积
        res = num / denom
        res[np.isneginf(res)] = 0
        #因为相似度越高越接近1
        return 1 - (0.5 + 0.5 * res)

    # 直接将前K个数据当成簇中心
    centers = data[:k]
    for i in range(limit):
        # 首先利用广播机制计算每个样本到簇中心的距离，之后根据最小距离重新归类
        #距离计算可以选择欧式距离和余弦相似度结合，也可以选择其他计算公式
        # distance =euclidean_distance(data, centers)+ cos_distance(data, centers)
        distance = cos_distance(data, centers)
        classifications = np.argmin(distance, axis=1)
        # 对每个新的簇计算簇中心
        new_centers = np.array([data[classifications == j, :].mean(axis=0) for j in range(k)])
        # 用-1替代nan值
        new_centers[np.isnan(new_centers)] = -1
        # 簇中心不再移动的话，结束循环
        if (new_centers == centers).all():
            break
        else:
            centers = new_centers

    return classifications, centers

我们以这张图片为例，来测验下效果。图片中一共存在三种颜色，蓝色、橘黄色和白色，希望能够通过kmeans算法将三种颜色区分开。

首先是使用opencv官方实现的kmeans算法

# 读取数据
img = cv2.imread(r"test.png")
h, w, c = img.shape
points = img.reshape([-1, 3]).astype(np.float32)
# 聚类数目
clusternum = 3
# 定义终止条件 (type,max_iter,epsilon)
criteria = (cv2.TERM_CRITERIA_EPS + cv2.TERM_CRITERIA_MAX_ITER, 10, 1.0)
# 重复试验kmeans算法次数，将会返回最好的一次结果
attempts = 5
ret, labels, center = cv2.kmeans(points, clusternum, None, criteria, attempts, cv2.KMEANS_PP_CENTERS)
labels = labels.flatten()
labels = labels.reshape([h, w])
for i in range(clusternum):
    mask = np.where(labels == i, 0, 255).astype(np.uint8)
    cv2.imshow(str(i), mask)
cv2.waitKey(0)

通过上图可以发现通过欧式距离计算，并不能很好的将三种颜色区分开

于是使用余弦距离

img = cv2.imread(r"test.png")
h, w, c = img.shape
# 将图片转换为数据保存
data = img.reshape([-1, 3]).astype(np.float32)
attempts = 3
labels, centers = kmeans(data, attempts)
labels = labels.reshape([h, w])
for i in range(attempts):
    # 前景为白色，背景为黑色
    mask = np.where(labels == i, 255, 0).astype(np.uint8)
    cv2.imshow(str(i), mask)
cv2.waitKey(0)

但是仅用余弦距离，发现轮廓细节处理并不到位。这是因为白色[255,255,255]与黑色[1,1,1]的余弦相似度居然为100%。而使用欧式距离轮廓细节很不错但是分类不够清晰，这时候我们只要将上文kmeans函数的第25行距离计算公式加上欧式距离的权重即可。

distance =0.1*euclidean_distance(data, centers)+ cos_distance(data, centers)

此时既能清晰的分割三种不同的颜色，也能有比较完整的轮廓范围