JPH0481229B2 - - Google Patents

Description

DETAILED DESCRIPTION OF THE INVENTION [Field of Industrial Application] The present invention relates to an apparatus for processing a color image and converting it into a color image in which the number of types of colors is limited to a small number.

[Conventional technology]

The use of an image memory and a color map as a means for efficiently displaying color images is a well-known technology in color image display devices.
In that case, the color map is hardware that functions as a correspondence conversion table between the index number corresponding to the pixel value of each pixel in the image memory and the actual display color, as shown in FIG. When it is 8 bits and there are 256 indexes, there are many types of colors based on combinations of each color component of R (red), G (green), and B (blue) (4096 types if each R, G, and B are 4 bits). You can select any of the 256 colors and use them for color image display. However, in order to display an actual color image input from a color TV camera or the like using a color map such as the one described above, it is necessary to select and extract colors to be registered in the color map from the input image. This extraction process is generally called "color quantization," and it is desirable to perform it as automatically as possible and with minimal deterioration from the original image.

Figures 4 and 5 are flowcharts outlining a specific method for the above-mentioned processing described, for example, in ``A Consideration on Color Map Creation'' (Proceedings of the 1985 IEICE General Conference National Conference 1173). It's a chat.

In FIG. 4, in step 31, a color image with M bits for each R, G, and B component is input from an image input device such as a color TV camera or scanner, or an image storage device such as a magnetic disk, and in step 32, the color image is input. The colors of all pixels in a color image are examined to create a frequency distribution of colors, that is, a histogram in a three-dimensional (RGB) color space. In step 33, the three-dimensional color space is divided into a plurality of regions based on this histogram, and a representative color is selected for each region. The specific contents of step 33 are, for example, steps 61 to 63 shown in FIG. In step 61, each axis of the three-dimensional RGB space is set to Nr, Ng,
By dividing the RGB space into Nb equal parts, Nr, Ng, Nb
The color with the highest frequency of occurrence within each rectangular parallelepiped is extracted as a candidate color. However, if there is no color that occurs within the rectangular parallelepiped, no candidate color is extracted from within the rectangular parallelepiped. Step 62 is the initial integration, in which each color in the RGB space is mapped to the candidate color with the smallest distance.
The space is divided into N regions, and the weighted average value of the colors in each region is taken as a representative color. That is, the set of candidate colors is Y={〓i}N-1 i=0, where 〓i is R, G,
Three-dimensional vector expressed by the components of B〓i=(ri,
gi, bi), and the colors in the RGB space are 〓 and 〓. Similarly, if we let the three-dimensional vector 〓 = (r, g, b), then 〓
is associated with the candidate color 〓i that satisfies the following formula (1), and belongs to the area Si with area number i. Note that this correspondence relationship is registered in a color space division map as illustrated in FIG.
is entered.

d(〓,〓i)d(〓,〓j); ∀j≠i(0jN-1) (1) Here, d(〓,〓i) represents the distance between vector 〓 and 〓i. , for example, the Euclidean distance d(〓,〓i) =√(-) ² +(-) ² +(-) ² (
2). Note that in the following explanation, when we simply refer to distance, we mean this Euclidean distance.

In this step 62, the weighted average value of the colors included in each region is calculated, 〓i= 〓 〓∈Sih(〓)・〓/hi (3) where hi= 〓 〓∈Sih(〓) Color. However, h(〓) is the appearance frequency of a pixel with color 〓, and 〓 〓∈Si means the sum of all colors 〓 belonging to the region Si. Total color frequency hi for each area and representative color 〓i
are summarized in a region table as shown in Figure 11,
It is used for color integration described later.

In step 63, an area adjacency relationship table is created. The adjacency table is a table as illustrated in FIG. 10, and although it is not essential, it is a means for improving the quality and processing speed of color integration, which will be described later.
For example, the adjacency relationship can be created as follows. Here, the color space division map is formally expressed as S(r, g, b). In other words, color (r, g,
Let S(r, g, b) be the area to which b) belongs. At this time, for each color (r, g, b) in the RGB space, S (r, g, b) = S (r + 1, g, b) (4) S (r, g, b) = S (r, g + 1, b ) (5) S(r, g, b)=S(r, g, b+1) Check whether (6) holds. If equation (4) does not hold, the area S(r, g, b) and the area S(r+
1, g, b) are adjacent, and if equation (5) does not hold, the area S(r, g, b) and the area S(r, g+1,
b) is adjacent, and if equation (6) does not hold, the area S
(r, g, b) and region S(r, g, b+1) are adjacent to each other. Adjacency relationships are created by performing the above processing for all colors in the RGB space. FIG. 10a is an example of an adjacency relationship table, in which the area adjacent to area Si is shown as the area of the column number of the part where the logical value 1 stands when row i is viewed in the horizontal direction,
The figure shows that region Si is adjacent to region _S2 and region Sj. The logical values on the diagonal line from the bottom right are always 0.

