An efficient information hiding method based on motion vector space encoding for HEVC

As the newest video coding standard, high efficiency video coding (HEVC) has great potential as a new information hiding carrier. This paper proposes an efficient information hiding method based on motion vector space encoding for HEVC encoding process. In this method, the mapping relationship between motion vector set and the points in the motion vector space is defined. The motion vector components from the N/2 prediction units (PUs) with smallest size in a coding tree unit (CTU) are selected as the secret information carriers. Each N secret bits are converted to a 2N + 1-ary number. By modifying at most one element in the set of N motion vector components, the mapping value of the set in the motion vector space can be equal to the 2N + 1-ary number. In this way, information hiding is realized. Since at most one element is changed and the N/2 PUs with smallest size are selected, this method contributes to excellent transparency of steganography and anti-steganalysis performance with high embedding efficiency. To the best of our knowledge, this is the first information hiding method based on motion vector for HEVC. Experimental results verify that the proposed method is practicable and has better performance than two typical embedding rules of information hiding based on motion vector.     

SVCEval-RA: an evaluation framework for adaptive scalable video streaming

Multimedia content adaption strategies are becoming increasingly important for effective video streaming over the actual heterogeneous networks. Thus, evaluation frameworks for adaptive video play an important role in the designing and deploying process of adaptive multimedia streaming systems. This paper describes a novel simulation framework for rate-adaptive video transmission using the Scalable Video Coding standard (H.264/SVC). Our approach uses feedback information about the available bandwidth to allow the video source to select the most suitable combination of SVC layers for the transmission of a video sequence. The proposed solution has been integrated into the network simulator NS-2 in order to support realistic network simulations. To demonstrate the usefulness of the proposed solution we perform a simulation study where a video sequence was transmitted over a three network scenarios. The experimental results show that the Adaptive SVC scheme implemented in our framework provides an efficient alternative that helps to avoid an increase in the network congestion in resource-constrained networks. Improvements in video quality, in terms of PSNR (Peak Signal to Noise Ratio) and SSIM (Structural Similarity Index) are also obtained.     

Analysis of YouTube’s traffic adaptation to dynamic environments

The popular Internet service, YouTube, has adopted by default the HyperText Markup Language version 5 (HTML5). With this adoption, YouTube has moved to Dynamic Adaptive Streaming over HTTP (DASH) as Adaptive BitRate (ABR) video streaming technology. Furthermore, rate adaptation in DASH is solely receiver-driven. This issue motivates this work to make a deep analysis of YouTube’s particular DASH implementation. Firstly, this article provides a state of the art about DASH and adaptive streaming technology, and also YouTube traffic characterization related work. Secondly, this paper describes a new methodology and test-bed for YouTube’s DASH implementation traffic characterization and performance measurement. This methodology and test-bed do not make use of proxies and, moreover, they are able to cope with YouTube traffic redirections. Finally, a set of experimental results are provided, involving a dataset of 310 YouTube’s videos. The depicted results show a YouTube’s traffic pattern characterization and a discussion about allowed download bandwidth, YouTube’s consumed bitrate and quality of the video. Moreover, the obtained results are cross-validated with the analysis of HTTP requests performed by YouTube’s video player. The outcomes of this article are applicable in the field of Quality of Service (QoS) and Quality of Experience (QoE) management. This is valuable information for Internet Service Providers (ISPs), because QoS management based on assured download bandwidth can be used in order to provide a target end-user’s QoE when YouTube service is being consumed.     

Object detection in video sequences by a temporal modular self-adaptive SOM

A video segmentation algorithm that takes advantage of using a background subtraction (BS) model with low learning rate (LLR) or a BS model with high learning rate (HLR) depending on the video scene dynamics is presented in this paper. These BS models are based on a neural network architecture, the self-organized map (SOM), and the algorithm is termed temporal modular self-adaptive SOM, TMSA_SOM. Depending on the type of scenario, the TMSA_SOM automatically classifies and processes each video into one of four different specialized modules based on an initial sequence analysis. This approach is convenient because unlike state-of-the-art (SoA) models, our proposed model solves different situations that may occur in the video scene (severe dynamic background, initial frames with dynamic objects, static background, stationary objects, etc.) with a specialized module. Furthermore, TMSA_SOM automatically identifies whether the scene has drastically changed (e.g., stationary objects of interest become dynamic or drastic illumination changes have occurred) and automatically detects when the scene has become stable again and uses this information to update the background model in a fast way. The proposed model was validated with three different video databases: Change Detection, BMC, and Wallflower. Findings showed a very competitive performance considering metrics commonly used in the literature to compare SoA models. TMSA_SOM also achieved the best results on two perceptual metrics, Ssim and D-Score, and obtained the best performance on the global quality measure, FSD (based on F-Measure, Ssim, and D-Score), demonstrating its robustness with different and complicated non-controlled scenarios. TMSA_SOM was also compared against SoA neural network approaches obtaining the best average performance on Re, Pr, and F-Measure.     

