【C++】B2103 图像相似度

---

博客主页： [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C++

---

---

---

💯前言

• 在现代计算机技术中，图像处理是非常重要的一个分支。无论是在图像识别还是图像对比中，如何精确地衡量图像之间的相似度都是一个不可忽视的问题。本篇文章聚焦于一道有关"黑白图像相似度计算"的编程题目，详细解析题目要求，结合两种不同的解法进行全面对比，并探讨如何进一步优化与拓展。
  C++ 参考手册
  

---

💯题目描述

B2103 图像相似度

我们被要求完成一个程序，用来计算两幅黑白图像的相似度。这两幅图像具有相同的大小（用 $0-1$ 矩阵表示）。

题目原文

给出两幅相同大小的黑白图像（用 $0-1$ 矩阵）表示，求它们的相似度。

说明：若两幅图像在相同位置上的像素点颜色相同，则称它们在该位置具有相同的像素点。两幅图像的相似度定义为相同像素点数占总像素点数的百分比。

输入格式

• 第一行包含两个整数 $m$ 和 $n$，表示图像的行数和列数，中间用单个空格隔开。
• 接下来 $m$ 行，每行 $n$ 个整数 $0$ 或 $1$，表示第一幅黑白图像上各像素点的颜色。
• 再接下来 $m$ 行，每行 $n$ 个整数 $0$ 或 $1$，表示第二幅黑白图像上各像素点的颜色。

输出格式

一个实数，表示相似度（以百分比的形式给出），精确到小数点后两位。

样例

输入：

3 3
1 0 1
0 0 1
1 1 0
1 1 0
0 0 1
0 0 1

输出：

44.44

---

💯题目分析

目标

通过比较两幅相同大小的图像，在每个位置上检查其像素值是否一致，并统计相同像素点的总数，最终计算出相似度。

核心公式

相似度的定义如下：

$$\text{相似度}=\frac{\text{相同像素点数量}}{\text{总像素点数量}}\times 100$$

• 相同像素点数量：两幅图像在相同位置上像素值相等的点数。
• 总像素点数量：两幅图像的行数与列数之积，即 $m\times n$。

输入规模

根据题目描述：

• 图像的最大尺寸为 $100\times 100$，总像素点数最多为 $10,000$。
• 由于 $m,n$ 的限制范围适中（$1\le m,n\le 100$），直接通过双重循环逐一比较的时间复杂度 ( O(m \times n) ) 是完全可行的。

---

💯两种解法对比

在解决这个问题时，我们提供了两种不同的解法，分别是"我的做法"与"老师的做法"。以下将逐一分析两种解法的具体思路与实现。

我的做法

核心思路

1. 读取两幅图像的数据，并将其存储在两个二维数组中。
2. 通过双重循环遍历每个像素点，比较两幅图像在同一位置的像素值是否相同。
3. 统计相同像素点的数量，并计算相似度。

代码实现

以下是我的实现代码：

#include <iostream>
#include <cstdio>
using namespace std;int arr1[105][105];
int arr2[105][105];int main()
{int m, n;cin >> m >> n;// 读取第一幅图像数据for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> arr1[i][j];}}// 读取第二幅图像数据for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> arr2[i][j];}}double sum = 0, suit = 0;// 比较两幅图像，统计相同像素点数量for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {if (arr1[i][j] == arr2[i][j])suit++;sum++;}}// 计算相似度double result = suit / sum * 100;printf("%.2lf", result);return 0;
}

思路解析

1. 定义两个二维数组 arr1 和 arr2，分别存储第一幅与第二幅图像的数据。
2. 使用嵌套循环读取图像数据，并比较对应位置的像素值是否相等。
3. 如果像素值相等，增加计数器 suit。
4. 总像素点数量 sum 通过遍历自然累加。
5. 根据公式计算相似度，并格式化输出到小数点后两位。

优点

• 逻辑清晰，分为读取数据、比较像素、计算相似度三部分，结构明了。
• 易于理解，操作直接。

缺点

• 两个二维数组均使用了固定大小的内存空间，虽然满足题目要求，但占用空间稍多。

---

老师的做法

核心思路

老师的解法与我的解法思路一致，但老师在空间使用上进行了优化，直接读取第二幅图像的像素值并即时与第一幅图像进行比较，无需额外存储。

代码实现

以下是老师的代码实现：

#include <iostream>
#include <cstdio>
using namespace std;const int N = 110;
int arr[N][N];
int m, n;int main()
{cin >> m >> n;// 读取第一幅图像数据for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> arr[i][j];}}int num = 0;int c = 0;for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {cin >> num;if (num == arr[i][j])c++;}}printf("%.2f\n", c * 1.0 / (m * n) * 100);return 0;
}

思路解析

1. 定义一个二维数组 arr，用来存储第一幅图像的数据。
2. 使用嵌套循环读取第一幅图像的像素值。
3. 第二幅图像的数据通过变量 num 逐个读取，并与 arr 对应位置的像素值比较。
4. 如果像素值相等，计数器 c 增加。
5. 最终计算相似度并输出结果。

优点

• 空间优化：只使用了一个二维数组存储第一幅图像的数据，第二幅图像的数据无需额外存储，节省内存。
• 高效性：即用即比，不需要额外操作。

缺点

• 对于代码初学者来说，可读性稍差。

---

💯两种解法对比

比较维度	我的做法	老师的做法
空间使用	使用两个二维数组	使用一个二维数组
时间复杂度	$O(m\times n)$	$O(m\times n)$
代码逻辑	简单清晰，易于理解	更加高效，略显复杂
适用场景	对空间不敏感的场景	空间受限的场景

---

💯优化与拓展

优化建议

1. 动态内存分配：

   • 使用 std::vector 动态分配二维数组，避免浪费固定大小内存。

   vector<vector<int>> arr(m, vector<int>(n));
   

2. 边界检查：

   • 增加对输入数据的合法性检查，比如行数和列数是否在规定范围内：

   if (m < 1 || m > 100 || n < 1 || n > 100) {cerr << "Invalid input!" << endl;return -1;
   }
   

拓展思路

1. 处理多幅图像的相似度对比：

   • 允许输入多幅图像，逐一计算任意两幅图像之间的相似度，输出一个相似度矩阵。

2. 支持灰度图像：

   • 扩展程序以支持灰度图像（像素值范围 $0-255$），相似度计算可基于绝对差值或均方误差。

---

💯小结

本篇文章通过详细解析"图像相似度计算"问题，从题目要求到两种解法的代码实现，再到优化与拓展思路，全面展示了解决此类问题的技术细节。在实际应用中，算法的选择应根据具体需求权衡时间复杂度与空间复杂度。希望本文的分析能为读者在处理类似问题时提供有益的参考。

---

---