Computationally Efficient Low-Artifact System for Spatially Filtering Digital Color Images

1. Field of the Invention

The present invention relates to spatial filtering of images that are represented by electronic signals compatible with a computer. More particularly, the invention concerns a computationally efficient system for spatially filtering an RGB input image to "sharpen" the image. The present invention enhances high frequency components of the image by extracting a luminance signal, processing the luminance signal, then modifying the image in accordance with the processed luminance signal.

2. Description of the Related Art

The primary colors of a color cathode ray tube ("CRT") result from the visible emissions of three different mixtures of phosphors, each of which can be independently excited by an electron beam. When an observer views the CRT from a proper distance, the observer's eyes cannot resolve the individual phosphor dots. Thus, the contributions of each of the three phosphors add together to create a combined spectrum, which the observer perceives as a single color. The intensity of light emitted from each phosphor is linearly related to the electron beam current of the CRT. Specifically, the light intensity is largely proportional to the electron beam current raised to the power of an exponent called "gamma". See, e.g., Foley & Van Dam, "Fundamentals of Interactive Computer Graphics," PC 1982, pp. 594-597. Gamma is the exponent to which an electron beam current must be raised to cause a phosphor on a computer monitor to emit light of a desired intensity. Accordingly, a CRT with a constant gamma for all three phosphors, viewed in a dark room, produces a color that can be described, in the color space of its primaries, according to Equation 1: ##STR1##

The level of current in an electron beam of a computer monitor is usually linearly related to the values stored in the display buffer. With the RGB values scaled into the range ›0,1!, if we wish to produce a color with tri-stimulus values in the color space of the monitor's primaries (R,G,B), then the beam current should be (R.sup.1/.sbsp..gamma., G.sup.1/.sbsp..gamma., B.sup.1/.sbsp..gamma.). This nonlinear RGB encoding is called "gamma-correcting". An image that has been gamma-corrected for a monitor with a gamma of 2.2 is referred to as itself having a gamma of 2.2, even though the corrective operation actually involves raising each component of each pixel in the image to the power of 1/2.2.

"Spatial filtering" encompasses various techniques concerned with processing multidimensional signals. In the field of computer graphics, image editors are used to carry out spatial filtering by changing the characteristics of a digital color image stored in computer memory. In this regard, an image editor may embody an executable process in a computer system or an integrated circuit that processes images displayed on a computer monitor.

RGB is one of the most common color spaces in digital image processing. In many graphics systems, RGB images are divided into three color planes: red, blue, and green. Image editors typically process RGB images by operating on a buffered array of pixels representing the image. As shown in FIG. 1, each pixel 100 includes three eight bit digital values 104-106 representing the intensity of the corresponding red, green, and blue pixel components, respectively. The signals corresponding to the pixels are stored in an image buffer 102 which is partitioned into three two-dimensional subparts 110-112 called "color planes". Each color plane 110-112 stores respective red, green, or blue components of all pixels in the array of pixels that forms an image.

The data storage arrangement of FIG. 1 is used by various image editors to perform spatial filtering. A primary goal of many spatial filters is the enhancement of certain image "contrasts" to achieve a "sharpening" effect. As shown by the flow diagram of FIG. 2, one example of such a spatial filter operates by subjecting each color plane of an RGB image to the same type of processing. This processing may involve, for example, convolution with a filter kernel. Such filtering is commonly used, for example, to sharpen or blur photographic or photo-realistic images, and to produce aesthetically pleasing effects. Table 1 (below) contains pseudocode corresponding to the technique of FIG. 2.

Although this technique provides some benefits, its usefulness is limited in certain applications. For instance, in some circumstances this technique produces objectionable artifacts, such as color "fringing" at object boundaries. Additionally, this technique changes the chromaticity of the image, depending on the amount of energy in each color plane that is within the filter's stopband. Since most sharpening applications aim to restrict changes to luminance, this effect is often undesirable.

FIG. 3 illustrates a flow diagram corresponding to a different type of sharpening filter, which processes one color plane to develop corrections for that plane, and subsequently adds the corrections for that plane to the other two planes. With this type of spatial filter, the first color plane may be processed by convolving the image of that plane with a filter kernel, as shown in FIG. 3.

Although the technique of FIG. 3 may be advantageous in some applications, it can alter the image in a manner that is undesirable for some users. Particularly, this technique changes the chromaticity of the image, depending upon the relative values of each color in each pixel location. The chief goal of most sharpening filters is to sharpen an image by changing the luminance of the image's pixels, while avoiding any changes to the image's chrominance. In a general sense, luminance refers to the brightness of a color, while chrominance concerns the color of an image regardless of its darkness or brightness. Therefore, since the approach of FIG. 3 changes an image's chrominance, it may not be appropriate for some applications.

