Other Free Encyclopedias » Online Encyclopedia » Encyclopedia - Featured Articles » Contributed Topics from A-E

Efficient Method for Image Indexing in Medical Application - INTRODUCTION, RELATED WORK, META-MODEL OF RELATIONS, Definition of Intersection Sets

salient images objects spatial

Richard Chbeir
University of Bourgogne, France


In last two decades, image retrieval has seen a growth of interests in several domains. As a result, a lot of work has been done in order to integrate it in the standard data processing environments (Rui, Huang, & Chang, 1999; Smeulders, Gevers, & Kersten, 1998; Yoshitaka & Ichikawa, 1999). To retrieve images, different methods have been proposed in the literature (Chang & Jungert, 1997; Guttman, 1984; Lin, Jagadish, & Faloutsos, 1994). These methods can be grouped into two major approaches: metadatabased and content-based approaches. The metadatabased approach uses alphanumeric attributes and traditional techniques to describe the context and/or the content of the image such as title, author name, date, and so on. The content-based approach uses image processing algorithms to extract low-level features of images such as colors, textures, and shapes. Image retrieval using these features is done by methods of similarity and hence is a non-exact matching.

The requirement of each method depends on the application domain. In this paper, we address the domain of medicine where image retrieval in particular is very complex and should consider:

  • Both content-based and metadata representations of images and salient objects. This guarantees a pertinent integration of all the aspects of image in order to capture pertinent information and to assure the relevance of all query types (Chbeir, Atnafu, & Brunie, 2002).
  • High-precision description of images. For example, the spatial data in surgical or radiation therapy of brain tumors is decisive because the location of a tumor has profound implications on a therapeutic decision (Chbeir, Amghar, & Flory, 2001; Chbeir et al., 2002). Furthermore, it is crucial to distinguish between similar situations. Figure 1 shows two different images of three salient objects that are traditionally described by the same spatial relations in both cases: topological relations: a1 Touch a2, a1 Touch a3, a2 Touch a3; and directional relations: a1 Above a3, a2 Above a3, a1 Left a2.
  • The evolutionary aspect of image content (Chbeir, Amghar, Flory, & Brunie, 2001) such as tumor development in brain (Figure 2), virus changes, and so on. The detection of the evolutionary aspects of objects (displacement, deformation, contraction, rotation, etc.) can significantly help physicians to establish an appropriate diagnosis or to make a therapeutic or surgical decision. An example for such a query is: “Find treatments of lesion detected inside brain images where a size increasing has been observed at every examination between time t and t+n”.

In this article, we address the spatial and evolutionary issues of images. We propose a novel method that considers different types of relations. This method allows providing a highly expressive and powerful mechanism for indexing images.

The rest of this article is organized as follows: the next section is devoted to detail the related work. In the following section, we define our method of
computing the different relations and we show how image indexing can be done. The subsequent section demonstrates how our method can adequately index medical images. Finally, we conclude and give future work orientations.


The problem of image retrieval is strongly related to image representation. Computing relations between either salient objects, shapes, points of interests, etc. have been widely used in image representation such as R-tree and its variants (Beckmann, 1990; Guttman, 1984), hB-tree (Lomet & Salzberg, 1990), ss-tree (White & Jain, 1996), TV-tree (Lin et al., 1994), 2D-String and its variants (Chang & Jungert, 1997; Chang & Jungert, 1991; Chang, Shi, & Yan, 1987), and so on. Spatial relations are mostly used for indexing and retrieval purposes for its automatic detection capability.

Three major types of spatial relations are generally proposed in image representation (Egenhofer, Frank, & Jackson, 1989):

  • Metric relations measure the distance between salient objects (Peuquet, 1986). For instance, the metric relation “far” between two objects A and B indicates that each pair of points A i and B j has a distance grater than a certain value d.
  • Directional relations describe the order between two salient objects according to a direction, or the localisation of salient object inside images (El-kwae & Kabuka, 1999). In the literature, fourteen directional relations are considered:

    • Strict: north, south, east, and west.
    • Mixture: north-east, north-west, southeast, and south-west.
    • Positional: left, right, up, down, front and behind.

