Search

Highlighting important information of a network is commonly achieved by using random walks related to diffusion over such structures. Complex networks, where entities can have multiple relationships, call for a modeling based on hypergraphs. But, the limitation of hypergraphs to binary entities in co-occurrences has led us to introduce a new mathematical structure called hyperbaggraphs, that relies on multisets. This is not only a shift in the designation but a real change of mathematical structure, with a new underlying algebra. Diffusion processes commonly start with a stroke at one vertex and diffuse over the network. In the original conference article—(Ouvrard et al. 2018)—that this article extends we have proposed a two-phase step exchange-based diffusion scheme, in the continuum of spectral network analysis approaches, that takes into account the multiplicities of entities. This diffusion scheme allows to highlight information not only at the level of the vertices but also at the regrouping level. In this paper, we present new contributions: the proofs of conservation and convergence of the extracted sequences of the diffusion process, as well as the illustration of the speed of convergence and comparison between classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to two use cases, one based on Arxiv publications and another based on Coco dataset images. All the figures have been revisited in this extended version to take the new developments into account.

Despite the evolution of deep-learning-based visual-textual processing systems, precise multi-modal matching remains a challenging task. In this work, we tackle the task of cross-modal retrieval through image-sentence matching based on word-region alignments, using supervision only at the global image-sentence level. Specifically, we present a novel approach called Transformer Encoder Reasoning and Alignment Network (TERAN). TERAN enforces a fine-grained match between the underlying components of images and sentences, i.e., image regions and words, respectively, in order to preserve the informative richness of both modalities. TERAN obtains state-of-the-art results on the image retrieval task on both MS-COCO and Flickr30k datasets. Moreover, on MS-COCO, it also outperforms current approaches on the sentence retrieval task. Focusing on scalable cross-modal information retrieval, TERAN is designed to keep the visual and textual data pipelines well separated. Cross-attention links invalidate any chance to separately extract visual and textual features needed for the online search and the offline indexing steps in large-scale retrieval systems. In this respect, TERAN merges the information from the two domains only during the final alignment phase, immediately before the loss computation. We argue that the fine-grained alignments produced by TERAN pave the way towards the research for effective and efficient methods for large-scale cross-modal information retrieval. We compare the effectiveness of our approach against relevant state-of-the-art methods. On the MS-COCO 1K test set, we obtain an improvement of 5.7% and 3.5% respectively on the image and the sentence retrieval tasks on the Recall@1 metric. The code used for the experiments is publicly available on GitHub at https://github.com/mesnico/TERAN., Comment: Accepted in ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM). arXiv admin note: text overlap with arXiv:2004.09144

Adopting Convolutional Neural Networks (CNNs) in daily routine of primary diagnosis requires not only near-perfect precision, but also a sufficient degree of transparency and explainability of the decision making. With physicians being accountable for the diagnosis, it is fundamental that CNNs provide a clear interpretation of their learning paradigm, ensuring that relevant pathology features are being considered. Building on top of successfully existing techniques such as multi-task learning, domain adversarial training and concept-based interpretability, this paper addresses the challenge of introducing diagnostic factors in the training objectives. Here we show that our architecture, by learning end-to-end an uncertainty-based weighting combination of multi-task and adversarial losses, is encouraged to focus on pathology features such as density and pleomorphism of nuclei, e.g. variations in size and appearance, while discarding misleading features such as staining differences. Our results on the classification of tumor in breast lymph node tissue scans show significantly improved generalization, with best average AUC 0.89 (0.01) against the baseline AUC 0.86 (0.005). This result is a starting point towards building interpretable multi-task architectures that are robust to data heterogeneity. Our code is available at https://bit.ly/356yQ2u.

Twitter has significant potential as a source of Volunteered Geographic Information (VGI), as its content is updated at high frequency, with high availability thanks to dedicated interfaces. However, the diversity of content types and the low average accuracy of geographic information attached to individual tweets remain obstacles in this context. The contributions in this paper relate to the general goal of extracting actionable information regarding the impact of natural hazards on a specific region from social platforms, such as Twitter. Specifically, our contributions describe the construction of a model classifying whether given spatio-temporal coordinates, materialized by raster cells in a remote sensing context, lie in a flooded area. For training, remotely sensed data are used as the target variable, and the input covariates are built on the sole basis of textual and spatial data extracted from a Twitter corpus. Our contributions enable the use of trained models for arbitrary new Twitter corpora collected for the same region, but at different times, allowing for the construction of a flooded area measurement proxy available at a higher temporal frequency. Experimental validation uses true data that were collected during Hurricane Harvey, which caused significant flooding in the Houston urban area between mid-August and mid-September 2017. Our experimental section compares several spatial information extraction methods, as well as various textual representation and aggregation techniques, which were applied to the collected Twitter data. The best configuration yields a F1 score of 0.425, boosted to 0.834 if restricted to the 10% most confident predictions.

