JPH06225154A - Data compression coding method for color picture - Google Patents

Abstract

PURPOSE:To attain efficient coding by mapping picture elements onto a parameter space, applying clustering to the picture elements on the space, dividing the space into areas and coding individually division information, lightness information and chromaticity error information. CONSTITUTION:A color space transformation section 10 transforms an input RGB signal into an Luu signal and a feature space transformation section 20 transforms the transformed signal into a point Luu in the feature space. An area division section 30 adopts the ISODATA method to implements 2-dimension clustering and to divide the area. Then an area information coding section 42 codes the information subjected to area division on a chromaticity space and a lightness information coding section 44 applies orthogonal transformation to a lightness signal L to implement coding. Furthermore, a chromaticity error information coding section 46 hardly detects deterioration in the chromaticity in comparison with the lightness, error information between an area division picture and an original picture is thinned to implement coding by orthogonal transformation. Each picture element is mapped on a feature space and clustered in this way, the efficient coding is executed.

Description

Detailed Description of the Invention

[0001]

BACKGROUND OF THE INVENTION 1. Field of the Invention The present invention relates to a color image data compression coding capable of efficiently describing various images such as a structural description of an image and extraction of a specific region and color correction. It is about the method.

[0002]

2. Description of the Related Art A technique for reducing the redundancy of image data having an enormous amount of information and compressing the amount of data to reduce the transmission / storage cost is a high efficiency coding such as orthogonal exchange and vector quantization. Has been realized as a law. The purpose of these encodings was to reduce the amount of data while maintaining good image quality.

In contrast to such high-efficiency coding, in recent years, structure information such as edge information and area information of an image is extracted and coded separately from other waveform information. A method called split coding has been studied.

An important technique for performing such encoding is a region division method by clustering on a color space. As shown in FIG. 1, the conventional area division method maps pixels in an image plane into a color space (for example, RGB color space) and uses a cluster boundary set according to a distance from a cluster centroid in the space. This is a method of classifying each pixel and labeling 1, 2, 3, etc. by the above clustering, obtaining an area-divided image by inverse mapping on the image plane, and performing area division.

[0005]

According to this conventional method, when the pixels in the same area are always localized in a specific place on the color space, the area can be properly divided, but it is not so in the actual image. In many cases. Therefore, even though they are the same area, they are divided into a plurality of areas, different areas are regarded as one area, and there are many problems in using them independently.

The present invention has been made to solve the above-mentioned conventional problems, and proposes a new clustering method based on a model of distribution of an image in a color space, from a viewpoint completely different from the conventional method. In addition to solving the above-mentioned problems, a method for compressing and compressing data of a color image is provided, which enables efficient processing and processing of various images such as extraction of a specific area and color correction by this method. The purpose is to

[0007]

According to the present invention, when a color image is divided into regions, the characteristics of the distribution in the color space estimated from the reflection model of the object are changed from "black" to "object color" to "white". By modeling as a curve leading to, and mapping each pixel on a parameter space that distinguishes the curve, a distribution in which pixels in the same region are localized at a specific place is obtained, and clustering is performed on that space. The above-described object is achieved by performing region division by performing the above process and separately encoding the obtained region information and brightness information.

Further, the chromaticity error information between the area-divided image obtained by the area division and the original image is also encoded separately.

Furthermore, when encoding the chromaticity error information, thinning is also used.

[0010]

In general, an image is photographed by illuminating an object having a three-dimensional spread with illumination light, passing the reflected light through an appropriate lens system, and mapping the reflected light on a two-dimensional plane.

