JPH0697459B2 - Color image area management device, color image area management method, and color image area search method - Google Patents

Description

Detailed Description of the Invention

[0001]

FIELD OF THE INVENTION This invention relates generally to image processing systems, and more particularly to a method and system for managing color images and a method for retrieving regions of a color image thus managed. And the system.

[0002]

2. Description of the Related Art In the field of color image processing, it is sometimes desired to perform processing only on a certain target area, such as cutting out an object or changing a color. These requirements are particularly remarkable in color image editing systems and painting systems, which are rapidly being commercialized for personal computers and workstations. These are largely different from image processing in remote sensing and medical systems, which mainly process the entire image, in that only the necessary parts need to be processed. In such partial processing, it is important in terms of processing efficiency and memory efficiency that a necessary area can be quickly detected and that area can be read and written as efficiently as possible. Therefore, the data structure also needs to be suitable for such partial processing. This is indispensable when the system is put into practical use, especially when a large number of target areas are scattered in a still image or when a large number of consecutive frames are processed like a moving image.

Color image data is usually stored as three primary color data for each pixel in a two-dimensional array. In this case, since the pixel value is basically described as a position function, it is necessary to read out the entire image and check whether or not the condition is satisfied for each pixel in order to detect the processing target area. .

By the way, there are a tree structure and a pyramid structure as effective methods for handling graphic information and image data. For example, if the data of a binary image is represented by a tree structure, the denser the information is, the finer the area is divided, so it is possible to manage the image data efficiently, and the white pixel is displayed at the specified position. Whether or not there is a black pixel can be searched at high speed. However, conversely, when it is desired to search for a target area, for example, a white pixel area, all of the lowest level nodes must be checked after all. If the information is very dense, in some cases the lowest level may be the pixel level. In any case, the search is less efficient in that all the lowest level nodes have to be examined. The tree structure can be applied to multi-valued image data, but the same applies in this respect.

On the other hand, the pyramid structure is effective when a low resolution image is processed and then a high resolution image is processed. However, in a low-resolution image, there is naturally missing information, so that it is unsuitable for the process of searching for all white pixel regions, for example.

As a conventional technique relating to color processing of color image data, Japanese Patent Laid-Open No. 182786/1988 discloses a technique relating to determination of an edge in a specified target region, and a technique for selecting a representative color for division in the target region. Japanese Patent Application Laid-Open No. 63-184475, Japanese Patent Application Laid-Open No. 63-18516 which discloses a technique of utilizing a color system other than the RGB color system in order to perform color conversion, lightness conversion, and data compression rate.
There is number 3. However, these conventional techniques are not suitable for searching a region having a designated color, nor do they disclose a data management method therefor.

[0007]

As described above, it is an object of the prior art to make it possible to search a region having a designated color in a color image at high speed. Therefore, an object of the present invention is to provide a color image area management method suitable for searching an area having a designated color, and to search for an area having a designated color at a high speed by using the method. It is to provide a search method of.

[0008]

[Means for Solving the Problems]

In order to achieve the above object, the color image area management apparatus of the present invention is such that the color of each pixel of the image data in which the color data of each pixel is represented by the three color system is the perceptual color system. A color class determining unit that determines which one of a plurality of color classes that are classified on the basis of, and that configures tree structure data that reaches a root node by using a block including at least one pixel as a leaf node. For each node in the structure data, the color index that stores the frequency of pixels having a color belonging to that color class for the pixels included in that node, and stores the calculated pixel frequency for each color class as a color index And a storage means.

In order to achieve the above object, a color image area management method of the present invention comprises a step of converting color data of each pixel of image data from a three color system to a perceptual color system, and a color based on the perceptual color system. A step of dividing the space into a plurality of color classes; a step of determining which color class the color of the pixel belongs to among the plurality of color classes; and a root including a block including at least one pixel as a leaf node. Composes tree-structured data up to a node, and for each node in the tree-structured data, calculates the frequency of pixels having a color belonging to that color class for each pixel included in that node, and for each color class. Storing the frequency of the selected pixels as a color index.

In order to achieve the above object, the color image area management system of the present invention includes an image input device for capturing an original image as image data represented by a three color system, and an output from the image input device. Storage means for storing image data represented by the three-color system, and a color of each pixel of the image data represented by the three-color system is based on the perceptual color system. Color class determining means for determining which one of a plurality of color classes classified according to the above, and tree structure data reaching a root node with a block including at least one pixel as a leaf node, and the tree structure data For each node in, the frequency of pixels having a color belonging to that color class is calculated for each pixel included in that node, and is calculated for each color class. It is characterized by having a color index storage means for storing the frequency of the pixel as a color indicator, the.

