Search

The graph-based multi-view clustering method has gained considerable attention in recent years. However, due to its large time complexity, it is limited to handling small-scale clustering datasets. Moreover, most existing models only consider the similarity within views and do not leverage the correlation between views and use the tensor nuclear norm (TNN) as a convex approximation to the tensor rank function. The TNN treats each singular value equally, leading to suboptimal results. To address this issue, this paper proposes a tensorial multi-view clustering model based on bipartite graphs. This paper first introduces a new non-convex logarithmic coupled penalty (LCP) function that treats different singular values differently and preserves the useful structural information required. Additionally, a tensorial bipartite graph clustering model based on logarithmic coupled penalty (LCP-TBGC) is proposed along with a corresponding solution algorithm. The paper also presents a theoretical proof that the obtained resulting sequence converges to the Karush–Kuhn–Tucker (KKT) point. Finally, to validate the effectiveness and superiority of the proposed model, experiments were conducted on eight datasets. • This paper for the first time proposes a new logarithmic coupled penalty function designed to better explore the low-rank nature of tensors. • The improved algorithm is used to solve this model, with theoretical proof showing that it obtains a Cauchy sequence that converges to the KKT point. • Experimental results across eight datasets demonstrate the efficacy of proposed method, which has outperformed other clustering strategies of the same type. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we kernelize conventional clustering algorithms from a novel point of view. Based on the fully mathematical proof, we first demonstrate that kernel KMeans (KKMeans) is equivalent to kernel principal component analysis (KPCA) prior to the conventional KMeans algorithm. By using KPCA as a preprocessing step, we also generalize Gaussian mixture model (GMM) to its kernel version, the kernel GMM (KGMM). Consequently, conventional clustering algorithms can be easily kernelized in the linear feature space instead of a nonlinear one. To evaluate the newly established KKMeans and KGMM algorithms, we utilized them to the problem of semantic object extraction (segmentation) of color images. Based on a series of experiments carried out on a set of color images, we indicate that both KKMeans and KGMM can offer more elaborate output than the conventional KMeans and GMM, respectively. [Copyright &y& Elsevier]

Semi-supervised nonnegative matrix factorization (NMF) methods have found extensive utility in data clustering applications. However, these existing methods encounter challenges in effectively leveraging the limited supervisory information to enhance the performance of clustering. In particular, the majority of these methods tend to solely utilize either the label information or the pairwise constraint information, neglecting the potential benefits of their joint utilization. To address this issue, a novel algorithm named semi-supervised pivotal-aware nonnegative matrix factorization (SPNMF) is proposed in this paper, which utilizes the label information and the pairwise constraint information simultaneously to enhance the performance in data clustering tasks. The proposed method has two main innovations: (1) adopting the dual constraint propagation (DCP) algorithm (i.e., label propagation and pairwise constraint propagation) to effectively utilize a meager amount of label information for learning a compact data representation; (2) incorporating the pivotal-aware technique to mitigate the negative impact of outliers. Notably, the DCP algorithm not only propagates limited label information to a multitude of unlabeled samples, but also disseminates the pairwise constraint supervisory information obtained from the labels to unconstrained samples, allowing for the acquisition of richer supervisory information in the form of pointwise and pairwise constraints. Furthermore, a comprehensive analysis of SPNMF is conducted. Extensive experimental results are executed on eight real-world image datasets. The results underscore the superior performance of SPNMF in comparison to several state-of-the-art methods. • A novel and robust semi-supervised NMF method called SPNMF is proposed, which not only surmounts the limitations of prior semi-supervised NMF methods but also inherits their advantages, resulting in the extraction of a concise low-dimensional data representation. • The DCP algorithm is developed for SPNMF to enable the comprehensive and efficient propagation of limited label information throughout the entire dataset, manifesting as both pointwise and pairwise constraints. • The pivotal-aware technique is applied to improve the robustness of the proposed method. • The convergence, supervisory information utilization, and computational complexity of SPNMF are analyzed. [ABSTRACT FROM AUTHOR]

The impressive success of style-based GANs (StyleGANs) in high-fidelity image synthesis has motivated research to understand the semantic properties of their latent spaces. In this paper, we approach this problem through a geometric analysis of latent spaces as a manifold. In particular, we propose a local dimension estimation algorithm for arbitrary intermediate layers in a pre-trained GAN model. The estimated local dimension is interpreted as the number of possible semantic variations from this latent variable. Moreover, this intrinsic dimension estimation enables unsupervised evaluation of disentanglement for a latent space. Our proposed metric, called Distortion , measures an inconsistency of intrinsic tangent space on the learned latent space. Distortion is purely geometric and does not require any additional attribute information. Nevertheless, Distortion shows a high correlation with the global-basis-compatibility and supervised disentanglement score. Our work is the first step towards selecting the most disentangled latent space among various latent spaces in a GAN without attribute labels. • We propose a scheme to estimate local intrinsic dimensions in GAN latent spaces. • Our local dimension estimate provides an upper bound on local semantic perturbations. • We propose a layer-wise unsupervised disentanglement score, called Distortion. • We analyze the layers of the mapping network in StyleGANs through Distortion metric. [ABSTRACT FROM AUTHOR]

Current graph clustering methods emphasize individual node and edge connections, while ignoring higher-order organization at the level of motif. Recently, higher-order graph clustering approaches have been designed by motif-based hypergraphs. However, these approaches often suffer from hypergraph fragmentation issue seriously, which degrades the clustering performance greatly. Moreover, real-world graphs usually contain diverse motifs, with nodes participating in multiple motifs. A key challenge is how to achieve precise clustering results by integrating information from multiple motifs at the node level. In this paper, we propose a multi-order graph clustering model (MOGC) to integrate multiple higher-order structures and edge connections at node level. MOGC employs an adaptive weight learning mechanism to automatically adjust the contributions of different motifs for each node. This not only tackles hypergraph fragmentation issue but enhances clustering accuracy. MOGC is efficiently solved by an alternating minimization algorithm. Experiments on seven real-world datasets illustrate the effectiveness of MOGC. • We propose a multi-order graph clustering model to integrate multiple higher-order and lower-order structures at the node level. • An adaptive weight learning mechanism is formulated to automatically adjust the contributions of different motifs for each node. • We employ the model to solve fragmentation issue and achieve more accurate partition results simultaneously. • Extensive experiments show the outperformance of our proposed method. [ABSTRACT FROM AUTHOR]

While many nonlinear pattern recognition and data mining tasks rely on embedding the data into a latent space, one often needs to extract the patterns in the input space. Estimating the inverse of the nonlinear embedding is the so-called pre-image problem. Several strategies have been proposed to address the estimation of the pre-image; However, there are no theoretical results so far to understand the pre-image problem and its resolution. In this paper, we provide theoretical underpinnings of the resolution of the pre-image problem in Machine Learning. These theoretical results are on the gradient descent optimization, the fixed-point iteration algorithm and Newton's method. We provide sufficient conditions on the convexity/nonconvexity of the pre-image problem. Moreover, we show that the fixed-point iteration is a Newton update and prove that it is a Majorize-Minimization (MM) algorithm where the surrogate function is a quadratic function. These theoretical results are derived for the wide classes of radial kernels and projective kernels. We also provide other insights by connecting the resolution of this problem to the gradient density estimation problem with the so-called mean shift algorithm. • Solid foundations on the resolution of the pre-image problem in Machine Learning • Relationship between the fixed-point iteration technique and Newton's method • Fixed-point iteration is a Majorize-Minimization algorithm • General theoretical results for the wide classes of radial and projective kernels [ABSTRACT FROM AUTHOR]

