Multimedia documents such as slide presentations and posters are designed to be interactive and easy to modify. Yet, they are often distributed in a static raster format, which limits editing and customization. Restoring their editability requires converting these raster images back into structured vector formats. However, existing geometric raster vectorization methods, which rely on low-level primitives like curves and polygons, fall short at this task. Specifically, when applied to complex documents like slides, they fail to preserve the high-level structure, resulting in a flat collection of shapes where the semantic distinction between image and text elements is lost. To overcome this limitation, we address the problem of semantic document derendering by introducing SliDer, a novel framework that uses Vision-Language Models (VLMs) to derender slide images as compact and editable Scalable Vector Graphic (SVG) representations. SliDer detects and extracts the attributes from individual image and text elements in a raster input and organizes them into a coherent SVG format. Crucially, the model iteratively refines its predictions during inference in a process analogous to human design, generating SVG code that more faithfully reconstructs the original raster upon rendering. Furthermore, we introduce Slide2SVG, a novel dataset comprising raster-SVG pairs of slide documents curated from real-world scientific presentations, to facilitate future research in this domain. Our results demonstrate that SliDer achieves a reconstruction LPIPS of 0.069, and is favored by human evaluators in 82.9% of cases compared to the strongest zero-shot VLM baseline.

Label noise is a pervasive problem in deep learning that often compromises the generalization performance of trained models. Recently, leveraging privileged information (PI) – information available only during training but not at test time – has emerged as an effective approach to mitigate this issue. Yet, existing PI-based methods have failed to consistently outperform their no-PI counterparts in terms of preventing overfitting to label noise. To address this deficiency, we introduce Pi-DUAL, an architecture designed to harness PI to distinguish clean from wrong labels. Pi-DUAL decomposes the output logits into a prediction term, based on conventional input features, and a noise-fitting term influenced solely by PI. A gating mechanism steered by PI adaptively shifts focus between these terms, allowing the model to implicitly separate the learning paths of clean and wrong labels. Empirically, Pi-DUAL achieves significant performance improvements on key PI benchmarks (e.g., +6.8% on ImageNet-PI), establishing a new state-of-the-art test set accuracy. Additionally, Pi-DUAL is a potent method for identifying noisy samples post-training, outperforming other strong methods at this task. Overall, Pi-DUAL is a simple, scalable and practical approach for mitigating the effects of label noise in a variety of real-world scenarios with PI.

Leveraging privileged information (PI), or features available during training but not at test time, has recently been shown to be an effective method for addressing label noise. However, the reasons for its effectiveness are not well understood. In this study, we investigate the role played by different properties of the PI in explaining away label noise. Through experiments on multiple datasets with real PI (CIFAR-N/H) and a new large-scale benchmark ImageNet-PI, we find that PI is most helpful when it allows networks to easily distinguish clean from noisy data, while enabling a learning shortcut to memorize the noisy examples. Interestingly, when PI becomes too predictive of the target label, PI methods often perform worse than their no-PI baselines. Based on these findings, we propose several enhancements to the state-of-the-art PI methods and demonstrate the potential of PI as a means of tackling label noise. Finally, we show how we can easily combine the resulting PI approaches with existing no-PI techniques designed to deal with label noise.

We introduce Three Towers (3T), a flexible method to improve the contrastive learning of vision-language models by incorporating pretrained image classifiers. While contrastive models are usually trained from scratch, LiT (Zhai et al., 2022) has recently shown performance gains from using pretrained classifier embeddings. However, LiT directly replaces the image tower with the frozen embeddings, excluding any potential benefits from training the image tower contrastively. With 3T, we propose a more flexible strategy that allows the image tower to benefit from both pretrained embeddings and contrastive training. To achieve this, we introduce a third tower that contains the frozen pretrained embeddings, and we encourage alignment between this third tower and the main image-text towers. Empirically, 3T consistently improves over LiT and the CLIP-style from-scratch baseline for retrieval tasks. For classification, 3T reliably improves over the from-scratch baseline, and while it underperforms relative to LiT for JFT-pretrained models, it outperforms LiT for ImageNet-21k and Places365 pretraining.

