Similarity query processing in image databases

CHITRA is a prototype CBIR system we are building. It uses a four layer data model we have developed, and enables retrieval based on high level concepts, such as "retrieve images of MOUNTAINS", and "retrieve images of MOUNTAINS and SUNSET". This paper deals with some issues about query processing encountered in the implementation of the system. The contributions of this paper can be summarized in terms of processing the following four example queries (I₁, I₂, ....., I_k are images). Q₁: "retrieve images similar to I₁ based on color". Q₂: "retrieve images similar to I₁ based on colour AND texture". Q₃: "retrieve images similar to I₁, I₂, ...., I_k based on color". Q₄: "retireve images similar to I₁, I₂, ..., I_k based on color AND texture".First a brief review of basic CBIR query processing literature is provided (processing of Q₁). Processing in Q₂ involves efficient evaluation of combining functions, a problem that has attracted research attention in recent times. Fagin has given an algorithm for evaluating combining functions [11]. In this paper we provide probabilistic analysis of the expected cost of his algorithm. Based on the insight gained, we propose a new multi-step query processing algorithm and prove that it performs better than Fagin's algorithm for certain combining functions. We then consider the problem of processing Query By Multiple Examples (QBME). This problem is encoutered, when the user poses queries giving multiple example images and while processing high level concept definitions. We categorize the previous work (of processing single feature QBME) and propose a new category of algorithms. We have presented techniques of processing multiple feature, multiple example queries, a problem not addressed before. We define the semantics of such queries and propose various strategies for processing them. The traditional cost measures are not adequate to evaluate the relative merits of CBIR query processing algorithms. We have proposed a measure for evaluating query processing algorithms considering the retireval performance in addition to the traditional processing costs. Experimental results of various algorithms are given using the proposed evaluation measure.