One object has the same spectral reflectance, that is, the same color, and various gradations occur depending on the relationship between the angle of the illumination light and the surface of the object and the position of the viewpoint. However, this gradation changes along a certain curve in the color space. The reason is that in the area of the object surface where the line of sight to the object is close to the exit angle determined by the incident angle when the illumination light is incident on the surface of the object, which is shaded and the area to which the illumination light does not reach become black. In many cases, it is a specular reflection state, which is a so-called catch light place. In this part, the illumination light reflects light of all wavelengths with a certain reflectance, so it becomes the same “white” as the illumination light, and in the middle part, the object surface is diffusely reflected and the reflectance is different with respect to the line-of-sight angle. Since it has a distribution, pixels in the same area (same object) are
In the color space (for example, L * u * v * space), it is considered that there is a tendency to concentrate on the curve of black → object color → white as shown in FIG. You can confirm that you are doing. Here, L * represents lightness, the distance from the L * axis in the u * v * plane represents saturation, and the rotation angle represents hue.

Therefore, when viewed from the entire image, there are a plurality of banana-shaped distributions such as a bent ellipsoid as shown in FIG. 2 corresponding to the number of regions (the number of objects) as shown in FIG. Become.

However, in the conventional method, since these matters are not taken into consideration at all, as shown by a broken line in FIG. 4, even though the same area (object) is divided into a plurality of areas, or in FIG. As shown by the broken line, different regions (objects) may be regarded as one region, and the conventional clustering method is incomplete as a region division method.

In the present invention, the problem of the conventional method is solved by performing clustering so as to separate a plurality of bent ellipsoidal distributions corresponding to respective regions based on the above-described distribution model.

The clustering method of the present invention will be described in detail below.

Now, as shown in FIG. 6, a color space (for example, L * u
Consider a group of curves passing through a point A representing "black" and a point B representing "white" on the * v * space). Then any pixel becomes
Although represented as one point in the color space, it always belongs to one curve in the curve group. That is, one curve corresponds to one pixel.

Since two parameters for distinguishing each curve are sufficient, each pixel can be represented by mapping to one point on a two-dimensional parameter space. As an example of this curve group, consider a set of semi-ellipses passing through points A and B as shown in FIG. 7, and move the position of the origin on the lightness axis according to L = L * -50 ... (1) The range of L * is 0 ≦ L * ≦ 10
Normalize to 0.

Here, since the plane where one semi-ellipse intersects the L = 0 plane is uniquely determined, the semi-elliptic curve group has parameters (u *, v *) coordinate values (μ, ν) of this intersection. Can be converted.

Therefore, each pixel can be mapped on the L = 0 plane by a kind of projective operation along the semi-ellipse.

When the distribution of the actual image in the color space is as shown in FIG. 8, for example, such mapping results in the distribution shown in FIG. 9 on the (μ, ν) plane. It is possible to obtain a localized distribution for each region. In this way, efficient mapping can be performed by mapping the feature space and then using a normal clustering method.

According to the present invention, the area division information, the other brightness information, and the chromaticity error information obtained in this way are separately thinned and separately coded to realize coding with high added value. To be done.

[0022]

Embodiments of the present invention will now be described in detail with reference to the drawings.

An apparatus for carrying out this embodiment is shown in FIG.
As shown in FIG. 3, the color space conversion unit 10, the feature space conversion unit 20, the region division unit 30, the encoding unit 40, the decoding unit 50, and the inverse conversion unit 60 are included. Also, the encoding unit 4
0 indicates the area information encoding unit 42 and the lightness information encoding unit 44.
And a chromaticity error information encoding unit 46, and a decoding unit 50.
Is an area information decoding unit 52 and a brightness information decoding unit 54.
And a chromaticity error information decoding unit 56.

The color space conversion unit 10 receives the input image signal,
For example, an RGB signal is converted into an L * u * v * signal. RG
B to XYZ coordinate system tristimulus values XYZ, XYZ to L
Conversion to * u * v * has been established and RGB to XY
The conversion to Z is defined by the following equation (see Makoto Miyahara “Systematic Image Coding” IPC Co., Ltd., page 134).

[0025]

[Equation 1]

