Mona Lisa video

Here is a small video demonstrating the polygons evolution:

(better results should be doable with more time and/or more parameters tweakings)
For this example, I used 50 polygons of at most 16 points, starting with 10 polygons.

Genetic Algorithms and Mona Lisa

Genetic Algorithms try to apply evolution mechanisms to find solutions to hard problems (typically, where no "proper" solution is known and where the search area is large).

Roger Alsing posted a couple of days ago an extremely cool article showing the convergence of 50 polygons to represent the Mona Lisa, using a random approach.

That was too cool to not try to implement it :)

The screenshot shows a rendering of the Mona Lisa using 50 polygons (16 points each), after 40818 total iterations, with 4577 elected states; the middle image is the original (i.e. the target) and the right image the difference between the current polygon-based image and the target (i.e. a representation of the fitness function).
Underneath was an earlier attempt using ovals instead of polygons.

Now, to be more exact, Roger Alsing's algo is more a hill climber algorithm or possibly a simulated annealing algorithm than a good example of a genetic algorithm; it should be interesting to actually implement a proper genetic algorithm approach (i.e. a population > 1) and see how the convergence rate compares... combining polygons and ovals might also result into interesting things.

Iliad iRex note taking and hand-writing recognition

I recently bought an Iliad iRex, a pretty awesome eBook reader. Among the cool features, it's running linux, an sdk is available, and it's really easy to hack stuff for it (for instance I wrote a simple script for downloading the 24h edition of The Guardian). Also, as shown with the previous link, the community is quite active :)

Just a couple of words about the iliad itself... the hardware is pretty awesome, with wifi, ethernet, wacom tablet, usb, mmc card and compactflash, audio jack...
the e-ink display is quite amazing too -- 768x1024 makes it precise enough to be able to read A4 PDF without too much problem (a great thing to review lots of research papers, believe me !).

The software side on the other hand... is a bit disappointing. Don't get me wrong: it's good enough, and some aspects are pretty cool. But you really unlock the possibilities of the devices by getting the root access and adding applications developed by the community (notably, the PDF viewer hacked by the community is fantastic, with gestures, etc.). Which means it's fine if you are a geek and not afraid to hack your device, but more annoying for your average consumer :-/
The other disappointing aspect is the (comparatively) low battery life: about 12-15 hours depending on the model (mine is a v1, the v2 do better), which is mostly caused by the fact that no sleep mode is available. Other eBook readers perform much better on that metric. To be fair they don't have wifi nor a wacom tablet :D ... so it's really a matter of choice.

All in all, it's a bit of a shame as really the platform is very nice, and with a bit more effort on the software side, Iliad would have a killer product on their hands. Oh, and yes the e-ink display refresh rate is slow, but curiously it's not that annoying, and having its full library in such small factor is absolutely fantastic.

Anyway... one of the really, really cool feature of the iliad is the presence of a stylus (i.e. the iliad display sports a wacom tablet), which allows you to annotate PDFs, take notes, etc.