Cross-modal retrieval is an important functionality in modern search engines, as it increases the user experience by allowing queries and retrieved objects to pertain to different modalities. In this paper, we focus on the image-sentence retrieval task, where the objective is to efficiently find relevant images for a given sentence (image-retrieval) or the relevant sentences for a given image (sentence-retrieval). Computer vision literature reports the best results on the image-sentence matching task using deep neural networks equipped with attention and self-attention mechanisms. They evaluate the matching performance on the retrieval task by performing sequential scans of the whole dataset. This method does not scale well with an increasing amount of images or captions. In this work, we explore different preprocessing techniques to produce sparsified deep multi-modal features extracting them from state-of-the-art deep-learning architectures for image-text matching. Our main objective is to lay down the paths for efficient indexing of complex multi-modal descriptions. We use the recently introduced TERN architecture as an image-sentence features extractor. It is designed for producing fixed-size 1024-d vectors describing whole images and sentences, as well as variable-length sets of 1024-d vectors describing the various building components of the two modalities (image regions and sentence words respectively). All these vectors are enforced by the TERN design to lie into the same common space. Our experiments show interesting preliminary results on the explored methods and suggest further experimentation in this important research direction., Comment: Accepted at CBMI 2021

Computational pathology is a domain that aims to develop algorithms to automatically analyze large digitized histopathology images, called whole slide images (WSI). WSIs are produced scanning thin tissue samples that are stained to make specific structures visible. They show stain colour heterogeneity due to different preparation and scanning settings applied across medical centers. Stain colour heterogeneity is a problem to train convolutional neural networks (CNN), the state-of-the-art algorithms for most computational pathology tasks, since CNNs usually underperform when tested on images including different stain variations than those within data used to train the CNN. Despite several methods that were developed, stain colour heterogeneity is still an unsolved challenge that limits the development of CNNs that can generalize on data from several medical centers. This paper aims to present a novel method to train CNNs that better generalize on data including several colour variations. The method, called H&E-adversarial CNN, exploits H&E matrix information to learn stain-invariant features during the training. The method is evaluated on the classification of colon and prostate histopathology images, involving eleven heterogeneous datasets, and compared with five other techniques used to handle stain colour heterogeneity. H&E-adversarial CNNs show an improvement in performance compared to the other algorithms, demonstrating that it can help to better deal with stain colour heterogeneous images., Errata corrige Proceedings of the IEEE/CVF International Conference on Computer Vision 2021

This work proposes the use of deep learning architectures, and in particular Convolutional Autencoders (CAE’s), to incorporate an explicit component of orthogonality to the computation of local image descriptors. For this purpose we present a methodology based on the computation of dot products among the hidden outputs of the center-most layer of a convolutional autoencoder. This is, the dot product between the responses of the different kernels of the central layer (sections of a latent representation). We compare this dot product against an indicator of orthogonality, which in the presence of non-orthogonal hidden representations, back-propagates a gradient through the network, adjusting its parameters to produce new representations which will be closer to have orthogonality among them in future iterations. Our results show that the proposed methodology is suitable for the estimation of local image descriptors that are orthogonal to one another, which is often a desirable feature in many patter recognition tasks.

We present a novel cooperative strategy based on active learning and crowdsourcing, dedicated to provide a solution to the cold start stage, i.e. initializing the classification of a large set of data with no attached labels. The strategy is moreover designed to handle an imbalanced context in which random selection is highly inefficient. In this purpose, our method is guided by an unsupervised clustering, and the computation of cluster quality and impurity indexes, updated at each active learning step. The strategy is explained on a case study of annotating Twitter content w.r.t. a real flood event. We also show that our technique can cope with multiple heterogeneous data representations.

The estimation of local intrinsic dimensionality has applications ranging from adversarial attack disclosure to clustering and outlier detection, indexing, and data fingerprinting. In this paper, we analyze measures of network centrality in the kNN graph and their relation to LID measures. Our method ranks the dataset by its centrality, measured as the number of reverse or mutual kNN of each object. The computation of these measures involves only kNN queries, allowing a speedup in its computation using probabilistic indexing. A property of independent interest is the rank being independent of k for a wide range of k values, leading to parameter-free density estimation and applications.

Traditional verbatim browsers give back information linearly according to a ranking performed by a search engine that may not be optimal for the surfer. The latter may need to assess the pertinence of the information retrieved, particularly when s\(\cdot \)he wants to explore other facets of a multi-facetted information space. Simultaneous facet visualisation can help to gain insights into the information retrieved and call for further refined searches. Facets are potentially heterogeneous co-occurrence networks, built choosing at least one reference type, and modeled by HyperBag-Graphs—families of multisets on a given universe. References allow to navigate inside the dataset and perform visual queries. The approach is illustrated on Arxiv scientific pre-prints searches.

