Monthly Archives: September 2007

Ask Dr. Color’s Assistant: Tone-mapping in MATLAB

How does the tonemap function in the Image Processing Toolbox product work?

Tone mapping, or tone reproduction, compresses the enormous amount of illumination data in a high dynamic range image to something more suitable for output on a medium that has a lower dynamic range. The recent discussion of my office image shows the results of tone mapping.

But what is dynamic range? And what makes a high dynamic range image?

In the simplest terms, dynamic range is the ratio of the brightest value in an image or scene and the darkest value. Consider the following table of illumination sources from High Dynamic Range Imaging by Erik Reinhard, Greg Ward, Sumanta Pattanaik, and Paul Debevic:

Condition Illumination (in cd/m2)
Starlight 10-3
Moonlight 10-1
Indoor Lighting 102
Sunlight 105

The human visual system is capable of discriminating about five orders of magnitude at most of these different illumination levels.[1] That is, if you have normal vision, you can see something with a brightness value of 1 and a value of 100,000 in the same scene. Under different conditions, you might be able to make out detail in something with a value of 0.001 at the same time that you look at an object with a brightness level of 100. What you can’t do is see detail in something with a value of 0.001 and another thing with brightness 100,000 simultaneously. That would require being able to distinguish between eight orders of magnitude at once.

An image with values that range from 1 to 100,000 has a dynamic range of 100,000:1. Most of the images made for display on contemporary monitors have a dynamic range of only 256:1 per color channel, because that’s all that most monitors are built to support. We’ll call the latter images low dynamic range (LDR) images and anything with the ability to store more illumination detail a high dynamic range (HDR) image. There’s nothing stopping us from creating HDR images, but we won’t be able to display them on a LDR device like a monitor or inkjet prints.

Tone mapping is the HDR to LDR conversion. There are many tone mapping operators that we might have implemented. (See “A review of tone reproduction techniques” (2002) by Kate Devlin for an overview of these technique.) We chose a technique that renders floating-point high dynamic range RGB radiance maps to low dynamic range RGB UINT8 images using a spatially uniform tone mapping operator similar to what Ward et al. described in their 1997 paper “A visibility matching tone reproduction operator for high dynamic range images” (IEEE Transactions on Visualization and Computer Graphics, 3(4):291-306). It differs in several ways, though.

In a nutshell, our tonemap function takes the base-2 logarithm of the RGB radiance map to mimic the human visual response to brightness, transforms the image into the L*a*b* colorspace, and performs contrast limited adaptive histogram equalization on the luminance channel without changing the overall color content of the image. After converting the modified L*a*b* image back to RGB, the result for most images is a fairly good LDR image suitable for output. We provide a couple of parameters to improve the “artistic” qualities of the rendering – AdjustSaturation and AdjustLuminance – as well as the ability to tune the histogram equalization.

While our technique doesn’t use much of what is known about how the human visual system performs tone mapping, we think we picked a method that balances good results, acceptable performance, and low complexity. My hope is that people doing work on HDR imagery will take a look at the two-dozen so important lines inside tonemap and see just how easy it is to get started implementing their own tone reproduction operator in MATLAB.

[1] – One “order of magnitude” is one power of ten. Engineering types are fond of talking about orders of magnitude.

Posted in Color and Vision, Computing, Fodder for Techno-weenies, MATLAB, Photography | 2 Comments

Dr. Color’s Assistant goes back to his notes

It’s Friday here at The Metrowest Homeopathic Imaging and File Rehabilitation Center, the day when I usually spend part of my time on 20% projects. [1] But I’ve basically been working on the results of my last such project full time, so perhaps it’s time to take a moment and look at the world rushing by and catch up on a few things before getting too far behind.

I moved offices for about the tenth time since I started working last week. That’s not a bad thing; we’ve been growing consistently over the last 9 1/2 years, and the company likes to keep work groups physically co-located without stuffing people into cubicles. While packing my office, I decided to purge my files, getting rid of a lot of old, old papers. (The process was actually a lot like Merlin Mann’s War on Clutter.)