In partial label learning, each training object is assigned a valid label and pseudo-labels, and a multi-class classifier is derived with inaccurate supervision. However, ambiguous labeling information adversely affects the performance of the classifier. Partial label feature selection has been shown efficiently improve the generalization performance of classifiers. Traditional manifold learning can employ intrinsic geometric information to identify discriminative features, while it is challenging due to the noisy manifold caused by pseudo-labels. Consequently, this paper proposes an embedding partial label feature selection based on noisy manifold and label distribution, which exploits feature dependency, label correlation, and instance relevance. Specifically, a linear regression function projects the feature space to the low-dimensional manifold space, which can avoid the influence of pseudo-labels affected by direct projection to the label space. The feature dependency and label correlation are obtained by manifold regularization in the feature and label space to reflect the feature significance. During optimization, instance similarity constraints variable iteration. Label distribution obtained through feature significance and instance relevance guides label space updates and reduces the impact of noise in the manifold. The effectiveness and robustness of the proposed algorithm are corroborated through experiments with three classifiers and five comparison methods on twelve datasets. • A novel manifold-based partial label feature selection method is proposed. • Low-dimensional manifold is induced to reduce the adverse effects of pseudo-labels. • Label distribution is explored to facilitate the selection of the most discriminative features. • Extensive experiments demonstrate that the proposed algorithm is effective and robust. [ABSTRACT FROM AUTHOR]

This paper proposes an online visual multi-object tracking (MOT) algorithm that resolves object appearance–reappearance and occlusion. Our solution is based on the labeled random finite set (LRFS) filtering approach, which in principle, addresses disappearance, appearance, reappearance, and occlusion via a single Bayesian recursion. However, in practice, existing numerical approximations cause reappearing objects to be initialized as new tracks, especially after long periods of being undetected. In occlusion handling, the filter's efficacy is dictated by trade-offs between the sophistication of the occlusion model and computational demand. Our contribution is a novel modeling method that exploits object features to address reappearing objects whilst maintaining a linear complexity in the number of detections. Moreover, to improve the filter's occlusion handling, we propose a fuzzy detection model that takes into consideration the overlapping areas between tracks and their sizes. We also develop a fast version of the filter to further reduce the computational time. • Deep features and occlusion handling model enhance visual MOT performance. • Deep features improve track re-ID and appearance–reappearance resolution. • Labeled random finite set filters (GLMB and LMB) are effective for visual tracking. [ABSTRACT FROM AUTHOR]

In density based clustering, the density peak algorithm has attracted much attention due to its effectiveness and simplicity, and a vast amount of clustering approaches have been proposed based on this algorithm. Some of these works require manual selection of cluster centers with a decision graph, where human involvement leads to uncertainty in clustering results. In order to avoid human involvement, some other algorithms depend on user-specified number of clusters to determine cluster centers automatically. However, it is well known that accurate estimation of number of clusters is a long-standing difficulty in data clustering. In this paper we present a sequential density peak clustering algorithm to extract clusters one by one, thereby determining the number of clusters automatically and avoiding manual selection of cluster centers in the meanwhile. Starting from a density peak, our algorithm generates an initial cluster surrounding the density peak in the first step, and then obtains the final cluster by expanding the initial cluster based on the relative density relationship among neighboring data points. With a peeling-off strategy, we obtain all the clusters sequentially. Our algorithm works well with clusters of Gaussian distribution and is therefore potential for clustering of real-world data. Experiments with a large number of synthetic and real datasets and comparisons with existing algorithms demonstrate the effectiveness of the proposed algorithm. • Be able to determine number of clusters and cluster centers automatically. • Present a non-parametric method to expand initial clusters. • The parameters are kept at the minimum and can be fixed for many datasets. • Extensive experiments demonstrate the effectiveness of our algorithm. [ABSTRACT FROM AUTHOR]

Tensor completion involves recovering the underlying tensor from partial observations, and in this paper we focus on the point that these observations obey the Poisson distribution. To contend with this problem, we adopt a popular method that minimizes the sum of the data-fitting term and the regularization term under a uniform sampling mechanism. Specifically, we consider the negative logarithmic maximum likelihood estimate of the Poisson distribution as the data-fitting term. To effectively characterize the intrinsic structure of the tensor data, we propose a parameter-free regularization term that can simultaneously capture the low rankness and local smoothness of the underlying tensor. Here, the transformed tensor nuclear norm is used to explore the low rankness under suitable unitary transformations. We present theoretical derivations to demonstrate the feasibility of the proposed model. Furthermore, we develop an algorithm based on the alternating direction multiplier method (ADMM) to efficiently solve the proposed optimization problem, with its overall convergence being established. A series of numerical experiments show that proposed model yields a pleasing accuracy over several state-of-the-art models. • We considers a tensor completion with Poisson observations, differing from common researches. • TCTV regularizer can simultaneously characterize global low rankness and local smoothness. • Transformed tensor nuclear norm is introduced to obtain lower transformed multi-rank. • ADMM-based optimization algorithm with global convergence guarantee is implemented. • Experiments show superior performance in recovering global structure and details. [ABSTRACT FROM AUTHOR]

It is known that unsupervised nonlinear learning is sensitive to the selection of hyperparameters, which hinders its practical use. How to determine the optimal hyperparameter setting that may be dramatically different across applications is a hard issue. In this paper, we aim to address this issue for multilayer bootstrap networks (MBN), a recent unsupervised model, in a way as simple as possible. Specifically, we first propose an MBN ensemble (MBN-E) algorithm which concatenates the sparse outputs of a set of MBN base models with different network structures into a new representation. Then, we take the new representation produced by MBN-E as a reference for selecting the optimal MBN base models. Moreover, we propose a fast version of MBN-E (fMBN-E), which is not only theoretically even faster than a single standard MBN but also does not increase the estimation error of MBN-E. Empirically, comparing to a number of advanced clustering methods, the proposed methods reach reasonable performance in their default settings. fMBN-E is empirically hundreds of times faster than MBN-E without suffering performance degradation. The applications to image segmentation and graph data mining further demonstrate the advantage of the proposed methods. • A simple MBN-E algorithm were proposed to reduce the sensitivity of MBN to its network structure. • MBN-SO and MBN-SD, which group some MBN base models with high performance into new MBN-E were proposed. • Theoretical analysis on the connection between the performance and the depth of MBN was made. • Experimental results demonstrate the effectiveness of the proposed methods without manual tuning. [ABSTRACT FROM AUTHOR]

Multi-view clustering algorithms based on graph learning have the ability to extract the potential association between data samples, which has been a concern of many researchers in recent years. However, existing algorithms have two limitations: (1) they directly learn from the raw graph, which includes noise and outliers, and they construct the graph filter statically, biasing the clustering results; (2) during graph construction, they mainly use the information of a single structure and fail to fully extract the multi-granular structural information among the data. To address these issues, this paper proposes a novel multi-view clustering method via dynamic unified bipartite graph learning. Specifically, a learnable graph filter is first refined to dynamically filter the original data feature space, gradually filtering out the undesirable high-frequency noise and achieving a clustering-friendly smooth representation. Second, a unified bipartite graph is constructed by combining the multi-granular structural information of different views to better explore the distinct and common information of each view. In one framework, the dynamic filter and multi-granular structure information are combined to iteratively learn the unified bipartite graph. An efficient iterative algorithm is designed to decompose the objective function into small-scale subproblems for solving. Extensive experiments on benchmark datasets show the superiority of the proposed algorithm over several existing state-of-the-art multi-view clustering algorithms. [ABSTRACT FROM AUTHOR]