We address the problem of the statistical description of 3D surfaces with the purpose of automatic classification and retrieval of archaeological potsherds. These are particularly interesting problems in archaeology, as pottery comprises a great volume of findings in archaeological excavations. Indeed, the analysis of potsherds brings relevant cues for understanding the culture of ancient groups. In particular, we develop a new local shape descriptor for 3D surfaces, called the histogram of spherical orientations (HoSO), which we use in combination with a bag-of-words approach to compute visual similarity between 3D surfaces. Given a point of interest on a 3D surface, its local shape descriptor (HoSO) captures the distribution of the spherical orientations of its neighboring points. In turn, those spherical orientations are computed with respect to the point of interest itself, both in the azimuth and the zenith axis. The proposed HoSO is invariant to scale transformations and highly robust to rotation and noise. In addition, it is efficient, as it only exploits the information of the position of the 3D points and disregards other types of information like faces or normals. We performed experiments on a set of 3D surfaces representing potsherds from the Teotihuacan civilization and further validations on a set of 3D models of generic objects. Our results show that our methodology is effective for describing 3D models and that it improves classification performance with respect to previous local descriptors.

Permutation-based indexing is one of the most popular techniques for the approximate nearest-neighbor search problem in high-dimensional spaces. Due to the exponential increase of multimedia data, the time required to index this data has become a serious constraint. One of the possible steps towards faster index construction is utilization of massively parallel platforms such as the GPGPU architectures. In this paper, we have analyzed the computational costs of individual steps of the permutation-based index construction in a high-dimensional feature space and summarized our hybrid CPU-GPU solution. Our experience gained from this research may be utilized in other individual problems that require computing Lp distances in high-dimensional spaces, parallel top-k selection, or partial sorting of multiple smaller sets. We also provide guidelines how to balance workload in hybrid CPU-GPU systems.

Indexing exploits assumptions on the inner structures of a dataset to make the nearest neighbor queries cheaper to resolve. Datasets are generally indexed at once into a unique index for similarity search. By indexing a given dataset as a whole, one faces the parameters of its global structure, which may be adverse. A typical well-studied example is a high global dimensionality of the dataset, making any indexing strategy inefficient due to the curse of dimensionality. We conjecture that a dataset may be partitioned into subsets of variable indexability. The strategy is, therefore, to define a procedure to extract parts of the dataset with predictable indexability and to adapt the index structure to this parameter. In this paper, we define and discuss indexability related to the curse of dimensionality and propose a related heuristic to partition the dataset into low-dimensional parts. Each data object is ranked according to its degree centrality, under a connected sparse graph, the Half-Space Proximal Graph (HSP). We postulate centrality measures are good predictors of dimensionality and indexability. In view of validation, we conducted an experiment using the degree centrality of the HSP graph as unique dimensionality/indexability measure. We ranked the data objects by their respective centrality degree under the HSP graph, then extracted the lower dimensional subsets, recomputed the HSP and repeated. Subsets were then indexed with an exact method in increasing, decreasing and random order. We measured the complexity of a fixed set of queries for each of the three arrangements. For each set we used a fixed dataset with 250 queries. The above single experiment demonstrated that the heuristic can extract low dimensional subsets, and also that those subsets are easier to index. This initial results demonstrate the validity of our conjecture and motivate the need for exploring further the notion of indexability and related dataset partitioning strategies.

We propose a new method for input variable selection in nonlinear regression. The method is embedded into a kernel regression machine that can model general nonlinear functions, not being a priori limited to additive models. This is the first kernel-based variable selection method applicable to large datasets. It sidesteps the typical poor scaling properties of kernel methods by mapping the inputs into a relatively low-dimensional space of random features. The algorithm discovers the variables relevant for the regression task together with learning the prediction model through learning the appropriate nonlinear random feature maps. We demonstrate the outstanding performance of our method on a set of large-scale synthetic and real datasets. Code related to this paper is available at: https://bitbucket.org/dmmlgeneva/srff_pytorch.

This work presents a methodology for dimensionality reduction of images with multiple occurrences of multiple objects, such that they can be placed on a 2-dimensional plane under the constrain that nearby images are similar in terms of visual content and semantics. The first part of this methodology adds inductive capabilities to the well known t-SNE method used for visualization, thus making possible its generalization for unseen data, as opposed to previous extensions with only transductive capabilities. This is achieved by pairing the base t-SNE with a Deep Neural Network. The second part exploits semantic information to perform supervised dimensionality reduction, which results in better separability of the low-dimensional space, this is, it separates better images with no relevance, while retaining the proximity of those images with partial relevance. Since dealing with images having multiple occurrences of multiple objects requires the consideration of partial relevance, additionally we present a definition of partial relevance for the evaluation of classification and retrieval scenarios on images, or other documents, that share contents, at least partially.

This abstract states the position of the Publimape project, and unveils progress achieved since its recent start.

Most networks tend to show complex and multiple relationships between entities. Networks are usually modeled by graphs or hypergraphs; nonetheless a given entity can occur many times in a relationship: this brings the need to deal with multisets instead of sets or simple edges. Diffusion processes are useful to highlight interesting parts of a network: they usually start with a stroke at one vertex and diffuse throughout the network to reach a uniform distribution. Several iterations of the process are required prior to reaching a stable solution. We propose an alternative solution to highlighting the main components of a network using a diffusion process based on exchanges: it is an iterative two-phase step exchange process. This process allows to evaluate the importance not only of the vertices but also of the regrouping level. To model the diffusion process, we extend the concept of hypergraphs that are families of sets to families of multisets, that we call hb-graphs. This version is an extended version of arXiv:1809.00190v1: the overlaps with the v1 are in black, the new content is in blue. The contributions of this extended version are: the proofs of conservation and convergence of the extracted sequences of the diffusion process, as well as the illustration of the speed of convergence and comparison to classical and modified random walks; the algorithms of the exchange-based diffusion and the modified random walk; the application to a use case based on Arxiv publications. All the figures except one have been either modified or added in this extended version to take into account the new developments., arXiv:1809.00190v1: Accepted version of article submitted at CBMI 2018 IEEE This version is an extended version of arXiv:1809.00190v1 currently in submission

