Search

Recently, there has been renewed interest in signed distance bound representations due to their unique properties for 3D shape modelling. This is especially the case for deep learning-based bounds. However, it is beneficial to work with polygons in most computer graphics applications. Thus, in this paper, we introduce and investigate an asymptotically fast method for transforming signed distance bounds into polygon meshes. This is achieved by combining the principles of sphere tracing (or ray marching) with traditional polygonization techniques, such as marching cubes. We provide theoretical and experimental evidence that this approach is of the O (N 2 log N) computational complexity for a polygonization grid with N 3 cells. The algorithm is tested on both a set of primitive shapes and signed distance bounds generated from point clouds by machine learning (and represented as neural networks). Given its speed, implementation simplicity, and portability, we argue that it could prove useful during the modelling stage as well as in shape compression for storage. [ABSTRACT FROM AUTHOR]

As we know, image colorization is widely used in computer graphics and has become a research hotspot in the field of image processing. Current image colorization technology has the phenomenon of single coloring effect and unreal color, which is too complicated to be implemented and struggled to gain popularity. In this paper, a new method based on a convolution neural network is proposed to study the reasonable coloring of human images and ensures the realism of the coloring effect and the diversity of coloring at the same time. First, this paper selects about 5000 pictures of people and plants from the Imagenet dataset and makes a small dataset containing only people and backgrounds. Secondly, in order to obtain the image segmentation results, this paper improves the U-net network and carries out three times of down sampling and three times of up-sampling. Finally, we add the expanded convolution, and use the sigmoid activation function to replace the ReLU (The Rectified Linear Unit) activation function and put the BN (Batch Normalization) before the activation function. Experimental results show that our proposed image colorization algorithm based on the deep learning scheme can reduce the training time of the network and achieve higher quality segmentation results. [ABSTRACT FROM AUTHOR]

Due to advances in high-performance computing technologies, computer graphics techniques—especially those related to mesh simplification—have been noticeably improved. These techniques, which have a strong impact on many applications, such as geometric modeling and visualization, have been well studied for more than two decades. Recent advances in GPUs have led to significant improvements in terms of speed and interactivity. In this paper, we present a mesh simplification algorithm that benefits from the parallel framework provided by recent GPUs. We customize the halfedge data structure for adaption with the dynamic memory restrictions of CUDA. The proposed algorithm is fully parallelized by employing a lock-free skip priority queue and a set of disjoint regions of the mesh. The proposed technique accelerates the simplification process while preserving the topological properties of the mesh. Some results and comparisons are provided to verify the efficiency of the proposed algorithm. [ABSTRACT FROM AUTHOR]

The objective of this paper is to apply clipping techniques on natural images and to analyze the performance of various clipping algorithms in computer graphics. The clipping techniques used in this paper is Cohen–Sutherland line clipping, Liang–Barsky line clipping, Nicholl–Lee–Nicholl line clipping and Sutherland–Hodgman polygon clipping. The clipping algorithms are evaluated by using the three parameters: time complexity, space complexity and image accuracy. Previously, there is no performance evaluation on clipping algorithms done. Motivating by this factor, in this paper an evaluation of clipping algorithms is made. The novelty of this paper is to apply the clipping algorithms on natural images. It is justified that the above mentioned clipping algorithms outperform well on clipping the natural images. [ABSTRACT FROM AUTHOR]

• Introduction of Riemannian global illumination. • A path tracer algorithm to approximate the solution of the Riemannian global illumination. • A map of the algorithm to the GPU, using the RTX platform. • We apply the Non-Euclidean path tracer to render "Photorealistic" inside views of the 3D flat torus, Poincaré sphere, and the hyperbolic mirrored dodecahedron. These are examples of the Euclidean, spherical, and hyperbolic spaces: the Thurston classical geometries. This paper presents a novel path tracer algorithm for immersive visualization of Riemannian manifolds. To do this, we introduce Riemannian illumination, a generalization of classical Computer Graphics illumination models. In this context, global light transport is expressed by extending the rendering equation to Riemannian manifolds. Using Monte Carlo integration to solve this equation results in the novel path tracer for Non-Euclidean spaces. We discuss its basic principles, as well as the general CPU algorithm. Additionally, we discuss in detail how to implement a GPU version, using the RTX pipeline. Finally, we apply the algorithm to render "photorealistic" inside views of the flat torus, Poincaré sphere, and the hyperbolic mirrored dodecahedron. These are examples of Euclidean, spherical, and hyperbolic spaces: the Thurston classical geometries. [ABSTRACT FROM AUTHOR]

Accurate and efficient methods for large-scale urban reconstruction are of significant importance to the computer vision and computer graphics communities. Although rapid acquisition techniques such as airborne LiDAR have been around for many years, creating a useful and functional virtual environment from such data remains difficult and labor intensive. This is due largely to the necessity in present solutions for data dependent user defined parameters. In this paper we present a new solution for automatically converting large LiDAR data pointcloud into simplified polygonal 3D models. The data is first divided into smaller components which are processed independently and concurrently to extract various metrics about the points. Next, the extracted information is converted into tensors. A robust agglomerate clustering algorithm is proposed to segment the tensors into clusters representing geospatial objects e.g., roads, buildings, etc. Unlike previous methods, the proposed tensor clustering process has no data dependencies and does not require any user-defined parameter. The required parameters are adaptively computed assuming a Weibull distribution for similarity distances. Lastly, to extract boundaries from the clusters a new multi-stage boundary refinement process is developed by reformulating this extraction as a global optimization problem. We have extensively tested our methods on several pointcloud datasets of different resolutions which exhibit significant variability in geospatial characteristics e.g., ground surface inclination, building density, etc and the results are reported. The source code for both tensor clustering and global boundary refinement will be made publicly available with the publication on the author's website. [ABSTRACT FROM AUTHOR]

