Search

International audience; In this paper, we present a medical image integrity verification system to detect and approximate local malevolent image alterations (e.g. removal or addition of lesions) as well as identifying the nature of a global processing an image may have undergone (e.g. lossy compression, filtering ...). The proposed integrity analysis process is based on non significant region watermarking with signatures extracted from different pixel blocks of interest and which are compared with the recomputed ones at the verification stage. A set of three signatures is proposed. The two firsts devoted to detection and modification location are cryptographic hashes and checksums, while the last one is issued from the image moment theory. In this paper, we first show how geometric moments can be used to approximate any local modification by its nearest generalized 2D Gaussian. We then demonstrate how ratios between original and recomputed geometric moments can be used as image features in a classifier based strategy in order to determine the nature of a global image processing. Experimental results considering both local and global modifications in MRI and retina images illustrate the overall performances of our approach. With a pixel block signature of about 200 bit long, it is possible to detect, to roughly localize and to get an idea about the image tamper.

In this paper, the duality in differential form is developed between a 3D primal surface and its dual manifold formed by the surface's tangent planes, that is, each tangent plane of the primal surface is represented as a four-dimensional vector that constitutes a point on the dual manifold. The iterated dual theorem shows that each tangent plane of the dual manifold corresponds to a point on the original 3D surface, that is, the "dual" of the "dual" goes back to the "primal." This theorem can be directly used to reconstruct 3D surface from image edges by estimating the dual manifold from these edges. In this paper, we further develop the work in our original conference papers resulting in the robust differential dual operator. We argue that the operator makes good use of the information available in the image data by using both points of intensity discontinuity and their edge directions; we provide a simple physical interpretation of what the abstract algorithm is actually estimating and why it makes sense in terms of estimation accuracy; our algorithm operates on all edges in the images, including silhouette edges, self occlusion edges, and texture edges, without distinguishing their types (thus, resulting in improved accuracy and handling locally concave surface estimation if texture edges are present); the algorithm automatically handles various degeneracies; and the algorithm incorporates new methodologies for implementing the required operations such as appropriately relating edges in pairs of images, evaluating and using the algorithm's sensitivity to noise to determine the accuracy of an estimated 3D point. Experiments with both synthetic and real images demonstrate that the operator is accurate, robust to degeneracies and noise, and general for reconstructing free-form objects from occluding edges and texture edges detected in calibrated images or video sequences.

International audience; The maximum clique problem (MCP) is to determine in a graph a clique (i.e., a complete subgraph) of maximum cardinality. The MCP is notable for its capability of modeling other combinatorial problems and real-world applications. As one of the most studied NP-hard problems, many algorithms are available in the literature and new methods are continually being proposed. Given that the two existing surveys on the MCP date back to 1994 and 1999 respectively, one primary goal of this paper is to provide an updated and comprehensive review on both exact and heuristic MCP algorithms, with a special focus on recent developments. To be informative, we identify the general framework followed by these algorithms and pinpoint the key ingredients that make them successful. By classifying the main search strategies and putting forward the critical elements of the most relevant clique methods, this review intends to encourage future development of more powerful methods and motivate new applications of the clique approaches.

International audience; This paper addresses the question of assessing the relative reliability of unknown information sources. We propose to consider a phase during which the consistency of information they report is analysed, whether it is the consistency of each single report, or the consistency of a report w.r.t. some trusted knowledge or the consistency of different reports together. We adopt an axiomatic approach by first giving postulates which characterize how the resulting reliability preorder should be; then we define a family of operators for building this preorder and demonstrate that it satisfies the proposed postulates.

The winner determination problem (WDP) is a key issue in combinatorial auctions with many applications.We recast the WDP to a clique problem (MWCP) and solve it with a recent clique heuristic.The approach is assessed on three test suites of 530 benchmark instances.The approach outperforms the current best specific WDP heuristics in quality and efficiency.The approach is an useful alternative to solve the WDP in respect to the CPLEX solver. Combinatorial auctions (CAs) where bidders can bid on combinations of items is an important model in many application areas. CAs attract more and more attention in recent years due to its relevance to fast growing electronic business applications. In this paper, we study the winner determination problem (WDP) in CAs which is known to be NP-hard and thus computationally difficult in the general case. We develop a solution approach for the WDP by recasting the WDP into the maximum weight clique problem (MWCP) and solving the transformed problem with a recent heuristic dedicated to the MWCP. The computational experiments on a large range of 530 benchmark instances show that the clique-based approach for the WDP not only outperforms the current best performing WDP heuristics in the literature both in terms of solution quality and computation efficiency, but also competes very favorably with the powerful CPLEX solver.

