Colour image quantization system.

At the present time color displays often employ a color lookup table (LUT) (see Figure 12). However, if a frame buffer can store all the intensities of red, green and blue components of image data, a color LUT becomes unnecessary; the data read from the frame buffer is used directly for video signals for the color display. Frequently, however, each of the red, the green and the blue components is represented by 8 bits, and thus 24 bits are required for one pel of the image data. In cases such as this the frame buffer requires enormous amounts of storage, and becomes expensive.

To overcome this problem a colour LUT, can be utilised, in which the contents of the frame buffer are used as color indexes to address the LUT. The contents of the LUT representing red, green and blue components of color are read and utilized as video signals for the color display. Therefore, it is sufficient for the pel data in the frame buffer to just accommodate the number of entries of the color LUT. For example, in a case where the number of entries of the color LUT or the number of colors simultaneously displayed on the color display is 256, the pel data of the frame buffer can be represented by 8 bits (1 byte).

At present, there are color LUT-type displays that can simultaneously display 8, 16, 32 or 256 colors. When utilising such displays a color image may have a greater number of color than the number of colors available for display (for example, a color image, where the intensity of each of the red, green and blue component is represented by 8 bits, has 16.7 million colors), it is important to be able to select the optimum number of simultaneously displayed colors, to cause as little deterioration of image quality as possible, and to map the original colors of the color image to those selected colors simultaneously displayable. Such a technique is called color image quantization.

As described by P. Heckbert in "Color Image Quantization for Frame Buffer Display," ACM SIGGRAPH '82, pp. 297 - 307, July, 1982, color quantization can be broadly divided into uniform sampling and adaptive sampling. Uniform sampling performs quantization by uniformly dividing a color space, and giving a representative color to each divided space; reloading of a LUT is not necessary once the representative color for each divided space has been loaded. A disadvantage of this technique is that image quality is significantly degraded for an input image whose colors are not uniformly distributed in a color-space, but are locally clustered. (Here, the term color-space means various spaces such as RGB space (Red, Green, Blue space), HLS space (Hue, Lightness, Saturation space), CYMB space (Cyan, Yellow, Magenta, Black space) and L*u*v space).

J. Tajima "Uniform Color Scale Applications to Computer Graphics," COMPUTER VISION, GRAPHICS, AND IMAGE PROCESSING, vol. 21, No. 3, pp. 305 - 325, March, 1983 discloses uniform sampling in an L*u*v space. L*u*v space means a color-space which is arranged so that color difference sensed by a human corresponds to a distance in the space, and is also called a uniform color-space.

Adaptive sampling is a technique where the contents of a lookup table change according to an input image to perform the optimum quantization. Various adaptive sampling methods have been proposed, but all perform quantization by the following four steps. (Here we assume that an input image is defined in an RGB space). <ul id="ul0001" list-style="none"><li>Step 1: Sample an input image represented by each n bits for of R, G, and B in a space with each "m" bits for each of R, G, and B (generally, m &lt;= n), and generate a histogram.</li><li>Step 2: Select colors to be loaded in the lookup table ("k" colors) (generally, 2^3m &gt;= k).</li><li>Step 3: Perform mapping from the sampled "m" bit RGB space to the lookup table.</li><li>Step 4: Assign the corresponding color in the lookup table to each pel of the input image.</li></ul>

Step 2 and subsequent steps determine the image quality, but the key steps for the quantization itself are Steps 2 and 3; the quality of the quantization depends on Step 2 where "k" representative colors are selected, and Step 3 where colors "close" to remaining colors are selected from the "k" representative colors, and assigned. In Step 4, error diffusion utilising errors of the quantization of dithering (a random noise method) are also used in many cases.

A known technique for performing Step 2 is listed in the following. P. Heckbert "Color Image Quantization for Frame Buffer Display," ACM SIGGRAPH, July, 1982 discloses the popularity algorithm and the median cut algorithm. The former is a method that sorts a histogram in descending order of frequency, and selects "k" colors from the top as the representative colors. This method is simple, but has a noticeable disadvantage that the image quality significantly deteriorates if many colors are distributed with equal frequency.

The latter is a method that calculates maximum and minimum values in each direction of R, G, and B components, and splits the space with their median value recursively. Extra time is necessary to find the maximum and the minimum values in each direction of R, G, and B components, and, if the median values are given in real numbers, a major amount of processing time is required because of real number calculation. If they are given in integers, there is the disadvantage that errors may be caused whether they are truncated or rounded.

U. S. Patent No. 4,654,720 discloses the population equalization algorithm. It is a method that selects "k" representative colors while finding neighbourhood spaces which render the frequency of the "k" colors as equal as possible in the color-space. This method provides excellent image quality, but a lot of time is necessary to merge the neighbourhood spaces depending on the input image, and an enormous amount of storage is required.

US 4, 710, 806 discloses a fixed are and chromaticity based algorithm. It is a method in which a fixed area is provided in a color lookup table in advance, entries whose values appear in the fixed area are removed from the histogram before a histogram is generated based on the ratio between R, G, and B (chromaticity), and representative colors are found according to peak values appearing therein. Colors in a region with constant chromaticity and varying lightness are mainly selected by utilizing the characteristic of the human eye that is sensitive to the lightness. Existence or nonexistence of the fixed area depends on an input image, so that it may be an advantage or a disadvantage. However, a major drawback is that this technique requires a lot of processing time because real number calculation is involved in a series of processes such as generation of the histogram for brightness and detection of the peaks (particularly, calculation of angles such as arc cosine).

