Algorithms for the Masses by Julian M Bucknall

Quick links to the most recent posts:

• Ray tracing image from June 2010’s PCPlus (Sun 21-Mar-2010)
• The Daily Shoot 122 (Fri 19-Mar-2010)
• The Daily Shoot 121 (Thu 18-Mar-2010)
• MTF Charts (Wed 17-Mar-2010)
• The Daily Shoot 120 (Wed 17-Mar-2010)
• PCPlus 280: Writing a spellchecker (Tue 16-Mar-2010)
• Daily Shoot 118 (Mon 15-Mar-2010)
• The Daily Shoot 114 (Sat 13-Mar-2010)
• The Daily Shoot 113 (Thu 11-Mar-2010)
• PCPlus 279: JPEG compression (Wed 10-Mar-2010)

I’ve just sent off June 2010’s article for PCPlus to my editor, just a smidgeon late. A couple of days is all. It’s on ray tracing, something I’ve wanted to discuss and play around with for a while. I downloaded POV-Ray, an open-source ray tracing renderer for Windows, OSX, and Linux to use as a test-bench, and spent some fun hours with it.

For the article I had to create an original image. Well, not ‘had to’ exactly, but I thought it only right that I show something that didn’t come from wikipedia or some other ray tracing enthusiast’s site. I certainly didn’t want to show the standard reflective ball hovering over a checkerboard image, although I admit snagging the sphere code from Christoph Hormann’s site. I decided to go for an image showing a 6×10 pentomino solution, since the previous article was about pentominoes and how to solve geometric puzzles with them.

Here’s the final image, after I’d spent entirely too much time this morning messing around with various options instead of completing the ruddy article.

(Click to make larger.) In essence I wanted to show off most of the topics I discussed in the article in one image. The pentominoes are translucent, so the shadow is colored. There are two light sources, a main white one and a slightly reddish-tinged dim one. The spheres reflect each other, the solution, and the shadows.

If you’ve downloaded POV-Ray and want to generate this image yourself, here’s the code. If you want to read the article, buy PCPlus’ June issue when it hits the newsstands, or wait until June 2011 when I’ll publish it here on this blog.

Share it:                

