Search

We illustrate the Efficient Forward Filtering Backward Smoothing (EFFBS) algorithm proposed by Khreich et al. (2010) for estimation of hidden Markov models. The algorithm is aimed at reducing the amount of memory required by the Baum-Welch recursions, while having the same complexity in terms of number of operations. In implementing the EFFBS algorithm we found a numerical problem that limits its applicability. We discuss this problem in detail, providing some possible explanations of the causes of the error, together with two illustrative examples.

The main contributions of this paper are: A new method for recognition of non-deformable severe occluded objects.Local shape descriptor from the wavelet coefficients of the tangent angle signature.Most likely object retrieval based on an ensemble of Hidden Markov Models.Two new area restrictions for consistency checking between hypotheses and occlusion. Shape classification has multiple applications. In real scenes, shapes may contain severe occlusions, hardening the identification of objects. In this paper, a method for object recognition under severe occlusion is proposed. Occlusion is dealt with separating shapes into parts through high curvature points, then tangent angle signature is found for each part and continuous wavelet transform is calculated for each signature. Next, the best matching object is calculated for each part using Pearsons correlation coefficient as similarity measure between wavelets of the part and of the most probable objects in the database. For each probable class, a hidden Markov model is created in an ensemble through training with the one-class approach. For hypotheses validation, two area restrictions are set to enhance recognition performance. Experiments were conducted with 1500 test shape instances with different scenarios of object occlusion. Results showed the method not only was capable of identifying highly occluded shapes (60%80% overlapping) but also present several advantages over previous methods.

This paper proposes a unified framework for Active Constrained Clustering.The proposed method relies on a multiple kernels learning setting.Utilization of constraints is considered by clustering method in this paper.Constraints are queried based on confidence about center and boundary of clusters. This paper examines the issues of constrained clustering and active selection of clustering constraints in a unified approach. A fuzzy clustering method specially crafted to deal with non-spherical clusters and explicit pairwise constraints is proposed in this paper as a core clustering method. An active method for constraints selection is embedded into the core clustering method for querying beneficial constraints during clustering. The proposed approach has two major advantages relative to traditional methods. First, it considers the dependency of constraints effectiveness on the clustering algorithm by unifying both clustering and constraints selection in a uniform, principled framework. Second, a constraints selection method is embedded into the core clustering method based on the fact that constraints will be more useful if they are selected according to the current state of clustering. Experiments conducted on synthetic and real-world datasets show the effectiveness of the proposed method.

We propose a graph-based mode-seeking method to fit multi-structural data.The proposed method combines mode-seeking with preference analysis.The proposed method exploits the global structure of graphs by random walks.Experiments show the proposed method is superior to some other fitting methods. In this paper, we propose a novel graph-based mode-seeking fitting method to fit and segment multiple-structure data. Mode-seeking is a simple and effective data analysis technique for clustering and filtering. However, conventional mode-seeking based fitting methods are very sensitive to the proportion of good/bad hypotheses, while most of sampling techniques may generate a large proportion of bad hypotheses. In this paper, we show that the proposed graph-based mode-seeking method has significant superiority for geometric model fitting. We intrinsically combine mode seeking with preference analysis. This enables mode seeking to be beneficial for reducing the influence of bad hypotheses since bad hypotheses usually have larger residual values than good ones. In addition, the proposed method exploits the global structure of graphs by random walks to alleviate the sensitivity to unbalanced data. Experimental results on both synthetic data and real images demonstrate that the proposed method outperforms several other competing fitting methods especially for complex data.

Multi-scale PCA framework is proposed for filtering the virus images.A multi-scale CLBP descriptor is developed to extract the features.Images are classified by the SVM with polynomial kernel and the MPMC features.Experiments show that the proposed method is better than the conventional methods. Virus image classification is an important issue in clinical virology, highly accurate algorithm of automatic virus image classification is very helpful. In this paper, instead of extracting virus feature from the original image, we propose a novel method that extracts the virus feature from the filtered images by multi-scale principal component analysis (PCA). Firstly, multi-scale PCA filters are learned from all original images in the data set. Secondly, the original images are convolved with the learned filters. Therefore, the filtered images can capture the principal texture information from different perspectives. Then, the completed local binary pattern (CLBP) descriptor is firstly utilized to depict the features of all filtered virus images. The multi-scale CLBP features extracted from filtered images by multi-scale PCA are combined as the feature MPMC (Multi-scale PCA and Multi-scale CLBP), which is proposed in this paper. Finally, support vector machine (SVM) with polynomial kernel is used for classification. Experiments show that the classification accuracy based on MPMC outperforms the previous methods in the literature for the same virus image data set.

An unsupervised procedure to local symmetry detection in natural images is proposed.Achieved via a Hough-style voting approach made at different scales and coordinate spaces.A final denoising scheme aims at removing noise and spurious local symmetries.Experiments have been conducted on the recent extension of the Berkeley Segmentation Dataset.The proposed method performs well compared to the state-of-the-art algorithms. Display Omitted In this paper, we propose a new unsupervised and simple approach to local symmetry detection of ribbon-like structure in natural images. The proposed model consists in quantifying the presence of a partial medial axis segment, existing between each pair of (preliminary detected) line segments delineating the boundary of two textured regions, by a set of heuristics related both to the geometrical structure of each pair of line segments and its ability to locally delimit a homogeneous texture region in the image. This semi-local approach is finally embedded in a two-step algorithm with an amplification step, via a Hough-style voting approach achieved at different scales and coordinate spaces which aims at determining the dominant local symmetries present in the image and a final denoising step, via an averaging procedure, which aims at removing noise and spurious local symmetries. The experiments, reported in this paper and conducted on the recent extension of the Berkeley Segmentation Dataset for the local symmetry detection task, demonstrate that the proposed symmetry detector performs well compared to the best existing state-of-the-art algorithms recently proposed in the literature.