This article presents the information-theoretic based feature information interaction, a measure that can describe complex feature dependencies in multivariate settings. According to the theoretical development, feature interactions are more accurate than current, bivariate dependence measures due to their stable and unambiguous definition. In experiments with artificial and real data we compare first the empirical dependency estimates of correlation, mutual information and 3-way feature interaction. Then, we present feature selection and classification experiments that show superior performance of interactions over bivariate dependence measures for the artificial data, for real world data this goal is not achieved yet.

The K-Nearest Neighbor (K-NN) search problem is the way to find the K closest and most similar objects to a given query. The K-NN is essential for many applications such as information retrieval and visualization, machine learning and data mining. The exponential growth of data imposes to find approximate approaches to this problem. Permutation-based indexing is one of the most recent techniques for approximate similarity search. Objects are represented by permutation lists ordering their distances to a set of selected reference objects, following the idea that two neighboring objects have the same surrounding. In this paper, we propose a novel quantized representation of permutation lists with its related data structure for effective retrieval on single and multicore architectures. Our novel permutation-based indexing strategy is built to be fast, memory efficient and scalable. This is experimentally demonstrated in comparison to existing proposals using several large-scale datasets of millions of documents and of different dimensions. HighlightsA Multi-core indexing and searching implementations of our data structure.Test our proposal on the full CoPhIR dataset 106-million features.Compare our proposal to all the available permutation based indexing technique with larger datasets (1-million and 10-million).Compare our proposal to other approximate similarity search techniques like LSH-Forest and AM-Tree.

This article presents an integrated framework for multimedia access and analysis of ancient Maya epigraphic resources, which is developed as an interdisciplinary effort involving epigraphers (someone who deciphers ancient inscriptions) and computer scientists. Our work includes several contributions: a definition of consistent conventions to generate high-quality representations of Maya hieroglyphs from the three most valuable ancient codices, which currently reside in European museums and institutions; a digital repository system for glyph annotation and management; as well as automatic glyph retrieval and classification methods. We study the combination of statistical Maya language models and shape representation within a hieroglyph retrieval system, the impact of applying language models extracted from different hieroglyphic resources on various data types, and the effect of shape representation choices for glyph classification. A novel Maya hieroglyph data set is given, which can be used for shape analysis benchmarks, and also to study the ancient Maya writing system.

We describe a framework to build distances by measuring the tightness of inequalities, and introduce the notion of proper statistical divergences and improper pseudo-divergences. We then consider the H\"older ordinary and reverse inequalities, and present two novel classes of H\"older divergences and pseudo-divergences that both encapsulate the special case of the Cauchy-Schwarz divergence. We report closed-form formulas for those statistical dissimilarities when considering distributions belonging to the same exponential family provided that the natural parameter space is a cone (e.g., multivariate Gaussians), or affine (e.g., categorical distributions). Those new classes of H\"older distances are invariant to rescaling, and thus do not require distributions to be normalized. Finally, we show how to compute statistical H\"older centroids with respect to those divergences, and carry out center-based clustering toy experiments on a set of Gaussian distributions that demonstrate empirically that symmetrized H\"older divergences outperform the symmetric Cauchy-Schwarz divergence., Comment: 25 pages

MapReduce is a programming model proposed to simplify large-scale data processing. In contrast, the message passing interface (MPI) standard is extensively used for algorithmic parallelization, as it accommodates an efficient communication infrastructure. In the original implementation of MapReduce, the reduce function can only start processing following termination of the map function. If the map function is slow for any reason, this will affect the whole running time. In this paper, we propose MapReduce overlapping using MPI, which is an adapted structure of the MapReduce programming model for fast intensive data processing. Our implementation is based on running the map and the reduce functions concurrently in parallel by exchanging partial intermediate data between them in a pipeline fashion using MPI. At the same time, we maintain the usability and the simplicity of MapReduce. Experimental results based on three different applications (WordCount, Distributed Inverted Indexing and Distributed Approximate Similarity Search) show a good speedup compared to the earlier versions of MapReduce such as Hadoop and the available MPI-MapReduce implementations.