Step 3, involves finding neighbourhood representative color for those remaining colors with more than one entry in the histogram. The technique described in US 4, 654, 720 processes them through merge while incrementing the distance as 1-st neighbourhood, 2-nd neighbourhood, and so on. Other approaches find representative neighbourhood colours by introducing some measures of distance (for example, Euclidean distance in the RGB space). The distance calculation involved in finding the neighbourhood is a time-consuming process.

The present invention provides a means for processing both Steps 2 and 3 utilising an adaptive sampling method at a high speed. The processing time and the storage required for quantization are proportional to the number of colors simultaneously displayable on the color display, and are not affected by the number of colors and the distribution of colors specific to the original image. Due to the decrease in storage required the invention can be implemented on a personal computer.

A color image quantization system is presented in which selection of representative color data to be loaded into a look up table are determined by division of an original color space to generate child-color spaces, which in turn are repeatedly divided until at least k child-color spaces have been generated, where k equals the number of addresses to the LUT, the order in which the color spaces are divided being dependent upon the frequency of original image pels whose color lies within each color space. This arrangement achieves the advantage that the number of pels (frequency of use) assigned in each divided color-space becomes as nearly equal as possible and image quality is maintained.

In a preferred embodiment the order of color-space division is determined by the value of a space-occupying number for a color-space, the number being obtained by calculating the number of pels of the original image with colors that lie within the color-space and multiplying the calculation by a weighting-factor corresponding to the level of the division, the level being related to the number of times the original color-space has been divided to yield the color-space. In one arrangement the weighting-factor becomes larger as the division level becomes higher, and the color-spaces are divided in descending order of space-occupying number.

A method and apparatus for color image quantization is presented which selects "k" display colors from 2^Σni colors obtained by assigning n_i bits to represent the intensity level of each of "a" kinds of basic color (1 ≦ i ≦ a); and quantizies an original color image comprising a number of pels for which any one of the said 2^Σni colors may be assigned so that it may be displayed with the said "k" display colors: <ul id="ul0002" list-style="none"><li>(a) Inputting the original image, sample in a color-space defined by assigning m_i (m_i ≦ n_i) bits representing the intensity level of each of the "a" kinds of basic color, and generating an a-dimension histogram,</li><li>(b)Repeating dividing a color-space into X child-spaces, when calculating a space-occupying number by: calculating the number of pels assigned for colors within each generated child-space, referring to the histogram, and multiplying the calculation result by a weighing-factor corresponding to a level of the division,</li><li>(c) Preparing a tree-structured list which describes a parent-child relationship of color-spaces, and updating the list by registering a newly generated color space each time a color space is divided,</li><li>(d) Selecting "k" color spaces as representative color spaces in the descending order of the space-occupying number, among those located at ends of the tree-structured list,</li><li>(e) Selecting a representative color for each of the said "k" representative color-spaces, and providing the representative color with an index,</li><li>(f) For a color other than the representative color within each of the said "k" representative color-spaces, giving the index assigned for the representative color of the color-space, for a color within a color-space other than the said representative color-spaces in the said tree-structured list, finding a representative color-space located close to the color-space, and giving it the index assigned for the found representative color-space, and</li><li>(g) For each pel in the said original image, obtaining an index given to the color assigned for the pel, and storing it in a storage device.</li></ul>

The above-mentioned "a" kinds of basic color are typically those basic colors such as red, green and blue. However, the scope of the invention is not limited to an image consisting of only these color components. For example, in the field of remote sensing, a component such as ground surface temperature may be included as a basic component. In this regard, an image to be quantized could be called a multi-dimensional multi-value image. However, in the following, the term "color image" is used for convenience.

A specific embodiment of the invention will now be described with the aid of the accompanying diagrams in which: <ul id="ul0003" list-style="none"><li>Figure 1 is a diagram schematically showing the entire constitution of an embodiment according to the invention.</li><li>Figure 2 is a diagram illustrating a histogram created by Step 1.</li><li>Figure 3 is a flowchart for generating the histogram in Step 1.</li><li>Figure 4 is a diagram illustrating the relationship between the RGB space and the divided color-spaces.</li><li>Figure 5 is a conceptual diagram of a divided color-space management list.</li><li>Figure 6 is a diagram illustrating a weighing-factor for finding a space-occupying number.</li><li>Figure 7 is a conceptual diagram of a division priority management list.</li><li>Figure 8 is a diagram two-dimensionally illustrating the process for dividing a color-space.</li><li>Figures 9 and 10 are diagrams illustrating the process for generating the division priority management list.</li><li>Figure 11 is a diagram illustrating a color-indexed histogram and a color lookup table.</li><li>Figure 12 is a diagram schematically illustrating a color display using the color LUT technique.</li><li>Figure 13 is a diagram illustrating the process flow of Step 2 in detail.</li><li>Figure 14 is a diagram illustrating the process for calculating the tree-structured level of a child color-space (processor 2-1).</li><li>Figure 15 is a diagram illustrating the process for calculating a range of a color-space occupied by a child color-space (processor 2-1).</li><li>Figure 16 is a diagram illustrating the process for calculating the frequency of use of colors (counts) in the child color-space (processor 2-1).</li><li>Figure 17 is a diagram illustrating the process for inserting and sorting the division priority management list (processor 2-2).</li><li>Figure 18 is a diagram illustrating the process of the divisibility check (processor 2-5).</li><li>Figure 19 is a diagram illustrating the process for setting color indices in the color lookup table (processor 2-6).</li><li>Figure 20 is a diagram illustrating the process for setting color data in the color lookup table (processor 2-6).</li><li>Figure 21 is a diagram illustrating the processing flow of Step 3 in detail.</li><li>Figure 22 is a diagram illustrating the process for providing the color indices with the parent color-space (processor 3-1).</li><li>Figure 23 is a diagram illustrating the process for setting the color indexes in the color indexed histogram (processor 3-2).</li><li>Figure 24 is a diagram illustrating an example of the histogram.</li><li>Figures 25 and 28 are diagrams illustrating examples of data for divided color-spaces after division into eight.</li><li>Figures 26, and 29 through 35 are diagrams illustrating the process for generating the division priority management list.</li><li>Figure 27 is a diagram illustrating an example of the divided color-space management list.</li><li>Figure 36 through 38 are diagrams illustrating an example of final divided color-space management list.</li></ul>