In order to achieve the above object, the color image area searching method of the present invention for searching the area of a color image using the tree structure data configured by the color image area management apparatus is based on a specified color. The steps of determining the color class to be searched, searching the tree structure data for the determined color class, and self-existing when the frequency of the pixels belonging to the determined color class is zero in each node other than the leaf node. Abort the search of lower nodes, and continue the search if not, and detect the block corresponding to the leaf node when the frequency of the pixels of the determined color class is larger than a predetermined value in the leaf node. Recording as an area of a color to be recorded.

[0013]

First, a general configuration of an image processing system to which the present invention can be applied will be described. The present invention can be applied to the image processing system as shown in FIG. This system includes an image input device 8,
The main memory 10, the auxiliary memory 12, the image processor 6, the display device 14, the keyboard device 18, and the pointing device 14 are included, but the present invention is not limited to this structure. An original color image (not shown) is converted into RGB data of a three color system by an image input device 8 such as a color scanner and stored in the auxiliary memory 12. The RGB data is converted into tree-structured data having a color index by the image processor 6 to which the present invention is applied, and the auxiliary memory 1 is again used.
Stored in 2. How to give a color index will be described in detail later. The RGB data and the tree structure data may be stored in separate memories. RGB for example
The data can be stored in the auxiliary memory 12 and the tree structure data can be stored in the main memory 10 in the image processor 6. By doing this, the data amount of the tree structure data is much smaller than the data amount of the RGB data.
Image retrieval processing can be performed at high speed. The image processor 6 has a tree structure data generation unit 2 according to the present invention.

FIG. 2 shows the structure of the tree structure data generation unit 2. The tree structure data generation unit 2 has a color system conversion device 20, a color class determination device 22, and a tree structure data conversion device 24. The memory 26 shown in FIG.
The main memory 10 and the auxiliary memory 12 of FIG. Hereinafter, the functions of the color system conversion device 20, the color class determination device 22, and the tree structure data conversion device 24 will be described in order.

The color system conversion device 20 represents the color data of each pixel with three attributes (hue, lightness and saturation) from the color data of the three color system represented by three primary stimuli or primary colors. Convert to perceptual color data. This color system conversion is performed as follows.

In this embodiment, R, which is one of the three color system, is used.
GB color system and CIE1976, which is one of the perceptual color systems
The conversion to and from the (L ^* , a ^* , b ^* ) uniform perceptual color space will be described as an example. Conversion from R, G, B to L ^* , a ^* , b ^* is performed according to the following formula. L ^* = 116 (Y / Y0) ¹ / 3−16 a ^* = 500 [(X / X0) ¹ / 3− (Y / Y0) ^1/3 ] b ^* = 200 [(Y / Y0) ^1/3 -(Z / Z0) ^1/3 ] X = XrR + XgG + XbB Y = YrR + YgG + YbB Z = ZrR + ZgG + ZbB where X, Y and Z are tristimulus values of the XYZ color system, X0, Y.
0 and Z0 represent tristimulus values of standard light, Xr to Xb, Yr to Yb, and Zr to Zb represent coefficients for conversion from the RGB color system to the XYZ color system.

At the 1975 CIE conference, metric
hue-angle (symbol H), metric li
ghness (symbol L ^* ), metric cro
The term ma (symbol C ^* ) was proposed. H and C ^* correspond to hue and saturation, respectively, and are given by the following equations. H = tan ⁻¹ (b ^* / a ^* ) C = (a ^{* 2} + b ^{* 2} ) ^{1/2 In the} present embodiment, these H, L ^* and C ^* are used. For convenience of explanation, these H, L ^*, and C ^* are referred to as hue (symbol H), lightness (symbol L), and saturation (symbol S) in this specification, respectively.

Although there are various types of three-color color system and perceptual color system other than the above, the above conversion is merely an example, and the present invention is not limited to which three-color color system and which perceptual color system. Can also be applied to. The color system conversion device 20 that performs such conversion can also be configured by a conversion table. Further, if necessary, the color system conversion device 20 may be further provided with means for performing an inverse conversion from the perceptual color system to the three-color color system. Depending on how the perceptual color system is selected, the saturation (sa
Chroma instead of
Is sometimes used, the term saturation is used herein to refer to saturation and chroma (ch).
Roma) will be used as a concept including both. Further, depending on how to select the perceptual color system, the perceptual chromaticity (chromaticness) in which the hue and the saturation are taken into consideration at the same time.
Is sometimes used, but the present invention can be applied to the case of such a perceptual color system.

