An accelerated incremental radiosity algorithm

The incremental radiosity method has been shown to be an efficient technique for providing global illumination in dynamic environments as it exploits temporal coherence in object space.This paper presents an accelerated incremental radiosity algorithm,which is based on a dynamically followed partial matrix.This not only reduces the computation cost in determining incremental form-factors when the geometrical relationships between objects are constantly changing,but also simplifies the management of user interaction with comparatively little storage cost.     

An incremental approach to automatic algorithm design

This paper presents an incremental approach to automatic algorithm design,which can be described by algebraic specifications precisely and conveniently.The definitions of selection operator and extension operator which ca be defined by strategy relations and transformations are given in order to model the process of finding the solution of a problem.Also discussed is its object-oriented implementation.The functional specification and the design specification for an algorithm are given in one framework so that the correctness of the algorithm can be easily proved.     

An accelerated K-means clustering algorithm using selection and erasure rules

The K-means method is a well-known clustering algorithm with an extensive range of applications,such as biological classification,disease analysis,data mining,and image compression.However,the plain K-means method is not fast when the number of clusters or the number of data points becomes large.A modified K-means algorithm was presented by Fahim et al.(2006).The modified algorithm produced clusters whose mean square error was very similar to that of the plain K-means,but the execution time was shorter.In this study,we try to further increase its speed.There are two rules in our method:a selection rule,used to acquire a good candidate as the initial center to be checked,and an erasure rule,used to delete one or many unqualified centers each time a specified condition is satisfied.Our clustering results are identical to those of Fahim et al.(2006).However,our method further cuts computation time when the number of clusters increases.The mathematical reasoning used in our design is included.     

A QoS-aware routing algorithm based on ant-cluster in wireless multimedia sensor networks

QoS-aware routing algorithm is important in wireless multimedia sensor networks. This paper formulates a generalized QoS-aware routing model on the basis of multiple routing metrics and priorities of packets. We first introduce a 2D plain-based routing algorithm IPACR which improves the standard ant colony algorithm by optimizing the initial distribution of artificial pheromone in order to accelerate the algorithm convergence rate. Then a clustering-based routing algorithm ICACR is presented which can be well applied in a large scale network. ICACR is a variation of IPACR because it can be suitable for clustering cases to satisfy the larger scale situations. Both the numerical algorithm performance analysis and simulation of IPACR and ICACR are given. The results show that ICACR outperforms IPACR in terms of both network lifetime and QoS-aware routing metrics in large scale wireless multimedia sensor networks. Moreover, the simulation based on the real video traces shows that by extending the multi-path to ICACR for different priorities of video frames better performance can be achieved.     

A Traffic Partition Algorithm for Switched LANs and Its Performance Analysis

An algorithm is proposed which can be used for the topology design of switched LAN with heavy traffic and multi-segments.The main principle of the algorithm is to split the whole traffic to segments as even as possible.The algorithm consists of binary division and ordinary division.When the number of segments equals to powers of 2,binary division is used;ordinary division is based on binary division but suitable to more common cases.Both correctness and time complexity of the algorithm are discussed in detail,and a comparison of the algorithm with the best result is given at the same time.     

Accelerated Backward Warping

In this paper a plane-based backward warping algorithm is proposed to generate novel viwews from multiple reference images.First.depth information is employed to reconstruct space planes from individual refernce images and calculate the potential occluding relationship between these planes.Then the planes which represent each identical space plane from different reference images are compared with each other to decide the one with the best sample rate to be preserved and used in the later warping period while the other samples are abandoned.While the image of a novel view is produced,traditional methods in computer graphics,such as visibility test.and clipping,are used to process the planes reconstructed.Then the planes processed are projected onto the desired image form the knowledge on which plane the desired image pixels are warped from can be acquired.Finally,pixels‘ depth of the desired image is calculated and then a ackwared warping is performed from these pixels to the reference images to obtain their colors.The storage requirement in the algorithm is small and increases slowly with the number of reference images increases.By combining the strategy of only preserving the best sample parts and the backward warping algorithm ,the sample problem could be well tackled.     

Fusion of Data and Knowledge for Safe UAV Landing

Autonomous Unmanned Aerial Vehicles (UAVs) have the potential to significantly improve current working practices for a variety of applications including aerial surveillance and search-and-rescue. However before UAVs can be widely integrated into civilian airspace there are a number of technical challenges which must be overcome including provision of an autonomous method of landing which would be executed in the event of an emergency. A fundamental component of autonomous landing is safe landing zone detection of which terrain classification is a major constituent. Presented in this paper is an extension of the Multi-Modal Expectation Maximization algorithm which combines data in the form of multiple images of the same scene, with knowledge in the form of historic training data and Ordnance Survey map information to compute updated class parameters. These updated parameters are subsequently used to classify the terrain of an area based on the pixel data contained within the images. An image''s contribution to the classification of an area is then apportioned according to its coverage of that area. Preliminary results are presented based on aerial imagery of the Antrim Plateau region in Northern Ireland which indicates potential in the approach used.     