Although the invention can apply to a multi-dimensional multi-value image, it is described as an apparatus for simple color image quantization by exemplifying a color-space consisting of red, green and blue components.

Figure 1 shows a schematic of apparatus for color image quantization. The apparatus broadly consists of four units; a histogram generator, a representative color selector, a neighbourhood representative color mapping device, and an index image generator. It is assumed that each of the red, green and blue components of an original image to be displayed is "n" bits, and that a display utilising a color LUT selects and displays "k" colors (hereinafter called "representative colors") from a color-space consisting of "m" bits for each of the red, green, and blue components. The apparatus performs quantization of a color image and the following describes the processing sequence in conjunction with each of the above units.

1) Step 1: Generation of histogram

The histogram generator receives an original image to be displayed, finds the frequency of colors used in the image, and outputs a histogram. The original image being received is represented by "n" bits for each of the red (R), the green (G), and the blue (B) components, and the histogram output has "m" bits for each of R, G, and B (n ≧ m). Figure 2 shows an example of a histogram, and Figure 3 illustrates the processing sequence of the histogram generator. In Figure 3, N indicates the number of pels in the original image, R(i), G(i) and B(i) indicate the i-th pel data of the original image ("n" bits for each of R, G and B), respectively, r, g, and b indicate data consisting of only significant "m" bits taken from data of R(i), G(i) and B(i), respectively, and H (r, g, b) indicates the frequency of use (count value) for elements (r, g, b) in a color-space represented by "m" bits for each of the red, the green, and the blue components. Once Step 1 is completed, Step 2 is started.

2) Step 2: Selection of representative colors

In Step 2, the representative color selector recursively divides into eight the color-space represented by "m" bits for each of the red, the green, and the blue components, and finally obtains "k" divided color-spaces from which the representative colors are selected. In this case, the color-space is recursively divided into eight so that the number of pels (frequency of use) assigned in each divided color-space may become as nearly equal as possible.

A divided color-space management list and a division priority management list are introduced to implement the above.

2-1) Divided color-space management list

Because the embodiment herein treats a three-dimensional space having red, green, and blue components, the space is divided into eight, and the divided color-space management list has an eight-branch (oct-tree) structure. The list will be a four-branch (quad-tree) structure if the space is two-dimensional, or a 16-branch structure if it is four-dimensional.

Figure 4 shows the relation between the color-space and eight divided spaces. At the time when the color image quantization process is started, each of the red, the green, and the blue components has a value in a range from the lower limit of 0 to the upper limit of 2^m - 1. First, the entire color-space is divided into eight. For the sake of convenience, the eight divided spaces are number from (1) to (8) according to the numbering practice as shown in Figure 4. They are called child color-spaces (child-octants) to the original color-space.

The original space is called a parent color-space (parent-octant) to those child color-spaces (1) to (8).

If the lower and the upper limits of the red, the green, and the blue components of a parent color-space are represented by (R_min, R_max), (G_min, G_max), and (B_min, B_max), those of the child color spaces are automatically defined according to the following rule.

Child-octant (1)

(R_min, (R_min + R_max)/2), (G_min, (G_min + G_max)/2), (B_min, (B_min + B_max)/2)

Child-octant (2)

((R_min + R_max)/2, R_max), (G_min, (G_min+ G_max)/2), (B_{min, (Bmin} + B_max)/2)

Child-octant (3)

(R_min, (R_min + R_max)/2), ((G_min + G_max)/2, G_max), (B_min, (B_min + B_max)/2)

Child-octant (4)

((R_min + R_max)/2, R_max), ((G_min + G_max)/2), G_max), (B_min, (B_min + B_max)/2)

Child-octant (5)

(R_min, (R_min + R_max)/2), (G_min, (G_min + G_max)/2), ((B_min + B_max)/2, B_max)

Child-octant (6)

((R_min + R_max)/2, R_max), (G_min, (G_min + G_max)/2), ((B_min + B_max)/2, B_max)

Child-octant (7)

(R_min, (R_min + R_max)/2), ((G_min + G_max)/2, G_max), ((B_min + B_max)/2, B_max)

Child-octant (8)

((R_min + R_max)/2, R_max), ((G_min + G_max)/2, G_max), ((B_min + B_max)/2, B_max)

Each child color-space is further subject to division into eight. As division is repeated, the difference between the lower and the upper limits becomes smaller.

Thus, a tree structure as shown in Figure 5 is obtained. It is the divided color-space management list that controls this tree structure.

Each element (node) in the divided color-space management list (node) has the following information for controlling each child color-space: <ul id="ul0004" list-style="none"><li>(1) Depth of the tree structure (level)</li><li>(2) Upper and lower limits of the red, the green, and the blue components of a child color-space.</li><li>(3) Space-occupying number</li><li>(4) Color index of a color lookup table (LUT)</li><li>(5) Representative color (red, green, and blue)</li><li>(6) Pointer to the parent color-space</li><li>(7) Pointers to eight child color-spaces</li></ul>

