838252
Background modeling and subtraction by codebook construction
We present a new fast algorithm for background modeling and subtraction. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. Our method can handle scenes containing moving backgrounds or illumination variations (shadows and highlights), and it achieves robust detection for compressed videos. We compared our method with other multimode modeling techniques.
6524269
Real-time foreground-background segmentation using codebook model
We present a real-time algorithm for foreground-background segmentation. Sample background values at each pixel are quantized into codebooks which represent a compressed form of background model for a long image sequence. This allows us to capture structural background variation due to periodic-like motion over a long period of time under limited memory. The codebook representation is efficient in memory and speed compared with other background modeling techniques. Our method can handle scenes containing moving backgrounds or illumination variations, and it achieves robust detection for different types of videos. We compared our method with other multimode modeling techniques. In addition to the basic algorithm, two features improving the algorithm are presented-layered modeling/detection and adaptive codebook updating. For performance evaluation, we have applied perturbation detection rate analysis to four background subtraction algorithms and two videos of different types of scenes.
39411693
IP lookup by binary search on prefix length
Waldvogel et al. [ACM SIGCOMM, 1997, 25-36] have proposed a collection of hash tables (CHT) organization for an IP router table. IP lookup can be done with O(log l/sub dist/) hash-table searches, where l/sub dist/ is the number of distinct prefix-lengths (also equal to the number of hash tables in the CHT). Srinivasan and Varghese [ACM transactions on Computer Systems, Feb:1-40, 1999] have proposed the use of controlled prefix-expansion to reduce the value of l/sub dist/. The algorithm of [V. Srinivasan, 1999] does not minimize the storage required by the prefixes and markers for the resulting set of prefixes. We develop an algorithm that minimizes storage requirement but takes O(nW/sup 3/ + kW/sup 4/) time, where k is the desired number of distinct lengths, n is the number of prefixes, and W is the length of the longest prefix. Also, we propose improvements to the heuristic of [V. Srinivasan, 1999].
7329667
Iterative kernel principal component analysis for image modeling
In recent years, kernel principal component analysis (KPCA) has been suggested for various image processing tasks requiring an image model such as, e.g., denoising or compression. The original form of KPCA, however, can be only applied to strongly restricted image classes due to the limited number of training examples that can be processed. We therefore propose a new iterative method for performing KPCA, the kernel Hebbian algorithm, which iteratively estimates the kernel principal components with only linear order memory complexity. In our experiments, we compute models for complex image classes such as faces and natural images which require a large number of training examples. The resulting image models are tested in single-frame super-resolution and denoising applications. The KPCA model is not specifically tailored to these tasks; in fact, the same model can be used in super-resolution with variable input resolution, or denoising with unknown noise characteristics, in spite of this, both super-resolution and denoising performance are comparable to existing methods.
9243298
Analysis of the competition between wired, DSL and wireless users in an access network
This paper analyzes the performance of a large population composed of several classes of long lived TCP flows experiencing packet losses due to random transmission errors and to congestion created by the sharing of a common tail-drop or RED bottleneck router. Each class has a different transmission error rate. This setting is used to analyze the competition between wired and wireless users in an access network, where one class (the wired class) has no or small (like BER in DSL) transmission error losses whereas the other class has higher transmission error losses, or the competition between DSL flows using different coding schemes. We propose a natural and simple model for the joint throughput evolution of several classes of TCP flows under such a mix of losses. Two types of random transmission error losses are considered: one where losses are Poisson and independent of the rate of the flow, and one where the losses are still Poisson but with an intensity that is proportional to the rate of the source. We show that the large population model where the population tends to infinity has a threshold (given in closed form) below which there are no congestion losses at all in steady state, and above which there is a stationary limiting regime in which we can compute both the mean value and the distribution of the rate obtained by each class of flow. We also show that the maximum mean value for the aggregated rate is achieved at the threshold.
1648937
Optimizing multidimensional index trees for main memory access
Recent studies have shown that cache-conscious indexes such as the CSB+-tree outperform conventional main memory indexes such as the T-tree. The key idea of these cache-conscious indexes is to eliminate most of child pointers from a node to increase the fanout of the tree. When the node size is chosen in the order of the cache block size, this pointer elimination effectively reduces the tree height, and thus improves the cache behavior of the index. However, the pointer elimination cannot be directly applied to multidimensional index structures such as the R-tree, where the size of a key, typically, an MBR (minimum bounding rectangle), is much larger than that of a pointer. Simple elimination of four-byte pointers does not help much to pack more entries in a node.
This paper proposes a cache-conscious version of the R-tree called the CR-tree. To pack more entries in a node, the CR-tree compresses MBR keys, which occupy almost 80% of index data in the two-dimensional case. It first represents the coordinates of an MBR key relatively to the lower left corner of its parent MBR to eliminate the leading O's from the relative coordinate representation. Then, it quantizes the relative coordinates with a fixed number of bits to further cut off the trailing less significant bits. Consequently, the CR-tree becomes significantly wider and smaller than the ordinary R-tree. Our experimental and analytical study shows that the two-dimensional CR-tree performs search up to 2.5 times faster than the ordinary R-tree while maintaining similar update performance and consuming about 60% less memory space.
14214328
Efficient construction of variable-stride multibit tries for IP lookup
Srinivasan and Varghese (1999) have proposed the use of multibit tries to represent routing tables used for Internet (IP) address lookups. They propose an O(n /sub */W/sup 2//sub */ k) dynamic programming algorithm to determine the strides for an optimal variable-stride trie that has at most k levels. Here, n is the number of prefixes in the routing table and W is the length of the longest prefix. We improve on this algorithm by providing an alternative dynamic programming formulation. The complexity of our algorithm is O(n/sub */W/sub */k), on real router data sets. This is an improvement by a factor of W over the corresponding algorithm of Srinivasan. Experiments conducted by us indicate that our variable-stride algorithm is between 2 and 17 times as fast for IPv4 routing table data.