# Implementing a Photo Stylizer in Python using a QuadTree Algorithm

Learn how to write a python script to create a quadtree based filter for stylizing photos

So recently, I discovered a project done by Michael Fogleman called Quadtree Art. It inspired me to try and code my own version of the project. This is what I will talk about in this article, how to implement your own Quadtree art program, just as I’ve done here: github.com/ribab/quadart

Above is a generated image I made from a picture of an an apple I found on freepik.com by kstudio. The original looks like this:

My algorithm essentially continues to divide the image up into quadrants only if the standard deviation of colors is too high.

To illustrate the algorithm working, I implemented a max-recursion feature to QuadArt, created 10 different images of different recursion depths using this shell command: `for i in {1..10}; do ./quadart.py apple.jpg -o r-out/apple-r$i.jpg -m $i --thresh 25; done`

, and then I generated the PNG using ImageMagick through the command `convert -delay 40 -loop 0 *.jpg apple-r.gif`

. The GIF is below, showing quadart magic in action.

# The QuadArt Algorithm, in simple terms

Even though my program QuadArt takes up 181 lines of code, the actual recursive algorithm used for generating the QuadArt can be described in only 8 lines

`class QuadArt:`

...

1 def recursive_draw(self, x, y, w, h):

'''Draw the QuadArt recursively

'''

2 if self.too_many_colors(int(x), int(y), int(w), int(h)):

3 self.recursive_draw(x, y, w/2.0, h/2.0)

4 self.recursive_draw(x + w/2.0, y, w/2.0, h/2.0)

5 self.recursive_draw(x, y + h/2.0, w/2.0, h/2.0)

6 self.recursive_draw(x + w/2.0, y + h/2.0, w/2.0, h/2.0)

7 else:

8 self.draw_avg(x, y, w, h)

The above algorithm is pulled directly from my code. `class QuadArt`

is the class holding the `imageio`

image data, `wand`

drawing canvas, and the standard deviation threshold. `x`

, `y`

, `w`

, `h`

, are passed into the function to specify the x,y location of the top-left corner of the currently-being-analyzed sub-image, along with it's width and height.

# Debugging slow QuadArt generation

Originally, I implemented the entire QuadArt program using the Python Wand module, which uses ImageMagick under the hood. This library renders circles beautifully. After coding through my first pass of implementing the quad-tree based photo filter, I ran into an issue where the code was taking way too long to process. As it turns out, having Wand check the color of every single pixel takes way too long for calculating standard deviation, and Wand had no built-in feature for performing this kind of analysis. Also, it’s difficult for me to tell whether my code is stuck when nothing is being displayed to the screen.

In order to tell whether my code was making any progress, I needed some kind of loading bar. However, loading bars are much easier with an iterative algorithm where you know exactly how many iterations are needed for the algorithm to finsh. With a quad-tree based recursive algorithm, I do know that the recursive-depth of 1 will run at most 4 times, and depth 2 will run at most 16 times, and so on. So taking this idea into account I implemented an addition to the algorithm to display a loading bar in the terminal while the program is executing. This loading bar tracks the number of times the recursive algorithm executes at depth 3.

For the loading bar function to track the progress of `recursive_draw()`

, I only needed to track its exit points, and track the current depth of recursion. The 2 kinds of exit points is when `recursive_draw()`

either recursed further or didn't. Here is the `recursive_draw()`

function modified to call `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()`

has logic to calculate progress only while depth<=3, but I still needed to check if the current `self.recurse_depth`

is equal to 3 in the 1st exit point of `recursive_draw()`

or else there will be redundant calls to `loading_bar()`

due to the recursion.

This is what `loading_bar()`

looks like

`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='')

For monitoring your own recursive function, you can easily stick this at the top of your python code, modify `recursion_spread`

to be how many times the function calls itself every time it recurses, and then call `loading_bar()`

from all your recursive function's end-points, making sure it's only called once per branch of recursion.

# Image analysis with imageio and numpy

For the threshold of `recursive_draw()`

on whether to split out into more quadrants, the function `too_many_colors()`

calculates the standard deviation of red, green, and blue, and returns `True`

if the standard deviation passes a threshold. For QuadArt generation, I find a nice threshold is about 25 STD or else the image becomes either too pixelated or too fine-grain. The python image-analysis library `imageio`

is perfect for this kind of analysis since it plugs right into `numpy`

for fast statistic calculations.

My initial setup for image analysis via `imageio`

and `numpy`

is as follows:

- Import imageio and numpy

`import imageio`

import numpy as np

2. Read image using imageio (filename is the name of the image we are analyzing)

`img = imageio.imread(filename)`

3. Choose portion of image we are analyzing. Effectively cropping img. “left”, “right”, “up”, and “down” specify where to crop img.

`self.img = self.img[up:down,left:right]`

4. Find image width and height

`input_width = img.shape[1]`

input_height = img.shape[0]

5. Ensure img is square by subtracting the difference of the longer side by the shorter side

`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]

6. Now the imageio object “img” can be used for calculating standard deviation like so:

# 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)

This is how my program QuadArt calculates whether the `recursive_draw()`

function sould recurse further due to a high color deviation. Take a look at `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

The above function does this:

- Selects colors
- Calculates averages from the colors
- Returns
`False`

right away if average is pretty close to white - Calculates standard deviations from colors
- Returns
`True`

(to recurse further) if standard deviation is greater than a threshold for any of the colors - Otherwise returns
`False`

# Finally displaying the circles

Now to the easy part: displaying circles in `wand`

.

My strategy for performing the image filter is to build the resulting image from a blank canvas.

This is a template for how to draw things using 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')

The aspect-ratio of the resulting canvas for `QuadArt`

is always square so that way QuadArt's recursive algorithm can split the image evenly into quadrants. By default I use `output_size=512`

since 512 is a power of 2, and can be continuously split in half into more quadrants without loosing resolution.

However the size of the input-image can vary. In order to account for this I divide the desired outptu size by the width of the cropped input image like so:

`output_scale = float(output_size) / input_width`

The function I used above in `recursive_draw()`

is `draw_avg()`

. This is a simple function that computes the average color of an input image within a boundary, and then draws a circle within a box (or a square if the user prefers).

`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)

The function `get_color()`

first grabs a cropped section of the input image (in `imageio`

format), and then computes the averages of red, green, and blue within that cropped section, and then creates a `wand.color.Color`

object based on the computed average colors.

`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

The function `draw_in_box()`

draws either a circle or a square within a defined box, which is the quadrant that was calculated earlier by the `too_many_colors()`

to have a low enough deviation. Before drawing to the canvas, the coordinates along with width and height are multiplied by `output_scale`

. And the fill color of `wand.drawing`

is set to the previously calculated average color. Then the circle or square is drawn to the canvas.

`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)

There you have it! This is how I implemented the Quadtree Photo Stylizer, and how you can implement the same, or be inspired and create your own algorithm for stylizing your photos.

You can view the entire code here: github.com/ribab/quadart/blob/master/quadart.py

*Originally published at **http://www.codingwithricky.com**.*