# Color-Texture-Based Image Retrieval System Using Gaussian Markov Random Field Model

Authors: Meng-Hsiun Tsai; Yung-Kuan Chan; Jiun-Shiang Wang; Shu-Wei Guo; Jiunn-Lin Wu
Journal: Mathematical Problems in Engineering
 (2009)

---

## Abstract

The techniques ofK-means algorithm and Gaussian Markov random field model are integrated to provide a Gaussian Markov random field model (GMRFM) feature which can describe the texture information of different pixel colors in an image. Based on this feature, an image retrieval method is also provided to seek the database images most similar to a given query image. In this paper, a genetic-based parameter detector is presented to decide the fittest parameters used by the proposed image retrieval method, as well. The experimental results manifested that the image retrieval method is insensitive to the rotation, translation, distortion, noise, scale, hue, light, and contrast variations, especially distortion, hue, and contrast variations.


---

## Body

## 1. Introduction

Much attention has been devoted to the design of image databases over the past few years [1–8]. Image retrieval is an important task in many image database applications, such as office automation, medical image archiving, digital library, multimedia publishing, computer-aided design, and geographic information systems.Most traditional and common methods of image retrieval utilize some method of adding metadata such as captioning, keywords, or descriptions to the images so that retrieval can be performed over the annotation words [4]. As these systems are built upon a large database, the textual-feature-based method becomes not only cumbersome but also inadequate to represent image contents. Hence, many content-based image retrieval (CBIR) systems have been proposed in the related literatures [1–8]. The CBIR aims at avoiding the use of textual descriptions and instead retrieves images based on their visual similarity to a user-supplied query image or user-specified image features.Low-level features, such as colors [9, 10], shapes [7, 8], and textures [11, 12], are extensively used to index the image features of the CBIR systems. The shape-based image retrieval system searches for images containing the objects similar to the objects specified by a query image. However, locating and recognizing objects from images is a real challenge. One of the difficulties is to separate the objects from background. These difficulties come from discretization, occlusions, poor contrast, viewing conditions, noise, complicated objects, complicated background, and so forth. Moreover, the shape-based image retrieval method can deal with only the images with simple object shapes efficiently. For complex object shapes, the region-based method has to build a binary sequence by using smaller grid cells so that more accurate results can be obtained; nevertheless, the storage of indices and retrieval time may increase tremendously.The color and texture attributes have been very successfully used in retrieving images with similar feature distributions. The color-based image retrieval method, such as the conventional color histogram (CCH) [13] and the fuzzy color histogram (FCH) [14], measures the similarity of two images with their distance in color space. The extraction of the color features follows a similar progression in each of the four methods: (1) selection of the color space, (2) quantization of the color space, (3) extraction of the color feature, (4) derivation of an appropriate distance function [13]. Color attribute may avoid object identification and extraction in image retrieval. Color may provide multiple measurements at a single pixel of the image, and often enable the classification to be done without complex object segmentation. Vu et al. [7] proposed a color-based image retrieval method, called a SamMatch method, to process the query by sampling-based matching approach. The SamMatch method has the benefits of region-based techniques without reliance on the highly variable accuracy of segmentation methods. However, this method requires the user to point out the object areas at the time of the query.Unfortunately, color-based image retrieval systems often fail to retrieve the images taken from the same scene but under different time or conditions, for example, the images of a countryside taken at dawn, dusk, or noon under a clear or a cloudy sky. In another scenario where a same scene is imaged by different devices, using one image taken by one device as the query example may fail to find the same scene taken by other devices.Texture attribute depicts the “surface” of an object. Intuitively, this term refers to properties such as smoothness, coarseness, and regularity of an object. Generally, the structural homogeneity does not come from the presence of a single color or intensity, but requires the interaction of various intensities within a region. Texture similarity is often useful in distinguishing objects with similar colors, such as sky and sea as well as leaves and grass. Making texture analysis is a real challenge. One of the ways to perform content-based image retrieval using texture as the cue is to segment an image into a number of different texture regions and perform a texture analysis on each region. However, segmentation can sometimes be problematic for image retrieval. In addition, texture is quite difficult to describe and subject to the difference of human perception. No satisfactory quantitative definition of texture is available at this time.The notion of texture appears to depend upon three ingredients [15]. First, some local “order” is repeated over a region which is large in comparison to the order's size. Second, the order consists in the nonrandom arrangement of elementary parts. Third, there are roughly uniform entities having approximately the same dimension everywhere within the textured region. Liu and Picard [16], and Niblack et al. [17, 18] used contrast, coarseness and directionality models to achieve texture classification and recognition. Huang and Dai [19] proposed a texture-based image retrieval method. The method associates one coarse and one fine feature descriptors with each image. Both descriptors are derived from the coefficients of wavelet transform of the original image. The coarse feature descriptor is used at the first stage to quickly screen out nonpromising images; the fine feature descriptor is subsequently employed to find the truly matched images. However, Huang’s method cannot give a high accuracy rate of precisely seeking the desired image.To solve the problems mentioned above, this paper proposes a color-texture-based image retrieval system (CTBIR method). The CTBIR method integrates the color and texture attributes of an image. It employsK-means algorithm [20] to classify the colors in all database images into clusters, then calculates the average of the pixel colors in each cluster, and uses this average color to represent the colors of the pixels in the cluster. Next, the CTBIR method utilizes Gaussian Markov random field model (GMRFM) to analyze the texture of each representative color in an image. A genetic algorithm is also provided to decide the most suitable parameters used in the CTBIR method. Besides, the performance of the CTBIR method is investigated by experiments. The effects of various image variations, such as rotation, translation, distortion, noise, scale, light, hue, and contrast on the performance of the CTBIR method are explored as well.


