Content-based Image Retrieval Using Approximate

Shape of Objects

Agma J. M. Traina, André G. R. Balan, Luis M. Bortolotti, Caetano Traina Jr.

Computer Science Department – University of São Paulo at São Carlos – Brazil
[agma, agrbalan, lbortol, caetano]@icmc.usp.br

Abstract
This paper presents a new approach to retrieve images by content using a composition of relevant
features regarding texture, shape and brightness distribution. The first step of the method is a
segmentation process based on Markov Random Fields, which can be done automatically, having
as parameter the number of desired classes. The regions obtained in the segmentation guide the
extraction of measures from the original image producing a 30-dimensional feature vector used
in the image retrieval. The experiments showed that the feature vector has high discrimination
power and the time for retrieval operations are only fractions of seconds.

1. Introduction

The ever increasing amount of images acquired in hospitals and medical centers has motivated the
research on automatic algorithms to retrieve images based on their intrinsic characteristics instead
of textual annotations/descriptions about them. Content-based image retrieval (CBIR) techniques
work on the whole information embodied into an image and are not restricted to a textual description
about it. Reservations about such descriptions arise from their inherent subjectivity, because when
describing an image, the specialist can be concerned about only specific aspects of it, laying
important aspects of the image down. Therefore, we can see that the CBIR and the retrieval based
on textual descriptions of the images are orthogonal approaches, but can be integrated into a system,
bringing more power to a Hospital Information System or a Picture Archiving and Communication
System [4].
The selection of images from a dataset, as performed by a CBIR system, involves comparing pairs
of images assigning a similarity coefficient to each pair, where such similarity is measured by a
distance (dissimilarity) function. The comparison is executed through features extracted from the
images. These features are chosen to get the “essence” of the images, adequately characterizing each
image. Thus, an important problem in CBIR is the development of effective and efficient feature
extraction methods to represent images, allowing their faithful retrieval.
It is usual to group the image features in three main classes: color, texture and shape [1, 10].
Ideally, these features should be integrated to provide better discrimination in the comparison
process. The first and simpler class of features to extract is color, or brightness distribution, mainly
given by image histograms. To extract information about shape and texture is much more complex
and costly tasks, usually performed after the initial filtering provided by color features.
This paper presents an approach to retrieve images through an automatic segmentation technique
that allows to get approximate information about the shape of the regions in the images. The
segmentation is performed through a stochastic algorithm using the texture of the regions under
analysis. We found that the image features generated from the image regions allow higher
discrimination among images than the existing approaches.

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE
 2. Background
The majority of image retrieval systems focus mainly on color distribution. The most popular and
well-developed techniques are based on color or brightness histograms [3]. Although the process to
obtain the histograms have low computational cost, as it is obtained in linear time regarding the
image size, a histogram produces an ambiguous image representation, as two different images can
have the same histogram. However, histograms can provide a first sift for image retrieval systems,
as they only bring extra images, which can be further isolated using more elaborated and complex
techniques. Applying the more complex techniques on fewer images reduces the retrieval total cost.
Regarding medical images, we believe that features based on texture and shape of the image
regions can discriminate and separate images better, and would be more appropriated for CBIR
systems. There are several works in the literature dealing with techniques based on each approach,
such as [6, 9] for texture and [8, 11] for shape. Regarding medical images, we claim that the image
objects or structures have characteristics texture, which can guide to obtain the objects’ shape.
In this paper we are dealing with queries such as: “Find the three images most similar to the one
identified as ChestRX_JohnDoe”. This query can be answered if there exists a distance
(dissimilarity) function to compare the features of the query image (ChestRX_JohnDoe) with the
features of all images in the database.
Whenever a new technique for feature extraction is proposed, it is necessary to evaluate how
effective it is. A well-known tool used to make such evaluation is the Precision vs. Recall graph
[2]. Precision is the fraction of the retrieved images that are relevant to the query. In contrast,
recall is the fraction of relevant images that has been retrieved. As a rule of thumb, the graph closest
to the top of the chart indicates the best effectiveness of the retrieval approach.

3. The proposed technique

In medical images texture and shape are strongly related, due to the fact that objects (organs,
tissues and anomalies) have, most of the time, specific shape and texture. Therefore, distinct textures
in the image regions can be employed to segment the image objects.
The technique presented herein is based on that premise. The main idea is to search for the regions
in the image looking for typical groups of (statistically) equally textured elements. All parts of the
image segmented based on a specific texture represents a class of the image. Thus, the features are
extracted from the segmented classes, i.e., all parts of the unconnected elements. Figure 1 shows a
segmented image with five classes.

3.1. The segmentation method

A crucial step in the proposed technique is the discrimination of the textured regions. To segment
images based on texture, we have employed a stochastic approach that associates classes to image

Figure 1 - Indication of the classes over the segmented image.

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE
 regions. Such segmentation approach generally aims at finding an estimate that optimizes a given