Next, a method of determining the color class of each pixel by the color class determining device 22 will be described. The color class determining device 22 divides the color space of the perceptual color system represented by the three elements of hue H, lightness L, and saturation S into a plurality of areas (that is, color classes) (not shown). ) And a color class discrimination means (not shown) for discriminating which divided area (color class) the color of each pixel belongs to. There are various ways of dividing by the color space dividing means, but in the present embodiment, the division is performed as follows from a practical viewpoint. The H direction and the L direction are equally divided. Regarding the S direction, those with a saturation below a predetermined level are treated as achromatic. This is because if a low-saturation color is treated as a chromatic color, it may be classified into completely different hues due to slight noise. As described above, when the saturation having a predetermined level or less is treated as an achromatic color, the reliability of the color area search can be improved.

An example of the color space divided into a plurality of areas as described above is shown in FIG. In FIG. 3, the direction perpendicular to the paper surface is the axis of L. A small circle in the center is an area in which the saturation below a predetermined level is classified as an achromatic color. In the example of FIG. 3, the H direction is divided into 10 and S
The direction is divided into five parts including the achromatic color part (the chromatic color part is divided into four parts) and the L direction is divided into four parts (however, the L direction is not shown). The number of divisions i, j, and k in each direction of H, L, and S can be set freely. In the present embodiment, the H direction, the L direction, and the S direction (however, the chromatic color portion) are divided into equal parts, but they need not be equally divided.

The color class determining means of the color class determining device 22 uses the color space conversion device 20 to convert the R, G, B colors of each pixel represented by H, L, and S into which region of the color space. (That is, belonging to the color class) is determined as follows. Now, it is assumed that the H, L, and S values of a pixel are h, l, and s, respectively. When h belongs to the i-th region Hi in the H direction, l belongs to the j-th region Lj in the L direction, and s belongs to the k-th region Sk in the S direction, the color classes of the pixels are Hi, Lj, and Sk. It belongs to the color class C (Hi, Lj, Sk) determined by. The color class may be assigned only to the area where the color of the original image exists. For example, if the number of divided areas of the color space is two
If the color of the pixel of the original image exists in 50 of those areas, the number of color classes is set to 50. Of course, if you want to fill a part of the original image with a color that does not exist in the original image, you need a divided area of a color that does not exist in the original image. Regardless of the absence, let the number of color classes be the total number of divided areas.

Steps 100 to 11 in FIG.
2 is a simple flowchart showing the conversion of the color system by the color system conversion device 20 and the division of the color space (definition of the color class) by the color class determination device 22 described above.

Color class C (Hi, Lj, Sk) of each pixel
To determine H, L, and S of pixels in the vicinity of that pixel.
If the value of is taken into consideration, the reliability of color region search can be further improved.

There are various ways to consider the neighboring pixels. For example, with respect to the target pixel Px, y, as shown in FIG.
The averages h, l, and s of the values of H, L, and S are taken for a total of nine pixels including the target pixel Px, y, and the average h, l obtained in this way is calculated. It is possible to determine the color class of the target pixel Px, y depending on which of the divided areas in the H direction, the L direction and the S direction the s and s belong to.

RGB data 2 of the original image by the three color system
8, the perceptual color system HLS data 30 converted by the color system conversion device 20, and the color class data 32 determined by the color class determination device 22 are stored in the memory 26 (that is, the main memory 10 or the auxiliary memory 12). The HLS data 30 and / or the color class data 32, which are stored, are stored in RGB of the original image whenever necessary.
The data 28 may be used to directly acquire from the color system conversion device 20 and the color class determination device 22.

Next, the function of the tree structure data conversion device 24 for generating the tree structure data 30 using the color class determined by the color class determination device 22 will be described. The generated tree structure data 30 is stored in the memory 26 of FIG. 1 (that is, the main memory 10 or the auxiliary memory 12). For simplicity of explanation, in this embodiment, the tree structure is 4
The case of using a branch tree will be described, but the present invention is not limited to the quadtree.

When a quadtree is used as the tree structure, the RGB data 28 stored in the auxiliary memory 12 is (2 to the nth power).
It is divided into a plurality of X (2 to the nth power) blocks. For simplicity of explanation, n = 3 as the level of the tree structure,
That is, let us consider the case of four levels, n = 0 to 3. 6 to 9 conceptually show the relationship between the node NB and the block B of the image at each level of the tree structure. Node NB of the highest level (n = 0)
Is the root node, the lowest level node (n = 3) NBxxx
Is called a leaf node, and nodes NBx and NBxx at other levels (n = 1 or 2) are called intermediate nodes. In general, each minimum block Bxxx corresponding to a leaf node is composed of two or more pixels. Of course, it is also possible to configure one minimum block with one pixel.
If the minimum block is composed of a large number of pixels of 2 or more, the amount of memory required to store the tree structure data can be reduced, and the color area search can be performed at higher speed. Become. The number of pixels forming one minimum block can be determined in consideration of the characteristics of the original image and the pixel density of the image input device 8.

