Approximating Functions on a Mesh with Restricted Voronoï Diagrams

We propose a method that computes a piecewise constant approximation of a function defined on a mesh. The approximation is associated with the cells of a restricted Voronoï diagram. Our method optimizes an objective function measuring the quality of the approximation. This objective function depends on the placement of the samples that define the restricted Voronoï diagram and their associated function values. We study the continuity of the objective function, derive the closed‐form expression of its derivatives and use them to design a numerical solution mechanism. The method can be applied to a function that has discontinuities, and the result aligns the boundaries of the Voronoï cells with the discontinuities. Some examples are shown, suggesting potential applications in image vectorization and compact representation of lighting.     

Procedural Generation of Rock Piles using Aperiodic Tiling

In this paper, we present a tiling method for generating piles of rocks without any computationally demanding physically‐based simulation. Previous techniques rely on a periodic tiling of rocks and generate unrealistic repetitive patterns. In contrast, our approach relies on a modified corner cube algorithm to generate a set of aperiodic tiles. We generalize the construction method so that the geometry of rocks should straddle corner cubes with a view to avoiding unrealistic gaps in the arrangement of rocks. Moreover, we propose an original technique to control the shape of rocks into contact by computing the Voronoï cells using a parameterized anisotropic distance. Our method has been successfully used to generate landscapes and stone huts and walls with thousands of rocks piled together.     

Intelligent computation offloading for educational virtual reality applications in smart campus using MoCell

Nowadays, as the smart campus concept becomes a reality, virtual reality (VR) applications are being applied to connect students with the virtual teaching world via VR devices (VDs), enhancing learning efficiency. Nevertheless, VR applications are latency-sensitive while VDs are subjected to shortcomings to handle many VR applications simultaneously. Fortunately, mobile edge computing (MEC) has been recognized as a promising solution that can bring abundant resources to VDs to relieve hardware limits. However, the computing resources of edge nodes in MEC are limited, and thus how to allocate resources effectively is critical. Meanwhile, some sensitive information of students collected by VD needs to be protected. In view of this, we investigate computation offloading for educational VR applications in MEC-enabled smart campus. The aims of this issue are to optimize the motion-to-photon latency, energy consumption, and resource utilization while satisfying the privacy and security constraints. To this end, we propose a new multi-objective optimization method using MoCell. Eventually, the experimental evaluations are designed to illustrate the effectiveness and superiority our proposed method.     

Medial axis computation for planar free-form shapes

We present a simple, efficient, and stable method for computing—with any desired precision—the medial axis of simply connected planar domains. The domain boundaries are assumed to be given as polynomial spline curves. Our approach combines known results from the field of geometric approximation theory with a new algorithm from the field of computational geometry. Challenging steps are (1) the approximation of the boundary spline such that the medial axis is geometrically stable, and (2) the efficient decomposition of the domain into base cases where the medial axis can be computed directly and exactly. We solve these problems via spiral biarc approximation and a randomized divide & conquer algorithm.     

Meshing volumes with curved boundaries

This paper introduces a three-dimensional mesh generation algorithm for domains whose boundaries are curved surfaces, possibly with sharp features. The algorithm combines a Delaunay-based surface mesher with a Ruppert-like volume mesher, resulting in a greedy scheme to sample the interior and the boundary of the domain simultaneously. The algorithm constructs provably good meshes, it gives control on the size of the mesh elements through a user-defined sizing field, and it guarantees the accuracy of the approximation of the domain boundary. A notable feature is that the domain boundary has to be known only through an oracle that can tell whether a given point lies inside the object and whether a given line segment intersects the boundary. This makes the algorithm generic enough to be applied to domains with a wide variety of boundary types, such as implicit surfaces, polyhedra, level-sets in 3D gray-scaled images, or point-set surfaces.     

Exploiting Voronoi diagram properties in face segmentation and feature extraction

