Efficient algorithms for computation of the burstiness curve of video sources

The burstiness of a video source can be characterized by its burstiness curve. The burstiness curve is useful in the optimal allocation of resources to satisfy a desired quality of service for the video stream in a packet network. In this paper, we present deterministic algorithms for exact computation of the burstiness curve of a video source, for both elementary video streams and MPEG-2 Transport Streams. The algorithms exploit the piecewise linearity of the burstiness curve and compute only the points at which the slope of the burstiness curve changes. We also present approximate versions of these algorithms, which save computational effort by considering only a small number of candidate points at which the slope of the burstiness curve may change. The approximate algorithm was able to compute the burstiness curve of a 2-h long elementary video stream in approximately 10 s, as compared to over 6 h for the exact algorithm, with virtually no loss of accuracy in the computation. The efficiency of the proposed algorithms makes them suitable for quality-of-service (QoS) provisioning not only in off-line environments such as in video-on-demand (VoD) servers, but also in real-time applications such as in live TV distribution systems.     

Efficient elliptic curve scalar multiplication algorithms resistant to power analysis

This paper presents four algorithms for securing elliptic curve scalar multiplication against power analysis. The highest-weight binary form (HBF) of scalars and randomization are applied to resist power analysis. By using a special method to recode the scalars, the proposed algorithms do not suffer from simple power analysis (SPA). With the randomization of the secret scalar or base point, three of the four algorithms are secure against differential power analysis (DPA), refined power analysis (RPA) and zero-value point attacks (ZPA). The countermeasures are also immune to the doubling attack. Fast Shamir’s method is used in order to improve the efficiency of parallel scalar multiplication. Compared with previous countermeasures, the new countermeasures achieve higher security and do not impact overall performance.     

Genetic algorithms for video segmentation

The current paper presents a new genetic algorithm (GA)-based method for video segmentation. The proposed method is specifically designed to enhance the computational efficiency and quality of the segmentation results compared to standard GAs. The segmentation is performed by chromosomes that independently evolve using distributed genetic algorithms (DGAs). However, unlike conventional DGAs, the chromosomes are initiated using the segmentation results of the previous frame, instead of random values. Thereafter, only unstable chromosomes corresponding to moving object parts are evolved by crossover and mutation. As such, these mechanisms allow for effective solution space exploration and exploitation, thereby improving the performance of the proposed method in terms of speed and segmentation quality. These advantages were confirmed based on experiments where the proposed method was successfully applied to both synthetic and natural video sequences.     

Efficient computation for Whittaker-Henderson smoothing

Efficient algorithms that compute both the estimates and the generalized cross-validation score for the problem of Whittaker-Henderson smoothing are presented. Algorithm efficiency results from carefully exploiting the problem's rich structure to reduce execution time and memory use. The algorithms are much faster than existing ones, and use significantly less memory. MATLAB M-files are included.     

Self-adaptivity for grid applications. An Efficient Resources Selection model based on evolutionary computation algorithms

Over the last few years, the adaptation ability has become an essential characteristic for grid applications due to the fact that it allows applications to face the dynamic and changing nature of grid systems. This adaptive capability is applied within different grid processes such as resource monitoring, resource discovery, or resource selection. In this regard, the present approach provides a self-adaptive ability to grid applications, focusing on enhancing the resources selection process. This contribution proposes an Efficient Resources Selection model to determine the resources that best fit the application requirements. Hence, the model guides applications during their execution without modifying or controlling grid resources. Within the evaluation phase, the experiments were carried out in a real European grid infrastructure. Finally, the results show that not only a self-adaptive ability is provided by the model but also a reduction in the applications’ execution time and an improvement in the successfully completed tasks rate are accomplished.     

基于多模态信息的视频描述算法

为了挖掘视频中不同的模态信息,提出一种基于多模态信息的视频描述算法。在基本的编码解码器网络基础上,更加关注视频多模态信息和高级语义属性。在编码器阶段,提取视频的静态特征、光流特征和视频段特征,同时设计语义属性检测网络得到视频高级语义特征。为了避免解码器阶段的曝光偏差和训练损失与评价准则不统一的问题,采用基于强化学习的训练算法直接将客观评价准则作为优化目标来训练模型。所提出的算法在公开视频描述数据集MSVD上取得了很好的实验效果。     

Efficient algorithms for clique problems