criterion. Our method uses the minimization of the expected number of misclassified pixels criterion.
To address this issue, a Markov Random Field (MRF) model is applied to the pixel classification
map. The idea of MRFs is to represent an image through its local features, stating for each pixel its
dependence on the value of its neighbors. Such dependency is given by a conditional probability
distribution for every pixel under analysis. The resultant segmentation is achieved by alternating
between finding the MPM (Maximizer of the Posterior Marginals) estimate [5] of the class map and
estimating the parameters of the observed image model.
One of the advantages of using MRF as a texture model is the demand of relatively few parameters
[7]. The main parameter of a MRF is known as spatial iteration parameter, or simply temperature,
and it plays the role of adjusting the influence of one pixel classification in the classification of its
neighbors.
The segmentation of textured images based on stochastic models can be supervised or
unsupervised. In the supervised approach the model parameters are obtained through a training set
generated by similar images already segmented by a specialist. On the unsupervised approach the
parameters are estimated during the segmentation process through the observation of the target
image. We have been using this latest approach, where only the number of groups or classes must
be stated beforehand.

3.2. Feature vector

The first step to extract the image features is to apply the segmentation method based on MRFs.
The image is automatically segmented, concerning the texture of its elements, in a predefined number
of classes, which is a tunning parameter of the segmentation process. As no validation of the
segmented regions is made by the radiologist, we actually have an approximation of the image’s
objects.
The distribution of different textured regions is a global feature used to characterize the image
content. Thus, one way to apply this global feature is storing information for each textured region
separately, such as its positions and sizes, for example. Doing this, the use of the real shape of the
objects in the class is not mandatory, and the regions guide to find an approximate shape of the
objects. In this case it would be necessary to develop a relatively more complex schema for
comparison between two feature vectors. Our approach treats all the regions of the same class as
if they are in a single region, so the comparison between two feature vectors becomes simpler.
The features we consider for each class are: its center of the mass (centroid) given in Eq. 2, the
mass of the class (size in pixels) given in Eq. 1, its dispersion (see Eq. 3), its mean (see Eq. 4) and
its variance (see Eq. 5). The three first features (mass, centroid and dispersion) are computed from
the segmented image, whereas mean and variance are computed from the original image restricted
to the segmentation obtained. Mass (Eq. 1) is the size in pixels of the region. In other words, the
number of pixels that were classified as a given class. Assume that the result of segmenting image
I is the image S, and that the pair (x,y) represents a spatial location in the rectangular pixel lattice
where I and S are defined. Thus, Ix,y and Sx,y denote, respectively, the values of I and S at location
(x,y). The mass of the region labeled with the class c (mc) after the segmentation is given by:
mc = ∑ h ( x , y)
x,y
c (1)
where,
1 if S x,y ∈ c
hc = 
 0 if S x, y ∉ c
The center of mass (centroid) of the region labeled as c and denoted by oc, is given by the

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE
 coordinates xoc and yoc, where

∑ x ⋅ h ( x, y)
x,y
c ∑ y ⋅ h ( x, y)
x,y
c
(2)
xoc = , yoc =
mc mc
The dispersion feature is a summation of distances. That is, for each region i of a given class c,
the centroid oi,c = (xoi,c, yoi,c) is computed and then their distances to the centroid oc are summed as
follows:
dc = ∑
dist (oc , oi ,c )
i
(3)

where, dist ( oc , oi ,c ) = ( xoc − xoi ,c ) 2 + ( yoc − yoi ,c ) 2 is the Euclidean distance between oc
(the global class center) and oi,c (the center of region i of the class c).
Finally, as mentioned before, the mean and variance features of the class c are computed over the
original image I considering the resulting segmentation S, and they are respectively denoted by :c and
F2c. Formally, we have
∑I
x,y
x,y ⋅ hc ( x , y )
(4)
∑ (I
x,y
x, y − µ c ) ⋅ hc ( x , y )
(5)
µc = σ 2
c =
mc mc

Figure 2 - Composition of the feature vector of an image considering the features of all classes.

The proposed feature vector is built using these five features for each class. Since the centroid has
two values, we have six features per class. Figure 2 shows a graphical representation of the feature
vector for an image segmented in L classes. It is important to note that the composition of the vector
is driven by the mean feature. That is, the class with the smallest mean has its features in the
leftmost part of the vector and the class with the largest mean constitutes the rightmost part of the
vector. This approach, allied to an adjustment of the feature ranges, allows the use of Euclidian
distance to compare the feature vectors more
Table 1 - Summary of image datasets
uniformly.
Image Category Number of Images
4. Experiments
Angiogram 21
To evaluate the effectiveness of the proposed MR Pelvis 33
approach we worked on a variety of medical
image categories. Due to space restrictions, we MR Axial Head 50
show here only the results for the categories MR Sagittal Head 38
summarized in Table 1. Figure 3 shows an
example of a query applied on the image MR Coronal Abdomen 34
2854.jpg, using the proposed six features per MR Sagittal Spine 44
class. As we are using five classes per image

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE
 Figure 3 - Example of a CBIR query processed using the proposed method.