Recently, zero-shot cross-modal hashing has gained significant popularity due to its ability to effectively realize the retrieval of emerging concepts within multimedia data. Although the existing approaches have shown impressive results, the following limitations still need to be solved: (1) Labels in large-scale multimodal datasets in real scenes are usually incomplete or partially missing. (2) The existing methods ignore the influence of features-wise low-level similarity and label distribution on retrieval performance. (3) The representation ability of dense hash codes limits its discriminative potential. To solve these issues, we introduce an effective cross-modal retrieval framework called two-stage zero-shot sparse hashing with missing labels (TZSHML). Specifically, we learn a classifier through the partially known labeled samples to predict the labels of unlabeled data. Then, we use the reliable information in the correctly marked labels to recover the missing labels. The predicted and recovered labels are combined to obtain more accurate labels for the samples with missing labels. In addition, we employ sample-wise fine-grained similarity and cluster-wise similarity to learn hash codes. Therefore, TZSHML ensures that more samples with similar semantics are clustered together. Besides, we apply high-dimensional sparse hash codes to explore richer semantic information. Finally, the drift and interaction terms are introduced into the learning of the hash function to further narrow the gap between different modalities. Extensive experimental results demonstrate the competitiveness of our approach over other state-of-the-art methods in zero-shot retrieval scenarios with missing labels. The source code of this paper can be obtained from https://github.com/szq0816/TZSHML. • Each stage operates independently, resulting in a concise and efficient algorithm. • Our approach emphasizes mitigating the impact of missing labels. • We train a classifier to predict labels for instances with missing labels. • We jointly utilize cluster-wise similarity and sample-wise fine-grained similarity. • We employ high-dimensional sparse hash codes to improve the discriminative ability. [ABSTRACT FROM AUTHOR]

In recent years, face detection algorithms based on deep learning have made great progress. Nevertheless, the effective utilization of face detectors for small and occlusion faces remains challenging, primarily stemming from the limitations in pixel information and the presence of missing features. In this paper, we propose a novel real-time face detector, YOLO-FaceV2, built upon the YOLOv5 architecture. Our approach introduces a Receptive Field Enhancement (RFE) module designed to extract multi-scale pixel information and augment the receptive field for accurately detecting small faces. To address issues related to face occlusion, we introduce an attention mechanism termed the Separated and Enhancement Attention Module (SEAM), which effectively focuses on the regions affected by occlusion. Furthermore, we propose a Slide Weight Function (SWF) to mitigate the imbalance between easy and hard samples. The experiments demonstrate that our YOLO-FaceV2 achieves performance exceeding the state-of-the-art on the WiderFace validation dataset. Source code and pre-trained model are available at https://github.com/Krasjet-Yu/YOLO-FaceV2. • Proposed an YOLO-FaceV2 detector to address face detection. • Good performance under face occlusion and varying scales. • Designed a novel weighting function alleviated the problem of imbalanced samples. • Detection results on the WiderFace validation dataset are 98.6%, 97.9% and 91.9%. • Achieved state-of-the-art performance on the easy and medium subset of WiderFace dataset. [ABSTRACT FROM AUTHOR]

Differentiable solvers for the linear assignment problem (LAP) have attracted much research attention in recent years, which are usually embedded into learning frameworks as components. However, previous algorithms, with or without learning strategies, usually suffer from the degradation of the optimality with the increment of the problem size. In this paper, we propose a learnable linear assignment solver based on deep graph networks. Specifically, we first transform the cost matrix to a bipartite graph and convert the assignment task to the problem of selecting reliable edges from the constructed graph. Subsequently, a deep graph network is developed to aggregate and update the features of nodes and edges. Finally, the network predicts a label for each edge that indicates the assignment relationship. The experimental results on a synthetic dataset reveal that our method outperforms state-of-the-art baselines and achieves consistently high accuracy with the increment of the problem size. Furthermore, we also embed the proposed solver, in comparison with state-of-the-art baseline solvers, into a popular multi-object tracking (MOT) framework to train the tracker in an end-to-end manner. The experimental results on MOT benchmarks illustrate that the proposed LAP solver improves the tracker by the largest margin. • We convert the problem of LAP to learning of edge selection from a bipartite graph. • We propose a differentiable graph-based framework to update the graph states. • The proposed model achieves excellent performance in different aspects. • The proposed LAP solver can be embedded into MOT pipeline boost tracking performance. [ABSTRACT FROM AUTHOR]

Recently, multi-view high dimensional data obtained from diverse domains or various feature extractors has drawn great attention due to its reflection of different properties or distributions. In this paper, we propose a novel unsupervised multi-view clustering method, which is called Multi-View Reduced Dimensionality K-means clustering (MRDKM) and integrates the dimension reduction mechanism, σ -norm, Schatten p -norm, and multi-view K-means clustering. Moreover, an unsupervised optimization scheme was proposed to solve the minimization problem with good convergence properties. Comprehensive evaluations of five benchmark datasets and comparisons with several multi-view clustering algorithms demonstrate the superiority of the proposed work. • In order to avoid the influence of dimensional curse and redundant features in the original space, we use dimension reduction technology to process high-dimensional multi-view data. • We use the σ -norm as an adaptive loss minimization, it flexibly weighs sparsity and continuity. • We form the label matrix into a third-order tensor and apply the Schatten p-norm to mine higher-order relationships between multiple views. • An optimization strategy based on ALM is proposed. A large number of experiments show that our method has good performance. [ABSTRACT FROM AUTHOR]

The challenge posed by the template-based reconstruction attack significantly impacts the security and privacy of biometric systems. Current reconstruction techniques rely on extensive training data or encounter limitations in adaptability, resulting in subpar reconstruction performance. In this paper, we propose a black-box palmprint template reconstruction method based on the modified Progressive GAN (ProGAN), which achieves a substantial success rate in attacking deep-learning-based and hand-crafted-based templates. Our approach incorporates the dropout mechanism into the generator of ProGAN and introduces a Double Reuse Training Strategy to enable effective training of the reconstruction network despite limited data. Furthermore, we devise a novel Scale-Adaptive Multi-Texture Complementarity loss, enhancing the texture quality of reconstructed images. We conduct extensive experiments on diverse palmprint recognition techniques. The resulting reconstructed images exhibit exceptional image quality. Additionally, we thoroughly examine the security and privacy aspects of the palmprint recognition algorithm based on the insights gained from the reconstruction attacks. [Display omitted] • The first palmprint reconstruction method suitable for both code and deep templates. • Dropout improves ProGAN architecture for reconstruction task. • Two strategies, namely SAMTC and DRTS, enhance reconstruction performance. • A comprehensive assessment system for reconstructed image quality. • This work reveals deep-based methods are more resistant to reconstruction attack. [ABSTRACT FROM AUTHOR]

Determination of the optimal number of clusters, the random selection of the initial centers, the non-detection of non-spherical clusters, and the negative impact of outliers are the main challenges of the K-means algorithm. In this paper, to tackle these issues three simple and intelligent algorithms are proposed by changing the structure of the K-means and K-medoids algorithms. The difference between these algorithms is in the selection of the initial centers and the stop condition. A method has been proposed to obtain the overlap space between the clusters. Using this method, a modified K-means algorithm is developed for the clustering of non-spherical data. These algorithms are designed in a way that they are not sensitive to outliers and can identify clusters having non-spherical shapes. The performance of the proposed methods is illustrated by applying the proposed algorithms to the different data sets and by comparing the results of the algorithms with other methods. • An Intelligent center selection method is proposed for faster convergence. • A method is proposed to identify clusters with non-spherical and asymmetrical shapes. • Two selection methods are proposed to determine the other initial centers to identify outliers. • Two methods are proposed to determine the optimal number of clusters during clustering. • All of the above are used seamlessly in K-means and K-medoids algorithms. [ABSTRACT FROM AUTHOR]

Adversarial training has been considered to be one of the most effective strategies to defend against adversarial attacks. Most existing adversarial training methods have shown a trade-off between training cost and robustness. This paper explores a new optimization direction from training data to reduce the computational cost of adversarial training without scarifying robustness. First, we show that some adversarial examples are less important, meaning that removing them does not hurt the robustness. Second, we propose a method to identify insignificant adversarial examples at a minimal cost. Third, we demonstrate that our approach can be integrated with other adversarial training frameworks with few modifications. The experimental results show that combined with previous works, our approach not only reduces about 20% of computational cost on the CIFAR10 and CIFAR100 datasets but also improves about 1.5% natural accuracy. With less computational cost, it achieves 58.22%, 30.68%, and 41.92% robust accuracy on CIFAR10, CIFAR100, and ImageNet datasets respectively, which are higher than those of the original methods. • Analyze the effectiveness of adversarial examples for adversarial training. • Design a method to remove inefficient adversarial examples but maintain the accuracy. • Design an algorithm to detect inefficient adversarial examples without extra cost. • Conduct experiments to demonstrate the compatibility with other frameworks. [ABSTRACT FROM AUTHOR]

