HMMD color space and method for quantizing color using HMMD space and color spreading

A new color model HMMD is disclosed based upon hue, the shade, the tone, the tint and the brightness of a color, and a color quantizing method using the HMMD color space. The present invention regards the colors adjacent to a given color in the color space as the neighboring colors to consider indices of the neighboring colors as the partial values according to the distance. Accordingly, the present invention can accomplish a color quantization close to the change of the color sensed by the human eye, thereby capable of enhancing a performance of the image searching system based on content.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a hue max min diff (HMMD) color model, and more particularly for quantizing colors using the HMMD space and color spreading. The present invention relates a content based image searching by building a color histogram.

2. Discussion of Related Art

Currently, extensive research for searching an image based upon the contents is actively being conducted. In response, commercial image searching apparatus and/or applications program are being developed to meet the demand for an improved content based image searching. For example, using contents such as a color temperature change, an external cross magnetic field, and a color homogeneity have been proposed for searching a human image. For color homogeneity, a color space must first be quantized or expressed as numerical values.

The most important information for use in the content based image searching is the color information. Accordingly, an effective performance of an image searching apparatus or applications program depends greatly on an accurate method for extracting the color information.

Generally, the number of different colors which can theoretically be expressed by a computer has been steadily increasing. However, the number of colors which can be displayed by the computer is limited by the available number of quantized colors. A problem arises because the number of quantized colors is less than the number of the colors which can be expressed. Quantization is a procedure of color mapping from M number of colors to N number of colors when M>>N, where M and N are positive integral numbers.

In computers, a color is expressed utilizing the RGB color model based upon the three primary colors of red R, green G, and blue B. However, the RGB space is hardware oriented and a limitation exists in expressing the color changes such that the change can be sensed by the human eye. Thus, the RGB space is often converted into a user oriented HSV color model based upon a hue H, saturation S and value V, then converted back to the RGB space by quantization.

Content based image searching apparatuses or applications programs utilizing the HSV space have been proposed by Foley and Dam in Fundamental of Interactive Computer Graphics , Addison Wesley, pp. 613-16, 1984; Smith in Integrated Spatial and Feature Image Systems: Retrieval, Analysis and Compression , Ph.D. thesis, Columbia University 1997; Virage searching engine, web cite: www.virago.com; and U.S. Pat. No. 5,751,286.

However, even within the HSV space, a range of color changes which can be sensed by the human eye are differently displayed. Also, a simple quantization of the colors in the HSV space does not result in a uniform expression of colors. On the other hand, to quantize the saturation vector value in consideration of the color change sensed by the human eye, the selection of a quantization model would be difficult and many complicated calculations are required. Thus, the performance of the content based image searching system using the HSV space deteriorates.

Accordingly, a color space and a color quantization method utilizing a color space capable of performing color quantization in consideration of the color changes sensed by the human eye and capable of uniformly dividing the colors are required.

SUMMARY OF THE INVENTION

Accordingly, an object of the present invention is to solve at least the problems and disadvantages of the related art.

An object of the present invention is to provide a new color model HMMD based upon the hue, the shade (max), the tint (min), the tone (diff), and the brightness (sum).

Another object of the present invention is to provide a method for quantizing a color using the HMMD space and color spreading.

A further object of the present invention is to provide a method for quantizing a color in consideration of the color changes sensed by the human eye.

To achieve the objects and in accordance with the purposes of the invention, as embodied and broadly described herein, the HMMD color space according to the present invention includes the hue, max, min, diff and sum. The method for quantizing a color using the HMMD color space and color spreading according to the present invention determines a distance between a color to be mapped and the neighboring colors and maps the color utilizing the determined distance as weights.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT

The HMMD color model according to the present invention is generally defined by the hue, the shade (max), the tint (min), the tone (diff), and the brightness (sum). These four factors are the three dimensional coordinate axis for the color space. FIG. 1 shows the HMMD model having the shape of two symmetrical cones being merged at the flat surfaces,

Particularly, the three dimensional color space is formed by the hue h having an angle of 0 -360 around the AB axis; the tone diff being a normal vector of ax in the direction from the center point O to the maximum circumference C; the shade max being a vector in the direction from the apex B to the maximum circumference C; and the tint min being a vector in the direction from the maximum circumference C to the apex A.

