使用QuadTree算法在Python中实现Photo Stylizer
使用QuadTree算法在Python中实现Photo Stylizer
作者 | Richard Barrera
来源 | Medium
编辑 | 代码医生团队
最近发现迈克尔·弗格曼（Michael Fogleman）完成了一个叫做四叉树艺术的项目。它激发了尝试编写自己的项目版本。这就是将在本文中讨论的，如何实现自己的Quadtree艺术程序，就像在这里所做的那样：
github.com/ribab/quadart
上图是用kstudio在freepik.com上找到的苹果图片制作的图像。原件看起来像这样：
只有当颜色的标准偏差太高时，算法才会基本上继续将图像划分为象限。
为了说明算法工作，实现了QuadArt的最大递归功能，使用这个shell命令创建了10个不同递归深度的不同图像：for i in {1..10}; do ./quadart.py apple.jpg -o r-out/apple-r$i.jpg -m $i --thresh 25; done 然后通过命令使用 ImageMagick 生成PNG convert -delay 40 -loop 0 *.jpg apple-r.gif 。GIF在下方，展示了四方魔法。
简单来说，QuadArt算法
尽管程序QuadArt占用了181行代码，但用于生成QuadArt的实际递归算法只能在8行中描述
class QuadArt:
...
def recursive_draw(self, x, y, w, h):
'''Draw the QuadArt recursively
'''
if self.too_many_colors(int(x), int(y), int(w), int(h)):
self.recursive_draw(x, y, w/2.0, h/2.0)
self.recursive_draw(x + w/2.0, y, w/2.0, h/2.0)
self.recursive_draw(x, y + h/2.0, w/2.0, h/2.0)
self.recursive_draw(x + w/2.0, y + h/2.0, w/2.0, h/2.0)
else:
self.draw_avg(x, y, w, h)以上算法直接从代码中提取。class QuadArt是包含imageio图像数据，wand绘制画布和标准偏差阈值的类。x，y，w，h，被传递到函数来指定x，则当前感分析后的子图像的左上角的y位置，沿着与它的宽度和高度。
调试缓慢的QuadArt生成
最初使用Python Wand模块实现了整个QuadArt程序，该模块使用了ImageMagick。这个库精美地渲染圆圈。在第一次实现基于四叉树的照片过滤器的编码后，遇到了一个代码占用时间过长的问题。事实证明，让Wand检查每个像素的颜色对于计算标准偏差来说太长了，并且Wand没有用于执行这种分析的内置功能。此外当没有在屏幕上显示任何内容时，很难判断代码是否卡住了。
为了判断代码是否有任何进展，需要某种加载条。但是使用迭代算法可以更加轻松地加载条形图，可以准确地知道算法需要多少次迭代才能完成。使用基于四叉树的递归算法，知道递归深度1最多可运行4次，深度2最多运行16次，依此类推。因此考虑到这个想法，实现了对算法的补充，以在程序执行时在终端中显示加载条。此加载栏跟踪递归算法在深度3处执行的次数。
对于跟踪进度的加载栏功能 recursive_draw()，只需要跟踪其退出点，并跟踪当前的递归深度。两种退出点是 recursive_draw() 进一步递归或不进行递归。这是 recursive_draw() 修改为调用的函数 loading_bar()：
def recursive_draw(self, x, y, w, h):
'''Draw the QuadArt recursively
'''
if self.too_many_colors(int(x), int(y), int(w), int(h)):
self.recurse_depth += 1
self.recursive_draw(x, y, w/2.0, h/2.0)
self.recursive_draw(x + w/2.0, y, w/2.0, h/2.0)
self.recursive_draw(x, y + h/2.0, w/2.0, h/2.0)
self.recursive_draw(x + w/2.0, y + h/2.0, w/2.0, h/2.0)
self.recurse_depth -= 1
if self.recurse_depth == 3:
loading_bar(self.recurse_depth)
else:
self.draw_avg(x, y, w, h)
loading_bar(self.recurse_depth)loading_bar() 有逻辑只在深度<= 3的情况下计算进度，但是仍然需要 self.recurse_depth 在第一个出口点检查电流是否等于3，recursive_draw() 否则会 loading_bar() 因递归而产生冗余调用。
这就是 loading_bar() 看起来像
def loading_bar(recurse_depth):
global load_progress
global start_time
load_depth=3
recursion_spread=4
try:
load_progress
start_time
except:
load_progress = 0
start_time = time.time()
print('[' + ' '*(recursion_spread**load_depth) + ']\r', end='')
if recurse_depth <= load_depth:
load_progress += recursion_spread**(load_depth - recurse_depth)
cur_time = time.time()
time_left = recursion_spread**load_depth*(cur_time - start_time)/load_progress \
- cur_time + start_time
print('[' + '='*load_progress \
+ ' '*(recursion_spread**load_depth - load_progress) \
+ '] ' \
+ 'time left: {} secs'.format(int(time_left)).ljust(19) \
+ '\r', end='')为了监视自己的递归函数，可以很容易地将它放在python代码的顶部，修改 recursion_spread 为每次递归时函数调用自身的次数，然后 loading_bar() 从所有递归函数的端点调用，确保它是每个递归分支只调用一次。
使用imageio和numpy进行图像分析
对于 recursive_draw() 是否分割成更多象限的阈值，该函数 too_many_colors() 计算红色，绿色和蓝色True的标准偏差，并在标准偏差超过阈值时返回。对于QuadArt生成，发现一个漂亮的阈值大约是25 STD，否则图像变得太像素化或太细粒度。python图像分析库imageio非常适合这种分析，因为它可以直接插入numpy以进行快速统计计算。
用于经由图像分析初始设置imageio和numpy如下：
import imageio
import numpy as np使用imageio读取图像（文件名是正在分析的图像的名称）
img = imageio.imread(filename)选择正在分析的图像部分。有效地裁剪img。“left”，“right”，“up”和“down”指定img的裁剪位置。
self.img = self.img[up:down,left:right]找到图像的宽度和高度
input_width = img.shape[1]
input_height = img.shape[0]通过减去较短边的较长边的差异，确保img为正方形
if input_width < input_height:
difference = input_height - input_width
subtract_top = int(difference/2)
subtract_bot = difference - subtract_top
img = img[subtract_top:-subtract_bot,:]
elif input_height < input_width:
difference = input_width - input_height
subtract_left = int(difference/2)
subtract_right = difference - subtract_left
img = img[:,subtract_left:-subtract_right]现在imageio对象“img”可用于计算标准偏差，如下所示：
# Selecting colors
red = img[:,:,0]
green = img[:,:,1]
blue = img[:,:,2]
# Calculating averages from colors
red_avg = np.average(red)
green_avg = np.average(green)
blue_avg = np.average(blue)
# Calculating standard deviations from colors
red_std = np.std(red)
green_std = np.std(green)
blue_std = np.std(blue)这就是程序QuadArt计算该recursive_draw()函数是否由于高颜色偏差而进一步递归的方式。看一眼too_many_colors()
class QuadArt:
...
def too_many_colors(self, x, y, w, h):
if w * self.output_scale <= 2 or w <= 2:
return False
img = self.img[y:y+h,x:x+w]
red = img[:,:,0]
green = img[:,:,1]
blue = img[:,:,2]
red_avg = np.average(red)
green_avg = np.average(green)
blue_avg = np.average(blue)
if red_avg >= 254 and green_avg >= 254 and blue_avg >= 254:
return False
if 255 - red_avg < self.std_thresh and 255 - green_avg < self.std_thresh \
and 255 - blue_avg < self.std_thresh:
return True
red_std = np.std(red)
if red_std > self.std_thresh:
return True
green_std = np.std(green)
if green_std > self.std_thresh:
return True
blue_std = np.std(blue)
if blue_std > self.std_thresh:
return True
return False上面的功能是这样的：
- 选择颜色
- 从颜色计算平均值
- False如果平均值非常接近白色，则立即返回
- 计算颜色的标准偏差
- True如果标准偏差大于任何颜色的阈值，则返回（进一步递归）
- 否则返回 False
最后显示圆圈
现在到了简单的部分：在中显示圆圈wand。
执行图像过滤器的策略是从空白画布构建结果图像。
这是如何使用Wand绘制内容的模板
# Import Wand
from wand.image import Image
from wand.display import Display
from wand.color import Color
from wand.drawing import Drawing
# Set up canvas to draw on
canvas = Image(width = output_size,
height = output_size,
background = Color('white'))
canvas.format = 'png'
draw = Drawing()
# Draw circles and rectangles and anything else here
draw.fill_color = Color('rgb(%s,%s,%s)' % (red, green, blue))
draw.circle((x_center, y_center), (x_edge, y_edge))
draw.rectangle(x, y, x + w, y + h)
# Write drawing to the canvas
draw(canvas)
# If you want to display image to the screen
display(canvas)
# If you want to save image to a file
canvas.save(filename='output.png')生成的画布的宽高比QuadArt总是为正方形，因此QuadArt的递归算法可以将图像均匀地分割为象限。默认情况下，使用output_size=512512是2的幂，并且可以连续分成两半而不会失去分辨率。
但是输入图像的大小可能会有所不同。为了解释这一点，将所需的outptu大小除以裁剪的输入图像的宽度，如下所示：
output_scale = float(output_size) / input_width上面使用的功能 recursive_draw() 是 draw_avg() 。这是一个简单的函数，可以计算边界内输入图像的平均颜色，然后在一个框内绘制一个圆（如果用户喜欢，则绘制一个正方形）。
class QuadArt:
...
def draw_avg(self, x, y, w, h):
avg_color = self.get_color(int(x), int(y), int(w), int(h))
self.draw_in_box(avg_color, x, y, w, h)该函数 get_color() 首先抓取输入图像的裁剪部分（imageio格式），然后计算该裁剪部分中的红色，绿色和蓝色的平均值，然后 wand.color.Color 根据计算的平均颜色创建一个对象。
class QuadArt:
...
def get_color(self, x, y, w, h):
img = self.img[y : y + h,
x : x + w]
red = np.average(img[:,:,0])
green = np.average(img[:,:,1])
blue = np.average(img[:,:,2])
color = Color('rgb(%s,%s,%s)' % (red, green, blue))
return color该函数 draw_in_box() 在定义的框内绘制圆形或正方形，这是先前由 too_many_colors() 具有足够低偏差计算的象限。在绘制到画布之前，坐标以及宽度和高度乘以 output_scale。并且填充颜色wand.drawing设置为先前计算的平均颜色。然后将圆形或方形绘制到画布上。
class QuadArt:
...
def draw_in_box(self, color, x, y, w, h):
x *= self.output_scale
y *= self.output_scale
w *= self.output_scale
h *= self.output_scale
self.draw.fill_color = color
if self.draw_type == 'circle':
self.draw.circle((int(x + w/2.0), int(y + h/2.0)),
(int(x + w/2.0), int(y)))
else:
self.draw.rectangle(x, y, x + w, y + h)这就是实现Quadtree Photo Stylizer的方法，以及如何实现它，或者启发并创建自己的算法来设置照片风格。
整个代码：
github.com/ribab/quadart/blob/master/quadart.py