Curved surface mesh generation is a key step for many areas. Here, a mesh generation algorithm for closed curved surface based on Delaunay refinement is proposed. We focus on improving the shape quality of the meshes generated and making them conform to 2-manifold. The Delaunay tetrahedralization of initial sample is generated first, the initial surface mesh which is a subset of the Delaunay tetrahedralization can be achieved. A triangle is refined by inserting a new point if it is large or of bad quality. For each sample, we also check the triangles that adjoin it whether from a topological disk. If not, the largest triangle will be refined. Finally, the surface mesh is updated after a new point is inserted into the sample. The definition of mesh size function for surface mesh generation is also put in this paper. Meshing experiments of some models demonstrate that the new algorithm is advantageous in generating high quality surface mesh, the count of mesh is suitable and can well approximate the curved surface. The presented method can be used for a wide range of problems including computer graphics, computer vision and finite element method. [ABSTRACT FROM AUTHOR]

B-spline functions are widely used in many industrial applications such as computer graphic representations, computer aided design, computer aided manufacturing, computer numerical control, etc. Recently, there exist some demands, e.g. in reverse engineering (RE) area, to employ B-spline curves for non-trivial cases that include curves with discontinuous points, cusps or turning points from the sampled data. The most challenging task in these cases is in the identification of the number of knots and their respective locations in non-uniform space in the most efficient computational cost. This paper presents a new strategy for fitting any forms of curve by B-spline functions via local algorithm. A new two-step method for fast knot calculation is proposed. In the first step, the data is split using a bisecting method with predetermined allowable error to obtain coarse knots. Secondly, the knots are optimized, for both locations and continuity levels, by employing a non-linear least squares technique. The B-spline function is, therefore, obtained by solving the ordinary least squares problem. The performance of the proposed method is validated by using various numerical experimental data, with and without simulated noise, which were generated by a B-spline function and deterministic parametric functions. This paper also discusses the benchmarking of the proposed method to the existing methods in literature. The proposed method is shown to be able to reconstruct B-spline functions from sampled data within acceptable tolerance. It is also shown that, the proposed method can be applied for fitting any types of curves ranging from smooth ones to discontinuous ones. In addition, the method does not require excessive computational cost, which allows it to be used in automatic reverse engineering applications. [ABSTRACT FROM AUTHOR]

Bilateral filter is an edge-preserving smoother that has applications in image processing, computer vision, and computational photography. In the past, field-programmable gate array (FPGA) implementations of the filter have been proposed that can achieve high throughput using parallelization and pipelining. An inherent limitation with direct implementations is that their complexity scales as $O(\omega ^2)$ with the filter width $\omega$ . In this paper, we propose an FPGA implementation of a fast bilateral filter that requires just $O(1)$ operations for any arbitrary $\omega$. The attractive feature of the FPGA implementation is that it is both scalable and reconfigurable. To the best of our knowledge, this is the first scalable FPGA implementation of the bilateral filter. As an application, we use the FPGA implementation for image denoising. [ABSTRACT FROM PUBLISHER]

From object tracking to 3D reconstruction, RGB-Depth (RGB-D) camera networks play an increasingly important role in many vision and graphics applications. Practical applications often use sparsely-placed cameras to maximize visibility, while using as few cameras as possible to minimize cost. In general, it is challenging to calibrate sparse camera networks due to the lack of shared scene features across different camera views. In this paper, we propose a novel algorithm that can accurately and rapidly calibrate the geometric relationships across an arbitrary number of RGB-D cameras on a network. Our work has a number of novel features. First, to cope with the wide separation between different cameras, we establish view correspondences by using a spherical calibration object. We show that this approach outperforms other techniques based on planar calibration objects. Second, instead of modeling camera extrinsic calibration using rigid transformation, which is optimal only for pinhole cameras, we systematically test different view transformation functions including rigid transformation, polynomial transformation and manifold regression to determine the most robust mapping that generalizes well to unseen data. Third, we reformulate the celebrated bundle adjustment procedure to minimize the global 3D reprojection error so as to fine-tune the initial estimates. Finally, our scalable client-server architecture is computationally efficient: the calibration of a five-camera system, including data capture, can be done in minutes using only commodity PCs. Our proposed framework is compared with other state-of-the-arts systems using both quantitative measurements and visual alignment results of the merged point clouds. [ABSTRACT FROM AUTHOR]

Haptics applications such as surgery simulations require collision detections that are more precise than others. An efficient collision detection method based on the clustering of bounding spheres was proposed in our prior study. This paper analyzes and compares the applied effects of the five most common subdivision surface methods on some 3D models for haptic collision detection. The five methods are Butterfly, Catmull-Clark, Mid-point, Loop, and LS3 (Least Squares Subdivision Surface). After performing a number of experiments, we have concluded that LS3 method is the most appropriate for haptic simulations. The more we applied surface subdivision, the more the collision detection results became precise. However, it is observed that the performance becomes better until a certain threshold and degrades afterward. In order to reduce the performance degradation, we adopted our prior work, which was the fast and precise collision detection method based on adaptive clustering. As a result, we obtained a notable improvement of the speed of collision detection. [ABSTRACT FROM AUTHOR]

Heterogeneous information networks (e.g. bibliographic networks and social media networks) that consist of multiple interconnected objects are ubiquitous. Clustering analysis is an effective method to understand the semantic information and interpretable structure of the heterogeneous information networks, and it has attracted the attention of many researchers in recent years. However, most studies assume that heterogeneous information networks usually follow some simple schemas, such as bi-typed networks or star network schema, and they can only cluster one type of object in the network each time. In this paper, a novel clustering framework is proposed based on sparse tensor factorization for heterogeneous information networks, which can cluster multiple types of objects simultaneously in a single pass without any network schema information. The types of objects and the relations between them in the heterogeneous information networks are modeled as a sparse tensor. The clustering issue is modeled as an optimization problem, which is similar to the well-known Tucker decomposition. Then, an Alternating Least Squares (ALS) algorithm and a feasible initialization method are proposed to solve the optimization problem. Based on the tensor factorization, we simultaneously partition different types of objects into different clusters. The experimental results on both synthetic and real-world datasets have demonstrated that our proposed clustering framework, STFClus, can model heterogeneous information networks efficiently and can outperform state-of-the-art clustering algorithms as a generally applicable single-pass clustering method for heterogeneous network which is network schema agnostic. [ABSTRACT FROM AUTHOR]