We present a supervised dimensionality reduction technique suitable for visualizing multi-label images on a 2-D space. This method extends the use of the well-known t-distributed stochastic embedding (t-SNE) algorithm to the case of multi-labels instances, where the concept of partial relevance plays an important role. Furthermore, it is applicable straightaway for weakly annotated data. We apply our approach to generate 2-D representations of Mayan glyph-blocks, which are groups of individual glyph-signs expressing full sentences. The resulting representations are used to place visual instances in a 2-D space with the purpose of providing a browsable catalog for further epigraphic studies, where nearby instances are similar both in semantic and visual terms. We evaluate the performance of our approach quantitatively by performing classification and retrieval experiments. Our results show that this approach obtains high performance in both of these tasks.

Traditional linear methods for forecasting multivariate time series are not able to satisfactorily model the non-linear dependencies that may exist in non-Gaussian series. We build on the theory of learning vector-valued functions in the reproducing kernel Hilbert space and develop a method for learning prediction functions that accommodate such non-linearities. The method not only learns the predictive function but also the matrix-valued kernel underlying the function search space directly from the data. Our approach is based on learning multiple matrix-valued kernels, each of those composed of a set of input kernels and a set of output kernels learned in the cone of positive semi-definite matrices. In addition to superior predictive performance in the presence of strong non-linearities, our method also recovers the hidden dynamic relationships between the series and thus is a new alternative to existing graphical Granger techniques.

This work extends the use of the non-parametric dimensionality reduction method t-SNE [11] to unseen data. Specifically, we use retrieval experiments to assess quantitatively the performance of several existing methods that enable out-of-sample t-SNE. We also propose the use of deep learning to construct a multilayer network that approximates the t-SNE mapping function, such that once trained, it can be applied to unseen data. We conducted experiments on a set of images showing Maya hieroglyphs. This dataset is specially challenging as it contains multi-label weakly annotated instances. Our results show that deep learning is suitable for this task in comparison with previous methods.

We present an approach for unsupervised computation of local shape descriptors, which relies on the use of linear autoencoders for characterizing local regions of complex shapes. The proposed approach responds to the need for a robust scheme to index binary images using local descriptors, which arises when only few examples of the complete images are available for training, thus making inaccurate the learning process of parameters of traditional neural networks schemes. Given the possibility of using linear operations during the encoding phase, the computation of the proposed local descriptor can be fast once the parameters of the encoding function are learned. After conducting a vast search, we identified the optimal dimensionality of the resulting local descriptor to be of only 128 dimensions, which allows for efficient further operations on them, such as the construction of bag representations with purposes of shape retrieval and classification. We evaluated the proposed approach indexing a collection of complex binary images, whose instances contain compounds of hieroglyphs from the ancient Maya civilization. Our retrieval experiments show that the proposed approach achieves competitive retrieval performance when compared with hand-crafted local descriptors.

This editorial introduces the Special Issue, which contains a selection of papers that present recent advances in a number of areas relating to image and video annotation and retrieval. Image and Video retrieval have now reached a state where successful techniques and applications have begun flourishing and technologies for retrieving multimedia content enable new applications and services for both commercial and personal end users. While existing techniques already provide promising results, recent advances such as the availability of large amounts of user-related data pose new challenges and generate the need for novel approaches to efficiently exploit them. Such data can be generated by the users explicitly, for example through tagging and participation in social media sharing properties, or implicitly, by analyzing user logs and feedback. In addition, affordable sensors provide further information, e.g. GPS data that can be used to increase the efficiency of existing solutions, such as concept detection. The aim of this special issue is to provide an overview of current research in emerging topics of image and video retrieval models and applications, while at the same time, including papers advancing the state of the art in related mature issues. Multimed Tools Appl (2011) 55:1–6 DOI 10.1007/s11042-010-0618-8

We introduce a method for estimation of rotation invariant local shape descriptors for 3D models. This method follows a successful idea commonly used to obtain rotation invariant descriptors in 2D images, and improves it by tackling the difficulty of the 3 degrees of freedom that exists in 3D models. Our method is simple, yet it achieves high levels of invariance after rotation transformations, and it produces short descriptors that can be efficiently used in several tasks. Such is the case of automatic classification of 3D surfaces with archaeological value, in which the proposed method attains state-of-the-art results in shorter times when compared with previous methods.

Providing a fast and accurate (exact or approximate) access to large-scale multidimensional data is a ubiquitous problem and dates back to the early days of large-scale Information Systems. Similarity search, requiring to resolve nearest neighbor (NN) searches, is a fundamental tool for structuring information space. Permutation-based Indexing (PBI) is a reference-based indexing scheme that accelerates NN search by combining the use of landmark points and ranking in place of distance calculation. In this paper, we are interested in understanding the approximation made by the PBI scheme. The aim is to understand the robustness of the scheme created by modeling and studying by quantifying its invariance properties. After discussing the geometry of PBI, in relation to the study of ranking, from empirical evidence, we make proposals to cater for the inconsistencies of this structure.

We analyze the performance of deep neural architectures for extracting shape representations of binary images, and for generating low-dimensional representations of them. In particular, we focus on indexing binary images exhibiting compounds of Maya hieroglyphic signs, referred to as glyph-blocks, which constitute a very challenging dataset of arts given their visual complexity and large stylistic variety. More precisely, we demonstrate empirically that intermediate outputs of convolutional neural networks can be used as representations for complex shapes, even when their parameters are trained on gray-scale images, and that these representations can be more robust than traditional handcrafted features. We also show that it is possible to compress such representations up to only three dimensions without harming much of their discriminative structure, such that effective visualization of Maya hieroglyphs can be rendered for subsequent epigraphic analysis.

