终极表情包生成器 - 2
接上回。在写程序的时候，发现性能的一大瓶颈就是ImageDraw.floodfill()函数。最开始用的是库里面自带的函数，结果发现实在太慢。自己略作修改后稍稍提升了一点效率，但还是不够快。当时决定有空一定研究一下应该如何改进。
原始代码
def _color_diff(rgb1, rgb2):
"""
Uses 1-norm distance to calculate difference between two rgb values.
"""
return abs(rgb1[0]-rgb2[0]) + abs(rgb1[1]-rgb2[1]) + abs(rgb1[2]-rgb2[2])
def floodfill_o(image, xy, value, border=None, thresh=0):
"""
(experimental) Fills a bounded region with a given color.
:param image: Target image.
:param xy: Seed position (a 2-item coordinate tuple). See
:ref:`coordinate-system`.
:param value: Fill color.
:param border: Optional border value. If given, the region consists of
pixels with a color different from the border color. If not given,
the region consists of pixels having the same color as the seed
pixel.
:param thresh: Optional threshold value which specifies a maximum
tolerable difference of a pixel value from the 'background' in
order for it to be replaced. Useful for filling regions of non-
homogeneous, but similar, colors.
"""
# based on an implementation by Eric S. Raymond
pixel = image.load()
x, y = xy
try:
background = pixel[x, y]
if _color_diff(value, background) <= thresh:
return # seed point already has fill color
pixel[x, y] = value
except (ValueError, IndexError):
return # seed point outside image
edge = [(x, y)]
if border is None:
while edge:
newedge = []
for (x, y) in edge:
for (s, t) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
try:
p = pixel[s, t]
except IndexError:
pass
else:
if _color_diff(p, background) <= thresh:
pixel[s, t] = value
newedge.append((s, t))
edge = newedge
else:
while edge:
newedge = []
for (x, y) in edge:
for (s, t) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
try:
p = pixel[s, t]
except IndexError:
pass
else:
if p != value and p != border:
pixel[s, t] = value
newedge.append((s, t))
edge = newedge
可以看到，原始代码用的是最基础的4邻接涂色的方法。但是，在选择邻接像素的过程中出了一点问题。通过计数发现，它遍历了所有需要涂色的像素将近四次！仔细分析一番发现，似乎它每次进入循环时有一些重复的点会混进去，导致还需要判断该点是否已经涂过色，从而造成了效率的极大下降。
那么该如何改进呢？通过查找了解到，这个算法最简单、最直观的实现就是头递归了。简单敲了个头递归的代码，却怎么也跑不通：Python提示递归次数超过了限制。也真是，一张图片动辄几百万几千万像素，递归那么多次Python肯定不爽啊。经过测试，递归的方法能处理的图片尺寸甚至小于1000*1000像素。遂放弃递归。
我的改进1
接下来第一个想法就是用hashtable，C++里的unorderedmap。对应Python的数据类型就是dict和set。理论上讲，这些牺牲空间换时间的数据结构查找时间复杂度都是O(1)，通过hash function找下标的。于是我把所有节点都加到一个大的table里，每次遍历时找是否已经遍历过了即可。但是，如你所料，每次需要把遍历后的像素坐标加到表里，最后形成的便是一个囊括了所有涂色后点坐标的巨大数据体。涂色范围越大占内存越大，仅仅处理一张两千万像素的图片就炸掉了我接近3GB内存……😰
我的改进2
显然，应该通过一些方法避免记录遍历过的所有像素。顺势躺到麻将席上，看着一块块竹席，考虑该如何优化。像素像涟漪般四面散开，只需记录当前波峰和前一时刻的波谷。没错，表里只用存上个迭代中的像素，以及本次迭代中新增的像素即可。
def floodfill(image, xy, value, border=None, thresh=0):
pixel = image.load()
x, y = xy
try:
background = pixel[x, y]
if _color_diff(value, background) <= thresh:
return # seed point already has fill color
pixel[x, y] = value
except (ValueError, IndexError):
return # seed point outside image
edge = {(x, y)}
full_edge = set() # use a set to record each unique pixel processed
if border is None:
while edge:
new_edge = set()
for (x, y) in edge: # 4 adjacent method
for (s, t) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
if (s, t) in full_edge:
continue # if already processed, skip
try:
p = pixel[s, t]
except IndexError:
pass
else:
if _color_diff(p, background) <= thresh:
pixel[s, t] = value
new_edge.add((s, t))
full_edge.add((s, t))
full_edge = edge # do not record useless pixels to reduce memory consumption
edge = new_edge
else:
while edge:
new_edge = set()
for (x, y) in edge:
for (s, t) in ((x+1, y), (x-1, y), (x, y+1), (x, y-1)):
if (s, t) in full_edge:
continue
try:
p = pixel[s, t]
except IndexError:
pass
else:
if p != value and p != border:
pixel[s, t] = value
new_edge.add((s, t))
full_edge.add((s, t))
full_edge = edge
edge = new_edge
def _color_diff(rgb1, rgb2):
"""
Uses 1-norm distance to calculate difference between two rgb values.
"""
return abs(rgb1[0]-rgb2[0]) + abs(rgb1[1]-rgb2[1]) + abs(rgb1[2]-rgb2[2])
另外，本来还想把color_diff也一并修正，模板化处理RGB/RGBA和错误输入的，但懒得再去查色彩标准里容差究竟是否包含透明度了。哪位同学有兴趣可以继续给PIL提PR。
最后
PIL虽然历久弥新，但源代码里还是有不少亟待改进的地方的。要不是借了Python写起来容易的光儿，我宁可写C++/OpenCV。
Leave a Comment