Coming to PhotoDemon 5.4: Language Support. Translators welcome!

Today I made an interesting discovery: my PhotoDemon release dates are slipping further and further apart.

  • PhotoDemon 4.3 – 10 August 2012
  • PhotoDemon 4.4 – 21 August 2012 (11 days later)
  • PhotoDemon 5.0 – 21 September 2012 (31 days later)
  • PhotoDemon 5.2 – 28 November 2012 (68 days later)
  • PhotoDemon 5.4 – …? (76 days and counting)

If I throw together a quick chart for the delay between releases, a clear trend emerges:

Not my favorite correlation...
Shame on me…

According to the chart, I still have a good for or five months available to work on the next release…

Actually, PhotoDemon 5.4 is rapidly nearing completion! My excuse for this latest delay is a good one, and I imagine you already inferred it from the title of the article… but in case you didn’t:

The next PhotoDemon release will include support for multiple languages, with French, German, and Dutch (Vlaams) officially supported at release.

Language support has been a monster to implement on account of the large amount of text in the project, not to mention classic VB’s utter lack of usable translation libraries. As a result, an entirely novel language engine was written from scratch, with (quite lovely) XML files being used to supply the actual translation data.

To give you an idea of the scope: as part of the translation process, I wrote a separate program whose sole purpose was to extract all necessary text from the PhotoDemon source code so that a “master” language file could be assembled. According to it, PhotoDemon contains almost 1400 unique phrases, with a total of more than 7800 words. Every one of those phrase occurrences needed code added to handle the actual text substitution, and then there’s the obvious challenge of the translation itself.

Fortunately, I didn’t tackle this project alone. An absolutely amazing contributor by the name of Frank Donckers contacted me with the initial prototype of the translation engine, and it is Frank who is supplying the French, German, and Dutch translation text. I could not have built this feature without him – so thank you, Frank!

At present, the translation engine is pretty much complete in terms of base functionality – all program text is translated on the fly, and the user is free to change languages at run-time at their leisure (no restart required!). The coding solution behind this is quite elegant, if I might say so, and users shouldn’t experience any noticeable performance hit while a translation is active. The only noticeable delay might be an additional second or two of start-up time on older machines, on account of the translation XML file being loaded and parsed. I’ve got some ideas for speeding up this process, however, so even that delay may disappear by release time.

I would love to include official support for additional languages. If you are fluent in a language other than English, please consider contributing a new translation!

No programming experience or specialized software is required to translate. I’ve got a master translation file ready to go – all that’s needed is to plug in the translated text in whatever language you might speak.

Here is how the French language file looks.  All a translator needs to do is place a translation between the translation XML tags - easy peasy!
Here is how the French language file looks in the free Notepad++ editor. All a translator needs to do is place a translation between the translation XML tags – easy peasy!

If you’re familiar with XML or HTML, you can see how simple the translation document is. Each phrase consists of original text and translated text, and that’s all there is to it. The lines in green are just comments added for convenience, in this case comments written by the language extraction tool. Translators can safely ignore these.

Before wrapping up, I should mention one rather large caveat with multiple language support – at present, only “ANSI” (Windows-1252) languages are supported. I apologize for this, but one of the problems with classic VB is its inability to handle unicode characters without major hacking – and by major hacking, I mean replacing every user interface aspect of the project, as well as every string library. If I ever port PhotoDemon to another programming language (something I often consider), Unicode support would be much more feasible, but I’m afraid it’s not on the present roadmap.

I need at least a couple more weeks to hammer out a few remaining issues with version 5.4, which leaves plenty of time for any ambitious translators out there to pitch in and contribute a new translation before release day. If it helps, note that your name will be visibly displayed as the translator in not only the language source file, but I’ll also add you to the special thanks section of the program, the PhotoDemon website, and the README file.

I can always be reached via this contact form – so that’s the place to go if you’re willing to help. Thank you in advance!

A simple algorithm for correcting lens distortion

One of the new features in the development branch of my open-source photo editor is a simple tool for correcting lens distortion. I thought I’d share the algorithm I use, in case others find it useful. (There are very few useful examples of lens correction on the Internet – most articles simply refer to existing software packages, rather than explaining how the software works.)

Lens distortion is a complex beast, and a lot of approaches have been developed to deal with it. Some professional software packages address the problem by providing a comprehensive list of cameras and lenses – then the user just picks their equipment from the list, and the software applies a correction algorithm using a table of hard-coded values. This approach requires way more resources than a small developer like myself could handle, so I chose a simpler solution: a universal algorithm that allows the user to apply their own correction, with two tunable parameters for controlling the strength of the correction.

This is what PhotoDemon's new lens correction tool looks like.
PhotoDemon’s new lens correction tool in action.

The key part of the algorithm is less than ten lines of code, so there’s not much work involved. The effect is also fast enough to preview in real-time.

Before sharing the algorithm, let me demonstrate its output. Here is a sample photo that suffers from typical spherical distortion:

This lovely demonstration photo comes from Wikipedia, courtesy of Ashley Pomeroy
This lovely demonstration photo comes from Wikipedia, courtesy of Ashley Pomeroy

Pay special attention to the lines on the floor and the glass panels on the right.

Here’s the same image, as corrected by the algorithm in this article:

Note the straight lines on both the floor and the glass panels on the right.  Not bad, eh?
Note the straight lines on both the floor and the glass panels on the right. Not bad, eh?

My use of simple bilinear resampling blurs the output slightly; a more sophisticated resampling technique would produce clearer results.

A key feature of the algorithm is that it works at any aspect ratio – rectangular images, like the one above, are handled just fine, as are perfectly square images.

Anyway, here is the required code, as pseudocode:


input:
    strength as floating point >= 0.  0 = no change, high numbers equal stronger correction.
    zoom as floating point >= 1.  (1 = no change in zoom)

algorithm:

    set halfWidth = imageWidth / 2
    set halfHeight = imageHeight / 2
    
    if strength = 0 then strength = 0.00001
    set correctionRadius = squareroot(imageWidth ^ 2 + imageHeight ^ 2) / strength

    for each pixel (x,y) in destinationImage
        set newX = x - halfWidth
        set newY = y - halfHeight

        set distance = squareroot(newX ^ 2 + newY ^ 2)
        set r = distance / correctionRadius
        
        if r = 0 then
            set theta = 1
        else
            set theta = arctangent(r) / r

        set sourceX = halfWidth + theta * newX * zoom
        set sourceY = halfHeight + theta * newY * zoom

        set color of pixel (x, y) to color of source image pixel at (sourceX, sourceY)

That’s all there is to it. Note that you’ll need to do some bounds checking, as sourceX and sourceY may lie outside the bounds of the original image. Note also that sourceX and sourceY will be floating-point values – so for best results, you’ll want to interpolate the color used instead of just clamping sourceX and sourceY to integer values.

I should mention that the algorithm works just fine without the zoom parameter. I added the zoom parameter after some experimentation; specifically, I find zoom useful in two ways:

  • On images with only minor lens distortion, zooming out reduces stretching artifacts at the edges of the corrected image
  • On images with severe distortion, such as true fish-eye photos, zooming-out retains more of the source material

As there is not a universally “correct” solution to these two scenarios, I recommend providing zoom as a tunable parameter. To give a specific example of the second circumstance, consider this fish-eye photo from Wikipedia, courtesy of Josef F. Stuefer:

Severe distortion like this is difficult to correct completely.
Severe distortion like this is difficult to fully correct.

If we attempt to correct the image without applying any zoom, the image must be stretched so far that much of the edges are lost completely:

This is hardly the same photo.  Note also the visible stretching at the edges.
This is hardly the same photo. The pier at the bottom has been completely erased!

By utilizing a zoom parameter, it is possible to include more of the image in the finished result:

Much more of the photo can be preserved by adding a simple zoom parameter to the algorithm.
Use of a zoom parameter allows us to preserve much more of the photo. When correcting severe distortion like this, you might want to apply a sharpening algorithm to the final image. (This sample image has no sharpening applied.)

Again, I only use a simple resampling technique; a more sophisticated one would produce clearer results at the edges.

If you’d like to see my actual source code, check out this GitHub link. The fun begins at line 194. I also include an optional radius parameter, which allows the user to correct only a subset of the image (rather than the entire thing), but other than that the code is identical to what you see above.

Enjoy!

P.S. For a great discussion of fish-eye distortion from a pro photographer’s perspective, check out http://photo.net/learn/fisheye/

Hooking modern Windows common dialogs: some notes

Background: common dialog hooking is used to append your own controls to a Windows common dialog box.

A good friend recently sent me a number of resources related to hooking common dialog controls. I’ve been interested in common dialog hooking for PhotoDemon, as it would allow me to add support for image previewing right in the dialog itself. This isn’t as necessary in modern versions of Windows (7 in particular includes a number of GDI+ improvements, making Explorer very robust with standard formats), but it can be helpful for unsupported formats like RAW photographs.

Unfortunately, several days of research have shown that it is not possible to hook a Vista or Windows 7 style dialog and maintain the modern layout. Let me explain with pictures:

