Looking Out To Sea

Taken from the man page for strncmp:

       The following sections are informative.
 
EXAMPLES
       None.
 
APPLICATION USAGE
       None.
 
RATIONALE
       None.
 
FUTURE DIRECTIONS
       None.

I hope that was a joke.

A couple of days ago I mentioned implementing simulated annealing for my comicbake program so I thought I would take some time to explain what that means and why it’s helpful. I’m sure there are some curious souls out there wondering what it’s all about!

He is seeking it, seeking it, all his thought is bent on it.

Let us start with a discussion of search.

Search is what you do when you don’t know how to get something by straightforward means. The type of search you do depends on what you’re looking for. Sometimes you know the goal but want to know how to get there. How to get from A to B is literally the problem solved by route-finding programs like Google Maps. The other type of search is where you don’t know what the goal is but you know what properties it has. You don’t know what your next chess move might be until you examine the board, but ideally it would involve not losing any pieces, and maybe gaining one of the opponent’s pieces.

Some searches are completely “uninformed” and will examine all possible solutions. This is obviously quite slow, so is avoided in all but the smallest of cases.

A simple improvement is to assume that any small change that improves the current solution can be used as a starting point to hunt for another small change. This is called “hill-climbing”, as we slowly ascend the terrain of the search space towards the highest point. An uninformed search would walk back and forwards across the landscape in a regular pattern as if looking for a contact lens. Hill climbing would never go back down hill, but follow the steepest course up hill.

The Gloaming from Beinn Bheoil.
© Iain Gillespie

The trouble with hill climbing, as any ramblers out there will know, is the minor summits. You get to the top of a small hill which seemed so all-encompassing, and you realise it actually stands in the shadow of a more massive peak. And to get onto that peak, you have to go downhill. Standard hill-climbing search doesn’t know there are other peaks and won’t ever go downhill to find them. It gets stuck in the foothills.

Simulated annealing is one further improvement to standard hill climbing search. It allows us to go down instead of up sometimes, if the direction we have chosen takes us down. We won’t always go downhill, as we want the gradual trend to be upwards, but a small proportion of downhill treks will help us avoid being trapped on the little peaks. To continue with the hill-climbing theme we can decide that the chances of going downhill as well as up should depend on how energetic we feel. Early in the day we may be willing to strike out in search of new peaks, but as the day wears on and the legs begin to tire, the adventurous spirit wanes.

Search with simulated annealing helps to avoid being trapped in locally good areas. The name in fact comes from the process of heating worked metal and cooling it very slowly — the molecules in this case are affected by temperature, allowing them to break out of their warped crystalline structure and slowly form better bonds as the temperature drops.

There were minstrels and mountebanks and harpers and clowns

What does all this have to do with where we started? With comic strips? You can probably see, in some vague way, how the search process might work if we actually wanted to find the tallest point in a range of hills, but how does this translate to the actual problem at hand?

In case there is any confusion, the problem at hand is choosing the best location to place speech bubbles on an individual panel of a comic strip, so that none of the bubbles overlap each other or hide the characters’ faces. Rather than jumping straight in to the solution we’ll work up to it slowly.

It helps to consider the problem in terms of the degrees of freedom we have at any point. How many things can we change at any step of the problem, in order to make the situation better or worse (ie, to ascend or descend our metaphorical hill)? If we were doing an actual hillwalk we could define our location in terms of x and y co-ordinates (such as latitude and longitude), and for every co-ordinate there would be a unique, corresponding height. Think of it as an association from co-ordinate to height:

(x,y) → Height

Here we have two degrees of freedom, as we can change each of the x and y co-ordinates independently to change our height.

In some situations you have more degrees of freedom. If you’re walking around your house looking for mobile phone signal you might also wave the phone in the air, or stand on the kitchen table or anything else if you think it will work. In this case you’re changing x, y and z co-ordinates. The value which changes is signal strength, and you’re trying to find the combination of co-ordinates which maximises signal.

(x,y,z) → Signal

This situation has three variable aspects, but other situations will have more. Every time we increase the number of variables the problem gets harder. Next you might imagine having to solve this problem to get several compatible solutions. If two people want to use their mobile phone at the same time they both can’t stand in the same spot. Now we need two places where the signal is strong! We can increase this to three, four, five…

