14060305
Effectively Detecting All-Zero DCT Blocks for H.264 Optimization
This paper presents a novel efficient algorithm to reduce redundant DCT and quantization computations for H.264 encoding. A theoretical analysis is performed to study the sufficient condition for DCT coefficients to be quantized to zeros in H.264. As a result, a more tight sufficient condition is derived to early detect all-zero 4x4 DCT blocks. Compared with other algorithms, the proposed algorithm provides a more precise and efficient condition to predict all-zero DCT blocks. The experimental results demonstrate that the proposed algorithm outperforms other algorithms in terms of all the evaluated performances.
3107591
Agent-based evolutionary approach for interpretable rule-based knowledge extraction
An agent-based evolutionary approach is proposed to extract interpretable rule-based knowledge. In the multiagent system, each fuzzy set agent autonomously determines its own fuzzy sets information, such as the number and distribution of the fuzzy sets. It can further consider the interpretability of fuzzy systems with the aid of hierarchical chromosome formulation and interpretability-based regulation method. Based on the obtained fuzzy sets, the Pittsburgh-style approach is applied to extract fuzzy rules that take both the accuracy and interpretability of fuzzy systems into consideration. In addition, the fuzzy set agents can cooperate with each other to exchange their fuzzy sets information and generate offspring agents. The parent agents and their offspring compete with each other through the arbitrator agent based on the criteria associated with the accuracy and interpretability to allow them to remain competitive enough to move into the next population. The performance with emphasis upon both the accuracy and interpretability based on the agent-based evolutionary approach is studied through some benchmark problems reported in the literature. Simulation results show that the proposed approach can achieve a good tradeoff between the accuracy and interpretability of fuzzy systems.
2060937
Efficient prediction algorithm of integer DCT coefficients for H.264/AVC optimization
This paper presents a novel efficient prediction algorithm to reduce redundant discrete cosine transform (DCT) and quantization computations for H.264 encoding optimization. A theoretical analysis is performed to study the sufficient condition for DCT coefficients to be quantized to zeros. As a result, three sufficient conditions corresponding to three types of transform and quantization methods in H.264 are proposed. Compared with other algorithms in the literature, the proposed algorithm derives more precise and efficient conditions to predict zero quantized DCT coefficients. Both the theoretical analysis and experimental results demonstrate that the proposed algorithm is superior to other algorithms in terms of the computational complexity reduction, encoded video quality, false acceptance rate, and false rejection rate.
14473430
An optimal shape encoding scheme using skeleton decomposition
This paper presents an operational rate-distortion (ORD) optimal approach for skeleton-based boundary encoding. The boundary information is first decomposed into skeleton and distance signals, by which a more efficient representation of the original boundary results. Curves of arbitrary order are utilized for approximating the skeleton and distance signals. For a given bit budget for a video frame, we solve the problem of choosing the number and location of the control points for all skeleton and distance signals and for all boundaries within a frame, so that the overall distortion is minimized. The problem is solved with the use of Lagrangian relaxation and a shortest path algorithm in a 4D directed acyclic graph (DAG) we propose. By defining a path selection pattern, we reduce the computational complexity of the 4D DAG shortest path algorithm from O(N/sup -5/) to O(N/sup -4/), where N is the number of admissible control points for a skeleton. A suboptimal solution is also presented for further reducing the computational complexity of the algorithm to O(N/sup -2/). The proposed algorithm outperforms experimentally other competing algorithms.
4379994
Interdomain Routing as Social Choice
Interdomain routing is essential to both the stability and efficiency of the global Internet. However, most previous studies focus only on stability, and only on a special class of routing protocols, namely BGP-type, path-vector protocols. In this paper, we conduct a systematic analysis of interdomain routing considering optimality and implementation in strategic settings. We adopt the novel perspective that an interdomain routing system is one which defines a social choice rule that aggregates individual preferences of all of the autonomous systems (ASes) in a network to select interdomain routes with a set of desirable properties. An interdomain routing protocol, then, is a mechanism to implement the identified interdomain routing social choice rule, when the ASes can adopt strategic actions. By pointing out the incompatibility among the desirable properties of an interdomain routing system and the requirements for strategic implementation in distributed settings, we reveal fundamental tradeoffs that must be made when extending BGP or designing the next-generation interdomain routing system. We also provide new insights into BGP, by "reverseengineering" its behaviors from the perspective of social choice and implementation theory.
7895439
An efficient rate-distortion optimal shape coding approach utilizing a skeleton-based decomposition
In this paper, we present a new shape-coding approach, which decouples the shape information into two independent signal data sets; the skeleton and the boundary distance from the skeleton. The major benefit of this approach is that it allows for a more flexible tradeoff between approximation error and bit budget. Curves of arbitrary order can be utilized for approximating both the skeleton and distance signals. For a given bit budget for a video frame, we solve the problem of choosing the number and location of the control points for all skeleton and distance signals of all boundaries within a frame, so that the overall distortion is minimized. An operational rate-distortion (ORD) optimal approach using Lagrangian relaxation and a four-dimensional direct acyclic graph (DAG) shortest path algorithm is developed for solving the problem. To reduce the computational complexity from O(N(5)) to O(N(3)), where N is the number of admissible control points for a skeleton, a suboptimal greedy-trellis search algorithm is proposed and compared with the optimal algorithm. In addition, an even more efficient algorithm with computational complexity O(N(2)) that finds an ORD optimal solution using a relaxed distortion criterion is also proposed and compared with the optimal solution. Experimental results demonstrate that our proposed approaches outperform existing ORD optimal approaches, which do not follow the same decomposition of the source data.
6980198
A combined approach to checking web ontologies
The understanding of Semantic Web documents is built upon ontologies that define concepts and relationships of data. Hence, the correctness of ontologies is vital. Ontology reasoners such as RACER and FaCT have been developed to reason ontologies with a high degree of automation. However, complex ontology-related properties may not be expressible within the current web ontology languages, consequently they may not be checkable by RACER and FaCT. We propose to use the software engineering techniques and tools, i.e., Z/EVES and Alloy Analyzer, to complement the ontology tools for checking Semantic Web documents.In this approach, Z/EVES is first applied to remove trivial syntax and type errors of the ontologies. Next, RACER is used to identify any ontological inconsistencies, whose origins can be traced by Alloy Analyzer. Finally Z/EVES is used again to express complex ontology-related properties and reveal errors beyond the modeling capabilities of the current web ontology languages. We have successfully applied this approach to checking a set of military plan ontologies.
37744397
Stay Current and Relevant in Data Mining Research
In a recent editorial of the Bioinformatics journal, Dr. Pavel Pevzner, a pioneering researcher in the field of bioinformatics, made the following statement [1]: For many years algorithms were taught exclusively to computer scientists, with relatively few students from other disciplines attending algorithms courses. A biology student in an algorithms class would be a surprising and unlikely (though not entirely unwelcome) guest in the 1990s. Things change; some biology students now take some sort of Algorithms 101. At the same time, curious computer science students often take Genetics 101.