Sometimes, in computer graphics, there is a need to show a part or a piece of a specific picture to study it accurately. For this purpose a window can be used to select the interested part of the picture for display out of other parts. This window is called a clipping window and this process is called a clipping process .On the other hand, clipping is required when a part of a moving image becomes out of the visible zone for display. So the clipping process is one of the important issues in the field of computer graphic specially for real time applications. Therefore a study of the line clipping with respect to a rectangular window while looking to various methods to achieve clipping process in the image space is presented in this paper. In addition to that, performance measurements are conducted and compared. The paper develops a method to perform clipping in the object space in which the line segment is clipped against a viewing volume. Finally, pipelining is adopted to realize clipping algorithm in hardware. [ABSTRACT FROM AUTHOR]

Abstract: This paper presents a new method to control scene sampling in complex ray-based rendering environments. It proposes to constrain image sampling density with a combination of object features, which are known to be well perceived by the human visual system, and image space saliency, which captures effects that are not based on the object''s geometry. The presented method uses Non-Photorealistic Rendering techniques for the object space feature evaluation and combines the image space saliency calculations with image warping to infer quality hints from previously generated frames. In order to map different feature types to sampling densities, we also present an evaluation of the object space and image space features'' impact on the resulting image quality. In addition, we present an efficient, adaptively aligned fractal pattern that is used to reconstruct the image from sparse sampling data. Furthermore, this paper presents an algorithm which uses our method in order to guarantee a desired minimal frame rate. Our scheduling algorithm maximizes the utilization of each given time slice by rendering features in the order of visual importance values until a time constraint is reached. We demonstrate how our method can be used to boost or stabilize the rendering time in complex ray-based image generation consisting of geometric as well as volumetric data. [Copyright &y& Elsevier]

To achieve realistic Augmented Reality (AR), shadows play an important role in creating a 3D impression of a scene. Casting virtual shadows on real and virtual objects is one of the topics of research being conducted in this area. In this paper, we propose a new method for creating complex AR indoor scenes using real time depth detection to exert virtual shadows on virtual and real environments. A Kinect camera was used to produce a depth map for the physical scene mixing into a single real-time transparent tacit surface. Once this is created, the camera’s position can be tracked from the reconstructed 3D scene. Real objects are represented by virtual object phantoms in the AR scene enabling users holding a webcam and a standard Kinect camera to capture and reconstruct environments simultaneously. The tracking capability of the algorithm is shown and the findings are assessed drawing upon qualitative and quantitative methods making comparisons with previous AR phantom generation applications. The results demonstrate the robustness of the technique for realistic indoor rendering in AR systems. [ABSTRACT FROM AUTHOR]

Saliency detection is an important preprocessing step in many application fields such as computer vision, robotics, and graphics to reduce computational cost by focusing on significant positions and neglecting the nonsignificant in the scene. Different from most previous methods which mainly utilize the contrast of low-level features, various feature maps are fused in a simple linear weighting form. In this paper, we propose a novel salient object detection algorithm which takes both background and foreground cues into consideration and integrate a bottom-up coarse salient regions extraction and a top-down background measure via boundary labels propagation into a unified optimization framework to acquire a refined saliency detection result. Wherein the coarse saliency map is also fused by three components, the first is local contrast map which is in more accordance with the psychological law, the second is global frequency prior map, and the third is global color distribution map. During the formation of background map, first we construct an affinity matrix and select some nodes which lie on border as labels to represent the background and then carry out a propagation to generate the regional background map. The evaluation of the proposed model has been implemented on four datasets. As demonstrated in the experiments, our proposed method outperforms most existing saliency detection models with a robust performance. [ABSTRACT FROM AUTHOR]

The exposure of an organisation's illegal or unethical practices is often known as whistleblowing. It is currently a high-profile activity as a consequence of whistleblowing websites such as Wikileaks. However, modern digital fingerprinting technologies allow the identification of the human users associated with a particular copy of a leaked digital file. Fear of such discovery may discourage the public from exposing illegal or unethical practices. This paper therefore introduces the novel whistleblower-defending problem, a unique variant of the existing document marking and traitor-tracing problems. It is addressed here by outlining practical steps that real-world whistleblowers can take to improve their safety, using only standard desktop OS features. ZIP compression is found to be useful for indirect file comparison, n cases where direct file comparison or use of checksums is impossible, inconvenient or easily traceable. The methods of this paper are experimentally evaluated and found to be effective. [ABSTRACT FROM AUTHOR]

This paper proposes a spectral-graph-based algorithm for face image repairing, which can improve the recognition performance on occluded faces. The face completion algorithm proposed in this paper includes three main procedures: 1) sparse representation for partially occluded face classification; 2) image-based data mining; and 3) graph Laplace (GL) for face image completion. The novel part of the proposed framework is GL, as named from graphical models and the Laplace equation, and can achieve a high-quality repairing of damaged or occluded faces. The relationship between the GL and the traditional Poisson equation is proven. We apply our face repairing algorithm to produce completed faces, and use face recognition to evaluate the performance of the algorithm. Experimental results verify the effectiveness of the GL method for occluded face completion. [ABSTRACT FROM PUBLISHER]