Segmentation of human faces from still images is a research field of rapidly increasing interest. Although the field encounters several challenges, this paper seeks to present a novel face segmentation and facial feature extraction algorithm for gray intensity images (each containing a single face object). Face location and extraction must first be performed to obtain the approximate, if not exact, representation of a given face in an image. The proposed approach is based on the Voronoi diagram (VD), a well-known technique in computational geometry, which generates clusters of intensity values using information from the vertices of the external boundary of Delaunay triangulation (DT). In this way, it is possible to produce segmented image regions. A greedy search algorithm looks for a particular face candidate by focusing its action in elliptical-like regions. VD is presently employed in many fields, but researchers primarily focus on its use in skeletonization and for generating Euclidean distances; this work exploits the triangulations (i.e., Delaunay) generated by the VD for use in this field. A distance transformation is applied to segment face features. We used the BioID face database to test our algorithm. We obtained promising results: 95.14% of faces were correctly segmented; 90.2% of eyes were detected and a 98.03% detection rate was obtained for mouth and nose.     

基于双语信息和标签传播算法的中文情感词典构建方法

文本情感分析是目前自然语言处理领域的一个热点研究问题,具有广泛的实用价值和理论研究意义。情感词典构建则是文本情感分析的一项基础任务,即将词语按照情感倾向分为褒义、中性或者贬义。然而,中文情感词典构建存在两个主要问题 1)许多情感词存在多义、歧义的现象,即一个词语在不同语境中它的语义倾向也不尽相同,这给词语的情感计算带来困难;2)由国内外相关研究现状可知,中文情感字典建设的可用资源相对较少。考虑到英文情感分析研究中存在大量语料和词典,该文借助机器翻译系统,结合双语言资源的约束信息,利用标签传播算法(LP)计算词语的情感信息。在四个领域的实验结果显示我们的方法能获得一个分类精度高、覆盖领域语境的中文情感词典。     

A 2D and 3D discrete bisector function based on annulus

The bisector function is an important tool for analyzing and filtering Euclidean skeletons. In this paper, we are proposing a new way to compute 2D and 3D discrete bisector function based on annuli. From a continuous point of view, a point that belongs to the medial axis is the center of a maximal ball that hits the background in more than one point. The maximal angle between those points is expected to be high for most of the object points and corresponds to the bisector angle. This logic is not really applicable in the discrete space since we may miss some background points that can lead to small bisector angles. In this work we use annuli to find the background points in order to compute the bisector angle. Our approach offers the possibility to change the thickness of the annulus at a given point and is thus flexible when computing skeletons. Our work can be extended to nD and we propose the nD algorithm.

     

Efficient implementation of multiprocessor scheduling algorithms on a simulation testbed

A layered and modular approach to implementing a process‐oriented simulator testbed is described. The simulation kernel is supported by a threads library and is, in turn, capable of supporting distinct domains or application areas for various applications. The testbed offers an implementation methodology for testing novel simulation algorithms at the domain level, without interfacing with the kernel. To demonstrate its utility, a novel algorithm for simulating multiprocessing with round‐robin scheduling is presented. The algorithm is more complex than the naïve round‐robin implementation in use, but offers significant performance improvement. Copyright © 2004 John Wiley & Sons, Ltd.     

A Path-Consistent Singleton Modeling (CSM) Algorithm for Arc-Constrained Networks

There is very little of time in a temporal constraint propagation algorithm. Most of these algorithms could easily handle reasoning over any domain mapable onto rational numbers, e.g., weight, frequency, luminosity, etc. Actually some of these algorithms are capable of handling more sophisticated domains than those mapped onto rational numbers, e.g., intervals, or partially ordered objects (say, time). In this article we have generalized such an algorithm, which was originally developed for time-interval domain, to any generic domain, where binary constraints are expressed over arcs of the constraint network. Given the composition table for the primitive relations between a pair of the domain entities (e.g., intervals) as an additional input along with a constraint graph, the algorithm would generate all consistent singleton models for a given network. The algorithm is also extended here to handle uncertainty values.     

Online transfer learning by leveraging multiple source domains