The Daily Shoot for Wednesday, March 17 (#ds122) was either wacky or genius, I’m still not sure. “Grab your camera and walk 2 minutes in any direction. Stop. Find a photo worth making from where you stopped and post it.”

A two-minute walk is roughly 200 yards, maybe 250. I work at home and that would basically put me somewhere within our neighborhood. No chance of getting outside it at all. So, at lunchtime, I diligently set the timer on my iPhone to two minutes, stepped outside the front door and pressed Start. At the end of the driveway, which way? I decided to go up the hill since we always drive home from the bottom. At the top, a junction. Which way? Let’s go left, I thought. A neighbor just there was having some flooring put in, bang, bang. Felt somewhat self conscious lugging around this camera plus zoom lens in the brilliant midday sun. It’s a short little street-let and another junction. I decided to go left again. A couple of steps and the Marimba sound played on the iPhone. So, here, then.

What’s here? Houses, gardens, a couple of cars further down. Felt self-conscious just standing there, looking around, casing the joint. Hmm. On the other side of the street was one of the postboxes that serve mail for a dozen houses. It’s different than the one in between our house and my neighbor’s, newer. It had a bright red sign on the grey background. Let’s go for that.

I also took another photo, this one of the box for large parcels, as I wasn’t quite sure how the first would look.

Both were cropped a little from the originals, but I didn’t futz around with any other settings.

I felt bloody daft taking photos of mailboxes in the dazzle of the midday sun, so it was with some relief than I walked down the street to complete the full circle to get back home.

Share it:                

For Tuesday, March 16 (#ds121), the Daily Shoot assignment was “Today's theme is ‘3’. Make a photograph that features the number itself or otherwise represents 3 items.”

I was determined to take a photo outside today (sometimes I think it’s cheating to do too many staged photos inside). But what? I was stumped, plus my lunchtime was curtailed because of a delayed conference call. In the end, as I was leaving to go to rehearsal at 6:30pm, I saw a road sign that I’ve seen a bazillion times and decided to go for that. It was getting late, so the lighting wasn’t that great.

So, all in all not a brilliant photo, plus I was shooting into the sunset to a certain extent. It’s also fudged with to reset the white balance, to crop and straighten it, and to sharpen it all (I use the Clarity setting in Adobe Lightroom to sharpen). A bit scrappy.

Share it:                

I was looking at the following lens, Canon EF-S 18-135mm f/3.5-5.6 IS, on Amazon today. The reason is simple: my favorite zoom is the Canon 28-135mm and I also have a Canon 20-35mm zoom. This could replace both, in theory. At something like $340, it’s affordable too. But how good is it?

The technical description had the following charts to help describe the performance of the lens, both at full telephoto and fully wide-angle:

Riiiight. I’m sure that helps, but I don’t have the decoder ring. What does it all mean?

Back to basics. A lens captures and focuses light onto the camera’s CCD sensor (or film, if you’re still using that). In a perfect world, a lens would let all of the light pass through without hindrance, but it just ain’t so. The focal length of a lens has an effect, as does the aperture. The lenses are built such that the center of the image has the best appearance, but the further you look away from the center the worse the distortions get. At a wide-angle with a wide aperture, the edges of the resulting photo are distorted the most. It could be color fringing or aberration (usually abbreviated to CA for chromatic aberration), it could be vignetting (the edges and corners having a distinct darkening), it could be a myriad other problems. The longer the focal length or the smaller the aperture, the less distortions you get (although at very small apertures, you’ll start to suffer from interference patterns).

For a given lens, these distortion effects will be different than another lens. How to best describe the capabilities of the lens then? Enter the Modulation Transfer Function (MTF) chart.

The two things in a lens we’re interested in are the resolution and the contrast. The resolution of a lens is a measurement of how finely the lens can resolve a set of parallel lines, black lines on a white background. At some point the black lines are thin enough to smear with each other to form a grey-ish color and this point varies with the focal length and the aperture, as well as the distance from the center of the CCD. This is the resolution. Contrast on the other hand is a measure of the difference between pure black and pure white. It’s intimately tied with the resolution, since the resolving power of the lens is correlated to the contrast.

To measure this stuff, the camera and lens are focused on a special card that has a black and white cross-hatching printed on it. There are two types of hatching: one patch at 30 lines per millimeter (in other words, very fine), and another patch at 10 lines per millimeter (that is, coarse). These patches are repeated across the card, some along and parallel to the diagonal of the image (known as sagittal lines), the others perpendicular to those (and known as meridional lines). For each focal length, measurements are taken with the aperture at its widest and with the aperture set to f/8, the aperture that produces the most accurate image. (The image on the right is courtesy and copyright Canon.)

Now we can look at the chart. The X-axis measures the distance in mm along the diagonal from the center of the image. The Y-axis measures the contrast as a percentage from 0 to 100% (or equivalently from 0 to 1.0). 100% contrast is the maximum difference between black and white, anything lower than that indicates that blacks are tending to dark grey and whites to light grey. 0% means you can’t tell the difference between black and white.

On the chart there is a confusion of black lines, blue lines, lines that are solid or dashed, and lines that are thick or thin. Each attribute measures something different:

• Thick/thin — This attribute is a direct measurement of the type of cross-hatching, whether coarse or fine. You’d expect the thicker lines to be above their thinner siblings in the chart.
• Black/blue — This attribute defines a wide-open aperture (black) versus f/8 (blue). You’d expect the blue lines to be above their black siblings.
• Solid/dashed — This attribute measures meridional lines (solid) or sagittal lines (dashed). You’d expect them to be pretty much the same, all other things being equal.

So, using all three binary attributes, you’d expect 8 lines on the chart. If you look at the charts above that’s what you’ll see.

What are you looking for? First of all, a contrast value above 0.8 means you’ll get excellent image quality. Between 0.6 and 0.8, it’s satisfactory; below 0.6, it’s just so-so. Given that, you want the lines to be as high as possible in the chart. Next up, the higher the thick lines are, the better the lens will be at reproducing contrast. Similarly, the higher the thin lines, the better the resolving power of the lens. Finally you’d like the black and blue equivalent lines to be as close together as possible: this means the lens performs just as well wide open as at f/8, the sweet spot, aperture-wise.

Take a look at the telephoto chart above (the left-hand chart). First of all, the lens performs just as well when wide-open or at f/8: all pairs of black/blue lines stick close to each other. Mind you, wide-open telephoto on this lens is f/5.6, only one stop below f/8, so you’d expect the line pairs to track each other closely. Next, the contrast provided by the lens is satisfactory to excellent (the bold lines). The resolution of the lens is equally impressive. The only issue seems to be that the lens exhibits some kind of astigmatism: the differences between meridional and sagittal values is quite marked (solid vs. dashed).

The wide-angle chart is all over the place. For a start you can see that at f/8 the lens resolves much better than when wide-open (the thin lines). Ditto for contrast (the thick lines). There’s also more difference between the meridional and sagittal values. Notice how some of the lines suddenly drop off to the right: at wide-angle the lens suffers from edge distortions.

All in all, I’d say that this lens set to wide-angle should not be used below f/8 and you should expect to crop your photos towards the center to avoid edge distortions. Telephoto is better, but again the best resolution is still close to the center. Given all that, I’d also say that I’m going to stick to my current setup.

Share it:                

I skipped Sunday’s assignment for one reason or another, and so the next time I took up the camera for the Daily Shoot was for Monday, March 15 (#ds120): “Trees and plants are great photographic subjects. Make a photograph of a tree or plant today.”

Perhaps a little easy this one, or maybe I should’ve spent a little more time on finding something else to shoot:

The subject was an indoor ivy that we’d just been given. Nothing too fascinating about this shot really: just green ivy leaves, a bit of bokeh, and the contrasting-colored wall. For a change, I used my monopod instead of the tripod.

Share it:                

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. What I’ll do is publish the article from a year ago or so here when I purchase the current issue.

Since I picked up April 2010’s issue when I was in England just over a week ago, I’m publishing this article from April 2009 slightly earlier than I usually do (which means May 2009’s article will be posted in June or something).

The topic is pretty interesting: how does a spell-checker give you alternatives to a badly-spelled word? The first step — finding out if a word is misspelled — is simple enough as a basic algorithm: just look it up in a big ol’ list o’ words. The next step can seem daunting though: how can you generate a valid list of possible corrections? The article talks about a few possibilities: the Levenshtein distance, the Damerau algorithm, and the Soundex method.

The Levenshtein distance is a bit impractical for a large list of words, although there are certain techniques you can use to speed things up. It essentially calculates the edit distance (the number of character insertions and deletions to go from one word to another) of the misspelled word and every other word in the list. The words with the smallest edit distance are your correction candidates. As I said, possibly too slow for a large dictionary, although it’s a great algorithm for creating diff tools.

The Damerau algorithm essentially calculates all the words that can be formed form the misspelled word by a single mistyped letter and checks those in the dictionary. Those that are present are valid correction candidates. Although single mistakes are common, two or more mistyped letters in a single word is fairly rare, so the algorithm does pretty well (as the article shows).

The Soundex algorithm is a “phonetic” algorithm: it finds candidate words that “sound like” the misspelled word.

Of course the article doesn’t go into deeper, harder algorithms for space reasons. For example, Bloom filters are great for compressing the dictionary at the expense of a few false positives and can be used to replace the article’s hash table for the word list. Different dictionaries could be employed that just store root words and then describe possible suffixes, prefixes, and circumfixes that can go with each word (for example, Hunspell). Better phonetic algorithms now exist than Soundex (for example, Metaphone). Nevertheless, I think the article hangs together quite well and I’m pretty pleased with it.

This article first appeared in issue 280, April 2009.

You can download the PDF here.

Share it:                

Our assignment from the Daily Shoot for Saturday 13 March (#ds118) was “Curves, squiggles, and flowing lines interest the eye. Make a photograph dominated by a curvy shape of some sort today.”

Mehul at work has just bought himself a Nikon DSLR (a D90 if I recall — I’m a Canon-boy myself) and was asking for some help with it while I was in the offices at Glendale this past week. I was trying to explain bokeh and how the aperture has an effect on it (and probably confusing the poor chap), so it came to me that I should take a photo with lots of bokeh, to illustrate it for him. Here we are: my fave zoom at 135mm, with f/5.6 and some ridiculously slow shutter speed that necessitated a tripod. Plus I was holding up a white sheet on the right to reflect some natural light...

It came out pretty well, considering. I did take another at f/16 to show the difference, but I must have jogged the tripod during the eons-long exposure and it came out shaken. I was using a remote to make sure I kept my hands off, honest...

(Aside: the remote I was using was the Canon RS60-E3. It plugs into the side of the camera — I have a Canon Rebel XTi — and allows you to take either a simple shot, with auto-focus by pressing half-way, or a shot with shutter locked open (“bulb-mode”). Well worth the $20. You can even get Chinese knock-offs for about $6 on eBay.)

Now playing:
Orb - Into the Fourth Dimension: Essenes in Starlight
(from The Orb's Adventures Beyond the Ultraworld)

Share it:                

The Daily Shoot assignment for Tuesday 9 March (#ds114) was “Most of us enjoy some symmetry in our lives. Look around for it today and make a symmetrical photo.”

There are several different types of symmetry, mathematically speaking: rotation, reflection, and translation being the basic, most familiar ones. Since everyone seemed to be going for reflection symmetry prior to my shot, I thought I’d do translation symmetry:

Again I “cheated” by pointing my camera out the window from my desk. The window is slightly tinted, giving the grayish pallor to the photo. Perhaps I should have bumped the greens up a bit and reduced the blues.

Share it:                

Because of travel, the next assignment from the Daily Shoot I was able to tackle was that for Monday 8 March (#ds113): “Take care of the Monday blues by picking up your camera. Make a photograph dominated by the color blue.”

I’m in Glendale this week at the DevExpress offices for my monthly visit, and I confess I just pointed my camera through the window opposite my desk at the new office block opposite. A very greyish blue, I’d say:

Share it:                

I write a monthly column for PCPlus, a computer news-views-n-reviews magazine in the UK (actually there are 13 issues a year — there’s an Xmas issue as well — so it’s a bit more than monthly). The column is called Theory Workshop and appears in the Make It section of the magazine. When I signed up, my editor and the magazine were gracious enough to allow me to reprint the articles here after say a year or so. What I’ll do is publish the article from a year ago or so here when I purchase the current issue.

One of the topics I wanted to write up back when I had a two-page article was how JPEG compression worked, but I didn’t think I could cover it adequately in such a small space. So for March 2009 I tried with my new three-page allowance, but found that it was equally as difficult. Trouble is, there’s so much to talk about: colour spaces, DCTs, downsampling, Huffman encoding, and so on, so forth. So in the end, it turned into more of a layman’s discussion than any kind of deeper/broader article that laid down the foundations of why JPEG compression works, and why, sometimes, it doesn’t very well.

I also tried to show with an image, what the conversion of an RGB image to the YCbCr colour space would look like, and completely ignored the fact that, although our screens use the RGB colour space, printers use the CYMK colour space. I was expecting it all to get translated from RGB to CYMK properly and the inks to cooperate as they were laid onto paper, etc. Even looking at the PDF of the article, that “decomposition” image looks weird. This is what it should look like (click on it for the full size image):

I actually created each supplementary image in code by using the RGB-YCbCr conversion equations on the original image and then stitched them together.

    private void button1_Click(object sender, EventArgs e) {
      Bitmap input = new Bitmap(@"D:\Users\Julian M Bucknall\Pictures\Group.jpg");

      Bitmap lumaImage = new Bitmap(input.Width, input.Height, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
      Bitmap crImage = new Bitmap(input.Width, input.Height, System.Drawing.Imaging.PixelFormat.Format24bppRgb);
      Bitmap cbImage = new Bitmap(input.Width, input.Height, System.Drawing.Imaging.PixelFormat.Format24bppRgb);

      for (int c = 0; c < input.Width; c++) {
        for (int r = 0; r < input.Height; r++) {
          Color color = input.GetPixel(c, r);
          int Y  = (int) Math.Round(( 0.2990 * color.R) + (0.5870 * color.G) + (0.1140 * color.B));
          int Cb = (int) Math.Round((-0.1687 * color.R) - (0.3313 * color.G) + (0.5000 * color.B));
          int Cr = (int) Math.Round(( 0.5000 * color.R) - (0.4187 * color.G) - (0.0813 * color.B));
          color = Color.FromArgb(Y, Y, Y);
          lumaImage.SetPixel(c, r, color);
          Cr *= 2;
          if (Cr >= 0)
            color = Color.FromArgb(Cr, 0, 0);
          else
            color = Color.FromArgb(0, -Cr, -Cr);
          crImage.SetPixel(c, r, color);
          Cb *= 2;
          if (Cb >= 0)
            color = Color.FromArgb(0, 0, Cb);
          else
            color = Color.FromArgb(-Cb, -Cb, 0);
          cbImage.SetPixel(c, r, color);
        }
      }
      lumaImage.Save(@"D:\Users\Julian M Bucknall\Pictures\GroupLuma.jpg", System.Drawing.Imaging.ImageFormat.Jpeg);
      crImage.Save(@"D:\Users\Julian M Bucknall\Pictures\GroupCr.jpg", System.Drawing.Imaging.ImageFormat.Jpeg);
      cbImage.Save(@"D:\Users\Julian M Bucknall\Pictures\GroupCb.jpg", System.Drawing.Imaging.ImageFormat.Jpeg);
    }

Well, OK, there is a little bit of futzing around in there so that you can more easily visualize the Cr and Cb images. I can’t remember now why I chose the code I did; only that there was quite a bit of experimentation behind it so that the results would look good when printed, albeit inaccurate.

Although I’m not 100% happy with how the article turned out when printed, and possibly three pages is still too few to do the subject justice, I did enjoy the research and the playing around that went into it. It is a fascinating topic; one that has more than its fair share of voodoo (where do those constants in the RGB-YCbCr conversion equations come from again?).

This article first appeared in issue 279, March 2009.

You can download the PDF here.

(Quick aside: PCPlus used to put part of their archive as PDFs on the DVD in the back of the magazine. They’ve now moved to a CD instead of a DVD, presumably to save on costs, and the archive is no longer on there. I hear they’re going to publish it online instead, sometime in the near future.)

Share it: