[机械模具数控自动化专业毕业设计外文文献及翻译]【期刊】提取颜色特征和动态匹配的图像数据库检索-外文文献

IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 9, NO. 3, APRIL 1999 501Extracting Color Features and DynamicMatching for Image Data-Base RetrievalSoo-Chang Pei, Senior Member, IEEE, and Ching-Min ChengAbstractColor-based indexing is an important tool in imagedata-base retrieval. Compared with other features of the image,color features are less sensitive to noise and background compli-cation. Based on the human visual systems perception of colorinformation, this paper presents a dependent scalar quantizationapproach to extract the characteristic colors of an image as colorfeatures. The characteristic colors are suitably arranged in orderto obtain a sequence of feature vectors. Using this sequence offeature vectors, a dynamic matching method is then employed tomatch the query image with data-base images for a nonstationaryidentification environment. The empirical results show that thecharacteristic colors are reliable color features for image data-base retrieval. In addition, the proposed matching method hasacceptable accuracy of image retrieval compared with existingmethods.Index TermsColor extraction, color index, dynamic match-ing, image data-base retrieval.I. INTRODUCTIONTHE fast evolution of workstations and network technol-ogy has made visual communication service more andmore popular. One application of this service is allowing net-work users to view materials of remote image data basese.g.,a trademarks data base, multimedia data base, etc.on theirworkstations. To make this application realistic, the effectiveindexing and retrieval of image data bases is essential. In1 and 2, texture keyword is described as a means forimage indexing and retrieval. This approach searches imagedata bases on the keyword records, and the associated imagesare retrieved on the completeness of the texture search. Someapproaches 3 using computer vision techniques are alsoconsidered. In computer vision, the identification of objectsis always the major task. Traditionally, the identification isbased on the geometrical features of the object, e.g., thegray spatial moments, the area, the extremal points, and theorientation. This means of identification suffers from variationsin the geometrical features in the scene, most importantly:distractions in the background of the object, viewing the objectfrom a variety of viewing points, occlusion, varying imageresolution, and varying lighting conditions.Manuscript received January 2, 1997; revised October 1, 1998. This workwas supported by the National Science Council, R.O.C., under ContractNSC88-2213-E-002-047. This paper was recommended by Associate EditorS. Panchanathan.S.-C. Pei is with the Department of Electrical Engineering, National TaiwanUniversity, Taipei, Taiwan, R.O.C. (e-mail: .tw).C.-M. Cheng is with the Applied Research Laboratory, TelecommunicationLaboratories, Ministry of Communications, Taipei, Taiwan, R.O.C. (e-mail:.tw).Publisher Item Identifier S 1051-8215(99)03051-7.On the contrary, color, unlike image irradiance, can beused to compute image statistics independent of geometricalvariations in the scene 4. With the help of color-basedfeatures, Swain and Ballard have presented a color indexmethod 5, called the histogram intersection method. Intheir method, they use the color histograms to create three-dimensional (3-D) histogram bins for each query image. The3-D bins are then matched with those of data-base imagesby using the histogram match value. Although this approachis useful in many situations, performance degrades signifi-cantly in changing illumination. To alleviate this problem,Funt and Finlayson 18 have extended Swains method todevelop an algorithm called color constant color indexing,which recognizes objects by matching histograms of colorratios. Reference 18 reported that Funts algorithm doesslightly worse than Swains under fixed illumination, butsubstantially better than Swains under varying illumination.Recently, Slater and Healey 19 have derived local colorinvariants, which capture information about the distributionof spectral reflectance, to recognize three-dimensional objectswith good accuracy. Slaters algorithm is independent of objectconfiguration and scene illumination, but the computationalcost of processing an image is high.On the other hand, Mehtre et al. 6 have developed thedistance method and reference color table method to do colormatching for image retrieval. The distance method uses themean value of the one-dimensional (1-D) histograms of eachof the three color components as the feature. Then a measureof distance between two feature vectors, in which one is froma query image and the other is from a data-base image, isused to compute the similarity of two feature vectors. In thereference color table method, a set of reference colors is firstdefined as a color table. Each color pixel in the color imageis assigned to the nearest color in the table. The histogramof pixels with the newly assigned colors is then computed asthe color feature of the image. For image retrieval, the colorfeature of the query image is matched against all images in thedata base by a similarity measure to obtain the correct match.Different from the above-mentioned color-based methods,which use the color histogram as a feature, we propose in thispaper the usage of the representative colors of an image asthe features for identification. This approach is similar to whatthe human visual system does to capture color informationof an image. When viewing the displayed image from adistance, our eyes integrate to average out some fine detailwithin the small areas and perceive the representative colorsof the image. The representative colors, called characteristic10518215/99$10.00 1999 IEEE502 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 9, NO. 3, APRIL 1999Fig. 1. The partition of color space by the DSQ.colors in this paper, are extracted by a dependent scalarquantization (DSQ) algorithm and ordered to obtain a sequenceof feature vectors. Matching the characteristic colors betweena query image and each data-base image is achieved byusing a dynamic matching method, which is based on thedynamic programming equation in order to overcome varyingviewpoints of the image, occlusion, and varying lightingconditions and to obtain the best match path. A dynamicprogramming approach has shown great potential in solvingdifficult problems in optical character recognition (OCR) 20,and especially speech recognition 21. Combining the DSQalgorithm and the dynamic matching method, a mechanismis proposed for image data-base retrieval. We demonstrate theproposed mechanism with a set of experiments, which comparethe performance of existing methods with that of the proposedmechanism.This paper is organized as follows. The approach to extract-ing the characteristic colors as the color features is presented inSection II. Section III describes how to use the proposed colorfeatures to carry out the tasks of image data-base retrieval.Section IV reports the simulation results of the proposedmatching method. Conclusions are drawn in Section V.II. APPROACH TO COLOR FEATURE EXTRACTIONIn the early perception stages of human beings, similarcolors are grouped together to fulfill the tasks of identification.Based on this assumption, we present a scheme in this sectionto group similar colors of an image and extract the charac-teristic colors as the features for identification. The proposedscheme for extracting the color features is similar to the designof the color palette for an image. It requires quantization of theoriginal full-color image into the limited color image. Amongmany approaches to the design of the color palette 7, 8, theDSQ approach proposed by Pei and Cheng 9 has been shownto perform well. We employ the DSQ approach to generatea color palette that contains the characteristic colors used asthe color features. This approach for the design of the colorpalette is reviewed below.A. Dependent Scalar QuantizationAs displayed in Fig. 1, the DSQ approach partitions colorspace of an image in a dependent way in order to fully utilizethe correlations of the color components of an image. Thepartition used is the 1-D moment-preserving (MP) technique.The advantage of the MP quantizer is that the output canbe written in the closed form 10. When using anotherfidelity criterion, such as mean square error (MSE) 11, it isusually impossible to obtain a closed-form expression for thequantizer. Also, using this DSQ procedure, the computationalcost is rather small.The DSQ mainly consists of two stages, namely, the bitallocation and recursive binary MP thresholding. Suppose theset of all grid points of the image is denoted by , and itsmembers that belong to may be explicitly written as ,where is the row index and is the column index. Thecolor value of is denoted as , where is theassociated color component value.1) Bit Allocation: If the DSQ expects to be unsupervised,the number of thresholding levels in each color componentmust be decided a priori. Since the number of thresholdinglevels can be expressed by powers of two, we choose bits torepresent the total thresholding levels. The purpose of the bitallocation is to automatically assign a given quota of bits toeach color component of the image, that is, a fixed numberof bits has to be divided among the color components,. The bit-allocation method typically assigns morebits to the color components with larger variance and fewerbits to the ones with smaller variance. The reason for thischoice is that if the data are very spread out on a particularcolor component, then presumably the data in that componentare more significant than that of other, more densely groupedcomponents.The significant component should be given more bits inorder to reduce the quantization error. If the probability densityfunctions are the same for all the components , exceptfor their variance, an approximate solution to the bit allocationof each component is given by 12(1)where is the variance of the component . After thebit allocation, the number of thresholding levels of eachcomponent for has been determined. Then,the recursive binary MP thresholding is used to partition eachcomponent.PEI AND CHENG: EXTRACTING COLOR FEATURES FOR DATA-BASE RETRIEVAL 503(a)(b)Fig. 2. Recursive binary moment-preserving thresholding.2) Recursive Binary MP Thresholding: Employing the bi-nary MP thresholding on a color component , the totalpixels are thresholded into two pixel classes, i.e., the below-threshold pixels and the above-threshold ones. The problemof binary MP thresholding, as Fig. 2(a) illustrates, is to selecta threshold value such that if the component valuesof all below-threshold pixels are replaced by , and thoseof all above-threshold pixels are set to , then the first threemoments of color component for the image are preservedin the resulting two-level image. Given the color value of eachpixel, the th moment of color component is defined as(2a)where is the total pixel number. The th moment can alsobe computed from the distribution of values, or histogram,as follows:(2b)where is the total distribution levels in the histogramand is the number of pixels with the value in thehistogram.Let and denote the fraction of the below-thresholdand above-threshold pixels in the image after the binaryMP thresholding. Then the resultant th moments of thetwo-level image are just(3)If we preserve the first three moments of the resultanttwo-level image equal to those of original image, we get the following moment-preservingequations:After some simple computations, can be obtained as(4)From , the desired threshold is chosen as the -tileof the histogram such that(5)Now considering partitioning color component intointervals, we use the binary MP thresholding technique re-cursively to obtain the desired thresholding levels instead ofdirectly applying the multilevel thresholding technique as in10. The range of the color component , with boundaryvalues zero and , is first partitioned into two inter-vals and , where represents thethreshold obtained by first binary MP thresholding. Then theinterval is partitioned into two subintervalsand , where is the threshold obtained bysecond binary MP thresholding. Similarly, ispartitioned into two subintervals andby third binary MP thresholding. The above procedures areillustrated in Fig. 2. If we continue the procedure recursivelyby using the binary MP thresholding times andorder the resultant thresholds according to their values, theoutput thresholding levels will bedetermined, i.e., for .3) The DSQ Algorithms: Based on the above discussionof bit allocation and recursive binary MP thresholding, thealgorithm to generate the DSQ color palette can be describedas follows.Step 1) Input the image and utilize the bit-allocation pro-cedure to determine the total thresholding levels ofeach color component.Step 2) Do the recursive binary MP thresholding on andcalculate the associated thresholding levels.Step 3) Do the following steps times:3.1) Perform the recursive binary MP thresholdingon of pixels within the rectangular boxbounded by and calculate theassociated thresholding levels.3.2) Do the following step times:504 IEEE TRANSACTIONS ON CIRCUITS AND SYSTEMS FOR VIDEO TECHNOLOGY, VOL. 9, NO. 3, APRIL 1999(a)(b)Fig. 3. The ordering of characteristic colors. (a) Layer l. (b) Layer l 43 ) Calculate the recursive binary MP threshold-ing on of the pixels within the long barlimited by andand compute the associated threshold-ing levels .Step 4) Assign the centroid of color points inside a cubeformed by Steps 2) and 3) as a characteristic colorof the color palette.B. Color Features from the DSQ ApproachAfter using the DSQ approach, the input colors of the imageare grouped into disjoint sets, .is the predetermined color-palette size. In each set , thereFig. 4. The images of 27 objects in the first data base.is a characteristic color chosen. These characteristic colorsconstitute the color palette. We defineas the set of the color features that represent the original image.The DSQ approach requirestimes binary MP thresholding to finish colorspace partition. It takes approximately multiplication oper-ations for binary MP thresholding. So, the total multiplicationsfor the recursive binary MP thresholding will be approximately.Furthermore, the partition of color space by the DSQapproach shown in Fig. 1 causes the characteristic colors tobe distributed layer by layer in the 3-D space. We arrangethese characteristic colors in the 1-D way in order to processthem efficiently in the mechanism of image data-base retrieval.As shown in Fig. 3, the characteristic colors are orderedsequentially in the 1-D way, where denotes the index ofthe associated characteristic color. The value of the index isincreasing from the bottom layer to the upper layer. Throughthis ordering, two neighboring indexes would represent twovisually close colors. The image could be represented by asequence of feature vectors(6)To illustrate the color features extracted by the proposedapproach, we have chosen three test images from a data baseof 27 images, shown in Fig. 4. The red, green, blue (RGB)images in the data base are 159 119 size coded at eight bitsfor each color component. For each test image, we utilize theDSQ approach, which allocates three bits to color components,to obtain a color feature set of size eight. Settingin (1), we have acquired for . Thus, binaryMP thresholding is used once for each color component in thesequential partition of color space shown in Fig. 1. In Fig. 5,we show test images, the corresponding color feature sets, andthe quantized images, which used the characteristic colors ineach color feature set to form the associated color palette.It is noticed from Fig. 5(c) that color information insidethe quantized images is similar to that of the correspondingtest images. That is, the characteristic colors in each colorPEI AND CHENG: EXTRACTING COLOR FEATURES FOR DATA-BASE RETRIEVAL 505(a)(b)(c)Fig. 5. Results of the DSQ approach to extract the color feature sets: (a) original images, (b) corresponding color feature sets, and (c) correspondingquantized images by using the characteristic colors to form the color palette.feature set of Fig. 5(b) can represent color information insidethe corresponding image. Therefore, the characteristic colorsextracted by our DSQ approach are reliable and able to beused as the color features of the image.III. MECHANISM OF IMAGE DATA-BASE RETRIEVALThis section describes how to use the sequence of featurevectors, which are the characteristic colors extracted by theDSQ approach, to identify a query image from data-baseimages. The problem of identification can be described asfollows. If is the query image and is one of imagesin the data base, minimize the distortion betweenand . The goal thus is to find an image in the data basewhose distortion satisfiesfor (7)where is the number of data-base images. Concerningthe distortion between two images, we designate it asthe distance between two sequences of feature vectors. Tocalculate this distance, a measure of closeness between twofeature vectors has to be found. Since each feature vector isa characteristic color, the measure used in this paper is thecolor distance. Then we will introduce a dynamic matchingmethod to obtain the distance between two sequences offeature vectors.A. Color DistanceA color space describing colors close to human perceptionis crucial in calculating color difference based on color percep-tual similarity. The RGB color space, which is normally usedin the frame grabber of color-processing systems, does notcarry direct information about the color. For example, peoplecannot distinguish between colors by their (R,G,B) triplet.Contrary to the RGB color space, the empirically definedhue, value, saturation (HVC) space, which is a va