The level in the tree structure (1) has a value of up to "m" at the deepest level. At the level "m," the upper limit coincides with the lower limit. This means that the space cannot be divided any more at the level "m." The space-occupying number (3) can be found by multiplying the frequency of use in the histogram found in Step 1 by a weighing-factor determined according to the depth of the tree structure (level) (1). Figure 6 shows an example of weighing-factor rules for m = 4. The color index of a color LUT (4) and the representative color (5) are set in Step 2 or 3. The pointers (6) and (7) are pointers connecting the parent color-space and the child color-space according to the numbering rules shown in Figure 4 when the parent color-space is divided into eight child color-spaces, and back pointers enabling easy reference from a child color space generated through division to the parent color space. In a case where a color space does not have any child color space, all the pointers of (7) are empty (NULL). Also, in a case where the space-occupying number becomes zero, the color space is not assigned for a memory for its control, and is treated as an empty (NULL) space. Therefore, some of the pointers to the child color-spaces may be empty (NULL).

2-2) Division priority management list

The division priority management list is used to determine which space should be divided into eight next, while a color-space is recursively divided into eight.

Figure 7 shows a division priority management list. Each element of the list is rearranged in descending order of the space-occupying number whenever a color-space is divided into eight. Thus, each element (node) of the list has the following three pointers: <ul id="ul0005" list-style="none"><li>(1) Pointer to a corresponding color-space element (node) in the divided color-space management list</li><li>(2) Pointer to an element (node) that has a space-occupying number smaller than its space-occupying number, but is closest to it</li><li>(3) Pointer to an element (node) that has a space-occupying number larger than its space-occupying number, but is closes to it</li></ul>

2-3) Procedure for selecting representative colors

Figure 8 shows the process in which a color-space is divided two-dimensionally for easy understanding. The numerals in the divided color-space of Figure 8 indicate examples of the space-occupying number.

First, a color-space is divided into four, and provides four child-color spaces. At the time, the above-mentioned divided color-space management list as well as the division priority management list are generated, so that the elements are arranged in descending order of the space-occupying number (proc-1 in Figures 8 and 9).

Then, a child-space (A) at the top of the division priority management list pointed by the division priority controlling pointer (CPTR), or having the largest space-occupying number is selected as the object of division, and divided into four. The divided color-space management list is updated in the same manner as above, and the division priority management list is rearranged and updated for its elements in the descending order of the space-occupying number (proc-2 in Figures 8 and 9). Such a process of division into four is recursively repeated until the number of divided color-spaces reaches "k" (the number of representative colors).

In a case where "k" is a very large number, the division of a color-space may be stopped at the moment when the number of color-spaces registered in the division priority management list reaches "k," and Steps 3 and 4 are started.

However, to attain further improvement of the image quality, division of the color-space, and update of the divided color-space management list and the division priority management list are further repeated.

When the number of the divided color-spaces becomes larger than "k," as shown in Figure 10, a color-space which is (k + 1) or behind in priority is deleted from the division priority management list.

In addition, after the number of the divided color-spaces becomes larger than "k," a child color-space to be divided is selected in the following manner. First, assuming that a child color-space at the top of the division priority management list pointed by CPTR (P in Figure 10) is divided into four, if the largest value of the space-occupying numbers for these four child color-spaces is larger than than that of the space-occupying number for a child color-space (R) at the end of the current division priority management list, the color-space (P) at the top of the division priority management list is divided into four. Otherwise, CPTR moves to the second child color-space (Q), which is then selected as the object of the division and divided into four. The same process is repeated, and the process of Step 2 is completed when CPTR points to the k-th child color-space R.

The representative color selector determines representative colors from colors contained in "k" child color-spaces in the final division priority management list generated in Step 2, and sets color indexes of the representative colors to corresponding "k" child color-spaces in the divided color-space management list. It also generates a color lookup table (LUT) that is a correlation table of the representative colors and the color indexes (see Figure 11A). The color indexes are also set in the corresponding entries in the histogram.

3) Step 3: Mapping to neighborhood representative color

The neighbourhood representative color mapping device determines representative colors closest to those of the original image, and sets indexes of the representative colors in the histogram generated in Step 1 (see Figure 11B). Step 3 consists of the following two major processes.

3-1) Process 1

To a non-end parent color-space in the generated divided color-space management list having child ponters, the color index of the child color space having the largest space-occupying number among those with representative colors is recursively set as its color index.

3-2) Process 2

Neighbourhood representative colors for mapping are determined in the following manner for entries of the histogram generated in Step 1 whose use frequency is non-zero, and which are not selected as the representative colors. <ul id="ul0006" list-style="none"><li>a) If any brother color-space, which means color-spaces having the same parent color space, is selected as a representative color, its color index is provided.</li><li>b) If there is no such color space, the color index of the representative color of the parent color-space set in Process 1 is provided.</li><li>c) Thus, each node in the divided color-space management list, or each color-space is provided with one color index. Then, it is sufficient to find an end node, to which the color of the entry with non-zero frequency of use in the histogram belongs, by traversing the divided color-space management list for each entry, and to set the index provided for the node to the entry.</li></ul>

4) Step 4: Index image generation

The index image generator replaces the color of each pel of the original image to an index of the representative color by referring to the histogram with indexes of the representative colors generated in Step 3 to generate an index image in which a pel sequence is represented by an index sequence.

II. More detailed embodiment

Now, a detailed explanation of the representative the color selector in Step 2 of the above-mentioned embodiment, and the neighbourhood representative color mapping device in Step 3, is given. It should be noted that the processor described in the following may be constituted by dedicated hardware, or by a software routine.

1) Step 2: Selection of representative colors

Figure 13 shows a more detailed process flow of the representative color selector. It has six processors. Input signals, output signals and processing procedure of each processor are described below.