Scientists have developed a variety of other color representations that endeavor to separately consider the image's chrominance and luminance. At first glance, the "YIQ" color space appears to have some benefits for use in spatial filters. The YIQ color space is a pseudo luminancechrominance color space, where Y represents an approximation to the luminance of a pixel. Using the YIQ color space is convenient for RGB-based images, since Y can be obtained from the RGB components of a pixel by combining them in predetermined proportions. However, the I and Q components encode other characteristics than chromaticity. Thus, operations in the YIQ color space change the chromaticity of the adjusted RGB intensity values, and the YIQ color space is not appropriate for most spatial filters.

To overcome the problems of YIQ, some scientists have considered the true luminance-chrominance color space "CIELAB". Although this approach may benefit some users, it comes with a high computation cost due to the complicated transformations between RGB and CIELAB. For another example of a spatial filter that operates in the chrominanceluminance color space, see Govrin, "Sharpening of Scanned Originals Using the Luminance, Hue and Saturation Coordinate System," Color Hard Copy and Graphic Arts III, SPIE vol. 2171, pp. 332-340. The Govrin approach, depicted in FIG. 4, first converts an input image to a color space that separates luminance from chrominance. Then, Govrin filters only the luminance component. In particular, Govrin converts an RGB image to a "CMYK" image, and then converts the CMYK image to an "LHS" image. Govrin then sharpens the LHS image, and then converts the sharpened LHS image back to CMYK.

Govrin's approach eliminates many of the color artifacts produced by the RGB processing methods. Nonetheless, Govrin's approach encounters limitations in certain applications. As discussed above, Govrin's approach involves three transformations: first to the CMYK color space, then to LHS, and then back to CMYK color space. Govrin may even require a fourth transformation for applications requiring conversion of the image back to the RGB color space. These transformations incur a significant computation cost, which may be manifested by excessive processing time. For applications in which processing time is critical, then, Govrin's technique might not be satisfactory.

The present invention concerns a computationally efficient system for spatially filtering a digital input image to sharpen the image. In one embodiment, the present invention comprises a process for spatially filtering pixels of an RGB input image by applying a high pass filter to the image. First, signals representative of luminance are extracted, then the image is filtered based upon the extracted luminance signals. Filtering may be achieved, for example, by applying a convolution filter to the luminance signals in accordance with an appropriate filter kernel. Then, the filtered signals are divided by the corresponding original luminance signals to yield quotient signals. Finally, the quotient signals are multiplied by the components of the input image to provide a filtered output image.

The present invention may also be embodied in an apparatus comprising an image editor configured to implement the spatial filtering process of the invention. The image editor of the invention may comprise various processors and RAM modules of a digital computer, circuitry of an ASIC, or components of another suitable hardware system.

The nature, objects, and advantages of the invention will become more apparent to those skilled in the art after considering the following detailed description in connection with the accompanying drawings, in which like reference numerals designate like parts throughout, wherein:

FIG. 1 is a diagram of a known structure of image buffer 100;

FIG. 2 is a flow diagram of a known spatial filtering process that processes each color plane separately;

FIG. 3 is a flow diagram of a known spatial filtering process that filters one color plane and processes the remaining color planes by adding the corrections obtained from the first plane;

FIG. 4 is a flow diagram of a known spatial filtering process that operates in the luminance-chrominance color space;

FIG. 5 is a diagram of the hardware components and interconnections of an illustrative construction of an image editing system 500 in accordance with the present invention;

FIG. 6 is a diagram of a computer-readable diskette 600 for use in implementing one embodiment of image editor in accordance with the present invention;

FIG. 7 is a diagram of the hardware components and interconnections of an illustrative image editor 512 in accordance with the present invention; and

FIGS. 8-9 are flow diagrams illustrating various illustrative embodiments of the process of the present invention.

In an illustrative embodiment, the present invention may be practiced in the physical context of the hardware components and interconnections of FIG. 5. Specifically, FIG. 5 illustrates an image editing system 500 that includes a computer 502. The computer 502 preferably comprises a general-purpose personal computer such as an IBM brand RS/6000 model computer. Although not shown, the structure of the computer 502 includes one or more processors, random access memory ("RAM"), direct access memory, and other suitable components.