Minimum Cost Subgraph Matching (MCSM) is an adaptation of Graph Edit Distance.The paper proposes a Binary Linear Program that solves the MCSM problem.The proposed formulation is very general and can tackle a large range of graphs.MCSM is more efficient and faster than a Substitution Only Tolerant Subgraph Matching (SOTSM). This paper presents a binary linear program for the Minimum Cost Subgraph Matching (MCSM) problem. MCSM is an extension of the subgraph isomorphism problem where the matching tolerates substitutions of attributes and modifications of the graph structure. The objective function proposed in the formulation can take into account rich attributes (e.g. vectors mixing nominal and numerical values) on both vertices and edges. Some experimental results obtained on an application-dependent dataset concerning the spotting of symbols on technical drawings show that the approach obtains better performance than a previous approach which is only substitution-tolerant.

The paper presents a novel texture descriptor based on Local Binary Patterns.We address the problem of rotation invariance and feature selections.The experiments are performed on standard datasets and the results are compared with the state-of-the-art.The source code to reproduce the results is made publicly available. In this paper, we present a novel rotation-invariant and computationally efficient texture descriptor called Dominant Rotated Local Binary Pattern (DRLBP). A rotation invariance is achieved by computing the descriptor with respect to a reference in a local neighborhood. A reference is fast to compute maintaining the computational simplicity of the Local Binary Patterns (LBP). The proposed approach not only retains the complete structural information extracted by LBP, but it also captures the complimentary information by utilizing the magnitude information, thereby achieving more discriminative power. For feature selection, we learn a dictionary of the most frequently occurring patterns from the training images, and discard redundant and non-informative features. To evaluate the performance we conduct experiments on three standard texture datasets: Outex12, Outex 10 and KTH-TIPS. The performance is compared with the state-of-the-art rotation invariant texture descriptors and results show that the proposed method is superior to other approaches.

This paper introduces a kernel version of the Subspace Pursuit algorithm.The proposed method, KSP, is a new iterative method for sparse regression.KSP outperforms and is less computationally intensive than related kernel methods. Recently, results from sparse approximation theory have been considered as a means to improve the generalization performance of kernel-based machine learning algorithms. In this paper, we present Kernel Subspace Pursuit (KSP), a new method for sparse non-linear regression. KSP is a low-complexity method that iteratively approximates target functions in the least-squares sense as a linear combination of a limited number of elements selected from a kernel-based dictionary. Unlike other kernel methods, by virtue of KSP's algorithmic design, the number of KSP iterations needed to reach the final solution does not depend on the number of basis functions used nor that of elements in the dictionary. We experimentally show that, in many scenarios involving learning synthetic and real data, KSP is less complex computationally and outperforms other kernel methods that solve the same problem, namely, Kernel Matching Pursuit and Kernel Basis Pursuit.

The paper proposes a novel Multi-objective Genetic Algorithm for Data Imputation, called MOGAImp.This is the first method that applies a multi-objective approach to data imputation.MOGAImp presents a good tradeoff between the evaluation measures studied.The results confirm the MOGAImp prevalence for utilization over conflicting evaluation measures.MOGAImp codification scheme makes possible to adapt it to different application domains. A large number of techniques for data analyses have been developed in recent years, however most of them do not deal satisfactorily with a ubiquitous problem in the area: the missing data. In order to mitigate the bias imposed by this problem, several treatment methods have been proposed, highlighting the data imputation methods, which can be viewed as an optimization problem where the goal is to reduce the bias caused by the absence of information. Although most imputation methods are restricted to one type of variable whether categorical or continuous. To fill these gaps, this paper presents the multi-objective genetic algorithm for data imputation called MOGAImp, based on the NSGA-II, which is suitable for mixed-attribute datasets and takes into account information from incomplete instances and the modeling task. A set of tests for evaluating the performance of the algorithm were applied using 30 datasets with induced missing values; five classifiers divided into three classes: rule induction learning, lazy learning and approximate models; and were compared with three techniques presented in the literature. The results obtained confirm the MOGAImp outperforms some well-established missing data treatment methods. Furthermore, the proposed method proved to be flexible since it is possible to adapt it to different application domains.

We propose an unsupervised spatio-temporal image filtering method based on mean-shift.We adapt the spatial and feature range domains to handle temporal evolution.A constraint is added on the sample's evolution to select temporal neighbors.Our method outperforms standard mean-shift by adequately considering time information.Effectiveness is demonstrated on both synthetic and real brain MRI time-series data. A new spatio-temporal filtering scheme based on the mean-shift procedure, which computes unsupervised spatio-temporal filtering for univariate feature evolution, is proposed in this paper. Our main contributions are on one hand the modification of the spatial/range domains to appropriately integrate the temporal feature into the mean-shift iterative form and on the other hand the addition of a trajectory constraint in the feature space with the use of the infinity norm. Therefore, only the samples living the same life in the feature space will converge. Major assets of the standard mean-shift framework such as convergence and bandwidth parameters adjustment are preserved. In this paper, we study the relative importance of the bandwidth parameters and the efficiency of the proposed method is assessed on synthetic data and compared to the standard mean-shift framework for spatio-temporal data filtering. The obtained results have allowed us to undertake a first study on real data, which has led to encouraging results in identifying spatio-temporal evolution of multiple sclerosis lesions appearing on T2-weighted MR images.