Here, the minimum block Bxxx is 2 × 2 = 4.
It is assumed that there are 64 pixels (m = 64) in total from the color class C1 to the color class C64. The color index I is from color class C1 to color class C64.
It is represented as an array of the color index elements i1 to i64 corresponding to each of them. Each element represents whether (or how much) a pixel having a color class corresponding to the element is included in the target block. The simplest expression method is to display each element in binary. For example, if a pixel having a color class corresponding to each element is included in the target block, the element is set to 1, and if not included, it is set to zero. Therefore, first, a color index in which each element is displayed in binary will be described.

For example, when all four pixels of the block B111 have the same color class C2, only the element i2 of the color index corresponding to the color class C2 is 1, so that the block B11
The color index IB111 of 1 is IB111 = (0, 1, 0, ...,
0) is defined. Similarly, when the color classes of the four pixels are all the same color class C3, the color index IB111 of the block B111 is IB111 = (0,0,1,0, ...,
0) is defined. When the color classes of the four pixels are the color class C1, the color class C2, the color class C3, and the color class C4, respectively, the color index IB1 of the block B111.
11 is defined as IB111 = (1,1,1,1,0, ..., 0). Next, a method of obtaining a color index for a node immediately above the lowest level node will be described. For example, the four smallest blocks B110, B111, B
Color index IB11 of block B11 composed of 112 and B113
Will be described as an example.

If the blocks B110, B111, B112 and B113 all have the same color index, the block B11 has the same color index. Color indicators IB110, IB111, IB112 and IB113 of blocks B110, B111, B112 and B113
, IB110 = (1,0, ..., 0), I
B111 = (O, 1,0, ..., 0), IB112 = (0,
0,1,0, ..., 0) and IB113 = (0,0,
0,1,0, ..., 0), the color index IB11 of the block B11 is IB11 = (1,1,1,1,0, ...
,, 0) is defined. In this way, the color index of the block immediately above the four blocks is the OR of the color indices of the four blocks immediately below itself.

With respect to the upper block Bx of the block Bxx and the upper block B of the block Bx, by repeating the same operation, the respective color indexes IBx.
And IB are obtained. By storing the color index thus defined for each node, the tree structure data to which the color index is added is generated.

The method of giving the color index described above is, in short, the simplest method of indexing what color class of pixels is included in the block.

Next, a method of giving a color index for further enhancing the reliability of color region search will be described.

According to the above-mentioned method of giving the color index, what color class of pixels is included in the block is indexed. In the second method described below, the color class of the block is determined. A color index is defined to indicate how many pixels are included.

In this second method, the frequency for the color class of the pixels contained in the block is calculated. In the simplest case, this frequency is calculated by counting the number of identical color classes. For example, block B
When all four pixels forming 111 are of the same color class C1, there are four pixels of color class C1 in total,
The color index IB111 of the block B111 is IB111 = (4,0,
..., 0) is defined. Similarly, when the color classes of all four pixels are the same color class C2, block B
The color index IB111 of 111 is IB111 = (0, 4, 0, ...
,, 0) is defined. Also, of these four pixels, one is color class C3 and the remaining three are color class C4.
, The color index IB111 of the block B111 is IB11.
1 = (0,0,1,3,0, ..., 0) is defined.

Next, how to obtain the color index for the node at the level immediately above the lowest level node will be described. For example, the four smallest blocks B110, B111, B
Color index IB11 of block B11 composed of 112 and B113
Will be described as an example.

The color indexes of the blocks B110, B111, B112 and B113 are IB110 = IB111 = IB112 = IB113 =
When it is (4, 0, ..., 0), the color index IB11 of the block B11 is defined as IB11 = (16, 0, ..., 0). Also, IB110 = (4,0, ...,
0), IB111 = (0, 4, 0, ..., 0), IB112
= (0,0,4,0, ..., 0), IB113 = (0,
0,0,4,0, ..., 0), the color index IB11 of the block B11 is IB11 = (4,4,4,4,4).
0, ..., 0). Also, IB110 =
(1, 2, 1, 0, ..., 0), IB111 = (0,
1, 2, 1, 0, ..., 0), IB112 = (0, 0,
1,2,1,0, ..., 0), IB113 = (0,0,
0, 1, 2, 1, 0, ..., 0), the color index IB11 of the block B11 is IB11 = (1, 3, 4,
4, 3, 1, 0, ..., 0). As can be seen from these examples, IBxx is configured to have as its respective elements the sum of the values of the corresponding elements of the four immediately lower blocks IBxxx. The same applies to IBx and IB. That is, the color index of the immediately upper block of the four blocks is configured to have the sum of the values of the corresponding elements of the color indexes of the immediately lower four blocks of the self as the respective elements of the self.