(1) Processor 2-1 (processor for generating a divided child color-space)

The processor 2-1 receives the divided color-space data to be divided and the histogram as input signals, and outputs child color-space data as output signals. The contents of the input and the output signals are provided as follows:

(Input signals) : The divided color-space to be divided being represented by ϑ

in

<ul id="ul0007" list-style="none"><li>(1) Level of ϑ_in (integer data)</li><li>(2) R_min, R_max of ϑ_in (integer data)</li><li>(3) G_min, G_max of ϑ_in (integer data)</li><li>(4) B_min, B_max of ϑ_in (integer data)</li><li>(5) Three-dimensional histogram H (r, g, b) (integer data)</li></ul>

(Output signals): j-th child color-space (1 ≦ j ≦ 8) being represented by ϑ

out

(j)

The following is outputted for j = 1 to 8. <ul id="ul0008" list-style="none"><li>(1) Level of ϑ_out (j)</li><li>(2) R_min, R_max of ϑ_out (j)</li><li>(3) G_min, G_max of ϑ_out (j)</li><li>(4) B_min, B_max of ϑ_out (j)</li><li>(5) Counts of the histogram for ϑ_out (j), that is, total number of the frequency of use of color (integer data)</li></ul>

The CPU of the processor 2-1 executes the following operation. <ul id="ul0009" list-style="none"><li>(i) Calculation of ϑ_out (j) level</li><li>(ii) Calculation of R_min, R_max, G_min, G_max, B_min, B_max, of ϑ_out (j)</li><li>(iii) Calculation of total number of the frequency of use of color in ϑ_out (j)</li></ul>

Figure 14 shows the procedure of operation (i).

Figure 15 shows a circuit used for the procedure of operation (ii).

For the sake of simplicity, an input signal string is sequentially represented by a set of four elements, (i, j, k, SW), and an output signal string is represented by a set of two elements, (k, (i + j)/2) or ((i + j)/2, k). By using these, the entire operation process of (ii) is given as follows (the left side of the arrow indicating the output string, and the right side indicating the input string):

For ϑ

out

(1)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_min of ϑ_in, ON) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_min of ϑ_in, ON) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_min of ϑ_in, ON)

For ϑ

out

(2)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_min of ϑ_in, OFF) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_min of ϑ_in, ON) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_min of ϑ_in, ON)

For ϑ

out

(3)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_min of ϑ_in, ON) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_max of ϑ_in, OFF) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_min of ϑ_in, ON)

For ϑ

out

(4)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_max of ϑ_in, OFF) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_max of ϑ_in, OFF) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_min of ϑ_in, ON)

For ϑ

out

(5)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_min of ϑ_in, ON) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_min of ϑ_in, ON) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_max of ϑ_in, OFF)

For ϑ

out

(6)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_max of ϑ_in, OFF) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_max of ϑ_in, ON) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_max of ϑ_in, OFF)

For ϑ

out

(7)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_min of ϑ_in, ON) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_max of ϑ_in, OFF) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_max of ϑ_in, OFF)

For ϑ

out

(8)

(R_min, R_max) _ (R_min of ϑ_in, R_max of ϑ_in, R_max of ϑ_in, OFF) (G_min, G_max) _ (G_min of ϑ_in, G_max of ϑ_in, G_max of ϑ_in, OFF) (B_min, B_max) _ (B_min of ϑ_in, B_max of ϑ_in, B_max of ϑ_in, OFF)

The operation of (iii) is processed in the flow shown in Figure 16 by using the output signals of (ii).

(2)Processor 2-2 (processor for inserting and sorting the division priority management list)

The processor 2-2 receives a divided color-space to be inserted as input signals, and generates a division priority management list inserted with the divided color-space as the output signals.

(Input signals) : The divided color-space subject to insertion being represented by ϑ

in

<ul id="ul0010" list-style="none"><li>(1) Level of ϑ_in (integer data) ... being represented by "level_in"</li><li>(2) Total number of the frequency of use of color in ϑ_in (integer data)</li><li>(3) ID of ϑ_in (integer data)</li><li>(4) m (data of number of bits in a histogram)</li><li>(5) N_in (number of entries in the division priority management list: before insertion)</li></ul>

(Output signal):

<ul id="ul0011" list-style="none"><li>(1) N_out (number of entries in the division priority management list: after insertion)</li><li>(2) ID (i) (ID of the i-th child color-space in the list (1 ≦ i ≦ N_out) : integer data)</li><li>(3) VAL (i) (space-occupying number for the i-th child color-space in the list)</li></ul>

Wherein VAL (i) is integer data values which are sorted in the descending order. The space-occupying number is given by the following equation: Space-governing number ≡ (Total number of frequency of use of color contained in the divided color-space) x (Weighing-factor corresponding to the level of the divided color-space)

The weighing-factor provides weighing (m + 1 - level) times for the direction of each axis of an RGB space according to the level of the divided color-space so that it can accommodate division of a "m" bits space. It indicates how many times a wider area the space has than the state where it is exactly divided into "m" in the direction of the axis (m = level). Because the RGB space is in fact three-dimensional, the weighing-factor is defined as (m + 1 - level)³.

Figure 17 shows the processing procedure of the processor 2-2.

(3) Processor 2-3 (processor for deleting the entry at the end of the division priority management list)

The processor 2-3 receives the current division priority management list as input signals, and generates a division priority management list, the entry at the end of which is deleted, as the output signals.

(Input signals) :