A computationally competitive Incremental Extreme Learning Machine based on QR factorization is proposed.The computational complexity of this approach is analyzed and found less than that of its rival algorithms.A certain condition (well-conditioned of hidden output matrix) has to be met to apply the incremental algorithms. In this paper, a computationally competitive incremental algorithm based on QR factorization is proposed, to automatically determine the number of hidden nodes in generalized single-hidden-layer feedforward networks (SLFNs). This approach, QR factorization based Incremental Extreme Learning Machine (QRI-ELM), is able to add random hidden nodes to SLFNs one by one. The computational complexity of this approach is analyzed in this paper as well. Simulation results show and verify that our new approach is fast and effective with good generalization and accuracy performance.

New global lower bound on the edit distance between graphs.An efficient preliminary filter for similarity search in graph databases.Almost-for-free improvement on the previous global lower bounds.The new bound is at least as tight as the previous global ones.Experiments show the effectiveness of the new bound. Graph similarity search is to retrieve data graphs that are similar to a given query graph. It has become an essential operation in many application areas. In this paper, we investigate the problem of graph similarity search with edit distance constraints. Existing solutions adopt the filter-and-verify strategy to speed up the search, where lower and upper bounds of graph edit distance are employed as pruning and validation rules in this process. The main problem with existing lower bounds is that they show different performance on different data graphs. An interesting group of lower bounds is the global counting ones. These bounds come almost for free and can be injected with any filtering methodology to work as preliminary filters. In this paper, we present an improvement upon these bounds without adding any computation overhead. We show that the new bound is tighter than the previous global ones except for few cases where they identically evaluate. Via experiments, we show how the new bound, when incorporated into previous lower bounding methods, increases the performance significantly.

Adaptation of the k-means algorithm is used by circle-centers.Incremental algorithm for searching for a globally optimal k-partition is proposed.A few known indexes for determining a number of clusters in partition are adopted.Hausdorff distance between two circles is adopted. The multiple circle detection problem has been considered in the paper on the basis of given data point set A ? R 2 . It is supposed that all data points from the set A come from k circles that should be reconstructed or detected. The problem has been solved by the application of center-based clustering of the set A , i.e. an optimal k-partition is searched for, whose clusters are determined by corresponding circle-centers. Thereby, the algebraic distance from a point to the circle is used. First, an adaptation of the well-known k-means algorithm is given in the paper. Also, the incremental algorithm for searching for an approximate globally optimal k-partition is proposed. The algorithm locates either a globally optimal k-partition or a locally optimal k-partition close to the global one. Since optimal partitions with 2, 3, ? clusters are determined successively in the algorithm, several well-known indexes for determining an appropriate number of clusters in a partition are adopted for this case. Thereby, the Hausdorff distance between two circles is used and adopted. The proposed method and algorithm are illustrated and tested on several numerical examples.

We propose an extracting algorithm for k nearest neighbors searching.Vector inner product instead of distance calculation for distance comparison.Extracting algorithm can integrate with any other algorithm as plug-in.Two prominent algorithms and seven models are employed to experiment.Open source of proposed algorithm using dynamic memory allocation. k Nearest neighbors (kNN) searching algorithm is widely used for finding k nearest neighbors for each point in a point cloud model for noise removal and surface curvature computation. When the number of points and their density in a point cloud model increase significantly, the efficiency of a kNN searching algorithm becomes critical to various applications, thus, a better kNN approach is needed. In order to improve the efficiency of a kNN searching algorithm, in this paper, a new strategy and the corresponding algorithm are developed for reducing the amount of target points in a given data set by extracting nearest neighbors before the search begins. The nearest neighbors of a reverse nearest neighborhood are proposed to use in extracting nearest points of a query point, avoiding repetitive Euclidean distance calculation in an extracting process for saving time and memories. For any point in the model, its initial nearest neighbors can be extracted from its reverse neighborhood using an inner product of two related vectors other than direct Euclidean distance calculations and comparisons. The initial neighbors can be its full or partial set of the all nearest neighbors. If it is a partial set, the rest can be obtained by using other fast searching algorithms, which can be integrated with the proposed approach. Experimental results show that integrating extracting algorithm proposed in this paper with other excellent algorithms provides a better performance by comparing to their performances alone.

Surface and curve skeletons are important shape descriptors with applications in shape matching, simplification, retrieval, and animation. In recent years, many surface and curve skeletonization methods for 3D shapes have been proposed. However, practical comparisons of such methods against each other and against given quality criteria are quite limited in the literature. In this paper, we compare 4 surface and 6 recent curve skeletonization methods that operate on voxel shapes. We first compare the selected methods from a global perspective, using the quality criteria established by a reference paper in the field. Next, we propose a detailed comparison that refines the gained insights by highlighting small-scale differences between skeletons obtained by different methods. Keywords: Medial axes; Surface and curve skeletons; Voxel shapes

In this paper we present a new quaternion-based encryption technique for color images. In the proposed encryption method, images are written as quaternions and are rotated in a three-dimensional space around another quaternion, which is an encryption key. The encryption process uses the cipher block chaining (CBC) mode. Further, this paper shows that our encryption algorithm enables digital fingerprinting as an additional feature. This feature follows from some artifacts which occur in the decrypted image. These artifacts can be maintained at such a low level that they remain imperceptible to the human eye and unique for each key. These artifacts are considered to be users' fingerprints and can be used to identify pirates in the event of illegal redistribution of multimedia data. Identification of pirates is performed in the form of non-blind detection. The purpose of this paper is to report a new approach to digital fingerprinting and to point out the method's existing flaws which need future research. A computer-based simulation was conducted to examine the potential of our quaternion encryption scheme for the implementation of digital fingerprinting.

Extreme Support Vector Machine (ESVM) is a nonlinear robust SVM algorithm based on regularized least squares optimization for binary-class classification. In this paper, a novel algorithm for regression tasks, Extreme Support Vector Regression (ESVR), is proposed based on ESVM. Moreover, kernel ESVR is suggested as well. Experiments show that, ESVR has a better generalization than some other traditional single hidden layer feedforward neural networks, such as Extreme Learning Machine (ELM), Support Vector Regression (SVR) and Least Squares-Support Vector Regression (LS-SVR). Furthermore, ESVR has much faster learning speed than SVR and LS-SVR. Stabilities and robustnesses of these algorithms are also studied in the paper, which shows that the ESVR is more robust and stable.