This is the standard common dialog control in Windows Vista and 7 (and presumably 8 as well, though I haven't verified this myself).  The biggest improvements over past common dialogs include breadcrumb navigation at the top, a dedicated refresh button, and a persistent search bar.
This is the standard common dialog control in Windows Vista and 7 (and presumably 8 as well, though I haven’t verified this myself). The biggest improvements over past common dialogs include a dedicated left-hand file tree, breadcrumb navigation at the top, and a persistent search bar.

The common dialog above comes directly from PhotoDemon’s current common dialog implementation. This is the native common dialog control on Vista and 7. I very much like it. As a comparison, here is the same dialog in Windows XP:

Same folder as the previous image.  The XP common dialog provides no breadcrumb nav, folder tree, dedicated refresh, or search bar.  Note also how many TIFF formats do not display correctly - including XP not recognizing the MINISWHITE flag on the CCITT TIFF files.  Kinda interesting.
Same folder and images as the previous image. There is no breadcrumb nav, dedicated refresh, or search bar. Note also how many TIFF formats do not display correctly – including XP not recognizing the MINISWHITE flag on the CCITT TIFF files. Kinda interesting.

I strongly prefer the Vista/7-style dialog, particularly the breadcrumb nav and the persistent folder tree on the left.

Unfortunately, it is impossible to hook the Vista/7 dialog and maintain the native Vista/7 appearance. If you attempt to hook it, Windows will ALWAYS drop back to a previous generation common dialog. Here are some images to demonstrate, using a basic image preview hook:

This is what happens when you attempt to hook a dialog, and all you provide is the OFN_ENABLEHOOK flag.  Not pretty (and the hook doesn't even work right).
This is what happens when you attempt to hook a dialog, and all you provide is the OFN_ENABLEHOOK flag. Not pretty (and the hook doesn’t even work correctly).
Here is the same dialog, but with the OFN_EXPLORER flag set.  Note that hooking now works properly, but the common dialog itself has been reduced to XP style - the left-hand folder tree is gone, and the top bar has no breadcrumbs or search.
Here is the same dialog, but with the OFN_EXPLORER flag set. Note that hooking now works properly, but the common dialog itself has been reduced to XP style – the left-hand folder tree is gone, and the top bar has no breadcrumbs or search.

Note that the image above uses an older version of the OPENFILENAME struct, namely (this is its declaration in VB):

Private Type OPENFILENAME
    lStructSize       As Long
    hwndOwner         As Long
    hInstance         As Long
    lpstrFilter       As String
    lpstrCustomFilter As String
    nMaxCustFilter    As Long
    nFilterIndex      As Long
    lpstrFile         As String
    nMaxFile          As Long
    lpstrFileTitle    As String
    nMaxFileTitle     As Long
    lpstrInitialDir   As String
    lpstrTitle        As String
    Flags             As Long
    nFileOffset       As Integer
    nFileExtension    As Integer
    lpstrDefExt       As String
    lCustData         As Long
    lpfnHook          As Long
    lpTemplateName    As String
End Type

If you modify the struct to its newest version (as described here), you can slightly improve the dialog to look like this:

The newest version of the OPENFILENAME struct enables the places bar on the left.  I don't find this particularly useful - certainly not as useful as a folder pane - but perhaps some might find it preferable.
The newest version of the OPENFILENAME struct enables the places bar on the left. I don’t find this particularly useful – certainly not as useful as a folder pane – but perhaps some might find it preferable.

That is the best you can get if you want to hook a common dialog in Vista or 7.

Reasons for this have been speculated on by more qualified individuals than I. Over at stackoverflow, David H explains:

The reason for this is that MS completely re-organised the file dialogs for Vista. Hooks are used to extend a file dialog by supplying a resource file. This gives the customiser too much power. They can all too easily modify standard elements of the dialog and indeed many apps did so. The reorganisation of the dialogs would have broken many apps that used hooks. Those would have tried to manipulate elements of the dialog that were not there, or were implemented differently. Legacy versions of the dialogs remain for such apps to “get their hooks into”.

You are correct that it is impossible to get the new look when you use a hook. Instead you need to use the IFileDialogCustomize interface to customise the dialog. This is less powerful but does result in appearance and behaviour that is more consistent with the standard part of the dialog.

(More information is available here for those who are interested.)

Unfortunately, I am not aware of any way to access the iFileDialogCustomize interface in classic VB. If someone knows how, I’d love to hear it.

The take home message of all this is – if you work in classic VB and you want to hook a common dialog, you need to be content with an XP-style dialog. There is currently no way to maintain a Vista/7 style dialog while hooking.

For this reason, I’m going to stick with the stock common dialog control in PhotoDemon. I may look at a dedicated “browse” window in the future, which would allow for full image previewing, but I’m afraid such a feature is not on the roadmap for the next few versions.

All hooking-related screenshots were created using Carles PV’s iBMP project, which made it very easy to modify various hooking parameters and test the output. Thanks, Carles!

Image Dithering: Eleven Algorithms and Source Code

Dithering: An Overview

Today’s graphics programming topic – dithering – is one I receive a lot of emails about, which some may find surprising. You might think that dithering is something programmers shouldn’t have to deal with in 2012. Doesn’t dithering belong in the annals of technology history, a relic of times when “16 million color displays” were something programmers and users could only dream of? In an age when cheap mobile phones operate in full 32bpp glory, why am I writing an article about dithering?

Actually, dithering is still a surprisingly applicable technique, not just for practical reasons (such as preparing a full-color image for output on a non-color printer), but for artistic reasons as well. Dithering also has applications in web design, where it is a useful technique for reducing images with high color counts to lower color counts, reducing file size (and bandwidth) without harming quality. It also has uses when reducing 48 or 64bpp RAW-format digital photos to 24bpp RGB for editing.

And these are just image dithering uses – dithering still has extremely crucial roles to play in audio, but I’m afraid I won’t be discussing audio dithering here. Just image dithering.

In this article, I’m going to focus on three things:

  • a basic discussion of how image dithering works
  • eleven specific two-dimensional dithering formulas, including famous ones like “Floyd-Steinberg”
  • how to write a general-purpose dithering engine

Update 11 June 2016: some of the sample images in this article have been updated to better reflect the various dithering algorithms. Thank you to commenters who noted problems with the previous images!

Dithering: Some Examples

Consider the following full-color image, a wallpaper of the famous “companion cube” from Portal:

This will be our demonstration image for this article.  I chose it because it has a nice mixture of soft gradients and hard edges.
This will be our demonstration image for this article. I chose it because it has a nice mixture of soft gradients and hard edges.

On a modern LCD or LED screen – be it your computer monitor, smartphone, or TV – this full-color image can be displayed without any problems. But consider an older PC, one that only supports a limited palette. If we attempt to display the image on such a PC, it might look something like this:

This is the same image as above, but restricted to a websafe palette.
This is the same image as above, but restricted to a websafe palette.

Pretty nasty, isn’t it? Consider an even more dramatic example, where we want to print the cube image on a black-and-white printer. Then we’re left with something like this:

At this point, the image is barely recognizable.
At this point, the image is barely recognizable.

Problems arise any time an image is displayed on a device that supports less colors than the image contains. Subtle gradients in the original image may be replaced with blobs of uniform color, and depending on the restrictions of the device, the original image may become unrecognizable.

Dithering is an attempt to solve this problem. Dithering works by approximating unavailable colors with available colors, by mixing and matching available colors in a way that mimicks unavailable ones. As an example, here is the cube image once again reduced to the colors of a theoretical old PC – only this time, dithering has been applied:

A big improvement over the non-dithered version!
A big improvement over the non-dithered version!

If you look closely, you can see that this image uses the same colors as its non-dithered counterpart – but those few colors are arranged in a way that makes it seem like many more colors are present.

As another example, here is a black-and-white version of the image with similar dithering applied:

The specific algorithm used on this image is "2-row Sierra" dithering.
The specific algorithm used on this image is “2-row Sierra” dithering.

Despite only black and white being used, we can still make out the shape of the cube, right down to the hearts on either side. Dithering is an extremely powerful technique, and it can be used in ANY situation where data has to be represented at a lower resolution than it was originally created for. This article will focus specifically on images, but the same techniques can be applied to any 2-dimensional data (or 1-dimensional data, which is even simpler!).

The Basic Concept Behind Dithering

Boiled down to its simplest form, dithering is fundamentally about error diffusion.

Error diffusion works as follows: let’s pretend to reduce a grayscale photograph to black and white, so we can print it on a printer that only supports pure black (ink) or pure white (no ink). The first pixel in the image is dark gray, with a value of 96 on a scale from 0 to 255, with zero being pure black and 255 being pure white.

Here is an example of the RGB values in the example.
Here is a visualization of the RGB values in our example.

When converting such a pixel to black or white, we use a simple formula – is the color value closer to 0 (black) or 255 (white)? 96 is closer to 0 than to 255, so we make the pixel black.

At this point, a standard approach would simply move to the next pixel and perform the same comparison. But a problem arises if we have a bunch of “96 gray” pixels – they all get turned to black, and we’re left with a huge chunk of empty black pixels, which doesn’t represent the original gray color very well at all.

Error diffusion takes a smarter approach to the problem. As you might have inferred, error diffusion works by “diffusing” – or spreading – the error of each calculation to neighboring pixels. If it finds a pixel of 96 gray, it too determines that 96 is closer to 0 than to 255 – and so it makes the pixel black. But then the algorithm makes note of the “error” in its conversion – specifically, that the gray pixel we have forced to black was actually 96 steps away from black.

When it moves to the next pixel, the error diffusion algorithm adds the error of the previous pixel to the current pixel. If the next pixel is also 96 gray, instead of simply forcing that to black as well, the algorithm adds the error of 96 from the previous pixel. This results in a value of 192, which is actually closer to 255 – and thus closer to white! So it makes this particular pixel white, and it again makes note of the error – in this case, the error is -63, because 192 is 63 less than 255, which is the value this pixel was forced to.

As the algorithm proceeds, the “diffused error” results in an alternating pattern of black and white pixels, which does a pretty good job of mimicking the “96 gray” of the section – much better just forcing the color to black over and over again. Typically, when we finish processing a line of the image, we discard the error value we’ve been tracking and start over again at an error of “0” with the next line of the image.

Here is an example of the cube image from above with this exact algorithm applied – specifically, each pixel is converted to black or white, the error of the conversion is noted, and it is passed to the next pixel on the right:

This is the simplest possible application of error diffusion dithering.
This is the simplest possible application of error diffusion dithering.

Unfortunately, error diffusion dithering has problems of its own. For better or worse, dithering always leads to a spotted or stippled appearance. This is an inevitable side-effect of working with a small number of available colors – those colors are going to be repeated over and over again, because there are only so many of them.

In the simple error diffusion example above, another problem is evident – if you have a block of very similar colors, and you only push the error to the right, all the “dots” end up in the same place! This leads to funny lines of dots, which is nearly as distracting as the original, non-dithered version.

The problem is that we’re only using a one-dimensional error diffusion. By only pushing the error in one direction (right), we don’t distribute it very well. Since an image has two dimensions – horizontal and vertical – why not push the error in multiple directions? This will spread it out more evenly, which in turn will avoid the funny “lines of speckles” seen in the error diffusion example above.

Two-Dimensional Error Diffusion Dithering

There are many ways to diffuse an error in two dimensions. For example, we can spread the error to one or more pixels on the right, one or more pixels on the left, one or more pixels up, and one or more pixels down.

For simplicity of computation, all standard dithering formulas push the error forward, never backward. If you loop through an image one pixel at a time, starting at the top-left and moving right, you never want to push errors backward (e.g. left and/or up). The reason for this is obvious – if you push the error backward, you have to revisit pixels you’ve already processed, which leads to more errors being pushed backward, and you end up with an infinite cycle of error diffusion.

So for standard loop behavior (starting at the top-left of the image and moving right), we only want to push pixels right and down.

Apologies for the crappy image - but I hope it helps illustrate the gist of proper error diffusion.
Apologies for the crappy image – but I hope it helps illustrate the gist of proper error diffusion.

As for how specifically to propagate the error, a great number of individuals smarter than I have tackled this problem head-on. Let me share their formulas with you.

(Note: these dithering formulas are available multiple places online, but the best, most comprehensive reference I have found is this one.)

Floyd-Steinberg Dithering

The first – and arguably most famous – 2D error diffusion formula was published by Robert Floyd and Louis Steinberg in 1976. It diffuses errors in the following pattern:


       X   7
   3   5   1

     (1/16)

In the notation above, “X” refers to the current pixel. The fraction at the bottom represents the divisor for the error. Said another way, the Floyd-Steinberg formula could be written as:


           X    7/16
   3/16  5/16   1/16

But that notation is long and messy, so I’ll stick with the original.

To use our original example of converting a pixel of value “96” to 0 (black) or 255 (white), if we force the pixel to black, the resulting error is 96. We then propagate that error to the surrounding pixels by dividing 96 by 16 ( = 6), then multiplying it by the appropriate values, e.g.:


           X     +42
   +18    +30    +6

By spreading the error to multiple pixels, each with a different value, we minimize any distracting bands of speckles like the original error diffusion example. Here is the cube image with Floyd-Steinberg dithering applied:

Floyd-Steinberg dithering
Floyd-Steinberg dithering

Not bad, eh?

Floyd-Steinberg dithering is easily the most well-known error diffusion algorithm. It provides reasonably good quality, while only requiring a single forward array (a one-dimensional array the width of the image, which stores the error values pushed to the next row). Additionally, because its divisor is 16, bit-shifting can be used in place of division – making it quite fast, even on old hardware.

As for the 1/3/5/7 values used to distribute the error – those were chosen specifically because they create an even checkerboard pattern for perfectly gray images. Clever!

One warning regarding “Floyd-Steinberg” dithering – some software may use other, simpler dithering formulas and call them “Floyd-Steinberg”, hoping people won’t know the difference. This excellent dithering article describes one such “False Floyd-Steinberg” algorithm:


   X   3
   3   2

   (1/8)

This simplification of the original Floyd-Steinberg algorithm not only produces markedly worse output – but it does so without any conceivable advantage in terms of speed (or memory, as a forward-array to store error values for the next line is still required).

But if you’re curious, here’s the cube image after a “False Floyd-Steinberg” application:

Much more speckling than the legit Floyd-Steinberg algorithm - so don't use this formula!
Much more speckling than the legit Floyd-Steinberg algorithm – so don’t use this formula!

Jarvis, Judice, and Ninke Dithering

In the same year that Floyd and Steinberg published their famous dithering algorithm, a lesser-known – but much more powerful – algorithm was also published. The Jarvis, Judice, and Ninke filter is significantly more complex than Floyd-Steinberg:


             X   7   5 
     3   5   7   5   3
     1   3   5   3   1

           (1/48)

With this algorithm, the error is distributed to three times as many pixels as in Floyd-Steinberg, leading to much smoother – and more subtle – output. Unfortunately, the divisor of 48 is not a power of two, so bit-shifting can no longer be used – but only values of 1/48, 3/48, 5/48, and 7/48 are used, so these values can each be calculated but once, then propagated multiple times for a small speed gain.

Another downside of the JJN filter is that it pushes the error down not just one row, but two rows. This means we have to keep two forward arrays – one for the next row, and another for the row after that. This was a problem at the time the algorithm was first published, but on modern PCs or smartphones this extra requirement makes no difference. Frankly, you may be better off using a single error array the size of the image, rather than erasing the two single-row arrays over and over again.

Jarvis, Judice, Ninke dithering
Jarvis, Judice, Ninke dithering

Stucki Dithering

Five years after Jarvis, Judice, and Ninke published their dithering formula, Peter Stucki published an adjusted version of it, with slight changes made to improve processing time:


             X   8   4 
     2   4   8   4   2
     1   2   4   2   1

           (1/42)

The divisor of 42 is still not a power of two, but all the error propagation values are – so once the error is divided by 42, bit-shifting can be used to derive the specific values to propagate.

For most images, there will be minimal difference between the output of Stucki and JJN algorithms, so Stucki is often used because of its slight speed increase.

Stucki dithering
Stucki dithering

Atkinson Dithering

During the mid-1980’s, dithering became increasingly popular as computer hardware advanced to support more powerful video drivers and displays. One of the best dithering algorithms from this era was developed by Bill Atkinson, a Apple employee who worked on everything from MacPaint (which he wrote from scratch for the original Macintosh) to HyperCard and QuickDraw.

Atkinson’s formula is a bit different from others in this list, because it only propagates a fraction of the error instead of the full amount. This technique is sometimes offered by modern graphics applications as a “reduced color bleed” option. By only propagating part of the error, speckling is reduced, but contiguous dark or bright sections of an image may become washed out.


         X   1   1 
     1   1   1
         1

       (1/8)

Atkinson dithering
Atkinson dithering

Burkes Dithering

Seven years after Stucki published his improvement to Jarvis, Judice, Ninke dithering, Daniel Burkes suggested a further improvement:


             X   8   4 
     2   4   8   4   2

           (1/32)

Burkes’s suggestion was to drop the bottom row of Stucki’s matrix. Not only did this remove the need for two forward arrays, but it also resulted in a divisor that was once again a multiple of 2. This change meant that all math involved in the error calculation could be accomplished by simple bit-shifting, with only a minor hit to quality.

Burkes dithering
Burkes dithering

Sierra Dithering

The final three dithering algorithms come from Frankie Sierra, who published the following matrices in 1989 and 1990:


             X   5   3
     2   4   5   4   2
         2   3   2
           (1/32)


             X   4   3
     1   2   3   2   1
           (1/16)


         X   2
     1   1
       (1/4)

These three filters are commonly referred to as “Sierra”, “Two-Row Sierra”, and “Sierra Lite”. Their output on the sample cube image is as follows:

Sierra (sometimes called Sierra-3)
Sierra (sometimes called Sierra-3)
Two-row Sierra
Two-row Sierra
Sierra Lite
Sierra Lite

Other dithering considerations

If you compare the images above to the dithering results of another program, you may find slight differences. This is to be expected. There are a surprising number of variables that can affect the precise output of a dithering algorithm, including:

  • Integer or floating point tracking of errors. Integer-only methods lose some resolution due to quantization errors.
  • Color bleed reduction. Some software reduces the error by a set value – maybe 50% or 75% – to reduce the amount of “bleed” to neighboring pixels.
  • The threshold cut-off for black or white. 127 or 128 are common, but on some images it may be helpful to use other values.
  • For color images, how luminance is calculated can make a big difference. I use the HSL luminance formula ( [max(R,G,B) + min(R,G,B)] / 2). Others use ([r+g+b] / 3) or one of the ITU formulas. YUV or CIELAB will offer even better results.
  • Gamma correction or other pre-processing modifications. It is often beneficial to normalize an image before converting it to black and white, and whichever technique you use for this will obviously affect the output.
  • Loop direction. I’ve discussed a standard “left-to-right, top-to-bottom” approach, but some clever dithering algorithms will follow a serpentine path, where left-to-right directionality is reversed each line. This can reduce spots of uniform speckling and give a more varied appearance, but it’s more complicated to implement.

For the demonstration images in this article, I have not performed any pre-processing to the original image. All color matching is done in the RGB space with a cut-off of 127 (values <= 127 are set to 0). Loop direction is standard left-to-right, top-to-bottom.

Which specific techniques you may want to use will vary according to your programming language, processing constraints, and desired output.

I count 9 algorithms, but you promised 11! Where are the other two?

So far I’ve focused purely on error-diffusion dithering, because it offers better results than static, non-diffusion dithering.

But for sake of completeness, here are demonstrations of two standard “ordered dither” techniques. Ordered dithering leads to far more speckling (and worse results) than error-diffusion dithering, but they require no forward arrays and are very fast to apply. For more information on ordered dithering, check out the relevant Wikipedia article.

Ordered dither using a 4x4 Bayer matrix
Ordered dither using a 4×4 Bayer matrix
Ordered dither using an 8x8 Bayer matrix
Ordered dither using an 8×8 Bayer matrix

With these, the article has now covered a total of 11 different dithering algorithms.

Writing your own general-purpose dithering algorithm

Earlier this year, I wrote a fully functional, general-purpose dithering engine for PhotoDemon (an open-source photo editor). Rather than post the entirety of the code here, let me refer you to the relevant page on GitHub. The black and white conversion engine starts at line 350. If you have any questions about the code – which covers all the algorithms described on this page – please let me know and I’ll post additional explanations.

That engine works by allowing you to specify any dithering matrix in advance, just like the ones on this page. Then you hand that matrix over to the dithering engine and it takes care of the rest.

The engine is designed around monochrome conversion, but it could easily be modified to work on color palettes as well. The biggest difference with a color palette is that you must track separate errors for red, green, and blue, rather than a single luminance error. Otherwise, all the math is identical.

 

This site - and its many free downloads - are 100% funded by donations. Please consider a small contribution to fund server costs and to help me support my family. Even $1.00 helps. Thank you!

Announcing PhotoDemon 5.2 – Selections, HSL, Rotation, HDR, and More

Summary

PhotoDemon v5.2 is now available. New features include selection tools, arbitrary rotation, HSL adjustments, CMYK support, new user preferences, multiple monitor support, and more. Download the update here.

PhotoDemon 5.2
Version 5.2 includes many new tools and features, including PhotoDemon’s first on-canvas tool – “Selections”.

New Feature: Selection Tool

Selections have been one of the top-requested PhotoDemon features since it first released, so I’m glad to finally be able to offer them. A lot of work went into making selections as user-friendly and powerful as possible.

Three render modes are provided. On-canvas resizing and moving are fully supported, as are adjustments by textbox (see screenshot above). Everything in the Color and Filter menus will operate on a selection if available, as well as the Edit -> Copy command.

(Note: as of this v5.2, selections are not yet tied into Undo/Redo, and selections will not be recorded as part of a Macro. These features will be added in the next release.)

New Feature: Crop to Selection

Finally!

New Feature: HSL Adjustments

PhotoShop and GIMP users should be happy about this tool.

New Feature: Arbitrary (Free) Rotation

Arbitrary rotation comes courtesy of the FreeImage library. A 3-shear method is used: very fast, very high quality.

New Feature: CMY/K Rechanneling

Both CMY and CMYK rechanneling are now available.

New Feature: Sepia (W3C formula)

Here’s the sepia version of the photo from the Rechannel screenshot. I still prefer PhotoDemon’s “Antique” filter for most photos, but this sepia formula (from the W3C spec) provides a pleasant, flat alternative.

New Feature: Preferences Dialog (rewritten from scratch)

Preferences, preferences, and more preferences. The old Preferences dialog was pretty lame, so it was due for an overhaul. Tons of new settings have been added, and they are now organized by category.

New preferences include:

Interface:

  • Render drop shadows between images and canvas (similar to Paint.NET)
  • Full or compact file paths for image windows and Recent File shortcuts
  • Improved font rendering on Vista, Windows 7, and Windows 8 (via Segoe UI)
  • Remember the main window’s location between sessions

Loading and Saving:

  • Tone map imported HDR and RAW images
  • Options for importing all frames or pages of multi-image files (animated GIFs, multipage TIFFs)

Tools:

  • Automatically clear selections after “Crop to Selection” is used

Transparency handling:

  • Pick your own transparency checkerboard colors
  • Pick from three transparency checkerboard sizes (4×4, 8×8, 16×16)
  • Allow PhotoDemon to automatically remove empty alpha channels from imported images

All preferences from v5.0 remain present, and there is now an option to reset all preferences to their default state – so experiment away!

New Feature: Recent File Previews (Vista, Windows 7, Windows 8 only)

Now that recent file previews are available, I honestly can’t use any software that *doesn’t* provide the feature. It makes locating the right file significantly easier – especially with digital camera filenames like IMG_0366.jpg.

New Feature: Multi-Image File Support (animated GIFs, multipage TIFFs)

PhotoDemon will now recognize when you try to load image files that are actually composed of multiple images. You are given the option to import every image, or just the first one (which is what most other software does). The default behavior can be changed in the Edit -> Preferences menu.

New Feature: Waaaay better transparency handling, including adding/removing alpha channels

It’s hard to overstate how much better transparency support is in v5.2 compared to v5.0. Images with alpha-channels are now rendered as alpha in all viewport, filter, and tool screens. When printing, saving as 24bpp, or copying to the clipboard, transparent images are automatically composited against a white background. As mentioned previously, user preferences have been added for transparency checkerboard color and sizes.

PhotoDemon also allows you to add or remove alpha channels entirely. Here’s an example of an image with an alpha channel, and the associated “Image Mode” setting:

Note how the top-level “Mode” icon has changed to match the current mode – this saves you from having to go to the sub-menu to check. I’m a big fan of small touches like this.

And here it is again, after clicking the “Mode -> Photo (RGB | 24bpp | no transparency)” option:

No more alpha!

Finally, PhotoDemon now validates all incoming alpha channels. If an image has a blank or irrelevant alpha channel, PhotoDemon will automatically remove it for you. This frees up RAM, improves performance, and leads to a much smaller file size upon saving. (Note: this feature can be disabled from the Edit -> Preferences menu if you want to maintain blank alpha channels for some reason.)

New Feature: Custom “Confirm Unsaved Image(s)” Prompt

This is the new “unsaved images” prompt in PhotoDemon. A preview is now provided – again, very important for digital photos with obscure names – and the options have been reworked to make them as crystal-clear as possible. Also handy is the “Repeat this action for all unsaved images” option, which will either save or not save all unsaved images per your request.

Improved Feature: Edge Detection

Edge detection now allows for on-black or on-white processing. Generally speaking, on-white is used for artistic purposes, while on-black is used for technical and research ones. (Thanks to Yvonne Strahovski, who appears in the sample image above.)

New Feature: Thermograph Filter

This Wikipedia article describes thermography in great detail. PhotoDemon’s thermography filter works by correlating luminance with heat, and analyzing the image accordingly. Here’s a sample, using a picture of the lovely Alison Brie, of Mad Men and Community fame:

New Feature: JPEG 2000 (JP2/J2K), Industrial Light and Magic (EXR), High-Dynamic Range (HDR) and Digital Fax (G3) image support

PhotoDemon now supports importing the four image types mentioned above, and it also supports JPEG 2000 exporting.

Other New and Improved Features:

  • Much faster resize operations, thanks to an updated FreeImage library (v3.15.4)
  • Multiple monitor support during screen captures (File -> Import -> Screen Capture)
  • Many miscellaneous interface improvements, including generally larger command buttons, text boxes, labels, and more uniform form layouts.
  • Many new and improved menu icons.
  • Heavily optimized viewport rendering. PhotoDemon now uses a triple-buffer rendering pipeline to speed up actions like zooming, scrolling, and using on-canvas tools like the new Selection Tool. Even when working with 32bpp images, all actions render in real-time.
  • Bilinear interpolation is now used during Isometric Conversion. This results in a much higher-quality transform. Hard edges are still left along the image border to make mask generation easy for game designers.
  • Vastly improved image previewing when importing from VB binary files.
  • Better text validation throughout the software. Invalid values are now handled much more elegantly.
  • More accelerator hotkey support, including changes to match Windows standards (such as Ctrl+Y for Redo, instead of the previous Ctrl+Alt+Z).
  • Update checks are now performed every ten days (instead of every time the program is run).
  • All extra program data – including plugins, preferences, saved filters and macros – have been moved to a single /Data subfolder. If you run PhotoDemon on your desktop, this should make things much cleaner for you.
  • PhotoDemon’s current and max memory usage is now displayed in the Preferences -> Advanced panel.
  • Tons of miscellaneous bug fixes, tweaks, and optimizations. For a full list of changes, visit https://github.com/tannerhelland/PhotoDemon/commits/master

In Conclusion…

Not bad for two months work, eh? I hope you enjoy all the new features in 5.2., and please remember to donate if you find the software useful!

Announcing PhotoDemon 5.2 Beta 1 – Testers Needed!

PhotoDemon 5.2 beta 1 screenshot
It’s time for another PhotoDemon update. This update includes many new tools, including PhotoDemon’s first on-canvas tool – “Selections”.
  1. Summary
  2. Download
  3. List of what’s new and improved

Summary

PhotoDemon 5.2 is nearing completion, and I need help testing it. Version 5.2 provides a bunch of new features, including selections, cropping, HSL adjustment, CMY/CMYK rechanneling, a new Sepia filter (based off the W3C standard), an overhauled preferences engine and interface, and more. Please download the beta and help me make sure everything is working properly.

Download

The PhotoDemon 5.2 beta comes in two flavors:

Remember – if you are an advanced user, you can always download the most recent development build of PhotoDemon’s source code from its GitHub page.

PhotoDemon is funded by donations from users like you.
Please consider a small donation to fund development and to help me support my family.
Even $1.00 helps. Thank you!

List of what’s new and improved in v5.2 (so far)

  • Selection tool! It’s a hell of a tool, and a lot of work went into making it as user-friendly and powerful as possible. Three render modes are provided. On-canvas resizing and moving are fully supported as well. Everything in the Color and Filter menus will operate on a selection if available, as well as the Edit -> Copy command. (Note: as of this beta, selections are not yet tied into Undo/Redo, and selections will not be recorded as part of a Macro.)
  • PhotoDemon Selection Tool
    Here’s an example of the selection tool in action. Note that the HSL adjustment tool is only operating on the selected area.
  • Image cropping is now possible via the Crop-to-Selection option (in the Image menu).
  • New HSL adjustment tool. (See above screenshot for sample.)
  • New Rechannel tool. Live previews, CMY, and CMYK color spaces were added.
  • PhotoDemon’s new and improved Rechannel tool.
  • New Sepia filter based off the official W3C formula (available here). I still prefer PhotoDemon’s “Filters -> Antique” effect, but felt it was worthwhile to make both available.
  • Here’s the sepia version of the photo from the Rechannel screenshot. I took this photo during a hike up Spanish Fork Canyon several weeks ago; the fall colors were stunning.
  • Vast improvements to PhotoDemon’s support for images with transparency. Images with alpha-channels will now be rendered as alpha in all filter and tool screens. When printing, saving as 24bpp, or copying to the clipboard, the image will be composited against a white background. User preferences were also added for transparency checkerboard color and sizes.
  • All-new User Preferences dialog. Many new options were added, and the Preferences interface is now sorted by category.
  • Interface-related options in the new Preferences dialog.
    As another example, here are the afore-mentioned transparency handling options.
  • Improved font rendering is now available for users on Windows Vista, Windows 7, and Windows 8.
  • A drop-shadow can now be rendered between the image and the canvas (similar to Paint.NET).
  • PhotoDemon is now capable of remembering its window size and position between sessions.
  • Multiple monitors are now supported by the Import -> Screen Capture tool.
  • Many miscellaneous interface improvements. Additionally, I am testing a new layout in the Color -> Grayscale tool. This layout style is intended to help users make sense of PhotoDemon’s many options. Let me know what you think, because if this style is popular, I will redo the other tool dialogs to match.
  • Heavily optimized viewport rendering. PhotoDemon now uses a triple-buffer rendering pipeline to speed up actions like zooming, scrolling, and using on-canvas tools like the new Selection Tool. Even when working with 32bpp images, all actions should render in real-time on any modern system.
  • Bilinear interpolation is now used in “Convert to Isometric Image”. This results in a much higher-quality transform. Hard edges are still left along the image border to make mask generation easy for game designers.
  • Many bug fixes and miscellaneous improvements. For complete details, please visit the commit log at https://github.com/tannerhelland/PhotoDemon/commits/master

Announcing PhotoDemon 5.0 – Everything is Faster, Everything is Better

Summary

PhotoDemon v5.0 is now available. It’s the biggest update PhotoDemon has seen in years, and it’s awesome. Download it here.

PhotoDemon 5.0 boasts a ton of improvements – both on the surface and under the hood.

New Feature: All-New Image Subsystem

In version 5.0, the way PhotoDemon stores and processes image data has been rewritten from scratch. What does this mean for you?

  • Filters, effects, and all tools are faster than version 4.4.
  • The software uses roughly half the RAM of previous versions.
  • No more upper limit on image sizes. Huge photos (30+ megapixel) should work just fine on any modern PC. The only limiting factor is the amount of RAM (actual and virtual) available on your system.
  • Much faster batch conversions. As an example of how much better version 5.0 is: I ran two identical batch conversions of 138 wedding photos (10 megapixels each, 3872×2592 pixels). The batch conversion was simple – load each image, then save it in another folder at a different JPEG quality. PhotoDemon 4.4 performed the conversion in 2 minutes 21 seconds. PhotoDemon 5.0 does it in 1 minute 11 seconds.
  • Much better OSX and Linux compatibility via Wine. (Wine v1.4 or later is required.)

This sole feature was the largest update PhotoDemon has seen in the past five years. As a teaser, the new subsystem is also compatible with selections and layers, which may make an appearance in a future update…

New Feature: Alpha-Channel (Transparency) Support

For the first time in the history of the program, PhotoDemon now provides proper transparency support. When images with an alpha-channel are loaded, PhotoDemon will automatically maintain the transparency data for the life of the image. When the image is saved to file, the alpha-channel is added back in, allowing you to do any amount of edits to images without harming the underlying alpha data.

Transformations like resizing and rotating also preserve the alpha channel. (Again, this was a prerequisite to features like layers… see a pattern here?)

New Feature: Redesigned Interface

Every menu item in PhotoDemon now has a descriptive icon, and menus have been reorganized according to improved design rules. No menu is more than two layers deep, and new accelerators (hotkeys) have been added to popular features.

The redesigned Color menu

The left-hand bar has been updated once again. Per feedback from users, a dedicated Close and Save As button has been added, along with descriptive text for each button. Tool-tips have also been added to each button. (Thanks to Robert Rayment for the suggestion!) Finally, the zoom box has been rebuilt with a new, more useful set of zoom values.

New left-hand bar in 5.0, including descriptive tool-tips.

All preview boxes have been enlarged on tool, filter, and effect windows. Text has also been enlarged to improve readability. PhotoDemon was originally designed to run on 800×600 resolutions (that was a concern in 2001!) but there’s no need for it to remain so compact in 2012.

The old and new edge detection tools
The old and new Custom Filter tools

Finally, a new View menu has been added to provide compatibility with other popular photo editors. The new menu is a great place to discover all the useful hotkeys (also called “accelerators”) for popular zoom functions. The key listed on the right-hand side of a menu item can be used as a shortcut to that menu – so pressing the “+” key will zoom in, the “-” key will zoom out, and the “0” key will instantly fit the entire image on the screen.

The new View menu

New Feature: All-New Image Load/Save Engine

PhotoDemon 5.0 uses a completely new system for getting images into – and out of – the program. As you may know, the program relies on an outside library called FreeImage for supporting non-standard image formats like Photoshop files (PSD), Macintosh PICT files (PICT), DirectDraw surfaces (DDS), and more.

FreeImage is an excellent tool, but its implementation in past versions of PhotoDemon was very rudimentary. PhotoDemon relied on FreeImage to do its own image file type detection, configure each image type properly, and prepare it for use within the program. While it was pretty good at guessing these parameters, it was not foolproof, and odd color-depths, transparencies, and mismatched file extensions could result in failed image loads or even program crashes.

So for version 5.0, the FreeImage interface was rewritten from the ground up. When images are loaded, a fallback system is used to identify the file format – first the file header is compared against a database of known filetypes. That works for 95+% of files. If for some reason a header cannot be found (which is the case with some formats, including outliers like CUT, MNG, PCD, TGA and WBMP), the image’s file extension is then analyzed. If that fails, PhotoDemon will attempt to blindly load bitmap data and hope for the best. And, if even that fails, PhotoDemon will give the image one final try by passing control off to the Windows’ GDI+ system and seeing if it can decipher the file.

This should make PhotoDemon as robust as possible when loading images. (Thanks to Herman Liu for much testing and help with the new image import implementation!) The full list of file formats supported by PhotoDemon now includes:

Importing:

  • BMP – Windows Bitmap
  • DDS – DirectDraw Surface
  • GIF – Compuserve
  • ICO – Windows Icon
  • IFF – Amiga Interchange Format
  • JNG – JPEG Network Graphics
  • JPG/JPEG – Joint Photographic Experts Group
  • KOA/KOALA – Commodore 64
  • LBM – Deluxe Paint
  • MNG – Multiple Network Graphics
  • PBM – Portable Bitmap
  • PCD – Kodak PhotoCD
  • PCX – Zsoft Paintbrush (uncompressed only)
  • PDI – PhotoDemon Image (the program’s native format)
  • PGM – Portable Greymap
  • PIC/PICT – Macintosh Picture
  • PNG – Portable Network Graphic
  • PPM – Portable Pixmap
  • PSD – Adobe Photoshop
  • RAS – Sun Raster File
  • SGI/RGB/BW – Silicon Graphics Image
  • TGA – Truevision Targa
  • TIF/TIFF – Tagged Image File Format
  • WBMP – Wireless Bitmap

Exporting:

  • BMP – Windows Bitmap
  • GIF – Graphics Interchange Format
  • JPG – Joint Photographic Experts Group
  • PDI – PhotoDemon Image (the program’s native format)
  • PNG – Portable Network Graphic
  • PPM – Portable Pixel Map
  • TGA – Truevision Targa
  • TIFF – Tagged Image File Format

New Feature: Color Temperature Tool

A full discussion of color temperature and how it works is available at this Wikipedia article, but a simple description is: color temperature allows you to retroactively adjust the lighting of a photograph. It’s a powerful way to change the mood of a photo, or to adjust lighting to reflect how you remember a scene – versus what the camera actually caught.

The all-new Color Temperature tool. To my knowledge, no other free photo editor provides a tool like this.

I’m quite proud of this tool, in part because it took a ridiculous amount of work to build. Other free photo editors like GIMP and Paint.NET lack anything like this, so short of Photoshop, PhotoDemon is one of the only software programs to provide such a feature.

The image below – a promotional poster for the HBO series True Blood – nicely demonstrates the potential of color temperature adjustments. On the left is the original shot; on the right, a color temperature adjustment using PhotoDemon. In one click, a nighttime scene can been recast in daylight.

Color temperature adjustment in action.

New Feature: Black and White (1-bit) Conversion

PhotoDemon already possesses a powerful grayscale engine, with more conversion options than any other tool on the market. But what if you want to literally convert an image to black and white – as in just black and just white?

Now you can, thanks to a revamped black-and-white tool.

The new black-and-white tool, rewritten from scratch for 5.0.

The new tool operates hand-in-hand with a flexible, powerful dithering engine. The new engine design allows for any combination of dithering and threshold, and if you’d like, you can also have PhotoDemon estimate an ideal threshold value for a given image. (An ideal threshold is one that leads to an image that’s roughly 50% black and 50% white.)

A comprehensive assortment of dithering algorithms is provided, including: Bayer 4×4 and 8×8, False (fast) Floyd-Steinberg, Genuine Floyd-Steinberg, Jarvis/Judice/Ninke, Stucki, Burkes, Sierra-3, Two-Row Sierra, Sierra Lite, and my personal favorite – Bill Atkinson’s classic Macintosh algorithm, which featured prominently in the original Apple Macintosh. Images treated with this algorithm evoke a certain nostalgia for anyone old enough to remember that era of computing.

Atkinson dithering, as applied to a screen capture from a Warehouse 13 episode.

New Feature: Tile Tool

Have you ever needed to tile an image? There are a lot of ways to do it. Most involve copying-and-pasting an image over and over again, then manually arranging those copies into a grid.

I hate tedious tasks like that. So PhotoDemon has a new tool that makes tiling a trivial operation.

The new Tile tool.

You can tile according to three rules: the current screen size (automatically detected), a set size in pixels, or a set number of tiles. The tool will automatically convert between each system for you, and it will let you know the size of the final image in both tiles and pixels.

Other new features and updates in version 5.0

Other updates in v5.0 include:

  • New “Duplicate Image” tool. Perfect for making a working copy of an image without fear of overwriting the original. (Thanks to Achmad Junus for the suggestion!)
  • Drag-and-Drop compatibility. Drag images from your desktop or file manager onto PhotoDemon, and it will open them all automatically. (Thanks to Kroc of camendesign.com for the suggestion!)
  • Auto-Enhance overhaul. All four auto-enhance tools (contrast, highlights, midtones, shadows) have been rewritten from scratch using completely new algorithms. I think you’ll find them way more useful than the old tools.
  • Improved mosaic tool. Faster, higher quality, and mosaics can now be as large as the image or as tiny as one pixel in either dimension.
  • Improved handling of edge pixels for all convolution filters (blur, soften, sharpen, etc)
  • Improved manual color reduction algorithms (faster and higher quality)
  • New histogram equalization form. Equalize any combination of color channels (red, green, blue) and luminance with real-time previews.
  • DPI-aware images mean no more distortion at 120dpi – a big improvement for people using “large font” settings.
  • Fixes for users of the “Classic Theme” in modern versions of Windows. Your menus should look much better in this release.
  • Improved bug reporting system and online form to match.
  • Tons of miscellaneous bug fixes, tweaks, and optimizations. For a full list of changes, visit https://github.com/tannerhelland/PhotoDemon/commits/master

In Conclusion…

I hope you enjoy the many improvements in version 5.0. As always, feel free to contact me with any feedback you might have.

How to Convert Temperature (K) to RGB: Algorithm and Sample Code

Converting temperature (Kelvin) to RGB: an overview

If you don’t know what “color temperature” is, start here.

While working on a “Color Temperature” tool for PhotoDemon, I spent an evening trying to track down a simple, straightforward algorithm for converting between temperature (in Kelvin) and RGB values. This seemed like an easy algorithm to find, since many photo editors provide tools for correcting an image’s color temperature in post-production, and every modern camera – including smartphones – provides a way to adjust white balance based on the lighting conditions of a shot.

Example of a camera white balance screen. Image courtesy of http://digitalcamerareviews2011online.blogspot.com

Little did I know, but it’s pretty much impossible to find a reliable temperature to RGB conversion formula. Granted, there are some algorithms out there, but most work by converting temperature to the XYZ color space, to which you could add your own RGB transformation after the fact. Such algorithms seem to be based off AR Robertson’s method, one implementation of which is here, while another is here.

Unfortunately, that approach isn’t really a mathematical formula – it’s just glorified look-up table interpolation. That might be a reasonable solution under certain circumstances, but when you factor in the additional XYZ -> RGB transformation required, it’s just too slow and overwrought for simple real-time color temperature adjustment.

So I wrote my own algorithm, and it works pretty damn well. Here’s how I did it.

Caveats for using this algorithm

Caveat 1: my algorithm provides a high-quality approximation, but it’s not accurate enough for serious scientific use. It’s designed primarily for photo manipulation – so don’t try and use it for astronomy or medical imaging.

Caveat 2: due to its relative simplicity, this algorithm is fast enough to work in real-time on reasonably sized images (I tested it on 12 megapixel shots), but for best results you should apply mathematical optimizations specific to your programming language. I’m presenting it here without math optimizations so as to not over-complicate it.

Caveat 3: this algorithm is only designed to be used between 1000 K and 40000 K, which is a nice spectrum for photography. (Actually, it’s way larger than most photographic situations will ever call for.) While it will work for temperatures outside these ranges, the estimation quality will decline.

Special thanks to Mitchell Charity

First off, I owe a big debt of gratitude to the source data I used to generate these algorithms – Mitchell Charity’s raw blackbody datafile at http://www.vendian.org/mncharity/dir3/blackbody/UnstableURLs/bbr_color.html. Charity provides two datasets, and my algorithm uses the CIE 1964 10-degree color matching function. A discussion of the CIE 1931 2-degree CMF with Judd Vos corrections versus the 1964 10-degree set is way beyond the scope of this article, but you can start here for a more comprehensive analysis if you’re so inclined.

The Algorithm: sample output

Here’s the output of the algorithm from 1000 K to 40000 K:

Output of my algorithm from 1000 K to 40000 K. The white point occurs at 6500-6600 K, which is perfect for photo manipulation purposes on a modern LCD monitor.

Here’s a more detailed shot of the algorithm in the interesting photographic range, which is 1500 K to 15000 K:

Same algorithm, but from 1500 K to 15000 K

As you can see, banding is minimal – which is a big improvement over the aforementioned look-up table methods. The algorithm also does a great job of preserving the slightly yellow cast leading up to the white point, which is important for imitating daylight in post-production photo manipulation.

How I arrived at this algorithm

My first step in reverse-engineering a reliable formula was to plot Charity’s original blackbody values. You can download my whole worksheet here in LibreOffice / OpenOffice .ods format (430kb).

Here’s how the data looks when plotted:

Mitchell Charity’s original Temperature (K) to RGB (sRGB) data, plotted in LibreOffice Calc. Again, these are based off the CIE 1964 10-degree CMFs. The white point, as desired, occurs between 6500 K and 6600 K (the peak on the left-hand side of the chart). (Source: http://www.vendian.org/mncharity/dir3/blackbody/UnstableURLs/bbr_color.html)

From this, it’s easy to note that there are a few floors and ceilings that make our algorithm easier. Specifically:

  • Red values below 6600 K are always 255
  • Blue values below 2000 K are always 0
  • Blue values above 6500 K are always 255

It’s also important to note that for purposes of fitting a curve to the data, green is best treated as two separate curves – one for temperatures below 6600 K, and a separate one for temperatures above that point.

From here, I separated the data (without the “always 0” and “always 255” segments) into individual color components. In a perfect world, a curve could then be fitted to each set of points, but unfortunately it wasn’t that simple. Because there’s a large disparity between the X and Y values in the plot – the x-values are all over 1000, and they are plotted in 100 point segments, while the y values all fall between 255 and 0 – it was necessary to transpose the x data in order to get a better fit. For optimization purposes, I stuck to first dividing the x value (the temperature) by 100 across each color, followed by an additional subtraction if it led to a significantly better fit. Here are the resultant charts for each curve, along with the best-fit curve and corresponding R-squared value:

Apologies for the horrifically poor font kerning and hinting in those charts. I love LibreOffice for many things, but its inability to do font aliasing on charts is downright shameful. I also don’t like having to extract charts from screenshots because they don’t have an export option, but that’s a rant best saved for some other day.

As you can see, the curves all fit reasonably well, with R-square values above .987. I could have spent more time really tweaking the curves, but for purposes of photo manipulation these are plenty close enough. No layperson is going to be able to tell that the curves don’t exactly fit raw idealized blackbody observations, right?

The algorithm

Using that data, here’s the algorithm, in all its glory.

First, pseudocode:



    Start with a temperature, in Kelvin, somewhere between 1000 and 40000.  (Other values may work,
     but I can't make any promises about the quality of the algorithm's estimates above 40000 K.)
    Note also that the temperature and color variables need to be declared as floating-point.

    Set Temperature = Temperature \ 100
    
    Calculate Red:

    If Temperature <= 66 Then
        Red = 255
    Else
        Red = Temperature - 60
        Red = 329.698727446 * (Red ^ -0.1332047592)
        If Red < 0 Then Red = 0
        If Red > 255 Then Red = 255
    End If
    
    Calculate Green:

    If Temperature <= 66 Then
        Green = Temperature
        Green = 99.4708025861 * Ln(Green) - 161.1195681661
        If Green < 0 Then Green = 0
        If Green > 255 Then Green = 255
    Else
        Green = Temperature - 60
        Green = 288.1221695283 * (Green ^ -0.0755148492)
        If Green < 0 Then Green = 0
        If Green > 255 Then Green = 255
    End If
    
    Calculate Blue:

    If Temperature >= 66 Then
        Blue = 255
    Else

        If Temperature <= 19 Then
            Blue = 0
        Else
            Blue = Temperature - 10
            Blue = 138.5177312231 * Ln(Blue) - 305.0447927307
            If Blue < 0 Then Blue = 0
            If Blue > 255 Then Blue = 255
        End If

    End If

In the pseudocode above, note that Ln() means natural logarithm. Note also that you can omit the “If color < 0” checks if you will only ever supply temperatures in the recommended range. (You still need to leave the “If color > 255” checks, though.)

As for actual code, here’s the exact Visual Basic function I’m using in PhotoDemon. It’s not yet optimized (for example, the logarithms would be much faster via look-up table) but at least the code is short and readable:


'Given a temperature (in Kelvin), estimate an RGB equivalent
Private Sub getRGBfromTemperature(ByRef r As Long, ByRef g As Long, ByRef b As Long, ByVal tmpKelvin As Long)

    Static tmpCalc As Double

    'Temperature must fall between 1000 and 40000 degrees
    If tmpKelvin < 1000 Then tmpKelvin = 1000
    If tmpKelvin > 40000 Then tmpKelvin = 40000
    
    'All calculations require tmpKelvin \ 100, so only do the conversion once
    tmpKelvin = tmpKelvin \ 100
    
    'Calculate each color in turn
    
    'First: red
    If tmpKelvin <= 66 Then
        r = 255
    Else
        'Note: the R-squared value for this approximation is .988
        tmpCalc = tmpKelvin - 60
        tmpCalc = 329.698727446 * (tmpCalc ^ -0.1332047592)
        r = tmpCalc
        If r < 0 Then r = 0
        If r > 255 Then r = 255
    End If
    
    'Second: green
    If tmpKelvin <= 66 Then
        'Note: the R-squared value for this approximation is .996
        tmpCalc = tmpKelvin
        tmpCalc = 99.4708025861 * Log(tmpCalc) - 161.1195681661
        g = tmpCalc
        If g < 0 Then g = 0
        If g > 255 Then g = 255
    Else
        'Note: the R-squared value for this approximation is .987
        tmpCalc = tmpKelvin - 60
        tmpCalc = 288.1221695283 * (tmpCalc ^ -0.0755148492)
        g = tmpCalc
        If g < 0 Then g = 0
        If g > 255 Then g = 255
    End If
    
    'Third: blue
    If tmpKelvin >= 66 Then
        b = 255
    ElseIf tmpKelvin <= 19 Then
        b = 0
    Else
        'Note: the R-squared value for this approximation is .998
        tmpCalc = tmpKelvin - 10
        tmpCalc = 138.5177312231 * Log(tmpCalc) - 305.0447927307
        
        b = tmpCalc
        If b < 0 Then b = 0
        If b > 255 Then b = 255
    End If
    
End Sub

This function was used to generate the sample output near the start of this article, so I can guarantee that it works.

Sample images

Here’s a great example of what color temperature adjustments can do. The image below – a promotional poster for the HBO series True Blood – nicely demonstrates the potential of color temperature adjustments. On the left is the original shot; on the right, a color temperature adjustment using the code above. In one click, a nighttime scene can been recast in daylight.

Color temperature adjustments in action. (Click for full size)

The actual color temperature tool in my PhotoDemon project looks like this:

PhotoDemon’s Color Temperature tool.

Download it here to see it in action.

addendum October 2014

Renaud Bédard has put together a great online demonstration of this algorithm. Check it out here, and thanks to Renaud for sharing!

addendum April 2015

Thank you to everyone who has suggested improvements to the original algorithm. I know there are a lot of comments on this article, but they’re worth reading if you’re planning on implementing your own version.

I’d like to call out two specific improvements. First, Neil B has helpfully provided a better version of the original curve-fitting functions, which results in slightly modified temperature coefficients. His excellent article describes the changes in detail.

Next, Francis Loch has added some comments and sample images below, which are very helpful if you want to apply these corrections to a photograph. His modifications produce a much more detailed image, as his sample images demonstrate.

Announcing PhotoDemon 5.0 Beta 1 – Testers Needed!

  1. Summary
  2. Download
  3. PhotoDemon 5.0: A Bit of Background
  4. List of what’s new and improved
PhotoDemon’s biggest update in years is nearing completion, which means it’s time for you to try and break it. Give it a spin and let me know what you think of the improvements (which are many!)

Summary

PhotoDemon 5.0 is nearing completion, and I need help testing it. Version 5.0 includes an all-new image subsystem that required rewriting every filter and effect in the program (and some 17,000 lines of code!). All those changes have made the software significantly faster and smoother, but it might also have broken a few things. Download the beta and help me make sure everything is working the way it’s supposed to.

Download

The PhotoDemon 5.0 beta 1 comes in two flavors:

Remember – if you are an advanced user, you can always download the most recent development build of PhotoDemon’s source code from its GitHub page.

PhotoDemon is funded by donations from users like you.
Please consider a small donation to fund development and to help me support my family.
Even $1.00 helps. Thank you!

PhotoDemon 5.0: A Bit of Background

As you might know, PhotoDemon has a long and complicated history spanning some 12 years. That longevity has some perks – for example, tons of features – but it also has some downsides.

One of the biggest downsides to being 12 years old is that the software carries with it some bad design choices, made many years ago when I was a young and immature programmer, that have perpetually bogged down the implementation of new and exciting features. In particular, features like large images, selections, and alpha-channel (transparency) support have all been impossible because of the way PhotoDemon stores and renders images. Originally, the software was only meant to work on 8-bit images, and 24-bit support was later tacked on as an afterthought. I took that framework as far as I could go, but upon releasing PhotoDemon to the public earlier this year, I realized that it was time to fix that problem.

Enter version 5.0.

PhotoDemon 5.0 has just about been rewritten from the ground up, and I don’t say that lightly. The software is comprised of some 30,000 lines of code, and version 5.0 involved the writing of more than half (17,000) of those lines. Why? Because it was finally time for a completely new image subsystem, one capable of potentially supporting selections, alpha-channels, high bit-depths, layers, and whatever else I might want to someday throw at it.

(Note: features like selections are not yet part of PhotoDemon. They will take a good chunk of time to write – but at least now it will be physically possible to add them!)

This new image subsystem is something I’m very proud of. At a high level, it’s basically a specialized image class that stores and tracks all image data, and passes that data between the screen, image files, and various filters and effects. The subsystem does not rely on anything specific to Visual Basic (the programming language PhotoDemon is written in), meaning it is capable of supporting any features it wants – regardless of whether or not VB actually supports them. Past versions of PhotoDemon relied on VB’s inherent “picture boxes”, as they are called, for image storage and processing, and because VB6 is now 14 years old it simply couldn’t handle things like large images or transparency.

But no more.

This rewrite has been a massive project, and every single filter and tool (every damn one!) had to be rewritten to accommodate the new technology. This proved to be a good thing, because I hadn’t revisited some of those filters for over a decade, and in the past ten years I’ve learned a great deal about writing cleaner, better, faster imaging code. That made this a prime chance to re-engineer every filter and tool in the program to make it as fast and accurate as possible, and I think you’ll like the result.

But enough about this – you probably want to know what’s actually new in PhotoDemon 5.0. I won’t discuss everything here (some features are still under construction), but here are the highlights.

List of what’s new and improved in v5.0 beta 1

  • Everything is faster – all filters, tools, effects, loading images, saving images, macros, batch conversion, undo/redo. Seriously – EVERYTHING.
  • Completely rewritten image load/save code. As an example of how much better the new version is: I ran two identical batch conversions of 138 wedding photos (10 megapixels each, 3872×2592 pixels). The batch conversion was simple – load each image, then save it in another folder at a different JPEG quality. PhotoDemon 4.4 did the conversion in 2 minutes 21 seconds. The PhotoDemon 5.0 beta did it in 1 minute 11 seconds. (Thanks to Herman Liu for much testing and help with the implementation!)
  • Redesigned menus. Every item has a descriptive icon, and menus have been reorganized according to improved design rules
  • Menus now have useful icons and improved organization
  • Drag-and-Drop compatibility. Drag images from your desktop or file manager onto PhotoDemon, and it will open them all automatically. (Thanks to Kroc of camendesign.com for the suggestion!)
  • MUCH better Wine compatibility for OSX and Linux users. Undo/Redo and all tools and effects should now work under Wine. Let me know if you find any that do not.
  • New “Tile” tool tiles the current image to a target size (in pixels) or number of tiles. (Thanks to Ye Peng for the suggestion!)
  • PhotoDemon’s new “Tile” tool
  • New “Duplicate Image” tool. Perfect for making a working copy of an image without fear of overwriting the original. (Thanks to Achmad Junus for the suggestion!)
  • Auto-Enhance overhaul. All four auto-enhance tools (contrast, highlights, midtones, shadows) have been rewritten from scratch using completely new algorithms. I think you’ll find them way more useful than the old tools.
  • Improved mosaic tool. Faster, higher quality, and mosaics can now be as large as the image or as tiny as one pixel in either dimension.
  • Added previewing to a bunch of forms that lacked it before – Reduce Colors (Quantize), Black and White Conversion, Find Edges
  • Increased size of all preview windows. They are now much larger, which makes it easier to see how a filter or tool will affect an image.
  • Improved handling of edge pixels for all convolution filters (blur, soften, sharpen, etc)
  • Improved color reduction algorithms (faster and higher quality)
  • Floating-point implementation of histogram equalization means it is now significantly more accurate
  • DPI-aware images mean no more distortion at 120dpi – a big improvement for people using “larger font” settings in Windows
  • No limit on image sizes. The bigger, the better. (Thanks to Robert Rayment for his help with this bug!)
  • Full GDI+ support for saving and loading. If the FreeImage plugin can’t be found, GIF/JPEG/PNG/TIFF import and export will still be available. (Thanks to Alfred Hellmueller for the suggestion to add GDI+ compatibility!)
  • Turbo JPEG loading while batch conversions are running
  • Improved bug reporting system and online form to match
  • Tons of miscellaneous bug fixes, tweaks, and optimizations

Announcing PhotoDemon 4.4 – Now With Update Notifications, Improved Histogram, and More

Summary

PhotoDemon v4.4 is now available. It has a lot of cool new features. Download it here.

New Feature: Update Notifications

The most important update in version 4.4 is the addition of an automatic update notifier.

PhotoDemon's new update notifier
PhotoDemon’s new update notifier.

By default, PhotoDemon will check for updates whenever the software is run. Automatic update checks can be disabled from the Edit -> Preferences menu. You can also manually check for updates by going to Help -> Check for Updates.

I’m not sold on the layout of the update notification form – particularly the center alignment of the version numbers, which looks off due to the white space on the right-hand side – so its appearance may change in future versions, but at least this first draft conveys all the essential information.

Finally, note that this is merely an update notifier, not an automatic updater – clicking the “Yes” button will only open the PhotoDemon download page in your browser. It will not download the update for you, and it will not overwrite your current copy of the software. This is my preferred behavior for portable applications, but I am open to suggestions for better methods.

New Feature: Helpful Undo/Redo Text

The left-hand bar in v4.4 has been redesigned from version 4.3:

Comparison of v4.3 and v4.4 left-hand bar
v4.3 is on the left, v4.4 is on the right

The new, more compact version is in preparation for adding additional tools to the bottom section of the left-hand bar. It was also done as part of the new “friendly text” version of the Undo/Redo buttons:

new Undo/Redo interface
PhotoDemon’s helpful new Undo/Redo text.

I tried displaying the full text of the Undo/Redo action in the Undo/Redo buttons themselves, but as some of the descriptions are rather long, the button text would get pushed onto multiple lines (or off the button entirely!) making them look terrible. So the current implementation is: hover over the Undo/Redo button to see what action will be performed. As you can see, the Edit menu also contains a full-text description of Undo/Redo behavior.

Redesigned Histogram

With version 4.4, I don’t think it’s biased to say that PhotoDemon provides the best image histogram tool in the business:

PhotoDemon 4.4's redesigned histogram
PhotoDemon 4.4’s redesigned histogram

Individual channels can now be hidden or displayed in any combination. (The histogram will automatically adjust its maximum and minimum values accordingly.) This is useful for comparing just two color channels, for example, or comparing a single color channel against luminance.

The histogram now provides a “use smooth lines” option. This enables two features: antialiased lines (which VB does not do natively, so it’s a custom implementation), and cubic spline interpolation. Here’s an example of the aesthetic difference this makes:

Comparison of histogram render methods
Makes a difference, doesn’t it?

The new histogram interface provides a logarithmic rendering option. Images that are very dark or very bright will blow out the histogram at one end or the other, making it very difficult to see what’s happening in those ranges. Take the histogram of this beautiful FF7 fan art from pixiv.net user マップ, for example:

Image in need of a logarithmic histogram

Logarithmic histogram in action

Classic features like displaying the values of the histogram level under the cursor are still present, and you can still export the histogram image to an 8-bit PNG, GIF, or BMP file.

Finally, as of version 4.4 PhotoDemon’s histogram window is now non-modal. This means that you can leave the histogram window open while loading/saving/manipulating images, and the window will automatically refresh itself when necessary. Perform a filter or color operation and the histogram will update to reflect those changes; Undo a previous action and it will also update, making it very useful for comparing the effects of various filters.

As part of these updates, the histogram code has been newly refactored and optimized, so it’s fast and extremely low-resource, even when left open during image operations. All histogram data is pre-calculated, so when you change rendering options (such as enabling/disabling channels or switching between logarithmic and regular representation) the new histogram is instantly redrawn without requiring a recalculation of the raw data.

I’m not done with histogram updates, but v4.4 provides a great improvement over v4.3.

Redesigned Grayscale Interface and New Grayscale Algorithms

The grayscale conversion form has been completely redesigned in v4.4:

Redesigned grayscale interface
Special thanks to pixiv user ぴよな*ティア for the image in the preview.

Grayscale conversion was one of the last features to lack an instant-preview option, but no longer – you can now see real-time previews of the various grayscale algorithms.

I have also ported over all seven of the grayscale conversion algorithms from my standalone grayscale project, some of which were not present in PhotoDemon. The full list of available grayscale conversion methods now includes:

  • Averaging
  • ITU standard (adjusting for cone density in the human eyes)
  • Desaturation (HSL color space)
  • Decomposition to maximum or minimum values
  • Single color channel reduction
  • Reduction to specific # of gray shades
  • Reduction to specific # of gray shades with dithering

PhotoDemon defaults to the ITU standard method, which is the best choice for people who have no idea what these various options mean. :) For a full discussion of how these methods work and why some are preferable to others, see my aforementioned in-depth grayscale article.

Finally, the reduce-to-specific-number-of-shades option can now be used to reduce an image to black and white (two shades). Previously it required three shades or more. That said, I still advise using PhotoDemon’s specific “convert to black and white” menu option, which provides more control over 2-color reduction.

Other miscellaneous updates and bugfixes

Other updates in v4.4 include:

  • The system hand cursor is now automatically applied to all clickable objects. This was previously done manually, and because VB isn’t smart about sharing resources, a hand cursor was stored in multiple places throughout the .exe. The new automated feature meant I could remove those references, so the new v4.4 .exe is actually smaller than v4.3, despite including a bunch of additional features. Windows Vista/7 users will also get a much prettier hand icon.
  • Batch conversion now has a more robust error handler. This is in preparation for the addition of an all-new batch conversion wizard, which didn’t make the cut for 4.4 but should be included in 4.5
  • Miscellaneous bug fixes related to save prompting, MDI maximizing, and more. See a full list of updates at PhotoDemon’s commit page on github.

In Conclusion…

I hope you enjoy the changes in version 4.4. As always, feel free to contact me with any feedback you might have.