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

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:

Original

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.

QuadArt GIF

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

1
2
3
4
5
6
7
8
9
10
11
12
  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.

Loading Bar

This loading bar GIF was generated using Byzanz with the help of xwininfo.

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():

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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:

  1. Import imageio and numpy

    1
    2
    import imageio
    import numpy as np

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

    1
    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.

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

  4. Find image width and height

    1
    2
    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

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    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:

    1. Selecting colors

      1
      2
      3
      red = img[:,:,0]
      green = img[:,:,1]
      blue = img[:,:,2]

    2. Calculating averages from colors

      1
      2
      3
      red_avg = np.average(red)
      green_avg = np.average(green)
      blue_avg = np.average(blue)

    3. Calculating standard deviations from colors

      1
      2
      3
      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()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
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:

  1. Selects colors
  2. Calcualtes averages from the colors
  3. Returns False right away if average is pretty close to white
  4. Calculates standard deviations from colors
  5. Returns True (to recurse further) if standard deviation is greater than a threshold for any of the colors
  6. 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
# 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:

1
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).

1
2
3
4
5
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.

1
2
3
4
5
6
7
8
9
10
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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

Get new posts by email:

Comments

Hint: To type code with Disqus, use 
<code><pre>insert.code.here()<pre/><code/>
▲