1 Introduction

An image storage and retrieval system typically supports text-based annotations and indexing. These indexes for large image collections are time consuming to create and maintain. Also, text indexing for images only provides hit-or-miss type searching. If the user does not specify the right keywords, the desired images may be forever unreachable. Fortunately, this bleak situation can be improved by allowing the computer to provide support in the domain it is most suited for -- automatic extraction of visual features. In such a system the computer analyzes each image and extracts pertinent information, such as colors, color patterns, textures and shapes. By automatically extracting these features and constructing the corresponding indexes, the image storage and retrieval system is given tremendous new possibilities. The feature indexes will not replace the text domain, but rather enhance it. As such, we envision that the following examples of image database queries will be straightforward: "give me a maroon car," or "give me the photo of Bill Clinton wearing a green and yellow polka-dot tie." In these cases, a text-search -- such as for "car" or "Bill Clinton" -- is modulated with color features such as "maroon" and "green and yellow polka-dot." Although the text index is created by human effort, the color feature index is generated automatically by computer.

Several domains of visual features are possible, but color is perhaps the most intuitive and straight-forward for the user. Yet color still poses deep challenges. What people naturally see and classify as specific colors, or as color patterns, usually appear distorted to the computer due to shading and lighting artifacts, and are usually modulated by surface and reflectance properties. While the computer can precisely record the color information in pixel values, the human perception of color is not a pixel process. Rather the human visual system automatically collects points of color to form areas, surfaces and objects. Furthermore, there is evidence that the perception of color is influenced by surrounding colors. Therefore, the computer must do more than allow the pixels to speak for themselves. To provide acceptable extraction of color information, the computer must combine pixel entities in ways to obtain and represent regions of color and color patterns satisfactory for humans. The complete understanding of images by computer would be the ideal solution to this problem, but it is generally accepted that full understanding is far off. However, in the absence of such understanding, automatic color feature extraction can go a long way to enhance image storage and retrieval systems. In this paper we will evaluate several approaches for using automatically extracted color information to filter collections of color images in image databases.

The first major color characteristic we consider is single color regions. We propose two techniques for extracting regions of "homogeneous" color from the image. Each gives the user a different way to communicate the query to the computer. One approach is based on a linguistic description of color and the other is based on color triple. The fundamental issues we address concern the choice of colors and color space, color distance measurement and tolerances, and the trade-off between color distance and spatial distance. We show that the single color technique can be extended to extracted multiple color regions. We also illustrate that color extraction lends itself to an interesting class of queries involving spatial positions and relationships. The next major color feature we consider is color histograms. We investigate several methods for generating color histograms. We also evaluate several methods for computing the similarity between two color histograms, namely, histogram intersection, histogram distance and histogram cross distance. We perform retrieval experiments on all the types of color queries using a test database of 500 color images of flowers and plants. We measure the retrieval effectiveness in terms of recall and precision and compare the effectiveness of the different color query techniques.

1.1 Integration of Visual Features

As mentioned so far for color, the perception of images is a very complex process. However, it has been postulated that nerve cells in the retina immediately break down images into separate components, namely contours, textures and colors. These fragmented pieces of information are then somehow reassembled in the brain into a single coherent image. From the coherent image, the information about its contents is extracted. It is at this high level that humans will naturally tend to organize images. For example, people organize their family pictures or photo albums based on a significance of the contents of the photos. People typically do not categorize photos based on the color contents or texture information. Computers, on the other hand, do have the capacity to de-construct images into components of textures, shapes, contours and colors. But they are very limited in their capability of reintegrating these features into a coherent image. Without image understanding, a computer or automated system cannot provide the level of image organization that is natural or convenient for people.

FIGURE 1. Communication between the user and the database. The user prefers to communicate at the semantic level. Some applications allow communication at the object level. In general, communication at visual feature level can be achieved.

