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.

Here is a tip for writing better SQL queries—specifically, the FROM/WHERE clause.1 I only work with SQL Server and MySQL, so the syntax may be different in different engines.2 I’m writing this because I often see very smart and experienced developers write some downright ugly SQL. I don’t mean to call anyone out; I just want everyone to know there is a better way of joining.

Rule of thumb: If you have a comma in your FROM clause, you’re doing it wrong.

Let’s take a query I just made up as an example

1
2
3
4
5
6
7
8
9
10
11
12
13
14

SELECT AVERAGE(Grades.score)
     , Departments.Name
     , Students.Gender
FROM Students,Grades,Departments,Teachers,Courses,Classrooms,Buildings
WHERE Students.id = Grades.Student_id
  AND Courses.Period = 3
  AND Courses.id = Grades.Course_id
  AND Buildings.Building_id = 11
  AND Classrooms.id = Courses.Classroom_id
  AND Buildings.id = Classrooms.Building_id
  AND Grades.Grade > 0
  AND Teachers.id = Courses.Teacher_id
  AND Departments.id = Teachers.Department_id
GROUP BY Departments.Name, Students.Gender

So what’s so bad about this? First of all, it’s tricky to see what exactly we are trying to do here. The WHERE clause is huge, and it’s full of stuff that isn’t really relevant to what we are trying to return. If you were told that this query was returning the wrong values, you would have to stare at it for quite a while to figure out what’s going on here. You know what tables the data is coming from, but you don’t have any simple way to tell how those tables relate to each other. You have to reverse-engineer that information from the monster WHERE clause.

And here is where developers are most likely to mess up: if you forget just one of those AND predicates in the WHERE clause, you end up with a cartesian product. This means if one table has n rows, and another has m rows, you will get n×m rows. This is pretty much never what you actually want. If the developer is working on a small database, with very little data3, he might not even realize this is happening. He checks in his code, and goes on to the next problem. But then the system goes into production, and the tables get a few hundred rows each, and now the query runs for twenty minutes and then the database server crashes! Ouch.

So, what’s the solution? Like I said, if you see a comma in your FROM clause, you’re doing it wrong. JOIN to the rescue!

1
2
3
4
5
6
7
8
9
10
11
12
13
14

SELECT AVERAGE(Grades.score)
     , Departments.Name
     , Students.Gender
FROM Grades
JOIN Students    ON Students.id = Grades.Student_id
JOIN Courses     ON Courses.id = Grades.Course_id
JOIN Teachers    ON Teachers.id = Courses.Teacher_id
JOIN Classrooms  ON Classrooms.id = Courses.Classroom_id
JOIN Departments ON Departments.id = Teachers.Department_id
JOIN Buildings   ON Buildings.id = Classrooms.Building_id
WHERE Buildings.Building_id = 11
  AND Courses.Period = 3
  AND Grades.Grade > 0
GROUP BY Departments.Name, Students.Gender

In this version of the query, we JOIN each of the tables together in the FROM clause. This has several advantages, but the biggest by far is that it forces the developer to specify how the tables are joined together. This makes it extremely difficult to accidentally create a cartesian product. It also cleans up the WHERE clause, stripping it down to conditions you are actually filtering on. In this case, we are just looking at third-period courses in some particular building where students are at least attending the class. Whenever I make a change to an existing query that doesn’t use joins, I usually rewrite with joins. I’ve done this for dozens of queries, and the WHERE clause is reduced to a single statement probably 80-90 percent of the time. This makes the query much easier for the next developer to understand at a glance, especially since the join conditions aren’t likely to change over time. As far as performance goes, there is a slight benefit because you’ve already told the database how the tables are joined together. But the database was already figuring this out on its own, so there’s not much of a difference. But it certainly doesn’t perform any worse.

Update 4/18: I forgot to mention one other benefit of this approach. There is a type of error that comes up every once in a while looks something like this: “This query doesn’t return online courses because Courses.Classroom_id is 0/NULL for online courses.” This is easy to solve with joins. Just change the “JOIN Classrooms” clause to “LEFT JOIN Classrooms”. I’ve seen some ugly code that tries to accomplish the same thing with UNION. Union is worse for performance than left join, and left join is specifically designed for this purpose.