## 2. Related Works

This section will give a brief introduction of Gaussian Markov Random Field Model, genetic algorithm, and other techniques to be used in the CTBIR method.


### 2.1. Gaussian Markov Random Field Model

Texture plays a very significant role in analyzing image characteristics. Chellappa and Chatterjee [11] adopted GMRFM to describe the relationship between each pixel and its surrounding pixels. Generally, there exist some similarities and correlations in gray-level variance between adjacent pixels. In GMRFM, the varying degree of texture in images is statistically calculated mainly on the basis of the property. While Chellappa and Chatterjee used GMRFM to describe the textures of objects on an gray-scale image and segment the objects from the image, in this paper it will be used to characterize the textures of images in order to retrieve the images from a database which are most similar to the given query image.In GMRFM [12, 21–23], all the pixels in each mG×mG block B are classified according to their relationship with the central pixel x0,0. Figure 1 illustrates an example of GMRFM where mG=5 and (i,j) indicates the neighboring pixels xi,j of x0,0, where xi,j is the pixel belonging to the jth category in the ith rank relative to x0,0. A set of eigenvalues θi,j’s are employed to describe the relationship between each xi,j and x0,0 where x0,0 is calculated as [11] (2.1)x0,0=∑(i,j)∈Nx0,0θi,jxi,j+e.
In this formula, e indicates a Gaussian distribution of noises. Nx0,0 denotes the neighbors of x0,0 shown in Figure 1. Let X and θ be the column vectors composed, respectively, of xi,j and θi,j excluding x0,0and θ0,0. Then, one can calculate θ as follows:(2.2)θ=⌊∑XXT⌋-1⌊∑x0,0X⌋,
which can be used to depict the texture of B. The larger most of the values in vector θ is, the rougher B is; otherwise, B is smoother. Yue [8] also uses θ to describe the texture of a telemeter image of glacier and divides the image into some regions according to their textures.Figure 1
The neighborhood ofx0,0 with a block of 5×5 pixels.


### 2.2. Genetic Algorithm

Seo [24] applied a genetic algorithm for selection and feature combination in pattern recognition applications. Ballerini et al. [25] used a genetic algorithm to select a subset of texture features from all the features extracted. Lai and Chen [26] used the interactive genetic algorithm to tune human judgment results on similarity of images. Joshi and Tapaswi [2] applied a genetic algorithm to decide the most plausible matching between two images in image retrieval. Stejić et al. [6] proposed an image retrieval system using local similarity patterns. The system used a genetic algorithm to find an optimal assignment of similarity criteria to image regions. Chan and King [1] provided a trademark image retrieval system which employed a genetic algorithm to find the weighting factors in the dissimilarity function by integrating five shape features. This paper will adopt a genetic algorithm to decide the fittest parameters which will be used by the CTBIR method.Genetic algorithm (GA) [27] is a heuristic optimization method that operates through a determined and randomized search. The set of possible solutions for an optimization problem is considered as a population of individuals, and the degree of adaptation of an individual to its environment is specified by its fitness. A chromosome, essentially a set of character strings, represents the coordinate of an individual in the search space. A gene is a subsection of a chromosome that encodes the value of a single parameter that is being optimized. Typical encoding for a gene can be binary or integer.Derived from the biological model of evolution, genetic algorithms operate on the Darwinian principle of natural selection, which holds that, given a certain population, only the individuals that adapt well to their environment can survive and transmit their characteristics to their descendants. A genetic algorithm consists of three major operations: selection, crossover, and mutation. Selection evaluates all individuals, and only those best fitted to their environment survive. Crossover recombines the genetic material of two individuals to form new combinations with the potential for better performance. Mutation induces changes in a small number of chromosomal units with the goal of maintaining sufficient population diversity during the optimization process.


### 2.3. System Evaluation

Whenever a certain imagefq is selected as a query image, the image retrieval system delivers the user R database images whose matching distances to fq are shortest. If the desired database image is one of these R transmitted images, we say the system correctly finds out the desired image [9, 10]. Otherwise, the system fails to respond to the desired image. In the following experiments, the accuracy rate of querying for a system will be explained with ACC.The other evaluation, normalized modified retrieval rank (NMRR), proposed by MPEG-7 [28] is usually used as a benchmark for system evaluation. NMRR not only indicates how many of the correct items are retrieved, but also how highly they are ranked among the retrieved items. NMRR is defined by(2.3)NMRR(q)=(∑k=1NG(q)(Rank(k)/NG(q)))-0.5-(NG(q)/2)K(q)+0.5-0.5×NG(q),
where NG(q) is the size of the ground truth set for a query image q, Rank(k) is the ranking of the ground truth images by the retrieval algorithm, and K(q) specifies the “relevance rank” for each query. As the size of the ground truth set is normally unequal, a suitable K(q) is determined by(2.4)K(q)=min(4×NG(q),2×GTM),
where GTM is the maximum of NG(q) for all queries. If Rank(k)>K(q), then Rank(k) is changed into K(q)+1. The NMRR is in the range of [0,1], and the smaller NMRR is, the better the retrieval performance will be. ANMRR is defined as the average NMRR over a range of queries, and is given by(2.5)ANMRR=1NQ∑q=1NQNMRR(q),
where NQ is the number of query images.