The conversion from XYZ to L * u * v * is
It is defined by the following formula (see "Image Analysis Handbook" edited by Mikio Takagi and Yoshihisa Shimoda, pages 107-108 of the University of Tokyo Press).

[0027]

[Equation 2]

Here, (X0, Y0, Z0) is (X, Y, Z) for a perfect diffuse white surface under a standard light source.
And the value of standard light source C (color temperature 6774K),
(X0, Y0, Z0) = (98.072, 100.0
0, 118.225).

In this embodiment, L * u * v * is used as the color space.
Although the color system is used, the equivalent effect can be obtained by considering an appropriate curve group that passes through “black → object color → white” in other color spaces such as the L * a * b * color system. Can be expected.

The conversion unit 20 to the feature space is (L *,
u *, v *) is a point (L,
μ, ν). From FIG. 11, the conversion formula is obtained by algebraic geometry, and is as follows.

[0031]

[Equation 3]

The area dividing unit 30 samples all images, creates training data from the values of (μ, ν) for each pixel, and ISODATA (Itera
tiveSelf Organizing Data Analysis Techniques
) Method for two-dimensional clustering (see “Image Analysis Handbook” supervised by Mikio Takagi and Yohisa Shimoda, pages 648-651 of the University of Tokyo Press).

In the ISODATA method, an appropriate cluster is given as an initial state, and its members are recombined to gradually obtain a "better cluster", which is a representative method of non-hierarchical clustering (relocation method). , Is a method that has been known since ancient times.

The procedure of this ISODATA method is shown in FIG.

In this ISODATA method, first in step 100, parameters such as relocation convergence conditions, minute clusters, isolated data determination conditions, and split / fusion branch conditions are set.

Then, in step 102, the center of gravity of the initial cluster is determined. For example, the total average can be used with the number of initial clusters being 1.

Then, in steps 104 to 108, the rearrangement method is performed. Specifically, first, step 104
Then, the distance between each piece of data and the center of gravity of the cluster is calculated, and each piece of data is arranged in the cluster having the smallest distance.
Then, in step 106, the center of gravity of each cluster is recalculated and corrected in the rearranged clusters. Then
In step 108, if the average of the distance between each data and the cluster centroid does not change as a result of the rearrangement / correction of the centroid, it is considered to have converged, and otherwise returns to step 104 to repeat.

After the rearrangement method is completed, the process proceeds to step 110,
Small clusters with a significantly small amount of data and isolated data that are significantly separated from other clusters are excluded from subsequent clustering.

Next, in step 112, when the minimum value of the distance between the cluster centroids is greater than or equal to a certain threshold value and the maximum value of the variance of the cluster is less than or equal to a certain threshold value, it is determined that the clustering has converged and the clustering ends. Otherwise, go to steps 114 and / or 116.

If the minimum distance between the cluster centroids is less than or equal to a threshold value, the process proceeds to step 114, the cluster pairs are integrated, and a new cluster centroid is calculated.

On the other hand, if the maximum value of the variance of the cluster is equal to or more than a certain threshold value, the process proceeds to step 116, the cluster is divided until the maximum value of the cluster variance is equal to or less than the threshold value, and a new cluster centroid is calculated. .

Integration by step 114 or step 1
After the division by 16 is completed, the process returns to step 104 again to repeat the processing.

In this way, cluster division (cluster boundaries are indicated by broken lines) and cluster representative points 1, 2, 3 (indicated by circles) as shown in FIG. 13 are obtained.

As described in the section of the operation of the invention, each of the representative points 1, 2, and 3 corresponds to one semi-ellipse that represents the area as shown in FIG. After that, it is determined which half ellipse each pixel belongs to, and the representative point (cluster centroid) (μ ₀ , ν ₀ ) representing the half ellipse is
The value of that pixel is used as a label, and the region division is completed. The image thus obtained is called a region-divided image.

