Existing outlier detectors calculate outlier scores for data objects independently, ignoring the consistency between score similarity and object similarity. As a result, these detectors may produce inconsistent scores for similar objects, leading the scores of some normal objects to exceed some of outlier objects, increasing the possibility of misclassification. To address this issue, we first assume that similar objects should have similar scores. Then, based on this assumption, we propose neighborhood averaging, an outlier score post-processing technique to improve any single outlier detector, which is the first of its kind.

We hypothesize thatsimilar objects should have similar outlier scores. To the best of our knowledge, all existing outlier detectors calculate the outlier score for each object independently regardless of the outlier scores of the other objects. Therefore, they do not guarantee that similar objects have similar outlier scores. To verify our proposed hypothesis, we propose an outlier score post-processing technique for outlier detectors, called neighborhood averaging (NA) for neighborhood smoothing in outlier score space. It pays attention to objects and their neighbors and guarantees them to have more similar outlier scores than their original scores. Given an object and its outlier score from any outlier detector, NA modifies its outlier score by combining it with its$k$nearest neighbors' scores. We demonstrate the effectivity of NA by using the well-known$k$nearest neighbors ($k$-NN). Experimental results show that NA improves all 10 tested baseline detectors by 13% on average relative to the original results (from 0.70 to 0.79 AUC) evaluated on nine real-world datasets. Moreover, deep-learning-based detectors and even outlier detectors that are already based on$k$-NN are also improved. The experiments also show that in some applications, the choice of detector is no more significant when detectors are jointly used with NA. This may pose a challenge to the generally considered idea that the data model is the most important factor. We open our code on www.outlierNet.com for reproducibility.

Indoor motion planning challenges researchers because of the high density and unpredictability of moving obstacles. Classical algorithms work well in the case of static obstacles but suffer from collisions in the case of dense and dynamic obstacles. Recent reinforcement learning (RL) algorithms provide safe solutions for multiagent robotic motion planning systems. However, these algorithms face challenges in convergence: slow convergence speed and suboptimal converged result. Inspired by RL and representation learning, we introduced the ALN-DSAC: a hybrid motion planning algorithm where attention-based long short-term memory (LSTM) and novel data replay combine with discrete soft actor-critic (SAC). First, we implemented a discrete SAC algorithm, which is the SAC in the setting of discrete action space. Second, we optimized existing distance-based LSTM encoding by attention-based encoding to improve the data quality. Third, we introduced a novel data replay method by combining the online learning and offline learning to improve the efficacy of data replay. The convergence of our ALN-DSAC outperforms that of the trainable state of the arts. Evaluations demonstrate that our algorithm achieves nearly 100% success with less time to reach the goal in motion planning tasks when compared to the state of the arts. The test code is available at https://github.com/CHUENGMINCHOU/ALN-DSAC.

We present two new clustering algorithms called k-sets and k-swaps for data where each object is a set. First, we define the mean of the sets in a cluster, and the distance between a set and the mean. We then derive the k-sets algorithm from the principles of classical k-means so that it repeats the assignment and update steps until convergence. To the best of our knowledge, the proposed algorithm is the first k-means based algorithm for this kind of data. We adopt the idea also into random swap algorithm, which is a wrapper around the k-means that avoids local minima. This variant is called k-swaps. We show by experiments that this algorithm provides more accurate clustering results than k-medoids and other competitive methods.

Precision and recall are classical measures used in machine learning. However, they are based on exact matching. This results in binary classification where the predicted item is either a true or false positive despite inexact matching is often preferred in pattern recognition. To address this problem, we introduce soft variants of precision and recall based on application-specific similarity measure. 2022 Elsevier Ltd. All rights reserved.

Classification of interbeat interval time-series which fluctuates in an irregular and complex manner is very challenging. Typically, entropy methods are employed to quantify the complexity of the time-series for classifying. Traditional entropy methods focus on the frequency distribution of all the observations in a time-series. This requires a relatively long time-series with at least a couple of thousands of data points, which limits their usages in practical applications. The methods are also sensitive to the parameter settings. In this paper, we propose a conceptually new approach calledattention entropy, which pays attention only to the key observations. Instead of counting the frequency of all observations, it analyzes the frequency distribution of the intervals between the key observations in a time-series. Attention entropy does not need any parameter to tune, it is robust to the time-series length, and requires only linear time to compute. Experiments show that it outperforms fourteen state-of-the-art entropy methods evaluated by real-world datasets. It achieves average classification accuracy of AUC = 0.71 while the second-best method, multiscale entropy, achieves AUC = 0.62 when classifying four groups of people with a time-series length of 100.

Location-based games have been around since 2000 across various fields, including education, health, and entertainment. The main challenge facing such games is content generation. In contrast to normal games, content in location-based games is inherently dependent on location. The biggest challenge is the availability of the content globally. Other challenges include player engagement, enjoyable interactions with the real-world environment, safety, and customizability based on player performance and preference. While crowdsourcing has often been adopted as a tool for content creation, this approach requires quality control. Designing high-quality content requires detailed guidelines. In this paper, we introduce design principles for the creation of high-quality content that can survive for long periods of time. These principles are derived from ten years of experience running our in-house orienteering treasure-hunt game called O-Mopsi , which represents a case study in this paper. O-Mopsi allows players to visit pre-defined locations. The design principles are expected to be generalizable to other location-based games as well as to the creation of sightseeing tours more generally.

Solving large-scale clustering problems requires an efficient algorithm which can be implemented also in parallel. K-means would be suitable but it can lead to an inaccurate clustering result. To overcome this problem, we present a parallel version of random swap clustering algorithm. It combines the scalability of k-means with high clustering accuracy. The new clustering method is experimented on top of Java parallel streams and lambda expressions, which offer interesting execution time benefits. The method is applied to standard benchmark datasets, with a varying population size and distribution of managed records, dimensionality of data points and the number of clusters. The experimental results confirm that high quality clustering can be obtained by parallel random swap together with a high time efficiency.

BACKGROUND: Adaptor proteins play a key role in intercellular signal transduction, and dysfunctional adaptor proteins result in diseases. Understanding its structure is the first step to tackling the associated conditions, spurring ongoing interest in research into adaptor proteins with bioinformatics and computational biology. Our study aims to introduce a small, new, and superior model for protein classification, pushing the boundaries with new machine learning algorithms. RESULTS: We propose a novel transformer based model which includes convolutional block and fully connected layer. We input protein sequences from a database, extract PSSM features, then process it via our deep learning model. The proposed model is efficient and highly compact, achieving state-of-the-art performance in terms of area under the receiver operating characteristic curve, Matthew's Correlation Coefficient and Receiver Operating Characteristics curve. Despite merely 20 hidden nodes translating to approximately 1% of the complexity of previous best known methods, the proposed model is still superior in results and computational efficiency. CONCLUSIONS: The proposed model is the first transformer model used for recognizing adaptor protein, and outperforms all existing methods, having PSSM profiles as inputs that comprises convolutional blocks, transformer and fully connected layers for the use of classifying adaptor proteins.

Abstract We propose two new algorithms for clustering graphs and networks. The first, called K‑algorithm, is derived directly from the k-means algorithm. It applies similar iterative local optimization but without the need to calculate the means. It inherits the properties of k-means clustering in terms of both good local optimization capability and the tendency to get stuck at a local optimum. The second algorithm, called the M-algorithm, gradually improves on the results of the K-algorithm to find new and potentially better local optima. It repeatedly merges and splits random clusters and tunes the results with the K-algorithm. Both algorithms are general in the sense that they can be used with different cost functions. We consider the conductance cost function and also introduce two new cost functions, called inverse internal weight and mean internal weight. According to our experiments, the M-algorithm outperforms eight other state-of-the-art methods. We also perform a case study by analyzing clustering results of a disease co-occurrence network, which demonstrate the usefulness of the algorithms in an important real-life application.

Averaging GPS trajectories is needed in applications such as automatic generation of road network and finding representative movement patterns. We organized a challenge where participants submitted proposals to solve the averaging problem. In this paper, we review the proposals and evaluate their performance. We present a synthesis of the submitted methods and develop a new baseline composed of the well-performing components. The new baseline outperforms all existing averaging methods. All datasets, submissions and evaluations can be accessed on the competition webpage: http://cs.uef.fi/sipu/segments.

Traditional outlier detection methods create a model for data and then label as outliers for objects that deviate significantly from this model. However, when dat has many outliers, outliers also pollute the model. The model then becomes unreliable, thus rendering most outlier detectors to become ineffective. To solve this problem, we propose a mean-shift outlier detector. This detector employs a mean-shift technique to modify data and cancel the bias caused by the outliers. The mean-shift technique replaces every object by the mean of its k-nearest neighbors which essentially removes the effect of outliers before clustering without the need to know the outliers. In addition, it also detects outliers based on the distance shifted. Our experiments show that the proposed method works well regardless of the number of outliers in the data. This method outperforms all state-of-the-art methods tested, with both real-world numeric datasets as well as generated numeric and string datasets.

The efforts needed to solve travelling salesman problems (TSP) obviously depend on the problem size. However, also other factors can predict the difficulty of a given problem instance. We present a measure based on the minimum spanning tree (MST). The measure counts the number of knot points, which branch the tree into multiple sub-trees. We show by experiments that the more there are knots in the tree, the more difficult the problem instance is to solve by both humans and computers.

We present a new keywords extraction method that applies the semantic similarity among the frequent words on the web page along with the distribution of POS tags. We apply hierarchical clustering to cluster the semantically similar words that have more coverage of the content of the web page. Our method shows better performance than CL-Rank and other existing methodologies.

In this paper, we study what are the most important factors that deteriorate the performance of the k-means algorithm, and how much this deterioration can be overcome either by using a better initialization technique, or by repeating (restarting) the algorithm. Our main finding is that when the clusters overlap, k-means can be significantly improved using these two tricks. Simple furthest point heuristic (Maxmin) reduces the number of erroneous clusters from 15% to 6%, on average, with our clustering benchmark. Repeating the algorithm 100 times reduces it further down to 1%. This accuracy is more than enough for most pattern recognition applications. However, when the data has well separated clusters, the performance of k-means depends completely on the goodness of the initialization. Therefore, if high clustering accuracy is needed, a better algorithm should be used instead.

Density peaks is a popular clustering algorithm, used for many different applications, especially for non-spherical data. Although powerful, its use is limited by quadratic time complexity, which makes it slow for large datasets. In this work, we propose a fast density peaks algorithm that solves the time complexity problem. The proposed algorithm uses a fast and generic construction of approximate k-nearest neighbor graph both for density and for delta calculation. This approach maintains the generality of density peaks, which allows using it for all types of data, as long as a distance function is provided. For a dataset of size 100,000, our approach achieves a 91:1 speedup factor. The algorithm scales up for datasets up to 1 million in size, which could not be solved by the original algorithm at all. With the proposed method, time complexity is no longer a limiting factor of the density peaks clustering.

In Joensuu, Finland, a new bridge, Sirkkalansilta, was to be built. In this work, we study its effect on the working population's commuting traffic. We investigate, with the working population census data, the traffic flow conditions of without and with the new bridge using multi-agent traffic simulation. We also investigate the correlations of the bridges with regards to bridge closures. Actual hourly bridge usage data was collected by Joensuu city council after Sirkkalansilta was opened to traffic. We compare our simulation with the collected hourly bridge usage data to conclude on the feasibility of using multi-agent traffic simulations for real world application and propose how it can provide suggestions on future improvement.

Location-based games have been around already since 2000 but only recently when PokemonGo came to markets it became clear that they can reach wide popularity. In this article, we perform a literature-based analytical study of what kind of issues location-based game design faces, and how they can be solved. We study how to use and verify the location, the role of the games as exergames, use in education, and study technical and safety issues. As a case study, we present O-Mopsi game that combines physical activity with problem solving. It includes three challenges: (1) navigating to the next target, (2) deciding the order of targets, (3) physical movement. All of them are unavoidable and relevant. For guiding the players, we use three types of multimedia: images (targets and maps), sound (user guidance), and GPS (for positioning). We discuss motivational aspects, analysis of the playing, and content creation. The quality of experiences is reported based on playing in SciFest Science festivals during 2011--2016.

In many web applications, users query a place name, a photo name, and other entity names using search words that include alternate spellings, abbreviations, and variants that are similar, but not identical to the title associated with the desired entity. Given two titles, an effective similarity measure should be able to determine whether the titles represent the same entity or not. In this paper, we evaluate 21 measures with the aim of detecting the most appropriate measure for matching the titles. Results show that Soft-TFIDF performs the best.

Comparing two clustering results of a data set is a challenging task in cluster analysis. Many external validity measures have been proposed in the literature. A good measure should be invariant to the changes of data size, cluster size, and number of clusters. We give an overview of existing set matching indexes and analyze their properties. Set matching measures are based on matching clusters from two clusterings. We analyze the measures in three parts: 1) cluster similarity, 2) matching, and 3) overall measurement. Correction for chance is also investigated and we prove that normalized mutual information and variation of information are intrinsically corrected. We propose a new scheme of experiments based on synthetic data for evaluation of an external validity index. Accordingly, popular external indexes are evaluated and compared when applied to clusterings of different data size, cluster size, and number of clusters. The experiments show that set matching measures are clearly better than the other tested. Based on the analytical comparisons, we introduce a new index called Pair Sets Index (PSI).

In this paper, we propose a noise reduced tone mapping method based on information content weights, where the perceptually unimportant pixels are smoothed during the decomposition in two steps. First, a saliency-based information content weight is introduced to give high fidelity to the data term based on the ratio of the local pixel power and the overall noise power in the base layer decomposition. Then, the detail layer is subtracted using the mutual information-based information content weight from the original image luminance and the clean base layer. Experiments show the effectiveness of the proposed method in the improvements of both signal-to-noise ratio and visual quality.

Abstract: Our goal is to give recommendations for mobile users about interesting places around his current location. The only input is the user, location and time. In this work, we study whether the social network of the user can be utilized for improving recommendations. We will answer the following two questions: (1) can we measure user similarity based on their Facebook profile and location history, (2) do these imply usefulness for the recommendations. 1

Abstract: A web page typically contains a blend of information. For a particular user, only informative data such as main content and representative images are considered useful, while non-informative data such as advertisements and navigational banners are not. In this work, we focus on selecting a representative image that would best represent the content of a web page. Existing techniques rely on prior knowledge of website specific templates and on text body. We extract all images, analyze and rank them according to their features and functionality in the web page. We select the highest scored image as the representative image. Our method is fully automated, template independent, and not limited to a certain type of web pages. 1

Abstract: We attack the problem of trajectory similarity by approximating the trajectories using a geographical grid based on the MGRS 2D coordinate system. We propose a spatial similarity measure which is computationally feasible for big data collections. The proposed measure is based on cell matching with a similarity metric drawn from Jaccard index. We equip the proposed method with interpolation and dilation to overcome the problems missing data and different sampling frequencies when comparing two trajectories. The proposed measure is implemented online in the framework of Mopsia. acs.uef.fi/mopsi 1

Clustering algorithm and cluster validity are two highly correlated parts in cluster analysis. In this paper, a novel idea for cluster validity and a clustering algorithm based on the validity index are introduced. A Centroid Ratio is firstly introduced to compare two clustering results. This centroid ratio is then used in prototype-based clustering by introducing a Pairwise Random Swap clustering algorithm to avoid the local optimum problem of k -means. The swap strategy in the algorithm alternates between simple perturbation to the solution and convergence toward the nearest optimum by k -means. The centroid ratio is shown to be highly correlated to the mean square error (MSE) and other external indices. Moreover, it is fast and simple to calculate. An empirical study of several different datasets indicates that the proposed algorithm works more efficiently than Random Swap, Deterministic Random Swap, Repeated k-means or k-means++. The algorithm is successfully applied to document clustering and color image quantization as well.

Data about people movement is nowadays easy to collect by the GPS technology embedded in smartphones. GPS routes provide information about position, time and speed, but further conclusion requires either prior information or data analysis. We propose a method to detect the movement type by segmentat

Systems that aim to predict user preferences and give recommendations are now commonly used in many systems such as online shops, social websites, and tourist guides. In this paper, we present a context aware personalized recommendation system on web and mobile, which recommends relevant location-ba

Enormous amounts of GPS trajectories, which record users' spatial and temporal information, are collected by geo-positioning mobile phones in recent years. The massive volumes of trajectory data bring about heavy burdens for both network transmission and data storage. To overcome these difficulties, a number of compression algorithms have been proposed by reducing the number of points in the trajectory data. But these algorithms lack a rigorous investigation on how to encode the reduced trajectories. In this paper, we propose an algorithm that optimizes both the trajectory simplification and the coding procedure using the quantized data. The underlying algorithm is also compared with the existing methods across 640 trajectories from Microsoft Geolife dataset using synchronous Euclidean distance (SED) as the error metrics. Experimental results show that the proposed method saves 60% of compression cost against the current state of the art compression algorithms.

In this paper, we present a novel system for joint speaker identification and speech separation. For speaker identification a single-channel speaker identification algorithm is proposed which provides an estimate of signal-to-signal ratio (SSR) as a by-product. For speech separation, we propose a sinusoidal model-based algorithm. The speech separation algorithm consists of a double-talk/single-talk detector followed by a minimum mean square error estimator of sinusoidal parameters for finding optimal codevectors from pre-trained speaker codebooks. In evaluating the proposed system, we start from a situation where we have prior information of codebook indices, speaker identities and SSR-level, and then, by relaxing these assumptions one by one, we demonstrate the efficiency of the proposed fully blind system. In contrast to previous studies that mostly focus on automatic speech recognition (ASR) accuracy, here, we report the objective and subjective results as well. The results show that the proposed system performs as well as the best of the state-of-the-art in terms of perceived quality while its performance in terms of speaker identification and automatic speech recognition results are generally lower. It outperforms the state-of-the-art in terms of intelligibility showing that the ASR results are not conclusive. The proposed method achieves on average, 52.3% ASR accuracy, 41.2 points in MUSHRA and 85.9% in speech intelligibility.

Recent advances in geopositioning mobile phones have made it possible for users to collect a large number of GPS trajectories by recording their location information. However, these mobile phones with built-in GPS devices usually record far more data than needed, which brings about both heavy data storage and a computationally expensive burden in the rendering process for a Web browser. To address this practical problem, we present a fast polygonal approximation algorithm in 2-D space for the GPS trajectory simplification under the so-called integral square synchronous distance error criterion in a linear time complexity. The underlying algorithm is designed and implemented using a bottom-up multiresolution method, where the input of polygonal approximation in the coarser resolution is the polygonal curve achieved in the finer resolution. For each resolution (map scale), priority-queue structure is exploited in graph construction to construct the initialized approximated curve. Once the polygonal curve is initialized, two fine-tune algorithms are employed in order to achieve the desirable quality level. Experimental results validated that the proposed algorithm is fast and achieves a better approximation result than the existing competitive methods.

Best language recognition performance is commonly obtained by fusing the scores of several heterogeneous systems. Regardless the fusion approach, it is assumed that different systems may contribute complementary information, either because they are developed on different datasets, or because they use different features or different modeling approaches. Most authors apply fusion as a final resource for improving performance based on an existing set of systems. Though relative performance gains decrease as larger sets of systems are considered, best performance is usually attained by fusing all the available systems, which may lead to high computational costs. In this paper, we aim to discover which technologies combine the best through fusion and to analyse the factors (data, features, modeling methodologies, etc.) that may explain such a good performance. Results are presented and discussed for a number of systems provided by the participating sites and the organizing team of the Albayzin 2010 Language Recognition Evaluation. We hope the conclusions of this work help research groups make better decisions in developing language recognition technology.

Traditional approach to clustering is to fit a model (partition or prototypes) for the given data. We propose a completely opposite approach by fitting the data into a given clustering model that is optimal for similar pathological data of equal size and dimensions. We then perform inverse transform from this synthetic data back to the original data while refining the optimal clustering structure during the process. The key idea is that we do not need to find optimal global allocation of the prototypes. Instead, we only need to perform local fine-tuning of the clustering prototypes during the transformation in order to preserve the already optimal clustering structure.

