如何用Matlab基于二进制矩阵高效生成邻域图邻接矩阵

针对你需要从二进制矩阵 B 生成邻域图邻接矩阵 A 的需求，我整理了几个实用且高效的实现方案，先再明确下规则：当原矩阵中 B(i) 和 B(j) 均为1，且线性下标 i、j 对应的原矩阵位置是8邻接（上下左右+四个对角线方向）时，A(i,j) 和 A(j,i) 设为1。

先回顾下你给出的示例：

示例矩阵：

B = [ 0 1 0; 0 1 1; 0 0 0 ];

对应的9×9邻接矩阵A中，只有A(4,5)、A(5,4)、A(4,8)、A(8,4)、A(5,8)、A(8,5)为1，因为原矩阵里B(4)、B(5)、B(8)都是1且彼此8邻接。

核心思路 #

避免暴力遍历所有下标对（时间复杂度O(n²)，大矩阵会极慢），而是通过邻域偏移批量生成+掩码过滤的方式，只处理符合条件的1元素及其邻域，大幅降低计算量。

MATLAB 实现方案 #

方案1：基于二维坐标的直观实现 #

这个版本逻辑清晰，容易理解，适合新手调试：

function A = generate_adjacency_8(B)
    [rows, cols] = size(B);
    total_elem = rows * cols;
    A = sparse(total_elem, total_elem); % 用稀疏矩阵节省内存，大矩阵必备
    
    % 找出所有值为1的位置的二维坐标和对应的线性下标
    [r, c] = find(B == 1);
    linear_idx = sub2ind([rows, cols], r, c);
    
    % 定义8邻域的行、列偏移量
    offsets = [-1 -1; -1 0; -1 1; 0 -1; 0 1; 1 -1; 1 0; 1 1];
    
    for k = 1:length(linear_idx)
        current_r = r(k);
        current_c = c(k);
        % 生成当前位置的所有8邻域坐标
        neighbor_r = current_r + offsets(:, 1);
        neighbor_c = current_c + offsets(:, 2);
        
        % 第一步过滤：去掉超出矩阵边界的邻域
        valid_mask = (neighbor_r >= 1) & (neighbor_r <= rows) & ...
                     (neighbor_c >= 1) & (neighbor_c <= cols);
        valid_r = neighbor_r(valid_mask);
        valid_c = neighbor_c(valid_mask);
        
        % 第二步过滤：只保留邻域位置值为1的情况
        valid_mask = B(sub2ind([rows, cols], valid_r, valid_c)) == 1;
        valid_r = valid_r(valid_mask);
        valid_c = valid_c(valid_mask);
        
        % 转换为线性下标，标记邻接关系
        neighbor_linear = sub2ind([rows, cols], valid_r, valid_c);
        A(linear_idx(k), neighbor_linear) = 1;
    end
    
    % 确保邻接矩阵对称（i-j邻接则j-i必然邻接）
    A = A | A';
end

方案2：基于线性下标偏移的高效实现 #

这个版本省去了二维坐标和线性下标的转换开销，速度更快，适合处理大型矩阵：

function A = generate_adjacency_8_fast(B)
    [rows, cols] = size(B);
    total_elem = rows * cols;
    A = sparse(total_elem, total_elem);
    
    % 直接定义8邻域对应的线性下标偏移量（基于矩阵的列数计算）
    linear_offsets = [-cols-1, -cols, -cols+1, -1, 1, cols-1, cols, cols+1];
    
    % 找出所有值为1的线性下标
    linear_idx = find(B == 1);
    
    for k = 1:length(linear_idx)
        current_idx = linear_idx(k);
        % 生成所有邻域的线性下标
        neighbor_idx = current_idx + linear_offsets;
        
        % 过滤超出矩阵范围的下标
        valid_mask = (neighbor_idx >= 1) & (neighbor_idx <= total_elem);
        neighbor_idx = neighbor_idx(valid_mask);
        
        % 过滤邻域值不为1的情况
        valid_mask = B(neighbor_idx) == 1;
        neighbor_idx = neighbor_idx(valid_mask);
        
        % 标记邻接关系
        A(current_idx, neighbor_idx) = 1;
    end
    
    % 对称化处理
    A = A | A';
end

关键优化点说明 #

• 稀疏矩阵：用sparse创建邻接矩阵，对于大规模矩阵，能避免存储大量0元素，节省内存同时提升计算速度。
• 批量处理：通过预定义偏移量一次性生成所有邻域，避免逐个方向判断，减少循环内的操作次数。
• 双重过滤：先过滤边界外的无效位置，再过滤值不为1的位置，只保留符合条件的邻接对，避免无效计算。
• 对称化：最后通过A | A'确保邻接矩阵的对称性，弥补遍历过程中可能只标记单向邻接的问题。

内容的提问来源于stack exchange，提问作者Shew