8718525
A mutual semantic endorsement approach to image retrieval and context provision
Learning semantics from annotated images to enhance content-based retrieval is an important research direction. In this paper,annotation data are assumed available for only a subset of images inside the database. An on the fly learning method is developed to capture the semantics of query images. Specifically, the semantics of annotated images in a visual proximity of a query are compared with each other to determine the amount of mutual endorsement. An image is considered endorsed by another if they possess similar semantics. Annotations with high mutual endorsement are used to narrow down a candidate pool of images. The new retrieval method is inherently dynamic and treats seamlessly different forms of annotation data. Experiments show that semantic endorsement can increase precision by as much as 70%in average for a wide range of parameter settings. We also develop a context provision mechanism to reveal the relationship between a query and semantic clusters extracted from the database. Context helps users explore the content of a database and provides a platform for them to tailor searches by stressing different perspectives in the interpretation of a query.
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.
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.
1837455
AFBV: a scalable packet classification algorithm
Packet classification is a central function of a number of network activities, such as routing and firewall management. The packet classifier has a ordered rule database, one rule for each type of packets, and all arriving packets are classified into equivalent classes based on the first rule they match. With the development of the Internet, the database size can only grow with time. Consequently, scalability becomes an important issue for packet classification algorithm. This project is addressing the scalability problem in the selection of rules for packet classification. There is significant previous work in this area. Much previous work executed in linear time with the number of rules. Our work is an improvement on the ABV scheme of Baboescu and Varghese [1], which in turn is an improvement in the straightforward linear Lucent bit vector scheme (BV) [2]. The BV scheme produces bit vectors of all rules for each field, and selects the rules applicable to the complete header by first finding the bit vectors corresponding to each field, then intersecting them, and the first set bit in the consequent bit vector implies the position of the rule in the database. ABV made two observations: first the set bits in the bit vectors are sparse and second a packet matches no more than a few rules. Hence, ABV improves BV to achieve logarithmic time in two steps. First, ABV rearranges the rules by sorting, so that those rules that match specific prefixes are near each other in the list. Second, it aggregates bits in each field to reduce memory accesses, but increasing the possibility of false matches. The rule rearrangement mitigates the false matches to some extent, but also incurs additional cost. First, rule rearrangement makes it necessary to find all matches, instead of first match in BV. Second, it is not easy to find an effective rearrangement method. Third, rules need to be mapped back to the original order so as to find the rule with the lowest order. Our scheme, the Aggregated and Folded Bit Vector algorithm (AFBV) inherits the idea of bit vector and aggregation from BV and ABV, but discards rule rearrangement and introduce a new concept: folding. All bits in a predefined range r (r is called folding range, usually equal to multiple aggregate sizes), whose positions have the same mod-f value are OR-ed together, the result occupying that position mod f, thus folding the bit vector (f is called folding size). Only when there are at least one bit set at the same mod-f position can one get false matches, while in ABV, a match among any bits within an aggregation group can lead to a false match. Once there is a match in the folded bit vector at position k (k is inclusively between 0 and f-1), the possible real match position must take the form (I · f + k). Therefore, folding helps not only filter out false matches but also locate the real match positions. This scheme will also not produce any false negatives (missing a match). Thus, correctness is guaranteed. Besides the folding range and the folding size, the number of folding is another important parameter in AFBV. By using multiple folding with different sizes, we can enhance the detecting and locating ability of the folded vectors. First, only if there are matches in all the intersections of the folded vectors may there be real matches in the original vectors. The gain here is that mostly we do not need to fetch the whole original bit vector to conclude a false match as required in BV and ABV. Second, with proper selection on the folding sizes, multiple folding greatly reduces the number of the possible match positions than single folding. The gain here is that in case of real matches, we only need to fetch parts instead of the whole original bit vectors. In addition to the aggregate bit vectors, AFBV needs to store the folded bit vectors, which incurs about 10% additional storage requirements, and could be even smaller. AFBV offers the following benefits: Only the first matched rule need to be found; no mapping back cost is needed; without rule rearrangement, pre-processing is much simple; a large aggregate size can be applied because the folded vectors reduce false matches. In our simulations of relative performance we compare the Lucent BV algorithm, the ABV algorithm and our AFBV algorithm, and evaluate both performance and space utilization. Preliminary results on different-sized databases show that AFBV outperforms ABF and BV on average, and can achieve the similar level of performance in worst cases, with about a 10% increase in memory requirements, for the additional, folded vectors.
2012673
Mining the smallest association rule set for predictions
Mining transaction databases for association rules usually generates a large number of rules, most of which are unnecessary when used for subsequent prediction. In this paper we define a rule set for a given transaction database that is much smaller than the association rule set but makes the same predictions as the association rule set by the confidence priority. We call this subset the informative rule set. The informative rule set is not constrained to particular target items; and it is smaller than the non-redundant association rule set. We present an algorithm to directly generate the informative rule set, i.e., without generating all frequent itemsets first, and that accesses the database less often than other unconstrained direct methods. We show experimentally that the informative rule set is much smaller than both the association rule set and the non-redundant association rule set, and that it can be generated more efficiently.
110311
Securing distributed adaptation
Open architecture networks provide applications with fine-grained control over network elements. With this control comes the risk of misuse and new challenges to security beyond those present in conventional networks. One particular security requirement is the ability of applications to protect the secrecy and integrity of transmitted data while still allowing trusted active elements within the network to operate on that data. This paper describes mechanisms for identifying trusted nodes within a network and securely deploying adaptation instructions to those nodes while protecting application data from unauthorized access and modification. Promising experimental results of our implementation within the conductor adaptation framework are also presented, suggesting that such features can be incorporated into real networks.
39140992
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 two-dimensional (2-D) image, the LDI consists of an array of pixels. However, unlike the 2-D image, an LDI pixel has depth information, and there are multiple layers at a pixel location. 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 the benchmark compression tools such as JPEG-2000 and MPEG-4, our scheme improves the compression performance significantly.
2572958
RACCOON: a peer-based system for data integration and sharing
Recent database applications see the emerging need to support data integration in distributed, peer-to-peer environments, in which autonomous peers (sources) connected by a network are willing to exchange data and services with each other. To address related research challenges, we are developing a system called "RACCOON", which allows different sources to integrate and share their data. We use an application to show several important features of the RACCOON system. The system also suggests semantic mappings for the user to choose. We show the two different querying modes, particularly how a query is expanded using the semantic mappings in the extended querying mode to compute as many answers to the query as possible.