It was during this time that I realized how much information I have tied up in paper notes. The same goes for e-mails. (Over those 9 1/2 years I’ve managed to keep more than 13,000 7,000 messages.) That information isn’t doing anyone other than me any good at all . . . coworkers, amateur color enthusiasts, no one! So expect to see some random color-related stuff coming your way.

[1] – A 20% project is a self-directed project that’s “off the books.” There are two main reasons for doing projects like this. It gives people freedom to explore and dive into topics that are risky or somewhat out-of-model. These projects also add slack to a system, preventing workers from being overutilized. Studies show that beyond a certain point the more you use any resource — whether it’s an engineer, a highway, a drillbit, whatever — you get lower productivity.

Posted in Color and Vision, From the Yellow Notepad, General, Life Lessons, Software Engineering | Leave a comment

Sorting words

Previously, I’ve posted about using non-English characters in programming and the basics of character set encoding. It appears that I need to keep adding to this theme of internationalization and Unicode.

In particular, the issue of collation — how to sort characters — came up in my UNIX Tools class. I knew that the sort order of words and strings depend on the localization, or “locale,” settings your system uses; as does the decimal separator, currency symbol, and a raft of other settings. For example, here’s the sort order of some files on my Mac OSX system. (The export command sets an environment variable.)

jeff-mathers-computer:~/tmp jeff$ export LANG=de_DE

jeff-mathers-computer:~/tmp jeff$ echo *.txt
A.txt a1.txt passé.txt passe.txt strabismus.txt strasberg.txt
strasse.txt strategery.txt straße.txt تاببا.txt تبب.txt देवनगारि.txt

jeff-mathers-computer:~/tmp jeff$ export LANG=de_DE.ISO8859-1

jeff-mathers-computer:~/tmp jeff$ echo *.txt
A.txt تاببا.txt تبب.txt देवनगारि.txt a1.txt passe.txt passé.txt
straße.txt strabismus.txt strasberg.txt strasse.txt strategery.txt

jeff-mathers-computer:~/tmp jeff$ export LANG=de_DE.UTF-8     

jeff-mathers-computer:~/tmp jeff$ echo *.txt
A.txt a1.txt passé.txt passe.txt strabismus.txt strasberg.txt
strasse.txt strategery.txt straße.txt تاببا.txt تبب.txt देवनगारि.txt

The Mac finder lists the files in yet a different way: A.txt, a1.txt, passe.txt, passé.txt, strabismus.txt, strasberg.txt, strasse.txt, straße.txt, strategery.txt, تاببا.txt, تبب.txt, देवनगारि.txt. Your system may be different.

The appearance of the term “UTF-8” surprised me, because I only knew about it in the context of character encoding. But it turns out that UTF-8 (along with the other Unicode character encodings) also includes the Unicode Collation Algorithm, descriptions about how to combine different characters together into one visual character (that is, how to make ligatures), and even more.

A key thing to remember seems to be that there’s no single collation order for a given character set and that these collation orders depend partly on the language of the locale. That makes sense; how you sort accented letters varies from language to language.

Posted in Computing, Software Engineering | Leave a comment

The English in America



Last week, Lisa and I visited the Copps Hill Burying Ground near the Old North Church in Boston’s North End. I had walked by it a few times before but never gone in because it is sooo close to the end of the Freedom Trail, and our guests are usually ready for the long walk to be over. I had a tip (via the Internet) that some of my relatives are buried there, so we finally went in.

I will give you the full rundown of the cemetery itself soon, but you might be interested in my family’s particular connection to this country that was so new to many of the people buried in Copps Hill.