Searching for similar objects within large-scale database is a hard problem due to the exponential increase of multimedia data. The time required to find the nearest objects to the specific query in a high-dimensional space has become a serious constraint of the searching algorithms. One of the possible solution for this problem is utilization of massively parallel platforms such as GPU architectures. This solution becomes very sensitive for the applications working with sparse dataset. The performance of the algorithm can be totally changed depending on the different sparsity settings of the input data. In this paper, we study four different approaches on the GPU architecture for finding the similar histograms to the given queries. The performance and efficiency of observed methods were studied on sparse dataset of half a million histograms. We summarize our empirical results and point out the optimal GPU strategy for sparse histograms with different sparsity settings.

Permutation-based indexing is one of the most popular techniques for the approximate nearest-neighbor search problem in high-dimensional spaces. Due to the exponential increase of multimedia data, the time required to index this data has become a serious constraint of the indexing techniques. One of the possible steps towards faster index construction is utilization of massively parallel platforms such as the GPGPU architectures. In this paper, we have analyzed the computational costs of individual steps of the permutation-based index construction in a high-dimensional feature space and proposed a hybrid solution, where computational power of GPU is utilized for distance computations whilst the host CPU performs the postprocessing and sorting steps. Despite the fact that computing the distances is a naturally data-parallel task, an efficient implementation is quite challenging due to various GPU limitations and complex memory hierarchy. We have tested possible approaches to work division and data caching to utilize the GPU to its best abilities. We summarize our empirical results and point out the optimal solution.

The first step in the analysis of video content is the partitioning of a long video sequence into short homogeneous temporal segments. The homogeneity property ensures that the segments are taken by a single camera and represent a continuous action in time and space. These segments can then be used as atomic temporal components for higher level analysis like browsing, classification, indexing and retrieval. The novelty of our approach is to use color information to partition the video into segments dynamically homogeneous using a criterion inspired by compact coding theory. We perform an information-based segmentation using a Minimum Message Length (MML) criterion and minimization by a Dynamic Programming Algorithm (DPA). We show that our method is efficient and robust to detect all types of transitions in a generic manner. A specific detector for each type of transition of interest therefore becomes unnecessary. We illustrate our technique by two applications: a multiscale keyframe selection and a generic shot boundaries detection.

Visual events occurring in video streams (such as human postures or more complex activities) are detected from a robust and generic region-based representation of the visual content and inferred using a spatio-temporal language that integrates domain-specific knowledge. More specifically, salient regions of activity are first extracted from the dynamic of the salient points along the scene. They are mapped to a vocabulary of the domain, using a state-of-the-art classifier, to describe the visual content in terms of semantic facts. Occurrences of events, modelled as assertions of a language representing spatio-temporal relationships between facts, are inferred from the description of videos by applying a forward-reasoning engine. An application to visual events retrieval in videos of meetings is presented as a test case.

Content-based image retrieval (CBIR) has been a very active research area for more than ten years. In the last few years the number of publications and retrieval systems produced has become larger and larger. Despite this, there is still no agreed objective way in which to compare the performance of any two of these systems. This fact is blocking the further development of the field since good or promising techniques can not be identified objectively, and the potential commercial success of CBIR systems is hindered because it is hard to establish the quality of an application. We are thus in the position in which other research areas, such as text retrieval or the database systems, found themselves several years ago. To have serious applications, as well as commercial success, objective proof of system quality is needed: in text retrieval the TREC benchmark is a widely accepted performance measures in the transaction processing field for databases it is the TPC benchmark that has wide support. This paper describes a framework that enables the creation of a benchmark for CBIR. Parts of this framework have already been developed and systems can be evaluated against a small, freely-available database via a web interface. Much work remains to be done with respect to making available large, diverse image databases and obtaining relevance judgments for those large databases. We also need to establish an independent body, accepted by the entire community, that would organize a benchmarking event, give out official results and update the benchmark regularly. The Benchathlon could get this role if it manages to gain the confidence of the field. This should also prevent the negative effects, e.g., “benchmarketing”, experienced with other benchmarks, such as the TPC predecessors. This paper sets out our ideas for an open framework for performance evaluation. We hope to stimulate discussion on evaluation in image retrieval so that systems can be compared on the same grounds. We also identify query paradigms beyond query by example (QBE) that may be integrated into a benchmarking framework, and we give examples of application-based benchmarking areas.

Permutation-based indexing is one of the most popular techniques for the approximate nearest-neighbor search problem in high-dimensional spaces. Due to the exponential increase of multimedia data, the time required to index this data has become a serious constraint of current techniques. One of the possible steps towards faster index construction is the utilization of massively parallel platforms such as the GPGPU architectures. In this paper, we have focused on two particular steps of permutation index construction – the selection of top-k nearest pivot points and sorting these pivots according to their respective distances. Even though these steps are integrated into a more complex algorithm, we address them selectively since they may be employed individually for different indexing techniques or query processing algorithms in multimedia databases. We also provide a discussion of alternative approaches that we have tested but which have proved less efficient on present hardware.