Expectation maximization (EM) algorithm, being a gradient ascent algorithm depends highly on the initialization. Repeating EM multiple times with different initial solutions and taking the best result is used to attack this problem. However, the solution space is searched inefficiently in Repeated EM, because after each restart it can take a long time to converge without any guarantee that it leads to an improved solution. A random swap EM algorithm utilizes random swap strategy to improve the problem in a more efficient way. In this paper, a theoretical and experimental comparison between RSEM and REM is conducted. Based on GMM estimation theory, it is proved that RSEM reaches the optimal result faster than REM with high probability. It is also shown experimentally that RSEM speeds up REM from 9% to 63%. A study in color-texture images demonstrates an application of EM algorithms in a segmentation task.

Filtering of raster map images or more general class of palette-indexed images is considered as a discrete denoising problem with finite color output. Statistical features of local context are used to avoid damages of some specific but frequently occurring contexts caused by conventional filters. Several context-based approaches have been developed using either fixed context templates or context tree modeling. However, these algorithms fail to reveal the local geometrical structures when the underlying contexts are also contaminated. To address this problem, we propose a novel context-based voting method to identify the possible noisy pixels, which are excluded in the context selection and optimization. Experimental results show that the proposed context based filtering outperforms all other existing filters both for impulsive and Gaussian additive noise.

Ghosting artifacts are usually caused by moving object when composing a high dynamic range image from multiple differently exposed conventional images. In this paper, a robust de-ghosting algorithm is proposed based on a double-credit intensity mapping function (IMF) and an adaptive threshold model derived from statistical training. The double-credit IMF is estimated using both pixel intensity distribution and spatial correlation. A statistical threshold model is trained from the image database, and the key parameters are determined on the fly with variance vector calculated during the IMF estimation to adapt to different scenarios. Optimal bidirectional comparison is used for further improves the detection accuracy. The experiments show the effectiveness of the proposed de-ghosting method.

Most of the single-channel speech separation (SCSS) systems use the short-time Fourier transform as their parametric features. Recent studies have shown that employing sinusoidal features for the SCSS application results in a high perceived speech quality. In this paper, we make a systematic study on automatic speech recognition results for a SCSS system that uses sinusoidal features composed of amplitude and frequency. We compare the speech recognition results with those already reported by other participants in the single-channel speech separation and recognition challenge. Our results show that a newly proposed system achieves an overall recognition accuracy of 52.3%, ranges at the median over all other participants in the challenge. Index Terms: sinusoidal modeling, single-channel speech separation and recognition challenge.

External validity measures in cluster analysis evaluate how well the clustering results match to a prior knowledge about the data. However, it is always intractable to get the prior knowledge in the practical problem of unsupervised learning, such as cluster analysis. In this paper, we extend the external validity measures for both hard and soft partitions by a resampling method, where no prior information is needed. To lighten the time burden caused by the resampling method, we incorporate two approaches into the proposed method: (i) extending external validity measures for soft partitions in a computational time of O(M2N); (ii) an efficient sub-sampling method with time complexity of O(N). The proposed method is then applied and reviewed in determining the number of clusters for the problem of unsupervised learning, cluster analysis. Experimental results has demonstrated the proposed method is very effective in solving the number of clusters.

Filtering of raster map images is chosen as a case study of a more general class of palette-indexed images for the denoising problem of images with a discrete number of output colors. Statistical features of local context are analyzed to avoid damage to pixel-level patterns, which is frequently caused by conventional filters. We apply a universal statistical filter using context-tree modeling via a selective context expansion capturing those pixel combinations that are present in the image. The selective context expansion makes it possible to use a much larger spatial neighborhood, with a feasible time and memory complexity, than fixed-size templates. We improve the existing context-tree approaches in two aspects: Firstly, in order to circumvent the context contamination problem, a context-merging strategy is applied where multiple similar contexts are considered in the conditional probability estimation procedure. Secondly, we study a specific continuous-input-finite-output problem in which the map images are corrupted by additive Gaussian noise. Performance comparisons with competitive filters demonstrate that the proposed algorithm provides robust noise filtering performance and good structure preservation in all test cases without any a priori information on the statistical properties of the noise.

In this paper, we propose a closed loop system to improve the performance of single-channel speech separation in a speaker independent scenario. The system is composed of two interconnected blocks: a separation block and a speaker identification block. The improvement is accomplished by incorporating the speaker identities found by the speaker identification block as additional information for the separation block, which converts the speaker-independent separation problem to a speaker-dependent one where the speaker codebooks are known. Simulation results show that the closed loop system enhances the quality of the separated output signals. To assess the improvements, the results are reported in terms of PESQ for both target and masked signals.

Gaussian selection is a technique applied in the GMM-UBM framework to accelerate score calculation. We have recently introduced a novel Gaussian selection method known as sorted GMM (SGMM). SGMM uses scalar-indexing of the universal background model mean vectors to achieve fast search of the top-scoring Gaussians. In the present work we extend this method by using 2-dimensional indexing, which leads to simultaneous frame and Gaussian selection. Our results on the NIST 2002 speaker recognition evaluation corpus indicate that both the 1- and 2- dimensional SGMMs outperform frame decimation and temporal tracking of top-scoring Gaussians by a wide margin (in terms of Gaussian computations relative to GMM-UBM as baseline).

Vector map compression can be solved by incorporating both data reduction (polygonal approximation) and quantization of the prediction errors, which is the so-called dynamic quantization. This straightforward solution is to calculate all the rate-distortion curves with respect to each of the quantization levels such that the best quantizer is the lower envelope of the set of curves. But computing an entire set of rate-distortion curves is computationally expensive. To solve this problem, we propose a fast algorithm first estimates an optimal Lagrangian parameter λ for each given quantization level l and thus only one rate-distortion curve is achievable for constructing the optimal quantizer of prediction errors. An experimental result demonstrates that proposed algorithm reduces the computational complexity significantly without compromising its rate-distortion performance.

In high dynamic range (HDR) imaging, two essential problems are to compose HDR image from conventional image set without any prior information about their exposures, and to access the synthesis result. To solve these problems, we first develop an exposure ratio estimation algorithm based on intensity mapping function (IMF). Then, we introduce an HDR image comparison method to verify whether two HDR images are from the same scene by using their log histogram similarity. Even though the images carrying the same information, their similarity cannot be detected by pixel-wise comparisons. We name such a pair of HDR images as near-identical images. According to experiments, our detection method is able to identify near-identical HDR images effectively, and our synthesis algorithm is able to recover the correct exposure ratios and compose near-identical HDR images.