In the above example, the frequency of the color class of the pixels included in the block is, as the simplest example,
Although the number of the same color class is counted and the count value is used as it is, the total number of pixels included in the block is quantized to determine which quantization level the total number of pixels of the color class under consideration belongs to. You may give as a frequency about a class. For example, it is assumed that a block (which may be a block of any level) is composed of 100 pixels. This is divided into ranges of 0, 1 to 10, 11 to 20, 21 to 30, ..., 91 to 100. Now, for example, paying attention to a certain color class, the frequency is 0 if the number of pixels of the color class is 0, and the frequency is 1 to 11 if it is in the range of 1 to 10.
The frequency is defined to be 2 in the range of 20 to 20 and 3 (hereinafter, the same) in the range of 21 to 30. The degree and method of quantization are not limited to this example.

When the total number of pixels included in a block is quantized and the quantization level to which the total number of pixels of the color class under consideration belongs is given as the frequency for that color class, the tree structure data is generated. Flow chart is shown in FIG.
And steps 200 to 236 of FIG.

Next, a search for a color area using the tree structure data 30 given a color index by the tree structure data generation unit 2 will be described. The color area search is performed by the search unit 4 shown in FIG. The color area search is necessary, for example, when the operator wants to change a certain color area to another color. In this case, first, it is necessary to detect the blocks in the area of that color just enough. Various methods can be considered for the color designation by the operator. For example, a method of designating a color by using a pointing device such as a mouse to move a cursor to an arbitrary position in a region having a desired color on the display screen and specifying a pixel by the cursor can be considered. As described above, the information regarding the color of the pixel can be stored in any of the RGB data 28, the HLS data 30 and the color class data 32. When the color data of a pixel is stored in the form of color class data, the color class C (Hi, Lj, Sk) of the pixel is directly specified by specifying the pixel with the cursor. If the pixel color data is stored in the form of HLS data,
The color class of the pixel is specified by converting the HLS data into color class data using the color class determining device 22. If the color data of the pixel is stored in the form of RGB data, the RG is converted using the color system conversion device 20.
The color class of the pixel is specified by converting the B data into the HLS data and further converting the HLS data into the color class data by the color class determining device 22.

As another method, a plurality of pixels may be designated in a region having a desired color and the color class having the largest number may be set as the color class of the region, or the average of a plurality of pixels may be specified. May be taken as the color class for that region. This average is taken in the same manner as in the case of determining the color class described above, taking the average of each of hue, lightness, and saturation. For example, if the pixel color data is H
When stored in the form of LS data, HLS data of each pixel of these plurality of pixels is used to generate H, L and S.
Take the respective averages h, l and s of the values of, and let the color class determined by these h, l and s be the color class of the region.

As another method, a color sample based on the color class may be displayed on the display screen in addition to the image, and the operator may directly specify the sample to specify the color class.

As another method, the color class may be specified by directly inputting the values of H, L and S or the number of the color class from the keyboard device 18 or the like.

The color class C (H
i, Lj, Sk) is searched for tree structure data having a color index for each node. The identified color class C (Hi,
By searching the tree structure data not only for Lj, Sk) but also for the color class C ′ in the vicinity thereof, it is possible to further enhance the reliability of the color region search. Color class C (Hi, Lj, S
For k), the neighboring color class C ′ exists in each of the H direction, the L direction, and the S direction. That is, the neighboring color class C ′ exists three-dimensionally close to the color class C in the color space. The degree of neighborhood color class C ′ to be searched can be freely set according to various conditions such as the nature of the original image and the number of color class divisions.

The degree of neighborhood color class C ′ to be searched is the same in any direction of the H direction, the L direction and the S direction. Therefore, for example, consider the H direction as shown in FIG. And the specified color class C
Hi with a slightly different hue Hi of (Hi, Lj, Sk)
−1 and Hi + 1 are the closest color classes from the viewpoint of the hue H to the color class C (Hi, Lj, Sk). As shown in the figure, a color class C '(Hi-1, Lj, Sk) and a color class C'in the vicinity of the color class C (Hi, Lj, Sk).
(Hi + 1, Lj, Sk) is the color class C (Hi, Lj,
If the weight of Sk) is 1, the weight W is relatively small (W <1). The range of the neighboring color classes is Hi-2 and Hi + 2, Hi-3 and Hi +.
In the case of further widening like 3, ..., Smaller weights may be given in order as the distance from Hi increases. For the weights of the neighboring color classes, different values may be used in the H direction, the L direction, and the S direction in consideration of the number of divisions in the H direction, the L direction, and the S direction, the characteristics of the original image, and the like. it can.