On the other hand, in step 34 of FIG. 4, the number of colors (i.e., the number of regions or the number of representative colors) is reduced by the area integration process on the color space, which will be explained below. Proceed to step 39.
If there are still many colors, area integration processing is further executed. Step 41 detects, among the regions on the color space, the region for which the sum of the frequencies of occurrence of colors belonging to that region (hereinafter simply referred to as region frequency) is the smallest. In step 42, an area having a representative color having the shortest distance from the representative color of the area having the minimum frequency is detected. (In the following explanation, the distance between the representative colors of the areas mentioned above may be simply abbreviated as the distance between areas.) At this time, if there is an adjacency relationship table, refer to it and Select the region with the smallest distance. In step 37, the two areas detected as described above are integrated. In other words, if the two regions are Si and Sj, and the frequencies of each region are hi, hj, or the representative colors are 〓i, 〓j, then the frequency h _K and the representative color 〓 _K of the new region S _K created by integration are h _K = hi + hj (7) 〓 _K = (hi〓i + hj〓j) / (hi + hj) (8). This result is reflected in the area table as shown in FIG. For example, if the frequency and representative color of S _K are Si(i
<j) and delete Sj from the table. As a result, the area table becomes Si+Sj→Si
will be updated as

In step 38, the adjacency relationship table is updated.
A specific example is shown in FIG. The update result when the area Sj is integrated into the area Si from the state shown in the figure a is shown in the figure b. That is, take the logical sum of row i and row j and write the result in row i, take the logical sum of column i and column j and write the result in column i, and write the result in row j and column j.
and write a logical value of 0 to the diagonal components.

The above processes of steps 41, 42, 37, and 38 are repeated, and when a predetermined number of colors is reached, the color image is converted into a color image consisting of a small number of target colors in step 39. The specific procedure is as shown in FIG. 7. In step 71, the representative colors reduced to the target number are extracted from the area table and registered in the color map, and in step 72, all colors in the RGB space and the color map are extracted. The correspondence relationship with the index number is registered in the color space division map. Finally step 73
In the step, the pixel value of each pixel in the image memory is converted into a color map index number with reference to the color division space map, and is written into the image memory.

A typical configuration of a device that executes the color image conversion process described above using the flowchart in FIG. This system consists of a microcomputer with a display.

FIG. 5 is a flowchart outlining another example of a processing method in a conventional color image conversion processing device. Steps 31 to 34 and 37 to 39 in the figure are similar to those in FIG. 4, and the only difference is the method of selecting two areas to be integrated. That is,
In the RGB space divided into regions, step
In step 51, the distance between regions is calculated, in step 52, a region pair with the minimum distance between regions is detected, and in step 37, both regions forming the pair are integrated. At this time, if there is an adjacency relationship table, it is only necessary to calculate the distance between areas for areas that have an adjacency relationship. Furthermore, even if the color integration process is repeated because the number of colors does not reach the target number, in step 51, it is only necessary to recalculate only the distance between the new area created by the previous area integration and the adjacent area. ,
Since distances between other adjacent regions remain unchanged due to region integration, the amount of calculation can be significantly reduced.

The configuration of the device that executes the process in FIG. 5 is also the same as that in FIG. 4.

Conventional color image conversion devices are configured to perform the processing described above. When a color image is input, it automatically performs color integration processing, registers the resulting representative color in a color map, and converts the original image. It is now displayed as follows.

[Problem that the invention seeks to solve]

In conventional color image conversion devices such as those described above, the method of detecting region pairs for which color integration should be performed does not sufficiently take into account the effect that color integration has on the image, so it may be inappropriate depending on the content of the image. There was a problem that color integration was performed. In other words, when performing color integration one after another, the order was inappropriate, and there was a great risk that the result of color integration would be significantly degraded from the original image, and important information content contained in the original image would be lost. .