The computer 502 includes an input image buffer 504 to store a multiplicity of pixels representing a digital color image. In an illustrative embodiment, the buffer 504 may utilize a configuration such as the image buffer 102. The buffer 504 receives its contents from an input device 506, which may comprise a variety of different hardware components. For example, the input device 506 may comprise a video camera, a digital scanner, or another suitable device to provide a digital color image for processing. In an illustrative embodiment, the input device 506 provides an output comprising a sequence of digital data packets, each packet including three eight-bit numbers representing the magnitudes of the red, green, and blue components of a pixel. In an illustrative embodiment, the buffer 504 assembles the sequence of digital data packets into three color planes such as shown in FIG. 1. Alternatively, the input data may originate from a direct access storage device ("DASD") 508, from which stored images are retrieved using an input-output ("I/O") channel 510.

The computer also includes an image editor 512. In one illustrative embodiment, the image editor 512 comprises a software product comprising a sequence of instructions that define functions that the image editor is to execute, along with workspace contents resident in the RAM of the computer 502, and one or more process control structures. In this embodiment, the image editor 512 may be implemented by a processor (not shown) that executes a series of computer-executable instructions that reside, for example, in RAM (not shown) of the computer 502, in the DASD 508, or in another suitable storage location of the computer 502. Alternatively, the instructions may be contained on a data storage medium, such as a computer-readable diskette 600 (FIG. 6), DASD array, magnetic tape, conventional "hard drive", electronic read-only memory, optical storage device, paper "punch" cards, or another data storage device. In an illustrative embodiment of the invention, the computer-executable instructions may comprise lines of compiled "Smalltalk" language code, or another language such as C.

Alternatively, the image editor 512 may comprise an application-specific integrated circuit ("ASIC") embodying customized logic and other resources that execute the functions of the image editor, as described below. In whatever form, the image editor 512 edits images by processing signals stored in the input image buffer 504, and transferring the processed signals to an output image buffer 514. Signals from the output image buffer 514 are conventionally fed to drivers 516 that produce, on signal lines 518, the red, green, and blue analog signals necessary to drive an output device 520. The output device 520, in an illustrative embodiment, comprises a video monitor such as a CRT monitor, LCD screen, or another suitable gamma-corrected RGB graphics monitor. The output device may instead comprise a color printer, color projector, or another suitable output apparatus.

An interactive interface to the image editor 512 is afforded by user-manipulated input devices such as a mouse 522 and keyboard 524 that are connected to the image editor 522 by a standard peripheral interface 526.

As described above, one embodiment of the image editor 512 may be implemented using an arrangement of circuit components, which may advantageously be embodied by an ASIC. This embodiment is illustrated in greater detail by the ASIC circuit 700 of FIG. 7. The circuit 700 includes input image buffers 702-704 to receive the red, green, and blue components of the pixels stored in the input image buffer 504. For each pixel stored in the buffer 504, the input image buffers 702-704 provide the corresponding red, blue, and green signals to a multiplexer 706. In response to a selector input (not shown), the multiplexer 706 selects a red, green, or blue signal from the input image buffers 702-704 and provides an output of the selected signal. In this way, the multiplexer 706 implements time-sharing of the circuitry 700, rather than requiring separate circuitry for processing signals from each color plane.

The multiplexer's output signal is directed to a lookup table 708, which creates a linearized signal by removing any nonlinearity present in the signal. In an illustrative embodiment, the lookup table 708 may comprise a table of pre-calculated conversions to translate from gamma-corrected input signals to signals without gamma correction. Where signals are represented by eight-bit numbers, the lookup table 708 may comprise, for example, a table that implements the relationship shown below in Equation 2.

where:

OUT represents a linear output signal between zero and 255;

IN represents the nonlinear input signal between zero and 255; and

.gamma. represents gamma.

The lookup table 708 directs its signal to a luminance signal extractor 710, which comprises a multiplier 712, an adder, 714, and a buffer 716. The multiplier 712 first multiplies linearized signals corresponding to color components of a pixel by pre-prepared coefficients 713 to create product signals. Then, the adder 714 sums the product signals to yield a signal representing the luminance of the pixel originally received from the input image buffers 702-704.

Luminance signals from the buffer 716 are fed to a filter 718, which includes a convolution operator 720 and a buffer 722. For each luminance signal, the convolution operator provides a filtered signal by convolving the luminance signal with luminance signals corresponding to certain other pixels in accordance with a pre-prepared filter kernel 724. The filtered signals are stored in the buffer 722.