Transfer learning aims to enhance performance in a target domain by exploiting useful information from auxiliary or source domains when the labeled data in the target domain are insufficient or difficult to acquire. In some real-world applications, the data of source domain are provided in advance, but the data of target domain may arrive in a stream fashion. This kind of problem is known as online transfer learning. In practice, there can be several source domains that are related to the target domain. The performance of online transfer learning is highly associated with selected source domains, and simply combining the source domains may lead to unsatisfactory performance. In this paper, we seek to promote classification performance in a target domain by leveraging labeled data from multiple source domains in online setting. To achieve this, we propose a new online transfer learning algorithm that merges and leverages the classifiers of the source and target domain with an ensemble method. The mistake bound of the proposed algorithm is analyzed, and the comprehensive experiments on three real-world data sets illustrate that our algorithm outperforms the compared baseline algorithms.     

Dynamic Voronoi diagram of complex sites

The Voronoi diagram (VD) is a fundamental geometric structure in many applications. There are fast and simple algorithms to construct the VD of static point sets. For complex sites (i.e., other than points) the algorithms are more sophisticated, and a few efficient solutions exist. However, updating the VD of dynamic sites is still challenging, and efficient solutions exist only for points. We propose an algorithm for constructing and updating the VD of large dynamic sets of complex sites. Although existing incremental algorithms allow fast insertion of complex sites, this work presents the first efficient implementation of the removal operation.     

Cost-optimal parallel algorithms for the tree bisector and relatedproblems

An edge is a bisector of a simple path if it contains the middle point of the path. Let T=(V,E) be a tree. Given a source vertex s ∈ V, the single-source tree bisector problem is to find, for every vertex υ ∈ V, a bisector of the simple path from s to υ. The all-pairs tree bisector problem is to find for, every pair of vertices u, υ ∈ V, a bisector of the simple path from u to υ. In this paper, it is first shown that solving the single-source tree bisector problem of a weighted tree has a time lower bound Ω(n log n) in the sequential case. Then, efficient parallel algorithms are proposed on the EREW PRAM for the single-source and all-pairs tree bisector problems. Two O(log n) time single-source algorithms are proposed. One uses O(n) work and is for unweighted trees. The other uses O(n log n) work and is for weighted trees. Previous algorithms for the single-source problem could achieve the same time O(log n) and the same optimal work, O(n) for unweighted trees and O(n log n) for weighted trees, on the CRCW PRAM. The contribution of our single-source algorithms is the improvement from CRCW to EREW. One all-pairs parallel algorithm is proposed. It requires O(log n) time using O(n²) work. All the proposed algorithms are cost-optimal. Efficient tree bisector algorithms have practical applications to several location problems on trees. Using the proposed algorithms, efficient parallel solutions for those problems are also presented     

Space-time light field rendering

In this paper, we propose a novel framework called space-time light field rendering, which allows continuous exploration of a dynamic scene in both space and time. Compared to existing light field capture/rendering systems, it offers the capability of using unsynchronized video inputs and the added freedom of controlling the visualization in the temporal domain, such as smooth slow motion and temporal integration. In order to synthesize novel views from any viewpoint at any time instant, we develop a two-stage rendering algorithm. We first interpolate in the temporal domain to generate globally synchronized images using a robust spatial-temporal image registration algorithm followed by edge-preserving image morphing. We then interpolate these software-synchronized images in the spatial domain to synthesize the final view. In addition, we introduce a very accurate and robust algorithm to estimate subframe temporal offsets among input video sequences. Experimental results from unsynchronized videos with or without time stamps show that our approach is capable of maintaining photorealistic quality from a variety of real scenes.     

3D clipping algorithm for feature mapping across domains