It starts with Richard Mather, the Puritan preacher of diminished means who came to Massachusetts Bay in 1635, fifteen years after the Mayflower arrived. The Puritans in America have their closest modern counterparts in the Ayatollahs of Iran, men who parlay religious authority into authoritarian political control. Richard’s son Increase Mather became one of the most influential men in New England. Increase’s son Cotton Mather carried on the family tradition, publishing prolifically on religious matters and is notoriously linked to the Salem witchcraft hysteria after giving expert testimony about how to identify “spectral evidence.” Increase is my tenth great-grand-uncle (once removed).

  1. John Mather of Lowton, Winwich Parish, Lancashire County, England
  2. Thomas Mather, Yeoman of Lowton
  3. Rev. Richard Mather (1596-1669) — He emigrated to Dorchester, Massachusetts in 1635
  4. Timothy Mather (1628-1684) — married Catherine Atherton. [1]
  5. Atherton Mather (1663-1734) — married Rebecca Stoughton. [2]
  6. William Mather (1698-1747)
  7. Timothy Mather (1722-1802)
  8. Timothy Mather (1757-1818) — married Hannah Church. [3]
  9. Timothy Mather (1785-1858) — married Harriet Adams. [4]
  10. John Adams Mather (1822-1875) — [5]
  11. James Sherman Mather (1852-1933) — married Emma Elizabeth Fanning. [6]
  12. Clarence Mather (1888-1975)
  13. Richard Mather (1915-1979?)
  14. Dennis Mather (1942- )
  15. Me (1974- )

[1] — Catherine Atherton was the daughter of Major General Humphry Atherton, who purchased land from the Narragansett Indians under false pretenses. The Major’s grandson Humphry Atherton, Jr., apparently owned some fellow human beings, as well. (According to the probate record, Atherton left “Mentions Cuffee, a Negro Man £300″ to his heirs.)

[2] — Rebecca Stoughton was the granddaughter of Hon. William Stoughton, the Lord High Witch-Presser in the Salem Witch Trials. There’s a Stoughton, Mass., too.

[3] — Hannah Church was the daughter of John Church and Jemima Montague of Hadley, Mass. So, it’s likely that I’m related to the family that gave Montague, Mass. its name.

[4] — Harriet Adams is a descendant of John Alden, a Mayflower passenger. Her parents came from Milton and Braintree, so it’s almost certain that I’m also related to two American presidents, though I’m still working on the link.

Update: If you go four generations up the family tree from President John Adams (or five from President John Quincey Adams) you will find Henry Adams and Edith Squire. Their seventh son, Joseph, begat the presidential family line. A descendant of Joseph’s younger brother, Henry, married into the Mather family in 1812. It’s a very distant link.

My link to the common ancestor…

  1. Henry Adams (1582/3 – 1646) m. Edith Squire (1587 – 1672/3)
  2. Edward Adams (1629 – 1716)
  3. John Adams (unknown)
  4. Edward Adams (1682/3 – 1743)
  5. John Adams, Dea. (1708/9 – 1790)
  6. Edward Adams (1738/39 – 1825) m. Dorothy Spear (1743/4 – 1802)
  7. Harriet Adams (1787 – 1828) m. Timothy Mather (1785 – 1858)

The presidents’ link to the common ancestor…

  1. Henry Adams (1582/3 – 1646) m. Edith Squire (1587 – 1672/3)
  2. Joseph Adams (1625/6 – 1694)
  3. Joseph Adams, Jr. (1654 – 1736/7)
  4. John Adams, Dea. (1690/1 – 1761)
  5. John Adams, President (1735 – 1826)
  6. John Q. Adams (1767 – 1848)

[5] — John Adams Mather was the guy who brought my family from New England to the Midwest. He first settled as a young man in western New York then moved his family to Wisconsin in 1857 and later to Minnesota.

[6] — Emma Fanning is a direct descendant of William Bradford, another Mayflower passenger and the second Colonial Governor of Massachusetts. I think we’re also related (indirectly) through her to the explorer Edmund Fanning.



(Click for larger image…)

Posted in Burying Grounds, This is who we are | 9 Comments

Death to bookmarks!

Del.icio.us icon I want to share my del.icio.us bookmarks with you. Some of my “statistically improbable” tags with many items include:

