递归处理PPM图像矩阵遇递归限制，求岛屿颜色平均解决方案

问题背景 #

我们将PPM格式图像转换为矩阵形式，示例矩阵如下：

208 21  139 96  38  169 0   172 123 115 172 154 0   227 153 29  234 109 222 39
5   241 176 62  133 69  0   152 145 154 99  93  0   74  85  47  241 23  207 45
25  92  229 196 163 139 0   189 76  0   0   220 0   2   152 0   79  44  249 203
5   8   75  228 108 125 0   129 0   39  0   18  0   144 30  0   0   0   172 54
222 3   25  196 240 0   0   1   0   11  0   226 0   202 20  203 235 169 0   93
238 184 0   0   0   0   249 123 0   178 0   252 0   91  152 49  119 200 0   31
0   0   220 170 165 11  148 0   0   52  0   233 0   241 131 83  173 196 0   0
204 0   0   0   0   0   0   0   92  225 0   0   0   141 159 182 0   0   0   143
141 178 217 74  0   174 243 164 200 98  138 122 67  44  34  96  0   0   68  118
133 227 39  0   0   118 234 247 38  0   0   0   0   0   0   0   243 247 108 153
54  185 145 0   0   9   102 9   57  0   159 210 128 152 171 4   0   0   118 139
225 161 52  17  0   0   115 129 0   0   170 0   0   0   0   83  45  0   204 91
212 57  167 39  174 0   0   0   0   89  178 0   197 0   0   219 0   0   0   0
173 113 78  184 115 48  107 253 0   0   53  216 0   0   109 245 0   102 42  26
251 187 218 234 139 140 84  101 0   0   64  102 0   0   0   0   106 111 237 26
164 142 31  222 63  218 252 0   0   228 151 76  169 0   95  153 168 195 157 127
141 157 99  86  156 0   0   109 0   227 97  54  0   0   144 11  237 169 67  53
171 211 226 0   0   156 208 207 0   0   0   0   0   249 56  229 194 48  216 197
29  200 99  0   188 160 178 199 145 244 0   0   162 163 254 201 0   120 239 5
51  134 175 0   193 216 79  49  89  86  180 0   0   0   0   0   35  37  42  2

矩阵中0代表墙体，正数代表颜色值，墙体（含对角墙体）将矩阵分割为多个独立的颜色“岛屿”区域（仅上下左右相邻的非墙体像素属于同一岛屿）。需求是识别每个岛屿的所有颜色值，将岛屿内所有颜色值替换为该区域颜色的平均值。

原代码问题分析 #

原递归代码存在以下问题：

• 未标记已访问像素，导致同一岛屿的像素被重复处理，无法区分不同岛屿
• 递归深度超过Python默认限制时，会触发RecursionError
• 仅收集颜色值，未实现平均值替换逻辑

原代码：

def rec_appender(img,r,c,lst):
    n_rows,n_cols=len(img),len(img[0])
    if r<0 or c<0 or r>=n_rows or c>=n_cols: # check out actual borders
        return
    if img[r][c] == 0:
        return
    lst.append(img[r][c])
    neigh_list=[[-1,0],[+1,0],[0,-1],[0,+1]]
    for neigh in neigh_list:
        rec_appender(img,r+neigh[0],c+neigh[1],lst)


def averager(img):
    lst = []
    n_rows,n_cols=len(img),len(img[0])
    for r in range(0,n_rows):
        for c in range(0,n_cols):
            if img[r][c] != 0: # is wall
                rec_appender(img,r,c,lst)

改进方案 #

使用**广度优先搜索（BFS）**替代递归，避免栈溢出；用访问矩阵标记已处理像素；逐个处理每个岛屿，计算平均值后替换所有像素值。

完整实现代码 #

def process_islands(img):
    if not img or not img[0]:
        return img
    
    n_rows = len(img)
    n_cols = len(img[0])
    # 创建访问矩阵，标记是否已处理该像素
    visited = [[False for _ in range(n_cols)] for _ in range(n_rows)]
    # 定义上下左右四个方向
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    
    for r in range(n_rows):
        for c in range(n_cols):
            # 仅处理非墙体且未访问的像素
            if img[r][c] != 0 and not visited[r][c]:
                # BFS队列，存储像素坐标
                queue = [(r, c)]
                visited[r][c] = True
                # 收集当前岛屿的颜色值和坐标
                island_colors = []
                island_coords = []
                
                while queue:
                    curr_r, curr_c = queue.pop(0)
                    island_colors.append(img[curr_r][curr_c])
                    island_coords.append((curr_r, curr_c))
                    
                    # 遍历四个方向的邻居
                    for dr, dc in directions:
                        nr = curr_r + dr
                        nc = curr_c + dc
                        # 检查邻居是否在矩阵范围内、非墙体且未访问
                        if 0 <= nr < n_rows and 0 <= nc < n_cols:
                            if img[nr][nc] != 0 and not visited[nr][nc]:
                                visited[nr][nc] = True
                                queue.append((nr, nc))
                
                # 计算岛屿颜色平均值（取整，根据需求可改为保留小数）
                avg_color = sum(island_colors) // len(island_colors)
                # 替换岛屿内所有像素为平均值
                for (ir, ic) in island_coords:
                    img[ir][ic] = avg_color
    
    return img

代码说明 #

1. 访问矩阵：visited矩阵记录每个像素是否已处理，避免重复访问同一岛屿的像素
2. BFS遍历：用队列存储待处理的像素坐标，逐层扩展邻居，避免递归深度限制
3. 岛屿处理：每个岛屿收集完成后，计算颜色平均值，再遍历岛屿坐标替换所有像素值
4. 边界处理：先检查矩阵是否为空，遍历邻居时确保坐标在矩阵范围内

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