Filtering of raster map images or more general class of palette-indexed images can be considered as a discrete denoising problem with finite color output. Statistical features of local context are used to avoid damages of some specific but frequently occurring contexts caused by conventional filters. Several context-based approaches have been developed using either fixed context templates or context tree modeling. However, these algorithms are limited to deal with image with finite color input. In this paper, we further extended the method to a specific continuous-input-finite-output problem, in which the map images are corrupted by additive Gaussian noise instead. This extended method iteratively conducts a fusion procedure based on the probability distribution of pixels' intensity in RGB space and their conditional probabilities in the local contexts. Experimental results have demonstrated that the proposed algorithm is very efficient in filtering both impulsive and additive Gaussian noise.

Location-based search engine is an alternative approach for information retrieval to traditional location-based services based on fixed databases. This is a relatively new concept that aims at utilizing the location of user but without restricting to any fixed location-based service. In this paper, we outline a prototype solution for multimedia mobile phones based on web search, ad-hoc georeferencing, prefix tree structure and gazetteer. Experimental results show that the proposed solution finds search results that have higher or equal mean relevance than that of the GoogleMaps and YellowPages.

Quantization plays an important part in lossy vector map compression, for which the existing solutions are based on either a fixed size open-loop codebook, or a simple uniform quantization. In this paper, we proposed an entropy-constrained vector quantization to optimize both the structure and size of the codebook at the same time using a closed-loop approach. In order to lower the distortion to a desirable level, we exploit two-level design strategy, where the vector quantization codebook is designed only for most common vectors and the remaining (outlier) vectors are coded by uniform quantization.

In this paper, we consider speaker identification for the co-channel scenario in which speech mixture from speakers is recorded by one microphone only. The goal is to identify both of the speakers from their mixed signal. High recognition accuracies have already been reported when an accurately estimated signal-to-signal ratio (SSR) is available. In this paper, we approach the problem without estimating SSR. We show that a simple method based on fusion of adapted Gaussian mixture models and Kullback-Leibler divergence calculated between models, achieves an accuracy of 97% and 93% when the two target speakers enlisted as three and two most probable speakers, respectively.

This paper describes a novel approach to improve monoaural speaker identification where two speakers are present in a single-microphone recording. The goal is to identify both of the underlying speakers in the given mixture. The proposed approach is composed of a double-talk detector (DTD) as a preprocessor and speaker identification back-end. We demonstrate that including the double-talk detector improves the speaker identification accuracy. Experiments on GRID corpus show that including the DTD improves average recognition accuracy from 96.53% to 97.43%.

Gaussian mixture model - universal background model (GMM-UBM) is a standard reference classifier in speaker verification. We have proposed a simplified model using vector quantization (VQ-UBM). In this study, we extensively compare these two classifiers on NIST 2005, 2006 and 2008 SRE corpora, while having a standard discriminative classifier (GLDS-SVM) as a reference point. We focus on parameter setting for N-top scoring, model order, and performance for different amounts of training data. The most interesting result, against a general belief, is that GMM-UBM yields better results for short segments whereas VQ-UBM is good for long utterances. The results also suggest that maximum likelihood training of the UBM is sub-optimal, and hence, alternative ways to train the UBM should be considered.

Raster map image is an important set of color images with similar patterns and textures presented in a limited number of colors. Manipulating this class of color images using conventional image filters may lead to a severe over-filtering problem, by which important details structures are over eliminated or degraded. Even if the statistical based algorithms have been recognized as a set of most efficient filters, their exponentially high memory consumption and computational cost can make them intractable in practice. To solve this operational difficulty, this work proposed a novel multi-layer image filtering approach transforming map image filtering into binary domain. It consists of three intuitive image operators: layer decomposition, binary image filters and layer merging. Experimental results demonstrated that the new proposed approach is very efficient for filtering of raster map image.

The expectation-maximization (EM) algorithm is a popular tool in estimating model parameters, especially mixture models. As the EM algorithm is a hill-climbing approach, problems such as local maxima, plateau and ridges may appear. In the case of mixture models, these problems involve the initialization of the algorithm and the structure of the data set. We propose a random swap EM algorithm (RSEM) to overcome these problems in Gaussian mixture models. Random swaps are repeatedly performed in our method, which can break the configuration of the local maxima and other problems. Compared to the strategies in other methods, the proposed algorithm has relative improvements on log-likelihood value in most cases and less variance than other algorithms. We also apply RSEM to the image segmentation problem.

We propose a local search algorithm for clustering based on deterministic variants of cluster swapping. Within a given time limit, the new method finds the correct clustering more efficiently than existing ones. The algorithm is simple to implement, which makes it useful for practitioners.

We formulate probabilistic clustering method based on a sequence of random swaps of cluster centroids. We show that the algorithm has linear dependency on the number of data vectors, quadratic on the number of clusters, and inverse dependency on the dimensionality. Each halving of the probability of failure (e.g. from 1% to 0.5%) is achieved at the cost of only linear increase in the processing time.

Clustering time-series data poses problems, which do not exist in traditional clustering in Euclidean space. Specifically, cluster prototype needs to be calculated, where common solution is to use cluster medoid. In this work, we define an optimal prototype as an optimization problem and propose a local search solution to it. We experimentally compare different time-series clustering methods and find out that the proposed prototype with agglomerative clustering followed by k-means algorithm provides best clustering accuracy.

The main challenge of cluster analysis is that the number of clusters or the number of model parameters is seldom known, and it must therefore be determined before clustering. Bayesian Information Criterion (BIC) often serves as a statistical criterion for model selection, which can also be used in solving model-based clustering problems, in particular for determining the number of clusters. Conventionally, a correct number of clusters can be identified as the first decisive local maximum of BIC; however, this is intractable due to the overtraining problem and inefficiency of clustering algorithms. To circumvent this limitation, we proposed a novel method for identifying the number of clusters by detecting the knee point of the resulting BIC curve instead. Experiments demonstrated that the proposed method is able to detect the correct number of clusters more robustly and accurately than the conventional approach.

Maximum a posteriori adapted Gaussian mixture model (GMM-MAP) is widely used in speaker verification. GMMs have three sets of parameters to be adapted: means, covariances, and weights. However, practice has shown that it is sufficient to adapt the means only. Motivated by this, we formulate maximum a posteriori vector quantization (VQ-MAP) procedure which stores and adapts the mean vectors (centroids) only. Experiments on the NIST 2001 and NIST 2006 corpora indicate that VQ-MAP gives comparable accuracy with GMM-MAP with simpler implementation and faster adaptation.