But let’s pull things back a bit. If there are two mobile phone users in the same general area they both want good signal. We’ll say for the sake of explanation that we have three people waiting for really important calls:

Phone1(x,y,z) → Signal1
Phone2(x,y,z) → Signal2
Phone3(x,y,z) → Signal3

We want to maximise the sum of all the signals, so that everybody gets a good quality connection.

Maximise (Signal1 + Signal2 + Signal3)

To maximise the signal across all the phones we still only have the options of changing x, y or z for each. If we number each co-ordinate of each phone — so that Phone1 is located at point (x1,y1,z1) — we can see that we really need to maximise the following function:

(x1,y1,z1,x2,y2,z2,x3,y3,z3) → Overall Signal

That’s a lot of choices! And the more things there are to change, the harder the problem is and the more likely that we’ll waste time changing things which don’t affect the overall problem.

(The astute might have noticed that if everyone starts off with okay signal, we might be able to give someone really great signal at the cost of bumping someone else into a signal black hole. Overall the sums might not change, or they may prefer the unfair arrangement to the fair-but-mediocre one. We can avoid this by careful planning.)

Johnny Boo, Twinkle Power
© John Cooper

Now back to the problem again. We’ve got a selection of bubbles that all have to occupy unique places on the comic panel. There are a few places which they definitely can’t occupy (the space occupied by characters’ faces) and they also shouldn’t be out of order otherwise the comic won’t make much sense.

This is more or less the same as the mobile phone example without the ability to change z co-ordinate. For simplicity we actually invert the sense of the search — what we’re trying to do is find sea-level rather than the highest peak, though the principle is identical. To do that we invent a set of guidelines, and breaking each guidelines induces a penalty, or “cost”. The search process is trying to find an arrangement which reduces the cost to zero by not breaking any guidelines.

If we’re finding the ideal arrangement of three speech bubbles then this is the function we have to minimise. Notice the similarity to all the others before:

(x1,y1,x2,y2,x3,y3) → Cost

To calculate the cost we add up all the individual penalties which would each contribute to a “bad” solution:

• Overlapping another bubble induces a penalty. There’s an additional penalty for each bubble that overlaps another, which reduces the chances of them all piling up at one spot on the image.
• Overlapping a character’s face induces a penalty.
• Being out of order induces a penalty proportional to how far out of order a bubble is. If the first bubble appears sixth that’s really bad — it’s at totally the wrong side of the image — so we need to ensure that kind of thing doesn’t happen.

With these simple rules we run the computer through the simple procedure of moving the bubbles randomly, assessing their cost and then repeating. They slowly settle on their chosen state and the search process ends.

Along the way we’ve been keeping note of best overall position of each speech bubble. If it’s the current position we leave them there, but if they have been rearranged since then we revert to the overall best formation.

This search procedure is widely used for a lot of difficult problems — problems which would take too long to solve exhaustively. It’s also surprisingly simple to implement the core. The hard part is coming up with suitable cost measures which are quick but effective.

It’s been a busy few days on the code front. After coming to no real conclusions about the best way to lay speech bubbles out on a page deterministically, I’ve decided to explore the issue of search. I’ve knocked up a quick implementation of simulated annealing, which I’m now weaving in to rest of the code.

Like all random search methods, simulated annealing lives or dies on the quality of the heuristics you can provide. Since you don’t generally know the answer when you’re solving the problem you can’t test any intermediate solutions in the obvious manner. You instead have to test properties which you expect the solution to have. In this case, I have to test that, for example, the speech bubbles are laid out sequentially on the page. Any pair of speech bubbles which are out of order will ruin the sense of the comic, so this is fairly important.

There are other measures of goodness (or badness) of a solution, and some may be more effective than others. This has to be offset against the cost of computing the worth of each solution. If it takes 5 minutes to generate one scene it’s no use to me. Most people would rather place bubbles manually than wait this long. So speed is similarly important.

Right now I’m just waiting. I want to use the Mersenne Twister PRNG from Hackage, and it’s just my luck that the Hackage server appears to be down at the moment:

$ cabal install mersenne-random
Resolving dependencies...
Downloading mersenne-random-1.0...
cabal: Error: some packages failed to install:
mersenne-random-1.0 failed while downloading the package.

I’m optimistic about the results from this approach. I’ve been doing some reading on graph visualisation and also map labelling, which both have a lot in common with my problem. Simulated annealing appears to be effective in both instances, so I look forward to seeing what it produces in the end. When I get my shipment of random numbers…

It’s been a week or so since I posted any updates about ComicBake, mostly because I’ve been taking several steps backwards in order to move forward again. Typical manoeuvre.

I replace Brent’s Diagrams library with bindings to GD, which gives more pixel-accurate control over sizes and locations of objects. Diagrams is really good for geometric stuff (and, eh, diagrams) but not so hot for accurate overlays.

The result is a lot of code churn with not an awful lot to show on the outside. The speech bubbles have become smaller and thinner, the edges have squared off and the dialogue tails have disappeared. All because I haven’t got round to adding them back again.

The major point of changing the graphics back end was to get reliable sizing and placement of objects, which will help me work through various methods of placing speech bubbles in a natural(ish) way. Some points which have come to mind.

• Having speech bubbles overlapping slightly from left to right is not a problem. But when going from right back to left it can be confusing. Thus the conversation above. “This is just…” flows naturally into “Is that because…” but the “Um” then seems lost. It should be definitely lower than the second bubble, to make the order of speech clearer.

• In a left/right conversation like the one illustrated, the most natural arrangement of bubbles is an interleaving pattern in the large gap down the middle of the screen. Each person’s dialogue should be shifted slightly in their direction. I have an idea that aligning the near edge of the bubbles vertically would look “right” also, but until I’ve actually seen what that looks right I can’t say for certain.

• I would dearly love to know if there is any theory behind the placement of speech bubbles. Even if it’s just heuristic/aesthetic stuff like rules of thirds and so on. And, if this doesn’t seem a strange idea, advice on dealing with pathological arrangements — such as where the character at the bottom of the page speaks first, then one at the top.

Thoughts on this always appreciated.

In other news, the GD library has given me exact size data for my speech bubbles before I write them to the image. I can actually arrange the speech bubbles in the space knowing what size they’ll be in the end. This is good for the morale! I got to discard my rather annoying guessing function, which was slightly wrong in 100% of cases. Good riddance to that one.

Also making better use of the type system and typeclasses to harden some assumptions and reuse some of the same principles in different places. No doubt there are plenty more places this can be done. For now I’m going to stop fiddling with the graphics stuff and pay more attention to layout. Choosing where speech bubbles go is a fundamental part of the function of this program, and it’ll probably require some serious thinking and experimentation. I’m looking forward to it.

As usual, code can be browsed in the repository or checkout out locally with Darcs:

darcs get --partial http://www.dougalstanton.net/code/comicbake/

It’s not what any sensible person would call usable, but I’m now announcing the appearance of ComicBake, which is what I’m calling my app for creating web comics.

ComicBake is a CLI tool for making web comics. I shall demonstrate a quick example to let you understand. (This example also appears in the source repository so you can actually recreate it too.)

Example Comic: The Conversation

The first thing you need is an image, preferably with characters who can do some talking. I’ve chosen this image from Flickr of two people having a conversation. I don’t know who they are but it’s a nice photo and it’s suitably licensed so I can manipulate it as I please.

Then you need a script file which tells the compiler all about the action in the scene.

-- A Conversation
-- A Series of Examples
-- 05 September 2009
-- Dougal Stanton
 
-- Photo CC-licenced from:
-- http://www.flickr.com/photos/clairity/154640125/
 
Scene 1. <scenes/conversation.png>
 
Woman: This is just a simple demonstration.
 
Man: Is that because it breaks
     with anything longer?

Ignore the first half-dozen lines as they’re just commentary (though I plan to use them in the future). The important points to note are:

1. The scene description (including file path to image)
2. The dialogue.

There are two characters here, and we can easily tell who is who but the computer needs more help. Next up is an image map, which associates names with co-ordinates:

<img src="conversation.png" width="500" height="306" border="0" usemap="#map" />
 
