14900758
Distributed Source Coding for Satellite Communications
Inspired by mobile satellite communications systems, we consider a source coding system which consists of multiple sources, multiple encoders, and multiple decoders. Each encoder has access to a certain subset of the sources, each decoder has access to certain subset of the encoders, and each decoder reconstructs a certain subset of the sources almost perfectly. The connectivity between the sources and the encoders, the connectivity between the encoders and the decoders, and the reconstruction requirements for the decoders are all arbitrary. Our goal is to characterize the admissible coding rate region. Despite the generality of the problem, we have developed an approach which enables us to study all cases on the same footing. We obtain inner and outer bounds of the admissible coding rate region in terms of /spl Gamma//sub N/* and /spl Gamma/~/sub N/*, respectively, which are fundamental regions in the entropy space defined by Yeung (1991). So far, there has not been a full characterization of /spl Gamma//sub N/*, so these bounds cannot be evaluated explicitly except for some special cases. Nevertheless, we obtain an alternative outer bound which can be evaluated explicitly. We show that this bound is tight for all the special cases for which the admissible coding rate region is known. The model we study in this paper is more general than all previously reported models on multilevel diversity coding, and the tools we use are new in multiuser information theory.
32850524
Linear inequalities for covering codes: Part I: Pair covering inequalities
The lower bounds on K(n,R), minimum number of codewords of any binary code of length n, and covering radius R are improved. A new technique combining the Hamming association scheme and the results of a classic problem of covering pairs by k-tuples is introduced. The new lower bounds are obtained by studying various linear inequalities satisfied by covering codes, and such an inequality is derived. The lower bounds for K(n,R) are studied for some special values of n and R, which serve as examples showing how the methods developed are applied to concrete cases. >
15006226
Bounds on the sizes of constant weight covering codes
Motivated by applications in universal data compression algorithms we study the problem of bounds on the sizes of constant weight covering codes. We are concerned with the minimal sizes of codes of lengthn and constant weightu such that every word of lengthn and weightv is within Hamming distanced from a codeword. In addition to a brief summary of part of the relevant literature, we also give new results on upper and lower bounds to these sizes. We pay particular attention to the asymptotic covering density of these codes. We include tables of the bounds on the sizes of these codes both for small values ofn and for the asymptotic behavior. A comparison with techniques for attaining bounds for packing codes is also given. Some new combinatorial questions are also arising from the techniques.
19004655
Identification via compressed data
A new coding problem is introduced for a correlated source (X/sup n/,Y/sup n/)/sub n=1//sup /spl infin//. The observer of X/sup n/ can transmit data depending on X/sup n/ at a prescribed rate R. Based on these data the observer of Y/sup n/ tries to identify whether for some distortion measure /spl rho/ (like the Hamming distance) n/sup -1/ /spl rho/(X/sup n/,Y/sup n/)/spl les/d, a prescribed fidelity criterion. We investigate as functions of R and d the exponents of two error probabilities, the probabilities for misacceptance, and the probabilities for misrejection. In the case where X/sup n/ and Y/sup n/ are independent, we completely characterize the achievable region for the rate R and the exponents of two error probabilities; in the case where X/sup n/ and Y/sup n/ are correlated, we get some interesting partial results for the achievable region. During the process, we develop a new method for proving converses, which is called "the inherently typical subset lemma". This new method goes considerably beyond the "entropy characterization" the "image size characterization," and its extensions. It is conceivable that this new method has a strong impact on multiuser information theory.
6153081
Zero-Error Capacity for Models with Memory and the Enlightened Dictator Channel
Summary form only given. We present a general class of "combinatorial" 0-error capacity problems with the "memory" covering known and many new cases. This class can be incorporated into a model of channels with memory. W analyse a seemingly basic channel in this class, which we call the "dictator channel". Clearly, a dictator always follows his own opinion. However, we speak of an enlightened dictator, if he responds to the unanimous vote of the people against his opinion to the degree, in this case he reaches a decision by coin tossing.
43476378
Partial converse for a relay channel
A special case of the general discrete memoryless relay channel is studied. This channel consists of an input x, a relay output z, a channel output y, and a noiseless channel of capacity C/sub r/ allowing the relay sender to send additional information to the decoder. The channel is described by a collection of distributions (p(y, z mod x)). The decoder uses the channel output y and a function f(z) of the relay output at a rate no greater than C/sub r/ to recover the message. Some results on the capacity of the channel are obtained. >
14611954
Limiting path exploration in BGP
Slow convergence in the Internet can be directly attributed to the "path exploration" phenomenon, inherent in all path vector protocols. The root cause for path exploration is the dependency among paths propagated through the network. Addressing this problem in BGP is particularly difficult as the AS paths exchanged between BGP routers are highly summarized. In this paper, we describe why path exploration cannot be countered effectively within the existing BGP framework, and propose a simple, novel mechanism - forward edge sequence numbers - to annotate the AS paths with additional "path dependency" information. We then develop an enhanced path vector algorithm, EPIC, shown to limit path exploration and lead to faster convergence. In contrast to other solutions, ours is shown to be correct on a very general model of Internet topology and BGP operation. Using theoretical analysis and simulations, we demonstrate that EPIC can achieve a dramatic improvement in routing convergence, compared to BGP and other existing solutions.
5688571
Enhancing Downlink Performance in Wireless Networks by Simultaneous Multiple Packet Transmission
In this paper, we consider using simultaneous Multiple Packet Transmission (MPT) to improve the downlink performance of wireless networks. With MPT, the sender can send two compatible packets simultaneously to two distinct receivers and can double the throughput in the ideal case. We formalize the problem of finding a schedule to send out buffered packets in minimum time as finding a maximum matching problem in a graph. Since maximum matching algorithms are relatively complex and may not meet the timing requirements of real-time applications, we give a fast approximation algorithm that is capable of finding a matching at least 3/4 of the size of a maximum matching in O(|E|) time, where |E| is the number of edges in the graph. We also give analytical bounds for maximum allowable arrival rate, which measures the speedup of the downlink after enhanced with MPT, and our results show that the maximum arrival rate increases significantly even with a very small compatibility probability. We also use an approximate analytical model and simulations to study the average packet delay, and our results show that packet delay can be greatly reduced even with a very small compatibility probability.
2276524
Automatic Business Card Scanning with a Camera
In this paper, we present a system to automatically extract, rectify and enhance business card images. First the business card image patch is automatically segmented by minimizing a novel local-global variational energy. Second a quadrangle is fitted to the segmented image patch. With the four corner points of the quadrangle, we then estimate the physical aspect ratio of the business card and obtain a homography to rectify the quadrangle back to rectangular shape. We finally enhance the contrast of the rectified business card image using a S-shaped curve. Extensive experiments demonstrated the efficacy and robustness of our system.
12105004
New Measurements and Corner-Guidance for Curve Matching with Probabilistic Relaxation
Reliable curve matching is a difficult yet important problem in many vision-based applications including image-based modeling. We describe in this paper two aspects of our research in this area: a new algorithm for curve matching (including lines) within a probabilistic relaxation framework, and an approach of incorporating previously matched points/corners to guide curve matching. We propose similarity-invariant unary and binary measurements suitable for curves, and introduce an additional measurement to model the uncertainty of the binary measurements. The uncertainty measure is proven to be very important in computing the matching support from neighboring matches. We also show how to use a set of previously matched points/corners to guide the curve matching. The role of the corner guidance is explicitly modeled by a set of unary measurements and a similarity function under the same relaxation framework. Preprocessing techniques contributing to the success of our curve matching techniques are also developed and discussed. Experiments with complex real scenes show that the rate of correct matching is higher than 98%.
8951856
Model-based head pose tracking with stereovision
We present a robust model-based stereo head tracking algorithm that operates in real time on a commodity PC. The use of an individualized three-dimensional head model, coupled with the epipolar constraint from the stereo image pair greatly improves the robustness of the tracking. Experimental results have shown that our method is able to track all the six degrees of freedom of the rigid part of head motions, over an extended period of time, in the presence of large angular and translational head motions, partial occlusions, and/or dramatic facial expression changes. Applications include human-computer interaction and eye-gaze correction for videoconferencing.