Mathias Brandewinder on .NET, F#, VSTO and Excel development, and quantitative analysis / machine learning.
31. July 2014 14:15

It is the summer, a time to cool off and enjoy vacations – so let’s keep it light, and hopefully fun, today! A couple of days ago, during his recent San Francisco visit, @tomaspetricek brought up an idea that I found intriguing. What if you had two images, and wanted to recreate an image similar to the first one, using only the pixels from the second?

To make this real, let’s take two images - a portrait by Velasquez, and one by Picasso, which I have conveniently cropped to be of identical size. What we are trying to do is to re-arrange the pixels from the Picasso painting, and recombine them to get something close to the Velasquez:

You can find the original images here: http://1drv.ms/XmlTN4

My thinking on the problem was as follows: we are trying to arrange a set of pixels into an image as close as possible to an existing image. That’s not entirely trivial. Being somewhat lazy, rather than work hard, I reverted to my patented strategy “what is the simplest thing that could possibly work (TM)”.

Two images are identical if each of their matching pixels are equal; the greater the difference between pixels, the less similar they are. In that frame, one possible angle is to try and match each pixel and limit the differences.

So how could we do that? If I had two equal groups of people, and I were trying to pair them by skill level, here is what I would do: rank each group by skill, and match the lowest person from the first group with his counterpart in the second group, and so on and so forth, until everyone is paired up. It’s not perfect, but it is easy.

Problem here is that there is no obvious order over pixels. Not a problem – we’ll create a sorting function, and replace it with something else if we don’t like the result. For instance, we could sort by “maximum intensity”; the value of a pixel will be the greater of its Red, Green and Blue value.

At that point, we have an algorithm. Time to crank out F# and try it out with a script:

open System.IO
open System.Drawing

let combine (target:string) ((source1,source2):string*string) =
// open the 2 images to combine
let img1 = new Bitmap(source1)
let img2 = new Bitmap(source2)
// create the combined image
let combo = new Bitmap(img1)
// extract pixels from an image
let pixelize (img:Bitmap) = [
for x in 0 .. img.Width - 1 do
for y in 0 .. img.Height - 1 do
yield (x,y,img.GetPixel(x,y)) ]
// extract pixels from the 2 images
let pix1 = pixelize img1
let pix2 = pixelize img2
// sort by most intense color
let sorter (_,_,c:Color) = [c.R;c.G;c.B] |> Seq.max
// sort, combine and write pixels
(pix1 |> List.sortBy sorter,
pix2 |> List.sortBy sorter)
||> List.zip
|> List.iter (fun ((x1,y1,_),(_,_,c2)) ->
combo.SetPixel(x1,y1,c2))
// ... and save, we're done
combo.Save(target)

… and we are done. Assuming you downloaded the two images in the same place as

let root = __SOURCE_DIRECTORY__

let velasquez = Path.Combine(root,"velasquez.bmp")
let picasso = Path.Combine(root,"picasso.bmp")

let picasquez = Path.Combine(root,"picasquez.bmp")
let velasso = Path.Combine(root,"velasso.bmp")

(velasquez,picasso) |> combine velasso
(picasso,velasquez) |> combine picasquez

… which should create two images like these:

Not bad for 20 lines of code. Now you might argue that this isn’t the nicest, most functional code ever, and you would be right. There are a lot of things that could be done to improve that code; for instance, handling pictures of different sizes, or injecting an arbitrary Color sorting function – feel free to have fun with it!

Also, you might wonder why I picked that specific, and somewhat odd, sorting function. Truth be told, it happened by accident. In my first attempt, I simply summed the 3 colors, and the results were pretty bad. The reason for it is, Red, Green and Blue are encoded as bytes, and summing up 3 bytes doesn’t necessarily do what you would expect. Rather than, say, convert everything to int, I went the lazy route again…

Original images: http://1drv.ms/XmlTN4

16. June 2014 22:15

Like many a good man, I too got caught into the 2048 trap, which explains in part why I have been rather quiet on this blog lately (there are a couple other reasons, too).

In case you don't know what 2048 is yet, first, consider yourself lucky - and, fair warning, you might want to back away now, while you still have a chance. 2048 is a very simple and fun game, and one of the greatest time sinks since Tetris. You can play it here, and the source code is here on GitHub.

I managed to dodge the bullet for a while, until @PrestonGuillot, a good friend of mine, decided to write a 2048 bot as a fun weekend project to sharpen his F# skills, and dragged me down with him in the process. This has been a ton of fun, and this post is a moderately organized collection of notes from my diary as a recovering 2048 addict.

Let's begin with the end result. The video below shows a F# bot, written by my friend @Blaise_V, masterfully playing the game. I recorded it a couple of weeks ago, accelerating time "for dramatic purposes":

