Monochrome Dithering in Bmp2HGR – An Overview

Introduction

Original Image 24-bit grey-scale

Resolution 560 x 384

Bmp2DHR – Floyd-Steinberg

Apple II Resolution 560 x 192

Double Hi-Res Graphics (DHGR) provides the most capable display mode that can be enjoyed across all Apple II computers from the time of the Apple IIe (1983), through the IIc, IIc Plus to the IIgs.

Bill Atkinson – Old Photo

Floyd-Steinberg - 25% reduced color bleed

The technology to produce DHGR dithered images somewhat approaching the quality shown above existed before Apple Computer made DHGR available, but Apple was focused on the Macintosh which was released the same year (1983), and applied their most advanced graphics on the Mac instead of on the already dated Apple II.

The Mac Team - 24-bit grey-scale

Bmp2DHR Atkinson – 560 x 192 DHGR

The Mac had a 9” monochrome display with square pixels and a fixed resolution of 512 x 342 pixels, almost twice DHGR monochrome resolution of 560 x 192. They even had their own “official” monochrome dither; Atkinson, which was first implemented in November 1984 by Andy Herzog in the Mac’s Thunderscan Software.

As the sun set on the Apple II, the DHGR user fumbled along with what passed for DHGR dithering in Jason Harper’s “][gif” freeware viewer for IBM-PC 256 color GIF images. GIF images were quite the rage at the time and despite “][gif’s” appalling rendering, a little love from the PC was better than no love at all. “][gif” basically went viral struggling to display IBM-PC images on Apple II’s all over the world. With the coming of the Internet, GIF remained the rage for quite a while, providing a ready supply of PC graphics for the Apple II user to diddle in “][gif”. PC color desktop graphics soon left Apple even further behind as the Macintosh continued to focus in niche monochrome markets like Desktop Publishing. It was quite a while before the Mac caught-up.

How much more would have been done if Bill Atkinson had worked some of his magic on DHGR in the days of the ThunderScan?

Original Image – 24-bit color

Atkinson Color

Atkinson 33% increased color bleed

Atkinson Mono

Original Image – 24-bit grey-scale

Atkinson Mono

Floyd-Steinberg Mono

Floyd-Steinberg 25% reduced color bleed

When the Apple IIgs came along with its more capable Super Hi-Res (SHR) graphics, and Bill Atkinson finally did some dithering, for Apple it was about selling computers rather than advancing DHGR on the Apple II’s previous models. Interest in advancing DHGR further seemed to vanish from the planet until only very recently with 3 notable efforts that offer color DHGR error diffusion dithered conversion from modern graphics; Sheldon Simms tohgr, Cybernesto’s VBMP which uses The Gimp, and Bmp2DHR.

About Bmp2DHR

Bmp2DHR is a simple single purpose command line utility for one thing only; producing DHGR output in a variety of rendering options including:

Direct Pixel Mapping (non-dithered default)
Error Diffusion Dithering (command option “d”) 8 – dithers

D, D1	DF	Floyd-Steinberg (default)
D2	DJ	Jarvis, Judice and Ninke
D3	DS	Stucki
D4	DA	Atkinson
D5	DB	Burkes
D6	DSI	Sierra
D7	DS2	Sierra Two
D8	DSL	Sierra Lite

I recently extended Bmp2DHR to include:

Monochrome output to an Apple II DHGR screen file in the same 8 error diffusion dithering algorithms supported for color dithering.

Direct conversion of a monochrome input file to an Apple II DHGR monochrome screen file. This means that monochrome images dithered outside of Bmp2DHR in applications like The GIMP can be converted verbatim. (Color dithered output from The GIMP can also be converted verbatim with Bmp2DHR using the same technique).

Bmp2DHR Review

For color output, Bmp2DHR uses a common psycho visual technique to match RGB colors from 24-bit Windows BMP images to the 16 Apple II colors (really only 15 colors). This technique is a color distance algorithm which includes CCIR 601 luminosity.

Some of Bmp2DHR’s color distance program code was adapted from a routine in Joel Yliluoma's arbitrary-palette positional dithering algorithm: http://bisqwit.iki.fi/story/howto/dither/jy/

For monochrome output, exactly the same routines are used by Bmp2DHR with a 2 color black and white palette in RGB color space. Instead of using a “Classic” threshold of something like summing the rgb values of a color only, Bmp2DHR’s monochrome dithering takes color perception and luminosity into account.

Color clipping is another area of Bmp2DHR’s error diffusion dithering that is also worth mentioning. Bmp2DHR uses a linear distance in RGB space to distribute an error of a positive or negative value. This value is not clamped to the RGB gun range of 0-255. Whether this “sharpens” the contrast in Bmp2DHR’s monochrome dithering or “washes-out” areas of the rendering is also a matter of perception.

The “color bleed” distribution to neighboring pixels in Bmp2DHR is not “academically precise” because no attempt whatsoever is made to avoid rounding by tracking the error’s children by using precision floating point arithmetic or to sum the various children and devising some scheme that decides which children the orphans bunk with.

To Bmp2DHR, such a notion seems like an accounting practice. Dithering is an approximation. Mixing insignificant values with significant values is even more approximate. A penny here or there doesn’t matter much to Bmp2DHR.

It is probably also important to note that “color bleeding” in error diffusion dithering is not defined in Wikipedia:

http://en.wikipedia.org/wiki/Color_bleeding_(disambiguation)

Color bleeding in dithering refers to (the ratio over proportion of) the quantization error to be diffused to neighboring pixels. Atkinson uses a 6/8 color bleed which is called a “reduced color bleed” because the whole error of the RGB differences is not difused. Bmp2DHR allows color bleed reduction by percentage for all of its dithers. By a 25% reduction (r25) of the color bleed of Floyd-Steinberg (which uses a whole color bleed like Bmp2DHR’s other dithers), the ratio over the proportion is scaled to the equivalent of Atkinson’s color bleed for a generally better and more “Mac-like” monochrome dithering. By increasing Atkinson’s color bleed by a negative ratio of minus 33% (r-33) a more “PC-like” color dithering can be achieved like Bmp2DHR’s 7 other dithers.

GAMMA is another area that Bmp2DHR ignores. The theory behind not ignoring GAMMA is that dithering is creating a brand new color where some other color originally lived by adding a bunch of errors to it. More serious minded rendering software may take the approach that GAMMA must be added or subtracted based on the difference of the previous pixel and the new dithered pixel. A penny here or there doesn’t matter much to Bmp2DHR.

Bmp2DHR is even a little cavalier about how it converts the RGB values in 2 colored lines in a 560 x 384 input file to one colored line before it dithers the line to a monochrome line; it merges the RGB values and then simply divides them by 2. In doing so it does not adjust for GAMMA differences and commits the second deadly sin of ignoring rounding errors, considering these insignificant.

According to the GAMMA FAQ “The recipient of an image should insert a transfer function appropriate for his viewing environment.” The appropriate transfer function for Bmp2DHR’s users is an external image editor like The GIMP or Windows Paint with the help of your eyeballs of course.

Images for conversion can be from many different sources, some corrected and some not.

“The NTSC GAMMA is adjusted at the camera”. This says to me to leave GAMMA alone.

“If an image originated in a bright environment and is viewed in a bright environment, it will need no modification no matter what coding is applied.” This says to me that it is up to the user to pre-process an image for GAMMA prior to conversion on an image by image basis.

“Viewing environments typical of computing are quite bright. When an image is coded according to video standards it implicitly carries the assumption of a dim surround. If it is displayed without correction in a bright ambient, it will appear contrasty.” This says to me that “black” areas in an error diffused image where no black occurs in an original image are “contrasty” and will affect the Pyschovisual color balance. This again seems something to ignore; it is up to the user to pre-process an image for GAMMA prior to conversion.

“If an image originates in linear-light form, gamma correction needs to be applied exactly once. If gamma correction is not applied and linear-light image data is applied to a CRT, the midtones will be reproduced too dark. If gamma correction is applied twice, the midtones will be too light.” This again says to me to leave GAMMA alone.

So to sum-up, Bmp2DHR isn’t very sophisticated, and is more concerned with results and appearances than actually doing something insignificant.

DHGR is a weird display as previously noted. Neither the color nor monochrome display has a “square pixel” like on more modern displays; they are both rectangular.

Relatively speaking DHGR color is a “square pixel” resolution of 280 x 192 with “double wide” pixels and an actual resolution of 140 x 192.

Relatively speaking DHGR monochrome is a “square pixel” resolution of 560 x 384 with “double high” pixels and an actual resolution of 560 x 192.

In either case, dithering will have a different appearance on an Apple II than it does on your more modern Bmp2DHR host computer.

To Bmp2DHR a full-screen is a full-screen, with one exception; default image fragment output is a full screen with the image fragment oriented from the top left corner. This is by design to accommodate the preview of the programmer’s rendering of an image fragment, rather than as a way of adjusting for Aspect Ratio.

Color Pre-Scaling

Bmp2DHR produces both full-screen DHGR color images and Image Fragments (“Sprites”). But because it is a simple utility at heart, it only considers even multiples of the DGHR screen resolution of 140 x 192 to be full-screened color images:

140 x 192 – Full-Screen or Image Fragment Output
280 x 192 – Horizontal Half-Scaled Full-Screen or Image Fragment Output
560 x 384 – Classic Full-Screened Even Scaled Output

When I initially designed Bmp2DHR it was as a DHGR color Image Fragment (“Sprite”) converter for the Apple II programmer. My consideration was that Sprites should be of a precise nature. The two input resolutions for Image Fragment output are called “Nominal Resolutions”.

With the addition of Error Diffusion Dithering to Bmp2DHR’s Psychovisual color matching to a variety of conversion palettes, I added some common Classic Sizes for full-screen conversion:

320 x 200 - Classic Full Screen Output by Squeezed or Clipped Scaling
640 x 400 - Classic Full Screen Output by Squeezed or Clipped Scaling
640 x 480 - Classic Full Screen Output by Squeezed or Clipped Scaling

Input files of 560 x 384 and 260 x 192 scale by even factors, but for Classic Sizes that do not scale evenly, you can scale a clipping region of even factors rather than the whole image

Pre-Scaling to full-screen DHGR is done outside of Bmp2DHR in a Paint Program or Photo Editor or some other kind of Image Editor by stretching an image in the horizontal or vertical axis, before saving as a Windows BMP Version 3 in 16 color, 256 color, or 24-bit uncompressed format with scan-lines stored from the bottom-up. This is the default BMP format that Windows Paint saves to.

Pre-Scaling is done in conjunction with clipping of an image if required, and color adjustment if required, prior to conversion. While Bmp2DHR supports many rendering options, it is a BMP to DHGR file converter and not an image studio, and does not concern itself with accepting a variety of image storage formats like GIF or JPEG or PNG, or in color-correction and other things of a photographic nature.

Bmp2DHR is also intended for verbatim conversion of legacy graphics and sprites as well as photos and complex images like art and illustration. So it is left as an exercise for the reader to scale and otherwise pre-process Bmp2DHR’s input files outside of the conversion process using one or more of the many excellent graphics editors available today.

The Short History of Bmp2DHR

We have come a long far way on our journey to today’s world of computer graphics since DHGR was introduced over 30 years ago, so when I set-out to develop Bmp2DHR (the best DHGR image converter on The Planet), I identified 3 essential ingredients that I would need:

Accurate Conversion Palette
Accurate Closest Color Mapping Routine
Accurate Rendering of Multi-Colored Illustrations and Photos

But I didn’t start-out to develop a DHGR converter; it just happened. I started-out by writing a Super Hi-Res (SHR) “Sprite” (Image Fragment) converter for a cc65 C compiler demo and then decided that I should do the same demo and converter in DHGR so that Apple II users who do not have an Apple IIgs could work with the equivalent cc65 routines. But soon I added more functionality, including dithering.

Unlike SHR which uses the 12-bit color model and an arbitrary 16 color palette from 4096 available colors, DHGR has a fixed palette of 15 colors (the same 15 colors available in the Apple II Lo-Res (LGR) and Double Lo-Res (DLGR) modes). In fact Apple II Hi-Res (HGR) also uses 6 colors from this same palette.

Apple II Graphics Modes: http://en.wikipedia.org/wiki/Apple_II_graphics

Accurate Conversion Palette

For accurate conversion to the Apple II DHGR colors an accurate palette is needed. I started-off by using several palettes (emulator palettes included) but was disappointed with the results I got from all but one; the Wikipedia Apple II Palette.

Apple II 15 Color Palette: http://en.wikipedia.org/wiki/List_of_8-bit_computer_hardware_palettes#Apple_II_series

For accurate conversion only the Wikipedia Palette works properly. The two shades of grey are identical in brightness on original Apple II hardware, except on the Apple IIgs. Bmp2DHR also supports a IIgs Wikipedia variant with a lighter grey.

There is also a difference in appearance between the Apple II RGB display and the Apple II composite display but testing using my own real Apple IIe’s RGB display confirm that Bmp2DHR’s conversions are acceptable and uniform on both displays.

The reason that the Wikipedia palette works properly is because the Apple II composite display is based on the YIQ color space:

http://en.wikipedia.org/wiki/YIQ

The DHGR image beside the 640 x 480 version of the Grand Tetons Wikipedia image is in the Wikipedia Apple IIgs Palette using Bill Atkinson’s Error-Diffusion Dithering Algorithm with an increased color bleed of 33%. Note also this same sample image is shown as an example in the Wikipedia YIQ article link noted above.

The YIQ system is intended to take advantage of human color-response characteristics and so is Bmp2DHR’s closest color routine.

Accurate Closest Color Mapping Routine

My previous DHGR converter (BmpA2FC) needed a specific palette. It wasn’t very robust. To make Bmp2DHR more robust, I wanted a closest color routine that would match an accurate Apple II palette from any color in a “true-color” image. Joel Yliluoma's arbitrary-palette positional dithering algorithm article provided a Euclidian distance closest color routine using the Pyschovisual color model that I adapted:

http://bisqwit.iki.fi/story/howto/dither/jy/

Joel’s routine compares the difference of two RGB values weighted by CCIR 601 luminosity. Additional information can be found at the following links:

CCIR 601: http://en.wikipedia.org/wiki/Rec._601

Color Difference: http://en.wikipedia.org/wiki/Color_difference

Accurate Rendering of Multi-Colored Illustrations and Photos

Adding classic error diffusion dithering is thanks mainly to an article by Tanner Helland:

http://www.tannerhelland.com/4660/dithering-eleven-algorithms-source-code/

Floyd Steinberg came first:

http://en.wikipedia.org/wiki/Floyd%E2%80%93Steinberg_dithering

The others followed:

http://www.efg2.com/Lab/Library/ImageProcessing/DHALF.TXT

Download Bmp2DHR

The latest version of Bmp2DHR complete with source code and Windows (Win32) binary can be downloaded here:

http://www.appleoldies.ca/cc65/programs/dhgr/bmp2dhr.zip

Users of systems other than Windows can either build their own latest version from source or download previous versions here (not necessarily the latest version):

MS-DOS: http://www.appleoldies.ca/cc65/programs/dhgr/bmp2dhrMSDOS.zip

Other: (Linux, OSX): http://hoop-la.ca/apple2/appleoldies/bmp2dhr/

Bmp2DHR is the result of work and study by the author (Bill Buckels). It is both a derivative work and an original work. You may use Bmp2DHR and all that it comes with for whatever you wish as long as you agree that Bill Buckels has no warranty or liability obligations whatsoever from said use.

Command Options “mono” and “reverse”

Original Image 24-bit grey-scale

Bmp2DHR – Floyd-Steinberg

The GIMP – Floyd-Steinberg

Converted Verbatim with Bmp2DHR

Jason Harper’s “][gif”

Unknown Algorithm

Bmp2DHR supports 2 types of Monochrome Apple II Double Hi-Res (DHGR) rendering:

Verbatim Direct Pixel Mapping
Error Diffusion Dithering (8 error diffusion dithering algorithms)

Input Files Control Output Type

For direct pixel mapping Bmp2DHR accepts 560 x 192 Monochrome Windows BMP Version 3 files only.

For Error Diffusion Dithering, Bmp2DHR accepts 560 x 384 Windows Color BMP Version 3 files only in 16 color, 256 color or 24-bit (16.7 million colors) only.

External Dithering

To convert dithered output in programs like The GIMP to Monochrome DHGR files, Scale Color Image to 560 x 192, select indexed image, dither with a Black and White Palette, then export to BMP.

The reverse command is the same as the mono command. Programs like The GIMP sometimes save a monochrome BMP in reverse video. When this happens use the reverse command to correct the problem (or to make a negative image from a normal one).

Comparing Apples to Apples

The sample converted images shown displayed in the AppleWin emulator on the previous page include a “][gif” conversion from a 560 x 384 x 256 color GIF file produced in The GIMP from exactly the same image that Bmp2DHR converted.

The GIMP was also used to scale the image with “unchained” aspect ratios. The GIMP’s scaling is much easier to use than the stretching feature in Windows Paint which works by percentage and is not usually accurate so requires clipping to produce a fixed size.

As far as the “][gif” conversion goes, it is included for reference only. Since the colors are already reduced from 16.7 million maximum colors to 256 colors in a GIF file, it would have been unfair to expect “][gif” to produce the same quality of dithered output as either Bmp2DHR or The GIMP unless we used a grey-scale which has 256 grey levels.

So the comparison is on a “level playing field”. Now let’s compare the example image from Wikipedia’s dithering article: http://en.wikipedia.org/wiki/Dither

Wikipedia – Floyd-Steinberg

Bmp2DHR – Floyd-Steinberg

The GIMP – Floyd-Steinberg

Converted Verbatim with Bmp2DHR

Jason Harper’s “][gif”

Unknown Algorithm

Zoom-in 200% or so to see if it better to dither using DHGR, or to diddle with the GIMP or “][gif”. These are displayed in the AppleWin emulator to avoid accusations of bias.

One Last Chance

Let’s give Jason Harper’s “][gif” one last chance. We’ll use the Girl256.gif classic test image from the Brutal Deluxe Website to try to keep things fair:

The color dithered images are presented in the Wikipedia Palette which shows how they appear on a real Apple IIe with a composite monitor.

140 x 192 Color DHGR

Bmp2DHR – Floyd-Steinberg

560 x 192 Monochrome DHGR

The GIMP – Floyd Steinberg “normal”

Converted Verbatim with Bmp2DHR

Bmp2DHR with or without The GIMP seems to do a reasonable job of converting a color GIF file with only 256 colors. I mentioned earlier that the GIMP is easy to use for scaling. When you are scaling a 256 color or a 16 color or even a Monochrome image, promote the image to RGB from indexed. In Windows paint, you would save it as a 24-bit BMP first before stretching it.

140 x 192 Color DHGR

Jason Harper’s “][gif” Unknown Algorithm

560 x 192 Monochrome DHGR

Some things do not improve with age. Strike three, you’re out!

Atkinson Dithering

Atkinson with “normalized” Color Bleed

Classic Atkinson

The output from Jason Harper’s “][gif” makes a terrible mess of DHGR conversion because it failed to utilize technology that was available at the time like Apple Computer’s own Atkinson Dithering developed by Bill Atkinson, the author of MacPaint.

The color DHGR image and the monochrome DHGR image shown above are both dithered using Atkinson Dithering. The color image has been converted with an increased color bleed of 33% which “bumps” the quantization error from Classic Atkinson of 6/8 to 8/8 comparable to Floyd-Steinberg and the 6 other Classic dithers offered by Bmp2DHR.

For DHGR color dithering, increasing Atkinson works best. But for monochrome conversion Atkinson’s reduced color bleed does a better job.

Command Option “R” – Reduced (or Increased) Color Bleed

Color bleed reduction and increasing is supported for all 8 of the Classic error diffusion dithers in Bmp2SHR. An increased color bleed is achieved by reducing the color bleed by a negative value.

As previously noted, reducing the color bleed by minus 33% allows us to “normalize” Apple Computer’s Atkinson dither in an equivalent manner to the 7 other Classic dithers in Bmp2DHR. Reducing the color bleed of the 7 other Classic dithers by 25% allows them to match Atkinson’s generally better results for monochrome dithering.

The GIMP has only 2 inflexible error diffusion dithering options; Floyd-Steinberg “normal” and Floyd Steinberg reduced color bleed. The GIMP does not allow you to specify values for color bleed reduction and seems to go a little “overboard”.

The GIMP – Floyd-Steinberg

Unspecified reduced color bleed

Bmp2DHR – Floyd Steinberg

25% color bleed reduction

Unlike Bmp2DHR’s reduced color bleed, The GIMP’s reduced color bleed is useless for monochrome DHGR conversion. It is not modeled after Atkinson like Bmp2DHR’s color bleed reduction or increase.

Jarvis

Stucki

Burkes

Sierra

25% color bleed reduction

The images above demonstrate the idea behind reducing color bleed in Bmp2DHR. Sierra Two and Sierra Lite are not shown; that’s enough already! Atkinson is not shown above, but here it is. Since Atkinson always uses a 25% color bleed reduction by comparison to the others, command option “R” is not needed for the equivalent Atkinson output:

The GIMP - Floyd-Steinberg “normal”

Bmp2DHR – Classic Atkinson

Summing-Up Monochrome Dithering in Bmp2DHR

Let’s take a farewell glance at the DHGR monochrome output from each of Bmp2DHR’s 8 dithers again using the image from Wikipedia’s dithering article: http://en.wikipedia.org/wiki/Dither

Zoom-in 200% or so and for the fun of it, and keeping in mind that the Bmp2DHR images appear exactly as they do on a real Apple II, look closely and you will see that Bmp2DHR does pretty well…

Now as for the others, that is left as an exercise for the reader.