I started to experiment a bit with the note taking feature of the iliad; the idea is that you can open a PNG image in the notes folder, and a copy will automatically be made where you can write on it (the image is being used as a background, so it's trivial to have customized backgrounds). But I then wanted to generate a PDF from those notes (i.e. combining the scribbles+PNG).

Iliad do provide a windows application to do all that, but it's a windows app, not really useful for me... there is a nice java application written by the community that allows merging scribbles with the PDF as well. Alas, the java scribble merging application only seems to work for PDF scribble; I guess it would be trivial to modify the java app, but I had a look at the xml scribbling format, and I saw that the format was really simple.

So I quickly wrote myself a MacOSX viewer for the notes, using the png image as a background, letting me print notes easily or convert them to PDF.

But then... I suddenly remembered the Ink handwriting recognition engine.

This thing comes straight from the ill-fated Apple Newton PDA (such a loss!), but what is nice is that it is available and installed by default on OSX.

Turns out it's not too difficult to feed Ink a set of custom datapoints, and after some tweaking it doesn't work too bad apparently, as can be seen on the screenshot...

So far, this is only highly experimental code, and it'll probably take a bit more time to have a really usable application. Still, pretty cool!

Pointillist

What is it ? well, Pointillism is a style of painting I quite like, but Pointillist is simply the (working) name of a small graph library I'm working on. The previous post was discussing about the simulation software I wrote, which uses a simple graph view. I decided to clean up a bit that view, put it in a framework and commit it somewhere (likely on the étoilé repository). Not quite done yet, but it's shaping well, and it's now quite a bit more generic:

One of my "I will do it one day" project is a simple graph calculator... So in order to properly test the graph framework, I created a class using the StepTalk scripting framework to express functions (written in Smalltalk), which actually makes me rather close to have such a program :-P

for the curious, the code of the functions is:

Red function:

|y| 
y := -0.5. 
((x < 0.5) and: (x > -0.5)) ifTrue: [y := 1]. 
(x < -1) ifTrue: [ y := 0.25]. 
( x < -1.5) ifTrue: [ y := -2 ]. 
(x > 1.5) ifTrue: [ y := 2]. 
y := y + 1.5. 
^y

Green function:

x sin - 1 / x

Blue function:

|y mod| 
y := -1. 
mod := x mod: 2. 
(mod = 0) ifTrue: [ y := 1 ]. 
y := y - 2. 
^ y

StepTalk is really cool btw -- Easy to integrate, and works both on OSX and GNUstep. Here is the code I use here:

id environment = [STEnvironment environmentWithDefaultDescription];
id conversation = [STConversation conversationWithEnvironment: environment
      language: @"Smalltalk"];

(...)

id number = [NSNumber numberWithFloat: x];
[environment setObject: number forName: @"x"];
[conversation interpretScript: @"^ (x tan) / (x atan)"];
id result = [conversation result];

[values addObject: result];

values beeing a NSMutableArray containing the numbers returned by the steptalk function (the ^ in smalltalk is equivalent to a "return" statement in C). As you can see, difficult to have a scripting framework simpler than that to work with!

You can see that in the environment object I put an "external" (to the script) object, number, and this object can be accessed from the script using the given name (here, x). You could, instead of getting the script result, get the value of specific objects you put in the environment.

Anyway, it's very simple to add StepTalk support to your program, and recent versions even add nifty UI widgets to play with scripts.. also, StepTalk is not "just" a Smalltalk scripting framework : it can actually use other languages. On GNUstep for instance there's an Io bundle, so you could use Io instead of Smalltalk, etc. (it's actually fairly easy to add languages to StepTalk).

Note also that StepTalk automatically bridge the numbers in the script to actual NSNumber instances... which is how I decided to implement the math functions, and this actually demonstrate a very cool Objective-C feature; NSNumber doesn't have thoses sin,cos,mod.. math functions; so in another programming language we'd be stuck. A "normal" solution could be to modify StepTalk so that it would use something else than NSNumber (say, a custom class of ours), or reversely, to add those functions to NSNumber and recompile -- wait! you could do that with GNUstep (because we have the source), but certainly not with Cocoa on OSX. So how comes it works ?

Well, Objective-C has this great feature: categories. A Category lets you add new code to an existing class, at runtime. So that's simply what I did here -- I created a category on NSNumber with my specific math functions. Without needing to have access to the NSNumber source, or to recompile Foundation. Isn't it great ?

System simulation

I'm (rather predictably) still working on my distributed rendering system.. but as it's a bit tiresome to make some modifications, recompile, restart.. -- more importantly, that it takes time to do so (1), I wrote a simple and nice simulation program that let me try different rendering/clustering strategies easily, swap them, evaluate or compare them, etc. That way I can concentrate on them rather than waiting 5-10 minutes to start visualizing a one gigabyte dataset on the cluster. Even better, the final idea is to integrate the simulation in the real system (it actually already gets timings from the real one and extrapolate the results) in order to have a nice feedback loop: run things, keep simulations in parallel, switch to other strategies if the simulation says it's better, update timings if needed, etc. Here is a screenshot of the current program:

The screenshot shows three simulated clustering strategies; basically we want to render an image using multiple computers. Each computer having one or more rendering agent. We divide the image in tiles and the rendering agents' job is to render them, send them back to the clustering agent, which will recompose the final image to send it back to a visualisation client. It's a fairly straightforward distributed technic. What's more interesting here is that we have three different strategies defining which tiles are sent to which agent. The simplest one is to divide the total number of tiles by the number of agents, and send continuous tiles up to that number for each agent (second bottom figure -- each color represents one agent). Another is to alternate tiles (eg no consecutive tiles are sent). Another one is to break the tiles according the the image complexity (first bottom left figure). The image complexity beeing the time each tile took to be renderered (bottom right figure).

The graphic shows the evolution of these three strategies depending on the number of agents. We can see that the alternate tiles strategy works fairly well usually (because the complexity is more evenly distributed), unless we ends on a multiple of the width (16), meaning the tiles are aligned, and thus the complexity is not properly distributed. Having a simulator can let us choose which strategy is the best before having to really use it.

(1) which break one of my Rules of Programming, ie, keep the REPL (Read-Eval-Print-Loop) cycle as short as possible: as obviously the shortest it is, the more ideas you can try.

Structured Edition

I have been playing since a week or so with the Text System on Cocoa/GNUstep... it's not immediately easy to understand, but it's really nice and powerful :-)
It handles automatically lots of things, you can redefine many things too (create specific layout manager to change the way the text is displayed, eg, to "flow" around an image, etc.)..

For instance, you're supposed to work with NSTextStorage, which contains the content you're editing, and which is supposedly an attributed string (a string plus related attributes -- fonts, links, attachments, etc), and you edit it via a NSTextView. But what if you want MORE than edit an attributed string ? like, say, edit some structured content ?

Well in fact,the answer is to create a subclass of NSTextStorage that will answer the base methods (just four) of NSTextStorage -- it's in fact a class cluster. So the idea is simply to have on one side your structured document (in my case, a simple array of "Section" objects, containing (optionally) a title and a content), and to have a NSTextStorage that will actually serve as a gateway between the text system (which expect a simple NSAttributedString) and your own structured model... Pretty cool :-) and that way you benefit of all the niceties of the text system..

The above screenshot is my current editor (which btw I wrote under Cocoa, and recompiled this evening on GNUstep), the button is there to define a selected text as a title.