无需计算全部成对距离的二值化表单图像聚类及异常检测算法咨询（Python/Scipy实现）

阿华AIGC实验室

2026-4-1

我完全get到你的需求：手里有一批二值化的表单图像，分N种固定布局，还有些乱入的异常图（随机文本/图像），想用相交黑像素数判断图像相似度（重叠越高越可能是同布局），但又不想算所有两两图像的距离——毕竟数据量大的话，O(n²)的计算量真的太劝退了，还得用Python+Scipy的工具栈来实现，同时要把异常点单独拎出来，不能混进簇里。

下面给你几个贴合需求的方案，都是不用全量成对距离的，适配你的场景：

一、先把你的重叠规则转化为聚类可用的度量

首先得把“相交黑像素数”这个相似度指标，转化为聚类算法能理解的距离/相似度函数：
对于两张展平成一维0-1向量的二值图像a、b（1=黑像素，0=白像素），相交黑像素数就是np.sum(a & b)。为了适配聚类，我们可以把它归一化：

相似度：overlap_ratio = np.sum(a & b) / np.sum(a | b)（代表黑像素的重叠比例，值越接近1越相似）
距离：1 - overlap_ratio（值越小，图像越相似）

这样转化后，不管用什么聚类算法，都能基于这个逻辑来判断。

二、不用全成对距离的聚类+异常检测方案

1. 自定义增量中心聚类（完全贴合需求，Scipy工具辅助）

这个方案最灵活，完全围绕你的重叠规则设计，而且只和簇中心计算距离，不用碰其他所有图像，计算量是O(k*n)（k是簇的数量，远小于n），非常高效。

核心逻辑：

从第一个图像开始，直接当成第一个簇的中心
每读入一张新图像，只和现有所有簇的中心算重叠率
若最大重叠率超过你设定的阈值，就把它加入对应簇，然后更新簇中心（比如用簇内所有图像的黑像素交集，或者选簇内和其他成员重叠率最高的图像当中心）
若所有簇的重叠率都低于阈值，再判断它是不是异常点（比如黑像素数量和所有簇差异极大，或者重叠率低到离谱），是异常就单独存，不是就新建一个簇

结合Scipy的实现示例：

import numpy as np
from scipy.stats import zscore
from scipy.ndimage import zoom

# 先统一图像尺寸（必须做！不然重叠计算没意义）
def normalize_img(img, target_shape=(200, 300)):
    return zoom(img, (target_shape[0]/img.shape[0], target_shape[1]/img.shape[1]), order=0)

# 假设images是你的原始二值图像列表，先归一化
normalized_images = [normalize_img(img) for img in images]
# 展平成一维向量
flat_images = [img.flatten() for img in normalized_images]

# 设定阈值（根据你的实际数据调！）
MIN_OVERLAP_RATIO = 0.8  # 同布局至少80%黑像素重叠
OUTLIER_THRESHOLD = 0.3  # 和最近中心重叠率低于30%算异常
Z_SCORE_THRESHOLD = 2  # 黑像素数量Z分数绝对值超过2算异常

clusters = []  # 每个元素是 [簇中心（展平向量）, 簇内所有图像]
outliers = []

for img in flat_images:
    img_black = np.sum(img)
    if img_black == 0:
        outliers.append(img)
        continue

    max_overlap = 0.0
    best_cluster_idx = -1

    # 只和每个簇的中心计算重叠率，不用遍历簇内所有图像
    for idx, (center, members) in enumerate(clusters):
        center_black = np.sum(center)
        if center_black == 0:
            continue
        # 计算相交黑像素数
        intersection = np.sum(np.bitwise_and(img, center))
        # 用最小黑像素数做分母，避免因为图像黑像素数量差异导致的偏差
        overlap_ratio = intersection / min(img_black, center_black)
        if overlap_ratio > max_overlap:
            max_overlap = overlap_ratio
            best_cluster_idx = idx

    if max_overlap >= MIN_OVERLAP_RATIO:
        # 加入对应簇，更新簇中心（这里用簇内所有图像的交集，也可以换成选medoid）
        clusters[best_cluster_idx][1].append(img)
        # 用簇内所有图像的黑像素交集更新中心（保证中心是所有成员共有的黑像素区域）
        new_center = np.bitwise_and.reduce(clusters[best_cluster_idx][1])
        clusters[best_cluster_idx][0] = new_center
    else:
        # 判断是否为异常点
        is_outlier = False
        if clusters:
            # 看黑像素数量是否偏离所有簇的中心
            cluster_black_counts = [np.sum(c[0]) for c in clusters]
            # 计算当前图像黑像素数的Z分数
            all_counts = cluster_black_counts + [img_black]
            z_scores = zscore(all_counts)
            current_z = z_scores[-1]
            if abs(current_z) > Z_SCORE_THRESHOLD and max_overlap < OUTLIER_THRESHOLD:
                is_outlier = True
        if is_outlier:
            outliers.append(img)
        else:
            # 新建簇
            clusters.append([img, [img]])