cote interne IRCAM: Mitsufuji14a; None / None; National audience; This paper proposes a new method to enhance the performance of non-negative tensor factorization (NTF), one of the most prevalent source separation techniques nowadays. The enhancement is mainly achieved by introducing weights on bin-wise NTF cost functions, which differentiates NTF target components from other components so that the target should be approximated more precisely than others. Assuming sources are distributed sparsely in a 2-D sound field, the target components approximating a target source are exclusively selected by a user, or from accompanying images by means of providing a spatial cue to an NTF framework. The spatial cue is given in a similar format to the well-known binaural feature, inter-channel level difference (IID). This helps incorporate the spatial cue into the system, since the similar features of this format can be easily calculated from every spectrogram bin. The weighting functions are designed taking into account the distance between the spatial cue and the calculated features. Namely, the largest values are assigned to the spectrogram bins where the features present the highest similarity to the spatial cue, and the value decreases in proportion to the distance between them. The method is evaluated in terms of separation quality, comparing the proposed algorithm to the conventional NTF technique, PARAFAC-NTF, as well as other source separation techniques. The evaluation results measured by the metric signal-to-distortion ratio (SDR), signal-to-interference ratio (SIR), and signal-to-artifact ratio (SAR) demonstrate the effectiveness of the new method, improved primarily by the weighting function and the initialization based on IID, while demonstrating a decrease in computational costs, a significant problem with NTF.

Novelty-based segmentation of audio signals has proven good performances for the estimation of boundaries of structural sections within music pieces. However, boundaries are detected only if structural sections satisfy the condition of sufficient acoustic inner-homogeneity. While this constraint is very restrictive and not representative of all musical contents, we propose in this paper to extend the detection of acoustic novelty to transitions between homogeneous and non-homogeneous sections and vice versa. Moreover, the length of the considered sections for the boundary detection is crucial, we also introduce a multi-scale novelty approach that allows to capture boundaries between sections of different temporal scales in a same segmentation. Evaluation of the combination of these two methods proves convincing results for temporal segmentation of music pieces. Embedding the algorithm in a music structure segmentation system, we show that performances can be consistently improved for this task.

cote interne IRCAM: Lanchantin11a; None / None; National audience; Hidden Markov chains (HMC) are a very powerful tool in hidden data restoration and are currently used to solve a wide range of problems. However, when these data are not stationary, estimating the parameters, which are required for unsupervised processing, poses a problem. Moreover, taking into account correlated non-Gaussian noise is difficult without model approximations. The aim of this paper is to propose a simultaneous solution to both of these problems using triplet Markov chains (TMC) and copulas. The interest of the proposed models and related processing is validated by different experiments some of which are related to semi-supervised and unsupervised image segmentation.

This paper present a study on the diagnoses of blood cell nuclei from patients affected by the Progeria disease. Nuclei are characterized with various methods that analyze them shape and texture, and subsequently classify them by learning techniques. These methods extract "measures" from nuclei, which are used for the computation of a set of values named "indexes". These indexes are function bringing up real or discrete values that give information about geometrical, morphological and textural features of nuclei. A description model of nuclei is built based on this data, that is used to classify nuclei.

This article deals with logical and graphical representations of uncertain information in a quantitative possibilistic theory framework. We first provide a deep analysis of relationships between these two forms of representational frameworks. Then, we provide a novel algorithm for reasoning with quantitative possibilistic logic. The algorithm exploits the syntactic relations between quantitative possibilistic logic bases and penalty logic bases. We provide experimental results that compare the propagation algorithm developed for the possibilistic product-based networks and the inference algorithm developed in this paper. quantitative possibilistic theory, penalty logic, uncertainty propagation algorithm.

Two approaches for characterising scales are presented and compared in this paper. The first one was proposed three years ago by the musician and composer Pierre Audetat, who developed a numerical and graphical representation of the 66 heptatonic scales and their 462 modes, a new cartography called the Diatonic Bell. It allows sorting and classifying the scales according to their similarity to the diatonic scale.

