21-04-2011, 11:37 AM
Presented By
N.V.L Deepak & M.Ravi
[attachment=12548]
ABSTRACT:
A novel algorithm for image retrieval is presented in this paper. The basic idea of the new algorithm is that the constituent segments of the images are used to retrieve images within a digital library. Image retrieval using segments is distinctive in that the local features of the image are used to retrieve the image instead of the typically utilized global features. In our algorithm, the given image is first segmented into dominant components and then the features of these components are extracted to perform retrieval. The features corresponding to each component are used to calculate the distance between components in the matching process. Each image is ranked based on the component wise distance measure with respect to the query component.One of the advantages of the algorithm is that, for a given retrieval image, the user can select a query segment with which to perform retrieval, thus it can satisfy different needs from different users.
INTRODUCTION:
With the exponential growth in image databases available on the Internet, we need an efficient storage, cataloging and retrieval system for images. Images in a database are typically indexed using text annotation, which is dependent upon the language and point of view of the operator. Content based image retrieval (CBIR), in contrast, is the method of retrieving images similar to a given query image using only the content of the image. Many features such as color, texture, and shape represent the content of the image can.
There are many algorithms for image retrieval. However, most of them are based on the global features of the images [1]. One disadvantage of global feature-based image retrieval is that a user is often interested only in a single object or in a few objects in the image, whereas a global mechanism uses all features for retrieval, including the background features. In order to overcome his shortcoming of the global feature-based image retrieval, a new image retrieval algorithm based on local features is proposed.
The new algorithm exploits image segments in the retrieval process. In segment-based image retrieval, a given image is divided into homogeneous regions and retrieval is based on a subset of the objects present in the image. Automated segmentation is a very powerful tool in retrieval because the user can narrow the field of search by selecting the objects in the image. In this paper we attempt to provide a segmentation algorithm and retrieve images based on the component features. Color, texture and shape of the component are extracted and stored in a database for use in CBIR. Figure 1 provides a flow chart for the algorithm. The images in the library are segmented and features are extracted off-line. When retrieval is initiated, the query segments are matched with segments from the feature database and the retrieved images are displayed.
IMAGE SEGMENTATION AND FEATURE EXTRACTION:
Segmentation:
Segmentation is the process of dividing an image into homogenous regions. A standard k-means image classification algorithm [2] is used in this paper to segment the image. The k-means is implemented with a different initialization. In the algorithm, the color image is first converted into a grey scale image and then threshold into classes to initiate the k-means classification [2]. Here we use the RGB color space but we believe this algorithm can be implemented in other color spaces with the same amount of success. Let I represent the 2-dimensional color image. We get the grayscale image by converting R, G and B color values to gray scale. The k-means is initiated by thresholding the grayscale image into K classes. Since grayscale image approximately represents the variation in the color intensities in an image, we can increase the efficiency of the k-means classification by this initialization. For the first iteration, K initial 3-D cluster centers Z1 (1), Z2 (1)… ZK (1) (1 means the first iteration here) are calculated using the R, G, and B values of color image. Each dimension represents the cluster center in each color.
for all i = 1,2…K. Here Zi (1) is the cluster center and N is the number of pixels for the i-th cluster, 1 Ai(1) denotes the set of pixels whose cluster center is Zi(1). In subsequent iterations, the color image is used to iterate the k-means. The distance between the mean intensity of each class is calculated as the distance between two points in a 3-D (RGB) Euclidian space. For the n-th iterative step the pixels of the image can be distributed among the cluster centers using (x, y) ε Aj(n)
for all i = 1, 2., K; i≠j where A j(n) denotes the set of pixels whose cluster center is ) (n z j in the RGB domain. After each stage the cluster centers are updated using RGB intensities of all the pixels of the updated classes as follows
If the cluster size N j of each class j = 1,2…K remains unchanged, the classification is terminated.
Each class extracted from the k-means algorithm is stored as a binary matrix Bi
for all i = 1,2… K, where Bi is the binary matrix and T is the number of iterations. The binary classes are processed by a set of order statistic filters to connect any two unconnected components, which actually are a part of the same region in the image but are separated, for example, by a thin line. The morphology is also effective in disconnecting two regions, which are connected by a thin "isthmus" region. Bi'= median (Bi, M) for all i= 1,2…K where M is a window.
Each class i is labeled into pi regions using connected component labeling (with 4-connectivitity) [3][4]. Let Rit represent the t–th region in the i-th class. The region Risi with maximum area is chosen as the dominant component in each class.
Ci(x,y) =1, if (x,y) εRisi for all i=1,2,…,K. Where
is the region of maximum area of all the pi regions labeled in each class I which is stored in Ci . All the "holes" in the region Ci, with area very small compared to the area of component, are filled. Bright spots, noise and speckles in the image that become classified into a different class by the k-means algorithm usually cause these holes. This is achieved by labeling Ci as a foreground (Rfg) region and the rest as a background (Rbg) region. All the background regions whose boundaries are included in the component or the “holes” in the component and whose area is significantly small compared to the foreground region are merged into the component. This is done so that the boundary of the component now represents its shape.
After this post-processing, the components Ci ' are stored in the database for each image and are accessed when needed for retrieval. Figure 2 shows an example of our image segmentation algorithm.
Feature Extraction:
For each segment, we extract three features: color, texture and shape. Texture is an important feature, which describes the regularity, smoothness and coarseness of the image. Many techniques have been proposed to describe texture feature. We use the method developed in [5] to extract the texture features. The only difference is that the extraction of texture feature here is not from the whole image but from the segments. To calculate the coefficients a square is fit inside the component such that all parts of the square are inside the component. This part of the component is used to calculate the wavelet coefficients. The similarity in texture DT between any two components is calculated as the Euclidean distance between the derived wavelet coefficients.
where , W I, Q (K) and W j,D(K) are the energies in the k-th sub band of the i-th component of the query image Q and of the j-th component of the database image D, respectively. Color is another important feature used in image retrieval. In the recognition of objects, color has enormous importance because it is largely view invariant and resolution independent [6]. The color histogram is obtained by measuring the frequency of a particular color in the image array. A benefit of this basic representation is that histograms are invariant to translation and rotation [6]. For a given component of an image its color content is extracted in the form of the histogram of each R, G and B value. Here again the distance C D between components is calculated similarly taking the histogram values of each component.
where H i, Q , H j,D are the histogram values of the i-th component of the query image Q and of the j-th component of the database image D respectively. Besides color and texture, we also use shape to perform retrieval. Shape of an object can be used to distinguish the object from other objects with the same color and texture. The component i C of the i-th class is dilated [7] in order to get a smooth shape.
where Gi' is a structuring element. A shape description that is robust to translation, rotation and scaling is the Fourier shape descriptors (FSD). The standard FSD approach first samples the contour at equal angles and then measures the radial distances of the samples and the angles subtended at the center of mass of the contour. The main drawback of this contour sampling is the non-uniform sampling of the contour – the portions of the contour that are closer to the center of mass are sampled more densely than the parts that are more distant.
In our algorithm, we use a contour-tracing algorithm to trace the contours. The given contours are assumed to be closed, continuous and 8-connected. The radial sweep algorithm [8] is employed to trace the contour, which is then down-sampled at regular intervals to obtain the point coordinates. The center of mass of the contour is calculated by taking the average of the coordinates in the x and y directions. For each of the sampled points on the contour, the radial distance from the center of mass and the angle made with some starting point is calculated and stored. The radial distances and the angles of all the sampled points are derived and stored in a complex number form as shown in equation (7). We then normalize the radial distances for all the coordinates. The radial distances and the angles of all the sampled points are stored in the form of a complex-range vector. The real part of each complex number represents the distance, and the imaginary part represents the angle subtended
in radians as:
Z (i) = R(i) + Jθ(i). (7)
where R (i) is the radial distance and θ( I) is the angle subtended at the center of mass by the sample. The Fourier shape descriptors of the coordinates are calculated using the following equation [9]
where N is the number of sampled points. Here N = 64 and Z (k)is the kth Fourier coefficient. The magnitude of the Fourier coefficients for each image are calculated and stored for use in the retrieval of similar shapes. Let ZQ (k) and ZD (k) represent the coefficients of the query component and an image component in the database. The similarity between shapes S D of these two components is measured by
SEGMENTS BASED IMAGE RETRIEVAL
In the retrieval process, a query image is first segmented and the dominant components found are highlighted. Once a dominant component is chosen, the corresponding features are compared with the features of the other image components in the database, and the M closest matches are retrieved. In this paradigm, we use a similarity measure combing the three features. Let the normalized color similarity and the normalized texture similarity between two segments be C D and T D which can be obtained by the method in Eq. (5) and (6). S D is the normalized similarity, which can be obtained by (9). Then the similarity between two segments d is computed as
where Q is the query segment and the D is a segment from an image in the database. Wc, W t, and Ws are weights for color, texture and shape features respectively
