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.

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.

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.

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.

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.

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.

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.

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.

Segmentation of pulmonary nodules in chest radiographs is a difficult task due to heavy noise and superposition of ribs, vessels, and other anatomical structures in lung field. In this paper, a polynomial fitting based ray-casting algorithm is proposed for pulmonary nodule segmentation in chest radiographs. Instead of directly detecting nodule edge points, the nodule intensity profiles are first fitted by using polynomials. Then, the edge positions are identified through analyzing the local minimum of the fitted curves. The algorithm has been experimentally tested over an image database with 148 nodule cases in chest radiographs collected from a variety of digital radiograph modalities. Preliminary results have shown that the proposed segmentation algorithm has obtained a high rate of successful segmentations.

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.

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.

The generalized Lloyd algorithm is one of popular partition-based algorithms to construct the codebook in vector quantization. We propose the delta-MSE dissimilarity measurement between training vectors and code vectors, based on the MSE distortion function. The delta-MSE function is heuristically derived by calculating the difference of MSE distortion before and after moving a training vector from one cluster to another. We show that the delta-MSE dissimilarity applies also to minimizing the F-ratio validity index of the vector quantizer. We incorporate the underlying dissimilarity into the generalized Lloyd algorithm in vector quantization with the initial codebook derived from the PCA-based k-d tree algorithm. Experimental results show that the proposed dissimilarity generally achieves better performance than the L2 distance in constructing the codebook of vector quantization.

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.