As a simple example, for the target color class C (Hi, Lj, Sk), only the two neighbors in each of the H direction, L direction, and S direction are neighboring color classes, and their weights are The weight of color class C is set to 1 and W
Consider the case of h, Wl and Ws. Then, the total number of neighboring color classes is 27 (= 3 × 3 × 3) including the color class C (Hi, Lj, Sk). The weights of these neighboring color classes are obtained by adding the weights in the H direction, the L direction, and the S direction for each color class. For example, the neighboring color class C '(Hi-1, Lj-
1, Sk−1) has a weight W of W = Wh + Wl + Ws, and a neighboring color class C ′ (Hi-1, Lj, Sk-1)
Weight W is W = Wh + 1 + Ws, and the color class C (H
The weight W of i, Lj, Sk) is W = 1 + 1 + 1 (= 3). If the weights of these color classes are standardized with the weight of the target color class C being 1, for example, the weight W of the neighboring color class C ′ (Hi-1, Lj-1, Sk-1) is W = 1/3 (Wh + W1 + Ws), and the weight W of the neighboring color class C ′ (Hi-1, Lj, Sk-1) is W = 1/3 (Wh + 1 + Ws). A color class whose weight W is not zero with respect to the target color class is called a neighboring color class. Note that if the neighboring color class is simply defined, it is sufficient to set the weights of the neighboring color classes to all 1. The determination of the weights as described above is very useful for block detection in leaf nodes, which will be described later. This point will be described in detail later.

Since the color of the neighborhood color class defined as described above is a color that is perceptually close to the color of the target color class, the reliability of the color area search can be improved. Therefore, in order to detect the block including the specified color, the color index quadtree is traced from the top and the color index of the color class of the specified color and the color indexes of the neighboring color classes of the color class are examined. Good. In the intermediate node,
If the color index of the color class of the designated color and its neighboring color class is zero, the node is inferior to that color index, so the search is terminated. As long as these color indices are not zero, the lower nodes are examined in order, and when the lowest node, that is, a leaf node is reached, the block (minimum block) corresponding to that leaf node is detected as follows. Determines if the block should be. The search method may be either depth-first search or breadth-first search. Preferably, a recursive method is used so as to simplify the search algorithm.

It is now assumed that the color index of the color class C (Hi, Lj, Sk) is not zero, which leads to one leaf node corresponding to the smallest block having pixels of that color class. When the color index is represented by a binary value of zero or one (hereinafter, also referred to as binary display), this block is recorded as a block to be detected. When the color index is represented by frequency (hereinafter also referred to as frequency display), when the block has a frequency exceeding a predetermined threshold value, the block is recorded as a block to be detected. By the way, the block corresponding to the leaf node searched because the color index of the color class C (Hi, Lj, Sk) is not zero includes the pixels of the color class C and the pixels of the neighboring color class C ′. In some cases, the predetermined threshold value may not be reached and the block may not be detected well just by examining the frequency of pixels of color class C. Therefore, in a preferred embodiment, a weighted sum of the frequency of pixels of the color class C and the frequency of pixels of the neighboring color class C ′ is taken in consideration of the weight of the above-mentioned neighboring color class C ′, and the weighted sum in consideration of the weight is taken. This problem is solved by setting the pixel frequency calculated as the pixel frequency to be compared with a predetermined threshold value. This threshold can be freely set according to the case, and it is more convenient if it can be dynamically changed. Even when the search reaches a leaf node because the color index of the neighboring color class C ′ is not zero, the frequency of the pixels of the neighboring color class C ′ and the neighboring color class C are similarly considered in consideration of the weight of the neighboring color class C ′. 'Is taken as the weighted sum of the pixel frequency, and the pixel frequency calculated as the weighted sum considering the weight is the frequency of the pixel to be compared with a predetermined threshold value, and when this exceeds the predetermined threshold value, Record the block as the block to be detected. When the color index is represented by a binary value of 0 or 1, the weight W of the neighboring color class needs to be set to 1. When the color index is represented by a binary value of 0 or 1, even if there is only one pixel of the color belonging to the specified color class in one minimum block composed of a plurality of pixels, Since a block is recorded as a block to be detected, it is good in that there is no omission in detection, but on the contrary, there is a possibility that a block that should not be detected will be detected. Therefore, if it is desired to detect a block having a specified color as accurately as possible, the color index is represented by the frequency of the color class as described above, and a block having a frequency exceeding a predetermined threshold is recorded as a block to be detected. Good to do. Even when the color index is represented by a binary value of zero or one (binary display), if the predetermined threshold value is considered to be 1, it is frequency display in a broad sense.