This paper describes an algorithm based on 3D clipping for mapping feature models across domains. The problem is motivated by the need to identify feature models corresponding to different domains. Feature mapping (also referred to as feature conversion) involves obtaining a feature model in one domain given a feature model in another. This is in contrast to feature extraction which works from the boundary representation of the part. Most techniques for feature mapping have focused on obtaining negative feature models only. We propose an algorithm that can convert a feature model with mixed features (both positive and negative) to a feature model containing either only positive or only negative features.The input to the algorithm is a feature model in one domain. The algorithm for mapping this model to another feature model is based on classification of faces of features in the model and 3D clipping. 3D clipping refers to the splitting of a solid by a surface. The feature mapping process involves three major steps. In the first step, faces forming the features in the input model are classified with respect to one another. The spatial arrangement of faces is used next to derive the dependency relationship amongst features in the input model and a Feature Relationship Graph (FRG) is constructed. In the second step, using the FRG, features are clustered and interactions between features (if any) are resolved. In the final step, the 3D clipping algorithm is used to determine the volumes corresponding to the features in the target domain. These volumes are then classified to identify the features for obtaining the feature model in the target domain. Multiple feature sets (where possible) can be obtained by varying the sequence of faces used for clipping. Results of implementation are presented.     

A Hybrid End-to-End QoS Path Computation Algorithm for PCE-Based Multi-Domain Networks

Inter-domain quality of service (QoS) routing is a challenging problem for today’s Internet. This problem requires the computation of paths that cross multiple domains and meet different QoS constraints. In addition, the used computation methods must meet the constraints of confidentiality and autonomy imposed by the domains of different operators. Path computation element (PCE)-based architecture offers a promising solution for inter-domain QoS routing. It ensures the computation of end-to-end QoS paths while preserving the confidentiality and the autonomy of the domains. In this paper, we propose a novel hybrid end-to-end QoS path computation algorithm, named HID-MCP, for PCE-based networks. HID-MCP is a hybrid algorithm that combines the advantages of pre-computation and on-demand computation to obtain end-to-end QoS paths. Moreover, it integrates a crankback mechanism for improving path computation results in a single domain or in multiple domains based on the PCE architecture. Detailed analyses are provided to assess the performance of our algorithm in terms of success rate and computational complexity. The simulation results show that our algorithm has an acceptance rate of the requests very close to the optimal solution; precisely, the difference is lower than 1 % in a realistic network. Moreover, HID-MCP has a low computational complexity. Besides, our solution relies on the PCE architecture to overcome the limitations related to inter-domain routing such as domain autonomy and confidentiality.     

A robust ant colony optimization for continuous functions

Ant colony optimization (ACO) for continuous functions has been widely applied in recent years in different areas of expert and intelligent systems, such as steganography in medical systems, modelling signal strength distribution in communication systems, and water resources management systems. For these problems that have been addressed previously, the optimal solutions were known a priori and contained in the pre-specified initial domains. However, for practical problems in expert and intelligent systems, the optimal solutions are often not known beforehand. In this paper, we propose a robust ant colony optimization for continuous functions (RACO), which is robust to domains of variables. RACO applies self-adaptive approaches in terms of domain adjustment, pheromone increment, domain division, and ant size without any major conceptual change to ACO's framework. These new characteristics make the search of ants not limited to the given initial domain, but extended to a completely different domain. In the case of initial domains without the optimal solution, RACO can still obtain the correct result no matter how the initial domains vary. In the case of initial domains with the optimal solution, we also show that RACO is a competitive algorithm. With the assistance of RACO, there is no need to estimate proper initial domains for practical continuous optimization problems in expert and intelligent systems.     

A New Approach for the Geodesic Voronoi Diagram of Points in a Simple Polygon and Other Restricted Polygonal Domains

We introduce a new method for computing the geodesic Voronoi diagram of point sites in a simple polygon and other restricted polygonal domains. Our method combines a sweep of the polygonal domain with the merging step of a usual divide-and-conquer algorithm. The time complexity is O((n+k) log(n+k)) where n is the number of vertices and k is the number of points, improving upon previously known bounds. Space is O(n+k) . Other polygonal domains where our method is applicable include (among others) a polygonal domain of parallel disjoint line segments and a polygonal domain of rectangles in the L ₁ metric. Received February 15, 1996; revised November 2, 1996.