However, we maintain that automatically extracted features will be greatly beneficial in a practical image database system. The user typically prefers to communicate with the database at the semantic level of image content. See Figure 1. This is only possible when the semantics of the entire image database contents are programmed in by humans ahead of time. Because this seems unfavorable, database systems may instead focus on object-level communication. When confined to specific domains typically involved with computer vision, such as for machine part identification, the computer may automatically generate an object-level index. Although, for other general applications, object-level content is supported through human-supplied text descriptions. After altogether eliminating any human involvement in supplying the index data, the database system can still automatically support communication at the visual feature level, as indicated in the lowest level of Figure 1. This requires automatic feature extraction by the computer to collect and organize features such as color, texture and shape information. This creates for the computer independence from human assistance in construction of the indexes. But this approach shifts the burden of the communication effort to the user, who now has the added task of translation of the desired semantic query into a visual features query. While this does not seem to be the most ideal path for the user, given the constraints of the system, it is far easier for the user to cognitively move between levels of image content than for the computer to do so. Furthermore, this system can allow the user to supply samples of the desired content, such as to cut from another image. The system can also provide graphics tools and color space navigators for the user to precisely construct a query key. We hope that with improvements in technology the computer will improve its capacity to translate information between levels of content. This will increase the independence of the system in index construction and reduce the amount of user effort required

2 Single Color Query and Indexing

2.1 Linguistic vs. Color Triple Specification of Color

For single color query we adopt a two-fold approach, envisioning two basic ways the user may query the database. In the first technique, color is specified by language and in the second technique through color triple.

Probably the most user-friendly approach to color specification is through words or phrases. Especially when formulating a text-based query, it will be easiest for the user to include color modifiers in the query string. The alternative is to require the user to select desired colors from a color picker. But navigating through 3-D color spaces is not always intuitive. To address this drawback, the Color Naming System (CNS) was developed by Berk, et. al. for computer graphics applications [6]. In the CNS, english words are used to classify colors along the dimensions of hue, saturation and lightness. The naming system is also divided into levels such that at the lowest level the colors are broadly classified. At successively higher levels, progressively descriptive tags provide more fine discrimination between colors [2]. Such a breakdown is illustrated in Figure 2 for the hue-saturation plane of the HVS color space.

This multilevel decomposition of color space is perfectly suited for the database application. In specifying color the user may at times prefer a very relaxed description of color. For example, for some queries, as long as the object is any "shade" of a specified color, i.e., "red," the query should be satisfied. However, at other times, the user may require more precise discrimination, such as to specify "orangish-red." It has been suggested that at a coarse level people tend to classify all colors into these eleven basic groups: black, gray, white, red, green, blue, yellow, pink, orange, purple, and brown [2]. If the user is acting on this classification of colors, the system should support the same grouping. Otherwise, if the color is taken "literally," for example a query specifying the color "blue," and the computer is utilizing a more stringent discrimination, then this may exclude much to the user's derision all of the light-blues, aqua-blues, dark-blues, etc., which are not exactly "blue." Therefore, we adopt the multi-level CNS for linguistic query of the database.

FIGURE 2. Hue circle in HVS color space: (a) level-1 division -- seven basic hues, (b) level-2 division, further breakdown between colors borders, (c) full hue-saturation plane, exact color is specified as a color triple.

The second technique for single color query is through precise specification of a color triple in color space. To facilitate this type of query formulation, the user is provided with a color space navigator tool which supports several color spaces. The user selects a color point by moving slide bars to vary the color coordinates. A swatch of color provides the user with feedback regarding the movement through the space. When the precise color is reached, he user may further specify the tolerances along each dimension for which a color match should be valid. The color space navigation tool is illustrated in Figure 6.

2.2 Single Color Query

The single color extraction approach provides quick and efficient indexing. Single color index creation is most similar conceptually to file inversion. This works well for image colors, because the full set of visible colors can be represented without visible distortion using a fixed finite set of colors. With this file inversion type of query, the computer first identifies the colors the user is interested in. Each of the colors will point to an index that then produces directly the matches from the database.

Once the single color index is created, it will point to regions within the image that contain individual colors. By recording the spatial coordinates and characteristics of the regions, the system allows for queries that specify spatial relationships between color regions. For example, queries can be formulated such as, "give me images containing a blue region above and touching a red region," or "give me images containing a black region inside a hazel brown region inside a white region," such as to describe hazel brown eyes. To execute this last query, the images containing these three color regions will be selected, then the spatial characteristics will be examined to identify matches. This approach provides a different type of query expression than using color histograms, or color pairs of image segments, as will be seen later. In the complete system, the techniques complement each other in providing a full set of tools for color-based queries.

2.3 Color Region Extraction

2.3.1 CNS color segmentation

The color regions are extracted by sampling the images using specific colors. To provide support for the linguistic color queries, we perform a separate segmentation of the image for each level in the CNS. For example, at the lowest level in the CNS, the image is segmented into 11 basic colors. The reason that separate segmentations are performed rather than joining the groups of segmented, finely colored regions later, is that in the extraction process we also exploit a trade-off between color and space to eliminate illumination noise and other artifacts.

Using the set of colors within each level of the CNS, the color regions are extracted in two stages. In the first stage, each pixel in the image is assigned to one of the classes of colors from the chosen level in the CNS. At the second stage this image is filtered using a color median filter. This stage eliminates isolated spots of color that fall within a region dominated by another color. Figure 3 illustrates stages 1 and 2 for a color image of a car, where the color set was selected from level-1 of the CNS. Stage 1 assigns each pixel from the original 24-bit RGB image into one of the bins in the color set. There are still spots of color noise which may result from uneven lighting, or other artifacts. Stage 2 removes these spots as indicated in Figure 3(c). Further processing before assigning the color regions to the index removes color regions that are smaller than a certain threshold of area. This process of single color region extraction is repeated across the levels of the CNS color space, each producing a separate index. The user query specifies which level of the CNS to use to determine which index is used in repose to a query.

FIGURE 3. Single color extraction using CNS colors, (a) original 24-bit RGB color image, (b) after each pixels assigned to appropriate level-1 CNS color, (c) image after non-linear filtering to remove spot noise and isolate homogeneous regions.

2.3.2 Color space, color point segmentation

To support greater precision in color query, a separate color extraction process is adopted. In this process, precise points in color space are used to extract color regions. Conceptually this may be thought of as being similar to the CNS approach but supporting an arbitrary number of colors and arbitrary color spaces. The extraction process proceeds as follows: first, a color histogram is generated for each image using the bins that correspond to the sampled color space. Then by iterating over the non-zero bins, the color distance is computed between each pixel in the image and each non-zero bin color. This produces a series of distance images, see Figure 4. Subsequent processing of the distance images exploits the trade-off in image space versus distance in color space. Next, thresholding of each distance image gives a binary mask that, when fitted over the original image, identifies the occurrences of the color within the image.

FIGURE 4. Color Image: (1) color selection, (2) distance computation, (3) non-linear distance smoothing, (4) distance thresholding, (5) size thresholding, and (6) region labeling and characterization.

The immediate application of the mask does not always give good results. This is because noise, lighting and other artifacts give spots within color regions and outside of color regions. To compensate for the spatial aberrations, we use a rank-order filter on the distance image. Linear filters, such as low-pass filters, are not appropriate for this task, because while artifacts might disappear, important information is also lost, such as boundary information being blurred. We use a generalization of the median filter -- the rank-order filter. This has the ability to eliminate isolated points of color and closes over regions that have holes or are disconnected.

Once the filtered distance image is obtained it is thresholded. After thresholding, a mask image is obtained. Next follows a sequential labelling routine, whereby unconnected regions are distinguished and labelled. This also provides for computation of region attributes such as area and location. Finally, a threshold is applied at this stage, based on region area. An example of this process is illustrated for the color image in Figure 5.

