Content-based multimedia retrieval: indexing and diversification

The demand for efficient systems that facilitate searching in multimedia databases and collections is vastly increasing. Application domains include criminology, musicology, trademark registration, medicine and image or video retrieval on the web. This thesis discusses content-based retrieval techniques that can be applied on these databases. The most important operation to support is query-by-example: retrieve items that are to some extent similar to a given query. In chapter 2 we study vantage indexing, a generic indexing approach not limited to a specific domain, because it only requires a (preferably metric) way of calculating a distance between the objects. With vantage indexing, objects are no longer compared directly, but it is investigated how similar their resemblance is to a set of reference objects: the vantage objects. We present a new way of selecting vantage objects, and demonstrate experimentally the scalability of the approach and the improvement in retrieval performance over existing methods. In many applications, it is possible to represent the objects by graphs. In chapter 3 we propose an indexing strategy for these scenarios. The assumption is that the graph's topology can be used to describe the underlying object. This topology is stored the laplacian matrix, and the sorted set of eigenvalues (spectrum) of this matrix is used as an indexing signature. To account for partial similarity, the difference in spectra of many subgraphs is considered as well. Both theory and experimental work support the claim that similarity in laplacian spectrum predicts similarity between the original objects. The proposed representation outperforms existing methods in various application domains. A possible limitation of the approach presented in chapter 3 is that two graphs with the same topology share the same representation, while the underlying objects may be different. In chapter 4, we enrich the graph representation therefore by storing additional object properties. We develop a complex-valued analogue of the laplacian matrix, a Hermitian matrix, and use its eigenvector associated to the second smallest eigenvalue as indexing signature. This eigenvector is known to be informative about the graph, and can be reused to partition the graph into meaningful subgraphs, resulting in less subgraphs to compare for partial similarity. We provide a successful instance of this framework within the context of 3D object retrieval. In chapter 5, we claim that good retrieval results are not only relevant to the query, they should in fact reflect the diversity of the relevant objects that are present in the collection as well. Given an initial result set for a user query (image search), we propose to cluster the retrieved images based on their visual characteristics and to show the most important objects from each cluster. We first dynamically determine appropriate weights of visual features for a specific query. These weights are used in a dynamic ranking function that is deployed in a clustering technique to obtain a diverse ranking based on cluster representatives. We provide three lightweight and efficient clustering algorithms, and show that the algorithmic output coincides consistently with the results of a user study