On the other hand, the amount of memory required to store the tree structure data is smaller in the binary display than in the frequency display. Therefore, in the preferred embodiment, the tree-structured data is configured such that the color index is displayed as frequency only for the leaf node and the color index is displayed as binary for the nodes other than the leaf node. By doing this, it is possible to detect the blocks having the specified colors without excess or deficiency while suppressing the amount of memory required to store the tree structure data (thus enabling the color area search to be performed faster). can do.

By the way, the color designated by the operator is located at the center of each of the divided regions Hi, Lj and Sk in the H direction, the L direction and the S direction, except when the color class is directly designated. Not necessarily. Therefore, if the specified color does not come to the center of the divided area, by changing the weight of the neighboring color class according to the deviation from the center,
The deviation is reflected.

As shown in FIG. 16, when the designated color is deviated from the center in a certain divided area Hi in the H direction (in this example, it is deviated from the center to the Hi + 1 direction), a simple example is designated. There is a range with a weight of 1 centered on the specified color with a width of 1 class, and W is placed on both sides of it.
Assuming that each range having a weight of 1 exists with a width of one class, the divided regions Hi-1, Hi, Hi + 1 and H
The weights of the divided regions Hi-1, Hi, Hi + 1 and Hi + 2 are determined so that the areas of i + 2 regions are equal to each other. For example, taking the divided region Hi-1 as an example, the weight Wi-1 of the divided region Hi-1 is a quadrangle abcd.
The area S1 of quadrangle efcg is equal to the area S2 of quadrangle efcg. In addition to the weights in the H direction, the weights in the L direction and the S direction are determined in the same manner, and the weights in the H direction, the L direction, and the S direction thus determined are determined for each color class. Define a neighborhood color class by adding. The method of adding weights in each direction is the same as in the above case. By changing the weight of the neighboring color class according to the shift from the center as described above to reflect the shift, the range of the neighboring color class does not consider the shift from the center of the color class of the specified color. It will be set slightly wider than the case.

FIG. 12 to FIG. 14 exemplify the flow chart of the color area search described above. 12 is a flow chart of the entire color region search, FIG. 13 is a flow chart of the block search executed in steps other than the leaf node in step 306 of FIG. 12, FIG.
4 is a flow chart of the block search executed in the leaf node in step 306 of FIG. Figure 1
The weighted sum of the color indices calculated in step 502 of 4 is the frequency of the color class calculated in consideration of the weight of the above-mentioned neighboring color class C ′.

[0053]

As described above, according to the present invention, by constructing the tree structure data in which the color index based on the perceptual color system is given for each node, the search of the color area in the color image can be performed at high speed and reliably. It becomes possible to do.

[Brief description of drawings]

FIG. 1 is a diagram showing a configuration of a tree structure data generation unit 2 according to an embodiment of the present invention.

FIG. 2 is a diagram showing a configuration of an embodiment of an image processing system to which the present invention is applied.

FIG. 3 is a diagram showing an example of a color space divided into a plurality of regions according to the present invention.

FIG. 4 is a flow chart of defining a color class according to an embodiment of the present invention.

FIG. 5 is a diagram showing neighboring pixels to be considered when determining a color class of a pixel.

FIG. 6 is a diagram conceptually showing a relationship between a node and a block in a root node of a tree structure.

FIG. 7 is a diagram conceptually showing a relationship between nodes and blocks in an intermediate node of a tree structure.

FIG. 8 is a diagram conceptually showing a relationship between a node and a block in an intermediate node of a tree structure.

FIG. 9 is a diagram conceptually showing a relationship between a node and a block in a leaf node of a tree structure.

FIG. 10 is a flow chart of tree structure data generation according to an embodiment of the present invention.

FIG. 11 is a flow chart of tree structure data generation according to an embodiment of the present invention.

FIG. 12 is an overall flowchart of a color area search according to an embodiment of the present invention.

FIG. 13 is a flowchart of block search executed in steps other than leaf nodes in step 306 of FIG.

14 is a flow chart of block search executed by a leaf node in step 306 of FIG.

FIG. 15 is a diagram for explaining how to give weights to neighboring color classes.

FIG. 16 is a diagram illustrating how to assign weights to neighboring color classes when the designated color deviates from the center of the color class.