Here’s an update on a few side projects I have going. First, you may remember QuickReplace. As I used it myself, I realized that there were some limitations, which I set out to address. So now we have QuickReplace 2.0. One thing I found myself doing with QuickReplace was opening it in several tabs, pasting text in the first tab, copying the output and pasting it in the next tab, because each tab could only run one filter at a time. But now, instead of having a fixed number of filters, which are executed in a fixed order, you can add as many filters as you want. The filters can be dragged and dropped in whatever order you want. And, if you want to save a filter and run it later, there is now a permalink option to do so. As before, the tool was written for me by me, with the assumption that the user (me) knows what they want to do. If you’re a programmer and you understand regular expressions, you should be able to figure it out. I’ve been using the new version for about a month and I think I’ve ironed out all the bugs, but if you find one let me know and I’ll take a look. Unless your “bug” is that it doesn’t work in a browser other than Firefox or Chrome. In which case the bug is that you’re using the wrong browser. (That being said, it seems to work just fine in IE, Safari, and Opera, but I haven’t tested extensively.) Also, the HTML file is self-contained, so you can save it locally if you’d like. (But you can’t run it offline because of a dependency on Google-hosted jQuery.)

The other side project I’ve made some updates to is my gradient generator. The previous version would generate horizontal or vertical gradients. But then I started thinking, wouldn’t it be better if it generated diagonal gradients too? So I worked out the math and made it happen. Now, instead of an “orientation” parameter that takes either “h” or “v”, we have an “angle” parameter, which takes a number in degrees (from 0 to 360, inclusive). It still takes “h” or “v”, for backwards compatibility—”h” is converted to 0, and “v” is converted to 90.

I added an extra parameter, “extend”. If it is false, the image is only as large as it needs to be to hold the gradient. This is OK if the image is being used as the background of a fixed-size element, but otherwise you won’t see the whole gradient. This is where the extend parameter comes in. If it’s set to true, you will see the whole gradient.

So here’s what it looks like without the extend parameter:

You might also notice that the y axis is inverted. That’s just how images are oriented, and I didn’t correct for it since I figure the most common case is a gradient oriented in the top-left corner. Now, if the gradient is extended, it will look like this:

You can view the gradient generator source code here.

Of course in a few years, when CSS 3 gradients are fully supported, my gradient generator will be obsolete. Oh well.

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.

Earlier this week I was informed that Twitter will soon be ending its support for “BasicAuth” in the Twitter API, in favor of OAuth authentication. This affects me because I use the API to automatically post a “just blogged!” link to Twitter after every new blog post. Using BasicAuth, this was super simple:

1
2
3
4
5
6
7
8
9
10
11

function postStatus($status, $username, $password)
{
  $ch = curl_init();
  curl_setopt($ch, CURLOPT_URL, 'http://www.twitter.com/statuses/update.xml');
  curl_setopt($ch, CURLOPT_CONNECTTIMEOUT, 2);
  curl_setopt($ch, CURLOPT_POST, 1);
  curl_setopt($ch, CURLOPT_POSTFIELDS, 'status=' . urlencode($status));
  curl_setopt($ch, CURLOPT_USERPWD, $username . ':' . $password);
  
  return curl_exec($ch);
}

OAuth is a little more complicated, but I got it to work after about four or five hours of banging away it with the help of this article.1 Since I couldn’t find anywhere that this was described in detail, I decided I would document the whole process here on my blog. I don’t claim that this code is great, but it gets the job done. If you couldn’t care less about the workings of OAuth, and just want a give-me-teh-codez solution, then this is for you.

The first thing you have to do is register a new app. This sounds scary but it’s actually very easy. When filling out the form, note the following fields:

• Application Name: this is what will show up under your tweets. In my case, I chose “vacantnebula.com” since all tweets from my app are announcements of new posts on this site.

• Application Website: this is the URL that application name will link to.

• Application Type: I’m not sure if it matters, but I chose “client”.

• Default Access Type: you must select “read & write” to be able to update status (i.e. “write”).

After registering your application, you can view application details. Here you will see your consumer key and your consumer secret. You will need these keys later.

For a single-user application (which is what I’m describing), you will need to click on my access token. This will give you the access token (oauth_token) and access token secret (oauth_token_secret). Again, you will need these later.