<ul id="ul0012" list-style="none"><li>(1) N_in (number of entries in the division priority management list: before deletion)</li><li>(2) ID (i) (ID of the i-th divided color-space in the list (1 ≦ i ≦ N_in) : integer data)</li><li>(3) VAL (i) (space-occupying number for the i-th divided color-space in the list)</li></ul>

(Output signals) :

<ul id="ul0013" list-style="none"><li>(1) N_out (number of entries in the division priority management list: after deletion)</li><li>(2) ID (i) (ID of the i-th divided color-space in the list (1 ≦ i ≦ N_out) : integer data)</li><li>(3) VAL (i) (space-occupying number for the i-th divided color-space in the list)</li></ul>

(4) Processor 2-4 (processor for indicating the division priority)

The processor 2-4 receives the division priority controlling pointer CPTR and the division priority management list as the input signals, and generates divided color-spaces (octants) as the output signals.

(Input signals) :

<ul id="ul0014" list-style="none"><li>(1) CPTR (division priority controlling pointer: integer data)</li><li>(2) N (number of entries in the division priority management list: integer data)</li><li>(3) ID (i) (ID of the i-th divided color-space in the list (1 ≦ i ≦ N) : integer data)</li></ul>

(Output signals): ϑ

out

being the divided colour-space of ID (CPTR)

<ul id="ul0015" list-style="none"><li>(1) Level of ϑ_out (integer data)</li><li>(2) R_min, R_max of ϑ_out (integer data)</li><li>(3) G_min, G_max of ϑ_out (integer data)</li><li>(4) B_min, B_max of ϑ_out (integer data)</li><li>(5) Total number of frequency of use of colors in ϑ_out (integer data)</li></ul>

(5) Processor 2-5 (processor for judging divisibility)

The processor 2-5 receives a divided color-space, which is a candidate of division, a division priority management list and a histogram as the input signals, and generates judgment value whether or not it can be divided as the output signals.

(Input signals) : Color-space subject to division being represented by ϑ

in

<ul id="ul0016" list-style="none"><li>(1) Level of ϑ_in (integer data) .... (being represented by level_in)</li><li>(2) Total number of frequency of use of colors in ϑ_in (integer data)</li><li>(3) m (data of number of bits in a histogram)</li><li>(4) N (number of entries in the division priority management list: integer data)</li><li>(5) ID (i) (ID of the i-th divided color-space in the list (1 ≦ i ≦ N) : integer data)</li><li>(6) VAL (i) (space-occupying number for the i-th divided color-space in the list)</li><li>(7) H (r, g, b) (value data of a 3m bit histogram)</li></ul>

(Output signals):

(1) Judgment value (ON or OFF)

Figure 18 shows the processing procedure. As shown in the figure, the processor 2-5 includes the processor 2-1.

(6) Processor 2-6 (processor for generating a color LUT)

The processor 2-6 receives the division priority management list, the divided color-space management list and the histogram as the input signals, and generates a color lookup table and an updated divided color-space management list as the output signals.

(Input signals) : ϑ

in

(j) being the j-th divided color-space (1 ≦ j ≦ M)

<ul id="ul0017" list-style="none"><li>(1) K (number of entries in the divided color-space management list: integer data)</li><li>(2) ID (i) (ID of the i-th divided color-space in the list (1 ≦ i ≦ K) : integer data)</li><li>(3) M (total number of divided color-spaces in the divided color-space management list: integer data)</li><li>(4) ID of ϑ_in (j) (integer data)</li><li>(5) H (r, g, b) (histogram: integer data)</li><li>(6) R_min, R_max, G_min, G_max, B_min, B_max of ϑ_in (j) (integer data)</li></ul>

(Output signals): ϑ

out

(j) being the j-th divided color-space (1 ≦ j ≦ M)

<ul id="ul0018" list-style="none"><li>(1) R (i) (value of red of the i-th index (1 ≦ i ≦ K): integer data)</li><li>(2) G (i) (value of green of the i-th index: integer data)</li><li>(3) B (i) (value of blue of the i-th index: integer data)</li><li>(4) Index value of ϑ_out (j) (integer data)</li></ul>

Although the total number of the divided color-spaces in the divided color-space management list is represented by M herein, it always has a relation of K ≦ M ≦ N_e where N_e is the number of non-zero entries in the histogram H (r, g, b).

In this processor, only "K" out of M output signals of ϑ_out (j) (1 ≦ j ≦ M) are actually set with values.

The processor 2-6 has the following two major processes. <ul id="ul0019" list-style="none"><li>(i) Scan the division priority management list, and set a color index value of a corresponding divided color-space in the table.</li><li>(ii) Scan the division priority management list, and set color data (r, g, b) of a corresponding color index value in the table.</li></ul>

In fact, both (i) and (ii) can be concurrently calculated. Figures 19 and 20 show their processing flows.

The processing flow of Figure 20 determines an average value obtained from color data of colors contained in a representative color-space weighed by the frequency of use of that color, as a representative color. Of course, a color with the highest frequency in the representative color-space may be selected as the representative color, but the process as shown in Figure 20 is preferable when taking image quality into consideration.

Once the representative color is determined, a color index is set to a corresponding entry in the histogram.

2) Step 3: Mapping to neighbouring representative color

Figure 21 shows the processing flow of the neighbourhood representative color mapping device. The device has two processors. The following shows input signals, output signals, and processing flows of each processor.

(1) Processor 3-1 (processor for providing color index to parent color-space)

The processor 3-1 receives the divided color-space management list as the input signals, sets a color index of a child color-space with the largest space-occupying number to the parent color-space in the list, and generates an updated divided color-space management list as the output signals.

(Input signals) : The root divided color-space of the divided color-space management list to be represented by ϑ

in

