The New Turing Omnibus Chapter 47 Storing Images

The Chapter

We began the meeting by welcoming everyone and sharing copies of the chapter. Mike had kindly volunteered to shepherd this meeting and kicked off proceedings by asking how everyone had found the chapter.

The quadtree data structure was new to some of us and we briefly touched on the power of it as an abstraction over images: affording operations such as scaling, rotation and translation due to its design.

We wondered how the technique might apply to coloured images (rather than the entirely monochromatic examples given in the chapter) and how the difficulty of image operations compared with the manipulation of a raw bitmap.

With everyone confident that we understood the concept, we decided to mob program a solution in Ruby, concentrating on getting to a point where we could explore image operations rather than converting images (as "Encoding images as Quad Trees with Paul Battley" already covers that).

Chris took to his laptop in a rare Emacs sighting at the typically Vim-dominated club.

We began by modelling a quad tree with simple Ruby objects. We debated whether to use domain terms from the chapter and how many different concepts we needed to represent: e.g. did we need separate leaves, branches and trees?

We settled on:

• Leaf: an object containing a single boolean value determining the colour of that node with the ability to represent itself as a string (we chose # for true, . for false);
• QuadTree: an object with four corners (northeast, northwest, southwest and southeast) that could render itself as a string as with Leaf.

We began with a QuadTree containing four Leaf objects and checked that it rendered itself correctly, e.g.

white = Leaf.new(true)
black = Leaf.new(false)

puts white
#

puts black
.

tree = QuadTree.new(white, white, black, white)
puts tree.to_s
##
.#

We then discussed how to deal with rendering nested quad trees by mapping out how the corners of different trees interleaved on the whiteboard:

With some judicious use of Ruby's zip we were able to combine QuadTree and Leaf to render successfully:

puts QuadTree.new(tree, tree, tree, tree).to_s
####
.#.#
####
.#.#

As one of the benefits of quadtrees is their ability to compress images where entire quadrants are the same colour, we then tackled mixing both trees and leaves at the same time (where a leaf might be a single pixel or an entire quadrant). This introduced the notion of a tree and leaf having some given size.

We decided to use the example image of a cat given in the book to explore this.

We first explored rendering Leaf objects with an explicit size.

puts white.to_s(2)
##
##

We also added this logic (and explicit size) to the QuadTree so that we could render a tree with a mix of levels. This also allowed us to scale up an entire image for free by increasing the given size.

We achieved rotation by adding a rotate method to QuadTree which returned a new tree with its corners rotated and placed in a different order (rotate being an identity method on Leaf).

This opened up a whole new world of ASCII cat image manipulation possibilities:

We were particularly excited by this Jolly Roger-esque cat-based flag and contemplated its potential as a Club flag.

Show & Tell

With that done, we had time for members to demonstrate their own exploration of quadtrees.

• Chris P demonstrated his frankly amazing Quad Trees / Mandelbrot / Minimax Mashup with combined several Club topics into a single browser-based game.

Chris L first tried to load it in Emacs and wowed us with a sample (but important) search:

Sadly, the game's reliance on the Canvas API meant we had to turn to a more typical browser choice.

We then played a few rounds of the game, sceptical that it was possible to avoid being eaten by a shark but Chris expertly navigated us to safety in the end:

Retrospective

• We thanked Kevin for organising the meeting including proposals and voting. It was raised that the time to raise proposals is rather tight considering that voting ideally completes before the first weekend after the meeting (so that the next shepherd has two weekends to prepare). We discussed whether to call for proposals before the meeting.
• In general, it was noted that very few proposals are made with the list being largely static for weeks.
• This tied into our previous discussions whether we want to finish the book and, if not, when we might move on. We decided to try to solve both problems by proposing all remaining book chapters to have a better idea when we are finished with it.

Thanks

Thanks to Leo and Geckoboard for hosting, Mike for shepherding, Kevin for organising the meeting, Chris L for typing and Chris P for his mashup.