Supervised learning datasets often have privileged information, in the form of features which are available at training time but are not available at test time e.g. the ID of the annotator that provided the label. We argue that privileged information is useful for explaining away label noise, thereby reducing the harmful impact of noisy labels. We develop a simple and efficient method for supervised learning with neural networks: it transfers via weight sharing the knowledge learned with privileged information and approximately marginalizes over privileged information at test time. Our method, TRAM (TRansfer and Marginalize), has minimal training time overhead and has the same test-time cost as not using privileged information. TRAM performs strongly on CIFAR-10H, ImageNet and Civil Comments benchmarks.

Large scale image classification datasets often contain noisy labels. We take a principled probabilistic approach to modelling input-dependent, also known as heteroscedastic, label noise in these datasets. We place a multivariate Nor-mal distributed latent variable on the final hidden layer of a neural network classifier. The covariance matrix of this latent variable, models the aleatoric uncertainty due to label noise. We demonstrate that the learned covariance structure captures known sources of label noise between semantically similar and co-occurring classes. Compared to standard neural network training and other baselines, we show significantly improved accuracy on Imagenet ILSVRC 2012 79.3% (+ 2.6%), Imagenet-21k 47.0% (+ 1.1%) and JFT 64.7% (+ 1.6%). We set a new state-of-the-art result on WebVision 1.0 with 76.6% top-1 accuracy. These datasets range from over 1M to over 300M training examples and from 1k classes to more than 21k classes. Our method is simple to use, and we provide an implementation that is a drop-in replacement for the final fully-connected layer in a deep classifier.

We consider the classical camera pose estimation problem that arises in many computer vision applications, in which we are given n 2D-3D correspondences between points in the scene and points in the camera image (some of which are incorrect associations), and where we aim to determine the camera pose (the position and orientation of the camera in the scene) from this data. We demonstrate that this posing problem can be reduced to the problem of computing ε-approximate incidences between two-dimensional surfaces (derived from the input correspondences) and points (on a grid) in a four-dimensional pose space. Similar reductions can be applied to other camera pose problems, as well as to similar problems in related application areas. We describe and analyze three techniques for solving the resulting ε-approximate incidences problem in the context of our camera posing application. The first is a straightforward assignment of surfaces to the cells of a grid (of side-length ε) that they intersect. The second is a variant of a primal-dual technique, recently introduced by a subset of the authors [2] for different (and simpler) applications. The third is a non-trivial generalization of a data structure Fonseca and Mount [3], originally designed for the case of hyperplanes. We present and analyze this technique in full generality, and then apply it to the camera posing problem at hand. We compare our methods experimentally on real and synthetic data. Our experiments show that for the typical values of n and ε, the primal-dual method is the fastest, also in practice.

We propose two solutions for both nearest neighbors and range search problems. For the nearest neighbors problem, we propose a c-approximate solution for the restricted version of the decision problem with bounded radius which is then reduced to the nearest neighbors by a known reduction. For range searching we propose a scheme that learns the parameters in a learning stage adopting them to the case of a set of points with low intrinsic dimension that are embedded in high dimensional space (common scenario for image point descriptors). We compare our algorithms to the best known methods for these problems, i.e. LSH, ANN and FLANN. We show analytically and experimentally that we can do better for moderate approximation factor. Our algorithms are trivial to parallelize. In the experiments conducted, running on couple of million images, our algorithms show meaningful speed-ups when compared with the above mentioned methods.

We consider the problem of distributed average consensus in a sensor network where sensors exchange quantized information with their neighbors. In particular, we exploit the increasing correlation between the exchanged values throughout the iterations of the consensus algorithm in order to design a novel quantization scheme, particularly efficient at low bit rates. We implement a low complexity, uniform quantizer in each sensor, where refined quantization is achieved by progressively reducing the quantization intervals with the convergence of the consensus algorithm. We propose a recurrence relation for computing the quantization parameters that depend on the network topology and the communication rate. Finally, simulation results demonstrate the effectiveness of the progressive quantization scheme that leads to the consensus solution even at low communication rate.