Cluster analysis is one of the most important research issues in data mining and machine learning. To date, numerous clustering algorithms have been proposed to tackle the fixed-length vector data. In many real applications, we need to detect clusters from a set of discrete sequences in which each sequence is an ordered list of items. Due to the sequential and discrete nature, the discrete sequence clustering problem is more challenging and most of existing vector data clustering algorithms cannot be directly employed. In this paper, we present a stochastic algorithm for clustering discrete sequences. Our method first quickly generates a set of random partitions over the sequential data set and then merges these random clustering results via weighted graph construction and partition. We perform extensive empirical comparisons on real data sets to show that our method is comparable to those state-of-the-art clustering algorithms with respect to both accuracy and efficiency. • A randomized algorithm is proposed to solve the discrete sequence clustering issue. • Our algorithm provides high success rate for sequence linkage in clusters. • Experimental results demonstrate the feasibility and effectiveness of our method. [ABSTRACT FROM AUTHOR]

Highlights • This paper proposes a novel connected components labeling (CCL) approach, a gamma-signal-regulated approach, for higher efficiency. • A new and more efficient block-based two-scan CCL algorithm, Eight-Connected Gamma-Signal-regulated (ECGS) algorithm, is proposed. • Experiment results have demonstrated that ECGS can outperform current state-of-the-art CCL algorithms for a number of digital images. Abstract This paper proposes a novel connected components labeling (CCL) approach that introduces a gamma signal to record certain mask pixels' values to eliminate duplicated pixel checking and regulate the labeling process for higher efficiency. A new block-based two-scan CCL algorithm, Eight-Connected Gamma-Signal-regulated (ECGS) algorithm, is designed and developed by applying this approach to evaluate a block of 2 × 2 pixels (with just 6 mask pixels) in each iteration such that the total number of operations is considerably reduced and the labeling efficiency is significantly improved. The experiments conducted on a public benchmark, YACCLAB (Yet Another Connected Components Labeling Benchmark), have demonstrated that the proposed ECGS algorithm can outperform current state-of-the-art CCL algorithms for a number of digital images. [ABSTRACT FROM AUTHOR]

Highlights • We find an observation important to the LSN subspace segmentation. • We provide the theoretical support of the mentioned observation. • Our paper is the first to adopt infinite norm in subspace segmentation. • The computational complexity of our ADM algorithm is lower than O (n 3). • Our method achieve the state-of-the-art results in extensive experiments. Abstract Spectral-clustering based methods have recently attracted considerable attention in the field of subspace segmentation. The approximately block-diagonal graphs achieved by this kind of methods usually contain some noise, i.e., nonzero elements in the off-diagonal region, due to outlier contamination or complex intrinsic structure of the dataset. In the experiment of most previous work, the number of the subspaces is often no more than 10. In this situation, this kind of noise almost has no influence on the segmentation results. However, the segmentation performance could be negatively affected by the noise when the number of subspaces is large, which is quite common in the real-world applications. In this paper, we address the problem of LSN subspace segmentation, i.e., large subspace number subspace segmentation. We first show that the approximately block-diagonal graph with the smaller difference in its diagonal blocks will be more robust to the off-diagonal noise mentioned above. Then, by using the infinity norm to control the bound of the difference in the diagonal blocks, we propose infinity norm minimization for LSN subspace segmentation. Experimental results demonstrate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Highlights • We propose a linear classifier design method in the weight space based on the observation that a training sample represents a plane in the weight space. • We proposed search algorithms to find the optimal subspace, though the optimal solution may not be guaranteed since the full search cannot be used. • Experimental results show that the proposed classifier performed better than or equivalent to existing linear classifiers (linear SVM, LDA). Abstract In this paper, we propose a linear classifier design method in the weight space. A linear classifier is completely determined by a weight vector. To design a linear classifier is equivalent to finding a weight vector. When there are a number of training samples, each training sample represents a plane in the weight space. On one side of the plane, the training sample is correctly classified while it is incorrectly classified on the other side. Thus, finding the optimal linear classifier can be formulated as finding a subspace that provides the best classification accuracy. In this paper, we have developed an algorithm to find such optimal subspaces in the weight space. Although we could not find the optimal linear classifier due to prohibitive computational complexity, the proposed design method produced noticeable improvements in some cases. Experimental results show that the proposed linear classifier performed better than or equivalent to existing linear classifiers. [ABSTRACT FROM AUTHOR]

Highlights • First system for Simultaneous Localization and Mapping in large environments from Squared Planar Markers. • Print markers with a regular printer and place them in environment. Use a camera an our system finds the camera position while estimating the pose of the markers at the same time. • Real time operation on CPUs (150 Hz) with a single execution thread. Abstract SLAM is generally addressed using natural landmarks such as keypoints or texture, but it poses some limitations, such as the need for enough textured environments and high computational demands. In some cases, it is preferable sacrificing the flexibility of such methods for an increase in speed and robustness by using artificial landmarks. The recent work [1] proposes an off-line method to obtain a map of squared planar markers in large indoor environments. By freely distributing a set of markers printed on a piece of paper, the method estimates the marker poses from a set of images, given that at least two markers are visible in each image. Afterwards, camera localization can be done, in the correct scale. However, an off-line process has several limitations. First, errors can not be detected until the whole process is finished, e.g., an insufficient number of markers in the scene or markers not properly spotted in the capture stage. Second, the method is not incremental, so, in case of requiring the expansion of the map, it is necessary to repeat the whole process from start. Finally, the method can not be employed in real-time systems with limited computational resources such as mobile robots or UAVs. To solve these limitations, this work proposes a real-time solution to the problems of simultaneously localizing the camera and building a map of planar markers. This paper contributes with a number of solutions to the problems arising when solving SLAM from squared planar markers, coining the term SPM-SLAM. The experiments carried out show that our method can be more robust, precise and fast, than visual SLAM methods based on keypoints or texture. [ABSTRACT FROM AUTHOR]

• We propose an improved differential evolution (DE) algorithm by composite binary crossover and Pareto refining operations to the DE. • DE solves the quantifying fraudulent transactions problem by minimizing the selected feature cost while maximizing the quantification ability. • We show that the proposed DE outperforms four other variants of DE and five state-of-the-art EAs on various credit datasets. • The results are also statically validated through the Friedman test and Wilcoxon post-hoc analysis. [Display omitted] Identification of fraudulent credit card transactions is a complex problem mainly due to the following factors: 1) The relative behavior of customers and fraudsters may alter over time. 2) The ratio of legitimate to fraudulent transactions is highly imbalanced, and 3) Investigators examine a small segment of transactions in a reasonable time frame. Researchers have proposed various algorithms to identify potential fraud in a new incoming transaction. However, these approaches require significant human investigator effort and are sometimes misleading. To address this issue, this paper proposes an improved multiobjective differential evolution (DE) algorithm to estimate the distribution of fraudulent transactions in a set of new incoming transactions, referred to as quantifying fraudulent transactions. Our paper has three major novelties. First, we present the problem formulation of cost-based feature selection with maximum quantification ability. Second, we improve the DE by applying effective trial vector generation algorithms to the random control parameter settings to exploit the advantage of individual DE variants. Third, we develop the maximum-relevancy-minimum-redundancy-based Pareto refining operator to enhance the self-learning ability of individuals in Pareto solutions. We compare our approach against four other modifications of DE and five state-of-the-art evolutionary algorithms on real-time credit datasets in streaming and non-streaming frameworks using hyper-volume, two-set coverage, and spread performance metrics. [ABSTRACT FROM AUTHOR]