One of the problems Preston and I ran into early was how to handle interactions with the game. A recent post by @shanselman was praising Canopy as a great library for web UI testing, which gave me the idea to try it for that purpose. In spite of my deep incompetence of things web related, I found the Canopy F# DSL super easy to pick up, and got something crude working in a jiffy. With a bit of extra help from the awesome @lefthandedgoat, the creator of Canopy (thanks Chris!), it went from crude to pretty OK, and I was ready to focus on the interesting bits, the game AI.

I had so much fun in the process, I figured others might too, and turned this into another Community for F# Dojo, which you can find here.

More...

16. March 2013 10:04

Mondrian is one of those modern painters whose work everyone recognizes, even though few people will quote his name. He also happens to be one of my favorite artists – in spite of their simple geometric structure, I find his pieces strangely beautiful:

“Composition II in Red, Blue, and Yellow”, from Wikipedia

I have been hard at work on some pretty dry stuff lately, and needed a bit of a change of pace, and ended up spending a couple of hours coding a simple Mondrianizer in F#: give it a picture, and it will transform it into something “in the style of Mondrian”.

For instance, starting from my Twitter avatar, here is what the Mondrianizer produces:

This was strictly quick-and-dirty hackery, so the code is not my best by any stretch of the imagination, but I was rather pleased by the results – you can find the current version of the Mondrianizer here on GitHub.

More...

25. March 2012 10:53

In a previous post, I looked at creating a Sierpinski triangle using F# and WPF. One of the pieces I was not too happy about was the function I used to transform a Triangle into a next generation triangle:

type Point = { X:float; Y:float }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
let x1 = p1.X + 0.5 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y1 = p1.Y + 0.5 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x2 = p1.X + 1.0 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y2 = p1.Y + 1.0 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x3 = p1.X + 0.5 * (p2.X - p1.X) + 1.0 * (p3.X - p1.X)
let y3 = p1.Y + 0.5 * (p2.Y - p1.Y) + 1.0 * (p3.Y - p1.Y)
{ A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

Per se, there is nothing wrong with the transform function: it takes 3 points (the triangle corners), and returns a new Triangle. However, what is being “done” to the triangle is not very expressive – and the code looks rather ugly, with clear duplication (the exact same operation is repeated on the X and Y coordinates of every point).

Bringing back blurry memories from past geometry classes, it seems we are missing the notion of a Vector. What we are doing here is taking corner p1 of the Triangle, and adding a linear combinations of the edges p1, p2 and p1, p3 to it, which can be seen as 2 Vectors (p2 – p1) and (p3 – p1). Restated that way, here is what the transform function is really doing:

A –> A + 0.5 x AB + 0.5 x AC

A –> A + 1.0 x AB + 0.5 AC

A –> A + 0.5 x AB + 1.0 x AC

In graphical form, the first transformation can be represented as follows:

In order to achieve this, we need to define a few elements: a Vector, obviously, a way to create a Vector from two Points, to add Vectors, to scale a Vector by a scalar, and to translate a Point by a Vector. Let’s do it:

type Vector =
{ dX:float; dY:float }
static member (+) (v1, v2) = { dX = v1.dX + v2.dX; dY = v1.dY + v2.dY }
static member (*) (sc, v) = { dX = sc * v.dX; dY = sc * v.dY }

type Point =
{ X:float; Y:float }
static member (+) (p, v) = { X = p.X + v.dX; Y = p.Y + v.dY }
static member (-) (p2, p1) = { dX = p2.X - p1.X; dY = p2.Y - p1.Y }

type Triangle = { A:Point; B:Point; C:Point }

Thanks to operators overloading, the transform function can now be re-phrased in a much more palatable way:

let transform (p1:Point, p2, p3) =
let a = p1 + 0.5 * (p2 - p1) + 0.5 * (p3 - p1)
let b = p1 + 1.0 * (p2 - p1) + 0.5 * (p3 - p1)
let c = p1 + 0.5 * (p2 - p1) + 1.0 * (p3 - p1)
{ A = a; B = b; C = c }

… and we are done. The code (posted on fsSnip.net) works exactly as before, but it’s way clearer.

It can also be tweaked more easily now. I got curious about what would happen if slightly different transformations were applied, and the results can be pretty fun. For instance, with a minor modification of the transform function…

let transform (p1:Point, p2, p3) =
let a = p1 + 0.55 * (p2 - p1) + 0.5 * (p3 - p1)
let b = p1 + 1.05 * (p2 - p1) + 0.45 * (p3 - p1)
let c = p1 + 0.5 * (p2 - p1) + 0.95 * (p3 - p1)
{ A = a; B = b; C = c }

… we get the following, bloated “Sierpinski triangle”:

Add a bit of transparency, some more tweaks of the linear combinations,

let transform (p1:Point, p2, p3) =
let a = p1 + 0.3 * (p2 - p1) + 0.6 * (p3 - p1)
let b = p1 + 0.8 * (p2 - p1) + 0.3 * (p3 - p1)
let c = p1 + 0.6 * (p2 - p1) + 1.1 * (p3 - p1)
{ A = a; B = b; C = c }

and things get much wilder:

I don’t think these are really Sierpinski triangles any more, but I had lots of fun playing with this, and figured someone else might enjoy it, too… If you find a nice new combination, post it in the comments!

Source code: fsSnip.net

16. March 2012 08:33

In my last post, I looked into drawing a Sierpinski triangle using F# and WinForms, and noted that the rendering wasn’t too smooth – so I converted it to WPF, to see if the result would be any better, and it is. In the process, I discovered John Liao’s blog, which contains some F# + WPF code examples I found very useful. I posted the code below, as well as on FsSnip. The differences with the WinForms code are minimal, I’ll let the interested reader figure that part out!

One thing I noticed is that the starting point of the Sierpinski sequence is a single triangle – but nothing would prevent a curious user to initialize the sequence with multiple triangles. And while at it, why not use WPF Brush opacity to create semi-transparent triangles, and see how their superposition looks like?

We just change the Brush Color and Opacity, and add a second triangle to the root sequence…

let brush = new SolidColorBrush(Colors.DarkBlue)
brush.Opacity <- 0.6
let renderTriangle = render canvas brush

let triangle =
let p1 = { X = 190.0; Y = 170.0 }
let p2 = { X = 410.0; Y = 210.0}
let p3 = { X = 220.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let triangle2 =
let p1 = { X = 290.0; Y = 170.0 }
let p2 = { X = 510.0; Y = 210.0}
let p3 = { X = 320.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let root = seq { yield triangle; yield triangle2 }

… and here we go:

Granted, it’s pretty useless, but I thought it looked rather nice!

As an aside, here is something I noted when working in F#: I often end up looking at the code, thinking “can I use this to do something I didn’t think about when I wrote it”? In C#, I tend to think in terms of restrictions: write Components, with a “containment” approach – figure out what the component should do, and enforce safety by constraining the inputs/outputs via an interface. By contrast, because of type inference and the fact that a function doesn’t require an “owner” (it is typically not a member of a class), I find myself less “mentally conditioned”, and instead of a world of IWidgets and ISprockets, I simply see functions that transform elements, and wonder what else they could apply to.

The case we saw here was trivial, but pretty much from the moment I wrote that code, I have been mulling over other extensions. What is the transform function really doing, and what other functions could I replace it with? generateFrom is simply permuting the triangle corners and applying the same transformation – could I generalize this to an arbitrary sequence and write Sierpinski Polygons? Could I even apply it to something that has nothing to do with geometry?

// Requires reference to
// PresentationCore, PresentationFramework,
// System.Windows.Presentation, System.Xaml, WindowsBase

open System
open System.Windows
open System.Windows.Media
open System.Windows.Shapes
open System.Windows.Controls

type Point = { X:float; Y:float }
type Triangle = { A:Point; B:Point; C:Point }

let transform (p1, p2, p3) =
let x1 = p1.X + 0.5 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y1 = p1.Y + 0.5 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x2 = p1.X + 1.0 * (p2.X - p1.X) + 0.5 * (p3.X - p1.X)
let y2 = p1.Y + 1.0 * (p2.Y - p1.Y) + 0.5 * (p3.Y - p1.Y)
let x3 = p1.X + 0.5 * (p2.X - p1.X) + 1.0 * (p3.X - p1.X)
let y3 = p1.Y + 0.5 * (p2.Y - p1.Y) + 1.0 * (p3.Y - p1.Y)
{ A = { X = x1; Y = y1 }; B = { X = x2; Y = y2 }; C= { X = x3; Y = y3 }}

let generateFrom triangle = seq {
yield transform (triangle.A, triangle.B, triangle.C)
yield transform (triangle.B, triangle.C, triangle.A)
yield transform (triangle.C, triangle.A, triangle.B)
}

let nextGeneration triangles =
Seq.collect generateFrom triangles

let render (target:Canvas) (brush:Brush) triangle =
let points = new PointCollection()
let polygon = new Polygon()
polygon.Points <- points
polygon.Fill <- brush

let win = new Window()
let canvas = new Canvas()
canvas.Background <- Brushes.White
let brush = new SolidColorBrush(Colors.Black)
brush.Opacity <- 1.0
let renderTriangle = render canvas brush

let triangle =
let p1 = { X = 190.0; Y = 170.0 }
let p2 = { X = 410.0; Y = 210.0}
let p3 = { X = 220.0; Y = 360.0}
{ A = p1; B = p2; C = p3 }

let root = seq { yield triangle }
let generations =
Seq.unfold (fun state -> Some(state, (nextGeneration state))) root
|> Seq.take 7
Seq.iter (fun gen -> Seq.iter renderTriangle gen) generations

win.Content <- canvas
win.Show()

app.Run() |> ignore