The k-clique problem is a cornerstone of NP-completeness and parametrized complexity. When k is a fixed constant, the asymptotically fastest known algorithm for finding a k-clique in an n-node graph runs in O(n0.792k) time (given by Nešet?il and Poljak). However, this algorithm is infamously inapplicable, as it relies on Coppersmith and Winograd's fast matrix multiplication.We present good combinatorial algorithms for solving k-clique problems. These algorithms do not require large constants in their runtime, they can be readily implemented in any reasonable random access model, and are very space-efficient compared to their algebraic counterparts. Our results are the following:

•

We give an algorithm for k-clique that runs in O(nk/(εlogn)^k−1) time and O(nε) space, for all ε>0, on graphs with n nodes. This is the first algorithm to take o(nk) time and O(nc) space for c independent of k.

•

Let k be even. Define a k-semiclique to be a k-node graph G that can be divided into two disjoint subgraphs U={u₁,…,uk/2} and V={v₁,…,vk/2} such that U and V are cliques, and for all i?j, the graph G contains the edge {ui,vj}. We give an time algorithm for determining if a graph has a k-semiclique. This yields an approximation algorithm for k-clique, in the following sense: if a given graph contains a k-clique, then our algorithm returns a subgraph with at least 3/4 of the edges in a k-clique.

     

Efficient algorithms for array redistribution

Dynamic redistribution of arrays is required very often in programs on distributed presents efficient algorithms for redistribution between different cyclic(k) distributions, as defined in High Performance Fortran. We first propose special optimized algorithms for a cyclic(x) to cyclic(y) redistribution when x is a multiple of y, or y is a multiple of x. We then propose two algorithms, called the GCD method and the LCM method, for the general cyclic(x) to cyclic(y) redistribution when there is no particular relation between x and y. We have implemented these algorithms on the Intel Touchstone Delta, and find that they perform well for different array sizes and number of processors     

An efficient algorithms for Tate pairing computation

The Weil and Tate pairings have found several new applications in cryptography. In most of these applications, the Weil pairing or Tate pairing of supersingular elliptic curves are essential tools. Therefore efficient computation of the Weil or Tate pairings are crucial factors for practical applications of the cryptographic protocols based pairings. The Weil pairing is thought one of two applications of the Tate pairing. Thus to compute the Weil pairing is more slow than the Tate pairing. To efficiently implement these cryptosystems it is necessary to optimize the computation time for the Tate pairing. This paper presents a new algorithm for computing Tate pairing, which is faster than Miller＇s algorithm that is the best-known general method. Finally, the computation cost of the new algorithm is compared with Miller＇s algorithm.     

Efficient algorithms for the instantiated transitive closurequeries

The performances of several algorithms suitable for processing an important class of recursive queries called the instantiated transitive closure (TC) queries are studied and compared. These algorithms are the wavefront, δ-wavefront, and a generic algorithm called super-TC. During the evaluation of a TC query, the first two algorithms may read a given disk page more than once, whereas super-TC reads the disk page at most once. A comprehensive performance evaluation of these three algorithms using rigorous analytical and simulation models is presented. The study reveals that the relative performance of the algorithms is a strong function of the parameters which characterize the processed TC query and the relation referenced by that query. The superiority of one of the super-TC variants over all of the other presented algorithms is shown     

Efficient algorithms for the soft morphological operators

This correspondence presents two soft morphological algorithms that process multiple images simultaneously. The first algorithm performs best when the structuring elements contain less than 19 points; whereas, the second algorithm should be used for larger structuring elements. Theoretical and experimental analyses show these algorithms are faster than the conventional algorithm     

Modeling video sources for real-time scheduling

What is the impact of the autocorrelation of variable-bit-rate (VBR) sources on real-time scheduling algorithms? Our results show that the impact of long term, or interframe, autocorrelation is negligible, while the impact of short term, or intraframe, autocorrelation can be significant. Such results are essentially independent of the video coding scheme employed. To derive these results, video sequences are modeled as a collection of stationary subsequences called scenes. Within a scene, a statistical model is derived for both the sequence of frames and of slices. The model captures the distribution and the autocorrelation function of real-time video data. In previous work, the pseudoperiodicity of the slice level auto-correlation function made it difficult to develop a simple yet accurate model. We present a generalization of previous methods that can easily capture this pseudoperiodicity and is suited for modeling a greater variety of autocorrelation functions. By simply tuning a few parameters, the model reproduces the statistic behavior of sources with different types and levels of correlation on both the frame and the slice level.     

A comparison of algorithms for vertex normal computation

We investigate current vertex normal computation algorithms and evaluate their effectiveness at approximating analytically computable (and thus comparable) normals for a variety of classes of model. We find that the most accurate algorithm depends on the class and that for some classes, none of the available algorithms is particularly good. We also compare the relative speeds of all algorithms.