<map name="map">
<!-- #$-:Image map file created by GIMP Image Map plug-in -->
<!-- #$-:GIMP Image Map plug-in by Maurits Rijk -->
<!-- #$-:Please do not edit lines starting with "#$" -->
<!-- #$VERSION:2.3 -->
<!-- #$AUTHOR:Dougal Stanton -->
<area shape="rect" coords="46,29,108,88" href="woman" />
<area shape="rect" coords="426,9,494,73" href="man" />
</map>

This is just the raw file produced by The GIMP when you use its HTML image map feature. The link name for each area (href="...") doubles as the character name. Thankfully you’ll only ever have to do this once for any given image.

Pull all that together and you get:

Getting it, Using it

The code is in the usual place:

darcs get --partial http://www.dougalstanton.net/code/comicbake

To build it use the cabal-install tool. This sets the default install to be your home dir rather than system-wide:

cabal configure --prefix=$HOME --user
cabal build

That should get all dependencies except for gtk2hs+cairo, which is a real pain and something I’m planning to abandon before long. The best bet is to see whether your distro has a package for it…

Running it is simple. It only take one argument, the script file. So if you want to execute the example script:

./comicbake example/conversation.script

This will save a frame1.png into the current working directory.

Bugs

I’m still in active hacking at the moment — not even really alpha as it’s a bit of a mess. But I figured that if I didn’t release something now I would forget about it and it would disappear eventually. Which would be a shame because I think it’s quite a neat idea with some interesting potential.

• The most obvious problem is that if you give it anything more than a couple of speech bubbles to place it can’t find space for them and bails out. The error message you see will be: Prelude.head: empty list. This needs sorted.

• The Diagrams package I’m using is not as suited to the job as I’d hoped, for two reasons. One is that I can’t know how big my speech bubbles will be before I place them, so I’m using conservative guesswork which has so far been quite successful. But it’s not a solution.

• The other problem is that accurate placement of the resulting objects is something that the Diagrams package doesn’t do very well. It doesn’t think in terms of absolute pixel sizes, so things tend to grow and shrink depending on the space needed.

• There are a lot of similar-looking tuples littering the code which should be more strictly separated. It would make the code easier to read and reason about, and the type checker would help me more.

The first thing I need to do is sort out my bubble placement algorithm which is clearly not as effective as I’d thought. Then I’ll be replacing Diagrams with GD, I think.

After that there are “to do” items which may happen if it falls easily into my schedule.

• Neaten up the script parser some more to allow multi-paragraph speeches and some unnamed characters to represent narration or offstage voices.

• Make the script preamble more explicit. At the moment I don’t use the author’s name or date or any of that stuff yet but it’s there for the future. It would be better if they existed as named fields rather than just being free-form.

• Write a proper parser for the image maps. I’m currently depending on Neil Mitchell’s TagSoup library for simple HTML parsing. But as I’m already using Parsec elsewhere it seems foolish to depend on them both. Why take two parser frameworks into the shower?

• Proper command line support. Multiple arguments, let the user choose filenames, maybe some help or useful error messages.

Later on there are some things which I would really like to do. These are actual features which are pretty neat:

• Stitch the various scenes together in some formation, eg 2x2 or 3x1, so they can be published as a single unit. The author name and comic strip title obviously become more important at this point as it brings all the images together into a story.

• An alternative that is also pretty good is converting the same story into a flickbook comic, using anim gifs or similar to show the progress.

If anyone has any good ideas just say so! Also if you want me to actually explain how it works I’ll make a detailed post later. Hopefully when it’s closer to working! :-)

I discovered Dinosaur Comics a few years and I think it’s great. It’s a bit strange but you soon get used to the idea. The scene is always the same from comic to comic but the dialogue changes. (Sometimes this repetition is even mentioned in the stories.) Dinosaur Comics is not the only comic in this style, but it’s the first I read and the only one I come back to regularly.

I wondered how these comics were constructed. Most of the comic writers who do this use graphics programmes — Photoshop or Inkscape or something similar. I got to wondering if all that overhead was necessary. The only real changes from episode to episode is the text, which can surely be written just as well in a text file as anywhere else. Is there not a program that can insert today’s script into the scene?