And without further ado, here is the code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84

<?php

class twitter
{
  //FILL IN THESE VALUES!!
  private $consumerKey      = '???';
  private $consumerSecret   = '???';
  private $oauthToken       = '???';
  private $oauthTokenSecret = '???';
  
  /**
   * Posts status to a twitter account. Returns true if successful, result
   * of curl_getinfo() if failure. 
   */ 
  function postStatus($status)
  {
    return $this->apiCall('https://api.twitter.com/1/statuses/update.xml'
                         , array('status'=>$status));
  }
  
  //separate function to leave the door open to other API calls...
  private function apiCall($url, $params)
  {
    $method = 'POST';
    
    //postString covers what will *actually* be posted
    $postString = $this->joinParams($params);
    
    //now adding to $params other OAuth properties...
    $params['oauth_nonce']            = sha1(time() . mt_rand());
    $params['oauth_timestamp']        = time();
    $params['oauth_signature_method'] = 'HMAC-SHA1';
    $params['oauth_version']          = '1.0';
    $params['oauth_consumer_key']     = $this->consumerKey;
    $params['oauth_token']            = $this->oauthToken;
    
    ksort($params); //IMPORTANT!
    $paramString = $this->joinParams($params);
    
    $signatureBaseString = $method
                         . '&' . rawurlencode($url)
                         . '&' . rawurlencode($paramString);
    $signatureKey = $this->consumerSecret . '&' . $this->oauthTokenSecret;
    $params['oauth_signature'] =
            base64_encode(hash_hmac('sha1', $signatureBaseString, $signatureKey, true));
    
    $authHeader = 'Authorization: OAuth realm=""';
    foreach($params as $key => $val)
      $authHeader .= ", $key=\"" . rawurlencode($val) . "\"";
    
    
    $ch = curl_init();
    curl_setopt($ch, CURLOPT_URL, $url);
    curl_setopt($ch, CURLOPT_CONNECTTIMEOUT, 2);
    curl_setopt($ch, CURLOPT_RETURNTRANSFER, 1);
    curl_setopt($ch, CURLOPT_POST, 1);
    curl_setopt($ch, CURLOPT_POSTFIELDS, $postString);
    curl_setopt($ch, CURLOPT_SSL_VERIFYPEER, false); //required for HTTPS URL
    curl_setopt($ch, CURLOPT_HTTPHEADER, array($authHeader));
    
    $content = curl_exec($ch);
    $resultInfo = curl_getinfo($ch);
    curl_close($ch);
    
    if ($resultInfo['http_code'] == 200)
      return true;
    
    $resultInfo['content'] = $content;
    return $resultInfo;
  }
  
  //Join key/value pairs together in url string format, encoding values.
  private function joinParams($params)
  {
    $paramString = '';
    foreach($params as $key => $val)
    {
      if($paramString !== '')
        $paramString .= '&';
      $paramString .= $key . '=' . rawurlencode($val);
    }
    return $paramString;
  }
}

And I assume you know this, but to use the API it’d look like this:

1
2

$twitter = new twitter();
$result = $twitter->postStatus('hello world!');

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.

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 wrote a program last week for resizing images so that they can fit onto a two-monitor desktop, and I figured I’d share with the world before heading to the beach.  This program does more than just resize an image, though.  It accounts for the gap between the two monitors, so that it looks much more like you are looking through the monitors.  Most of this post will consist of an explanation of what exactly that means and why you’d want to do it.

Okay, for starters let’s say you have two monitors sitting side-by-side.  In our example, these monitors each have a resolution of 304×228 pixels, giving a resolution of 608×228 for the entire desktop.  Here is what that looks like:1

Now, let’s say you want to use this photo of the Gizah pyramids by Ricardo Liberato, the #21 finalist for Wikimedia Commons Picture of the Year 2007, as your wallpaper.  Here is what the photo looks like initially:

There is a problem here, because that’s not the right proportion, so you’d want to crop out a portion of the image that is the right proportion.  Here is a cropped portion that is the proper ratio and size (608×228):

Now, let’s use that image as our desktop wallpaper on our dual-monitor setup:

