Steiner trees in probabilistic networks

Various network reliability problems are #P-complete, however, certain classes of networks such as series-parallel networks, admit polynomial time algorithms. We extend these efficient methods to a superclass of series-parallel networks, the partial 2-trees. In fact, we solve a more general problem: given a probabilistic partial 2-tree and a set T of target nodes, we compute in linear time the probability of obtaining a subgraph connecting all of the target nodes. Equivalently, this is the probability of obtaining a Steiner tree for T. The algorithm exploits a characterization of partial 2-trees as graphs with no subgraph homeomorphic to K₄.     

一种改进的Steiner树启发式算法

最小Steiner树问题是NP完全问题，关于Steiner问题的启发式算法的研究具有重要理论和实际意义。本文在MPH算法基础上，对于经过某些关键节点的短路径优先考虑，提出了KBMPH算法，从而实现更多链路的共享。在随机网络上的仿真结果表明，极大多数情况下，在准Steiner树的网络费用KBMPH算法优于MPH算法，KBMPH算法的复杂度为O（n^3）。     

Fast vicinity-upgrade algorithm for rectilinear Steiner trees

A new algorithm for rectilinear Steiner trees (RST) is presented. The proposed algorithm is based on successively constructing a vicinity structure from a rectilinear minimum spanning tree (MST) and generating a refined RST. The algorithm achieves an 8.5-10% average cost improvement over the rectilinear MST at a time complexity of O(n log n). To address specifically the linear programming approach of global routing the algorithm is modified to generate K trees.<>     

Restricted dynamic Steiner trees for scalable multicast in datagramnetworks

The paper addresses the issue of minimizing the number of nodes involved in routing over a multicast tree and in the maintenance of such a tree in a datagram network. It presents a scheme where the tree routing and maintenance burden is laid only upon the source node and the destination nodes associated with the multicast tree. The main concept behind this scheme is to view each multicast tree as a collection of unicast paths and to locate only the multicast source and destination nodes on the junctions of their multicast tree. The paper shows that despite this restriction, the cost of the created multicast trees is not necessarily higher than the cost of the trees created by other algorithms that do not impose the restriction and therefore require all nodes along the data path of a tree to participate in routing over the tree and in the maintenance of the tree     

Reliable transmission of high-quality video over ATM networks

The development of broadband networks has led to the possibility of a wide variety of new and improved service offerings. Packetized video is likely to be one of the most significant high-bandwidth users of such networks. The transmission of variable bit-rate (VBR) video offers the potential promise of constant video quality but is generally accompanied by packet loss which significantly diminishes this potential. We study a class of error recovery schemes employing forward error-control (FEC) coding to recover from such losses. In particular, we show that a hybrid error recovery strategy involving the use of active FEC in tandem with simple passive error concealment schemes offers very robust performance even under high packet losses. We discuss two different methods of applying FEC to alleviate the problem of packet loss. The conventional method of applying FEC generally allocates additional bandwidth for channel coding while maintaining a specified average video coding rate. Such an approach suffers performance degradations at high loads since the bandwidth expansion associated with the use of FEC creates additional congestion that negates the potential benefit in using FEC. In contrast, we study a more efficient FEC application technique in our hybrid approach, which allocates bandwidth for channel coding by throttling the source coder rate (i.e., performing higher compression) while maintaining a fixed overall transmission rate. More specifically, we consider the performance of the hybrid approach where the bandwidth to accommodate the FEC overhead is made available by throttling the source coder rate sufficiently so that the overall rate after application of FEC is identical to that of the original unprotected system. We obtain the operational rate-distortion characteristics of such a scheme employing selected FEC codes. In doing so, we demonstrate the robust performance achieved by appropriate use of FEC under moderate-to-high packet losses in comparison to the unprotected system.     

Restricted H.264/AVC video coding for privacy protected video scrambling

The issue of personal privacy has garnered significant attention with the extensive application of video surveillance systems. Privacy region scrambling is an effective method to protect privacy in video. To ensure that nonprivacy regions are not affected by scrambling, particular methods must be taken to prevent drift error in privacy protected video scrambling. However, existing methods have significantly reduced the coding efficiency. In this paper, we focus on improving coding efficiency while preventing drift error in privacy protected H.264/AVC video scrambling, which is the state-of-the-art coding standard. A restricted video coding scheme is proposed, which involves three parts of Mode Restricted Intra Prediction (MRIP), Search Window Restricted Motion Estimation (SWRME) and Boundary Strength Restricted Deblocking Filtering (BSRDF). Experimental results show that the proposed restricted video coding scheme prevents drift error with higher coding efficiency than others.     

