Abstract:
Instead of trying to minimize some cost function of color errors, the present invention exploits physical models of scene-image relations. An image is first segmented into regions corresponding to objects in the physical world. Each object is then painted with a few levels of shades of the same chromaticity. This is motivated by the observation that physical objects are the basic units for human visual perception. Chromatic variations within an object surface tend to be grossly discounted by our color vision, and therefore, it is not necessary to render those variations accurately. Furthermore, since the shading across an object surface spans a much smaller dynamic range as compared to the whole scene, the limited number of color shades can be more effectively used within a segmented image region.

Description:
A portion of the disclosure of this patent document contains material which is subject to copyright protection. The owner has no objection to the facsimile reproduction by anyone of the patent disclosure, as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights whatsoever. 
     FIELD OF THE INVENTION 
     The present invention is related to the field of image rendering and more particularly to the use of a luminance-chrominance histogram for image segmentation wherein each image segment is allocated a number of colors according to its size, busyness, and dynamic range. 
     BACKGROUND OF THE INVENTION 
     The trichromatic nature of human color vision requires three color primaries for reproducing color images. In the digital image processing art it usually takes 8 to 10 bits per color to render a high quality color image. However, there are many low-cost color monitors which have only 8-bit frame buffers. Although they have 8 or 10-bit digital-to-analog converters for the red, green, blue electron guns, and, given proper calibration, are capable of showing 2 24  or 2 30  colors, their frame buffers can only accommodate 8-bits per pixel thereby limiting the number of possible displayable colors at a given frame to 2 8  =256. With the help of a colormap lookup table (256 entries, each 24-bit deep), these 256 colors can be chosen from any of the 2 24  possible colors. The problem is how to choose the appropriate 256 colors to render a color image with the least objectionable artifacts. A number of methods have been proposed to solve the problem of 24-to-8-bit color reduction. These methods have been designed with explicit goals to minimize certain cost functions of colorimetric errors based on the statistical distribution of the colors in the input image. 
     The median-cut, the mean-cut, and the variance-based algorithms are typical examples of such error-minimization methods. The median-cut and the mean-cut algorithms were described by P. Heckbert, &#34;Color image quantization for the frame buffer display,&#34; Computer Graphics, 16, 3, 297-307, 1982. The variance-based algorithm was described by S. J. Wan, P. Prusinkiewicz, and S. K. M. Wong, &#34;Variance-based color image quantization for frame buffer display,&#34; COLOR research and application, 15, 1, 52-58, 1990. The basic idea behind all the three existing methods is to recursively partition the RGB color histogram into smaller and smaller sub-boxes so that each of the final 256 sub-boxes can be represented by its mean color without large errors. The three methods differ in how the sub-boxes are selected and partitioned. The median-cut and the mean-cut methods select the sub-box that has the largest dynamic range for further partitioning. The mean-cut algorithm partitions it at the mean value and the median-cut at the median value. In comparison, the variance-based method selects the sub-box that has the largest variance for further partitioning, and it partitions the sub-box at the point that produces the minimum sum of the variances of the resulting two smaller boxes. 
     Another variation of the above method is to form the color histogram in the &#34;uniform&#34; color space, such as CIELAB or CIELUV, so that the human perceptual error, rather than camera sensor error, is minimized. This was described by R. S. Gentile, J. P. Allebach, and E. Walowit, &#34;Quantization of color images based on uniform color spaces,&#34; Journal of Imaging Technology, 16, 1, 11-21, 1990. 
     Although the idea of minimizing color errors seems to be intuitively sound, the above mentioned solutions overlook the following empirical findings that can improve the color rendition even further: The world consists of separate objects whose surfaces reflect light in a way that could be approximated by some reflection models. The human visual system does not perceive the world as unrelated color patches that happen to fit into an image. Instead, it insists on interpreting the image as consisting of objects reflecting different color light. The consequence of this persistent cognitive interpretation is the tendency for us to ignore the color variations within an object surface and to emphasize those between different objects. Color errors are more difficult to see in a busy area than in a uniform area. The large dynamic range of a color scene is mainly due to illumination variations from one part of the scene to another. Luminance range across a surface is usually much smaller except when there is a shadow. Rendering an image region of an object surface thus requires much fewer levels of shades. 
     A patent of interest for its teaching is U.S. Pat. No. 4,907,075 entitled &#34;Method for Selecting Colors&#34; by G. W. Braudaway wherein an RGB histogram is formed and the most populated cell is selected as the representation color. The method then reduces the neighboring cell counts by an exponential function before it picks the next representation color. Another patent of interest is U.S. Pat. No. 5,049,986 entitled &#34;Method And Apparatus For Color Image Quantization&#34; by M. Aono et al. This patent relates to a data structure that allows a fast implementation of an algorithm similar to the one disclosed in the previous patent, U.S. Pat. No. 4,907,075. 
     SUMMARY OF THE INVENTION 
     Instead of trying to minimize some cost function of color errors, the present invention exploits physical models of scene-image relations. An image is first segmented into regions corresponding to objects in the physical world. Each object is then painted with a few levels of shades of the same chromaticity. This is motivated by the observation that physical objects are the basic units for human visual perception. Chromatic variations within an object surface tend to be grossly discounted by our color vision, and therefore, it is not necessary to render those variations accurately. Furthermore, since the shading across an object surface spans a much smaller dynamic range as compared to the whole scene, the limited number of color shades can be more effectively used within a segmented image region. 
     Two major components of the present method are a physics-based image segmentation algorithm and a psychophysics-based coloring algorithm. Based on models of light reflection, the image segmentation algorithm partitions the input image into regions that roughly correspond to different physical objects. The coloring algorithm renders the busy image regions with fewer luminance levels than the uniform image areas where shadings are subtle and errors easily visible. Many images rendered in 8-bits by this method have been compared with those rendered by other methods, such as the median-cut, the mean-cut, and the variance-based algorithms. The rendition by the present invention is shown to have the least contouring artifacts. Its good performance is consistent with the psychophysical finding that color is filled in to an image region from edges. 
     From the foregoing it can be seen that it is a primary object of the present invention to provide an improved method for displaying color images, particularly adapted for low-cost monitors. 
     A further object of the present invention is to provide a means for achieving a much improved rendition of color images using a few number of bits. 
     Another object of the present invention is to provide a technique for solving the 24-to-8-bit color reduction of an image. 
     These and other objects of the present invention will become more apparent when taken in conjunction with the following description and drawings wherein like characters indicate like parts and which drawings form a part of the present description. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 illustrates, in block diagram form, an apparatus for implementing the present invention. 
     FIG. 2 is a block diagram representation of the method of the present invention. 
     FIG. 3 is a block diagram representation of a segmentation algorithm. 
     FIG. 4 is a chrominance component axes graph (t and s), illustrating the relationship of a color c to a peak m. 
     FIG. 5 is a chart illustrating a luminance histogram and the representation of the mean level for each of the partitions of the histogram. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     FIG. 1 illustrates a system implementation of the present invention incorporating the object-oriented rendition algorithm, which can be used for displaying color images on a low-cost color monitor. An input color image 12 is digitized by any well known technique to provide red, green and blue signals each having a depth of 8 bits and representing a pixel of the original image. The three 8-bit code values are operated upon by an object-oriented rendition algorithm 14 which provides as outputs an 8-bit output to a monitor frame buffer 16 and an image-dependent lookup table that has 256 entries, each of which is 24-bits deep. The image-dependent lookup table is loaded into the monitor colormap lookup table 18 which is used to map the 8-bit code value of a pixel from the monitor frame buffer 16 into a 24-bit output value. The 24-bit output of the monitor colormap lookup table 18 is comprised of the red, green, and blue signals, each 8-bits in depth. These signals are converted from digital form to analog form by the D/A converters 22A, 22B and 22C and are directed to the control electrodes of a CRT color monitor 20. The 8-bit code value of a pixel in the monitor frame buffer 16 is used as an index to the colormap lookup table 18 to retrieve the 24-bit information that determines the color of the pixel displayed by the monitor 20. The 24-bit output from the monitor colormap lookup table 18 is divided into the three 8-bit signals that are converted to the analog voltages for driving the monitor 20. 
     Referring to FIG. 2 which is a block diagram that illustrates an implementation of the invention, the input color image 12 is first converted into an (L,s,t) color space in block 210, which will be explained later. The (L,s,t) image is then segmented into regions of different colors in block 220. Each image region corresponds roughly to an object. The next step, represented by block 230, is to determine how many colors should be allocated to an image region for coloring. In order to achieve good visual effect, the input image is converted into the output metric, block 230. For example, if the image is to be printed on paper, the output metric can be the Status A density. If the image is to be displayed on a monitor, then the image can be in gamma-corrected space to compensate for the non-linear distortion in the cathode-ray-tube. For each image region, the color-allocation algorithm computes indices that measures its dynamic range, busyness, area, and tone visibility. Based on these indices, the algorithm decides on the quota of colors that each image region is to be rendered. The color allocation is performed in the step color allocation, referenced as block 240. The shading algorithm then decides how an image region should be colored with its quota of colors as referenced by block 250 to then produce the output image of block 260. 
     The following describes the segmentation algorithm and the coloring algorithm in detail: 
     THE SEGMENTATION ALGORITHM 
     FIG. 3 shows a block diagram of the segmentation algorithm. The input color image 12 is first calibrated to be in log exposure space. By definition R,G,B is the red, green, and blue log exposures of a pixel in the input image. A neutral point estimation is provided by block 310 as an input to the conversion block 210. The neutral point estimation algorithm can be implemented by any of the existing methods, such as the Large Area Transmission Densitometry (LATD), as described by R. M. Evans, U.S. Pat. No. 2,571,697, Oct. 16, 1951, or the Discriminatory Transmission Density, as described in &#34;Automatic Color Printing Techniques&#34; by J. Hughes and J. K. Bowker, Image Technology, PP. 39-43, Apr./May, 1969. In the current implementation, the LATD method is used. However, the segmentation result is not sensitive to the error in the estimation of the neutral point, based on the observations from many experimental tests. The luminance-chrominance space, (L,s,t,), is defined as: ##EQU1## 
     The input color image is converted from the (R,G,B) space to the (L,s,t) space, in block 210, for the following reasons: 
     1. The two chrominance components, (s,t), are independent of variations in light-source intensity, i.e., a proportional increase in the red, green, and blue exposures by a constant factor does not change the (s,t) coordinates. For example, if the light source intensity is increased by a factor of two, then the values of the red log exposure, the green log exposure, and the blue log exposure will all be increased by the same amount, i.e., log 2=0.3010. Since the coefficients of R,G,B for s and t both sum up to zero, the values of s and t do not change. Furthermore, if the effect of changing surface orientation is mainly in changing the surface irradiance, the (s,t) components will only be weakly dependent on the lighting geometry (the specular highlight is one of the exceptions). As a result of this intensity-invariant nature, the (s,t) chrominance coordinates represent material types much better than the raw sensor signals, R,G,B. 
     2. The s component also captures the major portion of the variation of light source color temperature. For a daylight scene, surfaces are illuminated by direct sunlight and diffuse sky light. This mixture of illuminations of different spectral compositions tend to produce a wider spread of chrominance coordinates along the s (red-blue) direction than along the t (green-magenta) direction. Different weights can thus be applied to s and t to define color difference. 
     3. The luminance component, L, dominated by the variation of surface orientation and illumination gradient, can be discounted by giving it a smaller weighting factor when computing color difference between two pixels. 
     Once the input color image 12 has been converted into the (L,s,t) space, a three-dimensional histogram in that space is accumulated for the entire image as reflected by block 330. The 3-D color histogram in the (L,s,t) space for the input color image is constructed by quantizing the luminance-axis, L, into 32 bins, with a quantization interval of 0.1732. It is found that 100 bins for the s-axis and 100 bins for the t-axis are sufficient to cover most color gamuts. The quantization interval is 0.02 for s and t. The image segmentation is achieved by partitioning the 3-D color histogram. First, the histogram is smoothed by a 3×3×3 convolution kernel with the following coefficients in block 340: ##EQU2## The smoothed histogram is divided by 28, the sum of all the coefficients in the smoothing kernel. The local maxima (peaks) in the smoothed histogram are then detected in block 350. 
     Referring to FIG. 4 in conjunction with FIG. 3, the local peaks, (for example, peak m) are used as the centers for clustering. The entire color histogram is then partitioned into separated volumes (one for each peak) in block 360 such that each point c in a volume has a shorter distance to the peak m in that volume than to any other peaks. (The meaning of &#34;shorter distance&#34; will be discussed below.) Each pixel in the input color image is then labeled, in block 370, according to the volume that contains its color. 
     There are two major considerations in defining the color distance between a peak m and a color c: 
     1. The chrominance difference between m and c is a more reliable indicator of material change than the luminance difference. Therefore, the difference in chrominances should be weighted more in the computation of color distance than the difference in luminance. 
     2. Because of the presence of specular (or surface) reflection, the magnitudes of natural color variations tend to be larger along the saturation direction than along the hue direction. For example, specular highlight tends to reduce the color saturation to the point that highlight areas look almost white. Therefore the difference in saturation should be weighted less than that in hue because saturation variation often does not signal any change of material. 
     Referring to FIG. 4, the color distance between a color c and a peak m is defined as: 
     
         distance(c,m)=2.0*(ΔL).sub.c-m.sup.2 +0.5*(ΔP).sub.c-m.sup.2 +(ΔQ).sub.c-m.sup.2 
    
     where (ΔL) c-m , (ΔP) c-m , and (ΔQ) c-m  are the differences, between a color c and a peak m, in luminance, &#34;saturation&#34;, and &#34;hue&#34;, respectively, after they have been quantized into histogram bins. It should be noted that the above coefficients are dependent on the quantization intervals used in forming the 3-D color histogram. The definition of (ΔP) c-m  and (ΔQ) c-m  are as follows: If we connect each peak with the neutral point, we will form one radial line for each peak. The distance from any point, c, to a peak, m, is decomposed into two components: one parallel and the other perpendicular to the radial line of that peak. The parallel component is (ΔP) c-m  and the perpendicular, (ΔQ) c-m . Remember that we have quantized the luminance much coarser than the two chrominance components (0.1732 v.s. 0.02). The weighting factor 2.0 of (ΔL) c-m   2  still represents a significant discounting in the luminance difference. Appendix A, attached hereto, is a program listing for performing the segmentation portion of the present invention. This program is written in C language and is designed to run on a SUN workstation (SUN Microsystems). 
     The Coloring Algorithm 
     Once the input color image is segmented into regions, the coloring algorithm is used to render each image region with proper color and shades. Since we have only 256 colors (including the luminance and the chrominances) to color all the segmented image regions, the major decisions are (1) how to distribute them among the image regions? and (2) how to use the allocated number of colors to paint an image region?  The method used to distribute color quota is called the color-allocation algorithm, and the method to render the image regions is called the shading algorithm. 
     The Color-Allocation Algorithm 
     After the input color image is segmented into regions of different colors, it is mapped through the tone reproduction curve of the output device. It is important that the number of colors allocated to an image region be determined on the output metric so that the limited number of colors can be used to the best visual effects. It should also be pointed out that image segmentation should be performed in the (L,s,t) color space, but not the output metric, because the physical signals used in segmentation should not be further distorted by the output tone-scale mapping. 
     Since the segmentation algorithm partitions the input color image according to color attributes (luminance and chrominances), all the pixels of an image region will have roughly similar colors. Furthermore, the color distribution in a region is most likely unimodal, i.e., no big gaps between colors. There are mainly four factors that have to be considered for the good rendering of an image region: (1) its dynamic range, (2) its busyness, (3) its area, and (4) its tone-scale visibility. 
     Firstly, if the luminance dynamic range of a region is large, it needs more luminance levels to render the details well. Secondly, quantization errors are less visible in a busy, textured, region than in a uniform region. If the image region consists of subtle, gradual shadings, it needs more luminance levels to avoid contouring. Thirdly, if the area of an image region is large, the contouring effect can be seen easily. It requires more levels of shades to look right. Fourthly, if the image region is too dark or too light on the tone scale curve, its details are lost in the reproduction process, and therefore, need not be rendered accurately. 
     The color-allocation algorithm computes an index for each of the above four factors and then combines them to produce a weighting factor for each image region. The number of colors allocated to an image region is proportional to its weighting factor. 
     The dynamic range, RANGE, of an image region is the difference between the maximum green log-exposure (or code value) and the minimum green log-exposure (or code value). The green signal is used in the present embodiments because it is closer to the visual luminance than the red or blue signal is. In order to reduce the effects of noise, the minimum and the maximum are determined above a threshold, for example, the histogram cell must contain more than 3 pixels. The busyness, BUSY, is measured by the standard deviation of the green log exposures (or code value) of the image region. The area, AREA, is simply the number of pixels in the image region. The tone-scale visibility, VISI, is determined by first mapping the averaged green log-exposure through the tone reproduction curve of the output device and then looking up its visibility measure in a tone-visibility table. The tone-visibility table provides a flexible means for optimizing the shading algorithm according to the characteristics of the output device. This tone-visibility table can either be determined by measuring the subjective luminance contrast between two consecutive brightness levels on the output device, or constructed by inference from statistical distribution of signals from the important objects, such as human faces. Another alternative is simply to use Weber&#39;s law to construct the table. For example, if the monitor 20 can produce 256 levels of gray (say, 0 to 255) and each level of gray gives luminance of Y l ,l=0, . . . , 255, then the visibility of output level l can be computed as: Visibility(l)=(Y l+1  -Y l-1 )/Y l  for l=1, . . . , 254. Visibility (l=0) can be set equal to Visibility (l=1). Visibility (l=255) can be set equal to Visibility (l=254). 
     Let S be the number of image regions from the segmentation. S is limited by the segmentation algorithm to be less than 256. The weighting factor, W i , of an image region, i, 1≦i≦S, is computed by the following formula: 
     
         W.sub.i =(RANGE.sub.i)*(AREA.sub.i)*(VISI.sub.i)/(BUSY.sub.i). 
    
     The number of colors, N i , initially allocated to image region i is: ##EQU3## 
     The formula allocates at least one color to each segmented image region. N i  is compared to V i , the number of discrete green values in the image region i. If the region contains only 10 discrete values, there is no point to allocate more than 10 colors to it. The number of colors, M i , that is actually allocated to an image region, thus, is always limited by its number of discrete values, V i , i.e., M i  ≦V i . The number of colors in excess of this limit, N i  -V i , is given back to the pool of colors for re-distribution. The order of the re-distribution is from the larges area to the smallest and then starts from the largest region again until all 256 colors are used up. Regions which have been allocated as many colors as their number of discrete values are not allocated any additional colors. 
     The Shading Algorithm 
     Because subtle chromatic variations within an object surface are often ignored when an image is viewed this invention colors each image region with only one chromaticity, i.e., that of the peak cell in the color histogram. Alternatively, one can use the averaged chromaticity of the image region. Since the chromaticity is computed from the image region, the number of colors allocated to the region determines the number of luminance levels of that region. 
     Since there are only a few levels of luminance allocated to render the shadings, it is most important to use them to their best effect. An exact minimization of visual quantization errors requires precise specifications of the input and output devices, and a model of supra-threshold visual error model. For a specific application, this type of optimization should be performed to obtain the best results. Aiming at general applications, this invention uses a simple but relatively effective quantization method, which will be called the recursive partition method. The method is described as follows: 
     The histogram of the luminance (or green) signal of an image region i, is first accumulated. Let the total number of pixels in the image region be P i . If we are to render the shading with M i  output levels, we divide the total dynamic range of the image values into M i  intervals, each contains P i  /M i  pixels (this is called the partition size). Within each partitioned interval, its mean level is used as the representation level. FIG. 5 shows an example of how this is done. However, there is some complication in the digital implementation because one image value in the histogram may contain more than P i  /M i  pixels in the region. If the partition size is fixed at P i  /M i  pixels and if the pixels of the same image value are not to be mapped to different output levels, then there may not be M i  intervals. In order to fully use the allocated M i  levels, the algorithm reduces the partition size by 10% and repeats the partition process. If the M i  levels are not used up, then the algorithm reduces the partition size again. Since M i  is always less than or equal to the number of discrete values, V i , in the histogram of the image region i, this recursive process is guaranteed to stop, with the minimum possible partition size equal to 1. Appendix B, attached hereto, is a program listing for performing the coloring portion of the present invention. This program is written in C language and is designed to run on a SUN workstation (SUN Microsystems). 
     While there has been shown what is considered to be the preferred embodiments of the invention, it will be manifest that many changes and modifications may be made therein without departing from the essential spirit of the invention. It is intended, therefore, in the annexed claims, to cover all such changes and modifications as may fall within the true scope of the invention. ##SPC1##