This more general approach than the CNS color extraction allows us to investigate the many color spaces. This technique is not tied to any particular color space or color system. While color spaces such as RGB and YIQ are popular, other color spaces, such as CIELab and CIELuv provide better perceptually uniform spaces. Distance functions defined in these spaces give better performance than in non-uniform spaces. Also, for this type of query, the use of a color order system is also appropriate. For example, the Munsell color order provides a finite collection of colors which are spaced at perceptually uniform distances. Color order systems, such as Munsell provide convenient tools for the user to flip through color samples. They also provide a more direct way for assessing the similarity between colors.

FIGURE 5. (a) Color flowers image p0323 -- Layia elegans, (b) pixel distances to point (255, 255, 0) in RGB color space, (c) after distance thresholding (distance tolerance = 70), (d) after rank order filtering, sequential labelling and size thresholding, five isolated regions are identified.

2.4 Color Region Indexing and Color Agents

After the color regions have been identified using the above process, the database is populated with the color region data. The color, an image pointer, position and size of each color region are kept as attributes of each color region. The database query is initiated with the user selecting a color from a color picker, see Figure 6, or from an image. The color index is then searched to find the match to the selected color. The user may also specify tolerances for the color, such as in the different channels of a particular color space or for the distance function. We call the definition of the color with tolerances, the color agent. For example, in YIQ space, the user may specify a color agent that has a larger tolerance in the luminance (Y) channel, if the brightness of the desired color is not a significant factor. This may allow, say, all shades of the "blue" to be retrieved. The values of the tolerances will determine how many and which colors will be selected in the index. Once the colors in the index have been identified, the file inversion now allows the images containing matches to be read off directly. Therefore, the only delay in query execution will be the initial determination of the colors in the index that match the user specified color agent.

FIGURE 6. (a) Color Space Navigator -- tool that allows users continuous navigation through 3-D color spaces. (b) Color Extractor -- tool for extracting single color regions from images.

2.5 Single Color Retrieval Experiments

2.5.1 Retrieval effectiveness

The effectiveness of the two single color retrieval techniques were evaluated using a test database of 500 color images of flowers and plants. The collection [1] has a variety of flowers and plants photographed in different settings and under different lighting conditions. The images are rich in color. Most photos have a substantial contribution of background colors depending on the location of the photo shot.

Two metrics for retrieval effectiveness are recall and precision. Recall signifies the proportion of relevant images in the database that are retrieved in response to a user query. Precision is the proportion of the retrieved images that are relevant to a user query [19]. More precisely, let A be the set of relevant images in the database and B be the set of retrieved images, then recall and precision are defined through conditional probabilities: recall = P(B|A) and precision = P(A|B). As indicated by the formulas, the measure of recall and precision require that the relevance of each item in the database to the query be established ahead of time. For the experiments, this was done for each query by subjectively assigning one of three values to each image in the database: relevant = 1, partially relevant = 0.5 and not relevant = 0. This value can be interpreted as the probability that the item is relevant to a particular query. Several queries were evaluated for each single color retrieval technique and the results appear in the graphs in Figure 7.

FIGURE 7. Single color query -- retrieval effectiveness (a) linguistic query, (b) color triple query.

2.5.2 CNS color name query

For the linguistic query, from the color names from the CNS, the user specified the color of the plants or flowers to be retrieved from the database. The user also indicated the level of CNS desired. We evaluated several methods of ranking images in the database in response to the user query. But first, for all three methods the primary response of the computer to the query is to identify the appropriate index for the CNS query color. The index contains the set of all regions of the specified query color found within images in the database. For example see the table below.

CNS Color Table -- (Hi, Vj, Sk):