Searching for digital images in large-scale multimedia database is a hard problem due to the rapid increase of the digital assets. Metric Permutation Table is an efficient data structure for large-scale multimedia indexing. This data structure is based on the Permutation-based indexing, that aims to predict the proximity between elements encoding their location with respect to their surrounding. The main constraint of the Metric Permutation Table is the indexing time. With the exponential increase of multimedia data, parallel computation is needed. Opening the GPUs to general purpose computation allows to perform parallel computation on a powerful platform. In this paper, we propose efficient indexing and searching algorithms for the Metric Permutation Table using GPU and multi-core CPU. We study the performance and efficiency of our algorithms on large-scale datasets of millions of images. Experimental results show a decrease of the indexing time while preserving the quality of the results.

Relevance feedback algorithms improve content-based image retrieval (CBIR) systems by effectively using relevant/non-relevant images labeled by users. The main constraint of these algorithms is the update time for large datasets. Opening the graphics processing units (GPUs) to general purpose computation provides an opportunity for performing parallel computation on a powerful platform. In this paper, we suggest a fast interactive interface for CBIR which includes the conventional ranked list view along with two additional views based on fast k-means clustering and fast sampling-based multidimensional scaling (SBMDS) on a multi-core GPU architecture. We study the performance and efficiency of our framework on a collection of Maya syllabic glyph images. Experimental results show the improvement of retrieval performance at interactive speeds.

Content-Based Multimedia Indexing (CBMI) is the multi-disciplinary field broadly aiming at extracting knowledge from multimedia information and providing fluent access to it. CBMI research proposes to develop methods to model, abstract and organise multimedia data in view of fast, effective and accurate access. CBMI covers all the chain from the data to the user. It encompasses a large variety of challenges from multimedia information capture and representation via content understanding and information fusion to effective information indexing and retrieval. Since the early days, CBMI research has therefore produced a wide range of fundamental and application-oriented contributions and has provided methodological guidelines for progressing in the field. Due to its multi-disciplinary nature, CBMI research has also strongly been impacted by progress in adjunct domains such as machine learning, large-scale information storage and processing, and new modes of user interaction. The International Workshop on Content-based Multimedia Indexing has been established as one of the most important forums for the presentation of the newest ideas and original research results in the field. Following the eight successful previous events of CBMI (Toulouse 1999, Brescia 2001, Rennes 2003, Riga 2005, Bordeaux 2007, London 2008, Chania 2009, Grenoble 2010 and Madrid 2011), CBMI 2012, the 10th edition of the workshop was organised by the LISTIC lab of the University of Savoie, in Annecy, France from June 27th to 29th, 2012. CBMI 2012 brought together

International audience; We propose a privacy protection framework for large-scale content-based information retrieval. It offers two layers of protection. First, robust hash values are used as queries to prevent revealing original content or features. Second, the client can choose to omit certain bits in a hash value to further increase the ambiguity for the server. Due to the reduced information, it is computationally difficult for the server to know the client’s interest. The server has to return the hash values of all possible candidates to the client. The client performs a search within the candidate list to find the best match. Since only hash values are exchanged between the client and the server, the privacy of both parties is protected. We introduce the concept of tunable privacy, where the privacy protection level can be adjusted according to a policy. It is realized through hash-based piece-wise inverted indexing. The idea is to divide a feature vector into pieces and index each piece with a sub-hash value. Each sub-hash value is associated with an inverted index list. The framework has been extensively tested using a large image database. We have evaluated both retrieval performance and privacy-preserving performance for a particular content identification application. Two different constructions of robust hash algorithms are used. One is based on random projections; the other is based on the discrete wavelet transform. Both algorithms exhibit satisfactory performance in comparison with state-of-the-art retrieval schemes. The results show that the privacy enhancement slightly improves the retrieval performance. We consider the majority voting attack for estimating the query category and ID. Experiment results show that this attack is a threat when there are near-duplicates, but the success rate decreases with the number of omitted bits and the number of distinct items.cont

This paper presents a new methodology for the automatic estimation of the optimal amount of visual words that can be removed from a visual dictionary, such that no harm is induced in the discriminative potential of the resulting bag-of-visual-words representations. The proposed approach relies on a special definition of the entropy of each visual word when considered as a random variable, and a new definition of the overlap of class models computed with a normalized Bhattacharyya coefficient. We combined our proposed methodology with a recent approach that labels visual words as stop-words showing that this combination is beneficial to reduce the dimensionality of bag representations, while obtaining good results in terms of classification accuracy and retrieval performance.

We investigate kernel density estimation where the kernel function varies from point to point. Density estimation in the input space means to find a set of coordinates on a statistical manifold. This novel perspective helps to combine efforts from information geometry and machine learning to spawn a family of density estimators. We present example models with simulations. We discuss the principle and theory of such density estimation.

