图像检索与推土机距离

小象实战讲义 · 基于深度学习的计算机视觉

在本节中，我们将正式进入图像检索领域。你是否曾有过这样的经历：看到一株不认识的植物，拍下照片上传到搜索引擎，系统便能告诉你它的名字？这种“以图搜图”的能力，其背后核心就是图像检索技术。本节我们将首先了解图像检索的基本流程与应用场景，然后深入一个关键概念——推土机距离（Earth Mover’s Distance, EMD），它不仅是衡量颜色直方图相似度的有效工具，更是后续学习生成对抗网络（WGAN）等现代模型的理论基础。

💡 核心导读

• 图像检索：理解“以图搜图”的基本流程，即从查询图像和图像库中提取特征，并进行相似度比较。
• 推土机距离（EMD）：学习如何将两个分布（如颜色直方图）的相似度度量，转化为一个经典的“运输问题”来求解。
• 从土堆到颜色：掌握如何将抽象的推土机距离具体应用到颜色直方图的比较上，理解其相比简单逐维比较的优势。
• Wasserstein 距离：认识推土机距离的另一个名字，并了解其在计算机视觉领域（如WGAN）中的重要性。

图像检索：场景与基本原理

图像检索（Image Retrieval），尤其是基于内容的图像检索（Content-Based Image Retrieval, CBIR），其最典型的应用就是我们熟知的“以图搜图”。

想象一下，你在户外看到一株奇特的植物，不认识它。这时，你只需用手机拍下照片，然后将这张图片拖入搜索引擎的搜索框（是的，大部分主流搜索引擎都支持直接拖拽图片进行搜索）。点击搜索后，系统会返回大量相关信息，你很快就能知道这株植物原来是“芦荟”。

这个过程完美地诠释了图像检索的核心价值：当我们看到一个物体却不知其名时，可以通过图像来寻找答案。这仅仅是其应用场景之一，类似的还包括寻找相似风格的画作、识别商品、追踪图片出处等。

那么，这个系统是如何工作的呢？其基本原理可以概括为以下几个步骤：

1. 构建图像库与特征库：系统背后有一个海量的图像数据库。对于库中的每一张图像，都会先进行预处理（如尺寸归一化），然后提取特征。这些特征被存储起来，形成一个“特征数据库”。这里的特征，既可以是基于颜色、纹理、形状的传统特征，也可以是通过深度学习模型提取的深度特征（一种压缩的编码形式）。
2. 处理查询图像：当用户提交一张查询图片时，系统同样会对这张图片进行预处理和特征提取，得到一个查询特征向量。
3. 相似度比较与排序：系统将查询特征向量与特征数据库中的所有特征向量进行相似度比较。这种比较通常是“模糊”的，并非精确匹配，因为即使是同一物体，在不同光照、角度下拍摄的特征也会有差异。
4. 返回检索结果：系统根据相似度的高低对图像库中的图片进行排序，并将最相似的一系列图片作为结果返回给用户。

整个流程的核心在于特征提取和相似度度量。本节，我们将重点探讨一种用于度量分布相似性的重要方法——推土机距离。

推土机距离：从运输问题到分布度量

当我们比较两张图片的颜色直方图时，一个直观的想法是直接计算两个直方图在每个颜色桶（bin）上的数值差异，比如求差的绝对值或平方和。然而，这种方法存在一个根本问题：它默认所有颜色桶之间是相互独立的。

但实际上，颜色在色彩空间中是连续且相关的。例如，橙红色和橙黄色在视觉上非常接近，可能只因为细微的亮度或饱和度差异，就被划分到了两个不同的颜色桶中。如果使用简单的逐桶比较，这两个本应很接近的颜色会被视为完全不同，导致相似度计算不准确。

为了解决这个问题，我们需要一种能够考虑“元素”之间关联性的距离度量方式。这就是推土机距离（Earth Mover’s Distance, EMD），也称为Wasserstein距离。它的思想源于一个经典的运输问题。

运输问题模型

假设我们有若干个土堆（供应点）和若干个土坑（需求点）。

• 每个土堆有一定量的土（供应量）。
• 每个土坑需要一定量的土来填平（需求量）。
• 前提条件：所有土堆的土总量等于所有土坑的需求总量。
• 从任何一个土堆运送一单位土到任何一个土坑，都需要一定的“成本”（通常与两点之间的距离成正比）。
• 有一个搬运工，一次只能搬运一单位土。

我们的目标是：找到一种土方调配方案，用最小的总成本，将所有土堆的土运到土坑并恰好填平所有坑。

一个具体例子

让我们通过一个具体例子来理解。假设有三个土堆（E1, E2, E3），每个土堆都有5个单位的土。有三个土坑（H1, H2, H3），需要填的土量分别是3、7、5个单位。显然，总土量（5+5+5=15）等于总需求量（3+7+5=15），满足前提。

土堆和土坑之间的距离（即运输成本）如下表所示：

我们的任务是规划运输方案，使得总成本最低。

一种直观的贪婪策略是“就近填充”：