PHC: A Fast Partition and Hierarchy-Based Clustering Algorithm

Cluster analysis is a process to classify data in a specified data set.In this field,much attention is paid to high-efficiency clustering algorithms.In this paper,the features in the current partition-based and hierarchy-based algorithms are reviewed ,and a new bierarchy-based algorithm PHC is proposed by compbining advantages of both algorithms,which uses the cohesion and the colseness to amalgamate the clusters.Compared with similar algorithms,the performance of PHC is improved,and the quality of clustering is guaranteed.And both the features were proved by the theoretic and experimental analyses in the paper.     

An improved self-calibration approach based on adaptive genetic algorithm for position-based visual servo

An improved self-calibrating algorithm for visual servo based on adaptive genetic algorithm is proposed in this paper. Our approach introduces an extension of Mendonca-Cipolla and G. Chesi＇s self-calibration for the positionbased visual servo technique which exploits the singular value property of the essential matrix. Specifically, a suitable dynamic online cost function is generated according to the property of the three singular values. The visual servo process is carried out simultaneous to the dynamic self-calibration, and then the cost function is minimized using the adaptive genetic algorithm instead of the gradient descent method in G. Chesi＇s approach. Moreover, this method overcomes the limitation that the initial parameters must be selected close to the true value, which is not constant in many cases. It is not necessary to know exactly the camera intrinsic parameters when using our approach, instead, coarse coding bounds of the five parameters are enough for the algorithm, which can be done once and for all off-line. Besides, this algorithm does not require knowledge of the 3D model of the object. Simulation experiments are carried out and the results demonstrate that the proposed approach provides a fast convergence speed and robustness against unpredictable perturbations of camera parameters, and it is an effective and efficient visual servo algorithm.     

Squeezer: An efficient algorithm for clustering categorical data

This paper presents a new efficient algorithm for clustering categorical data,Squeezer,which can produce high quality clustering results and at the same time deserve good scalability.The Squeezer algorithm reads each tuple t in sequence,either assigning t to an existing cluster (initially none),or creating t as a new cluster,which is determined by the similarities between t and clusters.Due to its characteristics,the proposed algorithm is extremely suitable for clustering data streams,where given a sequence of points,the objective is to maintain consistently good clustering of the sequence so far,using a small amount of memory and time.Outliers can also be handled efficiently and directly in Squeezer.Experimental results on real-life and synthetic datasets verify the superiority of Squeezer.     

Efficient Hierarchical Refinement and Clustering for Radiosity in Complex Environments

Generating accurate radiosity solutions of very complex environments is a time-consuming problem. We present a rapid hierarchical algorithm that enables such solutions to be computed quickly and efficiently. Firstly, a new technique for bounding the error in the transfer of radiosity between surfaces is discussed, incorporating bounds on form factors, visibility, irradiance, and reflectance over textured surfaces. This technique is then applied to the problem of bounding radiosity transfer between clusters of surfaces, leading to a fast, practical clustering algorithm that builds on the previous work of Sillion¹. Volumes are used to represent clusters of small surfaces, but unlike previous algorithms, the orientations of surfaces inside each cluster are accounted for in both the error bound and radiosity transfer. This enables an accurate solution to be generated very efficiently, and results are presented demonstrating the performance of the algorithm on a variety of complex models, one containing almost a quarter of a million initial surfaces.     

An Exhaustive Error-Bounding Algorithm for Hierarchical Radiosity

This paper presents a complete algorithm for the evaluation and control of error in radiosity calculations. Providing such control is both extremely important for industrial applications andd one of the most challenging issues remaining in global illumination research. In order to control the error, we need to estimate the accuracy of the calculation while computing the energy exchanged between two objects. Having this information for each radiosity interaction allows to allocate more resources to refine interactions with greater potential error, and to avoid spending more time to refine interactions already represented with sufficient accuracy. Until now, the accuracy of the computed energy exchange could only be approximated using heuristic algorithms. This paper presents the first exhaustive algorithm to compute fully reliable upper and lower bounds on the energy being exchanged in each interaction. This is accomplished by computing first and second derivatives of the radiosity function where appropriate, and making use of two concavity conjectures. These bounds are then used in a refinement criterion for hierarchical radiosity, resulting in a global illumination algorithm with complete control of the error incurred. Results are presented, demonstrating the possibility to create radiosity solutions with guaranteed precision. We then extend our algorithm to consider linear bounding functions instead of constant functions, thus creating simpler meshes in regions where the function is concave, without loss of precision. Our experiments show that the computation of radiosity derivatives along with the radiosity values only requires a modest extra cost, with the advantage of a much greater precision.     

Reusable Radiosity Objects

