Graphic system for displaying images in gray-scale

What is claimed is:

1. A computer-controlled method for building an inverse luminance table in a memory of a computer graphics system, wherein the inverse luminance table accepts as an address input luminance values and provides as a data output index information for indexing a luminance lookup table stored in said memory, said luminance lookup table containing luminance values to be displayed on a display of said graphics system, the method comprising the steps of:

converting first color information to a first luminance value using a transformation function;

initializing an array of data elements, each of the data elements for storing the index information, wherein each of the data elements corresponds to a color position on a line in a color space ranging from a minimum luminance value for a minimum luminosity to a maximum luminance value for a maximum luminosity;

storing a first index value in the array, the first index value corresponding to an index for the luminance lookup table, wherein the first index value is stored in a first data element of the array of data elements, the first data element corresponding to a color represented by the first index value in the luminance lookup table;

storing an address of the first data element in a queue for later processing;

for a second of the data elements, the second of the data elements logically next to the first data element in luminosity along the line in the color space;

(a) determining whether the second data element has been assigned an index value;

(b) if the second data element has not been assigned an index value, assigning the second data element the first index value and storing an address for the second data element on the queue.

2. The method as recited by claim 1, further comprising repeating steps (a) and (b) for a third data element, the second and third data elements being logically to the left and right in luminosity of the first data element along the line in the color space.

3. The method as recited by claim 2, wherein an index value for each luminance in the luminance lookup table is stored in the array and the queue prior to processing the second data element.

4. The method as recited by claim 3, wherein steps (a) and (b) are repeated for each address in the queue.

5. A computer graphics system including a display, said graphics system further having:

a first transformation circuit translating a first color information to a first luminance value, said first color information being associated with a display position;

a first memory coupled to said first transformation circuit and storing a first table, the first table providing a first index value in response to receiving said first luminance value from said first transformation circuit;

a second memory coupled to said first memory and having a plurality of storage locations corresponding to a plurality of display positions, said second memory storing the first index value at a location associated with said display position; and

a third memory coupled to said second memory and storing a second table, the second table providing luminance information in response to receiving the first index value corresponding with a storage location of the first index value.

6. The graphics system of claim 5, wherein the first color information comprises twenty-four bits of color information.

7. The graphics system of claim 6, wherein the twenty-four bits of color information comprise eight bits of red color information, eight bits of green color information and eight bits of blue color information.

8. The graphics system of claim 5 wherein the luminance information indicates colors lying along a diagonal in three dimensional RGB color space, the diagonal ranging from a minimum value indicating minimum luminosity to a maximum value indicating maximum luminosity.

9. The graphics system of claim 5, wherein the first luminance value comprises eight bits of information and the first index value comprises four bits of information.

10. The computer graphics system of claim 5 wherein said first transformation circuit includes:

first means for receiving said first color information and extracting a first red, a first blue and a first green color information from said first color information;

second means coupled to said first means for generating a first product of said first red color information and two;

third means coupled to said first means for generating a second product of said first green color information and four; and

fourth means coupled to said first, second and third means for generating a sum of said first product, second product, and said blue color information, said first luminance value included in said sum.

11. The computer graphics system of claim 10 further comprising fifth means coupled to said fourth means for generating a dividend from said first luminance value and seven, and for storing said dividend into said first luminance value.

12. The computer graphics system of claim 11 wherein said second means and said third means each comprise a register which has a means for shifting a value stored in said register by one bit and by two bits.

13. The computer graphics system of claim 12 wherein said fifth means comprises a register which has a means for shifting a value stored in said register by four bits.

14. The computer graphics system of claim 5 wherein said first transformation circuit includes:

first means for receiving said first color information and extracting a first red, a first blue and a first green color information from said first color information;

second means coupled to said first means for generating a first product of said first red color information and five;

third means coupled to said first means for generating a second product of said first green color information and nine;

fourth means coupled to said first means for generating a third product of said first blue color information and two, and

fifth means coupled to said second, third and fourth means for generating a sum of said first product, second product, and said third product, said first luminance value included in said sum.

15. The computer graphics system of claim 14 wherein said fourth means comprises a register which has a means for shifting said register by one bit.

16. The computer graphics system of claim 14 further comprising sixth means coupled to said fifth means for generating a dividend from said fast luminance value and sixteen, and for storing said dividend into said first luminance value.