The bag of visual words model (BoW) and its variants have demonstrated their effectiveness for visual applications. The BoW model first extracts local features and generates the corresponding codebook where the elements of a codebook are viewed as visual words. However, the codebook is dataset dependent and has to be generated for each image dataset. Besides, when we only have a limited number of training images, the codebook generated correspondingly may not be able to encode images well. This requires a lot of computational time and weakens the generalization power of the BoW model. To solve these problems, in this paper, we propose to undo the dataset bias by linear codebook transformation in an unsupervised manner. To represent each point in the local feature space, we need a number of linearly independent basis vectors. We view the codebook as a linear transformation of these basis vectors. In this way, we can transform the pre-learned codebooks for a new dataset using the pseudo-inverse of the transformation matrix. However, this is an under-determined problem which may lead to many solutions. Besides, not all of the visual words are equally important for the new dataset. It would be more effective if we can make some selection and choose the discriminative visual words for transformation. Specifically, the sparsity constraints and the F-norm of the transformation matrix are used in this paper. We propose an alternative optimization algorithm to jointly search for the optimal linear transformation matrixes and the encoding parameters. The proposed method needs no labeled images from either the source dataset or the target dataset. Image classification experimental results on several image datasets show the effectiveness of the proposed method.

This paper presents focusing on an object of interest in thermal infrared (IR) imagery using the morphological gradient operator. Most existing focus metrics measure the degree of sharpness on the edge of an object in the field of view, often based on the local gradient operators of pixel brightness intensity. However, such focus measures may fail to find the optimal focusing distance to the object in thermal IR images, where strong edge components of an object do not exist. In particular, when the end goal of image acquisition is object recognition, focusing on an object must retain prominent features of the object for recognition. In this paper, the performances of various focus measures are evaluated in terms of sharpness as well as recognition accuracies for face recognition in thermal IR images. Experiment results show that the morphological gradient operator outperforms conventional gradient operators in terms of autofocusing resolution metric as well as face recognition accuracy.

The paper presents a novel unsupervised contextual spectral (CSE) framework for human action and video classification. Similar to textual words, the visual word (a mid-level semantic) representation of an image or video contains a combination of synonymous words which give rise to the ambiguity of the representation. To narrow the semantic gap between visual words (mid-level semantic representation) and high-level semantics, we propose a high level representation called approximate-semantic descriptor. The experimental results show that the proposed approach for visual words disambiguation could improve the subsequent classification performance. In the paper, the approximate-semantic descriptor learning is formulated as a spectral clustering problem, such that semantically associated visual words are placed closely in low-dimensional semantic space and then clustered into one approximate-semantic descriptor. Specifically, the high level representation of human action videos is learnt by capturing the inter-video context of mid-level semantics via a non-parametric correlation measure. Experiments on four standard datasets demonstrate that our approach can achieve significantly improved results with respect to the state of the art, particularly for unconstrained environments.

Segmenting multidimensional images, in particular hyperspectral images, is still an open subject. Two are the most important issues in this field. On one hand, most methods do not preserve the multidimensional character of the signals throughout the segmentation process. They usually perform an early projection of the hyperspectral information to a two dimensional representation with the consequent loss of the large amount of spectral information these images provide. On the other hand, there is usually very little and dubious ground truth available, making it very hard to train and tune appropriate segmentation and classification strategies. This paper describes an approach to the problem of segmenting and classifying regions in multidimensional images that performs a joint two-step process. The first step is based on the application of cellular automata (CA) and their emergent behavior over the hyperspectral cube in order to produce homogeneous regions. The second step employs a more traditional SVM in order to provide labels for these regions to classify them. The use of cellular automata for segmentation in hyperspectral images is not new, but most approaches to this problem involve hand designing the rules for the automata and, in general, average out the spectral information present. The main contribution of this paper is the study of the application of evolutionary methods to produce the CA rule sets that result in the best possible segmentation properties under different circumstances without resorting to any form of projection until the information is presented to the user. In addition, we show that the evolution process we propose to obtain the rules can be carried out over RGB images and then the resulting automata can be used to process multidimensional hyperspectral images successfully, thus avoiding the problem of lack of appropriately labeled ground truth images. The procedure has been tested over synthetic and real hyperspectral images and the results are very competitive.

Searching correlated pairs in a collection of items is essential for many problems in commercial, medical, and scientific domains. Recently, a lot of progress has been made to speed up the search for pairs that have a high Pearson correlation (@f-coefficient). However, @f-coefficient is not the only or the best correlation measure. In this paper, we aim at an alternative task: finding correlated pairs of any ''good'' correlation measure which satisfies the three widely-accepted correlation properties in Section 2.1. In this paper, we identify a 1-dimensional monotone property of the upper bound of any ''good'' correlation measure, and different 2-dimensional monotone properties for different types of correlation measures. We can either use the 2-dimensional search algorithm to retrieve correlated pairs above a certain threshold, or our new token-ring algorithm to find top-k correlated pairs to prune many pairs without computing their correlations. The experimental results show that our robust algorithm can efficiently search correlated pairs under different situations and is an order of magnitude faster than the brute-force method.

