作者 | 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