The area information coding unit 42 codes the information divided into areas in the chromaticity space. Since (μ ₀ , ν ₀ ) is the cluster centroid when clustering is performed, the number of possible values is about 16 to 32, and 4 to 5 per pixel.
It can be expressed in bits. Therefore, the region-divided image is labeled by the list (about 16 to 32) of cluster representative values (μ ₀ , ν ₀ ) and the cluster representative value number i (represented by 4 to 5 bits) for each pixel. Performed (called a labeling image). Further, since adjacent pixels are easily mapped to the same representative value, run length coding using this (see Masao Sakauchi “Image Database” Shokoido, P.136-P.140), or only area boundary pixels Further compression can be achieved by using a lossless encoding such as a chain encoding for tracking (see Masao Sakauchi “Image Database” Shokoido, P.91-P.103).

The lightness information encoding unit 44 encodes the L signal indicating the lightness. When RGB signals are mapped to points (L, μ, ν) on the feature space, L is the lightness,
(Μ, ν) is a signal corresponding to chromaticity. Human visual characteristics are more sensitive to changes in brightness than chromaticity, and deterioration of brightness information is easily detected. In particular, if there is blurring or rattling at the edge portion of the image, it will be felt as a great deterioration in image quality. Therefore, orthogonal transform coding such as DCT (discrete cosine transform) is used for coding the L signal (Makoto Miyahara "Systematic Image Coding" IPC, P.9 to P.11, P.3).
3 to P37), the bit allocation to the high frequency component must be larger than the chromaticity.

The chromaticity error information encoding unit 46 thins out the error information between the area-divided image and the original image and encodes it. The error between the area-divided image (μ ₀ , ν ₀ ) and the original image (μ, ν) is calculated by the following formula.

Δμ = μ−μ ₀ (9) Δν = ν−ν ₀ (10)

Since the deterioration of chromaticity is harder to detect than the brightness, the error image is, for example, 1 / horizontal in both the vertical and horizontal directions.
2 is thinned, and orthogonal transform coding such as DCT is performed on the thinned image. At this time, the bit allocation to the high frequency component may be less than the brightness.

The area information decoding unit 54 restores the list of cluster representative values and the cluster representative value number i for each pixel from the area information encoded data. Restored
By referring to the list of cluster representative values from i, (μ ₀ , ν ₀ ) for each pixel is restored to obtain a region-divided image.

The lightness information decoding unit 54 restores the signal L corresponding to the lightness from the lightness information encoded data by an orthogonal transform decoder such as DCT.

The chromaticity error information decoding unit 56 restores and interpolates the chromaticity error signal (Δμ, Δν) from the encoded chromaticity error information data by the orthogonal transform decoder, and the following formula μ = μ ₀ + Δμ (11) ν = ν ₀ + Δν (12) The signal (μ, ν) corresponding to chromaticity is restored.

Further, since the restored signal is Lμν, the inverse converter 60 inversely converts this to an L * u * v * signal. This inverse transformation is given by the following equation.

[0054]

[Equation 4]

This L * u * v * is further returned to an RGB signal. The formula for converting L * u * v * into XYZ is as follows.

[0056]

[Equation 5]

The conversion from XYZ to RGB is defined by the following equation.

[0058]

[Equation 6]

A final restored image is obtained by the above inverse transformation.

[0060]

As described above, in the present invention, the characteristic of the distribution in the color space estimated from the reflection model of the object is modeled as a curve from "black" to "object color" to "white". , Since the clustering is performed on the parameter space that distinguishes the curves, the pixels in the same region tend to be localized at a specific place on the parameter space, and as a result,
It is possible to obtain a better division compared to the conventional area division method. By separately encoding the area division information and other lightness information and chromaticity error information obtained in this way, the efficiency can be improved. Has achieved good encoding.

Further, the encoding method according to the present invention is characterized by not only being highly efficient but also describing the image structurally,
When constructing an image database, processing / processing or transmitting an image, various added values as described below occur.

