multidimensional indexing for image retrieval system

Question

Hi

 please, any one help me to solve my problem:

I am working now in trademark image retrieval system , now I was prepared my database space (i.e I compute more than one color features like color histogram , Mean Color, moment set ...), and I was used the distance measures to retrieve the images which are similar to the query image and I get a good result, I apply this procedure on 1000 trademark images. the Retrieval process take a long time, in order to speed the image retrieval in short time (in future I must apply my project on more than 10000 images) I must indexing the database space (features vector database). As you now their are many data structures for indexing like tree(Recursive Partitioning method) and their family like (Quad-trees, kd-tree, R*-tree, TV-tree, Vp_tree, B+-tree, grid file....) some of this technique are not suitable for Higher-multidimensional space(color histogram where is multidimensional space). Now who can I chose the suitable one for image retrieval ? and how can I implemented it in matlab ?

thanks

Answer 1

Hi

One avenue to explore would be to reduce the dimensionality of the space you want to index rather than to look for indexing techniques of higher dimensionality. For example, there are several ways to linearise the elements of a matrix so that it can be indexed in 1-dimension.

Another avenue would be multiple indexes, perhaps a simple index (eg mean color) for the first level of indexing, then moment set, then, well, that's something you'll have to look into.

Regards

Mark

Answer 2

the state of art of content based image retrival on large or very large dataset is based on "vocabulary trees". You can find something about this concept using google i suggest you to read the articles by nister & stewenius [link text][1] The idea is : 1) cluster the feature space in a hyerarchical way (for istance using a k-means clustering algorithm) 2) the clusters' centroids become nodes of a tree (the vocabulary tree). 3) in the leaves (also called visual words) u have to implement an inverted file which points to the images searching for similar features, in this way, becomes a matter of visiting the tree (in a procedure colled "quantization"). this is simpler than using a data structure as kd-tree (or similiar) becouse :

1. features are not rapresented in every node
2. the data structure is easy to be implemented