This paper proposes a novel approach to optimally solve volumetric registration problems. The proposed framework exploits parametric dictionaries for sparse volumetric representations, ℓ1dissimilarities and DC (Difference of Convex functions) decomposition. The SAD (sum of absolute differences) criterion is applied to the sparse representation of the reference volume and a DC decomposition of this criterion with respect to the transformation parameters is derived. This permits to employ a cutting plane algorithm for determining the optimal relative transformation parameters of the query volume. It further provides a guarantee for the global optimality of the obtained solution, which–to the best of our knowledge–is not offered by any other existing approach. A numerical validation demonstrates the effectiveness and the large potential of the proposed method.

This paper addresses the problem of image alignment based on random measurements. Image alignment consists of estimating the relative transformation between a query image and a reference image. We consider the specific problem where the query image is provided in compressed form in terms of linear measurements captured by a vision sensor. We cast the alignment problem as a manifold distance minimization problem in the linear subspace defined by the measurements. The transformation manifold that represents synthesis of shift, rotation, and isotropic scaling of the reference image can be given in closed form when the reference pattern is sparsely represented over a parametric dictionary. We show that the objective function can then be decomposed as the difference of two convex functions (DC) in the particular case where the dictionary is built on Gaussian functions. Thus, the optimization problem becomes a DC program, which in turn can be solved globally by a cutting plane method. The quality of the solution is typically affected by the number of random measurements and the condition number of the manifold that describes the transformations of the reference image. We show that the curvature, which is closely related to the condition number, remains bounded in our image alignment problem, which means that the relative transformation between two images can be determined optimally in a reduced subspace.

We consider the problem of distributed classification of multiple observations of the same object that are collected in an ad-hoc network of vision sensors. Assuming that each sensor captures a different observation of the same object, the problem is to classify this object by distributed processing from the sensors. We present a graph-based problem formulation whose objective function captures the smoothness of candidate labels on the data manifold. We design a distributed average consensus algorithm for estimating the unknown object class by computing the value of the above smoothness objective function for different class hypotheses. It initially estimates the objective function locally, based on the observation of each sensor. All the observations are then progressively taken into account in the estimation of the objective function, along the iterations of the distributed consensus algorithm. We illustrate the performance of the distributed classification algorithm by simulation of multi-view face recognition in an ad-hoc network of vision sensors. When the training set is sufficiently large, the simulation results show that the consensus classification decision is equivalent to the decision of a centralized system that would have access to all observations.

We consider the problem of classification of multiple observations of the same object, possibly under different transformations. We view this problem as a special case of semi-supervised learning where all unlabelled examples belong to the same unknown class. We propose a low complexity solution that is able to exploit the properties of the data manifold with a graph-based algorithm. It results into a discrete optimization problem, which can be solved by an efficient algorithm. We demonstrate its performance in video-based face recognition applications, where it outperforms state-of-the-art solutions that fall short of exploiting the manifold structure of the face image data sets.

Transformation invariance is an important property in pattern recognition, where different observations of the same object typically receive the same label. This paper focuses on a transformation-invariant distance measure that represents the minimum distance between the transformation manifolds spanned by patterns of interest. Since these manifolds are typically nonlinear, the computation of the manifold distance (MD) becomes a nonconvex optimization problem. We propose representing a pattern of interest as a linear combination of a few geometric functions extracted from a structured and redundant basis. Transforming the pattern results in the transformation of its constituent parts. We show that, when the transformation is restricted to a synthesis of translations, rotations, and isotropic scalings, such a pattern representation results in a closed-form expression of the manifold equation with respect to the transformation parameters. The MD computation can then be formulated as a minimization problem whose objective function is expressed as the difference of convex functions (DC). This interesting property permits optimally solving the optimization problem with DC programming solvers that are globally convergent. We present experimental evidence which shows that our method is able to find the globally optimal solution, outperforming existing methods that yield suboptimal solutions.

We address the problem of keyword spotting in continuous speech streams when training and testing conditions can be different. We propose a keyword spotting algorithm based on sparse representation of speech signals in a time-frequency feature space. The training speech elements are jointly represented in a common subspace built on simple basis functions. The subspace is trained in order to capture the common time-frequency structures from different occurrences of the keywords to be spotted. The keyword spotting algorithm then employs a sliding window mechanism on speech streams. It computes the contribution of successive speech segments in the subspace of interest and evaluates the similarity with the training data. Experimental results on the TIMIT database show the effectiveness and the noise resilience of the low complexity spotting algorithm.