(the image background is not considered), the feature vector is 30-dimensional. As a basis for
comparison, we also executed the same queries using as feature vectors the brightness histograms
of the images, because the histogram is one of the most employed features to retrieve images by
content. Figure 4 shows the precision vs. recall plots for the two feature vectors, obtained by asking
5 similarity queries over the same randomly selected images. Each point of the graph is obtained by
the average of the 5 queries. The histograms are 256-dimensional vectors while the proposed feature
vector is only 30-dimensional, but achieves higher effectiveness in characterizing the images, for five
image categories, losing for the histogram only for the MR axial head images considering high values
of recall. However, for small recall values the proposed method still overpasses the retrieval by
histograms. As the size of the proposed feature vector is much smaller than the histogram's, the time
demanded to answer the queries is also smaller as well as the memory space demanded to store it.

1 1

0,8 0,8
Precision

Precision

0,6 0,6

0,4 0,4

0,2 0,2

0 0
0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1 0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1

Recall Recall

Angiogram MR Axial Pelvis MR Axial Head Angiogram MR Axial Pelvis MR Axial Head
MR Coronal Abdom en MR Sagittal Head MR Sagittal Spine MR Coronal Abdomen MR Sagittal Head MR Sagittal Spine

Figure 4 - Precision vs. Recall graphs for the 6 image classes when answering similarity
queries. (a) For the proposed approach using a 6-D feature vector, (b) For 256-D histograms
as feature vectors.

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE
 5. Conclusions

The proposed technique to built image feature vectors through image segmentation using textured
objects can deal with the problem of identifying the organs and anomalies presented in the image
exams. An interesting point of this approach is the use of unsupervised segmentation, which has
given promising results. The extracted features use only the regions given by the segmentation
method, which is done automatically, allowing to work with the approximate description of objects.
The drawback of the segmentation step is its high computational cost, as the segmentation of an
image of 300 x 400 pixels takes between 3 to 5 seconds in a AMD Athlon XP 2600 machine. But
as the generation of the feature vectors for the image database is done off-line, and only the query
image needs to have its features extract during the query processing, this cost is acceptable. As the
querying time is what really matters to the users, is important to notice that this time is only a
fraction of seconds, and that depends on the database size.

Acknowledgments
The authors are grateful to the Center of Image Science of the Clinical Hospital of the University
of São Paulo at Ribeirão Preto - Brazil, which kindly provided the project with the images used in
the experiments. This research has been supported, in part, by the Sao Paulo State Research
Foundation (FAPESP) under grants 02/07318-1, 03/01769-4 and by the Brazilian National Research
Council (CNPq) under grants 52.1685/98-6, 860.068/00-7 and 35.0852/94-4.

6. References
[1] Y. A. Aslandogan and C. T. Yu, "Techniques and Systems for Image and Video Retrieval," IEEE
Transactions on Knowledge and Data Engineering, Vol. 11, No. 1, Jan/Feb 1999, pp. 56-63.
[2] R. Baeza-Yates and B. A. Ribeiro-Neto, Modern Information Retrieval. Wokingham, UK: Addison-
Wesley, 1999.
[3] R. Brunelli and O. Mich, "On the Use of Histograms for Image Retrieval," Proc. IEEE Intl. Conf.
on Multimedia Computing and Systems (ICMCS), Florence, Italy, June 7-11, pp. 143-147.
[4] X. Cao and H. K. Huang, "Current Status and Future Advances of Digital Radiography and PACS,"
IEEE Engineering in Medicine and Biology Magazine, Vol. 9, No. 5, Sept-Oct, pp. 80-88.
[5] M. L. Comer and E. J. Delp, "The em/mpm Algorithm for Segmentation of Textured Images:
Analysis and Further Experimental Results," IEEE Transactions on Image Processing, Vol. 9, No. 10,
October 2000, pp. 1731-1744.
[6] P. W. Huang and S. K. Dai, "Image retrieval by texture similarity," Pattern Recognition, Vol. 36,
No. 3, March 2003, pp. 665-679.
[7] A. Rosholm, Statistical Methods for Segmentation and Classification of Images,, Ph.D. thesis,
Technical University of Denmark, 1997.
[8] M. Safar, C. Shahabi, and X. Sun, "Image Retrieval by Shape: A Comparative Study," Proc. IEEE
Int. Conf. On Multimedia and Expo, New York
[9] G. Sheikholeslami, W. Chang, and A. Zhang, "SemQuery: Semantic Clustering and Querying on
Heterogeneous Features for Visual Data," IEEE Transactions on Knowledge and Data Engineering, Vol.
14, No. 5, September/October 2002, pp. 988-1002.
[10] A. W. M. Smeulders, M. Worring, S. Santini, A. Gupta, and R. Jain, "Content-Based Image
Retrieval at the End of the Early Years," IEEE Transactions on Pattern Analysis and Machine
Intelligence, Vol. 22, No. 12, December 2000
[11] D. Zhang and G. Lu, "Content-Based Shape Retrieval Using Different Shape Descriptors: A
Comparative Study," Proc. IEEE Conference on Multimedia and Expo (ICME'01), Tokyo, Japan, August
2001, pp. 317-320.

Proceedings of the 17th IEEE Symposium on Computer-Based Medical Systems (CBMS’04)

1063-7125/04 $ 20.00 © 2004 IEEE