Reliable tracking of facial features in semantic-based video coding

A new method of tracking the position of important facial features for semantic-based moving image coding is presented. Reliable and fast tracking of the facial features in head-and-shoulders scenes is of paramount importance for reconstruction of the speakers motion in videophone systems. The proposed method is based on eigenvalue decomposition of the sub-images extracted from subsequent frames of the video sequence. The motion of each facial feature (the left eye, the right eye, the nose and the lips) is tracked separately; this means that the algorithm can be easily adapted for a parallel machine. No restrictions, other than the presence of the speaker's face, were imposed on the actual contents of the scene. The algorithm was tested on numerous widely used head-and-shoulders video sequences containing moderate head pan, rotation and zoom, with remarkably good results. Tracking was maintained even when the facial features were occluded. The algorithm can also be used in other semantic-based systems     

Low-complexity video coding via power-rate-distortion optimization

Wireless multimedia sensor networks (WMSNs) have been potentially applicable for several emerging applications. The resources, i.e., power and bandwidth available to visual sensors in a WMSN are, however, very limited. Hence, it is important but challenging to achieve efficient resource allocation and optimal video data compression while maximizing the overall network lifetime. In this paper, a power-rate-distortion (PRD) optimized resource-scalable low-complexity multiview video encoding scheme is proposed. In our video encoder, both the temporal and interview information can be exploited based on the comparisons of extracted media hashes without performing motion and disparity estimations, which are known to be time-consuming. We present a PRD model to characterize the relationship between the available resources and the RD performance of our encoder. More specifically, an RD function in terms of the percentages for different coding modes of blocks and the target bit rate under the available resource constraints is derived for optimal coding mode decision. The major goal here is to design a PRD model to optimize a “motion estimation-free” low-complexity video encoder for applications with resource-limited devices, instead of designing a general-purpose video codec to compete compression performance against current compression standards (e.g., H.264/AVC). Analytic results verify the accuracy of our PRD model, which can provide a theoretical guideline for performance optimization under limited resource constraints. Simulation results on joint RD performance and power consumption (measured in terms of encoding time) demonstrate the applicability of our video coding scheme for WMSNs.     

Reliable eye-diagram analysis of data links via device macromodels

This paper addresses the impact of device macromodels on the accuracy of signal integrity and performance predictions for critical digital interconnecting systems. It exploits nonlinear parametric models for both single-ended and differential devices, including the effects of power supply fluctuations and receiver bit detection. The analysis demonstrates that the use of well-designed macromodels dramatically speeds up the simulation as well it preserves timing accuracy even for long bit sequences.     

Reliable low-power digital signal processing via reduced precision redundancy

In this paper, we present a novel algorithmic noise-tolerance (ANT) technique referred to as reduced precision redundancy (RPR). RPR requires a reduced precision replica whose output can be employed as the corrected output in case the original system computes erroneously. When combined with voltage overscaling (VOS), the resulting soft digital signal processing system achieves up to 60% and 44% energy savings with no loss in the signal-to-noise ratio (SNR) for receive filtering in a QPSK system and the butterfly of fast Fourier transform (FFT) in a WLAN OFDM system, respectively. These energy savings are with respect to optimally scaled (i.e., the supply voltage equals the critical voltage V/sub dd-crit/) present day systems. Further, we show that the RPR technique is able to maintain the output SNR for error rates of up to 0.09/sample and 0.06/sample in an finite impulse response filter and a FFT block, respectively.     

Reliable information embedding for image/video in the presence of lossy compression

Lossy compression is inherently contradictory with information hiding and may result in unreliable retrieval of embedded message. For most of the existing data hiding algorithms, the process of dealing with the conflict and trade-off of invisibility, capacity and robustness is done in an experimental fashion. We have developed an image and video unified data-embedding technique. The algorithm is capable of accurately retrieving hidden data after the embedded signals are subjected to JPEG/MPEG compression as long as its compression degree is above the predefined one. Embedding strategy is to integrate data hiding into the JPEG/MPEG coding structures and to combine the adjustment factor of the strength and quantity of data hiding with the control parameter of lossy compression, according to the constraint of human visual system, the demand of hiding capacity and distortion impact of lossy compression. Experimental evaluation demonstrates that the proposed algorithm allows us to hide data invisibly in an accurate retrievable way with effective and flexible trade-off mechanism in the presence of lossy compression. In addition, the scheme is robust to some common attacks including low-pass filtering, noisy interference, frame dropping and transcoding.     

