Content Based Image Retrieval using Mobile Agents
Chetan Arora, Paramjeet Nirankari, Hiranmay Ghosh, Santanu Chaudhury Department of Electrical Engineering, Indian Institute of Technology, Delhi India
E-mail: santanuc@cse.iitd.ernet.in, ghosh@cdotd.ernet.in
Abstract
We present a generic architecture for content-based retrieval of images, which can be extended to the requirements of large distributed and heterogeneous collections. The sys- tem is modeled as a multi-agent system where an autonomous search agent encapsulates an independent image retrieval algorihtms. An optimal team of agents is dynamically se- lected for every retrieval problem. A flexible protocol allows for dynamic addition of search agents incorporating new pattern recognition techniques. These agents are coded as mo- bile agents, so that they can travel across a wide area network and analyze the documents at their sources. The separation of physical image forms and their logical structural com- position allows the search agents to operate over heterogeneous repositories. A prototype implementation validates the effectiveness of the architecture.
1: Introduction
The proliferation of pictorial documents on the web calls for their effective retrieval.
Classification of images based on associated annotations [1] is generally unsatisfactory . Extraction and comparison of image features, e.g., color and shape [2,3], provides a suitable alternative. The effectiveness of an algorithm for content-based image retrieval depends on a particular situation. For example, while a histogram based algorithm [5] may be more suitable for recognizing natural images, gabor filter based approach may be more suitable for textured images. [9].
In this paper, we have presented an extensible architecture for content-based retrieval, where many pattern recognition algorithms can be independently developed and be easily incorporated to the system. The retrieval system is realized with a multi-agent architecture, each agent encapsulating an independent pattern recognition algorithm. A registry provides the mechanism for selection of the agents with the right set of capabilities for a retrieval problem. The open-ended architecture allows the system to scale up to the requirements of a heterogeneous distributed collection. We encapsulate the pattern recognition algorithms in a set of mobile agents, which can replicate themselves and travel to the nodes holding the document repositories on demand and analyze the documents at their sources. This approach has reduced network traffic and computational bottlenecks significantly.
The rest of this paper is organized as follows. Section 2 provides an overview of the architecture. Section 3 describes the classification of the search agents based on their characteristics. Section 4 explains the retrieval process using the search agents. A prototype implementation and results are discussed in section 5. Finally, we conclude the paper with a summary of our contributions.
2: Overview of the Architecture
We model the retrieval software as a society of autonomous and communicating software agents, where each agent performs a definite role. A collaboration of these agents result in image retrieval. We have followed an object-oriented approach where each agent in an agent class complies with a generic interface which hides all implementation details. However, the interface definitions provides for enough flexibility for specialization. The major agent classes are as follows.
Media Search Agent (MSA): An MSA specializes in a certain pattern identifying strategy and possesses adequate structural knowledge to recognize patterns of interest.
Generic search agents implement common feature recognition algorithms, like identification of colors or simple shapes. Specialized search agents may incorporate specific intelligence for recognition of complex objects, e.g. the face of an important personality. We have realized the MSAs as mobile agents.
Repository Manager Agent (RMA): An RMA encapsulates an image collection in an administrative domain. The collection may be physically stored on a single node of the system, or distributed over a network (typically a LAN). A RMA hides the implimentation details of a repository and produces a standard view of the repository. It may classify documents with any available metadata.
User Interface Agent (UIA): UIA provides the human machine interface for the re- trieval system. We have provided a powerful query language by combining textual phrases and sample images. For example, a user query may specify text 'An Image of Lake' ac- companied with a sample picture, selected from a collection of thumbnails. User is also prompted to specify some QOS parameters, such as the maximum permissible response time, desired recall and precision values, etc. The UIA extracts the essential specifica- tions from the query. It also provides a user-friendly display and navigation facility for the results.
Search Co-ordinator Agent (SCA): The search strategy in our architecture adapts itself for every instance of query to achieve optimal performance. This requires appropriate sets of document collections and pattern recognition algorithms to be selected for every query. The Search Co-ordinator Agents (SCA) perform this role. In effect, an SCA selects an agent team for retrieval and coordinates their activities for optimal retrieval. An SCA can also optimize over multiple queries generated by the same or a number of users located at the same site
Registration Agent (RA): The agents in the open-ended system do not have a-priori knowledge of each others capabilities and communication addresses. The Registration Agents (RA) aid the agent community in resource discovery. Every agent, when installed in the system, registers itself with a RA. A capability based search [see Section 3] by a client with the RAs yields the set of prospective agents with the required capability set.
Each RA caters to a closed administrative domain.
The interactions between various classes of agents are depicted in figure l(a).
3: Characterization of MSAs
Different MSAs employ various pattern recognition techniques and have different com- putational overheads. Thus a choice has to be exercised depending on the performance
( EA ) ... ( RA )
if MSA ) (f MSA J) ... (f MSA
(a) Inter Agent Interactions
\ \ 7
\ \
EMA J
y—
RA
\
- ^
Im£image
Reference similarity matrix \ s>* Perceptual space
(b) Perceptual space for benchmarking
Figure 1. Inter Agent Interactions
requirement and the system constraints such as the current load scenario. In order to make an optimal choice of a set of MSAs for a particular query we need to characterize them on a common benchmark. This characterization is accomplished by Registry Server Agent on submission of MSA by the user. The agent is chrarcterised on the basis of subjective ranking in some orthogonal feature space formed on the basis of perceptual similarity. One of the ways could be as shown in figure l(b). Here, the agent characterization is done in four orthogonal capability directions. The feature vector in each direction is decided by the similarity matrix generated by running on the standard collection of images combined on the basis of perceptual similarity. Proposed Benchmarking algorithm not only characterizes MSAs on a exhaustive basis in whole of the perceptual space but also gives the system easy extensibility in order to incorporate new characteristics emerging as a result of continued research.
Since the open-ended architecture allows any research group to add new agents, there is every possibility that some agents do not lie in the perceptual similarity space used by the Registrar for benchmarking. These agents are typically meant for some specific application, for example, identifying tumors from a set of X-ray images. To account for these agents, we have denned a distinct agent class, called the 'special agents'. Instead of benchmarking, RA retains the 'concepts' and grades specified by the research group and updates them using the feedback received from the retrieval instances.
4: Retrieval Mechanism
We deal with the problem of image retrieval at four distinct levels which are
Query Refinement: A query comprises a textual phrase accompanied with a sample image and the QOS parameters. The textual phrase is used for defining the strategy and the scope of the search. SCA takes in two parameters for processing query namely criterion and concept. Criterion comprises low level features whereas concept comprises high level abstractions. Its the job of UIA to refine the user provided textual phrase to appropriate concept and criterion.
Collection Guidance : While it is possible to identify the desired image documents by comparing every document in the collection with the sample image, it might turn out to be prohibitively costly for any non-trivial collection. We use collection guidance to restrict the search to subsets of the collections. The RMAs classify the collection based on some pre- determined attributes and rank the various document categories based on those attributes.
The concepts extracted from the query are used to determine the appropriate document categories for conducting a search. The SCA enters into a bidding process with the RMAs with the conceptual specification provided by the UIA. Bidding results in selection of the appropriate document categories for conducting the search. The process not only reduces computational overheads, but also improves search performance in terms of elapsed time requirement and precision.
Search co-ordination: After the selection of suitable RMAs and suitable document categories at each RMA, an appropriate set of MSAs need to be chosen depending on each individual query. The required capability set for a query is determined from the terms extracted from the query criterion. The SCA consults the RAs with the required capability set and QOS constraints specified in the query. The Registrar conducts a capability based search on the agent characterization database [see Section 3]. The list of suitable agents thus arrived at, with their ranking is passed to the RMAs. The RMA makes the final selection after actually contacting the agents (and being sure of their current availability) and with appropriate considerations for computational requirements and other local conditions.
Pattern Extraction: The RMAs now schedule an appropriate set of MSAs on the selected document categories. The MSAs are downloaded from their respective hosts for the purpose. MSAs are run on suitable categories. Each of the MSAs provide a ranking to the analyzed documents signifying degree of match. The ranks are then combined by the RMA to arrive at an overall rank for an image in context of the query.The RMA can also implement appropriate security methods to prevent any downloaded agent from unauthorized access to the repository.
5: Implementation and Example
We have implemented the system in Java to make it platform independent. Java RMI has been used as the underlaying layer for agent communication. A public interface is denned for every class of agents. The methods in these interfaces define the generic communication protocol. Many of the parameters for these methods are denned as abstract objects to provide for flexibility. An ASN.l like language is denned to encode these objects. The mobility of the search agents is achieved through a combination of Java class downloading facility and RMI. The SecurityManager provides an elegant way to implement controlled access to the document repositories.
We have so far integrated seven search agents to the system. Each MSA employs a dif- ferent image matching algorithm. Five of the agents are generic. They implement standard algorithms, for example, using colour histograms[8], edge detection(Laplacian)[5], chro- maticity, correlogram property [6] and gabor(texture) [9]. There are two special agents, one specializes in recognition of faces of some personalities using eigen space matching [7] and the other uses local feature matching and can be optimized for identification of a particular logo or a flag.
Our document repository is populated with about 100 images. The query 'An Image of Lake' with sample image shown in figure 2 (leftmost image) demanding high recall resulted in retrieval of two images from the collection shown in figure 2 (two rightmost images).
One point should be highlighted here the particular results shown here are the capabilities of a particular MSA selected. The better algorithm encapsulated in MSA would have led to better retrieval. The advantage of the system lies in the fact that new algorithms can be
plugged (By registering them as new MSAs) in without making any changes in the system.
Figure 2. A typical query with results
6: Conclusions
We have developed a mobile agent based architecture for content-based retrieval from distributed image repositories. Every search agent encapsulates an independent pattern recognition algorithm. Retrieval takes place as the action of one or more agents on the image documents.
The agents communicate through a well-defined, yet flexible communication protocol, making the system extensible. Search agents incorporating new pattern analysis routines can be independently implemented and dynamically plugged in to the system, thereby enhancing its capabilities. The agents are categorized based on their capabilities. A reg- istry provides a mechanism for selection of agents with an appropriate capability set, for a particular retrieval problem. The mobile agents travel to the nodes holding the doc- ument repositories to analyze the documents at their sources. This approach minimizes the network traffic by eliminating the needs to transport the image documents across the network for classification. Though the system has been implemented for image documents, the concepts are general enough to be applied for any other media forms.
References
[1] E.J. Guglielmo, and N.C. Rowe, "Natural-Language Retrieval of Images Based on Descriptive Captions", IEEE Trans, on Information Systems, 14(3), 1996, pp. 237-267.
[2] M. Flicker, et al., "Query by Image and Video Content: The QBIC System", IEEE Computers, 28(9), 1995, pp. 23-32.
[3] R. Mehrotra and J. E. Gary, "Similar-Shape Retrieval In Shape Data Management", IEEE Computers, 28(9), 1995, pp. 57-62.
[4] A. Zhang, et al., "NetView: Integrating Large-Scale Distributed Visual Databases", IEEE MultiMedia, 7(3), 1998, pp. 47-59.
[5] B.V.Funt and G.D.Finalyson, "Color constant color indexing", IEEE Trans, on Pattern Analysis and Machine Intelligence, 17(5), 1995, pp. 122129.
[6] J. Huang, et al., "Image indexing using color correlogram", Proc. on Computer Vision and Pattern Recognition, 1997, pp 762768.
[7] M. Turk and A. Pentland, "Eigenfaces for recognition", J. of cognitive Neuroscience, 3(1), 1991, pp 7186.
[8] M.J. Swain and D.H. Ballard, "Color indexing", Int. J. Computer Vision, 7(1), 1991, pp 11-32.
[9] D. Swapp, "Estimation of visual textual Gradient using Gabor Function ", PhD thesis, Univ. of Ab- erdeen, Aberdeen, 1996, http://www.csd.abdn.ac.uk/publcations/theses/swapp.html.