We consider the problem of classification when multiple observations of a pattern are available, possibly under different transformations. We view this problem as a special case of semi-supervised learning where all the unlabelled samples belong to the same unknown class. We build on graph-based methods for semi-supervised learning and we optimize the graph construction in order to exploit the special structure of the problem. In particular, we assume that the optimal adjacency matrix is a linear combination of all possible class-conditional ideal adjacency matrices. We formulate the construction of the optimal adjacency matrix as a linear program (LP) on the weights of the linear combination. We provide experimental results that show the effectiveness and the validity of the proposed methodology.

This paper addresses the problem of 3D face recognition using spherical sparse representations. We first propose a fully automated registration process that permits to align the 3D face point clouds. These point clouds are then represented as signals on the 2D sphere, in order to take benefit of the geometry information. Simultaneous sparse approximations implement a dimensionality reduction process by subspace projection. Each face is typically represented by a few spherical basis functions that are able to capture the salient facial characteristics. The dimensionality reduction step preserves the discriminant facial information and eventually permits an effective matching in the reduced space, where it can further be combined with LDA for improved recognition performance. We evaluate the 3D face recognition algorithm on the FRGC v.1.0 data set, where it outperforms classical state-of-the-art solutions based on PCA or LDA on depth face images.

In the past few years, the problem of distributed consensus has received a lot of attention, particularly in the framework of ad hoc sensor networks. Most methods proposed in the literature attack this problem by distributed linear iterative algorithms, with asymptotic convergence of the consensus solution. It is known that the rate of convergence depends on the second largest eigenvalue of the weight matrix. In this paper, we propose the use of polynomial filtering in order to accelerate the convergence rate. The main idea of the proposed methodology is to apply a polynomial filter that will shape the spectrum of the weight matrix by minimizing its second largest eigenvalue and therefore increase the convergence rate. We formulate the computation of the optimal polynomial as a semi-definite program (SDP) that can be efficiently and globally solved. We provide simulation results that demonstrate the validity and effectiveness of the proposed scheme in both fixed and dynamic network topologies.

This paper addresses the problem of representing multimedia information under a compressed form that permits efficient classification. The semantic coding problem starts from a subspace method where dimensionality reduction is formulated as a matrix factorization problem. Data samples are jointly represented in a common subspace extracted from a redundant dictionary of basis functions. We first build on greedy pursuit algorithms for simultaneous sparse approximations to solve the dimensionality reduction problem. The method is extended into a supervised algorithm, which further encourages the class separability in the extraction of the most relevant features. The resulting supervised dimensionality reduction scheme provides an interesting tradeoff between approximation (or compression) and discriminant feature extraction (or classification). The algorithm provides a compressed signal representation that can directly be used for multimedia data mining. The application of the proposed algorithm to image recognition problems further demonstrates classification performances that are competitive with state-of-the-art solutions in handwritten digit or face recognition. Semantic coding certainly represents an interesting solution to the challenging problem of processing huge volumes of multidimensional data in modern multimedia systems, where compressed data have to be processed and analyzed with limited computational complexity.

In this paper, we propose the use of (adaptive) nonlinear approximation for dimensionality reduction. In particular, we propose a dimensionality reduction method for learning a parts based representation of signals using redundant dictionaries. A redundant dictionary is an overcomplete set of basis vectors that spans the signal space. The signals are jointly represented in a common subspace extracted from the redundant dictionary, using greedy pursuit algorithms for simultaneous sparse approximation. The design of the dictionary is flexible and enables the direct control on the shape and properties of the basis functions. Moreover, it allows to incorporate a priori and application-driven knowledge into the basis vectors, during the learning process. We apply our dimensionality reduction method to images and compare it with principal component analysis (PCA) and non-negative matrix factorization (NMF) and its variants, in the context of handwritten digit image recognition and face recognition. The experimental results suggest that the proposed dimensionality reduction algorithm is competitive to PCA and NMF and that it results into meaningful features with high discriminant value.