Abstract: -Means algorithm and its variations are known to be fast clustering algorithms. However, they are sensitive to the choice of starting points and inefficient for solving clustering problems in large data sets. Recently, a new version of the -means algorithm, the global -means algorithm has been developed. It is an incremental algorithm that dynamically adds one cluster center at a time and uses each data point as a candidate for the -th cluster center. Results of numerical experiments show that the global -means algorithm considerably outperforms the -means algorithms. In this paper, a new version of the global -means algorithm is proposed. A starting point for the -th cluster center in this algorithm is computed by minimizing an auxiliary cluster function. Results of numerical experiments on 14 data sets demonstrate the superiority of the new algorithm, however, it requires more computational time than the global -means algorithm. [Copyright &y& Elsevier]

Abstract: This paper presents a novel algorithm for computing graph edit distance (GED) in image categorization. This algorithm is purely structural, i.e., it needs only connectivity structure of the graph and does not draw on node or edge attributes. There are two major contributions: (1) Introducing edge direction histogram (EDH) to characterize shape features of images. It is shown that GED can be employed as distance of EDHs. This algorithm is completely independent on cost function which is difficult to be defined exactly. (2) Computing distance of EDHs with earth mover distance (EMD) which takes neighborhood bins into account so as to compute distance of EDHs correctly. A set of experiments demonstrate that the newly presented algorithm is available for classifying and clustering images and is immune to the planar rotation of images. Compared with GED from spectral seriation, our algorithm can capture the structure change of graphs better and consume 12.79% time used by the former one. The average classification rate is 5% and average clustering rate is 25% higher than the spectral seriation method. [Copyright &y& Elsevier]

This paper investigates algorithms for matrix factorization when some or many components are missing, a problem that arises frequently in computer vision and pattern recognition. We demonstrate that the Jacobian used in the damped Wiberg (DW) method is exactly the same as that of Kaufman's simplified variable projection (VP) algorithm. Our analysis provides a novel perspective on the efficiency of VP algorithms by improving the strong convexity of the approximate function. To enhance numerical stability, we set a lower bound on the damping parameter instead of adding a null space like the DW algorithm. Another challenge of low-rank matrix decomposition with missing data is the existence of many sharp local minima, which are often distributed in narrow valleys of the landscape of objection functions. Falling into such minima tends to result in poor reconstruction results. To address this issue, we design a non-monotonic VP algorithm, which can facilitate the algorithm to escape from sharp minima and converge to flatter minima. Numerical experiments confirm the effectiveness and efficiency of the proposed nonmonotone VP algorithm. • We provide a new perspective to examine the superiority of the VP algorithm from a convexity point of view. • We propose a nonmonotone VP algorithm, which can facilitate the algorithm to escape from sharp minima. • We conduct extensive experiments to validate the effectiveness of the proposed nonmonotone algorithm. [ABSTRACT FROM AUTHOR]

Wide-angle video frames typically contain more information, but they also exhibit distortion that degrades the visual quality, especially at the edges. To eliminate this distortion from videos, we propose a self-supervised iterative optimization method in this paper. Specifically, we construct a motion parameter estimation model utilizing two consecutive distorted frames, where motion parameters comprise affine transform and distortion parameters. We apply the Gauss–Newton algorithm to minimize the sum-of-squares error between frames and update parameters. Treating inter-frame motion as undistort-affine-distort transformations, frame alignment is achieved by continuously adjusting transform parameters. Ultimately, frames are corrected using the converged parameters. We generated a synthetic dataset with various distortion parameters for evaluation. Experiments demonstrate superior performance versus state-of-the-art methods on synthetic and real wide-angle videos. Our algorithm also achieves higher parameter estimation accuracy without sacrificing efficiency. • proposes a algorithm for video distortion correction based on iterative optimization. • the distort transform and undistort transform are derived separately and the range of parameters and the experimental error are given. • Based on this, we transform the distortion correction into a parameter estimation problem in image alignment. • optimize the parameter estimation problem using Gauss-Newton algorithm. • Experimental results show that the proposed algorithms outperform some state-of-art algorithms in accuracy, without reducing robustness and efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we investigate L 0 -regularized logistic regression models, and design two fast and efficient algorithms for high-dimensional correlated data and massive data, respectively. Our first algorithm, the Variable Sorted Active Set (VSAS) algorithm, is based on the local quadratic approximation of the KKT conditions for L 0 -penalized maximum log-likelihood function in high-dimensional correlated data. We establish an L ∞ error upper bound for the estimator obtained by the VSAS algorithm and prove its optimal convergence rate. Moreover, when the target signal exceeds the detectable level, the estimator obtained by the VSAS algorithm can achieve the oracle estimator with high probability. Our second algorithm, Communication Effective Variable Sorted Active Set (CEVSAS), aims to solve high-dimensional and large-sample L 0 -regularized logistic regression models by reduce computational and communication costs, while maintaining estimation efficiency. Finally, simulations and real data demonstrate the effectiveness of our proposed VSAS and CEVSAS algorithms. • We develop a fast VSAS algorithm for L 0 regularized logistic regression involving high-dimensional correlated data. • An L ∞ upper bound is established on the estimation error of the solution sequence generated by VSAS algorithm. • The CEVSAS altorithm is proposed to reduce computational costs and ensure higher estimation efficiency. • We propose two adaptive versions of the VSAS and CEVSAS algorithms for selecting the optimal tuning parameters. [ABSTRACT FROM AUTHOR]

This paper proposes a new method of personal identification that introduces the analysis of lip prints. In spite of its important role in forensic and biometric applications, the results of previous investigations into lip prints are scanty. This is mainly due to the difficulties that accompany any analysis of the lips: lips are very flexible and pliable, and successive lip print impressions – even those obtained from the same person – may significantly differ from one other. Our article’s principal contribution is a proposal for a new personal identification methodology and application that uses, for the first time, a strategy for biometric and forensic analysis of lip print structure. As a result of our analysis we propose a lip print pattern for each individual. This pattern contains only such furrows that occur on the greatest number of lip prints obtained from the same person, where these furrows’ locations and inclinations remain similar across the lip prints obtained. It should be noted that in our approach, instead of lip photos we employ lip prints, such as can be obtained at a crime scene. It is worth noticing also that we propose a new method of personal identification where, instead of popular machine learning methods,the furrow-analysis of lip prints is introduced. Thus, no classifier learning phase is required. According to the authors’ convictions, based on reports in the literature, the proposed approach describes for the first time a strategy as to how lip print structures could be analyzed in biometric applications. The main novelty of this paper is its use of multiple lip print furrows from the same person to determine the most common lip furrow distribution in four different directions. On the basis of the pattern recognition of the lip furrows, the identity of the person will be determined. The proposed method’s effectiveness is 92.73%, determined using a database containing 350 lip prints. [ABSTRACT FROM AUTHOR]

This paper explores the problem of circle fitting for incomplete (partial arc) laser scanning point cloud data in the presence of outliers. In mobile laser scanning, data are commonly incomplete because of the orientation of the scanning unit to the surveying objects and the limited street-based positions. Also, multiple structures in the built environment often produce clustered outliers. To address these problems, this paper combines robust Principal Component Analysis (PCA) and robust regression with an efficient algebraic circle fitting method to develop two algorithms for circle fitting. Experimental efforts show that the proposed algorithms are statistically robust and can tolerate a high-percentage (exceeding 44%) of clustered outliers with insignificant error levels, while still achieving better shape recognition compared to existing competitive methods. For example, for a simulation of 1000 quarter circle datasets including 20% clustered outliers, RANSAC estimated the circle radius with a Mean Squared Error (MSE) of 172.10, whereas the proposed algorithms fit circles with an MSE of less than 0.42. The algorithms have potential in many areas including building information modeling, particle tracking, product quality control, arboreal assessment, and road asset monitoring. [ABSTRACT FROM AUTHOR]

