CONVERTING DITHERED IMAGES BACK TO GRAY SCALE
Undithering algorithms for image enhancement
Allen Stenger
Allen is a programmer for a large radar house. He may be reached on CompuServe (70401, 1171) or on AppleLink (Stenger).
Most printing uses only black ink, which does not allow shades of gray to be represented directly. Therefore, pictures in traditional halftoning are represented by a grid of variable-sized black dots, with thicker dots used for the darker areas. The eye blurs the dots and the white area between them, so we perceive shades of gray, though the picture still contains only black and white.
Computer printers and monitors usually don't have variable-sized dots, so digital halftoning (colloquially called "dithering") uses the cruder method of representing shades of gray by various patterns of fixed-sized black dots. For example, 50 percent black might be shown by a checkerboard pattern of black and white dots or pixels. Because of the loss of information in going from 8-bit pixels to 1-bit pixels, dithering is intended to be the last step before printing or displaying. Image-enhancement techniques, even the simplest ones, such as contrast enhancement, usually do not work on dithered images. Dithered images are widely available on BBSs and networks, but the original image (which you might like to have for display on a gray-scale monitor or to enhance in some way) is usually not available. The loss of information in dithering generally makes it impossible to recover the original image from a dithered image, but there are ways to "undither" a dithered image into a reasonable 8-bit reconstruction of the original image. Figure 1(a), for example, shows a 256-gray-scale photograph; Figure 1(b) shows it in Floyd-Steinberg dither (discussed below); and Figure 1(c) shows a reconstruction from Figure 1(b) using the methods described in this article.
Dithering Methods
The two most common methods are ordered dither and Floyd-Steinberg dither. Ordered dither uses a cleverly chosen set of black-and-white patterns (usually 8x8 squares of pixels) to represent the different gray-scale levels. (The use of ordered dither can be recognized by the characteristic crosshatch patterns that this set generates.) The dithering algorithm first divides the image into a grid of 8x8 squares. If each square had a constant gray level, it would be easy to dither. (Just use the pattern having the closest average gray value.) Since the squares are rarely constant, the algorithm uses a thresholding scheme to replace each gray pixel with a black or white pixel: For each pixel, imagine that the whole square did have that gray level, look up the correct pattern, and replace the pixel with the same-position pixel from the pattern. OrderedDither in Listing One (page 133) implements ordered dithering.
While ordered dither processes each pixel independently (so in theory all pixels could be processed in parallel), Floyd-Steinberg (F-S) dither (see Floyd-SteinbergDither in Listing One) is a serial method that avoids the artifacts (characteristic crosshatches) of ordered dither and does a better job of representing fine lines. (The use of F-S dither can be recognized by the characteristic snaky patterns occurring in almost-black or almost-white areas.) F-S is an error-diffusion method that processes the pixels of each scan line from left to right and top to bottom. Each pixel is examined and rounded to black or white. For example, if it was rounded to black, then the picture is now too black, and we compensate for this by making the neighboring gray pixels a little lighter (we diffuse the error) so that the sum of all the pixels' gray values is unchanged. Specifically, the pixels neighboring to the east, south, southeast, and southwest are adjusted. Floyd and Steinberg empirically distributed more of the error to some pixels than others; they used the weights:
0 x 7/16 3/16 5/16 1/16
where x is the pixel under consideration.
Computerized Blurring
The reason halftones and dithering work is that the eye blurs the dots into shades of gray, so the first step in undithering is to mechanically smooth or blur the image. The human eye does this without using any complicated mathematics, but computers need an algorithm.
I processed the images in Figure 1 with NIH Image, a widely available public-domain image processing and analysis program written and distributed in source form (Think Pascal) by Wayne Rasband at the National Institutes of Health. NIH Image, which runs on the Mac II, provides most needed transforms, and allows the addition of user-written subroutines for specialized processing. (Because of its size, NIH Image is available only electronically; see "Availability" on page 5.)
Computerized blurring is done by replacing each pixel's value with the average of the pixels in a small region around it. (In NIH Image each pixel's gray value is represented by a number from 0 to 255, with 255 representing black.) NIH Image has a built-in smooth function, which averages a 3x3 square centered at the pixel. The important grays of 50 and 25 percent black dither into checkerboard patterns; applying the smooth function to them produces a gray checkerboard instead of a constant gray, because an odd number of pixels is being averaged. A 4x4 square averages an even number of pixels and produces exactly the right gray level from these checkerboards. It also seems to produce better results in undithering, so the first step is to blur the dithered image with a 4x4 square.
To get a 4x4 average, you can use the convolve function. The word "convolve" literally means "roll together," and a convolution rolls together the pixels in a region as a weighted average and places it in the center pixel. The user-provided convolution kernel is just an array of weights for the pixels. For a 4x4 average, we therefore use the convolution kernel:
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Smoothing also has the desirable feature of increasing the number of gray levels present. From a gray-scale viewpoint, the largest deficiency of a dithered image is that it has a drab two levels of gray, not the rich 256 levels of the original picture. It is this lack of variety that prevents image enhancements from working on dithered images.
Adaptive Smoothing
For Floyd-Steinberg dither, the first step by itself usually produces an almost-realistic gray-scale image, and you could stop there. The two most obvious imperfections of the first step are that the picture often looks mottled and that the smoothing has blurred some details. The mottling occurs because there are not enough grays in the gray scale (only 17 shades compared to the original 256), causing a continuous shading of gray to be mapped into discrete and visibly different grays.
Smoothing blurs indiscriminately. We would like to smooth out the mottled areas without disturbing the high-contrast areas that represent the edges of objects. We can do this with an optimal filtering technique, Lee's local-statistics method (see "Optimal Estimation"). This method does what we want by providing a variable amount of smoothing in different regions of the picture. This is implemented as a user subroutine in NIH Image (LeeLocalStatistics in Listing One). For F-S dither, a 3x3 smoothing works well. To obscure the more blatant patterns in ordered dither, a 5x5 smoothing works better, although it also blurs more details of the picture.
Finishing Touches
The third enhancement is to recover some details that have been blurred by the previous two stages. For this we apply a mild sharpening filter. Sharpening filters are also convolutions; the convolution kernel we use is:
-1 -1 -1 -1 50 -1 -1 -1 -1
(Be sure to turn off Scale Convolutions in the Preferences to prevent the contrast from being reduced.) Sharpening is the opposite of smoothing, and we can only do a little without undoing the effects of the previous smoothings.
The result is shown in Figure 1(c). It is a little blurred, but is otherwise a good likeness of the original.
References
Bryson, Jr. Arthur E. and Yu-Chi Ho. Applied Optimal Control. Waltham, MA: Blaisdell, 1969.
Floyd, Robert and Louis Steinberg. "An Adaptive Algorithm for Spatial Gray Scale." Society for Information Display Digest (1975).
Judice, C.N., J.F. Jarvis, and W.H. Ninke. "Using Ordered Dither to Display Continuous Tone Pictures on an AC Plasma Panel." Proceeding of the Society for Information Display (1974).
Knuth, Donald E. "Digital Halftones by Dot Diffusion." ACM Transactions on Graphics (October, 1987).
Lee, Jong-Sen. "Digital Image Enhancement and Noise Filtering by Use of Local Statistics." IEEE Transactions on Pattern Analysis and Machine Intelligence (March, 1980).
Optimal Estimation
Optimal estimation is a group of statistical methods for solving the problem of making a "best guess" of a measured parameter's true value when the measurement is corrupted by "noise" (a random, undesired addition to the value of interest). It is widely used in control applications like radar tracking. With dithering, you can use it to estimate the true gray levels of a picture that has been corrupted by dithering.
After the first stage of our undithering process we have a picture with 17 gray levels, and we know the original picture had 256 gray levels. The most optimistic interpretation of the 17-level picture would be that each original gray level had been rounded to the nearest of the 17 gray levels. (The picture has been "posterized.") The difference between the original value and the rounded value is the noise.
Lee's local statistics method uses a least-mean-squares estimator. To apply this method, we need estimates of the mean and variance of both the true signal (the original picture) and the noise (the error introduced by dithering and blurring). The optimal estimate (see Bryson and Ho) is: estimate=mean + gain* (observed value-mean)=gain* observed value+(1-gain)* mean value, where the gain is calculated as: local variance/(local variance+noise variance).
None of these means or variances is known to us directly; we can estimate the mean and variance of the original picture at each point by calculating the mean and variance of a small square centered at the point in the blurred picture. (These are the "local statistics," as opposed to "global statistics" that would be calculated for the entire picture.) We can estimate the mean and variance of the noise as follows: Since the 17 gray levels are spaced every 16 grays, the maximum error from rounding would be 8, and the error function would be a uniform distribution from -8 to +8. The mean is therefore 0 and the variance is 16**2/12 = 256/12, or about 21. Since the picture really went through the even more corrupting process of dithering, we would expect the true variance to be somewhat larger, and experimentation shows that 150 produces good results in the algorithm.
Note that the gain is always between 0 and 1 (inclusive), so the estimate is a weighted average of the observation and the mean. If the local variance is small compared to the noise, the gain is close to 0 and we use mostly the mean value. (This is because a small local variance suggests that the noise is the source of most of the variation, and we therefore wish to cancel it out by averaging.) If the local variance is large compared to the noise, the gain is close to 1, and we use mostly the observed value. (This suggests that most of the variation is due to true differences in the gray levels and little is due to noise, so we essentially ignore the noise and believe the observed value is very close to the true value.) --A.S.
[LISTING ONE]
Copyright © 1992, Dr. Dobb's Journal<a name="026a_000c">
unit User;
{ This is an addition to, and incorporates parts of, the NIH Image program. }
{ NIH Image is written by Wayne Rasband at the National Institutes of Health }
{ and is in the public domain. This addition was written by Allen Stenger, }
{ March 1992. Written in THINK Pascal version 4.0.1. }
{ Replace the User.p supplied with Image with this one. Be sure to uncomment }
{ the call to InitUser in Image.p. If you have a small display you may need }
{ to use ResEdit to shorten the names of the other menu items in Image.rsrc }
{ so the User menu (which comes last) won't be pushed off the end. Use }
{ ResEdit to modify the User Menu in Image.rsrc to make the items Lee Local }
{ Statistics, Ordered Dither, Floyd-Steinberg Dither. }
{ Algorithm references: }
{ Ordered dither: C.N. Judice, J.F. Jarvis, and W.H.Ninke, "Using }
{ Ordered Dither to Display Continuous Tone Pictures on an AC Plasma }
{ Panel." Proceeding of the Society for Information Display v. 15 }
{ no. 4 (Fourth Quarter 1974), not paged. Reprinted in: John C. }
{ Beatty and Kellogg S. Booth (editors), Tutorial: Computer }
{ Graphics, 2nd edition. Silver Spring, MD: IEEE Computer Society }
{ Press, 1982, pp. 220-228.}
{ Lee local statistics: Jong-Sen Lee, "Digital Image Enhancement and }
{ Noise Filtering by Use of Local Statistics." IEEE Transactions on }
{ Pattern Analysis and Machine Intelligence, v. PAMI-2, no. 2 (March }
{ 1980), pp. 165-168. Reprinted in: Rama Chellapa and Alexander A. }
{ Sawchuk (eds.),Digital Image Processing and Analysis v. 1. Silver }
{ Spring, MD: IEEE Computer Society Press, 1985, pp. 440-443. }
interface
uses
QuickDraw, Palettes, PrintTraps, globals, Utilities, Graphics, Analysis,
Camera, Functions;
procedure InitUser;
procedure DoUserMenuEvent (MenuItem: integer);
implementation
type
UserFilterType = (LeeLocalStats, OrderedDither, FloydSteinbergDither);
procedure InitUser;
begin
UserMenuH := GetMenu(UserMenu);
InsertMenu(UserMenuH, 0);
DrawMenuBar;
end;
{ Most of UserFilter is copied with minor modifications from Image (procedure }
{ Filter in Functions.p). The new parts are the Lee local statistics and }
{ ordered dither code. Floyd-Steinberg dither is copied from Filter. }
procedure UserFilter (filterType: UserFilterType);
const
PixelsPerUpdate = 5000; { controls screen updating }
{ constants for Lee local statistics method }
NoiseVariance = 150; { empirical value for Lee method }
{ constants for ordered dither }
DitherSize = 8; { dimensions of ordered dither matrix }
DitherSizeMinus1 = 7; { ditto minus 1 }
type
DitherPattern = array[0..DitherSizeMinus1, 0..DitherSizeMinus1] of 0..255;
var
{ general variables for this procedure }
row, width, r1, r2, r3, c, value, error, sum, tmp, center: integer;
mark, NewMark, LinesPerUpdate, LineCount: integer;
MaskRect, frame: rect;
L1, L2, L3, result: LineType;
pt: point;
AutoSelectAll, UseMask: boolean;
StartTicks: LongInt;
{ variables for Lee local statistics method }
localVariance: longint;
localMean: longint;
gain: real;
i: integer; { loop control }
{ variables for ordered dither }
thePattern: DitherPattern;
procedure PutLineUsingMask (h, v, count: integer;
var line: LineType);
var
aLine, MaskLine: LineType;
i: integer;
SaveInfo: InfoPtr;
begin
if count > MaxPixelsPerLine then
count := MaxPixelsPerLine;
GetLine(h, v, count, aline);
SaveInfo := Info;
Info := UndoInfo;
GetLine(h, v, count, MaskLine);
for i := 0 to count - 1 do
if MaskLine[i] = BlackIndex then
aLine[i] := line[i];
info := SaveInfo;
PutLine(h, v, count, aLine);
end;
procedure MakeDitherPattern (var p: DitherPattern);
var
row: 0..DitherSizeMinus1;
column: 0..DitherSizeMinus1;
halfsize: 1..DitherSize;
scaleFactor: 1..256;
begin
{ The pattern is defined recursively; we implement the recursion }
{ as an iteration. }
p[0, 0] := 0;
halfsize := 1;
while halfsize < DitherSize do begin
for row := 0 to halfsize - 1 do
for column := 0 to halfsize - 1 do begin
p[row, column] := 4 * p[row, column];
p[row, column + halfsize] := p[row, column] + 2;
p[row + halfsize, column] := p[row, column] + 3;
p[row + halfsize, column + halfsize] := p[row, column] + 1;
end;
halfsize := halfsize * 2;
end;
{ adjust scaling for pixel ranges 0..255 }
scaleFactor := 256 div SQR(DitherSize);
for row := 0 to DitherSizeMinus1 do
for column := 0 to DitherSizeMinus1 do
p[row, column] := scaleFactor * p[row, column] + scaleFactor div 2;
end; {MakeDitherPattern}
begin
if NotinBounds then
exit(UserFilter);
StopDigitizing;
AutoSelectAll := not Info^.RoiShowing;
if AutoSelectAll then
with info^ do begin
SelectAll(false);
SetPort(wptr);
PenNormal;
PenPat(pat[PatIndex]);
FrameRect(wrect);
end;
if TooWide then
exit(UserFilter);
ShowWatch;
if info^.RoiType <> RectRoi then
UseMask := SetupMask
else
UseMask := false;
WhatToUndo := UndoFilter;
SetupUndoFromClip;
ShowMessage(CmdPeriodToStop);
frame := info^.RoiRect;
StartTicks := TickCount;
{Set up for ordered dither }
if filterType = OrderedDither then
MakeDitherPattern(thePattern);
with frame, Info^ do begin
changes := true;
RoiShowing := false;
if left > 0 then
left := left - 1;
if right < PicRect.right then
right := right + 1;
width := right - left;
LinesPerUpdate := PixelsPerUpdate div width;
GetLine(left, top, width, L2);
GetLine(left, top + 1, width, L3);
Mark := RoiRect.top;
LineCount := 0;
for row := top + 1 to bottom - 1 do begin
{Move Convolution Window Down}
BlockMove(@L2, @L1, width);
BlockMove(@L3, @L2, width);
GetLine(left, row + 1, width, L3);
{Process One Row}
if CommandPeriod then
exit(UserFilter);
case filterType of
LeeLocalStats:
for c := 1 to width - 2 do begin
localMean := (L1[c] + L1[c + 1] + L1[c + 2]
+ L2[c] + L2[c + 1] + L2[c + 2]
+ L3[c] + L3[c + 1] + L3[c + 2]) div 9;
localVariance := 0;
for i := 0 to 2 do begin
localVariance := localVariance + SQR(L1[c + i]
- localMean);
localVariance := localVariance + SQR(L2[c + i]
- localMean);
localVariance := localVariance + SQR(L3[c + i]
- localMean);
end;
localVariance := localVariance div (3 * 3);
if OptionKeyWasDown then { do extra smoothing }
gain := localVariance /
(localVariance + NoiseVariance * 16.0)
else
gain := localVariance / (localVariance + NoiseVariance);
result[c - 1] :=
round(localMean + gain * (L2[c + 1] - localMean));
if result[c - 1] > 255 then
result[c - 1] := 255;
if result[c - 1] < 0 then
result[c - 1] := 0;
end; {LeeLocalStats}
OrderedDither:
for c := 1 to width - 2 do begin
if L2[c + 1] >=
thePattern[row mod DitherSize, c mod DitherSize] then
result[c - 1] := 255 { dither to black pixel }
else
result[c - 1] := 0; { dither to white pixel }
end; {OrderedDither}
FloydSteinbergDither:
for c := 1 to width - 2 do begin
value := L2[c + 1];
if value < 128 then begin
result[c - 1] := 0;
error := -value;
end
else begin
result[c - 1] := 255;
error := 255 - value
end;
tmp := L2[c + 2]; {A}
tmp := tmp - (7 * error) div 16;
if tmp < 0 then
tmp := 0;
if tmp > 255 then
tmp := 255;
L2[c + 2] := tmp;
tmp := L3[c + 2]; {B}
tmp := tmp - error div 16;
if tmp < 0 then
tmp := 0;
if tmp > 255 then
tmp := 255;
L3[c + 2] := tmp;
tmp := L3[c + 1]; {C}
tmp := tmp - (5 * error) div 16;
if tmp < 0 then
tmp := 0;
if tmp > 255 then
tmp := 255;
L3[c + 1] := tmp;
tmp := L3[c]; {D}
tmp := tmp - (3 * error) div 16;
if tmp < 0 then
tmp := 0;
if tmp > 255 then
tmp := 255;
L3[c] := tmp;
end; {FloydSteinbergDither}
end; {case filterType}
if UseMask then
PutLineUsingMask(left + 2, row, width - 3, result)
else
PutLine(left + 2, row, width - 3, result);
LineCount := LineCount + 1;
if LineCount = LinesPerUpdate then begin
pt.h := RoiRect.left;
pt.v := row + 1;
NewMark := pt.v;
with RoiRect do
SetRect(MaskRect, left, mark, right, NewMark);
UpdateScreen(MaskRect);
LineCount := 0;
Mark := NewMark;
if magnification > 1.0 then
Mark := Mark - 1;
if CommandPeriod then begin
UpdatePicWindow;
beep;
if AutoSelectAll then
KillRoi;
exit(UserFilter)
end;
end;
end; {for row:=...}
trect := frame;
InsetRect(trect, 1, 1);
ShowTime(StartTicks, trect, '');
end; {with}
if LineCount > 0 then begin
with frame do
SetRect(MaskRect, left, mark, right, bottom);
UpdateScreen(MaskRect)
end;
SetupRoiRect;
if AutoSelectAll then
KillRoi;
end;
procedure DoUserMenuEvent (MenuItem: integer);
begin
case MenuItem of { User menu must be set up in this order }
1:
UserFilter(LeeLocalStats);
2:
UserFilter(OrderedDither);
3:
UserFilter(FloydSteinbergDither);
end;
end;
end.
