在 C++ 中查找给定布尔矩阵中具有最大公共区域大小的区域

2025年2月7日 | 阅读 9 分钟

引言

在计算机科学领域，尤其是在图像处理中，布尔矩阵扮演着至关重要的角色。布尔矩阵是指其元素仅表示布尔值（真和假，或表示为 1 和 0）的矩阵。这些矩阵在图像处理、网络连通性以及 GIS 应用中有着广泛的应用。

当使用布尔矩阵时，一个比较特殊的问题是搜索矩阵内的连续区域。换句话说，这些连续的真元素如果位于同一行、同一列或对角线上，则构成一个区域。当前的问题不仅在于找出这些区域，还要确定每个区域的大小，并发现最常出现的区域的大小。

这个问题在各种领域都有实际应用。例如，图像应用如图像处理区域和区域识别可以帮助物体识别和图像分割。寻找连通分量在分析中可能至关重要，因为识别它们有助于理解网络的结构和健壮性。

什么是布尔矩阵？

布尔矩阵是一种二维数组，其中的每个元素都具有布尔数据类型，该数据类型只有两个可能的值：“真”和“假”。在二进制值的情况下，如前所述，真用 1 表示，假用 0 表示。布尔矩阵在计算机科学中被广泛使用；它用于图像处理、图论和数据分析。

布尔矩阵的特性

二进制元素：我们正在考虑的矩阵 X 是一个 n * n 矩阵，其中每个数字是真 (1) 或假 (0)。
固定维度：像所有矩阵一样，布尔矩阵必须具有特定的行数和列数。
应用：它们用于显示二值图像、图中的邻接矩阵、逻辑运算等。

示例

在此矩阵中

1 代表真。
0 代表假。

布尔矩阵中的区域是什么？

在布尔矩阵的上下文中，区域简单地指所有元素都显示为真或等于 1 并且它们都相互连接的区域。连通性的概念可以定义为两种方式：4-连通和 8-连通是两个最常用的 LGA 包。

连通性类型

1. 4-连通

在 4-连通中，每个真元素与其上方、下方、左侧和右侧的元素相邻。
对角线邻居不被视为连接。

例如，在以下 4x4 布尔矩阵中

具有 4-连通的区域

区域 1：单个 1 位于第一通道，位于左上角。
区域 2：它连接了第二行中的两个连接的 1。
区域 3：第二行和第三行中的三个连接的 1。在最后一行，分母中的五个 1 通过较短的水平线连接。
区域 4：单个 1 位于 Android 应用程序图标的右下角。

2. 8-连通

同样，在 8-连通中，所有真邻居与公共元素之间存在连接，包括水平、垂直和对角线。例如，使用相同的矩阵

具有 8-连通的区域

区域 1：左上角的递增数字 1。
区域 2：第二列到第三列的第二行和第三行中的三个连接的 1。
区域 3：右下角的两个连接的 1。

如何识别区域？

要划分布尔矩阵，必须查找所有连接的“真”或 1 的块。这可以通过使用带有约束条件的图搜索方法来完成，例如，使用深度优先搜索 (DFS)、广度优先搜索 (BFS) 和并查集 (Disjoint Set) 算法。以下是每种方法的逐步指南

深度优先搜索 (DFS) 方法

DFS 在尽可能深入地探索一个分支，然后再回溯。它们可以使用递归或堆栈来实现。

1. 初始化

生成一个与输入矩阵大小相同的访问矩阵，其中填充了假值。

2. DFS 函数

def dfs(matrix, visited, i, j):
    # Directions for 4-connectivity (up, down, left, right)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    stack = [(i, j)]
    
    while stack:
        x, y = stack.pop()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and not visited[nx][ny] and matrix[nx][ny] == 1:
                visited[nx][ny] = True
                stack.append((nx, ny))
Identify Regions:
def find_regions(matrix):
    visited = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
    region_count = 0
    
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 1 and not visited[i][j]:
                dfs(matrix, visited, i, j)
                region_count += 1
                
    return region_count

广度优先搜索 (BFS) 方法

BFS 在进入树的下一层节点之前，会检查当前层的 ao 邻居。它可以使用队列来实现。

1. 初始化

创建一个与输入矩阵大小相同的 0 矩阵，并将其命名为访问矩阵，同时将其每个元素都设置为 false。

2. BFS 函数

from collections import deque
def bfs(matrix, visited, i, j):
    # Directions for 4-connectivity (up, down, left, right)
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    queue = deque([(i, j)])
    visited[i][j] = True
    
    while queue:
        x, y = queue.popleft()
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            if 0 <= nx < len(matrix) and 0 <= ny < len(matrix[0]) and not visited[nx][ny] and matrix[nx][ny] == 1:
                visited[nx][ny] = True
                queue.append((nx, ny))
Identify Regions:
def find_regions(matrix):
    visited = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
    region_count = 0
    
    for i in range(len(matrix)):
        for j in range(len(matrix[0])):
            if matrix[i][j] == 1 and not visited[i][j]:
                bfs(matrix, visited, i, j)
                region_count += 1
                
    return region_count

示例

C++ 程序：查找给定布尔矩阵中最常见的区域大小。

#include <iostream>
#include <vector>
#include <unordered_map>
#include <algorithm>

using namespace std;