In this paper we discuss the problem of alignment of patterns under arbitrary rotation. When a generic image pattern is geometrically transformed, it typically spans a (possibly nonlinear) manifold in a high dimensional space. When the pattern of interest is given by a sparse approximation over a structured dictionary of geometric atoms, we show that the rotation manifold can be expressed analytically as a function of the transformation parameters. At the same time, its high order derivatives are also given in a closed form when the pattern is represented as a sparse linear combination of a few differentiable basis functions. In this framework, the alignment problem is formulated as the minimization of the distance between the reference pattern and the manifold, which boils down to a nonlinear least squares optimization problem. We propose to solve this problem by a Newton-type method, whose solution is facilitated by the analytical expressions of the manifold derivatives. We further derive a global optimization heuristic algorithm based on Newton, and provide sufficient conditions for computing the global minimizer. Experimental results demonstrate the effectiveness of the proposed methodology for image alignment and rotation invariant pattern recognition.

This paper considers the problem of dimensionality reduction by orthogonal projection techniques. The main feature of the proposed techniques is that they attempt to preserve both the intrinsic neighborhood geometry of the data samples and the global geometry. In particular we propose a method, named Orthogonal Neighborhood Preserving Projections, which works by first building an "affinity" graph for the data, in a way that is similar to the method of Locally Linear Embedding (LLE). However, in contrast with the standard LLE where the mapping between the input and the reduced spaces is implicit, ONPP employs an explicit linear mapping between the two. As a result, handling new data samples becomes straightforward, as this amounts to a simple linear transformation. We show how to define kernel variants of ONPP, as well as how to apply the method in a supervised setting. Numerical experiments are reported to illustrate the performance of ONPP and to compare it with a few competing methods.

In the past few years, the problem of distributed consensus has received a lot of attention, particularly in the framework of ad hoc sensor networks. Most methods proposed in the literature attack this problem by distributed linear iterative algorithms, with asymptotic convergence of the consensus solution. In this letter, we propose the use of extrapolation methods in order to accelerate distributed linear iterations. The extrapolation methods are guaranteed to converge in a finite number of steps, upper bounded by the number of sensors. In particular, we show that the Scalar Epsilon Algorithm (SEA) can accelerate vector sequences produced by distributed linear iterations, with no communication overhead and without knowledge of the full network topology. We provide simulation results that demonstrate the validity and effectiveness of the proposed scheme.

This paper presents a distributed algorithm for the detection of patterns or their transformed versions, in noisy images. The proposed method projects the observed signal onto a redundant and structured dictionary of functions, which are distributed among general purpose vision sensors. Each of the sensors then approximates the projections on its own part of the dictionary, and transmits that short information to a central fusion center. The pattern detection problem is then cast to a parameter estimation problem, where the parameters of the geometric transformation of the pattern of interest are sought, instead of the pattern itself. The parameters of the transformation are estimated by introducing a score function over the parameter space. Such an approach allows the fusion center to directly work in the space of features computed by the sensors, without need for signal reconstruction. It advantageously provides a generic approach, where the processing of the image is directly driven by the detection task. Experimental results indicate the effectiveness of the proposed method and its resiliency to noise in the observation.

This paper proposes an algorithm for distributed classification, based on a SVM scheme. The contribution of each support vector is approximated by low complexity distributed thresholding over sub-dictionaries, whose union forms a redundant dictionary of atoms that spans the space of the observed signal. Redundant dictionaries allow for sparse representation of the observed signal, hence a good approximation of the support vector contributions, which is moreover robust to noise. The algorithm is applied to distributed image classification, in the context of handwritten digit recognition in a sensor network. The experimental results indicate that the proposed method is capable of achieving the same classification performance as the standard (non distributed) SVM, with an increased resiliency to noise

Feature extraction based on different types of signal filters has received a lot of attention in the context of face recognition. It generally results into extremely high dimensional feature vectors, and sampling of the coefficients is required to reduce their dimensionality. Unfortunately, uniform sampling that is commonly used to that aim, does not consider the specificities of the recognition task in selecting the most relevant features. In this paper, we propose to formulate the sampling problem as a supervised feature selection problem where features are carefully selected according to a well defined discrimination criterion. The sampling process becomes specific to the classification task, and further facilitates the face recognition operations. We propose to build features on random filters, and Gabor wavelets, since they present interesting characteristics in terms of discrimination, due to their high frequency components. Experimental results show that the proposed feature selection method outperforms uniform sampling, and that random filters are very competitive with the common Gabor wavelet filters for face recognition tasks

