Features
FeaturesLookup tables are fast but not very intuitive. A small software assist can turn friendlier data into tables.
Introduction
Digital image manipulation is becoming a commonplace activity today, and is now a routine operation on platforms ranging from the hospital CT machine to the desktop computer. Contrast enhancement operations are the backbone of these image processing packages. Contrast operations, through some sort of lookup table, allow an operator to selectively enhance some visual aspects of an image while suppressing other aspects. From a programmer's point of view, lookup tables are quite versatile and efficient in applying contrast enhancment. From a user's point of view, however, lookup tables are hard to work with. This article presents a way to use lookup tables that is both user friendly and efficient.
This article deals only with the contrast enhancement of gray-scale images, but lookup table operations can be applied effectively to color images as well. The short discussion at the end of this article presents other uses for lookup operations involving color. In terms of gray-scale images, the main elements of contrast enhancement are the input image, which is a matrix of brightness values; a transformation function; and the output image, an equally-sized matrix whose brightness values are appropriate for use on some display channel. Contrast enhancement consists of feeding values from the input matrix to the transformation function, to produce a corresponding set of new output values.
This transformation function can involve clipping of values above and below certain ranges; spreading values across the device's available contrast range; complex transformations such as a logarithmic curve that spreads low values while compressing higher values into a smaller contrast range; or completely arbitrary processes such as the piecewise stretch, which contains a series of ranges and spreads values linearly between them. Figure 1 shows an example of the kinds of transformations possible.
Lookup Tables
The lookup table sits between the image matrix and the display channel. Using the table, the program processes each value of the matrix before the data is copied across to a color channel. This provides control over the range of values that appear on a screen.
The simplest form of lookup table is an array indexed by the matrix value. The mapping between input and output is one-to-one; each element of the array contains the transformed value for that index. The problem with using a table like this — just a set of entries — is that once it is set it is hard to modify without rewriting the whole table. The easiest way to deal with such a table is to just write a few standard algorithms that manipulate the table as a whole and leave it at that.
The piecewise lookup table provides a more visual approach and lends itself to easy, interactive modification. The piecewise lookup table (LUT) can be visualized as a simple x,y plot (Figure 2b). The x-axis of the graph represents the input values (the raw data) while the y-axis values are the output or displayed values. The plot consists of line segments joining a series of control points. Each of these points defines a pair of values: input (x) and required output (y). In the region between each pair of points, the output varies as a linear function of input. Each region (the piece in ``piecewise'') provides a different linear transformation function, which ensures that when a given x-value within the region is transformed, the resulting y value lies on the line segment between the two endpoints.
The user of a piecewise lookup table need define only the control points. The software can then generate the transformation functions required for each region between these points. These relatively few points are much easier to modify than the numerous values in a simple one-to-one lookup table. However, the process of transforming an input value to an output value becomes more complicated, and thus slows down the process of iterating through an input matrix to produce a display.
An even better way to handle table lookups is to combine both the piecewise lookup approach and the simple one-to-one table approach. The user works with the piecewise lookup table, adjusting the transformation applied in each piece simply by moving the control points. The software then generates a one-to-one transformation table from the piecewise lookup table. When the image transformation is actually performed, the transformation procedure uses the simpler and more efficient one-to-one table.
This is the approach I took in designing my table lookup software. It displays a plot of the piecewise lookup table, with an added convenience: it can also superimpose a plot of an image's histogram on the plot of the piecewise lookup table. Histograms are a fundamental tool in contrast enhancement. They contain all the information applicable to the selection of a lookup table transformation. An image histogram is a plot of image values against their relative frequency of occurrence. In this case, the values are plotted on the x-axis, and their relative frequency is scaled and plotted on the y-axis.
Lookup Table Code
The code consists of two main classes: ImageLut and ImagePointLut. ImageLut (Listing 1) is a simple one-to-one eight-bit lookup table. It holds and manipulates a table of numbers and provides procedures to convert data sets. Values can be converted individually with the [] operator or as an array with ImageLut::Lookup (Listing 2) .
ImagePointLut (Listing 3) is a piecewise lookup table which derives its table operations from ImageLut. ImagePointLut holds and manipulates a series of control points within a linked list. The contents of this list follow certain constraints. For example, points can't overlap, because that would give multiple output values for a single index value. So the points must be sequential across the x-axis. The list must also have a point at either end of the x-axis, 0 and 255, so all possible index values are covered.
ImagePointLut::Update converts the point list from a series of transformation ranges into a one-to-one table held by ImageLut. To do this, Update first calls SortPointList. SortPointList checks the list of points to make sure that limits are not exceeded, x values are sequential, and that the list covers all possible values of x. If the Boolean argument to Update is true, it then calls TidyPointList. TidyPointList is an optional routine to remove points that are very close together or redundant. (A redundant point is one which lies upon a straight line between its neighbors.) TidyPointList is usually called internally when a number of points have been added automatically by a function. Many of these points may be redundant, and calling TidyPointList keeps the number of points to a minimum. Finally, Update scans through the tidied up point list, passing adjacent pairs of points in turn to ImageLut::ScaleTo. The ScaleTo function converts the transformation range represented by the pair of points to a set of one-to-one lookup table values, which it stores in ImageLut's lookup table.
ImagePointLut includes a set of standard functions for creating different lookup tables and manipulating points (Listing 4) . The simplest is SetMinToMax, which uses statistics from ImageHist to find the minimum and maximum image values and inserts these points in the table. Optimise is similar to SetMinToMax except that it adds a mean value, positioning the mean at the central contrast position. Other routines such as SetLog and SetExp approximate logarithmic or exponential curves across the given ranges.
ImagePointLut::Equalize is a histogram equalization routine. It inputs an image histogram and uses this information to try to spread an equal percentage of intensities across each contrast range. This routine is different from the other routines mentioned in that it directly manipulates the underlying ImageLut object. Equalize first fills ImageLut's table and then builds ImagePointLut's point list from the table by calling ImagePointLut::BuildPointList.
Most of the routines presented here have two versions: one in which the ranges are specified, and one in which the routine takes the information required from an ImageHist object. An ImageHist is a histogram of the image. It stores the frequency of each intensity value in the image and uses this set of frequencies to compute a series of univariate statistics. OptimiseMinMax uses this information to modify the minimum and maximum positions, shifting them toward the center by 5% to avoid problems with a small number of high or low values taking up the available contrast ranges.
A Sample Application
The sample application presented here is a simple MS-Windows program that loads and displays a single-channel gray-scale image and allows editing of the lookup tables via a dialog window. This application can be split into three parts: the Microsoft Foundation Classes (MFC) windowing architecture, the image manipulation and display routines, and the dialog control interface. Due to space constraints, I can only describe the code here, but the full source code is available on the CUJ ftp site. (See p. 3 for downloading instructions.)
MFC Architecture
The MFC windowing architecture is a fairly standard document-view arrangement. The document holds all the image specific information, handing it out to the different view windows on demand. CDisplayView is a CScrollView class, which handles painting of the window, printing, and mapping of the images' palette. RealizePalette is a Windows system function, which maps a logical palette to the system-wide palette entries. If there aren't enough colors to go around then it will match the image's colors to the closest colors available. RealizePalette is called when one of the display windows are activated or the system palette changes outside of the application's control. The application receives messages reflecting such a change through the main frame window procedure, via functions OnQueryNewPalette and OnPaletteChanged. The main frame window procedure relays these messages to all opened windows.
Image Processing Functions
All image manipulation is handled within the CDisplayDoc class, which is derived from the MFC CDocument class. CDisplayDoc's OnOpenDocument function takes a filename as a parameter. The function creates an Image object, and then passes the Image's open function the filename. The Image object attempts to open the file, and checks and loads the image header information. This application handles only Targa format — truecolor 24-bit and eight-bit gray-scale images.
OnOpenDocument creates a device independent bitmap (DIB) by creating an object of class ImagePsColDib, which is derived from an ImageDib object. ImageDib wraps all the handling of the DIB, and creates and handles a palette for the image. A Windows DIB consists of a BITMAPINFOHEADER and BITMAPINFO structure. The former contains the bitmap's formatting information. The latter contains the bitmap itself, which is made up of an array of pixel values of the size specified by the header (1, 4, 8, or 24 bits per pixel). For the purposes of this article I use only a 8-bit, palette-indexed bitmap.
ImagePsColDib's CreateDib function takes an Image object as a parameter, creates a device independent bitmap, and copies each line into the bitmap via ImageDib::Set. By default, CreateDib will read the blue channel of a color image. The copying process does not use lookup tables or attempt to apply contrast enhancement. The contrast enhancement step actually occurs in the creation of the image's palette, when the system sends a pixel from the DIB to the display. The system palette then will contain an optimized equivalent of the lookup tables maintained by ImagePsColDib.
ImagePsColDib holds three lookup table objects, one for each output color channel. To produce a gray (hueless) image, each component (red, green, and blue) of the color must be of equal intensity, so we set each lookup table accordingly. ImagePsColDib::UpdateDib uses these three lookup tables (red, green and blue) to set the palette for the image. The application must optimize this palette, since in some screen modes MS-Windows can have only 256 or fewer colors to be shared across many applications. In fact, for this application the colors must be shared across multiple windows within one application. Microsoft's Windows documentation suggests optimizing the usage of available colors by placing the most important colors — those appearing most frequently — at the lower end of the palette. This is the function of ImagePsColDib's Optomise function.
Optomise inputs a histogram, sorts it into a sequence from most-used values to least, and creates a lookup table. It then transforms the loaded bitmap, moving the most-used entries to lower positions in the palette list. This gives the most important colors the highest priority: the system sees and allocates them first, setting colors not used to black. Even after this process, the situation is by no means an optimum, as vital colors can still be missing in the background windows. I have noticed that a few software packages give up altogether on trying to share the palette, assigning their background windows a small gray-scale palette to avoid colors shifting about with palette changes.
Lookup Table Editing Dialog
EditLut is a form view containing the edit lookup table controls. It holds information about which channels are being edited ( red, green, blue, or all) and changes made to the lookup tables. EditLut does not make modifications to the displayed image until requested via the Apply button. When the button is pressed, CDisplayDoc::UpdateBitmap creates a new image from any changes made to the lookup tables and passes this on to all of the documents's child views. Child views are informed about changes through their Update routine.
LineControl subclasses a control within the dialog, redirecting and handling all of the controls' messaging, mouse movements, and repainting events. LineControl also contains a bitmapped backdrop to its window, which contains a grid and grayed-out histogram of the image. This histogram is plotted to the bitmap by graphing routines in ImageHistPlot, which automatically scale and plot the information.
LineControl passes information on mouse movements and other events on to an ImageLineControl object, which manages a point list similar to ImagePointLut's. Given a copy of the lookup table object (ImagePointLut), ImageLineControl coverts between control coordinates and lookup table coordinates, storing selections and changes, and drawing the information when requested.
Further Uses for Lookup Tables
The normal way to create a black to white gray-scale image is to map the same matrix to each color channel, giving each point on the display an equal intensity in red, green, and blue. However, it is possible to use a different technique to exploit a property of human vision: the human eye can resolve more color hues than shades of gray. In this technique, known as pseudocolor display, the order of hues (colors) in the spectrum represents values in the matrix.
In pseudocolor display low values appear not as black, but as shades of blue; central values not as gray but green; and high values appear as orange or red. Producing a pseudocolour display involves manipulating the matrix before it is copied to each display channel. The blue channel gets inverted matrix values, so 255 from the matrix becomes 0 in the blue channel, and 0 becomes 255. The green channel values are re-scaled so that 0 becomes 0, 128 becomes 255 and 255 becomes 0 again. The red channel is unchanged. This is just one of the uses of lookup tables.
In general, a digital image may contain more than one matrix of brightness values. Lookup tables allow these values to be mapped to display channels in a variety of combinations so as to best facilitate the visualization and understanding of data. o
Bibliography
M.E. Mortenson. Computer Graphics, an Introduction to Mathematics and Geometry (Heinemann/Newnes).
Microsoft Windows Programmer's Reference Version 3.0 (Microsoft Press, 1990).
David J. Kruglinski. Inside Visual C++ (Microsoft Press, 1993).
Microsoft Visual C++ 4.1 Documentation.
Conrad Dare-Edwards works for the Digital Imaging Group, Charles Sturt University, where he has developed a number of applications. He is also a partner in MC Software, and can be reached at cdare-edwards@csu.edu.au or at his home page on http://www.mcsoftware.com.au.