// Directions for 4-connectivity (up, down, left, right)
int directions[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

// Function to perform DFS and return the size of the region
int dfs(vector<vector<int>>& matrix, vector<vector<bool>>& visited, int i, int j) {
    int regionSize = 1;
    visited[i][j] = true;

    for (int d = 0; d < 4; ++d) {
        int newRow = i + directions[d][0];
        int newCol = j + directions[d][1];

        if (newRow >= 0 && newRow < matrix.size() && newCol >= 0 && newCol < matrix[0].size() &&
            !visited[newRow][newCol] && matrix[newRow][newCol] == 1) {
            regionSize += dfs(matrix, visited, newRow, newCol);
        }
    }

    return regionSize;
}

// Function to find regions and their sizes
unordered_map<int, int> findRegions(vector<vector<int>>& matrix) {
    int rows = matrix.size();
    int cols = matrix[0].size();
    vector<vector<bool>> visited(rows, vector<bool>(cols, false));
    unordered_map<int, int> regionSizeCount;

    for (int i = 0; i < rows; ++i) {
        for (int j = 0; j < cols; ++j) {
            if (matrix[i][j] == 1 && !visited[i][j]) {
                int regionSize = dfs(matrix, visited, i, j);
                regionSizeCount[regionSize]++;
            }
        }
    }

    return regionSizeCount;
}

// Function to find the most common region size
int findMostCommonRegionSize(unordered_map<int, int>& regionSizeCount) {
    int maxCount = 0;
    int mostCommonSize = -1;

    for (auto& pair : regionSizeCount) {
        if (pair.second > maxCount) {
            maxCount = pair.second;
            mostCommonSize = pair.first;
        }
    }

    return mostCommonSize;
}

int main() {
    // Sample input
    vector<vector<int>> matrix = {
        {1, 0, 0, 1},
        {0, 1, 1, 0},
        {1, 1, 0, 0},
        {0, 0, 1, 1}
    };

    // Find regions and their sizes
    unordered_map<int, int> regionSizeCount = findRegions(matrix);

    // Find the most common region size
    int mostCommonSize = findMostCommonRegionSize(regionSizeCount);

    // Output the most common region size
    cout << "The most common region size is: " << mostCommonSize << endl;

    return 0;
}

输出

The most common region size is: 1
=== Code Execution Successful ===

应用

在给定布尔矩阵中找到出现频率最高的区域大小，有助于解决不同领域的现实问题。以下是一些值得注意的应用：

计算机视觉和图像处理应用领域包括物体检测和分割、模式分析、医学成像和诊断、土地利用分类、网络、生态与环境、机器人和路径规划、材料和微观结构分析、数据压缩以及农业和城市规划。基于上述定义，物体检测和分割包括通过识别二值图像中的连通像素块来将物体与背景分离开来。另一个子任务是模式识别，其中识别和计数图像中相似大小的特征或模式。
在医学成像中，布尔矩阵用于根据肿瘤的大小、形状和布尔密度来诊断肿瘤。地理信息系统 (GIS) 根据特定特征（如连续性）对区域进行分类，其中可以通过国家、森林、水体和城市区域来区分适当的土地利用。网络分析应用于连通分量，以确定网络的结构和健壮性。
在生态学和环境科学中，栖息地测绘用于绘制栖息地图，并确定一系列相邻栖息地区域的局部分布和大小。布尔矩阵应用于机器人和路径规划，其中 1 表示障碍区域，有助于路径规划算法。在材料科学中，微观结构分析使用户能够推断其他性能，如强度和柔韧性。
数据压缩算法可最大限度地减少消息冗余；它们对二值图像中相似大小的区域进行编码。在农业中，使用卫星/航空影像来确定作物斑块以及最合适的施肥和控制策略。城市规划应用土地地块的概念，涉及识别土地地块及其各自的尺寸，以进行规划和开发。

结论

总之，布尔矩阵也适用于计算机科学的不同领域，尤其侧重于图像和网络的特征，以及 GIS。在这些应用中，通过扩展数学算法到物体检测、图像分割分析、连通网络等多个应用，定义包含真元素 (1) 的连续区域变得非常必要。识别区域及其大小对于了解矩阵所指示的数据结构非常有利。

通过采用常用的算法，如深度优先搜索 (DFS) 和广度优先搜索 (BFS)，可以轻松找到这些区域。此外，如果对这些区域的大小进行更详细的分析，就可以找出给定上下文中出现频率最高的区域的大小，而这些知识在许多研究领域都有一定程度的用处。例如，在图像处理中用于检测和分割物体，或在医学成像中用于查找肿瘤。

附带的 C++ 代码展示了如何解决在指示的布尔矩阵中识别具有最大区域大小的区域的问题。DFS 算法有助于探索矩阵，而 unordered_map 有助于计算区域大小并识别最常用的区域大小。此部分可以根据各种应用领域进一步泛化和专门化，并强调了布尔矩阵分析的用法和有用性。

下一主题K-inverse-pairs-array

在 C++ 中查找给定布尔矩阵中具有最大公共区域大小的区域

引言

什么是布尔矩阵？

布尔矩阵的特性

布尔矩阵的特性

布尔矩阵中的区域是什么？

连通性类型

如何识别区域？

深度优先搜索 (DFS) 方法

广度优先搜索 (BFS) 方法

示例

输出

应用

结论

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

在 C++ 中查找给定布尔矩阵中具有最大公共区域大小的区域

引言

什么是布尔矩阵？

布尔矩阵的特性

布尔矩阵的特性

布尔矩阵中的区域是什么？

连通性类型

如何识别区域？

深度优先搜索 (DFS) 方法

广度优先搜索 (BFS) 方法

示例

输出

应用

结论

相关帖子

霍夫曼编码

二维打印二叉树

数据结构中的后缀树

使用 Trie 实现自动完成功能

数据结构中树的类型

Y 型链表的交点

使用相同数字集查找下一个回文数

使用 DSU 检测图中的循环

Trie 数据结构

二叉树的垂直遍历

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器