This paper describes the cascaded recursive least square-least mean square (RLS-LMS) prediction, which is part of the recently published MPEG-4 Audio Lossless Coding international standard. The predictor consists of cascaded stages of simple linear predictors, with the prediction error at the output of one stage passed to the next stage as the input signal. A linear combiner adds up the intermediate estimates at the output of each prediction stage to give a final estimate of the RLS-LMS predictor. In the RLS-LMS predictor, the first prediction stage is a simple first-order predictor with a fixed coefficient value 1. The second prediction stage uses the recursive least square algorithm to adaptively update the predictor coefficients. The subsequent prediction stages use the normalized least mean square algorithm to update the predictor coefficients. The coefficients of the linear combiner are then updated using the sign-sign least mean square algorithm. For stereo audio signals, the RLS-LMS predictor uses both intrachannel prediction and interchannel prediction, which results in a 3% improvement in compression ratio over using only the intrachannel prediction. Through extensive tests, the MPEG-4 Audio Lossless coder using the RLS-LMS predictor has demonstrated a compression ratio that is on par with the best lossless audio coders in the field. In this paper, the structure of the RLS-LMS predictor is described in detail, and the optimal predictor configuration is studied through various experiments.

Significant lossless compression results of color map images have been obtained by dividing the color maps into layers and by compressing the binary layers separately using an optimized context tree model that exploits interlayer dependencies. Even though the use of a binary alphabet simplifies the context tree construction and exploits spatial dependencies efficiently, it is expected that an equivalent or better result would be obtained by operating directly on the color image without layer separation. In this paper, we extend the previous context-tree-based method to operate on color values instead of binary layers. We first generate an n-ary context tree by constructing a complete tree up to a predefined depth, and then prune out nodes that do not provide compression improvements. Experiments show that the proposed method outperforms existing methods for a large set of different color map images.

Best lossless compression results of color map images have been obtained by dividing the color maps into layers, and by compressing the binary layers separately by using an optimized context tree model that exploits inter-layer dependencies. In this paper, we extend the previous context tree based method to operate on color values instead of the binary layers. We generate an n-ary context tree by constructing a complete tree up to a predefined depth, and then prune out nodes that do not provide improvement in compression to generate sub-optimal context tree with incomplete structure. Experiments show that the proposed method outperforms existing methods for a large set of different color map images

A new MPEG-4 standard for lossless audio coding is going to be published in 2006. This coming international standard consists of two parts: the transform-domain scalable to lossless coding (SLS), and the time-domain audio lossless coding (ALS). In ALS, linear prediction is used to compress the dynamic ranges of the input audio signal. The prediction residual is coded by an entropy coder with either Rice code or arithmetic code. There are two prediction modes in ALS: linear predictive coding (LPC) and cascaded RLS-LMS. As the developer of the RLS-LMS prediction, we present this technology in this paper. In RLS-LMS prediction, the input audio samples go through the cascaded DPCM, RLS, and LMS predictors, whose output predictions are linearly combined to generate a prediction for the current input sample. Through MPLG testings, it has been found that ALS with RLS-LMS prediction provides the best lossless compression ratio compared with SLS, ALS with LPC, and several non-MPEG codecs

A two-stage lossless compression method based on a binary tree representation of colors and on context-based arithmetic coding has been recently proposed. We propose two improvements to this method: merge-based color quantization instead of the original splitting strategy, and context tree modeling optimized for each layer separately. The proposed method achieves better compression performance and a better reproduction quality in the color progression.

We propose a fast agglomerative clustering method using an approximate nearest neighbor graph for reducing the number of distance calculations. The time complexity of the algorithm is improved from O(tauN2) to O(tauNlogN) at the cost of a slight increase in distortion; here, tau denotes the number of nearest neighbor updates required at each iteration. According to the experiments, a relatively small neighborhood size is sufficient to maintain the quality close to that of the full search.

In speaker identification, most of the computation originates from the distance or likelihood computations between the feature vectors of the unknown speaker and the models in the database. The identification time depends on the number of feature vectors, their dimensionality, the complexity of the speaker models and the number of speakers. In this paper, we concentrate on optimizing vector quantization (VQ) based speaker identification. We reduce the number of test vectors by pre-quantizing the test sequence prior to matching, and the number of speakers by pruning out unlikely speakers during the identification process. The best variants are then generalized to Gaussian mixture model (GMM) based modeling. We apply the algorithms also to efficient cohort set search for score normalization in speaker verification. We obtain a speed-up factor of 16:1 in the case of VQ-based modeling with minor degradation in the identification accuracy, and 34:1 in the case of GMM-based modeling. An equal error rate of 7% can be reached in 0.84 s on average when the length of test utterance is 30.4 s.

Optimal context quantizers for minimum conditional entropy can be constructed by dynamic programming in the probability simplex space. The main difficulty, operationally, is the resulting complex quantizer mapping function in the context space, in which the conditional entropy coding is conducted. To overcome this difficulty, we propose new algorithms for designing context quantizers in the context space based on the multiclass Fisher discriminant and the kernel Fisher discriminant (KFD). In particular, the KFD can describe linearly nonseparable quantizer cells by projecting input context vectors onto a high-dimensional curve, in which these cells become better separable. The new algorithms outperform the previous linear Fisher discriminant method for context quantization. They approach the minimum empirical conditional entropy context quantizer designed in the probability simplex space, but with a practical implementation that employs a simple scalar quantizer mapping function rather than a large lookup table.

We present an algorithm for generating a mixture model from data set by performing a single pass over the data. The method is applicable when the entire data is not available at the same time in the main memory. We use Gaussian mixture model but the algorithm can be adapted to other types of models, too. We also outline a post processing method, which can iteratively reduce the size of the model obtained by the single-pass algorithm. This results in a model with fewer components, but with approximately the same representation accuracy than the result of the original model from the single-pass algorithm.

Recently a new convexity measure has been proposed based on approximation of input contour with a convex polygon. In this paper, an optimal algorithm is proposed for the construction of the convex polygon. The introduced algorithm provides exact value of the convexity measure and can therefore be used for evaluation of faster heuristic algorithms.

Polygonal approximation of closed contours with minimum number of segments can be found by applying optimal algorithm for the open curves repeated for all possible starting points, or by using heuristic adjustment of the starting point. A better approach, however, is to extend the optimal algorithm from open to closed curves by extending the search space circularly. In this paper, we adopt this idea to the case of min-# problem. The proposed algorithm finds the optimal solution in less than 1.5 times of the time required by the open curve.

We propose a method for compressing color map images by context tree modeling and arithmetic coding. We consider multicomponent map images with semantic layer separation and images that are divided into binary layers by color separation. The key issue in the compression method is the utilization of interlayer correlations, and to solve the optimal ordering of the layers. The interlayer dependencies are acquired by optimizing the context tree for every pair of image layers. The resulting cost matrix of the interlayer dependencies is considered as a directed spanning tree problem and solved by an algorithm based on the Edmond's algorithm for optimum branching and by the optimal selection and removal of the background color. The proposed method gives results 50% better than JBIG and 25% better than a single-layer context tree modeling.