On the stability of paths, Steiner trees and connected dominating sets in mobile ad hoc networks

We propose algorithms that use the complete knowledge of future topology changes to set up benchmarks for the minimum number of times a communication structure (like paths, trees, connected dominating sets, etc.) should change in the presence of a dynamically changing topology. We first present an efficient algorithm called OptPathTrans that operates on a simple greedy principle: whenever a new source–destination (s–d) path is required at time instant t, choose the longest-living s–d path from time t. The above strategy when repeated over the duration of the s–d session yields a sequence of long-lived stable paths such that number of path transitions is the global minimum. We then propose algorithms to determine the sequence of stable Steiner trees and the sequence of stable connected dominating sets to illustrate that the principle behind OptPathTrans is very general and can be used to find the stable sequence of any communication structure as long as there is a heuristic or algorithm to determine that particular communication structure in a given network graph. We study the performance of the three algorithms in the presence of complete knowledge of future topology changes as well as using models that predict the future locations of nodes. Performance results indicate that the stability of the communication structures could be considerably improved by making use of the knowledge about locations of nodes in the near future.     

Scalable video compression via overcomplete motion compensated wavelet coding

Recently, there have been a flurry of works on overcomplete motion compensated wavelet coding (OMCWC). In this paper, we address the importance of phase and focus on the design of scalable video coding algorithms within the OMCWC framework. Specifically, our new contributions consist of the following three components: (1) efficient block motion estimation techniques in the wavelet domain including hierarchical and fractional-pel block matching, (2) extend overcomplete motion compensated prediction (MCP) into overcomplete motion compensated temporal filtering (MCTF) to achieve temporal scalability (3) context modeling strategies for embedded quantization and entropy coding of 3D wavelet coefficients. Experiment results are used to demonstrate that the class of overomplete MCP/MCTF coders are capable of achieving comparable performance to other competing interframe wavelet coders.     

Reliable M2M/IoT data delivery from FANETs via satellite

The use of unmanned aerial vehicles (UAVs) is rising in several application fields. This work deals with the communication challenges in UAV swarms, or flying ad hoc network (FANET), when taking into account non–line‐of‐sight scenarios. The use of satellites is a necessity in such operating conditions; thus, this work provides architectural considerations and performance assessments when several (FANETs) share an uplink random access satellite channel, fed with M2M/IoT traffic generated from on‐board sensors, to be reliably delivered to a remote ground destination.     

Resilient peer-to-peer streaming of scalable video over hierarchical multicast trees with backup parent pools

This paper introduces a new cross layer tree-based peer-to-peer design using hierarchical cluster layers and a new method for selection of “backup parent pools” for resilient streaming of scalable video to provide highest quality of experience for all peers. Backup parent pools are selected during the process of multicast tree construction based on information provided by the hierarchical clusters. The proposed tree construction method aims to minimize bottlenecks that may be caused by non-leaf nodes with low upload bandwidth. Performance of the proposed system is demonstrated by extensive test results using a wide range of simulation scenarios. Comparison of the results with those of some recent works indicates that the proposed system is clearly superior in several aspects.     

Enhancing QoE for video streaming in MANETs via multi-constraint routing

In this paper, we propose a Multi-Constraint Quality-of-Experience (QoE) centric Routing (MCQR) technique for efficient real-time video streaming over Mobile Ad-hoc Networks (MANETs). The dynamic estimation of link quality metric during MCQR route discovery process is the key of enhancing QoE at end user. MCQR limits end-to-end delay and jitter of received data packets by selecting long lifetime routes with maximum permissible delay. This minimizes the distortion caused fluctuations in perceived video. To prove the effectiveness of MCQR for real-time video streaming, we have designed a hybrid MANET consisting of simulated nodes and physical machines. In our hybrid network, the source and destination nodes are video traffic generators and receivers running on physical devices. Emulation results are obtained using real-time video streaming over high fidelity virtual wireless network, and conforming that the MCQR protocol provides satisfactory QoE to end users as compared to existing similar techniques. The packet delivery ratio of MCQR is higher than 90 % and its mean opinion score is higher than three (i.e., satisfactory) even when mobility and shadowing effects are kept high in target network scenarios. These improvements are achieved along with still maintaining similar or better routing overhead and processing delays.     