So what’s this all about?

Thirteen years ago when I was new to the web, I made bookmarks for every interesting web page that I came across. (Search was in its infancy.) After a while my bookmark list became too long, leading me to organize my Netscape bookmarks the only way available: a hierarchical tree of folders. I’m not sure it was ever any easier to find a bookmark in a big, “organized” tree of folders or a huge, unorganized list. The unreliability of computing solved this problem for me; every six to twelve months I would get a new computer or browser, and *poof* all of my bookmarks were gone. Fortunately, after living five years with this dilemma and death-cycle, someone told me about Google. But Google isn’t perfect, and I still like keeping a separate, personal, durable list of pages and PDF documents on the web that I might eventually go back to . . . a collection that’s already relevant to my needs.

Enter del.icio.us, a social bookmarking service with a geeky cute name. I no longer make browser bookmarks, though I still keep track of interesting and useful pages. And I no longer fit links into a hierarchy. Instead, when I go to an interesting page I push a little button on my browser and enter tags, which are essentially mnemonic keywords, many of which the service suggests via some computing mojo.

Later, when I’m interested in looking up that information about, say, the TIFF file format, I simply go to my del.icio.us page and click on the tiff tag, and I see all of the pages I previously tagged. In addition, del.icio.us also lets me look at all of the pages everyone has tagged “tiff”. Letting other people do hard work for me is great!

(I told a little white lie earlier. I actually do keep a handful of links within my browser’s bookmark bar, but I only keep track of sites that I use almost every week: intranet pages, movie showtimes at my local theatre, NOAA Conus weather forecasts, my Netflix queue, the admin page for this site, etc. The key is that I use them all the time.)

How about you? Do you use a social bookmarking service like del.icio.us, scuttle, or ma.gnolia? If so, what are your more unusual, high-content tags?

Posted in Computing, General, Life Lessons | Leave a comment

Smarter image resizing

A bunch of us around the office were talking about the cool content aware image resizing algorithm that we saw on Doug’s blog.

The idea behind Shai Avidan and Ariel Shamir‘s work is to find information-neutral “seams” in the image and fold or expand the image along those constantly shifting fault lines. Unlike traditional methods for resizing images, “important” areas don’t become smaller at the same rate as low information areas. As a result, things can move around a bit in the resized images. Take a look at the video above to see this in action, or read the paper for information about how it works.

A seam is a connected path of low energy pixels in an image. On the left is the original image with one horizontal and one vertical seam. In the middle the energy function used in this example is shown (the magnitude of the gradient), along with the vertical and horizontal path maps used to calculate the seams. By automatically carving out seams to reduce image size, and inserting seams to extend it, we achieve content-aware resizing. The example on the top right shows our result of extending in one dimension and reducing in the other, compared to standard scaling on the bottom right.

Personally, I think this is another step in our cultural evolution with respect to imagery. First we believed every photograph represented an actual event that was faithfully transcribed. Photography was an optical-mechanical process of transcription, according to its earliest practitioners (and detractors). Then mid-20th century we realized imagery could be manipulated in order to entertain, mislead, or manipulate us; but we still more or less believed that images were inherently truthful. After another half-century we’re still coming around to the fact that images are surfaces that we project our thoughts and feeling onto and, as a result, must be treated rather skeptically.

Image manipulation techniques such as this — which change image content in a way that moves around visual elements automatically while attempting to retain the information within a scene — may finally highlight some latent connections between our mind’s images and those that are recorded. We’re constantly evaluating the content of scenes and unconsciously throwing out most of the “uninteresting” information, transforming the world’s “truthiness” along the way. Recorded images have no more inherent truth than people’s faulty memories do.

Posted in Color and Vision, Fodder for Techno-weenies, Life Lessons, Photography | Leave a comment

Deconstructing an image

Friends, I’ve been wanting to tell you about this for a while, and now that the beta public version of MATLAB R2007b is out, I can finally post. This will be the first of a series of articles about high dynamic range imaging. Let’s start by looking at a picture:

