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!

Fun with Objective-C

Following a mail from david on étoilé dev about how it could be nice to try allocating ObjC objects on the stack, I played with a couple of things...

First I wrote a mini benchmark -- get a very basic object (a couple of ivars, one method "plop" assigning a value to an ivar), and then create an instance, initialize it (call the init method), call the one method the object has, then deallocate the object. 10000000 times. As far as micro benchark goes this one is pretty stupid but well, that'll give us some ideas of what's going on.

Without optimizations: ~4.10s (on a macbook pro 2.16Ghz, core duo)

Not that great -- doing the same thing in C++ with a similar object here is the timings I get:

Objects created on the stack: 0.24s (17 times faster !)
Objects created on the heap: 1.37s (3 times faster)

Ouch, the poor Objective-C... not a surprise when allocating objects on the stack, but even allocating them on the heap C++ is still 3 times faster.

One obvious reason is that Objective-C calls a lot of methods when creating an object; and a method call is more costly than a C++ function call. Still...

So the obvious idea here is to cache some method calls (ask their address then call the function directly -- as a C function). I restrained myself to alloc/init, the method the object had ("plop"), and the release method. Of course, there's other methods that are called by those, that won't be cached.

Caching method calls: 2.77s

It's still twice as slow as creating the C++ object on the heap, but it's anyway a nice performance increase.

Ok, then our only option left is to allocate the Objective-C object on the stack. Surprise:

ObjC objects created on the stack: 0.23s
ObjC objects created on the stack + cached imps: 0.13s

:-)

[note of course that it's a stupid micro-benchmark that doesn't prove much, but it's fun]


...


What ? how can you allocate objective-c objects on the stack ? ah well... you can:

#define STACKCLASS(class) typedef struct { @defs(class) } \
    __CLASS_ON_STACK__ ## class;


#define STACKOBJECTISA(objectName,className,classIsa) \
    __CLASS_ON_STACK__ ## className __INSTANCE_ON_STACK__ ## objectName; \
    __INSTANCE_ON_STACK__ ## objectName.isa = classIsa; \
    className* objectName = (className*)& __INSTANCE_ON_STACK__ ## objectName;


#define STACKOBJECT(objectName,className) \
    STACKOBJECTISA(objectName,className,[className class]);

Here is an example:

STACKCLASS(Test);

int i;
for (i=0; i< 10000000; i++)
{
  STACKOBJECT(test,Test);
  [test init];
  [test plop];
}

Basically, create the corresponding struct for the class and set the isa member (you can also cache the class isa to gain one message send). A bit of a hack, but that seem to work ok :)

Note of course that by doing that, you loose flexibility -- exit class clusters for instance (eg classes that actually returns another class instance, such as NSNumber), you can only work with concrete classes. And also, don't call directly -dealloc as it would try to deallocate the object, which is not needed as it was created on the stack (so if you need to do some cleanup you should do it in another method).

Here's the macros I used for imp caching (fairly straightforward):

#define CALLIMP(imp,object,sel,args...) \
    (*imp)(object, @selector(sel) , ##args)
#define GETIMP(class,sel) [class methodForSelector: @selector(sel)];

You use them like that:

IMP imp1 = GETIMP(Test,alloc);
id p = [Test new];
IMP imp2 = GETIMP(p,init);
IMP imp3 = GETIMP(p,plop);
IMP imp4 = GETIMP(p,release);
[p release];

int i;
for (i=0; i< 10000000; i++)
{
   id test = CALLIMP (imp1, c, alloc);
   CALLIMP (imp2, test, init);
   CALLIMP (imp4, test, plop);
   CALLIMP (imp3, test, release);
}

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 ?