Over the holidays, Stephanie’s family was working on a jigsaw puzzle which featured an image from Winnie The Pooh, which was made up of hundreds of tiny animation cells from Winnie The Pooh cartoons. The puzzle was super tedious, but it did inspire me. I realized it would be a fun programming exercise to try to write a program to generate one of these mosaic images. So that’s what I did that evening, staying up till about four in the morning.

In this post, I’ll be talking about some of the challenges I faced in writing the code. If this doesn’t sound at all interesting to you, but you’d like to see the images I created, you can just view my mosaics photo album that I just posted.

Here is the original image I’ll be working with in this example:

To start with, I take a library of images and reduce them all to 12×9 pixels. This takes a while, so this library is cached. I then use these simplified images to determine which image to use for each tile in the mosaic.

In my first try, I picked the best match possible for each tile. Unfortunately, this results in a lot of duplication, which doesn’t actually look that great.

So, my next attempt was to prevent any image from being used twice. Unfortunately, you need lots of suitable images for this to work; my library of photos wasn’t sufficient. Additionally, because I was processing tiles column-by-column, from left to right, the mosaic generally was truest to the original image on the left, and furthest from the image on the right.

My next idea was to allow an image to be reused, but to limit reuse. So I implemented a system where an image receives a “penalty” each time it is used. The next time I check to see how suitable that image is for a given tile, I add the penalty to that tile’s score. This has the effect of allowing other similar images to be substituted. But after other similar images also have the same penalty, the original image will be selected again. And it will get another penalty. This produces a better image, but it still has the problem of the image getting worse as you go from left to right.

So, I next decided I would fill in the tiles in a random order. This gives better results:

Next, I had the idea that instead of filling them in randomly, I should fill in the tiles with the most detail first. (For those curious, I calculate the level of detail in a tile by computing the average RGB color of each pixel in the tile. Then I take the standard deviation of the “distance” of each pixel’s color from the mean color in the RGB color space. So the most detailed image would be one that is half black and half white. And the least detailed would be one that is one solid color. This isn’t perfect: a tile that is a black and white checkerboard pattern is more detailed than one that is half white and half black, split evenly down the middle. I suppose a better approach would be to do a frequency analysis, and find the areas of highest frequency changes. Similar to the way JPEG compression works. But I thought that was too much work for what I was trying to do.)

So now we have something that I’m pretty pleased with. The next step was just to up the resolution. The image below has 4560 individual tiles:

I’m not releasing the program right now because the code is way too bad. It is very sloppy, nothing is parameterized. (I adjust the parameters right now by editing the code and running from within Eclipse.) Plus, I’m sure there are programs out there already that do the same thing better. If you’re really interested, you can email me. If there’s enough interest, I can try to make the code presentable. But I don’t have any plans for that now.

If anyone wants it, I made a compact Fall 2011 TV premiere schedule. It contains the air time for all the shows, as well as the date of their season/series premieres. It only covers the four major networks because the cable channels are much more sporadic.

Edit: If you’re wondering why some channels are missing on some nights, it’s because I removed some rows that had nothing that looked like anything Stephanie or I would be interested in, in order to make it fit on one page. I only decided to put it up on the internet as an afterthought. This link is basically what I started with, except it is missing the premiere dates which can be found here.

If anyone is using ImageSizer, my unimaginatively-named multi-monitor image resizing and cropping tool, I’ve made some minor-but-long-overdue updates. Namely, it can operate on a list of input files, instead of just one. And the list of input files can be anywhere in the parameter list. So you can do something convenient like this:

1

java -jar ImageSizer.jar -monitorWidth 1024 -height 768 *.jpg

Download it here!

The source is also included in the jar file, if you are interested. And if you don’t know what ImageSizer is, I wrote a pretty extensive description with the initial release, which should answer all your questions.

It’s amazing how often, as a programmer, I find myself pasting something into Notepad, then pressing Down, Home, Ctrl+V, over and over and over. (Or a variant, like Down/End/Ctrl+V, or End/Comma/Delete, or F3/Ctrl+V/Enter, etc.) It gets very tedious, and sometimes requires me to write an adhoc Perl script to do it. Yesterday I had the idea to finally just take a few hours to write a simple tool that I should have written years ago.

I give you: QuickReplace

It’s really simple. Just paste text into the first big text area, and then it will be filtered and displayed in the lower text area. There are three types of filters: text that is prepended or appended to each line; a simple search/replace (with \n and \t allowed), and a full-on regex substitution. And everything is updated as you type it, so you can see the effects of the filters as you enter them. (This really helps when you haven’t written a regex in a month or so.)

Everything is done in Javascript so the page is completely self-contained—you can view source and save a local copy if you wish. (It does require an internet connection, as it uses Google-hosted jQuery.) It’s also kind of a work in progress that might at any time be edited on the fly. Consider yourself warned.

You may recall that the gradients I use on this site (in the background images on the photos pages, and in the header above each comment) are dynamically generated. I made some significant improvements to the code over the holiday weekend, which I will discuss here.

First, the minor things. I’ve added support for If-Modified-Since header, so that no cached image is retrieve and no content is returned to the browser if the user has the image cached. In doing this I learned that PHP’s filectime does not actually return the time the file was created; rather, it returns the last time it was changed. I don’t really understand the difference between this and filemtime (time the file was modified), as they both seem to always return the same time. Oh well.

Next, I added support for 3-character colors (like 000 for black and f00 for red). This just makes sense if you’re used to dealing with them in CSS.

And finally, the big improvement is an implementation of error diffusion.1 Why did I need to do this? In some very gradual gradients, you would see bands of individual colors. Eight bits per channel just isn’t quite enough.  For example, look at this gradient from 0x888888 to 0x444444:

You should be able to see vertical bands somewhere in that gradient. If not, it probably has to do with your monitor’s gamma settings or something. In any case, what I do to prevent this is keep a running sum of how far off each pixel is from its “true” color. When the absolute value of that sum is greater than 1, I adjust the color of the next pixel by one level in the appropriate direction to compensate. This gives a much smoother gradient:

This actually gives better results than Paint.NET and Paint Shop Pro. Here’s a close-up look at what that looks like, with pixel colors exaggerated:

It’s good, though it’s not quite as good as what you get in Photoshop:

Clearly the Photoshop guys are doing some kind of subpixel shading, since there are slightly colored pixels in a monochrome gradient. I guess they know what they’re doing.

Lastly, here is my PHP gradient generator source code, if you want to look under the covers and/or utilize the code.

Last week I came across Ian’s Shoelace Site, which describes several ways of tying your shoes. It turns that there are several more ways of doing it than they teach you as a kid. The “Ian Knot” is a much faster and easier way of tying the standard shoelace knot.  And the “Ian’s Secure Knot” produces a secure knot (it won’t easily come undone through the day), but it’s better than the traditional double knot because you can still easily untie it by pulling the loose ends. I’ve been using these for a week now and it’s a pretty nice timesaver that I thought I’d share with everyone else.

You may have noticed that the thumbnails for albums on our photos page are each little collages. Here are some examples:

Well as of today I’ve received three requests for the code behind these images, so I figured it was time to write up a proper blog post about the it. I mentioned the code in 2006, and that it was inspired by this article from A List Apart. I took their idea and came up with several more layouts to use, and some code to generate the thumbnail from dynamic layouts.

The class takes four image files as input, and generates a thumbnail for them. It does have the annoyance that the generated images have varying heights. I’ve thought about writing a fancy “2.0” version of the code, using Javascript to position/crop/scale the images, then use PHP to render the final result. But who knows if I’ll ever get around to it.

For now, I’ll just show you how it’s used. It’s very easy:

1
2
3
4
5
6
7

$at = new album_thumbnail();
$at->add_image('/images/001.jpg');
$at->add_image('/images/002.jpg');
$at->add_image('/images/003.jpg');
$at->add_image('/images/004.jpg');

$at->make_thumbnail('/images/thumb1234.jpg');

On my admin page, I initially pick four images at random from a given directory. I can then try again with four more images, or specify to keep some of the images and pick random images for the others, or I can specify the ids of all the images I want to be used. That part is left as an exercise for the reader. Without further ado...

View the source code here.

I’ve created a compact (fits on one page!) version of the 2010 Vancouver Winter Olympics TV schedule. (Similar to the one I made for the 2008 games.)  And, like last time, I thought it’d be polite to share it with the world.

You can download it here (PDF format)

A few things to note:

• Times were retrieved from nbcolympics.com, on 2010.02.12. They are subject to change.

• Times are for east coast United States time zone. They’re also in military format to conserve space and avoid ambiguity.

• I don’t care about hockey, and there are a ton of hockey games, so I didn’t include them. If you’re into hockey this isn’t for you.

• Whatever aired on NBC from 8pm to midnight is usually re-aired at 1:30 am that night. I didn’t include that on my schedule.

• Some of the curling events are probably re-airings of the same events, but I’m not sure. I left out some that I thought were re-airings which might not have been. But does anyone really need to watch more than an hour of curling every four years? Just pick one hour, watch it, comment about how it’s such a weird sport and the people look so funny with their brooms, then forget about the sport entirely until the 2014 games in Russia.

• Universal and Universal HD air stuff nearly every day, but it looked like it was all recaps so Ieft it out.

• This was a bit tedious so it’s quite possible I made a typo or two.

• Feedback always welcome

Today I ran across what might possibly be the only cool Facebook app I’ve ever seen. It takes random Facebook status messages from 2009 and makes a collage of them. I thought mine was very interesting:

A week or two ago I discovered the blog How To Write Badly Well. Anyone can write badly badly, but it takes real skill to write badly well, and that is what the blog tries to explore. (The blog only has twenty entries so far, so it’s possible to read from the start if you’re so inclined. Some of my favorite entries are here, here, and here.)

One post asked for badly-well-written 300-word stories, so I figured I’d give it a shot. I made an attempt to ham-fistedly combine fantasy and sci-fi, while also abusing the character map. I wasn’t the winner, so I figured I’d post it here. Enjoy.

Aõgÿne could do this. He knew the dragon had a weak point near her upper rectum, if only he could trick her into exposing it. He tossed an antimatter grenade to the dragon’s left. The implosion would tear a tiny rift though the space-time continuum, which he hoped would frighten the beast. When the grenade detonated the dragon turned with a screeching hiss. At once he activated a laser-tipped spear and hurled it with all his might. It was a direct hit, and the creature cried out in pain as the laser burned through her bowels. Aõgÿne now unsheathed his sword, approached the writhing dragon from behind, and slit her throat in one swift motion. This Wævian moon would be terrorized no more.

But he knew the victory was bittersweet.

After six months on Fa£aña, he would now have to leave. It was all part of the job for an intergalactic dragon slayer like Aõgÿne, and leaving had never been a problem before. But falling in love was never part of the plan. His heart ached as he thought of leaving Eröå behind.

He paused before entering the building to watch her through the window. The sight of her beautiful elvish features was too much for his heart to bear. He scribbled a message on an electronic tablet and placed it in front of her door.  With a heavy heart, he flew away from the moon at three hundred times the speed of light. But he knew there was no speed so fast that the memory of Eröå wouldn’t catch up to him.