This work introduces a new formulation of the Histogram-of-Orientations Shape-Context (HOOSC) descriptor [9], which has shorter dimensionality and higher degree of scale and rotation invariance with respect to previous formulations. We compare the performance of our proposed formulation in terms of dimensionality, computation time, robustness against scale and rotations transformations, retrieval precision and classification accuracy. Our results show that our approach outperforms previous formulations in all cases. We also propose the use of a normalized χ 2 test to compare the robustness of descriptors of different dimensionality against scale and rotations transformations.

Permutation-based indexing is a technique to approximate k-nearest neighbor computation in high-dimensional spaces. The technique aims to predict the proximity between elements encoding their location with respect to their surrounding. The strategy is fast and effective to answer user queries. The main constraint of this technique is the indexing time. Opening the GPUs to general purpose computation allows to perform parallel computation on a powerful platform. In this paper, we propose efficient indexing algorithms for the permutation-based indexing using multi-core architecture GPU and CPU. We study the performance and efficiency of our algorithms on large-scale datasets of millions of documents. Experimental results show a decrease of the indexing time.

In this paper, we present a model for characterising the skeleton of line images. For comparative purposes, we base our theoretical model formulation on the ideal ribbon-like non-branching image. The model developed is first contrasted with Blum's model and the wave propagation model. The aim of the proposed model is to avoid spurious branches of the skeleton and to refine the definition of centrality at sharp angles of the input image. The underlying concept of this model is based on a new definition for local width, derived from the idea of minimum base segment. This is first introduced in the real space, and then discretised for characterising a discrete skeleton. A graph theoretic approach, which is model-independent, is introduced for locating skeletons of non-branching images. By applying the graph-theoretic algorithm, performance evaluation of the proposed model is contrasted with Blum's original model by investigating reconstruction performance of the output skeletons.

Service Composition is an essential part of Service Oriented Architectures (SOA). The number of available alternatives for web services offering similar functional characteristics opens opportunities to maximise compositions based on criteria embedded into the Quality of Service (QoS). These non-functional criteria may be numerous and diverse, and arise from various constraints, making composition an optimal information fusion problem. A number of solutions have been offered to resolve the selection problem for web service composition, essentially relying on exploiting and combining absolute performance values for measuring multi-dimensional QoS. In this paper, we investigate the use of Rank Aggregation methods for performing adequate information fusion for web service selection in view of composition. Our goal is to take advantage of these methods working on ranks rather than on the direct values for inferring global QoS. We formalise our approach and demonstrate its validity via an empirical study. We further evaluate our approach on publicly available real data gathered from actual web service characteristics.

This paper extends the bag-of-visual-words representations to a bag-of-visual-phrases model. The introduced bag-of-visual-phrases representation is constructed upon a proposed method for probabilistic description of co-occurring visual words, which is adapted for each reference word. This bag-of-visual-phrases representation implicitly encodes spatial relationships among visual words, thus being a richer representation while remaining as compact as the bag-of-visual-words model. We demonstrate the effectiveness of our method with a series of statistical analysis and retrieval experiments, and show that it largely outperforms previous methods for construction of bag representations. Furthermore, our method allows to query traditional bag-of-words vs the proposed bag-of-phrases. We conducted retrieval experiments on a dataset of complex shapes, whose instances correspond to hieroglyphs of the pre-Columbian Maya culture from the ancient Americas.

Massive amounts of textual and digital data are created daily from business or public activities. The organisation, mining and summarization of such a rich and large information source is required to capture the essential and critical knowledge it contains. Such a mining is of strategic importance in many domains including innovation (eg to mine technological reviews and scientific literature) and electronic commerce (eg to mine customer reviews). Information content generally bears several important aspects, mapped onto visualisation dimensions, whose number needs to be reduced to enable relevant interactive exploration. In this paper, we propose a novel strategy to mine and organise document sets, in order to present them in a consistent manner and to highlight interesting and relevant information patterns they contain. We base our method on the formulation of a global optimisation problem solved by using the Traveling Salesman Problem (TSP) approach. We show how this compact formulation opens interesting possibilities for the mining of document collections mapped onto multidimensional information sets. We discuss the issue of scalability and show that associated scalable solutions exist. We demonstrate the effectiveness of our method over several types of documents, embedded into real business cases.

In this paper we explore the benefits of latent variable modelling of clickthrough data in the domain of image retrieval. Clicks in image search logs are regarded as implicit relevance judgements that express both user intent and important relations between selected documents. We posit that clickthrough data contains hidden topics and can be used to infer a lower dimensional latent space that can be subsequently employed to improve various aspects of the retrieval system. We use a subset of a clickthrough corpus from the image search portal of a news agency to evaluate several popular latent variable models in terms of their ability to model topics underlying queries. We demonstrate that latent variable modelling reveals underlying structure in clickthrough data and our results show that computing document similarities in the latent space improves retrieval effectiveness compared to computing similarities in the original query space. These results are compared with baselines using visual and textual features. We show performance substantially better than the visual baseline, which indicates that content-based image retrieval systems that do not exploit query logs could improve recall and precision by taking this historical data into account.