Each filtered signal is directed to a divider 724, which divides the filtered signal by the original luminance signal, to provide a quotient signal. A second lookup table 726 then creates a nonlinear signal by non-linearizing the quotient signal. The nonlinear signal is preferably created based upon a complementary relationship to Equation 2 (above). Next, a multiplier 728 multiplies component signals of each original input pixel by the correction signal to yield sharpened output signals. A demultiplexer 730 directs each sharpened output signal to the output image buffer 732-734 corresponding to the appropriate red, green, or blue color plane, as appropriate.

In an alternative embodiment, the output image buffers 732-734 may be eliminated, and the input image buffers 702-704 used to serve a dual purpose. In another embodiment, the multiplexer 706 and demultiplexer 730 may be replaced with additional multipliers and lookup tables (not shown). Such modifications are readily understood by a skilled artisan having the benefit of this disclosure.

Another aspect of the present invention comprises a process, which may be performed -by the image editing system 500 described above. The process to be applied depends upon which color representation is desired for processing of the input image. The flow diagram of FIG. 8, for example illustrates a series of tasks performed upon luminance signals generated under the CIE Yxy scheme of representation. This scheme uses the well-known CIE chromaticity diagram having two dimensions (x and y) that define the chromaticity of a color and a third dimension, Y, that establishes brightness. Therefore, any color can be defined according to the CIE diagram by a triplet (Yxy). Each component of the triplet may be assigned a value on the CIE diagram and the values are combined to yield the color. According to the CIE scheme, reference may be made to the xy chromaticity of the pixel and to the Y luminance of the pixel.

In a general sense, the process 800 spatially filters the stored image to visually sharpen the features of the image. Item 802 represents the stored digital color input image, which has been received previously from a source such as the input device 506. The image is preferably stored in the buffer 504, although it may be stored in another location such as the DASD 508. The image is stored according to an RGB scheme, such that the stored signals comprise nonlinear representations. To process the image in accordance with the invention, task 803 first linearizes the pixels of the entire input image or a selected part, and provides the linearized signals for use by task 804. Task 804 extracts a luminance signal Y, in accordance with the CIE Yxy color scheme. Since different luminance signals are developed for each pixel of the input image, the luminance signal may be considered as an array of individual values. Luminance signals may be extracted in task 804 for all pixels of the input image. Alternatively, task 804 may extract luminance signals for a selected portion of the input image.

Each luminance signal is generated based upon the stored red, green, and blue pixel component signals. This may be achieved using one of several different approaches, depending upon the type of RGB representation used to store the pixel signals in the input image buffer 504. For SMPTE-C type RGB, each luminance signal may be developed using the approximation of Equation 3 (below):

where:

Y represents a linear luminance signal corresponding to the input pixel; and

R, G, and B represent linearized signals corresponding to the red, blue, and green components of the input pixel.

Other approaches may be used instead to extract the luminance signal. If the input image is stored according to the CCIR 709 RGB standard, the luminance signal is developed according to Equation 4 (below):

After task 804 extracts the luminance signal, task 805 filters it. In an illustrative embodiment, this may be accomplished by performing convolution in task 806 with a kernel previously constructed in task 808. The kernel comprises an array of coefficients, which are used to selectively weight the luminance signal by luminance signals corresponding to other selected pixels, such as certain neighboring pixels, of the image. In an illustrative embodiment, the kernel comprises an array of values that may range from negative one to two or three. Construction of an appropriate kernel is within the abilities of an ordinarily skilled artisan having the benefit of this disclosure. However, an exemplary kernel is shown below in Table 2.

Alternatively, the filtering may be accomplished by adjusting luminance signals after correcting them to a frequency-based domain using a method such as "transform domain processing", the "Hadamard" method, or another suitable technique. For example, Fourier transforms may be employed to aid in the filtering of task 805. If Fourier transforms are used, the image is processed by: (1) using Fourier transform to convert the luminance signals extracted from the input image into a frequency-based domain, (2) filtering the converted image by applying certain mathematical operations to the image, and (3) applying inverse Fourier transform to convert the filtered image back to the original domain. In this embodiment, the filtering may be accomplished by simply by changing the high frequency pixel components to zero, or by scaling them, for example. Task 805 may be performed by a number of other techniques, as well, such as known methods of morphological filtering. As known in the relevant art, morphological filtering modifies a graphic image using skeletonization, dilation, and erosion. See, e.g., Pratt, "Digital Image Processing", 2nd edition, 1991.

After task 805 produces filtered luminance signals, task 810 normalizes each signal by dividing it by the original luminance signal corresponding to the same pixel, thereby yielding a quotient signal. Then, task 811 applies gamma correction to the quotient signal, yielding a corrected quotient signal. The corrected quotient signal indicates the amount, if any, by which the luminance of each pixel in the image must be increased or decreased. Accordingly, task 812 multiplies each corrected quotient signal by the components of the corresponding input pixel to create a new image, whose luminance varies as that of the filtered luminance signal.