cote interne IRCAM: Lanchantin08b; None / None; National audience; The hidden Markov chain (HMC) model is a couple of random sequences (X,Y), in which X is an unobservable Markov chain, and Y is its observable noisy version. Classically, the distribution p(y|x) is simple enough to ensure the Markovianity of p(x|y), that enables one to use different Bayesian restoration techniques. HMC model has recently been extended to "pairwise Markov chain" (PMC) model, in which one directly assumes the Markovianity of the pair Z=(X,Y), and which still enables one to recover X from Y. Finally, PMC has been extended to "triplet Markov chain" (TMC) model, which is obtained by adding a third chain U and considering the Markovianity of the triplet T=(X,U,Y). When U is not too complex, X can still be recovered from Y. Then U can model different situations, like non-stationarity or semi-Markovianity of (X,Y). Otherwise, PMC and TMC have been extended to pairwise "partially" Markov chains (PPMC) and triplet "partially" Markov chains (TPMC), respectively. In a PPMC Z=(X,Y) the distribution p(x|y) is a Markov distribution, but p(y|x) may not be and, similarly, in a TPMC T=(X,U,Y) the distribution p(x,u|y) is a Markov distribution, but p(y|x,u) may not be. However, both PPMC and TPMC can enable one to recover X from Y, and TPMC include different long-memory noises. The aim of this paper is to show how a particular Gaussian TPMC can be used to segment a discrete signal hidden with long-memory noise. An original parameter estimation method, based on "Iterative Conditional Estimation" (ICE) principle, is proposed and some experiments concerned with unsupervised segmentation are provided. The particular unsupervised segmentation method used in experiments can also be seen as identification of different stationarities in fractional Brownian noise, which is widely used in different problems in telecommunications, economics, finance, or hydrology.

Content based image retrieval using spatial image content (i.e. using multiple regions and their spatial relationships) is still an open problem which has received considerable attention in literature. In this paper we introduce a new representation of image based on the most general spatial image content representation that is Attributed Relation Graphs (ARG) representation and also a new method of image indexation. Like all CBIR systems, the one proposed here has two components: a segmentation component and a matching component using a novel inexact graph matching algorithm. We tested our work in lettrines image but it's also valid in general image.

In this paper, a graph classification approach based on a multi-objective genetic algorithm is presented. The method consists in the learning of sets composed of synthetic graph prototypes which are used for a classification step. These learning graphs are generated by simultaneously maximizing the recognition rate while minimizing the confusion rate. Using such an approach the algorithm provides a range of solutions, the couples (confusion, recognition) which suit to the needs of the system. Experiments are performed on real data sets, representing 10 symbols. These tests demonstrate the interest to produce prototypes instead of finding representatives which simply belong to the data set.

The learner follow-up in problem solving is a hard issue. It is more difficult when there are a lot of learners or when those learners use distance learning. We propose in this paper a two-dimensional graphic representation of student’s traces. To achieve this goal, we use and modify numerical analysis algorithms (automatic dimensionality reduction algorithms like Self Organizing Map and Stochastic Neighbour Embedding). We also propose a new distance between sets whose elements have semantic similarity. Finally, we validate and improve our algorithm with simulated data and experimental data., Le suivi d’apprenants lors de la résolution de problèmes est difficile, surtout lorsque le nombre d’apprenants est important ou lorsque la résolution de problèmes se fait à distance. Nous proposons ici une représentation graphique en deux dimensions des traces de ces apprenants qui pourrait être utilisée dans un logiciel de «monitoring » . Pour arriver à ce résultat nous avons adapté et combiné des algorithmes d’analyse numérique (principalement des algorithmes de réduction de dimensions : carte de Kohonen et SNE). Nous avons aussi abordé la problématique de distance entre ensembles en proposant une nouvelle mesure de similarité lorsque leurs éléments sont sémantiquement proches. Enfin nous avons validé et amélioré notre approche à l’aide tout d’abord de données simulées, puis de données réelles issues d’une expérimentation., Delestre Nicolas, Malandain Nicolas. Analyse et représentation en deux dimensions de traces pour le suivi de l’apprenant. In: Sciences et Technologies de l'Information et de la Communication pour l'Éducation et la Formation, volume 14, 2007. Les Dimensions émotionnelles de l'interaction dans un EIAH/Analyses des traces d'utilisation dans les EIAH. pp. 531-562.