Directional relations are rotation variant and there is a need to have referential base. Furthermore, directional relations do not exist in certain configurations.

  • Topological relations describe the intersection and the incidence between objects. Egenhofer and Herring (1991) have identified six basic relations: disjoint, meet, overlap, cover, contain, and equal. Topological relations present several characteristics that are exclusive to two objects (i.e., there is one and only one topological relation between two objects). Furthermore, topological relations have absolute value because of their constant existence between objects. Another interesting characteristic of topological relations is that they are transformation, translation, and scaling invariant.

In spite of all proposed work to represent complex visual situations, several shortcomings exist in the methods of spatial relation computations. Particularly, traditional methods do not have the required expressive power to distinguish between similar situations in critical domains such as in medicine.

On the other hand, the evolution of image content needs to be taken into consideration in several domains. Any evolution needs to consider time and thus temporal relations. For that reason, two paradigms are proposed in the literature in order to compute temporal relations:

  • The first paradigm consists of representing the time as a set of instants: t 1 ,..t i ,..t n . Traditionally, only three temporal relations are possible between two objects: before, its symmetric relation after, and equal.
  • The second paradigm considers the time as a set of intervals [t i , t j ]. Allen relations (Allen, 1983) are often used to represent temporal relations between intervals. Allen proposes 13 temporal relations (Figure 3), in which six are symmetrical.

For instance, in geographic applications, spatio-temporal queries (Bonhomme, Trepied, Aufaure, & Laurini, 1999) are used more and more to study the translation of a mobile object, the evolution of spatial objects, and so on. In the medical domain, images are evolutionary in nature. Their content evolution description can provide an important support for the treatment of diseases. To the best of our knowledge, the evolutionary content of medical images was only studied by Cárdenas, Ieong, Taira, Barker, and Breant, (1993); Chu, Hsu, Cárdenas et al. (1998). In Cardenas et al. (1993), the authors study the development of bones structures. They define a temporal evolutionary data model (TEDM). It extends traditional constructs. However, several evolutionary situations (such as deformation, expansion, contraction, etc.) are not considered.

In this paper, we present our indexing method that is capable to represent spatial relations in highly expressive manner and to provide efficient technique to detect evolutionary content of images.


Our proposal represents a generalized extension of the 9-Intersection model and its variants (Egenhofer & Franzosa, 1991). It provides a method for computing not only topological relations but also other types of relations with higher precision.

The idea is to identify relations of two values (or instances) on the basis of the same feature (such as shape, position, time, etc.). For example, the shape feature expresses spatial relations, the time feature provides temporal relations, and so on. To identify a relation between two feature values, we use an intersection matrix between several sets defined below.

Definition of Intersection Sets

Let us first consider a feature F. We define its intersection sets as follows:

  • The interior F O contains all elements that cover the interior or the core of F. In particular, it contains the barycentre of F. The definition of this set has a great impact on the other sets. F O may be empty (Ø).
  • The boundary ?F contains all elements that allow determining the frontier of F. ?F is never empty (¬Ø).
  • The exterior F – is the complement of F O ??F. It contains at least two elements: the minimum value and the maximum value. F – can be divided into several disjoint exterior subsets. This decomposition depends on the number of the feature dimensions.

If the feature has only one dimension i (such as the acquisition time of a frame in a video), two exterior intersection subsets are defined (Figure 4):

  • F i ? (or inferior) contains elements of F – that do not belong to any other intersection set and inferior to ?F elements on the basis of i dimension.
  • F i ? (or superior) contains elements of F – that do not belong to any other intersection set and superior to ?F elements on the basis of i dimension.

If we consider a feature of two dimensions i and j (as the 2D shape of a salient object in Figure 5), we then define four exterior intersection subsets:

  • F i ? nF j ? (or inferior) contains elements of F – that do not belong to any other intersection set and inferior to F O and ?F elements on the basis of i and j dimensions.
  • F i ? nF j ? (or superior) contains elements of F – that do not belong to any other intersection set and superior to F O and ?F elements on the basis of i and j dimensions.
  • F i ? nF j ? contains elements of F – that do not belong to any other intersection set and inferior to F O and ?F elements on the basis of i dimension, and superior to F O and ?F elements on the basis of j dimension.
  • F i ? nF j ? contains elements of F – that do not belong to any other intersection set and superior to F O and ?F elements on the basis of i dimension, and inferior to F O and ?F elements on the basis of j dimension.

More generally and using the same reasoning, we are able to determine intersection sets (2n) of n dimensional feature.