17. A method for providing luminance mapped graphics in a computer graphics system, comprising the steps of:

providing the graphics system with a first color information;

converting the first color information to a first luminance value using a transformation function;

addressing a first memory including a first table with the first luminance value, the first table providing an index value in response to the addressing; and

storing the index value and using said index value to address a second table which outputs a second luminance value for display in said computer graphics system.

18. The method of claim 17, wherein the first color information comprises a red component, a green component and a blue component.

19. The method of claim 18, wherein the transformation function comprises computing the sum of products of the red component and five, the green component and nine, and the blue component and two of the first color information.

20. The method of claim 19 wherein said computing is performed using a shift operation and an add operation.

21. The method of claim 19, wherein the transformation function further comprises dividing the sum of the products by sixteen.

22. The method of claim 18, wherein the transformation function comprises computing the sum of the following:

a product of the red component and two,

a product of green component and four; and

the blue component of the first color information.

23. The method of claim 22, wherein the transformation function further comprises dividing the sum of the products by seven.

24. The method of claim 22 wherein said computing is performed using a shift operation and an add operation.

25. A method of manipulating colors in a computer graphics system using luminance information, comprising the steps of:

providing the graphics system with a first color information corresponding to a display position;

converting the first color information to a first index value;

providing said first index value to a luminance lookup table;

providing a first luminance value from the luminance lookup table responsive to providing the first index value;

transforming a second color information to a second luminance value using a transformation function, and performing an operation on the first luminance value in conjunction with the second luminance value; and

generating a third luminance value responsive to performing said operation on the first luminance value in conjunction with the second luminance value.

26. The method of claim 25, further comprising the step of providing the third luminance value to an inverse luminance table, the inverse luminance table providing a second index value responsive to being provided the third luminance value.

27. The method of claim 25, wherein the first index value is stored in a first pixel location in a frame buffer.

28. The method of claim 27, wherein the second index value replaces the first index value being stored in the first pixel location in the frame buffer.

29. The method of claim 28, wherein the operation comprises adding the first luminance value to the second luminance value.

30. The method of claim 28, wherein the operation comprises subtracting the second luminance value from the first luminance value.

31. The method of claim 28, wherein the operation comprises blending the first luminance value with the second luminance value.

Description Submit all comments and votes

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to the field of displays for computer systems and, more specifically, to the field of graphical presentation and drawing systems displaying images in gray-scale.

2. Description of Related Art

A number of methods of presentation of color information to display devices are well known in the art. In general, such display devices may be divided into two categories: rod-green-blue (RGB) devices and NTSC or similar devices. In an RGB device, color information is presented to a display as three separate units of color information; a first unit of information representing the intensity of the red color gun of the display, a second unit representing the intensity of the green color gun of the display and a third unit representing the intensity of the blue color gun of the display.

NTSC devices (and their equivalents under other standards such as PAL) present color information to a display generally by phase-shifting a waveform some predetermined number of degrees from a reference signal. The color display, such as a television set interprets color based on the number of degrees the waveform is out of phase with the reference. Such systems may further control the intensity of the color by controlling the amplitude of the color signal.

In the RGB color system, a display may be controlled by presenting bits of color information to drive digital-to-analog converters which in turn produce three analog color signals which control the red, green and blue guns of a display. Typically, 24 bits of color information may be used; 8 bits representing red, 8 bits representing green and 8 bits representing blue. Using 24 bits of color information allows over 16 million (2.sup.24) colors to be produced.

In a typical computer system employing a color display, a device called a "frame buffer" is utilized. A frame buffer is a memory for storing color information corresponding to each pixel on the display. A frame buffer may store 24 bits of information per pixel and the 24 bits of information may be used to directly control the color display. Such a system is typically termed a direct color system. However, use of a full 24 bit frame buffer requires a large amount of memory space and leads to other processing inefficiencies. As an example of the amount of memory space required, many known displays, such as a display which may be utilized with the Macintosh II, available from Apple Computer, Inc. of Cupertino, Calif., have displays comprising 640.times.480 pixels.