I don’t know about you, but I find this very aesthetically displeasing.  Suddenly the pyramid is not shaped like a pyramid anymore!  Your mind expects the image to continue through the space between the monitors, but it actually just picks up where it left off on the edge of the other screen.  In fact, it kinda makes it look like there is a fourth, smaller pyramid, between the first and second one.

So here’s where my app comes in.  We need to figure out how wide that gap is, in pixels.  If you knew the dpi of your monitor, you could measure the gap in inches and calculate the number of pixels.  But if you don’t know that, here’s how I measure it.  Open up any kind of image editing app (Paint will do just fine).  Place the window so that it straddles the gap between monitors.  Draw a 45-degree line that spans the monitors.  It is very important that the line be exactly 45 degrees (you can hold control or shift or something to fix the line to 45 degrees in most image editing apps).  Now, hold something with a straight edge (say, a piece of paper) so that it lines up with the line on one monitor.  Holding the straight edge there, click somewhere on the other monitor, where the line would be if it was accounting for the gap, and draw another 45-degree line starting from there.  Now measure the vertical distance, in pixels, between the two lines.  This will be equivalent to the horizontal distance, in pixels, between the two monitors.  For our example, here is what that might look like:

You can see the solid black line is “straight” if the gap is not accounted for.  However, the dashed line shows how the line would behave if the gap was considered to have a width.  The distance between the dashed line and the solid line on the right-hand monitor is 50 pixels, so that is the width of our gap.  So now, let’s use my app:

1

java -jar ImageSizer.jar pyramids.jpg -monitorWidth 304 -height 228 -gap 50

This will generate pyramids.resized.png, which looks like this:

When we use this image as our desktop wallpaper, we get an image that looks correct:

If you’d like the program, you can download it right here.  But before you use it, here are a few things you should know:

• You may get OutOfMemory exceptions on very large images.  If this happens (thanks Peter), you can increase the Java heap size from the command line like this:
      java -Xmx256m -jar ImageSizer.jar ....
  If that still doesn’t work, increase the 256 to a bigger number.  It is important that the -Xmx parameter comes before the -jar parameter, so that Java knows it is a parameter to the JVM and not to the ImageSizer.

• When the image is not the proper proportion (which will be nearly all the time), it will crop from the middle of the image.  In many cases, this will be a less-than-ideal cropping.  If that happens, you should crop the image the way you want it cropped first.  (The tool will still help you out because removing the middle of an image is much more tedious.)

• Your monitors must be of equal resolution.

• Supported file types are .jpg, .png, and (I think) .bmp and .gif.  (I’ve only tested jpg and png myself though.)

• Output file will always be .png format, even if a different extension is used on output file.  This is important because a lossy compression can cause some pixels to “bleed” between the monitors.

• There is only support for two-monitor setups.

• If you want to modify the code, feel free to do so.  You can even redistribute if you want, just be sure to leave my name and URL in the comments and help info.  The source is included in the jar file (open it as a zip file).  There are only two Java files.

• There is a good chance there are some bugs, as this was written in two evenings, with a fourteen-month-old competing with the computer for my attention.  The vast majority of that time was spent trying to figure out how to use the Java image libraries.  I probably could have written this in PHP in an hour, but I didn’t want to use PHP from the command line, and I didn’t want to have to upload large images.

I learned something new about databases this week.  Perhaps I should have already known this, but it surprised me, so I have decided to share with the small segment of the world that reads this blog.  In the past, I’ve always done database table management (i.e. creating/dropping tables or columns) through a GUI (like Management Studio for SQL Server, or phpMyAdmin for MySQL).  In these tools, it is very easy to insert a new column in the middle of a table, and it never occurred to me that this was a big operation.  This week, I had to write a script that would perform my changes to a table on a customer database.  It turns out that the only way to put add a new column to the middle of a table1 is to:

1. Create a temporary table, with the columns in the order you want.

2. Insert everything from your original table into the new table.

3. Drop the original table.

4. Rename the temporary table to the name of the original table.

5. Recreate any indexes and constraints that existed on the original table.

On a very large table, this is quite a lengthy operation!  But if you just add the new column to the end of the table, you can do that in a single SQL statement, and it runs quite quickly.  And the fact is that if your code relies on the columns being in a particular order, you are doing something wrong.  (Fortunately, I knew enough that I got that part right.)