Orthogonal neighborhood preserving projections (ONPP) is a linear dimensionality reduction technique which attempts to preserve both the intrinsic neighborhood geometry of the data samples and the global geometry. The proposed technique constructs a weighted data graph where the weights are constructed in a data-driven fashion, similarly to locally linear embedding (LLE). A major difference with the standard LLE where the mapping between the input and the reduced spaces is implicit, is that ONPP employs an explicit linear mapping between the two. As a result, and in contrast with LLE, handling new data samples becomes straightforward, as this amounts to a simple linear transformation. ONPP shares some of the properties of locality preserving projections (LPP). Both ONPP and LPP rely on a k-nearest neighbor graph in order to capture the data topology. However, our algorithm inherits the characteristics of LLE in preserving the structure of local neighborhoods, while LPP aims at preserving only locality without specifically aiming at preserving the geometric structure. This feature makes ONPP an effective method for data visualization. We provide ample experimental evidence to demonstrate the advantageous characteristics of ONPP, using well known synthetic test cases as well as real life data from computational biology and computer vision.

This paper presents a method named "orthogonal projection reduction by affinity", or OPRA-faces, for face recognition. As its name indicates, the method consists of an (explicit) orthogonal mapping from the data space to the reduced space. In addition, the method attempts to preserve the local geometry, i.e., the affinity of the points in a geometric representation of the data. The method starts by computing an affinity mapping W, of the data, which optimally expresses each point as a convex combination of a few nearest neighbors. This mapping can be viewed as an optimal representation of the intrinsic neighborhood geometries and is computed in a manner that is identical with the method of locally linear embedding (LLE). Next, and in contrast with LLE, the proposed scheme computes an explicit linear mapping between the high dimensional samples and their corresponding images in the reduced space, which is designed to preserve this affinity representation W. OPRA-faces shares some properties with Laplacianfaces, a recently proposed technique for face recognition, which computes the linear approximation of the Laplace-Beltrami operator on the image manifold. Laplacianfaces aims at preserving locality but does not explicitly consider the intrinsic geometries of the neighborhoods as does OPRA. As a result of the preservation of the affinity mapping W, OPRA will tend to produce a linear subspace which captures the essential geometric characteristics of the dataset. This feature, which appears to be crucial in representing images, makes the method very effective as a tool for face recognition. OPRA is tested on standard face databases and its effectiveness is compared with that of Laplacianfaces, eigenfaces and Fisherfaces. The experimental results indicate that the proposed technique produces results that are sharply superior to the other methods, at a comparable or lower cost.

Keywords: LTS4 Reference EPFL-CONF-87295 Record created on 2006-06-14, modified on 2016-08-08

Latent Semantic Indexing (LSI) is a well established and effective framework for conceptual information retrieval. In traditional implementations of LSI the semantic structure of the collection is projected into the k-dimensional space derived from a rank-k approximation of the original term-by-document matrix. This paper discusses a new way to implement the LSI methodology, based on polynomial filtering. The new framework does not rely on any matrix decomposition and therefore its computational cost and storage requirements are low relative to traditional implementations of LSI. Additionally, it can be used as an effective information filtering technique when updating LSI models based on user feedback.

Given a matrix A, the computation of its pseudospectrum (A) is a far more expensive task than the computation of characteristics such as the condition number and the matrix spectrum. As research of the last 15 years has shown, however, the matrix pseudospectrum provides valuable information that is not included in other indicators. So, ask how to compute it eciently and build a tool that would facilitate engineers and scientists to make such analyses? In this paper we focus on parallel algorithms for computing pseudospectra. The most widely used algorithm for computing pseudospectra is embarassingly parallel; nevertheless, it is extremely costly and one cannot hope to achieve absolute high performance with it. We describe algorithms that have drastically improved performance while maintaining a high degree of large grain parallelism. We evaluate the eectiveness of these methods in the context of a MATLAB-based environment for parallel programming using MPI on small, o-the-shelf parallel systems. Keywords Pseudospectra, MPI, MATLAB, NOWs 1.