Abstract:Mesh simplification is very important for storage, transmission, process, and real-time rendering. In this paper, the mesh simplification techniques are detailed and the typical methods are analyzed. The outlook of the future work is also given in the end.

Abstract:Traffic shaping has an enormous impact on the provision of QoS (quality of service) guarantees. In this paper, the fundamentals of network calculus, a set of recent developments which provide a deep insight into flow problems encountered in computer networks are summarized and refined. By using network calculus, a general framework of traffic shaping is developed which includes greedy lossless shapers, traffic clippers and shapers with finite buffer to obtain, the input-output characterization of three traffic shapers, and how a traffic shaper can be used at all network elements to improve the efficiency of QoS mechanisms.

Abstract:Prestack depth migration is computationally intensive. To deal with this problem, people have made big efforts to develop high efficient parallel algorithms. In this paper, after some parallel algorithms are analyzed, according to the character of 3-D Kirchhoff depth migration, a simplified algorithm is presented based on shared memory . In the proposed algorithm, the slave processes store and read ray traveltimes directly so that the total amount of message passing will be remarkably decreased. At the same time, this algorithm has well combined both the "task pool" and the "coarse granularity" techniques together, the former ensuring the dynamic load-balance and the latter reduing the cost of communication between the slaves and the master. In the end, experimental results show that this algorithm has high efficiency and scalability.

Abstract:In the current applications such as video conferencing, the video codec speed is the key factor to maintain the real-time performance in the whole system. In order to minimize the computations and improve the performance of video coding, an adaptive zero block detection algorithm combined with multi-resolution motion estimation is proposed in this paper. The multi-resolution technique uses down-sampling method on the whole image, which can dramatically reduce the computations in searching for the best candidate block during the motion search period. At the same time, adaptive zero block detection criteria can make the motion search procedure even faster and improve the coding efficiency without any influence on the image quality. Furthermore, the run-time of DCT(discrete cosine transform) and quantization has been singificantly reduced afterwards. Simulation results show that with H.263 codec, the proposed algorithm can obtain 40% savings in computations at most without any losses in the subjective and objective quality of decoded images.

Abstract:By the currently developed component models and standards, the component interfaces convey only limited semantics and the interaction protocol among components is hidden within the implementations, which may result in the problem of architectural mismatches, also make these components in difficulty to reuse, validate and manage. In this paper, an XML-message based architecture description language (XADL) is outlined, which supports the description of explicit interaction protocols and the composing relations of components. Based on the XADL, the notion of architectural mismatch is introduced and shows how it can be checked. The XADL enhances the descriptive capacity of interfaces, prevents systems from potential architectural mismatches, and facilities the implementation of system monitor, performance analysis and dynamic tuning.

Abstract:More and more large systems are taking UML as requirements description language for system analysis and design, especially in those safety-critical systems. One of the most important dynamic behaviorspecifying mechanism of UML---the UML state machine, is widely used for specification of communicationprotocols and control units. Unfortunately, UML has no strictly defined formal dynamic semantics. It is difficult to do formal verification and proof on the requirements. In this paper, a formal semantics of UML state machine is built. The UML state is firstly represented by inductive state term from some kind of term algebra. Secondly, a labeled transition system (LTS) is introduced, in which an LTS-state is a UML state term, an LTS-transition is a micro step of UML state machine. In the end, a set of Plotkin-style structural operational semantics (SOS) rules inductively defines a compositional formal semantics for UML state machine. This method not only synthesizes those formal methods for classical Statecharts, but also makes innovation addrerssed to UML state machine. At any tiem, the configuration of the machine can be inferred from the state term. The simplified LTS-lable and structuralized operational semantics ruls will play a fundamental fole in formal verification.

Abstract:In this paper, an efficient algorithm is presented to dynamically schedule the task sets combining hard and soft real-time tasks in heterogeneous systems. The proposed algorithm improves the scheduling success ratio by introducing a new task assignment policy and a QoS (quality of service) degradation policy for soft real-time tasks. To evaluate the performance of the new algorithm, extensive simulation studies have been done. These simulations apply myopic algorithm to schedule the hard and soft real-time tasks in heterogeneous systems and use it as a baseline to compare with the proposed algorithm. Simulation results show that the scheduling success ratio of the new algorithm is always higher than that of myopic algorithm in real-time heterogeneous systems for a variety of task parameters.

Abstract:The CCN (calculate crossing number) algorithm using branch and bound method to calculate the crossing number of graph with small order is put forward to study the crossing number using computer. With the algorithm, the crossing number of all of the 4-regular graphs Aac(n) for n≤12 and the crossing number of some random 4-regular graphs Arc(n) for n≤16 are calculated. At the end of the paper, the average crossing number is shown, and a conjecture is given that the average crossing number of 4-regular graph is O(n²).

Abstract:In the model-based diagnosis, a key step is to compute the minimal hitting sets from the minimal conflict sets, because the minimal hitting sets of all the conflict sets are the faults of an investigated system. In Reiter s method, HS-tree is used for computing the minimal hitting sets. However, it will need a heavy work, and will result in the fact that the correct hitting sets are probably pruned away. In this paper, a new method is put forword for computing minimal hitting sets by the "binary hitting set tree", in brief, BHS-tree. This method will improve Reiter's approaches in the aspects as follows. (1) The number of BHS-tree nodes is apparently less than that of HS-tree; (2) As a result of being pruned, the loss of the minimal hitting sets will not produce; (3) When the new conflict sets are inserted, it is unnecessary to rebuild BHS-tree, instead, just adding the new branches to the BHS-tree. This property is extraordinarily useful for the actual diagnosis. Thus, the BHS-tree method is analyzed and verified in theory and the given programs are tested.