(Now I fully admit that there is a great skill in lettering and bubble placement when making comics. But something I have come to notice recently is that something which is 90% of the way there, or right-on 90% of the time, can be incredibly useful. And let’s not shoot down this project before it’s really airborne, eh?)

Speech Bubble
© Alper Çuğun

I did a bit of search and found some fascinating work, but nothing that seemed to come close to what I was thinking. The coolest thing I did find in the right area was automatic film-to-comic translation research. Using the screenplay and the movie side-by-side, the researchers’ program could extract relevant frames from the movie and place the correct dialogue in speech bubbles next to the actors. One of the authors has written an excellent page showing what their program does and has example scenes from a number of mainstream movies. Naturally, no source code is published. :-(

I decided in the end that any prior art on this subject was too well-hidden for me to find with Google. There were many fits and starts. My first attempts were almost immediately shelved because I was attempting to interface directly with Cairo to draw text and speech bubbles onto images. As nice as Cairo is, it’s not the right level of abstraction for this job.

Later on Brent Yorgey started his Diagrams project, building a functional combinator approach to drawing. This was exactly the approach I needed to get started, and I made some contributions so that it supported text. My sincere thanks to Brent for unwittingly kickstarting this project. I spent some time playing around with Diagrams and getting a feel for the best way to do things. I made a number of examples which could draw speech bubbles and place them on images at some desired location.

After a lot of thinking, and producing altogether too many doodles to be considered healthy, I finally got down to some serious procrastination. My problem was that I didn’t know where to start — I couldn’t see what shape the program was meant to be, and I didn’t work it out for a long time. But since I’m getting close to actually releasing the first version, I can say a good deal more about the structure and construction of the program.

First of all, it does indeed create “comics” out of written scripts. That you can be assured of. To create a three-panel comic strip you will need:

1. A script with three scenes.
2. At least one image, referenced in the script, which depicts the “scene” in the comic strip.
3. A file which gives the co-ordinates of any characters that appear in the scene.

I apologise for the requirement (3) but it’s best way that I know to ensure the speech bubbles can be attached to people in the scene, and to make sure bubbles don’t land in middle of a person’s face. And the idea is that you only have to write this file once. It will always be true for that image. I’ve also made it slightly easier because the parser expects the actual co-ordinate data to be in the form of an HTML image map as exported by any number of graphics programs. You can load your images into The GIMP and save out an image map with each character boxed and tagged. It’s cheap and it works.

On the inside it’s modelled pretty like a compiler. The source file is the script file which is pretty close to the script you’d find for a stage or screenplay. There are a number of obvious differences — specifying filenames, for example — but I’ve tried to minimise the amount of non-story-writing an author would do on a regular basis.

Found
© Alan Woo

The script is loaded in and does two separate things. First it reads through the script itself, noting down the names of characters and everything that they say in each scene. Obviously we want to know what the characters are saying, but knowing who is in a scene is also important. The program finds all the background images whose filenames are stored in the script. At the moment I can only handle .png files but this may change. It then looks for a .map file with the same name and loads that to see which characters appear in that image. If there’s a speaking character in the script who doesn’t have a location in any of the images we have a problem! So it’s important to know who we expect to find and to know that it’s accurate.

All along the way we’re noting down all this information for each scene — who is speaking? where are they? what are they saying? Once we know all this we can start placing speech bubbles around these characters. The canonical method of placing speech bubbles is left-to-right and top-to-bottom (I presume this changes for other languages which read right-to-left or vertically?) so we try that in a very simple way. We create a big margin around every character, like a thick frame, which is where bubbles can be placed. Each time we place a bubble we make sure that previous bubbles are placed “above” or “left” of the current location to keep the sense of the conversation.

Lastly we convert all this abstract data of locations and text and images into concrete files, which are written out to disk: frame1.png, frame2.png, frame3.png. At time of writing there are a few annoying problems, the most important being the bubbles have really rubbish tails. Creating good speech bubbles programmatically — and pointing the tails towards the speaker — is a problem I have not solved. The bubbles are a bit crap right now.

I hope to publish the code and some examples within the next couple of days. Look out for it!

The International Conference on Functional Programming (ICFP) is taking place this week in Edinburgh. A substantial group of attendees are Haskell programmers and researchers, so it seemed a good idea to organise a Hackathon to work on libraries, infrastructure tools and various bits that everybody can use.

Eric Kow was the driving force behind this, and he managed to get us use of the conference facilities on Sunday, while there were a couple of workshops happening elsewhere in the building.

We didn’t have anywhere definite arranged for Saturday, so I went scouting a couple of weeks ago and identified a couple of places that would be suitable. I emailed and phoned Henderson’s and they weren’t horrified by the idea. We spent the day there, making sure to buy enough coffees to keep the management happy. There were 8 or 9 of us at the busiest point and we got some pretty amused/strange looks from other customers: a crowded table of people all with laptops open, ignoring each other…

P1010566
© Brett Holman

In the evening we went out restaurant-hunting, which I don’t recommend in these circumstances — 9 people, Saturday night, Edinburgh festival, centre of town, no booking. I tried calling Calistoga (their number was still in my phone) as they’re both spacious and hidden from the tourists but they couldn’t take us either. We eventually found an Indian restaurant that would take us, so we idled in the pub across the road while they got ready for us.

On Sunday we were using the ICFP conference facilities, deep in the bowels of the Royal College of Physicians on Queen Street. It was a nice room, with little groups of tables, plenty of extension blocks for powering laptops, a flip chart and a projector. We even had wifi, though the networking infrastructure died a few times from heavy use. We were running off a separate system from the rest of the conference centre and their wireless access died, so there was an influx of random conference-goers looking for net access, which brought our wifi to its knees too. I had felt slightly guilty about taking people to a cafe with dodgy wifi the day before, but in fact the conference centre had an even less reliable connection! :-)