It is known to utilize a frame buffer having less than 24 bits of color information per pixel. Such a system may store for example 1, 2, 4, or 8 bits per pixel for color presentation. The bits of information from the frame buffer are used to address a color lookup table (CLUT). The data outputs of the CLUT are the RGB colors signals or their digital equivalents. The use of the CLUT offers a number of advantages. For example, less memory may be used for a frame buffer and colors on the display may be adjusted by adjusting the data content of the CLUT. So, an image represented using a full 24 bits may be displayed on a system having only 8 bits available for display.

Alternatively, some systems may represent images in gray-scale. Gray-scales are sometimes represented as a luminance values. Luminance values are those that range from minimum luminosity (black) to maximum luminosity (white). It can be appreciated that any value of gray depending on the number of bits used to represent the color may be represented between these minimum and maximum values. In an RGB color display system representing gray-scale images, equal intensities or values of red, green and blue are used to represent the corresponding gray or luminance value. A color system using 24 bits may be used for gray-scale images where the red, green and blue values are equal, providing 256 shades of gray (eight values of red, green and blue or 2.sup.8). In addition, color images may be represented in their corresponding gray-scale using a transformation function.

In one prior art approach as shown on FIG. 1, 24 bit RGB color information 102 may be used as an address input to a color lookup table 101. However, as shown on FIG. 1, use of the full 24 bit RGB color information field would require a color lookup table with an address space of 2.sup.24 entries of four bits each for each index. Such a large table is generally not desirable in a computer system as a large amount of computer main memory is consumed.

SUMMARY AND OBJECTS OF THE INVENTION

One objective of the present invention is to develop gray-scale graphics capable of producing image-quality graphics, i.e. the ability to display a reasonable likeness of a black and white photograph in a microcomputer system, or showing a color image in a gray-scale mode.

A second objective of the present invention is to avoid speed and performance degradation in the computer system for users not utilizing such image quality graphics. For example, a user utilizing a word processing system has little need for high quality gray-scale graphics.

A third objective of the present invention is to allow a user to cut graphics created in a first graphic mode and paste the graphics into a display created in a gray-scale graphic mode.

A fourth objective of the present invention is to provide image-quality black and white graphics while not degrading speed and performance of the computer system for users not utilizing such image-quality black and white graphics. In meeting this objective, the present invention discloses use of hardware and software means which support a number of different gray-scale modes on a display ranging from a monochrome mode where only two color (black and white) may be displayed, to a mode where numerous intermediate gray-scale values ranging from black to white may be displayed simultaneously. In modes which support fewer gray-scale values, speed may be maximized since less memory must be manipulated. In the full gray-scale mode, image-quality black and white graphics may be achieved while having a cost tradeoff against speed.

The present invention relates to the field of graphics systems for computers and has specific application to presentation of gray-scale images on gray-scale output devices or color devices operating in gray-scale mode in graphics systems. Color information is translated to a luminance value. The luminance value is then used to lookup an index value in a table. The index value may be stored in a frame buffer or otherwise used by the computer system. In the present invention, index values stored in the frame buffer may be used to address a luminance lookup table which provides luminance information for a display or other device.

The present invention further discloses a method for creating a luminance-to-index table (an "inverse luminance" table) which provides for seeding an array with luminance information from a luminance lookup table. Each "seed" in the array is then grown outward and data elements adjoining the seed are associated with the same luminance as the seed from the luminance lookup table. This method of the present invention offers speed and processing efficiency advantages over methods of calculating distances between points in the array to determine assignment of luminance values.

Utilizing the inverse luminance table of the present invention, color graphics may be created in a color mode and displayed in a gray-scale mode. The graphics, when displayed in the gray-scale mode, will provide an approximation of the luminance of the colors as originally created.

The present invention further provides a method for arithmetically manipulating luminance values for display.

BRIEF DESCRIPTION OF DRAWINGS

The present invention is illustrated by way of example and not limitation in the figures of the accompanying in which like references indicate like elements and in which:

FIG. 1 is a block diagram illustrating a prior art color lookup table.

FIG. 2 is a block diagram showing a computer system as used in the preferred embodiment.

FIG. 3 is a diagram illustrating red-green-blue (RGB) color space and a diagonal from the origin (minimum luminosity) to maximum luminosity for representation of images in gray-scale.

FIG. 4a is a block diagram illustrating the inverse luminance table and related circuitry in the preferred embodiment.