In this paper, we address the challenging task of simultaneous recognition of overlapping sound events from single channel audio. Conventional frame-based methods are not well suited to the problem, as each time frame contains a mixture of information from multiple sources. Missing feature masks are able to improve the recognition in such cases, but are limited by the accuracy of the mask, which is a non-trivial problem. In this paper, we propose an approach based on Local Spectrogram Features (LSFs) which represent local spectral information that is extracted from the two-dimensional region surrounding “keypoints” detected in the spectrogram. The keypoints are designed to locate the sparse, discriminative peaks in the spectrogram, such that we can model sound events through a set of representative LSF clusters and their occurrences in the spectrogram. To recognise overlapping sound events, we use a Generalised Hough Transform (GHT) voting system, which sums the information over many independent keypoints to produce onset hypotheses, that can detect any arbitrary combination of sound events in the spectrogram. Each hypothesis is then scored against the class distribution models to recognise the existence of the sound in the spectrogram. Experiments on a set of five overlapping sound events, in the presence of non-stationary background noise, demonstrate the potential of our approach.

The area under the receiver operating characteristic curve is a widely used measure of the performance of classification rules. This paper shows that when classifications are based solely on data describing individual objects to be classified, the area under the receiver operating characteristic curve is an incoherent measure of performance, in the sense that the measure itself depends on the classifier being measured. It significantly extends earlier work by showing that this incoherence is not a consequence of a cost-based interpretation of misclassifications, but is a fundamental property of the area under the curve itself. The paper also shows that if additional information, such as the class assignments of other objects, is taken into account when making a classification, then the area under the curve is a coherent measure, although in those circumstances it makes an assumption which is seldom if ever appropriate.

Kernel k-means clustering method has been proved to be effective in identifying non-isotropic and linearly inseparable clusters in the input space. However, this method is not a suitable one for large datasets because of its quadratic time complexity with respect to the size of the dataset. This paper presents a simple prototype based hybrid approach to speed-up the kernel k-means clustering method for large datasets. The proposed method works in two stages. First, the dataset is partitioned into a number of small grouplets by using the leaders clustering method which takes the size of each grouplet, called the threshold t, as an input parameter. The conventional leaders clustering method is modified such that these grouplets are formed in the kernel induced feature space, but each grouplet is represented by a pattern (called its leader) in the input space. The dataset is re-indexed according to these grouplets. Later, the kernel k-means clustering method is applied over the set of leaders to derive a partition of the leaders set. Finally, each leader is replaced by its group to get a partition of the entire dataset. The time complexity as well as space complexity of the proposed method is O(n+p^2), where p is the number of leaders. The overall running time and the quality of the clustering result depends on the threshold t and the order in which the dataset is scanned. This paper presents a study on how the input parameter t affects the overall running time and the clustering quality obtained by the proposed method. Further, both theoretically and experimentally it has been shown how the order of scanning of the dataset affects the clustering result. The proposed method is also compared with the other recent methods that are proposed to speed-up the kernel k-means clustering method. Experimental study with several real world as well as synthetic datasets shows that, for an appropriate value of t, the proposed method can significantly reduce the computation time but with a small loss in clustering quality, particularly for large datasets.

A set of objectives are partitioned into groups by means of fuzzy set theory-based clustering approaches, which ignores the hesitancy introduced by the relationship degree between two entities. The interval-based membership generalization in vague sets (VSs) is more expressive than fuzzy sets (FSs) in describing and dealing with data vagueness. In this paper, we introduce a fuzzy clustering algorithm in the context of VSs theory and fuzzy C-means clustering (FCM), i.e., Vague C-means clustering algorithm (VCM). First, the objective function of VCM and the definition of interval-based membership function are given. Then, the QPSO (quantum-behaved particle swarm optimization)-based VCM calculation is proposed. Contrastive experimental results show that the proposed scheme is more effective and more efficient than FCM and three varieties of FCM, that is, FCM-HDGA, GK-FCM and KL-FCM. Besides, the paper also discusses the influence of the VCM parameters on the clustering results.

Binary descriptors allow faster similarity computation than real-valued ones while requiring much less storage. As a result, many algorithms have recently been proposed to binarize floating-point descriptors so that they can be searched for quickly. Unfortunately, even if the similarity between vectors can be computed fast, exhaustive linear search remains impractical for truly large databases and approximate nearest neighbor (ANN) search is still required. It is therefore surprising that relatively little attention has been paid to the efficiency of ANN algorithms on binary vectors and this is the focus of this paper. We first show that binary-space Voronoi diagrams have thick boundaries, meaning that there are many points that lie at the same distance from two random points. This violates the implicit assumption made by most ANN algorithms that points can be neatly assigned to clusters centered around a set of cluster centers. As a result, state-of-the-art algorithms that can operate on binary vectors exhibit much lower performance than those that work with floating point ones. The above analysis is the first contribution of the paper. The second one is two effective ways to overcome this limitation, by appropriately randomizing either a tree-based algorithm or hashing-based one. In both cases, we show that we obtain precision/recall curves that are similar to those than can be obtained using floating point number calculation, but at much reduced computational cost.

Person re-identification is a recently introduced computer vision task that consists of recognising an individual who was previously observed over a video-surveillance camera network. Among the open problems, in this paper we focus on computational complexity. Despite its practical relevance, especially in real-time applications, this issue has been overlooked in the literature so far. In this paper, we address it by exploiting a framework we proposed in a previous work. It allows us to turn any person re-identification method, that uses multiple components and a body part subdivision model, into a dissimilarity-based one. Each individual is represented as a vector of dissimilarity values to a set of visual prototypes, that are drawn from the original non-dissimilarity representation. Experiments on two benchmark datasets provide evidence that a dissimilarity representation provides very fast re-identification methods. We also show that, even if the re-identification accuracy can be lower (especially when the number of candidates is low), the trade-off between processing time and accuracy can nevertheless be advantageous, in real-time application scenarios involving a human operator.