For each extracted region of each image, the position and area are kept as attributes. Three query methods were executed as follows: for the first retrieval method, images in the database were ranked in order of the size of the largest matching color region (size). For the second approach, images were ranked in order of the number of matching regions (count). For the third approach, images were ranked in order of the total area of all matching regions (area). A comparison of the retrieval effectiveness appears in Figure 7(a). The area and size methods yielded very similar results. These approaches show very good performance, as precision is consistently maintained at about 0.6 - 0.7, as nearly total recall is approached. The count methods shows slightly less retrieval effectiveness. This seems to indicate that a better match is obtained when a large region of the matched color exists over when many small matching regions exist. The optimum retrieval effectiveness is indicated at the top of the graph. This ideal curve is based directly on the probabilities of relevance assigned to each of the items in the database.

2.5.3 Color triple query

For the color triple queries, the user was asked to specify through the navigator interface in Figure 6(a) a point in a color space, such as RGB space, and a distance tolerance for discrimination. This type of query requires that the user have some familiarity with color spaces. For these experiments, a person was asked to devise a color query based on a region within color space. Then the relevance to each query was determined for each image in the database in the same manner as described previously for the linguistic query experiment. The retrieval effectiveness was evaluated based on the relevance assessments and the order in which the images are returned. We evaluated for the color triple query the same three methods of return as used for the linguistic query. The results appear in Figure 7(b). Again we see that the size and area rankings give the best performance. The count retrieval performance lags slightly behind.

2.6 Summary of the Single Color Query Technique

By comparing the retrieval effectiveness of the CNS linguistic query to the color triple query, we see that the color triple query performs better. However, the color triple technique requires more expertise of the user to formulate the query. With the CNS color name approach, the user does not have much trouble in specifying the query. The CNS system supports multiple levels of color description which allows for multiple definitions of a color, depending on the precision desired. In a real database system, the ease at which the CNS query can be formulated may balance out the slight loss in retrieval effectiveness. The color triple method is a more general approach than CNS. The color triple is not tied to any particular color space or color system. The performance of the query is under more direct control of the user. The user can specify a precise point in a color space and give tolerances surrounding that point. This type of query may not be as easy to formulate for a novice.

The single color extraction technique offers a good system for supporting retrieval of color images from an image database. The attributes stored for color regions also have the potential to extend the color queries to include spatial locations, orientations, shapes and relationships between color regions. The single color extraction technique can also be extended to include multiple color regions. This can be done by choosing more than one color for an extraction. This will combine the colors together when they appear in the segmented regions. While this extension was not included in this study, we are investigating its application to identifying color patterns. Especially when several colors are tightly interwoven into a textured pattern, the multiple color extraction can better extract the patterned region than multiple single color extractions.

3 Color Histograms

3.1 Color Histogram Techniques

3.1.1 Color histogram definition

A color histogram is formed by discretizing the colors within an image and counting the number of colors that fall into each bin. Since the typical computer represents color images with up to 16,777,216 colors, this process generally involves substantial quantization of the color space. The main issues regarding the color histograms are the choice of color space, the type of quantization and the degree quantization. The first two are related. When a perceptually uniform color space is chosen, uniform quantization is appropriate. If a non-uniform color space is chosen, then non-uniform quantization may be needed. Often practical considerations, such as to be compatible with the workstation display, influence the common selection of uniform quantization of RGB color space. The color histogram can be thought of as a set of vectors. For gray-scale images these are two dimensional vectors. One dimension gives the value of gray-level and the other the pixel count for that gray-level. For color images, the color histograms are actually composed of a set of 4-D vectors. This makes color histograms very difficult to visualize. There are several lossy approaches for viewing color histograms, one of the easiest is to view separately the histograms of the color channels. An example appears in Figure 8. This type of visualization does illustrate some of the salient features of the color histogram. For example, in Figure 8(b) are the channel histograms in RGB space. In Figure 8(c) are the channel histograms in LAB space. These plots make apparent the differences in which these spaces distribute color data.