This guest editorial introduces the twenty two papers accepted for this Special Issue on Articulated Motion and Deformable Objects (AMDO). They are grouped into four main categories within the field of AMDO: human motion analysis (action/gesture), human pose estimation, deformable shape segmentation, and face analysis. For each of the four topics, a survey of the recent developments in the field is presented. The accepted papers are briefly introduced in the context of this survey. They contribute novel methods, algorithms with improved performance as measured on benchmarking datasets, as well as two new datasets for hand action detection and human posture analysis. The special issue should be of high relevance to the reader interested in AMDO recognition and promote future research directions in the field. [ABSTRACT FROM AUTHOR]

Multiple instance learning (MIL) is a form of weakly supervised learning where training instances are arranged in sets, called bags, and a label is provided for the entire bag. This formulation is gaining interest because it naturally fits various problems and allows to leverage weakly labeled data. Consequently, it has been used in diverse application fields such as computer vision and document classification. However, learning from bags raises important challenges that are unique to MIL. This paper provides a comprehensive survey of the characteristics which define and differentiate the types of MIL problems. Until now, these problem characteristics have not been formally identified and described. As a result, the variations in performance of MIL algorithms from one data set to another are difficult to explain. In this paper, MIL problem characteristics are grouped into four broad categories: the composition of the bags, the types of data distribution, the ambiguity of instance labels, and the task to be performed. Methods specialized to address each category are reviewed. Then, the extent to which these characteristics manifest themselves in key MIL application areas are described. Finally, experiments are conducted to compare the performance of 16 state-of-the-art MIL methods on selected problem characteristics. This paper provides insight on how the problem characteristics affect MIL algorithms, recommendations for future benchmarking and promising avenues for research. Code is available on-line at https://github.com/macarbonneau/MILSurvey . [ABSTRACT FROM AUTHOR]

Ensemble methods have shown to be more effective than monolithic classifiers, in particular when diversity holds among their components. How to enforce diversity in classifier ensembles has received much attention from machine learning researchers, yielding a variety of different techniques and algorithms. In this paper, a novel algorithm for ensemble classifiers is proposed, in which ensemble components are trained with focus on different regions of the sample space. In so doing, diversity is mainly a consequence of the intention to limit the scope of base classifiers. The algorithm proposed in this paper shares roots with several ensemble paradigms, in particular with random forests, as it generates forests of decision trees as well. As decision trees are trained with focus on specific subsets of the sample space, the resulting ensemble is in fact a forest of “local” trees. Comparative experimental results highlight that, on average, these ensembles perform better than other relevant kinds of ensemble classifiers, including random forests. [ABSTRACT FROM AUTHOR]

The term “iris” refers to the highly textured annular portion of the human eye that is externally visible. An iris recognition system exploits the richness of these textural patterns to distinguish individuals. Iris recognition systems are being used in a number of human recognition applications such as access control, national ID schemes, border control, etc. To capture the rich textural information of the iris pattern regardless of the eye color, traditional iris recognition systems utilize near-infrared (NIR) sensors to acquire images of the iris. This, however, restricts the iris image acquisition distance to close quarters (less than 1 m). Over the last several years, there have been numerous attempts to design and implement iris recognition systems that operate at longer standoff distances ranging from 1 m to 60 m. Such long range iris acquisition and recognition systems can provide high user convenience and improved throughput. This paper reviews the state-of-the-art design and implementation of iris-recognition-at-a-distance (IAAD) systems. In this regard, the design of such a system from both the image acquisition (hardware) and image processing (algorithms) perspectives are presented. The major contributions of this paper include: (1) discussing the significance and applications of IAAD systems in the context of human recognition, (2) providing a review of existing IAAD systems, (3) presenting a complete solution to the design problem of an IAAD system, from both hardware and algorithmic perspectives, (4) discussing the use of additional ocular information, along with iris, for improving IAAD accuracy, and (5) discussing the current research challenges and providing recommendations for future research in IAAD. [ABSTRACT FROM AUTHOR]

Abstract: We correct a fundamental formula from paper “A Robust Real-Time Ellipse Detector” by Zhang and Liu published in journal “Pattern Recognition” in 2005. [ABSTRACT FROM AUTHOR]

• The first attempt to design a GEP-based codematrix generation algorithm. The individual structure of GEP allows the codematrix to be optimized in a much faster and more effective way. • The feature selection scheme is combined with the design of codematrix, to accomplish the feature selection and codematrix optimization simultaneously. • A greedy strategy-based adaptive optimization method to further improve the individual's quality to deal with hard classes by appending proper columns to the codematrix. The multi-class classification task is one of the most common tasks in machine learning. As a typical solution based on a partitioning strategy, Error-Correcting Output Codes (ECOC) can transform a multi-class classification problem into multiple binary classification problems. The key of ECOC is to construct an effective codematrix to represent a set of class decomposition schemes, which transforms a multiclass problem into a group of binary class problems. Consequently, the design of a fast and effective ECOC codematrix generation method is of great research significance and value for solving multi-class classification problems. In ECOC algorithms, the design of codematrix is treated as a combination problem between different code columns, in which the evolutionary algorithm shows a great advantage. Based on this consideration, the Gene Expression Programming (GEP) is applied to search for the codematrix with high performance because its expressive tree structure makes it well represent codematrcies for subsequent optimization operations. This paper proposes an adaptive ECOC algorithm based on Gene Expression Programming (GEP) and similarity measurement matrix, named GEP-ECOC. In our GEP, each individual represents a set of columns to form a random ECOC codematrix, which is optimized in the evolutionary process. Meanwhile, the crossover and mutation operations are modified to include a legality checking process to ensure that the generated codematrix satisfies the ECOC constraints. The GEP-based ECOC codematrix generation algorithm can quickly produce a codematrix with better performance, which ensures the efficiency of the algorithm to a certain extent. In addition, an adaptive algorithm based on a similarity measurement matrix is proposed to add new columns to the current codematrix, aiming to better handle hard classes. Our algorithm is compared with other algorithms on various data sets, and the experimental results confirm that our GEP-ECOC can balance the efficiency and performance of the algorithm and achieve higher performance. [ABSTRACT FROM AUTHOR]

Class imbalance problem commonly exists in multi-label classification (MLC) tasks. It has non-negligible impacts on the classifier performance and has drawn extensive attention in recent years. Borderline oversampling has been widely used in single-label learning as a competitive technique in dealing with class imbalance. Nevertheless, the borderline samples in multi-label data sets (MLDs) have not been studied. Hence, this paper deeply discussed the borderline samples in MLDs and found they have different neighboring relationships with class borders, which makes their roles different in the classifier training. For that, they are divided into two types named the self-borderline samples and the cross-borderline samples. Further, a novel MLDs resampling approach called Multi-Label Borderline Oversampling Technique (MLBOTE) is proposed for multi-label imbalanced learning. MLBOTE identifies three types of seed samples, including interior, self-borderline, and cross-borderline samples, and different oversampling mechanisms are designed for them, respectively. Meanwhile, it regards not only the minority classes but also the classes suffering from one-vs-rest imbalance as those in need of oversampling. Experiments on eight data sets with nine MLC algorithms and three base classifiers are carried out to compare MLBOTE with some state-of-art MLDs resampling techniques. The results show MLBOTE outperforms other methods in various scenarios. • A new borderline oversampling technique for multi-label imbalanced learning. • Defining self-borderline and cross-borderline samples in multi-label data sets. • Handling one-vs-rest imbalance in multi-label imbalanced learning. • Performing competitively in the experiments with C4.5, RBF kernel SVM and linear SVM. [ABSTRACT FROM AUTHOR]