For example, in the method explained in Figure 4, areas with low frequency are preferentially color-integrated, so lines and symbols that do not occupy a large area in the original color image but are important in terms of information are There is a great danger that it will disappear. In addition, in the method explained in Fig. 5, since pairs of regions with a small distance between regions are preferentially color-integrated, shapes that occupy a large area in the original color image but have colors that do not have a large difference are In cases where they are adjacent to each other on the image (this is often the case in natural images), there is a high risk that the original shape will be lost due to color integration.

In this way, in conventional color image conversion devices, the quantity (hereinafter referred to as a measure) used to quantitatively compare the priorities when detecting a pair of areas to be color integrated is only the frequency of the areas. Because it is a single quantity such as , or only the distance between regions, it is not possible to accurately represent the influence of color integration, and as a result, inappropriate color integration is performed preferentially. is what happens.

The present invention was made to solve this problem, and uses a measure as a quantity that well represents the influence of color integration to reduce the risk of inappropriate color integration and to perform good color image conversion processing. The object of the present invention is to obtain a color image converting device.

[Means for solving problems]

a histogram creation means for creating a histogram of the frequency of occurrence of colors in the original color image stored in the image memory; and a color space division for dividing the color space into a plurality of regions based on the histogram and selecting a representative color for each region. and integrating regions one after another in descending order of the measure defined between each divided region or between the representative colors of each region until the number reaches a predetermined number, and a step when the number of regions reaches a predetermined number. In a color image conversion device, the color integration means converts an original color image into a color image consisting of only a limited number of representative colors. A color image conversion device characterized by using hi+hj, where hi and hj are the sum of frequencies of colors in two areas to be integrated, and dij is the distance between representative colors of the two areas to be integrated.

[Effect]

In this invention, a composite quantity that incorporates both the frequency of regions and the distance between regions is used as a measure for detecting region pairs for which color integration should be performed. Therefore, since the measure sufficiently represents the influence of color integration, inappropriate region integration is given low priority, and conversion from the original image to a color image with less degradation can be performed.

〔Example〕

FIG. 1 is an overall configuration diagram of a color image conversion device which is an embodiment of the present invention. Also, Figure 2 shows
FIG. 3 is a system configuration diagram showing an example of the system configuration of a color image conversion device according to the present invention, and FIG. 3 is a flowchart showing an outline of processing in the color image conversion device according to the present invention. Embodiments of the present invention will be described below using these figures. In the figures, the same numbers represent the same or equivalent parts.

The image input means 1 is specifically a device such as a color TV camera or a magnetic disk, and by inputting or transferring a color image, it is written into the image memory 2 as image data having each of R, G, and B components ( Step 31). The image data stored in the image memory 2 is subjected to necessary correspondence conversion (including no conversion) by the color map 3 and displayed on the display device 4.

The histogram creation means 5 sequentially reads out the pixel values of the image data stored in the image memory 2, counts the frequency of occurrence of each color, and creates a histogram (step 32). Specifically, for example, the CPU 21 sequentially reads out the pixel values in the image memory 2 and counts the color of each pixel in a memory area reserved for frequency counting by color in the working memory 22. A histogram is created by incrementing the address values one by one.

The color space dividing means 6 divides the color space into a large number of rectangular parallelepipeds by dividing each axis of the three-dimensional (RGB) color space in the same way as the color space dividing process (step 33) described in the conventional example. The color with the highest frequency of occurrence within the rectangular parallelepiped is extracted as a candidate color. Next, the RGB space is divided into N regions by initial integration processing, and this division is registered in the color space division map in the working memory 22, and the weighted average value of the color of each region is used as the representative color of that region. . In addition, a region table is created in the working memory 22 and used and updated during color integration, which will be described later. Furthermore, the adjacency relationship table creation means 7 creates an adjacency relationship table in the working memory 22 from the color space division map. Similar to the conventional example, this adjacency table creation means 7 is not an essential component.

The color integration means 8 detects a pair of regions to be preferentially integrated based on a measure including both the frequency of regions and the distance between regions, as described below, defined between regions or representative colors, and sequentially integrates the regions. Run the integration. The procedure is almost the same as the conventional example shown in FIG. That is, in the RGB space divided into regions, the measure between regions is calculated in step 35,
In step 36, a pair of regions with the minimum inter-region measure is detected, and in step 37, the paired regions are integrated. The frequency and representative color of the new area are calculated by Equation (7) and Equation
Calculate according to (8). At this time, if there is an adjacency relationship table, it is only necessary to calculate the measure between areas for areas that have an adjacency relationship. Furthermore, even if the number of colors does not reach the target number in step 34 and the color integration process is repeated, in step 35 only the measure of the new area created by the previous area merging and the adjacent area is calculated anew. Since the measures between other adjacent regions have not changed due to the previous region integration, the amount of calculation can be significantly reduced. If there is an adjacency relationship table, the color integration means also updates the adjacency relationship in step 38 after area integration. This process is also similar to the conventional example.

