I’ve always had an interest in computer generated imagery and art, even though I’ll be the first to admit I level a level of artistic skill roughly on par with underdeveloped slime-mould. Fractals, Lorenz Attractors, cellular automata, and so on. All fascinating.
So after seeing a few pictures generated using Quadtrees to approximate actual images, I thought I’d give it a shot.
The principle is simple. Take an image; create a new image simply by taking the colour at the centre. Split it into four rectangles, each with a colour sampled from the original in their centre. Take the rectangle “furthest” from the original, repeat until you run out of divisions or reach some arbitrary limit.
Below are a couple of animations showing the process applied to some recent images featured on this site (HTML5 embeds to save on massive file sizes):
Turning the lines off gives a much different tone, leading to something of a pixel art effect:
All in all, quite pleased with the results. The code to do it is exceptionally quick and dirty, and quite probably wrong, but it turns out the images and that’s all I ask. It’s all in a single class and the only nods I made towards good code were putting the hard work in a separate thread and using something a little more low-level for accessing the bitmap data (somewhat necessary, and an easy 90% reduction in processing time). Other than that it’s definitely “never show to anyone under any circumstances” code. So here you go:
using System;
using System.Collections.Generic;
using System.ComponentModel;
using System.Drawing;
using System.Drawing.Imaging;
using System.IO;
using System.Windows.Forms;
namespace WindowsFormsApplication1 {
public partial class Form1 : Form {
private const int MIN_SIZE = 4;
private const int MAX_ITERATIONS = int.MaxValue;
private bool drawLines = true;
private List<Block> blocks;
private List<Block> finished;
private Bitmap baseImage;
private Bitmap workingImage;
private Graphics workingG;
private int iterations = 0;
private BackgroundWorker worker;
private bool completed = false;
private System.Diagnostics.Stopwatch timer;
private string filename;
public Form1() {
InitializeComponent();
}
private void start(string filename) {
this.filename = new FileInfo(filename).Name;
timer = System.Diagnostics.Stopwatch.StartNew();
baseImage = (Bitmap)Bitmap.FromFile(filename);
this.ClientSize = new System.Drawing.Size(baseImage.Width, baseImage.Height);
workingImage = (Bitmap)baseImage.Clone();
workingG = Graphics.FromImage(workingImage);
blocks = new List<Block>();
Block first = new Block();
first.Rect = new Rectangle(0, 0, baseImage.Width, baseImage.Height);
first.Col = baseImage.GetPixel(first.Rect.X + (first.Rect.Width / 2), first.Rect.Y + (first.Rect.Height / 2));
blocks.Add(first);
finished = new List<Block>();
worker = new BackgroundWorker();
worker.DoWork += worker_DoWork;
worker.RunWorkerCompleted += worker_RunWorkerCompleted;
linkLabel1.Visible = false;
worker.RunWorkerAsync();
}
void worker_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e) {
render();
if (iterations >= MAX_ITERATIONS)
completed = true;
if (!completed) {
if (iterations % 5 == 0)
this.Text = "Iterations: " + iterations + ", time: " + timer.ElapsedMilliseconds;
worker.RunWorkerAsync();
} else
this.Text = "Done";
}
void worker_DoWork(object sender, DoWorkEventArgs e) {
iterations++;
Block worst = getWorst();
if (worst == null) {
completed = true;
return;
}
blocks.Remove(worst);
Rectangle[] children = splitRect(worst.Rect);
foreach (Rectangle curr in children) {
Block block = new Block();
block.Rect = curr;
block.Col = baseImage.GetPixel(block.Rect.X + block.Rect.Width / 2, block.Rect.Y + block.Rect.Height / 2);
blocks.Add(block);
}
for (int index = blocks.Count - 1; index >= 0; index --) {
if (blocks[index].Rect.Width < MIN_SIZE || blocks[index].Rect.Height < MIN_SIZE) {
finished.Add(blocks[index]);
blocks.RemoveAt(index);
}
}
}
private Rectangle[] splitRect(Rectangle baseRect) {
Rectangle[] result = new Rectangle[4];
result[0] = new Rectangle();
result[1] = new Rectangle();
result[2] = new Rectangle();
result[3] = new Rectangle();
//Top left
result[0].X = baseRect.X;
result[0].Width = baseRect.Width / 2;
result[0].Y = baseRect.Y;
result[0].Height = baseRect.Height / 2;
//Top right
result[1].X = result[0].Right + 1;
result[1].Width = baseRect.Width - (result[0].Width + 1);
result[1].Y = baseRect.Y;
result[1].Height = result[0].Height;
while (result[1].Right >= baseImage.Width && result[1].Width > 1)
result[1].Width--;
//Bottom left
result[2].X = result[0].X;
result[2].Width = result[0].Width;
result[2].Y = result[0].Bottom + 1;
result[2].Height = baseRect.Height - (result[0].Height + 1);
while (result[2].Bottom >= baseImage.Height && result[1].Height > 1)
result[2].Height--;
//Bottom right
result[3].X = result[1].X;
result[3].Width = result[1].Width;
result[3].Y = result[2].Y;
result[3].Height = result[2].Height;
return result;
}
private Block getWorst() {
int index = -1;
int worstIndex = -1;
int worstDiff = 0;
Block worstBlock = null;
foreach (Block curr in blocks) {
index++;
int diff = getDiff(curr);
if (diff > worstDiff) {
worstDiff = diff;
worstBlock = curr;
worstIndex = index;
}
}
return worstBlock;
}
private int getDiff(Block block) {
int diff = 0;
BitmapData bitmapData = baseImage.LockBits(block.Rect, ImageLockMode.ReadWrite, baseImage.PixelFormat);
int bpp = System.Drawing.Bitmap.GetPixelFormatSize(baseImage.PixelFormat) / 8;
int numBytes = bitmapData.Stride * block.Rect.Height;
byte[] pixels = new byte[numBytes];
IntPtr ptrStart = bitmapData.Scan0;
System.Runtime.InteropServices.Marshal.Copy(ptrStart, pixels, 0, pixels.Length);
int heightPixels = bitmapData.Height;
int widthBytes = bitmapData.Width * bpp;
for (int y = 0; y < heightPixels; y++) {
int currLine = y * bitmapData.Stride;
for (int x = 0; x < widthBytes; x = x + bpp) {
diff +=
Math.Abs(pixels[currLine + x] - block.Col.R) +
Math.Abs(pixels[currLine + x + 1] - block.Col.G) +
Math.Abs(pixels[currLine + x + 2] - block.Col.B);
}
}
baseImage.UnlockBits(bitmapData);
return diff / (int)Math.Sqrt(block.Rect.Width * block.Rect.Height);
}
private void render() {
foreach (Block curr in blocks) {
workingG.FillRectangle(new SolidBrush(curr.Col), curr.Rect.X, curr.Rect.Y, curr.Rect.Width + 1, curr.Rect.Height + 1);
}
foreach (Block curr in finished) {
workingG.FillRectangle(new SolidBrush(curr.Col), curr.Rect.X, curr.Rect.Y, curr.Rect.Width + 1, curr.Rect.Height + 1);
}
if (drawLines) {
foreach (Block curr in blocks) {
workingG.DrawLine(Pens.Black, curr.Rect.X, curr.Rect.Y, curr.Rect.Right, curr.Rect.Y);
workingG.DrawLine(Pens.Black, curr.Rect.X, curr.Rect.Y, curr.Rect.X, curr.Rect.Bottom);
}
foreach (Block curr in finished) {
workingG.DrawLine(Pens.Black, curr.Rect.X, curr.Rect.Y, curr.Rect.Right, curr.Rect.Y);
workingG.DrawLine(Pens.Black, curr.Rect.X, curr.Rect.Y, curr.Rect.X, curr.Rect.Bottom);
}
workingG.DrawRectangle(Pens.Black, 0, 0, baseImage.Width - 1, baseImage.Height - 1);
}
picture.Image = workingImage;
/*
* Uncomment to spit out screenshots
*/
//if (iterations % 25 == 2) {
// string path = System.IO.Path.GetTempPath();
// string dir = @"arturo\";
// string file = System.Diagnostics.Stopwatch.GetTimestamp() + "_" + filename;
// string outDir = path + dir;
// if (!Directory.Exists(outDir))
// Directory.CreateDirectory(outDir);
// workingImage.Save(outDir + file);
//}
}
private void linkLabel1_LinkClicked(object sender, LinkLabelLinkClickedEventArgs e) {
OpenFileDialog openD = new OpenFileDialog();
DialogResult res = openD.ShowDialog();
if (res == System.Windows.Forms.DialogResult.OK && File.Exists(openD.FileName)) {
start(openD.FileName);
}
}
private void linkLabel1_Click(object sender, EventArgs e) {
linkLabel1_LinkClicked(null, null);
}
private void Form1_KeyUp(object sender, KeyEventArgs e) {
if (e.KeyCode == Keys.Space)
drawLines = !drawLines;
else if (e.KeyCode == Keys.Escape)
completed = true;
}
}
class Block
{
public Rectangle Rect;
public Color Col;
}
}
Yes, I know there’s no actual quadtree data structure in there. Shush.