## 2.1. Gaussian Markov Random Field Model

Texture plays a very significant role in analyzing image characteristics. Chellappa and Chatterjee [11] adopted GMRFM to describe the relationship between each pixel and its surrounding pixels. Generally, there exist some similarities and correlations in gray-level variance between adjacent pixels. In GMRFM, the varying degree of texture in images is statistically calculated mainly on the basis of the property. While Chellappa and Chatterjee used GMRFM to describe the textures of objects on an gray-scale image and segment the objects from the image, in this paper it will be used to characterize the textures of images in order to retrieve the images from a database which are most similar to the given query image.In GMRFM [12, 21–23], all the pixels in each mG×mG block B are classified according to their relationship with the central pixel x0,0. Figure 1 illustrates an example of GMRFM where mG=5 and (i,j) indicates the neighboring pixels xi,j of x0,0, where xi,j is the pixel belonging to the jth category in the ith rank relative to x0,0. A set of eigenvalues θi,j’s are employed to describe the relationship between each xi,j and x0,0 where x0,0 is calculated as [11] (2.1)x0,0=∑(i,j)∈Nx0,0θi,jxi,j+e.
In this formula, e indicates a Gaussian distribution of noises. Nx0,0 denotes the neighbors of x0,0 shown in Figure 1. Let X and θ be the column vectors composed, respectively, of xi,j and θi,j excluding x0,0and θ0,0. Then, one can calculate θ as follows:(2.2)θ=⌊∑XXT⌋-1⌊∑x0,0X⌋,
which can be used to depict the texture of B. The larger most of the values in vector θ is, the rougher B is; otherwise, B is smoother. Yue [8] also uses θ to describe the texture of a telemeter image of glacier and divides the image into some regions according to their textures.Figure 1
The neighborhood ofx0,0 with a block of 5×5 pixels.


## 2.2. Genetic Algorithm

Seo [24] applied a genetic algorithm for selection and feature combination in pattern recognition applications. Ballerini et al. [25] used a genetic algorithm to select a subset of texture features from all the features extracted. Lai and Chen [26] used the interactive genetic algorithm to tune human judgment results on similarity of images. Joshi and Tapaswi [2] applied a genetic algorithm to decide the most plausible matching between two images in image retrieval. Stejić et al. [6] proposed an image retrieval system using local similarity patterns. The system used a genetic algorithm to find an optimal assignment of similarity criteria to image regions. Chan and King [1] provided a trademark image retrieval system which employed a genetic algorithm to find the weighting factors in the dissimilarity function by integrating five shape features. This paper will adopt a genetic algorithm to decide the fittest parameters which will be used by the CTBIR method.Genetic algorithm (GA) [27] is a heuristic optimization method that operates through a determined and randomized search. The set of possible solutions for an optimization problem is considered as a population of individuals, and the degree of adaptation of an individual to its environment is specified by its fitness. A chromosome, essentially a set of character strings, represents the coordinate of an individual in the search space. A gene is a subsection of a chromosome that encodes the value of a single parameter that is being optimized. Typical encoding for a gene can be binary or integer.Derived from the biological model of evolution, genetic algorithms operate on the Darwinian principle of natural selection, which holds that, given a certain population, only the individuals that adapt well to their environment can survive and transmit their characteristics to their descendants. A genetic algorithm consists of three major operations: selection, crossover, and mutation. Selection evaluates all individuals, and only those best fitted to their environment survive. Crossover recombines the genetic material of two individuals to form new combinations with the potential for better performance. Mutation induces changes in a small number of chromosomal units with the goal of maintaining sufficient population diversity during the optimization process.


## 2.3. System Evaluation

Whenever a certain imagefq is selected as a query image, the image retrieval system delivers the user R database images whose matching distances to fq are shortest. If the desired database image is one of these R transmitted images, we say the system correctly finds out the desired image [9, 10]. Otherwise, the system fails to respond to the desired image. In the following experiments, the accuracy rate of querying for a system will be explained with ACC.The other evaluation, normalized modified retrieval rank (NMRR), proposed by MPEG-7 [28] is usually used as a benchmark for system evaluation. NMRR not only indicates how many of the correct items are retrieved, but also how highly they are ranked among the retrieved items. NMRR is defined by(2.3)NMRR(q)=(∑k=1NG(q)(Rank(k)/NG(q)))-0.5-(NG(q)/2)K(q)+0.5-0.5×NG(q),
where NG(q) is the size of the ground truth set for a query image q, Rank(k) is the ranking of the ground truth images by the retrieval algorithm, and K(q) specifies the “relevance rank” for each query. As the size of the ground truth set is normally unequal, a suitable K(q) is determined by(2.4)K(q)=min(4×NG(q),2×GTM),
where GTM is the maximum of NG(q) for all queries. If Rank(k)>K(q), then Rank(k) is changed into K(q)+1. The NMRR is in the range of [0,1], and the smaller NMRR is, the better the retrieval performance will be. ANMRR is defined as the average NMRR over a range of queries, and is given by(2.5)ANMRR=1NQ∑q=1NQNMRR(q),
where NQ is the number of query images.