First, since the encoded data includes data representing area information, it is only necessary to specify "ON (object part)" or "OFF (background part)" for each area. Can be extracted, and it becomes unnecessary to newly perform area division such as clustering on the restored image when the background portion is erased when a product catalog or leaflet is printed.

Secondly, as described above, the specific area can be easily extracted and only the color correction information for each area is added to the encoded data to obtain the color-corrected image at the next restoration. You can Therefore, it is not necessary to bother to compress and re-save the color-corrected image in the database in order to use it again. Further, even when an image before color correction becomes necessary, the original image can be reproduced at any time by restoring without using the color correction information.

Thirdly, usually, the problem of image rotation / magnification is the deterioration of the edge portion, but in the area division coding, the coded data includes data representing the area information. Therefore, by rotating and scaling only this information with high accuracy, high-quality rotation and scaling can be realized.

Fourthly, even if only the data representing the area information is restored, the rough structure can be grasped, so that high-speed retrieval can be performed using this image.

Fifth, the data representing the area information is transmitted first, and the other waveform information is sequentially transmitted, so that at the initial stage of the transmission, whether the image required by the receiver or not is required. Since the determination can be made, the reception can be stopped in the middle of the transmission, and the transmission cost can be reduced.

As described above, the encoding according to the present invention has various excellent effects.

[Brief description of drawings]

FIG. 1 is a diagram illustrating a conventional clustering method on an RGB color space.

FIG. 2 shows L * u * v * for explaining the principle of the present invention.
Diagram showing an example of distribution of object color of one object in space

FIG. 3 is a diagram similarly showing an example of distribution of object colors of a plurality of objects in the entire image.

FIG. 4 is a diagram showing an example of a division result by a conventional clustering method in an L * u * v * space.

FIG. 5 is a diagram showing another example in the L * u * v * space.

FIG. 6 is a diagram showing points representing “black” and “white” on the L * u * v * space for explaining the clustering method of the present invention.
Diagram showing a group of curves passing through points

FIG. 7 is a diagram showing a state in which the range of L * can be normalized.

FIG. 8 is a diagram showing an example of distribution of an actual image in a color space.

FIG. 9 is also obtained by mapping (μ,
ν) Diagram showing the distribution on the plane

FIG. 10 is a block diagram showing an overall configuration of an apparatus for carrying out an embodiment of the present invention.

FIG. 11 is a diagram for explaining a conversion formula used in a conversion unit for converting into a feature space in the embodiment.

FIG. 12 is a flowchart for explaining an example of a two-dimensional clustering method used in the area dividing unit of the above-described embodiment.

FIG. 13 is a diagram showing cluster division and cluster representative points obtained in the above embodiment.

14 includes L * u * v * including cluster representative points in FIG.
Diagram showing the area in space

[Explanation of symbols]

 10 ... Color space conversion unit 20 ... Feature space conversion unit 30 ... Region division unit 40 ... Encoding unit 42 ... Region information encoding unit 44 ... Lightness information encoding unit 46 ... Chromaticity error information encoding unit 50 ... Decoding Decoding unit 52 ... Region information decoding unit 54 ... Lightness information decoding unit 56 ... Chromaticity error information decoding unit 60 ... Inverse conversion unit

Claims (3)

[Claims] 1. A distribution characteristic in a color space estimated from a reflection model of an object has a characteristic of "white" passing from "black" to "object color".
By modeling each curve as a curve and mapping each pixel on the parameter space that distinguishes the curve, a distribution in which pixels in the same region are localized at a specific location is obtained, and clustering is performed on that space. A data compression coding method for a color image, characterized in that the area information is divided into areas and the obtained area information and lightness information are encoded separately. 2. The data compression encoding method for a color image according to claim 1, wherein the chromaticity error information between the area-divided image obtained by the area division and the original image is also encoded separately. 3. The data compression coding method for a color image according to claim 2, wherein thinning is also used when the chromaticity error information is coded.