1. E1离H1最近（成本1），所以先用E1的土填H1。H1需要3个单位，E1有5个，因此从E1运3个单位到H1，成本为 3 * 1 = 3。此时E1还剩2个单位土。
2. E2离H2最近（成本1），所以用E2的土填H2。H2需要7个单位，E2有5个，因此从E2运5个单位到H2，成本为 5 * 1 = 5。此时E2的土用完，H2还缺2个单位。
3. E3离H3最近（成本1），所以用E3的土填H3。H3需要5个单位，E3有5个，因此从E3运5个单位到H3，成本为 5 * 1 = 5。此时E3的土用完，H3填平。
4. 现在，H2还缺2个单位，而E1还剩2个单位。从E1运2个单位到H2，成本为 2 * 2 = 4（距离为2）。

总成本 = 3 (E1->H1) + 5 (E2->H2) + 5 (E3->H3) + 4 (E1->H2) = 17。

可以验证，这就是该问题的最优解（最小成本）。这个最小成本17，就是土堆分布{E1, E2, E3}与土坑分布{H1, H2, H3}之间的推土机距离。它衡量的是将一个分布（土堆）转化为另一个分布（土坑）所需要的最小“工作量”。

应用于颜色直方图比较

现在，我们将推土机距离的思想应用到颜色直方图的比较上。两张图片的颜色直方图可以看作是两个概率分布（每个颜色桶的值是该颜色出现的频率，所有桶的频率之和为1）。

假设我们有两个颜色直方图，分别记为 P 和 Q，它们各有若干个颜色桶，每个桶的值是该颜色出现的频率（所有桶之和为 1）。要把 P “搬运”成 Q，供应量就是 P 各桶的频率，需求量就是 Q 各桶的频率，而单位运输成本则是两个桶所代表颜色之间的视觉差异——通常用 CIELAB 颜色空间下的 CIEDE2000 色差来衡量。

课件用一个三桶（红、紫、粉）的例子演示了这一过程：同一颜色到自身的色差很小（如 2.5），相邻色调的色差中等（如 17.4、21.2、27.4），跨越较大的颜色差异则很大（如 39.7）。求解对应的运输问题后，得到的 EMD 约为 4.8（单位是 CIEDE2000 色差）。

需要说明的是，EMD 的价值并不在于“数值比逐桶距离更小”。归一化直方图的逐桶 L1 差最大只有 2，而 EMD 以色差为计量单位，两者量纲不同，不能直接比大小（检索示例中的 EMD 甚至可能超过 100）。它的优势在于：把“相似颜色被划进不同桶”的错位代价按真实色差（CIEDE2000）计入，于是相似图像的 EMD 小、差异大的图像 EMD 大，检索排序因而更符合人眼感知。

需要强调：EMD 的求解必须同时满足每个桶的供应量与需求量约束，不能把质量运到需求为 0 的桶；具体的最优流量分配由线性规划求解，这里不展开逐项数值。

这种“允许质量在相近颜色间流动”的机制，更符合人眼的视觉感知：如果两张图的主色调都是红色，只是阴影部分有些许紫色和粉色的差别，那么它们整体上应该是比较相似的。

代码示例：理解推土机距离的计算

虽然精确求解EMD需要线性规划等算法，但我们可以通过一个极简的例子，用穷举法来感受其计算逻辑，并与欧氏距离进行对比。

import numpy as np
import itertools

# 定义两个简单的1D分布（可以想象为两个只有两个颜色桶的直方图）
P = np.array([0.8, 0.2])  # 分布P
Q = np.array([0.2, 0.8])  # 分布Q

# 定义成本矩阵：桶1到桶1成本低，桶1到桶2成本高，反之亦然。
# 假设桶1和桶2是相邻颜色，成本为1；自身到自身成本为0。
cost_matrix = np.array([[0, 1],
                        [1, 0]])

# 方法1：计算欧氏距离（作为对比）
euclidean_dist = np.sqrt(np.sum((P - Q) ** 2))
print(f"分布P: {P}")
print(f"分布Q: {Q}")
print(f"欧氏距离: {euclidean_dist:.4f}")
print()

# 方法2：穷举法计算EMD（仅用于极小规模演示）
# 我们需要将P的0.8和0.2分配到Q的0.2和0.8上，流量矩阵F的每个元素f_ij表示从P_i到Q_j的流量。
# 约束：sum_j(f_ij) = P_i, sum_i(f_ij) = Q_j, f_ij >= 0
# 由于总和为1，且只有2x2=4个变量，我们可以穷举所有可能的流量分配（离散化）。
min_cost = float('inf')
best_flow = None

# 离散化步长
step = 0.1
# 生成所有可能的f_00值
for f00 in np.arange(0, min(P[0], Q[0]) + step, step):
    f00 = round(f00, 1)
    # 根据约束计算其他流量
    f01 = P[0] - f00
    f10 = Q[0] - f00
    f11 = P[1] - f10  # 也等于 Q[1] - f01
    # 检查所有流量是否非负且满足另一个约束
    if f01 >= 0 and f10 >= 0 and f11 >= 0 and abs((f10 + f11) - P[1]) < 1e-9:
        flow = np.array([[f00, f01], [f10, f11]])
        total_cost = np.sum(flow * cost_matrix)
        if total_cost < min_cost:
            min_cost = total_cost
            best_flow = flow