A competitive study of the pseudoflow algorithm for the minimum <Emphasis Type="Italic">s</Emphasis>–<Emphasis Type="Italic">t</Emphasis> cut problem in vision applications

Rapid advances in image acquisition and storage technology underline the need for real-time algorithms that are capable of solving large-scale image processing and computer-vision problems. The minimum s–t cut problem, which is a classical combinatorial optimization problem, is a prominent building block in many vision and imaging algorithms such as video segmentation, co-segmentation, stereo vision, multi-view reconstruction, and surface fitting to name a few. That is why finding a real-time algorithm which optimally solves this problem is of great importance. In this paper, we introduce to computer vision the Hochbaum’s pseudoflow (HPF) algorithm, which optimally solves the minimum s–t cut problem. We compare the performance of HPF, in terms of execution times and memory utilization, with three leading published algorithms: (1) Goldberg’s and Tarjan’s Push-Relabel; (2) Boykov’s and Kolmogorov’s augmenting paths; and (3) Goldberg’s partial augment-relabel. While the common practice in computer-vision is to use either BK or PRF algorithms for solving the problem, our results demonstrate that, in general, HPF algorithm is more efficient and utilizes less memory than these three algorithms. This strongly suggests that HPF is a great option for many real-time computer-vision problems that require solving the minimum s–t cut problem.     

Multiple <Emphasis Type="Italic">k</Emphasis> nearest neighbor search

The problem of kNN (k Nearest Neighbor) queries has received considerable attention in the database and information retrieval communities. Given a dataset D and a kNN query q, the k nearest neighbor algorithm finds the closest k data points to q. The applications of kNN queries are board, not only in spatio-temporal databases but also in many areas. For example, they can be used in multimedia databases, data mining, scientific databases and video retrieval. The past studies of kNN query processing did not consider the case that the server may receive multiple kNN queries at one time. Their algorithms process queries independently. Thus, the server will be busy with continuously reaccessing the database to obtain the data that have already been acquired. This results in wasting I/O costs and degrading the performance of the whole system. In this paper, we focus on this problem and propose an algorithm named COrrelated kNN query Evaluation (COKE). The main idea of COKE is an “information sharing” strategy whereby the server reuses the query results of previously executed queries for efficiently processing subsequent queries. We conduct a comprehensive set of experiments to analyze the performance of COKE and compare it with the Best-First Search (BFS) algorithm. Empirical studies indicate that COKE outperforms BFS, and achieves lower I/O costs and less running time.     

Cryptanalysis of an MOR cryptosystem based on a finite associative algebra基于有限结合代数的 MOR 公钥密码安全性分析

The Shor algorithm is effective for public-key cryptosystems based on an abelian group. At CRYPTO 2001, Paeng (2001) presented a MOR cryptosystem using a non-abelian group, which can be considered as a candidate scheme for post-quantum attack. This paper analyses the security of a MOR cryptosystem based on a finite associative algebra using a quantum algorithm. Specifically, let L be a finite associative algebra over a finite field F. Consider a homomorphism φ: Aut(L) → Aut(H)×Aut(I), where I is an ideal of L and H ? L/I. We compute dim Im(φ) and dim Ker(φ), and combine them by dim Aut(L) = dim Im(φ)+dim Ker(φ). We prove that Im(φ) = Stab_Comp(H,I)(μ + B²(H, I)) and Ker(φ) ? Z¹(H, I). Thus, we can obtain dim Im(φ), since the algorithm for the stabilizer is a standard algorithm among abelian hidden subgroup algorithms. In addition, Z¹(H, I) is equivalent to the solution space of the linear equation group over the Galois fields GF(p), and it is possible to obtain dim Ker(φ) by the enumeration theorem. Furthermore, we can obtain the dimension of the automorphism group Aut(L). When the map ? ∈ Aut(L), it is possible to effectively compute the cyclic group 〈?〉 and recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.     

Video parsing via spatiotemporally analysis with images

