洪水算法–python实现

开始

近来通过项目接触了一个填充算法—洪水算法。

洪水算法是一种局部填充的方法，算法将同一区域的颜色填充成同一颜色，从起始坐标开始，往四周扩散。所以有四邻域像素填充，八领域像素填充，还有基于扫描线的洪水填充方法。这三种算法详细可以在reference 1中看到。这三种方式的递归算法十分简单，但是遇到图片较大的情况下，则可能会出现栈溢出。

解决的方法则是通过人为设置存放扫描的起始坐标点的栈，来代替函数调用栈。通过比较简单。

算法

算法思路：
1.选择填充区域的起始点
2.入栈起始点
3.将起始点所在列填充颜色
4.将起始点的左右侧’起始点’压入栈
5.控制左右上下移动的范围在填充区域

以下程序大部分copy于reference 1中的实现，做了些许改动，来解决自己的问题。

代码

import numpy as np
import time
from PIL import Image

class Point:
    def __init__(self, x, y):
        self.x = x
        self.y = y

class Flood:

    def __init__(self, file, nc=255):

        org_img = Image.open(file)
        print(org_img)
        self.org_pix = np.array(org_img)  # 原始RGB格式数据

        im = org_img.convert('L')
        # print(org_img, im)
        self.pix = np.array(im)  # convert后的二维数据
        self.width, self.height = im.size
        self.sign = np.zeros((self.width, self.height))  # 标记访问过的位置

        self.nc = nc  # 需要填充的new color

        self.stack = []

    def init_stack(self, point):
        self.stack.append(point)

    def set_color(self, x, y):
        self.pix[x][y] = self.nc

    def get_color(self, x, y):
        return self.pix[x][y]

    def flood_fill_scan_line(self, x, y):
        oc = self.get_color(x, y)
        print('oc: ', oc)

        if oc == self.nc:
            print('{} <ERROR> filled area.'.format(time.ctime()))
            return

        self.stack.clear()

        self.stack.append(Point(x, y))

        while True:
            # print(len(self.stack))
            if len(self.stack) != 0:
                point = self.stack.pop()
            else:
                return
            if point.x == -1:
                return
            y_run = point.y  # y_run用来跑扫描线
            span_left, span_right = False, False  # 走单线标记
            while y_run >= 0 and abs(int(self.get_color(point.x, y_run))-int(oc)) < 5:
                y_run -= 1
            y_run += 1

            # while y_run < self.height and self.get_color(point.x, y_run) == oc:
            while y_run < self.height and abs(int(self.get_color(point.x, y_run))-int(oc)) < 5:
                print('x:', point.x, 'y: ', y_run, 'oc: ', self.get_color(point.x, y_run))
                self.set_color(point.x, y_run)
                self.org_pix[point.x][y_run][0] = self.nc
                self.org_pix[point.x][y_run][1] = self.nc
                self.org_pix[point.x][y_run][2] = self.nc
                # 往左
                if not span_left and point.x > 0 and abs(int(self.get_color(point.x-1, y_run))-int(oc)) < 5:
                    self.stack.append(Point(point.x-1, y_run))
                    span_left = True
                elif span_left and point.x > 0 and abs(int(self.get_color(point.x-1, y_run))-int(oc)) >= 5:
                    span_left = False

                # 往右
                if not span_right and point.x < self.width - 1 and abs(int(self.get_color(point.x+1, y_run))-int(oc)) < 5:
                    self.stack.append(Point(point.x+1, y_run))
                    span_right = True
                elif span_right and point.x < self.width - 1 and abs(int(self.get_color(point.x+1, y_run))-int(oc)) >= 5:
                    span_right = False
                y_run += 1


if __name__ == '__main__':
    flood = Flood('vacant.jpg', nc=10)
  
    flood.flood_fill_scan_line(1, 1)  # 外部

    flood.flood_fill_scan_line(15, 15)  # 内部
    img = Image.fromarray(flood.pix.astype('uint8')).convert('RGB')
    img.save('process.jpg')
    img = Image.fromarray(flood.org_pix.astype('uint8')).convert('RGB')
    img.save('org_process.jpg')

以下为运行结果，测试图片是32*32大小的图片，上传上来放大了就。。。

• 

• 

• 

Reference
1. https://blog.csdn.net/jia20003/article/details/8908464