The cross sectional plane of the cone taken perpendicular to the center line ax is a 2-dimensional plane having a circular shape, where the values diff and h may change depending on the cross sectional plane. The diff would be a vector from the center O to the circumference of a 2-dimensional plane, and the hue would be the angle defined by two vectors on the 2-dimensional plane from the center O to the circumference of the 2-dimensional plane.

When the circumference of the 2-dimensional color space with a maximized circumference, i.e. max maximum max , min 0, diff maximum diff , is spread, the change of the hue may be displayed as shown in FIG. 2 . The change of the hue would be displayed by pure colors such as red, yellow, green, cyan, blue and purple. Also, if the spread color is equally divided, the color quantization of the color space is accomplished. A detailed explanation of the HMMD model will follow.

A normal plane passing through a sum vector and having a boundary defined by the two apex A and B, and a point C on the maximum circumference becomes an MMD plane which contains the sum, the max, the min and the diff as shown in FIG. 3 . Note that the center line ax is the sum of the max and min vectors (sum). Moreover, the sum expresses the brightness of a color changing from black to white.

One MMD plane displays the max, the min, the diff, and the sum at a given hue 1 , and may be represented by a 2-dimensional plane or a triangle connecting three angular points expressing black, white and pure color. Particularly, the max value controls the color shade and changing the max value changes the shade from black to white and/or pure color. The min value controls the tint and changing the min value changes the tint from black and pure color to white. The diff value controls the tone and changing the diff value changes the tone from gray to a pure color.

Accordingly, utilizing a MMD plane of hue 1 as a color space, the color quantization can be performed by the color coordinate plane as shown in FIG. 4 . Referring to FIG. 4 , the MMD space is divided by lines 11 and 12 parallel to the center line ax, by a line 13 parallel to the max vector, and by a line 14 parallel to the min vector. The color quantization is achieved by mapping the color information within each divided areas (C 1 -C 4 ) to an identical value. Using the HMMD color space, color quantization can be performed uniformly by mapping the color information within the equally (or nonequally) divided areas in the color coordinate plane.

Therefore, a conversion from RGB space to the HMMD space is first performed for a user oriented model, and subsequently a quantization is performed in the HMMD color space to convert back to the RGB space for the computer. FIG. 5 shows a flow chart performing the RGB space conversion, the color quantization, and an image searching therefrom.

The color quantization is accomplished through three procedures, namely the division of the gray area, the color quantization in the MMD space and the color quantization in the hue area.

In the division of the gray area, the diff value is compared to a predetermined reference value gray . If the diff is equal to or less than the reference value gray (d gray ), the area is determined as the gray area. The reference value gray may changes depending upon the hue.

Theoretically, if dff 0, i.e. the AB axis, the gray color is displayed. Depending upon the relation of the diff value and the reference value, a given color area is determined as a gray area, shown by reference 11 in FIG. 4 . Furthermore, depending on the sum and diff values, the gray area is divided into several gray levels (Gray 1 -Grayn) or (Gray 11 -Grayn).

The color quantization in the MMD space is accomplished in the area except for the area determined as the gray area. The max, min and diff values are the reference values of the quantization. As shown in FIG. 4 , one MMD area is divided into plural areas (C 1 -C 4 ) by the reference values 11 , 12 , 13 and 14 . The divided areas are right isosceles triangles, and may be further divided into smaller triangles (C 1 -Cn) by an identical width based upon the max, min and diff values. As the MMD area is divided into smaller triangles, a more accurate mapping may be achieved.

FIG. 4 illustrates a case where the MMD area is divided into four levels (C 1 -C 4 ) and where the gray area is divided into Gray 1 -Gray 4 (or Gray 11 -Gray 42 ) in the gray areas in the MMD plane. The following is an explanation for the color quantization in the hue area.

As shown in FIG. 2 , the hue area is a continuous one dimensional apace in the order of red, green, blue and red. Defined as the angle around the AB axis, the hue area in the HMMD space according to the present invention has the same meaning as the hue in the existing HSV space. The hue area may be equally divided into identical segments. Alternatively, the hue area may be unequally divided giving the larger segments to the areas in which the RGB dominate.

Particularly, in order to use the existing quantization method, the hue value h according to the present invention may be transformed to h* to be more uniform with respect to the human eyses. A transformation from h to h* may be performed as follows for h ranging from 0 to 360. h * = 60 ( 1 - cos ( 3 / 2 Rem ) ) + ( quo ) 120 , where Rem = ( int ( h ) mod 120 ) + ( h - h ) and quo = h / 120