My sincere thanks to the staff of Henderson’s for putting up with us, to Graeme Hutton and Philip Wadler for getting us a room in the conference venue on Sunday, to Eric for doing all his organisation and to everybody who actually came along.

I’m putting a call out to everyone that attended to let me know what they did and so on. More updates when I hear back from them.

Here’s an interesting one:

Every system is either an interpreter or a compiler

Don Stewart’s talk Engineering Large Projects in Haskell: A Decade of FP at Galois at London HUG.

Having recently discovered that something I was writing was a compiler, it seems they’re more ubiquitous than people realise. In some sense it seems obvious. Even something like a computer game is obviously an interpreter, converting user input into the syntax of game play and evaluating it… but it also seems like such a stretch. :-)

One of the biggest boons of getting a new laptop has been that I now have access to a powerful enough machine to do programming on. Until very recently I would remember that I had personal projects about once a month, and have to fire up the desktop machine that’s sitting on a desk in the hallway. Neither comfortable nor accessible.

But enough waffle. You sat down this evening thinking, what has Dougal been programming? Didn’t you?

I’ve been playing with the parser combinator library called Parsec. I’m using it to parse a script (as for a stage or radio play) which I’ll be using later.

One of the nicer facilities Parsec has is somewhere to store state as we go along. So you can parse something and store it for later parses. For example, the file I’m parsing has sections that start

Scene 1. <path/to/file>

It’s perfectly legal for subsequent paths to be omitted, in which case we just assume it’s the same as Scene 1:

Scene 2.

Every time we parse a file name we store it for later reuse if the filename isn’t specified at the next section:

-- If no filename is given we fill in the most recently
-- used one. Then we store the current filename for later.
sceneheader = do try scenekw ; spaces
                 num <- many1 digit ; char '.' ; many space
                 oldurl <- getState
                 url <- option oldurl filename
                 setState url
                 newlines
                 return $ Start (read num) url

This really simplifies the sanity checking later on. I like it.

I recently enjoyed reading Oleg Kiselyov’s pair of posts on efficiently building subsets of a particular size. Read part one and part two on Oleg’s site.

(By the way, the very act of looking around his site is like wandering through a junk shop where every item you turn over appears to be some lost treasure. A real joy, with mysteries and delights behind every link.)

Whether you’re interested in efficiently finding subsets of size N or not — and let’s face it, you’re probably not — there’s still something incredibly dramatic about the presentation of the problem and solution. I think there is a certain charm to the writing as well:

This article will show the design of the fastest ever interpreted subsets function. Sorry I’m too excited about this.

A warning of course, that if you’re afraid of parentheses, don’t read any further.