3715563
Learning-based linguistic indexing of pictures with 2--d MHMMs
Automatic linguistic indexing of pictures is an important but highly challenging problem for researchers in computer vision and content-based image retrieval. In this paper, we introduce a statistical modeling approach to this problem. Categorized images are used to train a dictionary of hundreds of concepts automatically based on statistical modeling. Images of any given concept category are regarded as instances of a stochastic process that characterizes the category. To measure the extent of association between an image and the textual description of a category of images, the likelihood of the occurrence of the image based on the stochastic process derived from the category is computed. A high likelihood indicates a strong association. In our experimental implementation, the ALIP (Automatic Linguistic Indexing of Pictures) system, we focus on a particular group of stochastic processes for describing images, that is, the two-dimensional multiresolution hidden Markov models (2-D MHMMs). We implemented and tested the system on a photographic image database of 600 different semantic cat- egories, each with about 40 training images. Tested using 3,000 images outside the training database, the system has demonstrated good accuracy and high potential in linguistic indexing of these test images.
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.
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.
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.
34043187
Groups of connected objects
10602845
Maximizing Throughput for Optical Burst Switching Networks
A key problem in optical burst switching (OBS) is to schedule as many bursts as possible on wavelength channels so that the throughput is maximized and the burst loss is minimized. In this paper, we use competitive analysis to analyze the worst-case performance of a large set of scheduling algorithms, called best-effort online scheduling algorithms, for OBS networks, and establish a number of interesting upper and lower bounds on the performance of such algorithms. A surprising discovery is that the worst-case performance of any best-effort online scheduling algorithm is primarily determined by the maximum to minimum burst length ratio, followed by the range of offset time. Furthermore, if all bursts have the same burst length and offset time, all best-effort online scheduling algorithms generate the same optimal solution, regardless how different they may look like. Our analysis can also be extended to some nonbest-effort online scheduling algorithms, such as the well-known Horizon algorithm, and establish similar bounds. Based on the analytic results, we give guidelines for several widely discussed OBS problems, including burst assembly, offset time setting and scheduling algorithm design, and propose a new channel reservation protocol called VFO to improve the worst-case performance. Our simulation shows that it is quite often for an online scheduling algorithm to exhibit its (near) worst-case performance. Thus improving the worst-case performance is essential. Our simulation also suggests that VFO reduces the average burst loss rate by as much as 35%
42802236
Rule Evaluations, Attributes, and Rough Sets: Extension and a Case Study
Manually evaluating important and interesting rules generated from data is generally infeasible due to the large number of rules extracted. Different approaches such as rule interestingness measures and rule quality measures have been proposed and explored previously to extract interesting and high quality association rules and classification rules. Rough sets theory was originally presented as an approach to approximate concepts under uncertainty. In this paper, we explore rough sets based rule evaluation approaches in knowledge discovery. We demonstrate rule evaluation approaches through a real-world geriatric care data set from Dalhousie Medical School. Rough set based rule evaluation approaches can be used in a straightforward way to rank the importance of the rules. One interesting system developed along these lies in HYRIS (HYbrid Rough sets Intelligent System). We introduce HYRIS through a case study on survival analysis using the geriatric care data set.
468496
Incorporating Legacy System into Semantic Grid Framework
The semantic grid is an extension of the current grid. Resources description framework (RDF) can be used to extend the current grid into semantic grid in which information and services are given well-defined meaning. This paper proposed an approach to recognizing the reusable components from the legacy system and representing these components by using XML and RDF, which could be performed for incorporating legacy system components into the semantic grid framework
13902534
Towards evolving Web sites into grid services environment
Grid services are emerged by integrating grid computing and Web services to perform a seamless information processing system across distributed, heterogeneous, dynamic virtual organisations that the user can access from any location. The Web Service Resource Framework (WSRF) was announced as a new way for manipulating "stateful resources" to perform grid services. It defines the concept of "stateful resources" and how they can be discovered, queried and manipulated via Web services. In this paper, we proposed a grid services-oriented reengineering approach to create stateful resources from conventional HTML Web sites, which applies hierarchical cluster and wrapper techniques to extract and translate Web sites resources. It supports services identification and packaging and archives Web site evolution into grid services environment by exploiting WRSF.