Once the RGB to HMMD conversion and the color quantization are complete as discussed above, the image searching can be performed as shown in FIG. 5 . Generally, the RGB colors are divided into four gray areas and four color areas as shown in FIG. 4 , and into twelve hue areas, resulting in fifty two ((4 color areas 12 hue areas) 4 gray areas) quantized colors.

The characteristic elements used in the image searching system are a global color histogram expressed by the fifty two quantized colors and a local color histogram. The global color histogram is the distribution of the color in each pixel of the entire image and expresses a color distribution of the entire input image. The local color histogram is the distribution of the color in a portion of the image and expresses the color distribution displayed in a particular portion of the image.

The RGB color values for each pixel of input images are extracted, converted into the HMMD space, and mapped by one of the fifty two colors in the HMMD space. The global color histogram and local color histogram are built for the pixels of each image according to the mapped color values. Subsequently, the histograms of the input images is compared to a reference histogram of the target image. The images are arranged by the order beginning from the image with a histogram of the highest similarity, thereby a search of the most similar image to the target image is complete.

Although the HMMD space and color spreading as discussed above allows a uniform quantization, the quantization method may be improved. For example, in FIG. 6 , the color of position P 1 is mapped by C 2 and the color of position P 2 is also mapped by C 2 . However, because the position P 2 is near C 3 , the color sensed by the human may be closer to C 3 rather than C 2 . Nonetheless, the color quantizing method divides the color into n number of groups on the color space to simply map one group to one color.

Therefore, colors near the boundaries of the color group may be mapped to different colors in spite of being similar colors, thereby affecting the performance or reliability of the content based image searching system. Particularly, two colors closely positioned and thus similarly sensed by the human eye may be mapped to very different colors. As a result, a substantially similar image may be regarded as a different image.

Accordingly, the present invention proposes a color quantization method resulting in a color quantization which better reflects the changes sensed by the human eye by considering the neighboring colors on the color space in the color quantization. The indices of the neighboring colors are given weights according to the distance between a color to be mapped and the boundary lines of the neighboring colors.

FIGS. 7A and 7B illustrate a color quantizing method using color spreading according to the present invention. In the quantization method, the color of a position Px within the color group C 2 is mapped by either C 2 or by the adjacent color group C 3 depending upon a threshold value Th. Particularly, the color of position P 1 below the threshold Th is mapped by C 2 .

However, for the color of position P 2 over Th, a weighted value is allotted in consideration of a distance d 1 measured from P 2 to Th and a distance d 2 measured from P 2 to the boundary line of the adjacent color group C 3 . Similarly, for the color of position P 3 also over Th, a weighted value different from the weighted value of P 2 is allotted in consideration of a distance d 3 measured from P 3 to Th and a distance d 4 measured from P 3 to the boundary line of the adjacent color group C 3 .

Moreover, the weighted value allotted is proportional to the distance to Th. For P 2 , the value of the d 2 is lager than that d 1 , and for P 3 , the value of d 4 is smaller than d 3 . Thus, P 3 is closer to the boundary line than P 2 . Accordingly, the neighboring colors in C 3 is given less weight for P 2 than for P 3 .

The color quantizing method using the color spreading as discussed above performs the color quantization by adding the value of the neighboring colors Th-distance to neighboring color /Th 1/(number of neighboring colors 1) , where the number of neighboring colors is the number of the neighboring colors satisfying the condition (Th distance to neighboring color is larger than zero), and the value of the self color (1 value of n neighboring colors).

The value of the neighboring color is a value obtained by dividing a given weighted value by a partial value of the neighboring color groups, and the value of the self color is a rest value obtained by dividing the given weighted value by partial values of the neighboring color groups. For example, for P 1 , the distance from P 1 to the neighboring color is larger than the value of d 1 d 2 and P 1 does not satisfy the condition (Th distance to neighboring colors>0). Accordingly, P 1 is mapped by C 2 .

That is, assuming Th is ten, the d 1 is three and d 2 is seven for P 1 , the weighted value of C 1 is one. For P 2 , the color group adjacent C 2 including P 2 is only C 3 . Accordingly, the number of the neighboring color becomes one and the values for P 2 are obtained as follows.