FIG. 4b shows a block diagram of an alternative embodiment using an inverse luminance table.

FIG. 5 is an illustration of a point along a diagonal in RGB space showing the point and its orientation to its neighboring points.

FIG. 6 is a flowchart illustrating a method used by the preferred embodiment for initializing an inverse luminance lookup table.

FIG. 7 is a diagram illustrating a first-in, first-out queue as may be used by the preferred embodiment for initializing the inverse luminance lookup table.

FIG. 8 is a data flow diagram illustrating arithmetic operations on luminance data which may be performed by the preferred embodiment.

FIG. 9 is a data flow diagram illustrating various operations which may be performed on luminance data in the preferred embodiment.

DETAILED DESCRIPTION

Gray-scale imagery in computer systems is described. In the following description, numerous specific details are set forth such as number of bits, etc., in order to provide a thorough understanding of the present invention. It will be obvious, however, to one skilled in the art that the present invention may be practiced without these specific details. In other instances, well known circuits, structures and techniques have not been described in detail in order to not unnecessarily obscure the present invention.

INTRODUCTION

Gray-scale imagery performed by the preferred embodiment may be implemented in the Macintosh II Color Quick Draw system available from Apple Computer, Inc. of Cupertino, Calif., although any image processing system of similar or greater capability may be used. Image-quality gray-scale graphics in a microcomputer environment for systems using either gray-scale or color representations of data is described.

The preferred embodiment uses hardware and software means which support a number of different gray-scale modes on a display ranging from a monochrome mode where only two colors (black and white) may be displayed, to a mode where many intermediate gray-scale values ranging from black to white may be displayed simultaneously. In modes which support fewer gray-scale values, speed may be maximized since less memory must be manipulated. In full gray-scale mode, image-quality black and white graphics may be achieved while having a cost tradeoff against speed.

A user may dynamically change gray-scale modes to tailor gray-scale and speed capabilities of the system to suit the user's immediate requirements. Sometimes a user wishes to cut graphics created in one application and paste the graphics into another application. The user of a Macintosh.RTM. brand computer system may cut graphics from a display by marking the graphics to be cut using any one of a number of methods and selecting a cut function. Alternatively, the user may mark the selection and select a copy function. The copy function leaves the original display intact. In either case, a copy of the graphics are kept in what is termed the user's clipboard. The user may then change applications and paste the graphics from his clipboard into the new application. The preferred embodiment allows graphics which may have been created in, for example, image quality mode to be displayed in another mode such as one of these intermediate modes. In the graphics system of the preferred embodiment, the capability is provided for mixing of luminance values which are a display or to be displayed with other luminance values. A user may wish to blend two gray-values, add two gray-values together or subtract one gray-value from another. These functions are known as "arithmetic transfer modes."

THE COMPUTER SYSTEM USED BY THE PREFERRED EMBODIMENT

The computer system of the preferred embodiment is described with reference to FIG. 2. The preferred embodiment may be implemented on a general purpose microcomputer, such as one of members of the IBM Personal Computer brand computer family, a member of the Apple Macintosh.RTM. brand computer family, or one of several work-stations or graphics computer devices which are commercially available. Of course, better image quality and system performance is provided for by systems having a relatively high-speed processor. Of course, the present invention may also be implemented on a multi-user system while encountering all of the cost, speed and function advantages and disadvantages available with these machines.

Computer system 200 of the preferred embodiment generally comprises a bus or other communication means 201 for communicating information, a processing means 202 coupled with bus 201 for processing information, a random access memory (RAM) or other dynamic storage device 204 (commonly referred to as a main memory) coupled with bus 201 for storing information and instructions for said processor 202. Further a read only memory (ROM) or other static storage device 206 is coupled to bus 201 for storing static information and instructions for said processor 202. A data storage device 207, such as a magnetic disk and disk drive, is coupled to bus 201 for storing information and instructions, and a display device 221, such as a cathode ray tube, liquid crystal display, etc., is coupled to bus 201 for displaying information to the computer user. An alphanumeric input device 222 including alphanumeric and other keys is coupled to said bus 201 for communicating information and command selections to said processor 202, and a cursor control device 223, such as a mouse, track ball, cursor control keys, etc., is coupled to bus 201 for communicating information and command selections to said processor 202 and for controlling cursor movement. It is useful if system 200 includes a hardcopy device 224, such as a printer, for providing printouts of information from system 200. Hardcopy device 224 is coupled with the processor 202, main memory 204, static memory 206 and mass storage device 207 through bus 201.

