3D二值numpy数组非暴力最大内接立方体求解及分辨率判断问询

高效最大内接立方体求解算法 #

针对0/1构成的3D numpy数组，可使用3D动态规划（DP）算法替代暴力枚举求解最大内接全1立方体，时间复杂度仅为O(X×Y×Z)，其中X、Y、Z为数组三个维度的长度，远优于暴力方案的高阶复杂度，适配大尺寸3D数组的计算需求。

算法核心逻辑 #

定义三维DP数组dp[i][j][k]，表示以坐标(i,j,k)为右下角顶点的最大全1立方体的边长，递推规则如下：

• 若当前坐标原始值为0：dp[i][j][k] = 0，无法构成全1立方体
• 若当前坐标原始值为1：dp[i][j][k]等于相邻7个方向DP值的最小值加1，对应三个轴向、三个面、对角线方向的立方体约束
• 边界位置（三个坐标任意一个为0）的DP值直接等于原始数组的对应值
  遍历过程中记录全局最大DP值，即为所求最大内接立方体的边长。

参考Python实现 #

import numpy as np

def get_max_cube_edge(bin_3d_arr: np.ndarray) -> int:
    x_dim, y_dim, z_dim = bin_3d_arr.shape
    dp = np.zeros_like(bin_3d_arr, dtype=np.int32)
    # 初始化边界
    dp[0, :, :] = bin_3d_arr[0, :, :]
    dp[:, 0, :] = bin_3d_arr[:, 0, :]
    dp[:, :, 0] = bin_3d_arr[:, :, 0]
    max_edge = dp.max()
    # 递推计算
    for i in range(1, x_dim):
        for j in range(1, y_dim):
            for k in range(1, z_dim):
                if bin_3d_arr[i, j, k] == 1:
                    dp[i, j, k] = min(
                        dp[i-1, j, k], dp[i, j-1, k], dp[i, j, k-1],
                        dp[i-1, j-1, k], dp[i-1, j, k-1], dp[i, j-1, k-1],
                        dp[i-1, j-1, k-1]
                    ) + 1
                    max_edge = max(max_edge, dp[i, j, k])
                else:
                    dp[i, j, k] = 0
    return max_edge

最低识别分辨率的快捷技术路径 #

如果核心需求仅为判定可识别形状的最低分辨率，不需要输出最大立方体的具体参数，可直接使用多尺度下采样校验法，计算效率更高：

• 下采样规则：采用最小值滤波对原始数组做整数倍下采样，滤波窗口内存在0则下采样后对应位置设为0，否则为1，保证下采样后的1区域完全属于原始形状的有效区域
• 校验逻辑：从高到低依次降低分辨率，每次下采样后校验形状的预设识别条件（如连通性、特征点完整性、体积占比等），直到不满足判定要求为止，上一个符合要求的分辨率即为最低可识别分辨率

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