the value of the neighboring color C 3 (10 7)/10 1/(1 1) 3/20), and

the value of the self color C 2 1 3/20 17/20.

Therefor, a weighted value of 17/20 is allotted to the C 2 and 3/20 is allotted to C 3 .

As for P 3 , assuming that Th is ten, d 3 is eight and the d 4 is two, the color group adjacent C 2 including P 3 is also only C 3 , and accordingly the number of the neighboring color becomes one. Similarly, the values for P 3 are obtained as follow.

the value of the neighboring color C 3 (10 2)/10 1/(1 1) 2/5), and

the value of the self color C 2 1 2/5 3/5.

Therefor, a weighed value 3/5 is allotted to the C 2 and 2/5 is allotted to the C 3 . Note that if the positions Px on the color space as shown in FIG. 7 were included in C 3 , the number of the neighboring colors would be three (C 1 , C 2 and C 4 ) and respective weighted values would be allotted to C 1 , C 2 and C 4 .

Upon calculation of the weight values, a color quantization can be accomplished reflecting the real colors sensed by the human eye by giving the partial (weight) value to the neighboring color group in proportion to the distance to the neighboring color group using the color spreading. Moreover, the quantization method may be applied to a HSV color space or any other color space and is not limited to the HMMD color space.

Also, in the color quantizaton using the color spreading according to the present invention, the weights to the indices of neighboring color groups may be allocated by different methods. Rather than utilizing the threshold value Th, weights may be assigned based upon the concentric points of the quantized color groups. Namely, the neighboring color groups are given weights according to the distance between a color to be mapped and the concentric point of the quantized color group containing the color, and according to the distances between the color and the concentric point of the adjacent quantized color groups.

FIG. 8 illustrates a second embodiment of a color quantizing method using color spreading according to the present invention. First concentric points P 0 , P 1 , P 2 , and P 3 are determined in each quantized color groups C 0 , C 1 , C 2 and C 3 . The quantized space shown in FIG. 8 represents a 2-dimensional view of the quantized color spaces for one value of hue. However, each quantized color space would a 3-dimensional space according to the quantization of the hue. The concentric point is defined here as the center mass point of the 3-dimensional space.

To quantize a color on point x, the distance between point x and the concentric point of the quantized color group containing the color, and the distances between the color and the concentric points of the adjacent quantized color groups are calculated. Referring to FIG. 8 , the calculated distances may be expressed as follows:

where d 2 is the distance between point x and the concentric point of the quantized color group C 2 containing the x; d 0 , d 1 , and d 3 are the distances between point x and the concentric points of the adjacent quantized color groups C 0 , C 1 , and C 3 .

For quantization using the HMMD space, the concentric points would be based upon the hue, the max value and min value as expressed below:

Accordingly, when quantizing a color on point x, the weights are allocated to the indices of the quantized color groups according to the following equations:

Upon calculation of the weight values, a color quantization can be accomplished reflecting the real colors sensed by the human eye by giving the partial (weight) value to the neighboring color group in proportion to the distance from the concentric points using the color spreading.

As discussed above, the HMMD model and the color quantizing method using the HMMD color space and the color spreading has various effects. First, all the colors existing on the new HMMD color space is uniformly distributed and therefor, the color information corresponds to the change of color sensed by the human eye. The present invention also simply divides the colors by straight lines on the new HMMD color space to perform the color quantization.

In addition, the max, min, diff and sum values defining the HMMD model are obtained from R, G and B through a simple calculation without a special transformation and therefor, the calculating time is very rapid. Accordingly, the present invention may be proper in a digital color analysis.

Moreover, the present invention can perform an accurate image searching and image analysis at a high speed, and as well as extract efficient color information in an image processing of a face cognition, a motion picture searching, an MPEG and a gesture cognition, etc., where an image analysis technology is applied.

Furthermore, the present invention regards colors adjacent to a given color in the color space as the neighboring colors to allot partial values in proportion to the distance to the neighboring colors, instead of performing an indexing only in a particular color, for compensating an index error due to the color quantization. Therefore, a color quantization reflecting the change of the color sensed by the human eye may be accomplished. Accordingly, the present invention can enhance a performance of the image searching system based on content.

Finally, the present invention controls the quantization by adjusting a threshold used as a standard value in allotting the partial values, thereby being capable of performing the color quantization in various kinds of color spaces.