print("推土机距离（EMD）计算演示（离散化穷举）:")
print(f"最优流量矩阵:\n{best_flow}")
print(f"推土机距离（最小总成本）: {min_cost:.4f}")
print()
print("解释：")
print("欧氏距离直接计算 sqrt((0.8-0.2)^2 + (0.2-0.8)^2)，忽略了桶之间的相关性。")
print("EMD则寻找最优运输方案。由于桶1到桶2有成本(1)，最优方案是：")
print("  - 将P桶1的0.2运到Q桶1（成本0），剩下0.6需要运到Q桶2（成本0.6*1=0.6）。")
print("  - 将P桶2的0.2运到Q桶2（成本0）。")
print("  - 总成本 = 0.6，这就是EMD。它反映了将分布P‘挪动’成分布Q所需的最小工作量。")

分布P: [0.8 0.2]
分布Q: [0.2 0.8]
欧氏距离: 0.8485

推土机距离（EMD）计算演示（离散化穷举）:
最优流量矩阵:
[[0.2 0.6]
 [0.  0.2]]
推土机距离（最小总成本）: 0.6000

解释：
欧氏距离直接计算 sqrt((0.8-0.2)^2 + (0.2-0.8)^2)，忽略了桶之间的相关性。
EMD则寻找最优运输方案。由于桶1到桶2有成本(1)，最优方案是：
  - 将P桶1的0.2运到Q桶1（成本0），剩下0.6需要运到Q桶2（成本0.6*1=0.6）。
  - 将P桶2的0.2运到Q桶2（成本0）。
  - 总成本 = 0.6，这就是EMD。它反映了将分布P‘挪动’成分布Q所需的最小工作量。

通过这个简单例子，你可以看到：当两个分布形状相反但总量相同时，欧氏距离会很大（0.85），而EMD距离（0.6）则更小，因为它允许概率质量在相邻的桶之间流动，并且为这种流动付出了合理的成本。如果成本矩阵中的值更大（比如颜色差异很大），EMD也会相应变大。

推土机距离的意义与延伸

推土机距离（Wasserstein距离）的核心优势在于，它将一个分布变换为另一个分布所需的最小“工作量”进行了量化。这个“工作量”由我们定义的成本矩阵（如颜色差异、实际距离等）决定。

在图像检索中，这使我们能够更准确地进行基于颜色的相似性搜索。更重要的是，这个概念是整个计算机视觉领域的一个重要基石。在后续课程中，当我们学习生成对抗网络（GAN）时，你会遇到Wasserstein GAN（WGAN）。WGAN的提出者发现，使用推土机距离作为衡量生成数据分布与真实数据分布差异的度量，相比原始的GAN使用的JS散度等，能有效解决训练不稳定、模式崩溃等问题，从而引领了一波GAN研究的改进浪潮。

因此，理解推土机距离，不仅仅是掌握了一个图像检索的工具，更是为后续学习更现代的深度学习模型打下了坚实的理论基础。

📝 动手练一练

1. 概念辨析：为什么在比较颜色直方图时，推土机距离（EMD）通常比简单的欧氏距离或曼哈顿距离更合理？请从颜色感知的特性角度阐述。

2. 简单计算：假设有两个一维分布 A=[0.7, 0.3] 和 B=[0.4, 0.6]，成本矩阵为 [[0, 1], [1, 0]]。请模仿运输问题的思路，描述一个将分布A转化为分布B的可行运输方案，并计算该方案的总成本。你能推断出最小的可能成本（即EMD）是多少吗？

本章小结

本节我们开启了图像检索技术的大门。我们首先了解了以图搜图等图像检索的典型应用场景及其核心流程：特征提取与相似度匹配。接着，我们深入学习了用于度量分布相似性的关键工具——推土机距离（EMD/Wasserstein距离）。

推土机距离的精妙之处在于，它将抽象的分布差异比较，转化为一个具象的“最优运输问题”来求解。通过定义合理的成本（如颜色差异），EMD能够衡量将一个分布“改造”成另一个分布所需的最小工作量。这使得它在比较颜色直方图等具有内在相关性的特征时，比简单的逐点距离度量要准确得多。更重要的是，这个概念是连接传统图像处理与现代深度学习（如WGAN）的重要桥梁。

📋 行动清单

• 尝试使用一个主流搜索引擎的“以图搜图”功能，直观感受图像检索的效果。
• 在脑海中复述一遍从“土堆土坑”运输问题到“颜色直方图”比较的类比过程，确保理解EMD的核心思想。
• 记住“Wasserstein距离”这个术语，并了解它在后续生成对抗网络（GAN）中的重要地位。

—— 小象教研组