15784976
A New Algorithm to Solve Synchronous Consensus for Dependent Failures
Fault tolerant algorithms are often designed under the t-out-of-n assumption, which is based on the assumption that all processes or components fail independently with equal probability. However, real systems may exhibit dependent failures. Cores and survivor sets are used to build an abstraction model for dependent process failures. Using this abstraction, we design an algorithm to solve consensus problem crash failures. Our algorithm uses the processes in all cores to broadcast messages. Each core reaches agreement separately and even simultaneously in some round with no failure in the core. In the worst-case, the decision can be made in the round that is equal to the size of the minimal core. Our algorithm guarantees that all processes eventually decide on the same value regardless the initial values. We prove the correctness of our algorithm and give the lower bound of the number of rounds to solve consensus problem.
18868983
Mobility-Pattern Based Localization Update Algorithms for Mobile Wireless Sensor Networks
In mobile wireless sensor networks, sensors move in the monitored area at any direction and at any speed. Unlike many other networking hosts, sensor nodes do not have global addresses. Very often they are identified by using a location-based addressing scheme. Therefore, it is important to have the knowledge of the sensor location indicating where the data came from. In this paper, we design three mobility-pattern based localization update algorithms. Specifically, we divide sensor movements into three states, Pause, Linear, and Random. Each state adopts different localization update algorithms. Analytical and simulation results are provided to study the localization cost and location accuracy of the proposed localization-update algorithm in different mobility patterns. The analysis to these results indicates that the localization cost is minimized and the location accuracy is improved.
18137821
MILES: Multiple-Instance Learning via Embedded Instance Selection
Multiple-instance problems arise from the situations where training class labels are attached to sets of samples (named bags), instead of individual samples within each bag (called instances). Most previous multiple-instance learning (MIL) algorithms are developed based on the assumption that a bag is positive if and only if at least one of its instances is positive. Although the assumption works well in a drug activity prediction problem, it is rather restrictive for other applications, especially those in the computer vision area. We propose a learning method, MILES (multiple-instance learning via embedded instance selection), which converts the multiple-instance learning problem to a standard supervised learning problem that does not impose the assumption relating instance labels to bag labels. MILES maps each bag into a feature space defined by the instances in the training bags via an instance similarity measure. This feature mapping often provides a large number of redundant or irrelevant features. Hence, 1-norm SVM is applied to select important features as well as construct classifiers simultaneously. We have performed extensive experiments. In comparison with other methods, MILES demonstrates competitive classification accuracy, high computation efficiency, and robustness to labeling uncertainty
393
Linear-Time Approximation Algorithms for Computing Numerical Summation with Provably Small Errors
Given a multiset X={x1,. . .,xn} of real numbers, the floating-point set summation problem asks for Sn=x1 + . . . + xn. Let $E^*_n$ denote the minimum worst-case error over all possible orderings of evaluating Sn. We prove that if X has both positive and negative numbers, it is NP-hard to compute Sn with the worst-case error equal to $E^*_n$. We then give the first known polynomial-time approximation algorithm that has a provably small error for arbitrary X. Our algorithm incurs a worst-case error at most $2(\lceil\log(n-1)\rceil+1)E^*_n$. (All logarithms log in this paper are base 2.) After X is sorted, it runs in O(n) time. For the case where X is either all positive or all negative, we give another approximation algorithm with a worst-case error at most $\lceil\log\log n\rceil E^*_n$. Even for unsorted X, this algorithm runs in O(n) time. Previously, the best linear-time approximation algorithm had a worst-case error at most $\lceil\log n\rceil E^*_n$, while $E^*_n$ was known to be attainable in O(n log n) time using Huffman coding.
12301513
A Comparative Study of Skin-Color Models
In this paper, we report the results of a comparative study on skin-color models generally used for facial region location. These include two 2D Gaussian models developed in normalized RGB and HSV color spaces respectively, a 1D lookup table model of hue histogram, and an adaptive 3D threshold box model. Also, we present a new model – called “adaptive hue lookup table”. The model is developed by introducing the so-called “Continuously Adaptive Mean Shift” (Camshift) technique into a traditional hue lookup table method. With the introduction of Camshift, the lookup table is able to adaptively adjust its parameters to fit the illumination conditions of different test images. In the experiments reported here, we compare the proposed method with the four typical skin-color filters in the scenarios of different human races and illuminations. The obtained results indicate that the proposed method reaches the best balance between false detection and detect rate.
29712526
Three-sided side match finite-state vector quantization
Several low bit-rate still-image compression methods have been presented, such as SPHIT, hybrid VQ, and the Wu-Chen (see Proc. IEEE ICASSP, 1997) method. In particular, the image "Lena" can be compressed using less than 0.15 bpp at 31.4 dB or higher. These methods exercise the analysis techniques (wavelet or subband) before distributing the bit rate to each piece of an image, thus the dilemma between bit rate and distortion can be solved. In this paper, we propose a simple but comparable method that adopts the technique of side match VQ only. The side match vector quantization (SMVQ) is an effective VQ coding scheme at low bit-rate. The conventional side match (two-sided) VQ utilizes the codeword information of two neighboring blocks to predict the state codebook of an input vector. We propose a hierarchical three-sided side match finite-state vector quantization (HTSMVQ) method that can: (1) make the state codebook size as small as possible-the size is reduced to one if the prediction can perform perfectly; (2) improve the prediction quality for edge blocks; and (3) regularly refresh the codewords to alleviate the error propagation of side match. In the simulation results, the image "Lena" can be coded with a PSNR 34.682 dB at 0.25 bpp. It is better than SPIHT, EZW, FSSQ and hybrid VQ with 34.1, 33.17, 33.1, and 33.7 dB, respectively. At a bit rate lower than 0.15 bpp, only the enhanced version of EZW performs better than our method, at about 0.14 dB.
2366018
Constrained texture synthesis by scalable sub-patch algorithm
In this paper, we propose a novel scalable sub-patch algorithm for texture synthesis. Texture synthesis is an important research topic in computer graphics and image processing. We present an efficient algorithm which can paste a patch each time without boundary processing technique. In particular, the proposed sub-patch algorithm can be used in constrained texture synthesis to fill the large lost region. On the other hand, the searching neighborhood pixels can be changed due to different patch size in image reconstruction. The comparison of previous algorithms is also provided in this paper. We present a first algorithm used in constrained texture synthesis by regular synthesizing order