Python实现湖泊内岛屿填充为水域的算法优化问询

现有一个ndarray数组，每个单元格为陆地(1)或水域(0)，背景及边界均为陆地，内部包含湖泊，部分湖泊中存在岛屿（完全被水域包围的连通陆地像素）。需要实现算法自动将所有岛屿的数值改为0（填充为水域），同时保留未被包围的背景陆地。

本人尝试基于DFS实现，但递归逻辑生疏，编写了判断像素是否为岛屿陆地的代码，测试人工数组及Sentinel影像后结果异常，认为问题出在基准条件设置上，寻求技术帮助。

# 注：1代表水域，0代表陆地
def isInside(img,x,y):
    # img[:,:,1]是和img同尺寸的数组，0表示未访问，1表示已访问
    dim = img[:,:,0].shape

    # 如果超出边界，返回False
    if(x<0 or x>=dim[1] or y<0 or y>=dim[0]):
        return False

    # 已访问且是陆地，返回True
    if(img[y][x][1] == 1 and img[y][x][0] == 0):
        return True

    # 是水域，标记已访问并返回True
    if (img[y][x][0] == 1):
        img[y][x][1] = 1 
        return True
    
    # 是陆地且在边界上，标记已访问并返回False
    if ((x==0 or x == dim[1]-1 or y == 0 or y == dim[0]-1) and (img[y][x][0] == 0)):
        img[y][x][1] = 1
        return False

    # 是未访问的陆地
    if img[y][x][0] == 0:
        # 标记已访问
        img[y][x][1] = 1
        # 如果所有相邻节点都是水域或内部陆地，返回True
        if(isInside(img,x+1,y) and
            isInside(img,x-1,y) and
            isInside(img,x,y+1) and
            isInside(img,x,y-1)):
            return True
    return False

你的DFS逻辑存在几个核心问题：

• 判断顺序错误：边界陆地的判断被放在已访问判断之后，导致边界陆地被标记访问后会被误判为内部岛屿。
• 递归条件错误：用and判断所有相邻节点的逻辑不成立——内部岛屿只需要所有连通路径无法到达边界，而非每个相邻节点都必须满足条件，这种逻辑会漏判或误判。
• 职责混淆：当前函数同时承担访问标记、边界判断、岛屿识别三个任务，逻辑耦合度高，容易出现状态传递混乱。

更简洁可靠的思路是反向标记法：

1. 先标记所有与边界陆地连通的背景陆地（这些是需要保留的）。
2. 遍历数组，将未被标记的陆地（即岛屿）改为水域。

实现代码示例：

import numpy as np

def mark_background_land(arr, visited):
    rows, cols = arr.shape
    # 用栈实现DFS，避免递归深度超限
    stack = []
    # 先将所有边界陆地加入栈
    for i in range(rows):
        for j in [0, cols-1]:
            if arr[i][j] == 0 and not visited[i][j]:
                stack.append((i,j))
                visited[i][j] = True
    for j in range(cols):
        for i in [0, rows-1]:
            if arr[i][j] == 0 and not visited[i][j]:
                stack.append((i,j))
                visited[i][j] = True
    # 遍历所有连通的背景陆地
    dirs = [(-1,0),(1,0),(0,-1),(0,1)]
    while stack:
        y, x = stack.pop()
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if 0<=ny<rows and 0<=nx<cols and arr[ny][nx]==0 and not visited[ny][nx]:
                visited[ny][nx] = True
                stack.append((ny, nx))

def remove_islands(arr):
    rows, cols = arr.shape
    visited = np.zeros_like(arr, dtype=bool)
    # 标记所有需要保留的背景陆地
    mark_background_land(arr, visited)
    # 将未标记的陆地（岛屿）改为水域
    for i in range(rows):
        for j in range(cols):
            if arr[i][j] == 0 and not visited[i][j]:
                arr[i][j] = 1
    return arr

代码说明 #

• 用栈实现DFS，避免大尺寸影像下递归深度超过Python默认限制。
• 先标记边界陆地及其连通区域，确保所有需要保留的背景陆地被识别。
• 最后遍历数组，精准定位并修改岛屿像素。

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