Because of the view independence and photo realistic image generation in a diffuse environment, radiosity is suitable for an interactive walk through system. The drawback of radiosity is that it is time-consuming in form factor estimation, and furthermore, inserting, deleting or moving an object makes the whole costly rendering process repeat itself. To solve this problem, we encapsulate necessary information for form factor calculation and visibility estimation in each object, which is called a reusable radiosity object. An object is defined as a cluster or clusters of triangles. Whenever a scene updates, the radiosity algorithm looks up the prestored information in each object, thus speeding itself up by two orders of magnitude. Besides, solution time based on cluster representatives is linear to the number of objects since each object is reusable, encapsulated with preprocessed data in every level of hierarchy. We also analyze the unregarded error on visibility estimation and propose a statistically optimal adaptive algorithm to maintain the same error for each link.     

A Median Cut Algorithm for Efficient Sampling of Radiosity Functions

This paper presents an efficient method for sampling the illumination functions in higher order radiosity algorithms. In such algorithms, the illumination function is not assumed to be constant across each patch, but it is approximated by a function which is at least C¹ continuous. Our median cut sampling algorithm is inspired by the observation that many form factors are computed at higher precision than is necessary. While a high sampling rate is necessary in regions of high illumination, dark areas can be sampled at a much lower rate to compute the received radiosity within a given precision. We adaptively subdivide the emitter into regions of approximately equal influence on the result. Form factors are evaluated by the disk approximation and a ray tracing based test for occlusion detection. The implementation of a higher order radiosity system using B-splines as radiosity function is described. The median cut algorithm can also be used for radiosity algorithms based on the constant radiosity assumption.     

Data management scheme for parallel radiosity

The radiosity method is a very demanding process in terms of computing and memory resources. To cope with these problems, parallel solutions have been proposed in the literature. A new parallel solution, based on the use of a shared virtual memory, is proposed. It will be shown that this concept of SVM greatly simplifies the implementation of a parallel algorithm since distributed data are managed by the operating system. This new parallel radiosity algorithm has been implemented on an iPSC/2 hypercube using the SVM. The first results obtained with this algorithm are encouraging since the calculated efficiency curve is nearly linear.     

利用球谐方法分散计算场景的全局光照

作为一种特殊的光照模型,辐射度在图形学中有着重要的应用.然而,由于其计算的复杂性,辐射度方法一直得不到广泛的应用,特别是在动态场景中.提出一种基于辐射度算法的全局光照实时加速算法,在原有基于点采样进行场景的全局光照近似的基础上,提出了不同的点采样计算方法,以提高辐射度方法对动画场景的适应性.算法对场景中的物体建立六面体包围盒,并在包围盒各顶点设置采样点,这样就可以在环境变化对其光照影响不大的情况下采用原有的计算结果,实现辐射度算法在动态场景中的计算加速.同时,对场景中的每个物体的光照,利用立方体映射计算直接光照;而对物体间的能量交换采用点采样方法进行近似计算并利用附近采样点的光照插值作为物体的光照.实验结果表明,该算法可以减少大量的间接光照计算,提高了辐射度算法的效率.     

A Radiosity Solution for Curved Surface Environments

Radiosity has been a popular method for photorealistic image generation.But the determination of form factors between curved patches is the most difficult and time consuming procedure,and also the errors caused by approximating source patch‘s radiosity with average values are obvious.In this paper,a radiosity algorithm for rendering curved surfaces represented by parameters is described.The contributed radiosity from differential areas on four vertices of the source patch to a receiving point is calculated firstly,then the contribution from the inner area of the source patch is evaluated by interpolating the values on four corners.Both the difficult problem of determining form-factors between curved surfaces and errors mentioned above have been avoided.Comparison of the experimental results using the new algorithm has been made with the ones obtained by traditional method.Some associated techniques such as the visibility test and the adaptive subdivision are also described.     

Monte Carlo辐射度聚光灯模型

辐射度算法能绘制出更为真实的场景，而近几年发展起来的Monte Carlo辐射度算法可对复杂场景全局光照进行快速、有效的求解，基于Monte Carlo辐射度算法提出了一个精确的方向光源模型，通过直接设置光源角度即可快速生成舞台的聚光灯效果。     

Animating radiosity environments through the Multi‐Frame Lighting Method

Realistic rendering animation is known to be an expensive processing task when physically based global illumination methods are used in order to improve illumination details. This paper presents the Multi‐Frame Lighting Method, an efficient algorithm to compute animations in radiosity environments. The method, based on global Monte Carlo techniques, performs the lighting simulation of groups of consecutive frames in a single process. All frames computed have the same accuracy as if they were computed independently while a significant high speed‐up is achieved. Results show that the method it is an interesting alternative for computing non‐interactive radiosity animations for moderately complex scenarios. Copyright © 2001 John Wiley &Sons, Ltd.