Processor 202 used in the preferred embodiment is a MC68020 microprocessor manufactured by Motorola Corporation of Phoenix, Ariz. System 200 is a Macintosh.RTM. II brand computer system running the Macintosh.RTM. brand operating system.

It will be apparent, from the description of the preferred embodiment which follows, that several of the above-mentioned components of the computer system of the preferred embodiment are not essential to operation of a computer system employing the present invention. For example, the hardcopy device 224 may not be coupled to system 200. A device such as hardcopy device 224 may be useful in the preferred embodiment for purposes such as obtaining printouts of computer programs for documents, but is not essential for use of the system.

Much of the software for implementing the preferred embodiment is written in 68020 assembly language. Of course, other operating systems and programming languages could be selected in alternative embodiments. For instance, an object-oriented high-level programming language, such as C.sup.++ is desirable for a number features of such languages such as the use of class (or type) hierarchies.

RGB COLOR REPRESENTATION

As background to describing the preferred embodiment, a description of RGB color space is useful. The RGB color model is based on the principle that radiated color is composed of a mixture of red, green and blue light. Visible colors are the result of varying mixtures of these three primary color components. For example, mixing equal amounts of the full intensity of the primary colors creates white light, mixing green and red light created yellow, absence of all components creates black, etc. Theoretically, any visible color can be represented using an RGB triple.

As shown by FIG. 3, RGB color space can be represented as a three dimensional cube 300 with each of the colors, red, green and blue, represented by one of the cube's axis, 301, 302, or 303, respectively. Any arbitrary color may be represented by a point somewhere in the cube. For example, point (0,0,0) 310 may represent the lack of all color components and corresponds with the color black. Point (1,1,1) 311 represents the maximum intensity of all color components and results in the color white. Points (1,0,0) 312, (0,1,0) 313, and (0,0,1) 314 represent maximum intensity of each of the three primary colors and lack of the other two color components resulting in the colors red, green and blue, respectively. In a gray-scale system, all shades of gray which may be represented lie along a diagonal 315 in RGB color space such that each color is represented by an equal intensity of each of the red, green and blue components. The diagonal 315, as shown in FIG. 3, is a line segment running from the origin 310 (0,0,0) or minimum saturation (black in the additive color model) to maximum saturation (white) at point 311 (1,1,1).

It is worth noting that the color model used for devices which radiate light, such as those used in conjunction with the preferred embodiment, may be termed on additive color mode. Other color models, such as a subtractive color model used for media which absorbs light, follow different rules and may utilize different "primary" colors. However, the preferred embodiment's methods and apparatus may be equally applicable to other color models.

In the preferred embodiment, RGB colors are specified using 24 bits of color information shown as bits 402 in FIG. 4a. The 24 bits of color information 402 comprise 8 bits of red color information 405, 8 bits of green color information 406 and 8 bits of blue color information 407. Within each of the red, green and blue color fields, 405, 406 and 407 respectively, the value is treated as binary fraction. The range of each value is from 0.0 to approximately 1.0, where 0.0 represents absence of the color and 1.0 represents the maximum value of the color component. The actual data in the field is the fractional part of the actual value with the leading zero implied.

INVERSE LUMINANCE TABLE

As shown in FIG. 4a, the preferred embodiment utilizes a luminance value transformation function 409 to convert a three 8 bit RGB values 305, 306 and 307 into one 8 bit luminance value. This function multiplies the red component 305 (8 bits) of the 24 bit RGB value by 5, the green value 306 by 9 and the blue value 307 by 2 dividing the sum of the three results by 16. It can be appreciated by one skilled in the art that these arithmetic operations may be accomplished with little CPU overhead by combinations of register shift operations and additions instead of multiplies and divides. This transformation results in an 8 bit luminance value provided on line 410 which has 2.sup.8 or 256 possibilities. The result of this transformation function may then be used as an input into an abbreviated inverse luminance table (ILT) 411. Use of a luminance value transformation function for each color requires that the ILT 411 only have an address space of 2.sup.8 or 256 entries of four bits each.