In machine learning and statistics, kernel density estimators are rarely used on multivariate data due to the difficulty of finding an appropriate kernel bandwidth to overcome overfitting. However, the recent advances on information-theoretic learning have revived the interest on these models. With this motivation, in this paper we revisit the classical statistical problem of data-driven bandwidth selection by cross-validation maximum likelihood for Gaussian kernels. We find a solution to the optimization problem under both the spherical and the general case where a full covariance matrix is considered for the kernel. The fixed-point algorithms proposed in this paper obtain the maximum likelihood bandwidth in few iterations, without performing an exhaustive bandwidth search, which is unfeasible in the multivariate case. The convergence of the methods proposed is proved. A set of classification experiments are performed to prove the usefulness of the obtained models in pattern recognition.

The purpose of this paper is to elucidate the problem of testing for the absence of correlation between the trajectories of two stochastic processes. It is assumed that the process is homogeneous on a pre-specified partition of the index set. The hypothesis testing methodology developed in this article consists in estimating codispersion coefficients on each subset of the partition, and in testing for the simultaneous nullity of the coefficients. To this aim, the Mahalanobis distance between the observed and theoretical codispersion vectors is used to define a test statistic, which converges to a chi-square distribution under the null hypothesis. Three examples in the context of signal processing and spatial models are discussed to point out the advantages and limitations of our proposal. Simulation studies are carried out to explore both the distribution of the test statistic under the null hypothesis and its power function. The method introduced in this paper has potential applications in time series where it is of interest to measure the comovement of two temporal sequences. The proposed test is illustrated with a real data set. Two signals are compared in terms of comovement to validate two confocal sensors in the context of biotechnology. The analysis carried out using this technique is more appropriate than previous validation tests where the mean values were compared via t test and Wilcoxon signed rank test ignoring the correlation within and across the series.

Highlights? Linear time algorithm to cohomology generators computations for orientable open and closed 2d manifolds is presented. ? Extension to optimal cohomology generators is given. ? Some extension to non-manifold cases are provided. In this paper a fast algorithm to compute cohomology group generators of cellular decomposition of any orientable open or closed 2-manifold is described. The presented algorithm is a dual version of algorithm to compute homology generators presented by David Eppstein in "Dynamic generators of topologically embedded graphs" and developed by Jeff Erickson and Kim Whittlesey in "Greedy optimal homotopy and homology generators". Some parts of the paper bases on ideas presented in "Optimal discrete Morse functions for 2-manifolds" by Thomas Lewiner, Helio Lopes and Geovan Tavares. Extension of the algorithm to some non-manifold cases is provided.

Highlights? We consider retractions defined by digitally continuous multivalued maps. ? A special kind of retractions, called ( N , k ) -retractions, is considered. ? Deletion of simple points and many thinning algorithms are ( N , k ) -retractions. ? We characterize thinning algorithms that can be modeled as ( N , k ) -retractions. ? Characterization in terms of Ronse-like conditions for topology preservation. In some recent papers we have introduced a notion of continuity in digital spaces which extends the usual notion of digital continuity. Our approach, which uses multivalued maps, provides a better framework to define topological notions, like retractions, in a far more realistic way than by using just single-valued digitally continuous functions. In particular, we have characterized the deletion of simple points and some well known parallel thinning algorithm as a particular type of retractions, called ( N , k ) -retractions.In this paper we give a full characterization of the thinning algorithms that can be modeled as ( N , k ) -retractions. This class agrees, with minor modifications, with the class of thinning algorithms satisfying Ronse sufficient conditions for preservation of topology.

In this paper we consider a problem of the polygonal approximation of digital curves with a minimum number of approximation segments for a given error bound with L"2-norm. The Integral Square Error bound is defined by the number of vertices in the curve and by constraint on the Root-Mean-Squared-Error (RMSE) of the polygonal approximation. This paper proposes a new, fast and efficient algorithm for solving the problem. The algorithm that is offered was based on searching for the shortest path in a feasibility graph that has been constructed on the vertices of the input curve. The proposed algorithm provides a solution with 97% optimality on average in what is practically real time. This algorithm can also be used in combination with the Reduced-Search Dynamic Programming algorithm as a preliminary step for finding a near-optimal result in an acceptable time. Experiments conducted with the large size vector data have demonstrated both the high degree of efficiency and the fast performance time of the proposed algorithms. These algorithms can be used in practical applications for image vectorization and segmentation, the analysis of shapes and time series, the simplification of vector maps, and the compression of vector data.

This paper is a response to the similarity measure and pattern recognition problem of Mitchell that was published in Pattern Recognition Letters, 2003. The purpose of this paper is threefold. First, we reviewed and revised her computation for similarity measures. Second, we proved that the similarity values for the one-norm should be larger than that for the two-norm for her pattern recognition problem. Third, we proposed a more scattered similarity measure to help researchers determine patterns. Our findings may shed light on the ongoing debate between Li and Cheng (2002) and Mitchell (2003).

Recently chamfer distances have been developed not only on the usual integer grids, but also on some non traditional grids including grids which are not lattices. In this paper the truncated hexagonal grid is considered: its pixels are dodecagons and two shaped (oriented) triangles. Two types of ‘natural’ neighborhood relations are considered on the grid, consequently two weights are used to describe the chamfer distances. Formulae to compute the minimal weights of a connecting path, i.e., the distance of any two pixels, are provided to cases depending on the relative ratio of the weights. Some properties of these distances, including metricity are also analysed. Digital disks based on the weighted distances are also investigated. In some cases, these disks may not be convex, moreover they may contain holes. The conditions of holes are characterised.

