Abstract: Many geographical applications, medical, etc. are brought to manage images which occupy much place memory and which have similar characteristic to be similar or not very different. Sometimes these latter require to work on areas of images, to make the follow-up of the evolution of same areas in various images, to preserve different states from the same image, Each state corresponding to the result of an operation or a series of particular operations. We present, in this study a solution of this problem, based on the approach of Versions of Data bases, which consists in representing the colour images in the form of trees called Generic tree. This structure minimizes storage by sharing information between the images. This method makes it possible to apply various update operations as research, insertion, suppression and modification of the images simultaneously.
INTRODUCTION
Applications such as CAO, software engineering, Geographic’s Information Systems (GIS), need to preserve the history of data being manipulated. However this type of data has the characteristics of being bulky, complex and of large dimensions. Saving history is useful, in particular, it helps keep a trace of the updates and study the evolution of the modelled universe. For instance, it is the case in the follow-up of a pathology evolution in medical imagery. Users of images processing applications choose in cooperation way different treatments to different original images. These images and those resulting from their processing are stored in an independent way. This method of storage results in redundancy of information in the sense that stored images differ only by a few percent. An optimal way of storage is being sought by users in order to reduce the memory size needed by this type of data.
The aim of this study is to describe a process based on an Rtree structure capable of optimizing and managing the storage of similar images (the similarity between two images is defined by the distance between the trees representing these images). Such a structure minimises the space of storage by identifying the common parts of different images on which specifics operations can be done such as the insertion, the suppression and the comparison of region belonging to many images.
RTREE
The Rtree (Guttman, 1984) is a hierarchical structure, derived from the tree B and used to index the space objects or geometrics (Scholl et al., 1996). The space objects are represented by minimum rectangle including data (REM) on an image.
Example 1: The Fig. 1 represents an Rtree, built starting from a collection of fourteen objects. The space covered by each node sheets is represented by a rectangle in dotted line. There is overlapping of the rectangles associated with the nodes sheets. The rectangles including minima nodes of the Rtree are not represented on the Rtree.
PRINCIPLES OF THE R TREE GENERIC STRUCTURE
This structure is based on the following concepts: the division of information between trees representing the images, their similarity, the tree of images and the node generics (Manouvrier, 2000).
Share information: The Generic tree is based on the principle of division of areas between images. That is to say Im, a whole of images. If an area R has the same value set of image (I'm ⊂ Im,), this value is stored only once in the base and is associated to the whole of the identifiers of the images of I'm.
| Fig. 1: | RTree |
| Fig. 2: | Images organized out of Rtree |
In this case, one speaks about explicit division, because the identifier of each image sharing this value appears explicitly in the list of the images associated with this value.
If the images of unit Im are organized in tree structure, each image, except the root of the tree, has a single mother and an indefinite number of image girls. Consequently, the rule following of implicit division can be introduced: Except when the identifier of an image I is explicitly associated another value v, image I implicitly shares the value associated with its image mother.
If the tree organizing the images is stored, this rule of implicit division allows a compact representation of the whole of images, in particular when a great number of images share values of areas in several branches of the tree.
| Fig. 3: | The Rtree Generic storing the Rtree of Fig. 1 and 2 |
Similarity between images: The colour images are gathered, in the data base, according to a distance from similarity between the trees which represent them. This distance called R-similarity is proposed in order to optimize the storage of the images in the base.
The measurement of R-similarity between two images i and i’ is defined by the following equation:
S (i, i'): A number of nodes and identical areas between images i and i'.
U (i, i'): Total numbers (without doubled bloom) identifiers of the nodes and areas appearing in the trees R of images i and i'.
Example 2: The measurement of R-similarity, the two images represented by the Rtree N°1 (Fig. 1) and the Rtree N°2 (Fig. 2) is calculated as follows:
| • | |
| • | |
The images represented by their trees R N°1et N°2 are 0.9 R-similar.
Tree of images: The images represented by an Rtree Generic are organized using a structure called particular tree structure of Image or Hierarchy of tree.
The tree of images corresponds to the organization of various states of the same tree. A state derives from another because there is an update compared to the preceding state.
The Hierarchy of tree is used to optimize the space of storage by allowing the implicit division between images
Example 3: The Rtrees of Fig. 1 and 2 are organized out of Tree of images in Fig. 3.
Generic nodes of a generic Rtree: A Generic Rtree is composed of generic nodes. Each node is a table made up of lines. Each line contains a list of identifiers of Rtree and a value of node of Rtree. The value of a node of Rtree is a list of couples (rem, identifier). The various states of an Rtree can share nodes in the same way identifying and of the same value. Value v of a generic node N of Generic Rtree can take three values:
| • | When the node is internal, the value v is a list of couples (remi, nor) where nor is a node wire of N of minimum rectangle including remi included in the including rectangle associated N. |
| • | When the node is sheet, the value v is a list of couples (remi, oi) where oi is a space object of minimum rectangle including remi included in the including rectangle of N. |
| • | When the value is ⊥, means that the node does not exist in the trees R associated. |
Generic root: The root of the generic Rtree is regarded as a particular generic node. It allows the management of the evolution of the root of the Rtree, i.e., the follow-up of the various roots in the various states of the tree following insertions or suppressions in the tree. A generic root is made up of lines. Each line L contains a list of identifiers of Rtree, noted (a1…….., ap) and the identifier of a generic node ng. A line [(a1…….., ap), ng] of generic root means that the generic node ng is root of the tree in the states identified by ai, iε[1, p]. The value of this root is accessible to the reading from the generic node ng. The value of this node can vary from one state to another of the tree.
Example 4: The Fig. 3 represents a Rtree-Generic storing 3 Rtree identified from 1 to 3.
IMPLEMENTATION
We design a prototype named power RTG, it implements the mechanisms of the Generic Rtree. This prototype is developed in programming language BORLAND C++ Builder 5. The images managed by the prototype are similar colour images under Bitmap format organized out of Rtree. Our prototype is composed of a general window made up of several menus. The user can sail freely and can choose the operations which he wishes to apply to an image (posting, recording under format RT, insertion/suppression of an image of the base, visualization or search for an image of the base). The user can easily have information on the basis such as the R-similarity of the images, the graph of division which makes it possible to deduce the Tree from images.
| Fig. 4: | Series of images |
| Fig. 5: | Graph of images of the Fig. 4 |
Figure 5 shows the images of the series of images of the Fig. 4 such as the needs correspond to the identifiers and the label of each line corresponds to the value of the R-similarity between two images i and i'. For example the R-similarity between image 2 and 5 is equal to 0.5.
The following table gives the result of the establishment of our software for the storage of two example of image Database.
CONCLUSIONS
The representation of the fixed images is one of the essential elements of the multimedia applications. The handling of the images causes however problems much more complex than that of the text. Indeed, the image is an object with two dimensions, supposed to represent a space a th-dimensionnal space, has two major consequences: The volume of the data to be treated is much more significant;
The structure of these data is definitely more complex. Its follow that the storage and the representation of these data are restricted.
Structures of arborescent data are largely used in data processing and for persistent data, The Rtree is an effective structure of data making it possible to represent the images with two or three dimensions.
In this study, we describe the structure of the Generic Rtree. The prototype Power RTG is currently tested on similar series of images organized out of Rtree. The Generic Rtree allows storage of the similar colored images of as much better than the Tree of Images is well organized. The Generic Rtree facilitates several operations with knowing the update of an unspecified image, followed by an area in several images. This structure is thus very useful in applications when it is necessary to work on an image or several images simultaneously.