Self-learning-based post-processing for image/video deblocking via sparse representation

Blocking artifact, characterized by visually noticeable changes in pixel values along block boundaries, is a common problem in block-based image/video compression, especially at low bitrate coding. Various post-processing techniques have been proposed to reduce blocking artifacts, but they usually introduce excessive blurring or ringing effects. This paper proposes a self-learning-based post-processing framework for image/video deblocking by properly formulating deblocking as an MCA (morphological component analysis)-based image decomposition problem via sparse representation. Without the need of any prior knowledge (e.g., the positions where blocking artifacts occur, the algorithm used for compression, or the characteristics of image to be processed) about the blocking artifacts to be removed, the proposed framework can automatically learn two dictionaries for decomposing an input decoded image into its “blocking component” and “non-blocking component.” More specifically, the proposed method first decomposes a frame into the low-frequency and high-frequency parts by applying BM3D (block-matching and 3D filtering) algorithm. The high-frequency part is then decomposed into a blocking component and a non-blocking component by performing dictionary learning and sparse coding based on MCA. As a result, the blocking component can be removed from the image/video frame successfully while preserving most original visual details. Experimental results demonstrate the efficacy of the proposed algorithm.     

Advanced news video parsing via visual characteristics of anchorperson scenes

In this paper, we present an advanced news video parsing system via exploring the visual characteristics of anchorperson scenes, which aims to provide personalized news services over Internet or mobile platforms. As the anchorperson shots serve as the root shots for constructing news video, the addressed system firstly performs anchorperson detection which divides the news into several segments. Due to the manipulation of multi-features and post-processing, our method of anchorperson detection can even be efficiently applied to news video whose anchorperson scenes are most challenging and complicated. Usually, the segments produced from anchorperson detection are regarded as news stories. However, an observation in our database proves this is not true because of the existing of interview scenes. These interview scenes are showed in the form that interviewer (anchorperson) and interviewee recursively appear. Thus, a technique called interview clustering based on face similarity is carried out to merge these interview segments. Another novel aspect of our system is entity summarization of interview scenes. We adopt it in the system at final. The effectiveness and robustness of the proposed system are demonstrated by the evaluation on 19 hours of news programs from 6 different TV Channels.     

MAP estimation via agreement on trees: message-passing and linear programming

We develop and analyze methods for computing provably optimal maximum a posteriori probability (MAP) configurations for a subclass of Markov random fields defined on graphs with cycles. By decomposing the original distribution into a convex combination of tree-structured distributions, we obtain an upper bound on the optimal value of the original problem (i.e., the log probability of the MAP assignment) in terms of the combined optimal values of the tree problems. We prove that this upper bound is tight if and only if all the tree distributions share an optimal configuration in common. An important implication is that any such shared configuration must also be a MAP configuration for the original distribution. Next we develop two approaches to attempting to obtain tight upper bounds: a) a tree-relaxed linear program (LP), which is derived from the Lagrangian dual of the upper bounds; and b) a tree-reweighted max-product message-passing algorithm that is related to but distinct from the max-product algorithm. In this way, we establish a connection between a certain LP relaxation of the mode-finding problem and a reweighted form of the max-product (min-sum) message-passing algorithm.     

QoS provisioning by power control for video communication via satellite links

Video transmissions over satellite links are sensitive to signal fades because of rain, especially in the tropics. We performed a video‐streaming experiment over a satellite link for 24 days distributed over 1 year to investigate the effects of rain fade. Based on the measurements, models for the relationships between rainfall rate, power level, packet loss, and video quality are proposed. Furthermore, for both uplink and downlink channel, an adaptive closed loop power control algorithm, with a Proportional–Integral–Derivative controller is designed. This is used for the mitigation of the rain‐induced attenuation in order to guarantee a certain level of Quality of Service and Quality of Experience. Simulation results show the effectiveness of the proposed power control solution and its ability to sustain video quality levels in spite of rain fades. Copyright © 2014 John Wiley & Sons, Ltd.