In an alternative embodiment, a transformation function may be used which multiplies the red component of the color by 2, the green component by 4 and uses the blue component unmodified. The sum of these three values is divided by 7, generating a resulting luminance value. In this transformation function, it is possible to eliminate the divide operation if the values are already normalized to 7 (or 16 in the above example). It will be appreciated by one skilled in the art that various types of transformation functions may be applied to RGB value 402, and these are contemplated within the spirit and scope of the invention.

The dam output transmitted over line 412 from ILT 411 comprises four bits of index information to be stored in a frame buffer or otherwise used in computer system 200. The index information may be used to address a luminance lookup table (LLUT) to generate luminance signals for display in gray-scale.

An alternative ILT scheme is disclosed with reference to FIG. 4b. ILT 411 in FIG. 4b is addressed by an 8 bit luminance value 455 provided on lines 453 and provides as data output a four bit index value on line 412. In a system using a scheme as represented in FIG. 4b, values may be represented only as luminance information in the system and require no transformation function 409 as shown in FIG. 4a. The ILT may be considered to be a one-dimensional array of index values which correspond to luminance values that may be generated from the RGB color input information. Each output value transmitted on line 412 represents an index for a color having the same intensities of red, green and blue or a luminance value, which may be transmitted to a display 221 as shown in FIG. 2.

CONSTRUCTION OF THE INVERSE LUMINANCE TABLE

The preferred embodiment further provides a method for constructing an inverse luminance table. In constructing an inverse luminance table, one objective is to construct the table using as few of the computer resources as possible and to construct it as quickly as possible. In general, an ILT such as 411 cannot be precalculated and saved in a memory device or on disk because the available system gray-scales may be changed at any time. For example, when available system gray-scales are changed each time the number of bits of information used to represent a pixel stored in the indexed frame buffer is changed. As previously described, the number of bits per pixel may be changed when switching from application to application in a multitasking environment or at such other time as may be desired. For instance, when a user is operating in a word processing program and does not require image quality graphics, fewer bits per pixel can be used to represent an image. Also, the available system gray-scales may also be changed when the diagonal in RGB color space for gray-scales divided up in a different fashion. For example, rather than distributing all luminance values evenly along the diagonal for the ILT, emphasis may be placed on dark gray, or at the far end of the spectrum. Any change to the luminance lookup table will probably, but not necessarily, require rebuilding the inverse luminance table.

One method for building an ILT comprises generating a luminance value for a given color and calculating its distance from each value in the luminance lookup table. The luminance in the lookup table which is closest in distance to the calculated luminance value is selected as the index address to be stored in the inverse luminance table. Such a method ultimately requires a large number of calculations and substantial amounts of time.

The preferred embodiment uses an exponential solution to building the ILT which uses the diagonal 315 in RGB space shown in FIG. 3 that ranges from minimum luminosity to maximum luminosity. Generally, the method of the present invention utilizes a one-dimensional array of elements, simulating diagonal 315 on the RGB cube of FIG. 3, and a queue of elements to operate on. In concept, the present invention may be thought of as selecting each of the luminance values in the luminance lookup table and expanding the point along the diagonal space as if the point were smeared. When each of the "smears" in the luminance lookup table touch and cover all points along the diagonal, the points within each smear are assigned to the luminance in the luminance lookup table represented by the point from which the smear originated. The luminance lookup table already contains values according to a currently operating application on system 200 or initialization in some fashion.

In operation, this method is described in more detail with reference to FIGS. 5, 6, and 7. FIG. 6 shows a flowchart describing initialization process 600 for the inverse luminance lookup table (ILT) 411. An array representing points along the diagonal 315 in RGB color space as shown in FIG. 3 are set to initial values which indicates the points are not yet "owned" by a luminance at step 601 in process 600. Luminance values from the luminance lookup table are "seeded" into their appropriate positions into the array for the ILT at step 602. The seeding of the array comprises putting the addresses (indices) of each element of the luminance lookup table into the position in the array corresponding to the value represented by the value at that address (index) in the luminance lookup table. The RGB value is transformed, in the preferred embodiment, to a luminance value for the smear, in the manner discussed with reference to FIG. 4a to which lie in a range between 0 and 256. If the value is already repres