Channel pruning is broadly recognized as an effective approach to obtain a small compact model through eliminating unimportant channels from a large cumbersome network. Contemporary methods typically perform iterative pruning procedure from the original over-parameterized model, which is both tedious and expensive especially when the pruning is aggressive. In this paper, we propose a simple yet effective channel pruning technique, termed network Pruning via rEsource rEalLocation (PEEL), to quickly produce a desired slim model with negligible cost. Specifically, PEEL first constructs a predefined backbone and then conducts resource reallocation on it to shift parameters from less informative layers to more important layers in one round, thus amplifying the positive effect of these informative layers. To demonstrate the effectiveness of PEEL , we perform extensive experiments on ImageNet with ResNet-18, ResNet-50, MobileNetV2, MobileNetV3-small and EfficientNet-B0. Experimental results show that structures uncovered by PEEL exhibit competitive performance with state-of-the-art pruning algorithms under various pruning settings. Encouraging results are also observed when applying PEEL to compress the semantic segmentation model. Our code is available at https://github.com/cardwing/Codes-for-PEEL. • Previous methods typically perform iterative pruning and are tedious and expensive. • A simple yet effective method is proposed to quickly produce a slim model with negligible cost. • Our method constructs a predefined backbone and conducts resource reallocation on it. • Resource reallocation shifts parameters from less informative layers to more important ones in one round. • Extensive experiments on ImageNet with various models validate the effectiveness. [ABSTRACT FROM AUTHOR]

• The establishment of a new mathematical model to realize dense light field reconstruction. • The innovative application of optical flow method. • Simple algorithm structure and relatively easy to implement. • Algorithm strong adaptability, good dense reconstruction was completed. Dense light field sampling is an important basis for refocusing, depth estimation and 3-D imaging. It is difficult to obtain high resolution dense light field with a large-scale camera array and expensive equipment. At the same time, the current storage devices and transmission bandwidth also limit this technology's post-processing and application. In order to effectively reconstruct the angle domain of the light field based on the sparse light field data, this paper analyzes the correlation and constraint relationship between the optical flow field and the motion field of multi-view images in the same scene, extends the traditional optical flow constraint equation of two-dimensional imaging to the optical flow constraint equation of four-dimensional light field, and establishes an effective mathematical model. The coordinate position of the original pixel in the new angle image is determined by coordinate search, and its intensity is reconstructed. The experimental results of multi-scene dense reconstruction show that the proposed method can reconstruct the texture, shadow and color information in the light field of a long-baseline scene with high quality. The quantitative evaluation results show that the algorithm can be applied to dense light field reconstruction of complex scenes. The algorithm in this paper is only suitable for the case of optical flow constraint in a linear light field, and the follow-up research will focus on the case of nonlinear optical flow constraint. [ABSTRACT FROM AUTHOR]

In this paper, a robust method is presented to perform word spotting in degraded handwritten and printed document images. A new sequence matching technique, called the Flexible Sequence Matching (FSM) algorithm, is introduced for this word spotting task. The FSM algorithm was specially designed to incorporate crucial characteristics of other sequence matching algorithms (especially Dynamic Time Warping (DTW), Subsequence DTW (SSDTW), Minimal Variance Matching (MVM) and Continuous Dynamic Programming (CDP)). Along with the characteristics of multiple matching (many-to-one and one-to-many), FSM is strongly capable of skipping existing outliers or noisy elements, regardless of their positions in the target signal. More precisely, in the domain of word spotting, FSM has the ability to retrieve complete words or words that contain only a part of the query. Furthermore, due to its adaptable skipping capability, FSM is less sensitive to local variation in the spelling of words and to local degradation effects within the word image. The multiple matching capability (many-to-one, one-to-many) of FSM helps it addressing the stretching effects of query and/or target images. Moreover, FSM is designed in such a way that with little modification, its architecture can be changed into the architecture of DTW, MVM, and SSDTW and to CDP-like techniques. To illustrate these possibilities for FSM applied to specific cases of word spotting, such as incorrect word segmentation and word-level local variations, we performed experiments on historical handwritten documents and also on historical printed document images. To demonstrate the capabilities of sub-sequence matching, of noise skipping, as well as the ability to work in a multilingual paradigm with local spelling variations, we have considered properly segmented lines of historical handwritten documents in different languages and improperly as well as properly segmented words in printed and handwritten historical documents. From the comparative experimental results shown in this paper, it can be clearly seen that FSM can be equivalent or better than most DTW-based word spotting techniques in the literature while providing at the same time more meaningful correspondences between elements. [ABSTRACT FROM AUTHOR]

Highlights • A generalized 2D multi-level thresholding criterion function is proved rigorously by mathematical induction method. • A multi-level thresholding scheme for a RGB color image is proposed. • PSO algorithm is applied to seek to optimal threshold values in a very reasonable computational time. • The segmented image is compared with the human segmentation from BSDS300 to evaluate the experiment results quantitatively and objectively. Abstract In this paper, we propose a multi-level thresholding model based on gray-level & local-average histogram (GLLA) and Tsallis–Havrda–Charvát entropy for RGB color image. We validate the multi-level thresholding formulation by using the mathematical induction method. We apply particle swarm optimization (PSO) algorithm to obtain the optimal threshold values for each component of a RGB image. By assigning the mean values from each thresholded class, we obtain three segmented component images independently. We conduct the experiments extensively on The Berkeley Segmentation Dataset and Benchmark (BSDS300) and calculate the average four performance indices (BDE, PRI, GCE and VOI) to show the effectiveness and reasonability of the proposed method. [ABSTRACT FROM AUTHOR]

Highlights • The proposed method extends grid-based DBSCAN scalable to higher-dimensional dataset. • Cluster forest is devised to alleviate redundancies in the merging step. • HyperGrid Bitmap is used to index non-empty grids for efficient neighbor grid queries. • Experiments show performance superiority of proposed method on real/synthetic data. Abstract DBSCAN is one of clustering algorithms which can report arbitrarily-shaped clusters and noises without requiring the number of clusters as a parameter (unlike the other clustering algorithms, k -means, for example). Because the running time of DBSCAN has quadratic order of growth, i.e. O (n 2), research studies on improving its performance have been received a considerable amount of attention for decades. Grid-based DBSCAN is a well-developed algorithm whose complexity is improved to O (n log n) in 2D space, while requiring Ω(n 4/3) to solve when dimension ≥ 3. However, we find that Grid-based DBSCAN suffers from two problems: neighbour explosion and redundancies in merging, which make the algorithms infeasible in high dimensional space. In this paper we first propose a novel algorithm called GDCF which utilizes bitmap indexing to support efficient neighbour grid queries. Second, based on the concept of union-find algorithm we devise a forest-like structure, called cluster forest, to alleviate the redundancies in the merging. Moreover, we find that running the cluster forest in different orders can lead to a different number of merging operations needed to perform in the merging step. We propose to perform the merging step in a uniform random order to optimize the number of merging operations. However, for high-density database, a bottleneck could be occurred, we further propose a low-density-first order to alleviate this bottleneck. The experiments resulted on both real-world and synthetic datasets demonstrate that the proposed algorithm outperforms the state-of-the-art exact/approximate DBSCAN and suggests a good scalability. [ABSTRACT FROM AUTHOR]

Highlights • Always considered graph edit distance (GED) is a metric if edit functions are a metric. • We discern between GED computed through edit path and graph bijection. • Triangle inequality of edit functions not necessary if GED defined by graph bijection. • Important: usually recognition ratio is maximized in non-metric edit functions. Abstract In the presentation of the graph edit distance in 1983 and other newer bibliography, authors state that it is necessary to apply the distance restrictions (non-negativity, identity of indiscernible elements, symmetry and triangle inequality) to each of the edit functions (insertion, deletion and substitution of nodes and edges) involved in the process of computing the graph edit distance to make the graph edit distance a true distance. Moreover, graph edit distance algorithms presented in the last three decades have been based on mapping the edit path that transforms a graph into the other one into a bijection of the graphs in which some null nodes have been added. In this paper, we show that the triangle inequality does not need to be imposed in each edit function if the graph edit distance is defined through an edit path; however, it is necessary if it is defined as a graph bijection. This is an important finding since the triangle inequality is the only restriction that relates different edit functions and concerns the process of tuning the edit functions given a specific application. Hence, on one hand, it would encourage research to define new algorithms based on the edit path instead of the graph bijection and, on the other hand, use edit functions without the restriction, for instance, that the sum of the costs of insertion and deletion of a pair of nodes has to be larger or equal than the cost of substituting them, which could increase the recognition ratio of a concrete application. [ABSTRACT FROM AUTHOR]