[Explanation of symbols]

 2 Tree Structure Data Generation Unit 4 Search Unit 6 Image Processor 8 Image Input Device 10 Main Memory 12 Auxiliary Memory 20 Color System Conversion Device 22 Color Class Determining Device 24 Tree Structure Data Conversion Device

 ─────────────────────────────────────────────────── ─── Continuation of the front page (72) Inventor Machiko Sato 7-53-27 Tomiokanishi, Kanazawa-ku, Yokohama, Kanagawa 7-53-27 (56) Reference JP-A-3-262079 (JP, A) JP-A-3-174657 ( JP, A) JP 3-174658 (JP, A) JP 62-68384 (JP, A) JP 63-143626 (JP, A) JP 62-279468 (JP, A) JP Sho 62-50618 (JP, A) Actually opened Sho 62-62374 (JP, U)

Claims (13)

[Claims] 1. For each pixel of image data in which color data of each pixel is represented by a three-color system, which of a plurality of color classes the pixel color belongs to is classified based on the perceptual color system. And a tree structure data that reaches a root node by using a block including at least one pixel as a leaf node, and for each node in the tree structure data, a color of a pixel included in the node is determined. A color image area management device comprising: a color index storage unit that calculates a frequency of pixels having a color belonging to the color class for each class and stores the calculated frequency of pixels as a color index. 2. The frequency of the pixel is one of the logical values when, for each node in the tree structure data, there is a pixel having a color belonging to that color class for each pixel included in the node. 2. The color image area management device according to claim 1, wherein when there is no pixel having a color belonging to the color class, it is calculated as a binary number which is the other logical value. 3. The frequency of the pixel is calculated for each node in the tree structure data as a count value of the number of pixels having a color belonging to the color class for each pixel included in the node. Item 2. The color image area management device according to item 1. 4. The frequency of the pixel is such that when a node in the tree structure data is a leaf node, a pixel having a color belonging to the color class exists for each pixel included in the node. Is a logical value of one, and when there is no pixel having a color belonging to that color class, it is calculated as a binary number that is the other logical value, and when the node in the tree structure data is not a leaf node, The color image area management device according to claim 1, wherein the color image area management device is calculated as a count value of the number of pixels having a color belonging to the color class for each included pixel. 5. The color image area management device according to claim 3, wherein the count value of the pixel is quantized. 6. The color image area management device according to claim 1, wherein the number of pixels included in the block corresponding to the leaf node is two or more. 7. The color image area management device according to claim 1, wherein the number of pixels included in the block corresponding to the leaf node is one. 8. The conversion means for converting the color data of each pixel of the image data from the three color system to the perceptual color system, and the color space based on the perceptual color system into a plurality of color classes. 8. The color image area management device according to claim 1, further comprising: a unit that determines which color class the color that has been divided and converted into the perceptual color system by the conversion unit belongs to. 9. The color image area management device according to claim 8, wherein said color class determining means determines the color of the pixel as an achromatic color class when the color saturation of the pixel is smaller than a predetermined value. 10. A step of converting color data of each pixel of image data from a three color system to a perceptual color system, a step of dividing a color space based on the perceptual color system into a plurality of color classes, and a color of the pixel. Determines which of the plurality of color classes belongs to the color class, and configures tree-structured data reaching a root node with a block including at least one pixel as a leaf node, and the tree-structured data. For each node in, the frequency of pixels having a color belonging to the color class is calculated for each pixel included in the node, and the frequency of the pixel calculated for each color class is stored as a color index. A color image area management method having the same. 11. An image input device for capturing an original image as image data represented by a three-color color system, and a memory for storing image data represented by the three-color color system output from the image input device. Means, and for each pixel of the image data in which the color data of each pixel is represented by a three-color system, which of a plurality of color classes the color of the pixel belongs to is classified based on the perceptual color system. And a tree structure data that reaches a root node by using a block including at least one pixel as a leaf node, and for each node in the tree structure data, a color class for a pixel included in the node. And a color index storage unit that stores the frequency of pixels having a color belonging to the color class and stores the calculated pixel frequency for each color class as a color index. Color image area management systems. 12. A color image area search method for searching a color image area using tree structure data configured by the color image area management device according to claim 1, wherein the search is performed based on a designated color. The step of deciding the color class to be done, the step of searching the tree structure data for the decided color class, and in each node other than the leaf node, if the frequency of the pixels belonging to the decided color class is zero, Abort the search of the lower node, otherwise continue the search, and in the leaf node, detect the block corresponding to the leaf node if the frequency of pixels of the determined color class is greater than a predetermined value. A step of recording the color image area as a power color area; 13. The color image area searching method according to claim 12, wherein the color class to be searched is a color class to which a designated color belongs and a color class which is perceptually close to a color class to which the designated color belongs. .