FIGURE 8. (a) 24-bit color flower image -- Chrysanthemum carinatum `Monarch Court Jesters', (b) 1-D histogram for each channel in RGB, (c) 1-D CIELAB histograms

3.1.2 Color uniformity

However, the RGB color space is far from being perceptually uniform. Figure 9 illustrates the sampling of the CIE chromaticity produced by uniform sampling of the RGB color space. Figure 9(b), (c) clearly illustrate that this does not sample uniformly the CIE chromaticity. To obtain a good color representation of the image by uniformly sampling the RGB space, it is necessary to select the quantization step sizes to be fine enough, such that distinct colors are not assigned to the same bin. The drawback is that oversampling at the same time produces a larger set of colors than may be needed. The increase in the number of bins in the histogram impacts performance of database retrieval. Large sized histograms become computationally unwieldy, especially when distance functions are computed for many items in the database. Furthermore, as we shall see in the next section, to have finer but not perceptually uniform sampling of colors negatively impacts retrieval effectiveness.

FIGURE 9. (a) Portion of the CIE(x, y) chromaticity achievable on workstation display, (b) uniform sampling of the RGB space with 32 samples per channel produces 32768 colors, (c) RGB uniform sampling with 16 samples produces 4096 colors.

3.2 Color Histogram Discrimination

3.2.1 Histogram distance

The distance between two color histograms can be computed as: , where and are histograms and the summation is over all bins. In this distance formulation there is only comparison between the identical bins in the respective histograms. Two different bins may represent perceptually similar colors but are not compared in this distance formula. In this formula, all bins to contribute equally to the distance.

3.2.2 Histogram intersection

Color histogram intersection was used in [11] and [18], so that only the colors the user is interested in are considered. The intersection formula is: . Here, if colors are not present in the user's key, they will not contribute to the distance. Likewise, colors in the image not matching the user's colors will not be considered. This may reduce the contribution of background colors. The sum is normalized by the histogram set with fewest samples.

3.2.3 Histogram cross distance

Cross distance was used by [17] for the QBIC image database project. There, the distance formula: , was proposed to consider the cross-correlation between histogram bins based on the perceptual similarity of the colors represented by each bin. In the case that quantization of the color space is not perceptually uniform, the cross term contributes to the perceptual distance between color bins.

3.3 Color Histogram Retrieval Experiments

In a manner similar to that for the single color queries we evaluated the effectiveness of the color histogram approaches on the test database of 500 color images of flowers and plants. The same metrics were used to measure retrieval effectiveness: recall and precision. The experiments were conducted by asking a person to use one of the images as a key to find similar images. From a portion cut out of one of the images in the database, the user made a query key. Then for this query key, the person assessed the similarity between the key and all of the images in the database. A three-level probability was assigned to each image as an estimate of its the relevance to the query key. Using the relevances for the predetermined queries, experiments were designed to vary parameters for each of the color histogram methods and to measure the resulting retrieval effectiveness.

FIGURE 10. Retrieval effectiveness as a function of the number samples per color axis (RGB space), (a) color histogram intersection (b) color histogram distance -- Euclidean distance.

3.3.1 Histogram intersection

Figure 10(a) indicates the results when the histogram intersection method was used to determine the order of retrieval. The intersection score is high for similar images and low for dissimilar images. These experiments used the RGB color space for the histograms. The quantization of the RGB color space was varied. As the plots illustrate, as the quantization was made more fine in RGB space, the retrieval effectiveness based on histogram intersection was improved.

3.3.2 Histogram distance

Figure 10(b) indicates the results for the color histogram query where the histogram distance method was used to determine the order of retrieval. The distance score is low for similar images and high for dissimilar images. These experiments also used the RGB color space for the histograms. Interestingly, for the color histograms, as the quantization was made more fine in RGB space, the retrieval effectiveness worsened. Except for the case of very coarse quantization at 2 bins per color channel, the retrieval effectiveness decreased as the number of samples per color channel increased.

3.3.3 Histogram cross distance

Figure 12(a) indicates the results for the color histogram query where the histogram cross distance method was used to determine the order of retrieval. The distance score is low for similar images and high for dissimilar images. These experiments also used the RGB color space for the histograms. The cross distance between two histograms requires the most computation of the histogram distance formulas. But the cross distance has the ability to compensate for the histograms not being perceptually uniform. The way this is done is through a matrix that specifies the perceptual distance from each color in the color space to each of the other colors. The matrix values can be derived from a distance measure in color space, or produced from a color order system, such as Munsell, or derived subjectively by the user. Figure 11 illustrates examples of the correlation matrix derived from the RGB and CIELab color spaces. Notice that for the same pairs of colors, the RGB and CIELab matrices give sometimes very different distances.

To help reduce the computations required form the cross distance function, the QBIC team [17] has suggested a technique for bounding of the cross distance function. This is done by lower bounding the cross distance with distance between the average colors of the histograms. In response to a color histogram query, this lower bound can be used as a first stage filter to reduce the element set in the database.

FIGURE 11. Correlation matrices used in computation of color histogram cross distance (a) based on euclidean distance in RGB color space for 2 samples per channel = 8 colors, (b) distance in CIELab space, (c) RGB space and 4 samples per channel = 64 colors, (d) CIELab distance. Gray-intensity indicates the magnitude of the distance between row colors and column colors.

3.3.4 Comparison and summary of experiment

Figure 12(b) illustrates the comparison of all three retrieval methods. Histogram intersection, with 64 samples per color channel gives the best overall performance. The histogram cross distance gives nearly as good results with utilizing only 4 samples per color. However, this cross distance has the highest computational requirements. The ordinary euclidean histogram distance measure gives the least satisfactory retrieval effectiveness of the three.

FIGURE 12. Retrieval effectiveness as a function of the number of histogram bins per color axis (RGB space), (a) color histogram cross distance (b) best retrieval scores from intersection, distance and cross distance.

3.4 Color Histogram Summary

Color histograms provide a method for searching for color images that is complementary to the single color approach. Where as the single color query requires the user to specify a color either linguistically or as a color triple, the histogram approach allows the user to present to the database an example of what the user wants to retrieve. The color histogram provides the characterization of the contents of the color image that can be effectively used to judge similarity to other color images. However, their effectiveness depends on attention being given to the choice of color space, quantization size and histogram distance function. Color histograms also possess the ability to characterize regions within images. Once a reliable threshold for measuring similarity between color histograms is developed, this threshold can also be used to split and join regions within the image. While it may be impossible to achieve image segmentation, such as to separate the foreground from background, color histograms provide one effective method for separating regions having different color patterns.

4 Conclusion

In this paper we investigated two classes of techniques for retrieving color images from an image database: single color query and color histograms. Single color query is perhaps most suited for accompanying a text query, or when formulated as a spatial query of color regions. To accommodate the single color query seamlessly into the text queries, we presented a technique for specifying the query color linguistically. The Color Naming System (CNS)[6] was used to provide a multi-level breakdown of the Hue-Value-Saturation (HVS) color space. This system provides levels with increasingly descriptive tags to provide a color breakdown that is most suited to the user's needs. The CNS system allows the user to specify by choosing a color level, when the computer should be stringent with color matching and when it should be more relaxed. To accommodate the highest precision in color specification, we proposed also a single color extraction technique based on color triple specification. We provide the user with tools allowing navigation through color spaces to find the precise color. The user may also specify the bounds around the color triple over which a query should be satisfied.

To accommodate queries where the user may want color images that are similar to one particular image, we explored several characterizations based on color histograms. As with the single color query, the color space is a major issue of concern. There is no consensus on what color space is best. No color space is perfectly uniform perceptually, for everyone, and under all lighting conditions. Also, some good color systems do not offer ease of computation and transformation into and out of the color space, which makes them impractical. We investigated some of the issues regarding choice of color space. Experiments were carried on the a database of 500 color images of flowers and plants, which gleaned some of the issues concerning color space. The experiments were used to measure the retrieval effectiveness for a variety of color image queries. The conditional probabilities, recall and precision were used as measures of the retrieval effectiveness.

Image databases are providing new challenges. Traditional database techniques, largely based on text-based indexing are not appropriate for images. Increasingly, there has been focus on content-based techniques for image retrieval. These techniques are based on extraction of visual features and automated indexing of these feature by computer. Along with texture and shape, color is an important element of visual information. Although the human visual process is still not fully understood, it is believed that color provides features essential for image coherence. Color has also found its way into almost every computer. Therefore, it is natural to propose that the computer be used to analyze the heaps of color information on behalf of the people. Image databases are the ideal opportunity to use the computer as a tool to filter the large archives of visual information to help the user find particular images.

5 References

[1.] Roy Hay and Patrick Synge, The Color Dictionary of Flowers and Plants, Crown Publishers, 1992.

[2.] David Travis, Effective Color Displays, Theory and Practice, Harcourt, Brace & Javanovich Publishers, 1991.

[3.] R. W. G. Hunt, Measuring Color, John Wiley & Sons, 1989.

[4.] S. Tominaga, "A Computer Method for Specifying Colors by Means of Color Naming," in Cognitive Engineering in the Design of Human-Computer Interaction and Expert Systems, edited by G. Salvendy, Elsevier Science Publishers, 1987, p. 131 -- 138.

[5.] H. Farshoosh and G. Schrack, "CNS-HLS Mapping Using Fuzzy Sets," I.E.E.E. Computer Graphics and Applications, 2:, 1987, p. 28 -- 35.

[6.] T. Berk, L. Brownstone, A. Kaufman, "A new color naming system for computer graphics," I.E.E.E. Computer Graphics and Applications, 2:, 1982, pp. 37 -- 44.

[7.] T.S Chua, S-K Lim and H-K Pung, "Content-based Retrieval of Segmented Images," Proceedings of ACM Multimedia 94, San Francisco, Ca., October 1994.

[8.] Shoji Tominaga, "Color Classification of Natural Color Images," COLOR research nad applications, Vol. 17, No. 4, August 1992, pp. 230 -- 239.

[9.] A. R. Robertson, "Historical Development of CIE Recommended Color Difference Equations," COLOR research nad applications, Vol. 15, Number 3, June 1990, pp. 167 -- 170.

[10.] M. Miyahara and Y. Yoshida, "Mathematical transform of (R, G, B) color data to Munsell (H, V, C) color data," SPIE Vol. 1001, Visual Communications and Image Processing, 1988, p. 650 -- 657.

[11.] M. Swain and D. Ballard, "Color Indexing," International Journal of Computer Vision, 7:1, 1991, p. 11 -- 32.

[12.] A. Berger-Schunn, Practical Color Measurement, John Wiley & Sons, Inc., 1994.

[13.] G. Wyszecki and W. S. Stiles, Color Science: Concepts and Methods, John Wiley & Sons, 1982.

[14.] A. Netravali and B. Haskell, Digital Pictures, Plenum Press, 1988.

[15.] S.F. Chang, J.R. Smith and H. Wang, "Automatic Feature Extraction and Indexing for Content-Based Visual Query," submitted to I.E.E.E. Computer, 1995.

[16.] John R. Smith and Shih-Fu Chang, "Single Color Extraction and Image Query," submitted to IEEE International Conference on Image Processing, October, 1995.

[17.] C. Faloutsos, et. al., "Efficient and Effective Querying by Image Content," IBM RJ 9453 (83074), August 3, 1993.

[18.] M. P. Dubuisson and A. K. Jain, "Fusing Color and Edge Information for Object Matching," I.E.E.E International Conference on Image Processing, Nov. 1994.

[19.] Karen Sparck Jones, Information Retrieval Experiment, Butterworth & Co., 1981.

Generated with CERN WebMaker