Highlights • Unlike common multi-label feature selection, the proposed method derives from different cognitive standpoint. • Feature selection process is directly done on multi-label data, and there is no need to data transformation. • The proposed method tries to find label-specific features which are the most discriminative features for each label. • Also, an extension of our method is presented which selects a pre-defined number of features. • The proposed method is appropriate to both numerical and nominal features. • The proposed method is effective and fast. Abstract In multi-label data, each instance is associated with a set of labels, instead of one label. Similar to single-label data, feature selection plays an important role in improving classification performance. In multi-label classification, each class label might be specified by some particular characteristics of its own which are called label-specific features. In this paper, a fast accurate filter-based feature selection method is exclusively designed for multi-label datasets to find label-specific features. It maps the features to a multi-dimensional space based on a filter method, and selects the most salient features with the help of Pareto-dominance concepts from multi-objective optimization domain. Our proposed method can be used as online feature selection that deals with problems in which features arrive sequentially while the number of data samples is fixed. In this method, the number of features to be selected is specified during the process of feature selection. However, sometimes it is desired to predefine the number of features. For this reason, an extension of the proposed method is presented to solve this problem. To prove the performance of the proposed methods, several experiments are conducted on some multi-label datasets and the results are compared to five well-established multi-label feature selection methods. The results show the superiority of the proposed methods in terms of different multi-label classification criteria and execution time. [ABSTRACT FROM AUTHOR]

Highlights • Almost all existing attribute weighting approaches to naive Bayes are class-independent. • We propose a new class-specific attribute weighting paradigm for naive Bayes. • The resulting model is called class-specific attribute weighted naive Bayes (CAWNB). • To learn CAWNB, we propose two gradient-based learning algorithms. • The experimental results validate the effectiveness of the proposed algorithms. Abstract Due to its easiness to construct and interpret, along with its good performance, naive Bayes (NB) is widely used to address classification problems in real-world applications. In order to alleviate its conditional independence assumption, a mass of attribute weighting approaches have been proposed. However, almost all these approaches assign each attribute a same (global) weight for all classes. In this paper, we call them the general attribute weighting and argue that for NB attribute weighting should be class-specific (class-dependent). Based on this premise, we propose a new paradigm for attribute weighting called the class-specific attribute weighting, which discriminatively assigns each attribute a specific weight for each class. We call the resulting model class-specific attribute weighted naive Bayes (CAWNB). CAWNB selects class-specific attribute weights to maximize the conditional log likelihood (CLL) objective function or minimize the mean squared error (MSE) objective function, and thus two different versions are created, which we denote as CAWNBCLL and CAWNBMSE, respectively. Extensive empirical studies show that CAWNBCLL and CAWNBMSE all obtain more satisfactory experimental results compared with NB and other existing state-of-the-art general attribute weighting approaches. We believe that for NB class-specific attribute weighting could be a more fine-grained attribute weighting approach than general attribute weighting. [ABSTRACT FROM AUTHOR]

Highlights • Optimization is an important issue in machine learning because many machine learning models are reformulated as optimization problems. Different kinds of machine learning algorithms mainly focus on minimizing their emiprical loss like deep learning, logisitic regression, and support vector machine. Because data is explosively growing, it is challenging to deal with a large-scale optimization problem. We propose a fast and most condition number free algorithm for train machine learning algorithms. This algorithm has several advantages. • Contrast to previous work which approximates Hessian matrix by sketched or subsampled Hessian directly, we use the sketched or subsampled Hessian matrix as preconditioner and get the direction vector by preconditioned conjugate gradient method. Accordingly, we propose a novel stochastic second-order algorithm called Preconditioned Newton Conjugate Gradient with Sketched Hessian (PNCG). This strategy makes our algorithm almost independent on the condition number. • We numerically demonstrate the effectiveness and robustness of our algorithms in widely used machine learning algorithm Ridge Logistic Regression on several real datasets with different condition number. Our algorithms show good performance compared with existing second order methods in all cases, especially when condition number is large. Abstract Optimization is an important issue in machine learning because many machine learning models are reformulated as optimization problems. Different kinds of machine learning algorithms mainly focus on minimizing their empirical loss like deep learning, logistic regression, and support vector machine. Because data is explosively growing, it is challenging to deal with a large-scale optimization problem. Recently, stochastic second-order methods have emerged to attract much attention due to their efficiency in each iteration. These methods show good performance on training machine learning algorithms like logistic regression and support vector machine. However, the computational complexity of existing stochastic second-order methods heavily depends on the condition number of the Hessian. In this paper, we propose a new Newton-like method called Preconditioned Newton Conjugate Gradient with Sketched Hessian (PNCG). The runtime complexity of PNCG is at most logarithmic in the condition number of the Hessian. PNCG exhibits advantages over existing subsampled Newton methods especially when the Hessian matrix in question is ill-conditioned. We also show that our method has good performance on training machine learning algorithm empirically. The results show consistent improvements in computational efficiency. [ABSTRACT FROM AUTHOR]

Highlights • For Alzheimer's disease (AD) diagnosis, we consider the integration of multi-modality imaging and genetic data which encode different level of knowledge. • With a focus on taking advantage of both phenotype and genotype information, a novel structured sparsity, defined by ℓ 1, p -norm (p > 1), regularized multiple kernel learning method is designed. • An efficient block coordinate descent algorithm applicable to any case with p > 1 was derived to solve the proposed formulation. Abstract Multimodal data fusion has shown great advantages in uncovering information that could be overlooked by using single modality. In this paper, we consider the integration of high-dimensional multi-modality imaging and genetic data for Alzheimer's disease (AD) diagnosis. With a focus on taking advantage of both phenotype and genotype information, a novel structured sparsity, defined by ℓ 1, p -norm (p > 1), regularized multiple kernel learning method is designed. Specifically, to facilitate structured feature selection and fusion from heterogeneous modalities and also capture feature-wise importance, we represent each feature with a distinct kernel as a basis, followed by grouping the kernels according to modalities. Then, an optimally combined kernel presentation of multimodal features is learned in a data-driven approach. Contrary to the Group Lasso (i.e., ℓ 2, 1 -norm penalty) which performs sparse group selection, the proposed regularizer enforced on kernel weights is to sparsely select concise feature set within each homogenous group and fuse the heterogeneous feature groups by taking advantage of dense norms. We have evaluated our method using data of subjects from Alzheimer's Disease Neuroimaging Initiative (ADNI) database. The effectiveness of the method is demonstrated by the clearly improved prediction diagnosis and also the discovered brain regions and SNPs relevant to AD. [ABSTRACT FROM AUTHOR]

Highlights • We give theoretical guarantees for the block sparse representation based classifier. • A RBSRC (robust block sparse representation based classifier) framework is given. • We devise an efficient half-quadratic optimization algorithm for RBSRC. • Using RBSRC as a general platform, we propose three robust classifiers. Abstract By exploiting the low-dimensional structure of high-dimensional data, sparse representation based classifiers (SRC) has recently attracted massive attention in pattern recognition. In this paper, we study a natural generalization of SRC, i.e., block sparse representation based classifiers (BSRC), which takes into account the block structure of the dictionary. Our contributions are two-fold: (1) we provide theoretical guarantees for BSRC and theoretically show that BSRC performs perfect classification for any test sample under both cases of independent subspaces and arbitrary subspaces settings; (2) we extend BSRC and propose three robust BSRC methods based on M-estimators originating in robust statistics. This is motivated by the observation that many previous representation based classifiers utilize the mean square error (MSE) criterion as the loss function, which is sensitive to outliers and complicated noises in reality. In contrast, M-estimators has shown much stronger robustness than MSE against gross corruptions. We demonstrate the efficacy of the proposed methods through experiments on both synthetic and real-world databases for block sparse recovery, handwritten digit recognition and robust face recognition. [ABSTRACT FROM AUTHOR]