This is my office. It’s a window office. I don’t say that out of pride, rather to highlight that there’s a bright, sunny world out there beyond the window. It’s comparatively dark inside. In fact, it’s so much brighter outside in this scene, that contemporary digital cameras and films can’t record the full “dynamic range” of the image. The outside would be overexposed or the interior would be underexposed. High dynamic range (HDR) imagery solves the problem.

I will write more about dynamic range later, but I want to get around to deconstructing the image’s content. For now I hope the following pair of images show how amazing high dynamic range imagery really is.

The description of these images gets a little technical, and you can safely skip this paragraph . . . or you can pick up some new highfalutin party lingo. The image on the left shows the relative luminance (i.e., brightness) of the scene. The darkest value is black; the brightest value is white; and everything in between is linearly scaled. As you can see, the wide range of luminance values hides most of the scene’s information. If we take the base-2 logarithm of the values, linearly map the result, and apply a false coloring (as shown in the right image) you can see that all of the detail is actually there in the HDR image. (Click on any of the images for a larger version.)

For this image, knowing the way that it’s constructed may help you understand some of the visual content of the image. Right now — in what will soon be the olden days — the easiest way to get the “best” exposure is to use a handheld lightmeter and then change the lighting throughout the scene to produce even illumination. You can see one of these soon-to-be-antiquated devices on the right-hand side of my desk right next to a wee cowboy and dinosaur facing off and a copy of what I was reading at the time. A tiny version of this device (minus dinosaur and cowboy) appears inside almost every camera.

Using a light meter and portable lighting can be very time consuming and a bit expensive. You need equipment. You need assistants to set up and move the equipment. You need time to set it all up, make the test images, adjust the light output, take the “best” shot, and tear it all down again. I predict that HDR technology will appear in consumer electronics devices in the next few years — it’s already in Adobe Photoshop — and, while professionals will still need lighting rigs and serfs assistants, the rest of us will get most of the benefits without extra equipment. Mark my words, the move from traditional imagery to HDR imaging is going to be (almost) as big as the shift from film to digital.

MATLAB and the Image Processing Toolbox are used by the engineers who will likely develop those fancy consumer devices for you. So I created this image as a sample that ships with the toolbox to help show what we can do. One day I brought in my sturdy tripod, and Alex Taylor (who went to a trade show in California with me last February) brought in his new Nikon digital camera. We took seventeen “normal” low dynamic range images at different exposure values, ran it through some software I wrote in MATLAB to merge the different exposure values into one “properly exposed” image, called a function in the Image Processing Toolbox to create a “tone mapped” image, and voilà.

The last time I did something like this was six years ago when I needed to make a new colorful image for the toolbox. Being a perfectionist (and a bit of an artiste) it took me forever to think of what I wanted to do. Then one morning I remembered Edward Weston’s sexy peppers, grabbed my tripod and an old bed sheet, and bought thirteen dollars worth of peppers at the Stop & Shop. A couple days later I went to San Diego for my first trade show, and my coworkers ate the peppers. (Déjà vu…) My inspiration appears on the left below, along with the image that still ships with the toolbox and appears in multiple product demos.

  

The first image I made for the toolbox appears in the new image. (That’s MATLAB in the background.) I also put an apple in the picture as an homage to the earlier picture and a reference to my absent Mac laptop.


Finally, there are a bunch of dinosaurs in the picture because everyone loves dinosaurs. Or at least, they should.

Posted in Color and Vision, Computing, Photography | 2 Comments

Finally a No-hitter

Clay Buchholz pitched a no-hitter tonight. It wasn’t perfect — he hit a batter and walked a few — but it was just his second major league baseball game. Ever. What a great game!

The game had so much drama and was wonderful to watch. Even Lisa was cheering for the kid, despite the Sox and Yankees being caught in a tight duel for the AL East lead and the playoffs.

And the Cubs are leading the NL Central, too! I’m hoping for a great post-season.

Posted in Baseball | 1 Comment