## 3. Color-Texture-Based Image Retrieval System

This paper proposes a color-texture-based image retrieval system (CTBIR method) on the basis of the color and texture attributes of images. The system contains two phases—feature extraction and image matching. The feature extraction phase is to extract the GMRFM feature of an image. The image matching phase is to compare the GMRFM features of the given query image and each database image and then, deliver the most similar database image relative to the query image to the user.


### 3.1. Feature Extraction

For large sized blocks, the GMRFM feature needs high feature dimensions to precisely describe the texture of an image. The CTBIR method will require much memory space to hold the feature of the image and much time to compare the feature with that of each database image. In this paper, every gray-scale image is hence divided into many overlapping blocks of4×4 pixels, as shown in Figure 2(a), and the relationship of the positions for the 16 pixels in a block is depicted in Figure 2(b). Afterwards, each block B of 4×4 pixels is further partitioned into four overlapping subblocks, B1,1, B1,2, B2,1, and B2,2, of 3×3 pixels where each subblock Bi,j includes nine pixels: xi-1,j-1, xi-1,j, xi-1,j+1, xi,j-1, xi,j, xi,j+1, xi+1,j-1, xi+1,j, xi+1,j+1. Let θi,j in the GMRFM θ be the jth category in the ith rank in B. θi,j is defined as follows: (3.1)θi,j=∑h=12∑k=12θh,kBi,j4,
where θh,kBi,j, for h,k={1,2}, are the texture estimates and are computed as follows: (3.2)θ1,1Bi,j=xi,j×(xi,j-1+xi,j+1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ1,2Bi,j=xi,j×(xi-1,j+xi+1,j)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ2,1Bi,j=xi,j×(xi-1,j+1+xi+1,j-1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ2,2Bi,j=xi,j×(xi-1,j-1+xi+1,j+1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2).
As a result, each block B comprises four feature values θ1,1, θ1,2, θ2,1, and θ2,2.The cutting way for GMRFM feature and the relationship of positions.
(a)
The way to cut overlapped blocks of 4 × 4(b)
The relationship of positions for pixels in a blockEach pixel in a full color imageI consists of three color components: R, G, and B. The CTBIR method uses the three color components to construct three gray-scale images of the same size as I: Ir,Ig, and Ib, and each of which is entirely composed of R, G, and B color components from I, respectively. Next, I, Ir,Ig, and Ib are all divided into overlapping blocks of 4×4 pixels and the attributes θ’s in each block with regard to Ir,Ig, and Ib are calculated, which are, respectively, notated as θ1,1r, θ1,2r, θ2,1r, θ2,2r, θ1,1g, θ1,2g, θ2,1g, θ2,2g, θ1,1b, θ1,2b, θ2,1b, θ2,2b.In a full color image, a pixel is generally described by a 24-bit memory space; there are 224 possible colors in an image. However, it is impossible for most images to use all of the possible colors. In order to reduce the memory space required for storing image features and querying time, the CTBIR method employs K-means algorithm to group the pixels in all database images into K groups according to their colors. Moreover, the average color of all the pixels in one group is considered to be a representative color of all images (including database images and query image). The K representative colors comprise a common palette (CP).In every color imageI, the ith color Ci in CP is given a set of variables: θ1,1CPi,r, θ1,2CPi,r, θ2,1CPi,r, θ2,2CPi,r, θ1,1CPi,g, θ1,2CPi,g, θ2,1CPi,g, θ2,2CPi,g, θ1,1CPi,b, θ1,2CPi,b, θ2,1CPi,b, θ2,2CPi,b, and A. For each block B of 4 × 4 pixels in I, the average Ca of all the pixel colors in B is calculated. If Ca is similar to Ci in CP, the blocks θ1,1r, θ1,2r, θ2,1r, θ2,2r, θ1,1g, θ1,2g, θ2,1g, θ2,2g, θ1,1b, θ1,2b, θ2,1b, and θ2,2b are, respectively, added to θ1,1CPi,r, θ1,2CPi,r, θ2,1CPi,r, θ2,2CPi,r, θ1,1CPi,g, θ1,2CPi,g, θ2,1CPi,g, θ2,2CPi,g, θ1,1CPi,b, θ1,2CPi,b, θ2,1CPi,b, and θ2,2CPi,b, as well as Ai is increased by 1. Then, the CTBIR method adopts these θ’s and A’s of all colors in CP as the feature of I, where we call it the GMRFM feature of I. The GMRFM feature of I hence contains 12×K of θ’s values and K of A’s values, where Ai is the number of 4×4 blocks whose average pixel color is similar to one color Ci of CP in I. Hence, A’s can be used to describe the distribution of pixels colors in I, while the textures can be described by means of θ’s. On the whole, the distribution of the textures for different colors in I can be explained by A’s and θ’s.The GMRF model assumes that the texture field is stochastic, stationary and satisfies a conditional independence assumption. It is able to capture the local (spatial) contextual variations in an image and is effective for the analysis and synthesis of random looking textures. For each color imageI, the CTBIR method generates a set of θi,jCPk,r, θi,jCPk,g, θi,jCPk,b, and Ai for i,j={1,2} and 1≤k≤K. Here, (i,j) illustrates the orientation of GMRFM feature of I; CPk,r, CPk,g, and CPk,b are the three color components of the kth color in CP. Ai describes the color distribution of I. Hence, the GMRFM feature also can describe the texture orientation and color information of I.


### 3.2. Image Matching

Minkowski distance is widely used to calculate the distance between two multidimension vectors [5]. Suppose that (x1,x2,…,xK) and (x1′,x2′,…,xK′) are two K-dimension vectors. The Minkowski distance Dr of the two vectors can be defined by(3.3)Dr=(∑i=1K|xi-x′i|r)1/r,
where r is a user-defined constant. Dr is a Manhattan distance if r=1 and while Dr is a Euclidean distance in case of r=2.Letθi,jCPk,C and θ'i,jCPk,C, respectively, be the θi,jCPC of I and I′ with regard to the kth color in CP, where C=r, g, or b; i and j are 1 or 2 while Ak and Ak′ stand for A,respectively, of I and I′with regard to the kth color in CP. The image matching distance D between I and I′ is defined as follows:(3.4)D=∑k=1K∑C=r,g,b|Ak-A'k|r1(∑i=12∑j=12|θi,jCPk,C-θ'i,jCPk,C|r2)1/r2,
where r1 and r2 are two user-defined constants.


## 3.1. Feature Extraction

For large sized blocks, the GMRFM feature needs high feature dimensions to precisely describe the texture of an image. The CTBIR method will require much memory space to hold the feature of the image and much time to compare the feature with that of each database image. In this paper, every gray-scale image is hence divided into many overlapping blocks of4×4 pixels, as shown in Figure 2(a), and the relationship of the positions for the 16 pixels in a block is depicted in Figure 2(b). Afterwards, each block B of 4×4 pixels is further partitioned into four overlapping subblocks, B1,1, B1,2, B2,1, and B2,2, of 3×3 pixels where each subblock Bi,j includes nine pixels: xi-1,j-1, xi-1,j, xi-1,j+1, xi,j-1, xi,j, xi,j+1, xi+1,j-1, xi+1,j, xi+1,j+1. Let θi,j in the GMRFM θ be the jth category in the ith rank in B. θi,j is defined as follows: (3.1)θi,j=∑h=12∑k=12θh,kBi,j4,
where θh,kBi,j, for h,k={1,2}, are the texture estimates and are computed as follows: (3.2)θ1,1Bi,j=xi,j×(xi,j-1+xi,j+1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ1,2Bi,j=xi,j×(xi-1,j+xi+1,j)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ2,1Bi,j=xi,j×(xi-1,j+1+xi+1,j-1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2),θ2,2Bi,j=xi,j×(xi-1,j-1+xi+1,j+1)2×((∑h=-11∑k=-11xi+h,j+k2)-xi,j2).
As a result, each block B comprises four feature values θ1,1, θ1,2, θ2,1, and θ2,2.The cutting way for GMRFM feature and the relationship of positions.
(a)
The way to cut overlapped blocks of 4 × 4(b)
The relationship of positions for pixels in a blockEach pixel in a full color imageI consists of three color components: R, G, and B. The CTBIR method uses the three color components to construct three gray-scale images of the same size as I: Ir,Ig, and Ib, and each of which is entirely composed of R, G, and B color components from I, respectively. Next, I, Ir,Ig, and Ib are all divided into overlapping blocks of 4×4 pixels and the attributes θ’s in each block with regard to Ir,Ig, and Ib are calculated, which are, respectively, notated as θ1,1r, θ1,2r, θ2,1r, θ2,2r, θ1,1g, θ1,2g, θ2,1g, θ2,2g, θ1,1b, θ1,2b, θ2,1b, θ2,2b.In a full color image, a pixel is generally described by a 24-bit memory space; there are 224 possible colors in an image. However, it is impossible for most images to use all of the possible colors. In order to reduce the memory space required for storing image features and querying time, the CTBIR method employs K-means algorithm to group the pixels in all database images into K groups according to their colors. Moreover, the average color of all the pixels in one group is considered to be a representative color of all images (including database images and query image). The K representative colors comprise a common palette (CP).In every color imageI, the ith color Ci in CP is given a set of variables: θ1,1CPi,r, θ1,2CPi,r, θ2,1CPi,r, θ2,2CPi,r, θ1,1CPi,g, θ1,2CPi,g, θ2,1CPi,g, θ2,2CPi,g, θ1,1CPi,b, θ1,2CPi,b, θ2,1CPi,b, θ2,2CPi,b, and A. For each block B of 4 × 4 pixels in I, the average Ca of all the pixel colors in B is calculated. If Ca is similar to Ci in CP, the blocks θ1,1r, θ1,2r, θ2,1r, θ2,2r, θ1,1g, θ1,2g, θ2,1g, θ2,2g, θ1,1b, θ1,2b, θ2,1b, and θ2,2b are, respectively, added to θ1,1CPi,r, θ1,2CPi,r, θ2,1CPi,r, θ2,2CPi,r, θ1,1CPi,g, θ1,2CPi,g, θ2,1CPi,g, θ2,2CPi,g, θ1,1CPi,b, θ1,2CPi,b, θ2,1CPi,b, and θ2,2CPi,b, as well as Ai is increased by 1. Then, the CTBIR method adopts these θ’s and A’s of all colors in CP as the feature of I, where we call it the GMRFM feature of I. The GMRFM feature of I hence contains 12×K of θ’s values and K of A’s values, where Ai is the number of 4×4 blocks whose average pixel color is similar to one color Ci of CP in I. Hence, A’s can be used to describe the distribution of pixels colors in I, while the textures can be described by means of θ’s. On the whole, the distribution of the textures for different colors in I can be explained by A’s and θ’s.The GMRF model assumes that the texture field is stochastic, stationary and satisfies a conditional independence assumption. It is able to capture the local (spatial) contextual variations in an image and is effective for the analysis and synthesis of random looking textures. For each color imageI, the CTBIR method generates a set of θi,jCPk,r, θi,jCPk,g, θi,jCPk,b, and Ai for i,j={1,2} and 1≤k≤K. Here, (i,j) illustrates the orientation of GMRFM feature of I; CPk,r, CPk,g, and CPk,b are the three color components of the kth color in CP. Ai describes the color distribution of I. Hence, the GMRFM feature also can describe the texture orientation and color information of I.


## 3.2. Image Matching

Minkowski distance is widely used to calculate the distance between two multidimension vectors [5]. Suppose that (x1,x2,…,xK) and (x1′,x2′,…,xK′) are two K-dimension vectors. The Minkowski distance Dr of the two vectors can be defined by(3.3)Dr=(∑i=1K|xi-x′i|r)1/r,
where r is a user-defined constant. Dr is a Manhattan distance if r=1 and while Dr is a Euclidean distance in case of r=2.Letθi,jCPk,C and θ'i,jCPk,C, respectively, be the θi,jCPC of I and I′ with regard to the kth color in CP, where C=r, g, or b; i and j are 1 or 2 while Ak and Ak′ stand for A,respectively, of I and I′with regard to the kth color in CP. The image matching distance D between I and I′ is defined as follows:(3.4)D=∑k=1K∑C=r,g,b|Ak-A'k|r1(∑i=12∑j=12|θi,jCPk,C-θ'i,jCPk,C|r2)1/r2,
where r1 and r2 are two user-defined constants.


## 4. Genetic Algorithm-Based Parameter Detector

The performance of CTBIR method is significantly affected byr1 and r2. In this paper, a genetic algorithm-based parameter detector (GBPD) is used to determine the most suitable r1 and r2. The GBPD makes use of a binary string composed of m1+m2 binary bits to represent a chromosome Ch in which the first m1 bits and the remaining m2 bits are used to describe r1 and r2, respectively. For each chromosomeCh, r2 and r2 are encoded as r1=gap1×n1 and r2=gap2×n2, where n1 is the number of 1 bit in the first m1 bits of Ch, and n2 is the number of 1 bit in the remaining m2 bits of Ch; gap1 and gap2 are the maximum estimated errors of r1 and r2.For a certain application, one can accumulate some of its historic images (including database images and query images). After that, he can apply the accumulated historic images to train the most appropriate values forr1 and r2 via the genetic algorithm. In this genetic algorithm, we define the accuracy rate (ACC) obtained by the CTBIR method based on the accumulated historic images and the values of r1 and r2 encoded by a chromosome as the fitness of the chromosome.GBPD first randomly generatesN chromosomes, each with m1+m2 binary bits. To evolve the best solution, the genetic algorithm repeatedly executes mutation, crossover, and selection operations until the relative fitness of the reserved chromosomes is very similar.In the mutation operation, for each of theN reserved chromosomes, the GBPD uses a random number generator to specify one bit b1 from the first m1 bits and the other bit b2 from the remaining m2 bits in the chromosome. Later, b1 and b2 are replaced by⌝b1 and⌝b2 to generate a new chromosome, where ⌝ signifies the operator “NOT.”In the crossover operation, GBPD similarly uses a random number generator to designateN′ pairs of chromosomes from the N reserved chromosomes. Let Ch[i⋯j] be the substring consisting of the ith to jth bits in Ch. For each chromosome pair (Ch1,Ch2), the genetic algorithm concatenates (4.1)Ch1[1⋯⌊m12⌋],Ch2[(⌊m12⌋+1)⋯m1],Ch1[(m1+1)⋯(m1+⌊m22⌋)],Ch2[(m1+⌊m12⌋+1)⋯(m1+m2)]
into a new chromosome, and(4.2)Ch2[1⋯⌊m12⌋],Ch1[(⌊m12⌋+1)⋯m1],Ch2[(m1+1)⋯(m1+⌊m22⌋)],Ch1[(m1+⌊m12⌋+1)⋯(m1+m2)]
into other new chromosome.In the selection operation,N optimal chromosomes are selected from the N chromosomes reserved in the previous iteration along with the N and 2×N′ chromosomes created in the mutation and crossover operations according to their fitness. GBPD continuously performs the mutation, crossover, and selection operations, until the related fitness of the reserved N chromosomes is very close or the number of iterations is equal to the specified maximum number of generations (in this paper, the maximum number of generations is set to be 100). Finally, GBPD multiplies gap1 (resp., gap2) by the numbers of 1-bits in Ch[1⋯m1] (resp., Ch[m1+1⋯m1+m2]) to get r1 (resp., r2), where Ch is the chromosome having the best fitness in the N reserved chromosomes.Letm1=m2=14, gap1=gap2=0.1, and let Figure 3(a) be a chromosome Ch. Derived from Ch, r1=0.1×4=0.4, and r2=0.1×6=0.6. Figure 3(b) demonstrates a new chromosome created from Ch by the mutation operator, where the underlined bits are the randomly selected b1 and b2. Figure 3(c) displays two new chromosomes Ch1′ and Ch2′, generated from the two chromosomes Ch1 and Ch2 through the crossover operator.An example of GBPD.
(a)
A chromosomeCh(b)
A new chromosome created fromCh by mutation operator(c)
Two new chromosomesCh1′ and Ch2′derived from Ch1 and Ch2 by mutation operator


## 5. Experiments

The purpose of this section is to evaluate the performances of the CTBIR method by experiments. LetSetD={f1d,f2d,f3d,…,f1087d} and SetQ={f1q,f2q,f3q,…,f1087q} be two image sets, each of which contains 1087 full color images. The images in SetD are employed as the database images and those in SetQ are used as the query images. Some of them are captured from animations, where each image pair (fid,fiq) is randomly picked from a same animation. Most of the animations were downloaded from http://www.mcsh.kh.edu.tw. The rest of the images was scanned from natural images and trademark pictures.InSetD and SetQ, the former 500 images are almost cartoon images and the remainders are natural ones. Figure 4(a) shows parts of the query and database images in the former 500 ones of SetD and SetQ, and Figure 4(b) demonstrates parts of those in the latter 587 images of SetD and SetQ. In the following experiments, the parameters m1, m2, N, N′, gap1, and gap2 are given to be 40, 40, 20, 10, 0.05, and 0.05 to determine the most suitable r1 and r2 via the genetic algorithm. Moreover, the size K of CP is set to 16.Partial testing images.
(a)
Partial cartoon images(b)
Partial natural imagesThe first experiment is to investigate the performance of the CTBIR method in retrieving cartoon images. First, the images{f1d,f2d,…,f100d} and {f1q,f2q,…,f100q} are, respectively, specified to be the database images and the query images, and the GBPD is applied to determine the most suitable r1 and r2. The experimental results obtained by the GBPD tell that the most suitable r1 and r2 are 1.60 and 0.40. Then, the images {f1d,f2d,…,f500d} and {f1q,f2q,…,f500q} are used as the database images and the query images based on the most suitable r1=1.60 and r2=0.40.The second experiment is to scrutinize the performance of the CTBIR method in retrieving natural images. In this experiment,{f501d,f502d,…,f600d} and {f501q,f502q,…,f600q} are first taken as the database images and the query images, respectively, and the GBPD is employed to find out the most suitable r1=1.35 and r2=0.85. In the wake, {f501d,f502d,…,f1087d}and {f501q,f502q,…,f1087q} are used as the database images and the query images, and the CTBIR method is assigned to retrieve the expected database images with r1=1.35 and r2=0.85. Figure 5 shows the obtained r1, and r2, in 100 iterations obtained by the GBPD in experiments 1 and 2. This experimental result explains that a bigger r1is required to describe the cartoon images, since the color distributions between most natural images are more varied compared to those between most cartoon images even though the colors of both images are reduced to reserve only a few principal colors.Ther1 and r2 obtained by the GBPD in 100 iterations.
(a)
Cartoon images(b)
Nature imagesIn the third experiment, the images{f1d,f2d,…,f100d,f501d,f502d,…,f600d} and {f1q,f2q,…,f100q,f501q,f502q,…,f600q} are considered as the database images and the query images for determining the most suitable r1=1.65 and r2=0.50 by using the GBPD. Then, the images in SetD={f1d,f2d,f3d,…,f1087d} and SetQ={f1q,f2q,f3q,…,f1087q} are used as the database images and the query images based on the most suitable r1=1.65 and r2=0.50. Table 1 displays the results of the first to third experiments.Table 1
The results of the first to third experiments.
ExperimentImagesR1R2ACC (R =1) (%)ACC (R = 10) (%)ANMRRFirstPrevious 500 images inSetD and SetQ1.600.4091.596.80.079SecondLater 587 images inSetD and SetQ1.350.8577.891.80.231ThirdAll images inSetD and SetQ1.650.5082.493.20.161The fourth experiment is to compare the performances of the CTBIR, Huang’s and SamMatch methods by using the images inSetD={f1d,f2d,f3d,…,f1087d} and SetQ={f1q,f2q,f3q,…,f1087q}. Table 2 demonstrates the experimental results where r1 and r2 are given to be 1.65 and 0.50. The experimental results indicate that the CTBIR method gives much better ANMRR than Huang’s and SamMatch methods, especially for cartoon images. The CTBIR method totally spends 110.4 seconds to run the 1087 queries in this experiment. In this experiment, CP consists of K=16 colors each of which corresponds to twelve θ’s and one A; each value is held in a 4-byte memory space. Hence, the CTBIR method takes 1087×16×13×4=904,384 bytes to hold the whole GMRFM features of the 1087 database images.Table 2
The performances (ANMRR) obtained in Experiment 3.
MethodTesting imagesCTBIRHuang’sSamMatchPrevious 500 image pairs inSetD and SetQ0.0790.1370.229Later 587 image pairs inSetD and SetQ0.2310.2420.574All Images inSetD and SetQ0.1610.1940.415The SamMatch method resizes each image into a256×256 image, reduces all pixel colors in the image into only 256 colors, and divides the image into 16×16 blocks and uses the average colors of the blocks as the feature of the image. Hence, 113 samples evenly spread out in each image, and each dimension is held by a 4-byte memory space. It consumes 491.324 (=1087×113×4) bytes to hold the features of all database images. In addition, the SamMatch method takes 245.02 seconds to execute the 1087 queries. The Huang’s method consumes 620,928 bytes memory space to save the features of 1087 database images, and spends 125.6 seconds in running the 1087 queries.When one takes some pictures, the lens may be adjusted to different positions or different directions. Moving the position of certain objects or pixels on an image is called the shift variation of the image, rotating the objects in certain degree is called the rotation variation of the image, and being added some noises in the image is called the noise variation of the image. An image may be enlarged or reduced because of different camera resolution setups. We call this phenomenon a scale variation of the image. In the real world, the distortion variation is a very common phenomenon too. For example, putting a picture on an uneven plane may deform the objects on the picture. Besides that, the hue, contrast, and light variations, such as the image pairs in Figure6, may be often generated. These variations may make the image regarded as a different image from the original one by an image retrieval system. An excellent image retrieval method should be insensitive to these variations.Some variant image pairs.
(a)
Two scale variant images(b)
Two Shift variant images(c)
Two rotation variant images(d)
Two noise variant images(e)
Two distortion variant images(f)
Two lightness variant images(g)
Two hue variant images(h)
Two contrast variant imagesThe next experiment is designed to explore the capacities of the CTBIR method for resisting the variations of rotation, distortion, noise, scale, hue, luminance, and contrast in images. 100 full color imagesIq,1, Iq,2,…, Iq,100 are used as the query images. These 100 full color images comprise an image set Sq. Besides, this paper employs the rotation, distortion, noise, scale, hue, luminance, and contrast functions in ADOBE PHOTOSHOP 7.0 to process each Iq,i, and, respectively, generates the variant images Ir,i, Id,i, In,i, Is,i, Ih,i, Il,i, and Ic,i. The group of images Iα,1, Iα,2, …, Iα,100 forms an image setSα, which is produced by the same function where α = r, d, n, s, h, l, and c. Figure 7 shows some images in Sq, Sr, Sd, Sn, Ss, Sh, Sl, and Sc, respectively, where i is the image number in Sq, Sr, Sd, Sn, Ss, Sh, Sl, and Sc.Figure 7
Theith images in sets Sq, Sr, Sd, Sn, Ss, Sh, Sl, and Sc.In this experiment, all the images inSr, Sd, Sn, Ss, Sh, Sl, and Sc are employed as the database images, and the images in Sq as the query images. For the ith query, Iq,i is used as the query image and the CTBIR, Huang’s, and SamMatch methods are applied to retrieve the similar database images for the query image. Table 3 shows the experimental results. The ANMRRtotal in Table 3 is the accuracy (ANMRR) which the experiment obtains. Furthermore, the ANMRRr, ANMRRd, ANMRRn, ANMRRs, ANMRRh, ANMRRl, and ANMRRc in Table 3 are the accuracies (ANMRR) obtained by the experiments which take the images, respectively, in Sr, Sd, Sn, Ss, Sh, Sl, and Sc as the database images.Table 3
The results of the five experiment.
CTBIRHaung’sSamMatchANMRRtotal0.200.290.28ANMRRr0.210.920.95ANMRRd0.150.140.44ANMRRn0.350.540.21ANMRRs0.240.230.28ANMRRh0.190.120.11ANMRRl0.240.260.25ANMRRc0.180.160.02The experimental results show that the color feature is more significant than the texture feature in distinguishing different cartoon images; hence, a biggerr1 and smaller r2 should be provided. However, a smaller r1 and a bigger r2 should be assigned for recognizing natural images. The experimental results also indicate that the CTBIR method can offer impressive performances in resisting the rotation, translation, distortion, noise, scale, hue, light, and contrast variations, especially for distortion, hue, and contrast variations because it is indifferent to the shape, color, and light variations when describing the texture features of an image.


## 6. Conclusions

In this paper, a CTBIR method is proposed for image retrieval. The GMRFM feature is used to describe the texture and color information of an image. Based on this feature, the CTBIR method is used to deliver the database images, which are most similar to the given query image, to the user. The GBPD is offered to decide the fittest parameters ofr1 and r2, as well. The experimental results show that the CTBIR method is indifferent to the rotation, translation, distortion, noise, scale, hue, light, and contrast variations, especially distortion, hue, and contrast variations. Moreover, the CTBIR method could give a much better performances than those of the Huang’s and SamMatch methods. In the future, a subimage retrieval system based on the GMRFM feature will be developed. With a given query image IQ, the subimage retrieval system is to respond the images ID from a database so that IQ is very similar to a region on ID.



---

*Source: 410243-2010-02-02.xml*