Effective parsing of video through the spatial and temporal domains is vital to many computer vision problems because it is helpful to automatically label objects in video instead of manual fashion, which is tedious. Some literatures propose to parse the semantic information on individual 2D images or individual video frames, however, these approaches only take use of the spatial information, ignore the temporal continuity information and fail to consider the relevance of frames. On the other hand, some approaches which only consider the spatial information attempt to propagate labels in the temporal domain for parsing the semantic information of the whole video, yet the non-injective and non-surjective natures can cause the black hole effect. In this paper, inspirited by some annotated image datasets (e.g., Stanford Background Dataset, LabelMe, and SIFT-FLOW), we propose to transfer or propagate such labels from images to videos. The proposed approach consists of three main stages: I) the posterior category probability density function (PDF) is learned by an algorithm which combines frame relevance and label propagation from images. II) the prior contextual constraint PDF on the map of pixel categories through whole video is learned by the Markov Random Fields (MRF). III) finally, based on both learned PDFs, the final parsing results are yielded up to the maximum a posterior (MAP) process which is computed via a very efficient graph-cut based integer optimization algorithm. The experiments show that the black hole effect can be effectively handled by the proposed approach.     

On the Advice Complexity of the k-server Problem Under Sparse Metrics

We consider the k-Server problem under the advice model of computation when the underlying metric space is sparse. On one side, we introduce Θ(1)-competitive algorithms for a wide range of sparse graphs. These algorithms require advice of (almost) linear size. We show that for graphs of size N and treewidth α, there is an online algorithm that receives O (n(log α + log log N))^* bits of advice and optimally serves any sequence of length n. We also prove that if a graph admits a system of μ collective tree (q, r)-spanners, then there is a (q + r)-competitive algorithm which requires O (n(log μ + log log N)) bits of advice. Among other results, this gives a 3-competitive algorithm for planar graphs, when provided with O (n log log N) bits of advice. On the other side, we prove that advice of size Ω(n) is required to obtain a 1-competitive algorithm for sequences of length n even for the 2-server problem on a path metric of size N ≥ 3. Through another lower bound argument, we show that at least \(\frac {n}{2}(\log \alpha - 1.22)\) bits of advice is required to obtain an optimal solution for metric spaces of treewidth α, where 4 ≤ α < 2k.     

On polynomial solutions of the linear stationary control system

It is known that the controllable system x′ = Bx + Du, where the x is the n-dimensional vector, can be transferred from an arbitrary initial state x(0) = x ⁰ to an arbitrary finite state x(T) = x ^T by the control function u(t) in the form of the polynomial in degrees t. In this work, the minimum degree of the polynomial is revised: it is equal to 2p + 1, where the number (p ? 1) is a minimum number of matrices in the controllability matrix (Kalman criterion), whose rank is equal to n. A simpler and a more natural algorithm is obtained, which first brings to the discovery of coefficients of a certain polynomial from the system of algebraic equations with the Wronskian and then, with the aid of differentiation, to the construction of functions of state and control.     

Indefinite summation of rational functions with additional minimization of the summable part

An algorithm of indefinite summation of rational functions is proposed. For a given function f(x), it constructs a pair of rational functions g(x) and r(x) such that f(x) = g(x + 1) ? g(x) + r(x), where the degree of the denominator of r(x) is minimal, and, when this condition is satisfied, the degree of the denominator of g(x) is also minimal.     

On-line Walking Speed Control in Human-Powered Exoskeleton Systems Based on Dual Reaction Force Sensors

On-line walking speed control in human-powered exoskeleton systems is a big challenge, the translations of human intention to increase or decrease walking speed in maneuverable human exoskeleton systems is still complex field. In this paper, we propose a novel sensing technique to control the walking speed of the system according to the pilot intentions and to minimize the interaction force. We introduce a new sensing technology “Dual Reaction Force (DRF)” sensors, and explain the methodology of using it in the investigation of walking speed changing intentions. The force signals mismatch successfully applied to control the walking speed of the exoskeleton system according to the pilot intentions. Typical issues on the implementation of the sensory system are experimentally validated on flat terrain walking trails. We developed an adaptive trajectory frequency control algorithm to control the walking speed of HUman-powered Augmentation Lower Exoskeleton (HUALEX) within the human wearer intended speed. Based on the mismatch of DRF sensors, we proposed a new control methodology for walking speed control. Human intention recognition and identification through an sensorized footboard and smart shoe is achieved successfully in this work, the new term heel contact time H _{C T} is main feedback signal for the control algorithm. From the experimental walking trails we found that, the H _{C T} during flat walking ranges from 0.69±0.05 sec and 0.41±0.07 sec while walking speed varies between 1m/s and 2.5m/s. The proposed algorithm used an Adaptive Central Pattern Generators (ACPGs) applied to control joint trajectory frequency, the different walking speeds associated with different functioning of human body CPGs frequency. We validated the proposed control algorithm by simulations on single Degree of Freedom (1-DoF) exoskeleton platform, the simulation results show the efficiency and validated that the proposed control algorithm will provides a good walking speed control for the HUALEX exoskeleton system.     