Text line segmentation is an essential stage in off-line optical character recognition (OCR) systems. It is a key because inaccurately segmented text lines will lead to OCR failure. Text line segmentation of handwritten documents is a complex and diverse problem, complicated by the nature of handwriting. Hence, text line segmentation is a leading challenge in handwritten document image processing. Due to inconsistencies in measurement and evaluation of text segmentation algorithm quality, some basic set of measurement methods is required. Currently, there is no commonly accepted one and all algorithm evaluation is custom oriented. In this paper, a basic test framework for the evaluation of text feature extraction algorithms is proposed. This test framework consists of a few experiments primarily linked to text line segmentation, skew rate and reference text line evaluation. Although they are mutually independent, the results obtained are strongly cross linked. In the end, its suitability for different types of letters and languages as well as its adaptability are its main advantages. Thus, the paper presents an efficient evaluation method for text analysis algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Interpolating scalar refinable functions with compact support are of interest in several applications such as sampling theory, signal processing, computer graphics, and numerical algorithms. In this paper, we shall generalize the notion of interpolating scalar refinable functions to compactly supported interpolating -refinable function vectors with any multiplicity and dilation factor . More precisely, we are interested in a -refinable function vector such that is an column vector of compactly supported continuous functions with the following interpolation property where and for . Now for any function , the function can be interpolated and approximated by Since is interpolating, for all , that is, agrees with on . Moreover, for or , such interpolating refinable function vectors can have the additional orthogonality property: for all and , while it is well-known that there does not exist a compactly supported scalar 2-refinable function with both the interpolation and orthogonality properties simultaneously. In this paper, we shall characterize both interpolating -refinable function vectors and orthogonal interpolating -refinable function vectors in terms of their masks. We shall study their approximation properties and present a family of interpolatory masks, for compactly supported interpolating -refinable function vectors, of type with increasing orders of sum rules. To illustrate the results in this paper, we also present several examples of compactly supported (orthogonal) interpolating refinable function vectors and biorthogonal multiwavelets derived from such interpolating refinable function vectors. [Copyright &y& Elsevier]