Applicative and Combinatory Categorial Grammar is an extension of Steedman's Combinatory Categorial Grammar by a canonical association between rules and Curry's combinators on one hand and metarules which control type-raising operations on the other hand. This model is included in the general framework of Applicative and Cognitive Grammar (Desclés) with three levels of representation : (i) phenotype (concatened expressions) ; (ii) genotype (applicative expressions) ; (iii) the cognitive representations (meaning of linguistic predicates). The aim of the paper is : (i) an automatic parsing of phenotype expressions that are underlying to sentences ; (ii) the building of applicative expressions. The theoretical analysis is applied to spurious ambiguity and coordination. La Grammaire Catégorielle Combinatoire Applicative étend la Grammaire Catégorielle Combinatoire de Steedman par une association canonique entre les règles et des combinateurs de Curry d'une part et l'utilisation de métarègles qui contrôlent les opérations de changement de type d'autre part. Ce modèle est inclus dans le modèle général de la Grammaire Applicative et Cognitive (Desclés) avec trois niveaux de représentation : (i) le phénotype (expressions concaténées) ; (ii) le génotype (expressions applicatives) ; (iii) les représentations cognitives (sens des prédicats linguistiques). L'objectif de cet article est : (i) l'analyse automatique des expressions phénotypiques ; (ii) la construction des expressions applicatives sous jacentes aux énoncés analysés. L'analyse théorique est appliquée aux problèmes de la pseudo-ambiguité et de la coordination.

Following the tree method classification, we focus on the instability of the method and suggest a technique where the bootstrap is used. A detailed empirical study is illustrated in this paper. Après une présentation de la construction de prédicteurs par arbre de classification, nous nous intéressons à l'instabilité de cette méthode et proposons une méthodologie dans laquelle intervient le bootstrap. Une étude empirique détaillée illustre ce travail.

In this paper, we aim at showing how, in Geometric Data Analysis (Correspondence Analysis, Principal Component Analysis...) descriptive statistics utilized as aids to interpretation can be used as combinatorial inference procedures based on permutation tests interpreted in terms of proportion of samples which are more extreme than the data. These procedures directly extend statistical description. In the first part, we will present typicality and homogeneity tests. In the second part, we will apply them to the principal variables provided by Multiple Correspondence Analysis, taking as the population the set of individuals. Dans cet article, on se propose de montrer comment, en analyse géométrique des données (analyse des correspondances, analyse en composantes principales...) les statistiques descriptives utilisées comme aides à l'interprétation peuvent faire l'objet de procédures d'inférence combinatoire reposant sur des tests de permutation interprétés en termes de proportions d'échantillons plus extrêmes que les données, et qui prolongent directement la description statistique. Dans la première partie, on présente les tests de typicalité et d'homogénéité ; dans la deuxième partie, on les applique aux variables principales de l'analyse des correspondances multiples, en prenant pour population l'ensemble des individus.

In this paper, we propose an original and unifying framework in order to deal with abstraction of constraint networks. In this framework, classical and original forms of abstrac- tion can be taken into account. Classical forms correspond to (simple) value or/and variable clustering whereas original forms correspond to general clustering where "general" means that some clusters share some elements (values or variables). We show the declarative interest of general clustering by describing two representative problems, and its practical interest by solving these problems with a solver called AbsCon.

L'identification de structures propres a un probleme est souvent une etape clef pour la conception d'heuristiques de recherche comme pour la comprehension de la complexite du probleme. De nombreuses approches en Recherche Operationnelle emploient des strategies de relaxation ou de decomposition des lors que certaines structures idoines ont ete identifiees. L'etape suivante est la conception d'algorithmes de resolution qui puissent integrer a la volee, pendant la resolution, ce type d'information. Cet article propose d'utiliser un solveur de contraintes a base d'explications pour collecter une information pertinente sur les structures dynamiques et statiques inherentes au probleme. Identifying structure in a given combinatorial problem is often a key step for designing efficient search heuristics or for understanding the inherent complexity of the problem. Several Operations Research approaches apply decomposition or relaxation strategies upon such a structure identified within a given problem. The next step is to design algorithms that adaptively integrate that kind of information during search. We claim in this paper, inspired by previous work on impact-based search strategies for constraint programming, that using an explanation-based constraint solver may lead to collect invaluable information on the intimate dynamic and static structure of a problem instance.

