使用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

上面的功能是这样的:

  1. 选择颜色
  2. 从颜色计算平均值
  3. False如果平均值非常接近白色,则立即返回
  4. 计算颜色的标准偏差
  5. True如果标准偏差大于任何颜色的阈值,则返回(进一步递归)
  6. 否则返回 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

原文发布于微信公众号 - 相约机器人(xiangyuejiqiren)

原文发表时间:2019-08-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券