One of the most usual strategies for tackling the 3D object recognition problem consists of representing the objects by their appearance. 3D recognition can therefore be converted into a 2D shape recognition matter. This paper is focused on carrying out an in depth qualitative and quantitative analysis with regard to the performance of 2D shape recognition methods when they are used to solve 3D object recognition problems. Well known shape descriptors (contour and regions) and 2D similarities measurements (deterministic and stochastic) are thus combined to evaluate a wide range of solutions. In order to quantify the efficiency of each approach we propose three parameters: Hard Recognition Rate (Hr), Weak Recognition Rate (Wr) and Ambiguous Recognition Rate (Ar). These parameters therefore open the evaluation to active recognition methods which deal with uncertainty. Up to 42 combined methods have been tested on two different experimental platforms using public database models. A detailed report of the results and a discussion, including detailed remarks and recommendations, are presented at the end of the paper.

Highlights? We show how the use of the original objects could improve the consensus results. ? Weighted association matrix extracts more information from clustering ensembles. ? Data representations and similarity measures can be summarized into a unified matrix. ? The two clustering ensemble algorithms have good performance on several datasets. ? These algorithms are able to work with numerical, categorical and mixed data. Co-association matrix has been a useful tool in many clustering ensemble techniques as a similarity measure between objects. In this paper, we introduce the weighted-association matrix, which is more expressive than the traditional co-association as a similarity measure, in the sense that it integrates information from the set of partitions in the clustering ensemble as well as from the original data of object representations. The weighted-association matrix is the core of the two main contributions of this paper: a natural extension of the well-known evidence accumulation cluster ensemble method by using the weighted-association matrix and a kernel based clustering ensemble method that uses a new data representation. These methods are compared with simple clustering algorithms as well as with other clustering ensemble algorithms on several datasets. The obtained results ratify the accuracy of the proposed algorithms.

This paper aims to solve the problem of matching images containing repetitive patterns. Although repetitive patterns widely exist in real world images, these images are difficult to be matched due to local ambiguities even if the viewpoint changes are not very large. It is still an open and challenging problem. To solve the problem, this paper proposes to match pairs of interest points and then obtain point correspondences from the matched pairs of interest points based on the low distortion constraint, which is meant that the distortions of point groups should be small across images. By matching pairs of interest points, local ambiguities induced by repetitive patterns can be reduced to some extent since information in a much larger region is used. Meanwhile, owing to our newly defined compatibility measure between one correspondence and a set of point correspondences, the obtained point correspondences are very reliable. Experiments have demonstrated the effectiveness of our method and its superiority to the existing methods.

International audience; Geometric moment invariants are widely used in many fields of image analysis and pattern recognition since their first introduction by Hu in 1962. A few years ago, Flusser has proved how to find the indepen- dent and complete set of geometric moment invariants corresponding to a given order. On the other hand, the properties of orthogonal moments show that they can be recognized as useful tools for image representation and reconstruction. Therefore, derivation of invariants from orthogonal moments becomes an interesting subject and some results have been reported in literature. In this paper, we pro- pose to use a family of orthogonal moments, called Gaussian-Hermite moments and defined with Her- mite polynomials, for deriving their corresponding invariants. The rotation invariants of Gaussian- Hermite moments can be achieved algebraically according to a property of Hermite polynomials. This approach is definitely different from the conventional methods which derive orthogonal moment invari- ants either by image normalization or by an expression as a linear combination of the invariants of geo- metric moments. One significant conclusion drawn is that the rotation invariants of Gaussian-Hermite moments have the identical forms to those of geometric moments. This coincidence is also proved math- ematically in the appendix of the paper. Moreover, the translation invariants could be easily constructed by translating the coordinate origin to the image centroid. The invariants of Gaussian-Hermite moments both to rotation and to translation are accomplished by the combination of these two kinds of invariants. Their rotational and translational invariance is evaluated by a set of transformed gray-level images. The numeric stabilities of the proposed invariant descriptors are also discussed under both noise-free and noisy conditions. The computational complexity and time for implementing such invariants are analyzed as well. In addition to this, the better performance of the Gaussian-Hermite invariants is experimentally demonstrated by pattern matching in comparison with geometric moment invariants.

International audience; In some real world applications, such as spectrometry, functional models achieve better predictive performances if they work on the derivatives of order m of their inputs rather than on the original functions. As a consequence, the use of derivatives is a common practice in Functional Data Analysis, despite a lack of theoretical guarantees on the asymptotically achievable performances of a derivative based model. In this paper, we show that a smoothing spline approach can be used to preprocess multivariate observations obtained by sampling functions on a discrete and finite sampling grid in a way that leads to a consistent scheme on the original infinite dimensional functional problem. This work extends (Mas and Pumo, 2009) to nonparametric approaches and incomplete knowledge. To be more precise, the paper tackles two difficulties in a nonparametric framework: the information loss due to the use of the derivatives instead of the original functions and the information loss due to the fact that the functions are observed through a discrete sampling and are thus also unperfectly known: the use of a smoothing spline based approach solves these two problems. Finally, the proposed approach is tested on two real world datasets and the approach is experimentaly proven to be a good solution in the case of noisy functional predictors.

This paper proves that Otsu threshold is equal to the average of the mean levels of two classes partitioned by this threshold. Therefore, when the within-class variances of two classes are different, the threshold biases toward the class with larger variance. As a result, partial pixels belonging to this class will be misclassified into the other class with smaller variance. To address this problem and based on the analysis of Otsu threshold, this paper proposes an improved Otsu algorithm that constrains the search range of gray levels. Experimental results demonstrate the superiority of new algorithm compared with Otsu method.

This paper presents an empirical evaluation on the methods of reducing the dimensionality of dissimilarity spaces for optimizing dissimilarity-based classifications (DBCs). One problem of DBCs is the high dimensionality of the dissimilarity spaces. To address this problem, two kinds of solutions have been proposed in the literature: prototype selection (PS) based methods and dimension reduction (DR) based methods. Although PS-based and DR-based methods have been explored separately by many researchers, not much analysis has been done on the study of comparing the two. Therefore, this paper aims to find a suitable method for optimizing DBCs by a comparative study. Our empirical evaluation, obtained with the two approaches for an artificial and three real-life benchmark databases, demonstrates that DR-based methods, such as principal component analysis (PCA) and linear discriminant analysis (LDA) based methods, generally improve the classification accuracies more than PS-based methods. Especially, the experimental results demonstrate that PCA is more useful for the well-represented data sets, while LDA is more helpful for the small sample size problems.