<ul id="ul0020" list-style="none"><li>(1) Index value of ϑ_in (integer data)</li><li>(2) ID of ϑ_in (integer data)</li><li>(3) Parent color-space flag of ϑ_in (integer data)</li><li>(4) Child color-space ID of ϑ_in (integer data)</li><li>(5) M (total number of divided color-spaces: integer data)</li></ul>

(Output signals): The j-th divided color-space to be represented by ϑ

out

(j) (1 ≦ j ≦ M)

(1) Index value of ϑ_out (j)

This processor can be very simply described by using recursive processing. Only an initial value and the root divided color-space of the divided color-space management list are given as the input signals. Then, the process is performed in the flow as shown in Figure 22. However, it is assumed that large integers are set in the divided color-space management list for the divided color-spaces other than those having the index values (value of 1 to K) set by the processor 2-6. Because a child color-space with the largest space-occupying number appears at the top of the division priority management list, it corresponds to the space with the smallest index value.

(2) Processor 3-2 (processor for generating color index portion of a histogram)

The processor 3-2 receives a histogram with a color index having non-zero entries of N_e (Figure 11B), a color lookup table having "k" color indexes, and the divided color-space management list as the input signals, and generates an updated histogram with color indices.

(Input signals) : The root divided color-space of the divided color-space management list to be represented by ϑ

in

<ul id="ul0021" list-style="none"><li>(1) H (r, g, b) (frequency of use portion of a histogram: integer data)</li><li>(2) I (r, g, b) (color index portion of the histogram: integer data)</li><li>(3) Index value of ϑ_in (integer data)</li><li>(4) ID of ϑ_in (integer data)</li><li>(5) Parent color-space flag of ϑ_in (integer data)</li><li>(6) Child color-space ID of ϑ_in (integer data)</li><li>(7) M (total number of divided color-spaces: integer data)</li><li>(8) R (i), G (i), B (i) (color lookup table: integer data)</li><li>(9) K (number of colors to be given: integer data)</li></ul>

(Output signals):

(1) I (r, g, b) (histogram with color index (color index portion): integer data)

Figure 23 shows the processing flow of the processor 3-2. As shown in the figure, the process for providing the color index of the neighbourhood representative color is performed by traversing the divided color-space management list provided with the color index as described above.

III. Example of execution

Examples of output results from each step are indicated by assuming that an original image has 256 pels, the number of representative colors k = 10, number of bits of each component of red, green and blue of a color space for a histogram m = 4.

III-I. Step 1

A histogram (4 bits for each of R, G, and B) is created from the original image (Figure 24).

III-II. Step 2

<ul id="ul0022" list-style="none"><li>(1) Because the number of non-zero entries in the histogram (15) is larger than k(10), the color-space is divided into eight by the processor 2-1. Figure 25 shows the result. Figures 26 and 27 show the division priority management list and the divided color-space management list at that moment, respectively.</li><li>(2) It is assumed that N is the number of elements in the division priority management list. Because N &lt; k (N = 4, k = 10), the color-space (2) is selected as the color-space subject to the dividing process. Then, it is divided into eight. It should be noted that notation (2)-(1) means that the parent is divided color-space (2) and the child is (1). Figure 28 shows the result of division. The processor 2-2 inserts and sorts these child-spaces. The divided color-spaces are arranged in the descending order of the space-occupying number that is the total number of the frequency of use of color weighed by level. The weighing-factor is given by the rule shown in Figure 6. Thus, the division priority management list shown in Figure 29 is obtained. The value in the parentheses is obtained by multiplying the total frequency number by the weighing-factor (space-occupying number).</li><li>(3) Because N &lt; k (N = 8, k = 10), the divided color-space (8) is selected as the divided color-space subject to the dividing process, and divided into eight. The resultant division priority management list is shown in Figure 30.</li><li>(4) Because N &lt; k (N = 9, k = 10), the divided color-space (8)-(2) is selected as the divided color-space subject to the dividing process, and divided into eight. The resultant division priority management list is shown in Figure 31.</li><li>(5) Because N = k is attained, the processor 2-5 subsequently checks the divisibility in the dividing process. Because CPTR is not equal to k, the divided color-space (2)-(2) is selected as the divided color-space subject to the dividing process. Divisibility check: Assuming that (2)-(2) is divided, the child color space with the highest frequency is (2)-(2)-(1). The value of it multiplied with the weighing-factor is 8*50 = 400, which is larger than the space-occupying number (8) for the last entry of the division priority management list. Thus, it is actually divided. The resultant division priority management list is shown in Figure 32. At that moment, because N &gt; k, divided color-spaces M = N - k are deleted from the end of the division priority management list by the processor 2-3. That is, the entry of (2)-(2)-(6) is deleted.</li><li>(6) Because CPTR is not equal to k, the divided color-space (2)-(8) is selected as the divided color-space subject to the dividing process. Divisibility check: Assuming that (2)-(8) is divided, the child color space with the highest frequency is (2)-(8)-(3). The value of it multiplied with the weighing-factor is 8*30 = 240, which is larger than the value of the last entry (8) of the division priority management list. Thus, it is actually divided. The resultant division priority management list is shown in Figure 33. At that moment, because N &gt; k is attained again, divided color-spaces only to the number of M = N - k (= 2) are deleted from the end of the division priority management list by the processor 2-3.</li><li>(7) The dividing process is sequentially executed up to the divided color-spaces (2)-(4), (3), (8)-(2)-(1), and (2)-(6) in exactly the same manner, the division priority management list is as shown in Figure 34. Until this point, CPTR always points to the top element. However, if the divided color-space (2)-(2)-(1) is then selected and checked for divisibility, the one with the highest frequency of supposed child color-spaces is (2)-(2)-(1)-(7). However, the value multiplied with the weighing-factor is only 50. This is smaller than the value of the end of the division priority management list. Therefore, it is not divided. Thus, CPTR _ CPTR + 1 is attained, which means that the divided color-­space (2)-(2)-(1) is selected as the first object for output.</li><li>(8) Because CPTR (2) is not equal to k, it is intended to perform a similar dividing process with the divisibility check. The divisibility check judges that neither divided color-space of (2)-(4)-(7) nor (2)-(6)-(4) can be divided any more, and CPTR is incremented twice and becomes 4. Because the color-space (8)-(6)-(2) that is one of supposed color-spaces of the divided color-space (8)-(6) has the largest space-occupying number (160), the color-space (8)-(6) is actually divided, and its child color-spaces are inserted and sorted in the division priority management list. The same is true of the divided color-space (3)-(8). Because the supposed color-space (3)-(8)-(4) has the space-occupying number of 160, the color-space (3)-(8) is actually divided, and its child color-spaces are inserted and sorted in the division priority management list. At that moment, the list after the CPTR is as shown in Figure 35.</li><li>(9) Then, all of the divided color-spaces pointed by the CPTR are rejected in the divisibility check, so that only the CPTR is repeatedly incremented and reaches the divided color-space (2)-(5) at the end of the division priority management list. Thus, CPTR = k is attained. Finally, the processor 2-6 provides color indices for the representative colors (r, g, b) corresponding to divided color-spaces from the top of the division priority management list.</li></ul>