In addition to the flow diagram 800 of FIG. 8, the invention may also be illustrated by a sequence of pseudo code. Two alternate embodiments of such pseudo code sequences are shown below in Tables 3 and 4.

An exemplary embodiment of the present invention was constructed to test the operation of the present invention. To perform the test, the hardware arrangement of FIG. 5 was implemented using an IBM brand RS/6000 model computer. The flow diagram of FIG. 8 was implemented using the "IBM Image Assistant" software package. Specifically, programming instructions were written in "script" form, then executed to carry out the tasks of FIG. 8. The input image was stored under the SMPTE-C RGB format, and luminance was generated using the CIE Yxy color space, as discussed above in conjunction with FIG. 8. This test employed a kernel of seven rows and seven columns, as shown below in Table 5 (below):

The number of add, multiply, and divide operations needed to process an input image were counted, each operation being performed on an eight bit integer, and the results were normalized to represent the operations required for processing one pixel. Table 6 (below) illustrates the results of this test.

For comparison, a conventional image editor was constructed using the hardware and software mentioned above, and each plane was processed separately according to the flow diagram of FIG. 2. Table 7 (below) illustrates the computational cost of this method, per pixel of the input image.

As shown above by Tables 6-7, the tested embodiment of the present invention required 135 less operations than the conventional approach. This precise difference in computational efficiency, however, would be expected to vary from FIGS. 2-3 depending upon the particular filtering technique that is used. Smaller kernels, for example, may yield a smaller difference in efficiency, whereas larger kernels may result in a larger difference.

The invention affords its users with a number of distinct advantages. Chiefly, the invention provides an image editor that implements a spatial filter that is significantly less computation-intensive than known arrangements. As a result, the invention operates with increased speed and efficiency, freeing computer resources to perform other functions.

Moreover, the invention provides more accurate results than many prior arrangements having the same speed. An image sharpened in accordance with the invention, for example, carries hue angles that closely correspond to those of the original image. In particular, when an image is processed in accordance with the present invention, the chroma of the image increases where the filtered image is brightened, and decreases where the filtered image is darkened, as would occur if light falling on the object represented by the image were increased or decreased. As a result, the processed image provides a natural and visually-pleasing effect.

Another advantage of the invention is that it does not change the proportion of red, green, and blue coloring for each pixel, since the three color planes are all multiplied by the same amount for each pixel. This is true even if the pixels in the input image are stored in gamma-corrected RGB format. This occurs because multiplying a linear representation by an original constant and then gamma-correcting the product produces the same results as multiplying a gamma-corrected representation by a different constant, as shown below in Equations 5-7:

where:

k is the original constant;

k.sup..gamma. is the different constant; and

R', G', and B' represent values of red, green, and blue for a pixel.

While there have been shown what are presently considered to be preferred embodiments of the invention, it will be apparent to those skilled in the art that various changes and modifications can be made herein without departing from the scope of the invention as defined by the appended claims.

For example, other luminance signals may be extracted, in contrast to computation of CIE Yxy described above. For example, luminance may be measured in accordance with the CIELAB, CIELUV, CIEXYZ, YC.sub.r C.sub.b, the YIQ, or another appropriate standard. Another useful approximation of luminance is the value Y' defined by the well-known NTSC standard. FIG. 9 shows a flow diagram 900 that employs the NTSC representation scheme for luminance. This diagram 900 is similar to the flow diagram 800 for CIE Yxy in many respects. However, luminance (Y') is extracted in task 901 without requiring any linearizing of the signals of the stored input image. Luminance may be extracted, in an illustrative embodiment, according to the approximations of Equations 8-12, below.

where:

Y' represents gamma-corrected luminance; and

R', G', and B' represent gamma-corrected value of red, green, and blue, respectively.

If desired, the extracted luminance signals may be processed in task 902 to remove their nonlinearities prior to filtering. However, this step is optional, and omission of task 902 may yield acceptable results for some applications, with little or no degradation in performance. If task 902 is performed, the flow diagram 900 also includes task 904, which performs gamma-correction to introduce the nonlinearities removed in task 902.

Those skilled in the art, however, will appreciate that NTSC luminance Y' is not the CIE Yxy luminance "Y" discussed above. Some other luminance approximations are described in U.S. Patent application Ser. No. 08/329,040, which was filed on Oct. 25, 1994 now abandoned in the name of the present inventor, and is hereby incorporated herein by reference in its entirety.