In addition, we use a tolerance degree in the feature intersection sets definition in order to represent separations between sets and to provide a simple flexibility parameter for the computing process. For this purpose, we use two tolerance thresholds:

  • Internal threshold e i : defines the distance between F O and ?F,
    External threshold e e : defines the distance between subsets of F – .

Relations Computing Via Intersection Matrix

To calculate relation between two feature values, we establish an intersection matrix of their corresponding feature intersection sets. Matrix cells have binary values:

  • 0 whenever intersection between sets is empty
  • 1 otherwise

For two-dimensional feature (such as the shape) of two values A and B, we obtain the following intersection matrix.

The indexing relation between two values is expressed then by a binary value which is the juxtaposition of each raw of the corresponding intersection matrix. This is very important for indexing purposes.

Indexing Images

To index an image, we proceed as follows. First, we identify the spatial relations between the whole image and its salient objects. This allows determining the relative position of each object inside the image. In this case, the shape is used as a feature. The image is considered as a special object 1 that encloses all salient objects. We compute the intersection matrix of each pair of Image/Salient object. Figure 7 shows the result of this step on a 2D image I: three different spatial relations between the image I and its salient objects (a1, a2, and a3) are identified. It is important to mention that these relations are traditionally described by only one expression (i.e. northwest). We can see that, even at this level, our method provides a higher expression capability.

The second step consists of computing spatial relations between each pair of salient objects. Our method allows combining both directional and topological relation into one binary relation. The directional and topological relations are replaced by an expressive binary spatial relation between two salient objects. Figure 8 shows the result of this step where a distinguished 2 spatial relation is identified for each pair of salient objects of the image I.

Indexing Evolutionary Content

To index evolutionary content of images, we compare some of their features values. We consider that calibrating techniques are already applied before comparing. In Chbeir et al. (2001b), we identified several types of evolutionary possibilities in the medical domain. In this paper, we address only two major possibilities: the displacement and the transformation of salient object.

The displacement represents the evolution of salient object position between two images. For example, the displacement of a fibrinocruorique clot through a deep vein of the lower limb is very common in medicine. The displacement of a salient object can be captured by comparing its relative spatial relations with images, and then its spatial relations with other salient objects. Using our method, even similar and complex spatial situations are detected (see following below).

The transformation represents the evolution of an object shape between two images. For example, the expansion of tumor size inside the left lobe of a brain is an example of this type of evolution. The transformation can be expressed as deformation, contraction, stability, and so on. To detect salient object transformation, we consider the surface as a feature. In this case, the exterior set F – is considered as indivisible. We determine then the relation between the surface changes of the same salient object detected in two images. In the medical domain, it is obvious that the two images must belong to the same patient. Figure 9 snapshots some of the possible evolutionary relations that can be detected.


Let us consider a medical image with three salient objects a1, a2, and a3 (Figure 10) where shapes have changed during a period of time. These two situations resemble similar but actually different. The distinction between them must be well expressed especially in the application domains that require precision (such as in medicine). As shown in Figure 10, our method is capable to distinguish the different situations that are traditionally impossible to detect. The relations R 12 and R’ 12 are equal but both relations R 23 /R’ 23 , and R 13 / R’ 13 are clearly distinguished.

Furthermore, our indexing method allows detecting the salient objects transformations: the deformation of a3, and the contraction of both a1 and a2.


We presented the domain of spatio-temporal image indexing and an original method capable of considering different types of relations in image representation. With our method, it is possible to homogenize, reduce and optimize the relations in image description models (Chbeir et al., 2002). In this article, we showed how to provide a highly expressive power to spatial relations that can be applied to describe images and then to formulate complex visual queries. We also showed how to detect evolutionary content of images. The example in medical domain demonstrates how image indexing can be improved.

Currently, we are working on integrating such indexing method in our prototype EMIMS (Chbeir et al., 2001a; Chbeir et al., 2002). Future work includes considering indexing of low-level features (color, texture, etc.) and more intense experiments in complex environment where large number of feature dimensions (2,5D 3 and 3D images) and salient objects exist. Our method will also be studied to see if it can used in datagrid computing.

Egas Moniz, Antonio (C De A F) [next] [back] Edwards, Robert (Geoffrey)

User Comments

Your email address will be altered so spam harvesting bots can't read it easily.
Hide my email completely instead?

Cancel or