Abstract:An algorithm for the drawing of circles is proposed in this paper. It differs greatly from the conventional algorithms that select one pixel per iteration because it can generate at least two pixels every time an I/O operation is executed. The algorithm is presented on the observation that the discrete loci of a circle are composed of a series of horizontal displacements and diagonal displacements. By locating and drawing these displacements one by one, the algorithm can effectively increase the speed of circle drawing due to the great reduction in the number of I/O operations. The experiment results prove that the circle-drawing speed of the algorithm can be almost doubled comparing with of the Bresenham algorithm. Furthermore, the algorithm can be generalized to the production of other conics in computer graphics.

Abstract:A method of color images separation and printing for spot printing technology is presented. A combination of inks for printing images is selected by genetic algorithm according to the information of both original color images and given inks. Then a numerical optimization algorithm is used to compute the separations of color images with customization inks. With the ability of producing the same or more vivid reproduction than tradition four-process color printing with just a small number of inks, this method can be widely applied in many industries such as printing, dying and ceramics trades, etc.

Abstract:In this paper, a linear camera self-calibration technique based on projective reconstruction is proposed. With the camera undergoing at least a pure translation and two arbitrary motions, all the five intrinsic parameters can be obtained. The novelties of the proposed method are three-fold. Firstly, it is a linear one, which does not involve any local minimum problem largely plagued non-linear calibration methods in the literature. Secondly, the proposed method is based on projective reconstruction. Its robustness is markedly increased since all the images are aligned in the projective reconstruction process. Thirdly, the proposed method does not require specialized hardware support, as a result, as a result, can be used in a wide range of applications. For example, in an extreme case, the camera can applicability and feasibility of the proposed method.

Abstract:An on-line structure-learning algorithm of belief network is proposed. The basic idea is to incrementally update the structure and parameters of a belief network after each group of data samples is received. The algorithm consists of two steps. The first step is to update the current belief network based on newly received data samples using incremental updating rules, including parameter incremental updating rule and three structure incremental updating rules, which are adding edge, deleting edge and reverting edge. The second step is to use the result selection criterion to select the most appropriate result from the set of candidates resulted by the first step. The selection criterion fulfills the desire to balance the consistency of the result with the newly received data against the distance between the result and the previous model. Experimental results show that the algorithm can efficiently perform on-line learning of belief network structure. Since on-line learning does not need history data and can adapt to the variation of the problem domain, this algorthm is suitable to model those domains that vary with time.

Abstract:In this paper, the properties of Ada tasking and the correlative state explosion problem are discussed by using the net language. The synchronous composition and decomposition of Ada net is studied, as a result, net language properties are obtained, and the safeness and liveness properties of Ada tasking by using the Ada net language are analyzed and verified, which provide a new and useful way for analyzing and verifying the complex Ada tasking.

Abstract:A drawback of ant colony algorithm is not suitable for solving continuous optimization problems. A method for solving optimization problem in continuous space by using ant colony algorithm is presented. By dividing the space into subdomains, in each iteration of the ant colony algorithm, the method first find the subdomain in which the solution located by using the trail information, then the values of the components in the solution can be determined from the existing solutions in the subdomain. The experimental results on the nonlinear programming problem show that the method has much higher convergence speed than that of GA and SA.

Abstract:Interaction is one of the important features of virtual assembly. In order to promote the system s interactive performance, computer and human should share in cognitive burden in reason. The realization of virtual environment s perceptual mechanism is the critical method towards this objective. In this paper, a formal description of virtual assembly structure is given first, then a perceptual mechanism of compound object is put forward, lastly, a three-stage perception mode is given, and the perceptual process constructions which are needed in virtual assembly application are also analyzed. The desktop virtual assembly practices demonstrate that this perception mechanism has a good real-time interactive characteristic, and it is also a wonderful facility to help understanding user's intention.

Abstract:In this paper, the time complexity of the HEWN algorithm for the maximum clique problem is analyzed. Firstly, a sort of data structure to implement the HEWN algorithm is designed by analyzing the structural characters of HEWN and the needed operations. It is pointed out that the storage structure of HEWN should use the linked list which combine adjacency multi-list with binary linked list. And then, the building procedure of HEWN is anatomized by starting with the storage structure of HEWN. In the anatomizing procedure, by comparing with the MCST, it is pointed out that underlying exponential times of creating and modifying GM exists in the HEWN algorithm when 2j>n. Therefore, the time complexity of the HEWN algorithm is exponential instead of O(n^8.5).

Abstract:In this paper, a solution to reengineering the legacy system based on mobile agent technology is proposed to satisfy the demand of continuous introducing new requirements and techniques into legacy system. An agent viewpoint is adopted to model the legacy system, with the components frequently interacting with others implemented as mobile agent and new requirements added as customized agents. Through the practice of migrating a standalone single-user computing software onto networking platform with the support of several remote user's concurrent accesses, an alternative way of introducing new requirements and technologies into legacy system is proposed.