We present a new method for performing vector quantization of binary vectors. The proposed method varies the distance metric and updates the centroids in an optimal manner regarding the current metric. The corresponding centroids change from "soft", allowing variables of codevectors to have values between zero and one, to hard, pure binary codevectors.

We propose optimal and near-optimal algorithm for multiresolution polygonal approximation of digital curves. The solution with minimum number of segments is constructed as the shortest path in a weighted graph where the weights are recursively defined as the number of segments of all embedded layers.

We propose a method for filtering raster map images by context tree modeling. This is a two-pass method. At the first pass, the filter utilizes statistical information about the image spatial structure and stores the statistics in a tree structure. At the second pass, these statistics are used in actual filtering to calculate the probability of the current pixel in its neighborhood. We test this method on a set of map images. We use different noise models to evaluate the performance of the proposed filter. Finally we compare the performance results for our method with the vector median filter. The proposed method does not destroy the object borders and outperforms the vector median filter for a moderate level of noise.

K-means clustering utilizes an iterative procedure that converges to local minima. This local minimum is highly sensitive to the selected initial partition for the K-means clustering. To overcome this difficulty, we present a heuristic K-means clustering algorithm based on a scheme for selecting a suboptimal initial partition. The selected initial partition is estimated by applying dynamic programming in a nonlinear principal direction. In other words, an optimal partition of data samples in the kernel principal direction is selected as the initial partition for the K-means clustering. Experiment results show that the proposed algorithm outperforms the PCA based K-means clustering algorithm and the kd-tree based K-means clustering algorithm respectively.

In speaker identification, most of the computation originates from distance or likelihood computations between the feature vectors of the unknown speaker and the models in the database. The identification time depends on the number of feature vectors, their dimensionality, the complexity of the speaker models and the number of speakers. In this paper, we focus on optimizing vector quantization (VQ) based speaker identification. We reduce the number of test vectors by pre-quantizing the test sequence prior to matching, and the number of speakers by pruning out unlikely speakers during the identification process. The best variants are then generalized to Gaussian mixture model (GMM) based modeling also. We obtain a speed-up factor of 16:1 with VQ-based system, and 34:1 with GMM-based system with a minor degradation in the identification error rate.

Cohort normalization is a method for normalizing the scores in speaker verification in order to reduce undesirable variation arising from acoustically mismatched conditions. A particular form of cohort normalization, unconstrained cohort normalization (UCN) is addressed in this study. The UCN method has been shown to give excellent results but its major drawback is the huge computational load arising from the search of the cohort speakers. In this paper, we propose a fast cohort search algorithm, that quantizes the test vector sequence and uses the quantized data for both impostor and claimant scoring. Results on the NIST-1999 corpus show a speed-up factor of 23:1 compared to full search. Furthermore, the equal error rates are decreased from those of the full search.

The compression of color map images by context tree modeling and arithmetic coding was studied. The main aim of this approach is to utilize the correlations between the color layers of the image and to solve the optimal order of the layers as an optimum branching problem. The acquiring of the inter-layer dependencies is done by optimization of the context tree for every pair image layer. The cost matrix of the inter-layer dependencies is then solved by Edmond's algorithm for optimum branching.

Search for nearest neighbor is the main source of computation in most clustering algorithms. We propose the use of nearest neighbor graph for reducing the number of candidates. The number of distance calculations per search can be reduced from O(N) to O(k) or where N is the number of clusters, and k is the number of neighbors in the graph. We apply the proposed scheme within agglomerative clustering algorithm known as the PNN algorithm.

