使用稀疏矩阵表示聚类二值图像

Question

我在 Whosebug 上看到了这个 question，我确实想使用 稀疏矩阵表示 :

我知道有更简单有效的聚类方法（KMeans、Mean-shift 等...），我知道这个问题可以用其他解决方案解决，例如 connected components,

但我的目标是使用稀疏矩阵表示方法。

目前我尝试过的是：

读取图像并定义距离函数（以欧氏距离为例）：

#!/usr/bin/python3
# -*- coding: utf-8 -*-

import cv2
import numpy as np
from math import sqrt
from scipy.sparse import csr_matrix

original = cv2.imread("km.png", 0)

img = original.copy()

def distance(p1, p2):
    """
    Euclidean Distance
    """
    return sqrt((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2)

根据二值图像的非零点构建稀疏矩阵，为了简单起见，我正在考虑两个簇，以后可以扩展到k集群：

data = np.nonzero(img)
data = tuple(zip(data[0],data[1]))
data = np.asarray(data).reshape(-1,2)
# print(data.shape)

l = data.shape[0] # 68245

# num clusters
k = 2
cov_mat = csr_matrix((l, l, k), dtype = np.int8).toarray()

第一个循环将质心作为彼此最远的点：

# inefficient loop!
for i in range(l):
    for j in range(l):
        if(i!=j):
            cov_mat[i, j, 0] = distance(data[i], data[j])
# Centroids
# TODO: check if more than two datapoints with same max distance then take first!
ci = cov_mat[...,0].argmax()

计算与每个质心的距离：

# inefficient loop!
# TODO: repeat for k clusters!
for i in range(l):
    for j in range(l):
        if(i!=j):
            cov_mat[i, j, 0] = distance(data[i], data[ci[0]])
            cov_mat[i, j, 1] = distance(data[i], data[ci[1]])

根据最小距离聚类：

# Labeling
cov_mat[cov_mat[...,0]>cov_mat[...,1]] = +1
cov_mat[cov_mat[...,0]<cov_mat[...,1]] = -1
# Labeling Centroids
cov_mat[ci[0], ci[0]] = +1
cov_mat[ci[1], ci[1]] = -1

获取集群索引：

# clusters Indicies
cl1 = cov_mat[...,0].argmax()
cl2 = cov_mat[...,0].argmin()

# TODO: pass back the indices to the image to cluster it.

这种方法比较费时间，请问如何提高效率？提前致谢。

Answer 1

正如评论中所指出的，在使用 NumPy 数组时，矢量化代码应该优先于标量代码（即具有显式 for 循环的代码）。此外，正如我所见，在这个特定问题中，密集 NumPy 数组比 Scipy 稀疏数组是更好的选择。如果您不受限于使用稀疏数组，则此代码可以：

import numpy as np
from skimage.io import imread
from sklearn.cluster import KMeans
import matplotlib.pyplot as plt

n_clusters = 2
palette = [[255, 0, 0], [0, 255, 0]]

img = imread('https://i.stack.imgur.com/v1NDe.png')
rows, cols = img.nonzero()
coords = np.stack([rows, cols], axis=1)

labels = KMeans(n_clusters=n_clusters, random_state=0).fit_predict(coords)

result = np.zeros(shape=img.shape+(3,), dtype=np.uint8)
for label in range(n_clusters):
    idx = (labels == label)
    result[rows[idx], cols[idx]] = palette[label]

fig, (ax0, ax1) = plt.subplots(1, 2, figsize=(12, 8))
ax0.imshow(img, cmap='gray')
ax0.set_axis_off()
ax0.set_title('Binary image')
ax1.imshow(result)
ax1.set_axis_off()
ax1.set_title('Cluster labels');

使用稀疏矩阵表示聚类二值图像

Clustering binary image using sparse matrix representation

python

numpy

cluster-analysis

image-processing

sparse-matrix

但我的目标是使用稀疏矩阵表示方法。