Procedural content generation for platformers: designing and testing FUN PLEdGE

Video games are a peculiar medium, standing at the crossing point between art and software application, and characterized by an active involvement of its audience. The complexity of the product generates a huge challenge for the companies that develop video games. In the development process, level designers play a crucial role: they are in charge of declining the theoretical framework developed by the game designer into game levels, which contain the actual gameplay scenarios. Hence, the final goal of any level designer is to valorize the game design by creating enjoyable gaming experiences while, at the same time, respecting several constraints. To lighten the burden on level designers, several semi-automated approaches to level generation have appeared in time, but the majority of these tools suffer from several drawbacks. In the present work, we tackle the issue of designing, prototyping and testing FUN PLEdGE, a general-purpose automated levels generator and editor for platform video games. Its main goal is to shrink development time while producing – unassisted – levels that are both playable and fun. Moreover, our tool provides the maximum freedom to the level designer, by avoiding to impose unnecessary constraints on the structure of the levels and by guaranteeing the possibility to modify and personalize by hand the generated levels. During this process, the generator assists the designer by suggesting corrections functional to the quality of the player experience. To prove the effectiveness of our prototypal application we have also developed and tested with players a platform game. In the same vein, we asked to a group of game developers to test FUN PLEdGE.     

Efficient distance-based representative skyline computation in 2D space

Representative skyline computation is a fundamental issue in database area, which has attracted much attention in recent years. A notable definition of representative skyline is the distance-based representative skyline (DBRS). Given an integer k, a DBRS includes k representative skyline points that aims at minimizing the maximal distance between a non-representative skyline point and its nearest representative. In the 2D space, the state-of-the-art algorithm to compute the DBRS is based on dynamic programming (DP) which takes O(k m ²) time complexity, where m is the number of skyline points. Clearly, such a DP-based algorithm cannot be used for handling large scale datasets due to the quadratic time cost. To overcome this problem, in this paper, we propose a new approximate algorithm called ARS, and a new exact algorithm named PSRS, based on a carefully-designed parametric search technique. We show that the ARS algorithm can guarantee a solution that is at most ?? larger than the optimal solution. The proposed ARS and PSRS algorithms run in O(klog2mlog(T/??)) and O(k ² log3m) time respectively, where T is no more than the maximal distance between any two skyline points. We also propose an improved exact algorithm, called PSRS+, based on an effective lower and upper bounding technique. We conduct extensive experimental studies over both synthetic and real-world datasets, and the results demonstrate the efficiency and effectiveness of the proposed algorithms.     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

Minimization of the maximal lateness for a single machine

Consideration was given to the classical NP-hard problem 1|r_j|L_max of the scheduling theory. An algorithm to determine the optimal schedule of processing n jobs where the job parameters satisfy a system of linear constraints was presented. The polynomially solvable area of the problem 1|r_j|L_max was expanded. An algorithm was described to construct a Pareto-optimal set of schedules by the criteria L_max and C_max for complexity of O(n³logn) operations.     

Hybrid full-/half-duplex cellular networks: user admission and power control

We consider a single-cell network with a hybrid full-/half-duplex base station. For the practical scenario with N channels, K uplink users, and M downlink users (max{K,M} ≤ N ≤ K + M), we tackle the issue of user admission and power control to simultaneously maximize the user admission number and minimize the total transmit power when guaranteeing the quality-of-service requirement of individual users. We formulate a 0–1 integer programming problem for the joint-user admission and power allocation problem. Because finding the optimal solution of this problem is NP-hard in general, a low-complexity algorithm is proposed by introducing the novel concept of adding dummy users. Simulation results show that the proposed algorithm achieves performance similar to that of branch and bound algorithm and significantly outperforms the random pairing algorithm.     

Protecting query privacy with differentially private <Emphasis Type="Italic">k</Emphasis>-anonymity in location-based services

Nowadays, location-based services (LBS) are facilitating people in daily life through answering LBS queries. However, privacy issues including location privacy and query privacy arise at the same time. Existing works for protecting query privacy either work on trusted servers or fail to provide sufficient privacy guarantee. This paper combines the concepts of differential privacy and k-anonymity to propose the notion of differentially private k-anonymity (DPkA) for query privacy in LBS. We recognize the sufficient and necessary condition for the availability of 0-DPkA and present how to achieve it. For cases where 0-DPkA is not achievable, we propose an algorithm to achieve ??-DPkA with minimized ??. Extensive simulations are conducted to validate the proposed mechanisms based on real-life datasets and synthetic data distributions.