The color integration means 8 repeats the processing in steps 34 to 38 described above, and when it is determined in step 34 that the predetermined number of colors has been reached, color image conversion is performed in step 39 similar to the conventional example. That is, the color map creation means 9 extracts the representative colors reduced to the target number from the area table and registers them in the color map 3, and the color space division map creation means 10 extracts all the colors in the RGB space and the index of the color map 3. A table of correspondence with the numbers is created in the working memory 22. Finally, each pixel value in the image memory 2 is read out, converted into the corresponding index number of the color map 3 with reference to the color space division map, and this index number is written into the image memory 2. As a result, the input original color image is converted into a color image consisting of only a limited number of target color types, and is displayed on the display device 4.

As can be seen from the above description, the histogram creation means 5, color space division means 6, adjacency table creation means 7, color integration means 8, color map creation means 9, color space division map creation means 10, etc. are all specific. The device can be realized by a CPU 21 and a program working memory 22 that stores data such as its programs and various tables, and a part can also be realized by a hardware logic circuit. It is possible.

The specific functional form of the measure can be considered as follows. For the two regions Si and Sj, let the respective frequencies be hi and hj and the representative colors be 〓i and 〓j as described above, and the frequency and representative color of the new region by integrating the regions can be calculated using equations (7) and (8). ), for example, the total color change amount Δ of all pixels belonging to area Si is calculated as follows: Δ=hi( _〓K −〓i) =hihj/hi+hj(〓j−〓i) (9) |Δ| =hihj/hi+hjdij (10). Here dij is the distance between representative colors 〓i and 〓j. Similarly, the sum of the color changes of all pixels belonging to region Sj is Δ=hj (〓 _K − 〓j) = hihj/hi+hj (〓i−〓j) (11) ｜Δ｜=hihj/hi+hjdij ( 12) becomes. In other words, the amount of change in color between before and after integrating both regions can be estimated by |Δ|.
Therefore, as a measure to be defined between two areas |
If Δ| is used to detect and preferentially integrate a pair of regions with the smallest value, each time the region is integrated, the integration that has the smallest amount of color change and the least influence on the entire image can be performed. In this sense, color region integration is executed in the optimal order. In fact, if hihjdij/(hi+hj) is used as a measure, even if the frequency is small, color regions that are far away from other regions tend to remain without being immediately integrated, and the area ratio in the image is Compared to conventional methods, there is less risk of letters and symbols that are small but stand out from other parts and have a different color disappearing. In addition, when the image as a whole contains many similar colors, such as a natural image, even areas with a small distance between representative colors will not be easily integrated if the frequency of both areas is large, and the shape will still tend to be preserved. be.

Note that although the above-mentioned measure requires a slightly larger amount of calculation than the conventional method using a single quantity of frequency or distance, it is not extremely large.

Furthermore, hjdij can be considered as a measure that has the same effect as the above measure and can reduce the amount of calculation.
This is the product of the frequency of a region Sj and the distance dij between the region Si at the minimum distance from that region.

Furthermore, it is also conceivable to use the above two measures depending on the frequency ratio between regions. Since this is hihj/hi+hjdijhjdij (13) when hi≫hj, for example, if hi/hj>3, the formula (1
Calculate the measure on the right side of 3), and if it is 1hi/hj3, calculate and use the measure on the left side of equation (13). However, in this case, the higher frequency of the two areas is
Si, the smaller one is Sj. Using the right side of equation (13) means that the amount of color change due to the integration of both regions can be calculated using the equation
Instead of (8), 〓 _K = 〓i, that is, it corresponds to roughly estimating the amount of color change when a small area is absorbed into a large area. If the ratio of frequencies is large to a certain extent, this is a sufficiently good approximation, and thereby the amount of calculation can be reduced.

As explained above, according to the embodiment of the present invention, since a quantity that includes both the frequency and distance of regions is used as a measure, the influence of color integration is expressed accurately, and inappropriate color integration is not performed. Low risk.