Periodicity estimation of an audio signal, for applications such as pitch, multiple pitch or tempo estimation is often problematic due to the presence of multiple harmonics in the audio signal producing octave errors. While pitch models or rhythm models can be used, they remain often dedicated to a specific problem. In this paper, we propose a straightforward approach for periodicity estimation based on the combination of a spectral representation and a temporal representation. This method allows a better emphasis on the frequencies corresponding to the various pitches. We show the ability of this representation to adequately estimate pitch and visualize signals with multiple pitch content.

In this paper, we present the conversion of a specialized dictionary of bioindustries by means of Lexical Functions (Mel’čuk et al. 1984, 1988, 1992, 1999 ; Mel’čuk et al. 1995). The dictionary is based on semantic derivation as described in Explanatory and Combinatorial Lexicology, and explores compatibilities with lexico-syntactic descriptions as in Fillmore (1977, 2003) and Levin (1993) in order to assign circumstantial Lexical Functions. We first describe semantic relations such as hyperonymy, hyponymy, synonymy, antonymy and several cases of meronymy ; subsequently, we discuss verbs and predicative relations with reference to arguments and adjuncts. Finally, we explore the possibility of pursuing the research with an additional entry for definitions.

This paper addresses the problem of isolating light verb constructions (LVC) and classifying them according to semantic-syntactic parameters. LVC are firstly classified as a subtype of collocation. This step is important since it places the study of these constructions within a theoretical framework and defines the tests that are valid for their identification. Subsequently, on the basis of the reduction test (nominalization of the LVC and deletion of the verb), a boundary is traced between causative and non causative LVC on the one side and between base and extended LVC on the other side. Ultimately, a grid of semantic/aspectual criteria is proposed in order to distinguish different types of extended LVC. The application of this grid to Italian data allows a semantic classification of LVC based on a semantic decompositional analysis. This classification shows how it is possible to isolate different degrees in the function played by the verb in a LVC, according to its contribution to the semantic interpretation of the construction.

International audience; This paper describes an original approach for content-based video indexing and retrieval. We aim at providing a global interpretation of the dynamic content of video shots without any prior motion segmentation and without any use of dense optic flow fields. To this end, we exploit the spatio-temporal distribution, within a shot, of appropriate local motion-related measurements derived from the spatio-temporal derivatives of the intensity function. These distributions are then represented by causal Gibbs models. To be independent of camera movement, the motion-related measurements are computed in the image sequence generated by compensating the estimated dominant image motion in the original sequence. The statistical modeling framework considered makes the exact computation of the conditional likelihood of a video shot belonging to a given motion or more generally to an activity class feasible. This property allows us to develop a general statistical framework for video indexing and retrieval with query-by-example. We build a hierarchical structure of the processed video database according to motion content similarity. This results in a binary tree where each node is associated to an estimated causal Gibbs model. We consider a similarity measure inspired from Kullback-Leibler divergence. Then, retrieval with query-by-example is performed through this binary tree using the maximum a posteriori (MAP) criterion. We have obtained promising results on a set of various real image sequences

The aim of this paper is to build a categories typology from a square contingency table containing variables using the same nomenclature. Our assumption is that it exists categories groups according to attractions between categories and sequence of attractions among them. We use a modelling based on graphs and a decomposition method of connected (strong) component. L'objectif est de mettre en évidence, à partir d'un tableau de contingence croisant 2 variables utilisant la même nomenclature, une typologie des catégories de cette nomenclature. La recherche de cette typologie est basée sur l'hypothèse selon laquelle il existe des groupes de catégories en fonction des attractions entretenues entre elles ainsi que de leurs enchaînements. On s'appuie sur une modélisation sous forme de graphes et sur une méthode de décomposition des composantes (fortement) connexes.

In this paper, the discriminatory abilities of 16 similarity and dissimilarity indices are tested by means of a speaker-recognition experiment involving high-dimensional longterm speech spectra. The results give the ranking of the 16 indices on the basis of their discriminatory abilities