Fast algorithm for joint near-optimal approximation of multiple polygonal curves is proposed. It is based on iterative reduced-search dynamic programming introduced earlier for the min-/spl epsiv/ problem of a single polygonal curve. The proposed algorithm jointly optimizes the number of line segments allocated to the different individual curves, and the approximation of the curves by the given number of segments. Trade-off between time and optimality is controlled by the breadth of (the search, and by the numbers of iterations applied.

In this work, we describe a speaker identification system that uses multiple supplementary information sources for computing a combined match score for the unknown speaker. Each speaker profile in the database consists of multiple feature vector sets that can vary in their scale, dimensionality, and the number of vectors. The evidence from a given feature set is weighted by its reliability that is set in a priori fashion. The confidence of the identification result is also estimated. The system is evaluated with a corpus of 110 Finnish speakers. The evaluated feature sets include mel-cepstrum, LPC-cepstrum, dynamic cepstrum, long-term averaged spectrum of /A/ vowel, and F0.

We consider compression of multi-component map images by context modeling and arithmetic coding. We apply an optimized multi-level context tree for modeling the individual binary layers. The context pixels can be located within a search area in the current layer, or in a reference layer that has already been compressed. The binary layers are compressed using an optimized processing sequence that makes maximal utilization of the inter-layer dependencies. The structure of the context tree is a static variable depth binary tree, and the context information is stored only in the leaves of the tree. The proposed technique achieves an improvement of about 25% over a static 16 pixel context template, and 15% over a similar single-level context tree.

Digital maps can be stored and, distributed electronically using compressed raster image formats. In this work, we study how the latest JBIG2 standard can be used for storing the map images. Image tiling must be performed to support direct access to partial images in the compressed file. This can be implemented by storing each image block as its own segment. Another problem is how to store the multiple image components. There are altemative ways to solve this problem by utilizing the features of JBIG2 in creative ways.

We propose a dynamic map image handling system in a mobile environment with low computing and storage resources. We utilize a previously developed map image storage format (see Franti, P. et al., Spatial Data Handling 2002 Symp. - SDH'02, 2002), in which the maps are stored in compressed raster formats in separated logical binary layers. The proposed method combines the map dynamically from smaller image fragments retrieved on an on-demand basis. In this way, it is possible to design a cheap and low resource real-time map handling system for a client device. The system can be implemented using current wireless network bandwidth capacity, and existing compression technology. The applications are in personal navigation.

The pairwise nearest neighbor method (PNN) generates the clustering of a given data set by a sequence of merge steps. We propose an alternative solution for the merge-based approach by introducing an iterative shrinking method. The new method removes the clusters iteratively one by one until the desired number of clusters is reached. Instead of merging two nearby clusters, we remove one cluster by reassigning its data vectors to the neighbor clusters. We retain the local optimization strategy of the PNN by always removing the cluster that increases the cost function least. We give six alternative implementations, which all outperform the PNN in quality.

Abstract Binary images can be compressed efficiently using context‐based statistical modeling and arithmetic coding. However, this approach is fully sequential and therefore additional computing power from parallel computers cannot be utilized. We attack this problem and show how to implement the context‐based compression in parallel. Our approach is to segment the image into non‐overlapping blocks, which are compressed independently by the processors. We give two alternative solutions about how to construct, distribute and utilize the model in parallel, and study the effect on the compression performance and execution time. We show by experiments that the proposed approach achieves speedup that is proportional to the number of processors. The work efficiency exceeds 50% with any reasonable number of processors. Copyright © 2002 John Wiley & Sons, Ltd.

We present a method for estimating optimal context templates that are used for conditioning the pixel probabilities in context-based image compression. The algorithm optimizes the location of the context pixels within a limited neighborhood area, and produces an ordered template as a result. The ordering can be used to determine the shape of the context template for a given template size. The optimal template size depends on the size of the image, when the template shape depends on the image type. We apply the method to the compression of multi-component map images consisting of several semantic layers represented as binary images. We estimate the shape of the context-template for each layer separately, and compress the layers as generic regions using the Joint Bi-level Image Group standard JBIG2 compression technique.

Speech analysis applications are typically based on short-term spectral analysis of the speech signal. Feature extraction process outputs one feature vector per frame. The features are further processed by application-dependent techniques, such as hidden Markov models or vector quantization. Independent from the application, it is often desirable that the feature vectors form separable clusters in the feature space. In this work, we study whether data is really clustered in the feature space and, if so, what is the number of the clusters in typical speech data. We consider different forms of the widely used cepstral features.

Hough transform can be used for indexing of line-drawing images for content-based image retrieval. Angular information is used for generating the feature vector (index) as it gives global description of the image, allows compact indexing, fast retrieval and scale, translation and rotation invariant matching. In the case of very large images, however, the angular information is not always sufficient to differentiate images from each other. To alleviate this problem, we extend the idea by including also positional information of the lines in the feature vector. This gives more representative description of the images and therefore allows more accurate image matching. The main problems of this approach are: (1) to keep the feature vector compact, and (2) to preserve the property of the matching being translation and rotation invariant. We give solutions to both of these problems and introduce a new indexing scheme, which has better matching accuracy but at the cost of slower retrieval time.

Straightforward implementation of the exact pairwise nearest neighbor (PNN) algorithm takes O(N3) time, where N is the number of training vectors. This is rather slow in practical situations. Fortunately, much faster implementation can be obtained with rather simple modifications to the basic algorithm. In this paper, we propose a fast O(tauN2) time implementation of the exact PNN, where tau is shown to be significantly smaller than N, We give all necessary data structures and implementation details, and give the time complexity of the algorithm both in the best case and in the worst case. The proposed implementation achieves the results of the exact PNN with the same O(N) memory requirement.

This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. Reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average.

This paper introduces a new method for reducing the number of distance calculations in the generalized Lloyd algorithm (GLA), which is a widely used method to construct a codebook in vector quantization. The reduced comparison search detects the activity of the code vectors and utilizes it on the classification of the training vectors. For training vectors whose current code vector has not been modified, we calculate distances only to the active code vectors. A large proportion of the distance calculations can be omitted without sacrificing the optimality of the partition. The new method is included in several fast GLA variants reducing their running times over 50% on average.

A method for compression of large binary images is proposed for applications where spatial access to the image is required. The proposed method is a two-stage combination of forward-adaptive modeling and backward-adaptive context based compression with re-initialization. Compression stage is performed by JBIG arithmetic coder, namely the QM-coder. The method improves the compression performance significantly in comparison to JBIG if it is used in a similar manner. Only minor modifications to the existing software implementations are required. Implementation details are provided.

We consider the use of a static context tree for binary image compression. The contexts are stored in the leaves of a variable-depth binary tree. The tree structure itself is fully static and optimized off-line for a training image. The structure of the tree is similar for different images of the same type. The benefit from optimizing the tree for each input image separately is usually overweighed by the overhead required from storing the tree structure. The static approach is therefore applicable in most situations as the compression can be performed much faster and during a single pass over the image.

A method for compressing large binary images is proposed for applications where spatial access to the image is required. The proposed method is a two-stage combination of forward-adaptive modeling and backward-adaptive context based compression with re-initialization of statistics. The method improves compression performance significantly in comparison to a straightforward combination of JBIG and tiling. Only minor modifications to the QM-coder are required, and therefore existing software implementations can be easily utilized. Technical details of the modifications are provided. Copyright © 1999 John Wiley & Sons, Ltd.

We propose a new iterative algorithm for the generation of a codebook in vector quantization. The algorithm starts with an initial codebook that is improved by a sequence of merge and split operations. By merging small neighboring clusters additional resources (code vectors) will be released. These extra code vectors can be reallocated by splitting large clusters. The process can be iterated until no improvement is achieved in the distortion of the codebook. Experimental results show that the proposed method performs well in comparison to other tested methods, including the Generalized Lloyd algorithm (GLA) and two hierarchical methods.

Finite-state automata offer an alternative approach in the implementation of context models where the states in the automata cannot in general be assigned by a single context. Despite the potential of this approach, it makes the design of the modelling more problematic because the exact behaviour of the model is not known. Here we propose a simple formalism—context model automata (CMA)—that gives an exact interpretation for the minimum context belonging to each state in the automaton. The formalism is general enough to simulate context models such as PPM and GDMC. Using the CMA formalism as our tool, we study the behaviour of the above two context models.

We consider the clustering problem in the case where the distances between elements are metric and both the number of attributes and the number of clusters are large. In this environment the genetic algorithm approach gives high quality clusterings, but at the expense of long running time. Three new and efficient crossover techniques are introduced her. The hybridization of the genetic algorithm and k-means algorithm is discussed.

Block truncation coding (BTC) is a simple and fast image compression algorithm which achieves a constant bit rate of 2.0 bits per pixel. The method is however suboptimal. We propose a modification of BTC in which the compression ratio is improved by coding the quantization data and the bit plane by arithmetic coding with an adaptive modelling scheme. The results compare favorable with other BTC variants. The bit rate for test image Lena is 1.53 bits per pixel with a mean square error of 16.51.>

Block truncation coding (BTC) is a lossy moment preserving quantization method for compressing digital gray-level images. Its advantages are simplicity, fault tolerance, the relatively high compression efficiency and good image quality of the decoded image. Several improvements of the basic method have been recently proposed in the literature. In this survey we will study the basic algorithm and its improvements by dividing it into three separate tasks; performing quantization, coding the quantization data and coding the bit plane. Each phase of the algorithm will be analyzed separately. On the basis of the analysis, a combined BTC algorithm will be proposed and the comparisons to the standard JPEG algorithm will be made.

A two-stage modelling schema to be used together with arithmetic coding is proposed. The main motivation of the work has been the relatively slow operation of arithmetic coding. The new modelling schema reduces the use of arithmetic coding by applying to large white regions global modelling which consumes less time. This composite method works well and with a set of test images it took only about 41% of the time required by a QM-coder. At the same time the loss in compression ratio is only marginal.