In the above embodiment, the three-dimensional color space was explained as an RGB space, but the color space also includes LUV (uniform color space), LHS (lightness, hue, saturation), and YIQ (brightness and two-dimensional color space).
Three-dimensional spaces other than the RGB space can be considered, such as three chromaticities), and the color space can be divided in the same way by giving a distance function with appropriate weighting for each axis, and the same measure as in the above example can be considered. A color integration method using .

In addition, in the above embodiment, the color space division is performed by equally dividing each axis of the RGB space into Nr, Ng,
Divide into Nb rectangular parallelepipeds, extract the color with the highest frequency of occurrence within each rectangular parallelepiped as a candidate color, and match each color in the RGB space to the candidate color with the shortest distance. Although we have explained that the representative color is calculated in each area, we create a predetermined color space division map without calculating distance, and then select the color that has the highest frequency of occurrence in each divided area or (the color that occurs within the area). (If the color does not exist), the color corresponding to the center of gravity of the area may be used as the representative color. For example, if we formally represent the color division map as S(r, g, b), then S(r, g, b)
The following value is given as the area number for S(r, g, b) = i・Ng・Nb+j・Nb+k (14). However, here i, j, k are
Let Lr, Lg and Lb be each axis of RGB space as Nr,
The lengths of the sides in the R-axis, G-axis, and B-axis directions of Nr, Ng, and Nb rectangular parallelepipeds obtained by equally dividing Ng and Nb shall be values that satisfy the following formula.

i・Lrr<(i+1)・Lr j・Lgg<(j+1)・Lg k・Lbb<(k+1)・Lb (15) In addition, in the above embodiment, color space division (step
After step 33), I explained that the color integration should be repeated without changing the contents of image memory 2 and color map 3 until it is determined that the number of colors has reached the target number in step 34. Based on the result of the integration, registration in the color map 3, creation of a color space division map, etc. may be performed to execute color image conversion (step 39), and the intermediate results may be displayed on the display device 4. In particular, if the index number of color map 3 can be as large as the number of colors that may occur in the original color image, intermediate results can be obtained by simply rewriting color map 3 without changing each pixel value in image memory 2. Display is possible.
Furthermore, in terms of the system configuration, in the description of the embodiment, it is assumed that a color image is directly input from the image input device 1 to the image memory 2, but the color image is not limited to this, but it can be inputted via the CPU 21 by an interface for input/output and communication. It goes without saying that the configuration may be such that the image data is input to the image memory 2.

〔Effect of the invention〕

As explained above, this invention uses a composite quantity that includes both the area frequency as a measure defined between areas or representative colors and the distance between areas when performing color integration. The effect is that the influence on the entire image is reflected well, the risk of inappropriate color integration is reduced, and the original color image can be converted into a good color image consisting of a limited number of types of colors. be.

[Brief explanation of the drawing]

FIG. 1 is an overall configuration diagram of a color image conversion device according to an embodiment of the present invention, FIG. 2 is a system configuration diagram showing an example of the system configuration of a color image conversion device according to the invention, and FIG. 3 is a system configuration diagram showing an example of the system configuration of a color image conversion device according to the invention. FIG. 4 and FIG. 5 are flowcharts showing an outline of the processing in a conventional color image conversion device, and FIGS. 6 and 7 are partial details thereof. FIG. 8 is an example of a color map, FIG. 9 is an example of a color space division map, FIG. 10 is an example of an adjacency relationship table, and FIG.
The figure shows an example of a region table. In the figure, 1 is an image input means, 2 is an image memory, 3 is a color map, 4 is a display device, 5 is a histogram creation means, 6 is a color space division means, 7 is an adjacency table creation means, 8 is a color integration means, 9 is a color map creation means, 10 is a color space division map creation means, 21 is a CPU, and 22 is a program working memory. Note that the same reference numerals in the figures indicate the same or corresponding parts.

Claims (1)

[Scope of Claims] 1. Histogram creation means for creating a histogram of the frequency of occurrence of colors in an original color image stored in an image memory, and dividing a color space into a plurality of regions based on the histogram, and creating a representative image for each region. A color space dividing means for selecting a color, and integrating regions one after another in descending order of the measure defined by each divided region or between the representative colors of each region until the number reaches a predetermined number, and A color image conversion device comprising a color integration means for converting an original color image into a color image consisting of only a limited number of representative colors when a predetermined number of representative colors has been reached, the color integration means comprising:
A color image conversion device characterized in that the following formula hi・hj・dij/hi+hj is used as the measure. Here, hi and hj are the sums of the frequencies of colors in the two regions to be integrated, and dij is the distance between the representative colors of the two regions to be integrated.