III-III. Step 3

The divided color-space management list obtained is shown in Fig. 3.

In the figure, a single circle represents each divided color-space, the upper part of which indicates the frequency of use of the contained color, while the lower part indicates the color index in the color LUT. Although the divided color-space management list actually contains the space-occupying number, the total number of frequency of use of colors contained in each space is indicated in the figure for convenience. A double circle represents a divided color-space remaining in the division priority management list obtained in Step 2 which a color index was assigned to in advance. <ul id="ul0023" list-style="none"><li>(1) The first process in Step 3 is one in which each non-end node in the divided color-space management list of Figure 36 is set with the child divided color-space of the highest frequency of use from its divided color-spaces, or the one with the largest space-occupying number. Figure 37 shows the result of the setting.</li><li>(2) The second process in Step 3 is one in which the color index is set for the end node for which the color index is not yet set while looking for it in the neighbourhood. (No calculation is made for distance.) Its rule is to: &lt;a&gt; First, look for a brother divided color-space (from the closest one), and &lt;b&gt; If there is no brother, or if a color index is not set for a brother, if any, look for the color index that was set to the parent color-space in the above first process.</li></ul>

In this example, the result of setting is as shown in Figure 38 according to &lt;a&gt;.

At this moment, all color indices are found, and there is no case where &lt;b&gt; is applied. Even if, as in the case of the divided color-space (8)-(2)-(3), no index is set for the brother (8)-(2)-(1) in the initial stage, the color index is set in Step 1, so that there is no need to refer to the parent color-space (8)-(2) by applying the rule &lt;b&gt;. Subsequently, as described, color indexes are provided for non-zero entries in the histogram for which no color index is yet provided by traversing the divided color-space management list determined as in Figures 36 through 38. These color indices are then set in the histogram.

III-IV. Step 4

An index image is created by using applicable color index values, which are determined by referring to the color indexed histogram based on the values of r, g, and b (4 bit values that were made the entries of the histogram in Step 1) of the original image while scanning it. Although a specific embodiment has been described a number of variations may be possible.

For example, in the above embodiment, whenever the division priority management list is updated, its elements are rearranged in descending order of space-occupying number, so that the division priority controlling pointer (CPTR) points to an element as close to the top of the list as possible, or the one with as large a space-occupying number as possible. However, the division priority management list is not necessarily sorted. Of course, in that case, the process for determining the element pointed by the CPTR is more complicated.

In addition, in the above embodiment, the entries of the histogram store data of corresponding color indexes. However, it is possible to create a correlation table between the color and the color index separate from the histogram.

Furthermore, even if the embodiment described, it is a matter of course that some steps may be changed in the sequence of the process. For example, setting of the color indexes in the histogram may be conducted in Step 3 for all entries.

As previously stated, the color-space subject to the division is not limited to three dimensions. In the above embodiment, although an equal number of bits are assigned to each basic component, it is possible that a color-space to be subject to division in which the number of bits assigned to a basic component differs from that for another component. In this case, the number of divisions for each time other than 2 may be set for the basic component in its axial direction. Of course, in the three-dimensional cubic color-space, as in the above embodiment, the number of divisions for each time may be intentionally set to a number other than 8.

This invention provides a high-speed method and an apparatus for color image quantization utilizing an adaptive sampling technique in which the processing time is substantially determined by the number of simultaneously displayed colors to be selected, but is not affected by the number of colors or the color distribution in the original image.

Factors contributing to the improvement in the speed of color image quantization are that all calculations necessary for selecting the representative colors can be performed by integer operation, and that there is no need for calculation of the distance mapping to neighbouring representative colors.

All that is required as data are a histogram, a divided color-space management list, and a division priority management list, so that the required storage capacity may be small. Accordingly the invention can be implemented on a personal computer.

In addition, it is arranged that the divisibility of a color-space can be determined by introducing a weighing-factor which depends on the division level, so that, in a case where the original image does not have coloring that is not uniformly distributed in color-space, but has a number of local peaks, it is possible to avoid dropping of the colors representing a color group that are of low density in the color-space, but are widely distributed (they are often colors for accent). Therefore, it is possible to prevent degrading of the quantized image.