In a recent paper, Siddiqui et al. introduced a kernel function to be used as a radial basis function (RBF) in image registration tasks. This function is mainly designed so that the resulting deformation is fairly distributed inside its support. The important property of positive definiteness is checked in the paper erroneously, so that the conclusions inferred are wrong. In this communication, we discuss this point and some other methodological errors in the formulation. In addition, we provide some insights into the importance of positive definiteness, concluding that this property may not be critical, or may even be worthless, in certain interpolation problems.

Machine Learning based on the Regularized Least Squares (RLS) model requires one to solve a system of linear equations. Direct-solution methods exhibit predictable complexity and storage, but often prove impractical for large-scale problems; iterative methods attain approximate solutions at lower complexities, but heavily depend on learning parameters. The paper shows that applying the properties of Toeplitz matrixes to RLS yields two benefits: first, both the computational cost and the memory space required to train an RLS-based machine reduce dramatically; secondly, timing and storage requirements are defined analytically. The paper proves this result formally for the one-dimensional case, and gives an analytical criterion for an effective approximation in multidimensional domains. The approach validity is demonstrated in several real-world problems involving huge data sets with highly dimensional data.

A gray-scale image can be interpreted as a topographical surface, and represented by a component tree, based on the inclusion relation of connected components obtained by threshold decomposition. Relations between plateaus, valleys or mountains of this relief are useful in computer vision systems. An important definition to characterize the topographical surface is the dynamics, introduced by Grimaud (1992), associated with each regional minimum. This concept has been extended, by Vachier and Meyer (1995), by the definition of extinction values associated with each extremum of the image. This paper proposes three new extinction values - two based on the topology of the component tree: (i) number of descendants and (ii) sub-tree height; and one geometric: (iii) level component bounding box (subdivided into extinctions of height, width or diagonal). This paper describes an efficient computation of these extinction values based on the incremental determination of attributes from the component tree construction in quasi-linear time, compares the computation time of the method and illustrates the usefulness of these new extinction values from real examples.

A rules induction algorithm dedicated to describe groups of genes with similar expression profiles by means of Gene Ontology terms is discussed in the paper. The presented algorithm takes into consideration information contained in the Gene Ontology graph. A huge number of created rules requires defining the rules quality and similarity measures, thus the paper presents such measures and proposes a new method of the most interesting rules selection. Features reduction method based on the rough sets theory is adopted and applied in order to reduce the number of Gene Ontology terms occurring in rules. The paper presents results of performed experiments and describes shortly the internet application RuleGO in which the proposed methods were implemented.

This paper investigates feature selection based on rough sets for dimensionality reduction in Case-Based Reasoning classifiers. In order to be useful, Case-Based Reasoning systems should be able to manage imprecise, uncertain and redundant data to retrieve the most relevant information in a potentially overwhelming quantity of data. Rough Set Theory has been shown to be an effective tool for data mining and for uncertainty management. This paper has two central contributions: (1) it develops three strategies for feature selection, and (2) it proposes several measures for estimating attribute relevance based on Rough Set Theory. Although we concentrate on Case-Based Reasoning classifiers, the proposals are general enough to be applicable to a wide range of learning algorithms. We applied these proposals on twenty data sets from the UCI repository and examined the impact of feature selection over classification performance. Our evaluation shows that all three proposals benefit the basic Case-Based Reasoning system. They also present robustness in comparison to well-known feature selection strategies.

Wavelet shrinkage is an image denoising technique based on the concept of thresholding the wavelet coefficients. The key challenge of wavelet shrinkage is to find an appropriate threshold value, which is typically controlled by the signal variance. To tackle this challenge, a new image shrinkage approach, called AntShrink, is proposed in this paper. The proposed approach exploits the intra-scale dependency of the wavelet coefficients to estimate the signal variance only using the homogeneous local neighboring coefficients. This is in contrast to that all local neighboring coefficients are used in the conventional shrinkage approaches. Furthermore, to determine the homogeneous local neighboring coefficients, the ant colony optimization (ACO) technique is used in this paper to classify the wavelet coefficients. Experimental results are provided to show that the proposed approach outperforms several image denoising approaches developed in the literature.

In statistical pattern classification, generative approaches, such as linear discriminant analysis (LDA), assume a data-generating process (DGP), whereas discriminative approaches, such as linear logistic regression (LLR), do not model the DGP. In general, a generative classifier performs better than its discriminative counterpart if the DGP is well-specified and worse than the latter if the DGP is clearly mis-specified. In view of this, this paper presents a joint discriminative-generative modelling (JoDiG) approach, by partitioning predictor variables X into two sub-vectors, namely X"G, to which a generative approach is applied, and X"D, to be treated by a discriminative approach. This partitioning of X is based on statistical tests of the assumed DGP: the variables that clearly fail the tests are grouped as X"D and the rest as X"G. Then the generative and discriminative approaches are combined in a probabilistic rather than a heuristic way. The principle of the JoDiG approach is quite generic, but for illustrative purposes numerical studies of the paper focus on a widely-used case, in which the DGP assumes a multivariate normal distribution for each class. In this case, the JoDiG approach uses LDA for X"G and LLR for X"D. Numerical experiments on real and simulated data demonstrate that the performance of this new approach to classification is similar to or better than that of its discriminative and generative counterparts, in particular when the size of the training-set is comparable to the dimension of the data.