3756004
Parameter estimation of multi-dimensional hidden Markov models - a scalable approach
Parameter estimation is a key computational issue in all statistical image modeling techniques. In this paper, we explore a computationally efficient parameter estimation algorithm for multi-dimensional hidden Markov models. 2-D HMM has been applied to supervised aerial image classification and comparisons have been made with the first proposed estimation algorithm. An extensive parametric study has been performed with 3-D HMM and the scalability of the estimation algorithm has been discussed. Results show the great applicability of the explored algorithm to multi-dimensional HMM based image modeling applications.
10105
Real-Time Computerized Annotation of Pictures
Developing effective methods for automated annotation of digital pictures continues to challenge computer scientists. The capability of annotating pictures by computers can lead to breakthroughs in a wide range of applications, including Web image search, online picture-sharing communities, and scientific experiments. In this work, the authors developed new optimization and estimation techniques to address two fundamental problems in machine learning. These new techniques serve as the basis for the automatic linguistic indexing of pictures - real time (ALIPR) system of fully automatic and high-speed annotation for online pictures. In particular, the D2-clustering method, in the same spirit as K-Means for vectors, is developed to group objects represented by bags of weighted vectors. Moreover, a generalized mixture modeling technique (kernel smoothing as a special case) for nonvector data is developed using the novel concept of hypothetical local mapping (HLM). ALIPR has been tested by thousands of pictures from an Internet photo-sharing site, unrelated to the source of those pictures used in the training process. Its performance has also been studied at an online demonstration site, where arbitrary users provide pictures of their choices and indicate the correctness of each annotation word. The experimental results show that a single computer processor can suggest annotation terms in real time and with good accuracy.
3117640
Asymptotic Performance of Vector Quantizers with a Perceptual Distortion Measure
Gersho's (1979) bounds on the asymptotic performance of vector quantizers are valid for vector distortions which are powers of the Euclidean norm. Yamada, Tazaki, and Gray (1980) generalized the results to distortion measures that are increasing functions of the norm of their argument. In both cases, the distortion is uniquely determined by the vector quantization error, i.e., the Euclidean difference between the original vector and the codeword into which it is quantized. We generalize these asymptotic bounds to input-weighted quadratic distortion measures and measures that are approximately output-weighted-quadratic when the distortion is small, a class of distortion measures often claimed to be perceptually meaningful. An approximation of the asymptotic distortion based on Gersho's conjecture is derived as well. We also consider the problem of source mismatch, where the quantizer is designed using a probability density different from the true source density. The resulting asymptotic performance in terms of distortion increase in decibels is shown to be linear in the relative entropy between the true and estimated probability densities.
13204199
A source coding approach to classification by vector quantization and the principle of minimum description length
An algorithm for supervised classification using vector quantization and entropy coding is presented. The classification rule is formed from a set of training data {(X/sub i/, Y/sub i/)}/sub i=1//sup n/, which are independent samples from a joint distribution P/sub XY/. Based on the principle of minimum description length (MDL), a statistical model that approximates the distribution P/sub XY/ ought to enable efficient coding of X and Y. On the other hand, we expect a system that encodes (X, Y) efficiently to provide ample information on the distribution P/sub XY/. This information can then be used to classify X, i.e., to predict the corresponding Y based on X. To encode both X and Y, a two-stage vector quantizer is applied to X and a Huffman code is formed for Y conditioned on each quantized value of X. The optimization of the encoder is equivalent to the design of a vector quantizer with an objective function reflecting the joint penalty of quantization error and misclassification rate. This vector quantizer provides an estimation of the conditional distribution of Y given X, which in turn yields an approximation to the Bayes classification rule. This algorithm, namely discriminant vector quantization (DVQ), is compared with learning vector quantization (LVQ) and CART/sup R/ on a number of data sets. DVQ outperforms the other two on several data sets. The relation between DVQ, density estimation, and regression is also discussed.
26279535
On Zador's entropy-constrained quantization theorem
Zador's classic result for the asymptotic high-rate behavior of entropy-constrained vector quantization is recast in a Lagrangian form which better matches the Lloyd algorithm used to optimize such quantizers. A proof that the result holds for a general class of distributions is sketched.
1149168
Unsupervised Multiresolution Segmentation for Images with Low Depth of Field
Unsupervised segmentation of images with low depth of field (DOF) is highly useful in various applications. This paper describes a novel multiresolution image segmentation algorithm for low DOF images. The algorithm is designed to separate a sharply focused object-of-interest from other foreground or background objects. The algorithm is fully automatic in that all parameters are image independent. A multi-scale approach based on high frequency wavelet coefficients and their statistics is used to perform context-dependent classification of individual blocks of the image. Unlike other edge-based approaches, our algorithm does not rely on the process of connecting object boundaries. The algorithm has achieved high accuracy when tested on more than 100 low DOF images, many with inhomogeneous foreground or background distractions. Compared with he state of the art algorithms, this new algorithm provides better accuracy at higher speed.
15119633
Computationally efficient parameter estimation for harmonic sinusoidal signals
A Markov-like weighted least squares (WLS) estimator is presented herein for harmonic sinusoidal parameter estimation. The estimator involves two distinct steps whereby it first obtains a set of in ...
12799351
Mining risk patterns in medical data
In this paper, we discuss a problem of finding risk patterns in medical data. We define risk patterns by a statistical metric, relative risk, which has been widely used in epidemiological research. We characterise the problem of mining risk patterns as an optimal rule discovery problem. We study an anti-monotone property for mining optimal risk pattern sets and present an algorithm to make use of the property in risk pattern discovery. The method has been applied to a real world data set to find patterns associated with an allergic event for ACE inhibitors. The algorithm has generated some useful results for medical researchers.
13206070
Discovering and ranking important rules
Decision rules generated from reducts can fully describe a data set. We introduce a new method of evaluating rules by taking advantage of rough sets theory. We consider rules generated from the original data set as attributes in the new constructed decision table. Reducts generated from this new decision table contain essential attributes, which are the rules. Only important rules are contained in the reducts. Experiments on an artificial data set and a medical data set show that the "reduct rules" are more important, and this new method provides an automatic and effective way of ranking rules.
9732879
Compression of the layered depth image
A layered depth image (LDI) is a new popular representation and rendering method for objects with complex geometries. Similar to a 2D image, the LDI consists of an array of pixels. However, unlike the 2D image, an LDI pixel has depth information, and there are multiple layers at a pixel location. In this paper, we develop a novel LDI compression algorithm that handles the multiple layers and the depth coding. The algorithm records the number of LDI layers at each pixel location, and compresses LDI color and depth components separately. For LDI layer with sparse pixels, the data is aggregated and then encoded. An empirical rate-distortion model is used to optimally allocate bits among different components. Compared with benchmark compression tools such as JPEG-2000 and MPEG-4, our scheme improves the compression performance significantly.
3148051
Code-coverage guided prioritized test generation
With Internet applications spreading like wildfire, software testing is challenged with new topics related to the distributed nature of Web applications. We apply code based testing techniques to the testing of Web applications, specifically Java programs. Source code based automatic test generation is difficult because most previous methods use constraint satisfaction models as a solution, which is an NP complete problem [M. J. Gallagher et al. (1997)]. We present a method of guiding users through test case generations. Instead of automating the entire procedure, our method aims at generating a framework of test cases and providing instructions for users to instantiate the framework into actual executable test cases. An early experimental study of this method shows the effectiveness of this method.