邻域均值

GitHub跳转原题关系图 Canvas 关系图返回列表

用二维前缀和快速计算每个裁剪邻域的总和，再比较均值阈值。

OJ: shumeng

题目 ID: CSP202104B

难度:普及-

标签:前缀和二维前缀和模拟

日期: 2026-07-31 16:21

形式化题目

给出一幅 $n\times n$ 的灰度矩阵，值域为 $[0,L)$ 。对每个像素，其邻域是满足 $|x-i|\le r$ 且 $|y-j|\le r$ 的像素集合（越界部分裁剪掉）。统计邻域平均值不超过阈值 $t$ 的像素个数。

思路

朴素做法是对每个像素遍历整个邻域求和，复杂度为 $O(n^2r^2)$ 。用二维前缀和可以把每个邻域的求和降为 $O(1)$ 。

二维前缀和

$sum[i][j]$ 表示以 $(1,1)$ 到 $(i,j)$ 为对角矩形的像素总和，递推式为

sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[i-1][j-1]+A[i][j]。

判断较暗区域

对像素 $(i,j)$ ，把邻域裁剪成矩形 $[top,bottom]\times[left,right]$ ；
用前缀和 $O(1)$ 求矩形内的总和与格子个数；
用 $sum\le t\times count$ 比较，避免浮点误差。

先看一个直接枚举邻域格子的朴素解：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
// brute.cpp：小数据暴力解，枚举每个像素邻域中的全部格子，直接求和再比较均值。
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 605;

int n, levels, radius, threshold;
int image[MAXN][MAXN];   // 原始灰度矩阵

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> levels >> radius >> threshold;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cin >> image[i][j];
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 对每个像素，枚举其邻域内的所有格子求和
            int total = 0, count = 0;
            for (int x = max(1, i - radius); x <= min(n, i + radius); x++) {
                for (int y = max(1, j - radius); y <= min(n, j + radius); y++) {
                    total += image[x][y];
                    count++;
                }
            }
            if (total <= threshold * count) answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-31 16:21
 * update_at: 2026-08-17 22:39
 */
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 605;

int n, levels, radius, threshold;
int sum[MAXN][MAXN];   // sum[i][j] 为以 (1,1) 到 (i,j) 为对角矩形的像素总和

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> levels >> radius >> threshold;
    // 边读入边构造二维前缀和
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            int value;
            cin >> value;
            sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + value;
        }
    }

    int answer = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            // 邻域在图像边界处裁剪为矩形
            int top = max(1, i - radius), bottom = min(n, i + radius);
            int left = max(1, j - radius), right = min(n, j + radius);
            int total = sum[bottom][right] - sum[top - 1][right] - sum[bottom][left - 1] + sum[top - 1][left - 1];
            int count = (bottom - top + 1) * (right - left + 1);
            // 用乘法比较避免浮点误差：均值 <= t 等价于 总和 <= t * 个数
            if (total <= threshold * count) answer++;
        }
    }
    cout << answer << '\n';
    return 0;
}

复杂度

建表和枚举像素均为 $O(n^2)$ ，空间复杂度为 $O(n^2)$ 。

总结

二维前缀和把每个邻域求和从遍历正方形降为四次数组访问；边界只需裁剪矩形端点。

时间限制： 1.0 秒

空间限制： 512 MB

题目背景

顿顿在学习了数字图像处理后，想要对手上的一副灰度图像进行降噪处理。不过该图像仅在较暗区域有很多噪点，如果贸然对全图进行降噪，会在抹去噪点的同时也模糊了原有图像。因此顿顿打算先使用邻域均值来判断一个像素是否处于较暗区域，然后仅对处于较暗区域的像素进行降噪处理。

题目描述

待处理的灰度图像长宽皆为 $n$ 个像素，可以表示为一个 $n \times n$ 大小的矩阵 $A$ ，其中每个元素是一个 $[0, L)$ 范围内的整数，表示对应位置像素的灰度值。对于矩阵中任意一个元素 $A_{i,j}\ (0 \leq i, j < n)$ ，其邻域定义为附近若干元素的集和： $\text{Neighbor}(i, j, r) = \{ A_{x,y}|0 \leq x, y < n\ \mathrm{and}\ |x-i| \leq r\ \mathrm{and}\ |y-j| \leq r \}$ 这里使用了一个额外的参数 $r$ 来指明 $A_{i,j}$ 附近元素的具体范围。根据定义，易知 $\text{Neighbor}(i, j, r)$ 最多有 $(2r+1)^2$ 个元素。

如果元素 $A_{i,j}$ 邻域中所有元素的平均值小于或等于一个给定的阈值 $t$ ，我们就认为该元素对应位置的像素处于较暗区域。下图给出了两个例子，左侧图像的较暗区域在右侧图像中展示为黑色，其余区域展示为白色。

现给定邻域参数 $r$ 和阈值 $t$ ，试统计输入灰度图像中有多少像素处于较暗区域。

输入格式

从标准输入读入数据。

输入共 $n + 1$ 行。

输入的第一行包含四个用空格分隔的正整数 $n,L,r,t$ ，含义如前文所述。

第二到第 $n + 1$ 行输入矩阵 $A$ 。第 $i + 2\ (0 \leq i < n)$ 行包含用空格分隔的 $n$ 个整数，依次为 $A_{i,0}, A_{i,1}, \cdots, A_{i,n-1}$ 。

输出格式

输出到标准输出。

输出一个整数，表示输入灰度图像中处于较暗区域的像素总数。

input1

1
2
3
4
54 16 1 6
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15

output1

input2

1
2
3
4
5
6
7
8
9
10
11
1211 8 2 2
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0
0 7 0 0 0 7 0 0 7 7 0
7 0 7 0 7 0 7 0 7 0 7
7 0 0 0 7 0 0 0 7 0 7
7 0 0 0 0 7 0 0 7 7 0
7 0 0 0 0 0 7 0 7 0 0
7 0 7 0 7 0 7 0 7 0 0
0 7 0 0 0 7 0 0 7 0 0
0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0

output2

子任务

$70\%$ 的测试数据满足 $n \leq 100,\ r \leq 10$ 。

全部的测试数据满足 $0 < n \leq 600,\ 0 < r \leq 100,\ 2 \leq t < L \leq 256$ 。

邻域均值

目录

形式化题目

思路

二维前缀和

判断较暗区域

代码

复杂度

总结