Sparse representations of signals have drawn considerable interest in recent years. The assumption that natural signals, such as images, admit a sparse decomposition over a redundant dictionary leads to efficient algorithms for handling such sources of data. In particular, the design of well adapted dictionaries for images has been a major challenge. The K-SVD has been recently proposed for this task [1] and shown to perform very well for various grayscale image processing tasks. In this paper, we address the problem of learning dictionaries for color images and extend the K-SVD-based grayscale image denoising algorithm that appears in [21. This work puts forward ways for handling nonhomogeneous noise and missing information, paving the way to state-of-the-art results in applications such as color image denoising, demosaicing, and inpainting, as demonstrated in this paper. [ABSTRACT FROM AUTHOR]

In this paper, we consider the problem of sampling signals that are nonband-limited but have finite number of degrees of freedom per unit of time and call this number the rate of innovation. Streams of Diracs and piecewise polynomials are the examples of such signals, and thus are known as signals with finite rate of innovation (FR!). We know that the classical ("band-limited sinc") sampling theory does not enable perfect reconstruction of such signals from their samples since they are not band-limited. However, the recent results on FR! sampling suggest that it is possible to sample and perfectly reconstruct such nonband-limited signals using a rich class of kernels. In this paper, we extend those results in higher dimensions using compactly supported kernels that reproduce polynomials (satisfy Strang-Fix conditions). In fact, the polynomial reproduction property of the kernel makes it possible to obtain the continuous moments of the signal from its samples. Using these moments and the annihilating filter method (Prony's method), the innovative part of the signal, and therefore, the signal itself is perfectly reconstructed. In particular, we present local (directional-derivatives-based) and global (complex-moments-based, Radon-transform-based) sampling schemes for classes of FRI signals such as sets of Diracs, bilevel, and planar polygons, quadrature domains (e.g., circles, ellipses, and cardioids), 2-fl polynomials with polygonal boundaries, and n-dimensional Diracs and convex poly- topes. This work has been explored in a promising way in super- resolution algorithms and distributed compression, and might find its applications in photogrammetry, computer graphics, and ma- chine vision. [ABSTRACT FROM AUTHOR]

This paper presents a novel gradient-based image completion algorithm for removing significant objects from natural images or photographs. Our method reconstructs the region of removal in two phases. Firstly, the gradient maps in the removed area are completed through a patch-based filling algorithm. After that, the image is reconstructed from the gradient maps by solving a Poisson equation. A new patch-matching criterion is developed in our approach to govern the completion of gradient maps. Both the gradient and the color information are incorporated in this new criterion, so a better image completion result is obtained. Several examples and comparisons are given at the end of the paper to demonstrate the performance of our gradient-based image completion approach. [Copyright &y& Elsevier]

Rotational symmetry is important for many applications in computer graphics, vision, and image processing. However, it remains difficult to design an effective algorithm for automatic symmetry recognition. In this paper, we present a rotational symmetry detection algorithm, which is easy to use and can determine both the center and the radius of the rotational symmetry supporting region without human interaction. Our algorithm is derived from frieze-expansions approach and improved through a radius-based expansion idea. Multiresolution pyramid is used to accelerate this detection process. We also discuss a solution to deal with rotational symmetry detection under slight affine transformation. Experimental results show that the method is effective for most nature images with rotational symmetry. [ABSTRACT FROM AUTHOR]

Video segmentation is an important preprocessing step for many computer vision and graphics tasks. Its main goal is to group the voxels in the video volume with similar appearance and motion into spatio-temporally consistent supervoxels. In this paper, we formulate video segmentation as an L 0 gradient minimization problem, so that the spatio-temporal coherence can be effectively enforced through a gradient sparsity pursuit way. In our method, the appearance and motion descriptor space is first built for over-segmented image patches of each video frame. Then the L 0 gradient minimization is performed in the descriptor space, for both spatial and temporal dimensions. To solve the non-convex L 0 norm minimization problem, we extend the fused coordinate descent algorithm from 2D image grids to 3D video volume. We conduct quantitative evaluation of our method in a public video segmentation benchmark LIBSVX. The experimental results demonstrate our superior performance to state-of-the-arts in segmentation accuracy and undersegmentation error, and comparable performance in boundary recall and explained variation. [ABSTRACT FROM AUTHOR]

In this paper we survey all known (including own recent results) properties of the longest-edge n -section algorithms. These algorithms (in classical and recently designed conforming form) are nowadays used in many applications, including finite element simulations, computer graphics, etc. as a reliable tool for controllable mesh generation. In addition, we present a list of open problems arising in and around this topic. [ABSTRACT FROM AUTHOR]

The design of reinforced concrete sections of arbitrary shape, namely with variable geometry, holes as well as with arbitrary distribution of reinforcing steel bars, is a very common task in civil engineering, reinforced concrete structures. The design of these sections requires the integration of non-linear stress fields on complex shapes, because of the non-linear behavior of concrete in compression. In this paper, a novel algorithm is proposed to compute the ultimate strength of reinforced concrete sections under biaxial bending. The algorithm includes section subdivision into trapezoidal elements using the techniques of polygon clipping algorithm proposed by Weiler–Atherton. Exact numerical integration for normal strength concrete ( f ck ⩽ 50 MPa) is achieved, for each trapezoid, using the change of variables theorem followed by Gauss–Legendre integration. The proposed technique is hereafter referred to as WAGL (Weiler–Atherton, Gauss–Legendre). The verification of the proposed algorithm is performed by comparing analytical results between the WAGL technique and methods proposed by other authors (five examples). Additionally, the results obtained are also compared with experimental results available in the literature. The application of the WAGL technique is illustrated with two RC cross-section design examples. [ABSTRACT FROM AUTHOR]

Sequence alignment lies at heart of the bioinformatics. The Smith-Waterman algorithm is one of the key sequence search algorithms and has gained popularity due to improved implementations and rapidly increasing compute power. Recently, the Smith-Waterman algorithm has been successfully mapped onto the emerging general-purpose graphics processing units (GPUs). In this paper, we focused on how to improve the mapping, especially for short query sequences, by better usage of shared memory. We performed and evaluated the proposed method on two different platforms (Tesla C1060 and Tesla K20) and compared it with two classic methods in CUDASW++. Further, the performance on different numbers of threads and blocks has been analyzed. The results showed that the proposed method significantly improves Smith-Waterman algorithm on CUDA-enabled GPUs in proper allocation of block and thread numbers. [ABSTRACT FROM AUTHOR]

This paper discusses the hidden-surface problem from tile point of view of sorting. The various surfaces of an object to be shown in hidden-surface or hidden-line form must be sorted to find out which ones are visible at various places on the screen. Surfaces may be sorted by lateral position in the picture (X I'), by depth (Z), or by other criteria. The paper shows that the order of sorting and the types of sorting used form differences among the existing hidden-surface algorithms. To reduce the work of sorting, each algorithm capitalizes on some coherence property of the objects represented. ‘Scan-line coherence,’ the fact that one TV scan line of output is likely to be nearly the same as the previous TV scan line, is one commonly used kind of coherence. ‘Frame coherence,’ the fact that the entire picture does not change very much between successive frames of a motion picture can be very helpful if it is applicable. By systematically looking for additional kinds of coherence and untried sorting orders and sorting types, the paper is able to suggest two promising new approaches to the hidden-surface problem. The first, a combination of three existing algorithms, is promising because it would capitalize on both frame and scan-line coherence. The second new approach would sort in the order Y, Z, X, … the only sorting order for which an existing algorithm could not be found. [ABSTRACT FROM AUTHOR]

In our increasingly connected and instrumented world, live data recording the interactions between people, systems, and the environment is available in various domains, such as telecommunciations and social media. This data often takes the form of a temporally evolving graph, where entities are the vertices and the interactions between them are the edges. An important feature of this graph is that the number of edges it has grows continuously, as new interactions take place. We call such graphs interaction graphs. In this paper we study the problem of storing interaction graphs such that temporal queries on them can be answered efficiently. Since interaction graphs are append-only and edges are added continuously, traditional graph layout and storage algorithms that are batch based cannot be applied directly. We present the design and implementation of a system that caches recent interactions in memory, while quickly placing the expired interactions to disk blocks such that those edges that are likely to be accessed together are placed together. We develop live block formation algorithms that are fast, yet can take advantage of temporal and spatial locality among the edges to optimize the storage layout with the goal of improving query performance. We evaluate the system on synthetic as well as real-world interaction graphs, and show that our block formation algorithms are effective for answering temporal neighborhood queries on the graph. Such queries form a foundation for building more complex online and offline temporal analytics on interaction graphs. [ABSTRACT FROM AUTHOR]

In this paper, we present a novel fractal coding method with the block classification scheme based on a shared domain block pool. In our method, the domain block pool is called dictionary and is constructed from fractal Julia sets. The image is encoded by searching the best matching domain block with the same BTC (Block Truncation Coding) value in the dictionary. The experimental results show that the scheme is competent both in encoding speed and in reconstruction quality. Particularly for large images, the proposed method can avoid excessive growth of the computational complexity compared with the traditional fractal coding algorithm. [ABSTRACT FROM AUTHOR]

In this paper, we describe a new brute force algorithm for building the -Nearest Neighbor Graph (k-NNG). The k-NNG algorithm has many applications in areas such as machine learning, bio-informatics, and clustering analysis. While there are very efficient algorithms for data of low dimensions, for high dimensional data the brute force search is the best algorithm. There are two main parts to the algorithm: the first part is finding the distances between the input vectors, which may be formulated as a matrix multiplication problem; the second is the selection of the k-NNs for each of the query vectors. For the second part, we describe a novel graphics processing unit (GPU)-based multi-select algorithm based on quick sort. Our optimization makes clever use of warp voting functions available on the latest GPUs along with user-controlled cache. Benchmarks show significant improvement over state-of-the-art implementations of the k-NN search on GPUs. [ABSTRACT FROM AUTHOR]

The analysis of electrophysiological recordings often involves visual inspection of time series data to locate specific experiment epochs, mask artifacts, and verify the results of signal processing steps, such as filtering or spike detection. Long-term experiments with continuous data acquisition generate large amounts of data. Rapid browsing through these massive datasets poses a challenge to conventional data plotting software because the plotting time increases proportionately to the increase in the volume of data. This paper presents FTSPlot, which is a visualization concept for large-scale time series datasets using techniques from the field of high performance computer graphics, such as hierarchic level of detail and out-of-core data handling. In a preprocessing step, time series data, event, and interval annotations are converted into an optimized data format, which then permits fast, interactive visualization. The preprocessing step has a computational complexity of ; the visualization itself can be done with a complexity of and is therefore independent of the amount of data. A demonstration prototype has been implemented and benchmarks show that the technology is capable of displaying large amounts of time series data, event, and interval annotations lag-free with ms. The current 64-bit implementation theoretically supports datasets with up to bytes, on the x86_64 architecture currently up to bytes are supported, and benchmarks have been conducted with bytes/1 TiB or double precision samples. The presented software is freely available and can be included as a Qt GUI component in future software projects, providing a standard visualization method for long-term electrophysiological experiments. [ABSTRACT FROM AUTHOR]

The Student's-t mixture model, which is heavily tailed and more robust than the Gaussian mixture model, has recently received great attention on image processing. In this paper, we propose a robust non-rigid point set registration algorithm using the Student's-t mixture model. Specifically, first, we consider the alignment of two point sets as a probability density estimation problem and treat one point set as Student's-t mixture model centroids. Then, we fit the Student's-t mixture model centroids to the other point set which is treated as data. Finally, we get the closed-form solutions of registration parameters, leading to a computationally efficient registration algorithm. The proposed algorithm is especially effective for addressing the non-rigid point set registration problem when significant amounts of noise and outliers are present. Moreover, less registration parameters have to be set manually for our algorithm compared to the popular coherent points drift (CPD) algorithm. We have compared our algorithm with other state-of-the-art registration algorithms on both 2D and 3D data with noise and outliers, where our non-rigid registration algorithm showed accurate results and outperformed the other algorithms. [ABSTRACT FROM AUTHOR]

Multiple sequence alignment is a crucial task in a number of biological analyses like secondary structure prediction, domain searching, phylogeny, etc. MSAProbs is currently the most accurate alignment algorithm, but its effectiveness is obtained at the expense of computational time. In the paper we present QuickProbs, the variant of MSAProbs customised for graphics processors. We selected the two most time consuming stages of MSAProbs to be redesigned for GPU execution: the posterior matrices calculation and the consistency transformation. Experiments on three popular benchmarks (BAliBASE, PREFAB, OXBench-X) on quad-core PC equipped with high-end graphics card show QuickProbs to be 5.7 to 9.7 times faster than original CPU-parallel MSAProbs. Additional tests performed on several protein families from Pfam database give overall speed-up of 6.7. Compared to other algorithms like MAFFT, MUSCLE, or ClustalW, QuickProbs proved to be much more accurate at similar speed. Additionally we introduce a tuned variant of QuickProbs which is significantly more accurate on sets of distantly related sequences than MSAProbs without exceeding its computation time. The GPU part of QuickProbs was implemented in OpenCL, thus the package is suitable for graphics processors produced by all major vendors. [ABSTRACT FROM AUTHOR]

The part-based method has been a fast rising framework for object detection. It is attracting more and more attention for its detection precision and partial robustness to the occlusion. However, little research has been focused on the problem of occlusion overlapping of the part regions, which can reduce the performance of the system. This paper proposes a part-based probabilistic model and the corresponding inference algorithm for the problem of the part occlusion. The model is based on the Bayesian theory integrally and aims to be robust to the large occlusion. In the stage of the model construction, all of the parts constitute the vertex set of a fully connected graph, and a binary variable is assigned to each part to indicate its occlusion status. In addition, we introduce a penalty term to regularize the argument space of the objective function. Thus, the part detection is formulated as an optimization problem, which is divided into two alternative procedures: the outer inference and the inner inference. A stochastic tentative method is employed in the outer inference to determine the occlusion status for each part. In the inner inference, the gradient descent algorithm is employed to find the optimal positions of the parts, in term of the current occlusion status. Experiments were carried out on the Caltech database. The results demonstrated that the proposed method achieves a strong robustness to the occlusion. [ABSTRACT FROM AUTHOR]

Voxel-based data structures, algorithms, frameworks, and interfaces have been used in computer graphics and many other applications for decades. There is a general necessity to seek adequate digital representations, such as voxels, that would secure unified data structures, multi-resolution options, robust validation procedures and flexible algorithms for different 3D tasks. In this review, we evaluate the most common properties and algorithms for voxelisation of 2D and 3D objects. Thus, many voxelisation algorithms and their characteristics are presented targeting points, lines, triangles, surfaces and solids as geometric primitives. For lines, we identify three groups of algorithms, where the first two achieve different voxelisation connectivity, while the third one presents voxelisation of curves. We can say that surface voxelisation is a more desired voxelisation type compared to solid voxelisation, as it can be achieved faster and requires less memory if voxels are stored in a sparse way. At the same time, we evaluate in the paper the available voxel data structures. We split all data structures into static and dynamic grids considering the frequency to update a data structure. Static grids are dominated by SVO-based data structures focusing on memory footprint reduction and attributes preservation, where SVDAG and SSVDAG are the most advanced methods. The state-of-the-art dynamic voxel data structure is NanoVDB which is superior to the rest in terms of speed as well as support for out-of-core processing and data management, which is the key to handling large dynamically changing scenes. Overall, we can say that this is the first review evaluating the available voxelisation algorithms for different geometric primitives as well as voxel data structures. [ABSTRACT FROM AUTHOR]

Abstract: Parallel implementations of Ray Tracing have been enabling real time performance, as the algorithm is embarrassingly parallel. However, in order to achieve both interactivity and real time performance, the algorithm should run at a high frame rates, i.e. at least 60 frames per second. Thus, a custom parallel design in hardware is likely to achieve high rendering performance. In this paper, we improve the GridRT architecture presented in previous work. GridRT is capable of dealing with the main desirable features of Ray Tracing, such as shadows and reflection effects, imposing low area cost and a promising rendering performance. As to this work, an application-specific instruction has been added and the underlaying computation embedded into the processor’s microprogram in order to calculate the ray–triangle intersection computations. These computations are performed in pipeline, whenever possible, yielding to a considerable reduction in terms of cycles per intersection test. The presented architecture is based on the uniform grid acceleration structure. It allows for a massive twofold parallelism: parallel ray–triangle intersection tests as well as parallel processing of many rays. A hardware implementation of the improved architecture is presented, together with the corresponding performance results and resources requirements. The rendering time is reduced by 80% using a grid configuration of eight processing elements and each intersection computation time is reduced by 50% with respect to the original GridRT implementation. [Copyright &y& Elsevier]

Typical data visualizations result from linear pipelines that start by characterizing data using a model or algorithm to reduce the dimension and summarize structure, and end by displaying the data in a reduced dimensional form. Sensemaking may take place at the end of the pipeline when users have an opportunity to observe, digest, and internalize any information displayed. However, some visualizations mask meaningful data structures when model or algorithm constraints (e.g., parameter specifications) contradict information in the data. Yet, due to the linearity of the pipeline, users do not have a natural means to adjust the displays. In this paper, we present a framework for creating dynamic data displays that rely on both mechanistic data summaries and expert judgement. The key is that we develop both the theory and methods of a new human-data interaction to which we refer as “ Visual to Parametric Interaction” (V2PI). With V2PI, the pipeline becomes bi-directional in that users are embedded in the pipeline; users learn from visualizations and the visualizations adjust to expert judgement. We demonstrate the utility of V2PI and a bi-directional pipeline with two examples. [ABSTRACT FROM AUTHOR]

Abstract: Realistic rain simulation is a challenging problem due to the variety of different phenomena to consider. In this paper we propose a new rain rendering algorithm that extends present state of the art in the field, achieving real-time rendering of rain streaks and splashes with complex illumination effects, along with fog, halos and light glows as hints of the participating media. Our algorithm creates particles in the scene using an artist-defined storm distribution (e.g., provided as a 2D cloud distribution). Unlike previous algorithms, no restrictions are imposed on the rain area dimension or shape. Our technique adaptively samples the storm area to simulate rain particles only in the relevant regions and only around the observer. Particle simulation is executed entirely in the graphics hardware, by placing the particles at their updated coordinates at each time-step, also checking for collisions with the scene. To render the rain streaks, we use precomputed images and combine them to achieve complex illumination effects. Several optimizations are introduced to render realistic rain with virtually millions of falling rain droplets. [Copyright &y& Elsevier]

With the advance of embedded sensing devices, Pervasive Urban Sensing (PUS) with probe vehicles is becoming increasingly practical. A probe vehicle is equipped with onboard sensing devices that detect urban information as the probe vehicle drive across the road network. For example, GPS sensors can detect real-time vehicle status including instant speed and physical position. PUS can provide the general public valuable urban sensing information, such as frequently updated digital maps, and real-time traffic light states. In this paper, we first present the framework of Pervasive Urban Sensing with probe vehicles. Next, we present two cases of urban sensing with probe vehicles. As case one, we discuss the design of a sensing algorithm for detecting the instant state of traffic lights. As case two, we discuss the design of sensing algorithms for recognizing roads by using the vehicular footprints. Some preliminary results of these two cases of urban sensing are presented and discussed. [ABSTRACT FROM AUTHOR]

This paper deals with the problem of detecting "weak symmetry" in a polygon, which is a special bijective and continuous mapping between the vertices of the given polygon. An application of this work is the automatic reconstruction of 3D polygons symmetric with respect to a plane from free-hand sketches of weakly-symmetric 2D polygons. We formalize the weak-symmetry notion and highlight its many properties which lead to an algorithm detecting it. The closest research work to the proposed approach is the detection of skewed symmetry. Skewed symmetry detection deals only with reconstruction of planar mirror-symmetric 3D polygons while our method is able to identify symmetry in projections of planar as well as nonplanar mirror-symmetric 3D polygons. [ABSTRACT FROM AUTHOR]

This paper presents a high-speed image processing algorithm applied to multifaceted asymmetric radiation from the edge detection on Joint European Torus. The algorithm has been developed in C/C++ language using the OpenCV library for image processing and the LibSVM library for pattern classification and has been tested on a dedicated Intel 64-bit Linux computing platform. The code implemented achieves at the same time high accuracy and good run-time performance. The final version presents a correct detection rate of 93.3\% and an average image processing rate of 650 frames per second. A complete analysis of each image processing module is presented to illustrate the overall characteristics and performance of the algorithm. [ABSTRACT FROM PUBLISHER]

Abstract: In many applications, the first step into the topological analysis of a discrete point set P sampled from a manifold is the construction of a simplicial complex with vertices on P. In this paper, we present an algorithm for the efficient computation of the Čech complex of P for a given value of the radius of the covering balls. Experiments show that the proposed algorithm can generally handle input sets of several thousand points, while for the topologically most interesting small values of can handle inputs with tens of thousands of points. We also present an algorithm for the construction of all possible Čech complices on P. [Copyright &y& Elsevier]

Abstract: In the graph searching game the opponents are a set of searchers and a fugitive in a graph. The searchers try to capture the fugitive by applying some sequence of moves that include placement, removal, or sliding of a searcher along an edge. The fugitive tries to avoid capture by moving along unguarded paths. The search number of a graph is the minimum number of searchers required to guarantee the capture of the fugitive. In this paper, we initiate the study of this game under the natural restriction of connectivity where we demand that in each step of the search the locations of the graph that are clean (i.e. non-accessible to the fugitive) remain connected. We give evidence that many of the standard mathematical tools used so far in classic graph searching fail under the connectivity requirement. We also settle the question on “the price of connectivity”, that is, how many searchers more are required for searching a graph when the connectivity demand is imposed. We make estimations of the price of connectivity on general graphs and we provide tight bounds for the case of trees. In particular, for an n-vertex graph the ratio between the connected searching number and the non-connected one is while for trees this ratio is always at most 2. We also conjecture that this constant-ratio upper bound for trees holds also for all graphs. Our combinatorial results imply a complete characterization of connected graph searching on trees. It is based on a forbidden-graph characterization of the connected search number. We prove that the connected search game is monotone for trees, i.e. restricting search strategies to only those where the clean territories increase monotonically does not require more searchers. A consequence of our results is that the connected search number can be computed in polynomial time on trees, moreover, we show how to make this algorithm distributed. Finally, we reveal connections of this parameter to other invariants on trees such as the Horton–Strahler number. [Copyright &y& Elsevier]

In real world images, many algorithms for adaptive contours detection exist and various improvements to the contours detection have been proposed. The reason for such diversity is that real world images contains heterogeneous mixtures of features and each of the available algorithms exploits some of these features. Thus, depending on the image, different algorithms shows different quality of result. In this paper we propose a method that improves the result adaptive contours detection by using an algorithm selection approach. Previous methods using the algorithm selection approach have been focusing only on images with a particular class of features (artificial, cellular) because of the complexity of real world images. In order to successfully solve this problem we first determine a set of distinctive features of each algorithm using machine learning. Then using these distinctive features we teach an algorithm selector to select best algorithm when a set of features is provided. Finally, we propose a method to split the input image into sub regions that are selected in such a manner that improves the quality of the image processing result. The proposed algorithm is verified on the set of benchmarks and its performance is comparable and better in many cases than the currently best contour detection algorithms. [ABSTRACT FROM AUTHOR]

Information theory traditionally deals with “conventional data,” be it textual data, image, or video data. However, databases of various sorts have come into existence in recent years for storing “unconventional data” including biological data, social data, web data, topographical maps, and medical data. In compressing such data, one must consider two types of information: the information conveyed by the structure itself, and the information conveyed by the data labels implanted in the structure. In this paper, we attempt to address the former problem by studying information of graphical structures (i.e., unlabeled graphs). As the first step, we consider the Erdös–Rényi graphs \cal G(n,p) over n vertices in which edges are added independently and randomly with probability p. We prove that the structural entropy of \cal G(n,p) is $n\choose 2h(p)-\log n!+o(1)=n\choose2h(p)-n\log n+O(n),$ where h(p)=-p\log p-(1-p)\log (1-p) is the entropy rate of a conventional memoryless binary source. Then, we propose a two-stage compression algorithm that asymptotically achieves the structural entropy up to the n\log n term (i.e., the first two leading terms) of the structural entropy. Our algorithm runs either in time O(n^2) in the worst case for any graph or in time O(n+e) on average for graphs generated by \cal G(n,p), where e is the average number of edges. To the best of our knowledge, this is the first provable (asymptotically) optimal graph compressor for Erdös-Rényi graph models. We use combinatorial and analytic techniques such as generating functions, Mellin transform, and poissonization to establish these findings. Our experiments confirm the theoretical results and also show the usefulness of our algorithm for some real-world graphs such as the Internet, biological networks, and social networks. [ABSTRACT FROM PUBLISHER]

In this paper, an optimal tuning tool is presented for control structures based on multivariable proportional-integral-derivative (PID) control, using genetic algorithms as an alternative to traditional optimization algorithms. From an educational point of view, this tool provides students with the necessary means to consolidate their knowledge on these control structures, which are of particular relevance in control engineering. The graphical user interface designed for the tool allows for the following: the selection of the control structure, the desired decoupling, the type of PID, the analysis of the interaction effects through relative gain array (RGA), the planning of several optimal tuning processes, the comparison of different designs (through graphics or the numeric results obtained), and the management of data files saved during the planned optimal tunings process. The developed tool was made available to students for them to solve a practical problem and, subsequently, the impact of its use was evaluated. [ABSTRACT FROM PUBLISHER]

The radiosity method is usually employed for the rendering of highly realistic synthetic images. In this paper we present an implementation of the Monte Carlo radiosity algorithm on the GPU using CUDA. Our proposal is based on the partition of the scene into sub-scenes to be processed in parallel to exploit the graphics card structure. The convex partition method employed permits the exploitation of data locality and the optimization of the ray shooting procedure due to the minimization of the number of objects to be tested in the intersection calculation. The results are good in terms of execution times, increasing the flexibility of previous solutions and demonstrating that the GPU can outperform the CPU results even for non-regular algorithms. [ABSTRACT FROM AUTHOR]

Abstract: Silhouettes of polyhedra are an important primitive in application areas such as machine vision and computer graphics. In this paper, we study how to select view points of convex polyhedra such that the silhouette satisfies certain properties. Specifically, we give algorithms to find all projections of a convex polyhedron such that a given set of edges, faces and/or vertices appear on the silhouette. We present an algorithm to solve this problem in time for k edges. For orthogonal projections, we give an improved algorithm that is fully adaptive in the number l of connected components formed by the edges, and has a time complexity of . We then generalize this algorithm to edges and/or faces appearing on the silhouette. [Copyright &y& Elsevier]