开始
近来通过项目接触了一个填充算法—洪水算法。
洪水算法是一种局部填充的方法,算法将同一区域的颜色填充成同一颜色,从起始坐标开始,往四周扩散。所以有四邻域像素填充,八领域像素填充,还有基于扫描线的洪水填充方法。这三种算法详细可以在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