2. OPTICS 聚类（结合Scikit-learn+Scipy，支持自定义距离）

OPTICS是DBSCAN的升级款，不需要全量成对距离，它通过邻域查询（用Scipy的空间索引加速）来构建簇，还能自动把异常点标记为“噪声”（标签为-1）。它支持自定义距离函数，刚好适配你的重叠规则。

实现示例：

import numpy as np
from sklearn.cluster import OPTICS
from scipy.ndimage import zoom

# 先归一化图像（同上）
def normalize_img(img, target_shape=(200, 300)):
    return zoom(img, (target_shape[0]/img.shape[0], target_shape[1]/img.shape[1]), order=0)

normalized_images = [normalize_img(img) for img in images]
X = np.array([img.flatten() for img in normalized_images])

# 定义你的自定义距离函数
def form_distance(a, b):
    intersection = np.sum(np.bitwise_and(a, b))
    union = np.sum(np.bitwise_or(a, b))
    if union == 0:
        return 0.0
    # 返回1 - 重叠比例，作为距离（值越小越相似）
    return 1.0 - (intersection / union)

# 初始化OPTICS，用自定义距离，设置min_samples（每个簇至少的样本数）和xi（异常点检测阈值）
clustering = OPTICS(
    metric=form_distance,
    min_samples=3,  # 根据你的数据量调整，比如每个布局至少有3张图
    xi=0.05,  # 控制异常点的敏感度，值越小越容易把点当成异常
    n_jobs=-1  # 用多线程加速
)
clustering.fit(X)

# 结果解析
cluster_labels = clustering.labels_
# 标签为-1的就是异常点
outliers = X[cluster_labels == -1]
# 簇的数量是len(set(cluster_labels)) - (1 if -1 in cluster_labels else 0)

3. BIRCH 增量聚类（Scikit-learn+Scipy，适合大数据流）

BIRCH是专门为在线/增量聚类设计的，它会构建一个紧凑的聚类特征树（CF Tree），把数据点逐步插入树中，自动合并簇，同时能标记那些无法被任何簇吸收的点为异常。虽然它默认用欧氏距离，但你可以把图像特征转化为基于黑像素的统计特征（比如黑像素的行/列分布直方图），来适配你的场景。

比如，提取每个图像的黑像素行占比、列占比作为特征，然后用BIRCH聚类：

import numpy as np
from sklearn.cluster import Birch
from scipy.ndimage import zoom

def normalize_img(img, target_shape=(200, 300)):
    return zoom(img, (target_shape[0]/img.shape[0], target_shape[1]/img.shape[1]), order=0)

normalized_images = [normalize_img(img) for img in images]

# 提取特征：每一行的黑像素占比 + 每一列的黑像素占比
def extract_features(img):
    row_ratios = np.sum(img, axis=1) / img.shape[1]
    col_ratios = np.sum(img, axis=0) / img.shape[0]
    return np.concatenate([row_ratios, col_ratios])

X = np.array([extract_features(img) for img in normalized_images])

# 初始化BIRCH
birch = Birch(
    threshold=0.1,  # 簇合并的阈值，值越小簇越多
    branching_factor=50,
    n_clusters=None  # 自动决定簇的数量
)
birch.fit(X)

# 结果解析
cluster_labels = birch.labels_
# 可以用簇的大小来判断异常：比如只有1个样本的簇大概率是异常点
outlier_mask = np.array([np.sum(cluster_labels == label) == 1 for label in cluster_labels])
outliers = X[outlier_mask]

三、Scipy工具的实用小技巧

用scipy.ndimage.zoom统一图像尺寸：上面所有方案的前提是图像大小一致，这个函数可以帮你无损缩放二值图像（用order=0最近邻插值，保证0/1值不被模糊）
用scipy.stats.zscore检测异常：判断图像的黑像素数量、特征值是否偏离正常范围，是快速筛异常的好方法
用scipy.spatial.distance.jaccard快速计算重叠比例：1 - scipy.spatial.distance.jaccard(a, b)就是黑像素的Jaccard相似度，和我们自定义的重叠比例逻辑一致

四、关键调优提示

阈值是核心：比如MIN_OVERLAP_RATIO，你可以拿几张已知同布局的图像算一下重叠率，取一个中间值；异常点的阈值则看那些随机图的重叠率大概在什么范围
中心更新要灵活：自定义聚类里的簇中心，用“medoid”（簇内和其他成员重叠率最高的图像）比用交集更稳定，因为同布局的表单可能有细微差异（比如填写的内容不同），交集会越来越小
预处理不能少：除了统一尺寸，还可以做去噪（比如用scipy.ndimage.binary_opening去掉小的孤立黑像素），避免噪声影响重叠计算

如果还有具体的问题，比如怎么调参、怎么优化计算速度，或者处理特殊的表单情况，随时问我就行！